Decompiler

Last updated

A decompiler is a computer program that takes an executable file as input, and attempts to create a high level source file which can be recompiled successfully. It is therefore the opposite of a compiler, which takes a source file and makes an executable. Decompilers are usually unable to perfectly reconstruct the original source code, and as such, will frequently produce obfuscated code. Nonetheless, decompilers remain an important tool in the reverse engineering of computer software.

Contents

Introduction

The term decompiler is most commonly applied to a program which translates executable programs (the output from a compiler) into source code in a (relatively) high level language which, when compiled, will produce an executable whose behavior is the same as the original executable program. By comparison, a disassembler translates an executable program into assembly language (and an assembler could be used to assemble it back into an executable program).

Decompilation is the act of using a decompiler, although the term can also refer to the output of a decompiler. It can be used for the recovery of lost source code, and is also useful in some cases for computer security, interoperability and error correction. [1] The success of decompilation depends on the amount of information present in the code being decompiled and the sophistication of the analysis performed on it. The bytecode formats used by many virtual machines (such as the Java Virtual Machine or the .NET Framework Common Language Runtime) often include extensive metadata and high-level features that make decompilation quite feasible. The presence of debug data can make it possible to reproduce the original variable and structure names and even the line numbers. Machine language without such metadata or debug data is much harder to decompile. [2]

Some compilers and post-compilation tools produce obfuscated code (that is, they attempt to produce output that is very difficult to decompile). This is done to make it more difficult to reverse engineer the executable.

While decompilers are normally used to (re-)create source code from binary executables, there are also decompilers to turn specific binary data files into human-readable and editable sources. [3] [4]

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 will provide library interfaces. If it can determine the compiler or compilers used it may provide useful information in identifying code idioms. [5]

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

moveax,[ebx+0x04]

might be translated to the IR

eax:=m[ebx+4];

Idioms

Idiomatic machine code sequences are sequences of code whose combined semantics is 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:

cdqeax; edx is set to the sign-extension≠edi,edi +(tex)pushxoreax,edxsubeax,edx

could be translated to

eax  := abs(eax);

Some idiomatic sequences are machine independent; some involve only one instruction. For example, xoreax,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 the 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,

moveax,[ebx+0x04]addeax,[ebx+0x08]sub[ebx+0x0C],eax

could result in the following IR after expression propagation:

m[ebx+12]  := m[ebx+12] - (m[ebx+4] + m[ebx+8]);

The resulting expression is more like high level language, and has also eliminated the use of the machine register eax. Later analyses may eliminate the ebx register.

Data flow analysis

The places where register contents are defined and used must be traced using data flow analysis. The same analysis can be applied to locations that are used for temporaries and local data. A different name can then be formed for each such connected set of value definitions and uses. It is possible that the same local variable location was used for more than one variable in different parts of the original program. Even worse it is possible for the data flow analysis to identify a path whereby a value may flow between two such uses even though it would never actually happen or matter in reality. This may in bad cases lead to needing to define a location as a union of types. The decompiler may allow the user to explicitly break such unnatural dependencies which will lead to clearer code. This of course means a variable is potentially used without being initialized and so indicates a problem in the original program.

Type analysis

A good machine code decompiler will perform type analysis. Here, the way registers or memory locations are used result in constraints on the possible type of the location. For example, an and instruction implies that the operand is an integer; programs do not use such an operation on floating point values (except in special library code) or on pointers. An add instruction results in three constraints, since the operands may be both integer, or one integer and one pointer (with integer and pointer results respectively; the third constraint comes from the ordering of the two operands when the types are different). [6]

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:

structT1*ebx;structT1{intv0004;intv0008;intv000C;};ebx->v000C-=ebx->v0004+ebx->v0008;

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

xoreax,eaxl0002:orebx,ebxjgel0003addeax,[ebx]movebx,[ebx+0x4]jmpl0002l0003:mov[0x10040000],eax

could be translated into:

eax=0;while(ebx<0){eax+=ebx->v0000;ebx=ebx->v0004;}v10040000=eax;

Unstructured code is more difficult to translate into structured code than already structured code. Solutions include replicating some code, or adding boolean variables. [7]

Code generation

The final phase is the generation of the 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 an 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.

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. [8] 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). [9] 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. [10] Additionally, the Digital Millennium Copyright Act (PUBLIC LAW 105–304 [11] ) has proper exemptions for both Security Testing and Evaluation in §1205(i), and Reverse Engineering in §1205(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:

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: 1) the decompilation right is not used frequently and the decompilation right may therefore have been unnecessary, 2) the decompilation right functions well and provides sufficient legal certainty not to give rise to legal disputes or 3) illegal decompilation goes largely undetected. In a recent report regarding implementation of the Software Directive by the European member states, the European Commission seems to support the second interpretation. [13]

Tools

Decompilers usually target a specific binary format. Some are native instruction sets (eg Intel x86, ARM, MIPS), others are bytecode for virtual machines (Dalvik, Java class files, WebAssembly, Ethereum).

