GaloisInc / cclyzerpp

cclyzer++ is a precise and scalable pointer analysis for LLVM code.
https://galoisinc.github.io/cclyzerpp/
BSD 3-Clause "New" or "Revised" License
134 stars 15 forks source link

bug: Callgraph changed in test program #69

Closed langston-barrett closed 1 year ago

langston-barrett commented 1 year ago

Recent changes introduced a bug. In particular, the callgraph for this program is different between the initial commit (e224763fd3024549be0599c48b0e7c29b58a5d25) and a later one (d96ff8dd3a21e14504df3d38632df96670921a9e) even though no functional changes have been introduced during this time.

C program ```c /* MIT License Copyright (c) 2019 yuawn Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ #include #include #include void init() { setvbuf(stdout, 0, 2, 0); setvbuf(stdin, 0, 2, 0); setvbuf(stderr, 0, 2, 0); } int read_int() { char buf[0x10]; __read_chk(0, buf, 0xf, 0x10); return atoi(buf); } void welcome_func() { puts("Hello ~~~"); } void bye_func() { puts("Bye ~~~"); } void menu() { puts("1. add a box"); puts("2. exit"); puts(">"); } struct MessageBox { void (*welcome)(); void (*bye)(); }; void backdoor() { system("sh"); } int main() { init(); struct MessageBox *msgbox = (struct MessageBox *)malloc(sizeof(struct MessageBox)); msgbox->welcome = welcome_func; msgbox->bye = bye_func; msgbox->welcome(); free(msgbox); int n = 3, size; char *msg; while (n--) { printf("Size of your message: "); size = read_int(); msg = (char *)malloc(size); printf("Message: "); read(0, msg, size); printf("Saved message: %s\n", msg); free(msg); } msgbox->bye(); return 0; } ```
langston-barrett commented 1 year ago

The issue is present in 63793e68bfff36b3831e9cdc59a4b23dbd55907f; it is not yet present in 6a18607524ced07fa0933bc1b2c0bdc3d7103143.

langston-barrett commented 1 year ago

It is not yet present in 8da3c20bbd611fdf83fe3462691256e226f1c3b2 nor 60d20598b16a1dc4dd5e341ab3796ebcfd7d20fc, so it must have been introduced in 63793e68bfff36b3831e9cdc59a4b23dbd55907f.

