应用混沌果蝇算法的路径覆盖测试用例优化技术研究

李龙澍,郭紫梦

(安徽大学 计算机科学与技术学院,合肥 230601)

1 引 言

伴随软件应用领域和软件规模不停的扩展和增大,软件的质量显得愈发重要.软件测试是保障软件质量的关键技术措施,通常从始至终贯穿着全部的软件研发流程,软件测试的重点就在于测试用例的编写,测试用例的自动化便成为软件测试的重中之重[1].路径覆盖测试是指在测试过程中,选择有效且充足的测试数据,除去不可能路径,使得测试程序中的其余所有路径都存在至少一条对应的测试数据.在现实测试中,众多软件测试问题都可以转化为路径覆盖测试的数据生成问题.

S Xanthakis 等人在1992年,初次提出采取遗传算法进化生成路径覆盖测试用例的思想,因此首创了一个崭新的研究领域[2].自此后,遗传算法便广泛的运用在路径覆盖测试研究领域内,从而出现多量的相关研究文献.夏春艳等人从穿过节点的困难情况出发,用遗传算法实现路径覆盖测试[3];丁蕊等人提出关键点路径表示法,改进算法适应度函数,以快速生成路径覆盖测试数据[4];巩敦卫等人采用Huffman Coding提出一种新的多路径覆盖测试数据的进化方法[5];张岩等人从种群的搜索空间这一角度入手,提出一种新的路径覆盖测试进化技术[6];随后,张岩等人在前文的基础之上,再次提出测试数据具有不同贡献度的思想,以参数来调节个体的适应度值[7];Pachauri A等人提出一种扩展路径前缀的策略,使用遗传算法实现分支覆盖[8];Peng Ye-ping 等人从路径匹配的角度入手,实现了多条目标路径同时覆盖的测试进化方法[9];Jakkrit Kaewyotha等人用循环结构寻找关键路径,使用遗传算法进行基本路径测试[10];Ghiduk Ahmed S重新定义了遗传算法中染色体、交叉和变异等概念,用以快速覆盖路径[12].这些方法在处理路径覆盖测试这一领域的问题时,多是选取遗传算法,通过对算法的适应度函数做些改进,或者交叉算子,变异算子的重定义及优化,以此来提高算法生成测试数据的效率.但是,鉴于遗传算法原理上的制约,导致在处理较为复杂的路径覆盖时,会出现计算量爆炸增长的现象[13],从而不能高效的处理路径覆盖测试问题.

在 2011 年,学者潘文超提出一种新的智能算法——果蝇优化算法(Fruit Fly Optimization Algorithm,FOA),该算法是从果蝇搜寻食物行为中得出的一种全新的智能优化算法[14],具有程序简单,寻优精度高等特点,最突出的优点是该算法计算量小,复杂度低,在复杂问题下不会出现计算量爆炸增长的现象,已在求解数学函数极值、微调Z-SCORE模型系数、广义回归神经网络参数优化与支持向量机参数优化等多个领域得到广泛应用.同时该算法具有不稳定性因素,存在着“早熟”现象,针对这一现象,众多研究学者引入混沌策略来保持种群的多样性,跳出局部最优,寻找全局最优.唐贤伦等人提出多目标混沌来优化PSO算法[15];范九伦等人对Logistic方程做出一种分段处理,使得其具有优异的非线性征象[16].Cheng YuHuei提出一种基于正弦的混沌策略,以此来调整PSO中的函数参数[17];Rezaee Jordehi A利用混沌搜索策略优化蝙蝠群算法[18].这些针对“早熟”现象改进的研究,均取得了较好的效果.

在遗传算法、果蝇优化算法的优缺点及文献[16]的启发下,本文提出一种基于混沌果蝇优化算法(C-FOA)的路径覆盖测试用例生成方法:通过对算法进行建模及设计味道浓度判定函数(适应度函数),使之运用于路径覆盖测试领域;同时对果蝇优化算法每次迭代中的最优个体加入混沌操作,使其跳出局部最优,快速地覆盖目标路径.最后,经过仿真实验,分析考验了本文方法的有效性.

2 混沌果蝇优化算法

2.1 标准果蝇优化算法(FOA)

果蝇优化算法,其原始想法来源于果蝇在找寻食物时的飞行行为.果蝇这一物种具有天然良好的感官知觉,在找寻食物时,首先会利用优异的嗅觉能力搜寻食物的气味,根据气味调整飞行的方向,同时在距离食物位置较近时,再次利用敏感的视觉能力,两者相结合以此来找到食物.根据这一行为特性,FOA算法基本思路如下[13]:

