（计算机软件与理论专业论文）路由协议测试系统研究及实现.pdf

巾罔科学投术人。产埘! i 学位论文摘蛰摘要随着i n t e m e t 技术的不断发展以及各种新的应用的不断出现，网络规模不断扩大，结构同趋复杂，路由器性能的好坏对网络性能起着举足轻重的作用。每一个路由器都是遵照路由协议的要求产，l 路由信息的，但生产过程中路山器质量是否得到保证，足甭完全遵i ) ：了路协议的说明，只有经过路山协议测试之后j 。能证明，路山咖泌的测试足保证务种网络路t | j 产：品棚! i 连通，正确的相互操作的重耍于段。要实施测试就必须要f f 测试系统的义持，但足，目前的协议测试系统的存在一个主要的不足之处：难以扩展，通用性较差。针对这一问题，本文主要讨沦了一种易于扩展的协议测试环境的设计，以及在此基础上实现的路由协议测试系统。围绕这个中心，本文 要完成了以下儿方面的工作：( 1 ) 详细阅读与路山协议相关的文档，分析、 ：1 纳路山协议的特点。( 2 ) 对路由m 议一致性测试进行了研究，重点讨论了路由咖议测试集的生成方法和路协议f e j n 试方法。( 3 ) 对路由协议互操作性测试进行了研究，提出了种基于被动测试的路由协议互操作性测试方法。( 4 ) 研究了基丁t c l 的通用协议测试环境，阐述了测试环境实现的可行性，并指出了测试环境所要达到的目标和应实现的功能。( 5 ) 设计并实现了路山协议测试系统。( 6 ) 将测试系统应用丁实际的阱泌测试。关键词：蹄阱议，测试系统，j 办议测试，测试力法，t c中田科学挂术人学城f 学似论史摘蔓a b s t r a c tw i t ht h er a p i dd e v e l o p m e n to fi n t e r n e tt e c h n o l o g ya n da p p e a r a n c eo fm o r ea n dm o r ea p p l i c a t i o n s ，t h es c a l eo fn e t w o r kb e c o m e sl a r g e ra n dl a r g e ra n dt h es t r u c t u r eo fn e t w o r kb e c o m e sm o r ec o m p l i c a t e d p e r f o r m a n c eo fr o u t e r so nn e t w o r ki sm o s t l yr e s p o n s i b l ef o rt h ep e r f o r m a n c eo ft h en e t w o r k a n de v e r yr o u t e rp r o d u c e sr o u t i n gi n f o r m a t i o na c c o r d i n gt op r o t o c o ls p e c i f i c a t i o n ，b u ti t i sn o ts u r ew h e t h e rt h eq u a l i t yo fr o u t e r sc a nb eg u a r a n t e e dd u r i n gp r o d u c t i o np r o c e d u r ea n dw h e t h e rt h ei m p l e m e n t a t i o n so fr o u t i n gp r o t o c o l si nt h er o u t e r sf u l l yc o n f o r mw i t ht h ep r o t o c o ls p e c i f i c a t i o n s 。t h a tc a nb ed e c i d e db yt e s t i n go fr o u t i n gp r o t o c 0 1 t e s t i n go fr o u t i n gp r o t o c o l si sa ni m p o r t a n tm e a n st oa s s u r et h ec o m m u n i c a t i o na n dc o r r e c to p e r a t i o na m o n ga l lk i n d so fr o u t i n gd e v i c e s i no r d e rt oc a r r yo u tt e s t i n g ，t h es u p p o r to ft e s t i n gs y s t e mi si n d i s p e n s a b l e h o w e v e r , m o s tt e s t i n gs y s t e m sh a v eam a i nd e f e c tt h a ti ti sh a r dt oe x t e n dt h e m a i m i n ga ts u c hap r o b l e m ，t h i sp a p e rm a i n l yd i s c u s st h ed e s i g no fe x t e n d a b l ep r o t o c o lt e s t i n gs y s t e ma n dt h ei m p l e m e n t a t i o no ft e s t i n gs y s t e mo fr o u t i n gp r o t o c o l sb a s e do nt h i sd e s i g n c i r c l i n gt h i st o p i c ，i nt h i sd i s s e r t a t i o nw ef i n i s h e ds e v e r a lp a r t so fw o r ka sf o l l o w s ：( i ) c a r e f u l l yr e a dd o c u m e n t sr e l a t e dw i t hr o u t i n gp r o t o c o l s ，t h e na n a l y z et h em o s t l yu s e dp r o t o c o l so ni n t e m e ta n dc o n c l u d et h ec h a r a c t e ro fr o u t i n gp r o t o c o l s ( 2 ) m a k er e s e a r c ho nc o n f o r m a n c et e s t i n go fr o u t i n gp r o t o c o l s ，i nw h i c ht h eg e n e r a t i o nm e t h o do ft e s ts u i t ea n dt e s t i n gm e t h o do fr o u t i n gp r o t o c o l sa r em a i n l yd i s c u s s e d ( 3 ) m a k er e s e a r c ho ni n t e r o p e r a b i l i t yt e s t i n go fr o u t i n gp r o t o c o l sa n dp r e s e n tam e t h o do f i n t e r o p e r a b i l i t yt e s t i n go f r o u t i n gp r o t o c o l sb a s e do np a s s i v et e s t i n g ( 钔m a k er e s e a r c ho ng e n e r a lp r o t o c o lt e s t i n ge n v i r o n m e n tb a s e do nt e l ，e x p a t i a t eo nt h ef e a s i b i l i t yo fs u c hat e s t i n ge n v i r o n m e n ta n dd e s c r i b et h eg o a la n df u n c t i o no ft h et e s t i n ge n v i r o n m e n t ( 5 ) d e s i g na n di m p l e m e n tt h et e s t i n gs y s t e mo f r o u t i n gp r o t o c 0 1 ( 6 ) a p p l yt h es y s t e mi np r a c t i c a lp r o t o c o lt e s t i n g k e yw o r d s ：r o u t i n gp r o t o c o l ，t e s t i n gs y s t e m ，p r o t o c o lt e s t i n g ，t e s tm e t h o d ，t c中f i j 科学技术大学顺i 。学位论史第一市绪论第一章绪论1 1 协议工程与协议测试协议工程是由p i a t k o w s k i 于1 9 8 1 年提m 的，它借鉴了软件工程中的一些思想，经过几十年的发展，尽管协议丁程研究中遇到了许多困难，但还是引起了人们的极大关注与兴趣，在协议工程研究方面取得了一定的进展，形成了比较完善的研究体系。协议_ ：程的目的是减少协议开发过程中潜在的错误，提高协议的，f ：发效率，促进协议标准化的发展。可以说队议工程是以协议软件为研究对象的软件工程，建立了一奁严格的、数学化、形式化的理论和方法。协议工程的研究范围包括协议说明( p r o t o c o ls p e c i f i c a t i o m 、瞻议综合( p r o t o c o ls y n t h e s i s ) 、协议证实与验证( p r o t o c o lv a l i d a t i o n v e r i f i c a t i o n ) 、协议测试( p r o t o c o lt e s t i n g ) 、协议转换( p r o t o c o lc o n v e r s i o n ) 、性能分析( p e r f o r m a n c ea n a l y s i s ) 以及自动实现( a u t o m a t i ci m p l e m e n t a t i o n ) 。在卧议工程领域咀，协议说明是指对协议标准文本的形式化说明；协议综合是指根据协议标准文本说明设计的过程中保证协议正确性的方法研究；协议证实与验证是指对形式化协议说明的语法语义的j f 确性进行证实和验证：协议测试是指通过实验的方法发现协议实现在功能和性能方面的错误；协议转换是指实现不同协议进程之问的操作，它对于研究小同网络问的互通性有着重要的意义；性能分析是指对设汁完成的协议说明评价其所具有的特性：自动实现是指由机器对形式化协议说明进行编译处理，产，卜协议实现的主体部分。其中，由于协议工程几乎所有内容都和协议说明仃密切的关系，凼此形式化的说明是整个协议工程学研究的基础。协议测试是协议工程学的一个重要内容，早期的协议测试基本l j 是由协议的丌发者自己完成的，2 0 1 岘7 0 年代j t 始国外的一些机构丌始研究山第三方进行的协议测试技术；从2 0 世纪8 0 年代丌始，随着计算机网络发展特别是丌放型芹构网络的迅猛发展，协议测试理沦平f i 技术的研究越米越重要，已经成为国际上计算机网络研究的热点之。 办议测试的：要研究内容包括以f ) l 个方面：( 1 ) 测试方法：在被测系统提供1 i 刖的可访问程度时，组成测试系统的多个测试器相对于被测系统的配置方法；( 2 ) 测试牛成：如何从6 力、议的相关标准中得到协议测试所需要的测试集：( 3 ) 测试集描述：寻找一种合适的语占和图表，以简洁、通用和结构化的方法表示测试集；( 4 ) 测试执行：这是协议测试过程中的关键，通过对测试集f 门执 j ：作j i 坡后的测试判定。1 2 协议测试研究现状hl 诲协议测试已经小仪仪是产m i i t 丌发研剁过程巾个简单的检测支持过程，中困 ：t 学技术人半坝l j 学他论史第章绪论而是发展成为计算机网络技术的个重要分支和协议工程学的一个重要组成部分。对协议测试技术的研究将直接影响到计算机网络技术的进步和世界网络市场的竞争与发展。所以，很多国家都投入了夫量的人力物力从事坍议测试的研究工作。例如：英国的固家物理实验室n p l 、法国国家通信研究中心、德国国家通信研究局g m d 、美罔罔家标准化研究局、荚国新罕布什尔大学互操作研究实验室、清华大学计算机科学与技术系的网络和协议测试实验室和中科院计算所的网络测试实验室等单位都在这个领域投入了大量的研究力量。在国外，像美国硅谷有几家大的协议测试实验窀，比如t o l l yg r o u p 、k e yl a b s 、l a n q u e s t 等，它们专门提供独立公币的第i 方的测试服务，提供权威的测试报告，网络方而的一些著名生产厂家如c i s c o 、3 c o m 、l u c e n t 、n o r t e l 、i n t e l 等都是这螳实验室的客户。要对协议进行测试需要有完整的测试系统，目d 口协议测试系统可分为两类：类是专用的协议测试仪；另一一炎足能为协议测试人员提供测试丌发和测试支持的测试平台。这两类测试系统的域大别就是专用的协议测试仪不具有可扩腱性，而测试平台可以根据测试需求，对其进行扩充。协议测试仪是一种专用的网络测试设备，它能够连接到网络卜，向网上发送数据、捕捉网上数据、分析数掘，协议测试仪般具有网络监测、故障查找、协议解码和流量产生等功能。日前，流行的协议测试仪有两种形式，一种是带有自己的硬件设备，如a g i l e n t 公司的a g i l e n te t h e m e ta d v i s o r ，f l u k en e t w o r k s 公司的o p t i v i e w 系列网络协议分析产品。这种硬件协议测试仪的优点是全面提供了各种网络接口，实时性更强，分析处理速度快，但价格昂贵，普通用户难以接受。另种是纯软件的网络协议分析仪，如a g i l e n t 公司的j 1 9 5 5 a a d v i s o rs we d i t i o n 和f l u k e 公司的基本型协议分析仪( p i ) 和增强型协议分析仪( p l p ) 。这种协议测试仪的优点是可以直接从网卡上捕获数掘进行解码分析，而不依赖特定的硬件设备，因此通用性强，可以安装在接入局域网的任何机器上，并且价格也相对便宜。现在，对测试平台的进行研究的有：中科院计算所从1 9 9 9 年丌始与n o k i a 公司合作设计实现的v 6 p t s ，清华大学删络实验室在设汁的协议集成测试系统p i t s ( p r o t o c o li n t e g r a t e dt e s ts y s t e m ) 等。v 6 p t s 采j f l l 向行设计的测试套描述语苦t s s s ；九：输出函数，s i 0 。在这个模型中，s 。s ，r i ，一0 分别表示初始状态，重启输入和空输出，而且6 和九被定义成部分函数。当状态机处于状态s 时，接收到一个属于输入集合的输入激励a ，则状念机前己进入下一个状态，表示为6 ( s ，a ) ，同时产生一个输出，表示为u s ，a ) 。基于f s m 的测试序列生成方法，主要有四种，( 1 ) t 方法：( 2 ) w 方法；( 3 ) d 方法：( 4 ) u i o 方法。t 方法t 方法是最简单的一种基于有限状态机的测试序列生成方法，它通过遍历状态机中每一个状态转移生成相应的测试序列。t 方法生成的测试序列的优点是长度短、可以用于所有的有限状态机。缺点是没有检测到达的状念，错误检测能力很低。w 方法w 方法包括了两个输入序列集w - s e t 和p s e t 。w - s e t 是f s m 最小的特征集，它使得每对状态能够相互区分，即对不同的状态应用w - s e t 观察到的输出应是能够区分的。p s e t 包括了所有部分路狰，由一个测试树构成，它的根结点是初始状态，而每个变迁只出现一次。这种方法的优点是它可以用于描述非完备的有限状态机，但对每个状态的测试都需要使用r e s e t 功能。d 方法可区分序列法，简称d 方法。该方法的目的是得到个区分序列。一个输入序列i d = i ，i 2 , l ，i 。，如果将它分别作用于有限状态机的每一个状态，从这些状态丌始的输出均不相同，则称i d 为该有限状态机的区分序列。区分序列获得后，测试步骤分两个阶段：( 1 ) 从初始状念出发，寻求从初始状态到各状态的最短路径；( 2 ) 从某个状态丌始，检测其迁移的输出是否正确，应用区分序列，检测迁移后达到的状态是甭i l 二确。u i o 方法u i o 是唯一输入输出序列( u n i q u el n p u t o u p u ts e q u e n c e ) 的简写。u i o 方法用不同的输入输出序列米区分有限状态机的不同状态。一个状态的u i o 序列指的是这样一个输入输出序列：它起始丁该状态，当输入序列中规定的输入时，产生序列中舰定的输出，而再没有别的状态鼹示同样的输入输出行为。u i o 的作用与区分序列十h 同，f f l 构成1 i 同，d 力法l j m 分所有状态必须用矧一个输入序列，是通过输出信号的不同来区分当前状态的，而u i o 方法是通过输入输出的共同作用来区分当前状态的，因为测试序列中每个状态的u i o 是唯一的。区分序列中国科学技术人学颇| ：学化论文第州章路由协议的一致性测试必是u i o 序列，但反之不然。计算u i o 序列的基本方法如下：( 1 ) 建立所有状念的出边与输入输出集的关系：( 2 ) 对每个状态求出所有长度为1 的输入输出序列；( 3 ) 检查它们足甭唯一，若是，则找到了u i o 序列；( 4 ) 如果不是，对于未找到u i o 序列的状态，检查长度为2 的序列；( 5 ) 依据长度为k 的输入输出序列，构造长度为k + l 的输入输出序列，检查它们是否唯一，直到每个状态都找到u i o 序列或k 2 n 2 。，下面以图4 一l 所示的有限状态机为例，列出使用u i o 方法生成测试序列的步骤：图4 - 1 有限状态机示例1 为每个状态确定一个不同的输入输出序列：u l o o ) = a 1 ，u i o ( 2 ) = a o ，a 1 ，u i o ( 3 ) = b 1 ，a 1 ) 是满足上述要求的三个输入输出序列。2 测试有限状态机巾的每个状态。输入输出序列分别为： 4 盟，r e s e t )p 测试状态1 + “1 ，型q ! 型! ，r e s e t )+ 测试状态2 * b 1 ，b ! ! 型! ，r e s e t 产测试状态3 13 测试有限状态机巾的每个状态转移。输入输出序列分别为： 垦丛，a o ，a 1 ，r e s e t p 测试状态转移( 1 ，2 ) + 鱼丛，b l ，a 1 ，r e s e t )卓测试状态转移( 1 ，3 ) a 1 ，a _ _ 0 0 ，a 1 ，r e s e t 幸测试状念转移( 2 ，1 ) + “1 ，旦丛，b 1 ，a t ，r e s e t p 测试状念转移( 2 ，3 ) ( b 1 ，鱼丛，a 1 ，r e s e t p 测试状态转移( 3 ，1 ) + b 1 ，a o ，a o ，a 1 ，r e s e t p 测试状态转移( 3 ，2 ) + 从以上四种测试序列牛成方法来看，测试的能力直接影响到测试序列的长中困科学技术大学硕 ：学位论文第叫章路由协议的一致性测试度，尽管w 方法能够发现较为复杂的错误，但是因为它的测试序列长度在实际的复杂系统中是很难使用的，同时在现实中，已经去掉了一些错误，因而有些强大的测试功能“多余”的。d 方法的主要优点是能够发现故障点的位置，但是由于d 序列不能保证一定存在，而且比较难以进行d 方法的优化，所以它的测试序列往往过长。相对而占，u o 方法生成的测试序列比较短，错误检铡能力比较强，一致性测试本身并不关心错误的原因和位置，而且几乎可以适用于所有的有限状念机，所以u i o 方法一直是基于有限状态机测试序列生成的最常用的方法。4 2 2 2 互连行为测试部分的测试序列的生成在路由协议的一致性测试中，我们使用u i o 方法来生成互连行为测试部分的测试序列。虽然u i o 方法可以适用于很多类型的有限状态机，但对于协议规范中给出的原始的有限状念机，它通常不适用，主要原因是：( 1 ) 原始状态机中的某些事件是内部事件，这些事件不可控；( 2 ) 协议中的某些定时器，会引发一些事件，而原始状态机并没有体现这样的事件。因此，要使用u i o 方法产生测试序列，先要对原始的状念机进行变换。本节将以o s p f 邻居状态机的测试序列生成为例，对这一部分的测试序列的生成进行详细的说明。1 邻居状态机的事件变换( 1 ) 内部事件的变换通过对接收h e l l o 包过程的分析，可以知道h e l l o 包的接收与邻居状态机事件的产生是紧密相关的，下面，我们就以对邻居状态机这一部分事件的变换为例来说明如何对原始状态机的内部事件进行变换。路由器接收到一个h e l l o 包后，不是仅仅产生h e l l o r e c e i v e 事件，实际所产生的事件是和h e l l o 包的内容相关的，有四种不同的情况：( a ) 接收到一个正确的、没有携带路由器信息的h e l l o 包，将会向邻居状念机发送事件h e l l o r e c e i v e d和1 一w a y r e c e i v e d ；( b ) 接收到一个正确的、携带路由器信息的h e l l o 包，将会向邻居状态机发送事件h e l l o r e c e i v e d 和2 - w a y r e c e i v e d ：( c ) 接收到一个f 确的、包含路由器信息并声明自己是链路b d r 的h e l l o 包，将会向邻居状态机发送事件h e l l o r e c e i v e d 和2 - w a y r e c e i v e d ，并向接口状态机发送事件b a c k u p s e e n ：( d )接收到一个正确的、包含路由器信息并声明链路d r 或b d r 发生变化的h e l l o包，将会向邻居状态机发送事件h e l l o r e c e i v e d 和2 - w a y r e c e i v e d ，并向接口状态机发送班件n e i g h b o r c h a n g e 。根据以上分析，- 叮以肘邻膳状态机巾的班件作如下变换：( a ) 邻居状态机中的h e l l o r e c e i v e d 事件可以变换为接收到一个f 确的、没有携带路由器信息的h e l l o 包事件：中同科学技术人学硕卜学化论义第叫章路由协议的一投性测试( b ) 邻居状念机中的1 - w a y r e c e i v e d 事件也可以变换为接收到一个正确的、没有携带路由器信息的h e l l o 包事件；( c ) 邻居状态机中的2 - w a y r e c e i v e d 事件可以变换为接收到一个正确的、携带路由器信息且没有改变链路d r 或b d r 的h e l l o 包事件：( d ) 邻居状态机中的a d j o k 事件可以变换为接收到一个j 下确的、携带路由器信息且改变了链路d r 或b d r 的h e l l o 包事件。我们可以按照卜- 述方式对邻居状态机其它部分内部事件进行变换。( 2 ) 定时器产生的事件的变换出于接口状态机会启动发送h e l l o 包的定时器，每隔h e l l o i n t e r v a 发送一个h e l l o ，因此需要在邻居状态机的每个状态卜增加一个发送h e l l o 包的非定时自发事件。此外，邻居状态机接收到h e l l o 包后，会启动路出器死亡定时器等待下一个h e l l o 包的到来，若路由器死亡定时器超时，则会向邻居状态机发送i n a c t i v i t y t i m e r 事件，因此，可以将l n a c t i v i t y t i m e r 事件变换为在r o u t e r d e a d l n l e r v a l 时间删隔内没有接收到一个正确的h e l l o 包事件。2 邻居状态机的变换变换后的邻居状态机如图4 2 所示。- 小0 1 1 0 1s 1l f l j 删“一驯所有状毒接收删n h 、l l 、州。u o l f ，一妄刚j o l 。玉 ) 删舶2 。“0 4 事纠 转# 划”状卷一-一所 】s 3 的状忐接收铒h e l l 0 3 d d i 纠l u 弘| h e l l o l 事什衍转档到s 机每m 【| ”s ；。五nd d l d d 2, q l e l l 0 3( r m t l d d 2dd4dd3,qsr所青人i 二s 5 的状态挂收划d d 5 、l s r 2 事竹后转 鲫s s 状卷所自 js ，的机志摧收刊h c l l o l 事n 后知小邻接盖采 监“0 拈社纠s 4 状忐一一s 8 -”“，玉，- ，嚣黜：。图4 2 ：变换后的邻居状态机变换后的状态机中的输入输m 事件的含义如下：i u p ：打丌路由器上栩应接l 二 的事件。h e l l o l ：接收到正确的、没有携带路山器信息的h e l l o 包，相当于原状态机中的h e l l o r e c e i v e d 事件乖i1 - w a y r e c e i v e d 枣什。h e l l 0 2 ：接收到一个正确的、携带路由器信息且没有改变链路d r 或b d r 的h e l l o 包，相当于原状态机中的h e l l o r e c e i v e d 事件和2 - w a y r e c e i v e d 事件；h e l l 0 3 ：接收到一个正确的、包含路出器信息并声明链路d r 或b d r 发生变中园科学技术人学颂l 学位论文第叫章路由协议的一致性测试化的h e l l o 包。h e l l 0 4 ：r o u t e r d e a d i n t e r v a l 时间内没有接收到邻居发送的h e l l o 包。d d l ：收到正确的、携带初始化信息的数据库描述包。d d 2 ：收到萨确的、携带主从信息的数据库描述包。d d 3 ：收到正确的、携带链路状态信息的数据库描述包。d d 4 ：收到正确的、携带结束信息的数据库描述包。d d 5 ：收到序号错误或类型不匹配的数据库描述包。l s r l ：收到正确的链路状态请求包。l s r 2 ：收到请求链路状态错误的或请求链路状态不存在的链路状态请求包。3 邻居状态机测试序列的生成对邻居状态机的输入输出事件变换后，就可以使用u i o 方法来生成测试序列了。另外，有一点需要注意：在图4 2 所示的邻居状态机中，状态s 1 和状态s 2的输出事件时完全一致的，这两个状态没有不同的输入输出序列。值得庆幸的是s l 到s 2 的状念转移，在接口状态机中产生i n t e r f a c e u p 事件时也会进行测试，并且除去这两个状态之间的转移后这两个状态是完全等价的。因此，在使用u i o方法生成邻居状态机的测试序列时，抛弃了状态s 2 的测试。下面给出邻居状态机的u i o 序列：( 1 ) 为每个状态确定不同的输入输出序列u i o ( s 1 ) = - h e l l o l u x o ( s 3 ) = 一 i e l l 0 2 3 ，h e l l 0 3 d d l )u i o ( s 4 ) = 一h e l l 0 2 ，d d 5 一)u i o ( s 5 ) = 一h e l l 0 3 ，d d l d d 2 u i o ( s 6 ) = 一h e l l 0 3 ，( r x m t ) d d )u i o ( s 7 ) = 一h e l l 0 3 ，( r x m t ) l s r u i o ( s s ) = 一h e l l 0 3 ，d d 5 d d 2 ( 2 ) 测试邻居状态机【1 1 的每个状念的输入输f 序列为： h e l l o l ，r e s e t 产测试状态s 1 + h e l l o l ，一h e l l o l ，一1 1 1 0 2 3 ，h e l l 0 3 d d l ，r e s e t )p 测试状态s 3 + - h e l l ol ，一h e l l o1 ，一h e l l 0 2 3 ，h e l l 0 2 一，一h e l l 0 2 ，d d 5 - ，r e s e t )* 湖j j 试状态s 4 + f 一h e l l o l ，一h e l l o l ，h e l l 0 2 3 ，h e l l 0 3 d d l ，一h e l l 0 3 ，d d l d d 2 ，r e s e t )卓测试状态s 5 + - h e l l o l ，一h e l l o l ，h e l l 0 2 3 ，h e l l 0 3 d d l ，一h e l l 0 3 ，d d 2 - ，一h e l l 0 3 ，中罔科学技术人学顾i ：学位论文第叫章路由协议的一致悻测试( r x m t ) d d ，r e s e t )p 测试状态s 6 + 一h e l l o l ，一h e l l o l ，- h e l l 0 2 - 3 ，h e l l 0 3 d d i ，h e l l 0 3 ，d d 2 一，一h e l l 0 3 ，d d 3 l s r i ，一h e l l 0 3 ，( r x m t ) l s r ，r e s e t 幸测试状态s 7 + - h e l l o l ，一h e l l o l ，- h e l l 0 2 - 3 ，h e l l 0 3 d d i ，一h e l t 0 3 ，d d 2 o ，一h e l l 0 3 ，d d 4 一- h e l l 0 3 ，d d 5 d d 2 ，r e s e t 宰测试状态s 8 + ( 3 ) 测试邻居状念机中的每个状念转移的输入输山序列为： 一h e l l o l ，h e l l o l 一，- i l e l l 0 2 3 ，h e l l 0 3 d d l ，r e s e t + 测试状态转移( s 1 ，s 3 ) + 4 2 3 路由信息交换测试和路由表计算测试由于路由信息的产生和路由表的计算一般都是由于网络的拓扑结构发生变化而引起的，因而这两部分的测试集的产生所涉及的关键问题就是如何根据不同的测试同的来设计合适的测试网络。例如，o s p f v 3 协议规定：当路由器收到i n l e r a r e a r o u t e r - l s a 后，若经过路由计算后，发现到达转发地址的路由发生了变化，需要重新计算a se x t e r n a l路由。如何实现这一测试昵? 根据协议的描述，我们可以知道耍实现测试必须满足以下条件：( 1 ) 使待测路山器产牛条a s e x t e r n a l 路由，并且该路由是通过转发地址获得；( 2 ) 当到转发地址的路由发生变化时，待测路由器能够产生新的a s e x t e r n a l路由替代原路 _ l ( 为了便于观察测试结果) 。分析了测试所需的条件后，可以构造如f 的测试组劂冈：圈4 3 ：o s p f v 3 测试逻辑组叫幽幽中，n e t w o r k1 0 为啊的网络，v t r l 和v t r 2 可以使条什1 得剑满足，t r l l 使条什2得以满足。l 体测试过程如f ：中固科学技术大学硕l ：学位论文第叫章路由协议的一致性测试1 在r u t 上重新启动o s p f 进程。2 r u t 和t r i l 成为n e t w o r k0 的d r 和b d r ，t r l l 和r u t 建立邻接关系。3 r u t 和t r 2 l 成为n e t w o r kl 的d r 和b d r ，t r 2 1 和r u t 建立邻接关系。4 t r l l 通过n e t w o r k0 向r u t 发送l s u p d a t e 包。包中包含t r l l 产生的r o u t e r - l s a 、l i n k l s a 、a s e x t e r n a l l s a ( e b i t 为l ，f b i t 为0 ，m e t r i c为2 ) 。5 t r 2 l 通过n e t w o r kl 向r u t 发送l su p d a t e 包，包中包含t r 2 1 产生的r o u t e r l s a 、l i n k l s a 、为v t r l 产生的i n t e r - a r e a r o u t e r - l s a 、为n e t w o r k2 产生i n t e r - a r e a p r e f i x l s a ( m e t r i c 设置为1 ) 和r 1 产生的a s e x t e r n a l l s a ( e b i t 为1 ，f b i t 为1 ，f o r w a r d i n ga d d r e s s 为v t r 2 ，m e t r i c 为2 ) 。6 观察r u t 的路由表。7 m i n l s i n t e r v a l 秒后，t r 2 l 通过n e t w o r ki f 旬r u t 发送l su p d a t e 包。包中包含t r 2 1 为n e t w o r k2 产生的i n t e r - a r e a - p r e f i x l s a ( m e t r i c 设置为6 ) 。8 观察r u t 的路山表。4 3 测试集的结构图4 - 4 中给出了测试集的结构。每个测试集( t e s ts u i t e ) 都是针对某一被测协议的，它由多个测试组构成；每个测试组通常是针对某一类测试目的，测试组由多个测试例组成；每个测试例针对某一个特定的测试目的，测试例由测试步和测试事件构成：测试步通常是个测试事件序列；测试事件是构成测试例的基本单位，它描述的是测试者的每一个具体行为( 收发数据包，启动定时器等) 。铡试啦删让组测试虮j ；测试细测试自l测试组删试制测试例) i i i 盘例删试侧测试制洲试班测试事什图4 4 测试集的结构4 4 测试方法啦i j试l 竹侧，fil件鼎步f测im女r赢甙i吐：测蝌测i ，试i什测事渺_ 二【测抽中因科学技术人学碗i 学位论文第u u 章路由协泌的一致性测试对于协议的一致性测试，1 s o9 6 4 6 2 中给出了一些的测试方法，我们在2 2 3节中进行了详细的介绍。在实际测试中，通常使用分稚测试法或远程测试法。由于路由协议不需要位上层的协议提供服务，因此路由协议的测试不需要u t 的存在，对路由协议的进行测试通常采用远程测试法。考虑到路出协议具有分布式系统的特点，凶此对路山协议的测试通常都需要多个测试体进行测试，这样势必会造成组网的困难，为了便于构造测试所需的网络拓扑结构，我 l l j r , r 以考虑利- 虚拟测试法：它实质一卜是用一个物理的网络适配器来虚拟出多个网络适配器，可将每个虚拟的适配器视为一个测试体，在每个虚拟的网络器上可以配置多个i p 地址，这样理论上可以组成任意的网络拓扑结构。这些虚拟测试体可以通过一个协调模块来组织以共同完成对待测体的测试。用虚拟出来的测试体组建的测试环境来进行一致性测试，和具有相同拓扑结构的物理环境来进行测试的效果相同，并且可以利用较少的设备完成测试任务。协议测试采用的模型通常是黑盒测试。若对路山协议测试也采用这种模型，则只能通过观察路山模块的转发行为来推测路由表的正确性，进而反推路由信息收集和处理的正确性，这样必然会使得测试集的设计变碍复杂，测试能力受到较大限制，测试的完备性受到很大影响。因此路由协议的一致性测试完全采用黑盒测试的方法并不合适，我们可以对此稍加改进：将路由表从黑盒中“取出”，使路由表在测试过程中可见，而使路由阶议的其余部分不可见。这样就可以很容易地获知路由信息的处理是否j 下确。这种测试方式在实现上也是可行的。基于以上几点考虑，我们采用如图4 5 所示的模型。它能够较好的满足路由协议一致性测试的需要。il tv i r a m la d a p t e rv i r l u z da d a p l c rc o o r d i n a t o r币l 址部分“r 虬部仆路m t i 息的继：收姓j q l 和发i 苎t lvl+t11峰2“vlt+12pcop c op c op c o路嶙驯i 装端忐n n1 ! ：j ：l1 卜一( n - 1 ) s e r v i c ep r o v i d e r图4 5 路由协议的测试结构本章小结本章讨论了路出协议的一致，陀测试，包括路山协议一致性测试所包含的内容、抽象测试测试集的生成以及路山协议洲试方法的设计。其中，重点介绍了路中周科学技术大学坝l ：学位论史第四章路由协议的一致性测试由协议互连行为部分抽象测试集的生成( 以o s p f 的邻居状态机部分测试集的生成为例) 。另外，针对路由协议的特点，结合现有的测试方法，设计了一种分布式虚拟测试方法，它能较好的满足路由协议一致性测试的需求。中闺科学技术人学颁i + 学化论立第五章路由协议的互操作性测试第五章路由协议的互操作性测试憾u i ：0k _ t u 础tj ，m 1图5 - i ：互操作性测试框架5 1 2 互操作性测试的形式化模型通常，每个协议实体的行为可以使用一个有限状态机( 4 2 21 给出了有限状态机的形式化定义) 来描述，而协议的互操作性测试涉及到两个待测实体间的通信，我们可以用复合有限状态机米描述它们的全局行为。复合有限状态机定义如下：定义2 ：复合有限状态机：f s ma 和f s mb 的复合有限状态机m 是一个五元组( s i l ，s 1 10 ，i i i ，0 i i ，t i i ) ，其巾s i i = s 1 10 ，s i il ，s i i n - 1 ) 是m 的状态集，s 】i i = ( s ( a ) 。，s ( b ) 。) 是f s ma 的状态s ( a ) 和f s mb 的状态s ( b ) 。组成的全局状态：s i f 0 = ( s ( a ) 。，s ( b ) 。) s 是初始状态：i i i i n = v i ii ，v i l 2 ，v i i m 是输入符号集，vi i i l ( a ) u i ( b ) 一l ( a ) n o ( b ) 一o ( a ) n i ( b ) 是外部输入符号：0 i i = u i il ，u l i2 ，u 1 1k ) 是输符号集，u 1 1 i = 是个输出符号序列，中国科学技术人学倾i 学位论义第五章路由协议的正操作性测试o o ( a ) u 0 ( b ) ；t i i 一 t i il ，t i i2 ，t l j 是转换集，其中每个转换t 1 1 i 可以表示为fs i i ，s 1 i ，v u j ，s 1 1 、s 1 1 s 1 1 ，v i l i ，u 0 1 i 。在复合有限状念机中，a 和b 之间交互的消息称为内部消息，而与外部环境之间交换的消息称为外部消息。定义3 ：本地( 局部) 转换：在复合有限状态机中不包含内部消息的转化称为局部转换或本地转化。比如t i i i - s i i ，s l i ，v u ，若u 不包含内部消息，则t 1 1 i 是本地( 局部) 转换。定义4 ：互操作转化：在复合有限状态机q 1 ，包含内部消息的转化称为互操作转换。定义5 ：互操作测试序列：瓦操作测试序列t s 是复合有限状态机中的一个连续的状态转换序列 ，其中t t i i ，t 。的头状态为初始状态s 1 1 0 。有限状态机可用有向图g = ( e ，v ) 表示，其中边集e 中的每条有向边e 代表有限状态机的一个转换，顶点集v 中的每一个顶v 代表有限状态机的一个状态。互操作测试序列可以表示为一个有序边集( 有向图中的一条路径) 。5 1 3 互操作性测试序列的生成对于一个复合有限状态机的有向转换图g ，可以通过如下步骤生成互操作测试序列3 6 1 ：( 1 ) 找出有向图中的所有强连通子图( s c c ) ；( 2 ) 在原图中将每个强连通子图用一个顶符代，构造出有向无环图( d a g ) g 1 ：( 3 ) 在g 1 中找山所有从源节点到汇节点( 只有入边没有出边的节点) 的无环路径；( 4 ) 对每个s c c 找出所有的无环路径和简单回路：( 5 ) 用s c c 中的无环路径替代3 的无环路径中的相应的顶，生成陶g 中的无环路径；( 6 ) 将5 的所有无环路径和4 的所有简单网路复合，生成最终的路径集，该路径集代表了复合有限状态机的互操作性测试集。5 2 路由协议的互操作性测试5 2 1 测试1 i 容协议的互操作性测试足在m 泌的一致性测试基础上完成的，它只需要关注协议实体州的交互灶夼v m 议舰范。敏。就路山胁 义而古，它的互操作性测试则主要包括以下两个方：状念机测试和路信息交换测试。5 2 2 测试方法路由协议有别于+ 般的通信协议，它不需要为上层的协议提供接口，因此在中田科学技术人学颇i ：学位论义招五章路由悱议的互操作性测试路由协议的互操作性测试巾不需要u t 的存在。图5 - 2 描述了一般通信协议的互操作性测试过程，t e s t e ra 通过1 u ta 提供的接口向t e s t e rb 发出连接请求，从而触发了i u ta 和i u tb 之间的互操作，t e s t e rb 预期会接收到连接请求，若未收到，则测试失败( 发现错误) ，若收到，则检查待测系统的状态是否与预期的一致。出于路由协议没有为上层协议提供访问的接口，外部环境控制被测系统的唯一途径就是启动和停止路出守护进程，因而不能按照通常的协