CrashLocator: Locating Crashing Faults Based on Crash Stacks

把堆栈信息扩充+程序调用图，自定义一套算法来给与每个函数一定的故障分数，由高到低进行排序。

摘要

软件崩溃很常见。当崩溃发生时，软件开发人员可以在用户允许的情况下收到一份报告。崩溃报告通常包括崩溃时的调用堆栈。调试崩溃的一个重要步骤是识别有问题的函数，而这通常是一项繁琐且耗费人力的任务。在本文中，我们提出了一种利用崩溃报告中的崩溃堆栈信息定位故障函数的方法—CrashLocator。它通过将崩溃堆栈与静态调用图中的函数进行扩展，推断出可能的崩溃轨迹（导致崩溃的失败执行轨迹）。然后计算近似崩溃轨迹中每个函数的可疑度。然后根据可疑度得分对函数进行排序，并推荐给开发人员作进一步调查。我们使用真实的 Mozilla 崩溃数据对我们的方法进行了评估。结果表明，我们的方法非常有效：通过检查 CrashLocator 推荐的前 1、5 和 10 个函数，我们可以分别定位 50.6%、63.7% 和 67.5% 的崩溃故障。我们的方法明显优于传统的纯堆栈方法。

引言

软件崩溃是软件故障的严重表现。崩溃通常需要优先修复。最近，人们提出并部署了许多崩溃报告系统，如 Windows 错误报告系统 [14]、Apple 崩溃报告系统 [2] 和 Mozilla 崩溃报告系统 [25]。这些系统会自动收集崩溃时的相关信息（如崩溃堆栈和崩溃模块），将可能由同一故障引起的类似崩溃报告归类，并将崩溃信息提供给开发人员进行调试。

现有的崩溃报告系统[2, 14, 25]大多侧重于有效地收集和分类崩溃报告。虽然收集到的崩溃信息对调试很有用，但这些系统并不支持崩溃故障的自动定位。因此，针对崩溃的调试需要大量的人工工作。

多年来，人们提出了各种故障定位技术（如 [1, 18, 21, 22]）来帮助开发人员定位故障。这些技术通过对测试用例的通过和失败执行轨迹进行统计分析，提出可疑程序实体列表。然后，开发人员可以检查排序列表以定位故障。然而，这些故障定位技术都假定有失败和通过的执行轨迹的完整信息，而崩溃报告通常只包含崩溃时转储的崩溃堆栈。

本文提出的 CrashLocator 是一种基于崩溃堆栈和静态分析技术的新型崩溃故障定位技术。我们的技术以定位故障函数为目标，因为函数常用于单元测试，有助于崩溃重现[5, 16]。对于一个广泛使用的系统来说，一个崩溃故障可能会引发大量的崩溃报告。因此，CrashLocator 可以使用足够数量的崩溃堆栈来定位崩溃故障。

CrashLocator 利用静态分析（包括调用图分析、控制流分析和后向切片）将崩溃堆栈扩展为近似崩溃轨迹（导致崩溃的失败执行轨迹）。为了有效定位故障，CrashLocator 采用了术语加权的概念[24]：定位崩溃故障被视为术语加权问题，即计算一个函数（术语）对于一桶崩溃痕迹（文档）的重要性。CrashLocator 在对函数进行加权时会考虑以下几个因素：函数在碰撞痕迹桶中出现的频率、函数在不同碰撞痕迹桶中出现的频率、函数与碰撞点之间的距离以及函数的大小。利用这些因素，CrashLocator 可以计算出近似碰撞痕迹中每个函数的可疑度得分。最后，它会向开发人员返回一份可疑故障函数的排序列表。开发人员可以检查返回的前 N 个函数，以查找崩溃故障。

我们使用 Firefox、Thunderbird 和 SeaMonkey 这三款不同 Mozilla 产品的真实碰撞数据对 CrashLocator 进行了评估。评估结果令人欣喜：使用CrashLocator开发者可以通过检查返回的排序列表中的前 1、5 和 10 个函数，分别定位了 50.6%、63.7% 和 67.5% 的崩溃故障。此外，评估结果表明，我们的方法优于传统的纯堆栈方法。

本文的其余部分安排如下：第 2 节介绍背景信息。第 3 节介绍基于实证研究的一些观察结果，并提出碰撞故障定位问题。第 4 节介绍我们的方法。第 5 节介绍我们的实验设计，第 6 节展示实验结果。第 7 节讨论了我们的方法所涉及的问题，第 8 节讨论了有效性所面临的威胁。第 9 节介绍了相关工作，第 10 节是结论。

主要贡献

我们提出了一种用于定位崩溃故障的新技术。我们的框架仅基于崩溃堆栈，不需要部署站点或程序仪器提供额外信息。据我们所知，这是首次提出这种技术。
我们使用 Mozilla 产品来实施我们的技术和评估我们的方法，这些产品都是真实的流行项目。

背景

