arXiv:2605.27051cs.SEcs.AI2026-05被引 1

用大模型生成函数契约,实现大规模C程序的高效形式化验证

ConVer: Using Contracts and Loop Invariant Synthesis for Scalable Formal Software Verification

论文配图:ConVer: Using Contracts and Loop Invariant Synthesis for Scalable Formal Software Verification
图 1 · 摘自论文原文
  • 通过大模型自动生成函数契约,分层递归验证程序正确性
  • 在4个基准测试中平均验证成功率超80%,多数案例仅需一次迭代收敛
  • 适合需要高可靠性保障的嵌入式系统与安全关键软件验证

大型C程序的形式化验证受限于状态空间爆炸:基于有界模型检测(BMC)的工具必须展开所有嵌套结构以编码整个状态空间。本文提出ConVer,一种自顶向下的组合验证工具。给定带顶层断言的C程序,ConVer自顶向下分解验证任务:利用大语言模型(LLM)从系统属性合成函数契约,并在CEGAR-CEGIS循环中交替进行系统级与函数级检查,失败时通过SMART ICE学习机制更新契约。我们在四个难度递增的基准集上评估ConVer,对比当前最先进(SOTA)工具。在包含45个简单C程序的Frama-C基准中,三种LLM后端均实现82%-96%验证成功率,其中93%-95%的已收敛程序仅需一次迭代。在X.509解析器基准(6~个程序)和LF2C-Simple套件(17个程序)中,验证成功率分别为33%-50%和82%-88%。在包含11个递归与循环密集型程序的VerifyThis套件中,预抽象策略实现55%-64%成功率。此外,我们提出ESBMC-LF预处理器,可将LF模型转为保留原语义的C代码,使ConVer得以验证。我们使用ESBMC-LF将LF验证基准转为C代码,称为LF-Hard。结果表明,ConVer成功验证了67%的LF-Hard基准。

原文摘要 · Abstract (English)

Formal verification of large C programs is impeded by state-space explosion: Bounded Model Checking (BMC) tools must encode the entire state space up to the predetermined bound by unrolling all nested constructs. We present ConVer, a top-down compositional verification tool. Given a C program with a top-level assertion, ConVer decomposes verification top-down: it uses a large language model (LLM) to synthesise function contracts from the system property, then alternates system-level and function-level checks in a CEGAR-CEGIS loop, refining contracts whenever a check fails via SMART ICE learning. We evaluate ConVer on four benchmark suites of increasing difficulty and against other state-of-the-art (SOTA) tools. On the Frama-C benchmark of 45 simple C programs, ConVer achieves 82-96% verification success across three LLM backends, with 93-95% of converged programs requiring only a single CEGAR-CEGIS iteration. On the X.509 parser benchmark (6~programs) and LF2C-Simple suite (17 programs), ConVer achieves 33-50% and 82-88% success respectively. On the VerifyThis suite of 11 recursive and loop-intensive programs, the Pre-Abstraction strategy achieves 55-64% success. In addition, we present ESBMC-LF a preprocessor tool that converts LF models to C while preserving the properties of the LF files, enabling ConVer to verify them. We transpile the LF Verifier Benchmarks using ESBMC-LF to C; we denote those LF-Hard. We show that ConVer successfully verifies 67% of LF-Hard benchmarks overall.

形式化验证大模型应用程序分析合同合成

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。