计算机科学 ›› 2020, Vol. 47 ›› Issue (6): 38-43.doi: 10.11896/jsjkx.191100113

• 智能软件工程 • 上一篇    下一篇

基于多目标优化的测试用例优先级排序方法

夏春艳1, 王兴亚2, 张岩1   

  1. 1 牡丹江师范学院计算机与信息技术学院 黑龙江 牡丹江157011
    2 南京大学计算机软件新技术国家重点实验室 南京210023
  • 收稿日期:2019-11-15 出版日期:2020-06-15 发布日期:2020-06-10
  • 通讯作者: 王兴亚(xingyawang@nju.edu.com)
  • 作者简介:xia-chun-yan@163.com
  • 基金资助:
    黑龙江省教育厅基本科研业务费(1353MSYYB005);牡丹江师范学院科学技术研究(2018-KYYWF-0419)

Test Case Prioritization Based on Multi-objective Optimization

XIA Chun-yan1, WANG Xing-ya2, ZHANG Yan1   

  1. 1 School of Computer and Information Technology,Mudanjiang Normal University,Mudanjiang,Heilongjiang 157011,China
    2 State Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210023,China
  • Received:2019-11-15 Online:2020-06-15 Published:2020-06-10
  • About author:XIA Chun-yan,born in 1980,postgra-duate,associate professor,is a member of China Computer Federation.Her main research interests include search-based software engineering,information processing and data mining.
    WANG Xing-ya,born in 1990,Ph.D,associate professor,is a member of China Computer Federation.Her main research interests include blockchain analysis and testing,software defect location.
  • Supported by:
    This work was supported by Science Research Project of Heilongjiang Provincial Education Department (1353MSYYB005) and Research Project of Mudanjiang Normal University (2018-KYYWF-0419)

摘要: 回归测试是软件测试中使用最频繁、成本最昂贵的测试方法。测试用例优先级排序是一种能够有效降低回归测试成本的方法,其目的是通过优先执行高级别的测试用例来达到提升软件故障检测的能力。文中提出了一种基于多目标优化的测试用例优先级排序方法,该方法在遗传算法的个体评价机制中融入了选择函数,设计了合理的编码方式以及合适的选择、交叉和变异策略,以故障检测率、语句覆盖率和有效执行时间为优化目标,采用非支配排序遗传算法对测试用例优先级排序。基于4个基准程序和4个工业程序的实验结果表明:与其他方法相比,所提方法能够提高软件测试的有效性。

关键词: 软件测试, 测试用例优先级, 多目标优化, 非支配排序遗传算法, 选择函数

Abstract: Regression testing is the most frequently used and expensive testing method in software testing.Test case prioritization is an effective way to reduce the cost of regression testing.Its purpose is to improve the ability of software fault detection by prio-ritizing the execution of high-level test cases.In this paper,a method of test case prioritization based on multi-objective optimization is proposed.The method integrates choice function into individual evaluation mechanisms of genetic algorithm.By designing a reasonable coding method and appropriate selection,crossover and mutation strategies,taking fault detection rate,sentence covera-ge rate and effective execution time as optimization objectives,non-dominated sorting genetic algorithm is used to optimize test case sort.The experimental results based on four benchmark programs and four industrial programs show that the proposed method can improve the effectiveness of software testing compared with other methods.

Key words: Software testing, Test case priority, Multi-objective optimization, Non-dominated sorting genetic algorithm, Choice function

中图分类号: 

  • TP311
