在软件开发过程中，回归测试是一项重要而复杂耗时的工作。测试用例排序技术作为提高测试效率的一种有效手段，是近年的研究热点之一。测试用例排序技术根据测试目标对测试用例进行排序，使得最优的测试用例能够优先执行。同时，各种软件信息的底层结构及关联信息有助于提高测试效率。不同的代码单元在测试过程中拥有不同的测试需求。因此，利用聚类算法能够有效地分析测试用例间的结构信息，从而指导测试用例的排序过程。实验结果表明，新的测试用例排序策略有效地提高了测试用例排序的效果，能够更早地检测到软件错误。
蔡景媛,任志磊,胡燕,等:基于聚类算法的测试用例排序 2016,52(5) 1)选出各簇首位测试用例进行排序,若充用例覆盖的软件错误,也无法得知其检测信息。因此 首位则跳过; 移除不被任何测试用例覆盖的语句和软件错误。 2)顺序加入测试川例排序结果,将各簇首42实验算法 位测试用例移除。 本文对比三种算法的测试用例排序效果。 Until各簇均空 A算法为原有的聚类测试用例排序算法。在对测 End 试用例聚类后,利用代码覆盖信息对簇内的测试用例进 对每个簇内的測试用例根据其覆盖的代码单元权行排序,簇间排序随机。 重进行排序,对于已排序的各簇内测试用例进行二次排 B算法为本文收进的聚类测试用例排序算法。在 序。首先对各簇第一位的测试用例进行排序,将排序结对测试用例进行聚类后,利用代码覆盖信息对簇内的测 果直接输出到测试用例的排序结果中。然后对各簇的试用例进行排序,利用本文设计的簇间排序算法对聚类 第二位测试用例进行排序,将排序结果直接输出到洌试后的结果进行排序。 用例的排序结果中,以此类推直至所有簇都为空。排序 C算法为引入代码权重的排序算法。在对测试用 过程如图1所示。 例进行排序后,利用代码权重信息对簇内测试用例进行 瘊1簇2簇3簇4簇 排序,利用本文设计的簇间排序算法,并引入代码单元 1518 16I8"n7T315I6 的权重对簇间测试用例进行排序。 T1 T9 T10 T2 T15 T10 TI T2 T15 T9 4.3评价方式 II111211lT13I12 T14 测试用例排序的目的是尽可能多地检测出被测软 I16 件存在的错误: Rothermel等定义平均错误检测率 测试用例排序结果 (Avcragc Pcrccntagc of Faults Dctcction, APFD )uIF I81713T5 T14116 TF,+TF、+…+TF 图1聚类测试用例排序算法示例 APFD=1 nt 在对簇内和簇间测试用例进行排序时,使用传统的其中,n为测试用例的个数,t为软件错误个数,TF表 测试用例排序算法。已有的研究证明,采用迭代方法对示首个可以检测到软件错误k的测试用例在该执行次 测试用例进行排序的增量贪心算法为简单且高效的测序中所处的位置。APED的值越高,测试用例的排序结 试用例排序算法。因此,本文采用增量贪心算法对簇果能够越早地检测到钦件错误,因而对软件错误的检错 内和簇间的测试用例进行排序。在每次迭代过程中,选能力越强。因此,本文使用APFD作为测试用例排序结 择对未被覆盖的代码单元具有最大代码覆盖信息的测果的总体评价标准。 试用例 为验证算法检测不同软件错误的能力,根据软件错 误被测试用例覆盖的次数定义其难易程度ω。被越少 4实验设计 测试用例检测到的软件错误越困难,被越多测试用例检 4.1数据集 测到的软件错误越简单。 实验中选取 Software Infrastructure Repository(SIR) 中6个经典的回归测试数据集,细节描述如表2所示。实验结果 其中, printtokens schedule tcas tot in0、 replacc个为5 1 APFD实验结果 Siemens数据集。 printtokens为词法分析器, schedule为 在6个SIR数据集上对3个算法进行实验。表3为 优先选择器,tcas为肮空避撞系统, replace为模式匹配测试用例排序结果的APFD平均值 和互换。gzip为广泛使用的Uniⅸx程序 通过对比A和B两种算法的测试用例排序结果,可 表2数据集说明 以验证本文改进的基于聚类测试用例排序算法是否优 于原算法。由表中的APFD值可看出,在6个数据集中, 程序 语句个数软件错误个数测试用例个数 185 4130 本文的算法在5个数据集上都要优于原算法。其中,在 schedule 265( printtokens数据集上A算法稍好于B算法。表屮数据显 tcas 示,改进算法在tas和gzjp数据集上的提高最为明显。 tot info 这是由于tcas数据集的软件锆误数量最大,gzjp数据集 234 29 5542 的代码规模最大。这使得测试用例在排序时的区分程 1359 5 214 度更加明显 对于任何测试用例都不能覆盖的语句,其对测试用 通过对比B和C算法,可以验证引入代码单元的权 例排序的结粜无任何影响;同理,对于没有被任何测试重能否提升测试用例排序算法的效果。由表3中的 14 016,52(5) Computer Engineering and4 pplications计算机工程与应用 APFD数值可以看出,引入代码单元权重的测试用例排集上,A和B两种算法在错误首次检测位詈上:都出现了 序算法明显优于无代码单元权重的算法。在6个数据明显的抖动。在 tot info数据集中第一个最难检测的软 集中,C算法在4个数据集中的表现优于B算法。在tcas件错误上,B算法要优于A算法,在剩余的22个软件错 数据集上,两种算法的效果相当。因为 replace数据集的误:,两种算法的效果相当。在gaip数据集:,B算法 测试用例集相对稳定,所以在该数据集上,C算法的效要明显优于A算法。 果稍弱于B算法。另山表3中数值可知,在 replacc数据 对比B和C两种算法,可以很容易发现C的稳定性 集上,A、B、C三种算法的效果差别不大。 要远远好于B。不过在 printtokens、 schedule和 replace 表3APFD实验结果 三个数据集上,C算法在检测较难的软件错误时花费了 程序 较多的测试用例。在 tot info数据集上,C算法要优于B printtokens0.95160.95010.9742 算法,这种优势在tcas和gzp两个数据集上表现得尤为 schedule 0.9420 明显。 lcas 09217).95230.9523 tot info0.95020.95320.9566 6相关工作 re 0.95840.95980.9596 0.93720.95750.9748 回归测试的测试用例排序问题主要针对的是原有 测试用例集中,可重用测试用例在重新利用时的效率问 通过对比A、B、C三种算法,可以看出C算法对B算题3。针对代码修改导致的部分测试用例失效问 法的改进要高于B算法对A算法的提高因此,代码单题,研究人员提出了测试用例修复这一概念。由于程 元的权重信息在测试用例排序中要比算法的选择更重要。序源码的修改会导致原有测试用例集中的部分测试用 52错误发现位置 例失效叫。针对这部分测试用例,需要对测试用例进行 图2为3个算法在6个数据集上的软件错误首次检修改才能够重新利用。研究工作包括如何衡量程序的 测位置 修改部分发相应测试川例的修改方式5 如图2所示,在同一个数据集上,不同的算法在同 在使用聚类进行测试用例排序的算法中,一般以追 个软件错误上的检测位置不同。整体而言,困难错误求最大化测试用例多样性为目标 Leon等利用 的检测时间要晚于简单错误的检测时间。 代码单元的覆盖信息对测试用例进行聚类分析。Yoo 通过对比A和B两种算法的软件错误首次检测位等在聚类时引入专家知识。通过聚类算法,可以有效 置,可以得知改进的基于聚类测试用例排序算法与原算地减少专家知识的指定关系,从而减少人工工作。实验 法间的差别。总体而言,两种算法在软件错误的首次检结果证明,该方法的排序结果优于传统的机遇代吗覆盖 测位置上效果相当。其中,在 printtokens和 replace数据信息的算法,同时具有铰好的鲁棒性。Ryan等"在对测 集上,两种算法的差异不大。在 schedule数据集上,B算试川例进行聚类时,使川了多种信息作为距离度量,其 法对前两个较难软件错误的检测能力弱于A算法,在剩中包括代码覆盖信息和历史软件错误检测信息等。 余7个软件镨误的检测位置上优于A算法。在tcas数据 在利用代码覆盖信息进行测试用例排序的算法中, rint tokens schedule 800 400 300 A 600 B 300 B 200 4U0 200 0 4567 456 软件错误序号(由难到易) 软件错误序号(由难到易) 软件错误序号(由难到易) 54p A 1400 300 00 200 B C C 150 C 100 400 0 0 0 591317212529 钦件错误序号(由难到易) 钦件错误序号(由难到易) 钦件错误序号(由难到易) 图2错误首次检测位置 蔡景媛,任志磊,胡燕,等:基于聚类算法的测试用例排序 2016,52(5) 15 一般以最大化代码覆盖率为目标n。 Rothermel等首6 Elbaum s, Malisheysky a, Rothermel G Incorporating vary 次提岀测试用例排序问题并给岀其一般性描述,其论文 ing test costs and fault severities into test casc prioriti 比较了贪心类算法在各个代码单元上的实验效果,并证 zation C/International Conference on Software Engineer- 实了代码矍盖信息能够有效地解决测试用例排序问 ing,2001:329-338 题。Ii等根据不同的贪心策略,比较了一系列贪心算 [7 Li Z, Harman M, Hierons R M Search algorithms for regres 法和基于搜索算法的效果。 sion test case prioritization [].IEEE Transactions on Soft- ware Engineering, 2007, 33(4): 225-237 [8 Fang C, Chen 7, Xu B Comparing logic coverage crite- 7结论 ria on test case prioritization[J]. Science China Informa 本文通过对现有的基于聚类的测试用例排序算法 tion sciences,2012,55(12):2826-2840 进行分析提出了改进的基于聚类测试用例排序算法,[9]Yo0s, Harman m, Tonella p, et al. clustering test cases 同时引入代码单元的权重。通过对程序代码的分析,代 to achieve effective and scalable prioritization incorpo 码单元根据测试川例的覆盖次数进行加权。实验结果 rating expert knowledge[C]iNternational Symposium on 表明,改进后的算法优于原算法,提高了测试川例的排 Software Testing and Analysis, Chicago, USA, 2009 序效果,拥有更好的软件错误检测能力。本文的算法能 201-212 够更早地检测到被较少测试用例覆盖的软件错误,因此 Carlson R,DoH, Denton AA clustering approach to 可以使川更少的测试用例检测到所有的软件错误。同 improving test case prioritization: an Industrial case 时,从实验结果可以看出,在较大规馍的数据集上,这种 study [c] /International Conference on Software Mainte nance.20l1:382-391 优势更为明显。在未来工作中,计划研究困难错误的检 [11 Leon D, Podgurski A.A comparison of coverage-based 测代价、测试用例排序问题的目标等内容。 and distribution-based techniques for filtering and prio ritizing test cases[C]proceedings of the IEEE Interna 参考文献: tional Symposium on Software Reliability Enginccring [I]张智佚,陈振宇,徐宝文,等测试用例演化研究进展[J软 2013,22(3):442-456 件学报,2013,24(4):663-674 [12]Do H, Elbaum S, Rothermel Gi Supporting controlled experi [2 Rothermel G, Untch R, Chu C, ct al. Prioritizing test cascs mentation with testing techniques: an infrastructure and for regression testing.IEEE Transactions on Software its patential impact[. Empirical Softwarc Enginccring: Engineering,2001,27(10):929948 An International Journal, 2005,10(4):405-435 [3]陈翔陈继红,鞠小林,等回归测试中的测试用例优先排13] Thomas s w, Hemmati h, Hassan ae,ctal. Static test 序技术述评[]软件学报,2013,24(8):1695-1712 case prioritization using topic models[]. Empirical Soft [4 iang B, Zhang 7, Chan WK, ct al. How well docs test ware Enginccring, 2012, 19(1):182-212 case prioritization integrate with statistical fault localiza- [14 Grechanik M, Xie Q, Fu C Maintaining and evolving GUI tion? []Information and Software Technology, 2012, 54 directed test scripts[C] /International Conference on Sof (7):739-758 ware Engineering, Vancouver, Canada, 2009: 408-418 1 Ma Z, Zhao J, Test case prioritization based on analysis [15 Daniel B, Dig D, Gvero T, et al.ReAssert: a tool for repair- of program structure[C]//Asia-Pacific Software Engineer- ing broken unit tests[C]//International Conference on ing Conference, Beijing, China, 2008: 471-478 Software Engineering, Hawaii, US.A, 2011: 1010-1012