（计算机应用技术专业论文）fp树算法的研究以及在入侵检测中的应用.pdf

江苏大学硕士研究生毕业论文 摘要 关联规则是数据挖掘的一个重要研究方向，旨在挖掘项集之间的内在联系。 f p 树算法是关联规则的一种基于深度的典型算法，具有良好的性能和可扩展性。 f p 树通过自顶向下构造频繁树和自底向上挖掘频繁项集，只需扫描事务数据库 两次便可以有效的挖掘出频繁项集，因而比基于宽度的a p r i o r i 算法快一个数量 级。但是，f p 树采用递归的方法，同一条路径需要多次遍历，这成为制约f p 树 算法效率的瓶颈。改进后的算法采用空间换时间的方法在每个节点上添加一个标 记位来标识该节点是否被遍历，首先通过遍历f p 树找到所有叶子节点，然后从 头表找出树中的叶子节点，从叶子节点开始回溯树中的路径，将同一条路径存储 在一个线性链表中，从而减少同一条路径的遍历次数。实验显示：改进后的算法 对于稀疏事务数据和稠密事务数据都能有效的提高挖掘效率，虽然增加了标记位 的空间消耗，但是同时减少了条件f p 树的生成，因而空间性能也有所提高。 入侵检测是数据挖掘的一个重要应用方向，而挖掘算法效率的提高则是其中 的一个研究热点。本文分析了当前入侵检测的研究进展，采用j p c a p 开源库设计 了入侵检测的数据采集模块。将改进后的f p 算法应用于入侵检测中的关联规则 挖掘中，采用主轴因子和参考因子有效地过滤频繁项集来获得规则集，通过模式 比较来获得入侵行为。采用林肯实验室的1 9 9 8 年的网络实时数据进行实验，将 改进后的f p 树算法应用到关联规则的模式库挖掘中，采用不同的支持度来挖掘 训练数据集和测试数据集。实验结果显示，对于入侵数据，改进后的f p 树算法 比原f p 树算法挖掘效率更高。检测结果显示，改进后的算法具有良好的检测率 和较低的误检率。 关键词：f p 树，入侵检测，数据挖掘，关联规则 江苏大学硕士研究生毕业论文 a b s t r a c t a s s o c i a t i o nm l ei s 锄i m p o n a n tr e s e a r c hd i r e c t i o no fd a t am i i l i n 2 i t sp m 口o s ei st o f i n do u tm ei n h e r tl i i l l 【so ft h ei t 锄s e t s f pt t e ei sa 帅i c a id 印t h b a s e da l 擘r o r i t 量l i i l o f 舔s o c i a t i o nm l e ，w h i c hh 觞9 0 0 dp e r f 0 肌觚c e 锄ds c a l a b i l i t y b yc o n s t m c t i n gt l l e f e q u e n t 仃f b mm et o pt ot l l eb o t t o ma n dm i m n gt h e 向e q u e n ti t 锄s e t s 丘d mt l l e b o t t o mt om et o p ，f pt r e ec a nm i n em e 仔e q u e mi t e ms e t sw i t h i n2t i m 鹪s c a n n i i l go f t h ed a t a b a s e ，s oi ti sl0t i m e sq u i c k e rt h a i lm ew i d e - b a s e da p 订o r ia l g o r i m m h o w e v 吼 d u et ot h er e c u r s i v em e t h o d ，t h es 锄ep a m m a yb e 廿a v e l e df o rs e v e r a lt i m e s ，w h i c h b e c o m e st h em a i nf a c t o rt h a ta a 、e c t st h ee 衔c i e n c yo ft h ea 1 9 0 r i t h m b yu s i n gt h e m 锄o r yt or e d u c em et i m e ，t h ei m p r o v e da l g o r i t a d d sam a r kt oe v e r yi l o d eo ft h e t r e et od 锄o n s t r a t ew h e t h e rt h en o d ei sv i s i t e d a tf i r s tt 1 1 ea l g o r i t l l r i l 位e l st h e w h o l et r e et op r e ta ut h el e a fs e t s ，a i l dt h e n 行o mt h eh e a dt a b l eo ft h et r e et o6 n do u t t h el e a fs e t si nt h et r e ea n ds t o r et h ew h o l ep a mh d mt h el e a ft ot h er o o ti nal i n l ( 1 i s t t h ee x p e r i e n c es h o w st h a t ：t h ei m p r o v e da l 擘r o r i t l u i lh a sam u c hb e t t e re 伍c i e n c yn o t o n l yf o rt l es p a f s ed a t a b 嬲eb u ta l s of o rt h ed c f l s ed a t a b a s e a 1 t h o u 曲a d d i n gt 1 1 em a r k m a vc a u s es o m es p a c e ，t h ei m p r o v e da l p r o m mh l d u c e st h ec o n d i t i o nf pt r e ：ea n dh a s ab e t t e rp e 舶n n a n c ei ns p a c et h a nf pt r e e i n t r u s i o n d e t e c t i o ni sa ni m p o r t a n ta p p l i c a t i o n 笛p e c to fd a t am i n i n g ，w h i l e i m p r 0 v i n gt h em i n i n ga 1 9 0 r i t h i ne 伍c i e n c yi sah o tr e s e a r c h t h i sp a p e ra j l a l y s i s e st h e r e s e a r c hp r o g r e s so ft h ei n t n j s i o nd e t e c t i o n ，a n du s 骼j p c a po p s o u i c et od e s i 印t h e d a t ac o l l c c t i o nm o d u l e b yu s i n gt h ei m p r 0 v e da l g o r i t h mt og e tt h ef b q u e n ti t 锄s e t s ， t l l i sp a p e ru s e st h es p i n d l ef a c t o ra i l dr e f e r c = 1 1 c ef a c t o rt of i l t e rm l e s ，锄dc o m p a r e st l l e p a t t e mt og e tt h ei n t r u s i o nb e h a v i o r t h el9 9 8l i n c o l nl a b sr e a lt i m en 舐v o r kd a t a s e t sa n dt i l ei m p r o v e da 1 盛o r i t l l la r eu s e di nt h ee x p e r i e n c e ，d i 仃打锄ts u p p o n sa r e u s e di nt h et r a i n i n gd a t a 锄dt e s td a t a t h er e s u l ts h o w st h a tt h ei m p r o v e da l 星r o r i t t l i i l h a sa 埘【u c hm o r ee 伍c i e n c yt h a nt h ef pt r e ef o rt h ei n t r u s i o nd a t aa i l da l s oh a sa 星r o o d d e t e c t i o nr a t ea n dl o wm i s d c t e c t i o nr a t e 1 ( e yw o r d s ：f pt r e e ，i n t m s i o nd e t e c t i o n ，d a t am i l l i n 私s o c i a t i o n1 1 l l e 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权江苏大学可以将本学位论文的全部内容或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口， 在 年解密后适用本授权书。 不保密团 学位论文作者签名：董哮乎 舻年月l 日 指导教师签名： 移年参月 7 日 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容以 外，本论文不包含任何其他个人或集体己经发表或撰写过的作品 成果。对本文的研究做出重要贡献的个人和集体，均已在文中以 明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：覆豸尹 日期：j ，j 呸年 易月1 1 日 日期：j ，j 哂年 勿月 1 1 日 江苏大学硕士研究生毕业论文 第一章绪论 1 1 课题的研究背景及意义 计算机科学技术的迅猛发展对人类社会产生巨大的影响，一场信息革命正在 酝酿。人们认知自然、改造自然的方式也随之发生变化，在众多领域，计算机正 逐渐代替人类完成一些极具挑战性的任务，2 4 年，美国“勇气”号宇宙飞船 成功踏上火星，不仅鼓舞人类探索自然的勇气，同时还说明计算机在人类生活中 已开始扮演着越来越重要的角色。 数据库中的知识发现n 1 ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 予1 9 8 9 年在第一界k d d 会议上提出，它强调的是通过数据驱动发现方法，获得“知识”。 k d d 是指从数据库中抽取出其中隐含的、新颖的、有用的信息的非平凡过程，即 从大型数据库的数据中提取入们感兴趣的知识。这些知识是隐含的、事先来知的、 潜在的、有用的信息，提取的知识表示为概念( c o n e e p t s ) 、规则( r u l e s ) 、规 律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式。数据挖掘技术n 3 ( 洲，d a t am i n i n g ) 就是从大量的数据中提取或“挖掘知识”，也就是从大量不安全的、有噪声的、 模糊的或者随机的数据中提取人们事先不知道的但又是有用的信息和知识。关联 规则挖掘1 ( a s s o e i a t i o nr u l em i n i n g ) 是数据挖掘研究的一个重要分支，是 数据挖掘的众多知识类型中最为典型的一种。关联规则挖掘可以发现存在于数据 库中的项目( i t e m s ) 或属性( a t t r i b u t e s ) 间的有趣关系，这些关系是预先未 知的和被隐藏的，也就是说不能通过数据库的逻辑操作或统计的方法得出。随着 科学技术的发展，我们获取各种数据的能力提离得很快，需要挖掘的数据痒通常 极为庞大，如果采用一些基本算法，运算复杂度会很高，需要占用大量时间和空 间，这些将导致用户满意度下降，从而限制数据挖掘的应用和发展。所以，数据 挖掘的核心步骤是算法的设计阶段，算法是影响数据挖掘效率的最重要的因素。 因此，研究设计出快速高效的挖掘算法熊有效提高数据挖掘的效率，扩展数据挖 掘的应用范围，对数据挖掘具有十分重要的意义。 计算机信息躁终已经成为一个国家最为关键的政治、经济和军事资源，也成 为国家实力的象征。网络改变了人们的生活、工作方式，使信息的获取、传递、 处理和利用更加高效、迅捷；但是网络也使“黑客 侵犯和操作一些重要的信息 t 江苏大学硕士研究生毕业论文 和数据成为可能，因而引发了网络信息安全与对抗问题。国内由于以前计算机和 互联网的普及较低，并且黑客的攻击技术较为落后，因此，前几年因为计算机和 网络安全造成的问题暴露得不是太明显。但是随着近年计算机和互联网的飞速发 展、普及，黑客攻击技术的不断提高，我们本就十分脆弱的系统面临着越来越严 重的威胁。据调查，国内考虑并实施完整安全措施的机构寥寥无几，很多机构仅 仅用了一些安全策略或根本无任何安全防范。近年来发生的中美、中日黑客大战 就充分说明了国内很多机构安全的脆弱性。因此加强网络的安全性已经成为人们 必须面对的问题。 入侵检测技术口1 是一种积极主动的安全防护技术，成为了目前网络上广泛应 用的技术和管理手段。但是当前大多数的入侵检测系统1 是通过手工定制的方法 建立起来的，例如在误用检测系统中，一些入侵模式需要用特定的模式语言进行 手工编写在异常监测系统中，需要根据系统设计者的经验并利用审计数据的特征 和度量加以描述入侵模式。这使得入侵检测的效率以及对付攻击行为的能力受到 了一定的限制。因此，迫切需要有效的工具帮助人们及时、准确地从海量的数据 中发现数据之间存在的关系或模式、找出有用的信息以便做出正确的决策。数据 挖掘正是这样一种工具和技术。它的优势是可从大量的网络数据以及主机的r 志 数据中挖掘出j 下常的或入侵性的行为模式。 把数据挖掘的算法融入到入侵检测技术进行研究具有理论意义和实际应用 价值，因此本文的意义主要体现在以下三方面： ( 1 ) 关联规则的典型算法f p 树算法对于稠密事务数据和稀疏事务数据都具 有良好的性能，但是要产生大量的条件频繁树。提高f p 树算法的效率对于关联 规则算法的研究以及相关的应用具有重要的意义。 ( 2 ) 入侵检测是网络信息系统的一种重要的动态防护手段，基于数据挖掘 的入侵检测系统同益成为一个研究热点。如何提高入侵检测的效率和提高入侵检 测的精度则是一个重要的研究方向。挖掘引擎的核心算法的研究对于提高网络安 全有着重要的意义。 ( 3 ) 数据挖掘和入侵检测两种技术的有效结合，为数据挖掘提供宽广应用前 景的同时，也将极大地推动数据挖掘和入侵检测技术本身的研究与发展。 1 2 国内外的研究现状 数据挖掘技术的迅速发展使得它在入侵检测领域中得到广泛的应用。当前， 2 江苏大学硕士研究生毕业论文 国内外已有很多研究机构及大学教研室从事基于数据挖掘的入侵检测方面的研 究工作。 最早将关联规则引入入侵检测中进行研究的是美国c 0 1 u m b i a 大学w e e k e l e e $ 8 1 所在的课题组。w e e k el e e 提出了一个构造入侵检测模型的数据挖掘框架 m a d a m i 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 ) 。 w e e k el e e 对通用的关联分析算法进行了改进，在基于统计学度量的支持度和可 信度的基础上，提出了与领域知识密切相关的兴趣度量度，用以指导关联挖掘过 程。通过引入主轴属性和参考属性的概念剪除了无关模式，引入逐层近似挖掘概 念解决重要的低频模式挖掘问题，用相对支持度解决属性值分布不均匀的问题， 这些研究成果使得检测模型获得了较好的检测率。 其它有代表性的成果还包括g e o r g em a s o n 大学d a n i e lb a r b a r a 等人研究的面 向入侵检测的数据挖掘a d a m 阳1 ( a u d i td a t aa n a 】y s i sa n dm i n i n g ) 。a d a m 从 t c p d u m p 审计轨迹中挖掘频繁模式，并以此发现入侵。a d a m 首先将t c p i p 流量数 据进行预处理，从每个数据包中抽取其头部信息，为每个连接建立一个连接记录， 挖掘过程在连接记录数据集上进行。a d a m 的挖掘引擎是由一组关联规则挖掘算法 所组成的，用以实现训练和检测任务，挖掘引擎的输出是一组可疑的关联规则， 然后由分类引擎进行进一步处理。它是一个实时的异常入侵检测系统，其主要缺 点是对纯净数据的依赖较多，虽然具有一定的检测未知入侵类型的能力，但误报 率较耐1 0 】。 u n i v e r s i t yo fn 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 叫2 研究组进行的是 针对主机系统调用的审计数据分析处理，最初的思想是基于生物免疫系统的概 念，无论是针对生物机体还是针对计算机系统，免疫系统的关键问题在于：使用 一组稳定的、并且在不同个体之间存在足够差异的特征( f e a t u r e s ) 来描述自我， 从而使系统具备识别“自我非自我”的能力。然而，对于计算机系统来说，要 解决这个问题相当困难。由于恶意代码隐藏在正常代码之中难以区分且系统的可 能状态几乎是无限的，要寻找一组稳定的特征来定义“自我并不容易。s t e p h a n i e f o r r e s t 使用短序列匹配算法对特定的特权程序所产生的系统调用序列进行了细 致的分析，并在这一领域做出了大量开创性工作。 在基于数据挖掘的入侵检测研究方面，有代表性的国内学者的研究成果包括 中国科学院研究生院选择了层次化协作模型n 3 1 作为研究基础，在模型中采用数据 3 江苏大学硕士研究生毕业论文 挖掘算法对安全审计数据进行分析处理，以便帮助系统自动生成入侵检测规则， 从而建立异常检测模型；清华大学提出了一种基于数据挖掘方法的协同入侵检测 系统框架1 ，并采用a g e n t m a n a g e r u i 三层实体结构，使用多种数据挖掘方法 建立检测模型；华中科技大学的王卉n 础将最大频繁项目集挖掘算法用于入侵检 测；武汉大学电子信息学院的凌军n 刚等人提出并实现了一个基于规则的、层次化 的智能入侵检测原型系统。 孙志强阻力为了解决入侵检测在不降低精度的同时提高检测速度的问题，提高 算法的效率，将f p g r o w t h 算法应用于入侵检测系统中，提出对f p g r o w t h 算法改进 f p t r e e 的头表结构并引入关键属性来挖掘原始审计数据中的频繁模式，实验结 果表明改进后的算法比传统的关联算法在入侵检测中的应用效果更好。 张帆n 踟等在分析几种现有关联规则算法的基础上，针对网络数据的具体情况， 引入关键属性、参考属性以及属性相对支持度的约束，对关联规则挖掘算法 f p g r o w t h 进行了扩展，解决了基本关联规则挖掘算法中产生大量无用模式的问 题，从而帮助系统发掘出更有意义的模式，提高了系统挖掘的执行效率和规则库的 准确度。 黄雯霆n 钔等在分析了传统关联规则算法缺点的基础上，对关联规则挖掘算法 的优化策略和时态因素的分类处理重点进行了讨论。即在利用主属性约束最后规 则的同时，提出了高频属性直接入选的策略。以更快地获取有效的入侵检测规则 实验测试结果表明，优化后的算法在挖掘速度和规则的检出率等性能上有较大提 高，找到了一些原来被忽略的规则并剔除了一些不重要的规则，证明此优化算法 是切实有效的。 邓菲楠啪1 等针对入侵检测系统中由于模式库更新不及时造成的高误报率和 漏报率，提出了协同数据挖掘的入侵检测模型。该技术依据关联规则，自动发现事 物问联系的特性，利用关联规则自动生成模式库，并针对传统a p r i o r i 算法的缺陷 引入加权关联规则。实验结果表明，该模型对已有的典型攻击检测率为9 0 以上。 于枫乜门等提出了一种基于事件序列的频繁情节挖掘算法，并将该算法用于基 于网络的入侵检测中。实验结果证明，与关联规则挖掘算法相比较，频繁情节挖掘 算法可以有效地提高入侵检测系统的准确性，降低误报率。 总之，国内外对于数据挖掘在入侵检测系统中的应用主要集中在如何提高入 侵检测的挖掘效率和提高入侵检测的检测率两个方面。其中，数据挖掘算法效率 4 江苏大学硕士研究生毕业论文 的提高以及如何将挖掘算法应用到入侵检测中是一个热门的研究方向。 1 3 研究的主要内容 基于数据挖掘的入侵检测系统的核心是挖掘算法的效率的提高以及如何提 高检测精度，因此本文研究的内容主要包括： ( 1 ) 研究关联规则中的f p 树算法的优缺点以及f p 树的相关性质，针对f p 树算法多次遍历同一条路径所产生的缺点，提出一种采用增加节点标记位的方法 从叶子节点开始回溯减少同一条路径的遍历次数的f p c 算法，并使用稠密事务数 据库和稀疏事务数据库进行测试，分析了改进后的算法的时间效率和空间效率。 ( 2 ) 入侵检测的相关知识以及基于关联规则的异常检测系统的研究。针对 入侵检测的数据特点，采用改进的f p 树挖掘规则集，并用主轴因子和参考因子 来过滤规则库得到有效的规则集。 ( 3 ) 设计了基于关联规则的异常检测系统，采用j a v a 开源包j p c a p 实现网 络数据的监听，并将改进的f p 算法应用到该系统中，采用林肯实验室1 9 9 8 年的 数据进行模拟实验，将改进后的算法与原来的f p 算法的挖掘进行了比较，对于 训练数据集和测试数据集采用不同的支持度进行挖掘，并进行模式比较，得出规 则集与入侵行为，并分析了相关的检测结果。 1 4 论文的组织结构 第一章绪论，阐述了网络安全的现状以及国内外对基于数据挖掘的入侵检 测的研究现状，提出了本文的研究意义并概述了本文的研究内容。 第二章入侵检测的基本理论，介绍了入侵检测以及入侵检测系统的概念与 功能、入侵检测的分类以及它们的区别。阐述了数据挖掘应用到入侵检测中的优 势，介绍了国内外基于数据挖掘的入侵检测方法的研究，并重点介绍了关联规则 的相关概念，为后文介绍关联规则算法以及关联规则算法在入侵检测中的应用做 了铺垫。 第三章f p 树算法的相关知识，介绍了f p 算法的构造过程以及f p 树的完备 性和紧密性。分析了f p 树算法的优缺点以及国内外学者对f p 树算法的改进。针 对f p 树算法需要多次重复遍历同一条路径的缺点，提出了基于标记的改进方法， 并采用稠密数据库和稀疏数据库进行测试，对改进后的算法进行时间和空间两方 面的分析。 5 汪苏太学硕士研究生毕业论文 第四章基于改进的f p 树算法的入侵检测系统的研究，介绍了入侵检测系统 的技术指标，改进了入侵检测系统的模式，采焉j p c 印包设计了数据采集模块， 采用改进后的f p 树算法设计了关联规则挖掘模块，采用林肯实验室1 9 9 8 年的数 据作为阏络实时数据，设计了数据预处理模块，规剿过滤模块，检测模块。 第血章对全文的工作做了总结，并提出了进一步的工作。 6 江苏大学硕士研究生毕业论文 第二章入侵检测与数据挖掘技术 作为一种新型的、积极主动的安全防护体系的入侵检测是新一代的网络安全 技术，它在众多研究人员的参与下快速的发展着，本文的研究离不开对入侵检测 的相关内容进行深入的认识与理解，因此对入侵检测进行概述性的分析与研究是 非常必要的。 2 1入侵检测的定义和功能 1 9 8 0 年，a n d e r s o n 船2 。2 盯首次提出了入侵检测的概念。他将入侵定义为未经授 权蓄意尝试访问信息、篡改信息、使系统不可靠或不可用。他将入侵行为划分为 外部闯入、内部授权、用户的越权使用和滥用等三种类型，并提出用审计追踪监 视入侵威胁。 美国国际计算机安全协会对入侵检测的定义是入侵检测是通过从计算机网 络或计算机系统中的若干关键点收集信息并对其进行分析，从中发现网络或系统 中是否有违反安全策略的行为和遭到袭击迹象的一种安全技术。 1 9 8 6 年，美国斯坦福国际研究所首次提出了一种抽象入侵检测模型。此模 型独立于任何特殊的系统、应用环境、系统脆弱性或入侵种类。随后，在此基础 上，经过二十年的发展，大量的入侵检测系统己经被研制出来，并得到了一定范 围的应用。 入侵检测系统( i d si n t r u s i o nd e t e c t i o ns y s t e m ) 可以使管理员能够及时的 处理入侵警报，尽可能地减少入侵对系统造成的损害。由于入侵事件的实际危害 越来越大，对入侵检测系统的关注也越来越多，入侵检测系统也就成为网络安全 体系结构中的一个重要环节。 一个入侵检测系统应能够具有以下功能： ( 1 ) 监视分析用户和系统的行为； ( 2 ) 审计系统的配置和漏洞； ( 3 ) 评估敏感数据和系统的完整性； ( 4 ) 识别攻击行为； ( 5 ) 对异常行为进行统计； ( 6 ) 进行审计跟踪，识别违反安全规则的行为； 这些特点结合起来，就可使系统管理员轻松的监视、审计、评估网络系统的 7 江苏大学硕士研究生毕业论文 安全性。 2 2 入侵检测的分类 入侵检测技术的出发点是，认为用户或者程序在计算机上的任何操作( 包括 合法和非法操作) 都是可以被监测的，并认为合法和非法操作对系统造成的结果 是截然不同的。入侵检测从原理上可分为两种检测模型心钔：误用检测模型( m i s u s e d e t e c t i o nm o d e l ) 和异常检测模型( a n o 唿1 yd e t e c t i o nm o d e l ) ，均可用于实时 检测和事后检测，对应的检测方法是误用入侵检测和异常入侵检测。 2 2 1 误用检测 误用检测方法是利用已知的系统缺陷和己知的入侵模式来进行入侵活动的 检测，和病毒检测的方法类似，因此又称特征检测1 ( s i g n a t u r ed e t e c t i o n ) 。 执行误用检测，需要具备以下几个条件： ( 1 ) 完备的规则模式库： ( 2 ) 可信的用户行为记录： ( 3 ) 可靠的记录分析技术： 误用检测依赖于模式库，其关键是如何表达入侵的模式，以j 下确区分真f 的 入侵与j 下常行为。与异常检测相反，误用检测能直接检测不利的或违法的行为， 而异常检测足发现同正常行为相违背的行为。它的优点是能有针对性地建立高效 的i d s ，检测精度高，误报率低。主要缺点是只能检测到大部分或所有己知的攻 击和入侵模式，不能检测到未知的入侵和已知入侵的变种，因此可能发生漏报。 同时，对具体系统的依赖性太强，移植性较差。 2 2 2 异常检测 异常检测( a n o m a l yd e t e c t i o n ) 是利用正常用户和系统的行为特征来检测当 前行为的背离度，以确定当前行为是否为入侵行为。异常检测技术假定所有入侵 行为都是与正常行为不同的，即假设入侵活动是异常活动的子集，利用系统或用 户的正常行为模式检测入侵。 异常入侵检测的主要工作分为两个阶段：学习阶段和检测阶段。 ( 1 ) 学习阶段：系统首先对提供的数据( 训练数据) 进行学习、分析，从中归 纳、总结出训练数据中存在的规律，为系统建立安全模型。这是一种有指导的学 习，提供学习的训练数据可以是安全状态下的数据，也可以是入侵发生时的数据， 但都必需由安全人员指定数据所属的类别( 是正常数据还是入侵数据) 。 8 江苏大学硕士研究生毕业论文 ( 2 ) 检测阶段：系统以学习阶段建立的安全模型为标准，对实际检测的数据 进行分析，并对不符合安全模型标准的数据进行记录并报警。 理想状况下的异常活动集与入侵性活动集等同，若能检测所有的异常活动， 才可检测所有入侵性活动。而实际上入侵性活动并不等同异常活动，这里存在4 种可能情况：( 1 ) 入侵但非异常；( 2 ) 非入侵且非异常；( 3 ) 非入侵但异常；( 4 ) 入 侵且异常。因此，异常入侵要解决的问题就是构造异常活动集并从中发现入侵性 活动子集。 2 2 3 两种检测技术的比较 ( 1 ) 检测结果 误用检测检测率相对较高，因为检测的匹配条件描述清楚，所以可以明确指 示出当前发生攻击的类型，但是只能检测到已知的攻击模式，而异常检测检测率 相对较低，尽管无法明确指示攻击为何种类型，但是可以检测到未知的入侵行为。 ( 2 ) 误报警率 误用检测相对较低，而异常检测相对较高，因为系统的正常活动是不断变化 的，需要不断的学习，所以在学习阶段，异常模式在正常工作可能会生成额外的 虚假报警信号，或者在此阶段，信息系统遭受非法的入侵攻击后，学习结果中可 能包含了相关的入侵行为的信息，使得今后系统无法检测到此种入侵行为。 ( 3 ) 可移植性 误用检测的可移植性较差，需要在某个特定的环境下生效，而异常检测较少 依赖特定的操作系统环境。 ( 4 ) 内部用户 误用检测对于检测内部用户的误用权限活动很困难，而异常检测对内部用户 超越权限的违法行为检测能力相对较强。 ( 5 ) 报告的数据 误用检测报告的数据是一条指示特定攻击行为发生的警告信号，其中还包含 相关的提示数据，而异常检测生成的数据量多，这些数据量都是超出期望行为范 围的事件。 ( 6 ) 系统配置工作量 误用检测系统配置工作量较少，并且相对容易，而异常检测比较难配置，需 要对系统的已知和期望的行为模式做全面综合的定义，因此也就需要更多的数据 9 江苏火学硕士研究生毕业论定 收集、分析和更新工作。 2 。3数据挖掘用于入侵检测中的优势 数据挖掘通常应用于市场行销、金融投资、生产制造等领域，但在入侵检测 设计领域中运用数据挖掘技术对网络业务进行分析也具有嚼显优势，主要体现在 以下几方面： ( 1 ) 霹络中监测到的数据量大且种类繁多，并具有稳定的数据来源，适合 进行数据挖掘； ( 2 ) 鼹络中监听到的数据按其所具有的不同属性可以进行分类，同时，不 同的数据之间的确存在有某种相关性，如一个连接往往伴随另一种连接发生。因 此，运用数据挖掘技术对审计数据进行挖掘能够得到有价值的信息； ( 3 ) 从各种渠道所获得的审计数据，经过加工处理之后适合运用数据挖掘 中的联系分析方法。 2 。4 入侵检测中的数据挖掘方法 数据挖掘在入侵检测中的应用一般包括数据源的选择、数据预处理和挖掘算 法选择几个主要阀题，其关键之处就是在予挖掘算法的选择。常用于入侵检测巾 的数据挖掘算法主要有关联规则分析、序列模式分析、分类分析以及聚类分析。 2 4 。l 关联规则分析 关联规则分析算法是本文主要研究和应用的算法，所以在第3 章中将重点对 其进行分概与研究。下面先给出关联规则分析的相关概念和属性。 关联规则是数据挖掘的一个重要的研究方向，它是r a g r a w a l 瞳鲫等人1 9 9 3 年首先提出的。它用于确定不同项目集之翔酶联系，找出关联规则的挖掘，我们 可以找出事物之问的内在联系，为决策提供支持。关联规则最初是用于商业中， 著名的啤酒和尿布的故事就是这个道理。 下面从数据挖掘出发，给出关联规则形式化的定义。 假设薹= 缸；，薹：，至 是项的集合。设任务相关的数据d 是数据库事务的集合， 其中每个事务t 是项的集合，使得r 互，。每一个事务有一个标识符，称作t i d 。 设x 是薹中项的集合，称作项集( 量毫e 掇s e 专s ) ，事务善包含x 当且仅当x 主f 。 如果x 中有k 个项目，则又称x 为k 一项目集，或x 的长度为k 。 定义l ：关联规则泣 1 0 江苏大学硕士研究生毕业论文 关联规则是形如x 专y 的蕴涵式，其中，石j ，y 王，盟xn y 盘彩。 规则的支持度和置信度是规则兴趣度的两种度量。它们分别反映所发现的规 则的有用性和确定性。 规则x 一】，在事务集d 中成立，具有支持度s ，其中s 是d 中事务包含xu 】， 的百分比。它是概率p ( x u y ) 。揽刘x 专y 在事务集d 中具有置信度e ，其 中c 是d 中包含x 的事务同时也包含y 的百分比。这是条件概率p ( yx ) 。即 s u p p o r t ( x y ) = p ( x u y ) ( 2 一1 ) c o n f i d e n c e ( x 争y ) = p ( y l x )( 2 2 ) 震时满足最小支持度阀值 m i n - s u p ) 和最小置信度阙值( | l l i 轧e o n f ) 的规则 称作强规则。满足最小支持度的项集称为频繁项集( f r e q u e n t “e m s e t ) 。 关联规则主要有基于宽度的算法和基于深度的算法。基于宽度的算法通过挖 掘频繁k 一项集来挖掘频繁k + 卜项集，该类算法需要多次扫描事务数据库，因而效 率比较低。疆前，基予宽度的算法有：r a g r a 宵a l 等人提出a p r i o r i ，a p r i o r i t i ! d 和a p r i o r i h y b r i d 算法，j s p a r k 等人的d h p 算法汹1 等。a p r i o r i 算法是这类算法的 典型代表，需扫描数据集的次数等于最大频繁项目集的项臣数。磊p r i o r i t i d 算法 在a p r i o r i 算法的基础上对数据集进行修剪，以减少扫描数据库的时间，但对数 据集的修剪需要额外的计算和i o 操律。d p 算法采用哈希技术对数据集和候选项 目集进行修剪，特别是对候选2 项目集的修剪特别有效。a p r i o r i h y b r i d 算法是 a 弦主o r i 算法和矗p r i o r i t i d 算法的融合，该算法开始采用a p r i o r i 算法，然后在每 次扫描完数据集之后计算修剪后的数据集的大小；若修剪后的数据集可在内存中 进行处理，燹| j 切换至a p r i o r i t i d 算法直到找出所有的频繁项目集。 基于深度的算法的思想是采用树的深度遍历的方式来挖掘频繁项集，该类算 法比基于宽度的算法效率高效得多。此类算法中最新最高效的是j h a n 等人提出 的f p g r o w t h 算法1 。目前已经提出的用于发现最大频繁模式的典型算法有 滟f i a 汹3 以及g e n m a x 等。磷a f i a 采用垂直二进制位图表示投影数据库，同时使用 p a r e n t e q u i v a l e n c ep r u n i n g 和d y n a l n i cr e o r d e r i n g 等方法来减少搜索空闻； g e n m a x 也采用数据库垂直投影方法，同时使用了p r o g r e s s iv ef o c u s i n g 和 d i f f s e tp r o p a g a t i o n 这两种新技术，前者用来剪去非最大频繁项目集，后者用来 对频繁性进行快速检查。 目前，已经用于入侵检测的关联规则算法有a p r i o r i ，d h p ，f p 树等算法以及它 1 1 江苏大学硕士研究生毕业论文 们的改进算法。 2 4 2 序列模式分析 序列模式分析和关联分析相似，也是为了挖掘数据之间的联系，但它的侧重 点在于分析数据问的前后序列关系。它能发现数据库中形如“在某一段时问内， 顾客购买商品a ，接着购买商品b ，而后购买商品c ，即序列a b c 出现的频度较 高”之类的知识，序列模式分析描述了在给定交易序列数据库中，每个序列是按 照交易时间排列的一组交易集，挖掘序列函数的作用在这个交易序列数据库上， 返回该数据库中出现的高频序列。主要的序列模式挖掘算法有a p r i o r i a l l ， a p r i o r i s o m e ，g s p ，s p a d e 以及p r e f i x s p a n 等。 a p r i o r i a ll 算法是对所有的大序列进行计数来计算支持度，包括非最高序 列，而a p r i o r i s o m e 算法通过避免或减少对那些被更长序列所包含的序列即非最 高宇列进行计数来提高系统性能。在低支持度的情况下，相对来说计算过程中会 产生更长的大序列，因此会有更多的非最高序列产生，此时a p r i o r i s 0 m e 更好； 如果在高支持度情况下，则应采用算法a p r i o r i a l l 。 g s p 算法从性能上与a p r i o r i a l l 算法相比，g s p 计算的候选序列比较少，速 度快，具有很好的s c a l e u p 特性，设定了有效的时间限制和滑动窗口。 1 9 9 9 年m j 提出了使用格搜索技术的s p a d e 算法。该算法使用垂直的 i d 一1 i s t 数据库，通过临时合并列举频繁序列，并用格论方法分解搜索空间。克 服了以往算法中多次扫描数据库的缺陷，避免使用复杂的h a s h 结构。 2 0 0 1 年j i a np e i 和j i a w e ih a n 提出了p r e f i x s p a n 算法。该算法提出前缀、 投影、后缀等概念，使用频繁的去划分搜索空间并产生一些小投影数据库，然后 再搜索相关的序列。该算法利用模式增长方法使得搜索更集中更确定，可以挖掘 出长序列模式躺。 2 4 3 分类分析 设有一个数据库和一组具有不同特征的类别标记，该数据库中的每一个记录 都被赋予一个类别的标记，这样的数据库称为示例数据库或训练集。分类分析就 是通过分析示例数据库中的数据，为每个类别做出准确的描述，或建立分析模型， 或挖掘出分类规则，然后利用这个分类规则对其它数据库中的记录进行分类。 入侵检测可以看作是一个分类问题，就是希望能把每一个审计记录分类到可 能的类别中，即正常或某种特定的入侵。一般来讲，分类根据系统特征进行，所 1 2 江苏大学硕士研究生毕业论文 以，分类任务的关键步骤就是选择j 下确的系统特征。例如可以根据黑客入侵的危 害程度将入侵行为划分为致命的入侵、一般的入侵以及弱入侵三类，当然，还可 以根据其它各种标准进行分类。分类分析检查以前的黑客入侵行为，根据分类标 准，对每一个危害等级进行分类，然后给出每个等级的描述。 目前，有多种分类分析模型得到应用，几种典型的模型包括线性回归模型、 决策树模型、贝叶斯分类模型、基本规则模型和神经网络模型。 2 4 4 聚类分析 聚类分析是分类分析的逆过程，是根据一定的规则，合理地划分一组未标记 的记录集合，按照相似性的原则归纳成若干类别，用显式或隐式的方法描述这些 类别，其目的是使得属于同一类别的个体之间的距离尽可能的小，而不同类别上 的个体间的距离尽可能的大。 聚类分析包括系统聚类、分解、加入、动态聚类、模糊聚类、运筹、统计、 机器学习、神经网络和面向数据库等方法。采用不同的方法，对于相同的记录集 合可能有不同的划分结果。 2 5 本章小结 本章介绍了入侵检测和入侵检测系统的定义以及入侵检测的分类，重点介绍 了数据挖掘在入侵检测中的应用。 1 3 江苏大学硕士研究生毕业论文 第三章f p 树算法的改进 3 1 经典f p 算法 h a nj i a w e i 等人2 0 0 0 年提出了一种基于f p t r e e 的关联规则算法f p g r o w t h ， 该算法只需扫描数据库两次，不产生候选项集，采用了“分而治之”的策略，首 先将事务数据库压缩到一棵频繁模式树中，然后再将压缩后的数据库分成一组条 件数据库，并分别挖掘每个条件数据库。 算法f p g r o w t h 分为以下两步：第一步，构造频繁模式树f p t r e e 。在f p t r e e 中，每个节点由4 个域组成：节点名称i t e m _ n a m e ，节点记数s u p p o r t c o u n t ，节 点链指针】i n k ，孩子节点c h i l d 。第二步，调用f p g r o w t h 挖掘所有频繁项目集。 频繁模式树f p t r e e 的构造如下： ( 1 ) 扫描事务数据库d 一次，收集频繁项的集合f 和它们的支持度计数。 对f 按支持度计数降序排序，结果为频繁项列表l 。 ( 2 ) 创建f p 树的根节点，以“n u l l ”标记它。对于d 中每个事务t r a n s ， 执行： 选择t r a n s 中的频繁项，并按l 中的次序排序。设排序后的t r a n s 中频繁项 列表为 pp ，其中，p 是第一个元素，而p 是剩余元素的列表。调用 i n s e n t r e e ( p l p ，t ) 。该过程执行情况如下：如果t 有一个子女n 使得 n i t e m n a m e = p i t e m n a m e ，则n 的计数增加1 ；否则，创建一个新节点n ，将其 计数设置为1 ，链接到它的父节点t ，并且通过节点链结构将其链接到具有相同 i t e m n a m e 的节点。如果p 非空，递归地调用in s e n t r e e ( p ，n ) 。 定义1 条件模式基乜钉：项朋条件模式基为瑚前缀路径集。 基于f p t r e e 的频繁项目集挖掘算法是通过调用f p g r o w t h ( f p t r e e ，n u l1 ) 来实现的。该过程的实现如下： p r o c e d u r ef p g r o w t h ( t r e e ，q ) ( 1 ) i ft r e e 含单个路径pt h e n (