协议测试.doc

摘要 协议测试是提高协议实现正确性的重要保证。被动测试是一种比较新的协议测试概念，本文的主要工作是将被动测试方法应用于协议测试中。 本文介绍了协议的形式化描述工具：FSM/NFSM/EFSM/CFSM模型，总结了在以上几个模型上做被动测试的现状和遇到的难点问题。 本文重点讨论了EFSM模型上被动测试的变量管理问题，总体思路是要将尽可能多的协议信息记录下来，以发现被测系统中的错误，同时尽量降低算法复杂度。在此基础上，提出了多个变量管理方法，并对各个方法进行了综合，设计了变量管理的综合算法。 在实践方面，设计了与协议无关的被动测试系统的总体框架，该系统具有良好的通用性和可扩展性。介绍了各个模块的实现，其中重点介绍了变量管理器。介绍了采用被动测试对BGP和OSPF协议实现的测试情况。对于OSPF中协议参数的测试体现了变量管理系统的能力，测试结果验证了算法的正确性和有效性。 最后，本文总结了变量管理问题在被动测试中的意义，提出了被动测试研究的进一步工作方向。 关键字协议测试 被动测试 扩展有限状态自动机 约束满足问题 Abstract Protocol testing is very important to guarantee the correctness of protocol implementations. Passive Testing is a new concept of protocol testing in recent years. In this paper, we try to apply passive testing method to routing protocol testing. We show several formal models for protocol specifications: Finite State Machine, Non-deterministic Finite State Machine, Extended Finite State Machine and Communicating Finite State Machine. The former works on passive testing on these models are reviewed. Problems are also raised. Our work concentrates in the problem of variable management for passive testing EFSM model. Several solutions in different views are suggested and analyzed. An integrated algorithm is suggested. We also show the implementation of passive testing on FSM/NFSM/EFSM models with the examples of testing BGP/OSPF protocols. A protocol-independent passive testing architecture is introduced. Each part of the system is described. The parts for variable management are explained in detail. The experimental results of the passive testing on BGP/OSPF are also shown and analyzed. Finally, the importance of the variable management in passive testing is suggested. And the future work is also described. Keyword Protocol Testing Passive Testing Extended Finite State Machine (EFSM) Constraints Satisfaction Problem (CSP) 目 录 摘要 1 关键字 1 Abstract 2 Keyword 2 目 录 3 第一章 引言 5 1.1. 背景 5 1.2. 论文章节安排 6 第二章 协议的形式化描述和被动测试的理论概述 7 2.1. 协议的形式化描述方法 7 2.2. 协议测试的基本概念 8 2.3. 被动测试 9 第三章 FSM/NFSM被动测试的实验系统及实验结果 13