DeFault: Mutual Information-based Crash Triage for Massive Crashes

快速删除大量崩溃痕迹的重复数据，并准确定位独特崩溃的根本原因
使用互信息量将崩溃分组去重
利用神经网络来识别根本原因的基本块。

摘要

随着现代模糊测试基础设施取得的巨大成功，产生的崩溃比以往任何时候都多。为了挖掘根本原因，对大量 crash 进行快速而忠实的崩溃分类一直很有吸引力。然而，由于在不影响效率的情况下降低分析不精确度的实际困难，这一目标并未实现。

在本文中，我们提出了一种端到端的崩溃分类解决方案 DeFault，用于准确、快速地从大量崩溃中查明独特的根本原因。特别是，我们根据互信息量化程序实体的“崩溃相关性”，这是唯一崩溃桶的标准，并允许我们在不预先分析其根本原因的情况下对大规模崩溃进行桶存储。“crash relevance” 的量化也用于缩短长 crashing trace。在此基础上，我们利用神经网络的可解释性，通过评估每个基本块对崩溃标签的影响，精确定位缩短轨迹中的根本原因。使用 20 个程序进行评估，总共发生 22216 次崩溃，DeFault 表现出卓越的准确性和性能，这远远超出了最先进的技术所能达到的水平：以超快的处理速度实现崩溃重复数据删除——每条崩溃跟踪 0.017 秒，没有遗漏任何独特的错误。之后，它确定了 43 次唯一崩溃的根本原因，没有漏报，平均误报率为 9.2%。

1 引言

软件漏洞是网络空间中普遍存在的威胁。为了发现和消除软件漏洞，模糊测试已被认为是最有效的方法之一，它通过随机或战略性地生成大量输入来馈送程序并触发程序异常。例如，模糊测试基础设施 ClusterFuzz 在 2020 年 9 月在 Google 产品（例如 Chrome）中发现了超过 25,000 个错误，在 340 多个开源项目中发现了大约 22,500 个错误 [3]。尽管在触发崩溃方面取得了相当大的进展，但后续过程（崩溃分类）仍然不精确、耗时且劳动密集。

准确性、效率和通用性是当前碰撞分类技术的主要关注点。但是，缺乏一个系统的解决方案，可以平衡权衡并实现准确、快速和全自动的崩溃分类。在过去十年中，尽管对崩溃分类进行了大量研究，包括崩溃重复数据删除 [16， 18， 27， 29， 33， 34] 和故障定位 [5， 10， 20， 25， 26， 31， 42， 44， 47， 48]，但这些方法的有效性因不同的漏洞类型、崩溃报告和运行环境而异，因此不太适用于一般程序。特别是，一系列先前的崩溃重复数据删除方法在函数调用级别的粒度上工作，并且无法通过检查崩溃的实际根本原因来存储崩溃，这可能会导致触发但错过的关键漏洞。另一项研究旨在通过检查崩溃的根本原因或用崩溃路径的限制来表示根本原因来删除重复的崩溃，当处理的崩溃数量增加时，这需要花费大量时间。在故障定位方面，鉴于以往的统计方法无法捕获根因基本块的序列信息，严重影响了识别的准确性。更重要的是，这些方法只输出一组基本块的可疑分数，例如，前 20 个基本块。在实践中，这并没有为分析师提供足够的指导，因为他们仍然有一组基本的候选块需要检查。

在本文中，我们提出了一种名为 DeFault 的端到端崩溃分类解决方案，用于快速删除大量崩溃痕迹的重复数据，并准确定位独特崩溃的根本原因。我们借用了信息论中的互信息概念，将 crash 分类视为一个信息挖掘过程。关键的见解是，程序实体（例如，函数和基本块）的互信息是它们与崩溃相关性的度量。我们利用这样的 “崩溃相关性”：（1）作为在崩溃重复数据删除中存储唯一崩溃的标准;（2）在我们基于神经网络的故障定位中识别并过滤掉不相关的程序实体，以缩短痕迹。无需检查每个崩溃的根本原因，我们的方法即可在短时间内完成崩溃重复数据删除，而不会遗漏错误。在随后的故障定位过程中，再次使用有关“crash relevance”的互信息来过滤与崩溃无关的程序实体，从而缩短较长的执行跟踪，从而促进将输入馈送到神经网络。在此基础上，在最后一步中，我们利用神经网络的可解释性，从缩短的轨迹中提取实际的根本原因。与传统方法相比，神经网络能够捕获序列信息，显著提高了根本原因识别的准确性。

我们实现了一个功能齐全的 DeFault 原型，并使用 20 个程序对其进行了评估，其中包括 8 个 CGC 程序和 12 个真实程序。一方面，对于崩溃重复数据删除，DeFault 以每条跟踪 0.017 秒的速度处理了 22216 个崩溃跟踪。它识别了 42 个唯一的崩溃跟踪，没有遗漏任何错误。关于故障定位，它报告没有漏报和 9.2% 的低假阳性率，这远远超出了最先进的工具所能达到的水平。

