- 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:
- Any given assembly language is necessarily strongly related to the machine language of the target processor
- 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
- Pseudocode by definition does not conform to a language specification. This precludes lexical analysis, which is an essential step in text to text transformation
- 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.
- 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
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.1
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.2
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:
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) . BAP lifts sequential x86 assembly instructions in the CFG into an intermediate language called BIL, whose syntax is shown in Table 1 (see ). As we will see, the end goal of Phoenix is to decompile this language into the high-level language shown in Table 2.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:
- Microcode generation
- The local optimization
- Global optimization
- Local variable allocation
- Structural analysis
- Initial pseudocode
- Pseudocode transformations
- 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