利用GPU构建高性能模糊测试器！

TL;DR：能否在使用云服务对嵌入式软件进行模糊测试时，通过GPU实现10倍性价比？基于初步研究，我们认为答案是肯定的！

模糊测试是一种通过向程序提供大量随机化输入来触发异常行为的软件测试技术。作为重要的行业标准技术，它已发现众多安全漏洞并预防了更多问题。然而，模糊测试耗时较长，且测试嵌入式软件面临额外挑战。

嵌入式平台并非为模糊测试所需的插桩和高吞吐量计算而设计。在没有源代码的情况下，对此类平台进行实际模糊测试需要模拟器（速度慢）或大量物理设备（通常不现实）。大多数模糊测试方法使用传统CPU架构或模拟器，但我们决定使用其他商用硬件——特别是GPU——来解决这个问题。近期机器学习热潮降低了GPU的非高峰期价格，并使所有主要云提供商都能提供大规模GPU计算能力。GPU非常擅长并行执行任务，而模糊测试正是易于并行化的问题。

本文将带您了解这款基于GPU的大规模并行模糊测试器的设计与实现。目前，我们已实现的执行引擎能够达到比libFuzzer高5倍的每秒每美元执行次数，且还有大量优化空间。

核心构想：用GPU进行模糊测试

模糊测试旨在生成程序的意外输入并引发不良行为（如崩溃或内存错误）。最常用的模糊测试器是覆盖引导式模糊测试器，其专注于发现导致新代码覆盖（如执行此前未执行的函数）的输入，以探索可能使程序崩溃的边缘情况。为此，模糊测试器通过目标程序运行许多不同的随机化输入。该任务易于并行化，因为每个输入可以独立于其他输入执行。

GPU相当便宜：在Google Cloud上，可抢占式Tesla T4的价格为0.11美元/小时。此外，GPU非常擅长并行执行多项任务——Tesla T4可以在超过40,000个线程之间进行上下文切换，并能同时并行执行2,560个线程——而且如前所述，模糊测试是天然可并行化的问题。使用数千个线程，理论上我们应该能够同时测试数千个不同的输入。

为何此前无人尝试？

简而言之，在GPU上运行代码与在CPU上运行代码在几个关键方面有很大不同。

首先，GPU无法直接执行x86/aarch64等指令，因为GPU有自己的指令集。我们的目标是对没有可用源代码的嵌入式软件进行模糊测试。由于只有二进制文件，我们无法轻松生成要运行的GPU汇编代码。

其次，GPU没有操作系统。传统的并行模糊测试器启动多个进程，这些进程可以单独执行输入而不会相互干扰。如果一个输入导致一个进程崩溃，其他进程不会受到影响。GPU没有进程或地址空间隔离的概念，任何内存违规都会导致整个模糊测试器崩溃，因此我们需要找到某种方法来隔离被测试程序的并行实例。

此外，没有操作系统，就没有实体来响应系统调用（这些调用使程序能够打开文件、使用网络等）。系统调用必须被模拟或中继回CPU由主机操作系统执行。

最后，GPU内存难以有效管理。GPU具有复杂的内存层次结构，包含几种不同类型的内存，每种内存的易用性和性能特征各不相同。性能高度依赖于内存访问模式，控制线程何时以及如何访问内存可以成就或破坏应用程序。此外，可用内存不多，这使得正确管理内存布局和访问模式更加困难。拥有16GB设备内存可能听起来令人印象深刻，但将其分配给40,000个执行线程后，每个线程仅剩419 KiB。

我们能构建它吗？是的，我们能！

构建可工作的GPU模糊测试器存在许多障碍，但都不是不可逾越的。

通过二进制翻译执行代码

首先，让我们看看是否能让aarch64二进制文件在GPU上运行。

如前所述，我们希望在GPU上对嵌入式二进制文件（如ARMv7、aarch64等）进行模糊测试。NVIDIA GPU使用称为PTX（“并行线程执行”）的不同指令集架构，因此我们不能直接执行要模糊测试的二进制文件。此问题的常见解决方案是模拟嵌入式CPU，但为GPU开发CPU模拟器可能是一项昂贵的投资，且性能不佳。另一种替代方案是将二进制文件翻译为PTX，以便它们无需模拟即可直接在GPU上执行。

Trail of Bits开发了一个名为Remill的二进制翻译工具，我们可以用它来做这件事。Remill将二进制文件“提升”为LLVM IR（中间表示），然后可以重新定位并编译为LLVM项目支持的任何架构。碰巧的是，LLVM支持将LLVM IR作为PTX代码发出，这非常适合我们的目的。

假设我们有一个简单的示例函数，它将w19设置为0，加5，然后返回结果：

1
2
3
4
5

main:
    mov w19, #0       // 将数字0存储在寄存器w19中
    add w19, w19, #5  // 加5
    mov w0, w19       // 返回结果
    ret

我们可以将这些指令的字节传递给Remill，它会产生模拟在ARM处理器上执行原始程序的LLVM IR：

1
2
3
4
5
6

