总览:关于 zlib 证明了什么
本页说明本项目关于 zlib 证明了什么、假设了什么,以及证明是怎样搭起来的。要点是:默认 x86_64 Linux 构建中每个有文档的公开函数,都被证明在一个流、一个文件或一个解码器的每段调用历史上是安全的;这是对 C 的一份 Lean 翻译证明的,前提是每条定理自己写明的条件。加粗的词在术语表中有定义。
结论
已证明。 zlib 的默认 x86_64 Linux 构建中,每个有文档的公开函数都是安全的。对其前提所容许的每个输入,翻译后的调用都会返回,没有未定义行为,没有内存错误,只写它获准写的内存(它的帧),不泄漏,并且终止。这对调用序列也成立:对 inflate 流、deflate 流、回调解码器和 gzip 文件句柄的每段历史都成立。这里的每一句话都是一个目标,由一个类型与该目标完全相同的定理证明,并且每一个都已完成:定理存在,并通过了本项目的每一项检查。每个函数对应的定理见按函数查覆盖情况。
前提简述如下(按函数列出的见偏离记录):
- 源码是 zlib 1.4 加上七个补丁。未打补丁的 zlib 1.4 有发现一页列出的缺陷。
zalloc和zfree为Z_NULL:zlib 使用它的默认分配器。自定义分配器在每个目标之外。malloc失败的情况被覆盖。- 一段历史只关于一个对象:一个流(从它的 init 起)、一个 gzip 文件句柄(从它的 open 起),或一个回调解码器(从它的 init 起)。历史中的每次调用都满足对其参数的前提,不论它返回什么。两次调用之间,调用者只改动流记录的四个缓冲区字段,以及不属于这个对象的内存。每个目标都写明一次调用可以写哪些内存(它的帧)。没有目标说明同一程序中两个对象的历史如何组合。
- 一次调用中调用者的各个缓冲区互不重叠,也不与对象拥有的内存重叠;任何字节对象都不到 2^63 字节。
gzread、gzfread、gzgetc、gzgetc_、gzgets和gzungetc在描述符还能交付的字节少于 2^61 时被证明会返回。没有这条前提时,仍然证明了它们不引起未定义行为。gz 的写调用被证明会返回,所在的模型中write对非空请求从不返回 0。- 一次
inflateBack调用得到的输入少于 2^48 字节,并且in和out函数遵守目标写明的协议。 gzprintf或gzvprintf的调用是 C 对其格式串和参数有定义的调用,格式串中没有%n。模型不读取调用者的格式串,所以发现不了与参数不匹配的格式串。
另有一项功能结论也已证明:默认 zlib 流的往返。给 compress 留出 compressBound 的空间时,uncompress(compress(x)) = x。对流:在默认级别的 deflateInit 之后,deflate 调用可以用任意刷新值、对缓冲区作任意切分,最后由有输出空间的 deflate(Z_FINISH) 调用结束;这样写出的流,由 inflateInit 之后的 inflate 调用在任意切分下、有输出空间时读回,得到的恰好是原输入。它的前提包括每次分配都成功、不用预设字典。deflateParams、重置和其他级别不在其中(往返)。
所作假设。 这些定理说的是一份运行在运行时模型上的 Lean 翻译。有六件事是被信任而没有被证明的(可信基础):
- Lean 内核、三条标准公理,以及检查证明用了哪些公理、定理的命题是否与目标完全相同的程序;
- 关于内存、指针、故障和循环的运行时模型;
- 对 C 的手工翻译;
- 选定的源码:固定版本的 zlib 加上各个补丁;
- 构建配置,以及分配、文件和格式化的模型;
- 命题本身:每个目标说的确实是它该说的。
差分测试是忠实度的证据,不是证明。编译器、操作系统和硬件的正确性在证明之外。定理对调用者提出的前提列在偏离记录中,按函数排成核对清单。
未完成。 这一往返之外的功能正确性:其他配置下的往返,或 inflate 对格式拒绝的流做什么。安全结论不需要它;安全证明依赖某个功能性事实时,该事实得到了证明。它不在计划内;仅关于模型的命题(说的是抽象 API 模型,而不是翻译后的 C)、其他构建配置,以及 zlib.h 声明为未文档化的函数,也都不在计划内。进度页把每项结论列为完成或未完成,并列出不在计划内的每一组及其理由。
目录
证明是怎样搭起来的
证明分四步。
- 翻译。 固定版本的 C 加上各个补丁,由人手工逐条语句翻译成 Lean。C 可能到达的每一种未定义行为,在翻译里都成为故障
Fault.ub。 - 定义不变量。 对每一类流定义一个不变量:在每次调用之前都成立的、关于流状态的事实。以 inflate 流为例:窗口是
NULL,或者是一个恰好2^wbits字节的可写块,其中有效字节的个数(whave)不超过它的大小(WinInv)。 - 逐个函数证明。 证明初始化函数建立这个不变量。对其余每个函数,证明它在不变量成立时返回而不出故障,保持不变量,只写它的帧,并且分配和释放的恰好是它的账本所记的那些块。不假设任何函数的行为:每个被调用的函数都有一条关于它自己的翻译的定理。
- 组合。 对调用历史作归纳,就得到序列目标。End 函数被证明会释放流拥有的每一个块。另有一条非空性定理给出一个具体的堆,在它上面初始化成功,所以这些前提不是空的。
flowchart LR
S["固定版本的 C 与补丁"] -->|"手工翻译"| T["Lean 翻译"]
T --> I["init:建立不变量"]
I --> V["不变量成立"]
V -->|"任意一次调用:不出故障,只写它的帧"| V
V --> E["End:释放拥有的每个块"]
通用方法详细给出这个归纳,实现论证给出每个 C 组件的不变量。
怎样读一项结论
一项结论有四个部分:目标、它的前提、证明它的定理,以及它的状态。下面以 inflate 为例。
| 部分 | 对 inflate 而言 |
|---|---|
| 目标 | Goal.inflate_safety |
| 它说了什么 | 两个子句。调用子句:对每个堆、每个流 r 和每个 flush 值,只要前提成立,调用 inflate(r, flush) 就返回而不出故障,保持不变量,只写流自己的块、流记录、挂接的 gzip 头部和输出范围,并且存活块集合的变化与它的账本完全一致(StreamCallSafe)。拒绝子句:对 NULL 流或不一致的流,调用返回 Z_STREAM_ERROR,不写原先存活的任何块,存活块的集合保持原样 |
| 前提 | 调用子句的前提是 StreamCallDomain:流是可达的(有一段从成功的初始化开始的历史产生了它);每个字节对象都小于 2^63 字节;缓冲区符合偏离记录的描述(StreamArguments)。拒绝子句的前提是:流是被拒绝的流(RefusedInflate,见偏离记录,注 2),并且模型的堆在下一个未用块号及其之后没有存活的块(Fresh) |
| 定理 | ZlibF.Spec.Public.StreamCallSafetyProof.inflate_safety |
| 状态 | 完成(见术语表) |
按函数查覆盖情况对每个函数给出同样的四个部分。
读任何一项结论时,有两点要留意。
- 关于某一个分支的引理,或者关于抽象 API 模型的定理,并不确立一个公开函数的结论。只有类型与目标完全相同的定理才算。
- 有限次的差分测试检查的是例子,证明不了关于所有输入的命题。
各条规则写在哪里
| 问题 | 页面 |
|---|---|
| “安全”到底指什么:未定义行为、帧、终止、泄漏? | 安全性 |
| 假设的是哪个平台? | 平台:默认 x86_64 Linux 构建;每个字节对象小于 2^63 字节,这并不限制流的长度 |
| 调用者的调用要满足什么? | 偏离记录 |
| 模型有哪些调用者无能为力的限制? | 模型的限制 |
| 什么是被信任而没有被证明的? | 可信基础 |
| 哪条定理覆盖某个函数? | 按函数查覆盖情况 |
| 哪些结论完成了,哪些未完成? | 进度 |
| “完成”二字背后有哪些检查? | 完成的结论依靠什么 |
安全目标的全称量词覆盖其前提所容许的每个输入、参数、分配结果和历史。输入配置中那些较窄的范围描述的是内部引理,并不限制安全目标。