Igor: Crash Deduplication Through Root-Cause Clustering

修建不必要的跟踪元素，通过CFG来解决堆栈哈希的缺点，来实现崩溃分组。
测试用例减少（最小化和简化测试用例）和崩溃分组（确定两个输入是否触发相同或不同的错误）
https://github.com/HexHive/Igor

摘要

模糊测试已成为最有效的 bug 查找技术。模糊测试器的输出是一组概念验证（PoC）测试用例，用于所有观察到的“唯一”崩溃。开发人员需要花费大量精力来分析每个崩溃的测试用例。这个主要是手动过程导致报告的崩溃数量超过了错误修复的数量。自动崩溃重复数据删除技术主要依赖于覆盖率配置文件和堆栈哈希，应该可以缓解这些压力。但是，这些技术都会夸大实际的 bug 计数，并错误地混淆不相关的 bug。这会阻碍而不是帮助开发人员，并需要更准确的技术。

模糊测试的高度随机性意味着 PoC 通常会执行许多与崩溃的根本原因正交的程序行为。程序行为的这种多样性表现为崩溃的多样性，从而导致错误计数膨胀和混淆。基于这一见解，我们开发了 Igor，这是一种自动化的双阶段崩溃重复数据删除技术。通过最小化每个 PoC 的执行跟踪，我们获得了修剪后的测试用例，这些测试用例执行触发错误所需的关键行为。然后，我们根据最小化执行跟踪的控制流图，使用与集群崩溃的图表相似性比较，每个集群映射回一个唯一的根本原因。

我们根据 254,000 个 PoC 产生的 39 个错误（分布在 10 个程序中）对 Igor 进行了评估。我们的结果表明，Igor 准确地将这些崩溃分为 48 个唯一可识别的集群，而其他最先进的方法产生的错误计数至少大一个数量级。

引言

软件测试研究的主要重点是查找错误。从物理层 [14， 59， 61， 77] 到应用层 [5， 15， 51， 62， 71， 83] 的整个开发堆栈中，最大限度地发现错误是一个关键主题。“我们总是有能力修复 Bug”的假设推动了 Bug 查找技术的驱动力，这些技术可以在短时间内产生大量崩溃，其中最突出的是模糊测试。软件行业的大玩家也推动了这一运动，为其庞大的用户群提供开放访问的报告平台 [4， 29， 56] 和漏洞赏金。由于几乎没有动力对崩溃进行分类，用户和软件测试人员经常提交原始结果/崩溃转储，让软件维护人员承担提炼崩溃和修复错误的重量。随着报告的崩溃数量增加，将更多时间花在崩溃分类和修剪重复报告上，从而使维护人员用于修复错误和提高软件质量的时间减少。大型模糊测试场（例如 ClusterFuzz [30]、OSS-Fuzz [68]）（全天候运行并自动提交崩溃报告）加剧了这个问题。例如，截至 2021 年 4 月下旬，有 979 个未解决的 Linux 内核错误，最早的一次是在 2017 年 11 月提交的（基于 syzbot 统计数据 [31]）。

这个问题的解决方案包括协作式的，维护者依靠社区在他们的报告中提供可操作的分析，到系统性的，在大型故障转储中使用启发式方法来过滤掉冗余和重复项 [1， 19， 21， 41， 80]。这些启发式方法通常依赖于动态程序行为来识别根本原因并回答“给定崩溃的测试用例，最有可能导致崩溃的原因是什么”的问题。例如，Aurora [7] 提出了一种基于 delta 调试 [85] 的根本原因识别方法：错误和良性的测试用例都被执行，并且程序行为的分离标志着错误。相比之下，崩溃分桶（参见分组）将重点从查明崩溃的原因转移到根据崩溃的根本原因对崩溃进行分组。崩溃分桶回答了“给定许多崩溃测试用例，哪些崩溃会触发相同的错误”的问题。崩溃分桶技术在实践中被广泛使用 [43]，并依赖于崩溃站点、覆盖率配置文件或堆栈哈希来集群崩溃。

崩溃站点。所有 bug 都会在特定的程序位置崩溃。这些崩溃站点（例如，崩溃时存储在指令指针中的地址）用作粗粒度错误标识符。不幸的是，崩溃站点不精确，并导致错误分类（例如，对于释放后使用的错误，对象可能会被任意重用，从而触发广泛的“唯一”崩溃）。崩溃网站低估和高估了 bug 数量，因此在实践中没有使用。

将执行新的控制流边或省略公共边的崩溃视为“唯一”。边缘覆盖的精细特性使其对控制流中的微小变化敏感，并导致崩溃计数膨胀;对 Bug 的路径进行轻微修改会导致新的崩溃。覆盖率概况高估了 2-3 个数量级的 bug 数量 [33， 43]。

堆栈哈希。堆栈哈希为崩溃提供功能敏感的标签，通常由模糊测试程序（例如 honggfuzz [71]）和模糊测试农场（例如 ClusterFuzz [30]）使用。堆栈哈希会累积（堆栈上的最后 N 个）函数调用（在堆栈上），以此找到崩溃站点，并对这些跟踪进行哈希处理以形成唯一的错误标识符。与覆盖率分析相比，堆栈哈希更加粗粒度，并且导致更少的崩溃存储桶。然而，堆栈哈希很容易出现错误分类，无论是过度近似还是低估计 bug 的数量（前者是由于到崩溃站点的路径不同 [7， 22]，而后者是由于 bug 共享相同的调用序列）。堆栈哈希值高估了 1-2 个数量级的 bug 数量 [43]。

