毕业论文范文——基于程序谱的软件错误定位方法研究

基于程序谱的软件错误定位方法研究Research of software fault localization techniques based on program spectrum学科专业：软件工程研 究 生：指导教师： 天津大学软件学院 年 月摘 要软件测试是保证软件能够正常运行的重要环节，而其中根据软件测试的结果进行错误定位的过程是一个自动化程度不高且费时费力的工作。因此，针对这一过程的改进是软件测试研究工作的重要领域。近十多年来，国内外学者提出了多种软件错误自动定位方法，其中最引人注目的是基于程序谱的一类方法。基于程序谱的软件错误定位方法使用插桩的方式在测试用例运行时收集程序信息，并作为错误定位方法的输入，采用数据挖掘和机器学习的方法寻找软件中与失败测试用例最为相关的代码或模块。众多基于程序谱的错误定位方法中，仍然存在定位精度不高、无法针对多错误的程序版本以及没有考虑程序中错误的类型等等问题。因此，进一步研究具有更好错误定位效果的错误定位方法仍然对提高软件测试和开发效率、降低成本和工作复杂度等仍具有重要的意义。本文工作针对目前的错误定位方法存在的问题展开，主要内容包括：一、 回顾了已提出的基于程序谱的软件错误定位方法，简单介绍其基本思路，并总结了各类方法的优劣。较为正式地定义程序谱以及错误定位问题的概念，并以例子阐述了相似度系数方法的过程。二、 提出一种相似度系数的程序错误定位方法，Multi-Ochiai方法。该方法引入了候选错误分布组合的概念，以解决程序中存在多个错误的问题。使用遗传算法搜索具有高可疑度的候选错误分布组合，并将结果转换为语句可疑度排名列表。三、 提出一种基于支持向量机的程序错误定位方法。该方法使用测试用例对程序语句的覆盖矩阵以及测试用例的运行结果对支持向量机进行训练，得到的模型对大量模拟测试用例进行分类，再以群体投票的方式得到语句的可疑度排名列表，四、 将本文提出的两种方法同三种相似度系数方法进行实验对比，并使用Friedman检验和多重比较检验检验结果的显著性。结果证明，本文提出的两种方法在不同的调试策略下相对于其他方法具有优势。关键词：软件测试 错误定位 程序谱 支持向量机ABSTRACTSoftware testing is an important phase to guarantee the quality of software. Debugging is a laborious job mainly by artificial means, so that fault localization becomes a focus field. In recent years, the spectrum-based fault localization techniques have attracted more and more research interest. The program spectra are collected by instrumentation in programs before test cases running. Then these techniques take this kind of information to correlate program entities and failed test cases so that the faulty entities can be found. However, there is a lot to be improved. So, the research on software fault localization is useful for increase efficiency in software developing, and it helps to free developers from tedious debugging work. The contribution of this paper includes:1. Review the existing spectrum-based fault localization techniques, and define the program spectra and the fault localization problem more formally.2. Propose a similarity coefficient fault localization technique, named Multi-Ochiai. This method uses the candidate of faults distribution to describe the location of multiple bugs in program. Genetic algorithm is employed to search for candidates with high suspiciousness values, and its results are converted to statements suspiciousness ranking.3. Propose a fault localization based on support vector machine. Program spectra and test case results are used to train a support vector machine, which will classify vast simulative test cases. Group voting method is used to get the suspiciousness ranking.4. An experiment is conducted to compare the two new methods with other three methods, and the Friedman test and multiple compare test are used to investigate the statistical significance of any differences observed in the experiments. The result suggests that the new methods outperform other related techniques in some respects.KEY WORDS：software testing, fault localization, program spectrum, support vector machine目 录第一章 绪论11.1 研究背景11.2 研究现状21.2.1 动态软件错误定位方法研究现状21.2.2 研究现状分析与总结51.3 本文工作及组织结构61.3.1 本文主要工作61.3.2 本文组织结构7第二章 相关工作82.1 软件测试概念及相关技术82.2 程序谱92.3 错误定位问题92.4 相似度系数错误定位方法112.5 相关工具142.5.1 Gcov142.5.2 SIR142.5.3 LIBSVM14第三章 基于程序谱的软件错误定位方法163.1 Multi-Ochiai方法163.1.1 Multi-Ochiai相似度系数163.1.2 错误数量估计183.1.3 候选错误分布组合搜索及获取可疑度排名列表203.2 基于支持向量机的方法253.2.1 动机253.2.2 支持向量机253.2.3 基于支持向量机的错误定位方法30第四章 实验验证364.1 被测程序选择及错误植入364.1.1 被测程序选择364.1.2 错误植入364.2 实验环境374.3 评价标准384.4 实验结果394.4.1 参数设置394.4.2 单个错误的错误版本实验结果404.4.3 多个错误的错误版本实验结果414.5 结果分析45第五章 总结与展望505.1 本文工作总结505.2 下一步工作展望51参考文献52发表论文和参加科研情况说明56致 谢57第一章 绪论第一章 绪论1.1 研究背景近年来，计算机、手机等电子设备的应用越来越广泛，计算机软件迅速地从人们脑海中遥不可及的概念进入到眼前和指尖的生活。计算机软件的数量、规模以及软件开发的速度都在飞速发展。航天、汽车、机械控制等领域所使用的软件要求极高，任何形式的软件失效都有可能导致严重的后果；即使在民用软件领域，软件的出错也会极大地影响用户体验，甚至导致用户的流失，造成严重损失。在此条件下，对于软件开发团队来说，如何保证软件的质量成为需要重点考量的问题。因此，软件测试成为贯穿软件开发流程的一项重要工作，越来越得到软件开发团队的重视。在极限编程、测试驱动开发等概念得到广泛应用的时代，软件测试的重要性不言而喻。版本高速迭代的条件下，软件测试所耗费的时间以及测试后进行错误调试的时间都是极其宝贵的，是软件成本构成中的很大一部分1,2。因此，任何对软件测试以及错误调试的改进都是降低软件成本的有效手段。自动化测试的引入让一些可重复的测试工作能够自动完成并生成测试报告；测试用例约简、选择及排序技术的应用让回归测试针对性更强；但是，对错误的定位工作往往仍然需要人工完成。如何让这一过程尽可能地自动化，如何让测试报告尽可能地将进行调试工作的人员正确地引向错误发生的位置，这就是软件错误定位这一研究领域所关注的问题。目前，国内外学者对软件错误定位都进行了大量的研究。软件错误定位的技术按是否需要运行测试用例可分为静态分析和动态分析36两类方法。其中静态分析主要指对程序代码进行审查，分析代码质量和内在联系（数据依赖、控制依赖等关系），以期找出有错误的语句在程序中的可能位置。而动态错误定位方法需要运行测试用例，其中比较有代表性的方法包括基于程序谱的方法、基于程序状态修改的方法、基于模型推理的方法、基于程序依赖关系的方法以及基于程序修改（变异）的方法等等。在动态错误定位方法中，基于程序谱的方法是目前国内外研究最多的一类方法。程序谱即为测试过程中收集的描述程序运行状况的信息，包括语句覆盖信息、谓词取值、测试用例结果等等，通过对程序谱进行分析，可以找到测试用例失败同程序实体（语句、方法、类、谓词等等）之间的关联关系，从而较为精确地定位软件中的错误。基于程序谱的软件错误定位方法研究虽然很多，但是仍然存在一些问题。一是大多数方法都是针对软件中只有一个错误的情况来考虑的，这在实际生产中并不实际；二是这些方法通常没有考虑错误的类型，而一些类型的错误是不能够或者不能被准确地通过这类方法进行定位的；三是错误定位的精度仍有改进的空间。本文就针对这些问题进行了一系列研究，并提出了两种针对多错误的基于程序谱的错误定位方法，并进行了实证研究，取得了不错的效果。1.2 研究现状1.2.1 动态软件错误定位方法研究现状如前文所述，当前的软件错误定位方法可按照是否执行测试用例分为静态的错误定位方法和动态的错误定位方法。其中，静态的错误定位方法主要为代码审查方法，而动态错误定位方法需要执行测试用例并收集运行信息。在此对有代表性的动态错误定位方法的国内外研究现状做一介绍。早期的研究发现，程序切片7，进一步是动态切片811能够用于程序的理解以及软件测试和错误定位当中。Reps等人早在1997年解决千年虫问题时提出了程序谱的概念12，其通过在程序中插桩的方式可收集到程序在运行时的路径分布情况，并指出，程序谱是一种易于获得的刻画程序运行时行为的信息。Harrold、Rothermel等人在2000年的一篇文章中就开始使用程序谱13，他们通过实验来比较程序修改前后程序谱的异同，这是最早的程序谱应用在回归测试中的例子。文章指出，在特定的程序输入条件下，如果程序结果出现错误，那么其程序谱也往往会与正常情况相异；而若程序谱出现不一致情况时，程序有可能出现正确的结果，但这种情况出现的频率远低于前者。这一结论也为之后的研究工作奠定了基础。NNQ法是Renieres和Reiss在2003年提出的一种程序谱来定位软件中的错误的方法14，其思路是比较失败的测试用例的程序谱与通过的测试用例的程序谱，找出与失败测试用例程序谱最为相似的通过测试用例程序谱，再通过比较两者的异同来定位错误。其在论文里还描述了Set-Union和Set-Intersection两种类似的方法。这一类方法认为通过的测试用例执行过的代码都不应该被怀疑，或者怀疑度更低，但这一点通常并不成立：输入值的不同可能导致错误的代码语句表现出不同的行为，被通过测试用例执行的代码同样有可能是有缺陷的，只要这些代码被失败的测试用例执行过。针对这一问题，Jones和Harrold等人在2002年提出了著名的Tarantula相似度系数方法15,16。该方法是由所有测试用例的结果以及所有测试用例对待测程序代码的覆盖情况，计算出程序中每一语句与失败用例的相似度系数，这样的系数也可被称为该语句的怀疑度，因此本方法也叫做Tarantula怀疑度计算公式法。Tarantula的指导思想是，被更多失败的测试用例覆盖到的语句，相对于被更多通过的测试用例覆盖的语句，更应被怀疑。Tarantula法的计算公式如下：（1-1）其中，s表示程序中的某一行语句，这里计算的就是该语句的怀疑度，怀疑度最高为1，最低为0。和分别表示运行了语句s的失败的测试用例数量和通过的测试用例数量；（本公式中未出现）和分别表示没有运行语句s的失败的测试用例数量和通过的测试用例数量。通过Tarantula的计算公式可以发现，该相似度系数的计算方法考虑到了有错误的程序语句偶尔被正确执行的情况。与Tarantula类似，Abreu等人之后提出的Ochiai相似度系数5：（1-2）Ochiai相对于Tarantula，考虑到了，即没有运行语句s的失败测试用例数量的影响。显然，如果该项更大的话，语句s是错误的可能性应该更低。Jones和Harrold等人还引入了程序语句可疑度的置信度，进而改进了Tarantula相似度系数的计算方法16：（1-3）此外，还有一系列类似Tarantula和Ochiai的方法，Naish等人在2011年提出一个模型来比较这些相似度系数方法的效果17。其在文章中给出了一个叫If-Then-Else-2（ITE2）的小程序，用来说明（1）错误代码并不是在每个测试用例中都会执行，因此有些很少被执行到的错误代码很难被发现（即信号微弱）；（2）存在影响错误定位精度的噪声，即可能出现错误被掩盖等情况。他们还提出了一个最优公式OP：（1-4）郝丹等人提出的SAFL方法考虑了测试用例的相似性18，并且试图消除测试用例的相似性对于错误定位效果的影响。与这些方法不同，另一类基于程序谱的方法把关注点集中在程序中的谓词。Liblit等人在2005年提出的CBI（Cooperative Bug Isolation）方法19分别统计程序中的每个谓词在通过的测试用例和失败的测试用例中取值为真的次数来计算该谓词的怀疑率。Liu等人提出的SOBER方法20中提出了取值偏差的概念。一个谓词P的取值偏差指该谓词在一次执行中取真值的频率。如果谓词P的取值偏差在通过和失败的测试用例中的差异越大，则说明该谓词更有可能为程序的缺陷所在。SOBER使用以下公式来计算谓词P的可疑度：（1-5）其中，P是谓词P在所有通过的测试用例中的取值偏差的方差，Z是谓词P在所有失败的测试用例中的取值偏差的均值的随机变量，|Tf|是所有失败的测试用例的数量。张震宇等人提出的DES（debugging through evaluation sequences）方法21考虑到了谓词的布尔表达式求值时的短路现象。其发现，短路现象会影响到缺陷定位的效果，因此将每个谓词排名最高的取值序列作为该谓词的排名。改进之后的算法在仅需花费很小的额外开销的情况下提高了缺陷定位的效果。Baah等人提出了概率程序依赖图PPDG22，借助程序谱，预测出程序中语句之间的条件统计相关性和独立性，进而有效地推测出缺陷语句的位置。此外，Dallmeier等人提出的基于方法调用序列的Ample方法23，Yilmaz等人提出的引入了程序执行时间信息的TWT方法24，都是在基于程序谱的方法基础上的改进，取得了不错的效果。Wong等人将统计表25、BP神经网络26、RBF神经网络27等统计方法和机器学习方法与程序谱相结合，提出了一系列新颖的错误定位方法。程序谱与神经网络结合的方法具有良好的容错性，即此类方法不会因为运行了错误的语句却没有出错的测试用例而受到影响。Wotawa等人提出的错误定位方法28与以上的基于谱的方法差别较大，此类方法被统称为基于模型的错误定位方法6。此类方法使用逻辑推理的方式来诊断程序中的错误，并且也使用到了程序谱信息。Mun等人提出的MUSE方法29采用对源程序进行随机变异的方法，将变异测试的概念引入错误定位问题，取得了很好的效果。此外，Jeffrey等人提出的值替代的方法30采用在运行时将变量值进行替换的方式来进行错误定位。也存在一些方法和技术针对存在多个缺陷的软件错误定位问题。Jones等人提出的并行调试方法31使用聚类技术将失败的测试用例的程序谱分为针对某一单独缺陷的类，再由多个程序员进行并行的调试过程。Abreu等人在2009年提出的BARINEL方法32则是结合了基于谱的方法和基于模型的方法的优点，使用概率组合模型来对存在多错误的软件进行定位，并证明了其有效性。1.2.2 研究现状分析与总结综上，软件错误定位这一领域在最近二十年有着丰硕的研究成果，虞凯33等人也对此做了总结。不同的研究人员以多种研究思路提出了各种类型的方法。从最为简单的静态的代码审查，到需要通过运行测试用例得到程序谱和测试用例结果信息进行统计分析的基于程序谱的方法，再到需要建立概率模型或其他模型的基于模型的方法，以及最近的例如MUSE的基于变异的方法等等。这些方法各有各的优势，但也各自存在一些需要改进之处。静态的代码审查方法没有使用到任何运行时的信息，因此其局限性较大，只能根据软件度量原则，推测出软件各部分组件的错误易发性，并不能较为精确地指出错误的位置，因此一般不会用于代码出现错误时的调试过程。但是，静态方法中所使用的建立程序依赖关系模型以及使用到的软件度量等方法可以作为借鉴，结合程序谱等动态信息来更为精确地定位软件中的缺陷。基于模型的方法充分利用了程序谱等动态信息，同时根据代码结构和上下文依赖关系建立起精确的模型，因此该类方法的精确性非常高，即使在没有完全命中错误的情况下，也可以根据数据依赖关系和结构依赖关系来迅速定位错误。但是，基于模型的方法的缺点也很明显，建立这样的模型是需要较多的数学背景，同时建立模型的过程和进行推导的过程也比较耗费时间。因此，在实际应用中，虽然基于模型的方法有很好的精确性，但是相对的，其代价也比较大，且对人员要求也比较高，不适用与一般的开发流程。前文所提到的MUSE方法采用的是一种思路比较新颖的方法。该方法借用变异测试的概念，对程序中的语句进行随机的变异，包括修改逻辑符号、更改常量等等，再用变异后的新的程序版本进行测试。对一个程序进行不同位置不同类型的变异，再进行大量的测试，会出现失败的测试用例增多、减少、不变或者全部通过的情况。如果某次变异的测试中，失败的测试用例减少或者全部通过，则说明该次变异刚好是出现在原版本程序中有缺陷的位置，或者是正好将原版本中缺陷导致的程序异常行为进行了纠正。根据这样的信息，可计算出各语句的可疑度，得到可疑度排名列表，程序员便可根据该列表有针对性地进行错误修正了。显然，这样的方法能够得到很好的结果，但是所需的运算量是非常大的，变异的版本越多，所需要进行的测试量也就越大。相对比较折中的方法就是基于程序谱的软件错误定位方法。类似于Tarantula和Ochiai这一类相似度系数的方法计算速度很快，通过定义好公式，将程序谱0-1矩阵输入，即可瞬时得到可疑度排名。因此这类轻量级的方法也是研究的重点领域，也能够在工业界得到较好的应用。但是，这类方法的针对性并不太强，因为它们都只是将所有代码等同，并未对代码作一个客观的、先验的评价，以辅助错误定位。而SOBER这样的方法就将谓词作为其研究的重点，其认为谓词是程序中较为容易出错的片段，因此通过研究针对谓词的错误定位相对比较有目的性。目前已有的基于程序谱的错误定位方法研究成果的定位精度仍然可以进一步提高，同时，根据分析错误类型，对错误类型与定位精度之间的关系进行探究，可以比较有针对性地对可以使用本方法的错误类型进行定位，而排除掉不能使用基于程序谱的错误定位方法定位的错误，以降低工作的盲目性。此外，针对软件中存在多个缺陷的情况也应进行针对性的考虑，因为这种情况下，缺陷对程序行为的影响会出现相互干扰，从而降低软件错误定位的精确性。本课题的工作就是以考虑多缺陷情况下提高错误定位精确性和针对性为目的进行的。1.3 本文工作及组织结构1.3.1 本文主要工作本文提出了两种基于谱的错误定位方法，一是Multi-Ochiai方法，二是基于支持向量机（SVM）的方法。Multi-Ochiai是对传统的基于相似度系数的方法Ochiai的扩展，并与聚类算法和遗传算法34相结合，以解决多错误场景下的软件错误定位问题。基于SVM的方法引入了一种机器学习方法，即支持向量机，通过空间映射将线性不可分的错误定位问题转化为等价的线性可分的问题，并计算特征点（即代表程序语句）与分类面的距离来确定其可疑度。本课题的主要研究内容包括：1、提出一种基于相似度系数的程序错误定位方法，即Multi-Ochiai方法。Multi-Ochiai拓展了Ochiai相似度系数计算公式，将原先Ochiai等相似度计算公式计算程序语句的可疑度拓展成为计算候选错误分布组合的可疑度，由此可以针对程序中存在多个错误的情形。Multi-Ochiai方法使用遗传算法搜索具有高可疑度的候选错误分布组合，并形成候选错误分布组合池。候选错误分布组合池可转化为程序语句可疑度排名列表。在Multi-Ochai方法中，还讨论了程序中错误数量的估计方法以及调试人员进行调试时采用的策略等内容。2、提出一种使用机器学习方法的基于谱的程序错误定位方法，即基于支持向量机的方法。本方法针对的是程序中的错误语句间歇表现的特点，具有较好的噪声处理能力。基于支持向量机的方法将线性不可分的程序谱信息进行空间映射，转化为线性可分问题进行求解，将程序语句进行分类。程序语句的覆盖向量与分类超平面的距离可作为该程序语句的怀疑度，进行排序后便可得到可疑度排名列表。3、实验验证Multi-Ochiai方法和基于支持向量机的方法，并将其与经典的相似度系数方法进行比较。实验结果使用Friedman检验35和多重比较36等参数检验方法对方法之间的差异进行分析。1.3.2 本文组织结构本文在第二章会介绍软件错误定位的一些背景，正式地定义软件错误定位问题，例证基于相似度系数的软件错误定位方法，并介绍使用到的相关工具。第三章会详细描述两种新的基于谱的错误定位方法。第四章是实验验证，将本文提出的方法同已有的方法相比较。第五章是本文总结和对未来工作的展望。54第二章 相关工作第二章 相关工作2.1 软件测试概念及相关技术首先需要阐明的是错误（error）、故障（fault）、失效（failure）以及缺陷（defect）等词的概念区别。错误是指程序员在编写程序时无意或有意写出的与正确代码相异的代码。而故障是一个或者多个错误的表现。当程序执行时，有故障的代码会引起程序失效，致使程序中途报错或者不符合期望的输出结果。缺陷以及bug一词也通常用来描述程序代码中导致程序运行失效的那部分不正确的代码。本文中，错误、故障、缺陷和bug几个词没有作明确的区分，均指引起程序失效的源代码中的不正确的代码。软件测试是采用测试用例来执行软件的活动，测试有两个显著的目标，即找出失效以及演示正确的执行。它是帮助识别开发完成（中间版本或者最终版本）的计算机软件的正确性、完全性以及质量的软件过程。根据测试对象和目的的不同，软件测试包括单元测试、回归测试、压力测试、性能测试、验收测试等等。测试用例（test case）是为某个特殊的目标而编制的一组测试输入、执行条件和预期结果，以测试某个程序路径或者核实软件是否满足某个特定需求。一个完善的测试用例应该包括测试目标、测试环境、输入数据、测试步骤、预期结果、测试脚本等内容，并形成文档进行保存，具有可重复性。对大型、复杂的软件以及目前应用广泛的嵌入式软件的测试是一项劳动密集型的工作。一次完整的测试过程通常会包含数千甚至上万的测试用例。这一过程若完全由人工进行的话，即劳神费力，还极其容易出错，不易规范管理。因此，测试自动化就成为了软件测试的一个重要的研究方向。然而，由于软件运行的环境千差万别，测试目标和测试种类繁多，测试自动化的过程并不通用，因此测试自动化往往是一项很有针对性的工作，企业和组织内部开发了许多专用的自动化测试工具。但是确有一些通用的自动化测试工具，例如JMeter、QTP、Selenium等等，这些软件针对不同的测试目标，得到了较为广泛的应用，极大减轻了测试人员的工作量。软件测试的工作是找出测试用例在软件运行时的失效，而由失效定位并修正程序中错误的过程称为调试（debug）。调试工作一般是由开发人员手动完成。有文献指出，软件测试约占软件开发、维护总成本的50%到75%，而这其中最为耗时、花费最大的一项任务就是调试。整个调试过程中，错误定位的过程又是最为困难的。因此，任何针对错误定位技术的改进都可以很大程度上降低调试的成本，从而降低整个软件开发过程的成本。同时，错误定位的过程对于开发人员来讲是枯燥而艰难的，因此，错误定位技术的改进对于开发人员来讲是一个降低工作强度，把他们从繁杂工作中解放出来的有益工作。本文所做的工作就是对错误定位技术的改进。2.2 程序谱程序谱，也称为程序轨迹、程序行为特征等等，是在程序执行过程中收集到的描述程序执行过程和执行特征的信息。程序谱这一概念是由Reps等人在研究千年虫问题时最早提出的概念，而之前其他人的一些工作也部分用到了这一信息。程序谱包含程序代码在运行时是否被执行、执行次数，程序中的谓词的取值情况，代码分支覆盖情况等等，可根据实际需求进行有针对性的剪裁。本课题所需要的程序谱信息为代码在运行时是否被执行，以及每个测试用例是否通过。程序谱的收集通常借助一些工具，在源代码中插桩以在运行时收集所需信息。以C语言为例，程序谱的收集需要借助gcov工具，在编译时在源代码中插桩，以便程序在运行时记录语句的执行情况，最后生成测试报告。Gcov生成的测试报告记录了源代码中每一行代码是否被执行，以及被执行的次数。根据gcov生成的报告，可通过脚本转化为程序谱常见的0-1矩阵形式，供后续研究使用。表2-1 0-1矩阵形式的程序谱e1e2e3e4e5e6e7resultt111100010t210011001t300001110t411110000t501111010t6100111002.3 错误定位问题本节将较为正式地定义错误定位问题，本节之后的内容将参照本节所定义的符号和概念。本文所讨论的是计算机软件测试时的错误定位问题。待测程序表示为P，其测试用例集表示为：（2-1）其中，m为待测程序P的测试用例集中测试用例的数量，1im，ti表示该测试用例集中第i个测试用例。此外，TF可表示测试用例集中失败的测试用例的集合，TP可表示测试用例集中通过的测试用例的集合。待测程序P中的实体表示为：（2-2）这里的实体可以是程序中的一条语句，一个方法，一个类或者一个代码段。在本课题的研究中，实体都是指待测程序P中的语句。其中，n为待测程序P中实体的数量（可执行的代码行数），1jn，ej表示程序P中的第j个实体（第j行可执行代码）。测试用例的执行结果可表示为结果向量：（2-3）其中，m为待测程序P的测试用例集中的测试用例的数量，ri表示第i个测试用例的执行结果，1im。如果ri=1，则第i个测试用例的输出与其期望的输出不一致，即该测试用例为一个失败的测试用例；如果ri=0，则第i个测试用例的输出与其期望的输出一致，即该测试用例为一个通过的测试用例。程序谱可表示为覆盖矩阵：（2-4）即M为表示T和E覆盖关系的矩阵，M为一个mn的矩阵。覆盖矩阵M中的第i行可表示当第i个测试用例运行时，待测程序P中的语句是否被执行，由这一行组成的向量也被称作该测试用例的覆盖向量。而覆盖矩阵M中的第j列可表示待测程序P中的第j行可执行语句在所有测试用例运行时是否被执行。覆盖矩阵M中的每一项Mij表示第i个测试用例执行第j行可执行代码的情况，如果Mij=1，则第i个测试用例运行时执行了待测程序P的第j行可执行代码，也称第i个测试用例覆盖到了第j行可执行代码；如果Mij=0，则第j个测试用例在运行时没有执行到待测程序P的第j行可执行代码。由失败的测试用例可构成失败用例覆盖矩阵：（2-5）MF是覆盖矩阵的一部分，仅包含失败的测试用例的覆盖信息。同样地，由通过的测试用例可构成通过用例覆盖矩阵：（2-6）覆盖矩阵M和结果向量R即为本课题中讨论的软件错误定位问题的输入，由该程序谱信息，通过软件错误定位方法，得到程序实体集E的可疑度排名列表，即为本课题所研究的问题。根据该可疑度排名列表，程序员从由可疑度最大的程序实体（语句）开始检查，直到找到有缺陷的程序实体（语句）。2.4 相似度系数错误定位方法在第一章中介绍过几种计算程序语句与失败测试用例之间相似度系数的软件错误定位方法。此类方法是基于程序谱的软件错误定位方法中研究较为广泛的方法。最为经典的相似度系数方法包括Jones和Harrold等提出的Tarantula：（2-7）引入了置信度的改进的Tarantula：（2-8）以及Abreu等人使用的Ochiai：（2-9）以下以一个函数findSecond来说明此类方法是如何工作的。findSecond函数以4个整数作为输入，输出其中第二大的整数。在findSecond函数的错误版本中，其第17行存在错误，temp=b应为temp=c。findSecond的错误版本如表2-2所示。表2-2 函数findSecond的错误版本代码函数findSecond1int findSecond(int a, int b, int c, int d) 2int max, min, temp;3if(a max) 11temp = max;12max = c;13 else if(c min) 14temp = min;15min = c;16 else 17temp = b; /* 错误。应为temp = c */1819if(d temp) 20return d;21 else if(d max) 22return max;23 else 24return max;2526findSecond函数的测试用例集中有9个测试用例，图2-1是9个测试用例在findSecond函数上的运行结果、覆盖信息以及上文所述几个相似度系数的计算结果和可疑度排名。在图2-1中，只列出了findSecond函数体中的可执行语句，忽略了不可执行的语句。每一个测试用例都有其输入和期望的输出值，测试用例执行后可得到实际的输出值，两个输出值进行对比即可得到测试用例的结果向量，即指明测试用例是通过还是失败。在本例中，第7个测试用例失败，其他用例都通过。覆盖矩阵和结果向量用以计算Tarantula、Ochiai以及带有置信度的Tarantula等三种相似度系数，可得到每一可执行语句的可疑度值。不同相似度系数计算公式得出的同一语句的可疑度有可能不同，但在本例中，每一语句在可疑度排名列表中的位置都是一致的。如果两条语句的可疑度值相同，则其排名相同，在检查语句时可以任意语句进行检查。由可疑度排名列表可知，第16及第17条语句的可疑度最大，而第17条语句恰好正是错误所在。因此这三种相似度系数错误定位方法都能够精确地定位findSecond函数错误版本中的错误。需要指出的是，虽然在本例中三种相似度系数计算公式的排名结果一致，但在更大更复杂的程序中，它们可能会出现不同甚至迥异的结果。图21 findSecond错误版本的测试用例执行情况以及三种相似度系数方法的结果2.5 相关工具2.5.1 Gcov本课题所研究的错误定位技术均针对C语言，并在实验验证部分使用C语言程序作为被测程序。因此需要工具来对C语言程序进行插桩收集其语句覆盖信息。Gcov（GCC coverage）是一个针对C/C+语言程序，获取测试代码覆盖率的工具。它是一个命令行方式的控制台程序，伴随GCC发布，并配合GCC共同实现对C/C+文件的语句覆盖、分支覆盖等覆盖类型的测试。同时，gcov可同程序概要分析工具（如gprof）等一起工作，对代码的耗时进行估计和分析。根据不同的命令行参数，gcov能够按照基本块或者分支等不同的粒度来统计代码的执行情况，并输出每个基本块/分支的执行次数，指出哪些部分的代码没有被执行等等。正是基于这样的功能，gcov是一个理想的获取程序谱的工具。Gcov的使用大致分为三步。在编译时，需要告诉编译器生成gcov需要的额外信息，这也相当于让编译器在程序中进行插桩。在运行时，gcov统计程序代码的执行情况，并生成gcov的数据文件。最后生成gcov的报告，该报告记录了每行代码的执行情况和具体执行次数等程序谱信息。2.5.2 SIRSIR（Software-artifact Infrastructure Repository）是一个程序组件库37，为程序分析、软件测试技术等研究工作提供实验所需的程序和相关材料。SIR中包括了Java、C、C+以及C#等语言的程序，且一并提供对应的测试用例、错误数据、脚本以及文档等等。每一程序都有多个错误版本，以供软件测试研究使用。SIR中的程序广泛应用于软件错误定位研究的实验部分，本课题的研究使用到了其中最为常用的七个C语言程序，即print_tokens、print_tokens2、replace、schedule、schedule2、tcas、tot_info。2.5.3 LIBSVMLIBSVM是台湾大学林智仁教授等开发设计的一个支持向量机模式识别与回归的软件包，其具有简单、易用且快捷有效等优点。LIBSVM提供了编译后的执行文件，也提供了源代码方便进行改进。LIBSVM目前支持C、Java、Matlab、R、Python等等多种语言。LIBSVM提供了很多默认参数，且提供了交叉检验功能以便尝试出最优的核函数和相关参数。该软件支持C-SVM、-SVM、一类SVM、-SVR以及-SVR等问题。软件包的svmtrain方法根据提供的数据、类别标签以及参数训练支持向量机，使用svmpredict方法对数据进行类别预测。本课题中基于SVM的方法在Matlab上使用LIBSVM进行数据训练与分类。第三章 基于程序谱的软件错误定位方法第三章 基于程序谱的软件错误定位方法本章将介绍两种基于程序谱的软件错误定位方法，一是在Ochiai相似度系数计算公式基础上进行改进的Multi-Ochiai方法，二是基于支持向量机的软件错误定位方法。Multi-Ochiai针对Ochiai相似度系数计算公式只能以单条语句为单位进行可疑度计算的问题进行改进，并使用遗传算法进行高可疑度值的候选错误分布组合的搜索，最终转换为可疑度排名列表；基于支持向量机的方法使用支持向量机对程序谱数据进行训练和分类，将代表语句的向量与分类超平面之间的距离作为可疑度值（可信度值），从而得到可疑度排名列表。本章将详细描述和定义这两种方法。3.1 Multi-Ochiai方法3.1.1 Multi-Ochiai相似度系数如前文介绍，Tarantula、Ochiai等相似度系数计算公式通过计算测试用例覆盖语句信息和测试用例的结果直接的相似度系数，得出每一条程序语句的可疑度（即与失败测试用例的相关性）。通过对所有语句的可疑度进行从大到小的排名，可得到可疑度排名列表，程序员便可按顺序逐个检查该列表上的语句，从而发现错误在程序中的具体位置。Tarantula及Ochiai等相似度系数计算公式所度量的是每一条语句的可疑度值，这是基于软件中只存在一个缺陷的假设。但是在实际的软件调试过程中，被测程序往往并非只有一个错误。Tarantula和Ochiai所得出的可疑度排名列表在多错误的情况下能够作为参考，但是因为并没有根据多错误的情况进行优化，因此会存在潜在的问题。本课题提出的Multi-Ochiai相似度系数计算公式便是针对这一问题在Ochiai相似度系数计算公式上做的改进。当测试用例出现错误的结果的时候，即测试用例失败时，程序中至少存在一条语句为错误的语句，可能会存在多个错误导致了该测试用例的失败。候选的错误分布组合38可表示为一个二进制向量：（3-1）其中，n为被测程序的可执行语句的数量，cj表示被测程序中的第j条语句，如果cj=1，则在该候选错误分布组合中，第j条语句被认为是存在错误的；如果cj=0，则在该候选错误分布组合中，第j条语句被认为没有缺陷。例如一个候选错误分布组合：（3-2）该候选错误分布组合C表示，被测程序共有9条可执行的语句，其中第三和第八条语句被认为是有缺陷的，其余的语句被认为是无错的。Multi-Ochiai相似度系数计算公式度量候选错误分布组合的可疑度值。对于一个候选错误分布组合C，其可疑度值（即该候选错误分布组合为真实的错误分布组合的概率）可由下式计算：（3-3）其中，(C)定义为：（3-4）式（3-4）中函数被称作指示函数，定义为：（3-5）公式（3-3）中的|TF|为失败的测试用例的数量。(C)计算的是候选错误分布组合C“解释”失败的测试用例的能力。如果一个失败的测试用例运行了一个或者多个在候选错误分布组合C中被认为是有错的语句，则该失败的测试用例能够被候选错误分布组合C解释；如果该失败的测试用例运行到的语句在候选错误分布组合C中都被认为是无错的，则该失败的测试用例不能被候选错误分布组合C解释。(C)的值为候选错误分布组合C能够解释的失败测试用例的数量。(C)的值加一，当且仅当候选错误分布组合C能够解释一个失败的测试用例，即：（3-6）式（3-3）中P(C)定义如下：（3-7）其中，|TP|是通过的测试用例的数量。P(C)是一个惩罚函数，如果一个候选错误分布组合C中被认为是有错的语句被通过的测试用例执行到，则P(C)加一。需要说明的是，(C)中如果C能解释一个失败的测试用例，则(C)增一，而P(C)中并未引入指示函数，则C中被认为有错的语句被通过的测试用例执行一次则P(C)增一。这样做的目的是让候选错误分布组合C中被认为有错的语句数量保持在一个比较低的水平，这与实际调试时程序的错误数量一致。如果一个候选错误分布组合C中被认为有错的语句数量较多，则其P(C)值会更大，从而降低该候选错误分布组合的可疑度值。3.1.2 错误数量估计在存在单个错误的程序错误定位问题中，调试人员可根据错误定位方法给出的程序语句可疑度排名列表顺序对程序语句进行检查。当调试人员发现一个错误后，即可停止这一检查过程。这里一般做了一个乐观假设，即调试人员检查程序语句时，如果语句存在错误，调试人员就一定能够发现该错误。然而，当存在错误的程序中的错误数量未知时，何时停止检查语句并重新运行测试用例成为一个需要解决的问题。在调试过程中，有两种策略可供选择，一是每次找到错误并修改后均重新运行测试用例并得到新的可疑度排名列表；二是一次性根据预估的数量找到多个错误或者达到设立的停止标准后再重新运行测试用例以确认程序中是否还存在错误。在Multi-Ochiai方法中，采用了对错误数量进行估计的方法来设置停止检查程序语句的条件。Multi-Ochiai方法使用了聚类方法来估计程序中的错误数量。对错误数量的估计基于这样的假设：如果测试用例的失败由同一个错误引起，则其覆盖信息（即程序谱）应相似；如果测试用例的失败由不同的错误引起，则其覆盖信息应有明显的区别。基于这样的假设，则可对测试用例的覆盖向量进行聚类从而分析出程序中错误的数量。具体方法如下：(1). 使用K-means聚类算法39去除具有相同覆盖向量的失败测试用例。K-means聚类算法是最常用的聚类算法之一，其以聚类个数以及需要进行聚类的数据对象作为输入，输出满足方差最小标准的数个聚类。此处使用的K-means聚类算法仅完成一次迭代，初始聚类数量为失败的测试用例数量，进行聚类的数据对象即被测程序所有失败的测试用例的覆盖向量。在聚类过程中，若遇到空聚类，则直接移除该类，使用到的标准测度函数为汉明距离。因此，在K-means聚类算