参考文档 / ZLIB × LEAN
为什么构建通过还不够
本页说明:一次每个证明都编译通过的构建为什么仍然可能毫无价值,以及本项目的结论靠什么来防住每一种这样的情况。要点是:Lean 内核对照定理的类型检查证明。它不检查这个类型是不是项目所声称的那个命题。一项结论要称为完成,仅有构建通过是不够的。
可信基础列出任何程序都不检查的东西。完成的结论依靠什么是本页的简短版本。
可能出什么问题,以及靠什么防住
| 可能出的问题 | 防护 |
|---|---|
| 把一个较弱命题的证明当作目标的证明 | 精确命题。 只有类型与目标完全相同的定理才算证明了目标。多一条前提、名字相近,或者是关于抽象模型的定理,都不算。 |
| 证明依赖一条没有依据的假设 | 只用允许的公理。 允许的是 propext、Classical.choice 和 Quot.sound,即 Lean 的三条标准公理。定理所依赖的每个声明都被检查,出现其他任何公理就拒绝。 |
| 证明用了绕过内核的构造 | 没有禁用构造。 源码中没有 sorry、native_decide、bv_decide、axiom、implemented_by、extern、unsafe、partial 和 opaque。 |
| 内核从未见过的证明项 | 构建库时内核检查每个证明,有警告构建就失败,源码不得设置任何关闭或削弱内核检查的选项。一次构建只复用由已被接受的源码构建出的编译模块,从不复用来自待审改动的模块。在全新环境中对编译好的结论作独立重放,是读者可以运行的一条命令(lake env leanchecker --fresh ZlibF.Results);它不是每次改动都运行。 |
zlib.h 的某个函数被悄悄漏掉 |
函数列表与固定版本的 zlib.h 作了比对。目标构建中每个有文档的函数都必须有带定理的安全目标,序列目标、拒绝目标和非空性目标也一样。 |
| 没有任何堆满足的不变量,使定理说的是空话 | 非空性目标:在一个具体的堆上,初始化或打开成功,并得到其他目标所谈论的流或句柄。 |
| 证明假设了它所调用函数的行为 | 任何结论都不假设一个自身未被证明的库函数的契约。每个被调用的函数都有一条关于它自己的翻译的定理。 |
| 翻译与 C 不一致 | 差分测试用同样的输入运行真实的 C 和翻译,其中的 C 用 AddressSanitizer 和 UndefinedBehaviorSanitizer 构建。它们是忠实度的证据,不是证明。 |
任何程序都不检查的东西
没有工具能判定一个目标说的是不是它该说的,也没有工具能判定运行时模型和翻译的含义是不是 C 的含义。一个命题可以连同它的证明一起被改成更容易的东西,而上面的每一项防护对改过的命题仍然成立:
- 目标仍然只由类型与它完全相同的定理证明,不管这个类型是什么;
- 仍然只允许那三条公理;
- 差分测试仍然针对现有的翻译运行。
这些都发现不了一个被改得更容易的目标。所以,依赖某项结论的读者要读它的目标的命题,以及命题提到的定义。项目遵守的规则是:绝不为了让证明通过而削弱命题、缩小定义域或改动翻译。只有在有证据表明命题原先是错的(例如有反例)时才改动命题。
什么才算证明
- 定理的类型与目标完全相同。
- 初始化函数被证明在整个允许的定义域上建立不变量。对顶层定理另加一个具体的见证;它补充全称命题,从不取代全称命题。
- 任何结论都不假设一个自身未被证明的库函数的契约。
- 没有任何允许的堆满足的不变量,不能用来支持公开的结论:非空性目标排除了这种情况。
编译器会生成一些标为 unsafe 或 partial 的辅助声明,例如 ._unsafe_rec。它们不受禁用构造规则的约束。其他任何属于禁用种类的声明都被拒绝。
人工审查
契约是否完整、运行时是否表示了所选 C 的语义、翻译是否与源码一致,要靠审查来判断。内核对证明体的检查代替不了这一点。审查的对象是命题、前置条件、运行时、偏离记录和补丁。