（交通信息工程及控制专业论文）基于EFSM的CBTC通信协议一致性测试的研究.pdf

中文摘要 摘要：在基于通信的列车运行控铝l j ( c o m m u n i c a t i o n s - b a s e dt r a i nc o n t r o l ，c b t c ) 系统 中，安全通信协议是各子系统间可靠的数据通信的保证，也是整个系统安全的基 础。自主开发的c b t c 通信协议已通过安全分析及验证，能够满足c b t c 系统的 要求。为了保证网络中各实体间能够正确、可靠地进行通信，必须根据协议规范 进行协议一致性测试，因而针对c b t c 系统通信协议的一致性测试也成为通信协 议测试的研究重点。 本文在研究c b t c 系统通信协议的相关文档和规范基础上，深入研究了当前 一致性测试技术的不同理论方法，结合c b t c 通信协议的特点，采用扩展有限状 态机( e x t e n d e df i n i t es t a t em a c h i n e ，e f s m ) 建模方法和u i o r ( e x t e n d e du n i q u e i n p u t o u t p u ts e q u e n c e s ) 算法对c b t c 系统通信协议的一致性测试进行了研究。 本文首先详细介绍了c b t c 系统通信协议的规范，其中包括协议的需求分析、 外部接口、相关安全防护措施，以及通信协议的基本原理等；根据e f s m 的建模 方法及c b t c 系统通信协议的特点，建立了基于e f s m 的c b t c 通信协议模型； 详细分析了f s m 与e f s m 模型一致性测试的序列生成算法，根据通信协议的特点 及需求，提出了基于e f s m 模型和u i o e 算法的c b t c 通信协议测试序列生成算法， 并生成c b t c 系统通信协议的一致性测试序列；最后按照生成的通信协议一致性 测试序列，构建了仿真测试平台，对c b t c 通信协议被测实现进行一致性测试， 并对测试结果进行了分析，一致性判决表明协议实现的被测部分达到了协议规范 的需求。 关键词：c b t c 通信协议；协议一致性测试；被测协议实现；扩展有限状态机； u i o s 序列； 分类号：t p 3 9 3 a bs t r a c t a b s i r a c i ： i nt h ec o m m u n i c a t i o n s - b a s e dt r a i nc o n t r o l ( c b t c ) s y s t e m ，as a f e t yc o m m u n i c a t i o n p r o t o c o li s n o to n l yt h eg u a r a n t e eo fr e l i a b l ed a t ac o m m u n i c a t i o nb e t w e e ne v e r y s u b s y s t e m ，b u ta l s ot h ef o u n d a t i o no ft h ew h o l es y s t e m ss a f e t y as e l f - c o n t a i n e d c o m m u n i c a t i o np r o t o c o lo fc b t cs y s t e mw h i c hc a nm e e tt h er e q u i r e m e n t sh a sb e e n d e s i g n e da n dp a s s e dt h r o u g hs a f e t ya n a l y s i sa n dv e r i f i c a t i o n t om a k es u r et h a tt h e s e d e v i c e si nn e t w o r kc a nc o m m u n i c a t ew i t he a c ho t h e r sc o r r e c t l y , w em u s tp e r f o r m c o n f o r m a n c et e s to ne a c hc o m p o n e n ta c c o r d i n gt ot h e i rs p e c i f i c a t i o n s t h e r e f o r e , t h e c o n f o r m a n c et e s to fc b t cc o m m u n i c a t i o np r o t o c o lh a sb e c o m et h ef o c u so fr e s e a r c ho f c o m m u n i c a t i o np r o t o c o lt e s t i n g i nt h i sp a p e r , w i t hc b t cc o m m u n i c a t i o np r o t o c o ls t a n d a r d sa n ds p e c i f i c a t i o n s ，l o t s o fc o n f o r m a n c et e s t i n gt h e o r i e sa n dt e c h n o l o g i e sh a v e b e e ns t u d i e d ，a n de f s m m o d e l i n ga n du i o sa l g o r i t h mh a v eb e e na p p l i e d o nt h ec b t cc o m m u n i c a t i o n p r o t o c o la c c o r d i n gt oi t sc h a r a c t e r i s t i c i nt h ep a p e r , f i r s t l y , c b t cc o m m u n i c a t i o np r o t o c o ls p e c i f i c a t i o n sw e r ee x p a t i a t e d ， i n c l u d i n gr e q u i r e m e n ta n a l y s i s ，e x t e r n a li n t e r f a c e ，r e l a t e ds a f e t yd e f e n c e s ，a n db a s i c p r i n c i p l e so fc b t cc o m m u n i c a t i o np r o t o c 0 1 s e c o n d l y , c b t cc o m m u n i c a t i o np r o t o c o l m o d e lw a se s t a b l i s h e du s i n gf o r m a lm o d e l i n gm e t h o db a s e do ne f s m ( e x t e n d e df i n i t e s t a t em a c h i n e ) a c c o r d i n gt ot h ec h a r a c t e r i s t i co fc b t cc o m m u n i c a t i o np r o t o c 0 1 t h e n ， v a r i o u st e s ts e q u e n c eg e n e r a t i n ga l g o r i t h mo ff s ma n de f s mm o d e lh a v eb e e n d e s c r i b e dp a r t i c u l a r l y , a n dat e s t s e q u e n c eg e n e r a t i n ga l g o r i t h m o fc b t c c o m m u n i c a t i o np r o t o c o lh a v eb e e np r o p o s e db a s e do ne f s mm o d e l l i n ga n d u i o s a l g o r i t h m t h ec b t cc o m m u n i c a t i o np r o t o c o lc o n f o r m a n c et e s ts e q u e n c eh a sb e e n g e n e r a t e du s i n gu i o ra l g o r i t h m a t l a s t ，as i m u l a t i o nt e s t p l a t f o r mh a sb e e n e s t a b l i s h e da n dt h ec b t cc o m m u n i c a t i o np r o t o c o lc o n f o r m a n c et e s th a sb e e n p e r f o r m e du s i n gt e s ts e q u e n c eg e n e r a t i n ga c c o r d i n gt ou i o ra l g o r i t h m t h r o u g ht h e a n a l y s i so ft e s tr e s u l t ，t h ec o n f o r m a n c ea d j u d g e m e n th a si n d i c a t e dt h a tt h el u tc a n m e e tt h er e q u i r e m e n t so fc b t cc o m m u n i c a t i o np r o t o c o ls p e c i f i c a t i o n k e y w o r d s ：c b t cc o m m u n i c a t i o np r o t o c o l ；p r o t o c o lc o n f o r m a n c et e s t i n g ； i m p l e m e n t a t i o nu n d e rt e s t ( i u t ) ；e f s m ；u i o r c l 。a s s n：sequencesot p 3 9 3 图索引 图1c b t c 系统组成框图3 图2 开放空间无线c b t c 车地通信系统构成4 图3e u r o r a d i o 系统结构6 图4 协议一致性测试过程8 图5 开放空间传输系统1 3 图6 发送接收处理1 4 图7c b t c 安全通信协议所在层次结构。1 4 图8c b t c 通信协议外部接口l5 图9 接口( 3 ) 的信息帧格式1 6 图1 0 通信链路建立过程2 3 图11 通信链路终止过程2 4 图1 2f s m 的有向图2 7 图1 3 正常建链过程中序列号的产生和变化2 9 图1 4 发起方没有收到跟随方发来的数据时序列号的变化情况3 0 图1 5 建立链路连接阶段超时3 l 图1 6 链路保持阶段的超时3 2 图1 7 发起方e f s m 模型3 3 图1 8 跟随方e f s m 模型3 4 图1 9 发起方的部分n a 树4 8 图2 0 跟随方的部分n a 树4 9 图2 l 协议一致性测试平台5 2 图2 2v c 下的测试结果( 第1 周期) 6 0 图2 3v c 下的测试结果( 第1 7 周期) 6 0 图2 4v x w o r k s 下的测试结果( 第1 - 6 周期) 6 1 图2 5v x w o r k s 下的测试结果( 第7 、1 7 周期、第1 8 2 4 周期) 6 2 表索引 表1 接口( 1 ) 功能1 5 表2 接口( 2 ) 功能。16 表3 通信发起方状态定义1 9 表4 通信跟随方状态定义2 0 表5 事件定义2 0 表6 活动定义2 0 表7 通信发起方状态转换表2 1 表8 通信跟随方状态转换表21 表9f s m 的二维动态数组，4 0 表1 0f s m 的各个状态的u i o 序列4 0 表1 1 发起方不可区分变迁集4 7 表1 2 跟随方不可区分变迁集4 7 表1 3 发起方的u i o e 序列及转换序列4 9 表1 4 跟随方的u i o e 序列及转换序列5 0 表1 5 发起方单条变迁测试清单5 3 表1 6 跟随方单条变迁测试清单5 6 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 弛精丫一名：如弋 签字日期：鲫黔6 月厂日 签字日期：d 8 年月c 。日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位做储躲月新签期期：渺孑年6 即日 7 1 致谢 本文是在导师李开成副教授的悉心指导下完成的。在短暂的研究生学习期间， 除了我自己的努力和付出之外，更多的是得到了交大的多位老师、同学、师兄师 姐及家人的关心与支持。尤其使我难忘的是我的导师李开成副教授。 在攻读硕士学位期间，李开成副教授对我的学业倾注了大量的心血。他以严 谨的治学态度，精湛的学术水平，渊博的专业知识和宽厚的待人品格，对我的学 习给予了悉心指导和帮助，使我受益匪浅并圆满完成学业。无论是学术上还是做 人上，李老师都为我做出了表率。正所谓教书加育人，而我则更看重后者。李老 师留给我的不仅是知识，更重要的是高尚的品格和无私奉献的精神。我的论文从 选题到实验直到整个论文的的修改，都渗透着李老师的指点和汗水。这种奉献精 神将永远影响我今后的工作、学习和生活。此时，我发自内心的道一声感谢! 在这里，我还要感谢轨道交通控制与安全国家重点实验室的唐涛教授、马连 川副教授、郜春海副教授、王海峰副教授指导我参与实验室的科研工作，研究生 期间使我的科研能力得到了很大的提高。感谢张建明、赵波波、黄友能和袁磊老 师对我的悉心指导。 特别感谢关心帮助我的师姐师兄牛儒、孙琳、陈树泉、刘朔、陆启进以及师 妹师弟李雁、单振字。还有我的同学谢雨飞、张岩、戚瑶、张亦南、杨旭文、黄 勃、袁彬彬、王伟、王春军、王呈等。在此向他们表达我的感激之情。 最后，我更要感谢远在长春的父母，您们是女儿的支撑，是女儿的后盾。感 谢父亲为我树立了良好的榜样，感谢重病卧床的母亲对我生活点滴的关怀呵护， 使我在人生的道路上一直保持乐观向上阳光般的心态和前进的动力。还有所有关 爱我的亲人们，有了你们的支持和鼓励，使我的人生道路充满温馨与快乐。 最后，感谢在交大的六年来所有曾经关心我、帮助我的老师、同学和朋友。 1 综述 基于通信的列车运行控制系统( c o m m u n i c a t i o n s - b a s e dt r a i nc o n t r o l ，简称 c b t c ) 技术发源于欧洲连续式列车控制系统，经过多年的发展，取得了长足的进 步【l 】。系统独立于轨道电路，采用高精度的列车定位和连续、高速、双向的数据通 信，通过车载和地面安全设备实现对列车的控制，现已成为列车控制系统发展的 方向，可满足铁路运输智能化、信息化和网络化的发展需要。 在消化吸收国外先进技术的同时，我国正在研究新一代符合我国国情的基于 通信的c b t c 列车控制系统。c b t c 是防护安全的复杂系统，各子系统问必须安 全可靠的通信，并且由于整个c b t c 系统应用两种通信网络( 有线、无线) ，因此 需要一个可靠、完备、统一的通信协议来保证数据传输的安全，保证各个通信对 象( 车载设备、地面设备) 之间正常的进行数据交互，进而才能保证整个系统的 安全等级的要求【2 】。 目前的网络协议多是以自然语言描述的文本【3 】。实现者对于协议文本的不同理 解和可选的协议属性以及实现过程中的非形式化因素都会导致不同的协议实现， 有时甚至是错误的协议实现。同一协议的不同实现还存在着性能差别。在这种情 况下，需要一种有效的方法对协议实现进行评价，这就是“协议测试 。在协议测 试中，又以协议的一致性测试为最重要的部分。一致性测试是指对被测实现 ( i m p l e m e n t a t i o nu n d e rt e s t ，i u t ) 进行的细致、系统的试验，以确定该实现是否 完全符合协议规范中的标准。 对c b t c 系统的通信协议进行协议一致性测试是十分必要的。目前国内的 c b t c 系统尚不成熟，在开发试验阶段，对该系统及其各子系统进行周密、详尽的 安全评估与验证，性能评价及系统级测试是不可或缺的。对于c b t c 中的通信协 议来说，由于其在该系统中起到至关重要的作用，而且是以欧洲列车控制系统 ( e u r o p e a nt r a i nc o n t r o ls y s t e m ，e t c s ) 的通信协议为参考，将其思想与实际需 求相结合，加以改善设计出来的。这就需要对c b t c 的通信协议的实现进行一致 性测试。 本章将简述自主开发的c b t c 系统基本原理、开放空间无线c b t c 系统车地 通信系统、c b t c 系统通信协议、以及列车控制系统通信协议国内外发展现状；还 将介绍协议一致性测试技术的相关理论与发展；最后介绍论文的主要工作和结构 安排。 j 匕塞交通太堂亟堂僮i 金塞绽述 1 1研究背景 1 1 1c b t c 系统概述 1 9 9 9 年，电气和电子工程师协会轨道交通运输车辆接口委员会( i e e er a i l t r a n s i tv e h i c l ei n t e r f a c es t a n d a r d sc o m m i t t e e ，i e e er 1 v l s c ) 制定并颁布了c b t c 技术标准i e e es t d1 4 7 4 1 1 9 9 9 ( ( i e e e 基于通信列车控制的性能和功能要求( 第 一版) 。该标准详细定义了c b t c 系统的功能，并规定了c b t c 系统的列车运行 间隔、安全性和可用性等技术指标【4 】。2 0 0 3 年1 2 月，i e e e 为c b t c 制订了第二 份标准i e e es t d1 4 7 4 2 2 0 0 3 ，建立了c b t c 对用户接口的要求。 i e e e 将c b t c 定义为：利用高精度的列车定位( 不依赖于轨道电路) ，双向 连续、大容量的车一地数据通信，车载、地面的安全功能处理器实现的一种连续 自动列车控制系统p 】。c b t c 系统是利用列车和地面间的双向数据通信设备，使地 面信号设备可以得到每一列车连续的位置信息，并据此计算出每一列车的运行授 权，动态更新并发送到列车，列车根据接收到的运行授权和自身的运行状态，计 算出列车运行的速度曲线，实现列车的安全防护。相比以前的信号系统制式，c b t c 系统更有利于线路通过能力的充分发挥，可以让列车运行获得更短的间隔。 目前，全球正在建设和已经签署合同的无线c b t c 线路已达2 0 多条，目前国 外开通运营的有拉斯维加斯单轨线、纽约的n y c t 、德国纽伦堡的r u b i n 、巴黎 地铁1 4 号线和新加坡东北线等1 6 】，国内的c b t c 线路包括香港地铁迪斯尼乐园线、 广州地铁4 号线、北京地铁4 号线、北京地铁1 0 号线、沈阳地铁等【7 】。其中正在 建设的北京地铁1 0 号线是北京轨道交通中首条使用c b t c 系统的线路。 通常c b t c 系统包括地面设备、车载设备、车地双向的信息传输系统等( 如 图1 ) 。地面设备包括区域控制器( z o n ec o n t r o l l e r ，z c ) 、计算机联锁( c o m p u t e r i n t e r l o c k i n g ，c 1 ) 、列车自动监督( a u t o m a t i ct r a i ns u p e r v i s i o n ，a t s ) 、数据库存 储单元( d a t a b a s es t o r a g eu n i t ，d s u ) 以及其他系统设备。车载设备主要包括车 载控制器( v c 临d eo nb o a r dc o n t r o l l e r ，v o b c ) 、测速定位设备以及车载天线等设 备。 2 图1c b t c 系统组成框图 h g u r e1g 饥e r a ls t r u c t u r eo f c b t cs y s t e m c b t c 系统从根本上将基于轨道电路的单向信息传输，改变为基于无线的双 向、连续、大容量信息传输，它的特点可以总结为以下几点f 4 】： 1 大容量连续双向车地通信； 2 地面设备及车载设备均采用安全计算机实时处理列车状态、控制命令，实 现连续的间隔控制、进路控制、速度防护、自动驾驶等； 3 高精度列车定位； 4 列车运行控制灵活、高精度，可实现移动闭塞； 5 设备集成度高，可减少地面设备，系统结构简单，并改善可靠性和可维修 性，减少全寿命周期成本； 6 c b t c 信息可以叠加在既有信号系统上，便于既有线改造，可实现城市轨 道交通的互连互通。 1 1 2开放空间无线c b t c 系统车地通信系统 开放空间无线c b t c 车地通信系统是由轨旁有线、车载通信单元和无线三部 分组成的数据通信系统【8 】如图2 所示。 3 8 0 2 1 1 车辆 圈 图2 开放空间无线c b t c 车地通信系统构成 f i g u r e2o p e ns p a c ew i r e l e s sc b t ct r a i n g r o u n dc o m m u n i c a t i o n ss y s t e mc o n s t i t u t i o n ( 1 ) 有线网络 有线部分应用i e e e 8 0 2 3 以太网标准，由接入网和骨干网两部分组成。 轨旁无线接入点( a p ) 和列车进行双向通信，并通过多模光纤与接入交换机 相连，组成接入网。轨旁a p 包括一个或两个完全冗余的无线单元，并协同工作。 每个a p 通过光纤以太网，分别连接到相应的接入交换机。每个接入交换机直接与 其所属的骨干交换机连接，从而接入到骨干网。 骨干网是冗余的高速单模光纤以太网，它由1 0 0 m b p s 的网络交换机构成。骨 干网采用了双向自愈的环形拓扑结构。骨干交换机位于设备集中站，所有轨旁设 备都通过一对冗余端口接入到骨干交换机。为满足系统要求的安全性和可靠性， 有线网络应用两条环网结构的有线路径，采用冗余的电子设备、冗余的入网路径、 冗余的环网结构。 ( 2 ) 车载通信单元 列车上的无线系统包括两个完全冗余的车载通信单元，它们是轨旁a p 的通信 客户端，分别安装在车头和车尾的车载设备机架内。车载通信单元包括两个冗余 的无线单元，它们之间协同工作。每个无线单元都与两个一组的车载天线相连， 提高了通信稳定性。前后端驾驶室列车通信单元的c p u 通过点对点以太网连接通 信。每个c p u 与车载控制单元通过电气机架内的t c p i p 以太网线连接。 ( 3 ) 无线网络 无线网络主要由标准的无线局域网商业部件组成，应用w l a n 技术，遵循 i e e e 8 0 2 1 1 无线局域网标准。i e e e8 0 2 1 l x 系列是国际电气和电子工程师协会制定 的通用无线局域网标准。在实际应用中，为满足系统安全性和可靠性要求，利用 a p 的无线重叠覆盖和冗余的车载无线设备，可以形成四条单独的无线路径，只有 四条单独的无线通道同时失效或者阻塞，才会导致通信中断。 4 苗 1 1 3c b t c 系统通信协议 协议是通信网络和分布式系统中各种通信实体之间相互交换信息所必须遵守 的一组规则，在通信网络及系统的发展过程中，协议一直处于核心地位。 c b t c 系统最显著的特点是引入了通信子系统，建立车地之间连续、双向、高 速的通信，使系统的主体c b t c 地面设备和受控对象列车紧密地联结在一起。因 此，“车地通信 是c b t c 系统的基础，是整个系统的支柱之一，也是关键技术之 一。可见，在这样一个基于无线数据通信的列控系统中，安全的地车数据通信协 议是保证c b t c 系统安全的重要组成部分，在整个系统中有着至关重要的作用。 当前我国c t c s 技术标准正在制定过程中，对于协议方面的规范并不成熟。 因此吸收和借鉴国外先进技术，对我国c t c s 的发展是很重要的【2 1 。同时，我国轨 道交通与欧洲的起点、技术基础、标准内涵、实施策略、发展目标等方面有所不 同，因此不能照搬欧洲的标准，而应在参考的基础上加以创新【9 】。 c b t c 通信协议具备的主要作用为： 1 能够利用合理正确的防护机制来保证信息实时性； 2 能够利用错误侦测数据传输协议来保证信息的安全性； 3 具有清晰的分层次的系统结构； 4 具有模块化和可移植性； 5 将上层的信息在双冗余总线上传输。 c b t c 通信协议是基于开放式的传输系统，因此势必存在一些未知的危险因素 睇j 。这些危险与应用功能或网络特征功能并无关系，例如信息的重复、删除、乱序、 损坏、延时和伪装等等。为了保证信息传输的安全性和可靠性，采用数据传输系 统已有的一些成熟的技术，为自主开发的控制和防护系统所用。 1 1 4列控系统通信协议国内外发展现状 国外研究c b t c 的时间较早，技术发展也比较快，典型的系统有：北美的a t c s 、 欧洲的e t c s 、日本的c a r a t 、德国的l z b 等。 e t c s 是一种列车运行控制系统技术规范，解决了欧洲各国信号制式互不兼容 的问题，保证高速列车在欧洲铁路网内互通运行。其通信协议有以下特点： 1 采用了分层次的结构； 2 采用单时间戳来判断信息时效性； 3 采用错误侦测数据传输协议来保证连接的安全： 4 将上层的信息在两条冗余总线上传输。 5 目前，欧洲铁路运输管理系统e r t m s 为高速铁路线定义了一批规范，传统的 信号系统被无线信号所代替，列车由地面设备通过无线信号来传输移动授权信息 进行管理。e t c s 第2 级和第3 级规定了以g s m r 数字无线通信系统作为列车控 制信息及其相关信息的传输平台，因为g s m 本身不能确保数据传输的安全性，因 此，e r t m s 制定了安全协议e u r o r a d i o ，其结构如图3 所示【1 0 1 。 安全相关设备安全相关设备 g s mp l m n i s d np s i n (或) 、 图3e u r o r a d i o 系统结构 f i g u r e3e u r o r a d i os y s t e ms t r u c t u r e 从其结构中可以看出，在e t c s 车载和轨旁终端设备的安全应用与通信功能 之间加入安全相关传输层，它通过一个或多个安全层接入点，以安全原语的方式， 与安全应用进行通信。 安全传输层要确保只能在合法的用户之间建立一个安全的链接，同时，在这 个安全链接存在的情况下，还要确保安全信息的安全传输。e u r o r a d i o 规范也 是根据e n 5 0 1 5 9 2 安全标准制定的，并且已经被a n s a l d os e g n a l a m e n t of e r r o v i a r i o 利用u m l 状态图进行了形式化分析，并验证其为安全通信协 ! ；【1 1 l 。 我国对于c b t c 系统的研究还处在起步阶段，至今还没有成熟的具有自主知 识产权的系统。相应的，c b t c 系统的通信协议也在进一步的开发与研究中。 1 2协议一致性测试技术 1 2 1协议测试 ( 1 ) 协议测试概述 协议测试是协议工程学的一个重要分支，是从软件测试的基础上发展而来的 一种黑盒功能测试，它依据协议的描述，对协议实现的外部可观察行为( 协议实 6 现与周围环境的相互作用) 进行测试，而不涉及协议实现的内部结构【1 2 1 。 协议测试通过实验来对被测协议实现( i u t ) 的行为特性进行测量，是一个试 图通过实验找出系统错误的过程。对一个系统进行无穷尽的测试是不现实的，所 以测试并不能保证协议实现的完全正确性，即测试只能表明“存在错误 ，而不能 证明“不存在错误 ，这是协议测试的基本出发点。 协议模糊性和二义性问题的解决，以及协议实现中潜在问题的发现，一方面 要靠协议验证和形式化描述理论和技术的发展，另一方面，要依靠一致性、互操 作性及性能测试等各种协议测试技术的完善。随着开放型异构网络的迅猛发展， 协议测试理论和技术的研究越来越重要，己经成为国际上网络研究的热点之一。 ( 2 ) 协议测试内容 协议测试主要研究内容包括测试组织、测试方法、测试生成、测试表示、测 试管理、测试执行和判决及测试结果分析等多个方面f 1 2 】： 测试组织主要是针对整个协议测试过程进行框架性的研究，明确测试过程 中各个阶段所应完成的功能； 测试方法则是研究在被测系统提供不同的可访问程度时，组成测试系统的 多个测试器相对于被测系统的配置方法； 测试生成主要关注于如何从协议标准的描述中获得进行协议测试所需要 的测试用例； 测试表示的目的是寻找一种合适的语言或公式，从而能以简洁、通用和结 构化的方式表达协议测试所需要的测试用例； 测试管理的研究对象是如何管理好由众多测试用例组成的庞大测试集，并 依据实际被测系统的信息对测试集进行选择； 测试执行和判决是测试过程中的重要阶段，如何解释测试用例的涵义以及 如何作出测试判决是它的研究内容，同时也是构造测试系统的理论基础； 测试结果分析是协议测试过程的最后一个阶段，如何从测试结果中生成测 试报告并得出对被测协议实现的结论，是这一阶段的研究目标。 ( 3 ) 协议测试分类 协议测试主要有三种u z j ：一致性测试、互操作性测试和性能测试。 协议标准对协议实现所应具有的特定行为做出了规定，对具体的协议实现与 相应协议标准的一致性关系进行检验的过程，就是协议的一致性测试。一致性测 试是保证协议实现正常工作的前提，是各类协议测试工作的基础。 单纯对一个协议实现进行一致性测试，并不能确保不同协议实现之间通信的 成功，还需要将协议实现放在一个实际的通信网络环境中进行测试。在这种测试 中，主要检测一个协议实现与其它系统之间是否能够进行成功可靠的通信交互， 7 因此称为互操作性测试。对于一个新的协议实现来说，与典型的、主流的协议实 现的互操作测试是非常重要的。 性能测试就是测定协议实现的性能特性，如吞吐量、响应时间、传输延迟等， 并以此对系统的性能做出评价。 一致性测试和互操作性测试都是功能测试，而性能测试的目的是测试协议实 现的性能参数，并根据这些参数对协议实现的性能做出评价。此外，一致性测试 和性能测试的测试对象都是一个，而互操作性测试的测试对象则是多个协议实现。 三种测试之间同样是有联系的，一致性测试是其它两种测试的基础，只有协 议实现满足一致性需求，对它进行互操作性测试和性能测试才更有意义。而性能 测试的结果对互操作性测试也有影响，性能匹配的协议实现之间才能更好地互操 作。 1 2 2协议一致性测试 一致性测试的目的在于验证协议实现与相应的协议标准或规范的一致性，它 只关心协议实现呈现于外部的性能。作为各项协议测试工作的前提和基础，一致 性测试始终是协议测试领域研究的重点。 一致性测试过程主要分为四步【1 3 1 ，如图4 所示。 图4 协议一致性测试过程 f i g u r e4p r o t o c o lc o n f o r m a n c et e s t i n gp r o c e s s 测试生成，即从协议标准产生抽象测试集。之所以称为“抽象测试集 是 因为它是独立于所有的协议实现的，抽象测试集由多个用于不同测试目的 的测试序列组成； 8 测试实现，即由抽象测试集产生可执行的测试序列集。抽象测试集中的抽 象测试序列被转变为在个实际的测试设备或测试系统上可执行的测试 用例。这一阶段需要考虑测试环境与被测协议实现的具体情况。 测试执行，即将可执行的测试序列集施加到被测网络协议上，并对i u t 的外部响应行为进行观察，记录各条测试序列的执行结果。 测试判决，即对测试执行的结果进行验证和分析，得到一个有关砌t 相对 于协议标准一致性的判决，给出协议一致性测试报告。 一致性测试首先需要根据协议规范建立起协议原型，然后根据原型，生成相 应的测试序列集，针对于具体的实现，选择合适的测试方法，将生成的测试集转 化为可执行的测试用例，应用到被测协议实现上，观察激励反映，得到验证结果。 1 2 3协议与状态机 有限状态机( f i n i t es t a t em a c h i n e ，f s m ) ，是一种用来进行对象行为建模的工 具，其作用主要是描述对象在它的生命周期内所经历的状态序列，以及如何响应 来自外界的各种事件。一般说来，对象在其生命期内是不可能完全孤立的，它必 须通过发送消息来影响其它对象，或者通过接受消息来改变自身。在大多数情况 下，这些消息都只不过是些简单的、同步的方法调用而已。 在描述有限状态机时，状态、事件、转换和动作是几个基本概念。 状态指的是对象在其生命周期中的一种状况，处于某个特定状态中的对象 必然会满足某些条件、执行某些动作或者是等待某些事件。 事件指的是在时间和空间上占有一定位置，并且对状态机来讲是有意义的 那些事情。事件通常会引起状态的变迁，促使状态机从一种状态切换到另 一种状态。 转换指的是两个状态之间的关系，表明对象将在第一个状态中执行一定的 动作，并将在某个事件发生同时某个特定条件满足时进入第二个状态。 动作指的是状态机中可以执行的那些原子操作，所谓原子操作指的是它们 在运行的过程中不能被其他消息所中断，必须一直执行下去。 状态机的应用范围很广，诸如时序电路设计、词汇分析等系统。近年来，随 着通信领域的迅猛发展，状态机又被广泛引入到协议建模及测试的过程中【1 2 】。 将状态机理论应用到测试领域的研究最早可以追溯到2 0 世纪5 0 年代，m o o r e 在g e d a n k e n ee x p e r i m e n t s 一文中对状态机测试的问题进行了阐述。20 世纪6 0 年 代及7 0 年代初，由于自动机理论的发展及时序电路测试的需要，对于测试理论的 研究活动逐渐开展起来。之后该领域经历了一段时间的沉寂，随着近年来通信科 9 学的迅猛发展，状态机模型开始被广泛的应用于协议建模，对于通信协议的测试 又促使状态机测试理论重新成为当前较为活跃的研究领域之一。 通信协议被认为是由若干个事件驱动的实体组成的，这些实体间可以通过消 息传送进行相互通信，每个实体的特性可以描述为一系列响应外部和内部事件的 动作( 或者状态转换) ，可以用状态机模型来加以描述。 网络通信协议或其具体实现往往具有如下的特性。 ( 1 ) 协议的复位能力 协议的复位能力是指无论系统处于那种状态，如果收到复位信息，就会转移 到特定的初始状态。为了保证系统的正常运行，通信协议一般均具有复位能力【1 2 】。 因此，协议的状态机模型一般是具有强连通性的。 ( 2 ) 协议的半描述性 协议中通常会存在大量状态和输入输出，如i e e e 2 0 2 2 逻辑链路控制协议中包 含1 4 个状态，4 8 个输入以及6 5 个输出【1 4 1 。然而，对于某一状态而言，并非每个 输入都会对其产生影响，这就是协议的半描述性。对应于状态机，它可以由半描 述的f s m 或e f s m 建模进行表示。现有的网络协议大多是半描述的【l 5 】 ( 3 ) 协议实现的确定性 对于一个具体产品而言，其功能往往是确定的。然而，为了满足不同情况的 需要，协议规范中常常存在着许多可选项，它允许协议实现者在这些可选项之间 进行选择，以实现特定的功能。因此，协议标准所允许的不确定性会在协议实现 过程中被消除，即对于某个具体的协议实现而言，其模型往往是确定性的。这也 使得利用有限状态机模型来生成协议一致性测试集成为了可能。 状态机在一致性测试中主要应用于协议建模和测试序列自动生成两个方面 【1 2 1 。在一致性测试过程中，通常采用的做法是利用有限状态机或扩展有限状态机 对协议进行建模，然后选用某种测试序列生成算法，对最短测试序列进行求解。 一般而言，协议描述分为控制和数据两部分。对于协议的控制部分，可由f s m 进行建模表示，它可以将协议内部各状态之间的变迁关系简洁明确的表述出来； 但是对于数据部分，f s m 的功能就显得较为有限，而增加了变量描述的扩展有限 状态机( e x t e n d e df i n i t es t a t em a c h i n e ，e f s m ) ，则很好地解决了这一问题。 1 2 4协议测试的发展 鉴于实际应用的需求和对协议测试认识的加深，在八十年代早期，欧洲的许 多研究机构开始在建立标准化的协议一致性测试活动方面进行合作，其目的是制 定一个在o s i 框架内进行协议一致性测试的指导标准1 2 】。最初的参与者包括法国 l o 巴黎的a d i 、德国的g m d 和英国的国家物理实验室n p l 。到1 9 8 4 年，又有更多 的来自欧洲和北美的研究人员加入到这一合作之中。这一项目的许多研究成果曾 在由i f i p 主办的协议描述、测试和验证会议p s t v 的年会上发表，它们包括：各 种测试结构、测试语言、各种测试方法的可行性、测试序列的自动生成等等，这 为后来协议一致性测试研究的深入开展奠定了基础。 2 0 世纪9 0 年代，国际标准化组织i s o 专门制定了一套国际化标准i s o i e c 9 6 4 6c t m f ，为协议的一致性测试提供了基本方法和框架。 目前的协议测试已经不仅仅是产品开发研制过程中一个简单的检测支持过 程，而是发展成为计算机网络技术的一个重要分支和协议工程学的一个重要组成 部分【3 】。对协议测试技术的研究将直接影响到计算机网络技术的进步和世界网络市 场的竞争与发展。所以很多国家都投入了大量的人力物力从事协议测试的研究工 作。例如：英国的国家物理实验室n p l 、法国国家通信研究中心、德国国家通信 研究局g m d 、美国国家标准化研究局、美国新罕布什尔大学互操作研究实验室、 清华大学计算机科学与技术系的网络和协议测试实验室和中科院计算所的网络测 试实验室等单位都在这个领域投入了大量的研究力量。 现有的一些测试方法都是针对特定实现，有许多的限制。这些专用的测试平 台没有兼容性，测试方法较单一，其他测试人员也难以用它们来进行扩展测试。 以i p v 6 测试为例，目前国内外的研究包括【3 】：1 9 9 8 年底东京大学、y d c 公司、 y o k o g a w a 公司发起组织了对i p v 6 进行侧试的t a h i 计划，采用p e a l 语言来描述口v 6 测试套并用解释执行方式执行测试例，在测试方法上并没有提出新的思想；美国 新罕布什尔大学的i o l 实验室对i p v 6 协议的一致性测试，采用自然语言来描述测 试套，覆盖测试并不是很完备；中科院计算所从1 9 9 9 年开始与n o k i a 公司合作设 计实现的v 6 p t s ，采用他们自行设计的测试套描述语言t s s ( t e s ts u i t e