不准确的崩溃分组技术（如前面描述的技术）浪费了开发人员宝贵的时间。特别是，错误标识符（例如，覆盖率配置文件、堆栈哈希）容易受到程序行为波动的影响。覆盖率引导的模糊测试程序（通常旨在最大限度地提高代码覆盖率）放大了这种波动，产生了许多崩溃的测试用例，这些测试用例会执行与根本原因无关的“嘈杂”代码。这种干扰阻碍了基于控制流的重复数据删除技术，增加了错误计数。此外，准确的 bug 分类依赖于识别 bug 的特征触发因素。如果（a）执行跟踪中缺少触发器（例如，如果跟踪太粗粒度），和/或（b）执行跟踪包含无关元素（例如，如果跟踪太精细），则很难在部分执行跟踪中识别此触发器。这需要一种新的碰撞分组方法;它能够消除执行跟踪中的干扰，以准确对路径进行分组，并保留关键的控制流信息，以准确隔离不同的根本原因。

虽然覆盖率最大化策略非常适合通过模糊测试来查找错误，但我们建议对应的策略 - 覆盖率最小化模糊 - 是最小化执行跟踪和实现有效崩溃分组的关键。我们通过修剪不必要的执行跟踪元素（即 noise）来提高崩溃标签的精度，从而实现更简洁的重复数据删除。我们还通过使用控制流图（CFG）来解决堆栈哈希（以函数调用粒度运行）的缺点，以获得崩溃执行跟踪的更完整视图。使用 CFG 可以保留关键的控制流信息，并允许对冗余（已执行的）代码进行主动修剪，从而实现更准确的崩溃分组。

我们提出了 Igor1，这是一种双阶段崩溃重复数据删除技术，它利用覆盖率减少模糊测试和 CFG 相似性指标来通过关键行为来评估集群崩溃。通过简化每个崩溃的执行跟踪，我们获得了执行触发 bug 所需的最小化行为的测试用例。然后，我们对所有最小化执行跟踪的 CFG 执行图形相似性比较，以将它们分组到紧密打包的集群中，每个集群都映射回唯一的根本原因。

我们回答以下研究问题：

什么是理想的碰撞分组，为什么在实践中无法实现？
密集执行跟踪对崩溃计数膨胀的影响有多大，稀疏性能否提高精度？
什么指标最适合捕获和隔离根本原因？

贡献：

一个覆盖率减少模糊测试器，它在收集的边缘覆盖率上应用最小化适应度函数以缩小测试用例;
一种新的崩溃分组指标，基于使用 Weisfeiler-Lehman Subtree Kernel 算法的控制流图相似性 [45];
用于评估崩溃分组技术的 ground-truth 基准，其中包含来自 14 个真实程序的 52 个 CVE2 和 254000 个崩溃测试用例（生成超过 58.7 个 CPU 年的模糊测试）。利用这些程序的源代码和这些错误的补丁，我们开发了分析工具，并使用真实值手动标记这些测试用例（大约需要 30 个人日）。此基准测试使我们能够测试 Igor 的准确性。

为了帮助开发人员（以便他们能够快速准确地发现崩溃的根本原因）和研究人员（以便他们能够重现和扩展我们的结果），我们在 https://github.com/HexHive/Igor 上提供了 Igor 原型和基准测试。

背景和直觉

崩溃分桶对测试用例进行分组，以隔离崩溃的根本原因。准确的崩溃分桶需要：

将具有相同根本原因的崩溃归为一组（最大限度地减少 I 类错误）;
为具有不同根本原因的崩溃创建新组（最大限度地减少 II 类错误）;
捕获准确的 bug 上下文。捕获准确的 bug 上下文需要对程序行为进行完整的建模和分析。然而，现有的建模/分析技术（例如，符号执行）无法扩展 [6]。相反，实际的崩溃分桶依赖于容易出错的启发式方法。减少这些错误需要
1. 与 bug 上下文相关的行为指标，
2. 执行跟踪修剪以最大限度地减少干扰。

行为指标

由相同 bug 或不同 bug 生成的错误可能会显示相同的覆盖率，从而降低类型 I 的错误率，但会提高类型 II 的错误率。尽管如此，布尔函数覆盖率需要最少的资源来测量和收集，从而提高了可扩展性。

研究背景

根据 Dhaliwal 等人 [23] 的说法，80% 的 bug 根本原因位于崩溃时的调用堆栈上。几个研究项目采用了这个概念并探索了不同的堆栈哈希技术 [11， 13， 21， 42， 46， 64， 66]。堆栈哈希快速且易于部署，适用于批量处理大量测试用例的大规模活动，但容易出现 I 类和 II 类错误，并且缺乏高质量的分类。

执行跟踪还可用于对测试用例进行分类。这种方法通常使用二进制翻译 [52] 或插入 [57]。一些基于污点的方法也研究了将测试用例分类为崩溃分析的一种形式。例如，CrashFilter [39] 根据静态污点分析自动对失败的测试用例进行分类。RETracer[20] 基于反向污点分析从内存转储中恢复早期程序状态，之后分析师手动对测试用例进行分组。REPT [19] 扩展了 RETracer，并通过重构数据流来获得更准确的分类结果。最后，POMP [80] 从数据流对程序崩溃的不同贡献的角度对崩溃进行分类。

