Cobblestone: Iterative Automation for Formal Verification

Saketh Ram Kasibatla, Arpan Agarwal, Yuriy Brun, Sorin Lerner, Talia Ringer, Emily FirstarXiv 2024 · arXiv · OpenReview

Abstract

Formal verification using proof assistants, such as Coq, is an effective way of improving software quality, but it is expensive. Writing proofs manually requires both significant effort and expertise. Recent research has used machine learning to automatically synthesize proofs, reducing verification effort, but these tools are able to prove only a fraction of the desired software properties. We introduce Cobblestone, a new proof-synthesis approach that improves on the state of the art by taking advantage of partial progress in proof synthesis attempts. Unlike prior tools, Cobblestone can produce multiple unsuccessful proofs using a large language model (LLM), identify the working portions of those proofs, and combine them into a single, successful proof, taking advantage of internal partial progress. We evaluate Cobblestone on two benchmarks of open-source Coq projects, controlling for training data leakage in LLM datasets. Fully automatically, Cobblestone can prove 48% of the theorems, while Proverbot9001, the previous state-of-the-art, learning-based, proof-synthesis tool, can prove 17%. Cobblestone establishes a new state of the art for fully automated proof synthesis tools for Coq. We also evaluate Cobblestone in a setting where it is given external partial proof progress from oracles, serving as proxies for a human proof engineer or another tool. When the theorem is broken down into a set of subgoals and Cobblestone is given a set of relevant lemmas already proven in the project, it can prove up to 58% of the theorems. Our research shows that tools can make better use of partial progress made during proof synthesis to more effectively automate formal verification.

Introduction

Formal verification is the "gold standard" of software quality, mathematically proving that a system is free of certain classes of bugs. However, it is notoriously difficult and expensive; writing proofs in assistants like Coq can take eight times as much effort as writing the actual code. While Large Language Models (LLMs) have shown promise in automating this, they often struggle with long-form reasoning or fail entirely due to a single minor error in a complex proof.

Automated proof synthesis typically falls into two camps: tactic-by-tactic search and whole-proof generation. Tactic-by-tactic tools often get "lost" in massive search spaces because they lack a high-level plan. Conversely, whole-proof LLMs are good at planning but fragile; a single hallucinated tactic or syntax error causes the entire proof to fail, and the tool learns nothing from the "partial success." Cobblestone bridges this gap by leveraging the planning power of LLMs while using the rigorous feedback of a theorem prover to salvage the correct parts of a failed attempt.

The Cobblestone Pipeline

Cobblestone operates through a multi-stage, recursive pipeline designed to break down complex theorems into manageable subgoals. The process begins with CoqHammer, an SMT-solver-based tool that is fast but limited in its reasoning capabilities (e.g., it cannot perform induction). If the hammer fails, Cobblestone prompts an LLM (such as GPT-4) to generate several "whole-proof" candidates.

The Cobblestone pipeline, illustrating the recursive application of CoqHammer and LLM-based proof sampling to decompose theorems.

The core innovation of Cobblestone is its Fail-Safe Mode. Instead of stopping at the first error encountered in an LLM-generated proof, Cobblestone executes the proof and identifies which sub-proofs—often organized by "bullets" in Coq—were actually successful. It replaces failing sections with an admit tactic, effectively "saving" the progress made on other subgoals.

Cobblestone then recursively invokes itself on the remaining "admitted" subgoals. Because the original LLM attempt likely decomposed the hard problem into smaller ones, these new subgoals are often simple enough for the hammer or a subsequent LLM call to solve. This recursive divide-and-conquer strategy ensures that partial progress is never wasted.

Fail-safe mode output, where successful subproofs are marked "correct" and failing ones are replaced with "admit" and marked "in progress."

Evaluation and Results

The researchers evaluated Cobblestone on four benchmarks of open-source Coq projects: CoqGym100, Wigderson100, BB5100, and PnVRocqLib100. The latter three were specifically chosen because their code was published after the training data cutoff for GPT-4, ensuring the results were not biased by data leakage.

Key results include:

  • Superior Success Rates: On the CoqGym100 benchmark, Cobblestone achieved a 48% success rate, significantly outperforming CoqHammer (30%) and the RNN-based Proverbot9001 (17%).
  • Outperforming LLM Baselines: It outperformed the state-of-the-art LLM tool PALM on three out of four benchmarks when controlled for token usage.
  • Efficiency: A Cobblestone run costs an average of $1.25$ and takes about 14.7 minutes. While more expensive than a simple hammer, this is a fraction of the cost of a human proof engineer.
  • Human-in-the-loop Potential: When tested with an "oracle" (simulating a human providing the right lemmas or proof structure), Cobblestone's success rate jumped to 58%.

Conclusion

Cobblestone demonstrates that partial progress is a goldmine for automated verification. By treating a failed proof attempt as a potential decomposition plan, the tool can navigate complex search spaces that stymie traditional methods. While currently dependent on structured proof styles (like bullets), Cobblestone establishes a new state of the art and points toward a future of highly effective, semi-automated proof assistants.

Summary updated

Abstract

Formal verification using proof assistants, such as Coq, is an effective way of improving software quality, but it is expensive. Writing proofs manually requires both significant effort and expertise. Recent research has used machine learning to automatically synthesize proofs, reducing verification effort, but these tools are able to prove only a fraction of the desired software properties. We introduce Cobblestone, a new proof-synthesis approach that improves on the state of the art by taking advantage of partial progress in proof synthesis attempts. Unlike prior tools, Cobblestone can produce multiple unsuccessful proofs using a large language model (LLM), identify the working portions of those proofs, and combine them into a single, successful proof, taking advantage of internal partial progress. We evaluate Cobblestone on two benchmarks of open-source Coq projects, controlling for training data leakage in LLM datasets. Fully automatically, Cobblestone can prove 48% of the theorems, while Proverbot9001, the previous state-of-the-art, learning-based, proof-synthesis tool, can prove 17%. Cobblestone establishes a new state of the art for fully automated proof synthesis tools for Coq. We also evaluate Cobblestone in a setting where it is given external partial proof progress from oracles, serving as proxies for a human proof engineer or another tool. When the theorem is broken down into a set of subgoals and Cobblestone is given a set of relevant lemmas already proven in the project, it can prove up to 58% of the theorems. We qualitatively study the theorems Cobblestone is and is not able to prove to outline potential future research directions to further improve proof synthesis, including developing interactive, semi-automated tools. Our research shows that tools can make better use of partial progress made during proof synthesis to more effectively automate formal verification.
BibTeX
@misc{kasibatla2024cobblestone,
  author = {Saketh Ram Kasibatla and Arpan Agarwal and Yuriy Brun and Sorin Lerner and Talia Ringer and Emily First},
  title = {{Cobblestone: Iterative Automation for Formal Verification}},
  year = {2024},
  eprint = {2410.19940},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.19940},
}

Loading related content...

Figure