（计算机软件与理论专业论文）动态协议一致性测试及其可靠性问题的研究.pdf

摘要 协议一致性测试的目的是检验待测实现是否完全与协议规范所描述的内容 一致。协议实现是一个复杂的实体，完全测试协议在时间和开销上几乎是不可实 现的，所以如何在测试的完全性、彻底性和测试的时间、开销上做到平衡是一个 需要研究的问题，事实上测试的本质就是在有限的预算范围内要求测试达到给定 的覆盖度。 本文所要研究的动态测试不同于软件工程中的定义，而是在协议测试中，按 照测试集的执行和生成情况，将协议的一致性测试分为静态测试和动态测试两 类。所谓静态测试就是测试集在整个测试期间不会被改变，而且测试集中的每一 条测试序列在执行过程中按照一定的顺序相互独立的逐条执行。所谓动态测试是 指测试集的执行和生成都是随实际测试情况而动态改变的。 当前使用的大部分协议一致性测试方法都属于静态测试，在这种测试中人们 追求的目标是使用尽可能短的测试序列发现尽可能多的错误，但由于协议相关性 对测试的影响，使得静态协议一致性测试存在两方面问题：1 执行效率低：2 可 能无法达到理想的实际测试覆盖度。为解决这两个问题，本文将提出一种动态协 议一致性测试，并围绕这种测试所遇到的相关问题展开研究。 本文的研究工作主要集中在以下几个方面： ( i ) 协议的相关性 协议规范的功能组内和功能组间，以及测试序列内和测试序列间都存在相 关性，这些相关性是导致上述两个问题的直接原因。为此本文从依赖性的角度揭 示相关性对协议一致性测试的影响，并给出了相应的解决方案，从而使协议的一 致性测试达到理想的测试效果。 ( 2 ) 动态协议一致性测试 动态协议一致性测试主要用于解决上述两个问题，因此它应该由两部分构 成：静态测试集的动态执行用以提高测试集的实际执行效率：测试用例的动 态生成用以扩大实际测试的覆盖度。 本文首先在完全定义的有限状态机模型下讨论动态协议一致性测试，然后把 它扩展到对非完全定义的有限状态机的测试。 由于静态测试集对动态协议一致性测试的效率有很大的影响静态测试 中国科学技术大学博十学位论文摘要 集发现错误的能力越大，则动态协议一致性测试获得的信息就越多，效率就越商， 因此本文通过对测试对象的变更，使用动态协议一致性测试方法来评估测试集是 否是m 完全的，如果非m 完全，则自动补充新的测试序列，直到它构成m 完全。 ( 3 ) 一致性测试的可靠性 由于一致性测试并不能保证对待测实体可计算集的穷尽，所以协议即使通过 一致性测试也不能保证它的可靠性为1 0 0 ，因此本文从统一的协议一致性测试 方法入手，提出种新的协议一致性测试的可靠性架构，然后以均一假设和正则 假设为例，说明可靠性的计算过程，并在“零错误”条件下，对于原始的均一假 设给出了一种更简单的计算方法。 关键字：协议测试，一致性测试，动态测试，协议相关性，可靠性 i i 一! 旦型兰垫查查兰竖主兰垡堡塞垫薹 a b s t r a c t t h ep u r p o s eo fp r o t o c o lc o n f o r m a n c et e s t i st o v e r i f y w h e t h e rt h e p r o t o c o l i m p l e m e n t a t i o nc o n f o r m st o t h e p r o t o c o ls p e c i f i c a t i o nc o m p l e t e l y t h ep r o t o c o l i m p l e m e n t a t i o n i sa c o m p l e xe n t i t y , a n d i ti s i m p o s s i b l e t ot e s tt h e p r o t o c o l c o m p l e t e l ya n dt h r o u g h o u t ，s oh o w t h ep r o t o c o lc a r lb et e s t e d p e r f e c t l yi nl i m i tc o s t s i sar e s e a r c h a b l ep r o b l e m a c t u a l l y , t h ee s s e n c eo f t e s ti st og e tt h er e q u i r e dc o v e r a g e i nt h el i m i tc o s t s t h ed y n a m i ct e s t i nt h i s p a p e ri s d i f f e r e n tf r o mt h ed e f i n i t i o ni ns o f t w a r e e n g i n e e r i n g a c c o r d i n g t ot e s ts u i t ee x e c u t e da n d c r e a t e d ，p r o t o c o lt e s tc a nb ed i v i d e d i n t ot w o t y p e s ：t h es t a t i ct e s ta n dt h ed y n a m i ct e s t t h es t a t i ct e s tm e a n st e s ts u i t ec a n n o tb e m o d i f i e do n c ei ti sc r e a t e d a n dd u r i n gi ti s e x e c u t e d ，e v e r y t e s tc a s es h o u l db e r u no n eb yo n e t h ed y n a m i ct e s tm e a n st e s t s u i t ec a nb ea d j u s t e d d u r i n gi t i s e x e c u t e da n dc r e a t e d m o s to ft h et e s tm e t h o d su s e dc o m m o n l ya r e b e l o n gt ot h e s t a t i ct e s t i nt h i st e s t ，u s i n gs h o r t e rt e s ts e q u e n c et of i n dm o r ef a u l t si s s o u g h t ，b u t b e c a u s eo fp r o t o c o l r e l a t i v i t yt w op r o b l e m sc a nb ef o u n di nt h es t a t i c p r o t o c o l c o n f o r m a n c et e s t ：f i r s ti s i n e f f i c i e n t l ye x e c u t e d ；s e c o n di s t h a tt h ep r e f e r a b l et e s t c o v e r a g em a yn o tb er e a c h e d i no r d e rt os o l v et h e s et w op r o b l e m s ，t h i sp a p e rw i l l r e s e a r c ht h ed y n a m i ct e s ta n dr e l a t i v ef i e l d s t h i sp a p e rw i l li n c l u d et h e s ep a n s ： ( 1 ) p r o t o c o lr e l a t i v i t y t h e p r o t o c o lr e l a t i v i t i e se x i s ta m o n ga n di nt h ep r o t o c o lf u n c t i o ng r o u p sa n dt e s t s e q u e n c e s t h em e n t i o n e dt w op r o b l e m sa r ec a u s e db yt h e s er e l a t i v i t i e sd i r e c t l y t h i s p a p e rw i l lu n c o v e rt h ee f f e c tc a u s eb yt h ep r o t o c o lr e l a t i v i t yf r o mt h ed e p e n d e n c e ， t h e ns o m es c h e m ea r er e s e a r c h e d o u r p u r p o s ei st og e tt h ep e r f e c tt e s te f f e c t ( 2 ) t h ed y n a m i cc o n f o r m a n c et e s t i no r d e rt os o l v et h et w op r o b l e m s ，t h i s p a p e rw i l l i n t r o d u c et h e d y n a m i c p r o t o c o lc o n f o r m a n c et e s t i tw i l lr e s e a r c ht w op a r t s ：1 h o wc a nt h es t a t i ct e s ts u i t eb e d y n a m i c a l l ye x e c u t e di no r d e rt oi m p r o v ee f f i c i e n c yt h a tt h et e s ts u i t ei se x e c u t e d ；2 h o wc a l lw eg e n e r a t en e wt e s t s e q u e n c ed y n a m i c a l l y , i no r d e rt oi m p r o v et h et e s t ! 里型兰垫查查兰堕主兰垡堕奎 塑墨 c o v e r a g e t h i sp a p e rw i l lb es t a r t e df r o md y n a m i ct e s tb a s e do nt h ec o m p l e t e l yd e f i n e d f s m t h e ni tw i l lb ee x t e n d e dt ot h en o n c o m p l e t ed e f i n e df s m b e c a u s et h e c a p a b i l i t yo ff a u l t s d e t e c t e do ft h es t a t i ct e s ts u i t ew i l la f f e c tt h ee f f i c i e n c yo ft h e d y n a m i cp r o t o c o lc o n f o r m a n c e t e s td e e p l y w h e t h e rt h et e s ts u i t ei sm - c o m p l e t ew i l l b er e s e a r c h e d a n di ft h et e s ts u i t ei sn o tm c o m p l e t e ，am e t h o d w i l lb ei n t r o d u c e dt o g e n e r a t ed e w t e s ts e q u e n c e si no r d e rt om a k et h et e s ts u i t eb e c o m em c o m p l e t e - ( 3 ) r e l i a b i l i t yo f c o n f o r m a n c et e s t t h ec o n f o r m a n c et e s tc a nn o tc o v e re v e r yt e s ts e q u e n c ei nt h ee x h a u s tt e s ts u i t e s ot h er e l i a b i l i t yo ft h ei m p l e m e n t a t i o nu n d e rt e s td o e sn o te q u a l1 0 0 ，e v e nt h o u g h i th a sp a s s e dt h ec o n f o r m a n c et e s t i nt h i sp a p e r , an e wc o m p u t a t i o nf r a m ew i l lb e i n t r o d u c e df r o mt h eu n i f i e dt h ep r o t o c o lc o n f o r m a n c et e s tm e t h o d t h e n ，u n i f o r m i t y a n dr e g u l a r i t y h y p o t h e s e s w i l lb eu s e dt oi l l u s t r a t et h e c o m p u t a t i o np r o c e s s o f r e l i a b i l i t y e s p e c i a l l yu n d e rt h e z e r o f a u l td e t e c t e d ”c o n d i t i o n ，as i m p l e rm e t h o d b a s e do n o r i g i n a lu n i f o r m i t yh y p o t h e s e s w i l lb ei n t r o d u c e d k e yw o r d s ：p r o t o c o lt e s t ，c o n f o r m a n c et e s t ，d y n a m i ct e s t ，p r o t o c o lr e l a t i v i t y , r e l i a b i l i t y 中国科学技术大学博士学位论文 第一章绪论 第一章绪论 本章主要介绍论文的研究背景、研究现状、研究目的、研究方案等内容，最 后给出论文的章节安排。首先介绍研究背景。 1 1 研究背景 通信协议是计算机和通信网络中各种通信实体或进程之间相互交换信息所 需遵守的一组规则，它是计算机通讯、计算机网络、多机系统等分布式系统的灵 魂。为了给开放式系统互连提供标准，国际标准化组织i s o 提出了i s o o s i 模型， 即开放系统互连参考模型( o p e ns y s t e mi n t e r c o n n e c t i o nr e f e r e n c em o d e l ) 【1 ； 而另一方面，以t c p ，i p 协议为核心的i n t e m e t 网络体系结构拥有更为广泛的用户， 从而成为了事实上的计算机网络工业标准【2 。 近年来，随着计算机通讯与网络技术的飞速发展，使得通信协议的种类和数 量越来越多，其规模和复杂性也越来越大，而实现这些协议的厂商并非只有一个， 所以协议产品中的任何微小错误都可能带来严重的后果，因此如何保证协议产品 按照需求安全可靠的与其他设备通信越来越被人们所重视。为此人们将形式化方 法和软件工程方法引入到协议设计和实现中，从而形成了一种新的研究领域 协议工程( p r o t o c o le n g i n e e r i n g ) 3 】。 协议工程是一体化形式化的协议开发过程 4 ，它主要研究以下6 个方面内 容：协议设计、协议描述、协议验证、协议实现、协议测试和协议维护。在上述 研究范围中，人们尽可能使用形式化技术，力图使研究工作具有坚实的理论基础、 更精确化和更规范化。 协议测试是协议工程的一个研究领域，协议测试的类型很多，比如一致性测 试、强度测试、性能测试等，其中一致性测试是其它测试的基础。 协议的一致性测试是一种黑盒测试，所谓黑盒测试就是不需要知道待测实体 的代码细节，而只通过观察系统与环境的交互来判定其行为的正确性，因此它具 有方便快捷的特点，目前对协议测试的研究也主要集中在黑盒测试范围。 协议一致性测试的目的是测试协议产品所表现出来的行为是否与协议规范 一致【5 】。目前通用的协议一致性测试过程是：首先对协议进行形式化描述；然 后根据协议的测试假设和错误模型生成抽象测试序列：第三，实例化这些测试序 第1 页 中国科学技术大学博士学位论文第一章绪论 列并实测待测实体；最后，对测试结果进行分析，给出待测实体一致性的结果。 协议一致性测试中抽象测试序列的生成方法有很多种，常用的有基于状态机 的t 方法、d 方法、w 方法和u i o 方法，基于代数规范的方法，以及变异分析 等。但这些方法都是静态的，也就是说无论是测试序列的执行还是测试序列的生 成都是静态的，不能根据对待测实体的实际测试而动态做出调整。由于协议相关 性的影响，静态一致性测试有两个明显的缺点，就是效率低下和实际测试范围被 缩小。因此本文提出一种动态协议一致性测试的方法，来解决这两个问题，同时 对一些与动态协议一致性测试相关的问题进行探讨。 1 2 研究现状 协议测试的研究最早于1 9 7 9 年由英国国家物理实验室( n p l ，n a t i o n a l p h y s i c a ll a b o r a t o r y ) 展开【6 。1 9 8 3 年，n p l 开始了基于o s i 模型的协议形式 化和一致性测试的标准化工作。协议一致性测试经过二十多年的发展，取得了很 大的进展。国际标准化组织i s o 也专门制定了一个国际标准0 s i 的一致性 测试方法与框架，这个标准由1 9 8 7 年的5 部分【6 ，已经扩展为1 9 9 4 年的7 部 分【7 。 协议一致性测试的理论研究主要集中在三个方面：协议的形式化描述，测试 序列生成，测试结果分析。本节将分三部分简单介绍协议一致性测试的研究现状。 1 2 1 形式化技术 形式化技术是协议工程的基础，采用形式化描述技术f d t ( f o r m a l d e s c r i p t i o n t e c h n i q u e ) 能充分表述协议的各种特性和体系结构，为协议的验证、 实现及一致性测试提供良好的基础【8 】 9 】。 采用形式化技术来描述协议有很多好处，h e l o v u o ，j 归纳了6 点 5 】。下面分 形式化模型、形式化描述语言，两个方面来简单介绍一下形式化技术的研究现状。 1 2 1 1 形式化模型 目前常用的形式化模型有：有限状态机( f s m ) 【1 0 、p e t r in 1 1 、时态逻 辑( t l ) 【1 2 】、通讯进程演算( c c s ) 【1 3 1 等，下面简单介绍之。 f s m 是一种最常用的模型，它直观性强、可实现与其它形式方法的组合和 第2 页 中国科学技术人学博士学位论文第一章绪论 转换，易于自动实现。随着f s m 被广泛地应用和发展，出现了很多的扩充模型， 主要有：扩展有限状态机e f s m ( e x t e n d e d f i n i t es t a t em a c h i n e ) 1 4 】、结构化有限 状态机c h s m ( c o m m u n i c a t i n g h i e r a r c h i c a ls t a t em a c h i n e s ) 【1 5 】、通信有限状态 机c f s m ( c o m m u n i c a t i n g f i n i t es t a t em a c h i n e s ) 【1 6 1 等。目前常用的协议一致性 铡试序列的生成方法主要是基于f s m 模型。但它存在一个主要问题就是无法表 述并发行为。 p e t f i 网是在协议形式化描述中另一种被广泛使用的技术。它是德国学者 c a p e t r i 在其博士论文中首次提出的，它可以用来描述通讯系统中异步成分之间 的关系 1 7 1 。p e t r i 网的分析技术主要有两种：可达树分析方法和矩阵方程分析方 法。借助p e t r i 网的分析技术能得到被模拟系统的有界性、安全性、守恒和可达 性等方面的性能评价。目前p e t r i 网模型主要是用于协议验证。 i 时序逻辑t l 是模态逻辑的扩充，以状态为可能世界，以状态的演变次序关 系为可能世界间的可到达关系 1 8 1 。时序逻辑的种类很多，随时间结构不同，算 子的选择也有差异。时序逻辑的成功之处在于它具有表达并发程序性质的能力， 同时它也是很多证明方法的基础，其中一些证明方法已写成算法。 进程代数是一门8 0 年代才发展起来的数学，r m i l e r 在这方面作了开拓性 工作，他的通讯进程演算c c s 已在协议工程等领域内得到了重要的应用，是所 有进程代数的基础。以c c s 为基础，其它学者也提出了一些进程代数，其中比 较成熟的是通讯顺序进程c s p ( t h ec o m m u n i c a t i n gs e q u e n t i a lp r o c e s s e s ) 【1 9 】。 1 2 1 2 形式化描述语言 常用的形式化描述语言有：s d l 、l o t o s 、e s t e l l e 。 s d l 是由c c i t t ( i t u t ) 组织开发的电信领域的国际标准 2 0 】。它是一种说 明与描述语言。它主要由三部分构成：系统结构说明，每个抽象机器的动态行为 说明和数掘操作。它能够精确定义通信系统功能规格及对其行为进行描述，采用 多层结构来描述整个系统。它是基于扩展的有限状态机模型。 l o t o s 是i s o 组织开发的一种形式化描述语言【2 1 】。它是一种时态次序说 明语言，基本上由两部分构成的：一部分是以进程代数方法为基础，可用于对进 程行为以及交互作用的描述；另一部分是以抽象数据类型( a d t ) 2 2 2 3 1 为基 础，适用于数据结构和数值的描述。 e s t e l l e 是由i s o 组织开发的另一种形式化描述语言 2 4 1 。它在描述协议时， 第3 页 中国科学技术大学博士学位论文 莞一章绪论 将协议视为由若干任务或模块实例构成的集合，每个任务又含有若干输入输出 点访问( 亦称交互点) 。一个任务的内部行为可采用有限状态机进行描述，其转 移活动可进一步采用程序语言描述。e s t e l l e 可为任务之间的通信提供两种机制： 报文交换和内部变量共享。 1 2 2 测试序列生成 测试序列是一组根据协议规范产生的输入、输出事件序列，它是协议一致性 测试的核心数据。在进行协议一致性测试时，测试执行系统向待测实体施加输入 事件序列，然后接收输出事件序列，并以此判定待测实体的行为是否符合协议规 范的描述。 本节介绍一些常用的测试序列生成方法，我们从通用的协议一致性测试结构 开始介绍。 1 2 2 1 测试结构 i s o i e c9 6 4 6 国际标准的诞生是协议一致性测试领域的重要里程碑，它为协 议的一致性测试提供了基本框架。 图1 1 协议一致性测试的基本结构 图l 。l 为协议一致性测试的基本结构，其中i u t ( i m p l e m e n t a t i o n u n d e r t e s t ) 为待测协议实体，可以由一个或多个协议组成，它通过控制观察点p c o ( p o i n t s o f c o n t r o la n do b s e r v a t i o n ) 与外部环境交互，u t ( u p p e r t e s t e r ) 为上层测试体， 通过在p c o 上调用i u t 提供的抽象服务原语( 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 s ) 检测i u t 的行为，l t ( l o w e rt e s t e r ) 为下层测试体，它通过p c o 并经由n 1 第4 页 里型兰i ：盔兰翌主兰堡垒塞兰= 茎丝垒 层服务提供者( s e r v i c ep r o v i d e r ) 发送n 1 层a s p 给i u t ，以支持i u t 的行动。 在a s p 中可能承载协议数据单元p d u ( p r o t o c o ld a t au n i t e ) 。在测试期间l t 和 u t 通过测试协调过程( 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 和u t 向i u t 发送激励事件模拟i u t 所处的场景，然后 观察i u t 的响应事件来判断其是否一致性的。 1 2 2 2 测试类型 根掘对i u t 控制观察点的不同，可以把测试方法分为四种，如图1 2 所示。 ( 1 ) 本地测试：u t 位于测试系统内部，它与i u t 问的p c o 为标准的硬件 接口。t c p 在测试系统内部实现。 ( 2 ) 分布式测试：u t 位于被测试系统内部，它与i u t 间的p c o 为用户界 面或编程语言接口。 ( 3 ) 协调测试：u t 位于被测试系统内部，但u t 与i u t 间没有p c o 。u t 执行有关的测试管理协议( t m p ，t e s tm a n a g e m e n tp r o t o c 0 1 ) ，与l t 交换t m p 协 议数据单元来实现t c p 。 ( 4 ) 远程测试：没有u t ，需要通过设置被测系统( s u t ) 来实现简单的u t 功能。 a ，本地测试 c ，协调坝口试 b 分布式测试 d 远程测试 图1 2 协议一致性测试的四种测试方法 第5 页 中国科学技术大学博士学位论文第一章绪论 1 2 2 3 测试序列生成方法 测试序列来源于i u t 应该表现出来的逻辑行为。因此它可以从协议模型中 推导出来。由于协议本身可以抽象成数据描述以及作用在这些数据上的行为描 述，因此协议致性测试可以分为对控制流的测试以及对数据流的测试。 对控制流的测试理论上相对成熟一些，大多数控制流的测试序列生成方法都 是基于f s m 模型，主要有w 方法、t 方法、d 方法、u i o 方法。 w 方法包括了两个输入序列集ws e t 和ps e t 。ws e t 是f s m 最小的特征 集，它使得每对状态能够相互区分。即对不同的状态应用ws e t 观察到的输出 应是能够区分的。文【3 0 】给出了构建最小ws e t 的方法。ps e t 包括了所有部分 路径，由一个测试树构成，它的根节点是初始状态，而每个状态只出现一次。文 【3 1 给出了一种部分w 方法，它有更短的测试序列以及比原始w 方法更强的测 试能力，文【3 2 】在非确定有限状态机上实现了w 方法。 t 方法 3 3 】的基本思想是遍历状态机所有的变迁，也就是说转移覆盖，文 3 4 】 借助于中国乡村邮路算法，保证了生成的测试序列具有最小的开销。 d 方法 3 5 3 7 1 的主要思想是为每个状态找到一个区分序列，这个区分序列 由相同的输入序列构成，不同的状态对这条序列产生不同的输出响应序列，以此 来判定当前所处的状态。 u i o 方法最早在1 3 8 3 9 1 中被提出，其基本思想是为状态机的每个状态寻找 有别于其它状态的唯一的输入输出序列。这种方法一被提出就因为其简单高效而 被广泛的研究和改进，比如 4 0 】 4 1 利用中国邮路问题求解最短的u i o 序列，以 及u l o v 4 2 4 3 】，m u l t i p l eu i o 4 4 4 5 】，p u i o 4 6 等等。u i o 方法并不能保证所 有的错误都被检测出来，因此又有了【4 2 4 3 4 7 4 8 等的改进。 其它基于控制流的测试主要有：基于p e t r i 网的方法 5 2 5 3 】，基于约束满足 技术的方法 5 4 】，基于o n - t h e - n y 技术的 5 5 5 6 】，基于变异技术的【5 7 】【5 8 等，但 这些方法并没有被广泛使用。 对于数据流的测试本质上都可以归结到分割测试，也就是说通过某种分割方 式，将输入空间划分成若干子域，然后通过测试假设从子域中选取一些元素进行 测试。数据流的测试主要是从抽象数据类型出发，通过前置条件对子域进行划分， 目前这种测试主要有：基于代数规范的 1 0 1 1 1 1 0 2 1 等，以及基于构造类别代数的 f u 2 1 1 1 1 3 等。 第6 页 数据流和控制流相结合的测试首先需要建立合适的形式化模型，比如e f s m 模型，然后在模型的基础上结合控制流和数据流两方面特性，生成测试序列。比 如基于e f s m 的 2 5 2 9 】，基于代数规范的 1 0 2 】，直接从形式化描述语言出发的 【5 9 - 6 2 1 等。 关于测试方法更多的内容可以参考 8 9 - 9 1 1 。 1 2 3 测试评估 测试评估主要包括：测试集的质量评估和测试结果分析。 测试序列的质量评估，用以保证快捷高效的发现错误。目前这部分工作主要 在状态机上完成，有这样几类方法：1 基于测试方法本身的评估，比如 6 3 6 6 1 ， 这种方法只能找出一些特例：2 基于测试距离的评估，这是由v u o n g ，s t 在1 1 0 4 】 中提出的，但这种方法对测试序列生成帮助不大：3 通过还原状态机进行评估， 这主要由m i n g y uy a o 和j z h u 分别在 6 7 1 0 7 1 ，这种方法只能评估，但不能自 动补充测试序列使测试集完整：4 目前常用的主要是借助模型检查工具，通过 变异分析进行评估，主要有6 8 7 1 1 0 5 等。 测试结果分析主要包括：错误标识定位、待测实体通过测试后的可靠性计算。 本文关注的焦点主要是后者。错误标识定位技术是协议一致性测试的难点，在基 于状态机的模型下，g h e d a m s i ，a 和l e e ，d 对此做了大量研究，并提出了一些方 法，但这些方法对错误模型都进行了比较严格的限制【7 2 7 4 ，7 6 】， b e l h a s s i n e c h e r i f 将g h e d a m s i ，a 的思想扩展到非确定的有限状态模型 7 5 1 ，但仍 然摆脱不了严格限制的错误模型。r a y m o n de 在1 9 4 1 中提出了种新的思想，在 被动测试中利用逆向h o m i n g 过程确定状态机的错误，在单错误模型下它有优于 g h e d a m s i ，a 提出的方法的效率，但令人遗憾的是它并不能检查出所有的单错误。 由于完全测试的不可实现性，所以待测实体即使通过了测试，其可靠性也不 应该是1 0 0 ，因此，通过概率统计的方法计算i u t 经过测试后的可靠性为人们 所关注，w e w o n g 在文 7 7 】中指出错误发现能力和代码覆盖是s _ 卡目关的，p o o m ， jh 和m r l y u 分别在 7 8 7 9 1 q h 介绍了基于统计的测试方法，【8 0 8 2 1 0 0 1 等文 献给出了i u t 通过测试时其出错概率的计算公式，但大多数公式对于i u t 通过 测试集测试时( 即“零错误”) 给出的可靠性为1 0 0 ，这不符合实际，h a g w o o d ， c 对此做了研究，并在【8 l 】【8 2 】中利用求解最优化问题给出了一个新的计算公式， 但在均一假设下存在更简单的公式解决这个问题。 第7 页 中国科学技术大学博士学位论文 第一章绪论 1 3 研究目的 上一节介绍了很多基于控制流的协议一致性测试序列生成方法，在这些方法 中大家关注的焦点始终是怎样保证静态测试集在完整的条件下更为高效，这里的 完整就是指测试集要有完全的错误发现能力。这种思路的一个优点就是测试集一 旦生成就可以一直使用，只要i u t 不通过测试，则它必然含有不一致的地方。 于是通过回归测试的不断反复，最终可以逐渐找到i u t 中满足错误模型的所有 不一致之处。 由于测试序列之间具有的相关性，一个测试目的的执行可能依赖于另一个测 试的结果，所以要想找到i u t 中满足错误模型的所有不一致，可能需要多次回 归测试，而每次回归都需要执行测试集中的所有测试序列，这个过程是非常耗时 的。比如在测试r i p 协议 8 3 1 时，它的定时更新每3 0 秒发生一次，而删除一条 路由时，最长需要1 8 0 秒的时间。所以原有的静态协议致性测试方法的缺点就 表现无遗了：执行效率低下，即测试序列的重复执行问题，当与之相关的测试序 列执行失败时它仍然要执行；无法达到理想的实际测试覆盖度，即当测试序列的 引导序列发生错误时，这个测试的测试目的并没有达到。 因此基于开销上的考虑，要求回归的次数尽可能的少，同时一次测试尽可能 多的发现错误。实际上测试的本质就是在有限的预算范围内要求测试达到给定的 覆盖度。 m y u n g c h u lk i m 和本文的作者分别独立的从错误标识的角度最先考虑这两 个问题，并给出了各自的解决方法 8 4 1 1 8 5 1 。 8 4 采用预先生成待测部分所有可 能的引导序列和验证序列的方法，当测试出现测试时选择没有被标记的序列继续 进行测试： 8 5 从错误标识的角度出发，通过已经执行的测试序列标识出状态机 上的错误，然后当测试新的部分时，动态产生相应的引导序列和执行序列，绕开 i u t 中被标记的实现与规范不一致性的地方。 由于准确错误定位的困难，因此 8 4 采用层次测试，逐级检测待测部分， 8 5 采用单错误假设进行错误标识，对于更复杂的错误模型，它们都无能为力。本文 在 8 5 的基础上提出一种新的动态协议一致性测试模型，它采用优化的约束满足 技术，通过对不等价的错误状态机的区分，逐步确定出i u t 的实现状态机，以解 决复杂错误模型的动态协议一致性测试问题。 由于静态测试集对动态协议一致性测试的执行效率有很大的影响，所以可以 第8 页 中国科学技术大学博士学位论文 第一章绪论 使用这种动态协议一致性测试方法，对一致性测试的测试集进行评估，以产生m 完全的测试集。 由于完全测试的不可实现性，所以一致性测试都是由测试假设( 错误模型) 限定的，因此测试完成后需要对i u t 的可靠性进行计算。本文将给出一种新的一 致性测试的可靠性计算架构，它考虑了测试假设对可靠性的影响。并且对于均一 假设下i u t 通过测试集测试时( 即“零错误”条件) 的可靠性，本文给出一种更 简洁的计算公式。 1 4 研究内容和方案 本文的研究内容主要有以下几个方面： 协议的相关性理论 在实际测试中，我们发现协议描述的功能组内和功能组间以及测试序列内和 测试序列问都存在相关性，这些相关性对协议一致性测试的影响很大。研究相关 性的目的在于揭示相关性对协议一致性测试的影响，并给出了相应的解决方案， 从而往协议的一致性测试达到理想的测试效果。 动态协议一致性测试的原理、相应的算法 动态协议一致性测试试图解决两个问题：1 静态测试集执行效率低下；2 实 际测试覆盖度可能被缩小。因此相应的解决方案也分为两个方面。这部分通过对 实现方法以及应用分析的研究，证明动态协议一致性测试的可行性。 提高静态测试集的错误发现能力 静态测试集发现错误的能力越高，则提供的关于待测实体的信息就越多，这 部分主要研究如何通过动态协议一致性测试方法，产生具有“完全”错误发现能 力的测试集，以及产生这样测试集的一些条件。注意，这里的完全是由错误模型 限定的。 i u t 经过一致性测试后的可靠性 这部分主要研究待测实体经过一致性测试后，其可靠性的计算架构，同时以 均一假设和正则假设为例研究计算方法。 动态协议一致性测试的实际使用情况 这部分主要是对动态协议一致性测试的应用研究，通过在实际协议一致性测 试中的使用，说明这种方法。 第9 页 中国科学技术大学博士学位论文第一章绪论 1 5 论文安排 本文的章节安排如下： 第二章主要介绍一些与本文相关的状态机和协议一致性测试的基本理论和 方法。 第三章主要论述协议的相关性对测试的影响，主要包括协议本身的相关， 以及测试序列的相关性，并对各种影响提出相应的解决方法。 第四章主要论述动态协议一致性测试的原理和方法，首先在完全定义的有 限状态机模型下论述，然后扩展到非确定的有限状态机模型，最后论述通过动态 协议一致性测试方法产生具有“完全”错误发现能力的测试集，以及产生这样测 试集的一些条件。 第五章以b g p 协议为例，详细介绍动态协议一致性测试的过程。 第六章对待测实体经过协议一致性测试的可靠性进行探讨，提出可靠性的 计算架构，并以均一假设和正则假设为例研究计算方法。 第七章总结全文，并提出进一步的工作。 第1 0 页 中国科学技术大学博士学位论文第二章状态机及协议一致性测试的基本理论 论。 第二章状态机及协议一致性测试的基本理论 为后续讨论的方便，本章介绍一些关于状态机和协议一致性测试的基本理 2 1 状态机的一般性理论 状态机以其简单、直观、可预测、易开发、易测试等特性，在协议一致性测 试领域有着广泛的使用。本节介绍一些状态机的般性理论，首先给出有限状态 机的定义。 2 1 1 有限状态机的基本定义 根据输出的不同，有限状态机可以被分为两种类型：m o o r e 机和m e a l y 机。 定义2 - lm o o r e 机 8 6 就是输出只与当前状态有关，而与输入的当前值无关 的有限状态机。 定义2 - 2m e a l y 机【8 7 就是输出是当前状态和输入的函数的状态机。 由于这两种状态机可以相互转化，所咀通常采用m e a l y 机对协议进行建模。 下面给出一个m e a l y 机表示的有限状态机定义。 定义2 - 3 ：一个确定的有限状态机( f i n i t es t a t em a c h i n o ) 可以表示为一 个六元组：m = ( s i ，0 ，s 。，6 ，九) 。 其中s = so ，s i ，“sl 是状态标识集， i = i “i “，i ) 是输入标识集， o = 0 ，0 ：，0 。 是输出标识集， s o 表示初始状态： 6 ：s i s 表示状态转移函数； ：s i 一0 表示输出函数。 根据状态机对输入集合的限制，可以将一个有限状态机分为完全定义和非完 全定义两种类型。 定义2 4 状态机m 被称之为完全定义的有限状态机( f u l l ys p e c i f i e df s m ) ，如 果对于v s s ，i i ，转移函数6 ( s ，i ) 和输出函数入( s ，i ) 都有定义；否则m 被称 为菲完全定义的有限状态机( p a r t i a l l ys p e c i f i e df s m ) 。 第1 1 页 中国科学技术大学博士学位论文 第二章状态机及协议一致性测试的基本理论 对于现实中使用的符合状态机性质的大多数协议来说，都属于非完全定义的 有限状态机，这些状态机中定义的转移称为状态机的核心边，对于没有定义的转 移，可以假设协议实体在此状态对这个输入没有输出，并且保持当前状态不改变， 这些添加的边称为非核心边。由此可以把非完全定义的有限状态机转化成完全定 义的 9 5 。事实上规范定义的有限状态机可以是非完全定义的，但实现的有限状 态机必须是完全定义的，因为实现面向的是协议的实际运行环境，因此每个状态 机可能接收到环境产生的任何输入事件。 1 定义2 5m 被称为非确定的有限状态机( n o n - d e t e r m i n i s t i cf s m ) ，如果对于 v s s ，i i ，( 1 8 ( s ，i ) 障1 ) v ( i 九( s ，i ) i 1 ) ；m 被称之为确定的有限状态机 ( d e t e r m i n i s t i c f s m ) ，如果对于v s s ，i i ，( 1 6 ( s ，i ) i = 1 ) ( i 九( s ，i ) i = 1 ) 。 状态机的非确定性表明允许实现有不同的选择，但现实中的大多数的协议都 符合确定性。本文的后续讨论都以完全定义的确定的有限状态机为基础。 有限状态机可以用图的形式表示，如图2 - l ( a ) 所示，也可以用矩阵的形式表 示：状态转移矩阵和响应输出矩阵，如图2 1 ( b ) 所示。 ( a ) ( b ) 图2 一l 有限状态机 定义2 6 令i + 表示一个输入序列的集合，0 表示一个输出序列的集合，则 6 + ：s x r 斗s 是扩展的状态转移函数，表示给定状态对一个输入序列产生的最终 转移状态；九：s i + 一0 + 是扩展的输出函数，表示给定状态对一个输入序列 产生的输出序列。 定义2 7 一个有限状态机中的两个状态s ，、s ，是等价的，记为s 。；s ，当且 仅当对于任意的输入序列，状态机从它们出发都