Functions and Control-Flow Graphs

In Linear vs Recursive Disassembly you recovered a list of instructions. A list is the wrong shape for understanding code. Programs branch, loop and dispatch, and a flat listing hides all of that behind addresses you have to match up by eye.

Every serious disassembler therefore groups instructions into basic blocks, connects them into a control-flow graph (CFG), and groups graphs into functions connected by a call graph. Those structures are what you actually navigate in IDA, Ghidra, Binary Ninja or Cutter. This lesson explains how they are built, how to read the common shapes, and why the shape of a graph can tell you a sample is obfuscated before you read a single instruction.

Basic blocks

A basic block is a maximal run of instructions with one way in and one way out: execution can only enter at the first instruction and, once it starts, runs every instruction in order until the last one. There are no jumps into the middle and no branches out of the middle.

The standard way to find blocks is to mark leaders, the instructions that start a block:

A block then runs from one leader up to, but not including, the next. The last instruction of a block is usually a jmp, a conditional jump or a ret; if it is an ordinary instruction, the block simply falls through into the next leader.

What about call? Inside a function's CFG, most tools treat a call as an ordinary instruction that returns to the next one, so it does not end a block. The call relationship goes into the call graph instead. The exception is a call to a function known not to return, such as exit or ExitProcess, which does end the block with no successor.

Control-flow graphs

The CFG of a function has one node per basic block and one directed edge for each possible transfer of control:

• Taken edge: from a block ending in a jump to the jump target.
• Fall-through edge: from a block ending in a conditional jump (or in no jump at all) to the block that follows it in memory.
• Indirect edges: from a jmp rax or jmp [table + reg*8] to every target the tool could recover, typically from a switch table.

A block with no successors is an exit: it ends in ret, a tail call, or a call to a non-returning function.

The call graph is the same idea one level up: one node per function, one edge per call site. It is how you find "everything that eventually reaches CreateRemoteThread" or "who calls the string decryption routine". Indirect calls (call rax, call [rbx+18h], virtual methods, callbacks) leave holes in it, exactly as indirect jumps leave holes in a CFG. Tracking those down is the topic of Cross-References and Data Flow.

Reading common shapes

With practice you read a CFG like a silhouette. The same source structures compile to the same shapes across compilers and architectures.

if and if/else

      if without else                   if / else
      ┌─────────┐                      ┌─────────┐
      │ cmp; jcc│                      │ cmp; jcc│
      └──┬───┬──┘                      └──┬───┬──┘
         │   ▼                            ▼   ▼
         │ ┌──────┐                  ┌──────┐ ┌──────┐
         │ │ then │                  │ then │ │ else │
         │ └──┬───┘                  └──┬───┘ └──┬───┘
         ▼    ▼                         ▼        ▼
      ┌─────────┐                      ┌─────────┐
      │  join   │                      │  join   │
      └─────────┘                      └─────────┘
       "triangle"                        "diamond"

Compilers usually invert the condition: if (x == 0) { ... } becomes test eax, eax; jne skip, so the taken edge skips the body. Read the jump as "skip the block unless...". cmp and test set the flags; the conditional jump names the relation.

Loops and back edges

A loop is a cycle in the graph. The edge that closes the cycle, from the end of the body back to the block that decides whether to go round again, is a back edge; its target is the loop header.

   while / for at -O0                 at -O2 (rotated loop)
   ┌───────┐                          ┌───────────┐
   │ init  │── jmp ──┐                │ init; test│── jcc ──► exit (0 iterations)
   └───────┘         ▼                └─────┬─────┘
   ┌───────┐    ┌──────────┐                ▼
   │ body  │◄───│ cond; jcc│          ┌───────────┐
   └───┬───┘    └────┬─────┘          │ body      │◄──┐
       └── back ─────┘ ▼ exit         │ cond; jcc │───┘ back edge
                                      └─────┬─────┘
                                            ▼ exit

A precise definition uses dominators: block A dominates block B if every path from the function entry to B goes through A. A back edge is an edge B → A where A dominates B, and the natural loop is A plus every block that can reach B without passing through A. You rarely compute dominators by hand, but the idea explains two useful facts. First, the loop header is the block the entry must pass through, which is not always the block at the lowest address: at -O0, GCC often jumps forward to a condition placed after the body. Second, "which blocks are inside this loop" has a crisp answer, which is how decompilers turn a cycle back into while or for.

switch statements

A switch compiles to one of two shapes, and the compiler picks per switch:

