基于历史数据和多目标优化的测试用例排序方法

doi:10.11772/j.issn.1001-9081.2021112015

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (1): 221-226.DOI: 10.11772/j.issn.1001-9081.2021112015

基于历史数据和多目标优化的测试用例排序方法

李兴佳, 杨秋辉, 洪玫, 潘春霞, 刘瑞航

四川大学计算机学院，成都 610065

收稿日期:2021-11-28 修回日期:2022-05-01 发布日期:2022-05-24
作者简介:李兴佳（1997—），男，河北石家庄人，硕士研究生，主要研究方向：软件质量保证与测试；杨秋辉（1970—），女，山东青岛人，副教授，博士，主要研究方向：软件自动化测试、软件项目管理；洪玫（1963—），女，浙江舟山人，教授，硕士，CCF高级会员，主要研究方向：软件分析与测试 email：hongmei@scu.edu.cn；潘春霞（1995—），女，四川内江人，硕士，主要研究方向：软件质量保证与测试；刘瑞航（1998—），男，黑龙江哈尔滨人，硕士研究生，主要研究方向：移动应用质量保证与测试；

Test case prioritization approach based on historical data and multi-objective optimization

LI Xingjia, YANG Qiuhui, HONG Mei, PAN Chunxia, LIU Ruihang

College of Computer Science， Sichuan University， Chengdu Sichuan 610065， China

Received:2021-11-28 Revised:2022-05-01 Online:2022-05-24
Contact: HONG Mei， born in 1963， M. S.， professor. Her research interests include software analysis and testing.
About author:LI Xingjia， born in 1997， M. S. candidate. His research interests include software quality assurance and testing；YANG Qiuhui， born in 1970， Ph. D.， associate professor. Her research interests include software automatic testing， software project management；PAN Chunxia， born in 1995， M. S. Her research interests include software quality assurance and testing；LIU Ruihang， born in 1998， M. S. candidate. His research interests include mobile application quality assurance and testing；

摘要/Abstract

摘要： 针对如何提高测试用例序列的揭错效率和回归测试效益问题，提出一种基于历史数据和多目标优化的测试用例排序方法。首先，根据测试用例的文本主题相似性和代码覆盖相似性对测试用例集进行聚类，并根据历史执行信息对测试用例间的执行失败关系进行关联规则挖掘，从而为后续过程做准备；然后，利用多目标优化算法对每个类簇内的测试用例进行排序，在此之后生成最终排序序列，使相似的测试用例分隔开；最后，利用测试用例间的关联规则，动态调整测试用例执行次序，从而使可能失败的测试用例优先执行，以进一步提高缺陷检测效率。与随机排序方法、基于聚类的排序方法、基于主题模型的排序方法、基于关联规则和多目标优化的排序方法相比，所提方法的平均故障检测率（APFD）平均值分别提高了12.59%、5.98%、3.01%和2.95%，基于成本的平均故障检测率（APFDc）平均值分别提高了17.17%、5.04%、5.08%和8.21%。实验结果表明，所提方法能有效提高回归测试效益。

关键词: 回归测试, 测试用例聚类, 关联规则挖掘, 测试用例排序, 多目标优化

Abstract: To improve the error detection efficiency and the benefit of regression testing of test case sequence， a test case prioritization approach based on historical data and multi-objective optimization was proposed. Firstly， the test case set was clustered according to the text topic similarity and code coverage similarity of test cases， and the association rules were mined for execution failure relationships between test cases according to the historical execution information， thereby preparing for the subsequent process. Then， the multi-objective optimization algorithm was used to sort the test cases in each cluster. After that， the final sorting sequence was generated to separate the similar test cases. Finally， the association rules between test cases were used to dynamically adjust the execution order of test cases， so that the test cases that may fail were executed with priority， so as to further improve the efficiency of defect detection. Compared with random search approach， the approach based on clustering， the approach based on topic model， the approach based on association rules and multi-objective optimization， the proposed approach has the average value of Average Percentage of Faults Detected （APFD） increased by 12.59%， 5.98%， 3.01% and 2.95%， respectively， and has the average value of APFD cost-cognizant （APFDc） increased by 17.17%， 5.04%， 5.08% and 8.21%， respectively. Experimental results show that the proposed approach can improve the benefit of regression testing effectively.

Key words: regression test, test case clustering, association rule mining, test case prioritization, multi-objective optimization

中图分类号:

TP311.5

