0 引言

软件测试是保障软件产品质量的重要手段^[1]。软件测试的智能化能够极大地提高测试效率,其中测试数据的自动生成是实现软件测试智能化的重要部分^[2]。将测试数据的生成过程考虑为在被测程序的输入空间进行抽样的过程,则该问题就转化为可以用智能算法求解的优化问题^[3-4]。Sthamer^[5]在1995年首次使用遗传算法(Genetic Algorithm,GA)解决全路径覆盖测试数据生成问题,但求解效率不高,研究一度陷为沉寂。直至2008年Ahmed等^[6]利用GA一次生成覆盖多条目标路径的测试数据时,本领域的研究才再次引起广泛关注;近年已有许多学者使用智能优化算法生成测试数据。2011年Gong等^[7]将多路径覆盖测试数据生成问题建模为一个使用GA求解的多个目标优化问题,提高了问题求解效率; Windisch等^[8]使用参数少且易实现的粒子群(Particle Swarm Optimization,PSO)算法生成测试数据;Jiang等^[9]对PSO算法进行缩减用以生成测试数据,一定程度上解决了PSO算法易陷入局部最优和搜索结果精度低的问题。

烟花爆炸优化(Fireworks Explosion Optimization,FEO)算法^[10-11]是在烟花爆炸现象启发下提出的并行弥漫式搜索算法。

通过对烟花爆炸点的模拟实现最优解的寻优。FEO算法使用并行搜索的方式,具有搜索速度快、参数少的特点,已被应用于解决最优化问题。本文在前期研究工作^[12-13]的基础上,借鉴Gong等^[7]和王培崇等^[14]的思想,针对面向路径覆盖的软件测试数据生成问题,定义了难覆盖路径;利用难覆盖路径的邻近路径测试数据作为部分初始烟花,这些带有启发信息的初始烟花能够提高烟花爆炸优化算法生成难覆盖路径测试数据的效率;在烟花算法中设计自适应策略的爆炸半径既提高了收敛速度,也一定程度上避免了早熟收敛;借用边界值测试法的思想修正越界的火花个体,算法更易于生成难覆盖路径的测试数据。

1 相关知识 1.1 测试数据生成

测试数据的自动生成能够极大地提高软件测试的效率。如何使用优化算法提高测试数据的生成效率是近年的研究热点。研究者们从不同角度思考解决方案,如缩小搜索空间以提高搜索速度^[15]、改进算法以提高搜索效率^[16]、利用已有信息或测试数据生成新的测试数据^[17]等。在实际的测试数据生成工作中,优化算法能够快速生成覆盖绝大多数路径的测试数据,其困难在于难以生成覆盖某个或某些分支的测试数据,将这些难覆盖到的路径简称为难覆盖路径。分析这些难覆盖路径及其测试数据的特点,可发现难覆盖路径中难于满足条件的分支的测试数据,实际上与使用边界值法生成的测试数据有密切关系。边界值法是对输入或输出的边界值进行测试的一种方法。本文考虑使用优化算法自动生成面向路径覆盖的测试数据,借用传统软件测试方法中边界值测试法的思想,利用已生成的部分测试数据,生成难覆盖路径的测试数据。

1.2 烟花爆炸优化算法

烟花爆炸优化算法是近年新兴的群智能算法,已在复杂优化问题中表现了优良的性能和效率。烟花爆炸优化算法的流程如图 1所示。

烟花算法通过爆炸搜索机制进行全局优化求解。其基本思想^[10]是:随机选择N个烟花作为初始群体,群体中的每个烟花以一定的半径经爆炸操作生成 P个火花,通过映射规则保证爆炸生成的火花仍在可行解范围内,保留当前的最优个体,同时在当前代的所有烟花和火花中选择N-1个个体组成下一代群体,循环迭代,最终求得问题的全局最优解。与其他群智能优化算法相比, 烟花算法的显著特点在于爆炸产生火花的瞬时性和局部覆盖性。瞬时性是指在爆炸中产生的火花如果没有被选中成为下一代烟花,这些火花或烟花自身将在本次迭代中消亡,这一特点使得算法实现简单且保持了优化的分布并行性;局部覆盖性是指每个烟花爆炸出来的火花在烟花所处的局部范围内进行搜索,这一特点能够使算法在已明确全局最优解所在区域的前提下提高收敛速度。