Due to information loss during compilation, decompilation is almost never perfect, and not all decompilers perform equally well for a given binary format. There are studies comparing the performance of different decompilers. [14]

See also

Related Research Articles

Assembly language Low level programming language

In computer programming, assembly language, often abbreviated asm, is any low-level programming language in which there is a very strong correspondence between the instructions in the language and the architecture's machine code instructions. Because assembly depends on the machine code instructions, every assembler has its own assembly language which is designed for exactly one specific computer architecture. Assembly language may also be called symbolic machine code.

A compiler is a computer program that translates computer code written in one programming language into another language. The name compiler is primarily used for programs that translate source code from a high-level programming language to a lower level language to create an executable program.

Java virtual machine runtime environment that can execute Java bytecode as a result of compiling computer programs written in the Java programming language

A Java virtual machine (JVM) is a virtual machine that enables a computer to run Java programs as well as programs written in other languages that are also compiled to Java bytecode. The JVM is detailed by a specification that formally describes what is required in a JVM implementation. Having a specification ensures interoperability of Java programs across different implementations so that program authors using the Java Development Kit (JDK) need not worry about idiosyncrasies of the underlying hardware platform.

Machine code Set of instructions executed directly by a computers central processing unit (CPU)

Machine code is a computer program written in machine language instructions that can be executed directly by a computer's central processing unit (CPU). Each instruction causes the CPU to perform a very specific task, such as a load, a store, a jump, or an arithmetic logic unit (ALU) operation on one or more units of data in the CPU's registers or memory.

In computing, source code is any collection of code, possibly with comments, written using a human-readable programming language, usually as plain text. The source code of a program is specially designed to facilitate the work of computer programmers, who specify the actions to be performed by a computer mostly by writing source code. The source code is often transformed by an assembler or compiler into binary machine code that can be executed by the computer. The machine code might then be stored for execution at a later time. Alternatively, source code may be interpreted and thus immediately executed.

Common Intermediate Language (CIL), formerly called Microsoft Intermediate Language (MSIL) or Intermediate Language (IL), is the intermediate language binary instruction set defined within the Common Language Infrastructure (CLI) specification. CIL instructions are executed by a CLI-compatible runtime environment such as the Common Language Runtime. Languages which target the CLI compile to CIL. CIL is object-oriented, stack-based bytecode. Runtimes typically just-in-time compile CIL instructions into native code.

In computer science, an interpreter is a computer program that directly executes instructions written in a programming or scripting language, without requiring them previously to have been compiled into a machine language program. An interpreter generally uses one of the following strategies for program execution:

  1. Parse the source code and perform its behavior directly;
  2. Translate source code into some efficient intermediate representation and immediately execute this;
  3. Explicitly execute stored precompiled code made by a compiler which is part of the interpreter system.

Bytecode, also termed portable code or p-code, is a form of instruction set designed for efficient execution by a software interpreter. Unlike human-readable source code, bytecodes are compact numeric codes, constants, and references that encode the result of compiler parsing and performing semantic analysis of things like type, scope, and nesting depths of program objects.

In computer science, a high-level programming language is a programming language with strong abstraction from the details of the computer. In contrast to low-level programming languages, it may use natural language elements, be easier to use, or may automate significant areas of computing systems, making the process of developing a program simpler and more understandable than when using a lower-level language. The amount of abstraction provided defines how "high-level" a programming language is.

A low-level programming language is a programming language that provides little or no abstraction from a computer's instruction set architecture—commands or functions in the language map closely to processor instructions. Generally, this refers to either machine code or assembly language. Because of the low abstraction between the language and machine language, low-level languages are sometimes described as being "close to the hardware". Programs written in low-level languages tend to be relatively non-portable, due to optimized for a certain type of system architecture.

Executable file that can be directly run by a computer

In computing, executable code, executable file, or executable program, sometimes simply referred to as an executable, causes a computer "to perform indicated tasks according to encoded instructions", as opposed to a data file that must be parsed by a program to be meaningful.

In computing, just-in-time (JIT) compilation is a way of executing computer code that involves compilation during execution of a program – at run time – rather than before execution. Most often, this consists of source code or more commonly bytecode translation to machine code, which is then executed directly. A system implementing a JIT compiler typically continuously analyses the code being executed and identifies parts of the code where the speedup gained from compilation or recompilation would outweigh the overhead of compiling that code.

The GNU Assembler, commonly known as gas or simply as, its executable name, is the assembler used by the GNU Project. It is the default back-end of GCC. It is used to assemble the GNU operating system and the Linux kernel, and various other software. It is a part of the GNU Binutils package.

An intermediate representation (IR) is the data structure or code used internally by a compiler or virtual machine to represent source code. An IR is designed to be conducive for further processing, such as optimization and translation. A "good" IR must be accurate – capable of representing the source code without loss of information – and independent of any particular source or target language. An IR may take one of several forms: an in-memory data structure, or a special tuple- or stack-based code readable by the program. In the latter case it is also called an intermediate language.