1)设置果蝇种群数目为 NP,最大迭代次数为 Maxgen,并任意给出果蝇种群二维开始位置为 X_axis,Y_axis.

2)给予果蝇个体运动的随机方向与间隔,random value为运动的间隔.

Xi=X_axis+RandomValueYi=Y_axis+RandomValue

(1)

3)求出果蝇个体与原点的间隔Dist、味道浓度判定值S和味道浓度Smell.

(2)

4)得到该种群中Smell值最大的果蝇个体,记为当前最优果蝇个体.

[bestSmellbestIndex]=max(Smell)

(3)

5)判断当前最优个体浓度值bestSmell是否高于上一次迭代的最优味道浓度值,若是,执行(6);若否,执行(7).

6)保存下来当前最优个体的味道浓度值与其二维坐标X、Y,其他果蝇个体则操纵方向飞往最优位置.

Smellbest=bestSmellX_axis=X(bestIndex)Y_axis=Y(bestIndex)

(4)

7)判断是否满足结束条件,若是,则结束;反之,执行2).

2.2 混沌果蝇优化算法(C-FOA)

果蝇优化算法的不足之处在于其稳定性差,易出现“早熟”现象,从而导致收敛速率减缓,收敛精度降低,甚至于不能获取全局最优值.混沌是天然的一种普遍的非线性征象.表面上是紊乱无序的混沌变量,实际却蕴含着一种深层的内在联系,众多学者利用这种深层联系进化搜索来达到相应效果[19].在FOA中融入混沌策略,提升算法脱离局部最优的能力,从而使得算法收敛的速率和精度得以提高.

本文使用Logistic映射的混沌方法.Logistic映射是探究混沌等繁杂体系行径的一个典型模型.按照如下方程进行反复迭代:

Z(t+1)=μZ(t)(1-Z(t))

(5)

式(5)中μ为控制参量,当μ=4,0≤Z0≤1,Logistic 处于绝对混沌状态.对于任何指定的Z0∈[0,1],均可迭代出唯一明确的混沌序列Z1,Z2,Z3,….

基于混沌策略的果蝇优化算法的基础思想为:每次迭代过程中,对整个果蝇群体搜寻到的最优个体A进行混沌扰动操作,将混沌序列中的最优个体A*保留,以A和A*各自为中心的随机搜索方向和距离范围内产生一半种群个体,并搜索到当前迭代过程中的最优值,继续进行混沌操作.融入混沌策略的进化算法可在迭代中不断产生局部最优点运动距离外的混沌个体,协助相应算法跳出局部极值点,以此更快的搜寻到全局最优值.

3 基于混沌果蝇的路径覆盖测试用例生成方法

3.1 路径覆盖测试问题描述

本小节通过一个实例来描述如何通过路径覆盖来达到测试的目的.首先,为了得到测试数据在程序中的运行走向,需要对程序加入插桩.如图1所示,是一个插桩后的三角形分类程序,输入一组数据(a,b,c),运行该程序得到标识变量序列,通过与目标路径对应的标识变量序列对比,来判断是否覆盖目标路径.本文中使用的三角形程序借鉴了文献[20]中的三角形程序,并对其稍加改动,此程序包含2个多分支选择关系,以及4个选择并列关系,剔除不可行路径后,共有19条可行路径,将分别作为需要覆盖的目标路径.

3.2 C-FOA算法的路径覆盖测试

在路径覆盖测试中,利用果蝇优化算法的收敛性迭代出最优个体来达到测试目标.将每个果蝇个体作为一条测试数据,设F0=(t1,t2,…,tm)表示路径覆盖测试中的目标路径标识序列,于是该问题就转化为寻找最优向量(x1,x2,…,xm)覆盖目标路径标识序列,具体如下:

1)编码

C-FOA算法采用整数编码方式,每个整数代表相应果蝇个体在该维度上的分量位置,其范围为[min,max],其中min为该维度上的最小值,max为该维度上的最大值.

图1 三角形分类插桩程序
Fig.1 Instrumentation program of triangular classification

2)果蝇个体

果蝇个体Gi(x1,x2,…,xj,…,xm),其中xj为整数,表示第i个果蝇个体在第j维度上的分量位置,N个果蝇个体构成果蝇种群,记为G={G1,G2,…,Gn}.

3)混沌果蝇个体

4)味道浓度函数