这些基于污点的方法从数据流的角度对崩溃进行分组。它们比堆栈哈希更精确。然而，基于污点的方法通常无法扩展到复杂的程序，因为它们需要记录详细的程序跟踪，即使是简单的程序，也会很快超过几百吉B ，并且需要对使用污点输入数据的路径进行复杂的符号推理来做出控制流决策。如果错误仅依赖于数据流，而不依赖于基于受污染输入数据的控制流决策，那么基于污点的方法可能是有效的 [15， 62， 76]。

在不同的功能（get16u 或 get32u）中。相比之下，清单 2 显示了不同的漏洞如何在同一位置崩溃。程序中有一个 if-else 结构，其中包含每个分支上的唯一堆栈溢出漏洞。触发漏洞后，程序最终在调用 memcpy 时崩溃。虽然崩溃位置相同，但崩溃是由不同的漏洞引起的。由于程序中控制流路径的复杂性，基于调用栈或崩溃站点的方法无法区分不同和相似的 bug，导致误识别率高 [43]。

在实践中，找到灵敏度、准确性和可扩展性之间的平衡需要确定哪个行为指标与根本原因最密切相关。我们从结果中得出结论，最小化执行跟踪可以最好地了解错误触发器，使其适合进行相似性匹配。

测试用例减少

行为指标中的缺陷可能会因记录的执行跟踪中的无关数据点而被放大。虽然降低指标的灵敏度可以提高其对噪声测量的弹性，但这只能解决噪声的一个症状，而不能解决其来源：熵。在他们对故障定位的研究中，Christi 等人 [17] 表明，减少测试用例对定位的准确性有很大好处。测试用例减少是指在始终触发相同的 crash 的前提下，不断减小 crashing input 的大小。在实践中，简化的测试用例改进了软件开发过程;例如，在漏洞挖掘中，最小化的测试用例可以提高突变效率并引导过程产生有趣的行为;在 crash analysis 中，它消除了多余的字节，以简化导致 crash 的控制流。

研究背景

测试用例减少中使用的两种主要方法是增量调试 [85] 和污点分析 [50]。

增量调试是一种流行的方法，它使用两种算法自动最小化测试用例：简化和隔离 [54]。前者不断缩小原始输入文件的大小，直到找不到导致程序崩溃的较小文件，而后者则搜索可以通过的输入，在满足其他约束后，该输入将再次成为失败的输入。最流行的用于模糊测试活动的测试用例简化工具 afl-tmin [83] 就是基于这一原则。

污点分析是一种在程序崩溃时将访问的 registers 和 memory 标记为 taunted 的方法，然后跟踪污点的来源以标记 input 中所有与崩溃相关的组件，从而将崩溃的测试用例减少到相关的字节。通常，可以使用任何前向或后向污点分析 [18]，但在实践中，输入或跟踪的长度通常令人望而却步。长走线和复杂的输入会导致过度污染或污染不足，并且难以在给定合成输入的情况下保持对控制流依赖关系的控制。在实践中，污点分析在碰撞分组中的应用是有限的。

挑战

Aurora [7] 是一种根本原因识别方法，它利用增量调试来区分崩溃导致的关键执行跟踪和良性执行跟踪。该过程从崩溃多样化阶段开始，在该阶段，错误的输入被改变以生成崩溃和非崩溃测试用例。然而，多样化存在引入与所研究的根本原因无关的新错误的风险。这是因为 Aurora 遵循探索性模糊测试过程（即增加覆盖率）来生成新的输入。

测试用例最小化还可能引入与原始 bug 无关的新 bug。这可以通过更严格的适应度函数来解决：只需执行原始跟踪的子集，这严重限制了探索。虽然这并不能保证不会引入新的错误，但我们的评估表明，错误率在实践中可以忽略不计。与 AFL 的崩溃模式 [83] 相比，它与 fuzzer 的适应度相同，Igor 引入了 90%更少的误报。

最小化崩溃的问题也是非凸的。通常，测试用例缩减的适应度函数是输入的大小（以字节为单位）。相反，我们建议最小化程序执行跟踪的大小，从而降低执行复杂性，而不是输入的大小。修剪崩溃测试用例的执行跟踪可以生成更简洁的输入，这些输入执行相同的所需程序行为。错误由所有可能的执行跟踪的子集触发，通过对输入空间的最小化功能，可以找到根本原因的关键路径并用于对崩溃进行分类。但是，程序行为很复杂，爬山最小化过程可能会收敛到局部最小值。直观地说，收敛到不同局部最小值的轨迹可能表明不同的根本原因，从而使分析进一步复杂化。但是，我们发现，将此过程与聚类过程相结合会导致跟踪的微小变化被忽略，而有利于全局跟踪重叠。

我们的方案