langston-barrett commented 1 year ago
Full diff ``` [WARN] No relation at 60d2059/_landingpad_instruction_filter_clause.csv.gz 63793e6/indirect_call_or_invoke_instruction.csv differs from 60d2059/indirect_call_or_invoke_instruction.csv --- 63793e6/indirect_call_or_invoke_instruction.csv 2022-10-12 20:56:56.826387002 +0000 +++ 60d2059/indirect_call_or_invoke_instruction.csv 2022-10-12 20:48:22.411161272 +0000 @@ -1,3 +1 @@ -:main:17 :main:23 -:read_int:3 63793e6/alloc_context.csv differs from 60d2059/alloc_context.csv --- 63793e6/alloc_context.csv 2022-10-12 20:56:56.808387006 +0000 +++ 60d2059/alloc_context.csv 2022-10-12 20:48:22.396161252 +0000 @@ -9,12 +9,10 @@ [:main:12, nil] [:main:15, nil] [:main:16, nil] -[:main:17, nil] [:main:18, nil] [:main:19, nil] [:main:8, nil] [:read_int:2, nil] -[:read_int:3, nil] [:read_int:5, nil] [:welcome_func:0, nil] nil 63793e6/subset.callgraph.callgraph_edge.csv differs from 60d2059/subset.callgraph.callgraph_edge.csv --- 63793e6/subset.callgraph.callgraph_edge.csv 2022-10-12 20:56:56.835387000 +0000 +++ 60d2059/subset.callgraph.callgraph_edge.csv 2022-10-12 20:48:22.420161285 +0000 @@ -1,3 +1,4 @@ +[<>, nil] :read [<>, nil] :main:17 [:bye_func:0, nil] :puts nil :bye_func:0 [:init:1, nil] :setvbuf nil :init:1 [:init:3, nil] :setvbuf nil :init:3 @@ -6,14 +7,13 @@ [:main:12, nil] :printf [<>, nil] :main:12 [:main:15, nil] :malloc [<>, nil] :main:15 [:main:16, nil] :printf [<>, nil] :main:16 -[:main:17, nil] :read [<>, nil] :main:17 [:main:18, nil] :printf [<>, nil] :main:18 [:main:19, nil] :free [<>, nil] :main:19 [:main:8, nil] :free [<>, nil] :main:8 [:read_int:2, nil] :llvm.lifetime.start.p0i8 nil :read_int:2 -[:read_int:3, nil] :__read_chk nil :read_int:3 [:read_int:5, nil] :llvm.lifetime.end.p0i8 nil :read_int:5 [:welcome_func:0, nil] :puts nil :welcome_func:0 +nil :__read_chk nil :read_int:3 nil :atoi nil :read_int:4 nil :bye_func [<>, nil] :main:23 nil :init [<>, nil] :main:0 63793e6/drop_last.csv differs from 60d2059/drop_last.csv --- 63793e6/drop_last.csv 2022-10-12 20:56:56.767387016 +0000 +++ 60d2059/drop_last.csv 2022-10-12 20:48:22.351161189 +0000 @@ -9,11 +9,9 @@ nil [:main:12, nil] nil [:main:15, nil] nil [:main:16, nil] -nil [:main:17, nil] nil [:main:18, nil] nil [:main:19, nil] nil [:main:8, nil] nil [:read_int:2, nil] -nil [:read_int:3, nil] nil [:read_int:5, nil] nil [:welcome_func:0, nil] [WARN] No relation at 60d2059/_landingpad_instruction_filter_clause.csv 63793e6/max_num_callsites.csv differs from 60d2059/max_num_callsites.csv --- 63793e6/max_num_callsites.csv 2022-10-12 20:56:56.747387021 +0000 +++ 60d2059/max_num_callsites.csv 2022-10-12 20:48:22.332161163 +0000 @@ -1,4 +1,4 @@ -:__read_chk 3 +:__read_chk 1 :atoi 1 :backdoor 1 :bye_func 1 @@ -11,7 +11,7 @@ :menu 1 :printf 3 :puts 5 -:read 3 +:read 1 :read_int 1 :setvbuf 3 :strtol 1 [WARN] No relation at 60d2059/_phi_instruction_pair_label.csv.gz [WARN] No relation at 60d2059/_switch_instruction_case_label.csv 63793e6/subset._merge.merge.csv differs from 60d2059/subset._merge.merge.csv --- 63793e6/subset._merge.merge.csv 2022-10-12 20:56:56.835387000 +0000 +++ 60d2059/subset._merge.merge.csv 2022-10-12 20:48:22.421161286 +0000 @@ -1,3 +1,4 @@ +[<>, nil] :main:17 [<>, nil] [:bye_func:0, nil] :bye_func:0 nil [:init:1, nil] :init:1 nil [:init:3, nil] :init:3 nil @@ -6,12 +7,10 @@ [:main:12, nil] :main:12 [<>, nil] [:main:15, nil] :main:15 [<>, nil] [:main:16, nil] :main:16 [<>, nil] -[:main:17, nil] :main:17 [<>, nil] [:main:18, nil] :main:18 [<>, nil] [:main:19, nil] :main:19 [<>, nil] [:main:8, nil] :main:8 [<>, nil] [:read_int:2, nil] :read_int:2 nil -[:read_int:3, nil] :read_int:3 nil [:read_int:5, nil] :read_int:5 nil [:welcome_func:0, nil] :welcome_func:0 nil nil :atoi:0 nil @@ -19,4 +18,5 @@ nil :main:13 [<>, nil] nil :main:23 [<>, nil] nil :main:7 [<>, nil] +nil :read_int:3 nil nil :read_int:4 nil [WARN] No relation at 60d2059/_variable_in_function.csv [WARN] No relation at 60d2059/_basicblock_preds.csv 63793e6/context_depth.csv differs from 60d2059/context_depth.csv --- 63793e6/context_depth.csv 2022-10-12 20:56:56.764387017 +0000 +++ 60d2059/context_depth.csv 2022-10-12 20:48:22.349161186 +0000 @@ -10,11 +10,9 @@ 1 [:main:12, nil] 1 [:main:15, nil] 1 [:main:16, nil] -1 [:main:17, nil] 1 [:main:18, nil] 1 [:main:19, nil] 1 [:main:8, nil] 1 [:read_int:2, nil] -1 [:read_int:3, nil] 1 [:read_int:5, nil] 1 [:welcome_func:0, nil] [WARN] No relation at 60d2059/_basicblock_preds.csv.gz [WARN] No relation at 60d2059/_variable_in_function.csv.gz [WARN] No relation at 60d2059/_phi_instruction_pair_value.csv 63793e6/context_to_string.csv differs from 60d2059/context_to_string.csv --- 63793e6/context_to_string.csv 2022-10-12 20:56:56.804387007 +0000 +++ 60d2059/context_to_string.csv 2022-10-12 20:48:22.391161245 +0000 @@ -9,12 +9,10 @@ [:main:12, nil] :main:12#nil [:main:15, nil] :main:15#nil [:main:16, nil] :main:16#nil -[:main:17, nil] :main:17#nil [:main:18, nil] :main:18#nil [:main:19, nil] :main:19#nil [:main:8, nil] :main:8#nil [:read_int:2, nil] :read_int:2#nil -[:read_int:3, nil] :read_int:3#nil [:read_int:5, nil] :read_int:5#nil [:welcome_func:0, nil] :welcome_func:0#nil nil nil [WARN] No relation at 60d2059/_switch_instruction_case_label.csv.gz [WARN] No relation at 60d2059/_landingpad_instruction_catch_clause.csv.gz 63793e6/subset._merge.count_context_items.csv differs from 60d2059/subset._merge.count_context_items.csv --- 63793e6/subset._merge.count_context_items.csv 2022-10-12 20:56:56.815387004 +0000 +++ 60d2059/subset._merge.count_context_items.csv 2022-10-12 20:48:22.402161260 +0000 @@ -6,7 +6,6 @@ :main:12 1 :main:15 1 :main:16 1 -:main:17 1 :main:18 1 :main:19 1 :main:8 1 @@ -14,6 +13,5 @@ :menu:1 1 :menu:2 1 :read_int:2 1 -:read_int:3 1 :read_int:5 1 :welcome_func:0 1 63793e6/context.csv differs from 60d2059/context.csv --- 63793e6/context.csv 2022-10-12 20:56:56.786387011 +0000 +++ 60d2059/context.csv 2022-10-12 20:48:22.372161218 +0000 @@ -9,12 +9,10 @@ [:main:12, nil] [:main:15, nil] [:main:16, nil] -[:main:17, nil] [:main:18, nil] [:main:19, nil] [:main:8, nil] [:read_int:2, nil] -[:read_int:3, nil] [:read_int:5, nil] [:welcome_func:0, nil] nil [WARN] No relation at 60d2059/_constant_in_function.csv.gz [WARN] No relation at 60d2059/_switch_instruction_case_value.csv 63793e6/subset._merge.count_contexts.csv differs from 60d2059/subset._merge.count_contexts.csv --- 63793e6/subset._merge.count_contexts.csv 2022-10-12 20:56:56.781387013 +0000 +++ 60d2059/subset._merge.count_contexts.csv 2022-10-12 20:48:22.366161210 +0000 @@ -6,7 +6,6 @@ :main:12 1 :main:15 1 :main:16 1 -:main:17 1 :main:18 1 :main:19 1 :main:8 1 @@ -14,6 +13,5 @@ :menu:1 0 :menu:2 0 :read_int:2 1 -:read_int:3 1 :read_int:5 1 :welcome_func:0 1 [WARN] No relation at 60d2059/_switch_instruction_case_value.csv.gz [WARN] No relation at 60d2059/_instruction_bb_entry.csv 63793e6/context_item_by_invoc.csv differs from 60d2059/context_item_by_invoc.csv --- 63793e6/context_item_by_invoc.csv 2022-10-12 20:56:56.821387003 +0000 +++ 60d2059/context_item_by_invoc.csv 2022-10-12 20:48:22.407161267 +0000 @@ -6,7 +6,6 @@ :main:12 :main:12 :main:15 :main:15 :main:16 :main:16 -:main:17 :main:17 :main:18 :main:18 :main:19 :main:19 :main:8 :main:8 @@ -14,6 +13,5 @@ :menu:1 :menu:1 :menu:2 :menu:2 :read_int:2 :read_int:2 -:read_int:3 :read_int:3 :read_int:5 :read_int:5 :welcome_func:0 :welcome_func:0 [WARN] No relation at 60d2059/_phi_instruction_pair_value.csv.gz 63793e6/drop_context_item_by_invoc.csv differs from 60d2059/drop_context_item_by_invoc.csv --- 63793e6/drop_context_item_by_invoc.csv 2022-10-12 20:56:56.790387011 +0000 +++ 60d2059/drop_context_item_by_invoc.csv 2022-10-12 20:48:22.376161224 +0000 @@ -1,4 +1,6 @@ :atoi:0 :backdoor:0 :main:13 +:main:17 +:read_int:3 :read_int:4 [WARN] No relation at 60d2059/_constant_in_function.csv [WARN] No relation at 60d2059/_landingpad_instruction_catch_clause.csv [WARN] No relation at 60d2059/_phi_instruction_pair_label.csv 63793e6/indirect_call_instruction.csv differs from 60d2059/indirect_call_instruction.csv --- 63793e6/indirect_call_instruction.csv 2022-10-12 20:56:56.793387010 +0000 +++ 60d2059/indirect_call_instruction.csv 2022-10-12 20:48:22.380161229 +0000 @@ -1,3 +1 @@ -:main:17 :main:23 -:read_int:3 63793e6/num_indirect_calls_to_compatible_func.csv differs from 60d2059/num_indirect_calls_to_compatible_func.csv --- 63793e6/num_indirect_calls_to_compatible_func.csv 2022-10-12 20:56:56.822387003 +0000 +++ 60d2059/num_indirect_calls_to_compatible_func.csv 2022-10-12 20:48:22.408161268 +0000 @@ -1,8 +1,10 @@ +0 :__read_chk 0 :atoi 0 :main 0 :malloc 0 :printf 0 :puts +0 :read 0 :read_int 0 :setvbuf 0 :strtol @@ -15,5 +17,3 @@ 1 :llvm.lifetime.start.p0i8 1 :menu 1 :welcome_func -2 :__read_chk -2 :read [WARN] No relation at 60d2059/_instruction_bb_entry.csv.gz [WARN] No relation at 63793e6/switch_instruction_case_value.csv [WARN] No relation at 63793e6/landingpad_instruction_catch_clause.csv.gz [WARN] No relation at 63793e6/phi_instruction_pair_label.csv.gz 60d2059/indirect_call_or_invoke_instruction.csv differs from 63793e6/indirect_call_or_invoke_instruction.csv --- 60d2059/indirect_call_or_invoke_instruction.csv 2022-10-12 20:48:22.411161272 +0000 +++ 63793e6/indirect_call_or_invoke_instruction.csv 2022-10-12 20:56:56.826387002 +0000 @@ -1 +1,3 @@ +:main:17 :main:23 +:read_int:3 60d2059/alloc_context.csv differs from 63793e6/alloc_context.csv --- 60d2059/alloc_context.csv 2022-10-12 20:48:22.396161252 +0000 +++ 63793e6/alloc_context.csv 2022-10-12 20:56:56.808387006 +0000 @@ -9,10 +9,12 @@ [:main:12, nil] [:main:15, nil] [:main:16, nil] +[:main:17, nil] [:main:18, nil] [:main:19, nil] [:main:8, nil] [:read_int:2, nil] +[:read_int:3, nil] [:read_int:5, nil] [:welcome_func:0, nil] nil 60d2059/subset.callgraph.callgraph_edge.csv differs from 63793e6/subset.callgraph.callgraph_edge.csv --- 60d2059/subset.callgraph.callgraph_edge.csv 2022-10-12 20:48:22.420161285 +0000 +++ 63793e6/subset.callgraph.callgraph_edge.csv 2022-10-12 20:56:56.835387000 +0000 @@ -1,4 +1,3 @@ -[<>, nil] :read [<>, nil] :main:17 [:bye_func:0, nil] :puts nil :bye_func:0 [:init:1, nil] :setvbuf nil :init:1 [:init:3, nil] :setvbuf nil :init:3 @@ -7,13 +6,14 @@ [:main:12, nil] :printf [<>, nil] :main:12 [:main:15, nil] :malloc [<>, nil] :main:15 [:main:16, nil] :printf [<>, nil] :main:16 +[:main:17, nil] :read [<>, nil] :main:17 [:main:18, nil] :printf [<>, nil] :main:18 [:main:19, nil] :free [<>, nil] :main:19 [:main:8, nil] :free [<>, nil] :main:8 [:read_int:2, nil] :llvm.lifetime.start.p0i8 nil :read_int:2 +[:read_int:3, nil] :__read_chk nil :read_int:3 [:read_int:5, nil] :llvm.lifetime.end.p0i8 nil :read_int:5 [:welcome_func:0, nil] :puts nil :welcome_func:0 -nil :__read_chk nil :read_int:3 nil :atoi nil :read_int:4 nil :bye_func [<>, nil] :main:23 nil :init [<>, nil] :main:0 60d2059/drop_last.csv differs from 63793e6/drop_last.csv --- 60d2059/drop_last.csv 2022-10-12 20:48:22.351161189 +0000 +++ 63793e6/drop_last.csv 2022-10-12 20:56:56.767387016 +0000 @@ -9,9 +9,11 @@ nil [:main:12, nil] nil [:main:15, nil] nil [:main:16, nil] +nil [:main:17, nil] nil [:main:18, nil] nil [:main:19, nil] nil [:main:8, nil] nil [:read_int:2, nil] +nil [:read_int:3, nil] nil [:read_int:5, nil] nil [:welcome_func:0, nil] [WARN] No relation at 63793e6/constant_in_fn.csv.gz 60d2059/max_num_callsites.csv differs from 63793e6/max_num_callsites.csv --- 60d2059/max_num_callsites.csv 2022-10-12 20:48:22.332161163 +0000 +++ 63793e6/max_num_callsites.csv 2022-10-12 20:56:56.747387021 +0000 @@ -1,4 +1,4 @@ -:__read_chk 1 +:__read_chk 3 :atoi 1 :backdoor 1 :bye_func 1 @@ -11,7 +11,7 @@ :menu 1 :printf 3 :puts 5 -:read 1 +:read 3 :read_int 1 :setvbuf 3 :strtol 1 [WARN] No relation at 63793e6/landingpad_instruction_catch_clause.csv [WARN] No relation at 63793e6/basicblock_preds.csv 60d2059/subset._merge.merge.csv differs from 63793e6/subset._merge.merge.csv --- 60d2059/subset._merge.merge.csv 2022-10-12 20:48:22.421161286 +0000 +++ 63793e6/subset._merge.merge.csv 2022-10-12 20:56:56.835387000 +0000 @@ -1,4 +1,3 @@ -[<>, nil] :main:17 [<>, nil] [:bye_func:0, nil] :bye_func:0 nil [:init:1, nil] :init:1 nil [:init:3, nil] :init:3 nil @@ -7,10 +6,12 @@ [:main:12, nil] :main:12 [<>, nil] [:main:15, nil] :main:15 [<>, nil] [:main:16, nil] :main:16 [<>, nil] +[:main:17, nil] :main:17 [<>, nil] [:main:18, nil] :main:18 [<>, nil] [:main:19, nil] :main:19 [<>, nil] [:main:8, nil] :main:8 [<>, nil] [:read_int:2, nil] :read_int:2 nil +[:read_int:3, nil] :read_int:3 nil [:read_int:5, nil] :read_int:5 nil [:welcome_func:0, nil] :welcome_func:0 nil nil :atoi:0 nil @@ -18,5 +19,4 @@ nil :main:13 [<>, nil] nil :main:23 [<>, nil] nil :main:7 [<>, nil] -nil :read_int:3 nil nil :read_int:4 nil 60d2059/context_depth.csv differs from 63793e6/context_depth.csv --- 60d2059/context_depth.csv 2022-10-12 20:48:22.349161186 +0000 +++ 63793e6/context_depth.csv 2022-10-12 20:56:56.764387017 +0000 @@ -10,9 +10,11 @@ 1 [:main:12, nil] 1 [:main:15, nil] 1 [:main:16, nil] +1 [:main:17, nil] 1 [:main:18, nil] 1 [:main:19, nil] 1 [:main:8, nil] 1 [:read_int:2, nil] +1 [:read_int:3, nil] 1 [:read_int:5, nil] 1 [:welcome_func:0, nil] [WARN] No relation at 63793e6/landingpad_instruction_filter_clause.csv.gz [WARN] No relation at 63793e6/landingpad_instruction_filter_clause.csv [WARN] No relation at 63793e6/switch_instruction_case_label.csv [WARN] No relation at 63793e6/switch_instruction_case_value.csv.gz 60d2059/context_to_string.csv differs from 63793e6/context_to_string.csv --- 60d2059/context_to_string.csv 2022-10-12 20:48:22.391161245 +0000 +++ 63793e6/context_to_string.csv 2022-10-12 20:56:56.804387007 +0000 @@ -9,10 +9,12 @@ [:main:12, nil] :main:12#nil [:main:15, nil] :main:15#nil [:main:16, nil] :main:16#nil +[:main:17, nil] :main:17#nil [:main:18, nil] :main:18#nil [:main:19, nil] :main:19#nil [:main:8, nil] :main:8#nil [:read_int:2, nil] :read_int:2#nil +[:read_int:3, nil] :read_int:3#nil [:read_int:5, nil] :read_int:5#nil [:welcome_func:0, nil] :welcome_func:0#nil nil nil [WARN] No relation at 63793e6/phi_instruction_pair_value.csv.gz [WARN] No relation at 63793e6/instruction_bb_entry.csv.gz 60d2059/subset._merge.count_context_items.csv differs from 63793e6/subset._merge.count_context_items.csv --- 60d2059/subset._merge.count_context_items.csv 2022-10-12 20:48:22.402161260 +0000 +++ 63793e6/subset._merge.count_context_items.csv 2022-10-12 20:56:56.815387004 +0000 @@ -6,6 +6,7 @@ :main:12 1 :main:15 1 :main:16 1 +:main:17 1 :main:18 1 :main:19 1 :main:8 1 @@ -13,5 +14,6 @@ :menu:1 1 :menu:2 1 :read_int:2 1 +:read_int:3 1 :read_int:5 1 :welcome_func:0 1 [WARN] No relation at 63793e6/phi_instruction_pair_label.csv 60d2059/context.csv differs from 63793e6/context.csv --- 60d2059/context.csv 2022-10-12 20:48:22.372161218 +0000 +++ 63793e6/context.csv 2022-10-12 20:56:56.786387011 +0000 @@ -9,10 +9,12 @@ [:main:12, nil] [:main:15, nil] [:main:16, nil] +[:main:17, nil] [:main:18, nil] [:main:19, nil] [:main:8, nil] [:read_int:2, nil] +[:read_int:3, nil] [:read_int:5, nil] [:welcome_func:0, nil] nil [WARN] No relation at 63793e6/switch_instruction_case_label.csv.gz [WARN] No relation at 63793e6/variable_in_fn.csv.gz 60d2059/subset._merge.count_contexts.csv differs from 63793e6/subset._merge.count_contexts.csv --- 60d2059/subset._merge.count_contexts.csv 2022-10-12 20:48:22.366161210 +0000 +++ 63793e6/subset._merge.count_contexts.csv 2022-10-12 20:56:56.781387013 +0000 @@ -6,6 +6,7 @@ :main:12 1 :main:15 1 :main:16 1 +:main:17 1 :main:18 1 :main:19 1 :main:8 1 @@ -13,5 +14,6 @@ :menu:1 0 :menu:2 0 :read_int:2 1 +:read_int:3 1 :read_int:5 1 :welcome_func:0 1 60d2059/context_item_by_invoc.csv differs from 63793e6/context_item_by_invoc.csv --- 60d2059/context_item_by_invoc.csv 2022-10-12 20:48:22.407161267 +0000 +++ 63793e6/context_item_by_invoc.csv 2022-10-12 20:56:56.821387003 +0000 @@ -6,6 +6,7 @@ :main:12 :main:12 :main:15 :main:15 :main:16 :main:16 +:main:17 :main:17 :main:18 :main:18 :main:19 :main:19 :main:8 :main:8 @@ -13,5 +14,6 @@ :menu:1 :menu:1 :menu:2 :menu:2 :read_int:2 :read_int:2 +:read_int:3 :read_int:3 :read_int:5 :read_int:5 :welcome_func:0 :welcome_func:0 60d2059/drop_context_item_by_invoc.csv differs from 63793e6/drop_context_item_by_invoc.csv --- 60d2059/drop_context_item_by_invoc.csv 2022-10-12 20:48:22.376161224 +0000 +++ 63793e6/drop_context_item_by_invoc.csv 2022-10-12 20:56:56.790387011 +0000 @@ -1,6 +1,4 @@ :atoi:0 :backdoor:0 :main:13 -:main:17 -:read_int:3 :read_int:4 [WARN] No relation at 63793e6/instruction_bb_entry.csv [WARN] No relation at 63793e6/phi_instruction_pair_value.csv [WARN] No relation at 63793e6/variable_in_fn.csv 60d2059/indirect_call_instruction.csv differs from 63793e6/indirect_call_instruction.csv --- 60d2059/indirect_call_instruction.csv 2022-10-12 20:48:22.380161229 +0000 +++ 63793e6/indirect_call_instruction.csv 2022-10-12 20:56:56.793387010 +0000 @@ -1 +1,3 @@ +:main:17 :main:23 +:read_int:3 60d2059/num_indirect_calls_to_compatible_func.csv differs from 63793e6/num_indirect_calls_to_compatible_func.csv --- 60d2059/num_indirect_calls_to_compatible_func.csv 2022-10-12 20:48:22.408161268 +0000 +++ 63793e6/num_indirect_calls_to_compatible_func.csv 2022-10-12 20:56:56.822387003 +0000 @@ -1,10 +1,8 @@ -0 :__read_chk 0 :atoi 0 :main 0 :malloc 0 :printf 0 :puts -0 :read 0 :read_int 0 :setvbuf 0 :strtol @@ -17,3 +15,5 @@ 1 :llvm.lifetime.start.p0i8 1 :menu 1 :welcome_func +2 :__read_chk +2 :read [WARN] No relation at 63793e6/constant_in_fn.csv [WARN] No relation at 63793e6/basicblock_preds.csv.gz ```

