用于软件故障定位的关键分片*
关键词：测试、调试、故障、故障、突变分析、临界分片、动态程序分片、静态程序分片、故障定位
制定有效的调试策略以保证软件的可靠性是很重要的。通过分析有经验的程序员所使用的调试过程，我们发现有四项不同的任务被持续执行。(1）确定参与程序故障的语句（2）选择可能包含故障的可疑语句（3）对可疑的故障（变量和locations）做出假设（4）将程序状态恢复到特定的状态以进行验证。这项研究重点支持第二项任务，即减少故障的搜索域，我们称之为故障定位。我们探索了一种新的方法来加强基于动态程序切片和基于突变测试的故障定位过程。在这种新方法中，我们开发了'关键切片'技术，使调试器能够突出可疑的语句，从而将搜索域限制在一个小区域内。临界分片技术是基于突变的测试方法的'语句删除'操作。我们研究了临界分片的特性，如临界分片、动态程序分片和静态程序分片之间的关系；构建临界分片的成本；以及临界分片的有效性。实验结果支持我们的猜想，即使用临界切片进行故障定位的有效性和可行性。
本文解释了我们的技术并总结了我们的一些发现。由此，我们得出结论，配备了我们提出的故障定位方法的调试器有助于复杂软件的调试。
（一）引言
在软件生命周期中，测试和调试阶段花费了大量的时间和精力：一些较早的研究表明，这一成本占整个软件开发工作的50%以上。在IEEE标准中，错误被定义为程序员或设计者的不恰当行为。故障或错误是程序编码过程中错误的表现和结果。当故障导致程序在执行某项输入时获得意外的结果时，就会发生程序故障。目前调试工具中使用的许多故障定位技术（例如设置断点）是在20世纪60年代开发的，而且变化不大。用户必须自己发现用于调试的有用信息。调试过程中涉及的两个主要步骤是定位和纠正故障。以前的研究发现，定位故障是调试中最困难和重要的任务。我们研究的主要目标是找到一种有效的方法来完成定位故障的任务。通过分析有经验的程序员所使用的调试过程，我们发现有四项不同的任务被持续执行。（1）确定哪些语句涉及程序故障（2）选择可能含有故障的可疑语句（3）对可疑故障（变量和位置）做出假设（4）将程序状态恢复到特定的语句上进行验证。如果这四项任务都是在调试工具的直接帮助下完成的，那么调试工作就会变得更加容易。我们的研究集中在第二项任务上，即减少故障的搜索域，被称为故障定位。我们相信，对这项任务的改进方法可以增强调试过程，减少人与人之间的互动时间。
在这方面，我们的方法是以一种独特的方式结合两种著名的技术，即测试和程序切片。我们首先观察到，调整测试程序的输入，使该程序表现出故障。调试试图在测试过程中发现故障后定位并修复故障（bug）或使用。虽然测试和调试是密切相关的，但现有的调试技术都没有尝试与测试阶段的结果对接。我们的方法已经建立了这样一种关系。
程序切片是一种强大而有用的方法，可以帮助理解实际的程序行为。动态程序切片技术可以确定哪些语句实际上影响了程序的故障，从而减少故障的搜索域。虽然不能保证动态切片总是包含故障（例如，缺失的语句或规范故障），但在调试中，找出实际影响程序故障的语句是一种合理的策略。
通过分析动态切片中可疑语句的语义和变量的值，我们可能会发现有价值的调试信息。然而，这并不是唯一可能的有用信息来源。我们可以从测试阶段获得一些信息（例如基于故障的测试方法中的测试用例和故障分析），这些信息在调试过程中应该是有帮助的。
我们加强故障定位过程的方法是基于动态程序切片和基于突变的测试。在本文中，我们描述了从最简单的突变算子中衍生出来的方法--关键切片法'语句删除'。实验结果表明，'关键分片'是一种很有效的方法，大大减少故障的搜索域。对于我们研究中的程序，从整个程序中平均减少了64%左右的误差。此外，大约80%的临界片仍然包含导致故障的错误语句，因此不会误导用户进行进一步的调试。
我们开发了一系列启发式方法来减少搜索域，这些方法基于测试案例的分类和动态程序切片技术，不需要进一步测试信息的帮助。我们对这个启发式系列的初步研究结果表明，减少的搜索范围平均比整个程序至少减少43%。
我们在调试中使用的动态程序切片的形式是由Agrawal等人在[4，2，6]中正式定义的。我们在这里提出一个非正式的定义，如[3]中提出的：构建动态程序片有两个主要部分：动态数据片和动态控制片。对于一个给定的表达式、location和测试用例来说，动态数据片是所有赋值的集合，这些赋值的计算已经传播到给定位置上的给定表达式的当前值。这是由在给定位置的表达式中使用的变量的动态到达定义的转折闭合完成的。属于这个闭合的所有赋值的集合构成了动态的静态程序切片是由Weiser[39,40]提出的。读者可参考[37]了解程序切片的演变，包括动态程序切片。程序突变已经被研究了十多年。它在文献中得到了很好的记载（例如，[13,12,11,16]），并在第2节中进行了简要的描述。另一方面，对于一个给定的位置和测试用例，动态控制片是执行测试用例后包围给定位置的所有谓词的集合。这是由从给定位置开始的包围谓词的反义闭合完成的。属于这个闭合的所有谓词的集合构成了动态控制片断。因此，关于一个给定的变量、位置和测试用例的动态程序片是关于其组成的动态数据和控制片中所有表达式和位置的所有数据和控制片。
总之，一个动态程序切片，DPS(P, v, l, t)，由给定程序P中的所有语句组成，当P针对给定的测试用例t执行时，这些语句会实际影响位置l的变量v的当前值。另外，由Weiser[39,40]提出的静态程序切片被称为SPS。一个静态程序切片，SPS(P, v, l)，包含P的可执行语句，这些语句可能会影响选定的变量位置对（v, l）的值。
在使用程序切片进行故障定位时，我们希望在选定的程序切片中处理少量的相关语句，这些语句包含有故障的语句。静态片（SPS）包含可能与故障无关的语句。DPS方法中的动态片断由实际影响（修改）某个输入的变量值的语句组成。然而，在某些情况下，计算DPS可能很低效。一个更简单的方法是对代码进行简单的检测，并得出执行的静态程序分片（ESPS）。我们将其定义为选定的静态切片SPS(P, u, l)中的语句集。当我们针对一个选定的测试用例/行使P时，执行一个已执行的静态程序片被表示为ESPS(P, v, l, t)。计算已执行的静态片断的成本通常比动态片断的成本低很多。然后，我们使用这些ESP片断作为故障定位的搜索空间。
本文的其余部分组织如下。在第二节中，我们定义了'关键切片'，并分析了'关键切片'的特性，如'关键切片'、'动态程序切片'和'执行的静态程序切片'之间的关系；构建'关键切片'的成本；以及'关键切片'的有效性。我们进行了一个小型实验，以探索使用'关键切片'进行调试的有效性和可行性。实验的结果在第3节中描述。最后，我们在第4节中描述了在我们的故障定位技术支持下的新的调试范式。还讨论了这项研究的未来方向。这项研究的主要贡献是一个新的调试范式，通过减少搜索范围来加强故障定位的过程。
我们的方法是基于动态程序切片和基于突变的测试中获得的信息。尽管它不能保证故障总能在缩小的搜索域中被精确定位，但包含导致故障发现的信息的缩小的搜索空间仍然对用户的调试有帮助。
图1：C语言的语句删除突变体的例子：（a）被测试的给定程序；（b）Ml；（c）M2；（d）M3；和（e）M4。
（二）临界切片
在测试阶段，软件测试人员创建测试用例，以满足选定的测试方法的标准（例如，状态指导覆盖）。然后，这些测试用例针对一个给定的程序被执行。如果程序发生故障，测试用例（被称为故障揭示测试用例）将显示故障的存在，并将在以后用于调试。然而，我们感兴趣的不仅是相关的故障揭示和非故障揭示的测试用例，还有测试用例（尤其是故障揭示的测试用例）所满足的测试标准。满足标准的方式和被建立的标准的特点可以帮助我们理解程序失败的行为。正如在[31,32]中所讨论的，我们选择了程序突变作为调试目的的测试方法，而动态程序切片作为我们详细分析的工具。
通过研究基于突变的测试方法中的'声明删除'突变算子，得出了一种简单有效的方法，被称为'关键切片'。这里介绍一下基于突变的测试的简单描述。
程序变异的主要目标是帮助用户构建一个充分变异的测试集，将被测试的程序P与不正确的程序区分开来。测试集的充分性是通过对一系列简单的突变程序执行该测试集来衡量的。一个突变程序是通过对程序P引入一个简单的变化而产生的。这些简单的变化被认为是对P的简单的故障诱导转换，它们是通过研究程序员的常见故障和抽象故障的语法结构而根据经验得出的。一组突变的测试用例是在这些变化的基础上形成的。一个简单的P的突变程序，M是通过根据一个突变操作符对P的一个语句进行修改而生成的。P和M之间的唯一区别是P的第5行的原始状态（即语句Sp）和M中S的突变语句（称为突变，Sm）。一个测试集杀死的突变体的数量越多，暗示该测试集的充分性越好。用户试图通过寻找不同的测试数据来杀死所有简单的突变体。这样就构建了一个充分的测试集。如果P是正确的，测试集就是保证P的正确性的证据。另一方面，如果P不正确，错误就会通过杀死一些简单突变体而产生的测试数据表现出来。
图1展示了四个变种，它们是通过在ANSIC do-while迭代语句块上应用“语句删除”变种操作符生成的。文献[1,25]中已经报道了C的突变算子，并且在文献[15,14,41]报道了一种基于C的突变工具。从下面的描述中可以看出，派生语句变体不需要专门的工具。相反，一次删除一行代码、执行并比较结果的简单脚本将提供相同的结果，尽管效率低于专用程序。[1]中对“语句删除”突变运算符的描述总结如下：删除语句操作符(SSDL)的设计是为了表明给定程序中的每个语句对输出都有影响。SSDL鼓励测试人员设计一个测试集，使所有的语句都被执行，并产生与被测程序不同的输出。为了保持语法上的有效性，SSDL确保在删除一个语句时保留分号。根据C语言的语法，分号只出现在表达式语句和do-while迭代语句的结尾。因此，在突变一个表达式语句时，SSDL从状态中删除了可选的表达式，保留了分号。同样地，在改变一个do-while迭代语句时，将在其他情况下，如选择语句，分号会被保留，因为它不是被修改的语法实体的一部分。在其他情况下，例如选择语句，分号自动被保留，因为它不是被变异的语法实体的一部分。
在探索语句分析变异运算符（例如，SSDL）时，我们对每条语句的实际效果感兴趣，尤其是当程序通过显示故障的测试用例执行时。在那些直接导致程序失败的语句集中，很可能存在错误语句。死亡的SSDL突变体识别了一组语句，这些语句实际上对程序结果产生了影响，并且在SSDL突变体被显示失败的测试用例杀死时，对程序失败至关重要。这组语句是关键切片的基础。
1．定义
假设一组语句S={S1，S2，hellip;，Si，hellip;，SF}是针对给定故障执行错误程序P时的执行路径，显示故障类型为F的测试用例t，其中S表示可执行语句是不同类型故障的集合，F是发生故障的语句。例如，F可能是最后执行的语句，输出变量错误；或者SF是异常故障的语句（例如，除以零）发生。对于输出变量值不正确的故障类型，不正确的值被视为相关故障类型的特征。
定义1 当且仅当针对测试用例t执行的不带S<sub
剩余内容已隐藏，支付完成后下载完整资料</sub
英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[596141]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
课题毕业论文、外文翻译、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
