基于无关变量分离的EFSM测试数据进化生成

扩展有限状态机（EFSM）相比于有限状态机（FSM）能够更加精确地刻画系统的动态行为，因而广泛作为各种控制流与数据流系统的测试模型。在EFSM模型的测试中，使用搜索的方法获得触发目标测试路径的测试数据是近年来的一个研究热点。为进一步提高搜索效率，在遗传算法（GA）的基础上提出一种自动分离测试路径中无关输入变量的方法，该方法通过分析模型中变量与迁移间的关系，判定不影响子路径中谓词条件的无关输入变量，进而从个体中将其分离以实现搜索空间的自动缩减，提升测试数据生成效率。对几种具有不同复杂度的基准EFSM模型进行实验后的结果表明，该方法生成有效测试数据的成功率均达到98.2%以上，且与未分离输入变量的遗传算法相比，所需平均迭代次数减少44.7%~85.9%，平均运行时间减少24.1%~85.5%。 

Evolutionary generation of test data for EFSM based on irrelevant variable separation

Extended finite state machine (EFSM), a more accurate test model than finite state machine (FSM), has been widely used to describe dynamic behavior of system, and thus has been taken as the test model of various control flow and data flow systems. For EFSM model test, using search method to obtain test data to trigger a given test path has become a research hotspot in recent years. In order to improve the search efficiency, this paper proposed a method that originates from genetic algorithm (GA) and can automatically separate irrelevant input variables in a test path. By analyzing the relationship between variables and state transitions in EFSM and separating irrelevant input variables from the individual that does not affect the transition's guard in the sub-test path, the new method reduced the search space and enhanced the efficiency of test data generation. The experimental results on various complex benchmark EFSM models show that the success rate of the new method to generate effective test data is larger than 98.2%. Compared to the traditional genetic algorithm, the average number of iterations of the new method is reduced by 44.7%-85.9% and the average running time is reduced by 24.1%-85.5%.