味道浓度函数代表着果蝇个体的效用,用Fitness表示,以此用来区分不同果蝇个体间的优劣情况,进而挑选出最优的那一个个体.本文的味道浓度函数依据路径覆盖测试适应度函数的设计,分为层接近度(approach_level)和分支距离(branch_distance)两部分相结合.

假设果蝇个体Gi穿越的路径标识序列为F(Gi),目标测试路径标识序列为F0.Gi的层接近度为approach_level(Gi),计算方法为:统计F(Gi)与F0相同标识变量的个数,用其除以目标测试路径标识序列F0的标识变量总数来计算,故层接近度值与个体的优异程度成正比;分支距离为branch_distance(Gi),计算方法与Tracey方法相同[21].同时为防止分支距离过大,从而使层接近度失去引导作用,将其采取1.001-branch_distance(Gi)做出标准化操作,故分支距离值与个体的优异程度成正比.

于是,个体Gi的味道浓度Fitness(Gi)可表示为:

Fitness(Gi)=approach_level(Gi)+1.001-branch_distance(Gi)

(6)

由式(6)可得,个体Gi的味道浓度Fitness(Gi)与个体的优异程度成正比.

3.3 算法步骤

假设需要覆盖的目标路径为F0,C-FOA算法具体流程如下:

输入:群体数量为 N,最大迭代次数为 Maxgen,混沌次数为K,并随机果蝇群体m维开始位置X1_axis,X2_axis,…,Xm_axis

输出:目标测试数据x1,x2,…,xm

Step1.给予果蝇个体Gi的随机方向与间隔,xi=Xi_axis+randomvalue,(i=1,2,…,m);

Step2.运行插桩后的程序;

Step3.根据公式(6)计算每只果蝇的味道浓度值,并找出其中浓度最高的;

Step4.判断当前最优个体的浓度值是否高于上一次迭代的值,若是,保存最优个体GBest(x1,x2,…,xm),若否,继续下一步;

Step5.判断是否覆盖目标路径F0,或达到最大迭代次数,若是,跳转Step 8,若否,继续下一步;

Step7.给予个体GBest*和GBest的随机方向与间隔,且分别对GBest*和GBest给予一半种群数目的个体,跳转Step 2;

Step8.终止种群的进化,保存并输出相应的测试结果.

C-FOA算法过程对应的流程图如图2所示.

图2 算法流程图Fig.2 Algorithm flowchart

为了防止混沌策略太过干扰最优值的寻找,同时也为了保持FOA计算量小的优势,根据情况对混沌次数做出了恰当的调整,即每两个周期添加一次混沌干扰.即使算法在未添加混沌的周期内出现“早熟”征兆,随后的混沌干扰便会迅速的使算法脱离局部极值.

4 仿真实验及结果分析

为了确定本文方法的实际可操作性及有效性,选择 3 个基准程序进行考验.将本文方法(C-FOA)与同类方法(即GA方法、ACO方法、FOA方法、及文献[11]中改进的GA方法)在同样的被测程序上实验.每组实验结果都将与同类方法的结果进行比较分析.

为了降低随机性的误差,5种方法的选择依据均是使用分支距离和层接近度相结合作为适应度函数(即味道浓度函数),并且均选取相同的参数设置进化生成测试数据.同时,以生成覆盖目标路径的测试数据或达到最大迭代次数作为算法运行的终止条件,针对不同程序每种情况独立运行 20 次后取其平均值.与其对比,可以更好地验证本文方法生成测试数据的效率.

共进行了两组实验,第一组为在不同迭代次数下的覆盖率;第二组为找到覆盖目标路径测试数据的评价次数与运行时间.实验条件:Windows 7 操作系统,MyEclipse 10仿真环境,计算机主频 2.80GHz,内存4GB.

4.1 基准程序

表1 被测程序的基本信息
Table 1 Basic information of tested programs

程序分支结构三个数排序3个选择并列关系三角形分类2个多分支选择结构，4个选择并列关系冒泡程序 2层循环嵌套，内层嵌套含有1个选择结构输入分量个数目标路径数代码行数插桩节点数37183319276434246

4.2 对比实验

实验1.不同迭代次数下的覆盖率

程序输入变量取值范围为 0-1023 之间的整数,种群大小为 50.对三个基准程序,分别在限定迭代次数为1、50、100、150、200的条件下,对于所有目标路径进行覆盖测试,得到相应的覆盖率,如图3-图5.

图3 三个数排序覆盖率Fig.3 Coverage of ranking of three numbers