路线图。本文的其余部分组织如下：第 2 节调查了相关研究。第 3 节提供了必要的背景，涵盖了互信息和神经网络可解释性的注意力机制。第 4 节描述了 DeFault 的详细设计。第 5 节介绍了评估结果以及与现有技术的比较。第 7 节总结了本文。

贡献

新技术。我们提出了一种基于互信息来衡量程序实体的“崩溃相关性”的新方法，这对于崩溃重复数据删除和故障定位至关重要。通过这种方法，我们设计并提出了一种新颖的端到端分析系统 DeFault，它直接将模糊测试器的崩溃执行跟踪作为输入，并自动查明程序错误的根本原因。
评估。我们评估了 20 个程序的 DeFault，包括 8 个 CGC 程序和 12 个真实程序。结果表明，DeFault 既高效又准确。该工具公开可用于持续研究1。

2 相关工作

在本节中，我们将回顾用于软件测试的崩溃重复数据删除和故障定位的相关工作。还总结了现有方法的局限性。

崩溃重复数据删除

崩溃重复数据删除旨在对模糊测试程序生成的崩溃进行聚类，并从具有相同根本原因的每个集群崩溃组中选择一个唯一的崩溃（或代表性崩溃）。后续的故障定位将针对此类唯一崩溃执行。随着模糊测试基础设施产生的崩溃越来越多，崩溃重复数据删除已成为一项迫切需求，从而减轻了后续故障定位的负担。然而，现有的方法远非准确和实用，因为它们要么是粗粒度的，要么是做出某些假设的。下面我们介绍相关工作。

调用基于堆栈的重复数据删除。广泛使用的基于调用堆栈的方法测量调用堆栈上函数的函数调用序列 [16， 18， 27， 29]、函数参数 [9] 或调用图 [23] 之间的相似性。通常，此类方法是粗粒度的。如果具有不同漏洞的程序在同一函数中崩溃，则调用基于堆栈的重复数据删除将错过唯一的崩溃。

基于约束的重复数据删除。作为典型的代表，Pham et al. [33] 和 Podelski et al. [34] 收集了对失败路径和通过路径的约束，并推断出它们最长的公共前缀，这进一步用于描述失败的语义。重复数据删除基于独特的符号语义进行。然而，受到符号执行技术 [11， 14] 的缺点（例如，控制流依赖性和无法解决的约束）的阻碍，这些方法对于现实世界程序的大规模崩溃来说可扩展性较差。

基于补丁的重复数据删除。基于补丁的重复数据删除首先在崩溃点自动修复特定漏洞 [12， 28， 37]（例如缓冲区溢出和空指针取消引用），然后观察是否可以重现未修复的崩溃。无法重现的崩溃将聚集到同一组中。这种方法依赖于源代码分析和特定的漏洞类型，更不用说程序转换的副作用了。因此，它不太适用于漏洞类型未知的二进制程序。

基于报告的重复数据删除。基于报告的重复数据删除利用信息检索技术来分析崩溃报告的文本信息。例如，Wang et al. [38] 利用主题模型，Scaffle et al. [35] 使用神经网络，Ye et al. [46] 利用排序算法来提取与崩溃相关的信息，如调用序列和漏洞修补的历史。Kim et al. [22] 使用机器学习技术来预测根本原因，以区分各种车祸。但是，基于报告的方法过于粗糙，通常在函数级别执行。除此之外，有效性还取决于 OS 或调试器写入记录的方式，而 OS 或调试器可能无法提供足够的崩溃相关信息。

故障定位

自动故障定位技术利用运行时目标程序的统计信息来定位程序故障。相关工作可分为以下几类：

对基于频谱的方法进行编程。程序频谱（例如程序路径执行的统计信息）是程序运行状态的度量。Collefello 等 [15] 首次利用程序频谱进行故障定位。通过比较程序实体的正常退出和崩溃统计信息，为每个程序实体给出可疑分数。通常，程序实体在崩溃样本中的执行时间比普通退出样本多，程序实体获得的分数就越高。程序实体的分数可以根据各种方法进行计算和排序 [5， 10， 19， 20， 25， 26， 31， 42， 44， 47， 48]。但是，现有的方法都只考虑样本中是否存在程序实体，而忽略了某个样本中实体的执行时间及其执行顺序。如第 5 节所示，如果没有这样的序列信息，基于程序频谱的故障定位将不可避免地引入不精确性。

