Abstract: Test case generation of EFSM (Extended Finite State Machine Models) includes test path generation and test data generation. However, nowadays most research into EFSM testing focuses on test path generation. In order to explore the automatic test generation, a test data generation method oriented to the path of EFSM models was proposed. A Tabu Search (TS) strategy was adopted to automatically generate test data, and the key factors that affect the performance of test data generation in EFSM models were analyzed. Moreover, the test generation efficiency was compared with that of Genetic Algorithm (GA). The experimental results show that the proposed method is promising and effective, and it is obviously superior to the GA in the test generation for EFSM models.

Key words: Tabu Search (TS) algorithm, Genetic Algorithm (GA), Extended Finite State Machine (EFSM), test data generation, Tabu table

摘要： 可扩展有限状态机(EFSM)模型的测试用例生成包括测试路径生成和测试数据生成两部分。然而，目前针对EFSM模型的测试研究大多集中于测试路径生成。为探索路径上测试数据的自动生成，提出一种面向EFSM路径的测试数据生成方法，利用禁忌搜索(TS)策略实现了EFSM测试数据的自动生成；分析了影响EFSM测试数据生成的关键因素，并与遗传算法(GA)的生成效率进行了比较。实验结果表明：基于TS算法的EFSM模型测试数据自动生成是确实可行的，其测试生成效率相对于GA有很大提高。

关键词: 禁忌搜索算法, 遗传算法, 可扩展有限状态机, 测试数据生成, 禁忌表