英语原文共 34 页，剩余内容已隐藏，支付完成后下载完整资料

译文

软件故障定位研究

摘 要

软件故障定位，即识别程序中故障位置的行为，被广泛认为是程序调试中最繁琐、耗时和昂贵但同样关键的活动之一。由于当今软件的规模和复杂性不断增加，当故障发生时，手动定位故障正在迅速变得不可行，因此，对能够指导软件开发人员在一个程序中以最小的人为干预的故障位置的技术有着强烈的需求。这种需求反过来又推动了广泛的故障定位技术的提出和发展，每一种技术都旨在简化故障定位过程，并通过以独特的方式解决问题，使其更加有效。在这篇文章中，我们对这些技术进行了分类并提供了一个全面的概述，并讨论了关键问题和关注点。

索引术语：软件故障定位，程序调试，软件测试，执行跟踪，可疑代码，调查

1引言

软件对我们今天的生活至关重要，它的使用和采用越来越多，其影响几乎无处不在。事实上，目前，软件不仅应用于医药、航空航天和核能等行业的许多安全和安全关键系统，而且对这些系统至关重要。毫不奇怪，伴随这一趋势的是软件的规模和复杂性急剧增加。不幸的是，这也导致了更多的软件错误，这往往导致执行失败，损失巨大[260]、[275]、[365]。此外，安全关键系统中的软件故障具有重大影响，不仅包括财务损失，而且还包括潜在的生命损失，这是一个令人震惊的前景[368]。国家标准和技术研究所(NIST)2002年的一份报告[304]指出，软件错误估计每年使美国经济损失595亿美元 (占国内生产总值的0.6%)；从那时起，成本无疑有所增加。修复或响应这些错误的一半以上的成本转嫁给软件用户，而软件开发人员和供应商吸收其余的。

即使由于错误的行为或错误的其他表现而发现软件中的错误，找到和修复它们是一件完全不同的事情。故障定位，侧重于前者，即识别历史上，故障的定位一直是一项人工任务这已经被认为是耗时且乏味的以及昂贵得令人望而却步的[347]，因为当今大规模软件系统的规模和复杂性。此外，手动故障定位在很大程度上依赖于软件开发人员的经验、判断和直觉来识别和优先处理可能有故障的代码。这些限制导致人们对开发技术的兴趣激增，这些技术可以部分或完全自动化软件中故障的局部化，同时减少人类输入。虽然有些技术是相似的，有些技术是非常不同的（在所消耗的数据类型、程序组件的重点、比较有效性和效率等方面）。他们每个人都试图从一个独特的角度来解决故障定位问题，并且通常提供相对于彼此的优点和缺点。由于已经存在许多技术，而且其他技术不断被提出，并且从理论和实践的角度都取得了进展，因此必须对故障定位方面的现有技术进行编目和概述，以便为已经在该领域工作的人以及对此有兴趣的人提供全面的资源。

为了提供一份完整的调查，涵盖自1970年代末以来与软件故障定位相关的大多数出版物，我们创建了一个出版物存储库，其中包括1977年至2014年11月发表的331篇论文。我们还寻找硕士和博士与软件故障定位密切相关的论文，列于表1。

我们仓库里的所有文件都是按年份分类的，结果如图1所示。如图所示，2001年后出版物的数量迅速增长，表明在过去10年中,越来越多的研究人员开始致力于软件故障定位领域。

此外，根据我们的存储库，图2给出了从2001年到2014年11月出现在高质量和领先的软件工程期刊和会议上的与软件故障定位相关的出版物数量，这些期刊和会议主要关注软件工程-美国电气工程师学会软件工程学报、美国计算机学会软件工程与方法论学报、国际软件工程会议、美国计算机学会软件工程基础国际研讨会和美国计算机学会自动化软件工程国际会议。这一趋势再次支持了这样一种说法，即软件故障定位不仅是一个重要的，而且是一个流行的研究课题，在过去十年中，在高质量的软件工程期刊和会议上进行了大量的讨论。

因此，关于各种技术的大量文献旨在促进故障定位并使其更有效。尽管这些技术有着相似的目标，但它们之间可能有很大的不同，而且往往来自几个不同学科的想法。虽然我们的目标是全面涵盖尽可能多的故障定位技术，但没有一篇文章，无论广度或深度，都可以涵盖所有这些技术。在这次调查中，我们主要关注的是博柏格的技术[139]。那些用于诊断曼德尔伯格[139]如性能缺陷，内存泄漏，软件膨胀，和安全漏洞不包括在范围内。此外，由于篇幅有限，我们将技术分成适当的类别进行集体讨论，重点放在最重要的特征上，并将这些技术的其他细节留给各自发表的论文。针对特定应用领域的技术尤其如此，例如并发错误和电子表格的故障定位。对于这些，我们提供了一个帮助读者理解的综述。

