Decompiling 2024: A Year of Resurgance in Decompilation Research
mahaloz.re
mahaloz.re
Regarding AI-assisted renaming of variables, the author calls this "a strict improvement over traditional decompilation." But looking at the example:
struct IxpMsg { struct Buffer {
char* data; uint8_t* buffer;
char* pos; uint8_t* pos;
char* end; => uint8_t* streamPos;
_ixpuint size; uint32_t bufferSize;
_ixpuint mode; uint32_t type;
}; }
Ground Truth ReSym (AI)
Combining this with reasoning models that can justify their labels would be very helpful. UX improvements could also be made to indicate confidence or progressively disclose these assumptions.
SERVICE_TABLE_ENTRY* local_5c;
I wish it at least did something like:
SERVICE_TABLE_ENTRY* local_5c_pServiceTableEntry;
Oh yeah, there’s probably some plugin or Python script to do this. But I just dabble with Ghidra in my spare time
It would be great if it tracked the origin of a variable/parameter name, and could show them in a different colour (or some other visual distinction) based on their origin. That way you could easily distinguish “name manually assigned by analyst” (probably correct) vs “name picked by some LLM” (much more tentative, could easily be a hallucination)
Ghidra does have an extensive scripting API, and I've used LLMs to help me write scripts to do bulk changes like you've described. But you would have to think about how you would ensure the name suffix is synchronized as you retype variables during your analysis.
Although I suppose when decompiling to C, you need to translate it out of SSA form when you encounter loops or backwards control flow.
I don’t reject the whole concept and am bullish on AI-assisted decompilation. But the UX needs to help the user have confidence in the results, just like source code-level static analyzers generate proofs.
Decompilation, seen as a translation problem, is by any means a job that suits AI methods. Give time to researchers to gather enough mappings between source code and machine code, get used to training large predictive models, and you shall see top notch decompilers that beat all engineered methods.
My first priority for a decompiler is that the output is (mostly) correct. (I say mostly because there's lots of little niggling behavior you probably want to ignore, like representing a shift instruction as `a << b` over `a << (b & 0x1f)`). When the decompiler's output is incorrect, I can't trust it anymore, and I'm going to go straight back to the disassembly because I need to work with the correct output. And AI--especially LLMs--are notoriously bad at the "correct" part of translation.
If you look at decompilation as a multistep problem, the main steps are a) identify the function/data symbol boundaries, b) lift the functions to IR, c) recover type information (including calling convention for functions), d) recover high-level control flow, and e) recover variable names.
For step b, correctness is so critical that I'm wary of even trusting hand-generated tables for disassembly, since it's way too easy for someone to copy something by hand. But on the other hand, this is something that can be machine-generated with something that is provably correct (see, e.g., https://cs.stanford.edu/people/eschkufz/docs/pldi_16.pdf). Sure, there's also a further step for recognizing higher-level patterns like manually-implemented-bswap, but that's basically "implement a peephole optimizer," and the state of the art for compilers these days is to use formally verifiable techniques for doing that.
For a lot of the other problems, if you instead categorize them as things where the AI being wrong doesn't make it incorrect, AI can be a valuable tool. For example, control flow structuring can be envisioned as identifying which branches are gotos (including breaks/continues/early returns), since a CFG that has no gotos is pretty trivial to structure. So if your actual AI portion is a heuristic engine for working that out, it's never going to generate wrong code, just unnecessarily complicated code.
mmh. Yesterday i tried some LLM-augmented "analysis", given a 50 lines source of C, a function with few goto's in it.. somehow all "explanations" were ~correct except it completely ignored the goto's. Using a deepseek-r1-...7b, ollama's default, probably too weak ; but i don't believe other models would be 100% correct either.
Can't you just compare the compiled binaries to see if they are the same? Is the issue that you don't have the full toolchain so there are different outputs from the two compilers? Thinking about it though you could probably figure out which compiler was used using those same differences though..
"Do these two binaries always behave the same for the same inputs" is practically an unsolvable problem in general. You can get fairly close with something like AFL (American fuzzy lop, a fuzzer and also a type of rabbit).
(Someone should really make an LLM bot that scans HN for instances of "just" and explain why you can't just do that, it's such a red flag word)
If you only make mistakes very rarely and in places that don't cause cascading analysis mistakes, you can recover. But if you keep making mistakes all over the place and vastly misjudge the structure of the program over and over, the entire output is garbage.
Things like function and variable names. Letting an LLM pick them would be perfectly fine, as long as you make sure the names are valid and not duplicates before outputting the final code.
Or if there are several ways to display some really weird control flow structures, letting an LLM pick which to do would be fine.
Same for deciding what code goes in which files and what the filenames should be.
Letting the LLM comment the code as it comes out would work too, as if the comments are misleading you can just ignore or remove them.
If given a mostly correct transform from binary back to code, how would we fix that?
Exactly!
Heuristics are dead.
I guess it is an example of an heuristic.
> Our methodology leverages state-of-the-art natural language processing techniques to systematically evaluate the evolution of research approaches in computer vision. The results reveal significant trends in the adoption of general-purpose learning algorithms and the utilization of increased computational resources. We discuss the implications of these findings for the future direction of computer vision research and its potential impact on broader artificial intelligence development.
The arxiv paper is well written, worth a read.
This is the simplistic tl;dr, but that isn't what is says. You should reread the essay and the linked arxiv paper.
It is much more than throwing more compute at a problem.
However, I also acknowledge that AI can solve many pattern-based problems well. I think a considerable value can be extracted from AI by focusing in on micro decisions in the decompiler process, like variable types, as recent work has.
[1] And one of the big advances in compilers in the past decade or so is the fact that compilers are actually using these in practice!
God yes. These people are infuriating; it's as if they've abandoned the concept of provable correctness, or never understood it in the first place, and replaced it with "looks good enough to me on a few examples". Some sort of gambler's fallacy where if you get a right answer once it doesn't matter how many wrong answers you get.
Decompilation is about dependencies which makes it a graph problem.
One such problem is boolean satisfiability and this particular kind of problem is extremely important. It also very easy to gather mappings between CNF and solutions. Actually, randomization of standard benchmarks is now part of SAT competitions, AFAIK.
Have you seen any advances there using large predictive models?
Proper decompilation is even harder, it is much like halting problem than SAT. Imagine that there is a function that gets inlined and, therefore specialized. One definitely wants source for the original function and calls to it, not a listing of all specializations.
This moves us to the space of "inverse guaranteed optimization" and as such it requires approximation of the solution of halting problem.
Compilation is also a translation problem but I think many people would be leery of an LLM-based rust or clang -- perhaps simply because they're more familiar with the complexities involved in compilation than they are with those involved in decompilation.
(Not to say it won't eventually happen in some form.)
We will have LLM based compilers in the near future. Determinism is a property of the system, not the components.
You set the criteria.
It probably just hasn't happened because decompilation is not a particularly useful thing for the vast majority of people.
precision wrt translation, especially when the translation is not 1-to-1, is not excellent with LLMs.
In fact, their lack of precision is what makes them so good at translating natural languages!
"It's pattern matching, plain and simple, an area where pattern matching algorithms excel. Pattern matching driven decomp absolutely leads"
Decompilation is a dependence graph problem, one can formulate decompilation as a graph transformation/rewrite. Neural networks are notoriously bad at graphs.
AlphaFold is based on graph neural networks. The biggest issue is that we still do not know how to best encode graph problems in ways neural networks can exploit. Current graph neural network techniques exploit certain invariants but cannot distinguish between various similar graphs. And yet, they're still generating meaningful insights.
And what is the size of graphs processed by AlphaFold? How does it compare to the size of program dependence graph?
Here's evaluation of boolean satisfiability encoding of protein folding problem: https://pmc.ncbi.nlm.nih.gov/articles/PMC7197060/
Boolean satisfiability solvers are used in satisfiability modulo theories solvers that, in turn, are used to prove various things about programs.
Not anytime soon. There is more to a decompiler than assembly being converted to x language. File parsers, disassemblers, type reconstruction, etc are all functionality that have to run before a “machine code” can be converted to the most basics of decompiler output.
it seems to be very capable of having some understanding of what the original code would do.
for instance i was feeding it some game decomp. a function looking for an entity in a 3d array of tiles.
It somehow inferred it was an array of tiles and that it was hunting for a specific entity.
None of the decomp I fed it had any variable/function names or comments, just the usual var1,var2 ect.
How did it know what the underlying code was doing?