// 为简洁起见简化了 :)
define dso_local %struct.Memory* @_Z5sliceP6MemorymPm(%struct.Memory* readnone returned %0, i64 %1, i64* nocapture %2) local_unnamed_addr #0 {
  %4 = add i64 %1, 1
  store i64 %4, i64* %2, align 8, !tbaa !2
  ret %struct.Memory* %0
}

然后，通过一些优化，我们可以让LLVM将上述LLVM IR编译为PTX汇编：

1
2
3
4
5
6
7

ld.param.u64  %rd1, [sub_0_param_0];
ld.param.u64  %rd2, [sub_0_param_1];
mov.u64       %rd4, 5;
st.u64        [%rd1+848], %rd4;
add.s64       %rd5, %rd2, 12;
st.u64        [%rd1+1056], %rd5;
ret;

最后，我们可以将此PTX加载到GPU中并执行它，就像我们一开始就有源代码一样。

管理内存

如前所述，GPU没有操作系统来提供进程间的隔离。我们需要实现地址空间隔离，以便被测试程序的多个实例可以访问同一组内存地址而不会相互干扰，并且我们需要检测目标程序中的内存安全错误。

Remill用对特殊函数read_memory和write_memory的调用替换了原始程序中的所有内存访问。通过提供这些函数，我们可以实现一个软件内存管理单元，以填补缺失的操作系统功能并中介内存访问。

例如，考虑这个接受指针并递增其所指整数的函数：

1
2
3
4
5

add_one:
ldr w8, [x0]   // 加载指针所指的值
add w8, w8, #1 // 递增该值
str w8, [x0]   // 将新值写回
ret

Remill将此汇编翻译为以下包含read_memory调用、add指令和write_memory调用的IR：

1
2
3
4
5
6
7

define %struct.Memory* @slice(%struct.Memory*, i64 %X8, i64* nocapture %X0_output) local_unnamed_addr #2 {
%2 = tail call i32 @__remill_read_memory_32(%struct.Memory* %0, i64 undef) #3
%3 = add i32 %2, 1
%4 = tail call %struct.Memory* @__remill_write_memory_32(%struct.Memory* %0, i64 undef, i32 %3) #3
%5 = tail call %struct.Memory* @__remill_function_return(%struct.State* nonnull undef, i64 16, %struct.Memory* %4) #2, !noalias !0
ret %struct.Memory* %5
}

通过提供__remill_read_memory_32和__remill_write_memory_32函数，我们可以为每个线程提供自己的虚拟地址空间。此外，我们可以在无效访问导致整个模糊测试器崩溃之前验证内存访问并拦截无效访问。

但请记住，当在40,000个线程之间共享时，16GB的设备内存实际上并不算多。为了节省内存，我们可以在MMU中使用写时复制策略；线程共享相同的内存，直到其中一个线程写入内存，此时该内存被复制。以这种方式节省内存一直是一种出乎意料的有效策略。

初始性能

太好了——我们有了可行的东西！我们可以获取二进制程序，将其翻译为LLVM，转换为PTX，混入MMU，并在数千个GPU线程上并行运行结果。

但是，我们在实现构建比其它模糊测试器性价比高10倍的模糊测试器的目标方面表现如何？

评估模糊测试器是一项非常棘手的工作，并且已经发表了许多关于如何有效比较它们的论文。我们的模糊测试器还太年轻，无法正确评估，因为我们仍然缺少关键的模糊测试器组件，例如用于生成程序新输入的变异器。为了仅测量执行器性能，我们可以查看模糊测试器通过目标程序运行输入的速度（以每秒执行次数计）。通过归一化计算硬件的成本（GPU比其它模糊测试器运行的CPU更昂贵），我们可以比较每秒每美元执行次数。

在我们的基准测试中应该模糊测试什么？来自libpcap的BPF数据包过滤代码似乎是一个很好的候选者，原因如下：

• 它实现了一个复杂的状态机，人类难以推理，使其成为模糊测试的良好候选者。
• BPF组件过去曾存在错误，因此这是一个我们可能想要模糊测试的现实目标。
• 它没有系统调用（我们的最小模糊测试器尚不支持系统调用）。

让我们编写一个测试应用程序，从模糊测试器获取数据包并对其运行复杂的BPF过滤程序：

1
2

dst host 1.2.3.4 or tcp or udp or ip or ip6 or arp or rarp
or atalk or aarp or decnet or iso or stp or ipx

这个测试程序并没有做很多事情，但它确实执行了复杂的逻辑并需要大量的内存访问。

为了评估我们的模糊测试器，我们可以将其与libFuzzer（一个快速且广泛使用的模糊测试器）进行比较。这并不是完全公平的比较。一方面，libFuzzer解决了一个更简单的问题：它使用测试程序的源代码进行模糊测试，而我们的模糊测试器翻译并检测为不同架构编译的二进制文件。在安全研究中，源代码通常不可用。另一方面，libFuzzer执行变异以生成新输入，而我们没有这样做。虽然显然不完美，但这种比较足以提供数量级估计。

我使用Google Compute Engine 8核N1实例（在撰写本文时，非抢占式实例为0.379998美元/小时）和Tesla T4 GPU（在撰写本文时为0.35美元/小时）运行了此比较。

