Blogs / Control-flow recovery

Recovering Jump Tables from x86-64 ELF

An indirect jump does not encode its destination in the instruction. To recover a switch, HydIR must connect the jump's addressing expression to bytes or relocations in a table, then justify each target as executable code within the selected function. Two checked-in fixtures show both routes: an absolute pointer table in a linked ELF and a relative table in an unlinked object.

The control-flow problem

A direct branch carries an encoded destination. An instruction such as jmp qword ptr [rdi * 8 + jump_targets] instead reads a destination from memory. Recursive decoding can follow the preceding comparison and the branch to the default case, but without table recovery it stops at that indirect jump. The case blocks might be present elsewhere in .text; their mere proximity does not prove that the jump can reach them.

The fixtures implement the same broad pattern. A 32-bit unsigned comparison routes out-of-range inputs to a default return of zero. In-range inputs select a table entry and return 10, 20, 30, or (in the relative fixture) 40. The ja guard is an unsigned “above” test, so a negative signed value in EDI also takes the default path when viewed as an unsigned 32-bit index. HydIR records the machine-level guard and target evidence rather than assuming a recovered source-language switch.

Case one: a linked table of absolute pointers

The absolute-table fixture contains this dispatch:

table_dispatch:
    cmp edi, 2
    ja .Ldefault
    jmp qword ptr [rdi * 8 + jump_targets]

jump_targets:
    .quad .Lcase0
    .quad .Lcase1
    .quad .Lcase2

In the checked-in linked ELF, table_dispatch begins at 0x201214 and its symbol and unwind records both give a 33-byte extent. The indirect jump is at 0x201219. Its decoded operand has an eight-byte scale and a table displacement of 0x2001b0. ProgramSpec maps that virtual table address to file offset 0x1b0; the table occupies 24 bytes of .rodata.

For this indexed memory operand, HydIR reads consecutive 64-bit little-endian entries, subject to a 256-entry cap. A candidate must land in executable text and inside the selected function extent. Recovery stops at the first unreadable or out-of-scope slot; it does not skip over a gap and resume at a convenient later value. At least two valid entries are required before an indexed pointer table is accepted as table evidence. These constraints keep adjacent data or an unrelated function from becoming a case merely because its bytes resemble an address.

The resulting MachineIR retains the original jmp bytes, ff24fdb0012000, and adds three indirect_target edges. The branch at 0x201217 still has its separate taken edge to the default block at 0x201232 and fallthrough edge to the indirect jump. The recovered paths are:

The evidence required for one edge

For a linked pointer table, four checks support each indirect_target edge. First, the decoded operand must match a supported table-addressing form; an arbitrary memory expression is not sufficient. Second, HydIR must identify a bounded table base from a mapped address or a proven constant register. Third, it must read a consecutive slot from file-backed data or resolve that slot from relocation evidence. Fourth, the resulting address must belong to executable text and to the selected function's extent. Failing any check leaves the jump unresolved instead of manufacturing an edge.

The linked fixture's recovered jump can be inspected directly in MachineIR. This abridged JSON retains the dispatch address and all three target edges:

{
  "address": {"address_space": 0, "value": "0x0000000000201219"},
  "mnemonic": "jmp",
  "bytes_hex": "ff24fdb0012000",
  "edges": [
    {"kind": "indirect_target", "target": {"address_space": 0, "value": "0x0000000000201220"}},
    {"kind": "indirect_target", "target": {"address_space": 0, "value": "0x0000000000201226"}},
    {"kind": "indirect_target", "target": {"address_space": 0, "value": "0x000000000020122c"}}
  ]
}

The bounded_indirect_targets diagnostic reports three in-function targets across one indirect site. The index's candidate_targets list contains the same three case entries, while the function's symbol and unwind evidence remain separate. In particular, the table entries are CFG destinations inside table_dispatch; they are not three newly discovered functions.

Case two: a relocatable table of signed offsets

The relative-table fixture is an ELF relocatable object (ET_REL). Its dispatch computes a destination rather than loading a full pointer:

relative_table_dispatch:
    cmp edi, 3
    ja .Ldefault
    lea rax, [rip + .Ltable]
    movsxd rcx, dword ptr [rax + rdi * 4]
    add rcx, rax
    jmp rcx

.Ltable:
    .long .Lcase0 - .Ltable
    .long .Lcase1 - .Ltable
    .long .Lcase2 - .Ltable
    .long .Lcase3 - .Ltable

movsxd sign-extends a 32-bit table value. Adding the table base converts that signed relative value into a code target. An ET_REL file has not been assigned final process addresses: in HydIR's ProgramSpec, .text uses address space 2 and .rodata uses address space 4. The dispatch starts at (2, 0x0); the table starts at (4, 0x0). Treating both zero offsets as the same virtual address would be incorrect.

The encoded lea instruction at (2, 0x5) contains a linker placeholder, not a finalized displacement. A 32-bit PC-relative relocation at (2, 0x8) identifies the .rodata base. Each four-byte table slot has its own PC-relative relocation toward .text. HydIR verifies the contiguous lea → movsxd → add → register jmp pattern, resolves the table base from the instruction relocation, and interprets the slot relocations in their section address spaces. It does not infer targets from placeholder bytes.

