[[email protected]:62] ValueError: The given set of variables is not an independent set. At least two variables interfere!

[mm4rks]

What happened?

  File "/opt/dewolf/decompiler/util/bugfinder/bugfinder.py", line 164, in iter_function_reports
    task_result = self.decompile(function, options)
  File "/opt/dewolf/decompile.py", line 51, in decompile
    pipeline.run(task)
  File "/opt/dewolf/decompiler/pipeline/pipeline.py", line 109, in run
    raise e
  File "/opt/dewolf/decompiler/pipeline/pipeline.py", line 102, in run
    instance.run(task)
  File "/opt/dewolf/decompiler/pipeline/ssa/outofssatranslation.py", line 83, in run
    self._out_of_ssa()
  File "/opt/dewolf/decompiler/pipeline/ssa/outofssatranslation.py", line 101, in _out_of_ssa
    self.out_of_ssa_strategy[self._optimization](self)
  File "/opt/dewolf/decompiler/pipeline/ssa/outofssatranslation.py", line 142, in _lift_minimal_out_of_ssa
    MinimalVariableRenamer(self.task, self.interference_graph).rename()
  File "/opt/dewolf/decompiler/pipeline/ssa/variable_renaming.py", line 262, in __init__
    super().__init__(task, interference_graph)
  File "/opt/dewolf/decompiler/pipeline/ssa/variable_renaming.py", line 95, in __init__
    self._contract_variables_that_need_same_name()
  File "/opt/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 "/opt/dewolf/decompiler/structures/interferencegraph.py", line 62, in contract_independent_set
    raise ValueError(f"The given set of variables is not an independent set. At least two variables interfere!")

Error class [email protected]:62 contains 1176 cases.

How to reproduce?

python decompile.py f70d9c140d39f45a63ea704e172d3e7e7fc3394bfc7bf72fe50c9bc8211cc2a0 sub_4031b4 --debug

sample: f70d9c140d39f45a63ea704e172d3e7e7fc3394bfc7bf72fe50c9bc8211cc2a0
dewolf commit: 5566666
Binaryninja version: 3.4.4271

[ebehner]

The error seems to be in expression-propagation memory. Before this stage the cfg looks as follows, the interesting rows are marked:

Expression-propagation memory propagates the assignment rdx#1 = &(var_f4#0) into instruction 0x205e81(0x0, arg2#0, rdx#1, rcx#0). See the following picture:

Next, identity elimination identifies the variables var_f4#1 and var_f4#0 because they always have the same value.
The resulting cfg looks as follows:

The problem is, that after this transformation, the variable var_f4#0 interfere with the variables var_f4#3, but they need to get the same name due to the relation var_f4#3 -> varHf4#0.

We should not propagate a variable over a relation with the same name.

[NeoQuix]

/cib

[github-actions]

Branch issue-245-_ValueError_interferencegraph_py_62_ValueError_The_given_set_of_variables_is_not_an_independent_set_At_least_two_variables_interfere! created!

[NeoQuix]

Currently the bug finder does not work, therefore I can't test the mentioned sample.
I have another one (main.main), where the issue only happens on BNinja 3.5 with the new lifter.

[NeoQuix]

Tested the new PR for #192 but it did not work.
If the code is modified to not allow any alias variable to be propagated it will work.
So at least we know it's an aliased variable that produces the error.

[NeoQuix]

Fixed the PR to use all relations for the same var (ignoring SSA).
Solves the problem for f70d9c140d39f45a63ea704e172d3e7e7fc3394bfc7bf72fe50c9bc8211cc2a0 and the hello_world go in bninja 3.5.

Issue #192 still fails.