Driller
Driller通过结合fuzzing的速度和符号执行输入生成能力实现功能。
总之，本文做出以下贡献：
- 我们提出了一种新方法，通过利用选择性符号程序来获得更深层的程序代码来提高模糊测试的有效性，同时通过使用模糊测试来缓解路径爆炸，从而提高了模型执行的可扩展性。
- 我们设计并实施了一个工具Driller来演示这种方法。
- 我们通过在同一数据集上识别与Cyber Grand Challenge资格赛的获胜团队相同数量的漏洞来证明Driller的有效性。
3 Overview
2类输入
- General input
- Special input
Driller’s Components
Input test cases.
- Driller不需要输入测试案例，但是这些测试案例可以加速fuzzing的初始化。
Fuzzing
- 启动Driller，首先启动一个fuzzer，探索第一个ACom，到达第一个
complex check，stuck无法继续搜索新的路径。
What is Application Compartment (ACom)？
An ACom of an application is a subset of a ROBAC where only the users, permissions, roles, and organizations applicable to the application are included.
Role and Organization Based Access Control (ROBAC)
Concolic Execution
-
Fuzzer进入
stuck时，Driller启动符号执行部分；符号执行分析应用，根据上一步Fuzzing得到的输入值来限制用户输入，从而避免路径爆炸。 -
根据fuzzer得到的输入，符号执行优化
constraint solver，识别执行未探索过的路径的输入。
Repeat
-
一旦符号执行发现新的输入，立即传递回Fuzzing部分。
-
Fuzzing部分根据这些输入产生变异，模糊执行新的ACom。
-
Driller在Fuzzing和符号执行之间循环执行，直到发现导致Crash的输入。
4 Fuzzing
模糊测试使用大量输入来执行应用程序，通过检查这些输入是否会导致应用程序崩溃。
为了保持执行速度，模糊器是最小的 - 它们对底层应用程序执行最少的检测，并且主要从外部监视它。 近年来，对模糊引擎进行了许多改进。 在本节中，我们将详细介绍与Driller性能相关的改进。
为了实现Driller，我们利用了一种流行的现成模糊器，即American Fuzzy Lop(AFL)。 我们的改进主要涉及将模糊器与Concolic Execution引擎集成。 没有改变AFL的逻辑；AFL依靠插桩来做出有关哪条路径感兴趣的明智决策。 该工具可以在编译时引入，也可以通过修改后的QEMU引入，我们选择了QEMU后端来消除对源代码可用性的依赖。
A. Fuzzer功能
现代模糊器实现了许多功能，可以更好地识别crashing inputs。在本节中，我们将列出并描述最重要的AFL功能，并提及Driller如何使用它们。
Genetic fuzzing AFL通过遗传算法进行输入生成，根据遗传学启发的规则（转录，插入等）改变输入并通过适应度函数对它们进行排序。对于AFL，fitness function基于唯一代码覆盖,即与其他输入触发不同的执行路径。
状态转换跟踪： AFL跟踪它从输入中看到的控制流转换的并集，作为源和目标基本块的元组。基于发现新的控制流转换，输入被优先用于遗传算法中的育种 breeding，这意味着导致应用以不同方式执行的输入在未来输入的生成中获得优先权。
Loop bucketization： 处理循环是模糊引擎和类似执行引擎的复杂问题。为了帮助减小循环的路径空间的大小，执行以下启发式操作。当AFL检测到路径包含循环的迭代时，将触发二次计算以确定该路径是否有资格进行breeding。
- AFL确定执行的循环迭代次数，并将其与导致路径经过同一循环的先前输入进行比较。这些路径都通过其循环迭代计数的对数（即，1,2,4,8等）放入“桶”中。在遗传算法中考虑来自每个桶的一条路径用于育种。这样，对于每个循环，只考虑log(N)路径，而不是N路径的方法。
去随机化： 程序随机化干扰了遗传模糊器对输入的评估 - 在给定的随机种子下产生有趣路径的输入可能不会在另一个下产生。我们将AFL的QEMU后端预先设置为特定的随机种子，以确保一致执行。稍后，当发现崩溃输入时，我们使用我们的concolic execution引擎来恢复任何依赖于泄漏随机性的“质询 - 响应”行为或漏洞。例如，二进制文件中的“质询 - 响应”过程将随机数据回送给用户，并期望相同的数据回显给它。在不删除随机化的情况下，模糊测试组件每次都可能无法通过此检查并探索很少的路径。如果随机性是恒定的，程序每次都接受相同的输入，让模糊器（或者执行组件）自由地找到这一个值，然后进一步探索。发现崩溃后，可以用符号方式对随机性进行建模，如第V-D4节所述，并且可以相应地修补崩溃输入。
这些功能允许AFL快速发现应用程序中的唯一路径，在应用程序的给定隔离区中执行路径发现工作的主要任务。然而，模糊测试的局限性是众所周知的。
B.模糊限制
因为模糊器随机改变输入，而遗传模糊器反过来改变输入，过去通过二进制生成唯一路径，它们能够快速发现处理一般(general)输入的不同路径（即，具有许多输入的输入） 可以触发有意义的程序行为的不同值）。 然而，在应用程序中传递复杂检查的特定specific输入的生成（即，需要具有极少数特定值之一的输入的检查）对于模糊器来说是非常具有挑战性的。
int main(void)
{
int x;
read(0, &x, sizeof(x));
if (x == 0x0123ABCD)
vulnerable();
}
上表中的应用程序从用户读取值并将其与特定值进行比较。 如果提供了正确的值，应用程序将崩溃。 但是，由于模糊测试的性质，模糊器极不可能满足谓词。 对于非插桩的模糊器（即，为输入选择随机值的模糊器），模糊器将发现该错误的可能性是$2^{32}$中的无穷小。对于插桩的模糊器，将导致该二进制文件的控制流布局在一条被发现的道路上。如果没有对新路径进行优先排序的能力（因为没有），一个插桩的模糊器将被简化为在现有路径上应用随机变化，这实质上与非插桩案例相同，具有相同的极小机会成功。
C.Transition to Concolic Execution
Driller旨在通过利用强制执行的优势，补充模糊测试的基本弱点，确定通过复杂检查所需的特定用户输入。当模糊测试分量经历了预定量（与输入长度成比例）的突变而没有识别出新的状态转换时，我们认为它stuck了。然后，Driller检索模糊器在当前隔间中认为有趣的输入，并在它们上调用concolic execution引擎。
如果两个条件之一成立，则模糊器将输入识别为有趣： 1）输入导致应用程序采用的路径是第一个触发某些状态转换的路径。 2）输入导致应用程序采用的路径是第一个放入唯一“循环桶”的路径。
这些条件将传递给concolic execution组件的输入数量保持在一个合理的数量，同时保留很高的传递输入的机会，这些输入可以突变执行以到达应用程序中的下一个隔离区。
5 Concolic Execution
当Driller确定模糊器无法找到其他状态转换时，会调用concolic execution引擎。 Driller使用concolic execution的见解如下：模糊器未能在程序中找到新状态转换的主要原因之一是模糊器无法生成特定输入以满足代码中的复杂检查。 concolic execution引擎用于利用符号求解器来改变现有的输入（这些输入路径可达但不能满足复杂的检查），以得到新输入（路径达到并满足此类检查）。
当Driller调用concolic execution引擎时，它会传递由模糊测试引擎识别的所有“有趣”输入（如第IV-C节中所定义）。 象征性地跟踪每个输入以识别模糊引擎不能满足的状态转换。
当识别出这样的转换时，concolic execution引擎产生输入，该输入将通过该状态转换驱动执行。
在concolic execution引擎完成处理提供的输入之后，其结果被反馈到模糊测试引擎的队列中，并且控制被传递回模糊引擎，以便它可以快速浏览新发现的应用程序的分区。
本节的其余部分将描述Driller实施的concolic execution以及我们为Driller问题域所做的具体调整。
A. Concolic Execution
我们利用angr，一个最近开源的符号执行引擎，用于Driller的concolic execution引擎。该引擎是基于Mayhem和S2E推广和改进的模型。首先，引擎将二进制代码转换为Valgrind的VEX中间表示，该表示被解释为确定程序代码对符号状态的影响。此符号状态使用符号变量来表示可能来自用户的输入或非常量的其他数据，例如来自环境的数据。符号变量是一个变量（例如X），它可以产生许多可能的具体解决方案（例如数字5）。其他值（例如程序中硬编码的常量）被建模为具体值。随着执行的进行，符号约束被添加到这些变量中。约束是对符号值的潜在解决方案的限制性陈述（例如，X <100）。具体的解决方案是满足这些约束的X的任何值。
分析引擎在整个执行过程中跟踪存储器中的所有具体和符号值以及寄存器（上述符号状态）。在引擎到达的程序中的任何点处，可以执行约束解析以确定满足对状态中的所有符号变量的约束的可能输入。当传递给应用程序的正常执行时，这样的输入将驱动应用程序到那一点。有条理执行的优点是它可以探索和查找约束求解器可以满足的任何路径的输入。这使得它可以用于识别复杂比较的解决方案（包括某些散列函数），模糊器不太可能暴力破解。
Driller的符号记忆模型可以存储具体和符号值。它使用基于索引的内存模型，其中读取地址可能是符号，但写入地址始终具体化。这种由Mayhem推广的方法是保持分析可行的一个重要优化：如果读取和写入地址都是符号，则使用相同符号索引重复读取和写入将导致符号约束的二次增加，或者取决于符号执行引擎的实现细节，存储的符号表达式的复杂性。因此，符号写地址始终具体化为单个有效解决方案。在某些条件下，如本领域文献所提出的，符号值被具体化为单一的潜在解决方案。
符号内存优化增加了concolic execution引擎的可伸缩性，但可能导致不完整的状态空间，可能的解决方案更少。 不幸的是，这是必须进行的权衡，以便对现实世界的二进制文件进行分析。
B. Example
concolic execution比模糊测试擅长解决不同的问题。 回想一下下面这个示例，展示了模糊化的缺点。由于传递检查所需的输入的准确性来保护对vulnerable()的调用，因此模糊测试无法在合理的时间范围内探索该段代码。
int main(void)
{
int x;
read(0, &x, sizeof(x));
if (x == 0x0123ABCD)
vulnerable();
}
但是，一个独特的执行引擎将能够轻松地满足此检查并触发易受攻击的功能。 对于这个例子，在这个例子中，concolic execution只需要探索少量路径来找到一个到达bug的路径，但对于更大的二进制文件和真实世界的例子，将会以相同的方式探索太多的路径。
C. Limitations
传统的concolic execution方法包括从程序开始就concolic execution，并使用符号执行引擎探索路径状态，以找到尽可能多的bug。然而，这种方法存在两个主要限制。
首先，concolic execution很慢。这是由于需要解释应用程序代码（与本机执行它相反，如使用模糊器）以及约束求解步骤中涉及的开销。具体而言，后一种操作涉及NP完全问题的解决方案，使得潜在输入的生成（以及确定哪些条件跳转是可行的）是耗时的。
更糟糕的是，符号执行受到状态爆炸问题的困扰。随着符号执行引擎探索程序，路径的数量呈指数级增长，探索超过一小部分路径也很快变得不可行。考虑下表中的示例。在此程序中，当用户输入正好25个B字符时会触发vulnerability()，但这是在符号执行框架中难以表达的条件。当模拟CPU将递归调用降级为check()函数时，该程序的符号执行将导致巨大的状态爆炸。每个执行三元条件比较一个字符与文字B将每个模拟状态分成两个，最终导致$2^{100}$个可能的状态，这是一个不可行的处理量。
int check(char *x, int depth) {
if (depth >= 100) {
return 0;
} else {
int count =(*x == 'B') ? 1 : 0;
count += check(x+1, depth+1);
return count;
}
}
int main(void)
{
int x;
read(0, &x, sizeof(x));
if (check(x, 0) == 25)
vulnerable();
}
另一方面，基于状态转换选择输入的遗传模糊器不会推断程序的整个状态空间，而只会推断由输入触发的状态转换。 也就是说，它将主要关注次数，例如，第5行的检查成功。 也就是说，无论输入中B字符的位置如何，都将根据输入中的数字来判断状态，避免路径爆炸问题。
虽然通过智能状态合并已经在减少这个问题方面取得了进展，但仍然存在一般性问题。
D. Driller的执行
在大多数情况下，模糊测试可以单独充分探索大部分路径，只需通过随机位翻转和其他变异策略找到它们。通过利用本机执行，它可以在大多数可以随机触发路径的情况下胜过符号执行。因此，大部分工作都从concolic execution引擎转移到模糊器，这将快速找到许多路径，让常规引擎能够解决更难的约束。
当模糊测试无法发现输入产生新执行路径时，将调用concolic execution引擎。它跟踪模糊测试发现的路径，识别分散到新程序组件中的输入，并执行有限的符号探索。另外，当模糊测试组件发现崩溃输入时，该concolic execution引擎“重新随机化”它以恢复依赖于随机性和其他环境因素的崩溃输入的部分。
1）预约束跟踪：Driller使用concolic execution来跟踪来自模糊器的有趣路径并生成新输入。这种方法有效性的一个关键因素是它允许Driller避免在符号探索中固有的路径爆炸，因为只分析了代表应用程序处理该输入的路径。
当跟踪从模糊器传递到符号执行时，目标是发现模糊测试之前未找到的新过渡。 Driller的concolic execution引擎跟踪输入，遵循模糊器采用的相同路径。当Driller发生条件控制流转移时，它会检查反转该条件是否会导致发现新的状态转换。如果愿意，Driller会生成一个示例输入，通过新的状态转换而不是原始控制流来驱动执行。
通过这样做，Driller的concolic execution引擎将模糊引擎引导到应用程序的新隔间。生成输入后，Driller继续跟踪匹配路径以查找其他新状态转换。
2）输入预约束：Driller使用预约束来确保concolic execution引擎的结果与本机执行中的结果相同，同时保持发现新状态转换的能力。在预约束执行中，输入的每个字节被约束以匹配由模糊器输出的每个实际字节，例如/dev/stdin[0]=='A'。当发现新的可能的基本块转换时，简单地移除预约束，允许Driller求解将偏离到该状态转换的输入。预约束是必要的，以在符号执行引擎中生成相同的跟踪，并使有限的范围探索可行。
int check(char *x, int depth) {
if (depth >= 100) {
return 0;
} else {
int count =(*x == 'B') ? 1 : 0;
count += check(x+1, depth+1);
return count;
}
}
int main(void)
{
char x[100];
int magic;
read(0, x, 100);
read(0, &magic, 4);
if (check(x, 0) == 25)
if (magic == 0x42d614f8)
vulnerable();
}
为了演示输入预约束如何在Driller中工作，我们使用上表中的示例，它类似于V-C中的示例，另外为了达到vulnerable()，我们必须在第18行提供幻数（0x42d614f8）。在对输入进行模糊测试之后，Driller最终意识到它没有发现任何新的状态转换，因为单独的模糊器无法猜出正确的值。
当调用concolic execution来跟踪输入时，Driller首先约束符号输入中的所有字节以匹配跟踪输入的字节。由于程序是象征性执行的，每个分支只有一种可能性，因此只遵循一条路径。这可以防止第V-C节中描述的路径爆炸。然而，当执行到达第18行时，Driller认识到在模糊测试期间从未进行过替换状态转换。然后，Driller删除在执行开始时添加的预约束，不包括通过跟踪输入以符号方式执行程序而放置的谓词。字符数组x中的字节部分受路径约束，而magic的值受等式检查if(magic == 0x42d614f8)约束。因此，concolic execution引擎创建一个包含25个B实例和magic = 0x42d614f8的输入。这通过了第18行的检查并达到了vulnerable()。
3）有限的符号探索：为了减少昂贵的符号引擎调用的数量，我们还引入了一个符号探索存根，以发现在新发现的状态转换后直接存在的更多状态转换。这个符号探索存根探索状态转换的周围区域，直到资源管理器遍历了可配置数量的基本块。一旦发现了这个数量的块，Driller就会为浏览器发现的所有路径提供输入。我们认为这样做可以防止模糊器在提供Driller生成的输入后快速“卡住”。在许多情况下，Driller生成一个新输入，只能通过多部分复杂检查中途，并且必须立即回溯以允许模糊器更深入地进入二进制文件。符号探索存根是一个小优化，它允许Driller在请求之前找到进一步的状态转换，而不必回溯其步骤。
4）重新随机化：在程序运行期间引入的随机值可以破坏模糊测试，如前所述。下表显示了一个小程序，challenge反映用户随机输入。这使得模糊不稳定，因为在不监视程序输出的情况下我们永远无法知道challenge的具体值。
int main(void) {
int challenge;
int response;
challenge = random();
write(1, &challenge, sizeof(challenge));
read(0, &response, sizeof(response));
if (challenge == response)
abort();
}
一旦发现漏洞，我们使用符号执行来跟踪崩溃的输入并恢复需要满足目标二进制文件提出的动态检查的输入字节（例如上表中的challenge-response）。 通过在崩溃时检查符号状态并找到应用程序输出和崩溃输入之间的关系，Driller可以确定应用程序的challenge-response协议。 在这个例子中，我们可以看到由read调用引入的符号字节被约束为等于write写出的字节。 确定这些关系后，我们可以生成一个漏洞规范，用于处理在真实环境中发生的随机性。
Conclusion
在本文中，我们介绍了Driller，这是一个结合了动态模糊和符号执行的最佳工具，可以有效地发现隐藏在二进制文件中的bug。 我们介绍了二进制文件的概念，它在很大程度上将功能和代码分开。 在Driller中，模糊测试可以快速而便宜地查看隔间，有效地探索循环和简单检查，但通常无法在隔间之间进行过渡。 在考虑循环和内部检查时，选择性的符号执行会进入状态爆炸，但在查找二进制文件的分区之间的路径时非常有效。 通过将这两种技术相结合，每个技术都失败，Driller能够在二进制文件中探索更大的功能空间。