Foundational Multi-Modal Program Verifiers
Proceedings of the ACM on Programming Languages · 08.01.2026 · 10 (POPL) · 2233-2264
DOI: 10.1145/3776719 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 08.01.2026. Verfasst von Vladimir Gladshtein und 4 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 115 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Singapore Ministry of Education.
Abstract (Originalsprache)
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 machine-assisted 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.
Förderung
- Singapore Ministry of Education
Zitieren
APA
Gladshtein, V., Pîrlea, G., Zhao, Q., Kurin, V., & Sergey, I. (2026). Foundational Multi-Modal Program Verifiers. Proceedings of the ACM on Programming Languages, 10(POPL), 2233-2264. https://doi.org/10.1145/3776719
Vancouver
Gladshtein V, Pîrlea G, Zhao Q, Kurin V, Sergey I. Foundational Multi-Modal Program Verifiers. Proceedings of the ACM on Programming Languages. 2026;10(POPL):2233-2264. doi:10.1145/3776719
BibTeX
@article{Gladshtein2026,
author = {Gladshtein, Vladimir and Pîrlea, George and Zhao, Qiyuan and Kurin, Vitaly and Sergey, Ilya},
title = {Foundational Multi-Modal Program Verifiers},
journal = {Proceedings of the ACM on Programming Languages},
year = {2026},
volume = {10},
number = {POPL},
pages = {2233--2264},
doi = {10.1145/3776719}
}
EUVIMED