软件故障定位综述外文翻译资料

A Survey on Software Fault Localization

Abstract

Software fault localization, the act of identifying the locations of faults in a program, is widely recognized to be one of the most tedious, time consuming, and expensive – yet equally critical – activities in program debugging. Due to the increasing scale and complexity of software today, manually locating faults when failures occur is rapidly becoming infeasible, and consequently, there is a strong demand for techniques that can guide software developers to the locations of faults in a program with minimal human intervention. This demand in turn has fueled the proposal and development of a broad spectrum of fault localization techniques, each of which aims to streamline the fault localization process and make it more effective by attacking the problem in a unique way. In this article, we catalog and provide a comprehensive overview of such techniques and discuss key issues and concerns that are pertinent to software fault localization as a whole.

Index Terms—Software fault localization, program debugging, software testing, execution trace, suspicious code, survey

1 INTRODUCTION

Software is fundamental to our lives today, and with its ever-increasing usage and adoption, its influence is practically ubiquitous. In fact, at present, software is not just employed in, but is critical to, many security and safety-critical systems in industries such as medicine, aeronautics, and nuclear energy. Not surprisingly, this trend has been accompanied by a drastic increase in the scale and complexity of software. Unfortunately, this has also resulted in more software bugs, which often lead to execution failures with huge losses [260], [275], [365]. Furthermore, software faults in safety-critical systems have significant ramifications, including not only financial loss, but also potential loss of life, which is an alarming prospect [368]. A 2002 report from the National Institute of Standards and Technology (NIST) [304] indicated that software errors are estimated to cost the U.S. economy $59.5 billion annually (0.6 percent of the GDP); the cost has undoubtedly grown since then. Over half the cost of fixing or responding to these bugs is passed on to software users, while software developers and vendors absorb the rest.

Even when faults in software are discovered due to erroneous behavior or some other manifestation of the fault(s),finding and fixing them is an entirely different matter. Fault localization, which focuses on the former, i.e., identifying the locations of faults, has historically been a manual task that has been recognized to be time consuming and tedious as well as prohibitively expensive [347], given the size and complexity of large-scale software systems today. Further-more, manual fault localization relies heavily on the software developerrsquo;s experience, judgment, and intuition to identify and prioritize code that is likely to be faulty. These limitations have led to a surge of interest in developing techniques that can partially or fully automate the localization of faults in software while reducing human input. Though some techniques are similar and some very different (in terms of the type of data consumed, the program components focused on, comparative effectiveness and efficiency, etc.), they each try to attack the problem of fault localization from a unique perspective, and typically offer both advantages and disadvantages relative to one another. With many techniques already in existence and others continually being proposed, as well as with advances being made both from a theoretical and practical perspective, it is important to catalog and overview current techniques in fault localization in order to offer a comprehensive resource for those already in the area as well as those interested in making contributions to it.

In order to provide a complete survey covering most of the publications related to software fault localization since the late 1970s, we created a publication repository that includes 331 papers published from 1977 to November 2014. We also searched for Mastersrsquo; and Ph.D. theses closely related to software fault localization, which are listed in Table 1.

All papers in our repository2 are sorted by year, and the result is displayed in Fig. 1. As shown in the figure, the number of publications grew rapidly after 2001, indicating that more and more researchers began to devote themselves to the area of software fault localization over the last 10 years.

Also, as per our repository, Fig. 2 gives the number of publications related to software fault localization that have appeared in top quality and leading journals and conferences that focus on Software Engineering–IEEE Transactions on Software Engineering, ACM Transactions on Software Engineering and Methodology, International Conference on Software Engineering, ACM International Symposium on Foundations of Software Engineering, and ACM International Conference on Automated Software Engineering–from 2001 to November 2014. This trend again supports the claim that software fault localization is not just an important but also a popular research topic and has been discussed very heavily in top quality software engineering journals and conferences over the last ten years.

There is thus a rich collection of literature on various techniques that aim to facilitate fault localization and make it more effective. Despite the fact that these techniques share similar goals, they can be quite different from one another and often stem from ideas that originate from several different disciplines. While we aim to comprehensively cover as many fault localization techniques as possible, no article, regardless of breadth or depth, can cover all of them. In this survey, our primary focus is on the techniques for locating Bohrbugs [139]. Those for diagnosing Mande

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

软件故障定位综述

摘要

软件故障定位，即识别程序中故障位置的这一行为，被广泛认为是程序调试中最繁琐、最耗时、最昂贵但同样重要的活动之一。由于当今软件的规模和复杂性不断增加，当出现故障时手动定位故障变得越来越不可行，因此，非常需要能够在最少人工干预的情况下将软件开发人员引导到程序中的故障位置的技术。这种需求反过来又推动了各种故障定位技术的提出和发展，每种技术都旨在简化故障定位过程，并通过以独特的方式解决问题来提高效率。在本文中，我们对这些技术进行了分类和全面的概述，并讨论了与软件故障定位相关的关键问题和关注点。

