（计算机软件与理论专业论文）bgp4基于策略的互操作性测试研究.pdf

内蒙古大学硕士学位论文 b g p 4 + 协议基于策略的互操作性测试研究 摘要 随着互联网的迅速发展，高效稳定的路由协议成为保障网络性能的重要 因素，协议测试理论和测试方法的研究也日益显得重要。协议一致性测试和 互操作性测试是协议实现能够在实际环境中正确互连互通的重要保障。 我们的工作主要针对互操作性测试展开，包括以下两个部分： 第一：理论研究工作。总结分析了互操作性测试和一致性测试的相互关 系，指出对协议实现进行互操作性测试的必要性。针对b g p 4 路由协议的特 点，将测试分为基于有限状态机测试和达到稳定状态后路由选择策略的测试。 有限状态机可以描述路由协议的基本行为，基于它我们给出自己的互操作性 测试推导方法，生成了部分测试序列。对于路由选择策略的部分，详细研读 了b g p 4 及b g p 4 + 的最新说明，并参考一些互操作性测试相关资料来抽取测 试例。 第二：测试实践工作。根据自己推导的测试目的和选定的测试架构的需 要，开发了互操作性测试工具，这样可以适应某些特殊的测试例。同时对 b g p 4 + 协议的不同的实现，根据具体的测试目的和测试设计，进行了一些互 操作性测试实验，针对b g p 4 + 的策略部分进行了互操作性测试设计与实施， 并且给出了测试报告。 关键词路由协议，互操作性测试，b g p 4 + ，有限状态机，策略 b g p 4 + 协议基于策略的互操作性测试研究 r e s e a r c h o ni n t e r o p e r a b i l i t yt e s t i n go fb g p 4 + b a s e do np o l i c y a b s t r a c t w i t ht h ef a s td e v e l o p m e n to fi n t e m e t ，e f f i c i e n ta n ds t a b l er o u t e p r o t o c o l sh a v e t u r n e do u tt ob eak e yf a c t o rt oe n s u r et h eh i g hp e r f o r m a n c eo fn e t w o r k s ，a n d r e s e a r c ho nt h e o r i e sa n dm e t h o d sa b o u tr o u t i n gp r o t o c o lt e s t i n ga p p e a r st ob e 一一 一 一 m o r ei m p o r t a n tt h a nb e f o r e c o n f o r m a n c et e s t i n ga n di n t e r o p e r a b i l i t yt e s t i n g c a ng u a r a n t e eap r o t o c o l i m p l e m e n t a t i o np e r f o r mc o r r e c t l yi nar e a ln e t w o r k e n v i r o n m e n t o u rr e s e a r c hw o r km a i n l yf o c u s e so ni n t e r o p e r a b i l i t yt e s t i n g ，a n dc o n s i s t so f t h ef o l l o w i n gt w op a r t s ： f i r s tp a r ti st h e o r e t i cw o r k t h er e l a t i o n s h i pb e t w e e ni n t e r o p e r a b i l i t yt e s t i n ga n d c o n f o r m a n c et e s t i n gi s a n a l y z e d ，a n di n t e r o p e r a b il i t yt e s t i n go fap r o t o c o l i m p l e m e n t a t i o ni se s s e n c i a lt ot h ep r o d u c t so nt h ei n t e m e t a c c o r dt ot h ef e a t u r e s o fb g p 4 ，t e s t i n gw o r ki sd i v i d e di n t ot w op a r t s ：t e s t i n gb a s e do nfs ma n d t e s t i n g b a s e do np o l i c ya f t e rt h ef s mr e a c h e se s t a b i l i s h e ds t a t e b a s i ca c t i o n so fr o u t e p r o t o c o l sc a nb ed e s c r i b e db yf s m ，a n dt h et e s t i n gs e q u e n c e sa r eg e n e r a t e d s o m et e s t c a s e sa r ea c h i e v e db yr e f e r r i n gt ot h en e w e s ts p e c i f i c a t i o n so fb g p 4 a n dt h er e l a t e dm a t e r i a lo fi n t e r o p e r a b i l i t yt e s t i n g s e c o n dp a r ti sp r a c t i c a lw o r k 。a c c o r d i n gt ot h ep u r p o s eo f t e s t i n ga n dn e e d so f t e s t i n g ，t h et o o lo fi n t e r o p e r a b i l i t yt e s t i n gi sd e v e l o p e dw h i c hc a nb ea d a p t e dt o 内蒙古大学硕士学位论文 s o m es p e c i a lt e s t c a s e s t h es p e c i f i cp u r p o s e so ft e s t i n ga n dd e s i g no ft e s t i n ga r e f i n i s h e di na c c o r d a n c ew i t ht h ed i f f e r e n tr e a l i z a t i o n so ft h eb g p 4 + p r o t o c 0 1 s o m ei n t e r o p e r a b i l i t yt e s t i n gc a s e sa r ef i n i s h e d ，a n dt h et e s tr e p o r t sa r e p r e s e n t e d k e y w o r d sr o u t i n gp r o t o c o l ，i n t e r o p e r a b i l i t yt e s t i n g ，b g p 4 + ，f s m ，p o l i c y i i i 内蒙古大学硕士学位论文 图表目录 图1 1 域间和域内路由的示例3 图1 2i n t e m e t 的横向结构9 图1 3i n t e m e t 的纵向结构9 图2 1 互操作性测试框架1 1 图2 2 互操作性测试体系结构1 2 ( a ) 互操作性测试体系结构l 1 2 ( b ) 互操作性测试体系结构i i 1 2 ( c ) 互操作性测试体系结构i i i 1 2 图2 3 由两个有限状态机组成的系统1 4 l 虱：! z if s mm 1 15 图2 5f s mm 2 一15 图2 - 6m 1 和m 2 组成的部分可达图1 6 图2 7m 1 和m 2 组合的有限状态机mi * m 2 17 图2 8 输出错误18 图2 - 9 变迁错误：18 表2 1m i * m 2 的状态检测序列2 0 图2 10 由e t 边组成的图g t 2 0 图2 1 1 图g t 2 l 表3 1b g p 4u p d a t e 包格式。2 4 图3 1b g p 4 和b g p 4 + 连接建立过程2 6 表3 2b g p 4 + u p d a t e 包格式2 7 表3 3b g p 4 路由信息库。2 9 图4 1b g p 4 + 主动模式下的f s mm l 。3 2 图4 2b g p 4 + 被动模式下的f s mm 2 3 3 表4 1m 1 和m 2 的输入输出说明3 3 图4 3b g p 4 + 互操作性测试可达图3 5 图4 - 4 互操作性测试例3 6 图4 5 测试集生成过程3 9 图4 6 策略测试的架构图4 0 v i i b g p 4 + 协议基于策略的互操作性测试研究 图4 7b g p 4 + 决策过程4 1 表4 2 测试例实例。4 2 图5 ，1 互操作性测试工具基本架构4 4 图5 2 测试套编辑流程图4 5 图5 3 执行模块的设计4 6 图5 4 日志模块设计：4 7 图5 5 基于f s m 测试的配置。4 8 图5 - 6 策略测试的配置4 9 表5 1 测试例实例。4 9 表5 2 测试例实例5 0 表5 3 测试例列表5 1 表5 - 4 测试示例5 2 v i i l 原创性声明 本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成 果。除本文已经注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得囟苤直太堂及其他教育机构的学位或证书而使用过的材料。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作了明确的说明弗表示谢意。 学位论文作者签名： 日期： 指导教师签名： 日期： 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，i i p - 内蒙古大学有权将 学位论文的全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允 许编入有关数据库进行检索，也可以采用影印、缩印或其他复制手段保存、汇编学位论文。 为保护学院和导师的知识产权，作者在学期间取得的研究成果属于内蒙古大学。作者今后 使用涉及在学期间主要研究内容或研究成果，须征褥内蒙古大学就读期间导师的同意；若用 于发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表。 学位论文作者签名： 日 指导教师签名： 日期： 鑫 盏 内蒙古大学硕士学位论文 引言 随着计算机网络的飞速发展，网络技术已经应用于各个领域。协议测试理论与技术是 保证计算机网络协议实现能够正常工作的关键，所以针对它的研究工作非常重要。协议测 试是对协议实现进行评价的有效方法。协议测试包括一致性测试和互操作性测试，其中一 致性测试工作开始的最早，所以理论技术比较成熟，但通过一致性测试并不能保证多个不 同协议实现在实际网络环境中能正确的互联互通，因此，互操作性测试也越来越被重视， 对多个不同的协议实现进行互操作性测试是必要的。 随着i n t e m e t 的发展和网络服务商业化进程的加快，i n t e m e t 的规模和复杂程度都在迅 速增长。从管理角度，i n t e r a c t 由不同的a s 构成，所谓的a s 是相对独立的网络，在一个 a s 内有自主的路由策略。这些a s 可能分别隶属于不同的i n t e m e t 服务提供商( i n t e m e t s e r v i c ep r o v i d e r 简称i s p s ) ，而不同的i s p s 可能重组成为新的i s p ，从而形成动态的管理 组织结构。在a s 内部，路由是通过域内路由协议来管理调度，如o s p f 、i s i s 和r i p 等； 在a s 之间它们通过公共网络访问点( p u b l i c n e t w o r k a c c e s sp o i n t s 简称p n a p ) 和边界网 关协议来接收和转发网络信息。 由于下一代互联网技术的发展，面向i p v 6 的路由协议也得到了不断的发展和完善。 i e t f 已经分别给出了下一代路由协议的r f c ，例如r i p n g 、o s p f v 3 以及b g p 4 + 。其中 由于b g p 4 协议是最基本和最重要的域问路由协议，其面向i p v 6 的版本为b g p 4 + ，所以 对于它的实现进行互连互通性测试具有重要的现实意义。我们所做的工作是针对b g p 4 + 进行互操作性测试，既需要基于b g p 4 分析又需要分析b g p 4 + ，因此，本项工作的理论 分析以及实践的工作量都很大。 本文围绕b g p 4 和b g p 4 + 协议，对其互操作性测试和策略路由进行了分析研究。我 的工作包括以下几个部分： 1 、 阅读国内外相关论文，分析每篇论文解决问题的特点，总结互操作性测试重 点。通过详细研究分析b g p 4 和b g p 4 + 协议文档，总结适合于b g p 4 和 b g p 4 + 协议的互操作性测试方法。 2 、 对路由协议进行形式化描述，通过模型，找出协议实现之间的交互行为，检 测其是否能正确处理交互信息。策路是b g p 4 协议的重要特点，所以，本文 对其做了深入的研究。 3 、根据实验的需要，对b g p 4 + 协议在n e t 环境下开发了相应的测试工具。 l b g p 4 + 协议基于策略的互操作性测试研究 4 、根据自己研究需要搭建t n 试环境，对b g p 4 + 协议不同实现进行了互操作 性测试。 本文一共分为六章，第一章对协议测试概念和当前研究状况进行了概述；第二章给出 了协议形式化方法；第三章给出了b g p 协议的概述；第四章介绍b g p 4 + 协议基于有限状 态机的测试生成方法和基于策略的测试生成方法；第五章给出了互操作性测试工具以及具 体的测试过程及部分结果；第六章为工作总结及下一步工作展望。 2 内蒙古大学硕士学位论文 1 1 协议概述 第一章协议测试 协议是通信双方关于如何进行通信的约定规则。通信双方只有实现相同的协议，才 可以正确有效的进行信息的传输。常用的协议包括通信协议和路由协议。其中t c p i p 就 是常用的因特网协议簇。常见的通信协议有i p 、t c p 等，路由协议有r i p 、o s p f 、b g p 和i s i s 等。路由器就是通过运行路由协议算法得到到达其它网络的信息。对于路由协议， 根据它的使用是在一个自治系统( a s 缩写) 内部还是a s 之间使用，又可以分为内部网关协 议( 域内路由) 和外部网关( 域问路由) 协议。自治系统内使用的协议为内部网关协议， 比如o s p f 和r i p 协议；自治系统外使用的协议为外部网关协议，主要用来在不同的a s 之间进行路由信息选择和交换，比如b g p 协议。 图1 1 域间和域内路由的示例 f i g u r e1 - 1e x a m p l eo f i n t e r - d o m a i na n di n t e m a lr o u t e 与通信协议相比，路由协议有以下几个不同点： ( 1 ) 路由协议的功能是为路由计算提供所需的信息，正确的处理和发送网络拓扑的信息 是路由协议的主要职责之一，它并不要求数据的“尽力转发”；而通信协议所传送的 3 b g p 4 + 协议基于策略的互操作性测试研究 通常是上层协议的数据，目的是将这些数据尽力、正确、迅速的传送。 ( 2 ) 路由协议需要通信协议所提供的服务，i ：f , 女i b g p 是使用t c p 协议服务的，而o s p f 是使用i p 协议服务的。 ( 3 ) 路由协议都是分布式的。三大路由协议b g p 、r i p 、o s p f 虽然在复杂程度上有很大 的差异，但是它们的实现都具有分布式系统的共性，没有中心控制。各个a s 内和 a s 间的路由器共同构成主干网和各级子网，各自运行自己的协议，通过相互交换 数据信息，共同协作实现一定的功能，有利于网络资源的分配和优化，保证了网络 的强壮性和可靠性。 ( 4 ) 路由协议中有一个非常重要的概念就是数据信息库，用于存放路由信息。路由表是 其中最为重要的数据信息库，直接提供路由所需的信息。 ( 5 ) 路由协议中存在大量的内部处理过程。比如在b g p 4 中，主要的内部处理过程称为 决策处理，包括三个阶段：计算路由的优先度、路由选择、路由传播。这三个阶段 既有顺序的调用关系，又需互斥访问数据库。在三个阶段的处理过程中，遵守许多 规则和应用大量的策略。 ( 6 ) 路由协议利用下层协议传送路由信息，没有“上层”协议存在；而通信协议则有第n 层使用n 1 层的服务为n + i 层提供服务的上下层实体。 ( 7 ) 路由协议之间的交互较为复杂。以b g p 为例，路由器既要与b g p 对等体进行交互 又要与自治系统内部运行其它路由协议的路由器进行交互。 在研究的过程中应注意这些特点，有些关于通信协议的测试方法可以部分的应用于路 由协议，而对于路由协议的一些其它特点，则需要根据实际情况进行测试分析、设计与实 施。 1 2 协议测试基本概念 网络协议的正确实现是保证网络正确无误运行的根本，因此，作为保证网络协议正确 实现的重要技术一协议测试，是必不可少的工作。研究协议测试理论是一项非常重要并具 有很大挑战的工作。 目前，因特网的协议标准r f c 文档已经到达5 0 0 0 多，目前基本上仍是使用自然语言描 述的，实现者对于协议的不同理解会产生不同的协议实现，甚至有时会是错误的实现。因 此需要一种有效的方法来对协议实现的正确性和有效性进行判别，这就是“协议测试”。一 个标准化的协议并不能确保该协议的不同实现之间能够成功的进行通信，因此需要研究协 4 内蒙古大学硕士学位论文 议测试理论。 实际上，协议测试就是试图通过实验的方法找出错误的过程。在协议测试过程中既 要模拟协议实现正常工作的情况，也要模拟异常使用的情况；既要模拟协议实现单独运 行的情况，也要模拟协议实现之间互相通信的情况，这样才能确保在任何情况下协议实 现可以正常工作。由于对一个协议实现进行穷举测试是不现实的，所以协议测试并不能 保证一个协议实现的完全正确，也就是说协议测试只能表明“存在错误”，而不能证明“不 存在错误”，这是协议测试的基本出发点。 一般的软件测试可以分为功能测试和结构测试两种。其中，结构测试又称为“白盒 测试”，它是基于一个软件的内部结构进行的测试，其目的是通过执行每条语句、遍历 程序的各个分支来检查整个程序代码的正确性。与此相反，功i i 钡, t 试只是依据软件的说 明对从外部可以观察到的软件功能进行测试，所以也称之为“黑盒测试”，即把被测试系 统看作一个黑盒，仅仅通过观察外部行为来确定软件的功能实现，而不涉及程序的内部 结构。功能测试的目的是根据软件的说明确定软件实现是否达到了要求，因此预先要有 一个简洁明确的软件功能说明。而协议测试属于功能测试，即黑盒测试。 协议测试包括四种类型的测试：一致性测试( 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 tt e s t i n g ) 。 一致性测试旨在检测协议实现或系统本身与协议规范的符合程度；互操作性测试则重在 检测两个或两个以上的协议实现或系统在接近真实的环境下互相操作互相通信的能力； 性i i 钡, t 试重点检测协议实现或系统的性能指标( 如数据传输速度、连接时间、执行速度 等) ；健壮性测试主要检测协议实现或系统在各种恶劣的环境下运行的能力( 如注入干 扰报文、信道被切断等) 。其中，一个协议实现或系统能否通过一致性测试和互操作性 测试是它能否与其它实现成功互连互通的重要保障，因此对协议实现进行互操作性测试 和一致性测试都是非常必要的。 1 3 一致性测试与互操作性测试 1 3 1 一致性测试与互操作性测试的区别 一致性测试和互操作测试都是测试协议实现重要而有效的方法，在某种程度上可以相 互验证，但二者并非完全一样。 首先，测试目的不同，一致性测试是确定被测实现是否与标准规定一致，而互操作测 b g p 4 + 协议基于策略的互操作性测试研究 试是确定被测设备是否完成要求的功能； 其次，测试级别不同，一致性测试是在协议级，而互操作测试是在功能级； 最后，测试效果不同，一致性测试适用所有被测实现，而互操作测试主要适用于被测 设备之间。 1 3 2 互操作性测试的必要性 在实际测试工作中，通过一致性测试的设备也并不一定能保证能正确互操作。最根本 的原因是一致性测试使用标准规定的绝对完整和完全正确是不现实的，其中也包含各个标 准制定人或制定单位理解不同与利益妥协的问题。具体表现如下： 标准方面：标准中错误与含糊内容；标准本身的兼容性问题。 实施方面：人为错误( 如编程错误) ；对于通信标准不同理解；标准本身允许不同选 项。 技术方面：通信网络使用不同流量策略；设备兼容性问题；设备配置问题。 在过去的通信发展过程中，国际组织主要关注协议一致性测试，协议一致性展开的工 作最早，也形成了很多有价值的成果，而互操作性测试仅仅作为商业测试的一种手段来满 足具体测试者的需求。但是随着通信技术的不断发展，新的协议越来越复杂，协议一致性 测试工作遇到了很多困难，很多情况下通过一致性测试的协议实现，并不能保证它们可以 在实际的网络中能正确的互连互通互操作，所以互操作性测试相关研究也越来越受到重 视。虽然互操作测试在商业测试中已经有很广泛的应用，但是基于实际需求进行理论化、 标准化的研究工作还有待深入进行。互操作测试仅仅可以证实被测系统中不同设备之间的 互操作能力，而不能证实设备是否符合标准，因为互操作测试根本就不关心协议细节。故 此，互操作测试不可能替代一致性测试。 一致性测试和互操作测试是互为验证、互为补充的关系，只有把两者合理地结合才能 完成完整的协议测试，来保证协议实现正确的运行。 1 4 研究机构的测试工作 1 4 1 科研组织具体的测试工作 在协议测试方面，国内外的许多科研组织和团体做了各种研究实践工作。其中：日本 的t a h i i 项目研究和开发了i p v 6 协议的一致性测试系统和互操作性测试系统，他们在 6 内蒙古大学硕士学位论文 i p v 6 方面做了大量的工作，并且在官方网站上公布了部分测试套，而且也公布了最新的 研究进程，目前公布了i p v 6r e a d yl o g o 的测试套，并且仍在继续更新中。n e wh a m p s h i r e 大学的互操作实验室i o l ( i n t e r o p e r a b i l i t yl a b ) 【2 】在协议互操作性测试方面也做了大量 的工作，目前他们对i p v 6 的测试包括测试i p v 6 的基本协议部分以及i p v 6 的相关协议， 并免费提供部分相关测试套，在支持i p v 6 的路由协议测试方面包括b g p 4 + 、o s p f v 3 、 r i p n g 的部分互操作性测试套。e t s i 组织也对i p v 6 协议展开了大量的工作，该组织成员 来自5 5 个国家，并且与许多科研组织和相关工业组织合作，在2 0 0 7 年1 1 月召开i p v 6 协 议测试论坛【3 】，讨论了协议一致性测试和互操作性测试的方法，分析了一致性测试和互 操作性测试各自的特点和局限性，讨论了一致性测试和互操作性测试之间的关系，介绍了 自己的方法；他们使用t t c n 3 来进行一致性测试。在国内，清华大学的计算机网络技术 研究所在网络协议方面做了大量的研究实践工作，完成了多项目国家级项目，发表相关论 文多篇；中科院计算所开发的协议一致性测试系统是一个通用的完整的i p v 6 协议测试平 台，采用自己定义的描述语言来描述测试过程和测试报文，涵盖3 5 个r f c ，5 9 9 个测试 套，能对i p v 6 及相关协议进行完整的一致性测试；中国科技大学、兰州大学、上海交通 大学等多所高校的i p v 6 实验室也开发了自己的测试平台并对i p v 6 及相关协议进行了测 试。 1 4 2 相关的理论研究工作 在协议互操作性理论方面，许多学者发表了相关的文章。文献 4 提出了一种互操作 测试套的生成算法，这种算法很适用于像a t m b i s d n 这类通信协议，并且通过 a t m b i s d n 给出了测试套生成的例子，但是这种算法存在一定的局限性，就是只能处理 两个内部消息交互的情况，也就是说由外部输入激励的内部消息的数目小于等于二。文献 【5 】提出了基于单激励的测试套自动生成算法，并且把该算法应用到a t m b i s d n 和t c p 协议上，给出了测试套生成的示例，之后对生成的两个t c p 互操作性测试套进行了变迁 覆盖分析。文献 6 】提出了一种基于多激励原则的测试生成方法，提高了测试集的变迁覆盖 度，但是没有进行状态空间削减，生成的测试集过于庞大，容易发生状态爆炸问题；而且该方 法要求对协议实体间的交互行为进行控制，不易于实际应用。文献【7 】提出了基于有向图 的最小完全覆盖互操作性测试序列生成算法，提出了最小完全覆盖准则，文中提出思路为： 对于两个测试序列，如果只是本地转化不同，其中所包含的互操作性转化是相同的，那么 这两个测试序列对于互操作性测试来说是等价的。文献【8 】提出了基于多通信端口的模型， 7 b g p 4 + 协议基于策略的互操作性测试研究 被测系统包含两个以上的协议实现，其中每个组件包括多个端口，更适合实际情况，并且 考虑了状态爆炸问题，最后给出了基于单激励的生成算法，且添加了末状态验证序列，用 来检测变迁错误。文献【9 】给出了基于多激励的互操作性测试方法，首先分析了协议实现 的问题，把协议说明中没有定义或定义不明确的变迁作为研究重点，称之为可疑变迁，然 后建立模型，并且给出了怎样解决多激励中存在的活锁问题的方法；其后，又给出基于多 激励模型检测可疑变迁的算法，为了提高覆盖度和效率，该算法使用了增量算法【1 0 】。文 献【1 1 提出了一种新的互操作性测试生成方法，首先分析了引起状态爆炸的原因来自计算 说明中的并行交互，即交互队列f i f o 没限定引起的，使用b i l a t e r a lc r i t e r i o n 方法，将互 操作性测试中使用的测试目的分为两个对称的测试目的，分别对应一个i u t ，这就避免计 算说明中的交互行为，有效的避免了状态爆炸，最后将该方法应用于i s d n 通信协议。文 献【1 2 提出了一种将“q u i e s c e n c em a n a g e m e n t 应用于互操作性测试的方法，主要解决的问 题是：在互操作性测试中，几个组件之间相互通信，当一个组件保持静止( 即没有外部激 励下没有任何的下一步的行为) 的时候，就将整个测试判定为失败是不合适的，有时候， 这种静止可能是说明中所期望的行为；该文是在i o l t s 基础上改进，称为q u i e s c e n c ea n d s u s p e n s i v ei o l t s ，这样便把q u i e s c e n c e 描述在模型之中，然后，举例说明该模型解决上 述问题的过程。 1 5i n t e r n e t 的结构 i n t e r a c t 路由体系结构【1 3 】可以从多个角度进行分析。从横向来看，任何通信系统包 括计算机网络都是由末端节点和网络节点构成，其中末端节点是通信的主题( 在计算机网 络中称为主机) ，而网络节点是进行通信的接入和交换设备，也可称为网络接口信息处理 机。由于i n t e r a c t 这样一个广域的计算机网络系统自始自终都具有这样一个特点：由国际 范围内的组织松散的自治的计算机网络构成，这些自治的网络是由一些智能的网络节点一 一路由器连接起来，用户数据封装在i p 分组内由这些路由器一段一段的进行传播，直到 目的主机。因此，i n t e m e t 是一个基于路由器的通信网络，所有末端节点( 主机) 都必须 通过网络节点( 路由器) 才能与其它末端节点进行通信。图1 2 说明了这一横向结构特点 ( 其中h 表示主机，r 表示路由器) 。 内蒙古大学硕士学位论文 图1 - 2i n t e m e t 的横向结构 f i g u r e1 - 2h o r i z o n t a ls t r u c t u r eo fi n t e r n e t 从纵向来看，即从o s i 参考模型的协议层次的观点来看，i n t e m e t 为了掩盖网络层以 下各种不同的具体网络实现的差异，各主机之间从网络层以上都遵守t c p i p 协议簇，以 实现网络层以上的互连。所有的上层协议及应用层协议都是直接的或间接的建立在口这 种不可靠的无连接的数据报协议之上的，i p 分组是整个i n t e m e t 数据传输的基本单位。 因而，对于路由器来说，最重要的是实现i p 协议以及路由协议，能够根据收到的p 分 组的头信息进行正确的处理和转发。 主机a主机b 物理网络 i p 层 数据链路层 物理接口 物理网络 图1 - 3i n t e m e t 的纵向结构 f i g u r el - 3v e r t i c a ls t r u c t u r eo fi n t e m e t 从图1 2 和1 3 的i n t e m e t 的结构来看，是路由器把主机从繁重的路由负担中解放出 9 一一帐一一一 一一雌一一一一 b g p 4 + 协议基于策略的互操作性测试研究 来，决定i p 分组转发方向的关键因素是路由表。路由表的建立、查找、维护和更新工作 是路由器完成的。而路由协议正好承担了这部分工作，由此可见，对于它进行一致性和互 操作性测试的重要性。 1 6 关于路由协议测试的思考 文献 1 4 1 5 1 6 1 1 1 7 1 介绍了关于路由协议测试的研究工作和测试方法，通过阅读这些 文献和其它资料，以及自己的思考，关于路由协议测试有如下总结。 路由协议的实现基于底层通信协议的提供的功能，底层通信协议可以由有限状态机来 描述，通过有限状态机生成测试集，对各个需要测试的变迁和状态进行测试。当然，有限 状态机只可以描述路由协议的基本行为，在有一些时候需要直接基于协议的文档说明进行 研究。 从1 5 节所描述的来看，路由器最重要的行为是负责i p 分组的正确转发，这是由路 由器查找自己的路由表来实现的。有限状态机描述了路由器之间建立连接的过程，即如果 能保证路由器正确实现有限状态机所描述的所有行为，也只是表明路由器之间能互相稳定 的传输数据，不能保证路由器能正确的处理i p 分组及其转发；有限状态机并没有描述路 由器怎样处理转发i p 分组，而这正是路由器的核心任务，也是路由协议的关键所在。 对于路由协议来说，有限状态机只描述了协议的二部分行为，有时候甚至是一小部分。 路由协议更多的行为是在建立连接后，路由信息的转发与否，转发的路由信息格式是否正 确，以及转发的路由信息是否是所期望的，这些都不是状态的变化所能体现的，状态的变 化只是在路由器建立连接前的描述。例如b g p 协议，有限状态机只是描述了对等体建立 连接的过程，而路由处理和分发是在稳定状态后体现出来，协议实现关于路由信息的处理 有很大一部分，这也是路由协议核心所在，有限状态机中并没有描述出来，因此如果基于 协议说明中给出的有限状态机进行测试推导，不可能得到相关的测试例，所以这部分需要 通过详细研读协议说明及相关资料，理解协议工作机制，然后抽取测试例。 l o 内蒙古大学硕士学位论文 第二章协议的互操作性测试方法 2 1 互操作性测试架构 图2 1 给出了互操作性测试框架，被测系统由两个协议实现组成，它们之间的通信为 内部消息，外界环境可以给被测系统发送消息，也可以从被测系统接收消息。当外界环境 给被测系统中任何一个实现输入一个外部消息时，该实现都会产生一个内部输出给另外一 个被测实现，同时会产生一个输出给外部环境，内部消息为两个单向的f i f o 队列。互操 作性测试就是在外部输入的激励下，观察被测系统中两个协议实现是否有我们所期望的交 互，即内部消息队列有我们所期望的消息。 删田 薯 i n t e r n a lm e s s a g e s 薹 。 。 暑暑 竺 n 口需t it 个i卜i f it 下l 一 王要 马舛驯们a 臣；川h 露 器2 是转换集， 其中，每个转换t n i 可以表示为 s 兀，s n ，v u ，s 兀、s 兀s n ，v i n ，u e o n 。其中 i 、j 、k 、p 为自然数。 2 4 基于有限状态机的多激励模型 对于协议互操作性测试的形式化模型，可分为单激励模型和多激励模型。单激励为被 测系统在同一时刻只有一个外部激励，只有当被测系统处理完该激励后，外部再输入下一 个激励；多激励为被测系统在同一时刻有多个外部激励，被测系统同时处理这些激励。 我们的方法需要建立多激励模型。多激励模型相对于单激励的优点为可以包括单激励 没有描述的行为，可以增加测试覆盖，但是也更加复杂。 下面给出我们对系统的多激励形式化模型。如图2 3 中，我们所描述的系统由两个 f s m 组成，i lu1 2 和o lu0 2 分别表示外部输入符号集和外部输出符号集，c 1 2 和c 2 l 表示 内部f i f o 队列，分别表示f s m l 对f s m 2 的内部输出和f s m 2 对f s m l 的内部输出，它 们的符号集分别用e l 和e 2 来表示。f s m l 和f s m 2 为并行通信过程，两个队列分别存储 内部消息。我们所考虑的是多激励模型，即外部环境对系统同时有两个输入，分别为对 f s m l 和对f s m 2 的输入，对于每个外部输入，f s m l 和f s m 2 都有两个输出：外部输 b g p 4 + 协议基于策略的互操作性测试研究 出和内部输出。f s m l 的内部输出即为f s m 2 的内部输入，f s m 2 的内部输出即为f s m l 的内部输入。我们同时假设系统处于慢环境中工作，即只有前一个外部输入被系统处理完 后( 内部队列为空) 下一个外部输入才能被应用。在这种假设下，初始时两个内部队列都 为空，对于外部的一个多激励输入下，每个队列获得一个消息。当一个队列中的消息被处 理完后，它会产生一个新的消息加入到另外一个队列，所以，在任何时候，内部队列的消 息数不会超过两个。 根据上面的假设和描述，我们可以用一个组合的有