oss-proof:开源 C 库的形式化验证
用 Lean 4 对开源 C 库的逐语句翻译作机器检查的证明:公开函数在每条定理写明的前提下没有未定义行为、没有内存错误、没有泄漏,并且终止。
验证库与状态
每个结论只使用两种状态:完成(存在命题恰好等于目标的 Lean 定理且通过全部检查)或未完成。
默认 x86_64 Linux 构建下 zlib 1.4(含七个补丁)中每个有文档公开函数对任意输入与调用序列均已证明安全,并证明默认 zlib 流的往返性质。
- 有文档的公开函数
- 86 / 86
- 必需目标(已完成 / 总数)
- 113 / 113
- 在上游发现的真实缺陷
- 8
7-Zip × Lean
未完成针对官方 7-Zip 纯 C SDK(.7z 容器 DAG、BCJ2、PPMd7 内存池子分配器、LZMA/LZMA2)的 Lean 4 顶层安全不变量模型与严格 ISO C17 运行时基座;完整 C 翻译的安全性证明尚未完成。
- 有文档的公开函数
- —
- 已登记目标(已证 / 已列)
- 12 / 16
- 在上游发现的真实缺陷
- 0
针对 libarchive 中 RAR5 与 7-Zip 归档格式解码器的 Lean 4 顶层安全不变量模型与严格 ISO C17 运行时基座;C 逐语句翻译的安全性证明尚未完成。
- 有文档的公开函数
- —
- 已登记目标(已证 / 已列)
- 13 / 16
- 在上游发现的真实缺陷
- 0
zstd × Lean
未完成针对 Meta Zstandard 独立 C 解码器(libzstd)的严格 ISO C17 运行时基座与验证规约;C 翻译与公开解码器安全性证明尚未完成。
- 有文档的公开函数
- —
- 已登记目标(已证 / 已列)
- 5 / 9
- 在上游发现的真实缺陷
- 0
针对 Google Brotli C 解码器(libbrotlidec)的严格 ISO C17 运行时基座与验证规约;C 翻译与公开解码器安全性证明尚未完成。
- 有文档的公开函数
- —
- 已登记目标(已证 / 已列)
- 5 / 9
- 在上游发现的真实缺陷
- 0
共同验证方法
同一套翻译规则、严格 ISO C17 内存与故障模型及证明结构用于所有库。
C 代码按原语句顺序翻译为 Lean。ISO C17 中可到达的每一种未定义行为(包括空指针或悬垂指针加零与跨对象指针减法)都表示为显式故障 Fault.ub;无符号算术回绕,有符号算术逐处检查。
对每种流、解码器或文件句柄定义跨调用保持的状态性质:拥有的堆块、缓冲区容量、表内容与游标上界。
不把被调函数的契约当作公理。每个内部函数都在其自身翻译上证明定理;每个公开函数证明无故障返回、只写允许的内存帧并按账本分配与释放。
对任意合法调用序列作归纳,证明生命周期与关闭释放无泄漏;单独的非空性定理给出满足前提的具体初始堆。
flowchart LR
S["选定的 C 源码与补丁"] -->|"逐语句人工翻译"| T["Lean 翻译与故障模型"]
T --> I["初始化定理:建立状态不变量"]
I --> V["跨调用保持不变量、帧边界与无泄漏"]
V --> G["Lean 内核检查精确目标命题"]完成的结论依靠什么
Lean 内核检查每一条证明:定理的类型必须在语法上恰好等于目标命题,只允许三条标准公理(propext、Classical.choice、Quot.sound),禁止 sorry、native_decide、bv_decide、unsafe、partial、opaque、自定义公理与外部绑定。
证明建立在显式的可信基础之上:Lean 内核与检查器、内存与指针运行时模型、C 到 Lean 的人工翻译、选定的上游源码与补丁、构建配置与外部接口模型,以及目标命题本身。开启 AddressSanitizer 与 UndefinedBehaviorSanitizer 的差分测试把翻译与真实 C 逐字节对比,作为一致性的证据(而非证明)。