[Paper] KVerus: Scalable and Resilient Formal Verification Proof Generation for Rust Code

Source: arXiv - 2605.03822v1

Overview

The paper introduces KVerus, a retrieval‑augmented system that automatically generates and repairs formal verification proofs for Rust code written with the Verus verifier. By building a dynamic knowledge base of code metadata, lemma semantics, and toolchain details, KVerus can keep proofs alive as the codebase and verification tools evolve—something that current LLM‑based approaches struggle with.

Key Contributions

• Self‑adaptive verification paradigm that bridges the “semantic‑structural gap” between LLM‑style reasoning and the rigid dependency graph required by formal verification.
• Dynamic knowledge base that indexes code symbols, lemma meanings, and Verus version specifics, enabling on‑the‑fly retrieval of relevant proof fragments.
• Dependency‑aware program analysis that automatically discovers cross‑module relationships and feeds them into the proof synthesis loop.
• Error‑driven self‑refinement mechanism that detects proof failures, queries the knowledge base, and iteratively repairs the proof without human intervention.
• Empirical validation on single‑file, multi‑file, and real‑world OS kernel benchmarks, showing up to a 43 % absolute improvement over the prior AutoVerus system.

Methodology

1. Metadata Extraction – KVerus parses the Rust project and the Verus specifications to collect a graph of functions, types, and lemmas, together with versioned information about the Verus toolchain.
2. Semantic Lemma Indexing – Each lemma is embedded using a lightweight semantic encoder and stored in a searchable index, allowing the system to retrieve lemmas that are semantically relevant to a proof goal.
3. Retrieval‑Augmented Synthesis – When a verification task is issued, KVerus queries the index for candidate lemmas, then composes a proof sketch that respects the exact structural dependencies (e.g., module imports, trait bounds).
4. Error‑Driven Self‑Refinement – If Verus reports a failure, KVerus analyzes the error message, updates the knowledge base (e.g., noting a changed API or a new Verus rule), and re‑runs the synthesis loop until the proof succeeds or a timeout is reached.
5. Iterative Adaptation – The knowledge base persists across verification runs, so subsequent code changes automatically benefit from previously learned repairs.

The pipeline is deliberately modular so developers can plug in alternative semantic encoders or replace the Verus backend with another Rust verifier.

Results & Findings

Additional observations

• When Verus introduced breaking updates, KVerus’s performance degraded by less than 5 % whereas AutoVerus dropped by >30 %.
• The self‑refinement loop typically converged within 2–3 iterations, keeping verification latency under 30 seconds for most tasks.

Practical Implications

• Reduced manual proof maintenance: Teams can rely on KVerus to keep existing verification artifacts up‑to‑date as the code evolves, cutting down on costly “proof rot.”
• Scalable adoption for large Rust codebases: The ability to handle cross‑module dependencies means that libraries, micro‑services, and even OS kernels can start leveraging formal verification without rewriting proofs from scratch.
• Integration into CI pipelines: Because KVerus works incrementally and reports concrete repair steps, it can be dropped into continuous integration workflows to automatically reject regressions that break verification guarantees.
• Lower barrier for security‑critical projects: Developers without deep expertise in formal methods can obtain high‑assurance proofs simply by running the tool, accelerating adoption in domains like embedded systems, blockchain, and cloud infrastructure.

Limitations & Future Work

• Toolchain lock‑in: KVerus is currently tied to the Verus verifier; extending the approach to other Rust verification frameworks (e.g., Prusti, Creusot) will require additional adapters.
• Semantic encoder quality: The proof synthesis quality depends on the encoder’s ability to capture lemma intent; more sophisticated models could further improve retrieval relevance.
• Scalability to massive monorepos: While the system handles multi‑file projects, indexing and retrieval overhead may become a bottleneck for repositories with tens of thousands of modules.

Future directions proposed by the authors

1. A language‑agnostic abstraction layer for cross‑verifier support.
2. Tighter integration with LLMs for natural‑language specification generation.
3. Distributed indexing to handle very large codebases.

Authors

• Yuwei Liu
• Xinyi Wan
• Yanhao Wang
• Minghua Wang
• Lin Huang
• Tao Wei

Paper Information

• arXiv ID: 2605.03822v1
• Categories: cs.SE, cs.CR
• Published: May 5, 2026
• PDF: Download PDF