李兴佳, 杨秋辉, 洪玫, 潘春霞, 刘瑞航. 基于历史数据和多目标优化的测试用例排序方法[J]. 计算机应用, 2023, 43(1): 221-226.

LI Xingjia, YANG Qiuhui, HONG Mei, PAN Chunxia, LIU Ruihang. Test case prioritization approach based on historical data and multi-objective optimization[J]. Journal of Computer Applications, 2023, 43(1): 221-226.

参考文献

1 LEONG C， SINGH A， PAPADAKIS M， et al. Assessing transition-based test selection algorithms at Google［C］// Proceedings of the IEEE/ACM 41st International Conference on Software Engineering： Software Engineering in Practice. Piscataway： IEEE， 2019： 101-110. 10.1109/icse-seip.2019.00019
2 YOO S， HARMAN M. Regression testing minimization， selection and prioritization： a survey［J］. Software Testing， Verification and Reliability， 2012， 22（2）： 67-120. 10.1002/stv.430
3 LUO Q， MORAN K， ZHANG L M， et al. How do static and dynamic test case prioritization techniques perform on modern software systems？ an extensive study on GitHub projects［J］. IEEE Transactions on Software Engineering， 2019， 45（11）： 1054-1080. 10.1109/tse.2018.2822270
4 XIAO L， MIAO H K， ZHUANG W W， et al. Applying assemble clustering algorithm and fault prediction to test case prioritization［C］// Proceedings of the 2016 International Conference on Software Analysis， Testing and Evolution. Piscataway： IEEE， 2016：108-116. 10.1109/sate.2016.25
5 NAJAFI A， SHANG W Y， RIGBY P C. Improving test effectiveness using test executions history： an industrial experience report［C］// Proceedings of the IEEE/ACM 41st International Conference on Software Engineering： Software Engineering in Practice. Piscataway： IEEE， 2019： 213-222. 10.1109/icse-seip.2019.00031
6 NOOR T B， HEMMATI H. A similarity-based approach for test case prioritization using historical failure data［C］// Proceedings of the IEEE 26th International Symposium on Software Reliability Engineering. Piscataway： IEEE， 2015：58-68. 10.1109/issre.2015.7381799
7 BUSJAEGER B， XIE T. Learning for test prioritization： an industrial case study［C］// Proceedings of the 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering. New York： ACM， 2016： 975-980. 10.1145/2950290.2983954
8 DE OLIVEIRA NETO F G， AHMAD A， LEIFLER O， et al. Improving continuous integration with similarity-based test case selection［C］// Proceedings of the ACM/IEEE 13th International Workshop on Automation of Software Test. New York： ACM， 2018： 39-45. 10.1145/3194733.3194744
9 CARLSON R， DO H， DENTON A. A clustering approach to improving test case prioritization： an industrial case study［C］// Proceedings of the 27th IEEE International Conference on Software Maintenance. Piscataway： IEEE， 2011： 382-391. 10.1109/icsm.2011.6080805
10 THOMAS S W， HEMMATI H， HASSAN A E， et al. Static test case prioritization using topic models［J］. Empirical Software Engineering， 2014， 19（1）： 182-212. 10.1007/s10664-012-9219-7
11 PRADHAN D， WANG S， ALI S， et al. REMAP： using rule mining and multi-objective search for dynamic test case prioritization［C］// Proceedings of the IEEE 11th International Conference on Software Testing， Verification and Validation. Piscataway： IEEE， 2018： 46-57. 10.1109/icst.2018.00015
12 HAO D， ZHANG L M， ZHANG L， et al. A unified test case prioritization approach［J］. ACM Transactions on Software Engineering and Methodology， 2015， 24（2）： No.10. 10.1145/2685614
13 MEI H， HAO D， ZHANG L M， et al. A static approach to prioritizing JUnit test cases［J］. IEEE Transactions on Software Engineering， 2012， 38（6）： 1258-1275. 10.1109/tse.2011.106
14 JIANG B， ZHANG Z Y， CHAN W K， et al. Adaptive random test case prioritization［C］// Proceedings of the 2009 IEEE/ACM International Conference on Automated Software Engineering. Piscataway： IEEE， 2009： 233-244. 10.1109/ase.2009.77
15 ANDERSON J， SALEM S， DO H. Improving the effectiveness of test suite through mining historical data［C］// Proceedings of the 11th Working Conference on Mining Software Repositories. New York： ACM， 2014： 142-151. 10.1145/2597073.2597084
16 ZHU Y C， SHIHAB E， RIGBY P C. Test re-prioritization in continuous testing environments［C］// Proceedings of the 2018 IEEE International Conference on Software Maintenance and Evolution. Piscataway： IEEE， 2018： 69-79. 10.1109/icsme.2018.00016
17 李昡熠，周鋆. 基于频繁项挖掘的贝叶斯网络结构学习算法BNSL-FIM［J］. 计算机应用， 2021， 41（12）： 3475-3479. LI X Y， ZHOU Y. BNSL-FIM： Bayesian network structure learning algorithm based on frequent item mining［J］. Journal of Computer Applications， 2021， 41（12）： 3475-3479.
18 EPITROPAKIS M G， YOO S， HARMAN M， et al. Empirical evaluation of Pareto efficient multi-objective regression test case prioritization［C］// Proceedings of the 2015 International Symposium on Software Testing and Analysis. New York： ACM， 2015： 234-245. 10.1145/2771783.2771788
19 李二超，毛玉燕. 基于空间收缩技术的约束多目标进化算法［J］. 计算机应用， 2021， 41（12）： 3419-3425. LI E C， MAO Y Y. Constrained multi-objective evolutionary algorithm based on space shrinking technique［J］. Journal of Computer Applications， 2021， 41（12）： 3419-3425.
20 DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGA-II［J］. IEEE Transactions on Evolutionary Computation， 2002， 6（2）： 182-197. 10.1109/4235.996017
21 DO H， ELBAUM S， ROTHERMEL G. Supporting controlled experimentation with testing techniques： an infrastructure and its potential impact［J］. Empirical Software Engineering， 2005， 10（4）： 405-435. 10.1007/s10664-005-3861-2
22 LIANG J J， ELBAUM S， ROTHERMEL G. Redefining prioritization： continuous prioritization for continuous integration［C］// Proceedings of the ACM/IEEE 40th International Conference on Software Engineering. New York： ACM， 2018： 688-698. 10.1145/3180155.3180213

