基于扩展并行多组件状态机的网络协议测试研究

发布时间：2020-07-22 11:19

【摘要】：基于形式化方法的协议一致性测试是确保协议可靠性的基本手段。当前,一些新型互联网协议中存在不同的并行组件,而传统形式化方法难以描述这些特点,本文针对基于扩展并行多组件状态机的网络协议测试进行了深入的研究。本文综述了相关的研究现状,指出单一组件模型难以描述多组件的协议,而现有的多组件模型也难以描述组件间共享数据的情况;软件定义网络是带有并行多组件的新型互联网协议的典型代表,但尚缺少采用形式化方法的黑盒测试。本文研究了扩展并行多组件状态机的建模框架,分别提出了三种不同的扩展并行多组件状态机模型:为了描述并行组件间采用共享数据通信的情况,提出了读取外部变量的并行扩展有限状态机模型;为了描述多级流水线结构,提出了流水线扩展有限状态机模型,其同级组件间存在共享变量读写,跨级组件间存在单向消息传递;将消息传递与网络拓扑结合,提出了信息表扩展有限状态机模型。本文提出了基于定义使用路径的并行扩展有限状态机测试生成方法。首先生成内部变量的定义使用路径,然后使其可执行化并生成外部变量的定义使用路径。该方法是启发式方法,可用于变量无限取值的模型并避免状态空间爆炸。本文提出了基于可达图的并行扩展有限状态机层次化测试生成方法。该方法适用于变量取值有限的模型,其使用自底向上的可达图生成缓解状态空间爆炸,同时使用自顶向下的测试序列生成确保可执行。将前述两种测试生成方法分别应用于源地址验证协议测试,验证了方法的有效性。本文提出了流水线扩展有限状态机测试生成方法。首先将模型转换为数据图并找到数据路径;然后生成数据路径上的组件状态机的前导序列并组成测试序列。通过实验对比表明该方法能够生成系统覆盖模型的测试集,并有效控制了测试生成的时间和空间开销。将本方法应用于Open Flow交换机的一致性测试,发现了协议实现中的错误和协议中值得讨论的问题。本文提出了信息表扩展有限状态机测试生成方法。对于设计缺陷,用模型检测工具根据模型生成反例;对于实现错误,综合运用组件部分组合、拓扑对称化简和拓扑模拟执行生成扩展测试序列。该方法能够同时检测设计缺陷和实现错误,而且在与网络拓扑结合的同时,减缓状态空间爆炸的风险。
【学位授予单位】：清华大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP393.04

【相似文献】

相关期刊论文 前10条

1 黄勇;;游戏中的状态机[J];程序员;2008年12期

2 丘映莹;;复杂层次状态机的一种解决方案[J];煤炭技术;2013年03期

3 张俊;;状态机思路在单片机程序设计中的应用[J];今日电子;2009年02期

4 聂旭中;;状态机设计研究[J];洛阳师范学院学报;2009年02期

5 徐东明,黄海生;电路设计状态机描述算法研究[J];微电子学与计算机;2001年02期

6 罗宏洋;;状态机在离子注入机中的应用[J];电子工业专用设备;2009年09期

7 刘晖,李明禄;基于抽象状态机的网格系统设计和分析[J];电子学报;2003年S1期

8 杨朝红;刘海燕;肖庆;;基于扩展状态机的资源泄漏检测方法[J];装甲兵工程学院学报;2009年01期

9 冯学伟;王东霞;马国庆;李津;;基于状态机的入侵场景重构关键技术研究[J];微型机与应用;2010年17期

10 王咏武;;疯狂的火星虫——面向对象状态机实践指南[J];程序员;2004年08期

相关会议论文 前3条

1 易剑;马亚平;朱冰;;基于BOM的组合模型描述方法研究[A];2013第一届中国指挥控制大会论文集[C];2013年

2 周建;王健;;μC/OS的层次式状态机在人机界面中的应用[A];浙江省电子学会2010学术年会论文集[C];2010年

3 杨盛光;周干民;林大隽;高明伦;;基于状态机的IIC总线接口封装[A];全国第十五届计算机科学与技术应用学术会议论文集[C];2003年

相关重要报纸文章 前3条

1 ;做个RPG游戏主人翁[N];电脑报;2004年

2 广东 智轩;《做个RPG游戏主人翁》重点回顾[N];电脑报;2004年

3 北京大学信息科学与技术学院　马浩海　邵维忠　麻志毅;UML 2.0修成正果[N];计算机世界;2003年

相关博士学位论文 前2条

1 姚姜源;基于扩展并行多组件状态机的网络协议测试研究[D];清华大学;2015年

2 阮坚;异步控制电路设计与实现关键技术研究[D];国防科学技术大学;2008年

相关硕士学位论文 前10条

1 贺增川;基于状态机的微模块化程序设计技术在声学滑翔机中的应用研究[D];中国海洋大学;2015年

2 袁军;一种基于状态机的数字逻辑系统的功能验证方法[D];西南交通大学;2009年

3 王欣;基于状态机的移动终端应用软件设计[D];上海交通大学;2007年

4 林莉;状态机的若干代数性质[D];广西师范大学;2004年

5 李志军;基于状态机的安全漏洞检查机制的设计与实现[D];西安电子科技大学;2010年

6 陆原;基于状态机的计费系统框架的设计[D];复旦大学;2008年

7 赵海龙;[D];天津大学;2006年

8 尹鹏;基于多值逻辑状态机的需求分歧研究[D];西安理工大学;2007年

9 杨丹丹;基于抽象状态机的协议软件测试方法研究[D];西安电子科技大学;2010年

10 冯凌云;基于状态机AI技术的网络游戏战斗系统设计[D];复旦大学;2011年

本文编号：2765744