利用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线程以32个为一组执行，称为一个warp。warp中的所有线程在并行多处理器中一起执行，并且它们同步运行，即，它们同时运行相同的指令。

当线程读取或写入内存时，内存访问以128字节块发生。如果warp中的32个线程尝试读取位于相同128字节块中的内存，那么硬件将只需要从内存总线请求一个块（一个“事务”）。

然而，如果线程各自从不同的块读取内存地址，硬件可能需要