4 ms·

This is why round-tripping the code is important. If you decompile the binary to source, then compile the source back to binary you should get the original bin

by Eager 3y ago

This is why round-tripping the code is important. If you decompile the binary to source, then compile the source back to binary you should get the original binary. You just need to do this enough times until the loss drops to some acceptable amount. It's a great task for reinforcement learning, which is known to be unreasonably effective for these types of problems.

thfuran 3y ago
>If you decompile the binary to source, then compile the source back to binary you should get the original binary. You really can't expect that if you're not using exactly the same version of exactly the same compiler with exactly the same flags, and often not even then.
- vasvir 3y ago
  Right. A less formidable problem with higher chances of succeeding is from a given binary to figure out first compiler, compiler-version, compiler-flags. From there you could have a model for every combination or at least a model for the compiler variant and use the other info (version, flags) as input to the model.
- moyix 3y ago
  Yes, that's a limitation of trying to ensure exact binary reconstruction. Luckily there is also a separate line of work on detecting the compiler version and optimization flags based on a binary – it turns out this is not that hard and it's easy to get a bunch of labeled data for a classifier. If folks are interested in reading more there's a nice paper by Grammatech on the idea: https://eschulte.github.io/data/bed.pdf https://eschulte.github.io/data/bed.pdf (though it's pre-LLM and uses evolutionary algorithms on the initial decompilation to search for a version that recompiles exactly).
- Eager 3y ago
  You try your best, and if you provide enough examples, it will undoubtedly get figured out.
  - junon 3y ago
    Err, no, sorry, it won't. Compilers don't work that way. There's a lot of ways to compile down source to machine code and the output changes from compiler version to compiler version. The LLM would have to know exactly how the compiler worked at which version to do this. So the idea is technically possible but not technically feasible.
  - deleted 3y ago
    [deleted]
  - thfuran 3y ago
    What exactly are you suggesting will get figured out?
    - spqrr 3y ago
      The mapping from binary to source code.
      - layer8 3y ago
        The question was about the reverse mapping.
      - thfuran 3y ago
        Even ignoring all sources of irreproducibility, there does not exist a bijection between source and binary artifact irrespective of tool chain. Two different toolchains could compile the same source to different binaries or different sources to the same binary. And you absolutely shouldn't be ignoring sources of irreproducibility in this context, since they'll cause even the same toolchain to keep producing different binaries given the same source.
        achrono 3y ago
        Exactly, but neither the source nor the binary is what's truly important here. The real question is: can the LLM generate the functionally valid source equivalent of the binary at hand? If I disassemble Microsoft Paint, can I get code that will result in a mostly functional version of Microsoft Paint, or will I just get 515 compile errors instead?
- dheera 3y ago
  Maybe we then need an LLM to tell us if two pieces of compiled code are equivalent in an input-output mapping sense (ignoring execution time). I'm actually serious; it would be exceedingly easy to get training data for this just by running the same source code through a bunch of different compiler versions and optimization flags.
  - saagarjha 3y ago
    An LLM cannot do this. I don’t even mean this in a formal sense, because your problem is addressed by Rice’s Theorem, which places bounds on what any system (LLM or not) can do here; I mean it in the sense that an LLM isn’t even appropriate to use here because the best it can possibly do is provide you with its best guess at the answer. And while this might be a useful property for decompilation in general that’s not what was being discussed here.
    - dheera 3y ago
      Rice's theorem does NOT prevent a program from giving correct answers to non-trivial properties of programs (including the halting problem or other undecidable problems) for 99.99% of inputs and "I don't know" for 0.01% of inputs. It only states that you cannot write a program that provides a correct and definitive yes-or-no for 100% of inputs. For a decompiler, being able to decompile even 90% of programs would be awesome. We're not looking for theoretical perfectness.
  - thfuran 3y ago
    Why would an llm be the tool for that job?
    - dheera 3y ago
      Without analytical thinking how else would you come to conviction that two functions are identical, for a computationally unfeasible number of possible inputs?
      - kolinko 3y ago
codethief 3y ago
> you should get the original binary According to the project's README, they only seem to be checking mere "re-compilability" and "re-executability" of the decompiled code, though.
1024core 3y ago
> If you decompile the binary to source, then compile the source back to binary you should get the original binary. Doesn't that depend on the compiler's version though? Or, for that matter, even the sub-version. Every compiler does things differently.
- fulafel 3y ago
  From the README: > By re-compiling the decompiled output and running the test cases, we assess if the decompilation preserved the program logic and behavior. As this is in the metrics section, I guess fully automating this is not part of the research.

