 |
| 图 1 基于程序变异的Simulink模型测试方法流程Fig. 1 Process of Simulink model testing method based on program mutation |
| 图选项 |
过程具体说明如下:①用已有的测试集T执行原始Simulink模型P.②根据设定好的变异算子生成活跃变异模型L集合.③选取一个未考虑过的活跃变异模型M.④选取未执行过的测试用例t.⑤使用测试用例t执行变异模型M,检查针对测试用例t执行M产生的结果与执行P产生的结果是否相同.若相同则返回步骤④,选取下一测试用例;若不相同则称为t杀死了变异模型M,将M添加到被杀死的变异模型D集合中.⑥当测试集T中没有测试用例能将变异模型M杀死时,将M放回到活跃变异模型L中.⑦检查L集合是否为空.若不为空,测试其与原始模型P的等价性.从L中剔除出等价变异模型E.⑧计算测试用例集T的变异评分(mutation score).给定集合L,D和E,用SM(T)表示T的变异评分,则
正如上式所示,一个测试集的变异评分总是介于0~1之间.如果测试集T能够杀死除等价变异模型外的所有变异模型,则|L|=0,变异评分SM(T)为1,该测试集T的发现错误能力较强.反之T不能杀死任何一个变异模型,则|D|=0,变异评分SM(T)为0,测试集T的发现错误能力较弱.测试用例t杀死变异模型为当且仅当测试用例t使得变异模型的最终输出与原模型的最终输出不同.3 Simulink模型的改进变异算子集Simulink包含很多现成的模块库,主要有输入源库、离散及连续系统库、数学运算库及非线性系统库.根据以上通用的模块库,考虑Simulink建模过程中的典型错误,文献[10]中首次研究了Simulink模型的故障模型,包括类型故障、变量故障、常量故障、连续离散时间故障、语句故障和表达式故障,并基于上述故障模型,针对Simulink模型提出了一组变异算子集.不同于传统程序变异的算子,该组算子集针对Simulink中常用的不同模块进行变异,如Switch模块的门限发生变异、积分及延时模块的变异.文中将其提出的变异算子集应用于一个二次方程模型的测试过程,通过计算4组测试用例集的变异评分,从而选择出最优用例集.文献[10]针对一组典型Simulink模型设计了变异测试实验,本文对实验结果进行了统计.该实验共生成59个变异模型,其中,TRO算子生成的变异模型数量最多,且该实验的等价变异模型全部由TRO算子产生,根据N-selective mutation策略,本文首先将TRO算子忽略,不仅有效减少生成27.11%的变异模型,还可以减少等价变异模型的生成,从而大幅降低测试开销.随后的实验验证了优化方案的必要性.基于充分变异算子的指导准则,上述算子集可以分为如下5类:数据类型变异(TRO)、变量变异(VCO,VNO)、常量变异(CCO,CRO,DCO)、Switch模块变异(SCO,SSO)和表达式变异(ROE,AOR,ASR,LOR).考虑文献[9]中的6条变异算子优化策略,依次对每一类里的变异算子进行分析.本文选择出6种重要的变异算子:VCO,CRO,SCO,DCO,ROR,AOR.图 2是一个包含基本模块的Simulink模型,其主要功能是判断二次方程解的类型,通过对该模型的变异测试实验表明,以上6种变异算子组成的针对Simulink模型的改进变异算子集比原有的变异算子集,在变异模型生产数量和变异评分方面都有进步.
 |
