清华大学毕业设计论文第 1 页摘要协议测试是提高协议实现正确性的重要保证。被动测试是一种比较新的协议测试概念，本文的主要工作是将被动测试方法应用于协议测试中。本文介绍了协议的形式化描述工具：FSM/NFSM/EFSM/CFSM 模型，总结了在以上几个模型上做被动测试的现状和遇到的难点问题。本文重点讨论了 EFSM 模型上被动测试的变量管理问题，总体思路是要将尽可能多的协议信息记录下来，以发现被测系统中的错误，同时尽量降低算法复杂度。在此基础上，提出了多个变量管理方法，并对各个方法进行了综合，设计了变量管理的综合算法。在实践方面，设计了与协议无关的被动测试系统的总体框架，该系统具有良好的通用性和可扩展性。介绍了各个模块的实现，其中重点介绍了变量管理器。介绍了采用被动测试对 BGP 和 OSPF 协议实现的测试情况。对于 OSPF 中协议参数的测试体现了变量管理系统的能力，测试结果验证了算法的正确性和有效性。最后，本文总结了变量管理问题在被动测试中的意义，提出了被动测试研究的进一步工作方向。关键字协议测试 被动测试 扩展有限状态自动机 约束满足问题清华大学毕业设计论文第 2 页AbstractProtocol 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.KeywordProtocol TestingPassive TestingExtended Finite State Machine (EFSM)Constraints Satisfaction Problem (CSP)清华大学毕业设计论文第 3 页目 录摘要 .1关键字 .1ABSTRACT .2KEYWORD .2目 录 .3第一章 引言 .51.1. 背景 .51.2. 论文章节安排 .6第二章 协议的形式化描述和被动测试的理论概述 .72.1. 协议的形式化描述方法 .72.2. 协议测试的基本概念 .82.3. 被动测试 .9第三章 FSM/NFSM 被动测试的实验系统及实验结果 .133.1. FSM/NFSM 被动测试系统的结构 .133.2. 协议数据包的表示和协议包解析 .143.3. 测试控制器 .153.4. 采用 FSM 描述 BGP 的被动测试实验 .153.5. 采用 NFSM 描述 OSPF 的被动测试实验 .16第四章 EFSM 被动测试中变量管理问题的算法研究 .184.1. 区域状态机的思路 .184.2. 可能变量值的存储 .184.3. 利用条件的 “暗示信息 ”.214.4. 适度状态分裂 .244.5. 记录历史 .244.6. 算法的综合问题 .25第五章 EFSM 被动测试的实现 .285.1. EFSM 被动测试系统的结构 .285.2. 变量管理器的框架 .295.3. 数据翻译器 .