Automated Proof Generation for Rust Code via Self-Evolution
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
Venue: ICLR 2025 Poster (2025)
Keywords: Large Language Models
Program Verification
Primary area: applications to computer vision, audio, language, and other modalities

Abstract: Ensuring correctness is crucial for code generation. Formal verification offers a
definitive assurance of correctness, but demands substantial human effort in proof
construction and hence raises a pressing need for automation. The primary obsta-
cle lies in the severe lack of data—there is much fewer proofs than code snippets
for Large Language Models (LLMs) to train upon. In this paper, we introduce
SAFE, a framework that overcomes the lack of human-written proofs to enable
automated proof generation of Rust code. SAFE establishes a self-evolving cycle
where data synthesis and fine-tuning collaborate to enhance the model capability,
leveraging the definitive power of a symbolic verifier in telling correct proofs from
incorrect ones. SAFE also re-purposes the large number of synthesized incorrect
proofs to train the self-debugging capability of the fine-tuned models, empowering
them to fix incorrect proofs based on the verifier’s feedback. SAFE demonstrates
superior efficiency and precision compared to GPT-4o. Through tens of thousands
of synthesized proofs and the self-debugging mechanism, we improve the capa-
bility of open-source models, initially unacquainted with formal verification, to
automatically write proofs for Rust code. This advancement leads to a signifi-
cant improvement in performance, achieving a 52.52% accuracy rate in a bench-
mark crafted by human experts, a significant leap over GPT-4o’s performance of
14.39%.

Published as a conference paper at ICLR 2025
AUTOMATED PROOF GENERATION FOR RUST CODE VIA SELF-EVOLUTION
Tianyu Chen Shuai Lu 2 Shan Lu"
Yeyun Gong" Chenyuan Yang Xuheng Li Li 4
Md Rakib Hossain Misu 5." Hao Yu Nan Duan 2 Peng Cheng Fan Yang
Shuvendu K Lahiri 2 Tao Xie Lidong Zhou?
Peking University, ftycher.811 yh0315, taoxie/pku. edu. cn
2 Microsoft Research, {shuai lu, shanlu, yegong, nanduan, penge, fanyang, shuvendu. lahiri, lidongzz)@m http:////mccroooof.ooooooooooooe crosoft. com
3 University of Illinois at Urbana- Artaan-Chaamaainn
cy54eillinon edu,
4 Columbia University, suheng@cs..cllumbie cowumbia.
5 University of California Irvine, mdrhêuci. edd
ABSTRACT
Ensuring correctness is crucial for code generation. Formal verification offers a definitive assurance of correctness, but demands substantial human effort in proof construction and hence raises a pressing need for automation. The primary obsta- cle lies in the severe lack of data-there is much fewer proofs than code snippets for Large Language Models (LLMs) to train upon. In this paper, we introduce SAFE, framework that overcomes the lack of human- numan-written proofs to enable automated proof generation of Rust code. SAFE establishes a self-evolving cycle where data synthesis and fine-tuning collaborate to enhance the model capability, leveraging the definitive power of symbolic verifier in telling correct proofs from incorrect ones. SAFE also re- re-purossss the large number of synthesized incorrect proofs to train the delf-debugging capability of the fine-tuned models, empowering them to fix incorrect proofs based on the verifier's ' feedback. SAFE demonstrates superior efficiency and precision compared to GPT-4o. Through tens of thousands of synthesized proofs and the self-debugging mechanism, we improve the capa- bility of open-source models, initially unacquainted with formal verification, automatically write proofs for Rust code. This advancement leads to a signifi- cant improvement performance, achieving a 52.52% accuracy rate bench- mark crafted by human experts, a significant leap over GPT-4o's performance of 14.39%.
INTRODUCTION
Large Language Models (LLMs) have recently exhibited impressive capabilities in code generation (Roziere et al. 2023 Guo et al. 2024 Lozhkov et al., 2024] Google (024)). However, the correct- ness of generated code cannot be guaranteed. To prove that a program satisfies the desired properties under all possible inputs, without running the program, we need formal verification. Unfortunately. formal verification is difficult conduct, as one needs to first formally express the desired prop- erties, often in special proof-oriented language, and then craft formal proofs. taking substamtial formal verification expertise (Zhang et al. 2024). Therefore, advance trustable code generation, automated formal verification, particularly automated proof generation, is in a pressing need.
Two main approaches of proof automation have been explored. The first (Misu et al.) 2024 Sun
et al.] 2024a] Pei et al., 2023 Liu et al. 2023] Chakraborty et al.) [023] Kamath et al. 2023 Chakraborty et al. 2024 Yao al., 2023 Yang et al.) (0244)) relies on well crafted prompt or in-context learning on L.Mss. To teach LLMs about formal proofs, this approach often requires intensive prompt engineering that hardcodes proof-writing tips, and/or requires support from static program analysis, resulting in limited generalization ability. The second approach (Polu et al.
2022
First et al. 2023 Azerbayev et al. 2023 Yang et al., 2024b) fine-tunes open-source LLMs.
Work done during internship at Microsoft Research.
corresponding author.

---

Published as a conference paper at ICLR 2025
This approach has been shown to be effective for Lean (Avigad 2017) (for mathematical proving) and F (Swamy et al. 2016) (a special proof-oriented language), where tens of thousands of human- written Lean and F proofs exist. However, how to apply this data-oriented approach to many other tion.
verification tools or proof languages that have much fewer exiting proofs remains as an open ques-
In this paper, we tackle this open question for Verus (Lattuada et al. 2023) the state-of-the-ar verification tool for code written in Rust. Verus a perfect target for us, since (1) it is one of the rare verification tools that can directly prove the correctness of code written in a popular language (Rust), which is increasingly popular in production as a safer and better alternative to C/C++ (ONCD) 2024] Rivera et al.] (02I)) and (2) due to its short history, there are fewer than 500 Rust files currently verified by Verus on GitHub, too few for fine-tuning-
The challenge of lacking data for Verus proof generation shows up at three main levels. First, lack of suitable programs to quickly generate proofs for. Not all Rust features are supported by Verus yet. Furthermore, large Rust projects typically require code refactoring to get verified (Zhou al. 2024] Sun et al. 2024b), and yet small Rust programs may not have meaningful properties to prove (e.g.. a hello-world function). Second, lack of Verus specifications. Before proving any Rust function, Verus needs a formal specification that describes the expected behavior of the function, such as the pre-condition (Lines 7-9) and post-condition (Lines 10-13) shown in Listing D Not surprisingly, these specifications do not exist except for in those existing verified Rust files on GitHub. Third, lack of Verus proofs. It took many months write couple of thousand lines of Verus proofs even for experts (Zhou et al., 22024] Sun et al. 2024b). It took more than ten years' effort to accumulate those fine-tuning training data for Lean Yang al. 2024b) and F-Star (Chakraborty al. 2024).
In this paper, we propose the Self-evolving Automated prooF gEneration (SAFE) framework that overcomes the challenge of multi-level data scarcity. First, to quickly obtain a large number of proof-friendl) Rust programs, we leverage GPT-4o to "translate" tens of thousands of and Rust programs in popular code-synthesis datasets to programs written in Verus-supported Rust syntax. Any program that cannot be compiled by the Verus compiler is dropped.
small Python
Second, to obtain formal specifications for these tens of thousands of Rust programs, SAFE uses a few rounds of self-evolving specification generation. The bootstrapping round prompts GPT-4o to generate Verus-style specifications based on each Rust function and its associated natural language doc-string. In every following round, specifications generated in previous iterations are used to train a new fine-tuned open-source LLM that produces more specifications in generally higher quality for the next round of finetuning. Keys to the success of this step include (1) using quantitative metric [Lahiri 2024) to differentiate high-quality specifications from low-quality ones, and use the former for only finetuning; and (2) the observation that we need only reasonably well, instead of perfect, specifications to enable proof generation in the next step.
Next, to obtain tens of thousands of verified Rust programs, SAFE similarly uses self-evolving procedure. Code proofs are very difficult to synthesize: even with careful prompt engineering, GPT- 4o managed synthesize correct proofs for only < 20% of programs in the the preceding dataset with synthesized specifications, after a month of non-stop invocations. Fortunately, this is sufficient to bootstrap SAFE. Through rounds of self-evolving, the quantity and quality of synthesized proofs keep increasing, while fine-tuned open-source models' capability of proof synthesis keeps getting augmented. These models also generate proofs much faster than GPT-4o. The keys to the success here include (1) the ability of Verus in authoritatively and quickly telling correct proofs from in- correct ones, allowing SAFE to sift through the huge amount of low-quality data in early rounds without any human labeling. and (2) the reasonable quality of SAFEEsynthesized specifications that allow SAFE to largely avoid trivial proofs, which have little usage in fine-tuning.
Finally, SAFE re- puppppsssss the huge number of incorrect proofs generated in the previous step to add the self-debugging capability into its model. In each round, when a correct proof P/ is synthesized after several attempts, the triplet of an earlier incorrect proof Px, the verification error reported by Verus on Px, and Pv, becomes a training data point, which fine-tunes the model's capability in debugging and repairing proof-a great side effect of having incapable models early on.
In our experiments, SAFE leverages DeepSeekCoder (Guo et al. 2024) as the generator, success- fully synthesizing 19,017 formal specifications and 9,706 verified Rust functions, from dataset comprising 45,395 Rust functions sourced from the MBPP (Austin et al. 202I) training split and
2

---