For this fixture, the slot relocations refer to the start of .text and carry addends 21, 31, 41, and 51. The target offset for slot i is the relocation target base plus its addend minus the slot's 4i offset. The resulting calculation is directly checkable:

The arithmetic above is section-relative. The relocation target is (2, 0x0), and each slot is (4, 4i); the calculation yields an offset in address space 2, not a finalized virtual address. Reading the four raw 32-bit slot words as if they were already linked would lose the symbol and addend information that makes those destinations meaningful. The instruction relocation at (2, 0x8) is equally necessary: without it, the lea placeholder does not identify the table's address space or base.

Each target must remain in the 48-byte function extent and in executable text. Recovery stops at the first missing, invalid, or out-of-scope relocation and accepts at most 256 consecutive slots. MachineIR for the jmp rcx at (2, 0x13) consequently contains four indirect_target edges to (2, 0x15), (2, 0x1b), (2, 0x21), and (2, 0x27). The ja at (2, 0x3) separately reaches the default return at (2, 0x2d).

Why recovery iterates

An initial recursive pass reaches the indirect jump but cannot follow its cases until table evidence has supplied targets. HydIR collects bounded targets for recovered indirect sites, decodes the newly reachable blocks, and repeats when those blocks expose more control flow. The process has an explicit 32-pass limit and retains diagnostics for any unresolved outcome. The FunctionIndex keeps candidate targets as evidence; a candidate is not automatically promoted into a new function or an exact source-level case mapping.

This distinction matters for both examples. The graph now contains the case bodies, but table recovery by itself does not prove that the preceding guard admits exactly those indices under every machine-state condition. It also does not solve arbitrary register value sets or every compiler's table encoding. HydIR records the discovered destinations and preserves the remaining uncertainty.

The unresolved switch default survives C emission

CIR represents the linked dispatch at 0x201219 as a switch terminator with three target addresses and unresolved_default: true. The relative fixture has the same terminator shape with four targets at (2, 0x13). The relevant linked CIR fields are:

{
  "kind": "switch",
  "dispatch": {"address_space": 0, "value": "0x0000000000201219"},
  "targets": [
    {"address_space": 0, "value": "0x0000000000201220"},
    {"address_space": 0, "value": "0x0000000000201226"},
    {"address_space": 0, "value": "0x000000000020122c"}
  ],
  "unresolved_default": true
}

The generated switch is over an indirect target expression, not a claimed reconstruction of the original source expression switch (edi). A shortened excerpt from the linked fixture's low-level C shows the distinction:

switch (hydir_indirect_target(state, UINT64_C(0x201219))) {
  case UINT64_C(0x201220): goto case_0;
  case UINT64_C(0x201226): goto case_1;
  case UINT64_C(0x20122c): goto case_2;
  default:
    hydir_unknown_control(state, UINT64_C(0));
    return;
}

The labels above abbreviate the generated block labels; the cases, target addresses, and unknown-control branch reflect the emitted artifact. The actual assembly's out-of-range branch to .Ldefault is a separate, known CFG edge. The switch's unresolved default is about the indirect jump if it produces an address outside the recovered target set. Collapsing those two defaults would claim a proof the analysis has not made.

For these checked-in artifacts, the reported status is deliberately split into independent claims:

complete describes the recovered graph within the selected function boundary. It does not erase the CIR switch's unresolved_default or upgrade conservative semantic fidelity. Static validation checks artifact structure; it is distinct from a differential execution test. Successful C compilation checks the generated C and its helper contract, but does not prove that an arbitrary input can only select the enumerated cases or authorize a binary rewrite.

Reproduce the analysis

These commands inspect the exact checked-in fixtures without executing them. Run them from the repository root with the pinned Rust toolchain:

cargo run --locked --bin hydirctl -- discover fuzz/corpus/elf_import/jump_table.elf
cargo run --locked --bin hydirctl -- lift fuzz/corpus/elf_import/jump_table.elf --function table_dispatch --ir machine
cargo run --locked --bin hydirctl -- lift fuzz/corpus/elf_import/jump_table.elf --function table_dispatch --ir cir
cargo run --locked --bin hydirctl -- decompile fuzz/corpus/elf_import/jump_table.elf --function table_dispatch --view unit

cargo run --locked --bin hydirctl -- inspect fuzz/corpus/elf_import/relative_jump_table.o
cargo run --locked --bin hydirctl -- lift fuzz/corpus/elf_import/relative_jump_table.o --function relative_table_dispatch --ir machine
cargo run --locked --bin hydirctl -- decompile fuzz/corpus/elf_import/relative_jump_table.o --function relative_table_dispatch --view unit

In the MachineIR JSON, inspect the edges on each indirect jmp and the bounded_indirect_targets diagnostic. In the CIR JSON, inspect the switch terminator's targets and unresolved_default fields. In the unit, compare structural_completeness, semantic_fidelity, verification, and rewrite_ready independently. The Linux native fixture gate also runs discovery, coverage, batch C emission, deterministic re-emission, and strict C compilation across the broader pinned corpus.

Jump-table recovery is useful because it makes previously unreachable case blocks inspectable. Its output remains a bounded set of justified targets with an explicit unknown remainder, which is the appropriate contract for further analysis.