Motivation

I've been thinking a lot about verifying that a decompilation is "correct". This problem is becoming increasingly important because many neural decompilers produce output that is obviously incorrect. Wouldn't it be nice if we could detect these cases, either when evaluating decompilers for a paper, or in practice?

I have long wondered if we could use a simple dynamic technique to detect non-equivalent decompilations using something like Manuel Egele's blanket execution or Godefroid's micro execution. But every time that I think about this, I realize how many nuances there are, and I often forget my conclusions. The idea of this post is to write down some insights so that I remember them.

I would have liked to write a post that convinces someone other than me, but that was taking too long. So instead, this is mostly a set of observations recorded for myself. Maybe they will provide insight or make sense to others... I hope so, but I certainly understand if not.

The Idea

The idea starts by assigning random values to registers and executing a binary function concretely. When unassigned memory is referenced, intercept it and set it to something random. If both the reference decompilation and a candidate execute to an "equivalent" output state, the two programs are equivalent for that particular input. This is a cheap test, so we can run with a lot of different random inputs.

In other words, we replace the real callers with random ones.

Here's a simple example. Suppose the reference function is:

uint32_t f_reference(uint32_t a, uint32_t b) {
    return (a * 2654435761u) ^ ((b << 13) | (b >> 19));  // rotate b left 13
}

and a broken candidate decompilation:

uint32_t f_candidate(uint32_t a, uint32_t b) {
    return (a * 2654435761u) ^ (b << 13);  // BUG: rotate became a shift
}

For a random input a=0x6b8b4567, b=0x327b23c6, the reference returns 0xce416d78 and the candidate gives 0xce416b37. Clearly these are not equivalent!

Things get a little more complicated when you have a function call. Blanket and micro execution both execute into the callee. But I really wanted to keep testing isolated to the function in question (the caller here).

So my idea was to model callees such that they return arbitrary but deterministic values for each input combination (e.g., hash them). For example, let's say we happened to call foo(10). We might hash foo(10) to the random value 0x08cbc4a9. If the reference and candidate both call foo(10) and use it in the same way, they should behave similarly.

Observations

Not executing callees

There are two problems if you try to avoid executing callees.

Structural vs. physical equality

The hashing scheme rests on an assumption: a callee invoked on the same input should return the same output. But what counts as "the same input"?

Consider:

int *foo(char *s);

int *f_reference(char *out) {
    strcpy(out, "hello");
    return foo(out);
}

int *f_candidate(char *out) {
    strcpy(out, "goodbye");
    return foo(out);
}

If we call f_reference and f_candidate on the same argument, are their respective calls to foo on "the same input"? In a technical sense, the values of out will be equal according to the == operator. Let's call this physical equality.

But these two functions are obviously different, since out will point to different strings; they are not structurally equal. And physical equality is exactly what a hash of the argument registers gives us, so the hashing scheme would declare these two functions equivalent.

To hash structurally instead, we would have to know how much of the buffer matters. And without looking inside foo, we really can't tell how the pointer is going to be used. Are all bytes going to be used up until a NULL terminator? Or perhaps a fixed hard-coded number of bytes will be accessed. We can't know.

Conclusion: It's hard to achieve structural equality without examining callee functions.

Calling Conventions

Even determining the inputs and outputs of a callee function is not possible without examining it.

Here's an example that shows that you can't determine function signatures from looking at a function in isolation. Below are two programs. Both contain a caller and a callee. In the first program, the callee takes one argument:

long callee(long t) { return t * 3; }
long caller(long a, long c) { long v = c * c; return callee(a + v); }

gcc -O2 compiles caller to:

caller:
        imulq   %rsi, %rsi
        addq    %rsi, %rdi
        jmp     callee

In the second program, callee takes two:

long callee(long t, long v) { return t * 3 + v; }
long caller(long a, long c) { long v = c * c; return callee(a + v, v); }

gcc -O2 compiles this caller to the same three instructions:

caller:
        imulq   %rsi, %rsi
        addq    %rsi, %rdi
        jmp     callee

The two callers are indistinguishable, so we can't infer a callee's signature by looking at the caller's code alone. We would at least need to look at callee.

