Reading Papers 01 - Concurrency Testing

# Concurrency Testing

PCT 即 Probabilistic Concurrency Testing ，是一种随机化的并发调度算法。PCT 提供了在每次 test run 中找到某个并发错误的数学概率，因而重复独立运行 test run 能够将发现错误的概率提高到任意所期望的值。

Key Idea ：并发错误通常仅涉及少数线程执行的少数指令之间的交互。

PCT 的设计旨在为深度较小的错误提供更好的保证：在每次 test run 中，PCT 专注于概率性地查找特定深度 $d$ 的错误。

设被测程序最多创建 $n$ 个线程、每个线程最多执行 $k$ 条指令，则对于一个深度为 $d$ 的 BUG ，PCT 在每次 test run 中以不小于 $1 / nk^{d - 1}$ 的概率找到此 BUG 。

PCT 调度算法 ：

PCT scheduler 为每个线程维护一个优先级，仅调度具有最高优先级的、当前可运行的线程。换句话说，一个线程被调度当且仅当所有比它优先级更高的线程都被阻塞。

PCT 会在每次 test run 时将被测程序的某些程序点设为 priority change point ，并为每个点关联一个预定的优先级值。当线程执行到 priority change point 时，PCT 将当前线程的优先级更改为与之关联的优先级值。

具体地讲，设被测程序最多创建 $n$ 个线程、每个线程最多执行 $k$ 条指令，则对于一个深度为 $d$ 的 BUG ，PCT 按如下方式工作：

初始时，将 $n$ 个优先级值 $d,\ d + 1,\ d + 2,\ ...,\ d + n - 1$ 随机分配给每个线程。
将 $d - 1$ 个 priority change point 随机分布在范围 $[1,\ k]$ 内。不妨设第 $i$ 个点位于第 $k_i$ 条指令处，且其关联的优先级值为 $i$ 。
根据优先级调度线程，并在某个线程执行到第 $k_i$ 条指令时将其优先级更改为 $i$ 。（？：是否应该为第一个执行到此处的线程？）

PCT 的调度是序列化的，即每一步只有一个线程在执行。

基于以下原因，在实践中 PCT 的表现可能比最坏界限更好：

SKI 基于 PCT 算法扩展了对中断的支持，并且针对中断优化了 PCT 调度策略。

SKI 实现 ：

TBD.

SKI 优化 ：

Key Idea ：在实践中，通过很少的 reschedule point 就能触发大多数并发错误；在实践中，通过少量线程和少量并发请求就能触发许多并发错误。

SKI 限制 reschedule point 仅会出现在 communication point 处，以避免测试冗余的调度。

SKI 在每次运行期间跟踪 memory trace 并生成一组潜在的 communication point 。此过程不依赖于 sample run ，各次运行的潜在点集会被合并累积，可以视为一个迭代的学习过程，前次累积的点集会被用于下一次运行。

Key Idea : overlapped memory access in different threads means potential concurrency bugs

对于由其它 input generator (e.g. Syzkaller) 生成的每个系统调用序列，在单线程下，从固定的初始状态出发执行并记录 memory trace 。存在对相同地址的读写访问的输入被绑定为 PMC-Based Input Pair 。

基于 SKI ，将 PMC 作为 scheduling hint 使用，在 PMC 指令附近频繁 schedule 。