Hopper: Interpretative Fuzzing for Libraries——论文阅读

摘要

problem 1：虽然目前最先进的fuzzers能够有效地生成输入，但是现有的模糊驱动程序仍然不能全面覆盖库的入口。(entries in libraries，库中的不同条目或入口点。包括调用库中的函数、使用库中的类等)

problem 2：大多数模糊驱动程序都是开发人员手工制作的，它们的质量取决于开发人员对代码的理解。虽然现有工作尝试通过从代码和执行轨迹学习API使用来自动生成模糊驱动程序，但生成的模糊驱动程序被学习的代码限制在几个特定的调用序列中。

Hopper：为了解决上述挑战，作者提出了Hopper。它可以模糊库，而不需要任何领域知识来制作模糊驱动程序。它将库模糊化问题转化为解释器模糊化问题。与被测库链接的解释器可以描述任意API用法的输入。为了为解释器生成语义正确的输入，Hopper学习库中API内（Intra-API）和API间（Inter-API）的约束，并通过语法意识改变程序。

成果：实现了Hopper，并在11个现实世界的库上评估了它对手工制作的模糊器和其他自动解决方案的有效性。研究结果表明，Hopper在代码覆盖率的漏洞挖掘方面远远优于其他模糊器，发现了之前其他模糊器未能发现的25个漏洞。此外，还证明所提出的API内和API间约束学习方法可以正确地学习库中隐含的约束，因此，显著提高模糊效率，Hopper能够探索广泛的API用法。

一、介绍

fuzzing是用于发现软件漏洞的最流行的技术之一。它通过给予软件大量的随机输入来观察是否发生意外行为(unexpected behaviors)。

基于覆盖率的灰盒模糊器(Coverage-based grey-box fuzzer)，例如AFL和LibFuzzer，它可以改变输入以探索更深层次的程序状态，而无需了解输入格式或程序规范。
基于约束的灰盒模糊器(Constraint-based grey-box fuzzers)，采用约束求解技术来达到复杂约束保护代码分支。

在库模糊测试中，模糊驱动程序在调用API时需要传入正确的参数类型，并满足API内和API间的约束，否则可能发生意外崩溃。

举个例子：测试c-ares库中的ares_send(ares_channel channel, char *qbuf, int qlen, ares_callback callback, void *arg)函数
约束一，为了满足外部API的约束，需要调用ares_init()函数初始化参数channel。
约束二，内部API约束要求第三个参数 qlen 应该设置为第二个参数 qbuf 的长度，同时第四个参数 callback 应该是一个非空函数指针，并且具有 ares_callback 类型。所以需要按这些要求对这些参数进行一个设置。

# 测试打印字符数组的函数
# 该函数的外部约束就是第一个参数需要时char类型的数组，
# 内部约束就是length为数组a的长度
void print(char a[], int length) {
	for (int i = 0; i < length; i++) {
		printf("%c", a[i]);
	}
}

任何一个违反上述约束的行为，都可能会导致程序崩溃。

problem 1：在实践中，关于这些约束的信息要么缺失，要么分散在库文档或注释中，使得很难以全自动的方式收集它们。

• 自动生成模糊驱动程序的方法：

  • 基于学习的方法(Learning-based methods)：例如FuzzGen试图从现有的消费者代码(consumer code)中学习API的正确用法，但当消费者代码不可用(Consumer code is unavailable)(例如对新的或者正在进行的库)，该方法无效。
  • 基于模型的方法(Model-based methods)：例如GraphFuzz，要求用户提供测试API的规范，这需要特定领域的知识和大量人工参与。
  • 此外，用这两种方法生成的模糊驱动程序的质量在很大程度上受外部输入的影响，这些输入可能是不完整或不准确的，模糊驱动程序可能会因为这些输入发生虚假崩溃(spurious crashes)。

• $概念补充$：

  • 生产者代码：生产者代码是实现和提供某个功能或服务的代码。这可以是一个库、框架、服务等。
  • 消费者代码：消费者代码是使用生产者代码提供的功能的代码。这些代码调用、调用或“消费”生产者代码，以在自己的应用程序中实现特定的功能或服务。

solution：作者提出了Hopper在不需要外部知识的条件下模糊测试API。受基于覆盖率的模糊测试的启发，它从变异的随机种子中学习有效的格式。
Hopper从变异API的调用及其参数的组成中学习API的潜在用法。如果执行变异的程序触发了新的路径或崩溃，Hopper会根据动态反馈推断API内和API间的约束。
为了实现这一点，引入了一个特定领域的语言（Domain-Specific Language，DSL）用于描述任意的API用法。DSL输入可以通过一个轻量级解释器与正在测试的库链接并解释。通过这种方式，将库模糊测试转化为解释器模糊测试。模糊器负责生成以DSL格式编码的程序，将其提供给解释器。然后，解释器执行这些程序，以查看是否发生了意外的行为。

