VeriStruct: AI-assisted Automated Verification of Data-Structure Modules in Verus
Chuyue SunYican SunEthan ZhangDaneshvar AmrollahiShuvendu LahiriShan LuDavid DillClark Barrett
Presents VeriStruct, an automated framework that scales AI-assisted formal verification to complex Rust data-structure modules in Verus by combining structured proof planning with syntax-guided error repair to achieve a 99.2% verification success rate.
As software development increasingly relies on artificial intelligence, systems face growing risks of critical correctness bugs and security vulnerabilities. Formal program verification can mathematically prove that software is free of such defects, but its real-world adoption has been severely limited by the high human expertise and effort required to write complex mathematical annotations. While recent artificial intelligence approaches have automated simple, single-function verification, they struggle with data-structure modules, which are foundational components across software systems that require coordinated reasoning across multiple methods.
The article introduces and evaluates VeriStruct, an artificial intelligence–assisted framework designed to automate the formal verification of multi-method Rust data-structure modules within the Verus verification ecosystem.
VeriStruct uses a structured, two-stage approach that takes standard Rust code and a unit test suite as inputs. First, an automated planning module determines the necessary verification artifacts—such as mathematical representations (views), shared structural invariants, method contracts, and proof hints—and generates an initial draft using targeted language model prompts enriched with formal syntax rules. Second, when the Verus verifier detects failures, VeriStruct executes an automated repair loop that uses pattern matching on error messages to apply specialized fixes, including correcting state mutability, adjusting contract strengths, and resolving syntax mismatches.
Across an evaluation of 11 diverse Rust data-structure benchmarks encompassing 129 functions, VeriStruct fully verified 10 out of 11 modules and 128 out of 129 total functions (a 99.2% success rate). In contrast, a single-prompt baseline solved only 4 modules (52 functions), and an advanced tool-using coding agent solved 8 modules (102 functions). VeriStruct achieved these superior results while consuming slightly fewer computational tokens than the autonomous coding agent. Additionally, an in-depth case study showed that the framework discovered simpler, more concise mathematical representations than those originally written by human experts.
These findings demonstrate that structured, multi-stage artificial intelligence pipelines can overcome the reasoning limitations of language models in complex software verification tasks. Automating this process dramatically reduces manual engineering overhead, lowers development costs, and shortens verification timelines. Most importantly, it creates a practical pathway for establishing mathematically verified, high-assurance software libraries, mitigating the systemic security and reliability risks introduced by unverified code.
Based on these results, software engineering teams should adopt structured planning-and-repair frameworks to verify reusable foundational data structures. To further scale the approach, future development should incorporate automated test generation to eliminate the manual burden of writing unit tests, integrate retrieval-augmented generation to leverage existing mathematical proof libraries, and explore reinforcement learning to improve contract synthesis.
The current evaluation is limited to a benchmark suite of 11 Rust data-structure modules and relies on user-provided unit test suites to establish intended behavior. While confidence in the evaluated domain is high, broader deployment on more complex, large-scale concurrent systems will require additional validation and expanded verification capabilities.
- Paper: VeruSAGE: A Study of Agent-Based Verification for Rust Systems, Chenyuan Yang et al. (2025). Its study of agent frameworks automating Verus proofs in real Rust systems establishes the immediate research context that VeriStruct advances from functions to data-structure modules.
- Paper: seL4: formal verification of an OS kernel, Gerwin Klein et al. (2009). Its end-to-end machine-checked verification of a production Rust kernel grounds VeriStruct’s goal of making formal guarantees practical for systems software.
- Paper: Towards Functional Correctness of Large Code Models with Selective Generation, Jaewoo Jeong et al. (2026). It extends automated code assurance toward calibrated abstention, using fuzz-generated tests to bound risks in accepted code outputs.
- Paper: BlueCodeAgent: A Blue Teaming Agent Enabled by Automated Red Teaming for CodeGen AI, Chengquan Guo et al. (2026). It carries AI-assisted code assurance into security defense by combining learned safety rules with executable tests for vulnerabilities.