2 基于FEO的路径覆盖测试数据生成 2.1 难覆盖路径

面向路径覆盖的测试数据生成工作,首先要分析程序代码,考虑测试数据需要覆盖到的路径。目前结构化程序通常包括顺序、选择、循环三种基本结构,选择结构中的多分支可以分解成多个双分支结构的组合;循环结构通过引入Z路径覆盖^[19]的思想转化为选择结构。由此,将程序看成由顺序和双分支结构组成。面向路径覆盖的测试数据生成就是自动生成一组能够覆盖被测程序所有可行路径的输入数据。对于程序的所有可行路径,根据其被覆盖的难易程度分为易覆盖路径和难覆盖路径。

易覆盖路径是指覆盖该路径的测试数据可以通过在被测程序的输入域空间随机抽取生成，难覆盖路径则难以通过随机方式生成覆盖该路径的测试数据。确定易覆盖路径和难覆盖路径的基本思想是:分析被测程序,得出关键点表示^[12]的路径集A,A中包含被测程序的所有m条理论路径;在程序输入域范围内随机生成包含n个测试数据的集合S={s₁,s₂,…,s_i,…,s_n},s_i是覆盖一条路径的测试数据。对于被测程序有p个输入变量的情况,s_i可表示为向量形式:s_i=(s_i1,s_i2,…,s_ip)，包括n个测试数据的集合S通常不能覆盖n条路径,这是由于不同的测试数据可能覆盖相同的路径。使用S中的数据运行程序,得到覆盖的路径并记录其对应的测试数据,此时已被覆盖的路径即称为易覆盖路径,构成易覆盖路径集E。使用不可行路径检测模型^[20]检测集合A-E,确定不可行路径集U,即得到由难覆盖路径组成的集合H,H=A-E-U。以三角形判断程序为例,程序输入的3个整数为三角形的三条边长,程序功能为判断输入的3条边是否能构成或构成怎样的三角形,预设的输出结果有四种:不构成三角形、普通三角形、等腰三角形和等边三角形,分别对应程序的四条理论路径P1、P2、P3和P4,该程序中不存在不可行路径。在输入域空间[10,100]中用随机抽取的方式生成5组测试数据,以三元组的形式分别表示三角形所对应的三条边,5组测试数据分别为(20,15,62),(52,43,71),(21,66,10),(78,26,59),(61,37,90),可以看出,这随机抽取的5组测试数据能够覆盖程序的两条路径,分别是不构成三角形的路径P1和普通三角形的路径P2,但却没有随机生成能够覆盖判定为等腰三角形和等边三角形所对应的路径P3和P4的测试数据。此时,称P1和P2为易覆盖路径,P3和P4为难覆盖路径。

在面向路径覆盖的测试数据生成问题中,路径的表示方式与优化算法的数学模型及其求解密切相关^[21]。本文使用关键点路径表示法,是为了便于得到待测程序的理论路径数目,并在算法优化过程中快速确定已知路径的邻近路径。利用已生成的易覆盖路径的测试数据,生成其邻近的难覆盖路径的测试数据^[12]。

2.2 面向路径覆盖测试数据生成的烟花爆炸优化算法 2.2.1 烟花爆炸算法自动生成测试数据方法的模型

本文提出面向路径覆盖测试数据生成的烟花爆炸优化算法,该方法模型如图 2所示。

2.2.2 自适应烟花爆炸半径

爆炸半径r是烟花爆炸优化算法中的最主要参数之一。半径的大小决定着算法的收敛速度和求解精度。在算法迭代初期,爆炸半径r值较大以利于全局探索,随着迭代次数的增加,r值线性递减以利于局部搜索。经典烟花爆炸优化算法^[9]使用式(1)计算最大爆炸半径r,r随算法的迭代次数线性递减。

