使用 Lean 和 LLMs 进行证明自动化

使用 Lean 和 LLMs 进行证明自动化

LLMs 正在使形式验证变得实用

依赖类型语言的采纳历史上面临的主要障碍是“证明工作量”——证明程序遵循其指定不变量所需的巨量人力劳动。seL4 微内核项目为此开销提供了基准，工程师们在证明系统上花费的时间大约是设计和实现时间的 10 倍，导致证明代码的行数是 C 代码的 20 倍。

大型语言模型（LLMs）通过自动生成这些证明正在改变这一局面。由于像 Lean 这样的依赖类型系统可以机械地验证证明是否正确，LLM 的“幻觉”风险被消除：如果 LLM 生成了错误的证明，类型检查器只会直接拒绝它。这种转变将软件工程的负担从编写实现和证明转移到编写精确的形式规范。

案例研究：Lean 中的已验证 Zstandard 解压缩器

为了探索 Lean 与 LLM 自动化的交叉点，实现了一个 Zstandard（zstd）解压缩器。Zstandard 是一种高性能压缩工具，它结合了 LZ77 和一种称为有限状态熵（Finite State Entropy，FSE）的复杂熵编码器。

FSE 的挑战

FSE 是一种基于状态机的熵编码器，通过将符号分布到多个状态中，允许每个符号具有 fractional bits（小数位）的比特。这使得它能够实现比仅限于整比特增量的 Huffman 编码更高的压缩率。然而，FSE 要求解压缩器从块的末尾逆向读取比特，这显著增加了实现复杂度。

形式化不变量

在普通语言中，优化解码循环所需的假设通常被放到注释或运行时检查中。在 Lean 中，这些可以被编码为形式定理。在 FSE 表构造过程中，以下普遍属性在 LLM 的帮助下被正式证明：

  1. 正确的表大小：表格匹配指定的精度常量。
  2. 符号分布：分配给符号的状态数量正确地反映其概率。
  3. 状态有效性：对于任何状态，添加基线值和读取的比特始终会得到一个有效的状态编号。
  4. 可达性：对于每个非零概率的符号，恰好有一个状态可以到达任何给定的目标状态。

这些证明传统上需要数小时或数天的人工努力，而在大约 20 分钟内由 LLMs 生成。

Lean 在系统编程中的技术优势

Lean 提供了一些特性，使其相比传统定理证明器更适合用于编程：

  • 严格求值：与 Haskell 的惰性不同，Lean 是严格的，这使得性能和资源使用更易于推理。
  • 命令式语法糖：Lean 的 monadic do 表示法支持 for 循环、return 语句和 break 语句，允许使用命令式编程风格。
  • 引用计数优化：当对象的引用计数为一时，Lean 可以执行就地修改，从而实现类似命令式语言的高效数组更新。

已验证软件的未来展望

向规范工程的转变

行业讨论表明，程序员的角色正在转向“规范工程”。如果实现是由 LLM 生成并由定理证明器验证的工件，那么软件唯有人类面向的部分就变成了规范本身。这要求规范具有模块化、可组合且足够简短，以便人工验证。

扩展问题

一些批评者认为，依赖类型在一般维护方面无法扩展。为程序添加新的不变量通常需要细化每个依赖类型，并在整个代码库中调整每个证明，因为计算和证明交织在一起。所提出的替代方案是主要在模块边界使用依赖类型以暴露不透明类型，而将内部问题单独处理。

已验证的汇编和性能

人们对使用类似 AWS 的 LNSym（AArch64 的语义和模拟器）这样的工具进行高级 Lean 函数与优化后的汇编实现之间等价性的证明兴趣浓厚。这将使 LLMs 能够在不引入功能错误的情况下激进地优化汇编代码，因为等价性可以得到形式验证。

‘错误事物的正确性’风险

形式验证证明实现与规范匹配，但它不能证明规范本身就是用户实际想要的。正如社区讨论所指出的，如果提供给 LLM 的规范也是相反的，LLM 可能会勤勉地证明一个完全倒置实现的功能的正确性。

Sources