N-Version Disassembly

Definition

N-Version Disassembly is a software-testing technique introduced by Paleari, Martignoni, Fresi Roglia, and Bruschi in their 2010 paper "N-version disassembly" (ACM, pages 265–274, DOI 10.1145/1831708.1831741). It applies the concept of N-Version Programming — running multiple independent implementations of the same functionality on a common input and comparing their outputs — to the domain of binary disassembly.

In the N-Version Disassembly approach, several disassemblers are treated as redundant implementations of a (typically underspecified) specification, namely the x86 / x86-64 instruction-set specification. Because no single decoder can be assumed to be a perfect oracle, disagreements between decoders are treated as evidence that at least one of them has produced an incorrect result, allowing bugs and undocumented or ambiguous instruction-encoding behaviors to be surfaced without a hardware ground truth.

Relationship to differential fuzzing of x86-64 instruction decoders

The 2021 paper "Differential analysis of x86-64 instruction decoders" by Woodruff, Carroll, and Peters (which introduces the MISHEGOS differential fuzzer) cites Paleari et al.'s "N-version disassembly" (2010) directly in its references.

MISHEGOS extends the N-Version Disassembly idea by:

Automating input generation via coverage-guided differential fuzzing, producing hundreds of millions of decoder tests per hour on modest hardware, rather than relying on manually assembled test suites.
Adding a sliding-window strategy over an over-approximated model of machine instructions to handle variable-length x86-64 encoding, which produces inputs that probe instruction-boundary edge cases.
Providing an extensible analytical framework that lets users inspect results either to find bugs in a single decoder or to study discrepancies among many decoders.

In this sense, MISHEGOS can be viewed as an evolved, fuzzing-driven instance of the N-Version Disassembly principle applied to modern x86-64 instruction decoders.

Related prior work cited alongside N-Version Disassembly

In the same 2021 paper, N-Version Disassembly is grouped with other differential-testing precedents:

McKeeman (1998), Differential Testing for Software — the foundational differential-testing paper.
Jay and Miller (2018), Structured random differential testing of instruction decoders — also applies multiple-decoder comparison to instruction decoders and is cited alongside N-Version Disassembly as closely related prior art.
Miller, Fredriksen, and So (1990), An empirical study of the reliability of UNIX utilities — the original differential / random-testing study.

Limitations and considerations

Because N-Version Disassembly identifies bugs via inter-decoder disagreement, it cannot detect bugs that are present symmetrically in every decoder under test. The MISHEGOS authors address this by using a large, diverse corpus of decoders, but the fundamental limitation — that no decoder is guaranteed to be a correct oracle — is inherited directly from the N-Version Disassembly formulation.

Key reference

Roberto Paleari, Lorenzo Martignoni, Giampaolo Fresi Roglia, Danilo Bruschi. N-version disassembly. 2010, pages 265–274. DOI: 10.1145/1831708.1831741.