（计算机应用技术专业论文）基于序列模式挖掘的入侵检测研究及应用.pdf

摘要近年来，随着网络数据流量不断增大，与数据挖掘相结合的入侵检测系统成为了研究热点。如何将数据挖掘算法有效地结合到入侵检测系统中，是入侵检测研究要解决的问题之一。目前基于数据挖掘的入侵检测系统的算法研究主要有以下四个方面：关联分析算法，可以挖掘出记录中不同属性之间的关联关系，利用训练数据中各属性之间的关系形成关联规则；序列分析算法，可以发现审计数据中一些经常以某种规律出现的事件序列模式；分类分析算法，可以用来预测新的审计数据属于正常还是异常；聚类分析算法，可以直接将未知的网络数据聚成不同的类。本文对序列模式挖掘及其在入侵检测系统中的应用进行了研究，展开了以下工作：分析了入侵检测系统的研究现状和面临的主要问题，研究了数据挖掘技术应用到入侵检测中的优势，分析了当前基于数据挖掘的入侵检测系统中存在的不足；研究了序列模式挖掘算法，针对目前基于数据挖掘的入侵检测时空效率不高的问题，对序列模式挖掘算法进行了改进；研究了基于序列模式挖掘的入侵检测系统模型，将改进的p r e f i x s p a n 算法应用于该模型。仿真试验结果表明，改进后的p r e f i x s p a n 算法时空效率得到了改善，同时减少了规则的数量，提高了规则的有用性。关键词：入侵检测；数据挖掘；序列模式挖掘；p r e f i x s p a n 算法a b s t r a c tr e c e m l y ，w i t ht h ei n c r e a s i n gn e t w o r kf l u x ，t h ei n t n l s i o nd e t e c t i o ns y s t e mb a s e do nd a t am i n i n gt e c h n i q u eh a sb e e nr e s e a r c h e dw i d e l y h o wt oi m e g r a t ee 行b c t i v e l yd a t am i n i n ga l g o r i t h m si m oi n t r u s i o nd e t e c t i o ns y s t e mi s0 n eo ft h ep r o b l e m st ob es o l v e df o ri n t n l s i o nd e t e c t i o nt e c h n i q u e a tp r e s e n t ，r e s e a r c ho nt h ea l g o r i t h mi ni n t m s i o nd e t e c t i o nb a s e do nd a t am i n i n gt e c h n i q u ei sm a i n l yf o c u s e do nf o u ra s p e c t s ：a p p i y i n ga s s o c i a t i o na n a l y s i sa l g o r i t h mt om i n e1 1 j l e sa m o n gd i f r e r e n ta n r i b u t e so fr e c o r d s ，a p p l y i n gs e q u e n c ea n a l y s i 8a l g o r i t h mt of i n do u tt h es e q u e n t i a lp 砒t e r n sa m o n gd i f f e r e n tr e c o r d s ，a p p l y i n gc l a s s i f i c a t i o na n a i y s i sa l g o r i t h mt of o m c a s tw h e t h e rn o r m a lo ra b n o r m a ln e w 如d “f e c o r d sa r e a n da p p l y i n gc l u s t e r i n ga l g o r i t h mt og e tt h ew a n t e dc l u s t e r sf o rn e wn e t w o r kd a t a t h ew r i t e ra i m sa tt h er e s e a r c ho fs e q u e m i a lp a t t e mm i n i n ga l g o r i t h mt h a tf i t sj n t oi d s ( i n t n i s j o nd e t e c t i o ns y s t e m ) a n d 埘a k e st h ew o r ka sf 0 】l o w i n g ：a n a l y z i n gt h el a t e s tr e s e a r c hp r o g f e s s 孤dm a i np r o b l e m se x i s t e do fi d s ，m s e a r c h i n ga d v a n t a g eo fd a t am i n i n gt e c h n i q u ea p p l i e dt oi d s ，a n da n a l y z i n gd i s a d v a n t a g eo fi d sb a s e do nd a t am i n i n gt e c h n i q u e r e s e a r c h i n gs e q u e m i a lp a t t e mm i n i n ga 1 9 0 r i t h md e e p i y ，a n di m p r o v i n gas e q u e m i a lp a t t e mm i n i n ga l g o r i t h m r e s e a r c h i n ga 行a m e w o r ko fi d sb a s e do ns e q u e n t i a lp a t t e r nm i n i n g ，t h e na p p l y i n gt h ep m f i x s p 柚a l g o r i t h mi nt h i sm o d e l f i n a l l ys o m ee x p e r i m e n t sh a sb e e np e r f o r m e d ，柚dt h ee x p e r i m e n t a lr e s u l t ss h o wt h ei m p r o v e dp r e f i x s p a na l g o r i t h mi m p r o v et h et i m ea n ds p a c ee a i c i e n c ya n dd e c r e a s et h en u m b e ro fn l l ea n dh e i g h t e nt h ea v a i l a b i l i t yo f 邝l e k e yw o r d s ：i n t m s i o nd e t e c t i o n ；d a t am i n i n g ；s e q u e m i a lp 砒t e r nm i n i n g ；p f e f i x s p a na l g o r i t h m长沙理工大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子舨，允许论文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于l 、保密口，在年解密后适用本授权书。2 、不保密团。( 请在以上相应方框内打“”)作者签名：日期：年月日导师张七日易钟吼7 年r 月矽日第一章概述i 1 论文的研究背景及意义信息社会的豺来，给全球带来了技术和经济飞速发展的契机但是，麓着隧络技术在世界及中国各个领域应用的深入开展。人们在进行资源共享的同时。也感受翻信息安全问题的扫益突出辔予计算机系统中硬件设备、操作系统，应用软件不可避免地会存在一些安全漏洞，丽且i m e 嘲t 自身协议和结构的初始设计也存在一些缺陷，所有这些都使“黑客。侵犯和操缴一些重要信息和数据成为可能计算机紧急情况响应组( c o m 叫e r e 融e 唱e n c y 狲亭p 蚰彬r e 珊c e r t 的统计数字显示：随着互联网的发展，安全事件数量不断上舞尤其是近两三年出现了成倍增长的急剧上升趋势。关于网络安全甸题目前存在许多专仃技术，如口令认证、安全审计、舫火墙、加密技术等等，总的来说这些技术都属于一种静态的防御系统，如同建立了一个有各种防卫措施的银行，而没有配置警察等监控系统一样。对于没有一个主动监控和跟踪入侵的入侵检测系统，这样的网络其安全性是不完整的。入侵检测技术是继。防火墙”，。数据加密。等传统安全保护措施后新一代的安全保障技术，它是一种积极主动的安全防御技术“1 目前，入侵检潞( i m i 飞l s 妇ld e t e c t i o n ，l d ) 即通过对计算机网络或计算机系统中的若干关键点收集信息并对其进行分析，从而发现网络或系统中是否有违反安全策略的行为和被攻击的迹象。进行入侵检测的软件与硬件的组合便是入侵检测系统( 孙咖s i 蚰d e t e c i i o ns y 蚍喇，d s ) 入侵检测技术实质上归结为对安全审计数据的处理这种处理可以针对鼹络数据。也可以针对主机的审计记录或应用程序的日志文件然而，随着操作系统的日益复杂化和网络数据流量的急刷膨胀，导致了安垒审计数据以惊人的速度递增激增的数据背后稳藏着许多重要的信息。入们希望能够对其进行更高抽象层次的分析，似便更好地利用这些数据数据挖掘本身是一项通用的知识发现技术，其目的是要从海量数据中提取出潜在的、有价值的知识( 模型或规则) 数据挖掘技术按其动能可划分为。关联规则分析、，序列模式分析、分类分祈，聚类分析等”数据挖掘技术在国外各个领域都已经得到了广泛的应用将数据挖掘技术应用于入侵检测系统中能够广泛收集审计数据，并在此基础上计算模型，从而精确地捕获实际的入侵和正常行为模式这种自动化的方法无需再手工分析和编码入侵模式，在创建正常使用轮廓畦也不褥像以前那样需要凭经验来选择统计方法箍且相同的数据挖掘工具可应用于多个数据流。这些优势都有利于创建自适应的入侵检测系统随着入侵手段的不断提高，许多入侵行为依赖于事件的发生顺序。当入侵一台服务器或主机时，入侵者往往按照某种顺序实施一系列的攻击步骤，其中任何单独的一条报文或者命令都是正常的，没有明显的字符串攻击特征，但一系列按时间顺序排列的报文或者命令就构成一次攻击。因此，在这种情况下，基于关联规则等数据挖掘算法就显得力不从心了。序列模式挖掘算法克服了关联规则等算法中不能反映事件在时间顺序上的前后相关性的缺点，可以检测出以往入侵检测方法很难检测到的序列攻击，从而提高检测率。r a g r a w a l 等人首先提出的序列模式挖掘算法分别为a p r i o f i a l l 、a p r i o “s o m e和d y n a m i c s o m e 此后又提出了g s p ( g e n e r a l i z e ds e q u e n t i a lp a t t e r n s ) 算法加入分类法、滑动窗口以及时间限制等，使得挖掘得到的信息更为有效。接着，序列模式挖掘又被广泛地研究”“”1 。本文针对目前序列模式挖掘在入侵检测中的应用研究中存在的不足，提出了改进的p r e f i x s p a n ( p r e f i x p r o j e c ts e q u e n t i a lp a t t e r nm i n i n g ) 算法，并将其应用于入侵检测中，因此具有一定的研究意义。本文的研究上具有如下重要意义：( 1 ) 序列模式挖掘和入侵检测两种技术的有效结合，为序列模式挖掘技术提供了更宽广应用的同时，也将极大地推动序列模式挖掘技术和入侵检测技术本身的研究。( 2 ) 入侵检测对维护国家主权和保护人民的财产安全具有极其重要的作用。( 3 ) 目前数据挖掘在入侵检测中的应用已经有了广泛的研究，但是，总体上处于初级阶段，大部分工作都着重于理论探讨和实验阶段。因此，本论文的研究对数据挖掘技术的发展具有一定的促进作用。( 4 ) 网络安全是计算机科学的一个重要分支，这一领域的任何突破都将推动整个计算机科学的发展。1 2 国内外研究现状国外对入侵检测的研究最早可以追溯到2 0 世纪8 0 年代，1 9 8 0 年，j a m e sa 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 “n ga n ds u r v e i l l a n c e 报告中首先详细阐述了入侵检测的概念，将入侵尝试或威胁定义为：潜在的有预谋未经授权访问信息、操作信息，致使系统不可靠或无法使用的企图”l 。同时，a l i d e r s o n 还提出了利用审计数据监视入侵活动的思想。1 9 8 7 年，d e n n i n g 的“a ni n t m s i o nd e t e c t i o nm o d e i ”论文可以称为入侵检测模型研究的开创性工作9 i 。1 9 8 8 年，d e n n i n g 和t e r e s a l 公布了他们的入侵检测专家系统( i n t m s i o nd e t e c t i o ne x p e r ts y s t e m ，i d e s ) ”，堪称i d s 原型研制的典范。1 9 9 0 年，加州大学戴维斯分校的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 ) 系统l i ”，将网络流作为审计数据来源，在网络环境下实现监控异种主机和网络设备的入侵检测。2国内对入侵检测研究工作开展较晚。从发表的文献看，对系统框架“蛳幔嗍，i和入侵检测算法”碰”的研究居多，主要工作以利用现有技术开发应用系统为主j 随着目前攻击的多样化、复杂化，入侵检测技术也在飞速的发展。它已经成为网络安全领域内研究的热点，不断有新的入侵检测模型与系统拨开发设计出来二十世纪年代中期后。众多组织和机构投入了将数据挖掘技术应用于入侵检测数据分析的研究，成为一个新的研究热点国际上在这方面豹研究很活跃多数得到了美国国防部高级研究计划署、周家自然科学基金的支持主要有美国哥伦比亚大学( c o i u m b i au n i v e r s i t y ) 的w e n k ol e 研究组和u n i v e r s i l yo f n e wm e x i 的s t e p h a n i tf o n t 砒研究组。w e n k ek o 研究小组在数据挖掘技术应用于入侵检测系统中傲了大量开创性工作i i l h 嘲圳l 圳嘲w b n k el e e 在摁a p r i o r i 运用到入侵检测中时，加入了领域知识对关联分析算法和序列模式挖掘算法进行了改进此外，通过引入轴属性( a 蝣a t t r - b u t e ) 和参考属性的概念来作为限制仅仅得到相关的模式，使用逐层近似挖掘( l 。v e l w i s ea p p r o x i m a t em i n i n g 概念来提取低频但重要的模式，使得检测模型更有效。搬据美国国防高级研究计划署da l 瞪a t h td e f e n a d v d 巍e 靠c hp r o j e c t s a g e 鹏y j 的报告，由c o l u m b i 8 u n i v 盯摹i t y 实现的基于数据挖掘的入侵检涮系统在检测拒绝服务攻击和扫描方面优于其他系统在检测本地用户非法提升权限方面与其他系统大概持平。在检测远程攻击如缓冲区溢出方面，所有系统表现都不令人满意，检测率都在7 0 以下u n i r s i t yo f n e w m e x i c o 的s t c p h a n i 霉f o r 件t 研究组提出了将生物免疫机制引入计算机系统对主机系统调用的审计数据进行分析处理，通过大量的实验发现，对一个特定的程序来说，其系统调用序列是相当稳定的，使用系统调用序辫来识别“自我”，应该可以满足系统的要求提出了基于系统调用的短序列匹配算法，用于计算实际系统调用序列与正常序列模式的相似程度，并作了大量开刨性的工作嘲1 j l 堋l q 鲫然而短序列匹配算法只考虑了系统调用在时何上豹次序，两没有考虑调用的参数同时，g c o 理e m a s o n 大学d a n i e i b a f b a m 等人研究了面向入侵检测的数据挖掘a d a m ( a u d i t o a t | a n a l y s i s 曩n d m i n i n g ) 圳 d 柚d 童蕞过从t c p d u 唧审计轨迹中挖掘频繁模式，似此来发现入侵对t c p _ ，i p f l r r 舳s m i s s i o nc o m m lp f o t o i ，l 曲嘲b 珊，r o t o c o l l 流量数据进行预处理，从每个数据包中抽取其头部信息，为每个? e p ，i p连接建立一个连接记录，挖掘过程在连接记录数据集上进行 d a m 的主要缺点是对纯净数据的依赖较多虽然具有一定的检测未知入侵类型的能力，但误报事较高此外，针对入侵检测问题本身的模糊性和连续属性钓离散化产生的。尖锐边界”问题，m i s s i s s i p p i 州立大学的m 毪虹。嵫t 枷l 和铀观nm b 矾萨等人俸出了突出的贡献，提出了将模糊逻辑引入入侵检测”。采用模糊关联规则和模糊频繁情节算法挖掘审计数据，能够得到更加抽象和灵活的模式。国内学者在基于数据挖掘的入侵检测研究方面还在理论研究和实验阶段，主要是对关联规则算法和序列模式挖掘算法的改进。武汉大学电子信息学院的朱天清等将模糊技术应用到入侵检测中，对传统a p r i o r i 算法进行了改进，提出了在模糊关联规则的挖掘中将事务属性模糊集作为单一属性来处理，详细描述了在异常检测中应用模糊关联规则挖掘的具体步骤，即建立系统正常模式下的关联规则集，然后挖掘系统在某暂态模式下的关联规则集，通过计算两规则集的相似度来确定系统是否处于异常状态”。华中科技大学的王卉将最大频繁项集挖掘算法用于入侵检测”“”。武汉大学电子信息学院凌军等人提出并实现了一个基于规则的、层次化的智能入侵检测原型系统( r i d e s p l 。杭州电子科技大学计算机学院的丁宏等针对网络入侵检测领域使用关联规则挖掘关联模式精度不够，效率不高的问题，提出了一种新的基于最大值限制的关联规则算法1 。杭州电子科技大学计算机学院的赵观军等针对网络入侵检测领域使用a p r i o r i 算法挖掘频繁模式效率不高、精度不够的问题，提出了在f p ( f r e q u e n tp a t t e r n s ) g r o 叭h 的基础上基于分割原理的p f p g r o m h ( p a r t i t i o nb a s e df p g r o 、v t h ) 算法o ”，该算法采用分而治之的方法，即有效利用了f p ( f r e q u e n tp a t t e r n s ) t r e e 特性，又减轻了系统挖掘大容量数据库的负荷，使挖掘效率有了明显提高。中国科学院研究生院信息安全国家重点实验室连一峰等人对t e l n e t 会话中用户执行的s h e l l 命令序列进行挖掘，建立用户异常行为模型9 “。总之，目前国内外将数据挖掘应用于入侵检测系统的基本原理和方法尚未得到充分研究，主要集中在基于关联规则入侵检测系统的研究舯l 和基于序列模式挖掘的入侵检测系统研究。对于关联规则的研究主要是针对入侵检测的特点改进通用的关联规则算法，例如加入领域知识、引入逐层近似挖掘概念等；针对入侵检测问题本身的模糊性和连续属性的离散化产生的“尖锐边界”问题，将模糊逻辑引入入侵检测；对于使用关联规则挖掘关联模式精度不够的问题，运用领域划分方法对最小支持度进行了调整。序列模式挖掘算法在入侵检测中的研究主要是针对主机系统调用序列和用户命令序列的研究。对于序列挖掘算法的研究主要是加入领域知识、改进挖掘效率、引入模糊逻辑、应用约束来去除无用规则等。1 3 论文的主要研究内容及安排随着网络技术的发展，网络安全工作也在日益飞速发展。入侵检测技术作为新一代的网络安全技术，也在众多研究人员的参与下快速的发展着。作为一种新型的、积极主动的安全防护体系，入侵检测相比于“防火墙”等老一代的安全技术有着它明显的优点。但同时，入侵检测技术目前很多方面还处于研究阶段，并4没有形成一个较为完善的系统体系，因此本文的研究具有巨大的挑战性。数据挖掘是运用到入侵检测中的较新的技术，它可以从大量的网络数据以及主机的日志敛据中提取出入们需要的、事先未知的知识和规律怎样将敛据挖掘技术有效、灵活的运用到入侵检测系统中去将是本文主要研究的问题本文的主要工作在于首先，介绍了本文的研究背景及意义，分析了目前基于数据挖掘的入侵检测系统的国内外研究现状。研究了数据挖掘技术及在入侵检测中的应用研究了数据挖掘技术应用到入侵检测系统中的优势、基于序列模式挖掘的入侵检测系统研究现状和目前基于数据挖掘的入侵检测系统中存在的不足接着，分析了序列模式挖掘算法，针对目前基于序列模式挖掘的入侵检测中存在的不足。对p r e f i x s p a n t 算法进行了改进。t 最后，研究了基于序列模式挖掘的入侵检测系统模型将改进的- p r e f i x s p 粕。算法应用于该入侵检测系统中。详细墙介绍了该系统模型中的数据预处理模块、数据挖掘模块和模式比较模块并进行了仿真实验给出了安验结果分析本文章节组织如下第一章为概述介绍了本论文的研究背景及意义，分析了目前基于数据挖掘的叭侵检测系统的国内外研究现状，介绍了本文的组织结构。第二章为数据挖掘技术及在入侵检测中的应用研究。介绍了数据挖掘技术和入侵检测技术，研究了数据挖掘技术及在入稷检测中的应用，研究了数据挖掘技术应用到入侵检测系统中的优势，基于序列模式挖掘的入侵检泓系统研究现状和目前基于数据挖掘的入侵检测系统中存在的不足第三章为巾f e f i x s p a n 序列模式挖掘算法的改避，对序列模式挖掘算法进行7分析，并研究了序列模式挖掘算法应用于入侵检测中的不足。详细阐述了改进的p f e f i x s p a n 算法。第四章研究了基于序列模式挖掘的入侵检测系统模型。将改进的陬磊x s p a n算法应用于该入侵检测系统中，详细地介绍了该系统模型中的数据预处理模块、数据挖掘模块和模式比较模块并进行了幼真实验- 给出了实验结果分析总结与展望，总结本文的贡献和创新。并对下一步工作进行了展望。最后是攻读硕士期间撰写的论文、致谢以及参考文麓5第二章数据挖掘技术及在入侵检测中的应用研究数据挖掘( d | t am i n i n g ) 。也称数据库中的知识发现( k n o w i e d g ed i 鲫懈y 蠊d a t | b o s 。垄【d d ) 这一术语最早出现在1 9 8 9 年a 从i ( 知啮r i c a - a s c i 戤i 伽l ；瞳a r t i f i c i a h m d l i g e n c e ) 的：k d d 专题研讨会上它是指从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中豹、人们事先不知道的、但又是潜在有用的信息和知识的过程，提取的知识一般可表示为概念( c 朋c e p t s ) 、规剐( r u i e i ) 、规律( r e g u i a r i t i c s ) ，模式( p i t t e m 0 ) 等形式。入侵检测( i 埘m s i 帆幽吨e c t i o n )是用于检铡任何损害或企图损害系统的保密性，完整性或可用性行为的一种网络安全技术数据挖掘技术已经得到了广泛的应甩，常用于入侵检测的数据挖掘分析方法主要有关联分析方法，序列模式分析方法、分类分析方法等。本章首先介绍数据挖掘技术和入侵检测技术，然后对基于数据挖掘的入侵检测进行了研究。2 1 数据挖掘技术随着网络技术的不断发展和网络速率的提高，嗣络流量飞速提高，为入侵检涮系统分析事件而提供的网络数据也随着时闾的积累丽越来越多。激增的数据背骺隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析。以便更好地利用这些数据利用手工分析如此庞大的数量的数据并及时得到有价值的结果显然是不可能的。为实现用智能化的方法自动从大量的数据中迅速发现有用的知识。必须寻找更有效的工具和技术随着人工智能的发展出现了机器学习，它是采用计算机模拟人类学习的一门科学人们用数据库来存储数据用机器学习韵方法来分析数据，挖掘大量数据背后的知识这两者的结合形成了知识发现) d 它的全过程定义描述如图2 1所示整个知识挖掘过程是由若干挖掘步骤组成的，而数据挖掘仅是其申一个圭要步骤。知识挖掘的主要步骤有：1 数据准备( d a t ap r e p a i i 伽) 。针对挖掘目标收集、整理原始数据集l2 数据预处理( d a t a p 增p f o c 伪s i n g ) ：从相关的数据集合中除去明显错误韵数据和冗余的数据。精减数据中的有用部分，并将数据转换成为有效形式以使数据开采更有效。数据预处理包括数据清理、数据集成、数据选择和数据交换( 1 ) 数据清理：消除噪声或不一致数据；6( 2 ) 数据集成：把多种数据源组合成在一起；( 3 ) 数据选择：从数据库中检索与分析任务相关的数据；( 4 ) 数据变换：将数据变换或统一成适合挖掘的形式；3 数据挖掘( d a t am i n i n g ) ：它就是知识挖掘的一个基本步骤，就是利用智能方法挖掘数据模式或规律知识；4 模式评估( p a t t e r ne v a l u a t i o n ) ：其作用就是根据一定评估标准从挖掘结果筛选出有意义的模式知识；5 知识表示( k n o w l e d g ep r e s e n t a t i o n ) ：其作用就是利用可视化的知识表达技术，向用户展示所挖掘出的相关知识。尽管数据挖掘仅仅是整个知识挖掘过程中的一个重要步骤，但是由于“数据挖掘”已经被广泛使用并被普遍接受，广义地使用“数据挖掘”一词来表示整个知识挖掘过程，数据挖掘就是一个从数据库、数据仓库或其它信息资源库的大量数据中发掘有趣的知识。评价与表i；o数据 哇掘1po选择与转换f 盐知识i c i集成f 1ri 特定l 一，模式圉_，i 数据集l、itji c illlli 旱皇lji图2 1 知识发现的全过程世界上对数据挖掘的正式研究是在1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会议上提出。随后数据挖掘的研究成为热点。近年来注重对贝叶斯等方法的研究和提高；k d d 与数据库的紧密结合。在国外，数据挖掘技术已经广泛地应用于金融业、零售业、远程通讯业等信息化程度较高的行业。而它在网络中的应用也正在成为一个热点。数据挖掘技术在网络安全领域的主要应用有：对安全检测对象的海量审计数据的分析，例如网络连接流量的分析，主机日志分析等等；对安全检测对象的行为数据分析，例如基于用户命令序列的行为分析，对用户邮件模式的行为分析等；7对安全系统报警事件的数据分析等。在特定的甸题中。敷据挖掘的分析方法有一定的区别，这主要取决于数据的类型和规模，以及求解的目标。与国外相比，；国内对数据挖掘技术的研究稍晚。1 9 9 3 年国家自然科学基金首次开始支持对该领域的研究项目。近年来发展迅速，进行的大多数研究项目是由政府资助进行的。如国家自然科学基金、堪6 3 计划、。九五。计划等。所涉及的研究领域很多。一般集中于学习算法的研究、数据挖掘的实际应用以及有关数据挖掘理论方盾的研究。国内从事数据挖掘研究的机构主要在大学，也有部分在研究，所或公司。其中，北京系统工程研究所对模糊方法在知识发现中韵应用进行了较：深入的研究，浙江大学等单位开展了对关联规则开采算法的优化和改造上海交通大学等单位探讨、研究了非结构化数据的知识发现以及w 曲数据挖掘。尽管且+ 前数据挖掘的论文统计数相当可观，但我国的数据挖掘应用尚处于尝试性的萌芽阶段。企业大规模地运用数据挖掘技术尚不普遍。下面来介绍几种常用于入侵检测的数据挖掘技术1 关联分析关联分析就是要发现关联规则，找出给定数据集中数据项之间的联系。用于关联规则发现的主要对蒙是事务型数据库( 1 h n s a c t i e n d a t 曲a 嘲) 也就是给定一组i e m 和一个记录集合，通过分析记录集合，推导出h e m 间的相关性。关联规则是形式如下的一种规则“在购买面包和黄油的顾客中，有9 0 的人同时也买了牛奶”( 面包+ 黄油一 牛奶h关联规则的发现可分为两步t步骤一i 迭代识别所有的频繁项目集要求频繁项目集的支持度不低于用户设定的最低值：步骤二l 从频繁项目集中构造信任度不低于用户设定的最低值的规贝4 其中，识别或发现所有频繁项目集是关联规则发现算法的核心，也是计算量最大的部分而第二步骤的工作只是根据生成的频繁集创建相应规则的枚举过程。无需复杂的计算因此，目前所谓的算法设计饲题主要是围绕如何生成频繁集展开的。在i d s 中关联分析算法可以挖掘出记录中不同属性之间的关联关系。利用调练数据中各属性之阔的关系形成关联规则构造用户正常行为模式及入侵模型2 序列分析关联规则挖掘用于发现数据记录中不同数据项之问的关联性。而序列分析算法则是处理不同记录之伺属性集的关联关系。把数据之间的关联性与时阔联系起来。，序列分析目标是在事务数据库中发掘出序列模式( i a r g es e q u e n s ) ，即满足用户指定的最小支持度( m i n i m u ms u p p o r t ) 要求的大序列。并且该序列模式必须是最高序列( 船x i m a ls e q u 蜘c e ) 。8为了发现序列模式，不仅需要知道事件是否发生，而且需要确定事件发生的时间。序列模式分析的侧重点在于分析数据问的前后序列关系。序列分析描述的问题是：在给定交易序列数据库中，每个序列按照交易时间排列成一组交易集，挖掘序列模式作用在这个交易序列数据库上，返回出现的高频序列。例如入侵行为发生的先后关系常常有一定的规律，黑客在入侵前先进行端口扫描然后再进行猜测密码的攻击的过程就可以用序列模式来描述。目前序列模式挖掘算法基本上可以分为两大类。第一类是基于a p r i o r i 特性的、逐层( 1 e v e l w i s e ) 的发现方法，包括a p r i o r i a l l算法和g s p 算法等，这类方法最先由r a g r a w a l 等人提出。此类算法根据a p r i o r i特性在基于已生成的频繁序列搜寻更长的频繁序列的过程中对待检查的序列集进行有效的修剪。除此之外，此类方法中的大多数采取了一种逐层的、侯选序列生成和测试方法。另一类方法由h a n 等人提出，称为基于序列模式增长方法，包括f r e e s p a n ( f r e q u e n tp a t t e r n - p n o j e c t e ds e q u e n t i a lp a n e r nm i n i n g ) ，p r e f i x s p a n 算污蔓毒筝。这类方法采取了一种分而治之的思想，挖掘过程中无需生成候选序列，不断缩小投影数据库。在i d s 中序列分析算法可以获取记录之间在时间窗口中的关系，可以发现审计数据中一些经常以某种规律出现的事件序列模式。这些频繁发生的事件序列模式可以在构造入侵检测模型时选择有效的统计特征。3 ，分类分析数据分类的目的是提取数据库中数据项的特征属性，生成分类模型，该模型可以把数据库中的数据记录映射到给定类别中的一个。数据分类的步骤为：步骤一：获得训练数据集，该数据集中的数据记录具有和目标数据库中数据记录相同的数据项。步骤二：训练数据集中每一条数据记录都有己知的类型标识与之相关联。步骤三：分析训练数据集，提取记录的特征属性，为每一种类型生成精确的描述模型。步骤四：使用得到的类型描述模型对目标数据库中的数据记录进行分类或生成优化的分类模型( 分类规则) 。在i d s 中，可以先收集用户或应用程序的“正常”和“非正常”的审计数据，然后用一个分类算法得到分类模型，用它来预测新的审计数据属于正常还是异常。4 聚类分析聚类( c l u s t e r i n g ) 是一个将数据集划分为若干组( c l a s s ) 或类( c l u s t e r ) 的过程，并使得同一组内的数据对象具有较高的相似度，而不同组中的数据对象则是不相似的。相似或不相似的度量是基于数据对象描述属性的取值来确定的，通常就是利用( 各9对象问) 距离来进行描述的。在机器学习中，聚类分析属予一种无监督的学习方法与分类学习不同，无监督学习不依赖事先确定的数据类别以及标有数据类别的学习训练样本集合。正因为如此。聚类分析又是一种通过观察学习方法( 1 e a m i 鸭姆o b 坼r v 砒i o n 。而不是示例学习( 1 e a m i n gb ye x a m p l e 。聚类分析的基本指导思想是最大程度地实现类中对象相似度最大，类间对象相似度最小在i d s 中，可以利用聚类分析算法直接将未知的网络数据聚成不同的类。使得同一类的数据相似性大，不同类的数据相似性小。由此可以直接将罔络数据翅分成正常类和异常类而不需要带有类别标记的谰练数据集2 2 入侵检测技术入侵( i n t m s i 硼) 是指任何企翻危及资源舶完整性( 1 砒昭m y ，杌密性 c 0 n f i d e n t i a l i t y ) 和可用性( v i h _ 艟l i t y ) 的活动入侵检测( i l i t m s i 锄d e l e c l i 嘲)是用于检测任何损害或企圈损害系统的保密性，完整性或可用性行为的一种两络安全技术。它不仅检测来自夕卜部的入侵行为，同时也检测内部用户的未授权 a u t h o r i 船t i o n ) 活动入侵检测提供了用于发现入侵攻击与合法用户滥用特权的一种方法，它基于这样一个前提基础：入侵行为和合法簟亍为是可区分的，也就是说可以通过提取行为的模式特征来判断该行为的性质。叭侵检测系统( i n t m s i o nd e t e c l i o ns y 吼哪撙s ) 是执行入侵检测工作的硬件和软件产品。i d s 通过实对的分析，检查特定的攻击模式、系统配置、系统漏漏、存在缺陷的程序版本以及系统或用户的行为模式。监控与安全有关的活动一个基本的i d s 需要解决两个饲题- 一是如何充分可靠地提取描述行为特征的数据，二是如何根锯特征数据高效并准确地判定行为的合法性a 入侵检测是监视计算机稠络系统中违背系统安全策略行为的过程。按照最为规范的形式来划分，入侵检测系统分为以下3 个模块( 1 ) 数据源。提供用于系统监视的审计记录流z ( 2 ) 分析引擎。用于对审计数据进行分析发现入侵或异常行努( 3 ) 响应根据分析引擎的输出结果，产生适当的反应入侵检测系统可以分别从数据源、分析弓i 擎，响应这3 个角度进行分类倒如根据数据源的不同，：i d s 可以分为基于主机、基于网络等类型；针对分柝弓l擎，则可似划分为误用检澍( 越i s u s e d e t e c t i o n ) 系统和异常检测系统；而从响应的角度来看，i d s 则包括主动响应、被动响应及混合响应这三种模式：根据i d s 对入侵的 反应速度，入侵检测技术分实时入侵检测和事后入侵检溺两种。实时入侵检测在网络连接过程中进行，系统根据用户的历史行为模型存储在计算机中的专家知识库系统以及智能技术模型对用户当前的操作进行判瞬一旦发现入侵迹象立即采取相应措施，并马上收集证据和实施数据恢复。实时检测分析使入侵检测系统对入侵的自动反应成为可能。而事后入侵检测由网络管理人员进行，他们具有网络安全专业知识，根据计算机系统对用户操作所做的历史审计记录判断用户是否具有入侵行为，若有就断开连接，并记录入侵证据和进行数据恢复。事后入侵检测由管理员定期或不定期进行，不具有实时性，防御能力不如实时入侵检测系统，易于遭受到非法破坏。实时入侵检测系统对网络系统免遭破坏具有现实的重大意义。正是由于实时入侵检测系统的优越性，目前的发展趋势主要是研制智能实时入侵检测系统，使其具有智能化、更准确、更高效、更易于理解。入侵检测系统根据其采用的技术，可以分为异常检测和误用检测，均可用于实时检测和事后检测。1 异常检测( a n o m a l yd e t e c t i o n )异常检测又称为基于行为( b e h a v i o u r b a s e d ) 的检测，根据使用者的行为或资源使用状况是否偏离正常的情况来判断入侵是否发生。通过对系统异常行为的检测，可以发现未知的攻击模式。其结构如图2 2 所示：是否偏离图2 2 异常检测示意图异常检测基于已掌握了被保护对象的正常工作模式，并假定正常工作模式相对稳定。一般方法是建立一个对应“正常活动”的系统或用户的正常轮廓，检测入侵活动时，异常检测程序产生当前的活动轮廓并同正常轮廓比较，当活动轮廓与正常轮廓发生显著偏离时即认为是入侵。异常检测的关键问题在于正常模式( n o r m a lp r o f i l e ) 的建立以及利用该模式对当前的系统用户行为进行比较，从而判断出与正常模式的偏离程度。异常检测主要有以下几个优点：( 1 ) 异常检测与系统相对无关，通用性较强。( 2 ) 具有较强的适应性，能检测出以前从未出现过的攻击方法；同时，异常检测也存在如下缺点：( 1 ) 由于不可能对整个系统内的所有用户行为进行全面的描述丽且每个用户的行为是经常改变的，所以它的主要缺陷在于误检率很高； 即如果一个项目集不是频繁项目集那么它的所有超集都不是频繁项目集，这样所有的( k + i ) 候选项目集是在k 频繁项目集的基础上生成的。在过去基于数据挖掘的入侵检测应用中，很多研究人员利用a p r i o f i 算法挖掘频繁模式。例如哥伦比亚大学的w e n k el 等人从1 9 9 5 年开始首先将数据挖掘技术应用于入侵检测，提出了各种入侵检测的方法。w e n k el e e 在把a p r i o f i 运用到入侵检测中时，加入了领域知识对其进行改进，比如设置轴属性( a x i i 觚r i b t l e ) 来减少产生候选项目集，并使用近似层次挖掘( l c v e i w i ”a p p f 似i 麟髓m i n i n g ) 来提取稀疏但重要的信息。随着入侵手段的不断提高，许多入侵行为依赖于事件的发生顺序当入侵一台有一定防护措施的服务器或主机时，入侵者往往按照某种顺序实施一系列的攻击步骤，其中任何单独的一条报文或者命令都是正常的，没有明显的字符串攻击特征。但一系列按时间顺序摊列的报文或者命令就构成一次攻击。在这种情况下基于关联规则等数据挖掘算法就显得力不从心了，而序列模式挖掘技术能够反跌出这种时间顺序特征。可以检测出以往入侵检测方法很难检测到的序列攻击，予是序列模式挖掘算法就被引入到了入侵检测系统2 4 本章小结本章首先介绍了数据挖掘技术的基本概念、研究现状及几种常用于入侵检测的数据挖掘技术。接着介绍了入侵检测技术的基本概念、异常检测技术和误用检铡技术、研究现状及今后豹发展方向最后研究了基于数据挖掘的入侵检测技术分析了数据挖掘技术应用到入侵检测中的优势，分析了基于序列模式挖掘的入侵检测系统的研究现状，最后给出了目前基于数据挖掘的入侵检测系统中存在的不足。第三章p r e fi x s p a n 序列模式挖掘算法的改进运用数据挖掘方面的知识来实现入侵检测的方法在近凡年得到了越来越多的重视，序列模式挖掘算法能够挖掘出不同记录之间的规律性，并且已经在入侵检测领域中得到了应用本章首先给出了序列模式挖掘的一些基本概念，接着对序列模式挖掘算法进行了分析，然后针对目前基于序列模式挖掘的入侵检测系统中存在的不足，对p f e f i x s p 矗n 算法进行了改进。并给出算法流程和算法示例。3 1 序列模式挖掘的基本概念序列挖掘或称序列模式挖掘，序列模式挖掘最早的定义由姆a w a l 和s f i k a n t给出：给定一个序列集合和用户指定的最小支持度阈值，其中每个序列由元素的列表组成，每个元素由项集组成。序列模式挖掘就是找到所有出现频率不低于最小支持度的子序残。序列分析算法的目标是在事务数据库中挖掘出序列模式，即：满足用户指定的最小支持度要求的大序列。有时只需要找出最高序歹l i 。定义，1 ；序列是一列排好序的项集假定项集中的项由一些连续整数代替，这样一个项集；可以表示为( j j j 政i 。) ，面这里的0 代表了一个项。一个序歹l j 可以表示为 $ j ，却驴。这里的岛代表的是一个项集。定义3 2 ：序列饷长度是指它所包含的项集的总数。具有k 长度的序列称为k 序列。，定义3 3 ：两个序列口 和矗 ，如果存在整数办 b k 且砚包含于南j ，国包含于南扣，锄包含予参i - 。则称序列包含于序列6 比如序列 ( 8 ) 包含予序列q 7 ) 毛g ，( 9 ) 心5 ，缈8 ) 因为( 3 包食于( 3 ，珐住5 包含予 5 ，6 ) 以及( 墨 包含予( s ) 但是序列 ( 3 ) 5 ) 不包含于 反之亦然两者的区别在于：前者表示项3 和项5 是先后发生的而后者则表示项和项5 是同时发生的。定义3 铂在一个序列集中如果序列j 不包含于任何其他序列中则称序列矗为最高盼定义3 5 ：序列的支持度皑删是指包含了该序列的谢数与全部蒯数的比倪。也可以用包含该序列的蒯数来表示。定义3 6 ：前缀户嘲缸假定序列中所有的项都是以字典顺序排列。给定两个序列口一 ，l 6 = 伽 = 圳，6 是口的前缀，当且仅当以下三个条件满足：( 1 )自名e j ，f = m - j ；( 2 )p 。包含于p 。；( 3 )所有( p 。p 。，) 中的项都必须在字符顺序中排在口。后。如s ，= 的前