32

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.

7
  • 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, 2013 at 10:23
  • Is that better? Mar 27, 2013 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. Mar 27, 2013 at 10:37
  • 3
    @IgorSkochinsky Did you just call your Hex-Rays decompiler crappy with that edit? :P Mar 27, 2013 at 10:39
  • Well I was going with the general sentiment you can read in many of such questions :)
    – Igor Skochinsky
    Mar 27, 2013 at 10:41

4 Answers 4

45

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.

1
  • 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.
    – Jongware
    Oct 19, 2013 at 23:01
11

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.

2

As someone who has worked on a suite of Python decompilers, I have thought about this a bit.

I am going to take a different tack than other bottom-up answers; I start to describe the situation from a slightly more general and philosophical side which I think is easy to see.

tl;dr:

Think of this as a common situation where someone is trying to reconstruct an object from its fragmented pieces. For example why might a smashed sandcastle be harder to reconstruct than a broken ceramic vase? From this point of view, there would be no surprise. For sure, a real explanation of the sand versus ceramic problem would involve adhesion strength of the materials, properties of fracturing for the materials involved, and mending techniques. Similarly, the properties of computer languages, compilers, runtime systems, machine code and decompilation techniques can vary just as much as sand castles and ceramic vases.

A little background

In general, compilation performs a kind of information entropy loss. This may seem surprising since the source code and the binary object are supposed to be semantically identical. Yes, that is true, but only with respect to how computers understand the world.

And although humans were the inventors or creators of computers, it seems strange that the world in which the computer operates, its "experience" of the world, is already so different than the experience of a human programmer.

It is easier to build a machine that just understands how to perform logic, arithmetic, read memory locations, and jump to different program states than it is to build a computer that inherently understands concepts in programming and its patterns and paradigms, algorithms, or data structures which is the level that programmers may operate in.

So in a sense, one thing that fascinates me here is the inherent problem of communicating between different forms of "intelligence". If it is this hard here, the simplistic idea that we would ever be able to communicate with some sort of alien life where our level of shared experience may be much less is, in my opinion almost hopeless. In addition to the problems seen in decompilation, you have additional problems with transmission speed and delay, and just topics that we might both be interested in.

As an example, using the cited "Universal Language" of Mathematics, if intelligent life is in a highly curved geometry where all "parallel" lines always touch or always diverge, then all this Euclidean Geometry would be super boring for that alien since it would have no practical use. And Shakespeare's Poetry - forget about it!

Factors that go into the level of goodness in translation

Although the question posed here is pretty specific, it is also a bit general or maybe vague. Here are factors that go into the ease (and thus quality) that a decompiler can provide:

  • What was the source language used?
  • How long, sophisticated and complex is the code to be decompiled?
  • What specific compiler was used?
  • What compiler/translator options were specified along the various pipelines that were involved in the translation?
  • Which kind of native code?
  • Which specific decompiler was used and what techniques were used there?
  • Was there any other packaging, encryption, or code obfuscation done?

Before delving into each of the categories above, let me first give an analogy using that general principle that basically we are going against information entropy or information loss.

Why is it that reconstructing a sand castle is harder than a vase that has been shattered?

I suppose this question is a bit general as was question posed. The answer partially depends on how much effort was used to create the initial object, sand castle versus a ceramic vase. One can imagine a very simple primitive sand castle that does not have a lot of detail. Maybe it is just a box of some form. That would be easy to reconstruct while an intricate sand castle would be very hard to reconstruct.

The complexity of the program is analogous to the shape of the object we are trying to reconstruct. If your source code or machine code is small and simple, you'd might just dispense with the decompiler and try to understand the machine code.

And the material for the end result and processes used to create it are important too.

Reconstructing things made out of sand is much harder than ceramic that has a couple of well-defined factures. This is like the kind of object that gets run: binary code or bytecode. For bytecode, some are higher level then others. Python bytecode, Pascal P-code or GNU Emacs bytecode is more like ceramic than ARM assembly which is more like sand.

Also, how our sand castle or vase were destroyed is important too. Was the sand castle just kicked once or was at worn away by the tide repeatedly? And was the vase just accidentally dropped on the floor once or was it smashed to little pieces by a hammer?

The analogous process here has the compilation process. Was this a "one-pass" compiler like CPython or a multi-stage compilation pipeline that say GNU gcc or clang do where levels of "optimization" have been turned on?

And finally we get to the amount of effort or care you want to put in to recreating the initial object. If this vase is not of much value to you, you probably won't bother to do a careful and accurate job if you bother at all. Getting something approximately vase like, might be good enough for your needs. However if the vase is precious, well then you probably will spend a lot of effort to reconstruct the original. In fact when my mother broke a vase that she considered a precious heirloom, she hired professionals from the Smithsonian Museum in Washington DC to reconstruct the part of the vase that was broken.

Some of the Details

Having the above out of the way, we can get to the nitty gritty. Just as with sand castles versus ceramic vases, I'll focus on two examples which are at opposite extremes.

But first some factors to consider.

Decompilation quality depends on:

  • the language the code was written in
  • The compiler you started with
  • compiler flags,
  • code object
  • the specific decompiler used
  • Additional packaging and/or deliberate obfuscation

I will give an example that I know very well.

