软件工程的主要目标是生产高质量的软件^[1].在软件开发中,软件测试是对软件需求分析、设计规格说明和编码的最终复审,是软件质量保证的关键步骤^[2].软件测试分为黑盒测试和白盒测试.路径覆盖测试属于白盒测试,要求在测试过程中尽可能地覆盖程序的所有可达到的路径.因此,高效地自动生成覆盖目标路径的测试数据,是该类测试的关键.

测试数据自动生成是生成一组测试数据,满足给定的测试标准的过程^[3].在自动生成测试数据时,为实现路径覆盖而呈现的一个具有挑战性的问题是存在不可达路径,这些路径对于任何输入数据都是不可执行的.

在软件测试中,检测被测程序的不可达路径将有效节省测试成本和提高测试效率.到目前为止,检测不可达路径的方法有两种:动态法和静态法.动态法一般不能直接判定不可达路径,通常在测试后期采用某种手段,比如限定路径覆盖的深度和搜索次数来判定不可达路径^[4].静态法主要有符号估值法^[5]和检测分支相关性^[6]等方法.符号法采用符号作为程序的输入变量,但很难确定哪个符号对结果能起到关键作用.Gupta^[7]和Zhuang^[8]等人分别提出了检测分支相关性的方法,但这些方法只针对极少的条件谓词种类,使得分支覆盖率偏低.Santone和Vaglini^[9]、Pourvatan和Sirjani^[10]、Chen和Mitra^[11]、Ngo和Tan^[12]、Delahaye和Botella^[13]对软件测试中不可达路径的检测也进行了深入的研究.姚香娟^[14]在其博士学位论文中提出了基于条件语句相关性的不可达路径自动检测方法.该方法结合上述方法的优点,能够准确地检测程序中全部或大部分的不可达路径.对于被测程序的所有路径,如果删除其中的不可达路径,自动求解覆盖可达路径的测试数据,将大大提高测试效率,缩短测试时间,节约软件开发成本.

遗传算法是自动求解路径覆盖测试数据的有效方法.Ahmed和Hermadi^[15]、Sofokleous和Andreou^[16]、Malhotra和Garg^[17]、Irfan和Ranjan^[18]、谢晓园等人^[19]对遗传算法实现路径覆盖测试数据的自动生成问题进行了研究,并取得了较好的成果.文献^[2]在测试数据进化生成中动态扑捉稀有数据,根据目标路径中稀有数据的贡献度设计适应度函数,得到满足路径覆盖的测试数据.但该方法在动态扑捉稀有数据时要求每一次迭代过程都重新统计节点的贡献度,从而增加了计算量.

本文采用条件语句的相关性自动检测不可达路径,在检测不可达路径的同时,统计不可达路径中节点出现的概率,从而确定必经节点(即割点),并且证明:除割点外的节点在不可达路径中出现的概率越大,则其在可达路径中出现的概率越小,该节点就越难以覆盖,即穿越该节点的个体就越少.依据文献^[2]指出的稀有数据具有较高的贡献度可知:在可达路径中,穿越该节点的个体具有较高的穿越度.本文根据个体的穿越度设计适应度函数,使得穿越难以覆盖的节点具有较高的适应度,在进化中得以保留,从而提高生成测试数据的效率.

本文第1节介绍相关概念以及不可达路径的检测.第2节提出个体的穿越度,并且设计适应度函数,分析算法性能,介绍算法步骤.第3节是所提方法在基准程序和工业用例中的应用,并与同类方法进行对比及分析实验结果.第4节总结全文,并提出需要进一步研究的问题.

1 检测不可达路径确定割点

文献[14]提出采用条件语句的相关性自动检测不可达路径,从而减少目标路径,可以有效地提高测试效率.在此基础上,计算节点在路径中出现的概率,确定割点.为介绍方便起见,首先给出几个基本概念.

(1) 控制流图

控制流图(control flow graph,简称CFG)是程序控制结构的图形表示,是一种具有如下结构的有向图G=(V,E,s,e),其中,V的元素v_i称作G的节点,E的元素${e_{ij}} = \langle {v_i},{v_j}\rangle $称为G的边,表示从语句v_i到语句v_j存在控制流.每个程序的控制流图还包含唯一的一个入口节点s和一个出口节点e.

图 1(a)为文献^[14]用到的示例程序的源代码,对应的控制流图如图 1(b)所示.

(2) 路径

路径是指给定有向图G的一个节点序列集$\Gamma = \left\{ {s,{v_1},{v_2}, \ldots ,{v_n},e} \right\},{v_i} \in V\left( {i = 1,2, \ldots ,n} \right)$,且:

$\langle s,{v_1}\rangle \in E,\langle {v_i},{v_i}_{ + 1}\rangle \in E(i = 1,2, \ldots ,n - 1),\langle {v_n},e\rangle \in E.$

如图 1(b)所示的一条路径为$\Gamma = \left\{ {s,{v_1},{v_2},{v_4},{v_5},{v_7},{v_8},e} \right\}$.

(3) 割点

给定有向图G=(V,E,s,e),$\forall {v_i} \in V\left( {i = 1,2, \ldots ,n} \right)$,对于任何路径$\Gamma $均有${v_i} \in \Gamma $,则称v_i为G的割点,即,在G中所有路径一定会经过的节点.

割点的确定方法:记被测程序为$\Phi ,{x_1},{x_2}, \ldots ,{x_m}$为$\Phi $的m组输入向量,输入域为D,运行$\Phi $得到m条穿越路径$\Gamma \left( {{x_1}} \right),\Gamma \left( {{x_2}} \right), \ldots ,\Gamma \left( {{x_m}} \right)$,根据第i个输入向量x_i穿越第j个节点v_j的情况定义随机变量Z_ij.

${Z_{ij}} = \left\{ {\begin{array}{*{20}{l}} {1,{\rm{ }}{v_j} \in \Gamma ({x_i})}\\ {0,{\rm{ }}{v_j} \notin \Gamma ({x_i})} \end{array}} \right.,$

得到如下容量为m的样本:

(z₁₁,z₁₂,…,z_1n),(z₂₁,z₂₂,…,z_2n),…,(z_m1,z_m2,…,z_mn),

则每个节点v_j被穿越的概率为

${p_j} = \frac{1}{m}\sum\limits_{i = 1}^m {{z_{ij}}} ,1 \le j \le n$

(1)

其中,$\Phi $中节点的个数,p_j即为v_j在m次输入中被穿越的概率.

· 若p_j=0,说明v_j在m次输入中均未被穿越;

· 若p_j=1,说明v_j在m次输入中均被穿越,即为割点.如图 1(b)所示,节点v₁,v₄和v₇均为割点.

(4) 相关性^[14]

设v_i和v_j是两个条件语句:

· 若v_i取真分支时v_j必然取真分支,则称语句对(v_i,v_j)具有真-真相关性;

· 若v_i取真分支时v_j必然取假分支,则称语句对(v_i,v_j)具有真-假相关性;

· 若v_i取假分支时v_j必然取真分支,则称语句对(v_i,v_j)具有假-真相关性;

· 若v_i取假分支时v_j必然取假分支,则称语句对(v_i,v_j)具有假-假相关性.

如图 1(b)所示,语句组(v₁,v₄)存在假-假相关性,语句组(v₁,v₄,v₇)存在真假-假相关性.

(5) 可达路径与不可达路径

对于路径$\Gamma $,如果存在$x \in D$,使得以x为输入运行被测程序$\Phi $,穿越路径$\Gamma \left( x \right) = \Gamma $,称$\Gamma $为可达路径;反之,若不存在$x \in D$,使得$\Gamma \left( x \right) = \Gamma $,称$\Gamma $为不可达路径.本文将可达路径记为$\Gamma $,不可达路径记为$\Gamma $.

不可达路径的检测:设v_i和v_j是两个条件语句.如果(v_i,v_j)具有真-真(或真-假)相关性,则任何包含v_i真分支以及v_j假分支(或真分支)的路径都是不可达路径;如果(v_i,v_j)具有假-真(或假-假)相关性,则任何包含v_i假分支以及v_j假分支(或真分支)的路径都是不可达路径^[14].

如图 1(b)所示的被测程序共有如下8条路径,分别是:

· ${\Gamma _1} = \left\{ {s,{v_1},{v_2},{v_4},{v_5},{v_7},{v_8},e} \right\};$

· ${\Gamma _2} = \left\{ {s,{v_1},{v_2},{v_4},{v_5},{v_7},{v_9},e} \right\};$

· ${\bar \Gamma _3} = \{ s,{v_1},{v_2},{v_4},{v_6},{v_7},{v_8},e\} ;$

· ${\Gamma _4} = \left\{ {s,{v_1},{v_2},{v_4},{v_6},{v_7},{v_9},e} \right\};$

· ${\bar \Gamma _5} = \{ s,{v_1},{v_3},{v_4},{v_5},{v_7},{v_8},e\} ;$

· ${\bar \Gamma _6} = \{ s,{v_1},{v_3},{v_4},{v_5},{v_7},{v_9},e\} ;$

· ${\Gamma _7} = \left\{ {s,{v_1},{v_3},{v_4},{v_6},{v_7},{v_8},e} \right\};$

· ${\Gamma _8} = \left\{ {s,{v_1},{v_3},{v_4},{v_6},{v_7},{v_9},e} \right\}.$

由于语句组(v₁,v₄)存在假-假相关性,那么任何包含v₁的假分支和v₄的真分支的路径都是不可达路径,因此,${\bar \Gamma _5}$和${\bar \Gamma _6}$是不可达路径.同理,由于语句组(v₁,v₄,v₇)之间存在真假-假相关性,那么任何包含v₁的真分支、v₄的假分支和v₇的真分支的路径都是不可达路径,因此,${\bar \Gamma _3}$是不可达路径.其余5条路径均为可达路径.

2 基于不可达路径节点出现概率的测试数据进化生成方法 2.1 个体的穿越度

在应用遗传算法生成测试数据的过程中,有大量测试数据运行被测程序,分别穿越被测程序可达路径中的不同节点.这些节点(除割点外)在可达路径中出现的概率不同.节点在可达路径中出现的概率越小,则生成穿越该节点的测试数据(即进化个体)越难,依此定义个体的穿越度.

以个体x_i为测试数据运行被测程序$\Phi $,得到其穿越路径$\Gamma \left( {{x_i}} \right)$,该路径包含n'个节点,删除割点后,剩余节点数为n,n≤n'.计算该个体的穿越度P(x_i)为

$P({x_i}) = \sum\limits_{j = 1}^n {\{ [1 - P({v_j}|\Gamma ')] \cdot {\theta _j}\} } $

(2)

其中,节点${v_j} \in \Gamma \left( {{x_i}} \right),j = 1,2, \ldots ,n;\Gamma '$为$\Phi $的所有可达路径集合;$P({v_j}|\Gamma ')$为v_j在$\Gamma '$中出现的概率;${\theta _j}$表示v_j是否为目标路径${\Gamma _0}$中的节点,即:

${\theta _j} = \left\{ {\begin{array}{*{20}{l}} {1,{\rm{ }}{v_j} \in {\Gamma _0}}\\ {0,{\rm{ }}{v_j} \notin {\Gamma _0}} \end{array}} \right..$

由公式(2)可知,计算个体的穿越度需要统计节点在可达路径集中出现的概率.易知:对于复杂的被测程序,含有较多的不可达路径,在生成路径覆盖测试数据时,为了提高生成效率,总是先检测不可达路径并将其删除.由于程序节点在可达路径集中出现的概率与其在不可达路径集中出现的概率存在一定的对应关系,详见定理1,因此在检测不可达路径时,统计节点在不可达路径集中出现的概率,利用节点在不可达路径集中出现的概率计算个体的穿越度,将大大减少计算量,提高测试效率.

定理1. 节点v_i(除割点外)在不可达路径集$\bar \Gamma '$中出现的概率$P({v_i}|\bar \Gamma ')$越大,则其在可达路径集$\Gamma '$中出现的概率$P({v_i}|\bar \Gamma ')$越小;反之,节点v_i(除割点外)在不可达路径集$\bar \Gamma '$中出现的概率$P({v_i}|\bar \Gamma ')$越小,则其在可达路径集$\Gamma '$中出现的概率$P({v_i}|\Gamma ')$越大.

证明:对于被测程序$\Phi $,令v_i(i=1,2,…,n)为$\Phi $的节点(除割点外),$\Gamma '$为可达路径集,$\bar \Gamma '$为不可达路径集,$P({v_i}|\bar \Gamma ')$为v_i在$\bar \Gamma '$中出现的概率,$P({v_i}|\Gamma ')$为v_i在$\Gamma '$中出现的概率,P(v_i)为v_i在所有路径集中出现的概率,$P\left( {\Gamma '} \right)$为可达路径集概率,即,可达路径集含有路径条数占所有路径集含有路径条数的比例.

节点v_i在不可达路径集$\bar \Gamma '$中出现的概率$P({v_i}|\bar \Gamma ')$为

$P({v_i}|\bar \Gamma ') = \frac{{P({v_i} \cdot \bar \Gamma ')}}{{P(\bar \Gamma ')}} = \frac{{P(\bar \Gamma '|{v_i}) \cdot P({v_i})}}{{P(\bar \Gamma ')}}$

(3)

则有:

$P(\bar \Gamma '|{v_i}) = \frac{{P({v_i}|\bar \Gamma ') \cdot P(\bar \Gamma ')}}{{P({v_i})}}$

(4)

节点v_i在可达路径集$\Gamma '$中出现的概率$P({v_i}|\Gamma ')$为

$P({v_i}|\Gamma ') = \frac{{P({v_i} \cdot \Gamma ')}}{{P(\Gamma ')}} = \frac{{P(\Gamma '|{v_i}) \cdot P({v_i})}}{{P(\Gamma ')}} = \frac{{\{ 1 - P(\bar \Gamma '|{v_i})\} \cdot P({v_i})}}{{P(\Gamma ')}}$

(5)

将公式(4)代入公式(5),可得:

$P({v_i}|\bar \Gamma ') = \frac{{\left\{ {1 - \frac{{P({v_i}|\bar \Gamma ') \cdot P(\bar \Gamma ')}}{{P({v_i})}}} \right\} \cdot P({v_i})}}{{P(\Gamma ')}} = \frac{{P({v_i}) - P({v_i}|\bar \Gamma ') \cdot P(\bar \Gamma ')}}{{P(\Gamma ')}} = \frac{{P({v_i})}}{{P(\Gamma ')}} - \frac{{1 - P(\Gamma ')}}{{P(\Gamma ')}} \cdot P({v_i}|\bar \Gamma ')$

(6)

即:

$P({v_i}|\bar \Gamma ') = \alpha - \beta \cdot P({v_i}|\bar \Gamma ')$

(7)

其中,$\alpha = \frac{{P({v_i})}}{{P(\Gamma ')}},\beta = \frac{{1 - P(\Gamma ')}}{{P(\Gamma ')}}$.P(v_i)和$P(\Gamma ')$随着被测程序$\Phi $的给定就已经确定,因此,上式中α和β为常数.由此可知:节点在不可达路径集中出现的概率越大,其在可达路径集中出现的概率越小.证毕. □

下面通过实例进一步验证定理1的正确性.如图 1(b)中去掉割点v₁,v₄和v₇,计算其余节点v_i(i=2,3,5,6,8,9)在不可达路径集和可达路径集中出现的概率.

先统计节点在不可达路径集中出现的概率.由第1节的示例可知:不可达路径集$\bar \Gamma ' = \{ {\bar \Gamma _3},{\bar \Gamma _5},{\bar \Gamma _6}\} $,即,有3条不可达路径.因为v₂仅在${\bar \Gamma _3}$中出现,即${v_2} \in {\bar \Gamma _3},$所以$P({v_2}|\bar \Gamma ') = \frac{1}{3},$因为v₃同时在${\bar \Gamma _5}$和${\bar \Gamma _6}$中出现,即${v_3} \in {\bar \Gamma _5} \cap {\bar \Gamma _6},$所以$P({v_3}|\bar \Gamma ') = \frac{2}{3}.$同理,$P({v_5}|\bar \Gamma ') = \frac{2}{3},P({v_6}|\bar \Gamma ') = \frac{1}{3},P({v_8}|\bar \Gamma ') = \frac{2}{3},P({v_9}|\bar \Gamma ') = \frac{1}{3}.$

有了上述节点在不可达路径集中出现的概率,可依据公式(7)计算节点在可达路径集中出现的概率.

以节点v₂为例,${v_2} \in {\Gamma _1} \cap {\Gamma _2} \cap {\bar \Gamma _3} \cap {\Gamma _4},$所以v₂在所有路径中出现的概率为$P({v_2}) = \frac{4}{8},$可达路径集含有路径条数占所有路径集含有路径条数的比例为$\frac{5}{8},$即可达路径集的概率为$P(\Gamma ') = \frac{5}{8}.$由上面计算得到$P({v_2}|\bar \Gamma ') = \frac{1}{3},$依据公式(7)可得:$P({v_2}|\Gamma ') = \alpha - \beta \cdot P({v_2}|\bar \Gamma ') = \frac{{P({v_2})}}{{P(\Gamma ')}} - \frac{{1 - P(\Gamma ')}}{{P(\Gamma ')}} \cdot P({v_2}|\bar \Gamma ') = \frac{{4/8}}{{5/8}} - \frac{{1 - 5/8}}{{5/8}} \cdot \frac{1}{3} = \frac{3}{5}.$

同理可计算$P({v_3}|\Gamma ') = \frac{2}{5},P({v_5}|\Gamma ') = \frac{2}{5},P({v_6}|\Gamma ') = \frac{3}{5},P({v_8}|\Gamma ') = \frac{2}{5},P({v_9}|\Gamma ') = \frac{3}{5}.$

通过手工计算验证公式(7)计算结果的正确性.仍以节点v₂为例,在可达路径集$\Gamma ' = \{ {G_1},{G_2},{G_4},{G_7},{G_8}\} $中,v₂仅出现在3条路径${\Gamma _1},{\Gamma _2}$和${\Gamma _4}$中,即${v_2} \in {\Gamma _1} \cap {\Gamma _2} \cap {\Gamma _4}$,则$P({v_2}|\Gamma ') = \frac{3}{5},$与公式(7)计算结果相同.同样,节点v₃,v₅,v₆,v₈和v₉在可达路径集中出现的概率均与公式(7)的计算结果相同.由此说明,依据节点在不可达路径集中出现的概率$P({v_i}|\bar \Gamma ')$计算其在可达路径集中出现的概率$P({v_i}|\Gamma ')$是正确的.

综上,通过理论证明和实例验证了定理1的正确性.

推论1. 节点v_i在不可达路径集$\bar \Gamma '$中出现的概率$P({v_i}|\bar \Gamma ')$越大,则穿越该节点的个体的穿越度越高.

证明:由定理1可知,节点v_i在不可达路径集$\bar \Gamma '$中出现的概率$P({v_i}|\bar \Gamma ')$越大,则其在可达路径集$\Gamma '$中出现的概率$P({v_i}|\Gamma ')$越小.根据个体的穿越度计算公式(2)可知:在可达路径中,穿越该节点的个体具有较高的穿越度. □

根据定理1和推论1,依据节点v_j在不可达路径集$\bar \Gamma '$中出现的概率$P({v_j}|\bar \Gamma ')$定义新的个体穿越度P'(x_i).

以个体x_i为测试数据运行被测程序$\Phi $,得到其穿越路径$\Gamma \left( {{x_i}} \right)$,该路径包含n'个节点,删除割点后,剩余节点数为n,n≤n'.计算该个体的穿越度P'(x_i)为

$P'({x_i}) = \sum\limits_{j = 1}^n {(P({v_j}|\bar \Gamma ') \cdot {\theta _j})} $

(8)

其中,节点${v_j} \in \Gamma \left( {{x_i}} \right),j = 1,2, \ldots ,n$;$\bar \Gamma '$为$\Phi $的所有不可达路径集合;$P({v_j}|\bar \Gamma ')$为v_j在$\bar \Gamma '$中出现的概率;${\theta _j}$表示v_j是否为目标路径${\Gamma _0}$中的节点,即:

${\theta _j} = \left\{ {\begin{array}{*{20}{l}} {1,{\rm{ }}{v_j} \in {\Gamma _0}}\\ {0,{\rm{ }}{v_j} \notin {\Gamma _0}} \end{array}} \right.$

实际上,个体x_i的穿越度P'(x_i)为其穿越路径与目标路径相同的节点(除割点外)在不可达路径中出现的概率之和.

如图 1(b)所示中目标路径${\Gamma _0}$={s,v₁,v₃,v₄,v₆,v₇,v₈,e}.若种群规模为4,进化到某一代时4个个体穿越的路径分别为:

· $\Gamma \left( {{x_1}} \right) = \left\{ {s,{v_1},{v_2},{v_4},{v_5},{v_7},{v_8},e} \right\};$

· $\Gamma \left( {{x_2}} \right) = \left\{ {s,{v_1},{v_3},{v_4},{v_6},{v_7},{v_9},e} \right\};$

· $\Gamma \left( {{x_3}} \right) = \left\{ {s,{v_1},{v_2},{v_4},{v_6},{v_7},{v_9},e} \right\};$

· $\Gamma \left( {{x_4}} \right) = \left\{ {s,{v_1},{v_2},{v_4},{v_5},{v_7},{v_9},e} \right\}.$

其中,节点v₁,v₄和v₇为割点.

· 对个体x₁,除割点外,仅穿越目标路径中的节点v₈.由前面计算可知,$P({v_8}|\bar \Gamma ') = \frac{2}{3},$其穿越度$P'({x_1}) = \frac{2}{3};$

· 对个体x₂,除割点外,穿越目标路径中的节点v₃和v₆,由前面计算可知,$P({v_3}|\bar \Gamma ') = \frac{2}{3},P({v_6}|\bar \Gamma ') = \frac{1}{3},$其穿越度$P'({x_2}) = \frac{2}{3} + \frac{1}{3} = 1;$

· 同理可得$P'({x_3}) = \frac{1}{3},$P'(x₄)=0.

由此可见:根据个体的穿越度,可以有效地区分个体的优劣.

由定理1及推论1可知:在计算个体的穿越度时,可以通过其穿越节点在不可达路径中出现的概率得到,这样要比计算其穿越节点在可达路径中出现的概率简便得多.

2.2 设计适应度函数

采用遗传算法自动生成测试数据,适应度函数体现了自然进化中的优胜劣汰原则.对于优化问题,适应度函数是根据目标函数确定的.因此,适应度函数的设计在遗传算法中发挥着重要作用.到目前为止,针对路径覆盖的测试数据进化生成,适应度函数的设计方法主要有3种:分支距离(branch_distance)、层接近度(approach_ level)以及二者相结合的方法.本文采用分支距离与层接近度结合的方法设计适应度函数.

假设个体x_i穿越的路径为$\Gamma \left( {{x_i}} \right)$,目标路径为${\Gamma _0}{x_i}$的层接近度为approach_level(x_i),计算方法采用统计个体穿越路径$\Gamma \left( {{x_i}} \right)$与目标路径${\Gamma _0}$相同节点的个数,用其除以目标路径的节点数来计算,该值越大,个体越优;分支距离为branch_distance(x_i),计算方法与Tracey方法相同.为了权衡其与层接近度的大小,并统一为最大化运算,将其采用${1.001^{ - branch\_distance({x_i})}}$进行规范化,其值越大,个体越优^[20].

于是,个体x_i的适应度fit(x_i)可表示为

$fit({x_i}) = approach\_level({x_i}) + {1.001^{ - branch\_distance({x_i})}}$

(9)

个体x_i的穿越度越大,其适应度应越大.因此,将个体的穿越度作为权重调整原来的适应度,得到新的适应度函数为

$f({x_i}) = fit({x_i}) \cdot P'({x_i}) = fit({x_i}) \cdot \sum\limits_{j = 1}^n {(P({v_j}|\bar \Gamma ') \cdot {\theta _j})} $