虽然现有方法为减少需要分类的大量崩溃测试用例提供了初始步骤，但这些方法引入的 I 类和 II 类错误会导致不确定性，甚至可能增加开发人员的工作量和/或导致遗漏错误。我们通过引入双相碰撞分析方法来解决这种不精确性。这种方法建立在一个关键观察的基础上：每个 bug 都有一个核心行为，必须执行该行为才能触发 bug。提取和匹配此行为的技术可以将大量崩溃提炼成一组精确的唯一错误。在分析大量崩溃的测试用例（及其基本事实）时，我们观察到同一错误的测试用例在其执行跟踪的基本阶段部分重叠;bug 触发器。我们的技术 Igor 提取了 bug 触发器的近似值，然后利用拓扑图匹配将相似的测试用例分组到 bug 类别中。因此，这种通过根本原因分析实现高效和有效的崩溃分组的双阶段方法结合并扩展了两个重要的研究领域：测试用例减少（最小化和简化测试用例）和崩溃分组（确定两个输入是否触发相同或不同的错误）。从广义上讲，Igor 利用测试用例缩减来简化测试用例观察到的执行跟踪，以便我们可以根据崩溃覆盖率的相似性对崩溃进行分组（即，我们利用前者来改进后者）。

IGOR 设计

图 1 描述了 Igor 的主要组件和工作流程。从一组崩溃的测试用例开始，预处理阶段通过利用采样和 afl-tmin 来减少不必要的分析成本。在此之后，跟踪生成器（IgorFuzz）记录并最小化每个预处理测试用例的执行跟踪。然后，图形分析器从最小化的跟踪中构建控制流图，并提取描述每个测试用例的图形相似性指标。最后，集群构建器将测试用例分类为单独的组，每个组确定一个独特的根本原因，并利用验证循环来查找最佳集群配置。

采样。尽管堆栈哈希通常不精确，但在整个调用堆栈中，两个不同的根本原因重叠的情况很少见。换句话说，一个 bug 可能会导致许多不同的堆栈哈希值，但一个堆栈哈希值通常只映射到一个 bug。在我们的数据集中，三个程序中只有 6 个（共 71 个）错误对包含共享堆栈哈希。我们利用这一观察结果，通过根据 PoC 的完整调用堆栈哈希对 PoC 进行分组来减少 PoC 语料库。如果有许多 PoC 映射到同一个唯一堆栈哈希，我们只处理 50 个最多样化的 PoC。这使我们能够删除映射到相同错误的高度相似的 PoC，从而在不影响精度的情况下降低处理成本。

因此，可以通过预处理测试用例来删除无关的字节来改进。我们借助 afl-tmin [83] 实现了这一点，afl-tmin [83] 是 AFL 附带的一个轻量级测试用例缩减工具。尽管 afl-tmin 只专注于减少输入的长度（即，这是它优化的唯一指标），但它间接缩短了执行跟踪的长度，进一步帮助 IgorFuzz 找到最小的 PoC。Afl-tmin 还允许我们合并减少到相同字节序列的 PoC。在第二个预处理阶段使用 afl-tmin 可以提高 IgorFuzz 在探索较短执行跟踪方面的效率。正如 2.2 节中所讨论的，afl-tmin 可能会引入新的错误。然而，在使用 afl-tmin 最小化过程中发现新错误的情况很少见：在我们的评估中，5,531 个 PoC 中只有一个在通过 afl-tmin 最小化后触发了不同的错误。我们的评估表明，其他 9 个 PoC（针对同一错误）仍然正确，使 Igor 能够正确地将 9 个 PoC 聚集到该根本原因。虽然我们在最小化过程中丢失了 1 个 PoC（共 5,531 个），但仍然有足够的 PoC 来正确识别所有唯一错误。这实际上意味着我们没有通过 afl-tmin 在评估中引入任何假阴性。

最小化。最小化的测试用例在两个方面有利于模糊测试：（i）输入大小的减小导致目标更快地解析和处理，从而产生更高的模糊测试吞吐量;（ii）通过从输入中删除无关的字节，模糊测试程序的更改更有可能修改对程序行为至关重要的字节。最小覆盖率模糊测试的情况也不例外，并且可以通过预处理测试用例来删除无关的字节来改进。我们借助 afl-tmin [83] 实现了这一点，afl-tmin [83] 是 AFL 附带的一个轻量级测试用例缩减工具。尽管 afl-tmin 只专注于减少输入的长度（即，这是它优化的唯一指标），但它间接缩短了执行跟踪的长度，进一步帮助 IgorFuzz 找到最小的 PoC。Afl-tmin 还允许我们合并减少到相同字节序列的 PoC。在第二个预处理阶段使用 afl-tmin 可以提高 IgorFuzz 在探索较短执行跟踪方面的效率。正如 2.2 节中所讨论的，afl-tmin 可能会引入新的错误。然而，在使用 afl-tmin 最小化过程中发现新错误的情况很少见：在我们的评估中，5,531 个 PoC 中只有一个在通过 afl-tmin 最小化后触发了不同的错误。我们的评估表明，其他 9 个 PoC（针对同一错误）仍然正确，使 Igor 能够正确地将 9 个 PoC 聚集到该根本原因。虽然我们在最小化过程中丢失了 1 个 PoC（共 5,531 个），但仍然有足够的 PoC 来正确识别所有唯一错误。这实际上意味着我们没有通过 afl-tmin 在评估中引入任何假阴性。

IgorFuzz：最小覆盖率模糊测试

覆盖率引导的模糊测试通常会合并反馈，以最大限度地提高代码覆盖率并触发崩溃。模糊测试程序的高度随机性意味着它们经常会发现许多触发相同 bug 的不同测试用例。这会导致无关的执行跟踪，从而放大底层指标的不精确性并阻碍集群。