由图3-图5可得:

1)从遗传算法、蚁群算法和果蝇优化算法的对比可以看出,在相同环境下,FOA的覆盖率在多数情况下是高于GA和ACO的,说明FOA方法应用在路径覆盖测试领域内是可行的.

图4 三角形分类覆盖率Fig.4 Coverage of triangular classification

2)在三个基准程序中,本文方法的覆盖率明显高于另外四种方法,特别是,在未达到完全覆盖时,本文方法具有更高的覆盖率;在均能达到完全覆盖时,本文方法具有更快的覆盖速度.综合以上,本文方法生成测试数据的效率高于同类方法.

图5 冒泡排序覆盖率Fig.5 Coverage of bubble sort

实验2.覆盖目标路径下的评价次数与运行时间

程序输入变量取值范围为 0-127 之间的整数,种群大小为 50.对三个基准程序进行所有目标路径的覆盖测试,得到相应的评价次数与运行时间.若评价次数超过1000,即认为该路径的测试数据寻找失败.具体结果如表2.

表2 覆盖全部目标路径下的评价次数与运行时间
Table 2 Evaluation times and runtime with all the target paths covered

测试函数GAACO评价次数运行时间(S)覆盖率(%)评价次数运行时间(S)覆盖率(%)三个数排序29．330．99510021．670．898100三角形分类495．6516．45694．74195．829．313100冒泡排序 246．439．399100149．146．298100测试函数FOA文献[11]的GA评价次数运行时间(S)覆盖率(%)评价次数运行时间(S)覆盖率(%)三个数排序21．480．72710011．630．725100三角形分类187．846．37910076．104．744100冒泡排序 133．174．52210097．126．054100测试函数C⁃FOA评价次数运行时间(S)覆盖率(%)三个数排序9．750．659100三角形分类54．263．682100冒泡排序 92．533．142100

由表2可以得到:

1)从评价次数来看,在5种方法中,本文方法以最少的评价次数获取了所有的测试数据.如在三角形分类程序中,本文方法的评价次数为54.26,遗传算法的评价次数为495.65,且未能全部覆盖,蚁群算法的评价次数为195.82,果蝇算法的评价次数为187.84,文献[11]中遗传算法的评价次数为76.10.以上数据说明本文方法的性能优于同类方法;

2)从运行时间来看,本文方法的运行时间明显少于另外4种方法.特别是,随着程序的复杂度增加,本文方法的优势更加明显,这是因为,本文方法具有计算量小,复杂度低等优势,再次证明本文方法生成测试用例的效能优于同类方法;

3)从覆盖成功率来看,随着目标路径的增多以及路径复杂程度的增加,本文方法的评价次数和运行时间也有所增加.但是本文方法仍能有效生成测试数据.而且生成测试数据的成功率均可达到 100%,说明本文方法具有有效性.

通过以上的两组实验,本文方法充分考验了 FOA 算法应用在路径覆盖测试用例进化生成领域内的可行性,并且考证了本文方法生成路径覆盖测试数据的有效性,提升了获取测试用例的效率.

5 结 论

鉴于果蝇优化算法和遗传算法等智能算法同属于一类算法,同时果蝇优化算法具有计算量小,复杂度低,寻优精度高等优点,本文把果蝇优化算法应用到路径覆盖测试领域内,并针对果蝇优化算法稳定性差的缺点,对迭代过程中的最优个体加入混沌策略,在保留优秀个体的同时,增加种群多样性,优化全局搜索能力,加快算法收敛速度,有效提高了生成测试数据的效率.实验结果表明,本文方法与同类方法相比生成测试数据的效率更高.

[1] Dong Yue-hua,Dai Yu-qian.Automatic software test data generation based on DPPSO[J].Journal of Chinese Computer Systems,2015,36(9):2015-2020.

[2] Xanthakis S,Ellis C,Skourlas C,et al.Application of genetic algorithms to software testing[C].Perry D,Jeffery R,Notkin D,eds.Proceedings of the 5th International Conference on Software Engineering and its Applications.Los Alamitos:IEEE,1992:625-636.

[3] 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.

[4] Ding Rui,Dong Hong-Bin,Zhang Yan,et al.Fast automatic generation method for software testing data based on key-point path[J].Journal of Software,2016,27(4):814-827.

[5] 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.

[6] 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.

[7] 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.

[8] Pachauri A,Srivasatava G.Towards a parallel approach for test data generation for branch coverage with genetic algorithm using the extended path prefix strategy[C].International Conference on Computing for Sustainable Global Development.IEEE,2015:1786-1792.

