基于否定选择遗传算法的路径覆盖测试数据生成

doi:10.3969/j.issn.0372-2112.2019.12.024

电子学报 ›› 2019, Vol. 47 ›› Issue (12): 2630-2638.DOI: 10.3969/j.issn.0372-2112.2019.12.024

基于否定选择遗传算法的路径覆盖测试数据生成

夏春艳¹, 张岩¹, 万里², 宋妍¹, 肖楠¹, 郭冰¹

1. 牡丹江师范学院计算机与信息技术学院, 黑龙江牡丹江 157012;
2. 天津大学智能与计算学部, 天津 300350

收稿日期:2018-08-20 修回日期:2018-10-18 出版日期:2019-12-25
- 通讯作者:
- 张岩
- 作者简介:
- 夏春艳 女,1980年3月出生,黑龙江桦川人.副教授,CCF会员.2007年毕业于长春理工大学计算机应用技术专业,获得硕士学位.现为牡丹江师范学院教师,主要从事软件工程、数据挖掘等方面的研究工作.E-mail:xia-chun-yan@163.com;万里男,1994年4月出生,湖北松滋人.2018年进入天津大学智能与计算学部.现为硕士研究生,主要从事人工智能、软件工程等方面的有关研究.E-mail:1151843852@qq.com;宋妍女,1977年出生,黑龙江牡丹江人.现为牡丹江师范学院教师,硕士,研究方向为软件工程、大数据技术.;肖楠女,1983年出生,黑龙江牡丹江人.现为牡丹江师范学院教师,硕士,研究方向为基于搜索的软件工程.;郭冰女,2000年出生,河北省唐山市人.现为牡丹江师范学院学生,本科.研究方向为基于搜索的软件工程.
- 基金资助:
- 黑龙江省教育厅基本科研业务费 (No.1353MSYYB005）; 牡丹江师范学院科学技术研究 (No.YB2018004，No.GP201602）; 黑龙江省自然科学基金 (No.F2016039）; 黑龙江省教育厅 (No.1353ZD003，No.1353MSYYB007，No.1353MSYQN006）; 牡丹江市科技计划 (No.Z2016s0027，No.Z2018s073）; 牡丹江师范学院大学生创新训练项目 (No.201910233006）

Test Data Generation of Path Coverage Based on Negative Selection Genetic Algorithm

XIA Chun-yan¹, ZHANG Yan¹, WAN Li², SONG Yan¹, XIAO Nan¹, GUO Bing¹

1. School of Computer and Information Technology, Mudanjiang Normal University, Mudanjiang, Heilongjiang 157012, China;
2. Tianjin University Division of Intelligence and Computing, Tianjin University, Tianjin 300350, China

Received:2018-08-20 Revised:2018-10-18 Online:2019-12-25 Published:2019-12-25
- Corresponding author:
- ZHANG Ya
- Supported by:
- Fundamental Research Funds of Education Department of Heilongjiang Province (No.1353MSYYB005); Science and Technology Research Program of Mudanjiang Normal University (No.YB2018004, No.GP201602); Natural Science Foundation of Heilongjiang Province, China (No.F2016039); Education Department of Heilongjiang Province (No.1353ZD003, No.1353MSYYB007, No.1353MSYQN006); Project of Science and Technology Plan of Mudanjiang (No.Z2016s0027, No.Z2018s073); Innovative Training Program for College Students in Mudanjiang Normal University (No.201910233006)

摘要/Abstract

摘要： 路径覆盖是软件测试领域重要的测试方法之一.在搜索空间中，找到一组测试数据满足路径覆盖是一个具有挑战性的问题.因此，自动生成测试数据是软件测试的关键问题.文中提出一种基于否定选择遗传算法的路径覆盖测试数据生成方法，将否定选择策略融入遗传算法，动态优化遗传算法的种群数据，自动生成覆盖目标路径的测试数据.多个基准程序和工业程序的实验结果表明，与随机方法和遗传算法比较，文中方法能够提高路径覆盖率，减少冗余测试数据的生成.

关键词: 软件测试, 遗传算法, 否定选择, 路径覆盖, 测试数据

Abstract: Path coverage is one of the most important testing methods in the field of software testing. It is a challenging problem to find a set of test data to satisfy the path coverage in the search space. Therefore, automatically generating test data is a key issue in software testing. In this paper, a generation method of test data based on the negative selection genetic algorithm is proposed. The negative selection strategy is integrated into the genetic algorithm, and the population data of the genetic algorithm is dynamically optimized, and the test data covering the target path is automatically generated. The experimental results show that compared with the random method and the genetic algorithm, the proposed method can improve the path coverage and reduce the generation of redundant test data.

Key words: software test, genetic algorithm, negative selection, path coverage, test data

中图分类号:

TP311

夏春艳, 张岩, 万里, 等. 基于否定选择遗传算法的路径覆盖测试数据生成[J]. 电子学报, 2019, 47(12): 2630-2638.

XIA Chun-yan, ZHANG Yan, WAN Li, et al. Test Data Generation of Path Coverage Based on Negative Selection Genetic Algorithm[J]. Acta Electronica Sinica, 2019, 47(12): 2630-2638.

参考文献

[1] Mei Jia,Wang Sheng-yuan.An improved genetic algorithm for test cases generation oriented paths[J].Chinese Journal of Electronics,2014,23(3):494-498.
[2] Omur Sa-hin,Bahriye Akay.Comparisons of metaheuristic algorithms and fitness functions on software test data generation[J].Applied Soft Computing,2016,49:1202-1214.
[3] Ghiduk A S.Automatic generation of basis test paths using variable length genetic algorithm[J].Information Processing Letters,2014,114(6):304-316.
[4] 夏春艳,张岩,宋丽.基于节点概率的路径覆盖测试数据进化生成[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)
[5] 单锦辉,王戟,齐治昌.面向路径的测试数据自动生成方法述评[J].电子学报,2004,32(1):109-113. SHAN Jin-hui,WANG Ji,QI Zhi-chang.Survey on path-wise auto-matic generation of test data[J].Acta Electronica Sinica,2004,32(1):109-113.(in Chinese)
[6] 吴川,巩敦卫,姚香娟.基于分支覆盖的回归测试路径选择[J].软件学报,2016,27(4):839-854. WU Chuan,GONG Dun-wei,YAO Xiang-juan.Selection of paths for regression testing based on branch coverage[J].Journal of Software,2016,27(4):839-854.(in Chinese)
[7] 杨波,吴际,刘超.基于变量影响分析与数据变异的回归测试用例生成[J].计算机学报,2016,39(11):2372-2387. YANG Bo,WU Ji,LIU Chao.An approach of regression test case generation based on variable impact analysis and data mutation[J].Chinese Journal of Computers,2016,39(11):2372-2387.(in Chinese)
[8] Chang-ai Sun,Fei-fei Xue,Huai Liu,Xiang-yu Zhang.A path-aware approach to mutant reduction in mutation testing[J].Information and Software Technology,2017,81:65-81.
[9] Pedro Reales Mateo,Macario Polo Usaola.Reducing mutation costs through uncovered mutants[J].Software Testing,Verification and Reliability,2015,25:464-489.
[10] 张功杰,巩敦卫,姚香娟.基于统计占优分析的变异测试[J].软件学报,2015,26(10):2504-2520. ZHANG Gong-jie,GONG Dun-wei,YAO Xiang-juan.Mutation testing based on statistical dominance analysis[J].Journal of Software,2015,26(10):2504-2520.(in Chinese)
[11] Gwan Hwan Hwang,Heng-yi Lin,Shao-yan Lin,Che-sheng Lin.Statement-coverage testing for concurrent programs in reachability testing[J].Journal of Information Science and Engineering,2014,30:1095-1113.
[12] Tian Tian,Dun-wei Gong.Test data generation for path coverage of message-passing parallel programs based on co-evolutionary genetic algorithms[J].Automated Software Engineering,2016,23:469-500.
[13] Ali Shahbazi,James Miller.Black-box string test case generation through a multi-objective optimization[J].IEEE Transactions on Software Engineering,2016,42(4):361-378.
[14] Yeresime Suresh,Santanu Ku Rath.A genetic algorithm based approach for test data generation in basis path testing[J].The International Journal of Soft Computing and Software Engineering,2013,3(3):326-332.
[15] 张岩,巩敦卫.基于搜索空间自动缩减的路径覆盖测试数据进化生成[J].电子学报,2012,40(5):1011-1016. ZHANG Yan,GONG Dun-wei.Evolutionary generation of test data for path coverage based on automatic reduction of search space[J].Acta Electronica Sinica,2012,40(5):1011-1016.(in Chinese)
[16] 姚香娟,巩敦卫.基于路径比较的变异测试方法[J].电子学报,2012,40(1):103-107. YAO Xiang-juan,GONG Dun-wei.Mutation testing based on comparison of paths[J].Acta Electronica Sinica,2012,40(1):103-107.(in Chinese)
[17] 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.
[18] 周明,孙树栋.遗传算法原理与应用[M].北京:国防工业出版社,1999.
[19] 张岩,巩敦卫.基于稀有数据拓扑的路径覆盖测试数据进化生成方法[J].计算机学报,2013,36(12):2429-2440. 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-2440.(in Chinese)

基于否定选择遗传算法的路径覆盖测试数据生成

Test Data Generation of Path Coverage Based on Negative Selection Genetic Algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李杨帅, 彭斐, 韩倩, 李小帅, 解光军. 一种针对QCA电路自动布局布线的混合策略研究[J]. 电子学报, 2023, 51(3): 666-674.
[2]	李志博, 李清宝, 兰明敬, 孙剑帆. 基于镜像选择序优化的MART算法[J]. 电子学报, 2022, 50(2): 314-325.
[3]	张笑宇, 沈超, 蔺琛皓, 李前, 王骞, 李琦, 管晓宏. 面向机器学习模型安全的测试与修复[J]. 电子学报, 2022, 50(12): 2884-2918.
[4]	钱忠胜, 俞情媛, 宋涛, 朱懿敏, 祝洁, 赵畅. 基于支持向量机回归模型的测试用例生成与重用[J]. 电子学报, 2021, 49(7): 1386-1391.
[5]	刘焕淋, 黄美娜, 陈勇, 杨健, 黄冰川, 张彤. 基于NOMA技术的PLC-VLC用户配对和子载波分配方法[J]. 电子学报, 2021, 49(10): 1952-1959.
[6]	金泽芬芬, 侯志强, 余旺盛, 王鑫, 寇人可. 基于量子遗传算法的视觉目标跟踪[J]. 电子学报, 2020, 48(8): 1493-1501.
[7]	廖伟志, 夏小云, 贾小军. 基于蚁群算法的多路径覆盖测试数据生成[J]. 电子学报, 2020, 48(7): 1330-1342.
[8]	薛河, 苟思育, 倪陈强. 紧凑拉伸试样参比电位差接线点布局的优化方法[J]. 电子学报, 2020, 48(7): 1396-1402.
[9]	范书平, 张岩, 马宝英, 万里, 姚念民, 宋妍. 基于均衡优化理论的路径覆盖测试数据进化生成[J]. 电子学报, 2020, 48(7): 1303-1310.
[10]	郭广颂, 陈良骥, 文振华, 张勇. 求解高维混合指标优化问题的交互式进化计算[J]. 电子学报, 2020, 48(7): 1361-1368.
[11]	徐超群, 易忠, 孟立飞, 刘超波, 黄魁. 基于遗传算法的卫星磁模型研究[J]. 电子学报, 2020, 48(6): 1108-1112.
[12]	唐香琼, 黄春跃, 梁颖, 匡兵, 赵胜军. 基于再流焊冷却过程应力分析的板极组件BGA焊点参数优化[J]. 电子学报, 2020, 48(6): 1117-1123.
[13]	祁志卫, 王笳辉, 岳昆, 乔少杰, 李劲. 图嵌入方法与应用:研究综述[J]. 电子学报, 2020, 48(4): 808-818.
[14]	田甜, 巩敦卫. 并发程序变异测试研究综述[J]. 电子学报, 2020, 48(11): 2267-2277.
[15]	梁颖, 黄春跃, 邹涯梅, 高超, 匡兵. 基于扭转载荷的微尺度CSP焊点应力应变分析与优化[J]. 电子学报, 2020, 48(10): 2033-2040.