5 ms·

> If you’ve ever talked to me in person, you’d know that I’m a disbeliever of AI replacing decompilers any time soon Decompilation, seen as a translation probl

by benob 2y ago

> If you’ve ever talked to me in person, you’d know that I’m a disbeliever of AI replacing decompilers any time soon 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.

kachapopopow 2y ago
Typical obfuscation sure. vms, obfuscation and everything in between is just noise to AI.
donatj 2y ago
It's pattern matching, plain and simple, An area where AI excels. AI driven decomp is absolutely on its way
- dartos 2y ago
  Maybe in conjunction with a deterministic decompiler. 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!
- ChrisKnott 2y ago
  It's also perfect for RL because it can compile it's output and check it against the input. It's a translation exercise where there's already a perfect machine translator in one direction. It probably just hasn't happened because decompilation is not a particularly useful thing for the vast majority of people.
- thesz 2y ago
  Let me parrot you, it's fun. "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.
  - gsam 2y ago
    > 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.
    - thesz 2y ago
      > AlphaFold is based on graph neural networks. 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/ 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.
wzdd 2y ago
> Decompilation, seen as a translation problem, is by any means a job that suits AI methods. 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.)
- chrisco255 2y ago
  LLMs are not deterministic, and I want deterministic builds from compiled code to assembly. I also do not want the LLM to arbitrarily change the functionality, I have no such guarantees.
  - sitkack 2y ago
    Compilers aren't deterministic in the ways that people would think matter. We will have LLM based compilers in the near future. Determinism is a property of the system, not the components.
    - LowLevelMahn 2y ago
      "near" like never :)
      - sitkack 2y ago
        You want to put money on it? You set the criteria.
        pjc50 2y ago
        Let me know when an LLM compiler is licensed for use on critical infrastructure. Admittedly Java doesn't meet this bar (see "You acknowledge that Licensed Software is not designed or intended for use in the design, construction, operation or maintenance of any nuclear facility" https://www.oracle.com/technetwork/java/javase/downloads/jdk-6u21-license-159167.txt https://www.oracle.com/technetwork/java/javase/downloads/jdk... )
__alexander 2y ago
> 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. 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.
jcranmer 2y ago
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.
mahaloz 2y ago
I agree with many other sentiments here that if it can replace decompilers, then surely it can replace compilers... which feels unlikely soon. So far, I've seen four end-to-end binary-to-code AI approaches, and none have had convincing results. Even those that crawled all of GitHub continue to have issues of making fake code, not understanding math, omitting portions of code, and (a personal irritant for me) being unable to map what address a line of decompilation came from. 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.
- jcranmer 2y ago
  I'd feel a lot more comfortable in the prospects of AI if their big boosters weren't so gung-ho about it replacing absolutely everything. Compilers (and by extension decompilers) are one of the areas where we have the ability to have formal proofs of correctness [1]--and the fact that AI people seem to be willing to throw all of that away in favor of their maybe-correct-but-does-it-really-matter-if-it's-not tools is extremely distressing to me. [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!
  - pjc50 2y ago
    > I'd feel a lot more comfortable in the prospects of AI if their big boosters weren't so gung-ho about it replacing absolutely everything. Compilers (and by extension decompilers) are one of the areas where we have the ability to have formal proofs of correctness [1]--and the fact that AI people seem to be willing to throw all of that away in favor of their maybe-correct-but-does-it-really-matter-if-it's-not tools is extremely distressing to me. 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.
thesz 2y ago
> 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. 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.

by benob 2y ago

kachapopopow 2y ago

Typical obfuscation sure. vms, obfuscation and everything in between is just noise to AI.

donatj 2y ago

It's pattern matching, plain and simple, An area where AI excels. AI driven decomp is absolutely on its way

dartos 2y ago
Maybe in conjunction with a deterministic decompiler. 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!
ChrisKnott 2y ago
It's also perfect for RL because it can compile it's output and check it against the input. It's a translation exercise where there's already a perfect machine translator in one direction. It probably just hasn't happened because decompilation is not a particularly useful thing for the vast majority of people.
thesz 2y ago
Let me parrot you, it's fun. "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.
- gsam 2y ago
  > 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.
  - thesz 2y ago
    > AlphaFold is based on graph neural networks. 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/ 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.

wzdd 2y ago

> Decompilation, seen as a translation problem, is by any means a job that suits AI methods. 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.)

chrisco255 2y ago
LLMs are not deterministic, and I want deterministic builds from compiled code to assembly. I also do not want the LLM to arbitrarily change the functionality, I have no such guarantees.
- sitkack 2y ago
  Compilers aren't deterministic in the ways that people would think matter. We will have LLM based compilers in the near future. Determinism is a property of the system, not the components.
  - LowLevelMahn 2y ago
    "near" like never :)
    - sitkack 2y ago
      You want to put money on it? You set the criteria.
      - pjc50 2y ago
        Let me know when an LLM compiler is licensed for use on critical infrastructure. Admittedly Java doesn't meet this bar (see "You acknowledge that Licensed Software is not designed or intended for use in the design, construction, operation or maintenance of any nuclear facility" https://www.oracle.com/technetwork/java/javase/downloads/jdk-6u21-license-159167.txt https://www.oracle.com/technetwork/java/javase/downloads/jdk... )

__alexander 2y ago

> 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. 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.

jcranmer 2y ago

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.

mahaloz 2y ago

I agree with many other sentiments here that if it can replace decompilers, then surely it can replace compilers... which feels unlikely soon. So far, I've seen four end-to-end binary-to-code AI approaches, and none have had convincing results. Even those that crawled all of GitHub continue to have issues of making fake code, not understanding math, omitting portions of code, and (a personal irritant for me) being unable to map what address a line of decompilation came from. 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.

jcranmer 2y ago
I'd feel a lot more comfortable in the prospects of AI if their big boosters weren't so gung-ho about it replacing absolutely everything. Compilers (and by extension decompilers) are one of the areas where we have the ability to have formal proofs of correctness [1]--and the fact that AI people seem to be willing to throw all of that away in favor of their maybe-correct-but-does-it-really-matter-if-it's-not tools is extremely distressing to me. [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!
- pjc50 2y ago
  > I'd feel a lot more comfortable in the prospects of AI if their big boosters weren't so gung-ho about it replacing absolutely everything. Compilers (and by extension decompilers) are one of the areas where we have the ability to have formal proofs of correctness [1]--and the fact that AI people seem to be willing to throw all of that away in favor of their maybe-correct-but-does-it-really-matter-if-it's-not tools is extremely distressing to me. 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.

thesz 2y ago

> 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. 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.