利用遗传算法进行测试用例自动生成

1、利用遗传算法进行数据流分析下的测试用例自动生成摘要： 软件测试越来越受到重视，但是软件测试是一个复杂、工作量很大的过程。测试用例的自动生成在一定程度上能够减小软件测试的工作量， 但是测试用例自动生成技术是一个难点。 本文通过借鉴遗传算法，基于数据流分析，在 def-use 路径覆盖的测试准则上，提出了一个测试用例自动生成的算法。并通过实验比较了遗传算法和随机选择法在测试用例自动生成上的优劣。关键词：软件测试；数据流测试；遗传算法； GA测试用例自动生成中图分类号： TP311Automatic Test Data Generation for Data Flow Testing Using a

2、Genetic AlgorithmAbstract: Software testing is more and more important, but the software testing is complex and has heavy workload. The automatic generation of test cases can reduce the workload of software testing, but the automatic generation of test cases is a difficult problem. This paper introd

3、uces an automatic test case generation algorithm which uses genetic algorithm and is based on data flow analysis and is under the test criterion of the def-use path coverage. And compares the advantages and disadvantages between genetic algorithm and random selection method in the automatic generati

4、on of test cases.Key words: software testing; data flow testing; genetic algorithms; automatic test data generation1 引言软件测试描述一种用来促进鉴定软件的正确性、 完整性和质量的过程， 是一种实际输出与预期输出间的比较过程。 软件测试主要包含两方面的内容， 测试用例生成和测试充分性准则的应用。 测试充分性准则包括基于控制流和基于数据流等， 是用来判定测试数据集对于被测试程序是否充分的准则。 软件测试是一项费时费力且单调乏味的工作， 测试用例的自动生成能有效提高软件测试的效率。

5、但是， 测试用例自动生成是软件测试中的一个难点。 本文利 用遗传算法对测试用例的自动生成进行探讨。2 测试用例自动生成技术简介2.1 软件测试相关概念测试用例是为某个特殊目标编制的一组测试输入、 执行条件以及预期结果， 以便测试某个程序路径或核实是否满足某个特定需求。测试用例的设计应遵循下列原则 1 。（ 1）准确性：测试用例的设计必须有明确的目标，即针对需求设计测试用例。（ 2）可复用性：设计的测试用例应能在类似的情况下重复使用。（ 3）可追踪性：测试用例必须能够追溯到需求。（ 4）完整性：考虑到需求的完整性和逻辑完整性。测试用例自动生成方法可以分为三类，随机的测试用例生成，结构导向的测试用

6、例生成和基于数据规格说明书的测试用例生成。随机的测试用例生成从输入变量的域中随机产生测试用例。结构导向的测试用例生成基于覆盖程序中特定的结构元素，比如路径覆盖，分支覆盖和def-use 覆盖等。基于数据规格说明书的测试用例生成从软件的说明书中选择测试用 例。本文所使用的测试用例自动生成技术属于结构导向的测试用例自动生成技术，使用遗传算法(genetic algorithm )迭代生成覆盖全部 def-use路径的测试用例。 2.2软件测试的分类软件测试按照运行状态，可以分为静态测试和动态测试。其中静态测试是在不执行程序 代码而寻找程序代码中可能存在的缺陷或评估程序代码的过程。动态测试则以测试数

7、据为输入，通过执行程序来检验程序的动态行为和运行结果以发现缺陷。图1为软件测试分类的一个例子。本文的软件测试方法属于动态测试中的白盒测试，是基于数据流测试中的全定义使用覆盖。;购春泅试技术)I.M值至亘西) 口连藏而)5盘逑 次,控制而引a判定*动他分析全佗用覆盖图1软件测试技术的分类Fig.1 Classification of the software testing technologies3数据流分析技术程序的控制流可以表示出有向图的形式，其中每个节点表示可以顺序执行的语句，其中不包括分支，形成一个基本的语句块；每条边表示节点间控制流的可能的转移。路径就是由边连接起来的节点的有限序列。

