内容来源于论文：Angora: Efficient Fuzzing by Principled Search
发表在IEEE Symposium on Security and Privacy 2018
第一作者是来自上海科技大学的Peng Chen，第二作者是来自加利福尼亚大学的Hao Chen
文章地址：
https://ieeexplore.ieee.org/abstract/document/8418633
1 背景
模糊测试(又称Fuzzing)是一种用于查找软件错误的流行技术，它的执行过程如下：首先随机生成大量不规则的测试数据，然后自动地将它们输送到目标程序中运行，尝试着引发程序崩溃。模糊测试的特点是方法简单、执行迅速且无需目标程序源码。基于覆盖引导理念的AFL是最先进的模糊测试工具。然而模糊测试随机生成的测试用例质量不高，面临着难以满足复杂约束的困境。一些模糊测试工具使用符号执行来解决路径约束，但会导致路径爆炸。所以，如何去更好地生成输入来触发更多的程序状态是基于覆盖率的模糊测试方法的一个关键挑战。本文提出了对AFL的改进方案，并基于AFL开发了Angora。
2 Angora概述
Angora的主要目标是在不使用符号执行的前提下去解决路径约束来提高代码覆盖率，它主要采用了五种关键技术：
1）上下文敏感的分支计数；
2）可适应的字节级污点跟踪；
3）基于梯度下降搜索的约束求解方法；
4）形状和类型推断；
5）输入长度的智能探索。
Angora对目标程序进行模糊测试主要分为两个阶段：插桩和Fuzzing循环。在Fuzzing循环的每次迭代期间，Angora选择一个未探索过的分支，搜索进入该分支的输入，然后采用上下文敏感的分支计数来记录分支覆盖。Angora对条件语句做一次Fuzzing的步骤如图1所示，用到的关键技术已在图中用红框标识出来。
图1：Angora探索一个条件语句的输入
对于大多数条件语句，其判断仅受输入中的几个字节的影响，因此，Angora会采用字节级污点跟踪技术来确定输入的哪些字节流入相应的判断条件，并仅专注于改变这些字节；确定要改变的字节后，Angora需要决定如何改变它们。使用基于随机或启发式的突变不能有效地找到令人满意的值，所以Angora将分支上的路径约束视为输入上黑盒函数的约束，用梯度下降算法来求解约束；在梯度下降期间，Angora在其参数上评估blackbox函数，其中一些参数由多个字节组成。例如，当输入中的四个连续字节作为整数流一起用于条件语句时，Angora将这四个字节视为函数的单个参数而不是四个独立参数。为了实现这一目标，Angora采用形状和类型推理技术来推断输入中的哪些字节是一同作用于程序中的单个值，以及该值的类型是什么。再者，仅仅改变输入的字节是不够的，有些错误仅当输入的长度超过一个阈值后才会触发，这给输入长度的确定带来了两难的问题：如果输入太短，则可能无法触发某些错误；但如果输入太长，则可能大大降低程序运行速度。Angora用输入长度智能探索技术在程序中做代码插桩，插入的代码能检测输入为多长时将探索的新分支，并确定触发新分支的最小长度。
6 结论
3 关键技术详解
3.1
上下文敏感的分支计数
AFL的分支对上下文不敏感，因此它们无法区分不同上下文中同一分支的执行，图2说明了这个问题。考虑第3行分支的覆盖范围。在第一次运行期间，程序输入“10”。当它在第19行调用f()时，它会进入第3行 if 语句的true分支，走到第4行，这时AFL所记录的分支是(line3, line4)；之后，当它在第21行调用f()时，它进入第3行 if 语句的false分支，走到第10行，记录的分支是(line3, line10)。因此它认为对于第3行的if语句，true和false两个分支都已执行。之后，当程序采用新输入“01”时，AFL认为此输入不会触发新的内部状态，因为第4行和第10行的分支都在上一次运行中执行，但这就无法发现第六行的崩溃错误。
图2：简单代码示例
Angora将上下文合并到分支的定义中。将分支定义为元组 (line_prev, line_cur, context)，line_prev和line_cur分别是条件语句之前和之后的基本块的ID，context是调用上下文。例如，让图3中的程序首先在输入“10”上运行。在它从第19行进入f()之后，它将执行分支(line3, line4, [line19])。然后，在从第21行进入f()之后，它将执行分支 (line3, line10, [line21])。相反，当程序在输入“01”上执行时，它将执行分支 (line3, line10, [line19])，然后执行 (line3, line4, [line21])。通过将调用上下文合并到分支的定义中，Angora可以检测到第二次运行会触发新的内部状态，即当 input[2]=1 时引发第6行崩溃。
向分支添加上下文会增加不同分支的数量，这在发生深度递归时会很明显。Angora通过计算调用堆栈的散列来解决该问题。
3.2
可适应的字节级污点跟踪
下面结合图3所示的简单例子来理解Angora是如何Fuzzing一个条件语句的。
图3：简单例子
Angora在尝试探索第11、12和13行的if语句时，它必须知道输入中的哪些字节偏移影响分支的谓词。显然，第11行是判断输入的长度，12和13行以4字节为单位读取输入到变量 i 和 j。Angora对此输入使用污点跟踪，记录哪些字节偏移流入了哪个条件语句（如图4）。Angora将程序中的每个变量x与污点标签tx相关联，污点标签tx表示输入中可能流入x的字节偏移量。传统的标签用位向量存储，内存开销极大。Angora创作团队提出了一种新的数据结构，它包含两个组件：
二叉树将位向量映射到其标签。每个位向量b由高度为|b|的唯一树节点vb表示，其中|b|是b的长度。vb存储b的标签。要从根到达vb，检查"b0,b1…"序列。如果bi为0，则转到左边的子节点；否则，去右边的子节点。每个节点都包含一个指向其父节点的后向指针。
查找表将标签映射到其位向量。标签是该表的索引，相应的条目指向表示该标签的位向量的树节点。
图4：该输入的第1024到1031字节分别为变量 i 和 j
3.3
基于梯度下降搜索的约束求解方法
字节级污点跟踪发现输入流中的哪些字节偏移成为条件语句。但是如何改变输入以运行未探索的分支语句？AFL采用随机策略，往往效果不佳。Angora将此视为搜索问题，并利用机器学习中的搜索算法。将分支上的路径约束视为黑盒函数f(x)，例如将条件语句中的表达式视为输入x上的函数f(x)，其中x是输入中流入判断的值的向量，函数f(x)捕捉从程序开始到此约束的路径上的所有计算信息。
对f(x)，有f(x) > 0，f(x) <= 0或f(x) == 0三种类型的约束。将条件语句中所有形式的比较转换为上述三种类型的约束，如果条件语句的判断包含逻辑运算符&& 或 ||，则将语句拆分为多个条件语句。例如，将(a && b){s} else {t}拆分为if(a){if(b){s} else {t}} else {t}。用数值近似解决程序中大多数离散的变量。由于程序中大多数变量都是离散的，所以模糊测试中的f(x)是个离散函数。f(x)的梯度是唯一的矢量场，其每个点x处的任意单位矢量v的点积是 f 沿 v 的方向导数, 我们将每个方向导数近似为如下公式：
其中 δ 是一个小的正值, 是第 i 维中的单位向量。为了计算每个方向导数，我们需要两次运行程序，一次使用原始输入 x，一次使用不定输入。用梯度下降搜索针对f(x)的可能解，不需要找到最优解，因为只要搜索到一个可行解，程序就能够进入被该条件约束所保护的代码区域。对于图3所示代码，梯度下降的做法如图5。
图5：梯度下降搜索在例子中的运用
因此从理论上分析得出，基于梯度下降的搜索模型可以迅速解决任何约束，且没有路径爆炸和约束求解带来的时空消耗问题。
3.4
形状和类型推断
Angora必须判断输入中的哪些字节是一同作用于程序中的单个值，比如四个连续字节是一个整型，这就是形状推理。最初输入中的所有字节都是独立的，在污点分析时，指令将输入的字节序列读入变量，然后Angora将字节序列长度与基本类型大小做个匹配，若匹配得上，Angora将这些字节标记为相同的类型。对于类型推断，Angora依赖于对值进行操作的指令的语义。例如，如果指令对有符号整数进行操作，则Angora将相应的操作数推断为有符号整数。当相同的值同时用作有符号和无符号类型时，Angora将其视为无符号类型。对图3的示例，形状和类型推断如图6所示。
图6：形状和类型推断
3.5
输入长度的智能探索
在污点跟踪期间，Angora将类似read的函数调用中的目标内存与输入中的相应字节偏移相关联。它还使用特殊标签标记来自读取调用的返回值。如果在条件语句中使用返回值并且不满足目标约束，则Angora会增加输入长度，以便读取调用可以获取它请求的所有字节。例如，在图3中，如果第12行的条件语句为 false，则Angora会扩展输入长度，以便 fread 可以读取它请求的所有1024个字节。
4 评估
文章将Angora的性能与其他最先进的模糊测试工具进行了比较，并测试了Angora的代码覆盖率及其在现实世界程序中发现未知错误的能力。最后，评估了它的关键新颖特征。
4.1
Angora与其他模糊测试工具进行比较
LAVA-M数据集上对Angora和其他模糊测试工具进行测试，实验结果如表1：
表1：6个模糊测试工具在LAVA-M数据集上的测试结果
Angora表现最佳，在uniq和base64程序上，Angora发现了LAVA-M作者未列出的bug。
4.2
在8个流行的真实开源程序上进行测试
表2是将AFL和Angora对真实程序的Fuzzing结果进行对比。图7和图8是两者运行时行覆盖数和分支覆盖数的对比。
表2：AFL和Angora在真实程序上的比较
图7：行覆盖
图8：分支覆盖
它们表明Angora在任何时候都覆盖了比AFL更多的行和分支。Angora覆盖优越的原因在于它可以探索复杂条件语句的两个分支。
4.3
评估Angora的新颖特征
分别使用上下文敏感的分支计数和上下文不相关的分支计数来运行Angora。图9显示从运行30分钟开始到模糊测试结束，使用上下文敏感分支计数的Angora始终比不用上下文敏感计数和AFL覆盖更多代码行。
图9：上下文敏感分支计数与上下文无关计数的覆盖率比较
然后将梯度下降与另外两种策略进行了比较：随机变异，VUzzer的魔术字节加随机变异。表3显示梯度下降解决了比所有程序中的其他两个策略更多的约束。
表 3：使用三种策略在条件语句中解决约束的百分比
5 结论
Angora是个强大的Fuzzing工具，可以产生高质量的输入，这得益于以下关键技术：上下文敏感的分支计数，可扩展的字节级污点跟踪，基于梯度下降的搜索算法，形状和类型推断和输入长度探索。Angora在很大程度上超越了其他最先进的模糊器。在LAVA-M测试机上，它明显能够比其他模糊测试工具发现更多的错误。在8个成熟的开源程序中，Angora发现175个新错误。Angora将模糊测试的标准提升到了一个新的水平。
改进建议
梯度下降可以解决约束的速度取决于数学函数的性质，如果数学函数是不可导的，则无法使用梯度下降。必要时可以结合其他算法来寻找有效解。比如对于无约束的非线性求解表现较好的粒子群算法。
字节级污点跟踪代价高昂，存储污点标签和其位向量耗费的内存空间大。Angora采用二叉树结构，从根到叶节点的路径来表示位向量，若位向量中间有大量连续的0值，将极大地浪费存储空间。可考虑冗余剪枝或者连续值压缩存储。
关于 天 方 夜 “谈”
天方夜谈原意讲不切实际的东西，而这里想要 “脚踏实地”真正弄懂并感受一篇文章的思想。
方班人有自己的浪漫，
我们探讨知识，谈论理想，
采摘科研的繁星，
脚下是星辰大海。
天：代表我们的理想犹如天空般浩荡
方：代表方班
夜：代表代码人的冷静与静谧
谈：代表方班愿与您，就领域内的经典思想和前沿成果“秉烛夜谈”
