4 ms·

How decompilers work

82 points by drx 15y ago

demallien 15y ago
The cynical part of me wants to respond with one word: badly! But I've spent enough time hand-reversing code to know that that doesn't do justice to the work done by decompiler writers, it's just that it's a problem that requires strong AI to do it properly.
- ma2rten 15y ago
  why do you think that ? I actually would think that just statistics would also work.
  - demallien 15y ago
    Because for two years it was my job to make sure that decompilers didn't work on code generated by my company... It's so easy to throw automatic analysis tools of the track. It's easy to throw humans, and we're way better at this game than automated tools, at least for the time being. To give you an idea of how easy it is, if you want the decompiler to drop the ball on a for-loop, all you need to do is something simple like increment by two and then decrement by one at the start of the loop body... The tool might be looking for the use of an INC instruction, but because you increment by two, the compiler generates an ADD... and now your tool doesn't know how to recognise the loop.
    - verroq 15y ago
      I don't think anyone uses decompilers to analyse machine code.
      - demallien 15y ago
        Err, what do you think decompilers are for then?
        verroq 15y ago
        Well in reversing applications, most people use disassemblers and debuggers to step/trace/analyse the machine code. Just because they exist doesn't mean what they provide is of any practical value, as you said it yourself they decompile badly.
        swolchok 15y ago
        The Hex-Rays decompiler is very good, and I've used it for reversing several times. In particular, it was extremely useful for our analysis of the Green Dam censorware system (http://www.cse.umich.edu/~jhalderm/pub/gd/ http://www.cse.umich.edu/~jhalderm/pub/gd/).
        Luyt 15y ago
        Thanks for exposing that shipwreck of government-mandated Horrorware. From the Wikipedia article: "As of 30 June 2009, the mandatory pre-installation of the Green Dam software on new computers has been delayed to an undetermined date." Source: http://en.wikipedia.org/wiki/Green_Dam http://en.wikipedia.org/wiki/Green_Dam
        DCoder 15y ago
        The decompilation quality really depends on how obfuscated the original code was, and how much time you care to invest. For example, I'm using Hex-Rays to decompile Command & Conquer: Red Alert 2 and extend it, and now its output looks like [1] , which is a lot better than raw assembly menemonics. Though I've been digging into this game since late 2008, which is a long time. [1] http://img824.imageshack.us/img824/1188/hexrayscpp.png http://img824.imageshack.us/img824/1188/hexrayscpp.png
    - zeugma 15y ago
      What was the reason to do that ? Apart from rendering your own code completely unreadable ?
      - ma2rten 15y ago
        That is exactly what I though. I don't know enough about decompilation to argue with OP, but it is my impression that people are too focused on making something that is always guaranteed to work. If you would use some kind of statistical machine learning instead and learn from data (like machine translation for human languages), I would think that you can come a long way, or am I mistaken?
- mjb 15y ago
  I don't thing strong AI would solve the problem, because one crucial piece of data is lost when the code is compiled: the intention of the programmer. Good code clearly indicates its intended function through structure, most of which does not translate into assembly. When decompiled, this structure needs to be inferred from the assembly, which contains an incomplete view of the required information. This missing information includes, but is not limited to, the extra information that the programmer put in deliberately: class names, variable names, comments, etc. They also encoded a large number of assumptions about typical program inputs, the execution environment, expected and unexpected branches, chunks of logic (classes, functions, etc) into the code. With all this lost, even a strong AI would not be able to piece together the original program. Instead, I think, the best that could be hoped for is a sort of uncanny-valley zombie of the original code. Certainly better than nothing, but totally not a replacement for your dead wife.
  - demallien 15y ago
    No, strong AI will solve the problem - just ask geohots... The system that is uncrackable has not yet been invented, the best we've been able to do is to make the process slower.
    - mjb 15y ago
      I think it comes down to which problem you are trying to solve: 1) Recover enough to understand the program and make small changes (this is the cracking case). 2) Recover the original code of the program or something close to it, that can be 'stolen' and maintained without much more overhead than if you had the original code. (1) is not easy, but is becoming easier. (2) is still a long way off, and isn't solvable without a good understanding of the domain the original code was written for.
      - spc476 15y ago
        There are legitimate cases for (2). I've worked in companies that have lost the source code to programs developed. If you're wondering how source code can be lost---think of no revision control, a poor backup policy, and a program that goes a long time between modifications.
- drx 15y ago
  > The cynical part of me wants to respond with one word: badly! You are right. Decompiling seems hopeless when you look at the problem. Which is one of the reasons why I wrote my decompiler -- to see what can be done. That also depends on what problem you think decompilers are to solve. Decompilers are somewhat good at telling you additional information about the original structure of the program. They suck at recovering the original source code (which, with enough optimization and mangling, is impossible).
