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

术语表

本页定义其他页面用到的术语,每个术语只定义一次,用一两句话说清。术语分为几组:目标、结论的两种状态、模型、前提、gzip 文件世界和证据。每项结论的状态见进度页。

目标

目标(goal)。 关于一个 C 函数或一个调用序列的一个 Lean 命题,名字以 Goal. 开头。只有类型与目标完全相同的定理才算证明了它。英文页里的 target 是同一个意思。

安全目标。 这类目标说:调用正常返回而不出故障(没有未定义行为,没有内存错误,并且终止),只写它获准写的内存(它的帧),并且不泄漏。多数安全目标名为 Goal.<函数名>_safety。

功能目标。 这类目标说调用的结果是什么:返回值、输出字节、与数据格式的关系。安全结论不依赖未完成的功能目标。

序列目标。 关于同一个流或句柄上每个调用序列的目标,例如 Goal.inflate_sequence_safety。它说:每段历史之后不变量都成立,再做一次调用也是安全的。

历史。 在同一个流或句柄上至今做过的调用,从初始化或打开调用开始,中间夹着调用者在两次调用之间所做的修改。序列目标对每段历史量化;历史用归纳谓词定义(StreamReachable、GzHistory、BackSafeReachable)。

可达。 一个流可达,是指有某段历史产生了它:一次成功的初始化,然后是任意多次调用和调用者修改。对应的 Lean 谓词是 StreamReachable;流函数的单函数安全目标在每个可达的流上成立。

拒绝。 C 以错误值驳回的调用,例如对 NULL 流或不一致的流的调用。拒绝子句给出返回的值,并说明调用可以改变什么。除四个初始化函数之外的每个有文档的 inflate 和 deflate 流函数、inflateCopy 和 deflateCopy、接受句柄的 gzip 文件函数,以及 inflateBack 和 inflateBackEnd,其安全目标在针对合法调用的子句之外都有一个拒绝子句;另有三个拒绝目标(Goal.inflate_refusal、Goal.deflate_refusal、Goal.gz_refusal)各用一个命题陈述若干函数的拒绝。哪些流算作被拒绝的流,以及返回的值和改变的内容,见偏离记录。

非空性目标。 这类目标说明其他目标的前提可以被满足:存在一个具体的堆,在它上面初始化或打开成功,并得到一个可达的流或句柄。没有它,序列目标就可能只是因为不存在任何历史才成立。

见证。 非空性目标给出的那个具体的堆(对 gz 还有具体的文件系统),例如 witnessHeap。

有文档的函数。 zlib.h 在注释 undocumented functions (not part of the zlib API) 之前声明的函数。该注释之后的十个函数是未文档化函数,它们各自的目标不在计划内。例外是 gzvprintf:gzprintf 要经过它,所以它有安全目标 Goal.gzvprintf_safety,它也是 gz 序列目标里的一种调用。

安全目标的种类。 目标构建有 86 个有文档的函数。安全结论由四种目标组成:单函数安全目标、序列安全目标、拒绝目标和非空性目标。单函数安全目标是每个有文档的函数各一个,再加 gzvprintf 一个;compressBound 和 compressBound_z 是纯函数,由功能目标代替安全目标。

仅关于模型的命题。 关于抽象 API 模型的定理,而不是关于翻译后的 C。在另有定理把两者联系起来之前,它对实现什么也没有说。

状态

一项结论、一个目标或一个函数,处于两种状态之一。

完成(done)。 存在一条命题与目标完全相同的 Lean 定理,并且它通过了本项目的每一项检查。这些检查是什么,见完成的结论依靠什么。

未完成(not done)。 不存在这样的定理。只有一部分有定理的目标是未完成;页面可以用平实的话说明哪一部分有定理。

不在计划内(not planned)。 对项目不为之投入工作的目标,在“未完成”之外加上的说明。

模型

故障(fault)。 模型对一次没有正常返回的运行给出的结果。C 可能到达的每一种未定义行为都产生 Fault.ub;循环耗尽燃料则产生 Fault.outOfFuel。安全定理说明没有任何运行产生这两者。gz 的目标把两者分开:gz 序列目标以及六个读取调用各自的目标,证明在任何世界里都不会出现 Fault.ub,并证明六个读取调用在有读取预算时返回。

燃料(fuel)。 翻译后的每个循环的迭代次数上限:2^64。结论为正常返回的定理证明了这个上限永远达不到;本项目所说的“终止”就是这个意思。

堆。 运行时内存模型:每类对象一张表(字节数组、字数组、z_stream 记录、gzip 头部、三种状态记录),加上静态表和分配器的簿记。

块。 堆中的一次分配,用一个编号指称。某张表在该编号下存有对象时,这个块就是存活的。释放过的编号不会再用。

指针。 NULL,或者“某个对象加偏移”的引用。模型里没有表示未初始化指针的值:新分配内存中的指针字段读出来是 NULL,所以漏掉一次写入是看不出来的。指针字段在被读取之前已被写入,这不是定理;它尚未确认,须由源码审查确认(可信基础第 2 项)。

良构的堆。 多数目标对调用开始时的堆陈述的三个条件:Fresh(下一个块编号及其以上没有存活的块)、Uniq(一个块编号至多在一张表中存有对象)和 LibraryGlobals(静态表就是所选构建的那些表)。它们描述的是模型的簿记;C 调用者无法破坏它们(模型的限制)。

