（计算机应用技术专业论文）孤立点挖掘技术在异常检测中的应用研究.pdf

摘要 随着i n t e r n e t 覆盖范围的不断扩大、计算机与网络技术研究的不断深入， 网络安全作为一个无法回避的问题呈现在人们面前。如何保障信息安全、防范网 络入侵已经成为人们最为关心的问题。入侵检测技术作为一种主动的网络信息安 全保障措施，可以有效地弥补传统安全防护技术的不足，已经成为网络安全领域 的研究热点。 我们所研究的内容主要集中在基于无监督的异常检测技术的研究上。本文首 先阐述了入侵检测系统定义、理论、分类和模型等，然后分析了各种入侵检测方 法的优缺点；结合当前一些基于数据挖掘的入侵检测的研究成果，分析了基于有 监督的数据挖掘方法在入侵检测中存在的问题，指出了无监督入侵检测研究的意 义；提出了基于孤立点挖掘的异常检测技术，分析了该方案的可行性，设计了两 种孤立点挖掘的异常检测实现技术，利用k d d 9 9 数据和t c p d u m p 数据验证了该技 术的异常检测性能；在论文最后介绍了我们所设计的一个异常检测原型系统。本 文主要创新点如下： ( 1 ) 根据对入侵事件的特征分析，将孤立点挖掘技术引入到异常检测领域，提 出了一种全新的基于孤立点挖掘的无监督异常检测技术； ( 2 ) 针对h i l o u t 算法所存在的不足进行改进，提出一种基于索引树的孤立点 挖掘算法t r e e o u t 。该算法避开了原先复杂的h i l b e r t 编号的生成，通过 r - r e g i o n 和索引树来估算数据的权值上下界，大大减少了数据点间的距 离计算。 ( 3 ) 提出了一种基于b i r c h 的孤立点挖掘算法b i r c h o u t 算法。算法利用 c f - t r e e 结构快速查找每个数据的近似的最近邻居集，来估算权值，有效 克服了在孤立点挖掘中精确计算权值存在的复杂度高的问题。 关键词：异常检测孤立点挖掘k 一最近邻 a p p l i e dr e s e a r c ho f o u t l i e rm i n i n gt e c h n o l o g yi na n o m a l y d e t e c t i o n a b s t r a c t t h en e t w o r ks e c u r i t yb e c o m e sa l lu n a v o i d a b l ep r o b l e ms h o w i n gi nf o n to fp e o p l e ，w i t h c o v e r a g eo ft h ei n t e r n e tc o n t i n u e st oe x p a n d h o wt op r o t e c ti n f o r m a t i o ns e c u r i t ya n dp 他v e n t n e t w o r ki n t r u s i o nh a v eb e c o m et h em o s tc o n c e r n e di s s u e s a sap r o a c t i v ei n f o r m a t i o ns e c u r i t y m e a s u r e , i n t r u s i o nd e t e c t i o nt e c h n o l o g yc a l le f f e c t i v e l yc o m p e n s a t ef o rt h es e c u r i t ya n dp r o t e c t i o n o f t r a d i t i o n a lt e c h n i c a ls h o r t a g e s , w h i c hh a sb e c o m et h eh o t s p o ta r e a so fn e t w o r ks e c u r i t y o u rs t u d i e sm a i n l yf o c u so nt h eu n s u p e r v i s e da n o m a l yd e t e c t i o nt e c h n o l o g y t h i sp a p e r s h o w st h et h e o r y , t h ed e f i n i t i o n , a n dt h em o d e lo fi n t r u s i o nd e t e c t i o ns y s t e m s t h e nw ea n a l y z e t h ea d v a n t a g e so ft h ei d sc a t e g o r i e s c o m b i n i n gt h er e s e a r c ho ft h ed a t am i n i n g - b a s e di n t r u s i o n d e t e c t i o n , w ea n a l y z e dt h ep r o b l e m se x i s t i n gi nt h e i n t r u s i o nd e t e c t i o nt e c h n o l o g yb a s e do n s u p e r v i s e dd a t am i n i n g a n dw ef i g u r eo u tt h es i g n i f i c a n c eo fu n s u p e r v i s e di n t r u s i o nd e t e c t i o n f i n a l l ya ni n t r u s i o nd e t e c t i o nt e c h n o l o g yb a s e d o no u t l i e rm i n i n gw a sp r o p o s e d w ea n a l y z e dt h e f e a s i b i l i t yo fo u t l i e rm i n i n gb a s e da n o m a l yd e t e c t i o n , a n dd 懿i g n e dt w oa n o m a l yd e t e c t i o n m e t h o d sb a s e do no u t l i e rm i n i n g t h ep e r f o r m a n c eo ft h et e c h n o l o g yh a sb e e nv a l i d a t e db yu s i n g t h ek d d c u p 9 9 f i n a l l yw ed e s i g n e dap r o t o t y p es y s t e mf o ra n o m a l yd e t e c t i o nf o ri n t e g r a t e d e x p e r i m e n t s t h em a i ni n n o v a t i o n si nt h i sp a p e ra r es h o w e da sf o l l o w s ： ( 1 ) b a s e do nt h ec h a r a c t e r i s t i c so ft h ei n t r u s i o n s , w ea p p l i e dt h eo u t l i e rm i n i n gm e t h o dt o t h e 部他ao fa n o m a l yd e t e c t i o m ( 2 ) af 删o u t l i e rm i n i n ga l g o r i t h mn a m e dt r e e o u ti sp r o p o s e dt os o l v et h ep r o b l e m si nt h e h i l o u ta l g o r i t h m i ti m p r o v e so nt h eh i l o u ta l g o r i t h mt oa v o i dt h ec o m p l e xg e n e r a t i o n o fh i l b e r tv a l u ea n dc a l c u l a t e st h eu p p e ra n dl o w e rb o u n do ft h ew e i g h to fe a c hr e c o r d w i t hr - r e g i o na n di n d e xt r e et oa v o i dm m e c e s s m yd i s t a n c ec a l c u l a t i o n ( 3 ) a n o t h e rn e wo u t l i e rm i n i n ga l g o r i t h mb a s e do nb i r c hi sp r o p o s e dt os e a r c ht h e k - n e a r e s tn e i g h b o r so fe a c hd a t ap i d i mf l e e t l yb yu s i n gt h es t r u c t u r eo fc f - t r e e i t e s t i m a t e se v e r yw e i g h tm o r ee f f e c t i v e l y k e y w o r d ：a n o m a l yd e t e c t i o n , o u t l i e rm i n i n g , k - n e a r e s tn e i g h b o r s 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。本人在 论文写作中参考的其他个人或集体的研究成果，均在文中以明确方式标明。 本人依法享有和承担由此论文产生的权利和责任。 声明人( 签名) 景桶 川年莎月，日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大学有权保留 并向国家主管部门或其指定机构送交论文的纸质版和电子版，有权将学位论文用 于非赢利目的的少量复制并允许论文进入学校图书馆被查阅，有权将学位论文的 内容编入有关数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密的 学位论文在解密后适用本规定。 本学位论文属于 1 保密( ) ，在年解密后适用本授权书。 2 不保密( 0 ( 请在以上相应括号内打“一) 作者签名： 导师签名 6 窍 易月 ，1 3 r 日 第一章绪论 第一章绪论 1 1 引言 网络技术，特别是i n t e r n e t 的发展极大地促进了社会信息化的发展，人们 的生活、工作和学习等已经越来越离不开i n t e r n e t ，i n t e r n e t 给人们带来了很 大的方便的同时，基于i n t e r n e t 的计算机网络信息的安全也变得越来越重要。 根据权威机构统计，每年由于黑客的攻击造成的损失有数十亿美元。而且据有关 调查统计，2 0 0 1 年全球每干部电脑在一个月平均遭受网络攻击的次数达到1 1 3 次，其中6 0 来自黑客攻击。 严峻的现实让人们清醒地认识到计算机网络的发展离不开信息安全技术的 保障，随着人们安全意识的提高，安全领域的探索和研究日益深入，网络安全的 问题也是越来越受到各方面的重视。 信息安全概念是随着信息技术的发展而不断拓展、不断深化的，从早期的通 信安全，发展到计算机安全、信息系统安全，现在已扩展到对信息基础设施、应 用服务和信息内容实施全面保护的信息安全保障。信息安全的内涵也不断丰富， 由单一的对通信信息的保密，拓展到对信息的保密性、完整性、真实性、可控性， 信息基础设施的可用性以及交互行为的不可否认性的全面保护，还包括在信息作 战条件下的积极防御。但是目前常用的解决网络安全问题方法( 身份认证技术、 访问控制和防火墙) 都存在一定的局限性： ( 1 ) 身份认证技术不能有效抵御弱口令、字典攻击、特洛伊木马、网络 探测以及电磁辐射等攻击手段； ( 2 ) 访问控制不能有效抵御入侵者利用系统漏洞或程序漏洞绕过访问控 制、非法权限提升或非法文件读写； ( 3 ) 防火墙一不能有效阻止内部入侵行为。 因此人们开始研究积极的防御手段入侵检测技术。从技术层面上讲入侵 检测是对面向计算资源和网络资源恶意行为的识别和响应，它从计算机网络或计 算机系统的关键点收集信息并加以分析，从而发现网络或系统中是否有违反安 全策略的行为和被攻击的迹象。从管理层面上讲是为应对恶意攻击而采取法律和 孤立点挖掘技术在异常检测中的应用研究 行政手段提供依据。入侵检测既要检测来自系统外部的入侵行为，同时也监督内 部用户的未授权活动。 而入侵检测系统( i d s ) 是实现入侵检测功能的系统。它在被保护系统的安全 性受到侵害时发出报警并采取适当的行动来阻止入侵行为，从而起到保护系统 安全的作用。i d s 一般包括3 个部分：信息的收集和预处理、入侵分析引擎及 响应和恢复系统。入侵检测首先要进行信息收集。检测成功与否依赖于信息的可 靠性、正确性和实时性。入侵检测利用的数据一般来自以下几个信息源：主机系 统信息、网络信息、其他安全产品产生的审计记录和通知消息等。入侵分析引擎 是i d s 中的核心部分，传统的入侵检测方式为异常检测和误用检测两种。目前的 i d s 系统大多是两者的结合。事件响应和恢复很重要，但往往被忽略。事件响应 的类型分为：主动响应，响应机制会阻断或者干扰入侵过程：被动响应，仅是 汇报情况和记录入侵过程。 1 2 入侵检测的发展历程 1 9 8 0 年，a n d e r s o n 首先提出了入侵检测的概念n 】，他将入侵尝试或威胁定 义为：潜在的、有预谋的、未经授权的访问信息、操作信息，致使系统不可靠或 无法使用的企图。他提出审计追踪可应用于监视入侵威胁。但这一设想的重要性 当时并未被理解，但他的这一份报告被认为是入侵检测的开创性工作。从1 9 8 4 年到1 9 8 6 年，d e n n i n g 和n e u m a n n 研究并发展了一个实时入侵检测系统模型雎1 ， 命名为i d e s ( 入侵检测专家系统) ，它是一种通过使用统计方法发现用户异常操 作行为并且判断检测攻击的基于主机的入侵检测系统，将异常定义为“稀少和不 寻常 ( 指一些统计特征量不在正常范围内) ，他们的这个假设是许多8 0 年代入 侵检测研究和系统原型的基础。1 9 8 7 年，d e n n y i n g 提出关于这个问题的论文被 认为是另一篇入侵检测的开创之作。1 9 8 8 年，m o r r i si n t e r n e t 蠕虫事件导致 了许多i d s 系统的开发研制。1 9 8 8 年，l u n t 等人进一步改进了d e n n y i n g 提出的 入侵检测模型，他提出了与系统平台无关的实时检测方案。1 9 9 0 年，h e b e r l e i n 等人提出基于网络的入侵检测n s m ，n s m 可以通过在局域网上主动地监视网络 信息流量来追踪可疑的行为。1 9 9 1 年，n a d i r 提出了收集和合并处理来自多个主 机的审计信息从而用以检测针对一系列主机的协同攻击。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 建议使用自治代理以便提高i d s 的可伸缩性、可维护性、效率 和容错性呻1 。1 9 9 4 年b i s w a n a t hm u k h e r j e e 等对先前i d s 的研究做了较为完整的 回顾和分析，对各种i d s 的系统原型进行了分析和评述。1 9 9 5 年以后出现了很 多不同的新的i d s 研究方法特别是智能i d s ，包括神经网络、遗传算法、模糊识 别、免疫系统、数据挖掘等。 1 3 入侵检测通用模型 最早的入侵检测模型是由d e n n i n g 给出的 铂，该模型主要根据主机系统审计 记录数据，生成有关系统的若干轮廓，并监测轮廓的变化差异发现系统的入侵行 为，如图1 - 1 所示。 图1 - 1i d e s 入侵检测模型 资料来源：a ni n u u s i o ud e 怔c f i o om o d e # 入侵行为的种类不断增多，涉及的范围不断扩大，而且许多攻击是经过长时 期准备，通过网上协作进行的。面对这种情况，入侵检测系统的不同功能组件之 间、不同i d s 之间共享这类攻击信息是十分重要的为此，c h e n 等提出一种通 用的入侵检测框架模型，简称c i d f 嘲。该模型认为入侵检测系统由事件产生器 ( e e v e n tb o x ) 、事件分析器( a n a l y z e r s b o x e s ) 、响应单元( c o u n t e r m e a s u r e ) 和事件数据库( s t o r a g eb o x e s ) 组成，如图1 - 2 所示。 3 孤立点挖掘技术在异常检测中的应用研究 图1 - 2c i d f 各部件之间的关系 资料来源：t h ec 锄m i n 岫s i 帆d c t 。c t i f 姗c w o r ka r c h i t e c t t l 陀【5 l e b o x e s 的目的是为了向系统的其它部件提供事件信息。一个“事件 可能 是复杂的，也可能是一个具体的底层网络协议。e b o x e s 是一个完整i d s 的传感 组织或者称为传感器( s e n s o r ) ，e - b o x e s 的输入，可以为一个入侵检测系统获得 对安全事件得出结论的信息。 a - b o x e s 分析来自事件发生器的输入数据或信息。多数关于入侵检测系统的 研究集中在如何创建一种新的方法上，分析事件流，抽取相关信息，目前已经研 究有很多不同的方法。 e b o x e s 和a - b o x e s 会产生大量的数据。在需要使用时，系统操作员必须能 够获得这些信息。一个i d s 的d b o x 部件被定义用来存储这些信息，使得在将 来需要时可以获得。很多d 系统被设计来仅仅作为报警使用。尽管这样，目前 可获得的绝大多数商业i d 系统配备有某种形式的响应( c - b o x e s ) 能力，如能够 切断t c p 连接或修改路由过滤列表。这样使得i d s 在发现初始的攻击后能够阻 止进一步的攻击。 c i d f 模型中，研究人员最为关心的通常是事件分析器c a - b o x e s ) 的性能， 它的检测精度直接影响整个入侵检测系统的实用性。本文也是针对事件分析器的 所使用的检测方法进行研究。 4 第一章绪论 1 4 入侵检测技术分类 入侵检测技术传统上分为两大类型：异常入侵检测( a n o 眦1 yd e t e c t i o n ) 和误用入侵检测( m i s u s ed e t e c t i o n ) 。 异常入侵检测系指建立系统的正常模式轮廓，若实时获得的系统或用户的轮 廓值与正常值的差异超出指定的阈值，就进行入侵报警。异常检测的前提是异常 行为包括入侵行为。理想情况下，异常行为集合等同于入侵行为集合，此时，如 果i d s 能够检测所有的异常行为，就表明能够检测所有的入侵行为。误用入侵 检测是指根据已知的攻击特征检测入侵，可以直接检测出入侵行为。误用检测方 法的优点是误报率低，可以发现已知的攻击行为。但是，这种方法检测的效果取 决于检测知识库的完备性。为此，特征库必须及时更新。此外，这种方法很难发 现未知的入侵行为。 由于误用检测方法在技术上比较简单和容易实现，系统的性能比较稳定，所 以在现今商用的入侵检测系统广泛采用这种方法。 采用两种检测技术对攻击进行检测，所得出的结论有非常大的差异。误用检 测技术的核心是维护一个知识库。对于已知的攻击，它可以详细、准确地报告出 攻击类型，但是对未知攻击却效果有限，而且知识库必须不断更新。而异常检测 技术则无法完全准确判别出攻击的类型，但它在理论上可以判别更广泛、甚至新 型的攻击，因此引起了研究人员的广泛关注，也是本文研究的重点所在。 1 4 1误用入侵检测技术 误用入侵检测的前提是，入侵行为能按某种方式进行特征编码。入侵检测的 过程，主要是模式匹配的过程。入侵特征描述了安全事件或其它误用事件的特征、 条件、摔列和关系。特征构造方式有多种，因此误用检测方法也多种多样。下面 列举主要的误用检测方法： ( 1 ) 基于条件概率的误用检测方法 指将入侵方式对应一个事件序列，然后观测事件发生序列，应用贝叶斯定理 进行推理，推测入侵行为。 ( 2 ) 基于状态迁移分析的误用检测方法 状态迁移分析方法以状态图表示攻击特征，不同状态刻画了系统某一时刻的 5 孤立点挖掘技术在异常检测中的应用研究 特征。初始状态对应于入侵开始前的系统状态，危害状态对应于已成功入侵时刻 的系统状态。初始状态与危害状态之间的迁移可能有一个或多个中间状态。攻击 者执行一系列操作，使状态发生迁移，可能使系统从初始状态迁移到危害状态。 因此，通过检查系统的状态就能够发现系统中的入侵行为。采用该方法的i d s 有 s t a t ( s t a t et r a n s i t i o na n a l y s i st e c h n i q u e ) 脚和u s t a t ( s t a t et r a n s i t i o n a n a l y s i st o o lf o ru n i x ) 吲。 ( 3 ) 基于键盘监控的误用检测方法 基于键盘监控的误用检测方法，假设入侵行为对应特定的击键序列模式，然 后监测用户击键模式，并将这一模式与入侵模式匹配发现入侵行为嗍。这种方法 的缺点是，在没有操作系统支持的情况下，缺少捕获用户击键的可靠方法。此外， 也可能存在多种击键方式表示同一种攻击。如果没有击键语义分析，用户提供别 名( 例立h k o r ns h e l l ) 很容易欺骗这种检测技术；而且该方法是无法检测恶意程 序的自动攻击。 ( 4 ) 基于规则的误用检测方法 基于规则的误用检测方法，指将攻击行为或入侵模式表示成一种规则，只要 符合规则就认定它是一种入侵行为。s n o r t 入侵检测系统叫旧就采用了基于规则 的误用检测方法。这种方法的优点是，能够比较准确地检测入侵行为，误报率低； 其缺点是，无法检测未知的入侵行为。 ( 5 ) 基于特征检测得误用检测方法 特征检测对已知的攻击或入侵的方式做出确定性的描述，形成相应的事件模 式。当被审计的事件与已知的入侵事件模式相匹配时，即报警。原理与专家系统 相仿。其检测方法与计算机病毒的检测方式类似。目前基于对数据包特征描述的 模式匹配应用较为广泛。该方法预报检测的准确率较高，但对于无经验知识的入 侵与攻击行为无能为力。 1 4 2异常入侵检测技术 异常检测先定义一组系统“正常 情况的模型，如c p u 利用率、内存利用 率、文件校验和、进程运行情况、网络数据流( 这类数据可以人为定义，也可以 通过观察系统、并用统计的办法得出) ，然后将系统运行时的数值与所定义的“正 常情况比较，得出是否有被攻击的迹象。这种检测方式的核心在于如何定义所 6 第一章绪论 谓的“正常情况。 异常检测技术可以发现未知的入侵行为，因此研究人员对异常检测技术有着 浓厚的兴趣，研究的成果也比较丰富。下面将对异常检测的常用方法进行介绍。 ( 1 ) 基于统计的异常检测技术 统计异常检测方法根据异常检测器观察主体的活动，然后产生刻画这些活动 的行为的轮廓数据库。每个轮廓数据库保存记录主体当前行为，并定时地将当前 的特征数据与轮廓数据库中的数据合并。通过比较当前的轮廓与已建立的轮廓数 据来判断异常行为。一个典型的基于统计异常检测的系统是s r ii n t e r n a t i o n a l 的n i d e s n 3 。统计异常检测方法的有利之处是所应用的技术方法在统计学中得到 很好的研究，可以应用的方法比较成熟，也比较多。 但是基于统计的异常检测有以下的缺点： 1 ) 单纯的统计入侵检测系统容易被入侵者通过长时间的训练，使模型适应 其入侵行为，从而让入侵检测系统把入侵行为误认为是正常行为。这也 是基于统计的异常检测研究正在重点研究的一个难点。 2 ) 难以确定判断异常的阀值，阀值的设置对检测的结果有较大的影响。 ( 2 ) 基于预测模式生成的异常检测 基于预测模式生成( p r e d i c t i v ep a t t e r ng e n e r a t i o n ) 的异常检测方法的 假设条件是事件序列不是随机的而是遵循可辨别的模式。这种检测方法的特点是 考虑了事件的序列及相互联系。t e n g 和c h e n 给出了基于时间的归纳方法t i m ( t h e t i m e b a s e di n d u c t i v em a c h i n e ) n 3 1 ，利用时间规则来识别用户行为正常模式的 特征。通过归纳学习产生这些规则集，并能动态地修改系统中这些规则，使之具 有较高的预测性、准确性和可信度。如果规则大部分时间是正确的，并能够成功 地运用预测所观察到的数据，那么规则就具有高可信度。这种方法的主要优点有： 1 ) 能较好地处理变化多样的用户行为，并具有很强的时序模式。 2 ) 能够集中考察少数几个相关的安全事件，而不是关注可疑的整个登录会 话过程。 3 ) 对于针对检测系统本身的攻击，具有良好的灵敏度。因为根据规则的隐 含语义，在系统学习阶段，能够更容易地辨别出欺骗者训练系统的企图。 该方法的主要弱点是误警率较高。 7 孤立点挖掘技术在异常检测中的应用研究 ( 3 ) 基于神经网络的入侵检测 人工神经网络( a n n ) 自从2 0 世纪5 0 年代r o s e n b l a t t 首次将单层感知器应 用与模式分类学习以来，已经有了4 0 多年的研究历史。人工神经网络中每个神 经元的结构和功能是相对简单和有限的，但正是这些众多结构简单、功能有限的 神经元的“微观活动，构成了复杂的“宏观效应”能完成各种复杂的信息 识别和任务处理。人工神经网络无需预编程，无需制定工作规则，它通过学习自 行领悟事物内在规律。这种自组织、自学习及推理的自适应能力是神经网络相对 于传统a i 的最大优势。如今人工神经网络已经发展出模糊逻辑、概率推理、遗 传算法、混沌系统、支持向量机以及局部学习方法构成新一代智能计算内核 软计算。 目前，神经网络已经广泛的应用于入侵检测的研究n 铂n 町。只要提供系统的审 计记录数据，神经网络就可以通过自身学习从中提取正常的用户或系统活动的特 征模式，而不需要获取描述用户行为特征集以及用户行为特征的统计分布。神经 网络可以利用大量入侵实例对其进行训练建立正常行为的神经网络模型，获得检 测能力，并且这一过程可以是完全抽象的计算，神经网络可以自动掌握调节各个 度量之间的内在关系，使其最大限度地逼近于现实环境下的工作模型或网络攻击 模型，从而对于输入的数据做出正确的判断。 神经网络的缺点在于训练模型的时间很长，对系统资源的占用比较大。在神 经网络的训练过程中可能导致无法收敛、陷入局部最小点和过训练等问题，都是 困扰神经网络在入侵检测中应用的难点。 ( 4 ) 基于数据挖掘的i d s 计算机网络上的大量网络数据包及主机上的大量日志和审计信息，这些记录 数据是海量的，若单独依靠手工的方法来发现记录中的异常现象是非常困难的。 w k l e e 和s s t o l f o 在这方面作了许多工作1 们洲2 7 1 恻1 嘲，他们应用数据挖掘 的方法从海量的数据中提取感兴趣的知识，并用这些知识去检测异常入侵。其研 究的目标是尽可能地减少建立入侵检测系统的个人经验。 同概率统计方法相比，数据挖掘方法具有如下优点：数据挖掘体现了一个完 整的数据分析过程侧。它一般包括数据准备、数据预处理、建立挖掘模型、模型 评估和解释等。另外，它是一个迭代的过程，通过不断地调整参数和方法以得到 8 第一章绪论 较好的模型。基于数据挖掘的异常检测方法，目前已有现成的k d d 算法可以利用。 这种方法的优点是可适应处理大数据量的情况。但是对于实时入侵检测还存在问 题，需要开发出有效的数据挖掘算法和相应的分布式体系。 ( 5 ) 基于人工免疫的入侵检测系统 人工免疫技术首先是由f o r r e s t 等人应用于入侵检测的。免疫系统是生 物体的重要组成部分，它所具有的许多信息处理机制和功能特点，如自我的抗原 识别机制、学习和记忆能力、自适应环境能力以及能与体内其它系统和组织进行 协调共处的特点等。目前，对基于人工免疫系统的入侵检测系统模型的研究，有 两个方向。一是针对主机系统的特权进程的系统调用序列恤】【删，另一个是针对网 络数据包的免疫模型，但是两者建模的方法基本相同。 由于免疫系统具有分布式、多样性、记忆性、可扩充性等特点，可以利用这 些特点建立分布式、高效和自组织的入侵检测模型。其缺点是目前还没有一套完 善的人工免疫的理论体系，也没有有效的抗原识别算法。 1 5 入侵检测发展现状 由于单一检测模式的局限性以及当前入侵行为走向分布式协作式入侵的特 点，越来越多的研究投入到分布式i d s 系统中f 6 习跚。分布式入侵检测基于对不 同的检测环境进行分类并采用不同的检测方法和技术手段的思想，采用多个检 测部件，各检测部件选用不同的检测方法，监控不同的主机和网络部分，协同合 作完成检测任务。这种方法有利于取各种检测方法之长，大幅度地提高检测效率 和准确性。 国外一些研究机构已经对分布式入侵检测进行了有益的研究，并建立了一 些实验性系统。n a d i r 系统使用已有的服务节点在网络上进行分布式审计数据 收集，然后由一个中心专家系统来分析这些数据。n f r 能够抓住网络上最重要 的活动类型，并观察常见的入侵和攻击，是“分布式监测、集中式管理 的典型。 u cd a v i s 大学提出的c i d f 系统主要的研究目标是提供一种能够使各种入侵检 测系统互操作的方法，侧重于系统的各个部件之间的通信，希望能形成一个所有 入侵检测系统都遵循的标准。 国内近两年也建立了一些系统：清华大学信息网络工程研究中心开发的 9 孤立点挖掘技术在异常检测中的应用研究 d i d a p p e r ( d i s t r i b u t e di n t r u s i o nd e t e c t o r w i t ha p p e r c e p t i o n ) ，即具有认知能力的 分布式入侵检测系统，以分析大型t c p i p 网络中的网络行为为设计目标，使用 了m 陷阱、流量标本和神经网络等几种关键技术。中国科学院提出了一个基于 代理( a 鹊n t ) 的分布式入侵检测系统模型【6 5 1 。该模型采取无控制中心的多a g e n t 结构，每个检测部件都是独立的检测单元，模型尽量降低各检测部件间的相关性， 不仅实现了数据收集的分布化，而且将入侵检测和实时响应分布化。 随着网络速度的提高，网络的数据流量越来越大，如果依靠人上分析入侵数 据，不但费时费力，而且不能在最短的时间内对入侵行为做出反应。随着数据挖 掘技术的发展，出现了一些较为成熟的方法，并且已应用到入侵检测中。1 9 9 7 年左右，美国学者就开始着手将数据挖掘方法应用到入侵检测中，目前已取得了 一定的成果。国内也有一些高校，如清华大学、西安电子科技大学和华中科技大 学的学者在关注这个领域的研列1 6 1 1 7 】 目前国内外类似的基于数据挖掘的入侵检测系统有m a d a mi d ，a d a m ， 分布式协同入侵检测系统以及无监督异常检测系统等。 ( 1 ) m a d a mi d ( m i n i n ga u d i td a t af o ra u t o m a t e dm o d e l sf o ri n t r u s i o nd e t e c t i o n ) m a d a mi d 是美国哥伦比亚大学开发的最为有名的基于数据挖掘的入侵检 测项目【2 1 p g l 。它的主要思想包括建立用于关联分析的关联规则，用于序列分析 的频繁片断以及分类器。研究者对于己有的算法，如a p r i o r i 算法和频繁片断算 法等进行了一些改进。他们根据需要把记录中的某些较重要的属性设为数据挖掘 时的轴属性( a x i sa t t r i b u t e s ) ，另一些不太重要的则设为参考属性( r e f e r e n c e a t t r i b u t e s 。例如反映网络连接特征的时间戳、源主机地址、目的主机地址、源端 口、目的端口和服务类型等可设为轴属性，因为它们可以用于定义一条唯一的记 录，而连接时间等则可设为参考属性。通过轴属性的使用可以减少无用规则的产 生量，并且为入侵检测提供了丰富有效的审计数据信息。 m a d a mi d 系统利用基于规则的分类算法r i p p e r 在训练数据集上进行归 纳学习，最终产生描述每个类( 正常类或入侵类) 的模型。r i p p e r 算法产生的规 则简洁明了，并且可以在任何需要的时候山安全专家进行检查和编辑。研究者通 过使用不同的数据源和不同的检测方法，进行了大量实验。这些数据包括来自主 机的系统调用序列数据和来自网络的数据包，主要分为网络层数据和应用层数 1 0 第一章绪论 据。m a d a mi d 是一种典型的误用检测系统，由于误用检测系统的局限性，它 无法检测到新类型的攻击。 ( 2 ) a d a m ( a u d i td a t aa n a l y s i sa n dm i n i n g ) a d a m 是乔治梅森大学设计的异常检测系统嘲，系统可以捕捉到偏离己建 立的系统正常行为模式的行为，因此，可以发现新类型的攻击，但由于可能会把 未知的正常行为标记为异常，因此具有较高的误报率，需要大量的时间区分真正 的入侵数据和被误报的正常数据。a d a m 采用了区分可疑事件为入侵或误报事 件的有效机制，具有两个方面的主要特点：一是使用数据挖掘技术建立正常行为 的模式，并且对于可疑攻击使用了分类器以区分其为误报或真实攻击；第二点是 通过使用具有滑动窗口的递增挖掘算法来发现可疑事件，使其能够在实时状态下 使用。 另外，a d a m 还使用了关联规则和分类算法来挖掘t c p d u m p 审计数据中 所包含的攻击数据。系统首先在正常数据集上挖掘出正常模式，接着通过使用具 有滑动窗口的在线算法找出剩余数据中的频繁模式，把它们与己生成的正常模式 库进行比较，丢弃掉那些被认为是正常的数据。a d a m 对最后剩余的数据采用 了分类器以区分其为己知攻击形式、未知攻击形式或者是正常数据。a d a m 从 一定程度上解决了传统异常检测系统误报率较高的问题。 ( 3 ) 基于数据挖掘的分布式协同入侵检测系统 为了提高对用户异常行为的识别能力和对未知模式攻击的检测能力，华中科 技大学的刘科等人提出了一种基于数据挖掘的分布式协同入侵检测系统框架，即 在协同入侵检测中采用了基于数据挖掘的入侵检测技术，并与常规入侵检测系统 相结合圈。其结构包括数据采集器、常规入侵检测器、常规入侵规则库、常规 安全事件库、协同安全事件库、协同入侵检测器、协同入侵规则库和基于数据挖 掘的规则生成器等部分。通过将基于专家知识库的误用检测技术和协同入侵检测 技术相结合，该系统具有一定的常规入侵检测和协同入侵检测能力。使用基于数 据挖掘的关联规则算法使系统可以自适应地生成一些具有一定支持度和可信度 的协同入侵规则，从而具备一定检测未知模式协同入侵的能力。 ( 4 ) 无监督异常检测系统 前面提到的系统一般都需要在大量的已标记为正常或异常的训练数据集上 孤立点挖掘技术在异常检测中的应用研究 进行训练，在实际应用中通常没有已标记好的数据可供使用，因为原始的网络数 据或系统调用数据都是没有标记的，所以这些标记需要以手工的方式进行，因此 会耗费大量的人力物力。而无监督异常检测方法就没有这些限制，由于它们不需 要使用任何已标记好类别的数据，大大降低了训练数据集的生成要求，成为了近 来研究的热点。无监督异常检测方法通常假设数据集包含了大量的正常数据和相 对少量的异常数据，并且异常数据与正常数据间存在着本质的不同洲。 文献 2 4 1 中提出了一种基于聚类的入侵检测系统，它可以自动检测新的或其 他未知的攻击形式。在这个系统中，不需要在训练阶段提供手上或其他方式得到 的标记数据，并且能够检测多种不同类型的攻击，同时保持较低的误报率。此方 法中用于建立模型的训练数据集必须正确且充分地代表了整个网络或主机环境 的数据分布情况。如果这个前提不满足的话，系统中使用的判断入侵方法就会变 得不适用。 ( 5 ) 其它系统 w i s d o m 是最早的基于数据挖掘的入侵检测系统，它可以从系统审计数据中 挖掘出代表正常行为的关联规则。t e n g 等人采用了类似的方法自动学习代表正 常用户行为的频繁片断规n t l 3 】。m u k k a n m a l a 等人通过使用数据挖掘技术以减 少在入侵检测中需要维护和分析的审计数据量，l a i n 等人也采用了类似的审计数 据缩减技术瞄】。另外还有大量研究致力于在系统调用序列中建立模型，采用的 方法包括神经网络、隐藏m a r k o v 模型以及固定和变化长度模式等，w a r c n d e r 和 d e b a r 等人的研究都是这些研究工作的代表阑 1 6 入侵检测存在的问题 目前入侵检测技术还是面临着许多问题，主要反映在以下几个方面： ( 1 ) 误报率、漏报率高，执行效率低，系统响应能力有限 ( 2 ) 没有通用的构造方法，自我更新能力不强，规则集维护困难，系统缺乏 灵活性 ( 3 ) 自身结构上存在安全隐患，鲁棒性和容错性不强 ( 4 ) 缺乏好的测试手段 ( 5 ) 对入侵的理解能力有限 1 2 第一章绪论 针对目前网络环境复杂多变，用户及系统产生的审计数据量巨大的现状，人 们急需一种更加系统化、自动化的方法来构造入侵检测模型，它帮助系统实时监 测网络攻击，扩展了系统的安全管理能力，提高了信息安全基础结构的完整性。 随着各种软件的层出不穷，新的漏洞不断被发现，黑客入侵的技术日益提高，入 侵检测系统需要完成的任务变得越来越艰巨，人工智能技术为入侵检测系统提供 了新的方法和思路，它和入侵检测系统紧密结合必将极大的提高现有入侵检测系 统的性能，同时促进更多人工智能算法的提出和应用于入侵检测这个新的领域。 1 7 本文研究内容和主要创新点 我们所研究的内容主要集中在基于无监督的异常检测技术的研究上。本文首 先研究了入侵检测系统的一些理论，对入侵检测的定义、分类、模型等进行了综 述，并分析了各种入侵检测分类的优缺点；结合当前一些基于数据挖掘的入侵检 测的研究成果，分析了基于有监督的数据挖掘方法在入侵检测中存在的问题，指 出了无监督入侵检测研究的意义；基于孤立点和入侵行为存在的相似性，提出了 基于孤立点挖掘的异常检测技术，从理论分析了该方案的可行性，最后我们设计 了两种孤立点挖掘的异常检测实现技术，通过实验验证了基于孤立点挖掘的异常 检测技术性能。本文的主要创新点如下： ( 1 ) 根据对入侵事件的特征分析，将孤立点挖掘技术引入到异常检测领域，提 出了一种全新的基于孤立点挖掘的无监督异常检测技术； ( 2 ) 针对h i l o u t 算法所存在的不足进行改进，提出一种基于索引树的孤立点 挖掘算法t r e e o u t 。该算法避开了原先复杂的h i l b e r t 编号的生成，通过 r - r e g i o n 和索引树来估算数据的权值上下界，大大减少了数据点间的距 离计算。 ( 3 ) 提出了一种基于b i r c h 的孤立点挖掘b i r c h o u t 算法。算法利用c f - t r e e 结构快速查找每个数据的近似的最近邻居集，来估算权值，有效克服了在 孤立点挖掘中精确计算权值存在的复杂度高的问题。 1 3 孤立点挖掘技术在异常检测中的应用研究 1 8 本文结构安排 本论文的内容安排如下： 第一章 第二章 第三章 第四章 第五章 简要说明了所做工作的目的、范围；入侵检测及无监督入侵检 测的国内外进展情况；本文工作的切入点、研究方法、取得的 成果等。 主要介绍了数据挖掘技术在入侵检测中的常见的应用方法，然 后介绍了孤立点挖掘的基本方法，分析了孤立点挖掘方法在异 常检测中的可行性。 主要介绍作者所做的工作，包括两种孤立点挖掘算法以及它们 在异常检测中的应用；分析了现有算法的缺点，提出了基于索 引树和基于b i r c h 的孤立点挖掘算法，然后分别用它们在 k d d c u p 9 9 数据集上做了实验。 描述了系统及实验，我们设计了一个插件式结构的系统，可以 非常方便地加入新算法或更新现有算法，同时也允许用户自己 定义流程；接着我们在实验室内部截获了部分网络流量数据， 使用该系统进行了异常检测实验。 本文工作的总结和展望 1 4 第二章基于数据挖掘的入侵检测技术 第二章基于数据挖掘的入侵检测技术 本章首先介绍了基于数据挖掘的入侵检测技术思想，阐述了具有代表性的实 现方案，分析了当前基于数据挖掘的异常检测技术所存在的问题，探讨了将孤立 点挖掘技术引入到异常检测领域中的可行性。 2 1 数据挖掘技术概述 数据挖掘是从海量数据中提取隐含的、以前不知道的、有潜在作用的信息， 应用一系列技术从大型数据库或数据仓库中提取人们感兴趣的信息和知识，这些 知识或信息是隐含的，事先未知而潜在有用的，提取的知识表示为概念、规则、 规律、模式等形式。也可以说，数据挖掘是一类深层次的数据分析，它利用统 计与可视化技术以易于理解的形式发现并表现信息嘲。 图2 l 数据挖掘受多学科的影响 资料来源：数据挖掘概念与技术) 嗍 数据挖掘是一个交叉学科领域，受多个学科影响( 见图2 1 ) ，包括数据库系 统、统计学、机器学习、可视化和信息科学。数据挖掘的方法从功能上主要有4 类方法，如图2 2 所示：基于关联的分析、基于序列的分析、分类分析和聚类分