Reversing Custom VMs for CTF: Find the Dispatch Loop, Write the Emulator

Introduction

You open a binary in Ghidra, find main, and the decompiler hands you a hundred-case switch statement inside a while(1), indexed by a byte pulled out of a global array. There is no flag comparison anywhere. There is barely any logic anywhere.

That is a virtual machine, and the real program is not the one you are looking at. The binary is an interpreter, the array is the program, and your job is to recover the instruction set well enough to read it.

// The fingerprint, as Ghidra prints it
while (true) {
    op = *(byte *)(code + pc);
    pc = pc + 1;
    switch(op) {
        case 1:  stack[sp++] = *(int *)(code + pc); pc += 4; break;
        case 2:  sp--; stack[sp-1] += stack[sp];    break;
        case 3:  sp--; stack[sp-1] ^= stack[sp];    break;
        ...

A custom VM does not hide the algorithm. It moves the algorithm out of the instruction set your tools understand and into one they have never seen.

This is the reverse engineering category's favourite way to raise difficulty without raising complexity, and I have a soft spot for it, because the work is so mechanical once you accept the shape of it. There is no clever insight to have. You label about twenty opcodes, you write sixty lines of Python, and a problem that looked impenetrable turns into a listing you can read over breakfast. The only thing that stops people is not knowing that this is what the job is.

How far down this you need to go

Recognising a VM in five minutes

Four signs, and you rarely need all four. Two is enough to commit.

# Fast triage before opening a decompiler at all
file ./chal && checksec --file=./chal
strings -n 6 ./chal | head -40          # a VM binary is oddly quiet here
objdump -s -j .rodata ./chal | head -40 # look for the unexplained blob
 
# Jump tables are the loudest tell in the disassembly
objdump -d ./chal | grep -E 'jmp +\*.*\(,%r[a-z0-9]+,8\)'
 
# And the blob usually has a giveaway byte histogram: a handful of values,
# repeated, in the 0x00-0x20 range.
python3 -c "
import collections,sys
d=open('chal','rb').read()
print(collections.Counter(d[0x3000:0x3400]).most_common(12))"

How a bytecode VM works

Every interpreter, from the one in a 300-byte crackme to CPython, is the same three steps in a loop. Fetch the next instruction. Decode what it means. Execute it, which usually means changing some state and possibly moving the program counter somewhere other than forwards.

state:
    code[]    the bytecode, read-only
    pc        index into code
    stack[]   or regs[]  (see below)
    sp        index into stack
    mem[]     optional scratch memory
    input[]   your flag attempt, usually copied in at startup
 
loop:
    op = code[pc]; pc += 1          # fetch
    operands = code[pc:pc+n]; pc += n   # decode, n depends on op
    dispatch(op, operands)          # execute

The one design decision that changes how you read the bytecode is stack versus register. A stack machine has instructions with no operands: ADD pops two values and pushes one. A register machine has instructions that name their operands: ADD r1, r2, r3. Stack machines are far more common in CTF because they are easier to write, and you can tell which one you have by looking at whether the arithmetic cases in the switch reference an index that the case itself decrements.

Four shapes of dispatch loop

The switch statement is the friendly case. Three other shapes exist and each one hides the opcode table somewhere different, so knowing which you are looking at saves an hour.

The function pointer table is a gift when you meet it, because Ghidra will happily create a symbol for each handler and you can rename them as you work out what they do. Threaded code is the annoying one, and it is what obfuscators generate deliberately. The tell is that the loop appears to have no bottom: each case jumps to the next fetch rather than falling out to a shared one.

Recovering the opcode table

This is the part that feels like work, and there is a way to do it that keeps you honest. Make a table with four columns before you start, and fill it in as you read each case. Never carry an opcode meaning in your head.

Three practical rules make this go fast. First, name the state variables in the decompiler immediately: pc, sp, stack, code. Ghidra propagates the names into every case and the switch becomes readable in one pass. Second, work out operand widths from the pc increments, not from the arithmetic: a case that does pc += 4 takes a four-byte immediate regardless of what it does with it. Third, find the input opcode early. The instruction that reads your flag attempt is the anchor for everything else, because it tells you where the comparison logic starts.

Write the disassembler first

The instinct is to jump straight to an emulator. Resist it. A disassembler is half the code, it validates your opcode table immediately, and it gives you something to read. If your table is wrong, the disassembly desynchronises and produces obvious garbage, which is a much better error message than an emulator that quietly computes the wrong number.

import struct
 
CODE = open('bytecode.bin', 'rb').read()
 
# opcode -> (mnemonic, operand size in bytes)
OPS = {
    0x01: ('PUSH', 4), 0x02: ('ADD', 0), 0x03: ('XOR', 0),
    0x04: ('POP',  0), 0x05: ('DUP', 0), 0x06: ('JMP', 1),
    0x07: ('JZ',   1), 0x0e: ('OUT', 0), 0x0f: ('IN',  0),
    0xff: ('HALT', 0),
}
 
pc = 0
while pc < len(CODE):
    op = CODE[pc]
    if op not in OPS:
        print(f'{pc:04x}: .byte {op:#04x}   <-- unknown, table is wrong')
        pc += 1
        continue
    name, n = OPS[op]
    raw = CODE[pc+1:pc+1+n]
    if   n == 4: arg = struct.unpack('<i', raw)[0]
    elif n == 1: arg = struct.unpack('<b', raw)[0]
    else:        arg = None
    print(f'{pc:04x}: {name}' + (f' {arg}' if arg is not None else ''))
    pc += 1 + n

Run it. If ninety percent of the output is sensible and the last two hundred bytes are nonsense, you have found the boundary between code and data, which is useful. If it desynchronises at byte forty, one of your operand widths is wrong, and the instruction just before the garbage is the one to re-read.

Then the emulator

Once the listing reads cleanly, the emulator is a direct transcription of your table. Sixty lines, no cleverness. The reason to build it at all is that it lets you run the program on inputs of your choosing, instrument it, and search.

def run(code, user_input, trace=False):
    stack, pc, ip, out = [], 0, 0, []
    while pc < len(code):
        op = code[pc]; pc += 1
        if trace:
            print(f'{pc-1:04x} {op:#04x} {stack[-4:]}')
        if op == 0x01:                       # PUSH imm32
            stack.append(int.from_bytes(code[pc:pc+4], 'little'))
            pc += 4
        elif op == 0x02:                     # ADD
            b = stack.pop(); stack.append((stack.pop() + b) & 0xffffffff)
        elif op == 0x03:                     # XOR
            b = stack.pop(); stack.append(stack.pop() ^ b)
        elif op == 0x07:                     # JZ rel8
            rel = int.from_bytes(code[pc:pc+1], 'little', signed=True); pc += 1
            if stack.pop() == 0: pc += rel
        elif op == 0x0e:                     # OUT
            out.append(stack.pop())
        elif op == 0x0f:                     # IN
            stack.append(user_input[ip]); ip += 1
        elif op == 0xff:                     # HALT
            break
        else:
            raise ValueError(f'opcode {op:#04x} at {pc-1:#06x}')
    return out

Two details save real time. Mask arithmetic to the machine's word size, because Python integers are unbounded and a missing & 0xffffffff produces results that diverge from the binary only after a few thousand operations. And raise on unknown opcodes rather than ignoring them: an emulator that silently skips what it does not understand will happily produce a confident wrong answer.

Solving the program it runs

Now you have a readable program and a way to execute it. What you do next depends on what the bytecode is doing, and there are only three answers.

The z3 route deserves a note, because it is much less work than it sounds. You do not write a symbolic execution engine. You take your existing emulator and replace the input bytes with BitVec objects. Python operator overloading does the rest: every ^ and + in your emulator builds a constraint instead of computing a number, and at the end you assert the success condition and call solve().

from z3 import BitVec, Solver, sat
 
flag = [BitVec(f'c{i}', 32) for i in range(32)]
s = Solver()
for c in flag:
    s.add(c >= 0x20, c <= 0x7e)      # printable ASCII narrows the search a lot
 
result = run(code, flag)             # same emulator, symbolic input
for got, want in zip(result, EXPECTED):
    s.add(got == want)
 
print(s.check())
if s.check() == sat:
    m = s.model()
    print(''.join(chr(m[c].as_long()) for c in flag))

Branches are where the naive version breaks down, because a symbolic condition cannot decide which way to jump. If the bytecode has data-dependent control flow, either force the path you believe is correct and check the result, or hand the whole binary to angr and let it explore. The tradeoffs between those two are covered in z3 for CTF and the angr tutorial.

The other shape worth naming is the one MATRIX uses: the bytecode is not a checker at all, it is a puzzle. The VM encodes a maze, and the flag comes from the sequence of moves that walks it. Once you have the emulator, the solution is a breadth-first search over VM states rather than a constraint solve. That is worth keeping in mind before you reach for z3, because a state search over an emulator you already wrote is twenty lines.

When the VM is not custom

Before you spend two hours recovering an instruction set, check whether someone has already documented it. Half the "VM" challenges in the wild run a machine that has a specification and a disassembler you can install.

Redcode is the odd one out in that table, because you are not asked to reverse it at all: you write for it. That family, machines and languages with a published standard and a deliberately strange surface, is covered in esoteric languages in CTF, and the dividing line is simple. If a specification exists, reading it beats reconstructing the instruction set from a dispatch loop every time.

weirdSnake is the picoCTF version of this lesson. It looks like an unreadable binary blob and it is a marshalled Python code object, so the entire challenge collapses to two standard library calls. The language-specific paths are in Python reversing, WebAssembly reversing, Java reverse engineering, and Android APK reversing.

Why real software does this

It would be easy to file this under "CTF trick" and move on, but VM-based obfuscation is one of the few reverse engineering topics where the competition version and the industry version are genuinely the same technique.

Commercial protectors translate a program's hot functions into a randomly generated instruction set and ship an interpreter for it, so every protected build has a different machine and a disassembler for one binary is worthless against the next. Anti-cheat engines do the same to their detection routines. Malware families do it to their configuration parsers. The reason the technique is popular is not that it is unbreakable, because it obviously is not, but that it converts a five minute job into a five hour one, repeatedly, for every analyst.

Virtualisation obfuscation does not make software impossible to understand. It makes understanding it cost the same again, every time you rebuild.

Which is exactly why the mechanical method in this guide is worth practising on toy challenges. The skill that transfers is not the opcode table. It is the habit of recognising the shape in the first five minutes instead of the second hour.

picoCTF challenges

The wider category ladder is in the reverse engineering roadmap, and the assembly literacy every step above assumes is in x86-64 assembly for CTF.

Quick reference

# Is it a known VM? Thirty seconds, always first.
file ./chal && xxd ./chal | head -2
#   \0asm  -> wasm2wat      0xCAFEBABE -> javap -c
#   .pyc   -> marshal+dis   dex\n035   -> jadx
 
# Find the dispatcher
objdump -d ./chal | grep -E 'jmp +\*'          # jump table
objdump -s -j .rodata ./chal | head -60         # the bytecode blob
 
# Ghidra
#   rename pc / sp / stack / code in the decompiler first
#   right-click an indirect jump -> Create Jump Table if the switch looks broken
 
# Trace instead of reading, when the switch is large
gdb -q ./chal -ex 'break *DISPATCH' \
  -ex 'commands' -ex 'silent' -ex 'p/x $rax' -ex 'cont' -ex 'end' -ex run
 
# Build order that catches your own mistakes
#   1. opcode table as a written table
#   2. disassembler  (desyncs loudly when the table is wrong)
#   3. emulator      (mask arithmetic, raise on unknown opcodes)
#   4. validate against the real binary on one known input
#   5. invert, brute force, or z3

Related reading: Ghidra for recovering the switch, GDB for tracing the dispatch loop, z3 for the constraint solve, angr when the control flow is data-dependent, Python reversing for the bytecode you did not have to reverse, and binary patching for when the fastest answer is to remove the check instead of satisfying it.

Sources and further reading

The techniques here are standard practice rather than published research, so the references are the specifications and tools rather than writeups.

• CPython's ceval.c is the best-commented dispatch loop in open source, and reading its fetch-decode sequence once makes every hand-rolled VM in a crackme legible. It is also a working example of threaded dispatch, which is the shape that confuses Ghidra most.
• The dis module documentation doubles as an opcode reference for the most common "custom" VM you will meet, which turns out not to be custom.
• The WebAssembly core specification is worth skimming for its instruction listing alone: it is a modern stack machine designed in the open, and the design decisions it documents are the same ones a challenge author makes by instinct.
• Ghidra for the decompiler and jump-table recovery, and Unicorn when the machine turns out to be a real architecture you would rather emulate than reimplement.
• Z3 for the final solve. Its Python bindings are what make the "run your own emulator symbolically" trick a five-line change rather than a project.