ByteObjectsFit。 堆中每个字节数组都小于 2^63 字节,即 LP64 下单个对象大小的上限 PTRDIFF_MAX。它不限制内存总量,也不限制流的长度。

分配预言。 堆的字段 allocOk:从“第几次分配尝试”到“成功或失败”的函数。目标对每个预言量化,所以涵盖了分配失败的每一种模式。

任意初值函数(garbage function)。 堆的字段 garbage:给出新分配内存中每个整数单元的值。目标对每个这样的函数量化,所以对未初始化整数的任何内容都成立。

帧(frame)。 一次调用可以写的那些块和字节范围。“只写它的帧”是说:其余每个存活的块在调用前后相同(Frame、BufferFrame)。

账本(ledger)。 目标结论中对分配的精确记账:调用新建了哪些块、释放了哪些块(LiveChange)。“不泄漏”是说:调用之后仍存活的每个块,要么调用之前就存活,要么归这个流或句柄所有。

拥有。 流或句柄的状态指向某个块时,这个块就归它拥有:状态记录、窗口、哈希表、待输出缓冲区(StreamOwned、GzOwned)。

结果单元。 某个指针参数所指的变量,C 通过这个指针写出结果,例如 *destLen 或 *dictLength。有八个公开函数的翻译把这个单元当作值,而不是内存,所以它们的目标对这个单元的内存什么都没说:四个 compress* 函数、两个 GetDictionary 函数、deflatePending 和 deflateUsed(偏离记录的“结果单元”和“整缓冲区压缩”两行)。

库堆。 API 条目对上面定义的良构堆的叫法(契约约定)。

表示不变量。 流的状态所具有的、每次调用都保持的性质,例如 deflate 流的 DGood、inflate 流的 Good 和 gz 句柄的 GzInv。它由初始化或打开函数建立。

可信基础。 证明所依赖而内核并不检查的东西,共六项:Lean 内核与检查公理和命题的程序;运行时模型;手工翻译;选定的源码;构建配置与外部世界的模型;以及命题本身。见可信基础。

固定版本(pin)。 这些证明所针对的上游 zlib 提交。被验证的源码是这个固定版本加上按文件名顺序应用的补丁。

规范化。 翻译可以不同于逐语句照抄 C 的四种方式之一,每一种的行为都与 C 相同。翻译逐条列出它们,各配一个例子。翻译中另有至少六种形式,是这四种覆盖不到的(可信基础第 3 项)。改变了 C 的计算结果的差别是翻译缺陷。

前提

前置条件、前提。 定理对其输入所作的假设。

偏离。 比 zlib.h 允许的范围更窄的前置条件。它写在陈述它的那个定义的文档注释里,并列在偏离记录中。

分离前置条件。 调用者的各内存区域互不重叠,也不与流自己拥有的存储重叠。定理把它写成一条假设。

调用者修改。 调用者在一段历史的两次调用之间对流所做的事:改 z_stream 的 next_in、avail_in、next_out 或 avail_out,或者改不归这个流拥有的内存。对应的 Lean 谓词是 Rebuffer;gz 的对应形式是 GzCallerFrame。调用者改了流的其他任何东西的历史,不在序列目标之内(偏离记录的“调用之间调用者的修改”一行)。

聚焦契约。 API 手册中的这样一个条目:它的前置条件描述通常的正确用法,有意比函数实际接受的范围窄(契约约定)。

DefaultOrNull。 流的 zalloc 和 zfree 各自是 Z_NULL 或库的默认函数。使用自定义分配器的流不在任何目标之内。

StreamBuffers。 关于 next_in、avail_in、next_out、avail_out 的假设:每个范围是 NULL 或可读(输出范围还须可写),都不落在流自己的存储里,并且两个范围相互分离。安全目标中的每次 inflate、deflate 和 deflateParams 调用都假设它。

gzip 文件世界

世界。 模型中供 gz 函数使用的操作系统状态(Fs):文件、打开的描述符、errno,以及两个预言,一个管系统调用,一个管 vsnprintf。gz 安全目标对每个良构的世界成立。

系统调用预言。 世界中的一些字段,为每次 open、read、write、lseek 和 close 调用决定:按普通文件行事、以选定的 errno 失败,或者返回模型给该调用规定的范围之内的某个选定结果。

读取预算。 一个描述符还能交付的字节数(readBudget)。六个 gz 读取调用的终止,是在预算小于 2^61 字节(ReadsFinite)的条件下证明的。

检查

差分测试。 用同一输入分别运行真实的 C 和 Lean 翻译,再比较结果。它是忠实度的证据,不是证明。

sanitizer 复现。 一个小的 C 程序:用 AddressSanitizer 或 UndefinedBehaviorSanitizer 构建真实的 zlib 时,它让某个问题显现出来。它是关于真实 C 的一次运行的证据,不是证明。

允许的公理。 propext、Classical.choice 和 Quot.sound,即 Lean 的三条标准公理。完成的结论不依赖其他任何公理。

精确命题。 完成的结论背后那条定理的类型与目标完全相同。多带一条前提的定理不算数。

内核重放。 读者可以运行的一项独立检查:Lean 内核在一个全新的环境里把编译好的结论及其依赖的一切重新检查一遍(lake env leanchecker --fresh ZlibF.Results)。它不是每次改动都运行;每次改动都经过的内核检查是构建中的那一次。

ZLIB × LEAN

目录

正在阅读术语表