8、完全路径指路径的第一个节点是程序的开始节点，最后一个节点是程序的终止节点。一个变量的def-clear路径指的是该路径中不包括改变量的一个新的定义。数据流分析把焦点放在变量的定义和使用上。而变量的使用又可以分为“c-use ”和“p-use"，c-use指的是变量被用来计算，而 p-use指的是变量被用来进行判定，是判 定语句的一部分。变量的c-use被和节点相关联，而p-use则被与边相关联。数据流分析的 目标就是找出变量的所有定义以及和该定义相关联的所有使用。这样的数据流关系可以被分为下面两类。dcu(i)和dpu(i,j) 。dcu(i)指的是这样一个变量定义的集合，存在一条到

9、节 点i上的def-clear 路径,而节点i包括该变量的一个 c-use ; dpu(i,j)则指的是这样一个变量定义的集合，存在一条到变量(i,j )的def-clear 路径，而该边包括一个该变量的p-use。Reach(i)指的是所有能到节点i的定义，也就是存在一条def-clear 路径,能从该变量 的定义节点到i节点。Avail(i)指的是所有在节点i可得到的变量定义，它既包括在节点i对某变量的定义，也包才所有能到达节点i并且在节点i上没有进行重新定义的变量定义。因此，dcu(i)和dpu(i,j)可由下式计算得到。dcu(i):= reach(i)- c-use(i);dpu(i

10、,j):=avail(i)- p-use(i,j)其中，c-use(i) 指的是在节点i上存在c-use的变量，p-use(i,j) 指的是在边(i,j ) 上存在p-use的变量。全路径就是指从每个变量的定义到该变量每个使用的def-clear 路径,他可以分成dcu-path和dpu-path两类。每个Dcu-path可以表示成一个定义节点，一个c-use节点，killing nodes集合。Killingnodes是指那些不能包含在 dcu-path 中的节点，也就是那些对变量的重新定义。Dpu-path可以表示成定义节点，一个p-use边以及killing nodes 集合。例如下图是

