Reading Papers - Kernel Concurrency
# Overview
# Scheduling Control
对于内核并发测试而言,要想有效地探索调度空间,必须对内核的线程调度采取一定程度的控制。按照控制的程度,可以将主流方法划分为三大类:
stress testing :主要由早期的黑盒随机测试类的工作所采用。
delay injection :通过代码插桩在有价值的程序点处延迟程序执行,间接影响内核的线程调度情况。
scheduling control :通过 hook 调度点或修改 scheduler 等方式实现对线程调度的完全控制。
# Fuzzing
# S&P'19 - Razzer
Razzer 利用静态分析获取存在 potential data race 的程序点,据此指导 fuzzing 过程,并实现定制的 VMM 以发现能真实触发 data race 的线程调度。
Taxonomy : kernel concurrency testing / kernel fuzzing / scheduling control
Taxonomy : mutation-based / coverage-guided / specification-based / static-assisted fuzzing
Tag : static analysis / virtualized environment
Key Idea :感觉这份工作在 high-level 的策略上和 PLDI'08 - RaceFuzzer 高度相似,都是利用静态分析高效地得到低准确率的 potential data race ,然后据此指导动态测试过程。
Razzer 的策略类似于 RaceFuzzer ,同样是分为静态和动态两个阶段;不同的是,Razzer 的第二阶段是一个更加复杂的两阶段动态测试过程。
Razzer 在静态阶段进行 context-insensitive, flow-insensitive but field-sensitive 的 points-to analysis ,利用这种过度近似的分析来减少漏报,并利用后续的动态阶段来解决此分析的高误报问题。
为了改善性能问题,Razzer 对内核进行按模块的分区分析。
Razzer 的静态分析未考虑同步原语(尤其是 kernel 自己实现的同步原语),但这些信息可以被用于减少误报(即缩小 potential data race 集合)。
Razzer 的两阶段动态测试过程如下:
在第一阶段,Razzer 利用 Syzkaller 已有的系统调用语法模板,以类似的方式随机生成用户程序,随后执行单线程的 kernel fuzzing :
如果执行时触及了某一组 potential data race 的全部两条指令,则标注相关信息并将该输入(记为 )传递至第二阶段。若一次执行覆盖了多对指令,则制造输入的拷贝,使传递给第二阶段的每个输入仅包含一对指令。
如果执行覆盖到了新的代码,则像传统 fuzzer 那样将其作为 feedback 用于后续的输入生成。
在第二阶段,Razzer 对接收的每个标记过的输入 插桩一系列的 hypervisor call 指令,用于在运行时刻确定性地控制线程调度、以及执行各种检查,使其能确定性地触发并检测到 data race(如果真实存在的话)。
Razzer 在定制的 VMM 上执行被测内核,利用一系列定制的 hypervisor call API 来支持测试需求:
per-core(或者说 per-vCPU)的 breakpoint ,用于支持确定性的线程调度(启动、暂停、指定顺序等)。
检测是否真实地触发 data race 。
# S&P'20 - Krace
一方面,Krace 提出了 alias instruction-pair coverage 以表征并发调度的覆盖情况,并设计了更适合并发程序的种子变异策略;另一方面,Krace 详细考量了 kernel 实现中丰富的同步原语,并据此进行 happens-before analysis 。
Taxonomy : kernel concurrency testing / kernel fuzzing / delay injection
Taxonomy : mutation-based / coverage-guided / specification-based fuzzing
Tag : correctness criteria / happens-before
Preceding Work : S&P'19 - Razzer
S&P'19 - Razzer 的 workflow 仍有改进的空间:
保守的指针分析会产生海量的 potential data race ,无法全部触及;
对于给定的 potential data race ,Razzer 仅尝试通过 Syzkaller 触及。
# Alias Instruction-Pair Coverage
Krace 在运行时追踪每个内存地址 的 last def operation (类似于 def-use chain 的 def)以及执行 时的上下文 ,记为 。
每当 处以上下文 触发任一内存访问指令 时:
若 为写指令,则更新 last def operation 为 。
若 为读指令且 ,则在 alias coverage 中记录有序对 。
若 为读指令且 ,则 为冗余指令对,不作任何处理。
Krace 用 alias coverage 来额外表征当前 workload 是否还有继续探索 thread interleavings 的价值(即探索不同的 delay injection 选择),而不是用于完全代替 branch coverage 。
- 只要 alias coverage 仍在增长,Krace 就会持续尝试探索不同的调度;若趋于饱和,则应尝试变异 workload 或更换 input seed 。
Krace 在所有内存访问指令处插桩 delay 指令,其参数为(静态决定的)随机数 ,表示将该指令的执行延迟到 次其它内存访问操作之后。
- 可以选择更大的粒度以减小 overhead 。
# Concurrency-Targeted Input Generation
在 specification-based fuzzing 的基础上,Krace 设计了面向并发程序的种子变异策略:
每个输入(即 syscall trace ,称为主序列)被划分为 个互斥的子序列,对应每个线程的 workload(默认 ,可配置)。
除传统变异操作 mutate / add / delete 等,有 shuffle 操作改变 syscall 所属的子序列。
采用更先进的 merge 方案,将两个种子的主序列交叉合并:这最大程度地保留原先每个主序列内部的相对顺序。
在产生新的种子后,Krace 首先进行修剪,仅保留序列中成功执行的系统调用;然后将其拆分为互不相交的子序列,满足每个子序列都是 self-contained 的;这些子序列被称为 primitives ,它们捕获了系统调用之间的依赖关系,并将被用于后续的 fuzzing 过程中。
- Krace 共收集了约 10000 个 3-thread primitives ;作者声称未来将要开源该数据集,但我在其研究组主页和 GitHub 上都没找到。
# Krace Data Race Detection
Krace 在运行时记录包含所有同步原语操作的 trace 。与其它 kernel fuzzer 不同,Krace 不在测试运行期间同时进行错误检测,而是在 coverage 增长时离线检查 trace 以减小 overhead 。这可能导致误报,因为 alias coverage 并不能表征所有的并发交错(为什么?)。
与过去的大部分 kernel fuzzer 不同,Krace 会在每次 testrun 中启动新的 fresh kernel instance ,这是考虑到并发线程交织会让原本就很严重的 hard-to-reproduce 问题变得更加糟糕。然而,S&P'19 - Janus 利用 LKL 实现快速加载的方法不适用于 Krace ,因为 LKL 不支持 SMP 。这导致 Krace 遭受了额外的 overhead ,(我觉得)这可能也是 Krace 选择进行离线错误检测的一个重要原因。
Krace 无法做到 deterministic replay ,因而 Krace 会在发现错误时生成尽可能完备的错误报告。事实上,内核开发者通常也足以据此定位 bug 的 root cause 。
lockset analysis
Krace 考虑了 kernel 中的 spinlock 、mutex lock 、reader/writer lock 、RCU lock 、sequence lock ,对不同类型的同步原语采取不同的做法。
Krace 为每个线程分别维护 reader-side lockset 和 writer-side lockset 两个锁集。线程 在指令 处的 lockset 记为 。对于每个 potential data race ,满足一定条件的会被认为不可能是 data race 。
happens-before analysis
Krace 将 kernel file system 中的 happens-before relation 分为三类,并据此进行 happens-before analysis 。
benign data race
Krace 采取一些启发式方法来剔除 benign data race ,这可以处理简单的情况,但对复杂的情况无能为力。
将名称中含有
stat
的变量剔除,将用于统计的函数中的内存访问指令剔除;将读写同一变量的不同 bits 范围的内存访问指令剔除;
将已知可以容许 data race 的函数剔除(例如
list_empty_careful
)。
# S&P'23 - SegFuzz
SegFuzz 提出了 interleaving segment coverage 以改善其它 concurrency fuzzing 工作所用的 coverage metric 的固有缺陷,并设计了 segment 的计算和使用方法以在缺陷检测能力和调度空间探索能力之间进行 trade-off 。
Taxonomy : kernel concurrency testing / kernel fuzzing / scheduling control
Taxonomy : mutation-based / coverage-guided / specification-based fuzzing
Tag : correctness criteria
Preceding Work : S&P'20 - Krace
S&P'20 - Krace 和 NDSS'22 - ConFuzz 中提出的 coverage metric 度量了并发调度的覆盖情况,但其存在固有缺陷:作为偏向于启发式策略的度量,过去的 coverage metric 并不能严格区分(与共享内存访问相关的)所有不同的线程调度。
S&P'20 - Krace 仅将 alias coverage 用作 fuzzer 判断是否继续探索更多调度的标准,而采用随机插入 delay 的方式,并未充分利用并发的 coverage metric 来引导对线程调度空间的探索;本文 argue 后者是更合适的选择。
# Interleaving Segment Coverage
我对 SegFuzz 的理念的理解是,设计 coverage metric 以考虑程序中的所有并发调度(即便仅考虑共享内存访问操作)是不现实的,关键在于其能否区分两个不同的调度。
SegFuzz 在缺陷检测能力和调度空间探索能力之间进行 trade-off ;具体地讲,SegFuzz 将调度空间划分为极小的 subspace ,称为 interleaving segments 。每个 interleaving segment 包括少量(不超过 4 个)共享内存访问操作之间的执行顺序。
- 绝大多数的并发错误仅涉及不超过 4 个共享内存访问操作(作者简单检验了 Shan Lu 的这一结论在现代的 Linux 内核代码中仍然适用),因此 interleaving segment 中的最大指令数为 4 。
SegFuzz 利用 DAG 来表示一次 testrun(即一个调度)的指令执行顺序,每个节点表示一条内存访问指令,每条边表示两条指令之间的执行顺序约束,包括:
program-order edge 表征了指令的静态顺序,即单一线程内的指令执行顺序。
interleaving-order edge 表征了该调度下不同线程执行指令的相对顺序,仅对可能存在 data race 的指令对生效(即由不同线程读写同一地址,且含有写操作)。
SegFuzz 在运行时记录每个共享内存访问指令在执行时的 timestamp ,并据此维护一个全程序的 DAG 。在 testrun 执行完毕后,SegFuzz 通过提取 2 条 interleaving-order edge 生成若干个节点数不超过 4 的子图(不互斥,子图之间有交集),称为 segment graph 。每个 segment graph 都表征了一个 interleaving segment 。
- 为减少内存消耗,SegFuzz 在实现中利用 Merkel hashing (?) 来压缩 segment graph 。
# SegFuzz 工作流程
类似于其它的并发调度覆盖,SegFuzz 的 interleaving segment coverage 通过追踪 segment graph 得知是否探索到了新的调度,借此判断当前 workload 是否有继续探索其它调度的价值。
SegFuzz 对 explored interleaving segment 所对应的 segment graph 进行变异和重组来获取 unexplored interleaving segment 。
mutation :改变 segment graph 中边的方向,即翻转指令之间的执行顺序。变异结果不允许存在环路,即必须仍为 DAG 。
recompose :将多个变异后的 segment graph 组合得到更大的 DAG ,以便在一次 testrun 内同时探索多组 segment 。
对于每次 testrun 要探索的 DAG ,SegFuzz 通过定制的 VMM 在对应的指令处调度指定的线程。
SegFuzz 的工作流程分为 single-threaded fuzzing 和 multi-threaded fuzzing 两个阶段(类似于 S&P'19 - Razzer 的两阶段动态测试过程);关键在于 SegFuzz 的 single-threaded fuzzing 阶段就推断 workload 是否有潜力探索到新的 interleaving segment(判断标准写得太简略了,我没看懂)。
# Scheduling Control
# OSDI'14 - SKI (to-be-reread)
SKI 基于 PCT 算法扩展了对中断的支持,并且针对中断优化了 PCT 调度策略。
Taxonomy : concurrency testing / scheduling control
Tag : scheduling control
SKI 实现 :
TBD.
SKI 优化 :
Key Idea :在实践中,通过很少的 reschedule point 就能触发大多数并发错误;在实践中,通过少量线程和少量并发请求就能触发许多并发错误。
SKI 限制 reschedule point 仅会出现在 communication point 处,以避免测试冗余的调度。
- 定义 communication point 为一条指令,该指令会访问其它线程在测试期间访问的内存位置,并且其中存在至少一个写操作。
SKI 在每次运行期间跟踪 memory trace 并生成一组潜在的 communication point 。此过程不依赖于 sample run ,各次运行的潜在点集会被合并累积,可以视为一个迭代的学习过程,前次累积的点集会被用于下一次运行。
# SOSP'21 - Snowboard
Snowboard
Taxonomy : concurrency testing / scheduling control
Tag : scheduling control
Key Idea :overlapped memory access in different threads means potential concurrency bugs
- PMC : Potential Memory Communication
对于由其它 input generator (e.g. Syzkaller) 生成的每个系统调用序列,在单线程下,从固定的初始状态出发执行并记录 memory trace 。存在对相同地址的读写访问的输入被绑定为 PMC-Based Input Pair 。
基于 SKI ,将 PMC 作为 scheduling hint 使用,在 PMC 指令附近频繁 schedule 。
- 01
- Linux Kernel - Source Code Overview05-01
- 02
- Linux Kernel - Per-CPU Storage05-01
- 03
- Linux Kernel 88 - Macros05-01