面向软件错误定位的测试用例约简技术的发展策

0引言
　　计算机软件正广泛应用于经济、军事、商业等各个领域中，对其可靠性问题的研究也日益得到了人们的广泛重视。保证软件高可靠性已成为系统开发和维护工作中不可或缺的一个重要方面。随着软件规模越来越大、逻辑越来越复杂，对软件可靠性的要求也日渐提高。然而，软件并不是如人们预期般总能可靠地运行，影响软件可靠性的一个主要因素就是软件中潜在的错误，这些潜在的软件错误极有可能对计算机应用系统带来不利影响。在此背景下，软件错误自动定位的目的就是通过执行程序源代码，分析程序运行过程中的运行时状态，检测程序中的异常情况，并将其独立出来作为需要进一步调试的可疑代码，从而将与软件错误无关的代码自动过滤掉，缩小错误代码的搜索范围，辅助开发人员快速有效地定位软件错误。
　　错误定位技术以定位软件中的错误代码为目的，可通过在待测程序上运行合适的测试用例，进而分析并定位错误语句。因此，错误定位的精度要更多地依赖于所执行的测试用例的质量。相应地，制定合适的测试用例约简方法，得到适合定位程序错误的测试用例的集合，已经成为亟需解决的问题。
　　本文在介绍测试用例的基础上，对面向错误定位的测试用例约简方法进行了分类，并对各类测试用例约简方法进行了介绍，最后对现有的测试用例约简方法进行了分析和总结。
　　1面向软件错误定位的测试用例约简方法概述
　　目前，关于测试用例的研究大多用于软件测试\[1-2\]，该方法首先在被测程序上执行测试用例，分析被测程序的动态行为和运行结果，由此而发现程序错误或功能缺陷，追求的目标是测试的充分性，因此，软件测试所使用的测试用例的集合一般都会比较大。但是该测试用例的集合中，很大一部分测试用例对错误定位的贡献不大，甚至一些冗余或偶然正确的测试用例还会降低错误定位的精度和效率。针对这一问题，很多学者提出了不同的测试用例约简方法，并进一步研究测试用例的约简对错误定位精度的影响。
　　测试用例约简是指在原测试用例的集合基础上，根据不同的测试需求，采用相应的约简策略，删除与测试需求无关的测试用例。目前，测试用例约简的研究大多面向软件测试，而用于错误定位的测试用例约简方法的研究较少。在研究面向错误定位的测试用例约简方法\[7-12\]中，学者们的研究对象主要是程序在执行过程中的程序谱\[13\]信息，即根据程序运行测试用例时的语句覆盖情况进行分析，据此再进行测试用例的约简。
　　2面向软件错误定位的测试用例约简方法分类
　　面向错误定位的测试用例约简方法主要分为基于语句覆盖的测试用例约简方法、基于语句向量的测试用例约简方法和突出考虑错误测试用例对错误定位影响的测试用例约简方法。下面对这三种约简方法逐一地展开分析。
　　第3期龚丹丹，等：面向软件错误定位的测试用例约简技术综述智能计算机与应用第4卷 2.1基于语句覆盖的测试用例约简方法
该类方法主要目的是保证各语句在约简后的测试用例的集合中皆被执行。即在原测试用例集合的基础上，制订不同的策略，选择部分测试用例，最终达到各语句皆被执行的目的。通常，基于语句覆盖的测试用例约简方法得到的约简后的测试用例数目较少，但与未约简的测试用例的集合相比，约简后的测试用例的集合很难提高错误定位的精度。
　　下面举例说明基于语句覆盖的测试用例约简方法。图1为实例程序mid()和所执行的测试用例的集合{t1,t2,t3,t4,t5,t6,t7,t8}。该实例程序mid()已广泛应用于错误定位和测试用例约简方法中，以验证其方法的有效性。其中，程序mid()的功能为，输入三个整数，输出三个整数的中间值。程序的第7行“m=y”为错误语句，正确语句应为“m=x”。程序的右侧为8个测试用例t1～t8。●表示执行测试用例t时，第i条语句被执行。由此可以看出，语句5仅被测试用例t2覆盖，则约简后的测试用例的集合应包含t2，语句11仅被t4覆盖，则约简后的测试用例的集合也应包含t4。对于语句6，同时被t1、t5、t7和t8覆盖，各学者对此提出了不同的策略，在t1、t5、t7和t8中选取其一。按照以上方法，当所有语句皆被覆盖时，即可得到最终约简后的测试用例的集合。在语句覆盖的测试用例约简方法中，一些学者首先将正确测试用例和错误测试用例进行区分，再制订相应的测试用例约简策略，最终得到不同的测试用例的集合。
　　Baudry等\[14\]将相同测试用例所覆盖的语句定义为动态基本块，研究了动态基本块的数量对错误定位精度的影响。结果表明错误定位的精度受动态基本块数量的影响。
　　Zhang等\[15\]将相对冗余的思想应用于错误定位约简方法中，研究成果表明，均衡语句覆盖可以提高错误定位的精度。
　　2.2基于语句覆盖的测试用例约简方法
　　该方法主要将测试用例执行后的覆盖信息以向量为对象进行分析。例如，执行测试用例t1的向量为<1,1,1,1,0,1,1,0,0,0,0,0,1>，执行测试用例t2的向量为<1,1,1,1,1,0,0,0,0,0,0,0,1>，由此可以看出，t1的向量与t2的向量不同，则约简后的测试用例的集合应同时包含t1和t2。t1、t7和t8所对应的向量相同，则可根据不同的策略，选择其中之一。同时，也可以将正确测试用例和错误测试用例区别对待，再制订相应的测试用例约简策略，最终得到不同的测试用例的集合。
　　mid() {
　　int x ,y ,z ,m ;测试用例t1t2t3t4t5t6t7t83,3,51,2,33,2,15,5,55,3,47,5,42,1,34,3,51: read ( x,y,z ) ;●●●●●●●●2:m=z;●●●●●●●●3:if(yy)●●●10:m=y;●●11:else if (x>z )●12:m=x;13:printf(m);●●●●●●●●}Pass / Fail StatusPPPPPPFF图1实例程序及测试用例
　　Fig.1Example program and its test cases
　　Yu\[16\]等在语句向量的基础上，将相对冗余思想用于测试用例约简，并将结果与基于语句覆盖的测试用例约简方法相对比。实验结果证明，与基于语句覆盖的测试用例约简方法相比，基于语句向量的测试用例约简方法删除了较少的测试用例，但约简后的测试用例更有利于错误定位。
　　2.3突出考虑错误测试用例对错误定位影响的测试用例约简方法该类方法主要目的是保证各语句在约简后的测试用例的集合中皆可得到执行。即在原测试用例的集合的基础上，制订不同的策略，选择部分测试用例，最终达到各语句皆可 执行的目的。通常，基于语句覆盖的测试用例约简方法得到的约简后的测试用例数目较少，但与未约简的测试用例的集合相比，约简后的测试用例的集合很难提高错误定位的精度。
　　在以上两类测试用例约简方法中，尽管一些学者提出了将正确测试用例和错误测试用例分类，但并未突出考虑错误测试用例对错误定位的影响。而研究表明，与正确测试用例相比，错误测试用例更有助于错误定位。
　　Wang\[18\]等提出根据错误路径生成最相似的正确路径，但算法的复杂度很高并只能生成一条成功路径且对赋值错误的定位不太敏感。
　　Chen\[19\]等研究了根据测试需求直接生成测试用例集合的方法。文中指出，测试用例需求的好坏，直接影响所生成的测试用例的质量。在构造需求关系图的基础上，首先生成测试用例需求，并在此基础上进行测试需求的优化，由此即构造出与测试需求相关的测试用例。
　　3结束语
　　目前的测试用例约简方法，都只研究了程序运行时的语句覆盖情况，忽略了程序运行时的具体执行路径信息，因为具有相同语句覆盖的测试用例所对应的执行路径未必相同，而且约简测试用例时对错误定位的需求考虑并不充分，因此，约简后的测试用例对错误定位的精度没有明显提高，甚至某些测试用例选择方法还会降低错误定位的精度。如果能够在分析程序执行路径基础上，面向错误定位需求约简出对错误定位有效的测试用例，那么不仅能降低错误定位的复杂度，而且也必将有助于提高错误定位的精度。
　　参考文献：
　　\[1\]VESSEY ise in debugging computer programs\[J\].International Journal of Man-Machine Studies: A Process Analysis,1985,23(5):459-494.
　　\// Proc.7th Network and Distributed System Security Symp,Internet Soc,2002: 3-17.
　　\[3\]ALEXANDRE P,RUI A,ANDRE R.A dynamic code coverage approach to maximize fault localization efficiency\[J\].Journal of Systems and Software,2014:18-28.
　　\.Computer & Security,2013,32:130-157.
　　\[5\]MAO X G,YAN L,DAI Z Y,et -based statistical fault localization\[J\].Journal of Systems and Software,2014,89:51-62.
　　\[6\]FEYZULLAH K,HASAN S,RRI um-based fault localization for diagnosing concurrency faults\[J\].Testing Software and Systems,2013,8254:239-254.