Dalvik is a discontinued process virtual machine (VM) in Google's Android operating system that executes applications written for Android. Dalvik was an integral part of the Android software stack in the Android versions 4.4 "KitKat" and earlier, which were commonly used on mobile devices such as mobile phones and tablet computers, and more in some devices such as smart TVs and wearables. Dalvik is open-source software, originally written by Dan Bornstein, who named it after the fishing village of Dalvík in Eyjafjörður, Iceland.

Cosmos (operating system) open source operating system building kit

C# Open Source Managed Operating System (Cosmos) is a toolkit for building operating systems, written mostly in the programming language C# and small amounts of a high level assembly language named X#. Cosmos is a backronym, in that the acronym was chosen before the meaning. It is open-source software released under a BSD license.

Java bytecode is the instruction set of the Java virtual machine (JVM).

JD Decompiler Decompiler for the Java programming language

JD is a decompiler for the Java programming language. JD is provided as a GUI tool as well as in the form of plug-ins for the Eclipse (JD-Eclipse) and IntelliJ IDEA (JD-IntelliJ) integrated development environments.

JEB decompiler software reverse engineering software

JEB is a disassembler and decompiler software for Android applications and native machine code. It decompiles Dalvik bytecode to Java source code, and MIPS, ARM, x86 32-bit, x86 64-bit machine code to C source code. The assembly and source outputs are interactive and can be refactored. Users can also write their own scripts and plugins to extend JEB functionality.

WebAssembly binary format for executables used by web pages

WebAssembly is an open standard that defines a portable binary-code format for executable programs, and a corresponding textual assembly language, as well as interfaces for facilitating interactions between such programs and their host environment. The main goal of WebAssembly is to enable high-performance applications on web pages, but the format is designed to be executed and integrated in other environments as well.

References

  1. Van Emmerik, Mike (2005-04-29). "Why Decompilation". Program-transformation.org. Retrieved 2010-09-15.
  2. Miecznikowski, Jerome; Hendren, Laurie (2002). "Decompiling Java Bytecode: Problems, Traps and Pitfalls". In Horspool, R. Nigel (ed.). Compiler Construction: 11th International Conference, proceedings / CC 2002. Springer-Verlag. pp. 111–127. ISBN   3-540-43369-4.
  3. Paul, Matthias R. (2001-06-10) [1995]. "Format description of DOS, OS/2, and Windows NT .CPI, and Linux .CP files" (CPI.LST file) (1.30 ed.). Archived from the original on 2016-04-20. Retrieved 2016-08-20.
  4. Paul, Matthias R. (2002-05-13). "[fd-dev] mkeyb". freedos-dev. Archived from the original on 2018-09-10. Retrieved 2018-09-10. […] .CPI & .CP codepage file analyzer, validator and decompiler […] Overview on /Style parameters: […] ASM source include files […] Standalone ASM source files […] Modular ASM source files […]
  5. Cifuentes, Cristina; Gough, K. John (July 1995). "Decompilation of Binary Programs". Software Practice and Experience. 25 (7): 811–829. CiteSeerX   10.1.1.14.8073 . doi:10.1002/spe.4380250706.
  6. Mycroft, Alan (1999). "Type-Based Decompilation". In Swierstra, S. Doaitse (ed.). Programming languages and systems: 8th European Symposium on Programming Languages and Systems. Springer-Verlag. pp. 208–223. ISBN   3-540-65699-5.
  7. Cifuentes, Cristina (1994). "Chapter 6". Reverse Compilation Techniques (PDF) (PhD thesis). Queensland University of Technology. Archived (PDF) from the original on 2016-11-22. Retrieved 2019-12-21.)
  8. Rowland, Diane (2005). Information technology law (3 ed.). Cavendish. ISBN   1-85941-756-6.
  9. "U.S. Copyright Office - Copyright Law: Chapter 1".
  10. "The Legality of Decompilation". Program-transformation.org. 2004-12-03. Retrieved 2010-09-15.
  11. "Digital Millennium Copyright Act" (PDF). US Congress. 1998-10-28. Retrieved 2013-11-15.
  12. Czarnota, Bridget; Hart, Robert J. (1991). Legal protection of computer programs in Europe: a guide to the EC directive. London: Butterworths Tolley. ISBN   0-40600542-7.
  13. "EUR-Lex - 52000DC0199 - EN".
  14. Harrand, Nicolas; Soto-Valero, Cesar; Monperrus, Martin; Baudry, Benoit (2019). "The Strengths and Behavioral Quirks of Java Bytecode Decompilers". 19th International Working Conference on Source Code Analysis and Manipulation (SCAM). IEEE: 92–102. arXiv: 1908.06895 . Bibcode:2019arXiv190806895H. doi:10.1109/SCAM.2019.00019. ISBN   978-1-7281-4937-0.