（计算机科学与技术专业论文）基于cpn的isis路由协议互操作性测试的研究.pdf

含为获得内蒙古大学及其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 日期： 指导教师签名：壑垒叁 日期：教丛，笸：么 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有权将 学位论文的全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允 许编入有关数据库进行检索，也可以采用影印、缩印或其他复制手段保存、汇编学位论文。 为保护学院和导师的知识产权，作者在学期间取得的研究成果属于内蒙古大学。作者今后使 用涉及在学期间主要研究内容或研究成果，须征得内蒙古大学就读期间导师的同意；若用于 发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表。 学位论文作者签名： 日 指导教师签名： 日期：监 内蒙古大学硕士学位论文 基于c p n 的is is 路由协议互操作性测试的研究 摘要 信息化已成为当今社会发展的大趋势，而网络的快速发展与普及，加快了 这一进程。如今，网络已经成为我们生活当中不可或缺的一部分。高效稳定的 路由协议，作为保障网络性能的重要因素，也受到人们的高度重视。协议测试 是保证协议实现能够在实际环境中正确运行的重要手段。然而，单纯的进行一 致性测试是不够的，因此，有必要进行互操作性测试的研究。 i s i s 路由协议是一种主流的内部网关协议，具有分层的网络路由、可扩展 性强、收敛速度快、稳定性好、占用资源少等特点。因此，在一些大型网络当 中，i s i s 路由协议得到了越来越多的应用。 本文首先对i s i s 协议进行了研究。通过对相关协议规范的研究，建立i s i s 协议的互操作性测试的f s m 模型，结合层次化的思想和m s c 消息序列图，将 f s m 模型向c p n 模型进行转换，得到分层的i s i s 协议互操作性测试的c p n 模 型。其次，使用c p nt o o l s 工具，自动生成完全状态空间。对完全状态空间进行 分析，根据测试目的，生成测试序列，编写测试例，并且手工抽取一些必要的 测试例，作为对测试集的补充。最后，搭建测试平台，进行互操作性测试。在 w i n d o w sx p 平台下，使用路由模拟软件g n s3 模拟c i s c o7 2 0 0 、c i s c o3 6 4 0 等 设备，用得到的测试例对其进行测试，并对实验结果进行分析。 关键词：i s i s ，互操作性测试，f s m ，c p n ，g n s3 内蒙古大学硕士学位论文 t e s ti sa n i m p o r t a n tm e t h o dt og u a r a n t e e t h ep r o t o c o l i m p l e m e n t a t i o nr u n n i n g c o r r e c t l yi nar e a le n v i r o n m e n t h o w e v e r , c o n f o r m a n c et e s ta l o n ei sn o te n o u g ha n d t h 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 ti sr e q u i r e d i s i s r o u t i n gp r o t o c o l isam a i n s t r e a mi n t e r i o rg a t e w a yp r o t o c 0 1 w r i t hi t s a d v a n t a g e ss u c ha sah i e r a r c h i c a ln e t w o r kr o u t i n g ，s c a l a b i l i t y , f a s tc o n v e r g e n c e ，g o o d s t a b i l i t ya n ds m a l lf o o t p r i n t ，i s i sr o u t i n gp r o t o c o lh a sb e e ni n c r e a s i n g l yu t i l i z e di n t h el a r g en e t w o r k i nt h ea r t i c l e ，t h ef i r s ts t e pi st os t u d yi s i sp r o t o c 0 1 f s mm o d e lo fi s - i s p r o t o c o li n t e r o p e r a b i l i t yt e s tw a s e s t a b l i s h e da c c o r d i n gt ot h er e s e a r c ho ft h er e l e v a n t p r o t o c o ls p e c i f i c a t i o n a n dt h e nf s m m o d e lw a sc o n v e r t e dt ot h ec p nm o d e lw i t h t h ei d e ao fh i e r a r c h i c a la n dt h em s cm e s s a g es e q u e n c ec h a r t a f t e rt h ea b o v e a c t i o n s ，t h ec p nm o d e lo fh i e r a r c h i c a li s - i sp r o t o c o li n t e r o p e r a b i l i t yt e s t i n gi s e s t a b l i s h e d s e c o n d l y , t h es t a t es p a c ei sg e n e r a t e da u t o m a t i c a l l yb yu s i n gc p n t o o l s u n d e r t h es t a t es p a c e ，t h et e s ts e q u e n c ei s g e n e r a t e da c c o r d i n gt ot h et e s t i n gp u r p o s e f o l l o w e dt h eh a n ds e l e c t i o no f n e c e s s a r yt e s tc a s e sa sas u p p l e m e n t ，t h et e s tc a s ew a s t h e no b t a i n e d f i n a l l y , t h et e s tp l a t f o r mw a sb u i l tb yu s i n gr o u t i n gs i m u l a t i o ns o f t w a r eg n s 3t o s i m u l a t ec i s c o7 2 0 0a n dc i s c o36 4 0u n d e rw i n d o w sx p , w h i c hw e r et h e nt e s t e dw i t h i i i 内蒙古大学硕士学位论文 t h eo b t a i n e dt e s tc a s e t h er e s u l tw a sa n a l y z e da tl a s t k e y w o r d s ：i s - i s ，i n t e r o p e r a b i l i t yt e s t ，f s m ，c p n ，g n s3 i v i i i i v v i i v i i i 】l 1 2 3 1 4 论文结构：3 第2 章协议互操作性测试理论：5 2 1 互操作性测试概述5 2 2 互操作性测试框架及方法6 2 3 互操作性测试的形式化描述技术_ 7 2 4 互操作性测试生成8 2 5 本章小结“9 第3 章i s i s 路由协议分析1 0 3 1 i s i s 协议概述：l0 3 2i s i s 协议数据包一：“ 3 3i s i s 协议工作原理，。l3 3 3 1 i s i s 分层网络拓扑结构1 3 3 3 2i s i s 子网相关功能1 4 3 3 3i s i s 子网独立功能15 3 4 本章小结1 6 第4 章i s i s 路由协议互操作性测试模型的建立l7 4 1 i s i s 路由协议的f s m 模型1 7 4 1 1 子网相关功能的f s m 模型1 7 4 1 2 子网独立功能的f s m 模型2 0 v 内蒙古大学硕士学位论文 4 1 3 单个i s i s 路由协议的f s m 模型2 3 4 1 4 交互的i s i s 路由协议的f s m 模型2 6 4 2c p n 建模研究2 9 4 2 1c p n 概述2 9 4 2 2f s m 有限状态机到c p n 模型的转换方法3 0 4 3 基于c p n 的i s i s 路由协议互操作测试模型的建立：31 4 3 1i s i s 协议层次化建模分析31 4 3 2 消息序列图m s c 在互操作性测试当中的应用3 2 4 3 3 基于c p n 的i s i s 互操作性测试的交互模型的建立3 5 4 4 本章小结3 9 第5 章i s i s 协议互操作性测试序列生成4 0 5 1 基于c p n 的i s i s 互操作测试序列生成4 0 5 1 1c p n 模型的完全状态空间4 0 5 1 2 由完全状态空间生成互操作性测试序列的方法4 3 5 2i s i s 互操作性测试序列的补充4 4 5 3 本章小结4 5 第6 章实验及结论。4 6 6 1 i s i s 协议互操作性测试框架。4 6 6 2i s i s 协议互操作性测试环境4 6 6 3i s i s 协议互操作性测试举例4 7 6 4i s i s 协议互操作性测试结果5 1 6 5 本章小结5 2 第7 章结论与展望5 3 7 1 结论5 3 7 2 进一步工作5 3 参考文献5 4 附录1 广播网络下子网相关模型的完全状态空间5 7 霉l 谢5 9 v i 内蒙古大学硕士学位论文 图目录 图2 1 互操作性测试框架6 图2 2 互操作性测试框架结构7 图3 1 i s i s 协议报头字段1 2 图3 2i s i s 网络拓扑结构1 3 图3 3i s i s 路由选择引擎1 5 图4 1 点对点网络下i s i s 子网相关功能f s m 模型_ 。1 8 图4 2 广播网络下i s i s 子网相关功能f s m 模型。1 9 图4 3 点对点网络下i s i s 子网独立功能f s m 模型。2 1 图4 4 广播网络下i s i s 子网独立功能f s m 模型：2 2 图4 5 单个i s i s 路由协议的f s m 模型2 4 图4 6 交互的i s i s 路由协议f s m 模型。2 6 。 图4 7f s m 到p e t r i 网转换k “31 ， 图4 8 点对点网络下i s i s 协议消息序列图。3 3 图4 9 广播网络下i s i s 协议消息序列图。3 4 图4 1 0 点对点网络下子网相关功能c p n 模型3 6 图4 1 1 广播网络下子网相关功能c p n 模型j 3 7 图4 1 2 点对点网络下子网独立功能c p n 模型3 7 图4 1 3 广播网络下子网独立功能c p n 模型o 3 8 + ： 图5 1 点对点网络下子网相关模型的完全状态空间4 0 图5 2 状态空间中结点和弧对应的信息- 4 1 图5 3 广播网络下子网相关模型的部分状态空间4 l 图5 4 点对点网络下子网独立模型的完全状态空间：4 2 图5 5 广播网络下子网独立模型的完全状态空间j j 4 2 图5 8 测试序列举例4 3 图6 1 i s i s 协议互操作性测试环境拓扑图4 6 图6 2 表6 1 所示的实验中捕获的h e l l o 包：4 8 图6 3 表6 1 所示的实验中路由器的邻接关系计时器重置过程4 9 图6 4 表6 2 所示的实验中捕获的p s n p 包5 0 v i i 内蒙古火学硕士学位论文 表目录 表3 1 i s i s 术语和i p 术语对照表1 0 表3 2i s i s 协议数据包类型1 1 表4 1 点对点网络下i s i s 子网相关功能f s m 状态表1 8 表4 2 点对点网络下i s i s 子网相关功能f s m 活动表1 8 表4 3 广播网络下i s i s 子网相关功能f s m 状态表1 9 表4 4 广播网络下i s i s 子网相关功能f s m 活动表1 9 表4 5 点对点网络下i s i s 子网独立功能f s m 状态表2 1 表4 6 点对点网络下i s i s 子网独立功能f s m 活动表2 1 表4 7 广播网络下i s i s 子网独立功能f s m 状态表2 2 表4 8 广播网络下i s i s 子网独立功能有限状态机活动表2 2 表4 9 单个i s i s 路由协议的f s m 活动表2 4 表4 1 0 交互的i s i s 路由协议的有限状态机活动表2 7 表4 1 1 点对点网络下i s i s 协议消息表3 4 表4 1 2 广播网络下i s i s 协议消息表3 5 表4 1 3i s i s 协议的c p n 模型库所3 8 表4 1 4i s i s 协议的c p n 模型变迁表3 8 表5 1i s i s 协议互操作性测试部分测试序列4 3 表6 1 i s i s 协议互操作性测试的测试例l ：4 7 表6 2i s i s 协议互操作性测试的测试例2 4 9 表6 3i s i s 协议互操作性测试结果51 v i i i 内蒙古大学硕士学位论文 1 1 研究背景及意义 第1 章绪论 信息化已成为当今社会发展的大趋势，而网络的快速发展与普及，加快了这一进程，如 今，网络已经成为我们生活当中不可或缺的一部分。云计算、i p a d 等新技术和新产品层出不 穷，使得网络的规模不断扩大，复杂性不断提升。相应的，作为网络核心部分的协议，发展 速度也很快。根据2 0 1 0 年2 月份的统计数据，自1 9 8 0 年互联网工程任务组( i n t e m e t e n g i n e e r i n g t a s kf o r c e ，i e t f ) 提出第一个r f c 开始，目前r f c 的数量已经超过5 7 0 0 个，而且新的r f c 文档仍在不断的增加，除了新协议的不断出现，对已有协议的完善、扩展也在同时进行。各 厂家正是根据这些协议，生产出不同的软硬件网络产品。 然而，协议规范通常采用自然语言进行描述，可能存在一些二义性，使得不同的人对其一 产生不同的理解。另外，由于协议本身的灵活性以及可扩展性等问题，使得不同厂商生产的 产品能否在网络环境中正常运行存在了一些不确定性。为了保证各网络产品能够正常使用， 需要对其进行测试，即协议测试。协议测试是软件测试当中的一种，并不检查相应的代码， 而是通过观察被测的协议实现的外部行为，判断协议实现的正确与否。 协议测试包括一致性测试、互操作性测试、性能测试和鲁棒测试。一致性测试的目的是j 检测协议实现与协议说明之间是否相一致，这是协议测试的最基本的工作。互操作性测试的 目的，主要是检测两个或者多个协议实现之间能否进行正确的通信和交互。性能测试的目的 是检测协议实现的各项性能指标。鲁棒测试的目的是检测协议实现能否在各种恶劣条件下正 常的工作。 一致性测试作为协议测试当中最基本的工作，一直是协议测试相关研究当中的重点，通 过各国科研人员的多年努力，取得了丰硕的成果，并在测试方法和测试框架上形成了国际标 型1 1 。然而，受各种条件的制约，对协议实现的一致性测试，无法进行穷举测试，加上协议 规范本身的灵活性，不同厂家对同一协议的理解不同，相应的产品也不同，另外对于协议可 选项，不同厂家在生产产品的时候也会进行不同的取舍，这些原因导致了即使通过一致性测 试的产品，也不能保证他们之间能进行正确的互操作。因此有必要在一致性测试之后，再进 行互操作性测试。 互操作性测试是在一致性测试基础上发展起来的。早期对互操作性测试的研究，很多是 基于c p n 的i s i s 路由协议互操作性测试的研究 将一致性测试的方法移植到互操作性测试当中。然而，互操作性测试本身的一些特点使得一 致性测试的方法不能完全适用于互操作性测试当中。文献 2 】对一致性测试和互操作性测试的 关系和区别进行了研究。目前，对于互操作性测试的研究越来越被重视，一些大的组织，例 如e t s i 、i t u t 、i s o 等组织均已开展相应的工作，并取得了一些成果1 3 巧j 。 中间系统中间系统( 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 m ，i s i s ) 路由协议， 与r i p 、o s p f 等协议一样，是一种主流的内部网关协议。i s i s 协议具有分层的网络路由、 可扩展性强、收敛速度快、稳定性好等特点，特别适合于大型网络，在大型网络当中，其性 能要比o s p f 协议好。因此，在一些大型网络当中，i s i s 路由协议得到了越来越多的应用。 许多厂商，例如思科、华为、中兴等，都推出了支持i s i s 协议的网络产品。然而，相对于 r i p 、b g p 、o s p f 等协议，对i s i s 协议的研究相对较少。国内外对i s i s 协议测试的研究， 也多集中于一致性测试当中。美国新罕布什尔大学互操作实验室i o l 在其网站上公布了i s i s 协议一致性测试的相关测试套标准【6 】，但是尚未给出i s i s 互操作性测试套。因此，需要对i s i s 协议进行互操作性测试的研究。 1 2 国内外研究现状 目前，国内外对互操作测试的研究，主要集中在测试框架和方法、形式化建模、测试生 成等方面。 国外方面，日本的t a h i 项目对i p v 6 协议的一致性测试和互操作性测试进行了长期深入 的研究，对d h c p 、b g p 、r i p n g 等协议进行了测试并在其网站上公布了相应的研究结果。 欧洲的e t s i 对一致性测试和互操作性测试的关系进行了分析，强调了互操作性测试的重 要性，并免费公开了e t s i 互操作性测试方法、测试标准以及部分测试套。 美国新罕布什尔大学互操作实验室i o l 也对互操作性测试进行了深入的研究，对o s p f 、 b g p 、r i p n g 、l d p 等协议进行了互操作性测试，在其官网上免费公布了部分的测试套。 国内研究方面，清华大学在协议测试领域处于领先地位，在协议一致性测试和互操作性 测试方面都做了大量卓有成效的工作，开发了协议集成测试系统p i t s 并对多家厂商的路由产 品进行了测试。 中科院计算所开发了一个通用的完整的协议测试平台，涵盖了3 5 个r f c ，5 9 9 个测试套， 可对i p v 6 协议进行一致性测试。 另外，中国科技大学、上海交通大学、兰州大学、内蒙古大学等高校，也都在协议一致 性测试和互操作性测试领域取得了一定的成果。由电信研究院、华为、中兴公司参与起草、 2 内蒙古大学硕士学位论文 工信部颁布的中国通信行业标准，也对多个协议的互操作测试过程进行了规定。 1 3 本文的研究内容和主要工作 i s i s 协议最早的协议规范是i s 0 1 0 5 8 9 9 7 1 ，是为o s i 七层网络模型设计的路由选择协议， i e t f 工作组对其进行扩展，使其在纯o s i 网络环境下和i p 网络环境下都能够运行，相应的 协议说明是r f c l1 9 5 i 8 1 。本文的主要目的是对i p 环境下i s i s 协议的互操作性测试进行研究， 因此相关标准以r f c l1 9 5 为准。 本文的主要工作如下： 首先，研究i s i s 协议。通过对相关r f c 的研究，采用形式化的方法建立i s i s 协议的互 操作性测试模型。第一步根据协议说明中对协议各个部分的描述，分别建立相应的有限状态 机( f i n i t es t a t em a c h i n e ，f s m ) 模型，之后对其进行整合建立交互的i s i s 路由协议互操作 性测试的f s m 模型。第二步，结合层次化的思想和消息序列图( m e s s a g es e q u e n c ec h a r t ， m s c ) ，将f s m 模型向有色p e t r i 网( c o l o u r e dp e t r in e t s ，c p n ) 1 9 ，1 0 1 模型进行转换，得到分 层的i s i s 协议互操作性测试的c p n 模型。 其次，对c p n 模型进行分析，生成测试序列。具体做法是使用c p nt o o l s 工具，自动生 成完全状态空间，通过对状态空间的分析，得到相应的测试序列，编写测试例。并结合测试 目的，手工抽取一些必要的测试例，作为对测试集的补充。 最后，搭建测试平台，使用得到的测试例对i s i s 协议进行互操作性测试，并对结果进行 分析。 1 4 论文结构 本文章节安排如下： 第一章，介绍了本文研究的背景、意义，国内外研究现状和相关工作，给出了本文研究 的主要内容和所作的主要工作，以及论文的篇章结构。 第二章，介绍了协议互操作性测试的相关理论。从互操作性测试框架及方法，互操作性 测试的形式化描述技术，互操作性测试生成三个方面，分别进行了介绍。 第三章，对i s i s 路由协议进行分析研究。通过仔细阅读相关的协议规范文档，对协议数 据包的类型、格式、用途，i s i s 协议分层网络拓扑结构以及协议的相关功能和工作原理进行 深入的研究与分析。 基于c p n 的i s i s 路由协议互操作性测试的研究 第四章，i s i s 协议的形式化建模。根据协议说明建立交互的i s i s 路由协议互操作性测 试的f s m 有限状态机模型。再将f s m 模型转换为c p n 模型，最终得到分层的i s i s 协议互 操作性测试的c p n 模型。 第五章，i s i s 互操作性测试生成。使用c p nt o o l s 工具，自动生成完全状态空间。根据 完全状态空间，采用相应的算法，得到测试序列，编写测试例。然后结合测试目的，手工抽 取一些必要的测试例，作为对测试集的补充。 第六章，i s i s 协议互操作性测试实施。搭建测试环境，进行i s i s 协议互操作性测试， 并分析实验结果。 第七章，对全文进行总结，并提出下一步工作。 4 能。按测试对象的个数来分，互操作性测试可分为“一对一”和“一对多”两类【1 1 】。在“一 对一”的互操作测试中，又可分为对称协议实体的互操作性测试和非对称协议实体的互操作 性测试。前者是指被测实体实现的是同一个协议规范，例如i s i s 路由协议、o s p f 路由协议 等互操作性测试；后者是指被测实体实现了不同的协议规范，如客户端与服务器端的互操作 性测试。根据互操作性测试与协议规范的关系，又可分为基于协议规范和不基于协议规范的 互操作性测试【1 2 1 。 协议互操作性测试是在一致性测试之后进行的，是对一致性测试的重要补充。进行互操 作性测试的意义，有如下几点： 1 ) 实现绝对的完全覆盖的一致性测试几乎是不可能的，因此一致性测试不能保证协议实 现与协议说明的完全一致，因此，即使通过了一致性测试的协议实现，也不一定能通过互操 作性测试。 2 ) 由于协议规范本身的灵活性，以及对于协议扩展功能的不同选取，也可能导致不同厂 家的产品，甚至同一厂家不同型号的产品之间，不能够进行正确的互操作。 3 ) 各个厂家在对某一协议进行实现的时候，可能会对协议的功能进行扩展，增加一些特 有的功能，导致与其他产品之间的互操作失败。 4 ) 互操作测试是在多个协议实现之间进行，更加接近真实的网络环境，所得结果更加真 实，具有更多的实用价值。 协议互操作性测试是在一致性测试之后发展起来的，与一致性测试有很多相似之处。目 前，对于互操作性测试的研究，主要集中在测试框架和方法的研究、形式化建模技术、测试 例自动生成这三个方面。 基于c p n 的i s i s 路由协议互操作性测试的研究 2 2 互操作性测试框架及方法 与一致性测试不同，互操作性测试并没有一个国际化的标准。文献【1 3 ，1 4 1 对互操作性测试 进行了研究，给出了互操作性测试的基本框架，包括互操作性测试的定义、互操作性测试过 程、抽象测试方法分类等。图2 1 是互操作性测试框架【1 1 】，它将已有的一致性测试的概念应 用于互操作性测试研究，定义了互操作性测试的形式化框架。 t e s ts y s t e m ( t s ) 图2 1 互操作性测试框架【l l l f i g u r e2 1i n t e r o p e r a b i l i t yt e s ts t r u c t i o n 图2 1 所示的测试框架包含两个上测试器u t ( u pt e s t e r ) 和两个下测试器l t ( l o wt e s t e r ) 。 根据测试系统t s 和被测系统s u t 的不同组合，可以有多种不同的互操作性测试构架： 1 ) 单边互操作性测试构架。在这种测试构架中，只对被测系统中的一个对象进行观察控 制。即只包含一个测试者t e s t e r l 或t e s t e r 2 。这种构架又分为三种：l o w e r 、u p p e r 、t o t a l ， 分别表示只包含l t 、只包含u t 和包含两者的情况。 2 ) 双边互操作性测试架构。在这种测试架构中，两个测试者t e s t e r l 和t e s t e r 2 分别独立 地对相应的i u t ( i m p l e m e n t a t i o nu n d e rt e s t ) 进行观察和控制，但两个测试器之间不进行通 讯。这种构架也分为l o w e r 、u p p e r 、t o t a l 三种。 3 ) 全局互操作性测试构架。使用两个测试者t e s t e r l 和t e s t e r 2 对被测系统进行测试，而 且两个测试者之间需要进行通讯。 4 ) 混合互操作性测试构架，是上述三种构架的组合。 s h i n 等人，根据测试系统对互操作系统的观察和控制能力的不同，将互操作性测试框架 结构分为3 类，如图2 2 所示【1 5 1 。 6 图中向上的箭头表示观察( 接收消息) ，向下的箭头表示控制( 发送消息) 。双向箭头表 示一个访问控制点( p c o ) ，单向的向上箭头表示一个观察点( p o ) 。在图2 2 中的三种测试框架 中，t e s t e ra 和t e s t e rb 都能通过与i u ta 和i u tb 交换消息而对i u t 进行观察和控制。在 图2 2 ( a ) 中，t e s t e rc 既可以观察两个i u t 的信息交互，也可以给两个i u t 发送消息，同时具 有观察和控制的能力。图2 2 ( b ) 所示的框架结构中，m o n i t o r 作为观察者，只能观察两个i u t 之间的信息交互，不具备控制能力。在图2 2 ( c ) 中，测试者对两个i u t 之间的互操作行为是 不可观察和不可控制的。 女 上述测试框架结构是基于互操作双方均有完整的信息、可以进行形式化建模的前提下提 出的。在实际当中，可能出现互操作的一方由于各种原因，无法进行完整的建模，只有一方 是可以进行建模和可观察可控制的。为解决这种情况下互操作测试的困难，文献 1 6 提出了 一种“a 对b 的互操作能力 的互操作性测试模型，测试一个新的系统对一个已有系统的互 操作能力。 2 3 互操作性测试的形式化描述技术 采用形式化描述技术，对互操作系统进行建模，是进行互操作性测试的基础。目前，常 用的形式化描述技术有：有限状态机f s m ，p e t r i 网模型，进程代数，时序逻辑，构造类别代 数等。 有限状态机f s m 是一种常用的形式化模型，具有直观性强、可与其他形式化方法组合转 7 基丁c p n 的i s i s 路由协议互操作性测试的研究 换、可自动实现等特点。除了基本f s m ，还有很多扩充模型，例如：扩展有限状态机、结构 化有限状态机，通信有限状态机等。 p e t r i 网是由德国人c a p e t r i 在其博士论文中提出的一种形式化模型。该模型建立在并发 的概念上，能够直观地表示非确定性，可用于描述通信系统中异步成分之间的关系f 1 7 1 。在基 本p e t r i 网的基础上产生了很多扩充，比如数字p e t r i 网、时间p e t r i 网和有色p e t r i 网等。 进程代数是将协议描述成进程的集合，通过进程事件的集合和进程的迹描述进程的行为， 通过并发、选择、递归等描述进程之间的关系。 时序逻辑是模态逻辑的扩充，以状态为可能世界，以状态的演变次序关系为可能世界间 的可到达关系。 构造类别代数，是一种基于代数规范的形式化描述技术。通过定义构造函数或延拓函数 来进行限制，即用公理集合构成了协议行为的规范，特别适合于对协议数据部分及其处理过 程的描述。 国际标准化组织i s o 提出了三种形式化描述语言：e s t e l l e ，l o t o s 和s d l 。 e s t e l l e 是一种基于扩展有限状态机的形式化描述语言，是对p a s c a l 语言的扩充，专门 设计用来描述协议。用e s t e l l e 描述的协议很容易转换成p a s c a l 或c 代码，是一种面向协 议实现的形式化描述语言。 在l o t o s 语言中，一个通信系统被描述成为一系列有时间顺序的、可由外部观察的事 件。l o t o s 使用通信演算系统来描述进程的行为和交互，使用a c t o n e 语言来描述数据结 构和表达式。l o t o s 语言同样存在一些扩展，如d l o t o s ，g l o t o s 等等。 s d l 有两种表示方式图形表示和语句表示。s d l 语言主要由以下几个部分组成：结 构、行为以及通信；s d l 是一种基于扩展有限状态机的形式描述语言，可用于从需求分析到 具体实现的整个开发过程，主要用于实时交互分布式系统的形式化描述。 2 4 互操作性测试生成 基于形式化技术的互操作性测试序列生成是互操作性测试方法中的一个重要的问题i l 。 其目的是从协议规范的形式化模型出发，通过生成算法自动生成用于测试的测试集。互操作 性测试序列生成的过程分两个步骤全局状态生成和测试序列生成。全局状态的构造不可 避免地会引起状态爆炸的问题。为避免这一问题，做以下的假设【1 8 】： 1 ) 慢环境假设：系统处理完前一个输入后，才施加下一个输入； 2 ) 协议规范和实现中都没有活锁：对任何外部输入只能执行有限数目的变迁； 8 内蒙古大学硕士学位论文 在这两个假设的基础上，提出了两个原则1 8 】： 1 ) 基于稳定状态的原则：在系统的稳定状态下，如果没有外部激励，则状态保持不变； 2 ) 单激励原则：在一个外部输入施加之后，只有等到系统达到稳定状态后才能施加下一 个状态，该原则符合慢环境的假设。 在上述假设和原则的基础上生成互操作性测试序列，只考虑稳定的全局状态，根据包含 全局稳定状态的可达图即可生成互操作性测试序列。这样就大大减少了互操作系统中全局状 态的数目，从而减少了发生状态空间爆炸的可能。 当前对互操作性测试生成已经有了初步的研究，但是对于互操作性测试生成方法的研究 仍然存在以下一些不足1 2 】： 1 ) 几乎所有的研究都局限于“一对一”的简单情况，对于“一对多 等更为一般的情形 缺乏研究； 2 ) 在测试生成的过程中，没有考虑分布式测试架构； 3 ) 上述研究的基本思想都是基于控制部分的变迁覆盖，但一般缺少对于末状态的验证； 4 ) 在测试生成过程中，均没有考虑协议中的时间约束，因此这些方法不易应用于带有较蟛 复杂时间约束的协议中； 5 ) 缺乏比较实用的互操作性测试生成工具。 一 2 5 本章小结 本章介绍了互操作性测试的相关的背景知识。对互操作性测试的概念、特点、与一致性 测试的关系以及进行互操作性测试的意义进行了介绍。然后分别从互操作性测试框架，形式 化建模技术以及互操作性测试生成三个方面，对互操作性测试研究所采用的方法和取得的成 果以及存在的一些不足之处进行了说明。 9 基于c p n 的i s i s 路由协议互操作性测试的研究 3 1is is 协议概述 第3 章is ls 路由协议分析 i s i s 协议是一种得到广泛应用的、功能强大的路由选择协议。i s i s 协议最早是由国际 标准化组织i s o 定义的，用于o s i 七层网络模型中，来实现无连接的网络路由功能，其标准 化文档为i s o l 0 5 8 9 。由于i p 协议的应用远比o s i 开放系统应用广泛，发展迅猛，而i s i s 协 议由于其自身简单、快速收敛等特性得到了广泛的应用，因此，i e t f 工作组将i s i s 协议进 行了改进，使其能够同时运行在o s i 和t c p i p 两种网络环境中，其标准化文档为r f c l l 9 5 。 根据r f c l l 9 5 ，i s i s 协议既可以运行在独立的o s i 网络环境中，也可以运行在独立的i p 网 络环境中，还可以同时运行在o s i 、i p 双重网络环境中。 根据i s 0 1 0 5 8 9 和r f c l l 9 5 标准，i s i s 协议支持2 层分层体系。将一个域分成l e v e l l ( l 1 ) 层和l e v e l 2 ( l 2 ) 层。l 1 层内路由器形成l 1 层邻接关系，各个l 1 层之间通过l 2 层互联，l 2 层也称为骨干网。 由于i s i s 最初是为了o s i 系统设计的，因此很多术语都采用o s i 术语，与我们所熟悉 的t c p i p 术语有很大差别，为了使熟悉口环境的研究者能更方便的理解i s i s 协议，表3 1 给出了i s i s 协议术语对应的m 术语【1 9 1 ，本文接下来的研究当中，也将尽可能使用i p 术语。 袁3 1 l s 1 s 术语和术语对照表 t a b l e3 1i s - i sa n di pt e r ms y n o p s i st a b l e 术语缩写含义i p 术语 i n t e r m e d i a t es y s t e mi s 中间系统路由器 e n d s y s t e m e s 端系统主机 n e 似o r ks e r v i c ea c c s e ep o i n tn s a p网络服务接入点网络层地址 p r o t o c o ld a t au n i tp d u 协议数据单元i p 包( 相当于) l i n ks t a t ep d ul s p 链路状态数据单元路由选择信息通告 d e s i g n a t e di n t e r m e d i a t es y s t e m d l s 指派中间系统指派路由器( d r ) l e v e l2l 2 第2 层区域0 l e v e l1 l l 第l 层区域0 以外的区域 a r e a区域 区域 i o 在介绍i s i s 协议工作原理之前，需要先了解i s i s 数据包的类型和格式。根据i s 0 10 5 8 9 和r f c l l 9 5 标准，i s i s 协议数据包分为三大类，共9 种。表3 2 列出了i s i s 协议数据包的 名称和类型代码。 表3 2i s i s 协议数据包类型 t a b l e3 2t y p e so fl s i sp r o t o c o ld a t ap a c k e t l a nl i 层h e l l o 数据包 p d u 类型1 5 h e l l o 数据包( h e l l op d u )l a n l 2 层h e l l o 数据包p d u 类型1 6 点剑点h e l l o 数据包p d u 类型1 7 l l 层链路状态数据包p d u 类型1 8 链路状态数据包( l s p ) l 2 层链路状态数据包p d u 类型2 0 l 1 层完全序列号数据包p d u 类型2 4 l 2 层完全序