Lune

PLDI2023Top-tier venue

Mostly Automated Proof Repair for Verified Libraries

Kiran Gopinathan, Mayank Keoliya, Ilya Sergey

Abstract

The cost of maintaining formally specified and verified software is widely considered prohibitively high due to the need to constantly keep code and the proofs of its correctness in sync—the problem known as proof repair . One of the main challenges in automated proof repair for evolving code is to infer invariants for a new version of a once verified program that are strong enough to establish its full functional correctness. In this work, we present the first proof repair methodology for higher-order imperative functions, whose initial versions were verified in the Coq proof assistant and whose specifications remained unchanged. Our proof repair procedure is based on the combination of dynamic program alignment, enumerative invariant synthesis, and a novel technique for efficiently pruning the space of invariant candidates, dubbed proof-driven testing , enabled by the constructive nature of Coq’s proof certificates. We have implemented our approach in a mostly-automated proof repair tool called Sisyphus. Given an OCaml function verified in Coq and its unverified new version, Sisyphus produces a Coq proof for the new version, discharging most of the new proof goals automatically and suggesting high-confidence obligations for the programmer to prove for the cases when automation fails. We have evaluated Sisyphus on 10 OCaml programs taken from popular libraries, that manipulate arrays and mutable data structures, considering their verified original and unverified evolved versions. Sisyphus has managed to repair proofs for all those functions, suggesting correct invariants and generating a small number of easy-to-prove residual obligations.

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.

6 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

  • QED in Context: An Observation Study of Proof Assistant Users cites Proof repair across type equivalences
  • RefinedC: automating the foundational verification of C code with refined ownership types cites Simple High-Level Code for Cryptographic Arithmetic - With Proofs, Without Compromises
  • Why the Proof Fails in Different Versions of Theorem Provers: An Empirical Study of Compatibility Issues in Isabelle cites Proof repair across type equivalences
  • Foundational Multi-Modal Program Verifiers cites RefinedC: automating the foundational verification of C code with refined ownership types
  • Foundational Multi-Modal Program Verifiers cites Simple High-Level Code for Cryptographic Arithmetic - With Proofs, Without Compromises
  • Diaframe: automated verification of fine-grained concurrent programs in Iris cites RefinedC: automating the foundational verification of C code with refined ownership types
  • Proof Repair across Quotient Type Equivalences cites Proof repair across type equivalences
  • StarMalloc: Verifying a Modern, Hardened Memory Allocator cites RefinedC: automating the foundational verification of C code with refined ownership types
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers6

  1. StarMalloc: Verifying a Modern, Hardened Memory AllocatorAntonin Reitz, Aymeric Fromherz, Jonathan ProtzenkoOOPSLA 2024 · 5 citations
  2. Foundational Multi-Modal Program VerifiersVladimir Gladshtein, George Pîrlea, Qiyuan Zhao, Vitaly Kurin et al.POPL 2026 · 4 citations
  3. QED in Context: An Observation Study of Proof Assistant UsersJessica Shi, Cassia Torczon, Harrison Goldstein, Benjamin C. Pierce et al.OOPSLA 2025 · 2 citations
  4. Why the Proof Fails in Different Versions of Theorem Provers: An Empirical Study of Compatibility Issues in IsabelleXiaokun Luan, David Sanán, Zhe Hou, Qiyuan Xu et al.FSE 2025 · 1 citation
  5. Proof Repair across Quotient Type EquivalencesCosmo Viola, Max Fan, Talia RingerOOPSLA 2025 · 1 citation

Builds on4

  1. 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
  2. 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
  3. Diaframe: automated verification of fine-grained concurrent programs in IrisIke Mulder, Robbert Krebbers, Herman GeuversPLDI 2022 · 27 citations
  4. Proof repair across type equivalencesTalia Ringer, RanDair Porter, Nathaniel Yazdani, John Leo et al.PLDI 2021 · 20 citations

Related papers

  1. Live Verification in an Interactive Proof AssistantSamuel Gruetter, Viktor Fukala, Adam ChlipalaPLDI 2024 · 3 citations
  2. Engineering a Formally Verified Automated Bug FinderArthur Correnson, Dominic SteinhöfelFSE 2023 · 6 citations
  3. TacTok: semantics-aware proof synthesisEmily First, Yuriy Brun, Arjun GuhaOOPSLA 2020 · 39 citations
  4. VST-A: A Foundationally Sound Annotation VerifierLitao Zhou, Jianxing Qin, Qinshi Wang, Andrew W. Appel et al.POPL 2024 · 12 citations
  5. Synthesizing Implication Lemmas for Interactive Theorem ProvingAna Brendel, Aishwarya Sivaraman, Todd D. MillsteinOOPSLA 2025
Dusk over the sea between two cliffs drawn in fine vertical lines