| 图 2 二次方程式模型Fig. 2 Quadratic model |
| 图选项 |
在图 2的二次方程模型解类型检验模型中,本文选择了6组测试用例集(每组包含6个测试用例),并执行于由上面6种算子生成的29个变异模型,得出了如表 1所示的实验结果.本文中变异模型均通过修改模块参数以实现算子对模型的变异操作.从表 1中的结果可看出,改进后的变异算子集能够显著减少变异模型的数量,并且略微提高了测试用例集的变异评分.由于其中随机生成的测试用例的广泛性不够,测试用例集T3的变异评分偏低.对于未被杀死的非等价变异模型,在第4节中将介绍基于搜索的用例生成方法,在改进变异算子集的基础上,主要关注于如何生成能够杀死上面提到的变异模型的测试用例.表 1 用例集的测试结果Table 1 Testing results of test sets
| 测试用例集 | 原变异算子集 | 改进后的变异算子集 | ||||||
| 杀死 变异模型 | 存活 变异模型 | 等价 变异模型 | 变异 评分/% | 杀死 变异模型 | 存活 变异模型 | 等价 变异模型 | 变异 评分/% | |
| T1 | 52 | 3 | 4 | 94.55 | 29 | 0 | 0 | 100 |
| T2 | 48 | 7 | 4 | 87.27 | 26 | 3 | 0 | 89.65 |
| T3 | 51 | 4 | 4 | 92.73 | 26 | 3 | 0 | 89.65 |
| T4 | 54 | 1 | 4 | 98.16 | 29 | 0 | 0 | 100 |
| T5 | 51 | 4 | 4 | 92.73 | 28 | 1 | 0 | 96.55 |
| T6 | 50 | 5 | 4 | 90.91 | 27 | 2 | 0 | 93.1 |
| 平均 | 51 | 4 | 4 | 92.73 | 27.5 | 1.5 | 0 | 94.83 |
表选项
4 基于搜索的测试用例生成由图 1可看出,当用例集T的测试用例都不能杀死变异模型,则需要向T中添加用例,其中测试用例生成是最花费人力和时间的过程.文献[11]中提出了一个自动化的测试用例生成框架,该框架采用搜索算法为结构化的模型生成了测试用例,实验证明该组用例能够达到较高的结构化覆盖准则，但是该实验仅选用了3个变异算子,对于变异测试的充分性不足.本文通过采用第3节中的改进算子集,更真实地模拟了Simulink仿真过程中可能出现的错误.文献[12]研究了基于搜索的Simulink模型测试数据生成法,针对Simulink模型复杂性的特点,采用模拟退火算法对目标函数求优.但是,满足结构化覆盖标准的测试用例有时并不能够发现Simulink模型中的一些错误,如逻辑模块故障、Switch模块故障等.由于结构化覆盖标准下的测试用例仅能保证覆盖特定路径,如果上述模块发生故障(如设计人员将Switch模块的门限“>0”错写为“>=0”)的情况下,该用例仍然可覆盖该特定路径,则该故障不能被发现.因此如何高效地从Simulink模型产生符合高变异评分的测试用例是本节研究的重点.基本思想是:反复执行被测程序,根据执行过程中搜集到的数据判断当前输入满足特定测试需求的程度.借助反馈机制,逐渐调整输入直到满足测试需求为止.本文考虑对于指定路径上不满足要求的分支,将测试数据生成问题转化为函数极小化问题,其重点在于如何选择合适的目标函数和函数极小化方法.4.1 构造代价函数根据文献[13]提出的代价函数,本文设计了代价函数定义基本规则和变异模型的代价函数构造规则,其中基本规则如表 2所示.表 2 代价函数Table 2 Cost functions
| 断言 | 代价函数值 |
| 布尔型 | 满足时为0,否则为K |
| E1<E2或E1≤E2 | 满足时为0,否则为E1-E2+K |
| E1=E2 | 满足时为0,否则为E1-E2+K |
| E1≠E2 | 满足时为0,否则为K |
| E1∨E2 | cos(E1)×cos(E2) cost(E1)+cost(E2) |
| E1∧E2 | cost(E1)+cost(E2) |
表选项
表 2中,K表示当断言不满足时的代价函数值,可用于比较各断言之间的差距.例如,对于断言来说A<5,A=6比A=10更接近于该断言,A=6的代价函数值更小.为了构造Simulink不同模块之间的代价函数,文献[14]中提出为了使得原模型与变异模型的输出产生差异,必须满足两个条件:1) 变异模块的输出必须发生改变;2) 该输出的改变必须影响到整个模型的输出.一般模块变异后,条件1能够满足.但是条件2则需要研究模型的结构,并保证从变异模块到系统输出之间的路径上，每个模块的输出与原模型的不同.如果系统模型包含多个输出,则至少1个输出不同就认为被杀死.针对本文提出的优化变异算子集,不同位置的不同类型变异均有不同的代价函数,下面将逐一介绍代价函数的构造.4.1.1 常量模块与变量模块如果模块的变异类型为常量变异与变量变异,则其代价函数应该为:C=CCV+CA.其中,CCV为常量模块与变量模块变异后需不同于原模块的代价,CA为该模块变异后其改变需影响到整个模型的输出的代价.4.1.2 Switch模块图 3(a)代表受影响的信号输入Switch模块的第1或第3输入,此时其代价函数应为:C=CD+CS+CA.其中,CD表示受影响的信号需不同于原模型中信号的代价，CS表示若受影响的信号输入Switch模块的第1输入时,第2输入信号达到门限的代价;若受影响的信号输入Switch模块的第3输入时,第2输入信号未达到门限的代价.
 |