二、背景

2.1 库的模糊测试

problem：由于库在各种程序中被广泛使用，所以保护库的安全也十分重要。但仅对程序进行模糊测试来测试库是不完全的。因为程序可能在复杂的路径约束条件下调用库的API，或者使用特定的参数调用库的API，这使得这些API很难被完全测试到。

• 为了解决这个问题，已经出现了专门的模糊测试工具来测试库，例如，LibFuzzer。LibFuzzer测试库的必要步骤如下：
  • 制作模糊驱动程序(Craft a fuzz drivers)：一个高质量的模糊驱动程序应该提供一个入口，以探索库中尽可能多的代码进行彻底的测试。
      具体的执行路径不仅由API调用中的参数决定，还由调用它们相关的API决定。这些相关的API可以返回值作为参数，或者影响依赖于它们的其他API的上下文（例如，全局值）。
      显然枚举所有有效的API是耗时且具有挑战性的。所以模糊驱动程序只包含一些常见的API用法。
      此外，由于不同的API使用具有不同的模糊搜索空间，因此将它们全部按顺序放置将是低效的。但将它们写入多个模糊驱动程序或在单个模糊驱动程序中有条件地执行它们会更有效。
    • 例如下图：虽然这些库被广泛的使用，但是开发者只将其中少部分API写入了模糊驱动程序。
  • 指定输入格式(Specify the format of input)：由于LibFuzzer生成的字节流是盲目的，这使得创建满足API内的约束的结构化输入变得困难。所以我们需要指定输入格式，引导模糊测试工具生成超出字节数组的参数。
      FuzzedDataProvider 能够将模糊输入分成多个不同类型的部分，而 libprotobuf-mutator可以基于提供的语法生成结构化的输入。然而，内部 API 约束的存在使得定义用于模糊测试的潜在参数范围变得非常庞大的任务。因此，开发者可能会选择将参数直接编码为字面常量，嵌入到模糊测试驱动程序中。
      例如下图cJSON_ParseWithOpts的第二个参数，但方法可能导致对API函数的测试不充分。
    

2.2 模糊测试解释器

• 语法感知的灰盒模糊测试在解析输入的程序中取得的成功，尤其是在解释器中。模糊测试解释器的成功归纳于以下两个关键技术。
  • 语法感知输入变异(Grammar-aware input mutation)：盲目变异的输入可能被解析过程(parsing procedure)拒绝，而结构化的输入可以达到更深的路径。语法感知的变异将输入解析为基于其编码语法的中间表示（IRs），并在遵循约束的同时对 IRs 进行变异。
  • 覆盖率反馈引导模糊测试(Coverage guided fuzzing)：在覆盖反馈的指引下，模糊器保留触发新路径的输入，并对其突变，以进入更深的分支或发现新的bug。
• 我么可以观察到，为库构造的模糊驱动程序类似于为输入实现一个解释器，对解释器进行模糊测试等同于等同于在底层对库进行模糊测试。

三、设计

3.1 概述

Hopper将库的模糊测试问题转化为解释器模糊测试问题。Hopper主要由两个主要组件组成：
  语法感知模糊器(grammer-aware fuzzer)：生成DSL格式的输入，或对解释器的反馈进行变异生成DSL格式的输入，然后送入解释器。
  轻量级的解释器(lightweight interpreter)：输入DSL格式的输入，执行，然后输出一个反馈。

  模糊器为了调用库的API生成高质量的输入。它首先从库的头文件中提取函数声明和类型定义，通过利用这些信息，Hopper通过API函数和参数的随机组合生成一系列API调用。
  解释器使用输入并调用库API。在编译阶段，被测库与解释器相链接，在链接之前，Hopper对二进制文件进行检测，以捕获执行期间的内部状态。

3.2 DSL和输入解释

为什么要在Hopper中引入DSL和轻量级解释器？
  开发模糊驱动程序所使用的编程语言通常和被测库的编程语言一致。因此，对于像C/C++这样的编译语言，模糊驱动程序在模糊测试前就需要被编写和编译。在每一轮模糊测试的过程中，只有输入字节会被改变。为了在模糊测试过程中替换API调用序列，同时避免编译开销，所以在Hopper中引入了DSL和一个轻量级解释器，来加速整个过程。

