1

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?

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.

| improve this answer | |
  • The first example is something I'd thought of (which kinda boils down to the one above, since res could be really a NULL pointer as far as we know from the disassembly), but in that case, wouldn't it suffice to just force the variable to be a pointer if there's at least a case where it is used as such? Yeah, would be interesting to see an example. – Antonio Frighetto Jan 30 at 11:37
0

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.