VeriStruct : AI-assisted Automated Verification of Data-Structure Modules in Verus

Chuyue Sun, Yican Sun, Daneshvar Amrollahi, Ethan Zhang, Shuvendu Lahiri, Shan Lu, David Dill, Clark Barrett · 2025

Read VeriStruct : AI-assisted Automated Verification of Data-Structure Modules in Verus by Chuyue Sun, Yican Sun, Daneshvar Amrollahi, Ethan Zhang, Shuvendu Lahiri, Shan Lu, David Dill, Clark Barrett (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-25015.txt.

Introduction

Chuyue Sun, Yican Sun, Daneshvar Amrollahi, Ethan Zhang, Shuvendu Lahiri, Shan Lu, David Dill, and Clark Barrett are the eight authors. They built VeriStruct, a frame that uses AI help to prove whole data modules. It works on more than lone functions. The proof tongue is Verus, used on Rust code. Chat models often slip on its mark syntax and proof sense, which has capped past work.

A plan part in the frame queues the build of short forms, type rules, specs, and proof code in set steps. Syntax help sits in each prompt, and a fix stage mends mark slips on its own. On eleven Rust modules, the frame proved near all functions in ten modules. That nears full auto proof for such code.

Catalog record

CREATORChuyue Sun, Yican Sun, Daneshvar Amrollahi, Ethan Zhang, Shuvendu Lahiri, Shan Lu, David Dill, Clark Barrett
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-25015

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

VeriStruct : AI-assisted Automated Verification of Data-Structure Modules in Verus Chuyue Sun, Yican Sun, Daneshvar Amrollahi, Ethan Zhang, Shuvendu Lahiri, Shan Lu, David Dill, Clark Barrett Abstract We introduce VeriStruct , a novel framework that extends AI-assisted automated verification from single functions to more complex data structure modules in Verus. VeriStruct employs a planner module to orchestrate the systematic generation of abstractions, type invariants, specifications, and proof code. To address the challenge that LLMs often misunderstand Verus’ annotation syntax and verification-specific semantics, VeriStruct embeds syntax guidance within prompts and includes a repair stage to automatically correct annotation errors. In an evaluation on eleven Rust data structure modules, VeriStruct succeeds on ten of the eleven, successfully verifying 128 out of 129 functions (99.2%) in total. These results represent an important step toward the goal of automatic AI-assisted formal verification. 1 Introduction The power of generative AI introduces new risks to our critical digital infrastructure. AI systems have a remarkable ability to analyze code, making it much easier for a malicious actor to find and exploit vulnerabilities [ 1 ] . At the same time, more and more code is being written by or with the assistance of AI systems. While it is true that such AI systems can greatly increase the productivity of programmers, they can also introduce additional correctness errors and security vulnerabilities [ 2 , 3 ] . Thus, productivity gains come at the risk of churning out mountains of buggy, insecure code. Program verification can mitigate these risks by mathematically proving that code—whether human-written or AI-generated—is free of bugs and vulnerabilities. However, program verification relies on the addition of sophisticated logical annotations to code, including preconditions, postconditions, invariants, and auxiliary proof blocks. These annotations, which we also refer to as specifications , are used to generate verification conditions, which are then proved automatically by automated reasoning tools like satisfiability modulo theories (SMT) solvers [ 4 ] . The application of program verification in practice has been severely limited because of the enormous effort and expertise required to create such annotations. Fortunately, the power of generative AI is also shifting the calculus on the practicality of program verification. Recently, there have been encouraging results on using large language models (LLMs) to automatically specify and verify software [ 5 , 6 , 7 , 8 , 9 ] . Our work aims to build on these efforts with the vision of one day making it possible to have AI-assisted program verification at scale and verified libraries of reusable code [ 10 ] . So far, AI-assisted verification efforts have focused on simple textbook algorithms consisting of a single function. In this paper, we extend this by developing a novel workflow for the verification of data structure modules. The ability to verify data structures is a crucial advance since: (1) data structures are ubiquitous in everyday programming, forming the foundation of many software systems; and (2) verifying library data structures lowers the burden for verifying more complex code, as client code can then rely on the correctness of these already-proven components. We implement our workflow in VeriStruct , an AI-assisted automated verification framework for Verus [ 11 , 12 ] . Verus is a state-of-the-art program verification extension for Rust. We target Verus because it has been successfully applied to the construction of verified systems [ 12 ] , and its design allows developers to write verification annotations using a syntax closely aligned with Rust. This design not only lowers the barrier for Rust engineers to adopt formal verification but also positions Verus to have an increasing impact as Rust continues to gain traction in mainstream software development. The input to VeriStruct consists of the Rust source code for the module to be verified and a unit test suite that illustrates the intended usage and expected behavior of the data structure. The test suite serves a dual purpose: it helps ensure that the generated formal specifications align with the developer’s intent, and it helps rule out trivial or vacuous specifications [ 13 ] . VeriStruct automatically augments the provided Rust implementation with annotations needed for program verification. This augmented code, together with the provided unit test suite, are then sent to the Verus verifier, which attempts to formally verify the assertions in the test suite. If the verification check succeeds, the formally verified code is returned to the user. Otherwise, VeriStruct attempts to extend or repair the annotations based on the feedback from the verifier. We highlight two challenges for LLM-assisted verification of data-structure modules. The first challenge is that verifying data structures is inherently more complex than verifying a single function. Specifically, data-structure verification often requires two additional elements: ( i ) a suitable mathematical abstraction that allows the verifier to reason logically about the data structure [ 14 , 15 , 16 ] ; and ( ii ) so-called type invariants that must be preserved by operations on the data structure [ 8 , 17 ] . Moreover, data-structure modules usually expose multiple methods that must be verified jointly under a shared type invariant. This stands in contrast to other recent approaches, which focus on generating a single specification artifact (e.g., proof blocks for an individual function or automated synthesis of class invariants) [ 7 , 18 , 9 , 6 , 8 , 19 , 20 ] . In short, our verification task extends beyond the scope of these existing techniques. The second challenge lies in the LLMs’ limited understanding of Verus’ specialized syntax and verification-specific semantics. For instance, annotations in Verus are only allowed to invoke “specification functions,” which cannot modify global state. However, the LLM sometimes suggests invoking a regular Rust function. Such deficiencies primarily stem from the scarcity of Verus code in existing training data. To address the first challenge, we build on previous work [ 7 ] by adding two new modules: (1) a View module responsible for producing a mathematical abstraction of the data structure; and (2) a Type Invariant module, responsible for producing type invariants. For each component, we design dedicated system and user prompts that clearly articulate the task. These prompts include: (1) the objective of the component; (2) relevant background information to help the LLM better understand the task; (3) step-by-step instructions and the required output format; and (4) in-context learning examples [ 21 ] . Additionally, because not all verification components are necessary for every task, we introduce a planner module, which analyzes the verification task as an initial step and decides which components need to be generated. To address the second challenge, we pursued two approaches. First, we developed a suite of automated repair modules to identify and correct errors in the generated annotations. Compared with the previous work [ 7 ] which focused solely on repairing proof blocks, we further introduce dedicated repair modules targeting views, type invariants, and specifications. Specifically, to facilitate the joint verification of multiple methods and tests, VeriStruct includes a repair module that refines specifications whenever the verifier reports a failed test verification. Second, we embedded structured syntax guidelines into the prompt to mitigate syntax errors in generated annotations. We sourced these guidelines from the Verus tutorial [ 22 ] and from standard

Read the complete text