Linear vs Recursive Disassembly

Up to now you have treated the code of a sample as a black box: you read its headers, its imports and its strings, and you measured its entropy. From this module on you open the box. The first tool you reach for is a disassembler, which turns machine-code bytes back into instructions such as mov, call and ret.

It is tempting to think of disassembly as a lookup table: byte C3 is ret, done. Translating one instruction is indeed mechanical. The hard part is deciding which bytes to translate, and where each instruction starts. Get that wrong and the listing you spend hours reading is fiction. This lesson explains the two classic strategies, where each one breaks, and why the answer matters so much when the author of the binary is actively trying to mislead you.

What a disassembler has to decide

A code section is just a run of bytes. Nothing in it marks "an instruction starts here" or "these eight bytes are a pointer, not code". A static disassembler must infer two things:

1. Where code is. Which byte ranges hold instructions, and which hold data (jump tables, constants, strings, alignment padding) that happen to sit in an executable section?
2. Where each instruction begins. On x86 and x86-64, instructions are anywhere from 1 to 15 bytes long. Their length depends on prefixes, the opcode, the ModRM and SIB bytes, and the size of any displacement and immediate (see x86 instruction encoding). You only learn how long an instruction is by decoding it, so one wrong starting point shifts every instruction after it.

Fixed-width architectures such as AArch64 make the second question almost free (every instruction is 4 bytes, aligned), which is why data-in-code is a much smaller problem there. x86 is dense: almost every byte value is a valid opcode or prefix, so a disassembler that starts in the wrong place rarely hits an obvious error. It just prints plausible-looking nonsense.

Here are the first seven bytes of a toy function, decoded two ways:

bytes:   eb 01 e8 8d 47 01 c3

follow the jmp (what the CPU does)       decode the next byte (linear sweep)
  +0  eb 01      jmp  +3                   +0  eb 01            jmp  +3
  +3  8d 47 01   lea  eax,[rdi+1]          +2  e8 8d 47 01 c3   call rel32 0xc301478d
  +6  c3         ret

Both columns are valid x86. Only control flow tells you which one the CPU actually executes. That example is not hypothetical: it is the first function you will build in the lab.

Linear sweep

The simplest strategy decodes a code section front to back: decode the instruction at the first byte, advance by its length, repeat until the end. objdump -d works this way, as do ndisasm and the quick "disassemble this buffer" loop most people write first.

  .text  ┌────┬──────┬────┬───────────┬────┬─────┐
         │ i1 │  i2  │ i3 │    i4     │ i5 │ ... │   decode, advance, decode...
         └────┴──────┴────┴───────────┴────┴─────┘
          ───────────────────────────────────────►

Strength: coverage. Linear sweep looks at every byte, so it never misses a function just because nothing visibly calls it. Code reached only through a function pointer, a callback registered with the OS, or a virtual method table still shows up in the listing.

Weakness: it has no idea what is data. Whenever non-code bytes sit inside an executable section, linear sweep decodes them anyway:

• Jump tables. A switch statement compiled to an indirect jump often uses a table of addresses or offsets. GCC and Clang put these tables in a read-only data section, but MSVC has historically placed some of them in .text right after the function.
• Inline constants and literal pools. Hand-written assembly, some runtime libraries and a lot of shellcode keep data next to the code that uses it.
• Padding. Compilers align function starts with nop sequences or int3 bytes (0xCC). These decode harmlessly, but other fillers do not.
• Deliberate junk. Bytes inserted by an obfuscator precisely because they derail a linear sweep.

Decoding data as code produces two kinds of damage. The data itself becomes garbage instructions, which is annoying but usually recognisable. Worse, the last garbage "instruction" can run past the end of the data and swallow the first bytes of real code. The disassembler is now desynchronised: it is decoding real code from the wrong offset.

x86 resynchronises — eventually

The good news is that x86 decoding tends to fall back into step on its own. A misaligned decode produces a few bogus instructions, and sooner or later one of them happens to end exactly on a real instruction boundary; from then on the two streams agree. In the lab you will measure this on a real binary: most misaligned starting points line up again after one or two bogus instructions, and few need more than five.

