核心发现
方法论
本研究提出了一种基于Dafny的形式验证框架，通过自然语言到代码的生成过程来评估大语言模型的能力。使用了三种提示策略：无上下文提示、结构签名提示和自愈提示。通过Dafny验证器的迭代反馈，自愈提示模拟了人类开发者的工作流程，显著提高了代码验证的成功率。
关键结果
- 结果1：在使用结构签名提示和自愈提示的情况下，Gemma 4-31B模型的验证成功率达到90.91%，而GPT-OSS 120B从零提升至81.82%。这表明通过结构化提示和反馈机制，开放权重的大语言模型可以有效生成形式验证代码。
- 结果2：无上下文提示策略几乎导致所有模型失败，表明结构化提示在形式验证中的重要性。
- 结果3：通过uDebug平台进行功能验证，确保生成的代码不仅形式上正确，而且在实际应用中功能健全。
研究意义
本研究在学术界和工业界具有重要意义。它不仅展示了大语言模型在形式验证中的潜力，还为高保证软件开发提供了一条可行的路径。通过结合形式验证和大语言模型，研究解决了代码生成中的可靠性问题，为自动化软件工程带来了新的可能。
技术贡献
技术贡献包括：1) 提出了一个新颖的基于Dafny的形式验证框架，2) 通过引入结构签名和自愈提示策略，显著提高了代码生成的准确性，3) 将uDebug平台整合到验证过程中，提供了双层验证机制，确保代码的功能正确性。
新颖性
本研究首次将大语言模型与Dafny形式验证相结合，提出了一种新的代码生成方法。与现有工作相比，本研究不仅关注代码的生成，还强调了代码的验证和功能正确性，填补了自然语言到形式验证代码生成的空白。
局限性
- 局限1：尽管自愈提示显著提高了验证成功率，但在某些复杂问题上仍然存在失败的情况，需要进一步优化提示策略。
- 局限2：Dafny生态系统的数据集规模较小，可能限制了模型在更大规模问题上的泛化能力。
- 局限3：目前的研究主要集中在算法问题上，尚未在更广泛的软件工程领域进行验证。
未来方向
未来的研究方向包括：1) 扩展数据集规模，涵盖更多样化的问题类型，2) 优化提示策略，进一步提高验证成功率，3) 探索大语言模型在其他形式验证语言中的应用，如Coq和Lean。
AI 总览摘要
在软件工程领域，自动化代码生成一直是一个备受关注的研究方向。然而，现有的大语言模型在生成代码时，常常会出现语法上合理但语义上错误的情况，这被称为“幻觉”。为了解决这一问题，研究人员提出了一种新的方法，将大语言模型与Dafny形式验证相结合，以确保生成代码的正确性。
本研究提供了一个名为NaturalLanguage2VerifiedCode (NL2VC)-60的数据集，其中包含60个复杂的算法问题。研究人员使用了三种提示策略：无上下文提示、结构签名提示和自愈提示。通过Dafny验证器的迭代反馈，自愈提示模拟了人类开发者的工作流程，显著提高了代码验证的成功率。
在实验中，研究人员选择了11个问题集，使用七个开放权重的大语言模型进行评估。结果显示，结构签名提示和自愈提示显著提高了验证成功率，其中Gemma 4-31B模型的验证成功率达到90.91%，而GPT-OSS 120B从零提升至81.82%。这些结果表明，通过结构化提示和反馈机制，开放权重的大语言模型可以有效生成形式验证代码。
此外，研究还整合了uDebug平台进行功能验证，确保生成的代码不仅形式上正确，而且在实际应用中功能健全。uDebug是一个社区驱动的平台，专为竞争性程序员设计，用于验证他们的解决方案是否符合高质量的测试套件。
本研究在学术界和工业界具有重要意义。它不仅展示了大语言模型在形式验证中的潜力，还为高保证软件开发提供了一条可行的路径。通过结合形式验证和大语言模型，研究解决了代码生成中的可靠性问题，为自动化软件工程带来了新的可能。
尽管取得了显著的成果，但研究也存在一些局限性。例如，Dafny生态系统的数据集规模较小，可能限制了模型在更大规模问题上的泛化能力。此外，尽管自愈提示显著提高了验证成功率，但在某些复杂问题上仍然存在失败的情况。未来的研究方向包括扩展数据集规模，优化提示策略，以及探索大语言模型在其他形式验证语言中的应用。
深度分析
研究背景
形式验证在软件工程中扮演着至关重要的角色。它通过数学证明确保程序严格满足其规格说明，尤其在高风险领域如安全敏感基础设施、加密库和自主航空系统中，形式验证的应用愈发广泛。然而，编写程序属性和证明仍然是一个创造性且手动的过程，需要大量的专业知识。随着大语言模型的兴起，如GitHub Copilot和Amazon Q Developer，软件开发工作流发生了显著变化。这些AI驱动的工具通过自然语言到代码的翻译和智能自动补全，加速了编程任务。然而，尽管这些系统在语法上流畅，它们生成的代码常常在语义上不正确，尤其在处理复杂算法逻辑时。为了确保生成代码的正确性和逻辑完整性，研究需要在AI合成和形式验证之间架起桥梁。
核心问题
大语言模型在自动化软件工程中展现出潜力，但其生成代码的正确性常常受到错误或幻觉代码的影响。为了确保模型的诚实性，形式验证要求大语言模型在合成实现逻辑的同时提供形式规格说明，并通过数学验证器证明其正确性。然而，从非正式的自然语言到精确的形式规格说明的过渡仍然是一项艰巨的任务。现有的形式验证语言，如F*、Coq、Lean和Java建模语言（JML），在这一过程中面临挑战。Dafny作为一种平衡命令式编程和自动定理证明的语言，尽管支持通过断言、前置条件和后置条件进行验证，但编写形式规格说明和辅助验证断言仍然困难。
核心创新
本研究的核心创新在于：1) 提出了NaturalLanguage2VerifiedCode (NL2VC)-60数据集，专为评估从复杂的现实世界需求中合成形式验证代码而设计。2) 开发了一种基于Dafny的形式验证框架，通过自然语言到代码的生成过程来评估大语言模型的能力。3) 引入了三种提示策略：无上下文提示、结构签名提示和自愈提示，通过Dafny验证器的迭代反馈，自愈提示模拟了人类开发者的工作流程，显著提高了代码验证的成功率。4) 整合了uDebug平台进行功能验证，确保生成的代码不仅形式上正确，而且在实际应用中功能健全。
方法详解
- �� 提出NaturalLanguage2VerifiedCode (NL2VC)-60数据集，包含60个复杂的算法问题。
- �� 使用三种提示策略：无上下文提示、结构签名提示和自愈提示。
- �� 通过Dafny验证器的迭代反馈，自愈提示模拟了人类开发者的工作流程。
- �� 选择11个问题集，使用七个开放权重的大语言模型进行评估。
- �� 整合uDebug平台进行功能验证，确保生成的代码在实际应用中功能健全。
实验设计
实验设计包括从UVa Online Judge中选择11个问题集，使用七个开放权重的大语言模型进行评估。使用三种提示策略：无上下文提示、结构签名提示和自愈提示。通过Dafny验证器的迭代反馈，自愈提示模拟了人类开发者的工作流程。整合uDebug平台进行功能验证，确保生成的代码在实际应用中功能健全。实验结果显示，结构签名提示和自愈提示显著提高了验证成功率，其中Gemma 4-31B模型的验证成功率达到90.91%，而GPT-OSS 120B从零提升至81.82%。
结果分析
实验结果显示，结构签名提示和自愈提示显著提高了验证成功率，其中Gemma 4-31B模型的验证成功率达到90.91%，而GPT-OSS 120B从零提升至81.82%。无上下文提示策略几乎导致所有模型失败，表明结构化提示在形式验证中的重要性。通过uDebug平台进行功能验证，确保生成的代码不仅形式上正确，而且在实际应用中功能健全。
应用场景
本研究的应用场景包括：1) 高保证软件开发，通过结合形式验证和大语言模型，解决代码生成中的可靠性问题。2) 自动化软件工程，为软件开发提供了一条可行的路径。3) 在安全敏感基础设施、加密库和自主航空系统等高风险领域的应用。
局限与展望
尽管研究取得了显著的成果，但也存在一些局限性。例如，Dafny生态系统的数据集规模较小，可能限制了模型在更大规模问题上的泛化能力。此外，尽管自愈提示显著提高了验证成功率，但在某些复杂问题上仍然存在失败的情况。未来的研究方向包括扩展数据集规模，优化提示策略，以及探索大语言模型在其他形式验证语言中的应用。
通俗解读 非专业人士也能看懂
想象一下你在厨房里做饭。你有一个食谱（自然语言描述），但你需要确保每一步都正确无误（形式验证）。大语言模型就像一个聪明的助手，它可以根据食谱帮你做饭，但有时候它会犯错，比如放错了调料。这时，你需要一个验证器（Dafny）来检查每一步是否正确。研究人员发现，通过给助手提供一些结构化的提示，比如告诉它先放盐再放糖，它的表现会更好。此外，如果助手犯了错，验证器会告诉它哪里出了问题，然后助手可以根据反馈进行调整，直到每一步都正确。这就像在厨房里，你不断尝试和调整，直到做出完美的菜肴。通过这种方式，研究人员展示了如何利用大语言模型和形式验证来生成高质量的软件代码。
简单解释 像给14岁少年讲一样
嘿，小伙伴！想象一下你在玩一个游戏，你需要根据提示来完成任务。有时候，提示很模糊，你不知道该怎么做。这就像大语言模型在生成代码时遇到的问题。为了帮助它，我们给它一些更明确的提示，就像在游戏中给你一个更详细的任务说明。这样，它就能更好地完成任务啦！而且，如果它做错了，我们还有一个超级聪明的检查员（Dafny）来告诉它哪里出问题了。然后，它可以根据检查员的反馈进行调整，就像你在游戏中不断尝试，直到完成任务一样。通过这种方式，我们可以确保生成的代码是正确的，就像你在游戏中获得高分一样酷！
术语表
大语言模型 (Large Language Model)
一种基于大量文本数据训练的人工智能模型，能够生成自然语言文本。
用于自动生成软件代码。
形式验证 (Formal Verification)
通过数学证明来确保程序严格满足其规格说明的过程。
用于验证大语言模型生成的代码的正确性。
Dafny
一种支持形式验证的编程语言，能够通过断言、前置条件和后置条件进行验证。
作为形式验证框架使用。
自愈提示 (Self-Healing Prompting)
一种提示策略，通过反馈机制帮助大语言模型修正错误。
用于提高代码验证的成功率。
uDebug
一个社区驱动的平台，用于验证程序员的解决方案是否符合高质量的测试套件。
用于功能验证，确保代码在实际应用中功能健全。
幻觉 (Hallucination)
大语言模型生成的语法上合理但语义上错误的代码。
需要通过形式验证来解决。
结构签名提示 (Signature Prompt)
一种提示策略，通过提供结构化的提示来帮助大语言模型生成更准确的代码。
用于提高代码验证的成功率。
UVa Online Judge
一个在线自动评判系统，提供大量的编程问题。
用于选择实验问题集。
程序合成 (Program Synthesis)
自动生成满足特定规格说明的程序的过程。
研究的核心任务。
验证成功率 (Verification Success Rate)
生成代码通过形式验证的比例。
用于评估大语言模型的性能。
开放问题 这项研究留下的未解疑问
- 1 如何在更大规模的数据集上提高大语言模型的泛化能力？现有的Dafny生态系统数据集规模较小，可能限制了模型在更大规模问题上的表现。需要开发更大规模的数据集，并探索优化提示策略的方法。
- 2 如何在其他形式验证语言中应用大语言模型？目前的研究主要集中在Dafny上，尚未在其他形式验证语言如Coq和Lean中进行验证。需要探索大语言模型在这些语言中的应用潜力。
- 3 如何进一步提高自愈提示的效果？尽管自愈提示显著提高了验证成功率，但在某些复杂问题上仍然存在失败的情况。需要优化提示策略，并探索新的反馈机制。
- 4 如何解决大语言模型生成代码中的幻觉问题？现有的形式验证方法可以解决部分问题，但仍需探索新的方法来提高代码生成的准确性。
- 5 如何在更广泛的软件工程领域应用大语言模型？目前的研究主要集中在算法问题上，尚未在更广泛的软件工程领域进行验证。需要探索大语言模型在其他领域的应用潜力。
应用场景
近期应用
高保证软件开发
通过结合形式验证和大语言模型，解决代码生成中的可靠性问题，为高保证软件开发提供了一条可行的路径。
自动化软件工程
为软件开发提供了一条可行的路径，利用大语言模型加速编程任务，减少人工干预。
安全敏感基础设施
在安全敏感基础设施中应用形式验证，确保系统的安全性和可靠性，防止关键漏洞和操作中断。
远期愿景
加密库
在加密库中应用形式验证，确保加密算法的正确性和安全性，防止数据泄露。
自主航空系统
在自主航空系统中应用形式验证，确保系统的安全性和可靠性，防止关键漏洞和操作中断。
原文摘要
Large Language Models (LLMs) show promise in automated software engineering, yet their guarantee of correctness is frequently undermined by erroneous or hallucinated code. To enforce model honesty, formal verification requires LLMs to synthesize implementation logic alongside formal specifications that are subsequently proven correct by a mathematical verifier. However, the transition from informal natural language to precise formal specification remains an arduous task. Our work addresses this by providing the NaturalLanguage2VerifiedCode (NL2VC)-60 dataset: a collection of 60 complex algorithmic problems. We evaluate 11 randomly selected problem sets across seven open-weight LLMs using a tiered prompting strategy: contextless prompts, signature prompts providing structural anchors, and self-healing prompts utilizing iterative feedback from the Dafny verifier. To address vacuous verification, where models satisfy verifiers with trivial specifications, we integrate the uDebug platform to ensure functional validation. Our results show that while contextless prompting leads to near-universal failure, structural signatures and iterative self-healing facilitate a dramatic performance turnaround. Specifically, Gemma 4-31B achieved a 90.91\% verification success rate, while GPT-OSS 120B rose from zero to 81.82\% success with signature-guided feedback. These findings indicate that formal verification is now attainable for open-weight LLMs, which serve as effective apprentices for synthesizing complex annotations and facilitating high-assurance software development.
参考文献 (20)
Gemma 3 Technical Report
Gemma Team Aishwarya Kamath, Johan Ferret, Shreya Pathak 等
CWM: An Open-Weights LLM for Research on Code Generation with World Models
Fair CodeGen team. Jade Copet, Quentin Carbonneaux, Gal Cohen 等
The Llama 3 Herd of Models
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey 等
Testing Dafny (experience paper)
Ahmed Irfan, Sorawee Porncharoenwase, Zvonimir Rakamarić 等
Validity Threats in Empirical Software Engineering Research - An Initial Survey
R. Feldt, Ana Magazinius
Theories of Programming: The Life and Works of Tony Hoare
Developing verified programs with Dafny
K. Rustan M. Leino
Program Synthesis
Sumit Gulwani, Oleksandr Polozov, Rishabh Singh
Formal and Executable Semantics of the Ethereum Virtual Machine in Dafny
F. Cassez, J. Fuller, Milad K. Ghale 等
DafnyPro: LLM-Assisted Automated Verification for Dafny Programs
Debangshu Banerjee, Olivier Bouissou, Stefan Zetzsche
FormalFuzzer: Formal Verification Assisted Fuzz Testing for SoC Vulnerability Detection
Nusrat Farzana Dipu, Muhammad Monir Hossain, K. Z. Azar 等
The MINERVA Software Development Process
Anthony Narkawicz, C. Muñoz, Aaron Dutle
Evaluating Large Language Models Trained on Code
Mark Chen, Jerry Tworek, Heewoo Jun 等
DafnyBench: A Benchmark for Formal Software Verification
Chloe Loughridge, Qinyi Sun, Seth Ahrenbach 等
Prompt Programming for Large Language Models: Beyond the Few-Shot Paradigm
Laria Reynolds, Kyle McDonell
The CompCert C verified compiler: Documentation and user’s manual
X. Leroy
Program Synthesis with Large Language Models
Jacob Austin, Augustus Odena, Maxwell Nye 等
Model Checking and Other Ways of Automating Formal Methods
J. Rushby
SMT-COMP: Satisfiability Modulo Theories Competition
Clark W. Barrett, L. D. Moura, Aaron Stump