以下术语在本文中反复出现，因此为了方便起见，我们在这里根据[37]中提供的分类法为它们提供定义：

• 失败是指服务偏离其正确行为。
• 错误是系统中可能导致故障的条件。
• 错误是错误的根本原因，也称为错误。

本文的其余部分以下方式组织:我们首先在第2节中描述传统和直观的故障定位技术，然后在第3节中转向更先进和复杂的技术。在第4节中，我们列出了一些流行的主题程序，这些程序已经在不同的案例研究中使用，并讨论了这些程序是如何演变的。在第5节中描述了评估故障定位技术有效性的不同评估指标，然后在第6节中讨论了故障局部化工具。最后，在第7节和第8节中分别介绍了关键方面和关键问题。

2传统的失败定位技术

本节描述传统和直观的故障局部化技术，包括程序日志记录、断言、断点和分析。

2.1程序记录

用于生成程序日志的语句(如打印)通常以临时方式插入到代码中，以监视变量值和其他程序状态通知[105]。当检测到异常的程序行为时，开发人员根据保存的日志文件或打印的运行时信息检查程序日志，以诊断故障的原因。

2.2协助

断言是添加到程序中的约束，在程序的正确操作过程中必须是真实的。开发人员在程序代码中将这些断言指定为条件语句，如果它们评估为false,则终止执行因此，它们可以用来检测运行时的错误程序行为。使用断言进行程序调试的更多细节可在[309]、[310]中找到。

2.3断点

断点用于在执行时暂停程序到达指定点并允许用户检查当前状态。在触发断点后，用户可以修改变量的值或继续执行以观察bug的进展。数据断点可以配置为在指定表达式的值变化时触发，例如变量值的组合。连续断点只在满足用户指定的谓词时暂停执行。早期的研究(例如[80]，[155])使用这种方法来帮助开发人员在程序在符号调试器控制下执行时定位错误。更先进的调试工具，如GNUGDB[121]和Micros of Visual Studio调试器[255]也采用了同样的方法。

2.4概况

分析是对执行速度和内存使用等度量的运行时分析，这通常是针对程序优化的。但是，还可以利用这一工具进行调试活动，例如:

• 检测不同功能的意外执行频率(例如[43])
• 识别内存泄漏或性能出乎意料地差的代码(例如[150])
• 检查懒惰评估的副作用(例如[313])。用于程序调试的分析工具包括GNU的gprof [120]和Eclipse插件TPTP[108]。

3改进的不平衡定位技术

随着当今软件系统的庞大规模和规模，传统的故障定位技术在解决故障的根本原因方面并不有效。因此，最近出现了许多先进的故障定位技术，使用因果关系[215]，[288]的思想，与哲学理论有关，目的是描述事件/原因(在我们的情说下是程序错误)和Phenomenon效应(在我们的情况下是执行失败)之间的关系。有不同的因果关系模型[288]，如基于反事实的、基于概率或统计的和基于因果关系的微积分模型。其中，概率因果关系模型在故障定位中应用最广泛，以识别负责执行失败的可疑代码。

在本次调查中， 我们将故障定位技术分为八类，包括基于切片、基于频谱、基于统计、基于程序状态、基于机器学习、基于数据挖掘、基于模型和杂项技术。许多评价特定故障定位技术有效性的研究报告[8]、[10]、[11]、[12]、[25]、[31]、[36]、[49]、[53]、[91]、[93]、[94]、[102]、[124]、[178]、[185]、[191]、[207]、[209]、[253]、[266]、[267]、[296]、[299]、[335]、[366]、[390]、[391]、[393]、[420]、[406]、[410]、[424]。然而，没有一个国家对所有这些技术进行全面讨论。

3.1切片技术

程序切片是一种技术，通过删除不相关的部分，将程序抽象成一个简化的形式，这样得到的切片相对于某些规范仍然会表现出与原始的程序相同的性能。自Weiser于1979年[361]首次提出静态切片以来，已发表了数百篇关于这一主题的论文[52]、[344]、[394]。