基于机器学习的方法。基于机器学习的方法 [30， 32， 36， 50] 将项目实体视为输入，并利用分类系统输出每个项目实体的根本原因概率。例如，Liu et al. [30] 将程序的执行流程表示为图形。此外，他们还使用图形挖掘方法来提取有关程序故障的子图，并使用 SVM 来确定每个子图对崩溃的贡献。同样，Nessa 等人 [32] 使用 N-Gram 来计算程序实体在执行跟踪到崩溃的条件概率。然而，与基于程序谱的方法类似，这些研究无法恢复根本原因基本区组的序列信息。

基于程序切片的方法。程序切片技术 [39]，包括静态切片和动态切片，用于计算一组可能影响某个感兴趣点的值的程序语句。特别是，动态切片 [6] 经常通过分析程序执行跟踪来用于故障定位。Agrawal 等人 [7] 利用动态切片，通过计算切片的交集来定位程序故障。Wang等[40,41]使用动态切片，通过分析程序实体之间的数据依赖性来查明程序故障。Zhang等[51,53]使用动态切片来提取与崩溃相关的变量的变化，以找到根本原因。此外，Xu et al. [43] 在 Intel PT 的支持下使用向后程序切片来定位程序故障。然而，由于控制流依赖性问题——数据流分析的一个基本缺点，这些方法的有效性并不令人满意。

2.3 先前研究的局限性

尽管在碰撞分类的研究上投入了大量精力，但现有方法仍然存在多个关键局限性，如下所述。

共性。崩溃分类技术的有效性因漏洞类型、崩溃报告和运行环境的不同而有很大差异，因此不太适用于一般程序。
准确性。之前的崩溃重复数据删除方法在函数调用级别的粒度上工作，并且无法通过检查崩溃的实际根本原因来存储崩溃，这可能会导致不精确和遗漏错误。另一方面，现有的故障定位方法不考虑序列信息，这再次引入了不精确性。
耗时。为了对崩溃进行存储，现有方法会检查每个崩溃，而不管粒度如何。在此之后，所有崩溃之间的成对匹配是不可避免的，随着崩溃数量的增加，这需要很长时间。

3 准备

本节提供了一些必要的互信息背景，并介绍了神经网络的注意力机制。

3.1 互信息

3.2 神经网络的注意力机制

4 默认设计

我们系统的高级设计如图 1 所示。输入是由模糊测试程序生成的一组崩溃的执行跟踪。这些跟踪记录将馈送到崩溃重复数据删除模块中，该模块根据其根本原因将崩溃跟踪记录分为多个类别，并输出一个具有代表性的崩溃跟踪记录，每个类别具有唯一的根本原因。然后，将每个类别的代表性崩溃轨迹发送到过滤模块，该模块由两个过滤步骤组成 – 函数过滤和基本块过滤。它过滤掉了 trace 中与崩溃无关的绝大多数函数和基本块，以便后续模块中的神经网络可以将缩短的 trace 作为其输入。最后，故障定位模块利用 attention 机制来识别一组导致崩溃的基本块。

4.1 崩溃重复数据删除

崩溃去重有两个步骤：首先，我们根据计算出的基本区块的互信息，将崩溃的 Trace 分为多组;然后，我们从每个组中选择一个具有代表性的崩溃跟踪。所选代表性崩溃的根本原因彼此不同。

分组。假设 traceTA 崩溃的根本原因包括基本块 bA，并且 bA 不包含在崩溃的跟踪 TB 中。因此，我们可以将这两条迹线分为两组：一组包含带 bA 的迹线，另一组包含不带 bA 的迹线。受此启发，我们将数据集分为两组：组 GA 是具有基本块 bˆ 的崩溃跟踪集;另一个组 GB 没有基本块 bˆ 的崩溃跟踪集。基本块 bˆ 在数据集 D 中具有最高的 I （y|b， thˆd），这被认为对特定崩盘有重大贡献。

我们对组 GB 重复上述分组步骤，直到没有崩溃的跟踪。在这样的初步分组过程之后，组中的大多数崩溃跟踪都具有相同的根本原因。

由于具有不同基本数据块统计信息的跟踪可以分为不同的组，因此这种分组算法会产生误报。尽管如此，它不会给出假阴性。例如，假设跟踪 TC 中的基本块 bc 和跟踪 TD 中的基本块 bd 与相同的根本原因相关（即，跟踪 TC 和跟踪 TD 具有相同的根本原因），但 bc 和 bd 的出现次数不同。当根本原因导致程序中的不同崩溃点时，就会发生这种情况。因此，我们的算法会将迹线 TC 和迹线 TD 分为两个不同的组。幸运的是，尽管生成的组多于基本事实，但过度分类不会错过模糊测试程序生成的崩溃跟踪的任何根本原因。我们在算法 2 中展示了完整的分组算法。

