Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

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

Open
NeoQuix opened this issue Mar 2, 2023 · 6 comments
Open

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

NeoQuix opened this issue Mar 2, 2023 · 6 comments
Labels
bug Something isn't working priority-high High priority issue

Comments

@NeoQuix
Copy link
Collaborator

NeoQuix commented Mar 2, 2023

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 NeoQuix added bug Something isn't working priority-high High priority issue labels Mar 2, 2023
@NeoQuix
Copy link
Collaborator Author

NeoQuix commented Mar 2, 2023

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
Copy link
Collaborator Author

NeoQuix commented Apr 6, 2023

Also in OslGetBootStatusData in winload.exe

@ebehner
Copy link
Collaborator

ebehner commented Apr 26, 2023

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)
test_cfg_after_dead_code
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):
test_cfg_after_ep_memory

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
Copy link
Collaborator

ebehner commented Apr 27, 2023

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

@mari-mari
Copy link
Collaborator

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

@NeoQuix NeoQuix mentioned this issue Apr 24, 2024
Closed
@NeoQuix
Copy link
Collaborator Author

NeoQuix commented Jun 5, 2024

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug Something isn't working priority-high High priority issue
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@ebehner @mari-mari @NeoQuix