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.

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?

Can existing neural decompiler artifacts be used to run on a new example? Here are some notes on the current state of the art. I assign each decompiler a score from 0 to 10 based on how easy it is to use the publicly available artifacts to run on a new example.

SLaDe: 2/10

SLaDe has a publicly released replication artifact but there are several problems that prevent it from being used on new examples:

1. The models are trained on assembly code produced from compilers rather than disassemblers. This is probably minor.
2. More problematically, SLaDe uses IO testcases during beam search to help detect the best candidate. It can be used without these, but the results will be worse. SLaDe does not contain a mechanism for producing testcases for new examples.

Below is a quote from a private conversation with the author:

You are right that IO are somehow used to select in the beam search, in the sense that we report pass@5. They are not strictly required to get the outputs though.

The link you sent is for the program synthesis dataset. In this one, IO generation was programmatic but still kind of manual, I don't think it would be feasible to automatically generate the props file in the general case. For the Github functions, we have a separate repo that automatically generates IO tests, but those are randomly generated and the quality depends on each case. If I had to redo now, I would ask an LLM to generate unit tests! I can give you access to the private repo we used to automatically generate the IO examples for the general case if you wish, but now I'd do it with LLMs rather than randomly.

LLM4Decompile: 9/10

LLM4Decompile has published model files on HuggingFace that can easily be used to run on new examples. I created a few HuggingFace Spaces for testing.

resym: 2/10

resym has a publicly released replication artifact. Unfortunately, as of February 2025, the artifact is missing the "prolog-based inference system for struct layout recovery" which is the key contribution of the paper. Thus it is not possible to run resym on new examples.

DeGPT: 8/10

DeGPT has a publicly released GitHub repository. I'm largely going on memory, but I used it previously on new examples and it was relatively easy to use. I did have to file a few PRs though.

This page documents my experience with "pressure washing" my vinyl fence and siding. I have pressure washing in quotes, because it's SH or sodium hypochlorite (or bleach) that does the bulk of the work. Pros often call this "soft washing".

For vinyl fence soft washing, you want around 1-2% SH. Most household bleach is 6% SH, so if you mix 1 part bleach with 5 parts water, you'll get around 1% SH.

You also want to use a surfectant to help the mixture stick to the fence. I used Dawn Ultra. Some people claim that some dish soaps will cause a bad reaction with the bleach, ranging from "mustard gas" to neutralizing the bleach.

I personally found that at 1-1.5% SH, the mixture was safe to use around grass. I wet the grass before and after applying the mixture, and I didn't see any damage.

Supplies

• 1 Gallon Pump Sprayer
• Measuring cup
• Dawn Ultra
• Whatever 6% bleach you can find

Recipe

1. Add 3 cups of 6% SH bleach
2. Add 0.8 gallons of water
3. Add 2 fl. oz. of Dawn Ultra

Make sure to put the soap in last, or your mixture will foam up and overflow the sprayer when you try to close it.

Spray the mixture on the fence, let it sit for about five minutes, and then rinse it off. You can use a garden hose, but I personally found that using a Ryobi One+ EZ-Clean worked better. I'm sure a pressure washer would have been even faster, but it is less convenient to use.

That's about it. This removed most of the staining.

For some areas that had large amounts of growth, I used a Ryobi Scrubber to physically remove it before spraying.

The bleach was not able to remove all stain spots. For those remaining spots that were in conspicuous places, I used a magic eraser / melanine sponge.

At some point, I hope to create a Notes section on my website that will turn Markdown files into a list of notes. This is basically how the blog works. But, I'm kind of busy. And since Gatsby seems like it's dead, I'm not sure that I want to invest a whole lot of time into it. (Although putting the notes in markdown seems like a good idea for compatibility.)

Anyway, here is my first very short note on Profiling.

SpeedScope

SpeedScope is an awesome tool for visualizing profiler output. It has a flame graph view that is wonderful. I also like to use the Sandwich view, sorting by total time and simply looking for the first function that I recognize. This is often the culprit.

The documentation is pretty good. It also shows how to record profiles in compatible formats for most platforms. I mostly use py-spy and perf.

Java

The one notably missing platform is Java! Luckily, it's not too hard to convert Java's async-profiler output to a format that SpeedScope can read. Here's how I do it:

• Download async-profiler
• Create an output file in collapsed format
• You can do this in several ways, such as:
• ./asprof start -i 1s Ghidra followed by ./asprof stop -o collapsed -f /tmp/out.prof.collapsed Ghidra
• ./asprof collect -d 60 -o collapsed -f /tmp/out.prof.collapsed Ghidra
• Then open out.prof.collapsed in SpeedScope.

The collapsed format takes a while to parse, so it might be worth it to export the native SpeedScope format.