Compiling by Proving in \({\mathbb{K}}\) : From All-Path Reachability Proofs to Single-Step Semantic Rules
Open Access
- 28 July 2026
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Software Engineering and Methodology
Abstract
The \({\mathbb{K}}\) framework generates language tools from formal semantics and hosts comprehensive semantics for real-world languages including C, Java, JavaScript, and the Ethereum Virtual Machine, with industrial adoption in blockchain verification. However, the generated executors interpret programs by applying semantic rules step by step, causing performance overhead that limits practical scalability. We present compiling by proving , a language-agnostic mechanism that eliminates this overhead. Given a code unit, we use symbolic execution to prove that its specification holds across all execution paths, generating a proof graph that encodes the complete input-output behavior. We compile this proof graph into a single-step rule that directly maps inputs to outputs, replacing step-by-step interpretation with one-step execution. Because the pipeline is language-agnostic, it benefits any language formalized in \({\mathbb{K}}\) . We evaluate on EVM and Rust MIR semantics, showing speedups in concrete and symbolic execution, and demonstrate applications to semantic equivalence verification and compositional smart contract verification.
Keywords
This publication has 55 references indexed in Scilit:
- Towards a Trustworthy Semantics-Based Language Framework via Proof Generation2021
- Matching logic explainedJournal of Logical and Algebraic Methods in Programming, 2021
- All-Path Reachability Logic2014
- Why3 — Where Programs Meet Provers2013
- Dafny: An Automatic Program Verifier for Functional Correctness2010
- Demand-Driven Compositional Symbolic Execution2008
- Boogie: A Modular Reusable Verifier for Object-Oriented Programs2006
- Efficient weakest preconditionsInformation Processing Letters, 2005
- Local Reasoning about Programs that Alter Data Structures2001
- Translation validation1998