by Eager 3y ago

thfuran 3y ago

>If you decompile the binary to source, then compile the source back to binary you should get the original binary. You really can't expect that if you're not using exactly the same version of exactly the same compiler with exactly the same flags, and often not even then.

vasvir 3y ago
Right. A less formidable problem with higher chances of succeeding is from a given binary to figure out first compiler, compiler-version, compiler-flags. From there you could have a model for every combination or at least a model for the compiler variant and use the other info (version, flags) as input to the model.
moyix 3y ago
Yes, that's a limitation of trying to ensure exact binary reconstruction. Luckily there is also a separate line of work on detecting the compiler version and optimization flags based on a binary – it turns out this is not that hard and it's easy to get a bunch of labeled data for a classifier. If folks are interested in reading more there's a nice paper by Grammatech on the idea: https://eschulte.github.io/data/bed.pdf https://eschulte.github.io/data/bed.pdf (though it's pre-LLM and uses evolutionary algorithms on the initial decompilation to search for a version that recompiles exactly).
Eager 3y ago
You try your best, and if you provide enough examples, it will undoubtedly get figured out.
- junon 3y ago
  Err, no, sorry, it won't. Compilers don't work that way. There's a lot of ways to compile down source to machine code and the output changes from compiler version to compiler version. The LLM would have to know exactly how the compiler worked at which version to do this. So the idea is technically possible but not technically feasible.
- deleted 3y ago
  [deleted]
- thfuran 3y ago
  What exactly are you suggesting will get figured out?
  - spqrr 3y ago
    The mapping from binary to source code.
    - layer8 3y ago
      The question was about the reverse mapping.
    - thfuran 3y ago
      Even ignoring all sources of irreproducibility, there does not exist a bijection between source and binary artifact irrespective of tool chain. Two different toolchains could compile the same source to different binaries or different sources to the same binary. And you absolutely shouldn't be ignoring sources of irreproducibility in this context, since they'll cause even the same toolchain to keep producing different binaries given the same source.
      - achrono 3y ago
        Exactly, but neither the source nor the binary is what's truly important here. The real question is: can the LLM generate the functionally valid source equivalent of the binary at hand? If I disassemble Microsoft Paint, can I get code that will result in a mostly functional version of Microsoft Paint, or will I just get 515 compile errors instead?
dheera 3y ago
Maybe we then need an LLM to tell us if two pieces of compiled code are equivalent in an input-output mapping sense (ignoring execution time). I'm actually serious; it would be exceedingly easy to get training data for this just by running the same source code through a bunch of different compiler versions and optimization flags.
- saagarjha 3y ago
  An LLM cannot do this. I don’t even mean this in a formal sense, because your problem is addressed by Rice’s Theorem, which places bounds on what any system (LLM or not) can do here; I mean it in the sense that an LLM isn’t even appropriate to use here because the best it can possibly do is provide you with its best guess at the answer. And while this might be a useful property for decompilation in general that’s not what was being discussed here.
  - dheera 3y ago
    Rice's theorem does NOT prevent a program from giving correct answers to non-trivial properties of programs (including the halting problem or other undecidable problems) for 99.99% of inputs and "I don't know" for 0.01% of inputs. It only states that you cannot write a program that provides a correct and definitive yes-or-no for 100% of inputs. For a decompiler, being able to decompile even 90% of programs would be awesome. We're not looking for theoretical perfectness.
- thfuran 3y ago
  Why would an llm be the tool for that job?
  - dheera 3y ago
    Without analytical thinking how else would you come to conviction that two functions are identical, for a computationally unfeasible number of possible inputs?
    - kolinko 3y ago

codethief 3y ago

> you should get the original binary According to the project's README, they only seem to be checking mere "re-compilability" and "re-executability" of the decompiled code, though.

1024core 3y ago

> If you decompile the binary to source, then compile the source back to binary you should get the original binary. Doesn't that depend on the compiler's version though? Or, for that matter, even the sub-version. Every compiler does things differently.

fulafel 3y ago
From the README: > By re-compiling the decompiled output and running the test cases, we assess if the decompilation preserved the program logic and behavior. As this is in the metrics section, I guess fully automating this is not part of the research.