摘要
定向模糊测试着重于通过利用如（部分）bug堆栈追踪、修补程序或危险操作等附加信息，来自动测试代码的特定部分。关键性的应用包括bug复现、补丁测试和静态分析报告验证。尽管定向模糊测试近来受到了广泛关注，但是诸如UAF这类难以检测的漏洞问题仍未得到很好的解决，尤其是在二进制级别。由此，我们提出了“UAFuzz”，这是第一个专用于UAF bugs的（二进制级）定向灰盒模糊测试器（Greybox Fuzzer）。该技术的特点是一个根据UAF的具体情况定制的模糊测试引擎、一个轻量级的代码插装和一个高效的bug分类步骤。对真实案例中的bug复现所进行的实验评估表明了，UAFuzz在故障检测率、检测时间和bug分类等方面显著优于目前最先进的定向模糊测试器。UAFuzz在补丁测试中也被证明是有效的，它在Perl、GPAC和GNU补丁中发现了20个新bugs（包括一个buggy补丁），所有这些bugs都被证实，且其中14个已被修复。最后不能不提的是，我们为社会提供了第一套专门针对UAF的模糊测试基准，而该基准是建立在真实代码和真实bugs基础上的。
1.介绍
背景：大多数程序都含有bugs，而这些bugs又有可能变成漏洞。因此，及早发现bug是漏洞管理过程中的关键所在。最近在学术界和行业内兴起的模糊测试，比如微软的Springfield和谷歌的OSS-FUZZ，显示了模糊测试可以在现实应用程序中发现各种类型bugs的能力。基于覆盖率的Greybox Fuzzing（CGF），比如AFL和LIBFUZZER，充分利用代码覆盖率信息来引导输入生成到被测程序的新部分（PUT），为了触发崩溃而探索尽可能多地程序状态。另一方面，定向Greybox Fuzzing（DGF）旨在对预选的潜在漏洞目标位置进行极限测试，并将应用程序应用于不同的安全上下文：（1）bug复现；（2）补丁测试；（3）静态分析报告验证。根据应用程序的不同，目标位置源自于bug堆栈跟踪、补丁程序或静态分析报告。
我们主要关注bug复现，这是DGF中最常见的实际性应用。包括根据bug报告信息生成已披露的漏洞的概念验证输入（PoC）。由于信息丢失和用户隐私受到侵犯，只有54.9%的错误报告能被复制的时候，bug复现就显得尤为必要了。即使在bug报告中提供了PoC，开发人员仍然需要考虑bug的所有极端案例，以避免回归（循环引用）bug或不完整的修复。在这种情况下，提供更多的bug触发输入对于促进和加速修复过程非常重要。bug堆栈跟踪，在bug触发时函数调用的序列，被广泛用于指导定向模糊测试器。在分析工具（如AddressSanitizer或VALGRIND）下对PoC输入运行代码，将会输出这样的bug堆栈跟踪。
问题：尽管在过去的几年里取得了巨大的进步，但是目前（定向或非定向的）灰盒模糊测试器仍然很难找到复杂的漏洞，如UAF、非干扰的或一些奇怪的bugs，而这些漏洞需要其bug触发路径满足非常特定的属性。比如说，OSS-FUZZ或最近的灰盒模糊测试器s只找到少量UAF。事实上，RODE0DAY作为一个持续性的发掘bugs的竞争，认识到fuzzers在未来应该着眼于覆盖像UAF这类新的bug。比如说，OSS FUZZ或最近的灰盒模糊测试器s只找到少量UAF。事实上，RODE0DAY作为一个持续性的发掘bugs的竞争，认识到fuzzers在未来应该着眼于覆盖像UAF这类新的bug，从而在被广泛使用的只包含缓冲区溢出的LAVA bug语料库中更进一步。我们着重于UAF bugs。它们一般出现在堆元素被释放后使用时。国家漏洞数据库（NVD）中的UAF bugs数量一直有所增加。 与其他类型的bugs相比，UAF bugs由于缺乏缓解技术，它们目前被确定为最关键的可扩展漏洞之一，且可能会造成如数据损坏、信息泄漏和拒绝服务攻击（DoS）等严重后果。
表1：现有灰盒模糊测试技术的概要
| AFL | AFLGO | HAWKEYE | UAFUZZ | |
| 定向模糊测试方法 | ✗ | ✓ | ✓ | ✓ |
| 支持二进制 | ✓ | ✗ | ✗ | ✓ |
| 适用于UAF bug | ✗ | ✗ | ✗ | ✓ |
| 快速插桩 | ✓ | ✗ | ✗ | ✓ |
| UAF bug分类 | ✗ | ✗ | ✗ | ✓ |
目标和挑战：针对UAF，我们集中精力于设计一种高效的定向模糊化处理方法的问题上。由于安全关键程序的源代码并不总是开放可用的，或者可能部分依赖于第三方数据库，因此该技术还必须能够作用于二进制级别（无源代码级插桩）。然而，以检测UAF bugs为目标的fuzzer面临着以下挑战。
C1.复杂性：执行UAF bugs需要在同一个内存位置生成触发3个事件（alloc、free和use）序列的输入，这些事件贯穿PUT的多个函数，其中缓冲区溢出只需要一个单独的界外内存访问。这种时间和空间约束的结合在实践中极难满足；
C2.悄然无声：UAF bugs通常没有例如分段错误这类明显的后果。在这种情况下，fuzzers仅简单地观察计算机瘫痪行为是不会检测到测试案例触发了这样的内存错误。遗憾的是，由于运行成本过高，像ASan或VALGRIND等流行的盈利工具，未能在模糊测试环境下使用。
事实上，目前最先进的定向模糊器，即AFLGO和HAWKEYE，并不能应对这些挑战。首先，它们过于通用化，以致于无法处理UAF的特殊性，例如时序性 — 它们的指导性指标没有考虑到任何顺序性的概念。其次，他们对UAF bugs完全视而不见，却需要将所有生成的种子用于分析工具以支付高昂的额外检查。第三，它们是检测源代码的，因此不适合检测闭源代码可执行文件中的bugs。最后，基于源代码的DGF模糊器在当前的实施中通常会遇到投入成本高昂的插桩步骤，例如，AFLGO花了将近2小时的时间编译和检测cxxfilt（Binutils）。
建议：为了解决上述限制，我们提议UAFuzz，作为第一个专门针对UAF bugs的（二进制级）定向灰盒模糊器。表1给出了UAFuzz与现有灰盒模糊器在UAF方面的快速比较。虽然我们主要遵循定向模糊化的通用方案，但我们也会根据UAF的具体情况仔细地调整它的几个关键组件：
u距离度量偏好较短的引向目标函数的调用链，这样更可能同时包含分配和自由函数，而soa定向模糊器却仅依赖于通用的基于CFG的距离；
u种子选择现在是基于一个序列感知的目标相似性度量，而soa定向模糊器充其量只依赖于目标覆盖率；
u我们的功率计划得益于这些新指标，再加上另一个偏好前缀路径而被称为“切割边缘”的指标更有可能达成整个目标。
最后，bug分类步骤利用了我们以前的度量来预先确定种子是否可能是bug，并抽检出大量疑似bug留给分析工具进行确认（我们实践中用的是VALGRIND）。
贡献：我们的贡献如下：
v我们设计了第一个针对直接处理可执行文件的UAF bug的定向灰盒模糊测试技术（见第4节）。尤其是，我们系统地回顾了定向模糊测试的三个主要因素（选择启发式、功率调度、输入度量），并将它们专门化为UAF。实验证明，这些改进是有益的和互补的；
v我们在最先进的灰盒模糊器AFL和二进制分析平台BINSEC的基础上开发了一个工具链，命名为UAFuzz，实现了上述的基于二进制代码的UAF定向模糊测试方法（见第5章），同时享受了小型插桩和运行时开销等好处；
v我们构建并公开发布了第一个专门用于UAF的模糊测试基准，它包含了12个广泛使用的项目中的14个真正的bugs（包括由定向模糊器发现的少数以前的UAF bugs），希望能促进将来UAF模糊测试评估的发展；
v我们在bug复现设置（见第6节）中评估了我们的技术和工具，证明了UAFuzz是高效的，并且显著优于最先进的竞争对手：触发bugs的平均速度提高了2倍（高达43倍），平均成功运行率提高了34%（高达+300%），分类bugs的平均速度提高了17倍（高达130倍）；
v最后，UAFuzz在补丁测试中也被证明是有效的，它在如Perl、GPAC和GNU补丁等安全关键项中发现了20个以前未知的bugs（包括一个buggy补丁）。所有这些bugs都被证实，且其中14个已被修复。
UAFuzz是第一个专用于检测只有bug堆栈跟踪的UAF漏洞（二进制）的定向灰盒模糊测试器。在这类漏洞方面，UAFuzz的bug复现性能优于现有的（所有）定向模糊器，并且在补丁测试方面也取得了令人鼓舞的成果。我们相信，我们的方法在稍微相关的环境中也可能有用，比如来自静态分析或其他漏洞类的部分bug报告。
2.背景
让我们先澄清一下这篇论文中使用的一些概念。
2.1Use-After-Free
执行：执行是通过程序对输入执行的完整状态序列。执行追踪会在以可见错误结束时崩溃。模糊器的标准目标是找到导致崩溃的输入，因为崩溃是通向可利用漏洞的第一步。
内存安全错误：尤其是指内存安全违规的情况。这可以分成两类。空间安全冲突，比如缓冲区溢出，通常发生在将指针指向到其指定对象的限制范围之外时。目前的模糊器在发现这种错误方面已被证明是非常有效的。而时间安全冲突发生在指针的指向对象不再无效的时候（即指针悬空）。遵守一个好的堆栈规程通常是很容易的，并且足以避免涉及到指针指向堆栈对象的错误。因此，最严重的时间内存冲突包括指向堆上分配的对象的指针。这些被称为释放重引用(UAF)漏洞，其中Double Free（DF）是一种特殊情况。
UAF触发条件：触发UAF错误需要找到一个输入，该输入的执行序列包含3个UAF事件：一个分配（alloc）、一个释放和一个使用（通常是一个解引用），三者都引用同一个内存对象，如清单1所示。
清单1：说明UAF错误的代码片段
1 char * buf = (char *) malloc ( BUF_SIZE );
2 free ( buf ); // pointer buf becomes dangling
3 …
4 strncpy (buf , argv [1] , BUF_SIZE -1) ; // Use-After-Free
此外，这种最后一次使用通常不会使执行立即崩溃，因为内存冲突只有当进程访问进程的地址空间之外的地址时才会使程序崩溃，这在使用悬挂指针时是不可能发生的。因此，UAF漏洞常常被忽视，从而是一个很好的可利用载体。
2.2堆栈跟踪和bug跟踪
通过检查进程的状态，我们可以提取堆栈跟踪，即在该状态下活动的函数调用列表。当进程崩溃时，很容易从该进程中获取堆栈跟踪。由于它们提供了（部分）关于导致崩溃的程序位置序列的信息，因此对于 bug 复现非常有价值。
然而，由于UAF错误导致的崩溃可能在UAF发生很久之后发生，标准的堆栈跟踪通常无助于复现UAF bugs。希望用于动态检测内存损坏的分析工具，如as an或VALGRIND，能够记录所有内存相关事件的堆栈跟踪：当它们检测到某个对象在被释放后被使用时，实际上会报告三个堆栈跟踪（当对象被分配、被释放时和被释放后被使用时）。我们称这种由3个堆栈跟踪组成的序列为（UAF）bug追踪。当我们使用bug追踪作为输入来尝试复现bug时，我们将这样的bug追踪称为目标。
图1:VALGRIND生产的CVE-2018-20623（UAF）的bug追踪
2.3定向灰盒模糊测试
模糊测试是指通过大量的输入生成来强调被测代码以发现bugs。虽然最初的方法完全是黑盒，这或多或少类似于大规模随机测试，但最近基于覆盖率的灰盒模糊器（CGF）依靠轻量级程序分析来引导搜索，这通常是通过基于覆盖率的反馈。简单来说就是，当种子（输入）到达代码中未开发充分的部分时，该种子（输入）被优先（选择），然后对这些被优先（选择）的种子进行变异，以创建新的种子供代码执行。顾名思义，CGF致力于覆盖一个给定的代码，以期发现未知的漏洞。
另一方面，定向灰盒模糊测试（DGF）旨在尽可能频繁和快速地从目标（例如，补丁、静态分析报告）到达预先识别的潜在buggy代码部分。定向模糊器遵循CGF的一般规范和体系结构，但会根据目标调整关键组件，本质上有利于种子“更接近”目标。总体有向模糊器主要建立在三个步骤上：（1）插桩（距离预先计算），（2）模糊测试（包括种子选择、功率调度和种子变异），（3）分类。
在算法中给出了DGF的标准核心算法（我们在UAFuzz中修改的是灰色部分）。给定一个程序P、一组初始种子S0和一个目标T，算法输出一组触发bug的输入S’。模糊队列S用S0（见第1行）中的初始种子初始化。
1.DGF首先执行静态分析（例如，每个基本块的目标距离计算），并插入动态覆盖或距离信息的插桩（见第2行）；
2.模糊器反复地使从模糊测试S队列（见第4行）中选择出来的s输入变异，直到超时为止。如果一个输入是有利的（即被认为是有趣的），或者带有一个小概率α（见第5行），则选择该输入。随后，DGF将能量（也就是要产生的突变体的数量M）分配给所选种子s（见第6行）。然后，模糊器通过在种子s（见第8行）上随机应用一些预定义的变异算子生成M个新输入，并监视它们的执行（见第9行）。如果基因突变型s’使程序崩溃，则将其添加到崩溃输入的集合S’（见第11行）。另外，新产生的突变体被添加到模糊测试队列（见第13行）；
3.最后，DGF作为一组bug触发输入返回S’（分类在标准DGF中不起作用）（见第14行）。
算法1：定向灰盒模糊测试
AFLGO首先提出了一种基于CFG距离的方法以估计种子执行与多个目标之间的接近度，以及基于模拟退火算法的功率调度。HAWKEYE保留了基于CFG的看法，但提高了其准确性，提出了部分基于目标覆盖率（视为一组位置）的种子选择启发式算法，并提出了自适应变异。
篇幅较长，未完待续……..