Recursive Disassembling

Tags:rev python

The two widespread ways to disassemble binaries are called linear sweep and recursive disassembling. While the first one is particularly easy to use and implement it also has severe drawbacks. Let me demystify the recursive algorithm, show its merits and provide you with a small sample script so you don’t need to skimp on disassembling when whipping up your next static analysis toolchain.

The situation is the same time and time agaion: You are analyzing yet another virtual machine in some CTF competition and you arrive at the point where you want to start writing the disassembler. As time is of the essence corners are cut and you end up with yet another linear sweep disassembler. But who can fault you? Once you finish the instruction decoder the full disassembler is just one list comprehension away.

from struct import unpack_from as upf

def decode(base_addr, code, addr):
    base_addr: The base address of the code
    code:      raw instructionstream as bytearray
    addr:      The address of the instruction to be decoded

    decode returns a triple:
    - True if this instruction terminates the bb, False if not
    - List of successors to this instruction (will contain exactly one element if it is not a terminator)
    - Decoded Instruction
    ins = upf("<HBQBQBQ", code, addr - base_addr)
    if ins[0] == 0x14:                     # JMP
        return (True, [ins[2]], ins)
    if ins[0] in [0x15, 0x16, 0x17, 0x1b]: # JEQ, JNE, JA, JG
        return (True, [addr + 0x1d, ins[2]], ins)
    return (False, [addr + 0x1d], ins)

def disass_linear(vaddr, code):
    num_ins = len(code) // 0x1d
    return [decode(vaddr, code, vaddr + 0x1d * i) for i in range(num_ins)]

This usually does suffice, and works well as long as you don’t need to recover the control flow graph. Once you need it however you usually regret going the quick and easy way and think about how you can shoehorn CFG recovery into your tooling. To save you from regrets the next time around let’s throw together a small recursive disassembler. Not only is CFG recovery part of this algorithm but as added benefit disassembling will not fail due to embedded constant data.

from sortedcontainer import SortedDict

def disass_rec(vaddr, code, entry):
    todo = [entry]      # working set of basic block entry points
    insn = {}
    bbs = SortedDict()  # the recovered basic blocks
    while len(todo):
        cur = todo[0]   # take the first element from the working set
        todo = todo[1:]
        bbaddr = cur
        bb = []         # instructions in this basic block
        suc = []        # list of basic block successors

        # if we have not seen this virtual address yet a basic block starts here
        if cur not in insn:
            bbs[cur] = (suc, bb)
        # as long as we have unseen virtual addresses
        while cur not in insn:
            if cur < vaddr:
                # decode the instruction
                term, nxt, ins = decode(vaddr, code, cur)
                term, nxt, ins = True, [], f"INVALID / SEGFAULT"

            # place the instruction into the current basic block
            bb.append((cur, ins))
            # register the virtual address
            insn[cur] = bbaddr

            if term:
                # the instruction terminates the basic block

            # go to the next virtual address
            cur = nxt[0]
            # we hit a virtual address we have already seen
            # fetch the coresponding basic block address
            bbaddr = insn[cur]
            if cur == bbaddr:
                # we hit the first instruction of the block, so just mark it as successor

            # it is not the first instruction, so we want to split the basic block
            # fetch the basic block
            oldbb_suc, oldbb_ins = bbs[bbaddr]
            # gather the instructions with virtual address >= cur
            overlap = [*dropwhile(lambda x: x[0] < cur, oldbb_ins)]

            # get the virtual address of the basic block that we split off
            ovs = overlap[0][0]
            # update the instruction registry such that the instructions in the block
            # that is split off point to its basic block again
            for insaddr, _ in overlap:
                insn[insaddr] = ovs
            # register the split off basic block, steal the old blocks successor
            bbs[ovs] = (oldbb_suc, overlap)

            # remove the instructions we transfered from the old block
            del oldbb_ins[-len(overlap):]
            # update the old basic block
            bbs[bbaddr] = ([ovs], oldbb_ins)

            # make the split off block the successor to this basic block

    return bbs

An added benefit of recursive disassembling is that instrucitons don’t need to be aligned to a multiple of their size. There can be holes in the instruction stream faultering linear sweep algorithms that would be off after the hole.