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
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.
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.
External (65)
- Scaling instruction-selection verification against authoritative ISA semantics (artifact) (2025)
- RGFuzz: Rule-Guided Fuzzer for WebAssembly Runtimes (2025)
- Wasmtime: a fast and secure runtime for WebAssembly (2025)
- SpecTec update and poll (2025)
- Lift-Offline: Instruction Lifter Generators (2024)
- Hydride: A Retargetable and Extensible Synthesis-based Compiler for Modern Hardware Architectures (2024)
- Translation Validation for JIT Compiler in the V8 JavaScript Engine (2024)
- Hydra: Generalizing Peephole Optimizations with Program Synthesis (2024)
- Icarus: Trustworthy Just-In-Time Compilers with Symbolic Meta-Execution (2024)
- Lightweight, Modular Verification for WebAssembly-to-Native Instruction Selection (2024)
- Bringing the WebAssembly Standard up to Speed with SpecTec (2024)
- aslp: partial evaluator for Arm's Architecture Specification Language (2024)
- Projects using K (2024)
- Sail RISC-V model (2024)
- Introduction to the Go compiler's SSA backend (2024)
- ASL to Sail translation tool (2024)
- JIT integer optimization peephole rule DSL (2024)
- JIT integer optimization peephole rules (2024)
- Crocus: an SMT-based ISLE verification tool (2024)
- ISLE language reference (2024)
- X64 fixed select + load floating point wrong lowering (Wasmtime issue 8112) (2024)
- ACL2-to-Sail translator and the resulting Sail x86 ISA model (2024)
- Engineering large multipurpose microprocessor specifications (using the x86-64 architecture as a case study) (2024)
- SMT-LIB Reals theory (2024)
- SMT-LIB FloatingPoint theory (2024)
- Tiers of support in Wasmtime (2024)
- WaVe: a verifiably secure WebAssembly sandboxing runtime (2023)
- Lift-off: trustworthy ARMv8 semantics from formal specifications (2023)
- Iris-Wasm: Robust and Modular Verification of WebAssembly Programs (2023)
- Guest-controlled out-of-bounds read/write on x86_64 (Wasmtime security advisory) (2023)
- cvc5: A Versatile and Industrial-Strength SMT Solver (2022)
- Formally Verified Native Code Generation in an Effectful JIT: Turning the CompCert Backend into a Formally Verified JIT Compiler (2022)
- EXAMINER: automatically locating inconsistent instructions between real devices and CPU emulators for ARM (2022)
- Taming an Authoritative Armv8 ISA Specification: L3 Validation and CakeML Compiler Verification (2022)
- Islaris: verification of machine code against authoritative ISA semantics (2022)
- Provably-safe multilingual software sandboxing using WebAssembly (2022)
- Isla: Integrating Full-Scale ISA Semantics and Axiomatic Concurrency Models (2021)
- Доверя'й, но проверя'й: SFI safety for native-compiled Wasm (2021)
- Alive2: bounded translation validation for LLVM (2021)
- RFC: design of ISLE instruction-selector DSL (2021)
- Towards a verified range analysis for JavaScript JITs (2020)
- Specification and verification in the field: applying formal methods to BPF just-in-time compilers in the Linux kernel (2020)
- ISA semantics for ARMv8-a, RISC-v, and CHERI-MIPS (2019)
- A complete formal semantics of x86-64 user-level instruction set architecture (2019)
- WebAssembly core specification (2019)
- Mechanising and verifying the WebAssembly specification (2018)
- Engineering a Formal, Executable x86 ISA Simulator for Software Verification (2017)
- Bringing the web up to speed with WebAssembly (2017)
- Vale: verifying high-performance cryptographic assembly code (2017)
- Encoding of immediate values on AArch64 (2017)
- XSat: A Fast Floating-Point Satisfiability Solver (2016)
- Trustworthy specifications of ARM® v8-A and v8-M system level architecture (2016)
- End-to-end verification of ARM processors with ISA-Formal (2016)
- An Automatable Formal Semantics for IEEE-754 Floating-Point Arithmetic (2015)
- Provably correct peephole optimizations with alive (2015)
- Compositional CompCert (2015)
- Halide: a language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines (2013)
- Automatically generating instruction selectors using declarative machine descriptions (2010)
- Intro to the LLVM MC project (2010)
- Beaver: Engineering an Efficient SMT Solver for Bit-Vector Arithmetic (2009)
- Z3: An Efficient SMT Solver (2008)
- C Compiler Retargeting Based on Instruction Semantics Models (2005)
- Generating machine specific optimizing compilers (1996)
- Efficient software-based fault isolation (1994)
- Automatic Derivation of Code Generators from Machine Descriptions (1980)