(10)

从而得到基于不可达路径节点出现概率的路径覆盖测试数据自动生成方法.

2.3 性能分析

假设种群进化到某一代,有两个个体x₁和x₂穿越的路径分别为$\Gamma \left( {{x_1}} \right)$和$\Gamma \left( {{x_2}} \right).\Gamma \left( {{x_1}} \right)$和$\Gamma \left( {{x_2}} \right)$分别与目标路径相比,两条路径穿越目标路径的节点只有第i和第j两个节点不同,即,个体x₁穿越目标路径的第i个节点,个体x₂穿越目标路径的第j个节点,其余节点均相同.按照公式(9)适应度计算方法可得fit(x₁)=fit(x₂).如果第i个节点在不可达路径中出现的概率大于第j个节点在不可达路径中出现的概率,即$P({v_i}|\bar \Gamma ') > P({v_j}|\bar \Gamma ')$,则由公式(8)可得:个体x₁的穿越度大于个体x₂的穿越度,即P'(x₁)>P'(x₂).也就是说,在传统适应度计算相等的情况下,由于两个个体的穿越度不同,导致本文方法对应的适应度调整权重不同.按照本文方法,由公式(10)可得个体x₁和x₂的适应度分别为:

· f(x₁)=fit(x₁)·P'(x₁);

