基于组合混沌遗传算法的最小测试用例集生成

doi:10.11959/j.issn.1000-0801.2016178

摘要/Abstract

摘要：

最小测试用例集生成是软件测试的重要研究领域之一。将具有均匀分布特性的Chebyshev和Logistic混沌映射相结合的混沌序列引入遗传算法的选择、交叉和变异操作，并在遗传测试用例选择方法中添加混沌扰动，实现全局最优，以解决遗传算法用于测试用例集约简时局部搜索能力弱、易早熟收敛等问题。在随机生成的测试用例需求对应关系及Siemens测试套件等实例上进行了实验研究，并与现有的经典方法在测试用例集生成规模和算法执行时间上进行了比较，实验结果表明，在保持算法执行时间的基础上，在遗传测试用例方法中引入混沌映射有助于生成规模更小的测试用例集。

关键词: 软件测试, 测试用例最小化, 混沌遗传算法, 测试用例

Abstract:

Test case minimizing is one of the most important research fields in software testing.Uniformly distributed Chebyshev and Logistic chaos sequence were introduced in the selection，crossover and mutation of genetic algorithm.Chaos disturbance was also added in genetic testing suite to address the common problems of weak ability in local search and premature convergence，thus to optimize the test result.Experiments were conducted in randomly generated test suites and Siemens test suites.Comparisons were also made with classical methods regard to the scale of production of test suite and the execution time of the algorithms.The results of the experiment indicate that based on the same execution time of the algorithms，a smaller scale test suite can be produced by introducing chaotic sequence in genetic testing suite selection.

Key words: software testing, test cases minimizing, chaos genetic algorithm, test case

申情,蒋云良,沈张果,楼俊钢. 基于组合混沌遗传算法的最小测试用例集生成[J]. 电信科学, 2016, 32(6): 93-102.

Qing SHEN,Yunliang JIANG,Zhangguo SHEN,Jungang LOU. Test case minimizing based on combination chaos genetic algorithm[J]. Telecommunications Science, 2016, 32(6): 93-102.

图/表 8

图1

表1

图2

图3

表2

表3

图4

参考文献 28