[1]	徐赛娟, 裴镇宇, 林佳炜, 刘耿耿. 基于多阶段搜索的约束多目标进化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2345-2351.
[2]	金苍宏, 邵育华, 何琴芳. 基于自适应群组重排的长尾推荐模型[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1122-1128.
[3]	马艳芳, 张文, 李宗敏, 闫芳, 郭凌云. 考虑负效应的垃圾回收两级选址‒路径模型与算法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 289-298.
[4]	刘美英, 杨秋辉, 王潇, 蔡创. 基于提交排序和预测模型的测试套件选择方法[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2534-2539.
[5]	张翔宇, 杨阳, 冯国徽, 秦川. 基于多目标优化的加密图像可逆信息隐藏[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1716-1723.
[6]	张金泉, 徐寿伟, 李信诚, 王重洋, 徐景芝. 基于正交自适应鲸鱼优化的云计算任务调度[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1516-1523.
[7]	张京, 朱爱红. 基于遗传算法和粒子群优化的列车自动驾驶速度曲线优化方法[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 599-605.
[8]	郭潇, 李春山, 张宇跃, 初佃辉. 基于自适应多目标强化学习的服务集成方法[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3500-3505.
[9]	罗明宇, 骆晓萌, 朱文敏, 张磊, 范秀敏. 船舶狭小空间虚拟人维修姿态建模技术[J]. 计算机应用, 2021, 41(8): 2466-2472.
[10]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[11]	张祥飞, 鲁宇明, 张平生. 基于协同进化的约束多目标优化算法[J]. 计算机应用, 2021, 41(7): 2012-2018.
[12]	马晓航, 廖灵霞, 李智, 秦斌, 赵涵捷. 基于动态混合超时的软件定义网络多目标优化[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3658-3665.
[13]	乔钢柱, 王瑞, 孙超利. 基于分解的高维多目标改进进化算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3097-3103.
[14]	李二超, 李康伟. 基于最小距离和聚合策略的分解多目标进化算法[J]. 计算机应用, 2021, 41(1): 22-28.
[15]	李二超, 杨蓉蓉. 基于自适应反向学习的多目标分布估计算法[J]. 计算机应用, 2021, 41(1): 15-21.

基于历史数据和多目标优化的测试用例排序方法

Test case prioritization approach based on historical data and multi-objective optimization

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics