A Survey of LLM-based Program Synthesis and Verification |LLM驱动的程序合成与形式化验证综述 |arxivreview

简介: 传统形式化验证因规格编写成本高昂而难以在大规模软件中普及,大语言模型(LLM)在代码生成上的突破为自动化规格推断提供了新路径。早期研究将LLM视为代码补全工具,验证仅作为后验测试,核心痛点在于语法与基本功能错误。随着跨域基准暴露出LLM幻觉导致的逻辑错误,研究者引入形式化验证器作为“真理裁判”,确立了“生成-验证-修复”闭环范式。各路线在表示质量、适应效率与计算成本之间做出了不同取舍,由此形成当前神经符号融合的方法格局。本综述梳理这条从概率直觉到逻辑必然的因果演进链条,为读者提供一张领域认知地图。全文按问题演化与路线取舍组织,覆盖该领域从奠基到当前的主要工作。

综述原文见 ArxivReview

导读

传统形式化验证因规格编写成本高昂而难以在大规模软件中普及,大语言模型(LLM)在代码生成上的突破为自动化规格推断提供了新路径。早期研究将LLM视为代码补全工具,验证仅作为后验测试,核心痛点在于语法与基本功能错误。随着跨域基准暴露出LLM幻觉导致的逻辑错误,研究者引入形式化验证器作为“真理裁判”,确立了“生成-验证-修复”闭环范式。各路线在表示质量、适应效率与计算成本之间做出了不同取舍,由此形成当前神经符号融合的方法格局。本综述梳理这条从概率直觉到逻辑必然的因果演进链条,为读者提供一张领域认知地图。全文按问题演化与路线取舍组织,覆盖该领域从奠基到当前的主要工作。

1. 研究背景、问题结构与演进脉络

该领域的兴起源于传统形式化方法在大规模软件应用中的高成本与低效率,以及LLM在代码生成上的突破。传统形式化验证(如模型检查、定理证明)依赖人工编写精确的形式化规格说明(Formal Specification),这一过程耗时且易出错,构成了“规格瓶颈”。与此同时,LLM生成的代码虽高效,但缺乏数学上的正确性保证,存在“幻觉瓶颈”。这两重约束共同定义了该领域的核心问题:如何构建一种神经符号闭环机制,使LLM的概率性语义理解能力能够可靠地转化为形式化验证器可接受的确定性逻辑证据。

问题形式化通常涉及从自然语言意图或代码片段推断出机器可检查的逻辑约束。设程序 $P$ 和自然语言描述 $D$,目标是在形式化语言(如Dafny, ACSL)中生成规格 $S$,使得 $S$ 忠实于 $D$ 且能被验证器接受。这一过程可分解为子问题:意图解析、规格合成、循环不变量(Loop Invariant)生成、验证器检查与反馈修复。这些子问题存在严格的依赖关系:规格精度直接决定验证器的通过率,而验证器反馈的质量又决定了LLM修复的有效性。若规格过于宽松,验证将失去意义;若过于严格,验证将频繁失败。

范式边界在于LLM与验证器的角色分工。LLM负责利用语义理解生成候选解(代码、规格、不变量),验证器负责利用逻辑严谨性进行最终裁决。这种神经符号集成(Neuro-Symbolic Integration)弥补了单一范式的不足:LLM缺乏逻辑严谨性,验证器缺乏语义灵活性。当前研究处于高速活跃期,重点在于解决LLM幻觉、提升验证器可扩展性,以及探索强化学习(RL)在可验证代码生成中的应用。

约束演化史揭示了方法如何因应约束变化而演变。2020-2022年,研究聚焦于代码生成,LLM被视为代码补全工具,验证仅作为后验测试。2023年,AlphaVerus证明了LLM在系统级语言(Rust)中生成可验证代码的可行性,开启了Vericoding时代。2024-2025年,问题转向“规格缺失”,LLM被引入作为规格生成器,核心痛点变为如何从自然语言推断出精确的逻辑约束。2026年,问题演变为“系统级可扩展性与神经符号融合”,研究重心从单函数正确性转向组合式推理、仓库级依赖管理,以及解决LLM幻觉与验证器反馈之间的语义鸿沟。

如果用一个核心问题概括该领域,那便是:如何构建一种神经符号闭环机制,使LLM的概率性语义理解能力能够可靠地转化为形式化验证器可接受的确定性逻辑证据,从而实现“正确性由构造保证”。

2. 方法体系

  • 2007:Daikon——通过动态分析观察程序执行轨迹来推断不变量属性,是早期自动规格推断的代表性工具

  • 2010:Dafny——一种内置形式化验证支持的编程语言,奠定了现代Vericoding范式的基础

  • 2023:AlphaVerus——首个展示LLM能够生成通过Verus验证器检查的Rust代码及证明的工作

  • 2024:SpecGen——提出基于变异引导的对话式管道,是早期将LLM与验证器深度结合的规格合成方法

  • 2025:AutoSpec——结合LLM与静态分析,解决了单一LLM调用难以处理复杂程序结构的问题

  • 2026:VERISPECGEN——提出意图对齐的形式化规格合成框架,显著提升了规格的正确性与完整性

  • 2026:NeuroInv——提出神经符号方法,结合了神经网络的生成能力与符号推理的精确性

  • 2026:P3 (Program-and-Proof Planning)——提出联合规划程序与证明的方法,确保实现与证明在算法结构上的一致性

这条时间线勾勒了该领域方法演进的代表性节点:从 2007 年的 Daikon 奠定该领域方法基线,经 2010 年 Dafny 的推进,到 2026 年的 Vero 代表当前前沿。各节点对应的技术路线、取舍与关联,详见后续小节。

2.1 形式化规格合成

形式化规格合成旨在从自然语言或代码自动生成机器可检查的逻辑约束。早期方法如SpecGen(Hossain et al., 2024)采用对话式管道,利用LLM从Java方法签名生成JML规格,并通过验证器反馈迭代修复。然而,单一LLM调用难以处理复杂程序结构,且生成的规格常过于宽松或严格。AutoSpec(Hossain et al., 2025)结合LLM与静态分析,将程序分解为组件并构建层次图,针对每个组件查询LLM生成规格并组合,解决了单一LLM调用难以处理复杂程序结构的问题。

VERISPECGEN(Ye et al., 2026, P27)进一步提出意图对齐的形式化规格合成框架,通过可追溯的精炼过程将自然语言意图转化为形式化规格。该方法引入分解器和对抗测试模块,显著提升了规格的正确性与完整性。与AutoSpec相比,VERISPECGEN更强调意图的忠实度,通过中间表示作为检查点,允许在合成过程中进行细粒度的错误定位与修复。其代价是增加了推理步骤和计算开销,且依赖高质量的初始意图描述。AutoACSL(Zhou et al., 2026, P39)则结合LLM与基于程序图(CPG)的静态分析,利用静态分析提供程序结构信息以指导LLM生成,显著提高了规格的可验证性比例。

2.2 循环不变量生成

循环不变量合成是程序验证中的关键瓶颈,通用循环不变量合成是图灵不可判定问题。Quokka(Wei et al., 2025, P3)利用LLM生成候选不变量,并通过验证器检查其正确性与充分性,引入了迭代精炼机制。然而,LLM生成的不变量往往缺乏足够的强度,或在复杂嵌套循环中失效。NeuroInv(King et al., 2025, P13)提出基于最弱前件推理的神经符号方法,利用LLM生成初始不变量,并通过最弱前件计算验证不变量是否被循环体保持,若验证失败则利用符号推理生成反例或修正建议,反馈给LLM进行修复。

InvWeaver(Wu et al., 2026, P41)针对多循环程序提出神经符号框架,构建循环级调用图(LCG)以暴露循环间依赖,通过义务引导的上下文感知推理过程合成不变量,解决了局部欠指定问题。与NeuroInv相比,InvWeaver能够处理更复杂的程序结构,生成的不变量更具全局一致性。其代价是LCG构建和双向推理的计算开销较大,且依赖循环间依赖关系的准确提取。WONDA(Pinto et al., 2026, P22)则专注于提升小语言模型(SLM)在循环不变量生成任务上的性能,通过数据策展框架将符号求解器生成的原始输出转化为高质量训练信号,降低了部署成本。

2.3 端到端验证代码生成