Hypothesis: The problem stems from indirect_call_instruction:

63793e6/indirect_call_instruction.csv differs from 60d2059/indirect_call_instruction.csv
--- 63793e6/indirect_call_instruction.csv   2022-10-12 20:56:56.793387010 +0000
+++ 60d2059/indirect_call_instruction.csv   2022-10-12 20:48:22.380161229 +0000
@@ -1,3 +1 @@
-<ntu-uaf.c>:main:17
 <ntu-uaf.c>:main:23
-<ntu-uaf.c>:read_int:3

This relation has one rule:

indirect_call_instruction(Instr) :-
   call_instruction_fn_operand(Instr, Variable),
   variable(Variable).

However,

diff -u 63793e6/call_instruction_fn_operand.csv 60d2059/call_instruction_fn_operand.csv
diff -u 63793e6/variable.csv 60d2059/variable.csv

show no differences.

langston-barrett commented 1 year ago

Looks like the new version added several .input pragmas that weren't there before:

git checkout 63793e6
mcpp -e utf8 -W0 -I "." datalog/import/import.dl > new.dl
cat datalog/import/import-* > old.dl

(remove rules, comments, newlines, filenames, etc. from old.dl and new.dl; sort both)

diff -u old.dl new.dl           

--- old.dl  2022-10-12 17:12:29.985174659 -0400
+++ new.dl  2022-10-12 17:12:29.374161860 -0400
@@ -62,13 +62,16 @@
 .input cmpxchg_instruction_is_volatile
 .input cmpxchg_instruction_new_value
 .input cmpxchg_instruction_ordering
