Foundational Multi-Modal Program Verifiers
Vladimir Gladshtein, George Pîrlea, Qiyuan Zhao, Vitaly Kurin, Ilya Sergey
Abstract
Multi-modal program verification is a process of validating code against its specification using both dynamic and symbolic techniques, and proving its correctness by a combination of automated and interactive machineassisted tools. In order to be trustworthy, such verification tools must themselves come with formal soundness proofs, establishing that any program verified in them against a certain specification does not violate the specification's statement when executed. Verification tools that are proven sound in a general-purpose proof assistant with a small trusted core are commonly referred to as foundational.
We present a framework that facilitates and streamlines construction of program verifiers that are both foundational and multi-modal. Our approach adopts the well-known idea of monadic shallow embedding of an executable program semantics into the programming language of a theorem prover based on higher-order logic, in our case, the Lean proof assistant. We provide a library of monad transformers for such semantics, encoding a variety of computational effects, including state, divergence, exceptions, and non-determinism.
The key theoretical innovation of our work are monad transformer algebras that enable automated derivation of the respective sound verification condition generators. We show that proofs of the resulting verification conditions enjoy automation using off-the-shelf SMT solvers and allow for an interactive proof mode when automation fails. To demonstrate versatility of our framework, we instantiated it to embed two foundational multi-modal verifiers into Lean for reasoning about (1) distributed protocol safety and (2) Dafny-style specifications of imperative programs, and used them to mechanically verify a number of non-trivial case studies.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers1
Builds on27
- Coverage-based Greybox Fuzzing as Markov ChainMarcel Böhme, Van-Thuan Pham, Abhik RoychoudhuryCCS 2016 · 1,026 citations
- Simple High-Level Code for Cryptographic Arithmetic - With Proofs, Without CompromisesAndres Erbsen, Jade Philipoom, Jason Gross, Robert Sloan et al.S&P 2019 · 147 citations
- Interaction trees: representing recursive and impure programs in CoqLi-yao Xia, Yannick Zakowski, Paul He, Chung-Kil Hur et al.POPL 2020 · 133 citations
- Incorrectness logicPeter W. O'HearnPOPL 2020 · 122 citations
- EverCrypt: A Fast, Verified, Cross-Platform Cryptographic ProviderJonathan Protzenko, Bryan Parno, Aymeric Fromherz, Chris Hawblitzel et al.S&P 2020 · 114 citations
Related papers
- Formal Foundations for Translational Separation Logic VerifiersThibault Dardinier, Michael Sammler, Gaurav Parthasarathy, Alexander J. Summers et al.POPL 2025 · 8 citations
- A Formalization of Core Why3 in CoqJoshua M. Cohen, Philip Johnson-FreydPOPL 2024 · 10 citations
- Generically Automating Separation Logic by Functors, Homomorphisms, and ModulesQiyuan Xu, David Sanán, Zhe Hou, Xiaokun Luan et al.POPL 2025
- DimSum: A Decentralized Approach to Multi-language Semantics and VerificationMichael Sammler, Simon Spies, Youngju Song, Emanuele D'Osualdo et al.POPL 2023 · 18 citations
- Generating Proof Certificates for a Language-Agnostic Deductive Program VerifierZhengyao Lin, Xiaohong Chen, Minh-Thai Trinh, John Wang et al.OOPSLA 2023 · 12 citations
