Motivation

In my last post, I ended with a question. My thought experiment had led me to believe that you can have structural equality of callee arguments or you can avoid executing callees, but not both. Is this actually true?

I've kept thinking about it, and I now think the answer is mostly no. If memory is equal, comparing pointers by address is okay, so we can sidestep structural equality entirely. There are some exceptions, though. As before, these are mostly notes for myself so that I don't forget my conclusions.

Compare memory, not arguments

To recap the problem, consider the example from last time:

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);
}

The calls to foo are physically equal (same out), but not structurally equal (different strings). To check structural equality we would need to know how much of *out foo reads, and we can't know that without looking inside foo.

Rather than trying to figure out what foo reads, which would require looking at foo, we can instead require that everything foo could read is equal. Specifically, at each call, check that:

1. the arguments are physically equal, and
2. all memory the callee could observe is equal in both executions.

If both hold, then foo receives identical inputs no matter how it uses the pointer, so it's safe to give both executions the same (random, hashed) response. This over-approximates the callee's read set, but it doesn't require knowing anything about foo.

But this idea only works when equivalent code produces identical pointers. So when could two functions be equivalent and still have different pointers? I see two main cases: new memory that the candidate introduces itself (e.g., string literals), and implementation choices (e.g., mostly stack layout).

Exception 1: new memory in the candidate

The first case is memory that the candidate introduces itself, such as string literals. Our idea above is based on the assumption that all memory that a callee can read is equal. If the candidate introduces new memory segments, it breaks that assumption.

For example, suppose the target function calls printf("hello world\n"). The original executable contains the literal "hello world\n" at some address in its read-only data. When we compile the candidate, assuming it also contains the literal "hello world\n", it receives its own, separate copy of the literal at a different address. So printf receives different pointers in the two executions, and a physical comparison of the arguments fails even though the strings are identical.

Fortunately, constants are fairly easy to solve. Since constants are immutable, their identity is their content. We can find a correspondence before execution by searching the original binary's read-only sections for each of the candidate's constants, and then forcing the candidate to use the original's addresses instead. Then the arguments are physically equal and there's nothing to special-case at runtime.

Exception 2: stack layout

The second case is stack layout. Consider two decompilations of the same function that differ only in the order in which their locals are declared:

void g(char *);
int foo(char *);

int f_reference(void) {
    char a[8], b[8];
    g(a);
    g(b);
    return foo(b);
}

int f_candidate(void) {
    char b[8], a[8];   // same code, locals declared in the other order
    g(a);
    g(b);
    return foo(b);
}

C says nothing about where locals live, so these two functions are equivalent. Here's what gcc -O2 does with each of them, where S is the stack pointer at entry:

; f_reference
pushq  %rbp
subq   $16, %rsp        ; rsp = S-24
leaq   8(%rsp), %rbp    ; b = S-16
movq   %rsp, %rdi       ; a = S-24
call   g@PLT            ; g(a)
movq   %rbp, %rdi
call   g@PLT            ; g(b)
movq   %rbp, %rdi
call   foo@PLT          ; foo(S-16)

; f_candidate
pushq  %rbp
subq   $16, %rsp        ; rsp = S-24
movq   %rsp, %rbp       ; b = S-24
leaq   8(%rsp), %rdi    ; a = S-16
call   g@PLT            ; g(a)
movq   %rbp, %rdi
call   g@PLT            ; g(b)
movq   %rbp, %rdi
call   foo@PLT          ; foo(S-24)

Notice that the calls to foo are not physically equal: foo receives S-16 in one and S-24 in the other. Note that this is the same compiler at the same optimization level: all I changed was the declaration order. A decompilation recompiled with a different compiler, or with a slightly different set of locals, can shift things around even more.

This problem is specific to the stack. Most other layout is decided by the linker: globals, functions and literals are placed at link time, so we can make the candidate use the original's addresses when we link it, as with the literals above. The frame layout, by contrast, is decided by the compiler inside each function, and there are no symbols we could bind. So the trouble is confined to stack addresses that escape.

Can we carve up the stack frame?

One idea is to carve the frame into objects and compare the object each escaped pointer refers to. But the frame is just bytes: it's hard to tell a scalar from a struct or an array, or where each object ends.

And even if we could carve perfectly, we can't tell how much the callee will read. A pointer to a struct is also a pointer to its first field:

struct point { int x, y; };
struct point p = { 1, 2 };
draw(&p);   // does draw read p.x (4 bytes) or all of p (8 bytes)?

And at the machine level, a callee given a stack pointer can read pretty much anything on the stack.

Conclusions and Questions

My personal conclusion is that this "compare memory, not arguments" idea is worth exploring. To that end, I have mocked up an interactive demo. There are built-in examples, but you can also upload your own (ELF x86-64 for now) binaries and candidate decompilations.

For now, I don't have a solution to the stack layout problem. This means that candidates that are equivalent except for their stack layout may be falsely reported as non-equivalent if they pass a pointer to the stack to a callee.