Abstract
不使用符号执行来解决路径约束，从而增加分支覆盖率。为了有效地解决路径约束，我们引入了几个关键技术：可扩展的字节级污点跟踪，上下文敏感的分支计数，基于梯度下降的搜索和输入长度探索。
Design
使用上下文敏感的分支覆盖作为覆盖的度量。每次 fuzzing，Angora 选择一个未探索的分支并搜索探索该分支的输入。
- 对于大多数条件语句，其判断仅受输入中的几个字节的影响，因此改变整个输入将是徒劳的。因此，在探索分支时，Angora会确定哪些输入字节流入相应的判断，并专注于仅改变这些字节
- 确定要改变的输入字节后，将分支上的路径约束视为输入上黑盒函数的约束，并且我们调整梯度下降算法来解决约束
- 在梯度下降期间，我们对黑盒函数的参数进行评估，其中一些参数由多个字节组成
- 仅仅改变输入中的字节是不够的。只有在输入超过阈值后才会触发一些错误，Angora 对程序进行插桩，检测什么时候较长的输入能够探索新分支并且确定所需的最小长度
上下文敏感的分支计数
元组：
除了分支前后基本块的 ID，context 是 ，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
的唯一节点
表示，其中
- 查找表将标签映射到其位向量。标签是该表的索引，相应的条目指向表示该标签的位向量的树节点。
INSERT：
- 删除向量的所有尾随 0
- 跟踪向量中的位，如果为 0，遍历左子树，为 1，遍历右子树，如果不存在，创建新节点
- 将向量标签存储在最后一个节点中
基于梯度下降的搜索算法
字节级污点跟踪发现了输入的哪些字节流入条件语句。但是如何改变输入以运行未探索的分支语句？
将分支的判断看作黑盒函数 的约束，
是输入中流入判断的值的向量，
捕获从程序开始到此判断的路径的计算，
有三种约束：
如果包含逻辑运算 $$ 或者 ||，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。
网友评论