Skip to main content
Be Bitwise

Control Flow Recovery

How Decompilers Work · Reverse Engineering track

6 min read

In this module

Reconstructing Structure from Flat Code

Machine code is flat — instructions, jumps, branches, nothing else. No if statements. No while loops. The decompiler has to infer the original control flow from branch patterns alone.

The Control Flow Graph

The first step is building a Control Flow Graph (CFG). The code is divided into basic blocks - maximal sequences of instructions with no branches in the middle. A basic block has one entry point (the first instruction) and one exit point (a branch, jump, or return at the end).

text
Machine code:
0x1000: CMP EAX, 5
0x1003: JLE 0x1010
0x1005: MOV EBX, 1 \
0x1008: ADD ECX, EBX | Block B (if-true)
0x100A: JMP 0x1015 /
0x1010: MOV EBX, 0 \
0x1013: SUB ECX, 1 | Block C (if-false)
0x1015: ... / Block D (merge point)

The CFG connects blocks with edges representing possible execution paths. Block A branches to B (if EAX > 5) or C (if EAX <= 5). Both B and C flow into D.

Key Concept

A Control Flow Graph represents the program as a directed graph of basic blocks connected by branch edges. Decompilers analyse the CFG's structure to recover high-level constructs: diamond shapes become if/else, back-edges become loops, and multi-way branches become switch statements.

Recognizing If/Else

An if/else pattern in the CFG looks like a diamond: one block branches into two paths that merge back together.

text
[A: condition]
/ \
[B: if-true] [C: if-false]
\ /
[D: merge]

The decompiler emits:

text
if (condition) {
// B
} else {
// C
}
// D

If the else branch is empty (one path goes directly to the merge point), it becomes a simple if without else.

Recognizing Loops

Loops create back-edges in the CFG - edges that jump backward to an earlier block. The decompiler identifies the loop header (the target of the back-edge) and the loop body (all blocks between the header and the back-edge).

text
[A: loop header, condition check]
| \
[B: loop body] [C: exit]
|
+---> back to A

This becomes:

text
while (condition) {
// B
}
// C

Distinguishing while, do-while, and for loops depends on where the condition check occurs (at the top or bottom of the loop) and whether there is an obvious counter variable.

Switch Statements and Jump Tables

Compilers often optimise switch statements into jump tables - an array of code addresses indexed by the switch variable. The decompiler must recognise the pattern:

asm
MOV EAX, [variable]
CMP EAX, max_case
JA default_case ; unsigned check also catches negatives
JMP [jump_table + RAX * 8] ; computed jump through 8-byte addresses

That's the simplest x86-64 form. Position-independent code more often stores 4-byte offsets relative to the table (MOVSXD RAX, [table + RAX*4], ADD RAX, table, JMP RAX), which the decompiler has to recognise as well.

Recovering the jump table entries and mapping them back to case labels is one of the harder challenges in decompilation, especially when the compiler applies additional optimisations like binary decision trees for sparse switch values.

The Structuring Problem

Not all CFGs correspond cleanly to structured code. Compiler optimisations can create irreducible control flow - patterns that cannot be expressed with nested if/else and while loops. Formally, a loop is irreducible when it can be entered at more than one block, so no single block is its header. goto into the middle of a loop is the classic source.

The textbook case is a loop you can enter in two places. In the graph below, A can jump straight to B or straight to C, and B and C loop through each other:

Try writing that as a while. Whichever block you make the loop header, the other is a second way into the loop body, and the C language has no structured way to say "start halfway through". A structurer that gets here either copies one of the blocks or emits goto to the middle of the loop.

When the decompiler encounters irreducible flow, it must either:

  • Insert goto statements (accurate but ugly)
  • Restructure the code by duplicating blocks (cleaner but changes the structure)
  • Mark the region as unstructured and present it as-is

Ghidra and IDA handle this differently, and neither produces perfect results in all cases.

Function Boundary Detection

Before analysing control flow within a function, the decompiler must identify where each function starts and ends. This involves:

  • Looking for known function prologues (push ebp; mov ebp, esp on x86)
  • Analysing CALL instruction targets
  • Using symbol table information if available
  • Heuristic analysis of code patterns

Inlined functions (where the compiler copies the function body into the caller) do not have clear boundaries and are particularly difficult to identify.

The Fundamental Limitation

Decompiled control flow is an educated guess. The CFG doesn't preserve intent — a for loop and an equivalent while loop produce identical machine code, and the decompiler cannot know which one the programmer wrote. Multiple source-level constructs collapse into the same binary, so perfect reconstruction is impossible by design.

Modern decompilers still produce impressively readable output for well-structured code. Treat it as a starting point, not ground truth. Cross-reference against the raw assembly when something looks off. Build intuition for what decompilers handle well and what trips them up. With enough exposure, you'll read decompiler output fluently — knowing what it's telling you and when to second-guess it.