decompiler

How it is built

Architecture overview

A decompiler reads a compiled program (machine code in an executable file) and reconstructs a readable, C-like approximation of the source: functions, local variables with types, if, while and switch structure, and named calls. The compiler threw away names, types, comments and the original control structure; the decompiler has to infer them from what remains. The result is never the original source, but it is far easier to read than a disassembly listing, and it is good enough to understand what a function does, which is why decompilers are standard tools in malware analysis, vulnerability research, interoperability work (understanding an undocumented file format or protocol implemented by a closed library), recovery of lost sources, and checking that a compiler produced what it should have.

The design follows the compiler in reverse. A loader reads the executable container and finds code and data. A disassembler decodes instructions and a function and control-flow recoverer groups them into functions and basic blocks. A lifter translates each machine instruction into a small, uniform intermediate language with explicit side effects, so that one analysis serves every CPU architecture. A stack of analyses on that IR removes machine detail (flags, stack-pointer arithmetic, register shuffling) and recovers variables and types. A structurer turns the control-flow graph back into loops and conditionals. A printer writes C-like text. Ghidra, IDA with its Hex-Rays decompiler and Binary Ninja are the best-known assemblies; Ghidra's source is open.

This page describes reverse engineering for analysis, interoperability and security research.

Parts:

• Loader — reads the container and maps sections to addresses — executable-formats-elf-pe (no page yet)
• Disassembler — decodes bytes into instructions — disassembly (no page yet)
• Function and CFG recovery — finds functions, basic blocks, jump tables — cfg-recovery (no page yet), built on Control-flow graph and dominator-tree (no page yet)
• Lifter — translates instructions into a semantic IR — binary-lifting-to-ir (no page yet), built on SSA form
• Data-flow simplifier — removes machine artefacts and propagates constants — Dataflow analysis, sparse-conditional-constant-propagation (no page yet), alias-analysis (no page yet), built on Union-find
• Type and calling-convention recovery — infers variable types, struct layouts and function signatures — type-recovery (no page yet), unification (no page yet), calling-conventions-abi (no page yet)
• Control-flow structurer — turns jumps into loops and conditionals — Structured control flow, built on strongly-connected-components (no page yet)
• Library recognition — names known library functions by signature — function-fingerprinting (no page yet), built on Fast hash functions and radix-trie (no page yet)
• Path and constraint reasoning — explores feasible paths and solves constraints — symbolic-execution (no page yet), dpll-t (no page yet), built on bit-blasting (no page yet), cdcl-sat-solving and congruence-closure (no page yet)

 executable file (ELF / PE / Mach-O)
        │ loader: sections, entry points, imports, symbols
        ▼
  disassembler (linear sweep + recursive descent) ──► instructions
        │
        ▼ function and CFG recovery (jump tables, tail calls)
  basic blocks + call graph
        │
        ▼ lifter
  semantic IR (explicit flags and memory effects)
        │
        ▼ SSA construction (dominators) ► constant propagation, dead code,
        │   stack/ABI recovery, alias analysis, type inference
        ▼
  clean IR with typed variables
        │ structurer: dominators, loops, if / else, switch
        ▼
  C-like source text   ◄── library signatures name known functions
        ▲
  analyst: renames, retypes, annotates ──► re-runs analyses

The loop in the last row is part of the design. The analyst is a component: types, names and function prototypes the user supplies feed back into the analyses and change the output, because decompilation is an interactive refinement, not a one-shot translation.

How the parts fit together

Loader

The loader (executable-formats-elf-pe, no page yet) parses the container: ELF on Linux, PE on Windows, Mach-O on macOS and iOS. It decides which bytes are code and which are data, at what virtual address each section sits, where execution starts, which functions are imported from shared libraries (the import table) and exported, and which symbols survive in the file. Relocations tell the loader which words are addresses, which later helps separate pointers from integers. Stripped binaries lose symbol names; debug information, if present (Debug info (DWARF)), is the best possible help, giving real names, types and line mappings.

Disassembler