端到端验证代码生成旨在让LLM同时生成可执行代码与机器可检查证明。早期方法如AlphaVerus(Wilf et al., 2023)证明了LLM在系统级语言中生成可验证代码的可行性,但受限于“先程序后证明”范式导致的结构不匹配问题。P3(Li et al., 2026, P43)提出联合规划程序与证明的方法,将程序生成和证明生成视为一个联合优化问题,LLM同时规划算法结构和证明策略,确保两者在逻辑上的一致性。与分离生成方法相比,P3生成的程序更易于验证,因为证明结构在生成初期就已考虑在内。

VeruSAGE(Yang et al., 2025, P15)研究基于代理的Rust系统验证,探索通用编码代理在特定验证工具链下的应用。该方法采用Hands-off和Hands-on两种策略,发现Hands-on策略在复杂系统代码上显著优于Hands-off。FM-Agent(Ding et al., 2026, P28)提出基于LLM的Hoare风格推理,将形式化方法扩展到大型系统,通过组合式推理降低了验证复杂度,使其能够处理超过10万行代码的系统。Vero(Ye et al., 2026, P44)评估AI代理构建形式化验证软件仓库的能力,发现即使前沿模型在单函数验证上表现良好,但在处理多文件、多函数的仓库级验证任务时仍面临显著瓶颈。

2.4 程序验证基准评估

程序验证基准评估旨在构建专用数据集,评估模型在形式化验证任务中的表现。DafnyBench(Xu et al., 2025, P5)针对Dafny语言构建的基准,评估LLM生成证明提示的能力,但未能捕捉多函数间的组合依赖。LiveFMBench(Xu et al., 2026, P31)提出首个针对C程序规格生成的持续演进基准,包含630个ACSL注释程序,通过从SV-COMP仓库持续筛选新案例来缓解数据泄露问题。VCoT-Bench(Xie et al., 2026, P23)提出通过验证链(Verification Chain of Thought)评估LLM在Rust验证中的推理能力,将Z3证明提升为Verus级别的验证步骤,提供了评估LLM形式化推理过程的细粒度基准。

Verus-SpecGym(Agarwal et al., 2026, P36)提出用于评估规格自动形式化的代理式环境,支持多种LLM和代理工作流,并引入规格忠实度评估指标。与DafnyBench等单函数基准相比,Verus-SpecGym支持更复杂的系统级代码,并提供了更细粒度的评估维度。SysMoBench(ICLR 2026, P45)提出评估AI在形式化建模复杂现实系统能力的基准,专注于TLA+语言,揭示了LLM在复杂系统推理上的不足。

2.5 代码推理与解释

代码推理与解释旨在研究LLM对代码执行轨迹、语义等价性及程序行为的推理能力。PIPS(Stein et al., 2025, P8)提出通过为每个实例合成程序来进行推理的方法,利用程序执行的可验证性来纠正LLM推理中的幻觉。与Chain-of-Thought方法不同,PIPS不依赖LLM的自然语言推理能力,而是依赖程序执行的确定性,从而提高了推理的可靠性。Agentic Interpretation(Mitchell et al., 2026, P34)提出基于格结构证据的LLM程序分析框架,通过评估查询和生成查询引导LLM代理收集证据,将LLM的贡献形式化为可验证的证据链。

ExecVerify(ACL 2026, P46)提出白盒强化学习方法,利用可验证的步骤级奖励训练LLM进行代码执行推理,通过显式验证中间执行状态而非仅最终输出,提升了小模型在代码推理任务上的性能。Teaching LLMs Program Semantics via Symbolic Execution Traces(Bayer et al., 2026, P33)提出利用符号执行轨迹训练LLM理解C程序语义的方法,专注于内存安全和未定义行为,提高了LLM对低层语言语义的理解能力。

2.6 验证器引导优化

验证器引导优化旨在利用形式化验证器或执行反馈作为奖励信号,通过强化学习或进化搜索优化LLM生成的程序。Loong(Huang et al., 2025, P1)提出利用可验证奖励进行大规模合成数据生成的框架,通过验证器筛选高质量推理轨迹,用于后训练LLM。与传统的RLHF方法不同,Loong利用形式化验证器提供客观的奖励信号,避免了人类偏见的引入。SLMFix(Fu et al., 2025, P11)提出利用小语言模型(SLM)通过强化学习修复LLM生成程序中的语法错误,特别针对低资源编程语言,降低了大模型微调的成本。