最小覆盖率模糊测试背后的直觉是，只有在执行错误代码时才会出现错误。最大限度地减少在到达错误代码之前执行的代码可以减少开发人员在调试期间必须分析的状态量。给定一种机制来测量触发 bug 时执行了哪些代码，以及一种对不同样本的测量结果进行排序的机制，就可以找到触发 bug 所需的最小代码跟踪，我们将其确定为最短的 bug 触发路径（绝对最小代码跟踪是空集）。此观察结果说明了通过不同路径触发 bug 的可能性。通过模糊测试，我们对不同 bug 路径附近的状态空间执行搜索，目的是找到最短（最简单）的执行跟踪。由于模糊测试是一种动态技术，因此不可避免地会发现多个次优解;但是，我们的评估表明，不同的解决方案显示的特征非常相似，可以归类为相同的根本原因。

理想情况下，通往 bug 的最短路径是其最佳标识符。确定最短路径的 oracle 将解决崩溃分组问题，因为同一 bug 的所有 PoC 都将减少到相同的路径。将任意 PoC 减少到最小路径具有挑战性，因为它需要确定仍然满足所有 bug 上下文约束的最短路径。在实践中，这会导致较长的执行跟踪，超出了当今求解器的能力。例如，我们评估中的最短路径包含超过 91,000 个基本块（在 LibPNG 中），而最短执行跟踪包含多达 22,563,000 个基本块（在 Poppler 中）。

现有的测试用例缩减技术使用支持较小 input size 的目标函数。这是错误报告指南的产物，通常需要一个最低限度的工作示例作为 PoC。但是，减小 input 大小并不总是意味着降低跟踪复杂性。为了突出这种影响，我们使用 5 个目标和 10 个 bug 对 afl-tmin 进行了一项研究。虽然测试用例的大小通常会减小，但这并不一定保证执行跟踪的长度会减少。例如，afl-tmin 将 OpenSSL 的 x509 输入大小减少了 41.10%，而只修剪了 4.83% 的 CFG 边缘。此外，尽管 afl-tmin 将 pdfimages 的输入大小减少了 82.45%（平均），但 15.18% 的测试用例在通过 afl-tmin 减少后执行了更多的边缘。这表明较小的输入大小并不能保证更简单的执行跟踪。有关我们的完整结果，请参见表 6 和附录 C。

与漏洞挖掘类似，模糊测试为高效且可扩展的流程提供了机会，该流程可以找到执行类似行为的更简单的输入。为了降低执行跟踪的复杂性，我们提出了一种新型的模糊测试器，其目标与现有的模糊测试器略有不同。模糊测试程序 IgorFuzz 中的适应度函数支持更简单的执行跟踪，通过练习更少的边缘，同时仍然在同一位置使目标崩溃。

减少的目标是找到触发相同 bug 的更简单的测试用例。多个 bug 可以共享同一个崩溃站点，并且最小化的测试用例存在在同一位置触发不同 bug 的风险。然而，在实践中，简化的测试用例触发不同 bug 的概率是微不足道的。区分崩溃站点的使用与分组和简化崩溃之间非常重要。当基于崩溃站点进行分组时，输入是多种多样的，并且可能会执行不同的程序行为。由于这种干扰，错误分类的 bug 将很常见。但是，当基于崩溃站点简化测试用例时，我们会在执行类似的程序行为时降低执行跟踪的复杂性。这样可以最大限度地降低新派生的测试用例触发不同 bug 的可能性。

最先进的模糊测试程序旨在实现最大覆盖范围，以帮助发现错误。最大化覆盖率的现有工作可以分为三个领域：种子保留策略 [28， 62， 75， 78]、种子选择策略 [9， 15， 24] 和种子调度策略 [8， 9， 81]。我们根据这三个领域的见解指导 IgorFuzz 的设计，并修改了一个通用的反馈导向的灰盒模糊测试器，例如 Böhme 等人 [9] 提出的那个。算法 1 概述了我们的覆盖率最小化算法，图 2 给出了 IgorFuzz 有效性的示例。

种子选择原则

为了在探索目标的覆盖空间时实现更高的效率，AFL [83] 将练习分离的边集的种子标记为收藏夹。通过在每个种子执行的边集上找到一个最小集合（例如，由 Karp [40] 执行），AFL 确定了更有可能增加代码不同方向覆盖率的种子，并更有利地改变这些种子。先前关于种子选择的研究[35]也验证了这一策略：种子越少越明显，模糊器就越能最大限度地覆盖。

与 AFL 的方法相反，IgorFuzz 试图通过偏爱修剪分离边缘集的种子来最大限度地减少覆盖率。修剪 Edge 组的新种子更有可能在进一步更改时从执行跟踪中删除这些 Edge。出于这个原因，我们将此类种子标记为最爱，并为它们分配更高的能量。

种子能源调度

Seed Energy （种子能量）确定种子在被选中后将被模糊化的次数。更高的种子能量会导致更多的突变和处决。通过改变具有较少记录边数的种子，IgorFuzz 可以更快地处理输入，并且更有可能发现更简单的 PoC。我们使用贪婪启发式方法将更多能量分配给执行时间较短的种子。

我们还根据 Seed 的覆盖率情况将能量动态分配给不同的 seed。我们将更多的能量分配给执行路径较短的种子。我们不仅将更多的能量分配给更简单的种子，而且还确保分配的能量偏向于更大程度的覆盖率减少。

