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

[jnhols]

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

[NeoQuix]

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]

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]

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

[NeoQuix]

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]

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

[ebehner]

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:

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

[ebehner]

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