（计算机应用技术专业论文）网络协议组合测试模型的研究与实现.pdf

南京邮电大学硕士研究生学位论文网络协议组合测试模型的研究与实现 摘要 随着网络技术和网络应用的发展，通信技术的发展也越来越迅速，通信协议也需要提 供更多的功能并越来越复杂。另外伴随网络应用的不断增加，通信协议也提供了扩展功能 来满足网络应用的发展，这就需要在不改变原有协议框架的前提下进行协议扩展。然而目 前协议一致性测试技术无法满足新的网络环境下的协议发展的要求。本文的主要目的就是 针对目前协议的复杂性和功能不断扩展的情况研究网络协议一致性测试问题。 协议组合是计算机网络中的一个传统研究课题，协议组合方法是一种重要的进行网络 协议设计和验证的方法。它将协议按照功能划分为多个不同的构件，依次实现各个协议构 件并将这些构件组合在一起最终达到实现复杂协议的目的。目前的协议组合思想主要用在 协议的设计和实现中，本文将组合协议的思想用于网络协议一致性测试中，提出了协议组 合一致性测试方法，建立了网络协议组合测试模型。网络协议组合测试模型符合协议规范 的构件化思想，方便一致性测试在原有协议构件测试的基础上生成测试序列。 文章在该模型的基础上，基于现有的协议规范所规定的协议框架，提出了s i p 组合测试 模型，这是协议组合测试模型在s i p 中的应用。在此基础上，运用了p r o m e l a 语言描述了 s i p 协议，采用工具s p i n 验证了s i p 组合测试模型的正确性。然后利用本文中提出的基于通 信有限状态机的一致性测试序列生成算法生成相应的测试序列。最后在l i n u x 操作系统上实 现了对开源的s i p 协议v o c a l 的一致性测试。 南京邮电大学硕士研究生学位论文 网络协议组合测试模型的研究与实现 a b s t r a c t w i t ht h ed e v e l o p m e n to fn e t w o r kt e c h n o l o g ya n da p p l i c a t i o n s ，t h ed e v e l o p m e n to f c o m m u n i c a t i o np r o t o c o li si n c r e a s i n g l yr a p i d l y c o m m u n i c a t i o np r o t o c o ln e e d st op r o v i d e m o r ea n dm o r ef u n c t i o n sa n db e c o m e sm o r ec o m p l e x w i t ht h ei n c r e a s i n gu s eo fn e t w o r k a p p l i c a t i o n s ，c o m m u n i c a t i o np r o t o c o la l s op r o v i d e se x p a n d e df u n c t i o nt om e e tt h ed e v e l o p m e n t o fn e t w o r l ia p p l i c a t i o n sw i t h o u tc h a n g i n gt h eo r i g i n a lp r o t o c o lf r a m e w o r k h o w e v e r ，t h e t e c h n o l o g yo f c u r r e n tp r o t o c o lc o n f o r m a n c et e s tc a l ln o tm e e tt h en e wr e q u i r e m e n t so ft h e d e v e l o p m e n to fn e t w o r kp r o t o c 0 1 t h em a i np u r p o s eo f t h i sp a p e ri st or e s e a r c ho nn e t w o r k p r o t o c o lc o n f o r m a n c et e s tt oa c c o m m o d a t ep r o t o c o lc o m p l e x i t ya n de v e r e x p a n d i n gf u n c t i o n s p r o t o c o lc o m p o s i t i o ni sat o p i co ft r a d i t i o n a lc o m p u t e rn e t w o r kr e s e a r c h p r o t o c o l c o m p o s i t i o ni sav e r yi m p o r t a n tm e t h o df o rt h ep r o t o c o ld e s i g na n dv e r i f i c a t i o n p r o t o c o li s d i v i d e di n t oan u m b e ro fc o m p o n e n t si na c c o r d a n c ew i t l lt h ef u n c t i o n a lp a r t i t i o n t h e ne v e r y c o m p o n e n ti si m p l e m e n t e ds e p a r a t e l y f i n a l l y ，t h ec o m p o n e n ti m p l e m e n t a t i o n sa r ep u tt o g e t h e r s ot h a tt h ei n i t i a lc o m p l e xp r o t o c o lc a nb ei m p l e m e n t e d t h et r a d i t i o n a la p p l i c a t i o no fp r o t o c o l c o m p o s i t i o ni si nt h ed e s i g na n di m p l e m e n t a t i o no ft h en e t w o r kp r o t o c 0 1 i nt h i sp a p e r , a c o m p o s e dt e s tm e t h o da n dc o m p o s i t i o nt e s tm o d e lo fn e t w o r kp r o t o c o li sp r o v i d e du s i n gt h e i d e a so fp r o t o c o lc o m p o s i t i o nf o rp r o t o c o lc o n f o r m a n c et e s t p r o t o c o lc o m p o s i t i o nt e s tm o d e l a c c o r d i n gt oc e r t a i nt h ep r o t o c o ls p e c i f i c a t i o nf a c i l i t a t et e s ts e q u e n c eg e n e r a t i o no nt h eb a s i so f t h eo r i g i n a lp r o t o c o la f t e rt h ef u n c t i o ne x t e n s i o n b yu s i n gt h ec o m p o s e dt e s tm o d e l ，t h i sp a p e rg i v e ss i pc o m p o s e dt e s tm o d e l b a s e do n t h ee x i s t i n gp r o t o c o ls p e c i f i c a t i o n s i pc o m p o s e dt e s tm o d e li sa na p p l i c a t i o no ft h e c o m p o s e dt e s tm o d e lo fn e t w o r kp r o t o c o lf o rt h es i p t h e nb a s e do nt h i sm o d e l ，t h i sp a p e r d e s c r i b e st h es i pu s i n gp r o m e l al a n g u a g e s p i nv e r i f i c a t i o n t o o li su s e dt ov e r i f yt h e c o r r e c t n e s so ft h em o d e l t h i sp a p e rg e n e r a t e st e s ts e q u e n c eu s i n gp r o p o s e da l g o r i t h mb a s e d c o m m u n i c a t i n gf i n i t es t a t em a c h i n e f i n a l l yac o n f o r m a n c et e s to fs i pi m p l e m e n t a t i o ni nt h e l i n u x ，v o c a l ，i sp e r f o r m e d 1 i 南京邮电大学硕士研究生学位论文缩略语 缩略语 s u t ( s y s t e mu n d e rt e s t ) ：被测协议系统 t m p ( t e s tm a n a g e m e n tp r o t o c 0 1 ) ：测试管理协议 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 ) ：抽象服务原语 t c p ( t e s tc o o r d i n a t i o np r o c e d u r e s ) ：测试协同过程 l t ( l o w e rt e s t e r ) ：下测试器 u t ( u p p e rt e s t e r ) ：上测试器 a t s ( a b s t r a c tt e s ts u i t e ) ：抽象测试集 t t c n ( t r e ea n dt a b u l a rc o m b i n e dn o t a t i o n ) ：树表结合符号 p c o ( p o i n to f c o n t r o la n do b s e r v a t i o n ) ：控制观测点 s i p ( s e s s i o ni n i t i a t i o np r o t o c 0 1 ) ：会话初始协议 u a ( u s e r a g e n t ) ：用户代理 u a c ( u s e r a g e n tc l i e n t ) ：用户代理客户端 u a s ( u s e r a g e n ts e r v e r ) ：用户代理服务器端 t u ( t r a n s a c t i o nu s e r ) ：事务用户 i o t s ( i n p u t - o u t p u tt r a n s i t i o ns y s t e m ) ：输入输出变迁系统 e 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 ) ：扩展有限状态机 c f s m ( c o m m u n i c a t i n gf i n i t es t a t em a c h i n e ) ：通信有限状态机 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 ) ：协议实现一致性声明 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 ) ：被测协议实现附加信息 s a p ( s e r v i c e a c c e s sp o i n t ) ：服务访问点 s d u ( s e r i v ed a t eu n i t ) ：服务数据单元 5 8 南京邮电大学硕士研究生学位论文 缩略语 p d u ( p a c k e td a t au n i t ) ：报文数据单元 o s i ( o p e ns y s t e mi n t e r a c t i v e ) ：开放系统互联模型 r t p ( r e a l - t i m et r a n s p o r tp r o t o c 0 1 ) ：实时传送协议 r t s p ( r e a l - t i m es t r e a m i n gp r o t o c 0 1 ) ：实时流传送协议 m e g a c o ( m e d i ag a t e w a yc o n t r o lp r o t o c 0 1 ) ：媒体网关控制协议 p s t n ( p u b l i cs w i t c h e dt e l e p h o n en e t w o r k ) ：公共交换电话网 r s ( r e d i r e c ts e r v e r ) ：重定向服务器 f s ( f e a t u r es e r v e r ) ：特征服务器 r s ( r e g i s t e rs e r v e r ) ：注册服务器 v o i p ( v o i c eo v e ri n t e r a c tp r o t o c 0 1 ) ：因特网电话 m t ( i m p l e m e n t a t i o n u n d e rt e s t ) ：被测协议实现 5 9 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：2 霉誓釜 日期：丝窆：竺：夕 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：2 赴导师签名：? 蟛日期：叫 南京邮电大学 硕士学位论文摘要 学科、专业：工学计算机应用技术 研究方向： 计算机网络与分布计算系统 作 题 2 0 0 4 级研究生李希合指导教师沈苏彬 目：网络协议组合测试模型的研究与实现 英文题目： r e s e a r c ha n di m p l e m e n t a t i o no ft h ec o m p o s e dt e s t m o d e lo fn e t w o r kp r o t o c o l 主题词： 协议组合会话发起协议协议一致性测试 通信有限状态机 k e y w o r d s ： p r o t o c o lc o m p o s i t i o n s e s s i o ni n i t i 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 c o m m u n i c a t i n gf i n i t es t a t em a c h i n e 课题来源：国家自然科学基金计划项目，项目编号：6 0 2 7 3 0 9 1 南京邮电大学硕士研究生学位论文第一章引言 1 引言 1 1 研究背景 计算机网络发展至今，已进入一个系统化工程化的时代。为了解决通信和分布式系统 中的通信问题，各计算机系统必须遵守一组规则。协议描述了两个或多个实体交互的句法、 语义和时序规则。为了使不同厂家的系统能够成功地进行通信，协议必须标准化。但协议 标准制订后还只是一个自然语言描述的文本，其产品化开发通常由不同的人员或组织进 行。如何系统地开发协议软件，确保根据同一标准实现的不同产品能可靠的进行通信，这 是协议工程中一个非常关键的问题。由于不同协议软件的开发者对协议标准理解可能不 同，实现过程又可能存在错误，使得产品的某些功能偏离标准，或者仅是标准的一个子集， 因此绝对忠实于协议标准的实现几乎不存在，这些与标准不一致的产品在联网时难以可靠 地通信。解决这一问题的办法就是对协议实现进行一致性测试( c o n f o r m a n c et e s t i n g ) 。 下一代网络( n g n ，n e x tg e n e r a t i o nn e t w o r k ) 是一种要求提供各种多媒体业务的宽 带网络，主要基于分组交换网络。s i p 是由i e t f 规范化的会话协议，可以满足下一代网 络环境下多方、多媒体的信令控制，提供一种更加容易扩展的架构，更适用于智能用户终 端。随着下一代网络业务的不断增加，各方的研究人员已经在原来s i p 基本协议的基础上， 提出了多项s i p 扩展来不断地丰富s i p 功能，从而满足网络业务增加的需要。s i p 功能的 增加同时也使s i p 协议变得越来越复杂。如何在s i p 功能不断增加的情况下进行一致性测 试也就成为一个需要研究的问题。 协议组合是计算机网络中的一个传统研究课题，协议组合方法是一种重要的进行网络 协议设计和验证的方法。使用组合协议方法进行协议的设计和验证产生的协议构件不仅易 于协议的设计和验证，还便于协议的重用及协议的扩展。根据下一代网络的开放性特点， 下一代网络协议需要有很好的扩展性。使用协议组合思想能很好的满足下一代网络协议的 这一要求。但是，目前的协议组合思想主要用在协议的设计中，如何将组合协议的思想用 于当前网络协议的测试是本文中要研究的问题。 为了方便满足网络业务增加和s i p 协议扩展，s i p 设计人员在规范中定义了分层结构， 其中划分了协议事务和事务用户，构件化的思想在协议规范中得到了体现。因此s i p 一致 性测试中需要采用构件化的思想来分析协议。本文的工作目标是，将协议组合的思想应用 于一致性测试中，对组合测试模型进行研究，并实现对s i p 的一致性测试。 南京邮电大学硕士研究生学位论文 第一章引言 1 2 相关工作 当前，协议一致性测试技术的研究重点仍然集中在测试序列的生成，而测试序列生成 技术的目标是生成检错能力最强，测试成本最小的测试序列。目前协议一致执行测试的主 要研究内容包括： 一致性测试序列优化技术研究。测试序列的成本由测试序列的长度和测试序列的总时 间来度量，目前的优化技术集中在研究如何减少测试序列的长度和验证序列的长度问题。 一致性测试序列检错能力优化技术研究。测试成本和检错能力是一致性测试序列生成 技术中互相矛盾的两个方面，当矛盾无法解决时，以检错能力为重。检错技术的研究主要 集中在提高对被测协议的覆盖度和生成检错能力更强的验证序列。 测试系统的实现。测试系统实现也是一项很重要的工作，一个测试系统需要将抽象的 测试用例转化为可执行的测试用例，并在实际的系统中进行测试。目前的测试系统研究集 中在测试系统的实现模型上。 协议组合是计算机网络中的一个传统研究课题，协议组合方法是一种重要的进行网络 协议设计和验证的方法。其主要的思想为： ( 1 ) 首先，将一个复杂的协议分解成一系列小的、简单的以及易于实现的子协议； ( 2 ) 接着，以协议构件( c o m p o n e n t ) 的形式来设计和验证实现第一步分解得到的子协议； ( 3 ) 最后，将实现好的子协议组合成复杂的、难于直接实现的协议。 协议组合思想不仅易于协议的设计和验证，还便于协议的重用及协议的扩展。所以本 文将协议组合的思想引入协议一致性测试中，协议的扩展部分都作为构件添加到原有的协 议中，成为对一种新的构件化模型的一致性测试。 1 3 论文的主要工作 目前研究的协议一致性测试的模型主要是基于有限状态机( f s m ) 矛i 扩展有限状态机 ( e f s m ) 的，还有一些是基于输入输出变迁系统( i o t 8 ) 。但是这些模型都是对协议中只存在 一个状态机条件下的一致性测试。而当协议中包含有多个状态机的情况则研究很少。本文 主要考虑协议包含有多个状态机的情况，将多个状态机抽象为通信有限状态机模型，基于 通信有限状态机研究一致性测试序列的生成问题，提出了基于通信有限状态机的测试序列 生成算法。并运用该算法生成了s i p 协议的一致性测试序列。 本文用协议组合的思想分析协议规范，简化了协议测试过程的复杂性，同时提高了协 2 南京邮电大学硕士研究生学位论文第一章引言 议测试模型的可扩展性。主要工作是研究协议组合测试模型，在实现测试时将其转化为通 信有限状态机模型，基于通信有限状态机模型生成一致性测试序列。并且实现了对模型的 验证，最后在l i n u x 操作系统中实现了一致性测试过程。 本文创新点有以下几点： ( 1 ) 用协议组合的思想分析协议规范，提出了协议组合一致性测试方法和组合测试模型； ( 2 ) 提出了基于通信有限状态机的一致性测试序列生成算法； ( 3 ) 在分析s i p 扩展功能的基础上，提出了基于s i p 协议规范的s i p 组合测试模型。 本文的主要工作有以下几点： ( 1 ) 用c 语言实现了基于通信有限状态机的一致性测试序列生成算法； ( 2 ) 分析了s i p 协议的基本规范和扩展规范，通过状态机表示了s i p 协议中的基本功能和 扩展功能； ： ( 3 ) 采用p r o m e l a 语言描述s i p 协议，并且在此基础上通过s p i n 工具验证通信有限状态 机模型； ( 4 ) 基于开源的协议系统v o c a l 实现对s i p 的一致性测试系统。 1 4 论文结构 本文主要分为六章，具体的划分如下： 第一章，论述了研究的背景，提出了要解决的问题，并给出了解决问题的步骤以及 要达到的目标，同时对一些和本文相关的工作进行了一些比较。 第二章，主要介绍一些背景知识。主要包括状态机的一般性理论、一致性测试方法 及其测试序列生成方法。 第三章，提出了协议组合一致性测试方法和组合测试模型，提出并实现了通信有限 状态机的测试序列生成算法，并对算法进行了分析。 第四章，对现有的s i p 协议的扩展做了分析，给出了s i p 组合测试模型，其中包括 了新的对话扩展部分和对话内部扩展部分。 第五章，论述了对s i p 组合测试模型的一致性测试，对s i p 组合测试模型进行了验 证，生成相应的测试序列，并设计了测试系统，对已经实现的s i p 协议进行一致性测试。 第六章，总结全文，给出本文的工作和应用价值，同时给出了对以后工作的展望。 南京邮电大学硕士研究生学位论文 第二章通信协议一致性测试的基本理论 2 通信协议一致性测试的基本理论 2 1 状态机的一般性理论 5 0 年代，m e a l y 和m o o r e 最早提出了状态机模型，状态机模型被广泛用在电路设计等方 面，在通信协议出现之后，状态机模型被用于协议测试中，因为很多协议中的状态变迁成 为协议的核心问题。 状态机以其简单、直观、可预测、易开发、易测试等特性，在协议一致性测试领域有 着广泛的使用。本节介绍一些状态机的一般性理论，首先给出有限状态机的定义。 2 1 1 基本的f s m 模型 定3 ( 2 1 有限状态机( f i n i t es t a t em a c h i n e ：f s m ) t 1 】 有限状态机模型由一个五元组来表示m = ( s ，i ，o ，正名) 。其中，s = sl ，s 。 是 一个有限状态集合， i = i i , - - - i 。) 是一个有限输入集合，o = o i c o ， 是一个有限输出集 合，万：s ijs 是状态变迁函数，五：s i 岭o 是输出函数。 有限状态机m 也可以被看成图g = ( v ，e ) 。顶点集合v = v i ，v n ) 是m 的状态集合， e = ( v j ，v k ；a b ) iv j ，v k v 表示m 中变迁的边集合，每一个边e j k = ( v j ，v k ；a b ) e 表 示一个从状态v j 到v k 在输入为a 输出为b 时的状态变迁。v j ，v k ，a b 分别叫做头节点， 尾节点和变迁的标记。 同样，有限状态机还可以表示为状态表，状态表的行表示每一个状态，列表示输入， 每一个表中的元素表示下一个状态和输出。 当使用有限状态机模型描述一个协议规范时，状态是协议实体能够停留的稳定条件， 输入是协议实体从外界接收到的报文激励或者内部产生的事件激励，输出是协议实体对外 晃的响应。 定义2 2 完全定义的状态机 m 是一个有限状态机m = ( s ，i ，0 ，艿，们，如果对于v s s ，i ，变迁函数万g ，i ) 和输出 函数a g ，i ) 都有定义，则称m 是完全定义的有限状态机，否则m 被称为非完全定义的有限状 态机。 4 南京邮电大学硕士研究生学位论文第二章通信协议一致性测试的基本理论 一般协议实体对应的状态机都是非完全定义的状态机，对于没有定义的变迁，可以假 设协议实体在此状态对这个输入没有输出，并且保持当前状态不改变，这些添加的变迁称 为非核心变迁，其他的称为核心变迁。 定义2 3 等价状态 m 是一个有限状态机m = ( s ，i ，o ，万，d ，如果存在状态s ies ，s ，es ，使得这两个状态 对于任意的输入序列都产生相同的输出序列，则称状态s 。和s j 等价。 定义2 4 最小化的状态机 m 是一个有限状态机m = ( s ，i ，0 ，万，旯) ，如果m 中不存在等价的状态，则称状态机m 是 最小化的状态机。 定义2 5 一个有限状态机中的两个状态s ；，j 是等价的，记为s ；兰j ，当且仅当对于任 意的输入序列，状态机从它们出发都产生相同的输出序列，否则称s ；和s ，是不等价的，记 为s i s ，。这个定义的形式化表述如下： v s i ，s s贝0 s i 三s 亡令v r ，2 ( s i ，) = l ( s j , ，) ( 2 1 ) v s i ，s ，s贝0 s i s c ，3 r ，兄( _ ，) a ( s ，) ( 2 2 ) 对于两个不相同有限状态机m l 和m 2 ，令s i 是m 1 中的状态，s i 是m 2 q h 的状态，则s i 和 s j 的等价性定义与定义2 5 相同。另外( 2 2 ) 式中的r 称为s i 和s j 的一个区分序列。 定义2 6 两个状态机m 1 和m 2 是等价的，当且仅当对于m 1 中的每个状态，存在m 2 中的 一个状态与它等价；同时对于m 2 中的每个状态也存在m 1 中的一个状态与它等价。形式化 表述如下： m 1 羞m 2 营( v s ，s u ，了s ，t 兰s j ) a ( v s f ，3 s ，s ，暑j ) ( 2 3 ) 由定义2 6 可以知道等价的状态机有相同的输入集和相同的输出集。 定义2 7 路径 m 是一个有限状态机m = ( s ，i ，0 ，万，五) ，对状态s ；es ，s ，es ，如果存在变迁序列 ，l ，2 ，乙，使得： ( 1 ) s i 为变迁t i 的头状态； ( 2 ) 对于2 k ，l ，转换t k 的头状态是转换t k 1 的尾状态。 南京邮电大学硕士研究生学位论文 第二章通信协议一致性测试的基本理论 ( 3 ) s i 为转换t 。的尾状态； 则称转换序列，：，乙是一条从s ；n s ；的路径。 定义2 8 强连通有限状态机 m 是一个有限状态机m = ( s ，i ，o ，万，旯) ，对任意状态s i s ，s ，s ，如果均存在从s i 到s i 的路径，则称m 是一个强连通的有限状态机。 定义2 9 非确定有限状态机 m 是一个有限状态机m = ( s ，i ，0 ，万，元) ，如果存在状态s s 和输) k i i ，使得变迁集合 中存在两个或者以上的变迁的头状态均为s ，输入均为i ，形式化的表示为，3 s s ，i ，使 得( i8 ( s ，i ) | 2 ) v ( ia ( s ，f ) | 2 ) ，则称m 为非确定的状态机，反之m 为确定的状态机。 可以将一个非确定的状态机转换为一个确定的状态机【2 6 1 ，所以本文中如未特别指明，一 般的状态机都是指确定的状态机。 2 1 2f s m 的一些扩展模型 f s m 并不能满足通信协议中的所有假设条件，通信协议中还有许多的数据部分无法体 现在有限状态机模型中，而借助于扩展的有限状态机( e f s m ) 可以更有效的进行基于数 据流的测试。下面对e f s m 的基本概念进行介绍。扩展的有限状态机( e f s m ) 在不同的研 究中对扩展部分的定义的形式是不一样的，但是原理基本相同，本文给出了【捌中的定义。 定义2 10 扩展有限状态机( 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 ) 一个扩展有限状态机m 为一个七元组m = ，其中： s 表示状态的集合，s 。s 表示初始状态； t 表示变迁的集合； v 表示环境变量的集合； p 表示作用于环境变量和输入输出参数的谓词的集合： a 表示作用于环境变量和输入输出参数的行为的集合。 在状态s ；下，对环境变量v 中所有变量的一个赋值，称为状态s ；的一个环境配置，记 为s i ( v ) 。变迁集合t 的每个元素是一个五元组t = ，其中s i s 称为变迁t 的 头状态，i s 和0 0 分别称为变迁的输入和输出，s ；s 称为转换t 的尾状态，p 表示执行 6 南京邮电大学硕士研究生学位论文第二章通信协议一致性测试的基本理论 转换t 时必须满足的条件，a 表示执行转换t 时的动作，只有转换条件p 为真值的情况下，转 换t 才可以执行。 当使用扩展有限状态机模型描述一个协议规范时，状态是协议实体能够停留的稳定条 件；输入是协议实体接收到的外界激励或者内部产生的事件激励( 可能包含一些输入参数) ； 输出是协议实体对外界的响应( 可能包含一些输出参数) ；变迁执行条件是关于输入参数和 当前环境变量的条件表达式；变迁执行动作包含对输出参数的设置，以及对环境变量的改 变。变迁t = 表示当协议实体处于状态s i 时，接收到外界输入激励或者内 部事件i ，如果在当前的环境配置s ；( y ) 下条件p 能够满足，则执行动作a 来修改环境变量， 设置输出参数，对外界产生响应o ( 包含输出参数) 并进入状态s ；。对于变迁 t s i ，s j ，i o ，p ，口 和状态s i 的一个环境配置s i ( v ) ，如果存在输入t 满足条件p ，则称变迁t 在该环境配置s ；( v ) 下可执行。 定义2 1l 可执行路径 假设m 是一个扩展有限状态机，如果存在变迁序列f 。，t 2 ，乙，使得 ( 1 ) 假定s ；为变迁t i 的头状态，则变迁t i 在某个环境配置s i ( y ) 下可执行； ( 2 ) 对于2 k 刀，变迁t k 的头状态是变迁t k 1 的尾状态，并且变迁t k 在执行 完变迁t 后的环境配置下是可执行的； 则称转换序列，f 2 ，一是一条可执行路径。 通信有限状态机( c o m m u n i c a t i n gf i n i t es t a t em a c h i n e ，c f s m ) 也是一种f s m 的扩展模 型，将在第3 章详细讨论。 2 1 3f s m 的错误模型 对于状态机模型而言，一致性测试就是比较协议规范确定的有限状态机 m = ( s ，i ，0 ，万，元) ，是否和待测实体实现的状态机m 。= ( s 。，i ，o ，艿，名) 一致，其中由于理论 上m 的个数是无穷的，所以为保证测试的顺利进行，有必要对m 的错误建模以限定测试 范围。 首先假设m 和m 。都是最简的有限状态机，由定义2 1 知，一个有限状态机主要由三个 7 南京邮电大学硕士研究生学位论文 第二章通信协议一致性测试的基本理论 集合、两个函数构成，因此其错误类型也与这五部分相关。具体有下面几类错误【4 5 1 1 4 6 1 。 ( 1 ) 关于变迁函数的错误尾状态错 对于两个给定的状态s 和s ，其中s s n s ，se s ，以及一个输入，i ，如果万( s ，j ) = s 。 但万g ，f ) s ，则m 中存在一个尾状态错误。 ( 2 ) 关于输出函数的错误输出错 对于两个给定的状态s 和s ，其中s e s n s ，j s ，以及一个输入f ，和一个输出 。 oe0 ，如果兄( s ，f ) = d 但爿( s ，f ) d ，则m 中存在一个输出错误。该错误在实际测试中可 以被即时的检测到。 ( 3 ) 集合s ，i ，0 中元素个数的错误，包括个数的增加和减少 对于m 来说，在这种类型的错误中，最可能发生的错误是对s 集合元素的增加或减少， 这主要是因为由对协议规范的理解不同造成的。理论上is 。i 的取值范围可以是【0 ，o o ) ，但显 然这样的取值使测试无法进行，因为无论怎样测试都有更大的lsi 使得一些状态没有被测 试到。因此在建立错误模型时通常对ls 。i 设置一个上限m ，即0qs i 历，而且由于初始状 态的特殊性，一般都假定被测实体中一定正确地实现了初始状态，亦即s o2s 。 ( 4 ) 关于输入的错误 对于完全定义的有限状态机而言，这种类型的错误可以转化成输出错误或尾状态错误 或这两者的结合，因此一般不考虑。 2 2 一致性测试方法 目前，协议一致性测试技术研究主要集中在两个方面：( 】) 一致性测试方法的研究和测试 结构的建立；( 2 ) 一致性测试序列的生成方法。2 2 主要介绍一致性测试方法。一致性测试序 列方法将在2 3 介绍。 8 南京邮电大学硕士研究生学位论文第二章通信协议一致性测试的基本理论 图2 1 测试结构图2 2 本地测试法 当前，大部分协议都类似于o s i 七层协议参考模型，i s o 在该参考模型的基础上提出的 抽象测试方法学【4 0 删，是构造一致性测试系统的基础。抽象测试方法学是根据对被测协议 实现( i u t ) 输入的控制和输出的观察来描述的。 在分层协议中，由于协议的允许行为是通过对等层实体间的协议数据单元( p d u ) 和协 议实体上下层间的抽象服务原语( a s p ) 来定义的，第n 层实体的行为是根据n 层a s p 和( n 1 ) 层a s p ( 包含n 层p d u ) 来定义的，因此，对协议行为的控制观察实际上是对这些a s p 矛d p d u 的控制观察，这就需要测试者从不同点在本地或远程观察和控制这两种a s p 的交互作用。 这些控制观察的地方叫控制观察点( p c o ) 。 对于端系统内m t ，i s o 4 1 1 定义了四种抽象测试方法，种是局部的，三种是外部的， 分别为分布测试法、协同测试法和远程测试法。 在局部测试法中，上下测试器与i u t 在同一系统中，两在外部测试方法中，下测试器 远离i u t 通过网络相联。每一种方法可以有多种实现，只要能完成方法的功能即可。这些 方法可测一个多层系统中的某一层，也可以测多层系统中的几层。 下面对这些方法做些介绍和比较。为方便计，n t 表示i u t 的最高层，n b 表示i u t 的最 底层，如果i u t 是单层，则t = 。 ( 1 ) 局部测试法 局部测试法的结构如图2 2 所示。该方法所要控制观察的是( 6 1 ) 和n t 层的a s p ，以 及从n b 到n t 层的p d u 。为了更有效和可靠的执行致性测试，上下测试器间的同步与合 作由协同测试过程( t c p ) 完成。 ( 2 ) 分布测试法 分布测试法如图2 。3 p f i 示。该方法所要控制观察的也是( 虬一1 ) 和n t 层的a s p ，以及从 9 南京邮电大学硕士研究生学位论文第二章通信协议一致性测试的基本理论 n b 到n ti 驹p d u ，但下测试器不在i u t 所在的系统里，而是通过( 6 1 ) 层协议提供的业务 及物理介质连接起来。上下测试器间的同步与合作也是哇 t c p 完成，因为上下测试器不在 同一系统中，所以实现起来要困难一些。 图2 3 分布测试法图2 4 协同测试法 ( 3 ) 协同测试法 协同测试法实际上是分布测试法的一种变形，如图2 4 所示。它与分布测试法的区别在 于：t 的上界面不设接口，无需访问；利用标准的测试管理过程( t m p ) 和测试管理协议数 据单元( t m p d u ) 来自动进行测试管理和协同测试过程。因此，它只控制观察( 一1 ) 层的 a s p 和n b 到n t 层p d u ，上测试器只把接收到的信息反馈给下测试器。 ( 4 ) 远程测试法 远程测试法的结构如图2 5 所示，其重要特点是没有上测试器，i u t 的上界面无p c 0 ， 因此没有明显的t c p ，要观察控制的内容也只是( 6 一1 ) 层的a s p 和n b 到n t 层p d u 。 图2 5 分布测试法图2 6 协同测试法 前面介绍的四种测试方法明显或不明显地涉及到上下测试器间的同步问题，这一点很 重要，但解决起来不容易，中科院曾华博士提出的渡船法较好地解决了这一问题。 ( 5 ) 渡船法【2 3 】 渡船法将上测试器“渡”到测试系统中，使得上下测试器在同一系统中，易于同步。而 1 0 南京邮电大学硕士研究生学位论文第二章通信协议一致性测试的基本理论 在原来上测试器所在地方用一个“渡船控制协议实体”来替换。其结构模型如图2 6 所示。 2 3 协议一致性测试过程 对协议进行一致性测试，选择适当的测试方法建立测试系统是实现协议一致性测试的 基础，而测试序列是一致性测试的核心和主线，两者是互相配合，互相制约的。一个有好 韵测试方法的测试系统，可以极大地简化测试序列的设计，使测试能方便、自动、高效地 进行；而一个好的测试集也可以极大地减轻测试系统的负担。 2 3 1 测试序列的结构 测试序列是一组输a 预期输出序列。测试集是测试序列的集合，i s 0 1 4 2 1 将其规范为层 次结构，自上而下分为测试组( t e s tg r o u p s ) 、测试实例( t e s tc a s e s ) 、测试步( t e s ts t e p s ) 和测 试事件( t e s te v e n t s ) 。测试组规定该组中测试实例的逻辑顺序，测试实例是测试组中最重要 的部分，每个测试实例由测试步组成，测试步为一系列测试事件，这些测试事件包括r l j t 发送或接收的一个p d u 或a s p 等。 i s o 把测试实例分为通用测试实例、抽象测试实例和可执行测试实例。 通用测试实例由测试体和该测试体的初始状态组成。测试体是为完成一定测试目的并 对可能的测试结果进行判定所必须的测试事件序列。测试结果判定有三种结论：通过、失败 和无结论。一旦获得通用测试集，就可根据不同的测试方法生成相应的由抽象测试实例组 成的抽象测试集。 抽象测试实例是把通用测试实例加上测试前件( t e s tp r e a m b l e ) 和测试后件( t e s t p o s t a m b l e ) ，并按照控制观察的要求表达出来得到的。测试前件是当i u t 不在该测试实例之 测试体要求的初始状态时，使i u t 到达测试体要求的初始状态的一个测试事件序列。而测 试后件是测试体测试结束后，使i u t 回到需要的稳定状态，以便后面测试运行的一个测试 事件序列。 可执行测试实例是由抽象测试实例，根据实际测试系统、协议实现一致性声明( p i c s ) 、 i u t 及其环境的附加信息( p i x i t ) 进行推导并参数化得来的，成为测试的一个具体实现，运 行在实际测试系统上。 三类测试实例的演变过程如图2 7 所示h 0 1 。 南京邮电大学硕士研究生学位论文 第二章通信协议一致性测试的基本理论 通用测试实例 抽象测试方法 抽象测试实例 选择的抽象测试实例 p i t 参数化的抽象测试实例 实际测试系统 实际测试系统 实际测试系统 可执行测试实例 选中的可执行测试实例 p i t 参数化的可执行测试实例 图2 7 测试实例演变过程 2 3 2 一致性测试序列的生成方法 基于有限状态机f s m 的测试序列生成方法可以分为两类： 第一类为变迁游历法( t r a n s i t i o nt o u r s ) ，对于f s m 中所有的变迁，所生成的测试序列 中至少包含一次；第二类方法要求协议的f s m 具有一些特殊的交互作用序列，如特征集 ( c h a r a c t e r i z a t i o ns e t ) ，可区分序y l j ( d i s t i n g u i s h i n gs e q u e n c e s ) ，和唯一输入输出序列 u i o ( u n