· f(x₂)=fit(x₂)·P'(x₂).

即:两个个体的适应度不同,f(x₁)>f(x₂).

因此,根据个体的穿越度调整个体的适应度,可以使穿越难以覆盖节点的个体获得较高的适应度,在后续进化过程中得以有效的保留,从而提高了生成覆盖目标路径测试数据的效率.

本文采用遗传算法生成测试数据,算法的时间复杂度主要考虑适应度函数的计算.由公式(10)可知:适应度的计算主要取决于个体穿越度的计算,此值在于统计不可达路径节点出现的概率.节点在不可达路径中出现的概率在检测不可达路径的过程中得到统计计算,其概率值始终保持不变,无需重复计算.因此,本文方法降低了算法的时间复杂度.

2.4 算法步骤

步骤1. 对算法所需的控制参数赋值,插装被测程序;

步骤2. 检测不可达路径,确定割点;

步骤3. 初始化种群;

步骤4. 对进化个体解码,执行被测程序;

步骤5. 判断进化个体是否穿越目标路径:若是,保存进化个体,转至步骤9;

步骤6. 判断是否达到最大进化代数:若达到,转至步骤9;

步骤7. 按公式(10)计算进化个体的适应度函数;

步骤8. 对种群实施选择、交叉和变异操作,生成子代种群,转至步骤4;