- JoeAltmaier 15y ago
  Decompiled code can end up looking like high-level assembly code. Like a programmer just learning a new language, using all the habits of their old one. You have to call decompiling a success if the result executes the same algorithm. Much more than that is very hard. I wrote a similar conversion tool - PL/M to C - years ago. It did quite a good job, because it had semantic clues (not to mention the original variable names). And even that can be done badly - the 1st pass result folks called "CL/M" because it was obviously not written by a C programmer.
- leon_ 15y ago
  After playing around with the Hexrays C decompiler we got I decided to stay with analyzing disassemblies.
- grav1tas 15y ago
  Applying AI to a decompilation problem is just like applying AI to a compilation problem. You're taking a potentially nondeterministic approach to a problem that should be formalized and deterministic. I think AI applied to compilers is something to avoid, in general.
  - hackinthebochs 15y ago
    >Applying AI to a decompilation problem is just like applying AI to a compilation problem I think they're very different. Compilation strips semantic information from code. Decompilation attempts to recover semantic information from program structure and, in the AI case, domain knowledge. They are fundamentally different processes.
    - grav1tas 15y ago
      That's fine that they're different. My point is that they're both formal processes. Adding AI to the mix will not help you arrive at formal conclusions. The conclusions will be probabilistic, instead. If an AI could use formal routines to show you formal conclusions, then you wouldn't need an AI, you'd just need your routines.
      - jerf 15y ago
        And those formal processes will tell you, in the most formal of manners, that when information is actually removed from a system that by definition of information you are incapable of formally reconstructing it. If you can reconstruct it, by definition it was not removed in the first place. Intent is gone from compiled code. You can not formally reconstruct it. All you could formally get are reasonable guesses, and actually that's what the decompiler is giving you; it is not hard to interpret its output as very precisely vague on exactly the points it does not know about.
xcallemjudasx 15y ago
As a college student I found this article very easy to read and understand. It gave a simple enough overview with enough detail to explain but not confuse.
phillijw 15y ago
Am I misunderstanding how to program or does this line look wrong? It appears to be missing the open curly brace. > if (m == 0) return n + 1;}
shasta 15y ago
Decompilation is undecidable? "you cannot write an algorithm that would decompile every possible piece of code" I'm not sure what claim is actually being made here, but decompilation of any particular compiler is trivially decidable: try every input program until you find the one that produces the observed output.
- drx 15y ago
  The compiler isn't part of the input. You could get code that was compiled by a compiler not available to you. When the compiler is part of the input, then yes, the problem is decidable.
  - shasta 15y ago
    I'm still doubtful. I think you're trying to invoke Rice's theorem here, but I don't think it really applies. Compilers don't apply arbitrary transformations that preserve behavior - they only employ transformations that are understood to preserve behavior.
  - demallien 15y ago
    I don't think it is decidable even when you have the compiler available to you - what happens if I decide to insert a bunch of assembly code in my gcc-compiled program using the gcc embedded assembly extensions? How do I decide that a particular sequence of generated op-codes is actually impossible from pure C code, and hence must have been assembly in the original program?
    - peti 15y ago
      In that case, the GCC extension is part of the input language (in a broader sense). Still, your example clearly shows the difficulties involved in practice.
  - nandemo 15y ago
    The problem only makes sense if the compiler is fixed. Otherwise, it's trivial: for any input x I can say the source code is x. It's source code written in a programming language called MachineLanguage. The compiler is called cat.
T-R 15y ago
Have you tried applying any of this to (segments of) 68k binaries? You mentioned that a decompiler would have been only slightly useful for older games written in C/C++; is flow analysis not helpful in practice for simplifying code that was originally hand-coded in assembly? Edit1: Thanks for the link to the paper[1], by the way. Do you know of any other good resources? Edit2: Nevermind, I see you have them in github[2]. Thanks again. [1] http://www.ci.tuwien.ac.at/~grill/decompilation_thesis.pdf http://www.ci.tuwien.ac.at/~grill/decompilation_thesis.pdf [2] https://github.com/drx/ocd https://github.com/drx/ocd
- drx 15y ago
  I've started writing a 68k ASM module a while ago but I never finished. Hand-coded assembly code is better in that it's less optimized and mangled. But worse in that it has much less structure -- I can't convert ASM code into C. Each programmer has its own way of implementing certain programming patterns, etc. IDA Pro is actually quite good at flow analysis of ASM code.
- drx 15y ago
  As I can't edit my post any more, and you don't have an email address in your profile, I will double post. > Do you know of any other good resources? The thesis has many references, I would start with that.

