（计算机系统结构专业论文）无线局域网安全协议测试平台的构建方法和技术研究.pdf

捅璺随着无线局域网( w l a n ) 技术的飞速发展，其在国防、科研、教育、经济等各行业中的应用日益广泛。但是，w l a n 也面临一系列阻碍其市场发展的圃难，其中，安全性问题是这些阻力当中的关键问题，而如何对w l a n 安全协议的安全实现进行相关测试，是本文关注的焦点。本文针对该问题，借鉴网络协议测试工程学的概念结合安全协议本身的特点，提出了一套针对安全协议的测试方法，并最终设计出一个通用的安全协议测试平台。该平台能够对w l a n 安全协议的软件实现进行一致性测试和安全性测试。一致性测试主要检测所实现的安全协议是否符合协议规范，为协议能够正常运行提供保证。安全性测试主要则主要检测所实现的安全协议是否能抵御各种已知的攻击，如地址欺骗、重放攻击、中间人攻击和拒绝服务粪攻击等，进而判断所实现的安全协议的安全性。测试结束后，该平台还应该根据测试结果对所实现的安全协议进行分析和评价。文章先给出了协议测试的一般理论，接着简要分析了w l a n 安全协议的特点，在此基础上，给出一些相关技术难点的解决方案和平台的整体设计框架，并在本文的最后以8 0 2 1 1 b 协议为例进行了部分实例演示。关键词：安全协议测试一致性测试安全性测试测试序列生成a b s t r a c tw i 廿lt h er a p i dd e v e l o p m e n to fw l a nt e c h n o l o g y , i tf i n d si n c r e a s i n g l yw i d ea p p l i c a t i o n si nav a r i e t yo fa r e a s ，s u c ha sn a t i o n a ld e f e n s e ，s c i e n t i f i cr e s e a r c h ，e d u c a t i o na n de c o n o m i c s ，e t c h o w e v e r , w l a ni sa l s oc o n f r o n t e dw i t hl o t so fo b s t a c l e sb l o c k i n gi t sm a r k e t i n g ，a m o n gw h i c hs e c u r i t yi so n eo ft h ek e yp r o b l e m s ，a n dh o wt ot e s tt h ei m p l e m e n t a t i o no fw l a ns e c u r i t yp r o t o c o l si st h ef o c u so ft h i sp a p e r t os o l v et h i sp r o b l e m ，w e ，b o r r o w i n gt h ec o n c e p t sf r o mn e t w o r kp r o t o c o lt e s te n g i n e e r i n ga n dc o n s i d e r i n gt h ef e a t u r e so fs e c u r i t yp r o t o c o l s ，p r e s e n tan e ws o l u t i o nf o rs e c u r i t yp r o t o c o lt e s t , a n dd e s i g nac o l r l l l o ns e c u r i t yp r o t o c o lt e s tp l a t f o r m ，f i n a l l y t h ep l a t f o r mi sc a p a b l eo fp r o v i d i n gc o n f o r m a n c ea n ds e c u r i t yt e s t i n go ft h es o f t w a r ei m p l e m e n t a t i o no fw l a ns e c u r i t yp r o t o c o l s c o n f o r m a n c et e s t i n gi st oe v a l u a t ew h e t h e rt h es o f t w a r ei m p l e m e n t a t i o ni si na c c o r d a n c ew i t ht h es p e c i f i c a t i o no ft h es e c u r i t yp r o t o c o l ，a n dg u a r a n t e et h en o r m a lo p e r a t i o no ft h ep r o t o c 0 1 s e c u r i t yt e s t i n gi st oj u d g ep r o t o c o ls e c u r i t yt h r o u g hc h e c k i n gw h e t h e rt h er e a l i z e ds e c u r i t yp r o t o c o li sa b l et or e s i s tv a r i o u sk n o w na t t a c k s ，t y p i c a l l y , a d d r e s ss p o o f i n g ，r e p l a y , m a i li nt h em i d d l e ，a n dd d o s f o l l o w i n gt h et e s t i n g ，t h ep l a t f o r ma n a l y z e sa n de v a l u a t e st h er e a l i z e dp r o t o c o la c c o r d i n gt ot e s t i n gr e s u l t s a f t e rt h ed e s c r i p t i o no fg e n e r a lt h e o r i e s ，t h ef e a t u r e so fw l a ns e c u r i t yp r o t o c o l sa r ea n a l y z e d ，b a s e do nw h i c h ，s o l u t i o n st os o m er e l a t e dt e c h n i c a ld i f f i c u l t i e sa n do v e r a l ld e s i g nf r a m e w o r ko ft h ep l a t f o r ma r ep r e s e n t e d f i n a l l y , t h et e s t i n go f8 0 2 1 1bi sg i v e na sa ni n s t a n c e k e y w o r d ：s e c u r i t yp r o t o c o lt e s t ；c o n f o r m a n c et e s t ；s e c u r i t yt e s t ；t e s ts e q u e n c e s西安电子科技大学学位论文创新性声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切的法律责任。本人签名：舞：耋圣日期西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。( 保密的论文在解密后遵守此规定)本学位论文属于保密，在一年解密后适用本授权书。本人签名：导师签名：日期日期上坐_ 阜第一章绪论第一章绪论1 1 引言随着计算机技术和网络技术的蓬勃发展，有线网络以其传输速度高，技术发展快速、成熟等优点，在各行各业得以广泛应用。伴随着有线网络的普及，以快捷高效，组网灵活为优势的无线网络技术也在飞速发展。无线局域网( w i r e l e s sl o c a la r e an e t w o r k ，简称w l a n ) 是在有线网的基础上发展而来的，指以无线信道作为传输媒介的计算机局域网络，它是计算机网络与无线通信技术相结合的产物。无线局域网要求以无线方式相连的计算机之间共享资源，具有现有网络操作系统所支持的各种服务功能，它使网上的计算机具有可移动性，能快速、方便地解决有线方式不易实现的网络信道的连通问题。随着无线网络在技术上的成熟，产品种类的不断增加和产品成本下降，无线局域网的应用越来越广泛，其本身也是有线局域网的一种很好补充。在不远的未来，随着信息技术极速发展，无线网将依靠其无法比拟的灵活性，移动性和极强的可扩容性，使人们真正享受到简单、方便、快捷的网络服务。相对于蓝牙、3 g 等无线技术，无线局域网己成为当前无线领域中一个更为引人关注的热点。而无线局域网由于其本身的特点也带来一些新的问题，并引出相关的研究。1 2 研究背景1 1 1w l 蝌协议的发展协议是通信网络和分布式系统中各种通信实体之间相互交换信息所必须遵守的一组规则。在w l a n 网络发展的过程中，协议的发展一直处于核心地位。1 9 9 7 年，i e e e 发布了8 0 2 1 1 协议，这是在无线局域网领域第一个国际上被认可的协议。i e e e 8 0 2 1 1 规定了统一的m a c 层，使得各种不同厂商的无线产品得以互联。无线局域网的真正推广，是在被称为、矾f i 的i e e e8 0 2 1 1 b 标准发布以后。1 9 9 9 年，i e e e8 0 2 1 1 无线局域网标准工作组发布了两个物理层的扩充规范，即i e e e8 0 2 1 l b 、i e e e8 0 2 1 l a 。2 0 0 3 年又发布了i e e e8 0 2 1 1 9 标准。基于8 0 2 1 1 a的产品工作在更高的频段，具有更多不重叠的子频道和更高的数据通信带宽，得到了较为广泛的应用。8 0 2 1 l a 和8 0 2 1 l b 工作在两个完全不同的频带，采用完全不同的调制技术，因此两者是完全不兼容的，但可以共存于同一区域中而互不干扰。而之后的8 0 2 1 l g 有两个最主要的特征：高速率和兼容8 0 2 1 l b 。8 0 2 1 1 9 标2无线局域网安全协议测试平台的构建方法和技术研究准是下一个主流的无线局域网标准，它提供了高速数据通信带宽，并以较为经济的成本提供了对原有主流无线局域网标准的兼容。i e e e 除了制定上述的三个主要无线局域网协议之外，还在不断改善这些协议，并推出或即将推出一些新的相关协议。如：8 0 2 1 l d ，8 0 2 1 l e ，8 0 2 1 i f , 8 0 2 1 1 s等。此外，欧洲电信标准化协会( e t s i ) 的宽带无线电接入网络( b r a n ) 小组也着手制定h i p e r ( h i g hp e r f o r m a n c er a d i o ) 接入标准，任务之一是h i p e rl a n ，已推出h i p e r l a n1 和h i p e r l a n 2 。h i p e r l a n1 采用在g s m 网络中广泛使用的高斯最小移频键控( g m s k ) ，速率能达到2 0 m b p s 以上。h i p e r l a n 2 与i e e e 0 8 2 1 1 a一样采用o f d m 并工作在5 g 频段，速率为5 4 m b p s ，是一种高性能的局域网标准。h y p e r l a n 2 标准定义了动态频率选择、无线小区切换、链路适配、多波束天线和功率控制等多种信令和测量方法，用来支持无线网络的功能，它的数据链路层是面向连接的，因而能更好地实现服务质量( q o s ) 。作为一种迅速兴起的新技术，w l a n 也有一系列阻碍其市场发展的困难，如标准统一问题、设备互通性问题、安全性问题、可运营性问题、盈利模式等问题等等。其中，安全性问题是这些阻力当中的关键问题。由于在无线网络中，信息是通过无线电波的发射传送的，任何人都可以通过监听设备获取网络信息。另外，由于无线通信设备一般具有较小的计算能力、存储能力、电源保障能力，以及容易被丢失等特点，所以无线局域网中存在的安全问题更具有独特性和复杂性。相反，在有线网络中，线缆可以看作一道物理上的“边界”，攻击者如果连接不上网络线路，就无从获得网络上的信息。为了弥补这些安全漏洞，i e e e8 0 2 工作组研究开发了新的安全性更强的8 0 2 1 1 i 【1 】基于端口的访问控制协议及安全加密标准。在此基础上w i f i 联盟也发布了新的无线局域网安全标准w p a ( w i f ip r o t e c t e d a c c e s s ) 。面对无线局域网在国内的迅速推广以及安全问题越来越突出的现实，我国也在2 0 0 3 年7 月，国标委、信息产业部和国密办联合推出了我国的w l a n 安全标准w a p l l 2 】( w l a na u t h e n t i c a t i o np r i v a c yi n f r a s t r u c t u r e ，无线局域网鉴别保护基础结构，国标g b1 5 6 2 9 1 1 ) 。1 1 2 安全协议测试的意义和目的网络协议是网络实现信息共享和交换的基础，是构建网络的基石。对于安全协议来说，通常用于保证安全协议设计及实现的有效性、安全性的一种手段，是在设计协议规范时，采用形式化的方法对规范进行验证或证明。尽管形式化方法的研究在发现安全缺陷及改进协议安全性等方面都取得了很大成果，但是由于其在一方面忽略了某些关键细节，例如加密实现、协议边界等，另一方面它又不能第一章绪论保证自己使用的模型是完备的。因此，形式化的证明手段并不能为安全协议及其实现提供足够可靠的安全评价。同时，由于目前的网络协议多是以自然语言描述的文本，所以在实现安全协议时，程序设计人员对协议规范理解的偏差、软件的漏洞都可能使协议实现存在新的未知的安全问题。针对这些情况，研究人员提出了利用代码自动生成工具，由协议规范自动生成协议软件代码。虽然出发点很好，但是目前自动代码生成方法仍处于研究阶段，无法应用到实际协议开发中。综上所述，为了更进一步对安全协议及其协议实现的安全性提供保障，协议测试成为另一种必不可少的手段。安全协议测试主要包含以下几个部分：一致性测试：根据协议文本对协议实现的功能进行测试，检测其是否符合协议标准的要求；互操作性测试：检测不同的协议实现之间是否能可靠的进行通信交互；性能测试：是测定协议实现的性能特征，如响应时间、延迟等，并据此对系统性能做出评价。安全性测试：对安全协议的安全机制和安全协议实现平台的分别进行测试，并给出对被测对象的安全评价。其中，一致性测试是互操作性测试及性能测试的基础，用于检查给定的协议实现是否与规范等价，是确保不同实现版本和不同网络间能互操作的必需步骤。实现者对于协议规范的不同理解和可选的协议属性以及实现过程中的非形式化因素都会导致不同的协议实现，有时甚至是错误的协议实现。而安全协议的实现与其规范一致又具有双重的意义，其一是保证其协议能正确运行，其二，协议的一致性实现又是保障安全协议的安全性能的基础。因此，一致性测试不可或缺。安全性测试在现代软件开发过程中扮演着重要角色，其在安全协议开发中的地位尤为重要。首先，对于安全协议，传统的协议一致性测试并不足以保证安全协议的安全性，因为传统一致性测试只对实现与规范的功能是否一致进行验证，然而，实现包含了很多实现细节，通常比规范复杂得多。此外，一致性测试无法验证规范之外的行为。其次，协议规范可能存在漏洞以及实现者的错误理解，都可能导致实现存在漏洞。第三，安全协议软件实现上的漏洞，如缓冲区溢出等，通常也是不可避免的。最后，安全协议应用环境可能存在问题，例如由8 0 2 1 1 协议的缺陷而导致的s i f s 时隙攻击、n a v 向量攻击等拒绝服务类( d e n i a lo fs e r v i c e ，简称d o s ) 攻击。综上所述，结合安全协议本身的特点，本文认为，安全协议测试的主要方面应为一致性测试和安全性测试。其中：一致性测试的主要目的是检测所实现的安全协议是否符合协议规范，从而为协议能够正常运行和抵御攻击提供基础保证；4无线局域网安全协议测试平台的构建方法和技术研究安全性测试则主要检测所实现的安全协议是否能抵御各种已知和未知的攻击，进而对所实现的安全协议的安全性能给出相应的反馈，为协议本身和协议实现的完善提供有价值的参考。1 3 协议测试技术的国内外发展现状目前的协议测试已经不仅仅是产品开发研制过程中一个简单的检测支持过程，而是发展成为计算机网络技术的一个重要分支和协议工程学的一个重要组成部分。对协议测试技术的研究将直接影响到计算机网络技术的进步和世界网络市场的竞争与发展。因此，很多国家都投入了大量的人力物力从事协议测试的研究工作。例如：英国的国家物理实验室n p l ，法国国家通信研究中心、德国国家通信研究局g m d 、美国国家标准化研究局、美国新罕布什尔大学互操作研究实验室、清华大学计算机科学与技术系的网络和协议测试实验室以及中科院计算所的网络测试实验室等单位都在这个领域投入了大量的研究力量。迄今为止，协议测试领域所进行的工作主要集中在通信协议的一致性测试方面。协议一致性测试是检查协议实现与协议规范是否一致的过程，是保证协议实现能够按照协议规范准确工作的重要步骤。目前，对通信协议的一致性测试已经有一套相对完整的自动化测试理论，但是其理论支持和对具体协议的测试实践上还存在着一定差距。对于作为网络协议子类的安全协议，目前并没有一套高效且适用的一致性测试方法。在安全性测试方面，现有研究主要集中在软件安全性测试方面。常用方法是渗透测试，即在开发过程中执行已定义的测试脚本以发现安全漏洞。渗透测试通常分为四类：依赖性测试；未预期的用户输入测试；设计漏洞测试；实现漏洞测试。文献 3 提出了被动监听和主动检测的方法测试安全协议的消息保密性。文献 4 提出了自学习的主动测试方法。目前在安全性测试方面已经取得的研究成果虽然对安全协议的安全性测试有一定的参考价值，但是由于它们对协议层面的渗透测试并没有给予应有的重视，因此，对于安全协议的安全性测试来说，这些方法并不是完全适用的。1 4 研究内容和目的本文作者所在的研究小组借鉴网络协议测试工程学的理论，并结合无线局域网安全协议的特点，提出一套针对无线局域网安全协议的测试方法，在解决其中的相关技术难题的前提下，最终设计出一个通用的无线局域网安全协议测试平台。该平台能够对软件实现的w l a n 安全协议进行一致性测试和安全性测试。一致性测试主要检测所实现的安全协议是否符合协议规范，为协议能够正常运行提供第一章绪论保证；安全性测试主要是以攻击的方式来完成检测的功能，由内置的测试系统检测所实现的安全协议是否能抵御各种己知的攻击，如地址欺骗、重放攻击、中间人攻击以及各种拒绝服务类攻击，并同时提供可扩展的模块，以便应用者自行构建攻击序列进行扩展测试，进而综合判断所实现的安全协议的安全性能。系统可根据测试结果对所实现的安全协议的标准化程度以及安全性能给出客观的反馈。1 5 论文结构安排第一章首先介绍w l a n 及其相关协议的发展，之后引出了安全协议测试的意义和目的，接着，对协议测试相关的背景知识和发展现状进行了简要的概括和总结，并在本章的最后给出本文的主要研究方向和内容。第二章介绍了协议测试的基础理论，其中包括了协议工程和协议测试的基本概念，协议的形式化方法，接着重点介绍了一致性测试的结构和测试方法。对一致性测试中几种常用的测试序列生成方法作了概述。第三章是对w l a n 安全协议测试平台中一些重要部分的相关技术细节的详细阐述。这些细节主要包括在进行一致性测试时，对w l a n 安全协议实现进行主动测试的过程中，测试序列的具体生成方法，以及在被动测试时，如何用帧过滤器来实现对信息帧的自动筛选功能。安全性测试方面，平台安全测试部分主要介绍一些典型的针对硬件平台的攻击手段，给出原理分析和相关帧序列的构造，协议安全测试部分则给出了应用原理。第四章描述无线局域网安全协议测试平台的总体设计，各个模块实现的功能以及模块之间的相互关系。第五章以8 0 2 1 1 b 协议的认证接入部分为例，在主动测试方面，通过对接入点端和站点端状态转换的形式化描述，得到各自的状态转换图，并根据前述算法自动得出其测试序列。被动测试方面，则通过对抓取的信息帧的自动过滤，得到过滤结果，并对筛选后的帧进行相关分析。第六章，总结全文，并针对研究的不足提出今后需要继续努力的方向。第二章协议测试的一般理论第二章协议测试的一般理论2 1 协议工程和协议测试2 1 1 协议工程的相关概念协议的开发主要包括协议设计、协议描述、协议验证、协议实现、协议测试和协议维护等阶段。在协议的开发过程中，需要采用一体化、形式化的方法，这种开发过程被称为协议工程( p r o t o c o le n g i n e e r i n g ) 哺1 。协议工程中的“形式化”指的是：用形式化描述语言( ( f o r m a ld e s c r i p t i o nl a n g u a g e s ：f d l ) 连接协议开发的各个阶段。利用形式化，我们可以力争做到协议的验证、实现、测试在协议工程系统中的自动化进行。协议描述阶段是对自然语言表达的协议进行形式化描述，研究如何用数学模型来精确描述协议，主要解决用自然语言描述协议的不精确性和二义性问题。协议验证技术是采用数学方法来证明协议的形式化描述中是否存在逻辑错误，如死锁，活锁，不可达等等。协议的实现则是将协议文本或者协议的形式化描述变换成为计算机可执行代码的过程。协议的测试是检查协议实现与协议规范是否一致的过程，是保证协议实现能够按照协议规范准确工作的重要步骤。2 1 2 协议软件测试的一般方法目前，协议测试的研究主要集中在主动测试领域，主动测试以测试用例为中心，由测试程序完全控制整个测试过程，负责生成测试序列，并将其发给待测系统( i m p l e m e n t a t i o nu n d e rt e s t ：i u t ) 作为对i u t 的激励，然后由测试程序继续监测i u t ，看其能否根据激励做出正确的响应。主动测试是一种非常有效的测试手段，但由于测试程序要与i u t 直接通信，因此做主动测试时i u t 一般要与其它网络分离。此外，由于协议越来越复杂且差异性越来越大，以致在采用主动测试时，测试程序的编写和测试序列的构造等方面都非常繁琐。被动测试则采用了另一种思想，它不向通信实体发送任何报文，而只是“被动”地监听通信实体之间的输入输出行为，通过分析监听到的数据，来推断协议实现中是否存在错误。被动测试比较简单，不需要构造测试集，支持在线测试，且可以长时间进行测试而无需人工干预。尽管被动测试具有上述优点，但由于它不控制测试过程，所以相较于主动测试来说，被动测试更加不能保证测试的完备性。无线局域网安全协议测试平台的构建方法和技术研究主动测试和被动测试的方法有着共同的弱点，即：都只能够用来发现错误而并不能保证协议实现是没错的。实际上，在测试工程的实践中，要在细节上保证测试的完备性往往并不现实，所能做的只是在测试方式和内容上给出尽可能周密的考虑，使测试的结果尽可能的客观，全面。对于主动测试来说，即使协议实现通过了主动测试，在实际运行中还是可能会出错，而被动测试则往往能够发现实际运行中出现的差错。由于主动测试和被动测试两种方式各有利弊，所以，在实际的测试中，将二者结合起来，使其优势互补，成为一种合适的选择。主动测试和被动测试主要区别在测试分析方法上，在测试平台的构建上，两者并无大的区别。2 1 3 协议的形式化方法如前文所述，使用自然语言描述的协议规范，人们很难做出有效的测试。因为这种基于生活语言的规范描述不仅在表达上可能出现模糊并导致二义性，而且往往不能将协议的各种属性清楚的分离开，而进行测试的首要问题就是去除规范中可能产生的歧义和错误。目前解决该问题的一个很好的方法是对协议使用形式化的语言就行描述，使协议模型化。形式化描述是通过一系列形式化理论、模型和方法，对协议进行精确的描述。形式化描述是协议设计、实现、测试的基础，对协议实现的正确性、完整性和标准性有重要的意义。2 1 3 1 基于形式化的描述模型形式化方法是指用数学方法描述和推理基于计算机的系统，直观的说，就是规范语言加形式推理。其在技术上通过精确的数学手段和强大的分析工具得到支持。表现形式通常有逻辑，离散数学，状态机等等。规范语言包括语法，语义以及满足关系等几部分。规范语言可以分为四类：抽象模型规范法，代数规范法，状态迁移规范法和公理规范法。基于协议的形式化描述方法，己经研究并开发出多种形式的模型，而当前应用比较广泛的主要有以下几种：有限状态机( f i n i t es t a t em a c h i n e ) 、p e t r i 网( 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 em a c h i n e s ) 。在一个l t s 中是不区分输入和输出的，输入与输出通常表达成相互作用的状态。一个具有如是属性的l t s 的子集被称为输入输出迁第二章协议测试的一般理论移系统( i o t s ) ，i o t s 与输入输出状态机器( i o s m ) 非常相似。不同的是在这个模型中，当输入不导致任何输出的情况时，也将为这些状态定义表示状态迁移的边，这些边就表述没有输出的自环。另一个不同之处为l o t s 中的状态集和迁移集都可能是无限的，而i o s m 则都是有限的，因而i o s m 经常被作为有限状态机。几乎以上所有方法都可以用来规范，描述，以及分析安全协议。但由于有限状态机f s m 方法发展成熟，且用f s m 来描述协议实现具有简明直观的优点，因此该方法被本文所描述的安全协议测试平台所采用。f s m 对于有限状态空间和可以确定的协议行为具有足够的描述表达能力，并且可以为测试人员提供最大的测试控制能力。简单的说，f s m 是l t s 的子集，只不过对于每一个状态迁移，一个输入对应一个或者几个( 也包括零个) 不同的输出。一个有限状态机m 是一个六元组：m = ( i ，o ，s ，s 。，6 ，入) 。其中i 是输入符号集，o 是输出符号集，s 是状态符集，i ，0 ，s 均为非空集合，s 。是初始状态。6 ：sxi s 是状态转移函数( 初始状态到后状态的转变)入：sxi 专o 是输出函数( 初始状态+ 输入符号= 输出符号)状态转移函数5 和输出函数入共同定义了状态的转换集合t ，因此，有限状态机也可以看作是一个五元组m = ( i ，0 ，s ，s 。，t ) 。t 中的每个元素可以表示为一个三元组t = 。s ，s 称为转换t 的头状态。i i 和o = 入( s 。，i ) 0 分别称为转换t 的输入和输出。s j = 6 ( s 。，i ) s 称为转换t 的尾状态。_ 叶6 ，表示有限状态机m处于状态s j 时接受输入i 使状态转移到s ，并且产生输出o 。当使用有限状态机模型描述一个协议规范时，状态是协议实体能够停留的稳定条件，输入是协议实体从外界接收到的报文激励或者内部产生的事件激励，输出是协议实体对外界的响应n 3 。2 1 3 2 安全协议形式化分析的发展一般公认，n e e d h a m 和s c h r o e d e r 首次提出了使用形式化的方法对安全协议进行分析。d o l e v 和y a o 发表了第一篇用形式化方法对安全协议进行分析的文章。d o l e v - y a o 定义了安全协议并发运行环境的形式模式，密码算法无关的验证以及敌手的攻击行为等等，形成了被后来者所尊崇的d o l e v - y a o 模型。s h o u p 发展了模拟模型。这里模拟的概念来自于零知识证明的密码学成果。s h o u p 使用两个系统：理想( i d e a l ) 系统和实际( r e a l ) 系统。主要安全保障在于：敌手在同实际系统交互时能够得到的结果与敌手同理想系统交互所得到的结果一样多。这样，从理想模型的安全性就可以体现实际系统的安全性。参加安全协议运行的主体可以分为两种9一1 0无线局域网安全协议测试平台的构建方法和技术研究一种是诚实主体，在协议运行中按照协议的规范进行，如果收到不合规范的信息，则认为与自己无关，另一类主体就是所谓的入侵者。他们能力的强弱，直接反映到所使用的敌手模型中。最为常见的，形式化方法中最流行的敌手模型是d o l e v - y a o 模型。在协议运行的开始或者运行过程中，敌手可以窃听，消去以及任意安排公开通信通道上的消息。他可可以从观察到的消息产生新的消息。并将他们加入到信道中。敌手能够用自己已知的密钥对任意的消息加密。敌手还可以解密一个收到的密文，前提是敌手知道相应的密钥。敌手可以根据需要，截断信道上传输的任何消息，注入自己产生的新消息，发送该消息至目标主体或者任何其他主体哺1 。基于d o l e v - y a o 模型的最早的安全分析系统是i n t e r i o g a t o r ，作为一个软件工具，它的原理是企图通过遍历整个状态空间，找到协议安全的漏洞。其基本思想被后来许多系统所继承，也为本文所描述的系统采用。2 2 协议的一致性测试协议一致性测试是检查协议实现与协议规范是否一致的过程，是保证协议实现能够按照协议规范准确工作的重要步骤。一致性测试的研究最早于1 9 7 9 年由英国国家物理实验室( n a t i o n a lp h y s i c a ll a b o r a t o r y ：n p l ) 展开。1 9 8 3 年，n p l开始了基于o s i 模型的协议形式化和一致性测试的标准化工作。法国的a d i 和德国d a r m s t a d t 的g m d 等也是最早的参与者。协议一致性测试经过2 0 来年的发展，取得了很大的进展。国际标准化组织i s o 专门制定了一个国际标准i s 0 9 6 4 6 一o s i的一致性测试方法与框架哺3 ，这个标准的制定具有里程碑意义。2 2 1 协议一致性测试模型和方法论总的来说，协议的一致性测试是验证某个待测的协议实现是否能够按照协议文本正确执行的过程。一致性测试只依据被测系统的外部行为做出分析判断。它基于这样一个前提，即被测系统( s y s t e mu n d e rt e s t ：s u t ) 被看成是一个黑盒子，任何被测系统一致性测试的结果只与其对输入的响应有关，如图2 1 所示：测试系统待测实现图2 1 协议一致性测试模型i s o i e c 在i o s i e c9 6 4 6 一致性测试的方法论与框架结构( c t m f ) 标准中，对第二章协议测试的一般理论o s i 一致性测试过程作了详细定义。c t m f 一由七个部分组成，它包括了一致性测试概念的描述，测试套描述，测试系统结构，测试表示，测试实现，测试方法以及测试的组织结构的描述。根据i s o i e c9 6 4 6 一致性测试方法论的规定，测试标准包括三个部分：抽象测试集( a t s ) ，协议实现一致性说明( p i c s ) ，协议实施附加信息( p i x i t ) 。可执行测试集( e t s ) 是在以上三部分的基础上生成的。a t s 是测试软件的核心，其内容直接来自于规范，是描述测试过程的文本。每个a t s 规定某一标准协议的测试目的、测试内容和步骤，所以a t s 的形成决定了测试的质量。一个a t s 可以具有多个测试组，每个测试组用于为测试项提供一个过程安排，它们对测试集的规划、开发和执行起辅助作用。每一个测试组由若干个测试项组成，每个测试项又含有一系列测试步，测试集的最小单元是测试事件。其中，测试项是测试集的最重要的一级，每个测试项都有一个特定事件，例如证明被测协议实现i u t 具有某种要求的能力或某种要求实现的行为( 如当特定事件在某特定状态下发生时，i u t 所做出的响应) 。c t m f 将被测系统与外界的接口定义为控制观察点( p o i n t so fc o n t r o la n do b s e r v a t i o n ：p c o ) ，通过p c o 的激励和响应定义为抽象服务原语( a b s t r a c ts e r v i c ep r i m i t i v e s ：a s p ) ，a s p 所封装的实际需传送的数据定义为协议数据单元( p r o t o c o ld a t au n i t ：p d u ) ，需要有测试系统产生为实现测试目的所要求的a s p 或p d u 作为激励，并观察i u t 在收到此a s p 或p d u 后的动作，验证其最终所处的状态，以确定i u t 的动作及处理是否符合规范的规定。一一般而言，一致性测试集合应该具有以下分级式结构：测试集、测试组、测试项、测试步和测试事件。其中，每个测试项由前测试步、测试体和后测试步组成。每个测试步都是由一组有序的测试步或测试事件组成的，每个测试事件表示发送或接收一个帧或一个消息。其中前测试步的作用是将i u t 置为测试体所需的初始测试状态。测试体是一个测试组中，为达到测试目的所必需的一组测试步。而测试判定如：通过、失败或无结论将指出测试项的可能输出。后测试步的作用则是把i u t 从结束状态置回到一个稳定的空闲状态中。后测试步图2 2 测试项的构成1 2无线局域网安全协议测试平台的构建方法和技术研究在执行测试项的过程中，测试体通过控制观察点对i u t 的输入和输出进行控制和观察，并分析得到的输出是否与测试项预先规定的输出相一致，从而得到以下结论：通过：表示得到的输出与抽象测试项描述中表示“通过的输出集合存在一个映射；失败：表示得到的输出与抽象测试项描述中表示“失败 的输出集合存在一个映射；无结论：表示得到的输出与抽象测试项中所描述的输出均不一致。如上所述，通过对所设定测试项的执行结果的分析，即可最终得出被测协议实现与协议文本的一致化程度的结论。2 2 2 一致性测试中测试序列生成的形式化方法一致性测试是性能测试、互操作性测试以及安全性测试的基础，是协议测试的关键部分。根据测试分析方法的不同，又分为主动测试和被动测试两种，而如何从协议标准的描述中获得进行协议测试所需要测试集这一问题，又引出了测试序列生成方法的研究，这是主动测试的主要工作部分。对于通讯协议来说，数据流的类型往往分为数据流和管理、控制流，因此协议一致性主动测试又可以分为对控制流的测试以及对数据流的测试，由于数据流作用单一，因而当前的一致性测试研究多集中于对管理、控制流的测试。目前广泛应用的基于有限状态机的控制流测试序列的生成方法主要有以下四种旧1 ：( 1 ) 转换回路法( t r a n s i t i o nt o u rm e t h o d ) ，也称t 方法( 2 ) 区分序列法( d i s t i n g u i s h i n gs e q u e n c e s ) ，也称d 方法( 3 ) 特征序列法( c h a r 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方法下面对以上方法分别进行简要介绍：2 2 2 1t 方法有限状态机常常用有限状态图的方式来表示，对于一个有限状态图来说，最直观的测试方法就是从初始状态出发，将其中所有的转换边至少遍历一次。这样的一次遍历，就是对有限状态机的一个覆盖。t 方法一种最简单的实现是将随机将一个正确的输入激励作用在有限状态机上，直至所有的转换都被遍历至少一次为止。但是这样生成的测试序列可能包含很多重复冗余的转换。另一种实现是借助于中国邮递员算法。中国邮递员问题用图论的方式来描述，第二章协议测试的一般理论1 3即：要求在图中找一条路径，使得这条路径经过所有的边，且距离最短。针对t方法的冗余输入问题，u y a r 和d a h b u r a 曾借助于“中国邮递员 方法，保证了在某些情况下生成测试序列具有较小的开销n 们。但中国邮递员算法要求目标状态图是必须是强连通的。t 方法的另一个不足之处是，该方法在测试过程中只检测了状态迁移的状况，而没有对转换到达的状态进行检查，因而在某些情况下，影响了其错误检测能力。2 2 2 2d 方法d 方法首先对有限状态机构造一个区分序列d s ( d i s t i n g u i s h i n gs e q u e n c e ) ，然后根据该区分序列构造测试输入序列。该方法的测试输入序列数目较少，但并不是每一个状态机都存在区分序列，因此限制了该方法的使用。d 方法的研究主要是基于c h e c k i n g e x p e r i m e n t s 的结果，由三个部分组成：初始序列；状态识别序列；变迁检查序列。d s 使每个状态对输入序列的反应不同于其他，这是通过构造可识别树得到的。d 方法的主要优点是能发现故障点，缺点是：d 序列不能总是保证存在，序列优化方法比较难，序列长度也比较长1 。2 2 2 3w 方法该方法基于状态机的状态识别集来构造测试输入序列，每个状态机只要是精简的都存在状态识别集，因此该方法的适用性较为普遍，但该方法产生的测试输入序列数目太多，在实际应用中会使测试效率降低。w 方法包括了两个输入序列集w _ s e t 和p _ s e t 。w 集合是f s m 最小的特征集。它使得每对状态能够相互区分。即对不同的点应用w 集观察到的输出应试能够区分的。p 集合包括了所有部分路径，由一个测试树构成。它的根节点是初始状态，而每个变迁只出现一次。该方法的优点是适用于描述非完备的自动机。缺点是：对每一个点的测试都必须使用r e s e t 功能，导致其在实际的复杂系统中很难使用。有一种对w 方法的简化方法称为w p 方法，该方法的前提条件是规约说明和实现中的有限状态机是精简的、强连通的、完备的，并且实现中的每个状态都存在r e s e t 操作且都已正确实现。强连通可以通过添加r e s e t 操作来实现，当有限状态机处于任意状态时，通过应用r e s e t 操作它都可以返回到初始状态，这样使得每一个测试输入序列都从初始状态开始，否则无法保证测试的正确性n2 1 。该方法保证了与w 方法具有相同的错误覆盖度，但产生的测试输入序列数目让然较多。2 2 2 4u 方法u 方法首先为状态机的每一个状态得到一个识别序列，该识别序列叫作唯一输入输出序列( u n i q u ei n p u t o u t p u ts e q u e n c e ：u i o ) ，该识别序列可以区分每1 4无线局域网安全协议测试平台的构建方法和技术研究一个状态，然后根据该识别序列构造测试输入序列，因此u 方法又被称作u i o 方法。但并不是所有的有限状态机都存在u i o ，如果状态机不存在u i o ，则无法构造测试输入序列。对于u i o 方法的改进也已经有了许多研究成果。一下是集中对u i o 方法的改进n 副。s u i o 方法：s u i o 方法利用一个中国邮递员回路将f s m 的所有测试子序列最优地连接起来，从而大大缩短了测试序列的长度。m u i o 方法： , f l j i o 方法是针对s u i o 方法的一种改进，这种改进依赖于具有多个最短u i o 序列的状态的一个适当的u i o 序列的选择，这种选择导致最终测试序列长度的进一步缩小。叠加方法：叠加方法是针对测试序列可能重叠这一信息，将测试子序列经过叠加处理后，使得单纯用于测试子序列连接的转换个数大大减少，从而最终降低测试序列的长度n 射。形式叠加方法：形式叠加方法是对叠加方法的一种扩展，它不限定仅仅使用最短u i o 序列，获得更加明显的叠加处理效果，从而达到优化测试序列的目的。2 2 2 5 测试序列生成方法小结从以上介绍的四种方法来看，尽管w 方法能够发现较为复杂的错误，但是因为它的测试序列长度在实际的复杂系统中是很难使用的，同时在现实中，已经去掉了一些错误，因而有些强大的测试功能就显得“多余。d 方法的主要优点是能够发现故障点的位置，但是由于d 序列不能保证一定存在，而且比较难以进行d方法的优化，所以它的测试序列往往过长。相对而言，u i o 方法生成的测试序列比较短，错误检测能力也比较强。总体上讲，w ，d ，u 都是基于特征序列的方法，而u 方法事实上是d 方法和w方法的子集，它们的核心思想是划分测试子序列，逐个确定状态并测试状态转移。相对于t 方法，d ，u ，w 三种方法的现实需求是为了更有效的解决t 方法不能有效识别当前状态的问题。因而，对于某一类特殊的，每个状态都能够根据其独有的激励和输出来唯一确定的有限状态机，u 方法实际上又回归与t 方法。2 3 协议的安全性测试安全性测试在保障协议实现的安全性方面有着非常重要重要的作用。首先，对于安全协议，传统的协议一致性测试并不足以保证安全协议的安全性，因为传统一致性测试只