（计算机软件与理论专业论文）路由协议的一致性测试.pdf

中陶科学技术人学硕l 论空 摘要 考虑到在一个复杂的通信刚络中，多种不同设备的互操作性，我们必须对 网络中的每一个组成部件，根据它们的规范进行一致性测试。随着通信协议的 复杂性不断的增长，根据协议规范对坍议进行一致性测试已经逐渐成为软件产 品开发周期中的一个部分。同时网络的飞速发展引发了i n t e r n e t 结构的改变，路 由协议对网络f 确稳定运行起着重要作用，因而针对路由协议的测试也成为通 信协议测试的研究重点。本论文在研究路由协议的相关文档和规范基础上，深 入研究当前一致性测试技术的不同理论方法，使用不同的测试方法对路由功- 议 进行了测试实践，过程中注重不同测试方法过程中的形式化技术的应用，同时， 探讨了多种不同的测试方法之间的比较，提出了更适应于路由协议测试的一致 性测试生成的建议。 论文的主要工作包括以下几个方面： 1 ) 介绍和比较了目前常用的测试序列生成技术的特点，描述了一种基于 u i o 序列和中国乡村邮递员问题的测试序列生成方法。 2 ) 使用基于f s m 的测试生成方法对边缘网关协议( b g p ) 进行了测试实践。 并以b g p 协议的互连行为状态机为例实践了基于u i o 序列和中国乡村邮路算法 生成测试序列的方法。该方法易于自动化实现，能够生成更短的测试序列。 3 ) 在基于测试目的的幼、议一致性测试实践中，结合- 议测试的特点，选取 b g p 4 协议进行了协议形式化描述的工作。 4 ) 对比了不同的协议测试方法在路由协议测试中的应用优势，并提出了更 全面的路由协议测试的一致性测试构思。 关键词 路山协议，一致性测试；有限状态机，测试f | 的，测试序列 分类号t p 3 9 3 中困科学技术人学顺 ：论史 a b s t r a c t c o n s i d e r i n gt h ei n t e r c o n n e c t i n ga n di n t e r o p e r a t i n gb e t w e e nd e v i c e so fv a r i o u s v e n d o r s ，w eh a v et ot e s te a c hc o m p o n e n ti nt h ec o m p l i c a t e dc o m m u n i c a t i o n n e t w o r k sa c c o r d i n gt ot h ep r o t o c o ls p e c i f i c a t i o n s w i t ht h eg r o w i n go fc o m p l e x i t yo f c o m m u n i c a t i o np r o t o c o l s ，s p e c i f i c a t i o nb a s e dc o n f o r m a n c et e s t i n gi sb e c o m i n gp a r t o fs o f t w a r ed e v e l o p m e n tc y c l e a tt h es a m et i m e ，t h eh i g h l ye x p a n d i n gc o m p u t e r n e t w o r kr e s u l t si ng r e a tc h a n g eo ft h es t r u c t u r eo fi n t e r n e t r o u t i n gp r o t o c o l sa r e m o s t l yr e s p o n s i b l ef o rt h ec o r r e c to p e r a t i n ga n ds t a b l er u n n i n go fc o m p u t e rn e t w o r k s ， s oc o n f o r m a n c et e s t i n go fr o u t i n g p r o t o c o l b e c o m e st h ef o c u so fp r o t o c o l e n g i n e e r i n g w i t hr o u t i n gp r o t o c o ls t a n d a r d s ，w em a k et h es t u d yo fv a r i o u s c 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 s ，a n da p p l i e dt h e mo nt h ep r a c t i c a l w o r ko ft h ec o n f o r m a n c et e s t i n go fr o u t i n gp r o t o c 0 1 i nt h ea p p l i c a t i o n ，w ea r e h i g h l yc o n c e r n e do nt h eu s eo ff o r m a lm e t h o d si nd e s c r i p t i o n ，v a l i d a t i o na n d i m p l e m e n t a t i o n a tl a s tw ec o m p a r et h ea d v a n t a g e so fd i 腩r e n tt e s t i n gm e t h o d s w h e na p p l i e dt or o u t i n gp r o t o c o lt e s t i n ga n dm a k es u g g e s t i o no nt e s tg e n e r a t i o n m e t h o db e t t e ra c c o m m o d a t i n gr o u t i n gp r o t o c o l s t h em a i nw o r ko f t h ep a p e ri n c l u d e st h ef o l l o w i n ga s p e c t s ： 1 ) i n t r o d u c et h ef e a t u r e so fc u r r e n tp o p u l a rt e s ts e q u e n c eg e n e r a t i o n t e c h n i q u e s a n dd e s c r i b eat e s ts e q u e n c eg e n e r a t i o nm e t h o db a s e do nu i os e q u e n c e a n dr u r a lc h i n e s ep o s t m a np r o b l e m 2 ) t e s tb g pp r o t o c o lu s i n gm e t h o db a s e do nf s m a n dp r a c t i c eo nt h et e s t s e q u e n c eg e n e r a t i o nm e t h o db a s e do nt h eu 1 0s e q u e n c ea n dc h i n ap o s t m a np r o b l e m ， a n dd e m o n s t r a t eb yu s eo ft h es t a t em a c h i n eo fb g p t h em e t h o di s e a s yt ob e a u t o m a t e da n d g e n e r a t e sas h o r t e rt e s ts e q u e n c e 3 ) i nt h ep r a c t i c eo np r o t o c o lc o n f o r m a n c et e s tb a s e do nt h et e s tp u r p o s e ， s e l e c tb g pt op r a c t i c et h ef o r m a ld e s c r i p t i o no ft h ep r o t o c 0 1 4 )c o m p a r et h ea d v a n t a g e so f d i f f i r e n tp r o t o c o lt e s tm e t h o d si nt h e a p p l i c a t i o no fr o u t i n gp r o t o c o lt e s t ，a n dg i v eam o r ec o m p r e h e n s i v ei d e ao fr o u t i n g p r o t o c o lc o n f o r m a n c et e s t k e y w o r d s r o u t i n gp r o t o c o l ；c o n f o r m a n c et e s t i n g ：f s m ：t e s tp u r p o s e ；t e s ts e q u e n c e k e v c o d e t p 3 9 3 4 中国科学技术人学颂j 论文 1 1 研究背景 第一章引言 数据通信领域目前l e 仡发生这两个转变，其一赴通信协议日趋复杂其二就是网络环境 中，数据通讯涉及剑越来越多的设备供府商乖l 服务提供商。如果没有协议测试的 - 作，符种 设备之间的互操作性就得不到保证。首先，对丁协议规范f l 勺不同理解就可能导致多种协议实 现版本：其次，协议的实现在很多情况r 依赖丁可选的协没属性，这也可能造成多种不同的 协议实现：第三，由丁胁泌的复杂性，协议开发人员可能在开发中山现火误：最后，对丁没 有进行完器详尽描述的协议，最容易山现不同协泌实现之间的不兼容情况。 故考虑到在一个复杂的通信网络中，多种不同设备的互操作性，我1 j 必须对网络中的每 一个组成部什，根据它们的规范，进行致性测试。随着通信协议的复杂性不断的增长，根 据胁议规范对机议进行一致性测试已经逐渐成为软什产协开发周期中的一个部分，协议测试 也越来越成为一个倍受巫视的研究方向，其中测试序列的自动生成逐渐成为一致性测试中的 研究热点。 一致性测试是对被测实现i u t ( i m p l e m e n t a t i o nu n d e rt e s t ) 进行的细致、系统的试 验，以确定该实现是否正确完成了协议规范中的标准。进行协议测试的一般做法首先要根据 协议规范( p r o t o c o ls p e c if i c a t i o n ) 取得严格的形式化描述：接着，从协议的形式化描 述出发依照一致性测试的测试套生成规范化方法，生成相应的测试序列，再结合具体的测 试数据和测试环境来描述删试j h 例。最后搭建测试系统将测试用例在待测协议实现i u t 上执 行，生成测试报告。对丁一致性测试方法的研究，国内外已经开展了长期的工作，并在理论 上得到了相当成熟的理论。对于不同丁誓纯通信协议的路由协议测试，更需要研究讨论一种 贴切的洲试方法，这使我所进行的研究内容贝有一定的理论价值。 1 2 研究现状 协议测试的研究最甲丁1 9 7 9 年由英国国家物理实验空( n p l ，n a t i o n a lp h y s i c a l l a b o r a t o r y ) 展开。1 9 8 3 年，n p l 开始了基0 ：o s i 模型的防议形式化帚f 一致性测试的标准化。】： 作。协泌一致性测试经过2 0 米年的发展，取得了很人的进展。国际标准化组织i s 0 专门制定 的国际标准一o s i 一致性洲试方法j j 框架。 目前，协议致性测试研究】：作士要集中1 ：两方而： ( 1 ) 测试组织：叫i 测试方法的研究jo 9 4 试系统的建立； ( 2 ) 测试集：即如何从珊论利方法上研究) ：产生赢质艟的测试集： 其中，测试集足一致性测试的核心羊士线，沸议一致性测试系统是实现协议一致性测试的基 础。蹦者是榴且配台，川且制约的。一个蚶的测试系统可以极人地简化测试序列的设汁，使 得洲试能方便、白动、高敛地进行：而一个好的洲试集也可以极火地减轻测试系统的负担。 协议一致性测试的过程人致分为四个阶段： ( 1 ) 协议的形式化描述。这魁协议一致性测试的基础，日的是为了避免自然语言的二义性， 使得测试者或实现者对晰议规范有一个清晰一致的理解。 中国科学技术人学硕卜论义 ( 2 ) 测试序列生成。测试序列是协议一致性测试的核心数据，它的检错能力直接影响着测 试的错误覆蔫率：而测试序列的妊度则影响着测试效率。结合具体的测试环境和测试要求， 可采刚t t c n 语言描述测试序州，以生成测试j | j 例。 ( 3 ) 测试序列执行。t t c n 测试用例经过语言分析和编译，转化为可以被实际的测试设备或 测试系统执行或解析的可执行测试j h 例。将_ j 执行测试埘例与待测协议实现i u t 一起执 i 测 试，生成测试报告。 ( 4 ) 测试结果分析。根据洲试川例执行的结果分析i u t 的协议一致性符台程度，得到一致 性报告。 以上四个阶段中( 1 ) ( 2 ) 是协议毁性测试研究的热点，已经形成了很多相当成熟 的理论。 1 3 研究目的 本论文的主体讨论了两种通信协议测试方法，以及他们的实践。这两种测试方法分别 为：基于有限状态机f s m 的协议一致性测试方法，= 以及基丁洲试目的描述的协议一致性洲试。 基丁- 协议的f s m 模l ! ，哉 j 的一致性测试方法预j 9 j 产生最小代价的一致性测试例，并 且期望得到最人的错误覆盖率。同时为了解决现实中的实际限制，即突破实际被测系统的可 测试性乖l 实际的测试环境造成的实践问题，我甜j 对丁协议测试的模型进行了改进，使得测试 的复杂度降低同时可测试性提高的日的。在理想情况f 。测试这应该可以完全观察并控制被 测系统s u t ，换旬衍说就是测试者可以对i u t 实施任意的输入，并观察剑所有的相应输出。 本文土要阐述的是这些理想情况难以达剑，测试受限的条件一f ，如何产生恰当的测试例。实 际测试中的限制包括对i u t 符个接口的可控性( 例如某些接口被隐藏在被侧系统中) ，以及 可能需要根据i u t 的内部计时器，限制i u t 在指定状态的停留测试时间等。本文中论述的 f s m 改进测试方法着眼丁受限的测试环境中，保证协议的可测性和测试的覆盖率的烈重考 虑。 基了测试目的描述的测试是另一种通信协议测试生成方法，我1 j 尝试了这种测试方法在 路由协议b g p 4 协议测试- 1 j 的实践同时将这种测试方法与基丁f s m 的测试做出比较。 1 4 文章结构安排 本文的组织结构为：前言部分的第一章对协议一致性测试作出简要介纠；第二章介荆了 协议的形式化描述理论和常见的测试序列生成算法，以及一种测试序列优化方法，母后介绍 了协议的测试套描述语言：第二章介细了通信协议的一致性测试方法理论和本文采用的实际 测试方法和环境；第四章简要的介绍了当前主要的路由拂议；接下来论文的主体部分介萱 了两种不同的洲试方法研究。首先是基于有限状态机的防泌一致性测试及b g p 4 测试研究( 第 元章) ，以及基。】：测试目的捕述的协议一致性测试方法及b g p 4 的测试研究( 第a 章) 。在第 七章中针对不同的通信协议一致性测试方法，对他们进行了有效性可凄性等性能表现上 的比较：同时捉“i 了以历前世进一步研究的儿个n q 题。第八章灶本文的 求语，总结全文。 6 中周科学技术人学坝l 论史 第二章协议的形式化描述与测试序列生成 2 1 协议形式化模型理论 形式化描述是通过，系列形式化理论、模掣和方法，对协议进行精确的描述。形式化描 述是协议殴计、实现、测试的基础，对协议实现的i f ：确性、完全性雨j 复杂性有至关重要的影 响。 关丁协议的形式化方法，目前已经研究井开发出多种形式的模型，主要有以一r 儿种： 有限状态机( f i n i t es l a t em a c h i n e ) 、p e t r il 取l ( p e t r i n e t ) 、时序逻辑( t e m p o r a ll o g i c ) 、通信系统 演算( c a l c u l a t i o n so fc o m m u n i c a t i o ns y s t e m ) 、形式文法( f o r m a lg r a m m a r ) 、过样语言 ( p r o c e d u r a ll a n g u a g e ) 等数学谈型平逻辑模型。在广泛使川丁协议实现的形式化规范的方法 中，主要有标号迁移系统l t s ( l a b e l l e dt r a n s i t i o ns y s t e m s ) 和有限状态机f s m ( f i n i t es t a t e m a c h i n e s ) 。在一个l t sr f l 是4 ：区分输入和输山的，输入与输出通常表达成相互作用的状态。 一个具有如是属性的l t s 的子集被称为输入输小迁移系统( 1 0 t s ) ，l o t s 与输入输山状态机 ( i o s m ) 北常相似。不_ j 的是在这个模氆中，当输入不导致任何输出的情况时，也将为这 些状态定义表示状态迁移的边，这些边就表述没有输出的白环。另一个不同的就是l o t s 中的状态集硐l 迁移集部可能足无限的，而i o s m 则都是有限的，冈而i o s m 经常被作为有限 状态机。 本文中使川有限状态机f s m 来描述协议实现。f s m 对丁有限状态空间和可以确定的协 议行为且有足够的描述表达能力，并且可以为删试人员提供最大的测试控制能力。简单的说， f s m 时l t s 的子集。只不过对丁饵个状态迁移，一个输入对应一个或者儿个( 也包括零 个) 不同的输出。 考虑协议的有限状态机模刑( f f s m ) ，它可川一个而元组来表示：m = ( s ，i ，0 ，6 ， ) ， 在这里： s ：有限的状态的集合 s 1 ，s 2 ，s n ) ； 【：仃限的输入的集合 1 1 ，1 2 ，r n ； 0 ：有1 妣的输u5 的集合 0 1 ，0 2 一，o nj ； 6 ： 转移函数，s r s ； ：输【l j 函数s i 0 。 基丁不同的数学模型，人们也提山丁多种形式化描述语言( f d l ) ，概括起来主要有以r 儿种：l o t o s ( l a n g u a g e o ft e m p o r a l o r d e r i n gs p e c i f i c a t i o n 时序规范语言) 、 e s t e l l e ( e x l e n d e ds t a t et r a n s i t i o nl a n g u a g e 扩展的状态转移语占) 干s d l ( s p e c 讯c a t i o na n d d e s c r i p t i o nl a n g u a g e 规范描述沿言) 。其中，l o t o s 和e s t e l l e 是i s o 为协议o s i 模型戍川 开发的但是也可以h j _ 丁其他的领域。e s t e l l e 的理论荩础是有限状态机模型，f n 灶经过p a s c a l 语青加以扩展的描述i f “i 。s d l 丌始址山c c i i t 为捕述交换系统开发的它也可以川r 其 他的场含，它和e s t e i e 川似，足丛j 扩艇的有限状态机模型，它主要是面向剧形方式农达， 同时也支持抽缘数据炎j 儿m 议的形式化描述这一部分的l ：作1 f 常重要它的j e 确性格决定 中田科学技术人学碳：论史 接f 老的测试步骤是否有意义。 2 , 2 基于图形表示的测试理论 m 可以州有向幽g = ( v e ) 来表示。其中顶点集合v = i v l ，vz ，v ) 对应着f s i a 的状 态集合s ，有向边集合e ：( ( v ，v ，；i - 0 ) ：v ，v 。属丁v ，i t 属于i ，0 - 属r0 对廊着f s m 的转移，表示往状态v 收剑输入h ，则迁移剑状态v ，同时输出o - 。在本文中，我们假设g 是强连通的，f s m 是确定f f j 且存在一个输八r i ，使f s m 在任何状态r 能够同到初始状态 该输入不产生任何输出。 在作为黑盒测试的协议一致性溯试中，i u t 是作为一个黑盒存在的，只有对i u t 的输 入和它相应的输山可以分刖的观察控制，i u t 的内部细：仃是不能直接观察的。如果对丁协议 规范中定义的每一个迁移部分别通过了测试，那么我们就认为该实现与规范是一致的。对于 给定的一个代表协议标准的f s m ( 川f s m s 表示) * j i l lf s m 的实现( 刖f s m i 表示) ，通过对 f s m i 进行黑箱测试米确定f s m i 和f s m s 是否一致。我们需要做以下l ：作： ( 1 ) 从f s m s 生成输入输序列s f 手s e ； ( 2 ) 把s i 鹿h j t - f s m i 的输入端； ( 3 ) 在f s m j 的输端观察实际的输山s a ； ( 4 ) 把s a 雨ls e 相比较以确定f s m i 对丁f s m s 的一致性。 作为黑箱测试的结果，f s m i 对j if s m s 的一致性只能通过对观察到的反应进行分析米确 定。7 l ：人多数情况r ，f s m ij ，f s m s 可能在r 列方面4 ：刚： ( 1 ) 状态的数目： ( 2 ) 转移的数日： ( 3 ) 输山和转移功能的实现。 显然由f s m s 推出的s i 币s e 一般不能检测山f s m i 中多余的状态和转移，然而，这些 序列可以检测山其他的所彳丁f s m i 与f s m s 不同的情况。事实上，特征序列可川米识别f s m i 中丢火的状态，而且，丢火的转移利f s m s 的输出与输入功能的不止确的实现会以输山错误 或转移错误显现i 山米。 为了进行协议的一致性测试我们需要检查f s m s 的每一个转移t j k = ( v j ，v k ：i o ) 在f s m i 中是甭得到了u ：确的实现，哉_ l 1 5 7 j , j 二步来进行： ( 1 ) 把f s m i 带剑状态s j ； ( 2 ) 对f s m i 应用输入1 ，检夼其输出是否为0 ； ( 3 ) 检卉剑达的状态魁行为s k 。 所以测试t j k = ( v j ，v k ：i o ) 晌输入序列耍包括： ( 1 ) 一个可变的致意序剁把f s m i 从当前状态带到s j ； ( 2 ) 激励转移r j k 的输入1 ： ( 3 ) 确认f s m 剑达的状态s k 的特征序列。 这样，一个使f s m 从起初始状态扦始，并对f s m 中的每个转移都包含一个测试子序列。 最后义使f s m 同剑初始状态的输入序列就被称为测试序列( t e s ts e q u e n c e s ) 。多种测试序列 生成方法，如t 方法、d 方法、w 方法、u i o 方法等，它们的不同主要是体现在“确认f s m i 到逃的状态s k 的特征序州”，j j | 的。一股u o 方法比较常h j 。 中田科学披术人学f ! 卜论史 2 3 协议的测试序列生成 测试序列是- - t f l 根据饥议规范产生的输入、输山事什序列，它是协议一致性测试的核心 数据。协议一致性测试羽，测试执行系统向i u t 施加输入事r ：序列，接收校验输出事t ，1 ：j 7 列， 检布状态转换，根据输出寸j = 什和状态转换，削定1 u t 的行为是否符合协议规范的描述。本 ， 主要介绑四种基丁f s m 模型的基本的测试序列生成方法，井对它们的特点进行了分析比较。 2 3 1 测试序列生成方法概述 测试序州说明i u t 所戍该表现的逻辑行为，冈此它可以从协议模型中推导山来( f s m 模 型，e f s g 模型，p e t r i 网模耻，c c s 模掣笛) 。目前，理论上比较成熟的测试序列生成算法 都是基t f s m 棋刑，而丝t i ! f s m 等其它模型的测试序列生成方法仍处于研究探索阶段。通 常的做法灶从 e 控制流特一发，商接 _ e 川i 1 ：f s m 模_ 的测l 武序列生成算法。基t f s m 模 掣的测试序列生成算法均要求i u 7 ( 即它的f s m 模型) 具有以下四个特性： ( i ) i u t 的状态数、所能接收的输入事什数、所产生的输出事f l ：数都是有限的、确定的。 这个特陛保证算法是收敛的。 ( 2 ) i u t 有完整性，即它在每个状态r 都能接收所有饥议规范描述的输入事件。输入事什 可以分为两种：核心市仆和非核心事件。j u t 在某个状态r 对一部分输入事t f ：产生响应( 或 产生输出书仆，战政变状态或产，p 输出事什的同时改变状态) ，这些输入事什称作核心事 件，其它输入事f ，| = 称作m 核心啊什，如报文丢弃处理等。1 | 核一f l , 事什是不合法书r i ：的一部分。 f f i m 幽只画出梭心弓干什所引发f f j 转换，田此，测试序列生存算法也只关心核心事什而1 f 核 心事件的测试! j ! j j 留待洲试例乍成时扩充。 ( 3 ) 对丁每个输入市什，如果i u t 产生输山事什，那么该输出事件在给定有限时间内产生。 根据这个特性，i u t 的超时审件造可以削定的，它是否产生输出事件也是可判定的。 ( 4 ) i u t 的每个状态是可达的即它的f s m 【冬j 是连通的。这是所有测试序列生成算法能够 执行的基本前提。 最佳的测试序列应陔满足以r 条f 1 ： ( 1 ) 住满足测试序列路径最人覆盖率的条件f 测试序列蛙短。 ( 2 ) 对廊不同的测试序列，其输序列不同。 注：对丁输入原语相同，而参数不同的情况，这里也当作输入不同。 芙丁基丁- i ? s m 模4 耻f f j 状态转换的测试的详细说明可参考3 2 牾。 瑟t f s m 的测试序列生成方法主要有以f 四种： 9 中圆科学技术人学坝- i ? 论文 ( 1 ) 剧游法( t r a n s i t i o nl o u rf i l e t h o d ) ，也称7 i 办法： ( 2 ) r 分序列法( d is t i n g u is h in gs e q u e n c e s ) ，也称d 方法； ( 3 ) 特征序列法( c h ar a c t e r i n gs e q u e n c e s ) ，也称w 方法： ( 4 ) 唯一输入输出序列法( u n i q u ei n p u t o u t p u ts e q u e n c e s ) ，也称u i o 方法。 t 的优点是生成f | 勺测试序列短，缺点是没有解决“测试的观测陀问题”，也就是没有枪卉 到达的状态，只能发现输饼嵌，而发现不了转换错误，错误检测能力很低。 d z 法、w 方法, f l i ut o 方法都解决了“测试的观测4 r k 问题”。 d 方法的土要优点是能发现故障点，同咎了“剑达的状态是什么状态”的问题但：( 1 ) 火多少f s m 都不存在d 序列：( 2 ) 序列优化方法比较雄，序列艮度比较k ：( 3 ) 一致性测试本 身并不芙心错误的原冈羽位置。 w 方法也同答了“到达的：状态是什么状态”的问题，它的优点是适合丁二描述1 r 完稀的自 动机，能发现比较复杂的锚议，但w 方法人人加长了测试序州，这是它的最人缺点。 实际中，很多人都业倾m 丁采j i j u m 方法。u i o 方法同答了“剑达的状态是否为状态s ” 的题。u i o 序列的主要优点7 i ：( i ) f i | 丁u i o 序列只是d 序列或者w 序列的子集，所以u i o 序 列要比他j 短得多：( 2 ) 儿乎所有的f s m 都存任u i o 序列，闪而它具有普遍适用的特点。 u i o 序列和w 序列相结含的方法被认为是一种理想方法：如果f s m 的某些状态找不剑u 1 0 序列，则川w 序删代替。 2 3 2t 方法 t 方法的基本思想造遍历状态机所有的变迁。 法保证r 生成的测试序列具彳最小的开销。对蚓 生成测试序列 a y ，b x ，“y ，“z ，c y ，b z ，“y ， f 、 av u y a r 和d a h b u r a 借助。j ：1 一国乡村i i 1 5 路算 2 一i 所示的有限状态机，通过t 方法可以 a z 。 h 2 if s m 示倒一 t 力法址凹种丛f s m 楔删的测试序列生成方法中展简单的一种方法但它没有执行前 而捉刮的测试步骤3 ，也就赴没有验证曰的状态，冈而其错误检测能力娃四种测试序列生成 方法中最低的。如果i 划2 “l 所示的f s m 被实现为h2 2 所示的f s m 上述测试序列就无法 检测；这个错误。 ( j 中国科学技术夫学颂，1 论文 2 3 3d 方法 图2 - 2f s m 示例 幽2 - 3f s m 示例三 d 方法的主要思想是对每个状态发送相同的输入序列，通过各臼不同的输出响应序列判 断当前状态。f 面以幽2 - 3 所示的f s m 为例，介纠采j l jd 方法生成一致性测试序列的步骡： ( 1 ) 确定区分序列( d 序列) ，要求每个状态对该序州的响应不同于其它状态。一个满足 要求的d 序列为 a ，c a 。各状态的相廊输山序列为： $ 状态1 x ，y ，x j 状态2 * y ，y ，x 牢状态3 * y y ，z 1 $ 状态4 * f x y ，z ) 十状态5 * f z ，y ，x ( 2 ) 洲试f s m 中的每个状态s 。测试序列由二部分绑成：( a ) 引导序列；( b ) d 序列( 带 下划线标记) ：( c ) 同步序列r i n u l l ( 川丁把f s m 的状态恢复至初始状态) 。 a 测试状态1 十f a x ，c y ，a x ，f i n u 1 ) $ 测试：状态2 * c y ， i x ，h y ，a y ，c y ，a x ，r i n u 【l 测试状态3 * c y h z ，a y ，c y ，a z ，r i n u 1 $ 测试状态4 e y ，a x c y ，a z ，r i n u l l ) 中周科学 点术人学坝i 二论文 测试状态5 * f c y ，a x ，a z c y ，a x ，r i n u l1 】 ( 3 ) 测试f s m 中的每个状态转换( s 】，s j ，i l o ) 。测试序列由四部分组成：( a ) 引导序列； ( b ) 待测转换i o ( 带下划线标记) ；( c ) d 序列：( d ) 同步序歹t r i 。 序测试状态转换( 1 ，1 ，a x ) ( a x ，a x c y ，a x ，r i n u l l * n 试状态转换( 1 ，4 c y ) c y ，a x c y ，a z ，r i n u l l ) 序测试状态转换( 2 1 ，a y ) c y ，a x ，b y ，a y a x ，c y ，a x ，r i n u l lj 测试状态转换( 2 ，3 ，b x ) ( c y ，a x ，h y ，b x ，a y ，c y ，a z ，r i n u l 【) 胁测试状态转换( 3 ，5 ，a y ) e l y ，l a x a y ，a z ，c y ，a x ，r i n u l l l 测试状态转换( d ，3 ，b z ) c y ，b z ，a y ，c y ，a z ，r i n u l l 丰测试状态转换( 4 ，5 ，a x ) f c y a x ，a z c y ，a x ，r i n u l lj 十测试状态转换( 5 ，2 b y ) c y ，a x b y ，a y ，c y ，a x ，r i n u l l ) 序测试状态转换( 5 ，5 ，c y ) ( c y ，a x ，c y a z ，c y ，a x ，r i n u l t ) $ 测试状态转换( 5 ，l ，a z ) $ c y ，a x ，a z ，a x ，c y ，a x ，r i n u l l d 方法的错误检测能力很高，仅次于w 方法，但测试序列太长，而且人多数的f s m 都 不存在d 序列。如图2 4 所示的f s m 孰不存在d 序列。 2 3 4u i o 方法 图2 4f s m 示例四 实际测试中，我们别转换到达的状态是有所期待的，井1 r 无所知。u i o 的主要思想 是为f s m 。 i 每个状态确定个不同的输入输出序列，通过这些序列中的输入输出关系可以 唯一标识每个状态。 定义u l o 序列：一个输入序列是一个u l o 序列，当对应1 ：该输入序列，状态s 产生的输出 信号不同丁其他任何状态的相庶输山。即 ( s ，x ) ( s ，x ) 对丁s s 成立。 求某个状态s i 的u l o 序列的蟹乖筇沾足 中国科学技术人学顺一i ：论文 。- 。_ _ 。_ 。_ _ 。_ 。_ _ h _ _ 。_ 。- - _ 。_ 。一 算法21 ( 1 ) 建立所有的边标号，1 ，输入输出集的关系： ( 2 ) 对每个状态求出所有 = = 度为一的输入输出序列： ( 3 ) 检布它们是否唯一，如果是，这个状态的u i o 序列就找到了； ( 4 ) 如果不是，对没有u 1 0 序列的状态，考虑长度为2 的输入输出序列： ( 5 ) 从长度为k 的输入输出序列中继续求山长度为k + 1 的输入输出序列，检查它们是否 唯一，直到对每个状态都找剑u i o 序列或者k 度超过2 n 2 。 可求得幽2 3 各状态的u 】o 序列为： u i o ( 1 ) = f c y ，a x ) ，u i o 序列开销为2 ； u i o ( 2 ) = f b x ) ，u i o l f 1 开销为l ： u i o ( 3 ) = a y 。a z ) ，u 1 0 序列开销为2 ； u i o ( 4 ) = b z ，u 0 序列开销为l ； u 1 0 ( 5 ) = b y ，u 【0 序列开销为l ： 注意并状态的u 1 0 序列不足唯一的，女n u l o ( 1 ) 就有 c y ，a x 、 a x ，a x 、( c y ，b z 三种t 可以任选一种，选取的原则是u t o 序列开销最小的。仍然以图2 3 所示的f s m 为例， 介绑采；4 j u i o 方法生成一致性测试序列的步骡： ( 1 ) 确定各个状态的u i o 序列。选取状态1 f 0 5 # j u o 序列如前所述。 ( 2 ) 测试f s m 中的每个状态s i 。测试序列由三部分组成：( a ) 引导序列：( b ) 状态s i 的u 1 0 序列( 带r 划线标记) ；( c ) 同步序歹 i n u l l 。 a 测试状态i ( c y ，a x ，r i n u l i 胁测试状态2 * ( c y ，a x ，b y ，b x ，r i n u l l l 一测试状态3 * c y ，b z ，a y ，a z ，r i n u l l a 测试状态4 c y ，i ) z ，r i n u l l 测试状态s * c y a x ，b y ，f i n u l 】 ( 3 ) 测试f s m 中的每个状态转换( s j ，s j ，i o ) 。输入序列由四部分组成：( a ) 引导序列；( h ) 待测转换j o ( 带f 划线标i 0 ) ；( c ) 状态s j 的u i o 序列；( d ) 同步序p i 。 聿测试状态转换( 1 ，l ，a x ) a x ，c y a x ，r i n u l l , f 0 1 0 试状态转换( 1 ，4 ，c y ) c y ，b z ，r i n u l * n 试状态转换( 2 ，1 ，t t y ) c y ，a x ，b , y ，a y ，c , y ，a x ，r i r ) u 1 1 j 丰测试状态转换( 2 ，3 ，b x ) c y ，a x ，b y b x ，a y ，a z ，r i n u 儿 * n a t 状态转换【3 ，5 ，a y ) 十 c y ，b x ，a y ，b y ，r i n u l 中同科学技术大学坝j ：论史 * n 试状态转换( 4 ，3 b z ) c y ，b z ，a y ，a z ，r i n u l l 肛测试状态转换( 4 ，5 a x ) c y a x ，b y ，r i n u l l 肛测试状态转换( 5 ，2 ，b y ) c y ，a x ，b y ，b x ，r i n u l l 丰测试状态转换( 5 ，5 ，c y ) c y ，a x ，c y ，b y ，r i n u l l 测试状态转换( 5 1 ，a z ) c y a x ，a z ，e y ，a x ，r i n u l l 可以看剑，用u i o 方法产生的测试序列的k 度明最要比p j d 方法产生的短。但并非每个f s m 都 存在u 0 序列，图2 5 所示的f s m 就不存在u 1 0 序列。一个f s m ，如果没有u 1 0 序列，则也没有d 序列。解决的办法足采川f 而介纠的w 方法。 2 3 5w 方法 a ，y i 划2 5 不存在u i o 序列的f s m w 方法包括了两个输入序列! 三w s e t * l i p s o t , 。l s e t 是f s m 最小的特征集，它使得每对状 态能够相且区分。即对不同的状态麻川w s e t 观察到的输出j 幢是能够区分的。p s e t 包括了所 有部分路释，由一个测试树构成它的根结点楚初始状态，而每个变迁只出现一次。例如 对 i 幽2 5 的f s m ，可阻按以r 步骤求得ws e t ： s t e pl ：输e k a ，把状态集合s = f 1 2 ，： ，4 划分为两个予集： ( 1 ) 输出xs 1 = 2 ，3 ) ；( 2 ) 输山ys 2 = l ，4 j ； s t e p2 ：输a b ，把s 1 再细分为两个子集： ( 1 ) 输山xs 1 2 = 2 ；( 2 ) 输f l iys 1 2 = 3 ； s t e p3 ：输入b 把s 2 雨细分为两个r 集： ( 1 ) 输 j x $ 2 1 = f 1 ) ： ( 2 ) 输出y $ 2 2 = 4 ) ； 从而可以锝到w s e t = hb 。何个：队态对该特征序列的输出响j 艇如r ： 1 4 中围科学技术人学坝l ：论义 状态1 ：a y ，b x ：状态2 ：a x ，h x ：状态3 ：a x ，b y ；状态4 ：a y ，b y 。 p s e t 为： e ，a ，b ，a b ，a a ，b h ，b a ，b a b ，b a a 】。其中e 表示空序列。网此，j l j w 方 法产生的图4 5 的f s m 的一致性测试序列为： p - s e t 一s e t = a ，b ，a a ，a b ，b a ，b b ，a h a ，a h b ，a a a ，a a b ，b b a ，b b h tb a a ，b a b ， b