周艺斌，殷永峰，李骁丹，王明威

(北京航空航天大学 可靠性与系统工程学院，北京100191)

随着模型驱动软件设计思想(MBD)的广泛应用，软件开发的重心已由传统的代码设计转移到建模及模型的转换上［1］.如果能在完成软件初步设计的同时，及早发现并修复模型中的错误，不仅能缩短后期的代码测试周期，还能提高模型的可靠性，改善软件产品的质量.因此，越来越多的研究开始关注高层次的模型验证与测试工作.

Simulink是Matlab提供的一个用于对动态系统进行建模、仿真和分析的工具.它为用户建模提供了一个图形化的用户界面，通过不同类型模块库中的功能模型来完成系统的建模.目前，许多航空机载安全关键软件已运用Simulink/RTW技术进行开发，但仍存在缺乏完善的模型测试充分性准则及自动高效的测试用例生成等问题［2］.不同于基于控制流和数据流的测试充分性准则，程序变异是一项用于评价测试优良程度的有效技术，它为测试评价和测试增强提供了准则.将程序变异技术应用于Simulink的模型测试，不仅可以为Simulink模型提供测试充分性准则，还可以用来指导设计较强发现故障能力的测试用例生成.但是由于Simulink模型的变异测试过程中存在的测试执行开销大和测试用例生成效率低两个问题，是将变异测试技术从学术界研究转化为工业界应用所面临的主要技术难题.

本文研究设计了针对Simulink模型测试的改进变异算子集，在不影响测试用例集变异评分的情况下，该组变异算子集能够减少变异模型的生成数量，从而有效降低测试开销.在此基础上设计了一种基于搜索的Simulink模型变异测试用例生成方法.

1 相关工作

程序变异(program mutation)是一种面向缺陷的测试技术，最早由DeMillo等在文献［3］中提出，主要应用于单元测试，在接口测试、面向方面测试及面向对象测试中也有相关的理论研究.它依赖于两个基本原则:其一是称职程序员假设，即假设熟练的程序员写出的是一个接近于正确的程序P;另一个是耦合效应假设，即若测试用例可以检测出简单缺陷，则该测试用例也易于检测到更为复杂的缺陷.

程序变异的基础是变异算子集.变异算子是在符合语法规则前提下，从原有程序生成差别极小程序(变异体)的转换规则［4］.文献［5］于1987年针对Fortran77语言首次定义了22种变异算子，这组算子集为后来的其他编程语言变异算子的设计提供了重要的依据.该组变异算子主要分为4种类型，即常量变异、操作法变异、语句变异及变量变异，实际中每种分类下面都有很多个变异算子.每种分类下面的变异算子的类型和数量依赖于针对的编程语言.

程序变异技术虽然已有较多研究成果，但其应用却存在分析过程中计算开销过大的技术难题.大量变异模型的生成使得测试分析工作的开销及其高昂，为此需要有效的优化方法来减小计算开销.文献［6］中首先提出了选择性变异的方法，即忽略ASR和SVR两个可以生成30% ～40%变异体的变异算子.这种策略被称为“2-selective mutation”，文献［7］将这种策略延伸为“N-selective mutation”.实验结果表明，使用“N-selective mutation”策略后的变异评分均值仍可以保持较高，并明显降低了变异体数量.在以上的实验研究分析下，文献［8］将文献［5］中提出的22种变异算子进一步分为了操作数类算子、表达式类算子和语句类算子.通过对每一类变异算子的分析，最终确定了5个最为重要的变异算子:ABS算子、AOR算子、LCR算子、ROR算子、UOI算子，实验结果表明，使用这5个变异算子仅将其变异评分降低了0.5%.文献［9］中针对Proteum测试工具为C语言的变异算子设计了优化的方法，提出了选择出充分变异算子集的6条指导策略.即:①考虑能获得高变异评分的变异算子.②考虑每个变异算子类中的一个算子.③依据实验将包含在高效算子中的算子除去.④建立增量策略.⑤考虑能够在变异评分上提供增量的变异算子.⑥考虑具有高可信度的算子.

在上述研究分析的基础上，本文拟在不影响变异评分的前提下，以上述6条策略为指导，通过对Simulink变异算子进行约简优化来大规模减少变异体数量，从而减小变异测试的计算开销.

2 基于程序变异的模型测试过程

许多航空机载安全关键软件已运用Simulink/RTW技术进行开发，但仍存在以下问题:①仍缺乏完善的测试充分性度量证明模型的测试是充分的.不同的软件测试人员使用不同的充分性准则标准，没有统一的标准.②如何自动高效生成满足Simulink模型测试所需的测试用例集，仍是一个亟待解决的问题.③虽然已有众多工具应用于模型驱动的软件开发过程领域，但是对Simulink模型的测试工具研究尚属于起步阶段.

考虑Simulink环境特点，设置被测单位为一个系统模型，在生成变异模型的过程中不对子系统的模块进行变异.这时子系统类似于代码中的调用函数，在以子系统为被测单位时再对其模块进行变异.本文提出了基于程序变异的Simulink模型测试过程，如图1所示.

