基于无关变量分离的EFSM测试数据进化生成
发布时间：2021-06-13 03:13
扩展有限状态机（EFSM）相比于有限状态机（FSM）能够更加精确地刻画系统的动态行为,因而广泛作为各种控制流与数据流系统的测试模型。在EFSM模型的测试中,使用搜索的方法获得触发目标测试路径的测试数据是近年来的一个研究热点。为进一步提高搜索效率,在遗传算法（GA）的基础上提出一种自动分离测试路径中无关输入变量的方法,该方法通过分析模型中变量与迁移间的关系,判定不影响子路径中谓词条件的无关输入变量,进而从个体中将其分离以实现搜索空间的自动缩减,提升测试数据生成效率。对几种具有不同复杂度的基准EFSM模型进行实验后的结果表明,该方法生成有效测试数据的成功率均达到98. 2%以上,且与未分离输入变量的遗传算法相比,所需平均迭代次数减少44. 7%～85. 9%,平均运行时间减少24. 1%～85. 5%。
【文章来源】：北京航空航天大学学报. 2019,45(05)北大核心EICSCD
【文章页数】：11 页
【部分图文】：
ATM的扩展有限状态机模型Fig．1ExtendedfinitestatemachinemodelofATM将不同的测试数据代入到LTP中所实际经过的关系可以划分为变量与赋值语句及谓词条件中
北京航空航天大学学报2019年图2EFSM中的一条测试路径Fig．2AtestpathinEFSM图3不同变量间的关系图Fig．3ＲelationshipdiagramamongdifferentvariablesQ=1110111000100011根据矩阵Q及算法3可以得出:变量{a，b，c，d}的取值会对迁移t3的谓词条件能否满足造成影响，而迁移t4的谓词条件仅受变量d的影响，由于{a，b，c，d}均为输入变量，因此对于LTP的子路径L'TP=t4来讲，变量{a，b，c}属于无关输入变量，可以分离，其起始分离迁移为t3，而变量d对应的起始分离迁移为t4，说明其在整个测试路径中不能分离。3无关输入变量的自动分离方法3．1自动分离方法及测试数据生成过程基于无关输入变量分离与遗传算法的EFSM测试数据生成过程如图4所示。图4EFSM测试数据生成的实现过程Fig．4ImplementationprocessofEFSMtestdatageneration设待测EFSM模型M包含的输入变量为Iv={x1，x2，…，xn}，变量的取值空间为D，选取M中的一条目标测试路径LTP=［t0，t1，…，tm－1］，设遗传算法产生的初始种群包含k个个体，不同个体对应的测试数据分别为X1，X2，…，Xk，不同个体以其对应测试数据作为输入，在动态执行EFSM模型时，所能实际经过的路径分别为LTP1，LTP2，…，LTPk，以LTP表示相应路径的路径长度(路径所包含迁移的个数)，由1．2节可知，实际经过的路径长度越长，该个体的适应度值越好。无关输入变量的分离方法为:在每一次迭代中，
(t1)+2，…，xj(t2)}，…，{xj(tm－1)+1，xj(tm－1)+2，…，xj(tm)}，且0＜j(t1)＜j(t2)＜…＜j(tm)＜n，则此时搜索空间将分别变为Dt1?∏ni=j(t1)+1DiDt2?∏ni=j(t2)+1Di?Dtm?∏ni=j(tm)+1Di(5)设该测试路径目标解的空间为Dr，则D，Dt1，Dt2，…，Dtm及Dr的关系可以用图5表示。由图5可知，随着分离变量的增多，搜索空间逐渐减小，在更小的搜索空间内进行搜索，将显著提高遗传算法的搜索效率［16］。图5不同搜索空间之间的关系Fig．5Ｒelationshipbetweendifferentsearchspaces4实验为了验证采用本文方法对遗传算法搜索效率的影响，将采用全空间搜索(GlobalSpaceSearch，GSS)的传统遗传算法［3］与本文无关输入变量分离(IrrelevantInputVariablesSeparation，IIVS)的遗传算法进行对比，2种方法均采用二进制编码、轮盘赌选择、使用单点交叉及单点变异，算法的一些其他参数为:交叉概率0．75，变异概率0．1，初始种群规模25，最大迭代次数50000代。此外，为进一步验证IIVS方法的优势，本文还对使用IIVS方法的随机算法(ＲandomAlgorithm，ＲA)与全空间搜索的随机算法［17］进行了比较，与遗传算法中无关输入变量的分离方法类似，IIVS-ＲA也是在每次迭代中判断实际经过的路径是否包含可分离输入变量的起始分离迁移，若包含则在以后的搜索过程中固定该变量的取值，以此达?
【参考文献】：
期刊论文
[1]基于EFSM不定型切片测试用例自动生成的研究[J]. 苏宁,郭俊霞,李征,赵瑞莲. 计算机研究与发展. 2017(03)
[2]基于路径自动分割的测试数据生成方法[J]. 廖伟志. 电子学报. 2016(09)
[3]基于程序变异的Simulink模型测试方法[J]. 周艺斌,殷永峰,李骁丹,王明威. 北京航空航天大学学报. 2015(03)
[4]回归测试数据进化生成[J]. 巩敦卫,任丽娜. 计算机学报. 2014(03)
[5]基于搜索空间自动缩减的路径覆盖测试数据进化生成[J]. 张岩,巩敦卫. 电子学报. 2012(05)
[6]基于扩展有限状态机测试中测试输入数据自动选取的研究[J]. 张涌,钱乐秋,王渊峰. 计算机学报. 2003(10)
本文编号：3226874
【文章来源】：北京航空航天大学学报. 2019,45(05)北大核心EICSCD
【文章页数】：11 页
【部分图文】：
ATM的扩展有限状态机模型Fig．1ExtendedfinitestatemachinemodelofATM将不同的测试数据代入到LTP中所实际经过的关系可以划分为变量与赋值语句及谓词条件中
北京航空航天大学学报2019年图2EFSM中的一条测试路径Fig．2AtestpathinEFSM图3不同变量间的关系图Fig．3ＲelationshipdiagramamongdifferentvariablesQ=1110111000100011根据矩阵Q及算法3可以得出:变量{a，b，c，d}的取值会对迁移t3的谓词条件能否满足造成影响，而迁移t4的谓词条件仅受变量d的影响，由于{a，b，c，d}均为输入变量，因此对于LTP的子路径L'TP=t4来讲，变量{a，b，c}属于无关输入变量，可以分离，其起始分离迁移为t3，而变量d对应的起始分离迁移为t4，说明其在整个测试路径中不能分离。3无关输入变量的自动分离方法3．1自动分离方法及测试数据生成过程基于无关输入变量分离与遗传算法的EFSM测试数据生成过程如图4所示。图4EFSM测试数据生成的实现过程Fig．4ImplementationprocessofEFSMtestdatageneration设待测EFSM模型M包含的输入变量为Iv={x1，x2，…，xn}，变量的取值空间为D，选取M中的一条目标测试路径LTP=［t0，t1，…，tm－1］，设遗传算法产生的初始种群包含k个个体，不同个体对应的测试数据分别为X1，X2，…，Xk，不同个体以其对应测试数据作为输入，在动态执行EFSM模型时，所能实际经过的路径分别为LTP1，LTP2，…，LTPk，以LTP表示相应路径的路径长度(路径所包含迁移的个数)，由1．2节可知，实际经过的路径长度越长，该个体的适应度值越好。无关输入变量的分离方法为:在每一次迭代中，
(t1)+2，…，xj(t2)}，…，{xj(tm－1)+1，xj(tm－1)+2，…，xj(tm)}，且0＜j(t1)＜j(t2)＜…＜j(tm)＜n，则此时搜索空间将分别变为Dt1?∏ni=j(t1)+1DiDt2?∏ni=j(t2)+1Di?Dtm?∏ni=j(tm)+1Di(5)设该测试路径目标解的空间为Dr，则D，Dt1，Dt2，…，Dtm及Dr的关系可以用图5表示。由图5可知，随着分离变量的增多，搜索空间逐渐减小，在更小的搜索空间内进行搜索，将显著提高遗传算法的搜索效率［16］。图5不同搜索空间之间的关系Fig．5Ｒelationshipbetweendifferentsearchspaces4实验为了验证采用本文方法对遗传算法搜索效率的影响，将采用全空间搜索(GlobalSpaceSearch，GSS)的传统遗传算法［3］与本文无关输入变量分离(IrrelevantInputVariablesSeparation，IIVS)的遗传算法进行对比，2种方法均采用二进制编码、轮盘赌选择、使用单点交叉及单点变异，算法的一些其他参数为:交叉概率0．75，变异概率0．1，初始种群规模25，最大迭代次数50000代。此外，为进一步验证IIVS方法的优势，本文还对使用IIVS方法的随机算法(ＲandomAlgorithm，ＲA)与全空间搜索的随机算法［17］进行了比较，与遗传算法中无关输入变量的分离方法类似，IIVS-ＲA也是在每次迭代中判断实际经过的路径是否包含可分离输入变量的起始分离迁移，若包含则在以后的搜索过程中固定该变量的取值，以此达?
【参考文献】：
期刊论文
[1]基于EFSM不定型切片测试用例自动生成的研究[J]. 苏宁,郭俊霞,李征,赵瑞莲. 计算机研究与发展. 2017(03)
[2]基于路径自动分割的测试数据生成方法[J]. 廖伟志. 电子学报. 2016(09)
[3]基于程序变异的Simulink模型测试方法[J]. 周艺斌,殷永峰,李骁丹,王明威. 北京航空航天大学学报. 2015(03)
[4]回归测试数据进化生成[J]. 巩敦卫,任丽娜. 计算机学报. 2014(03)
[5]基于搜索空间自动缩减的路径覆盖测试数据进化生成[J]. 张岩,巩敦卫. 电子学报. 2012(05)
[6]基于扩展有限状态机测试中测试输入数据自动选取的研究[J]. 张涌,钱乐秋,王渊峰. 计算机学报. 2003(10)
本文编号：3226874
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3226874.html