The bad news is what gets lost in between. Those few instructions are exactly the ones the data swallowed, and one of them may be the call or conditional jump that matters. A branch target that lands in the middle of an instruction in your listing is the classic symptom: the code says "go to address X", yet the disassembler shows no instruction starting at X.

Tip: Symbols hide desynchronisation. objdump restarts decoding at every symbol it knows about, so an unstripped binary resynchronises at each function start for free. Strip the binary and the same junk byte can corrupt the tail of one function and the head of the next.

Recursive descent

The second strategy decodes by following control flow, the way the CPU would. It starts from addresses known to be code and treats every branch as a pointer to more code:

• Seeds: the entry point from the file header, exported functions, symbols if the binary has any (see ELF for Malware Analysts and Imports, Exports and the IAT).
• Decode instructions one after another from a seed.
• At a jmp, queue the target and stop this run; the bytes after an unconditional jump are not reached from here.
• At a conditional jump, queue the target and keep going, because both outcomes are possible.
• At a call, queue the callee and (usually) keep going, assuming the callee returns.
• At ret or hlt, stop this run.
• Repeat until the work queue is empty.

  entry ──► push rbx
            ...
            call add_one ─────────────► add_one: jmp L1 ──┐
            ...                                   (junk)  │ never decoded
            ret                              L1:  lea ◄───┘
                                                  ret

Because it never decodes bytes that no path reaches, recursive descent steps over inline data and junk that sits after an unconditional jump. This is why every serious interactive disassembler is built on it.

Weakness: it only sees what it can follow.

• Indirect branches. jmp rax, call [rip+X] and call [r12+rbx*8] have targets that only exist at runtime. Switch tables, virtual calls, callbacks and every call through the import table fall into this category.
• Unreached code. A function whose only reference is a pointer stored in data (a thread start routine, a window procedure, an entry in a table of handlers) has no incoming call, so it is never seeded.
• Non-returning functions. After call exit or call abort the compiler may place something unrelated: the next function, padding or a jump table. A disassembler that assumes every call returns decodes it as fall-through code; one that knows the callee never returns stops correctly. Getting this list wrong in either direction produces errors.
• Both edges of a branch are assumed live. If a conditional jump can in fact only go one way, the "other" edge leads into bytes the CPU never executes, and the disassembler decodes them anyway.

The last point is the one obfuscators exploit most, as you will see below.

What real tools do: recursive descent plus heuristics

IDA, Ghidra and Binary Ninja all start with recursive descent, then fill the gaps it leaves with heuristics:

The .pdata point deserves emphasis for Windows analysts. The x64 Windows ABI requires unwind information so exceptions can walk the stack, which means a normal 64-bit PE ships with an accurate list of function boundaries built in. Disassemblers use it to seed analysis, and you can read it yourself; the next lesson does exactly that. You met .pdata as "just another section" in PE Sections. It is one of the most useful ones.

These heuristics are also why two tools can disagree about the same binary. When IDA shows a function that Ghidra does not, or vice versa, one of them has applied a heuristic the other skipped. Knowing the underlying algorithms tells you which one to trust for a given region.

Warning: Aggressive heuristics trade false negatives for false positives. Ghidra's "Aggressive Instruction Finder" and similar options find more code in stripped binaries but also turn data into bogus functions. Use them deliberately, on a copy of your project, and check what they add.

How obfuscators exploit both strategies

Malware authors know which assumptions each strategy makes, and anti-disassembly tricks are built to break exactly those assumptions. A later module covers anti-disassembly in depth; here is the short version, so you recognise the patterns when your listing looks wrong:

• Junk byte after an always-taken jump. An unconditional jmp over one byte such as 0xE8 (the opcode of call rel32). Linear sweep decodes the junk as a five-byte call, swallowing the next four bytes of real code. Recursive descent handles this one correctly.
• Opaque predicate with junk on the dead edge. Replace the jmp with a conditional jump whose outcome is fixed, such as xor ecx, ecx followed by jz. The CPU always takes the branch, but a disassembler assumes both edges are live, so recursive descent now decodes the junk too, and the two decodings collide. See opaque predicates.
• Overlapping instructions. A byte that is both the last byte of one instruction and the first byte of the next one actually executed. The two-byte sequence EB FF is a jmp whose target is its own second byte, where FF C0 decodes as inc eax. No flat listing can show both interpretations of the same byte at once.
• Runtime-generated code. Code decrypted or patched at runtime (self-modifying code, packers) is not in the file at all; no static strategy can recover it. That is the domain of unpacking and dynamic analysis.