+.input cmpxchg_instruction_type
 .input constant
 .input constant_array
 .input constant_array_has_size
 .input constant_array_index
 .input constant_expression
+.input constant_expression
 .input constant_has_type
 .input constant_has_value
+.input constant_hashes_to
 .input constant_struct
 .input constant_struct_has_size
 .input constant_struct_index
@@ -76,6 +79,8 @@
 .input constant_vector
 .input constant_vector_has_size
 .input constant_vector_index
+.input direct_call_instruction
+.input direct_invoke_instruction
 .input extractelement_instruction
 .input extractelement_instruction_base
 .input extractelement_instruction_index
@@ -168,6 +173,8 @@
 .input icmp_instruction_condition
 .input icmp_instruction_first_operand
 .input icmp_instruction_second_operand
+.input indirect_call_instruction
+.input indirect_invoke_instruction
 .input indirectbr_instruction
 .input indirectbr_instruction_address
 .input indirectbr_instruction_label
langston-barrett commented 1 year ago

Current conclusions: when a relation is marked as .input, Soufflé will not attempt to apply any rules provided for it. The fact generator had been generating indirect_invoke_instr &co., but the analysis had a different, non-input relation with the same name. Hence, when import-*.dl was generated from predicates.inc, these relations became imported rather than computed and had different content.

