（计算机软件与理论专业论文）一种基于高效模式匹配算法的入侵检测系统.pdf

摘要随着互联网的日益开放以及网络技术的飞速发展，网络应用的种类和重要性日益增加，网络攻击的行为也越来越严重，因此保障网络安全越来越具有挑战性。传统的各种静态安全防御体系，如防火墙、身份认证及数据加密技术已经不能完全适应当前的网络安全状况。于是，入侵检测技术应运而生，而基于模式匹配的入侵检测系统由于其检测的准确性高、误警率低且具有很强的实用性而越来越受到广泛的应用。本文主要研究的是种基于高效模式匹配算法的入侵检测系统。首先从网络安全的现状出发，讨论了网络安全的关键技术，从而引出了入侵检测系统。接着，介绍了入侵检测系统的发展历史、定义、系统结构以及常用的检测系统类型，并在此基础之上，提出了一种基于高效模式匹配算法的入侵检测系统。该系统的关键是模式匹配算法。本文首先介绍了几种典型的单模式匹配算法和多模式匹配算法，然后从运行时问和占用空间等方面考虑，经过分析，提出了一种高效的模式匹配算法( h p p m ) 。高效的模式匹配算法( 1 p p m ) 是建立在这样的思想基础之上，即：如果在数据包有效负载中发现了有最少见的四个连续的字母串是一个攻击模式的子串，那么就可以认为和该攻击模式串产生了匹配。在这种算法中，每一个模式都用四个最少出现的字符序列作为特征。通过实验证明，该算法可以大大地提高检测的效率。该系统除了有入侵检测系统中通用的数据收集模块、检测引擎模块和入侵响应模块外，还加入厂预处理模块、协议解析模块和管理配置模块，并且在检测引擎中，使用了不同于传统入侵检测系统的方法，在进行模式检测前，根据独特的规则参数对规则进行优化，使得系统在整体性能上有了较大的提高。本系统是一个开放的平台，所以其中的一些功能还有待于进一步地扩展。关键词：闻络安全；入侵检测；模式匹配：哈希函数；h p p m 算法a b s t r a c tw i t ht h er a p i dd e v e l o p m e n to ft h en e t w o r kt e c h n 0 1 0 9 ya n d 廿1 ec o n i i n u a lo p e n i n gf o ri n t e m e t ，t h e1 ( i n d a 1 1 dt 1 1 ei m p o r t a n c eo fn e t w o r ka p p l i c a t i o ni n c r e a s ed a yb yd a y ，a n dm eb e h a v i o ro fn e t w o r ka t t a c k si sm o r ea n dm o r es e n o u s ，s oi t i sm o r ea n dm o r ec h a l l e n g i n gt oe n s u r en e 觚o r ks e c u r 主t yv a “o u sk i n d so ft r a d i t i o n a ls t a t i cs e c u r i t yd e f e n c es y s t e m ，s u c ha sf i r ew a l l ，i d e n t i t ya u t h e n t i c a t i o na n dd a t ae n c r y p c i o n ，c a n ta l r e a d ya d a p tt ot h ec u r r e n tn e t w o r ks e c u r i f ys t a t e t h e ni n t m s i o nd e t e c t j o ns y s t e ma r i s e da n di ti sa p p l i e dw i d e l yb e c a u s eo fi t sh i 曲d e t e c t i o na c c u r a c y ，l o wf a l s ep o s i t i v er a t ea n ds t r o n gp r a c t i c a b 订i t yf r o mt h ec u r r e n ts i t u a t i o no f n e t w o r ks e c u r i t y ，t h i st h e s i sf i r s td i s c u s s e ss o m et e c h n 0 1 0 9 yo fn e t w o r ks e c u r i t y ，a n dp r o p o s e si n t r u s i o nd e t e c t i o ns y s t e m t h e ni ti n t r o d u c e st h ed e v e l o p i n gh i s c o r y ，d e f i n i t i o n ，a r c h i t e c t u r ea n du s u a l l yu s e dd e t e c t i o ns y s c e mt y p e s ，a n do nt h i sf o u n d a t i o n ，p u t sf o n v a r da ni n n l j s i o nd e t e c t i o ns y s c e mb a s e do nh 塘hp e r f o n t l a n c ep a t t e mm a t c h i n gt h j st h e s i sm a i n l yd e a l sw i t ha ni n t r u s i o nd e t e c t i o ns y s t e mb a s e do nh 培hp e r f o r m a n c ep a t t e mm a t c h i n g ( h p p m ) a l g o r i m m t h ek e yt ot h es y s t e mi sc h ep a t t e r nm a t c h i n ga l g o r i t h m t h et h e s i si n t r o d u c e ss o m et y p i c a ls i n 9 1 e p a t t e mm a t c h i n ga l g o r i t h m sa n dm u t i p a f t e mm a t c h i n ga l g o r i t h m s ，t h e nt h i n k i n ga b o u tt h em f m i n gt i m ea n du s e ds p a c e ，i tp r o p o s e sah i g hp e r f b n n a n c ep a t t e mm a t c h i l l ga l g o r i t h ma f t e ra n a l y z i n gh p p ma l g o r i e h mi sb a s e do nt h ei d e at h a ti fw e 矗n dt h er a r e s t4 一b y t es u b s t r i n go fap a t t e mi n s i d et h ep a c k e tp a y l o a d ，t h e nw ea s s u m et h a tt h i sp a t t e mm a t c h e s e a c hp a t t e mi sn o wr e p r e s e n t e db yi t sl e a s tp o p u l a r4 _ b y t es e q u e n c e ，w h e r e p o p u l a rr e f l e c t st h en u m b e ro f t i m e st 1 a tas p e c i n cs u b s t r i n ge x i s t si na 1 ip a t t e m s t h ee x p e r i m e n t sp r o v et h a ti tc a ni m p r o v ei h ed e t e c t i o ne 币c i e n c y 铲e a t l ye x c e p tf o rd a t ac 0 1 l e c t i o nm o d u l e ，i n t r u s i o nd e e e c t i o ne n g i n em o d u l ea n dr e s p o n d i n gm o d u l et h a ta ni n t m s i o nd e t e c t i o ns y s t e mc o r r l m o n l yh a s ，t h es y s t e ma l s oh a sp r e p r o c e s s o rm o d u l e ，p r o t o c 0 1a n a l y s i sm o d u l ea n dm a n a g e m e n t & d e p l o ) ，r n e n tm o d u l e i nt h ed e t e c i i o ne n g i n e ，t h es y s t e mu s eam e t h o dt h a td e r e n tt ot r a d i t i o n a li n t m s i o nd e t e c t i o ns y s t e m b e f o r ep a t t e md e t e c t i o n ，t h ed e t e c t i o ne n g i n eo p t i m i z e dt h en l l e sa c c o r d i n gs p e c i a lm l ep a r a m e t e r s a 1 1a b o v ei m p r o v et h es y s t e mp e r f o r n l a n c et h es y s t e mi sa no p e np l a t f o m ，a n ds o m ef u n c t i o n sn e e dt ob ee x d a n d e dk e y w o r d s ：n e t w o r ks e c u r i t y ；i n t m s i o nd e t e c t i o n ；p a t t e mm a t c h i n g ；h a s h f l i n c t i o n ；h p p ma l g o r i t h m一种基于高效模式匹配算法的入侵榆测系统第一章绪论1 1 引言计算机和计算机网络的不断普及，把人们的学习、工作和生活紧密地联系在了一起。它涉及到政治、军事、经济、交通、文教等各个部门，成为整个社会基础设施中非常重要的一部分。特别是i n t e r n e t 的高速发展，极快地加大了社会信息化的步伐，但是网络的开放性也为信息的窃取、盗用、非法修改以及捣乱破坏提供了可乘之机，使得信息在存储、处理、传输等各个环节都呵能受到入侵者的攻击和病毒的危害，从而造成系统的瘫痪或重要数据的丢失。因此计算机和网络系统在给人们带来巨大方便的同时，也同样带来一个令人担忧的问题，即它们的安全性。人们对计算机的依赖程度越高，对计算机的安全性也就要求越高。近年来，随着i n t e r n e t的迅速发展，网络攻击事件时有报道。据c e r t c c k r 在2 。0 0 年的报告“，全球的i n t e r n e t 在2 0 0 0 年所受到的攻击数量是1 9 9 9 年的3 倍。因此我们必须尽可能地确保计算机和网络系统的安全，否则，不仅会造成大量人力、物力资源的浪费，还会使公司由于商业信息和研究技术被窃而带来竞争能力的丧失，更为严重的是，会丢失有关国家机密，从而危及国家的安全。这些都使得网络安全问题显得日盏重要。我国的信息化进程发展迅速，网络已经渗透到国民经济的各个领域，渗透到我们工作和生活的方方面面。然而现有的计算机网络大多数在建设之初就忽略了安全问题，即使考虑到安全问题，也只是把安全建立在物理机制上，因此，随着网络互联程度的扩大，这种安全机制对于网络环境来说形同虚设。另外，目前网络上使用的协议，如r c p i p 协议，在制定之初，也没有将安全考虑在内，所以在安全方面存有漏洞。由f 网络安全问题的敏感性，我们不能像引进其它高科技产品一样，大量引进国外网络的安全产品。因此，研究和丌发自己的网络安全产品就显得格外重要。1 2 网络安全和主要安全机制网络安全是一门涉及计算机科学、网络技术、通信技术、密码技术、信息安全技术、应用数学、数论和信息论等多种学科的综合性学科。它基本上是一个实践性的技术领域，大多数的理论基本上是经验的汇集，因此要给出个形式化的定义是很困难的，在这星，给出网络安全的一个通用定义。网络安全“1 是指网络系统中的硬件，软件及其系统中的数据受到保护，不受偶然或者恶意的原因而遭到破坏、更改、泄漏，系统可以连续可靠地运行，网络服务不山西大学2 0 0 5 届硕士研究生学位论文会中断。网络系统的主要安全机制有。”：物理安全，指为保证计算机设备和通信线路及设施的安全。一是要预防自然灾害，保证设备正常的运行环境：二是设定安全管理规定，并且防止有关设备被盗。身份验证( i d e n t i t ya u t h e n t i c a t i o n ) 。最常见的身份验证是用户名( u s e r n a m e )和口令( p a s s w o r d ) 。系统要求用户登录时输入用户名和口令，以确保用户合法性，从而防止任何非经授权的用户对系统资源的访问。身份验证的其它方法还有智能号、指纹、语音识别和数字签名等。访问控制( a c c e s sc o n t r 0 1 ) 。主要通过操作系统来实现，除了保护计算机网络安全的硬件之外，网络操作系统是确保计算机网络安全的最基本部件。网络操作系统安全保密的核心是访问控制，即确保主体对客体的访问只能是授权的，未经授权的访问是不允许的，而且操作是无效的。它是系统对资源访问的一种保护机制。系统对授权用户的访问权限进行检查，以确定该用户是否被允许访问某一特定的系统资源。常用的方法主要有两种：自主访问控制，即d a c ( d is c r e t i o n a r ya c c e s sc o nl r 。1 ) ，强制访问控制，即m a c ( m a n d a t o r ya c c e s sc o n t r 0 1 ) 。密码技术( c r y p t o g r a p h y ) 通过采用一些基本的数学理论，防止非法截取或修改信息流，本质上是在通信双方之间建立一条安全的通信链路。当授权用户通过网络和其它用厂1 和资源进行交互时，系统可以在信息的发送端对待发送的倩息进行加密，在接收端对接收的信息进行解密，从而使得任何非经授权的用户无法在这一通信过程中读懂、理解、更改授权用户所交互的信息。防火墙( f i r e w a l l ) 是网络安全的基础，它是保护内部网络的第一道防线，它j 监视和控制内部网络和外部网络之间的访问通道，按照系统预定的安全策略，在网络边界上阻断一切被认为是不安全的外部网络流量。物理上，防火墙就是在被保护网络和i n t e r n e t ，或者其他网络之问限制访问的种或者系列的部件。防火墙是使汁算机和网络系统上的资源免受外来威胁的标准方法，也是目前使用最“泛的一种保护网络安全的方式。防火墙的基本类型有包过滤型、代理胀务垂_ 、状态检测型和复合型。入侵检测( i n t r u s i o nd el e c t i o n ) 是防火墙后面的第二道防线它刘网络系统的运行状态进行监视，发现各利t 攻击企俐、攻击行为或者攻击结果，以保证系统资源的机密性、完整性和可用性。一个完善的入侵检测系统必须具有经济性、时效性、安全性和可扩展性的特点。有关入侵柃测的详细内容清参阅第部分。一种基于高教模式匹配算法的入侵检测系统需要指出的是虽然提出了各种各样的安全技术和方法，但安全绝不是技术和产品的堆积，安全也永远不会是一劳永逸的事情，攻击和反攻击的较量会一直持久下去，所以为了使系统更安全，我们必须同时在人和制度方面加以协调。1 3 入侵检测系统的研究历史与现状入侵检测方面的工作屉早是在1 9 8 0 年由j a m e sp a n d e r s o n 进行的，他在一份题为c o m p u t e rs e c u r i t yt h r e a tm o n i t o r i n ga n ds u r v e j ll a n c e ”3 ( 计算机安全成胁监控与监视) 的技术报告中，第一次闸述了入侵检测的概念。他对三类主要的计算机威胁进行了识别：( 1 ) 外部闯入者，指系统的非授权用户。( 2 ) 内部渗透者，指系统合法用户访问未经授权的系统资源。( 3 ) 违法者，指授权用户滥用权限。1 9 8 6 年d o r o t h yd e n n i n g 提出入侵检测专家系统的抽象模型5 j ，首次将入侵检测的概念作为一种计算机系统安全防御问题的措施提出，与传统加解密和访问控制的方法比较，入侵检测系统是全新的计算机安全措施。1 9 8 8 年，s r i c s l 的t e r e s al u n t 等人改进了d e n n i n g的入侵检测模型，开发出了i d e s ( i n t r u s i o nd e t e c t i o ne x p e r ts y s t e m ) 。该系统包括一个异常检测器和一个专家系统，分别用于统计异常模型的建立和基于规则的特征分析检测。1 9 8 8 年的莫里斯蠕虫事件发生之后，网络安全才真正引起了军方、学术界和企业的高度重视，从而人们丌始了入侵检测系统的开发研制工作。先后出现了许多这方面的研究原型，如a u d ita n a 】y s is 项目、d i s c o v e ry 、h a y s l a c k 、m i d a s以及w i s d o ma n ds e n s e 等入侵检测系统。1 9 9 0 年是入侵检测系统发展史上的一个分水岭，在这之前，所有的入侵检测系统都是基于主机的，它们对于活动的检查局限于操作系统审计踪迹数据及其它以主机为中心的数据源，而这一年，加州大学戴维斯分校的l t h e b e r l e i n 等人开发出了n s m ( n e t w o r ks e c u r i t ym o n i t o r ) 。该系统第一次将网络流作为检测数据的来源。从此以后，形成了两种类型的入侵检测系统：基于主机的入侵检测系统和基于网络的入侵检测系统。美国空军、国家安全局和能源部共同资助空军密码支持中心、劳伦斯利弗摩尔副家实验室、加州大学戴维斯分校、h a y s t a c k 实验室丌发研究的分市式入侵检测系统( d i d s ) “3 第一次将基于主机和基于网络的方法集成在了一起。同时d i d s 是分布式入侵检测系统历史上的一个罩程碑式的产品，它的检测模型采用了分层结构，包括数据、事件、主体、上下文、威胁和安全状态等6 层。1 9 9 4 年，m a r kc r o s b i e 和g e n es p a f f o r d 建议使用自治代理( a u t o n o n l o u sa g e n t s ) ，以提高入侵检测系统的可伸缩性、可维护性、效率和容错性。1 9 9 6 年提出g r i d s “( g r a p h 岫a s e di n tr l 】s io n 【) e t e cl i o ns y s t e m ) ，使得系统对大规山西大学2 0 0 5 届硕士研究生学位论文模自动协同攻击做出检测。近年的主要创新有，f o r r o s t 等将免疫原理”运用到分布式入侵检测领域。1 9 9 8 年r o s sa n d e r s o n 和a b i d ak h a t t a k 将信息检索技术引入入侵检测。总之，从2 0 世纪9 0 年代到现在，入侵检测系统的研究和开发出现了百家争鸣的繁荣局面，并在许多方面都取得了很大的进步。国内对入侵检测系统的研究起步较晚，目前处于对国外技术的跟踪状态。近年来中科院、清华大学、国防科技大学、北京邮电大学、中联绿盟和肩明星辰等单位开展了入侵检测系统的理沦研究和产品的开发工作，但从发表的文献来看主要以研究综述和提出系统框架等居多。从理论上来看，突破性的创新理论还没有出现。1 4 论文研究的意义在网络的主要安全机制中，入侵检测是一种比较新的技术，它属于积极主动的防护技术，提供了对内、外攻击和误操作的实时保护，在网络系统受到危害之前拦截入侵。防火墙用在一个不可信网络( i n t e r n e t ) 和可信网络( 专用网络) 之间，以提供个安全边界。它利用事先制定的规则对出入系统( 网络和主机) 的数据进行选择，阻止异常数据出入系统。单靠防火墙不足以保证网络的安全性，因为：( 1 ) 配晋复杂。经调查表明，半数以上的防火墙配置不正确。( 2 ) 过滤器只能对网络数据包出现的域进行操作，某些决策的产生需要更高级别的信息，而这些信息只有在数据报文被接收并重组后才能得到。( 3 ) 过滤器不含有应用程序的特有知识( 例如：只能在i p 地址基础上限制t e l n e t 连接，而不能获取t e l n e t 连接的用户信息) 。( 4 ) 1 i 理解连接的数据报文内容的特定含义( 例如，通过r i p 登录某个主机并下载主机rj 令文什的行为，防火墙无法察觉。) ( 5 ) 防火墙不能阻止内部的攻击。f 因如此，入侵检测技术j 被研发并得以利用。入侵枪洲作为防火墒之后的第二道安全闸门，具有高智能。在f ：影响网络性能的情况f ，它能对m 入系统的数据进行实时监控，并且搜集、整理数据报文中各个协议层和数据内容中的可疑信息，时当6 u 系统( 网络和主机) 状态和用户行为做出推断，看是否有入侵产牛。按照检测技术进行划分，入侵检测系统。j 以分为异常检测和误用检测，存误川检测巾，基于模式匹配的入侵检测技术首先将入侵行为表示成一种模式或特征，然后从系统同志或网络流量中查找是否有匹配的发尘。这种类型的入侵榆测系统具有检测牢高，误警半低，并且较其它方法简币，可行，所以引起了广泛的火汁= =种基于高效模式匹配算法的入侵检测系统1 5 论文组织本文主要研究的是基于模式匹配的入侵检测系统的设计与实现，论文包括如下主要内容：第一章为绪论部分，对网络安全的概念和主要安全机制、入侵检测的研究历史与现状以及论文研究的意义进行了综合论述。第二章介绍了入侵检测系统的定义、基本结构和分类，从而提出了基于模式匹配的网络入侵检测系统。第三章阐述了模式匹配的方法和概念，并给出一些常用的模式匹配算法，然后在此基础上提出了一种高效的模式匹配算法。第四章具体说明了一种基于高效模式匹配算法的入侵检测系统的设计与实现。第五章在前面内容的基础上，进行了系统测试，并给出了测试结果。最后对本文所做的工作进行总结，提出今后继续研究和扩展的方向。其中第三、第四章是本文的重点。山西大学2 0 0 5 届硕士研究生学位论文第二章入侵检测系统2 1 入侵检测系统的定义入侵的定义：任何试图危害资源的完整性、可信度和可获取性的动作。s a l v a t 。r e从访问方式e 把入侵分为四种。：d o s ( d e n i a lo fs e r v i c e ) 拒绝服务攻击，如p i n go fd e a lh ，t e a r d r o p 等：r 2 l ( u n a u t h o r i z e da c c e s sf r o mar e m o t om a c h i n e ) 远程未授权访问，如密码破译等；u 2 k ( u n a u t h o r i z e da c c e s st o1o c a 】s u p e r u s e rp r iv ii e g e sb yl o c a lu n p r jv i l e g e du s e r ) 本地非授权用户成为超级用户未授权访问，如各种缓冲区溢出攻击等；p r o r 探测，如p o r t s c 1 n 等。入侵检测“”( i n t r u s i o nd e t e c t i o n ) ：指从网络系统中的若干关键点收集信息并进行分析，从而发现网络系统中是否有违反安全策略的行为和被攻击的对象，并做出适当的响应。它既能检测非经授权而使用计算机系统的用户( h a c k c r s ) ，也能榆测那些虽有合法的权限，却滥用系统的用户( i n s jd e rt h r e a t ) 。入侵检测系统”。( i n tr u s i o nd e t e c t i o ns y s t c m i d s ) ：是标识和隔离入侵的安伞技术。入侵检测被认为足防火墙之后的第二道防线，足动态安全技术的核一心技术之一。一个完善的入侵检测系统必须具有下列特征：( 1 ) 经济性。为了保证系统安全策略的实施而引入的入侵检测系统必须保证不能妨碍系统的正常运行。( 2 ) 时效性。指必须及时地发现各种入侵行为，能在攻击行为发乍的过程中检测到。( 3 ) 安全性。入侵检测系统自身必须安全，如果系统自身的安全得，f i 到保障，首先意味着信息的无j i f ，更i 重的是入侵者控制了入侵检测系统而获得了对系统的控制权。( 4 j j 扩展性。苒先是机制与数据的分离，即存现有机制不变的前提下能够对新的攻击进行检测：其次是体系结构的可扩充性，即在必要的时候可以在不对系统的整体结构进行修改的前提下对检测手段进行加强，以能够检测到新的攻击。22 入侵检测系统的基本结构图2 1 通用入侵检洲系统结构6二型苎! 童塾堡茎坚墼竺鲨塑垒堡丝型墨竺在图2 ，l 中给出了一个通用的入侵检狈9 系统结构框图“”。探测器用于收集数据，包括任何可能包含入侵行为线索的系统数据。分析器负责从一个或多个探测器处接收信息，然后用各种不同的检测方法对数据进行分析。用户接口使得用户易于观察系统的输出信号，并对系统行为进行控制。其中数据分析是入侵检测系统的核心。2 3 入侵检测系统的分类2 3 1 数据来源入侵检测系统按照数据的来源，分为两类：( i ) 基于主机的入侵检测系统( h 0 s t 咄a s e dr d s h i d s ) “：通常安装在受保护的主机上，用柬监视、检测某一给定计算机系统或用户，它有两种类型的信息源，操作系统审计踪迹和系统同志。其主要优点是，信息源完备。系统产生的日志是归类有序的，它准确地记录了每个用户的行为序列，这样便可以精确监控每个用户的行为，同时也使得i d s 对信息源的处理简单、一致。其次，对某些特定的攻击十分有效。比如，审计日志能显示出由缓冲区溢出攻击引起的优先级转移的情况，从而能够有效她检测出缓冲区溢出攻击。其主要缺点是，首先信息源与操作系统密切相关。所以i d s 系统不能通用于各种平台。其次，信息源单一，缺乏相关性。随着黑客入侵技术的不断发展，系统入侵通常发生在整个网络范围内，涉及一系列主机。所以仅靠单一主机的信息源无法做出准确的判断。第三，剥网络底层攻击检测困难。尽管月志记录了大量的嘲络事件信息，但是通过审计日志不能发现网络数据包内容或底层攻击，比如s y nf 1 0 0 d 攻击。基于主机的i d s 由于在这些日志中没有找到相应信息而忽略某些攻击。( 2 ) 基于网络的入侵检测系统( n e t w o r k _ b a s e di d s n i d s ) “”：它通常安装在网络的关键段，监控出入网络的通信数据流，按照一定规则对数据流的内容进行分析，从而发现攻击的企图，做出入侵攻击的判断。其主要优点是，首先，平台无关性。它以网络数据作为信息源，与主机平台无关。其次，全局性。由于它通常位于网络的关键劂段，所有的通信都会通过这里。所以，它的信息源涵盖了整个内部网络，有利于根据信息的相关性作了全局推断。其j i 要缺点是，首先，对经过加密的数据流进行分析存在困难。数据流经过加密后，其一p 的数据特征已经变形，i o s 无法对其进行分析、识别。其次，难以精确监控用户的行为。它只能从用户交换的报文中奉日略地判断用户的行为，却不能判断出用户行为对目标系统造成的影响，从而忽略某些入侵行为。比如，用户执行了一个缓冲区溢出程芋，网络i d s 只能够决定用户在执7山西大学2 0 0 5 届硕士研究生学位论文行一个程序，却无法判断用户执行的程序是否有害。2 3 2 检测方法根据检测方法的不同，可以将入侵检测系统分为两类：( 1 ) 异常检测( a n o 腑l yd e t e c t i o n ) ：它来源于这样的思想，即任何一种入侵行为都能由于其偏离正常或者所期望的系统和用户的活动规律而被检测出来。描述正常或者合法活动的模型是从对过去通过各种渠道收集到的大量历史活动资料的分析中得出来的。入侵检测系统将它与当前的活动情况进行对比，如果发现了当前状态偏离了正常的模型状态，则系统发出警告信号。就是说，任何不符合以往活动规律的行为都将被视为入侵行为。其优点是，首先，能够发现任何仓图发掘、试探系统最新和未知漏洞的行为，同时在某种程度上它较少依赖于特定的操作系统环境。其次，对于合法用户超越其权限的违法行为的检测能力大大增强。其缺点主要是很高的洪警率。常用的异常检测方法有：统计模型“，神经网络“，人工免疫“。，数据挖掘= ”。”等。( 2 ) 误用检测( m i s u s ed e t e c t i o n ) ：是建立在对过去各种已知网络入侵方法和系统缺陷知识的积累之上，它需要首先建立一个包含上述已知信息的数据库，然后存收集到的网络数据流中查找与之匹配的项目，从而发现是否有攻击的行为。其优点是，具备较高的检测准确率和较低的误警率，同时检测的条件可以进行清楚地描述，从而有利于安全管理人员采取清晰明确的预防保护措旌。其缺点是，收集所有已知或已发现攻击行为和系统脆弱性信息的困难性阻及及时更新庞大数据库需要耗费大量精力和时i 剐。另一个问题在于弱的可移植性。因为关于网络攻击的信息绝大多数是与主机的操作系统、软件平台和应用类型密切相关的。此外，检测内部用户的滥用权限活动将变得相当困难，因为通常这种行为并未利用任何系统缺陷。常用的误用检测方法有：模式匹配，状态转换”“等。23 3 时效性按照数据分析发生的时间不同，可以分为：( 1 ) 脱机分析：就是指先收集数据，然后再对数据进行分析。而不是在数据收集的同时进行分析。如对几志的审核、对系统文件的完整性榆查等部属于这种，但是，脱机分析也不会间隔很长，它只是和联机相对而言的。( 2 ) 联机分析：就是指在数据产生的同时对其进行检查，以发现攻击行为。这种方式一般用于对网络数据的实时分析，对系统的资源要求比较高。种基于高效模式匹配算法的入侵检测系统2 3 4 分布性按照系统各个模块运行的分布方式不同，可以分为：( 1 ) 集中式：系统的各个模块包括数据的收集、分析和响应都集中在一台主机上运行。这种技术的优点是：数据的集中处理可以更加准确地分析可能的入侵行为。缺点是：数据的集中处理使检测主机成了网络安全的瓶颈，若它出现故障或受到攻击，则整个网络的安全将无从保障这种方式适用于网络环境比较简单的情况，因为数据采集对于大型的复杂的网络很难实现。( 2 ) 分布式：系统的各个模块分布在网络中不同的计算机上，这种分布式结构采用多个代理在网络各部分分别进行入侵检测，并且协同处理可能的入侵行为，其优点是：能够较好地实现数据的监听，可以检测内部和外部的入侵行为。这种方式适用于网络环境比较复杂的情况，并且是现在入侵检测的发展方向之一。2 4 检测技术标准化( c i d f 模型)c i df 2 l ( c o m m o ni n t r u s i o nd e t e c t i o nf r a m e w o r k ) 是一个入侵检测系统的通用模型，它将一个入侵检测系统分为以下部分：事件产生器( e v e n tg e n e r a t o r ) 、事件分析器( e v e n ta n a l y z e r ) 、响应单元( r e s p o n s eu n i t s ) 和事件数据库( e v e n td a t a b a s e ) 。c i d f 将入侵检测系统需要分析的数据统称为事件( e v e n t ) ，它既可以是基于网络的入侵检测系统中网络中的数据包，也可以是基于主机的入侵检测系统从系统同志等其他途径得到的信息。事件产生器的任务是收集事件，并将这些事件传送给其他部件。事件分析器将收到的数据进行分析，并产生分析结果。响应单元则对分析结果做出反应，并采取相应的措施，如断掉连接等。事件数据库是存放各种中间和最终数据的地方的统称，它可以是复杂的数据库，也可以是简单的文本文件。2 5 小结本章主要介绍了入侵检测系统的发展、定义、基本结构、分类以及检测技术标准化模型( c i d f ) 。从检测方法上分析，现有的些方法还处于模型阶段，没有应用到实践中去。所以本文提出了一种基于模式匹配的嘲络入侵检测系统，它主要分析的是网络流量，所以属于基于网络的、集q 、的、实时的入侵检测系统，它同样遵循c r d f 标准，并且实现方法比较简单、可行。在基于模式匹配的入侵检测系统中，模式匹配就显得尤为重要，所以在下一章具体讨论基于模式匹配的入侵检测方法。山两大学2 0 0 5 届硕士研究生学位论文第三章基于模式匹配的入侵检测方法3 1 模式匹配的方法、概念及研究的意义3 1 1 模式匹配原理模式匹配是由入侵检测领域的大师k u m a r 在1 9 9 5 年提出的，首先，k 。- m a r 提出了入侵信号的层次性概念。依据底层的审计事件，可以从中提取出高层的事件；由高层的事件构成入侵信号，并依照高层事件之间的结构关系，划分入侵信号的抽象层次并对其进行分类。其次，k u m a r 将入侵信号分成四个层次，每一层对应相应的匹配模式。】存在( e x i s t e n c e )这种入侵信号表示只要存在这样种审计事件就足以说明发生了入侵行为或入侵企图，它所对应的匹配模式称为存在模式( e x i s t e n c ep a t t e r n ) 。存在模式可以理解为在一个固定的时问对系统的某些状态进行检查，并对系统的状态进行判定。2 序列( s e q u e n c e )有些入侵是由一些按照一定顺序发生的行为所组成的，它具体u 以表现为纽事件的序列。其对应的模式就是序列模式( s e q u c n c ep a t t e r n ) 。序列模式在检测入侵时需要特别关注问隔和持续时间。3 舰则表示( r e g u l a re x p r o s s i o n s )规则表示模式( r e g l l l a re x p r e s s j o n sp a t t e r n s ) 是指用一种扩展的规则表达式方式构造匹配模式，规则表达式是由用a n d 逻辑表达式连接一些描述事件的原语构成的。适用这种模式的攻击信号通常由一些相关的活动所组成，而这些活动问没有什么事件顺序的关系。4 其他其他模式( m h e rp a l t c r n ) 是指些不能用前面的方法进行表示的攻山。在具体的实现中，很难做到对所有入侵信号进行模式匹配，一般只是部分实现。31 2 模式匹配系统的特点把攻击信号看成种模式进行匹配检测有以下一螳特点：事件来源独立：模式的拙述并不包含对事件来源的描述，模式只需要r 解事件u 以提供什么数据，而刁i 管事件如何提供这些数据。描述和匹配相分离：描述入侵信号的模式主要是定义什么需要匹配，而，1 i 是如何去匹醚。一种基于高效模式匹配算法的入侵检测系统动态的模式生成：描述攻击的模式可以在需要的时候被动态生成。可移植性：入侵模式可以被轻易地移植，而不需要重新生成。3 ，1 3 模式匹配系统的具体实现模式的提取：要使提取的模式具有很高的质量，能够充分表示入侵信号的特征，i 司时模式之间不能有冲突。匹配模式的动态增加和删除：为了适应不断变化的攻击手段，匹配模式必须具有动态变更的能力。增量匹配和优先级匹配：在事件流对系统处理能力产生很大压力的时候，要求系统采取增量匹配的方法来提高系统效率，或者可以先对高优先级的事件先行处理，暂缓对低优先级事件的处理。完全匹配：匹配机制必须能够提供对所有模式进行匹配的能力。3 1 4 模式匹配的概念模式匹配系统主要是用一定的模式描述来提取攻击的主要特征，其基本任务就是把存放在入侵检测规则集中的已知入侵模式与系统眶在检测的网络包或者重构的t c p 流中的文本进行匹配，如果匹配成功，则可以断定发生了入侵。这个过程是不断循环f i 仃进的。模式匹西己是指：已知一长度为n 的文本字符串t = t t 。t 。，和一长度为m ( m n ) 的模式字符串p = p 。p ：p ，看t 中是否存在长度为m 的子串。3 1 5 模式匹配研究的意义模式匹配检测技术主要优点是检测过程简单，无须训练，检测效率高，一般情况f 不存在误检测。模式匹配在网络入侵检测中有着非常重要的影响，以前的调查结果表明? 2 ：，3 0 的处理时间都在进行模式匹配，除了运行时间，网络入侵检测系统同时需要较小的内存空m ，所以需要找到一种好的模式匹配算法，以提高入侵检测系统的性能。3 2 常用的匹配算法32 1 单模式匹配单模式匹配算法：对文本t 的一次扫描，只能处理一个模式串。1 b r u t ef o r c e 算法：此算法的实质是将模式p 和文本t 从庄到右逐个搜索，若在某一位匹配失败，则将模式p 向右移动一位，仍从模式p 的第一位开始搜索，卣到将文本r 搜索完为止。在最坏的情况下，耍执行( n m + 1 ) m 次字母的匹配，因此其时间复杂度为臼( m n ) 。所山西大学2 0 0 5 届硕士研究生学位论文以当n 不大时，可以采用这种算法。2 k m p 算法。“b r u t ef o r c e 搜索算法在一饮字符比较失败后，只是简单地把模式向右移动一个字符位置。这样做的缺点是完全丢弃了前面己经做过的字符匹配中得到的信息，实际上这些匹配信息是可以利用的。k m p 算法是k n u t h ，m o r r i s ，p r a t t 提出的。和简单算法不同当某次匹配不成功，模式串不一定只能右移一格，右移后也不一定必须从模式起点处开始匹配。具体算法描述如下：在某次试匹配成功时，若t ，p 。，即模式的前j 1 个字符全能匹配，如果事先知道子模式p 。p ：p 。有一个最长的真首子串和它的尾子串相等，即p r = p 。+ 。p - 一p 。，那么，下一次试匹配时，可把模式串右移n e x t j 位置，n e x t 】j 表示当模式串中第j 个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。n e x t j 可以在预处理时计算。为了不遗漏可能完全匹配的情况，l 述的真首子串必须是最长的。故对于任。个子模式p ，r p j ( 1 j n ) ，“自匹配”的真首子串是唯一的，它只和模式自身的结构有关。k p 算法采取的方法是一次把模式向右移动多个位置，这就使得在匹配过程中完全不需要回溯。在最好的情况下，k 算法的时间复杂度为口( n 十m ) 。计算n e x t j 的时间复杂度为驴( m ) 。3 b 。y e rm o o r e ( b m ) 算法”“( 1 ) 匹配自右向序进行；( 2 ) 若匹配失败发牛存p t ，且t ，不出现在模式p 中，则将模式右移直到p h 寸于匹配失败位t 的右边第一位( 即t 。位) ，若t 。存p 巾有若下地方出现，则应选择j = m a x f k l r = t ：( 3 ) 若模式p 后面k 位和文本t 中一致的部分，仃一部分在t 中其他地方出现，则玎以将t 向右移动，舟接使这部分对齐，且要求这部分尽，叮能的大。b 算法采用“跳跃式”查找策略，多数情况下不需要对文本进行次完整的扫描，其时问复杂度为臼( f 1 m ) 。3 22 多模式匹配多模式匹配算法：对文本t 的一次扫描，能够同时处理多个模式串的集合。1 ，a h 0c o r a s i c k ( a c ) 算法“j 1一种基于高效模式匹配算法的入侵检测系统a c 算法是同时搜索多个模式的经典算法。a c 算法使用了有限状态自动机的结构来接收集合中所有的字符串。自动机是结构化的，这样每个前缀都可用唯一的状态来标识，甚至是那些多个模式的前缀。当文本中下一个字符不是模式中预期的下个字符中的一个时，会有一条失败链指向那个状态，代表最长的模式前缀，同时也是当前状态的相应后缀。a c 算法的复杂性是臼( n ) ，预处理阶段的复杂性是口( 【1 1 ) 。在用a c 算法构造的有限状态自动机中，可以发现这样一个现象：离自动机根较近的地方，结点比较密集，即这时自动机的各个分枝中的结点都比较密集，相反，离根越远，结点越稀疏，这是由于模式串的长度不同而引起的。在a c 算法中，要为每一个模式串的每一个字符建立一个结点，这样无疑便得该算法的空问使用情况很高，为了压缩a c 算法的空间使用率，可以将稀疏的结点合并成一个结点，即a c p a t h算法。但是a c p a t h 算法在节省了空间的同时，却也增加了模式匹配时的难度，其运行所需要的时间也随之增加。2 w u m a n b e r ( w m ) 算法jw u m a n b e r 算法是b m 算法处理多模式匹配问题的派生形式，是一种快速实用的多模式匹配算法。它采用了b m 算法的基本框架，但不同于b m 的是，它不是使用一个字符来计算坏字符移动的距离表，而是使用块字符来计算坏字符移动的距离表( s h i f t ) 。此外，在进行模式匹配时，它使用哈希表选择模式串集合中的一个子集与当前的文本进行匹配，以减少无谓的匹配运算。w u m a n b e r 算法不会随着模式串集合的增加而成比例的增长，而且要远少于使用每一个模式和b m 算法对文本进行匹配的时间总和。w u m a n b e r 算法的时间复杂度在最好的情况下能达到臼( b n m ) ( b 是块字符的长度，是算法在每一个入口点计算块字符的时间) 。3 3 高效的模式匹配算法( h p p m )在单模式匹配算法中，b m 算法是比较经典的，它能利用跳转表跃过待搜索文本中的大段字符，从而提高搜索速度。但它一次只能处理