Static disassembly has to answer one question before it can do anything: where does each instruction begin? On x86 the byte stream is ambiguous, the same byte can be data, an opcode, or an operand, so the disassembler guesses.
The guess is usually right and sometimes wrong, and when it is wrong the standard fix is a runtime fallback: a JIT that re-translates on the fly. You have quietly put an emulator in your trusted computing base to cover for a guess.
Don't guess. Enumerate.
A recent tool, Elevator, refuses the guess. Instead of choosing one interpretation of each byte, it works the whole problem ahead of time:
- consider every feasible reading of each byte: data, opcode, operand;
- emit a translation for each;
- prune only the paths that provably crash.
The output is one fully static x86-64-to-AArch64 binary, no heuristics and no runtime component, on the entire SPECint suite, at performance on par with QEMU's JIT.
A heuristic is a guess you decided to trust because enumerating the truth looked too expensive.
What you buy by not guessing
It is not speed. It is a trusted base small enough to certify. With no JIT in the loop, the translation is a static artifact you can validate, sign, and ship, which is the same property that makes a hardware-anchored attestation mean anything: the thing that runs is the thing you signed, not whatever a runtime decided to assemble.
A heuristic-plus-fallback design can only ever be monitored. A deterministic one can be verified before it ships. That is the difference between a guess and an oracle, in the one place you least want to be guessing.
| Heuristic + fallback | Deterministic enumeration | |
|---|---|---|
| A wrong guess | a runtime JIT re-translates on the fly | cannot happen; every reading was emitted ahead of time |
| Trusted base | includes an emulator | one static binary |
| Assurance | can only be monitored | verified and signed before it ships |
| The cost | paid later, in trust | paid upfront, in code size |
It is not free
Enumerating every feasible interpretation blows up code size, sometimes a lot. That is the honest shape of soundness: the cost does not vanish, it relocates, here out of runtime risk and into static bytes. Same trade as building any real checker, paid upfront, in space, so you stop paying later, in trust.
The general version
Past binaries, the shape recurs. A heuristic is a loan against correctness. It is cheap today, because guessing is cheaper than knowing, and you repay it the day the guess is wrong, with interest, in the form of a runtime you now have to trust and watch.
Determinism pays the principal upfront and walks away with something it can sign instead of something it must monitor. The disassembly was always a guessed surface laid over the real bytes; Elevator throws out the surface and keeps the territory, all of it, enumerated.
Most systems take the loan, and often that is the right call. It is worth knowing, each time, that you took one.
Disassembly has to answer one question first: where does each instruction start? On x86 the bytes are ambiguous, the same byte can be data, an opcode, or an operand, so the disassembler guesses.
The guess is usually right. When it is wrong, the standard fix is a runtime fallback, a JIT that re-translates on the fly. So to cover a guess, you have put an emulator in your trusted base.
Elevator doesn't guess
A recent tool, Elevator, enumerates instead. Ahead of time, it:
- considers every feasible reading of each byte (data, opcode, operand);
- emits a translation for each;
- throws out only the paths that provably crash.
The result is one fully static x86-64-to-AArch64 binary, no heuristics, no runtime, on all of SPECint, at QEMU-JIT speed.
What you get
Not speed. A trusted base small enough to certify. With no JIT in the loop, the output is a static artifact you can validate, sign, and ship: the thing that runs is the thing you signed.
A heuristic-plus-fallback design can only be monitored. A deterministic one can be verified before it ships.
The cost
Enumerating everything blows up code size, sometimes a lot. That is the honest shape of soundness: the cost does not vanish, it moves, out of runtime trust and into static bytes. You pay upfront, in space, so you stop paying later, in trust.
The general rule
A heuristic is a loan against correctness. Cheap today, because guessing is cheaper than knowing. You repay it the day the guess is wrong, with interest: a runtime you now have to trust and watch. Determinism pays the principal upfront.
A heuristic is a loan against correctness, repaid the day the guess is wrong, with interest.
Most systems take the loan, and often that is the right call. Just know, each time, that you took one.
Source
- Hongyu Chen, James McGowan, Michael Franz, "Deterministic Fully-Static Whole-Binary Translation without Heuristics" (Elevator), arXiv:2605.08419: considers every feasible interpretation of each byte ahead of time, ships a static, runtime-free, signable binary, at the cost of code-size expansion.