29

Java and .NET decompilers can (usually) produce an almost perfect source code, often very close to the original.

Why can't the same be done for the native code? I tried a few but they either don't work or produce a mess of gotos and casts with pointers.

  • 1
    Its great that you wrote this post, however it still needs to be in the form of a Q&A. If you could turn this into a set of questions, then it would be even better :) – asheeshr Mar 27 '13 at 10:23
  • Is that better? – Rolf Rolles Mar 27 '13 at 10:33
  • Do you really expand on how to make recovery of high level code difficult? I would skip that part of the question and simply make this about decompilation. Your answer is very good though imo. – Peter Andersson Mar 27 '13 at 10:37
  • 3
    @IgorSkochinsky Did you just call your Hex-Rays decompiler crappy with that edit? :P – Peter Andersson Mar 27 '13 at 10:39
  • Well I was going with the general sentiment you can read in many of such questions :) – Igor Skochinsky Mar 27 '13 at 10:41
40

TL;DR: machine code decompilers are very useful, but do not expect the same miracles that they provide for managed languages. To name several limitations: the result generally can't be recompiled, lacks names, types, and other crucial information from the original source code, is likely to be much more difficult to read than the original source code minus comments, and might leave weird processor-specific artifacts in the decompilation listing.

  1. Why are decompilers so popular?

    Decompilers are very attractive reverse engineering tools because they have the potential to save a lot of work. In fact, they are so unreasonably effective for managed languages such as Java and .NET that "Java and .NET reverse engineering" is virtually non-existent as a topic. This situation causes many beginners to wonder whether the same is true for machine code. Unfortunately, this is not the case. Machine code decompilers do exist, and are useful at saving the analyst time. However, they are merely an aid to a very manual process. The reason this is true is that bytecode language and machine code decompilers are faced with a different set of challenges.

  2. Will I see the original variable names in the decompiled source code?

    Some challenges arise from the loss of semantic information throughout the compilation process. Managed languages often preserve the names of variables, such as the names of fields within an object. Therefore, it is easy to present the human analyst with names that the programmer created which hopefully are meaningful. This improves the speed of comprehension of decompiled machine code.

    On the other hand, compilers for machine-code programs usually destroy most of all of this information while compiling the program (perhaps leaving some of it behind in the form of debug information). Therefore, even if a machine code decompiler was perfect in every other way, it would still render non-informative variable names (such as "v11", "a0", "esi0", etc.) that would slow the speed of human comprehension.

  3. Can I recompile the decompiled program?

    Some challenges relate to disassembling the program. In bytecode languages such as Java and .NET, the metadata associated with the compiled object will generally describe the locations of all code bytes within the object. I.e., all functions will have an entry in some table in a header of the object.

    In machine language on the other hand, to take x86 Windows disassembly for example, without the help of heavy debug information such as a PDB the disassembler does not know where the code within the binary is located. It is given some hints such as the entrypoint of the program. As a result, machine code disassemblers are forced to implement their own algorithms to discover the code locations within the binary. They generally use two algorithms: linear sweep (scan through the text section looking for known byte sequences that usually denote the beginning of a function), and recursive traversal (when a call instruction to a fixed location is encountered, consider that location as containing code).

    However, these algorithms generally will not discover all of the code within the binary, due to compiler optimizations such as interprocedural register allocation that modify function prologues causing the linear sweep component to fail, and due to naturally-occurring indirect control flow (i.e. call via function pointer) causing the recursive traversal to fail. Therefore, even if a machine code decompiler encountered no problems other than that one, it could not generally produce a decompilation for an entire program, and hence the result would not be able to be recompiled.

    The code/data separation problem described above falls into a special category of theoretical problems, called the "undecidable" problems, which it shares with other impossible problems such as the Halting Problem. Therefore, abandon hope of finding an automated machine code decompiler that will produce output that can be recompiled to obtain a clone of the original binary.

  4. Will I have information about the objects used by the decompiled program?

    There are also challenges relating to the nature of how languages such as C and C++ are compiled versus the managed languages; I'll discuss type information here. In Java bytecode, there is a dedicated instruction called 'new' to allocate objects. It takes an integer argument which is interpreted as a reference into the .class file metadata which describes the object to be allocated. This metadata in turn describes the layout of the class, the names and types of the members, and so on. This makes it very easy to decompile references to the class in a way that is pleasing to the human inspector.

    When a C++ program is compiled, on the other hand, in the absence of debug information such as RTTI, object creation is not conducted in a neat and tidy way. It calls a user-specifiable memory allocator, and then passes the resulting pointer as an argument to the constructor function (which may also be inlined, and therefore not a function). The instructions that access class members are syntactically indistinguishable from local variable references, array references, etc. Furthermore, the layout of the class is not stored anywhere in the binary. In effect, the only way to discover the data structures in a stripped binary is through data flow analysis. Therefore, a decompiler has to implement its own type reconstruction in order to cope with the situation. In fact, the popular decompiler Hex-Rays mostly leaves this task up to the human analyst (though it also offers the human useful assistance).

  5. Will the decompilation basically resemble the original source code in terms of its control flow structure?

    Some challenges stem from compiler optimizations having been applied to the compiled binary. The popular optimization known as "tail merging" causes the control flow of the program to be mutilated compared to less-aggressive compilers, which usually manifests itself as a lot of goto statements within the decompilation. The compilation of sparse switch statements can cause similar problems. On the other hand, managed languages often have switch statement instructions.

  6. Will the decompiler give meaningful output when obscure facets of the processor are involved?

    Some challenges stem from architectural features of the processor in question. For example, the built-in floating point unit on x86 is a nightmare of an ordeal. There are no floating point "registers", there is a floating point "stack", and it must be tracked precisely in order for the program to be properly decompiled. In contrast, managed languages often have specialized instructions for dealing with floating-point values, which are themselves variables. (Hex-Rays handles floating point arithmetic just fine.) Or consider the fact that there are many hundreds of legal instruction types on x86, most of which are never produced by a regular compiler without the user explicitly specifying that it should do so via an intrinsic. A decompiler must include special processing for those instructions which it supports natively, and so most decompilers simply include support for the ones most commonly generated by compilers, using inline assembly or (at best) intrinsics for those which it does not support.

