形式验证

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 spinPromela 模型检查(状态穷举 + LTL)锁序 / futex 等待唤醒 / 中断-抢占 / 调度出入队4 个模型,全 PASSnightly 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→桶禁止)313PASS(errors: 0)
futex_wait_wakeLTL NoLostWakeup + NoPermanentSleep;INV-FUTEX-1(等待者在桶锁内置 INTERRUPTIBLE 后才释放)3,220,543PASS(1.19 s)
interrupt_preemptLTL HardirqBounded(0≤深度≤3)+ PreemptNoUnderflow181PASS
sched_enqueue_dequeueLTL NrRunningValid(0≤nr_running≤4)+ NoPermanentStarvation;INV-SCHED-1..34,815PASS
  • 运行: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。