选择代表性的崩溃跟踪。在一个组中，当崩溃跟踪包含一个基本块 bˆ 和另一个基本块 b1（这是另一个唯一崩溃的根本原因）时，此崩溃跟踪不能表示此组。这将导致后续步骤中出现误报和漏报。因此，要代表这组，我们需要选择一个 crashing trace，其 rootcause basic blocks 只包括一个准则 basic block bˆ，而不包含其他唯一 crash 的基本 block。为此，我们根据所有标准基本块的出现情况，对一组内的崩溃轨迹进行排名。如果崩溃的跟踪出现更多的 criteria 基本块，则它会获得更高的分数。最后，我们选择得分最低的崩溃跟踪来表示它的组，这意味着崩溃的跟踪更“纯”。算法 3 中介绍了该算法。

4.2 过滤器

选择具有代表性的崩溃跟踪后，过滤模块（如图 2 所示）将执行初步过滤，以过滤掉与崩溃无关的函数和基本块。它可以大大缩短崩溃的跟踪的长度，并促进神经网络模块处理缩短的跟踪。

构建数据集。为了涵盖更多基本块并全面评估不同基本块的执行如何影响崩溃，我们构建了一个从唯一崩溃跟踪中生成的数据集。我们使用 afl-fuzz 来改变单个崩溃的 input，并培育探索不同基本块的 Input。afl-fuzz 的输出可以分为崩溃输入和非崩溃输入。请注意，在极端情况下，例如，当 afl-fuzz 触发新的崩溃时，后续过程不会受到影响。非崩溃的 inputs 是通过随机改变崩溃的 inputs 来获得的。这样，崩溃跟踪中的很大一部分基本块也会出现在非崩溃跟踪中，并且这些基本块与崩溃无关。因此，在数据集中，那些重叠的基本块的统计数据与崩溃相关基本块的统计数据明显不同。它有助于形成具有可微分和足够样本的数据集。请注意，此数据集还用于 Section 4.3 中的神经网络训练。

过滤掉不相关的函数。在程序中，存在一些低级函数，如数据复制函数、链表的操作函数以及结构体或对象的构造函数/析构函数。当这些函数在根本原因附近被调用时，这些函数的基本块的互信息将非常接近实际根本原因的互信息，这会给结果带来误报。因此，我们在函数级别计算互信息，以过滤掉与实际根本原因无关的函数。

过滤掉不相关的基本块。过滤不相关的函数之后，下一步是过滤掉不相关的基本块。我们将数据集表示为 D =< B， Y >，其中 n 是样本量，B = {B1， B2， …， Bn } 是基本块级别的一组执行跟踪，Y = {y1， y2， …， yn } 是执行跟踪的标签集。在筛选数据集中不相关的函数后，筛选的执行跟踪变为 Br = （br1， br2， …， brn ），其中 bri 是一个基本块。通过计算 brj 到标签 y = 0 的互信息，我们可以选择对崩溃贡献更大的基本块集。

4.3 故障定位

在过滤了不相关的函数和基本块之后，跟踪的大小大大减小，这变得适合馈送神经网络。在故障定位模块中，我们利用神经网络来识别根本原因的基本块。短迹线中的基本块具有很高的互信息值，可标记为 y = 1。但是，到目前为止，它们仍然不能被视为根本原因，因为一些不是根本原因但接近根本原因的基本块也获得了很高的互信息值。根本原因是 Basic Block 的统计信息在其执行跟踪中不包含序列信息。由于所有现有方法都无法恢复执行跟踪中的序列信息，尤其是在处理长序列中的依赖关系时，我们利用带有注意力机制的 LSTM 来建模和捕获有关根本原因的序列信息。更具体地说，我们有数据集 D =< Bv， Y >，其中 Bv 是由选定基本块序列组成的执行跟踪集，Y 是相应标签的集合。该模块利用神经网络来计算每个基本区块与崩溃的相关性分数。根本原因是导致崩溃的基本块，这由相关性分数表示（即，基本块的相关性分数越高，表示对崩溃的贡献更大）。

神经网络的输入和输出。用于训练网络的数据是缩短的基本块。正样本是缩短的碰撞迹线，负样本是缩短的非碰撞迹线。我们使用 one-hot 向量对输入进行编码：将迹线 Bv 中基本块 bvi 的数量表示为 nb 。然后，基本块 bvi ∈ Bv 表示为习，其中习 = {0， 1}nb 和 jnb=0 |习 j |2 = 1。输入为 X = （x1， x2， …， xn）。由于输入的长度不同，我们选择最长的 Bv 作为输入长度，并用大小为 nb 的零向量填充短输入。每个 basic block 在 input 中都是相互独立的。需要通过神经网络的权重分配来恢复基本块之间根本原因的序列信息。神经网络的输出是表示是否触发崩溃的布尔值。此外，我们使用上采样 [4] 来平衡数据集中的负样本和正样本。

网络结构。网络结构是经典的具有注意力机制的 LSTM 网络。