（计算机软件与理论专业论文）isis路由协议一致性测试的研究.pdf

内蒙古大学硕士学位论文 is ls 路由协议一致性测试的研究 摘要 随着计算机网络规模的不断扩大，大型互联网络的迅猛发展，路由技术在 网络技术中已逐渐成为关键部分，路由器也随之成为最重要的网络设备。人们 已经不满足于仅在本地网络上共享信息，而希望最大限度的利用全球各个地区、 各种类型的网络资源，用户的需求推动着路由技术的发展和路由器的普及，高 效稳定的路由协议成为保障网络性能的重要因素。协议测试是保证网络设备之 间互联的重要手段。 i s i s 路由协议是目前内部网关协议的主流协议之一，它可以同时运行在 o s i 和i p 两种环境中，在当今的网络中有着广泛的应用。i s i s 采用分层的网络 结构，稳定性好、收敛快、可扩展性强，而且在同等规模的网络下需要的资源 比其它内部网关协议更少。 本文在对i s i s 路由协议分析的基础上，运用形式化与非形式化相结合的方 法，对i s i s 进行了协议一致性测试。对邻接关系状态机进行了e - l o t o s 描述， 并利用自动生成工具p a t s a g 自动生成了t t c n 一3 抽象测试例，给出了i s i s ， 协议的所有可执行测试例。最后在l i n u x 下对路由软件q u a g g a - 0 9 9 7 中实现的 i s i s 协议进行了一致性测试，并对测试结果进行了分析。 关键词：协议一致性测试，i s i s ，测试例，q u a g g a - 0 9 9 7 ，t t c n - 3 i s i s 路由协议一致性测试的研究 r e s e a r c ho nt h ec o n f o r m a n c et e s t i n go ft h e i s - i sr o u t i n gp r o t o c o l a b s t r a c t r o u t i n gt e c h n o l o g yh a sg r a d u a l l yb e e nt h e e s s e n t i a l p a r to f n e t w o r k i n g t e c h n o l o g ya st h ec o m p u t e rn e t w o r ks c a l ec o n t i n u o u s l ye x p a n da n dt h ei n t e r n e t r a p i d l yb e e nd e v e l o p e d r o u t e ra l s ob e c o m e st h em o s ti m p o r t a n tn e t w o r ke q u i p m e n t p e o p l ea r en ol o n g e rs a t i s f i e dw i t ho n l yl o c a ln e t w o r kt os h a r ei n f o r m a t i o n ，a n dh o p e t h a tt h e yc a nm a x i m i z et h en e t w o r kr e s o u r c e su s eo fv a r i o u sp a r t sa n dv a r i o u st y p e s o ft h ew o r l d t h en e e d so fu s e r sp r o m o t et h ed e v e l o p m e n to ft h er o u t i n gt e c h n o l o g y a n dp o p u l a r i t yo fr o u t e r s e f f i c i e n ta n ds t a b l es e c u r i t yn e t w o r kr o u t i n gp r o t o c o l s b e c o m ea ni m p o r t a n tf a c t o ri n p e r f o r m a n c e c o n f o r m a n c et e s t i n g o fp r o t o c o l i m p l e m e n t a t i o ni s a ni m p o r t a n tm e a n st oe n s u r et h ei n t e r c o n n e c t i o na m o n gt h e i n t e m e tp r o d u c t s n o wi s i sr o u t i n gp r o t o c o li so n eo ft h em a i ni g p s ( i n t e r n a lg a t e w a y p r o t o c 0 1 ) i tc a nr u ni nb o t ho s ia n di pe n v i r o n m e n t i nt o d a y sn e t w o r k , i th a sa w i d er a n g eo fa p p l i c a t i o n s i s - i sh a sal a y e r e dn e t w o r ks t r u c t u r e ，g o o ds t a b i l i t y ，f a s t c o n v e r g e n c e ，s t r o n ga b i l i t yo fe x p a n d i n g ，a n di nt h es a m en e t w o r ks c a l ei tn e e d sl e s s r e s o u r c e st h a no t h e ri g p s b a s e do nt h ea n a l y z i n go fl s i sp r o t o c o l ，t h i st h e s i sa p p l i e sc o n f o r m a n c et e s t 塑鍪直奎堂婴主堂篁堡苎 o ni s i sp r o t o c o lb yu s i n gt h ef o r m a la n di n f o r m a lc o m b i n e dm e t h o d i td e s c r i b e s a d ja c e n c ys t a t em a c h i n ei ne l o t o s ，a u t o m a t i c a l l yg e n e r a t e st h ea b s t r a c tt e s tc a s e i nt t c n - 3f o r m a tb yu s i n gt h et o o lo fp a t s a g ，g i v e sa l le x e c u t a b l et e s tc a s e s ， f i n a l l ya p p l i e sc o n f o r m a n c et e s t o nq u a g g a - o 9 9 7 si s i s p r o t o c o l i nl i n u x e n v i r o n m e n ta n da n a l y z e st h et e s tr e s u l t k e y w o r d s ：p r o t o c o lc o n f o r m a n c et e s t ，i s i s ，t e s tc a s e ，t t c n 3 ，q u a g g a - 0 9 9 7 i i i 内蒙古大学硕士学位论文 图表索引 图2 1 路由协议的测试模式4 图2 2 静态方式和动态方式5 图2 3 一致性测试的工作流程。6 图2 4 一致性测试的基本模型7 图3 1e l o t o s 描述层次图：9 图3 2 核心语言和各种表示格式的用户视图一1 0 图3 - 3t t c n 3 测试套层次图1 1 图4 1i s i s 路由协议拓扑结构图1 2 表4 1i s i s 的报文格式13 图4 2 子网独立功能分解1 5 图5 1i s i s 广播网络邻接关系状态机18 图5 2i s i s 广播网络邻接关系状态机和输入事件1 8 图5 3 生成的状态定义2 4 图5 4 生成的输入、输出事件定义2 5 图5 5i s i s 协议测试套中的一个抽象测试例2 5 表5 1i s i s 协议测试套中的一个可执行测试例2 7 表5 2i s i s 协议测试套中的一个手工找出的可执行测试例2 8 图6 1 远程测试法3 0 表6 1i s i s 协议测试套中的一个未通过的可执行测试例3 1 图6 2由i u t 发送的l 1h e l l o 报文3 2 图6 3由t 发送的l 2h e l l o 报文3 2 图6 4由测试机端口1 发送的l 1h e l l o 报文3 3 图6 5 另一个由i u t 发送的l 1h e l l o 报文3 4 图6 6 t 上的i s i s 邻接关系数据库3 4 图6 7 由i u t 发送的l 1c s n p 报文3 4 图6 8 t 上的i s i sl s p 数据库3 5 图6 9由测试机在端口1 发送的l 1p s n p 报文3 5 v i i i s i s 路由协议一致性测试的研究 图6 1 0 由i u t 发送的l 1l s p 报文3 5 图6 1 1i s i sh e l l o 报文的j a v a 代码。3 6 图6 12i s i sc s n p 报文的j a v a 代码。3 7 v i 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。除了 文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人己经发表或撰写过的研 一，_ 究成果，也不包含为获得内蒙古大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。 学位论文作者签名：复量堡1 指导教师签名： 日期： 彩彬g , s - 日期： 在学期间研究成果使用说明书 学位论文作者完全了解内蒙古大学有关保留和使用学位论文的规定，即：内蒙古大学研 究生在校攻读学位期间论文工作的知识产权单位属内蒙古大学。学校有权保留并向国家有关 部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文 的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。作者今 后使用涉及在学期间主要研究内容或研究成果，须征得内蒙古大学就读期间导师的同意；若 用于发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表。 一 学位论文作者签名：雩翌丝堡指导教师签名： 日期：刎踢、厶f f日 期： 盛 内蒙古大学硕士学位论文 1 1 研究背景 第一章绪论 现在网络正朝着数字化、宽带化、智能化、综合化的方向发展，网络提供的服务从传统 的通信服务向信息服务转变。软件规模急剧增大，结构也越来越复杂。同时，网络系统的复 杂性在协议方面体现出空间分布性、并发性、异步性、不稳定性和多样性，因此高效稳定的 路由协议成为保障网络性能的重要因素。然而，由于协议本身是用自然语言描述的，实现者 在实现这些协议的时候会由于对协议文本的不同理解导致不同的协议实现甚至是错误的协议 实现。为了验证协议实现是否与协议标准相符合，必须对协议实现进行测试。 与已被人们熟知的r i p 、b g p 、o s p f 这些路由协议一样，i s i s 路由协议是目前内部网 关协议的主流协议之一，它采用分层的网络结构，稳定性好、收敛快、可扩展性强，而且在 同等规模的网络下需要的资源比其它内部网关协议更少。近年来由于主流的网络设备提供商， 如思科、华为、中兴等厂家均已研制出了支持i s i s 路由协议的网络产品，因此使得i s - i s 路 由协议得到了比较大范围的应用，从而使其在现今网络中有着广泛的部署。 目前，国内外对b g p 、o s p f 路由协议所作的测试已经日趋成熟和完善。在国内，以清 华大学测试实验室开发的集成测试系统p i t s 为代表，在其上对b g p 、o s p f 等协议进行了测 试，但是，p i t s 并未涉及对i s i s 路由协议的测试；国内其它期刊所发表的有关协议测试的 论文中，i s i s 路由协议一致性测试方面的论文也很少，这使得有关i s i s 路由协议测试方面 的资料和成果非常匮乏，因此，关于i s i s 路由协议测试方面有待更多的研究。在国外，美国 新罕布什尔大学的互操作实验室i o l ( i n t e ro p e r a b i l i t yl a b s ) 对i s i s 路由协议的测试也做了 研究，它所公布的成果丰j 它所找出的测试例提供在一个设备上孤立问题的一种方法，但并 不能决定一个产品是否 1 ji s i s 的协议说明【1 1 。通过阅读有关i s i s 协议测试的论文和相关 资料，可以看出目前各厂家关于i s i s 路由协议的实现有着各种缺陷，所以对i s i s 路由协议 的测试是有必要的。 1 2 研究目标和主要工作 目前，国际标准中与i s i s 路由协议相关的重要标准有两个，o p i s o1 0 5 8 9 和r y e11 9 5 。其 q j i s o1 0 5 8 9 是最初的i s i s 路由协议的标准，它指, h q i s i s 路由协议是如何运行在o s i 网络七层 i s i s 路由协议一致性 瘐9 试的研冗 架构中的。然而，现今的网络大都是运行在t c p i p 架构中的，所以r f c1 1 9 5 提出了集成i s i s 路由协议的概念，它通过对l s i s 路由协议的扩展，使i s - i s 路由协议能够同时运行在o s i 和 t c p i p 环境下。我们的研究目标是在t c p i p 环境下对i s i s 路由协议进行一致性测试，所以相 关i s i s 路由协议的报文格式应符合r f cl1 9 5 中所述。本文是在研究i s i s 路由协议标准的基础 上，对i s - i s 协议广播网络邻接关系状态机进行e l o t o s 描述，并用软件p a t s a g 对其自动生 成抽象测试例，然后手工找出i s i s 协议其它内容的测试例并分类，最后用所找出的测试例在 l i n u x 下对路由软件q u a g g a - 0 9 9 7 中实现的i s - i s 协议进行一致性测试，并对测试结果进行分 析。 1 3 本文中涉及的标准、开发工具及技术 ( 1 ) e l o t o s 标准【2 】 i s o i e cf d i s15 4 3 7 ：2 0 01 ( e ) i n f o r m a t i o nt e c h n o l o g y _ _ _ 。e n h a n c e m e n t st ol o t o s ( e l o t o s ) ( 2 ) t t c n 3 标准跚4 】【5 】【6 】 e t s ie s2 018 7 3 - 1v 3 3 ( 2 0 0 5 - 0 6 ) m e t h o d sf o r t e s t i n ga n ds p e c i f i c a t i o n ( m t s ) ；t h e t e s t i n ga n dt e s tc o n t r o ln o t a t i o nv e r s i o n 3 ( 3 ) i s i s 路由协议标准7 】【8 】 i s od p10 5 8 9 ，i n t e r m e d i a t es y s t e mt oi n t e r m e d i a t es y s t e mi n t r a - d o m a i nr o u t i n ge x c h a n g e p r o t o c o lf o ru s ei nc o n j u n c t i o nw i mt h ep r o t o c o lf o rp r o v i d i n gt h ec o n n e c t i o n l e s s m o d en e t w o r k s e r v i c e ( i s o8 4 7 3 ) r c a l l o n , u s eo fo s ii s - i sf o rr o u t i n gi nt c p i pa n dd u a le n v i r o n m e n t sr f c119 5 ，19 9 5 ( 4 ) 测试例发包编写语言：j a v a ，j p c a p ( j a v a 在数据链路层发包的接口) ( 5 ) 测试例自动生成工具：p a t s a g ( 内蒙古大学计算机学院开发的根据协议的e l o t o s 描述自动生成测试例的工具) 。 ( 6 ) 收包解析工具：e t h e r e a l ( 用来观测接收到的包的格式和类型并作一定程度解析的 工具) 。 2 内蒙古大学硕士学位论文 2 1 路由协议测试概述 2 1 1 路由协议特点 第二章路由协议一致性测试 认识路由协议的特点是对路由协议开展有效的测试工作的基础。 首先，路由协议的目的是为路由提供所需的信息。路由协议交互的是关于网络拓扑结构 的信息，正确的处理、发送这些信息，形成对于网络拓扑结构的正确反映是路由协议的主要 功能，并不要求数据尽力转发。相反，各个路由协议中对尽量减少数据量的交互、降低交互 频率，避免路由更新时造成突发数据都有所考虑。 其次，路由协议利用下层协议传输路由信息，没有上层协议的存在。路由协议都要使用 下层协议提供的服务，例如b o p 使用t c p 的服务，o s p f 使用i p 的服务，i s i s 使用数据链 路层的服务。不同的服务提供者所提供的接口不同，对于测试工作而言，确定相应的接口是 开展测试工作的前提。 路由协议的另一显著特点是其具有分布式系统的特性。 路由协议会涉及到很多重要的数据库，用于存放相关路由信息，其中路由表是最为基础 的数据库。路由协议有大量的内部处理过程都要用到数据库，所以数据库中存储信息的大小 和正确性直接关系到路由协议的正确性与效率。 路由协议测试中的很小一部分是依据协议状态机从建立连接到断开连接的过程的维 护，而很大一部分是对于达到稳定状态后的行为，对路由协议的测试要充分考虑路由协议的 特点。 2 1 2 路由协议测试内容 针对路由协议的特点，对其进行测试的内容和目标应当包括： ( 1 ) 协议帧结构的测试：主要针对协议数据帧的基本功能。 ( 2 ) 协议状态机测试：测试其所有变迁路径，其中包括对错误帧的处理。 ( 3 ) 路由信息的交换与处理：这是路由协议测试的重要内容，需要测试路由协议在网络 拓扑结构发生变化时，发现、传播这些变化的能力，测试相应的接收者对于这些信息的处理 和转发，测试路由协议对于包括路由表在内的数据库的更新与维护，测试内部处理过程的正 i s l s 路由协议一致性测试的研究 确有效。 ( 4 ) 互操作测试：保证不同的路由协议的实现之间能够正确的交互信息。 ( 5 ) 性能方面的统计与测试：这一般是现在商业上测试的重点，例如路由器的信息流量 等。 2 1 3 路由协议的测试方法与手段 路由协议的测试应当在动态的测试环境中开展。比如对于网络拓扑结构变化的发现与传 播，以及收敛时间等，需要能够模拟网络拓扑结构变化的环境或系统。 针对路由协议的特点，对路由协议的帧结构、状态机和路由信息的交换与处理的测试， 采用图2 1 所示的测试模式 9 1 。 不可见部分可见部分 可控制 可观察 可观 路由信 息接收 数据库 路由表 路由信i路由协议 息发送l 路 由 模 块 图2 1 路由协议的测试模式 f i g u r e2 1t e s tm o d eo f r o u t i n gp r o t o c o l 路由协议的互操作测试，如不同路由器的交互，可以通过在线监听的工作方式，捕获全 部的数据帧，解析、显示每个帧的数据内容，比较不同的实现在帧格式上的异同，得到互操 作性方面的基本依据。 对于路由协议内部过程的测试可以采用两种方式，称为“静态方式 和“动态方式， 如图2 2 所示 9 1 ，这两种方式的差别在于“正确 结果确定的时间。在静态方式中，根据测试 数据，通过计算过程得到正确结果，由测试数据和正确结果形成测试集，由测试执行负责执 行，测试执行根据被测实现i u t 的响应与正确结果进行比较，得到判决，即正确结果在测试 执行之前一定要得到；而动态方式则是直接将测试数据形成测试例，由测试执行发送给i u t ， 同时由计算过程得到正确结果，与i u t 的响应进行比较得到判决，正确结果是在测试执行过 程中得到的。动态方式灵活性较强，如果动态生成测试数据，则可动态生成并执行大量测试 例，但是采用何种测试方式与测试系统的特性有关。如果采用t t c n ( 一种描述测试例格式 4 内蒙古大学硕士学位论文 的标准) 格式的测试集，一般采用静态方式。尽管存在上述区别，但是两种方式的共同点在 于都将内部过程作为“黑盒 处理，不关心内部过程的实现细节，而只关心处理结果，将其 与计算过程得到的“正确”结果进行比较。 图2 2 静态方式和动态方式 f i g u r e2 2s t a t i cm o d e - a n dd y n a m i cm o d e 总的来说，一般情况下对于路由协议基本功能的测试，如帧格式、状态机等，采用成熟 的形式化手段，对于难以形式化的，如果采用形式化方法，可能造成不可测或开销太大的问 题，此时应当采用非形式化的方法和手段1 0 1 。 2 2 协议一致性测试 2 2 1 一致性测试概论 协议测试主要可以划分为四种类型：一致性测试( c o n f o r m a n c et e s t i n g ) 、互操作测试 ( i n t e r o p e r a b i l i t yt e s t i n g ) 、性能测试( p e r f o r m a n c et e s t i n g ) 和强健性测试( r o b u s t n e s st e s t i n g ) 。其 中，一致性测试主要是测试协议实现是否严格遵循相应的协议标准，它是其它三种测试的基 础；互操作测试关注的是对同一个协议标准，不同协议实现之间的互连通问题；性能测试是 判别一个协议实现的性能特性是否符合协议说明；而强健性测试则是检测协议实现在各种恶 劣环境下的运行能力。 目前一致性测试领域存在两个理论体系：国际标准i s o i e c 9 6 4 6 “o s i 一致性测试方法和 框架”c t m f ( c o n f o r m a n c et e s t i n gm e t h o d o l o g ya n df r a m e w o r k ) 【1 1 】【1 2 j 和i s 伽e c 与i t u t s 的联合项目“一致性测试中的形式化方法 f m c t ( f o r m a lm e t h o d si nc o n f o r m a n c et e s t i n g ) 1 3 1 0 c t m f 为测试集制定了设计步骤和描述方法，并为测试系统提供了指导。 5 i s i s 路由协议一致性测试的研究 2 2 2 一致性测试过程 一致性测试过程大致可以划分为三个阶段：第一阶段是为某特定协议文本描述一个抽象 测试集，称之为“测试生成 ，之所以称为“抽象测试集是因为它独立于所有的协议实现， 抽象测试集本身也应该是标准的。第二阶段是实现特定测试集的执行方法，也称作“测试实 现 。在这一阶段，抽象测试集中的抽象测试例被转变为在实际的测试设备或测试系统上可 执行的测试例，同时应考虑到测试环境与被测协议实现的具体情况。第三阶段为“测试执行 ， 运行已经具体化的测试例，并对t 的外部行为响应进行观察，最终可以得到测试判决，并 将测试执行的结果记录在协议一致性测试的报告中。 协议一致性测试的工作流程如图2 3 所示【l 。、首先根据协议说明生成一致性测试套；再利 用协议实现一致性说明p i c s ( p r o t o c o li m p l e m e n t a t i o nc o n f o r m a n c es t a t e m e n t s ) 和协议实现的 测试附加信息p i x i t ( p r o t o c o li m p l e m e n t a t i o ne x t r ai n f o r m a t i o nf o rt e s t i n g ) 进行测试选择， 选择适当的测试例进行执行；测试记录参照p i c s 和p i x i t 对i u t 进行评估，并给出测试报告。 图2 3 一致性测试的工作流程 f i g u r e2 3t h ef l o wc h a r to fc o n f o r m a n c et e s t i n g 6 内蒙古大学硕士学位论文 2 2 3 一致性测试方法 根据i s 0 9 6 4 6 1 拘定义，协议一致性测试的基本模型如图2 4 所示【l l 】。u t ( u p p e rt e s t e r ) 是 高层测试软件或硬件，l t ( l o w e rt e s t e r ) 是低层测试软件或硬件。u t 与l t 通过控制观测点 p c o ( p o i n to fc o n t r o la n do b s e r v a t i o n ) 和m t 交换a s p ( a b s t r a c ts e r v i c ep r i m i t i v e s ) 。根据 这种测试模型，提出了四种测试方法： 本地测试法l m ( l o c a lm e t h o d ) 沿用传统的软件测试方法。在l m 中，t 的两个p c o 都 可以当作端口访问，并且i u t 和测试器位于同一个系统。 分布测试法d m ( d i s t r i b u t e dm e t h o d ) 的l t 通过p c 0 1 和低层服务从另一个系统访问i u t 。 协调测试法c m ( c o o r d i n a t e dm e t h o d ) 与d m 很相似，主要差别在于c m 使用一种测试协 调协议( t e s tc o o r d i n a t i o np r o t o c 0 1 ) ，通过一条特殊的通道来协调u t 和l t 。 远程测试法r m ( r e m o t em e t h o d ) 与d m 相比，r m 仅有l t ，而且在i u t 的被测层上有可 能有多层协议。 图2 4 一致性测试的基本模型 f i g u r e2 4t h em o d e lo f c o n f o r m a n c et e s t i n g 7 i s i s 路由协议一致性测试的研究 3 1 形式描述语言 第三章理论基础 形式描述在整个协议开发生命周期中起主导作用，它是协议开发活动的基础。与自然语 言相比，形式描述语言具有以下特征：克服了自然语言的不精确性和二义性；有利于对协议 的正确性进行验证：有助于协议实现的半自动代码生成；可从协议的形式描述文本自动生成 测试序列；可以自动选择基于形式描述的测试例；测试结果与协议规范之间的比较分析可以 自动执行；有利于采用工具搭建协议开发环境。 协议说明的形式化描述是以协议模型为基础的，目前主要有两种协议模型：状态转换模 型和进程模型。 状态转换模型是最早用于协议说明的一种形式模型，它认为网络协议是由若干事件驱动 的实体组成，实体间可以通过传送事件相互进行通信。每个实体的特性可以描述为一系列响 应外部和内部事件的动作。 进程模型是由数学家提出的，他们将进程作为演算目标建立一个代数系统进程代数 ( a l g e b r ao f p r o c e s s e s ) 。进程代数有着明确的定义和代数变换法则，抽象程度非常高。 为了更好的描述协议，人们将上述模型和程序设计语言结合起来，开发出专门用于描述 协议的语言：形式描述语言f d l 。f d l 既有程序设计语言可读性好的优点，又可以充分描述 协议的各种特性( 并发性、时序性、不确定性等) 。现在形式化的协议说明大部分是用f d l 描述的。常见的f d l 有： ( 1 ) e s t e l l e ( e x t e n d e ds t a t et r a n s i t i o nm o d e ll a n g u a g e ) 是一种基于扩展有限状态机 e f s m 的f d l 。它把一个系统看作是由许多相互通信的模块分层嵌套而构成的，这些模块的行 为用可相互通信的非确定性e f s m 来描述。e s t e l l e 是p a s c a l 语言的扩充，对并发、不确 定性、超时、异步通信状态转换有较强的表达能力，但对递归、共享通道、同步通信、协议 性质的表示缺少有力的手段。 ( 2 ) s d l ( s p e c i f i c a t i o na n dd e s c r i p t i o nl a n g u a g e ) 也是基于e f s m 的f d l 。其数据部分 采用抽象数据类型的代数表示法a c to n e 来描述，程序变量和数据结构用c c i t t 定义的程序 设计语言c h i l l 来表示。s d l 还开发了一种图形的表示形式。 ( 3 ) l o t o s ( l a n g u a g eo f t e m p o r a lo r d e rs p e c i f i c a t i o n ) 是以进程模型通信系统演算c c s 8 内蒙古大学硕士学位论文 和通信顺序进程c s p 为基础开发出来的f d l ，其数据部分用a c to n e 描述。l o t o s 将一个系 统看作是由多个相互作用的子进程组成的进程，每个子迸程又是由多个子进程构成，它能够 很好的描述分布、并发和信息处理系统。l o t o s 有很好的数学基础，抽象级别较高，但可读 性差，无异步通信机制。 ( 4 ) e l o t o s ( e i l l l a n c e m e n t st ol o t o s ) 是由i s o i e cj t c l s c 2 1 w g 7 开发的一个 l o t o 的增强版本。e l o t o s 增加了模块和接1 2 1 定义、友好的数据类型( 预定义类型、递 归类型、结构类型) 、时间说明( 针对实时系统) 等许多功能，它能有效地描述时间和随机 事件的发生。e l o t o s 语言是在l o t o s 基础上对l o t o s 的描述能力进行了增强，增强的功能 不仅使e l o t o s 在描述实时性及不确定性等方面有了更强的描述能力，而且还引入了模块语 言，使e l o t o s 说明具有封装性、易于实现代码重用和转换为计算机语言【1 4 】【1 5 】【1 6 1 。 e l o t o s 是一种分层语言，高层是模块语言，底层是基本语言，如图3 1 所示。e l o t o s 中的模块语言能描述完全抽象的语法。这些抽象语法包括：说明描述、模块、模块表达式、 一般模块说明、接口说明、接口表达式和说明。 e l o t o s 描述 s p e c i f i c a t i o n 模块描 类型定义 函数或过程描述 其它引入模块 类型定义 函数或过程描述 图3 1e - l o t o s 描述层次图 f i g u r e 3 1 ：t h eh i e r a r c h yo f e l o t o s 3 2 测试套描述语言t t c n - 3 测试表示方法是协议测试理论的一个重要分支，其研究目的是提供一种适合于表达在 p c o 处的测试交互动作以及测试集结构的语言。作为一种通用的协议测试表示方法，应满足 以下几点要求：( 1 ) 使用这种测试表示方法所描述的测试集应该是系统独立的；( 2 ) 使用 9 i s i s 路由协议一致性测试的研冤 这种测试表示方法可以描述任意协议的一致性测试集；( 3 ) 能为测试集的设计人员提供自动 或半自动支持工具以加快测试集开发过程；( 4 ) 降低整个测试集的开发和维护费用：( 5 ) 提高协议一致性测试的标准化程度，以增强开放系统之间的互操作性；( 6 ) 易于学习和掌握， 易于测试操作人员理解。而t t c n 3 正是满足上述条件的一种形式化语言。 t t c n 一3 ( t h et e s t i n ga n dt e s tc o n t r o ln o t a t i o nv e r s i o n3 ) 是指测试和测试控制表示法第 三版，它是一种灵活和强有力的语言，可以用做多种通信端口上的各种响应系统的测试描述 语言。典型的应用领域是协议测试、服务测试、模块测试等等。t t c n 3 并不仅仅局限于一致 性测试，它可用于多种类型的测试，如互操作测试、强健性测试、回归测试等。 t t c n 的发展经历了3 个版本。t t c n 2 是树表结合表示法，即采用以树和表格为表现形 式的测试表示法，其中表格主要用于数据类型、原语、协议观察点、约束等，树则用于描述 测试集、测试例、测试步。t t c n - 2 对t t c n - 1 进行了一定程度的扩展。t t c n 3 建立在t t c n 2 之上，并且对其有了重要的扩展：描述t t c n 3 的核心语言类似程序设计语言，因此容易学 习；它不再像t t c n 2 一样使用协议中的术语，如p c o ，a s p ，p d u 等等，它有新的标准化 的图形表示格式，完全是动态的测试配置，支持异步通讯，支持对分布式系统的测试，有标 准化的测试系统接口，改进了测试串的匹配彼用规则的表达式，具有与抽象语法符号更 好的兼容性【l7 1 。 3 2 1t t c n - 3 核心语言 t t c n 3 核心语言是广义的基于文本的t t c n 3 测试语言，是t t c n 3 测试套在不同 t t c n 3 t 具之间转换的标准化格式，同时也是其它表示形式的语义基础。表示形式有表格表 示形式，图形表示形式，也可以是用户自定义表示形式，如图3 2 所示【3 】。 l o l 卜一 c o r 一亿t a b u l a 卜 妇抖磐哺纛擘蠹 1 嚣：霉卜一一艳g r a p h ；= 卜 i l ，& o t v h e 。r 。t 。y ；p 。e 5 卜l 绝”巩r 。势 图3 2 核心语言和各种表示格式的用户视图 f i g u r e 3 2 - u s e r sv i e wo fc o r el a n g u a g ea n dt h ev a r i o u sp r e s e n t a t i o nf o r m a t s t t c n 3 基本语言元素包含模块定义、其它模块的定义引入、组定义、数据类型定义、通 1 0 内蒙古大学硕士学位论文 信端口定义、测试成分定义、特征定义、外部函数定义、常量定义、模板定义、函数定义、 可选步定义、测试例定义、变量声明、定时器定义。 t t c n 3 的顶层单元是模块。一个模块中不能包含子模块，但是它可以从其它模块中引入 定义。一个模块由一个定义部分和一个控制部分组成，如图3 3 【3 】所示。模块的定义部分定义 测试成分、通信端口、数据类型、常数、测试数据模板、函数、测试端口上调用的过程特征、 测试例等等。模块的控制部分调用测试例，并控制它们的执行。 模块定义 定义部分 数据类型、测试成 分、测试端口等定义 测试例等 控制部分 测试执行等 图3 3t t c n - 3 测试套层次图 f i g u r e 3 3 ：t h eh i e r a r c h yo f t t c n 3t e s ts u i t e t t c n 3 支持许多预定义的基本类型，而且还可以从基本类型中构造结构类型。 测试例在模块定义部分定义，在模块控制部分执行。 3 3 测试例自动生成工具p a t s a g 测试例自动生成工具p a t s a g 是由内蒙古大学计算机学院自主开发的、能自动生成用 e l o t o s 语言描述的多种协议的t t c n 3 格式的抽象测试例，图5 5 即为用该工具生成的一个 关于i s i s 协议的抽象测试例。 i s 1 s 路由协口一致件测试研究 41 i s - i s 协议概述 第四章l s l s 路由协议 i s * i s 协议原是o s i 七层架构中的路由协议，由于得到广泛的认可和应用，i e t f i 作组将 之引a t t c p i p 协议族中来，制定了相应g j r f c 标准使其可以同时运行在o s i 、i p 两种环境 之中；i s i s 协议直接使用数据链路层服务，而不使用网络层服务。i s i s 协议一般用于同一个 自治系统a s 内：每个运行i s i s 的路由器都维护一个数据库，该数据库能精确、实时的描述整 个或者部分a s 的拓扑结构以及链路的状态，i s ，i s 路由器通过此数据库计算得出i s i s 路由表； i s i s 路由器通过与邻接路由器交换路由信息来工作，具有分布式的特点。 i s i s 协议是一种内部网关路由协议，它采用两层分层体系l 】层和l 2 层，以便在大型 网络中管理选路和实现可扩展路由选择。它节省资源并且可扩展性好。如图41 所示i s i s 协议将路由器分为l 1 路由器、l 2 路由器和l 1 ，l 2 路由器三种。i s i s 将整个路由域分为多个区 域，区域之间通过l 2 ( l 1 l 2 ) 路由器相连接，区域内的所有l i 路由器知道整个区域的拓扑 结构。只有同一层次的相邻路由器才有可能形成邻接关系【”1 1 1 9 1 2 0 l 。 ，每。二皆誊j 若一寥一。霉譬精 l i f 5 萄 “7 “f 留 i ，7 。 ，尹鲞、 浮瞄 、国。， 图41i s i s 路由协议拓扑结构图 42 s i s 协议报文 根据i s 0 1 0 5 8 9 和r f cl1 9 5 所述，i s - i s 协议使用9 种p d u 类型柬进行它的控制信息处 理，并使用一个5 位二进制位的类型号来标识每一个p d u ，所有p d u 可以归纳分为3 类， 塑鍪直奎堂堡主竺竺丝茎 即h e l l op d u 、l s p 和s n p 。 ( 1 ) h e l l op d u ：i s i sh e l l op d u 是同一条链路上的i s i s 路由器用来发现与它们相邻 接的i s i s 邻居路由器的。一旦路由器发现了它的邻居路由器并且成功建立了邻接关系，h e l l o p d u 报文的工作就可以只担当维持邻接关系的功能，并将邻接关系中的任何参数的变化通知 邻居。 ( 2 ) l s p ：i s i s 协议中的一台l 1 路由器把l 1 类型的l s p 泛洪到整个区域，用来确 定它的邻接关系和这些邻接关系的状态。一台l 2 路由器把l 2 类型的l s p 泛洪到整个层2 的 域，用来确定它与其它l 2 路由器的邻接关系，并标识出该l 2 路由器能够到达的地址前缀。 ( 3 )s n p s n p 报文通过描述数据库中的部分或者全部的l s p 的信息，对域中各路由 器上的i s i s 链路状态数据库的同步进行维护。一台指定中间系统d i s 将会周期性的以组播 方式发送c s n p 来描述伪节点数据库当中的所有l s p 信息。一个p s n p 只是携带部分l s p 的 信息。一台路由器可以在一个点到点网络上发送p s n p 来确认收到的l s p 。在一个广播型的 网络上，p s n p 将会用来请求丢失的或者最新的l s