
新方法可对现有代码做形式化验证,无需重写
来源标题:How to Formally Verify Everything
作者提出一种无需重写代码即可进行形式化验证的新路径,并已证明 OpenSSL 的 SHA-256 实现正确。做法是在 Lean 中为计算机建立形式化模型,再让待验证软件在该模型上运行并证明其性质。作者认为,随着 AI 进展,借助证明助手检查现有代码有望实现近乎无 bug 的世界。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
仓库 我曾以为,代码的形式化验证永远不可能创造一个无 bug 的世界,因为把所有东西都用 Lean 重写一遍是不现实的。当然,你可以证明常用算法的一些性质,但你永远无法证明人们实际使用的具体实现的性质。你不可能把世界上所有的 Linux 机器都移植到一个完全经过验证的软件栈上。 结果我完全错了;你不需要重写一切,你可以证明现有代码的性质!下面我们将探索这个非常令人兴奋且全新的代码形式化验证方向,并且证明 OpenSSL 的 SHA-256 哈希函数实现是正确的,以及其他一些东西。 作为 AI 疯狂快速进步的一个副作用,AI 似乎很快就能证明我们想要的一切[1],这是 AI 进步为数不多的明显积极方面之一。因此,我现在认为,通过用证明助手检查现有代码,一个几乎无 bug 的世界是可以实现的。 这种新的形式化验证方法是如何工作的?通过在 Lean 等语言中编写计算机的形式化模型,然后在该计算机模型上运行感兴趣的软件,并证明模型加软件的行为性质。在一篇博客文章中,Anthropic 的 Lucas 等人(2026)基于 Kaashoek 和 Zeldovich(2026)等研究者的工作,展示了向问题投入大量 agent 编码算力,正如预期的那样,会产出结果。我发现文章中埋藏的案例研究最有趣:他们在 Lean 中编写了 x86 汇编的形式化模型,并证明 Linux 内核中 zlib 压缩格式的实现(以及其他几个实现)符合官方规范,除了一些次要的、可修复的 bug。 遗憾的是,作者没有开源这部分,所以让我们先建立一个 x86 的形式化模型。 我们的最终目标是形式化一整台计算机。第一步是形式化计算机的核心——CPU——所使用的指令集。这本身非常复杂:Intel 2003 年的 IA-32 指令集手册长达 978 页。幸运的是,已有一些先前工作,例如 Watt(2018)对 WASM 汇编规范进行了形式化验证。最近一篇关于安全关键汇编代码、证明了更雄心勃勃命题的优秀论文是 Kaashoek 和 Zeldovich(2026 年 10 月)。他们在 Lean 中编写了 RISC-V 指令集的模型,以及许多有趣特性,如特权级别和硬件接口。 由于 Lucas 等人的 x86 形式化模型并未公开(而且从描述来看,未必经过充分测试?),并且据我所知没有其他公开的 x86 形式化模型,我决定以我能访问的 CPU——AMD EPYC 7742[2]——的行为作为基准真相。由于我预期 32 位指令集[3]的证明会更容易,我们将使用其 32 位模式作为主要形式化模型。QEMU 模拟器对于快速测试很有用。我们最终还会通过添加平台设备,将模型扩展到指令集层面之外,这在证明使用输入输出的 Linux 特性正确性时会很有趣。 现代指令集本身显然非常复杂。我以前从未用汇编编过程,但我玩过汇编编程解谜游戏 TIS-100,它的 CPU 有 14 条指令。对于现代 CPU,取决于你如何定义一条指令,指令数量可能超过 1000 条。我们有整数运算、控制流、等待、浮点相关、单指令多数据等等。 由于一切都依赖于形式化模型的正确性,我们最好充分测试它。这里的基本技术是针对不同类型的指令,与真实处理器进行模糊测试。这样做当然会在实现中发现 bug,而且似乎每当我们把测试用例数量增加十倍,就会出现新的 bug。然而,它只在久经考验的模拟器 QEMU 中发现了 bug!不过到目前为止,这些 bug 都算不上重大或严重到值得花时间报告。 除此之外,既然我们手头有一个大致可用的 CPU 模型,我们应该能用它做 CPU 能做的所有事情:特别是,我们可以在它上面启动 Linux。瞧,它运行良好: 果然,我们可以在那个 Linux 中启动 DOOM 并游玩,虽然很慢。 请注意,运行 DOOM 实际上并没有覆盖许多重要的指令测试:浮点、虚拟化等等。 在这个领域,让我们用三个常用的软件来演示: 关于汇编代码的有趣定理是什么?大概是证明某个重要软件的安全性和正确性。也可能证明从数学角度很有趣。由于我不想被迫披露常用软件中疯狂的零日漏洞,让我们在这里专注于正确性。我们将用关于三个常见软件库的命题来演示: 一个密码学库,每天运行在数千万甚至数亿台设备上,主要通过它在 sodium PHP 扩展中的使用。这里我们从简单的正确性性质开始: 一个用于 SSL(Secure Sockets Layer)等协议的 ubiquitous 库。我们专注于其中的密码学原语。 它是 cURL,你知道它是什么!这里我们专注于更小的一部分,即函数 Curl_cert_hostcheck。它检查证书上的名称是否与用户请求的主机匹配。这里有三个简单的命题。
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。