尽管在软件质量保证方面付出了巨大努力，但已发布的软件产品在交付时仍经常出现故障。有些故障在软件部署后会表现为崩溃。来自部署站点的崩溃信息对调试崩溃非常有用。

为了收集崩溃信息，人们提出并广泛部署了许多崩溃报告系统，如 Windows 错误报告系统 [14]、Apple 崩溃报告系统 [2] 和 Mozilla 崩溃报告系统 [25]。图 1 给出了崩溃报告系统的概况。当部署地点发生崩溃时，系统会收集与崩溃相关的信息，如产品名称、版本、操作系统、崩溃方法签名和崩溃堆栈。收集到的崩溃信息会在用户允许的情况下发送到服务器端。崩溃报告系统可能会在一段时间内收到大量崩溃报告。由于多个崩溃报告是由同一故障引起的，因此服务器会检查崩溃报告的重复性，并将可能由同一故障引起的报告分配到一个桶中。最后，崩溃报告系统会将错误报告提交给开发人员。

在大型系统（如 Microsoft Windows 和 MozillaFirefox）中，开发人员会收到用户在部署地点发送的大量崩溃报告。这些崩溃报告会根据崩溃方法的特征自动分组[25]。分组是基于崩溃故障导致相同崩溃方法或类似堆栈的假设。理想情况下，每个桶都应对应一个唯一的崩溃故障。在本文中，我们的研究目标是在给出一桶崩溃报告的情况下定位故障函数。

崩溃定位问题

定位崩溃错误的挑战

崩溃报告通常包含有限的信息，如崩溃方法签名和崩溃堆栈。触发故障的执行环境（包括结构覆盖范围）不可用。根据这些有限信息定位故障函数具有挑战性。更具体地说，我们发现了以下两个主要挑战：不完整的崩溃跟踪和不确定的故障位置。

不完整的崩溃跟踪

崩溃堆栈只包含部分崩溃（失败）轨迹，不包含完整的通过执行轨迹信息。因此，许多传统的故障定位技术无法应用。这些故障定位技术允许程序员通过检查一小部分代码来定位故障 [1、18、21、22]。它们将通过的执行轨迹与失败的执行轨迹进行对比，计算单个程序元素（如语句和谓词）的故障可疑度，并给出按故障可疑度排序的程序元素列表。这些技术不能直接用于崩溃故障定位，因为崩溃堆栈不包含完整的通过和失败执行跟踪。另一种方法是采用符号分析技术，从程序崩溃中生成可能的测试套件，并在部署现场应用这些测试套件来收集通过和失败的执行轨迹 [3，4]。不过，这需要提供所有库调用的精确规范，如果程序崩溃可能导致严重的副作用，则会给最终用户带来困难。此外，符号分析成本高昂，可能无法扩展到 Firefox 这样的大型程序。收集完整的通过和失败执行跟踪的另一种方法是在生产环境中部署仪器版本。仪器版本可以监控部署地点的程序执行情况，并向开发人员发送执行跟踪和调试信息。然而，这种监控会大大增加执行开销，在实际生产中很少采用。例如，早期的研究 [23, 32] 分析了动态二进制仪器的开销，发现平均性能开销为对于简单的仪表化来说，平均开销约为 30%-150%。最近的一种方法，即 BugRedux [16]，在函数调用级平均引入了 17.4% 的仪表化开销，这对许多应用来说仍然很高。

故障位置不确定

Schröter 等人[29]调查了 Eclipse 项目的崩溃堆栈。他们的研究表明，许多 Eclipse 崩溃故障的错误修复点都涉及堆栈中的函数，而且错误修复点更有可能出现在前 10 个堆栈帧中。然而，我们对 Firefox 项目的实证研究（将在下一节中展示）表明，许多崩溃故障也存在于从崩溃堆栈中弹出的函数中。因此，仅检查崩溃堆栈中的函数是不够的。故障函数的位置是不确定的—它可能会也可能不会出现在崩溃堆栈中。

碰撞故障实证研究

为了找出存在于崩溃堆栈函数中的崩溃故障数量，我们对 Firefox 进行了实证研究。我们选择了从 4.0b4 到 4.0b6 的三个火狐发布版本。为了找出导致崩溃的实际故障函数，我们对崩溃报告、错误报告和更改日志进行了如下挖掘：

我们分析了 Mozilla Crash Reporter [25] 收集的崩溃报告，并找出了与 Mozilla 错误跟踪系统中的错误报告有链接的崩溃报告。由于一个桶中的崩溃报告数量可能很大，我们按照 Dhaliwal 等人[12]的做法，在每个桶中随机抽取 100 份崩溃报告。如果一个桶中的崩溃报告少于 100 份，我们就收集其中的所有崩溃报告。
对于每个崩溃故障，我们都收集了相应的错误报告，其状态为 “已解决修复 “或 “已验证修复”。我们通过人工检查进一步验证了崩溃报告和错误报告之间的联系。对于崩溃报告和错误报告之间的链接，如果它们描述的是不同的产品版本，我们会在实验中排除该链接。
对于每个错误报告，我们都会通过挖掘源代码库来确定相应的错误修复变更。然后，我们获得了为修复漏洞而修改的相关函数。