Published as a conference paper at ICLR 2025
Listing 1: An Example Verus Program (Binary Search).
varua!i
// Perforns binary search sorted vector 64-bit unsigned incegera (u64) f'rd the index of given Larget value.
binary_search (wr sVeosu54>,
u64)
usi
requires pepreecooditions of this progsam
Foralili:int, ]:int| D <= ce ] v.len() ma> v[i] <- v(i
exlstal1:int
(e
v[1.e.
//poat-conditions of this progeam
TT <- T,
v.lenff,
10
== M 55 19t
11
12
let mut 11: usize 0;
13
let mut 12: usize v.len() 1;
14
while 11
15
Invariant //1oop Invarianta (used for proof) v.l exists
17
<o 12 v(1),
18
Torall i: int, 3: Int <e <e ve viil <= vi1l.
19
20
let ix
11) 2:27
21
1f v[ix] k
22
i1
23
1 else 12 = 181
24
25
i1
26
11
This Rust program's pre-conditions are highlighted in orange background; its post-conditions are highlighted in green; and its Verus proof annotations (loop invariants) are highlighted in gray.
CodeNet (Puri et al. 202T) training dataset. Note that the initial Rust dataset contains zero lines of formal specification proof. Our evaluation on human-curated Verus benchmark with human- written specifications, VerusBench, and a synthetic benchmark, CodeNet-TTstt, demonstrates that SAFE empowers DeepSeekCoder, which is initially unacquainted with Verus, achieve 43.17% and 43.83% accuracy on the two benchmarks by direct generation, far surpassing GPT-4o's perfor- mance of 11.11% % and 0.28%, respectively. Furthermore, the model's accuracy reaches 79, 19.14% in VerusBench and 48 43% in CodeNet-Tees once its self-debugging feature is used.
BACKGROUND AND RELATED WORK
2.1 VERUS VERIFICATION TOOL
Verus (Lattuada et al. 2023) statically analyzes every proof target (i.e., a Rust function and its specification) and any given proof annotations, and forms queries for the underlying SMT solver (e.g., 73 (De Moura & Bjørner 2008) to solve. By leveraging the type system in Rust and allowing both specification and proof annotations to be written in Rust syntax, Verus has become the state- of-the-art verification tool for Rust, one of the most popular programming languages (Porkel 2020) Fulton al. 2021) and has been used to successfully verify large systems (Sun al. 2024b Zhou et al. 2024). Unfortunately, since Verus has been developed for only about three years, there are fewer than 500 Verus verified Rust files on GitHub.
Listing T shows Rust function that implements binary search. Its specification includes pre- requires block and post-condition enclosed in an ensures block (Lines 4-10). The pre-condition states that the input array is ordered in an ascending way and the input value k searched exists in the array (Foral1 and exi sts are Verus quantifiers); the post-condition requires that the return value should be valid index pointing to the input value
condition enclosed
For simple programs/speecficaations Verus can accomplish the formal verification without any extra annotations (we refer these cases trivial proofs). Unfortunately, for functions and specifications that involve loops, collections, and quantifiers, Verus often needs users to provide proof annotations. The loop invariants specified Lines 16-18 one type of proof annotations. They specify what properties are true right before and right after every loop iteration. Verus will prove the correctness of each loop invariant and then proved loop invariants to help prove the function specification. If

---

Published as a conference paper at ICLR 2025
any loop invariant is incorrect or if needed invariants missing, the proof will fail. For more com- plicated tasks, other types of proof annotations like assert and lemma functions may be needed.
2.2 PRIOR WORK
BOOF-BBNNHHARK BUILDING AND SELF-EVOLVING FRAMEWORK
There has been much effort recently in building datasets of existing human written proofs (Loughridge et al, 2024 Zhang et al., 2024; Chakraborty et al. 2024). Unfortunately, since writ- ing proofs takes expertise beyond normal coding, this dataset- dataset-building approach is difficult to scale. Recent work has explored augmenting the Dafny-proof dataset using proofs synthesized by GPT-4 through few-shot learning and human- -wrtttnn proof examples (Misu et al. 2024 Sun et al. 2024a). power of GPT-4, the number of proofs in these datasets
However, due to the limited are fewer than 200, with many being trivial proofs.
Self-evolving style of learning has been explored in other contexts: A reinforced self-training frame- work is proposed in the machine translation task (Gulcehre et al. 2023), and the expert iteration strategy is leveraged for math proving with Lean (Polu et al. (2022). Our work applies self-evolving and expert iteration to synthesize proofs for Rust code. This new task raises different challenges from prior tasks like writing math proofs (Polu et al. 2022) and hence requires different designs.
One obvious challenge is the issue of data scarcity discussed in Section T SAFE does not have access to billions of tokens of manually-writter examples (e.g., math proofs) and hence cannot rely on fine-tuned models for bootstrapping as in prior work; fact, SAFE does not even have access to large quantity of proof problems and hence has to synthesize problems by itself (i.e., Verus- compatible Rust functions and the associated specifications).
Another major challenge is related to the underlying verification engine. Supported by an interactive theorem prover, Lean (Avigad 2017), math-proof synthesis is naturally decomposed to many small steps tactics, with clear judgment about what are useful intermediate proofs. In contrast, like many code- verification tools (Leino 2010 Swamy et al.] 2016). Verus leverages a SMT solver to prove the correctness of function as whole, while proof annotations are used as hints to the SMT solver. It is difficult to decompose Verus-proof synthesis into small steps, and it is difficult to judge whether incorrect proof annotations useful. Consequently, step-wise search strategies used in prior work do not apply here. Instead, whole-prood debugging is crucial for SAFE.
We believe that SAFE presents a new application of the self-evolving and expert iteration philos- ophy to an important and challenging task-code-proof automation. Through its automated mea- suring and filtering every step of data synthesis-Vente compiler for program transpilation, the quantitative specification quullity metric for specification synthesis, and Verus verification for proof- synthesis/debuggnng, SAFE overcomes those unique challenges and allows high-quality training data to gradually accumulate without manual effort.
3 APPROACH
As illustrated in Figure D SAFE involves two self-evolving TTao et al.) 2024 Gulcehre et al.) 2023) procedures. The first procedure synthesizes specifications that are used as inputs to the second procedure, while the second procedure produces the end-result of SAFE can automatically synthesize proofs for Rust code. As listed in Algorithm D both procedures use GPT-40 to generate the round-0) data spec/pr prroofddato and filtered from earlier rounds, 0...- 1, to fine-tune model, based on its preceding model,- At the end of each round, model, is used to generate the round-r data. High-quality specifications are preserved for the next round. Low-quality specifications are discarded; incorrect proofs are re-purposed to become self-debugging training data for the next round.
fine-tuned LLM that
In each round r, we use data collected
3.1 STEP 1: GENERATING CERUS-COMPATIBLE CODE
This step ensures the compatibility of our input Rust programs with Verus, which does not support all Rust features. For instance, some Rust expressions and standard library functionalities like for, Iterators, HashMap, and others are not supported or only partially supported by Verus. Thus, is necessary to adapt normal Rust code to Verus- corpatcome one before adding specifications.
To address this compatibility issue, we employ GPT-4o as a code translator, effectively substitut- ing Veros-inco Rust code snippets with Verus-compatible alternatives, such converting
4

---

Published as a conference paper at ICLR 2025
Fine-
Test Cases
Specification
Translate
Generator
Code with Doestring
Cerpa-Compatible
Verus
High-Quality
Code
Specification
Verus Specification
1. Conns-Com Code
2. Self-Evolving Specification Synthesis
Generation
Generate
Verus Verifier
Solf-debug
Generator
Verifled Proof
Output
Error Messgg
Fine-Tune
3. Self-Evolving Proof Synthesis
Figure I: The SAFE Framework
Algorithm 1: Self-Evolving
Input : modelo, an open-source LLM; rust.programss, a set Rust programs
Output: model,, the self-evolved LLM
programs + crr.ooo.rralaaaeersstt
hotp:/ambeseoooilllleebbbeeeeeee Compiler);
Specification Generation:
spec-datag t GPT-4o. (ennerddelroorrmmss.ftteeeee.e..
for r in [1, Ri] do
model, + model,- spec-data,):
spec-data, model-.gnneratelproooon filter(Testt)
return model,;
Auto-Proving:
proof-datay debug-datag + GFTTd (Veres (Verus Verifier); for r in [1.... R2] do
10
11
model, +-
(proof-data; + debug-data:)):
proof-data, + model, moded filter (Verus Verifier);
12
debug-data, modeel willffieeeeettte (Verus Verifier);
13
return model,;
an tterator-based implementation into while-loop based implementation. Specifically, we prompt GPT-4o with all the unsupported features sourced from Verus official documentation. All the con- verted code that can pass the grammar check of Verus compiler collected for next steps. This step performed only once in self-evolving framework.
3.2 STEP 2: SELF-EVOLVING SPECIFICATION SYNTHESIS
In this step, LLMs are tasked with generating preconditions and postconditions for Rust function based on the function's 's implementation and doestring. Different from prior work in specification generation (Flanagan & Leino 2001 Ma et al.) 2024), SAFE needs synthesized specification as input for self-evolving proof-synthesis framework, which raises unique requirements on its specification evaluation criteria (i.c., which specification to keep discard) and the mechanism to evaluate the criteria.
In terms of criteria, perfect specification S should be correct (i.e., any correct implementation should be accepted by S) and complete (i.e., any incorrect code implementation should be rejected by S). In SAFE, getting perfect specification is not the goal. SAFE should discard incorrect speci- fications, which can never be proved and hence will waste training cycles in the next step. However, SAFE is fine with incomplete specifications, the usage of specifications in SAFE is stimulate

---

