（计算机应用技术专业论文）基于合并式fpgrowth的网络入侵检测模型的研究.pdf

摘要 随着网络和其它信息技术的广泛应用，网络系统的安全变得至关重要。 入侵检测是目前保护网络系统安全的关键技术和重要手段，成为了网络安全 体系结构的重要课题之一。 现行的入侵检测技术在检测新的攻击或未知特征的入侵方面能力较弱， 而且检测的准确性与实时性达不到实际应用的需求；另外，在网络数据流量 如此之多的情况下，传统的入侵检测就更难达到要求将数据挖掘技术用于 入侵检测可以有效地检测已知入侵以及未知攻击模式，因此，研究数据挖掘 的算法对于提高入侵检测的准确性和时效性具有重要的意义 本文以入侵检测模型的建立和数据挖掘算法在入侵检测方面的应用作为 研究的主线。首先，研究和分析了入侵检测和数据挖掘的理论基础及相关的 技术内容。然后着重的研究了关联规则分析的f p - g r o w t h 算法，为了进一步 降低传统f p g r o w t h 算法的时间复杂度，针对传统的f p - g r o w t h 算法而提出 了合并式f p - c , r o w t h 算法，并根据两种算法设计了实验测试程序，以便对两 种算法进行比较验证接着构建了基于数据挖掘的网络入侵检测模型框架， 分别设计了该模型框架中各功能模块的结构图，同时详细阐述了数据采集和 数据预处理模块、数据分析模块以及前台管理模块的具体功能，对于该模型 的核心模块，即数据分析模块，采用合并式f p - o r o w t h 算法进行挖掘数据。 最后本文探讨了该模型框架中一些功能模块的实现情况以及模型实现后所需 要的性能评估指标。 关键词：入侵检测：数据挖掘；关联规则；f p - g r o w t h 算法；合并式f p - o r o w t h 算法 哈尔滨工程大学硕士学位论文 、b s t r a e t w i t ht h ee x t e n s i v ea p p l i c a t i o no fn e t w o r ka n do t h e ri n f o r m a t i o nt e e t m o l o g y , t h es e c u r i t yo f n e t w o r ks y s t e mb e c o m e sv e r yi m p o r t a n t t h ci n t r u s i o nd c t e c t i o l li s t h ek c yt e e l m o l o g ya n di m p o r t a n tm e t h o do fp r o t e c t i n gt h es e c u r i t yo fn e t w o r k s y s t e m i ti s co ft h ei m p o r t a n tt o p i c sa b o u ts y s t e ms t r u c t u r eo fn e t w o r k s e c u r i t y 1 1 a b i l i t ro f p r e s e n tt e c h n o l o g yo f i n t r u s i o n d c ! t e c l j o ni sw e a k e rt ot h e 嗍 a t t a c ko tt h ei l n l m o w nc h a r a c t e r i s t i c i na d d i t i o n , t h ea e e l r a e y 捌r e a lt i m eo f d e t e c t i o n 锄r i o ta c h i e v el b ed e m a n do fp r a c t i c a la p p l i c a t i o n a mi ti sm o r e d i f f i c u l tf o rt r a d i t i o n a li n t r u s i o nd c , t e c t i o nt om e e tt h er e q u e s tu n d e rt h ec o n d i t i o n o f s om a n yn e t w o r kd a t ah a t 五e 1 1 l ci n l l u s i o nd e t l 。c t i o l l lm 蛾l j 辩o ft h ed a t am i n i n gt e e l m o l o g y 锄 e f f e c t i v e l yd e t e c tt h ek n o w ni n l r u s i o na n du n k l l o w na t t a c kp a t t e r n 酬o l e ，i ti s v e r ys i g n i f i c a n tt os t u d yt h ea l g o r i t h m so fd a t am i n i n gi no r d e rt oe n h a n c et h e a c e l a a e ya n df i l ee f f e c t i v e n e s so f i n t r u s i o nd e 删o m 1 1 把c o n s t n l c t i o no f i n m 坞i o nd e t e c t i o nm o d e la n dt h ea p p l i c a t i o no f t h ed a t a m i n i n ga l g o r i t h mi nt h ei n t r u s i o nd e t c c t i 矾t h em a i nc o l l t e n to ft h et h e s i s f i r s t l y , t h eb a s i ct h e o r y 棚缸r e l a t i v et e c h n o l o g yo fi n t r u s i o nd e t e c t i o na n dd a t a m i n i n ga i s t u d i e dl a da a l r z e d t h ea l g o r i t h mo ff p - g r o w t l ai sm a i n l ys t u d i e d t of l l r t h e l rr e d u c et h et i m ec o m p l e x i t yo ft r a d i t i o n a lf l - c , r o w t h , q ni n c o r p o r a t e f i 一g r o w t ha l g o r i t h mi sp u tf o r w a r d t oc o m p a r et w ok i n d so fa l g o r i t h m s , t h e e x p e r i m e n t a lt e s t i n gp r o g r a m s 娥d e s i g n e da c c o r d i n gt ot h et w oa l g o r i t h m s a n d t h e n t h em o d e lf i a m c w o r ko fn e t w o r ki n l a u s i o nb a s e d0 1 1d a t am i n i n gi s c o n s l l u c t e d t h e 刚n k ：t l 腓g r a p h so ff u n c t i o nm o d u l e si n t h em o d e l 黜 r e s p e c t i v e l yd e s i g n e d m e a n w h i l e , t h ef l , i i i c i i o i i so fd a t a 鲷l h 甜m o d u l e , d a t a a n a l y s i sm o d u l ea n dm a n a g e m e n tm o d u l ea 弛e x p a t i a t e d f o rt h ec o m o d u l eo f t h em o d c 卜1 d a t aa n a l y s i sm o d u l e , t h ei n c o r p o r a t ef p - g r o w t ha l g o r i t h mi s a d o p t e dt om i n ed a t a f i n a l l y , t h ei m p l e m e n to fs o m ef t m c t i o nm o d u l e sa n d p e r f o r m a n c et a r g e ta r ed i s c u s s e d k e y w 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 nr u l e s ；f p - g r o w t h a l g o r i t h m ；i n c o r p o r a t ef p - g r o w t ha l g o r i t h m 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：理 日期：聊年2 月堂日 哈尔滨工程大学硕士学位论文 1 1 研究的背景及意义 第1 章绪论 随着计算机网络的不断发展，全球信息化已成为人类发展的大趋势，人 类享受着信息技术带来的便利，同时也面临各种安全事件的威胁习前，在 网络安全领域中有多种安全防护方法应运而生，如避免程序出错、用户签名、 加密以及防火堵等，这些都属于避免计算机和网络系统受到入侵的静态防护 技术，也是保护计算机和网络系统的一道基本防线“，但是随着计算机软件越 来越大，系统变得越来越复杂，而且现今的网络数据庞大、更新快，仅仅采 取这些静态防护措施避免入侵很难达到目的。因此，解决信息安全防护技术 的相关问题迅速成为了一个多学科交叉研究的热点。本文正是基于这样背景 下进行研究工作的。 入侵检测技术是种积极主动的安全防护技术，成为了目前网络上广泛 应用的技术和管理手段。但是当前大多数的入侵检测系统是通过手工定制的 方法建立起来的，例如：在滥用检测系统中，一些入侵模式需要用特定的模 式语言进行手工编写；在异常监测系统中，需要根据系统设计者的经验并利 用审计数据的特征和度量加以描述入侵模式这使得入侵检测的效率以及对 付攻击行为的能力受到了一定的限制因此，迫切需要有效的工具帮助人们 及时、准确地从海量的数据中发现数据之间存在的关系或模式、找出有用的 信息以便做出正确的决策。数据挖掘正是这样一种工具和技术。它的优势是 可从大量的网络数据以及主机的日志数据中挖掘出正常的或入侵性的行为模 式一。 把数据挖掘的算法融入到入侵检测技术进行研究具有理论意义和实际应 用价值，因此本文的意义主要体现在以下三方面： ( 1 ) 网络安全是计算机科学的一个重要分支，这一领域的任何突破都将 推动整个计算机科学的发展； 哈尔滨工程大学硕士学位论文 ( 2 ) 入侵检测是网络信息系统的一种重要的动态防护手段，在当今的信 息社会中，对维护国家主权和保护人民的财产安全具有极其重要的作用； ( 3 ) 数据挖掘和入侵检测两种技术的有效结合，为数据挖掘提供宽广应 用前景的同时，也将极大地推动数据挖掘和入侵检测技术本身的研究与发展。 1 2 研究的国内外现状 数据挖掘技术本的迅速发展使得它在入侵检测领域中得到广泛的应用。 当前，国内外已有很多研究机构及大学教研室从事基于数据挖掘的入侵检测 方面的研究工作。 最早将关联规则引入入侵检测中进行研究的是美国c o l u m b i a 大学 w e n k el e e 所在的课题组。w e n 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 n d e t e c t i o n ) w e n k cl 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 ( a u d i t d a t a a n a l y s i s a n d m i n i n g ) 。a d a m 从t q , d u m p 审计轨迹中挖掘频繁模式，并以此发现入侵a d a m 首先将t c p f l p 流量数据进行预处理，从每个数据包中抽取其头部信息，为每个t c p i p 连接 建立一个连接记录，挖掘过程在连接记录数据集上进行。a d a m 的挖掘引擎 是由一组关联规则挖掘算法所组成的。用以实现训练和检测任务，挖掘引擎 的输出是一组可疑的关联规则，然后由分类引擎进行进一步处理a d a m 是 一个实时的异常入侵检测系统，其主要缺点是对纯净数据的依赖较多，虽然 具有一定的检测未知入侵类型的能力，但误报率较高一 在基于数据挖掘的入侵检测研究方面，有代表性的国内学者的研究成果 包括：中国科学院研究生院选择了层次化协作模型作为研究基础，在模型中 采用数据挖掘算法对安全审计数据进行分析处理，以便帮助系统自动生成入 2 哈尔滨工程丈学硕士学位论文 侵检测规则，从而建立异常检测模型；清华大学，提出了一种基于数据挖掘 方法的协同入侵检测系统框架，并采用a g 蹦t m 柚a g c 饥i 三层实体结构，使 用多种数据挖掘方法建立检测模型；华中科技大学的王卉将最大频繁项目集 挖掘算法用于入侵检测；武汉大学电子信息学院的凌军等人提出并实现了一 个基于规则的、层次化的智能入侵检测原型系统 总之，数据挖掘技术在入侵检测系统中的应用大大减少了手工和经验的 成分基于数据挖掘的网络入侵检测模型可以进行机器学习和模式扩充，入 侵检测效率和可靠性明显得到提高 1 3 研究的主要内容 如何将数据挖掘技术有效、灵活的运用到入侵检测模型中去将是本文主 要研究的问题，因此本文研究的内容主要包括： ( 1 ) 研究入侵检测系统的基本概念，分类、体系结构及发展方向； ( 2 ) 研究数据挖掘技术的基本概念，主要算法及应用，将它引入入侵检 测系统提供了理论基础； ( 3 ) 根据入侵检测的特点，构造基于数据挖掘算法的入侵检测模型； ( 4 ) 改进数据挖掘中f p - c - r o w t h 算法，并应用在模型中进行数据挖掘， 使其可以有效地从网络数据中挖掘出更为有用的规则，为入侵检测系统服务 3 第2 章入侵检测概述 作为一种新型的、积极主动的安全防护体系的入侵检测是新一代的网络 安全技术，它在众多研究人员的参与下快速的发展着，本文的研究离不开对 入侵检测的相关内容进行深入的认识与理解，因此对入侵检测进行概述性的 分析与研究是非常必要的 2 1 入侵检测的定义和功能 1 9 8 0 年，a n d e r s o n 首次提出了入侵检测的概念。他将入侵行为划分为外 部闯入、内部授权、用户的越权使用和滥用等三种类型，并提出用审计追踪 监视入侵威胁。 美国国际计算机安全协会对入侵检测的定义是：入侵检测是通过从计算 机网络或计算机系统中的若干关键点收集信息并对其进行分析，从中发现网 络或系统中是否有违反安全策略的行为和遭到袭击迹象的一种安全技术。 1 9 8 6 年，美国斯坦福国际研究所的d e d e n n i n g 首次提出了一种抽象入 侵检测模型i d e s 此模型独立于任何特殊的系统、应用环境、系统脆弱性或 入侵种类随后，在此基础上，经过二十年的发展，大量的入侵检测系统已 经被研制出来，并得到了一定范围的应用。 入侵检测系统i d s ( i n t r u s i o nd e t e 甜o ns y s t e m ) 是在计算机系统和网络 系统上实时进行入侵检测、报警、响应和防范的一个安全系统。入侵检测的 软件和硬件的结合就组成了d s 的体系结构n “。 总的来说，用i d s 来识别针对计算机系统和网络系统，或者更广泛意义 上的信息系统的非法攻击，包括检测外界非法入侵者的恶意攻击或试探，以 及内部用户的越权非法行动。它的主要功能就是：监视分析用户和系统的行 为、审计系统配置及漏洞、评估敏感系统和数据的完整性，识别攻击行为， 对异常行为进行统计，自动地收集与系统相关的补丁，审计跟踪识别违反安 4 哈尔滨工程大学硕士学位论文 全法规的行为，使用诱骗服务器记录黑客行为等一从而使系统管理员比较有 效地监视、审计、评估自己的系统。 2 2i d s 的信息获取 类似于监控系统，为了监视不同的图像，安装在不同位置的摄像头一样， i d s 根据系统的探测器所放置的位置的不同，分为两种获得信息( 采集数据) 的方式：网络入侵检测模块方式和主机入侵检测模块方式。 1 网络入侵检测模块方式 基于网络的探测器被安装在被监控的服务器的同一个h u b 或交换机上， 通过监听网络上到达服务器的报文来分析告警。其原理是：当一篇文章从网 络的一端传向另一端时，是被封装成个个小包( 报文) 来传送的，每个小 包包括了文章中的一段文字，在到达另一端之后，这些报文再被组装起来。 因此，本文可以通过检测网络中的报文来达到获得信息的目的。一般来说， 检测方式只能检测到本机的报文，为了监视其它机器的报文，需要把网卡设 置为混杂模式，只有数据包的目的地址是网卡的m a c ( m e d i a a c , c , e s sc o n l r 0 1 ) 地址是，网卡才会接受这个数据包并处理。通过在网络中放置一块入侵检测 模块，就可以监视被保护机器的数据报文w 2 主机入侵检测模块方式 基于主机的探测器被安装在所要监控的服务器上或者受保护的机器上， 通过收集服务器和主机中的系统日志和特定应用程序日志、捕获特定的进程 和系统调用等信息进行分析告警等w 3 两种方式的比较 ( 1 ) 信息来源方面：网络入侵检测模块方式只获得网络报文，而主机入 侵检测模块方式所获得的信息比较全面。 、 ( 2 ) 检测结果方面：网络入侵检测模块方式的准确性没有主机入侵检测 模块方式高。 ( 3 ) 系统平台：网络入侵检测模块方式不受系统平台限制，只是根据不 同的网络结构设计不同的实施方案，而主机入侵检测模块方式受操作系统平 台限制，当网络中的机器存在不同的操作系统时，不能保证每个操作系统都 蔓 哈尔滨工程大学硕士学位论文 有对应的主机入侵检测模块 c 4 ) 定制的规则：网络入侵检测模块方式定制的规则相对较多，且需要 全面，而主机入侵检测模块方式是有针对性地定制规则，例如，一个在服务 器和个人计算机上安装了h i d s 的网络，对于安装在邮件服务器上的h i d s 主要设置和邮件服务器相关的规则，安装在w e b 服务器上的h i d s 主要设置 和w e b 服务相关的规则，零散的计算机可以使用常用的规则集，当有新的漏 洞公布后，在及时或定期的更新以检测新漏洞，如果运行h i d s 的计算机上 没有运行域名服务( d n s ) ，就不需要加上用于检测d n s 攻击的规则集 ( 5 ) 监视范围；网络入侵检测模块方式能够监视整个网络，而主机入侵 检测模块方式只能保护它所在的计算机。 ( 6 ) 安装费用：网络入侵检测模块方式相对较低，在网络中安装一个入 侵检测模块即可，主机入侵检测模块方式相对较高，需要在每个机器上安装 基于主机的入侵检测模块 2 3i d s 的检测方法 2 3 1 误用检测 误用检测( m i 戳瑚d e t e 甜o n ) 又称为滥用检测，此检测原理和现今的杀 毒软件的工作原理类似，都是基于病毒库的特征来识别已经被感染的文件、 程序和动态网页内容并阻止它们进入计算机系统。滥用检测所建立的不是病 毒库，而是攻击库，攻击库是已知攻击的行为特征的集合i d s 对所获的数 据进行各种处理后，与这些特征的集合进行匹配工作。如果匹配成功，则指 出发生了攻击行为。常用的误用检测技术有以下几种。 1 模式匹配 它是一种用于误用检测分析的较传统和简单的入侵检测方法它建立一 个攻击特征库，然后将捕获的事件记录与特征库中的记录逐一比较，判断是 否存在攻击。这种分析技术原理简单、扩展性好、效率高，可用于实时检测； 缺点就是它只能用于检测比较简单的攻击模式，误报率也较高。由于系统的 6 哈尔滨工程大学硕士学位论文 实现、配置、维护都很方便，模式匹配技术得到了广泛的应用 2 专家系统 专家系统主要用于误用检测，针对有特征的入侵行为进行检测，然后将 有关的入侵知识转换成i f - t h e n 结构，i f 部分为入侵特征，t h e n 部分是系统防 范措施。专家系统的建立依赖于知识库的完备性，而知识库的完备性又取决 于审计记录的完备性与实时性。使用专家系统规则表示一系列的活动时不具 有直观性，除非由专业人员来做专家系统的升级工作，否则规则的更新将是 很困难的“，。7 2 3 2 异常检测 异常检测( a n o m a l y 舾c t i ) 所建立的知识库是系统历史正常活动的 集合是否发生了攻击行为就要通过观察当前活动与知识库中正常活动之间 的差异来判断。异常检测的特点是学习正常，发现异常异常检测最大的好 处是可以检测到一些未知的攻击方法，因为它检测入侵的时候并不需要知道 各种具体攻击手法的特点常用的异常检测技术有以下几种： 1 统计分析 统计分析是在异常入侵检测中普遍使用的技术。它通过设置极限值等一 些方法，将检测数据与已有的正常行为加以比较，如果超出极限值，就认为 发生了入侵。 统计方法的最大优点是它可以“学习”用户的使用习惯，从而具有较高 检出率与可用性。但是它的。学习”能力也给入侵者以机会通过逐步“训练” 使入侵事件符合正常操作的统计规律，从而透过i d s 。另外一点，统计分析 极限值的选取是一个关键技术，因为它的选取并不是根据特定的攻击，因此 要选择有网络和系统特征意义的测量点 2 神经网络 神经网络具有自适应、自组织和自学习的能力，此项技术用于i d s 可以 检测未知的攻击基于人工神经网络构建的入侵检测技术能够很好的处理带 噪声数据，检测时不依赖于底层数据特征的统计假设，而且容易修改以适应 新的用户环境”一 7 哈尔滨工程大学硕士学位论文 2 3 3 两种检测方法的比较 1 检测结果 滥用检测检测率相对较高，因为检测的匹配条件描述清楚，所以可以明 确指示出当前发生攻击的类型，但是只能检测到已知的攻击模式，而异常检 测检测率相对较低，尽管无法明确指示攻击为何种类型，但是可以检测到未 知的入侵行为。 2 误报警率 滥用检测相对较低，而异常检测相对较高，因为系统的正常活动是不断 变化的，需要不断的学习，所以在学习阶段，异常模式的 d s 在正常工作可 能会生成额外的虚假报警信号，或者在此阶段，信息系统遭受非法的入侵攻 击后，学习结果中可能包含了相关的入侵行为的信息，使得今后系统无法检 测到此种入侵行为 3 可移檀性 滥用检测的可移植性较差，需要在某个特定的环境下生效，而异常检测 较少依赖特定的操作系统环境。 4 内部用户 滥用检测对于检测内部用户的滥用权限活动很困难，而异常检测对内部 用户超越权限的违法行为检测能力相对较强。 5 报告的数据 滥用检测报告的数据是一条指示特定攻击行为发生的警告信号，其中还 包含相关的提示数据，而异常检测生成的数据量多，这些数据量都是超出期 望行为范围的事件 6 系统配置工作量 滥用检测系统配置工作量较少，并且相对容易，而异常检测比较难配置， 需要对系统得已知和期望的行为模式做全面综合的定义，因此也就需要更多 的数据收集、分析和更新工作 哈尔滨工程大学硕士学位论文 2 4 高级的检测技术 1 遗传算法 遗传算法是进化算法( e v o l u t i o n a r ya l g o r i t h m ) 的一种。它引入了达尔 文在进化论中提出的自然选择的概念，并利用对染色体的编码和相应的变异 及组合，形成新的个体的一种算法。遗传算法在入侵检测中的应用主要体现 在搜索过程中自动获取和累积有关搜索空间的知识，并自适应地控制搜索过 程，从而得到最优解或次最优解w 2 。免疫技术 计算机系统的保护机制与生物的生理免疫系统之间具有显著的相似性。 即两个系统运行的关键是执行“自己”和。异己”的识别能力。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 n e s t 研究组利用免疫技术，并针对主机 系统调用的审计数据进行分析处理，研究出系统调用短序列方法。认为特权 进程的系统调用的短序列相对稳定，可以代表。自己”。在检测时，通过比较 特权进程的系统调用序列与已建立的模型的相似程度发现异常，如果相似程 度较低，说明是异常。如果能够获得程序运行的所有情况的执行轨迹，那么 得到的程序轮廓特征将会很好地刻画程序的特征，而基于它的检测系统将会 具有很低的误检率”， 3 协议分析 与传统的模式匹配技术相比，协议分析技术弥补了模式匹配的一些不足， 是新一代m s 探测攻击的主要技术，它利用网络协议的高度规则性快速探测 攻击的存在，它通过对协议进行解码，减少了i d s 需要分析的数据量，从而 提高了解析的速度。 4 数据挖掘 数据挖掘技术是一项通用的知识发现技术，其目的是要从海量数据中提 取对用户有用的数据。将该技术用于入侵检测领域，利用数据挖掘中的关联 分析、序列模式分析等算法提取相关的用户行为特征，并根据这些特征生成 安全事件的分类模型，应用于安全事件的自动鉴别一个完整的基于数据挖 掘的入侵检测模型要包括对审计数据的采集，数据预处理、特征变量选取、 9 哈尔滨工程大学硕士学位论文 算法比较、挖掘结果处理等一系列过程。数据挖掘应用的关键点在于算法的 选取和建立一个正确的体系结构一将数据挖掘技术应用于入侵检测是入侵 检测研究的一个热点问题，也是本文的研究重点，将在以下几章进行详细的 讨论。 2 5 本章小结 本章是论文研究的基础和铺垫。首先介绍了入侵检测的定义以及入侵检 测获取信息的两种方式，并对这两种方式的各个参数指标进行了详细的比较； 然后详细介绍了两种基本检测方法，同时对它们进行了全面的比较最后总 结了目前入侵检测的高级技术方法。 第3 章数据挖掘综述 数据挖掘属于数据库技术和机器学习两个学科的交叉研究领域，它利用 数据库技术对现实世界中存在的一些具体数据进行前端的处理，同时也利用 机器学习方法从处理后的数据中提取有用的知识。研究数据挖掘技术与入侵 检测的融合问题，首先就要深入研究与数据挖掘有关的内容，因此本章将对 数据挖掘进行综述性的分析及研究。 3 1 数据挖掘概述 3 1 1 数据挖掘定义及其功能 1 定义 数据挖掘( d a t am 越呜，d m ) 是源于大型零售商面对决策支撑问题而 提出的。数据挖掘也是大型数据库中知识发现( k n o w l e d g ed i s c o v e r yf r o m d a t a b a s e ，k d d ) 的一个步骤，主要是利用某些特定的知识发现算法，在一 定的运算效率的限制下，从大量的、不完全的、有噪声的、模糊的、随机的 数据库中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息 和知识的过程w 2 功能 ( 1 ) 数据总结或称之为描述( d e s c f i 砸) 目的是对数据进行浓缩。 给出总体的综合描述，实现对原始数据的总体把握。常用的数据描述方法是 统计学的传统方法，如计算数据项的总和、均值、方差等基本描述统计量和 绘制直方图、折线图等统计图形。 ( 2 ) 分类( c l a s s i f i c a t i o n ) 就是研究已分类资料的特征，分析对象属性， 据此建立一个分类函数或分类模型，然后运用该模型计算总结出数据特征， 将其它未经分类或新的数据分派到不同的组中计算结果通常简化为几个离 哈尔滨工程大学硕士学位论文 散值，常用来对资料作筛选工作。 ( 3 ) 聚类( c l u s t e r i n g ) 当需要分析的数据缺乏描述信息或是无法组成 任何分类模式时就采用聚类的方法。将组群之间的差异识别出来，并对个别 组群内的相似样本进行挑选，实现相同群组数据相近，不同群组数据相异。 分类和聚类两者功能不同，分类是根据预先定好的一些特征值进行对象分组， 聚类是在事先不知道的情况下根据对象的一些相似特征分组。 ( 4 ) 估计与预测( e s t i m a t i o na n dp r e d i c t i o n ) 估计是根据已有的资料， 对某一参数或数值进行估计，来获取数据其它未知属性之值。预测是根据对 象属性、过去的观察值和有关资料对该属性的未来值进行预测，估计预测使 用的技巧主要是回归分析、时匈数列分析及人工神经网络方法 ( 5 ) 关联和序列发现( c o r r e l a t i o na n ds e q u e n c ed i s c o v e r y ) 数据库中 的数据一般都存在关联关系，即变量之间存在某种规律，关联就是要找出事 件或资料中同时出现的东西。序列分析的相关关系是在关联中增加了时间属 性因此关联分析就有了简单关联和时序关联之分如第一次购买电脑的顾 客中9 5 的人同时购买电脑应用软件，此为简单关联一支股票前一天上涨， 则第二天股票上涨的可能性为8 5 这就是时序关联。由于并不知道数据库中 数据的关联是否存在精确的关联函数，即使知道也是不确定的，因此关联分 析生成的规则带有可信度，可信度级别度量了关联规则的强度一 3 1 2 数据挖掘用于入侵检测的优势 数据挖掘通常应用于市场行销，金融投资、生产制造等领域，但在入侵 检测设计领域中运用数据挖掘技术对网络业务进行分析也具有明显优势，主 要体现在以下几方面： ( 1 ) 网络中监测到的数据量大且种类繁多，并具有稳定的数据来源，适 合进行数据挖掘； ( 2 ) 网络中监听到的数据按其所具有的不同属性可以进行分类，同时， 不同的数据之间的确存在有某种相关性，如一个连接往往伴随另一种连接发 生。因此，运用数据挖掘技术对审计数据进行挖掘能够得到有价值的信息； ( 3 ) 从各种渠道所获得的审计数据，经过加工处理之后适合运用数据挖 1 2 哈尔滨工程大学硕士学位论文 掘中的联系分析方法 3 2 入侵检测中的数据挖掘方法 数据挖掘在入侵检测中的应用一般包括数据源的选择、数据预处理和挖 掘算法选择几个主要问题，其关键之处就是在于挖掘算法的选择常用于入 侵检测中的数据挖掘算法主要有：关联规则分析、序列模式分析、分类分析 以及聚类分析。 3 2 1 关联规则分析 关联规则分析算法是本文主要研究和应用的算法，所以在第4 章中将重 点对其进行分析与研究下面先给出关联规则分析的相关概念和属性 1 关联规则的基本概念 ( 1 ) 数据项与数据项集 设i _ i l ，i e , ，i m ) 是m 个不同项目的一个集合，每个k ( k = l 2 ，o n ) 称 为数据项( i t e m ) ，数据项的集合i 称为数据项集( i t e m s e t ) ，简称为项集， 其元素个数称为数据项集的长度，长度为k 的数据项集称为k 维数据项集， 简称为i ，项集( k - i t e m s e t ) ( 2 ) 事件 事件( t r a n s a c t i o n ) t 是数据项集i 上的一个子集，每个事件均有个唯一 的标识符t i d 与之关联，不同事件的全体构成了全体事件集d ( 即事件数据 库) 。 ( 3 ) 关联规则 关联规则( a s s o c i a t i o nr u l e ) 可以表示成式3 1 ： r ：a = ，b( 3 一1 ) 其中a 、b 是两个项集，a c l ，曰c ，且a n b = a 关联规则的含义为：如果项目集a 在某一事件中出现，必然会导致项目 集b 也会在同一事件中出现。a 称为规则的先决条件，b 为规则的结果 哈尔滨工程大学硕士学位论文 ( 4 ) 支持 设i - i l ，1 2 ，i 。 是一组项目集，d 是一组事件集。d 中的每个事件t 是 一组项目，丁e ，假设一个项目集a ，一个事件t ，如果a c t ，则称事件 t 支持项目集a m 2 关联规贝i j 的属性 一般用四个参数来描述一个关联规则的属性：可信度( c o n f i d e n c e ) 、支 持度( s u p p o r t ) 、期望可信度和作用度。 ( 1 ) 可信度 设在一组事件集d 中，支持项目集a 的所有事件中有c 的事件支持项 目集b ，则c 称为关联规则a jb 的可信度。简单地说，可信度就是指在 出现了项目集a 的事件t 中，项目集b 也同时出现的概率有多大。如上面所 举的铁锤和铁钉的例子，该关联规则的可信度就回答了这样一个问题：如果 一个顾客购买了铁锤，那么他也购买铁钉的可能性有多大呢? 在上述例子中， 购买铁锤的顾客中有7 0 的人购买了铁钉，所以可信度是7 0 ( 2 ) 支持度 设在一组事件集d 中，有s 的事件同时支持项目集a 和b ，s 称为关 联规则a j b 的支持度。支持度描述了两个项目集a 和b 的并集c 在所有 的事件中出现的概率。例如，某天共有1 0 0 0 个顾客到商场购买项目，其中有 1 0 0 个顾客同时购买了铁锤和铁钉，那么上述的关联规则的支持度就是1 0 。 支持度表示成式3 - 2 ： 5 聊一似j 彤= 聊矽( 3 - 2 ) ( 3 ) 期望可信度 设d 中有d 的事件支持项目集b ，e 称为关联规则a j b 的期望可信 度。期望可信度描述在没有任何条件影响时，项目集b 在所有事件中出现的 概率有多大。如果某天共有1 0 0 0 个顾客到商场购买项目，其中有2 0 0 个顾客 购买了铁钉( 支持) ，则上述的关联规则的期望可信度就是2 0 期望可信度表示成式3 3 ： e x p e c t e d c o n f i d e n c e c a 号矽= 尸6 矽 ( 3 - 3 ) 式中：p ( b ) 事件中出现项目集b 的概率。 ( 4 ) 作用度 l 哈尔滨工程大学硕士学位论文 作用度是可信度与期望可信度的比值。作用度描述项目集a 的出现对项 习集b 的出现有多大的影响。因为项目集b 在所有事件中出现的概率是期望 可信度，而项目集b 在有项目集a 出现的事件中出现的概率是可信度，通过 可信度与期望可信度的比值反映了在加入出现项目集a 的条件后，项且集b 的出现概率发生了多大的变化。在上例中作用度就是7 0 f 2 0 = 3 5 作用度表示成式3 4 ： ： 工圻纠j 助：鱼婴塑竺兰璺( 3 - 4 ) e x p e c t e d c o n f i d e n c e ( a 占) 在关联规则的四个属性中，支持度和可信度能够比较直接地形容关联规 则的性质，它们也是两个度量有关规则趣味性的方法它们分别描述了一个 被挖掘出的关联规则的有用性和确定性，即可信度是对关联规则的准确度的 衡量，而支持度是对关联规则重要性的衡量支持度说明了这条规则在所有 事件中有多大的代表性，显然支持度越大，关联规则越重要有些关联规则 可信度虽然很高，但是支持度很低，说明该关联规则实用的机会很小，因此 也不重要。从关联规则定义可以看出。任意给出事件中的两个项目集，它们 之间都存在关联规则，只不过属性值有所不同。如果不考虑关联规则的支持 度和可信度，那么在事件数据库中可以发现无穷多的关联规则。事实上，人 们一般只对满足一定的支持度和可信度的关联规则感兴趣。因此，为了发现 有意义的关联规则，需要给定两个阙值，即最小支持度和最小可信度。前者 规定了关联规则必须满足的最小支持度，后者规定了关联规则必须满足的最 小可信度。一般称满足一定要求的( 如较大的支持度和可信度) 规则为强规 则( s t r o n gr u l e s ) 当一个关联规则满足最小支持度的阈值( m i n i m u ms u p p o r t t h r e s h o l d ) 和最小可信度的阈值( m i n i m u mc o n f i d e n c et h r e s h o l d ) ，则认为该 关联规则是有意义的。 期望可信度描述了在没有项目集a 的作用下，项目集b 本身的支持度 作用度描述了项目集a 对项目集b 的影响力的大小。作用度越大，说明项目 集b 受项目集a 的影响越大一般情况，有用的关联规则的作用度都应该大 于l ，只有关联规则的可信度大于期望可信度，才说明a 的出现对b 的出现 有促进作用，也说明了它们之问某种程度的相关性* ” 哈尔滨工程大学硕士学位论文 3 2 2 序列模式分析 序列模式分析和关联分析相似，也是为了挖掘数据之间的联系，但它的 侧重点在于分析数据间的前后序列关系。它能发现数据库中形如“在某一段 时间内，顾客购买商品a ，接着购买商品b ，而后购买商品c ，即序列 ajb 等c 出现的频度较高”之类的知识，序列模式分析描述了在给定交易 序列数据库中，每个序列是按照交易时问捧列的一组交易集，挖掘序列函数 的作用在这个交易序列数据库上，返回该数据库中出现的高频序列。主要的 序列模式挖掘算法有：a r i o d 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 l l 算法是对所有的大序列进行计数来计算支持度，包括非最高序 列，而a p r i o r i s o m e 算法通过避免或减少对那些被更长序列所包含的序列( 即 非最高序列) 进行计数来提高系统性能。在低支持度的情况下，相对来说计 算过程中会产生更长的大序列，因此会有更多的非最高序列产生，此时 a p r i o r i s o m e 更好：如果在高支持度情况下，则应采用a i 】f i o 血算法 g s p 算法从性能上与a p r i o r t a u 算法相比，g s p 计算的候选序列比较少， 速度快，具有很好的s c a i e u p 特性，设定了有效的时间限制和滑动窗口 1 9 9 9 年m j 提出了使用格搜索技术的s p a d e 算法。该算法使用垂直的 i d - l i s t 数据库，通过临时合并列举频繁序列，并用格论方法分解搜索空间。 克服了以往算法中多次扫描数据库的缺陷，避免使用复杂的h a s h 结构 2 0 0 1 年j i a np e i 和j i a w e ih a r t 提出了p r e f i x s p a n 算法。该算法提出前缀、 投影，后缀等概念，使用频繁的p r e f i x 去划分搜索空间并产生一些小投影数 据库，然后再搜索相关的序列该算法利用模式增长方法使得搜索更集中更 确定，可以挖掘出长序列模式一， 3 2 3 分类分析 设有一个数据库和一组具有不同特征的类别( 标记) ，该数据库中的每一 1 6 哈尔滨工程大学硕士学位论文 个记录都被赋予一个类别的标记，这样的数据库称为示例数据库或训练集。 分类分析就是通过分析示例数据库中的数据，为每个类别做出准确的描述， 或建立分析模型，或挖掘出分类规则，然后利用这个分类规则对其它数据库 中的记录进行分类 入侵检测可以看作是一个分类问题，就是希望能把每一个审计记录分类 到可能的类别中，即正常或某种特定的入侵。一般来讲，分类根据系统特征 进行，所以，分类任务的关键步骤就是选择正确的系统特征。例如：可以根 据黑客入侵的危害程度将入侵行为划分为致命的入侵、一般的入侵以及弱入 侵三类，当然，还可以根据其它各种标准进行分类。分类分析检查以前的黑 客入侵行为，根据分类标准，对每一个危害等级进行分类，然后给出每个等 级的描述m 。 目前，有多种分类分析模型得到应用，几种典型的模型包括：线性回归 模型、决策树模型、贝叶斯分类模型、基本规则模型和神经网络模型。 3 2 4 聚类分析 聚类分析是分类分析的逆过程，是根据一定的规则，合理地划分一组未 标记的记录集合，按照相似性的原则归纳成若干类别，用显式或隐式的方法 描述这些类别，其目的是使得属于同一类别的个体之间的距离尽可能的小， 而不同类别上的个体问的距离尽可能的大 聚类分析包括系统聚类、分解、加入、动态聚类、模糊聚类、运筹、统 计、机器学习、神经网络和面向数据库等方法采用不同的方法，对于相同 的记录集合可能有不同的划分结果w 3 3 本章小结 本章是对与入侵检测相关的数据挖掘算法的概述首先简要的介绍了数 据挖掘的定义；然后说明了数据挖掘的功能及其用于网络入侵检测上的优势； 最后对四种典型的数据挖掘分析方法分别进行了阐述。 1 7 哈尔滨工程大学硕士学位论文 第4 章关联规则算法的研究 关联规则分析是数据挖掘中一个重要的课题，不论关联规则的挖掘算法 有多少，都可以归纳为两类，一类是产生频繁项目候选集的算法，