模型的限制
本页列出模型的一类限制:zlib 的调用者对它们无法采取任何行动。它们分三类:目标作为前提陈述的、对模型中的堆的条件;运行时表示 C 的内存和库调用时所作的选择;以及功能定理和模型定理的限制,安全目标都不依赖它们。每一条限制都是模型可能与 C 不同的地方。调用者的义务在另一页:偏离记录。被信任的东西概括在可信基础中,本页是其中第 2 项的细节。
本页用到的名字
| 名字 | 含义 |
|---|---|
| 块 | 模型的堆中的一次分配,用一个编号指称 |
nextBlk |
下一次分配将得到的编号。释放之后编号不会再用 |
Fresh |
编号在 nextBlk 及以上的块都不存活 |
Uniq |
一个块编号至多在堆的一张表中存有对象 |
allocOk |
分配预言:对每一次分配尝试,说它是否成功 |
Heap.garbage |
任意初值函数:新分配内存中每个整数单元的值 |
Tbl |
堆中表的类型:一个数组,按块编号当作全函数来读 |
Space.get、put、modify |
读堆中的一个数组、替换它,或就地修改它 |
copyK |
整个记录的复制,即对一个结构体做 memcpy 的模型 |
strLitRef |
指向一个 C 字符串字面量的指针 |
目标所陈述的、对模型的条件
第一行是目标的前提。C 程序什么都不用做就满足它们;它们之所以存在,是因为 Lean 命题要对模型中的每个堆量化,其中包括任何 C 程序都造不出来的堆。其余四行是模型所作的选择,目标就是在这些选择之上陈述的。
| 领域 | 模型怎样做 | 由此得出什么 |
|---|---|---|
堆的良构性(Fresh、Uniq、LibraryGlobals、CrcGlobals) |
初始化、打开、compress* 或 uncompress* 调用开始时的堆,在 nextBlk 及以上没有存活的块(Fresh),每个块编号至多有一个对象(Uniq),并且带有所选构建的常量表(LibraryGlobals)。CRC 目标只要求两张 CRC 表(CrcGlobals),inflate 和 inflateSync 的拒绝只要求 Fresh。两次调用之间调用者的修改保持这三条(Rebuffer、GzCallerFrame)。 |
这些是关于模型自身记账的前提。zlib.h 没有把这样的义务加给调用者,C 的调用者也破坏不了它们。 |
| 循环燃料 | 翻译后的每个循环至多运行 2^64 次迭代;耗尽这个上界就是 Fault.outOfFuel。 |
结论为正常返回的安全目标证明了这个上界永远达不到。凡是 C 可能无界地循环、而证明又推不出上界的地方,目标都有一条给出上界的前提:回调输入总量和 gz 读取预算。 |
| CRC 地址与字访问 | addrOf 只观察地址的低位。堆字节块从对齐的地址开始;静态的或内嵌的字节对象有一个任意而稳定的余数,它是堆的元数据,任何写入都不改变它。字的加载由八个字节拼成。 |
没有建模:通用的 ABI 布局、原始块的任意起点,以及 C 中转换为 z_word_t * 的别名语义。校验和目标的定义域不因此变窄。 |
指针加零与 NULL - NULL |
Ptr.add p 0 对每一种指针值都返回 p:空指针、从未写入的指针字段(在模型中是 NULL)、指向已释放块的指针。Ptr.diff 对两个 NULL 返回零。在空指针或指向已释放块的指针上的其他运算都出故障。 |
模型比 ISO C 宽松:C17 和 C23 只对指向存活数组对象或其末尾后一位的指针定义 p + 0,也都没有定义 NULL - NULL。模型允许某个操作,并不说明 C 有定义。安全性规格把这些操作与语言规则作了对照。被验证的源码会到达这两种操作。gzseek64 和 gz_skip_have 在 x.next 上计算 x.next += 0,而它可能从未写入,或指向调用者已释放的调用者缓冲区;没有补丁改动这一点。dest 为 NULL、*destLen == 0 的 compress 调用在它的目标之内,它的 deflateInit 成功时,compress2_z 计算 stream.next_out - dest,两个指针都是 NULL。 |
| 外部错误字符串 | strerror 返回一个只读视图,视图上带有一个代次,每次 strerror 调用都会改变这个代次。它不消耗分配尝试,也不占用库拥有的存活块。下一次 strerror 调用使先前的视图失效。 |
模型说的是固定区域设置下的顺序调用。没有建模:并发调用、区域设置的改变,以及旧指针身份的再次使用。 |
运行时怎样表示 C
运行时定义了翻译后的一次运行是什么意思,所以“不出故障”的定理说的就是这些定义。
内存与库操作
堆为每一类对象单设一张表。释放过的块编号永不再用。分配器只有在 nextBlk 这个编号在每一张表中都尚未使用时才写入(Heap.slotUsed),否则出故障。
| 操作 | 模型怎样做 |
|---|---|
memcpy、zmemcpy |
即使长度为零也拒绝 NULL 指针,并拒绝重叠的范围;长度不为零时拒绝只读的目的地址。整个记录的复制使用 copyK,它拒绝把对象复制到自身上。单独的一次记录读取加一次记录写入,不检查重叠。 |
memmove |
检查同样的范围和可写性(长度为零时同样例外),但允许重叠,并从原来的源复制。 |
memset、zmemzero |
Ptr.fill 按元素计数并赋一个值;即使长度为零它也拒绝 NULL 指针,长度不为零时拒绝只读的目的地址。只有在指明的用法里它才表示按字节的 memset 或清零。Ptr.memset 重复一个字节。整个记录的清零是写入一个显式的零记录。 |
strlen |
要求所表示的块内有 NUL。 |
| 分配 | 新分配的整数来自任意初值函数;新分配的指针字段是 NULL。超过 PTRDIFF_MAX 字节的 malloc 请求返回 NULL。否则由预言 allocOk 决定是否失败。每次 malloc 调用消耗一个预言编号。自动局部对象绕过这个预言,不消耗分配尝试。 |
free |
NULL 是空操作。否则参数必须指向对应种类的一次存活、可写的分配的起点。没有记录分配来源的标签。 |
| 字符串字面量 | strLitRef 指称生成的封闭表 strTable 中一个静态、只读、以 NUL 结尾的条目。它始终存活,身份稳定,永不释放。表中没有的字面量文本会出故障。 |
分配、格式化、errno、abs 和 strerror 的模型覆盖 zlib 对它们的用法。它们不是 libc 的通用模型;它们与 libc 相符,靠的是审查,不是证明。
表示上的缺口与证明义务
| 选择或缺口 | 对关于 C 的结论意味着什么 |
|---|---|
| 未初始化指针变成 NULL | 在模型里,对这样的指针作比较、复制和释放,可以在没有先写入的情况下成功。关于 C 的结论需要每个指针都先写后读;没有定理陈述这一点,它尚未确认,须由源码审查确认。初始化的翻译显式地把分配出来的两种流状态记录清零;这并不是新分配的记录或自动变量 z_stream 的普遍性质。inflateBackInit_ 建立的状态记录,其 strm 和 mode 字段没有写过;模型把这个 strm 读作 NULL,所以 inflate 函数的状态检查会拒绝这个记录。把 Goal.inflate_refusal 和 inflate 各目标的拒绝子句用于这样的流,得到的只是关于模型的陈述。zlib.h 用 inflateBackEnd 结束这样的流。 |
| 每个单元一个任意初值 | 关于整数的定理对每个 Heap.garbage 量化,它以分配尝试和单元位置为下标。在模型里,对同一个单元的多次读取结果一致;C 对不确定的值不保证这一点,也没有程序检查证明是否依赖了它。 |
| 数组的范围是谓词 | 数组的长度不是它的类型的一部分:WellFormed、Heap.RecordsWellFormed 和 Statics.WellFormed 陈述 C 中的长度,生成的引理说明各操作保持它们。运行时不把静态表的内容与 C 作比较。 |
| 指针相等是结构相等 | 指向不同对象的指针比较为不等,对悬空指针作相等比较不出故障。这两点 C 都不保证,在相邻对象的边界处尤其如此;没有程序检查证明是否依赖了它。关系比较要求两个指针在同一个存活的数组里。 |
| 地址与布局模型不完整 | 没有 ABI 地址、有效类型或“记录作为字节”的通用模型。有八个公开函数的结果单元是值而不是内存(偏离记录的“结果单元”和“整缓冲区压缩”两行)。z_stream 记录放在单独的表里,所以与缓冲区或另一个记录部分重叠的记录无法表达(偏离记录,“复制的目的流”一行)。 |
| 只读标记不完整 | 字节块、具名的静态表和实例可以是只读的。字块和表中的记录无法表示这个限定。 |
| 指针构造的检查不完整 | Ptr.add 检查它的结果,但不检查它出发的偏移是否有效。没有翻译经由构造器 Ptr.ref 造出偏移无效的指针,这一点靠审查,没有检查。 |
| 不跟踪对象的来源 | 翻译后的代码可以释放由 allocBytes 创建的调用者块。在 API 禁止这样做的地方,排除它的是目标的帧子句和所有权子句。把状态转换成错误的种类,会比相应的 C 访问更早出故障。 |
表的更新
Tbl 包着一个数组,按块编号当作全函数来读。不存在的条目返回默认值(none 或 false)。更新操作 upd 有已证明的同键、异键和重复更新规则,它们来自 Tbl.get_set。
执行写入的原语使用 Space.modify:它把数组从表中取出,修改后放回,这样就不会留下一串旧数组。Space.modify_eq 说它等于更简单的函数式操作 put,证明是用 put 来推理的。靠审查而被信任的有:Tbl.get_set、Tbl.modify_eq,以及每个生成的 Space 实例的 modify 和 modify_eq。
功能命题与模型命题
下面各行限制的是功能目标、API 模型和内部引理。安全目标都不依赖它们。哪些功能目标在计划内,见进度。
| 领域 | 限制 | 由此得出什么 |
|---|---|---|
| API 手册条目 | 条目的 Pre 可以要求有效的句柄、互相分离的缓冲区、实际字符串的校验和、生成的算子,或某种写明的调用顺序 | 条目描述的是通常的用法。函数的 Lean 目标是更宽的命题,不因此变窄。 |
| API 模型中压缩器的长度单元 | 功能模型 Concrete.compress2_z 和 Concrete.compress2 把长度单元当作一个可选的标量,并返回写入的值 |
对与输入或输出别名的单元,这些模型什么都没说。翻译用的是同样的标量单元,这限制了安全目标:见偏离记录中“整缓冲区压缩”一行。 |
| 计数解压的单元 | uncompress* 的功能模型(Uncompress2)让输入长度、输出长度和数据范围保持分离 |
与数据别名或与另一个单元别名的单元,在这些模型之外。 |
| 压缩器的数据关系 | Compress2 用一个粗粒度的拒绝标志来描述数据;Compress2Z 和 Compress2Wrapper 表达指针的形态、错误的先后顺序和长度的写回 |
只关于数据模型的定理,对入口函数什么都没说。 |
| 上界的算术 | 在 LP64 上两个长度都是 64 位 | Goal.compress_bound_value 覆盖每个 UInt64。它陈述的是数值公式;这个上界足以容纳输出,是另一个命题。其他 ABI 需要关于大小转换的命题。 |
| deflate 字典的顺序 | 模型 DeflSetDict 的 zlib 分支在 started 之后拒绝字典 |
C 可以在流结束之后接受字典。deflate_valid 是关于模型的定理,不是关于这些 C 执行的定理。 |
| 字节格式中的预设字典 | 格式关系用一份初始的预设字典来解释一个普通的流 | 没有描述:解码开始之后替换裸流的字典对窗口的影响;这个功能命题不在计划内。这类历史的安全性已经证明:Goal.inflate_sequence_safety 覆盖任何位置上的 inflateSetDictionary。 |
| 位预置、头部和恢复 | 这些函数各有自己的功能目标 | 没有功能目标描述它们在一段历史中的每种组合。 |
| 快速解码辅助函数 | 关于 inflate_fast 的引理假设:输入和输出是原始字节块(不同的块,或同一块中不相交的范围),窗口所在的块不是输出块,有六个输入字节、258 个输出字节,进入时的比特数小于八,并且处于 sane 模式 |
这些是内部引理的前提,由公开目标的证明来确立。它们不限制公开的 inflate 目标。 |
| 窗口参数被接受时的 inflate 初始化 | 引理 inflate_init2_valid_public 假设 windowBits 被接受:Api.inflWbits wb.toInt = some (wrap, bits) |
Goal.inflateInit2_ 没有这个前提:它的定理 inflate_init2_public 覆盖每个 windowBits,对被接受的取值使用这条引理。 |
| Gz 文件数据 | 功能性的 gz 契约(FileData、CloseContract、GzWriterFormat、读写的值),以及目标 Goal.gzoffset64、Goal.gzoffset 和 Goal.gzrewind,都是针对“每个系统调用都按普通文件行事”的世界(RegularOs)陈述的 |
预言的 lseek 可以返回而不移动描述符,某些 Linux 设备就是这样;在那里,偏移值和倒回的结果不成立。这三个函数在每个世界上的安全性是 Goal.gz_sequence_safety 的一部分,该目标没有 RegularOs 前提。没有表示:权限、父目录、链接、属主和加锁;它们对每次调用的影响由预言的失败来涵盖。 |
中间 deflate 定理的前提,以及局部的打开、关闭和位预置引理的前提,收窄的是引理,从不是公开目标。