步骤9. 停止种群的进化,解码保存的进化个体,输出测试数据.

3 实 验

本节通过实验进一步检验本文所提方法的有效性.首先给出实验需要验证的问题;然后介绍两组实验所用的程序,第1组为基准程序,第2组为工业用例,并给出实验结果和分析.

3.1 需要验证的问题

本文研究的目的是基于不可达路径节点出现的概率设计适应度函数,进一步提高路径覆盖测试数据的生成效率,需要验证的问题如下:

问题1. 利用本文方法设计适应度函数,能否提高生成测试用例的效率?

验证方法:通过比较本文方法与同类方法的评价次数和运行时间进行验证.

问题2. 利用本文方法生成测试用例的有效性如何?

验证方法:主要通过生成测试用例的成功率进行验证.

问题3. 测试数据的输入范围是否影响本文方法的有效性?

验证方法:在搜索空间爆炸性增长的情况下,进一步验证本文方法性能的优越性.

3.2 实验程序

为了验证本文方法的性能,每组实验结果都与同类方法(即文献[2, 21]中方法)的结果进行比较分析.同类方法的选择依据是均使用分支距离和层接近度相结合作为适应度函数,并且均采用遗传算法进化生成测试数据,与其对比,可以更好地验证本文方法生成测试数据的效率.为了降低随机性误差,3种方法采用相同的实验参数、相同的种群规模和相同的初始种群,比较3种方法找到覆盖目标路径测试数据的评价次数、运行时间和成功率.实验条件:Windows XP操作系统,VC++6.0仿真环境,计算机主频2.80GHz,内存2GB.