11、一个样例程序。其中语句旁的第一列数字是语句编号，第二列是语句所属节点的编号。1 1INTEGER X,Y,Z12 RELSE21READ(5,*)XtYjZ131F(X.GE.Y)THEN31MII>Z14gMID=Y41出(YLT0THEN1510ELSE52F(X.LT.Y)T1IEN16ioIF(X.GT.Z)TIIEN63MID=Y17iiMID=X74ELSE他12END IF84IF(X.LT2)THEN1913END IF95MID-X2014END IF106ENDJF2114PR1NT*JM】DDLE VALUE=* MIDII7END IF2214END图2样例程序F

12、ig.2 Example program其对应的dcu-path如下表。表1样例程序dcu-path列表Tab.1 List of the dcu-paths of the example programDcu-path 编号变量定义节点C-use节点Killing nodes1y13无2x15无3y19无4x111无5mid1143,5,9,116mid3141, 5,9,117mid5141,3,9,118mid9141,3,5,119mid11141,3,5,9其对应的dpu-patn如下表表2样例程序dpu-path列表Tab.2 List of the dpu-paths of th

13、e example programDpu-path 编号变量定义节点P-use 边Killing nodes1y11-2无2z11-2无3y11-8无4z11-8无5x12-3无6y12-3无7x12-4无8y12-4无9x14-5无10z14-5无11x14-6无12z14-6无13x18-9无14y18-9无15x18-10无16y18-10无17x110-11无18z110-11无19x110-12无20z110-12无4遗传算法简介4.1 遗传算法相关概念简介遗传算法借鉴了自然界中的适者生存以及遗传学中的交叉变异现象。遗传算法从一个群体中选出一部分适应度较高的个体，以一定的概率对选出来

14、的个体进行交叉和变异操作。通过遗传操作，使优良品质被不断保留、组合，从而不断产生出更佳的子个体，子代个体中包含父代个体的大量信息，并在总体上胜过父代个体，从而使群体向前进化发展。经过不断迭代，将会产生满足要求的群体，或者在迭代次数达到一定值时，停止算法。交叉操作就是交换两个染色体中的部分内容，变异操作是改变某个染色体的部分内容。遗传算法的有关概念术语定义如下。个体：模拟生物个体而对问题中的对象(本文中是一个测试用例)的一种称呼。种群：模拟生物种群而由若干个体组成的群体(本文中是一组测试用例)。适应度：借鉴自然界中生物个体对环境的适应程度，而对问题中的个体对象所涉及的表征其优劣的一种测度。染色体

15、：问题中个体的某种字符串形式的编码表示。编码与解码：遗传算法中两个必须的数据转换操作，把搜索空间中的参数或解转换成遗传空间中的染色体的操作成为编码，反之为解码。遗传算法的整体结构如下。Simple Genetic Algorithm。Initialize population;Evaluation population;While termination criterion not reached Select solutions for next population; Perform crossover and mutation; Evaluate population;4.2 编码操作染

16、色体编码需要遵循以下几个原则：2(1)输入参数所能取得的任何值都应存在相应的唯一编码。(2)任何一个编码都应存在唯一的参数值与之对应。(3)选择使问题得以自然表达的最小字母表进行编码。(4)编码方法应和问题本身的相关性大、结合紧密。根据这几个原则，我们设计了对应的编码方法。假设我们有k个变量，每个变量的取值范围是Di=ai,b,再假设每个变量的精度是di，为了达到这样一个精度 R应该变成(bi-3)*10di。mi应该取值成一个最小的整数，满足(bi- a) *10di <= 2吸1。这样每个变量就可以 被表示成长度为mi的0-1字符串。将这个字符串转换成原数据的方法如下公式。, bi

17、- ai Xi = ai + Xi * (2Ami) -1例如，假设有变量 x, y, -3.0<=x<=12.1, 4.1<=y<=5.8,且需要的精度是 4,也就是保留4位小数。X的定义域的长度是12.1- (-3) =15.1。所以我们希望编码后的字符串的长度能够 表示15.1*10000。此外，2A17 < 151000 <=2A18 ,所以mx应取值18,也就是用 18位0-1字 符串对x进行编码。同理可得，my应取值17,所以对x,y进行编码需要33位长的字符串。假设对x,y编码后的字符串是 010001001011010000111110010

18、100010 ,此时前18位表示的 是x,后17位表示的是y。有上式计算可得，x = 1.0542, y=5.7553。4.3 适应度的计算对种群的初始化就是随机产生个pop-size个m位的0-1字符串，其中pop-size是种群的大小。算法根据每个测试用例新覆盖的def-use路径的数量来计算对应的适应度。测试用例m的适应度计算方法如下。1.1 新覆盖的def - use路径数量 eVal(Vi)=总共的路径数量适应度是遗传算法唯一的反馈。当某测试用例的适应度大于0时，我们认为这个测试用例是有效的。4.4 个体的选择从有效的个体中选择一部分以产生下一代种群，当种群中没有有效的个体时，我们将

19、选择整个种群以产生下一代种群。选择的方法主要有两类，轮盘选择法和随机选择法。轮盘选择法将一个圆分为种群大小个扇形区间，区间大小与该区间所代表的染色体的适应度成正比。设一固定指针，转动轮盘，等其停止后，指针指向的区间对应的染色体即被选中。轮盘的创造算法如下。(1)计算每个染色体的适应度eval(v i) o(2)计算整个种群的适应度F = £ iyeevalWi)。(3)计算每个有效染色体被选中的概率pi = eval(v i)/F 。 P也是染色体占据的扇形面积的比例。(4)为每个染色体计算一个累计概率qi = £ ijpj。选择一个染色体的算法如下。(1)随机产生一个 0

20、到1之间的浮点数r。(2)如果r < q 1,就选择染色体v1,否则如果qi-1 < r <=q i,那么就选择染色体 vi。重复pop_size次，就选择了 pop_size个染色体参与遗传操作。随机选择法就是从有效染色体中随机选择pop_size个参与遗传操作，每个染色体被选中的概率相等。算法如下。(1)假设有效染色体的个数是l ,那么将染色体从 0到l编号。(2)随机产生一个 0到l之间的整数，选择相应编号的染色体。重复这个过程pop_size次，就选择了 pop_size个染色体参与遗传操作。4.5 遗传操作遗传操作有交叉和变异。交叉操作指通过一对双亲个体中的遗传信息