The jump-table shape is distinctive: a single node with five, ten or two hundred outgoing edges, all converging on one join block (the break). A bytecode interpreter, a command dispatcher in a backdoor and a state machine all look like this. So does a flattened function, as you will see next.

Function boundaries on x64 Windows

Everything above assumes you know where a function starts and ends. In a stripped binary you do not, so tools combine several sources of evidence.

Prologues and epilogues. A typical MSVC x64 function saves the non-volatile registers it uses, reserves stack space once, and undoes both before returning:

; prologue
mov     [rsp+8], rbx        ; save a non-volatile register in the home space
push    rdi
sub     rsp, 20h            ; shadow space for callees (+ locals)
; ... body ...
; epilogue
mov     rbx, [rsp+30h]      ; restore rbx from the home space
add     rsp, 20h
pop     rdi
ret

Frame-pointer prologues (push rbp; mov rbp, rsp) are common in GCC -O0 output and 32-bit code but optional on x64. Optimised leaf functions may have no prologue at all. Prologue scanning is a useful heuristic, not proof. The calling conventions page covers which registers are volatile, the 32-byte shadow space, and how arguments arrive in rcx, rdx, r8 and r9 on Windows versus rdi, rsi, rdx, rcx, r8 and r9 on Linux; see also the stack.

.pdata and unwind information. The x64 Windows ABI does not walk the stack through frame pointers. Instead, every function that touches the stack or calls anything must have a RUNTIME_FUNCTION entry in the exception directory (normally the .pdata section): a start RVA, an end RVA and a pointer to an UNWIND_INFO structure in .xdata that describes the prologue. The table is sorted by address and must be accurate or exception handling breaks, so it is one of the most reliable function lists you will get from a stripped PE. Only leaf functions (ones that call nothing, allocate no stack space and save no non-volatile registers) may omit an entry.

Two caveats matter for malware. A function can be split into several chunks, with separate .pdata entries chained together, when the compiler moves cold code (error paths) away from the hot path. And code that is written into memory at runtime, such as injected shellcode or an unpacked payload, has no entry at all unless its author registered one.

ELF has no mandatory equivalent. On Linux, .eh_frame often lists function ranges for unwinding, and symbols help when present, but a stripped ELF leaves tools more reliant on recursive descent and prologue scanning.

CFG shape as a fingerprint

Because compilers produce such regular shapes, an irregular shape stands out. Three patterns are worth recognising at a glance; a later module covers deobfuscation in depth:

• Flattened control flow. Control-flow flattening rewrites a function so every original block returns to a central dispatcher that picks the next block from a state variable. The graph becomes one hub with dozens of spokes, each spoke jumping back to the hub. It looks like a giant switch inside a loop, and the natural loop covers almost the whole function.
• Opaque predicates. Opaque predicates add conditional branches whose outcome is fixed. The graph gains edges into blocks that never execute, often filled with junk or dead code.
• Virtualised code. Code virtualization replaces a function with bytecode and an interpreter: the CFG you see is the interpreter's fetch-decode-dispatch loop, identical for every protected function.

Shape is also a similarity measure. Graph-based diffing tools match functions across two builds by comparing block counts, edges and call-graph neighbours, which is how analysts track a malware family from one version to the next even after recompilation.

Graph views in practice

• IDA: press Space to toggle between the linear listing and the graph view. Edges are coloured: green for a taken conditional jump, red for the fall-through, blue for unconditional flow.
• Ghidra: open Window → Function Graph for the current function; Window → Function Call Graph shows callers and callees.
• Cutter (the GUI for Rizin): the Graph tab shows the CFG of the function under the cursor.

In all of them, start with the silhouette: how many exits, where the loops are, whether there is a fan-out block. Only then read instructions, beginning with the blocks that make calls.

Tip: Rename blocks as you go. Labelling the loop header, the switch dispatcher and the error exits turns an anonymous graph into a map you can navigate days later.

Lab: build and compare CFGs

You need the Python virtual environment from the previous lab (capstone, pyelftools), plus pefile, an x86-64 Linux GCC (native or x86_64-linux-gnu-gcc), and optionally x86_64-w64-mingw32-gcc and Graphviz. The function under study is a harmless string scorer with a loop and a switch.

1. Save the program and build it twice:

   /* lab2.c - a harmless scoring function with a loop and a switch */
   #include <stdio.h>
   
   int score(const char *s) {
       int total = 0;
       for (int i = 0; s[i] != '\0'; i++) {
           switch (s[i]) {
           case 'a': total += 1;   break;
           case 'b': total += 3;   break;
           case 'c': total *= 2;   break;
           case 'd': total -= 4;   break;
           case 'e': total ^= 5;   break;
           case 'f': total <<= 1;  break;
           default:  total -= 1;   break;
           }
       }
       return total;
   }
   
   int main(int argc, char **argv) {
       printf("%d\n", score(argc > 1 ? argv[1] : "abcdef"));
       return 0;
   }

   x86_64-linux-gnu-gcc -O0 -o lab2_O0 lab2.c
   x86_64-linux-gnu-gcc -O2 -o lab2_O2 lab2.c
   ./venv/bin/pip install pefile

2. Save cfg.py. It reuses the worklist idea of recdis.py, but stays inside one function, does not follow calls, records the successors of every branch, recovers simple 8-byte jump tables, then splits the result into blocks:

   # cfg.py - split one function into basic blocks and emit a Graphviz CFG
   import struct, sys
   from capstone import Cs, CS_ARCH_X86, CS_MODE_64, CS_GRP_JUMP, CS_GRP_RET
   from capstone.x86 import X86_OP_IMM, X86_OP_MEM
   from elftools.elf.elffile import ELFFile
   
   def find_function(elf, name):
       for sym in elf.get_section_by_name(".symtab").iter_symbols():
           if sym.name == name and sym["st_info"]["type"] == "STT_FUNC":
               return sym["st_value"], sym["st_size"]
       sys.exit(f"no function {name}")
   
   def read_va(elf, va, size):
       """Read `size` bytes at virtual address `va` from whichever section holds it."""
       for sec in elf.iter_sections():
           start = sec["sh_addr"]
           if start and start <= va < start + sec["sh_size"] and sec["sh_type"] != "SHT_NOBITS":
               return sec.data()[va - start: va - start + size]
       return None
   
   def jump_table(elf, insn, prev, lo, hi):
       """Recover targets of `jmp [reg*8 + table]`, bounded by a preceding `cmp x, N`."""
       op = insn.operands[0]
       if op.type != X86_OP_MEM or op.mem.scale != 8 or op.mem.base != 0:
           return []
       bound = next((p.operands[1].imm for p in reversed(prev)
                     if p.mnemonic == "cmp" and p.operands[1].type == X86_OP_IMM), None)
       if bound is None:
           return []
       raw = read_va(elf, op.mem.disp, 8 * (bound + 1)) or b""
       targets = [struct.unpack_from("<Q", raw, i)[0] for i in range(0, len(raw), 8)]
       return [t for t in targets if lo <= t < hi]
   
   def recover(elf, start, size):
       text = elf.get_section_by_name(".text")
       base, code = text["sh_addr"], text.data()
       md = Cs(CS_ARCH_X86, CS_MODE_64)
       md.detail = True
       lo, hi = start, start + size
       insns, succs, leaders = {}, {}, {start}
       todo = [start]
       while todo:
           addr = todo.pop()
           while lo <= addr < hi and addr not in insns:
               insn = next(md.disasm(code[addr - base:], addr, 1))
               insns[addr] = insn
               nxt = addr + insn.size
               if insn.group(CS_GRP_RET) or insn.mnemonic == "hlt":
                   succs[addr] = []
                   break
               if insn.group(CS_GRP_JUMP):
                   op = insn.operands[0]
                   if op.type == X86_OP_IMM:
                       targets = [op.imm]
                   else:                          # indirect: try a switch table
                       before = [insns[a] for a in sorted(insns) if a < addr][-4:]
                       targets = jump_table(elf, insn, before, lo, hi)
                       print(f"indirect {insn.mnemonic} {insn.op_str} at {addr:#x}"
                             f" -> {len(set(targets))} table targets", file=sys.stderr)
                   if insn.mnemonic != "jmp":     # conditional: also falls through
                       targets = targets + [nxt]
                   succs[addr] = targets
                   leaders.update(targets)
                   todo.extend(targets)
                   break
               addr = nxt                          # calls fall through, not followed
       # split the reached instructions into basic blocks
       blocks, current = {}, None
       for a in sorted(insns):
           if current is None or a in leaders or blocks[current][-1].address in succs:
               current = a
               blocks[a] = []
           blocks[current].append(insns[a])
       edges = []
       for b, body in blocks.items():
           last = body[-1]
           if last.address in succs:
               outs = succs[last.address]
           else:                                  # block ends because the next one is a leader
               outs = [last.address + last.size]
           for t in dict.fromkeys(outs):          # de-duplicate, keep order
               kind = "fall" if t == last.address + last.size and last.mnemonic != "jmp" else "jump"
               edges.append((b, t, kind))
       return blocks, edges
   
   def back_edges(blocks, edges, entry):
       """Edges whose target is still on the DFS stack: the signature of a loop."""
       graph = {b: [t for s, t, _ in edges if s == b] for b in blocks}
       state, found = {}, set()
       def dfs(n):
           state[n] = "open"
           for m in graph.get(n, []):
               if state.get(m) == "open":
                   found.add((n, m))
               elif m not in state:
                   dfs(m)
           state[n] = "done"
       dfs(entry)
       return found
   
   def to_dot(name, blocks, edges, back):
       out = [f'digraph "{name}" {{', '  node [shape=box fontname="monospace" fontsize=10];']
       for b, body in blocks.items():
           text = "\\l".join(f"{i.address:x}: {i.mnemonic} {i.op_str}" for i in body)
           out.append(f'  b{b:x} [label="{text}\\l"];')
       for s, t, kind in edges:
           style = "color=blue" if (s, t) in back else ("style=dashed" if kind == "fall" else "")
           out.append(f"  b{s:x} -> b{t:x} [{style}];")
       out.append("}")
       return "\n".join(out)
   
   if __name__ == "__main__":
       elf = ELFFile(open(sys.argv[1], "rb"))
       start, size = find_function(elf, sys.argv[2])
       blocks, edges = recover(elf, start, size)
       back = back_edges(blocks, edges, start)
       print(to_dot(sys.argv[2], blocks, edges, back))
       print(f"{sys.argv[2]}: {len(blocks)} blocks, {len(edges)} edges, "
             f"back edges: {', '.join(f'{s:#x}->{t:#x}' for s, t in sorted(back))}",
             file=sys.stderr)

   The leader rules from the start of this lesson are the leaders set plus the blocks[current][-1].address in succs test, which starts a new block after any branch or ret. Back edges are found with a depth-first search: an edge to a block that is still being explored closes a cycle. On reducible graphs such as compiler output, that matches the dominator definition.