[1]TIAN T,GONG D W.Evolutionary generation approach of test data for multiple paths coverage of message-passing parallel programs[J].Chinese Journal of Electronics,2014,23(2):291-296.
[2]SAHIN O,AKAY B.Comparisons of metaheuristic algorithms and fitness functions on software test data generation[J].Applied Soft Computing,2016,49:1202-1214.
[3]PRADHAN D,WANG S,ALI S,et al.Employing rule mining and multi-objective search for dynamic test case prioritization[J].The Journal of Systems and Software,2019,153:86-104.
[4]WONG W,HORGAN J,LONDON S,et al.A study of effective regression testing in practice[C]//Proceedings of the Eighth International Symposium on Software Reliability Engineering.New Mexico,USA,1997,11:264-274.
[5]KAVITHA R,SURESHKUMAR N.Test case prioritization for regression testing based on severity of fault[J].International Journal on Computer Science & Engineering,2010,2(5):1462-1466.
[6]NAYAK S,KUMAR C,TRIPATHI S.Enhancing efficiency of the test case Prioritization technique by improving the rate of fault detection[J].Arabian Journal for Science & Engineering,2017,42(11):1-17.
[7]WALCOTT K R,SOFFA M L,KAPFHAMMER G M,et al.Time-Aware test suite prioritization[C]//Pollock L,ed.Proc.of the Int’l Symp.on Software Testing and Analysis.Portland:ACM Press,2006:1-12.
[8]SRIKANTH H,WILLIAMS L,OSBORNE J.System test case prioritization of new and regression test cases[C]//Proceedings of the International Symposium on Empirical Software Engineering.Noosa Heads,Australia,2005:64-73.
[9]CHEN X,CHEN J H,JU X L,et al.Survey of test case prioritization techniques for regression testing[J].Journal of Software,2013,24(8):1695-1712.
[10]MICHAEL R G,DAVID S J.Computers and intractability:a guide to the theory of NP-completeness[M].WH Free.Co,San Fr,1979.
[11]MAHMOOD H,HOSAIN S.Improving test case prioritization based on practical priority factors[C]//Proceedings of IEEE International Conference on Software Engineering and Service Science.Beijing:IEEE Press,2017:899-902.
[12]CHEN Y F,LI Z,ZHAO R L.Applying PSO to multi-objective test cases prioritization[J].Computer Science,2014,41(5):72-77.
[13]MUKHERJEE R,PATNAIK K S.A survey on different approaches for software test case prioritization[J].Journal of King Saud University Computer and Information Sciences,2018:1319-1578.
[14]COWLING P,KENDALL G,SOUBEIGA E.A hyperheuristic approach to scheduling a sales summit[C]//Practice and Theory of Automated Timetabling.2001:176-190.
[15]KENDALL G,SOUBEIGA E,COWLING P.Choice function and random hyperheuristics[C]//Asia-Pacific Conference on Simulated Evolution and Learning.Springer,2002:667-671.
[16]MAASHI M,ÖZCAN E,KENDALL G.A multi-objective hyper-heuristic based on choice function[J].Expert Syst.Appl.,2014,41(9):4475-4493.
[17]郑金华.多目标进化算法及其应用[M].北京:科学出版社,2007:2-8.
[18]ROTHEMEL G,UNTCH R H,CHU C,et al.Prioritiz-ing test cases for regression testing[J].IEEE Transactions on Software Engineering,2001,27(10):929-948.
[19]SUN C A,GUO X L,ZHANG X Y,et al.A Data Flow Analysis Based Redundant Mutants Identification Technique[J].Chinese Journal of Computers,2019,42(1):44-60.
[20]ZHENG Y,WANG Z,FANG X,et al.Localizing multiple software faults based on evolution algorithm[J].The Journal of Systems and Software,2018,139:107-123.
[21]YOO S,HARMAN M,CLARK D.Fault localization prioritization:comparing information theoretic and coverage based approaches[J].ACM Transactions on Software Engineering and Methodology,2013,22(3):1049-1078.
[1] 孙昌爱, 张守峰, 朱维忠. 一种基于变异分析的BPEL程序故障定位技术[J]. 计算机科学, 2021, 48(1): 301-307.
[2] 张清琪, 刘漫丹. 复杂网络社区发现的多目标五行环优化算法[J]. 计算机科学, 2020, 47(8): 284-290.
[3] 郑友莲, 雷德明, 郑巧仙. 求解高维多目标调度的新型人工蜂群算法[J]. 计算机科学, 2020, 47(7): 186-191.
[4] 赵松辉, 任志磊, 江贺. 软件升级问题的多目标优化方法[J]. 计算机科学, 2020, 47(6): 16-23.
[5] 孙敏, 陈中雄, 叶侨楠. 云环境下基于HEDSM的工作流调度策略[J]. 计算机科学, 2020, 47(6): 252-259.
[6] 王绪亮, 聂铁铮, 唐欣然, 黄菊, 李迪, 闫铭森, 刘畅. 流式数据处理的动态自适应缓存策略研究[J]. 计算机科学, 2020, 47(11): 122-127.
[7] 冯沈峰, 高建华. 基于AHP的回归测试用例优先级排序方法[J]. 计算机科学, 2019, 46(8): 233-238.
[8] 董明刚,刘宝,敬超. 模糊自适应排序变异多目标差分进化算法[J]. 计算机科学, 2019, 46(7): 224-232.
[9] 薄莉莉, 姜淑娟, 张艳梅, 王兴亚, 于巧. 并发缺陷检测技术研究进展[J]. 计算机科学, 2019, 46(5): 13-20.
[10] 李志博,李清宝,于磊,侯雪梅. 基于划分的自适应随机测试综述[J]. 计算机科学, 2019, 46(3): 19-29.
[11] 汪晨欣, 杨家海, 庄奕, 罗念龙. 未来网络试验设施的节点资源调度算法[J]. 计算机科学, 2019, 46(12): 95-100.
[12] 赵云涛, 谌竟成, 李维刚. 融合自适应差分进化机制的多目标灰狼优化算法[J]. 计算机科学, 2019, 46(11A): 83-88.
[13] 王蓁蓁, 刘嘉. 基于校正因子的随机TBFL方法[J]. 计算机科学, 2019, 46(11): 161-167.
[14] 包晓安, 熊子健, 张唯, 吴彪, 张娜. 一种基于改进遗传算法的路径测试用例生成方法[J]. 计算机科学, 2018, 45(8): 174-178.
[15] 马元锋,李昂儒,余慧敏,潘晓英. 基于动态拥挤距离的混合多目标免疫优化算法[J]. 计算机科学, 2018, 45(6A): 63-68.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .