Lune

POPL2024Top-tier venue

A Formalization of Core Why3 in Coq

Joshua M. Cohen, Philip Johnson-Freyd

Abstract

Intermediate verification languages like Why3 and Boogie have made it much easier to build program verifiers, transforming the process into a logic compilation problem rather than a proof automation one. Why3 in particular implements a rich logic for program specification with polymorphism, algebraic data types, recursive functions and predicates, and inductive predicates; it translates this logic to over a dozen solvers and proof assistants. Accordingly, it serves as a backend for many tools, including Frama-C, EasyCrypt, and GNATProve for Ada SPARK. But how can we be sure that these tools are correct? The alternate foundational approach, taken by tools like VST and CakeML, provides strong guarantees by implementing the entire toolchain in a proof assistant, but these tools are harder to build and cannot directly take advantage of SMT solver automation. As a first step toward enabling automated tools with similar foundational guarantees, we give a formal semantics in Coq for the logic fragment of Why3. We show that our semantics are useful by giving a correct-by-construction natural deduction proof system for this logic, using this proof system to verify parts of Why3’s standard library, and proving sound two of Why3’s transformations used to convert terms and formulas into the simpler logics supported by the backend solvers.

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.

5 top-tier papers have 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

  • Towards Trustworthy Automated Program Verifiers: Formally Validating Translations into an Intermediate Verification Language cites Formally Validating a Practical Verification Condition Generator
  • RefinedC: automating the foundational verification of C code with refined ownership types cites VST-A: A Foundationally Sound Annotation Verifier
  • VST-A: A Foundationally Sound Annotation Verifier cites RefinedC: automating the foundational verification of C code with refined ownership types
  • Formal Foundations for Translational Separation Logic Verifiers cites Towards Trustworthy Automated Program Verifiers: Formally Validating Translations into an Intermediate Verification Language
  • Formal Foundations for Translational Separation Logic Verifiers cites RefinedC: automating the foundational verification of C code with refined ownership types
  • Formal Foundations for Translational Separation Logic Verifiers cites Formally Validating a Practical Verification Condition Generator
  • Sound State Encodings in Translational Separation Logic Verifiers cites Towards Trustworthy Automated Program Verifiers: Formally Validating Translations into an Intermediate Verification Language
  • Sound State Encodings in Translational Separation Logic Verifiers cites Formal Foundations for Translational Separation Logic Verifiers
  • Sound State Encodings in Translational Separation Logic Verifiers cites Compositional Symbolic Execution for the Next 700 Memory Models
  • Sound State Encodings in Translational Separation Logic Verifiers cites Formally Validating a Practical Verification Condition Generator
  • Compositional Symbolic Execution for the Next 700 Memory Models cites Towards Trustworthy Automated Program Verifiers: Formally Validating Translations into an Intermediate Verification Language
  • Compositional Symbolic Execution for the Next 700 Memory Models cites Formal Foundations for Translational Separation Logic Verifiers
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers5

  1. VST-A: A Foundationally Sound Annotation VerifierLitao Zhou, Jianxing Qin, Qinshi Wang, Andrew W. Appel et al.POPL 2024 · 12 citations
  2. Formal Foundations for Translational Separation Logic VerifiersThibault Dardinier, Michael Sammler, Gaurav Parthasarathy, Alexander J. Summers et al.POPL 2025 · 8 citations
  3. Towards Trustworthy Automated Program Verifiers: Formally Validating Translations into an Intermediate Verification LanguageGaurav Parthasarathy, Thibault Dardinier, Benjamin Bonneau, Peter Müller et al.PLDI 2024 · 6 citations
  4. Compositional Symbolic Execution for the Next 700 Memory ModelsAndreas Lööw, Seung Hoon Park, Daniele Nantes-Sobrinho, Sacha-Élie Ayoun et al.OOPSLA 2025 · 4 citations
  5. Sound State Encodings in Translational Separation Logic VerifiersHongyi Ling, Thibault Dardinier, Ellen Arlt, Peter MüllerOOPSLA 2026

Builds on4

  1. RefinedC: automating the foundational verification of C code with refined ownership typesMichael Sammler, Rodolphe Lepigre, Robbert Krebbers, Kayvan Memarian et al.PLDI 2021 · 83 citations
  2. Integration verification across software and hardware for a simple embedded systemAndres Erbsen, Samuel Gruetter, Joonwon Choi, Clark Wood et al.PLDI 2021 · 29 citations
  3. Formally Validating a Practical Verification Condition GeneratorGaurav Parthasarathy, Peter Müller, Alexander J. SummersCAV 2021 · 19 citations
  4. VST-A: A Foundationally Sound Annotation VerifierLitao Zhou, Jianxing Qin, Qinshi Wang, Andrew W. Appel et al.POPL 2024 · 12 citations

Related papers

  1. Foundational Multi-Modal Program VerifiersVladimir Gladshtein, George Pîrlea, Qiyuan Zhao, Vitaly Kurin et al.POPL 2026 · 4 citations
  2. Generically Automating Separation Logic by Functors, Homomorphisms, and ModulesQiyuan Xu, David Sanán, Zhe Hou, Xiaokun Luan et al.POPL 2025
  3. Generating Proof Certificates for a Language-Agnostic Deductive Program VerifierZhengyao Lin, Xiaohong Chen, Minh-Thai Trinh, John Wang et al.OOPSLA 2023 · 12 citations
  4. Diaframe: automated verification of fine-grained concurrent programs in IrisIke Mulder, Robbert Krebbers, Herman GeuversPLDI 2022 · 27 citations
  5. An Iris Instance for Verifying CompCert C ProgramsWilliam Mansky, Ke DuPOPL 2024 · 14 citations
Dusk over the sea between two cliffs drawn in fine vertical lines