3. Build the CFG of the unoptimised build:

   ./venv/bin/python cfg.py lab2_O0 score > score_O0.dot

   score: 22 blocks, 32 edges, back edges: 0x40116d->0x401171

   digraph "score" {
     node [shape=box fontname="monospace" fontsize=10];
     b4010e7 [label="4010e7: push rbp\l4010e8: mov rbp, rsp\l ... 4010fd: jmp 0x401171\l"];
     b4010ff [label="4010ff: mov eax, dword ptr [rbp - 8]\l ... 401112: cmp eax, 0x66\l401115: je 0x401163\l"];
     b401117 [label="401117: cmp eax, 0x66\l40111a: jg 0x401168\l"];
     b40111c [label="40111c: cmp eax, 0x65\l40111f: je 0x40115d\l"];
     ...
     b4010e7 -> b401171 [];
     b4010ff -> b401163 [];
     b4010ff -> b401117 [style=dashed];
     b401117 -> b401168 [];
     ...
     b40116d -> b401171 [color=blue];
     b401171 -> b4010ff [];
     b401171 -> b401189 [style=dashed];
   }

   At -O0 GCC compiled the switch into a compare chain: cmp eax, 0x66 / je, then jg to the default, walking down to 0x61. Every local lives on the stack at [rbp - 4] and [rbp - 8]. Notice the back edge: the entry block jumps forward to 0x401171, the loop condition, so that block is the loop header even though the body sits at lower addresses.

4. Build the CFG of the optimised build:

   ./venv/bin/python cfg.py lab2_O2 score > score_O2.dot

   indirect jmp qword ptr [rax*8 + 0x402008] at 0x40113a -> 5 table targets
   score: 13 blocks, 18 edges, back edges: 0x40114a->0x401130

     b401130 [label="401130: sub eax, 0x61\l401133: cmp al, 5\l401135: ja 0x40117d\l"];
     b401137 [label="401137: movzx eax, al\l40113a: jmp qword ptr [rax*8 + 0x402008]\l"];
     b401148 [label="401148: add edx, edx\l"];
     b40114a [label="40114a: movzx eax, byte ptr [rdi]\l40114d: add rdi, 1\l401151: test al, al\l401153: jne 0x401130\l"];
     ...
     b401137 -> b401170 [];
     b401137 -> b401168 [];
     b401137 -> b401148 [];
     b401137 -> b401160 [];
     b401137 -> b401178 [];
     b40114a -> b401130 [color=blue];

   Now there is a jump table. sub eax, 0x61 maps 'a'..'f' to 0..5, cmp al, 5 / ja sends everything else to the default, and the indirect jmp fans out. Six table entries produce only five targets: GCC noticed that total *= 2 and total <<= 1 are the same operation and merged the 'c' and 'f' cases into one add edx, edx block. Locals live in registers, and the loop is rotated: the test at 0x40114a jumps back to the dispatcher.

