[Extended pipeline crash] Non-deterministic error

[mari-mari]

What happened?

python decompile.py tests/samples/bin/extended/32/0/test_memory test12 sometimes crashes and sometimes produces decompiled output.

var_18#0
var_18#5
[pipeline.py:107 run()] ERROR - Failed to decompile test12, error during stage out-of-ssa-translation: The given set of variables is not an independent set. At least two variables interfere!
Traceback (most recent call last):
  File "/home/mry/Documents/dewolf/decompile.py", line 76, in <module>
    main(Decompiler)
  File "/home/mry/Documents/dewolf/decompiler/util/commandline.py", line 80, in main
    task = decompiler.decompile(function_name, options)
  File "/home/mry/Documents/dewolf/decompile.py", line 51, in decompile
    pipeline.run(task)
  File "/home/mry/Documents/dewolf/decompiler/pipeline/pipeline.py", line 109, in run
    raise e
  File "/home/mry/Documents/dewolf/decompiler/pipeline/pipeline.py", line 102, in run
    instance.run(task)
  File "/home/mry/Documents/dewolf/decompiler/pipeline/ssa/outofssatranslation.py", line 83, in run
    self._out_of_ssa()
  File "/home/mry/Documents/dewolf/decompiler/pipeline/ssa/outofssatranslation.py", line 101, in _out_of_ssa
    self.out_of_ssa_strategy[self._optimization](self)
  File "/home/mry/Documents/dewolf/decompiler/pipeline/ssa/outofssatranslation.py", line 142, in _lift_minimal_out_of_ssa
    MinimalVariableRenamer(self.task, self.interference_graph).rename()
  File "/home/mry/Documents/dewolf/decompiler/pipeline/ssa/variable_renaming.py", line 262, in __init__
    super().__init__(task, interference_graph)
  File "/home/mry/Documents/dewolf/decompiler/pipeline/ssa/variable_renaming.py", line 95, in __init__
    self._contract_variables_that_need_same_name()
  File "/home/mry/Documents/dewolf/decompiler/pipeline/ssa/variable_renaming.py", line 179, in _contract_variables_that_need_same_name
    self.interference_graph.contract_independent_set(connected_component)
  File "/home/mry/Documents/dewolf/decompiler/structures/interferencegraph.py", line 64, in contract_independent_set
    raise ValueError(f"The given set of variables is not an independent set. At least two variables interfere!")
ValueError: The given set of variables is not an independent set. At least two variables interfere!

extern void * data_3014 = "\x25\x64\x00";

void * test12() {
    int var_2;
    int var_3;
    int * var_4;
    __x86.get_pc_thunk.ax();
    __isoc99_scanf(/* format */ data_3014, &var_2);
    var_4 = &var_2;
    *var_4 = 0x7;
    var_3 = var_2;
    return &var_3 + var_2 * 4;
}

How to reproduce?

s.o.

Affected Binary Ninja Version(s)

3.3.3996

[mari-mari]

/cib

[github-actions]

Branch issue-206-_Extended_pipeline_crash_Non-deterministic_error created!

[mari-mari]

Seems to be expression-propagation-memory bug.

[mari-mari]

The issue was actually in not checking if there is some change via alias or reference when propagating postponed aliased in expression propagation memory. Since the relations and relation like definitions are placed non-deterministically, sometimes this wrong propagation caused interference and led to crash and sometimes, if placement was lucky, just produced the incorrect decompiled code.

The original source:

int test12(){
// real - world example where we get dereference in plus operation fron Binja
    int x;
    x = 10;
    int y;
    int *ptr;
    scanf("%d", &y);
    x = y;
    ptr = &y;
    *ptr=7;
    return &x + y;
}

The decompilation in the issue description is wrong:

extern void * data_3014 = "\x25\x64\x00";

void * test12() {
    int var_2;
    int var_3;
    int * var_4;
    __x86.get_pc_thunk.ax();
    __isoc99_scanf(/* format */ data_3014, &var_2);
    var_4 = &var_2;
    *var_4 = 0x7;
    var_3 = var_2;
    return &var_3 + var_2 * 4; 
}

since var_3, which address is used in return statement, has value of 7. The original code uses address of variable storing the user input after call to scanf in the return statement.

Now we do it correctly:

void * test12() {
    int var_2;
    int var_3;
    int * var_4;
    __x86.get_pc_thunk.ax();
    __isoc99_scanf(/* format */ data_3014, &var_2);
    var_3 = var_2;
    var_4 = &var_2;
    *var_4 = 0x7;
    return &var_3 + var_2 * 4;
}

var_2*4 is an artifact of Binja trying to represent C pointer arithmetics (computing the offset from address), is not relevant for this issue.

[mari-mari]

In case we want to address non-deterministic definitions insertion order: #224