不幸的是，我们的模糊测试器与libFuzzer相比表现不佳。libFuzzer达到5.2M execs/s/$，而我们的模糊测试器仅达到361K execs/s/$。

让我们看看能否做得更好……

内存交错

在开始优化性能之前，我们应该对模糊测试器进行分析，以更好地了解其性能。Nvidia的Nsight Compute分析器有助于解释硬件利用率和性能瓶颈。

从分析中，我们可以看到GPU仅使用其计算能力的3%。大多数时候，GPU计算硬件处于空闲状态，什么都不做。

这通常是由于高内存延迟造成的：GPU正在等待内存读/写完成。然而，这并不是因为我们的模糊测试器需要访问太多内存；分析显示GPU仅使用其可用内存带宽的45%。相反，我们必须非常低效地访问内存。每次内存访问都需要很长时间，并且没有为计算提供足够的数据。

要解决此问题，我们需要更好地了解GPU的执行模型。

GPU线程以称为warp的32个线程组执行。warp中的所有线程在并行多处理器中一起执行，并且它们以锁步方式运行，即它们同时运行相同的指令。

当线程读取或写入内存时，内存访问以128字节块进行。如果warp中的32个线程尝试读取位于同一128字节块中的内存，则硬件只需要向内存总线请求一个块（一次“事务”）。

但是，如果线程各自从不同的块读取内存地址，则硬件可能需要进行32次单独的内存事务，这些事务通常是串行化的。这导致了我们在分析中发现的行为：计算硬件几乎总是空闲的，因为它必须等待如此多的内存事务完成。内存带宽利用率看起来并不那么糟糕，因为正在读取许多128字节块，但每个块中实际上只使用了四或八个字节，因此使用的带宽大部分被浪费了。

目前，我们为每个线程分配单独的内存，因此当线程访问内存时，它很少会与不同线程落入相同的128字节块。我们可以通过为warp（32个线程）分配一块内存，并在该warp内交错线程的内存来改变这一点。这样，当线程需要从内存访问值时，它们的值都彼此相邻，并且GPU可以通过单次内存事务完成这些内存读取。

尝试这一点，我们发现性能提高了一个数量级！显然，在为GPU编程时，注意内存访问模式极其重要。

减少数据传输和内核启动

重新运行分析器，我们可以看到我们获得了更好的计算利用率（33%，从3%上升），但我们仍然远未达到完全利用率。我们能做得更好吗？

继续检查内存使用模式，让我们看看使用的内存类型。Nvidia GPU有几种位于不同物理位置的内存类型，但最容易使用的类型称为“统一内存”，它会自动代表我们在不同物理位置之间传输数据。我们一直在使用这个，因为它不需要我们过多考虑字节的物理存储位置，但如果管理不当，它可能导致性能瓶颈，因为数据会在物理内存位置之间低效传输。

由于我们仍然看到非常高的内存延迟，让我们仔细看看这些传输。

我们的简单模糊测试器以“轮次”工作：如果GPU可以运行40,000个线程，我们向GPU传递40,000个输入，每个线程在启动下一轮之前对一个输入进行模糊测试。在轮次之间，我们重置使用的内存（例如，覆盖跟踪数据结构和被测试程序使用的内存）。然而，这导致在每轮之间GPU和CPU之间存在显著的数据传输，因为内存被分页回CPU，重置，然后分页回GPU。当这些传输发生时，GPU什么都不做。当GPU等待CPU启动下一轮时，会产生额外的延迟。

我们可以通过单次启动GPU代码并避免CPU和GPU之间的同步来改进此设置。大部分数据不需要在统一内存中；我们可以改为在GPU上分配全局内存，然后在需要发送关于模糊测试进度的信息（例如，哪些输入导致崩溃）时异步将数据传输到CPU。这样，当线程完成对一个输入的模糊测试时，它可以重置内存并处理下一个输入，而无需数据传输开销，也无需等待CPU。

这实现了几乎又一个数量级的加速！现在，模糊测试器每美元比libFuzzer快大约五倍。

这是非常有前途的——尽管我们的模糊测试器缺少变异引擎并且无法处理系统调用，但以这种程度超过libFuzzer的性能表明，使用GPU进行模糊测试可能对某些应用非常有用。

GPU基于模糊测试的下一步是什么？

尽管我们接近了这个测试程序的性能目标，但项目还有很长的路要走。硬件利用率仍然很低，因此还有更多优化的空间。

此外，我们需要构建处理系统调用的支持，这在模糊测试I/O密集型应用程序时可能会产生显著的性能影响。我们还需要构建变异引擎，然后这个模糊测试器才能有用，尽管这个问题比构建执行引擎更容易理解。

尽管如此，我们非常兴奋在开发的如此早期阶段就获得如此有希望的结果。我们期待在模糊测试嵌入式二进制文件方面实现数量级的改进。

我们很想听听您对这项工作的想法！通过ryan@reberhardt.com或artem@trailofbits.com与我们联系。

最后，衷心感谢Artem Dinaburg设计了该系统的初始设计并在整个项目中指导我。同时，感谢Peter Goodman提供设计反馈和调试建议。