[1]	TODD L . An empirical study of regression test selection techniques[J]. ACM Transactions on Software Engineering and Methodology， 2001，10（2）： 185-207.
[2]	NIE C ， LEUNG H . An empirical study of regression test selection techniques[J]. ACM Transactions on Software Engineering and Methodology， 2011，20（4）： 1-38.
[3]	BIBLE J ， ROTHERMEL G ， ROSENBLUM D . A comparative study of coarse- and fine-grained safe regression test selection techniques[J]. ACM Transactions on Software Engineering and Methodology， 2001，10（2）： 149-183.
[4]	HARROLD M ， GUPTA R ， SOFFA M . A methodology for controlling the size of a test suite[J]. ACM Transactions on Software Engineering and Methodology， 1993，2（3）： 270-285.
[5]	CHEN T ， LAU M . A new heuristic for test suite reduction[J]. Information and Software Technology， 1998，40（5）： 347-354.
[6]	CHEN T ， LAU M . On the divide and conquer approach towards test suite reduction[J]. Information Sciences， 2003，152（1）： 89-119.
[7]	邢颖，宫云战，王雅文 . 基于分支限界搜索框架的测试用例自动生成[J]. 中国科学：信息科学， 2014，44（10）： 1345-1360. XING Y ， GONG Y Z ， WANG Y W . Based on branch threshold search framework of automatic generation of test cases[J]. China Science：Information Science， 2014，44（10）： 1345-1360.
[8]	WINDISCH A ， WAPPLER S ， WEGENER J . Applying particle swarm optimization to software testing[C]// The 9th Annual Conference on Genetic and Evolutionary Computation，April 4-8，2007，London，UK. New Jersey： IEEE Press， 2007： 1121-1128.
[9]	陈翔，顾庆，王子元 . 一种基于粒子群优化的成对组合测试算法框架[J]. 软件学报， 2011，22（12）： 2879-2893. CHEN X ， GU Q ， WANG Z Y . A paired combination test algorithm based on particle swarm optimization framework[J]. Journal of Software， 2011，22（12）： 2879-2893.
[10]	史娇娇，姜淑娟，韩寒 . 自适应粒子群优化算法及其在测试数据生成中的应用研究[J]. 电子学报， 2013，41（8）： 1555-1559. SHI J J ， JIANG S J ， HAN H . Adaptive particle swarm optimization algorithm and its application in test data generation[J]. Electronic Journals， 2013，41（8）： 1555-1559.
[11]	王令赛，姜淑娟，张艳梅 . 基于正交搜索的粒子群优化测试用例生成方法[J]. 电子学报， 2014，42（12）： 2345-2351. WANG L S ， JIANG S J ， ZHANG Y M . Particle swarm optimization based on orthogonal search method for generating test cases[J]. Electronic Journals， 2014，42（12）： 2345-2351.
[12]	YOO S ， HARMAN M . Regression testing minimization，selection and prioritization：a survey[J]. Journal of Software Testing，Verification and Reliability， 2012，22（2）： 67-120.
[13]	MICHAEL C C ， MCGRAW G E ， SCHATZ M A . Generating software test data by evolution[J]. IEEE Transactions on Software Engineering， 2001，27（12）： 1085-110.
[14]	MA X Y ， SHENG B K ， YE C Q . Generating software test data by evolution[C]// The 6th International Workshop on Advanced Parallel Processing Technologies，April 5-10，2005，Hong Kong，China， New Jersey： IEEE Press， 2005： 253-262.
[15]	JONES B ， EYRES D . A strategy for using genetic algorithms to automate branch and fault-based testing[J]. The Computer Journal， 1998，41（2）： 98-107.
[16]	LIN J C ， YEH P L . Using genetic algorithms for test case generation in path testing[C]// The 9th Asian Test Symposium，October 3-5，2000，Washington D C，USA， New Jersey： IEEE Press， 2000： 241-246.
[17]	BERNDT D ， FISHER J ， JOHNSON L . Using genetic algorithms for test case generation in path testing[C]// The 36th Hawaii International Conference on System Sciences，May 5-8，2003，Hawaii，USA， New Jersey： IEEE Press， 2003： 17-26.
[18]	KHOR S ， GROGONO P . Using a genetic algorithm and formal concept analysis to generate branch coverage test data automatically[C]// The 26th IEEE/ACM International Conference on Automated Software Engineering（ASE 2011），IEEE Computer Society，November 6-10，2004，Lawrence，KS，USA， New Jersey： IEEE Press， 2004： 346-349.
[19]	LEE J ， CHUNG C . An optimal representative sets election method[J]. Information and Software Technology， 2000，42（1）： 17-25.
[20]	MARRE M ， BERTOLINO A . Using spanning sets for coverage testing[J]. IEEE Transactions on Software Engineering， 2003，29（11）： 974-984.
[21]	JEFFREY D ， GUPTA N . Improving fault detection capability by selectively retaining test cases during test suite reduction[J]. IEEE Transactions on Software Engineering， 2007，33（2）： 108-123.
[22]	张涌，钱乐秋，王渊峰 . 基于扩展有限状态机测试中测试输入数据自动选取的研究[J]. 计算机学报， 2003，26（10）： 1295-1303. ZHANG Y ， QIAN L Q ， WANG Y F . Based on extended finite state machine test input data in the automatic selection of research[J]. Journal of Computer， 2003，26（10）： 1295-1303.
[23]	杨瑞，陈振宇，张智轶 . 一种基于扩展有限状态机的自动化测试用例生成方法[J]. 中国科学：信息科学， 2014，44（5）： 588-609. YANG R ， CHEN Z Y ， ZHANG Z Y . Based on extended finite state machine automation test case generation method[J]. China Science：Information Science， 2014，44（5）： 588-609.
[24]	HOLLAND J . Adaption in natural and artificial systems[M]. Boston： MIT Press， 2015： 126-137.
[25]	俎云霄，周杰基于组合混沌遗传算法的认知无线电资源分配[J]. 物理学报， 2011，41（12）079501. ZU Y X ， ZHOU J Based on the combination of chaos genetic algorithm in cognitive radio resource allocation[J]. Journal of Physics， 2011，41（12）079501.
[26]	SRINIVAS M ， PATNAIK L M . Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Transactions on System，Man and Cybern， 1994，24（4）： 656-667.
[27]	HARMAN M . The current state and future of search based software engineering[C]// The 29th IEEE International Conference on Software Engineering.Minneapolis，May 23-25，2007，Minneapolis，MN，USA. New Jersey： IEEE Press， 2007： 342-357.
[28]	University of Nebraska-Lincoln. Computer science＆ engineering[[EB/OL].（2016-02-11）[2016-03-12]. .

序号	矩阵规模（测试需求数×用例数）	TCGG		MTCGG		TCGCG
序号	矩阵规模（测试需求数×用例数）	花费时间/ms	平均最优用例/个	花费时间/ms	平均最优用例/个	花费时间/ms	平均最优用例/个
1	20×20	326	3.7	292	3.8	334	3.7
2	40×40	1 001	4.63	877	4.73	629	4.33
3	60×50	1 573	5.37	956	5.23	922	5.27
4	60×60	1 856	5.30	1 033	5.03（99.3%）	1 042	5.13（99.9%）
5	80×80	3 397	6.13	2 899	5.67	2 375	5.57
6	90×80	4 229	6.23	3 784	6.07	3 651	5.87
7	100×100	5 424	6.57（99.9%）	4 616	5.97（99.8%）	4 096	6.20
8	150×100	8 743	7.23	6 341	6.67	5 722	6.27
9	200×150	23 262	6.87	20 453	6.87	12 569	6.23
10	300×200	46 723	7.53	33 274	7.37	21 415	6.63

被测程序	描述	可执行测试用例数（约简前）		总需求数
被测程序	描述	分支覆盖	定义—引用覆盖	分支	定义—引用对
space	解释器	533	3 585	1 356	5 179
tcas	航空器避撞系统	46	57	41	51
print tokens	词法分析器	97	268	127	275
print tokens2	词法分析器	159	240	154	235
schedule	优先级调度器	62	294	84	148
replace	模式匹配及替换	191	664	155	759
totinfo	数据统计系统	83	292	83	287

被测程序	N		N₁、N₂、N₃、N₄、N₅
被测程序	分支覆盖	定义—引用覆盖	分支	定义—引用对
space	874	3 585	300，360，420，480，540	300，400，500，600，700
tcas	46	57	20，25，30，35，40	20，25，30，35，40
print tokens	97	268	30，40，50，60，70	60，70，80，90，100
print tokens2	159	240	40，50，60，70，80	40，50，60，70，80
schedule	62	294	40，50，60，70，80	60，70，80，90，100
replace	191	664	40，50，60，70，80	60，70，80，90，100
totinfo	83	292	20，30，40，50，60	30，40，50，60，70