面向全迁移的小规模EFSM测试序列集生成方法

Generation method of small-scale EFSM test sequence suite for all transitions

针对在扩展有限状态机(extended finite state machine,EFSM)模型上测试序列集生成效率低、规模大等问题,提出了一种面向全迁移的小规模测试序列集生成方法。该方法基于改进的自适应多种群遗传算法(improved adaptive multi-population genetic algorithm,IAMGA)。首先,利用迁移覆盖增益设计适应度函数,使每次生成的可行迁移路径均能产生迁移覆盖增益;然后,根据个体的可行迁移划分子种群,并在子种群内使用轮盘赌算法进行选择,克服了“早熟”问题,提高了全迁移覆盖的成功率;再利用种群的平均路径通过率自适应地调整交叉和变异概率,加快了收敛速度;最后,通过倒序遍历测试序列集去除冗余序列,进一步压缩了测试序列集规模。实验结果表明,与面向单迁移的测试序列生成方法相比,本文所提出的测试序列生成方法面向全迁移,仅一次就能以90%以上的成功率生成满足全迁移覆盖的测试序列集;与传统的遗传算法相比,IAMGA算法生成的测试序列集的平均规模减少了50%,平均迭代次数也减少了20%。本文提出的测试序列集生成方法可有效提高EFSM测试序列集生成的效率和质量。

In order to address the issues of low efficiency and large scale of test sequence suite on the extended finite state machine(EFSM)model,a method of small-scale EFSM test sequence suite generation for all transitions was proposed based on the improved adaptive multi-population genetic algorithm(IAMGA).Firstly,the fitness function was designed by the transition coverage gain so that each generated feasible transition path can improve transition coverage.Next,the individual was selected within the subpopulations divided by feasible transition paths,which can overcome the premature convergence and improve the success rate of all transitions coverage.Then,the probabilities of crossover and mutation were adaptively adjusted based on the average path pass rate of the population so as to speed up convergence.Finally,by traversing the test sequence suite in reverse order,redundant sequences were removed,which further reduced the size of the test sequence suite.The experimental results show that compared with the generation test sequence method for single transition,this method which is designed for all transitions,can generate a test sequence suite that meets all transitions coverage with a success rate of more than 90%at a time.Compared with the traditional genetic algorithm,the average size of test sequence suite generated by IAMGA is reduced by 50%,while the average number of iterations is reduced by 20%.The method proposed in this paper can effectively improve the efficiency and quality of the generating EFSM test sequence suite.