Published as a conference paper at ICLR 2025
proof synthesis not to judge code correctness. In fact, SAFE needs incomplete specifications, as complete specifications are likely too challenging to prove at the early stage of the proof-synthesis model's evolution. Of course, specifications that are too incomplete should be discarded, because trivial specifications can be proved without any proof annotations and hence offer no usage for proof-synthesis training (e.g.,
r for the binary search function).
In terms of the mechanism to evaluate the preceding criteria, previous work relies on running many test cases (Endres et al., 2024). formally verifying the consistency between specifications and code (Ma et al., 2024), or user inspection (Lahiri et al. 2022). None of these mechanisms suit SAFE: user inspection or running many test cases would severely slow down the self-evolving framework; formal verification also does not work when we do not have a capable model to auto- matically synthesize proofs.
With all these constraints, chooses to leverage a recently proposed technique (Lahin 2024) to measure the Correctness and Completeness of specifications. We use Verus symbolically evaluate what percentage of test cases T provided by the original dataset can pass a given specification S (i.e., the Correctness score), and what percentage of test cases T mutated from T can be rejected by S (i.e., the Completeness score). For given method sn(x:): y, with x being the input parameter and y being the output, we denote the input/output-valll (i,0) and generate corresponding mutated test case by changing o into a randomly different value o'. The two metrics for a specification S are formally defined as following, with S(i, o) being a boolean value representing whether the input-output value pair (i,0) satisfies the specification S or not:
pair of any test case in a test suite T as
{ (1. 5((, o) and (1, ET)
Correctnesss:
T
{ (i, | not o(i,o') and (i, ETH
Completenessg:
T'
We can now set threshold that fits the need of SAFE: we keep all the specifications with 80% Correctness score and 260% of Completeness score. This way. SAFE can obtain many imperfect but useful specifications for its proof synthesis. We do not set the Correctness threshold to be 100%, because we use GPT to generate test cases when few test cases are provided by the dataset, and we cannot guarantee perfect correctness of these test cases. Since Verus can symbolically evaluate S(i, o) in the preceding formula without checking or running the Rust function, the scoring is fast.
For each function, we keep up to three synthesized specifications, which not only enrich the spec- ification training dataset but also increase the chance of synthesizing valid proofs later. Our self- evolving process for specification stops when there no significant increase in the total number of accepted function-speciffiattin pairs, at which time all these pairs move on to become the input for the next step.
3.3 STEP 3: SELF-EVOLVING PROOF SYNTHESIS
Now that we have tens of thousands of function-speciffcation pairs, we can start the self-evolving procedure of proof synthesis. Compared with specification synthesis, deciding whether to accept or reject a synthesized item is much more straightforward -nly proof that Verus can use verify the Rust function satisfies its specification is accepted; if any verification error is raised, the proof is discarded However, since proof synthesis is much more difficult than specification synthesis, we need to pay special attention to bootstrap the self-evolving procedure and to keep it moving forward.
For bootstrapping, a simple prompt to GPT-40 would not work, as is very difficult for GPT-4o to synthesize all the needed loop invariants without any incorrect ones in between, not to mention more complicated proof annotations like proof blocks and lemma functions. Therefore, we write a detailed prompt for GPT-4o, explaining the principles and tricks of writing Verus proofs. By doing so, we finally manage to make GPT-4o synthesize proof annotations that allow Verus to prove more than one thousand Rust functions at the cost of one whole month of non-stop GPT-4o invocations. Fortunately, doing so is sufficient for bootstrap. For the remainder of the self-evolving procedure, GPT-4o is not used any more. Instead, efficiently synthesize data and improve its capability in a self-evolving manner as in Algorithm [ Specifically, we fine-tune our open-source LLM on two tasks, proof generation and self-debugging.
an open-source LLM much smaller than GPT-4o to
If Rust function is in fact buggy a synthesized specification is incorrect, no proof will be accepted.

---

Published as a conference paper at ICLR 2025
Task #1: Proof generation. The synthesized proofs and specifications are directly used for training this task. Taking a code snippet with specifications as input S. LLM M is tasked with generating proof Y (consisting of tokens yo...... MNN) that can make the code proved by Verus. We train this task with a sequence-to-sequenne objective where
LGen (0)
Σ log Po(us S, Uttc))
Task #2: Sell-debugging. The self-debugging task is trained on the data pair of an incorrect proof and its revision. "Thanks to" the incapability of LLMs in proof generation, a huge number of incorrect proofs are generated during data synthesis. For every Verus program (together with its specification) for which a perfect proof Y- = (yo. yNv is eventually synthesized in a round, we denote those incorrect proofs generated before Y/ as [Y,,.... Y... For every incorrect proof Yx E ,Y,....,Yo ..... a triplet (Yx, Erroryx Y-) } added to our self-debugging training dataset, where ErrorYx represents the verification enrors reported by Verus about Yx. The objective of self-debugging task is
Debuu (0) = Σ log Po Yx, Erroryx MiCs)
important to train the model to "'debug" an imperfect proof. In many cases, the proof anno- tations generated by the model contain only small errors miss one line of annotation. Without the capability of self-debugging, the model would start from scratch and fail to synthesize a perfect proof even after many attempts. In SAFE, we conduct joint training for the proof generation task and the self-debugging task, empowering the LLM to both generate a proof from scratch and repair an existing proof based on verification error messages for a Rust function and its specification.
EXPERIMENTS
4.1 DATASET
As an early exploration of automated formal verification, in this paper, we focus solely on the Rust code of algorithm types at the function level, as our source of data. We employ the MBPP dataset (Austin et al. 2021 1) (only training split for data synthesis) and the CodeNet dataset (Puri et al. 2021b as our data sources. These two datasets contain small programs written different programming languages, each of which is intended solution to a coding problem described in natural language and is associated with three test cases on average. We translate the Python programs in MBPP and extract the Rust programs in CodeNet. In total, we collect 45,395 Rust single-function programs. Of these programs, 21,3% 21,398 have been successfully transformed into Rust code that is compatible with Verus by GPT-4o. We conduct the specification synthesis first, and after two rounds of self- evolution, we obtain 19,017 high-quality specifications. Then we run three rounds of relf-evolving proof synthesis, ending with 9,706 verified programs, and 10,486 self-debugging data pairs. To the best of our knowledge, this dataset represents the most extensive synthetic dataset created for Verus code date.
4.2 BENCIMARR AND METRICS
We assess model's proficiency in generating proofs in two benchmarks, the human- written bench- mark VerusBench and the synthetic benchmark CodeNet-Test.. VerusBench is a human-written benchmark dataset with human-written Rust code and corresponding Verus specifications. It con- tains 139 code files in total. 23 of them are algorithmic programs from Verus tutorials. 38 of them come from the dataset of SV-COMP-
(Beyer 202I) (in short, SV), which is a contest focused on program verification for C and Java languages; we utilize 38 Kerus-translar by Yao et al. (202)). The remaining 78 tasks come from MBPP-DFY-153 (Misu et al,, 2024), a Dainy version of the MBPP test set. We have translated 78 of them that are compatible with Verus. CodeNet- Test is an expansive benchmark, 10x larger than VerusBench, crafted by LLM and en- compassing 1,435 diverse tasks. Given the substantial human effort required to write Verus code and specifications, it's impractical to create a large test suite by human. To comprehensively measure the model capability of generating proofs, we split subset of CodeNet for testing, ensuring that it is not utilized in our data synthesis process. We leverage our specification generator to craft specifications for this subset and apply the same scoring mechanism to preserve reasonably well specifications.
tasks provided
7

---

Published as a conference paper at ICLR 2025
Table 1: Accuracy SAFE and baselines. Prompt is GPT-4o with a long prompt used bootstrap SAFE; column SAFE is LLaMa3. or DeepSeekCoder with three rounds of finetuning and simple prompt. For SAFE+, Accuracy @2 means getting one initial proof sample and one debugging sam- ple; Accuracy @ 100 means getting 10 initial proof' and then 10 x 10 debugging samples.
GPT-4o
LLaMa3.1
DeepSeekCoder
Benchmark
Accuracy
Raw
Prompt
Raw
SAFE
SAFE+
Raw
SAFE
SAFE+
@
11.51
25.90
3.60
46.04
9.35
43.17
VerusBench
@2
14.39
30.93
5.76
48.20
52.52
10.79
46.76
49.64
@ 10
24.46
41.01
11,51
53.96
17.27
53.96
@ 100
43.88
46.76
28.78
55.40
64.03
32.37
59.71
70.50
0.28
2.86
0.00
44.32
0.21
43.83
CodeNet-Test
@
0.70
3.41
0.03
45.34
48.50
0.55
44.74
48.43
We measure the capability of proof generation by Accuracy @ K. Specifically, we use any model under evaluation to sample K proofs during proof generation. For Accuracy@1, we use greedy decoding, which generates only I output, and for Accuracy @ 10, we sample 10 outputs with a tem- perature of 0.7. Then, for each task in our benchmark set, Accuracy@ K equals one if at least one proof/debugged proof is verified by Verus. Note that, when the self-debugging feature of SAFE is used (i.e., SAFE+), the proof generation includes two rounds: at the first round, K initial proof's are sampled; at the second round, if none of the initial proofs are correct, K proof' are generated by self-dehugging each initial proof, resulting in K K debugged proofs.
4.3 EVALUATION RESULTS
we compare the accuracy of SAFE with our baseline approaches. Due to the inherent complexity of this task, there is no pre-existing fine-tuned model to serve as a baseline. We employ model (Guo et al. 2024). and Llama3. 1-8--..--B- model (Dubey et al. 2024) with basic prompts the same what we use for the fine-tuned models our baselines. To offer some advantages to the baselines. we also feed four examples for in-context learning in these baselines, which we do not use for SAFE fine-tuned models.
In Table I
GPT-4o. CoeeSeeeCooer-33B----1
We can see that SAFE achieves substantially higher accuracy compared to baseline approaches in both datasets and metrics. In the VerusBench benchmark, even without self-debugging, SAFE achieves an Accuracy @1 I of 46.04% 04% and an Accuracy @ 10 of 53.96% while the best of 'Raw' results come from GPT-4o with 11.51% 1% in Accuracy@ and 24.46% Accuracy @ 10. With the long and carefully designed prompt, which was used to bootstrap SAFE proof synthesis, GPT-4o is reasonably effective for VerusBench. For the CodeNet- Test benchmark, we find the performance of basclines and prompt-based GPT-4o, denoted as Prompt, drops significantly- by more than 10X compared with VerusBench, while SAFE does not suffer as much. It is important to note that CodeNet- is significantly larger and exhibits distinct data distribution compared to VerusBench, and the former derived from competitive programming, whereas the latter encompasses common algorithms. The results indicate that the prompt-based approach has limited generalizability in automated proof generation, while SAFE no longer needs complicated prompts during inference. We further report paired t-test (Hsu & Lachenbruch 2014) results for Table Tin Table in Appendix.
Table alsoo shows the efficacy of self-debugging (i.e., SAFE+). For example, after one initial proof sampled, applying self-debugging on this proof produce the second sample (Accuracy @2 for SAFE+) consistently outperforms simply producing a second sample of proof without debugging (Aceuracy @2 for SAFE) for both LLaMa and DeepSeekCoder on both VerusBench and CodeNet- Test, as shown in Table [ SAFE+ with DeepSeekCoder achieves the best performance of 70.50% in Table when 10x 10 debugged proofs are produced for 10 initial proofs for each proof task.
Overall, by leveraging our self-evolving framework, SAFE can substantially improve the capability of open-source model and effectively generate proofs for Verus programs.
4.3.1 BENEFITS FROM SELF-EVOL.VING
In Table 2 we use the performance on VerusBench to show how our self-evolving framework improves the capability of models. In this set of experiments, we use DeepSeekCoder-333B
8

---

Published as a conference paper at ICLR 2025
Table 2: Accuracy of SAFE models produced by each round (measured on VerusBench)
Self- Evolving
Proof Generation
Self- Self-Debugging (K + K * K)
Metric
SV
MBPP
Tutorial
Total
SV
MBPP
Tutorial
Total
Accuracy@1 1
39.47
19.23
26.09
25.90
GPT-4o
Accuracy @ 10
60.53
33.33
34.78
41.01
Accuracy@ @1 1
55.26
29.49
4.35
32.37
57.89
30.77
4.35
33.81
Round
Accuracy @ 10
81.58
30.77
13.04
41.73
81.58
30.77
13.04
41.73
Accuracy@ @ 1
73.68
29.49
34.78
42.45
84.21
38.46
39.13
51.08
Round2
Accuracy @ 10
89.47
30.77
47.83
49.64
92.10
56.41
52.17
65.47
Accuracy @ 1
78.95
30.77
26.09
43.17
81.58
41.03
26.09
49.64
Round
Accuracy @ 10 92.11
35.90
52.17
53.96
97.37
58.97
65.22
70.50
Instruct for data synthesis and fine-tuning; Rounds 1, 2, represent three models fine tuned from BatSSeeeCooder-33--Innn-t Table that for every subset of VerusBench, the best Accu- racy@ and Accuracy 10 scores are achieved at the last two rounds of model evolution, indicating the effectiveness of self-evolution. Besides, Round 1 model with a simple prompt already outper- forms GPT-4o with much more sophisticated prompt for all but the "Tutorial" subset. Round model outperforms Round model in terms of Accuracy @ 10 for all subsets of tasks, with without self-debugging. Meanwhile, the improvement from Round 2 to Round is much smaller than the improvement from GPT-4o to Round 1, and from Round 1 to Round 2, justifying our decision of stopping the self-evolution after three rounds. We further report paired t-test results for Table 2 in Table in Appendix.
Finally, Round 3 model greatly outperforms GPT-4o for all three sub-sets of VerusBench, even though GPT-4o uses a much more sophisticated prompt: GPT-4o most effective for the SV subset with a 39.47% Accuracy@ @ I, while Round 3 model improves that metric to 78.95% (81.58% with self-debugging); GPT-4o is the least effective for the MBPP subset with 19.23% Accuracy @ 1, which is improved by Round 3 model to 30. 70%7 (41.03% with self-debugging). This trend bolds well for SAFE work with different datasets and different bootstrapping approaches in the future.
4.3.2 IMPROVEMENT OF SELF-DEBUGGING
Table I demonstrates that SAFE+, which allows LLMs to do self-debugging, substantially improves the accuracy compared to direct generation, indicating the effectiveness of the self-debugging mech- anism. As we show in Listing of the Appendix, Verus provides eπror messages for any incorrect proof about which proof annotation, which part of the specification, or which implicit proof target (c.g., no overflow for every arithmetic expression) cannot be verified. These error messages can help repair the proof for experienced human users and well trained models.
Decoding Strategies for Self-Debugging. From Table D we can see that the enhancements of self-debugging become more significant with the increase in the number of sampled outputs. To further evaluate how decoding strategies affect the performance of self-debugging in VerusBench, conduct four settings by combining greedy and sampling decoding during the generation and debugging phases, and run two more self-debugging rounds with greedy decoding, [eguree]showe that more rounds of self-debugging hardly improve the accuracy, with the improvement less than 1%. Besides, the sampling decoding strategy is more useful for the generation phase rather than for the self-debugging phase. Notably, the "sampling+greedy" each incorrect proof generate one debugged proof) strategy outperforms the "greedy++sampling" (generating one proof and generate multiple debugged proofs) setting. Existing work (Chen et al.)
(generating multiple proofs and for
2023 Olausson al. 2023) has shown similar results.
4.3.3 IMPACT OF SPECIFICATION QUALITY
As mentioned in Section 3.2 we keep only specifications with high Correctness scores and reason- ably high Completeness scores. To investigate the impact of this design decision, we zoom into the last round of proof-synthesis model fine-tuning see how the quality of proof-synthesis model can affected by the quality of the used specification dataset. Specifically, the current Round-3 SAFE model is obtained by fine-tuning the Round-2 SAFE model using correct proofs synthesized

---

Published as a conference paper at ICLR 2025
0.625
Accursyy
0.60
0.55
0.500
Cready Brouey
Groady Creedy
Gready Sonsiin
0.475
Samplingt Samping
Sarn
Round of self self-debugging
Round of self-debugging
(a) LLaMa
(b) DeepSeckCoder
Figure 2: SAFE's accuracy with different self-debugging, sampling decoding strategies
Table 3: Accuracy drop of proof synthesis w/ Suaning-specificatiin quality drop (on VerusBench)
Model
Proof Generation
Self- Soff-Debugging (K + K K)
Metric
(Spec-Quality
SV
MBPP
Tutorial
Total
SV
MBPP
Tutorial
Total
Accuracy @ 1
78.95
30.77
26.09
43.17
81.58
41.03
26.09
49.64
SAFE
Accuracy @ 10
92.11
35.90
52.17
53.96
97.37
58.97
65.22
70.50
Aecuracy @ 1
0.00
29.49
4.35
17.27
0.00
43,59
21.74
28.06
Low-Quality
Accuracy @ 10
5.26
32.05
21.74
23.02
15.79
50.00
47.83
40.29
Accuracy @ 1
36.84
30.77
17.39
30.22
42.11
43.59
21.74
39.57
Mix-Quality
Accuracy @ 10 65.79
32.05
30.43
41.01
71.05
51.28
52.17
56.83
by the bootstrapping model, the Round-1 model, and the Round-2 model based on the specifica- tions S selected by SAFE, denoted Po [S] P [|[S] U P2[S] (P:[S] denotes all the correct proofs synthesized in round i based on specification set 5). In our two alternative settings, we go back to the of all specifications synthesized during the specification synthesis self-evolving procedure and randomly sample a set of specifications S* that have the same size as S: naturally S* contains many low-quality specifications that not pass our Correctness or Completeness threshold. In our alternative setting of Mix-Qualing
we obtain model by fine-tuning the Round-2 SAFE model using Po[S] U P.l [S] U [2[S:]: in our alternative setting of "Low-Quality', we obtain model by fine-tuning the original DeepSeckCoder using P2[S*] alone.
From the results in Table 3 we can see that high-quality specifications contribute substantially to the end-to-end effectiveness of SAFE. If model is trained without any high quality data ('Low- Quality'), the accuracy drops for all three subsets of VerusBench and even drops to 0% Accuracy @ and 5.26% Accuracy @ 10 for SV. Probably because more debugging data is created in this setting, the self-debugging feature helps more for this setting, but the overall accuracy still lags way behind the default SAFE Round-3 model. When low quality data is mixed with high quality one, the performance still drops as shown in the fixxed-ualitty row in the table. In Appendix, we further report paired t-test results for Table 3 in Table 7 and provide an example Rust program (Listing [4] whose low quality specification leads to an extremely simple proof-the this simple proof probably offers no benefit for soooh-sy ane-tuning. In conclusion, specification selection matters the fine-tuning and the evolution of proof-synthest, models.
CONCLUSION
In this paper, we have proposed SAFE, novel self-evolving framework to advance automated proof generation for Rust. SAFE alleviates the severe data scarcity challenge by coupling data synthesis and model fine-tuning in a self-evolving manner, demonstrating superior efficiency and precision compared relying solely GPT-4o. Through ten of thousands of synthesized proofs and the self-debugging mechanism, we improve the capability of open-source models to automatically write proofs for Rust code. Our evaluation shows that SAFE has significant improvement over GPT-4o.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was partially supported by National Natural Science Foundation of China under Grant No. 92464301. Tao Xie also affiliated with the School of Computer Science, Peking Univer- sity; Key Laboratory of High Confidence Software Technologies (Peking University), Ministry of Education, Beijing, China
REFERENCES
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry. Quoc Le, al. Program synthesis with large language models. arXiv preprint arXiv:2108.07733 07732, 2021.
Jeremy Avigad. The lean theorem prover. Microsoft Research, Carnegie Mellon University. 2017.
Zhangir Azerbayev, Hailey Schoelkopf, Keiran Paster, Marco Dos Santos, Stephen McAleer, Al- bert Q Jiang, Jia Deng, Stella Biderman, and Sean Welleck. Llemma: An open language model for mathematics. arXiv preprint arXiv:2310.1063/ 2023.
Dirk Beyer. Software verification: 10th comparative evaluation. Proceedings of Tools and Algo- rithms the Construction and Analysis of Systems: 27th International Conference, pp. 401-422, 2021.
Saikat Chakraborty, Shuvendu K Lahiri, Sarah Fakhoury. Madanlal Musuvathi. Akash Lal, Aseem Rastogi, Aditya Senthilnathan, Rahul Sharma, and Nikhil Swamy. Ranking --M--eeertted loop invariants for program verification. arXiv preprint arXiv:2310.09342, 2023.
Saikat Chakraborty, Gabriel Ebner, Siddharth Bhat, Sarah Fakhoury, Sakina Fatima, Shuvendu Lahiri, and Nikhil Swamy. Towards neural synthesis for smt-assisted proof-oriented program- ming. arXiv preprint arXiv:2405.00787 2024.
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug. arXiv preprint 0315:22004.05128, 2023.
Leonardo De Moura and Nikolaj Bjørner. Z3: An efficient SMT solver. In Proceedings of Inter- national conference on Tools and Algorithms for the Construction and Analysis of Systems, pp- 337-340, 2008.
Verus Doc. Verus tutorial and reference. In http:///wwe..uugg.eiibbobooeerge reveal-hide.huml, 2024.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The LLaMa 3 herd of models. arXiv preprint arXiv:2407.21788. 2024.
Madeline Endres, Sarah Fakhoury, Saikat Chakraborty, and Shuvendu K Lahiri. Can large language models transform natural language intent into formal method postconditions? In Proceedings of the ACM International Conference on the Foundations of Software Engineering, pp. 1889-1912, 2024.
Emily First, Markus N Rabe, Talia Ringer, and Yuriy Brun. Baldur: Whole-proof generation and repair with large language models. In Proceedings of the 31st ACM Joint European Software Engineering Conference and Symposium the Foundations of Software Engineering, pp. 1229- 1241, 2023.
Conmac Flanagan and K. Rustan M Leino. Houdini, annotation assistant for ESC/Java. In Pro- ceedings of the International Symposium of Formal Methods Europe, pp. 500-517, 2001.
Kelsey R Fulton, Anna Chan, Daniel Votipka, Michael Hicks, and Michelle L Mazurek. Benefits and drawbacks of adopting a secure programming language: Rust as a case study. In Proceedings of Seventeenth Symposium Usable Privacy and Security, pp. 597-616, 2021.
11

---

Published as a conference paper at ICLR 2025
Google. CodeGemma: Open Code Models Based on Gemma. 2024. URL
googleapis wwt. dwwpmindeeendeeee www/deepmindddeeeeeeeeeeeeeeeeee
hteea///aaaaaaaaa//aaa/a/aaaaaaa mediae/eiaaaaaeeaae gemma/ cotpaa/ccddeeaaaaame pewpeeeeeaarrepprttttoo pdf
Caglar Gulcehre, Tom Le Paine, Srivatsan Srinivasan, Ksenia Konyushkova, Lotte Weerts, Abhishek Sharma, Aditya Siddhant, Alex Ahern, Miaosen Wang, Chenjie Gu, et al. Reinforced self-training (rest) for language modeling. arXiv preprini arXiv:2308. 08998, 2023.
Daya Guo, Qihao Zhu, Dejian Yang. Zhenda Xie, Kai Dong, Wentao Zhang, Guanting Chen, Xiao Bi, Wu, YK Li, et al. DeepSeck-Coder: When the large language model meets programming- the rise of code intelligence. arXiv preprint arXiv:2401.
2024.
Henry Hsu and Peter A Lachenbruch. Paired t test. Wiley StatsRef: statistics reference online, 2014.
Adharsh Kamath, Aditya Senthilnathan, Saikat Chakraborty. Pantazis Deligiannis, Shuvendu K Lahiri, Akash Lal, Aseem Rastogi, Subhajit Roy, and Rahul Sharma. Finding inductive loop invariants using large language models. arXiv preprint A.Xiv:3311.07444 2023.
Shuvendu K Lahiri. Evaluating LLM-driven User-Intent Formalizaiion for Verification-Awar Lan- guages. arXiv preprint arXiv:2406. 09757, 2024.
Shuvendu K Lahiri, Sarah Fakhoury, Aaditya Naik, Georgios Sakkas, Saikat Chakraborty, Madanlal Musuvathi, Piali Choudhury, Curtis von Veh, Jeevana Priya Inala, Chenglong Wang, et al. Inter- active code generation via test-driven user-intent formalization. arXiv preprint arXiv:2208.05950 2022.
Andrea Lattuada, Travis Hance, Chanhee Cho, Matthias Brun, Isitha Subasinghe, Yi Zhou, Jon How- ell, Bryan Parno, and Chris Hawblitzel. Verus: Verifying rust programs using linear ghost types. In Proceedings of the Annual Conference on Object-Oriented Oriented Programming Systems, Languages, and Applications, pp. 286-315, 2023.
K Rustan M Leino. Dafny: An automatic program verifier for functional correctness. In Proceedings of the International Conference on Logic for Programming Artificial Intelligence and Reasoning. pp.
2010.
Chang Liu, Xiwei Wu, Yuan Feng, Qinxiang Cao, and Junchi Yan. Towards general loop invari- ant generation via coordinating symbolic execution and large language models. arXiv preprint arXiv:2311.10483 2023.
Chloe Loughridge, Qinyi Sun, Seth Ahrenbach, Federico Cassano, Chuyue Sun, Ying Sheng, Anish Mudide, Md Rakib Hossain Misu, Nada Amin, and Max Tegmark. DafnyBench: A benchmark for formal software verification. arXiv preprint arXiv:2406.08467 2024.
Anton Lozhkov, Raymond Li, Loubna Ben Allal, Federico Cassano, Joel Lamy-Poirier, Nouamane Tazi, Ao Tang, Dmytro Pykhtar, Jiawei Liu, Yuxiang Wei, et al. Starcoder and the stack v2: The generation. arXiv preprint arXiv:2402.1 19173, 2024.
Lezhi Ma, Shangqing Liu, Yi Li, Xiaofei Xie, and Lei Bu. Specgen: Automated generation of formal program specifications via large language models. arXiv preprint 1eXiv:2401.08800 2024.
Md Rakib Hossain Misu, Cristina V Lopes, Iris Ma, and James Noble. Towards Al-assisted synthesis of verified Dafny methods. Proceedings of the ACM International Conference on the Foundations 2024.
of Software Engineering. pp.
Theo X Olausson, Jeevana Priya Inala, Chenglong Wang, Jianfeng Gao, and Armando Solar- Lezama. Is self-repair silver bullet for code generation? In Proceedings of the Twelfth ternational Conference on Learning Representations, 2023.
ONCD. Back to the building blocks: A path toward secure and measurable software. pp- 19, 2024. URL httpst::: www. wwww:wwwwwhh....c.cc..... www.nniceehhacaal.lalaaa.aaaaaaa Rewort..p...o....
Kexin Pei. David Bieber, Kensen Shi, Charles Sutton, and Pengcheng Yin. Can large language models reason about program invariants? In Proceedings of the International Conference on Machine Learning, pp. 27496-27520, 2023.
12

---

Published as a conference paper at ICLR 2025
Jeffrey M. Perkel. Why scientists turning Rust. Nature, 588:185, 2020.
Stanislas Polu, Jesse Michael Han, Kunhao Zheng, Mantas Baksys, Igor Babuschkin, and llya Sutskever. Formal mathematics statement curriculum learning, arXiv preprint arXiv:2202.01344. 2022.
Ruchir Puri, David S Kung, Geert Janssen, Wei Zhang, Giacomo Domeniconi, Vladimir Zolotov, Julian Dolby, Jie Chen, Mihir Choudhury, Lindsey Decker, et al. CodeNet: A large-scale ai for code dataset for learning a diversity of coding tasks. arXiv preprint arXiv:2105. 12655, 2021.
Elijah Rivera, Samuel Mergendahl, Howard Shrobe, Hamed Okhravi, and Nathan Burow, Keeping safe Rust safe with Galeed. In Proceedings of the 37th Annual Computer Security Applications Conference, pp. 624-836, 2021.
Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, et al. Code Llama: Open foundation models for code. arXiv preprint arXiv:2308. 12950, 2023.
Chuyue Sun, Ying Sheng, Oded Padon, and Clark Barrett. Clover: Closed-loop verifiable code generation. In Proceedings of the International Symposium on Al Verification, pp. 134-155, 2024a.
Xudong Sun, Wenjie Ma, Jiawei Tyler Gu, Zicheng Ma, Tej Chajed, Jon Howell, Andrea Lattuada, Oded Padon, Lalith Suresh, Adriana Szekeres, et al. Anvil: Verifying liveness of cluster manage- ment controllers. In Proceedings of the 18th USENIX Symposium Operating Systems Design and Implementation, pp. 649-666, 2024b.
Nikhil Swamy, Cätälin Hritcu, Chantal Keller, Aseem Rastogi, Antoine Delignat-Lavaud, Simon Forest, Karthikeyan Bhargavan, Cédric Fournet, Pierre-Yves Strub, Markulf Kohlweiss, et al. De- pendent types and multi-monadie effects in F. In Proceedings of the 43rd Annual ACM SIGPIAN- SIGACT Symposium on Principles of Programming Languages, pp. 256-270, 2016.
Zhengwei Tao, Ting-En Lin, Xiancai Chen, Hangyu Li, Yuchuan Wu, Yongbin Li, Zhi Jin, Fei Huang, Dacheng Tao, and Jingren Zhou. A survey self-evolution of large language models. arXiv preprint arXiv:2404. /4387, 2024.
Chenyuan Yang. Xuheng Li. Md Rakib Hossain Misu, Jianan Yao, Weidong Cui, Yeyun Gong, Chris Hawblitzel Shuvendu Lahiri, Jacob R Lorch, Shuai Lu, al. Auto Automated proof generation for rust code. arXiv preprint arXiv:2409. 13082, 2024a.
Kaiyu Yang, Aidan Swope, Alex Gu, Rabul Chalamala, Peiyang Song. Shixing Yu, Saad Godil, Ryan Prenger, and Animashree Anandkumar. LeanDojo: Theorem proving with retrieval- augmented language models. Advances in Neural Information Processing Systems, 36, 2024b.
Jianan Yao, Ziqiao Zhou, Weiteng Chen, and Weidong Cui. Leveraging large language models for automated proof synthesis in rust. arXiv preprint arXiv:2311.03739 2023.
Lichen Zhang, Shuai Lu, and Nan Duan. Selene: Pioneering automated proof in software verifica- tion. Proceedings of the 62nd Annual Meeting of the Association for Computational Linguisties, pp. 1776-1789, 2024.
Ziqiao Zhou, Weiteng Chen, Sishuai Gong, Chris Hawblitzel, Weidong Cui, et al. [VeriSMo): A verified security module for confidential (VMs). In Proceedings of the 18th USENIX Symposium Operating Systems Design and Implementation, pp. 599-614, 2024.
13

---

Published as a conference paper at ICLR 2025
APPENDIX
Verus Examples
15
A.1 Imperfect Proof Example
15
A.2 More Complicated Proof Annotations
17
Prompts
17
Implementation Details
17
Specification Filtering
17
Statisties of Synthesized Data
19
Training Hyperparameters
20
D) Discussion and Limitation
20
D.1 Scaling to Real-World Large Software Projects
20
D.2 Fine-Grained Self-Debugging
20
Additional Experiments
20
Statistics VerusBench
20
E,2
Distribution of Specification Metrics
21
E.3
Results of Statistical Significance Testing
Self-Evolution with Small Backhone Models
22
Case Studies
23
SAFE's 's Advantages Compared to GPT-4o
23
F22
The Elfectiveness of Our Sell Sell-Debugging Mechanism
23
An Ineffective Example
25
An Example Proof with Low Low-Quality Specification
25
14

---

Published as a conference paper at ICLR 2025
A VERUS EXAMPLES
Listing 2: An imperfect proof of binary search with its error message recieved from Verus,
use vsta: spre lude::+; main()
varua!i
// Perforns binary search scrted vector of 61-bit unsigned inzegera (u64) to find the index of given terget value. fn binary_search &Veosu64,, u64)
usi
requires //bre-conditions of this progzam
forallli:int, j:int|
<= J < v.len() v[i] v(jb,
existali:fnt
() == v[1).
10
ensures 7/post conditions this progsam
11
0 Fr
12
v.lenil.
13
=n v 55 Int
14
15
let mut i1: usize - 0; v.len()
let
17
while 11 12
18
invariant //loop inveriants (used for proof)
19
12 vol
20
7/ existsli: intl 11 <e <= 12 66 wn v(t
21
Torall 1: int, 31 int
velee()) v[i] vill.
22
23
let ix 11 + (12 11) 21
24
[[ix]
25
11 ix elee
26
27
12 ix7
28
29
30
11
31
32
33
34
messages from Verus: error: postcondition not satisfied
35
36
37
13
- vlc as intl,
failed postcondition
39
14
/
40
15
let mut il: usize 0, let 12: usize v.len() while 11 1a 12
41
16
42
17
43
...
44
30
11
46
I_" at the end of the Sunction body
47
48
possible arithmotic underflcew/overflox
49
50
let
11)
51
53
error: possible srithmetic undexflew/overflee
54
55
23
let ix (12 11)
56
57
58
error: aborting due to 3 previous errors
60
veritication resulta:: verified, errors
A.1
IMPERFECT PROOF EXAMPLE
An imperfect proof annotation of binary search is shown in Listing 2 Compared with the correct version in Listing I this imperfect proof lacks a crucial loop invariant in Line 20. According to the that postcondition cannot be proved without this
messages following the code, we loop invariant. Furthermore, the absence of this invariant causes Verus to fail to prove the absence of arithmetic underflow/overflows. Specifically, this loop invariant states that value exists in 1i1
15

---

Published as a conference paper at ICLR 2025
Listing 3: The proof code of fibonacci.
use :ptd::preldd:::>>
in main()
varva!
In (ns int) -> nat decreases a
if <= 0 else if n 1 (
ribo
ribo
10
12
spec riso_rite 132 (2r inL)
bool
13
(n) 0x8000_0000
14
15
16
proof Liboissmonooonicci int,
17
Fequ' F85
J
19
ehaures
20
(ibo (]b
21
22
23
24
25
26
ibo.is.monotonieli 1
27
assect Eiboty 1 -lbol 2117
28
29
30
In risonacol (ns usiget >> (cet: Veck132>)
32
zequires
33
Fibo (32(0 a8 Intl,
34
A
2
35
ensures
36
forail 1i3 int 2 <= 28> [=xiggerr) rct0(1)
5:bb (1),
37
Bg
38
(ec::new
40
(0);
41
fib.pash(1);
42
let
43
45
while i <
Invarlant
47
Torall
Arrigger]] [k)
48
1ibo 1Its as iRE),
<= L,
50
Fibe.len() <m Dr.
51
52
53
proof(
54
F.bo.s.monoronicii 35 int, a5 int]
55
56
let sikt_sib fibli
fibli 21;
57
58
fio.push (napptthhnext_taa (next_"bbx)
59
+-
61
63
fib
64
65
121. Without this loop invariant, Verus cannot reason about the comparison between v [ix] and k on Line 24, and hence cannot reason about how the values of i1 and i2 would change in this loop. This incapability of reasoning then leads Verus' failure in reasoning about the bound of 12 i1 on Line 23 (and hence the arithmetic underflow/overflow error), and the final value on Line 30 (and hence the postcondition not satisfied error).
16

---

Published as a conference paper at ICLR 2025
A.2 MORE COMPLICATED PROOF ANNOTATIONS
Listing shows much more complicated proof annotations for Rust function that computes the Fibonacci sequence. The proof for this code includes not only loop invariants introduced in Listing but also proof function (Lines 16-29 in the listing), proof block (Lines 53-55), and assert statements (Line 27) that are used to provide hints to the underlying theorem prover. This example comes from the Verus paper (Lattuada al. 2023), with more detailed explanation available in that paper.
B PROMPTS
Listing 4: SAFE's prompt for proof generation.
experienced formal language programmer. Verua, which is tcol for veritying the correctness of code written in Rust, Your miselon is assertions
Instructions "You
very familiar with
code, so verus can verify the give function behaves exact what is described in the specifications. the verified code "stua code block. Here the given rust coda." Input:: "rstrust (The Input Rust Programj ".
proef code, including loop invarients
given
Listing 5: SAFE'S prompt for self-debugging.
instruction "You are en experienced formal langsage programmer, You are vary Verva, which 1a tool for werifying the correctnesa of code written in Rust. Your miasion is to write correct proof oode, including 1oo9 invarients and assertiens that Verus speci fication, which is 'requires' and 'ensures', The given verus code cannot be verified, there exiata messages. Return the verified code in "uuutt code block." input "The given ruat isiin rstrust Program) 19,, and the arrer messaqes areila (**) (The Errer Messaqes] AnAn"
with
the given Rust code,
verify the give function behaves
what described in the
in the proof code. Flease he debig geven according the
Rust
C IMPLEMENTATION DETAILS
C. SPECIFICATION FILTERING
The example below shows two types of imperfect specification. The specification in the left column correct but incomplete for the binary search function, an incorrect implementation that always returns would be accepted by this specification; the specification in the right column below is incorrect, as a correct implementation may fail this specification when the input array has multiple elements matching the search key.
correct, incomplete specification. v.len(),
incorrect specification. r may > vI= 11, vis 1),
0 <m
v.len
Listing 7 shows an example of how we leverage test cases and Verus' symbolic reasoning capability to quickly score and filter specifications. For each function with synthesized specification (i.e., Lines 6-8 in Listing 7 in order to know whether this specification is consistent with a test case t, we do the following: 1) We replace the function body with Verus' assume statements. Each assume tells Verus about the value of one input output variable (these values come from the test case f); 2) When an input/output variable is a container, multiple assert statements are inserted to make sure that the underlying theorem prover
correctly reason about the value of every element in the container; 3) Verus is invoked to prove this function. If the specification is consistent with this test case, Verus verification would succeed: otherwise, Verus verification would fail.
17

---

Published as a conference paper at ICLR 2025
Listing 6: GPT-4o's prompt for proof generation.
system "You are en experienced formal language programnar, You are very familian with Verce, which tool veri syritying co"reatness code written in Rust."
instruction
4 Your miasiona to
1. Add loop inverients to the given Rast code, if there are lcops in the code, so that Veruz verify the give function behaves
what described in the specifications 2. Add the proof blocks that could help Verus to prove tha folloring anda snippet. You need to analyse which locations
blocka to help Verua to prove the correctness of the code, You can insert miltiple prouf blocks in the code as long
proved and as they are necessary to prove correctness variables that could help
code. You the correctness of the code.
include ghost
The proof block looks like this:
10
proof
11
// your proof code here
assert I...)
13
// PLWAT_ONNTIONN....
14
//
15
Added
16
17
18
# Step 1: add Loop invariants
please follow thase steps in adding loap invariants for every loop:
20
1. You should identify every variable that is read in the loop (e.g., x(s), particularly for acray elements like x(k], and add on invariant about the initial value for EACH such variaale
array;
21
2. You ahould identify every variable that la weitten (e.g.r
x.set ) in every if invariant already
locp, add an invarient about the value that variable. specified earlier in the program, please do repeat it in every loop suitable. invariant.
3.
can leverage the apea functions and proof funations
23
24
# step 2: Constant propagotion refinement
25
26
If an uppec bound oz lower bound about constant funetion paramete: (e.g.r X c ... X ...) provided
function pre-condition fL.e., in 'requires' code block at baginning of the function),
27
p ease copy that (e-g., 10, > 5) loop invariant every loop the function,
28
aven if invariant alresdy specified earlier the program, please do repeat it in every cop suftable.
29
30
# Step 3: Array length refinement
31
32
For every loop in the function, please identify avery array that is read (e.g., x(k)) or written (e,g., x.aet (. (.) in it, and then add 1oop invariant that spectfies the Length of the array (1.e., x.len() ...).
33
34
SLep Quantifier range refinement
35
following steps to check every loop invariant that involves arrey (e.g., x k|l in the given Rust code:
Please
37
IF this azray x[k] has been modibled in this 1oop through x.set (), leave this invariant as it is, do NOT make any changes, and
the next invarient.
38
Otherwiae, when there is no x.set 1) in the loop, please make sure that the Invaziant covera every element shatever-property. when you make this change, please use comment to explain why you believe the related grray never changed the lcop. Do NDT make any other changes the loop invariant!
array and bence
the forn
'forell [krine]
x.lea
39
40
# Step Conditionsl leop invariant refinement
41
42
refine some loop invariants the given Russ code only if the Loop has special handling for the first steration, This is what you should dot if existing loop invartant holda for all iteracions variable updates
Your mission
loop except for "tret iteration (e.g., some only (not) occur during the first loop iteration), please leave P it is and add another loop inveriant conditioned on the loop index (e.g., index 0 may P), following the example below.
43
Du not change e or any other loop inveriants in any other way. n**
44
As mentioned earlier in the paper, evaluate the completeness of specification, mutate existing test cases to see whether incorrect test cases can be rejected by a specification. In this example, we mutate the output in the ground truth by adding new value 15 into result vector. In this case,
18

---

Published as a conference paper at ICLR 2025
Verus will report that the postcondition Line fails because 15 does not exist in vector a. If synthesized specification does not contain something like Line 7, this mutated test case will likely point out the incompleteness of that specification.
In our experiments, we take ground truth test cases and 20 mutated wrong test cases on average for scoring. We filter all the specifications that have score lower than 0.8 in correctness 0.6 in incompleteness. To avoid too many specifications being preserved for single program, we allow most three specifications be preserved for a single function.
Listing 7: An example used for scoring and filtering based on test cases.
use sptd:::grodddd::
in main() []
varua!!
pub En ShacedBlements (a: Vec<132>, bi Veoci32>, result: Vee<132>) ensures
forall [krint] 0 <e k result.lent (en()) ma> (f[trigger) a8.contains (result(k)) sa +1 trigger] bg.contains treaul tr (())),
8
Torall Milrint,kiiaat 0 <= kl < k2 resclt.ien() --> [klul][k]] !- result (k2),
10
11
assume (ad -"- seg! [11, 12, 14, 13]1; assume
seqi [17, 15, 14, 13117 assume (result@ = seg! [14, 13));
13
15
assert (a[0) 111;
16
assert (a[1]
121:
17
assect
18
assert (a[3] -- 1317
20
assert [0]
171:
21
assert (b[1]
151;
22
(b
1417
23
assert (b[3] -- 131;
24
25
assert (result [0] == 1414
assert (result 1312
27
28
C.2 STATISTICS OF SYNTHESIZED DATA
As explained carlier in the paper, obtain 45,495 Rust fingle-function programs from the MBPP training set and CodeNet dataset. After translating them into Verus-compatiable Rust programs, have 21,398 programs left for specification synthesis. The statistics of all synthesized data in different rounds of our self-evolution process are shown in Table Note that, at the very beginning, we put aside a random subset of CodeNet Rust programs be used for the evaluation of SAFE. Those programs do not participate in the fine-tuning and are not included in the numbers shown in Table
In round 0, we employ GPT-4o to synthesize specifications, retaining only the verified Rust functions along with their specifications. This process 3,673 verified programs. Even with our designed prompts, GPT-4o needs to sample 20-30 times for a single program on average. We then use the synthesized specifications evolving specification synthesis process, which is conducted over two rounds. In each round, we leverage the fine-tuned model to generate specifications for 21k Verus programs and select the high quality ones for further fine-tuning, At the end, we use the selected 19,017 specifications as inputs for the proof synthesis procedure. The numbers verified programs and debugging fine- tuning triplets also shown in Table 4 As we see, many 9,706 verified programs and 10,486 debugging data are produced after the Round-2 2 model and are used to fine-tune the Round-3 model, being the final proof-synthesis model.
consuminn,, taking an entire month to synthesize
bootstrap the self-
19

---

Published as a conference paper at ICLR 2025
Table 4: Statistics of synthesized data
Verus programs
All spees
Selected spees
Verified programs
Debugging data
Seed
21,398
Round-0
3,673
3,673
0
Round-1
102,549 117,759
16,530
8,368
9,910 10,486
Round-2
19,017
9,706
C.3 TRAINING HYPERPARAMETERS
Bootstrapped by 3,673 verified programs synthesized by GPT-4o, we employ the DeepSeekCoder model (Guo et al. 2024 the generator in the self-evolution procedure. We run the self-evolving specification generation and auto-pres auto-proving process for multiple rounds. For specification generation, run rounds. Proof generation three. At each round of fine-tuning, combine the verified programs and self-debugging data pairs together as training data, and train DeepSeekCoder 5 epochs, using a batch size of 128 and learning rate of 1 10-5.
D DISCUSSION AND LIMITATION
D.1 SCALING TO WORLD LARGE SOFTWARE PROJECTS
In this paper, we have focused on generating proofs for small programs mainly because there are too few existing large Verus projects for us to fine-tune LLMs. Consequently, just like many code- synthesis projects that start from small programs, we also focus small programs a starting point for Verus proof synthesis.
Since every function is the unit for Verus verification, we believe that the LLM fine-tuned by SAFE on functions in small programs would continue to useful for functions in large projects. Of course, if apply SAFE synthesize proofs for large Rust projects, expect key challenge in how to resolve code dependencies across functions. Specifically, a function may call another executable function specification function, and the callee function may exist in different file and/or belong to different class. How to resolve all the code dependencies and provide LLM with all the needed information may require support that goes beyond machine learning.
D.2 FINE-GRAINED SELF- BELF-DEBUGGING
Figure 2 illustrates that increasing the number of self-debugging rounds hardly improves proof- synthesis accuracy. This situation might be changed if we change the formation of our self- debugging training data. Currently, the training data for self-debugging includes many pairs of incorrect proof Yx and a corresponding correct proof Yv. Sometimes, the incorrect proof may con- tain many mistakes, causing many different verification errors. If future research can break down the difference between Yx and Y/, figuring out which edit in Y/ is used to fix which verification error in Yx. the resulting data can probably train model that is better fixing deeply flawed proof through multiple rounds of debugging.
E ADDITIONAL EXPERIMENTS
E. STATISTICS OF VERUSBENCH
Figure illustrates the distributions of the number of tokens in specifications and proofs in Verus- Bench. For preconditions, in Figure we show that SV's average number of tokens is substantially larger than that MBPP and Tutorial. In contrast, SV's average number tokens is substantially smaller than the rest two as shown in Figure 3b Such statistics can, to some extent, reflect the difficulty of three components in VerusBench, i.e., SV is relatively easiler than the rest two. When comparing the Hommnn-writee proof annotations for MBPP and Tutorial programs in VerusBench, Figure 3e shows that the average number of tokens of proof annotations in MBPP is larger than that of Tutorial, although there are some outliers.
20

---

Published as a conference paper at ICLR 2025
(a) The distribution of the number (b) The distribution of the number (c) The distribution of the number of tokens in preconditions
of tokens postconditions of tokens in ground-truth proofs
Figure 3: The statistics specifications and proofs VerusBench
E.2 DISTRIBUTION SPECIFICATION METRICS
FigureAshows the distribution of the correctness-scorc and the completeness-score of all the spec- ifications synthesized during the self-evolving process of SAFE. As we can see, during the self- evolving process, many trivially correct specifications are generated (i.e., 1.0 correctness score but < 0.6 completeness score) the clusters the top of the figure and not overlapping with the gray rectangle. These specifications tend to lead to trivial proofs and hence are filtered out. There is also big cluster of incorrect specifications that have incorrectly rejected all test cases the bottom-right corner of the figure (i.e., 0 correctness score but 1.0 completeness score). There no way Verus prove that the Rust function satisfies these specifications, matter what proof annotations used, so it is good that SAFE filters all of them out.
E.3 RESULTS OF STATISTICAL SIGNIFICANCE TESTING
SAFE Compared Raw Models. Table shows the p-values between SAFE under various set- tings and its base models. We highlight p-values that are larger than 0.05 in italics. From this table, can observe that the p-values of all fine-tuned models (LLaMMa and DeepSeekCoder) are less than 5E-7, indicating the significant improvement of SAFE.
Table The p-values of SAFE's accuracy compared to raw models; non-significant data (p 0.05)
points are pointed out in Italies
GPT-4o
LLaMa3.1-88
I-S-ntrreetttttt
DeepSeekCooder-33B-Ine Instruct
Benchmark
Accuracy
SAFE
SAFE
SAFE+
SAFE
SAFE+
Accuracy@ @
2.01E-03 4.69E-03
4.68E-11
3.88E-14 14
2.34E-09
6.33E-13
VerusBench
Accuracy @ 10
5.39E-07
5,23E-12
5.39E-07
1.53E-15
Accuracy @ 100
8.67E-31
9.25E-45
2,45E-34
5.15E-64
CodeNet Test
Accuracy@1 @1
0.08
2.26E-122
1.07E-24
1.54E-142
1.51E-215
Comparison between Various Rounds of Self-Evolving. Table 6 shows the p-values of SAFE'S accuracy between various rounds of self-evolving. We highlight p- p-values that are larger than 0.05 in italics. When compared to round 1, round and round 3 show significant improvement in Accuracy, especially after self-debugging. Additionally, we also show that there insignificant improvement between round 2 and round except the accuracy in Tutorial after self-debugging. Thus, three rounds of self-evolution are sufficient for our approach.
Comparison between SAFE's Accuracy with Low/High Quality Specifications. Table shows the p-values of SAFE's accuracy between round 3 and low quality ones. We highlight p-values that larger than 0.05 in italics. We show that in most scenarios (except Accuracy @ 1 in round 2 low quality specifications), low quality specifications might lead to a significant decrease in terms of SAFE's end-to-end effectiveness.
21

---

Published as a conference paper at ICLR 2025
1.0
30000
0.8
25000
Number of Specifications
Correctness
Selected Area
15000
0.4
10000
0.2
5000
0.0
0.2
0.4
0.6
0.8
1.0
Completeness
Figure 4: The correctness and completeness distribution of SAFE synthesized specifications. The coordinate of the center of every circle indicates the Completeness- score (x-axis) and the Correctness-score (y-axis) of the corresponding cluster of specifications; the size and color of each circle reflect number specifications that are in one cluster. The gray rectangle highlights range of accepted scores: all the specification clusters that overlap with the gray rectangle sidered good enough and hence kept by SAFE.
Table 6: The p-values of SAFE's accuracy between various rounds of self-evolving: non-significant data (p > 0.05) points are pointed out in Italics
Paired T-Test Rounds
Proof Generation
Self- Self-Debugging
SV
MBPP
Tutorial
Total
MBPP
Tutorial
Total
Accuracy
1.09F-03
4.40F-11
6.66F-07
2774--3
2.30F-03
Round &
Accuracy@ 10
0.06
1.00
9,14E-11
0.15
7.97E-03
1.00-005
5.24E-13
3,60E-05
Accuracy @
19F.05
0.79
3.04F-07
0.06
1.36F-05
0,06
3.04F-07
4.98F-03
Accuracy@ 10
7.97E-03
0.37
5.24E-13
4.12E-02
1.67E-05
L.70E-06
L.1E-21
9,11E-07
Accuracy @
0.33
0.79
0.12
1.00
0.53
0.63
10F-002
0,87
Round
Accuracy @
0.41
0.37
0.47
0.72
2.86B-02
0.44
E.4 SELF-EVOLUTION WITH SMALL BACKBONE MODELS
To evaluate the effectiveness of our self-evolution framework on LLMs with smaller number of parameters, conduct additional experiments using DeepSeckCoder- (DSCoder-1.3B) the backbone model. In this experiment, we follow the same experimental settings described Sec- 4.1 bootstrapping DSCoder-1.33 with GPT-4o's predictions.
22

---

Published as a conference paper at ICLR 2025
Table The p-values of SAFE's accuracy with low quality specifications, compared round 3 with high quality ones; non-significant data (p > 0.05) points are pointed out in Italics
Proof Generation
Debuggnng
Data Source
Metric
MRPP
Tutorial
Tutorial
Low Quality
Accuracy 601
5.15E-64
0.79
3.04E-07
3.221-006
3.62E:71
0,72
0.49
1,98E:04
Accuracy 10
4,04E-87
0.53
9.39E-08
5.38E-08
8.66E-71
0.15
3.26E-03
4.79E-07
Accuracy @
1.94E-13 2.78E-08
8.07E-02
2.45B-02
1.71E-12
Mix-Quality
Accuracy @ 10
0.53
2.27E-04
3,05E-02
5.34E-10
0.23
2,86E-2
2.51E-02
Table Each round's accuracy with DeepSeekCoder-11 1.3B as the backbone model
Proof Generation
Self Debugging (l: * k:)
Metric
Accuracy
Accuracy @
Accuracy@)
Accuracy
Raw
1.44
6.47
Round 1
12.95
24.46
12.95
24.46
Round 2
19.42
26.69
24.46
52.52
Round 3
21.58
40.29
27.34
57.55
After the same rounds of self-evolving specification generation and proof generation, the results on VerusBench are listed in Table 8 The results indicate that our self-evolution framework effectively improves the accuracy even with a smaller backbone model of 1.3 billion parameters.
F CASE STUDIES
F.1 SAFE'S ADVANTAGES COMPARED TO GPT-40
To demonstrate the effectiveness of SAFE, we show an example proof generated by GPT-4o without our prompts and SAFE in Listing 8 and Listing respectively.
In Listing 8 GPT-4o introduces four loop invariants, specifying that (1) the index variable does not exceed the length of input array xlen; (2) the length of the input array remains during the loop; (3) the values of the first i elements are equal to their original values plus 4; (4) the values of the rest elements are equal to their original values. However, GPT-4o neglects to include proofs to address the potential arithmetic underflow/overfflow thus leading the errors reported in Lines 30-64.
In contrast, SAFE addresses this error and successfully generates a correct proof for this program. Listing/]shows correct proof generated by SAFE (DeepSeekCoder). Compared to GPT-4o's 's proof, adds another loop invariant Line 19 pointing out that the original values of the input array are less than equal OXFFFFrrE, thus addressing the ari thmetic under wwwp//wwwwww..ooooooooooweooolle error. SAFE's effectiveness mainly credits to our self-evolution framework.
F.2 THE EFFECTIVENESS OF OUR SELF-DEBUGGING MECHANISM
In Listing 10 and Listing II we demonstrate the effectiveness of our self-debugging mechanism during proof synthesis with another example. This example program checks whether a given ar- ray is sorted by checking whether there exists a pair of adjacent elements where arr [index] arr [index
1].
I Listing 10 shows the initial proof generated by SAFE, including loop invariants: (1) the index does not exceed the length of the given arryy; (2) all elements before the current index satisfy the 'sorted'' property. However, during each iteration of this loop, this program checks the current element against the next and terminates the loop when index equals len result, the loop invariants fail to account for the last element, leading to the error described in Lines 29.41.
As
SAFE successfully fixes this emor via self-debugging. The error message clearly indicates that the ndex cannot be verified. Using
loop invariant forall Hi: int, j: intl 0
23

---

Published as a conference paper at ICLR 2025
Listing 8: An incorrect proof of myfum2 generated by GPT-4o.
use vutd::preluda::>
in maii())
varva!!
pub In my 1x: smut Vec<132>)
zequices
forail [k:int
Jen()
enaures
XF xF.len() Fld(x)..leatl forail [k:int]
x.len() [trigger] xē
11
12
let mut i: usize 0y
13
let xlen:
x.
14
while xlen
16
3 <= <e xien, xe.len() o1d
17
18
fcrall Ik:int/
[[trigger] xF] old(x)
19
Torall [ksinti k Xlen and XB[K] =- old(x)((k),
20
kis x(i] + +
22
24
25
26
27
aote: while loop: net all ecrers may have been seported; recun with higher value for mitiple-esrozs find potentisl this
28
--> /pllyyrrond//rr//minnnr......
30
14
/
while i xlen invariant
31
15
32
16
<= i xlen,
33
17
(e =- old (xlleen)),,,
35
22
1-1+1
23
37
38
39
recommendation
40
--> btlayrround/stc/msin..o 1s:18:33
42
18
forall [k:int] D <= ceck an> [trigger] жE[K] (x)
43
44
45
::
http://orrrr/ttt/t//o....aaa wttpe////////////eeeeeeeeeeeeeee rttp///...r..........e.o.e 18
46
47
62
0. <= i len
recommendat fnn not
49
50
51
52
error: precandition not satisfied
53
54
X. (1, x11] 417
56
57
58
59
60
old(self) ()
61
failed precondition
63
64
error: aborting due to previous errors
this feedback from Verus, SAFE modifies the boundary condition in that loop invariant, i.e., the ranges of the variable i and j in that invariant. The adjusted invariant forall li: int, j: intl 0 < index allows Verus successfully finish the proof.
24

---

Published as a conference paper at ICLR 2025
Listing 9: The correct proof of myy'un2 generated by SAFE.
use spre::proldd
in main()
verual:
pub myfun2 Ix: 6mut Veck1 32>)
requices
forell [k:int] C c= à
-a> (ld [K] c- DETE
enaures
XE lenlen() old(x)8. (ea
forell [k:int 0 c= à x.len() ma> [[trigger] x [k] -- cld(x) [k]
11
let mut i: usize
12
let xlen: usize x.len()7
13
while xien)
14
invarlant
K xien,
16
lenlent) (1d
17
Torall Ik:int| D <- any [[trigger] X8 [K] (x 4,
forall [k:int]
xlon x8[k] (x)
forall [krint]
PEPB,
20
21
x.set x(i] + 4)
22
1+11
23
24
25
27
verification results:: verified, ercors
F.3 AN INEFFECTIVE EXAMPLE
We report that SAFE fails to generate correct proof for 20.86% of the programs in VerusBench, even after sampling 100 proofs and 100 debugged proofs for each incorrect proof (i.e., Accuracy @ 100). In Listing 12 and Listing 13 analyze example where SAFE fails generate correct proof. This program removes odd numbers from a given array by scanning the input array arr and append- ing the even numbers to new array, even_list.
Listing 12 shows that SAFE successfully generates the main structure of the proof, verifying that the elements in even 1 st correspond the elements in the first nndex elements of However, Verus reports errors indicating that the loop invariants are not satisfied both before and after the loop (Lines 34-44 in Listing 12). Even under the Accuracy @ 100 setting, where 100 100 debugged proofs are generated, SAFE encounters similar errors, and fails to generate a correct proof.
The root cause of this error is that proving this program needs to add assert statements and leverage the reveal feature of Verus (Doc) 2024). We suspect that the reveal feature never synthesized in any finetuning dataset, so the final SAFE model also lacks sufficient domain knowledge to prove this program. This limitation can be substantially mitigated by incorporating larger and more diverse training set during the initial round of self-evolution.
F.4 AN EXAMPLE PROOF WITH A LOW-QUALA SPECIHCATION
In Section 4.3.3 we demonstrate that the quality of specifications contributes substantially to the end-to-end effectiveness of SAFE. Listing 14 presents example proof with low-quality spec- ification. This program computes the greatest common divisor of two integer numbers using the Euclidean Algorithm. However, this specification merely requires that the result be greater than zero, 'result > 0"', without ensuring that the result should be divisors of both inputs a and
Programs with such low-quee wow-quality specifications might lead to extremely simple proofs, which are very different from proofs in more realistic tasks. For example, the proof annotations synthesized in Lines 16-17 simply copy the function precondition-s. can rarely get done this way. Consequently, putting many proofs with this quality (i.e., all resulted from low-quality specifications) into the fine-tuning dataset does not help model's evolution.
0 and b > 0. For more realistic tasks, proofs
25

---

Published as a conference paper at ICLR 2025
Listing 10: An incorrect proof of is_sorfed generated by SAFE before self-debugging.
use vpre: ludei1d
in main() [ varua!
fn ia_sorted SVen<132>) -> (fa_sorted: bool)
requires
lrr. ensures
so.tte (Sorallli: int, 1: int acr.lenfi
Jarr [1]
acz (i))
11
let mut index D: while arc.len()
13
invariant
Tncex llr Torall
15
int
16
17
arr [index] arr [index + 1] | false;
18
19
20
21
23
24
// verus!
25
26
Error messages from Verus:
27
errer: postcondition satiefied
28
--> sllaytrousd/sr//mmin.coo
29
30
9
la_sorted =- ("orallli: int, 1: int D ce < ler aa> (arr[l] < a
31
failed this pastcondition
32
10
/1
33
11
let mut Index - 3;
34
arc.len() inveriant
35
13
37
22
true
38
23
39
1_" at end funotion body
40
error: invarient satisfied,
loop body
42
--> /pl.yyroooddarrr/m..i...........
44
15
Iorallll: int, J: intl 0- index (arr[i] <- airlll),
45
46
47
error: aborting due to 2 previous errors
49
Standard Cutput
verification resulta:: verified, errors
26

---

Published as a conference paper at ICLR 2025
Listing 1I: The correct proof of is.sorted fixed by SAFE after self-debugging.
In main() 1
verua!
in is (s_sorted aVeer132>) +> (is_sorted: bool]
requires
arr.lan() 2 D2
1e.sorted =. (forsllli: int, ): int
(acz [1]
(51))
10
12
wht le Index < arr.len 1
13
invariant
14
<= index
len()
15
arr.len() > C,
forall SEE, 3: int
3.1 me> [arr
arr (1)),
17
18
orr [indox] > arr (index 1] return faise;
20
1;
22
23
true
24
25
// verca!
26
27
varification results:: 2 verified,
errors
Listing 12: An incorrect proof of remove odds before and after self-dehugging.
vetd::prelodd:::)
In maint) U: verus!
In monoe_oddss sVeosu32>) -> (even_List: Vecsu32>)
eveallist@= arrd. Eilter ix: u32 8 01,
even_list: Veccu32> Vec::new<);
10
let input_len arr.len()
12
let mut index while index err.len()
13
14
invariant
15
0 <- index <= imput_les,
77 following is changed loop inveriants
self-debugging.
17
cven-liat@es arrê, filter :32] 2 en 0) take (index) col lect
18
77 The Following is the changed loop inverients aEtes: self debugging
19
even_list@m stzf.filtes(ike (Ix: =32] x $ == 0) bake (index as int] .flter u32] x 8 0),
20
21
22
if [index] & 01
23
even_ (arr
24
25
26
27
avan_list
28
29
// verua!
31
error: irvariant
loop body
33 --> (playsroons/sreemiiii.r.r..
34
35
take filter 0),
36
37
38
error: invarient not satisfied before loop
/playground/srr/meiinn rs:19:13
40
41
19
even aven_ Hate arrd. take as Intl. ffller u321 x 2 -- 0),
42
43
The changed loop invariants before and after self-debugging are marked in red and + green.
27

---

Published as a conference paper at ICLR 2025
Listing 13: The ground truth proof of remove odds.
use veld: vstd: spreludeing
In main() (
verus!
in remave_odds (arr: (Veeku32>)
leven_list: Veccu]2>)
ensures
Bven_ cirtr u321 X O1,
let mut even liat: Veocu32> Vectsnew (1 input_len a)).len();
11
12
assert (arrd. fflterr() u32) x
:eg::<u32>+ :1mpty
index
14
while Index arr.len invariant
15
16
<m index ())
17
evet_1ist@=s arre.take (index as int) filterr (|x: #32| x == 0),
18
19
(azr (index) 2
0J
20
even Htt. wts...pp.hhhie. (arr (arr (index));
21
22
assert (orrg.taka Tindex 11 05 int) drop. drtp..aass. last =s arre. take [index as intll revea (Seq::filter);
23
24
index 1-
25
26
(asrd=s
27
list
28
29
// verus!
31
verification results:: verified, errors
Listing 14: An example proof of god with low quality specification.
use lodd:::?e
In main() (
verus!
In gedia: u32, by u321 requires
(cesult: u32)
D 37
O2
10
result 0,
11
12
let mut bi
14
le 1=
invariant
16
0,
17
5 >= C,
18
19
let temp = by b; temp:
21
22
23
24
25
26
verification resulta:: fiedf errors
28


Reviews:
[{"review_id": "uz9z3Wghvd", "reviewer": "Reviewer_73u5", "summary": "This paper proposes SAFE, a data generation and fine-tuning procedure for improving LLMs in generating proofs for the correctness of Rust code. SAFE consists of three stages: (i) verus-compatible code generation, (ii) self-evolving specification synthesis, and (iii) self-evolving proof synthesis. During stage (ii), SAFE leverages a symbolic and quantitative measure based on the correctness and completeness of the specification. For stage (iii), SAFE fine-tunes both proof generation and repair models. The experiments demonstrate the advantages of SAFE: it significantly improves the performance, compared to both the base model and GPT-4o.", "questions": "Please address the points raised in the “Weakness” section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper studies automating proof generation in formal program verification with LLMs, an important direction with great potential for practical applications. The focus is on Rust, a relatively new language that is gaining widespread adoption. Although synthetic data generation for fine-tuning LLMs is not a completely novel idea, the paper introduces a few interesting techniques for the domain of proof generation for Rust. I particularly like the metric for filtering high-quality specifications. The evaluation is thorough, demonstrating the benefits of SAFE over baselines and the effectiveness of its individual components.", "weaknesses": "The paper only focuses on small programs in the style of MBPP and CodeNet. Although I understand this is partly due to the limitation of the Verus tool, I do believe that the paper should present some case studies or discussion on how to scale the approach to real-world software projects.\n\nApart from proof generation, a major part of formal verification is writing the specifications. The paper covers mechanisms to fine-tune a “good” specification generation. It would strengthen the paper if more evaluation can be done on the specification generation task and how it can be combined with proof generation to automate end-to-end verification.\n\nThe paper lacks a study on the choice of the correctness and completeness thresholds for the specification metric.\n\nThe paper writing can be improved. Below are some issues I found or some recommendations:\n- The text in Section 3 is sometimes ad-hoc and contains low-level details (e.g., choice of parameters). I would be helpful to revise the text to be more formal and move the details to later sections.\n- Line 289: The paper says “much previous work relies on running many test cases” without providing any references.\n- Line 519: Table 2 should be Table 3\n- Table 3: The split of model names to multiple lines is confusing. I thought one line of text corresponds to one single baseline. The $\\Delta$ rows look redundant as well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YrdrV5Eli2", "reviewer": "Reviewer_aKrU", "summary": "This paper introduces SAFE, an innovative framework designed to address the challenges of automated proof generation for Rust code, SAFE overcomes the significant data scarcity issue ( i.e., there is far less proof data than code data for training language models) by using a self-evolving approach to synthesize specification/proof data and fine-tune models iteratively. SAFE operates through a feedback loop where synthesized proofs are continuously verified by a symbolic verifier, distinguishing correct from incorrect proofs. Incorrect proofs are used to train the model's self-debugging ability, while the correct proofs are used to improve the model for the next round. The design of the approach is smart and uses the insight that (1) using a quantitative metric to select high-quality specifications for fine-tuning; (2) we only need reasonably well, instead of perfect specifications to fine-tune in the next step; and (3) Verus can quickly tell correct proof from incorrect ones, which enables the collecting and filtering of large amount of data.\n\nSAFE achieves a substantial improvement, attaining a 70.50% accuracy on a benchmark set crafted by human experts, a notable advancement over GPT-4o's performance of 24.46%. SAFE also obtains self-debugging ability using the incorrect proofs collected during the data collection step. Experiments show that each round of self-evolving improves the accuracy of SAFE, and proves the importance of using high-quality training data.", "questions": "1. A clarifying question about the self-evolving data: The data collected through GPT-4o (round 0) is used to fine-tuned the first specification/proof generation model. What's the data input used to let the generation model generate data for then next round? \n* Are these data the same programs as those used in the generating round 0 data? If this is the case, would the training data in each round kind of repetitive and lack of diversity?\n* Or does author use some strategies to leave some unique programs for each round, so that the fine-tuning data for each round contains different programs?\n2. Self-debugging is quite effective and improves the accuracy, how does the model obtain the ability of self-debugging? does the fine-tuning procedure contains self-debugging training data?\n3. Why are the baseline models prompted with 4 examples instead of more examples?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper proposes a novel approach that use self-evolving to iteratively improve LLM's ability of generating Rust specification and proofs. The fact that this approach does not rely on larger LLM such as GPT-4o in the following iterations (except the first round) makes it more generalizable and scalable.\n2. The proposed approach shows great effectiveness, with three round of self-evolving, the fine-tuned LLM shows about 40% higher accuracy@1 compared to the prompting approach.\n3. Comprehensive analysis and experiments, showing that each round of 1, 2 and 3 brings some improvement to the fine-tuned LLM (although the round 2 model is better than the round 3 model under some settings), and showing that high-quality specifications important to improve the model's accuracy during self-evolving.", "weaknesses": "1. The self-debugging ability is shown to be only effective for the first time, what could be potential approach for improving the self-debugging ability in the following rounds?\n2. I am wondering if this self-evolving approach can improve smaller LLMs ability. For instance, if the backbone is DeepSeekCoder-1.3B, how effective is the self-evolving approach?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "t709a3IAlB", "reviewer": "Reviewer_K5mr", "summary": "The presented paper proposes a method to bootstrap training data for generating proofs of Rust code using LLMs. The pipeline starts from a small set of curated programs and gradually evolves using the verifier as signal for dataset curation. Finally they evaluate the resulting fine-tuned LLM and show state of the art results on a difficult dataset of low-resource correctness proofs.", "questions": "Please provide a short statement or clarification to the points raised above.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The paper is well-written and nicely structured. The figures and tables are well formatted and legible.\n- The story is engaging and the tackled topic highly relevant.\n- The results are clearly presented and provide interesting insights.", "weaknesses": "- In Table 1 the Accuracy of GPT-4o on VerusBench @100 is unfortunately missing (likely due to high inference cost?). Similarly the result of DeepSeekCoder RAW @100 is missing. If the authors could provide these values, the tables would provide a much more complete picture.\n- In Table 2, Round 3 appears to severely degrade performance of the resulting model on the Tutorial dataset. Does this constitute some first signs of overfitting or collapse or could the authors provide some more insight on what is happening here? It might be interesting to provide some basis on deciding where to stop the iterative process.\n- There is no discussion of Limitations. While the provided method is clearly powerful some discussion on potential limitations would be highly appreciated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Iyp60m3Ja0", "reviewer": "Reviewer_hvY6", "summary": "This paper seeks to finetune a code-generating LLM to generate verification annotations for code.\nSpecifically, the authors target Verus, which is an SMT-backed automated-theorem-proving-style verifier for Rust code.\nThe key technical challenge that the authors thus need to overcome is that ths is a very low resource language,\nso simple techniques such as finetuning aren't directly applicable; and even API-backed models do so poorly\non this task that naively distilling wouldn't help, either.\nInstead, the authors basically bootstrap the finetuning process as follows:\n- First, they generate a set of proof *specifications* for some Rust programs using GPT-4o. They then filter out specs which are \"low quality\", e.g. those which are always true.\n- Then, they use these specifications to generate (against using GPT-4, with some expert-crafted task-specific prompts) proof *annotations* for a small subset of these specifications.\n- Finally, they bootstrap a finetuning process from these initial annotations, training in each round the open-source model on the correct proofs it generated in the last round.\nThere's some additional bells and whistles, such as also training on incorrect proofs by framing it as auxiliary repair task, but I believe this summarizes the core idea.\n\nIn terms of the experiments, the authors share results both for a small, human-written benchmark and for GPT-transpiled versions of MBPP and SV.\nAt first glance I was a bit worried about the scale of this data, but given the novelty of the task and the relative lack of Rust datasets in the literature I actually commend the authors on their effort to collect as much data to evaluate on as possible.", "questions": "- In table 2 you report a \"total\" column; I noticed the numbers don't add up if you just take the mean of the other columns, so I presume what you're actually doing is taking the mean over all of the samples in the entire dataset? (I think that's what you want to do, I just want to make sure I understood correctly).\n- When constructing training data for the repair task, are you doing any filtering to make sure that the \"incorrect program\" is actually similar to the \"correct program\", or could they be completely different?\n- What is the difference between SAFE and expert iteration, other than your synthetic data generation for the specifications?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 4, "strengths": "I think the core ideas in this paper are very interesting, and that there are several good contributions here:\n- Filtering the specifications based on a symbolic, deterministic score computed from the tests seems like the right thing to do, and I appreciate the brief ablation study of the impact of this step (section 4.2.4).\n- The experiment in 466-474 provide further evidence for previous findings in the code generation literature about \"sampling+greedy\" self-debugging outperforming \"greedy+sampling\" (I recommend that the authors consider explicitly comparing these results to e.g. [1, 2]).\n- Perhaps most importantly, verifying Rust code is not only potentially impactful but also (as far as I know) a completely novel task; kudos to the authors for going through the effort to collect all the data.\n\n\n[1] \nTeaching Large Language Models to Self-Debug\nXinyun Chen, Maxwell Lin, Nathanael Schärli, Denny Zhou.\nInternational Conference on Learning Representations (ICLR), 2024.\n\n[2] \nIs Self-Repair a Silver Bullet for Code Generation?\nTheo X. Olausson, Jeevana P. Inala, Chenglong Wang, Jianfeng Gao, Armando Solar-Lezama.\nInternational Conference on Learning Representations (ICLR), 2024.", "weaknesses": "There are a few rather major flaws that make me hesitant to recommend the paper for acceptance in its current format.\n\nOne is that I find that the paper tries a little bit too hard to sell the novelty of this \"SAFE\" approach.\nBootstrapping finetuning of LLMs by interleaving it with search has been done before; most people call it \"expert iteration\" [3] (authors: please correct me if you think there is a *significant* difference between your method and this).\nEspecially what you call \"SAFE_0\" feels a bit rich: unless I am mistaken, you are literally just doing synthetic data generation with GPT-4o and filtering the results based on some measure of quality.\nAlso, on line 359 you say \"21,398 [programs] have been successfully transformed [...] by SAFE\"; unless I'm mistaken you mean \"by GPT-4\" here, because at this point you haven't done anything other than asking GPT to first transpile the code to Rust and to then transpile the Rust code into the subset of the language that is supported by Verus.\n\nI would encourage the authors to tone down the language a bit more and focus on the actually novel parts of this paper, which I believe to be: the task target; finetuning on repair tasks to improve generation performance; and the metric used to filter the specification samples.\n\nA more important issue is that I do not think the comparison to the baselines is fair in its current form for the \"SAFE+\" method.\nThe authors themselves point out that in this variation (i.e., when you do a round of self-debugging if the initial generation does not succeed), they generate `k * k` repair samples - how can you then compare against pass@1? You have actually drawn `k + k*k` samples from the model, so you should at least compare against a baseline of `pass@(k + k*k)`.\nThis is an issue that has come up again and again the self-debugging/refinement literature, and I once again encourage the authors to engage with that literature.\nYou still have good results here - for example, the SAFE+ pass@10 is substantially higher than the SAFE pass@100 on VerusBench - but the way you're currently presenting them overstates their significance.\n\nFinally, the writing could use some more proof reading, especially the abstract and the introduction (but this is a minor complaint).\n\n\n[3] \n@misc{polu2022formalmathematicsstatementcurriculum,\n      title={Formal Mathematics Statement Curriculum Learning}, \n      author={Stanislas Polu and Jesse Michael Han and Kunhao Zheng and Mantas Baksys and Igor Babuschkin and Ilya Sutskever},\n      year={2022},\n      eprint={2202.01344},\n      archivePrefix={arXiv},\n      primaryClass={cs.LG},\n      url={https://arxiv.org/abs/2202.01344}, \n}", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)