参考文档 / ZLIB × LEAN
缓冲区工具函数:源码上的决定
本页列出 compress.c、uncompr.c 以及 deflate.c 的上界函数中,C 的做法需要模型小心表示的地方。每一处都说明 C 做了什么,模型做了什么,以及是否有定理覆盖它。这些函数的安全证明在另外两页;本页是它们的源码阅读配套页。
结论在哪里
| 函数 | 安全定理(必需) | 页面 |
|---|---|---|
compress、compress_z、compress2、compress2_z |
compress_safety、compress_z_safety、compress2_safety、compress2_z_safety |
compress* 的安全性 |
uncompress、uncompress_z、uncompress2、uncompress2_z |
uncompress_safe、uncompress_z_safe、uncompress2_safe、uncompress2_z_safe |
uncompress* 的安全性 |
deflateBound、deflateBound_z |
deflateBound_safety、deflateBound_z_safety |
流式压缩 |
compressBound、compressBound_z |
compressBound、compressBound_z:公式的精确值。这两个函数不读内存,所以这两个完整契约也就是它们的安全目标 |
compress* 的安全性 |
这些函数的功能契约,例如 uncompress 写出的字节,或者压缩器的每个输出都不超过上界,不是安全结论所必需的。
对 C 的某种解读如果没有定理陈述,就标为尚未由证明确认。
各项决定
局部流是自动存储
- C。
compress2_z和uncompress2_z把z_stream stream;声明为局部变量。创建它不会失败,也不是对分配器的调用。 - 模型。 局部流是由
allocLocalZ建立的一条新分配的记录。它不消耗分配失败预言的一次调用,也不移动库自身各次分配的序号。每次返回之前它都被释放。被取了地址的标量局部变量按同样的方式处理。 - 覆盖情况。 已覆盖:安全定理带着这个局部变量运行翻译,并证明没有任何东西仍处于已分配状态。
包装函数在调用 _z 之前读取长度单元
- C。
compress2在调用compress2_z之前执行z_size_t got = *destLen;。uncompress2以同样的方式读取*destLen和*sourceLen。_z函数内部的NULL测试来得太晚,保护不了这些读取:NULL单元在包装函数里就是未定义行为。 - 模型。 在
compress2、compress、uncompress2或uncompress中,NULL单元是Fault.ub。 - 覆盖情况。 这四个函数的安全目标要求单元非
NULL;_z形式允许传入NULL,并返回Z_STREAM_ERROR拒绝它。zlib.h没有说包装函数可以接受NULL单元。
compress* 的长度单元是值,不是内存
- C。
destLen指向调用者的一个单元。compress2_z写它两次。参数检查之后,它读出容量并立即存入 0(left = *destLen; *destLen = 0;)。循环之后,它存入输出长度。所以deflateInit失败后的返回在单元里留下 0,被拒绝的调用不写这个单元。compress2把单元复制到一个局部变量,把这个局部变量传给compress2_z,并在每次返回时复制回去。 - 模型。 翻译接收
*destLen的值(NULL对应none),并把返回时单元里的值作为第二个结果返回:调用被拒绝时是传入的值,deflateInit失败后是 0,其余情况是输出长度(翻译)。这个单元不是内存。 - 覆盖情况。 这限制了安全目标:与源缓冲区或目的缓冲区重叠的长度单元无法表达,所以这样的调用在定理之外。偏离记录的 “整缓冲区压缩” 一行记录了这一点。
uncompress* 的长度单元是内存
- C。
uncompress2_z在参数检查之后读取*sourceLen和*destLen,并在循环之后写它们一次(*sourceLen -= len; *destLen -= left;)。被拒绝的调用和inflateInit失败后的返回都不写它们。uncompress2把两个单元复制到局部变量,并在每次返回时复制回去。 - 模型。 每个单元是一个八字节的块,按小端序存放这个值。
- 覆盖情况。 由安全定理覆盖。这些单元与各缓冲区分离、彼此也分离,是目标的一条显式前提(偏离记录的 “计数解压” 一行)。
compress2_z 中容量为零的 NULL 目的缓冲区
- C。
dest == NULL且*destLen == 0能通过参数检查。函数在结束时计算stream.next_out - dest,两个指针都是NULL。 - 模型。 指针差
Ptr.diff对NULL - NULL返回 0。两个指针中只有一个是NULL时,它产生故障。 - 覆盖情况。 安全定理是在模型的这条规则下证明的。尚未由证明确认:选定的构建定义了
NULL - NULL;C 标准(C17、C23)没有定义它。它是可信基础中的一项(安全,NULL指针)。
uncompress2_z 的占位输出指针
- C。 对于
dest == NULL且*destLen == 0,函数令dest = (Bytef *)&stream.reserved,因为next_out不可以是NULL。这个指针只会在avail_out == 0时作为next_out传递。 - 模型。 占位对象是一个单独的八字节局部块,每次返回之前都被释放。模型不表示它是流记录的一部分。
- 覆盖情况。
uncompress2_z_safe对翻译覆盖了这种情形。尚未由证明确认:在avail_out == 0时解码器不通过next_out写任何东西,所以记录的一个字段与一个单独的块之间的差别无法被观察到。
循环用 64 位长度补充 32 位计数
- C。
avail_in和avail_out是unsigned;剩余长度是z_size_t。每一轮循环给空了的计数补充至多(uInt)-1个字节。循环只在Z_OK时继续。初始化成功之后会运行deflateEnd或inflateEnd,返回码在最后被映射。 - 模型。 翻译逐条保留这些语句。
- 覆盖情况。 由安全定理覆盖;它们的终止度量在两个安全页上。解码器较晚的内存失败可能出现在已经写出一些输出之后:
uncompress*的安全目标允许Z_MEM_ERROR伴随非空的输出。
compressBound_z:回绕的加法与饱和
- C。 公式使用回绕的
z_size_t加法,并在和发生回绕时返回最大值。 - 模型。
UInt64上的一个纯函数。 - 覆盖情况。
compressBound和compressBound_z对每个输入证明了精确值。
deflateBound_z:gzip extra 字段的长度
- C。
deflateBound_z读取封装状态和可选的 gzip 头字符串;每次字符串扫描都包含结尾的 NUL。对于 extra 字段,打过补丁的 C 把 2 和extra_len的低 16 位以z_size_t加到封装开销上,这正是头部写入函数输出的长度(补丁 0007)。上游 zlib 加的是按 32 位unsigned求值的2 + extra_len,当extra_len >= 0xfffffffe时会回绕。 - 模型。 翻译遵循打过补丁的 C。
-
覆盖情况。 安全性已覆盖(
deflateBound_safety、deflateBound_z_safety)。在上游 zlib 中,上界的值有两处缺陷。- 当
extra_len为2^32 - 2和2^32 - 1时上界偏小,对 C 的一次运行表明了这一点(发现)。补丁 0007 取长度的低 16 位(上游 PR 1360 的deflate.c部分,处于打开状态)。没有目标陈述 gzip 头部时上界的值。 - 在
windowBits为 15、memLevel为 8、使用Z_FIXED且级别为 1 到 3 时,输出可以超过上界,对 C 的一次运行表明了这一点(发现)。补丁 0006 让Z_FIXED使用保守的上界(上游 PR 1394,处于打开状态)。
尚未由证明确认:在源数据和头部定义域的其余部分上,输出不超过上界。
- 当