网络设备中的软件、配置错误往往会引起网络服务失效或者性能下降。协议故障检测是要发现协议实现中的错误,减少由此引起的网络失效,提高网络的运行水平。被动测试是一种故障检测方法,通过对运行时设备进行监测,找出系统中可能存在的故障。本文研究被动测试理论,应用于网络协议实现的故障检测。 本文综述了现有的协议故障检测方法,包括主动测试、网络管理、协议分析等,分析了现有方法的适用范围,指出它们在线检测能力的不足。被动测试由于能够对正在运行的设备进行实时、在线验证,适合网络故障管理的需求,近年来得到了较大的发展。 本文建立了被动测试的理论框架。从被动测试概念出发,作者论述了被动测试的原理和一般性的方法,提出了逆向搜索技术,用于测试覆盖计算。主动测试的慢环境假设在被动测试中并不成立,本文通过对各种网络协议进行研究,提出了适用于互联网协议被动测试的事件驱动模型。 本文提出了一个有效的被动测试算法,用来检测协议实现数据部分的错误。算法使用事件驱动的扩展有限状态机模型,通过解决路径可满足性来进行格局跟踪。算法实现要考虑各种协议变量,整型变量是较难处理的一类变量,本文提出了整型变量的线性规划和区间细化算法,分别用来精确/近似求解系统变量,实现协议变量跟踪。在正向检查后,使用逆向搜索来检验格局的可达性,设计了一种启发性算法来提高收敛速度。 本文提出了被动测试和协议仿真相结合的测试床测试方法,在测试床中用协议仿真模拟出各种网络环境,用被动测试来进行协议分析。协议仿真和协议分析的分离,可以充分利用现有协议仿真工具,降低故障检测复杂度。本文将协议仿真内容分为网络激励和协议相关激励,提出了一种使用已有实现的简单仿真方法,以Linux平台为例说明仿真的实现方法,并讨论了确定性和随机两种激励注入的方式。 为了验证被动测试方法的有效性,作者开发了一个通用的被动测试平台,实现了被动测试各种算法,应用于协议故障检测。在实验中发现了观测不精确的问题,这是由于观测点往往不能放置在IUT访问点上引起的,本文分析了观测不精确的原因以及对被动测试的影响,提出了解决问题的方法。为了验证被动测试方法的有效性,本文做了大量测试实验,对OSPF/BGP/TCP等协议进行摘要了被动测试,发现了网络设备中一些错误和互操作性问题。在测试床中,利用被动测试和协议仿真对一台路由器的OSPF实现进行了测试,发现了其OSPF邻接状态机中的DR选举问题。另一个实验演示了如何通过放置观测器来进行网络故障定位。 网络协议常常存在可选项而需要用非确定性状态机来描述,协议实现采用某些特定选项。本文了研究如何从非确定性协议描述中辨别确定性的协议实现的问题。非确定性变迁可以分为可观察和不可观察两类,实现可以是或者不是描述的子状态机,这样就产生了四种情形。本文由浅入深的讨论每种情形下的被动测试算法,采用逆向搜索技术进行状态机辨认,并以互联网实际协议为例说明各种方法的使用。关键词:被动测试,协议测试,故障检测,非确定性状态机