模糊测试输出选择标准

为了探索不同的代码区域，模糊测试通常对目标的覆盖空间采用元启发式优化。在搜索过程中，模糊测试自然会遇到与原始目标不同的解决方案。在 IgorFuzz 的上下文中，该目标是找到触发相同初始错误的最简单的 PoC。在 BitmapSize（AFL++ [27] 用于显示激活了多少个唯一边缘）的帮助下，我们通过查找位图大小最小的 PoC 来选择最简单的 PoC。尽管将搜索限制在原始执行跟踪附近，但不可避免地会触发其他 bug。为了过滤掉那些错误的解决方案，我们依靠崩溃站点作为倒数第二个选择标准，在剩余的种子中，我们选择位图大小最小的 PoC。根据我们的评估，IgorFuzz 发现由其他错误引起的崩溃的可能性很低（第 5.5 节）

测试用例相似度测量

用于测量测试用例相似性的现有方法利用了崩溃站点上可用的信息（例如，调用堆栈、指令指针、寄存器内容）。这些方法的一个基本限制是，一个 bug 可能会导致程序在许多不同的位置崩溃，从而导致唯一 bug 计数的过度近似。向后切片可以通过跟踪崩溃条件的流程到其来源来缓解这个问题。遗憾的是，向后切片并不适用于所有类型的漏洞（例如，在释放后使用漏洞中，数据被重用的位置可以独立于数据的释放位置）。此外，跨 100,000 个基本块向后扩展到大型复杂程序跟踪是一个未解决的问题。研究当前方法的局限性后，我们得出了以下见解：由同一 bug 导致的所有崩溃都必须具有（部分）重叠的执行跟踪。此外，分析执行跟踪拓扑结构的方法可用于提取同一 bug 的崩溃信号。

程序执行跟踪是按执行顺序排序的程序地址的采样序列。为了计算它们的相似性，现有方法利用了 Levenshtein 距离 [82] 和最长公子序列 [36]。遗憾的是，程序循环增加了执行跟踪之间的差异，从而限制了这些技术的实用性。即使这些执行跟踪来自相同根本原因的崩溃，它们的序列相似性也很低。但是，将执行跟踪折叠到图形上意味着控制流相似性不再受不同循环迭代计数的影响。因此，我们的方法使用图拓扑来计算跟踪之间的相似性。

控制流图（CFG）

控制流图描述了程序的执行过程。CFG 中的节点表示程序地址，边连接两个连续的地址。为了构建 CFG，我们以预定义的粒度对执行跟踪进行采样。一方面，细粒度 instructionlevel traces 将冗余节点引入 CFG，因为连续指令之间的边被程序执行的顺序性质隐式捕获。此外，记录指令级跟踪会带来可扩展性挑战，使该方法变得棘手。另一方面，函数跟踪很容易收集，但它们是粗粒度的，并且可能会忽略程序中捕获 bug 上下文的关键行为。基本的块级粒度在精度和可扩展性之间提供了平衡，我们使用它来构建 CFG 以进行相似性匹配。

执行跟踪包含必须筛选的噪声。有两种类型的噪声：

在外部共享库（例如 glibc）中执行的代码;
程序崩溃点之后的多余代码（例如，ASan 的崩溃处理程序）。由于我们专注于特定的目标程序，因此不需要外部代码的执行跟踪。因此，我们过滤了目标代码之外的任何地址。排错程序通过引入额外的软件防护来及早检测错误。检测到错误时，排错程序会执行其他代码来收集和报告信息。此信息收集和报告会增加不必要的噪音，并且也会被过滤。我们将在第 4 节中讨论如何过滤这两种类型的噪声（在执行期间和 bug 触发器之后）。

计算图形相似度

记录轨迹后，我们构建一个 CFG 来计算图相似度。高效的图相似性估计已经被广泛研究 [44]，结果表明核方法最适合估计图结构相似性。目前，大多数用于图相似性估计的核方法包括两种：图嵌入和图核。前者利用了基于输入图降维的传统向量核算法，这会导致结构信息的丢失。后者直接在高维 Hilbert 空间中执行核算法，使图的结构信息保持不变。

在调查了不同的图核（例如，标记图、加权图或有向图）后，我们发现 WeisfeilerLehman Subtree Kernel 算法表现出了区分不同根本原因的测试用例的最高能力，同时将高相似性度量分配给相同根本原因的测试用例。因此，我们采用 Weisfeiler-Lehman 子树核来估计 CFG 之间的相似性。Weisfeiler-Lehman Subtree Kernel 算法要求标记图形的节点。我们使用基本数据块地址（来自执行跟踪）作为节点标签。

Bug 集群

模糊测试程序在如何通过目标程序发现错误和路径方面具有高度不确定性。模糊测试程序可能会发现一个或多个 bug 的崩溃，但先验地不知道它会找到多少个崩溃。因此，Igor 无法知道在模糊测试活动期间发现了多少个 bug。例如，一组给定的 100 次崩溃可能会映射到 100 个 bug（每个 bug 有 1 次崩溃）、一个 bug 有 100 次崩溃，或者介于两者之间的任何错误。集群的主要挑战是（a） 发现确切的 bug 数量，以及（b） 将崩溃分配给正确的 bug。如上所述，预期的集群数量是未知的，必须在集群期间推断。我们的方法通过多次运行集群过程来确定集群的数量，根据启发式方法优化假设的错误数量（参见 Section 3.4.2）。

