（计算机软件与理论专业论文）基于数据流挖掘技术的入侵检测模型研究.pdf

摘要 摘要 随着i n t e m e t 的迅速发展，操作系统规模的不断增大，传统的静态防火墙技 术不能满足当今网络安全的需求。入侵检测作为一种主动的防御技术，是传统计 算机安全机制的有效补充。从本质上讲，入侵检测技术是对各种审计数据的分析。 数据挖掘是一种高级的数据分析技术，把其用到入侵检测领域，构建智能、自适 应的入侵检测系统得到了很多研究人员的关注。 传统的数据挖掘技术在入侵检测系统中的应用大多是改进现有数据挖掘算 法或者将多种数据挖掘方法相结合来构建入侵检测模型。传统的数据挖掘技术以 静态的数据集为数据源，多遍扫描数据集挖掘有用的知识模式。而入侵检测系统 处理的数据是无限、高速的多维网络数据流，把网络数据保存后再进行分析有着 一定的滞后性，并且把海量的网络访问数据保存后分析也是不可行的。因此需要 直接分析网络数据流，构建基于数据流挖掘技术的入侵检测模型。 本文分析了数据集k d d 9 9 中的四类攻击数据，论证用户的行为可以通过分 析访问数据进行追踪，即可以通过分析用户的访问数据来刻画用户的行为。网络 访问数据有着数据流的特点，因此本文设计了基于数据流挖掘技术的入侵检测模 型，利用数据流挖掘技术分析不断到来的高速网络数据流，得到用于刻画用户行 为的访问模式，利用得到的访问模式检测新到来的数据是否为入侵数据。 构建基于数据流挖掘技术的入侵检测模型的关键在于有高效的数据流挖掘 算法的支持。本文设计一种新型数据结构m a x f p t r e e ，并在m a x f p t r e e 的基础 上设计了基于衰减窗口机制的挖掘网络数据流上用户访问模式的算法 a p i n n d s 。a p i n n d s 与传统的基于a p r i o r i 的算法思想( 通过频繁项集之间的并 集操作寻找新的频繁项集) 完全不同，它以在数据记录中实际出现的节点为根据， 通过抽象操作实现对频繁项集支持度的记录，它不是从空集开始正向生长的树， 而是从全集开始反向生长的树。同时采用衰减机制来消除历史数据的影响，使内 存中维护的m a x f p t r e e 树能真实反映用户当前的状况，并使m a x f p t r e e 树的 规模保持在一个合理的规模，从而可以高效的处理不断到来的网络数据流。 最后通过实验验证本文设计的基于数据流挖掘的技术的入侵检测模型是可 行的。 关键词入侵检测；数据挖掘；数据流；最大频繁模式：异常检测 a b s t r a c t 苎i 二i ；= = ；i 一二 i i 一一i i ；_ i i i i ! 鼍曼! 曼曼皇曼! ! 鼍曼! 曼! ! 曼苎! 皇皇 a b s t r a c t w i t l lt h er a p i dd e v e l o p m e n to fi n t e m e ta n dt h eg r o w i n gs i z e so fo p e r a t i n g s y s t e m s ，t h et r a d i t i o n a ls t a t i cf i r e w a ut e c h n o l o g yc a l ln o tm e e tt h er e q u i r e m e n t so f t o d a y sn e t w o r ks e c u r i t y i n t r u s i o nd e t e c t i o na s a l la c t i v ed e f e n s et e c h n o l o g yi s s u p p l e m e n to ft r a d i t i o n a lc o m p u t e rs e c u r i t ym e c h a n i s m i ne s s e n c e ，t h ei n t r u s i o n d e t e c t i o nt e c h n o l o g yi sa n a l y z i n gk i n d so fa u d i td a t a d a t am i n i n gi sa n a d v a n c e dd a t a a n a l y s i st e c h n i q u e ，i t sa p p l i c a t i o nt ot h e f i e l do fi n t r u s i o nd e t e c t i o na n db u i l d i n g i n t e l l i g e n t ，a d a p t i v e i n t r u s i o nd e t e c t i o ns y s t e mh a sa t t r a c t e dl o t so fr e s e a r c h e r s i n t e r e s t s m o s to ft h ea p p l i c a t i o n so ft r a d i t i o n a ld a t am i n i n gt e c h n i q u e si ni n t r u s i o n d e t e c t i o ns y s t e ma r ci m p r o v i n ge x i s t i n gd a t am i n i n ga l g o r i t h m s ，o rc o m b i n i n gm u l t i d a t am i n i n gm e t h o d st ob u i l di n t r u s i o nd e t e c t i o nm o d e l t r a d i t i o n a ld a t am i n i n g t e c h n i q u e sm a k es t a t i cd a t as e t sa si t si n p u t ；t h r o u g hm a n yt i m e ss c a nt om i n eu s e f u l k n o w l e d g e h o w e v e r , t h ed a t a sw h i c hi n t r u s i o nd e t e c t i o ns y s t e m sn e e d t op r o c e s sa r e u n l i m i t e d ，h i g h - s p e e dn e t w o r kd a t as t r e a m s ，i ti sd e l a y e dt oa n a l y z et h ed a t aa f t e r s t o r i n gt h e mt od i s k a n do nt h eo t h e rh a n di ti si n f e a s i b l et os t o r et h ev a s ta m o u n t so f n e t w o r kd a t a t h e r e f o r e ，i tn e e d st oa n a l y z et h en e t w o r kd a t as t e a m sd i r e c t l ya n d c o n s t r u c ti n t r u s i o nd e t e c t i o nm o d e lb a s e do nt h et e c h n o l o g yo fd a t as t r e a m s t h i sp a p e ra n a l y z e sf o u rc a t e g o r i e so f 锨a c kd a t ai nt h ed a t a s e to fk d d 9 9 ，t h e r e s u l ts h o w st h a tu s e rb e h a v i o rc a nb et r a c e dt h r o u g ht h ea n a l y s i so fa c c e s sd a t a a s n e t w o r ka c c e s sd a t ah a st h e c h a r a c t e r i s t i co fd a t as t r e a m ，t h i sp a p e rp r e s e n ta l l i n t r u s i o nd e t e c t i o nm o d e lb a s e do nt h em i n i n gd a t as t r e a m s ，u s i n gd a t am i n i n g t e c h n o l o g yt oa n a l y z eh eh i g h s p e e dn e t w o r kd a t a s t r e a m sa n dg e tu s e r a c c e s s p a t t e r n s a tl a s t ，c h e c kt h en e wc o m i n gd a t aw h e t h e ri si n t r u s i o no rn o tb ya l r e a d yg o t u s e ra c c e s sp a t t e r n s e f f i c i e n td a t as t r e a mm i n i n ga l g o r i t h mi st h ek e yp o i n tt oc o n s t r u c tt h ei n t r u s i o n d e t e c t i o nm o d e l a c c o r d i n gt ot h ei n t r u s i o nd e t e c t i o nb a c k g r o u n d ，t h i sp 印e rd e s i g na n e wd a t as t r u c t u r ew h i c hc a l l e dm a x f p t r e e ( m a x i m a lf r e q u e n tp a t t e r nt r e e ) ，a n d b a s e do nm a x f p t r e ew ei n t r o d u c ea l la l g o r i t h ma p i n n d st om i n em a x i m a lf r e q u e n t i t e m s e t si nn e t w o r kd a t as t r e a m t h ea l o g o r i t h ma p i n n d si su s i n gd a m p e dw i n d o w s s t r a t e g y a p i n n d si sd i f f e r e n tf r o mt h et r a d i t i o n a la l g o r i t h m sb a s e do nt h ei d e ao f a p r i o r iw h i c hi st h r o u g hd ou n i o no p e r a t i o nb e t w e e nf r e q u e n ti t e m s e t st of i n dn e w f r e q u e n ti t e m s e t s h o w e v e r , a p i n n d st h r o u g hd oa b s t r a c to p e r a t i o nb e t w e e nt h e i i i 北京t 渡大学下学硕士学位论文 i i l li l l l i l l l l li l l l i l l l l _ - _ _ _ _ _ 一 n e t w o r ka c c e s sr e c o r da n dt h en o d ea p p e a r e di nt h er e c o r dt oc o u n tt h es u p p o r to ft h e n o d e 。n l em a x f p t r e ei ss t a r t i n gf r o maf u l ls e to t h e r w i s ee m p t ya n di sg r o w i n g u p w a r d s a tt h es a m et i m ea p i n n d sa d a p t sd a m p e dm e c h a n i s mt oe l i m i n a t et h e i m p a c to fh i s t o r i c a ld a t a , s ot h a tm a x f p t r e ec a l lr e f l e c tu s e r sr e a ls i t u a t i o na n dt h e s c a l eo fm a ) ( 薹p - t r e ec a l lb ek e p ta tar e a s o n a b l es c a l e ，a n dt h e na p i n n d sc a nh i g h l y e f f i c i e n td e a lw i t ht h ec o n s t a n ta r r i v a lo ft h en e t w o r kd a t as t r e a m a tl a s tt h i sp a p e rt h r o u g he x p e r i m e n t st op r o v et h ei n t r u s i o nd e t e c t i o nm o d e l b a s e do nm i n i n gd a t as t r e a m si sf e a s i b l 。 k e yw o r d si n t r u s i o nd e t e c t i o n ；d a t am i n i n g ；d a t as t r e a m ；m a x i m a lf r e q u e n ti t e m s e t s ； a n o m a l yd e t e c t i o n i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：雄导师签名： 日期：星! 堕：兰 繁l 窜绫论 。 入侵检测技术 第1 章绪论 1 。1 。1 入侵检测技术的产生与发展 随着i n t e r n e t 在全球戆普及稻应藤，丽络对久销正常的王作和生活起着越来 越重要的终用。然而人们在方便使用网络的周时受到来自网络的攻击也越来越 多，网络安全问题是人们所必须解决的问题。传统解决网络安全问题的主要技术 手段翔物理隔离、防火墙技术、舞份识掰、加解密技术、访闻控制等，它稍都可 以在某一方嚣、定程度上保护系统和网络豹安全。但密于现在的网络环境帮操 作系统变的越来越复杂，同时由于系统和网络设计本身的缺陷，其弱点和漏洞不 断的暴露出来，褥加上攻击者现在知识越来越丰富，可以耐用的手段越来越多， 悠们采用鹣方法越来越离晚，单独依靠传统麓静态防御方法不能起到有效保护系 统和网络的作用。入侵检测( i n t r u s i o nd e t e c t i o n ) 是一种主动的防御技术【l j ，可 以检测未经许可的访问或对系统或网络的攻击，提供了对内部、外部攻击和误操 作静实时裣溅，是传统计冀机安全机制酌有效孝 充。 入侵检测熬研究最早可追溯到19 8 0 年j a m e se a n d 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 d s u r v e i l l a n c e ) 譬l 的技术报告，在报告中他首次提出了入侵检测的概念，提出了将 窜诗帮跟踪痘震予监视入侵活动的思想，但盘手当辩所有已有系统熬安全程序都 着重予拒绝未经认证主体对重要数据的访阅，这思想的重要性当时并未被理 解。 d e n n i n g 在1 9 8 7 首次撬凄了异常检测( a n o m a l yd e t e c t i o n ) 的方法耱天侵检 测专家系统( 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 ，简称i d e s ) 【3 】该原型系统被称为 里程碑性的入侵检测系统( 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 e s 原型系统使 爝统计学摸式来摇述系统用户的行药特 垂，包括个异常捡测器和个专家系 统。异常检测器使用了统计学技术来描绘正常行为模式，面专家系统使用了基予 规则的方法识别融知的安全入侵。 1 9 9 0 年l t h e b e r l e i n 等人提出了基于网络盼入侵裣溅( n e t w o r ks e c 确够 m o n t i o r ，简称n s 蚴斑，该系统第一次直接将网络数据流作为审计数据的来源， 因而可以在不将审计数据转换成统一格式的情况下监控异常主机。这是入侵检测 北京t 业大学t 学硕十学位论文 发展史上的一个分水岭，从此形成了两大研究方向：基于主机的入侵检测和基于 网络的入侵检测。 近年来入侵检测的创新主要是：f o r r e s t 等将免疫原理【5 叫运用到分布式入侵 检测领域；w e n k el e e 等将数据挖掘的方法应用到入侵检入侵检测领域【7 d5 1 ，数 据挖掘技术的应用使入侵检测系统有了自适应性，提高了入侵检测系统的智能 性。 1 1 2 入侵检测系统的分类 根据分类的标准不同，入侵检测系统可以分为不同的类型。主要可以根据数 据源、检测方法、体系结构来进行分类【l6 1 。 ( 1 ) 根据数据来源分类 基于主机的入侵检测系统( h o s t 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 ) ，检测目 标主要是主机系统和本地用户，数据源来自所在主机的系统审计记录或应用程序 的日志文件。 基于网络的入侵检测系统( n e t w o r k 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 ) ，提取 一定网段上传输的数据包作为数据源，保护整个网段的正常运行。 ( 2 ) 根据检测方法分类 误用检测( m i s u s ed e t e c t i o n ) ，又称基于特征的检测( s i g n a t u r e b a s e d d e t e c t i o n ) 。通过收集非正常操作( 攻击行为) 的行为模式，建立相关的特征库， 当待检测行为的特征与特征库中特征匹配时，则判定这种行为是入侵。误用检测 对于预防大量已知入侵方式的攻击是简单且高效的，但其缺陷在于只能检测已知 的入侵方式。目前大多入侵检测系统都采用这种方法。 异常检测( a n o m a l yd e t e c t i o n ) ，又称为基于行为的检测，它假设“攻击者 的行为模式同正常使用者的行为模式有本质的不同”，首先根据系统在长时间正 常运行中产生的大量审计数据建立一个正常行为模型，将待检测的行为同正常行 为模型进行比较，根据它们相异的程度来判断待检测行为是否为攻击行为。它的 优点是能有效检测未知类型的入侵行为，缺点是很难提取完整的用户正常行为特 征，误报率较高。但在入侵日益复杂化、不断变化趋势下，这种入侵检测方式具 有更好的适应性。现在基于异常机制的入侵检测方法还不成熟，是目前研究的重 点。 ( 3 ) 根据模块部署的体系结构分类 集中式入侵检测系统，系统的各个模块，包括数据的收集与分析以及响应模 块，都集中在一台主机上运行，这种方式适用于网络环境比较简单的情况。 分布式入侵检测系统，也称为基于代理的入侵检测系统，系统的各个模块可 2 筹l 豢绻论 分布在网络中不同的计葬机和设备上，这种方式适用予网络环境复杂、数据量大 豹情嚣。 1 2 数据挖掘技术在入侵检测系统中的应用 数据挖搌( d a t am i n i n g ) 是一个多学科交叉研究领域，经过十几年的研究， 一些基本概念和方法趋于清晰，它的研究也向更深入的方向发展。随着信息技术 酶发震和互联网豹兴起，数据量急耩膨胀，丽且数据的形式也多种多样。为了能 在大量数据中挖掘邀有用的信息，研究者已经设计了许多高效鲍挖掘方法。数据 挖掘技本质上是一种数据分析的技术。将数据挖掘技术应用到入侵检测领域是国 内外的研究熟点懿。数据挖掘技术在入侵检测中的应用主要有两个方向：一是 用于发现入侵的勰则、模式，与模式嚣配方法相结合；二是用于异裳检测，发现 用户正常的行为，建立用户燕常的行为模式库。蔗大部分研究都是基于异常检测 机制。目前将数据挖掘应用到入侵检测中有代表性的是：c o l u m b i au n i v e r s i t y 的 w e n k el e e 研究缀的和u n i v e r s i t yo f n e wm e x i c o 韵s t e p h a n i ef o r r e s t 研究组。 1 。2 1 传统数据挖掘方法在入侵检测系统中的应用 数据挖掘主要有四类算法：关联规则、分类、聚类霸序列分擀等，每一类算 法都在入侵检测系统中褥到了应用。 ( 1 ) 关联规则( a s s o c i a t i o nr u l e s ) 关联援篓| j 挖掘的雹的在予寻找数据瘁表串多个属性之闻关系。关联藏则挖掘 是给定一组i t e m 和一个记录集合，逶过分析记录集合，推导出i t e m 闻的相关性。 例如，“在购买面包和黄油的顾客中，有9 0 的人同时也买了牛奶( 面包十黄油= 牛奶) 。帮用予关联规刘发现静主要对象是事务数据库( t r a n s a c t i o nd a t a b a s e s ) 。 一般用置信度( c o n f i d e n c e ) 和支持度( s u p p o r t ) 来摧述关联规则。 1 9 9 8 年w e n k el e e 第一次提出了将数据挖掘的方法用在基于异常检测机制入 侵检系统中f 1 2 】，尝试用关联规则算法分析网络数据指导能描述用户行为的网络数 据属性的选择。焉褥裂游频繁模式来指导审计数据躺收集和藏性特征的选择，使 用选定的属性去建立能识别用户行隽的分类器。2 0 0 0 年w e n k el e e 进一步改进 了属性选择的方法【1 3 】，提出了核心属性( a x i s ) 和相关属性( r e f e r e n c e ) 的概念； 同时使用l e v e - w i s e 方法得到覆盖用户所有正常的行为的规则，而又不会导致规 则的泛滥，其思想是迭代豹运行算法，每次运行对支持度以一定的魄倒缩夺，直 至达到用户定义的最小闽值。2 0 0 4 年m i nq t n 提出一种基本支持度( b a s es u p p o r t ) 的挖掘模式l 埘，它使用了文献 1 3 中提出的a x i s 属性的思想，设x 为一项目集 ( i t e m s e t ) ，剃x 鹃基本支持度为x 中核心( a x i s ) 属性翡支持度的值用s ( x ) 3 毵京泣大学工学磙。垂学位论文 表示。2 0 0 5 年t i a n r u il i 提出了使用妒一a s s o c i a t i o nr u l e 方法1 1 8 】来挖掘用户正常 的模式【1 9 1 ，驴一a s s o c i a t i o nr u l e 主要思想是用一个兴趣度的函数妒( x ) 来区分不同 的项目集。2 0 0 6 年a l ye i s e m a r y 等使用基于模糊逻辑的关联规则来建立入侵检 测模型刚。 ( 2 ) 分类( c l a s s i f i c a t i o n ) 通过研究己有分类数据的特征，据此建立一个分类函数或分类模型，运用该 模型计算总结出数据的特征，将其他未经分类或新的数据进行分类。用于入侵检 测时，可以使用规则集或决策树的形式表示分类特征。入侵检测串通过收集针对 一个用户或一个程序的足够多的“正常”和“异常 审计数据，通过分类算法得 到一个分类器，该分类器能标记或者预测未见过的新审计数据属于正常还是异 常。文献【1 3 】给出了如何使用r i p p e r 算法在入侵检测系统中来构建分类器。 ( 3 ) 聚类( c l u s t e r i n g ) 聚类( c l u s t e r i n g ) 是将物理或抽象的对象分组成为多个类或簇( c l u s t e r ) 的过 程，划分的原则是在同一个簇中的对象之间具有较高的相似度，而不同簇中的对 象差别较大。聚类分析作为一种无指导的学习方法，是一个获得数据分布情况的 有力工具。聚类分析在入侵检测中的典型应用是建立用户的正常行为模型。2 0 0 1 年l e o n i dp o r t n o y 把聚类( c l u s t e r ) 方法应用到入侵检测中b ，这种方法的优点 是无指导的学习，但精度太低，这是入侵检测系统所不能接受的。文献 2 2 2 4 都探索将合适的聚类方法结合入侵检测问题进行有针对性的研究。此赡，聚类分 析还经常用于其他分析方法的一个预处理步骤。 ( 4 ) 序列分析( s e q u e n c e a n a l y s i s ) 关联分析用予挖掘数据记录中不同属性之间的关联性，而序列分析则用来发 现数据记录之闻的相关性，郄获取数据库记录之闻在时间窗霹中的关系。这类算 法可以发现审计数据中的一些经常以某种规律出现的时间序列模式。这些频繁发 生的时间序列模式可以帮助构造入侵检测模型选择有效的统计特征。u n i v e r s i t y o f n e wm e x i c o ( u n m ) 的s t e p h a n i ef o r r e s t 研究组进行的是针对主枫系统调用的 审计数据分析处理。s t e p h a n i ef o r r e s t 5 1 使用短序列匹配算法对特定的特权程序所 产生的系统调用序列进行了细致分析，在这一领域做出了大量开创性的工作。 - l 。2 。2 数据流挖掘技术在入侵检测系统中的应用 传统数据挖掘技术在入侵检测中的应用基本上是按照如何改进关联、聚类、 序列等算法或多种方法进行结合来构造用户的行为模式库，这些方法都是通过分 析有限的静态数据集去 | 导到用户已有的行为模式，丽用户的行为是不颤演化的， 4 麓l 章缝论 它们不能动态的去学习用户的行为模式，而入侵检测系统处理的是网络上动态的 数据流，不畿在数据瀛上去构建弱户翦模式库。因此要解决这些翘题，必须突破 传统数据挖掘技术在入侵检测领域的应用模式，用数据流挖掘算法来构造入侵检 的测模型。 2 0 0 5 年s a n g - h y u no h 释5 】提出在数据滤主进行聚类来构建入侵检测模囊， 由于数据流是无限的，在数据流中聚类不能预先确定类别的数曩，文中根据数据 流中对象的分布对聚类结果进行划分或合并。在建立入侵检测模型时假设各个属 性之闻是无关的，针对每个满性单独进行聚类，我们认为假设各个属性乏间为无 关是不合理的。例如一台安全级别严格的主枫开了t e l n e t 服务，只允诤特定的p 地址范圈和时间允许登录，因此服务、访问i p 地址和时间三个属性是相关的， 必须综合考虑三个属性才有意义。聚类算法的优点是可以进行无指导的学习，但 其精度院较低，两入侵检测系统要求高酶精确度，因此必须选择合适蘸挖掘算法 来构建正常模式麾。关联规则可以发现属性之间的关系，更熊准确的撼述用户的 行为，在线挖掘频繁项日集融经得到了广泛的研刭z 6 j 。 2 0 0 5 年w 雒妒迦提出了在数据流中检测蠕虫的方法咎霸，文中提出结合使用 误用检测和异常检测的方法。正鬻模式库中豹规则毙基于特征鲶误用模式库中规 则在数量上多很多倍，如果只用正常模式库来检测异常，速度和检验率都会低于 使用误用模式库来检测已知的入侵行为。而如果只基于误用模式库来检测，便不 能发现泰靠的入侵行茺，函诧把两瓣方法结合麓框架哥以提供更高翦检验率和更 快的响应速度。文中提崽的框架( 图1 1 ) 对我们橡建基于数据流的入侵检测模 型框架有一定的借鉴意义。 1 ，a n o m a l yd e t e c t i o n3u p d a t es i g n a t u r e 2s i g n a t u i ee x t r a c t i o n4m i s u s ed e t e c t i o n 图1 。l 蠕虫检测框架图 。 f i g u r e l iw o r md e t e c t i o ns y s t e mf r a m e w o r k 2 0 0 6 年z h e n g j u n 等提穗一种基予数据流方法翡大撬穰霹络异常发瑗方法 【2 8 l ，文书第一次将数据流模型应用予大规模嬲络的异常发现。这种方法在一定程 度上取决于安全策略定制的好坏，没有考察数据包的内容，只适用于流量分析。 文献 2 9 探讨了在线规则的生成模型，文中针对利用传统方法进行入侵检测结果 难于理解的阕逶，提出了一释对入侵检测酶结果( 驿对入侵的数据在线分橱) 熊 北京t 业大学工学硕1 ：学位论文 实时规则在线生成方法，解决了传统方法需要多遍扫描数据库的要求。文中使用 了完全信息树的结构来保存整个历史数据的信息。我们认为提取入侵规则的方法 必须配合基于异常检测机制和误用检测相结合的方法，才更有意义。因为如果只 使用基于误用机制，发现的攻击行为为已知的入侵方式，入侵规则已经存在规则 库中，再次提取入侵规则是没有意义的。如果单独使用基于异常检测机制，检测 过程使用的为由大量正常数据提取得到的正常模式库，入侵数据得到的规则除了 利于管理员理解之外没有其它的用途。在两种检测机制结合的入侵检测系统中， 可以提取正常模式库检测出的入侵规则，加入到入侵库中。 由此可以看出基于数据流技术的入侵检测研究已经引起大家的兴趣，但研究 只是处于起步阶段，没有成熟的成果可供借鉴。要把数据流技术成功的应用到入 侵检测领域需要首先在理论基础、模型框架、算法探索和原型系统研制等方面加 大探索力度，取得突破。 1 3 挖掘数据流中频繁项目集在入侵检测中的应用问题分析 规则库是入侵检测系统的重要组成部分之一，基于异常检测机制的入侵检测 系统能否构建成功的关键是用户正常访问规则库的建立。一般情况下用户正常的 行为发生的次数会远远多于入侵的行为，因此用户正常的行为反映到网络上为频 繁发生的网络访问数据，频繁发生的用户正常访问数据会形成频繁项目集，因此 挖掘频繁项目集是数据挖掘方法在入侵检测应用中的基础。在数据流中挖掘频繁 项目集是数据挖掘领域中的新问题，网络访问数据可以看成无限的数据流，如何 高效的在网络数据流中挖掘频繁项目集是构建入侵检测模型需要研究的一个基 础问题。 数据流中挖掘频繁项目集的目标与在静态数据集中挖掘频繁项目集的目标 是一致的【3 0 1 。但是，在数据流中挖掘频繁项目集面临着许多挑战。( 1 ) 数据流是 持续、高速、无限，不可能用多次扫描的方法挖掘频繁项目集【川；( 2 ) 数据流挖 掘频繁项目集的算法要保证在有限的时间和内存下完成；( 3 ) 数据流的产生是随 时间变化，通常人们关心的是最近的模式，但过去的模式对于挖掘结果也具有不 同程度的影响。由于上述的挑战，研究人员提出了许多新方法来解决在数据流中 发现频繁项目集的问题。同时由于入侵检测系统处理是网络数据流，需要在网络 数据流中挖掘用户的行为模式，为了能准确反映用户的行为模式，必须关注宏观 时间段内( 一周或更长) 数据流中的频繁模式。因此需要使用窗口的概念，窗口 模型的概念对在数据流中挖掘频繁项目集可分为三类p z j ： ( 1 ) 里程碑窗口t 3 3 - 3 4 1 ( l a n d m a r kw i n d o w s ) 关注整个历史阶段数据流中的频繁模式；在里程碑窗口处理模型中，它们总 6 第l 帝绪论 是关注数据流中流过的所有数据，并通过对整个历史数据的分析得到全局性的频 繁模式。的确，全局性的知识模式是许多数据流挖掘中的期望结果。但是，由于 数据流的大容量和不可预测的数据高速的到达，近期的研究表明里程碑窗口处理 模型必须结合快速的近似归纳技术或合适的数据淘汰技术才能真正适合数据流 的挖掘。最有代表性的基于里程碑窗口的数据流挖掘算法是是l o s s yc o u n t i n g 【3 4 1 ，它基于a p d o f i 算法的思想，但是利用近似归纳技术实现数据一次扫描。 从表面上看基于里程碑窗口机制挖掘整个历史数据流中的频繁模式方法可 以用于入侵检测系统中去发现用户历史的行为模式。例如用户正常的行为不仅在 过去是正常的，在将来也会是正常的，所以要发现用户全部正常行为的模式库必 须在整个历史的数据流进行挖掘。然而用户的正常行为模式库会非常的巨大，如 果用里程碑窗口的模式去发现用户正常的行为，内存中会维护巨大的行为模式 库，有限的内存无法维护所有的历史信息。挖掘数据流的关键是发现变化1 3 5 1 ，用 户正常的行为会在一段时间内得到反映，因此只需关注最近一段时间的数据流。 ( 2 ) 滑动窗1 ：3l j u j ( s l i d i n gw i n d o w s ) 关注最近一段时间内( 窗口大小) 的频繁项目集；在滑动窗口处理模型中， 关注点总是放在最近发生的若干事务上，因此，它们的挖掘结果是某段时间内的 局部频繁模式。在大多数的数据流环境中，这种局部模式是不适合的，这是滑动 窗口的固有缺陷。但是，滑动窗口处理模型具有易于理解、设计简单等优点，因 此在数据流挖掘中也得到广泛的研究和应用。2 0 0 3 年，t e n g 等提出了一种称为 f t p d s 算法【3 6 】，它是在滑动窗口中使用统计回归技术来挖掘频繁项集。2 0 0 4 年， c h i 等给出了m o m e n t 算法【3 7 】，它也是基于滑动窗1 ：3 技术的，但是m o m e n t 仅关 注在数据流中如何挖掘频繁闭项集，它可以被期望来减少内存数据结构的规模和 获得较高的挖掘效率。 基于滑动窗口原理的方法，把目标事务限定在最近一段固定的时间内，因此 得到的当前挖掘结果完全依赖于在窗口内最近产生的数据记录，同时为了消除从 当前窗1 ：3 滑出去的数据记录的影响，需要维护所有在窗口中的数据记录。而如果 把这种方法用在基于异常检测机制的入侵检测系统中去发现用户的正常行为模 式( 即频繁模式) ，如果窗口定义的比较小，而入侵数据在段时间内会较多如d o s 攻击，因此入侵的数据在当前窗口中会变的频繁，而频繁的模式我们认为是正常 的行为，这样攻击的模式便会被认为正常的模式。因此要发现真正的正常行为必 须把窗口定义的很大，而内存不能满足这种要求。因此滑动窗口不适合用于入侵 检测模型中去挖掘用户的正常行为模式。 ( 3 ) 衰减窗口 4 1 4 3 j ( d a m p e dw i n d o w s ) 数据流中的每个事务都有个权值，根据权值和时间进行衰减；在衰减窗口 处理模型中，每个事务都对应一个权值，而且这种权值随时间的增加而减少。因 7 北京t 业大学下学硕十学位论文 此，它能在这些权值的控制下考虑历史数据相关信息的保存以及裁减等工作。在 衰减窗1 ：3 处理模型中，比较有代表性的方法是2 0 0 3 年c h a n g 等提出的e s t d e c 算 法1 4 ，它通过定义一个称为衰减因子的参数，使得较早到达数据流的事务的影响 逐渐减弱。2 0 0 3 年，g i a n n e l l 等提出了一种传统的f p t r e e 改造的处理数据流的 算法f p s t r e a m 4 3 1 ，该方法利用不同时间粒度来实现不同时间段的频繁项集的生 成工作。 衰减窗口只是逻辑上的窗口，它可以消除滑动窗口内存上的限制，又能关注 较长时间段内的频繁模式，因此适合用于异常检测去发现用户正常的模式。 1 4 主要研究内容 1 4 1 问题的提出 根据上文的介绍，数据挖掘在入侵检测中的应用已经得到广大研究者的关 注。基于异常的入侵检测具有发现未知的入侵行为的优点，是当前入侵检测技术 的研究热点。如何高效的分析网络数据形成用户的访问模式库是入侵检测需要解 决的重点问题。数据挖掘技术可使数据分析自动化，然而大多研究者关注的是如 何把传统的数据挖掘方法应用到入侵检测中去，传统的数据挖掘技术是基于数据 库技术的，而在入侵检测中的应用方法是事先得到大量的训练数据，用学习算法 处理后得到用于检测入侵的模式库，这种方法的局限性在于用事先得到的训练数 据构造检测模型不能动态的处理用户新的行为，同时随着操作系统和网络规模的 不断扩大，所要处理的数据的规模是海量的，保存之后再进行分析不具有可行性。 鉴于入侵检测系统所要处理的数据具有数据流的特性，在数据流上构建入侵检测 模型更具有合理性。而构建基于数据流的入侵检测模型需要解决以下问题： ( 1 ) 入侵检测模型如何能有效的处理高速的网络数据流。 ( 2 ) 如何在有限内存中存储无限的网络数据流，并能反映用户访问的真实 情况。 ( 3 ) 如何从高速、无限的网络数据流中获得用户网络访问模式。 1 4 2 研究内容 究： 针对构建基于数据流入侵检测模型所面临的问题，本文主要做以下方面的研 ( 1 ) 分析网络数据流的特点并设计基于数据流挖掘技术的入侵检测模型。 ( 2 ) 设计能高效的存储网络数据流并能反映网络真实情况的数据结构。设 8 第l 章绪论 计有效的数据结构处理网络数据流是本文的一个重点工作。 ( 3 ) 设计一种能高效处理网络数据流，获取用户访问模式的学习算法。用 户的正常行为数据反映在网络上会远远的多于入侵数据，因此挖掘网络数据流中 的频繁模式来刻画用户的正常行为。我们不需要关注整个历史阶段的数据流，只 需要对一段时期的数据进行考察，使用衰减窗口机制可以让我们关注较长时间段 的数据流的特点。高效的处理网络数据流算法是本文的一个重点工作。 ( 4 ) 对所设计的入侵检测模型和用户网络访问模式学习算法进行实验验证 和分析。 1 5 本论文的组织形式 本论文共分为四章，其组织结构如下： 第1 章为本文的绪论，介绍了入侵检测的基本概念和数据挖掘技术在入侵检 测系统中的应用情况；同时介绍了在数据流中挖掘频繁项目集的研究发展情况， 并对其是否适合于入侵检测的应用给出分析；最后给出了本课题的研究意义和内 容。 第2 章阐述了基于数据流挖掘技术的入侵检测模型。首先分析数据集k d d 9 9 中的4 种攻击类型的特点，给出了用户行为具有可追踪性的特点，然后介绍了入 侵检测系统处理的数据具有数据流的特点，因此可以使用数据流挖掘技术得到用 户网络访问模式来构建入侵检测模型。用户新到来的行为和得到的用户网络访问 模式进行比较，判断是否有入侵行为发生。 第3 章详细介绍了基于数据流挖掘技术的入侵检测模型的关键部分一后台网 络访问模式学习算法。为了能够高效的处理不断到来的网络数据流，得到用于入 侵检测模式库的用户网络访问模式，本章给出了一种新的适合处理网络数据流的 数据结构m a x f p t r e e ，并在此数据结构的基础上设计了挖掘用户网络访问模式 的算法a p i n n d s 。并给出了算法a p i n n d s 执行示例。 第4 章是实验结果与分析。使用k d d 9 9 数据集对检测模型构建方法和检测 方法进行了性能测试，并对算法a p i n n d s 的性能进行了分析。 最后归纳本文的研究，总结了文章的内容，提出了论文所做的工作以及论文 的创新点，并对今后的工作进行了展望。 9 第2 章基于数据流挖掘技术的入侵榆测模型 第2 章基于数据流挖掘技术的入侵检测模型 构建基于异常检测机制的入侵检测系统需要建立用户正常的的行为库，而在 网络数据流上构建入侵检测模型，需要直接分析网络数据流，用户的行为是否能 够通过分析网络数据流获得是构建基于数据流挖掘技术的入侵检测模型的前提， 因此本章首先分析了用户行为的可追踪性。同时，网络访问数据具有数据流的特 点，本章分析了这一特性，给出了处理数据流的算法所应具有的条件。在用户的 行为可以通过分析网络数据流追踪的前提下，如何构建适合处理高速网络数据流 的入侵检测模型是本章的另外一个重点。 2 1 用户行为的可追踪t i 生 用户的行为是变化多样的，反映到网络上为形式多样的数据，数据是不可确 定的，但行为是可以确定，可以通过分析用户的访问数据构造出可以刻画用户行 为的模型。通过对数据集k d d 9 9 4 4 】中的四类攻击进行分析来说明用户的行为是 可以追踪和刻画的。 ( 1 ) 远程攻击( r e m o t et ol o c a l r 2 l ) 如基于字典的口令猜测。用户正常的 登录行为长时间内会趋于稳定。一个上班族用户，般在每周一至周五的上午九点 进行登录操作，登录过程中很少发生密码输入错误的情况，既使登录密码输入错 误，一般情况也不会超过三次，通常情况下用户登