（通信与信息系统专业论文）网络入侵检测系统中模式匹配算法的研究.pdf

华北电力人学硕十学位论文摘要 摘要 模式匹配是网络入侵检测系统中一种非常重要的检测方法，它直接影响到系统 的实时性。当前计算机网络向着高速、宽带化的方向发展，入侵检测系统的检测速 度越来越成为其性能的瓶颈。本文首先阐述了模式匹配的基本原理以及模式匹配在 网络入侵检测系统中的应用，然后具体分析了入侵检测系统中重要的单模式b m 算 法，多模式a c 算法和a c b m 算法，在此基础上提出了一种改进的模式匹配算法一 m a c 算法，并从时间和空间的角度分析了这些算法的复杂度。m a c 算法可以同时进 行多个模式的匹配，并在匹配过程中实现比较大的跳跃，因而可以更快地进行模式 匹配。最后，对以上算法进行了文本测试和对网络数据包的检测，实验表明改进的 m a c 算法使入侵检测的速度有了提高。 关键字：网络入侵检测系统，模式匹配，模式匹配算法，算法测试 a bs t r a c t p a t t e r nm a t c h i n gi sav e r yi m p o r t a n td e t e c t i o nm e t h o df o rn e t w o r ki n t r u s i o n d e t e c t i o ns y s t e m ，a n di th a sad i r e c t l yi n f l u e n c eo nt h er e a l t i m ep e r f o r m a n c eo ft h e i n t r u s i o nd e t e c t i o ns y s t e m ( n i d s ) b u ta sn e t w o r kh a sd e v e l o p e dt o w a r d sr a p i da n d b r o a d b a n d ，t h ed e t e c t i o ns p e e di sb e c o m i n gap e r f o r m a n c eb o t t l e n e c ko ft h ed e t e c t i o n s y s t e m t h i sp a p e rf i r s t l yi n t r o d u c e st h ep r i n c i p l eo fp a t t e r nm a t c h i n ga n di t sa p p l i c a t i o n i nn i d s t h e nw es t u d yt h em a i np a t t e r nm a t c h i n ga l g o r i t h m sn o wu s i n gi ni d ss u c ha s b m ，a ca n da c b m ，a f t e rt h a tw eb r i n gf o r w a r da ni m p r o v e da l g o r i t h mn a m e dm a c ， a n da n a l y z eb o t ho ft h e i rt i m e c o m p l e x i t ya n da p a c ec o m p l e x i t y t h ei m p r o v e d a l g o r i t h mc a nm a t c hm a n yp a t t e r n sa to n et i m ea n di to b t a i n sb i g g e rs k i pv a l u e ，s oi tc a n m a t c hp a t t e r n sq u i c k e rt h a no t h e ra l g o r i t h m s f i n a l l yt h e s ea l g o r i t h m sa r ea l li m p l e m e n t e d i nt e x tt e s ta n dn e t w o r kp a c k e t sd e t e c t i o n ，a n de x p e r i m e n t si n d i c a t et h a tt h ei m p r o v e d a l g o r i t h mm a cp r o v i d e sas i g n i f i c a n ti m p r o v e m e n ti np a t t e mm a t c h i n gp e r f o r m a n c ew h e ni t i su s e di na ni n t r u s i o nd e t e c t i o ns y s t e m h u a n gj i n - l i a n ( c o m m u n i c a t i o na n di n f o r m a t i o ns y s t e m ) d i r e c t e db yp r o f g a oh u i s h e n g k e yw o r d s ：n 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 ，p a t t e r nm a t c h i n g ，p a t t e r nm a t c h i n g a l g o r i t h m ，a l g o r i t h mt e s t 声明 本人郑重声明：此处所提交的硕士学位论文网络入侵检测系统中模式匹配算法的 研究，是本人在华北电力大学攻读硕士学位期脚，在导师指导下进行的研究工作和取 得的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名踅链日期：趟， 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权保管、 并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手 段复制并保存学位论文；学校可允许学位论文被查阅或借阅：学校可以学术交流为 目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同媒体上发表、传播 学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定1 作者签名：塑垒垂导师签名：趁 日期：丝型；1 2 日期：峨，t ，哆 华北l h 力人学硕士学位论文 第一章引言 1 1 入侵检测在网络安全中的重要性 1 1 1 安全的意义 信息安全就是防止计算机上或网络传输中的信息被故意地或偶然地非授权泄 漏、更改、破坏或使信息被非法的系统识别或控制。它包括操作系统安全、数据库 安全、网络安全、病毒防护、访问控制、加密与鉴别七个方面，其目的就是实现数 据的保密性、完整性和有效性。其中，保密性( c o n f i d e n t i a l i t y ) 是指保护数据 不受非授权操作的破坏；完整性( i n t e g r i t y ) 是指保证非授权操作不能修改数据； 有效性( a v a i l a b i i i t y ) 是指保证非授权操作不能获得保护信息或计算机资源。 网络安全是信息安全的重要组成部分。随着信息时代的到来，计算机网络已经 成为现代社会生产、生活中不可或缺的一部分，并且已经成为2 1 世纪全球最重要的 基础设施。但与此同时，由于计算机网络固有的丌放性特点，使网络一丌始就面临 巨大的安全风险。而网络协议、各种协议、各种软件的不完善以及网络管理人员的 错误使这种风险成为现实的灾难，网络入侵事件不断发生，甚至政府网站被破坏、 军事机密被窃取的事件也时有发生。所有这些，都促使网络安全研究工作快速地向 前发展。 1 1 2 入侵检测在动态网络安全模型中的作用 目阿应用比较广泛的网络安全产品是防火墙，它在内部网络和外部网络之间建 立一道屏障，通过限制、过滤、监测、更改跨越防火墙的数据流来对外部网络屏蔽 被保护网的信息。其它的网络安全技术还有：安全路山器、数据加密、身份认证等， 但这些手段只是静态的安全技术，只能起到被动防御的作用，无法有效地保障网络 安全。 2 0 世纪9 0 年代起人们开始用动态的安全模型、方法、技术和解决方案来应对更 加复杂的安全问题。随着以入侵检测h 2 1 为代表的动态检测技术和产品的发展，动 态安全模型也相应的得到了发展，由i s s 公司提出的p 2 d r 模型就是这样的技术模型 的典型代表。 如图卜1 所示，p 2 d r 模型【3 】包含4 个部分的主要内容：安全策略( p o l i c y ) 、防 护( p r o t e c t i o n ) 、检测( d e t e c t i o n ) 和响应( r e s p o n s e ) 。 华北电力人学硕十学位论文 图i lp 2 d r 动态安全模型 p 2 d r 形成了一个完备的闭环自适应体系。它是在整体的安全策略的控制和指导 下，在综合运用防护工具( 如防火墙、加密、操作系统身份认证等手段) 进行网络 信息安全保护的同时，利用各种检测工具( 如入侵检测系统、漏洞评估系统等) 及 时了解和评估系统的安全状态，并通过适当地响应使系统调整到“最安全”和“风 险最低”的新的状态。外层的p d r 循环从图中看是一个平面的过程，但在实际的应 用中则是一个螺旋式上升的过程，经过一个循环之后，进行防护的水平显然是提高 的。 在这个模型中，入侵检测承接防护和响应，是静态防护转化为动态的关键，是 动念响应的依据，是p 2 d r 模型作为一个动态安全模型的关键所在。有了这样的动态 检测机制，就可以主动及时地发现信息系统中存在的安全问题，并且通过实时的响 应，来消除使系统处于不安全状态的问题。因此，入侵检测的研究对网络安全具有 十分重要的意义。 1 2 入侵检测及模式匹配算法的研究现状 1 2 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 ) 是在传统的安全筻略无 法满足同益苛刻的安全需求的情景下产生的，是动态安全技术的典型代表，它的出 现给计算机安全领域的研究带来了新的活力。从实验室原型研究到推出商业化产品 走向市场，入侵检测系统i d s 已经走过了2 0 多年的历程。 1 9 8 0 年4 月，j a m e sp a n d e r s o n 在为美国空军做的一份题为c o m p u t e r s e c u r i t yt h r e a tm o n i t o ra n ds u r v e i l l a n c e ) ) ( 计算机安全威胁监控与监视) 4 1 的 技术报告中，第一次详细阐述了入侵检测的概念，这份报告被公认为入侵检测的开 山之作。 从1 9 8 4 年到1 9 8 6 年，乔治敦大学的d o r o t h yd e n n i n g 【5 】和s r i c s l 公司计算 ， 华北电力人学硕f ：学位论文 机科学实验室的p e t e rn e u m n n n 研究出了一个实时的入侵检测系统模型 i d e s ( i n t r u s i o i ld e t e c t i o i le x p e r ts y s t e m s ：入侵检测专家系统) ，首次把入侵检 测的概念作为计算机系统安全防御问题的措施提出，入侵检测系统迅速发展起来。 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 ) ，第一次直接将网 络流作为审计数据来源，因而可以在不将审计数据转换成统一格式的情况下监控异 种主机，入侵检测系统的发展翻开了新的一页，两大阵营正式形成：基于网络的i d s 和基于主机的i d s 。 9 0 年代后，随着基于网络的入侵检测系统的问世，对入侵检测的研究也进入高 涨阶段，由早期的实验阶段进入了商业化，并且其他领域的一些方法也被人们引入 到了该领域，像神经网络、人工智能、数据挖掘、免疫学方法等。但是，这些方法 大多还处于试验研究阶段，实用性不高。模式匹配方法由于其检测原理简单易懂、 易于实现、准确率高、实时性好而备受青睐，并且技术已经相对成熟，在入侵检测 产品中得到广泛应用。掘公安部计算机信息系统安全产品质量监督检验中心的报 告，国内送检的入侵检测产品9 5 是属于使用入侵规则进行模式匹配的特征检测产 品，其他5 是采用概率统计的检测产品与基于同志的专家知识库产品。 当今社会网络同益普及，人们对网络的依赖性同趋增强，尤其是近年来网络以 令入难以置信的速度向前发展，网络技术同新月异，大型网络以及干兆以太网的出 现，使目前的网络入侵检测系统很难跟上网络快速发展的步伐，n i d s 面l | 缶严峻挑战： ( 1 )计算机网络向着高速、宽带的方向发展，对获得的数据包进行实时处理的难 度加大，大流量的网络环境使对入侵检测系统的检测能力的要求不断提高。( 2 ) 网 络攻击技术和手段的闩益多样化，为描述所有的攻击行为不得不增加入侵规则，使 得入侵检测规则库相当的庞大，网络入侵检测系统的检测负担极大的增加，报文处 理速率下降。 可见，对网络数据包进行检测的速度越来越成为制约网络入侵检测系统性能的 瓶颈。如果检测速度跟不上网络流量，就会丢包并发生显著的漏报问题，结果造成 对一些攻击行为不能及时识别并做出反应。因此，为数据包的攻击检测过程找到一 种快速有效的模式匹配算法是当前的网络入侵检测系统面临的个重要问题。 1 2 2 模式匹配算法的研究现状 自1 9 9 5 年s a n d e e pk u m a r 在他的博士论文6 1 中提出用模式匹配的方法检测入侵 以来，入侵检测系统中的模式匹配方法得到了长足的发展。最初采用的是朴素的模 式匹配算法b f ( b r u t ef o r c e ，b f 算法) ，这种算法对数据包的匹配效率相当的低， 于是人们希望将更有效的模式匹配算法应用于入侵检测。1 9 9 9 年入侵检测系统 华北l i 王力人学硕十学位论文 机科学实验聿的p e t e rn e u m a n n 研究出了一个实时的入侵检测系统模型 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 a t ：e m s ：入侵检测专家系统) ，首次把入侵检 测的概念作为计算机系统安全防御问题的措施提出，入侵检测系统迅速发展起来。 1 9 9 0 年是入侵检测系统发展史上的一个分水岭。这一年，加州大学戴维斯分校 的l 1 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 ) ，第一次直接将网 络流作为审计数据来源，因而可以在小将审计数据转换成统一格式的情况下监控异 种主机，入侵检测系统的发展翻，i ：了新的一页，两大阵营j 下式形成：基于网络的i d 5 和基于主机的i d s 。 9 0 年代后，随着基于网络的入侵检测系统的问世，对入侵检测的研究也进入高 涨阶段，由早期的实验阶段进入了商业化，并且其他领域的一些方法也被人们引入 到了该领域，像神经网络、人工智能、数据挖掘、免疫学方法等。但是，这些方法 大多还处于试验石j f 究阶段，实用性不高。模式匹配方法由丁| 其检测原理简单易懂、 易于实现、准确率高、实时性好而备受青睐，并且技术已经相对成熟，在入侵检测 产品中得到广泛应用。据公安郁计算机信息系统安全产品质量监督检验中心的报 告，国内送检的入侵检测产品9 5 是属于使用入侵规则进行模式匹配的特征检测产 品，其他5 是采用概率统计的检测产品与基于r 志的专家知识库产品。 当令社会网络同益普及，人们对网络的依赖性同趋增强，尤其是近年来网络以 令人难以置信的速度向前发展，网络技术f | 新月异，大型网络以及千兆以太网的出 现，使目前的网络入侵检测系统很难跟上网络快速发展的步伐，n i d $ 面临严峻挑战： ( 1 )计算机网络向着高速、宽带的方向发展，对获得的数掘包进行实时处理的难 度加大，大流量的网络环境使对入侵检测系统的检测能力的要求不断提高。( 2 ) 刚 络攻击技术和手段的n 盏多样化，为拙述所有的攻击行为不得不增加入侵规则，使 得入侵检测规则库相当的庞人，网络入侵检测系统的检测负担极大的增加，报文处 理速率下降。 可见，对网络数据包进行检测的速度越来越成为制约网络入侵检测系统性能的 瓶颈。如果检测速度跟不上网络流量，就会丢包并发生显著的漏报题，结果造成 对一些攻击行为不能及时识别并做出反应。因此，为数据包的攻击检测过程找到一 种快速有效的模式匹配算法是当前的嘲络入侵检测系统面临的一个重要问题。 1 22 模式匹配算法的研究现状 自】9 9 5 年s a n d e e pk u m f d r 在他的博 二论文6 1 中提 _ j 用模式匹配的方法检测入侵 蛆来，入侵检测系统中的模式匹配方法得到了长足的发展。最初采用的是朴素的模 式匹配算法b f ( b r u t ef o r c e ，b f 算法) ，这种算法对数据包的匹配效率相当的低， 于是人们希啦将更有效的模式匹配算法应用于入侵检测。1 9 9 9 年八侵检测系统 于是人们希挚将更有效的模式匹配算法应用于入侵检测。1 9 9 9 年入侵检测系统 3 华北电力人学硕十学位论文 s n o r t 引入了b m ( b o y e r m o o r e ，b m ) 算法i ”i s l ，使检测效率有了巨大的改善，此后 入侵检测产品大都采用b m 算法或基于它的改进算法如b m h ( b o y e r m o o r e h o r s p o o l ， b m h ) 1 9 ，o s ( q u i e ks e a r c h ，q s ) 算法1 1 0 j 等，这些单模式匹配算法适应了当时简单 的网络环境要求。 随着现代网络由i o m 升级到1 0 0 m 甚至是1 0 0 0 m 网络，网络技术的进一步发展又导 致入侵检测规则库的日益庞大，模式匹配算法再次成为了入侵检测的发展瓶颈。多 模式匹配算法扫描一次数据包就可以完成对多个规则模式的匹配，在规则数量大时 检测比较快，2 0 0 1 年之后入侵检测也就开始引入了多模式匹配算法。多模式匹配算 法因为有着较好的时间效率，有很高的发展前景和应用价值，是入侵检测模式匹配 算法的主要研究方向。主要运用的多模式匹配算法有： a c ( a h o - c o r a s i c k ，a c ) 算法1 基于有限状态自动机( d e t e r m in i s t i cf i n i t e s t a t ea u t o m a t a ，d f s a ) ，采用一种有限自动机把所有的模式串构成一个集合，可 以在只对文本进行一次扫描的情况下查找多个模式，是最经典的多模式匹配算法。 w m ( w u m a b e r ，w m ) 算法 1 2 l ，采用了三个哈希表来控制模式的跳转，也可以很 好地进行多模式匹配。它内存资源消耗相对较小，但匹配速度比a c 算法略差l i 。 c w ( c o m m e n t z w a t e y ，c w ) 算法【”j 、s b m h ( s e t w is eb o y e r m o o r e h o r s p 0 0 1 ，s b m h ) 算法【”1 以及f s 算法u 6 i 等也被运用于入侵检测，但是效果都不太理想。 直n c j a s o nc o i t ，s t u a r ts t a n i f o r d 平l j j o s e p hm c a l e r n e y 提出了a c b m 算法l l7 1 ， 该算法在a c 算法的匹配自动机基础上结合了b m 算法，入侵检测系统的检测速度得到 了较大的提高。 目前，国外方面还有以sa n t o n a t o s ，m i k ef i s k 等为主要代表的个人、研究组织 积极展开对模式匹配算法的研究 1 8 1 一【2 1 j 。国内也加紧了这方面的研究，如上海交通 大学的王永成【2 2 1 2 3 1 ，清华大学的宋华1 2 ”，以及其它一些高校如河北大学、西北工业 大学、哈尔滨工业大学、南京师范大学等1 2 5 1 - 28 1 。 从查阅的相关资料、文献可以看到，目前针对入侵检测的模式匹配算法的研究 一部分还停留在单模式匹配算法，而对多模式匹配算法的研究主要集中在算法的综 述、测试以及对现有算法的一些相应改进上。这些改进的算法虽然也取得一定的成 果，但是总体效果都不是很理想，主要是算法速度受限于入侵规则数目或者实现算 法需要的空间消耗太大，用于入侵检测系统实用性不强。同时也可以看到，提出一 个全新的模式匹配算法难度较大，因此，自采用多模式匹配算法进行检测以来，入 侵检测产品引入的多模式匹配算法并没有发生太大的变化，主要的算法仍然继续沿 用，比如著名的源代码开放的s n o r t ”】入侵检测系统采用了a c 或w m 算法；e a s y g u a r d 入侵防护系统采用w m 算法【3 0 】：北京启明星辰公司的天阗入侵检测产品 3 1 1 和联想网御 4 华匕电力大学硕士学位论文 的检测系列产品瞰】采用a c b m 算法等。 本文根据高速网络环境的实时检测要求对入侵检测中的模式匹配算法进仃了 研究。b m 算法是种高效的单模式匹配算法：而a c 算法是经典的多模式匹配算法， 并且后来的一些多模式匹配算法如a c b m 算法都是在a c 算法的基础上改进的，因 此本文主要讨论了单模式的b m 算法、多模式的a c 算法和a cb m 算法，在此基础 提山基fa c 算法的一种改进，提高网络入侵检测系统的检测速度。 1 23 入侵检测的发展趋势 作为一项动念安全技术，i d s 正在成为网络安全的热点研究领域。但是i d s 仍 然是一个很年轻的研究领域，它的理论研究和实际应用还有许多问题有待研究与探 索。具体来院，入侵检测有这样的发展趋势3 3 j 1 3 4 1 ： l 、宽带高速刚络的实时入侵检测 随着各种宽带技术和网络技术的飞快发展，如何实现高速例络下的实时入侵检 测已成为一个很现实的问题。目前人们开始研究基于千兆以太嘲的入侵检测产品， 但是性能指标还不成熟。为此，入侵检测系统的软件结构和算法需要重新设计，以 适应高速网络的新环境，重点是提高运行速度和效率。 2 、分们式入侵检测 传统的集中式的i d s 一般局限于单一主机或网络的结构，在网络的1 j 州嘲段放 置多个传感器或探测器用来收集当前网络的状态信息，然后将这些信息、传到中央控 制台进行处理和分析。异构网络环境带来的平台差异性，网络传输带来的延时问题， 大规模网络带来的大量检测负荷都使集中式入侵检测带来诸多困难。同时，网络攻 击手段向分布式方向发展( 如分布式d o s 攻击) ，其破坏性和隐蔽性也越来越人， 冈此有必要研究分布式的入侵检测系统体系结构。 3 、智能化入侵检测 入侵方法越来越多样化和综合化，这使得入侵检测系统不得不提升自身的智能 化。尽管已经有了数据挖掘、神经网络与遗传算法等技术在入侵检测领域的应用研 究，但这还只是一些尝试性的研究j 作，真正要达到实用阶段还有很长的路要走。 4 、与其它网络安全技术相结合 网络的安全现状使得技术融合变得越来越重要，单一的技术很难构筑道强有 力的安仝防线，这就需要1 d s 和其他安全技术共同组成更完备的安全保障系统，如 结合防火墙、p k i p m i 、安全电子交易s e t 等新的网络安全技术，提供完整的网络安 全保障。 华北电力人学硕一f ：学位论文 1 3 论文内容安排 第一章主要是研究的背景和意义，介绍了入侵检测和模式匹配算法的研究现状 以及本文的内容安排。 第二章介绍了入侵检测领域的相关概念、入侵检测系统的基本结构以及入侵检 测系统从不同角度的划分。 第三章详细介绍模式匹配原理，入侵规则的描述方式以及基于模式匹配的网络 入侵检测系统的结构，并分析了模式匹配检测方法面临的问题以及它的主要特点。 第四章首先详细介绍了网络入侵检测系统中常用的几种模式匹配算法，包括单 模式的b m 算法、多模式的a c 算法和a cb m 算法，分析了它们的匹配原理，在此基 础上提出了一种基于a c 的改进算法m a c ( m y - - a c ) 算法，并综合讨论了各个算法的 时间复杂度和空间复杂度。 第五章是匹配算法的测试实验及结果。采用两种测试方案：文本测试和网络数 据包检测。文本测试采用的是随机的文本和模式：网络数据检测实现一个简单的入 侵检测系统，对真实的网络数据进行了检测，并分析了实验结果。 第六章对本文进行了总结，提出了进一步的研究方向。 6 华北电力人学颐十学位论文 2 1 相关概念 第二章入侵检测系统概述 入侵( i n t r u s i o n ) 是指有关试图破坏资源的完整性、机密性及可用性的活动 的集台【3 5 l ，入侵违背了系统安全策略。从入侵策略的角度来看，入侵包括尝试性闯 入、伪装攻击、安全控制系统渗透、泄漏、拒绝服务攻击、恶意使用6 种类型。 入侵检测( i n t r u s i o nd e t e c t i o n ) 是指“通过对行为、安全f 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 ) 是入侵检测的具体实现， 可定义为检测企图破坏计算机资源的完整性、机密性和可用性的行为的软件和硬件 的组合。入侵检测系统对系统进行实时监控，获取系统的网络数据包或者审计数据， 然后将得到的数据进行分析，并判断系统或者网络是否出现异常或入侵行为。一旦 发现异常或入侵情况，就发出警报并采取相应的保护措施。 个入侵检测系统应当具有以下功能：监视用户和系统的运行状况，发现用户 的越权操作；检测系统配置的j 下确性和安全漏洞，弗提示管理员修补漏洞；对用户 非正常活动的统计分析，发现行为规律；检测系统程序和数据的一致性及正确性； 能够即使检测到攻击行为，并进行反应；操作系统的审计跟踪管理。 2 ，2 入侵检测系统的基本结构 入侵检测是监测计算机网络和系统以发现违反安全策略事件的过程。简单的说 入侵检测系统包括三个基本的功能部件。 在图2 - 1 中给出了一个通用的入侵检测系统的结构。 图2 - 1 入侵检测系统的基本结构 7 华北电力入学硕十学位论文 入侵检测的第一步是数据采集，而数据采集模块的作用在于为系统提供数据。 数据的来源可以是主机上的f = 1 志和变动信息，也可以是网络上的数据信息，甚至是 流量变化等，这些都可以作为数据源。数据采集模块在获得数据之后，需要对数据 进行简单的处理，如简单的过滤、数据格式的标准化等，然后将经过处理的数据提 交给数据分析模块。 数据分析模块的作用在于对数据进行深入地分析，发现攻击并根据分析的结果 产生事件，传递给结果处理模块。数据分析的方式多种多样，可以简单到对某种行 为的计数( 如一定时间内某个特定用户登陆失败的次数，或者某种特定类型报文的 出现次数) ，也可以是一个复杂的专家系统。该模块是一个入侵检测系统的核心， 平时所说的入侵检测方法就是指数掘分析的方法。本文中采用的数据分析方法是模 式匹配方法。 结果处理模块的作用在于告警与响应，这实际上与p 2 d r 模型的r 有所重叠。 从非技术角度说，结果处理模块的告警是通知管理员，而r 的作用在于产生一个f 式的告警，作为单位个体正式的安全事件进行处理；从技术角度来说，两者的功能 很难划分，也可以将入侵检测的结果反应功能归结为r 的一部分。 2 3 入侵检测系统的分类 2 3 1 按照检测数据源的分类 根据入侵检测系统检测的数据来源，它可以分为：基于主机的入侵检测系统、 基于网络的入侵检测系统和分布式入侵检测系统【2 j 。 l 、基于主机的入侵检测系统 基于主机的入侵检测系统( h o s t b a s e di d s ，简称t t l d s ) ，通常是安装在重点 检测的主机上，保护所在的主机系统。如果其中主体活动十分可疑，入侵检测系统 就会采取相应的措施。h i d s 通过对系统审计同志和操作系统进程进行分析来检测入 侵，这类入侵检测系统的数据主要来自于系统的同志记录、进程信息、文件目录信 息、安全配置文件、系统调用信息等。这些数据中包含了重要的有关用户的权限、 允许的操作、占用的资源等关键信息。 h i d s 的主要优势有：适用于加密和交换环境；近实时的检测和应答；不需要额 外的硬件。其缺点是系统负担大，对操作系统的依赖大。 2 、基于网络的入侵检测系统 基于网络的入侵检测系统( n e t w o r k b a s e di d s ，简称n i d s ) ，以原始的网络 数据包作为数据源，并分析其是否存在己知的攻击模式或将引起网络系统异常，以 此来判断是否为入侵。一旦发现该网段上发生网络入侵，则实时报警或者阻断有害 华北l 乜力人学硕十学位论文 的网络连接。 n i d s 的优点是实时的检测和响应；检测速度快：能够检测到未成功的攻击企图： 攻击者不易转移证据：操作系统无关性：占用主机资源少。缺点是只能监视经过本 网段的活动，且精确度较差，在交换网络环境下难于配置，防欺骗能力也比较差， 对加密环境无能为力。 3 、分布式的入侵检测系统( d i s t r i b u t e di d s ，简称d i d s ) h i d s 和n i d s 两者各自都有自身独特的优势，在某些方面是很好的互补，而单 纯使用一类系统并不能形成完整而全面的主动防御体系。因此综合了以上两种方式 的优点而形成的一种新的入侵检测系统，这种入侵检测系统能够同时分析来自主机 系统审计同志和网络的流量数据信息，一般为分布式结构，由多个部件组成。 分布式的i d s 将是今后人们研究的重点，它是一种相对完善的体系结构，为f 1 趋复杂的网络环境下的安全策略的实现提供了最佳的解决对策。 23 2 按照检测方法的分类 检测方法也可以称为数据分折方法，根据检测方法的不同，入侵检测可分为异 常检测和误用检测【2 l 。前者主要采用统计分析的方法，后者主要采用规则匹配的方 法。 l 、异常检测( a n o m a l yd e t e c t i o n ) 检测与可接受行为之间的偏差。如果可以定义每项可接受的行为，那么每项不 可接受的行为就应该是入侵。异常检测首先收集一段时期正常操作活动的历史数 据，总结f 常操作应该具有的特征，建立代表用户、主机等正常行为轮廓，然后收 集事件数据并使用各种方法来判断它与可接受行为模型之间的偏差。当用户活动与 该难常行为有重大偏离时即被认为是入侵。 异常检测的方法有阈值检测、统计方法等，还有神经网络等一些新技术。从它 的实现机理来看，异常检测面临的技术难点在于：“j 下常”行为特征轮廓的确定及 更新；特征量的选取：比较阈值的选定；比较频率的选取。由于这几个因素的制约， 异常检测的误警率会很高，但对于未知的入侵行为的检测非常有效。此外，由于需 要实时地建立和更新系统或用户的特征轮廓，所需的计算量很大，对系统的处理性 能要求会很高。 2 、误用检测( m i s u s ed e t e c t i o n ) 检测与己知的不可接受行为之间的匹配。如果可以定义所有的不可接受行为， 那么每种能够与之匹配的行为都可以认为是入侵。误用检测首先收集违背安全策略 事件的行为特征，用一定的方法对该行为进行描述，建立相关的特征库，在检测时 9 华北电力人学硕士学位论文 判别当前搜集到的数据特征是否在入侵模式库中出现。当监测的用户或系统行为与 库中的记录相匹配时，系统就认为这种行为是入侵。 误用检测的关键是如何表述入侵的模式，把真正的入侵与正常行为区分开来以 及怎样快速的检测是否有匹配发生。误用检测的优点是误报率低，对于已知的攻击， 它可以详细、准确地报告出攻击类型。局限是它只能发现已知的攻击，对未知的攻 击无能为力，而且特征库必须不断更新。 2 3 3 其它的分类方法 按工作方式的不同入侵检测系统还可以分为：离线入侵检测系统和在线入侵检 测系统。离线入侵检测系统在事后分析审计事件，从中检查入侵活动，是种非实 时工作的系统。优点是漏报率低，缺点是不能实时的产生告警。在线入侵检测系统 是实时联机的检测系统，包含对实时网络数据包分析和实时主机审计分析。优点是 可以产生实时告警，缺点是网络数据流量大时可能因丢失数据包而产生漏报。 按照系统检测频率可以分为实时连续入侵检测系统和周期性入侵检测系统；按 照系统的对抗措施还分为主动系统和被动系统。 当然，以上各种分类方法并不相交，一个入侵检测系统可能同时属于某几类。 2 4 本章小结 本章首先介绍了入侵检测领域的相关概念：入侵、入侵检测和入侵检测系统以 及入侵检测系统的主要功能；其次给出了入侵检测系统的基本结构，对系统的数据 采集、数据分析和数据处理三个主要功能模块进行了分析；最后主要从入侵检测系 统的数据源和检测方法对其进行分类：按照数据源的不同，入侵检测系统可以分为 基于主机的入侵检测系统、基于网络的入侵检测系统和分布式入侵检测系统；按照 检测方法的不同，入侵检测系统又可以分为基于异常检测的入侵检测系统和基于误 用检测的入侵检测系统。分析了各类入侵检测系统的优缺点。 1 0 华北电力人学硕士学位论文 第三章模式匹配及其在网络入侵检测中的运用 3 1 模式匹配原理 字符串模式匹配算法一直是计算机领域的研究重点之一，在拼写检查、语言翻 译、搜索引擎、数据压缩、网络入侵检测、计算机病毒特征码匹配以及d n a 序列匹 配等应用中，都需要进行字符串模式匹配。 模式匹配算法在入侵检测中可以描述为：给定入侵规则库中一个特定的模式字 符串p ，在网络数据报文t 中进行查找，以确定p 是否在t 中出现。基于模式匹配 检测方法的入侵检测系统是由k u m a r 在1 9 9 5 年提出的，目前模式匹配已经成为入 侵检测领域中最广泛的检测手段和机制。 k u m a r 提出了入侵信号的层次性概念 6 1 。根据底层的审计事件，可以从中提取 出高层的事件或活动；由高层的事件构成入侵信号，并依照高层事件之间的结构关 系，划分入侵信号的抽象层次并对其分类。如果对构成信号的事件按照审计进行精 确的定义，就可以从抽象的层次实例化中得到具体的层次结构。实例化的层次结构 意味着对于层次结构中的每一层而言，都可以对该层中匹配信号的复杂性边界进行 划分( 至少理论上可以如此) 。 k u m a r 把入侵信号分为四个层次，每一个层次对应相应的匹配模式，具体如下： 1 、存在( g x is t e n c e ) 这种入侵信号表示只要存在这样一种审计事件就足以说明发生了入侵行为或 入侵企图，它所对应的匹配模式称为存在模式( g x is t e n c ep a t t e r n ) 。存在模式可 以理解为在一个固定的时间对系统的某些状态进行检查，并对系统的状态进行判 定，比如查找某个特定文件的存在、文件内容格式是否符合规则等。存在模式是很 重要的，尤其是当攻击者破坏了系统的审计数搌，导致提交的审计数据无法正常反 映当前真实状态的时候，通过主动的查询可以起到很好的作用。 2 、序列( s e q u e n c e ) 有些入侵是由一些按照一定顺序发生的行为所组成的，它具体可以表现为一组 事件的序列。其对应的匹配模式就是序列模式( s e q u e n c ep a t t e r n ) ，这种入侵的 审计事件可以表示为在某个方向一连串连续的峰值。 3 、规则表示( r e g u l a rg x p r e s s i o n s ) 规则表示模式( r ep a t t e r n ) 是指用一种扩展的规则表示方式构造模式，规则 表示式是由用a n d 逻辑表达式连接一些描述事件的原语构成的。适用这种模式的攻 击信号通常有些相关的活动所组成，而这些活动间没有什么事件顺序的关系。 1 1 华北电力人学硕士学位论文 4 、其它模式( o t h e r sp a t t e r n ) 其它模式( o t h e rp a t t e r n ) 是指一些不能用前面的方法表示的攻击，包括内 部否定模式、归纳选择模式。 但是在具体的实现中，往往很难实现对所有的入侵信号进行模式匹配，一般只 是部分实现。例如s n o r t ，它主要用存在模式表示入侵信号。模式匹配方法基本上 是查找网络包中的这种模式。 3 2 检测规则 基于模式匹配的入侵检测的两个主要问题是：如何描述入侵行为以及使用什么 算法来快速检测入侵行为。 每个基于模式匹配的入侵检测方法都需要一种已定的入侵模式，这就需要有 一种对入侵行为的描述方法。现在的各个入侵检测系统中的描述方法各有不同，每 个产商定义自己的描述方法，每种方法各有长短。描述方法的不一致使得用户只能 够依赖于丌发商来升级入侵检测模式库。 s n o r t 是一个开放源代码的轻量级的基于网络的入侵检测系统，它的入侵行为 的描述方法简单灵活，易于实现，具有很强的描述性，能够拙述绝大多数的入侵行 为。下面介绍它的入侵规则描述方法： 每条规则在逻辑上分为两部分：规则头( r u l e rh e a d ) 和规则选项( r u l e r o p t i o n ) 。规则头定义了规则的行为操作、所匹配网络报文的协议、源j p 地址、目 标i p 地址及其网络掩码和端口等信息。规则选项包含了所要显示给用户查看的报 警信息及用来判断此报文是否为攻击报文的检测信息。 以f 是一个例子：a l e r tt c p a n ya n y 一 1 9 2 1 6 8 1 0 2 4 】ll ( c o n t e nl ：“lo o 0 l8 6a 5 i ”：m s g ：m o u n t da c c e s s ”：) 它描述了：任何使用t c p 协议连接网络1 9 2 1 6 8 1 0 2 4 中任何主机的1 i l 端 口的数据包中，如果出现了二进制数据0 0o l8 6a 5 ，便发出警告信息m o u n t d a c c e s s 。 在圆括号前的部分是规则头部，规则头的第一项是规则操作，规则操作说明当 发现适合条件的数据包时应该做些什么。规则头部的第二部分是协议。规则头部的 第三部分是i p 地址和端口。规则头部包含了定义数据包“从哪早来，到什么地方 去，干什么”以及发现满足这个规则所有条件的数据包时应该干什么的信息。 在圆括号中的部分是规则选项。规则选项定义了攻击数据包的特定特征，它形 成了检测系统的核心，功能强大，具有易用性和灵活性，入侵检测系统根据规则选 项检查网络数据包。一个规则的规则选项中可能有多个选项，不同选项之间使用“；” 华北l u 力人学硕十学位论文 分隔开来，它们之间为“与”的关系。选项由关键字和参数组成，每个关键字和它 的参数使用冒号“：”分隔。其中主要的关键字有： m s g 一在警报信号和数据包闩志中显示的消息。 l o g t o 一将数据包记录到用户指定的文件中。 t t l 一检测i p 数据包的t t l 字段值。 i d 一检测i p 数据包的分段i d 值是否等于指定值。 d s iz e 一检测数据包的有效载荷段大小是否等于指定值。 c o n t e n t 一在数据包的有效荷载中搜索指定模式。 n o c a s e 在进行字彳啻串模式匹配时，不区分大小写。 3 3 基于模式匹配的n l d s 的结构 网络入侵检测可以分为数据包的捕获、数据包的预处理以及对数据包进行攻击 检测的过程，其结构如图3 一l 所示。 幽3 - 1 基十模式匹配的网络入侵榆测系统的结构图 网络入侵检测是以网络中的数据包为数掘源，通过对网络包的直接检测发现整 个网络内可能存在的攻击的一种入侵检测方式。数据包的攻击检测就是在要在网络 数据包中检测是否存在可以代表攻击的一些字符串，也就是查找出描述攻击特征的 入侵规则中规则选项c o n t e n t 中所标识的字符串。这是入侵检测中时闻消耗最大过 程之一，如果没有高效的模式匹配算法，那么系统就会发生丢包，产生漏报。 3 4 模式匹配方法在实现中的问题 模式匹配方法在入侵检测的具体应用中需要解决以下一些问题： l 、模式的提取：要使提取的模式具有很高的质量，能够充分表现入侵信号的 特征，同时模式之间不能有冲突。 1 3 华北电力人学硕十学位论文 2 、模式匹配的动态增加和删除：为了适用不断变化的攻击手段，匹配模式必 须具有动念变更的能力。 3 、增量匹配和优先级匹配：在事件流对系统处理能力产生很大压力的时候， 要求系统采取增量匹配的方法来提高系统效率，或者可以先对高优先级的事件先行 处理，暂缓对低优先级事件的处理。 4 、完全匹配：匹配机制必须能够提供对所有模式匹配进行匹配的能力。 3 5 模式匹配检测方法的特点 8 5 1 模式匹配的优点 l 、原理简单，易于实现 模式匹配思想简明清晰，经过多年的研究，技术已经非常成熟。这种方法将数 据包捕获和规则剖析分离，因此在检测引擎中实现比较容易。 2 、误警率低 采用模式匹配，根据具体规则库中精确的模式来判断入侵，不需要学习过程， 相对于基于统计学的异常入侵检测系统而占，误警率要低的多。 3 、扩展性好 每当新的攻击手段出现，基于模式匹配的入侵检测系统无需作大的改动，只需 要对新的攻击编写相应的规则，在规则库中添加即可。 4 、报警明确 由于入侵