形式验证
kernel/verify/ · 五种验证装置作用于同一份镜像的内核逻辑:符号执行(Kani)、模型检查(SPIN)、并发交错枚举(loom)、未定义行为检测(Miri)、属性测试(proptest) —— 各装置的证明对象、规模、运行节奏与已捕获缺陷 · 正本:kernel/verify/README.md、docs/architecture/security-design.md §3
§1装置全景
| 装置 | 方法 | 证明对象 | 规模(当前树) | 节奏 |
|---|---|---|---|---|
| make verify | 镜像同步检查 + 属性测试 + 单元测试 | 被镜像进宿主 crate 的内核算法 | 1,184 个 #[test](含 proptest!) + 内核内 1,584 个用例 | 每次 push |
| make kani | 符号执行,对全部输入证明断言与 panic 可达性 | 核心 unsafe 代码与协议不变量 | 164 个 #[kani::proof](34 文件) | nightly CI |
| make spin | Promela 模型检查(状态穷举 + LTL) | 锁序 / futex 等待唤醒 / 中断-抢占 / 调度出入队 | 4 个模型,全 PASS | nightly CI |
| loom | 并发交错枚举(受抢占界约束) | SleepMutex 交接状态机 | 8 场景(5 清洁 + 3 预植必捕) | nightly CI |
| make miri | 解释执行 + UB 检测 | verify 镜像 crate 全量 | 随 1,184 测试 | nightly CI |
全部装置运行于宿主侧、不依赖内核镜像:验证对象是从 kernel/src 镜像进 verify crate 的纯类型与状态机。装置分工互补 —— proptest 答"算法对采样输入正确",Kani 答"对全部输入正确",SPIN/loom 答"所有交错下无死锁/无丢失唤醒",Miri 答"无未定义行为"。
§2Kani 符号执行(164 harness)
- 覆盖分布:fs 19、drivers 18、arch 17、process 16、signal 14、net 14、interrupt 11、sched 9、security 9、mm 18、ipc 5、errno 5、sync 4(每文件计数,合计 159/34 文件)。
- harness 合同风格:每个 harness 将 kernel/src 的纯类型镜像进 verify(注释逐字标注来源文件),以
kani::any()取符号输入,kani::assume收窄前条件,断言具名不变量INV-<域>-K<n>。示例:INV-CAP-K1(能力掩码合法 41 位)、INV-RT-K1(空位图返回 None)、INV-INODE-K3(文件类型互斥)、INV-PCI-K4(64 位 BAR 判定位型)、INV-ERRNO-K3(EWOULDBLOCK == EAGAIN,POSIX 要求)。 - 旗舰证明(sync/mutex_kani.rs,S-1 试点数据面):K1 对任意长度 K 的规范操作序列证明不变量表 INV-M1..M4 逐步保持、INV-M5 令牌守恒全程成立、INV-M6 无算术 panic(Kani 直接检查 panic 可达性);K2 证明设计内的 do_exit 孤儿等待者泄漏有界且不妨碍门控/纪元/防饿路径。两证明合计 ~2.2 s(Kani 0.68.0)。
- 不变量密度:verify crate 内 902 处 INV- 引用、约 150 个不变量族;内核源码侧另有 158 处运行时不变量引用(INV-PCP、INV-LOCK、INV-FUTEX、INV-SCHED 等)。
- harness 自身的缺陷也被捕获:首批运行暴露三个 harness 调用纪律缺口并逐个修复 —— pid-0 空闲态别名(两个内核实体共享 pid 0,不得建模为同一者)、计数等待者同时无门获取(单一 lock() 调用不可产生的调用序)、设计内 do_exit 泄漏被正确判为 INV-M5 违例(检测正确,建模补 leaked 字段)。其中一次还修复了令 cargo kani 完全无法编译的 vma_kani 预存缺陷。
§3SPIN 模型检查(4 模型全 PASS)
| 模型 | 被检性质 | 状态数 | 结论 |
|---|---|---|---|
| lock_ordering | 锁获取无死锁环;层级 L0 IRQ→L1 preempt→2a GRQ→2b futex 桶→3 waiter 槽;INV-LOCK-5(桶→GRQ 允许,GRQ→桶禁止) | 313 | PASS(errors: 0) |
| futex_wait_wake | LTL NoLostWakeup + NoPermanentSleep;INV-FUTEX-1(等待者在桶锁内置 INTERRUPTIBLE 后才释放) | 3,220,543 | PASS(1.19 s) |
| interrupt_preempt | LTL HardirqBounded(0≤深度≤3)+ PreemptNoUnderflow | 181 | PASS |
| sched_enqueue_dequeue | LTL NrRunningValid(0≤nr_running≤4)+ NoPermanentStarvation;INV-SCHED-1..3 | 4,815 | PASS |
- 运行:
make spin(spin -a → pan.c → pan -a),仅 errors: 0 判 PASS,重生成 spin-report.txt,任何 FAIL/编译错误退出码 1;nightly CI 固定执行。 - 活性属性按建模注释有取舍:interrupt_preempt 有意不建模饥饿消除("SPIN 会穷举真实硬件上不存在的饥饿交错")—— 判据是建模范围与硬件现实的对应,而非状态数最大化。
§4loom 交错枚举:SleepMutex 提取
内核并发原语的忠实提取:mutex_model.rs 提取 kernel/src/sync/mutex.rs 的交接状态机(R84/R85 公平性 + 孤儿交接恢复),环境钩子(get_jiffies/wake_up_one/防饿阈值)作参数注入;mutex_loom.rs 为驱动与 8 场景。
- 不变量表 INV-M1..M6:M1 locked ⇒ depth≥1;M2 !locked ⇒ owner==0(逆命题不成立:pid==0 的早期/中断上下文可经无门自旋路径持锁);M3 !locked ⇒ depth==0;M4 owner≠0 ⇒ locked;M5 令牌守恒;M6 waiters 无下溢。互斥以共享计数器在每个状态临界区内断言恰为 1;另检死锁自由。
- 8 场景:5 个清洁场景(双任务/三任务/自旋者+睡眠者/递归与退出释放/防饿覆盖)+ 3 个预植必捕场景(P1 无纪元恢复 = R85 前搁浅形态;P2 令牌跳过递减 = M5 破坏;P4 重泊重计)—— 装置对已知缺陷类的检出能力本身经过校准。
- 运行:8 场景 59.5 s,抢占界 3(release);CI nightly 以 LOOM_MAX_PREEMPTIONS=3、--cfg loom 构建执行,失败判据含 FAILED 与 deadlock。
- 首启用 90 秒捕获真实内核缺陷(011a71c5):递归分支仅判
owner == pid—— 空闲锁 owner==0 而无任务上下文 get_current_pid()==0,无任务调用者在交接窗内命中"空闲锁"即误入递归分支,对未锁对象置 depth=1;该伪 guard 的 release 可释放他人真持有的锁(互斥破坏)。修复 = 四个递归分支加st.locked &&,另加确定性回归测试。 - 设计特征的穷举论证:两任务纯公平争用无 R85 定时器即无搁浅;3+ 等待者存在仅能由 R85 定时器界定的搁浅交错 —— 防饿定时器由模型检查给出存在性证明,非启发式。
- 解释规则已记录在案:定时器为部分建模(泊车时限检查在模型时钟推进过限期时投递)——"锁空闲且全部等待者已泊"的死锁判定为设计内有界等待状态,非内核缺陷。
§5属性测试与 Miri
- 规模:verify crate 1,184 个 #[test](164 文件),其中 proptest! 块若干(proptest 1.5,每测试默认 256 例,PROPTEST_CASES 可调);内核内另有 1,584 个用例(unit-test feature,QEMU 内 make test 执行)。
- 覆盖面:buddy 对齐/对合性、引用计数非负且无下溢释放、VMA 不重叠、Newton 法整平方根与水位线公式、Sv39 PTE/Satp 编码、RFC 1071 校验和 / RFC 6298 RTT / RFC 5681 拥塞控制、最长前缀匹配、ARP 缓存 LRU、路径规范化与根逃逸防护、Unix DAC 判定(含 CAP_DAC_OVERRIDE)、ext4 间接块/namei/超级块/分配器、OOM badness 评分(10 项:OOM_SCORE_ADJ_MIN 免疫、饱和规避、小 totalpages 无调整、对称性)、CFS 权重表单调性、deadline 带宽钳制、futex 键匹配、能力代数(De Morgan/子集/补)、cmdline 解析、JBD2 标签算术。
- 边界如实声明:不覆盖裸指针/内联汇编/GlobalAlloc 实现、运行期并发与中断行为、需 QEMU 的系统集成 —— "verify 回答'算法是否正确',单元测试回答'实现是否正确'",集成面由 LTP/压力并发集群承担。
- Miri:对 verify crate 全量以
-Zmiri-disable-isolation解释执行,检出任何 UB 即 fail(nightly,360 分钟预算)。
§6镜像同步纪律:证明钉在被证代码上
- verify crate 手工镜像被证算法;镜像副本与内核原文的漂移使构建失败(scripts/verify_sync_check.py,逐函数等价归一化检查)—— 证明不可能在代码演化后静默失效;CI 与 make verify/make kani/make miri 全部先跑同步检查。
- 状态机类提取(mutex_model.rs)额外要求状态转换表与内核实现在同一提交内变更。
§7运行节奏
- 每次 push:三架构构建烟测 + 镜像同步 + verify 全量(1,184 测试)—— 单提交预算内。
- nightly:Kani 全 164 harness、Miri 全量、SPIN 4 模型、loom 8 场景 —— 重型作业不占 per-push 预算(避免每提交染红)。
- 证明性改动落地前:make verify && make kani 手动前置。
§8调研试点 → 已落地
- S-1(并发原语模型检查试点,seL4 谱系):SleepMutex 提取 + loom/Kani 双装置已落 main(11c73f42/011a71c5/1d697ec2d/3b7b6f68);后续提取目标按事故密集度排队(D-7 magazine、D-11 GRQ claim、futex 桶嵌套)。
- S-5(类型化定时器轮槽域试点):落地为 D-19,六类误用成为编译错(证据:同树六处 rustc 拒绝 + 同一测试平台 A/B)。
- S-2(类型化 binder 事务 FSM)为登记的占位项 —— 进占位区的唯一出口是交付实测证据。
装置选型原则(对照 Linux):Linux 无 Kani/loom/Miri 对应物,SPIN 对应其 lockdep 的编译期子集 —— Rux 的差异在验证前移到构建/CI 期而非运行期采样。代码:kernel/verify/(34 harness 文件 + spin/4 模型 + mutex_loom.rs);CI:.github/workflows/{kani,spin,loom,miri}.yml。