Lune

POPL2026Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • EverCrypt: A Fast, Verified, Cross-Platform Cryptographic Provider cites Simple High-Level Code for Cryptographic Arithmetic - With Proofs, Without Compromises
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. miniF2F-Dafny: LLM-Guided Mathematical Theorem Proving via Auto-Active VerificationMantas Baksys, Stefan Zetzsche, Olivier Bouissou, Sean B HoldenICML 2026 · 2 citations

Builds on27

  1. Coverage-based Greybox Fuzzing as Markov ChainMarcel Böhme, Van-Thuan Pham, Abhik RoychoudhuryCCS 2016 · 1,026 citations
  2. 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
  3. Interaction trees: representing recursive and impure programs in CoqLi-yao Xia, Yannick Zakowski, Paul He, Chung-Kil Hur et al.POPL 2020 · 133 citations
  4. Incorrectness logicPeter W. O'HearnPOPL 2020 · 122 citations
  5. EverCrypt: A Fast, Verified, Cross-Platform Cryptographic ProviderJonathan Protzenko, Bryan Parno, Aymeric Fromherz, Chris Hawblitzel et al.S&P 2020 · 114 citations

Related papers

  1. Formal Foundations for Translational Separation Logic VerifiersThibault Dardinier, Michael Sammler, Gaurav Parthasarathy, Alexander J. Summers et al.POPL 2025 · 8 citations
  2. A Formalization of Core Why3 in CoqJoshua M. Cohen, Philip Johnson-FreydPOPL 2024 · 10 citations
  3. Generically Automating Separation Logic by Functors, Homomorphisms, and ModulesQiyuan Xu, David Sanán, Zhe Hou, Xiaokun Luan et al.POPL 2025
  4. DimSum: A Decentralized Approach to Multi-language Semantics and VerificationMichael Sammler, Simon Spies, Youngju Song, Emanuele D'Osualdo et al.POPL 2023 · 18 citations
  5. Generating Proof Certificates for a Language-Agnostic Deductive Program VerifierZhengyao Lin, Xiaohong Chen, Minh-Thai Trinh, John Wang et al.OOPSLA 2023 · 12 citations
Dusk over the sea between two cliffs drawn in fine vertical lines