alt Hacker NewsUnless you explicitly need byte-matching decompilation, there are significantly faster ways to produce a decompilation/C which is functionally equivalent. I need to post about this. What's been working for me is that for every function, Agent A is tasked with writing some code which is semantically equivalent to the original assembly, but not necessarily exactly the same. Agent A also writes tests. Agent A submits the implementation of the function and tests to the harness for it to judge. The harness runs both the original function and the submitted function in a virtual machine/simulator/emulator (the tests define function inputs and starting state). The harness will only accept the implementation if 1) the read/write sequence to RAM is identical to the original function's, and 2) there must be complete line and branch coverage of the original function being decompiled.
I've found this to be robust for decompiling games, while giving the agents enough freedom to write code that is readable and not waste a ton of time making sure e.g. instruction ordering, register assignments, etc. are all exactly the same. For me, having byte-matching decompilation is only one way to produce a decompilation I know is faithful to the original. This "high-level decompilation" process I just described is something agents can do much more quickly.
Replies
Functional equivalence here, of course, depends on the completeness of the test suite, where byte-identical compiled artifacts does not.
(For example, your approach would not necessarily catch all the same overflow behaviors; the OP expressly claimed that "replicating all bugs" was also important, and many bugs are caused by certain overflow behaviors)
Games depend enough on stuff like global state or externally provided data that in practice this often isn't enough to guarantee the code actually working the same as the original. You can have tens of thousands of tests that exercise every branch in the game code, and the game still may not behave the same. You really won't know for sure that your code behaves the same under all conditions unless you're able to reproduce the same executable.
Could you talk more about how you’ve used this technique? I want to start on a similar kind of AI-driven decomp project and I’m looking for any kind of edge I can get.
Only an LLM can give reasonably meaningful names to most functions and variables automatically, though.
So you restricted it to implementing the same function (same inputs,outputs, dependencies as original?) and prevented the agents from making design decisions by keeping it's scope restricted?
Read/write sequences to RAM are inconclusive regarding semantic equivalence. You can have identical sequences and semantics can still be wrong (e.g. when working with the FPU and the float stack, or instructions operating purely on registers). You can also have diverging sequences when having identical semantics, e.g. variables occupying different stack slots, despite computing the same thing.
Also, it feels like just fuzzing the function is slow, compared to simply checking bytes. Fast feedback allows agents to iterate much faster. At some point I wrote a tool that simply proves semantic equivalence, while ignoring irrelevant changes, e.g. register selection or stack slot changes. Turns out it was way too slow as a harness. I still used it to verify some of the remaining functions.
It turns out that getting functions byte-matching is actually not that complicated. Most functions are small and can be one shotted, and over time, agents figured out rules how to control code generation for more complex functions. They wrote down techniques and tricks on how to control register selection for example, or how certain control flow operations may impact basic block ordering, etc. Super insteresting what they figured out. So the further we got into the project, the easier it was to get functions exact.