跳到正文
参考文档 / ZLIB × LEAN

可信基础:内核不检查什么

内核对照 Lean 命题检查证明。这个命题说的是不是选定的 C 源码的真实情况,还取决于下面六项。它们经过审查和测试,但没有被证明;把证明编译通过并不能免除它们。

# 被信任的东西 靠什么检查
1 Lean 内核、三条公理,以及检查公理和命题的程序 构建:内核检查每个证明,对结论的检查查看每条定理的类型和它依赖的公理。内核在全新环境中的重放是读者可以运行的一条命令
2 运行时:堆、指针、故障、循环、建模的库调用 审查和差分测试
3 对 C 的手工翻译 审查,以及与真实 C 对比的差分测试
4 选定的源码:zlib 1.4 加七个补丁 补丁页面。每个补丁所修的缺陷都已用真实的 C 在 sanitizer 下复现,有两处例外:0003 的一个分支依据的是对 C 的解读;0006 和 0007 修复的是没有兑现的承诺,没有 sanitizer 会报告
5 构建配置,以及外部世界的模型 对照 glibc 与 POSIX 的审查;差分测试
6 命题:每个目标说的确实是它该说的 对照 zlib.h 的审查;“定理的命题与目标完全相同”的检查

编译器、操作系统和硬件的正确性完全在证明之外。差分测试是忠实度的证据,不是证明。

相关页面:安全性定义结论;偏离记录列出调用者必须满足的前提;模型的限制是第 2 项的细节;为什么构建通过还不够说明结论靠什么防护;每项结论的状态见进度。

1. 内核与允许的公理

被信任的是 Lean 内核,以及 propext、Classical.choice、Quot.sound 三条公理。构建库时,内核检查每个证明。在同一次构建中,对结论的检查查看定理所依赖的每个声明,只允许这三条公理。执行测试替代不了内核的检查。

独立的重放是读者可以运行的一条命令:lake env leanchecker --fresh ZlibF.Results 让内核在全新的环境中把编译好的结论及其依赖的一切重新检查一遍。它不是每次改动都运行。

做这些事的程序本身也是被信任的代码,它们依据的数据也是被信任的。对结论的检查是在构建中运行的 Lean 代码,检查的是这次构建刚检查过的声明。目标与定理的配对、必需目标的列表是手工写的;目标本身由检查自己找出,有目标不在任何列表中时检查失败。用来与必需目标对照的 zlib.h 函数列表是手工写的,并与固定版本的 zlib.h 作了对照。编译器生成的辅助声明(例如 ._unsafe_rec)不受 unsafe 和 partial 检查的约束。

2. 运行时与对象结构

运行时定义了翻译后的一次运行是什么意思。它提供:对象引用和更新;故障、顺序执行和循环;指针算术、读、写和比较;zlib 所需的库操作的模型,包括分配;strerror 返回的文本(libcErrnoText);字节指针地址的低位,CRC 代码会观察这些位;以及每类结构体的记录、常量、堆表和操作。最后这一组由程序生成;生成器和运行时结构参考也属于这一项。

“不出故障”的定理说的就是这些定义。设想的对应关系是:C 可能到达的每一种未定义行为都成为 Fault.ub。无符号算术是模算术。有符号算术、移位和转换由每处翻译加以检查;被采纳的例外和翻译中另有的几种形式见第 3 项。这种对应是有限度的,其中五点与每位读者都有关:

  • 未初始化的指针。 模型里没有表示未初始化指针的值:新分配内存中的指针字段读出来是 NULL,所以漏掉一次写入是看不出来的。对这样的字段作比较、复制和释放,在模型里可以成功,而 C 对此不作任何保证。C 在读每个指针字段之前都写过它,这一点不是定理,在这个模型里也不可能是;它尚未确认,须由源码审查确认。已证明的是:每一类状态的不变量(InflateInv、DInv、GzInv)在每个可达的流上、在每个有历史的 gz 句柄上成立,并且它说明了它提到的那些指针字段里是什么。
  • 未初始化的整数。 新分配内存中的整数单元取一个任意的值,由任意初值函数按单元固定下来。定理对每个这样的函数都成立。
  • 循环燃料。 一个循环至多运行 2^64 次迭代;耗尽这个上界就是 Fault.outOfFuel,终止证明要排除它。有一处命题允许 outOfFuel:gz 安全目标的前一半,它是“每个循环 2^64 次迭代以内”的部分正确性。随迭代而增长的未定义行为(每次迭代至少加 1 的有符号 64 位计数器)会在 2^63 次迭代之内出现,仍在燃料之内,所以不会被 outOfFuel 掩盖。
  • 表的就地更新。 执行写入的原语就地修改堆中的表(Space.modify)。有一条引理(modify_eq)说,这等于证明所用的那种函数式更新;对这条引理和表类型的审查属于这一项。
  • 指针加零与 NULL - NULL。 模型给 C17 没有定义的两种操作规定了结果。加零或减零返回原指针,对每一种指针值都如此:空指针、从未写入的指针字段、指向已释放块的指针。NULL - NULL 是 0。在这些指针上的其他运算都是故障。这比 ISO C 宽松:ISO C 只对指向存活数组对象或其末尾后一位的指针定义 p + 0。被验证的源码会到达这两种操作。gzseek64 和 gz_skip_have 在 x.next 上计算 x.next += 0,而它可能从未写入,或指向调用者已释放的调用者缓冲区。目的缓冲区为 NULL、容量为 0 的 compress 调用在目标之内,它的 deflateInit 成功时,compress2_z 计算 stream.next_out - dest,两个指针都是 NULL。“不出故障”的定理并不说明 C 避开了这两种操作(模型的限制,“指针加零与 NULL - NULL”一行)。

