计算机科学

计算机科学 ›› 2019, Vol. 46 ›› Issue (12): 208-212.doi: 10.11896/jsjkx.181102106

• 软件与数据库技术 • 上一篇    下一篇

一种动态约简的多目标测试用例优先级排序方法

张娜1, 徐海霞1, 包晓安1, 徐璐1, 吴彪2   

  1. (浙江理工大学信息学院 杭州310018)1;
    (山口大学东亚研究科 山口753-8514)2
  • 收稿日期:2018-11-15 出版日期:2019-12-15 发布日期:2019-12-17
  • 通讯作者: 包晓安(1973-),男,硕士,教授,主要研究方向为自适应软件、软件测试与智能信息处理,E-mail:baoxiaoan@zstu.edu.cn。
  • 作者简介:张娜(1977-),女,硕士,副教授,主要研究方向为软件工程、软件测试;徐海霞(1994-),女,硕士,主要研究方向为软件测试、智能信息处理;徐璐(1988-),男,博士,讲师,主要研究方向为智能驾驶;吴彪(1989-),男,博士,主要研究方向为软件工程、软件测试。
  • 基金资助:
    本文受国家自然科学基金项目(61502430,61562015),广西自然科学重点基金项目(2015GXNSFDA139038),浙江理工大学521人才培养计划项目资助。

Multi-objective Test Case Prioritization Method Combined with Dynamic Reduction

ZHANG Na1, XU Hai-xia1, BAO Xiao-an1, XU Lu1, WU Biao2   

  1. (School of Information Science and Technology,Zhejiang Sci-tech University,Hangzhou 310018,China)1;
    (The Graduate School of East Asian Studies,Yamaguchi University,Yamaguchi-shi 753-8514,Japan)2
  • Received:2018-11-15 Online:2019-12-15 Published:2019-12-17

PDF (PC)

766

摘要： 针对蚁群算法在求解MOTCP问题时存在收敛速度慢、易陷入局部最优等缺陷,提出了一种动态约简的在线指导蚁群信息素更新的多目标测试用例优先级排序方法。该方法引入一种动态约简的思想,首先根据各测试用例覆盖需求的情况,对覆盖有相同需求的初始测试用例集进行初次约简。其次,根据测试用例在执行过程中能否检测出错误以及检测出的错误的严重程度来设计一种测试用例失效度的判别方法,在蚁群每一次迭代后均对未检测出错误的测试用例进行二次约简,以减少下一轮迭代时蚁群需要经过的测试用例数,通过两次约简大幅度缩短排序时间。同时,在蚁群的每次迭代过程中,考虑测试用例的重要度、失效度和实际执行时间3个因子对下一轮信息素的影响,设计一种同时在3个影响因子下在线指导更新蚁群信息素的方法,使蚁群能够更快更准确地寻找到下一个测试用例。最后,将该方法、传统蚁群排序方法和多目标优化排序方法分别应用于多个开源软件程序进行实验比较。仿真实验结果表明,所提动态约简的在线更新信息素的优先级排序方法在缺陷检错能力以及有效执行时间等性能指标方面均有较大优势,能更早发现等级较高的错误。

关键词: 测试用例失效度, 测试用例重要度, 动态约简, 实际执行时间, 蚁群算法, 优先级排序

Abstract: Aiming at the shortcomings of ant colony algorithm in solving MOTCP problem,such as slow convergence rate and easy to fall into local optimum,a dynamic multi-objective test case prioritization method for online ant colony pheromone updating was proposed.The method introduces a dynamic reduction idea.Firstly,the initial test case set cove-ring the same requirements is firstly reduced according to the coverage of the requirements by each test case.Secondly,according to whether the test case can detect the error and the severity of the detected error during the execution process,a method for judging the failure degree of the test case is designed.After each iteration of the ant colony,a se-cond reduction is made to the test case in which no error is detected,so as to reduce the number of test cases that the ant colony needs to pass in the next iteration,and the sorting time is greatly reduced by two reductions.At the same time,in the process of each iteration of the ant colony,by considering the influence of the test factor importance degree,the failure degree and the actual execution time on the next round of pheromone,an online ant colony is designed to update the ant colony simultaneously under three influence factors.The pheromone method enables ant colonies to find the next test case faster and more accurately.Finally,this method,traditional ant colony sorting method and multi-objective optimization sorting method were respectively applied to multiple open source software programs for experimental comparison.The simulation results show that the prioritization method of the online update pheromone of the proposed dynamic reduction has great advantages in performance indicators such as defect detection capability and effective execution time,and can detect errors with higher severity at an earlier level.

Key words: Actual execution time, Ant colony algorithm, Dynamic reduction, Priority sorting, Test case failure degree, Test case importance

