当一个程序被 Lean 证明为「正确」时，大多数人的直觉反应是：这意味着程序在生产环境中不会出错。然而，2025 年底发生的一个真实案例彻底颠覆了这一假设。一位开发者在使用 Lean 4 验证一个 zlib 压缩库（lean-zip）后，利用 AI Agent 配合模糊测试工具发现了两类 bug—— 它们都位于证明边界之外。这个案例揭示了形式化验证中一个常被忽视的根本性问题：证明环境与运行时环境之间的不变式检查断裂。

证明边界的迷思：什么被验证了什么没有

Lean 4 作为新一代证明助手，其核心价值在于通过类型论和归纳类型提供高可信度的程序正确性证明。然而，当开发者声称「Lean 证明了某程序正确」时，这个陈述隐藏着一个关键前提：证明仅覆盖被明确指定验证的代码部分。在 lean-zip 案例中，被验证的是核心压缩与解压缩算法 —— 即 decomp(comp(x)) = x 这一数学性质。这一性质本身优雅而强大，但它只覆盖了整个系统的一个子集。

未被验证的部分包括两个关键区域。首先是归档解析器，它负责解析压缩文件的 Headers 和元数据。这部分代码从未被形式化验证，因此在处理恶意构造的输入时可能导致拒绝服务（DoS）。其次是 Lean 运行时（Runtime），它是用 C++ 编写的底层执行环境，负责内存管理、垃圾回收和字节码解释。这两个未验证区域恰恰是 bug 的藏身之所 —— 一个导致程序崩溃，另一个可能导致堆缓冲区溢出，进而可能被利用进行代码执行攻击。

这暴露了形式化验证的一个基本现实：验证本身是有边界的，而这个边界由开发者的 specification（规范）决定。规范之外的代码区域，即使存在于同一二进制文件中，也不会获得任何形式化保证。这就是为什么 HN 讨论中有开发者指出：「证明义务通常不会跨越那些未验证的层。」

运行时验证的特殊困境

Lean 4 与其说是单一工具，不如说是一个多层技术栈。最底层是 Lean 内核（Kernel），它负责检查证明的正确性 —— 这是整个系统中最受信任的部分，也是经过最严格审计的代码。内核本身是用 Lean 编写的，形成了一个自证的逻辑链条。然而，内核之上存在一个关键的信任缺口：运行时的实现。

Lean 运行时由 C++ 编写，负责执行经过验证的 Lean 代码编译后的产物。这个运行时不在 Lean 的验证范围内，但它对于任何 Lean 程序的正确执行都至关重要。在 lean-zip 案例中发现的堆缓冲区溢出正是发生在这个运行时层。当处理包含大量元素的标量数组时，如果数组大小未得到适当边界限制，运行时可能会触发内存错误。这个 bug 影响的不仅是 lean-zip，而是所有使用相同 Lean 编译器版本编译并依赖数组操作的 Lean 程序。

这揭示了一个深层的哲学问题：形式化验证的链条在某个地方必然需要一个「信任基点」（Trusted Computing Base, TCB）。即使是最严格的形式化验证系统，也必须在某处停止验证并开始信任。问题是，这个信任基点的边界在哪里？ sel4 微内核的做法是将整个二进制纳入验证范围，包括一个极简的运行时和编译器。但对于 Lean 这样功能更强大的语言，完全验证整个技术栈的成本可能令人望而却步。

不变式检查的断裂：从证明到执行

形式化证明本质上是对程序状态空间的一种抽象描述。证明中的不变式（Invariant）—— 例如「数组索引永远不会越界」或「压缩后总能解压缩为原始数据」—— 是在证明环境中建立的逻辑断言。然而，这些断言在编译和执行阶段是否被保持，取决于多个隐藏假设。

第一个断裂发生在规范层面。开发者可能证明了 length(leftpad(s, n, ch)) = max(n, length(s))，但实际需求可能是更精确的行为，例如对 Unicode 字符的处理方式。多字节字符在 UTF-8 和 UTF-16 中的表示差异，可能导致证明通过但实际输出与用户预期不符。这种情况下，bug 并不在代码实现中，而在规范本身的定义偏差中。

第二个断裂发生在环境假设层面。形式化证明通常依赖于特定的环境假设，例如「整数运算不会溢出」或「内存是无限的」。这些假设在证明环境中可能完全成立，但在实际运行时可能失效。Lean 4 提供了 Int.ofNat 和 USize 等类型来处理不同范围的整数，但如果开发者混用了这些类型或在边界条件下未能正确处理，证明仍然可能通过而运行时却会失败。

第三个断裂正是 lean-zip 案例所展示的：运行时本身的 bug。证明假设运行时会正确执行其承诺的功能 —— 内存分配、数组操作、异常处理 —— 但这些假设的成立取决于未被验证的外部代码。当运行时出现 bug 时，整个「已验证」程序的行为可能变得不可预测。

工程层面的缓解策略

面对这些断裂，形式化验证的实践者已经发展出一系列工程补偿策略。

第一，明确界定验证边界并显式声明。在任何验证项目开始时，团队应该明确列出哪些代码已被验证、哪些代码未被验证，以及验证所依赖的假设清单。 lean-zip 案例的作者在发现 bug 后明确指出：「两个 bug 都在证明覆盖范围的边界之外」—— 这种清晰的边界声明对于后续维护者和使用者至关重要。

第二，将运行时纳入验证的 TCB 进行审计。虽然完全验证 Lean 运行时可能不切实际，但对关键路径进行手动审计和模糊测试是可行的。AI Agent 配合结构化模糊测试的方法已经在 lean-zip 案例中证明了其价值 —— 它发现了人类开发者和传统测试流程都未能捕获的运行时 bug。

第三，建立运行时不变式监控。即使证明无法覆盖运行时代码，在生产环境中部署不变式检查器可以在运行时捕获异常行为。例如，使用 Linux 的 ptrace 或类似的运行时检测工具来监控数组访问边界、内存分配模式等，可以作为形式化验证的补充防线。

第四，对规范进行分层验证。将「核心算法正确性」与「输入处理安全性」分开验证。前者可以使用形式化证明，后者则应该结合模糊测试和边界测试。压缩库的核心算法可能已被完美验证，但如果解析器对畸形输入的处理不当，整个系统的安全性仍然会受到威胁。

结论：证明是起点而非终点

lean-zip 案例给形式化验证社区的教训并非「验证无用」，而恰恰相反 —— 它说明了验证的真正价值在于清晰地界定已知正确的部分，从而强制开发者正视未知部分。当 Lean 证明了一个程序正确时，正确的理解应该是：在给定规范和假设的前提下，该程序的行为被形式化地确认。如果规范本身不完整、如果环境假设不成立、如果运行时存在 bug—— 这些问题都会独立于证明而存在。

对于工程实践者而言，这意味着在使用形式化验证工具时，应该始终追问：我验证了什么？我假设了什么？谁在为这些假设背书？只有当这些问题的答案足够清晰时，「证明正确」才能真正转化为「生产可靠」。

参考资料

  • Kiran 博客: "Lean proved this program correct; then I found a bug" (kirancodes.me)
  • Hillel Wayne: "Let's Prove Leftpad" - 形式化验证中弱不变式的经典案例
  • Hacker News 讨论: id=47759709 - 开发者对验证边界与运行时 bug 的深入讨论