完整的列表在模型的限制中,分三个小节:“内存与库操作”(memcpy、malloc、free 等被建模的调用检查什么)、“表示上的缺口与证明义务”(指针、数组范围、地址、只读标记)和“表的更新”。

3. 手工翻译

翻译是手工逐条语句写成的。内核不检查它与 C 是否对应。审查要核对求值顺序、各处检查、算术、存储的生命周期和效果。不一致就是翻译缺陷:关于一条译错的语句的定理,对 C 什么都没有说。

翻译与字面上的逐句照搬有四处被采纳的不同,每一处都与 C 等价:内部函数的输出参数按值传入,并作为第二个结果返回;对同一位置的两次读取,中间没有写入时,合为一次读取;对同一记录的字段的连续赋值,合为一次记录更新;有符号运算如果已被同一函数中前面的判断限制在范围之内,就使用普通运算符。翻译规则对每一处各举一例。

翻译中还有至少六种形式,是上面四处覆盖不到的:刚写入的值不经读取就再次使用;某个操作数在 C 中由短路判断把守,翻译却在判断之前对它求值;字段的值取自一条在某次写入之前加载的记录;按常数计数的移位使用普通运算符;inflate 中 C 没有初始化的局部变量从固定的值开始;一次写入在 C 中位于某次调用之前,翻译却把它写在这次调用之后。其中每一种算出的都是 C 所算出的,这一点是被信任的,没有被证明。翻译列出了已知的位置;这份列表并不完整。

这一项中有三部分容易被忽略:

  • 定义在翻译文件里的辅助定义。 并非每个语义辅助定义都属于运行时。带检查的算术和移位、整数转换、循环和控制流的形式、字段和表的访问、分配器的分派、局部存储、字符串字面量以及库函数的替身,都定义在使用它们的翻译文件里。它们和运行时一样被信任。架构按种类列出了它们。
  • CRC 的按字读取。 crc32.c 通过一个转换成 z_word_t * 的指针读缓冲区。翻译(loadWord)读八个字节,并按小端拼起来。两者一致,以及这个转换的别名语义,都是被信任的(模型的限制,“CRC 地址与字访问”一行)。
  • inflate 的局部变量。 翻译(IL.init)给 C 没有初始化的局部变量 copy、len、from、here 和 last 的值是 0、NULL 和一个全零的 code。inflateBack 使用同一个记录。对未初始化整数的规则是取任意值;这里的值却是固定的。inflate 是否可能在给这些局部变量赋值之前读它们,尚未确认,须由源码审查确认:关于当前翻译的证明说明不了这一点。

差分测试把有限次的执行与真实的 C 作比较。它们是忠实度的证据,不是证明。尤其是,结果一致加上 sanitizer 没有报告,并不能确立某个 C 表达式的语义有定义。

4. 选定源码

被验证的源码是 zlib 1.4(上游提交 99623ef7),加上按文件名顺序应用的各个补丁。补丁修复 zlib 的一个问题:不修复它,某个安全命题就无法证明,或者 zlib.h 的某项承诺不成立。补丁只做修复所需的最小改动;并与提交上游的修复一致。

应用了七个补丁。每条定理说的都是打过补丁的源码,所以每个补丁都是读者所信任内容的一部分。补丁给出每个补丁的证据。

