快速解码:inflate_fast 为什么是安全的
源文件:zlib/inffast.c。翻译:ZlibF/Zlib/inffast.c.lean。
inflate_fast 解码字面量和匹配时,并不在每次读写时检查输入和输出是否还有剩余。它之所以安全,是因为调用者只在至少有 6 个输入字节和 258 个输出字节时才进入它,而它的循环每一轮至多读 6 个字节、至多写 258 个字节。本页列出定理假设的入口条件,给出循环不变量,并解释这两个界。
inflate_fast 是内部函数。调用它的是 inflate(流式解码)和 inflateBack(回调解码器)。
结论
| 结论 | 定理 |
|---|---|
Goal.fast_safe:在入口条件下,调用返回且不出故障;后置条件 FastPost 准确说明了改动了什么 |
inflate_fast_safe |
循环的一轮是安全的:至多读 6 个字节,至多写 258 个字节,循环继续时至少写了一个字节(Goal.step_safe) |
inflate_fast_body_step_safe |
| 静态固定表具有表形状 | lenfix_tableSafe、distfix_tableSafe |
同样的安全性命题,外加:结束时模式不是 TYPE 或 BAD 的调用,留下的输出空间比进入时少 |
inflate_fast_safe_progress |
同上,外加:一次调用绝不使 bits + 8 * avail_in 增加,并且除非结束于 TYPE 或 BAD,都使它减小 |
fast_consumes |
Goal.fast_safe 和 Goal.step_safe 这两个目标已完成。inflate_fast_safe 是针对 inflate 的入口条件(Env)陈述的。表中最后两条定理 inflate_fast_safe_progress 和 fast_consumes 是针对两个调用者的入口条件(EnvG)陈述的;它们是调用者的证明内部的引理。
调用者这样使用这些定理:
inflateBack。fast_env证明入口条件。LEN_fast_p从它取得这些条件,并应用fast_consumes。这在inflate_back_sequence_safety的证明内部。从inflateBack发出的调用靠它才安全,这个调用者的循环也靠它才终止。inflate,输入和输出位于两个不同的堆块。inflate_fast_raw_entry在这条前提(ib ≠ ob)下证明入口条件,然后对它们应用inflate_fast_safe_progress。inflate,每一种布局。inflate_sequence_safety_public允许输入和输出是同一个块里的两段。对快速调用,它的证明用的是inflate_fast_default_view_buffers_progress,它是那个证明的一条引理。这条引理对块没有前提。它是对同一个翻译后的函数的第二个证明,针对调用者的区域和解码器不变量陈述;它不使用EnvG。fast_consumes没有用于inflate。见流式解码。inflate,功能结论。inflate_fast_entry对每一种布局证明入口条件。功能定理fast_call_meaning用到它;安全结论不用它。
FastPost 说的是:流的 next_in、avail_in、next_out、avail_out 和 msg,以及状态的 mode、hold 和 bits 被写过;输出字节只在本次调用写入的范围内发生变化;bits < 8 和 hold < 2^bits 重新成立;模式不变,或者变成 TYPE(块结束),或者变成 BAD。堆里其他东西都没有变,也没有发生分配。
关于 inflate_fast 也有功能结论,见功能结论。
假设
这些定理假设下面的入口条件。在 Lean 里它们是记录 EnvG 的字段。Env 是 inflate 的情形,这时窗口绝不是输出对象;inflate_fast_safe 是针对 Env 陈述的。这些是内部前提:调用者在应用本页的定理之前证明它们;做这件事的引理列在结论一节。
- 流。
strm指向一个可写的流记录,它的state是 inflate 状态。 - 输入。
next_in指向一个少于2^63字节的字节对象内部。avail_in ≥ 6,这avail_in个字节都在对象内。字节对象是一个堆块,或者模型里其他的字节数组,例如状态记录内部的数组。 - 输出。
next_out指向一个少于2^63字节的可写字节对象内部。avail_out ≥ 258,这avail_out个字节都在对象内。start ≥ avail_out,并且在同一个对象里next_out之前有start - avail_out个字节;所以下面的beg是指向该对象内部的指针。 - 分离。 输入和输出是不同的字节对象,或者是同一个对象里互不重叠的两段。
- 位缓冲。
bits < 8,hold < 2^bits,sane ≠ 0。 - 窗口。
wsize ≤ 32768,whave ≤ wsize,wnext ≤ wsize。如果whave ≠ 0,window指向某个堆块内的wsize个字节。对inflate,这个块不是输出对象。对inflateBack,它可以就是输出对象;这时wnext = 0,并且窗口的末尾落在输出区域之内。 - 表。
lencode和distcode指向的表,对lenbits和distbits具有安全的形状(LenTableSafe、DistTableSafe;见解码表)。
内部契约页面也描述了 inflate_fast 的入口。那里的描述若比上面的列表多,安全定理假设的是上面的列表。
没有哪条前提提到模式。也没有哪条前提说窗口里的字节是什么,或者说 whave < wsize 蕴含 wnext = whave。安全性只需要上面这些界;其余的属于功能论证。
fast_consumes 多一条前提:每个字面量/长度叶子至少用掉一位(LenLeavesPositive)。对建出来的表,inflate_table_len_leaves_positive 证明了它;对固定表,lenfix_leavesPositive 证明了它。
循环及其不变量
last = in + (strm->avail_in - 5); /* 当 in < last 时继续循环 */
beg = out - (start - strm->avail_out); /* 外层调用的输出起点 */
end = out + (strm->avail_out - 257); /* 当 out < end 时继续循环 */
do {
/* 解码一个字面量,或者一组长度和距离并完成复制 */
} while (in < last && out < end);
/* 把没用到的整字节还回去;把 in、out、hold、bits 写回 */
记 in0 和 out0 为入口处 next_in 和 next_out 的值。
输出块 beg ........ out0 ........ out ............ end ... out0 + avail_out
| 更早的输出 | 本次调用 | 空闲;进入循环时至少 258 字节
输入块 in0 ........ in ............ last ... in0 + avail_in
| 已读 | 未读;进入循环时至少 6 字节
每一轮开始时,下面各条成立(LS,以及 fast_loop_wp 的循环不变量)。
| 名字 | 内容 |
|---|---|
| I1 | in0 ≤ in,并且 in + 6 ≤ in0 + avail_in:可以读六个字节 |
| I2 | out0 ≤ out,并且 out + 258 ≤ out0 + avail_out:可以写 258 个字节 |
| I3 | bits ≤ 30 且 hold < 2^bits |
| I4 | bits + 8 * in0 ≤ bits_entry + 8 * in:手里的每一位要么来自入口,要么来自本次调用读入的字节 |
| I5 | [out0, out) 之外的输出字节与入口时相同 |
因为这是 do 循环,第一轮不经检查就进入。入口条件直接给出它的 I1 和 I2。之后各轮由循环条件得到它们。
每一轮为什么保持不变量
至多读六个字节
一轮里有四处读输入。
| 位置 | 条件与读取 | 之后 |
|---|---|---|
| R1,查长度表之前 | bits < 15:读两个字节 |
16 到 30 位 |
| R2,长度的附加位 | bits < op,其中 op ≤ 5:读一个字节 |
够 op 位 |
| R3,查距离表之前 | bits < 15:读两个字节 |
16 到 30 位 |
| R4,距离的附加位 | bits < op,其中 op ≤ 13:读一个字节;若仍有 bits < op,再读一个 |
够 op 位 |
一个编码至多用 15 位,包括二级查表在内;这是表形状的一部分。所以在 R1 或 R3 之后,或者它们被跳过时,后面的编码都有足够的位。op 的界 5 和 13 也是表形状的一部分。因此每次 bits -= op 拿走的都是确实存在的位,每次移位的位数都小于操作数的宽度。
把四处的最大值加起来是七个字节。七个字节不可能出现。假设 R1、R2、R3、R4 分别读了 2、1、2、2 个字节。
- R1 之后手里至少有 16 位。长度编码至多用 15 位:至少剩 1 位。
- R2 加上 8 位,长度的附加位至多用 5 位:至少剩 4 位。
- R3 加上 16 位,距离编码至多用 15 位:至少剩 5 位。
- R4 只有在读完第一个字节后手里的位数仍少于
op ≤ 13时,才读第二个字节。那么 R4 之前手里的位数少于 5。这与第 3 步矛盾。
所以一轮至多读六个字节,这就是 last 比输入末尾提前五个字节的原因。一轮写一个字面量,或者一次至多 258 字节的匹配,这就是 end 比输出末尾提前 257 个字节的原因。258 这个界来自表形状:长度基值加上它最大的附加值至多是 258。inflate_fast_body_step_safe 陈述了这两个界。
读表
根下标是 hold & ((1 << lenbits) - 1),小于 2^lenbits;表形状保证这 2^lenbits 个表项都在数组之内。根表项是叶子或链接。链接指定一张二级表,它整个在数组之内,并且只含叶子,所以每个编码至多发生一次 goto dolen 或 goto dodist。
无效编码设置 msg 和模式 BAD,然后离开循环。块结束符设置模式 TYPE,然后离开循环。两者经过的出口代码与正常结束相同。
匹配复制
设 dist ≥ 1 是解码出的距离,len 是长度,3 ≤ len ≤ 258。
从输出复制。 如果 dist ≤ out - beg,源 out - dist 不早于 beg,在输出块里。复制逐字节向前进行。它读到的每个字节,要么在这一轮之前就写好了,要么是同一次复制中更早的一步写的;dist < len、两段区域重叠时也是如此。
从窗口复制。 否则有 op = dist - (out - beg) 个字节来自窗口。C 检查 op > whave,由于 sane ≠ 0,这时它报错离开。检查之后 1 ≤ op ≤ whave ≤ wsize。特别地 whave ≠ 0,所以窗口块存在。源位置有三种。
| 条件 | 窗口中的起始下标 | 为什么在 [0, wsize) 之内 |
|---|---|---|
wnext == 0 |
wsize - op |
1 ≤ op ≤ wsize |
0 < wnext < op |
wsize + wnext - op |
op ≤ wsize 且 wnext < op。复制一直进行到环的末尾,再从下标 0 继续,至多 wnext 个字节 |
wnext ≥ op |
wnext - op |
op ≤ wnext ≤ wsize |
每一段复制的字节数,取窗口在那里所存的数量与匹配还需要的数量中较小的一个。如果匹配更长,剩下的部分从输出复制,如上所述。
对 inflateBack,窗口就是输出缓冲区本身。这时 wnext = 0,只有第一行适用;窗口末尾落在输出区域之内这条前提,保证读操作不出块。
归还字节与写回
len = bits >> 3;
in -= len;
bits -= len << 3;
hold &= (1U << bits) - 1;
I4 给出 bits ≤ bits_entry + 8 * (in - in0)。加上 bits_entry < 8,就得到 len ≤ in - in0:函数归还的只是它自己读入的字节,in 不会退到 in0 之前。之后 bits < 8,所以掩码的移位在合法范围内。入口条件 bits < 8 就用在这里。没有它,函数可能退过调用者已经消耗掉的字节。
inflate 在选择快速路径的条件里自己检查了 bits < 8。inflateBack 不检查。它的分派循环的证明把这个事实放在循环不变量里:每一轮以 TYPE、TABLE 或 LEN 模式开始时,持有的位都少于 8 个(Short)。LEN_fast_p 把入口处的 bits < 8 当作前提,由上述不变量提供,并证明调用之后它再次成立。
随后函数算出新的 avail_in 和 avail_out,两者各由同一个块内的指针差得到,连同两个游标、hold 和 bits 一起存回(fast_finish_wp)。
循环为什么会结束
主循环的度量是剩余的输出空间 out0 + avail_out - out(fast_loop_wp)。不离开循环的一轮至少写一个字节,所以度量下降。它小于 2^63,远小于 2^64 的循环燃料。
在一轮之内,复制循环跑 op 或 len 次并递减计数,一个编码至多多查一次表。
难点在哪里
两个余量都很小,而且恰好够用。循环之所以安全,只是因为一轮绝不会读第七个字节,而这一点在任何单独一条语句里都看不出来:它来自四处补位与表所允许的位数之间的相互作用。证明在堆上、对每一张形状安全的表,照着上面论证里同样的分情形方式进行。
第二个难点是输出块。它在同一轮里既被读又被写,匹配的源可以与目的重叠,输入和输出还可能是同一个块里的两段:在 sanitizer 下运行,真实的 C 在这种布局下解码正确,没有任何报告。因此循环不变量跟踪的是整个输出数组,而不是分开的“旧”字节和“新”字节两个视图。
没有定理陈述的 C 解读
- 匹配从窗口读到的字节是先前写过的。对
inflate,这来自流式解码的窗口形状 W.5:没有填满的窗口里wnext = whave,所以只可能出现表的第三行,它读的位置在wnext之前。EnvG不带 W.5,安全定理也不需要它:在模型里,读一个从未写过的字节会得到任意值,不算故障(可信基础)。尚未由证明确认。
功能结论
这些结论说的是快速解码器算出了什么。每一项都有定理,但都不是安全结论所必需的。
| 结论 | 定理 |
|---|---|
| 一轮恰好消耗格式中一个记号的那些位,并且它消耗的位就是源中接下来的位 | actual_body_refines_token、actual_body_preserves_origin |
| 查长度表或距离表得到的是格式规定的符号 | length_lookup_matches_format、distance_lookup_matches_format |
| 匹配复制就是格式中的 LZ77 复制 | actual_distance_refines_lz77、actual_copy_match_refines_lz77 |
这些结论用的不变量更大:它把已消耗的位与源数据流联系起来,把窗口内容与更早的输出联系起来。fast_call_meaning 把这层含义带过 inflate 中 LEN 的快速分支,输入和输出可以在任何字节对象里:调用之后,已解码的记号仍然能按格式的规定解析;或者模式是 BAD,并且已读的输入没有任何合法的续接。它是默认 zlib 流的往返的一步。提前读入又归还的字节,与已解码符号的含义无关;见流式解码。