按照上述步骤，我们共获得了 1107 份崩溃报告，对应 51 个崩溃故障。我们发现，约有 59% 至 67% 的崩溃故障位于崩溃堆栈的函数中。约 33% 至 41% 的崩溃故障位于其他函数中。

通过实证研究，我们还对包含崩溃故障的函数提出了以下看法：

观察结果 1：每个数据桶中的崩溃报告大多由相同的崩溃故障引起。包含故障的函数经常出现在导致这些崩溃报告的崩溃跟踪中。

直观地说，如果某个函数频繁出现在由某个故障引发的多个崩溃跟踪中，那么它很可能就是引发该故障的原因。在此，我们将崩溃跟踪表示为由崩溃故障引发的失败执行跟踪。在实证研究中，我们调查了错误函数在每个桶中出现的频率，结果发现，对于 89%-92% 的崩溃故障，其相关的错误函数会 100% 出现在相应桶中的崩溃跟踪中。对于 89%-96% 的崩溃故障，相关的错误函数至少出现在 50%的崩溃跟踪中。经验结果表明，包含崩溃故障的函数经常出现在崩溃堆栈中。因此，函数频率可以作为函数可疑性的指标。

观察结果 2：在崩溃跟踪中，包含崩溃故障的函数更接近崩溃点

在我们以前的工作[11]中，我们发现对于某些微软产品，崩溃跟踪中的故障函数比 “干净 “函数更接近崩溃点。这促使我们研究 Firefox 4.0 的故障函数离崩溃点有多近。到崩溃点的距离定义为当前函数与崩溃函数之间的位置偏移。我们的实证研究表明，在 84.3% 的崩溃故障中，相关故障函数与崩溃点的距离小于 5，而在 96.1% 的崩溃故障中，与崩溃点的距离小于 10。结果表明，包含崩溃故障的函数离崩溃点更近。因此，到崩溃点的距离可以作为函数可疑性的指标。

观察结果 3：不包含崩溃故障的函数更改频率通常较低

直观地说，如果一个函数在很长一段时间内没有被更改过，那么它导致崩溃的可能性就会降低。我们调查了崩溃故障的更改次数，发现 94.1% 的故障函数在过去 12 个月中至少更改过一次。结果表明，”干净 “函数的更改频率往往较低。因此，函数更改信息可以作为衡量函数可疑程度的有用指标。

上述观察结果可用于定位可疑函数。我们将在第 4 节介绍的 CrashLocator 的设计中利用这些观察结果。

问题定义

如下图所示，多个崩溃故障的崩溃跟踪可组合成一个矩阵，其中每列表示一个函数，每行表示一个崩溃跟踪。当某个函数被碰撞跟踪覆盖时，标记为 1；否则标记为 0。每个碰撞跟踪都与一个特定的桶相关联。

崩溃故障定位的目标是找出导致崩溃的故障函数。我们需要为崩溃跟踪中的每个函数分配一个可疑分值。开发人员可以通过检查可疑度得分排名靠前的函数来定位故障。

如果我们把从一个桶的碰撞堆栈中得出的碰撞痕迹视为一类文档，把一个函数视为一个术语，那么这样的问题就可以视为一个术语加权问题[24]，即计算一个术语对文档的重要性。正式来说，对于一组桶 B（B1、B2、….Bn）和一组函数 F（f1、f2、……fm），为每个函数 fi 计算一个权重 wi （1 <=i<= £m），以表示 fi 相对于 Bj（1<= j <=n）的可疑程度，这样可疑程度越高的函数权重越高。

CRASHLOCATOR

概述

在本节中，我们将介绍拟议的 CrashLocator 方法。CrashLocator 的整体结构如图 4 所示。给定一组桶式崩溃报告，CrashLocator 首先使用程序的静态函数调用图为每个报告的崩溃恢复近似的崩溃跟踪。由于相关的崩溃堆栈并不包含所有的运行时信息，因此恢复的轨迹只是真实崩溃轨迹的近似值。然后，CrashLocator 会计算恢复跟踪中每个函数的可疑度得分。最后，它会根据可疑分数对函数进行排序，并输出一份排序列表，供开发人员定位故障。我们将在第 4.2 节中介绍恢复崩溃痕迹的过程，并在第 4.3 节中介绍对可疑函数进行排序的方法。

恢复崩溃痕迹

基本崩溃堆栈扩展

包含崩溃故障的函数并不总是存在于崩溃堆栈中。因此，要定位此类崩溃故障，第一步是根据崩溃堆栈恢复崩溃跟踪。崩溃堆栈只记录了崩溃时的堆栈信息，但没有记录执行过程中从崩溃堆栈中弹出的函数。为了推断崩溃前可能执行的函数，我们可以利用静态调用图[28]，它捕捉了崩溃程序的函数调用关系。静态调用图由调用对组成。每个调用对由调用者和被调用者函数组成。举个例子，下午展示了一个简单程序的静态函数调用图，其中每个节点代表一个函数 (fi)。我们使用符号 “fi->fj “表示 fi 调用 fj。

