基于分支界限搜索的EFSM协议测试序列生成算法

针对EFSM中状态迁移不确定导致的协议一致性测试序列生成困难的问题, 提出了一种协议一致性测试序列生成算法。该算法基于互异代表系理论为每个协议状态变迁赋权值, 再基于分支界限法搜索生成的协议测试序列, 将协议一致性测试序列的生成转换为寻找最小权值状态变迁路径的问题。该算法克服了无赋权要求的宽度优先搜索的缺陷, 降低了测试序列的搜索与生成时间复杂度, 提高了测试序列生成的效率。

Algorithm for generating test sequences based on branch and bound in EFSM model

In the protocol conformance testing based on the extended finite state machine model, this paper proposed a new protocol test sequence generation algorithm to solve the uncertain state traversing problem in test generation. The paper introduced a weighting method for every protocol state transition sequence at first. Then it generated test sequences through searching protocol state transitions in the branch and bound way. In this way, protocol conformance test sequences were reformulated to find the minimum state transition weighting paths. The proposed algorithm can overcome the shortcoming of bread first search without weighting methods. It is effective to generate protocol test sequences with a shorter search time and a higher efficiency.