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

平台假设:对象大小

目标对系统只取一条前提:没有哪个字节对象达到或超过 2^63 字节。 这是目标平台(默认 x86_64 Linux LP64 构建)的事实:在这个平台上,没有分配器会返回大于 PTRDIFF_MAX 的对象。 它不需要调用者去检查。本页陈述这条前提,说明为什么需要它,并列出带有它的目标。

操作系统、编译器和硬件的性质没有被证明;它们列在可信基础中。

前提

模型中每个字节对象都少于 2^63 字节:调用者提供的缓冲区、库分配的块、静态数组,以及内嵌在记录里的字节数组。

Lean 谓词是 PlatformMemory.lean 中的 ZlibF.PlatformMemory.ByteObjectsFit:

对每个字节对象引用 ref 及其数组 a:
    若 Space.get h ref = some a,则 a.size < 2^63
这条前提说了什么 这条前提没有说什么
每个单独的对象都少于 2^63 字节。 它不涉及所有分配的总和,也不涉及一个流在多次调用中处理的总长度。
它不说明指针合法、已初始化或没有越界。那些是另外的安全义务。

为什么需要它。 指向同一个对象的两个指针之差是 ptrdiff_t,一个有符号 64 位整数。 在达到或超过 2^63 字节的对象里,这个差可能溢出,而这是未定义行为。有了这条前提,每个这样的差都放得下。 快速解码器(inflate_fast)的入口证明就是从它推出各自的大小事实的。

哪里不必假设它就成立。 模型的分配器拒绝 2^63 字节及以上的请求,所以库分配的每个块都满足它 (ByteObjectsFit.allocB,Proof/PlatformMemory.lean)。 对调用者的内存,以及历史起点的堆,这条前提是假设的。 偏离记录中有“平台字节对象范围”一行。

哪些目标带有它

需要这条前提的目标会明确写出它:写在调用开始时的堆上,以及调用者每次交回的堆上。 没有写出它的目标,不靠它也成立。

目标 前提出现在哪里
对流的一次调用:Goal.<function>_safety、Goal.inflate_sequence_safety、Goal.deflate_sequence_safety 在这次调用的堆上(StreamCallDomain,以及 StreamSequenceSafety 的子句 2)。
inflate 历史(StreamReachable .inflate) 还出现在历史中此前的每次调用上,以及调用者每次修改之后。
deflate 历史(StreamReachable .deflate) 不出现在此前的堆上。不论此前的堆是否满足这个上界,deflate 流都可达。所以 deflate 目标覆盖的历史更多。
compress*、uncompress* CompressorSafety、UncompressCountedSafe 和 UncompressSingleSafe 的一条前提。
gzip 文件接口 在每次打开时的堆上,以及调用者每次修改之后(GzHistory;GzOpenSafe 和 GzDopenSafe 也带有它)。
回调解码器 在每次 inflateBack 调用的堆上(BackSafeReachable、Goal.inflate_back_sequence_safety)。回调必须保持它(BackPlatform)。
校验和、zlibVersion、zlibCompileFlags、初始化、End、复制、拒绝 没有写出:这些目标不靠它也成立。inflateEnd 和 inflateCopy 从 inflate 历史出发,而 inflate 历史如第二行所说带有它。

这条前提对每个输入范围都相同。它不是压缩参数。

这条前提不涵盖什么

模型对指针加零和 NULL - NULL 的处理是另一条限制,说明见 安全性,空指针与指针差和可信基础。

ZLIB × LEAN

目录

正在阅读平台假设:对象大小