按函数查覆盖情况
本页回答一个问题:zlib.h 的函数 X 的安全性是由哪条定理证明的,定义域是什么?每个有文档的函数占一行。每行写明安全目标,以及类型恰好就是该目标的定理。另有一列写明该函数的功能目标,以及它完成时的定理;安全结论不依赖未完成的功能目标。
- 完成。 本页提到的每个安全目标都已完成:目标构建中每个有文档的函数,都在其所在行写明的定义域上有一条安全定理。
- 所作假设。 可信基础的六项,以及偏离记录中的前提;“定义域”一列指向的就是这些前提。
- 比
zlib.h更窄。 某一行的定义域比zlib.h要求得更多时,该行或比zlib.h更窄的定义域一节会写明,相应的前提见偏离记录。
进度页列出每项结论及其状态。
怎样读一行
- 安全目标与定理。 所有目标都在命名空间
ZlibF.Spec.Public中,这里写作Goal.…。除非该行另写了名字,定理与它的目标同名;每张表前面的那一行给出定理的命名空间。 - 定义域。 目标在“流可达”之外还要求什么。“无”表示对参数没有前提。有三条前提是每个流函数行和实用函数行共有的,不再重复:默认分配器、良构的模型堆,以及字节对象小于
2^63字节(偏离记录)。 NULL流或不一致的流。 对NULL流,或对zlib.h称为不一致的记录的调用,是一次拒绝。除四个初始化函数之外,每个流函数的安全目标在针对可达流的子句之外,都有一个针对它的子句。这一列写的是该子句陈述的内容:返回的值,以及堆的变化。该子句的定义域是RefusedInflate或RefusedDeflate(偏离记录,注 2):在zalloc和zfree已设置时,它不包括悬空的、属于另一种流的或垃圾的状态指针。这一列写有“Goal.inflate_refusal也陈述”或“Goal.deflate_refusal也陈述”的地方,是说那个目标把同一个拒绝又陈述了一遍;它的定理是ZlibF.Spec.Public.RefusalProof.inflate_refusal或ZlibF.Spec.Public.RefusalProof.Deflate.deflate_refusal。- 序列目标。 除初始化、End 和 Copy 之外,每个流调用除了自己的目标,还是所属那一类流的序列目标中的一种调用,所以它在任何历史的任何位置上也被覆盖:
Goal.inflate_sequence_safety:定理Zlib.Inflate.Proofs.inflate_sequence_safety_public;Goal.deflate_sequence_safety:定理Zlib.Deflate.Universal.deflate_sequence_safety。
End 调用是序列目标的第 3 个子句。一次成功的初始化或复制开启一段历史。
Inflate 流
“安全目标”一列的定理:ZlibF.Spec.Public.StreamCallSafetyProof.<名字>,除非该行另写了名字。两条初始化定理是 ZlibF.Spec.Public.InitSafetyProof.<名字>。
| 函数 | 安全目标(定理同名) | 定义域 | NULL 流或不一致的流 |
功能目标,以及它完成时的定理 |
|---|---|---|---|---|
inflateInit_(宏 inflateInit) |
Goal.inflateInit__safety |
zlib.h 允许的每次调用(InitArguments):strm 为 NULL 或使用默认分配器的记录;任意的 state、版本字节和 stream_size;每一种分配结果 |
在目标之内 | Goal.inflateInit_:init15_public |
inflateInit2_(宏 inflateInit2) |
Goal.inflateInit2__safety |
同上,并对每个 windowBits |
在目标之内 | Goal.inflateInit2_:inflate_init2_public |
inflate |
Goal.inflate_safety |
StreamBuffers 与 ActiveHeader |
在目标之内:Z_STREAM_ERROR;在满足 Fresh 的堆上,不写原先存活的任何块,存活的块保持原样;Goal.inflate_refusal 也陈述 |
Goal.inflate:Zlib.Inflate.Proofs.inflate_public |
inflateEnd |
Goal.inflateEnd_safety |
无 | 在目标之内:Z_STREAM_ERROR,堆不变;Goal.inflate_refusal 也陈述 |
Goal.inflateEnd:inflate_end_public |
inflateSetDictionary |
Goal.inflateSetDictionary_safety |
字典缓冲区(CallerRange) |
在目标之内:Z_STREAM_ERROR,堆不变;Goal.inflate_refusal 也陈述 |
Goal.inflateSetDictionary:inflateSetDictionary_public |
inflateGetDictionary |
Goal.inflateGetDictionary_safety |
目的缓冲区(CallerRange)。结果单元 *dictLength 在模型中是一个值(见说明) |
在目标之内:Z_STREAM_ERROR,长度值按传入时的值原样返回,堆不变;Goal.inflate_refusal 也陈述 |
Goal.inflateGetDictionary:inflate_getdict_public |
inflateSync |
Goal.inflateSync_safety |
输入范围 | 在目标之内:Z_STREAM_ERROR;在满足 Fresh 的堆上,不写原先存活的任何块,存活的块保持原样 |
Goal.inflateSync:未完成,不在计划内 |
inflateCopy |
Goal.inflateCopy_safety:ZlibF.Spec.Public.InflateCopySafetyProof.inflateCopy_safety |
source ≠ dest;目的流是一个可读的记录 |
在目标之内。dest 为 NULL:Z_STREAM_ERROR,堆不变。source 为 NULL,或源记录属于 RefusedInflate,而 dest 记录可读:Z_STREAM_ERROR,且只把 dest->state 置为 NULL。对被拒绝的源,Goal.inflate_refusal 也陈述 |
Goal.inflateCopy:inflate_copy_public |
inflateReset |
Goal.inflateReset_safety |
无 | 在目标之内:Z_STREAM_ERROR,堆不变;Goal.inflate_refusal 也陈述 |
Goal.inflateReset:reset_public |
inflateReset2 |
Goal.inflateReset2_safety |
无;每个 windowBits |
在目标之内:Z_STREAM_ERROR,堆不变;Goal.inflate_refusal 也陈述 |
Goal.inflateReset2:reset2_public |
inflatePrime |
Goal.inflatePrime_safety |
无 | 在目标之内:Z_STREAM_ERROR,堆不变 |
Goal.inflatePrime:prime_public |
inflateMark |
Goal.inflateMark_safety |
无 | 在目标之内:-65536,堆不变 |
Goal.inflateMark:mark_public |
inflateGetHeader |
Goal.inflateGetHeader_safety |
head 不是 NULL;头部缓冲区(HeaderMemory) |
在目标之内:Z_STREAM_ERROR,堆不变 |
Goal.inflateGetHeader:getheader_public |
Deflate 流
“安全目标”一列的定理:ZlibF.Spec.Public.StreamCallSafetyProof.<名字>;两个初始化函数则是 ZlibF.Spec.Public.InitSafetyProof.<名字>;该行另写了名字时以该行为准。
| 函数 | 安全目标(定理同名) | 定义域 | NULL 流或不一致的流 |
功能目标,以及它完成时的定理 |
|---|---|---|---|---|
deflateInit_(宏 deflateInit) |
Goal.deflateInit__safety |
zlib.h 允许的每次调用(InitArguments),每个压缩级别 |
在目标之内 | Goal.deflateInit_:deflateInit_proof |
deflateInit2_(宏 deflateInit2) |
Goal.deflateInit2__safety |
同上,并对每个方法、windowBits、memLevel 和策略 |
在目标之内 | Goal.deflateInit2_:deflateInit2_proof |
deflate |
Goal.deflate_safety |
StreamBuffers 与 ActiveHeader |
在目标之内:Z_STREAM_ERROR,堆不变;Goal.deflate_refusal 也陈述 |
Goal.deflate:Zlib.Deflate.Universal.deflate_safety |
deflateEnd |
Goal.deflateEnd_safety |
无 | 在目标之内:Z_STREAM_ERROR,堆不变 |
Goal.deflateEnd:deflate_end_public |
deflateSetDictionary |
Goal.deflateSetDictionary_safety |
字典缓冲区(CallerRange) |
在目标之内:Z_STREAM_ERROR,堆不变;Goal.deflate_refusal 也陈述 |
Goal.deflateSetDictionary:未完成,不在计划内 |
deflateGetDictionary |
Goal.deflateGetDictionary_safety |
目的缓冲区(CallerRange)。结果单元 *dictLength 在模型中是一个值(见说明) |
在目标之内:Z_STREAM_ERROR,不存入长度,堆不变;Goal.deflate_refusal 也陈述 |
Goal.deflateGetDictionary:deflate_getdict_public |
deflateCopy |
Goal.deflateCopy_safety:Zlib.Deflate.Universal.deflate_copy_safety |
source ≠ dest;目的流是一个可读的记录 |
在目标之内。dest 为 NULL:Z_STREAM_ERROR,堆不变。source 为 NULL,或源记录属于 RefusedDeflate,而 dest 记录可读:Z_STREAM_ERROR,且只把 dest->state 置为 NULL。对被拒绝的源,Goal.deflate_refusal 也陈述 |
Goal.deflateCopy:deflate_copy_public |
deflateReset |
Goal.deflateReset_safety |
无 | 在目标之内:Z_STREAM_ERROR,堆不变 |
Goal.deflateReset:deflate_reset_public |
deflateParams |
Goal.deflateParams_safety |
StreamBuffers 与 ActiveHeader |
在目标之内:Z_STREAM_ERROR,堆不变;Goal.deflate_refusal 也陈述 |
Goal.deflateParams:未完成,不在计划内 |
deflateTune |
Goal.deflateTune_safety |
无 | 在目标之内:Z_STREAM_ERROR,堆不变 |
Goal.deflateTune:tune_public |
deflateBound |
Goal.deflateBound_safety |
ActiveHeader 与 DeflateHeaderLive |
在目标之内:返回对 NULL 流调用时返回的值(是上界,不是错误值),堆不变 |
Goal.deflateBound:未完成,不在计划内 |
deflateBound_z |
Goal.deflateBound_z_safety |
ActiveHeader 与 DeflateHeaderLive |
在目标之内:返回对 NULL 流调用时返回的值(是上界,不是错误值),堆不变 |
Goal.deflateBound_z:未完成,不在计划内 |
deflatePending |
Goal.deflatePending_safety |
无。结果单元 *pending 和 *bits 在模型中是值(见说明) |
在目标之内:Z_STREAM_ERROR,两个计数都不存入,堆不变 |
Goal.deflatePending:pending_public |
deflateUsed |
Goal.deflateUsed_safety |
无。结果单元 *bits 在模型中是一个值(见说明) |
在目标之内:Z_STREAM_ERROR,不存入计数,堆不变 |
Goal.deflateUsed:used_public |
deflatePrime |
Goal.deflatePrime_safety |
在第一次 deflate 调用之前(DeflateNotStarted),这是 zlib.h 的规则 |
在目标之内:Z_STREAM_ERROR,堆不变 |
Goal.deflatePrime:未完成,不在计划内 |
deflateSetHeader |
Goal.deflateSetHeader_safety |
在第一次 deflate 调用之前;头部缓冲区(HeaderMemory) |
在目标之内:Z_STREAM_ERROR,堆不变 |
Goal.deflateSetHeader:header_public |
结果单元。 inflateGetDictionary、deflateGetDictionary、deflatePending 和 deflateUsed 通过指针写出结果。翻译把这样的指针当作值,而不是内存,所以这四个函数的安全目标对结果单元的内存什么都没说:既没说它可写,也没说它与其他区域分开。模型表示的是哪些调用,见偏离记录的“结果单元”一行。compress* 的长度单元也是如此(整缓冲区实用函数)。
回调解码器
“安全目标”一列的定理:ZlibF.Spec.Public.BackSafetyProof.<名字>。
| 函数 | 安全目标(定理同名) | 定义域 | NULL 流或不一致的流 |
功能目标,以及它完成时的定理 |
|---|---|---|---|---|
inflateBackInit_(宏 inflateBackInit) |
Goal.inflateBackInit__safety |
zlib.h 允许的每次调用(InitArguments),对每个 windowBits、stream_size 和 state;窗口非 NULL 且 windowBits 为 8 到 15 时,窗口有 2^windowBits 个可写字节;每一种分配结果 |
NULL 流在目标之内 |
Goal.inflateBackInit_:ZlibF.Spec.Public.InflateBackInitProof.back_init_public。它对每个 state 值说明错误的版本或大小、NULL 流、NULL 窗口、错误的 windowBits 和分配失败各返回哪个值。 |
inflateBack |
Goal.inflateBack_safety |
BackSafeReachable 的一段历史;inputBound < 2^48;窗口和每个输入片段都在堆字节块中;回调协议 |
在目标之内:NULL 流,以及状态为 NULL 的流记录 |
Goal.inflateBack:未完成,不在计划内 |
inflateBackEnd |
Goal.inflateBackEnd_safety |
BackSafeReachable 的一段历史;没有别的要求 |
在目标之内:NULL 流,以及状态或 zfree 为 NULL 的流记录 |
Goal.inflateBackEnd:ZlibF.Spec.Public.InflateBackEndProof.back_end_public |
- 序列目标。
Goal.inflate_back_sequence_safety:定理Zlib.Infback.Safety.inflate_back_sequence_safety。它多说一点:每段历史之后,调用者的窗口上都有一个有效的解码器状态。它的子句 1 和子句 3 是Goal.inflateBack_safety的第一个和第三个子句,它的子句 4 是Goal.inflateBackEnd_safety的第三个子句。历史从一次返回Z_OK的inflateBackInit_调用开始,调用之前state字段可以取任意值(BackInitArguments)。 - 非空性。
Goal.inflate_back_initialisation_domain:初始化可以成功。Goal.inflateBack_call_domain:定理ZlibF.Spec.Public.BackCallDomainProof.inflateBack_call_domain。它表明Goal.inflateBack_safety调用子句的每个前提在一个具体的历史和一个具体的回调协议上同时成立。
校验和与查询
“安全目标”一列的定理:ZlibF.Spec.Public.StatelessSafetyProof.<名字>。这些目标说的是:调用返回,并且堆保持不变。每个 CRC 目标,包括各组合目标,都有一条前提:模型中的两张 CRC 表就是该构建的表(CrcGlobals)。这是对模型的条件,不是对参数的条件(模型的限制),所以对参数没有前提的 CRC 行,“定义域”一列写“无”。
| 函数 | 安全目标(定理同名) | 定义域 | 功能目标,以及它完成时的定理 |
|---|---|---|---|
adler32 |
Goal.adler32_safety |
比 zlib.h 更窄:只有 len = 0 时 buf 才可以是 NULL(AdlerBufferBytes)。len = 1 时 C 会读 buf[0]。buf 为 NULL 且 len ≥ 2 在 C 中是安全的,但不被覆盖。 |
Goal.adler32:adler_public |
adler32_z |
Goal.adler32_z_safety |
与 adler32 相同 |
Goal.adler32_z:adler_z_public |
adler32_combine、adler32_combine64 |
Goal.adler32_combine_safety、Goal.adler32_combine64_safety |
无 | Goal.adler32_combine、Goal.adler32_combine64:combine_public、combine64_public |
crc32、crc32_z |
Goal.crc32_safety、Goal.crc32_z_safety |
buf 可读,或为 NULL(长度任意)(BufferBytes) |
Goal.crc32、Goal.crc32_z:crc32、crc32_z |
crc32_combine、crc32_combine64 |
Goal.crc32_combine_safety、Goal.crc32_combine64_safety |
无 | Goal.crc32_combine、Goal.crc32_combine64:combine、combine64 |
crc32_combine_gen、crc32_combine_gen64 |
Goal.crc32_combine_gen_safety、Goal.crc32_combine_gen64_safety |
无 | Goal.crc32_combine_gen、Goal.crc32_combine_gen64:gen、gen64 |
crc32_combine_op |
Goal.crc32_combine_op_safety |
op 来自 crc32_combine_gen 或 crc32_combine_gen64,这是 zlib.h 的规定 |
Goal.crc32_combine_op:op |
zlibVersion |
Goal.zlibVersion_safety |
无 | Goal.zlibVersion:zlibVersion |
zlibCompileFlags |
Goal.zlibCompileFlags_safety |
无 | Goal.zlibCompileFlags:zlibCompileFlags |
compressBound、compressBound_z |
Goal.compressBound、Goal.compressBound_z:ZlibF.Spec.Public.Proofs.compressBound、compressBound_z |
无 | 同样的两个目标。它们的翻译是纯函数,不涉及堆,也不会出故障,所以完整的契约同时充当两种目标。 |
整缓冲区实用函数
| 函数 | 安全目标与定理 | 定义域 | 功能目标,以及它完成时的定理 |
|---|---|---|---|
compress、compress_z、compress2、compress2_z |
Goal.compress_safety、Goal.compress_z_safety、Goal.compress2_safety、Goal.compress2_z_safety:ZlibF.Spec.Public.Proofs.Compress.<名字> |
源与目的缓冲区分离;长度单元在模型中是标量,所以与数据重叠的单元不被覆盖(偏离记录)。每个压缩级别。 | Goal.compress*:未完成,不在计划内 |
uncompress、uncompress_z、uncompress2、uncompress2_z |
Goal.uncompress_safe、Goal.uncompress_z_safe、Goal.uncompress2_safe、Goal.uncompress2_z_safe:ZlibF.Spec.Public.Proofs.Uncompress.<名字> |
数据与各长度单元两两分离(UtilitySeparation) |
Goal.uncompress*:未完成,不在计划内 |
Gzip 文件接口
31 个有文档的 gz 函数以及 gzvprintf,各有自己的安全目标 Goal.<function>_safety。定理与目标同名:ZlibF.Spec.Public.GzCallSafetyProof.<function>_safety。每个目标是序列目标的一个子句,限制到一个函数的调用上。接受句柄的函数,其目标还带有对 NULL 句柄的拒绝。
- 序列目标。
Goal.gz_sequence_safety:定理ZlibF.Spec.Public.Proofs.gz_sequence_safety_public。它的定义域是一个句柄在每个文件系统世界中的每段历史(GzHistory)。 - 非空性。
Goal.gz_sequence_nonvacuity:定理ZlibF.Spec.Public.Proofs.GzNonvacuity.gz_sequence_nonvacuity_public。 NULL句柄。Goal.gz_refusal:定理ZlibF.Spec.Public.GzRefusalProof.gz_refusal。接受句柄的 29 个 gz 函数(包括gzvprintf)各自返回文档规定的值,堆和世界都不变。三个打开函数不接受句柄。这 29 个函数各自的目标都重复了属于它的那个子句。
下表说明每个函数的目标限制的是序列目标的哪个子句。前提是偏离记录中 gz 的各行。
函数(各有自己的 Goal.<function>_safety) |
目标所限制的 Goal.gz_sequence_safety 的部分 |
说明 |
|---|---|---|
gzopen、gzopen64 |
打开子句(GzOpenSafe) |
每个路径、模式和世界,包括每一种失败 |
gzdopen |
打开子句(GzDopenSafe) |
每个 fd。功能目标 Goal.gzdopen 也已完成(Zlib.Gzlib.Proofs.gzdopen_complete)。 |
gzbuffer、gzeof、gzerror、gzclearerr、gztell、gztell64、gzoffset、gzoffset64、gzrewind、gzseek、gzseek64 |
调用子句;gzerror 还有关于它所返回字符串的子句 |
gzbuffer、gzeof、gzerror、gzclearerr、gzoffset、gzoffset64 和 gzrewind 的功能目标也已完成。 |
gzwrite、gzfwrite、gzputc、gzputs、gzprintf、gzvprintf、gzflush、gzsetparams |
调用子句 | gzprintf 和 gzvprintf:调用是 C 对其格式串和参数有定义的调用,没有 %n;没有前提陈述这一点,而模型不读取格式串(偏离记录,“Gz printf 调用”一行)。zlib.h 把 gzvprintf 列为未文档化;它仍然有安全目标,因为 gzprintf 经由它实现。 |
gzread、gzfread、gzgetc、gzgetc_、gzungetc、gzgets |
调用子句;终止需要 ReadsFinite。gzgetc 还有宏子句 |
在每个世界中都不出故障;读取预算小于 2^61 时正常返回 |
gzdirect |
调用子句 | 在每个世界中都终止 |
gzclose、gzclose_r、gzclose_w |
关闭子句 | 模式不对的关闭被拒绝,什么也不改变;否则释放拥有的每个块,并释放描述符 |
zlib.h 的 gzgetc() 宏(在 Goal.gzgetc_safety 中) |
宏子句,以及历史步骤 GzHistory.getcMacro |
有已缓冲的输出时走内联路径;x.have = 0 时调用函数,在 ReadsFinite 之下被覆盖。对 NULL 句柄使用这个宏在 C 中是未定义行为,不被覆盖。 |
| 同一描述符上的第二个句柄 | 世界步骤 GzHistory.world |
一次调用之后可以换成任何良构的世界,所以别的参与者可以关闭或重用这个描述符。 |
比 zlib.h 更窄的定义域
每一条在偏离记录中都有对应的行。
inflateBack:inputBound < 2^48;窗口和每个输入片段都在堆字节块中;两次调用之间调用者不写窗口。inflateCopy与deflateCopy:source ≠ dest。adler32与adler32_z:只有len = 0时buf才可以是NULL。inflate、deflate、deflateParams、compress*、uncompress*:调用者的各区域互不重叠。compress*、inflateGetDictionary、deflateGetDictionary、deflatePending、deflateUsed:结果单元在模型中是一个值,所以目标对它的内存什么都没说。- gz 的读取调用:终止需要读取预算。
- 每个流:默认分配器。