索引词汇—软件故障定位、程序调试、软件测试、执行跟踪、可疑代码、调查

1导言

软件是我们如今生活的基础，随着软件的使用和采用不断增加，它的影响几乎无处不在。事实上，目前，软件不仅仅应用于医疗、航空和核能等行业的许多防护程序和安全关键系统，而且对这些系统至关重要。这一趋势伴随着软件规模和复杂性的急剧增加并不令人奇怪。但不幸的是，这也导致了更多的软件错误，这些错误通常会导致执行失败并且造成巨大的损失 [260], [275], [365]。此外，安全关键系统中的软件故障具有重大的影响，不仅包括经济损失，还包括潜在的生命损失，这是一个令人担忧的前景[368]。国家标准和技术研究所(NIST)2002年的一份报告[304]指出，软件错误这一问题预计每年给美国经济造成595亿美元的损失(占国内生产总值的0.6%)；从那以后，无疑增加了许多的成本。有超过半数修复或响应这些bug的成本转嫁给了软件用户，而软件开发人员和供应商则承担了其余的成本。

即使软件中的故障是由于错误行为或故障的其他表现形式而被发现的，发现它们和修复它们也是完全不同的事情。故障定位侧重于前者，即识别故障的位置，而且在历史上一直由人工完成，鉴于当今大规模软件系统的复杂性，它被认为既耗时又乏味，而且极其昂贵[347]。此外，手动故障定位在很大程度上依赖于软件开发人员的经验、判断和直觉来识别和优先考虑可能有故障的代码。这些限制导致了人们对开发能够部分自动化或完全自动化软件故障定位并同时减少人工输入这些技术的兴趣大大提高。虽然有些技术相似，有些则非常不同(就所使用的数据类型、所关注的程序组件、相对有效性和效率等而言)，它们都试图从一个独特的角度来解决故障定位的问题，并且通常都提供了两者间的优点和缺点。许多已经存在的技术和其他不断被提出的技术，从理论和实践的角度来看都取得了进步，因此对当前的故障定位技术进行分类和概述非常重要，以便为在该领域工作的人员以及想加入该领域的人员提供全面的资源。

为了提供涵盖自20世纪70年代末以来与软件故障定位相关的大多数出版物的完整调查，我们创建了一个出版物存储库，其中包括从1977年到2014年11月发表的331篇论文。我们还搜索了与软件故障定位密切相关的硕士和博士论文，如表1所示。

我们的知识库2中的所有论文都是按年份排序的，结果如图1所示。如图所示，2001年后，出版物的数量迅速增长，这表明在过去的10年里有越来越多的研究人员开始致力于这一领域。

此外，根据我们的知识库，图2给出了2001年至2014年11月期间，出现在软件工程的高质量领先期刊和会议上的与软件故障定位相关的出版物包含——IEEE软件工程交易会、ACM软件工程和方法交易会、国际软件工程会议、ACM软件工程基础国际研讨会和ACM自动化软件工程国际会议。这一趋势再次证明了软件故障定位不仅是一个重要的而且是一个流行的研究课题，并且过去十年中在高质量的软件工程期刊和会议中被大量讨论。

因此，有大量关于各种旨在促进故障定位并使其更加有效这一技术的文献。尽管这些技术有着相似的目标，但它们之间可能会有很大的不同，并且通常是源于几门不同学科的思想。虽然我们的目标是全面覆盖尽可能多的故障定位技术，但无论从广度或深度上，没有一篇文章能够覆盖所有这些技术。在这项调查中，我们的主要的重点技术是定位 Bohrbugs [139]。那些判断Mandelbugs的 [139]如性能缺陷、内存泄漏、软件膨胀和安全漏洞不包括在范围内。此外，由于篇幅限制，我们将技术分成适当的类别进行集中讨论，强调最重要的特征，并将这些技术的其他细节留给他们各自发表的论文。针对特定应用领域的技术尤其如此，例如并发错误和电子表格的故障定位。对于这些，我们提供一个评论，帮助读者大致了解。

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

• 失败是指服务偏离了其正确的行为。
• 错误是系统中可能导致故障的一种情况。
• 故障是错误的潜在原因，也称为bug。