3.2.1 DSL

为了通用性，Hopper中的解释器将DSL程序作为输入。每个DSL程序都包含语句作为其最基本的组件，每个语句都有一个唯一的索引，后继的语句可以引用它。

• 作者在DSL中将MCF中发现的常见模糊行为分为五种语句类型：
  • Load Statement：load语句定义值的类型和文本表现形式。强类型允许直接以特定类型生成输入数据，这消除了从未知类型的字节流输入转换为输入数据类型的要求。
  • Call Statement：call语句通过提供函数名和参数列表来调用库中的特定API函数，其中每个参数引用了load语句定义的变量。
  • Update Statement：update语句在运行时重写了call语句的返回值。
  • Assert Statement：assert语句在运行时检查call的返回值。如果断言失败，程序立即退出。(例如，调用者需要简介引用返回值，但这个返回值时null)
  • File Statment：file语句为I/O操作指定有效的文件资源。如果file语句被用于reading，那么会在运行时在文件中填充一系列随机字节以供读取。

  此外，为了保持语法简单，作者的DSL不支持条件语句。某些模糊驱动程序使用条件语句来选择不同的API函数或参数。相比之下，Hopper生成不同的DSL程序来枚举这些API函数或参数。

3.2.2 解释器

  解释器解析DSL程序，并在执行每条语句后监视程序的状态。为了而调用库API，Hopper在编译阶段将解释器与测试中的库链接起来。
  解释器还构建了一个映射表，根据库的头文件将每个函数的名称与它的调用方（如主函数）关联起来。在程序执行期间，调用方将值转换为被调函数所需的参数类型，然后执行。
  在链接解释器之前，Hopper使用计算分支的代码以及挂钩 (hooks) 比较指令和资源管理函数(例如malloc，free和fopen)来对库二进制文件进行插装。

• 然后，解释器在运行时收集以下反馈。
  • 可选的分支跟踪(optional branch tracking)：Hopper定义了一个全局标志来保护分支跟踪代码。该标志的值由DSL输入确定，当调用以问号 ? 结尾的API函数时(如下图13行)，解释器为该调用启动分支跟踪。
    
  • 上下文敏感的代码覆盖率(Context-sensitive CodeCoverage)：为了区分不同API访问相同分支的情况，解释器将当前API函数名称的哈希设置为与上下文相关的。这样，每个API函数都有一个唯一的上下文哈希。插装代码读取上下文，并为每个API计算一个独特的代码跟踪(code trace)。
      通过为每个API计算不同的代码跟踪，解释器能够跟踪和监视多个API的执行情况，并区分它们之间的代码访问路径。这有助于分析和理解各个API的行为以及它们对程序状态的影响。
  • 溢出检测(Overflow Detection)：当一个语句加载一个大小可变的值（如数组）时，解释器会将这些值存储在内存区域，并附加一个canary标记来检测肯恩那个泄露的缓冲区。
  • 释放后使用检测(Use-after-free Detection)：解释器通过插桩维护一个由malloc分配和free释放的内存块。对于函数参数中使用的每个指针，如果该指针指向的内存块被释放，解释器立即退出程序，以避免释放后使用的问题。
  • 比较挂钩(Comparison Hooking)：解释器收集比较指令和函数中使用的参数，以指导模糊器解决魔法字节 (magic bytes)。在模糊测试中，解决或正确处理这些“魔术字节”通常是一个重要的目标，因为它们可能作为特定条件的标识或触发特定行为的关键。

LibFuzzer使用的模糊驱动程序很难生成一个在推出之前重置所有资源的程序，而Hopper解释器通过在单个进程中运行每个输入来解决这个问题。

3.3 语法感知的输入模糊

为了在库而不是解释器中找到错误，Hopper专注于生成各种有效的API调用。该过程包括两个阶段，如下图所示，首先，Hopper根据函数签名中的可用信息生成输入，以初始化种子池。其次，Hopper在种子库中选择输入，并在覆盖反馈的指导下变异它们。

• 试点阶段(Pilot Phase)：Hopper绘制输入的概况并推断约束。最初，种子池不包含任何输入。因此，Hopper尝试根据每个API函数的声明为它们生成简单的输入，并从中学习约束。
    为了实现这一点，Hopper选择库中的一个API函数作为目标，并尝试为其随机生成一个调用语句，这包括生成参数和插入引用必要上下文的相关调用。这些语句最终形成一个输入，然后由解释器执行。
    如果输入触发了库中的新路径而没有崩溃，Hopper会将其保存到种子池中以进行进一步的突变。
