ESIS序列自适应生成算法

Adaptive generation algorithm for executable state identification sequences in EFSM model

在以扩展有限状态机(EFSM)为模型描述的协议一致性测试系统中,为了提高可执行状态验证序列(ESIS)的计算效率,提出一种ESIS序列自适应生成算法.新算法采用基于可执行分析树(EAT)的可执行分析方法确保生成的ESIS序列的可执行性.引入变迁区分度因子和节点收敛度因子,计算EAT搜索树节点权重来评价当前搜索方向的正确性.利用EAT搜索树节点权重函数作为节点搜索引擎,根据当前已经搜索节点的权重自适应选择下一步搜索的目标节点,把ESIS序列自动生成问题转化为自适应搜索权重最大的EAT节点问题来解决.实验数据表明,与宽度优先可执行性分析方法相比,自适应算法具有更小的状态格局搜索空间.

In the protocol conformance testing system specified in extended finite state machine （EFSM） model,an algorithm for adaptive generating executable state identification sequences （ESIS） is introduced to improve efficiency in the Computation of state identification sequences （SIS）.The executability of the ESIS generated in the novel algorithm can be ensured by an executability analysis method based on the executability analysis tree （EAT）.Transition distinguish degrees and node convergence degrees are introduced to compute the weight of the current node for the EAT,which can be used to evaluate the correctness of the current search direction.Using a search strategy based on the node-weight function for the EAT,the node which is to be the root of the new sub-spanning tree is adaptively selected based on the weight of the latest explored node.In this way,the problem of automatic ESIS generation is formulated as adaptive exploration of the maximum weight node from unexplored nodes in EAT.Experimental results show that the proposed method needs to explore less state configuration than the executability analysis algorithm based on bread-first-search.