中图分类号: 

  • TP311
[1]CHEN X,CHEN J H,YAN X L,et al.A Review of Test Case Prioritization Techniques in Regression Testing[J].Journal of Software,2013,24(8):1695-1712.(in Chinese)
陈翔,陈继红,鞠小林,等.回归测试中的测试用例优先排序技术述评[J].软件学报,2013,24(8):1695-1712.
[2]YU H,YANG Y,WANG Y,et al.Priority ordering of regression test cases based on risk analysis[J/OL].Chinese Journal of Computers,2017:1-19[2019-08-08].http://kns.cnki.net/kcms/detail/11.1826.TP.20171228.1931.006.html.(in Chinese)
于海,杨月,王莹,等.基于风险分析的回归测试用例优先级排序[J/OL].计算机学报,2017:1-19[2019-08-08].http://kns.cnki.net/kcms/detail/11.1826.TP.20171228.1931.006.html.
[3]YOO S,HARMAN M.Regression testing minimization,selec- tion and prioritization:a survey[J].Software Testing,Verification and Reliability,2012,22(2):67-102.
[4]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.
[5]ZHANG N,LIN Q X,BAO X A,et al.A Prioritization Method for Combined Test Cases Based on OTT Strategy[J].Computer Engineering and Applications,2018,54(13):41-46,92.(in Chinese)
张娜,林青霞,包晓安,等.基于OTT策略的组合测试用例优先级排序方法[J].计算机工程与应用,2018,54(13):41-46,92.
[6]CHANG L H,MIAO H K,XIAO L.Adaptive Test Case Priority Technology Based on Historical Information[J].Computer Science,2015,42(9):154-158.(in Chinese)
常龙辉,缪淮扣,肖蕾.基于历史信息的自适应测试用例优先级技术[J].计算机科学,2015,42(9):154-158.
[7]SINGH Y,KAUR A,SURI B,Test case prioritization using ant colony optimization [J].ACM SIGSOFT Software Engineering Notes,2010,35(4):1-7.
[8]DORIGO M,STUTZLE T.Ant colony optimization:overview and recent advances[M]//Handbook of metaheuristics.Sprin-ger,Cham,2019:311-351.
[9]OLIVAS F,VALDEZ F,CASTILLO O,et al.Ant colony optimization with dynamic parameter adaptation based on interval type-2 fuzzy logic systems[J].Applied Soft Computing,2017,53:74-87.
[10]GU C H,LI Z,ZHAO R L.ATO-based Test Case Pre-Optimization and Parameter Influence Analysis[J].Computer Science and Technology,2014,8(12):1463-1473.(in Chinese)
顾聪慧,李征,赵瑞莲.基于ACO 的测试用例预优化及参数影响分析[J].计算机科学与探索,2014,8(12):1463-1473.
[11]STUTZLE T,HOOS H.MAX-MIN ant system and local search for the traveling salesman problem [C]//Proceedings of the 1997 IEEE International Conference on Evolutionary Computation.Piscataway,NJ:IEEE,1997:309-314.
[12]DORIGO M,GAMBARDELLA L M.Ant colony system:a cooperative learning approach to the traveling salesman problem [J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.
[13]ZHANG X,YE T,JIN Y.Approximate non-dominated sorting for evolutionary many-objective optimization[J].Information Sciences,2016,369:14-33.
[14]MASHWANI W K,SALHI A,YENIAY O,et al.Hybrid non-dominated sorting genetic algorithm with adaptive operators selection[J].Applied Soft Computing,2017,56:1-18.
[15]XING X,SHANG Y,ZHAO R L,et al.A pheromone update strategy for ant colony algorithm for multi-objective test case prioritization[J].Journal of Computer Applications,2016,36(9):2497-2502.(in Chinese)
邢行,尚颖,赵瑞莲,等.面向多目标测试用例优先排序的蚁群算法信息素更新策略[J].计算机应用,2016,36(9):2497-2502.
[16]REN H L,ZHANG W,LIANG J A.Optimization of test case set based on ant colony algorithm[J].Computer Engineering and Applications,2010,46(29):58-62.(in Chinese)
任洪丽,张伟,梁家安.基于蚁群算法的测试用例集优化方法[J].计算机工程与应用,2010,46(29):58-62.
[17]ZHANG N,YAO L,BAO X A,et al.Multi-objective Optimization Test Case Online Priority Adjustment Strategy[J].Journal of Software,2015,26(10):2451-2464.(in Chinese)
张娜,姚澜,包晓安,等.多目标优化的测试用例优先级在线调整策略[J].软件学报,2015,26(10):2451-2464.
[18]CAI K,CHEN T Y,LI Y,et al.Adaptive Testing of Software Components 1[C]//Acm Symposium on Applied Computing.DBLP,2005.
[1] 刘鑫, 王珺, 宋巧凤, 刘家豪.
一种基于AAE的协同多播主动缓存方案
Collaborative Multicast Proactive Caching Scheme Based on AAE
计算机科学, 2022, 49(9): 260-267. https://doi.org/10.11896/jsjkx.210800019
[2] 高文龙, 周天阳, 朱俊虎, 赵子恒.
基于双向蚁群算法的网络攻击路径发现方法
Network Attack Path Discovery Method Based on Bidirectional Ant Colony Algorithm
计算机科学, 2022, 49(6A): 516-522. https://doi.org/10.11896/jsjkx.210500072
[3] 孙振强, 罗永龙, 郑孝遥, 章海燕.
一种融合用户情感与相似度的智能旅游路径推荐方法
Intelligent Travel Route Recommendation Method Integrating User Emotion and Similarity
计算机科学, 2021, 48(6A): 226-230. https://doi.org/10.11896/jsjkx.200900119
[4] 郭蕊, 芦天亮, 杜彦辉, 周杨, 潘孝勤, 刘晓晨.
基于改进蚁群算法的WSN源位置隐私保护
WSN Source-location Privacy Protection Based on Improved Ant Colony Algorithm
计算机科学, 2020, 47(7): 307-313. https://doi.org/10.11896/jsjkx.200100056
[5] 曹义亲, 武丹, 黄晓生.
基于改进蚁群算法的轨道缺陷图像分类
Track Defect Image Classification Based on Improved Ant Colony Algorithm
计算机科学, 2019, 46(8): 292-297. https://doi.org/10.11896/j.issn.1002-137X.2019.08.048
[6] 郑本立, 李跃辉.
基于改进蚁群算法的SDN网络负载均衡研究
Study on SDN Network Load Balancing Based on IACO
计算机科学, 2019, 46(6A): 291-294.
[7] 李珊珊, 刘福江, 林伟华.
一种基于多起点、多终点的大型火灾救援路径规划方法
Path Planning Method of Large-scale Fire Based on Multiple Starting Points and Multiple Rescue Points
计算机科学, 2019, 46(11A): 134-137.
[8] 李光华, 李俊清, 张亮, 辛衍森, 邓华伟.
一种融合蚁群算法和随机森林的特征选择方法
Feature Selection Method Based on Ant Colony Optimization and Random Forest
计算机科学, 2019, 46(11A): 212-215.
[9] 符晓.
云计算中基于共享机制和群体智能优化算法的任务调度方案
Task Scheduling Scheme Based on Sharing Mechanism and Swarm Intelligence
Optimization Algorithm in Cloud Computing
计算机科学, 2018, 45(6A): 290-294.
[10] 李航, 臧洌, 甘露.
基于蚁群算法的猜测符号执行的路径搜索
Search of Speculative Symbolic Execution Path Based on Ant Colony Algorithm
计算机科学, 2018, 45(6): 145-150. https://doi.org/10.11896/j.issn.1002-137X.2018.06.025
[11] 刘俊, 徐平平, 武贵路, 彭杰.
室内环境下基于最优路径规划的PSO-ACO融合算法
PSO-ACO Fusion Algorithm Based on Optimal Path Planning in Indoor Environment
计算机科学, 2018, 45(11A): 97-100.
[12] 王鑫, 王人福, 覃琴, 蒋华.
云存储副本优化选择策略
Optimization Selection Strategy of Cloud Storage Replica
计算机科学, 2018, 45(10): 300-305. https://doi.org/10.11896／j.issn.1002-137X.2018.10.056
[13] 谢永浩,高嵩峰,代明竹.
基于改进蚁群算法的虚拟网络映射优化
Virtual Network Mapping Optimization Based on Improved Ant Colony Algorithm
计算机科学, 2017, 44(Z6): 312-313. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.071
[14] 曹峰,唐超,张婧.
一种结合二元蚁群和粗糙集的连续属性离散化算法
Algorithm of Continuous Attribute Discretization Based on Binary Ant Colony and Rough Sets
计算机科学, 2017, 44(9): 222-226. https://doi.org/10.11896/j.issn.1002-137X.2017.09.041
[15] 郑巧仙,何国良,李明,唐秋华.
第2类U型装配线平衡问题的双阶段蚁群算法
Two Stage Ant Colony Optimization for Type 2 of U-shaped Assembly Line Balancing Problem
计算机科学, 2017, 44(6): 206-211. https://doi.org/10.11896/j.issn.1002-137X.2017.06.034
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发