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
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．
SHU Ting, SUN Shou-qian, WANG Hai-ning, XU Wei-qiang. Adaptive generation algorithm for executable state identification
sequences in EFSM model. J4, 2010, 44(11): 2183-2187.
［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．
