🤖 AI

Automated Proof Generation for Rust Code via Self-Evolution

The paper introduces SAFE, a self-evolving framework that synthesizes and refines formal proofs for Rust code through iterative data generation and self-debugging guided by symbolic verifiers, enabling open-source models to achieve a 52.52% accuracy rate in automated proof generation—a significant improvement over GPT-4o's 14.39%.

Original authors: Tianyu Chen, Shuai Lu, Shan Lu, Yeyun Gong, Chenyuan Yang, Xuheng Li, Md Rakib Hossain Misu, Hao Yu, Nan Duan, Peng Cheng, Fan Yang, Shuvendu K Lahiri, Tao Xie, Lidong Zhou

Published 2026-02-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tianyu Chen, Shuai Lu, Shan Lu, Yeyun Gong, Chenyuan Yang, Xuheng Li, Md Rakib Hossain Misu, Hao Yu, Nan Duan, Peng Cheng, Fan Yang, Shuvendu K Lahiri, Tao Xie, Lidong Zhou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master chef (the Large Language Model, or LLM) who is incredibly talented at cooking delicious meals (writing code). You can whip up a perfect pasta dish or a complex soufflé just by reading a recipe description. However, there's a catch: sometimes your pasta is undercooked, or your soufflé collapses. In the world of software, a "collapsed soufflé" isn't just a bad meal; it's a security breach or a system crash.

To ensure the food is safe, you need a Food Safety Inspector (a Formal Verifier like Verus). This inspector doesn't just taste the food; they check the chemical composition, the temperature history, and the hygiene logs to mathematically prove the meal is safe.

The Problem:
The problem is that while there are millions of recipes (code snippets), there are almost no "Safety Inspection Reports" (formal proofs). Writing these reports requires a PhD-level understanding of food chemistry and math. Because there are so few reports, our master chef has never learned how to write them. They can cook, but they can't prove the food is safe.

The Solution: SAFE (Self-evolving Automated prooF gEneration)
The paper introduces a framework called SAFE. Think of SAFE not as a single chef, but as a self-improving cooking academy that teaches the chef how to write safety reports, even when no one has written one before.

Here is how SAFE works, broken down into three simple stages:

1. The "Translation" Phase (Making the Ingredients Compatible)

The Verus inspector only speaks a very specific dialect of "Rust" (a programming language). The chef's original recipes are in Python or standard Rust, which the inspector can't read.

The Analogy: Imagine the chef has a recipe for "Spicy Tacos," but the inspector only accepts recipes written in "French."
What SAFE does: It uses a super-smart AI (GPT-4o) to translate thousands of existing recipes into the specific "French" dialect the inspector understands. If a recipe uses an ingredient the inspector hates (like a specific type of loop), the AI swaps it for a safe alternative.

2. The "Speculation" Phase (Guessing the Rules)

Before the inspector can check the food, the chef needs to write down what the food should look like (e.g., "The sauce must be red," "The meat must be cooked to 160°F"). These are called Specifications.

The Analogy: The chef has to guess the rules of the safety inspection.
The Challenge: If the chef guesses wrong (e.g., "The sauce must be blue"), the inspector will reject the food immediately.
What SAFE does: It starts with the chef guessing the rules. Then, it uses a "Quality Score" (like a taste test) to see if the guessed rules make sense.
- If the rules are too easy (e.g., "The food must exist"), they are thrown out because they don't teach the chef anything.
- If the rules are impossible, they are thrown out.
- If the rules are "good enough" (reasonable but not perfect), they are kept.
- The Magic: The chef then practices writing these rules over and over, getting better at each round, creating a massive library of "Good Guesses."

3. The "Proof & Debug" Phase (The Real Training)

Now the chef tries to write the actual Proof (the safety report) based on the rules.

The Struggle: At first, the chef fails 80% of the time. The inspector says, "Error: You forgot to prove the meat didn't burn!"
The "Self-Debugging" Superpower: This is the most brilliant part of SAFE. Instead of just throwing away the failed attempts, SAFE turns them into training lessons.
- It creates a "Study Card" for the chef:
  - The Mistake: "You wrote the report saying the meat was safe."
  - The Inspector's Note: "Error: You didn't check the temperature."
  - The Correction: "Here is the correct sentence to add."
- The chef studies these cards. Over time, the chef learns not just to write the report from scratch, but to fix their own mistakes when the inspector points them out.

The Results: From Novice to Master

The paper tested this "Cooking Academy" against the world's best chef (GPT-4o) and a standard student (Open Source models).

GPT-4o (The Pro without the Academy): Even with a very long, detailed instruction manual, GPT-4o could only get about 14% of the safety reports right. It was like a pro chef trying to write a French safety report without ever studying French.
The SAFE-Trained Model (The Academy Graduate): After going through the self-evolving cycle, the open-source model achieved 52.5% accuracy.
- The Leap: It went from knowing almost nothing about safety reports to being more than 3 times better than the world's most advanced AI at the task.

Why This Matters

In the real world, software bugs cause billions of dollars in losses and can be dangerous (think self-driving cars or medical devices).

Before SAFE: We had to hire expensive human experts to write these safety proofs, which was slow and expensive.
With SAFE: We have built a machine that can teach itself to write these proofs by practicing on thousands of examples and learning from its own mistakes. It creates its own textbook as it goes.

In a nutshell: SAFE is a system that takes a smart AI, gives it a pile of code, and says, "Go write the safety report. If you fail, read the error message, fix it, and try again." By doing this millions of times, the AI evolves from a code-writer into a code-verifier, solving a problem that was previously thought to require human genius.

1. Problem Statement

The paper addresses the critical challenge of automated formal verification for code generated by Large Language Models (LLMs). While LLMs excel at code generation, ensuring their correctness under all possible inputs requires formal proofs.

