Is there a tool capable of reconstructing structured code from arbitrary assembly code?

Question

Essentially, I'm looking for a tool that could reconstruct pseudocode with conditional operators, loops, break/continue, etc. from assembly language code for an arbitrary CPU, given only a limited understanding of the assembly constructs related to control flow, and taking anything that it doesn't understand as opaque blobs. Alternatively, it wouldn't need to understand any assembly if it could take pseudocode "if (condition) goto label" and "goto label" as basic block boundaries.

For example,

    blob1
    CMP A, B
    BLE L1
    blob2
    CMP C, D
    BEQ L2
L1: 
    blob3
    CMP E, F
    BGT L3
L2: 
    blob4
    ...
    B L4
L3: 
    blob5
L4: 
    blob6

Could become either something like

blob1;
if ( A > B && { blob2; C == D } || {blob3; E <= F} ) { 
    blob4;
} else {
    blob5;
}
blob6;

or a conventional tree of ifs, if blob2 and blob3 are "too large".

Also, the variables A to F don't have to follow any addressing mode conventions, they can be arbitrary strings, reproduced literally in the output. The tool doesn't need to know anything but how the labels look like, and the style of the comparison operators and the branches (one comparison instruction produces condition codes consumed by various branch instructions, vs. various comparison instructions produce a true/false value in a register, consumed by "branch if true" and "branch if false" instructions, etc).

Things become somewhat nontrivial when these structures are nested, labels are reused, break/continue were used in the source code, incidental non-structured control transfers may occur, and so on. Switch/case statements are separate story. To recognize them adequately, a deeper understanding of the underlying ISA is needed.

It appears that what I need is an implementation of the basic DREAM decompilation algorithm; I was unable to find a straightforward implementation that takes a CFG in a text format as input.

Answer 1

Initial comments:

• The process being described in the question is not decompilation

• The definition associated with the "decompilation" tag is not correct

• No tool in existence performs the described process, for several reasons:

  1. Any given assembly language is necessarily strongly related to the machine language of the target processor
  2. Due to the strong relationship between assembly code (text) and the object code (binary machine language) it is a symbolic representation of, it seems doubtful that the functional equivalent of a universal assembly language translator could exist in the first place
  3. Pseudocode by definition does not conform to a language specification. This precludes lexical analysis, which is an essential step in text to text transformation
  4. Decompilers do not accept arbitrary text as input, because they create CFGs from parsed machine code. Additionally, approaches to CFG contstruction differ between decompilers, because the CFGs are used to create intermediate representations which vary across decompilers.
  5. Since decompilers use architecture-independent intermediate representations to perform machine code to HLL translation, the need to develop a tool that somehow parses arbitrary pseudo-assembly does not exist
• While assembly source text instructions generally have a 1-to-1 relationship with target machine language instructions, intermediate representations can be language- and architecture-independent. It depends on the choice of intermediate representation

Decompilation

1. It is important to be able to refer to a correct definition of decompilation in order to get some sense of what it entails

As stated previously, the definition associated with the "decompilation" tag is not correct. Here it is:

Process of translating assembly code extracted from a binary file in a structured programming language, such as C.

We can compare this definition to correct definitions offered in academic literature:

A decompiler is a program that reads a program written in a machine language – the source language – and translates it into an equivalent program in a high-level language – the target language. A decompiler, or reverse compiler, attempts to reverse the process of a compiler which translates a high-level language program into a binary or executable program.¹

More directly:

At its surface, decompilation is the recovery of a program’s source code given only its binary. Underneath, decompilation consists of a collection of abstraction recovery mechanisms such as indirect jump resolution, control flow structuring, and data type reconstruction, which recover high-level abstractions that are not readily available in the binary form.²

Certain inferences can be made based on the correct definitions:

• The input to a decompiler is expected to be object code, not ASCII text or renditions of object code by way of mnemonics. To suggest - incorrectly - that assembly code (the symbolic language representation of machine code) is the expected input is a critical conceptual error. This is why the tag definition needs to be changed, as this error could lead to confusion or misunderstanding
• The purpose of decompilation is to create a semantic approximation by way a high level language of the operations encoded in the binary as object code. In order to create such an approximation to an acceptable degree of accuracy, a variety of methods are necessary to compensate for information loss that occurs during the compilation process. In other words, the less principled one is regarding abstraction recovery, the less accurately the decompiled source text will be as an approximation of information encoded the object code of a binary

2. Decompilation makes use of intermediate representations, not assembly language text, to create HLL output

Here is an outline of what is generally involved:

Another example:

Control Flow Graph Recovery The first stage parses the input binary’s file format, disassembles the binary, and creates a control flow graph (CFG) for each function. At a high level, a control flow graph is a program representation in which vertices represent basic blocks, and edges represent possible control flow transitions between blocks.(See §2.1 for more detail.) While precisely identifying binary code in an executable is known to be hard in the general case, current algorithms have been shown to work well in practice [4, 5, 24, 25]. There are mature platforms that already implement this step. We use the CMU Binary Analysis Platform (BAP) [10]. BAP lifts sequential x86 assembly instructions in the CFG into an intermediate language called BIL, whose syntax is shown in Table 1 (see [10]). As we will see, the end goal of Phoenix is to decompile this language into the high-level language shown in Table 2.²

