Reference. Scaling Instruction-Selection Verification against Authoritative ISA Semantics

Secure, performant execution of untrusted code—as promised by WebAssembly (Wasm)—requires correct compilation to native code that enforces a sandbox. Errors in instruction selection can undermine the sandbox’s guarantees, but prior verification work struggles to scale to the complexity of realistic industrial compilers. We present Arrival , an instruction-selection verifier for the Cranelift production Wasm-to-native compiler. Arrival enables end-to-end, high-assurance verification while reducing developer effort. Arrival ( 1 ) automatically reasons about chains of instruction-selection rules, thereby reducing the need for develop-er-supplied intermediate specifications, ( 2 ) introduces a lightweight, efficient method for reasoning about stateful instruction-selection rules, and ( 3 ) automatically derives high-assurance machine code specifications. Our work verifies nearly all AArch64 instruction-selection rules reachable from Wasm core. Furthermore, Arrival reduces the developer effort required: 60 % of all specifications benefit from our automation, thereby requiring 2.6 × fewer hand-written specifications than prior approaches. Arrival finds new bugs in Cranelift’s instruction selection, and it is viable for integration into production workflows.

Cite

Cite as @mcloughlin-2025-scaling (helia, typst) · \cite{mcloughlin-2025-scaling} (LaTeX)
BibTeX
bibtex · 1 line
@article{mcloughlin-2025-scaling, title={Scaling Instruction-Selection Verification against Authoritative ISA Semantics}, volume={9}, ISSN={2475-1421}, url={http://dx.doi.org/10.1145/3764383}, DOI={10.1145/3764383}, number={OOPSLA2}, journal={Proceedings of the ACM on Programming Languages}, publisher={Association for Computing Machinery (ACM)}, author={McLoughlin, Michael and Sheng, Ashley and Fallin, Chris and Parno, Bryan and Brown, Fraser and VanHattum, Alexa}, year={2025}, month=Oct, pages={4064–4090} }
hayagriva YAML (typst)
yaml · 22 lines
mcloughlin-2025-scaling:
  type: article
  title: Scaling Instruction-Selection Verification against Authoritative ISA Semantics
  author:
  - McLoughlin, Michael
  - Sheng, Ashley
  - Fallin, Chris
  - Parno, Bryan
  - Brown, Fraser
  - VanHattum, Alexa
  date: 2025-10
  page-range: 4064-4090
  url: http://dx.doi.org/10.1145/3764383
  serial-number:
    doi: 10.1145/3764383
    issn: 2475-1421
  parent:
    type: periodical
    title: Proceedings of the ACM on Programming Languages
    publisher: Association for Computing Machinery (ACM)
    issue: OOPSLA2
    volume: 9
Cites 67 works (2 here)
With notes (2)

CakeML: A verified implementation of ML kumar_cakeml_2014

We have developed and mechanically verified an ML system called CakeML, which supports a substantial subset of Standard ML. CakeML is implemented as an interactive read-eval-print loop (REPL) in x86-64 machine code. Our correctness theorem ensures that this REPL implementation prints only those results permitted by the semantics of CakeML. Our verification effort touches on a breadth of topics including lexing, parsing, type checking, incremental and dynamic compilation, garbage collection, arbitraryprecision arithmetic, and compiler bootstrapping.
PDF · DOI · pldb

Formal verification of a realistic compiler leroy_formal_2009

This paper reports on the development and formal verification (proof of semantic preservation) of CompCert, a compiler from Clight (a large subset of the C programming language) to PowerPC assembly code, using the Coq proof assistant both for programming the compiler and for proving its correctness. Such a verified compiler is useful in the context of critical software and its formal verification: the verification of the compiler guarantees that the safety properties proved on the source code hold for the executable compiled code as well.
DOI
External (65)
mcloughlin-2025-scaling reference entries/refs/mcloughlin-2025-scaling/mcloughlin-2025-scaling.hel