3.2.1 两个基准程序

两个基准程序分别选择三角形分类程序和冒泡排序程序.首先,检测两个程序的不可达路径,确定割点;然后,采用遗传算法自动生成覆盖目标路径的测试数据;最后,将本文方法与同类方法对比,以验证本文方法的有效性.

(一) 三角形分类程序

三角形分类程序的源代码与控制流图如图 2所示.

(1) 判定条件语句的相关性.

程序输入变量为{a,b,c},取值范围为0~300之间的整数,样本容量为50,设定{a,b,c}能构成等边或等腰三角形的概率均为0.1.三角形分类程序中条件语句间的相关性实验数据见表 1^[14].

(2) 由条件语句间的相关性检测三角形分类程序中的不可达路径,确定割点,实验数据见表 2.

三角形分类程序中,全部路径40条,不可达路径22条.其中,割点为v₁,v₅,v₉和v₁₃.

(3) 统计三角形分类程序节点(不考虑割点)在不可达路径集中出现的概率$P({v_i}|\bar \Gamma '),$实验数据如下:

$\begin{array}{l} P({v_2}|\bar \Gamma ') = P({v_3}|\bar \Gamma ') = P({v_4}|\bar \Gamma ') = \frac{{12}}{{22}},P({v_6}|\bar \Gamma ') = P({v_7}|\bar \Gamma ') = P({v_8}|\bar \Gamma ') = \frac{{15}}{{22}},\\ P({v_{10}}|\bar \Gamma ') = P({v_{11}}|\bar \Gamma ') = P({v_{12}}|\bar \Gamma ') = \frac{{10}}{{22}},P({v_{19}}|\bar \Gamma ') = \frac{{12}}{{22}},P({v_{14}}|\bar \Gamma ') = \frac{1}{{22}},\\ P({v_{15}}|\bar \Gamma ') = P({v_{16}}|\bar \Gamma ') = \frac{{21}}{{22}},P({v_{17}}|\bar \Gamma ') = \frac{{15}}{{22}},P({v_{18}}|\bar \Gamma ') = \frac{{21}}{{22}}. \end{array}$

(4) 应用遗传算法生成测试数据.个体采用二进制编码,轮盘赌选择、单点交叉、单点变异,交叉和变异概率分别为0.9和0.3.根据个体的穿越度计算适应度函数,对三角形分类程序中的可达路径生成测试数据.为确保实验条件基本相同,本组实验每种方法均运行15次,目标路径选择等边三角形路径$\Gamma $₀={s,v₁,v₅,v₉,v₁₃,v₁₅,v₁₆,v₁₇,v₁₈,e},输入数据范围分3种,选择不同的种群规模和最大终止代数,本文方法与文献[2, 21]中方法进行比较,实验结果见表 3.

由表 3可以看出:

① 从评价次数来看,在3种方法中,本文方法以最少的评价次数成功生成了测试数据.如在数据范围为[1, 512]时,本文方法的评价次数为29 180.3,文献[2]中方法的评价次数为30 540.7,文献[21]中方法的评价次数为1 225 290.3.本文方法与文献[2]中方法均采用调整适应度函数的方法,所以评价次数相差不大;但文献[21]中方法约是本文方法的42倍.另外,两种数据范围得到的结果类似,说明本文方法的性能明显优于同类方法;

② 从运行时间来看,本文方法的运行时间明显少于文献[2, 21]中方法.特别是,随着数据范围、种群规模和最大代数的增加,本文方法的优势更加明显.这是因为,本文方法只需计算1次节点在不可达路径中出现的概率就可以调整适应度函数,能够较快地生成最优解,说明本文方法生成测试数据的效率明显高于同类方法;

③ 从成功率来看,随着数据范围、种群规模和最大代数的增加,本文方法的评价代数和运行时间也有所增加.但是本文方法仍能有效生成测试数据,而且生成测试数据的成功率为100%,说明本文方法具有有效性.

为了进一步验证本文方法性能的优越性,在搜索空间呈爆炸性增长的情况下,选择三角形分类程序在更大的输入范围进行实验.在种群规模不变的情况下,仍以等边三角形路径为目标路径,实验设置及结果见表 4.

由表 4可以看出:在数据范围变大,导致搜索空间爆炸性增长的情况下,本文方法的性能如下:

① 文献[21]中方法在搜索空间爆炸性增长的情况下,生成测试数据的概率逐渐降低.数据范围在[1, 8192]情况下,成功率仅有6.67%.说明文献[21]中方法在搜索空间爆炸性增长的情况下很难奏效;

② 本文方法和文献[2]中方法的成功率均达到了100%,但在评价次数和运行时间上,本文方法明显少于同类方法,说明本文方法对测试数据的生成效率仍有所改进.

(二) 冒泡排序程序

冒泡排序也是验证实验的基准程序之一,其特点包含循环结构,功能是对数据进行排序.程序输入变量为8个[1, 65535]范围内的数据,该程序包含两个相互嵌套的循环语句,其中嵌套一个条件语句.种群规模为50,最大终止代数为1 000,3种方法独立运行15次,得到的实验结果见表 5.

由表 5可以看出:从评价次数来看,在含有循环结构的基准程序中,本文方法的评价次数更具优势,还不足文献[21]方法的一半,而且对于文献[2]方法来说,本文方法的评价次数也较少;从运行时间来看,由于本文方法计算量的减少,运行时间明显少于同类方法,本文方法的运行时间为0.089 3,文献[2]中方法的运行时间为0.140 9,文献[21]中方法的运行时间为0.178 1;从成功率来看,本文方法和文献[2]中方法均达到了100%,而文献[21]中方法只有86.7%,说明本文方法可以有效地生成测试数据.

3.2.2 工业用例

为了进一步验证本文方法的有效性,选择4个工业用例进行实验.程序描述及参数设置见表 6.

本组实验设定每种方法各运行50次,分析评价次数、运行时间和生成测试数据的成功率.实验结果见表 7.

由表 7可以看出:从评价次数来看,在工业用例中,本文方法的评价次数仍少于同类方法;从运行时间来看,本文方法的优势更加明显,对于复杂用例flex来说,本文方法的平均运行时间为62.321 7s,文献[2]中方法的平均运行时间为89.741 2s,文献[21]中方法的平均运行时间为103.436 7s,本文方法比文献[2]中方法少用27.419 5s,比文献[21]中方法少用41.115 0s,可见,本文方法在运行时间上的优势非常明显;从成功率来看,本文方法和文献[2]中方法均达到了100%,而文献[21]中方法对于程序repalce,sed和flex只有66%、46%和36%的成功率,说明本文方法能够很好地生成测试数据.

由以上的基准程序和工业用例实验,充分验证了本文方法生成覆盖路径的测试数据的有效性,并且验证了本文方法能够提高生成测试数据的效率.

4 结 论

本文给出了一种依据不可达路径节点出现概率计算个体穿越度,进而调整个体适应度函数的路径覆盖测试数据的生成方法.本文方法在检测不可达路径时,统计节点在不可达路径中出现的概率,从而计算个体的穿越度,设计适应度函数,使得穿越度较高的个体在进化中得到保留,有效提高了生成测试数据的效率.实验结果表明,本文方法与同类方法相比生成测试数据的效率较高.

本文研究的是覆盖单目标路径测试数据进化生成问题,今后将进一步研究覆盖多目标路径测试数据生成问题.

致谢 在此,向对本文工作给予支持和建议的评审专家表示衷心的感谢.