MIST-RL(Zhu et al., 2026, P19)提出基于变异的增量套件测试强化学习方法,将测试生成转化为效用驱动的序贯决策过程,强调测试用例的边际效用,避免生成冗余测试。ReaComp(Naik et al., 2026, P32)提出将LLM推理编译到符号求解器中,用于高效程序合成,结合神经生成与符号执行的优点,提高了程序合成的正确性。

3. 关键共识、分歧与开放问题

3.1 领域共识

形式化验证是确保LLM生成代码正确性的唯一可靠手段,单元测试无法排除所有潜在Bug。这一共识在多个基准上被反复验证:AxDafny的92.7%与Agent-Guided Tree Search的95.0%均大幅超越传统方法。与此相关的另一个共识是“生成-验证-修复”迭代循环显著提升LLM生成代码和规格的通过率,优于单次生成。AxDafny通过迭代修复在DafnyBench上取得了92.7%的通过率,显著优于单次生成方法。

3.2 观点分歧

LLM在验证中的角色定位存在分歧:是作为“启发式引导器”(辅助搜索)还是“语义翻译器”(直接生成证明)?现有证据偏向启发式引导,因为LLM的逻辑推理能力仍不足以独立生成复杂证明。VCoT-Bench显示LLM在中间推理步骤中逻辑错误率高,需符号系统辅助。这一分歧的背后,是另一个更根本的争论:规格生成的粒度。完整合同生成难度大,LLM常生成过于严格的约束导致验证失败。场景依赖:在安全关键系统中,完整合同是必须的;在性能敏感系统中,最小约束可能更优。

3.3 其他开放问题

当前研究面临两大认知边界:一是“工程问题”,如验证器反馈的语义转换和token成本优化;二是“研究问题”,如LLM在大规模并发系统中的抽象能力不足。验证器错误信息晦涩,需中间层进行语义转换;LLM推理成本高,需编译为符号求解器复用。LLM难以处理深层跨过程依赖和并发内存布局,组合式推理尚难完全自动化。未来方向包括利用强化学习优化验证器引导策略,以及构建跨语言的通用验证基准。

4. 总结与展望

该领域的核心矛盾在于LLM的概率性语义理解与形式化验证的确定性逻辑推理之间的鸿沟。早期方法依赖LLM的语义直觉,但受限于逻辑严谨性;中期方法引入静态分析辅助,牺牲了灵活性换取结构约束;当前主流方法采用“生成-验证-修复”闭环,通过验证器反馈迭代优化,以计算开销换取正确性保证。核心瓶颈在于系统级验证的可扩展性,LLM难以处理深层跨过程依赖和并发内存布局。

未来可能突破的方向包括:1. 提升LLM在复杂系统级验证中的抽象与分解能力,引入层次化验证策略和结合领域特定知识图谱;2. 开发更可靠的规范忠实性评估机制,利用可执行规范进行对抗性测试和引入人类反馈强化学习;3. 探索LLM与形式化验证器的深度协同,构建验证器引导的代理工作流和将验证反馈转化为训练信号以微调模型。对进入者最值得做的一件事是构建跨语言的通用验证基准,以解决现有基准局限于特定语言或简单算法导致泛化能力评估不足的问题。

以上为节选,完整内容见ArxivReview