Lab: two disassemblers, one junk byte

You need an x86-64 Linux GCC (native on Linux, or a cross compiler such as x86_64-linux-gnu-gcc on macOS), binutils, Python 3 and a virtual environment with capstone and pyelftools. Optionally, install Ghidra. The program is harmless: it prints two numbers.

1. Create the C file and a hand-written assembly file with two toy helpers:

   /* lab1.c - a harmless program whose helpers live in tricks.S */
   #include <stdio.h>
   
   int add_one(int x);    /* jmp over a junk byte               */
   int times_two(int x);  /* always-taken jz over a junk byte   */
   
   int main(void) {
       printf("%d %d\n", add_one(41), times_two(21));
       return 0;
   }

   /* tricks.S - two toy functions with an inserted junk byte */
           .intel_syntax noprefix
           .text
           .globl add_one
   add_one:
           jmp     1f              /* unconditional: skip the junk      */
           .byte   0xE8            /* first byte of "call rel32"        */
   1:      lea     eax, [rdi+1]
           ret
   
           .globl times_two
   times_two:
           xor     ecx, ecx        /* ZF = 1, so the jz is always taken */
           jz      2f
           .byte   0xE8
   2:      lea     eax, [rdi+rdi]
           ret
   
           .section .note.GNU-stack,"",@progbits

2. Build it, keep a stripped copy, and set up Python:

   x86_64-linux-gnu-gcc -O1 -o lab1 lab1.c tricks.S    # or plain gcc on Linux
   x86_64-linux-gnu-strip -o lab1_stripped lab1
   python3 -m venv venv && ./venv/bin/pip install capstone pyelftools

   To try the same on Windows, build with x86_64-w64-mingw32-gcc and disassemble with x86_64-w64-mingw32-objdump -d. Note that the first integer argument arrives in ecx there, not edi, so the toy functions return different numbers; the disassembly lesson is identical.

3. Linear sweep: disassemble the stripped copy with objdump and find the two helpers right after main (addresses will differ on your system):

   x86_64-linux-gnu-objdump -d -M intel lab1_stripped

     401116:	5b                   	pop    rbx
     401117:	c3                   	ret
     401118:	eb 01                	jmp    40111b <printf@plt+0xeb>
     40111a:	e8 8d 47 01 c3       	call   ffffffffc34158ac <printf@plt+0xffffffffc301487c>
     40111f:	31 c9                	xor    ecx,ecx
     401121:	74 01                	je     401124 <printf@plt+0xf4>
     401123:	e8 8d 04 3f c3       	call   ffffffffc37f15b5 <printf@plt+0xffffffffc33f0585>
     401128:	0f 1f 84 00 00 00 00 	nop    DWORD PTR [rax+rax*1+0x0]

   The real lea and ret of both helpers are gone, swallowed by two impossible calls to addresses outside the program. Two branch targets, 40111b and 401124, point into the middle of those calls: that is your desynchronisation alarm. The stream is back in step one instruction later.