数据特征

Weisfeiler-Lehman 子树核算法生成相似性矩阵 Ms;设 Md = 1 − Ms，其中 Md 是相应的距离矩阵。我们在两个矩阵上构建聚类算法。

矩阵 Ms 和 Md 不足以确定样本的分布。多维缩放（MDS） [10] 是一种降维算法。它通过在低维空间中查找抽象的笛卡尔坐标，将高维数据投影到低维空间，使样本之间的距离几乎保持不变。我们利用 MDS 来可视化样品在二维平面上的分布。

我们根据这些可视化来分析分布。例如，图 3 显示了 x509 的样本在笛卡尔平面上的分布情况。聚类的形状不是球形的，这表明类似 k 均值的方法不合适，因此我们依靠替代方法来识别任意形状的聚类。

Igor 利用剪影分数 [63] 来描述集群结构的质量。通过简化测试用例，样本往往具有更好的聚类结构，见图 7。

聚类算法

DBSCAN [26] 是一种基于密度的聚类算法，它使用相似性/距离矩阵。DBSCAN 算法采用两个参数，ε 和 MinPts，用于定义密度阈值。主要挑战是如何确定这些参数。尽管存在启发式方法[65,67]，但样本密度分布的变化会导致聚类过程失败。OPTICS [3] 和 HDBSCAN* [12] 等替代算法执行分层分析以获得更好的结果。但是，它们仍然需要预定义的密度描述参数，在分析新程序时必须调整这些参数（因为样品的密度分布因程序而异）。

我们发现，谱聚类 [74] 算法解决了存储在 Weisfeiler-Lehman 子树核相似性矩阵中的高维信息带来的参数调整挑战。Spectral Clustering 仅接受一个参数：聚类数。给定聚类数和相似性矩阵，Spectral Clustering 在相似性矩阵的基础上构建一个图 Laplacian。计算图 Laplacian 的特征向量以实现降维。然后，该算法会自动将样本分组到较低维空间中指定数量的聚类中。

由于聚类的实际数量是未知的，因此我们需要一个指标来评估聚类结果。为此，我们再次使用 silhouette 分数。Liu等[49]描述了不同的聚类验证措施。在他们的研究中，他们表明可以通过最大化 silhouette 分数的值来确定最佳聚类数。

由于当只有一个集群时，silhouette 分数是不确定的，因此我们假设数据集中至少有两个集群。然后，我们列举要运行聚类过程的集群数，并计算结果的 silhouette 分数。之后，我们选择具有最高 silhouette 分数的聚类结果。但是，此方法可能会低估集群的数量。因此，我们开发了一种启发式方法，以决定是否需要根据完整长度的崩溃调用堆栈的数量重复聚类：对于少于 20 个调用堆栈，运行一次聚类过程就足够了，而对于超过 20 个调用堆栈，我们聚类两次。表 1 和表 7 显示了我们基于这种启发式方法的实验结果。

单个 bug 的误聚类

紧密散布的子集群的存在表明可能只有一个集群。可检测集群的最小数量为 2。如果只有一个，则在枚举期间人为地增加聚类数，以查找更高的 silhouette 分数。在实践中，模糊测试活动很少只针对一个漏洞找到数百个测试用例。经过数千小时的 CPU 模糊测试后，我们从未观察到这种情况。在这种情况下，使用当前的崩溃分组方法（例如堆栈分桶）就足够了。

为了缓解这种罕见的情况，Igor 将其集群结果与基于调用堆栈的方法（例如 afl-collect）进行比较。如果 Igor 报告的集群数多于 afl-collect，我们会向分析师指示他们应该参考 afl-collect 结果。

实现

我们的 Igor 原型证明了我们方法的实际可行性。我们将在以下部分中简要说明重要的实现细节。完整的源代码可在 https://github.com/HexHive/Igor 上获得。我们在 AFL++ 上实施 IgorFuzz，使用 Intel Pin 记录执行跟踪，并开发多个 Python 脚本来编排 gdb 以选择和过滤执行跟踪。我们使用 NetworkX [32] 从跟踪中构建 CFG，使用 Graphviz [25] 可视化它们，并使用 GraKeL [69] 计算图相似性。聚类阶段利用 scikit-learn [58]。我们的实现由大约 1000 行 C++ 代码和 2500 行 Python 代码以及几个小脚本组成。

记录执行跟踪和噪声筛选。我们开发了 smart-tracer，这是一款基于 Intel Pin 的跟踪记录器，可在函数调用、基本块和指令级粒度上记录执行跟踪。在后处理过程中，我们会过滤掉（a）到辅助代码中（例如，对 libc 的调用），以及（b）触发崩溃后发生的函数调用（例如，排错程序信息收集）。

CFG 相似度指标。筛选的跟踪首先用于构建 CFG。然后，我们使用这个 CFG 通过 Weisfeiler-Lehman Subtree Kernel 算法计算图相似度。

聚类。默认情况下，聚类过程最多运行 15 次，枚举从 2 到 16 的聚类数，并每次（重新）计算 silhouette 分数。此过程将输出具有最高 silhouette 得分的聚类结果。最后，创建聚类后散点图，以帮助分析师直观地评估聚类结果的质量。

实验评价

