（计算机应用技术专业论文）关联规则挖掘在入侵检测系统中的研究.pdf

哈尔滨下稗大学硕十学位论文 摘要 随着i n t e r n c t 的快速普及，i n t c m e t 已经在社会政治、经济、文化、军事 等领域中发挥着越来越大的作用。与此同时，在全球范围内，对计算机及网 络基础设施的攻击行为也已经成为一个越来越严重和值得关注的问题，特别 是各种政府机构的网站，更是成为黑客攻击的热门目标。对类似猖獗的入侵 行为的察觉和防护成为各种机构( 无论是商业或是政府机构) 的一个日益迫 切的要求。 虽然对入侵检测方法及技术的研究已经有2 0 多年的历程，但目前入侵检 测系统仍处于相当初级的阶段，由于商业化产品在实施方法上大都采用类似 于反病毒软件的硬编码机制，系统只能检测已知类型的攻击行为，但是对新 的攻击往往无能为力。针对传统入侵检测系统的不足，本文研究了入侵检测 技术和数据挖掘技术，针对网络审计数据的特点，提出一种新的入侵检测方 法，该方法一方面采用了分而治之的思想扩展了f p g r o w t h 算法，将整个数 据库中频集的挖掘分解到一系列的分块滑动窗口中，这样大大减少了频集的 搜索空问从而提高了频集挖掘的效率，另一方面该方法通过轴属性和参照属 性限制了无用频集的生成，这样可以大大提高关联规则提取的质量从而提高 用关联规则方法对入侵模式建模的准确性。同时，本文提出一种基于该方法 的入侵检测模型，并给出一种将该模型应用于基于误用检测技术的入侵检测 系统s n o r t 中的解决方案，使s n o r t 系统不仅能进行误用检测而且可以进行异 常检测。 最后，本文通过实验研究了该方法参数的选取对入侵效果和效率的影响， 并通过实验证明了该方法的频集挖掘效率要优于f p g r o w t h 算法。 关键词：入侵检测；数据挖掘；关联规则；f p - g r o w t h 算法 哈尔滨下程大学硕十学位论文 a b s tr a c t w i t ht h er a p i dd e v e l o p m e n ta n dw i d es p r e a do fi n t e r n e t i n t e m e th a s p l a y e dam o r ea n dm o r ei m p o r t a n tr o l ei nt h ef i e l do fs o c i a lp o l i t i c s ，e c o n o m y ， c u l t u r e ，m i l i t a r ya f f a i r sa n do t h e rs o c i a lf i e l d a tt h es a m et i m e ，o nt h eg l o b a l r a n g e ，i tb e c o m e sam o r ea n dm o r es e r i o u sp r o b l e mw h i c hn e e d st ob ep a i dm o r e a t t e n t i o nt h a tt h ea t t a c k so nc o m p u t e r sa n dn e t w o r ki n f r a s t r u c t u r e e s p e c i a l l y ，t h e w e bs i t e so fg o v e r n m e n t sw h i c hb e c o m ep o p u l a rt a r g e t sa r ea t t a c k e db yh a c k e r s t h e r e f o r e ，ap e r f e c tm e t h o dt op r o t e c to u rs y s t e m sn e e d st ob ef o u n d ，i n t r u s i o n d e t e c t i o ni st h eo n ew h i c hw ef i n dt op r o t e c to u rs y s t e m s a l t h o u g hi n t r u s i o nd e t e c t i o nt e c h n i q u e sa n dt e c h n o l o g yh a sb e e nr e s e a r c h e d f o rm o r et h a n2 0y e a r s ，i n t r u s i o nd e t e c t i o ns y s t e m sa r es t i l li nav e r yp r e l i m i n a r y s t a g ea tp r e s e n t m o s tc o m m e r c i a lp r o d u c t su s et h em e t h o dt h a ti ss i m i l a rt ot h e h a r d w a r ee n c o d i n gm e c h a n i s mo fa n t i v i r u ss o f t w a r e ，m o r e o v e ro n l yt h ek n o w n t y p e so fa t t a c k sc a nb ed e t e c t e db yt h ei n t r u s i o nd e t e c t i o ns y s t e m sw h i c ha r e p o w e r l e s s t ot h en e wt y p e so fa t t a c k s i no r d e rt o g i v eas o l u t i o nt o t h e d i s a d v a n t a g eo ft h et r a d i t i o n a li n t r u s i o nd e t e c t i o ns y s t e m s ，t h ei n t r u s i o nd e t e c t i o n t e c h n o l o g ya n dd a t am i n i n gt e c h n o l o g ya r es t u d i e do nt h i st h e s i s 。a c c o r d i n gt o t h ec h a r a c t e r i s t i c so fn e t w o r ka u d i td a t a , t h et h e s i sp r e s e n t san o v e la p p r o a c ht o d e t e c t i n gi n t r u s i o n t h i sa p p r o a c h , o nt h e o n eh a n d ，e x t e n d st h ef p g r o w t h a l g o r i t h mb ya d o p t i n gt h ei d e ao fd i v i d ea n dr u l e ，w h i c hd i v i d e sf r e q u e n ti t e m s e t s m i n i n gi n t o as e r i e so fb l o c ks l i d i n gw i n d o w st or e d u c et h es e a r c hs p a c eo f m i n i n gf r e q u e n ti t e m s e t sa n de n h a n c e st h ee f f i c i e n c yo fm i n i n gf r e q u e n ti t e m s e t s o nt h eo t h e rh a n d ，t h ep r o p o s e da p p r o a c hl i m i t st h eg e n e r a t i o no ft h eu n w a n t e d f r e q u e n ti t e m st h r o u g ha x i sa t t r i b u t e sa n dr e f e r e n c ea t t r i b u t e s ，w h i c hc a ne n h a n c e t h e q u a l i t yo fe x t r a c t i n ga s s o c i a t i o nr u l e s ，t h e r e f o r e c a ni n c r e a s ea c c u r a c yo f m o d e l i n gt h ei n t r u s i o np a t t e mb ya p p l y i n ga s s o c i a t i o nr u l e sm i n i n g a n d ，t h e t h e s i sc o n s t r u c t si n t r u s i o nd e t e c t i o nm o d e lb a s e dt h ep r o p o s e da p p r o a c ha n da s o l u t i o nt h a ta p p l i e st h ep r o p o s e di n t r u s i o nd e t e c t i o nm o d e li n t os n o r ts y s t e m 哈尔滨t 稗大学硕士学位论文 b a s e dm i s u s ed e t e c t i o nt e c h n i q u es ot h a ts n o r ts y s t e mc a l ld e t e c ti n t r u s i o n b e h a v i o r st h r o u g hm i s u s ed e t e c t i o nt e c h n i q u ea n da b n o r m a ld e t e c t i o nt e c h n i q u e f i n a l l y ，t h ee x p e r i m e n ts h o w sh o wt h es e l e c t i o no fd i f f e r e n tp a r a m e t e r so f t h ep r o p o s e da p p r o a c ha f f e c t st h ee f f e c t i v e n e s sa n de f f i c i e n c yo fi n t r u s i o n d e t e c t i o n a n dt h ee x p e r i m e n ta l s os h o w st h a tt h ee f f i c i e n c yo ft h ep r o p o s e d a p p r o a c hi ss u p e r i o rt of p g r o 、t ha l g o r i t h mi nm i n i n gf r e q u e n ti t e m s e t s k e yw o r d s ：i 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 ，a s s o c i a t i o n ，r u l e s ， f p g r o w t ha l g o r i t h m 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献等的引用己在文中指出，并与参考文献相对应。除文中 已经注明引用的内容外，本论文不包含任何其他个人或集 体已经公开发表的作品成果。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意 识到本声明的法律结果由本人承担。 作者( 签字) ：卫筮量盟芝l 日期：2 0 0 7 年参月彤日 哈尔滨丁程大学硕十学位论文 第1 章绪论 1 1 研究的背景、目的和意义 随着i n t e m e t 的快速普及，网络已经融入到社会、政治、经济、文化、 军事和社会等各个方面。与此同时，在全球范围内，对计算机及网络基础设 施的攻击行为也已经成为一个越来越严重和值得关注的问题。特别是各种政 府机构的网站，更是成为黑客攻击的热门目标。对类似猖獗的入侵行为的察 觉和防护成为各种机构( 无论是商业或是政府机构) 的一个日益迫切的要求。 解决方法之一是按照若干安全策略建立一种能够及时发现并报告入侵行为或 异常现象的安全系统，即入侵检测系统( 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 ) 。 在早期的入侵检测系统中，入侵检测模式是安全专家通过对己知的入侵 方法和系统脆弱性的分析手工编写的。但是由于网络系统的复杂性，安全专 家的知识一般是有限的，因此安全专家所编写的入侵模式有时不能很好地反 映入侵行为，从而导致早期的入侵检测系统的误报率和漏报率较高，缺乏对 未知攻击的检测能力。同时，由于手工操作和基于各自需求的设计开发过程， 使得传统的入侵检测系统缺乏准确性、可扩展性和环境适应性。为了提高传 统入侵检测系统的准确性、适用性和扩展性，越来越多的新技术被融合到入 侵检测的研究中，其中包括神经元网络、基因算法和人工免疫原理。1 9 9 9 年 c o l u m b i a u n i v e r s i t y 的w e n k e l e e 提出了将数据挖掘技术用于入侵检测口i 。结 合数据挖掘的入侵检测技术相对传统的入侵检测技术而言，可以自动地从大 量数据中发现新的入侵模式，减少了入侵检测系统开发过程中对入侵模式的 手工编码。 与此同时，网络带宽飞速增长，“带宽无极限”的说法已经不是一种遥不 可及的假设。网络传输速率提高的速度，要比微处理器快得多。现在，微处 理器的速度已达3 0 0 0 m h z ，而4 年前其速度仅为1 0 0 0 m h z ，4 年内增长了3 倍，而网络传输速率却在3 年内提高了l o 倍。在这样的环境下，网络攻击技 术也呈现出多样化、复杂化和大规模高速化的特点。目前，骨干网以太网的 哈尔滨r 程大学硕士学位论文 带宽已经发展到了1 0 0 0 0 m b p s ，同时网络用户也急剧增长，这使得骨干网或 大型网络流量急剧增高。这时如何在大流量的网络情况下进行入侵检测就是 一个有待研究的课题。 融合了数据挖掘技术的入侵检测系统可以建立一个有效性高的( 低误警 率和低漏报率) 、易于扩展的、环境适应性好、智能的入侵检测系统。本文研 究了数据挖掘和入侵检测的相关文献，针对网络审计记录的特点提出一种新 的入侵检测方法，从而将关联规则挖掘技术应用于入侵检测中，同时在此基 础上提出了基于该方法的入侵检测模型和一种解决方案，该方案将本文提出 的入侵检测模型应用于基于误用检测技术的入侵检测系统s n o n 中，从而使 s n o r t 系统可以同时利用异常检测和误用检测两种技术对入侵进行识别和响 应。 1 2 入侵检测概述 1 2 1 入侵检测的产生和发展 入侵是指任何试图危及资源的完整性、机密性或可用性的活动集合”1 。 入侵通常可以分为六类：尝试性的闯入、伪装攻击、安全控制系统的渗透或 泄露、拒绝服务攻击和恶意使用。入侵检测可以定义为对于面向计算机资源 和网络资源恶意行为的识别和响应。 入侵检测从诞生到现在已经有2 0 多年的历史了，在其发展过程中有几个 重要的里程碑。1 9 8 0 年，j a m e sp a n d e r s o n 在报告计算机安全威胁的监察 中提出，必须改变现有系统审计机制，以便为专职系统安全人员提供全面的 安全信息，此文被公认为是有关入侵检测的最早论述【4 】。1 9 8 5 年，d e n n i n g 和n e u m a n n 提出了一个通用的入侵检测模型，这一模型在入侵检测的研究中 被誉为里程碑之作旧。1 9 9 0 年，l u n t 等对d e n n i n g 提出的模型进行了改进， 提出了与系统平台无关的实时监测思想【6 l 。1 9 9 0 ，h e b e r l e i n 等人提出基于网 络的入侵检测系统n s m ，通过主动监视网络信息流量来检测攻击阴。1 9 9 1 年， n a d i r ( n e t w o r ka n o m a l yd e t e c t i o na n di n t r u s i o nr e p o a e r ) 与d i d s ( d i s t r i b u t e i n t r u s i o nd e t e c t i o ns y s t e m ) 提出了收集和合并处理来自多个主机的审计信息 从而用以检测针对一系列主机的协同攻击嗍。1 9 9 4 年，m a r kc r o s b i e 和g e m 哈尔滨t 程大学硕十学何论文 s p a f f o r d 提出用自治代理来提高入侵检测系统的性能m 。1 9 9 6 年g r i d s 的设 计和思想解决了当时大多数入侵检测系统伸缩性不足的问题，使得对大规模 自动或协同攻击的监测更为便利。 近年来在入侵检测领域又有了一些新的研究，如s f o r r e s t 把免疫原理运 用于入侵检测系统中】，r o s s a n d e r s o n 和a b i d ak h a t t a k 将信息检索技术引进 到入侵检n t , 2 j ，s a n d e e pk u m a r 和g e n es p a f f o r d 设计的着色p e t r i 网( c p - n e t ) 1 3 1 ，采用状态转换技术来优化误用检测系统，s u p e l e d 将基因算法作为检测方 法而设计了g a s s a t a 系统4 】，w e n k el e e 等用数据挖掘技术实现了在海量 数据中发现隐含特征模式1 1 5 。 1 2 2 入侵检测的分类 入侵检测基于的重要前提是入侵行为与合法行为是可区分的，也就是说 可以通过提取行为的模式特征来判断该行为的性质。基于这一前提可将入侵 检测分为两类：异常检测和误用入侵检测。 ( 1 ) 异常入侵检测 异常入侵检测主要思想是建立计算机系统中正常行为的模式库，然后根 据所采集的统计数据与正常行为的偏差，确定是否有异常行为发生。例如， 给用户、工作站、服务器、文件等资源对象定义变量( 如c p u 利用率、内存 利用率和文件校验和) ，通过分析历史统计数据和预定义的期望值，为每个变 量建立一个基值，当发生系统活动时，如果这些变量的数值与其相应的基值 的偏差大于某个预定义的偏差，则说明系统中有异常行为发生。在入侵检测 技术发展的早期，主要是采用异常入侵检测，优点是能识别的攻击类型广泛， 包括未知的攻击方法，缺点是计算复杂、漏报高和误报率高。这类检测技术 包括概率统计方法和神经元网络方法。 ( 2 ) 误用入侵检测 该方法直接对入侵行为进行特征化描述，建立某类入侵行为的特征模式， 如果发现当前行为与某个入侵模式一致，就表示发生了入侵。随着对计算机 系统弱点、漏洞和入侵行为分析的深入研究，误用检测在入侵检测技术中起 到越来越重要的作用。其优点主要是：检测过程简单、检测效率高和检测精 度高，一般情况下不存在误报率，可依据检测到的不同攻击类型，采取不同 哈尔滨t 稃大学硕十学位论文 的响应措施。但是，由于攻击手段的种类繁多、技术复杂、且不断发展，目 前的误用检测方法缺乏系统化，对多种攻击类别检测时的整体效率低下，同 时误用检测也无法检测未知的攻击。误用检测技术的发展正受到对入侵活动 的分析方法和攻击分类研究的限制。 1 2 3 入侵检测系统 入侵检测系统( i d s ) 是一套运用入侵检测技术对计算机或者网络资源 进行实时检测的系统工具d 6 。i d s 一方面检测未经授权的对象对系统的入侵， 另一方面还监视授权对象对系统的非法操作。因此，一个入侵检测系统需要 解决两个基本问题：一是如何充分、可靠地提取描述行为特征的数据；二是 如何根据特征数据高效并准确地判定行为的性质。目前主要的方法是通过监 视受保护系统的状态和活动，发现非授权的或恶意的系统及网络行为。入侵 检测系统原理如图1 1 所示。 图1 1 入侵检测系统原理图 从功能逻辑上来讲，入侵检测系统由探测器、分析器和用户接口组成。 ( 1 ) 探测器 主要负责收集数据。探测器的输入数据源包括任何可能包含入侵行为线 索的系统数据，比如说网络数据包、日志文件和系统调用记录等。探测器将 这些数据收集起来，然后发送到分析器进行处理。 ( 2 ) 分析器 哈尔滨t 稃大学硕十学位论文 分析器又称为检测引擎，它负责从一个或者多个探测器处接受信息，并 通过分析来确定是否发生了非法入侵检测活动。分析器模块的输出为标识入 侵行为是否发生的指示信号，例如一个警报信号，该指示信号还可能包括相 关的提示信息。另外，分析器组件还能够提供关于可能的响应措施的提示信 息。分析器是入侵检测系统的核心模块。分析器采用基于异常的入侵检测或 采用基于误用的入侵检测。 ( 3 ) 用户接口 入侵检测系统的用户接口使得用户易于观察系统的输出信号，并对系统 行为进行控制。在某些系统中，用户接口又被称为“管理器”、“控制器”、或 者“控制台”等。 ( 4 ) 管理员 管理员的主要工作是根据安全需求编制安全策略以及根据安全策略配置 探测器和分析器。 ( 5 ) 操作员 操作员的主要工作是监视入侵检测系统的运行状态。当入侵检测系统发 出报警时，操作员可以提示信息采取相应的应急措施。 根据分析器所采用的检测技术的不同，入侵检测系统可以分为基于异常 检测的入侵检测系统和基于误用检测的入侵检测系统。这两类入侵检测系统 的不同之处在于： ( 1 ) 所需的知识 对于基于误用检测技术的i d s ，如果要检测到所有攻击行为的话，那么 它就需要知道所有可能攻击行为的先验知识。该类i d s 为此必须识别任何攻 击行为的细节过程，或者标识该类攻击行为的特征模式。而对于基于异常检 测技术的i d s 而言，它必须记录已知的系统期望行为的所有信息，才能够检 测到所有的入侵行为。 ( 2 ) 配置的难易度 一般说来，基于误用检测技术的i d s 比起基于异常检测技术的i d s 需要 少得多的配置工作，因为后者需要对系统的已知行为模式做全面综合的定义。 这就要求用户去发现、理解并表示和维护目标系统的所有正常状态。但是， 有些基于误用检测技术的i d s 也允许用户创建自己的特征模式文件，这样也 哈尔滨下程大学硕十学位论文 将会增加系统配置的难度。 ( 3 ) 报告的数据 基于误用检测技术的i d s 一般在模式匹配的基础上生成最后结论。其具 体输出形式可以是一条指示特定攻击行为发生的报警信号，其中还包含相关 的提示信息数据。而基于异常检测技术的i d s 的输出数据通常是建立在实际 活动行为与系统期望行为的统计偏差的基础上的报警信号。由于任何偏离期 望行为范围的事件都要被报告给系统管理员，所以基于异常检测技术的i d s 通常要比基于误用检测技术的i d s 生成更多的报警信号。 1 2 4 已有入侵检测系统的不足 目前商业化i d s 通常是基于误用检测技术，在实施方法上大都采用类似 于反病毒软件的手动编码机制，这显然不适合日益变化的网络攻击行为。实 验室研究虽然提出了各种新方法来检测新类型攻击行为，但离实用还有相当 的距离。当前研究机构和工业界的入侵检测系统普遍存在的最突出的共性问 题是： ( 1 ) 缺少有效性。现存的规则库和知识库都是根据安全专家的知识进行 手工编写的，面对复杂的网络环境，专家知识往往不全面、不精确。 ( 2 ) 缺少适用性。由于安全专家仅集中分析己知的攻击方法和系统漏洞， 所以系统无法检测未知的攻击。对于新出现的攻击方法，安全专家需要时间 去学习从而提出检测方法，这大大增加了系统检测新攻击的时间。 ( 3 ) 缺少扩展性。专家规则和统计方法一般都是针对特定的网络环境， 因此，很难在新的网络环境下实现i d s 的再利用。 总之，入侵检测技术处于快速发展之中，但目前还不够成熟。在商业产 品领域，方法、技术的单一性限制了入侵检测系统在性能上的进一步提高； 在研究领域，科研人员尝试着使用各种各样的方法，但目前为止，还缺乏一 个全面的、指导性的理论框架，大量的研究还需要进一步深入。 1 3 本文研究的主要内容及内容安排 在研究传统入检测系统的不足和数据挖掘技术的基础上，本文提出一种 新的入侵检测方法，该方法一方面采用了分而治之的思想扩展了f p - g r o 州h 6 哈尔滨下程大学硕士学位论文 算法，将整个数据库中频集的挖掘分解到一系列的分块滑动窗口中，这样大 大减少了频集的搜索空间从而提高了频集挖掘的效率，另一方面该方法通过 轴属性和参照属性限制了无用频集的生成，这样可以大大提高关联规则提取 的质量从而提高用关联规则方法对入侵模式建模的准确性。同时，本文提出 一种基于该方法的入侵检测模型，并给出一种将该模型应用于基于误用检测 技术的入侵检测系统s n o r t 中的解决方案，该方案使s n o r t 系统不仅能进行误 用检测而且可以进行异常检测，扩大了它的检测范围。本文的主要工作是围 绕以下几个方面进行的： 1 讨论数据挖掘在入侵检测中的应用。首先介绍了入侵检测基本概念和 入侵检测系统原理，其次介绍了数据挖掘的基本概念，最后介绍了数据挖掘 在入侵检测中的应用。 2 研究关联规则挖掘。首先介绍了关联规则的基本概念，并通过一个实 例分析了关联规则挖掘算法中的两个典型算法，提出了这两种算法的不足以 及国内外研究人员对这两算法的改进。 3 研究关联规则挖掘技术在入侵检测系统中的应用。首先研究用关联规 则对入侵模式进行建模的方法，通过改进了f p g r o w t h 算法的频集挖掘过程 和使用轴属性和参照属性提出了一种新的入侵检测方法。其次提出了一种基 于该方法的入侵检测模型。最后提出一种解决方案，该解决方案将本文提出 的入侵检测方法应用于基于误用检测技术的入侵检测系统s n o r t 中，从而使 s n o r t 系统可以同时进行误用检测和异常检测。 本文的章节安排以上述内容为主，具体安排如下： 第1 章叙述了课题的研究背景和意义，并概述了入侵检测技术。 第2 章概述了数据挖掘技术在入侵检测系统中的应用。介绍了数据挖掘 的定义及其主要任务，例如：分类和预测，聚类，关联分析，和时序模式。 在本章的最后分析介绍了分类、聚类和关联分析在入侵检测中的应用，并讨 论了基于数据挖掘的入侵检测系统的优缺点。 第3 章研究关联规则。介绍了关联规则的基本概念。其次，分析了关联 规则挖掘所要解决的基本问题即频集的挖掘和关联规则的提取，并讨论了频 集挖掘时的所需的搜索空间以及可以采用的搜索策略。最后，通过一例子分 析了两个关联规则的经典算法即a p r i o r i 算法和f p g r o w t h 算法，并分析了每 哈尔滨丁程大学硕十学位论文 种算法的不足以及国内外学者对它们的改进。 第4 章研究关联规则挖掘技术在入侵检测系统中的应用。首先，针对网 络入侵检测审计记录的特点提出一种新的入侵检测方法，该方法一方面采用 了分而治之的思想扩展了f p g r o w t h 算法，将整个数据库中频集的挖掘分解 到一系列的分块滑动窗口中，这样大大减少了频集的搜索空间从而提高了频 集挖掘的效率，另一方面该方法通过轴属性和参照属性限制了无用频集的生 成，这样可以大大提高关联规则提取的质量从而提高用关联规则方法对入侵 模式建模的准确性。其次，提出一种基于该方法的入侵检测模型并提出了一 种将该模型应用于基于误用检测技术的入侵检测系统s n o r t 中的解决方案。 最后，通过实验研究了本文所提出的入侵检测方法的参数的选取对入侵效果 和效率的影响，并通过实验证明了本文所提出方法的频集挖掘效率要优于 f p g r o w t h 算法。 结论是对全文的总结和对今后工作的展望。 哈尔滨t 程大学硕士学位论文 第2 章数据挖掘技术在入侵检测中的应用 2 1 数据挖掘概述 2 1 1 定义 数据挖掘公认的定义是由u m f a y y a d 等人提出的：数据挖掘就是从大 型数据集( 可能是不完全的、有噪声的、不确定的、各种存储形式的) 中提取 出人们感兴趣的知识，这些知识是隐含的、先前未知的和对决策有潜在价值 的，提取的知识表示为概念、规则、规律和模式等形式旧。 谈到数据挖掘，必须提到数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ，r , d d ) 。1 9 8 9 年8 月在美国底特律召开的第1 1 届国际人工智能联 合会议的专题讨论会上，知识发现首次被提出。k d d 的出现很好地满足了 数据处理的需要。知识发现是一个交互、重复进行的过程，包括的步骤如图 2 1 所示。 图2 1知识发现的过程 ( 1 ) 数据选择，了解知识发现所要应用的领域，包括相关必备知识和应 用知识发现的目标。 ( 2 ) 目标数据的提取，该目标数据是原始数据的个子集。 ( 3 ) 数据的净化处理，包括去除无用数据和处理丢失的数据。由于现实 中数据规模大，不完整或缺乏一致性，因此在进行数据挖掘之前必需对数据 9 哈尔滨t 程大学硕七学位论文 净化。 ( 4 ) 数据的整合，包括整合多维、异质的数据源。 ( 5 ) 数据的映射，包括用某种映射方式找出可以描述数据的属性( 所选 的属性取决于应用的目标) 。 ( 6 ) 数据挖掘功能的选取，包括确定由数据挖掘算法所发现的模型的功 能( 即：概念描述、分类、回归、聚类、w e b 挖掘、关联规则的提取或者这 些功能的组合) 。 ( 7 ) 数据挖掘算法的选取，即确定用于寻找模式的方法。针对特定的应 用目标，主要看选取哪个模型或者哪些参数合适。 ( 8 ) 数据挖掘，找出数据中有用的模式。 ( 9 ) 解释，解释所挖掘出的模式并尽可能将其可视化。这样可以帮助数 据分析员自动或半自动地分析模式，从而帮助数据分析员确定哪些模式对用 户是有用的。 ( 1 0 ) 使用被发现的知识。 因此，数据挖掘是k d d 过程中的一个步骤。把数据挖掘作为k d d 的一 个重要步骤看待，可以使本文更容易聚焦研究重点，从而有效解决问题。 2 1 2 数据挖掘的主要任务 数据挖掘的主要任务有：概念描述、分类和预测、聚类、关联分析、时 序模式等l i | l 。 ( 1 ) 概念描述 概念描述本质上就是对某类对象的内涵特征进行概括。一个概念常常是 对一个包含大量数据的数据集合总体情况的概述。如对一个商店所售电脑的 配置信息总结就会获得所售电脑基本情况的一个整体概念( 如：基本上为p 4 以 上的兼容机) 。对含有大量数据的数据集合进行概述性的总结并获得简明、准 确的描述，这种描述就称为“概念描述”。概念描述分为特征性描述和区别性 描述。前者描述某类对象的共同特征，后者描述不同类别对象之间的区别。 ( 2 ) 分类和预测 分类是数据挖掘中的一个重要的目标和任务。目前的研究在商业上应用 最多。分类就是对数据的过滤、抽取、压缩以及概念提取等。分类的目的是 1 0 哈尔滨t 程大学硕十学位论文 学会一个分类函数或分类模型( 也常常称作分类器) 。由于数据挖掘是从数据 中挖掘知识的过程，因此要构造这样一个分类器，分类器的作用就是能够根 据数据的属性将数据分派到不同的组中，即：分析数据的各种属性，并找出数 据的属性模型，确定哪些数据属于哪些组。这样就可以利用该分类器来分析 已有数据，并预测新数据将属于哪一个组，即数据对象的类标记，然而，在 某些应用中，人们可能希望预测某些空缺的或不知道的数据值，而不是类标 记。当被预测的是数值数据时，通常称之为预测。分类模式可以采用多种形 式表示，如分类规则、判定树、数学公式或神经网络。可应用于分类知识挖 掘的一些有代表性的技术有：判定树归纳、贝叶斯分类、神经网络、k 最近 邻、遗传算法、粗糙集等方法。 分类应用的实例很多。例如，可以将银行网点分为好、一般和较差三种 类型，并以此分析这三种类型银行网点的各种属性，特别是位置、盈利情况 等属性，并决定它们分类的关键属性及相互间关系。此后就可以根据这些关 键属性对每一个预期的银行网点进行分析，以便决定预期银行网点属于哪一 种类型。 ( 3 ) 聚类 数据库中的数据可以划分为一系列有意义的子集，即类。在同一类内的 对象之间具有较高的相似度，而类之间的对象差别较大。聚类增强了人们对 客观现实的认识，即通过聚类建立宏观概念。例如自行车、汽车、火车都属 于交通工具。 聚类中用到的方法包括统计分析、机器学习和神经网络等。在统计分析 方法中，聚类分析是基于距离的聚类，如欧氏距离，海明距离等。这种聚类 分析方法是一种基于全局比较的聚类，它需要考察所有的个体才能决定类的 划分。 在机器学习方法中，聚类是无导师的学习。在这里距离根据概念的描述 来确定，故聚类也称概念聚类，当聚类对象动态增加时，概念聚类则称为概 念形成。 在神经网络中，自组织神经网络方法用于聚类。如a r t 模型、k o h o n e n 模型等，这是一种无监督学习方法。当给定距离阈值后，各样本按给定的阈 值进行聚类。 哈尔滨下程大学硕十学忙论文 ( 4 ) 关联分析 关联分析主要用于发现不同事件之间的关联性，即一个事件发生的同时， 另一个事件也经常发生。关联分析的重点在于快速发现那些有实用价值的关 联发生的事件。其主要依据是事件发生的概率和条件概率应该符合一定的统 计意义。 对于结构化的数据，以客户的购买习惯数据为例，利用关联分析，可以 发现客户的关联购买需要。例如，一个开设储蓄账户的客户很可能同时进行 债券交易和股票交易，购买纸尿裤的男顾客经常同时购买啤酒等。利用这种 知识可以采取积极的营销策略，扩展客户购买的产品范围，吸引更多的客户。 通过调整商品的布局便于顾客买到经常同时购买的商品，或者通过降低一种 商品的价格来促进另一种商品的销售等。 对于非结构化的数据，以空间数据为例，利用关联分析，可以发现地理 位置的关联性。例如，8 5 的靠近高速公路的大城镇与水相邻，或者发现通 常与大型超市相邻的对象等。 国内外关于关联规则挖掘算法的研究可以分为六类：频繁项集的挖掘、 频繁闭项集的挖掘和最大频繁项集的挖掘、并行和分布式挖掘和增量更新式 挖掘。 ( 5 ) 时序模式 通过时间序列搜索出重复发生概率较高的模式。这里强调时间序列的影 响。例如，在所有购买了激光打印机的人中，半年后8 0 的人再购买新硒鼓， 2 0 的人用旧硒鼓装碳粉；在所有购买了彩色电视机的人中，有6 0 的人再 购买v c d 产品。在时序模式中，需要找出在某个最小时间内出现比率一直 高于某一最小百分比( 阈值) 的规则。这些规则会随着形式的变化做适当的调 整。时序模式中，一个有重要影响的方法是“相似时序”。用“相似时序”的方 法，要按时间顺序查看时间事件数据库，从中找出另一个或多个相似的时序 事件。例如在零售市场上，找到另一个有相似销售的部门，在股市中找到有 相似波动的股票等。 2 2 数据挖掘技术应用于入侵检测 哈尔滨t 程大学硕十学位论文 2 2 1 数据挖掘在入侵检测中的应用 很多数据挖掘方法都能应用于入侵检测系统，每一种方法都有它独特的 优势，下面就三种常用于入侵检测的数据挖掘分析方法来概述一下数据挖掘 在入侵检测中的应用肛z ”。 ( 1 ) 分类在入侵检测中的应用 分类分析是数据挖掘领域重要的研究课题之一，其目标是建立基于属性 的分类属性模型。数据分类一般分为两步：第一步，选择一个数据集进行训 练。首先，在训练前，为训练数据集中的每个元组( 训练样本) 增加一个类 标号。例如，在入侵检测中可以根据黑客入侵行为的危害程度将类标号赋值 为：正常、弱入侵、般入侵、强入侵。然后，通过分析由属性所描述的训 练数据集元组来构造学习模型。由于事先提供了每个训练样本的类标号，所 以该步也称作为有指导的学习过程。通常，学习模型可用分类规则、判定树 或者数学公式的形式表示。第二步，对模型进行分类。首先评估模型( 分类 规则) 的预测准确率，对于每个测试样本，将已知的类标号与该样本的类预 测标号进行比较，模型在给定测试集上的准确率是被模型分类的测试样本的 百分比。如果模型的准确率可以被接受，就可以用它来对类标号未知的数据 元组或对象进行分类。 ( 2 ) 聚类分析在入侵检测中的应用 聚类分析是识别数据对象的内在规则，将对象分组以构成相似对象类， 并导出数据分布规律。分类与聚类的区别在于分类是将分类规则应用于数据 对象，而聚类是发现隐含于混杂数据对象中的分类规则。p o r t n o y 提出基于聚 类分析的入侵检测算法( 无监督异常检测算法) ，通过对未标识数据进行训练 检测入侵。 该算法是基于两个假设：第一，正常行为记录数目远大于入侵行为记录 数目：第二，入侵行为本质上与正常行为不同。算法基本思想在于入侵模式 与正常模式本质上不同，则它们将出现在正常模式范畴之外，因此能够被检 测出来。算法将原始数据进行正规化处理转换为标准形式，采用标准欧几里 德度量，使用改进单链法聚类，经过标识，通过分类以检测入侵行为，但该 算法不适用于恶意攻击和拒绝服务攻击的检测。 哈尔滨t 程大学硕十学位论文 ( 3 ) 关联规则分析在入侵检测中的应用 关联规则是数据挖掘技术中最为广泛应用的技术之一，也是最早用于入 侵检测的技术。最早运用这种技术是作为一种工具去产生关于网络流量报告。 发现关联规则问题就是发现所有支持度和可信度均超过预先设定的阈值 的关联规则，这个发现过程分为两步：第一步识别所有频繁项目集即所有支 持度不低于用户事先规定的最小支持度阈值的项目集；第二步是从第一步得 到的频繁项集中生成置信度不小于用户事先设定的最小置信度阈值的规则。 应用在网络流量分析上，可以将一次连接看作是一个事务t ，将采集到的很 多连接记录组成事务数据库d ，每个事务t 由t i m e ，d u r a t i o n ，s e r v i c e ，s r c _ h o s t ， d s th o s t ，d s tb y t e s ，f l a g 共7 项组成，事务的唯一标识符为t i m e ，其中s e r v i c e 为服务( 或目的的端口号) ，s r ch o s t 为源主机，d s th o s t 为目的主机，d s t b y t e s 为源主机发出的数据包大小，f l a g 为标记。 下面列举一个关联规则：1 0 ，9 0 ，s r ch o s t = 2 0 2 3 8 2 1 4 1 8 8 ， d s th o s t = 2 0 2 6 6 3 0 7 ，s e r v i c e = w w w 。规则的含义为：在所有的网络流量中 有1 0 的连接符合源主机i p 为2 0 2 3 8 2 1 4 1 8 8 ，目的主机的i p 为2 0 2 6 6 3 0 7 的情况下，连接访问报务有9 0 的可能为w w w 服务。 2 2 2 基于数据挖掘技术的入侵检测系统的优缺点 数据挖掘技术在入侵检测系统的应用中有如下优点： ( 1 ) 自适应性好 传统入侵检测系统规则库的建立需要一个安全专家小组根据现有的某一 攻击方法去发现它的特征并继而开发出它的检测工具，然而要一个系统总能 很快地跟上入侵技术的发展是不可能的。同时，针对每一种新的攻击方法更 换系统的代价是很大的。由于应用数据挖掘技术的异常检测不是基于模式匹 配，它并不就每一个特别的模式进行检测，所以就不存在这个问题，表现出 一定程度的自适应性。 ( 2 ) 误报率低 现有的系统过度依赖于单纯的模式匹配，它发出的报警可能远远多于实 际的情况，在某种正常的工作中如果包含( 这是很有可能的) 这种模式的话， 就必然产生误报。采用数据挖掘的系统可以从报警发生的序列发现某种规律 1 4 哈尔滨下程大学硕十学位论文 从而滤出那些正常的行为产生的模式。数据挖掘方法还可以有效地剔除重复 的攻击数据，因而具有较低的误警率。 ( 3 ) 漏报率低 当一种新的以前从未出现过的攻击方式出现时，或者当一种攻击改变它 的某些方式时，传统的系统很有可能就不会产生反应。而应用数据挖掘技术 的入侵检测系统就可以很快地发现新的攻击，在很大程度上减少了漏报的可 能。 ( 4 ) 减轻数据过载 对于传统的入侵检测系统另外一个需要考虑的问题是需要多少的数据 才能准确地发现一个攻击。现在网络上的数据流量越来越大，例如一个跨国 公司的网络每天所产生的流量以及各种网络记录是非常庞大的，在这么大规 模的数据中发现入侵行为对传统的入侵检测系统来说是一个很大的挑战。而 应用数据挖掘技术可以很好地解决这个问题，现有的数据挖掘算法通过发掘 数据之间的关系，可以为分析提供不同数据特征的刻画。特别是可以将以前 的结果和最新的数据加以综合，这样可以大大减少不必要的数据。 经过深入分析发现，尽管基于数据挖掘的入侵检测模型在检测性能和通 用性方面具有很大的优势，但是，在实现和采用此类系统中仍然存在一定困 难。主要有以下几个方面： ( 1 ) 检测的效率方面：由于是对大量历史数据处理，检测模型在学习和 评价阶段的计算成本高，实时发现入侵比较困难。 ( 2 ) 使用性能方面：系统需要大量的训练数据，而且系统的配置比传统 系统更加复杂。 ( 3 ) 尚未考虑检测模型自身安全性问题。 2 3 本章小结 本章首先介绍了数据挖掘的基本定义和其主要任务，例如：分类和预测， 聚类，关联分析和时序模式等。然后概述了数据挖掘在入侵检测中的应用， 重点说明了数据挖掘中分类分析、聚类分析和关联规则分析如何应用于入侵 检测中。最后分析了基于数据挖掘的入侵检测的优缺点。 哈尔滨t 稗大学硕士学位论文 3 1 定义 第3 章关联规则挖掘的基本原理 定义3 1 ：k 项集 一个商品或者一个属性称为一个项目。多个项目的集合称为项集。设i 为数据库d 中全体项目的集合，集合x = ( i j i 2 ，i k ) ( x 互