Selene: Pioneering Automated Proof in Software Verification

Lichen Zhang, Shuai Lu, Nan DuanACL 2024 · DOI

Introduction

In high-assurance software engineering, formal verification represents the gold standard, providing mathematical proof that a system is free of bugs. However, the cost of achieving this is immense. For the seL4 microkernel—the first operating system kernel to be formally verified—the proof code is ten times larger than the implementation itself. While writing the specifications took seven person-months, completing the proofs required a staggering 11 person-years.

The Selene project addresses this "proof gap" by automating formal proof generation for industrial-scale software. Unlike mathematical theorem proving, software verification involves thousands of files and complex dependencies, presenting a unique challenge for Large Language Models (LLMs).

The Selene Pipeline

The core of the Selene framework is a pipeline designed to bridge the gap between LLM generation and formal verification tools like the Isabelle prover.

The Selene pipeline automates proof generation, validation via the Isabelle Prover, and iterative fixing based on error messages.

A primary innovation is Lemma Isolation. In large-scale projects, verifying a single proof step typically requires rebuilding the entire environment, a process that can take tens of minutes. Selene extracts a "target lemma" and its immediate dependencies into a lightweight, isolated environment. This allows the Isabelle prover to validate LLM-generated proofs in seconds, enabling rapid iteration.

Enhancing LLM Performance through Augmentation

To overcome the "dependency trap"—where LLMs fail because they lack access to specific project-level facts—the researchers introduced three automated augmentation strategies:

  1. Similar Lemma Augmentation: Uses BM25 retrieval to provide the model with examples of similar proofs from the existing seL4 codebase.
  2. Dependency Augmentation: Supplies the model with the exact definitions and functions required by the target lemma.
  3. Fixing Augmentation: Implements a two-round dialogue where the LLM receives specific error messages from Isabelle and attempts to repair its own proof.
Selene utilizes various augmentation strategies, including searching for similar lemmas and extracting dependencies, to provide context to the LLM.

The Selene Benchmark and Results

The study introduced the Selene Benchmark, a dataset of 360 lemmas randomly sampled from over 100,000 lines of Isabelle code in the seL4 project. These were categorized by difficulty (P1 to P3) based on proof length and style (Procedural vs. Declarative).

The results highlight both the potential and the current limitations of LLMs in this domain:

  • Baseline Success: GPT-4 significantly outperformed GPT-3.5, achieving a 41.7% success rate on simple (P1) proofs compared to 28.1% for GPT-3.5.
  • Augmentation Impact: When combining "Similar Lemma" and "Fixing" augmentations, GPT-4’s success rate on P1 lemmas jumped to 61.9%.
  • The Complexity Wall: Performance plummeted as complexity increased. For the most difficult category (P3), GPT-4’s success rate remained near zero (1.7%), even with assistance.

Conclusion and Future Directions

Selene demonstrates that while LLMs are proficient at debugging simple proofs when provided with feedback, they struggle with the deep logic and procedural "tactics" required for complex software verification. Future work will focus on moving toward interactive proving agents that can observe the "proof state" after every command, mimicking the step-by-step approach used by human experts. Additionally, improving automated dependency extraction remains a critical hurdle for scaling these systems to entire software ecosystems.

Summary updated

BibTeX
@inproceedings{zhang2024selene,
  author = {Lichen Zhang and Shuai Lu and Nan Duan},
  title = {{Selene: Pioneering Automated Proof in Software Verification}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2024},
  doi = {10.18653/v1/2024.acl-long.98},
}
Figure