基于均衡优化理论的路径覆盖测试数据进化生成

doi:10.3969/j.issn.0372-2112.2020.07.008

电子学报 ›› 2020, Vol. 48 ›› Issue (7): 1303-1310.DOI: 10.3969/j.issn.0372-2112.2020.07.008

基于均衡优化理论的路径覆盖测试数据进化生成

范书平¹, 张岩¹, 马宝英², 万里³, 姚念民⁴, 宋妍¹

1. 牡丹江师范学院计算机与信息技术学院, 黑龙江牡丹江 157011;
2. 牡丹江医学院卫生管理学院, 黑龙江牡丹江 157011;
3. 天津大学智能与计算学部, 天津 300350;
4. 大连理工大学计算机科学与技术学院, 辽宁大连 116024

收稿日期:2019-05-08 修回日期:2019-12-06 出版日期:2020-07-25
- 通讯作者:
- 马宝英
- 作者简介:
- 范书平 男,1977年出生,黑龙江牡丹江人.副教授,CCF会员,主要从事复杂软件的测试数据生成和进化计算研究.E-mail:f8259@163.com;张岩女,1972年出生,辽宁本溪人.教授,CCF会员,主要研究方向为基于搜索的软件工程、进化计算.E-mail:zhangyancumt@126.com;万里男,1994年出生,湖北荆州人.天津大学在读研究生,主要研究软件测试、语音信号处理;姚念民 男,1974年出生,黑龙江大庆人.教授,主要从事基于搜索的软件工程的研究;宋妍女,1977年出生,黑龙江牡丹江人.副教授,主要研究方向为复杂软件的测试数据生成.
- 基金资助:
- 黑龙江省省属高等学校基本科研业务费 (No.1353ZD003，No.2018-KYYWFMY-0104）; 黑龙江省自然科学基金 (No.F2016039）; 牡丹江市科学技术计划项目 (No.Z2018g023）; 牡丹江师范学院科学技术研究项目 (No.YB2019003）; 大连市科技创新项目 (No.2018J12GX045）

Evolutionary Generation of Test Data for Paths Coverage Based on Balance Optimization Theory

FAN Shu-ping¹, ZHANG Yan¹, MA Bao-ying², WAN li³, YAO Nian-min⁴, SONG Yan¹

1. School of Computer and Information Technology, Mudanjiang Normal University, Mudanjiang, Heilongjiang 157011, China;
2. School of Health Management, Mudanjiang Medical University, Mudanjiang, Heilongjiang 157011, China;
3. Department of Intelligence and Computing, Tianjin University, Tianjin 300350, China;
4. School of Computer Science and Technology, Dalian University of Technology, Dalian, Liaoning 116024, China

Received:2019-05-08 Revised:2019-12-06 Online:2020-07-25 Published:2020-07-25

摘要/Abstract

摘要： 为了快速生成覆盖目标路径的测试数据，提出在测试数据进化生成中，利用种群中个体穿越程序各分支的均衡程度调整进化过程.首先，在个体运行被测程序后，统计个体穿越各分支节点真假分支的情况；然后，设计并计算个体穿越程序的均衡度；最后，计算个体对程序均衡度的影响，使对程序均衡度影响大的个体具有较高的适应值，有更多机会参与到后续进化中，有效地提高了测试数据的生成效率.基准程序和工业用例的实验结果表明，与同类方法比较，所提出的方法在生成测试数据的运行时间与成功率方面具有优越性.

关键词: 软件测试, 路径覆盖, 遗传算法, 测试数据, 程序均衡度

Abstract: In order to speed up the generation of test data that covers the target path,the paper makes good use of the balance of individual traversing program to adjust the evolutionary process of generating test data.First,after the individuals run the program,the number of individuals crossing the true and false branches of each branch node is counted.Then,the program balance is designed and calculated.Finally,the influence on the program balance of each individual is calculated.The individual with high influence has a bigger fitness value to have greater chance to participate in subsequent evolution.The proposed method effectively improves the efficiency of test data generation.The experiment results of benchmark programs and industrial cases show that our methods have superiority in running time and success rate of test data generation when compared with similar methods.

Key words: software testing, path coverage, genetic algorithm, test data, program balance

中图分类号:

TP311

范书平, 张岩, 马宝英, 万里, 姚念民, 宋妍. 基于均衡优化理论的路径覆盖测试数据进化生成[J]. 电子学报, 2020, 48(7): 1303-1310.

FAN Shu-ping, ZHANG Yan, MA Bao-ying, WAN li, YAO Nian-min, SONG Yan. Evolutionary Generation of Test Data for Paths Coverage Based on Balance Optimization Theory[J]. Acta Electronica Sinica, 2020, 48(7): 1303-1310.

参考文献

[1] 靳蓉,姜淑娟,张红昌.一种新的数据流覆盖测试数据进化生成方法[J].小型微型计算机系统,2012,33(4):722-726. JIN Rong,JIANG Shu-juan,ZHANG Hong-chang.Novel evolutionary generation approach to test data for data-flow coverage[J].Journal of Chinese Computer Systems,2012,33(4):722-726.(in Chinese)
[2] JIANG S J,SHIN J J,ZHANG Y M,et al.Automatic test data generation based on reduced adaptive particle swarm optimization algorithm[J].Neurocomputing,2015,158:109-116.
[3] JIA Ya-hui,CHEN Wei-neng,ZHANG Jun,et al.Generating software test data by particle swarm optimization[A].Proceedings of 10th International Conference on Simulated Evolution and Learning[C].Springer International Publishing Switzerland,2014.37-47.
[4] 薛猛,姜淑娟,张争光,等.一种基于Kalman滤波和粒子群优化的测试数据生成方法[J].电子学报,2017,45(10):2473-2483. XUE Meng,JIANG Shu-juan,ZHANG Zheng-guang,et al.A test data generation method based on Kalman filter and particle swarm optimization algorithm[J].Acta Electronica Sinica,2017,45(10):2473-2483.(in Chinese)
[5] DAHIYA S S,CHHABRA J K,Kumar S.Application of artificial bee colony algorithm to software testing[A].21st Australian Software Engineering Conference[C].Auckland,New Zealand:ASWEC,2010.149-154.
[6] ADISRIKANTH KULKARNI N J,NAVEEN K V,et al.Test case optimization using artificial bee colony algorithm[J].Communications in Computer & Information Science,2011,192:570-579.
[7] MAO C,XIAO L,YU X,et al.Adapting ant colony optimization to generate test data for software structural testing[J].Swarm & Evolutionary Computation,2015,20:23-36.
[8] SHAHBAZI A,MILLER J.Black-box string test case generation through a multi-objective optimization[J].IEEE Transactions on Software Engineering,2016,42(4):361-378.
[9] MOHI-ALDEEN S M,MOHAMAD R,DERIS S.Application of negative selection algorithm(NSA) for test data generation of path testing[J].Applied Soft Computing,2016,49:1118-1128.
[10] MAO Y H,LIN R Q.Application of dynamic program slicing technique in test data generation[J].Procedia Computer Science,2017,111:355-360.
[11] MEI J,WANG S Y.An improved genetic algorithm for test cases generation oriented paths[J].Chinese Journal of Electronics,2014,23(3):494-498.
[12] 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.
[13] 夏春艳,张岩,宋丽.基于节点概率的路径覆盖测试数据进化生成[J].软件学报,2016,27(4):802-813. XIA Chun-yan,ZHANG Yan,SONG Li.Evolutionary generation of test data for paths coverage based on node probability[J].Journal of Software,2016,27(4):802-813.(in Chinese)
[14] McMinn P.Evolutionary search for test data in the presence of state behavior[D].University of Sheffield,England,2005.
[15] HARMAN M,MCMINN P.A theoretical and empirical study of search-based testing:local,global,and hybrid search[J].IEEE Transactions on Software Engineering,2010,36(2):226-247.
[16] DEEPAK G,PALLVI G.Basis path testing using SGC&HGA with ExLB fitness function[A].International Conference on Eco-friendly Computing and Communication Systems[C].Procedia Computer Science,2015.593-602.
[17] 张岩,巩敦卫.基于稀有数据扑捉的路径覆盖测试数据进化生成方法[J].计算机学报,2013,36(12):2429-2439. ZHANG Yan,GONG Dun-wei.Evolutionary generation of test data for paths coverage based on scarce data capturing[J].Chinese Journal of Computers,2013,36(12):2429-2439.(in Chinese)
[18] 王亚鑫,杨大成.一种基于C-RAN的BBU负载均衡优化算法[J].北京邮电大学学报,2018,41(5):115-119. WANG Ya-xin,YANG Da-cheng.An optimization algorithm for BBU load balancing in C-RAN[J].Journal of Beijing University of Posts and Telecommunications,2018,41(5):115-119.(in Chinese)
[19] KAEWYOTHA J,SONGPAN W.Finding the critical path with loop structure for a basis path testing using genetic algorithm[J].Advances in Intelligent Systems and Computing.2015,361:41-52.
[20] 夏辉,宋昕,王理.基于Z路径覆盖的测试用例自动生成技术研究[J].现代电子技术,2006,(6):92-94. XIA Hui,SONG Xin,WANG Li.Research of test case auto generating based on Z path coverage[J].Modem Electronics Technique,2006,(6):92-94.(in Chinese)
[21] 巩敦卫,张岩.一种新的多路径覆盖测试数据进化生成方法[J].电子学报,2010,38(6):1299-1304. GONG Dun-wei,ZHANG Yan.Novel evolutionary generation approach to test data for multiple paths coverage[J].Acta Electronica Sinica,2010,38(6):1299-1304.(in Chinese)

基于均衡优化理论的路径覆盖测试数据进化生成

Evolutionary Generation of Test Data for Paths Coverage Based on Balance Optimization Theory

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李志博, 李清宝, 兰明敬, 孙剑帆. 基于镜像选择序优化的MART算法[J]. 电子学报, 2022, 50(2): 314-325.
[2]	钱忠胜, 俞情媛, 宋涛, 朱懿敏, 祝洁, 赵畅. 基于支持向量机回归模型的测试用例生成与重用[J]. 电子学报, 2021, 49(7): 1386-1391.
[3]	刘焕淋, 黄美娜, 陈勇, 杨健, 黄冰川, 张彤. 基于NOMA技术的PLC-VLC用户配对和子载波分配方法[J]. 电子学报, 2021, 49(10): 1952-1959.
[4]	金泽芬芬, 侯志强, 余旺盛, 王鑫, 寇人可. 基于量子遗传算法的视觉目标跟踪[J]. 电子学报, 2020, 48(8): 1493-1501.
[5]	廖伟志, 夏小云, 贾小军. 基于蚁群算法的多路径覆盖测试数据生成[J]. 电子学报, 2020, 48(7): 1330-1342.
[6]	薛河, 苟思育, 倪陈强. 紧凑拉伸试样参比电位差接线点布局的优化方法[J]. 电子学报, 2020, 48(7): 1396-1402.
[7]	郭广颂, 陈良骥, 文振华, 张勇. 求解高维混合指标优化问题的交互式进化计算[J]. 电子学报, 2020, 48(7): 1361-1368.
[8]	徐超群, 易忠, 孟立飞, 刘超波, 黄魁. 基于遗传算法的卫星磁模型研究[J]. 电子学报, 2020, 48(6): 1108-1112.
[9]	唐香琼, 黄春跃, 梁颖, 匡兵, 赵胜军. 基于再流焊冷却过程应力分析的板极组件BGA焊点参数优化[J]. 电子学报, 2020, 48(6): 1117-1123.
[10]	祁志卫, 王笳辉, 岳昆, 乔少杰, 李劲. 图嵌入方法与应用:研究综述[J]. 电子学报, 2020, 48(4): 808-818.
[11]	田甜, 巩敦卫. 并发程序变异测试研究综述[J]. 电子学报, 2020, 48(11): 2267-2277.
[12]	梁颖, 黄春跃, 邹涯梅, 高超, 匡兵. 基于扭转载荷的微尺度CSP焊点应力应变分析与优化[J]. 电子学报, 2020, 48(10): 2033-2040.
[13]	段毅, 谭贤四, 曲智国, 王红. 基于分支定界法的相控阵雷达事件调度算法[J]. 电子学报, 2019, 47(6): 1309-1315.
[14]	李军华, 黎明, 陈昊, 伍家驹. 正态随机噪声环境下遗传算法的动态适应度评价[J]. 电子学报, 2019, 47(3): 649-656.
[15]	王建培, 黄春跃, 梁颖, 邵良滨. 基于回归分析和遗传算法的BGA焊点功率载荷热应力分析与优化[J]. 电子学报, 2019, 47(3): 734-740.