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

compress* 的安全性

compress、compress_z、compress2 和 compress2_z 在满足下列前提的每个输入上都是安全的:调用会返回,没有未定义行为,只写目的缓冲区,并且释放它分配的一切。本页给出这个命题、它的前提和证明的轮廓。

源文件:compress.c。缓冲区工具函数一页解读这段 C。术语见术语表。

证明了什么

目标 定理
Goal.compress2_z_safety compress2_z_safety
Goal.compress2_safety compress2_safety
Goal.compress_z_safety compress_z_safety
Goal.compress_safety compress_safety

这四个都是安全结论,都是必需的,并且都已完成。每个定理证明的正是原样写出的目标,没有附加假设;下面的前提是目标命题的一部分。

每个目标都是 CompressorSafety 的一个实例。对满足下列前提的每个输入:

  • 调用在没有未定义行为的情况下运行并返回;
  • 被拒绝的参数返回 Z_STREAM_ERROR,并且什么都不改变;
  • 否则,调用向输出缓冲区写入的字节数不超过容量,此外什么都不写;
  • 每次分配在每条路径上都被释放;
  • Z_MEM_ERROR 只在某次分配失败之后出现。

关于写出的字节,这里什么都没有说。那是功能契约 CompressorContract,不是安全结论所必需的。

假设了什么

前提 含义
Fresh、Uniq、LibraryGlobals 调用者的堆是良构的,静态表是初始的那些表。
ByteObjectsFit 每个字节对象少于 2^63 个字节。
CompressArguments 参数要么被 C 自己的检查拒绝,要么源缓冲区可读、目的缓冲区在其容量范围内可写,并且两者不重叠。
长度单元 compress 和 compress2 要求 destLen 非 NULL。_z 形式允许传入 NULL,并拒绝它。在翻译中,这个单元是一个传入的值和一个返回的值,不是内存。所以与源缓冲区或目的缓冲区重叠的单元无法表达,这样的调用在定理之外。

源缓冲区与目的缓冲区的分离,以及对长度单元的限制,在偏离记录中有一行:“整缓冲区压缩”。

结构

flowchart TD
  args["参数检查:在建立任何对象之前拒绝"] --> init
  init["init_cases:deflateInit_ 失败(释放流)或成功"] --> loop
  loop["loop_run:循环 do ... while (err == Z_OK),每次迭代调用一次 deflate"] --> epi
  epi["epilogue:输出长度、deflateEnd、释放流"] --> z["compress2_z_safety_gen"]
  z --> w["compress_z, compress2, compress"]

compress2_z 驱动一个局部的 z_stream,依次经过 deflateInit_、一个由 deflate 调用组成的循环和 deflateEnd。每次调用 deflate 之前,循环用 64 位的剩余长度补充 32 位的 avail_in 和 avail_out。本页把这次补充称为流的重新装填(rebuffer)。

CState 是两次迭代之间的状态:流不变量、可达性、已消耗输入和已产生输出的计数,以及这样一个事实:堆就是调用者的堆,只是目的缓冲区里写入了到此为止的输出。

证明不依赖它所驱动的流有哪一类历史(CompressReach),对任意一类都适用。compress2_z_safety_gen 以关于这些历史的两个事实为前提:

  • 一次 deflate 调用的完整契约 Goal.deflate,限制在这些历史上;
  • DeflateLoopFacts,即 Goal.deflate 没有陈述的、关于一次 deflate 调用的四个事实:
  • 一次 Z_NO_FLUSH 调用如果没有被拒绝,有输入也有空间,并且返回 Z_OK,就取得进展;
  • 第一次 Z_FINISH 之后的新输入,要么得到 Z_BUF_ERROR,要么至少写出一个字节;
  • 每次调用都保持 gzip 头指针;
  • 每次调用都保持所拥有的块。

compress2_z 以 memLevel 8 初始化它的流。所以这四条定理用 DeflateReachMid 实例化这个通用证明:这些历史以 memLevel ≥ 3 的 deflateInit2_ 开始,之后只重新装填流并调用 deflate。沿着这些历史有 lit_bufsize ≥ 512,两个事实都无需假设即成立(goalDeflate_mid、loopFacts_mid)。memLevel 为 1 或 2 的历史还需要一个关于压缩器共用的待输出与符号缓冲区的界,见树。这里的定理不使用它。

deflateInit_ 和 deflateEnd 通过它们各自的定理使用(deflateInit_proof、deflateEnd_safe、deflate_end_public)。

终止

度量是 avail_in + sourceLen + avail_out + left。这里的 sourceLen 和 left 是 C 的局部变量:尚未交给流的源字节数和目的空间。度量的初值低于循环燃料 2^64。补充保持度量不变。返回 Z_OK 的调用没有被拒绝,并且有空间;否则 Goal.deflate 给出 Z_BUF_ERROR。使用 Z_NO_FLUSH 时调用有输入,因为补充之后源数据还有剩余,所以 DeflateLoopFacts 给出进展。使用 Z_FINISH 时,Goal.deflate 的进展子句给出进展,除非流已经结束而又有新输入;在那种情况下 DeflateLoopFacts 给出 Z_BUF_ERROR 或一个写出的字节。进展使度量下降。

上界函数

compressBound 和 compressBound_z 不读内存。它们的目标 Goal.compressBound 和 Goal.compressBound_z 给出上界公式的精确值,这同样的两个目标也就是它们的安全目标。定理是 compressBound 和 compressBound_z。

不涵盖:翻译后的压缩器的每个输出都不超过上界。那是一条功能命题,安全结论用不到它;见缓冲区工具函数。对 compress 和 compress_z,在每次分配都成功时,Goal.compress_completes 和 Goal.compress_z_completes 陈述了这一点(见往返)。对其他级别,定理 compress_bound_adequate 陈述了这一点,deflate_bound_adequate 对 deflateBound 的上界陈述了同样的事,但都只针对不涉及堆的 API 模型。没有定理说翻译后的 compress2 或 deflate 遵循这个模型。

ZLIB × LEAN

目录

正在阅读compress* 的安全性