假设程序从 f1 开始，在 f11 处崩溃。崩溃堆栈（图 5(B)）f1->f3->f12->f11 实际上并不是一个完整的崩溃跟踪。直观地说，我们提出了一种简单的崩溃堆栈扩展方法，即根据函数调用图扩展给定的崩溃堆栈。例如，对于 f1，有两个调用对 f1->f3 和 f1->f4，因为 f4 可能在 f3 之前被调用。一旦包含了 f4，f9 和 f13 也会被包含在近似崩溃跟踪中。同样，通过扩展崩溃堆栈中的其他函数（f3、f12 和 f11），也可以获得近似的崩溃跟踪。

为了便于描述崩溃堆栈扩展，我们定义了一个名为 “调用深度 “的概念：

定义函数 fi 对给定崩溃堆栈 S 的调用深度是指从 S 中任何函数调用到 fi 的最少函数调用步数。

例如，图 5(C) 显示了图 5(A) 中函数的调用深度。f1 位于崩溃堆栈中，因此其深度为 0。f13可以被f4 (f1->f4->f13)2步调用，也可以被f12一步调用（f12->f13)。在这种情况下，我们选择最少的调用步数作为调用深度，其调用深度为 1，因为我们选择最少的步数作为调用深度。调用深度控制着故障定位分析的函数集。调用深度的值可根据经验设定；深度值越大，意味着要分析的函数越多。

在碰撞堆栈扩展中，我们还考虑了虚拟函数。虚拟函数在程序运行时动态映射到特定方法。我们采用类层次结构分析方法 [7] 来静态识别虚拟函数调用。我们首先使用静态分析工具 Understand [33] 提取所有虚拟函数之间的重载关系，然后用所有重载函数替换每个虚拟函数。

改进的碰撞堆栈扩展

在崩溃堆栈扩展过程中，函数的数量会随着调用深度值的增加而呈指数增长。在此过程中，可能会引入许多无关函数，这可能会对碰撞定位产生不利影响。我们利用控制流分析、后向切片和函数变化信息来减少无关函数的数量，从而改进了基本的碰撞堆栈扩展算法。

我们的控制流分析类似于 [30] 中描述的方法，其目的是根据崩溃堆栈信息排除无法到达的函数。例如，在图 5(B)和(D)中，帧 0 表示文件 1 中第 1 行的函数 f11 发生崩溃。使用基本扩展方法，f14、f15、f16 和 f17 被包括在内，以便进一步扩展。然而，控制流分析表明，f14 是不可达的，可作为无关函数处理。我们对碰撞堆栈中的每一帧进行控制流分析，并从扩展的碰撞跟踪中排除无关函数。

我们从崩溃点开始，对崩溃堆栈中的每一帧进行后向切分 [34]。例如，在图 5(D) 中，由于崩溃发生在文件 1 的第 1 行，因此变量 s 和 c 与崩溃相关。首先，我们将变量 s 和 c 作为切片的兴趣点。然后，通过逆向切分，我们知道变量 c 受变量 b 的影响，因此我们将 b 纳入切分范围。最后，由于函数 f16 和 f17 与变量 s、b 和 c 相关，我们将这两个函数纳入进一步扩展。

我们还在崩溃堆栈扩展算法中利用了函数变化信息。我们的实证研究表明，如果一个函数在很长一段时间内没有更改过，那么它就不太可能包含崩溃故障。因此，我们选择那些在给定时间内至少更改过一次的函数进行扩展。在我们的工作中，我们根据经验将周期值设定为 12 个月。

通过控制流分析、后向切片和函数变化信息分析，我们可以在碰撞堆栈扩展过程中减少无关函数的数量。CrashStackExpansion 算法会迭代扩展碰撞堆栈。它将 S 和 d 作为输入，其中 S 是碰撞堆栈，d 是预定义的调用深度值。首先，我们将原始碰撞堆栈中的所有函数标记为深度为 0 的函数。然后，对于depth-0 中的每个函数 f i，我们通过控制流分析（CFA）和后向切片分析（BSA）提取函数 f 调用的所有函数，并将不在 ExpandSet 中的depth-1 中。然后，对于depth-1 中的每个函数 f j，我们提取 f j 调用的所有函数，这些函数在一定时期内（如过去 12 个月内）至少被更改过一次，并将那些不在 ExpandSet 中的函数添加到depth-1 中。重复这一过程，直到达到预定义的深度 d。最后，收集所有深度中的所有函数，形成近似的崩溃轨迹。

对可疑功能进行排序

根据我们在实证研究（第 3.2 节）中的观察结果以及我们之前在软件缺陷分析方面的研究 [39, 40, 41]，我们考虑了以下四个判别因素，以识别可能导致崩溃的最可疑功能。