82 points by drx 15y ago

The cynical part of me wants to respond with one word: badly! But I've spent enough time hand-reversing code to know that that doesn't do justice to the work done by decompiler writers, it's just that it's a problem that requires strong AI to do it properly.

ma2rten 15y ago
why do you think that ? I actually would think that just statistics would also work.
- demallien 15y ago
  Because for two years it was my job to make sure that decompilers didn't work on code generated by my company... It's so easy to throw automatic analysis tools of the track. It's easy to throw humans, and we're way better at this game than automated tools, at least for the time being. To give you an idea of how easy it is, if you want the decompiler to drop the ball on a for-loop, all you need to do is something simple like increment by two and then decrement by one at the start of the loop body... The tool might be looking for the use of an INC instruction, but because you increment by two, the compiler generates an ADD... and now your tool doesn't know how to recognise the loop.
  - verroq 15y ago
    I don't think anyone uses decompilers to analyse machine code.
    - demallien 15y ago
      Err, what do you think decompilers are for then?
      - verroq 15y ago
        Well in reversing applications, most people use disassemblers and debuggers to step/trace/analyse the machine code. Just because they exist doesn't mean what they provide is of any practical value, as you said it yourself they decompile badly.
        swolchok 15y ago
        The Hex-Rays decompiler is very good, and I've used it for reversing several times. In particular, it was extremely useful for our analysis of the Green Dam censorware system (http://www.cse.umich.edu/~jhalderm/pub/gd/ http://www.cse.umich.edu/~jhalderm/pub/gd/).
        Luyt 15y ago
        Thanks for exposing that shipwreck of government-mandated Horrorware. From the Wikipedia article: "As of 30 June 2009, the mandatory pre-installation of the Green Dam software on new computers has been delayed to an undetermined date." Source: http://en.wikipedia.org/wiki/Green_Dam http://en.wikipedia.org/wiki/Green_Dam
        DCoder 15y ago
        The decompilation quality really depends on how obfuscated the original code was, and how much time you care to invest. For example, I'm using Hex-Rays to decompile Command & Conquer: Red Alert 2 and extend it, and now its output looks like [1] , which is a lot better than raw assembly menemonics. Though I've been digging into this game since late 2008, which is a long time. [1] http://img824.imageshack.us/img824/1188/hexrayscpp.png http://img824.imageshack.us/img824/1188/hexrayscpp.png
  - zeugma 15y ago
    What was the reason to do that ? Apart from rendering your own code completely unreadable ?
    - ma2rten 15y ago
      That is exactly what I though. I don't know enough about decompilation to argue with OP, but it is my impression that people are too focused on making something that is always guaranteed to work. If you would use some kind of statistical machine learning instead and learn from data (like machine translation for human languages), I would think that you can come a long way, or am I mistaken?
mjb 15y ago
I don't thing strong AI would solve the problem, because one crucial piece of data is lost when the code is compiled: the intention of the programmer. Good code clearly indicates its intended function through structure, most of which does not translate into assembly. When decompiled, this structure needs to be inferred from the assembly, which contains an incomplete view of the required information. This missing information includes, but is not limited to, the extra information that the programmer put in deliberately: class names, variable names, comments, etc. They also encoded a large number of assumptions about typical program inputs, the execution environment, expected and unexpected branches, chunks of logic (classes, functions, etc) into the code. With all this lost, even a strong AI would not be able to piece together the original program. Instead, I think, the best that could be hoped for is a sort of uncanny-valley zombie of the original code. Certainly better than nothing, but totally not a replacement for your dead wife.
- demallien 15y ago
  No, strong AI will solve the problem - just ask geohots... The system that is uncrackable has not yet been invented, the best we've been able to do is to make the process slower.
  - mjb 15y ago
    I think it comes down to which problem you are trying to solve: 1) Recover enough to understand the program and make small changes (this is the cracking case). 2) Recover the original code of the program or something close to it, that can be 'stolen' and maintained without much more overhead than if you had the original code. (1) is not easy, but is becoming easier. (2) is still a long way off, and isn't solvable without a good understanding of the domain the original code was written for.
    - spc476 15y ago
      There are legitimate cases for (2). I've worked in companies that have lost the source code to programs developed. If you're wondering how source code can be lost---think of no revision control, a poor backup policy, and a program that goes a long time between modifications.
