A Program Logic for First-Order Encapsulated WebAssembly
Preprint
Abstract
We introduce Wasm Logic, a sound program logic for first-order, encapsulated WebAssembly. We design a novel assertion syntax, tailored to WebAssembly's stack-based semantics and the strong guarantees given by WebAssembly's type system, and show how to adapt the standard separation logic triple and proof rules in a principled way to capture WebAssembly's uncommon structured control flow. Using Wasm Logic, we specify and verify a simple WebAssembly B-tree library, giving abstract specifications independent of the underlying implementation. We mechanise Wasm Logic and its soundness proof in full in Isabelle/HOL. As part of the soundness proof, we formalise and fully mechanise a novel, big-step semantics of WebAssembly, which we prove equivalent, up to transitive closure, to the original WebAssembly small-step semantics. Wasm Logic is the first program logic for WebAssembly, and represents a first step towards the creation of static analysis tools for WebAssembly.Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- The Essence of Higher-Order Concurrent Separation Logic2017
- Higher-Order Separation Logic in Isabelle/HOLCFElectronic Notes in Theoretical Computer Science, 2008
- Proof-Transforming Compilation of Eiffel Programs2008
- A Compositional Natural Semantics and Hoare Logic for Low-Level LanguagesElectronic Notes in Theoretical Computer Science, 2006
- A Bytecode Logic for JML and TypesLecture Notes in Computer Science, 2006
- A Program Logic for BytecodeElectronic Notes in Theoretical Computer Science, 2005
- A Typed, Compositional Logic for a Stack-Based Abstract Machine2005
- A Compositional Logic for Control FlowLecture Notes in Computer Science, 2005
- Goto statements: semantics and deduction systemsActa Informatica, 1981
- Program proving: Jumps and functionsActa Informatica, 1972