跳到正文
形式化验证

zlib × Lean

用 Lean 4 对 zlib 的逐语句翻译作机器检查的证明:默认 x86_64 Linux 构建中每个有文档的公开函数都是安全的,即没有未定义行为、没有内存错误、没有泄漏,并且终止;每条定理都写明自己的前提。

结论

前三项是安全结论;第四项是一项功能结论。每一项的状态是完成或未完成。

  1. 1完成

    inflate 对每个输入都安全:没有未定义行为、内存错误、泄漏,并且终止;对一个流上的每个调用序列和缓冲区的任何切分都成立。

  2. 2完成

    deflate 对每个输入都安全,对一个流上的每个调用序列都成立。

  3. 3完成

    其余每个有文档的公开函数都安全:compress* 与 uncompress*、其他流函数、校验和函数、gzip 文件接口和回调解码器 inflateBack。

  4. 4完成

    默认 zlib 流的往返:uncompress(compress(x)) = x;用默认级别的 deflateInit 和任意刷新值的 deflate 调用压缩,以 deflate(Z_FINISH) 调用结束,再用 inflateInit 解压,对缓冲区的任何切分都得到原输入。

完成:存在一条 Lean 定理,它的命题恰好就是这个目标,并且通过了本项目的每一项检查。未完成:没有这样的定理。

翻译和运行时模型与 C 相符,这一点靠审阅和测试,不是靠证明:见 可信基础;调用必须满足的条件见 偏离记录;一项完成的结论依靠什么,见 这一页。

每个函数的状态,以及哪些不在计划内 →

先读 zlib 本身

  1. 基础压缩:LZ77 与 Huffman

    一个完整的小编解码器:重复片段、Huffman 编码、规则的传递与终止。从 ABABABAB 开始,逐步重建 DEFLATE 的核心。

  2. zlib 的实现与优化

    zlib 如何真正实现并优化压缩与解压:窗口、哈希链、匹配搜索、查表和复制。这是最深入的一篇。

  3. zlib 的功能扩展:流式处理与校验

    流式调用、字典、封装、Adler-32 与 CRC-32,以及应用接口:为什么完整缓冲区不够用。

参考

  • 结论的状态: 每项结论、每个函数是完成还是未完成
  • 规格: 安全目标、API 契约、格式、可信基础与偏离记录
  • 证明: 证明方法与各组件的论证
  • 术语表
ZLIB × LEAN

目录

正在阅读zlib × Lean