drx 15y ago
> The cynical part of me wants to respond with one word: badly! You are right. Decompiling seems hopeless when you look at the problem. Which is one of the reasons why I wrote my decompiler -- to see what can be done. That also depends on what problem you think decompilers are to solve. Decompilers are somewhat good at telling you additional information about the original structure of the program. They suck at recovering the original source code (which, with enough optimization and mangling, is impossible).
JoeAltmaier 15y ago
Decompiled code can end up looking like high-level assembly code. Like a programmer just learning a new language, using all the habits of their old one. You have to call decompiling a success if the result executes the same algorithm. Much more than that is very hard. I wrote a similar conversion tool - PL/M to C - years ago. It did quite a good job, because it had semantic clues (not to mention the original variable names). And even that can be done badly - the 1st pass result folks called "CL/M" because it was obviously not written by a C programmer.
leon_ 15y ago
After playing around with the Hexrays C decompiler we got I decided to stay with analyzing disassemblies.
grav1tas 15y ago
Applying AI to a decompilation problem is just like applying AI to a compilation problem. You're taking a potentially nondeterministic approach to a problem that should be formalized and deterministic. I think AI applied to compilers is something to avoid, in general.
- hackinthebochs 15y ago
  >Applying AI to a decompilation problem is just like applying AI to a compilation problem I think they're very different. Compilation strips semantic information from code. Decompilation attempts to recover semantic information from program structure and, in the AI case, domain knowledge. They are fundamentally different processes.
  - grav1tas 15y ago
    That's fine that they're different. My point is that they're both formal processes. Adding AI to the mix will not help you arrive at formal conclusions. The conclusions will be probabilistic, instead. If an AI could use formal routines to show you formal conclusions, then you wouldn't need an AI, you'd just need your routines.
    - jerf 15y ago
      And those formal processes will tell you, in the most formal of manners, that when information is actually removed from a system that by definition of information you are incapable of formally reconstructing it. If you can reconstruct it, by definition it was not removed in the first place. Intent is gone from compiled code. You can not formally reconstruct it. All you could formally get are reasonable guesses, and actually that's what the decompiler is giving you; it is not hard to interpret its output as very precisely vague on exactly the points it does not know about.

xcallemjudasx 15y ago

As a college student I found this article very easy to read and understand. It gave a simple enough overview with enough detail to explain but not confuse.

phillijw 15y ago

Am I misunderstanding how to program or does this line look wrong? It appears to be missing the open curly brace. > if (m == 0) return n + 1;}

shasta 15y ago

Decompilation is undecidable? "you cannot write an algorithm that would decompile every possible piece of code" I'm not sure what claim is actually being made here, but decompilation of any particular compiler is trivially decidable: try every input program until you find the one that produces the observed output.

drx 15y ago
The compiler isn't part of the input. You could get code that was compiled by a compiler not available to you. When the compiler is part of the input, then yes, the problem is decidable.
- shasta 15y ago
  I'm still doubtful. I think you're trying to invoke Rice's theorem here, but I don't think it really applies. Compilers don't apply arbitrary transformations that preserve behavior - they only employ transformations that are understood to preserve behavior.
- demallien 15y ago
  I don't think it is decidable even when you have the compiler available to you - what happens if I decide to insert a bunch of assembly code in my gcc-compiled program using the gcc embedded assembly extensions? How do I decide that a particular sequence of generated op-codes is actually impossible from pure C code, and hence must have been assembly in the original program?
  - peti 15y ago
    In that case, the GCC extension is part of the input language (in a broader sense). Still, your example clearly shows the difficulties involved in practice.
- nandemo 15y ago
  The problem only makes sense if the compiler is fixed. Otherwise, it's trivial: for any input x I can say the source code is x. It's source code written in a programming language called MachineLanguage. The compiler is called cat.

T-R 15y ago

Have you tried applying any of this to (segments of) 68k binaries? You mentioned that a decompiler would have been only slightly useful for older games written in C/C++; is flow analysis not helpful in practice for simplifying code that was originally hand-coded in assembly? Edit1: Thanks for the link to the paper[1], by the way. Do you know of any other good resources? Edit2: Nevermind, I see you have them in github[2]. Thanks again. [1] http://www.ci.tuwien.ac.at/~grill/decompilation_thesis.pdf http://www.ci.tuwien.ac.at/~grill/decompilation_thesis.pdf [2] https://github.com/drx/ocd https://github.com/drx/ocd

drx 15y ago
I've started writing a 68k ASM module a while ago but I never finished. Hand-coded assembly code is better in that it's less optimized and mangled. But worse in that it has much less structure -- I can't convert ASM code into C. Each programmer has its own way of implementing certain programming patterns, etc. IDA Pro is actually quite good at flow analysis of ASM code.
drx 15y ago
As I can't edit my post any more, and you don't have an email address in your profile, I will double post. > Do you know of any other good resources? The thesis has many references, I would start with that.