Angora: Efficient Fuzzing by Pri

2021-09-10 本文已影响0人佩玖吟

Abstract

不使用符号执行来解决路径约束，从而增加分支覆盖率。为了有效地解决路径约束，我们引入了几个关键技术：可扩展的字节级污点跟踪，上下文敏感的分支计数，基于梯度下降的搜索和输入长度探索。

Design

使用上下文敏感的分支覆盖作为覆盖的度量。每次 fuzzing，Angora 选择一个未探索的分支并搜索探索该分支的输入。

对于大多数条件语句，其判断仅受输入中的几个字节的影响，因此改变整个输入将是徒劳的。因此，在探索分支时，Angora会确定哪些输入字节流入相应的判断，并专注于仅改变这些字节
确定要改变的输入字节后，将分支上的路径约束视为输入上黑盒函数的约束，并且我们调整梯度下降算法来解决约束
在梯度下降期间，我们对黑盒函数的参数进行评估，其中一些参数由多个字节组成
仅仅改变输入中的字节是不够的。只有在输入超过阈值后才会触发一些错误，Angora 对程序进行插桩，检测什么时候较长的输入能够探索新分支并且确定所需的最小长度

上下文敏感的分支计数

元组： $(l_{prev},l_{cur},context)$

除了分支前后基本块的 ID，context 是 $h(stack)$ ，h 是哈希函数，stack 包含调用栈的状态。

因为上下文改变之后到达同一个分支可能触发新的内部状态。

目前的实现是使用 h 计算所有调用位置 ID 的异或，当 Angora 对程序插桩时，它会为每个调用点分配一个随机 ID。

字节级污点跟踪

Angora 的目标是创建能够执行未被探索的分支的输入。当它尝试执行未探测的分支时，它必须知道输入中的哪些字节偏移影响分支的判断。因此，Angora需要字节级别的污点跟踪。

Angora将程序中的每个变量x与污点标签tx相关联，污点标签tx表示输入中可能流入x的字节偏移量。污点标签须支持的操作：

INSERT(b)：插入位向量b并返回其标签。
FIND(t)：返回污点标签t的位向量。
UNION(tx; ty)：返回污点标签，表示污点标签tx和ty的位向量的并集。

不可行的实现：

将污点标签表示为位向量，位 i 表示输入的第 i 个字节，那么大输入就会是禁止的。
将位向量存储在表中，使用索引作为污点标签，但是 union 代价会很高，union 首先找到两个标签的位向量并计算并集 u，接下来会搜索表确定 u 是否已经存在，代价很高。

新的数据结构，为每个位向量分配唯一标签（无符号整数）：

二叉树将位向量映射到其标签，每个位向量 b 由 level $|b|$ 的唯一节点 $v_b$ 表示，其中 $|b|$ 为 b 的长度。 $v_b$ 存储 b 的标签，从根到达 $v_b$ ，如果节点值为 0，向左搜索，否则向右。每个节点都包含一个指向父节点的指针，使我们可以提取出位向量。
查找表将标签映射到其位向量。标签是该表的索引，相应的条目指向表示该标签的位向量的树节点。

INSERT：

删除向量的所有尾随 0
跟踪向量中的位，如果为 0，遍历左子树，为 1，遍历右子树，如果不存在，创建新节点
将向量标签存储在最后一个节点中

基于梯度下降的搜索算法

字节级污点跟踪发现了输入的哪些字节流入条件语句。但是如何改变输入以运行未探索的分支语句？

将分支的判断看作黑盒函数 $f(x)$ 的约束， $x$ 是输入中流入判断的值的向量， $f()$ 捕获从程序开始到此判断的路径的计算， $f(x)$ 有三种约束：

$f(x) < 0$
$f(x) <= 0$
$f(x) == 0$

如果包含逻辑运算 $$ 或者 ||，Angora 将语句拆分成多个条件语句，如 if (a && b) { s } else { t } 拆分为 if ( a ) { if ( b ) { s } else { t }} else { t }

形状和类型推断

对于形状推断，最初输入中的所有字节都是独立的。在污点分析期间，当指令将输入字节序列读入变量，其中序列的大小与基本类型的大小匹配（如 1，2，4，8 字节），Angora 标记这些字节输入相同值。当冲突发生时，Angora 使用最小的 size。

对于类型推断，Angora 依赖于对值进行操作的指令的语义。如果指令对有符号整数进行操作，那么 Angora 将相应的操作数推断为有符号整数，当相同的值同时用作有符号和无符号类型时，Angora 将其视为无符号类型。

输入长度探索

与大多数其他模糊器一样，Angora开始使用尽可能小的输入进行模糊测试。但是，仅当输入长于阈值时才执行某些分支。这给模糊器带来了两难境地。如果模糊器使用太短的输入，则无法探索这些分支。但如果它使用太长的输入，程序可能运行缓慢甚至内存不足。

在污点跟踪期间，Angora 将类似 read 的函数调用中的目标内存输入中的相应字节偏移相关联。它还使用特殊标签标记来自读取调用的返回值。如果在条件语句中使用返回值并且不满足约束，则Angora会增加输入长度，以便读取调用可以获取它请求的所有字节。

Implementation

插桩

Angora 通过 LLVM Pass 来对程序进行插桩。插桩

收集条件语句的基本信息，并通过污点分析将条件语句链接到其对应的输入字节偏移。
记录执行 trace 以识别新输入
在运行时支持上下文
在判断时收集表达式值（梯度下降）

为了支持可扩展的字节级污点跟踪，我们通过扩展 DataFlowSanitizer (DFSan) 为 Angora 实现了污点跟踪。我们为 FIND 和 UNION 操作实现了缓存机制，显著加快了污点跟踪。

Angora 依赖于 LLVM 4.0.0（包括 DFSan），它的 LLVM Pass 有 820 行 C++ 代码（不包括 DFSan），runtime 有 1950 行 C++ 代码，包含存储污点标签的数据结构以及用于污染输入和跟踪条件语句的 hooks。

Angora 将每个 switch 语句转换为 if 语句序列。Angora 识别 libc 函数，用于在条件语句中出现时比较字符串和数组。例如，Angora将 “strcmp（x，y）”转换为 “x strcmp y”，其中strcmp是Angora理解的特殊比较运算符。

Fuzzer

我们以 4488 行 Rust 代码实现了 Angora，我们使用 fork server 和 CPU 绑定等技术优化了 Angora。