The Bottleneck: Formal verification tools like Verus (for Rust) require human experts to write complex specifications (pre/post-conditions) and proofs (loop invariants, lemmas). This process is labor-intensive and requires deep expertise.
Data Scarcity: Unlike general coding tasks, there is a severe lack of training data for formal proofs. Existing datasets (e.g., for Lean or F*) contain tens of thousands of human-written proofs, but for Verus/Rust, there are fewer than 500 verified files on GitHub.
Limitations of Current Approaches:
- Prompt Engineering: Relying on in-context learning or complex prompts yields limited generalization and struggles with complex proofs.
- Standard Fine-tuning: Cannot be applied directly due to the lack of high-quality proof data.

2. Methodology: The SAFE Framework

The authors propose SAFE (Self-evolving Automated prooF gEneration), a framework that overcomes data scarcity by creating a self-evolving cycle where data synthesis and model fine-tuning collaborate. The framework operates in three main stages:

Stage 1: Generating Verus-Compatible Code

Input: A dataset of 45,395 small Rust/Python programs (from MBPP and CodeNet).
Process: Since Verus does not support all Rust features (e.g., iterators, HashMap), GPT-4o is used to translate these programs into Verus-compatible Rust syntax.
Filtering: Only code that compiles with the Verus compiler is retained, resulting in ~21,398 compatible programs.

Stage 2: Self-Evolving Specification Synthesis

Goal: Generate formal specifications (pre/post-conditions) for the compatible programs.
Challenge: Perfect specifications are hard to generate; incorrect ones waste training cycles, while trivial ones offer no learning value.
Mechanism:
1. Bootstrapping: GPT-4o generates initial specifications based on code and docstrings.
2. Quantitative Filtering: Instead of human review, SAFE uses a symbolic metric (Correctness and Completeness scores) derived from test cases.
  - Correctness: Percentage of original test cases passing the spec.
  - Completeness: Percentage of mutated (incorrect) test cases rejected by the spec.
3. Evolution: High-quality specs (Correctness $\ge$ 80%, Completeness $\ge$ 60%) are used to fine-tune an open-source LLM. This model then generates better specs for the next round.
Outcome: 19,017 high-quality specifications synthesized after two rounds.

Stage 3: Self-Evolving Proof Synthesis & Self-Debugging

Goal: Generate proofs that allow Verus to verify the code against the synthesized specifications.
Bootstrapping: GPT-4o is heavily prompted to generate initial proofs, managing to verify ~3,673 programs after a month of computation.
The Self-Evolving Loop:
1. Proof Generation: An open-source LLM (DeepSeekCoder) is fine-tuned to generate proofs.
2. Verification: The Verus compiler acts as an authoritative judge. If a proof fails, it is discarded.
3. Self-Debugging (Key Innovation):
  - When a model generates an incorrect proof ( $P_{X}$ ) that fails, Verus provides an error message.
  - If the model eventually generates a correct proof ( $P_{\checkmark}$ ) for the same task, the triplet $\{P_{X}, \text{Error Message}, P_{\checkmark}\}$ is added to the training set.
  - This teaches the model to repair its own proofs based on verifier feedback, rather than just generating from scratch.
Outcome: After three rounds, the model synthesizes 9,706 verified Rust functions and 10,486 self-debugging data pairs.

3. Key Contributions

SAFE Framework: A novel self-evolving architecture that solves the "cold start" problem of formal verification data by synthesizing its own training data (code $\to$ specs $\to$ proofs) without human labeling.
Self-Debugging Mechanism: A specific training objective that leverages the verifier's error messages to train models to repair incorrect proofs, significantly boosting accuracy.
Quantitative Specification Filtering: A method to automatically filter synthesized specifications using symbolic execution and test case mutation, ensuring high-quality training data without human intervention.
Dataset Creation: The creation of the largest synthetic dataset for Verus to date, containing ~19k specifications and ~10k verified proofs.

4. Experimental Results

The authors evaluated SAFE on two benchmarks: VerusBench (human-curated) and CodeNet-Test (synthetic, larger scale).

Performance vs. GPT-4o:
- VerusBench: SAFE (DeepSeekCoder) achieved 43.17% accuracy (Accuracy@1) compared to GPT-4o's 11.51%. With self-debugging (SAFE+), accuracy jumped to 52.52% (vs. GPT-4o's 14.39%).
- CodeNet-Test: SAFE achieved 43.83% vs. GPT-4o's 0.28%.
Impact of Self-Debugging: The self-debugging capability consistently improved performance. For example, on VerusBench, using 10 initial proofs + 100 debugged proofs (Accuracy@100) raised DeepSeekCoder's performance to 70.50%.
Ablation Studies:
- Specification Quality: Training on low-quality specifications caused a drastic drop in performance (e.g., Accuracy@1 dropped to 0% on the SV subset), proving the necessity of the filtering mechanism.
- Model Evolution: Each round of self-evolution significantly improved the model, with Round 3 outperforming Round 2 and the base GPT-4o significantly.

5. Significance

Bridging the Gap: SAFE demonstrates that open-source models can be trained to perform high-level formal verification tasks even when no human-written training data exists for the specific tool (Verus).
Scalability: The framework is generalizable. It suggests a path to automate formal verification for other languages and tools where data is scarce, moving away from reliance on expensive human experts or massive pre-existing datasets.
Trustworthy AI: By enabling automated proof generation, this work directly contributes to the reliability of AI-generated code, a critical step for deploying LLMs in safety-critical systems.

In conclusion, SAFE successfully transforms the data scarcity problem of formal verification into a solvable engineering challenge through a self-improving loop of specification synthesis, proof generation, and error-driven debugging.