[out-of-ssa-translation] The given set of variables is not an independent set

[NeoQuix]

What happened?

[pipeline.py:107 run()] ERROR - Failed to decompile mktime_internal, 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/neoquix/Git-Repos/DeWolf/decompile.py", line 80, in <module>
    main(Decompiler)
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/util/commandline.py", line 87, in main
    task = decompiler.decompile(function_name, options)
  File "/home/neoquix/Git-Repos/DeWolf/decompile.py", line 55, in decompile
    pipeline.run(task)
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/pipeline/pipeline.py", line 109, in run
    raise e
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/pipeline/pipeline.py", line 102, in run
    instance.run(task)
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/pipeline/ssa/outofssatranslation.py", line 83, in run
    self._out_of_ssa()
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/pipeline/ssa/outofssatranslation.py", line 101, in _out_of_ssa
    self.out_of_ssa_strategy[self._optimization](self)
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/pipeline/ssa/outofssatranslation.py", line 142, in _lift_minimal_out_of_ssa
    MinimalVariableRenamer(self.task, self.interference_graph).rename()
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/pipeline/ssa/variable_renaming.py", line 262, in __init__
    super().__init__(task, interference_graph)
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/pipeline/ssa/variable_renaming.py", line 95, in __init__
    self._contract_variables_that_need_same_name()
  File "/home/neoquix/Git-Repos/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/neoquix/Git-Repos/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!")
ValueError: The given set of variables is not an independent set. At least two variables interfere!

How to reproduce?

Decompile mktime_internal in touch.zip

Affected Binary Ninja Version(s)

Version 3.3.3996

[NeoQuix]

Note: The problem was already fixed with #150 by fixing the ssa labels on global variables.
Most likely the ssa labels on other variables have a problem as well.

There error is also in:

• mktime_internal in dir
• mktime_internal in ls
• mktime_internal in du
• mktime_internal in pr

The functions are all the same, therefore the bin in touch should be enough.

[NeoQuix]

Also in OslGetBootStatusData in winload.exe

[ebehner]

I guess this is a problem of expression propagation memory, but I am not sure. I try to explain where the problem comes from:
Consider the following cfg (Before Expression Propagation Memory)

In block 12, we have the phi-functions:

• rpb#2 = Phi(rax_27#33, r10_1#2)
• var_d0#3 = Phi(var_d0#2, var_d0#19)

Now, Expression propagation memory propagates the variable var_d0#4 into r10_1#2 (see cfg after expression propagation memory below):

The propagation of var_d0#4 into var_d0#5 in block 14 is okay, but I think we should not propagate into r10_1#2 because we "go over" the variable var_d0#19. Since var_d0 is an aliased variable, I think we do not want to do this.

Now, the problem of propagating var_d0#4 into the phi-function of block 12 is that when we remove the phi-functions, the variables var_d0#3 and var_d0#4 interfere. In this case, it could probably be possible to sort the instruction in such a way that they do not interfere by first adding the instruction rbp#2 = var_d0#4 and then the instruction var_d0#3 = var_d0#19.

(sample of Issue description)

[ebehner]

fix in expression propagation, should be part of expression-propagation memory

[mari-mari]

Could be related to #245, TODO check after #245 is done (if noone does something on this issue earlier)

[NeoQuix]

Does not get fixed with #245 and #390 resolved.