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

ValueError: At least two variables in an identity group have out degree zero #135

Open
jnhols opened this issue Nov 10, 2022 · 7 comments
Open

ValueError: At least two variables in an identity group have out degree zero #135

jnhols opened this issue Nov 10, 2022 · 7 comments
Labels
bug Something isn't working priority-high High priority issue

Comments

@jnhols
Copy link
Collaborator

jnhols commented Nov 10, 2022

What happened?

The decompiler crashes with a ValueError in identity_elimination.

Traceback (most recent call last):
	File ""/home/ubuntu/.binaryninja/plugins/dewolf/decompile.py"", line 80, in <module>
main(Decompiler)
	File ""/home/ubuntu/.binaryninja/plugins/dewolf/decompiler/util/commandline.py"", line 65, in main
task = decompiler.decompile(function_name, options)
	File ""/home/ubuntu/.binaryninja/plugins/dewolf/decompile.py"", line 55, in decompile
pipeline.run(task)
	File ""/home/ubuntu/.binaryninja/plugins/dewolf/decompiler/pipeline/pipeline.py"", line 97, in run
instance.run(task)
	File ""/home/ubuntu/.binaryninja/plugins/dewolf/decompiler/pipeline/dataflowanalysis/identity_elimination.py"", line 312, in run
variable_replacer.replace_variables(identity_group, identity_graph.find_replacement_variable_of_group(identity_group))
	File ""/home/ubuntu/.binaryninja/plugins/dewolf/decompiler/pipeline/dataflowanalysis/identity_elimination.py"", line 225, in find_replacement_variable_of_group
raise ValueError(message)
ValueError: At least two variables in the identity group {rcx_7#44 (type: char * aliased: False), rcx_7#30 (type: char * aliased: False), var_128_1#7 (type: char * aliased: False), rcx_7#42 (type: char * aliased: False), r10_1#27 (type: char * aliased: False), r10_5#18 (type: char * aliased: False), 1 type: long, r10_1#1 (type: char * aliased: False), rcx_7#33 (type: char * aliased: False), var_128_1#18 (type: char * aliased: False), var_128_1#1 (type: char * aliased: False), r10_5#16 (type: char * aliased: False), rcx_7#41 (type: char * aliased: False), r10_1#12 (type: char * aliased: False), rcx_7#6 (type: char * aliased: False), rcx_18#37 (type: char * aliased: False), var_128_1#6 (type: char * aliased: False), r10_1#20 (type: char * aliased: False), r10_1#21 (type: char * aliased: False), var_128_1#3 (type: char * aliased: False), r10_1#26 (type: char * aliased: False), rcx_18#39 (type: char * aliased: False), r10_1#9 (type: char * aliased: False), var_128_1#16 (type: char * aliased: False), var_58#0 (type: char * aliased: False)} have out degree zero, namely 0x1 and r10_1#1, i.e., these set of vertices is not an identity group

How to reproduce?

Decompile main in the following sample.

seq.zip

Affected Binary Ninja Version(s)

3.2.3814
@jnhols jnhols added bug Something isn't working priority-high High priority issue labels Nov 10, 2022
@NeoQuix
Copy link
Collaborator

NeoQuix commented Feb 2, 2023

Notes on the problem itself:

  • uninitialized var_58 (type: char*) is not in the group of out-nodes(sinks), therefore the algorithm used to break phi nodes does not work as intended, which leads to the error above.

==> Some times uninitialized should be in the group of out-nodes (or completely purges from the dependency graph).

@NeoQuix
Copy link
Collaborator

NeoQuix commented Feb 2, 2023

Smaller Code which probably represents the same problem:

int f1(int argc){
    char* g_1 = "dump global str1";
    char* g_2 = "dump global str2";
    char* ptr;

    if(argc){
        g_1 = ptr;
    }else{
        g_2 = ptr;
    }

    return g_1;
}

Output of Decompiler:

void * f1(int arg1) {
    return "dump global str1";
}

The stage incorrectly merges var_10#0, var_20#3 and "dump global str1" into "dump global str1", completely destroying the correct control flow.
Again var_10#0 (char* ptr) is not in the group of out-nodes, which would probably fix the problem.

Binary for testing:
a.out.zip

@NeoQuix
Copy link
Collaborator

NeoQuix commented Feb 2, 2023

Note: All three functions in the binary have the same problem, but main behaves differently because of the return type.
(Maybe other issue)

@NeoQuix
Copy link
Collaborator

NeoQuix commented Mar 7, 2023

Many more binaries have the problem.
I will not upload them all, but the log which shows what function has a problem.

All binaries are part of the GNU core utils
ValueError: At least.log

@NeoQuix
Copy link
Collaborator

NeoQuix commented Apr 6, 2023

Updated log for Windows bins:
ValueError: At least two varia.log

@ebehner
Copy link
Collaborator

ebehner commented Apr 27, 2023

I guess I found the problem, at least for some of the samples, I did not check all 😉

We build the identity graph and then remove edges such that each connected component can be an identity afterward.
What we miss is the following case:
We have the following phi-functions:

  • var_70#7 = phi(var_70#0, var_40_1#3)
  • var_70#3 = phi(var_70#0, rcx_12#11)
  • var_70#4 = phi(var_70#0, r9_10#8)
    The variable var_70#0 is undefined, and the other variable in each phi-function is a value which can not be identified with is defining value.
    Now, it should be possible to identify each phi-function by itself, but not all together. But since they are in one connected component, we try to identify them all together.
    In this case, it could be a good to identify var_70#7 and var_40_1#3, var_70#3 and rcx_12#11, as well as var_70#4 and r9_10#8, and to remove the three phi-functions.

cfg:
ie_bug_start

identity graph, where we try to identify each connected component:
ie_graph_prune_one

@ebehner ebehner mentioned this issue Feb 23, 2024
Closed
@ebehner
Copy link
Collaborator

ebehner commented Feb 23, 2024

Issue #388 only solves some of the problems mentioned in this Issue. It does not address #135 (comment)

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 @NeoQuix @jnhols