5. Render both graphs and put them side by side:

   dot -Tsvg score_O0.dot -o score_O0.svg
   dot -Tsvg score_O2.dot -o score_O2.svg

   Dashed edges are fall-throughs, the blue edge is the back edge.

6. Find function boundaries in a stripped PE. Build the same program for Windows, strip it, and read its exception directory with this pdata.py:

   # pdata.py - list function starts recorded in a PE32+ exception directory
   import sys
   import pefile
   
   pe = pefile.PE(sys.argv[1])
   base = pe.OPTIONAL_HEADER.ImageBase
   entries = getattr(pe, "DIRECTORY_ENTRY_EXCEPTION", [])
   print(f"{len(entries)} RUNTIME_FUNCTION entries")
   for e in entries[:int(sys.argv[2]) if len(sys.argv) > 2 else 10]:
       s = e.struct
       print(f"  {base + s.BeginAddress:#x} - {base + s.EndAddress:#x}"
             f"  ({s.EndAddress - s.BeginAddress:4} bytes)  unwind @ {s.UnwindData:#x}")

   x86_64-w64-mingw32-gcc -O2 -o lab2.exe lab2.c
   x86_64-w64-mingw32-strip -o lab2_stripped.exe lab2.exe
   x86_64-w64-mingw32-nm lab2.exe | grep -E " T (score|main)$"
   ./venv/bin/python pdata.py lab2_stripped.exe 12

   0000000140002ac0 T main
   0000000140001490 T score
   47 RUNTIME_FUNCTION entries
     0x140001000 - 0x140001001  (   1 bytes)  unwind @ 0x6000
     0x140001010 - 0x140001017  (   7 bytes)  unwind @ 0x6004
     ...
     0x140001480 - 0x140001481  (   1 bytes)  unwind @ 0x6068
     0x140001490 - 0x14000150d  ( 125 bytes)  unwind @ 0x606c
     0x140001510 - 0x140001552  (  66 bytes)  unwind @ 0x607c

   The stripped file has no symbols, yet .pdata still records a function at exactly the address the unstripped build calls score, with its size. Most of the 47 entries belong to the mingw-w64 C runtime, not to lab2.c.

7. Optional: open lab2_O2 in Ghidra (Function Graph) or Cutter (Graph tab) and compare with your SVG. Then disassemble score in lab2.exe with x86_64-w64-mingw32-objdump -d -M intel: the Windows build uses a table of 32-bit offsets (movsxd rax, dword ptr [r8+rax*4]; add rax, r8; jmp rax), which cfg.py does not recover. Extending jump_table to handle it is a good exercise.

Questions to answer: Which leader rule created the one-instruction block at 0x401148 in the -O2 graph? Why is the -O0 loop header at a higher address than the loop body, and how does the dominator definition settle which block is the header? What would happen to the -O2 CFG if cfg.py could not read the jump table, and how would a flattened function look different from this legitimate switch-in-a-loop? Why is .pdata more trustworthy than prologue scanning for a normal compiled PE, and when would it be missing?

Key takeaways

• A basic block has one entry and one exit; leaders are the function start, every jump target, and every instruction after a branch or ret.
• A CFG connects blocks with taken, fall-through and indirect edges; a call graph connects functions. Indirect jumps and calls leave holes in both.
• If/else makes triangles and diamonds, loops make cycles closed by back edges to a header that dominates the body, and switches make compare ladders or a single fan-out block driven by a jump table.
• On x64 Windows, .pdata RUNTIME_FUNCTION entries give reliable function boundaries even in stripped files; prologue scanning is only a heuristic.
• Optimisation reshapes the graph: fewer blocks, registers instead of stack slots, rotated loops, jump tables and merged cases.
• A hub-and-spoke graph covering a whole function, edges into never-executed blocks, or identical interpreter loops everywhere point to flattening, opaque predicates or virtualisation.