VM-based reversing challenges often reduce to a bytecode + dispatcher pair. The main task is to recover each opcode’s semantics and lift the bytecode into a form that exposes the verifier’s constraints.
This post uses a small stack VM to show the workflow from dispatcher analysis to direct inversion and SMT solving.
1. VM Skeleton
Many challenge VMs are stack-based. A program counter, stack pointer, condition flag, and small value stack are enough for the example below.
typedef struct { const uint8_t *code; const uint8_t *input; uint32_t pc; uint8_t sp; uint8_t flag; uint8_t stack[64];} VM;
static uint8_t rol8(uint8_t v, unsigned r) { r &= 7u; return (uint8_t)((v << r) | (v >> ((8u - r) & 7u)));}
static int vm_run(VM *vm) { for (;;) { uint8_t op = vm->code[vm->pc++]; switch (op) { case 0x01: { // PUSH imm8 vm->stack[vm->sp++] = vm->code[vm->pc++]; break; } case 0x02: { // LOAD idx uint8_t idx = vm->code[vm->pc++]; vm->stack[vm->sp++] = vm->input[idx]; break; } case 0x10: { // XOR uint8_t b = vm->stack[--vm->sp]; uint8_t a = vm->stack[vm->sp - 1]; vm->stack[vm->sp - 1] = a ^ b; break; } case 0x11: { // ADD uint8_t b = vm->stack[--vm->sp]; uint8_t a = vm->stack[vm->sp - 1]; vm->stack[vm->sp - 1] = (uint8_t)(a + b); break; } case 0x12: { // ROL imm uint8_t r = vm->code[vm->pc++]; vm->stack[vm->sp - 1] = rol8(vm->stack[vm->sp - 1], r); break; } case 0x20: { // CMP imm uint8_t v = vm->stack[--vm->sp]; uint8_t imm = vm->code[vm->pc++]; vm->flag = (v == imm); break; } case 0x30: { // JNZ rel8 (jump when flag == 0) int8_t off = (int8_t)vm->code[vm->pc++]; if (!vm->flag) { vm->pc = (uint32_t)(vm->pc + off); } break; } case 0xFF: { // HALT imm uint8_t ret = vm->code[vm->pc++]; return ret; } default: return 0; } }}When reversing this interpreter, I would establish the following details first.
- Whether
pcadvances before or after each opcode and operand fetch. - Whether
spchanges before or after each push and pop. - Whether the branch uses
flagdirectly or tests an inverted condition. - Whether the
JNZoperand is a signed relative offset or an absolute address.
Opcode Table
Recording the stack effect makes it much easier to derive expressions later. Let S denote the stack.
| Opcode | Mnemonic | Stack Effect | Desc |
|---|---|---|---|
0x01 | PUSH imm8 | S -> S, imm | Push an immediate byte |
0x02 | LOAD idx | S -> S, input[idx] | Push an input byte |
0x10 | XOR | S, a, b -> S, (a ^ b) | XOR |
0x11 | ADD | S, a, b -> S, (a + b) | mod 256 |
0x12 | ROL imm | S, a -> S, rol8(a, imm) | rotate |
0x20 | CMP imm | S, a -> S | flag = (a == imm) |
0x30 | JNZ rel8 | S -> S | Add off to pc when flag == 0 |
0xFF | HALT imm | S -> S | Return an immediate byte |
Write down stack effects before translating instructions into formulas. In particular, determine whether
CMPpops its operand or leaves it on the stack.
Dispatcher
I usually narrow down a VM interpreter in the following order.
- Opcode fetch: find a loop that repeatedly performs something like
op = code[pc++]. - Switch or jump table: look for
switch (op)or an indirect branch such asjmp [table + op*8]. - Operand fetch: note which handlers read additional bytes with
code[pc++]. These reads determine each instruction’s length. - Stack updates: use the positions of
sp++and--spto fix the exact push and pop semantics. - Flag use: trace whether the result of
CMPorTESTfeeds a laterJZorJNZhandler.
An obfuscated VM may transform each fetched opcode with XOR or ADD, or decrypt the whole bytecode buffer at runtime. Keep the raw encoded byte separate from the decoded dispatch value. Per-opcode transforms usually appear directly before dispatch; whole-buffer decryption means the bytecode should be extracted after that routine runs.
Bytecode Extraction and Disassembly
Once the bytecode is dumped, the next step is a small disassembler. If the opcode lengths are known, a linear parser is enough for this VM.
op_info = { 0x01: ("PUSH", 1), 0x02: ("LOAD", 1), 0x10: ("XOR", 0), 0x11: ("ADD", 0), 0x12: ("ROL", 1), 0x20: ("CMP", 1), 0x30: ("JNZ", 1), 0xFF: ("HALT", 1),}
def disasm(code): pc = 0 out = [] while pc < len(code): op = code[pc] name, imm_len = op_info.get(op, ("DB", 0)) if name == "DB": out.append(f"{pc:02X}: DB 0x{op:02X}") pc += 1 continue imm = None if imm_len: imm = code[pc + 1] if name == "JNZ": off = imm if imm < 0x80 else imm - 0x100 tgt = (pc + 2 + off) & 0xFFFFFFFF out.append(f"{pc:02X}: JNZ {off:+#x} ; -> {tgt:02X}") elif imm_len: out.append(f"{pc:02X}: {name} 0x{imm:02X}") else: out.append(f"{pc:02X}: {name}") pc += 1 + imm_len return outJNZ rel8 is relative to the program counter after the operand has been read. The one-byte operand is sign-extended before it is added. Using the instruction start or treating the offset as unsigned shifts every branch target.
2. Bytecode Example
This bytecode verifies an 8-byte input. Every input byte passes through the same instruction pattern, so a correct disassembly exposes the constraints immediately.
static const uint8_t program[] = { 0x02, 0x00, 0x01, 0x13, 0x10, 0x01, 0x05, 0x11, 0x12, 0x01, 0x20, 0xEE, 0x30, 0x64, 0x02, 0x01, 0x01, 0x57, 0x10, 0x01, 0x11, 0x11, 0x12, 0x01, 0x20, 0x94, 0x30, 0x56, 0x02, 0x02, 0x01, 0x9B, 0x10, 0x01, 0x1F, 0x11, 0x12, 0x01, 0x20, 0x3C, 0x30, 0x48, 0x02, 0x03, 0x01, 0xDF, 0x10, 0x01, 0x2A, 0x11, 0x12, 0x01, 0x20, 0xAD, 0x30, 0x3A, 0x02, 0x04, 0x01, 0x22, 0x10, 0x01, 0x07, 0x11, 0x12, 0x01, 0x20, 0xA8, 0x30, 0x2C, 0x02, 0x05, 0x01, 0x68, 0x10, 0x01, 0x19, 0x11, 0x12, 0x01, 0x20, 0x62, 0x30, 0x1E, 0x02, 0x06, 0x01, 0xA1, 0x10, 0x01, 0x2D, 0x11, 0x12, 0x01, 0x20, 0x06, 0x30, 0x10, 0x02, 0x07, 0x01, 0x3C, 0x10, 0x01, 0x3B, 0x11, 0x12, 0x01, 0x20, 0x1B, 0x30, 0x02, 0xFF, 0x01, 0xFF, 0x00};The disassembly repeats the following block.
00: LOAD 002: PUSH 0x1304: XOR05: PUSH 0x0507: ADD08: ROL 10A: CMP 0xEE0C: JNZ +0x64(repeated)70: HALT 172: HALT 0Each block is 14 bytes long.
- The first
JNZoffset is0x72 - 0x0E = 0x64. - The failure address is
0x72, whereHALT 0begins. - The success address is
0x70, whereHALT 1begins.
Deriving the Constraints
Because every block has the same shape, it is enough to lift one block. Tracking the stack after each instruction gives the expression directly.
LOAD i -> [x_i]PUSH k[i] -> [x_i, k_i]XOR -> [x_i ^ k_i]PUSH c[i] -> [x_i ^ k_i, c_i]ADD -> [(x_i ^ k_i) + c_i]ROL 1 -> [rol8((x_i ^ k_i) + c_i, 1)]CMP t[i] -> flag = (top == t_i), stack popJNZ fail -> if flag == 0, jump to failHere, is an input byte, is the XOR key, is the addition constant, and is the comparison target. Every arithmetic result is truncated to 8 bits.
Reversing the operations in the opposite order gives:
The constants extracted from the VM are:
k = [0x13, 0x57, 0x9B, 0xDF, 0x22, 0x68, 0xA1, 0x3C]c = [0x05, 0x11, 0x1F, 0x2A, 0x07, 0x19, 0x2D, 0x3B]t = [0xEE, 0x94, 0x3C, 0xAD, 0xA8, 0x62, 0x06, 0x1B]Real challenge VMs may mix
ROLandROR, reorder the addition, or move values between stacks and registers. The workflow is still the same: recover one handler at a time, record its state effect, and lift one repeated block before generalizing it.
3. Solving
Direct
def ror8(v, r): return ((v >> r) | (v << (8 - r))) & 0xFF
keys = [0x13, 0x57, 0x9B, 0xDF, 0x22, 0x68, 0xA1, 0x3C]adds = [0x05, 0x11, 0x1F, 0x2A, 0x07, 0x19, 0x2D, 0x3B]targets = [0xEE, 0x94, 0x3C, 0xAD, 0xA8, 0x62, 0x06, 0x1B]
out = []for i in range(8): v = ror8(targets[i], 1) v = (v - adds[i]) & 0xFF v = v ^ keys[i] out.append(v)
print(bytes(out))The eight constraints are independent, so direct inversion is the simplest solution. It is deterministic, easy to audit, and avoids introducing a solver when no variables depend on one another.
The script recovers b'andsopwn'. Replay those bytes through the original VM as a final check; a correct-looking inverse is not enough if an opcode, width, or truncation point was transcribed incorrectly.
SMT
SMT becomes useful when instructions mix several input bytes, share state across blocks, or constrain a path through control flow. The same lifted expression can be modeled with 8-bit bit-vectors.
from z3 import *
def rol8(v, r): return ((v << r) | LShR(v, 8 - r)) & 0xFF
keys = [0x13, 0x57, 0x9B, 0xDF, 0x22, 0x68, 0xA1, 0x3C]adds = [0x05, 0x11, 0x1F, 0x2A, 0x07, 0x19, 0x2D, 0x3B]targets = [0xEE, 0x94, 0x3C, 0xAD, 0xA8, 0x62, 0x06, 0x1B]
x = [BitVec(f"x{i}", 8) for i in range(8)]s = Solver()
for i in range(8): expr = rol8((x[i] ^ keys[i]) + adds[i], 1) s.add(expr == targets[i])
if s.check() == sat: m = s.model() ans = bytes([m[x[i]].as_long() for i in range(8)]) print(ans)
Here, sat only proves that the translated constraints have a model. It does not prove that the translation matches the binary or that the model is unique. Run the candidate through the original interpreter and, when uniqueness matters, add a blocking constraint and ask for a second model.
Small semantic differences can change the entire solution path. I would keep the following checklist nearby.
- Treat a
JNZ rel8operand as signed unless the handler proves otherwise. Anint8_tcast is a strong clue. - Fix the PC base precisely. Relative offsets are often measured from the PC after the operand fetch.
- Fix the stack and register widths. Confusing
uint8_twithuint32_tchanges overflow behavior. - Check whether
CMPpops its operand. The stack expression changes if the value remains live. - Look for XOR or ADD opcode decoding, or a buffer-decryption loop, before the dispatcher.
- When a pattern repeats, lift one block and apply the resulting expression to the rest.
4. Practice
#include <stdint.h>#include <stdio.h>
static uint8_t ror8(uint8_t v, unsigned r) { return (uint8_t)((v >> r) | (v << (8 - r)));}
static int run_vm(const uint8_t *code, size_t code_len, uint8_t *out, size_t out_cap, size_t *out_len) { uint8_t stack[64]; size_t sp = 0; size_t pc = 0; size_t out_idx = 0;
while (pc < code_len) { uint8_t op = code[pc++]; switch (op) { case 0xA1: { // PUSH imm8 if (pc >= code_len || sp >= sizeof(stack)) { return 0; } stack[sp++] = code[pc++]; break; } case 0xB2: { // ADD imm8 if (pc >= code_len || sp == 0) { return 0; } uint8_t imm = code[pc++]; stack[sp - 1] = (uint8_t)(stack[sp - 1] + imm); break; } case 0xC3: { // XOR imm8 if (pc >= code_len || sp == 0) { return 0; } uint8_t imm = code[pc++]; stack[sp - 1] ^= imm; break; } case 0xD4: { // ROR imm8 if (pc >= code_len || sp == 0) { return 0; } uint8_t imm = code[pc++]; stack[sp - 1] = ror8(stack[sp - 1], imm & 7u); break; } case 0xE5: { // OUT if (sp == 0 || out_idx >= out_cap) { return 0; } out[out_idx++] = stack[--sp]; break; } case 0xF6: { // HALT *out_len = out_idx; return 1; } default: return 0; } }
return 0;}
int main(int argc, char **argv) { (void)argc; (void)argv; static const uint8_t program[] = { 0xA1, 0xA7, 0xB2, 0x3A, 0xC3, 0x05, 0xD4, 0x01, 0xE5, 0xA1, 0x02, 0xB2, 0x7F, 0xC3, 0x2D, 0xD4, 0x05, 0xE5, 0xA1, 0xB0, 0xB2, 0x12, 0xC3, 0x71, 0xD4, 0x03, 0xE5, 0xA1, 0x3D, 0xB2, 0xC6, 0xC3, 0x13, 0xD4, 0x07, 0xE5, 0xA1, 0xDB, 0xB2, 0x9D, 0xC3, 0xA9, 0xD4, 0x02, 0xE5, 0xA1, 0x96, 0xB2, 0x21, 0xC3, 0x6C, 0xD4, 0x06, 0xE5, 0xA1, 0x55, 0xB2, 0xB8, 0xC3, 0x0F, 0xD4, 0x04, 0xE5, 0xA1, 0xE8, 0xB2, 0x4E, 0xC3, 0xD2, 0xD4, 0x01, 0xE5, 0xA1, 0x95, 0xB2, 0x3A, 0xC3, 0x05, 0xD4, 0x01, 0xE5, 0xA1, 0xC2, 0xB2, 0x7F, 0xC3, 0x2D, 0xD4, 0x05, 0xE5, 0xA1, 0xF8, 0xB2, 0x12, 0xC3, 0x71, 0xD4, 0x03, 0xE5, 0xA1, 0x62, 0xB2, 0xC6, 0xC3, 0x13, 0xD4, 0x07, 0xE5, 0xA1, 0x9F, 0xB2, 0x9D, 0xC3, 0xA9, 0xD4, 0x02, 0xE5, 0xA1, 0xCF, 0xB2, 0x21, 0xC3, 0x6C, 0xD4, 0x06, 0xE5, 0xA1, 0x55, 0xB2, 0xB8, 0xC3, 0x0F, 0xD4, 0x04, 0xE5, 0xA1, 0xD0, 0xB2, 0x4E, 0xC3, 0xD2, 0xD4, 0x01, 0xE5, 0xA1, 0xA3, 0xB2, 0x3A, 0xC3, 0x05, 0xD4, 0x01, 0xE5, 0xA1, 0x82, 0xB2, 0x7F, 0xC3, 0x2D, 0xD4, 0x05, 0xE5, 0xA1, 0x38, 0xB2, 0x12, 0xC3, 0x71, 0xD4, 0x03, 0xE5, 0xA1, 0xBD, 0xB2, 0xC6, 0xC3, 0x13, 0xD4, 0x07, 0xE5, 0xF6 };
uint8_t out[256]; size_t out_len = 0; int ok = run_vm(program, sizeof(program), out, sizeof(out), &out_len);
if (!ok) { return 1; }
fwrite(out, 1, out_len, stdout); fputc('\n', stdout); return 0;}This VM has the following instruction set.
| Opcode | Mnemonic | Stack Effect | Desc |
|---|---|---|---|
0xA1 | PUSH imm8 | S -> S, imm | Push an immediate byte |
0xB2 | ADD imm8 | S, a -> S, (a + imm) | mod 256 |
0xC3 | XOR imm8 | S, a -> S, (a ^ imm) | XOR |
0xD4 | ROR imm8 | S, a -> S, ror8(a, imm) | rotate |
0xE5 | OUT | S, a -> S | Append to the output buffer |
0xF6 | HALT | S -> S | Stop execution |
The bytecode repeats this pattern.
PUSH e_iADD k_iXOR a_iROR r_iOUTEach was chosen so that becomes one byte of the hint string. Solving the expression for gives:
The flag file contains bytecode in which these values are interleaved with the opcodes.
A1 8D B2 3A C3 05 D4 01 E5 A1 61 B2 7F C3 2D D405 E5 A1 40 B2 12 C3 71 D4 03 E5 A1 E4 B2 C6 C313 D4 07 E5 A1 77 B2 9D C3 A9 D4 02 E5 A1 91 B221 C3 6C D4 06 E5 A1 11 B2 B8 C3 0F D4 04 E5 A1C2 B2 4E C3 D2 D4 01 E5 A1 89 B2 3A C3 05 D4 01E5 A1 E4 B2 7F C3 2D D4 05 E5 A1 F8 B2 12 C3 71D4 03 E5 A1 E1 B2 C6 C3 13 D4 07 E5 A1 AB B2 9DC3 A9 D4 02 E5 A1 9A B2 21 C3 6C D4 06 E5 A1 B1B2 B8 C3 0F D4 04 E5 A1 6C B2 4E C3 D2 D4 01 E5A1 2D B2 3A C3 05 D4 01 E5 A1 8C B2 7F C3 2D D405 E5 A1 C6 B2 12 C3 71 D4 03 E5 A1 F6 B2 C6 C313 D4 07 E5 A1 DC B2 9D C3 A9 D4 02 E5 A1 8F B221 C3 6C D4 06 E5 A1 11 B2 B8 C3 0F D4 04 E5 A166 B2 4E C3 D2 D4 01 E5 A1 29 B2 3A C3 05 D4 01E5 A1 A4 B2 7F C3 2D D4 05 E5 A1 79 B2 12 C3 71D4 03 E5 A1 E2 B2 C6 C3 13 D4 07 E5 A1 D0 B2 9DC3 A9 D4 02 E5 A1 80 B2 21 C3 6C D4 06 E5 A1 D1B2 B8 C3 0F D4 04 E5 A1 1E B2 4E C3 D2 D4 01 E5A1 3D B2 3A C3 05 D4 01 E5 A1 A1 B2 7F C3 2D D405 E5 A1 DE B2 12 C3 71 D4 03 E5 A1 E4 B2 C6 C313 D4 07 E5 A1 DB B2 9D C3 A9 D4 02 E5 A1 9A B221 C3 6C D4 06 E5 A1 C0 B2 B8 C3 0F D4 04 E5 A1B4 B2 4E C3 D2 D4 01 E5 A1 2D B2 3A C3 05 D4 01E5 A1 0C B2 7F C3 2D D4 05 E5 A1 E0 B2 12 C3 71D4 03 E5 A1 C4 B2 C6 C3 13 D4 07 E5 A1 9F B2 9DC3 A9 D4 02 E5 A1 CF B2 21 C3 6C D4 06 E5 A1 42B2 B8 C3 0F D4 04 E5 A1 F0 B2 4E C3 D2 D4 01 E5A1 A5 B2 3A C3 05 D4 01 E5 A1 03 B2 7F C3 2D D405 E5 F6Because every bytecode block has the same fixed shape, we can parse , , , and directly.
from pathlib import Path
def ror8(v, r): return ((v >> r) | (v << (8 - r))) & 0xFF
def load_bytecode(path): data = path.read_text().strip().split() if not data: return [] return [int(tok, 16) for tok in data]
def parse_blocks(code): blocks = [] pc = 0
while pc < len(code): op = code[pc] if op == 0xF6: return blocks
if pc + 8 >= len(code): raise ValueError("truncated block")
if code[pc] != 0xA1 or code[pc + 2] != 0xB2 or code[pc + 4] != 0xC3: raise ValueError(f"unexpected opcode sequence at {pc:04X}") if code[pc + 6] != 0xD4 or code[pc + 8] != 0xE5: raise ValueError(f"unexpected opcode sequence at {pc:04X}")
e = code[pc + 1] k = code[pc + 3] a = code[pc + 5] r = code[pc + 7] blocks.append((e, k, a, r)) pc += 9
raise ValueError("missing HALT")
def recover_output(blocks): out = [] for e, k, a, r in blocks: v = (e + k) & 0xFF v ^= a v = ror8(v, r) out.append(v) return bytes(out)
def main(): bytecode_path = Path(__file__).with_name("flag") code = load_bytecode(bytecode_path) blocks = parse_blocks(code) output = recover_output(blocks) print(output.decode("ascii"))
if __name__ == "__main__": main()parse_blocks also validates the instruction sequence and rejects truncated data. This prevents a single wrong opcode length from silently desynchronizing the rest of the bytecode.
- Top 3 Solver (Discord @badabodaa)
@lacroix RubiyaLab 2025.12.31@Gunter RubiyaLab 2025.12.31@minzu RubiyaLab 2025.12.31