This matters because hashing a call requires knowing what to hash. In the first program %rsi is dead at the call; in the second it holds an argument. Hash too little and we miss a real difference; hash too much and we report a difference in a scratch register that nobody observes.

Contextual equivalence

I argue that the right definition of equivalence for decompilation is if you swap the decompiled function in for the original, nothing changes.

PL has a name for this idea: contextual equivalence. Two functions f and g are contextually equivalent if, for every program context C, C[f] and C[g] behave the same. The context is everything around the function: its callers, its callees, and the globals.

The nice thing about contextual equivalence is that it only cares about what the rest of the program can observe. It doesn't care which register holds a temporary value, or at which stack offset a local variable lives. If the candidate keeps a value in %rcx where the original used %rdx, or puts a buffer at a different stack offset, that's fine, as long as nothing else in the program can tell.

One of the benefits of contextual equivalence for decompilation is that it allows us to define equivalence without talking about the rest of the program. For example, suppose the reference function requires that its argument x is not NULL:

int f_reference(int *x) {
    assert(x);
    return *x * 2;
}

Let's assume that, in the rest of the program, every caller respects this and passes a non-NULL argument.

Now consider a candidate that omits the check:

int f_candidate(int *x) {
    return *x * 2;
}

In this program, are f_reference and f_candidate equivalent? On one hand, since callers never pass NULL, the assertion would never be triggered. We can swap f_candidate in for f_reference in this program and the behavior won't change. But establishing that requires understanding the entire program.

Contextual equivalence determines that these two functions are not equivalent because there is a context where x is NULL that causes the behavior to differ, even if this context does not occur in the particular program we are talking about. I argue that this is a good thing for two reasons:

1. Reverse engineers seek to understand the behaviors that are present statically in machine code. Even if an assert is "irrelevant", in many cases it is important to understand that it is present. Contextual equivalence gives us an elegant way to talk about what information is relevant.

2. Because contextual equivalence is defined over any possible context, even those that are not possible in a specific program, we can decide whether two functions are contextually equivalent without analyzing the rest of the program. This is important because it allows us to think about functions in isolation.

Contextual equivalence at the executable level

There are some complications with applying contextual equivalence to executable code. In the examples above, I provided the reference as C source code, because I think it's easier to think about. There are actually two types of contexts: an abstract C context and an executable context. The glue between these two contexts is the ABI, which tells us how to map from the function prototype to the concrete (executable) context, but not the reverse. To say if two functions are contextually equivalent, we thus need to know their prototype.

The awkwardness in decompilation is that, in practice, the reference is assembly code. It doesn't have a prototype. The best prototype we have is from the candidate decompilation. Thus, the question of contextual equivalence becomes "Is decompilation D (and its prototype) a possible decompilation for reference machine code R?". And there can be multiple possible decompilations with different prototypes.

Another point of awkwardness is that contextual equivalence is defined in terms of a function in isolation, but recovering a prototype at the binary level requires inter-procedural analysis.

So, to recap:

• Contextual equivalence allows us to think about a function's equivalence in isolation.

• We care about the C context, so we need to know the reference function's C prototype.

• We can't recover the function's C prototype by analyzing the function in isolation.

Put together, this is mildly circular: verifying a decompilation requires information that we can only get from the decompilation itself.

A downside to contextual equivalence

One downside to contextual equivalence is that it does not take implied preconditions into account. Consider a program that contains:

void scales_poorly(int x) {
    for (int i = 0; i < (1 << x); i++) {
        work(i);
    }
}

scales_poorly is obviously exponential in its argument, and the programmer decided to only call it on small numbers as a result.

Unfortunately, contextual equivalence has no way of knowing this. A testing technique based on random inputs might attempt to run scales_poorly on large inputs, even though (1) it would be very expensive, and (2) the program does not normally do this.

Symbolic execution could help this problem somewhat by forcing execution along short program paths instead of taking the paths of random inputs, but at the cost of significant engineering complexity.

Conclusions and Questions

1. Function prototypes are a parameter to the decompilation validation process. If you have ground truth source code, you should use the prototype from that. Otherwise, you can use the prototype from the candidate decompilation.

2. My thought experiment has led me to believe that you can have structural equality or you can avoid executing callees, but not both. Is this actually true?