Type reconstruction ambiguity

Question

In TIE: Principled Reverse Engineering of Types in Binary Programs, Lee J. et al claim to solve most of the challenges in the process of C code decompilation that come with type reconstruction.

While producing a complex type where maybe a void * could fit is definitely non-trivial, I was just thinking about a possible type recovery ambiguity for what merely concerns a variable of type int or int *.

int foo(int *a, int sz) {
    int res = 0;
    for (int *q = a; q < &a[sz]; q++)
        res += *q;
    return res;
}

In 32-bit architectures, the above code shows an example of such ambiguity for variable res, as both int and int * are compatible with a 32-bit register, and the disassembled code is the same. If res was a pointer though, it would be improperly used since we would be returning the address of an automatic variable (and would lead to undefined behaviour).

So can this example really be taken into account (is a valid instance)? Can you come up with an example where these two types generate ambiguity but are correctly used? Can we conclude that a variable can be inferred to be a pointer or not if it just gets dereferenced?

Answer 1

One common issue I’ve seen in real programs is the NULL pointer which has the same value as the integer 0. For example, currently (2020) the Hex-Rays decompiler does not support one variable holding different types so for example when a register initialized with zero is used as integer in one branch and as pointer in another, you might see “funny” output. Alas I don’t have an example at hand but if I see it again I’ll add it here.

Another thing that comes to mind is the “clever” implementation of double linked list using one field to store both next and previous pointers, known as XOR Linked List. This pattern is probably about impossible to recover automatically but luckily it seems to be more of a theoretical curiosity than practical construct.

Answer 2

In fact, type-reconstruction is mainly looking at how the program is using the data and tries to deduce the type based on this. Your example is really not a problem for most of the decompiler because res is only used as an int (the code always dereference the pointer when storing it to res).

But, at the assembly level you may enforce the usage of a constant to be both an integer value and an address if the part of the program you are in is totally static. For example:

mov 0xdeadbeef, %eax
xor %ebx, %eax       <-- bitwise operators are almost never used on addresses
mov (%ebx), $ecx     <-- Yet, %ebx is an address

The heuristics of the decompiler will give contradictory information here, is %ebx a data or an address ? So, one decision will be taken but both types (data and address) cannot be kept and backported to the decompiled code. Somehow, this is lost in translation.