Python/CPython/uncompyle6

  • language: Python (versions matter, but overall let's say in the 1.5 to 3.8 range)
  • compiler: CPython
  • compiler flags - none (which is the default)
  • code object: : High-level custom bytecode
  • specific decompiler: uncompyle6 or decompyle3 (for 3.7 and 3.8)
  • maintenance effort of decompiler: basically one unpaid volunteer person, me

Many people have noted that this decompiles very well. Here are the factors why this is so:

Python stores docstring comments in the code which is nice for humans looking at decompiled code, although it doesn't really change the decompilation process. Also there are standards for Python code formatting. So if the human and decompiler follow the same standard and there is basically only one, the the result will look similar.

The CPython compiler is a "one pass" compiler that doesn't do much in the way of code improving or code transformations. But as we move to later versions, More recent versions of CPython has been doing more here.

Python bytecode is also extremely high level. Variable, class, function and module names are all preserved. Python and Python bytecode are loose with type declarations.

The Python decompiler that I have been working on and maintaining makes use very specific idioms that can be found in instruction patterns. Since early Python translated everything one way (even though in theory there are many ways that it could choose), this kind of pattern driven approach is able to disambiguate between semantically identical code. For example if x: if y: ... versus if x and y. Earlier CPython create different kinds of code fragments for nested ifs versus and.

C/gcc/-O/ARM/Ghidra

Here I compare that with something at the other extreme and that I know less well. Some aspecs I know only vaguely.

  • language: C
  • compiler gcc
  • compiler flags -O (typically used)
  • code object ARM
  • specific decompiler: Ghidra?
  • maintenance effort of decompiler: probably more than one person, paid either via grant or as part of some other job-related duty

Python docstrings are, I suppose, a form of comment. In C any sort of document commenting is form of a comment; and all comments in C are stripped.

GCC is at least 3 or 4 distinct phases. C preprocessor, C compiler to assembly, assembly, and then a linking phase. The C compiler phase though can make several passes over the AST it produces, and or the instructions it produces. There is a lot of opportunity for code mangling that may need to be undone.

Unless you have symbol table generation turned on, -g, the mapping of memory locations and/or registers to names is gone. At the assembly level, any structure or type information is gone.

C indention can come in one of several varieties. One could run the result through a formatter, assuming the Ghidra produces valid C. But I suspect it doesn't.

It is very possible that nested if and && could compile to the same instructions. And there may be more than one template that a compiler might use for a single construct.

But even if a particular compiler for a particular language is passed a particular set of options that compiles if and && differently, I doubt that the way Ghidra's decompiler hones in on a specific compiler's code idioms for most things. My understanding is that the decompiler(s) in Ghidra are general purpose which means that they do not take into consideration that specific language, compiler or compiler options used. They work the same way on machine code whether the compiler used was gcc, clang or some vendor's C compiler like the ones IBM or Intel have. Or whether the source language was C++ instead of C.

And this is an interesting aspect too. It takes a bit of effort to teach a decompiler about some specific compiler's quirks or habits. These things can change over time depending on the language and within a language like C, C compiler and compiler version, and the assembly language that is produced. Since there are:

  • many different kinds of front end languages,
  • many different translators,
  • compilers releases constantly changing code-generation methods
  • the variations in code generation for the same construct (sometimes randomness may play a role here), and
  • many different back ends

it probably isn't worth the maintenance effort to hone in on idiosyncrasies of a particular compiler system at a particular point in time.

In the CPython/Python case, there is basically only one compiler CPython. Bytecode does vary from major release. For example between 3.5 to 3.6 there were a number of bytecode changes. However a Major release is on the order of a year. And many times the code generation doesn't change. However Python bytecode does vary a lot more than many other kinds of bytecode. Most bytecode stays the same. JVM stays largely the same. Emacs bytecode and P-Code stay the same over longer periods of time.

Because Ghidra is general purpose, it has a general purpose algorithm for detecting control flow. In uncompyle6 and decompyle3 we can do pretty well using the patterns approach. There has been some problem with control flow in the past, but recent not public versions of this code do very well by adding basic block and dominator information as pseudo instructions of the bytecode. Basically you can think of the instructions having additional parenthesis and comma marks to help detect nesting versus sequencing around jumps.

As for maintenance, I imagine there have been more than one person working on the decompilation aspect. And I imagine that person is funded at least partially by grants if this is not a part of the person's day job.

I mention the maintenance aspect because the person-hours that are spent on decompilers is much less than the person-hours spent in the compiler code generation.

1

Java and .NET both include a feature called "reflection", which makes it possible to access inner workings of a class and instances thereof, using runtime-generated strings that hold the names of those features. In C code, if one includes a structure definition:

struct foo { int x,y,z,supercalifragilisticexpialidocious; };

expressions that access field supercalifragilisticexpialidocious will generate machine code that accesses an int-sized object at offset 3*sizeof(int) in the structure, but nothing in the machine code will care about the name.

In C# by contrast, if code that was running with suitable Reflection permissions were to generate the string x, y, z, supercalifragilisticexpialidocious, or woof somehow, and used Reflection functions to retrieve the value of the field having that name (if any) from an instance of that type, the Runtime would need to have access to the names of those fields. Even if a program would in fact never use Reflection to access the fields by name, there would generally be no way the Compiler could know that. Thus, compilers need to include within executable programs the names of almost all identifiers used the source code, without regard for whether anything would ever care about whether or not they did so.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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