Please wait a minute...
浙江大学学报(工学版)
J4  2010, Vol. 44 Issue (11): 2183-2187    DOI: 10.3785/j.issn.1008973X.2010.11.025
计算机科学技术     
ESIS序列自适应生成算法
舒挺1,2, 孙守迁1,王海宁1,徐伟强2
1.浙江大学 计算机科学与技术学院,浙江 杭州 310027; 2.浙江理工大学 信息电子学院,浙江 杭州310018
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 SCITECH University, Hangzhou 310018, China
 全文: PDF  HTML
摘要：

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

国家自然科学基金资助项目(60702081); 浙江省科技厅重大专项资助项目(2006c11235).
通讯作者: 孙守迁，男，教授.     E-mail: ssqy@263.net
作者简介: 舒挺（1979-），男，浙江宁海人，博士生，从事计算机网络的研究工作. E-mail：shuting@zstu.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

舒挺, 孙守迁,王海宁,徐伟强. ESIS序列自适应生成算法[J]. J4, 2010, 44(11): 2183-2187.

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.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008973X.2010.11.025    或    http://www.zjujournals.com/eng/CN/Y2010/V44/I11/2183

［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］ ROBINSONMALLETT 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 Chungming, CHIANG Mengshu, JANG Mingyuhe . 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 Yangsu, WU Baiqing, 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．
[1] 李德骏,汪港,杨灿军,金波,陈燕虎. 基于NTP和IEEE1588海底观测网时间同步系统[J]. J4, 2014, 48(1): 1-7.
[2] 郭童,林峰. 基于混合遗传鱼群算法的贝叶斯网络结构学习[J]. J4, 2014, 48(1): 130-135.
[3] 杜瑞忠, 田俊峰, 张焕国. 基于信任和个性偏好的云服务选择模型[J]. J4, 2013, 47(1): 53-61.
[4] 张帅,孙建伶,徐斌,黄超,KAVS Aleksander J.. 基于RBAC的跨多企业服务组合访问控制模型[J]. J4, 2012, 46(11): 2035-2043.
[5] 陈岁生,卢建刚,楼晓春. 基于MDS-MAP和非线性滤波的WSN定位算法[J]. J4, 2012, 46(5): 866-872.
[6] 杨朝晖,李善平,林欣. 增量型上下文信息服务的质量优化实时调度[J]. J4, 2012, 46(1): 90-97.
[7] 潘巨龙,李善平,张道远. 无线传感器网络簇内可疑节点的博弈检测方法[J]. J4, 2012, 46(1): 72-78.
[8] 高庆,李善平,杨朝晖. 基于虚拟场的能量高效传感器网络地理路由[J]. J4, 2012, 46(1): 98-104.
[9] 钱剑锋, 尹建伟, 董金祥. 结构化P2P网络的语义发布/订阅系统
负载均衡算法[J]. J4, 2011, 45(10): 1710-1719.
[10] 杨朝晖,李善平,林欣. LBS中面向K-匿名服务资源约束的匿名度调节算法[J]. J4, 2011, 45(7): 1154-1160.
[11] 潘纲, 李石坚, 陈云星. ScudContext:信息-物理空间融合的大规模
环境上下文服务[J]. J4, 2011, 45(6): 991-998.
[12] 车建华, 何钦铭, 陈建海, 王备. 基于软件模拟的虚拟机系统故障插入工具[J]. J4, 2011, 45(4): 614-620.
[13] 张莉苹,潘纲,郑能干,杨国青,李红,赵民德. SmartC模型与代码一致性双向生成方法及开发平台[J]. J4, 2011, 45(1): 20-29.
[14] 李鉴庭,金心宇,唐军,张昱. 基于无线多媒体传感器网络的目标定位方法[J]. J4, 2011, 45(1): 45-49.
[15] 陈友荣, 俞立, 董齐芬, 洪榛. 基于近邻算法的无线传感器网络功率控制[J]. J4, 2010, 44(7): 1321-1326.