This is a great example of the confusion that can arise when there are multiple sources of truth as to which relations are input relations...

This is all supported by the fact that the following diff (when applied to 63793e6) seems to fix the problem.

diff --git a/FactGenerator/include/predicates.inc b/FactGenerator/include/predicates.inc
index 610e326..51d55ff 100644
--- a/FactGenerator/include/predicates.inc
+++ b/FactGenerator/include/predicates.inc
@@ -218,8 +218,6 @@ GROUP_END(resume)

 GROUP_BEGIN(invoke)
 PREDICATE(invoke, instr, invoke_instruction)
-PREDICATE(invoke, instr_direct, direct_invoke_instruction)
-PREDICATE(invoke, instr_indirect, indirect_invoke_instruction)
 PREDICATE(invoke, function, invoke_instruction_fn_operand)
 PREDICATE(invoke, arg, invoke_instruction_arg)
 PREDICATE(invoke, calling_conv, invoke_instruction_with_calling_convention)
@@ -440,8 +438,6 @@ GROUP_END(va_arg)

 GROUP_BEGIN(call)
 PREDICATE(call, instr, call_instruction)
-PREDICATE(call, instr_direct, direct_call_instruction)
-PREDICATE(call, instr_indirect, indirect_call_instruction)
 PREDICATE(call, function, call_instruction_fn_operand)
 PREDICATE(call, arg, call_instruction_arg)
 PREDICATE(call, calling_conv, call_instruction_with_calling_convention)