| 图 3 受变异的信号输入Switch模块Fig. 3 Mutated signal input Switch blocks |
| 图选项 |
图 3(b)代表受影响的信号输入Switch模块的第2输入,此时其代价函数应为:C=CD+(CS1S3+CPM)∨(C′S1S3+CPM)+CA.其中,CS1S3为原Switch模块的第3输入与变异Switch模块的第1输入不同的代价,C′S1S3为原Switch模块的第1输入与变异Switch模块的第3输入不同的代价.4.1.3 表达式模块如果模块的变异算子为ROR,AOR或LOR时,则其代价函数应为:C=CP≠M+CA.其中,CP≠M为输入经过变异表达式操作的输出值不同于原模块的代价.图 4(a)代表受影响的信号输入表达式模块的任意输入端口,其代价函数为:C=CD+CP≠M+CA.图 4(b)代表受影响的信号输入两个表达式模块的任意输入端口,其代价函数为:C=CD+(CO1∨CO2),其中,CO1=CP1≠M1+CA1,CO2=CP2≠M2+CA2.
 |
| 图 4 受变异的信号输入表达式模块 Fig. 4 Mutated signal input expression blocks |
| 图选项 |
结合表 2中的代价函数构造规则,可以递归地从变异模块到最终输出来计算,从一组随机测试用例中搜索出能够杀死该变异模型的测试用例的代价函数.假设图 3中模型受变异算子ROR影响生成变异模型,其中Compare To Zero模块的“>=”被替换为“<=”.如果该变异模型在图 1中步骤⑤中没有被杀死,则其代价函数应为
4.2 搜索杀死特定变异模型的测试用例在4.1节中将测试用例生成问题转化为了代价函数值极小化问题的基础上,采用模拟退火算法来解决代价函数极小化问题[15].首先,模拟退火算法能够跳出初始输入的局部最优解,搜索到目标输入的稳定性较高,对Simulink模型中各种复杂情况具有更高适应性[12].另外,由于从R2009a版本开始,Matlab自带的优化工具箱集成了模拟退火算法,因此用Matlab环境来验证本文的测试数据生成算法方便易行.在第5节中将通过典型实例来简要介绍该算法的应用和变现.5 实例验证本节通过设计4组图 2中模型的变异模型来验证第4节的测试数据生成方法.表 3为图 2中模型的4个变异模型,具体描述如表 3所示.表 3 实验变异模型描述Table 3 Description of mutated models in experiment
| 编号 | 变异模块 | 算子类型 | 变异描述 | 系统代价函数 |
| 1 | Compare To Zero | ROR | “>=”被替换为“>” | cost(b2=4ac)+cost(a≠0) |
| 2 | Switch1 | SCO | “~=0”被替换为“~=1” | cost(a≠0) |
| 3 | REAL_SOLUTION | CRO | “2”被替换为“1” | cost(b2≥4ac)+cost(a≠0) |
| 4 | b×b | AOR | “×”被替换为“+” | cost(b2≠2b)+cost((b2≥4ac) ∧(2b<4ac))∨ cost((b2<4ac)∧(2b≥4ac))+ cost(a≠0) |
表选项
这里设置代价函数的K=1,由定义可知,目标函数的最优值为0.即可使目标函数为0的测试输入能够杀死对应的变异模型.对于系统的代价函数及以上4组变异模型的目标函数,可用Matlab脚本编写.用Matlab编写的测试数据生成脚本如下:ObjectiveFunction=@obj_function;%目标函数句柄设定startingPoint=[010];%初始值设定lb=]-10-10-10];%输入值下限ub=[101010];%输入值上限options=saoptimset(‘InitialTemperature’,1 000,‘TemperatureFcn’,@temperatureexp,‘ReannealInterval’,500,‘PlotFcns’,{@saplotbestx,@saplotbestf,@saplotx,@saplotf});%模拟退火算法参数设定[x,fval,exitFlag,output]=simulannealbnd(ObjectiveFunction,startingPoint,lb,ub,options);%执行模拟退火算法这里设置模拟退火算法的终止条件为目标函数达到0,起始温度为1 000,冷却率为0.95.通过分别编写目标函数,执行算法生成测试数据,运行上述脚本,4组模型的执行结果如图 5所示.最优目标函数表示在横轴的迭代次数下得到纵轴的目标函数值(最优目标函数为0),最优变量值表示当目标函数达最优时的测试数据.
 |