The order of steps taken by CMU's Phoenix decompiler is slightly different from the order depicted in the diagram from Cristina Cifuentes' "Reverse Compilation Techniques" (her decompiler was called dcc): Phoenix creates a CFG for the binary, then translates it into an intermediate language rather than the other way around.

Yet another example, from No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantics-Preserving Transformations:

As is evident from the first sentence, the input to DREAM is a binary. Unlike Phoenix, which uses the BAP Intermediate Language as an intermediate representation, DREAM uses its own unspecified form of intermediate representation.

Final example - based on the dated discussion of the Hex-Rays decompiler from the Decompilers and beyond white paper, the general decompilation procedure looks like this:

1. Microcode generation
2. The local optimization
3. Global optimization
4. Local variable allocation
5. Structural analysis
6. Initial pseudocode
7. Pseudocode transformations
8. Type analysis

In a nutshell, the Hex-Rays decompiler converts the object code from a binary to microcode, creates a CFG, uses the CFG to create psuedocode (some unspecified, probably proprietary, intermediate representation) and then outputs the transformed psuedocode.

Some clear patterns emerge when these different decompilers are examined.

There are several good reasons that both compilers and decompilers use intermediate representation as part of the translation process. The main reason is that an IR can be both language- and architecture-independent while at the same time preserving the information encoded in the source language. This aspect of IR completely eliminates the need for the equivalent of a universal assembly language-to-pseudocode translator. The binary to CFG to IR approach is vastly superior and well established.

Source: Princeton CS320 Intermediate Representation lecture notes

Responses to assorted comments

It appears that what I need is an implementation of the basic DREAM decompilation algorithm; I was unable to find a straightforward implementation that takes a CFG in a text format as input.

No such implementation exists. As discussed previously, DREAM constructs a CFG from parsed object code contained in a binary file.

I already have my own disassembler. Using a tool that takes binary as input would be a waste of effort.

A tool that takes object code as input and produces assembly language ASCII text as output is irrelevant with respect to decompilation. Reinventing the wheel would be a waste of effort. Incidentally, all of the aforementioned decompilers take binary files as input.

My point is that reconstructing control flow structures is virtually independent on the architecture. I could bring the input one step higher: If one has a graph of opaque basic blocks connected by "if (condition) goto" and "goto", it should be possible to restore the original if-then-else statements and loops, and a tool that could do it won't need any disassembler capability

CFGs are generated via object code analysis in order to preserve as much information as possible. More preserved information = more accurate decompilation. Object code format depends directly on the architecture.

---

_{1. Reverse Compilation Techniques}

_{2. Native x86 Decompilation Using Semantics-Preserving Structural Analysis and Iterative Control-Flow Structuring}

Answer 2

IDA Pro is the nearest I am aware of. Whilst it only has decompilers for I think x86 and PPC, it handles many more CPUs and appears to have a limited understanding of control flow as illustrated by viewing a function in graphical mode. Using IDA Python you can parse a function, follow control flow and output a text file easily, but it would only get you to blob trees linked by true/false branches.

Disassembling my own and other microcontroller code leads me to conclude that a good decompiler needs specific information about the compiler and the CPU. Just following something manually can be difficult with structures of pointers, indirect addressing and limited type information.

Answer 3

It's hard to say whether such a tool exists without knowing which CPU architecture you want to target. However, I would recommend radare2 for two reasons:

1. it supports a lot of architectures, even exotic ones
2. it's open source and extensible — in case your CPU isn't supported, you can integrate an existing disassembler implementation or write one by yourself.

However, keep in mind that it will only produce flow control graph. Some data flow analysis may be available if the disassembler implements it.

Answer 4

I'm going to represent my abstract assembly code as a C program with basic blocks as externally defined procedures, variables in conditions as externally defined functions, etc. compile it to an optimized x86 binary, then pass it through an existing x86 decompiler.

Using an example from the question:

extern void blob1(), blob2(), blob3(), blob4(), blob5(), blob6();
extern int A(), B(), C(), D(), E(), F();
main() {
    blob1();
    if (A() < B()) goto L1;
    blob2();
    if (C() == D()) goto L2;
L1: blob3();
    if (E() > F()) goto L3;
L2: blob4();
    goto L4;
L3: blob5();
L4: blob6();
}

A decompiler produces:

_blob1();
int32_t v2 = _A();
int32_t v3;
if (v2 < _B()) {
    _blob3();
    v3 = _E();
    if (v3 > _F()) {
        _blob5();
        _blob6();
        return 0;
    }
    _blob4();
    _blob6();
    return 0;
}
_blob2();
int32_t v4 = _C();
if (v4 != _D()) {
    _blob3();
    v3 = _E();
    if (v3 > _F()) {
        _blob5();
        _blob6();
        return 0;
    }
}
_blob4();
_blob6();

That's not perfect, but it will do.