本文的其余部分按以下方式组织:我们在第2节中首先描述传统的和直观的故障定位技术，然后在第3节中介绍更高级和更复杂的技术。在第4节中，我们列出了在不同案例研究中使用的一些流行的主题项目，并讨论了这些项目是如何发展的。第5节描述了评估故障定位技术有效性的不同评估指标，随后第6节讨论了故障定位工具。最后，第7节和第8节分别介绍了关键性的地方和结论。

2传统故障定位技术

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

2.1程序记录

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

2.2断言

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

2.3断点

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

2.4特征分析

概要分析是对执行速度和内存使用等指标的运行时间分析，通常针对程序优化。但是也可以用于调试活动，例如:

• 检测不同功能的意外执行频率(如[43])；
• 识别内存漏洞或性能异常差的代码(例如[150])；
• 检查惰性编译的副作用(例如[313])

使用概要分析进行程序调试的工具包括GNU的gprof [120]和Eclipse插件TPTP [108]。

3高级故障定位技术

随着当今软件系统的巨大规模和范围，传统的故障定位技术在隔离故障的根本原因方面效果并不明显。因此，最近出现了许多先进的故障定位技术，使用了因果关系[215]，[288]的思想，这与哲学理论有关，目的是描述事件/原因(在我们的情况下是程序错误)和现象/结果(在我们的情况下是执行失败)之间的关系。有不同的因果关系模型[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年首次提出静态切片以来，已经发表了数百篇关于这个主题的论文[52]，[344]，[394]。

静态切片[360]的一个重要应用是在程序员查找程序中的bug时减少搜索域。其实这是基于这样的一个想法，如果一个测试用例由于一个语句中不正确的变量值而失败，那么缺陷应该在与该变量-语句相关联的静态切片中找到，容许我们将搜索限制在切片中，而不是查看整个程序。Lyle和Weiser通过构造一个程序块(作为两组静态切片的集合差)扩展了上述方法，以进一步缩小故障位置的搜索范围[235]。尽管基于静态切片的技术已经被实验方法评估与证实在故障定位中有用[207]，但有一个问题是处理指针变量会使数据流分析效率低下，因为需要存储由指针变量的解引用引入的大量数据。等价分析，识别由过程访问的各种存储单元之间的等价关系，用于在存在指针变量的情况下提高数据流分析的效率[220]。 在一个过程中，两个等价的内存位置共享相同的数据集。因此，数据流分析只需要计算代表的信息 ，存储器位置和其他等效位置的数据流可以从代表性位置获得。静态切片也适用于二进制文件中的故障定位可执行文件[192]和类型检查器[343]。

静态切片的一个缺点是，给定语句中给定变量的切片包含所有可能影响该语句中该变量值的可执行语句。因此，它可能会生成一个块，其中包含了不应包括在内的某些语句。这是因为我们无法通过静态分析预测一些运行时值。为了从块(以及切片)中排除这些额外的语句，我们需要使用动态切片[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

将动态切片与基于模型的特征相结合，实现更有效的故障定位。针对程序使用给定的测试套件，收集发现了错误变量的动态切片。构造了命中集，它包含来自每个动态切片的至少一个语句。语句出错的概率是根据覆盖该语句的命中集的数量来计算的。Zhang以及其他人[407]提出了多点动态切片技术，它与三种技术的切片相交:反向动态切片(BwS)、正向动态切片(FwS)和双向动态切片(BiS)。BwS捕获任何影响错误变量输出值的已执行语句，而FwS是根据测试失败和成功用例之间的最小输入差异计算的，隔离了触发失败的输入部分。BiS在执行失败的测试用例时翻转某些词的值，以便程序生成正确的输出。Qian和Xu[297]提出了一种面向场景的程序切片技术。用户指定的场景被标识为额外的切片参数，与特殊计算相关的所有程序部分都位于给定的执行场景下。实现面向场景的切片技术有三个关键步骤:场景输入、场景相关代码的识别，最后是面向场景切片的收集。

基于动态切片的技术的一个限制是，它们不能捕获执行遗漏错误，这可能导致程序中某些关键语句的执行被省略，从而导致失败[411]。Gyimothy等人[142]提出使用相关切片来定位导致执行遗漏错误的错误语句。给定一个失败的执行，相关的切片首先以与经典动态切片相同的方式构建一个动态依赖图。然后用潜在依赖边对动态依赖图进行扩充，并通过对扩充后的动态依赖图上的错误输出进行传递闭包来计算相关切片。然而，程序语句之间不正确的依赖关系可能会产生过大的相关切片。为了解决这个问题，Zhang等人[411]引入了隐式依赖的概念，其中依赖可以通过预描述切换来获得。Weeratunge等人[358]使用了类似的思想来确定并发程序中遗漏错误的根本原因，其中使用了动态切片和跟踪差分相结合的双重切片。

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

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

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