《关联规则和序列模式算法在入侵检测系统中的应用》由会员分享，可在线阅读，更多相关《关联规则和序列模式算法在入侵检测系统中的应用（7页珍藏版）》请在金锄头文库上搜索。
1、关联规则和序列模式算法在入侵裣溯系统中的应用关联规则和序列模式算法在入侵检测系统中的应用胡笑蕾胡华平宋世杰( 国防科技大学计算机学院湖南长沙4 1 0 0 7 3 )摘要数器挖掘可以利用各种分析工具从海量数据中发现模型和数据阿的关系并做出预测针对入侵检测系统的特点，本文将关联规则算法与序列模式算法应用于入侵梧澜系统中，舟绍了将适当改进的关联规则A p r i o r i 算法与序尹l 楗式G S P 算法相结合挖掘辱始审计数据中纂繁模武的过程，并着重研究了逮两种算法结合扩展关联规则的算法应用关键字关联规则；序列模式；囊繁模式；入侵控测T h eA p p l l c m t i o nO f
2、A s s o c i a t i o nR u l e sA n dS e q w n t eP a t t e r uA l g o r i t h mI nI D S H UX a o - l e i ，I I UH m - p i n g ，S O N GS i n - j i e( C o l l e g e o f C o m p u t e r , N a t i o n a l U n i v c t - s i t y o f D e f e n s e T e c h n o o g y , C h a n g s h a 4 1 0 0 7 3 ，C h i n a )A
3、 b s t r a c t ：D a t am i n i n gc mf i n dt h er e l a t i o nb e t w e e np a t t e r na n dd a t af r o mt h el a r g en u m b e ro fd a t aa n dt h ef o r e c a s tw i l lb em a d e I nt h i sp a p e r , t h ea p p l i c a t i o no fa s s o c i a t i o nr u l e sa l g o r i t h ma n ds e q u e
4、n c ep a t t e r na l g o r i t h mi nI D Si sp r e s e n t e d T h ep r o c e s si n t e g r a t e df i - e q u e n c cp a t t e r nf r o ma u d i td a t aw i t hA p r i o r ia l g o r i t h ma n dG S Pa l g o r i t h m , i si n t r o d u c e d , a n dt h ea p p l i c a t i o no f a l g o r i t h m
5、 sw i t he x t e n d e da s s o c i a t i o nr u l e si sa l s op r e s e n t e d k e y w o r d ：A s s o e i a t i o nr u l e s ，S e a u c n c ep a t t e r n ，F r e q u e n c ep a t t e m ，I n t r u s i o nd e t e c t i o n1 引言随着网络安全问题的愈加严竣，人们更加关注入侵检测技术。入侵检测是指对于面向计算资源和网络资源的恶意行为的识别和响应，是包括技术、人、工具三方面因素
6、的一个整体。入侵检测系统( I D S ) 可以对系统或网络资源进行实时检测，及时发现闯入系统或网络的入侵者，也可预防合法用户对资源的误操作 13 m根据检测方法，在广义上可以将入侵检测技术分为异常检测技术和误用检测技术。误用检测技术由于依据具体特征库进行判断，所以准确度很高、方便响应。但与具体系统依赖性太强，移植性不好。维护工作量大，受已有知识的局限，难以检测出权力滥用。异常检测技术与系统相对无关通用性较强。可能检测出以前未出现过的攻击方法。但由于网络攻击的复杂性，专家知识等通常不完全、不准确的使误检率很高。因此，采用单一的入侵检测技术实现的入侵检测系统在有效性、适应性等方面存在局限性。数据
7、挖掘是从大量的数据中抽取出潜在的、有价值的知识( 模型或规则) 的过程。数据挖掘技术是一门新兴的交叉性学科涉及到机器学习、模式识别、归纳推理、统计学、数据库、数据可视化、高性能计算等多个领域的最新进展。数据挖掘按其功能可划分为：关联规则分析、序列模式分析、分类分析、聚类分析等。数据挖掘的应用领域十分广泛多样，目前国内外已开始研究数据挖掘技术在入侵检测系统中的应用。例如哥伦比噩大学的W e n k c L e e ”“”等人从1 9 9 5 年开始首先将数据挖掘技术应用于入侵检测，提出了各种入侵检测的方法。但在如何建立数据仓库、序列模式挖掘等方面只做了少量工作等。数据挖掘理论的成熟为入侵检测提供
8、了许多可行的算法。其中关联规则、序列模式等算2关联规则和序列模式算法在入侵捡测系统中的应用法在入侵检测系统的应用中尤其有用。关联规则是寻找在同一个事件中出现的不同项目的相关性。序列模式刚是更进一步把数据之间的关联性与时间联系起来。本文首先介绍了关联规则算法和序列模式算法以及具体算法A p r i o r i 、G S P 的核心思路：其次对算法应用问题进行了简单的描述：针对算法的应用，在提高挖掘的合理性和有效性方面，采用扩展的关联规则；最后详细地阐述了算法的应用及其可行性。2 关联规则和序列模式算法关联规则挖掘算法是发现大量数据中项集之间有趣的关联和相关联系( 即关联模式) 。序列模式挖掘算法
9、可以靛现不同数据记录之间的相关性( 卸满足用户指定的最小支持度要求的大序列) 。2 1关联规则算法2 1 1关联规则：设1 2 i l ，i 2 ，i m 是项的集合a 设任务相关的数据O 是数据库事务的集合，其中每个事务Z 是项的集合。使得T I 。设A 是个项集，事务T 包含A 。当且仅当A c T 有；关联规则是形如A 等B 的蕴涵式，其中A c I ，B c l ，并且A nB = o 。 规则A ；B 在事务集D 中成立，具有支持度s ，其中s 是O 中事务包含A u B 的百分比，即为概率P ( A uB ) 。规则A j B 在事务集D 中具有置信度c 如果D 中包含A 的事务同
10、时也包含 B 的百分比是c 。这是条件概率P ( B l A ) 。 即为以下公式：s u p p o R ( A 等B ) 2P ( A O B )( 1 ) c o n f i d e n c e ( A j B ) = P ( B I A )( 2 ) 式中支持度和置信度是两个规则兴趣度度量，分别反映发现规则的有用性和确定性。同时满足最小支持度阚值( m i n _ s u p ) 和最小置信度阈值( m i n _ c o n f ) 的规则称为强规则。项的集合称为项集。如果项集满足最小支持度，则称它为频繁项集。关联规则算法的挖掘是通常是一个两步的过程：找出所有频繁项集：根据定义，这些
11、规则出现的频繁性至少和预定义的最小支持记数一样：由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最小置信度。比较经典的算法有A p n o f i 算法、A p r i o r i T i d 算法。2 1 _ 2 & p d o d 算法A p r i o r i “1 使用一种称作逐层迭代方法，先生成较小的频繁项目集L k 1 ，由它产生较大的候选频繁集c 【k + l 】，再查询事务数据库，以确定哪些侯选项目集是频繁的，如此反复，直到无法生成侯选集为止。将关联规则挖掘算法的设计可以分解为两个子问题：找到所有支持度大于最小支持度的项集，这些顷集称为频繁项集。使用第1 步找到
12、的频集产生期望的规则。在入侵检测的数据挖掘过程中，采用A p f i o d 算法，仍然存在许多不足，需对算法进行如下的改进：减少整个数据库被多次访问次数：采用模式匹配识别频繁项目集时，如何提高效率；改进数据库中的项目。项集事务的定义方式，使之适应挖掘的要求。关联趣则和序列模式算法在入侵检测系统中的应用2 2序列模式算法2 2 1序列摸式：序列( s e q u e n c e ) 是一列排好序的项集。 假定项集中的项由一些连续藏数代替，这样个项集i 可以表示为( i ，i r 。i ) ，i j 代表一个项。一个序列S 则可以表示为 ，如果存在整数i i z ( i 。且a 1 包含于b ，
13、 a 2 包含于b 。，a _ 包含于b 。则称序列a 包含于序列b 。在一个序列集中如果序列S不包含于任何其他序列中，则称序列S 为最大项序列。序列模式挖掘通常分以下五个步骤进行：排序阶段( s o , tp h a s e ) 、大项阶段( 1 i t e m s e tp h a s e ) 、转换阶段( t r a n s f o r m a t i o np h a s e ) 、序列阶段( s e q u e n c ep h a s e ) 和最大项序列阶段( m a x i m a lp h a s e ) 。2 2 2G S P 算法R h g r a w a l 等”1 首
14、先提出序列模式挖掘的算法分别为h p r i o r i h l l 、A p r i o r i S o m e 和D y n a m i c S o m e 。由于挖掘出来的序列模式中。相邻项目的相隔时间可能会太远或太近，使得挖掘到的模式变得多余且无意义，拉长了挖掘时间。为改善此缺点，R A g r a w a l 提出的G S P 算法“，加入分类法、滑动窗口以及时间限制等，使得挖掘得到的信息更为有效。G S P 算法的核心思想为；第一次遍历数据库，生成大项序列。第K 次遍历：开始在第K 一1 次遍历中产生的候选序列中寻找种子集；重新遍历数据库寻找候选序列的支持度；这样在一次遍历的最后，
15、就可以决定哪些候选序列是真正的大项序列，这些序列构成下一次遍历的种子集。当不再发现大项序列时终止。3 基于数据挖掘的I D S 实现的简单描述将数据挖掘技术应用于I D S 的过程中，数据挖掘算法起到了关键作用。本文将基于数据挖掘的I D S 的具体实现分为如下的四个步骤( 如图1 所示) ：从原始审计数据中提取A S C I I 网络包( 网络型) 或主机事件数据( 主机型) 形成连接记录( 网络型) 或主机会话记录( 主杌型) ，包括一系列基本特征，放入数据仓库；使用关联规则算法、序列模式挖掘算法等相关的数据挖掘程序找出关联模式和序列模式，抽取出频繁模式：通过模式编码、比较、可视化，并进行
16、模式的使用和积累，找出纯入侵模式，然后构建特征；“利用分类器( 如R I P P E R 等分类算法) 使用分类器建立分类模型以得到检测模型。其中前两步的实现，即挖掘频繁模式的实现过程是关联规则、序列模式等算法应用的重点。图，挖掘频繁模式的实现过程关联规则和序列模式算法在入侵检测系统中的应用4 算法的应用算法的目的是挖掘数据仓库中存放的网络连接记录和士机会话记录，寻找记录中的关联模式和序列模式，从而抽取出频繁模式。利用算法挖掘审计记录的过程( 参见表1 所示) 为：寻找审计记录内的大项集采用关联规则A p r i o r i 算法i 寻找审计记录阀的大项序列采用序，B 模式G S P 算法进行挖掘。 表1 挖掘审计记录的过程T a b 1T h e p r o c e s s o f m m i n ga u d i tr e c o r d由于关联规则和序列模式算法仅利用了最小支持度和置信度，输出的仅仅是统计意义上的模式，并未重视某些优先属性的有效
