自适应EFSM可执行测试序列生成  

Adaptive Executable Test Sequences Generation from an Extended Finite State Machine

作　　者：舒挺[1] 刘良桂[1] 徐伟强[1] 李文书[1] 

机构地区：[1]浙江理工大学信息学院

出　　处：《计算机研究与发展》2012年第6期1211-1219,共9页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61101111;61002016;60702081);浙江省自然科学基金项目(Y1090980);浙江理工大学科研启动基金项目(Y1090980)

摘　　要：基于扩展有限状态机(EFSM)模型自动生成测试序列可以提高测试效率.由于EFSM模型包含丰富的变量和谓词条件,它们之间的冲突可能导致自动生成的测试序列不可执行.对EFSM变迁及变迁之间的关联关系进行了详细的讨论和分析,定义了一个邻接变迁关联图,提出了一种自适应EFSM可执行测试序列生成算法.新算法首先根据变量和谓词包含情况对变迁进行分类,然后深入挖掘了邻接变迁之间的关联关系,最后,基于自适应预测搜索函数启发式引导可达性分析树扩展生成可执行的测试序列.实验数据表明,与宽度优先可达性分析方法相比,新算法可以有效降低可达性分析过程中产生状态空间爆炸问题的概率,从而提高测试序列自动生成的效率.在最坏的情况下,新算法的计算时空复杂度也等同于宽度优先算法.Automatic test sequences generation using the extended finite state machine （EFSM） model can improve the test efficiency. However, unexecutable test sequences due to the conflicts among the predicates and internal variables of transitions in an EFSM may exist. The existence of unexecutable test sequences increases the difficulties of automatic test sequences generation. How to determine whether a test sequence is executable becomes a challenging problem. In this paper, the intrinsic characteristics and dependence relations among transitions in an EFSM are discussed in detail. Then an adaptive approach to automated executable test sequence generation for EFSM models is proposed~ which is based on an adjacency transition dependence graph. In this method, firstly, transitions are classified according to their variables and predicates~ Then dependence relationships between any two adjacency transitions can be mined and defined; Finally, executable test sequences are generated through expanding a reachability analysis tree, with the heuristic guidance using an adaptive exploration function. Experimental results show that, compared with the reachability analysis algorithm based on bread-first-search, the proposed method can reduce the number of states explored in the reachability analysis process and relieve the state explosion problem. As a result, the efficiency of automatic executable test sequences generation is improved. In the worst case, time and space complexity of the proposed method is also not more than the bread-first-search algorithm.

关 键 词：自适应搜索 扩展有限状态机 状态格局 可达性分析 测试序列 

分 类 号：TP393.06[自动化与计算机技术—计算机应用技术]