Linux CPU 调度器缺陷的刻画与确定性测试（OSDI 2026）
原题：kSTEP: Characterization and Deterministic Testing of Linux CPU Scheduler Bugs
一句话总结：232 个 Linux scheduler 修复中 73% 没有 panic/warning、45% 隐藏超过一年；kSTEP 通过隔离 CPU、mock clock 和显式注入 tick/event，把 7 个真实缺陷压缩成至多 20-event 的确定性 reproducer，并进一步发现 4 个新缺陷。
问题与动机
Linux CPU scheduler 不只要避免 crash、starvation 和 affinity 违反，还要让实现符合 fairness、locality、work conservation 与 energy 等策略意图。后一类 policy bug 仍能完成功能，却悄悄损害服务质量，外部 performance anomaly 无法证明是缺陷还是合理 trade-off。
作者分析 2020 年以来 232 个 scheduler bug-fix commit，发现现有测试主要依赖 noisy、长时间 benchmark；生产报告常缺少精确 trigger sequence，修复也很少留下 regression test。核心困难是 scheduler state 随 tick 连续变化、trigger 涉及 userspace 之外的 kernel/hardware event，而普通 trace 又被 interrupt、RCU、workqueue 和 clock noise 污染。
关键观察 / 隐含假设
- 观察 1：232 个修复中 15% 导致 crash/hang，26% 是 silent functional fault，47% 是 policy misalignment；合计 73% 没有 panic/warning（§3.3、图 7）。
- 依赖假设：带
Fixes:或 defect 关键词的 2020 年后 commit 能代表 scheduler bug 总体。 - 可能失效场景：未报告、未修复和缺少关键词的 bug 被系统性漏掉，分类亦含人工判断。
- 依赖假设：带
- 观察 2：90% bug 依赖特定 workload 行为，54% 依赖 scheduler attribute，28% 还需 kernel event 或特殊硬件属性（§3.7、图 12）。
- 依赖假设：这些 trigger 能抽象为有限、串行的 event API，而不必重放完整生产环境。
- 可能失效场景：真正的 scheduler concurrency race；论文统计其中约 12%，kSTEP 明确不能直接暴露。
- 假设 1：隔离 CPU 上仅保留测试 task、mock scheduler 所见 clock、压制非预期 kernel activity，不会移除目标 bug 所需的真实交互。
- 证据强度：中。七个 case 的 buggy/fixed trace 能稳定分岔，但样本小且在 QEMU 上运行。
- 假设 2：policy oracle 可由开发者把设计意图编码成 invariant；clean coverage 足以引导 fuzzer 到有意义状态。
- 证据强度：中。fuzzer 找到两项新 bug，但每个 studied bug 仍需要手写 invariant，且一个 20k-task case 未触发。
核心方法
kSTEP 让 kernel-space driver 用 event API 描述 task create/wakeup/freeze、cgroup 与 kthread 操作、CPU topology/capacity/frequency，以及显式 scheduler tick。tick_until(predicate) 可把 scheduler 停在短暂 internal state 后立刻注入目标 event；driver 不能直接改 scheduler state，仍需经过原 Linux 路径，保留 fidelity。
控制 module 在专用 CPU 上执行 driver，其余 controlled CPU 只运行明确创建的 task。determinism module mock scheduler clock、屏蔽无关 interrupt/kernel activity，并在测试前重置 runqueue 等初态。相同 input 因而产生 noise-free internal trace，可逐事件比较 buggy/fixed kernel，而不是记录并重放一份带 noise 的 whole-machine execution。
基于此机制，kSTEP tracer 记录稳定 scheduler execution path。coverage-guided fuzzer 复用确定性 prefix，只变异后续 event；它跟踪 task 的 running/runnable/blocked/frozen 状态，只生成合法动作，并用 clean kernel scheduler coverage 反馈探索。bug oracle 则是测试者编码的 policy/functionality invariant。
设计取舍
- 隔离与确定性换取环境代表性：排除生产 noise 才能稳定归因，却也可能遗漏依赖 interrupt、device 或跨 subsystem concurrency 的 bug。
- event 序列串行化：大幅简化控制和 replay，但不能直接搜索 scheduler 内部并发缺陷。
- 不改 scheduler 源码：kernel module 跨版本复用且执行真实 code path；代价是 QEMU/module 适配、CPU 模型模拟和 kernel-internal API 演化成本。
- 人工 invariant：policy intent 可成为明确 oracle，但需要深厚 domain knowledge，无法宣称 general push-button bug discovery。
实验与结果
- 在 2×10-core Intel Xeon、Ubuntu 24.04、每次新启 QEMU 的环境中，7 个 sampled bug 的 reproducer 最多 20 events、47 LoC；除一个需 20k task 的 case 外，其余最多 5 task，并在数秒内运行（§6.1、表 4）。
- 24 小时 fuzzing 中，多数 studied bug 在 1 小时内触发；曾耗时约 30 天仍无 reproducer 的 cgroup/vruntime bug 在 8 小时以上触发，而 20k-task bug 超出 fuzzing scale（§6.1、表 4）。
- kSTEP trace 在 trigger 前跨 buggy/fixed kernel 保持相同，之后明确分岔；七个 case 覆盖 remote placement、starvation、freeze failure、额外 rebalance、util error 与高调度成本（§6.2、图 16）。
- 一个 load-balancing bug 在 20k pinned task 下使 rebalance 约耗 2.5 ms，fix 后约 1 µs；另一个 RT utilization bug 的错误估计约 500 ms 才恢复（§6.2、图 16）。
- 手写 driver 发现 2 个新 bug，fuzzer 再发现 2 个，包括官方 fix 不完整、特定 topology 下 CPU 空闲、错误 group label 和低容量 CPU idle accounting 错误（§6.3、图 17–18）。
论断—证据表
| 论断 | 证据 | 评测边界 | 置信度 |
|---|---|---|---|
| scheduler bug 普遍低可观测且长期潜伏 | §3、图 5/7：73% 无 warning，45% 超过一年，5% 超过十年 | 2020 年后 232 个 Linux 修复 commit，人工分类 | 强 |
| kSTEP 可把真实 bug 压缩成短而确定的测试 | §6.1、表 4：7/7 复现，至多 20 events、47 LoC | 7 个 purposive sample、QEMU、Intel host | 中 |
| trace determinism 足以区分 buggy/fixed 行为 | §6.2、图 16：trigger 前一致、之后分岔 | 所选 7 个 bug；未报告大规模 repeated-run 统计 | 中 |
| kSTEP 可发现未知 scheduler bug | §6.3、图 17–18：4 个新 bug | 2 个手写、2 个 fuzzing；需要 invariant 与人工确认 | 强 |
批判性分析
论证链条
characterization 清楚地把“低 observability + 复杂 trigger”映射到“受控 event + deterministic trace”，case study 也逐项验证 trigger、observe、discover 三个用途。薄弱处是从 7 个精选 bug 外推到整个 232-bug population：平台未覆盖最明确的 concurrency 类别，且选择能被 event model 表达的案例可能高估通用性。
假设压力测试
若 bug 需要真实 firmware、NUMA latency、interrupt storm、device driver 或并行 race，mock topology 和串行 driver 可能只保留表面配置而不保留因果机制。反之，过度 isolation 还可能制造生产中不可达的 scheduler state。需要把 kSTEP reproducer 在物理机或非隔离 kernel 上做可达性验证，论文主要验证的是 code-path fidelity，而非 production-frequency fidelity。
实验可信度
逐 commit 的 buggy/fixed A/B、精确 trace 与公开 artifact 使 case 证据可审计，四个新 bug 也比单纯 coverage 数据更有说服力。但缺少与 Syzkaller、LTP、benchmark/replay 方法在固定 CPU-hour 下的 head-to-head 比较；fuzzer 的 24 小时结果依赖每项手写 invariant，未报告 coverage 稳定性、false-positive 数量与 repeated trial variance。
系统性缺陷
kSTEP 是 developer testing substrate，而非 production detector。它依赖 kernel module、专用 CPU、QEMU 和 version-specific internal symbol，长期维护成本论文未量化。mock clock 与 suppression 的安全边界、模块自身 bug、不同架构（ARM/heterogeneous hardware）的 portability 未充分实验；测试失败也仍需专家理解 policy 并编写 fix。
局限与后续工作
- 局限 1：driver event 串行执行，不能直接发现 scheduler concurrency bug。
- 局限 2：七个复现样本和单一 Intel/QEMU 环境不足以覆盖 232-bug taxonomy 与异构硬件。
- 局限 3：fuzzer 需要人工 invariant，尚无通用 policy oracle。
- 后续工作 1：按 taxonomy 分层抽取至少 50 个历史 bug，报告可表达率、复现率、编写时间与跨 kernel version 稳定性。
- 后续工作 2：在 x86/ARM、NUMA、asymmetric core 与物理机上 replay 同一 driver，比较 trace divergence 和真实性能 effect。
- 后续工作 3：与 Syzkaller/LTP 在等 CPU-hour 下比较 coverage、unique bug、false positive 和 time-to-trigger，并加入受控并行 event 扩展。