1、1赵慧变异测试技术变异测试技术n变异测试是一种对测试集的充分性进行评估的技术，以创建更有效的的测试集。n变异测试与路径或数据流测试不同，没有测试数据的选择规则。n变异测试应该与传统的测试技术结合，而不是取代它们。基本思想基本思想n给定一个程序P和一个测试数据集T，通过变异算子为P产生一组变异体Mi（合乎语法的变更），对P和M都使用T进行测试运行，如果某Mi在某个测试输入t上与P产生不同的结果，则该Mi被杀死；若某Mi在所有的测试数据集上都与P产生相同的结果，则称其为活的变异体。接下来对活的变异体进行分析，检查其是否等价于P；对不等价于P的变异体M进行进一步的测试，直到充分性度量达到满意的程度。
2、程序变异概念（程序变异概念（1 1）n假设程序P已使用测试T中的测试用例测试通过，而且没有错误。变异是一种轻微改变程序的操作。Example:Program 11 begin int x,y;input(x,y);if(x y)output(x+y)else output(x*y);2end Program 1的变异体M11 begin int x,y;input(x,y);if(xy)output(x+y)else output(x*y);2end Program 1的变异体M21 begin int x,y;input(x,y);if(x y)output(x+y)else output(
3、x/y);2end Changed to PP程序变异概念（程序变异概念（2 2）nP称为P的变异体n如果对于T中的测试t，有P(t)P(t)，称作P与P有区别（distinguishes），或者t杀死（killed）P.n如果T中所有的测试 t使得P(t)=P(t)，称T不能区别P和P。那么称在测试过程中P是活的（live）.n如果在程序P的输入域中不存在任何测试用例t使得P与P 区别，则称P等价于P。n如果P不等价于P，而且T中没有测试能够将P与P区别，则认为T是不充分的。n不等价而且是活的变异体为测试人员提供了一个生成新测试用例的机会，进而增强测试T。Slides from Aditya
4、 P.Mathur为什么变异？为什么变异？nA Scenario：l程序员开发了一个程序P，按照某种测试充分性准则通过了测试，即将发布，这时会有人指出：程序中的表达式 countmax 还是 countmaxTemp)highCount=1;if(currentTemp1maxTemp)highCount=highCoun+1;if(currentTemp2maxTemp)highCount=highCount+1;if(highCount=1)danger=moderate;if(highCount=2)danger=high;if(highCount=3)danger=veryHigh;r
5、eturen(danger);例：原子反应堆控制软件例：原子反应堆控制软件P-M1P-M1enum dangerLevel none,moderate,high,veryHigh;Procedure chechTemp(currentTemp,maxTemp)float currentTemp3,maxTemp;int highCount=0;enum dangerLevel danger;danger=none;if(currentTemp0maxTemp)highCount=1;if(currentTemp1maxTemp)highCount=highCoun+1;if(currentTe
6、mp2maxTemp)highCounthighCount+1;if(highCount=1)danger=moderate;if(highCount=2)danger=high;if(highCount=3)danger=none;returen(danger);/if(highCount=3)danger=veryHigh;例：原子反应堆控制软件例：原子反应堆控制软件P-M2P-M2enum dangerLevel none,moderate,high,veryHigh;Procedure chechTemp(currentTemp,maxTemp)float currentTemp3,m
7、axTemp;int highCount=0;enum dangerLevel danger;danger=none;if(currentTemp0maxTemp)highCount=1;if(currentTemp1maxTemp)highCount=highCoun+1;if(currentTemp2maxTemp)highCounthighCount+1;if(highCount=1)danger=moderate;if(highCount=2)danger=high;if(highCount=3)danger=veryHigh;returen(danger);考查测试t:/if(hig
8、hCount=1)danger=moderate;强变异与弱变异应用变异评估测试的充分性（应用变异评估测试的充分性（1 1）nGiven a test set T for program P that must meet requirements R,a test adequacy assessment procedure proceeds as follows：lStep 1:Create a set M of mutants of P.Let M=M0,M1Mk.Note that we have k mutantslStep 2:For each mutant Mi find if th
9、ere exists a t in T such that Mi(t)P(t).If such a t exists then Mi is considered killed and removed from further consideration.Slides from Aditya P.Mathur应用变异评估测试的充分性（应用变异评估测试的充分性（2 2）lStep 3:At the end of Step 2 suppose that k1（k）mutants have been killed and(k-k1)mutants are live Case 1:(k-k1)=0:T
10、is adequate with respect to mutation.Case 2:(k-k1)0 then we compute the mutation score(MS)as follows:MS=k1/(k-e)Where e is the number of equivalent mutants.Note:e (k-k1).Slides from Aditya P.Mathur生成变异体活的变异体L确定并从L移出等价的变异体下一个变异体M将M添加到D计算变异的分数对T中的每一个测试用例，测试P选择下一个测试用例t所有的变异体 都遍历了的吗？所有的测试 都完成了吗？P(t)=M(t
11、)?对于T中所有的t，P(t)测试集T杀掉的变异体D等价的变异体E被测试程序P选用测试用例t执行M将M放回L关于变异的T的充分性（2）（3）（4）（5）（10）（6）（8）（9）（1）（7）（12）（11）yesM(t)NoP(t)yesNoNoYes测试充分性评估过程测试充分性评估过程测试充分性评估过程n第1步：程序执行lP(t)表示给定测试用例t，程序P的执行结果由P中变量的输出值表示（也可能与P的性能有关）l如果P已经采用测试T测试通过，测试结果已保存至数据库中，则这一步可以跳过。l不论何种情况，第一步的结果是对于T中的所有t，P(t)数据库对T中的每一个测试用例，测试P对于T中所有的t
12、，P(t)测试集T（1）Slides from Aditya P.Mathur测试充分性评估过程测试充分性评估过程n第2步：生成变异体l例如“”运算变成“”运算，“”运算变成“/”运算等l系统的生成方法：通过变异算子生成l第二步的结果是：活的变异体4这些变异体还没有与程序P区分，即没有被杀死。生成变异体活的变异体L被测试程序P（2）Slides from Aditya P.Mathur测试充分性评估过程测试充分性评估过程n第3步和第4步：选择下一个变异体l从L中选择，任意选择活的变异体L下一个变异体M所有的变异体 都遍历了的吗？（3）yesNoMSlides from Aditya P.Mat
13、hur测试充分性评估过程测试充分性评估过程n第5步和第6步：选择下一个测试用例l是否存在测试t能够区分变异体与被测试程序Pl采用测试T中的测试用例执行变异体M。l结束：所有的测试用例执行完毕或者M被某个测试用例区别（杀掉）。选择下一个测试用例t所有的测试 都完成了吗？测试集T（5）（6）yesNoMtSlides from Aditya P.Mathur测试充分性评估过程测试充分性评估过程n第7，8和9步：变异体执行和分类l变异体执行的结果是否与P的执行结果相同或不同n第10步：活变异体l如果没有测试用例能够区分变异体与P，则该变异体存活，并被放回活变异体集合L中。P(t)=M(t)?对于T中
14、所有的t，P(t)选用测试用例t执行M（8）（7）M(t)P(t)NoYest活的变异体L所有的测试 都完成了吗？将M放回L（5）（10）NoyesMSlides from Aditya P.Mathur测试充分性评估过程测试充分性评估过程n第11步：等价变异体l如果对于程序P的输入域中的每一个输入，变异体M的执行结果等于P的执行结果，则认为M等价于P。l例活的变异体L确定并从L移出等价的变异体等价的变异体E（11）Example:Program 11 begin int x,y;input(x,y);if(x y)output(x+y)else output(x*y);2end Progra
15、m 1的变异体M1 begin int x,y;input(x,y);if(x y+1)output(x+y)else output(x*y);2end 测试t:使得P(t)=2，M(t)=1，M不等价于P测试充分性评估过程测试充分性评估过程n第12步：变异数的计算l量化评价指标：41代表相关于变异T是充分的41表示相关于变异T是不充分的4可以通过增加额外的测试用例提高变异数lT的变异数记为MS（T）其中：|D|表示：杀死的变异体数|L|表示：表示活的变异体数|E|表示：等价的变异体数|M|表示：第2步生成的所有变异体数计算变异的分数杀掉的变异体D等价的变异体E（12）关于变异的T的充分性DL
16、D)(TMSEMD)(TMS或Slides from Aditya P.Mathur测试增强（例）测试增强（例）n P使用测试T并测试通过 t1:,t2:,t3:,t4:nM使用T运行的结果与P相同，无法区分P与Mn增加一个测试用例，使P和M区别，表明增强了TExample:Program 11 begin int x,y;input(x,y);if(x y)output(x+y)else output(x*y);2end Program 1的变异体M1 begin int x,y;input(x,y);if(x y+1)output(x+y)else output(x*y);2end 应用变
17、异查错（应用变异查错（1 1）nConsider the following function foo that is required to return the sum of two integers x and y.Clearly foo is incorrect.int foo(int x,y)return(x-y);This should be return(x+y)Slides from Aditya P.Mathur应用变异查错（应用变异查错（2 2）n假设foo已经由测试集合T 测试通过，T包含两个测试用例：t1:,t2:n注意：foo在每一个测试用例上返回了期望值，而且对于基
18、于控制流和数据流的充分性准则来说T是充分的。n假设foo生成了三个变异体int foo(int x,y)return(x+y);M1:int foo(int x,y)return(x-0);M2:int foo(int x,y)return(0+y);M3:Slides from Aditya P.Mathur应用变异查错（应用变异查错（3 3）使用T执行每个变异体，直到变异体被杀死或执行完所有的测试。Test(t)foo(t)M1(t)M2(t)M3(t)t11110t2-1-1-10LiveLiveKilledT=t1:,t2:Slides from Aditya P.Mathur执行完所
19、有的变异体后，2个活变异体，1个被杀死，计算变异数需要对所有活的变异体判断等价。应用变异查错（应用变异查错（4 4）考察两个活的变异体：int foo(int x,y)return(x+y);M1:int foo(int x,y)return(x-0);M2:关注M1.一个测试能够区分M1和foo一定满足条件：x-yx+y implies y 0.因此，得到一个新的测试数据 t3:Slides from Aditya P.Mathurint foo(int x,y)return(x-y);应用变异查错（应用变异查错（5 5）使用t3执行foo得到foo(t3)=0，然而根据需求应该得到foo(
20、t3)=2.因此，t3使得M1与foo区别，同时发现了错误 int foo(int x,y)return(x+y);M1:int foo(int x,y)return(x-0);M2:Slides from Aditya P.Mathurint foo(int x,y)return(x-y);变异算子（变异算子（1 1）n变异算子 O 是一个函数，建立了被测试程序P与P的K（=0）个变异体间的映射。n变异算子通过对被测试程序做简单的变化生成变异体。n变异算子对编程语言有依赖性，已经开发的、与语言相关的变异算子有 Fortran,C,Ada,Lisp 和 Java等。n变异算子的设计基于经验和一
21、些规则。O(P)M1M2Mk.Slides from Aditya P.Mathur变异算子（变异算子（2 2）nFor example,the“variable replacement”mutant operator replaces a variable name by another variable declared in the program.An“relational operator replacement”mutant operator replaces relational operator with another relational operatornA mutant
22、 operator models a simple mistake that could be made by a programmernSeveral error studies have revealed that programmers-novice and experts-make simple mistakes.For example,instead of using xy+1 one might use xynWhile programmers make“complex mistakes”too,mutant operators model simple mistakes.The“
23、coupling effect”explains why only simple mistakes are modeled.Slides from Aditya P.Mathur变异算子（例）变异算子（例）Mutant operatorIn PIn mutantVariable replacementz=x*y+1;x=x*y+1;z=x*x+1;Relational operator replacementif(xy)if(x=y)Off-by-1z=x*y+1;z=x*(y+1)+1;z=(x+1)*y+1;Replacement by 0z=x*y+1;z=0*y+1;z=0;Arith
24、metic operator replacementz=x*y+1;z=x*y-1;z=x+y-1;Slides from Aditya P.Mathur一阶和高阶变异体一阶和高阶变异体nA mutant obtained by making exactly“one change”is considered first ordernA mutant obtained by making two changes is a second order mutant.Similarly higher order mutants can be defined.For example,a second o
25、rder mutant of z=x+y;is x=z+y;where the variable replacement operator has been applied twicenIn practice only first order mutants are generated for two reasons:(a)to lower the cost of testing and(b)most higher order mutants are killed by tests adequate with respect to first order mutants.See couplin
26、g effect later.变异测试的理论基础变异测试的理论基础n程序员的能力假设（Competent programmer hypothesis(CPH)）：被测试程序是由足够程序设计能力的程序员书写的，所产生的程序是接近正确的。n组合效应假设（Coupling Effect）：假设简单的程序设计错误和复杂的程序设计错误之间具有组合效应，即一个测试数据如果能够发现简单的错误，也可以发现复杂的错误。n两个假设来源于软件开发的实验，至今未达到正确性证明，但确定了变异测试的基本特征：通过变异算子对程序做一个较小的语法上的变动来产生一个变异体。DeMillo,Lipton,and Sayward变
27、异测试工具变异测试工具nThere are few mutation testing tools available freely.lProteum for C from Professor Maldonado lmuJava for Java from Professor Jeff Offutt.nA typical tool for mutation testing offers the following featureslA selectable palette of mutation operators.lManagement of test set TlExecution of t
28、he program under test against T and saving the output for comparison against that of mutants.lGeneration of mutantsSlides from Aditya P.Mathur变异测试工具的特征（续）变异测试工具的特征（续）nMutant execution and computation of mutation score using user identified equivalent mutantsnIncremental mutation testing:i.e.allows t
29、he application of a subset of mutation operators to a portion of the program under test.nMothra,an advanced mutation tool for Fortran also provided automatic test generation using DeMillo and Offutts methodSlides from Aditya P.Mathur变异与系统测试变异与系统测试nAdequacy assessment using mutation is often recommen
30、ded only for relatively small units.l e.g.a class in Javala small collection of functions in CnHowever,given a good tool,one can use mutation to assess adequacy of system tests.nThe following procedure is recommended to assess the adequacy of system tests.Slides from Aditya P.Mathur测试步骤测试步骤Step 1:Id
31、entify a set U of application units that are critical to the safe and secure functioning of the application.Repeat the following steps for each unit in U.Step 2:Select a small set of mutation operators.This selection is best guided by the operators defined by Eric Wong or Jeff Offutt.Step 3:Apply th
32、e operators to the selected unit.Slides from Aditya P.Mathur测试步骤测试步骤Step 4:Assess the adequacy of T using the mutants so generated.If necessary,enhance T.Step 5:Repeat Steps 3 and 4 for the next unit until all units have been considered.We have now assessed T,and perhaps enhanced it.Note the use of
33、incremental testing and constrained mutation(i.e.use of a limited set of highly effective mutation operators).Slides from Aditya P.Mathur变异测试的优缺点变异测试的优缺点n排错能力强l发现错误的能力较强分析评估的结果n自动化程度高l测试工具自动产生变异体，自动运行P和M，自动发现被杀死的变异体n灵活性高l通过与测试工具的交互，有选择地使用变异算子n变异体与被测试程序的差别信息可以较容易地发现软件的错误。n可以完成语句覆盖和分支覆盖l将每条语句或每个条件用Tra
34、p语句代替n需要大量的计算机资源完成充分性分析lN行程序产生O（n2）变异体l存储变异体的开销大l变异体与被测试程序的等价判断需人工判定（判断两个程序是否等价是不可判定的命题）小结小结Mutation testing is the most powerful technique for the assessment and enhancement of tests.Identification of equivalent mutants is an undecidable problem-similar the identification of infeasible paths in con
35、trol or data flow based test assessment.Mutation,as with any other test assessment technique,must be applied incrementally and with assistance from good tools.Slides from Aditya P.Mathur小结（续）小结（续）While mutation testing is often recommended for unit testing,when done carefully and incrementally,it can be used for the assessment of system and other types of tests applied to an entire application.tests.Mutation is a highly recommended technique for use in the assurance of quality of highly available,secure,and safe systems.Slides from Aditya P.Mathur
