基于路径自动分割的测试数据生成方法

doi:10.3969/j.issn.0372-2112.2016.09.034

电子学报 ›› 2016, Vol. 44 ›› Issue (9): 2254-2261.DOI: 10.3969/j.issn.0372-2112.2016.09.034

基于路径自动分割的测试数据生成方法

廖伟志^1,2

1. 嘉兴学院数理与信息工程学院, 浙江嘉兴 314001;
2. 广西混杂计算与集成电路设计分析重点实验室, 广西南宁 530006

收稿日期:2014-10-10 修回日期:2015-03-26 出版日期:2016-09-25
- 作者简介:
- 廖伟志 男,1974年生于广西凤山,教授,博士,主要研究方向:软件测试、智能计算.E-mail:weizhiliao2002@aliyun.com
- 基金资助:
- 国家自然科学基金 (No.61163012）; 广西高校科研资助项目 (No.2013ZD040）; 广西混杂计算与集成电路设计分析重点实验室开放基金课题 (No.2012HCIC01）

Test Data Generation Based on Automatic Division of Path

LIAO Wei-zhi^1,2

1. College of Mathematics Physics and Information Engineering, Jiaxing University, Jiaxing, Zhejiang 314001, China;
2. Guangxi Key laboratory of Hybrid Computation and IC Design Analysis, Nanning, Guangxi 530006, China

Received:2014-10-10 Revised:2015-03-26 Online:2016-09-25 Published:2016-09-25
- Supported by:
- National Natural Science Foundation of China (No.61163012); Research Fund of Colleges and Universities in Guangxi Zhuang Autonomous Region (No.2013ZD040); Open Fund Project of Key Laboratory of Hybrid Computing and Integrated Circuit Design and Analysis of Guangxi Province (No.2012HCIC01)

摘要/Abstract

摘要：

为了提高路径覆盖测试数据生成效率，研究了路径自动分割方法并结合人工鱼群算法提出了一种路径覆盖测试数据生成方法.首先在分析变量与节点关系、变量与路径关系的基础上提出了路径分割的自动判定及分离算法，实现了变量对子路径有无影响的自动判定；其次引入Levy飞行策略和共轭梯度法对人工鱼群算法进行了改进；然后结合路径分离的结果和改进的人工鱼群算法实现路径覆盖测试数据的生成.在利用人工鱼生成测试数据的过程中，判断是否有人工鱼穿越分离的子路径.如果有，则记录人工鱼中穿越子路径相应的分量并在人工鱼的觅食、聚群及追尾等行为中固定这些分量，从而使得搜索空间不断减少.最后将提出的方法实现程序的测试数据生成，并与相关方法进行了比较.实验结果表明，本文方法在时间开销、成功率及算法稳定性等方面均具有优越性.

关键词: 软件测试, 路径分割, 测试数据, 路径覆盖, 人工鱼群算法

Abstract:

In order to improve the efficiency of test data generation for path coverage,a method for generating test data was proposed,which was based on automatic division of path and artificial fish-swarm (AFS) algorithm.Firstly,the relations between variables and nodes,and between variables and paths,were analyzed.Based on the analysis an algorithm for automatic division of path was presented,which can automatically judge the impact of variables on sub-paths.Secondly,an improved AFS algorithm was developed based on Levy flying and conjugate gradient.By making use of the result of path division and the improved AFS algorithm,a new method for searching test data was proposed.If there exist sub paths that the fish pass through in the process of using AFS to generate test data,the corresponding component of these fish were fixed,so that search space were reduced.Finally,the proposed method was applied to the test data generation of programs.It is shown that our method outperforms the related methods in running time,success rate and stability.

Key words: software testing, path division, test data, path coverage, artificial fish-swarm algorithm

中图分类号:

TP301

廖伟志. 基于路径自动分割的测试数据生成方法[J]. 电子学报, 2016, 44(9): 2254-2261.

LIAO Wei-zhi . Test Data Generation Based on Automatic Division of Path[J]. Acta Electronica Sinica, 2016, 44(9): 2254-2261.

参考文献

[1] 巩敦卫,张婉秋.基于自适应分组的大规模路径覆盖测试数据进化生成[J].控制与决策,2011,26(7):979-983. Gong Dunwei,Zhang Wanqiu.Evolutionary generation of test data for many paths coverage based on adaptive grouping[J].Control and Decision,2011,26(7):979-983.(in Chinese)
[2] 张婉秋.基于遗传算法的多路径覆盖测试数据生成方法[D].江苏徐州:中国矿业大学,2010. Zhang Wanqiu.Genetic algorithm based test data generation for multiple paths coverage[D].Xuzhou,Jiangsu:China University of Mining and Technology,2010.(in Chinese)
[3] Stefan J Galler,Bernhard K Aichernig.Survey on test data generation tools[J].International Journal on Software Tools for Technology Transfer,2014,16(6):727-751.
[4] Nigel Tracey,John Clark,Keith Mander.An automated framework for structural test-data generation[A].Proceedings of the International Conference on Automated Software Engineering[C].USA:IEEE,1998.285-285.
[5] Xiaofeng Xu,Yan Chen,Xiaochao Li.A path-oriented test data generation approach for automatic software testing[A].Proceedings of the 2^nd International Conference on Anti-counterfeiting,Security and Identification[C].Piscataway:IEEE,2008.63-66.
[6] Eugenia Diaz,Javier Tuya,Raquel Blanco.A tabu search algorithm for structural software testing[J].Computers & Operations Research,2008,35(10):3052-3072.
[7] 胡岳峰,高建华.一种面向对象测试用例自动生成的混合算法[J].计算机应用研究,2008,25(3):786-788. Hu Yuefeng,Gao Jianhua.Hybrid algorithm of automatically generating of test data for object-oriented program[J].Application Research of Computers,2008,25(3):786-788.(in Chinese)
[8] Moataz A Ahmed,Irman Hermadi.GA-based multiple paths test data generator[J].Computers & Operations Research,2008,35(10):3107-3124.
[9] Paulo Marcos Siqueira Bueno,Mario Jino.Automatic test data generation for program paths using genetic algorithms[J].International Journal of Software Engineering and Knowledge Engineering,2002,12(6):691-709.
[10] Jin-Cherng Lin,Pu-Lin Yeh.Automatic data generation for path testing using Gas[J].Information Sciences,2001,131(1-4):47-64.
[11] 张岩,巩敦卫.基于搜索空间自动缩减的路径覆盖测试数据进化生成[J].电子学报,2012,40(5):1011-1016. Zhang Yan,Gong Dunwei.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)
[12] A A Sofokleous,A S Andreou.Automatic evolutionary test data generation for dynamic software testing[J].Journal of System and Software,2008,81(11):1883-1898.
[13] 谢晓园,徐宝文,史亮,聂长海.面向路径覆盖的演化测试用例生成技术[J].软件学报,2009,20(12):3117-3136. Xie Xiaoyuan,Xu Baowen,Shi Liang,Nie Changhai.Genetic test case generation for path-oriented testing[J].Journal of Software,2009,20(12):3117-3136.(in Chinese)
[14] Yong Chen,Yong Zhong.Automatic path-oriented test data generation using a multi-population genetic algorithm[A].Proceeding of the 4th International Conference on Natural Computation[C].Piscataway:IEEE Press,2008.565-570.
[15] Chengying Mao.Structural test data generation based on harmony search[J].Lecture Notes in Computer Science,2013.353-360.
[16] 李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践,2002,22(11):32-38 Li Xiaolei,Shao Zhijiang,Qian Jixin.An optimizing method based on autonomous animats:fish-swarm algorithm[J].Systems Engineering-Theory & Practice,2002,22(11):32-38.(in Chinese)
[17] 王培崇,钱旭.基于改进鱼群算法的路径测试数据生成[J].计算机应用,2013,33(4):1139-1141. Wang Peichong,Qian Xu.Path test data generation based on improved artificial fish swarm algorithm[J].Journal of Computer Applications,2013,33(4):1139-1141.(in Chinese)
[18] JCB Ribeiro,MA Zenha-Rela,FFD Vega.Test case evolution and input domain reduction strategies for the evolutionary testing of object-oriented software[J].Information and Software Technology,2009,51(11):1534-1548.
[19] McMinn P.Evolutionary Search for test data in the presence of state behavior[D].Sheffied,England:University of Sheffied,2005.
[20] 王联国,洪毅.基于冯·诺依曼领域结构的人工鱼群算法[J].控制理论与应用,2010,27(6):775-780. Wang Lianguo,Hong Yi.Artificial fish-swarm algorithm based on Von Neuman neighborhood[J].Control Theory & Applications,2010,27(6):775-780.(in Chinese)

基于路径自动分割的测试数据生成方法

Test Data Generation Based on Automatic Division of Path

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李志博, 李清宝, 兰明敬, 孙剑帆. 基于镜像选择序优化的MART算法[J]. 电子学报, 2022, 50(2): 314-325.
[2]	张笑宇, 沈超, 蔺琛皓, 李前, 王骞, 李琦, 管晓宏. 面向机器学习模型安全的测试与修复[J]. 电子学报, 2022, 50(12): 2884-2918.
[3]	范书平, 张岩, 马宝英, 万里, 姚念民, 宋妍. 基于均衡优化理论的路径覆盖测试数据进化生成[J]. 电子学报, 2020, 48(7): 1303-1310.
[4]	廖伟志, 夏小云, 贾小军. 基于蚁群算法的多路径覆盖测试数据生成[J]. 电子学报, 2020, 48(7): 1330-1342.
[5]	祁志卫, 王笳辉, 岳昆, 乔少杰, 李劲. 图嵌入方法与应用:研究综述[J]. 电子学报, 2020, 48(4): 808-818.
[6]	田甜, 巩敦卫. 并发程序变异测试研究综述[J]. 电子学报, 2020, 48(11): 2267-2277.
[7]	姚渭箐, 胡凡. 基于IBED和仿生算法的LT码度分布设计[J]. 电子学报, 2019, 47(2): 428-433.
[8]	夏春艳, 张岩, 万里, 宋妍, 肖楠, 郭冰. 基于否定选择遗传算法的路径覆盖测试数据生成[J]. 电子学报, 2019, 47(12): 2630-2638.
[9]	孔德阳, 彭华, 马金全. 基于人工鱼群算法的自适应随机共振方法研究[J]. 电子学报, 2017, 45(8): 1864-1872.
[10]	陈田, 易鑫, 王伟, 刘军, 梁华国, 任福继. 一种低功耗双重测试数据压缩方案[J]. 电子学报, 2017, 45(6): 1382-1388.
[11]	巩敦卫, 秦备, 田甜. 基于语句重要度的变异测试对象选择方法[J]. 电子学报, 2017, 45(6): 1518-1522.
[12]	赵祖威, 冯世宁, 汤恩义, 陈鑫, 李宣东, 潘敏学, 赵晨. 一种符号执行制导的循环内界分析方法[J]. 电子学报, 2017, 45(11): 2582-2592.
[13]	薛猛, 姜淑娟, 张争光, 钱俊彦, 张艳梅, 曹鹤玲. 一种基于Kalman滤波和粒子群优化的测试数据生成方法[J]. 电子学报, 2017, 45(10): 2473-2483.
[14]	王红阳, 姜淑娟, 王兴亚, 鞠小林, 张艳梅. 基于子路径扩展的不可达路径检测方法[J]. 电子学报, 2015, 43(8): 1555-1560.
[15]	聂楚江, 刘海峰, 苏璞睿, 冯登国. 一种面向程序动态分析的循环摘要生成方法[J]. 电子学报, 2014, 42(6): 1110-1117.