遗传算法在测试用例最小化上的应用

第1页共6页遗传算法在测试用例最小化上的应用摘要：回归测试是软件测试过程中的一个重要阶段。测试数据生成的自动化和消除冗余对减少软件测试成本具有十分重要的意义。本文提出了用于测试用例最小化的遗传算法，其中讨论了编码策略和遗传算子的改进，并实现了该算法模型，最后对算法进行了实例研究。实验结果表明，该遗传算法能够有效缩减测试用例集的大小，有效降低回归测试成本。关键词：回归测试；测试用例最小化；最小测试覆盖；遗传算法TheGeneticAlgorithmForTestSuitsMinimizationAbstract：Theregressiontestisoneofimportantstageofthesoftwaredevelopmentlifecycle.Theautomationofsoftwaretestingcaseandtheminimizationbecameveryimportanttoreducetheregressiontestcost.Finally,thispaperprovidethegeneticalgorithmassearchpolicytochosetheminimizationtestcase.andanalyzesoftheperformancesofthealgorithms.anddiscusssuchascodingstrategy,operatorevolution.TheexperimentresultsshowthatourGeneticAlgorithmcanreducethesizeoftestsuiteeffectivelyandsignificantlylowdownthecostofregressiontest.Keywords：regressiontest;testsuiteminimization;minimizedtestsuite;GeneticAlgorithm1引言在软件开发过程的测试阶段，代码修改后、软件硬件平台变更后或硬件配置改变后，都必须进行回归测试。然而，对大多数的测试小组来说，回归测试占用了很大一部分的时间，特别是在软件开发生存期的最后阶段。一般的做法是将曾经用的测试用例保存起来，形成测试用例库，在进行下一次回归测试时，运行用例库中的所有用例。然而随着软件的不断修改，测试用例仓库不断地增大，回归测试成本也随之增加。研究测试用例最小化，就是从原始测试用例集中提取出最小数目的测试用例集，使得在运行这些测试用例时，能够达到运行原始用例的测试覆盖率。遗传算法从问题可能解集出发按照适者生存、优胜劣态的遗传规律，逐代生成越来越优化的近似解。它作为一种高效的搜索优化算法，在解决大规模，复杂度高的问题上具有独特的优势和性能。因此，把它引入到测试用例的最小化选择上将非常有效。2测试用例最小化当我们通过测试发现程序中的错误后，就必须立即改正这些错误，然后对改正后的程序重复以前做过的各种测试，以保证没有出现新的错误，同时还要再测定覆盖率，以保证能达到既定的覆盖率。但是，通常情况下，我们设计的一组测试用例所获得的覆盖率很有可能只需其中的几个测试用例就可以获得了，那些冗第2页共6页余的测试用例在每一次重新测定覆盖率时都浪费了大量的时间和资源。选取最小的测试用例集达到相同的覆盖度就是测试用例最小化。我们把用例抽象表示成n长的二进制串：f:{x1,x2,x3…xn}-{10010…1}其中1表示该测试用例测试过其软件对应的模块，0表示没有测试的软件模块。这个用例的生成，我们经过测试软件的插装来生成一个数据文件。我们定义1的个数在整个二进制串的百分比为这个用例测试软件的覆盖度，即测试到软件的模块数。我们把模块在这里抽象定义为段。3测试用例的生成和遗传算法的建模3.1覆盖率数据库文件覆盖率数据库文件保存每次运行被测软件时，源程序的各个记录点对应的程序块是否运行过的信息。覆盖率数据库文件如图1所示，结构描述如下。m_lValidBitNumberm_lLongIntNumberCCase[1]....Ccase[n]图1覆盖率数据库文件结构在覆盖率数据库文件头上依次保存着两个unsignedlong型数据：longm_lValidBitNumber;longm_lLongIntNumber;1.m_lValidBitNumber：源文件包含的记录点个数（就是段数）。2.m_lLongIntNumber：我们用一位(bit)数据表示一个记录点所对应的程序块在一次运行时是否被执行过的信息（值为1表示执行过，值为0表示未执行过），m_lLongIntNumber这个域的值就是保存源程序中所有记录点的是否被执行过信息所需的long型数目。实际计算方法就是：m_lLongIntNumber=(m_lValidBitNumber+31)/32。在两个长整形之后，就依次是一个CCase结构体。每个CCase结构体保存一次运行被测程序时各个记录点所对应的程序块的执行情况。CCase结构体如下：structCCase{longlTime;longlAuxiliaryTime;long*plData;//totalnumber:m_lLongIntNumber*4};lTime：本次运行被测程序的时间。lAuxiliaryTime：辅助时间位。plData：连续m_lLongIntNumber个long型数据。每一位(bit)数据表示一个记录点所对应的程序块在一次运行时是否被执行过的信息：值为1表示已执第3页共6页行过；值为0表示未执行。对应于源程序中的记录点（段点）顺序，每一个long型数据从高位记录到低位。3．2对测试用例建模测试用例最小化的原理和意义已在前面描述过，下面讨论用遗传算法来实现测试用例最小化。在数据覆盖文件中记录下源代码每个段在各个测试用例执行过程中的运行次数，并将统计数据保存在如图2所示的“段执行历史图”中。“段执行历史图”中，值为1表示该段已执行，值为0表示未执行。段执行历史图段1段2……段n……测试用例110……1……测试用例200……0……………………………………测试用例n01……1……………………………………图2测试用例覆盖段图整个测试用例库文件达到的覆盖度定义为req(r)=niija1/n......(公式1)。此覆盖度函数将作为遗传优化算法中的目标函数。4遗传算法的实现从测试用例最小化的算法我们可以得知算法得难点在于：如何尽快有效地确定最小覆盖点。也就是说以什么最有效的途径寻找最小覆盖点是我们设计的关键之处。4.1遗传算法在测试用例模型上的实现下面给出了遗传算法在该问题上的算法实现：（1）初始化编码：采用多参情况下的的编码方案。计算开始时，随机生成一定数目N个个体（父个体1，父个体2，父个体3，父个体4…….）。用2进制1、0来编码1个父个体。F{x1,x2,x3..xn}-{c1,c2,c3…cn}。后面的变异和交叉操作只要改变二进制编码的结构，如1变成0，0变成1。以种群形式存在的参数编码集通过加载遗传算法的寻优操作后，在进行解码。所得到的参数集就是提供的测试用例优化后的解集。（2）计算个体适应度值：如何定义适应度函数，是遗传算法解决问题的关第4页共6页键，评价函数的优劣将直接影响到解决问题的效率。取每个个体，计算“1”的个数占在n段中位数总和的百分比，作为整个优化的适应度函数。定义为个体覆盖度：i_req(x)=niicount1][/n…(公式2)。（3）选择：适应度越大表示这个个体越好。根据适应度大小顺序对群体中的个体进行排序。在实际计算时，按照每个个体顺序求出每个个体的累积概率。p(i)=其中i为个体排序序号。q是一个常数,表示最好个体的选择概率。miip1=1，若i_req(x1)i_req(x2)则p1p2然后随机产生一个随机数，进行个体选择。显然适应度大的选种的概率大，然后去替换适应度小的个体。适应度高的个体直接保存到下一代中。（4）交叉:随机挑选经过选择操作后种群中两个个体作为交叉对象，根据交叉概率p[i]两两进行交叉操作,这个操作重复进行直到全部个体已交叉。交叉过程是随机产生一个交叉位置pos,从位置pos到个体的末位进行交叉。在实验中选取p[i]=0.8，通过大量实验数据分析，具有较高的优化效率。（5）变异：以往的遗传算法都采用静态的变异率。整个二进制编码按照一定的变异率进行在某位进行突变。考虑到测试用例库里测试用例的大小。我们提出适时交叉概率rMutate(i)：按照种群大小动态地进行变化,采取自适应遗传算法的策略。这个改进在保持群体多样性的同时，保证了优化的收敛性。（6）在开始时，设置最大的进化代数max_gen做为进化的终止条件。等进化完成后，把最好的个体输出，就是我们的优化解：最小化的测试用例。在实验中我们设置max_gen=180。4.2仿真实验性能分析首先，我们对每个从原始数1到用例数80进行最小化选择，对原始用例的花费时间和运行时间和最小化选择的后花费时间和运行时间进行采集。结果遗传算法在测试用例越大时，花费时间（cost）有很大的缩减，有效缩减测试用例集的大小，有效降低回归测试成本。中间有个峰值，是因为在随机选择用例时候，覆盖度在同一个段的重复度较高。解决方法是需要在随即产生用例的时候根据覆q(1-q)1ii=1,2,…..m-1(1-q)1mi=m0.02size250.01525size350.0135size600.00960size700.004570size900.0020其它rMutate(i)=(size：初始种群数)第5页共6页盖度进行选择，这个排序时间也是很大的一个开销。考虑到综合因素，还是随机产生用例比较合理。图3用折线来表示遗传算法的选取最小化用例的花费时间。为了更加直观地看出它的效率，图中也列出了贪心算法进行比较。除了以上这个例子，我们还进行了多次测试，发现遗传算法实际效果在初始用例很大的情况下，效率提高非常明显。图3遗传算法与贪心算法性能比较为了实际验证遗传算法对测试用例库优化选择后手节省的时间，我们做了大量实验，实验过程如下：我们从覆盖文件中随机选初始用例，然后计算其测试花费时间，取优化前后的加权平均值进行比较BeforeCost=niit1][cos/n...(公式3)。AfterCost=cost[j]+..+cost[k]/m（公式4）,其中j..k是优化后用例，m是优化后的用例数，实验结果表明，初始用例数越大，优化挖掘后，节省花费时间更大，所以应用于回归测试所生成的庞大测试用例集合的优化选择上效果甚佳。对于实验数据如表1所示。表1优化前后测试花费时间比较初始用例数优化前测试花费时间(ms）遗传算法优化后花费时间(ms)10306972057175第6页共6页30747804012308150144679601646807018678180220182902451865总结本文主要对遗传算法在测试用例最小化上的应用进行了研究，其主要贡献总结如下：实现了用遗传算法建模实现测试用例最小化选择的功能。并对这种算法进行了改进，有效地缩减了选取测试用例集的花费时间，减少了回归测试成本。以上技术可应用于实际软件测试自动化中，但是克服各种编程语言间的差异，还有许多工作要做。参考文献[1]张文栓,滕奇志,罗代升.SAGA在软件测试数据自动生成中的应用.信息与电子工程,2005.1.[2]王小平，曹立明.遗传算法——理论、应用与软件实现.西安交通大学出版社,2002.[3]武兆慧,张桂娟,刘希玉.基于模拟退火遗传算法的关联规则挖掘.计算机应用,2005.5[4]刘刚,何麟书.双赌轮选择遗传算法.北京航空航天大学学报,2005.8.[5]姚砺.面向对象软件测试的研究.博士论文.浙江大学,2002.11.[6]JonesBF,SthamerH,EyresDE.Automaticstructuraltestingusinggeneticalgorithms.