$r=\frac{T-t}{T}({{r}_{initial}}-{{r}_{end}})+{{r}_{end}}$

(1)

其中:T为算法最大迭代次数;t为当前的迭代次数;r_initial为初始时烟花爆炸的最大半径;r_end为最后一次迭代时烟花爆炸的最大半径。这种爆炸半径的设置方式是基于迭代次数的考虑,在算法运行后期缩小爆炸半径以对某个烟花点附近的范围进行细致的局部搜索。事实上,在算法运行初期,即有可能得到一些适应度值高的烟花,细致搜索其局部区域就有机会快速得到问题最优解。本文考虑根据烟花的适应度值自适应地确定爆炸半径。对于每次迭代中适应度值低于指定阈值Gate的烟花,其爆炸产生的火花数目加倍,一部分使用缩小爆炸半径产生火花以对其进行局部搜索,由式(3)计算爆炸半径;剩余部分的火花由式(2)计算的爆炸半径产生;对于其他适应度值高于指定阈值Gate的烟花,则仍由迭代次数计算爆炸半径以提高收敛速度。此时的爆炸半径 r由式(1)计算得出。

$r=\alpha \left[ {{(\frac{T-t}{T})}^{k}}\times ({{r}_{initial}}-{{r}_{end}}) \right]+{{r}_{end}}$

(2)

$r=\beta \times {{r}_{end}}$

(3)

其中：α和β是区间(0,1)内的随机数。参数k用于调节全局收敛和局部收敛的时间比例,当k=1时,r的值是线性递减的；当k>1时,算法用于全局搜索的时间相应变长。由文献^[22]可知,当k=5时,算法的前2/3的时间将进行全局搜索,后1/3时间用于局部搜索。

2.2.3 爆炸操作生成的火花个体

设待求解问题有j个输入变量,则烟花算法中的个体表示为:

$X={{x}_{1}},\text{ }{{x}_{2}},{{x}_{3}}\ldots \ldots {{x}_{j}},{{x}_{i}}\in {{D}_{i}},\text{ }i=1,2,\cdots j$

(4)

每个输入变量有不同的定义域。第X_i个烟花爆炸后形成p个火花,以新产生的火花个体X′_ip为例,其形式化表示为:

$X{{'}_{ip}}={{X}_{i}}+{{r}_{i}}\times b$

(5)

其中：b是表示爆炸方向的向量，向量大小为j,其值随机确定为-1、0或1,分别表示反向爆炸、不爆炸和正向爆炸。经爆炸操作产生的新个体可能存在某一个或某几个维度的值不在解空间范围内的情况,按照边界值测试法的思想,软件错误常发生在输入或输出范围的边界上^[18],此时使用其刚越过的输入数据的边界值修正新个体。这里以三角形判定程序为例进行说明。该程序有三个输入参数,即j=3,分别对应三角形的三条边,其定义域均设为[0,100],设初始时的个体为X=(20,45,74),随机生成的爆炸方向向量为b=(-1,1,0),爆炸半径设由式(1)计算得25,则新生成的个体X'=(0,70,74)。这里第一个维度为0是由于其值20-25=-5,已经越过了输入边界,所以用其越过的边界值进行修正。

2.2.4 初始种群生成与编码方式

算法初始时,在被测程序输入数据的定义域内随机生成测试数据集,由2.2.1节中图 2的模型所示,确定难覆盖路径、易覆盖路径及不可行路径,并记录难覆盖路径邻近的易覆盖路径的测试数据,以此作为烟花爆炸优化算法的初始烟花,若此时的烟花数目小于算法指定的初始烟花数目,则通过随机抽取复制的方式补足。

使用多元组对个体进行编码,在算法运行过程中以向量的形式表示,多元组中每一项的长度由被测程序确定。以三角形判定程序为例:设输入域为[0,100],则定义多元组中各项的长度为3,随机抽取的三个输入数据1、20和5可以表示为三元组(001,020,005),最终个体表示为001020005。

2.2.5 适应度函数设计

适应度函数引导优化算法的优化方向。本文用分支距离表示当前输入数据与为覆盖给定分支所需输入数据之间的靠近程度,对循环使用Z路径覆盖的方式转化为分支。借鉴文献^[23]中的适应度函数设计方法,在其基础上进行简化,适应度函数为:

$F=\sum\limits_{1}^{i}{f(i);i=1,2,3,\cdots n}$

(6)

其中: f(i)表示指定路径中第i个分支的函数,不同的分支谓词对应不同的分支函数表达式,具体计算公式参见文献^[23]。当F值为0时,表示对给定路径分支做到了完全覆盖。

2.2.6 面向路径覆盖测试数据生成的烟花爆炸优化算法

step1 分析被测程序,使用关键点路径表示法,得出理论路径条数^[12]。

Step2 在定义域内随机生成测试数据集。

Step3 确定难覆盖路径及其邻近的易覆盖路径的测试数据。使用测试数据集中的数据运行程序,找到易覆盖路径及其测试数据;使用不可行路径检测模型,确定不可行路径;由理论路径、易覆盖路径和不可行路径确定难覆盖路径集。记录难覆盖路径邻近的易覆盖路径的测试数据。

Step4 设置烟花算法的参数。最大迭代次数T,初始烟花数目N,初始烟花爆炸最大半径r_initial,最后一次迭代时烟花的最大爆炸半径r_end,自适应参数阈值Gate,每个烟花产生的火花数目P。

Step5 将Step3中的难覆盖路径邻近的易覆盖路径的测试数据作为初始烟花的一部分, 统计这些初始烟花的数目记为N_init,在输入域范围内随机初始化生成N-N_init个烟花。

Step6 计算所有个体的适应度函数值,适应度函数根据文献^[23]方法设计。

Step7 计算自适应烟花爆炸的最大半径r,当个体的适应度值大于等于指定阈值Gate时,r由式(1)计算得出;当个体的适应度值小于指定阈值Gate时,r值分别由式(2)、(3)计算得出。

Step8 爆炸操作,生成子代个体。烟花个体X经爆炸操作生成新的个体X′,X′由式(5)计算得出。如果所生成的子个体超出解空间的范围,则使用该维度上输入范围的边界值进行修正。

Step9 计算新生成的火花的适应度值;

Step10 若t>T或找到最优个体,算法停止,输出得到的最优个体及其适应度函数值。

Step11 对种群中的所有烟花及火花按适应度值排序,保留初始时易覆盖路径的测试数据仍为N_init个烟花点,再保留N-N_init个最优个体,共同作为新一代烟花。 转到Step6。

3 实验分析

使用三角形判定程序、三个数排序程序和冒泡程序验证基于烟花算法的路径覆盖测试数据生成的效率。这三个基准程序被广泛用于验证优化算法生成测试数据的性能,如文献^{[6-7, 12, 24]}。将本文算法记为IFEO,与其他七种基于优化的测试数据生成算法对比。七种对比算法分别是：在文献^[22]中自适应爆炸半径的烟花算法基础上加了启发信息的算法(本文简称为NFEO算法);FEO是不带启发信息和自适应爆炸半径的简单烟花爆炸算法;F-method和NF-method来自文献^[12],分别是带启发信息的遗传算法和不带启发信息的遗传算法;Ahmed算法^[6]是首个一次使用遗传算法获得多条测试数据的优化算法;单目标路径算法(single target method)^[24]是一次运行遗传算法只能得到一条测试数据的算法,多路径覆盖算法(multiple paths coverage method)^[7]是利用多个目标优化的思想一次使用遗传算法求解多条测试数据的算法。算法中涉及的参数设置见表 1。算法终止条件为生成覆盖目标路径的测试数据或达到最大进化代数。每个程序使用不同算法独立运行100次,取平均运行时间以避免随机因素的影响。所有程序均使用Matlab编写,在Windows 7(32位)操作系统平台上运行,其他配置为 Intel Core 2 Duo CPU E8200,2.66 GHz,2.00 GB RAM。

表 1给出了IFEO算法的参数,其中初始烟花爆炸最大半径 r_initial的计算公式^[24]为：

${{r}_{initial}}=a*\left( {{X}_{max}}-{{X}_{min}} \right),\text{ }a\in [0.050.3]$

末代烟花最大爆炸半径r_end及其他参数由经验得出。这里算法的最大迭代次数统一设定为1000,是出于对单目标路径方法的考虑,在本文涉及的三个实例的优化过程中,除单目标路径方法之外,其他各种方法都能在100代以内到找问题最优解。表 2对三个基准测试程序进行说明,明确了每个被测程序的理论路径数、易覆盖路径数及难覆盖路径数。其中三个数排序和冒泡程序各有一条不可行路径。

表 3~5统计了不同算法在三个基准程序中生成测试数据的表现,其中：运行时间和平均迭代次数是常用的评价测试数据生成效率的标准；运行时间率和迭代效率分别用于衡量各算法相对于基准算法的时间效率和迭代效率。运行时间率等于找到最优解时基准方法的运行时间与其他方法运行时间的比值,迭代效率等于找到最优解时基准方法的迭代次数与其他方法迭代次数的比值。为便于对比,以F-method^[12]为基准方法进行计算,并引用文献^[12]中的数据。可以看出F-method、NFEO与IFEO算法的优化效率远高于其他五种测试数据生成方法,这是由于F-method、NFEO和IFEO算法都使用了难覆盖路径邻近的易覆盖路径测试数据的启发信息。Ahmed算法、单目标路径算法和多路径覆盖算法由于没有区分路径覆盖的难易程度,其所需的适应度函数及计算量都显著多于其他四种方法,优化效率相对较低。FEO与NF-method和F-method相比,优于NF-method,但略差于F-method,这是由于虽然FEO与NF-method都没有使用启发式信息,但FEO算法在使用了基于边界值思想的越界个体修正方案后,收敛速度相对较快,FEO与使用了启发信息的F-method方法相比,其运行时间和收敛代数都没有优势。F-method中由于仅使用经典遗传算法优化,虽然使用了启发信息,但优化效率仍低于本文提出的IFEO。NFEO与IFEO都使用了启发信息,但使用了不同的自适应爆炸半径,从表 4~5可看出,NFEO能在更短的时间内找到最优解,但所需迭代次数略高于IFEO,这是由于NFEO的自适应爆炸半径计算公式相对简单;而在表 3中,NFEO的寻优时间略高于IFEO,原因在于其需要更多的迭代次数,也就是说,当NFEO不能通过迭代迅速找到最优解时,其所需的寻优时间会因迭代次数增加而变长。IFEO中的自适应爆炸半径使得算法在优化初期即能实现细致的局部搜索,能够提高算法的优化效率。

4 结语

使用优化算法生成测试数据已成为近几年的研究热点。事实上,绝大部分测试数据可以通过随机的方法生成,只有小部分测试数据是优化算法求解的难点。本文在关键点路径表示法的基础上定义了难覆盖路径,并考虑如何充分利用已覆盖路径及其测试数据提供的启发式信息。烟花爆炸优化算法是受烟花爆炸现象启发提出的新型并行搜索算法,算法通过烟花爆炸的方式在一定范围内随机搜索。烟花爆炸方式和爆炸半径决定着算法的全局搜索和局部搜索能力。本文对烟花算法进行改进,设计了由适应度函数值决定的自适应爆炸半径,提出了新的个体更新方式;针对难覆盖路径测试数据生成问题,使用其邻近的易覆盖路径测试数据作为带有启发信息的部分初始烟花个体,同时使用边界值测试思想的越界处理方法;将改进的烟花算法用于面向路径覆盖的测试数据生成中,实验结果表明了算法的有效性。在未来的工作中,将使用工业程序进一步检验本文方法的有效性。