（计算机软件与理论专业论文）bt协议的互操作测试生成方法研究.pdf

原创性声明 本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成果。 除本文己经注明引用的内容外，论文中不包含其他人己经发表或撰写过的研究成果，也不包 含为获得囱墓直太堂及其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：巳盈坦 指导教师签名： 日日期： 么 7 y 训、；、 7 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有权将 学位论文的全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允 许编入有关数据库进行检索，也可以采用影印、缩印或其他复制手段保存、汇编学位论文。 为保护学院和导师的知识产权，作者在学期间取得的研究成果属于内蒙古大学。作者今后使 用涉及在学期间主要研究内容或研究成果，须征得内蒙古大学就读期间导师的同意；若用于 发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表。 ， 学位论文作者签名：拦盗趔 指导教师签名： 日 期： ) 以 厶! 醒 日 期： 7 警。 土 、多。 ) 内蒙古大学硕士学位论文 b t 协议的互操作测试生成方法研究 摘要 随着信息技术的发展，网络的日益普及，网络协议扮演着越来越重要的角 色，协议测试则是保证协议能正常工作的基础，协议测试一般可以分为一致性 测试、互操作测试、健壮性测试及性台日匕v , 训, a i l q l l 试，本文以b i t t o r r e n t 协议为例，介绍 了互操作测试生成方法。本文的研究内容如下： 第一，根据b i t t o r r e n t 的规约说明，详细的分析了b i t t o r r e n t 协议的工作原 理，给出了b i t t o r r e n t 的有限状态机( f s m ) 模型。 第二，介绍了m s c ，并用其形式化地描述测试目的，然后使用了互操作测 试中的全局测试目的的分解算法，将全局测试目的分解为多个单边的测试目的， 然后采用单边的测试生成方法进行测试生成，最后以b i t t o r r e n t 协议中t r a c k e r ， 和p e e r 之间的交互为例，生成测试例。+ 第三，分析- y n 试数据的选择方法，对测试数据选择方法进行了综述，从 而指导b t 协议数据包的组建。 第四，介绍了分布式测试结构，阐述了什么是可控制和可观察问题，分析 了其发生的原因，以及具体的解决方法，在分布式测试环境下，讨论了b t 协议 ， 的可控制问题，并对协议的模型进行了验证。 第五，自行设计和开发了款模型驱动的自动化测试生成工具，给出了该 工具的体系结构框架，该工具以形式化的模型为输入，采用相应的覆盖规则和 测试生成算法进行测试生成，然后用x m l 对测试例进行描述。 关键词：协议互操作测试，b i t t o r r e n t ，有限状态机，m s c ，可控制与可观察 b t 协议的互操作测试生成方法研究 r 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 t n 町g o fb i t t o r r e n tp r o t o c o 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 fi n f o r m a t i o nt e c h n o l o g ya n dt h eg r o w i n gp o p u l a r i t yo fl n t e r n e t ， n e t w o r kp r o t o c o l sp l a yam o r ea n dm o r ei m p o r t a n tr o l e p r o t o c o lt e s t i n gi st oe n s u r et h a tt h e p r o t o c o lc a l lw o r kp r o p e r l y p r o t o c o lt e s t i n gg e n e r a l l yc a nb ed i v i d e di n t oc 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 ，r o b u s tt e s t i n ga n dp e r f o r m a n c et e s t i n g i i lt h i st h e s i s ，w ei n t r o d u c e i n t e r o p e r a b i l i t yt e s t i n gg e n e r a t i o nm e t h o do fb i t t o r r e n tp r o t o c 0 1 t h er e s e a r c hw o r ki sa sf o l l o w s ： f i r s t l y , a c c o r d i n gt ot h es p e c i f i c a t i o no fb i t t o r r e n t , h o wt h eb i t t o r r e n tp r o t o c o lw o r k si s a n a l y z e da n di t sf i n i t es t a t em a c h i n e ( f s m ) m o d e li sp r e s e n t e d s e c o n d l y , m s c i si n t r o d u c e da n du s e dt o f o r m a l l y d e s c r i b e t e s t i n gp u r p o s e t h e d e c o m p o s i t i o na l g o r i t h mo fg l o b a lt e s t i n gp u r p o s ei ni n t e r o p e r a b i l i t yt e s t i n gi sa d o p t e d t h eg l o b a l t e s t i n gp u r p o s e i sd i v i d e di n t om u l t i p l eu n i l a t e r a lt e s t i n gp u r p o s e sa c c o r d i n gt ot h ea l g o r i t h m t h e n u n i l a t e r a lt e s t i n gg e n e r a t i o nm e t h o di su s e df o rt e s t i n gg e n e r a t i o n f i n a l l y , t h ei n t e r a c t i o nb e t w e e n t h et r a c k e ra n dp e e ri nb i t t o r r e np r o t o c o li sg i v e na sa ne x a m p l et og e n e r a t et h et e s tc a s e s t h i r d l y , t h es e l e c t i o nm e t h o d so ft e s td a t aa r ea n a l y z e da n ds u m m a r i z e ds oa st og u i d et h e c o n s t r u c t i o no fb tp r o t o c o lp a c k e t s f o u r t h l y , t h ed i s t r i b u t e dt e s ta r c h i t e c t u r e i si n t r o d u c e d t h et h e s i se l a b o r a t e sw h a ta r e c o n t r o l l a b l ea n do b s e r v a b l ep r o b l e m sa n da n a l y z e st h er e a s o n sf o ri t so c c u r r e n c ea sw a l la ss p e c i f i c s o l u t i o n s i nt h ed i s t r i b u t e dt e s te n v i r o n m e n t ，t h ec o n t r o l l a b l ep r o b l e mo fb t p r o t o c o li sd i s c u s s e d , a n dt h ep r o t o c o lm o d e li sv a l i d a t e d f i f t h l y , w ed e s i g na n dd e v e l o pa m o d e l d r i v e na n da u t o m a t i ct e s t i n gg e n e r a t i o nt o o la n dg i v e i t sa r c h i t e c t u r e t h et o o lt a k e saf o r m a lm o d e la st h ei n p u ta n du s e st h ec o r r e s p o n d i n gc o v e r a g e r u l e sa n dt e s t i n gg e n e r a t i o na l g o r i t h mt og e n e r a t et e s ts e q u e n c e k e y w o r d 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 t i n g , b i t t o r r e n t , f s m ，m s c ，c o n t r o l l a b l ea n d o b s e r v a b l e 内蒙古大学硕士学位论文 目录 摘要：i a b s t r a c t i i 目录i i i 图表目录v 第一章绪论1 1 1 协议测试介绍。“1 1 2 协议一致性测试介绍1 ， 1 3 协议互操作性测试介绍3 1 4 本文研究的工作4 1 5 本文结构“4 第二章相关概念。：5 2 1m s c 简介5 2 2 多端口有限状态机“6 2 3 测试序列生成方法。：7 2 4 前导序列生成方法8 第三章相关工作：1 0 3 1 测试目的描述j ：1 0 3 2 测试数据的生成方法1 1 3 3 可控制和可观察问题：1 2 第四章b t 协议的工作原理及形式化建模_ 1 8 4 1b t 协议的介绍1 8 4 2b t 协议的工作过程1 9 ， 4 3f s m 图表示法：2 1 4 4b i t t o r r e n t 协议的f s m 模型：2 2 4 5b t 协议的可控制问题2 4 4 5 1 构造b t 测试数据包：2 5 4 5 2 实验中遇到的问题。2 6 4 6 本章小结。3 0 m b t 协议的互操作测试生成方法研究 第五章b t 协议的互操作测试生成3 1 5 1 一般性的互操作测试生成方法31 5 2 测试目的分解的互操作测试生成方法31 5 2 1 用m s c 描述测试目的3 2 5 2 2 互操作测试生成方法介绍3 3 5 2 3 测试目的分解算法：。3 5 5 3b t 协议的互操作测试生成。3 6 5 4 模型驱动的自动化测试生成工具4 0 5 4 1 自动化测试的研究现状：。4 0 5 4 2 模型驱动的自动化测试生成工具的结构框架：4 0 5 4 3 使用模型驱动的自动化工具进行测试生成。4 1 5 5 本章小结4 5 一第六章测试执行_ j 4 6 6 1 现有b t 软件介绍4 6 6 2 测试环境的搭建4 6 6 3 模拟程序的说明：4 8 第七章工作总结和下一步工作5 0 7 1 工作总结：。5 0 7 2 下一步工作江5 0 参考文献5 2 致谢5 5 参加项目o 5 7 i v 内蒙古大学硕士学位论文 图表目录 图1 1 一致性测试流程图2 图2 1 m s c 发展历史5 图2 2 分布式测试结构6 表2 1 测试序列生成方法的对比8 图3 1 互操作测试结构_ 1 4 图3 2 可观察问题b i a s 和p e r m i s i v e n e s s 15 图3 3 加入时间戳和重构队列解决可观察问题1 6 图4 1b i t t o r r e n t 系统组织结构示意图。：。19 图4 2t r a c k e rh t t p h t t p s 协议的序列图：2 0 图4 3p e e rw i r e 协议的序列图2 1 图4 4b i t t o r r c n t 协议的f s m 2 3 图4 5b i t t o r r e n t 协议的可控制问题2 4 图4 6 实验拓扑2 5 图4 8 模拟t r a c k e r 程序的运行结果：2 6 图4 9 校对后的b i t t o r r c n t 协议的f s m j j _ 2 7 表4 1 简化b i t t o r r e n t 模型的状态对应表2 8 表4 2 简化b i t t o r r 髓t 模型的输入输出对应表2 8 图4 1 0b i t t o r r c n t 协议的简化f s m 2 9 图5 1 一般性的互操作测试生成。3 l 图5 2 单边互操作性测试结构3 2 图5 3m s c 描述测试目的3 3 图5 4 测试目的分解的互操作测试生成方法3 4 图5 5 算法描述图j _ 3 5 图5 6b t 协议的单边测试结构图3 6 图5 7t r a c k e r h t t p 协议模型3 7 图5 8t r a c k e r 和p e e r 之间的交互图“3 7 图5 9 全局测试目的及单边测试目的_ 3 8 图5 1 0 根据全局测试目的生成的测试例3 8 v b t 协议的互操作测试生成方法研究 图5 1 1 根据单边测试目的生成的两个单边测试例3 9 图5 1 2 测试工具体系结构图4 1 表5 1 图4 1 0 中各状态的u i o 序列表4 2 表5 2 图4 9 中各变迁的测试序列表4 2 图5 1 3 形式化模型的数据结构图4 3 图5 1 4 求得的u i o 序列图：4 4 图5 1 5 求得最短路径和最后的测试序列图4 5 图6 1 测试环境拓扑图。4 7 表6 1p e e r ( b c ) 澳j j 试目的表。4 7 图6 2 数据包组建图：_ 4 9 v i 内蒙古大学硕士学位论文 1 1 协议测试介绍 第一章绪论 目前随着信息技术的飞速发展，网络在人们的生活中扮演着越来越重要的角色，网络协 议也越来越复杂，因此需要进行测试。协议测试则是保证协议正常工作的基础，近二十年， 它的理论和技术得到广泛研究和深入发展。 协议是通信双方关于如何进行通信的行为准则，通信双方只有正确的实现相同的协议， 才可以正确有效的进行信息的交互和传输。协议的规约说明是由一个标准化的r f c 协议文档 来描述的，这些描述都是自然语言，不同的人可能会有不同的理解，这样就不能保证同一协 议的不同实现之间能够完全成功地进行通信。因此为了确保协议的实现是正确的，就需要测 试人员对协议进行测试。协议测试技术是保证网络通信协议正确实现以及不同的网络设备之 间正确交互的重要手段。协议测试属于软件测试范畴，在软件测试中，一般分为白盒测试和 黑盒测试。白盒测试又称结构测试，是对软件内部实现结构和实现逻辑进行测试；黑盒测试 又称功能测试，是通过外部环境对系统进行输入，观察系统的输出，从而来确定功能实现是 否正确。协议测试是一种黑盒测试，协议测试是协议工程中的一个重要的步骤。 协议测试包括一致性测试、性能测试、互操作性测试和健壮性( 坚固性) 测试。一致 性测试是用来检测协议的实现与协议的规约说明的符合程度；互操作测试是用来检测同一协 议规约说明的不同实现间的互连和互操作的能力；性能测试用来检测协议实体或系统的性能 指标；健壮性测试用来检测协议在各种环境下运行的能力，如信道被切断，断电，注入干扰 报文等情况。其中，一致性测试是测试的基础，其目标是检测协议实现是否与协议规范相一 致。作为一致性测试的补充，互操作性测试的主要目标是测试两个或更多的协议实现在实际的 网络环境中是否能够正确地交互，从而完成协议规范中规定的功能，它对于通信产品的质量保 证有着重要的现实意义。 ： 1 2 协议一致性测试介绍 协议一致性测试的目的是通过测试去发现被测协议实现在功能和逻辑方面的错误，目前 协议一致性测试的经典理论是i s o 制定的协议一致性测试标准和框架i s o o s l 9 6 4 6 。i s o9 6 4 6 共有7 个部分【2 】【3 】，分别介绍了一致性测试的基本原理、抽象测试套描述、树表结合表示法 b t 协议的互操作测试生成方法研究 t t c n 、测试实现、一致性判定过程对实验室和客户的要求、测试说明以及实现一致性声明等 内容。根据i s o9 6 4 6 的定义，协议的一致性测试过程大致分为四个阶段【4 1 ，如图1 1 所示： 图1 1 一致性测试流程图 f i g u r e l 1c o n f o r m a n c et e s t i n gp r o c e s s 第一阶段是协议的形式化建模( g e n e r a t ef o r m a lm o d e l ) ，即首先利用一定的形式描述技 术f d t ( f o r m a ld e s c r i p t i o nt e c h n i q u e s ) 生成协议的形式化模型，形式化模型是测试生成的 基础，因此它本身必须是正确的。目前国际上通用的形式化模型有：p e t r i 网、有限状态机 ( f s m ) 、带标记转换系统( l t s ) 等。由i s o 和c c i t t 规定的形式化描述语言有：s d l 、 l o t o s 、a s n 1 、m s c 、t t c n 等。 第二阶段是测试生成( t e s tg e n e r a t e ) ，即生成一个协议的抽象测试套，它是包含所有该 协议的实现设计的测试集。 一个完全的测试套应该是完备的，对被测实现进行充分的测试，通常这种测试套是非常 庞大的，有时甚至是无穷的，不可能在有限的时间内完成这种测试。实际上，必须从完全的 测试套中进行选择，然后用于实际测试。此时选择就是根据实际需求和测试目的，对测试套 进行选择，得到实际要执行的一致性测试的测试套。 由于测试的侧重点不同，形式化的测试生成技术可分为：基于控制流的测试生成方法、 基于数据流的测试生成方法、数据流与控制流相结合的测试方法。现有的控制流方法多是基 于有限状态机f s m 和e f s m 的。数据流测试起源于软件工程，且通常是基于数据流图。数据 流与控制流相结合的测试方法相对而言比较复杂，多数都是在( e ) f s m 上进行的 5 1 。 第三阶段是测试实现( t e s ti m p l e m e n t a t i o n ) 为执行特定的测试集做准备。在这一阶段， 抽象测试套中的抽象测试例被转变为可在一个实际测试环境或测试配置上执行的测试例，然 2 内蒙古大学硕士学位论文 后用于测试执行。 第四阶段测试执行( e x e c u t et e s t ) 运行可执行的测试例，最后得到一个关于被测协议实 现( i m p l e m e n t a t i o nu n d e r t e s t ) 相对于协议规范说明是否一致的判定。 协议一致性测试测试套分为三种：抽象测试套、通用测试套和可执行测试套。它们在协 议一致性测试过程中发挥着不同的作用。通用测试套是对一个协议进行一致性测试的全部测 试套。它仅仅根据协议的测试目的产生，不管使用何种测试方法，也不管协议的具体实现。 1 3 协议互操作性测试介绍 ， 互操作测试和一致性测试都是测试协议实现重要而有效的方法，互操作性测试作为一致 性测试的后继步骤，其采用的很多方法都沿用于一致性测试，但由于互操作性本身的特点，二 者也有明显的区别，一致性测试的方法并不能直接在互操作性测试中套用。首先，在进行一致 性测试时，通常把被测实现( t ) 当做一个黑匣子，由测试人员( t e s t e r ) 模拟与其通信的所有其 他实体，而在互操作性测试中，为了测试两个或多个i u t s 的交互行为，t s 通常放置在一个 开放环境中测试，由测试人员观察和控制i u t 间的交互，因此需要新的测试方法和测试框架结 构；其次，互操作系统的形式化描述不能直接来自于协议规范，必须先对通信双方分别进行形 式化描述之后通过可达性分析等技术获取整个系统交互行为的形式化描述；最后，互操作性 测试至少涉及两个通信实体。 在实际的测试中，通过一致性测试的设备并不一定能保证它们之间能正确有效的互操作， 原因如下：第一，标准中存在含糊和错误的内容；标准的兼容性问题；第二，标准是自然语 言描述的，不用的人对标准规范的理解不同；第三，标准本身存在很多可选项。 关于协议互操作性测试的理论研究，国内外的许多学者、科研组织和团体都做了大量的 工作。在理论研究方面，人们做出了很多成果，发表了很多文章。文章 5 】给出了多端口有限 状态机的模型，采用基于可达性分析的方法生成测试序列，然后进行差错覆盖分析，并进一 步给出了增强的测试生成算法，最后选择适当的分布式测试结构，加入测试部件之间的协调， 消息，用以解决可控制和可观察问题。文章 6 采用m s c ( 消息序列图) 来描述测试目的，采用 通信多端口有限状态机作为被测系统的描述模型，使用全局状态跟踪和逆向查找等技术生成 测试序列，从而减少了发生状态爆炸的可能。文章 7 】提出了基于有向图的最小完全覆盖互操 作性测试序列生成算法，使用该算法生成的测试集是_ 个能覆盖所有互操作转换序列的最小 集。文章 8 系统地研究了互操作性测试理论和方法。文中研究了基于有限状态机的互操作性 3 b t 协议的互操作测试生成方法研究 测试常用测试序列的生成方法，研究了基于有限状态机的测试覆盖和错误模型，研究了单边 互操作性的测试方法和动态测试方法，给出了基于贪心算法的次优互操作序列生成方法。国 内外的科研机构和团体也做了许多相关的研究工作，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 ) 在协议互操作性测试方面也做了大量的工作，目前他们对i p v 6 的测 试包括测试i p v 6 的基本协议部分以及i p v 6 的相关协议，并免费提供部分相关测试套【9 】，日本 的t a h i 项目研究和开发了i p v 6 协议的互操作性测试系统，他们在i p v 6 方面做了大量的工作， 并且在官方网站上【l o 】公布了部分测试套，而且也公布了最新的研究进程。在国内，清华大学 的计算机网络技术研究所在网络协议方面做了大量的研究实践工作，完成了多项目国家级项 目，发表多篇相关论文；中国科技大学、中国科学院、北京邮电大学也在协议的互操作性测 试方面作了很多工作。 1 4 本文研究的工作 由于互操作测试是在一致性测试的基础上发展而来的，所以一致性测试在理论基础和背 景上都要比互操作测试成熟。本文给出b t 协议的形式化模型，在分布式测试场景下发现了 可控制问题，分析了可控制和可观察问题并综述了常用的解决方法，通过大量模拟实验，对 模型进行了检测。本文从测试目的的形式化入手，用m s c 形式化测试目的，然后引入一个算 法，实现了测试目的的分解，将互操作测试的全局测试目的分解为单边测试的测试目的，实 现了从互操作测试到一致性测试的转化，从而可以使用一致性测试的理论方法来进行互操作 测试，分析了测试数据的选择方法，从而更有效的对被测实现进行测试。本文还自行设计和 开发了二个模型驱动的自动化测试工具，该工具以i u t 形式化模型为输入，它以文本的方式 进行存储，输入形式化模型中的顶点和边，然后自动生成测试序列，从而得到测试套，并用 x m l 对测试套进行描述，该工具还模拟分布式测试场景，模拟了个主测试成分( m t c ) 和多个 辅助测试成分，并在测试成分之间加入了一定的时序关系，从而解决了可控制和观察问题。 该工具目前实现到了自动生成测试序列。 1 5 本文结构 本文主要分为以下几个部分：第二章本文工作的相关概念；第三章本文的相关工作；第 四章介绍b t 协议的工作原理及形式化建模，b t 协议中的可控制问题；第五章介绍b t 协议 的互操作测试生成方法；第六章为测试执行；第七章为工作总结和下一步工作。 4 内蒙古大学硕士学位论文 第二章相关概念 本文涉及到对协议的建模、测试序列的生成方法及分布式测试结构，本章主要介绍论文 中涉及的相关概念。 2 1m s c 简介 用于建立形式化模型的方法虽然有很多，；口p e t n 网、s d l 、l o t o s 等，但m s c ( 消息序列 图) 是t ( 国际电信联盟) 提出的一种形式描述语言，它是一种标准的迹语言，与传统的形式 描述语言相比，它着眼于并发进程之间传递的消息，通过描述消息交换来说明系统成分与环 境之间的通信行为。它以直观、透明的方式反映通信行为，省略了传统的形式描述技术必须 考虑的大多数诸如程序变量以及变量值这样的细节，特别适用于说明通信协议。主要用于说 明和描述组成系统的消息实例之间的通信行为。 4 m s c 作为一种形式化的语言，可以应用于从分析到设计以及测试的全过程，以图形化的 方式描述消息实例之间的消息传递以及事件发生的顺序，并对传输数据的值和事件发生的时 间进行限制性说明，其形式化定义如下所述。 定义2 1m s c 一个m s c 6 可表示为一个8 元组( v ， = ( i ，e 2 ，n ) ，e k 是第k 个端口的输入，且i ne j = 空( i j ) ，令i - iu e 2 u u n ； f 是一个n 元组( f l ，f 2 ，f n ) ，f k 是第k 个端口的输出，r i nr j = 空( i c j ) ， 令o = r - u e ) xf 。u ，其中e 表示为空； 万是变迁函数，s i - s ；名是输出函数，允s i - ) o 图2 2 分布式测试结构 f i g u r e2 2d i s t r i b u t e dt e s ta r c h i t e c t u r e 6 内蒙古大学硕士学位论文 2 3 测试序列生成方法 一般情况下，协议测试都是先对协议进行形式化建模，然后根据形式化模型生成测试序 列，再根据测试序列生成测试例，目前的经典的测试序列生成方法主要有5 种，它们分别是【4 】： t 方法：这个方法假设一个最小的、强连通的且是完全说明的m e a l y 机模型，它的测试 序列生成方法是随机的向处理机输入一个字符，直到遍历每一个变迁至少一次。该方法的缺 点是测试输入序列中存在大量的冗余，检错能力较差。 、 d 方法：该方法假设m e a l y 机是最小的、强连通的、完全说明的，而且有可区分序列d s ( d i s t i n g u i s h i n gs e q u e l l c e ) ，然后根据该区分序列构造测试输入序列。该方法产生的测试输入 序列数目较少。但是这种方法要求处理机是完全说明的，才能生成d s 。 w 方法：该方法基于状态机的状态识别集来构造测试输入序列，包括两个输入序列集合 ws e t 和ps e t 。ws e t 是f s m 最小特征集，它使得每对状态能够相互区分，即对不同点应用 ws e t 观察到的输出应是能够区分的，ps e t 包括了所有部分路径，由一个测试树构成，它的 根节点是初始状态，每个迁移只出现一次。它适于描述非完全的状态机，但该方法产生的测 试序列数目较多，在实际应用中的测试效率不高。 w p 方法：该方法是对w 方法的简化，w p 方法的前提条件是规约说明和实现中的有限 状态机是精简的、强连通的、完全的，并且实现中的每个状态都存在r e s e t 操作且都已正确实 现。强连通可以通过添加r e s e t 操作来实现，当有限状态机处于任意状态时，通过应用r e s e t 操作它都可以返回到初始状态，这样使得每一个测试输入序列都从初始状态开始，否则无法 保证测试的正确性。该方法保证了与w 方法具有相同的错误覆盖度，但产生的测试输入序列 数目仍然较多。 。 u i o ( u m q u eh p u t o u t p u t ) 方法：u i o 方法通过为每个状态确定一个唯一的输入输出区 别序列来将该状态与其它状态进行区分，使用u i o 方法进行测试的基本步骤是： ( 1 ) 对每个迁移s i - s j 找到从初始点到s i 的序列； ( 2 ) 使输入按照s i s j 方向变迁； ( 3 ) 对s j 点应用u i o 序列。 7 b t 协议的互操作测试生成方法研究 表2 1 测试序列生成方法的对比 t a b l e2 1c o m p a r i s o no ft h et e s ts e q u e n c eg e n e r a t i o n 序列名称 方法特点 t 序列 随机性太强，容易生成大量的冗余用例 d 序列能发现故障点但不能保证总是存在 w 序列，w p 序列能发现比较复杂的错误，测试序列长度在实际 的复杂系统中很难使用 u i o 序列长度相对较短，生成算法也简单，几乎都存在 u i o 序列 u i o 方法 1 1 】蚴是通过找出每个状态的的唯一的输入输出区别序列来与其它状态区分。使 用u i o 方法检测变迁需要按照如下三个步骤进行。如要测试变迁s i s j ，首先找到从f s m 模 型的初始点到s i 的输入输出序列，加上变迁s i s i 的输入输出对，再加上s j 的u i o 序列。这 样就构成了测试变迁s i s j 的测试序列，最后将有重叠的测试序列进行合并，以得到较短的测 试序列，例如序列r1 1 1 2 和ri l l 2 1 3 ，可以包含合并只用ri l i ：1 3 表示。 u i o 方法要求f s m 是最小的、强连通的。为了使f s m 模型满足强连通性，将i u t 的复 位操作r e s e t 也加入到f s m 中，即不管m 处于何种状态下，都可以给其一个复位输入r 令 其回到状态机的初始状态。在f s m 描述上表现为为每个状态都加了到初始状态的变迁以， 这样就保证的f s m 的强连通性。 2 4 前导序列生成方法 当要测试一个变迁时，首先要找到从模型的起始点到该变迁起点的前导序列，在本文， 生成前导序列采用d i j k s t r a 算法。 d i j k s 缸a ( 迪杰斯特拉) 算法【1 3 】是典型的单源最短路径算法，用于计算一个节点到其它所有 节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。d i j k s t r a 算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数 据结构，图论，运筹学等等。d i j k s t r a - - 般的表述通常有两种方式，一种用永久和临时标号方 式，一种是用o p e n ，c l o s e 表的方式，这里均采用永久和临时标号的方式。注意该算法要求 8 内蒙古大学硕士学位论文 图中不存在负权边。 d i j k s t r a 算法思想为：设g = ( v ，e ) 是一个带权有向图，把图中顶点集合v 分成两组，第一 组为已求出最短路径的顶点集合( 用s 表示，初始时s 中只有一个源点，以后每求得一条最短 路径，就将加入到集合s 中，直到全部顶点都加入n s 中，算法就结束了) ，第二组为其余未 确定最短路径的顶点集合( 用u 表示) ，按最短路径长度的递增次序依次把第二组的顶点加入 s 中。在加入的过程中，总保持从源点v n s 中各顶点的最短路径长度不大于从源点v 到u 中任 何项点的最短路径长度。此外，每个顶点对应一个距离，s 中的顶点的距离就是从v n 此顶点 的最短路径长度，u 中的顶点的距离，是从v n 此顶点只包括s 中的顶点为中间顶点的当前最 短路径长度。 9 b t 协议的互操作测试生成方法研究 第三章相关工作 本文从测试目的的形式化入手，分析了测试数据的选择方法，在分布式测试结构下，讨 论了可能出现的可控制和可观察问题，最后给出- b t 协议的互操作测试生成方法。 3 1 测试目的描述 在测试过程中，测试目的一般都是用自然语言去描述，或者根据测试人员的经验去选择 一些被测实现说明中的属性，很难给出测试目的的形式化描述，关于这方面的研究工作也比 较少。 文章 6 】提出了一种基于m s c ( 消息序列图) 测试目的的互操作测试生成方法，采用多端 口有限状态机做为被测系统的描述模型，m s c 做为互操作性测试目的的描述模型，使用全局 状态跟踪和逆向查找等技术从系统规范中生成包含该测试目的的测试序列。该方法由于只需 遍历系统的部分状态空间，因此在一定程度上减少发生状态爆炸问题的可能。 文章 1 4 】提出了一种方法，用i o s t s 对系统进行建模，测试一个系统是否和它的规约说 明是一致，该文使用带符号执行技术，对i o s t s 的行为进行提取，得到所谓的测试目的，并 给出了相应的测试生成算法，和以往的测试生成方法相对比，该文的测试目的，直接被描述 成了被测说明中所必须的属性，它们是有限的带符号执行的子树。最后文章给出了覆盖原则， 并给出了一个例子来说明这个过程。 文章 1 5 提出了一种基于协议的s d l 和m s c 描述的一致性测试生成方法，这种方法从 协议的形式化描述出发，用形式化的语言定义测试目的和测试组，通过该文提出的算法自动 生成一致性测试套。 文章 1 6 1 基于模型构造一个在线的测试器，然后将它用于h a t 的黑盒测试，用e f s m 对 m 的行为进行建模，一个测试目的是t 模型中的一系列的用来衡量测试运行过程的布尔 变量，它和t 模型中的变迁密切相关，当所有的节点都被访问到，就说明达到了测试目的。 判定原则是通过i u t 模型和测试目的获得的。 文章 1 7 】给出了一种生成测试目的的方法，它采用带标记转化系统的形式，从规范说明 中的属性中获得，该方法的目的是在适应模型检测的过程，通过扩展搜索算法去进行进一步 的分析，以至于正例和反例都可以被抽象出来，通过分析正例和反例给出了测试目的生成算 法，通过研究一个例子，说明了c t l 属性和测试目的生成的一致性。 1 0 内蒙古大学硕士学位论文 上述文献对测试目的进行了描述，用m s c 描述测试目的、把测试目的描述为系统的属性 或者模型中的执行路径，本文采用m s c 描述测试目的。 3 2 测试数据的生成方法 当一个软件开发完成后，能否准确无误的完成任务，能否实际的投入运行，软件的质量 是关键。为了保证软件的质量，我们必须对其进行详尽的测试，然而测试活动需要大量的测 试数据，其来源有三种：( 1 ) 基于功能，从软件需求中获得；( 2 ) 基于结构，从软件实现中 获得；( 3 ) 基于错误，从开发过程中产生的典型和有用的错误中获得。基于功能的测试数据 通常由规约产生，基于结构的测试数据可从程序语句的路径来生成。据统计，在所有的软件 测试的开销中，约4 0 的花费在设计测试用例( 包括测试结果和预期结果) 上，约5 0 花费 在编写和编译测试脚本上，另外约1 0 花费在测试脚本的执行和配置管理上。当前，协议测 试主要依靠测试人员手工设计测试用例，这种方法费时，费力，且带有一定的盲目性和倾向 性。提高测试数据生成的自动化程度可以有效的减轻测试人员的劳动强度，提高软件测试的 质量。此外，测试数据的有效性将直