Natural Language based Specification and Verification

Zhaorui Li, Chengyu Song · 2026

Read Natural Language based Specification and Verification by Zhaorui Li, Chengyu Song (2026) 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-2605-11315.txt.

Introduction

Zhaorui Li and Chengyu Song study natural language based specification and verification. Frontier large language models show strong results finding security vulnerabilities in large, mature open-source systems. As LLM-made code becomes ever more common, a natural goal is stopping such models from making vulnerable implementations at all.

Formal verification gives a principled path to this goal, but today's verification pipelines still demand specifications written in rigid formal languages. Earlier work tried using LLMs to synthesize such specs, with limited success. This paper tests another route: LLMs write the specs and also check implementations piece by piece, with specs stated in natural language. Preliminary results suggest this approach is promising. Security teams get a route toward checks without rigid formal spec languages.

Catalog record

CREATORZhaorui Li, Chengyu Song
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65872
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.11315

Browse the full library · About the Tower of Babel

Full text

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

Natural Language based Specification and Verification Zhaorui Li, Chengyu Song Abstract Recent frontier large language models (LLMs) have shown strong performance in identifying security vulnerabilities in large, mature open-source systems. As LLM-generated code becomes increasingly common, a natural goal is to prevent such models from producing vulnerable implementations in the first place. Formal verification offers a principled route to this objective, but existing verification pipelines typically require specifications written in rigid formal languages. Prior work has explored using LLMs to synthesize such specifications, with limited success. In this paper, we investigate a different approach: using LLMs both to generate specifications and to verify implementations compositionally when the specifications are expressed in natural language. Our preliminary results suggest that this approach is promising. 1 Introduction Memory safety violations remain a major source of software vulnerabilities in C and C++ programs. Errors such as invalid dereferences, use-after-free, double free, invalid free, and out-of-bounds accesses often arise from subtle interactions among allocation, deallocation, initialization, aliasing, and control flow. In realistic code, these properties are rarely confined to a single statement or even a single function: whether an operation is safe often depends on facts established in one procedure, propagated through several callees, and discharged only later in the calling context. This interprocedural structure makes memory-safety verification difficult for traditional tools. As a result, new memory errors keeps being introduced to codebases, including mature projects maintained by corporations with plenty of resources (e.g., the Google Chrome browser). Note that this challenge is not just for human developers and traditional tools, LLM-based coding agents also face the same set of challenges: lacking enough context, agents can introduce new memory errors too. Recent progress in LLM-based bug finding makes this problem more urgent. LLMs are increasingly used not just to explain code, but to find bugs in real systems at a scale that was difficult to imagine with earlier tooling. In practice, LLM-assisted analysis can surface very large numbers of candidate bugs—for example, Linux kernel maintainers report that AI-generated bug reports increased from only two or three per week to roughly five to ten per day within about two years, with enough of those reports proving correct that additional maintainers were needed to handle them. This trend raises a broader question: once many bugs have been surfaced, how many bugs are still left in a code repository—or are there any left at all? And more critically, how can we prevent new bugs being introduced in the future? Answering these questions requires moving beyond bug finding, which seeks evidence of a feasible defect, to reasoning about whether defects are absent. Formal verification offers one of the strongest ways to answer this question, because it aims not merely to find individual counterexamples, but to establish explicit safety guarantees. Its effectiveness, however, depends critically on having the right specifications. Automated verifiers do not prove vague intentions; they prove explicit claims. As a result, users often must provide preconditions, postconditions, loop invariants, frame conditions, and auxiliary assertions that capture intended behavior. In practice, this annotation burden remains a central obstacle to adoption. Decades of work on annotation assistants and invariant inference—including systems such as Houdini, Daikon, and Liquid Types—show both the value of automation and the difficulty of recovering rich semantic intent from syntax, traces, or restricted logical templates alone 10 ; 9 ; 20 . This makes formal verification a natural lens for assessing whether LLMs can move beyond surfacing bugs to reasoning about whether any bugs remain. Recent LLM-based verification systems have renewed optimism that reducing this burden might become substantially easier. Most existing work uses LLMs primarily to generate formal proof artifacts like loop invariants, preconditions, and postconditions, that are then checked by external verifiers or theorem provers 19 ; 6 ; 13 ; 8 ; 24 ; 25 ; 16 ; 3 ; 17 ; 21 . This design has yielded promising results for invariant generation and specification synthesis, but it places the LLM in a largely supportive role: the model proposes candidate formal objects, while the core reasoning and validation are delegated to a symbolic backend. Our work explores a different point in the design space. Instead of asking whether LLMs can help produce formal specifications for another verifier, we ask whether LLMs can themselves reason about memory safety more effectively when that reasoning is structured appropriately. A straightforward way to pose this problem is to present an entire program to an LLM and ask whether it is memory-safe. However, this monolithic formulation is brittle. The model must, within a very long context, simultaneously infer the behavior of individual functions, recover how safety-relevant information flows across calls, and determine whether a violation is feasible under the accumulated calling context. Such long-context reasoning remain a major challenge for modern LLMs 1 . Whole-program prompts also obscure the modular structure that makes interprocedural verification tractable in the first place, forcing the model to rediscover local semantic facts each time it analyzes a new caller. Recent benchmarking results in formal verification point to the same broader limitation: local success on single functions does not readily translate into strong performance on multi-function programs 26 : models that achieve over 99\% syntax correctness and over 58\% verification on prior single-function benchmarks fall to 95.67\% syntax correctness and just 3.69\% verification on compositional tasks, a drop of roughly 92\% . Even the strongest model reaches only about 7\% verification at Pass@8, and most models remain below 2\% . Our intuition is that LLM reasoning for memory safety should follow traditional wisdom of compositional veification—decomposed around reusable semantic summaries of functions. However, intead of translating intermediate results into rigid formal specifications for a downstream symbolic verifier, we keep them in natural language and feed them back to the LLM in later reasoning stages. This design is motivated by the observation that, because LLMs are trained on code, documentation, and natural language, natural-language summaries may be easier for the model to generate, interpret, and refine consistently than rigid formal notation. Natural language can also be more expressive than formal notations. Based on this intuition, we present NLForge, a compositional LLM-based framework for memory-safety verification of C/C++ programs. NLForge first extracts functions from the program and constructs a call graph. It then performs a sequence of bottom-up analysis passes, generating summaries for allocation behavior, deallocation behavior, initialization behavior, and memory-safety contracts. These summaries are propagated from callees to callers and reused in a final verification pass, allowing the model to reason about a function under explicitly stated assumptions about its callees rather than raw source code alone. This decomposition is especially important for memory-safety bugs, where the safety of an operation often depends on a chain of prior facts: whether a pointer was allocated, whether ownership was transferred, whether storage was initialized, whether an alias may have been freed, or whether a size relationship remains valid across calls. We evaluate this design on a subsect of programs from the memory-safety category of the International Competition on Software Verification (SV-COMP) 2026 using several modern LLMs, and compare it against a non-compositional baseline that asks the model to analyze all relevant source in a single prompt. Our results show that compositional natural-language summaries can substantially improve

Read the complete text