（计算机应用技术专业论文）模式匹配型入侵检测系统改进.pdf

摘要 摘要 入侵检测技术是在传统的安全策略无法满足日益苛刻的安全需求的情 形下产生的，它的出现给计算机安全领域的研究带来新的活力。在入侵检 测技术中，对网络数据包有效载荷进行攻击检测的速度已经成为最制约网 络入侵检测系统效率的瓶颈。因此，在检测过程中，如何找到一种快速有 效的模式匹配方法是当前网络入侵检测系统面临的一个重要闷题。同时， 入侵检测系统检测过程就是将数据包负载与规则库中的规则进行匹配，因 此规则库的结构对检测效率也有很大的影响。 本文首先阐述了几种经典的模式匹配算法，对它们的适用范围和优缺 点进行了分析。在此基础上，另外提出了一种更为优越的字符串搜索算法 ( n e w - s e a r c h ) ，该算法充分利用每一次匹配比较的信息以跳过尽可能多的字 符进行下次比较。 其次，本文对规则库结构进行了改进。一方面通过优化规则的分类标 准，使得每条规则唯一地从属于一个规则链表；另一方面考虑到应用服务 使用频率的差异性，将常用的服务端口放在规则链表的前面。 本文利用轻量级网络入侵检测系统s n o r t 在l i n u x 操作系统下进行了一 系列实验，重点测试了本文提出的字符串匹配算法和改进的规则库的性能。 改进后的入侵检测系统仍然存在一些问题和不足，本文在最后给出了今后 的研究方向和内容。 关键词入侵检测；模式匹配；规则库；s n o r t ；l i n u x 燕山大学工学硕士学位论文 a b s t r a c t t h et e c h n o l o g yo fi n t r u s i o nd e t e c t i o ni sp r e s e n t e du n d e rt h es i t u a t i o nt h a t t r a d i t i o n a ls e c u r i t yi si n c a p a b l eo f s a t i s f y i n ge v e ri n c r e a s i n g l yr i g o r o u sd e m a n d i t se m e r g e n c eb r i n 塔sn e wv i t a l i t yt ot h er e s e a r c ho fc o m p u t e rs e c u r i t y i nt h e t e c h n o l o g yo fi n t r u s i o nd e t e c t i o n , t h es p e e do fa t t a c kd e t e c t i o ni st h el i m i tf o r e f f e c t i v eb a do fn e t w o r kp a c k e t s t h e r e f o r e ，i nt h ed e t e c t i o np r o c e s s ，i ti s s i g n i f i c a n tf o rt h en i d st of i n dap a t t e mm a t c hm e t h o do fs p e e da n de f f e c t a t t h es a l n et i m e ，t h ed e t e c t i o np r o c e s so fm i s u s e b a s e di n t r u s i o nd e t e c t i o ns y s t e m i st om a t c ht h ep a c k e t1 0 a da g a i n s tt h er u l e si nt h em l el i b r a r y , s ot h es t r u c t u r eo f t h er u l el i b r a r yh a sg r e a te f f e c to nd e t e c t i o ne f f i c i e n c y f i r s t l y , t h ep a p e re x p a t i a t e so ns o m ec l a s s i c a lm a t c h i n ga l g o r i t h m s ，a n d a n a l y s e st h e i ra p p l y i n gr a n g e s , a d v a n t a g e sa n dd i s a d v a n t a g e s o nt h eb a s eo f t h i s ，af a s t e rs t r i n gs e a r c h i n ga l g o r i t h m f n e w - s e a r c h ) i sp u tf o r w a r d t h i s a l g o r “h mm a k e sf u l lu s eo ft h ei n f o r m a t i o no fe v e r ym a t c h i n gc o m p a r i s o nt o s k i pm o r ec h a r a c t e r sb e f o r et h en e x tc o m p a r i s o n s e c o n d l y , t h ep a p e ri m p r o v e st h es t r u c t u r eo fr u l el i b r a r y t h r o u g h o p t i m i z i n gt h ec r i t e r i o no fc l a s s i f y i n gr u l e s ，e a c hr u l eb e l o n g st oo i l l yo n er u l e c h a i n o nt h eo t h e rh a n d ，c o n s i d e r i n gt h ed i f f e r e n c eo fu s e f r e q u e n c yo f s e r v i c e s ，c o m l u o ns e r v i c e sp o n sa r ed i s p l a y e di nt h ef r o n to f r u l ec h a i n s t h e p a p e rc o n d u c t sa n u m b e ro f p e r f o r m a n c et e s t sw i t hs n o r tu n d e rl i n u x o p e r a t i n gs y s t e m , a n dt h ee m p h a s i si s t ot e s tt h ep e r f o r m a n c e so ft h e e x c l u s i o n - b a s e dm a t c h i n ga l g o r i t h ma n di m p r o v e dr u l el i b r a r y f o ri n t r u s i o n d e t e c t i o ns y s t e ma f t e ri m p r o v e m e n t ，t h e r ea r es t i l ls o m es h o r t a g e s ，s ot h ep a p e r p r o v i d e st h ef u t u r ew o r kf i n a l l y k e y w o r d si n t r u s i o nd e t e c t i o n ；p a t t e r nm a t c h i n g ；r u l el i b r a r y ；s n o r t ；l i n u x 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文模式匹配型入侵检测系 统改进，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研 究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已 发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体， 均己在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签字日期：) 卯年眵月三瑁 燕山大学硕士学位论文使用授权书 模式匹配型入侵检测系统改进系本人在燕山大学攻读硕士学位期 间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有， 本人如需发表将署名燕山大学为第一完成单位及相关人员。本人完全了解 燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送 交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山大学， 可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部 分内容。 本学位论文属于 保密口，在年解密后适用本授权书。 日期：枷? 年。阴疗日 新勰馐钢 吼蝴：泊 第1 章绪论 1 1 研究背景 第1 章绪论 计算机网络技术的普及，给人类社会的方方面面都带来了极其深远的 影响，极大地丰富了人们的日常生活。根据中国互联网信息中一c , ( c n n i c ， c h i n a i n t e r n e t n e t w o r k i n f o r m a t i o n c e n t e r ) 发布的“第十六次中国互联网络发 展状况统计报告”显示：截止到今年6 月3 0 号，我国上网用户总数为1 0 3 亿人，比去年同期增长1 8 4 ；上网计算机达到45 6 0 万台，比去年同期增 长了2 5 6 ；c n ( c h i n a ) 下注册的域名数和网站数分别达到6 2 2 万和6 7 7 万，其中域名数比半年前增长了1 9 万个【”。 但是任何事物都具有两面性：一方面网络在给人类社会的发展创造广 阔天地，另一方面也为作恶者提供了一个更加便利的场所。据美国联邦调 查局( f b i ，f e d e r a lb u r e a uo f i n v e s t i g a t i o n ) 的调查，美国每年因为网络安全造 成的经济损失超过1 7 0 亿美元，在全球范围内每隔数秒就发生一起网络攻 击事件。据统计 2 】：信息窃贼在过去5 年中，以2 5 0 的速度增长，9 9 的 大公司都曾发生过大的入侵事件。世界著名的商业网站，如y a h o o 、b a y 、 加m z o n 等都曾被黑客入侵，造成巨大的经济损失，甚至连专门从事网络安 全的网站都曾遭到过黑客的攻击。 事实上，安全问题是从现代计算机系统诞生起就一直存在的，即使对 计算机和网络系统配备各类安全防护措施，仍然无法避免网络入侵事件的 发生。网络的安全问题主要表现在以下几个方面： ( 1 ) 目前通用的计算机系统都基于冯诺伊曼结构，这种结构的突出特点 在于程序和数据在计算机中的表示不再有任何区别，程序可以动态地被修 改和复制，甚至自毁口川。在这种结构下，具有自我繁殖能力、并能够修改 或删除其他程序的病毒及木马程序是计算机本身所允许的，因此对于此类 新型恶意代码的检测具有较大的难度【5 。】； 燕山大学工学硕士学位论文 ( 2 ) 运行于计算机之上的各类操作系统、网络协议以及应用系统都不可 避免地存在不足。造成这些不足的原因有多方面，如系统设计存在漏洞， 程序编写存在错误，软件系统中设置有程序调试跟踪点( 即后门) 等这些与人 相关的问题，虽然能够通过严格编程方法、应用更好的软件工程思想等手 段加以克服，但是不可能得到完全解决1 ； ( 3 ) 程序的行为具有其不可判定性。由于图灵机的停止问题是不可证的， 不存在任何程序可以证明另一个正在运行的程序可以结束。在网络环境中， 攻击者往往采用不重复的攻击手段，任何防护措施都不可以完全保证能够 及时、正确地发现并阻止其攻击行为【1 2 q 5 】； ( 4 ) 计算机系统不是静态的，系统中的程序可以添加或删除，系统配置 需要根据情况随时修改，根据安全策略应用到网络环境中的各种安全防护 工具( 如防火墙、加密、访问控制和日志审计等) 更需因网络状态的不同进行 动态调整。由于对这样一个动态系统进行形式验证( f o r m a lv e r i f i c a t i o n ) 是相 当耗时且难以正确完成的，因此网络安全策略、系统实现和系统配置的实 施缺乏必要的理论支持【m 1 8 1 。 根据网络入侵的手段，可将网络攻击大致分为三种类型1 1 9 】： ( 1 ) 探测攻击( r e c o n n a i s s a n c ea t t a c k s ) 指对网络系统、服务或其脆弱性 进行未授权的测试，通常此类攻击是其他攻击的前奏 2 0 , 2 1 1 。 ( 2 ) 探访问攻击( a c c e s sa t t a c k s ) 包括任何对未授权数据所进行的读写 操作、对未授权系统进行的访问，以及未授权的权限提升口2 埘】。 ( 3 ) 拒绝服务攻击( d e n i a lo f s e r v i c ea t a c k s ) 指攻击行为破坏网络、系统 或服务，使系统瘫痪、运行速度减慢，或仅破坏一个特定的应用，导致合 法用户不能得到正常的服务 2 5 - 2 8 】。 为了迅速、有效地发现各类入侵行为，保证系统和网络资源的安全， 很多组织和研究机构正致力于提出各种安全防护策略和方案，包括防火墙、 入侵检测、防病毒、访问控制等 2 9 1 。每一种防护措施都各有其应用范围和 特点，而入侵检测系统则是整个安全防护体系中不可缺少的重要组成部分。 入侵检测系统( i n t r u s i o nd e t e c t i o ns y s t e m ，简称i d s ) 的定义是：监视并 分析计算机系统和网络中传递的信息，从中发现来自网络外部的攻击行为 2 第1 章绪论 和网络内部的违规行为口。 入侵检测系统解决安全问题的方法是基于如下假设的：系统是不安全 的，但违反安全策略的行为( 即入侵) 是能够通过监控和分析系统及用户行为 而被检测到的，因此i d s 最主要的功能是检测并报告异常行为，实时发现 入侵埘】，主要包括： ( 1 1 监视、分析用户及系统活动； f 2 ) 检查系统配置及存在的漏洞； ( 3 ) 评估系统关键资源和数据文件的完整性； ( 4 ) 识别己知的攻击行为； ( 5 ) 统计分析异常行为； ( 6 ) 管理操作系统的日志，并识别违反用户安全策略的行为。 根据审计数据的来源，可以将i d s 分为两类，即基于网络的 i d s ( n e t w o r k - b a s e di d s ，简称n i d s ) 和基于主机的i d s ( h o s t - b a s e di d s ，简 称h i d s ) 。基于网络的入侵检测系统安装在被保护的网段中，分析网段中 所有的数据包，根据己知的攻击模式判断是否存在攻击；基于主机的入侵 检测系统则通常安装在被重点监测的主机中，对该主机的网络实时连接以 及系统审计日志进行分析和判蝌3 4 】。 由于现有的网络信息多是基于t c p f i p 协议的，数据格式相对标准化， 因此以网络数据包为信息来源的n i d s 能够对网络数据包的检测内容准确 定义，且实施简便，具有较高的检测准确率。与n i d s 相比，n i d s 得到了 更为广泛的应用。 在目前实际投入运行的n i d s 产品中，既有商用产品，同时也有多个开 放源代码软件( 如s n o r t ，b r o ，s h a d o w 等) ，这些自由软件为入侵检测系统的 研究和应用提供了非常宝贵的资源。目前，s n o r t 系统( h t t p ：w w w s n o r t o r g ) 是最为活跃的，并有多个其他机构跟踪最新网络安全信息为其提供用于检 测的规则库，如w w w c v e m i t r e o r g 的c v f 4 c o m m o nv u l n e r a b i l i t i e sa n d e x p o s u r e s ) ，w w w , w h i t e h a t s c o l n 的a r a c h n i d s ( a d v a n c e dr e f e r e n c ea r c h i v e o f c u r r e n th e u r i s t i c sf o rn e t w o r ki n t r u s i o nd e t e c t i o ns y s t e m s ) 等，其入侵特征 更新速度和研发的进展已超过了大部分同类产品( 3 5 】。 燕山大学工学硕士学位论文 1 2 研究现状 入侵检测技术的发展已有很长的历史，并且很早就在实际中取得了成 功的应用。在国外，入侵检测技术的发展如同病毒检测技术一样，许多检 测手段都已变得很成熟。国内近些年来，网络技术飞速发展，但网络安全 的问题却没有得到足够的重视。相对于美国等国家，入侵检测技术在国内 才刚刚起步，虽然出现了“天阗”、“天眼”、“冰之眼”等网络入侵检测系 统，但是研究还不够。 1 2 1入侵检测系统的不足 1 2 1 1入侵检测系统间的协同问题近年来，入侵技术无论是从规模上 还是从方法上都发生了很大的变化，主要表现在入侵的综合化和复杂化、 入侵主体对象的间接化、入侵规则的扩大化、攻击对象的转移、入侵技术 的分布化等等。丽传统的入侵检测技术一般针对某一主机类型或网络结构， 不同的入侵检测系统间缺乏协同工作能力。日益复杂的网络系统结构，广 泛采用的分布式应用环境，海量存储和高带宽的传输技术，都使得集中式 的入侵检测越来越不能满足系统需求。 1 2 ，1 2检测加密数据的攻击问题目前大多数入侵检测系统都是基于网 络的入侵检测系统。但是基于网络的入侵检测系统不能处理加密后的数据， 如果数据在传输中被加密，即使只是简单的替换，基于网络的入侵检测系 统也难以处理【3 6 。例如采用s s h 、h t t p s 、带密码的压缩文件等手段，都 可以有效地防止网络入侵检测系统的检测。此外，对于虚拟专用网( v p n ， v i r t u a lp r i v a t en e t w o r k ) ，入侵检测系统也显得力不从心。 1 2 1 3 漏报率和误报率的问题评价一个入侵检测系统最常用的指标是 误报率和漏报率。正确地检测入侵，减少误报是入侵检测正确性的问题； 最大限度地检测入侵，防止漏报是入侵检测的完备性问题。具有良好的正 确性与较大完备性始终是入侵检测技术的追求目标。虽然误用检测准确率 高，但是却不能检测未知攻击，并且规则库需要定期更新，维护工作量大： 异常检测能够检测未知攻击，但是漏报率高。 4 第1 章绪论 1 2 2 入侵检测系统的主要瓶颈 1 2 2 1 抓包速率许多的入侵检侧系统如s n o r t 等都是通过l i b p c a p 来实 现从网络获取原始的数据流的。l i b p c a p 是一个良好的抓包工具，但在高速 网络上，它本身也成为了一个瓶颈。高速的网络需要更加先进的抓包体系 和更高速的包处理方式。 1 2 2 2 不够先进的数据结构s n o r t 中定义了很多的数据结构来处理 l i b p c a p 抓过来的数据报。由于s n o r t 在开发历史己经较长，许多原来定义 的数据结构不能满足当前高速网络数据处理的需要，因此需要进行改进。 1 2 2 3 字符串匹配算法特征字符串的匹配是检测过程中最费时的部分， 匹配算法的性能直接影响到整个入侵检测系统的效率，是当前入侵检测的 一个主要瓶颈。 1 2 2 4 校验验证为了保证数据报的完楚性，s n o r t 需要对每一个数据报 的协议校验和都要重新计算一遍，以验证是否和当前数据报的校验和字段 一致，但这是一件很花费的工作，因此也成为了入侵检测系统的瓶颈之一。 1 2 _ 3 模式匹配算法 字符串匹配是字符串的一个基本运算，在文本编辑、文献检索、核苷 酸与氨基酸的匹配，以及图像处理技术中，都常常遇到这类问题。近年 来对于一维字符串的匹配问题研究较多。1 9 7 0 年，s a c o o k 从理论上证明 了一维模式匹配问题可以在o + n ) 时间内解决，为串匹配算法的进一步发 展奠定了坚实的理论基础，其中甩，m 分别为正文和模式的长度p 8 】；1 9 7 7 年， d o n a l de k n u t h h - 与j a m e sh m o r r i s 和v a u g h a nr p r a t t 仿照c o o k 的证明构造 y k m p 算法【3 9 l ；r s b o y e r 和j s m o o r e 设计t b m 算法【4 0 】；同时，k a r p 和r a b i n 给出了r k 算法】和随机算法 4 2 】；v i s h k i n 提出了决定性抽样算法 4 3 】，以上 五种算法都是精确的串匹配算法。 为了解决一维模式的近似匹配问题，b a s z a - y a t e s 和g o r m e t ，w u 和m a n b e r 提出了过滤算法，p e v z n e r 和w a t e r m a n t 采用多重过滤来加快运行速度。二维 模式匹配近几年也有较大的发展，k a r p 和r a b i n 利用“指纹函数”将一维精 燕山大学工学硕士学位论文 确匹配推广n - - 维。 在文献 3 9 , - - 4 3 五个精确串匹配算法中，k m p 算法的程序设计利用递归 函数来降低时间复杂度，其设计思想和预处理比较复杂且较难理解。而b m 算法和r k 算法虽然的设计思想较易理解，但它们的时间复杂度却为o ( m n ) ， 大大高于k m p 算法的时间复杂度0 ( 聊+ 胛) ，因此从理论上讲，b m 算法和r k 算法不是串匹配的最佳算法。v i s h k i n 提出的决定性抽样算法的时间复杂度 为o ( m + n l o g n ) ，黄占友等的k i v i p 改进算法【删只适用特殊的字符串，文献 4 5 】 给出了一种基于最长前缀的模式匹配算法，其时间复杂度为o ( m * n k ) ，赵一 谨给出了一个改进的b m 串匹配算法( n e w b m 算法) 【4 6 ，其基本思想是在模 式p 中找出一个最长的前缀子* s u b p ，使其末字符( 我们用p 后表示) 在s “b p 中 只出现一次，在模式匹配过程中仅当s b p 匹配成功才对模式p 余下的部分 e n d p = p s u b p 进行匹配，若e n d p 匹配不成功，则模式p 从正文中滑过长度 为m a x s u m , s u b p 的一个字段( e n d p 在第s u m 个字符时匹配失败) ，由于b m 算 法的匹配过程是从模式p 的右端开始向左逐个字符进行比较，文献 4 6 中提 出的改进算法在许多情况下可以比b m 算法有更高的效率。但在最坏情况下 n e w b m 算法的复杂度仍为o 沏功，并且文献 4 6 】设计的求s b p 子串的算法 却不能对任意的模式实现其基本思想下的分解。 1 2 4 检测分析技术 1 9 9 5 年k u m a r 提出了入侵信号( i n t r u s i o ns i g n a t u r e ) 的层次性概念。依 据底层的审计事件，可以从中提出高层的事件( 或者活动) ；由高层的事件构 成入侵信号，并依照高层事件之间的结构关系，划分入侵信号的抽象层次 并对其进行分类。如果对构成信号的事件按照底层的审计事件进行精确的 定义，就可以从抽象的层次实例化中得到具体的层次结构。实例化的层次 结构意味着对于层次结构中的每一层而言，都可以对该层次中匹配信号的 复杂性边界进行划分【4 ”。 其次，k u m a r 把入侵信号分成四个层次，每一层对应相应的匹配模式。 ( 1 ) 存在( e x i s t e n c e ) 这种入侵信号表示只要存在这样一种审计事件就 足以说明发生了入侵行为或入侵企图，它所对应的匹配模式称为存在模式 6 第1 章绪论 ( e x i g e n c ep a t t e r n ) 。存在模式可以理解为在一个固定的时间对系统的某些状 态进行检查，并对系统的状态进行判定。这种状态检查可以是查询特殊文 件的特殊权限、查找某个特定文件是否存在、文件内容格式是否符合规则 等，通过这种检查来寻找入侵者留下的蛛丝马迹。 ( 2 ) 序y 0 ( s e q u e n e e ) 有些入侵是由一些按照一定顺序发生的行为所组 成的，它具体可以表现为一组事件序列。其对应的匹配模式就是序列模式 ( s e q u e n c ep a t t e r n ) ，这种入侵的审计事件可以表示为在图形中某个方向上的 一串连续的峰值。在序列模式中，事件的过程时间是由在这个流里面已经 发生过的事件所决定的。 ( 3 ) 规则表示( r e g u l a re x p r e s s i o n s ) 规则表示模式( r e g u l a re x p r e s s i o n s p a t t e m s ) 是指用一种扩展的规则表达式方式构造匹配模式，规则表达式是由 用a n d 逻辑表达式连接一些描述事件的原语构成的。适用这种模式的攻击 信号通常由一些相关的活动所组成，而这些活动间没有什么事件顺序的关 系。 ( 4 ) 其他其他模式( o t h e r sp a t t e r n ) 是指一些不能用前面的方法进行表 示的攻击。 模式匹配是人侵检测系统所使用的基于攻击特征的网络数据包分析技 术。它具有分析速度快、误报率小等优点是其它分析方法不可比拟的。但 单纯使用模式匹配的方法有很大弊端，其根本问题是它把网络数据包看作 是无序随意的字节流。网络通信协议是一个高度格式化的、具有明确含义 和取值的数据流，如果能将合理的规则库结构和模式匹配方法结合起来， 则可以获得更好的效率、更精确的结果。 1 3 本文研究的主要内容及结构 入侵技术的发展与进化以及网络带宽的不断增加，对入侵检测系统提 出了新的挑战。本文研究的主要内容是以降低模式匹配型入侵检测系统的 误报率、漏报率，提高检测效率为目的，提出了两种改进方案。首先提出 了提出了一种更为优越的字符串搜索算法，该算法充分利用每一次匹配比 较的信息以跳过尽可能多的字符进行下次比较，具有更大的平均搜索步长、 7 燕山大学工学硕士学位论文 更少的匹配比较次数和更快的速度，因而提高了检测的效率；其次，通过 优化特征规则的分类标准和规则链表的结构，从而对规则库的结构进行了 改进，减少了内存占有量和检测时间。 本文章节安排如下： 第1 章主要分析了计算机网络系统的安全性，叙述了本文的研究背景， 包括网络安全现状分析，入侵检测系统，基于网络的入侵检测以及和s n o r t 的相互关系及研究现状，包括入侵检测系统的不足，入侵检测系统的主要 瓶颈，模式匹配算法和检测分析技术，并指出本文的主要内容和结构。 第2 章首先分析了几种经典的模式匹配算法的思想、适用范围和各自 的优缺点以及适用于s n o n 的匹配算法，然后重点描述了本文所提出的新模 式匹配算法，包括算法的思想、实现和性能分析。 第3 章首先介绍了s n o r t 的规则集、规则选项、规则链表、原来的规则 划分标准、快速规则匹配引擎的构造原理以及涉及到的主要数据结构，然 后介绍了s n o r t 快速检测的原理，最后重点介绍了规则划分标准和规则链表 结构的改进方案。 第4 章首先对轻量级网络入侵检测系统s n o n 进行了分析，包括它的特 点、功能、系统构架和工作原理。其次，介绍了实验平台的搭建，其中包 括实验环境、数据集的获取以及本文所提出的算法在s n o r t 中的实现；然后 介绍了算法性能测试实验，包括最佳元素大小的测试、不同数据集的测试 和不同大小规则集的测试；最后测试了改进后的规则库结构的合理性。 最后是全文总结和今后的研究方向。 第2 章入侵特征匹配算法的改进 第2 章入侵特征匹配算法的改进 字符串匹配是模式匹配中最简单的一个问题，它可用于数据处理、数 据压缩、文本编辑、信息检索、计算机科学等多种应用中，在以检测攻击 特征的规则选项内容的模式匹配型入侵检测系统等网络安全的应用中也发 挥着重要的作用。 基于网络的入侵检测可以分为数据包的捕获、数据包的预处理、对数 据包进行攻击检测以及检测结果输出的过程。对数据包的有效载荷进行攻 击检测是对攻击检测过程的重要组成部分，也是时间消耗最大过程之一。 数据包有效载荷攻击检测的主要任务是在数据包的有效载荷中查找出可以 代表发生攻击的字符串，以s n o r t 为例，也就是查找出由攻击特征的规则选 项c o n t e n t 或者选项u r i c o n t c n t 所标识的字符串，在第2 章有详细介绍。s n o r t 是一个跨平台、轻量级的网络入侵检测软件，将在第4 章有详细介绍。特 征模式匹配是入侵检测系统所使用的基于攻击特征的网络数据包攻击检测 技术。模式匹配技术按照以下方式进行操作： ( i ) n 络上每一个数据包都被检测，寻找攻击特征； ( 2 ) 与攻击特征相同的一组字节从可疑数据包首部取出，并对两组字节 进行b b 较； ( 3 ) 女1 1 果两组字节一样，攻击特征即被检测出来； ( 4 ) 如果两组字节不一样，攻击特征“前移个字节”，重复比较流程； ( 5 ) 第二次检测时，特征与数据包中第二开始的字节进行比较； ( 6 ) 该流程被重复，每次的比较起始位置都增加一个字节，直到所有的 数据字节都与攻击特征比较。 模式匹配算法的种类很多，根据不同的划分依据可有不同的分类。根 据模式数目的不同，可将匹配算法划分为单模式匹配算法和多模式匹配算 法；根据匹配方式可以划分为精确匹配和模糊匹配等【4 8 1 。 本章在分析几种典型匹配算法的基础上。提出了一种更为优越的模式 9 燕山大学工学硕士学位论文 匹配算法。 2 1 模式匹配的分类 i d s 的模式匹配即通过数据包的分析，并匹配自身的规则库，如果事 件匹配就产生报警或者保留准备更多相关情况的分析，否则就抛弃( 即便是 属于攻击) 。 s n o r t 是一个开放源代码的轻量级的基于网络的入侵检测系统，它描 述系统入侵行为的方法简单、易于实现，并且畿够描述绝大多数的入侵行 为，因此本文它的描述方法。模式匹配包括字符串匹配、协议匹配、大小 匹配、累积匹配和逻辑匹配。 ( 1 ) 字符串匹配 目前大多数i d s 最主要的匹配方式，事件的定义者根 据某个攻击的数据包或者的原因，提取其中的数据包字符串特征。通常i d s 经过协议分析后，进行字符串的匹配。 ( 2 ) 协议匹配通过协议分析模块，讲数据包按照协议分析的结果对协 议相应的部分进行检测，比如，t c p 包的标志位，协议异常等。协议匹配 需要对特定的协议进行分析，s n o r t 对i p 厂r c p u d p i c m p 进行了分析，但 是没有对应用协议分析。高层的应用协议分析，可以显著的提高匹配的效 率，本系统就采用了基于高层协议分析的匹配技术。 ( 3 ) 大小匹配也叫长度匹配。多数情况下，这也应该属于字符串匹配 底一种。不过，这种匹配方式对数据包中某段数据的长度而不是具体的字 符串进行匹配。比如，通过数据长度限制来对缓冲区溢出攻击进行检测。 ( 4 ) 累积匹配也叫量匹配。通过对某些事件出现的量( 次数或者单位 时间次数) 来产生新的事件。比如，某个i p 在一分钟内报出了i 0 0 条c g i 事件，那么就属于一次c g i 扫描事件。 ( 5 ) 逻辑匹配或者是集合匹配。一些有更强事件检测能力的i d s ，通 过对不同类型的事件组合来进行判断，从而获得新的事件。少数i d s 对多 种事件的组合来构成逻辑推理增强检测的智能。 以上只是一种不很严格的分类，其中有部分是重叠的。 l o 第2 章入侵特征匹配算法的改进 2 2 现有模式匹配算法的研究 在对数据包的有效载荷进行攻击检测时，对数据包的载荷进行攻击检 测的过程从本质上讲就是一个字符串的模式匹配的过程。对数据包有效载 荷进行攻击检测的速度已经成为最制约网络入侵检测系统效率的瓶颈。所 以如何为数据包有效载荷攻击检测过程找到一种快速有效实用的模式匹配 方法是当前网络入侵检测系统面临的一个重要问题。 2 ，2 1k m p 算法 这种算法是d e k n u t h 与v r p r a t t 和j h m o r r i s 同时发现的，因此人们 称为k m p 算法。此算法可以在o ( h + 卅) 的时间数量级上完成串的模式匹配 操作。其基本思想是，假设在模式匹配过程中当前正执行到比较字符串t ，和 p j ( 1 i ，1 j m ) ： ( 1 ) f ，= p ，则继续往右作匹配查找，即检查t 。和p 。是否匹配? ( 2 ) f ，p ，则，考虑下列两种情况： 若j = l ，则执行t 。和p ，的匹配操作，这相当于把模式、正文向右移动 个字符后，再从头进行匹配检查。 若1 m 或i n m + l 为止。 k m p 算法的核心是构造n e x t 函数，如何选取和计算n e x t 函数，应满 足下述条件： ( 1 ) 字符子串a p 2 p 。】与子串p j - ( d p r ( 。【，一2 】) p j - i 相 匹配( 简记作p 1 n e x t , - 1 = p 1 - ( n e x t u 一1 ) 一乒l 】) 。这是因为我们要求以后的 匹配检查可由t 。和p 。l 门开始，下式必须成立： p 1 n e x t 【， 一1 = ，【f 一( n e x t i 一1 ) i - 1 】 燕山大学工学硕士学位论文 根据已知的匹配成果若要使得： p 沪( n e x t , 一1 ) 一j 乙1 = t i 一( n e x t f - 1 ) 乒l 】 则必须要有： p 1 n e x t j 一1 】= p 产( n e x t f - 1 ) 4 - 1 】 ( 2 ) n e x t 叩必须为满足条件( 1 ) 的最大值。这使得在模式向右滑劾一n e x t , 1 时不错过其中某个可能匹配成功的位置。 当1 j m 时，我们定义函数n e x t , 1 如下： n e x t j ，= 。焉羔箍0 鬟麓描嚣j 等怂饕 并约定n e x t 1 = o 时，它使得每当检查到f ，p ，以后就去执行f 。和p 1 的匹配检查。 现在考察函数n e x t 的性质： ( 1 ) 对于所有的j ( 1 j s m ) ，有1 n e x t j 】 ，n e x t 【， 仅与下标j 和模 式尸有关，而与正文丁无关： ( 2 ) 若1 n e x t f l 勺，则p 1 n e x t 啊一1 印d - ( n e x t f l 一1 ) 一乒1 】是模式p 中下 标，以前最大的真前缀和真后缀的匹配。 ( 3 ) 若n e x t 们= 1 ，则表示模式p 中没有真前缀和真后缀的匹配。 可以证明，求n e x t 函数的算法3 3 在最坏情形下时间复杂性为o ( 肌1 ， k m p 算法3 2 在最坏情形下时间复杂性为0 ( 聊+ m 。 2 2 2b m 算法 b o y e r 和m o o r e 两人在k m p 算法的启发下，提出了一种新的字符串快 速匹配算法b o y e r - m o o r e 串匹配算法( 简称b m 算法) 。 它的特点是考虑到在匹配比较过程中，不少的情形是前面的许多字符 都匹配而最后的若干字符不匹配，这是采用从左到右的方式扫描的话会浪 费很多时间。因此，改用从右到左的方式扫描模式和正文，这是一旦发现 正文中出现模式中没有的字符时就可以将模式、正文大幅度的“滑过”一 段距离。 该算法有下列显著特点： 1 2 第2 章入侵特征匹日a 算法的改进 f 1 ) 模式与文本的匹配从右向左进行考虑到在匹配比较过程中，不少 的情形是前面的许多字符都匹配而最后的若干字符不匹配，最终导致匹配 失败，这时采用从左向右的方式扫描模式串和文本会浪费很多时间。因此， b m 算法将p 与r 左对齐，即弓与正对齐。匹配从p 的最右端字符开始，判 断巴与瓦是否匹配，如果匹配成功，则向左移动，继续判断只一，与l 一，是 否匹配，循环继续下去，直到p 中的字符全部匹配成功或者是有不匹配的 字符出现。 ( 2 ) 坏字符移动b m 算法对模式进行预处理，得到一些启发式信息， 并使用这些信息来计算模式p 向右移动的距离，该移动函数是针对模式串 的某个位置的。坏字符启发式规则是当发生失配时，移动模式串使得失配 的文本字符与该字符在模式串中的最右出现对齐。移动函数如下： b a d c h 一耄嚣蓍黧龇吲圳( 2 - 1 ， ( 3 ) 好后缀移动该移动函数是针对模式中某个子串的。当匹配失败时， 如果已匹配子串长度不为0 ，就可以采用好后缀启发式规则，即移动模式串 使得已匹配部分与该部分在模式串中的最右端出现对齐。 ( 4 ) 取较大者作为模式移动的距离当模式与文本不匹配时，根据具体 情况采用坏字符或者好后缀移动函数来计算偏移值。有时同时满足两种启 发式规则，在这种情况下就选取两者中的较大者作为模式串右移的距离。 b m 算法先对模式p 进行预处理，计算两个偏移函数：b a d c h a rf 针对 某个字符) 和g o o d s u f f i x ( 针对某个子串) ，然后将文本和模式对齐，从右往 左进行匹配，当文本字符与模式字符不匹配时，根据函数b a d c h a r 和 g o o d s u f f l x 计算出的偏移值，取两者中的大者，将文本指针往右移，匹配 成功则予以输出。 其主要特征如下：最差情况下找到模式的所有出现的时间复杂度为 o ( m ”) ，找到第一次出现的时间复杂度为o ( 3 n ) ；最优情况下的时间复杂 度为o ( n m ) 。 因为在实际应用中，字典表中大部分字符根本不出现在模式串中，所 以应用b m 算法可以大大加快字符串匹配的速度。我们将b m 匹配算法的 燕山大学工学硕士学位论文 形式描述如下： 算法2 1 ： v o i db m _ s t r i n g _ m a c h t i n g ( c h a r + p c b u 虢r ，i n ti b u f s i z e ) i n t 功，m ； i _ 0 ；h 文本当前的匹配位置 j = 0 ；n 模式当前的匹配位置 w h i l e ( i 2 0 ) & & ( p c b u f f e r i + j 一- - p c p a t t e r n j ) ) 匹配 j = j - 1 ； i f ( j 0 ) i + = g o o d s u f f l x 0 ； ) e l s e i - i - 。m a x ( g o o d s u f f i x j ，j b a d c h a r p c b u f f e r j ) ； ) ) 2 2 3 b m h ( b o y e r - m o o r e h o r s p 0 0 1 ) 算法 b m h 算法是b m 算法的一个简化和改进。 h o r s p o o l 通过研究和证明发现：在文本串r 字符种类较少的情况下， b m 算法的坏字符规则效率不高，所以通过好后缀规则可以增加匹配速度， 提高匹配效率。但是在文本串r 字符种类较多的情况下。 例如t 中字符为a s c i i 的情况，坏字符规则效率明显提高，这时好后 1 4 第2 章入侵特征匹配算法的改进 缀规则的优越性表现得并不明显。1 9 8 0 年，h o r s p o o l 提出了一种b m 算法 的改进和简化算法，即b m h 算法，该算法只使用坏字符启发式规则，使得 预处理过程很简洁。 b m h 算法在最坏情况下找到模式所有出现的时间复杂度为o ( m n ) ，但 在一般情况下比b m 算法有更好的性能。 2 2 4 q s ( q u i c ks e a r c h ) 算法 o s 算法【5 明在对模式p 预处理过程中，只计算偏移函数b a d c h a r ，方法类 似于b m 算法中的坏字符启发式规则。但在查找查找方式上q s 算法在b m i - i 算法的基础上作了一定的改进。 其思想如下：假设当前文本指针为t ，模式串p 与r t ，t + m 一1 】对齐， 考虑到文本串字符与模式串字符匹配不成功时，文本指针至少要移动1 个位 置，那么在下一次匹配过程中，t t + 用1 是待处理的对象，因而在计算偏移 量时，可将t t + 聊】考虑进去，通过判断丁p + m 是否在模式中从而决定模 式串的移动量。对于模式中不出现的字符，其偏移量为m 十1 。 q s 算法的主要特征是：模式串的移动量大；在模式串较短的情况小更 为有效；最差情况下找到模式所有出现的时间复杂度为o ( m n ) 。 2 2 5 a c ( a h o c o r a s i c k l 算法 a c 算法是一个同时搜索多个模式的经典多模式匹配算法。所谓多模式 匹配算法就是把所有的模式串合并到一个数据结构中，通过对文本进行一 次扫描，找到所有模式的所有出现。 a c 算法使用了有限自动机的结构来接收所有的字符串。由于自动机是 结构化的，这样每个前缀都可用唯一的状态来标识，甚至是那些多个模式 串的共同前缀。当文本中下一个字符不是模式中预期的下一个字符中的一 个时，会有一条失败链指向一个状态，这个状态代表最长的模式前缀，同 时也是当前状态的相应后缀。 a c 算法在以下方面得到了改进： ( t ) n 时支持确定型和不确定型有限状态自动机； 燕山大学工学硕士学位论文 ( 2 ) 采用线性链表来初始化状态转移表；