（计算数学专业论文）聚类算法在入侵检测中的应用.pdf

摘要 摘要 随着计算机技术和网络技术的不断发展，i n t c r n e t 在为我们带来许多机遇和丰 富的网络资源的同时，也使得计算机安全问题更加复杂和突出，这直接关系到个 人隐私、商业利益乃至国家机密。因此，如何有效而迅速地发现并阻止各种非法 入侵行为，成为当今网络安全有待解决的重要问题。虽然现在已有很多传统安全 产品，如认证、访问控制、加密、防火墙等，但是这些安全系统存在不完备性， 而入侵检测技术能够弥补它们的不足。入侵检测能够找到系统漏洞，并在非法入 侵者攻击计算机系统时，实时地捕获这些入侵攻击行为；因此，入侵检测技术是 一种新的安全保障技术，是计算机安全体系中的非常重要组成部分，已成为当前 计算机安全技术研究的重点。 现在已有的入侵检测系统的智能化水平低，对入侵攻击行为的实时检测能力 不强，检测的准确率低，误报率高；而数据聚类方法应用到入侵检测中，能够使 得入侵检测系统具有自学习、自组织的能力，提高系统处理海量数据的能力，从 而提取数据中有潜在价值的知识和规则，提高检测能力；数据聚类方法是一种典 型的无监督学习技术，可以在未标记数据集上直接建立入侵检测模型或者发现异 常数据；本文中提出的a i n e t 增量聚类算法结合了人工免疫原理中的克隆选择、亲 和力成熟以及网络抑制等免疫机制，有效地提高自学习和智能化能力；把增量聚 类和子簇合并的思想应用到该算法中，有效地提高聚类效率；数据聚类算法在入 侵检测领域有着广泛的应用前景，这是一个非常有价值的研究方向。 本文的课题来源于四川省科技厅应用基础研究项目“基于安全免疫服务网络 的入侵检测技术研究 ( 2 0 0 8 0 0 5 8 ) 。本文的主要研究工作： 1 介绍了几种传统的数据挖掘聚类算法，然后重点研究基于免疫原理的聚类 算法，并对算法优缺点进行了分析，在此基础上提出a i n e t 增量聚类算法。 2 在分析现有入侵检测系统模型的基础上，把a i n e t 增量聚类算法应用到入侵 检测中。该模型工作过程分为数据预处理、聚类分析、标识类和实时检测四个阶 段；首先对数据的所有属性值进行标准化，再利用该聚类算法来对网络数据进行 分类，区分哪些网络数据是正常的，哪些网络数据是异常的；然后把包含异常网 络数据的簇标记为异常簇，而将包含正常网络数据的簇标记为正常簇。 3 实时检测数据。根据检测算法进行增量聚类，在不断完善聚类结果的同时 摘要 有效而快速地检测出入侵攻击行为。 4 先使用二维数据集来证明，增量聚类算法的聚类结果与重新聚类的聚类结 果一致，以及a i n e t 增量聚类算法能有效地提高聚类效率；再使用k d d c u p9 9 数据 集对基于a i n e t 增量聚类算法和增量式k - m e a n s 聚类算法的入侵检测模型进行实验， 实验结果表明，基于a i n e t 增量聚类算法的入侵检测模型能有效地提高检测率和降 低误报率，而且检测速度也有所提高。 关键词：聚类算法，入侵检测，人工免疫网络，增量聚类 a b s t r a c t a bs t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e ra n dn e t w o r kt e c h n o l o g i e s ，i n t e r n e tb r i n g su s o p p o r t u n i t i e sa n dm a n yn e t w o r kr e s o u r c e s ，t h u sm a k i n gc o m p u t e rs e c u r i t yi n v o l v e di n p e r s o n a lp r i v a c y , b u s i n e s sb e n e f i t sa n dn a t i o n a ls e c r e tm o r ea n dm o r ec o m p l i c a t e da n d r e m a r k a b l e s oh o wt oe f f e c t i v e l ya n dq u i c k l yd e t e c ta n dp r e v e n ta c t so fi l l e g a li n v a s i o n b e c o m e sa l li m p o r t a n tp r o b l e mt ob es o l v e d t h o u g ht h e r ea r em a n yt r a d i t i o n a ls e c u r i t y p r o d u c t sn o w ，l i k ea u t h o r i z a t i o n ，a c c e s sc o n t r o la u d i t ，e n c r y p t i o na n df i r e w a l le t e ， h o w e v e r ，t h e s es e c u r i t ys y s t e m sa r ei n c o m p l e t e ，a n di 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 l m a k eu pf o r 也e i rs h o r t c o m i n g s ，t h ei n t r u s i o nd e t e c t i o nt e c h n o l o g yi sa b l et of i n d l o o p h o l e s ，a n di tc a p t u r e st h e mr e a l - t i m e l yw h e nt h ei l l e g a li n t r u d e r sa t t a c ks y s t e m s s o 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 yi san e ws e c u r i t yt e c h n o l o g y , i st h em a i nc o m p o n e n to f t h ec o m p u t e rs e c u r i t ya r c h i t e c t u r e ，a n dh a sb e c o m ea l li m p o r t a n tp a r to ft h ec o m p u t e r s e c u r i t yr e s e a r c h n o wi n t r u s i o nd e t e c t i o ns y s t e m sa r et h el o wl e v e lo fi n t e l l i g e n c e ，h a v et h ei n v a s i o n c a p a c i t yo ft h ep o o rr e a l - t i m ed e t e c t i o n ，h a v et h el o wr a t eo fd e t e c t i o na c c u r a c ya n d l l i g hf a l s ea l a r mr a t e ；d a t ac l u s t e r i n gt e c h n o l o g yi sa p p l i e dt oi n t r u s i o nd e t e c t i o n ，w h i c h e n a b l e st h ei n t r u s i o nd e t e c t i o ns y s t e m st oh a v et h e a b i l i t y o f s e l f - s t u d y a n d s e l f - o r g a n i z a t i o n ，a n di m p r o v et h es y s t e m sa b i l i t yt oh a n d l em a s s i v ed a t a , i no r d e rt o e x t r a c td a t ai nt h ep o t e n t i a lv a l u eo fk n o w l e d g ea n dr u l e s ，i m p r o v et h ed e t e c t i o n c a p a b i l i t y d a t ac l u s t e r i n gi sat y p i c a lu n s u p e r v i s e dl e a r n i n gt e c h n i q u et h a tc a nb u i l d i n t r u s i o nd e t e c t i o nm o d e la n dd e t e c ta n o m a l yr e c o r d si nu n l a b e l e dd a t a s e t i nt h i sp a p e r t h ei n c r e m e n t a lc l u s t e r i n ga l g o r i t h mb a s e do na i n e ti sr a i s e d ，w h i c hc o m b i n e st h e a r t i f i c i a li m m u n et h e o r y , s u c ha sc l o n a ls e l e c t i o n ，a f f i n i 锣m a t u r a t i o n ，a sw e l l 弱 n e t w o r k ss u p p r e s s i o n t h a ti n c r e a s e st h ec a p a c i t yo fs e l f - l e a r n i n ga n di n t e l l i g e n t e f f e c t i v e l y t h ei n c r e m e n t a lc l u s t e r i n ga n dt h ei d e ao fm e r g i n gs u b c l u s t e ri sa p p l i e dt o t h i sa l g o r i t h m ，w h i c he f f e c t i v e l yi m p r o v et h ee f f i c i e n c yo fc l u s t e r i n g t h e r e f o r ed a t a c l u s t e r i n gh a sp r a c t i c a lm e a n i n gi n t h ef i e l do fi n t r u s i o nd e t e c t i o n ，a n di sav e r y v a l u a b l er e s e a r c h t h es u b j e c to ft h i sp a p e ri sf r o mt h eb a s i cr e s e a r c hp r o j e c ti nt h ea p p l i e ds c i e n c e i a b s t r a c t a n dt e c h n o l o g yd e p a r t m e n to fs i c h u a np r o v i n c 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 y r e s e a r c hb a s e do ns a f e t yo fi m m u n i z a t i o ns e r v i c e sn e t w o r k ”( 2 0 0 8 j y 0 0 5 8 ) t h em a i n r e s e a r c hw o r ko ft h i sp a p e r ： 1 a n a l y s ec l u s t e r i n gm e t h o d i nd a t am i n i n ga i m i n ga ti n t r u s i o nd e t e c t i o n , a n dp u t f o r w a r da ni n c r e m e n t a lc l u s t e r i n ga l g o r i t h mb a s e do na r t i f i c i a li m m u n en e t w o r k 2 b a s e do na n a l y s i so fe x i s t i n gi n t r u s i o nd e t e c t i o ns y s t e m s ，i n c r e m e n t a lc l u s t e r i n g a l g o r i t h mi sa p p l i e dt ot h ei n t r u s i o nd e t e c t i o ns y s t e m t h em o d e lp r o c e s si n c l u d e st h e p r e p r o c e s s i n go fj o bd a t a ，c l u s t e r i n g ，l a b e l i n gc l u s t e r sa n dr e a l t i m ed e t e c t i o n ；f i r s to f a l lt h ep r o p e r t yv a l u e so fd a t ai ss t a n d a r d i z e d ，t h ea p p r o p r i a t ec l u s t e r i n ga l g o r i t h mi s u s e dt oc l a s s i f yt h e s ec o n n e c t i o n sr e c o r d ，d i s t i n g u i s h i n gn o r m a lc o n n e c t i o nr e c o r d s f r o ma b n o r m a lc o n n e c t i o nr e c o r d s ；a n dr e c o r d st h a tc o n t a i nt h ea b n o r m a lc o n n e c t i o n s i sm a r k e da sa b n o r m a lc l u s t e r s ，w h i l er e c o r d st h a tc o n t a i nt h en o r m a lc o n n e c t i o n si s m a r k e da sn o r m a lc l u s t e r s 3 t h er e a l t i m ed e t e c t i o ni s e x e c u t e d ；t h ed e t e c t i o na l g o r i t h mi s b a s e do n i n c r e m e n t a lc l u s t e r i n g ，i td e t e c t su n k n o w ni n t r u s i o n se f f e c t i v e l yw h i l et h ec l u s t e r i n g r e s u l t sa r ei m p r o v e dc o n t i n u o u s l y 4 f i r s t l yt w o - d i m e n s i o n a ld a t a s e ti su s e dt op r o v et h a t ，t h er e s u l to fi n c r e m e n t a l c l u s t e r i n ga l g o r i t h mi s t h es a m ea st h er e s u l to ft h er e - c l u s t e r i n g t h ei n c r e m e n t a l c l u s t e r i n ga l g o r i t h mb a s e do na i n e ti se f f e c t i v ei nr a i s i n gt h ee f f i c i e n c yo fc l u s t e r i n g t o o t h e nt h ek d d c u p9 9d a t a s e ti su s e df o ri n c r e m e n t a lc l u s t e r i n ga l g o r i t h mb a s e do n a i n e ta n di n c r e m e n t a lc l u s t e r i n ga l g o r i t h mb a s e do nk m e a n st oc a r r yo u te x p e r i m e n t s s h o w ，t h ei n t r u s i o nd e t e c t i o nm o d e lb a s e do na i n e ti n c r e m e n t a lc l u s t e r i n ga l g o r i t h m c a ne f f e c t i v e l yi m p r o v et h ed e t e c t i o nr a t ea n df a l s ea l a r mr a t e a tt h es a m et i m e ，i tc a l l e f f e c t i v e l yi m p r o v et h ed e t e c t i o ns p e e d k e yw o r d s ：c l u s t e r i n ga l g o r i t h m ，i n t r u s i o nd e t e c t i o ns y s t e m ，a r t i f i c i a li m m u n en e t w o r k ， i n c r e m e n t a lc l u s t e r i n g i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：幽童聋 日期：三砂矿7 年岁月胆日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：癣导师签名：j 她 咽飙炒了钌刖堋 第一章绪论 1 1 研究背景和意义 第一章绪论 计算机和互联网的出现是人类发展史中非常重要的科学成果，它们的作用和 重要性是不言而喻的，我们现在的生活和学习都已经离不开它们。前者从很大程 度上提高了我们的思维能力以及计算能力，而互联网让我们学习和生活变得更加 方便。当计算机和互联网发展到一定时期，随之而产生很多安全性问题，比如病 毒、网络入侵、网络攻击等。最近几年，很多关于计算机和网络安全的技术被发 展起来，由此可见，网络安全和计算机安全成为目前计算机科学技术研究的热点 和难点，具有很高的研究价值和现实意义。 随着计算机和互联网发展，计算机入侵和攻击手段也正朝着多元化、智能化、 复杂化的方向发展。如果只是仅仅依赖加密技术、防火墙技术根本不能满足计算 机安全和网络安全的需要。主要原因有以下几点：第一，加密技术和防火墙技术 都是静态安全技术，无法主动地跟踪入侵攻击者；第二，防火墙技术不能阻止内 部用户发起的攻击；第三，防火墙技术一般无法提供实时检测的能力。因此，现 在研究重点已经由静态安全技术逐步向能主动跟踪、主动监控、扫描非安全行为 的动态安全技术，诸如说入侵检测等。 由于解决以上几个问题的难度很大，我们可以按照一些安全策略来建立相应 的安全系统，而且这个安全系统在现有资源下要比较容易实现；通过这个安全系 统，系统管理员和计算机安全人员能够尽快发觉入侵攻击行为，使得管理员可以 快速地找到一些行之有效的方法来阻止入侵攻击行为，同时修复系统软件和应用 软件的漏洞。继“防火墙”技术、“数据加密”技术等之后新的安全防范技术应 运而生；入侵检测就是其中一个很典型的防范技术；从本质上说，入侵检测 ( i n t r u s i o nd e t e c t i o n ) 是一种安全机制，也是一种主动的安全防范技术。它既能够动 态地监控计算机系统，又能预防、抵御入侵攻击行为；它能快速地识别计算机和 网络中的恶意攻击行为，并做出响应，及时地进行处理。入侵检测系统很大程度 上可以协助防火墙等传统安全技术解决当前的信息安全问题，而且能保证企业信 息化系统的安全建设。 电子科技大学硕士学位论文 1 2 现状及其研究方向 当前我们研究入侵检测技术，一般都是从机器学习、数据挖掘、人工智能等 很多领域着手。国内外也已经取得一些可喜的成果；为了解决“边界锐化的问 题【旧，j o h ne d i c k e r s o n 和h i r e ns h a h 等人利用模糊逻辑算法和遗传算法来优化模糊 集合隶属度来提高检测效率；并且对于网络数据等其他数据的多种属性，利用属 性均值聚类算法来生成各种检测规则，从而达到很好的入侵检测效果【3 j 。m i ny a o 和h a ij i n 等人【4 ，5 】利用粗糙集理论从各种属性中选出能够反映入侵攻击特征的关键 属性，从而提高检测率，同时利用多决策树方法从所有数据集中找到入侵攻击特 征，从全局着手来判断，降低误报率；为了获得更好的入侵特征，高艳等人1 6 j 利用 实时击键序列作为入侵特征，结合贝叶斯方法实现对主机的用户行为进行入侵检 测；o k a z a k i 等人f 7 ，8 】通过关联规则来挖掘大多数的网络行为记录，从而获得正常网 络行为的频繁模式，用来对异常网络行为进行区别，提高系统的检测性能和检测 准确度。为了解决互联网分布特别广、流量不均匀等问题，张敏等人提出基于移 动a g e n t 技术的分布式入侵检测框架，它们在主机上自动执行，完成入侵检测任务， 更加适用于广泛的互联网环境【9 , 1 0 。 在前期的入侵检测专家系统d e s ( i n t r u s i o nd e t e c t i o ne x p e r ts y s t e m ) t 1 1 】中，它们 利用参量化的统计分析方法，来提取用户或者系统的行为模式特征；但是想要利 用这种分析方法的必要条件是被分析的所有数据必须满足一种特定的分布。在早 期的入侵检测专家系统中，一般都是假设用户模式或者系统行为模式满足正态分 布或者高斯分布。若是这个假设条件不成立，将会使得整个检测系统产生许多的 错误报告。有人提出使用非参量化的统计分析技术聚类分析方法来克服上面 这个问题 i2 1 。与大量神经网络等用于异常检测系统的智能化方法相比较，聚类分 析方法能够从有噪声的、没有被标记的数据集中进行有效地分析和分类。 l e o n i dp o n r o y 等) , 1 3 】将聚类分析方法应用于无监督的异常检测系统。在国外 有一名著名的研究员提出【1 4 】：将聚类分析方法用于组建无监督的检测模型非常有 研究价值，而且聚类分析方法应用于无监督的异常检测系统代表了一个有发展前 途和实用价值的研究方向。与利用其他技术的入侵检测技术相比较，基于聚类分 析方法的入侵检测的技术难点着重在于怎样根据每个具体应用环境的需求，从关 于原始的先验知识中提取那些能够反映用户行为和系统行为的重要属性，然后利 2 第一章绪论 用恰当的聚类算法进行挖掘。在入侵检测领域中的网络数据有很多显著的特点： 网络数据是多元化，网络数据量特别大，网络数据维度高、网络数据的结构特征 非常复杂( 在第五章的k d dc u p 数据集中就是这样，既有连续型的、又有离散型的) 。 这就要求用于入侵检测的聚类算法时间复杂度要很低，算法伸缩性要特别好，有 很高的智能性，还能处理复杂结构的数据。因此，我们要特别清楚数据集中的数 据的特点和数据特征，从而选取能够胜任入侵检测的聚类算法，并进行相应的改 进；从长远来看，这是一项非常有实际意义的研究工作。 为了解决上面的问题，本文将把研究的重要内容放在基于免疫网络理论的无 监督聚类( c l u s t e r i n g ) 分析方法上。这种无监督的方法可以在没有标记的网络数据上 执行聚类算法，将特征相似的网络数据聚集到同一个聚类( 簇) 中，同时把不同 特征的网络数据聚集到不同的聚类，然后通过标记类算法给所有聚类加上标记， 标明它们是正常，还是异常；再采用a i n e t 增量聚类算法对网络中刚收集到的新数 据进行聚类分析。文中最后还对这种改进后的聚类算法进行了数据测试实验，实 验结果表明，将聚类算法、人工免疫原理和入侵攻击行为有机结合起来，对提高 入侵检测模型的效率( 检测率和误报率) 有很好的的研究价值和实用价值。 1 3 本论文组织结构及内容 本文主要的研究内容包括：首先分析了目前比较流行的各种数据聚类算法， 从中找到这些算法优缺点，便于以后开展研究工作；第二，结合免疫网络的基本 原理，对现有的聚类算法做出相应的改进，提出了适合于入侵检测系统的a i n e t 增 量聚类算法，并对该算法的性能进行测试验证，对算法复杂度进行分析；最后， 将改进之后的a i n e t 增量聚类算法应用于入侵检测系统，构建一个新的检测器原型； 利用测试集，对检测器原型进行测试验证，并对其漏报率、误报率等进行分析、 比较。 本论文组织结构： 第一章绪论。阐述了当前计算机和互联网安全的需求和背景知识，同时提出 本文的研究背景、研究意义；指出了当前能应用于入侵检测的各种算法的研究现 状，还有入侵检测的未来发展前景；引出了基于无监督的聚类算法的入侵检测技 术。 第二章数据聚类算法。首先描述了无监督聚类算法以及其研究现状和未来展 望；再主要介绍了聚类分析方法的基本知识在数学方面的表现方式，比如说聚类 电子科技大学硕士学位论文 的相异度；还研究了几种传统聚类算法和基于免疫原理的聚类算法的基本思想及 其优缺点；最后，粗略地阐述了聚类算法应用于入侵检测的要求和可行性。 第三章入侵检测。主要介绍了入侵检测的概念和功能、三种入侵检测方法的 基本原理；另外还讨论了入侵检测系统存在的不足、发展前景。 第四章免疫网络原理概述。主要介绍了生物免疫系统和人工免疫原理的基本 概念、原理，将二者进行比较；其次，介绍了免疫算法的概念和原理、二种典型 的免疫网络模型，最后阐述了免疫网络未来的发展前景。 第五章增量聚类算法在入侵检测中的应用。首先粗略地介绍了增量聚类的原 理和步骤；其次，结合免疫网络原理，提出了a i n c t 增量聚类算法；然后通过数据 测试实验来验证算法的有效性；最后，将该算法应用于入侵检测系统，构建一个 新的检测器原型；利用数据测试实验，对检测器原型进行测试验证，并对其漏报 率、误报率等进行分析、比较。 第六章总结及展望。总结全文，分析本文在对应用于入侵检测的聚类算法研 究中存在的不足之处，同时在今后研究工作进行改进。 4 第二章数据聚类算法 2 1 无监督聚类方法 第二章数据聚类算法 2 1 1 无监督聚类算法研究 现在很多聚类算法都是利用许多的被标记过的数据或正常数据来训练和学 习。我们对应用到误用检测和异常检测中的数据聚类算法进行相应的讨论。在误 用检测中，所有的训练学习数据都被标记为正常的标记或异常的标记，任何一个 学习算法都是利用这个被标记的数据集上进行训练和学习；在异常检测中，绝大 多数算法都是从一个被标记为正常的数据集中学习，然后组建一个正常的行为模 型；最后，根据刚收集到的新数据离正常模型的程度大小，来判断这个新数据是 正常数据还是异常数据。 因此，大多数应用到误用检测和异常检测的聚类算法都很依赖带标签的训练 数据，如果训练数据的标签错误，那么通过该算法训练学习得到的正常和异常数 据模型就会出错，从而降低检测效率，甚至根本无法检测。然而，我们根本不可 能在互联网中实时地、很容易地获得有标签的或正常的网络数据。对于大量的网 络数据进行人工手动地分类根本不现实。如果我们是通过一些模拟入侵攻击行为 或者正常行为获得被标记的数据，那样我们所组建的数据模型又不能完整地反映 网络和计算机系统的真实的所有网络行为。而现在我们能够检测到的入侵攻击也 将仅限于我们自己所能模拟的入侵攻击，在未来出现的新攻击行为却无法及时反 映到训练数据中去。无监督聚类算法的研究也将变得越来越重要。 2 1 2 无监督聚类算法研究的现状及展望 无监督聚类算法的研究是一个新兴的研究领域，有着很好的研究前景。当然， 无监督聚类算法又是一个非常挑战的课题。从处理问题的角度来说，有以下几点： 1 被训练、学习的数据不需要标记上标签。 2 实际网络中的数据都是海量数据，同时是高维、异构的。 3 要求该算法具有自学习和自适应能力、筛选有用信息的能力、快速反应的 能力。 5 电子科技大学硕士学位论文 因此，现有技术与需要处理问题的需求是相互矛盾的。正是这种矛盾推动着 无监督聚类算法向前发展；当然，我们根本找不到一个算法完全满足上面这些要 求，而且还能克服现在这些算法的全部缺点和不足的地方；常见的方法是：在各 种性能之间找到一个平衡点，找到能处理好问题的、行之有效的方法。 2 2 聚类分析 2 2 1 聚类的数学定义 聚类是一种常用的数据挖掘和数据分析的工具，也就是把物理或者者抽象对 象的集合分为由相似的对象组成的多个类或簇的一个过程。通过聚类方法所生成 的类或簇都是对象的集合，这些对象和同一个类或簇中的对象都是相似的，和其 它类或簇中的对象不同。下面我们对聚类过程的数学表示如下： 不放假设，样本集是e ，类c 定义成e 的一个非空子集， 即c c e 且c = 每个类或簇就是满足下面二个条件的类或簇q ，c 2 ，c 的集合 1 guc 2 u g = e 2 q n c ，= 垂( 对任意i 歹) 由条件1 可以知道，样本集e 中的任何一个一定属于某一个类或簇。由条件2 可以知道，样本集e 中的任何一个最多只属于一个类或簇。 2 2 2 聚类的相异度度量 常见的数据类型包括区间标度变量、二元变量、序数型、标称型以及比例标 度变量。针对不同的数据类型，度量方法也就不同。有以下几种度量方法： 1 区间标度度量 区间标度变量是一种线性的连续型变量，如长度。为取得较好的聚类效果， 数据必须先进行标准化。进行下列变换： 1 ) 平均的绝对偏差s 1 s = 二( i 五一所l + i 恐一ml + + l 一m1 ) ，z 其中，而，是n 个度量值，m 是五，的平均值，即 1 ，竹= - - ( x , + 乇+ + k ) 6 第二章数据聚类算法 2 ) 标准化的度量值z z f = 王竺 j 通过标准化处理后，对象之间的相异度一般是欧氏距离来计算的。定义如下： d ( i ，) = l 毛一。1 2 + l 五：一勺2i 2 + 1 一勃1 2 其中，i = ( x t 。，五：，) 和j = ( x j 。，：，b ) 是二个p 维的数据对象。 2 二元变量 二元变量有两种状态：1 或者0 ，1 代表这个变量还存在，0 代表这个变量 为空。二元变量可以分成对称的和非对称的。对称二元变量的两种状态的权重是 相同的。定义： d ( i ，) = 生 g 十，十s 十t 其中，r 是对象i 值为1 而对象j 值为0 的变量数目；s 是对象i 值为0 而 对象j 值为1 的变量数目；q 是对象i 和j 值都为1 的变量数目； t 是对象i 和j 值都为0 的变量数目。 非对称二元变量的两种状态是非对称的。定义： d ( i ，) = 旦 q + r r s 3 标称变量 标称变量其实是二元变量的延伸，标称变量具有多种状态值。定义： d ( i ，_ ，) = 旦竺 p 其中，p 是全部变量的数目，m 是i 和j 取值相同的变量数目。 4 序数型变量 离散的序数型变量类似于标称变量。其相异度计算包括如下步骤： 1 ) 将变量值替代成1 聊之间的数；其中，所是有序状态的个数。 2 ) 将所有变量的值域映射n o ，1 】，使所有变量有相同的权重。 3 ) 使用区间标度变量的相异度计算方法。 5 比例标度型变量 不妨假设，数据集中有p 个不同类型的变量，对象i 与对象j 之间的相异 度d ( i ，j ) 定义为： 7 电子科技大学硕士学位论文 母力彤厶。i ”驴 d ( i ，) = 型f 一 秀门 其中，如果诱或者b 缺失，或靠= b = o ，那么指示项彭= o ；否则等于1 。 可以利用它的具体类型来计算。 2 3 传统聚类算法 所有聚类算法输入的都是：含有很多数据的一个数据集，所有数据都是用一 个属性向量( 五，置，) 表示；其中，置是离散型变量或者连续型变量，代表一 个属性值。所有聚类算法输出的都是若干个聚类。聚类算法的框架图如下： 图2 1 聚类算法框架 目前传统聚类算法可以分成以下几类1 5 】：基于划分方法、基于密度的方法、 基于层次的方法、基于网格的方法、基于模型的方法。 2 3 1 基于划分的方法 一个数据集中有n 个数据，基于划分的方法将整个数据集分成k 个子集；其 中，任何子集都代表一个类或者簇( 后以) 。这些类满足下列条件： 1 每类中至少有一个对象。 2 每个数据必须只能属于一个类。 k - m e 柚s 算法的步骤为： ( 1 ) 给定聚类个数k 。 ( 2 ) 选取k 个向量作为初始点：q ，e 2 ，& 。 ( 3 ) 分类的样本五，i = 1 ，2 ，以；按下面欧式距离计算n 个样本与某一个聚类 中心。 8 第二章数据聚类算法 i | 毛一c ji l = m i n | l 而一cil，1歹 ，其中a d ，r 为实数集合，为匹配阈值，根据下式( 2 1 ) 来完成分类： 聊舭j z ( f , e , i , d ) = p 皂笸，厂( i , a ) 扎q ( 2 - 1 ) 一 l - 目1 本，o t he g w i s e 第二，形态空间；不妨假设，入侵检测过程都发生在形态空间s ，s 是高维的空间， 空间s 中的点代表数据集中相互关联的数据，这个数据集包含二个子集自体集 和非自体集。空间s 的维数是空间s 中点的属性个数，根据用数学的向量定义， 现在可以把空间s 的点描述成三维字符串或者向量。在入侵检测过程中，先定义一 些数量的自体集，通过一些训练和学习来生成初始的检测器；再给定检测器的识 别区域，检测器能够识别到该区域中的所有非自体，从而实现用有限的检测器集 来检测无限的非自体，并通过计算二者之间的距离来完成对数据的分类，达到更 新和完善检测器的目的。第三，人工识别球( a r t i f i c i a lr e c o g n i t i o nb a l l s ，a r b s ) ；识 别球是在形态空间的理论基础上提出的；不妨假设识别区域都是球形，形态空间 的体积大小为y ，在这个空间中有n 个随机分布的检测器，这些检测器所对应的识 别球半径为，其体积为k ，那么总的检测体积为罗k ，1 f 刀。如果总的检测体 。一i_ 扭l 积大于形态空间的总体积y ，则认为这些检测器完全覆盖形态空间；由于这些检 测器是球形，所以检测器之间有重叠的识别区域，这也就证明了基于a i n e t 增量聚 类的入侵检测系统能够保证系统的安全性、可靠性。 实际上，入侵检测就是识别和区分数据是自体还是非自体，而判断方法是利用 检测器对数据进行识别和分类，所以入侵检测的关键还是在于聚类算法。本文提 出的a i n e t 增量聚类算法就是一种无监督的自主学习技术，它不必对初始数据进行 标记，就能自动对数据进行分析和分类。不妨假设，正常网络数据和异常网络数 据有本质上的区别，只有这样才能将它们区分开。事实上，在互联网中，正常的 1 4 第二章数据聚类算法 用户行为占绝大多数，黑客和误操作的用户一般很少，正常用户的网络数据和黑 客入侵行为产生的数据完全不同，因此，二者是完全相吻合的。在此基础上，假 设网络数据包是一个可划分聚类的数据集，其中正常网络数据占大部分，异常网 络数据只占少部分，因此，我们认为通过聚类算法生成的划分聚类解是网络数据 包中的正常网络数据的聚类中心，是用户正常网络行为的数据样本，而其他的数 据就会被认为是异常的入侵攻击行为，这样就可以建立一个免疫模型的自体和非 自体集；而且它们能够真实地反应实际数据的分布结构和特征。 1 5 电子科技大学硕士学位论文 第三章入侵检测 3 1 入侵检测的相关概念及功能 3 1 1 入侵检测的相关概念 入侵检测( i o nd e t e c t i o n ) 是指通过从计算机网络或者系统中收集相关的重 要信息并对其进行分析，从中发现计算机网络或者系统中是否有符合安全策略的 行为和被入侵迹象的一种安全技术。入侵检测作为对传统防御技术如防火墙的一 种补充，是计算机的第二道防御体系，监测计算机网络或者系统，并能够对外部 攻击、内部攻击以及错误操作的进行实时保护。它能对计算机网络或者系统起着 主动防御的作用，是计算机安全和网络安全必不可少的一个组成部分。 入侵检测大致可以分成3 个步骤，分别是信息收集、数据分析、响应( 被动响 应和主动响应) 。相应地，入侵检测系统i d s 一般由信息收集、数据分析、响应三 个功能模块组成，分别承担以上3 个步骤的任务。下面是几个入侵检测的相关概 念：警报( a l e r t ) 、异常( a n o m a l y ) 、攻击( a t t a c k s ) 、漏报( f a l s en e g a t i v e s ) 和 误报( f a l s ep o s i t i v e s ) 等；其中，漏报和误报是入侵检测的二个重要概念；评价 一个入侵检测系统的好坏就是要看它的漏报率和误报率的高低；优秀的入侵检测 系统可以从很大程度上协助管理员的安全工作，这样管理员可以更容易地监控、 监视网络和计算机系统，大大提高系统管理员的安全管理能力，这样便可以保证 计算机系统网络和系统安全地运行。 3 1 2 入侵检测系统的功能 入侵检测系统是通过数据分析和网络行为判断其行为是不是入侵行为，如图 3 1 所示，防火墙可以阻止外部攻击，但无法阻止内部攻击。访问控制系统可以阻 击低权限的人做越权访问，但无法阻止高权限的人做破坏工作。漏洞扫描系统能 够发现计算机系统和网络存在的漏洞，但无法对计算机系统和网络行为进行实时 扫描。 1 6 第三章入侵检测 图3 - 1 入侵检测的功能 入侵检测系统的功能如下： 1 准确地识别各种攻击活动。 2 监控用户和计算机系统的活动。 3 准确找到计算机系统的漏洞和弱点。 4 评估系统的安全性和各种文件的完整性。 5 判断、分析各种异常活动。 6 进行跟踪管理，识别违反行为策略的活动( 包括内部和外部) 。 入侵检测系统主要特征如下： 1 准确地检测出入侵行为和攻击。入侵检测系统不能出现误报，不应遗漏各 种攻击。它必须及时快速报告入侵活动，能检测不同的攻击行为。 2 强大的抗攻击能力。一个优秀的入侵检测系统不会轻易被攻击者入侵，它 必须能监视各种行为并能检测出是否是攻击行为。 3 有较强的容错功能。优秀的入侵检测系统崩溃之后，它必须能快速地恢复 到正常的状态，并且正常地重新提供服务。 4 不断地运行，而且尽量避免人工的干预。 5 系统运行消耗的资源小，以免影响系统的其他正常操作运行。 6 用户自己可以选择性的进行配置，从而实现被监测系统的安全策略。 7 容易使用和方便操作。 8 能够适应各种计算机系统和用户的变化。比如新应用程序的安装后，入侵 检测系统能够正常工作。 1 7 电子科技大学硕士学位论文 3 2 入侵检测的方法 从检测方法实现技术的不同角度出发，入侵检测技术可以分成三类：异常检 测( a n o m a l yd e t e c t i o n ) ，误用检测( m i s u s ed e t e c t i o n ) ，混合检测( c o m p o u n d d e t e c t i o n ) 。 3 2 1 误用检测方法 误用检测是指利用发现的攻击方法，由己定义好的入侵模式，通过判别这些 入侵模式是否出现来实现入侵检测。误用检测技术的主要难点：它只能根据己知 的入侵行为和系统漏洞来检测系统和网络中的行为，而对未知的入侵攻击行为和 未知的、潜在的系统漏洞无能为力。误用入侵检测技术的核心部分是建立一个入 侵检测规则库，还需要不断地更新。误用入侵检测依赖的是模式库，如果没有建 立最新的模式库，i d s 就不能检测到新的入侵者【5 0 】。误用检测系统类型包含专家 系统、误用预测系统以及模式匹配系统i ”j 。 误用检测主要需要解决的问题有： 1 怎样全面地描述各种网络攻击的特征，同时覆盖各种变种攻击特征。 2 怎样排除那些具有干扰的用户行为，从而使误报率降低。 3 如何划分基于误用检测系统的类型。 误用检测由于根据具体行为特征库进行判别，所以检测准确度特别高，并且 检测结果有一定的参照，以便于用户使用和理解。但是误用检测主要难点在于系 统移植性不好，对系统依赖性很强，维