From LaTeX and OCaml to LEAN4 and Executables: Lean-Checked Theorems and Generating Proof-Carrying Rust
本文提出了一种基于 Python 的 Hindley–Milner 前端，用于处理 OCaml 的一个子集，该前端能够同时生成经 Lean 4 验证的定理以及带有证明携带契约（proof-carrying contracts）的可执行 Rust 代码，并通过互归纳类型、有符号整数算术以及对其内核及其自描述方程的跨实现验证，成功验证了该系统。
原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
在软件世界中，代码的编写方式与我们如何确保其安全性之间存在着一种持续的张力。程序员使用高级语言以一种易于理解和管理的方式来描述复杂的逻辑，但运行这些代码的机器所使用的语言却要简单得多，也僵化得多。为了从一种语言过渡到另一种语言，编译器充当了翻译者的角色，但这个翻译过程正是错误经常潜伏的地方。翻译中的失误可能会将一条安全的指令变成一条危险的指令，导致程序崩溃或行为异常。几十年来，确保安全性的最可靠方法是验证最终的机器码，但由于原始程序的高级含义在这一过程中往往会丢失，这变得非常困难。研究人员提出的问题是：我们能否在保持原始高级语言清晰度的同时，仍然能够以绝对的确定性证明最终的机器指令完全符合我们的预期。
布伦特·哈特肖恩（Brent Hartshorn）构建了一个系统来回答这个问题，该系统将一段代码同时视为两种不同的事物。想象一份文档可以同时被读作数学证明和一组机器指令。在这项新工作中，作者采用了 OCaml 语言的一个子集（该语言以其对数据处理的严格规则而闻名），并赋予了每一个定义两个截然不同的含义。首先，代码被读作一个逻辑论证，程序的结构本身即作为证明某些条件将始终得到满足的证据。其次，同一段代码被翻译成另一种名为 Rust 的语言，Rust 旨在追求速度与安全，并随后被编译成计算机可以实际运行的程序。这种方法的精妙之处在于验证过程：逻辑证明由一个微小的、受信任的数学引擎进行检查，而运行中的程序则通过一个逐步模拟代码执行过程的参考解释器来进行校验。如果两者相匹配，且逻辑证明成立，那么结果就是一段自带“安全证书”的软件。
研究人员首先构建了一个理解特定 OCaml 片段的翻译器。这个用 Python 编写的翻译器足够小，以便由单个人阅读和理解，这至关重要，因为如果翻译器本身过于复杂，我们就无法信任它的输出。它接收 OCaml 代码并将其拆分为两条路径。在证明路径上，它将代码转换为一种数学内核可以检查的格式。这个内核是一个微小的程序，充当裁判的角色，在不做出任何假设的情况下验证逻辑是否严密。在程序路径上，翻译器将代码转换为 Rust，随后 Rust 会被编译成快速的原生机器码。为了确保翻译是完美的，团队还构建了一个直接运行原始 OML 代码的参考解释器。随后，他们通过这个解释器和编译后的 Rust 版本运行了 13 个不同的示例程序。在每一种情况下，编译后的代码产生的输出都与解释器的输出完全一致，这证明了翻译过程并未改变程序的行为。
代码成功翻译后，团队对编译后的 Rust 版本应用了严格的安全检查。他们将编译后的代码视为一份契约，其中关于程序应如何行为的具体规则被写成了数学定理。例如，他们检查了整数计算是否会意外溢出并回绕为负数，这是软件中常见的漏洞来源。他们发现，虽然大多数此类安全规则都是成立的，但在特定的边缘情况中，这些规则被打破了。在 11 个不同的场景中，编译后的代码达到了一个整数计算可能发生回绕的点，例如从零减去最小可能的数字。系统正确地将这些识别为“开放义务”（open obligations），这意味着代码在除了这些特定的、已知的极限之外的所有地方都是安全的。在对示例程序进行的 90 项总安全检查中，79 项被完全证明，而剩下的 11 项由于代表了计算机处理数字时的真实可达极限而被留作开放状态。
该项目进一步将此方法应用于一个小型操作系统内核，这是管理计算机资源的核心软件。研究人员获取了一个此前用 Python 和 Rust 编写的内核，并用他们的 OCaml 子集重写了它。随后，他们将这个新版本翻译成 Rust 并进行了编译。结果得到了同一个内核的第三种实现。在与原始 Python 版本进行对比测试时，这个由 OCaml 衍生的版本在所有 236 个测试用例中均给出了正确答案。团队随后尝试证明这个新内核的安全性。他们成功证明了 236 个安全义务中的 227 个。那些未被证明的部分并非代码错误，而是由于用于检查它们的数学工具存在局限性，特别是在处理复杂的循环和计数器方面。这证明了该方法可以从小型示例扩展到功能性的操作系统组件。
这项工作最令人震撼的部分在于能够将数学方程直接转化为运行中的程序。研究人员采用了一种描述内核行为的标准数学符号形式的正式方程，并将其输入到一个能将其转换为 OCaml 代码的工具中。这段代码随后被编译并运行。生成的程序表现得完全符合该方程的描述，在每一次实例中都与原始 Python 模型的输出相匹配。这一过程表明，高层级的数学描述可以在不丢失其含义的情况下，转化为经过验证的可执行二进制文件。团队证明了该方程的编译版本满足了大部分安全契约，尽管其中一些更复杂的逻辑步骤需要对检查工具进行进一步的改进。
这项工作的发现为构建可靠软件指明了一条新路径。通过保留高级源代码并同时验证其逻辑含义及其编译形式，研究人员创建了一个程序的安全性由数学证明支撑的系统。该方法成功识别了计算机处理数字时的现实局限性（如整数溢出），并将这些局限性与真正的程序漏洞区分开来。虽然该系统未能证明内核中最复杂部分的每一个安全规则，但它证明了绝大部分规则，并且那些未被证明的部分被明确标识为需要改进检查工具而非代码本身的地方。这项工作证明了，我们确实可以掌控从高级代码到机器指令的翻译过程，从而确保最终的可执行文件拥有一份与创建它的逻辑一样严密的安全性证书。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。