Decompiler
Program translating executable to source code
- 10 min read
- 3 chapters
Related on Lably
Through Computer program, Compiler and High-level programming language
Introduction
Decompilation is the process of transforming executable code into a high-level, human-readable format using a decompiler. This process is commonly used for tasks that involve reverse-engineering the logic behind executable code, such as recovering lost or unavailable source code. Decompilers face inherent challenges due to the loss of information during compilation, such as variable names, comments, and aspects of the original source-level structure.
Certain factors can impact the success of decompilation. Executables containing detailed metadata, such as those used by Java and .NET, are easier to reverse-engineer because they often retain class structures, method signatures, and debugging information. Executable files stripped of such context are more challenging to translate into meaningful source code.
Some software developers may obfuscate, pack, or encrypt parts of their executable programs, making the decompiled code harder to interpret. These techniques may be used to deter reverse engineering by making analysis more difficult and time-consuming.
Sign in to keep reading
2 more chapters are free with a Lably account.
Design
Decompilers can be thought of as composed of a series of phases, each of which contributes specific aspects of the overall decompilation process.
Loader
The first decompilation phase loads and parses the input machine code or intermediate language program's binary file format. It should be able to discover basic facts about the input program, such as the architecture (Pentium, PowerPC, etc.) and the entry point. In many cases, it should be able to find the equivalent of the main function of a C program, which is the start of the user written code. This excludes the runtime initialization code, which should not be decompiled if possible. If available, the symbol tables and debug data are also loaded. The front end may be able to identify the libraries used even if they are linked with the code; this can provide library interfaces. If it can determine the compiler or compilers used, this may provide useful information in identifying code idioms.
Disassembly
The next logical phase is the disassembly of machine code instructions into a machine independent intermediate representation (IR). For example, the Pentium machine instruction
<span id="mwPw"></span><span class="nf" id="mwQA">mov</span><span class="w" id="mwQQ"> </span><span class="no" id="mwQg">eax</span><span class="p" id="mwQw">,</span><span class="w" id="mwRA"> </span><span class="p" id="mwRQ">[</span><span class="no" id="mwRg">ebx</span><span class="err" id="mwRw">+</span><span class="mi" id="mwSA">0x04</span><span class="p" id="mwSQ">]</span>
might be translated to the IR
<span id="mwTQ"></span><span class="nf" id="mwTg">eax</span><span class="w" id="mwTw"> </span><span class="p" id="mwUA">:</span><span class="err" id="mwUQ">=</span><span class="w" id="mwUg"> </span><span class="no" id="mwUw">m</span><span class="p" id="mwVA">[</span><span class="no" id="mwVQ">ebx</span><span class="err" id="mwVg">+</span><span class="mi" id="mwVw">4</span><span class="p" id="mwWA">]</span><span class="c1" id="mwWQ">;</span>
Idioms
Idiomatic machine code sequences are sequences of code whose combined semantics are not immediately apparent from the instructions' individual semantics. Either as part of the disassembly phase, or as part of later analyses, these idiomatic sequences need to be translated into known equivalent IR. For example, the x86 assembly code:
<span id="mwYA"></span><span class="w" id="mwYQ"> </span><span class="nf" id="mwYg">cdq</span><span class="w" id="mwYw"> </span><span class="c1" id="mwZA">; sign-extend EAX into EDX:EAX</span> <span class="w" id="mwZQ"> </span><span class="nf" id="mwZg">xor</span><span class="w" id="mwZw"> </span><span class="nb" id="mwaA">eax</span><span class="p" id="mwaQ">,</span><span class="w" id="mwag"> </span><span class="nb" id="mwaw">edx</span> <span class="w" id="mwbA"> </span><span class="nf" id="mwbQ">sub</span><span class="w" id="mwbg"> </span><span class="nb" id="mwbw">eax</span><span class="p" id="mwcA">,</span><span class="w" id="mwcQ"> </span><span class="nb" id="mwcg">edx</span>
computes the absolute value of eax for values other than the most negative representable signed integer, and could be translated into an equivalent higher-level operation such as:
<span id="mwdw"></span>eax := abs(eax);
Some idiomatic sequences are machine independent; some involve only one instruction. For example, xor eax, eax clears the eax register (sets it to zero). This can be implemented with a machine independent simplification rule, such as a = 0.
In general, it is best to delay detection of idiomatic sequences if possible, to later stages that are less affected by instruction ordering. For example, the instruction scheduling phase of a compiler may insert other instructions into an idiomatic sequence, or change the ordering of instructions in the sequence. A pattern matching process in the disassembly phase would probably not recognize the altered pattern. Later phases group instruction expressions into more complex expressions, and modify them into a canonical (standardized) form, making it more likely that even the altered idiom will match a higher level pattern later in the decompilation.
It is particularly important to recognize compiler idioms for subroutine calls, exception handling, and switch statements. Some languages also have extensive support for strings or long integers.
Program analysis
Various program analyses can be applied to the IR. In particular, expression propagation combines the semantics of several instructions into more complex expressions. For example,
<span id="mwjg"></span><span class="w" id="mwjw"> </span><span class="nf" id="mwkA">mov</span><span class="w" id="mwkQ"> </span><span class="no" id="mwkg">eax</span><span class="p" id="mwkw">,[</span><span class="no" id="mwlA">ebx</span><span class="err" id="mwlQ">+</span><span class="mi" id="mwlg">0x04</span><span class="p" id="mwlw">]</span> <span class="w" id="mwmA"> </span><span class="nf" id="mwmQ">add</span><span class="w" id="mwmg"> </span><span class="no" id="mwmw">eax</span><span class="p" id="mwnA">,[</span><span class="no" id="mwnQ">ebx</span><span class="err" id="mwng">+</span><span class="mi" id="mwnw">0x08</span><span class="p" id="mwoA">]</span> <span class="w" id="mwoQ"> </span><span class="nf" id="mwog">sub</span><span class="w" id="mwow"> </span><span class="p" id="mwpA">[</span><span class="no" id="mwpQ">ebx</span><span class="err" id="mwpg">+</span><span class="mi" id="mwpw">0x0C</span><span class="p" id="mwqA">],</span><span class="no" id="mwqQ">eax</span>
could result in the following IR after expression propagation:
<span id="mwrQ"></span>m[ebx+12] := m[ebx+12] - (m[ebx+4] + m[ebx+8]);
The resulting expression more closely resembles a high level language expression and has eliminated the explicit use of the machine register eax. Later analyses may also eliminate the explicit use of ebx.
Data flow analysis
The places where register contents are defined and used can be traced using data flow analysis. The same analysis can be applied to memory locations used for temporary and local data. A different name can then be formed for each connected set of value definitions and uses. The same local storage location may have been reused for more than one source level variable in different parts of the original program. Conversely, an imprecise analysis may infer data-flow relationships between uses that could not occur in an actual execution. These ambiguities can make recovery of source level variables and types more difficult.
Type analysis
A machine code decompiler may perform type analysis. Here, the ways in which registers or memory locations are used impose constraints on their possible types. For example, an and instruction generally suggests an integer-like operand, while arithmetic involving a memory address may indicate a pointer. Type analysis attempts to combine such constraints to recover higher level type information.
Various high level expressions can be recognized which trigger recognition of structures or arrays. However, it is difficult to distinguish many of the possibilities because of the freedom that machine code, or even some high level languages such as C, allow with casts and pointer arithmetic.
The example from the previous section could result in the following high level code:
<span id="mwww"></span><span class="k" id="mwxA">struct</span><span class="w" id="mwxQ"> </span><span class="nc" id="mwxg">T1</span><span class="w" id="mwxw"> </span><span class="p" id="mwyA">{</span> <span class="w" id="mwyQ"> </span><span class="kt" id="mwyg">int</span><span class="w" id="mwyw"> </span><span class="n" id="mwzA">v0004</span><span class="p" id="mwzQ">;</span> <span class="w" id="mwzg"> </span><span class="kt" id="mwzw">int</span><span class="w" id="mw0A"> </span><span class="n" id="mw0Q">v0008</span><span class="p" id="mw0g">;</span> <span class="w" id="mw0w"> </span><span class="kt" id="mw1A">int</span><span class="w" id="mw1Q"> </span><span class="n" id="mw1g">v000C</span><span class="p" id="mw1w">;</span> <span class="p" id="mw2A">};</span> <span class="k" id="mw2Q">struct</span><span class="w" id="mw2g"> </span><span class="nc" id="mw2w">T1</span><span class="w" id="mw3A"> </span><span class="o" id="mw3Q">*</span><span class="n" id="mw3g">ebx</span><span class="p" id="mw3w">;</span> <span class="n" id="mw4A">ebx</span><span class="o" id="mw4Q">-></span><span class="n" id="mw4g">v000C</span><span class="w" id="mw4w"> </span><span class="o" id="mw5A">-=</span><span class="w" id="mw5Q"> </span><span class="n" id="mw5g">ebx</span><span class="o" id="mw5w">-></span><span class="n" id="mw6A">v0004</span><span class="w" id="mw6Q"> </span><span class="o" id="mw6g">+</span><span class="w" id="mw6w"> </span><span class="n" id="mw7A">ebx</span><span class="o" id="mw7Q">-></span><span class="n" id="mw7g">v0008</span><span class="p" id="mw7w">;</span>Structuring
The penultimate decompilation phase involves structuring of the IR into higher level constructs such as while loops and if/then/else conditional statements. For example, the machine code
<span id="mw9g"></span><span class="w" id="mw9w"> </span><span class="nf" id="mw-A">xor</span><span class="w" id="mw-Q"> </span><span class="no" id="mw-g">eax</span><span class="p" id="mw-w">,</span><span class="w" id="mw_A"> </span><span class="no" id="mw_Q">eax</span> <span class="nl" id="mw_g">l0002:</span> <span class="w" id="mw_w"> </span><span class="nf" id="mwAQA">or</span><span class="w" id="mwAQE"> </span><span class="no" id="mwAQI">ebx</span><span class="p" id="mwAQM">,</span><span class="w" id="mwAQQ"> </span><span class="no" id="mwAQU">ebx</span> <span class="w" id="mwAQY"> </span><span class="nf" id="mwAQc">jge</span><span class="w" id="mwAQg"> </span><span class="no" id="mwAQk">l0003</span> <span class="w" id="mwAQo"> </span><span class="nf" id="mwAQs">add</span><span class="w" id="mwAQw"> </span><span class="no" id="mwAQ0">eax</span><span class="p" id="mwAQ4">,[</span><span class="no" id="mwAQ8">ebx</span><span class="p" id="mwARA">]</span> <span class="w" id="mwARE"> </span><span class="nf" id="mwARI">mov</span><span class="w" id="mwARM"> </span><span class="no" id="mwARQ">ebx</span><span class="p" id="mwARU">,[</span><span class="no" id="mwARY">ebx</span><span class="err" id="mwARc">+</span><span class="mi" id="mwARg">0x4</span><span class="p" id="mwARk">]</span> <span class="w" id="mwARo"> </span><span class="nf" id="mwARs">jmp</span><span class="w" id="mwARw"> </span><span class="no" id="mwAR0">l0002</span> <span class="nl" id="mwAR4">l0003:</span> <span class="w" id="mwAR8"> </span><span class="nf" id="mwASA">mov</span><span class="w" id="mwASE"> </span><span class="p" id="mwASI">[</span><span class="mi" id="mwASM">0x10040000</span><span class="p" id="mwASQ">],</span><span class="no" id="mwASU">eax</span>
could be translated into:
<span id="mwASk"></span><span class="n" id="mwASo">eax</span><span class="w" id="mwASs"> </span><span class="o" id="mwASw">=</span><span class="w" id="mwAS0"> </span><span class="mi" id="mwAS4">0</span><span class="p" id="mwAS8">;</span> <span class="k" id="mwATA">while</span><span class="w" id="mwATE"> </span><span class="p" id="mwATI">(</span><span class="n" id="mwATM">ebx</span><span class="w" id="mwATQ"> </span><span class="o" id="mwATU"><</span><span class="w" id="mwATY"> </span><span class="mi" id="mwATc">0</span><span class="p" id="mwATg">)</span><span class="w" id="mwATk"> </span><span class="p" id="mwATo">{</span> <span class="w" id="mwATs"> </span><span class="n" id="mwATw">eax</span><span class="w" id="mwAT0"> </span><span class="o" id="mwAT4">+=</span><span class="w" id="mwAT8"> </span><span class="n" id="mwAUA">ebx</span><span class="o" id="mwAUE">-></span><span class="n" id="mwAUI">v0000</span><span class="p" id="mwAUM">;</span> <span class="w" id="mwAUQ"> </span><span class="n" id="mwAUU">ebx</span><span class="w" id="mwAUY"> </span><span class="o" id="mwAUc">=</span><span class="w" id="mwAUg"> </span><span class="n" id="mwAUk">ebx</span><span class="o" id="mwAUo">-></span><span class="n" id="mwAUs">v0004</span><span class="p" id="mwAUw">;</span> <span class="p" id="mwAU0">}</span> <span class="n" id="mwAU4">v10040000</span><span class="w" id="mwAU8"> </span><span class="o" id="mwAVA">=</span><span class="w" id="mwAVE"> </span><span class="n" id="mwAVI">eax</span><span class="p" id="mwAVM">;</span>Unstructured code is more difficult to translate into structured code than already structured code. Solutions include replicating some code or adding Boolean variables.
Code generation
The final phase is the generation of high level code in the back end of the decompiler. Just as a compiler may have several back ends for generating machine code for different architectures, a decompiler may have several back ends for generating high level code in different high level languages.
Just before code generation, it may be desirable to allow interactive editing of the IR, perhaps using some form of graphical user interface. This would allow the user to enter comments and non-generic variable and function names. However, these are almost as easily entered in a post decompilation edit. The user may want to change structural aspects, such as converting a while loop to a for loop. These are less readily modified with a simple text editor, although source code refactoring tools may assist with this process. The user may need to enter information that failed to be identified during the type analysis phase, e.g. modifying a memory expression to an array or structure expression. Finally, incorrect IR may need to be corrected, or changes made to cause the output code to be more readable.
Other techniques
Decompilers using neural networks have been developed. Such a decompiler may be trained by machine learning to improve its accuracy over time.
Legality
The majority of computer programs are covered by copyright laws. Although the precise scope of what is covered by copyright differs from region to region, copyright law generally provides the author (the programmer(s) or employer) with a collection of exclusive rights to the program. These rights include the right to make copies, including copies made into the computer’s RAM (unless creating such a copy is essential for using the program). Since the decompilation process involves making multiple such copies, it is generally prohibited without the authorization of the copyright holder. However, because decompilation is often a necessary step in achieving software interoperability, copyright laws in both the United States and Europe permit decompilation to a limited extent.
In the United States, the copyright fair use defence has been successfully invoked in decompilation cases. For example, in Sega v. Accolade, the court held that Accolade could lawfully engage in decompilation in order to circumvent the software locking mechanism used by Sega's game consoles. Additionally, the Digital Millennium Copyright Act (PUBLIC LAW 105–304) has proper exemptions for both Security Testing and Evaluation in §1201(i), and Reverse Engineering in §1201(f).
In Europe, the 1991 Software Directive explicitly provides for a right to decompile in order to achieve interoperability. The result of a heated debate between, on the one side, software protectionists, and, on the other, academics as well as independent software developers, Article 6 permits decompilation only if a number of conditions are met:
- First, a person or entity must have a license to use the program to be decompiled.
- Second, decompilation must be necessary to achieve interoperability with the target program or other programs. Interoperability information should therefore not be readily available, such as through manuals or API documentation. This is an important limitation. The necessity must be proven by the decompiler. The purpose of this important limitation is primarily to provide an incentive for developers to document and disclose their products' interoperability information.
- Third, the decompilation process must, if possible, be confined to the parts of the target program relevant to interoperability. Since one of the purposes of decompilation is to gain an understanding of the program structure, this third limitation may be difficult to meet. Again, the burden of proof is on the decompiler.
In addition, Article 6 prescribes that the information obtained through decompilation may not be used for other purposes and that it may not be given to others.
Overall, the decompilation right provided by Article 6 codifies what is claimed to be common practice in the software industry. Few European lawsuits are known to have emerged from the decompilation right. This could be interpreted as meaning one of three things:
- the decompilation right is not used frequently and the decompilation right may therefore have been unnecessary,
- the decompilation right functions well and provides sufficient legal certainty not to give rise to legal disputes or
- illegal decompilation goes largely undetected.
In a report of 2000 regarding implementation of the Software Directive by the European member states, the European Commission seemed to support the second interpretation.