静态切片[360]的重要应用之一是减少搜索域，而程序员在他们的程序中定位错误。这是基于这样的想法，即如果测试用例由于状态下的变量值不正确而失败，那么缺陷应该在与该变量语旬对相关联的静态切片中找到，允许我们将搜索限制在切片上，而不是查看整个程序。莱尔和威瑟通过构造程序骰子(作为两组静态切片的集合差)来扩展上述方法，以进一步减少故障可能位置的搜索域[235]。虽然基于静态切片的技术已经被实验评估并证实在故障定位中是有用的[207]，但有一个问题是，处理指针变量可以使数据流分析效率低下，因为需要存储指针变量取消引用引入的大量数据事实。等价分析，它识别一个过程访问的各个内存位置之间的等价关系，用于在指针变量存在下提高数据流分析的效率[220]。两个等效的内存位置在一个过程中共享相同的数据事实集。因此，数据流分析只需要计算具有代表性的内存位置的信息，而其他等效位置的数据流可以从具有代表性的位置获取。静态切片也应用 于二进制可执行文件[192]和类型检查器[343]中的故障定位。

静态切片的一个缺点是，给定语句中给定变量的切片包含所有可能影响语句中该变量值的可执行状态。因此，它可能产生一个骰子与certain语句，不应该包括。这是因为我们不能通过静态分析来预测一些运行时值。为了将这些额外的语句排除在骰子(以及切片)中，我们需要使用动态切片[20]、[202]而不是静态切片，因为前者可以识别确实影响在特定位置观察到的特定值的语句，而不可能影响与后者一样的值。[18]、[24]、[28]、[96]、[104]、[188]、[192]、[201]、[219]、[227]、[237]、[257]、[277]、[297]、[334]、[356]、[378]、[379]，在程序调试中使用动态切片概念的[406]、[407]、[410]已经被报道。在[379]中，Wotawa将动态切片与基于模型的诊断相结合，实现了更有效的故障定位使用给定的测试套件对程序，收集动态切片发现的错误variables。构造了点集，其中包含来自每个动态切片的至少一个语句。语句错误的概率是根据覆盖该语句的命中集数计算的。张等人[407]提出了多点动态切片技术，它与三种技术的切片相交：后向动态切片(BwS)、前向动态切片(FwS)和双向动态切片(BiS)。BWS上限一处理影响故障变量输出值的任何已执行语句，而FwS是根据失败和成功测试用例之间的最小输入差计算的，隔离了触发故障的输入 部分。在执行失败的测试用例时，BiS翻转某些谓词的值，以便程序生成正确的输出。钱和徐[297]提出了一种面向场景的切片技术。识别用户指定的场景作为额外的切片参数，以及所有相关的程序部分都位于给定执行场景下的特殊计算。序部分都位于给定的EXECU场景下。实现面向场景的切片技术有三个关键步骤：场景输入、场景相代码的识别以及面向场景的切片的收集。

基于动态切片的技术的一个限制是它们不能捕获执行遗漏错误，这可能导致程序中某些关键语句的执行被省略，从而导致失败[411]。Gyimothy等人[142]建议使用相关切片来定位造成执行遗漏错误的错误语句。给定一个失败的执行，相关的切片首先构造一个动态依赖图，就像经典的动态切片一样。然后对具有潜在依赖边的动态依赖图进行放大，并通过对增广动态依赖图的不正确输出的传递闭包来提出相关的切片。然而，程序语句之间不正确的依赖关系可能包括在内以产生过大的相关切片。为了解决这个问题，张等人[411]介绍了隐式依赖的概念，其中依赖可以通过预切换获得。Weeratunge等人也使用了类似的想法[358]来确定并发程序中遗漏错误的根本原因，其中双重切片，组合使用动态切片和跟踪差异。

静态和动态切片的另一种方法是使用基于数据流测试的执行切片来定位程序错误[21]，其中针对给定测试用例的执行切片包含由此测试执行的语句集。选择执行切片而不是静态切片的原因是，静态切片侧重于寻找可能会对任何输入感兴趣的变量产生影响的状态，而不是由特定输入执行的语句。这意味着静态切片不使用显示故障的输入值，并违反了调试中的一个非常重要的概念，即建议程序员在失败的测试用例下分析程序行为，而不是在通用测试用例下分析程序行为。收集动态切片可能会花费过多的时间和文件空间，尽管不同的算法[51]、[204]、[408]、[409]已提议解决这些问题。相反，如果我们从测试的执行中收集代码覆盖数据，则相对容易为给定的测试用例构造执行切片。已经开发并在实践中使用了不同的基于执行片的调试工具，如Telcordia(以前的Bellcore)[22]、[427] 和Avaya的eXVantage[372]。Agrawal 等人，[21]应用通过检查一个失败和一个成功测试的执行骰子来定位程序错误，从而将执行切片到错误定位。Jones等人[186]、[187]和Wong等人[375]利用基于以下观察结果的多个成功和失败的测试来扩展这项研究：

• 执行一段代码的测试越成功，代码包含错误的可能就越小
• 对于执行一段代码的

  剩余内容已隐藏，支付完成后下载完整资料

  ---

  资料编号：[606737]，资料为PDF文档或Word文档，PDF文档可免费转换为Word