|
|
|
Adaptive generation algorithm for executable state identification
sequences in EFSM model |
| SHU Ting1,2, SUN Shou-qian1, WANG Hai-ning1, XU Wei-qiang2 |
1. College of computer science and Technology, Zhejiang University, Hangzhou 310027, China ;
2. College of Informatics and Electronics, Zhejiang SCITECH University, Hangzhou 310018, China |
|
|
|
Abstract 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．
|
|
Published: 23 December 2010
|
|
|
ESIS序列自适应生成算法
在以扩展有限状态机 (EFSM)为模型描述的协议一致性测试系统中,为了提高可执行状态验证序列 (ESIS)的计算效率,提出一种ESIS序列自适应生成算法.新算法采用基于可执行分析树 (EAT)的可执行分析方法确保生成的ESIS序列的可执行性.引入变迁区分度因子和节点收敛度因子,计算EAT搜索树节点权重来评价当前搜索方向的正确性.利用EAT搜索树节点权重函数作为节点搜索引擎,根据当前已经搜索节点的权重自适应选择下一步搜索的目标节点,把ESIS序列自动生成问题转化为自适应搜索权重最大的EAT节点问题来解决.实验数据表明,与宽度优先可执行性分析方法相比,自适应算法具有更小的状态格局搜索空间.
|
|
| ［1］ RAMLIGOM T, THULASIRAMAN K, DAS A. Context independent unique state identification sequences for testing communication protocols modelled as extended finite state machines ［J］. Computer Communications, 2003, 26(14) : 1622-1633．
［2］ ROBINSONMALLETT C, MUCKE T, LIGGESMEYER P, et al. Extended state identification and verification using a model checker ［J］. Journal on Information and Software Technology, 2006, 48 (10): 981-992.
［3］ RAMLIGOM T, THULASIRAMAN K, DAS A. Context independent unique sequences generation for protocol testing ［C］ ∥ IEEE INFOCOM ’96. CA, USA: IEEE,1996: 1141-1148．
［4］ NAIK K. Efficient computation of unique input/ output sequences in finite state machines ［J］. IEEE/ ACM Transactions on Networking , 1997,5 (4) :585-599．
［5］ HUANG Chungming, CHIANG Mengshu, JANG Mingyuhe . UIOE: A protocol test sequence generation method using the transition executability analysis (TEA) ［J］ . Computer Communication , 1998, 21 (16): 1462-147．
［6］ PETRENKO A, BORODAY S, GROZ R. Confirming configurations in EFSM testing ［J］. IEEE Trans Software Engineering, 2004, 30 (1) : 29-42．
［7］ SABNANI K, DAHBURA A. A protocol test generation procedure ［J］. Computer Networks and ISDN Systems, 1988, 15(4):285-297．
［8］ 舒挺,魏仰苏,吴柏青,等. EFSM可执行状态验证序列的生成［J］.北京邮电大学学报,2007, 30(2):84-88．
SHU Ting, WEI Yangsu, WU Baiqing, et al. An algorithm for generating executable state identification sequences in EFSM model ［J］. Journal of Beijing University of Posts and Telecommunications, 2007, 30(2):84-88． |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
