从 C 到内核检查过的定理
本项目的定理说的是一个 Lean 程序,不是 C 的文本。本页展示这个程序由什么构成,让读者能够判断内核不检查的两个联系:运行时表示了 C 的操作,翻译与选定的 C 源码一致。可信基础列出所有依靠审查的东西。
各层
flowchart TD
C["固定版本的 zlib 源码 + 按顺序应用的补丁"] --> T["逐语句翻译"]
R["运行时:对象、指针、算术、故障、循环"] --> T
T --> P["执行证明:无故障、终止、帧性质、所有权"]
T --> F["细化证明"]
M["不涉及堆的算法模型和 API 模型"] --> F
S["独立的格式规格"] --> M
S --> F
P --> A["公开调用与合法的调用序列"]
F --> A
| 层 | 它的职责 | 它的依据 |
|---|---|---|
| 选定的 C | 确定被验证的是哪个程序 | 固定版本的上游 zlib 源码,加上按文件名顺序应用的本项目补丁 |
| 运行时 | 给翻译后的操作以可执行的语义 | 审查和差分测试 |
| 翻译 | 保留 C 的语句及其顺序 | 源码审查和差分测试;测试是证据,不是证明 |
| 模型与规格 | 说明程序做什么,而不限定它的实现方式 | 审查各个定义、定义域,以及它们与 zlib.h 和数据格式的关系 |
| 证明 | 把计算与这些命题联系起来 | Lean 内核的检查 |
安全结论只需要经过执行证明的那条路径:无故障、终止、帧性质和所有权,并在调用序列上组合。经过细化证明的路径给出功能正确性。
有一项关于翻译后的 C 的功能结果经由这条路径得到证明:默认 zlib 流的往返。它的目标说的是翻译后函数的运行:一次从默认级别的 deflateInit_ 开始的 deflate 运行,和一次从 inflateInit_ 开始的 inflate 运行。同一次运行的两次调用之间,调用者可以改动缓冲区字段(Rebuffer),所以缓冲区可以按任意方式分成片段。Goal.stream_roundtrip_total 说的是:有输出空间并拿到其余数据时,两次运行都到达 Z_STREAM_END,解码器写出的就是编码器消耗的字节。Goal.compress_uncompress_roundtrip 说的是 uncompress(compress(x)) = x。往返一页给出这些目标及其前提。其他一些细化结果也有定理;哪些功能结果在计划内,见进度。
用几个定义看模型
每个翻译后的函数都由下面这些定义搭成。它们引自运行时,略去了 deriving 行。
/-- Why a C computation did not produce a value. -/
inductive Fault where
/-- undefined behaviour, with a short reason -/
| ub (what : String)
/-- a loop used up its fuel (a termination theorem rules this out) -/
| outOfFuel
/-- A C computation: the heap in, a value and the heap out, or a fault. -/
def M (α : Type) : Type := Heap → Except Fault (α × Heap)
/-- Loop fuel. Large enough that no zlib loop over in-memory data can exhaust it. -/
def fuel : Nat := 2 ^ 64
/-- `while (cond) body` over the loop-carried locals `σ`. The condition may update them (`while (len--)`):
its update happens on every evaluation, including the last, false one, as in C. -/
def cwhile {σ : Type} (cond : σ → M (Bool × σ)) (body : σ → M σ) (s : σ) : M σ :=
go fuel s
where
go : Nat → σ → M σ
| 0, _ => fun _ => .error .outOfFuel
| n + 1, s => do
let (c, s) ← cond s
if c then go n (← body s) else pure s
怎样读这些定义:
- 返回类型为
T的 C 函数,翻译后的 Lean 类型是M T:给它一个堆,它返回.ok (value, new heap)或.error fault。没有别的结果。 Fault.ub是模型里的未定义行为。凡是 C 操作未定义的地方,运行时的对应操作就返回它:读到对象之外、有符号溢出、重复释放。Fault.outOfFuel不是 C 的行为。cwhile至多检验条件2^64次;如果最后一次检验时条件仍为真,这次运行以Fault.outOfFuel结束。循环绝不会因为燃料用完而悄悄退出。终止证明表明这个故障不会发生。cdoWhile对do … while也是这样。- 安全定理的形状是:“对每个满足前提的堆,这次运行是
.ok,并且新堆与旧堆的差别只限于定理写明的那些”。
指向数组内部的指针没有地址:
/-- A pointer into an array: null, or the array (`R` says where it lives: a heap block, an array inside a
struct, a static table) and an index. There is no address. One past the end is a valid pointer. -/
inductive Ptr (R : Type) where
| null
| ref (r : R) (off : Nat)
通过这种指针的读取是带检查的(Space.get h r 是 r 在堆 h 中所指的数组,前提是它还存活):
/-- `*p`. Faults if `p` is null, dangling, or outside its array (one past the end is not readable). -/
def Ptr.load (p : Ptr R) : M T := fun h =>
match p with
| .null => .error (.ub "null dereference")
| .ref r off =>
match Space.get h r with
| none => .error (.ub "read through a dangling pointer")
| some a => if hk : off < a.size then .ok (a[off], h) else .error (.ub "read outside its object")
所以越界读取、通过 NULL 的读取和 free 之后的读取,都是 Fault.ub。一个说“这次运行是 .ok”的定理把这三种情况都排除了。Ptr.store、Ptr.add(指针算术)、Ptr.diff 和 Ptr.lt 形式相同。字节指针是 BPtr;load8、index8 和 store8 是翻译中使用的字节版本。指向结构体的指针,要么是表示 NULL 的 none,要么是对该结构体的表中某一项的引用。
翻译把一个 C 函数与它的 Lean 文本并排列出,并逐行解读。
选定的源码与开发的各个部分
目标是默认的 x86_64 Linux 静态构建,使用 LP64 位宽和默认分配器。分配失败在范围内。其他构建配置和自定义分配器实现不在涵盖范围内;偏离记录记有这一限制。上游源码绝不改动。只有针对已确认的上游缺陷才允许打补丁;补丁登记表列出各个补丁。
整个开发有四个部分:
- 运行时:堆、指针、故障、循环,以及建模的 C 库操作;
- 翻译:每个 C 文件对应一个 Lean 文件,
zlib/X.c对应X.c.lean,zlib/X.h对应X.h.lean。deflate.c拆成deflate_base.c.lean、deflate_strategies.c.lean和deflate.c.lean三个文件。翻译里没有证明。gz 翻译还使用gzfs.lean,即文件、errno和格式化的模型(外部 I/O); - 规格:必需的安全目标;功能目标,连同不涉及堆的格式模型和 API 模型,它们不是安全结论所必需的;以及两类目标共用的定义(调用、历史、帧、参数、不变量);
- 证明,以及各证明共用的、不涉及堆的数学事实。
关于内部函数的命题,先对翻译后的函数证明,调用者才使用它(见下文)。
函数名就是 C 的名字。函数的文档字符串以它的 C 签名开头。
可信语义在哪里
本节中的一切都是被信任的:这里的错误内核发现不了。
运行时定义了:
- 堆的各张表、指针类型
Ptr、函数指针,以及未初始化整数的值; Fault、M、fuel、cwhile和cdoWhile;- 指针算术、读取、写入、相减和比较;
- 字节指针地址的低三位,CRC 的对齐检验要读它;
malloc、free、memcpy、memmove、memset、strlen、字符串字面量和strerror的文本;- 每个结构体的记录、引用类型、静态表和堆,以及每种结构体的读取、写入、
malloc、free和整记录memcpy。这些定义根据 C 头文件生成;运行时结构定义列出每个字段。
有些语义辅助定义不属于运行时。它们定义在使用它们的翻译文件中,被信任的方式相同。下面各表按种类列出它们。
这些表收入翻译文件中每个顶层的 def、abbrev、structure 和 inductive(这些文件里没有 instance、macro 或 notation),但下面几类除外:某个 C 函数的翻译,某个 C 函数的一部分(循环体、循环条件、switch 的一个 case)的翻译,C 宏、C 常量或 C 表的翻译,以及只把某个函数的局部变量或参数归在一起的记录。出现在两个文件里的同一个名字,在两个文件里各自定义;这些定义并不共用。
带检查的算术和移位。 C 未定义的结果就是 Fault.ub。
| 文件 | 辅助定义 | C 语义 |
|---|---|---|
inflate.c.lean |
chkI32、chkI64 |
放不下的 int 或 long 结果是故障 |
deflate_base.c.lean |
chk32、chk64、iadd、isub、ineg、ladd、lsub |
同上,加上 int 和 long 的 +、- 和一元 - |
inftrees.c.lean |
chk32 |
同上,用于 int |
inffast.c.lean |
chk64 |
同上,用于 long |
trees.c.lean |
ck、iadd、isub |
同上,用于 int |
gzguts.h.lean |
i64chk、i64add、i64sub、i64neg |
同上,用于 z_off64_t |
inflate.c.lean |
shl32、shr32、shl64、shr64 |
unsigned 或 unsigned long 的移位:计数不小于位宽是故障 |
inftrees.c.lean |
shl32、shr32、shl1i32 |
同上,用于 unsigned;int 的 1 << n 从 n = 31 起是故障 |
inffast.c.lean |
shl32、shl64、shr64 |
同上,用于 unsigned 和 unsigned long |
crc32.c.lean |
shr64 |
同上,用于 unsigned long |
deflate_base.c.lean |
ishl、ushl |
int 的 a << n(计数在 0..31 内,a 不为负,结果放得下)和 unsigned 的 a << n |
trees.c.lean |
shl1、shlUs、shrUs |
int 的 x << 1;作为 int 移位、计数在 0..31 内的 (ush)val << c 和 (ush)val >> c |
整数转换。
| 文件 | 辅助定义 | C 语义 |
|---|---|---|
inflate.c.lean |
u2i、i2u、i2ul |
(int)u、(unsigned)i、(unsigned long)i:按位宽取模,最后一个先作符号扩展 |
trees.c.lean |
u16i、u8i、i2u、u2i、i2ul、i2us |
ush 和 uch 转为 int;int 转为 unsigned、unsigned long 和 ush;unsigned 转为 int |
gzguts.h.lean |
u32ToI64 |
对 unsigned 的 (z_off64_t)u |
循环和控制流。 它们都建立在 cwhile 和 cdoWhile 之上,燃料相同。
| 文件 | 辅助定义 | C 语义 |
|---|---|---|
inflate.c.lean(infback.c.lean 也使用) |
模式单子 X,退出方式 Ex 和 Stop,循环 xwhileBrk、xwhile、xdoWhile、xloopBrk;IL.init |
把 inflate 的局部变量作为状态;大 switch 内部的 break、goto inf_leave 和 return。IL.init 是这些局部变量在第一次赋值之前的值:零和 NULL,而其中一些在 C 里没有初始化 |
gzfs.lean |
单子 G,gub、gwhile、gdoWhile |
同时携带文件系统世界的计算;其中的故障和两种循环 |
trees.c.lean |
cfor |
for (init; cond; step) body;continue 就是循环体的末尾 |
deflate_strategies.c.lean |
forever |
for (;;) 的条件:一直继续,直到 break 或 return |
指针、字段和表下标。
| 文件 | 辅助定义 | C 语义 |
|---|---|---|
deflate_base.c.lean |
rd、wr、zrd、zwr;padd、psub、store_at、freq_inc;config_at |
s->f 和 strm->f 作为一次读取,字段写入作为读取、记录更新、写回;p + n、p - n、p[i] = v、tree[i].Freq++;configuration_table[level],下标在 0..9 之外是故障 |
inflate.c.lean |
rdS、wrS、rdZ、wrZ、setMode;lensP、workP、codesP;orderAt |
对 *state 和 *strm 的字段访问;指向数组字段 lens、work、codes 的指针;order[i],下标在数组之外是故障 |
inffast.c.lean |
subn |
计数为 unsigned 的 p - n |
inftrees.c.lean |
geta、seta、storeCode |
局部数组的 a[i] 和 a[i] = v,下标在数组之外是故障;code 指针的 p[i] = v |
trees.c.lean |
sid、rd、md;pLtree、pDtree、pBltree、pHeap、pDepth、pBlCount、pLdesc、pDdesc、pBldesc;setAt、heapAt、heapSet、getFc、getDl、setFc、setDl、blOrder |
对 *s 的字段访问;指向 deflate 状态内部各数组和树描述符的指针;对这些数组和 bl_order 的元素读写 |
gzguts.h.lean |
castState、castFile、strmOf;ldS、updS、updX、ldZ、updZ |
(gz_statep)file、(gzFile)state、&(state->strm);对 gz 状态、state->x 和流的字段访问 |
crc32.c.lean |
crcTab、x2nTab、idx1、idx2、wordAt |
对 CRC 各表取下标,下标在表之外是故障;words[i] |
deflate.c.lean |
Z_NULL_strm |
类型为 z_streamp 的 Z_NULL |
把标量单元当作字节,以及 CRC 的地址和字读取。
| 文件 | 辅助定义 | C 语义 |
|---|---|---|
gzguts.h.lean |
load32、store32、load64、store64 |
字节块上的 *(int *)p 和 *(uint64_t *)p,小端 |
crc32.c.lean |
addrOf |
(z_size_t)buf,只知道它的低三位 |
crc32.c.lean |
loadWord |
把字节缓冲区看作 z_word_t 时的 words[i]:八个字节,小端 |
分配器分派和自动存储。
| 文件 | 辅助定义 | C 语义 |
|---|---|---|
inflate.c.lean |
ZALLOCB、ZALLOCS、ZFREEB、ZFREES |
经由 strm->zalloc 和 strm->zfree 的 ZALLOC 和 ZFREE:默认函数照常运行,任何其他函数指针是故障 |
deflate_base.c.lean |
zalloc_default、zfree_default、ZALLOC_bytes、ZALLOC_words、ZFREE_bytes、ZFREE_words |
同上,用于 deflate 一侧的字节块和 16 位字的块 |
deflate_base.c.lean |
CompressFunc |
函数指针 config.func,表示为各个局部压缩函数的枚举 |
inflate.c.lean、gzguts.h.lean |
allocLocalB、allocLocal |
局部数组:一个新分配的可写块,内容任意,不经过分配失败预言 |
compress.c.lean、uncompr.c.lean |
allocLocalZ |
局部 z_stream,不经过预言 |
字符串字面量、静态数据和库函数的替身。
| 文件 | 辅助定义 | C 语义 |
|---|---|---|
zutil.c.lean、gzfs.lean |
strLit |
字符串字面量:指向源码字面量只读表的指针 |
inflate.c.lean |
setMsg |
strm->msg = "..." |
gzfs.lean |
strerrorText、libcStr、zstrerror |
strerror(errno):一段借用的只读文本 |
crc32.c.lean、inftrees.c.lean、trees.c.lean |
initStatics(前两个文件各一个);trees_statics、install_trees |
该文件各静态表的内容,放进堆的 Statics |
gzguts.h.lean |
memchrB |
memchr |
gzfs.lean |
cstring、storeBytes、loadBytes、heapStr |
以 NUL 结尾的字符串的各字节;字节的整块写入和整块读取 |
gzfs.lean |
snprintf、vsnprintf、formatBytes,以及它们的组成部分 VaArg、Spec、isDigit、readNumGo、readNum、parseFlags、parseSpec、natDigits、pad、fmtInt、argStr、formatGo |
格式化器(外部 I/O) |
操作系统和回调。
| 文件 | 辅助定义 | C 语义 |
|---|---|---|
gzfs.lean |
Fs、OFile、Node;ReadChoice、WriteChoice、LseekChoice;fsOpen、fsRead、fsWrite、fsLseek、fsClose、fsFcntl,以及普通文件部分 fsOpenReg、fsReadReg、fsWriteReg、fsLseekReg、fsCloseReg;lowestFd、findName、tickW、okErrW、failErrno、readCap、debitW、relocateW |
文件系统、描述符表,以及系统调用 open、read、write、lseek、close、fcntl,连同选择其结果的预言(外部 I/O) |
gzfs.lean |
getErrno、setErrno、BLOCKED,各个 errno 值(ENOENT 等),open 的各个标志(O_WRONLY 等),以及 SEEK_SET、SEEK_CUR、SEEK_END |
errno,以及这些常量在 Linux x86_64 上的值 |
gzfs.lean |
Fs.put、Fs.mkdir、Fs.get?、Fs.posOf? |
不是 C 操作:它们为命题和测试构造并查看一个文件系统 |
infback.c.lean |
InCb、OutCb |
inflateBack 的回调 in_func 和 out_func 的类型。回调是一个 Lean 函数 |
可信基础指出了运行时和 gz 文件世界。对其他翻译文件里的辅助定义,它的第 3 项引用上面这些表。
每个翻译文件都在文件头注释里写明它的预处理选择和建模决定。
为什么用对象堆
C 的结构体用 Lean 的记录表示。一个堆(Heap)有十五个字段:
bytes:字节块的表(unsigned char数组:缓冲区、窗口、字符串);words:16 位字的块的表(head、prev);ro:字节块只读标志的表;streams、gzheaders、dstates、istates、gzstates:每种结构体各一张表,分别用于z_stream、gz_header、deflate_state、inflate_state和gz_state;static:静态表;- 分配状态:
nextBlk是下一个未用的块编号;nalloc是到目前为止的分配调用次数;allocOk是失败预言(allocOk n说明第n次调用是否成功);garbage是新分配的内存的内容; byteBase:每个静态字节数组或内嵌字节数组起点地址的低三位。CRC 的对齐检验读它们;libcErrorBorrow:当前借出的是哪一段strerror文本,用一个计数器和一个errno值表示,或者没有借出。它不是堆上的对象。
其他数组是记录的字段或静态表。一个指针指明一个堆块、一个记录内的数组或一个静态数组,再加上元素下标。
flowchart LR
P["指针:NULL,或引用 + 下标"] --> B["堆上的字节块/字块"]
P --> E["嵌在记录里的数组"]
P --> S["静态数组"]
H["堆"] --> B
H --> K["记录表:流、inflate 状态、deflate 状态……"]
K --> E
H --> O["分配预言、新块计数器、垃圾值"]
这样,字段更新和帧性质都很直接。记录的字段是一个投影;改它就是一次记录更新。一次字节写入改不了另一张表里的记录。复制整个记录也复制它内嵌的数组。
这种表示没有 ABI 字节偏移。所以它给不出结构体的字节视图,也表示不了标量单元与缓冲区之间的每一种别名。记录类型不强制数组字段的长度:WellFormed、Heap.RecordsWellFormed 和 Statics.WellFormed 陈述这些长度,证明要么带着它们,要么从自己的表示不变量推出它们。
执行与故障
| 操作 | 表示出来的行为 |
|---|---|
| 指针算术 | 留在同一个存活数组之内,包括它的末尾后一位;解引用末尾后一位会发生故障 |
| 读取和写入 | 检查存活性和边界;写入还检查只读状态 |
| 指针相减和比较大小 | 要求同一个存活数组和有效的偏移;差值必须能放进 ptrdiff_t |
| 指针相等 | 结构相等;不同的引用构造子比较结果为不相等 |
| 无符号算术 | 按 C 的位宽回绕 |
| 有符号算术和移位 | 由上面各表中的辅助定义检查,它们在翻译文件里。符合规范化 4的有符号运算,以及按字面量计数的移位(翻译,形式 4),用普通运算符 |
| 复制和填充 | 检查范围和可写性;memcpy 还检查不重叠 |
| 分配 | malloc 询问失败预言,并拒绝 2^63 字节或更大的请求;成功时给出一个新的块编号。在不满足 Fresh 的堆上它发生故障 |
| 释放 | 接受 NULL;否则要求是一个存活可写块的起始位置 |
| 循环 | 至多检验条件 2^64 次;耗尽是故障,绝不是普通的退出 |
安全性的定义说明定理对这些结果断言了什么。
模型与 C 不同的地方
这些是模型的限制,不是对 C 额外的断言。权威的细节在可信基础和偏离记录里。
| 差别 | 对证明的后果 |
|---|---|
| 新分配的整数单元取任意值 | 定理对每个 garbage 函数量化;绝不假设它为零 |
| 每个新分配的单元在一次运行中始终保持同一个值 | 证明不依赖重复的未初始化读取结果一致 |
| 新分配的指针字段是 NULL | 指针字段漏写一次,在模型里看不出来;单凭一次与 NULL 的比较,也表明不了字段已被写过。C 对每个指针字段都是先写后读,这一点尚未确认,须由源码审查确认:没有定理陈述它,在这个模型里也不可能有。证明表明的要窄一些:每种状态的不变量(InflateInv、DInv、GzInv)在每个可达的流上、在每个有历史的 gz 句柄上成立,而不变量说明了它提到的那些指针字段里是什么(可信基础) |
给任何指针值加零都成功,空指针和悬空指针也一样;NULL - NULL 是 0 |
“不出故障”的定理并不说明 C 避开了这些操作。被验证的源码到达它们的地方已列出(模型的限制) |
| 相等比较没有相邻对象地址的情形 | 没有哪个 C 分支是靠来自不同对象的指针相等来论证的 |
| 没有一般的地址、对齐或类型标签 | 类型转换和对地址敏感的路径逐一明确审查;结构体没有一般的字节视图 |
| CRC 观察地址的低位 | 堆字节块的起点是对齐的;静态字节数组和内嵌字节数组的起点余数任意但稳定。一般的 ABI 布局,以及按严格别名规则对那处字转换的解读,都在模型之外 |
| 只读状态覆盖字节块和静态对象 | 堆记录或字块在模型里从不只读 |
| 块编号从不重用 | 做分配的代码带着 Fresh;初始堆中各对象的身份互不相同 |
| 库的复制操作按元素计数 | C 的字节数要换算;整记录的 memcpy 使用检查重叠的记录复制 |
自动存储保持它的 C 生命周期,不消耗分配失败的序号。地址被传给某次调用的局部对象是一个表示出来的对象,在每个返回处被释放。没有哪个证明靠悄悄收窄公开定义域来弥补表示上的缺口。
设计决定
下表给出每个决定及其后果。
| 决定 | 后果 | |
|---|---|---|
| 1 | 对象堆,每种记录一张表 | 表示出来的操作依靠审查;记录与字节缓冲区之间的别名无法表达 |
| 2 | 证明自动化是局部的 | 每个生成的证明项都由内核检查;不用任何被假定正确的验证条件生成器来代替证明 |
| 3 | C 由人工逐语句翻译 | 对应关系依靠审查;差分测试是证据 |
| 4 | 压缩器中相互重叠的待输出存储和符号存储按 C 的方式建模 | 它的生命周期和不被覆盖的条件,对每个允许的内存级别都作了证明(trees) |
| 5 | 新分配的整数单元取任意值,新分配的指针是 NULL | 定理对整数垃圾值量化;指针字段漏写一次,在模型里看不出来(见上文) |
| 6 | 记录没有 ABI 字节布局 | 记录的字节视图,以及标量与缓冲区之间的别名,都在模型之外 |
组合调用而不假设其结果
辅助函数的定理说的是翻译后的辅助函数本身。它的调用者先证明该辅助函数的前置条件,再使用这条定理。辅助函数的契约都不是用来代替执行的假设。内部义务列出调用者要建立的条件。
每种状态记录有一个表示不变量,它带着边界、所有权和后续调用需要的历史。初始化函数建立它,后续调用保持它,结束函数释放所拥有的存储。因为初始化函数建立了它,这个不变量是能够成立的。序列定理把这些函数定理组合起来,包括拒绝和分配失败的情形。方法见证明指南。