5 ms·

Yes and no. 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 proba

Yes and no. 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 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.

sitkack 2y ago
You are right on a lot of things, but LLMs are the best bijective lens that humanity has ever discovered. They can invert functions we didn't think were invertible. If given a mostly correct transform from binary back to code, how would we fix that? Exactly! Heuristics are dead.
- thesz 2y ago
  > Heuristics are dead I guess it is an example of an heuristic.
  - ahartmetz 2y ago
    Absolutely. LLMs use methods that are not really provably solving the given problem, they just happen to work in most relevant cases. That's a heuristic.
    - sitkack 2y ago
      http://www.incompleteideas.net/IncIdeas/BitterLesson.html http://www.incompleteideas.net/IncIdeas/BitterLesson.html > 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. https://arxiv.org/abs/2410.09649v1 https://arxiv.org/abs/2410.09649v1
      - ahartmetz 2y ago
        I know that these algorithms are the best that exists for many tasks, but any non-deterministic non-provable algorithm is still technically a heuristic. Also, currently, the bitter lesson seems to be that more of the same runs into diminishing returns, contrary to "The Bitter Lesson"(tm). There will probably be a better AI architecture at some point, but "lol just add more GPUs / data / RAM" times are kind of over for now.
        sitkack 2y ago
        You are misinterpreting the bitter lesson, it only gets more bitter with time! The arxiv paper is well written, worth a read.
svilen_dobrev 2y ago
> identifying which branches are gotos 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.
Vt71fcAqt7 2y ago
>And AI--especially LLMs--are notoriously bad at the "correct" part of translation. 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..
- CFLAddLoader 2y ago
  The expected outcome of using a LLM to decompile is a binary that is so wildly different from the original that they cannot even be compared. 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.
  - Vt71fcAqt7 2y ago
    That makes sense. So it can work for small functions but not an entire codebase which is the goal. Does that sound correct? If so, is it useful for small functions (like, let's say I identify some sections of code I think are important becuase they modify some memory location) or is this not useful?
    - CFLAddLoader 2y ago
      There are lots of parts of analysis that really matter for readability but aren't used as inputs to other analysis phases and thus mistakes are okay. 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.
- fulafel 2y ago

sitkack 2y ago

You are right on a lot of things, but LLMs are the best bijective lens that humanity has ever discovered. They can invert functions we didn't think were invertible. If given a mostly correct transform from binary back to code, how would we fix that? Exactly! Heuristics are dead.

thesz 2y ago
> Heuristics are dead I guess it is an example of an heuristic.
- ahartmetz 2y ago
  Absolutely. LLMs use methods that are not really provably solving the given problem, they just happen to work in most relevant cases. That's a heuristic.
  - sitkack 2y ago
    http://www.incompleteideas.net/IncIdeas/BitterLesson.html http://www.incompleteideas.net/IncIdeas/BitterLesson.html > 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. https://arxiv.org/abs/2410.09649v1 https://arxiv.org/abs/2410.09649v1
    - ahartmetz 2y ago
      I know that these algorithms are the best that exists for many tasks, but any non-deterministic non-provable algorithm is still technically a heuristic. Also, currently, the bitter lesson seems to be that more of the same runs into diminishing returns, contrary to "The Bitter Lesson"(tm). There will probably be a better AI architecture at some point, but "lol just add more GPUs / data / RAM" times are kind of over for now.
      - sitkack 2y ago
        You are misinterpreting the bitter lesson, it only gets more bitter with time! The arxiv paper is well written, worth a read.

svilen_dobrev 2y ago

> identifying which branches are gotos 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.

Vt71fcAqt7 2y ago

>And AI--especially LLMs--are notoriously bad at the "correct" part of translation. 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..

CFLAddLoader 2y ago
The expected outcome of using a LLM to decompile is a binary that is so wildly different from the original that they cannot even be compared. 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.
- Vt71fcAqt7 2y ago
  That makes sense. So it can work for small functions but not an entire codebase which is the goal. Does that sound correct? If so, is it useful for small functions (like, let's say I identify some sections of code I think are important becuase they modify some memory location) or is this not useful?
  - CFLAddLoader 2y ago
    There are lots of parts of analysis that really matter for readability but aren't used as inputs to other analysis phases and thus mistakes are okay. 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.
fulafel 2y ago