(计算机软件与理论专业论文)bittorrent协议一致性测试的研究.pdf_第1页
(计算机软件与理论专业论文)bittorrent协议一致性测试的研究.pdf_第2页
(计算机软件与理论专业论文)bittorrent协议一致性测试的研究.pdf_第3页
(计算机软件与理论专业论文)bittorrent协议一致性测试的研究.pdf_第4页
(计算机软件与理论专业论文)bittorrent协议一致性测试的研究.pdf_第5页
已阅读5页,还剩44页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

内蒙古大学硕士学位论文 bit t o rr e n t 协议一致性测试的研究 摘要 随着网络的日益普及,互联网用户对网络的健壮性、安全性与灵活性提出 了更高的要求。p e e r _ t o p e e r ( p 2 p ) 是一种新兴的分布式网络结构,它不同于以 往的c s 、b s 的服务模式,允许网络参与者们共享他们的一部分资源,而且这 些资源可以被其他对等节点直接访问而不经过其他中间实体的组织。伴随越来 越多的p 2 p 软件的产生,针对这类软件的测试就变得非常有意义。 本文选择了基于p 2 p 网络的b i t t o r r e m 协议来进行协议一致性测试,首先分 析了b i t t o r r e n t 协议的工作原理,并且采用有限自动状态机( f s m ) 来对b i t t o r r e m 协议进行形式化建模。随后使用基于变迁覆盖的u i o 方法对b i t t o r r e m 协议的 f s m 模型进行测试生成,得到了b i t t o l l r e n t 协议一致性测试的抽象测试序列。在 分析了i s 0 9 6 4 6 中的四种测试结构后,最终决定采用分布式测试结构。之后详 细分析了分布式测试中可能出现的可控制与可观察问题,并且据此检查了之前 生成的抽象测试例,发现其中存在可控制问题。在综合考虑了两种常见的此类 问题解决方法后,最终采用增加管理模块,统一协调管理各个测试器的方法来 解决可控制问题。并且就仿真和模拟两种测试环境,提出了具体的解决方法。 在模拟环境下,通过编写模拟程序来模拟t r a c k e r 服务器和p e e r 端,对b i t c o m e t 和b i t s p i f i t 两款支持b i t t o r r e m 协议的文件共享软件进行了实际测试,给出了测 试结论。最后给出本文的结论及下一步需要研究的问题。 关键词:p 2 p ,b i t t o l l r e m ,可控制问题,可观察问题,模拟与仿真 b i t t o r r e n t 协议一致性测试的研究 r e s e a r c ho nc o n f o r m a n c et e s t i n g o fb i t t o rre n tp r o t o c o l a bs t r a c t w i t l lt h eg r o w i n gp o p u l a r i t yo fi n t e m e t , u s e r sp u tf o r w a r dah i g h e rd e m a n do fn e t w o r k s r o b u s t n e s s ,s e c u r i t ya n df l e x i b i l i t y p e e r - t o - p e e r ( p 2 p ) i san e wd i s t r i b u t e dn e t w o r ks t r u c t u r e ,i ti s d i f f e r e n tf r o mt h ep r e v i o u sc sa n db ss e r v i c em o d e l st h a ta l l o wn e t w o r kp a r t i c i p a n t st os h a r ep a r t o ft h e i rr e s o u r c e s ,a n dt h e s er e s o u r c ec a nb ea c c e s s e dd i r e c t l yb yo t h e rp e e rn o d e sw i t h o u tt h e o r g a n i z a t i o no fi n t e r m e d i a t ee n t i t i e s a sm o r ea n dm o r ep 2 ps o f t w a r e sa r ep u ti nu s e ;i ti sv e r y m e a n i n g f u lf o rt e s t i n gt h e s es o f t w a r e s i nt h i st h e s i s ,t h eb i t t o r r e n tp r o t o c o lb a s e do nt h ep 2 pn e t w o r k sh a sc h o s e nt oc o n f o r m a n c e t e s t i n g t h ep r i n c i p l eo ft h eb i t t o r r e n tp r o t o c o li sa n a l y z e da n df i n i t ea u t o m a t es t a t em a c h i n e ( f s m ) i su s e dt om o d e lb i t t o r r e n tp r o t o c o lf o r m a l l y t h ec o n f o r m a n c et e s ts e q u e n c eo fb i t t o r r e n t p r o t o c o la r eg e n e r a t e db a s e do nc l a s s i c a lt e s tg e n e r a t i o nm e t h o d u i o ( u n i q u ei n p u t o u t p u t ) a f t e ra n a l y z i n gf o u rt e s tm e t h o d so f f e r e db yi s o9 6 4 6 ,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 ei sc h o s e n a f t e rad e t a i l e da n a l y s i so ft h ec o n t r o l l a b i l i t ya n do b s e r v a b i l i t yp r o b l e m st h a tm a yb ea r i s e ni n d i s t r i b u t e dt e s tm e t h o d ,t h et e s ts e q u e n c e sg e n e r a t e da r ec h e c k e db e f o r ea n dt h ee x i s t e n c eo ft h e c o n t r o l l a b i l i t yp r o b l e m si si d e n t i f i e d a f t e rc o n s i d e r i n gt h et w oc o m m o nm e t h o d sf o rs o l v i n gt h e c o n t r o l l a b i l i t ya n do b s e r v a b i l i t yp r o b l e m s ,m a n a g e m e n tm o d u l ew h i c hc o o r d i n a t et e s t e rt os o l v e s u c hp r o b l e m si sa d o p t e da n dt h es p e c i f i cs o l u t i o ni s p u tf o r w a r db a s e do ns i m u l a t i o na n d e m u l a t i o nt e s te n v i r o n m e n t i ne m u l a t i o nt e s te n v i r o n m e n t , a ne m u l a t i o np r o g r a mi sd e v e l o p e dt o e m u l a t et h et r a c k e rs e r v e ra n dp e e rn o d e b i t c o m e ta n db i t s p i r i t ,t w of i l e s h a r es o f t w a r eb a s e do n b i t t o r r e n tp r o t o c o l ,a r ea c t u a l l yt e s t e da n dt h et e s tr e s u l t sa r er e p o r t e da n da n a l z e di nd e t a i l s f i n a l l y , t h ec o n c l u s i o na n dt h er e s e a r c hw o r ki nt h ef u t u r ea r ep r e s e n t e d k e y w o r d s :p e e r - t o - p e e r , b i t t o r r e n t , c o n t r o l l a b i l i t yp r o b l e m s ,o b s e r v a b i l i t yp r o b l e m s , s i m u l a t i o na n de m u l a t i o n 内蒙古大学硕士学位论文 图表目录 图2 1 一致性测试过程4 图3 1b i t t o r r e n t 系统组织结构示意图7 图3 2t r a c k e rh t t p h t t p s 协议的序列图8 图3 3p e e rw i r e 协议的序列图9 图3 4b i t t o r r e n t 协议的f s m 1 1 图3 5b i t t o r r e n t 协议的简化f s m 14 图5 1b i t t o r r e n t 协议的分布式测试结构图。1 9 图5 2 可控制问题示意序列图21 图5 3 可观察问题示意序列图2 2 图5 4b i t t o r r e n t 测试序列中的可控制问题序列图。2 4 图6 1 仿真测试示意图2 7 图6 2 构造数据包的t c p 字段示意图。2 9 表3 1 简化b i t t o r r e n t 模型的状态对应表1 2 表3 2 简化b i t t o r r e n t 模型的输入输出对应表。1 2 表4 1b i t t o r r e n t 模型中各状态的u i o 序列表1 7 表4 2b i t t o r r e n t 模型中各变迁的测试序列表1 7 表6 1b i t t o r r e n t 协议测试目的表3 4 v 原创性声明 本人声明:所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成果。 除本文己经注明引用的内容外,论文中不包含其他人己经发表或撰写过的研究成果,也不包 含为获得内苤直太堂及其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对 木研究所做的仟何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名: 日 指导教师签名: 期: 厂z 1 西贸。6 jf 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定,即:内蒙古大学有权将 学位论文的全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘,允 许编入有关数据库进行检索,也可以采用影印、缩印或其他复制手段保存、汇编学位论文。 为保护学院和导师的知识产权,作者在学期间取得的研究成果属于内蒙古大学。作者今后使 用涉及在学期间主要研究内容或研究成果,须征得内蒙古大学就读期间导师的同意;若用于 发表论文,版权单位必须署名为内蒙古大学方可投稿或公开发表。 学位论文作者签名:量:丝i _ 指导教师签名: e t 期:丝塑笸丝 e t期: 。心1 二 o 蝴j6 。活 内蒙古大学硕士学位论文 1 1 选题研究方向 1 1 1 课题来源及意义 第一章引言 目前互联网主要技术模式仍然是c l i e n t s e r v e r 方式,此方式要在互联网上设置拥有强大处 理能力和充足带宽的高性能计算机作为服务器,将大量的数据集中存放在上面并为互联网上 的其它p c 提供服务。这样的网络结构缺点很明显,整个网络的正常运行都需要依赖于这些 服务器的稳定运行。随着网络的日益普及,互联网用户对网络的健壮性、安全性与灵活性提 出了更高的要求。p e e r - t o p e e r ( p 2 p ) 是一种新兴的分布式网络结构,它允许网络参与者们共 享他们的一部分资源,而且这些资源可以被其它对等节点直接访问而不经过额外的中间实体。 它不同与以往的c s 、b s 的服务模式,每个参与p 2 p 网络的计算机( p e e r ) 都具有平等的地 位。每个p e e r 即扮演服务器,为其它p e e r 提供服务,同时又扮演用户;接受其它p e e r 提供 的服务。通过这种方式,整个网络的资源可以实现离散化,进而提升了网络的稳定性。p 2 p 网络一出现,就被广泛应用于文件共享、分布式计算、即时通信等各个领域,为用户提供更 加快捷的服务。 国内外关于p 2 p 网络应用的研究多集中于如下几个方面,如何在p 2 p 网络中进行更有效 的节点内容查询【1 1 ,p 2 p 网络的安全性探讨1 2 1 ,p 2 p 网络流量分析与检测【3 1 ,基于无线网络的 p 2 p 共享系统【4 1 等等。这当中关于p 2 p 系统的测试研究相对较少,且主要集中于性能测试与压 力测试。 b t ( b i t t o r r e n t ) 是一种日益盛行的p 2 p 文件共享软件,它允许对文件进行块切分,并将 每个数据块作为独立的传输单位在下载者之间进行交换。相比较把整个文件作为一个单位, 这样的数据块共享方法更能体现出p 2 p 的特点,不同的数据块可以“并行 的上传或下载。 正是由于b t 软件可以更快捷的实现文件的共享,目前在互联网的全部网络流量中b t 软件的 流量总和要占到3 5 t 5 1 。目前有许多的b t 软件,如著名的b i t c o m e t ,a r c t o c 等,还有许多正 在开发中的b t 软件。这些b t 软件是否都严格遵守b t 协议f 6 1 ,影响着它们的兼容性,决定 了它们能否在互联网上共同使用。因此在b t 软件设计实现完成并投入使用前,对其进行一 致性测试是至关重要的。 b i t t o r r e n t 协议一致性测试的研究 1 1 2 作者的研究内容及主要工作 本论文的主要目标是对b i t t o r r e n t 协议进行深入分析并对b i t t o r r e n t 软件进行协议一致性 测试。主要工作如下: ( 1 ) 分析研究了b i t t o r r e n t 协议的工作原理。 ( 2 ) 使用f s m 对b i t t o r r e n t 协议进行形式化建模。 ( 3 ) 使用基于变迁覆盖的u i o 方法产生b i t t o r r e n t 模型的一致性测试序列。 ( 4 ) 分析了分布式测试方法中的可控制与可观察问题,并提出了具体的解决方案。 ( 5 ) 构建模拟与仿真两种不同测试环境,对两款b i t t o r r e n t 软件进行一致性测试。 1 2 论文结构 本文共分六章:第一章引言,介绍了本文的课题来源和课题研究方向。第二章协议测试 相关理论及发展,介绍了协议测试的发展过程以及一致性测试的理论与框架。第三章 b i t t o r r e n t 协议的工作原理与形式化建模,根据b i t t o r r e n t 协议说明的两个子协议t r a c k e r h t t p h t t p s 协议与p e e rw i r e 协议,分析了不同主体在p 2 p 网络中的行为与作用。介绍 了形式描述语言f s m ,并用f s m 对b i t t o r r e n t 协议进行形式化建模。第四章测试生成,介绍 了常用的测试生成技术,并选用基于变迁覆盖的u i o 方法为已经生成b i t t o r r e n t 的f s m 模型 产生一致性测试序列。第五章测试实现,介绍了协议测试中的可控制与可观察问题,对已产 生的一致性测试序列进行可控制与可观察检测,并就发现的可控制性问题提出解决方案。第 六章测试环境的构建,根据解决方案,构建模拟与仿真两种测试环境。着重分析构建模拟测 试环境时遇到的问题与解决方法。第七章测试执行,在两种测试环境下分别对b i t c o m e t 和 b i t s p i r i t 两款b t 软件进行一致性测试,并对测试结果进行分析。第八章对本文进行总结及提 出进一步的工作。 2 内蒙古大学硕士学位论文 2 1 协议测试的发展 第二章协议测试相关理论及发展 随着计算机网络和通信技术的迅猛发展,尤其是开放异构网络的互联,网络协议的设计 和实现越来越复杂,因此对网络协议的测试要求就越来越高。这促使了协议测试的理论和技 术得到广泛研究和深入发展,使得协议测试成为计算机网络和分布式系统工程学中重要的发 展领域之一。协议测试属于软件测试的一种,软件测试一般可以分为黑盒测试和白盒测试。 黑盒测试又称功能测试,仅仅通过观察被测实现的外部可见行为来确定功能实现,不检查被 测实现的内部结构和内部特性。白盒测试又称结构测试,通过研究被测实现内部的实现结构 和实现逻辑,得出测试数据进行测试。协议测试和软件测试一样,都是一种实验验证行为。 由于时间、资源、技术的制约,无法对被测实现进行穷尽测试,因此它并不能保证被测实现 的完全正确。但在精心设计的测试数据和系统的测试行为下,可以保证被测实现能够实现需 求的功能并尽可能地减少出错,使之可以达到实际应用可以接受的程度。 协议测试包括四种类型的测试:一致性测试( c o n f o r m a n c et e s t i n g ) ,性能测试( p e r f o r m a n c e t 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 g ) 7 1 。一致性测 试旨在检测所实现的协议实体( 或系统) 与协议规范的符合程度;性能测试旨在检测协议实 体或系统的性能指标( 如数据传送率,连接时间,执行速度等) ;互操作测试旨在检测同一种 协议的不同实现版本之间,或同一类协议的不同实现版本之间互通的能力和互操作能力;坚 固性测试旨在检测协议实体或系统在各种恶劣环境下运行的能力( 如信道被切断,注入干扰 报文等) 。其中,一致性测试是其它三种测试的基础,它对协议的形式规范和协议实现行为之 间是否一致进行检查,即协议实现是否符合协议规范的要求。协议一致性测试就是通过执行 测试来检查测试实现是否符合协议规范的要求。 2 2 协议一致性测试的理论与框架 协议一致性测试的研究从2 0 世纪6 0 7 0 年代开始受到研究人员的重视,并投入了大量的 人力和物力从事这方面的研究。这其中最重要的成果是形成了协议一致性测试方法和框架的 标准i s o o s i9 6 4 6 。i s o9 6 4 6 共有7 个部分【8 1 【9 j b o l i l l l 【1 2 】【1 3 】【14 1 ,分别介绍了一致性测试的基 本概念、抽象测试套规范、t t c n 测试语言、测试实现以及实现一致性声明等内容。根据i s o b i t t o r r e n t 协议一致性测试的研究 9 6 4 6 的定义,协议的一致性测试过程大致分为四个阶段,如图2 1 所示: 图2 1 一致性测试过程 f i g u r e2 一lc o n f o r m s _ r l 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 ) 生成协议的形式说明模型,形式模型是测试的基 础,因此它本身必须是正确的。目前国际上通用的形式化模型有:有限状态机、带标记转换 系统l t s 、p e t r i 网。由i s o 和c c i t t 规定的形式化描述语言有:a s n 1 、l o t o s 、m s c 、 s d l 、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 上进行的。 4 内蒙古大学硕士学位论文 第三阶段是测试实现( t e s ti m p l e m e n t a t i o n ) 为执行特定的测试集做准备。在这一阶段, 抽象测试集中的抽象测试例被转变为可在一个实际测试设备或测试系统上执行的测试例。人 们需要导出长度最短的但却能提供最好差错覆盖的测试序列。 第四阶段测试执行( 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 rt e s t 简称i u t ) 相对于协议说明是否一致的判定。 协议一致性测试使用的测试套分为三种:通用测试套、抽象测试套和可执行测试套。它 们在协议一致性测试过程中发挥不同的作用。通用测试套是对一个协议进行一致性测试的全 部测试套。它仅仅根据协议的测试目的产生,不管协议的具体实现,也不管使用何种测试方 法。 b i t t o r r e n t 协议一致性测试的研究 3 1b i t t o r r e n t 协议 第三章b i t t o r r e n t 协议原理与建模 3 1 1b i t t o r r e n t 协议工作原理 b i t t o r r e n t 协议【6 】是b r a mc o h e n 设计的一种架构于t c p i p 协议之上的基于p 2 p 原理的内 容分发协议,它属于t c p i p 结构的应用层。它采用高效的点对点技术共享大文件,并使每个 用户都参与到网络共享中。一般的下载服务器会为每一个下载请求用户单独提供下载服务, 而b i t t o r r e n t 的工作方式不同,文件的持有者将文件发送给其中一名用户,再由这名用户转发 给其他用户,这样每个用户之间都能够互相转发自己所拥有的文件部分,直至所有用户的下 载都完成。在b i t t o r r e n t 协议中定义了如下实体: p e e r :所有参与文件共享的主机,包括原始文件的提供者。 t r a c k e r 服务器:管理并记录参加某一文件共享的所有p e e r 的地址。它能够为新加入共享 的p e e r 提供其他p e e r 的i p 地址和端口号,并定时向己加入共享的p e e r 更新其他p e e r 的地址 与端口。 m e t a i n f o 文件:即种子文件,包含了共享文件的唯一标示i n f oh a s h ,t r a c k e r 服务器的 u r l 地址,还有种子创建的日期,备注等信息。该文件主要用于标示所共享的文件和t r a c k e r 服务器的地址以供文件共享时使用。 种子发布服务器:一个为种子文件提供上传发布服务和传统下载服务的服务器。 b t 协议中描述的文件共享流程如图3 1 所示。准备加入文件共享的主机首先需要登陆种 子发布服务器,根据服务器上已经发布的资源信息选择需要共享的文件,并在该服务器上下 载文件对应的种子文件。使用主机上的b t 软件( 相当于一个p e e r ) 打开该种子文件,获得 该种子对应的t r a c k e r 服务器的地址与文件的i n f oh a s h 。接下来主机的b t 软件会根据得到的 t r a c k e r 服务器地址( 可能不止一个) 与t r a c k e r 服务器进行t c p 连接,然后向t r a c k e r 服务 器询问其他参与共享的p e e r 的地址。主机的b t 软件根据从t r a c k e r 得到的其他p e e r 的地址 与其他p e e r 进行连接并共享文件。在整个过程中,t r a c k e r 服务器只负责管理参与共享的p e e r 的地址等简单信息,并不存储真正的文件资源。所有参与共享的p e e r 都直接与其他p e e r 互换 资源,这样就构成了p e e r - t o p e e r 的结构。 6 内蒙古大学硕士学位论文 3 1 2b i t t o r r e n t 协议内容 图孓1b i t t o r r e n t 系统组织结构示意图 f i g u r e3 - 1b i t t o r r e n ts y s t e ms t r u c t u r ed i a g r a m 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 协议正常使用的保 障。这部分就是b i t t o r r e n t 协议下的两个子协议t r a c k e rh t t p h t r p s 协议和p e e rw i r e 协议。 其中前者描述了p e e r 与t r a c k e r 服务器通信下需要遵循的数据包格式和应对措施,后者描述 了p e e r 之间通信下需要遵循的数据包格式和应对措施。图3 2 和图3 3 用消息序列图( m s c s ) 的方式分别将这两个协议的主要内容表现出来。 在图3 2 中,遵循t r a c k e rh t t p h t t p s 协议,一个准备参与到文件共享过程中的p e e r 客户端应该通过分析已有的种子文件来获取该种子文件所对应的文件资源的i n f oh a s h 和为 该种子服务的t r a c k e r 服务器的地址和端口号。然后p e e r 客户端与t r a c k e r 服务器通过t c p 三次握手建立t c p 连接,在t c p 连接建立后,p e e r 客户端向t r a c k e r 服务器发送g e t 数据 包( 指定资源的i n t o _ h a s h ) 提出加入请求并注册,t r a c k e r 服务器会根据收到的g e t 信息检 查i n t oh a s h 所对应的资源是否存在并记录该p e e r 的p e e ri d 、地址、端口等信息。然后向p e e r 7 b i t t o r r e n t 协议一致性测试的研究 客户端回复一个p e e r l i s t 数据包,为其提供在该t r a c k e r 服务器登陆的参与该资源共享的其他 p e e r 的地址与端1 3 号。 图3 - 2t r a c k e rh t t p h t t p s 协议的序列图 f i g u r e3 - 2s e q u e n c ec h a r to f t r a c k e rh t t p h t t p sp r o t o c o l 为了可以更加直观地了解p e e r w i r e 协议,图3 3 以序列图的方式给出了一个顺利的资源 下载过程。p e e rw i r e 协议中主机上的b t 软件收到p e e rl i s t 后,从中选择一些p e e r ,与它们 通过互相交换h a n d s h a k e 数据包得知彼此的p e e ri d ,再通过互相交换b i t f i e l d 数据包得知彼 此拥有的文件部分。随后根据彼此已拥有的数据内容,向对方发送i n t e r e s t e d 信息表示对对方 数据感兴趣,如果对方回应c h o k e 信息同意,则可以向对方发送r e q u e s t 请求下载指定的数据 块,然后对方会用p i e c e 信息将需要下载的数据块传送给自己。在下载的过程中可以同时接受 其他p e e r 的下载请求,这样在下载的同时又可以上传资源给其他节点,由此构成了p 2 p 的共 享网络。整个网络的分享过程都与此类似,直至某个节点全部下载完后,它就不再向其他p e e r 提请下载了,只考虑接受下载请求。 这里介绍的都是正常共享的序列图,两个子协议还规定了一些特殊情况与错误处理的方 法。例如各个数据包都存在的超时问题,如果对方不想主机下载其资源不发送c h o k e 信息。 这些情况在b i t t o r r e n t 协议中都有涉及,且给出了解决方法。 8 内蒙古大学硕士学位论文 图3 3p e e r w i r e 协议的序列图 f i g u r e3 - 3s e q u e n c ec h a r to f p e e rw i r ep r o t o c o l 3 2 形式化描述b i t t o r r e n t 协议 因为b t 协议是用自然语言描述的协议规范,所以可能存在语义表达和语义理解上的二 意性。为了对b t 软件进行准确的测试,就必须采用一种形式化描述语言对b t 协议进行形式 化描述。形式化描述技术有很多种,如f s m ( f i n i t es t a t em a c h i n e ) 、p e t f in e t 、l o t o s 、l t s 9 b i t t o r r e n t 协议一致性测试的研究 ( l a b l e dt r a n s a t i o ns y s y t e m ) 等,这些技术各有特点。b t 协议相比较而言是一个轻量级协议, 对建模方法无特殊要求,而f s m 描述已有较为成熟的测试技术,因此这里选用f s m 进行形 式化描述。 3 2 1f s m 图表示法 f s m 由有限的稳定状态构成,通过激励信号( 内部或外部的消息) ,推动状态的迁移和自 动机的运转。在运转的过程中,会产生一定的输出信号。f s m 最初主要应用于开关电路、序 列电路和硬件设计等的测试和验证以及自动控制模型中。最早m o o r e 建立了一个有限状态机 测试的框梨1 5 】,定义了区别( d i s t i n g u i s h i i l g ) 和引导( h o m i n g ) 实验的概念,并给出了确定状态等 价的算法和构造引导序y l j ( h o m i n gs e q u e n c e s ) 的算法。近年来,系统的可靠性问题引起了对基 于有限状态机测试的广泛研究,以保障系统功能的正确【1 6 】【17 1 。研究成果主要应用在一些软件 的实现和测试中,包括词法分析程序、模式识别程序、协议一致性测试、g u i 测试和面向对 象测试等领域。 定义3 1 有限状态机f s m 可以表示为一个5 元组:m = i ,o ,s ,6 ,九 其中:其中i 、o 和s 分别是输入字符、输出字符和状态的有限非空集合;6 是从s x i 至s 的单值部分映射;入是从sx i 至o 的单值部分映射。当有限状态机处于s ( es 状态并收 到输入a i 时,它就转换到由6 ( 。,a ) 说明的下一个状态,并产生由入( 。,。) 说明的一个输出。 f s m 还可以用有向图g = ( s ,e ) 来表示,其中,顶点集s = s l ,s 2 ,s 。 对应着f s m 中规定 的状态。在边集e 中,从s i 到s j 的一条有向边对应着f s m 中从状态s i 到状态s j 的一个状态 转换变迁( t r a n s i t i o n ) 。图g 中的每一边都有一输入输出对作为记号。我们用( s i , s j ,i k o m ) 表 示从s i 到s j 的一条具有标号i k o m 的边,它说明当有限状态机f s m 在状态s i 时,接收输入 i k ,将产生输出o m ,并转换到状态s j 。 3 2 2 用f s m 描述b i t t o r r e n t 协议 我们用图表示的f s m 来描述b t 协议中p e e r 端的主要功能,如图3 - 4 所示。这个f s m 模型中描述的不仅有正常的共享流程,还有部分异常处理。为了后边的测试生成方便,我们 将f s m 中的状态和输入输出都进行编号。用0 1 0 表示p e e r 端的状态,用1 1 i l o 表示所有可能 的输入,o i 0 8 表示所有可能的输出。九表示无输入和无输出,编号对应的状态和输入输出如 表3 1 所示。重新编号后的f s m 图如图3 5 所示。 1 0 内蒙古大学硕士学位论文 r e q u e s t f a i l u r e r e q u - t r a c k e rr e q u e s t r e s p o n s e h a n d s h a k elh a n d s h a k e b i t f i e l d ( h a v e ) - f a i l u r e 图3 4b i f r r e n t 协议的f s m f i g u r e3 - 4f s m o fb i t t o r r e n tp r o t o c o l a n d s h a k e r e q u e s t b i t t o r r e n t 协议一致性测试的研究 表孓1 简化b i t t o r r e n t 模型的状态对应表 t a b l e3 - 1c o m p a r i s o no fb i t t o r r e n tf s m ss t a t e s 编号状态 0s t a r t 1 胎i t t r a c k e r 2 l o g i n 3i t h a n d s h a k e 4h a n d s h a k e 5肠i t - b i t f i e l d 6b i t f i e l d 7胎i t d o w n l o a d 8 u p l o a d 1 9d o w n l o a d 1 0 u p l o a d 一2 表3 2 简化b i t t o r r e n t 模型的输入输出对应表 t a b l e3 - 2c o m p a r i s o no fb i t t o r r e n tf s m si n p u t o u t p u t 编号输入编号输出 i l f a i l u r e o i t r a c k e r r e q u e s t 1 2 r e s p o n s e 0 2 h a n d s h a k e 1 3 h a n d s h a k e 0 3 b i t f i e l d 1 4 t i m e o u t 0 4 p i e c e 1 5 b i t f i e l d 0 3 u n c h o k e 1 6 i n t e r e s t e d & r e q u e s t 0 6 i n t e r e s t e d 1 7 i n t e r e s t e do , i n t e r e s t e d & r e q u e s t 1 8 r e q u e s to sr e q u e s t 1 9 u n c h o k e 1 1 0 p i e c e 在b i t t o r r e n t 的f s m 图中,我们将t r a c k e rh t t p h t t p s 和p e e rw i r e 两个子协议合并 表示,其中l o g i n 状态前的部分用于表示t r a c k e rh t t p h t t p s 协议,主要描述了p e e r 向 t r a c k e r 服务器发送t r a c k e rr e q u e s t ,并接收r e s p o n s e 的行为。f s m 中l o g i n 状态之下的部分 用于表示p e e rw h 协议,其中l o g i n 状态到h a n d s h a k e 状态描述了p e e r 间交换h a n d s h a k e 信息的行为;h a n d s h a k e 状态到b i t f i e l d 状态描述了p e e r 间交换b i t f i e l d 信息的行为;b i t f i e l d 状态到u p l o a d l 和u p l o a d 2 状态描述了两种不同的数据包上传实现行为;b i t f i e l d 状态到 d o w n l o a d 状态描述了两种不同的数据包下载实现行为。 1 2 内蒙古大学硕士学位论文 3 3b i t t o r r e n t 协议f s m 模型的不确定性 协议本身有时候并不会完全说明所有的协议行为,这就造成了实际建模的不确定性。因 为协议本身是用自然语言描写,因此在理解上有可能产生不确定性。或者协议并未就所有的 行为进行约束,导致实际执行时有一定的可选择性。这些都可以叫做协议的不确定性i l 引。 上节得到的f s m 所描述的b t 协议存在着不确定性因素。在状态6 时,如果无输入,则 有可能输出0 6 到达状态7 ,也有可能输出0 7 ,到达状态9 。这个不确定性是由描述的不确定 性产生的。协议描述中未准确说明当p e e r 准备下载资源时,必须先询问对端p e e r 是否u n c h o k e 请求,还是可以直接发送r e q u e s t 请求下载数据。正是因为协议的不确定性,导致了被测试实 现的不确定性。在实际测试时,无论被测试实现采用何种方法实现这部分功能,只要符合这 两条路径中的一条就可以证明是一致的。 b i t t o r r e n t 协议一致性测试的研究 图3 - 5b i t t o r r e n t 协议的简化f s m f i g u r e3 - 5s i m p l i f i e df s m o fb i t t o r r e n tp r o t o c o l 1 4 内蒙古大学硕士学位论文 4 1 形式化方法生成测试序列 第四章测试生成 第三章得到f s m 的是根据b i t t o r r e n t 协议生成的,正确描述行为特征的状态机模型,但 在实际的系统中存在着另一个状态模型,这就是程序运行时所产生的状态模型,由于被测实 现有可能存在错误,因此实际运行的状态模型会与预期的模型存在一定的差异。基于f s m 进 行测试的目的就是要找出这些差异,进而发现被测实现中存在的错误。 假设由协议描述产生的状态模型定义为s p e c ( s p e c i f i c a t i o n ) ,而被测实现运行时的状态模 型称为i u t ( o l j 被测实现:i m p l e m e n t a t i o n u n d e r t e s t ) ,则i u t 和s p e e 相比,通常存在以下差 异: ( 1 ) 丢失转换:对一个有效的激发事件,i l j t 没有做出响应; ( 2 ) 不正确的转换:t 的行为到达一个不正确的结果状态; ( 3 ) 丢失动作:对一个转换,t 没有产生任何动作( 输出遗漏) ; ( 4 ) 不正确的动作:对一个转换,m t 产生了错误的动作( 错误输出) ; ( 5 ) 错误状态:r l j t 通过转换,到达了无效的状态。 当进行协议与i u t ( 被测实现) 的一致性测试时,需要选择一定的方法从协议描述中生成测 试序列。目前在有限状态机建模下,测试序列的产生需要遵循以下两个覆盖准则。 状态覆盖:所有的状态至少要被访问一次 变迁覆盖:所有的变迁至少要被触发一次 目前基于这两个准则的测试方法主要有5 种,它们分别是: t 方法:测试输入序列对应于规约说明中的状态迁移随机的产生,它的基本思想是遍历 状态机所有的迁移,直到所有的状态迁移都

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论