• 进化阶段(Evolution Phase)：Hopper从种子池中选择一个输入并基于它们的类型随机变异语句。在执行分支覆盖率的指导下，Hopper保留了突变的可以探索更深层次代码和找到更多漏洞的输入。Hopper变异程序语句有以下五个步骤：
  • 1. Hopper从种子池中选取具有优先级的种子，因为新种子更有可能探索到更深的路径，所以给与新种子更高的选择优先级。
  • 2. Hopper选择根据种子的权重从从输入种子中选择要变异的语句。断言、文件和更新(assert、file、update)语句的权重被设置为0且不变异，而加载和调用(load、call)语句的权重由他们的复杂度决定。
  • 3. Hopper通过响应的策略变异加载语句和调用语句，如3.3.1和3.3.2节所述。
  • 4. Hopper根据在模糊测试的过程中学到的约束优化输入以正确的使用API。如3.4节所述。
  • 5. Hopper通过移除对探索路径且增加了变异的搜索空间的冗余语句使得输入最小化。正如3.3.3节所述。

3.3.1 调用语句的变异策略(mutation strategies for call statements)

  1. 将其中一个参数替换为保持相同类型的参数(Line 4 tp Line 24 in Algorithm 1)。
  2. 在目标调用前插入一个新call语句(Line 27 to Line 29 in Algorithm 1)。插入的call可以修改目标调用的参数值或更改库的全局状态。Hopper通过分支反馈来确定插入调用的有效性。(详情见3.4.2节)。
  3. 更新call的返回值，在call之后插入一个update语句，使用新值覆盖部分旧值。

3.3.2 类型感知的值变异 (type-aware value mutation)

  由于库经常使用各种参数类型，包括自定义复合类型，因此Hopper在调用相应API时需要为这些参数生成适当的类型。值变异也是如此，根据值的类型进行变异能够更有效地探索新的状态。为了实现这一点，Hopper解析类型定义(例如，struct、union和enum)，并递归地在头文件中输入别名。

• Hopper使用以下规则来生成新类型的值。
  • 基本类型(Primitive Types)：几乎所有的基本类型都是数值类型。因此Hopper生成的数字在一个小范围内均匀分布。Hopper采用下面四种方法之一实现值突变。
    • 设置一个有趣的值(interesting value)。
    • 翻转一位或一个字节
    • 加减一个小数字
    • 如果该值用作比较指令的操作数之一，Hopper将其设置为从该比较中收集的字面值。即，Hopper可能会分析程序的比较指令，并使用其中涉及的字面值进行变异。
      有趣的值：在测试或分析过程中，具有特殊或边缘情况行为的特定数值。这些值被选择用于测试程序的极端情况，以确保程序在各种情况下都能正确工作。
  • 数组(Array)：基于数组的长度和元素类型，Hopper生成一个元素序列。如果长度可变，Hopper首先随机选择一个长度。在编译过程中，Hopper选择一个或多个元素，分别对它们进行变异。此外，如果数组的长度不固定，Hopper可以通过删除或插入来调整数组的大小。
  • 结构类型(Structure)：具有自定义结构类型的值是通过递归生成其字段来创建的，当改变自定义结构值时，Hopper随机选择结构中的一个字段，并根据其类型突变它。
  • 简单指针(Trivial Pointer)：简单指针是指那些揭示指针类型布局的指针，即指向基本数据类型和结构类型的指针。Hopper 通过以下方法来变异它们：
    • 1. 设置为空指针
    • 2. 指向有相同类型的现有语句的地址
    • 3. 指向新生成的数组，其元素类型与被指对象相同
    • 4. 指向新生成的调用语句返回值的地址。call语句返回相同的指针类型。
  • 非凡指针(Nontrivial Pointer)：例如不透明指针，空指针和函数指针，由于其不可预测的性质，不能直接变异。
    • 不透明指针(opaque pointers)：Hopper通过返回指针或通过引用填充指针来检索初始化指针的API函数。
    • 空指针(void pointers)：有别名类型，Hopper将他们视为不透明指针，否则，Hopper尝试将任意长度的字节数组强制转换为所需的空指针，以查看它是否有效(详情见3.4.1节)。
    • 函数指针(funtion pointers)：Hopper在编译阶段合成具有所需签名的空函数，以允许模糊器使用让它们的地址作为指针。
  • 此外，字节数组可能包含具有自己编码的数据，这在头文件中没有定义。

3.3.3 输入最小化(Input Minimization)

3.4.2 API间的约束