| 图 5 搜索迭代次数与最优变量输入值Fig. 5 Searching iteration number and optimal input value of variables |
| 图选项 |
由图 5可看出,通过采用模拟退火算法经过一定迭代次数均可使目标函数达到最优值,即可以找到需要的测试数据.除第1组的迭代次数为761次外,另3组的平均迭代次数不超过30次,就可以找到满足代价函数为0的测试输入.因此,当变异模型不能被现有测试用例杀死而需要额外添加测试用例时,使用本文方法能够有效实现.6 结 论本文基于程序变异技术提出了Simulink模型的变异测试过程和一组改进变异算子集,并相应设计了一种基于搜索的Simulink模型变异测试用例生成方法,经实验验证表明:1) 该组改进变异算子集能够减少变异模型的数量,并且保证测试用例集的变异评分基本不变;2) 对于Simulink基本模块库中的不同变异模块,基于搜索的Simulink模型变异测试用例生成方法能够快速准确地生成满足测试要求的测试用例.今后研究将从以下几个方面展开:本文采用手工方式构造实验变异模型的代价函数,未实现代价函数构造自动化.仅考虑了Simulink中的基本模块库,对于其他特定领域的模块库,其变异算子的设计有待继续研究.等价变异模型判定、子系统模块处理等问题的优化,也是未来值得研究的方向.
参考文献
| [1] | Molina J M, Pan X,Grimm C,et al.A framework for model-based design of embedded systems for energy management[C]//Modeling and Simulation of Cyber-Physical Energy Systems(MSCPES).Piscataway,NJ:IEEE,2013:1-6. |
| Click to display the text | |
| [2] | He N, Rümmer P,Kroening D.Test-case generation for embedded Simulink via formal concept analysis[C]//Proceedings of the 48th Design Automation Conference.New York:ACM,2011:224-229. |
| Click to display the text | |
| [3] | DeMillo R A, Lipton R J,Sayward F G.Hints on test data selection:help for the practicing programmer[J].Computer,1978,11(4): 34-41. |
| Click to display the text | |
| [4] | Jia Y, Harman M.An analysis and survey of the development of mutation testing[J].IEEE Transactions on Software Engineering,2011,37(5):649-678. |
| Click to display the text | |
| [5] | King K N, Offutt A J.A fortran language system for mutation-based software testing[J].Software:Practice and Experience,1991,21(7):685-718. |
| Click to display the text | |
| [6] | Mathur A P. Performance,effectiveness,and reliability issues in software testing[C]//15th Annual International Computer Software and Applications Conference.New York:IEEE,1991:604-605. |
| Click to display the text | |
| [7] | Offutt A J, Rothermel G,Zapf C.An experimental evaluation of selective mutation[C]//Proceedings of the 15th International Conference on Software Engineering.Piscataway,NJ:IEEE Computer Society Press,1993:100-107. |
| Click to display the text | |
| [8] | Offutt A J, Lee A,Rothermel G,et al.An experimental determination of sufficient mutant operators[J].ACM Transactions on Software Engineering and Methodology(TOSEM),1996,5(2):99-118. |
| Click to display the text | |
| [9] | Barbosa E F, Maldonado J C,Vincenzi A M R.Toward the determination of sufficient mutant operators for C[J].Software Testing,Verification and Reliability,2001,11(2):113-136. |
| Click to display the text | |
| [10] | Binh N T. Mutation operators for Simulink models[C]//Knowledge and Systems Engineering(KSE),2012 Fourth International Conference on.Piscataway,NJ:IEEE,2012:54-59. |
| Click to display the text | |
| [11] | Zhan Y, Clark J.Search based automatic test-data generation at an architectural level[C]//Genetic and Evolutionary Computation-GECCO 2004.Berlin:Springer,2004:1413-1424. |
| Click to display the text | |
| [12] | 邓绍鹏,杨志义, 王宇英.基于搜索的Simulink测试数据生成[J].计算机应用研究,2012,29(7):2527-2530. Deng S P,Yang Z Y,Wang Y Y.Search-based test-data generation for Simulink[J].Application Research of Computers,2012,29(7):2527-2530(in Chinese). |
| Cited By in Cnki (1) | |
| [13] | Bottaci L. Predicate expression cost functions to guide evolutionary search for test data[C]//Genetic and Evolutionary Computation—GECCO 2003.Berlin:Springer,2003:2455-2464. |
| Click to display the text | |
| [14] | Zhan Y, Clark J A.Search-based mutation testing for Simulink models[C]//Proceedings of the 2005 Conference on Genetic and Evolutionary Computation.New York:ACM,2005:1061-1068. |
| Click to display the text | |
| [15] | McMinn P. Search-based software test data generation:a survey[J].Software Testing,Verification and Reliability,2004,14(2): 105-156. |
| Click to display the text |
