（测试计量技术及仪器专业论文）协议互操作测试技术及应用研究.pdf

南京邮电大学硕士研究生学位论文摘要 摘要 协议是计算机网络和分布式系统中各种通信实体之间相互交换信息所必须遵守的一 组规则。为保证网络中各设备正确、可靠地进行通信，必须根据协议规范对网络实体进行 协议测试。论文主要研究协议互操作测试理论基础与应用，分析测试过程中数学模型的建 立、测试序列的生成、测试方法与测试架构，并结合工程经验讨论系统的构成。 在协议互操作测试序列生成中，欧拉图被广泛应用予协议测试的测试序列生成，以往 算法大多以无向欧拉图或转为对称有向欧拉图求解，或者算法比较复杂，或者不能得到最 优解，本文提出一种新求解有向欧拉图测试序列的算法，详细描述算法思想及实现流程， 对算法的时间复杂度和空间复杂度进行分析，与其他算法相比本文所提出的算法具有较低 的时间复杂度且易于编程实现。 在协议互操作测试系统架构中，论文分析现有的两种测试方法：主动测试与被动测试 的不足，将这两种方法结合起来，优势互补，提出环境配置测试方法，解决了主动测试在 嵌入式系统的一致性测试中测试准备阶段的引导序列过长过于复杂的问题，也解决了单纯 的被动测试不能针对特定目标展开测试和分析数据量过大的问题。分析环境配置测试方法 的基本原理、实现过程及其优点，并以c d m a 2 0 0 0l x 的a 1 l 接口测试的一个测试例为例， 分析如何将该方法应于实践。 在协议互操作测试工程实现上，论文以m t v2 0s 4 接口测试为例，详细分析该接口 协议的形式化描述，利用本文所提算法实现抽象测试序列的生成，并转换为实际测试例， 利用本文提出的环境配置测试方法搭建测试环境，并介绍系统的实现，测试结果表明本文 提出的测试序列生成方法和环境配置测试方法正确有效。 关键词：协议测试，互操作测试，欧拉算法，主动测试，被动测试，环境配置测试， m t v 2 0 南京邮电大学硕士研究生学位论文a b s t r a c t a b s t r a c t a st h ec o m m u n i c a t i o nt e c h n o l o g i e sd e v e l o p ，c o m m u n i c a t i o nn e t w o r k sa n dp r o t o c o l s b e c o m em o r ea n dm o r ec o m p l e x f u r t h e r m o r e ，t h ee q u i p m e n t sa n dd e v i c e sc u r r g n tn e t w o r k s c o n s i s to fc o m ef r o mm a n yd i f f e r e n tm a n u f a c t u r e s i no r d e rt om a k es u r et h ee n t i t i e si nn e t w o r k s c a nc o m m u n i c a t ea c c u r a t d ya n dr e l i a b l y ，i t se s s e n t i a lt os t u d yp r o t o c o li n t e r o p e r a b i l i t y t e s t i n g t h i st h e s i sf o c u s e s o nt h eg e n e r a t i o no ft h et e s t i n gs e q u e n c e sa n dt h es y s t e ms t r u c t u r ef o r 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 o nt h eg e n e r a t i o no ft h et e s t i n gs e q u e n c e st h i st h e s i sp r o p o s e san e wa l g o r i t h mt os o l v et h e d i r e c t e de u l e rp a t hp r o b l e mo nt h eb a s i so ft r a n s f o r m a t i o no fg r a p h t h er e p r e s e n t a t i o na n d p e r f o r m a n c eo f t h ea l g o r i t h mw i l lb ei n t r o d u c e di nd e t a i l t h ea l g o r i t h mm a k e st h ep r o g r a m m i n g a n ds o l v i n gm a s s i v ec o m p l i c a t e dn e t w o r kp r o b l e m se a s i e r o nt h es y s t e ms t r u c t u r et h i st h e s i sp r o p o s e st h ee n v i r o n m e n t - b u i l tt e s tm e t h o d a tp r e s e n t ， t h em o s tp o p u l a rt e s tm e t h o d sa r ea c t i v et e s t i n ga n dp a s s i v et e s t i n g b a s e do nt h ei d e a so fa c t i v e t e s t i n ga n dp a s s i v et e s t i n g ， e n v i r o n m e n t - b u i l tt e s t i n ga v o i d st h ep r o b l e m st h a tt h el e n g t ho f t e s t i n gs e q u e n c ei st o ol o n g ，w h i c hi sc o m m o ni na c t i v et e s t i n g i tc a na l s ob ea p p l i e dt o i n t e r o p e r a b i l i t yt e s t i n ga i m i n gc e r t a i nt a r g e t ，w h i c hi si m p o s s i b l ei np a s s i v et e s t i n g t h e e n v i r o n m e n t - b u i l tt e s tm e t h o dh a sb e e na p p l i e dt oar e a ls y s t e ms u c c e s s f u l l y ，w h i c hp r o v e st h e f e a s i b i l i t yo fe n v i r o n m e n t - b u i l tt e s tm o h o d a tl a s tt h en e wa l g o r i t h m sa n dt h ee n v i r o n m e n t - b u i l tt e s t i n gm e t h o dp r o p o s e db yt h i st h e s i s a g ea p p l i e di n 口t v2 0s 4i n t e r f a c et e s t i n gs y s t e ms u c e s s f u l l y t h ep r o c e s sa n dd e t a i l sw e r e d i s c u s s e di nt h et h e s i s k e y w o r d s ：p r o t o c o lt 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 ， e u l e ra l g o r i t h m s ， a c t i v et e s t i n g ， p a s s i v et e s t i n g ，e n v i r o n m e n t - b u i l tt e s tm e t h o d ，i p t v 2 0 ， u 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：多遂灸 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名：数导师签名：二滔匀荽 南京邮电大学硕士研究生学位论文第一章引言 1 1 研究背景 第一章 己i 吉 ，i 口 通信协议是计算机网络和通信网络中各种通信实体或进程之间用于规定消息格式以及 如何发送和接收消息的规则，是各个通信实体或进程遵循的关于硬件、软件或端口等技术 规范，这些规则使得来自不同通讯设备制造商的不同通信实体相互交换信息有了公共的接 口定义，使得通讯网络和计算机网络得以飞速发展。 随着计算机通信与网络技术的飞速发展，新的通信协议不断引入通信网络，通信协议 的种类和数量越来越多，其规模越来越大，复杂度也越来越高，协议实现难度大，周期长， 而且潜在错误多，协议开发过程中任何一点错误和缺陷都将给通信系统的稳定性、可靠性、 坚固性、安全性、容错性以及系统之间互通性和互操作带来巨大的危害，且协议实现难以 维护。为了解决这些问题，对协议的开发过程需要采工程化的方法，形成了一个新的研究 领域协议工程( p r o t o c o le n g i n e e r i n g ) 。协议工程用形式化的方法描述协议的设计和维护 的各个活动，它以协议的软件工程为研究对象，但所建立的协议设计方法比现有软件工程 的一般方法更严格，从而使协议开发整个过程一体化、系统化和形式化【1 】。 协议的开发流程主要包括协议设计、协议描述、协议验证、协议实现、协议测试和协 议维护等等阶段。协议测试是“功能测试 ，依据协议标准来控制观察被测协议实现 ( i m p l e m e n t a t i o nu n d e rt e s t ，i u t ) 的外部行为，通过对被测协议实现的输入和输出加以 监控以达到测试目的。协议测试一般分为一致性测试，互操作测试和性能测试。一致性测 试主要用于判别协议实现是否与所对应的协议标准相一致，互操作测试旨在检测不同类或 同类协议的不同实现版本之间的互通互操作能力，此二者均是协议实现正确工作的基本保 证。本文主要研究协议互操作测试。 1 2 研究现状与方向 由于最初协议测试的研究工作主要集中在一致性测试，对互操作测试的研究起步比较 晚。虽然一致性测试在测试序列生成、测试执行和测试关系定义等形式化方法的研究与应 用已经趋于成熟，但在互操作测试的形式化描述方面的理论基础已经应用研究仍然比较 1 南京邮电大学硕士研究生学位论文第一章引言 少。然而在通信系统中，协议实现的测试过程免不了与其他设备的通信交互，工程实现上 互操作测试显得更为普遍常见，互操作测试的重要性日益显示。 互操作测试研究工作可以分为两大类：互操作测试的一般性概念研究及互操作测试试 验，其中一般性概念研究中以测试序列生成为主。由于互操作性是两个或多个协议实体之 间的交互过程，所以它具有较强的动态性与多边性，测试的难度也随之增大。近年来国际 上在互操作性测试领域的研究主要集中在互操作性测试生成技术、互操作性测试系统的构 造等方面。 在互操作性测试生成技术的研究中，形式化方法描述互操作性是一个重要问题，其目 的是从协议的形式化模型出发生成用于测试活动的测试集。目前采用最多的描述方法是用 通信有限状态机来生成被测系统的形式化模型。r a f i q 等最早提出采用一致性测试序列生成 方法去生成互操作性测试序列【2 】，通过对多个组成系统的可达性分析，构造互操作系统的 复合有限状态机，而直接将一致性测试技术应用于互操作性测试中。k a n g 和k i m 则提出 了协议控制部分的测试序列生成技术【3 】 4 】。上述的方法都只能辅助生成抽象的测试序列， 要生成具体化可执行的测试序列并展开测试活动，仍需要很多手工步骤去完成。当前越来 越多重点都在研究集成化和系统化的互操作性测试技术【5 】【6 】。文章【7 】对互操作性测试序 列的测试执行代价进行详细分析，提出一种通过构造测试生成树来生成互操作性测试序列 的方法。该方法在构造测试生成树过程中进行测试代价增量的计算，用局部最优的贪心策 略进行互操作边的选择，以对测试生成树进行扩展，最终得到近似最优的测试集。 目前通用的互操作性测试体系结构有两种，文章 8 】从不同的角度给出了互操作性测试 的体系结构，如单边( u n i l a t e r a l ) 、双边( b i l a t e r a l ) 、全局( g l o b a l ) 和混杂( h y b r i d ) ，同时给出 了互操作性测试的形式化概念以及多种互操作性测试关系，并证明了双边和全局互操作性 测试是等价的，其结论可用于指导互操作性测试的测试生成，在减弱甚至避免状态爆炸问 题的同时，提供更接近实际场景的互操作性测试研究。在i s 0 9 6 4 6 中定义了四种一致性测 试方法：本地测试方法、分布式测试方法、协同测试方法和远程测试方法，它们有各自的 使用场合，将其中某些方法运用于互操作性测试中可以构造互操作性测试系统。文章【9 】 中从定义并发t t c n 着手，构造了一种协议互操作性测试系统的结构。文章 1 0 】从更深入 的角度讨论了进行互操作性测试的双方的关系，对于以前判定为失败的测试例进行了更深 入的研究，分析了产生该结论可能的原因，进而细化了互操作性测试的研究。 本文主要研究互操作测试系统的形式化描述，互操作测试的测试序列生成算法和互操 作测试框架的方法，并以理论指导实现互操作测试的实验。 2 南京邮电大学硕士研究生学位论文 第一章引言 1 3 论文结构 本文的章节安排如下： 第一章，介绍协议形式化理论及互操作测试方法的基本概念和发展概况，并给出本文 的主要研究内容和研究方案。 第二章，介绍互操作测试的基本理论，分析互操作测试的定义、过程和分类，介绍互 操作测试常用的数学模型有限状态机，并简要介绍基于有限状态机的四种测试序列生 成方法。 第三章，提出一种基于有限状态机的协议互操作测试序列生成算法，该算法用于有向 图测试序列的生成，利用图形转换的方法，将对边的遍历转换为顶点的遍历，对该算法进 行性能分析，并与已有的算法进行比较。 第四章，分析协议互操作测试的特点，互操作测试必然涉及两个或多个的协议实现， 通常为嵌入式或分布式的测试结构，这给工程实现在环境搭建和初状态的预置上带来困 难，该章分析主动测试与被动测试的优缺点，提出环境配置测试方法，将主动测试与被动 测试结合起来，降低测试成本，提高测试效率。 第五章，以i p t v2 0s 4 的t 接口测试为例，在现有的协议测试理论基础以及本文提出 的测试序列生成算法和环境配置测试方法指导下，从互操作测试的协议形式化描述开始， 建立有限状态机模型，生成抽象测试序列，实例化为具体的测试例，详细介绍测试系统的 各个模块实现，借助第四章提出的环境配置测试方法搭建测试环境，给出测试结构，最终 具体实现一个互操作测试的实例，取得良好的测试效果。 第六章，总结全文。 3 南京邮电人学硕- j 二研究生学位论文第二章协议互操作测试理论基础 第二章协议互操作测试理论基础 2 1 协议测试的概念 随着分布式通信网络系统的发展，通信网络设备的各种功能，例如通信功能、处理功 能、信息存储、人机交互等分布于不同的通信系统中，增加了这些系统之间的信息交换需 求。为了保证成功通信，这些通信设备之间相互交换信息时必须遵守一定的规则，这些规 则就是协议。设备只有遵守协议才能实现成功、可靠的通信。 然而，即使有了标准化、规范化的协议，也并不能确保协议的不同实现之间能够成功 地通信。这是因为【1l 】： 目前协议规范一般都是采用自然语言描述，具有二义性。开发人员对协议规范理 解的差异会产生不同的协议实现； 对没有进行详尽完备描述的协议规范，容易出现不同协议实现间的不兼容； 不同的实现手段也会产生不同的协议实现； 协议的复杂度增大，协议开发人员在开发中容易出现失误。 因此，为了保证通信设备能够成功的通信，需要一种有效的方法对各种协议实现进行 测试，保证协议实现完全符合协议标准，这就是协议测试。 2 2 协议互操作测试技术 2 2 1 互操作测试的定义 互操作测试评价被测实现与相连接协议实现之间在网络操作环境中是否能够正确地交 互并且完成协议标准中规定的功能，从而确定被测设备是否支持所需要的功能。互操作测 试通常用于研发阶段多厂商准正式测试或者运营商的选型测试，提供重要的互通信息。 一致性测试和互操作测试都是测试协议实现重要而有效的方法，在某种程度上可以相 互验证，但二者并是完全一样 1 2 】。 测试目的不同，一致性测试是确定被测实现是否与标准规定一致，而互操作测试 是确定被测设备是否完成要求的功能： 4 南京邮i 乜人学倾十研究生学位论义第一二章协议互操作测试理论璀础 测试对象不同，一致性测试的对象是设备或者系统，而互操作测试的对象是设备； 测试级别不同，一致性测试是在协议级，而互操作测试是在功能级； 测试效果不同，一致性测试适用所有被测实现，而互操作测试主要适用于被测设 备之间。 实际测试中，一致性测试通过也并不能保证互操作测试一定可以通过。最根本的原因 是一致性测试使用标准规定的绝对完整和正确是不现实的，其中也包含各个标准制定人 制定单位理解不同与利益妥协的问题。具体表现如下t 标准方面：标准中错误与含糊内容；标准本身的兼容性问题； 实施方面：人为错误( 如编程错误) ，对于通信标准不同理解，标准本身允许不同 选项； 技术方面：通信网络使用不同流量策略；设备兼容性问题；设备配置问题。 由此可见，互操作测试是测试两个或更多的协议实现在网络操作环境中是否能够正确 的交互，从而完成协议标准中规定的功能，它的测试对象是一个或多个协议实体组成的系 统，是一致性测试的有力补充，是协议测试的重要组成部分。互操作性测试的必要性主要 体现在以下几个方面： 一致性测试集很难达到10 0 的测试覆盖； 厂商对协议的可选功能的选取以及扩展功能的不同可能会导致互操作失败； 网络协议自身的版本也在不断更新，不同厂商在更新网络设备版本，使得同一协 议的各种协议实现的差异性增强。 这几个方面使得协议互操作性测试变得更为重要，互操作性测试已经被互联网工程任 务组1 e t f 和欧洲电信标准化协会e t s i 等国际标准化组织广泛用于协议设计的过程中 1 3 。 2 2 2 互操作测试过程 刁： 协议互操作测试过程大致可以分为和协议一致性测试相似的三个阶段【1 2 】，如图1 - l 所 南京邮电人学硕士研究生学位论文 第二章协议互操作测试理论基础 图1 1 协议互操作测试过程 协议互操作测试的活动过程的第一阶段是为一特定协议描述生成一个“抽象互操作测 试集 ，被称为“互操作测试生成 。之所以称为“抽象互操作测试集 是因为它是独立于 任何一个特定的协议实现的。 第二阶段由实现特定互操作测试集的执行方法组成，也称作“互操作测试实现。在这 一阶段，抽象互操作测试集中的抽象测试例被转变为在一实际的互操作测试设备或互操作 测试系统上可执行的测试例。在这一阶段考虑了测试环境与两个被测协议实现( i u t s ) 的 具体情况，即要考虑被测协议实现的功能标准。 第三个阶段为“互操作测试执行 ，互操作测试设备对两个被测协议实现运行已经具 体化的测试例，并对它们的外部行为和内部交互进行观察，最终可以得到一个有关两个i u t 之间互操作的判决，并将测试执行的结果记录在协议互操作测试报告中。 2 2 3 互操作测试的类型 按照进行互操作测试时两个被测协议实现在功能上是否有差异，可以将互操作测试划 分为对称型和非对称型两种1 1 4 1 。 所谓对称型互操作测试是指互操作测试中的两个被测协议实现，。和i ：所对应的协议标 准是相同的，处于完全对等的角色，提供完全相同的功能【1 4 】，如对t c p 协议的两个协议 6 堕室堕皇奎兰堡主竺窒竺兰垡堡壅至三雯堡坚兰堡堡型堕里堡苎堡 实现进行互操作测试。t c p 协议的两个实现和，在功能上完全相等。例如既可以由发 起连接请求以发送数据，也可以由，发起连接请求以发送数据。任何一个互操作测试例， 只要将测试例中的和，所对应的p c o 互换，便可以得到另一个合法的互操作测试例。 + 这便是“对称型”。利用这种对称的特性，可以大大简化互操作测试集的生成。 所谓非对称型互操作测试是指互操作测试中的两个被测协议实现和，所实现的协议 标准中的功能是不相同的，即厶和，两者在功能上是有差异的。这样的互操作测试的例子 是很多的。例如口t v 测试中，流媒体服务器和机顶盒的协议功能有很大的差别，对来自 不同厂商的服务器和客户端协议实现之间的互操作进行测试便属于这种非对称型互操作 测试。显然，由于功能上的差异，非对称型互操作测试要比对称型互操作测试难度要大。 2 3 基于状态机的互操作测试方法 2 3 1 通信协议的形式化描述 通信协议互操作测试是协议测试中较为重要的测试，目的是测试种类不同或版本不同 的通信协议软件的实现是否能够正确正常通信。它的工作过程一般是首先对通信协议进行 形式化描述，然后使用通信协议的形式化描述生成测试序列，最后使用此测试序列进行测 试。形式化描述技术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 ) 能充分表述协议的各种特性和体 系结构【1 6 】，为协议的验证、实现及互操作测试提供良好的基础，有助于实现协议验证和 互操作测试的自动化或半自动化。同时，针对协议互操作测试使用形式化描述，还可以定 义不同层次的测试覆盖标准，便于针对测试的完备性和有效性进行分析。 目前，大量的形式化描述方法不断被提出并应用到实际的协议开发中。常用的形式化 描述技术包括：状态变迁技术 1 2 】( 如，有限状态机模型，p e t r i 网模型等) ，时序逻辑 t l ( t e m p o r a ll o g i c ) ，进程代数如：通讯进程演算( c o s ) ，通信顺序进程( c s p ) ，构造类别 代数等。有限状态机( f i n i t es t a t em a c h i n e ：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 ：c f s m ) 和扩展有限状态机【4 】( 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 ) 。 有限状态机模型直观性强，可以与其他形式化方法进行组合或转换，并且易于自动实现， 以下将依次介绍此三种状态机的相关定义。 ( 1 ) 有限状态机 一个确定的有限状态机( f i n i t es t a t em a c h i n e ：f s m ) 可以表示为一个六元组 1 5 】： 7 堕室些皇奎兰堡主竺! ! 竺兰垡丝茎 一一一 釜三垩堕坚皇堡堡塑堕墨堡墨型 m = ( ，0 ，s ，s o ，万，兄) ，其中： s = ( s o ，q ，一。) 是状态符号集：。 ，= ( ，毛，) 是输入符号集； d = ( o l ，0 2 ，) 是输出符号集： s o 是初始状态； 万：s x j 寸s 是状态转移函数； 五：s x ，寸0 是输出函数。 状态转移函数艿和输出函数五之共同定义了状态的转移集合t ( 因此，有限状态机也可 以看作是一个五元组m = ( ，0 ，s ，s o ，r ) ) ，其中每个元素可以表示为一个三元组 f 丑，j ，i o ，其中墨s 称为转移t 的头状态，f j 和0 - - - - 允( 墨，d 0 分别称为转移t 的输入 和输出，s j = 以墨，f ) s 称为转移t 的尾状态。 基本f s m 只反映了协议事件和协议状态之间的关系，适合于描述协议的控制流部分， 而不能表述其他重要的协议元素：协议变量和协议行为。为了满足复杂系统的描述需求， 通常会根据需要对基本f s m 模型进行扩展。如扩展有限状态机模型e f s m 在f s m 的基础 上增加了对数据部分的描述能力、互操作系统则通常用通信有限状态机c f s m 或复合有限 状态机c p f s m 来描述。下面给出这些扩展模型的介绍 1 5 】。 ( 2 ) 扩展有限状态机( 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 ) 一个扩展有限状态机膨一个：k 元簦t m = ( ，o , s ，l ，y ，p ，彳) 【1 5 】，其中： s 表示状态的集合，s o s 表示初始状态； t 表示转移的集合； y 表示环境变量的集合； p 表示作用于环境变量和输入输出参数的谓词的集合； a 表示作用于环境变量和输输出参数的行为的集合。 在状态墨下，对环境变量矿中所有变量的一个赋值，称为状态墨的一个环境配置，记为 毛( 矿) 。转移集合r 的每个元素是一个五元组 丑，墨，i o ，p ，口 ，其中而s 称为转移t 的头 状态，i 6 i 和o e 0 分别称为转移t 的输入和输出，s ，s 称为转移t 的尾状态，p 表示执行 转移t 时必须满足的条件，口表示执行转移t 时的动作，只有转移条件p 为真值的情况下， 转移t 才可以执行。 ( 3 ) 通信有限状态机( 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 ) 一个通信有限状态机是由状态机集合m 和通信通道集合c 组成= ( m ，c ) 1 5 1 ，其 8 南京邮电大学硕士研究生学位论文第二章协议互操作测试理论基础 中： m = j ，l i ，m 2 ，m 。 是有限个数的有限状态机集合： c = 如：f ，_ ，刀且f j 是有限个数的通道集合； 对每一个勺c 代表一个从到坍，的通信通道，其行为类似于一个先进先出( f i f o ) 的队列，m ，从队列头部取消息作为输入而礁则将产生的消息放在队列的尾部： 如上定义的c f s m 模型能够很好地描述实际协议当中的交互行为，可以将集合肘理解 成参与协议交互行为的实体集合，通道集合c 则是实体之间交互的网络连接通道。 协议的互操作需求通常可通过组合两个协议描述的状态空间，得到全局状态空间，然 后对全局状态空间进行分析来得到。互操作测试所针对的是两个协议实现之间的互连互通 的行为。所以，互操作需求可以从两个协议描述的组合中得到。因此，如何定义和实现两 个协议描述状态的组合状态机，或者说如何得到被测系统的全局状态空间便成为互操作测 试生成技术的一个主要问题。 2 3 2 互操作测试序列的生成方法 由于互操作测试和协议一致性测试的状态模型都可以用状态机表示，互操作测试的测 试序列生成可以引用协议一致性行测试的测试方法。目前常用的一致性测试序列的生成方 法主要集中在有限状态机模型。基于有限状态机上模型的基本测试方法有：转换回路法 ( t r a n s i t i o nt o u r ，简称t 方法) ，可区分序列法( d i s t i n g u i s h i n gs e q u e n c e s ，简称d 或d s 方法) ，特征集合法( c h a r a c t e r i z i n gs e t ，简称w 方法) 和唯一输入输出序列法( u n i q u e i n p u t o u t p u ts e q u e n c e s ，简称u 或u i o 方法) 。下面分别对这四种方法简要介绍。 2 3 2 1t 方法 算法思想：从初始状态出发，对有限状态机的每个转换至少遍历一次，最后回到初始 状态：通过对m 施加输入事件序列，把输出事件序列与协议标准相比较，得到测试结果。 优点：测试方法简单，容易实现； 缺点：有限状态机模型对应的状态转换图必须是强连通的；只检查输入输出事件，不 验证转换得到的新状态是否与协议规范相一致，因而不能发现转换错误。 2 3 2 2d 方法 算法思想：利用有限状态机的不同状态对d 序列相应的输入事件序列有不同的输出事 9 壹室坚皇盔兰堡型窒生堂垡堡塞苎三童坐垡三堡堡型堕墨堡茔堡! ! 件序列的思想，对i u t 施加相同输入事件序列，利用t 的各个状态的输出事件序列的不 同对m 的达到的新状态进行区分。 优点：能够检查转换也能够验证新状态是否与协议规范相一致； 缺点：很少f s m 存在d 序列；即使存在，其序列长度也相当大，上限为矿0 1 ) ，以为 有限状态机的状态数 1 2 】；要求初始状态已知。 2 3 2 3w 方法 算法思想：w 方法可认为是d 方法的改进，d 方法进行状态验证时对肼的每一个 状态转换施加相同d 序列，对d 序列的要求非常高，因而导致大多数f s m 不存在d 序列。 w 方法采用多个输入事件来确定状态。 优点：能检查转换也能验证新状态是否与协议规范相一致，测试序列较d 方法短； 缺点：算法复杂，往往需要若干个不同的输入事件，需检验多次；要求初始状态已知。 2 3 2 4u 1 0 方法 算法思想：f s m 的一个状态的u i o 序列是一个输入输出行为，有限状态机的每一个 状态的u i o 序列互不相同，借助这个序列可以进行状态区分和确认。 优点：大部分f s m 存在u i o 序列，生成的序列一般都比w 方法和d 方法的短。 缺点：有限状态机模型对应的状态转换图必须是强连通的。 以上四种方法中，因大部分f s m 都存在u i o 序列，且序列较短能达到较高的覆盖， u i o 方法应用较为广泛。不少学者对u i o 方法进行研究和改进。【1 6 在基于u i o 序列的协 议测试生成算法的基础上，介绍了u i o ( s ) 序列和u i o ( s ，k ) 序列的生成，对u i o 方 法进行改进；【1 7 】基于贪心算法提出了寻找f s m 各个状态的u i o 序列的伪多项式时间算法， 可以快速地找出f s m 的u i o 序列，基于由近及远的方法提出了寻找最短u i o 测试序列的 算法，可以找出f s m 的最短u i o 序列，【1 8 】提出了m - u i o 算法， 1 9 提出了b u i o 算法。 本文在实践中对状态转换采用的是t 方法。 2 4 本章小结 本章在介绍协议测试的基础上，引入协议互操作测试的相关概念，分析互操作测试的 特点、测试过程及分类，指出形式化描述方法在协议互操作测试中的重要地位，详细介绍 基于有限状态机的协议互操作测试生成测试例的四种方法。 1 0 南京邮电大学硕士研究生学位论文第三章一种求解有向欧拉图的测试序列算法 第三章一种求解有向欧拉图的测试序列算法 欧拉回路或欧拉路径的算法思想被广泛应用在测试序列生成中。对求解无向图的欧拉 回路或欧拉路径f l e u r y 已提出成熟的算法 2 0 ，但不适用于有向图。一般有向图并不符 合欧拉图的条件，例如货郎担问题，允许网络中各条边重复，f l e u r y 算法难以获得最优解。 本文借助欧拉算法的原理，提出一种对不符合欧拉图条件的连通有向图的新算法，通过补 边使之成为欧拉图，然后根据原图中的边与顶点的关系，新建一个以原图的边为顶点的新 图e ，将欧拉图的边的遍历转化成对图e 的遍历，然后利用d i j k s t r a 算法求得最短距离 后选择相关的最短边作为补边即可得到最优解。 参考文献 2 1 2 2 直接用遗传法来求解欧拉路径，算法比较难理解，实现比较困难； 参考文献 2 3 将非欧拉图补边成为完全对称欧拉图，求解补边较多，因而只能得到较优解， 不易得到最优解。 3 1 相关定义与已有算法 【定义一】欧拉回路 ( 1 ) 无向图：每个顶点的入度都是偶数，则存在欧拉回路。 ( 2 ) 有向图：每个顶点的入度等于出度。 【定义- - 欧拉路径 ( 1 ) 起点和终点不为同一点； ( 2 ) 一个无向图中如果除了源点和汇点的度数为奇数外，其余点的度数均为偶数，则存 在欧拉路径，并且欧拉回路的起点和终点为源点或汇点； ( 3 ) 无向图中如果除了源点和汇点的出度与入度不相等外，其他顶点的入度和出度相 等，并且总有源点的出度大于入度，汇点的入度大于出度，则存在以源点为起点， 汇点为终点的欧拉路径。 【定理】：有向欧拉图中存在度数不为o 的顶点时，当且仅当从源点开始遍历并止于汇点 时存在欧拉路径。 【算法l 】搜索最短路径子程序完成对有向网络图中每一对顶点之间最短路径的搜索，并 保存其最短路径和最短长度在遗传算法设计方面，首先采用以遍历边的次序进行编码的， l l 塑塞堂皇叁兰堡主塑塞生堂垡堡壅釜三童二登鲞塑塑塑堕垫堕塑型鎏壁型兰鲨 接着对于任一给定的码串，取码串的路径长度的倒数为该码串的适应度，采用比例选择机 制，选用适当的交叉操作，采取连续多次变换技术，使可行解有较大的顺序排列上的变化； 引入“逆转操作”改善遗传算法的局部搜索能力，加入小生境技术改善遗传算法搜索能 力，最后在译码部分把经过遗传算处理得出的结果转换成有向邮路问题的解见参考文献 2 1 2 2 。 【算法2 】将有向图g 通过补边成为完全对称图g ，借用无向图的欧拉回路的思想求解欧 拉路径，( 1 ) 如果图g 存在欧拉回路，那么测试序列t s = g 的欧拉回路u 1 0 ( 墨) ，其中墨 为该欧拉回路的开始和结束状态。( 2 ) 否则，如果图g 存在一个开始于墨结束于墨的欧拉 路径! 那么t 3 = g 的欧拉路径u 1 0 ( 墨) ；( 3 ) 否则，尽可能少的复制图g 中的边，使得图g 变成对称图g ，求得g 的结束于墨的欧拉路径，则t 3 = g 的欧拉路径为u 1 0 ( 墨) 。详情 见参考文献 2 3 。 f 1 e u r y 算法】该算法用于求解无向欧拉图的欧拉路径 2 0 。算法轮廓如下： ( 1 ) 任取v o v ( 6 ) ，令昂= v o ( 2 ) 设卑= 饥q h 乞m 。) 已经遍历，按下面方法来从e ( g ) 一编乞i ) 中选取弓+ i ： e l + i 与相关联； 除非无别的边可供遍历，否则。不应该为q = g 一他乞局+ ) 中的桥。 ( 3 ) 当( 2 ) 不能再进行时，算法停止。 3 2 欧拉路径求测试序列的算法 此算法本质在于求欧拉路径。将包含所有u 1 0 序列的f s m 图通过补边使之满足有向欧 拉图的条件，用本文的算法得到欧拉路径，然后用最短路径来代替补边，即可得到最短u 1 0 序列，这个算法只能使局部最优，因为最终的结果与补边的方法有关。但利用d i j k s t r a 算法 2 4 求得最短距离后选择相关的最短边最为补边即可得到最优解。算法的创新在于提 出一种新的解决有向欧拉图的方法。 3 2 1 算法描述 3 2 1 1 算法概要 设根据f s m 得到的u 1 0 序列图u ，若图u 为欧拉图，则直接得到图膨，否则通过补边 的方法使图u 成为欧拉图m ，设图m 有m 个状态，n 条边。则图m 表示为 1 2 堕室坚! 垒奎堂堡主堕窒竺兰垡笙塞蔓三兰二登茎笙蔓塑堕垫堕塑型堡壁型墨鲨 顶点集：s = 墨，是i po 0 9 墨) 边集：e = 编，e 2 ，e n 其中，每条边对应f s m 中的一个或多个转换，一个转换对应一组输入输出对。 【算法3 】图膨的边的遍历算法如下： 1 ) 新建一个图e ； 2 ) 对于原图膨中每一条有向边i ，在新图e 中建一个顶点e ( f ) ； 3 ) 利用本文的算法对新图e 进行顶点的遍历。 将图膨转化为以边集为顶点的图e ，则有向图m 的欧拉路径的求解即转化为对图e 顶 点的遍历，即将对边的遍历的求解问题转化为对图的遍历。 【算法4 1 转换的原则：设图mf f j m x m 邻接矩阵彳= ) ，图e 的刀以邻接矩阵曰= 如) 。 若图m 中有边q ：疋专咒，即a a b o ，e j ：墨专墨，即口腭 o ；若6 = p ，则= l ，否则 = 0 。 【定理】若在对图e 的深度优先搜索路径中每个顶点访问了一次且仅一次，则图e 的深度 优先搜索得到的路径即为图膨的欧拉路径。 证明由上述转换原则可知图e 与图m 等价，得证。 对图e 的深度优先遍历需要解决如下三个问题： 1 ) 若图中的顶点没有首尾之分，算法设计要指定访问的第一个顶点；对欧拉路径起点必 须为以图膨中出度大于入度的点为起点的边。 2 ) 由于欧拉路径每条边只能访问一次，图e 的遍历路径可能进入一个死胡同，即当前的 访问的顶点为死顶点，出度为0 ，但尚存在未访问的顶点，却因当前的访问顶点出度 为o 无法继续访问余下未被访问顶点。 3 ) 一个顶点往往有多个邻接点，如何选择其中一个作为下一个访问顶点，以避免出现( 2 ) 中的情况。 【算法5 】为了解决如上三个问题，提出如下算法： ( 1 ) 采用深度优先搜索的方法，使得每次搜索都以路径的长度优先。 ( 2 ) 每访问一个顶点，就把该项点的所有入边删除，保证每个顶点只能访问一次。 ( 3 ) 设当前顶点形有k 个尚未访问的可达邻接点： 当k = l 时，则取这个邻接点作为下一个访问顶点； 当k = 2 时，设可达邻接点为以，0 ) ，若圪一0 ，则取乓为下一个访问顶点，否 则取另一个邻接点为下一个访问顶点： 1 1 堕室堂皇奎兰堡主婴窒生兰垡丝奎 笙三童二登鲞鳖鱼塑堕垫堕箜型鎏壁型墨鲨 当k 3 时，若圪满足如下条件则取圪作为下一个访问顶点： 出度e ( x ) 0 ； 圪能到达k 其余可达邻接点； 删除圪的入边后，出度为o 的顶点数 o 且u 小于或等于图e 的定点数) 删除v 的所有出边； d f s ( u ，r e a c h ，l a b e l ) ； ) 1 4 南京邮电大学硕士研究生学位论文 第三章一种求解有向欧拉图的测试序列算法 ) 算法【3 】的流程图如图3 - 1 所示： 图3 - 1 算法 3 1 的流程图 ( 2 ) 算法 5 1 的流程 1 ，= b e g i n ( v ) 是用于返回下一个访问顶点，被d f s 所调用，确定下一个被访问的顶点。 伪代码如下： i n tb c g i n ( i n tv ) i f ( v 小于1 或大于图e 的顶点数)给出错误提示并返回0 ； 求出v 的可达邻接点数n n e x t ； 将v 的可达邻接点依次存放在s z n c x t 内； s w i t c h ( n n e x t ) c a s eo - 返回0 ： c a s e 1 - 返回s z n e x t o ； ls 南京邮电大学硕士研究生学位论文 第三章一种求解有向欧拉图的测试序列算法 c a s e 2 ：i f ( s z n e x t o - - - + s z n e x t 1 ) 返回s z n e x t 0 ； e l s e 返回s z n e x t 1 ； d e f a u l t ： ) 返回0 ； f o r ( i n ti n d e x l = 0 ；i n d e x l n n e x t ；i n d e x l + + ) f o r ( i n ti n d e x 2 = 0 ；i n d e x 2 数据空间，指用来存储所有常量和所有变量值所需的空间。数据空间由两个部分构成： ( 1 ) 存储常量和简单变量所需要的空间。 ( 2 ) 存储复合变量所需要的空间。这一类空间包括数据结构所需的空间及动态分配 1 7 童室坚皇查堂堡主翌壅生兰垡堡苎笙三兰二登茎鲤壹塑堕垫堕箜塑堕堡型簦鲨 的空问。 环境栈空间，环境栈用来保存函数调用返回时恢复运行所需要的信息。 此处只分析数据空间，其中数据空间主要消耗在图的邻接矩阵的表示上，图肘的邻接 矩阵的表示需要m x m 个整型数所占用的空间，图e 的邻接矩阵的表