--- title: "形式化验证的边界：Lean 证明正确但运行出错的工程案例分析" route: "/posts/2026/04/14/formal-verification-lean-runtime-bug-case-study/" canonical_path: "/posts/2026/04/14/formal-verification-lean-runtime-bug-case-study/" canonical_url: "https://blog2.hotdry.top/posts/2026/04/14/formal-verification-lean-runtime-bug-case-study/" markdown_path: "/agent/posts/2026/04/14/formal-verification-lean-runtime-bug-case-study/index.md" markdown_url: "https://blog2.hotdry.top/agent/posts/2026/04/14/formal-verification-lean-runtime-bug-case-study/index.md" agent_public_path: "/agent/posts/2026/04/14/formal-verification-lean-runtime-bug-case-study/" agent_public_url: "https://blog2.hotdry.top/agent/posts/2026/04/14/formal-verification-lean-runtime-bug-case-study/" kind: "research" generated_at: "2026-04-14T19:18:15.628Z" version: "1" slug: "2026/04/14/formal-verification-lean-runtime-bug-case-study" date: "2026-04-14T08:51:37+08:00" category: "compilers" year: "2026" month: "04" day: "14" --- # 形式化验证的边界：Lean 证明正确但运行出错的工程案例分析 > 通过 leftpad 等实际案例揭示形式化验证的三大实践盲区：规范定义偏差、环境假设失效、证明与实现脱节，为工程团队提供可操作的验证边界检查清单。 ## 元数据 - Canonical: /posts/2026/04/14/formal-verification-lean-runtime-bug-case-study/ - Agent Snapshot: /agent/posts/2026/04/14/formal-verification-lean-runtime-bug-case-study/index.md - 发布时间: 2026-04-14T08:51:37+08:00 - 分类: [compilers](/agent/categories/compilers/index.md) - 站点: https://blog2.hotdry.top ## 正文 形式化验证常被视为软件正确性的终极保障——当定理证明器确认代码符合规范时，我们似乎获得了数学意义上的保证。然而，2024 年引发广泛讨论的 leftpad 验证事件向整个形式化方法社区投下了一枚震撼弹：多个使用 Lean、Coq 等证明器验证过的 leftpad 实现，在实际运行时产生了错误的输出。这个案例不仅揭示了形式化验证并非万能，更暴露了工程实践中容易被忽视的系统性风险。 ## leftpad 验证事件：从「证明正确」到实际 bug leftpad 是一个简单的字符串填充函数：给定字符 c、目标长度 n 和字符串 s，当 s 长度不足 n 时，在左侧填充字符 c 使总长度达到 n；当 s 本身长度已超过 n 时，直接返回 s。这个函数在 2016 年因 npm 删包事件而成为互联网 meme，随后成为形式化验证社区的热门练习题。 多个团队使用不同的定理证明器对 leftpad 进行了形式化验证，其中包括使用 Lean 的实现。这些证明通常验证的核心性质是：`len(leftpad(c, n, s)) == max(n, len(s))`。从数学上看，这个性质无懈可击——它精确描述了输出字符串的长度与输入参数的关系。然而，当开发者实际部署这些「已验证」的代码时，输出出现了问题。 具体来说，Lean 验证的 leftpad 将 `leftpad('-', 9, 'אֳֽ֑')` 渲染为 `------אֳֽ֑`（6 个短横线），而非预期的 `---------אֳֽ֑`（9 个短横线）。问题根源在于 Unicode 字符的视觉宽度与代码点数量之间的差异。希伯来字母 א 和其上方附加的发音符号 ײ 在视觉上只占据一个字符宽度，但在某些 Unicode 处理方式下可能被计为两个或三个代码点。形式化验证针对的是代码点层面的长度计算，而用户实际期望的是视觉层面的对齐效果。 这个案例的讽刺之处在于：证明完全正确，代码完全符合规范，但最终产品仍然存在 bug。这并非证明器的缺陷，也非开发者的疏失，而是形式化验证本身存在三个根本性的实践边界。 ## 边界一：规范与真实意图的语义鸿沟 形式化验证的核心信条是「证明代码符合规范」，但这个看似简单的命题背后隐藏着深刻的哲学问题：规范本身是否正确反映了我们的真实意图？ 在 leftpad 案例中，验证社区证明的是 `len(leftpad(c, n, s)) == max(n, len(s))` 这一数学性质。这个性质易于形式化、易于证明，也确实描述了函数的一种正确行为。然而，用户真正关心的属性是「输出在视觉上与同长度的其他字符串左对齐」，这两种属性在 ASCII 范围内等价，但在 Unicode 环境中分道扬镳。 形式化验证研究者 Hillel Wayne 将此问题归纳为「属性定义错误」（properties are wrong）。他认为，形式化验证社区经常满足于证明那些容易表述、容易验证的性质，而忽略了真正有业务价值但难以形式化的属性。这种现象在工程实践中极为普遍：团队投入大量资源证明代码符合「规范」，但规范本身可能只是对真实需求的粗糙近似。 以排序算法为例，证明「输出数组非递减」相对直接，但「排序结果对业务正确」可能涉及更多维度：稳定性（相同键值的元素顺序保持）、时间复杂度在特定数据分布下的表现、内存使用模式是否符合硬件缓存层次结构。这些属性在形式上更难表达，有时甚至难以给出数学定义。 规范与意图之间的语义鸿沟并非技术问题，而是认知问题。验证者需要与业务专家进行深度沟通，将模糊的业务需求转化为精确的逻辑规范，同时清醒地认识到：任何规范都是对真实需求的有损压缩。解决这个问题的唯一方法是显式记录「已验证属性」与「未验证属性」之间的边界，并在团队内建立共享的理解。 ## 边界二：环境假设的隐藏失效 形式化验证的第二大盲区是环境假设的隐藏失效。即使规范本身完美无缺，代码在运行时的行为仍然依赖于一系列未被显式验证的假设。这些假设包括：硬件行为（整数运算不溢出、内存访问按预期对齐）、操作系统特性（文件描述符语义、进程调度影响）、编程语言运行时（垃圾回收器的停顿时间、并发原语的行为）以及外部依赖（第三方库的版本、API 的稳定性）。 以整数溢出为例，几乎所有形式化验证教程都假设数学整数（Mathematical Integers），即整数运算永不溢出。然而在实际的程序运行环境中，整数溢出的情况屡见不鲜。2014 年，Google Blog 发表了经典文章《Nearly All Binary Searches and Mergesorts are Broken》，指出几乎所有教科书上的二分搜索实现都存在整数溢出 bug——当搜索范围较大时，`mid = (low + high) / 2` 可能发生整数溢出。这个 bug 在形式化验证的「整数不溢出」假设下根本不会出现，但现实世界的机器整数会无情地暴露它。 并发环境下的假设失效更加隐蔽。一个经过验证的单线程排序算法在多线程环境中可能产生数据竞争；一个假设无其他进程修改文件的文件操作在并发文件系统中可能失败；一个假设内存充足的数据结构在资源受限的嵌入式环境中可能崩溃。 更棘手的是，环境假设经常是隐式的而非显式的。形式化验证者可能不自觉地依赖某些假设，使证明变得更容易，但这些假设从未被正式记录。当代码部署到新环境时，这些未文档化的假设可能失效，而验证结果仍然显示「正确」。因此，工程团队需要在验证报告中明确列出所有环境假设，并为每个假设标注其适用范围和潜在风险。 ## 边界三：证明工件与可执行代码的断裂 形式化验证的第三大陷阱是证明与实现之间的断裂。即使开发者用 Lean 写出了完美的证明，这些证明所针对的往往是高度抽象的代码模型，而非最终部署的可执行二进制。 这种断裂在多个层面可能出现。首先是提取（extraction）阶段的问题：Lean 等证明器支持从证明代码中提取可执行的函数，但提取过程可能引入微妙的行为差异。其次是编译器引入的错误：验证者在证明阶段使用的是解释型代码或中间表示，而生产环境使用的是优化后的机器码，编译器优化可能改变代码语义（虽然这种情况在经过验证的编译器下不太可能发生，但现实中多数项目使用的是未经验证的编译器）。第三是外部代码的污染：经过验证的核心算法通常依赖未被验证的辅助函数、库调用或系统接口，这些外部代码的行为不受形式化验证的保障。 Rust 安全社区对此有深刻认识：Safe Rust 的内存安全证明建立在「Unsafe Rust 代码符合规范」的假设之上。如果Unsafe 代码中存在未定义行为，整个 Safe Rust 外壳的证明都可能失效。这种「信任链」问题在真实项目中普遍存在：形式化验证的边界通常止步于应用代码，而操作系统、运行时、硬件抽象层仍然属于「可信但未验证」的领域。 针对这个问题，实践者可以采取若干防御措施。使用经过验证的编译器（如 CompCert）可以消除编译器引入错误的风险；对外部依赖进行接口契约检查，可以在运行时捕获假设失效；建立「验证边界图」，显式标记哪些组件已验证、哪些依赖未验证，有助于评估整体风险。 ## 工程实践的启示 leftpad 案例并非形式化验证的失败，而是揭示了形式化验证的本质：它是一种数学证明技术，而非魔法般的bug消除工具。理解这一点对于正确应用形式化验证至关重要。 工程团队在决定是否采用形式化验证时，首先需要明确验证目标。如果目标是消除某类特定的运行时错误（如空指针解引用、数组越界），形式化验证可以提供强有力的保障。如果目标是确保软件「完全正确」，则需要对「正确」给出精确到数学符号的定义，而这个定义过程本身就是最大的挑战。 其次，验证范围的选择需要策略性。形式化验证成本高昂，不可能对整个系统进行无差别验证。实践中，通常选择关键路径、高风险模块或难以通过测试覆盖的边界条件进行验证。明确验证范围后，需要清晰记录哪些属性已验证、哪些未验证，避免产生虚假的安全感。 最后，形式化验证不能替代其他质量保障手段。测试、代码审查、运行时监控仍然不可或缺。形式化验证提供的是「在特定假设下，特定属性必然成立」的数学保证，而测试提供的是「在采样的输入下，代码表现符合预期」的实证证据。两者互补而非替代。 回到 leftpad 案例，那个「错误」的 Lean 实现其实完美地完成了它的规范所要求的一切。问题在于规范与用户期望之间的错位。这个故事给所有形式化验证实践者的启示是：证明正确只是开始，理解证明在说什么、证明没有说什么，以及证明的结论在何种环境下可能失效，才是工程实践的真正挑战。 --- **参考资料** - Hillel Wayne, "Three ways formally verified code can go wrong in practice" (https://buttondown.com/hillelwayne/archive/three-ways-formally-verified-code-can-go-wrong-in/) - Luke Plant, "Breaking 'provably correct' Leftpad" (https://lukeplant.me.uk/blog/posts/breaking-provably-correct-leftpad/) - Kiran Gopinathan, "Scaling the Evolution of Verified Software" - PhD Thesis (https://kirancodes.me/docs/thesis.pdf) ## 同分类近期文章 ### [无环 e-graph 在 Cranelift 中的实践：中端优化器的设计权衡](/agent/posts/2026/04/14/acyclic-egraph-cranelift/index.md) - 日期: 2026-04-14T21:26:25+08:00 - 分类: [compilers](/agent/categories/compilers/index.md) - 摘要: 深入解析 Cranelift 如何利用无环 e-graph（aegraph）实现中端优化，探讨其在寄存器分配与指令调度中的工程化权衡。 ### [Lumina 静态类型系统与双目标编译管线设计解析](/agent/posts/2026/04/14/lumina-static-type-system-dual-compilation-pipeline/index.md) - 日期: 2026-04-14T20:26:07+08:00 - 分类: [compilers](/agent/categories/compilers/index.md) - 摘要: 深入解析 Lumina 的 Hindley-Milner 类型推导、代数数据类型与 trait 多态，以及如何实现同一代码同时编译为 JavaScript 与 WebAssembly 的工程实践。 ### [Lumina静态类型系统与双目标编译：类型安全至Web生态的工程实践](/agent/posts/2026/04/14/lumina-static-type-wasm-compilation/index.md) - 日期: 2026-04-14T17:27:41+08:00 - 分类: [compilers](/agent/categories/compilers/index.md) - 摘要: 解析Lumina语言如何通过Hindley-Milner类型推断实现编译时安全保障，并将其统一编译为JavaScript与WebAssembly的工程化路径。 ### [Lean 4 运行时验证的盲区：从 proof-correct 到 bug-found 的断层分析](/agent/posts/2026/04/14/lean4-runtime-invariant-checking-gap/index.md) - 日期: 2026-04-14T15:26:27+08:00 - 分类: [compilers](/agent/categories/compilers/index.md) - 摘要: 深入解析 Lean 4 证明环境与生产环境的语义差异，聚焦运行时不变式检查缺失与工程缓解策略。 ### [Go 事务回滚验证 Linter 规则实现指南](/agent/posts/2026/04/14/go-transaction-rollback-verification-linter/index.md) - 日期: 2026-04-14T13:26:54+08:00 - 分类: [compilers](/agent/categories/compilers/index.md) - 摘要: 详解如何通过静态分析检测 Go 事务回滚路径中的边界泄露，确保 defer/rollback 路径覆盖与事务状态一致性。