相关文章
|
7天前
|
Linux Go 开发工具
手机上跑 DeepSeek 智能体:开源安卓客户端 DSH Go 安装与使用指南
DSH Go 是一款开源安卓客户端,将 DeepSeek Harness 智能体引擎装进手机:免 Root、免 Termux,一键安装即用;支持本机运行(内置 Ubuntu+Node.js)或远程接管电脑会话;具备插话打断、过程折叠、屏幕操控、端到端加密分享等特色功能,真正实现智能体“口袋化”。
8705 21
|
7天前
|
弹性计算 人工智能 API
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
建议收藏本教程,2026 全年各版本更新随时回来查阅。如果你在搭建过程中遇到任何问题,欢迎结合 阿里云工单系统 提交技术支持请求,或在 阿里云开发者社区 搜索 Codex 相关话题交流。 祝你编码愉快,效率翻倍!
2645 12
|
2天前
|
人工智能 安全 应用服务中间件
NGINX 爆出两处高危漏洞 可导致未经身份验证的远程代码执行
NGINX曝出两个高危漏洞(CVE-2026-123633和CVE-2026-123007),CVSS 9.2分,均属HTTP/2内存安全缺陷,无需认证即可远程执行代码。影响自2015年起的多个版本,静态站点亦受威胁。修复版本为开源版1.30.7/1.31.9。(239字)
1273 0
NGINX 爆出两处高危漏洞 可导致未经身份验证的远程代码执行
|
5天前
|
传感器 安全 区块链
Windows 电脑运行安卓应用教程:开源工具 ApkStart 双击 APK 即装、独立窗口运行
ApkStart 是一款开源Windows工具,让安卓APP像原生软件一样运行:双击APK即安装、生成真实图标、独立窗口启动、开始菜单可搜索。无需传统模拟器,内置QEMU运行时,支持数据互通、ARM兼容与命令行操作。(239字)
|
10天前
|
人工智能 前端开发 API
阿里云Qwen4-Max 大模型详解:定位、特征、能力、适用场景与相对Qwen3-Max差异解析
2026年11月11日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问AI平台Token Plan并接入千问办公、Qoder等入口。该版本聚焦知识理解、世界感知、编程与Agentic四项升级,主打复杂编程、专业办公、前端设计与专业软件操作等真实任务。预览期为11月11日10:00至11月25日24:00,仅支持Token Plan调用,到期后模型标识下线;限时2折、新用户再享5折,最低1折可体验。
|
10天前
|
JSON 前端开发 API
阿里云最新Qwen4-Max大模型介绍:模型定位、特征、能力、适用场景解析
2026 年 11 月 11 日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问 AI 平台 Token Plan,并同步接入千问办公、Qoder 等入口。该版本聚焦知识理解、世界感知、编程与 Agentic 四项升级,主打复杂编程、专业办公、前端设计与专业软件操作。预览期至 11 月 25 日 24:00,到期后模型标识下线;限时 2 折、新用户再享 5 折,最低 1 折可体验。
|
22天前
|
Linux 开发工具 iOS开发
Codex保姆级教程(下载+安装+登录+使用,含所有版本,2026最新)
Codex是OpenAI推出的开源AI编程智能体,本地运行,可理解整个代码库,支持自然语言指令改代码、执行命令、跑测试、修Bug,兼容Win/macOS/Linux。(239字)
10978 59
|
3天前
|
人工智能 弹性计算 IDE
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
适合团队落地代码规范,每次提交自动生成评审报告,降低人工CR工作量。同时支持自定义技能脚本,接入团队内部SDK说明文档,让Codex生成符合团队编码规范的代码。Codex三大客户端覆盖本地开发、服务器远程编码、自动化流水线场景,搭配阿里云百炼的Token Plan、Coding Plan,能够低成本搭建稳定可控的AI编码助手。新手建议先从IDE插件入手,熟悉交互逻辑,再尝试CLI版本部署在阿里云ECS,实现云上项目远程编码、批量脚本处理。只要按照步骤完成环境准备、版本选型、密钥对接、项目初始化,就可以把Codex融入日常开发流程,大幅提升代码编写、问题排查、项目重构的效率。
926 0
|
5天前
|
人工智能 弹性计算 开发工具
零成本玩各大模型!DeepSeek Harness dsh-our-free-model 插件,13 个厂商模型直接用
总结一下:装这个插件,你不用注册、不用绑卡、不用填一个 Key,就能在 DeepSeek Harness 里用上 DeepSeek V4.1 Flash、Kimi K3 这一批前沿模型,而且是白嫖的、还不限量。三步搞定:下载插件,复制包含 `package.json` 的插件目录路径,在「添加插件」里粘贴路径安装并重启。无论是在阿里云 ECS 上通过命令行部署的 Web 版,还是本地的 Electron 桌面端,都能顺利跑通,快速搭建一套零成本的免费模型使用环境。
1261 1
|
8天前
|
Linux API iOS开发
【DSH】DeepSeek Harness新手保姆教程(下载+安装+配置+使用,2026最新实测)
DeepSeek Harness(dsh)是DeepSeek AI开源的智能体框架,秉持“一切皆插件”理念,支持读文件、改代码、跑命令、处理表格、联网搜索等操作。免费开源,兼容Windows/macOS/Linux,提供桌面端与网页端,可灵活安装插件扩展能力。