变异贪婪bt

软件学报ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,2019,30(5):14641480[doi:10.
13328/j.
cnki.
jos.
005723]http://www.
jos.
org.
cn中国科学院软件研究所版权所有.
Tel:+86-10-62562563基于SOM神经网络的二阶变异体约简方法宋利,刘靖(内蒙古大学计算机学院,内蒙古呼和浩特010021)通讯作者:刘靖,E-mail:liujing@imu.
edu.
cn摘要:二阶变异测试通过向源程序中人工注入两个缺陷来模拟程序实际的复杂缺陷,在软件测试中具有重要意义.
但由一阶变异体组合形成二阶变异体后数量会急剧增长,极大地增加了程序的执行开销.
为了减少二阶变异体数量,降低程序的执行开销,提出一种基于SOM神经网络的二阶变异体约简方法.
该方法首先采用较为全面的二阶变异体错误组合策略,对一阶变异体组合形成二阶变异体;然后,根据二阶变异体执行过程中的中间值相似性,进行基于SOM神经网络的变异体聚类.
使用经典的基准程序和开源程序进行了方法的验证,实验结果表明,一方面,使用错误覆盖更为全面的组合策略能够充分模拟程序的复杂缺陷,聚类约简后,二阶变异体的个数在极大减少的同时,二阶变异充分度和一阶变异充分度更加接近,但是因为执行的二阶变异体数目明显降低,从而使得运行聚类后的二阶变异体时间开销明显比执行全部二阶变异体降低;另一方面,实验过程发现了有利于增加测试组件的隐藏二阶变异体.
关键词:变异测试;二阶变异体;SOM神经网络;变异体聚类;变异体约简中图法分类号:TP311中文引用格式:宋利,刘靖.
基于SOM神经网络的二阶变异体约简方法.
软件学报,2019,30(5):14641480.
http://www.
jos.
org.
cn/1000-9825/5723.
htm英文引用格式:SongL,LiuJ.
Researchonsecond-ordermutantreductionbasedonSOMneuralnetworkRuanJianXueBao/JournalofSoftware,2019,30(5):14641480(inChinese).
http://www.
jos.
org.
cn/1000-9825/5723.
htmSecond-orderMutantReductionBasedonSOMNeuralNetworkSONGLi,LIUJing(CollegeofComputerScience,InnerMongoliaUniversity,Hohhot010021,China)Abstract:Second-ordermutationtestingsimulatestheactualcomplexdefectsintheoriginalprogrambymanuallyinjectingtwodefectsintotheoriginalprogram,whichisofgreatsignificanceinthemutationtesting.
However,thenumberofsecond-ordermutantsformedbythecombinationoffirst-ordermutantswillgreatlyincrease,whichwillbringlargeexecutioncosts.
Inordertoreducethenumberofsecond-ordermutantsandreducethetimeconsumptionintherunningprocedure,thisstudyproposesamethodofsecond-ordermutantreductionbasedonSOMneuralnetwork.
Theproposedmethodfirstlyutilizesamorecomprehensivecombinationstrategytogeneratefeasiblesecondordermutantsbasedontraditionalfirst-ordermutantgeneration,andthenconstructaccurateSOMneuralnetworkaccordingtothesimilarityofintermediatevaluesintheexecutionofsecond-ordermutants,andatlastmutantsareclusteredbasedonsuchmodeltoachievesecond-ordermutantreductionandsubtlemutantdetection.
Thisstudyusesthebenchmarkandopensourceprojectstoverifythemethod.
Experimentalresultsshowthatontheonehand,althoughthenumberofmutantsisverylarge,ithasdecreasedsignificantlythroughtheSOMneuralnetwork,whilethesecond-ordermutationscorelevelisthesameasthepre-unclusteredmutationscore.
However,becausethenumberofsecond-ordermutantsperformedissignificantlyreduced,thetimecostofmutationtestingwasgreatlylowerthantheexecutionofallmutants.
Ontheotherhand,subtlesecond-ordermutantsthatfacilitatetheadditionoftestcomponentsarefound.
基金项目:国家自然科学基金(61662051,61262017)Foundationitem:NationalNaturalScienceFoundationofChina(61662051,61262017)本文由智能化软件新技术专刊特约编辑申富饶教授和李戈副教授推荐.
收稿时间:2018-08-31;修改时间:2018-10-31;采用时间:2018-12-13宋利等:基于SOM神经网络的二阶变异体约简方法1465Keywords:mutationtesting;second-ordermutant;SOMneutralnetwork;mutantclustering;mutantreduction变异测试[1]是一种通过向源程序中人工注入缺陷来模拟软件中实际缺陷的技术,被注入缺陷的程序称为变异体.
传统的变异测试是指一阶变异测试,即通过向源程序中人工注入一个缺陷来模拟软件中的一个缺陷[2].
但程序中的实际缺陷往往是由两个或者更多个缺陷一起造成的[3,4],所以高阶变异测试被提出来用以解决程序中复杂缺陷的问题,在模拟程序的复杂缺陷方面有着重要意义[5].
由一阶变异体组合形成的高阶变异体数量会大量增加,大大增加了执行开销[6,7].
因此,减少高阶变异体数量和发现隐藏高阶变异体(subtlehigher-ordermutant)已经成为当前高阶变异测试的研究热点[8].
启发式算法被应用于高阶变异测试中解决高阶变异体数量[911]的问题,有效减少了高阶变异体的数量,降低了程序的执行开销,但却会存在未被发现错误组合的缺点,这将降低测试组件质量.
启发式算法也被应用于解决发现隐藏高阶变异体的问题[12,13],虽克服了未被发现错误组合的缺点,但却增加了时间开销.
与此同时,聚类法被证明在变异体约简上有很好的效果[14,15].
Ma等人[14]使用聚类法在不影响变异充分度的前提下减少了变异体数量,降低了程序的执行开销,但在运用到高阶变异测试时却因缺乏传值而受限.
针对该问题,本文着重研究二阶变异测试.
本文分析了影响二阶变异体执行过程中中间值相似性的因素,并将该中间值相似性描述为条件下二阶等价变异体,使用基于SOM神经网络模型[16,17]的方法进行变异体聚类以达到充分考虑二阶变异体组合时减少二阶变异体执行开销和发现隐藏二阶变异体(subtlesecond-ordermutant,本文定义为二阶变异体中单独的一阶变异体均被测试例杀死,但两者结合后的二阶变异体不能被现有测试例杀死的二阶变异体)的效果.
本文第1节介绍相关工作.
第2节是本文方法中用到的基础概念.
第3节对所提方法进行具体的介绍.
第4节对所提方法进行理论分析.
第5节给出实验结果及分析.
第6节是本文的结论.
1相关工作在变异测试中,如果在同一测试例下,变异体的结果和原始程序的结果不同,则称该变异体被杀死,否则它是存活的.
被杀死的变异体个数与所有的非等价变异体个数的比值称为变异充分度[2].
传统的变异体是指通过在原始程序中注入一个缺陷而产生的一阶变异体.
实际上,Purushothaman和Perry已经证明,程序中存在的许多缺陷都是复杂的,这类缺陷无法使用一阶变异体进行模拟.
为了解决该问题,高阶变异体则通过在原始程序中注入两个或更多个故障来模拟程序中的复杂缺陷.
然而高阶变异测试的成本却很高,因此,降低高阶变异测试的成本是非常重要的.
关于降低高阶变异测试成本方法的研究已经有很多学者在探索,综述文献[8]对相关研究进行了很好的总结分析.
其中,减少高阶变异体数量的方法主要有3种不同类型:第1种是选择有价值的高阶变异体,如基于搜索的软件工程的遗传算法[5];第2种是减少变异算子的数量,例如last-tofirst的变异算子选择算法和互不同的变异算子选择算法[9,10];第3种是减少变异位置的个数,如数据流技术[11,18].
关于发现隐藏高阶变异体的方法[8]则更多的关注于使用基于搜索的软件工程中的贪婪和遗传算法的方法来解决[6,12,13].
与此同时,聚类法已经在变异测试中得到了很好的应用[14].
该方法综合考虑了动态变异体和变异体筛选的优点.
研究表明,该方法在减少变异体数量方面具有很好的效果.
虽然聚类法已经在变异测试领域取得了很大进展[14,15,19,20],但是该方法更注重减少一阶变异体的数量并且缺乏中间结果的保存.
因此,我们在二阶变异测试中尝试采用一种新的方法,即应用SOM(self-organizingmap)神经网络方法进行聚类.
SOM神经网络[16]是通过模拟大脑神经系统自组织特征映射功能进行的一种无监督竞争式学习前馈网络,经过神经网络学习提取数据中的重要特征或某种内在规律,对数据进行聚类.
而SOM神经网络的学习算法则是通过模拟生物神经元之间的兴奋、协调与抑制、竞争作用的信息处理的动力学原理来指导网络的学习与工作.
所以该网络具有很强的聚类能力,并且在各领域得到了广泛的应用[17].
本文分析了影响二阶变异体执行中间值相似性的因素.
基于因素分析,提出了一种使用SOM神经网络聚类模型进行变异体约简及发现隐藏二阶变异体的方法.
具体而言,首先对不同变异点处的变异体组合成二阶变异体,在此基础上进行基于SOM神经网络聚类模型的变异体约简,根据不同变异点组合中间结果是否一样为一1466JournalofSoftware软件学报Vol.
30,No.
5,May2019类,然后从每一簇中选择一组变异体进行继续执行,达到对二阶变异体进行聚类和发现隐藏二阶变异体的效果.
2条件下二阶等价变异体二阶变异体的约简原理,主要是根据二阶变异体执行过程中的中间值相似性,即条件下二阶等价变异体进行的,所以本节就条件下二阶等价变异体的概念给出相关定义和示例.
2.
1概念定义a)等价变异体:指对于任何测试数据,执行源程序和变异体后,输出结果相同的变异体[20];b)变异体被杀死:指对于相同的测试数据,分行执行变异体和源程序,若变异体和源程序的执行结果不同,则称该变异体被杀死[20];c)条件下等价变异体(conditionallyoverlappedmutants):指对于相同的测试用例,一组一阶变异体的中间结果相同,但是有可能会被该测试用例杀死的一组变异体[14];d)二阶变异体的中间结果:本文定义为仅运行至二阶变异体中两个变异点后得到的结果,而非运行完整个程序后得到的结果,记为intermediateresultsofsecond-ordermutants,简单记为Irs;e)条件下二阶等价变异体:本文定义为对于相同的测试用例,一组二阶变异体的中间结果相同,但可能会被该测试用例杀死的一组二阶变异体,记为second-orderconditionallyoverlappedmutants,简单记为Second_CoM.
2.
2条件下二阶等价变异体示例为易于理解本文所提出的"条件下二阶等价变异体"概念,以图1(a)所示Java片段为例进行说明.
先使用关系运算符ROR和算术运算符AOR分别作用于程序中的第3行、第7行,生成各自的一个一阶变异体如图1(b)、图1(c)所示;再同时作用于第3行和第7行生成一个二阶变异体如图1(d)所示.
1intmy(intA,intB){2intC;3if(A>B)4C=C+A;5else6C=C-A;7C=C+B;8returnC;9}(a)1intmy(intA,intB){2intC;3if(AB)4C=C+A;5else6C=C-A;7C=C*B;8returnC;9}(c)1intmy(intA,intB){2intC;3if(A3)tri=tri+2;tri=tri+3;If(a+bba".
变异点的变异例如"a≤0!
(a≤0)";COR表示条件运算符替换,包含两个操作符,分别为"&&,||".
变异点的变异例如"(a&&b)(a||b)";AOR表示算术运算符替换,包含5个操作符,分别为"变异点的变异例如"(a+b)(ab).
5.
2实验结果及分析本文的实验将从以下几个方面开展:所提方法能否减少二阶变异体个数;所提方法对变异充分度是否影响;所提方法能否降低变异测试时间开销;所提方法能否发现隐藏二阶变异体.
针对以上几个方面进行如下实验.
(1)二阶变异体个数的实验为了验证本文方法能够减少运行的二阶变异体个数.
首先用本文方法生成一阶和二阶变异体,通过对一阶和二阶变异体个数的比较,以显示二阶变异体个数的庞大,并和文献[11]方法(记为已有方法)比较.
选择该文献的原因如下.
首先,该文献中解决的问题和本文所要解决的问题是一致的,即考虑文章中出现的错误组合,然后对二阶变异体个数进行约简;而其他文献中关于高阶变异体的约简则是通过对一阶变异体折半组合以达到减少变异体数量的目的,与本文研究的问题有稍许偏差.
其次,该文献作者所在研究组一直跟踪研究高阶变异测试,且该篇文章是该研究组近期发表的一篇非综述类研究高阶变异体约简的文章,该文献的工作具有较好的代表性,所以选其作为对比对象.
实验对比的具体信息见表3.
Table3Numberoffirst-orderandsecond-ordermutantsgeneratedforbenchmarkprograms表3基准程序生成的一阶和二阶变异体个数程序方法一阶变异体个数二阶变异体聚类前个数Triangle已有方法21947557本文方法21962369Mid已有方法11913935本文方法11924756其中,已有方法生成二阶变异体的方法使用的是LastToFirstDifferentOperators策略,该策略忽略了某一个宋利等:基于SOM神经网络的二阶变异体约简方法1475错误组合后再同其他错误组合的情况,造成程序中某些错误组合被遗漏;本文充分考虑程序中可能出现的错误组合,采用较为全面的组合策略对一阶变异体进行组合生成二阶变异体;接着进行聚类前后二阶变异体个数比较的实验,使用二阶变异体减少率的形式展示,具体见表4和表5.
Table4Numberofsecond-ordermutantsafterfilteringforMid表4Mid筛选后的二阶变异体数量方法测试例筛选后二阶变异体个数筛选后减少率(%)已有方法t1,t2,t32099.
86本文方法t11799.
93t21999.
92t31599.
94Table5Numberofsecond-ordermutantsafterfilteringforTriangle表5Triangle筛选后的二阶变异体数量方法测试例筛选后二阶变异体个数筛选后减少率(%)已有方法t1,t2,t35299.
89本文方法t11999.
97t22599.
96t32399.
96注:筛选后二阶变异体:本文方法指由聚类后从每簇中任选一个二阶变异体组成的二阶变异体如表3所示,为两个程序在本文方法和文献[11]方法下生成的二阶变异体(未筛选)个数.
由最后一列可知,与已有方法比,本文方法生成了更多的二阶变异体.
如就Triangle程序而言,已有方法产生的总的二阶变异体的个数为47557,而本文方法则生成了62369个二阶变异体,这将有利于充分表示程序中的复杂缺陷.
由表4和表5可知,一方面,二阶变异体聚类后个数极少,与聚类前相比减少了很多;另一方面,与已有方法相比,本文方法执行了更少的二阶变异体,如以Triangle为例,已有方法减少了99.
86%,而本文方法的减少率至少为99.
92%.
这表明,基于SOM神经网络的二阶变异体聚类能够有效减少二阶变异体个数.
为了验证结论是否有效,本文对表4和表5中本文方法和已有方法筛选后的减少率做了差异显著性分析(使用的是无重复双因素分析,其中a=0.
05),结果见表6.
Table6Resultofthesignificancedifferenceanalysisofreductionrateofsecond-ordermutantsforbenchmarkprograms表6基准程序中二阶变异体减少率的显著性差异分析的结果差异源FP-valueFcritMid筛选前后减少率组间1470.
00674318.
51282Triangle筛选前后减少率组间4840.
0020618.
51282表6从统计学上的显著性差异进行分析,从表格中可以看出,基准程序Mid和Triangle的P-value均小于0.
01,说明两组数据具备显著性差异的可能性大于99%,表明本文方法与已有方法的减少率差异极为显著,具有统计学意义上的差异显著性.
说明基于SOM神经网络的二阶变异体聚类能够有效减少二阶变异体个数.
(2)变异充分度的实验为验证本文方法对变异充分度的影响,首先进行一阶和二阶变异充分度比较的实验,来反映聚类后二阶变异体对变异充分度的影响;然后和文献[11]方法进行变异充分度比较,来反映本文方法的优劣性.
实验时使用的一阶变异体和二阶变异体个数的具体信息见表7,变异测试中变异体被杀死的具体信息见表8和表9,变异充分度的比较信息见表10,其中,二阶变异测试充分度计算方法为:假设100个非等价二阶变异体,聚类后有20个簇.
若10个簇的代表性二阶变异体被杀死,而10个簇中共含有60个二阶变异体,则变异充分度为60%.
1476JournalofSoftware软件学报Vol.
30,No.
5,May2019Table7Numberofmutantsundertestcasesforbenchmarkprograms表7基准程序的测试例执行的变异体个数程序方法选取的一阶变异体个数选取的二阶变异体个数Triangle已有方法2812本文方法2813Mid已有方法3610本文方法3613Table8Informationonthenumberoffirst-ordermutantskilledbyexecutingtestcasesforbenchmarkprograms表8基准程序执行测试用例时被杀死的一阶变异体个数的信息程序方法被杀死的一阶变异体没有被杀死的一阶变异体等价一阶变异体总和Triangle已有方法262028本文方法262028Mid已有方法320436本文方法320436Table9Informationonthenumberofsecond-ordermutantskilledbyexecutingtestcasesforbenchmarkprograms表9基准程序执行测试用例时被杀死的二阶变异体个数的信息程序方法被杀死的二阶变异体没有被杀死的二阶变异体等价二阶变异体总和Triangle已有方法111012本文方法121013Mid已有方法90110本文方法120113Table10Mutationscoreoffirst-orderandsecond-ordermutationtestingforbenchmarkprograms表10基准程序的一阶和二阶变异测试的变异充分度程序方法一阶变异充分度(%)二阶变异体变异充分度(%)Triangle已有方法92.
991.
7本文方法92.
992.
5Mid已有方法100.
0100.
0本文方法100.
0100.
0表8和表9展示了变异测试中变异体被杀死的具体信息,根据这两个表可得到表10的变异充分度比较信息.
其中,本文方法的某个二阶变异体被杀死指该二阶变异体所在簇中的二阶变异体被杀死.
以表9中三角形基准程序为例,本文所提方法中被杀死的二阶变异体为12个,则指的是有12个簇的二阶变异体被杀死.
由表10可知,一方面,本文所提方法的二阶变异充分度和一阶变异充分度很接近.
以三角形为例,本文方法中二阶变异体的变异充分度为92.
5%,较已有文献中的91.
7%,更加的接近一阶变异充分度.
根据文献[7,11]所述,当二阶变异充分度和一阶变异充分度越接近时,表明二阶变异体选取的越好,即本文选取聚类后的二阶变异体具有很好的效果.
另一方面,也表明了本文所提方法取得的二阶变异充分度较文献[11]更接近一阶变异充分度,表明本文所提方法与已有方法相比,能够运行更有效的少量二阶变异体,取得更好的二阶变异充分度.
为了验证该方法的可应用性和有效性,本文使用一个规模较大的开源项目和小组团队开发程序.
程序的信息见表11.
宋利等:基于SOM神经网络的二阶变异体约简方法1477Table11Informationlistforpracticalprojects表11实用项目的信息列表项目名类的个数代码行数Snake(github.
com/JiaxinTse/Snake)132160Shopping(小组开发)121560其中,Snake是一个开源的贪吃蛇游戏,通过键盘上的方向键控制蛇前进的方向,游戏实时记录自己当前的长度及可以计时;Shopping是一个自己小组使用SSH框架开发的电子商城,主要功能有订单管理、用户管理、商品管理.
使用本文提出的组合策略将Snake项目和Shopping项目的一阶变异体组合生成二阶变异体,其中的具体信息见表12.
Table12Informationofmutantsgenerationforpracticalprojects表12实用项目的变异体生成的具体信息项目名称核心类一阶变异体个数二阶变异体个数SnakeObstacle,Foodset,CreatNode,SnakeNode,Move13110414Windows15ShoppingProductAction,UserAction,AdminAction9112126ProductEntity,UserEntity,AdminEntity84由表12中可知,虽然项目代码行较多,但是由于其中多数为不易出错的代码,如Snake中GUI代码,该类代码相似的重复性操作较多(由熟练程序员假设可知,此部分属于不易出错范畴),含操作符代码不多,所以一阶变异体并不多,如Snake一阶变异体数为146个.
因为项目的主要功能分布在某些类中,我们重点对核心类进行分析,实验中,非核心类多数不产生变异体;为验证其可应用性,使用自己团队编写的测试用例进行实验,其中,测试用例并不能保证杀死全部的变异体,选择在全部测试用例下进行分析,而没有再分析单个测试例的变异测试充分度.
将聚类前的一阶变异测试充分度和聚类后的二阶变异测试充分度做对比,用以验证本文方法的可应用性.
具体信息见表13.
Table13Mutationscoreforpracticalprojects表13实用项目的变异充分度项目名一阶变异体个数筛选前二阶变异体个数一阶变异测试充分度(%)筛选后二阶变异测试充分度(%)Snake1461041413.
6813.
73Shopping1751212614.
7614.
69由表13可知,两个项目在使用本文方法约简后,二阶变异体测试充分度较一阶变异测试充分度较为接近,如Snake的一阶变异测试充分度为13.
68%,其筛选后二阶变异体测试充分度为13.
73%.
由文献[7,11]可知,当二阶变异充分度和一阶变异充分度接近时,表明二阶变异体约简的效果越好.
为验证该结果是否具有统计学上的差异显著性,对实验中的一阶变异测试充分度和筛选后二阶变异测试充分度的数据做差异显著性分析,分析结果见表14.
Table14Resultofthesignificantdifferenceanalysisofmutationscorebeforeandafterfilteringforpracticalprojects表14筛选前后的实用项目的变异充分度的显著性差异分析的结果差异源FP-valueFcrit组间0.
0277780.
894863161.
4476从表14中可以看出,显著性差异分析结果的P-value为0.
894863,大于0.
05,说明两组数据具备显著性差异的可能性小于95%,表明本文方法的筛选后二阶变异充分度较一阶变异测试充分度较为接近.
(3)时间开销和发现隐藏二阶变异体的实验1478JournalofSoftware软件学报Vol.
30,No.
5,May2019因为发现隐藏二阶变异体的实验需知道全部二阶变异体执行过测试例的信息,所以可从聚类后根据符合该特征的簇中获取隐藏二阶变异体.
基于该特征,可将发现隐藏二阶变异体和变异体约简的时间开销同时分析.
为了验证本文方法能够降低时间开销,同时便于发现隐藏二阶变异体实验的比较,所以实验中的程序使用基准程序Coordinate[7],测试例为非充分测试例(即测试组件不能杀死全部二阶变异体),并将本文方法使用的时间和文献[7]中的时间进行比较.
a)时间开销的实验本文通过和文献[7]的方法(记为文献法)比较平均时间来反映时间消耗.
实验需执行全部的测试组件,而不是执行单独的测试用例进行测试.
Coordinate程序的平均时间信息见表15.
Table15Averagetimecostofexecutingmutantsforprograms表15程序执行变异体的平均时间消耗方法时间消耗二阶变异体生成时间(s)聚类时间(s)测试例运行二阶变异体时间(s)发现隐藏二阶变异体时间(s)发现隐藏二阶变异体总时间(s)文献法无无无39685.
00039685.
000本文方法756.
82638010.
0990.
06780.
90038847.
892由表15可知,一方面,虽然聚类花费时间较长,但是聚类后的二阶变异体运行测试例的时间却很短;另一方面,本文中所提方法在发现隐藏二阶变异体功能上,比该文献方法中的时间开销减少了一些,如文献法使用了39685.
000s,而本文方法则使用了38847.
892s.
说明本文方法能够减少程序执行开销且用时较少.
b)发现隐藏二阶变异体的实验为了验证本文方法能够发现隐藏二阶变异体,实验中每次使用不同个数的算子运用到程序中,生成不同个数的二阶变异体.
如图7所示,为该文献方法和本文方法获取到的隐藏二阶变异体的平均数.
其中,本文隐藏二阶变异体的获取方法为:根据聚类后的二阶变异体,提取出第一变异体被杀死、第二变异体被杀死,但是二者共同作用时未被杀死的二阶变异体,进行比较,得到隐藏二阶变异体.
Fig.
7Averageoffindingsubtlesecond-ordermutants图7发现隐藏二阶变异体平均值由图7可知:本文方法寻找的到隐藏二阶变异体个数的平均数,在总数不是很大时优于该文献.
当数据量增大时,与该文献方法几乎一样稍微偏低.
原因为数量较大时,根据聚类后的二阶变异体,提取出第一变异体被杀死、第二变异体被杀死,但是二者共同作用时未被杀死的二阶变异体数有少许误差.
综合来说,表明本文方法能够发现隐藏二阶变异体,且数量相差不多.
宋利等:基于SOM神经网络的二阶变异体约简方法14796结论二阶变异测试中的二阶变异体能够模拟程序中的复杂缺陷,具有重要意义.
但由一阶变异体组合形成的二阶变异体数量庞大,因此减少执行的二阶变异体个数、降低程序的执行开销是至关重要的.
本文提出了一种基于SOM神经网络的二阶变异体约简方法.
首先,采用较为全面的二阶变异体错误组合策略对一阶变异体组合形成二阶变异体;然后,根据二阶变异体执行过程中的中间值相似性,进行基于SOM神经网络模型的变异体聚类;最后,以基准程序和开源项目进行验证.
结果表明,组合策略充分模拟了软件中的复杂错误,通过对二阶变异体执行过程中的中间值进行基于SOM神经网络的聚类,保证了在二阶变异测试充分度较为接近一阶变异充分度的情况下减少了二阶变异测试的执行开销;与此同时,在较短的时间里能够发现隐藏二阶变异体.
另外,二阶变异测试是高阶变异测试的基础,所以该方法可以推广到高阶变异测试中的其他阶的测试.
当推广到不同的阶数时,需要另外增加特征属性以达到更好的聚类效果.
如果不增加特征属性,也会有一定的聚类效果,但是效果不如现有的方法好,所以需要额外增加特征属性.
References:[1]DeMilloRA,LiptonRJ,SaywardFG.
Hintsontestdataselection:Helpforthepracticingprogrammer.
Computer,1978,11(4):3441.
[doi:10.
1109/C-M.
1978.
218136][2]ShanJH,GaoYF,LiuMH,LiuJH,ZhangL,SunJS.
Anewapproachtoautomatedtestdatagenerationinmutationtesting.
ChineseJournalofComputers,2008,31(6):10251034(inChinesewithEnglishabstract).
[3]PurushothamanR,PerryDE.
Towardunderstandingtherhetoricofsmallsourcecodechanges.
IEEETrans.
onSoftwareEngineering,2005,31(6):511526.
[doi:10.
1109/TSE.
2005.
74][4]JiaY,HarmanM.
Higherordermutationtesting.
InformationandSoftwareTechnology,2009,51(10):13791393.
[doi:10.
1016/j.
infsof.
2009.
04.
016][5]LangdonWB,HarmanM,JiaY.
Efficientmulti-objectivehigherordermutationtestingwithgeneticprogramming.
JournalofSystemsandSoftware,2010,83(12):24162430.
[doi:10.
1016/j.
jss.
2010.
07.
027][6]JiaY,HarmanM.
Constructingsubtlefaultsusinghigherordermutationtesting.
In:Proc.
ofthe8thIEEEInt'lWorkingConf.
onSourceCodeAnalysisandManipulation.
2008.
249258.
[doi:10.
1109/SCAM.
2008.
36][7]OmarE,GhoshS,WhitleyD.
Subtlehigherordermutants.
InformationandSoftwareTechnology,2017,81:318.
[doi:10.
1016/j.
infsof.
2016.
01.
016][8]GhidukAS,GirgisMR,ShehataMH.
Higherordermutationtesting:Asystematicliteraturereview.
ComputerScienceReview,2017,25(6):2948.
[doi:10.
1016/j.
cosrev.
2017.
06.
001][9]PoloM,PiattiniM,GarcaRodrguezI.
Decreasingthecostofmutationtestingwithsecondordermutants.
SoftwareTesting,VericationandReliability,2008,19(2):111131.
[doi:10.
1002/stvr.
392][10]MateoPR,UsaolaMP,AlemnJLF.
Validatingsecond-ordermutationatsystemlevel.
IEEETrans.
onSoftwareEngineering,2013,39(4):570587.
[doi:10.
1109/TSE.
2012.
39][11]GhidukAS.
Reducingthenumberofhigher-ordermutantswiththeaidofdataflow.
E-InformaticaSoftwareEngineeringJournal,2016,10(1):3149.
[doi:10.
5277/e-Inf160102][12]NguyenQV,MadeyskiL.
Problemsofmutationtestingandhigherordermutationtesting.
In:Proc.
oftheAdvancedComputationalMethodsforKnowledgeEngineering.
2014.
157172.
[doi:10.
1007/978-3-319-06569-4_12][13]NguyenQV,MadeyskiL.
Empiricalevaluationofmultiobjectiveoptimizationalgorithmssearchingforhigherordermutants.
CyberneticsandSystems,2016,47(1-2):4868.
[doi:10.
1080/01969722.
2016.
1128763][14]MaYS,KimSW.
Mutationtestingcostreductionbyclusteringoverlappedmutants.
JournalofSystemsandSoftware,2016,115:1830.
[doi:10.
1016/j.
jss.
2016.
01.
007][15]HussainS.
Mutationclustering[MS.
Thesis].
KingsCollegeLondon,2008.
1480JournalofSoftware软件学报Vol.
30,No.
5,May2019[16]KohonenT.
Theself-organizingmap.
In:Proc.
oftheIEEE'90.
1990.
14641480.
[doi:10.
1016/S0925-2312(98)00030-7][17]DelgadoS,HigueraC,Calle-EspinosaJ,MornF,MonteroF.
Asomprototype-basedclusteranalysismethodology.
ExpertSystemswithApplications,2017,88:1428.
[doi:10.
1016/j.
eswa.
2017.
06.
022][18]NguyenQV,MadeyskiL.
Addressingmutationtestingproblemsbyapplyingmulti-objectiveoptimizationalgorithmsandhigherordermutation.
JournalofIntelligent&FuzzySystems,2017,32(2):11731182.
[doi:10.
3233/JIFS-169117][19]KurtzB,AmmannP,DelamaroME,OffuttJ,DengL.
Mutantsubsumptiongraphs.
In:Proc.
ofthe2014IEEE7thInt'lConf.
onSoftwareTesting,VericationandValidationWorkshops.
Piscataway:IEEE,2014.
176185.
[doi:10.
1109/ICSTW.
2014.
20][20]YaoX,HarmanM,JiaY.
Astudyofequivalentandstubbornmutationoperatorsusinghumananalysisofequivalence.
In:Proc.
ofthe36thInt'lConf.
onSoftwareEngineering(ICSE2014).
NewYork:ACMPress,2014.
919930.
[doi:10.
1145/2568225.
2568265][21]ShinD,BaeDH.
Atheoreticalframeworkforunderstandingmutation-basedtestingmethods.
In:Proc.
ofthe2016IEEEInt'lConf.
onSoftwareTesting,VerificationandValidation(ICST).
Piscataway:IEEE,2016.
299308.
[doi:10.
1109/ICST.
2016.
22]附中文参考文献:[2]单锦辉,高友峰,刘明浩,刘江红,张路,孙家骕.
一种新的变异测试数据自动生成方法.
计算机学报,2008,31(6):10251034.
宋利(1993-),女,河南新乡人,硕士生,主要研究领域为软件测试方法与工具,云计算.
刘靖(1981-),男,博士,副教授,CCF高级会员,主要研究领域为云计算,容错计算,软件测试.