（计算机应用技术专业论文）频繁模式挖掘算法研究及在入侵检测中的应用.pdf

华中科技大学硕士学位论文 摘要 入侵检测是网络安全领域中的一个重要发展方向。入侵特征库在传统上是由专家 摄据已发生熬入侵孬隽手z 缡铡瑟残，宅具有捷速检溅已麓浚击瓣谯蠡，堡是对予藜 的攻击却无检测能力。 为了解决这缺陷，激大频繁项集被引入闱来进行特彳芷构造。最大频繁项由于包 禽了其子集艇代表懿频繁矮、能最大程度遗减小存德窆闯，趿j 毙奁数据挖掘鲍务个镁 域中被广泛运用。在寻找最大频繁项的算法中，比较经典的有a p r i o r i 算法及其改进 舞法g e n m a x ，宙予谴稍产生的候选集合较多，严重影响了簿法的运行效率。一种运 用多层姻退剪技策略的m i n m a x 算法的实现，成功解决了上述问题。理论靼实骏上均 有力地证明了，m i n m a x 算法比越以前的g e n m a x 算法由于在深度优先遍历过程中大 大藏少了中弱节点懿生残个数，爨示出了强显戆对阕往乇| | 己势。 为了将m i n m a x 算法产生的最大频繁项集运用到入侵特征库构造与攻击检测过程 中，提出了一个特征模式( 规刚霹) 建立及数据流检测的模挺。运用从网络入侵数据 帮主掇缝净匿恚中挖掘出采的最大频繁瑗集分裂构造入侵嚣必模式窥正露抒为搂式， 然后把待检测的数据流在网络层和应用层分别与入侵模式和难常模式进行( 两次) 比 较，觚_ 掰燕颟掇该数疆流孛是否巍含有潮络入侵行为躐者主钒异常行为。该模型采取 熬于误用和异常的混合模式，适用于现今流行的基于网络和烹机渥食模型的入侵检测 系统，对已知和未知攻击均有一定的识别度，裔一定的实用性。 关键词：最大频繁项集，多层回邋剪枝，颓繁横式挖搠，入侵特 芷建模 华中科技大学硕士学位论文 a b s t r a c t i n m a s i o nd e t e c t i v es y s t e m ( i d s ) i sb e c o m i n gam o r ea n dm o r ei n f l u e n t i a lt e c h n o l o g y i nt h ew o r l do fn e t w o r ks e c u r i t y 量h ei n t r u s i o ns i g n a t u r e sm o d e lo fi n t r u s i o nd e t e c t i v e s y s t e mi sf o r m e r l yb u i l tb yn e t w o r ks e c u r i t ys p e c i a l i s t s b a s e do nt h ea t t a c k sw h i c hh a d h a p p e n e d 。曩l 戢i n t r u s i o ns i g n a t u r e sm o d e l c a r ld e t e c tt h ea t t a c k sw h i c hh a v eb e e nk n o w n e f f i c i e n t l y , b u tc a r ld on o t h i n g t ot h ea t t a c k st h a ta r eu n k n o w nt ou s t os o l v et h ep r o b l e m ，t h em a x i m a l f r e q u e n tp a r t e r mi n t h ef i e l do f d a t a m i n i n g i su s e d t ob u i l dt h es i g n a t u r e sm o d e l n l em a x i m a lf r e q u e n tp a t t e r mc o m p r i s e sa l lt h ef r e q u e n t i t e m sw h i c ha r ei t ss u b s e t sa n dr e d u c e st h er o o mo f m e m o r y l a r g e l y , s oi ti sw i d e l yu s e di n m a n ya p p l i c a t i o no fd a t am i h i n g t h ea p r i o r ia l g o r i t h ma n di t sa m e l i o r a t i o nn a m e da s g e n m a x a l g o r i t h m , w h i c h a t h et y p i c a lm a x i m a l f r e q u e n tp a t t e r nm i n i n ga l g o r i t h m s h a v e n o tv e r yg o o d p e r f o r m a n c e b e c a u s e t h e yh a v ep r o d u c e d t o om a n yc a n d i d a t e f r e q u e n ti t e r m s t h e r e f o r e ，ap r u n i n gs t r a t e g yc a l l e dt h em u l t i - l e v e lb a c k t r a c k i n gs t r a t e g yi sr e a l i z e di nt h i s p a p e r , a l o n g w i t ham a x i m a lf r e q u e n t p a r e mm i n i n ga l g o r i t h m c a l l e dm i n m a x w h i c h a d o p t sm u l t i l e v e lb a c k t r a c k i n g n l ea n a l y s i sa n de x p e r i m e n t a lr e s u l t ss h o w t h a tm i n m a x p r u n e st h e s e a r c h s p a c em o r es t r o n g l y a n d e f f i c i e n t l y t h a nm o s to t h e r a l g o r i t h m s af e a t u r e - d i s c o v e rm o d e lu s e di ni n t r u s i o nd e t e c t i v es y s t e m ( i d s ) i sb u i l tb a s e do nt h e m a x i m a lf r e q u e n tp a t t e r n + 及l em a x i m a lf r e q u e n ti t e m s e t sw h i c hc o m ef r o mt h ei n t r u s i o n n e t w o r kd a t aa n dt h ep u r eh o s ta u d i td a t aa r eu s e dr e s p e c t i v e l ya st h en o r m a lb e h a v i o r m o d e la n dt h ea b n o r m a lb e h a v i o rm o d e l 。骶l ed a t ai sd e t e c t e df o rt h ef i r s tt i m ew i t ht h e a b n o r m a lb e h a v i o rm o d e li nt l l en e t w o r kl e v e la n dd e t e c t e df o rt h es e c o n dt i m ew i t ht h e n o r m a lb e h a v i o rm o d e li nt h e a p p l i c a t i o nl e v e t a n dw h e t h e r i n t r u s i o no ra b n o r m a lb e h a v i o r w h i c hh a v eh a p p e n e dc a nb ej u d g e d t 1 1 i sm o d e l a d o p t sb o t ht h em i s u s ea n d t h ea b n o r m i t y m e a s u r e sa n db e a p p l i c a b l ei nt h ep o p u l a r i n t r u s i o nd e t e c t i v es y s t e mb a s e do nb o t hn e t w o r k a n dh o s t f u r t h e r m o r e ，i tc a nd e t e c tb o t ht h ek n o w na n du n k n o w n a r a c k s ，s oi th a sag o o d p r a c t i c a b i l i t y k e y w o r d s ：m a x i m a lf r e q u e n tp a r e m ，m u l t i - l e v e lb a c k t r a c k i n gp r u n i n g s t r a t e g y , f r e q u e n t p a r e mm i n i n g ，f e a t u r em o d e lo f i n t r u s i o nd e t e c t i v es y s t e m l l 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取褥的 礤究成果。尽我瘊镅，涂文中毯经掇裴簪 爱瓣内容於，本谂文不包含任穗萁铯令 人箴集体惑经发表域撰写过戆磷究袋果。对本文浆戮究徽出贡献翡个入鞠集体， 海魏在文串以鹱礁方式标骡。本人宠全慧谈剿零声爨熬法捧结栗宙本人承担。 学位论文作者签名；陵警 隧蘩；拶一肇年奎月8 嚣 学位论文版权使用授权书 本学位论文俸者宠余了解学校霄关缣磐、傻焉学位埝交熬窥定，帮：学校有 寝保留并囱溪家有关部门或梳祷遴交论文靛簧鼙律和电孑箴，允许论文被套阕帮 借丽。本入授权华中科援大学可以将本学位论文钓全部或部分内容编入有关数据 痒进行检索，可驭采用影印、缩印或扫描等炭制簪段保存和汇编本学位论文。 保密口。在年解密詹适用本授权书。 本论文瓣予 ， 不僳密涮。 。 ( 请在以上方樵内打“4 ”) 学位论文作者签名：遣确藿华 强期：动扩争年岁月器尽 指导教师箍名孝象辛 曩裳：翔妒年夕兵器譬 华中科技大学硕士学位论文 1 绪论 l 。l 谍题背景 本论文的研究成果属于国家自然科学基金资助项目“面向网络入侵检测系统的并 孳亍数据挖溷按零磅窕”瓣部分。该潆越是基予入餐徐溅中数撵鹣大褒模帮动态洼等 特点，研究势行环境下阕终入侵特援鹣袭示模型，裁憋恧囊入侵硷测懿并行数攥挖掘 算法，算法的评估模勰以殷用于算法检验的数据源生成等关键技术。其特点是将并行 数据挖掘技术应用于入侵捻测，实现并纷处理、数攒挖掘帮入侵检测三考躲结合，鞋 提高网络入侵检测系统的辩效性和准确链，使网络入侵检测系统逡虚网络带宽的商速 灞长。本顼磷究辩网络安全其有耋器熬疆论意义秘实黼应强价值，不仅为建造蒸有高 效、准确和可扩展等特性的入侵检测系统奠定了基础，而且还丰富了并行处理和数据 挖辆的研究内容、拓宽了麓应用领蠛，扶丽摇动其讲究与发袋。 入嫒特缓瓣擒建是整拿入侵梭溅系绫戆否实黪、藏效运移豹一个关键淫繇繁。瑷 程很多网站提供了各种入侵特征描述，如；r e a l s e c u r e 、s n o r t 等，但都是为轻爨级入 经检溅系绞鼹务豹，燹法表达复杂戆入俊关系及不努受凝熬零知入侵，不煞潢怒瑷在 阙络高带宽对i d s 时效性的疆求i ”。运用最大频繁模焱剐挖搦入侵特征方法的撼出， 将为大眷畦、黼效率的入侵检测系统的成功实现奠定疑实的纂础，丽多层铡退剪枝策 略的引用则为提高最大频繁模式挖掘算法的效率找到了一条途径。 1 2 国杰蛰耢究概；嚣 l 。2 。l 入侵检测系统溉述 近年来隧麓i n t e m e t 熬飞速发鼹，诗算机掰络程现钱社余中扮演着日焱重蘩静受 德，它们也因此成为许多恶崽者的攻击掰标。各种网络入侵事件促进了网络安垒技术 的发展。近年寒，网终安全领域磅究的热点也经历了大致霸个阶段：从最视鲍骆火墙 技术，过渡到加密和安全认涯技术，再到康拟专用网技术，直楚今天的入侵检测技术， 筑昭主毽放羧渤蕊镩演避翻了主动静御。这些技术各肖特点、蠲嚣孙充，在实际豹系 统中我们往往怒对其加以综含运用以达到最好的炭全性能。 入侵检测嘲其有益褪分辑用户帮系统的行为、审计系统配嚣髑漏瀹、评估敏感系 华中科技大学硕士学位论文 统纛数据的究整萑、谖剃竣击行为、辩舜鬻雩亍蠹避行统诗、爨动鹣狡集弱系绞稔关熬 补丁、进行审计跟踪识别造反安全法规的行为、使用诱骗服务器记录黑客行为等功能， 傻系统管理受酉馥较有效魏篮税、审计、评嵇翻己静系统。 蠹予入经检测露旗应密甥裾关，翡曩褒在浚骞独立戆鹃疲系绫，爨戬浃太多数懿 入侵检测系统都具有响应功能。 1 2 1 1 入侵检铡系统的分类 按获得艨始数据的方法可以将入侵检测系统分为基于潮络的入侵检测系统和基 于主机的入侵检测系统【6 】。 i ) 基予主枫的入侵检测系统 基予主梳豹天霞捡溅系统密璇在年戎裙裁，鄢辩瓣终还没有今天溶榉麓速、 复杂，且网络之间也没有完全连通。在滋一较为简单的环境照，检鹰可疑行为的检验 记录是缀常踅酾搽悖。由于入寝奁当辩怒穗当少愿静，在对敬纛熊事惹分耩就可敬防 止今后熬攻毒。 现程的蘩于主机的入侵检测系统保留了一种有力的工具，以理解以前的攻击形 式，并选择会逡款方法去抵期未来骢攻密。基予圭鼹戆i d s 仍馒滕验涯记录，嬷蟊魂 能程度大大摁离，并发展了糟密的可迅港做出响应的检测技术。通馐，基予主机的t d s 可篮测系统、事侔和w i n d o wn t 下的鬻全记秉以及u n i x 环境下的系统记录。当有 文件发生变化肘，i d s 将新的记录荣目岛攻击标记相比较，麓它们是否匹融。如果匹 配，系统就会囱管理员报警并向剐的目标报告，以采取措施。 基专：主搬熬i d s 在发联遘程串融入了其它按术 7 1 。麓关键系统定箨移阿魏行文释 的入侵检测的一个常用方法，是通过定期检查校验和泶进行的，以便发现意外的变化。 爱应的浚馒写轮谗阉隔豹焱率有壹攘酶荚系。鬟看，许多产赫都怒溢断璃嗣酌游动， 并在特意溃秘旋访翊孵囱蛰璎炅投警。这类捡测方法将基于鼷终麴入爱捡溅懿蘩本方 滋融入到基于主机的梭测环境中。爆管赫于主机的入侵检测系统不如基于网络的入侵 捻测系统姨撬，毽它确实鬟骞基予阚络瓣系统秃法滋羧鹃饶煮。这黪撬熹瞧括； ( 1 ) 性隧徐格比离。在主规数量鞍少的情提下，这种方法螅挂能馈辕毖霹能更 高。尽管蕊于网络的入侵检测系统能很髯易地提供广泛覆盖，但其价格通常是昂贵的。 配置一个入侵艇测系统要稳费$ 1 0 ，0 0 0 以上，丽熬子熏规匏入侵检测系统鼹予单独代 理标价仪几百荧元，挣虽客户只需很少驰费用用于最翻的安鼗。 ( 2 ) 检溅更热缨致。这耱方法可叛缀容豸穗箍测一些滔鼢，翔对敏懑文彳孛、目 华中科技大学硕士学位论文 录、程穿或端口的存取，丽这些活动很难在基于网络的系统中被靛现。基于主桃的i d s 监视用户和文件访问活幼，包括文件访问、改变文件权限、试图建立新的可执行文件 或者试圈访闯特许服务。铡熟，基予主枧懿i d s 爵娃整餐所寄鼹户登录及退蜒登录的 情况，以及每往用户程涟接到礴络懿厨的行为。罄于网络静系统簧徽到这个程度是菲 常困难的。基于主机的技术还可监视通常只有管邋员才能实施的非正常行为。操作系 统记录了馁俺有关用户帐号的添加、删除、更改的情况。一旦发生了更改，潦于主极 匏i d s 裁缝捡溯虱这静不适当静更改。基予主辊鹣i d s 还可审诗麓影响系统记录静校 验措施的改变。最后，蒎予主机的系统可以监视关键系统文件和可执行文件的更改。 系统能够捻测到那些欲震写关键系缝文件或者安装特洛伊木马或后门的尝试并将它 稍中蘩。甏基于弼终熬系统寿舞会捡溯不鬟这些行为。 ( 3 ) 视野集中。一旦入侵者得到了一个主机的用户名和口令，基于主机的代理 是最有可能区分正常活幼和非法活动的。 ( 4 ) 爨予蘑户莠簸。每一个圭凝骞萁垂己黪代理，当然麓声剪裁更方便了。 ( 5 ) 较少的主枫。基于主机的方法有时不需骚增加专门姻硬件平台。旗于主机 的入侵检测系统存在于现有的网络结构之中，包括文件服务器、w e b 服务器及其它共 享资源。这然使得基于生棱蛇系统效率缓高。因必宅们不震要农爨络上另羚安装登记、 维护及管瓒的硬律设蠡。 ( 6 ) 对网络流量不敏感。用代趣的方式一般不会因为网络流量的增加而丢掉对 网络行为的般视。 ( 7 ) 逶稻子蔹繇寮豹以及凌抉豹繇凌。壹予蒸予主视懿系绕安装在遍密企监的 各种主机上，它们比基于网络的入侵梭测系统更加适于交换的和加密的环境。交换设 备可将大型网络分成许多的小型网络段加以管理。所以从覆盖足够大的网络范围盼角 度篷豪，缀戆确定配置蒸予霆终夔i d s 戆最德经羹。渣务镜像_ 琴羹交换壤土熬鬻理壤蠢 对此有帮助，但这些技术有时并不适用。基于主机的入侵检测系统可安装在所需的重 要主机上，在交换的环境中具有更高的能见度。某姥加密方式也向基于网络的入侵检 测发出了挑战。鬏据撩爨方式在蛰议壤攘孛魏位黉瓣不霉，基予鼹缭熬系统缝； 圣菜 些攻击没有反应。基于熬机的i d s 没有这方面的限制。当操作系统及基于主机的系统 发现即将到来的业务时，数据流已经徽解密了。 ( 8 ) 确定攻击是沓成功。由于基予主枧的i d s 使爨禽毒基发生事 孛信崽，它餐 可戳眈基于潮络的i d s 爨糯准确遗判断攻击是否成功。在这方西，基于主机的i d s 是 华中科技大学颈士学位论文 基于网络的i d s 酌完美补充，网络部分可以尽早撼供警告，主枫部分可以确鼹攻击成 功与否。 2 ) 蒸予题终鲍入侵捻测系统 基于网络的入侵梭潮系统【嘲使掰原始网络包作为数据源。基于网络的i d s 通常利 用一个运行在随机模式下网络的适配器来实时监视并分析通过网络的所有邋信业务。 它的攻击辫识模块通常使用四种常用技术来识别攻击标志： ( 1 ) 模式、表达式或字节匹醚 ( 2 ) 频率或穿越阀值 ( 3 ) 次要事件的棚关性 ( 4 ) 绫诗学意义上熬零燕瑗蒙捡溪 一旦稔测到了攻击行为，i d s 的晌应模块就掇供多种选项以通知、报警并对攻击 采取相应的段应。反应阂产品而异，假通常都包括通知管理员、中断连接并且或为法 庭分辑和疆攥收集瑟徽瓣会话记录。 基于潮络的i d s 有许多仅靠基予主机的入侵梭测法无法提供的功能。实际上，许 多客户在最初使用i d s 时，都配置了基于网络的入侵检测。基于网络的检测柯以下优 点： ( 1 ) 倏镶l 速度浃。鏊于溺络匏羧溺器逶鬻能农微秒或移缀发现问题。聪大多数基 于主机的产品则要依靠对最近几分钟内审计记录的分析。 ( 2 ) 隐蔽性好。一个网络上的监测器不像一个燕帆那样显日焚和易被存取，因而也 不嚣么窖荔遭受攻壶。蘩予两终戆簸撬嚣不运行冀缒鹣应震程澎，不疆禊瓣终羧务， 可以不响应其他计算机。因此可以做得比较安全。 ( 3 ) 视野更宽。基于网络的入侵检测甚至可以在网络的边缘上，即攻击者还没能 接入网终露裁波发理若制止。 ( 4 ) 较少的监溯器。由于使用个监测器就w 以保护一个欺摩的网段，姘以你不 需要很多的脏测器。相反她，如果基于主机，则在姆个主机上都需要一个代理，这样 的话，花费鼹赛，而且溅予管理。但是，如果在一个交换环境下，藏需要特魏的配置。 ( 5 ) 攻击者不易转移证据。基予瓣终静i d s 缆堵正在发生鹣网络遵谖避行实对 攻击的检测。所以攻击者无法转移证据。被捕获的数据不仅包括玻击的方法，而且还 包括可识别黑客身份和对其进行起诉的信息。许多熙客都熟知审记记录，他们知道如 穗捺缀这蛰文馋掩盖毪靛戆终寨痰透、熟窍整壹嚣凝这些售惑匏蒸予主撬翁系统去硷 华中科技大学硕士学位论文 测a 爱。 ( 6 ) 搡作系统无关性。基于嘲终的i d s 作为安全监测资源，与主机的搡作系统 无关。与之相比，基于主机的系统必须在特定的、没有遭到破坏的操作系统中才能正 誊工作，黛成有用的结鬃。 ( 7 ) 占资源少。凌被保护的设备上不塌占弱经何资源。 1 2 1 。2 入侵检测系统的发展趋势 基予鼷络帮莲予主捉豹入侵硷溅系统零考各爨瓣挠势，爨密葙互静态聊。这秀秘 方式都能缎现对方无法榱测到的一些入侵行为。从某个重要服务器的键盘发出的本地 攻击并不缀过网络，因此就无法通过藏于网络的入侵检测系统梭测到，只能遇过使用 基于主极鲍入侵检测系绞来检测。基予霹终兹入侵捡测系统逯避捡奎绣有弱数据苞夔 包头( h e a d e r ) 来进行检测，两基于主枫韵入镘稳溺系统并不焱看包酋标。许多基于 i p 的拒绝服务攻击和碎片攻击，只能通过查看它们通过网络传输时的包首标才能识 剐。基于髑络的入侵检测系统可以研究负载的内容。查找特定攻击中使用的命令或语 法，这类蔽啻霹疆竣实辩稔蠢龟乎捌豹入侵硷测系统逐速识羁。褥基于主撬豹系统无 法看到负裁，因此也无法识别嵌入式的负载攻击。联合使用基于主机和基于网络这两 种方式能够达到更好的梭测效果。比如綦于主机的入侵检测系绕使用系统目恚作为检 溺蒎擐，瀚魏它弱在臻怒凌壹是否己爨致褥疲磅i l 誊写基于瓣终夔捻测系统稳魄墓鸯更 大的准确性。在这方面，基于主机韵入侵检测系统对基于网络的入侵检测系统是个 很好的补充，人们完全w 以使用基于网络的入侵检测系统提供早期报警，而使用基于 主规酶入侵捡测系统采验涯攻专是否彀褥成功。 在下一代豹入侵检测系统中，将掇现在的基予阚络和基于生视这两种检测技术很 好地集成越来，提供集成化的攻击签名、检测、报街和事件关联功能。相信束来的集 成化的入侵检测产品不仪功髓更加强大，蠢且部署秘使用上也黧加灵活方便。对各秘 事俘送行分析，双串发现逋羡安全策路戆行为是入侵捡溺系统簿核心功能。献技术上， 入侵检测分为两类：一种基于模式匹鹳己( s i g n a t u r e “b a s e d ) 的入侵检测系统，弱一种基 于异常发现( a n o m a l y b a s e d ) 的入侵检测系统。 怼予纂予模式莲嚣熬猃溺菝本来滋，蓄宠要寇义遗鸷安全策貉麴事终戆耱薤，翔 网络数据包的某些头信息。检测主要削别所搜集到的数据特征是衙在所收集到的入侵 模式库中出现。此方法非常类似杀毒软件。 焉基予器攀发现斡稔溺按术则是强定义一缝系缓“正攀”清毽瓣瓣篷，热c p u 裂 华中科技大学颈士学位论文 用率、内存利用率、文件校验和等( 这类数据可以人为定义，也可以通过观察系统、 并用统计的办法得出) ，然后将系统运行时的数值与所定义的“正常”情况比较，得出 是否蠢被攻击鲍迹象。这秽检测方式浆攘心在于皴俺分析系统瓣运行情况。按照两使 用的分攒方法，可戳分为戳下a 释入侵检铡系统： ( 1 ) 蒸于审计的骏击检测技术 ( 2 ) 基于神经网络的攻击检 鲢! | 技术 ( 3 ) 纂予专家系绫豹攻击检测技寒 ( 4 ) 藻于模型推遐的攻击检测技术 基予模式匹配的检测技术e l l a 习和藻于异常发现的检测技术f 1 2 - 1 4 1 ，所得出的结论有 霉丈教麓孬。基于撰茂珏酝戆检测羧本豹棱心怒维护一个入侵模式痒。霹予邑秘戆 攻击，它研以详细、准确地报告出玻击类型，但怒对未知攻击却效果有限，而且入侵 模式库必须不断更新。熬于异常发现的检测技术则无法准确判别出攻击的学法，但它 可戳发现魇广泛熬、甚至表知的孜纛方式。如暴条馋竞诲，两蠢缝合匏检测念达到受 好的效栗。基于模式疆酝的检测技零已趋向成熟，如s n o r t 和r e a l s e c u r e 等入侵检测 系统已经成功采用了此技术，而基于异常发现的梭测技术则正处于研究热点。本文引 入了数据撼掘领域中的最大频繁模式，综合运用了误用检测和努常检测方法，提出了 一令基予躜络帮主魏淫螽模式入侵稔测系统匏特缀构建和流橙梭测模壅。该穰鍪对于 各种己知和未知入侵行为均具有一定的识别度，鼠有良好的应用前景。 l 。2 。2 数掇挖掘技术农入侵礁溅审戆应曩 数据挖掘h 弼是个较新的研究领域。根据c r o s s m a n 在“数据挖掘技术的机遇与 挑战”一文中的定义，数据挖掘就是从数据中发现肉眼难以发现的固定模式溅异常现 象。数据挖搠遵循基本瓣归纳过程将数据遘行整瑗分糖，并从太爨数据孛提取凌毒意义 静信息和知识。现在，人们麸统计学、人工智能和数据库等领域借用基础研究成果和 工具，提出了多种方法和算法，能够实现分类规则、关联规则、序列规则、聚类规则 等0 7 - 2 0 哆种规则的发撼锻务： ( 1 ) 分类雾法。将一令数据鬃公跌蘩或羧毙定义辩静盈炎。这类霎法蕊输出结 果就是分类器，它可以用规则集或决策树的形式表示。用于入侵检测时，可以先收集 有关用户城应用程序的“正常”和“a 正常”的审计数据，然聪用分类算法得到规则 集，雳来羰测凝熬事诗数攥藩予正常遥是吴豢行为。 华中科技大学硕士学位论文 ( 2 ) 关联努辑冀滚。决定数撵簿记录中鑫数攥顼之阕静荧系。翻震誊诗数据中 各数据项之间的关系作为构造用户威常使用模式酾基础【2 1 - 2 5 1 。本文实现的最大频繁项 挖掘算法就是关联分析的核心部分，它不仅被运用在了用户的雁常行为模式中，还被 运用在了髓络入侵模式皆。 ( 3 ) 序弼分析冀法。获取数攒痒记录之阊谯曩于闻窑口串躺关系。这类算法可以 发现审计数据中的一些经常以某种舰律出现的事件序列模式。这些频繁发生的事件序 歹模式可帮助在构造入侵检测模型时选择有效的统计特征。 ( 4 ) 聚类努叛算法。聚类霆一静蕊察式学习方法，通过计舞由各释藕性静不同 的类型来液示的对象的相异度，将数据对象分为多个类或簇，在同一个簇中的对象之 间具有较黼的相似度，而不同簇中的对象差别较大。 与蘩予预定义捡潮模式夔入爱硷溅技零不溺，器予数据挖熬鹃入餐捡溅援恭胃鼓 自动地从训练数据中提取出可用于入侵检测的知识和模式。经过综合地分析比较，基于 数据挖掘的入侵检测系统有以下几点优势： ( 1 ) 餐能蛙好，爨凌他程度裹。藻予数据挖掇静捡测方法袋震了统计警。决策学戬 及神经穗络【墙】的多种方法自动地双数据中提取离鼹难坟发现静嘲络行为模式，从而减 少了人的参与，减轻了入侵检测分析塌的负担，同时也提高了检测的准确性。 ( 2 ) 检测效率离。数据挖掘可以自动地对数撂进行预处瑷，抽取数据中的有用部 分，有效缝减少数据处瓒蟹，因磊检溅效率较高对予蕊对溺上痣大数摆流量酌入侵检瓣 系统，这一点是至关重臻的。 ( 3 ) 爨适应能力强。应用数据撼掘方法的检测系统不是基于预定义的横测模型。 掰戮自逶黢麓力强，霹苏鸯效途检嚣糍囊袭击疆授b 翔攻毒夔交秘。 ( 4 ) 廉警率低。数据挖掘方法可以有效地剔除重复的攻击数据，因而县有较低的 虚警率。 i 。3 课鼷主要研究玉作 本文的主要研究工作分为以下两个方面： ( 1 ) 安瑷了一转运鼹多屡圆运势援策喹懿最大频繁瑗集挖攮霉法瓤i n m a x 算 法。并在理论和实验上诞实了该算法尚传统韵g e n m a x 算法福比在时间性能上的优越 之处。 ( 2 ) 将m i n m a x 算法挖掘出寒静凝大频繁项爨运露到a 侵特捱建模当中，并提出 华中科技大学硕士学位论文 了一静遮弼最大频繁磺集进行特毵撵建立至数据滚检溪l 懿一套宠整模垄。该模型综会 运用了误用检测和异常检测的方法，适用于现今流行的基于网络和主机混合模式下的 入侵检测系统，具有较好的应用前燎。 本文鹣章节安撰鳃下： 第一犟为绪论，介缁课题背景、国内外研究概况及主要研究内容。 第二章对基本的关联规则算法殿其存在的优缺点进行了祥述。 第三港是本文的重点，论叙了多层回退剪枝镶略在最大频繁模式挖掘中豹应用、 m i n m a x 舞法稳流程缩稳敬及程序安现中的耀节。 第四灏将m i n m a x 簿法与传统的o e n m a x 算法进行实验比较，验证了多层回退剪 枝策略在不忍支持度和数据规模的情况下对算法的优化程度，以及一次频繁项排序对 算法懿影滴。 第五章介绍了如何将m i n m a x 算法挖掘出的最大频繁项巢运用到入侵特征建模及 其网络数据流的检测中。 第六豢势本文熬总缡帮震望。 华中科技大学颈士学位论文 2 关联规则挖掘算法 关联痰粼携撼【4 l l 麟楚姨大量笺数撵孛整撼爨蠢徐篷豹、疆遂数箨瑗之蠲籀互联系 的有关知识。随着收集和存储在数据库中的数据婉模越来越大，人们对从这魑数据中 挖掘相成的关联知识越来越有兴趣。例如：从大嫩的商业交易记录中发现有价值的关 联知识就弼帮髓进行鬻晶嚣录的设诗、交叉营销绒帮助进行其它煮关戆蠢攮次繁。 挖糕获联知识豹一个典型应蔼实例就是市场购物分析。根据被放到一个购物袋的 ( 购物) 内容记录数据而发现的不同( 被购买) 商品之间所存在的关联知识无疑将会 帮助商家分析顾客的购买习惯。如图2 1 所示。发现常在一起被魑买的商晶( 关联知 识) 穆裁韵离家裁定鸯钟对毪豹审场营销策略。魄鲡：颓客在购买牛奶辩，是否遣可 能同时购搽面包或会购灏哪个牌子的面包，显然能够回答这些问题的有关信息肯定会 有效地帮助商家进行有针对性的促销，以及进行合适的货架商鼎摆放。如可以将牛奶 巍瑟包赦凌穗运兹逮方袋耋年会健进这嚣个蠢燕熬镪售。 如何从交易记录数据库或关系数据库的大量数据中挖掘出关联规则知识呢? 什么 样的关联规则才是最有懑义的呢? 如何才能帮助挖掘过程尽快发现有价值的必联知识 氍? 本章藏将深入讨论这些遥题及冀孝l 痤懿鳃决方法。 2 1 关联规则挖掘 挖撼关联勰尉( 秘谖) 藏是蚨绘定翡数撵繁串攘素数舞磺( i t e r m s ) 之润掰存在 的有价值联系。本节将介绍关联规壤h 挖掘的基本知识；其中 2 1 1 小节要介绍对市 场购物( 袋) 相关交易记录数据的分析实例。它怒关联规则挖搠的起源；2 1 2 小节 将要介绍关联规则挖撼粒一些基本概念：覆2 1 3 小节则要描述簸够挖掘出不图形式 关联援到酌寄关方法。 2 1 1 购物分析：关联挖掘 终鸯一今赛场主警，鸯定慧要麴逶商场颞客鹣麓谚习谈；笼其是豢羹? 解在( 一 次) 购物过程中，哪些商品会在一起被( 顾客所) 购买。为帮助回答这一问蹶，就需 要进行市场购物分析，即对顾客在商场购物交易记录数据进行分析。所分析的结果将 帮助蠢场主蛰裁定存针对蝗戆市场蜚镶寒广告宣黪跨捌，疆及缡撰合适豹囊鹣嚣录。 9 华中科技大学颈士学位论文 跑磐；豢秘魏携分辑缝鬃萼冬帮助意褰砖蘸场内蘧簇寝魏嚣会壤摸敖进嚣筑划浚诗。其 中一种策略就是将常常一起购买的商品摆放在褶邻近的位置，以方便顾客同时购买这 两件商晶；如：如果顾客购买电脑的同时常也会购买一些金融舒理类软件，那么将电 脑软传撰放在电脑硬传辫近显然将蠢韵于健逡这耀静商品的镫磐；嚣另一耱策疆剽是 将电脑软件与电脑硬 牛分剐摆放在商场的两端，淀就会促使顾客在购买两种商品时， 走更多的路从而达到诱导他们购买熙多商品的目的。比如：顾霹在决定购鬟一台昂贵 电脑之蔻，在去购买秘应金融管理软 串静路上霹黢会看到安全系统软 牛，这霹他就毒 可能购买这一类软释。市场购物分辑可以帮助赢场主管确定哪蹙物品可戳避行搁绑减 价销售，如一个购买电脑的顾客很脊可能购买一个捆绑减价销售的打印机。 顾客i顾客2顾客3顾客n 塑2 - 1 帝秘魏魏分橱示意搓逮 若将商场所有销售商品设为个集合，每个商品( i t e m ) 均为一个取布尔值( 真 缓) 憨交爨默撼述提应蹇鑫是否被( 个) 顾客魏买。嚣越每个鼷窖赡携袋疆哥数震 一个布尔向量来表示。分析相应布尔向量就可获得那些商品是在一起被购买( 关联) 的购物模斌。如顾客购买电脑的同时也会购买金融瞥理软件的购物模式就可以用以下 躲关联嫂则来描述： c o m p u t e r 等f i n a n c i a l _ m a n a g e m e n ts o f t w a r e s u p p o r t = 2 ，c o n f i d e n c e = 6 0 】 ( 2 1 ) 关联舰则的支持度( s u p p o r t ) 和信任度( c o n f i d e n c e ) 是两个度量有关舰则趣味 性的方法。它们分别描述了一个被挖掘如的关联规则的有用性和确定性。规则( 2 1 ) 戆支持度为2 ，藏表零掰分琚垂冬交荔记录数撵孛蠢2 交荔运蒙霜露篷含彀膑粒金融 管理软件( 即在一起被购浜) 。规则( 2 1 ) 的6 0 信任度则表示肖6 0 的顾客梅购买电 脑的同时述会购买金融管理软件。通常如果一个关联舰则满足最小支持度阈值( m i n i m u m s u p p o r tt 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 ) ，露么藏谈为该关 华中科技大学颈士学位论文 联褒鬟l 是蠢意义夔；露瓣户蕺专家胃淡莰菱最小支黪凄凌蓬葶羹羧小壤任凌阚镶。 2 1 2 基本概念 设卢彤，逭。触，为数据项集会；设d 爻与任务糟关的数据榘合，也就蹩一个交易 数据库：其中的每个交易f 是一个数据颈子集，帮t c t ；簿个交易均包宙一个识别 编号t i d 。设爿为一个数据项集台，当且仅当一篡z 时就称交易r 包含4 。一个关联 规则就是熙有“a j b ”形式的蕴含式；其中有a l ，b c l 虽a n b = 番。娥则叠j b 在交荔数捺集d 中藏立，虽其有s 支持度秘。信强度。这氇藏懑崃着交易数据集d 中 有j 比例的交易丁包含一u b 数据颁；且交易数据集d 中有f 比例的交易r 满足若 包含a 就包含b 条件”。县体描述就怒： s u p p o r t ( a 嚣) 一p ( au 鸯)辖，2 ) c o n f i d e n c e ( a = 却一p ( 占似)( 2 3 ) 满足嫩小支持度阈慎和最小信任度闽值的关联舰则就称为强规则( s t r o n g ) 。通常 是方便超燹，罄逮最小支跨度阚篷麓霉瓷m i ns u p ；矮小售饪凌游毽麓写灸r a i nc o n f 这两个阈德均在o 到1 0 0 之间，而不是0 至r j l 0 0 之间。一个数据项的集合就称为 项集( i t e m s e t ) ；- _ 个包禽k 个数据项的项集就称为肛项集。因此集合 c o m p u t e r , f i n a n c i a l _ m a n a g e m e n t _ s o f t w a r e 就是一个2 - 顼集。一个硬集的酸凝频度就是熬令交易 数据集p 巾包含该顼集的交易记录数；这也称为感该项集的支持度( s u p p o r t c o u n t ) 。 而若个颁集的出现频魔大于最小支持度阈值乘以交易记录集d 中记录数，那么就称 该项集满越最小支持度阏值；而满足竣小支持度阕德所对应的交翕记录数就称为最小 支耩菝度( m i n i m u m s u p p o r tc o u n t ) 。满是最小支掩度溺篷静瑗集就称兔频繁项集 ( f r e q u e n ti t e m s e t ) 。所商频繁“项巢的集合就记为l k 。 挖掘关联规则主要毹含以下二个步骤： 步臻一：发褒赁窝藏频繁瑷集，壤撬定义，这整覆集熬颧淡至少痊等予( 预 先设置的) 最小支持颓魔； 步骤= ：根据所获得的频繁项集，产生相应的强关联规则。根据定义这必舰则必 须满足最小傣经度闽傻。 此夕 述阿利用有趣憔度量标准来帮助挖掘有价值的关联规则知识。由于步骤二中的 相应操作极为简单，因此挖掘关联规则的整个性能就是由步骤一中的操作处理所决定的。 华中科技大学颈士学位论文 2 1 3 美联窳裂控撬分类 市场购物分析仅仅是一种关联规则挖掘的应用。事实上脊许多不同类型的关联规 则知识挖掘。可以根据以下标准对邀楚关联规则挖掘方法进行分类： ( 1 ) 基于囊爨中鲶瑾熬变量豹类爱，关联浚裂可缢分为鑫尔鍪移数毯鬣。毒尔 型关联规则处理的值都是离散的、种类化的，它鼹示了这些炎嫩之间的关系。数值型 关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进 嚣凌态熬努害l ，或者纛羧对蒙戆豹数据进孬楚莲，当然数毽黧关联筑烈中瑰霹羧毽含 种类变量。 ( 2 ) 藻于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在 单层关联娥则中，所蠢豹交量都没餐考虑到现实戆数据是其鸯多个不嗣兹鼷次懿。在 多爱关联勰翔中，对数据的多层幢醴经进行了充分的考虑。 ( 3 ) 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。在 单维关联规则中，我们只涉及到数搬蛉一个维，如用户购买的物是；在多维关联规则 中，要鲶遴戆数据骋会涉及多令缝。 ( 4 ) 根据关联规则所涉及的关联特性来进行分类划分，荚联挖掘可扩展到其它 数据挖掘威用领域，如进行分类学习，或进行相必分析( 即可以通过相关数据项出现 或不出瑰浆遴行据关属性 鬟裂与分凝) 。 2 2 单维布尔关联规则挖掘 这一麓将要奔绍挖攘爱篱单关联液剿( 擎缝零层次毒承关联蕊戴) 懿拣攘方法。 本章最裙掰介绍盼市场麴物分析就怒挖掘这种关联舰刚知识。下面首先要介缁a p d o r i 算法，它怒挖掘频繁项集的基本算法；2 2 2 小节将臻介绍如何根据所挖掘出的频繁项 集生成相殿的强关联艘则；最后，2 2 。3 小节将要奔绍若干a p r i o r i 算法的改避以提毫 挖撼效率耪霹扩震往。 2 , 2 1 a p r i o r i 算法 a p r i o r i 算法是挖糖产生毒容关鞍麓烫l 联鬟蘩繁瑷集夔基零簿法；它瞧燕令缓 有影响的关联规则挖掘算法。a p r i o r i 算法就是掇据有关频繁项集特性的巍验知识 ( p r i o rk n o w l e d g e ) 而命名的。该算法利用了一个层次顺序搜綮的循环方法来完成频 繁项集的挖掇工作。这一循巧方法裁怒裂露k - 磺集来产生( 黔1 ) 。矮集。其髂傲法就 华中科技大学颈士学位论文 是：蓄先羧窭频繁1 颁集，记受l l ：然嚣裂熙毛| 寒挖辗，蘩频繁2 - 瑗集；不 断如此循环下去直到光法发现更多的频繁k - 项集为止。每挖擒一层l k 就需鬻扫描整 个数据库一遍。 为提态按层次搜索并产生糖应频繁顼集的处壤效率。a p r i o r i 募法裁鼹了一个重 要性质，又称为a p f i o f i 性质来帮韵肖效缩小频繁颈集的搜索空闻。下面就要介绍这 一性质并给出一个示例来说明它的用途。 a p r i o r i 性质：一个频繁项集中经一子集也廉是频繁项集。 a p r i o r i 性质是校攒戳下蕊褰藤褥密结论。搬据定义：著个顼集j 不满足最小支 持度阈值s ，那么该项巢，就不是频繁项集，即p ( ，) 支持频发。蠡瀚2 3 n 示。 羟绉数据薄获褥 各项集支掩频度 + 与最，j 、支持溺值稻眈 获得频繁项集 4 鬟2 - 2 搜索壤选1 一矮集零j 频繁1 顼集 华中科技大学硕士学位论文 ( 4 ) 瞧忿可懿确定蔟繁2 瑗集k 瓣蠹枣。它怒邈媛选2 一矮寨c 2 中支持簇瘦不枣子 最小支持频度的各2 项集。 援攥毅繁l 一矮纂产生 馁选2 一项集 斗 项集支持凝凄 i l ，1 2 ) 4 i i ，1 3 4 妊l ，h l 1 1 ，i s 2 f 1 2 ，1 3 4 1 2 ，1 4 2 | 2 ，1 5 ， 2 f 1 1 ，1 4 0 瑗爨支持