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

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

作　　者：尤娟[1] 李俊全[1] 夏松[2] 

机构地区：[1]解放军信息工程大学,郑州450004 [2]解放军电子工程学院,合肥230037

出　　处：《计算机应用研究》2013年第5期1349-1352,共4页Application Research of Computers

摘　　要：针对EFSM中状态迁移不确定导致的协议一致性测试序列生成困难的问题,提出了一种协议一致性测试序列生成算法。该算法基于互异代表系理论为每个协议状态变迁赋权值,再基于分支界限法搜索生成的协议测试序列,将协议一致性测试序列的生成转换为寻找最小权值状态变迁路径的问题。该算法克服了无赋权要求的宽度优先搜索的缺陷,降低了测试序列的搜索与生成时间复杂度,提高了测试序列生成的效率。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 intro- duced a weighting method for every protocol state transition sequence at first. Then it generated test sequences through search- ing 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 ef- ficiency.

关 键 词：协议一致性测试 测试序列生成 扩展有限状态机 赋权值 互异代表系 分支界限法 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]