4. Save the recursive disassembler as recdis.py:

   # recdis.py - a tiny recursive-descent disassembler for x86-64 ELF files
   import sys
   from capstone import Cs, CS_ARCH_X86, CS_MODE_64, CS_GRP_JUMP, CS_GRP_CALL, CS_GRP_RET
   from capstone.x86 import X86_OP_IMM
   from elftools.elf.elffile import ELFFile
   
   STOP = {"jmp", "ret", "hlt", "ud2"}         # no fall-through after these
   
   def load(path):
       elf = ELFFile(open(path, "rb"))
       text = elf.get_section_by_name(".text")
       seeds = {elf.header.e_entry}
       symtab = elf.get_section_by_name(".symtab")  # absent once stripped
       if symtab:
           seeds |= {s["st_value"] for s in symtab.iter_symbols()
                     if s["st_info"]["type"] == "STT_FUNC" and s["st_value"]}
       return text["sh_addr"], text.data(), seeds
   
   def direct_target(insn):
       """Return the target of a direct jmp/jcc/call, or None if indirect."""
       op = insn.operands[0] if insn.operands else None
       return op.imm if op is not None and op.type == X86_OP_IMM else None
   
   def disassemble(base, code, seeds, code_ptr_heuristic=False):
       md = Cs(CS_ARCH_X86, CS_MODE_64)
       md.detail = True
       end = base + len(code)
       insns = {}                                 # address -> instruction
       todo = [a for a in seeds if base <= a < end]
       while todo:
           addr = todo.pop()
           while base <= addr < end and addr not in insns:
               insn = next(md.disasm(code[addr - base:], addr, 1), None)
               if insn is None:                   # undecodable bytes: give up here
                   print(f"  ! invalid opcode at {addr:#x}")
                   break
               insns[addr] = insn
               if insn.group(CS_GRP_JUMP) or insn.group(CS_GRP_CALL):
                   target = direct_target(insn)
                   if target is not None:
                       todo.append(target)
                   else:
                       print(f"  ? indirect {insn.mnemonic} {insn.op_str} at {addr:#x}")
               elif code_ptr_heuristic:
                   # an immediate that points into .text may be a code pointer
                   for op in insn.operands:
                       if op.type == X86_OP_IMM and base <= op.imm < end:
                           todo.append(op.imm)
               if insn.mnemonic in STOP or insn.group(CS_GRP_RET):
                   break
               addr += insn.size                  # fall through (also after call)
       return insns
   
   def report(insns):
       covered = {}                               # byte address -> owning insns
       for a, i in insns.items():
           for b in range(a, a + i.size):
               covered.setdefault(b, []).append(a)
       for a in sorted(insns):
           i = insns[a]
           clash = {o for b in range(a, a + i.size) for o in covered[b]} - {a}
           flag = "  <-- overlaps " + ", ".join(hex(c) for c in sorted(clash)) if clash else ""
           print(f"{a:#x}: {i.bytes.hex(' '):<24} {i.mnemonic} {i.op_str}{flag}")
   
   if __name__ == "__main__":
       base, code, seeds = load(sys.argv[1])
       insns = disassemble(base, code, seeds, "--code-pointers" in sys.argv)
       report(insns)
       print(f"{len(insns)} instructions, {sum(i.size for i in insns.values())}"
             f" of {len(code)} .text bytes reached")

   The core is the worklist in disassemble: pop an address, decode until a stop instruction, push every direct branch target. The report function flags any two instructions that claim the same byte.

5. Run it on the stripped binary, seeded only by the entry point:

   ./venv/bin/python recdis.py lab1_stripped

     ? indirect call qword ptr [rip + 0x2f6e] at 0x401064
   0x401040: 31 ed                    xor ebp, ebp
   ...
   0x40105d: 48 c7 c7 e7 10 40 00     mov rdi, 0x4010e7
   0x401064: ff 15 6e 2f 00 00        call qword ptr [rip + 0x2f6e]
   0x40106a: f4                       hlt
   12 instructions, 43 of 353 .text bytes reached

   Pure recursive descent found _start and nothing else. _start hands the address of main to the C library in rdi and then calls __libc_start_main indirectly through the GOT. There is no direct call main anywhere to follow.

6. Enable the code-pointer heuristic, which treats immediates that point into .text as candidate code:

   ./venv/bin/python recdis.py lab1_stripped --code-pointers

   0x401118: eb 01                    jmp 0x40111b
   0x40111b: 8d 47 01                 lea eax, [rdi + 1]
   0x40111e: c3                       ret
   0x40111f: 31 c9                    xor ecx, ecx
   0x401121: 74 01                    je 0x401124
   0x401123: e8 8d 04 3f c3           call 0xffffffffc37f15b5  <-- overlaps 0x401124, 0x401127
   0x401124: 8d 04 3f                 lea eax, [rdi + rdi]  <-- overlaps 0x401123
   0x401127: c3                       ret   <-- overlaps 0x401123
   ...
   70 instructions, 221 of 353 .text bytes reached

   mov rdi, 0x4010e7 now seeds main, and from there both helpers. In add_one the junk byte is simply skipped: recursive descent wins. In times_two it decodes both edges of the always-taken je, so the junk call and the real lea/ret overlap. Your tool at least reports the conflict; a flat listing would have to pick one.