我们在 12 台运行 Ubuntu 18.04 LTS 的服务器上评估了 Igor，每台服务器具有 200 GiB 的 RAM 和一个具有 40 个内核的 Intel（R） Xeon（R） Gold 6254 CPU @ 3.10GHz。我们的基准测试数据集来自 58.7 个 CPU 年的模糊测试活动。在所有提交的实验中，特定于 Igor 的评估花费了 6,143.7 个 CPU 小时和 30 个人类日。IgorFuzz 评估花费了 5531 个 CPU 小时。重要的是，这并不一定表示最小化所需的实际时间：我们对每个采样的 PoC 运行 IgorFuzz 一小时（总共 5531 个 CPU 小时），以显示随时间的变化。在实践中，我们会让 IgorFuzz 每个 PoC 运行 15 分钟（我们在第 5.4.1 节中演示了这一点）;因此，最小化所有 5531 个 PoC 需要 1382.75 个 CPU 小时。与模糊测试的总成本相比，最小化可以忽略不计，并且消耗的持续时间不到模糊测试活动长度的 0.3%。

标准检查程序

我们在 Magma 基准 [33] 和 MoonLight 数据集 [34， 35] 上评估了 Igor。这些基准测试包含属于 14 个目标程序的 52 个 CVE，包含超过 254,000 个崩溃的 PoC，这些 PoC 映射到 39 个独特的错误。我们排除了四个仅包含单个 CVE 的程序：pdftotext （Poppler）、exif （PHP）、client （OpenSSL）和 libxml2_xml_read _memory_fuzzer （LibXML）。如第 3.4.3 节所述，在这种情况下，Igor 回退到 afl-collect（我们仍然在表 5 中报告这些结果）。此外，我们还排除了（a）两个导致跟踪文件过大（每个 PoC 超过 10 GiB）的 CVE，以及（b）六个 CVE，这些 CVE 与 39 个独特错误之一重复、语义等效或部分修复（有关详细信息，请参阅第 6.3 节）。我们使用精确的地面实况数据来增强这些基准，以验证每个 PoC 的根本原因。

遵循 Klees 等人 [43] 和 Hazimeh 等人 [33] 概述的方法，我们通过修复崩溃的补丁（如果应用）将崩溃映射到错误。重要的是，Magma 和 MoonLight 数据集都包含具有多个 bug 的目标。遗憾的是，多个 bug（在单个目标中）可能会相互干扰（例如，一个 bug 可能会屏蔽/启用其他不会在正常程序执行中表现出来的 bug）。为了最大限度地降低干扰风险，我们根据禁用崩溃的补丁重新标记我们的初始 PoC 数据集。我们在图 4 中展示了这个过程。

从目标的未修补版本开始，我们一次应用一个补丁，每次处理整个 PoC 语料库以标记崩溃状态的变化。如果检测到更改，则该补丁将被视为 PoC 的真实标签，并用于衡量聚类方法的性能。我们在修复崩溃的根本原因时手动验证了补丁的完整性。对于基准测试中的每次崩溃，我们都会标记 root cause 和 call-stack hash。我们的 ground-truth 数据使我们能够确定崩溃是否被正确分组（即，它们是否对应于特定的 CVE）。

结果摘要

表 1 显示了不同 IgorFuzz 截止时间的 Igor 聚类评估结果。截止时间是指我们允许 IgorFuzz 最小化单个 PoC 的时间。这里我们只报告了 15 分钟和 30 分钟的截止时间（由于空间限制），并在附录 D 的表 7 中提供了其他截止时间的结果。

对于 Igor，我们报告基本块级跟踪的集群结果。我们还在函数调用（便宜和最不精确）和指令级别（昂贵和最精确）粒度上评估了 Igor 的聚类结果。虽然三个跟踪粒度的结果相似，但我们认为更好的结果与崩溃网站数量较多的 bug 之间存在相关性。具体来说，我们的结果表明，当崩溃站点的数量超过 ∼ 20 时（例如，对于 xmllint 和 char2svg），Igor 应该切换到指令级跟踪。

虽然根据堆栈哈希对崩溃进行分组是常见的做法，但不同的工具使用不同的堆栈深度。例如，aflcollect 对所有堆栈帧进行哈希处理，honggfuzz 利用最后 7 个堆栈帧，而 CERT BFF [38] 使用最后 5 个帧。我们将 Igor 与这三种配置和单个堆栈帧（在表 1 中称为“Top Frame”）的基线进行了比较。为了衡量分类质量，我们计算了精度、召回率、纯度 [2， 70]、逆纯度 [2] 和 F 度量 [47， 70]。这些指标都是机器学习社区的标准方法。

我们的结果表明，与 Top Frame、BFF-5、honggfuzz 和 afl-collect 相比，Igor 在我们 90% 的实验中实现了最高的 F 度量（在剩余的 10% 中降低了 20%），并且在大多数情况下实现了更高的纯度和逆纯度分数。快速浏览一下表 1，崩溃站点似乎是最好的分组方法，但崩溃站点通常不是唯一的，因为不同的 bug 在同一个程序位置崩溃（参见表 5 中崩溃地址列中的唯一 bug 地址）。

我们还评估了错误计数推理过程造成的精度损失（这本身可能不准确）。我们使用 ground-truth 错误计数重新运行聚类过程，并将这些计数与依赖于推断错误计数的聚类结果进行比较。表 7（在附录 D 中）显示 Igor 的结果与真实错误计数一样准确。