英语原文共 34 页，剩余内容已隐藏，支付完成后下载完整资料
软件故障定位研究综述
摘要 - 软件故障定位是一种识别程序故障位置的行为，被广泛认为是程序调试中最繁琐，最耗时，最昂贵但同样最重要的活动之一。 由于当今软件的规模和复杂性的增加，在发生故障时手动定位故障正在变得不可行，因此，强烈需要能够以最少的人为干预将软件开发者引导到程序中的故障位置的技术。 反过来，这种需求推动了广泛的故障定位技术的提出和发展，每种技术旨在简化故障定位过程，并通过以独特方式攻击问题使其更有效。在本文中，我们对这些技术进行编目并提供全面的概述，并讨论与整个软件故障定位相关的关键问题和关注点。
1.简介
软件是我们今天生活的基础，随着使用和采用的不断增加，它的影响几乎无处不在。事实上，目前，软件不仅仅用于医疗，航空和核能等行业，而且在许多安全和安全关键系统中也至关重要。毫无疑问，这种趋势伴随着软件规模和复杂性的急剧增加。不幸的是，这也导致了更多的软件错误，这样会经常导致执行失败并造成巨大损失。此外，安全关键系统中的软件故障具明有显的贬值，不仅包括财务损失，还包括潜在的生命损失，这是一个令人震惊的消息。美国国家标准与技术研究院（NIST）2002年的一份报告表明，估计软件错误每年使美国经济损失595亿美元（占GDP的0.6％）;从那时起，成本无疑增长了。固定或响应这些错误的成本的一半以上传递给软件用户，而软件开发商和供应商则吸收其余的成本。
即使由于错误行为或故障的某些其他表现而发现软件中的故障，但发现和修复它们也是完全不同的事情。故障局部化，侧重于前者，即识别故障的位置，历史上一直是一项手动任务，在今天已被认为是耗时且繁琐的，并且考虑到大规模的复杂性而过于昂贵的软件系统。此外，手动故障定位在很大程度上依赖于软件开发人员的经验，用判断和直觉来识别可能存在错误的代码并确定其优先级。这些限制导致人们对开发技术的兴趣激增，这些技术可以部分或完全自动化软件中故障的定位，同时减少人为输入。虽然有些技术是相似的，但有些非常不同（在所消耗的数据类型，程序组件的重点，比较效率和效率等方面），它们都试图从独特的角度来解决故障定位的问题，通常相对于彼此提供优点和缺点。由于已经存在许多技术并且不断提出其他技术，并且从理论和实践角度都取得了进展，因此对故障定位中的当前技术进行编目和概述是非常重要的，以便为该地区以及有兴趣为此做出贡献的人和已经存在的技术提供全面的资源。
2.传统的故障定位技术
本节介绍传统和直观的故障定位技术，包括程序记录，断言，断点和配置
2.1程序记录
用于生成程序记录的语句（例如print）通常以ad-hoc方式插入代码中，用来监视变量值和其他程序状态信息。 当检测到异常程序行为时，开发人员会根据保存的日志文件或打印的运行时信息检查的程序日志，以此诊断故障出现的根本原因。
2.2断言
断言是添加到程序中的约束，在程序的正确操作期间必须为真。 开发人员在程序代码中将这些断言指定为条件语句，如果它们的计算结果为false，则终止执行。 因此，它们可用于在运行时检测错误的程序行为。
2.3断点
断点是用来在执行到达指定点时暂停程序，并允许用户检查当前状态。 触发断点后，用户可以修改变量值或继续执行以观察错误的进展。 数据断点可以配置为在特定表达式的值发生变化时触发，例如变量值的组合。 条件断点仅在满足用户指定的谓词时才暂停执行。 早期的研究是使用这种方法来帮助开发人员在程序在符号调试器的控制下执行时找到错误。 更高级的调试工具也采用了相同的方法，例如GNU GDB 和Microsoft Visual Studio Debugger。
2.4配置
配置是对度量的运行时分析，例如执行速度和内存使用，通常针对程序优化。 但是，它也可以用于调试活动，例如：
检测不同功能的意外执行频率;
识别内存泄漏或执行意外不良的代码;
检查惰性评估的副作用。
使用配置进行程序调试的工具包括GNU的gprof 和Eclipse插件TPTP。
3.先进的故障定位技术
随着当今软件系统的庞大规模和规模，传统的故障定位技术可以有效地解决故障的根本原因。 因此，许多先进的故障定位技术最近出现了因果关系的概念，这与哲学理论有关，其目的是描述事件/原因和现象/效果（执行失败的情况）之间的关系 。不同的因果关系模型，如基于反事实，概率或统计的，以及因果微积分模型等。 其中，概率因果关系模型是故障定位中最广泛使用的，用于识别不负责任的执行失败的可疑代码。
在本次调查中，我们将故障定位技术分为八类，包括基于切片，基于频谱，基于统计，基于程序状态，基于机器学习，基于数据挖掘，基于模型和各种技术。虽然已经报道了许多评估特定故障定位技术有效性的研究，但是，它们都没有提供有关所有这些技术的全面讨论。
3.1基于切片的技术
程序切片是一种通过删除不相关的部分将程序抽象为简化形式的技术，使得结果切片在某些规范方面仍然与原始程序的行为相同。 自Weiser于1979年首次提出静态切片以来，已发表了数百篇有关该主题的论文。
静态切片的一个重要应用是减少搜索域，同时程序员在程序中找到错误。这是基于这样的想法：如果测试用例由于语句中的变量值不正确而失败，那么应该在与该变量语句对关联的静态切片中找到缺陷，这样我们就可以将搜索结果限制在切片中而不是看整个计划。 Lyle和Weiser通过构造程序骰子（作为两组静态切片的集合差异）来扩展上述方法，以进一步减少故障的可能位置的搜索域。虽然静态基于切片的技术已通过实验评估并证实在故障定位中有用，但一个问题是处理指针变量会使数据流分析效率低下，因为指针变量的解引用所引入的大量数据事实需要存储。等价分析用于识别程序访问的各种存储单元之间的等价关系，用于提高指针变量存在时数据流分析的效率。两个等效的存储器位置在过程中共享相同的数据事实集。因此，数据流分析仅需要计算代表性存储器位置的信息，并且可以从代表性位置获得其他等效位置的数据流。静态切片也适用于二进制可执行文件和类型检查器中的故障定位。
静态切片的缺点是语句中给定变量的切片包含可能影响该语句中此变量值的所有可执行语句。因此，它可能会生成一些骰子，其中有一些不应该包含的语句。这是因为我们无法通过静态分析预测某些运行时值。为了从骰子（以及切片）中排除这些额外的陈述，我们需要使用动态切片而不是静态化，因为这可能会影响在特定位置观察到的特定值，而不是影响这样的特定值。价值与后者相同。比方一些研究在程序调试中使用动态切片概念，已经被报道了。Wotawa将动态切片与基于模型的诊断相结合，以实现更有效的故障定位。对程序使用给定的测试套件，收集发现的错误变量的动态切片。打击集合，其中包含至少一个声明的动态片段。语句出错的概率是根据覆盖该语句的命中集数计算的。 提出了多点动态切片技术，其与三种技术的切片相交：后向动态切片（BwS），前向动态切片（FwS）和双向动态切片（BiS）。 BwS捕获任何影响错误变量输出值的执行语句，而FwS则根据失败和成功测试用例之间的最小输入差异计算，隔离触发失败的输入部分。 BiS在执行失败的测试用例时会触发某些谓词的值，以便程序生成正确的输出。 Qian和Xu 提出了一种面向场景的程序化技术。用户指定的场景作为额外的切片参数，所有与特殊计算相关的程序部分都位于给定的执行场景下。实现面向场景的切片技术有三个关键步骤：场景输入，场景相关代码的识别，以及最终收集面向场景的切片。
基于动态切片的技术的一个限制是它们无法捕获执行遗漏错误，这可能导致程序中某些关键语句的执行被省略，从而导致失败。 Gyimothy等人建议使用相关切片来定位导致执行遗漏错误的错误陈述。鉴于一个错误的执行，与传统的动态切片相同的方式，首先构造动态依赖图。然后，它利用潜在的依赖边缘来增强动态依赖图，并且通过对增强的动态依赖图的不正确输出的敏感性条件来计算相关切片。但是，可以包括程序语句之间的不正确的依赖性用来产生超大的相关切片。为了解决这个问题，Gyimothy等人引入了隐式依赖的概念，其中依赖性可以通过预测切换获得。 Weeratunge etal使用了类似的想法来识别并发程序中的同时发生错误，其中使用了双切片，动态化和跟踪的组合。
静态和动态切片的另一种方法是使用基于数据流测试的执行切片来定位程序错误，其中关于给定测试用例的执行切片包含由该测试执行的语句集。在静态切片上选择执行切片的原因是静态切片侧重于发现可能对任何输入感兴趣的变量产生影响的语句，而不是由特定输入执行的语句。这意味着静态切片不会使用显示错误的输入值，并且违反调试中的一个非常重要的概念，这表明程序员在测试用例下分析程序行为失败而不是在通用测试用例下。收集动态切片可能会消耗过多的时间和文件空间，即使已经提出了不同的算法来解决这些问题。相反，如果我们从测试执行中收集代码覆盖率数据，则为给定的测试用例构造执行片段相对容易。已经开发并使用了不同的基于执行切片的调试工具，例如Telcordia的xSuds（以前的Bellcore）和Avaya的eXVantage。Agrawal等人通过检查一个失败的和一个成功的测试的执行骰子来定位程序错误，将执行片应用于故障定位。琼斯和Wong等人根据以下观察结果，通过使用多次成功和失败的测试来扩展该研究：
执行一段代码的测试越成功，代码包含错误的可能性就越小。
对于执行一段代码的给定错误，测试失败的次数越多，它就越有可能包含此错误。
我们使用以下示例来演示静态，动态和执行切片之间的差异。 使用表2第2列中的代码作为参考。 假设它在s7有一个错误。 输出变量product的静态切片包含所有可能影响s1，s2，s4，s5，s7，s8，s10和s13值的语句。产品的动态切片仅包含影响产品价值的语句，该测试用例包括s1，s2，s5，s7和s13，关于给定测试用例的执行片包含由该测试执行的所有语句。 因此，测试用例的执行切片a = 2由s1，s2，s3，s4，s5，s6，s7，s12，s13组成。
上述基于切片的技术的一个问题是该故障可能不在骰子中。即使骰子中存在错误，仍可能需要检查太多代码。为了克服这个问题，提出了基于块间数据依赖性的增强和重新定义方法。前者包括搜索域中的附加代码，用于基于其与当前正在检查的代码的块间数据依赖性进行检查，而后者使用其他成功测试的执行切片从搜索域中排除较少的可疑代码。另外，切片是有问题的，因为它们总是很长且难以理解。所以提出了使用障碍的概念，以便为较小的程序切片和更好的可理解性提供过滤方法。一位作者提出了薄切片，以便仅找到有助于计算和复制特定变量值的生成器语句，解释生成器语句影响特定变量值的原因的语句从精简片中排除。
3.2基于频谱的节目技术
在第3节开头的讨论之后，我们想强调许多基于频谱的技术受到基于概率和统计的因果关系模型的启发。 有了这种理解，我们现在解释这些技术的细节。
频谱从某些角度详细描述了程序的执行信息，例如条件分支的执行信息或无循环的过程内路径。 它可用于跟踪程序行为。Collofello和Cousins的早期研究表明，这种光谱可用于软件故障定位。当执行失败时，可以使用此类信息来识别导致失败的可疑代码。代码覆盖率或可执行语句命中频谱（ESHS）指示在执行期间已涵盖所测试的程序的哪些部分。有了这些信息，就可以确定哪些组件涉及故障，从而缩小了对执行失败的故障组件的搜索范围。
3.3基于统计的技术
有人提出了一种统计调试技术（Liblit05），它可以将程序中的错误与特定点上的检测谓词隔离开来。 对于每个谓词P，Liblit05计算P为真意味着失败，失败（P）以及P的执行意味着失败的概率.其余谓词根据其重要性分数进行优先级排序，这表明谓词和程序错误之间的关系。 应检查具有较高分数的谓词st。Chilimbi等建议用路径pro替换谓词可以提高Liblit05的有效性，路径程序在执行期间收集，并通过反馈报告在多个测试用例的执行过程中进行聚合。 计算每条路径的重要性分数，并选择最高结果并将其显示为潜在的根本原因。
计算陈述的可疑性。 为每个语句构造交叉表，其中包含两个垂直类别（覆盖/未覆盖）和两个水平类别（成功执行/执行失败）。 假设检验用于提供执行结果与每个语句的覆盖范围之间的依赖/独立性的引用。 每个陈述的确切可疑性取决于其覆盖范围与执行结果之间的关联程度。
Crosstab，SOBER和Liblit05之间的主要区别在于交叉表通常可用于对可疑程序元素（即语句，谓词，函数/方法等）进行排名，而后两者仅对可疑谓词进行故障定位排序。对于Liblit05和SOBER，前k个谓词的相应语句被视为要检查以查找错误的初始集。正如Jones和Harrold建议的那样，Liblit05没有办法量化所有陈述的排名。定义了谓词的顺序，但该方法没有详细说明如何对与谓词之外的任何错误相关的语句进行排序。对于SOBER，如果错误不在初始语句集中，则必须通过在相应的程序依赖图上执行广度优先搜索来包含其他语句，这可能是耗时的。但是，交叉表不需要进行此类搜索，因为程序的所有语句都是根据其可疑性进行排名的。报告的结果表明，Crosstab在定位西门子套件中的错误方面几乎总是比Liblit05和SOBER更有效。
3.4基于程序状态的技术
程序状态由程序执行期间特定点的变量及其值组成，这可以作为查找程序错误的良好指标。在软件故障定位中使用程序状态的一种方法是通过相对调试，其中可
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[439958]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