Function Frequency (FF):

如果某个函数频繁出现在由某个故障导致的崩溃跟踪中，那么它很可能就是导致该故障的原因。我们确定了函数频率（FF）这一因子，用于衡量函数 f 在特定故障桶 B 的碰撞痕迹中出现的频率：

$FF(f,B)=\frac{N_{f,B}}{N_B}$

其中，Nf,B 是函数 f 在 B 数据桶中出现的崩溃痕迹数量。NB 是水桶 B 中崩溃痕迹的总数。

Inverse Bucket Frequency (IBF):

如果一个函数出现在许多不同故障导致的崩溃跟踪中，那么它就不太可能是特定故障的原因。我们确定了一个因子 “逆水桶频率”（IBF），它可以衡量一个函数对所有水桶的判别能力：

$IBF(f)=\log(\frac{\#B}{\#B_f}+1)$

其中 #B 是数据桶的总数，#Bf 是碰撞轨迹包含函数 f 的数据桶数量。

Inverse Average Distance to Crash Point (IAD):

如果某个函数离碰撞点更近，则更有可能导致碰撞。我们确定了一个因子 “到撞车点的逆平均距离”（IAD），用于衡量函数与撞车点的距离：

$IAD(f,B)=\frac{N_{f,B}}{1+\sum_{j=1}^n{dis_j(f)}}$

dis j (f) 表示第 j 个碰撞轨迹中碰撞点与 f 之间的距离，其定义如下：

$dis_j(f)=pos_j(f)+CallDepth_j(f)$

其中，posj(f) 是第 j 个崩溃跟踪中崩溃点与展开 f 的堆栈帧之间的位置偏移。CallDepthj(f) 是 f 在第 j 个崩溃跟踪中的调用深度。

Function’s Lines of Code (FLOC):

我们之前对软件缺陷预测的研究 [39] 表明，较大的模块更容易出现缺陷。因此，我们将函数的大小作为一个判别因素。我们以代码行数来衡量功能，并确定一个因子 FLOC 如下：

$FLOC(f)=\log(LOC(f)+1)$

其中，LOC(f) 是函数 f 的代码行数。

综合以上四个因素，我们可以计算出函数 f 相对于数据桶 B 的可疑度得分，具体如下

$Score(f)=FF(f,B)*IBF(f)*IAD(f)*FLOC(f)$

我们的方法会为以下函数分配较高的分数：在某个碰撞桶的碰撞痕迹中出现频率较高、在其他碰撞桶的碰撞痕迹中出现频率较低、距离碰撞点较近以及 LOC 较大。对于每个碰撞桶，CrashLocator 会计算每个函数的可疑得分，根据得分从高到低对所有函数进行排序，并将排序列表推荐给开发人员。然后，开发人员可以检查列表中排名前 N 位的函数，找出崩溃故障。

实验设计

本节将介绍我们评估 CrashLocator 的实验设计。

实验设置

我们选择了三个大型开放源代码项目，即 Firefox 1、ThunderBird 2 和 SeaMonkey 3 作为评估对象，因为它们都维护着 Mozilla Crash Reporter [25] 收集的公开崩溃数据。我们收集了 5 个版本的 Firefox、2 个版本的 Thunderbird 和 1 个最新版本的 SeaMonkey 的崩溃报告。每个版本包含约 9~20K 个源文件和 120K~280K 个函数。Mozilla 崩溃报告程序根据崩溃特征将收集到的崩溃报告整理成不同的堆栈（即具有相同崩溃点的堆栈被归入同一堆栈）。

我们按照第 3 节所述的相同流程收集数据。我们总共收集了 160 个独特的崩溃故障（桶）。表 2 列出了数据集的详细信息。

评估指标

CrashLocator 会根据所有函数的可疑度得分（最上面的函数可疑度得分最高）生成一个排序列表。开发人员可以检查该列表并找出有问题的函数。显然，有问题的函数最好在列表中排名靠前。我们使用以下指标来评估 CrashLocator 的性能：

Recall@N：通过检查返回函数的前 N 个（N = 1、5、10……）函数，可以发现相关函数的崩溃故障百分比。更好的崩溃故障定位技术应能让开发人员通过检查更少的函数发现更多的故障。因此，度量值越高，故障定位性能就越好。
MRR（平均倒数秩）是一种统计量，用于评估生成查询可能答复列表的过程[24]。查询的互易等级是第一个相关答案等级的乘积倒数。平均倒数秩是一组查询结果 Q 的倒数秩的平均值： $MRR=\frac{1}{|Q|}\sum_{i=1}^{|Q|}\frac{1}{rank_i}$ MRR 值越高，故障定位性能越好。在我们的实验中，我们使用 MRR 来测量CrashLocator 定位所有崩溃故障的第一个相关故障函数的能力。

研究问题

为了评估我们的方法，我们设计了实验来解决以下研究问题：

问题 1：CrashLocator 可以成功定位多少故障？

问题 1 评估了我们方法的有效性。为了回答 RQ1，我们在表 2 所述的数据集上对 CrashLocator 进行了评估。对于每个崩溃故障，我们都会检查 CrashLocator 返回的可疑函数排序。如果发现任何与故障相关的函数，我们就认为故障已经定位。我们使用 Recall@N 和 MRR 来评估 CrashLocator 的性能。

问题 2：CrashLocator 是否优于传统的纯堆栈方法？

如第 3 节所述，Schröter 等人[29]发现，许多崩溃故障可以通过手动检查原始崩溃堆栈4 发现。本 RQ 将 CrashLocator 的性能与以下三种基于碰撞堆栈的定位方法的性能进行比较：

在这种方法中，我们从每个水桶中随机抽取一份崩溃报告，根据其在崩溃堆栈中的顺序对函数进行排序，并计算可定位在前 N 个函数中的崩溃故障百分比。由于一个桶中的崩溃报告在堆栈中可能不同，因此在抽取不同的崩溃报告时，函数的排名也会不同。为了克服随机性，我们重复上述过程 100 次，并计算 Recall@N 的平均值作为最终结果。
StackOnlyAverage 方法，在该方法中，我们会计算出桶中出现的每个函数到碰撞点的平均距离。根据平均距离的倒序对函数进行排序。然后，我们计算可在前 N 个函数中定位的崩溃故障百分比，并计算所有故障的 Recall@N 值。
通过 StackOnlyChangeDate 方法，我们从每个桶中随机抽取一份崩溃报告，根据函数最后修改日期的时间倒序对其进行排序，并计算可在前 N 个函数中定位的崩溃故障百分比。我们重复上述过程 100 次，并计算 Recall@N 的平均值作为最终结果。

问题 3：各因素对碰撞定位性能有何影响？

在第 4.3 节中，我们提出了四个因子，即函数频率 (FF) 因子、反向桶频率 (IBF) 因子、反向碰撞点平均距离 (IAD) 因子和函数代码行数 (FLOC) 因子。问题 3 评估了这些因素对碰撞定位性能的影响。为了回答问题 3，我们逐步将这些因素整合到 CrashLocator 中，对所有受试系统进行碰撞定位，并将结果与公式 6（所有四个因素的组合）得出的结果进行比较。

问题 4：提议的碰撞堆栈扩展算法效果如何？

在第 4.2 节中，我们介绍了一种基本的碰撞堆栈扩展方法，该方法基于静态调用图扩展碰撞堆栈。我们还提出了一种改进的崩溃堆栈扩展算法（CrashStackExpansion 算法），它通过利用控制流分析、后向切片和函数变化信息来排除无关函数。问题 4 评估了改进的崩溃栈扩展算法的有效性，并将其与基本扩展算法进行了比较。为了回答问题 4，我们分别使用基本扩展算法和改进扩展算法运行 CrashLocator，并使用 Recall@N 和 MRR 值来评估性能改进情况。

实验结果

本节针对研究问题介绍我们的实验结果。

问题 1：CrashLocator 可以成功定位多少故障？

表 3 显示了 CrashLocator 对受试系统的崩溃故障定位结果。调用深度设为 5。对于每个研究对象，CrashLocator 可以为 47.1% 至 55.6% 的崩溃故障定位相关的故障函数，并将它们排在返回结果的前 1 位。所有研究对象的 Recall@1 值均为 50.6%。对于 53.8% 至 78.8% 的崩溃故障，CrashLocator 可以成功地将相关故障函数排在返回结果的前 10 位。所有版本的 Recall@10 值为 67.5%。结果表明，使用我们的方法，我们只需检查几个函数（超过 121K 个函数），就能定位很大比例的崩溃故障。

表 3 还显示了以 MRR 衡量的 CrashLocator 性能。MRR 值从 0.528 到 0.627 不等。所有对象的 MRR 值均为 0.559。总的来说，评估结果表明，CrashLocator 能有效地根据崩溃堆栈识别出有问题的函数。

问题 2：CrashLocator 是否优于传统的仅堆栈方法？

图 6 显示，CrashLocator 优于仅基于堆栈的三种传统故障定位方法。总的来说（结合所有研究对象），通过检查 CrashLocator 返回的第一个结果，可以定位 50.6% 的崩溃故障，而通过 StackOnlySampling、StackOnlyAverage 和 StackOnlyChangeDate 方法返回的第一个函数，分别只能定位 32.6%、35.6% 和 11.3% 的故障。此外，通过检查 CrashLocator 返回的前 10 个函数，可以找到 67.5%的崩溃故障，而通过 StackOnlySampling、StackOnlyAverage 和 StackOnlyChangeDate 方法返回的前 10 个函数，分别只能找到 54.8%、53.8% 和 46.3%的故障。总体而言，在 Recall@10 方面，CrashLocator 比纯堆栈方法提高了 23.2% 至 45.8%。

表 4 还显示了不同方法在研究对象中取得的 Recall@1 值。CrashLocator 与 StackOnlySampling 相比，提高了 14.3% 到 267%。同样，CrashLocator 与 StackOnlyAverage 相比，提高了 14.3% 至 275%。与 StackOnlyChangeDate 相比，CrashLocator 的改进幅度更大，从 148% 到 1500%。

图 7 显示，就 MRR 而言，CrashLocator 在每个研究对象上的表现也优于纯堆栈方法。CrashLocator 相比 StackOnlySampling 的改进幅度从 28.9% 到 139%，相比 StackOnlyAverage 的改进幅度从 20.7% 到 107%，相比 StackOnlyChangeDate 的改进幅度从 74.1% 到 329%。成对 t 检验也证实了结果的统计意义。

总体而言，CrashLocator 的性能优于传统的纯堆栈方法。这是因为并非所有故障都存在于崩溃堆栈中。纯堆栈方法在定位所有崩溃故障方面存在固有的局限性（存在上限）。

问题 3：各因素对碰撞定位性能有何影响？

图 8 显示了通过逐步应用 IBF 因子、FF 因子、FLOC 因子和 IAD 因子，CrashLocator 的性能（以 MRR 度量）。单独使用 IBF 因子时，性能最低（例如，总 MRR 为 0.102）。当 FF 因子与 IBF 因子以及 FLOC 因子结合使用时，性能会有所提高。最后，当所有四个因素都考虑在内时（即采用 CrashLocator 方法），性能最佳（例如，总体 MRR 为 0.559）。如果用前 N 值来衡量性能，也可以观察到类似的结果。总的来说，IBF、FF、FLOC 和 IAD 这四个因素都有助于提高碰撞定位的性能。与其他因素相比，IAD 因素的贡献更大。

问题 4：提议的碰撞堆栈扩展算法效果如何？

图 9 显示了改进的碰撞堆栈扩展算法与基本扩展算法之间的比较。从 Recall@N（N=1，5，10，20，50）来看，改进的扩展算法比基本扩展算法高出 13.3%-72.3%。在 MRR 方面，改进的扩展算法比基本算法提高了 59.3%。

总体而言，改进的碰撞堆栈扩展算法优于基本算法。这是因为改进后的扩展算法过滤掉了不相关的函数，而且在过滤后，有问题函数的等级也得到了提高。

讨论

不同深度对结果有何影响？

在我们的方法中，采用了调用深度的概念，以便将更多的函数纳入可疑函数的排序列表。调用深度的选择会影响崩溃故障定位的结果。一般来说，增加深度可以定位更多的故障，但同时也会将更多的函数列入排序列表。

表 5 显示了在检查所有版本的前 N 个（N = 1、5、10）返回函数时，在不同调用深度下可发现的崩溃故障总数。调用深度 0 代表未进行任何扩展的原始崩溃堆栈。在深度为 0 的情况下，如果只检查前 1 个函数，可以找到 62 个崩溃故障。这个数字随着调用深度的增加而增加。

当调用深度达到 7 时，通过检查前 1 个返回函数可以发现 82 个崩溃故障。对于 Recall@3 和 Recall@5，我们观察到随着深度的增加而出现的相同趋势。不过，由于深度越深，引入的函数越多，其中不相关的函数会影响相关函数的排名。例如，当深度达到 7 时，Recall@5 和 Recall@10 的值略低于深度为 5 时的值。

CrashLocator 为何有效？

CrashLocator 使用崩溃堆栈扩展方法生成近似的执行轨迹，因此它可以发现不在崩溃堆栈中的错误的函数。我们的实验结果表明，扩展痕迹有助于定位崩溃故障。举例来说，让我们检查一下与 21 次崩溃报告相关的 Firefox Bug 600079。该错误是在函数 mozilla::gl::GLContext::InitWithPrefix 中修复的，而该函数并未出现在崩溃堆栈中。因此，仅检查崩溃堆栈中的函数是不够的。不过，崩溃堆栈中的函数都会调用该函数。CrashLocator 可以通过碰撞堆栈扩展成功定位此类故障。实际上，有问题的函数 mozilla::gl::GLContext:：InitWithPrefix 被 CrashLocator 排在第 4 位。

CrashLocator 还考虑了四个因素来定位与故障相关的函数。函数频率 (FF) 因素的依据是，如果某个函数是崩溃故障的根本原因，那么由该故障引起的大量崩溃痕迹在扩展后都应包含该函数。Inverse Bucket Frequency (IBF) 因子的依据是，如果一个函数出现在许多不同崩溃故障的痕迹中（如日志记录函数），则该函数出现故障的可能性较低。CrashLocator 还考虑了到崩溃点的距离 (IAD) 因素，假设离崩溃点较近的函数更容易发生崩溃。其他人也观察到了这一点 [11，29]。

我们举例说明使用我们的方法可以定位的崩溃故障。让我们检查一下 Firefox Bug 596245，它与 9 个崩溃报告相关。这个错误是在函数 GetStyleContextForElementNoFlush 上修复的。与 Bug 600079 类似，有问题的函数并不存在于崩溃堆栈中。利用崩溃堆栈扩展算法，CrashLocator 可以通过扩展成功地将故障函数纳入可疑列表。如果只考虑 IAD 因素，有问题的函数 GetStyleContextForElementNoFlush 排名第 20 位，排名并不靠前。CrashLocator 还利用了来自整个崩溃堆栈桶的信息。FF 因子会给偶尔接近崩溃堆栈顶部的函数较低的分数，而 IBF 因子会给常用函数较低的权重。通过结合 IAD、FF 和 IBF 因子，CrashLocator 减少了无关函数的排名，并将故障函数 GetStyleContextForElementNoFlush 的排名提升至第 7 位。因子 FLOC 进一步提高了优先级，最终 CrashLocator 可以将故障函数排在第 4 位。

在我们的方法中，CrashLocator 利用的是与同一崩溃故障相关的崩溃堆栈信息（即在同一个桶中）。一个桶通常包含许多从不同客户端收集的崩溃堆栈。不过，也有可能一个桶中只有一份崩溃报告。在这种极端情况下，CrashLocator 仍能正常工作。FF 和 IBF 因子不会对故障函数的权重分配产生任何影响。但是，IAD 和 FLOC 因子仍可为可疑函数分配更高的分数。例如，在 Firefox 4.0b8 中，9 个崩溃故障（桶）只有一个崩溃报告，其中 6 个可以通过 CrashLocator 成功定位。

尽管 CrashLocator 很有效，但即使在扩展崩溃堆栈后，它仍无法定位所有崩溃故障。例如，与多线程相关的故障就很难定位。为了说明这一点，我们以 Bug 505059 为例。该错误会影响构造函数 nsStyleSheetService 及其析构函数。根据 Firefox Bugzilla 中记录的开发人员的评论，该崩溃是由多个线程访问服务对象的同一引用引起的。由于对象的初始化和销毁是在其他线程中完成的，因此 CrashLocator 无法定位此类故障。有效发现所有类型的崩溃故障仍是未来的一项重要工作。

更好的分桶算法能否提高碰撞故障定位性能？

在第 5 节所述的实验中，我们使用了 Mozilla Crash Reporter [25] 提供的碰撞数据。碰撞报告分为 160 个桶。Mozilla 采用的分桶算法并不完美，因为有些桶是重复的。我们分析了分桶准确性对崩溃故障定位性能的影响。我们手动检查这些桶并合并重复的桶（从而使每个桶对应一个唯一的故障），然后在 “完美 “的桶上再次运行 CrashLocator。结果表明，即使采用了更好的桶算法，故障定位性能也没有显著差异（差异小于 0.002，不具有统计学意义）。这是因为重复桶提供的额外碰撞轨迹也可用于有效的碰撞故障定位。

对有效性的威胁

我们认为有效性面临以下威胁：

对象选择偏差：在本实验中，我们只使用了来自 Mozilla 产品的数据，因为很难获取真实世界的碰撞报告。我们找不到任何其他开源项目拥有大量收集整理良好的公开碰撞报告。今后，我们将在包括工业项目在内的更多项目上对 CrashLocator 进行评估。
数据量大：当碰撞报告数量较大时，我们的方法会更有效。对于小型或寿命较短的系统来说，碰撞报告的数量通常较少，因此不适合进行统计分析。
碰撞数据质量：在本实验中，我们直接使用了 Mozilla 碰撞报告系统提供的碰撞数据。碰撞数据的质量可能会影响故障定位性能。虽然我们收集了不同 Mozilla 产品的碰撞报告，但数据仍可能存在偏差。今后，我们将研究测量和改进碰撞数据质量的技术。
经验评估：在本文中，我们设计了实验来评估 CrashLocator 的有效性。最终，故障定位方法的实用性应由实际开发人员在实际调试实践中进行评估。开展用户研究是未来的一项重要工作。

结论

本文提出的 CrashLocator 是一种自动定位崩溃故障的新技术。CrashLocator 基于崩溃堆栈，通过堆栈扩展生成近似崩溃跟踪，计算近似崩溃跟踪中所有函数的可疑度分数，并返回可疑函数的排序列表。我们在三个 Mozilla 产品的八个版本上进行的评估表明，所提出的方法能有效定位崩溃故障。使用 CrashLocator，我们只需检查前 1、5 和 10 个函数，就能定位 50.6%、63.7% 和 67.5% 的崩溃故障。评估结果表明，我们的方法明显优于传统的纯堆栈方法，Recall@10 的改进幅度从 23.2% 到 45.8%。

今后，我们将在包括工业项目在内的更多项目中对 CrashLocator 进行评估。我们还将尝试将 CrashLocator 集成到碰撞报告系统中，并评估其实际效果。

阅读笔记：CrashLocator: Locating Crashing Faults Based on Crash Stacks