These are merely a few of the accessible examples of challenges that plague machine code decompilers. We can expect that limitations will remain for the foreseeable future. Therefore, do not seek a magic bullet that is as effective as managed language decompilers.

  • do you prefer a new answer for additional aspects or editing those into your answer? Generally I feel uncomfortable with editing at this rep level (maybe it's different for private betas?), because it ends up in a queue and such. But whatever. So which is it? :) – 0xC0000022L Mar 27 '13 at 17:07
  • You can feel free to edit it, or suggest new topics and I'll edit it. – Rolf Rolles Mar 27 '13 at 22:07
  • On 6. When code has gone through pipeline optimization, a logical sequence of single operations may get mixed with the previous and/or next logical block of operations. – usr2564301 Oct 19 '13 at 23:01
7

Decompilation is difficult because decompilers must recover source-code abstractions that are missing from the binary/bytecode target.

There are several types of abstractions:

  • Functions: The identification of code corresponding to a high function, with its entrance, arguments, return value(s) ,and exit.
  • Variables: The local variables in each function, and any global or static variables.
  • Types: The type of each variable, and each function's arguments and return value.
  • High-level control flow: The control flow schema of a program, e.g., while (...) { if (...) {...} else {...} }

Decompiling native code is difficult because none of these abstractions are represented explicitly in the native code. Thus, to produce nice decompiled code (i.e., not using gotos everywhere), decompilers must reinfer these abstractions based on the behavior of the native code. This is a difficult process, and many papers have been written on how to infer those abstractions. See Balakrishnan and Lee for starters.

In contrast, bytecode is easier to decompile because it usually contains enough information to permit type checking. As a result, bytecode typically contains explicit abstractions for functions (or methods), variables, and the type of each variable. The primary abstraction missing in bytecode is high-level control flow.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.