Razzer：通过模糊测试查找内核数据竞争漏洞

文/谈心

内核中的数据竞争可能导致许多有害行为。最严重的后果是数据竞争导致内存污染最终可能造成非法权限提升，例如CVE-2016-8655, CVE-2017-2636, and CVE-2017-17712。目前的技术在内核数据竞争漏洞的检测与防护方面都存在一定的局限性，其原因是内核中的数据竞争漏洞受到一些系统不确定性行为的影响，比如线程的调度与同步机制。因此与普通的漏洞相比，要检测这类漏洞除了需要控制流和数据流信息以外，还需要精准地执行信息。

在该项工作中，本文提出并设计了针对内核中的数据竞争类型漏洞的模糊测试（Fuzzing）工具Razzer。本文的思路是引导Fuzzing工具去尽可能地执行到存在数据竞争漏洞的代码。这包含了两种技术：一是通过静态分析来定位潜在存在数据竞争的代码；二是一种确定性的线程交错技术，来控制线程调度，以提供精确的并行执行信息，降低不确定性。本工作并没有去解决同步机制对多线程fuzzing的影响。

问题定义

为了更好地检测数据竞争类型漏洞，文中对这类问题给出了一个明确的定义。

如果目标程序内两条内存访问的指令满足以下3个条件，就是数据竞争:1. 访问的内存地址相同；2. 至少其中一条指令是对内存的写；3. 两条指令可以并发执行。

同时，数据竞争并不都是漏洞，有一些数据竞争可能是开发者有意设计的，有一些数据竞争行为可能产生非预期的行为，这些才是数据竞争漏洞。文中还引入了一些标注，以便后续的说明：

RacePair_{cand}：可能满足上面三个条件的RacePair

- RacePair_{true}：已确定满足上面三个条件的RacePair，是RacePair_{cand}的子集

- RacePair_{benign}：属于预期内的数据竞争

- RacePair_{harm}：非预期的数据竞争

本文给出了一个具体的例子CVE-2017-2636来具体说明，相关代码如图1所示。

一个用户态程序的两个线程A、B，分别调用了系统函数ioctl和write，这两个系统函数会由内核来执行。在参数满足一定条件的情况下，线程A和B都会去访问同一个内存地址n_hdlc-＞tbuf,满足条件一；其中第440行是对内存的写，第216行是对内存的读，满足条件二；这两处访存可以并行执行，满足条件三，因此这是一组RacePair_{true}。而且在这个例子中，程序的行为会由于两条指令执行先后的不同而变化。当第216行先于440行执行，n_hdlc-＞buf会被压入free_list两次，在后续的代码中，free_list中的元素会被依次释放（第269行）。因此最终会导致double free的问题。这一组指令是一组RacePair_{harm}。

图1 代码示例

设计与实现

本文把检测内核中的数据竞争漏洞拆分成了两个设计需求。

1. 找到一个执行RacePair_{cand}的程序。即找到一个多线程的用户态程序，每个线程能够在内核态分别执行到RaceRair_{cand}的指令。

2. 找到一个线程执行序列，使得这RacePair_{cand}的指令能并行执行。

需求1把问题做了简化，并不去考虑并行执行的问题，就不用考虑线程调度对分析的影响。需求2主要是去寻找一个交错执行的线程调度方案，使得RacePair_{cand}的指令能并行执行。现在的大部分工具都是只针对上述某一个需求的，而且都存在一定的局限性。

图2 工具架构

对于需求1，Google的内核Fuzz工具Syzkaller会随机生成一系列的系统调用，随机组合成多线程程序，然后运行。但不会考虑线程调度对程序运行的影响。而且纯随机的生成系统调用使得其效率较低。

对于需求2，有一些关注线程交错执行随机化地工作，比如 SKI和PCT 算法。这些工具对于给定的一个程序，会去探索所有可能的线程交错执行序列来执行这个程序。但其缺点是这些工具的算法随机性都比较强，效率不高。因为在这个研究课题的场景下，我们只需要关心RacePair_{cand}指令的线程调度情况，其他指令的执行顺序不是我们所关注的。

下面介绍本工作的设计思路。

Razzer结合使用了静态分析和动态分析的方法。先通过静态分析得到内核中潜在的存在数据竞争的代码RacePair_{cand}。之后会进行两阶段的动态分析，第一阶段进行单线程Fuzz,找到一个能执行到RacePair_{cand}的用户态程序。然后按照算法将这个程序转化为一个多线程程序（满足条件一）。第二阶段是多线程Fuzz。会寻找特定的线程交错，使得在执行多线程程序时能并行执行RacePair_{cand}。如果找到了，则获得了一个RacePair_{true}。Razzer还会检测内核是否出现了错误，如果RacePair_{true}在程序后续执行过程中，导致了内核错误，则得到一个RacePair_{harm}。整个工具的架构如图2所示。

图3 转化算法

以下是一些设计上的细节问题：

1. 静态分析:文中使用了Point_to分析来寻找内核中对同一个结构体的内存访问。但传统的Point_to分析具有误报率高，复杂度高的缺陷。对于静态分析的结果，Razzer会通过后续的动态分析来确认，以避免误报。在性能上，本文基于一定的insight，对内核代码进行了分部分分析，以减小分析的代码量。

2. 线程调度:待Fuzz的内核运行在虚拟化的环境中，为了控制虚拟CPU的调度，作者修改了虚拟环境的Hypervisor，增加了以下功能：为每个虚拟CPU设置断点，精确地控制在恢复执行时哪个线程的访存语句先执行，不同的执行顺序会导致后续是否存在错误行为，新的Hypervisor给Razzer提供了准确控制CPU调度的能力。

3. 多线程Fuzz:这一步的关键是将单线程Fuzz输出的一个单线程程序Pst，转化为一个多线程版本Pmt。在转换过程中还会进行一些插桩，与Hypervisor协作控制程序的调度。转化算法如图3所示。

当Pmt中的RacePair_{cand}指令都触发断点时，Razzer会检查访存指令的访问地址是否相同，如果相同，则判定为RacePair_{true}。可以注意到在Pmt的最后加入了一些随机的syscall，这是为了使数据竞争如果造成了恶性后果，程序会报错。当检测到一个RacePair_{true},会把结果反馈回生成算法，保持前面的代码不变，只修改后续随机添加的syscall，进行新的Fuzz。如果其中某个Pmt使kernel报错，则是一个RacePair_{harm}。

评价

Razzer最终发现了30个恶性的数据竞争漏洞。其中有16个已经被确认。数据竞争引起的漏洞往往难以复现，更难以找到原因并修复，Razzer生成的漏洞报告极大帮助了开发者对漏洞进行修复。此外作者还测量了工具的性能开销，并与最新的Fuzzing工具进行了比较。在可接受的额外开销下，能够更有效率地Fuzz这一类漏洞。

Razzer是一个专门Fuzz内核中数据竞争漏洞的工具，其亮点有两个：第一是通过静态分析得到一些RacePair_{cand},再用动态分析确认，即降低误报又减少了搜索空间。第二通过算法与工具的结合，给Fuzz工具提供了比较准确的线程并行执行状态，解决了Fuzz多线程程序的重大挑战，值得借鉴。