协议一致性测试的错误诊断研究

论文摘要

协议测试的目的是为了保证协议实现按照协议描述稳定可靠地运行。最近几年随着网络技术的发展，网络规模的增大，协议测试变得越来越重要。协议测试有很多种，协议一致性测试是其它测试的基础。协议一致性测试可以分为两类：主动测试和被动测试。主动测试是测试者通过观察被测系统的输入输出行为，最终推断出某些信息的过程，在这个过程中输入序列是可控制的，输出序列通过观察可以得到。主动测试的优点是可以针对可能的错误，设计测试例。被动测试只需要通过监听来收集数据，然后通过分析数据来检测错误。被动测试虽然不能控制输入序列，但由于它不会影响网络的正常工作，特别适用于做在线测试，现在应用得也比较广泛。检测到错误后，如何诊断错误是一个重要的问题。本文就是围绕错误诊断的相关问题进行研究。 本文的研究工作主要集中在以下几个方面： 1．主动测试中基于有限状态机的错误诊断 主动测试中检测到错误后，如何尽快定位错误一直是一个研究热点。本文在分析了一个已有的基于有限状态机的错误诊断方法后，提出了一个新的基于有限状态机的错误诊断算法，该算法利用已经确定正确的转换信息以及可疑转换的下一个输入／输出对的头状态集合等信息来高效完全地诊断单个错误。新提出的错误诊断算法与已有的一些诊断算法的比较结果说明该算法效率更高。接着本文又提出了一个基于UIO测试序列的错误诊断算法，该算法充分利用了UIO测试序列给出的判定消息及测试序列中的其它消息，从而能高效完全地诊断单个错误，最后用实验数据给出了本文算法和原始算法之间的比较结果。 2．被动测试中基于有限状态机的错误诊断 和主动测试中的错误诊断相比较，被动测试中的错误诊断更复杂，因为进行被动测试时不能设计测试例，只能被动的观察，所以已有的主动测试中的错误诊断算法不大适用于被动测试。本文在一个已有的单个错误诊断算法的基础上，结合主动测试方法和多观察几步枚举排除法提出了两个改进错误诊断算法，最后通过BGP协议上的实验给出了该算法和已有算法的比较结果。

论文目录

• 摘要
• Abstract
• 图目录
• 表目录
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.2.1 形式化技术
• 1.2.2 一致性测试
• 1.2.2.1 测试框架和方法
• 1.2.2.2 主动测试方法
• 1.2.2.3 被动测试方法
• 1.2.3 测试分析
• 1.3 研究目的和研究方案
• 1.4 论文结构
• 第二章 基于状态机模型的一致性测试理论
• 2.1 FSM的基本理论
• 2.1.1 FSM的定义
• 2.1.2 EFSM的定义
• 2.1.3 错误模型
• 2.2 协议一致性测试中的主动测试
• 2.2.1 一致性的定义
• 2.2.2 状态机测试的五个基本问题
• 2.2.2.1 自引导（Homing）序列
• 2.2.2.2 同步序列
• 2.2.2.3 区分序列
• 2.2.2.4 状态验证序列
• 2.2.3 主动测试
• 2.3 基于状态机的被动测试
• 2.3.1 基于FSM模型的错误检测
• 2.3.2 基于EFSM模型的错误检测
• 2.3.2.1 正向推理
• 2.3.2.1.1 直观算法
• 2.3.2.1.2 改进算法
• 2.3.2.2 逆向推理
• 2.4 小结
• 第三章 主动测试中基于FSM的错误诊断
• 3.1 基于FSM的错误诊断
• 3.1.1 错误诊断的基本过程
• 3.2 Ghedamsi的错误诊断方法
• 3.2.1 算法介绍
• 3.2.2 示例
• 3.3 新的基于FSM的错误诊断方法
• 3.3.1 算法介绍
• 3.3.2 算法复杂度分析和比较
• 3.3.3 实例
• 3.4 基于UIO测试序列的错误诊断
• 3.4.1 算法介绍
• 3.4.2 实验结果
• 3.4.2.1 两个FSM上的实验
• 3.4.2.2 随机生成的有限状态机上的实验
• 3.5 结束语
• 第四章 被动测试中基于FSM的错误诊断
• 4.1 被动测试中基于FSM的错误诊断
• 4.2 Miller的逆向判定法
• 4.2.1 错误检测介绍
• 4.2.2 错误诊断算法
• 4.3 逆向判定法的两个改进算法
• 4.3.1 结合主动测试
• 4.3.2 继续被动观察枚举排除
• 4.3.3 在BGP协议上的模拟实验结果
• 4.3.4 结论
• 4.4 结束语
• 第五章 基于EFSM的错误诊断
• 5.1 基于逐步排除的方法
• 5.1.1 基本定义
• 5.1.1.1 EFSM模型
• 5.1.1.2 把EFSM转化成FSM的方法以及EFSM的错误模型
• 5.1.2 EFSM的错误诊断
• 5.1.2.1 诊断方法概述
• 5.1.2.2 三种错误函数及其属性
• 5.1.3 错误诊断的算法
• 5.1.4 附加的诊断
• 5.2 基于逻辑推理的方法
• 5.2.1 错误模型
• 5.2.2 算法描述
• 5.2.3 结论
• 5.3 小结
• 第六章 结束语
• 6.1 总结
• 6.2 进一步的研究工作
• 参考文献
• 读博期间发表的论文
• 读博期间参加的科研项目
• 致谢