（计算机应用技术专业论文）入侵检测系统中高效模式匹配算法的研究.pdf

上海大学硕士学位论文 ! ! ! ! ! 坐! ! ! ! 坐! ! 型! ! ! ! ! ! ! g ! ! ! ! ! ! ：竺型￥ 摘要 基于模式匹配技术的入侵检测系统由于其检测的准确性高、误报率低、实用 性强而被广泛应用。但是随着网络速度的提高，这种入侵检测系统的处理速度跟 不上，导致了入侵事件的漏报，提高入侵检测系统的检测速度是目前亟需解决的 关键问题。改进入侵检测系统中采用的模式匹配算法的性能是解决该问题的一种 有效途径。 本文在分析入侵检测系统中常用模式匹配算法的基础上，设计了两种高效模 式匹配算法，并将其与协议分析技术相结合应用于基于模式匹配技术的入侵检测 系统中。 本文首先分析了入侵检测系统中常用的模式匹配算法，并通过实验方法对 b m 算法、a c 算法和w m 算法进行了性能对比，讨论了这三个算法的最佳适用 场合。进而对b m 算法和w m 算法分别进行了改进：采用以两个字符为基本处 理单元的思想，设计了一种高效的单模式匹配算法b m b 算法；分离w m 算法 中h a s h 表和s h i f t 表功能重合部分，并利用文本窗口中最右b - 1 个字符同下 一字符一起确定文本窗口的右移量，设计了一种w m 的改进算法w m n 算法。 实验证明改进后的这两个算法减少了匹配时的比较次数，从而减少了匹配所需的 时间，提高了系统的性能。 本文还将改进后的两个模式匹配算法应用于一个基于移动代理的入侵检测 系统原型中，结合协议分析技术重新设计和实现了该原型中的数据包分析代理。 关键词：入侵检测系统，模式匹配，协议分析，移动代理 v 上海大学硕士学位论文 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 型! ! ! ! ! 竺韭! ! ! ! ! ! ! ! 坐! a b s 仃a c t t h ei n t r u s i o nd e t e c t i o ns y s t e m ( i d s ) b a s e do np a t t e r nm a t c h i n gi s a p p l i e d w i d e l yb e c a u s eo fi t sh i g hd e t e c t i o na c c u r a c y , l o wf a l s ed e t e c t i o nr a t ea n ds t r o n g p r a c t i c a b i l i t y h o w e v e r ，w i t ht h ea c c e l e r a t i o no ft h en e t w o r ks p e e d ，t h ep r o c e s s i n g s p e e do fi d sc a r l n o tc a t c hu pw i t ht h en e t w o r ks p e e d ，r e s u l t i n gi nt h em i s s i n g d e t e c t i o n so fi n t r u s i o nf r e q u e n t l y s o ，i m p r o v i n gt h ed e t e c t i o ns p e e do fi d sh a s b e c o m et h ek e yp r o b l e mt h a tm u s tb es o l v e d b e t t e r i n gt h e p e r f o r m a n c eo ft h ep a t t e r n m a t c h i n ga l g o r i t h m su s e di ni d s i so n eo f e f f e c t i v es o l u t i o n st ot h i sp r o b l e m t h r o u g ht h ea n a l y s i so fc e r t a i np a t l e mm a t c h i n ga l g o r i t h m sc o m m o n l yu s e di n i d s ，t h i st h e s i sd e s i g n st w oe f f i c i e n tp a t t e r nm a t c h i n ga l g o r i t h m s ，t h e nc o m b i n e s t h e mw i t hp r o t o c o la n a l y s i st e c h n o l o g y , a n da p p l i e st h e mt oi d sb a s e do np a t t e r n m a t c h i n g f i m t l y ，t h i sd i s s e r t a t i o na n a l y z e st h ep a r e mm a t c h i n ga l g o r i t h m st h a ta r e c o m m o n l yu s e di ni d s ，m a k i n gac o m p a r i s o nb e t w e e nt h ea l g o r i t h m sb m ，a ca n d w mi np e r f o r m a n c ea n ds u i t a b i l i t yb ye x p e r i m e n t a t i o n t h e nt h em o d i f i e db m a l g o r i t h m ( n a m e l yb m b ) a n dt h em o d i f i e dw n ia l g o r i t h m ( n a m e l yw m n ) a r e s u g g e s t e d t h eb m ba l g o r i t h mi sak i n do fs i n g l e p a t t e r nm a t c h i n ga l g o r i t h m ，a n di t s p r o c e s s i n gu n i tc o n s i s i t so ft w oc h a r a c t e r s t h ew m na l g o r i t h me l i m i n a t e st h e d u p l i c a t ef u n c t i o n si nh a s ht a b l ea n ds h i f tt a b l e ，a n du s i n gt h eb - 1c h a r a c t e r si n t h em o s tr i g h ts i d eo fat e x tw i n d o wt o g e t h e rw i t ht h en e x tc h a r a c t e rt od e t e r m i n et h e d i s t a n c eo fr i g h ts h i ro ft h et e x tw i n d o w t h eb m ba l g o r i t h ma n dt h ew m n a l g o r i t h mr e q u i r ef e w e rc o m p a r i s o nt i m e sa n dp e r f o r mm o r ee f f i c i e n t l y t h i st h e s i sa l s od e a l sw i t ht h ea p p l i c a t i o no fb m ba l g o r i t h ma n dw m n a l g o r i t h m ，w h i c ha r eu s e dt o g e t h e rw i t hp r o t o c o la n a l y s i st e c h n o l o g yt oi m p l e m e n t t h ed a t aa n a n l y s i sf u n c t i o n a l i t yo f am o b i l ea g e n t b a s e di d sp r o t o t y p e k e y w o r d s ：i n t r u s i o nd e t e c t i o ns y s t e m ，p a t t e r nm a t c h i n g ，p r o t o c o la n a l y s i s ， m o b i l ea g e n t 上海大学硕士学位论文 t h ep o s t g r a d u a t et h es i so fs h a n g h a iu n i v e r s i t y 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：! 遇迫日期：兰堡：兰：竺 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：型鸥 导师签名：期：塑! 笪 i i 上海大学硕士学位论文 些! ! ! ! ! g ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 竖! ! ! ! ! ! 第一章序言 1 1 课题的背景、目的与意义 面对大量的安全问题，入侵检测系统 1 】作为一种关键的网络安全技术得到了 广泛的应用和研究。入侵检测系统是对防火墙的必要补充，作为重要的网络安全 工具可以对系统或网络资源进行实时检测，及时发现闯入系统或网络的入侵者， 也可以预防合法用户对资源的误操作。 入侵检测系统根据其数据来源可以分为两类【2 】：基于主机的入侵检测系统 ( h d s ) 和基于网络的入侵检测系统( n d s ) 。 基于主机的入侵检测系统通常从主机的审计记录和日志文件中获取所需的 数据，并利用主机上的其它信息，如文件系统属性、进程状态等，来完成检测攻 击行为的任务。基于主机的入侵检测系统具有检测效率高、分析代价小、分析速 度快等特点，能够迅速并准确地定位入侵者，并可以结合操作系统和应用程序的 行为特征对入侵行为进一步分析。它存在的问题是：首先，它严重依赖于特定的 操作系统平台，可移植性差；其次，它在一定程度上依赖于系统的可靠性，它要 求系统本身应该具备基本的安全功能，并进行合理的设置，然后才能提取入侵信 息；另外，由于它在所保护的主机上运行，将影响宿主机的运行性能，特别是当 宿主机是服务器的情况下。 基于网络的入侵检测系统通过网络接口提取网络数据包，并用协议分析】、 特征匹配和统计分析等方法判断数据包中是否包含攻击行为。它分析的对象是网 络数据包，其中包含的网络协议通常是标准化的，因此，一般没有移植性问题。 另外，它通常被布署在独立主机上，采用被动监听的工作模式，故不会影响其它 主机或服务器的自身运行。网络监视的主要缺点是数据量过于庞大，并且它难以 结合操作系统特征对网络行为进行准确的判断。 现有入侵检测系统的数据分析方法主要采用基于误用检测的模式匹配技术【3 】 4 1 和基于异常行为的检测技术【5 1 6 1 。前者能够准确检测到已知的攻击模式，具有 较高的检测率和较低的误报率，这种技术已广泛用于网络入侵检测系统中_ 】。但 是这种方法只能检测到已知的攻击模式，模式库需要不断的更新才能检测到新的 攻击行为。后者可以检测到未知的入侵行为，但是具有较低的检测率和较高的误 报率。在目前的实际系统中，大多采用基于特征的模式匹配检测技术，不过，在 若干优秀的入侵检测系统中也采用了不同形式的异常入侵检测技术和相应的检 测模块。 近年来随着高速网络技术如千兆以太网、a t m 等的快速发展，入侵检测系统 上海大学硕士学位论文 ! ! ! ! ! ! ! g ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! g ! ! ! ! ! ! 坚：! ! ! 如何在高速网络环境下实时有效地正常工作已成为一个研究重点。目前大多数基 于特征的模式匹配技术的入侵检测系统很难处理1 0 0 m p b s 网络满负荷时的数据 量，而1 0 0 0 m b p s 更是难以达到的目标。本文以面向高速网络环境下基于特征模 式匹配技术的入侵检测系统为研究目标，在综合分析现有的基于特征模式匹配技 术的入侵检测系统性能和数据分析方法的基础上，设计高速网络环境下基于特征 模式匹配技术的入侵检测系统的数据分析算法和解决方案。 1 2 本文进行的工作与结构 1 2 1 本文主要工作 本文在用实验方法对入侵检测系统中常用模式匹配算法进行研究和分析的 基础上，研究高效的模式匹配算法。市教委基金课题一智能a g e n t 技术在网络入 侵检测系统中的应用研究中设计了一个基于移动代理【8 】的分布式入侵检测系统 原型( m a d i d s ) 。m a d i d s 中数据包分析代理的性能较差，本文采用高效的模 式匹配算法。结合协议分析技术，开发一个高性能的数据包分析代理，提高 m a d d s 的性能。 本文主要研究工作有如下三个方面： 1 系统分析入侵检测系统中常用的模式匹配算法，并通过实验方法对b m 算法、a c 算法和w m 算法进行性能分析，说明这三种算法各自的最佳适用场合， 为模式匹配算法的选择和改进提供指导。 2 通过对b m 算法和w m 算法分别进行改进，设计高效的模式匹配算法， 并用实验证明改进算法的高效性。 3 针对m a d i d s 中数据包分析代理性能不足的问题，将设计的高效模式匹 配算法结合协议分析技术应用到m a d i d s 中，重新开发一个数据包分析代理来 提高m a d i d s 的性能。 1 2 2 本文组织结构 第一章简要介绍了本文研究的背景、目的和意义，概括了所做的工作及本文 的结构；第二章主要介绍本课题研究所涉及的模式匹配算法和协议分析技术：第 三章深入研究现有入侵检测系统中常用的模式匹配算法，并做性能对比分析试 验，在此基础上分别对b m 算法和w m 算法进行改进：第四章采用模式匹配和 协议分析技术重新设计并实现m a d i d s 中的数据包分析代理。第五章对本文的 课题研究工作进行总结，并提出未来需要做的一些工作。 2 上海大学硕士学位论文 ! ! ! ! ! ! 堡! ! ! ! ! ! ! ! ! 竺! ! ! ! ! 竺g ! ! ! 旦! ! ! ! ! 坐z 第二章模式匹配算法和协议分析技术 2 1 模式匹配算法概述 为描述方便引入下述定义 定义1 定义2 定义3 定义4 定义5 t ( t e x t ) 为待匹配的主串，标识为y 0 1 ，n - 1 ，长度为l t - = i i 。 p ( p a t t e m ) 为待匹配的模式串，标识为x 0 ，1 ，m 一1 】，长度为l p = m 。 t 和p 建立在有限字符集( a l p h a b e t ) 上，标识为，大小为o 。 对t 进行扫描时需要用的窗口w i n d o w 大小为m 。 将w i n d o w 和t 一端对齐，比较w i n d o w 中和p 中的字符称为尝试 ( a t t e m p t ) 。 定义6 ：在t 中发现一个和p 完全匹配或不匹配时，窗口右移值为s h i f t 。 对于给定的t = y 【0 ，1 ，n - 1 和p = x 【o ，1 ，m - l 】，在t 中寻找所有出现的p 的过程就是模式匹配。 根据在匹配过程中同时匹配的模式串个数，模式串匹配算法可分为单模式匹 配算法和多模式匹配算法。依据其功能来分，模式匹配算法可分为三类：精确串 匹配算法、近似串匹配【9 算法和正则表达式匹配算法【1 0 l 。精确串匹配算法是指在 数据序列中查找出与一个或多个特定的模式串完全一致的子串及其出现的位置， 例如串匹配在精确文本检索中的应用；近似串匹配算法是指按照算法定义的相似 程度，在数据序列中查找所有与一个或多个特定的模式串的相似程度在可接受范 围内的所有子串及其出现位置，主要应用于计算生物学 1 1 1 领域；正则表达式匹配 算法是指根据正则表达式的描述，在数据序列中查找满足正则表达式的所有子串 的出现位置，主要用来处理简单的关键字匹配无法描述的问题。另外，还可将某 些串匹配问题用硬件实现【1 2 】，这就是硬件匹配( h a r d w a r em a t c h i n g1 。 最早的单模式串匹配算法是b r u t e f o r c e 算法，该算法从主串的第一个字符开 始和模式串中的第一个字符比较，若相等，则逐个比较后续字符，否则从主串的 下一个字符开始再重新和模式串的第一个字符比较；b f 算法在最坏的情况下的 时间复杂度为o ( m n ) ( m 和n 分别为模式串和文本的长度) ，而且在主串中出现多 个与模式串部分匹配子串的情况下，主串的指针需要经常回溯，算法的效率很低。 1 9 7 0 年，c o o ks a 在理论上证明了模式串匹配问题可以在o ( m + n ) 时间内解决， 随后k n u t h d e 和p r a t tv r 仿照c o o k 的证明构造了一个算法，与此同时，m o r r i s j h 在研究正文处理时也独立地得到与前述两人本质上相同的算法，这两个算法 称为k n u t h m o r r i s p r a t t 算法( 简称k m p 算法) 1 3 1 0k m p 算法利用已匹配成功 部分的信息，可以使模式串向前推进若干个字符，而不只是一个字符，避免了重 上海大学硕士学位论文 ! ! ! ! ! ! ! g ! ! ! ! ! ! ! ! ! 型! ! ! ! ! ! ! 韭! ! 型! ! ! 竺坐! 复比较，同时也实现了主串指针的无回溯；k m p 算法需要进行预处理计算一个 s h i f t 表，用来确定发生不匹配时需要跳跃的距离；k m p 算法搜索阶段在最坏的 情况下时间复杂度为o ( m n ) 。1 9 7 7 年，b o y e rr s 和m o o r ej s 设计了一个新的 串匹配算法b o y e r - m o o r e 算法( 简称b m 算法) 【1 4 】，该算法是目前最常用、效率 较高的算法之一。b m 算法的基本思想是先对模式串p 进行预处理，计算两个偏 移函数：b a d c h a r ( c h a rc h ) 和g o o d s u f f i x ( s t r i n gs t r ) ，然后将文本和模式串对齐， 从右往左进行匹配，当文本字符与模式字符不匹配时，根据函数b a d c h a r ( c h a rc h ) 和g o o d s u f f i x ( s t r i n gs t r ) 计算出偏移值，取两者中的较大者作为文本指针的右移 量。在b m 算法的基础上，又派生出许多算法，例如b o y e r - m o o r e h o r s p o o l 算法 1 5 1 ，该算法仅采用b a d c h a r ( c h a rc h ) 来确定右移值。1 9 8 0 年，k a r p 和r a b i n 合作 从截然不同于k m p 算法和b m 算法的途径研究出一种基于数值计算的新算法， 称为k a r p r a h i n 算澍”i ( 简称k r 算法) 。1 9 9 0 年，s u n d a yd m 提出了q u i c k s e a r c h 算法【1 7 ( 简称0 s 算法) ，该算法实质上是b m 算法的简化，在实际应用 中是一种简洁高效的算法。 多模式串匹配算法中一个经典算法是由a h oa v 和c o r a s i e km j 提出的 d f s a ( d e t e r m i n i s t i ef i n i t es t a t e a u t o m a t a ) 算法【1 8 】，又简称为a c 算法，该算法通 过构造有限自动机来进行匹配。构造有限自动机的过程就是将多模式匹配问题转 化为单模式匹配问题，因此，完全可以在有限自动机构造完毕之后应用现有的快 速单模式匹配算法来加快匹配速度。s u n w u 和u d i m a n b e r 近年在b m 算法的框 架下派生出又一经典的多模式匹配算法，称为w m 算法【1 9 】。 2 2 常用模式匹配算法 2 2 1b m 算法 b o y e r - m o o r e 算法【1 4 1 是一个著名的单模式匹配算法，以后绝大部分的入侵检 测模式匹配算法都是在它的基础之上发展而来的。该算法基本原理为：先对模式 串p 进行预处理，计算两个偏移函数：b a d e h a r ( e h a rc h ) 和g o o d s u f f i x 0 ；然后将 模式串和文本对齐，从右往左进行匹配；当文本字符与模式字符不匹配时，根据 函数b a d c h a r ( c h a rc h ) 和g o o d s u f f i x 0 计算偏移值，取两者中的较大者作为s h i f t 的值，将模式p 往右移s h i f t 个字符，继续由右向左进行匹配，匹配成功则予以 输出。 b m 算法分预处理和查找两个阶段，下面分别讨论。 1 预处理阶段 预处理阶段主要是计算b a d c h a r ( c h a rc h ) 和g o o d c u f f i x 0 两个偏移函数的值。 4 上海大学硕士学位论文 ! ! ! ! ! 坐! 塑! ! ! ! ! ! 型! ! ! ! ! ! ! g ! ! ! 望! 生! ! 坐： b a d c h a r ( c h a rc h ) 函数计算字符集中每个字符所对应的偏移量，如果某个字符在 模式p 中出现多次，则由最右边的那个位置来确定偏移量，如下表示： 对于中的每个字符x rm i n f i l l _ i 0 ，窗口向右跳跃s h i f t e h 并转第一步；否则，转第 三步。 第三步：计算当前匹配窗口前缀的散列值p r e f i x _ h a s h ； 第四步：对于h a s h l h 指向的列表中的每个指针，检查h a s h e h 指向的模式 串最左的b 个字符的哈希值是否等于p r e f i x _ h a s h ，如果相等，将该模式串与文本 做逐字比对，如果发现匹配则报告一次成功匹配；然后转到第五步； 第五步：将当前窗口向右跳跃一个字符，然后转第一步，直至扫描完全部文 本。 由于w m 算法采用字符块技术，极大的降低了部分匹配的可能性，增加了直 接跳跃的机会；使用前缀表进一步减少了进行逐字匹配的次数：采用散列技术降 低算法对内存的需求，使得算法获得了很高的实际运行效率。 2 3 协议分析技术简介 传统的模式匹配技术就是将收集到的信息与已知的攻击模式进行比对，从而 发现违背安全策略的行为。模式匹配技术是第一代和第二代入侵检测系统广泛使 用的网络数据包分析技术。但是单纯使用模式匹配的方法有很大的不足之处： 1 计算量大。对每个网络数据包，模式库中每条模式都要和数据包里面的 内容匹配一次，并且对数据包中的所有内容都需要进行匹配，但是很多匹配过程 都是不需要的。例如，若数据包的传输层协议是t c p ，那么对应于u d p 的模式 串就不需要和这个数据包进行匹配。 2 不能识别模式串的变形攻击。简单的模式匹配只能检测特定类型的攻击。 对攻击特征微小的变形都将使得检测失败。例如，对于w e b 服务器，g e t o 上海大学硕士学位论文 ! ! ! ! ! ! ! g ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! g ! ! ! 旦! 盐! ! 坐z c g i b i n p h f , g e t 0 0 c g i b i n p h f , g e t 6 3 6 7 6 9 2 d 6 2 6 9 6 e p h f 这些 攻击特征用模式串g e t c g i b i n l p h f 都不能检测出来。 传统模式匹配技术具有上述缺点的根本原因在于它把网络数据包看作无序 的、随意的字节流，没有考虑网络数据包的内部结构。网络通信协议是一个高度 格式化，具有明确含义和取值的数据流。 为解决模式匹配技术的这些缺点，在第三代入侵检测系统中提出了协议分析 2 1 1 技术。 协议分析技术利用网络协议的高度有序性，将输入数据包视为具有严格定义 的数据流，并将输入数据包按照各层协议报文封装的反向顺序，层层解析出来。 然后，再根据各层网络协议的定义，对各层协议的解析结果逐个进行分析。其中， 各层协议封装报文中都包含了预先定义的若干协议字段。协议分析技术的重点操 作内容就集中在检查当前数据包中的各层协议字段值是否符合网络协议定义的 期望值或处于合理范围之内。如果当前所检查的某个协议字段里，包含了非期望 的不合理赋值，则系统认为当前数据包为非法网络流量。由此可见，协议分析技 术利用预先定义好的关于协议字段的期望值或合理值的详细知识，来判断是否出 现了恶意的网络流量。 协议分析有效利用了网络协议的层次性和协议相关知识，能够快速判断攻击 特征是否存在。它的高效使得匹配的计算量大幅度减小。下面举例说明采用协议 分析技术对以太网数据包的分析过程，数据包内容为： 0 0 2 0d a d 3c 5 8 05 2 5 4a b 2 7c 0 0 40 8 0 04 5 0 0 0 0 3 40 7 b a4 0 0 0 4 0 0 6a o f 6c a 7 2a 5l8c a 7 25 8 1 60 4 0 b0 0 5 02 3 e 52 4 1 e5 0 b b 0 7 8 08 0 1 09 3 1 0b d o a0 0 0 00 1 0 10 8 0 a0 0 0 22 5 9 e0 1 a 3c 8 8 l 协议规范指出以太网络数据包中第1 3 字节处包含了两个字节的网络层协议 标识。基于协议分析的入侵检测系统利用这个知识开始第一步检测，跳过数据包 前面1 2 个字节，直接读取1 3 字节处的2 字节协议标识为0 x 0 8 0 0 。根据协议规 范可以判断这个网络数据包是p 包。如图2 - 2 所示。 o b 2 。曲3c 5 。：聪柏2 ，c 。舛由娟。3 4 。，融4 。 4 啦6 la o f 6c a 7 2a 5 1 8c a 7 25 8 1 60 4 0 b | 0 0 6 0 2 3 e 52 4 l e5 0 b b o t 湘8 0 1 09 3 1 0b d o a0 0 0 0o l o l0 8 0 ao q 0 22 5 9 e0 1 a 3c 8 8 1 图2 - 2 数据包分析 根据口协议规定，可以知道在数据包第2 4 字节处有一个l 字节的传输层协 议标识。因此系统跳过数据包15 到2 4 字节直接读取传输层协议标识为0 x 0 6 ， 上海大学硕士学位论文 ! ! ! ! ! ! ! g ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 竺g ! ! ! ! ! ! ：! ! 生z 这个数据包是t c p 协议。 再根据t c p 协议规定，可以知道在数据包第3 7 字节处有一个2 字节的应用 层协议标识，即端口号。于是系统跳过第2 5 到3 6 字节直接读取第3 5 字节的端 口号为0 x 0 0 5 0 ，即8 0 。该数据包是一个h 1 v r p 协议的数据包。 然后根据h t t p 协议规定，可以知道在数据包第5 5 字节是u r l 开始处，我 们要检测入侵特征“g e t c g i - b i n p h i ，因此仔细检测这个u r l 就可以了。 我们可以把协议分析算法用一颗协议树来表示，如图2 3 。 图2 - 3 协议树 由上面的分析过程可以看出：协议分析的分析过程就是一条从根节点到某个 叶节点的路径。每个叶节点是某一种攻击类型的分析机。在分析机中再采用模式 匹配的算法来检测攻击，因此大大减少了计算量，提高了算法的效率。 每个分析机的数据结构中包含以下信息：协议名称、协议代号以及该协议对 应的攻击检测函数。协议名称是该协议的唯一标志，协议代号是为了提高分析速 度用的编号。为了提高检测的精确度，可以在树中加入自定义的协议节点，以此 来细化分析数据。例如在h t t p 协议中可以把请求u r l 列入该树中作为一个节 点，再将u r l 中不同的方法作为子节点。 分析机的功能是分析某一特定协议的数据，得出是否具有攻击的可能性存 在。一般情况下，分析机尽可能地放到树结构的叶节点上或尽可能地靠近叶节点， 因为越靠近树根部分的分析机，调用的次数越多。过多的分析机聚集在根部附近 会严重影响系统的性能。叶节点上的协议类型划分得越细，分析机的效率越高田j 。 利用协议分析技术可以解决单纯采用模式匹配技术所产生的问题，大大减小 模式匹配的计算量，提高匹配的精确度，减少误报率；协议分析技术还可以解决 以下问题： 1 进行i p 碎片重组防止i p 碎片攻击。不同类型的网络链路层数据帧都有一个 上限，如果i p 层数据包的长度超过了这个上限就要分片处理，各自路由到达主机 以后要进行重组。因此黑客可以利用碎片重组算法进行攻击。比如：i p 数据包最 长为o x f f f f ，也就是6 5 5 3 5 字节，如果有意发送总长度超过6 5 5 3 5 的i p 碎片，一 1 2 上海大学硕士学位论文 ! ! ! ! ! 塑! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 塑! ! ! ! 坐盐里坐 些系统的内核在处理的时候就会出现问题，导致崩溃或者拒绝服务。 2 减低误报率。由于简单模式识别很难限定匹配的开始点和终结点，也就 不能准确地定位攻击串的位置，当某数据包的其他位置出现该字串时也会被认为 是攻击串，这就产生了误报现象。协议解析也大大降低了基于模式匹配的i d s 系 统中常见的误报现象。使用命令解析器可以确保一个特征串的实际意义被真正理 解，辨认出串是不是攻击串或可疑的。 2 4 协议分析技术的优势 传统的模式匹配技术的缺点就是计算量过大、消耗系统资源，而协议分析技 术利用网络数据包中协议的有序性克服了这些问题，具有检测快、准确、资源消 耗少的特点。 协议分析是新一代i d s 系统探测攻击手法的主要技术，它利用网络协议的高 度规则性快速探测攻击是否存在。协议分析技术的优势在于： i 性能好：协议分析利用已知结构的通信协议，与模式匹配系统中传统的 穷举分析方法相比，在处理数据帧时更迅速、有效。 2 准确性高：与非智能化的模式匹配相比，协议分析减少了虚警和误判的 可能性。 3 基于上下文的分析：当协议分析入侵检测系统引擎评估某个包时，它考 虑了在这之前相关的数据包内容，以及接下来可能出现的数据包。与此相反，模 式匹配入侵检测系统孤立地考察每个数据包。 4 反规避能力强：因为协议分析入侵检测系统具有判别通信行为真实意图 的能力，它较少地受到黑客所用的像u r l 编码、干扰信息、t c p i p 分片等入侵 检测系统规避技术的影响。 5 系统资源开销小：基于协议分析技术的入侵检测系统的资源开销较小， 而模式匹配技术的系统资源消耗很大。 2 5 小结 本章首先概述了模式匹配算法的发展历程，然后对常用的单模式匹配算法 b m 算法和多模式匹配算法a c 算法、w m 算法进行了详细的描述，并在理论上 分析了它们的性能，为进一步的研究工作提供了理论指导。最后介绍协议分析技 术，用来弥补模式匹配技术的不足之处。 上海大学硕士学位论文 ! 皇! ! ! ! ! g ! ! 皇! ! ! ! ! ! ! ! ! ! 竺! 兰垫! 里墨皇! ! 型! ! ：! ! ! ! ! ! 第三章高效模式匹配算法的设计 随着模式匹配技术的发展，许多优秀的模式匹配算法被广泛应用于入侵检测 领域，如s n o r t 2 0 【2 3 】中就采用了b m 、a c 和w m 三种完全不同的模式匹配算法。 模式匹配在网络入侵检测中有着非常重要的影响，这主要是由于模式匹配技术的 检测过程简单和对已知入侵行为的高检测率，a n t o n a t o s 2 4 研究表明入侵检测系 统中3 0 的处理时间都在进行模式匹配。 由于网络速度的快速提升，入侵检测系统的处理速度跟不上导致了入侵事件 的漏报。提高入侵检测系统的检测速度是目前急需解决的关键问题。改进入侵检 测系统中采用的模式匹配算法的性能是解决该问题的一种有效途径 2 ” 2 6 1 。因此， 研究新的检测思想和快速匹配算法具有重要意义。本章首先通过实验对b m 、a c 和w m 算法进行性能对比分析，在此基础上设计出新的模式匹配算法，并通过 实验验证其优异性。 3 1 洲、a c 和删算法性能对比实验 在单模式匹配算法中b m 算法是性能很好、应用最广泛的一种算法，在多模 式匹配算法中a c 算法是最经典的，而w m 算法采用与a c 算法不同的原理，也 具有很好的性能。本节通过实验对b m 算法、a c 算法和w m 算法的性能进行对 比分析，指出每种算法的最佳适用场合，为进一步的算法设计和算法选择提供指 导。 实验环境：c p u 为i n t e lc c l c r o n1 7 0 g h z ，内存2 5 6m ，操作系统为w i n d o w $ x pp r o f e s s i o n a l ，算法实现环境是v i s u a lc + + 6 0 。 3 1 1 实验 测试文本为由5 0 0 0 个英文单词和常见的标点符号随机生成的文本文件，大 小为2 6 1 7 0 k b ；模式串从文本中随机抽取，模式串长度分别为2 、4 、6 、8 、1 2 、1 6 、2 0 、3 0 、5 0 、1 0 0 。为保证算法实现的正确性，采用s n o r t 2 0 中的b m 实 现算法计算每个模式串在文本中的出现次数，作为标准查找结果。然后，对上面 三种算法也分别计算每个模式串的出现次数，与标准查找结果进行对照，由此判 定每个算法是否正确实现。 本实验主要测试这三种算法在模式串长度分别为2 、4 、6 、8 、1 2 、1 6 、2 0 、 3 0 、5 0 、1 0 0 ，模式串个数分别为5 、1 0 、2 0 、5 0 、i 0 0 、5 0 0 、1 0 0 0 时的时间消 1 4 上海大学硕士学位论文 翌! ! ! ! ! ：! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 竺! ! ! ! ! ! ! ! ! 坐! 耗和内存消耗情况。 图3 1 至图3 7 为各算法的查找时间对比，表3 - 1 为各算法的内存占用情况。 图3 - 1 时间对比图一模式串个数为5 图3 2 时间对比图一模式串个数为1 0 图3 - 3 时间对比图一模式串个数为2 0 1 5 上海大学硕士学位 仑文 图3 - 4 时间对比图一模式串个数为5 0 图3 - 5 时间对比图一模式串个数为1 0 0 图3 - 6 时间对比图一模式串个数为5 0 0 6 上海大学硕士学位论文 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 型! ! ! ! ! ! ! g ! ! ! 旦! ! ：! ! 坐! 图3 7 时间对比图一模式串个数为1 0 0 0 表3 - 1 b m 、a c 和w m 算法的内存消耗量( k b ) 、模式长度 模式个沁 282 05 01 0 0 b m 2 9 7 4 52 9 7 4 5 2 9 7 4 62 9 7 4 7 2 9 7 4 9 5 a c2 9 8 5 02 9 8 5 82 9 8 7 02 9 8 9 82 9 9 5 0 w m2 9 9 4 02 9 9 4 02 9 9 4 l2 9 9 4 22 9 9 4 4 b m 2 9 7 4 52 9 7 4 8 2 9 7 5 22 9 7 6 0 2 9 7 7 5 5 0a c3 0 0 4 83 0 1 9 63 0 2 4 83 0 5 0 93 1 0 2 9 w m 2 9 9 4 2 2 9 9 4 42 9 9 5 02 9 9 5 62 9 9 6 9 b m 2 9 7 4 62 9 7 5 0 2 9 7 5 92 9 7 7 72 9 8 0 5 1 0 0 a c3 0 2 6 93 0 4 2 93 0 6 5 03 1 2 1 03 2 2 6 9 w m2 9 9 4 22 9 9 4 82 9 9 5 22 9 9 7 l2 9 9 9 3 b m2 9 7 5 12 9 7 7 02 9 8 0 42 9 8 5 52 9 9 1 0 5 0 0a c3 2 0 2 93 2 8 1 0 3 4 0 1 0 3 6 8 2 94 2 0 2 8 w m2 9 9 5 12 9 9 6 22 9 9 7 42 9 9 8 23 0 0 1 2 b m 2 9 7 5 82 9 7 7 0 2 9 8 6 02 9 9 1 52 9 9 6 2 1 0 0 0a c3 4 2 2 93 5 8 2 93 8 2 1 04 3 5 0 96 5 4 9 7 w m2 9 9 5 42 9 9 6 82 9 9 8 63 0 0 2 53 0 1 2 1 表3 - 1 中数据说明：表中内存空间数据包括2 6 1 7 0 k b 的空间用来存放测试文 本，还有一部分为算法辅助空间。 1 7 上海大学硕士学位论文 ! ! ! ! ! ! ! g ! ! 璺竺! 生! ! ! ! ! ! ! ! 兰! ! 竺星! ! ! 型! ! ! ! ! ! ! 1 3 1 2 实验结果分析 从图3 1 至图3 4 ，我们可以发现，单模式匹配算法b m 的时间消耗同模式 串个数成正比，而a c 算法随模式串个数的增加，时间消耗变化的幅度较小， w m 算法介于b m 算法和a c 算法之间。这是由于b m 算法对每个模式串都要在 文本串中搜索一遍，故匹配时间随模式串个数增多而成比例增长；而a c 和w m 算法对于所有模式串而言，只需遍历一次文本串即可。因此在图3 5 至图3 7 中 不再绘制b m 算法的时间消耗曲线，其消耗的时间可以估算出来。由此我们可以 看出，在模式串个数较多时，不宜采用b m 算法。 图3 一l 至图3 4 表明b m 算法的消耗时间随模式串长度的增大而递减。这体 现出b m 算法采用了跳跃的思想，当发生不匹配时，模式串向右跳跃的距离和模 式串的长度息息相关。大多数情况下，匹配失败的字符在模式串中没有出现时， 模式串可向右移动的安全距离是模式串长度的函数，最大可为模式串的长度，因 此，模式串长度越大，b m 算法的性能越好。 图3 1 至图3 7 表明模式串长度对a c 算法的性能影响不大，因为a c 算法 的时间复杂度为o ( i n + n ) ，其中m 为文本串的长度，n 为模式串的总长度，而i i 远小于m ，故模式串的长度对其影响极小；和b m 算法一样，w m 算法在匹配 失败时也产生跳跃，因此对模式串的长度也很敏感。w i v l 算法在模式串长度小于 某个值时，其性能不如a c 算法，而大于这个值时，其性能好于a c 算法，且该 值随模式串个数的增多而增大，如图3 - 1 到3 7 所示，该值分别为3 、4 、4 、5 、 5 、7 、9 。另外，在模式串较短时，模式串个数越多，w m 算法性能同a c 算法 的差距越大。 从表3 1 中我们可以看到，a c 算法的内存消耗很大，而且随模式串个数增 多而迅速增大，在模式串个数超过一定的值时将耗尽内存空间；而b m 算法和 w m 算法仅占用很少的内存空间。如我们可以算算对5 0 0 0 0 个模式串采用a c 算 法进行匹配所需要的内存空间：假设每个模式串的最大长度为4 0 个字节，最坏 情况下a c 自动机需要5 0 0 0 0 * 4 0 个状态节点，每个节点有2 5 6 个指向孩子节点 的指针，一个节点至少需要5 1 2 字节，因此a c 自动机树的空间需求为 5 0 0 0 0 * 4 0 * 5 1 2 b y t e = 9 7 6 m b 。在选择匹配算法时应综合考虑匹配的时间消耗和空 间消耗。 综上所述，b m 算法可以用于模式串长度较大、模式串集合较小( 1 0 个左右) 的应用环境中，若模式串集合较大( 大于1 0 ) ，根据模式串的长度和模式串集合 的大小确定一个值来选择多模式匹配算法，模式串长度大于该值时用w m 算法， 否则用a c 算法。 本文在深入研究b m 算法和w m 算法的基础上，结合该实验结果，对这两 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s iso fs h r n g h a iu n i v e r s i t y 种算法进行改进，设计出新的模式匹配算法。 3 2b m 改进算法 在实际应用中，b m h 算法比b m 算法容易构造，且匹配效率也要高一些， 因此我们在改进b m 算法时，只考虑b a d c h a r ( c h a rc h ) i 垂l 数，不考虑已匹配的文 本信息。 3 2 1 算法描述 为描述方便，我们采用2 1 节中的标记符号。 b m 算法在处理过程中以一个字符为处理单元，当文本中一个字符t i 和模式 串中一个字符p j 不匹配时，由t j 在模式串中出现的位置来确定模式串的移动量。 假设字