[9] Peng Ye-ping,Zeng Bi.Software test data generation for multiple paths based on genetic algorithms[J].Applied Mechanics & Materials,2012,263-266:1969-1973.

[10] Jakkrit Kaewyotha,Wararat Songpan.Finding the critical path with loop structure for a basis path testing using genetic algorithm[M].Recent Advances in Information and Communication Technology 2015,Springer International Publishing,2015:41-52.

[11] You Feng,Zhao Rui-lian,Lv Shan-shan.Output domain based automatic test case generation[J].Journal of Computer Research and Development,2016(3):541-549.

[12] Ghiduk Ahmed S.Automatic generation of basis test paths using variable length genetic algorithm[J].Information Processing Letters,2014,114(6):304-316.

[13] Zhang Wei-xiang,Wei Bo,Du Hui-sen.Test case prioritization method based on genetic algorithm [J].Journal of Chinese Computer Systems,2015,36(9):1998-2002.

[14] Fan Wen-chao.Fruit fly optimization algorithm-a new evolutionary computation approach[M].Taiwan:Tsang Hai Publishing,2011.

[15] Tang Xian-lun,Zhou Wei,Zhang Heng,et al.Robot soccer defensive strategy based on multi-objective chaotic PSO[J].Journal of System Simulation,2014,26(1):51-61.

[16] Fan Jiu-lun,Zhang Xue-feng.Piecewise logistic chaotic map and its performance analysis [J].Acta Electronica Sinica,2009,37(4):720-725.

[17] Cheng Yu-huei.Evaluation of sine-based chaotic strategy for adapting inertia weight of particle swarm optimization[J].Lecture Notes in Engineering & Computer Science,2015,1(1):36-40.

[18] Rezaee Jordehi A.Chaotic bat swarm optimisation(CBSO)[J].Applied Soft Computing,2015,26(C):523-530.

[19] Chuang Li-yeh,Tsai Sheng-wei,Yang Cheng-hong.Improved binary particle swarm optimization using catfish effect for feature selection[J].Expert Systems with Applications,2011,38(10):12699-12707.

[20] Wu Chuan,Gong Dun-wei.Evolutionary generation of Test data for regression testing based on path correlation [J].Chinese Journal of Computers,2015(11):2247-2261.

[21] Zhang Yan.Theories and methods of evolutionary generation of test data for path coverage[D].Beijing:China University of Mining and Technology,2012.

附中文参考文献：

[1] 董跃华,戴玉倩.一种改进PSO的软件测试数据自动生成算法[J].小型微型计算机系统,2015,36(9):2015-2020.

[3] 夏春艳,张 岩,宋 丽.基于节点概率的路径覆盖测试数据进化生成[J].软件学报,2016,27(4):802-813.

[4] 丁 蕊,董红斌,张 岩,等.基于关键点路径的快速测试用例自动生成方法[J].软件学报,2016,27(4):814-827.

[5] 巩敦卫,张 岩.一种新的多路径覆盖测试数据进化生成方法[J].电子学报,2010,38(6):1299-1304.

[6] 张 岩,巩敦卫.基于搜索空间自动缩减的路径覆盖测试数据进化生成[J].电子学报,2012,40(5):1011-1016.

[7] 张 岩,巩敦卫.基于稀有数据扑捉的路径覆盖测试数据进化生成方法[J].计算机学报,2013,36(12):2429-2440.

[11] 尤 枫,赵瑞莲,吕珊珊.基于输出域的测试用例自动生成方法研究[J].计算机研究与发展,2016(3):541-549.

[13] 张卫祥,魏 波,杜会森.一种基于遗传算法的测试用例优先排序方法[J].小型微型计算机系统,2015,36(9):1998-2002.

[14] 潘文超.果蝇最佳化演算法—最新演化式计算技术[M].台湾:沧海书局,2011.

[15] 唐贤伦,周 维,张 衡,等.一种基于多目标混沌 PSO 的机器人足球防守策略[J].系统仿真学报,2014,26(1):51-61.

[16] 范九伦,张雪锋.分段Logistic混沌映射及其性能分析[J].电子学报,2009,37(4):720-725.

[20] 吴 川,巩敦卫.基于路径相关性的回归测试数据进化生成[J].计算机学报,2015(11):2247-2261.

[21] 张 岩.路径覆盖测试数据进化生成理论与方法[D].北京：中国矿业大学,2012.