EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Foundational Multi-Modal Program Verifiers

Vladimir Gladshtein, George Pîrlea, Qiyuan Zhao, Vitaly Kurin, Ilya Sergey

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →