作者：Meng Xu, Sanidhya Kashyap, Hanqing Zhao, and Taesoo Kim
单位：Georgia Institute of Technology
出处：S&P ‘20
Abstract
在访问共享数据时，如果两个线程没有得到正确的同步便有可能导致数据竞争（data race）。内核文件系统在设计上就是高度并发的，因此数据竞争也是其中非常常见的一类错误，可能导致系统状态不一致或者数据丢失等问题。现有的针对内核的模糊测试方案（fuzzing）虽然在文件系统中发现了上百个错误，但是它们主要关注的是文件系统的顺序执行，而并没有全面的探索其并发执行的方面，因此无法检测其中存在的数据竞争。
本文通过提出三个新的组件将覆盖率导向（coverage-guided）的模糊测试应用到探索文件系统的并发执行上：1）用来追踪并发执行探索进度的覆盖率追踪标准，别名覆盖率（alias coverage）；2）用来生成、变异与合并多线程的系统调用序列，并以此作为并发模糊测试输入的演化算法；3）用来实现精确数据竞争检测的针对内核同步原语的全面建模。这些组件在模糊测试框架KRACE中得到了整合，该框架已经在ext4、btrfs与VFS层中发现了23个数据竞争错误，其中有9个已经被确认为有害错误。
1 Introduction & Background
数据竞争是一类特殊的条件竞争，在复杂软件中检测数据竞争主要涉及两个方面：1）如何确认某次执行存在数据竞争；2）如何生成能够探索内核代码与线程调度的有意义的模糊测试输入。
为了将覆盖率导向的模糊测试应用到探索文件系统的并发执行上，本文提出了模糊测试框架KRACE，该框架通过提出新的组件填补了内核文件系统模糊测试在三个基本方面上的空白：
- 覆盖率追踪：KRACE采取了两套覆盖率追踪机制。分支覆盖率（branch coverage）被照例用来追踪顺序执行的探索进度。此外，为了估计并发执行的探索进度，KRACE提出了一种新的覆盖率追踪标准，别名指令对覆盖率，即别名覆盖率。别名指令对是指位于不同线程但可能发生交错的两条内存访问指令。别名覆盖率被用来追踪在执行过程中覆盖到的这些交错位置，即别名指令对的个数。
- 输入生成：KRACE根据系统调用规范来生成与变异单个的系统调用。该框架的新颖之处在于演化多线程的模糊测试种子并以交错的方式来合并它们，从而在保持现有的覆盖率的同时最大限度地探索新的线程交错。输入生成组件的另一项任务则是进行线程调度以探索隐藏的输入空间。KRACE采取了轻量级的延迟注入方案，并依赖于别名覆盖率作为反馈来确定是否需要进行进一步的延迟调度。
- 错误检测：KRACE内部集成了错误检测组件，该组件根据执行记录来检测数据竞争。总的来说，KRACE监控内核的每次内存访问操作，并记录访问相同内存地址的访问操作对，KRACE检查：1）这两次访问操作位于不同线程且至少有一次是内存写入操作；2）这两次访问操作是严格有序的，即happens-before分析；3）至少存在一个共享锁来保护这些访问操作，即lockset分析。KRACE的挑战在于如何为各式各样的内核同步机制进行全面的建模。
KRACE采取了软件恢复的策略来避免操作系统老化的问题，即每次执行都是从一个全新的内核与清空的文件系统镜像开始的。该策略虽然影响了框架的性能，但是同时也提升了数据竞争检测的可追踪性与可调试性。
此外，KRACE还将数据竞争检测从内核状态探索中分离了出来。与现有方案在每次执行的过程中串联进行错误检测不同，KRACE只有在出现新的分支或者别名覆盖的时候才会启动错误检测组件。该策略能够防止耗时的数据竞争检测拖慢内核的状态探索。
2 A Coverage Metric for Concurrent Programs
因此，在对高度并发的文件系统进行模糊测试时，KRACE不仅需要关注代码路径的探索，还需要关注有意义的线程交错的探索，即使探索这些线程交错产生的分支覆盖率是相同的。
数据竞争，或者从广义上来说，并发错误通常只涉及少数线程中执行的个别指令之间的非预期交互。如果能够追踪这些个别内存访问指令之间的交互，KRACE便能够追踪线程交错的探索进度，继而检测数据竞争。
首先，假设内核中存在的所有内存访问指令都被唯一地标记为：$i1, i2, …, iN$。在内核的运行过程中，每个内存地址记录其最后的定义，即最后对该内存地址进行写入的指令$ix$以及该指令所位于的线程$tx$，该定义被标记为：$A \leftarrow <ix, tx>$。此时，假设位于线程$ty$中的指令$iy$对该内存地址进行了新的访问，如果$iy$是内存写入指令，KRACE就将该内存地址的最后定义更新为$A \leftarrow <iy, ty>$；如果$iy$是内存读取指令，KRACE就在别名覆盖中记录有向指令对$ix \rightarrow iy$。
在本文针对内核文件系统模糊测试的实验中，KRACE总共记录了63,590对直接访问相同内存地址的别名指令。
3 Input Generation for Concurrency Fuzzing
系统调用生成组件的目标是生成各式各样复杂的文件操作。由于许多系统调用的参数都是高度结构化的数据，因此KRACE使用系统调用规范来指导系统调用的生成与变异。KRACE的系统调用规范还定义了与文件系统模糊测试相关的系统调用之间的依赖关系，包括文件路径与描述符。
KRACE将多线程的系统调用序列作为模糊测试的种子，该种子由单个的系统调用主序列与可配置个数的系统调用子序列组成，各个子序列互不相交，KRACE默认使用三个系统调用子序列，每个子序列都代表在内核的运行过程中单个线程将要执行的系统调用。
为了最大限度地提升分支与别名覆盖率，KRACE采取了四种多线程的模糊测试种子的演化策略，即mutation、addition、deletion与shuffling。
在合并多线程的模糊测试种子的时候，KRACE将会以交错的方式来合并两个种子中包含的系统调用序列，并在合并后的主序列与子序列中保留原先系统调用之间的相对顺序。
在针对内核文件系统模糊测试的过程中，KRACE总共收集了大约10,000个被成功执行的多线程的模糊测试种子，这些种子涉及了68个文件系统相关的系统调用。
对于并发程序来说，线程调度是其隐藏的输入空间。然而，目前没有办法仅通过系统调用来完全控制内核的调度。KRACE采取了延迟注入的方案来实现针对内核调度的间接控制。
在启动内核之前，KRACE首先生成一个包含随机数的环状缓冲区。在内核每次访问内存时，KRACE便会挂起当前线程并从该环状缓冲区中取出一个随机数$T$，然后等待内核中的其它线程访问内存$T$次后再继续执行当前线程。
4 A Data Race Checker for Kernel Complexity
如果两次内存访问操作访问的内存地址相同，同时这两次访问操作位于不同的线程，并且至少有一次是内存写入操作，那么这两次访问操作就有可能导致数据竞争。为了验证这两次内存访问操作是否确实导致了数据竞争，KRACE进一步采取了两种分析方案：
- lockset分析：在两次内存访问操作发生时，这两次访问操作位于的线程之间不存在任何共享锁；
- happens-before分析：不论两次内存访问操作位于的线程被怎样调度，这两次访问操作之间都不是严格有序的。
在理想情况下，lockset分析不会产生任何漏报，但是由于不考虑内存访问操作之间的排序信息，因此该分析非常容易产生误报。而happens-before分析便可以被用来过滤这些误报。虽然从概念上来说非常简单，但是lockset分析需要为内核中所有可用的同步机制进行全面的建模。同样的，happens-before分析也需要标记所有的线程排序原语。
5 Putting Everything Together
尽管避免数据竞争是公认的最佳编程实践，但良性的数据竞争在内核中却并不少见，例如针对统计信息的读写或者针对变量的不同比特的读写。
在对内核文件系统进行模糊测试时，大多数通用操作系统模糊测试框架都不会针对新的模糊测试阶段重新加载全新的内核或者清空的文件系统镜像。虽然该策略省去了虚拟机模拟器重新加载与启动内核所带来的额外开销，但是这也意味着通过该策略发现的任何错误都有可能是由之前成百上千次的模糊测试的累积效应导致的。对于内核开发者来说，这样的错误是非常难以调试和确认的。
KRACE的代码可以被分为两个部分，即编译时准备与基于虚拟机的模糊测试循环。
6 Evaluation
只有少数数据竞争错误在被触发时会导致内核崩溃等直接影响，而剩下的大多数错误则只会造成性能下降等间接影响。这也就意味着KASan的报告或者内核的崩溃等错误信号是不足以能够被用来检测数据竞争错误的。
btrfs在并发程度上比ext4更强，因此KRACE在该文件系统中追踪到的别名指令对的个数也更多。
总的来说，在内核文件系统模糊测试的过程中，分支与别名覆盖率的增长是同步的。然而，在分支覆盖率饱和的时候，别名覆盖率则依旧在增长。这也就意味着KRACE一直在探索新的线程交错。如果只追踪了分支覆盖率，那么KRACE将错过这些线程交错所产生的新的内核状态。