21、进行随机重组，产生与双亲遗传信息相同、 组合不同的新个体。交叉操作分为单点交叉和多点交叉，如下图 3。图3单点交叉Fig.3 One-point crossover图4多点交叉Fig.4 Multi-point crossover本文采用的是单点交叉。在进行交叉操作前，还要先选取要进行交叉操作的染色体。选取染色体根据概率 pc进行，取值范围通常是0.40.99。选取染色体的算法如下。(1)为每个染色体进行下面两步的操作。(2)随机产生一个 0到1之间的浮点数r。(3)如果r < pc,就选取相应的染色体。由此，我们选取了要进行交叉操作的染色体。对每一对染色体，算法随机产生一个区间在1,m

22、-1的整数pos以表示交叉操作的起始位置，其中m是染色体的长度。对染色体b1b2, bposbpos+1, bm和 Ci, CposCpos+1 , Cm进行父叉操作后，变换为b1b2, bposCpos+1, Cm和Ci , Cposbpos+1, bmo变异操作指单独改变个体内一个或者多个基因座上的基因而产生新的个体。变异发生在染色体的各个位上，根据一个变异概率pm进行变异，取值范围通常是0.00010.1 ,所以期望的变异位数是 pm*m*pop_size。每个染色体的每一位都有相同的概率变异。对交叉操作后 的每个染色体在每一位上进行如下操作。(1)随机产生一个 0到1之间的浮点数r。(

23、2)如果r < pm,则对该位进行变异操作，将 0变异成1或将1变异成0。5实验分析程序结果用到一个整型的向量，叫做 define-use coverage vector ,用于记录每个 def-use路径对应的测试用例。样例程序对应的define-use 覆盖向量如下表。表3样例程序的def-use覆盖向量Tab.3 The def-use coverage vector of the example programDcu-path123456789测试用例31029131029Dpu-path12345678910测试用例33113310101010Dpu-path111213141

24、51617181920测试用例121222119911其中，测试用例对应的编号是程序运行过程中测试用例生成时的顺序。上表是利用遗传算法自动生成测试用例的结果。为了比较遗传算法和随机算法在自动生成测试用例方面的优劣，实验在15个FORTRAN程序上分别运行遗传算法和随机法。其中遗传算法设定 pc = 0.8,pm = 0.15。得到的程序运行结果如下表。表4遗传算法与随机算法的比较Tab.4 A comparison between the GA technique and the random testing technique程序编号变量个数种群大小方法迭代次数测试用例个数覆盖率138遗传算

25、法46100随机算法26100238遗传算法16100随机算法27100338遗传算法34100随机算法354100438遗传算法164100随机算法284100538遗传算法18681.3随机算法26681.3648遗传算法38100随机算法58100738遗传算法45100随机算法9151008310遗传算法151063.6随机算法51958.4928遗传算法13100随机算法441001018遗传算法75100随机算法351001118遗传算法2592随机算法45921238遗传算法55100随机算法9151001324遗传算法5396随机算法23961418遗传算法2663.6随机算法

26、15663.61538遗传算法81187.2随机算法16981.7从上表可以发现遗传算法有12个运行的都比随机算法好， 其中有10个只需要更小的迭代次数就能达到相同的覆盖率而第8个和第15个，遗传算法使用了更少了迭代次数达到了更高的覆盖率。所以，遗传算法的性能优于随机算法。为了比较遗传算法中，轮盘选择法和随机选择法的优劣，实验在上述的15个程序中运行了分别采用轮盘选择法和随机选择法的遗传算法，实验结果如下。表5轮盘选择法和随机选择法的比较Tab.5 A comparison between parent selection methods used in the GA technique程序编号选择方法迭代次数测试用例个数覆盖率1轮盘选择法46100随机选择法461002轮盘选择法16100随机选择法161003轮盘选择法34