偏离记录:一次调用要满足什么
本页写给调用 zlib 的人,回答一个问题:我的调用被安全定理覆盖了吗?下面的核对清单按函数族、用 C 的说法作答。清单之后的各表给出每一行背后的 Lean 前提、陈述它的目标,以及它的理由。
满足自己那个函数的各行,调用就被覆盖。不满足的调用不被覆盖:既没有被证明安全,也没有被断言不安全。
本页列出安全目标中每一条比 zlib.h 更窄的前提,以及读者容易漏看的前提。只是重复 zlib.h 的前提写在目标的 Lean 命题里;每个函数对应哪个目标,见按函数查覆盖情况。调用者无能为力的、对模型的条件在模型的限制中。被信任而没有被证明的东西在可信基础中。
给调用者的核对清单
每一行末尾是陈述它的 Lean 谓词;没有谓词陈述的行会注明。只有写明允许 NULL 的地方才允许 NULL。
每一次调用
- 库是默认的 x86_64 Linux 构建:LP64、静态链接,由 zlib 1.4(上游提交
99623ef7)加七个补丁编译而成。 - 每个
z_stream的zalloc和zfree都是Z_NULL,于是 zlib 使用它的默认分配器(DefaultOrNull)。自定义分配器不被覆盖。malloc失败是被覆盖的。 - 内存中没有任何单个对象达到或超过 2^63 字节(
ByteObjectsFit)。这是 LP64 下单个对象的上限PTRDIFF_MAX;它不限制内存总量,也不限制流的长度。 - 这些行对整段历史成立。一个流或一个文件上的某次调用被覆盖,前提是从它的初始化或打开算起,此前在它上面的每次调用也都满足各自的行;那些调用返回什么都可以(
StreamReachable、GzHistory、BackSafeReachable)。
inflateInit、inflateInit2、deflateInit、deflateInit2(zlib.h 的宏以及宏背后的函数)
strm是NULL,或者指向一个zalloc和zfree都为Z_NULL的z_stream(InitArguments)。- 除此之外没有要求。
z_stream的其他字段,包括state,可以是任何值。version(宏会替你传)是NULL或一个可读的字符串,stream_size可以是任何值:不匹配时调用返回错误码,并且不留下任何分配。每个level、windowBits、memLevel和strategy都被覆盖。
这就回答了最常见的那种调用:
z_stream s;
s.zalloc = Z_NULL;
s.zfree = Z_NULL;
s.opaque = Z_NULL;
int rc = inflateInit(&s); /* covered by Goal.inflateInit__safety */
这次调用被覆盖,结构体不必事先清零。它返回 Z_OK 时,定理还说这个流是可达的,所以此后在 s 上的每次调用都被下面的目标覆盖。对代码没有设置的字段,模型怎样处理,见注 1。
调用失败时,有两种情况下此后在 s 上的每次调用都以错误值被拒绝,因而被覆盖:调用返回了 Z_VERSION_ERROR,或者你在调用之前已经置 s.state = Z_NULL。其他情况取决于是哪一种失败:每种失败在记录里留下什么,见注 2。
inflate、deflate、deflateParams
next_in是NULL,或指向avail_in个可读字节。next_out是NULL,或指向avail_out个可写字节(StreamBuffers)。- 输入范围与输出范围不重叠,并且都不在 zlib 为这个流分配的内存里(
StreamBuffers)。 - 两次调用之间,你只改
z_stream的next_in、avail_in、next_out和avail_out,以及不是 zlib 为这个流分配的内存(Rebuffer)。 - 如果挂接了
gz_header,下面“gzip 头部”各行成立(ActiveHeader)。
inflateSync
next_in是NULL且avail_in == 0,或者指向流自身内存之外的avail_in个可读字节(StreamArguments)。
字典:inflateSetDictionary、deflateSetDictionary、inflateGetDictionary、deflateGetDictionary
- 字典指针是
NULL,或者是流自身内存之外的一个缓冲区:两个Set调用要求它有dictLength个可读字节,两个Get调用要求它对返回的那些字节可写(CallerRange)。zlib.h说 32768 字节对Get调用总是够用。 - 对两个
Get调用,dictLength是NULL,或者指向你自己的一个uInt变量,它与字典缓冲区、z_stream和流自身的内存都不重叠。这一行没有 Lean 谓词陈述:翻译把长度作为值返回(见“结果单元”一行)。
读取 gzip 头部:inflateGetHeader,以及之后的 inflate
- 调用
inflateGetHeader时:head不是NULL。它的extra、name和comment各自是NULL,或者分别有extra_max、name_max、comm_max个可写字节。这个记录和这些缓冲区都在流自身的内存之外(HeaderMemory)。 - 记录一直挂接在这个流上,直到一次成功的
inflateReset或inflateReset2、一次找到同步点的inflateSync(它会重置这个流)、一次换掉它的inflateGetHeader调用,或者inflateEnd。挂接期间,每次inflate调用时记录及其缓冲区都同样有效,头部读完之后也是如此(ActiveHeader中的HeaderMemory)。 inflate还在读头部期间,extra缓冲区不与尚未读取的输入重叠,并且在EXTRA模式下,记录的extra_len不小于流还要读的长度(InflateHeaderProgress)。这是每次inflate调用时对记录的条件,不论这个字段是谁写的。对一个流调用inflate会写它所挂接记录中的extra_len。inflateCopy得到的副本挂接着同一个记录。这几行对副本上的每次inflate调用同样成立,直到副本以上述方式之一解除挂接。挂接在同一个头记录上的两个流在目标之外:目标描述的是一个流。
写出 gzip 头部:deflateSetHeader、deflatePrime,以及之后的 deflate、deflateParams、deflateBound、deflateBound_z
deflateSetHeader和deflatePrime在初始化或重置之后的第一次deflate调用之前调用,这是zlib.h的规定(DeflateNotStarted)。- 调用
deflateSetHeader时:head是NULL,或者是流自身内存之外的一个记录。它的extra是NULL,或者有extra_len个可读字节,并且在流自身的内存之外。它的name和comment各自是NULL或以 NUL 结尾的字符串(HeaderMemory)。 - 记录一直挂接在这个流上,直到
deflateReset、一次换掉它的deflateSetHeader调用,或者deflateEnd。 - 从
deflateSetHeader起,到deflate把头部写完为止,每次deflate、deflateParams、deflateBound和deflateBound_z调用时: - 记录及其缓冲区仍像
deflateSetHeader那一行说的那样有效(ActiveHeader中的HeaderMemory); z_stream的输入范围和输出范围、extra 字段、name 和 comment 两两不重叠,三个头部缓冲区在流自身的内存之外(DeflateHeaderApart);- 如果某次
deflate调用在 extra 字段、name 或 comment 写到一半时返回,你不缩短那个字段,也不把它改成NULL(DeflateHeaderProgress)。 - 头部写完之后,
deflate和deflateParams对这个记录不再有任何要求。zlib 不会告诉你头部是在哪一刻写完的。 deflateBound和deflateBound_z不论何时调用都会读取挂接着的记录,头部写完之后也一样。每次这样的调用时,记录及其缓冲区都像deflateSetHeader那一行说的那样有效(DeflateHeaderLive)。deflateCopy得到的副本挂接着同一个记录。这几行对副本上的调用同样成立。
inflateCopy、deflateCopy
source是下一条所说的那种流,dest指向一个不是source的z_stream(source ≠ dest)。- 副本与
source指向同一个gz_header记录。于是“gzip 头部”各行对两个流上的调用都成立。
其余流调用(inflateEnd、deflateEnd、inflateReset、inflateReset2、inflatePrime、inflateMark、deflateReset、deflateTune、deflatePending、deflateUsed)
- 对参数没有前提。流须是某次初始化或复制返回
Z_OK得到的,并且一直按这份清单使用。 - 不在 deflate 流上直接调用
deflateResetKeep。zlib.h把它列在未文档化的函数里,含有直接调用的历史在各个 deflate 目标之外。deflateReset先调用它、再清空哈希表,是被覆盖的(StreamOperation)。 deflatePending和deflateUsed:每个结果指针(pending、bits)是NULL,或者指向你自己的一个变量,它与z_stream和流自身的内存都不重叠。这一行没有 Lean 谓词陈述:翻译把结果作为值返回(见“结果单元”一行)。
NULL 流或不一致的流
- 以下情况会被拒绝:流指针是
NULL;z_stream的state是Z_NULL,例如End之后;对仍然存活的z_stream作的结构体复制。除四个初始化函数之外,每个有文档的流函数的安全目标都有拒绝这一子句。 - 被拒绝的调用返回一个错误值,并让内存保持原样;例外是源被拒绝的
inflateCopy和deflateCopy会把dest->state置为Z_NULL。返回值和精确的命题见注 2。 - 不被覆盖:设置了分配器、而
state里是过期指针或垃圾指针的z_stream。这包括原件已被结束之后还在使用的结构体复制。
compress、compress2、compress_z、compress2_z
source有sourceLen个可读字节,dest有*destLen个可写字节,两者不重叠(CompressArguments)。sourceLen == 0时source可以是NULL,*destLen == 0时dest可以是NULL。- C 以
Z_STREAM_ERROR拒绝的调用,不论其他参数如何都被覆盖:source为NULL而sourceLen不为零,dest为NULL而*destLen不为零,以及_z形式的destLen为NULL(compressRejected)。 compress和compress2的destLen不能是NULL(CompressorSafety)。destLen指向你自己的一个变量,它与source和dest都不重叠。这一行没有 Lean 谓词陈述:翻译把*destLen当作值传入(见“整缓冲区压缩”一行)。
uncompress、uncompress2、uncompress_z、uncompress2_z
source是NULL,或在源长度范围内可读;dest是NULL,或有*destLen个可写字节。destLen,以及带2的两个函数的sourceLen,各自是NULL,或指向八个可读可写的字节(LengthCell)。source、dest和各个长度变量两两不重叠(UtilitySeparation)。uncompress和uncompress2的长度指针不能是NULL。
校验和与查询
adler32、adler32_z:只有len == 0时buf才可以是NULL;否则它有len个可读字节(AdlerBufferBytes)。crc32、crc32_z:buf是NULL,或有len个可读字节。crc32_combine_op:op是crc32_combine_gen或crc32_combine_gen64返回的值,这是zlib.h的规定。- 各个组合函数、
compressBound、compressBound_z、zlibVersion和zlibCompileFlags没有前提。
回调解码器:inflateBackInit、inflateBack、inflateBackEnd
- 调用
inflateBackInit时:zalloc和zfree是Z_NULL;windowBits在 8 到 15 之间;window不是NULL,有2^windowBits个可写字节,并且是一个字节数组或其中一段,而不是结构体里的字节字段(BackInitArguments、BackSafeReachable.init)。z_stream的state字段可以取任意值。 - 每次调用
inflateBack时,strm->next_in是NULL,或者指向avail_in个可读字节;这些字节不与窗口重叠,并且是一个字节数组或其中一段(BackFirstChunk)。 - 你的
in和out函数会返回,只写你自己的内存,不写窗口、z_stream和 zlib 的状态。in交出的每个片段都可读,是一个字节数组或其中一段,不与窗口重叠,并且在下一次in调用之前保持可读(CallbackProtocol、BackPlatform)。 - 一次
inflateBack调用总共得到的输入少于 2^48 字节,第一个片段也算在内(inputBound)。 - 两次
inflateBack调用之间,你不写窗口,并且只改z_stream的四个缓冲区字段(BackSafeReachable.caller)。如果window指向某个数组的第一个字节,这条规则管的是整个数组,包括2^windowBits字节之后的部分:两次调用之间,这个数组的任何字节你都不写。
gzip 文件:各个 gz* 函数
path和mode是NULL或以 NUL 结尾的字符串(GzOpenSafe、GzDopenSafe)。- 传给
gzread、gzfread或gzgets的缓冲区,在调用指明的长度内可写;传给gzwrite或gzfwrite的缓冲区,在调用指明的长度内可读。gzerror的errnum指针是NULL,或者指向你自己的一个int(GzRange)。 - 这些缓冲区、
gzerror的那个int、gzputs的参数,以及gzprintf和gzvprintf的格式串和每个指针参数,都是你自己的内存,不是 zlib 为这个文件分配的内存。尤其不要把gzerror返回的字符串再传回同一个文件上的调用(GzRange、GzArguments)。 gzputs的参数是以 NUL 结尾的字符串,不能是NULL(CString)。gzprintf或gzvprintf的调用是一次对其格式串和参数在 C 中有定义的vsnprintf调用,格式串中没有%n。库不检查这一点,也没有前提陈述它。模型不读取格式串中的转换,所以发现不了与参数不匹配的格式串:对这样的调用,定理对模型成立,对 C 什么也没说。文件以写方式打开且不处于错误状态时,格式串是以 NUL 结尾的字符串,每个指针参数都指向未被释放的内存(GzArguments)。- 两次调用之间,你不写 zlib 为这个文件分配的内存(
GzCallerFrame)。 - 关闭文件的那次调用之后,你不再使用这个文件:
gzclose,或者在相应模式的文件上调用的gzclose_r或gzclose_w。文件已被释放,C 中也是如此。 gzread、gzfread、gzgetc、gzgetc_、gzgets和gzungetc的终止,是在文件描述符还能交付的字节少于 2^61 时证明的(ReadsFinite)。没有这个条件,证明仍然说明这些调用不会引起未定义行为。NULL文件会被每个函数拒绝,什么也不改变(Goal.gz_refusal)。对NULL使用gzgetc()宏在 C 中是未定义行为,不被覆盖。
构建与平台
下面每张表的各列依次是:前提及陈述它的 Lean 谓词;它要求什么;陈述它的目标;它的理由,以及什么不被覆盖。
| 前提 | 要求什么 | 目标 | 理由,以及什么不被覆盖 |
|---|---|---|---|
| 初始配置 | 默认 x86_64 Linux、LP64、静态构建和默认分配器:zalloc 与 zfree 各自是 NULL 或默认函数(DefaultOrNull、DefAlloc) |
每个目标 | 证明针对的就是这个构建和这个分配器。不被覆盖:自定义分配器,以及任何其他构建配置(进度)。默认分配器失败是被覆盖的:各目标对每一种分配结果都成立。 |
平台字节对象范围(ByteObjectsFit) |
每个字节对象小于 2^63 字节,包括调用者的、静态的和内嵌的存储 |
见下面的列表 | LP64 下单个对象大小的上限 PTRDIFF_MAX(平台)。它既不限制内存总量,也不限制流的长度。 |
各目标在以下位置陈述 ByteObjectsFit:
- 每次流调用所在的堆(
StreamCallDomain,以及StreamSequenceSafety的第 2 个子句); - 对 inflate 流,还包括历史中此前的每个堆,即每次调用之前和每次调用者修改之后(
StreamReachable.step、.rebuffer);deflate 的历史只在目标所陈述的那次调用上带有它; compress*与uncompress*的目标(CompressorSafety、UncompressCountedSafe、UncompressSingleSafe);- 每次 gz 打开所在的堆,以及 gz 历史中每次调用者修改之后的堆(
GzHistory、GzOpenSafe、GzDopenSafe),这就覆盖了调用者的路径串和模式串; - 对回调解码器,是每次
inflateBack调用所在的堆和每个回调步骤之后的堆(BackSafeReachable.step、BackPlatform)。
初始化、校验和与拒绝目标不陈述它。End 目标不对调用时的堆陈述它;inflate 的历史按上面第二条带有它。有一个具体的堆满足它(inflate_default_witness_platform)。
目标对模型中的堆提出的条件(Fresh、Uniq、LibraryGlobals、CrcGlobals)、循环燃料、CRC 地址模型以及指针加零与 NULL - NULL 的规则,都不是调用者的义务。它们在模型的限制中。
流调用:inflate 与 deflate
流函数的安全目标在每个可达的流(StreamReachable)上成立,只要参数满足 StreamArguments。
| 前提 | 要求什么 | 目标 | 理由,以及什么不被覆盖 |
|---|---|---|---|
流的初始化(InitArguments) |
strm 是 NULL,或者是一个可读的记录,其 zalloc 与 zfree 各自是 NULL 或默认函数(DefaultOrNull)。version 是 NULL,或其第一个字节可读。堆是良构的(模型的限制)。记录的其他字段(包括 state)、version 的第一个字节和 stream_size 都是任意的。Goal.inflateBackInit__safety 多一条要求,zlib.h 同样有这条要求:窗口非 NULL 且 windowBits 为 8 到 15 时,窗口有 2^windowBits 个可写字节。 |
Goal.inflateInit2__safety、Goal.inflateInit__safety、Goal.deflateInit2__safety、Goal.deflateInit__safety、Goal.inflateBackInit__safety |
只有 DefaultOrNull 比 zlib.h 更窄。版本不对、stream_size 不对和 NULL 流都被覆盖:调用返回错误码,并且不留下任何块(InitResultSafe)。见注 1。 |
历史的第一次调用(StreamReachable.inflateInit、.deflateInit) |
一段历史从一次返回 Z_OK 的初始化调用开始:记录可读并满足 DefaultOrNull,version 的第一个字节是 '1',stream_size = 112。 |
两个序列目标,以及通过 StreamReachable 涉及的每个单函数流目标 |
除 DefaultOrNull 外,这些就是 C 返回 Z_OK 的条件。对 state 没有任何子句。 |
流缓冲区(StreamBuffers) |
输入范围(next_in、avail_in)与输出范围(next_out、avail_out)互相分离,且都不在流拥有的存储内。每个范围是 NULL 或可读,输出范围还须可写。 |
Goal.inflate_safety、Goal.deflate_safety、Goal.deflateParams_safety,以及两个序列目标中的这些调用(StreamArguments)。功能目标 Goal.inflate 与 Goal.deflate 也假设它。 |
zlib.h 描述的是调用者让各缓冲区互不重叠时的调用。不被覆盖:输入与输出重叠,以及缓冲区位于流自身的状态之内。 |
调用之间调用者的修改(Rebuffer) |
在一段历史的两次调用之间,调用者只改变流记录的 next_in、avail_in、next_out 和 avail_out,以及流不拥有的内存。 |
两个序列目标;通过 StreamReachable 涉及的每个单函数流目标 |
这是 zlib.h 的规则:应用程序更新缓冲区字段,其他字段都 must not be updated by the application(应用程序不得更新)。不被覆盖:调用者写了记录的其他字段,或写了流拥有的块的历史。 |
其他流参数(StreamArguments) |
inflateSync:输入范围是 NULL 且 avail_in = 0,或者可读且在流的存储之外。deflatePrime:还没有任何 deflate 调用启动过这个流(DeflateNotStarted);deflateSetHeader 有同样的顺序规则(“头部参数”一行)。头部调用和字典调用各有自己的行。其余流调用没有参数前提。 |
该函数的安全目标,以及序列目标中的同一种调用 | 次序规则是 zlib.h 的("before the first deflate() call",即在第一次 deflate() 调用之前)。在一次 deflate 调用之后调用 deflatePrime,是真实 C 的未定义行为(已用真实的 C 在 sanitizer 下复现)。 |
字典缓冲区(CallerRange) |
字典参数是 NULL,或是一个可读范围(两个 Get 调用还要求可写),其中没有字节落在流拥有的块内。inflateGetDictionary 的范围有 whave 字节;deflateGetDictionary 的范围有 min(w_size, strstart + lookahead) 字节。 |
Goal.inflateGetDictionary_safety、Goal.deflateGetDictionary_safety、Goal.inflateSetDictionary_safety、Goal.deflateSetDictionary_safety,以及序列目标中的这些调用 |
调用者的字典没有理由位于流的存储之内。不被覆盖:位于流的窗口或其他存储之内的字典缓冲区。 |
结果单元(dictLength、pending、bits) |
没有前提,也无法陈述前提。翻译把这些标量输出参数当作值传递,而不是内存。inflateGetDictionary 接收 *dictLength 的值,指针为 NULL 时是 none(Option UInt32)。deflateGetDictionary、deflatePending 和 deflateUsed 只接收每个指针是否为 NULL(Bool)。每个函数都把 C 写入的值作为另一个结果返回。 |
Goal.inflateGetDictionary_safety、Goal.deflateGetDictionary_safety、Goal.deflatePending_safety、Goal.deflateUsed_safety,以及序列目标中的这些调用 |
这些目标对结果单元的内存什么都没说;C 是用普通赋值经由指针写入它的(*dictLength = ...)。被覆盖:结果单元是调用者的一个普通变量,并且与字典缓冲区、流记录和流拥有的存储都分开的调用。不被覆盖:其他任何调用。 |
头部参数(HeaderMemory、DeflateNotStarted、DeflateHeaderLive) |
inflateGetHeader:头记录不是 NULL,不归流拥有,其 extra、name 和 comment 缓冲区各自是 NULL,或分别有 extra_max、name_max、comm_max 个可写字节。deflateSetHeader:头是 NULL,或是一个流不拥有的记录,其非 NULL 的 extra 有 extra_len 个可读字节,且没有字节落在流拥有的块内,非 NULL 的 name 和 comment 是短于 2^64 字节、以 NUL 结尾的字符串;并且还没有任何 deflate 调用启动过这个流。这次调用对 name 和 comment 没有关于归属的子句;那一子句在“deflate 的 gzip 头区域”一行。deflateBound、deflateBound_z:ActiveHeader(下面四行),并且已设置的 gzip 头在任何时候都存活,而不只是在写出期间。 |
Goal.inflateGetHeader_safety、Goal.deflateSetHeader_safety、Goal.deflateBound_safety、Goal.deflateBound_z_safety,以及序列目标中的这些调用 |
inflateGetHeader 经由这个指针写入(head->done = 0),所以 NULL 头部不被覆盖。deflateSetHeader 的次序规则是 zlib.h 的;在头部正被写出时设置的 NULL 头部,会被真实的 C 解引用(已用真实的 C 在 sanitizer 下复现)。 |
挂接的 gzip 头保持存活(ActiveHeader 中的 HeaderMemory) |
每次 inflate 调用时,在每种模式下,包括头已读完(done 已置位)之后:交给 inflateGetHeader 的记录仍是一个流不拥有的存活记录,其非 NULL 的 extra、name 和 comment 仍分别有 extra_max、name_max、comm_max 个可写字节,并位于流的存储之外。对 deflate 流,状态为 GZIP_STATE .. HCRC_STATE(DeflateHeaderWriting)期间的每次 deflate、deflateParams、deflateBound 和 deflateBound_z 调用时:交给 deflateSetHeader 的记录存活且不归流拥有,其非 NULL 的 extra 有 extra_len 个可读字节,并位于流的存储之外,非 NULL 的 name 和 comment 是以 NUL 结尾的字符串。GZIP_STATE 是 gzip 流从初始化或重置起、在任何 deflate 调用之前就有的状态,所以这个时段从 deflateSetHeader 开始。头写完之后调用者可以释放它,但 deflateBound 和 deflateBound_z 除外(见上一行)。inflateCopy 或 deflateCopy 得到的流与它的源有同一个头指针,所以这一行对副本上的调用同样成立。 |
Goal.inflate_safety、Goal.deflate_safety、Goal.deflateParams_safety、Goal.deflateBound_safety、Goal.deflateBound_z_safety,以及两个序列目标中的这些调用 |
库保存调用者的指针,并在之后的调用中使用它。对 inflate,这条前提要求的比 C 用到的多:inflate.c 只在头部模式(HEAD .. HCRC)中读写 state->head。不被覆盖:调用者释放了记录或其缓冲区之后的 inflate 调用,done 置位之后也一样。对 deflate,这条前提要求 extra_len 个可读字节;C 读取的是 extra_len mod 2^16 个。 |
inflate 的 gzip extra 字段(InflateHeaderProgress) |
inflate 把 gzip 头(HEAD .. HCRC)读入挂接的 gz_header 时,其 extra 缓冲区(extra_max 字节)与尚未读取的输入分离;在 EXTRA 模式中,记录的 extra_len 不小于 state->length。 |
Goal.inflate_safety,以及 Goal.inflate_sequence_safety 中的每次 inflate 调用;功能目标 Goal.inflate 与 Goal.inflate_sequence 也是如此 |
被排除的每种情形都是真实 C 在 EXTRA 的 zmemcpy 中的未定义行为(已用真实的 C 在 sanitizer 下复现):重叠的复制,或者 extra_len 在 extra 字段中途被调低之后越过 extra_max 的写入。这条前提是每次调用时对记录的条件,不论 extra_len 是谁写的:调用者,或者对挂接在同一记录上的另一个流调用的 inflate,因为 inflate 会写它所挂接记录中的 extra_len。不被覆盖:挂接在同一个头记录上的两个流,例如 inflateCopy 之后。zlib.h 对这些都没有说明。 |
deflate 的 gzip 头区域(DeflateHeaderApart) |
状态为 GZIP_STATE .. HCRC_STATE 且挂接着 gz_header 期间,每次 deflate、deflateParams、deflateBound 和 deflateBound_z 调用时:输入范围、输出范围、extra 字段(extra_len mod 2^16 字节)、name 与 comment(各含其 NUL)是两两分离的字节范围,可以位于同一个块中;extra 字段、name 与 comment 位于流拥有的存储之外。输入范围和输出范围就是那次调用时 z_stream 各字段所指的范围;对并不使用它们的 deflateBound 和 deflateBound_z 也是如此。 |
Goal.deflate_safety、Goal.deflateParams_safety、Goal.deflateBound_safety、Goal.deflateBound_z_safety,以及 Goal.deflate_sequence_safety 中的每次这类调用;功能目标 Goal.deflate 与 Goal.deflate_sequence 也是如此 |
这些区域没有理由重叠。不被覆盖:同一个字符串既用作 name 又用作 comment(同一地址,例如两个被合并的字符串字面量),因为两个范围(各含其 NUL)重合。name 位于输出范围或 pending_buf 之内,是真实 C 的未定义行为:一次刷新或一个头部字节会覆盖它的 NUL,name 循环随后读到缓冲区之外(已用真实的 C 在 sanitizer 下复现)。zlib.h 对这些布局没有说明。 |
deflate 的 gzip 头进度(DeflateHeaderProgress) |
在上一行所说的每次调用时,如果此前某次 deflate 调用在挂接的 gz_header 的某个字段写到一半时返回,调用者保留了已经写出的部分:字段仍覆盖已写出的部分(gzindex),并且在 EXTRA_STATE、NAME_STATE 或 COMMENT_STATE 中,该字段没有中途被置为 NULL(它为 NULL 时 gzindex = 0)。 |
与上一行相同的目标 | 被排除的修改是真实 C 的未定义行为(已用真实的 C 在 sanitizer 下复现):被缩短的字段会被读到末尾之外;中途被改成 NULL 的字段会被跳过而不重置 gzindex,下一个字符串就从 gzindex 处读起,越过它的末尾。zlib.h 要求在第一次 deflate 调用之前提供头部,对头部写出期间的改动没有说明。 |
被拒绝的流(RefusedInflate、RefusedDeflate) |
被拒绝的流是 NULL,或者是一个可读的记录:其状态为 NULL,或其 zalloc 或 zfree 为 NULL,或其状态是一个被检查拒绝的存活状态记录(回指指针、mode 或 status 字段有误)。 |
除四个初始化函数之外每个有文档的流函数的安全目标的拒绝子句,以及 Goal.inflateCopy_safety 和 Goal.deflateCopy_safety 的拒绝子句;Goal.inflate_refusal、Goal.deflate_refusal |
其中包括:End 之后的记录、失败的复制的目的记录、对存活记录的结构体复制,以及注 2所说的初始化失败之后的记录。同一条注列出不被覆盖的三类记录。 |
| 复制的目的流 | 在“从可达的源复制”这个子句里:目的流是一个可读的流记录,并且不是源记录(source ≠ dest),源使用默认分配器(DefAlloc)。拒绝子句只要求目的记录可读,dest 为 NULL 时则没有要求;它们没有 source ≠ dest 这条前提。 |
Goal.inflateCopy_safety、Goal.deflateCopy_safety,以及功能目标 Goal.inflateCopy、Goal.deflateCopy |
dest == source 且源可达时,C 的 zmemcpy(dest, source, sizeof(z_stream)) 把一个对象复制到它自身上,这是未定义行为。源被拒绝时,C 在复制之前就返回,所以那里 dest == source 是被覆盖的。因模型无法表达而不被覆盖:与源记录、某个缓冲区或某个状态记录部分重叠的目的记录(模型的限制,地址与布局模型)。 |
直接调用 deflateResetKeep |
deflate 的调用历史(StreamOperation .deflate)中没有对 deflateResetKeep 的直接调用;deflateReset 和 deflateInit2_ 仍在其中。 |
Goal.deflate_sequence_safety,以及通过 StreamReachable 涉及的各个单函数 deflate 目标 |
zlib.h 把 deflateResetKeep 声明在 undocumented functions (not part of the zlib API)(未文档化函数,不属于 zlib API)之下。不被覆盖:含有直接调用的历史。 |
注 1:初始化与未设置的字段
在 C 中,inflateInit 的调用者没有设置的字段,其值是不确定的。模型里没有这样的值。未设置的整数字段取一个任意的值;未设置的指针字段取模型能够表达的某个值:NULL,或对某个模型对象的引用。四个初始化目标和 Goal.inflateBackInit__safety 对每一个这样的值都成立,因为 InitArguments 只约束 zalloc 和 zfree。C 的初始化函数给 strm->state 赋值,而不读取它。模型里没有“未初始化指针”这种值,这是模型的一处限制(可信基础第 2 项)。
初始化的三个非空性目标(Goal.inflate_initialisation_domain、Goal.deflate_initialisation_domain、Goal.inflate_back_initialisation_domain)是针对调用之前 state 为 NULL 的记录陈述的(InitDomain)。它们说:在每个这样的堆上,只要没有分配失败,初始化就返回 Z_OK。它们不是任何安全目标的前提。
注 2:被拒绝的流
拒绝在哪里陈述。 除四个初始化函数之外,每个有文档的 inflate 和 deflate 流函数的安全目标都有两个子句:对被拒绝的流(RefusedInflate 或 RefusedDeflate)的拒绝,以及对可达流的调用。Goal.inflateCopy_safety 和 Goal.deflateCopy_safety 在针对 NULL 参数的子句之外,还有一个针对被拒绝的源的子句。Goal.inflate_refusal 和 Goal.deflate_refusal 各用一个目标再次陈述以下函数的拒绝:inflate、inflateEnd、inflateReset、inflateReset2、inflateGetDictionary、inflateSetDictionary 和 inflateCopy,以及 deflate、deflateSetDictionary、deflateParams、deflateGetDictionary 和 deflateCopy。
被拒绝的调用返回什么。 返回 Z_STREAM_ERROR,有两个例外,都与 C 一致。inflateMark 返回 -65536。deflateBound 和 deflateBound_z 返回它们在 sourceLen 相同时对 NULL 流给出的上界,这不是错误值。
被拒绝的调用改变了什么。 除 inflate、inflateSync 和两个复制函数外,调用之后的堆就是调用之前的堆。源被拒绝的复制把 NULL 写入目的记录的 state 字段,与 C 相同(dest->state = Z_NULL),此外什么也不改;这个子句要求目的记录可读、源指针不是 NULL。对 inflate 和 inflateSync,目标在满足 Fresh 的堆上陈述:调用不写原先存活的任何块,每个存活的块都保持原样,没有块被创建或释放。这不是堆相等:这两个翻译各自会分配并释放一个四字节的局部数组,所以模型的块计数器可能增大。
初始化失败之后的记录。 它在 state 为 NULL 时,或者在 zalloc 或 zfree 为 NULL 时被拒绝。下表说明每种失败在记录里留下什么。
| 失败 | 调用之后的 state |
调用之后的 zalloc、zfree |
|---|---|---|
Z_VERSION_ERROR;inflateBackInit_ 因窗口为 NULL 或 windowBits 不合法而返回的 Z_STREAM_ERROR |
与调用之前相同 | 与调用之前相同。它们原先按检查清单的要求是 NULL 时,不论 state 里是什么,记录都被拒绝 |
状态记录分配不出来时的 Z_MEM_ERROR |
与调用之前相同 | 已置为默认函数 |
deflateInit2_ 因参数有误返回的 Z_STREAM_ERROR |
与调用之前相同 | 已置为默认函数 |
inflateInit2_ 因 windowBits 有误返回的 Z_STREAM_ERROR |
NULL |
已置为默认函数 |
deflateInit2_ 的四个缓冲区之一分配不出来时的 Z_MEM_ERROR |
NULL |
已置为默认函数 |
在第 1 至 3 行中,state 里是调用者留下的值。zalloc 和 zfree 已设置时,这个值是 NULL 则记录被拒绝;它是过时指针或垃圾指针时,记录属于下面三类之一。
不被覆盖。 在 zalloc 和 zfree 已设置的情况下,有三类记录在拒绝的定义域之外。在 C 中,状态检查对其中每一类都会经由这个指针读取,这是未定义行为。
- 状态字段里是垃圾地址,例如从未初始化的自动变量
z_stream。模型无法表达它:这个字段是NULL、一个 inflate 状态编号或一个 deflate 状态编号,而新分配内存中的指针是NULL(模型的限制,“未初始化指针变成 NULL”一行)。 - 悬空的状态:字段指向一个已不存活的状态,例如原件已被结束之后还在使用的结构体复制。谓词排除它。
- 类型不对的状态:把 deflate 状态交给 inflate 函数,或者反过来。谓词排除它。
只关于模型的情形。 inflateBackInit_ 建立的状态,其 strm 和 mode 字段没有写过。在 C 里,inflate 函数的状态检查读到的是一个不确定的指针;模型读到的是 NULL,所以这个记录被拒绝(RefusedInflate)。对这样的流,拒绝目标只是关于模型的陈述(模型的限制,“未初始化指针变成 NULL”一行)。zlib.h 用 inflateBackEnd 结束这样的流。
整缓冲区实用函数与校验和
| 前提 | 要求什么 | 目标 | 理由,以及什么不被覆盖 |
|---|---|---|---|
整缓冲区压缩(CompressArguments) |
源与目的缓冲区不重叠:Separate source n dest c。源可读,目的缓冲区在其容量范围内可写,除非这次调用是 C 会拒绝的调用(compressRejected)。compress 与 compress2 的长度单元不能是 NULL;只有 _z 形式允许 NULL 单元。 |
Goal.compress_safety、Goal.compress2_safety 及其 _z 形式 |
源与目的没有理由重叠。长度单元 *destLen 在翻译中是一个标量值(Option UInt64),不是内存,所以这些目标对它的内存什么都没说。不被覆盖:源与目的重叠,以及长度单元不是一个与两者都分开的可写变量。 |
计数解压(UtilitySeparation、UncompressCountedSafe、UncompressSingleSafe) |
源、目的缓冲区、目的长度单元和源长度单元两两分离。uncompress 与 uncompress_z 需要源与目的缓冲区分离、长度单元与数据分离。长度单元是八个可读可写的字节(LengthCell);uncompress 与 uncompress2 的单元不能是 NULL。 |
Goal.uncompress_safe、Goal.uncompress2_safe 及其 _z 形式 |
这些区域没有理由重叠。这里的单元 *destLen 和 *sourceLen 在翻译中是内存,所以分离是一条写明的前提。不被覆盖:长度单元与数据缓冲区或另一个单元别名。 |
Adler 初始化查询(AdlerBufferBytes) |
只有长度为零时 buf 才可以是 NULL;非 NULL 的可读缓冲区保留完整的长度范围。 |
Goal.adler32_safety、Goal.adler32_z_safety,以及功能目标 Goal.adler32、Goal.adler32_z |
比 zlib 1.4 的 zlib.h 更窄:后者允许 buf 为 NULL,对 len 不加条件。NULL 且 len = 1 时,C 在检查 NULL 之前就读 buf[0]。不被覆盖:buf 为 NULL 而 len 非零。CRC 的目标仍用 BufferBytes,它容许 NULL 配任意长度。 |
| CRC 组合算子 | 算子是 crc32_combine_gen 或 crc32_combine_gen64 返回的值。 |
Goal.crc32_combine_op_safety |
这是 zlib.h 为 crc32_combine_op 规定的定义域。不被覆盖:任意的 op 值。 |
回调解码器
Goal.inflate_back_sequence_safety 在 BackSafeReachable 的历史上成立。Goal.inflateBack_safety 和 Goal.inflateBackEnd_safety 中关于历史的子句也是如此,它们重复了序列目标的子句:下面每一行只要写了序列目标,对这两个目标同样成立。Goal.inflateBackInit__safety 没有这些前提;它的前提在“流的初始化”一行。
| 前提 | 要求什么 | 目标 | 理由,以及什么不被覆盖 |
|---|---|---|---|
回调解码器的初始化(BackSafeReachable.init 中的 BackInitArguments) |
流记录可读;zalloc 与 zfree 各自是 NULL 或默认函数;version 指向一个可读的字节 '1';stream_size = 112;调用返回了 Z_OK。记录的其他字段(包括 state)可以取任意值。 |
Goal.inflate_back_sequence_safety |
除默认分配器外,这些就是 C 返回 Z_OK 的条件。失败的初始化调用不开始任何历史;它的安全性是 Goal.inflateBackInit__safety。 |
回调(CallbackProtocol) |
调用者为它的 in 和 out 函数提供一个协议;各子句见下面的列表。 |
Goal.inflate_back_sequence_safety |
回调是调用者的代码,所以它们做什么是一条前提。描述符对象可以与窗口共用同一次分配,只要在切片之外。 |
调用之间调用者的修改(BackSafeReachable.caller) |
两次调用之间,调用者的修改是一次 Rebuffer(“调用之间调用者的修改”一行),并且保持窗口切片,以及每个仍存活的块的只读标志。 |
Goal.inflate_back_sequence_safety |
窗口就是解码器的历史。这比 zlib.h 更窄:zlib.h 没有禁止在两次调用之间写窗口。窗口指针位于其所在块的偏移 0 时,在模型中流拥有这个块(InflateOwned),Rebuffer 于是在两次调用之间保持整个块,而不只是切片。C 不读取此前的窗口字节(inflateBack 在每次调用开始时置 state->whave = 0),这一点尚未由证明确认。C 代码无法改变只读标志,所以那个子句不排除任何调用者。 |
| 回调输入总量 | protocol.inputBound < 2^48:一次 inflateBack 调用总共得到的输入少于 2^48 字节。这个总量包括第一个片段(调用时的 next_in、avail_in)和各次 in 调用交出的每个片段。 |
Goal.inflate_back_sequence_safety |
运行时把每个循环限制在 2^64 次迭代以内(模型的限制),而解码循环的每一轮至少读一位,所以得到更多输入的调用可能在 C 还会继续的地方耗尽燃料。zlib.h 没有这样的限制。超过这个上界时,对这次调用什么也不得出:不得出它会返回,不得出没有未定义行为,也不得出它的框架。 |
| 回调解码器窗口 | 8 ≤ windowBits ≤ 15,窗口不是 NULL 并且有 2^windowBits 个可写字节,这是 zlib.h 的要求;另外还要求:窗口是某个堆字节块的切片。 |
Goal.inflate_back_sequence_safety,通过 BackSafeReachable.init |
模型中另外唯一可写的字节视图是 deflate 状态内的 depth 数组,它是库的存储,调用者无法指名。不被覆盖:位于那里的窗口。 |
| 回调解码器输入片段 | 每个输入片段都位于某个堆字节块中:调用者给出的第一个片段(BackFirstChunk),以及 in 交出的每个片段(BackPlatform)。 |
Goal.inflate_back_sequence_safety |
inflate_fast 在这个片段上运行,而它的证明针对堆上的字节块(模型的限制,“快速解码器辅助函数”)。不被覆盖:位于模型其他存储中的片段,例如结构体的字段或静态数据;C 能处理任何可读存储中的片段。 |
CallbackProtocol 的各个子句:
in和out各自都会返回而不出故障,并且只改变调用者自己的块;这些块不包括状态和流记录。- 存放回调输入的块(包括第一个片段)属于调用者自己的块,即使回调只读它们也是如此。对这些块,结论给出的保证是不变量子句,而不是框架子句(
CallbackFrame)。输入与窗口共用一个块时,这个块属于调用者自己的块;框架就不再把库对它的写入限制在窗口这一段之内,窗口段之外的字节由不变量描述。 - 关于一次
in或out调用的子句只在这样的堆上才被要求:流是这个窗口上的一个有效回调解码器(CallbackEntry)。库交给回调的只有这样的堆。没有这个限制,就不可能存在任何协议(回调)。 - 两者都保持窗口切片中的字节。
in交出的片段可读,并且与窗口、状态和流记录分离。out保持当前的输入片段可读。- 总输入有一个有限的上界(
inputBound)。 - 每个回调都让堆保持良构(
Fresh、Uniq),它新建的每个块都属于调用者自己(ExternalFrame)。 - 协议带有一个不变量,说的是堆以及“已供给和已交付字节”的日志。每个回调都保持它。这个不变量只能依赖调用者自己的块和堆的分配器字段,不能依赖窗口切片中的字节(
CallbackProtocol.local_)。
关于同一次调用还有两条前提,它们是目标第三个子句的前提,不是 CallbackProtocol 的子句:第一个片段(next_in、avail_in)可读,并且与窗口分离;在调用 inflateBack 时的堆上,不变量成立。Goal.inflateBack_call_domain 表明这些前提和一个协议在一次具体的调用上同时成立。
Gzip 文件接口
Goal.gz_sequence_safety 在一个句柄的每段历史(GzHistory)上、对每个文件系统世界成立。每个 gz 函数的安全目标(Goal.<function>_safety)把它的一个子句限制到这个函数上,前提相同:下面写了 Goal.gz_sequence_safety 的行,对该行所说的那些函数的目标同样成立。这些目标说的是打过补丁的源码(补丁 0002 至 0005)。gz 世界是堆之外的可信语义:外部 I/O 模型描述它,可信基础说明对它作了哪些假设。
| 前提 | 要求什么 | 目标 | 理由,以及什么不被覆盖 |
|---|---|---|---|
Gz 打开参数(GzOpenSafe、GzDopenSafe、GzHistory.open) |
path 与 mode 各自是 NULL,或是短于 2^64 字节、以 NUL 结尾的字符串;堆是良构的,其字节对象都不超限;世界是一个良构的文件系统(FileSystem)。 |
Goal.gz_sequence_safety |
C 把每个字符串一直读到它的 NUL。被覆盖:每个描述符、每种模式文本和每个世界,包括每一种失败。不被覆盖:在自身对象之内没有以 NUL 结尾的路径或模式。 |
Gz 调用者缓冲区(GzArguments 中的 GzRange) |
gzread、gzfread、gzwrite、gzfwrite、gzputs、gzgets 与 gzerror 的调用者缓冲区可读(读取调用的缓冲区和 gzerror 的 errnum 还须可写),并且与句柄拥有的块分开(GzOwned)。gzputs 的参数是以 NUL 结尾的字符串(CString),范围包含它的 NUL:没有 NUL 的可读字节,以及 NULL,都在范围之外。 |
Goal.gz_sequence_safety |
库在调用期间会释放并改写它自己的块(见下)。不被覆盖:位于句柄的块之内的缓冲区。 |
Gz printf 字符串(GzArguments) |
gzprintf 与 gzvprintf 的格式串以及每个指针参数都与句柄拥有的块分开(GzOwned)。 |
Goal.gz_sequence_safety |
理由与上一行相同。 |
Gz printf 调用(调用者的义务;GzArguments) |
vsnprintf 的调用对格式串和参数在 C 中有定义,且格式串中没有 %n:没有前提陈述这一点,由调用者保证,和每次 printf 调用一样(可信基础)。文件以写方式打开且不处于错误状态时,GzArguments 要求格式串是以 NUL 结尾的字符串,每个指针参数都指向未被释放的块。随后 gz_init、gz_zero 或 gz_vacate 失败时它也这样要求,尽管 C 在调用 vsnprintf 之前就返回了。 |
Goal.gz_sequence_safety |
vsnprintf 是按契约建模的外部调用,所以参数都是整数或字符串的每种有效格式都被覆盖。模型的参数类型(VaArg)没有浮点或 void * 的情形:浮点转换和 %p 不被覆盖。模型不读取格式串中的转换,所以 C 没有定义的调用在模型中不是故障,目标对这样的调用在 C 中的行为什么也没说。不被覆盖:%n,它会写调用者的内存,而结论的框架不描述这种写入;与参数不匹配的格式串;以及在 vsnprintf 之前返回、格式串又不是字符串的调用。 |
Gz 调用者步骤与世界步骤(GzCallerFrame、GzWorldStep) |
两次调用之间,调用者可以改变句柄不拥有的任何块,也可以释放自己的缓冲区;堆保持良构,其字节对象都不超限。世界可以变成任何良构的文件系统:别的参与者可以关闭或重用句柄的描述符。 | Goal.gz_sequence_safety |
句柄的块属于库。不被覆盖:调用者写了句柄拥有的块的历史。世界步骤容许的比真实系统更多。 |
Gz 读取调用的终止(ReadsFinite) |
对 gzread、gzfread、gzgetc、gzgetc_、gzgets 和 gzungetc:句柄的描述符有一个小于 2^61 字节的有限读取预算(fs.readBudget fd = some b 且 b < 2^61),即该描述符还能交付的总字节数。这条前提还说描述符编号不为负(HasBudget)。 |
Goal.gz_sequence_safety 中关于终止的那一半,且只针对这六个调用 |
在无穷无尽的来源上,C 有两个循环不会结束(见下)。这条前提不排除任何故障:无故障的那一半和后置条件对每个世界都成立,不需要预算。gzdirect、写入一侧和 gzseek 不需要它。 |
| Gz 操作系统事实 | 非空的 write 从不返回 0;close 即使失败也会释放描述符。 |
Goal.gz_sequence_safety,通过世界模型 |
这些是关于系统的假设,被信任,没有检查。两条都是 Linux 的行为。对 lseek 不加限制:成功的调用可以返回任意 64 位值。第一条为 gz_comp 的写循环定界。尚未由证明确认:按对 C 的解读,一个永远返回 0 的 write 会让 gz_comp 永远循环。模型中没有带这种 write 的世界,所以没有定理陈述这一点。 |
strerror 的模型是模型的限制,不是调用者的义务:见模型的限制,“外部错误字符串”一行。
为什么排除句柄自己的字符串
gzerror 返回的字符串就是 state->msg。库每次清除或替换错误时,都在 gz_error 里释放它,而许多入口函数在读取自己的参数之前就会这样做。所以把这个字符串再传回同一个句柄上的调用,在 C 中可能是释放后使用。在上一次写入停滞的写入端上,gzprintf(f, "%s", gzerror(f, &e)) 先释放这条消息,再在 vsnprintf 中读它:AddressSanitizer 报告堆释放后使用。zlib.h 只提醒说,之后的 gzerror 调用可能使这个字符串失效。这条前提对每个接受调用者内存的调用都排除句柄自己的块,不论那个调用是否释放这条消息。
为什么需要读取预算
C 里有两个循环在无穷无尽的来源上不会结束:来源永远交付只解码出空内容的数据(空的 gzip 成员)时,gz_fetch 会一直循环;待跳过的量极大时,gz_skip 会永远读下去。任何有限的循环燃料都覆盖不了这种情况。有读取预算时,每个循环都有界。
2^61 这个数是模型的限制,不是 zlib 的。模型的每个循环有 2^64 次迭代的燃料。读取循环由一些度量限定,这些度量由剩余的输入、读取预算和尚待交付的字节数构成(fetchRank,以及 gz_read 与 gz_skip 的度量)。一次取数会把缓冲区填满,除非它失败、输入结束、到达 GZ_OFF_MAX,或者降低了 fetchRank;所以小于 2^61 的预算使这些度量以及迭代次数都低于 2^64。某个上界是必需的:2^70 字节、每个 20 字节的空 gzip 成员所需要的轮数超过循环燃料。
预算按描述符编号记:close 之后被重用的编号继承剩余的预算。gzdopen 会拒绝负的描述符,所以没有句柄来自负描述符。