计算机科学 ›› 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: Choice function, Multi-objective optimization, Non-dominated sorting genetic algorithm, Test case priority, Software testing

中图分类号: 

  • 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] 孙刚, 伍江江, 陈浩, 李军, 徐仕远.
一种基于切比雪夫距离的隐式偏好多目标进化算法
Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance
计算机科学, 2022, 49(6): 297-304. https://doi.org/10.11896/jsjkx.210500095
[2] 李浩东, 胡洁, 范勤勤.
基于并行分区搜索的多模态多目标优化及其应用
Multimodal Multi-objective Optimization Based on Parallel Zoning Search and Its Application
计算机科学, 2022, 49(5): 212-220. https://doi.org/10.11896/jsjkx.210300019
[3] 彭冬阳, 王睿, 胡谷雨, 祖家琛, 王田丰.
视频缓存策略中QoE和能量效率的公平联合优化
Fair Joint Optimization of QoE and Energy Efficiency in Caching Strategy for Videos
计算机科学, 2022, 49(4): 312-320. https://doi.org/10.11896/jsjkx.210800027
[4] 滕俊元, 高猛, 郑小萌, 江云松.
噪声可容忍的软件缺陷预测特征选择方法
Noise Tolerable Feature Selection Method for Software Defect Prediction
计算机科学, 2021, 48(12): 131-139. https://doi.org/10.11896/jsjkx.201000168
[5] 王珂, 曲桦, 赵季红.
多域SFC部署中基于强化学习的多目标优化方法
Multi-objective Optimization Method Based on Reinforcement Learning in Multi-domain SFC Deployment
计算机科学, 2021, 48(12): 324-330. https://doi.org/10.11896/jsjkx.201100159
[6] 文进, 张星宇, 沙朝锋, 刘艳君.
基于次模函数最大化的测试用例集约简
Test Suite Reduction via Submodular Function Maximization
计算机科学, 2021, 48(12): 75-84. https://doi.org/10.11896/jsjkx.210300086
[7] 崔国楠, 王立松, 康介祥, 高忠杰, 王辉, 尹伟.
结合多目标优化算法的模糊聚类有效性指标及应用
Fuzzy Clustering Validity Index Combined with Multi-objective Optimization Algorithm and Its Application
计算机科学, 2021, 48(10): 197-203. https://doi.org/10.11896/jsjkx.200900061
[8] 朱汉卿, 马武彬, 周浩浩, 吴亚辉, 黄宏斌.
基于改进多目标进化算法的微服务用户请求分配策略
Microservices User Requests Allocation Strategy Based on Improved Multi-objective Evolutionary Algorithms
计算机科学, 2021, 48(10): 343-350. https://doi.org/10.11896/jsjkx.201100009
[9] 孙昌爱, 张守峰, 朱维忠.
一种基于变异分析的BPEL程序故障定位技术
Mutation Based Fault Localization Technique for BPEL Programs
计算机科学, 2021, 48(1): 301-307. https://doi.org/10.11896/jsjkx.200900051
[10] 张清琪, 刘漫丹.
复杂网络社区发现的多目标五行环优化算法
Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery
计算机科学, 2020, 47(8): 284-290. https://doi.org/10.11896/jsjkx.190700082
[11] 郑友莲, 雷德明, 郑巧仙.
求解高维多目标调度的新型人工蜂群算法
Novel Artificial Bee Colony Algorithm for Solving Many-objective Scheduling
计算机科学, 2020, 47(7): 186-191. https://doi.org/10.11896/jsjkx.190600089
[12] 孙敏, 陈中雄, 叶侨楠.
云环境下基于HEDSM的工作流调度策略
Workflow Scheduling Strategy Based on HEDSM Under Cloud Environment
计算机科学, 2020, 47(6): 252-259. https://doi.org/10.11896/jsjkx.190400047
[13] 赵松辉, 任志磊, 江贺.
软件升级问题的多目标优化方法
Multi-objective Optimization Methods for Software Upgradeability Problem
计算机科学, 2020, 47(6): 16-23. https://doi.org/10.11896/jsjkx.200400027
[14] 王绪亮, 聂铁铮, 唐欣然, 黄菊, 李迪, 闫铭森, 刘畅.
流式数据处理的动态自适应缓存策略研究
Study on Dynamic Adaptive Caching Strategy for Streaming Data Processing
计算机科学, 2020, 47(11): 122-127. https://doi.org/10.11896/jsjkx.190800093
[15] 冯沈峰, 高建华.
基于AHP的回归测试用例优先级排序方法
Test Case Prioritization Method Based on AHP for Regression Testing
计算机科学, 2019, 46(8): 233-238. https://doi.org/10.11896/j.issn.1002-137X.2019.08.038
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!