（计算机软件与理论专业论文）ospf协议性能测试的研究与实现.pdf

空罾挝鲎垫盔态堂亟堂鱼途童翅垂 摘要 随着通信技术的迅速发展，i n t e r n e ti 埘络用途的扩大网络规模也随之加 大。大规模的嘲络要求高性能的互连设备，冈此刚络设备的性能问题越来越为 广大m 络建设者所蘑视。为了公正，客观的评价蚓络产品的性能，从而给用厂 的选择提供可信的依据，刚络产品性能测试的重要性也就越来越突出了。 通信协议性能测试方法分为主动测试和被动测试两种。主动测试的优点是 测试的针对性强，缺点是和网络设备实际运行环境有所脱节，刁i 能反映待测设 备在实际刚络中的工作情况。被动测试的方法，弥补了主动测试的这一4 i 足， 冈此将两者结合使用，可以获得很好的测试效果。 本文中研究了有限状态机被动测试的理论和方法，并使用了这些方法，构 造了o s p f 被动测试序列，对两种路由协议软件的有限状态机进行了测试。 本文结合o s p f 协议性能测试的国际标准，对o s p f 其它性能做了测试， 其中包括o s p f 初始化时间性能，l s a 消息处理时间性能。s p f 计算时间性 能，l s a 泛滥时间性能，路由表更新时间性能等，给出了测试结果和测试数据 分析。 本文按照主动和被动测试相结合的思想，构造的测试平台，采用了阱络环 境仿真软件n s 2 的方法。该测试环境的特点是：降低了对组建测试系统的设备 要求，使性能测试可以简便易行的进行；可以很方便的修改测试环境配置和刚 络拓扑结构，提高了测试效率：测试过程可控，测试更有针对性。 关键字性能测试被动测试主动测试o s p fn s v 生崮型鲎撞盔丕堂亟堂焦途塞 5 照盟 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m m u n i c a t i o n st e c h n o l o g ya n dm o r ea n dm o r e u s eo fi n t e r n e t t h es c a l eo fn e t w o r kb e c o m e sl a r g e ra n dl a r g e r l a r g es c a l en e t w o r k r e q u i r e sh i g hp e r f o m a n c en e t w o r k - d e v i c e s ，s ot h en e t w o r k c o n s t r u c t o r sp a ym o r e a t t e n t i o nt op e r f o n n a c eo fn e t w o r k d e v i c e si no r d e rt oe v a l u a t et h ep e r f o r m a n c eo f t h en e t w o r k d e v i c e sf a i r l ya n di m p e r s o n a l y a n dp r o v i d et h ec l i e n t sw i t hb e l i e v a b l e t e s td a t a i ti sm o r ea n dm o r ei m p o r t a n tt oc a r r yo u tp e r f o r m a n c et e s tt ot h en e t w o r k d e v i c e s 1 tc a nb ed i v i d e dw i t ht w ok i n d si nc o m m u n i c a t i o np r o t o c o lp e r f o r m a n c et e s t o n e i sa c t i v et e s t t h eo t h e ri sp a s s i v et e s t t h ea d v a n t a g eo fa c t i v et e s ti st h a ti th a sm o r e p e r t i n e n c ew i t ht h ep r o t o c 0 1 a n dt h ed i s a d v a n t a g ei st h a ti tc a n n o tr e f l e c tt h ep o s t u r e o f r u n n i n gi na c t r u a ln e t w o r ke n v i r o m e n t s o i f w ec o m b i n et h ea c t i v ea n dp a s s i v e t e s t i tw i l lw o r kw e l l i nt h i sp a p e r ，t h ea u t h o rr e s e a r c ht h et h e o r ya n dm e t h o do f f s m ( f i n i t es t a t em a c h i n e ) p a s s i v et e s t ，a n dw i t ht h e s em e t h o d s ，c o n s t r u c to s p f p a s s i v et e s ts e q u e n c e s f i n a l l y i nt h i sp a p e r ，t h ea u t h o rc a r r yo u tp e r f o r m a n c et e s to f f s mo nt w or o u t ep r o t o c o ls o f t w a r e f u r t h e rl n o r e ，t h ea u t h o rc a r r yo u to t h e ro s p fp e r f o r m a n c et e s t sa c c o r d i n gt ot h e i n t e r n a t i o n a ls t a n d a r do fo s p fp e r f o r m a n c et e s tt h e s et e s t si n c l u do s p f i n i t i a l i z a t i o np e r f o r m a n c et e s t ，l s am e s s a g ep r o c e s s i n gp e r f o r m a n c et e s t ，s p f c a l c u l a t i o np e r f o r m a n c et e s t ，l s af l o o d i n gp e r f o r m a n c et e s ta n dr o u t et a b l eu p d a t e p e r f o n n a n c et e s te r e f i n a l l y ，t h et e s td a t aa n da n a l y z a t i o no ft h e s ed a t ai sg i v e n i nt h et e s t ，t h en e t w o r ks i m u l a t i n gs o f t w a r en s 2w a su s e dt os i m u l a t et h et e s t i n g n e t w o r ke n v i r o m e n t w i t ht h eh e l po f n s 2 ，t h er e q u i r e m e n tf o rc o n s t r u c t i n gt h e n e t w o r ke n v i r o m e n tw a sr e d c e dg r e a t l ya n dm a k et h et e s te a s yt oc a r r yo u t i ti sa l s o v e r ye a s yt om o d i f yt h et e s tn e t w o r k i n gt o p o l o g i e sa n dc o n f i g u r a t i o n ，a n dt h ep r o c e s s o f p e r f o r m a n c e t e s ti sf u l l yu n d e rc o n t r 0 1 k e y w o r d s ：p e r f o m a n c e - t e s tp a s s i v e - t e s t i n ga c t i v e t e s t i n go s p fn s v i 空罾挝堂垫盔态堂亟堂鱼途童至墨塑 致谢 硕士学位论文的完成也就意味着我在中国科大8 年学习生活的结束，在此 我要深深感谢曾经给我关怀和帮助的人们。 我的论文是在导师赵保华教授的指导下完成的，赵老师不仅学以渊博，而 且为人_ f 直，治学严谨，从我本科三年级进入计算机系软件工程教研室j 1 ：始， 到现在j 年的漫长时间单，他从学术上剥我的指导，以及言传身教的做人道 理，都让我受益终生。赵老师非常注重发展我们的特长，给我们自由生长的空 间，使我得以在教研室期间广泛涉猎了很多技术。他关心我们的日u 途，对我将 来的职业发展也提出很多宝贵的建议，深深感谢赵老师对我的关怀和教诲! 本教研室的屈玉贵老师，是我不可多得的良师益友，在研究生学习期问， 每次发表学术文章之前，都是屈老师逐字逐句的帮我审阅校对，她孜孜不倦的 好学精神，认真严谨治学态度，深深感染了我，成为我学习的榜样。 本教研室的周颢老师审阅了我的论文，并提出了宝贵的意见，深表感谢 在软件工程教研室学习工作期i 、日j ，和很多同学经历了非常愉快的合作，他 们基础知识扎实，动手能力强，给了我很多帮助，我也从他们那罩学到了很多 东西。教研室学习气氛很浓，举办的多次自由讨论会，让大家分别讲解自己的 研究领域，让我的表达能力得到了很大的锻炼，同时也丌阔了我的视野，丌拓 了学术研究的思路，非常感谢他们。他们是吕欣岩、周晓煜、阳野、林华辉、 柯尧、郭雄辉等。 我研究生阶段大部分时间都是在中国科大华为研究所渡过的，华为研究所 为我们提供了良好的学习工作生活条件，叶国华老师，陈强师傅和任艳丽、顾 晓曼小姐不辞辛劳的为我们提供了强大的后勤保障，衷心的感谢他们! 同时要 感谢深圳华为技术公司中研测试部的各位同仁，我发表的文章和毕业论文很多 思路是来自和他们的合作项目，他们对专业技术的深刻领悟和敬业精神给我留 下了深刻的印象。此外，对文中引用各类参考文献的作者也一并表示感谢! 感谢我的父母，我今天的成绩是二十多年来他们的辛勤培育的结果。我希 望付出自己的努力，能成为他们的骄傲，让他们为我感到欣慰。 最后要感谢和我深深相爱的女友，是她照亮了我的生活，让我感到世界原 来可以如此美好，让我平淡的每一天都变的那么富有生气。谢谢你，亲爱的! “路漫漫其修远兮，吾将上下而求索”，在中国科大学习生活的结束，意 味着又一个新的开始。探索的道路永无止境，我的征途是星辰大海 i v 李越鹏2 0 0 3 年5 月 于中国科学技术大学 生崮型主丝盔盍堂鲍堂焦迨塞筮二重i i 蛊 1 1 本文的研究背景 第一章引言 例络技术在近二二f 年来飞迷发展，随着i n t e r n e t 的迅速普及，删络规模 4 i 断扩大到2 0 0 3 年初，仅我国联刚汁算机主机总数就达到2 0 8 3 万台，上刚 人数达到5 9 1 0 万 1 。国家信息化程度越来越高，电子商务，电子政务方兴未 艾，m 络在人们的日常生活和国民经济中扮演着越来越重要的角色，可以设 想，如果刚络小能正常运行，会给人民生活带来很多1 i 便，使经济遭受晕大损 失。 4 i 幸的是，随着例络规模的增加，出现问题的可能性也在增加。这么庞大 的州络，是靠很多设备连接在一起的，这些设备包括交换机，路由器，集线器 等，嘲络能否正常高效运转，很大程度上取决于这些设备的丁作状况。而刚络 设备通常是通信协议的载体，刚络设备根据各自在刚络中扮演的角色实现了某 些协议，通过这些协议相互配合的丁作，使整个网络协调运转，冈此可以说通 信协泌是刚络的灵魂。 同前，在i t 行业中，从事刚络通信设备制造的食业1 i 少，国外的有c i s c o 等，国内则有华为中兴等。嘲络的建设者，在这么多厂商生产的设备中，要挑 选符合附络要求的产品就成了一个问题，选择的标准垒少应该符合下面几个条 件： 数等 功能要求：产品必须实现用户所需要的功能 规模要求：选择的产品必须符合应用规模的要求，包括其速度，端口 性能要求：对于大型脚络，尤其是骨t 部分，由于承担了大部分的州 络流量，所以对性能的要求就显得尤为蕈要； 对功能的要求，首先体现在m 络设备实现的协议必须和标准规定的一致， 台则“i 同厂商的产品就无法互连互通，这就是所谓的“协议一致性”问题。对 规模的要求和对性能的要求实际上是且相适应的，大型网络相对小型恻络来 说，对性能的要求就会苛刻一些。 对网络产品的这些要求，厂商会提供一些数据供用户参考。但出于商业的 原因，厂商对产品的评测并不具备能让用户普遍认同的权威性，尤其是性能测 试数据，厂商毫无疑问的会采用各种手段在有利自己的条件下测试，从而获得 具有宣传意义的数据。为了得到全面，客观，公正的测试结论，就需要第三方 用能得到普遍认同的标准对产品进行测试，这就是通信协议标准测试。 此外，在网络协议和产品的开发设计阶段，进行协议测试，可以发现协议 实现中的错误，提高协议实现的可靠性，从而保证数据网络尤其是i n t e r n e t 的高 效运行。目前，协议测试仍远远不能满足网络技术发展的需求。大量未经充分 测试( 尤其是第三方测试) 的网络产品( 包括协议实现的硬件与软件) 已经被 第1 页共7 4 页 史崮型堂垫查盔堂亟主堂焦途塞 筮二童i 直 广泛使用这给i 叫络的运行质量带来潜在的威胁。 由于通信协议测试是由第二方进行的，而且为了保持公正客观，它刁i 府参 考任何具体厂商的实现，它的所有测试理沦依据，测试方法，只能来源于已公 开发表的通信协汉标准，通信协 义丁程的理论和方法。冈此，从某种程度上来 说，通信协议完整测试的过程，也就是把待测协议简单的实现了一遍。所以协 泌t 程中的方法都可以应用到协泌测试中。 1 1 1 通信协议工程化开发方法 用丁程化的方法开发一个通信协议所经过的流程如图 1 一l 】所示( 2 。 图1 1 迎f 占协议开芨过程 、通蔼协议的开发流程从设汁开始，在这个阶段，开发人员根据需求，对包 括p d 镪格式，协议机制，服务原语等在内的协议元素进行设计。 协议描述阶段，对自然语言表达的协议进行形式化描述。这样做的好处和 必要性在于，自然语言是不严格，有二义的，、而用形式化语言描述的协议是明 确，无二义的。协议形式化描述语言包括f s m ，m s c ，s d l ，f d l ，l o t o s ， e s t e l l e 等。 协议验证是协议工程中非常重要的一个环节，它的作用是对所描述的协议 验证其正确性，分析其性能。协议验证是和协议描述紧密相关的，用什么方法 验证协议，取决于描述协议的形式化语言和模型。在验证中发现的问题，要回 到设计阶段去修改。 经过验证确认的协议，就可以进入开发流程了，这个阶段根据协议的形式 化描述，产生协议实体( 软件或硬件) 。 最后是对实现的通信协议软硬件进行测试和维护。由于协议测试是本文论 述的主要内容，所以在这里对这部分稍加论述，具体内容请参考相关章节。 第2 页共7 4 页 芋 生崮型堂披苤太主塑堂僮途塞箍二重i 直 1 1 2 通信协议测试 测试的日的按j ( 汁e n m lf 1 f 吣o i - sn - ( ( t h c ，u t s o f tx 、ct e s tif l g 5 l | i f l , j 脱l i ： ： 测i 代址为j 位t - e t 削父i n i 4 k f j ：p d i 0 过科 个阳0 测试川俐越nr 亡能发蜕个令术发j 妣门 m 父 一个成功的测试是发现了全今未发现的错误的测试。 上面这些原则虽然是针对程序测试提出的，但对于通信协议测试也有其指 导意义。协汉测试的目的旨在榆验所实现的协议是否完全和协议规范所描述的 内容一致( 协议一致性测试) ，协议的性能是台符合用广网络的要求( 性能测 试) 。测试系统的设计和测试套具的产生是协议测试所要解决的两大问题。测 试系统设计晕点解决测试方法$ t j n 试系统的结构问题，测试套具的产生要解决 测试“彻底性”，和“标准化”问题，解决测试套具自动生成问题。协议测试 是日前协议t 程中难度最大，实现最困难的一个课题，在近年来已经逐渐成为 热点。 传统的测试方法是测试系统根据测试项日，主动句协议实现发出消息、，并 观察待测实现的反应，但是这种测试对于复杂协议存在局限性。在嗍络协议t 程学中，为了对待测实现进行榆验，也可以使用监控诊断的方法。作为一种辅 助的测试手段，监控诊断通过观察协议实现的运行情况来榆测协议是否运作正 常。“被动测试”f p a s s i v et e s t i n g ) 就是一种监控诊断的方法，其概念最早在7 0 年代初被提出，相对地，称传统的测试为主动测试( a c t i v et e s t i n g ) 。被动测试是 另一种测试思想：通过监听来采集数据，通过分析数据来发现协议实现中存在 的错误。监听是从底层收集数据的方法，收到的数据用于验证系统的特性所 以称为被动测试。从目前的研究来看，被动测试比较适用于测试h 络动态行 为，如路由器中路由信息的测试，t c p 协议中的拥塞控制等。很多学者对此进 行了研究，先后提出了提出了在刚络中设置观察点，收集i 叫络信息，进行嘲络 故障检钡j j 4 1 ，并将这个方法应用于网络故障管理上；还有基于f s m 模型的有 效的算法 5 ，以及将被动测试的方法应用于刚络故障的发现和定位的设想 6 7 等。 由被动测试不影响网络设备的正常工作，特别适用于发现正在运行的州络 上的故障。设想将被动测试的方法应用于网络故障的发现和定位，目前的工作 大部分集中在理沦方面。参考现有的文献和研究成果，被动测试比较适合于下 面几方面的应用： 测试正在运行的实际网络设备。正在运行的设备不能将其取出，被 动测试能够保证在不干扰网络正常运行的情况下对设备进行测试： 测试系统的动态行为，比如路由器的路由表。路由信息的交互具有 随机性，不容易通过模拟生成主动测试例； 第3 页共7 4 页 虫国型堂拉苤太堂熊堂焦论塞笠= 室曼l 宣 测试复杂的系统，例如带请多协议变量的系统、实时系统。现有的 测试方法要测试系统行为，复杂度很高而且往往4 i 实用( 测试序列 长度常常是状态数的指数，而复杂系统的状态数日很大) ；而被动 测试比较适合这种情形： 帮助生成主动测试的测试例。被动测试有较为通用的测试方法，是 一种易于实现的测试手段。被动测试能够提供一定的错误覆盖，可 以帮助生成主动测试的测试例； 被动测试和主动测试的箨有优势，虽然它们在理沧和实践上都还存在着很 多没有解决的问题，但如果能够融合它们各自的优点，就可以取得很好的效 果。用这种方法进行的通信协议性能测试，在刚络管理，i 叫络优化等领域有良 好的应用前景。 本文作者选择这个题i q ，希单能用主动测试和被动测试相结台的方法，探 索通信协议性能测试的途径，为这种方法麻用于通信协议性能测试方面做一些 有益的探索。 1 。2 本文的主要内容和贡献 奉文综述了通信协议性能测试的一般方法，着最讨沦了被动测试利主动测 试相结合的方法在通信协议性能测试中的应用。 在理论研究的基础上，作者分析了影响路由协议o s p f 性能的冈素，提出 了o s p f 性能测试的一般方法，以及具体的测试项目和相应的测试过程。 结合上述研究，本文构建了o s p f 性能测试平台，对几种o s p f 协议实现 进行了测试，给出了测试结果，并对数据进行了分析。本文提出的测试霄法和 测试结果对评估实现o s p f 协议的路由器产品的性能有一定指导作用。 。 1 3 本文的章节组织 本文共分为七章。 第一章概论工作背景。 第二章介绍通信协议性能测试的一般理沦和方法。 第三章着重分析了o s p f 路由协议，讨论了o s p f 性能测试的目标，为后 面的测试工作打下了基础。 第四章结合o s p f 协议，给出了o s p f 协议性能测试的具体实现方法，介 绍了性能测试中所用的网络拓扑环境。 第五章中构建了o s p f 协议性能测试平台，介绍了使用模拟测试网络环境 进行性能测试的方法，给出了钡5 试平台的组网环境。 第4 页共7 4 页 虫崮型堂技丕太堂亟堂焦论塞笺二童i l 壹 第六章列出了测试结果和对测试数据的分析。 第七章是结论和展望。 第5 页共7 4 页 空圈型堂垫查丕堂熊鲎焦途塞箍三童丝能测达鲢二丝堡途 2 1 引言 第二章性能测试的般理论 奉章主要沦述了通信协议性能测试的一般方法，被动测试的基奉理论， i e t f 关于性能测试的标准r f c 2 5 4 4 中规定的测试原则和指标等。这一章的内 容是奉文的理论基础。 2 2 被动测试的研究背景 协议测试方法大体上可以分为主动测试和被动测试两种，如图2 u 2 2 。 所谓主动测试是指测试者( t e s t e r ) 和待测设备( d e v i c eu n d e r t e s t ，d u t ) 相 连接，主动向刚络中发送特定的数据包来分析d u t 的行为。在主动测试中， 雠t 仅与t e s t e r 连接，t e s t e r 根据所要测试的日标，与d u t 通信，同时检查 d u t 钓输入和输出情况，d u t 的运行是在t e s t e r 的引导下进行的。而被动测试 是由t e s t e r 监测网络中的数据，通过分析采集到的数据判断d u t 的行为。在被 动测试中，d u t 运行在一个实际的刚络环境中，和其它网络实体通信，t e s t e r 并1 i 对d u t 和网络的运行施加任何影响，不影响d u t 的正常t 作，也不给网 络造成额外的信息流，被动测试可以用作在线测试，监控设备的运转是否正 常。 裳 接 t es t e r 避接 收发 。t 图2 1 主动测试示意图 主动测试和被动测试各有优势，在实际测试中，应该发挥它们各自的优 势，结合使用。在协议设计阶段，和协议一致性测试中，往往使用主动测试， 冈为这时候需要有目的的使d u t 进入某些状态，以测试其实现的正确性或一致 性；在性能测试中采用被动测试，因为本文描述的是0 s p f 性能测试的理论和方 法，所以有必要对被动测试做更加详细的解释。 早在七十年代，就有人提出了被动测试这个概念，用于测试集成电路。而 近年来，随着计算机网络的普及，各种网络协议的测试成了热点。传统的协议 测试以主动测试为主，日趋成熟，但是主动测试主要适应于在网络协议和产品 的设计试验阶段的测试，而不能在产品运行阶段发现错误，也不能适应复杂的 动态行为。而被动测试较好的适应了这些情况，并且在近年来得到了一些应 第6 页共7 4 页 主崮型堂垫丕盔堂亟堂焦途塞筮三重馑鳇型这的二避堡途 用所以对被动测试的研究慢慢成为热点。早在1 9 9 6 年，贝尔实验窜的科学家 们就提出了用棼动测试方法测试有限状态机的一些基本原则和方法 8 ；在1 9 9 7 年开始了用被动测试方法测试有限状态机的t 作【9 】，提出在网络的被动测试中 采用c f s m 模型，讨论了被动测试的错误管理问题，【6 简介了在f s m 和 c f s m 模型上进行被动测试的错误管理概念，并给出了一些示例。 l 芏| 2 2 被动测试示意瞄 2 3 被动测试在状态机测试中的应用 2 3 1 有限状态机模型 0一 有隈状态机( f i n i t es t a t em a c h i n e ) 可以用一个四元组表示 定义一： m = ( i ，0 ，s ，6 ， ) ，其中 i 是输入元素集， 0 是输出元素集， s 是状态集， 6=sxi s 是状态转移集， =sxi 一0 是状态转移伴随输出元素集。 第7 页共7 4 页 有限状态机可以表示为一个状态转移图，图 2 - 3 给出了一个例子，该状 态机的四元组定义如下： s = s 。，s 。，s 。) ，i = a ，b ，0 = ( 0 ，1 ， 8 = ( s 。a ) 一s f s 2a ) 一s 2 f s 3a ) 一s 3 s lb ) 一s ： s 2b 一s 。 ( s 。b ) 一s 。) = s 。a ) 一0 ( s 2a 一1 f s 。a ) 一0 ( s 。b ) 一l 术大学硬士学食 图2 3 有限状态机模型 第8 页共7 4 页 虫崮型鲎熊莶丕堂亟堂焦途塞箍三童性能型达鳆二照堡i 金 2 3 2u i o 序歹0 在黑盒测试条件下，由于只能从外界向状态机输入，并观察其输出，而4 i 知道状态机内部的t 作情况，也4 ：知道状态机当前是什么状态，转移到了什么 ：映态，所以必须找到一种方法仅从输入输出序列中就可以推断出这些信息。 u l o 序列就是一种很好的方法。 定义二有限状态机的合理输入序列 序列x = x i x 2 x 。( x i i ) ，如果满足对每一个x i ，存在h ，o 、s i s 和a i i ，使得x = 6 ( s ，a ) b = ( s ，a ，) ( 其中i = 0 ，l ，n ) ，则称x 为有限状 态机m 的一个合理输入序列。 定义三状态等价 对一个输入序列x = x i x 2 x 。， 的，当且仅肖 ( s 。x ) = ( s 。，x ) 称两个状态s is j 在这个输入序列下是等价 即他们对x 的输出序列是一致的。 由定义二可知，一个输入序列x 对应于状态集s 的一个等价类划分，称为 n ( x ) 。 定义四u i o 如果对于某个输入序列x ，in ( x ) ，= ls ，则称x 是有限状态机m 的唯一 输入输出序列u i o 。 用u i o 序列的方法，我们就可以在完全不知道状态机当前状态的情况下 通过输入u 1 0 ，观察状态机的输出序列，来确定状态转换的轨迹。 2 3 3 状态机的等价问题 状态机的等价问题是状态机测试中一个很重要的方面，尤其是在黑盒测试 中，当测试者不了解状态机的定义，需要通过测试给出状态迁移图景时。状态 机的等价定义如下： 定义五： 状态机m = ( i ，o ，s ，6 ， ) 和m = ( i ，o ，s ，6 ， ) ，如果存在映射由，使 得对于任意s s ， a e i ，总有6 ( 由( s ) ，a ) = 中( 6 ( s ) ，a ) 和( 巾( s ) ，a ) = ( s ，a ) 成立，则称状态机m 和m 是同构的。特别地，如果中是一一映射 函数，则称状态机m 和m 是等价的。 2 。3 4 状态机测试的五个问题 状态机测试的过程就是我们从输入输出中推断某些信息的过程，输入序列 有两种：预置性的和适应性的。预置性测试是指测试输入序列事先已经设计好 适应性测试输入序列是指下一个输入符号是什么取决于上一次输出的结果，即 第9 页共7 4 页 虫罾型堂热盔盔主题堂丝论塞箍三童性篚型这的= 篮型淦 在测试过程中动态生成输入序列。显然适戍性测试比预置性的测试要更通用一 些，前者实际上就是一颗决策树。状态机测试问题可以分为如下几类： 1 己知状态机的完整描述，小知道当前状态是什么，要确定测试序列输入后 的终止：状态是什么： 2 已知状态机的完整描述，f i 知道当前状态是什么，要确定当前状态是什 么： 3 已知状态机的完整描述，小知道当前状态是什么，要证实状态机当前在某 个状态上； 4 状态机是黑盒( 即卅i 知道其描述) ，但已知另个状态机a 的完整描 述，确定待测状态机和状态机a 是否等价： 5 状态机是黑盒，要求给出这个状态机的描述。 对上血每一个测试需求，都有若t 个测试问题，它们是 这样一个测试序列是否存在? 如果存在，它至少需要多长? 判断是台存在测试序列，找到这种钡0 试序列，并选出其中最短的一 条的算法及其时间复杂度是多少? 2 3 5 自引导( h o m i n g ) 序列 、盘f ? ，在凝态机测试中，我们经常会碰到这种情况：状态机的初始状态我们是刁i 知遘韵i 。输入一个测试序列后，我们需要通过观察状态机的输出序列，以确知 它盼终止状态，也就是上节中提到的问题1 。这个输入测试序列就称为自引导 序夕1 j ( h o m i n gs e q u e n c e ) 。自引导序列问题，目前已经完全解决了，可以参考文 献 1 0 】 1 臼。 从上面的定义可以看出，h o m i n g 序列测试过程是一种被动测试过程。 h o m i n g 过程开始的时候，认为被测实现可能处于状态机所有状态中的任意一 个。通过4 i 断监听被测实现的输入输出，排除一些被测实现目前不可能处在的 状态，从而使被测实现可能处在的状态的集合的规模逐步变小。当p o s s i b l e s t a t es e t 里面只有一个状态的时候，被测实现所处的状态被确定，此时 h o m i n g 过程完成。 2 3 6 用h o m i n g 算法进行被动测试 以图【2 4 】所示的状态机为例，进行h o m i n g 算法。首先，在未进行任何输 入输出的情况下，有限状态机的当前状态是不确定的，或者说s l ，s 2 ，s 3 都有可 能。接着观察状态机的输入输出，如果输出的是0 那么证明初始状态是s 1 或 s 3 ，转移状态是s l 或s 3 ；如果输出的是1 ，则初始状态肯定是s 2 ，转移状态是 第1 0 页共7 4 页 虫国型堂蕉莶盔堂亟堂焦途塞笠三重世鸶型这鲍二篮堡途 s 2 。对于输出为1 的情况，显然马上就可以判断出有限状态机的状态转移轨 迹，h o m i n g 过程结束。对输出为0 的情况，虽然还是不能确定，但至少不确定 的范围变小了，由原来的( s l ，s ：，s 3 ) 变成了( s l ，s 3 ) ，以后就再分辨是这两个状 态中的哪一个就可以了。在( s i ，s 3 ) 不确定的情况下，输入b ，观察输出如果是 0 ，则原状态一定是s i ，如果输出是1 ，则原状态一定是s 3 ，这样就可以做到完 全把s i ，s 2 ，s 3 区分开了。完整的决策过程可以用图 2 5 表示。 通用的h o m i n g 算法如图【2 6 所示，摘自参考文献 9 。l 是当前可能状态 集合，初始化为所有状态。算法不断循环，每次观察一对输入输8 ( i ，o ) ，检查l 中的所有状态s 。，如果存在s 。使得o = ( s 。，i ) ，则用s 。替换l 中的s 。；去掉 l 中那些在输入i 下没有可能发生转移的状态。如果此时l 为空集，说明输入非 法，算法报错退出；如果l 中只有一个状态，说明找到了h o m i n g 序列，算法 正常退出；如果l 中的状态数多于一个，循环继续进行。 由上面的分析可以看出，该算法除了处理状态确认以外，还能对非法的输 入做出反应。 t? ”游 ， 。 a 1 图2 - 4 状态转移图 01 s 1 s 3j s 2 01 s ls 3 f s 2 ) 0l ollloolol ( s 2 ) s l ：s 2 j ( s 3 jt s 2 s 3 l s l ：s 3 ! s 1 ) s 2 图2 - 5h o m i n g 决策过程 第1 1 页共7 4 页 炎蘧 生崮型堂垫丕态堂亟堂焦淦窒熊三童世能型达笪二篮堡睑 a l g o r i t h m1 ( f a u l td e t e c t i o no fd e t e r m i n i s t i cm a c h i n e s ) + + m e t - as p e c i f i c a t i o nf s ma a n da ni os e q u e n c ef r o ma ni m p l e m e n t a t i o nf s mb “i l 。“k 几i ： o u t p u t w h e t h e rbi sn o to b s e f v a “o n a l l ye q u i a l c n tt oa b e g i n = s l ，j ；p o s s i b l ec u r r c n | s t a t e s ， f o r ( k = l 1 d o i c h e c ke a c h i op a i r + ， f o r l ，= it o ”t 1 ) d o ，c h e c ke a c hs t a t e i nl + i f ( nl m s i ，“女) ) r e p l a c es fh y6 ( s 1 u t l i nl ： e n d r e m o v er e d u n d a n ts t a t e si n ： i f l 耋o ) f e t u f mf a u l t 4bi sf a u l t y + e l s e i f f ；l f i ) g o t of a u l td e t e c t i o n ：ph o m h _ i 8s e q u e r a c ef o u n d | e l s e e n d 图2 - 6 h o m i n g 算法 2 3 7n f s m 下的h o m i n g 算法 a l g o r i t h m2 ( f a u l td e t e c t i o no fn o n d e t e r m i n i s t i cm a c h i n e s ) i n p u t as p e c l f i c a t o nn f s ma ，a n da ni 0s e q u e n c ef r o ma ni m p l e m e n t a t i o nn f s mb 口1 o 】a k l o k ； o u t p u t w h e t h e rbi s n o to b s e r v a t i o n a l l ye q u i v a l e n tt oa b e g i n l = l ，h ：+ p o s s i b l ec u r r e n ts t a t e s4 f o r 征= it o * ) d o c h e c ke a c h l l 0p a i r f o r ( i = o ” 、d o ，c h e c ke a c hs l a t e i n l d e l e t es if r o m ： f o re a c hj a ( s ，“t ，o c ) d o i n s e r tj l n e n d r e m o v em d u n d a n ts t a t e sj n ： j “l9 0 ) r e t u r nf a u l t ；pbi sf a u l t y | e n d e n d e n d ， 图2 - 7 n f s m 的血喀过程 第1 2 页共7 4 页 虫崮型堂筮盔盔堂亟主堂焦焦塞差三童焦熊型这的二丛堡j 金 前面讨沦的有限状态机都是确定的，即对某个特定状态对某个特定的输入 总有确定的输出和转移状态。所谓彳i 确定的有限状态机( n f s m ) 是指状态机 中某个状态对特定的输入可能有若t 个输出和转移状态。所以h o m i n g 过程 后，可能状态集有可能非但小会缩小，反而会变大。n f s m 的被动测试算法如 图 2 - 7 所示。 是当前可能状态集合初始化为所有状态。算法巧i 断循环，每次观察一 对输入输出( a ，o ) ，榆查l 中的所有状态s i ，首先从l 中删除s i ，将属于( s ，ak ， o k ) 的s 加入l 。然后从l 中删除冗余的状态。如果此时l 为空集，说驯输入非 法，算法报错退出：如果l 中只有一个状态，说明找到了h o m i n g 序列，算法 正常退出；如果l 中的状态数多于一个，循环继续进行。 2 3 8 同步序列 定义六： 一个输入序列x 称为同步序列，当且仅当对于任何初始状态s i ，s j ，“ j ) ，x 都将其带入相同的终止状态，即6 ( s i ，x ) = 6 ( s j ，x ) 。 由定义可知，同步序列必定是h o m i n g 序列，反之刁i 成立。一个状态机来 说，它4 i 一定存在同步序列，所以首先要判断同步序列是否存在，并将其构造 出来，采用如下算法。 定义七 对于一个f s m 的状态转移图g ，定义它的辅助图g x g ，其结点为( s 。s j ) 的 无序对( s 。，s i s ) ，结点( s ，s j ) 和( sp ，s q ) 之间有一条标有a ( ai ) 的有阳边，当且仅 当在g 中有从s i 到8 p 和从s i 到s q 并输出a 的转移。 图【2 4 】所表示的有限状态机的辅助图如图 2 8 】所示。 ( s 2 s 2 ( s 3 ，s 3 ) ( s 1 ( s 2 ，s 3 ) 一( s 1 s 3 ) b 图2 - 8 有限状态机的辅助图 第1 3 页共7 4 页 虫围挝堂挞鲞太堂亟堂丝迨塞筮三童丝能型这的= 篮理j 垒 容易知道，如果一个输入序列x 能使状态机从状态s 或s 转移到同一个状 态s 。，当且仅当在辅助图上有一条从( s s ，) 到( s ，s ) 的路符。如果一个状态 机的辅助转移图有同步序列，那么从任意一个结点( s ，s ) 到某个结点( s ，s ) 都有一条路静，反之也成立。也就是说可达性条件对同步序列的存在性是充分 必要的。而可达性条件榆验起来比较简单所以可以用它来代替同步序列存在 性的榆验。 构造同步序列的算法如下。 选择两个状态s s ，在轴助图中找到从( s 。，s ，) 到( s ，s ，) 的最短路稃， 将这条路径上的输入序列记为x ，。显然6 ( s + ，s ) = 6 ( s ，s ) = s 。并且s ， = 6 ( s ，x ；) 中的状态巧i 超过n 一1 个。类似地，检查s 。，取其中两个卅i 同的状 态，麻用一个输入序列x = ，x ：将这两个状态转移到同一个状态，从而获得新的 状态集s ：，易知s ：中的状态个数少于n 一2 。蕈复上述过程，直到得到单状态集 合s 。= s ) ，由于g x g 满足可达性条件，所以这个结果总是可以得到的。把上 述过程中得到的输入序列孙x ，x 。连接起来，所得到的序列x 就是同步序 列。 从图 2 - 8 中，从( s ：，s ；) 可以到达( s ：，s ：) ，输入序列是x 。= a ，于是我 们有s = s ，s ! = 6 ( s ，a ) ：又，从( s ，s ：) 可以到达( s ：，s 二) ，输入序列是 x = = b 于是我们有s ! = s ：) = 8 ( s ，b a ) ：于是将x 。和连接起来，我们就得 到一个同步序列x = a b a ，使得6 ( s 。，x ) = s = ) 。该算法的时间复杂度是 0 ( n + p n ：) 。 2 3 9 状态确认和状态验证 2 3 a 节中提出的问题2 ，也就是状态确认问题。在问题1 中我们是要确定 在测试结束时f s m 的状态，而问题2 要求确定测试开始之前的初始状态。相对 于问题l 来说，问题2 更为困难，冈为在状态转换的过程中，有可能引入二 义有可能丢失初始状态的信息并h i 可恢复。所以问题2 并不总是有解的。如 果对有限状态机m ，存在一个输入序列x 可以解决问题2 ，则称序列x 为有限 状态机m 的判别序列( d i s t i n g u i s h i n gs e q u e n c e ) 。从判别序列的定义可知，每一个 判别序列，必定是个h o m i n g 序列。 状态确认问题，也就是2 _ 3 a 节中提出的问题3 ，是在知道状态机的完整描 述的前提下，假设状态机的初始状态是s i ，要求证实这个假设。同问题2 一 样，问题3 也并不总是有解的。问题3 的解也就是u i o 序列。 判别序列和u i o 序列是问题2 和问题3 的解，此外，这两种序列还为其它 很多重要测试提供了有力的方法。 2 3 10 构造判别序列算法 如前所述，测试序列分为预置序列和自适应序列。 定义八预置判别序列 第1 4 页共7 4 页 生巨型堂撞丕太堂亟堂焦i 金塞 簋三童丝能型达鳇= 股垄盈 对于给定的有限状态机m ，如果状态机任意两个不同的状态s i ，s j ，对某 个输入序列x 的输出序列都不同，则称输入序列x 为有限状态机m 的为预置判 别序列。 定义九自适应判别序列： 一个自适应性判别序列是一棵决策树t ，其中包含且仅包含n 个叶结点： 其它内部结点标注了输入符号，树的各边标注了输出符号；叶结点标注了f s m 的状态，满足以下条件： 不o 从同一个普通结点( 非叶结点) 引出的各边上标注不同的输出符号； 对每个叶结点，如果x ，y 分别是由该结点形成的输入，输出符号，并且 从根结点到该叶结点的路径都标注了输出符号，且该叶结点标注为s i ， 则y = ( s i ，x ) ； 序列的长度等于树的高度。