diff --git a/FactGenerator/src/InstructionVisitor.cpp b/FactGenerator/src/InstructionVisitor.cpp
index 7133c3e..83e6a4b 100644
--- a/FactGenerator/src/InstructionVisitor.cpp
+++ b/FactGenerator/src/InstructionVisitor.cpp
@@ -276,11 +276,6 @@ void InstructionVisitor::visitIndirectBrInst(const llvm::IndirectBrInst &IBR) {
 void InstructionVisitor::visitInvokeInst(const llvm::InvokeInst &II) {
   refmode_t iref = recordInstruction(pred::invoke::instr, II);

-  gen.writeFact(
-      II.getCalledFunction() ? pred::invoke::instr_direct
-                             : pred::invoke::instr_indirect,
-      iref);
-
 #if LLVM_VERSION_MAJOR > 12
   const llvm::Value *invokeOp = II.getCalledOperand();
 #else
@@ -544,17 +539,6 @@ void InstructionVisitor::visitCallInst(const llvm::CallInst &CI) {
   // instructions due to the constraint that all direct calls must
   // be able to determine the function to be called.

-  if (!CI.isInlineAsm()) {
-    // Record if instruction is direct or indirect. This is
-    // probably redundant since it is inferred by the logic
-    // itself, according to the kind of the function operand.
-
-    gen.writeFact(
-        CI.getCalledFunction() ? pred::call::instr_direct
-                               : pred::call::instr_indirect,
-        iref);
-  }
-
 #if LLVM_VERSION_MAJOR > 12
   const llvm::Value *callOp = CI.getCalledOperand();
 #else