Decoding machine code is a table-driven problem with real difficulties (disassembly, no page yet). On x86 instructions have variable length and prefixes, so decoding from the wrong byte gives different, valid-looking instructions; ARM has fixed-length modes but mixes instruction sets (ARM and Thumb) in one file. Two strategies exist. Linear sweep decodes from the start of a code section straight through; it covers everything but desynchronises when data sits among code. Recursive descent starts from known entry points and follows control flow, decoding only reachable code; it avoids data but misses code reached only through computed jumps. Real tools use recursive descent and add heuristics for the gaps. In Ghidra the decoder is generated from a processor description language (SLEIGH), so adding an architecture means writing a specification rather than code.

Function and CFG recovery

Next the tool groups instructions into basic blocks and functions (cfg-recovery, no page yet). Function entries come from the entry point, exported symbols, call targets and known prologue patterns; function ends are not marked in the binary, so a function is "everything reachable from its entry without crossing a call". Hard cases are what make the stage a research topic: jump tables (an indirect jump through a table of addresses, produced by switch), whose size must be inferred from a bounds check; tail calls (a jump to another function's entry, indistinguishable from a branch without analysis); non-returning functions (calls to exit after which no code follows); and code that overlaps or is generated at runtime. The result is a control-flow graph per function and a call graph. Dominators (dominator-tree, no page yet; the fast iterative algorithm of Cooper, Harvey and Kennedy is the usual choice) are computed here because both SSA construction and structuring need them.

Lifter

Machine instructions have complicated, architecture-specific effects: an add also sets flags, a push changes the stack pointer, a rep movs loops. The lifter (binary-lifting-to-ir, no page yet) rewrites each instruction as a few primitive operations in a small IR with explicit inputs and outputs. Ghidra calls this IR p-code; the Remill library lifts to LLVM IR (lifting-bits/remill). Making flag and memory effects explicit costs volume, since one instruction can become many operations, but it gives every later stage one language to work with, and a new CPU needs only a new lifter.

Registers and stack slots are then rewritten into SSA form, where every value has one definition and merges at joins are explicit. SSA makes def-use chains immediate: "who computed this value" is a pointer, not a search.

Data-flow simplifier

Directly lifted code is full of noise: flags computed and never read, values moved through registers and the stack, stack-pointer additions that cancel out. Passes over the SSA IR remove it. Dataflow analysis computes reaching definitions and liveness, so dead flag computations are deleted. Sparse conditional constant propagation (sparse-conditional-constant-propagation, no page yet) evaluates constants and discards branches that can never be taken, which also unwraps simple obfuscations. Alias analysis (alias-analysis, no page yet) decides whether a store through a pointer can affect a load from another; without it every store must be assumed to clobber everything, and local variables on the stack cannot be promoted to SSA values. Points-to analyses based on union-find (the Steensgaard style) are cheap and nearly linear, which suits an interactive tool; more precise analyses cost more.

Stack analysis belongs here too: tracking the stack-pointer offset at every instruction lets each [sp+8] access become a named local variable or parameter, and the prologue and epilogue disappear from the output.

Type and calling-convention recovery

Machine code has bits and addresses, no types. Type recovery (type-recovery, no page yet) infers them from how values are used: a value passed as the first argument to strlen is a character pointer; a value added to a constant and dereferenced points to a structure with a field at that offset; a value compared with a floating-point instruction is a float. Each use generates a constraint, and constraints are solved by unification (unification, no page yet), possibly with subtyping. The published work of Noonan et al. on Polymorphic Type Inference for Machine Code (arXiv:1603.05495) describes a constraint-based system of this kind, and the Hex-Rays, Ghidra and Binary Ninja decompilers all contain some form of type propagation.

Function signatures come from the platform's calling convention (calling-conventions-abi, no page yet): which registers carry arguments, which return the result, which are preserved across calls. Matching the observed register uses to the convention recovers the parameter count and the return value. Prototypes known from imported library functions or header files give types for free and propagate through the call graph. Where the inference is ambiguous, the analyst supplies the answer and the analyses are rerun.

Control-flow structurer

The cleaned IR is still a graph with jumps. The structurer (Structured control flow) identifies loops using strongly connected components, then matches regions of the graph to if/else, while, do/while, break, continue and switch. Dominators and post-dominators find where a conditional's branches rejoin. Compilers produce code shapes the structurer must undo: loop rotation, shared tails after inlining, short-circuit conditions compiled into a chain of jumps. When no structured form fits, the tool falls back to goto, which is correct but harder to read. Research systems differ chiefly in how aggressively they avoid goto: Schwartz et al.'s Native x86 Decompilation using Semantics-Preserving Structural Analysis and Iterative Control-Flow Structuring (USENIX Security 2013) targets exactly this, with the aim that the output is correct before it is pretty.

Library recognition

Much of any binary is statically linked library code: runtime start-up, memcpy, printf, compression libraries. Analysing it is wasted effort, and naming it makes the rest readable. Function fingerprinting (function-fingerprinting, no page yet) compares code against a database of known functions. Byte-level signatures with wildcards for relocated addresses (IDA's FLIRT, see the Hex-Rays documentation) match quickly; structural fingerprints that hash the control-flow shape or the sequence of IR operations survive recompilation with different flags better. A fast hash of the normalised bytes turns a lookup into a table probe, and a prefix tree (radix-trie, no page yet) handles signatures that share a prefix. Matching a function also supplies its prototype, which feeds type recovery.

Path and constraint reasoning

Static analysis answers "what could happen"; sometimes the question is "which input reaches this branch". Symbolic execution (symbolic-execution, no page yet) runs the program on symbolic inputs, collecting a path condition at each branch and asking a solver whether it is satisfiable. Binary-level engines such as angr are built this way, and KLEE is the classic source-level system. The solver is an SMT solver (dpll-t, no page yet): a SAT core with conflict-driven learning (CDCL SAT solving) combined with theory solvers; machine arithmetic is reduced to bit-level logic (bit-blasting, no page yet), and equality over function symbols is handled by congruence closure (congruence-closure, no page yet). Typical uses inside a decompiler or its neighbours: proving that a branch is an opaque predicate that never goes one way, finding the input that triggers a code path for analysis, and checking that a simplification preserved behaviour. Z3 is the common solver. Path explosion limits the technique to focused questions, not whole programs.

Data and control flow

Decompiling one function:

1. The loader has mapped the file; the analyst selects an address.
2. The disassembler and CFG recovery produce basic blocks for the function, following jumps and resolving jump tables.
3. The lifter converts each instruction to IR; the result is put in SSA form.
4. Simplification passes run to a fixed point: dead code, constants, stack variables, propagated types.
5. Calling-convention analysis fixes parameters and the return value; callees' prototypes are used if known.
6. The structurer builds the loop and conditional tree; variable names and types are assigned.
7. The printer outputs C-like text, with each line mapped back to addresses so clicking a line shows the instructions.

Whole-binary analysis: the tool first finds all functions and runs signature matching and prototype propagation over the call graph, from leaves to roots, because a callee's signature improves its callers. Analysis runs in the background; results are cached in a project database and invalidated when the analyst edits a type or a prototype.

Scaling

1. Binary size. Large programs have hundreds of thousands of functions. Levers: analyse lazily (decompile only on demand), run the cheap passes first, cache per function, parallelise across functions.
2. Analysis precision versus time. Precise alias analysis and type inference are super-linear. Levers: near-linear algorithms such as union-find-based points-to, limiting inter-procedural analysis depth, letting the user raise precision on one function.
3. Obfuscation and packing. Packed code exists only at runtime. Levers: emulation or dynamic unpacking before analysis; symbolic execution for opaque predicates; manual guidance.
4. Architecture coverage. A new CPU needs a decoder and lifter. Levers: specification languages (SLEIGH) instead of hand-written code, lifting to a shared IR so analyses are reused.
5. Team use. Several analysts working on one binary need a shared database of names and types; this is a repository feature of the tools rather than a decompiler algorithm.

Failure modes

Real implementations

Sources

• E. Schwartz, J. Lee, M. Woo, D. Brumley, Native x86 Decompilation Using Semantics-Preserving Structural Analysis and Iterative Control-Flow Structuring, USENIX Security 2013. page
• M. Noonan, A. Loginov, D. Cok, Polymorphic Type Inference for Machine Code, PLDI 2016. arXiv
• C. Cadar, D. Dunbar, D. Engler, KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs, OSDI 2008. paper
• Hex-Rays documentation on FLIRT signatures: docs.hex-rays.com
• Repositories listed above (Ghidra, Remill, Rellic, RetDec, angr, Z3).