过程具体说明如下:①用已有的测试集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使得变异模型的最终输出与原模型的最终输出不同.

图1 基于程序变异的Simulink模型测试方法流程Fig.1 Process of Simulink model testing method based on program mutation

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的二次方程模型解类型检验模型中，本文选择了6组测试用例集(每组包含6个测试用例)，并执行于由上面6种算子生成的29个变异模型，得出了如表1所示的实验结果.本文中变异模型均通过修改模块参数以实现算子对模型的变异操作.

从表1中的结果可看出，改进后的变异算子集能够显著减少变异模型的数量，并且略微提高了测试用例集的变异评分.由于其中随机生成的测试用例的广泛性不够，测试用例集T3的变异评分偏低.对于未被杀死的非等价变异模型，在第4节中将介绍基于搜索的用例生成方法，在改进变异算子集的基础上，主要关注于如何生成能够杀死上面提到的变异模型的测试用例.

图2 二次方程式模型Fig.2 Quadratic model

表1 用例集的测试结果Table1 Testing results of test sets

4 基于搜索的测试用例生成

由图1可看出，当用例集T的测试用例都不能杀死变异模型，则需要向T中添加用例，其中测试用例生成是最花费人力和时间的过程.文献［11］中提出了一个自动化的测试用例生成框架，该框架采用搜索算法为结构化的模型生成了测试用例，实验证明该组用例能够达到较高的结构化覆盖准则，但是该实验仅选用了3个变异算子，对于变异测试的充分性不足.本文通过采用第3节中的改进算子集，更真实地模拟了Simulink仿真过程中可能出现的错误.文献［12］研究了基于搜索的Simulink模型测试数据生成法，针对Simulink模型复杂性的特点，采用模拟退火算法对目标函数求优.但是，满足结构化覆盖标准的测试用例有时并不能够发现Simulink模型中的一些错误，如逻辑模块故障、Switch模块故障等.由于结构化覆盖标准下的测试用例仅能保证覆盖特定路径，如果上述模块发生故障(如设计人员将Switch模块的门限“＞0”错写为“＞=0”)的情况下，该用例仍然可覆盖该特定路径，则该故障不能被发现.因此如何高效地从Simulink模型产生符合高变异评分的测试用例是本节研究的重点.

基本思想是:反复执行被测程序，根据执行过程中搜集到的数据判断当前输入满足特定测试需求的程度.借助反馈机制，逐渐调整输入直到满足测试需求为止.本文考虑对于指定路径上不满足要求的分支，将测试数据生成问题转化为函数极小化问题，其重点在于如何选择合适的目标函数和函数极小化方法.

4.1 构造代价函数

根据文献［13］提出的代价函数，本文设计了代价函数定义基本规则和变异模型的代价函数构造规则，其中基本规则如表2所示.

表2 代价函数Table2 Cost functions

表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(b)代表受影响的信号输入Switch模块的第2输入，此时其代价函数应为:C=CD+(CS1S3+)∨(C′S1S3+)+CA.其中，CS1S3为原Switch模块的第3输入与变异Switch模块的第1输入不同的代价，C′S1S3为原Switch模块的第1输入与变异Switch模块的第3输入不同的代价.

图3 受变异的信号输入Switch模块Fig.3 Mutated signal input Switch blocks

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 实验变异模型描述Table3 Description of mutated models in experiment

这里设置代价函数的K=1，由定义可知，目标函数的最优值为0.即可使目标函数为0的测试输入能够杀死对应的变异模型.对于系统的代价函数及以上4组变异模型的目标函数，可用Matlab脚本编写.用Matlab编写的测试数据生成脚本如下:

ObjectiveFunction=@obj_function;%目标函数句柄设定

startingPoint=［010］;%初始值设定

lb=［－10－10－10］;%输入值下限

ub=［101010］;%输入值上限

options=saoptimset(‘InitialTemperature’，1000，‘TemperatureFcn’，@temperatureexp，‘ReannealInterval’，500，‘PlotFcns’，{@saplotbestx，@saplotbestf，@saplotx，@saplotf});% 模拟退火算法参数设定

［x，fval，exitFlag，output］ =simulannealbnd(ObjectiveFunction，startingPoint，lb，ub，options);%执行模拟退火算法

这里设置模拟退火算法的终止条件为目标函数达到0，起始温度为1000，冷却率为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中的基本模块库，对于其他特定领域的模块库，其变异算子的设计有待继续研究.等价变异模型判定、子系统模块处理等问题的优化，也是未来值得研究的方向.

References)

［1］ Molina J M，Pan X，Grimm C，et al.A framework for modelbased design of embedded systems for energy management［C］//Modeling and Simulation of Cyber-Physical Energy Systems(MSCPES).Piscataway，NJ:IEEE，2013:1-6.

［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.

［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.

［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.

［5］ King K N，Offutt A J.A fortran language system for mutationbased software testing［J］.Software:Practice and Experience，1991，21(7):685-718.

［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.

［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.

［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.

［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.

［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.

［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.

［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).

［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.

［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.

［15］ McMinn P.Search-based software test data generation:a survey［J］.Software Testing，Verification and Reliability，2004，14(2):105-156.