补丁 修复的问题 上游状态
0001 inflateCopy 中对无关指针作大小比较 即上游 PR #1369 的提交,维护者已回复“Applied”;zlib 1.4 尚不包含它
0002 gzungetc 之后 gzseek64 中的有符号溢出 上游 PR #1361 的 gzlib.c 部分,该拉取请求处于打开状态
0003 透明模式下部分读取失败后 x.next 过期,以及读取时 gz 位置 x.pos 的溢出 上游 PR #1405,该拉取请求处于打开状态
0004 写入时 gz 位置 x.pos 的溢出 上游 PR #1406,该拉取请求处于打开状态
0005 lseek 的结果为负时 gzoffset64 中的有符号溢出 上游 PR #1404,该拉取请求处于打开状态
0006 Z_FIXED 在级别 1 到 3 时 deflateBound 偏小 上游 PR #1394,该拉取请求处于打开状态
0007 gzip extra 字段长度为 2^32 - 2 或 2^32 - 1 时 deflateBound 偏小 上游 PR #1360 的 deflate.c 部分,该拉取请求处于打开状态

5. 配置与外部世界

目标是默认 x86_64 Linux/LP64 静态构建和默认分配器。平台范围要求每个表示出的字节对象小于 2^63 字节。这是环境前提:LP64 下单个对象大小的上限 PTRDIFF_MAX。各目标在哪里陈述它,见偏离记录。分配失败是被覆盖的。其他构建配置和自定义分配器需要各自的对应关系论证;它们不在计划内(进度)。

分配大小。 对超过 PTRDIFF_MAX(2^63 − 1 字节)的请求,malloc 无论分配预言如何都返回 NULL。该调用仍消耗一个预言编号,之后的堆与预言失败之后的堆相同:除请求大小外,调用者无法区分两者。低于该上限时由预言决定。这是 glibc 2.43 的行为(malloc/malloc.c:_int_malloc 与 __libc_realloc 检查 bytes > PTRDIFF_MAX,返回 NULL 并设置 ENOMEM;__libc_calloc 先拒绝溢出 size_t 的乘积)。malloc 的 errno 不建模;zlib 没有路径在分配之后读取它。只有两个调用点可能发出这样的请求(gz_open 的路径复制和 gz_error 的消息);其他分配的大小是 unsigned 或固定值。因此每次库分配都使每个字节对象保持在 2^63 字节以下(ByteObjectsFit.allocB),平台前提只对调用者存储才需要。

格式化。 GzFs.snprintf 模拟 gzlib.c 的三个固定格式调用("%s%s%s"、"%s"、"<fd:%d>")。它在 [dst, dst + size) 内写入完整输出的至多 size - 1 个字节和一个 NUL,返回完整长度;超过 INT_MAX 时返回 -1。在 glibc 2.43 中,对带 char * 参数的 %s,以及对 %d,这是唯一的失败情形(stdio-common/vfprintf-process-arg.c 的 form_string 与 form_integer;stdio-common/Xprintf_buffer_done.c,超过 INT_MAX 时为 EOVERFLOW)。它的 errno 不建模。在系统调用再次设置 errno 之前,没有调用者读取它:模型只在 zstrerror 和 getErrno 中读取 errno,位于 gz_comp(在以 setErrno 0 开始的迭代中 fsWrite 失败之后)、gz_load(在 fsRead 失败之后)和 gzread(当 again 由同一次调用中的 gz_load 设置时)。

snprintf 的格式化函数(formatGo)在它读到的转换说明中,凡 C17 7.21.6.1 未定义的都出故障:%c 或 %s 上的长度修饰符、zl 这样的修饰符组合、%% 两个 % 之间的任何内容、%c 或 %s 上的 0 标志、%d、%i、%u、%c 或 %s 上的 # 标志、%c 上的精度、NULL 的 %s 参数,以及给无符号转换传负的有符号参数。所以库的三个调用都被证明是有定义的。VaArg.long 代表转换所期望的 64 位类型(long、long long、intmax_t、ptrdiff_t 或 size_t)。

