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

固定配置的引理所用的输入范围

对安全性来说,输入范围只有一个:每一种输入。 必需目标对每个参数的每个取值全称量化; 落在支持范围之外的值是文档规定的拒绝,目标同样覆盖它。 本页定义三个较窄的范围:默认、常见、全部支持。它们只在两件事上有用: 针对固定配置陈述的内部引理,以及功能目标(不是安全结论所必需的)。

“每一种输入”的例子:Goal.deflateInit2__safety 对每个压缩级别、方法、窗口、内存级别和策略都成立; Goal.inflateInit2__safety 对每个窗口值都成立;序列目标对从这样的初始化开始的每段历史都成立。

构建始终相同:默认 x86_64 Linux、LP64、静态库、默认分配器, 并带有平台假设:没有哪个字节对象达到或超过 2^63 字节。

三个范围

对每一族目标,默认输入包含在常见输入之中,常见输入又包含在全部支持的输入之中。 对两个流引擎,每一层包含都是严格的。 忽略或固定某个参数的函数,不同的范围就少一些;与另一个范围重合的范围不需要单独证明。

只证明几个例子并不覆盖一个范围: 每个范围都对其命题点名的数据、缓冲区、堆内容、分配失败和历史全称量化。

只有当一条类型与目标完全相同的定理覆盖了目标命题所允许的每一种输入时,这个目标才算完成。 只覆盖默认输入或只覆盖常见输入的定理,目标仍是未完成。

Deflate 输入

三个范围都使用 method = Z_DEFLATED = 8。

参数 默认 常见 全部支持
level -1,归一化为 6 -1 以及 0 到 9 -1 以及 0 到 9
memLevel 8 8 1 到 9
windowBits 15 -15、15、31 -15 到 -9;8 到 15;25 到 31
strategy 0 0 0 到 4
封装 zlib 裸、zlib、gzip 裸、zlib、gzip

每一列中的所有组合都包括在内。常见输入保持 32 KiB 窗口、默认内存级别和默认策略。 带符号的窗口参数在 -15 时选择裸流,在 15 时选择 zlib,在 31 时选择 gzip。 在完整范围内,zlib 的窗口值 8 被归一化为 9;裸流的 -8 和 gzip 的 24 被固定版本的源码拒绝。

五种策略是默认(0)、过滤(1)、仅 Huffman(2)、RLE(3)和固定码(4)。 内存级别决定哈希表的大小,也决定那个同时存放已记录符号和待输出字节的缓冲区的大小。 所以,较小的内存级别会改变“待输出字节永远不会覆盖尚未读取的符号”这一论证 (见 trees)。

压缩器各部分依赖的参数

下表说明压缩器的每个部分依赖哪个参数。针对该参数某一个取值的引理不覆盖其他取值。

压缩器的部分 它依赖的参数
默认初始化 deflateInit_ 固定方法、窗口、内存级别和策略,只留下级别可变。它的目标是 Goal.deflateInit__safety。
一般初始化 deflateInit2_ 接受全部五个参数。Goal.deflateInit2__safety 覆盖每个参数的每个取值。
策略分派 级别 0 选择存储引擎,级别 1 到 3 选择快速引擎,级别 4 到 9 选择慢速引擎。级别非零时,仅 Huffman 和 RLE 策略会取代这一选择。
匹配搜索 链长、惰性匹配长度和“足够好”的匹配长度,取自配置表中由级别选定的一行。
补充与滑动 窗口大小和哈希大小决定数组边界、环形位置和滑动。
树与块输出 符号容量、待输出缓冲区和第一个未读符号的位置依赖内存级别。关于一棵树或一个符号的引理给不出共用缓冲区的界。

这张表列的是依赖关系,不说明证明了什么。 不变量见 deflate 证明指南,哪些目标已完成,见进度。

Inflate 输入

inflate 没有级别、内存级别和策略。它的输入文法本身就包含存储、固定和动态三种块。

范围 windowBits
默认 15
常见 -15、15、31、47
全部支持 -15 到 -8;0;8 到 15;16;24 到 31;32;40 到 47

常见输入选择 32 KiB 窗口,流的类型是裸流、zlib、gzip 或自动检测。 取值 0、16 和 32 把窗口大小留给流的头部决定;gzip 头部不带窗口大小,这时固定版本的源码使用 15。 较小的窗口会改变匹配距离的检查。小窗口是否接受每个合法的流,是功能问题,不是安全问题。

快速执行与慢速执行

inflate 有一个快速解码循环(inflate_fast)和一个慢速解码循环。走哪一个不取决于配置: 当至少有六个输入字节和至少 258 个输出字节可用,并且已缓冲的位少于八个时, inflate 进入快速循环(have >= 6 && left >= 258 && bits < 8)。 随着调用者更换缓冲区,默认配置的流两条路径都可能走。 所以,针对默认输入的结论必须覆盖两条路径,以及它们之间的切换。

解码器的部分 它依赖什么
初始化与重置 窗口大小和所选的封装。
表构造 块的类型:存储、固定或动态。三种类型在每个范围里都会出现。
快速解码 上面的入口条件,以及前面各步留下的表和窗口。
慢速解码 字面量、长度、距离和匹配各步,每一步都作用在前一步返回的状态上。
分派与退出 两条路径、等待输入或输出的出口、错误出口、窗口更新,以及计数器的写回。

这些部分的说明见 inflate 证明指南。 关于一条路径的引理假设了入口处的不变量;它不是关于整个流的结论。

其他函数

对校验和、查询函数、整缓冲区函数、回调解码器和 gzip 文件函数, 输入范围就是目标命题所说的:它的参数和它的前提。 上面的流参数只在函数或它所操作的状态确实依赖它们时才适用。

每个范围都保留错误返回、分配失败和清理路径。公开目标还保留对每个非法参数值的拒绝。

ZLIB × LEAN

目录

正在阅读固定配置的引理所用的输入范围