协议一致性测试序列生成及错误诊断算法设计

摘要

通信协议是计算机网络和通信网络中各种通信实体或进程之间相互交换信息所遵守的一组规则。协议测试保证协议实现的正确性,协议一致性测试是协议测试中各部分的基础,而测试序列生成技术和错误诊断技术是一致性测试的关键技术。
　　 本文以有限状态机为基础,结合现有测试序列生成技术的优点,提出了新的优化测试序列生成算法。该算法在待测转移后附加唯一输入输出序列以确保转移到达正确预定状态,并重新构建有限状态机对应的有向图,通过对该图的遍历得到优化的测试序列。
　　 错误诊断算法在协议测试中发现错误时,进行错误定位。本文在Ghedamsi错误诊断算法的基础上,提出了新的诊断算法,该算法充分利用了协议测试的中间结果以及唯一输入输出序列的特性,大大缩减了算法的复杂度。

目录

文摘

英文文摘

第一章 绪论

1.1 研究背景

1.2 国内外研究现状

1.2.1 一致性测试的测试序列生成技术

1.2.2 一致性测试的错误诊断

1.3 本文研究内容

1.3.1 本文目标及研究内容

1.3.2 关键问题及采用的研究方案

1.4 章节安排

第二章 协议一致性测试相关理论

2.1 协议与协议测试

2.2 协议一致性测试

2.2.1 协议一致性测试的基本概念

2.2.2 协议一致性测试的过程

2.3 形式化技术

2.3.1 有限状态机(Finite State Machine:FSM)模型

2.3.2 Petri网(Petri Net:PN)模型

2.3.3 进程代数

2.3.4 时序逻辑TL

2.3.5 构造类别代数

2.4 基于有限状态机模型的一致性测试

2.4.1 有限状态机的基本概念

2.4.2 基于有限状态机的测试序列生成技术

2.4.3 基于FSM的错误检测

2.5 小结

第三章 基于FSM的一致性测试序列生成算法

3.1 常用测试序列生成方法分析

3.2 测试序列生成算法优化

3.2.1 抽象建模

3.2.2 UIO序列求解

3.2.3 测试子序列原子化

3.2.4 新模型构造

3.2.5 新模型修正

3.2.6 优化测试序列求解

3.3 对比分析

3.3.1 BGP协议测试序列对比

3.3.2 随机生成的FSM的对比

3.4 小结

第四章 一致性测试错误诊断算法设计

4.1 基于FSM的错误诊断

4.1.1 错误诊断的基本过程

4.2 Ghedamsi的错误诊断方法

4.2.1 算法介绍

4.2.2 Ghedamsi算法缺陷分析

4.3 Ghedamsi算法优化

4.3.1 优化算法介绍

4.3.2 基于单个完整测试套的优化算法

4.3.3 正确性验证

4.4 对比分析

4.4.1 时间复杂度对比

4.4.2 TCP协议FSM及示例FSM上的对比测试

4.4.3 随机生成的FSM上的对比测试

4.5 小结

第五章 结束语

5.1 总结

5.2 展望

致谢

参考文献