调用者的格式串。 GzFs.vsnprintf 把 gzvprintf 的调用 vsnprintf(next, state->size, format, va) 作为外部调用,按其 C 契约(C17 7.21.6.12)建模,而不是格式化。假定:这个调用对调用者的格式串和参数在 C 中有定义。这是调用者的义务,和 printf 族的每次调用一样;没有前提陈述它。特别地,格式串中没有 %n:通过参数写入的转换在契约之外。带 %n 时,调用会写调用者的内存,而结论的框架不描述这种写入,所以这项义务排除了 %n。模型的参数类型(VaArg)只有 int、uint、long、ulong 和 str 几种情形;带浮点或 %p 参数的调用不在目标所量化的调用之中。模型把格式串当作字符串读取,并在指针参数指向已释放的块时出故障(不确定的值,C17 6.2.4p2)。它不读取转换。所以,与参数不匹配的格式串在 C 中是未定义行为,在模型中却不是故障:对这样的调用,Goal.gzprintf_safety 和 Goal.gzvprintf_safety 对模型成立,对 C 什么也没说。世界预言选择结果 r(printfRet),可以是任意 int:

  • r ≥ 0:完整输出的长度,可以是 size 或更大。调用写入 printfOut 的前 min(r, size - 1) 个字节(不足时补零),其后一个 NUL。
  • r < 0:失败。errno 非零(printfErrno;零按 EOVERFLOW 读),缓冲区中是任意字节(至多 printfOut 的 size 个),不保证有 NUL。

不写 [dst, dst + size) 之外的任何内容。每个目标都对所有世界量化,所以契约允许的每个结果都被覆盖,glibc 的各种失败也在其中。

gz 文件世界。 文件系统的模型(Fs)有两部分。普通文件部分表示扁平路径、普通文件、目录标记、描述符位置和文件大小上限。系统调用预言(Fs 的字段,由调用计数器 nos 编号)为每次 read、write、lseek、close 和 open 调用决定:按普通文件行为、以所选 errno 失败,或返回所选结果。每个预言值都被映射到模型给该调用规定的范围之内:read 返回 -1 或至多请求的字节数;非空 write 返回 -1 或 1 到请求字节数之间的值;lseek 返回 -1 或任意 64 位值,可能与之后的读取无关;close 返回 0 或 -1,两种情况下都释放描述符;open 返回 -1 或任一此前未打开且小于 2^31 的描述符编号;当 2^31 以下没有空闲描述符时,以 EMFILE 失败。失败设置非零 errno,成功也可能改变 errno。安全目标对每个世界量化,因此对每个预言量化。

在这些范围之内,预言容许的比真实系统多:预言的读写不论描述符状态如何(已关闭、访问模式不符)都成功;预言的写不改变文件;预言的 lseek 不移动描述符;读到的数据任意;普通读取仍受读取预算截断。这些选择只增加行为。open 返回的编号不再受别的约束,因为模型的描述符表不是整个进程。

有两条关于系统的事实被假设而不检查:非空 write 从不返回 0;close 即使报告错误也释放描述符。两条在 Linux 上都成立。对 lseek 不作任何假设:成功的调用可以返回任意 64 位值,包括负值,Linux 上偏移为无符号数的文件就是这样。第一条是 gz_comp 终止所需。尚未由证明确认:按对 C 的解读,一个永远返回 0 的 write 会让 gz_comp 永远循环,因为两个写循环在计数为 0 时都不前进。没有定理陈述这一点:模型中没有带这种 write 的世界。

strerror(C.libcErrnoText)对每个 Int32 都有定义。对表外的编号,它返回 glibc 的 "Unknown error N"(glibc string/strerror_l.c,已在 glibc 2.43 上核对;glibc 内存不足时不带编号的后备文本 "Unknown error" 未建模)。其文本至多 37 字节加一个 NUL,只读,有效期到下一次调用为止。对 glibc 认识而表中没有的 Linux 编号,文本与 glibc 不同;没有任何安全论证依赖文本或其长度,因为 gz_error 按 strlen 确定复制大小。

读取预算(readBudget)限制一个非负的描述符编号还能交付的字节数。它只是 gz 安全目标中关于终止的那一半的前提(偏离记录)。功能性的 gz 契约是针对“每个系统调用都按普通文件行事”的世界(RegularOs)陈述的。fcntl 没有效果;C 忽略其结果。

gz 文件世界和格式化模型是堆之外的可信语义。操作系统或库可能表现出的文件种类、错误、转换和外部字符串分配,它们并没有全部表示。回调解码器的定理假设了调用者对 in 和 out 的协议:两者都会返回,总输入有界,窗口被保持(偏离记录)。

6. 命题与权威

证明所确立的规格可能是不完整的,甚至是错的。所以命题本身要经过审查:把每个目标、它的前置条件和它提到的定义,与 API、格式和选定的 C 作比较。审查还要确认初始化建立了不变量,并且调用者的定义域没有被缩小。目标对调用者的要求多于 zlib.h 的地方,都列在偏离记录中。

没有程序固定定义和定理的类型:含义是否正确由审查决定。命题改变时仍然防得住什么,见为什么构建通过还不够。每项结论的状态见进度。

ZLIB × LEAN

目录

正在阅读可信基础:内核不检查什么