7. Measure self-synchronisation. Save this as resync.py, build a plain program with no tricks, and run it:

   # resync.py - how many bogus instructions before a misaligned decode lines up again?
   import sys
   from collections import Counter
   from capstone import Cs, CS_ARCH_X86, CS_MODE_64
   from elftools.elf.elffile import ELFFile
   
   text = ELFFile(open(sys.argv[1], "rb")).get_section_by_name(".text")
   code, base = text.data(), text["sh_addr"]
   md = Cs(CS_ARCH_X86, CS_MODE_64)
   boundaries = {i.address for i in md.disasm(code, base)}   # the true stream
   
   cost = Counter()
   for off in range(len(code) - 32):
       if base + off in boundaries:
           continue                                           # only wrong starts
       for n, insn in enumerate(md.disasm(code[off:], base + off), 1):
           if insn.address + insn.size in boundaries:         # back in step
               cost[n] += 1
               break
       else:
           cost["never"] += 1                                 # hit undecodable bytes
   total = sum(cost.values())
   for n in sorted(k for k in cost if k != "never"):
       print(f"back in step after {n} bogus instruction(s): {cost[n]:4} starts")
   print(f"hit an invalid opcode first:           {cost['never']:4} starts")
   print(f"{total} misaligned starts tested")

   cat > plain.c <<'EOF'
   #include <stdio.h>
   int main(int argc, char **argv) {
       unsigned h = 5381;
       for (int i = 1; i < argc; i++)
           for (char *p = argv[i]; *p; p++)
               h = h * 33 + (unsigned char)*p;
       printf("%08x\n", h);
       return 0;
   }
   EOF
   x86_64-linux-gnu-gcc -O2 -o plain plain.c
   ./venv/bin/python resync.py plain

   back in step after 1 bogus instruction(s):  119 starts
   back in step after 2 bogus instruction(s):   51 starts
   back in step after 3 bogus instruction(s):   26 starts
   back in step after 4 bogus instruction(s):    9 starts
   back in step after 5 bogus instruction(s):    9 starts
   back in step after 6 bogus instruction(s):    5 starts
   back in step after 7 bogus instruction(s):    2 starts
   hit an invalid opcode first:             56 starts
   277 misaligned starts tested

   GCC output keeps no data in .text, so linear decoding of it is a fair ground truth. Capstone stops at an invalid opcode, which is why some starts never realign here; objdump prints (bad) and continues instead.

8. Optional, in Ghidra: import lab1_stripped, run auto-analysis with the default options and go to the addresses of the two helpers. Check whether the junk byte in add_one is left as undefined data, how the conflict in times_two is displayed (look in the Bookmarks window for error bookmarks), and whether Ghidra found main without any symbol.

Questions to answer: objdump restarts at the times_two symbol in the unstripped lab1. Would that restart have mattered if the junk instruction had been one byte longer? Which heuristic recovered main in step 6, and what false positive could the same heuristic produce? If you changed the junk byte from 0xE8 to 0x90 (nop), what would each disassembler show, and would the trick still hide anything? Why can't either strategy decide statically that the je in times_two is always taken?

Key takeaways

• Disassembling one instruction is easy; deciding where code is and where each instruction starts is the real problem, especially on variable-length x86.
• Linear sweep sees every byte but decodes data as code, desynchronising the stream; x86 usually realigns within a few instructions, but the swallowed instructions are lost.
• Recursive descent follows control flow and skips data, but misses targets of indirect branches, code referenced only from data, and mishandles non-returning calls and never-taken edges.
• IDA, Ghidra and Binary Ninja are recursive descent plus heuristics: prologue scanning, switch-table recovery, code-pointer scanning, signatures and, on x64 Windows, .pdata function starts.
• Branch targets that land inside an instruction, and instructions that overlap, are strong signs of anti-disassembly; inspect those bytes by hand.