随着软件行业的快速发展，软件测试的作用也越来越大，自动化测试用例生成方法也越来越多。如何找到一种高效的测试用例生成算法，一直是测试领域关注的热点。提出了一种基于碰撞域检测优化的测试用例生成方法，生成的测试用例能规避大量的冗余测试用例产生，因此该算法在短时间内能将代码的语句覆盖度收敛到一个较为满意的值；同时通过半径的动态调整，保证算法的覆盖度逐级上升，结合遗传算法对高覆盖率的测试用例进行交叉变异，快速找到有效的测试用例数据。实验证明，该算法的性能相比于传统随机法有较大的提升，而且参数的范围越大，效果越好。
第1期 杨丰玉,等:基于碰撞域检测优化的測试用例自动生成方法 137 成在碰撞域里的测试用例予以舍弃。 生的测试用例的某一位参数a发生了变异,变成了a#,a#是参 碰撞半径的本意就是过滤掉可能产生重复覆盖路径的测数范围里的任意数。 试用例,低覆盖率的测试用例碰撞半径大,高覆盖率的碰撞半 交叉 径小,表小对于低覆盖度的测试用例期望更低,也是为了避免 桕对高覆盖度的测试用例 产生低覆盖率周围的点,同时希望多产生高覆盖率周围的点 新产生的测试用例 碰撞半径如图3所示。 图3碰撞半径图两轴坐标分别为参数范围,矩形碰撞半径 交叉后产生的测试用例:a1b2 代表了测试用例碰撞半径,虚线矩形框代表了所有测试用例的 变异 新产斗的测试用例 氾围。 a# 变异后的测试用例 3)碰撞半径的自适应 生成在测试用例碰撞域里的测试用例记为碰擅,一旦碰 图5测试用例交叉变异图 擅,会记录碰撞次数。当连续碰撞次数到了一个阈值Cm,可2算法实现 以认为在这个参数范围里已经生成了足够多的测试用例,导致 了连续碰撞。此时,算法会减小碰撞半径,以此来收缩碰撞域,2.1主要算法 生成之前可能被过滤的测试用例,促使语句覆盖率逐级上升 算法主要包含参数文件配置、碰撞半径下调、测试用例碰 达到预期值 撞似测等,伤码如下 由前文可知,参数范围缺省值为Clu,则将碰撞域的初 BeginsetConfigPara//设置配置文件信息 始碰撞半径R1m设为C2,每次下调的值是当前值除2, getrelatedpara 获取参数参考值 碰撞半径的调整式如下 hile( Coverage< e Covera")//小于预期覆盖度 产生测试用例 此处参考希尔排序的初始化以及半径调整,目的是在参数 if Collision碰撞 范围过大的情况下,提高半径下调速度,避凭迭代次数过多。 Collisition Time++//累计碰撞次数 在最糟糕的情况下,碰撞半径会下调到1,此吋产生的测试数 I Collision'time>Cma/超过阈值 then rran=Bmg2//下调碰撞半径 据为一个个离散的点,抛开遗传算法,效率上等价丁随机法,对 CollisitionTime=0//重置碰撞计数器 于整型参数,能覆盖到参数范围的所有值。 T VARI< Randomly/是否变异 懂撞半径下调如图4所示。 then variation//变异 if cross< Random Cr//是否交叉 交叉 撞半 22实例分析 角形形状检测是测试领域中经典的测试模型4,以评 估测试效率与正确性。测试包含着等边三角形、等腰三角形、 图3砷撞半径示意图 图4碰撞半径下调示意图 直角三角形和非三角形 图4中的!1点是t1碰撞半径下的测试用例,涵盖1的范 在验证论文测试算法,选取三角形形状检测为例,实例代 围是t1的测试用例碰撞半径,达到碰撞阈值俏时,碰撞半径除2,码如下 对比于t2 #1 include〈 stdio.h〉 4)交叉变异 t2 void triangle( int a, int b, int c)3 对于被测代码,本文假定把一个具有高覆盖率的测试用例 #3if(a+b>c‖a+c<b‖b-c<a) 定义为优秀,把一个具冇低覆盖率的测试用例定义为糟糕。在 # printf(“ not triangle”) 5 else if(a ==e & a==b) 个多参数的測试环境中,一个相对优秀的测试用例其各个参 书6 printf(“ equilateral triangle”) 数均是相对优秀的,由于一个或几个变量的取值不善导致无法 7 else if((a==b&&a! =c)I(a==c&&b! =c)li(b==c&& 得到一个较高的覆盖率,所以高覆盖率携带的参数信息是极具a!=c)) 参考意义,试着在高覆盖率的测试用例上修改某一位,或者用 8pin(“ isosceles triangle” 高覆盖率的测试用例上的几位参数替换新生成的测试用例上 #9 else if(a*a+b来b==Cxc|b*b+cxe==a米a|a米a+c米 的参数,往往能加快牧敛速度,所以本文把关注点放在优秀的C 测试用例上。在遗传算法的每一代中选择出优秀的测试用例 #10 printf(“ right- angled Triangle”) 并在它身上集屮作交又变异,有助于产生一个较高覆盖率的测 #11} #12 else 3 试用例,对应如图5所示。 #13 printf(“ normal triangle”) 图5说明了交叉和变异的整个过程,在交叉过程中,新产 #14 生的测试用例和一个相对高覆率的测试用例后两位参数进行 了交换,产生了交叉后的新测试用例。在变异的过程中,新产 #16 int main( int arge, const char s argv[1) ·138 计算机应用研究 笃35卷 为85%、90%、100%,参数范围选取了20、50、100500来观察 fi8 returm 0 不同的参数范围对算法效率的影响。图7、8分别说明了相同 #19 代码预期覆盖度下,不同的参数范围以及相同的参数范围与不 算法在产生测试用例时,会对新产生的测试用例进行需区同代码预期覆盖度下,相同的参数范围下两种算法生成测试用 半径的检测,以此界定产生的用例是否为冗余的测试用例。具例次数的对比。 体流程如图6所示。 图7以三角形形状检测为被測代码实例,选取預期覆盖度 为85%以及参数范围为20、50、100、500为测试要求。图中随 配置文件二边K(参考值 生成新用例 用例有效 机法参数为50-500,相较于参数范围20花费测试用例次数 碰撞半径10 =6 =7 8 大幅增大,而对于本文算法并没有明显增加。 triangle 图8以三角形形状检测为被测代码实例,选取参数范围为 参数范20边长考1成新用例生成用例碰掉径20以及预期覆盖度为8%、90%、100%为测试要求。图中本 碰撞半径10 b=6 有效碰撞下调除2 文算法预期覆盖度在85%、90%、100%所产生的用例次数逐 级减少,但是并没冇扩大参数变量范围明显。 参数范围20 边长(参考l|′成新用例 a=5 用例有效 三角形形状检测 二角形形状硷澳 撞半径5 b=7 350 30÷ 算法时间比 3.5 图6测试用例检测图 叔3 对于三角形形状检测代码,人为注入参数范围20,碰撞半 00 径初始值Rcm为参数范围除2,为10。真实测试用例碰童半 径为T=测试用例覆盖率xRm。为了模拟实验,假定各个 测试用例覆盖率均为1。 20 100 图6中的测试用例(5,6,7)在参数范围为20,碰撞半径下 参数范围 参数范围 为10时,处于碰撞域之外,被算法认做有效解。当条件不变, 图7预期覆盖度85%的 图8参数范20的 基于之前产生的测试用例作为交叉变异的参考,牛成新的测试 不同参数范围 不同预期覆盖度 用例(11,7,8)落在碰撞域中,作为无效测试用例。假定碰撞 表2罗列出了参数为20~500,预期覆盖度为85% 次数超过了阈值,碰撞半径开始执行除2的下调。假定新生成100%的所有测试要求下的数据信息 的测试用例依旧为(11,7,8),此时由于半径下调新的测试用 表2不同测试要求下测试数据信息 例(11,7,8)落在新的碰撞半径以外,被收入样木集中。 样本数/范围平用时 方法 平均次数方差 最长刊问 一组完全覆盖的最小单元测试组的测试用例结果如表1 /覆盖度 随机法 100/20/85 3184 284 所示,覆盖路径节点参照三角形实例代码所示,涵盖」测试用 本文算法 10020/85 例覆盖度,是否碰撞,以及该测试用例出现在碰撞域里的次数、 随机法 10050/85 110.5 12264 是否交又、空异等系列信息。 本文算法100/50/85 399 109 表1最小单元测试组 随机法 248.4740531 测试用例覆盖度是否碰道碰撞是否是否未覆盖 本文算法100/100/85 /%碰撞次数半径交叉变异节点 随机法 412.1 053 56774mo010m0m04581011本文算法 法100500/85 29.8 21.41969 12131379 0 5 no461011 随机法 100/2090 371.1 299.81182711053 2131285 61011 本文算法 100/2090 211.1 187928326 随机法 10020100620.6546.81276441469 345 本文算法100/2090 490.8420.798732 在大量的实验中,得出了以下结沦: 3实验 a)随着参数范围的不断增大,随机法的时间、生成测试用 例次薮、方差增幅不断增大。在范围20预期覆盖度85%与范 3.1实验环境 围500预期覆盖度85%对比中,时间增加了4.3倍之多,而自 实验采用Java高级语言作为编程语言,IDE为 Eclipse和定义的算法时间只增加∫0.3倍。可见在应付参数范围很大 ⅹcode,DK版木为1.8.0。实验开发平台为 Mac osx yosemite的时候,提出的算法比随机法高效得多。 10.10.5 b)稳定性的巨大差异表示了随机法本身十分不稳定,在 实验运行处理器主频7.7cHz,CPU为 Intel core5,内存覆盖度大于50%时,自定义算法方差始终保持在随机法方差 为8GB。 的30倍以上,在范围100的实验屮,方差减少为随机法的90 3.2实验结果 倍。说明自定义算法本身具有一定的稳定性和规律性。 为了验证算法的正确性和性能,以三角形形状检测作为被 c)对于苛刻的条件,木文的覆盖准则带来的性能提升是 测代码实例,选择随机法作为对比算法,为了验证算法能快速不明显的,在范围20预期覆盖度85%与范围20预期覆盖度 将程序覆盖度收敛刭一个满意值,分别选取了代码预期覆盖度90%对比中,·般三角形、非三角形以及等腰三角形都很容易 第1期 杨丰玉,等:基于碰撞域检测优化的測试用例自动生成方法 139 生成,为了生成覆盖等边三角形和直角三角形的测试用例,自[5 Fraser G, Areuri a. EvoSuite at the SBst2016 tool competition 定义算法相较于随机法提升较有限,产生的用例次数减少了 [C// Proc of the th International Workshop on Search-Based Soft 0.6倍。这是木文把重心放在优秀测试用例的代价。当然将 ware Testing. 2016: 33-36 代码覆盖度快速收敛到一个满意值本就是笔者的初衷 [6 Vishawjyoti DR, Gandhi P. A survey on prospects of automated soft ware test case generation method[ C]//Proc of the 3rd International 4结束语 Conference on Computing for Sustainable Global Development. 2016 3867-3871 木文提出了一种基于碰撞域检测优化的测试用例生成方7 Bhasin h, Singla N, Sharma S. Cellular automata hased test data 法,目的是能够尽快将测试覆盖度收敛到一个较为满意的值 generation [ J]. ACM SIGSOFT Software Engineering Notes 这在测试要求不为完全覆盖的情况下,有着重要的意义。 2013,38(4):1-7 经过大量实验证明,发现本文算法随着参效范围不断增[8]雷英杰,张善文 MATLAB遗传算法工具箱及其应月M].丙安 大,达到预期覆盖率所用的平均次数越少,达到了最初设定的 西安电子科技大学出版社,2013 目标,在较少的时间快速收敛到预期的覆盖度。在极端的条件[9.MmM, mar P. Automatic goal-orlented test data generation using a genetic algorithm and simulated annealing[ C]//Proc of the 6th In- 下,如预期覆盖度为100%时,本文算法所花费的时间也少于 ternational Conference on Cloud System and Big Data Engineering 随机法,只是时间减少的幅度不如扩大参数变量范围明显。 2016:83-87. 本算法针对整型数字的效果最佳,对于浮点数与字符中等[101 Khan R, Amiad M, Srivastava a K. Optimization of automatic genera 长度不定的参数,因为其本身无法穷举,在某些需要测试覆盖 ted test cases for path testing using genetic algorithm[ C]//proc of the 率特別髙的情形下,会较耗时。适应于 long int型下的参数范 2nd Internalional Conferenc: e on Computational Intelligence Com 围,满足大部分测试环境下的测试任务。 munication Technologv 2016: 32-36 下一步的研究方向可探索如何最大程度地利用被测代码,[11 Haga H, Suehiro a. Automatic test case generation based on genetic 尽可能多地挖掘对测试有帮助的信息.如何利用多次生成的测 algorithm and mutation analysis C //Proc of IEEE International Con 试用例信息,来减少测试用例碰撞次数等,同时提高多类型下 ference on Control System, Computing and Engineering. 2012: 119 的测试效率以获取更高的生成效率。 12 Usanla M P, Maten P B Mutation lesting cost reduction ler hniques: a 参考文献 survey[J. IEEE Journals Magazines, 2010, 27 (3): 80-86 [1]邵楠,雁舟,基于二叉树搜索空间縮减的洲试数据生成[J].计[13]张思才,张方晓.一种遺传算法适应度函数的改诖方法[冂]·计算 算机应用研究,2014,31(1):188-191 机应用与软件,2006,23(2):108-110 [2]张妍,傅秀芬.基于多优化目标的软件测试用例约筒方法研究[14 Sharma O, Sabharwal s, Sibal F. A survey on software testing tech [冂.计算机应月硏究,2016,33(4):111-1113 ues using genetic algorithm[ J] Journal of Computer Science [3 Gaston C, Call P L, Rapin N, et al. Symbolic execution techniques for Issues,2013,10(1):381-393 st purpose definitions[C]//Proc of International Conference on T'es-[ 15 1 Michael C, Mcgraw C, Schatz M. Generating software lest data by ting of Communicating System. 2006: 1-18 evolution[J]. IEEE Trans on Software Engineering, 2001, 27 [4 Cadar C, 'Iwohey P, Ganesh V, et al. EXE: a systcm for automatical (12):1085-110 ly generating inputs of death using symbolic execution[ C ]//Proc of [ IG] Dong Yuehua, Peng Jidong. Aulomalic generation of software lesl ca- the 13th ACM Conference on Computer and Communication Security ses based on improved genetic algorithm C//Proc of International 2006 Conference on Multimedia Technology. 2011: 227-230 (上接第134页 similarity and relatedness based on WordNet structure J1. Journal of [8 Mihalcea R, Taral P. Text Rank: bringing order into lexIs[C//Prod Systems Software, 2012, 85(2): 370-381 of Conference on Empirical Methods in Natural Language Processing.「16]何夏燕.基于汉语概念图的词汇语义相似度计算D.上海:上 2004:404-411 海交通大学,2010 「9] Blei d m,NgAY, Jordan M. Latent Dirichlet allocation「J.「17马培军,李东,软件工栏知识体 SWEBOK的新进展——一 Journal of Machine Learning Research, 2003. 3: 993-1022 SWEBOK V3[J].计算机教育,2013(1):66-68 「l0韩欣,樊永生,马春森,等.基于树状绐构的语义相似度计算方法「l8lhtp:〃code.google.comp/jwpl/「EB/OL 分析J].微岂子学与计算机,2012,29(5):38-41 [19]hllp://www.wikipediaory/leb/ol.] I 11 Frohlich H. The COSim package[R.s1.1: University Medicine 20 Wang Zhichun, Wang Zhigang, Li Juanzi, et al. Knowledge extrac- Gittinger 2010 on fron Chinese Wiki encyclopedias[ J]. Journal of Zhe jiang Uni- [12]黄吴,周竹荣.基于领域本体的概念语义相似度疒算研究[J] versity Science C, 2012, 13(4): 268-280 计算机工程与设汁,2007,28(10):2460-2463 L21 Pearson K. The problem of the random walk[ J]. Nature, 1905, 72 [13]安建成,武俊丽,基于语义树的概念语乂相似度计算方法研究 (1865):294 [J].黴电子学与计算机,2011,28(1):138-141 [22 Hu Jian, Wang Gang, lax'hovsky F, ef ul. Understanding user's yue- 14 Liu Hongzhe, Bao Hong, Xu De. Concept vector for similarity meas ry intent with wikipedia C|//Proc of the 18th International Confe urement based on hierarchical domain structure[J]. Computing& rence on World wide Web. New york. ACM Press. 2009.471-480 Informatics,2011,30(5):881-900 [23]赵佳鹏,林民、基于维基百科的领域历史沿苹信息抽取[J].计 L 15 Liu IlongZhe, Bao llong, Xu De. Concept vector for semantic 算机应用,2015,35(4):1021-1025