已阅读5页,还剩58页未读, 继续免费阅读
(计算机应用技术专业论文)基于免疫算法和增量支持向量机的入侵检测研究.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
重庆邮电大学硕士论文摘要 摘要 入侵检测是一种用于检测计算机网络系统中入侵行为的网络信息安 全技术,目前已成为网络安全领域中的重要研究方向之一。以机器学习为 基础的异常检测技术,通过对样本的学习分析检测已知甚至未知攻击,渐 渐成为入侵检测主要研究的方向。但传统机器学习的入侵检测存在误报、 漏报及实时性差等缺点,且无法适应数据量增大的趋势,使机器学习时间 越来越长。 本文侧重于研究基于支持向量机的入侵检测系统中需要解决的两方 面问题,一是入侵检测评估样本集k d d c u p 9 9 的关键特征的选择;二是解决 入侵数据增多,导致支持向量机训练时间过长问题。 在k d d c u p 9 9 关键特征的选择方面,提出了一种基于免疫算法的特征选 择方法。免疫算法( i a ) 作为一种新的全局优化搜索算法,在算法实现上兼 顾全局搜索和局部搜索,吸取了遗传算法( g a ) 并行搜索优点,使得算法快 速收敛,同时保持一定的多样性,抑制了早熟现象,加快搜索到最优特征 子集的速度。对k d d c u p 9 9 数据集进行大量实验结果表明,免疫算法能有效 降低样本特征维数且训练预测精度得到提高,与基于遗传算法特征选择的 结果相比较,在有限代数内,该算法能收敛到更优的特征子集,从而验证 了算法的有效性和潜力。 在解决训练时间过长方面,提出增量学习方法。现有标准增量支持向 量机( s i s v m ) 算法虽然有效解决训练时间过长问题,但其过多的丢失对分 类有用的样本,导致训练得到的模型分类精度下降。因此本文提出新的改 进增量支持向量机算法( r i s v m ) ,该算法提出概率最大样本、邻近样本的 概念,目的是有选择的增加有用的样本,提高模型的分类精度和泛化能力。 实验通过r i s v m 、s i s v m 和批量学习算法( b a s v m ) 三种算法的对比,结果表 明,r i s v m 在训练时间上比s i s v m s n b a s v m 低,且测试时问和测试精度都比 s i s v m 和b a s v m 两者优秀,因此本文提出的算法更符合入侵检测系统要求。 关键词:入侵检测,免疫算法,特征选择,支持向量机,增量学习 重庆邮电大学硕士论文 摘要 a b s t r a c t i n t r u s i o nd e t e c t i o ni sat e c h n o l o g yo fn e t w o r ks e c u r i t ya n db e c o m eo n e o fi m p o r t a n tr e s e a r c hw h i c hi su s e di nn e t w o r ki n t r u s i o nd e t e c t i o n t h e a n o m a l y d e t e c t i o n t e c h n o l o g yb a s e d o nm a c h i n ele a r n i n gb e c o m e st h e i m p o r t a n tr e s e a r c hg r a d u a l l yw h i c hc a nd e t e c tk n o wa n du n k n o w ni n t r u s i o n b ya n a l y s i st h es a m p l e b u tt r a d i t i o n a lm a c h i n el e a r n i n gh a st h ed i s a d v a n t a g e s o ff a l s ep o s i t i v e s ,f a l s en e g a t i v e sa n du n r e a l t i m e i tc a n ta d a p tt ot h et r e a d o fi n c r e a s i n gd a t ab e c a u s ei tm a k e st h et r a i n i n gt i m em o r ea n dm o r el o n g t h i sp a p e rm a i n l ys o l v e st w oq u e s t i o n s t h ef i r s ti st os e l e c tk e yf e a t u r e s o fe s t i m a t i o n ss a m p l es e tk d d c u p 9 9 ;t h eo t h e ri st os o l v et h eq u e s t i o nw h i c h i n c r e a s i n gd a t am a k et h et r a i n i n gt i m eo fs v ml o n g e rt h a nb e f o r e t h em e t h o do ff e a t u r es e l e c t i o n sb a s e do ni m m u n ea l g o r i t h m ( i a ) i s p r e s e n t e d i ai s an e wg l o b a lo p t i m i z a t i o ns e a r c h i n ga l g o r i t h m i th a st h e c h a r a c t e r i s t i c so fg l o b a la n dl o c a ls e a r c ha n da s s i m i l a t e st h ep a r a l l e ls e a r c ho f g aa n dk e e p st h ed i v e r s i t yw h i c hr e s t r a i n sp r e m a t u r ec o n v e r g e n c ea n ds p e e d t h es e a r c h i n go fo p t i m a lf e a t u r es u b s e t e x p e r i m e n t ss h o wt h a ti ac a nr e d u c e t h ef e a t u r e sa n di m p r o v et h ep r e d i c t i o na c c u r a c y a n di ac a n sc o n v e r g e n c et o t h eo p t i m a lf e a t u r es u b s e ta n de f f i c i e n c ya n dp o t e n t i a la r ev e r i f i e d t h em e t h o do fi n c r e m e n t a ll e a r n i n gi sp r e s e n t e dt os o l v el o n gt r a i n i n g t i m e t h es i s v mc a ns o l v et h eq u e s t i o n ,b u tm u c hu s e f u ls a m p l e sw h i c hc a n i m p r o v et h ec l a s s i f i c a t i o na c c u r a c yo fm o d e la r el o s t ,s oan e w r e v i s ei s v mi s p r e s e n t e di nt h i sp a p e r t h ec o n c e p to fm a x i m u mp r o b a b i l i t ys a m p l e sa n d c o n t i g u i t ys a m p l e sw h i c ha r ef o ra d d i n gu s e f u ls a m p l e s a n di m p r o v e st h e c l a s s i f i c a t i o na c c u r a c yo fm o d e la n dt h eg e n e r a l i z a t i o na b i l i t ya r ea d v a n c e d r i s v m ,s i s v ma n db a s v m a r ec o m p a r e di ne x p e r i m e n t s i ts h o w sr i s v m s p e n dl e s st r a i n i n gt i m et h a ns i s v ma n db a s v ma n dh a sm o r ea d v a n t a g e t h a ns i s v ma n db a s v mi nt e s t i n gt i m ea n da c c u r a c y s ot h ea l g o r i t h m p r e s e n t e di nt h i sp a p e ri sm o r em e e tt h er e q u i r e m e n t so fi n t r u s i o nd e t e c t i o n k e yw o r d s : i n t r u s i o nd e t e c t i o n ,i m m u n ea l g o r i t h m ,f e a t u r es e l e c t i o n , s u p p o r tv e c t o rm a c h i n e ,i n c r e m e n t a ll e a r n i n g i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他 人已经发表或撰写过的研究成果,也不包含为获得重鏖邮电太堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名:i 礴 l 刮签字目期岬年f 月罗日 学位论文版权使用授权书 本学位论文作者完全了解重废业电盍堂有关保留、使用学位论文的规 定,有权保留并向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查 阅和借阅。本人授权重废韭皇盍堂可以将学位论文的全部或部分内容编入 有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 导师签名:乖匆磊穆 签字日期。2 可年月7 日 1 日r 弓p 月 一 , 6 年 名f、, 签 归 者 工 作 : 文 期 沦 日 位 字 学 签 重庆邮电大学硕士论文第一章绪论 1 1 引言 第一章绪论 随着计算机网络技术的发展,网络安全下日益成为人们关注的焦点, 传统的被动防御措施如防火墙技术、数据加密等不足以抵御黑客攻击,具 有学习能力的入侵检测技术成为网络安全的研究热点。入侵检测技术【lj 是 通过对计算机网络和主机系统中的关键信息进行实时采集和分类,从而判 断出非法用户入侵和合法用户滥用资源的行为,并做出适当反应的网络安 全技术。 近年来随着机器学习技术研究领域的拓展,把机器学习的技术应用到 入侵检测系统中得到很多学者的研究1 2 1 ,如c o l u m b i a 大学的w l e e 研究 小组从数据挖掘技术的角度探讨了入侵检测【3 】,k f o x 等人使用神经网络 来进行攻击检测,对于异常检测和识别分别采用多层感知机m l p 和多层 b p 神经网络模型,取得了不错的实验效果【4 j 。张凤斌等人在2 0 0 4 年提出 一个基于遗传算法的网络异常入侵检测算法【5 j 。l h z h a n g 等把粗糙集分 类用于入侵检测特征排序与选择。并利用g a 对规则进行进化学习,算法 可以得到“i f - t h e n ”形式的规则【6 】。f o r r e s t 小组提出基于免疫机制的入侵检 测模型【7 】。d s k i m 等利用支持向量机对k d d c u p 9 9 评估数据源进行网络 异常检测作了详细研究哺j 。 入侵检测可以看作是一个分类问题,也就是对给定的审计数据进行分 类:什么样的数据是正常的,什么样的数据是异常的。但现在流行的入侵 检测系统都存在误报、漏报及实时性差等缺点,且无法适应数据量增大的 趋势,这样会导致学习机学习时间过长的缺点。 本文所研究的和讨论的主要问题,如何通过免疫算法对k d d c u p 9 9 入 侵检测评估样本集进行特征选择;分析标准增量支持向量机的缺点,提出 新改进增量支持向量机,用k d d c u p 9 9 样本集进行评估测试,目的通过本 论文提出的方法能够有效解决支持向量机在入侵检测中存在的问题。 重庆邮电大学硕士论文第一章绪论 1 2 入侵检测研究的现状 1 2 1 入侵检测研究的内容 为便于评价不同异常检测的方法,m i t 林肯实验室在1 9 9 8 年和1 9 9 9 年 进行了一项入侵检测离线评估计划,公布了两套标准测试数据,其中最为 著名的是k d d c u p 9 9 评估数据集。在基于k d d c u p 9 9 评估数据集的入侵检 测研究中,入侵特征选择优劣和分类算法效率的好坏是两大主要研究内 容。 特征选择在入侵检测领域中扮演着一个极其重要的角色。一方面,在 样本有限的情况下,用大量特征来设计分类器无论是从计算开销还是从分 类器性能来看都不合时宜;另一方面,特征和分类器性能之间并不存在线 性关系,当特征数量超过一定限度时,会导致分类器性能变坏。因此,进 行正确有效的特征选择成为入侵检测领域必须要解决的问题,在海量数据 条件下尤为重要。特征选择是根据某种性能判据,从所有输入特征中选择 重要特征,去掉次要特征,这往往有利于缩短检测时间、发现某类攻击的 特征。特征选择的过程是一个求解组合优化问题的过程,因此可以用解决 组合优化问题的方法来解决特征选择问题。目前常用的算法有遗传算法, 粒子群优化算法,模拟退火算法,免疫算法等。 分类算法有神经网络、贝叶斯分类、支持向量机( s v m ) 等。s v m 是 v a p n i k 等人提出的一种全新的机器学习方法,近来,由于其优越的学习能 力,在国内外学术晃日益受到广泛的重视。s v m 主要思想可以概为两点: 它是针对线性可分情况进行分析,对于线性不可分的情况,通过使 用非线性映射算法将低维输入空间线性不可分的样本映射到高维属性空 间使其可分,从而使得在高维属性空间采用线性算法对样本的非线性特征 进行分析成为可能。 它通过使用结构风险最小化的理论在属性空间构建最优化分割超 平面,使得学习器得到全局最优化,并在整个样本空间的期望风险以某个 概率满足一定上界。因此,无论是在理论基础还是应用前景上,s v m 在很 多方面都具有其它学习方法难于比拟的优越性。 2 重庆邮电大学硕士论文 第一章绪论 1 2 2 目前存在的主要问题 特征选择需要解决两个问题,一是有效的特征子集的搜索策略,在允 许的时间内,以可以忍受的代价找出最小的、最能描述类别的特征组合; 二是确定评价标准,衡量特征组合是否最优,获取操作的停止条件。因此, 一般分两步进行特征获取,先产生特征子集,然后对子集进行评价,如果 满足停止条件,则操作完毕,否则重复前述两步直到条件满足为止。特征 选择大体上可以看作是一个搜索问题,搜索空间中的每个状态都指定可能 特征的一个子集。当特征维数为时,其搜索空间为2 “。原则上讲,只有 穷举搜索才能找出特征的最佳子集,但是当特征数目和数据量急剧增加 时,这种方法是不现实的。因此采用启发式搜索或随机方法搜索成为可能。 它们的策略是做局部最优选择,期望由此导致全局最优解。但现在方法大 都只能找到局部最优值,很难达到全局最优。因此需要一种更有效的全局 最优的优化算法。 基于支持向量机等机器学习方法的入侵检测系统,只有当存在完备的 审计数据集时,支持向量机才具有较好的入侵检测性能。然而,现实中的入 侵行为是不断变化的,很难获得完备的审计数据集和未知的攻击类型的入 侵。因此我们希望入侵检测系统对新的入侵行为具有增量式学习能力,使 其性能随着样本集的积累而逐步提高。 机器学习有批量学习( b a t c hl e a r n i n 9 1 和增量学习f i n c r e m e n t a l l e a r n i n g ) ,如果按批量学习方法学习支持向量机,每次把新样本和所有的旧 样本重新训练,这样需要相当长的训练时问,相应的增加了检测时间,且训 练得到的支持向量机模型泛化能力差。因l 比s y e d 9 】最早提出了基于支持向 量机的增量算法。在该算法中每次增量学习后只保留支持向量,丢弃所有 非支持向量样本,实验证明此方法虽有效的降低了训练时间,但样本分类 精度会下降,因为过多的丢失对支持向量机分类有用的样本,因此如何有 效的遗忘对训练精度影响不大的样本是解决增量学习的关键,也是研究增 量支持向量机的重点。 1 3 本文研究工作 本文主要涉及两个大的方面研究内容:一是免疫算法的研究以及对入 侵检测评估数据集k d d c u p 9 9 进行特征选择应用研究;二是提出新的改进 重庆邮电大学硕士论文第一章绪论 增量支持向量机算法以及在入侵检测中的应用研究。 分析研究现有各种免疫算法( i m m u n e a l g o r i t h m ) ,特别是应用于优化领 域的免疫算法,重点分析了免疫克隆选择算法及实现步骤。且建立免疫算 法进行特征选择的模型,此模型同样适合其它随机优化选择算法。实验首 先对k d d c u p 9 9 数据预处理,然后利用免疫克隆选择算法与标准遗传算法 比较证明,免疫克隆选择算法所选出的特征子集数目不仅小于遗传算法, 而且训练预测精度高。证明免疫算法的特征选择的有效性。 研究分析了标准增量支持向量机( s i s v m ) 不足,提出一种新的改进增 量支持向量机( r i s v m ) 的算法,该算法充分利用非支持向量和测试正确样 本,算法中提出概率最大样本与邻近样本的概念,目的是增加对支持向量 机分类有用的样本,并把r i s v m 用于入侵检测,实验证明该改进算法在 训练时间上比批量支持向量机( b a s v m ) 和s i s v m 有下降,而且测试精度 和测试时间都比其它两种算法效果好。 1 4 论文组织与结构 本文共分五章,各章的内容安排如下: 第一章是绪论。主要概述入侵检测需要研究的内容和目前存在的不 足。 第二章是入侵检测技术原理。主要概括了入侵检测系统的基本理论及 分类。包括入侵检测的概念、检测技术的分类、入侵检测体系架构。 第三章是基于免疫算法的k d d c u p 9 9 特征子集选择。主要概括了特征 选择涉及的问题,免疫算法的基本概念,重点描述免疫算法中一种优化算法 免疫克隆算法,并描述了利用免疫克隆算法进行特征选择的基本步骤。实 验证明其有效性。 第四章是基于增量支持向量机入侵检测研究。简要介绍了支持向量机 的基本概念,分析标准增量支持向量机原理及弊端,提出一个新的改进增 量支持向量机算法。并通过实验对b a s v m ,s i s v m 和r i s v m 三者比较, 证明r i s v m 的优势。 第五章是结论。 4 重庆邮电大学硕士论文 第二章入侵检测技术原理 第二章入侵检测技术原理 2 1 入侵检测技术概念 入侵,是指任何试图危及计算机资源的完整性,机密度性或可用性的 行为。而入侵检测对入侵行为的发觉。它通过从计算机网络或系统中的若 干关键点收集信息,并对这些信息进行分析,从而发现网络或系统中是否 有违反安全策略的行为和遭到攻击的迹象。 入侵检测作为一种积极主动地安全防护技术,提供了对内部攻击、外 部攻击和误操作的实时防护,在网络系统受到危害之前拦截和对入侵做出 响应。强大的入侵检测软件的出现极大的方便了网络的管理,实时报警为 网络安全增加了又一道保障。从网络安全立体纵深、多层次防御的角度出 发,入侵检测理应受到人们的高度重视j 但现状是入侵检测还不够成熟, 处于发展阶段,或者是防火墙中集成较为初级的入侵检测模块,所以对于 入侵检测技术的研究是很重要的。未来的入侵检测系统将会结合其它网络 管理软件,形成入侵检测、网络管理、网络监控三位一体的结构。 2 2 通用入侵检测模型 公共入侵检测框架( c o m m o ni n t r u s i o nd e t e c t i o nf r a m e w o r k ,c i d f ) u j 建立了一个公共体系结构、入侵描述语言规范和应用程序接口规范,使不 同的入侵检测和相应工具在该体系结构下可以通信,致力于解决互操作性 问题。如图2 1 ,c i d f 将入侵检测系统分为了四个组件: 事件产生器( e v e n tg e n e r a t o r s ) :从整个计算环境中获得事件,并向系 统的其它部分提供此事件。 事件分析器( e v e n ta n a l y z e r s ) :分析得到的数据,并产生分析结果。 响应单元( r e s p o n s eu n i t s ) :对分析结果作出反应的功能单元,它可以 是作出切断连接、改变文件属性等反应,甚至发动对攻击者的反击,也可 以只是简单的报警。 事件数据库( e v e n td a t a b a s e s ) :存放各种中间和最终数据的地方的总 称,它可以是复杂的数据库,也可以是简单的文本文件。 重庆邮电大学硕士论文第二章入侵检测技术原理 c i d f 模型将入侵检测系统( i d s ) 需要分析的数据统称为事件( e v e n t ) , 它可以是网络中的数据包,也可以是从系统日志等审计记录途径得到的信 息。组件之间的交互数据被封装到c i d f 消息中进行传递。 图2 1c i d f 模型 2 3 网络入侵方式分类 网络攻击的方式和方法从早期的粗糙、单一的攻击方法发展到今天的 精致、综合的攻击方法。早期主要的攻击方法以口令破解、泛洪式拒绝服 务和特洛伊木马为主;近几年出现了综合各种网络攻击手段的网络欺骗攻 击、分布式拒绝服务攻击和分布式网络病毒攻击等。下面从入侵者的角度 出发,入侵的步骤可分为探测( p r o b e ) 、攻击( e x p l o i t ) 和隐藏( c o n c e a l ) 。 因此可分为探测技术、攻击技术和隐藏技术三大类】。 探测技术,信息探测类攻击主要是收集目标系统的各种与网络安全有 关的信息,为下一步入侵提供帮助。这类攻击主要包括:扫描技术、体系 结构刺探、系统信息服务收集等。目前正在发展更先进的网络无踪迹信息 探测技术。 攻击技术,攻击者通过探测阶段掌握的有关攻击目标的安全情况会选 择不同的攻击方法来达成其攻击目的。攻击方法层出不穷,但我们可以将 其归为以下四类,即窃听技术、欺骗技术、拒绝服务和数据驱动攻击。 窃听技术指攻击者通过非法手段对系统活动的监视从而获得一些安 全关键信息。目前属于窃听技术的流行攻击方法有键击记录器、网络监听、 非法访问数据和攫取密码文件。 欺骗技术包括i p 地址欺骗和假消息攻击,前者通过冒充合法网络主机 获取敏感信息,后者主要是通过配置或设置一些假消息来实施欺骗攻击, 主要包括:a r p 缓存虚构、d n s 高速缓存污染、伪造电了邮件等。 拒绝服务攻击指中断或者完全拒绝对合法用户、网络、系统和其他资 源的服务的攻击方法,被认为是最邪恶的攻击,其意图就是彻底地破坏, 而这往往比真正取得他们的访问权要容易得多,同时所需的工具在网络上 6 重庆邮电大学硕士论文第二章入侵检测技术原理 也唾手可得。d o s 是典型的拒绝服务攻击,常见的方法有:泪滴攻击、d d o s 攻击、u d p t c p 泛洪攻击、l a n d 攻击、s m u r f 攻击、电子邮件炸弹等多种 方式。 数据驱动攻击是通过向某个程序发送数据,以产生非预期结果的攻 击,通常为攻击者给出访问目标系统的权限,数据驱动攻击分为缓冲区溢 出攻击、格式化字符串攻击、输入验证攻击、同步漏洞攻击、信任漏洞攻 击等。 隐藏技术,攻击者在完成其攻击目标( 如获得r o o t 权限) 后,通常会 采取隐藏技术来消除攻击留下的蛛丝马迹,避免被系统管理员发现,同时 还会尽量保留隐蔽的通道,使其以后还能轻易的重新进入目标系统。隐藏 技术主要包括日志清理、安装后门、内核套件等。 2 4 入侵检测技术分类 按照检测技术原理可分为误用检测( m i s u s ed e t e c t i o n ) 、异常检测 ( a n o m a l yd e t e c t i o n ) 1 2 】 误用检测是运用已知攻击方法,通过将已定义好的入侵模式和待检测 数据比较进行检测的。因为绝大部分的入侵是利用了系统的脆弱性,所以 通过分析入侵过程的特征、条件、排列以及事件间的关系就能具体描述入 侵行为的迹象。这种方法由于是根据具体的攻击特征库进行判断,所以检 测的准确度很高,目前大多数入侵检测系统都采用这种方法。主要缺陷是 只能检测已知的攻击,漏报率较高,对具体系统的依赖性太强,不但系统 移植性不好,维护工作量大,而且将具体入侵手段抽象成为知识也很困难。 误用检测通过对已知决策规则编程实现,可以分为以下三种: 状态建模,它将入侵行为表示为许多个不同的状态。如果在观察某个 可疑行为期间,所有状态都存在,则判定为恶意入侵。 专家系统,它可以在给定入侵行为描述规则的情况下,对系统的安全 状态进行推理。一般情况下,专家系统的检测能力强大,灵活性也高,但 计算成本较高,通常以降低执行速度为代价。 串匹配:它通过对系统之间传输的或系统自身产生的文本进行子串匹 配实现。该方法灵活性差,但易于理解,目前有很多高效的算法,其执行 速度快。 异常检测是假设攻击者的行为模式异于正常使用者的行为模式,用户 的正常行为数据来建立系统及网络的正常行为模型,通过比较待检测数据 7 重庆邮电大学硕士论文第二章入侵检测技术原理 与正常行为模型的差异来判断待检测数据是否为攻击行为。因此它可以检 测出未知的攻击。但是因为不可能对整个系统内所有用户行为进行全面的 描述,况且每个用户的行为是经常改变的,所以它的主要缺陷在于误检率 高,入侵者如果知道某系统在检测器的监视之下,他们就能通过训练检测 系统,以至于检测系统最初认为是异常的行为经过一段时间训练后也可能 判定为正常,异常检测方法有概率统计方法、。基于免疫原理,机器学习方 法等。 概率统计方法:是基于对用户历史行为建模,以及在早期的证据或模 型的基础上检测用户对系统的使用情况。系统要根据每个用户以前的历史 行为,生成每个用户的历史行为记录库,当有可疑用户行为发生时,跟踪、 监测并记录该用户的行为。 基于免疫原理的异常检测:生物免疫系统对病原体或非自身组织的检 测是相当精确的,识别“自我i - - - i 我( s e l f n o n s e l f ) ”是其最基本也是最重要的 功能之一。美国的f o r r e s t 等研究人员在生物免疫机制和计算机系统安全保 护机制之间发现了某种相似性,发展了基于免疫原理的异常检测方法。这 种方法以系统调用为审计数据,通过长度固定的系统调用序列来描述特权 进程的正常行为模式( 轮廓) ,并将序列之间的“距离”作为反映行为模式之 间差异的测度。实验表明,基于免疫原理的异常检测系统可以检测出许多 利用u n i x 程序漏洞进行的攻击行为。 机器学习的方法【1 3 】:机器学习应用于入侵检测技术方面有两种思想。 一种是把入侵检测看成一个模式识别问题,即根据网络流量特征( 目的地 址、源地址、目的端口号、源端口号、传输协议、发送字节数、t c p 选项 等) 和主要审计记录( c p u 利用率、i 0 利用率、文件访问、用户命令序列) 等区分系统的正常行为和异常行为。另一种基本思想是把入侵检测视为一 个知识表示和规则提取问题。在入侵检测系统中,实际获得的数据源往往 具有多变性、不同质、高维数等特性,在高速网络环境下,采集的数据通 常构成一个多属性、非线性的海量数据集。在这种情况下,通过基于符号 的归纳机器学习方法( 决策树、粗糙集等) 对数据集进行约简,得到面向用 户的数据的简洁表示,提取出系统正常行为的规则,从而完成异常检测。 在网络安全防护中要充分衡量各种方法的利弊,综合利用各种方法, 有效地将异常检测和误用检测的思想结合起来,才能更有效地检测出入侵 者的非法行为。 重壅塑皇查兰堡主垒奎 笙三主垒堡垒塑垫查垦型 2 5 本章小结 本章的主要工作是为后面几章的入侵检测数据分析技术打下基础。在 对入侵检测系统概要性介绍的基础上,描述了虽基本的入侵检测系统的模 型以及目前流行的主要网络攻击方法,然后根据检测不同的分类标准,对 入侵检测进行了分类,详细描述了异常检测技术,误用检测技术。 重庆邮电大学硕士论文第三章基于免疫算法的k d d c u p 9 9 特征子集选择 第三章基于免疫算法的k d d c u p 9 9 特征子集选择 3 1 引言 在基于机器学习的入侵检测系统中,特征选择是机器学习领域的难 题。在实际应用中,寻找最优的特征子集通常是很难的,已被证明是n p 完全问题。但通过采用一些优化搜索算法,可以得到相对比较好的结果。 本章分析免疫算法的原理和常见的免疫优化算法,以及免疫算法相对于遗 传算法的优点。重点描述免疫优化算法中具有代表性的算法一免疫克隆选 择算法。实验首先对k d d c u p 9 9 入侵检测评估数据预处理,然后利用免疫 克隆选择算法进行k d d c u p 9 9 的特征子集选择,结果证明其效果相对遗传 算法较好。 3 2 特征选择方法分析 特征维数是多大的时候就已经包含足够的类别信息? 这是一个难以 确定的问题【1 4 】:一方面,在样本有限的情况下,用大量特征来设计分类器 无论是从计算开销还是从分类器性能来看都不合宜;另一方面,特征和分 类器性能之间并不存在线性关系,当特征数量超过一定限度时,反而会导 致分类器性能变坏,因此,一些文献【1 5 - 2 4 中提出了对于样本数据降维的方 法,以得到对分类最有效的特征。 数据降维常用的两类方法是特征变换和特征选择。 特征变换是指将原有的特征空间进行某种形式的变换,得到新的特 征。主成份分析是这类方法中最著名的算法,该算法对许多学习任务都可 以较好降维,但是特征的理解性很差,因为即使简单的线性组合也会使构 造出的特征难以理解,而在很多情况下,特征的可理解性是很重要的。另 外,由于特征变换的新特征通常由全部原始特征变换得到,从数据收集角 度看,并没有减少工作量。 特征选择是指从原始特征集中选择使某种评估标准最优的特征子集。 其目的是根据一些准则选出最小的特征子集,使得任务如分类、回归等达 到和特征选择前近似甚至更好的效果。通过特征选择,一些和任务无关或 1 0 重庆邮电大学硕士论文第三章基于免疫算法的k 1 ) d c u p 9 9 特征子集选择 者冗余的特征被删除,简化的数据集常常会得到更精确的模型。 如果把特征选择问题视为状态空间搜索问题,那么任何特征选择方法 基本都涉及以下的2 个问题:一是确定选择算法,在允许的时问内,以可 以忍受的代价找出最小的、最能描述类别的特征组合;二是确定评价标准, 衡量特征组合是最优,得到特征获取操作的停止条件,因此,一般分两步 进行特征获取,先产生特征子集,然后对子集进行评价,如果满足停止条 件则操作完毕,否则重复前述两步直到条件满足为止。基本过程如图3 1 3 2 1 特征子集的搜索策略 图3 1 特征选择过程 如何搜索优化特征子集的候选状态空间是特征选择的关键之一,目前 的搜索策略主要有三种:穷举法( e x h a u s t i o n ) 、启发式( h e u r i s t i c ) 方法和随 机( r a n d o m ) 搜索法i l 。 穷举法指遍历特征空间中所有特征的组合,选取最优特征组合子集的 方法。假设特征个数为时,则搜索空间为0 ( 2 “1 。常用的方法有回溯方 法及其变体等。其优点在于一定能得到最优子集,但实际情况下由于特征 空间过于庞大,时间耗费和计算复杂度太大,导致实用性不强。 启发式方法为一种近似算法,具有很强的主观倾向。实际应用中通过 采用期望的人工机器调度规则,重复迭代产生递增的特征子集。特征个数 为时,则搜索空间一般小于或者等于o ( n 2 ) 。这种方法实现过程比较简 单而且快速,在实际中应用非常广泛,如向前( 向后) 选择、决策树法、r e l i e f 方法及其变体等。但是,不能保证结果最优,般能够获得近似于最优解 的解。 随机方法是一种相对较新的方法,细分为完全随机方法和概率随机方 法两种。完全随机方法是指“纯”随机产生子集,概率随机是指子集的产 生依照给定的概率进行。虽然搜索空间仍为0 ( 2 “) ,但通过设置最大迭代 次数可以限制则搜索空间小于0 ( 2 “) 。常用的方法有遗传算法、模拟退火 算法及其变体等。这类方法需要进行参数设置,并且参数值决定是否能得 重庆邮电大学硕士论文第三章基于免疫算法的k d d c u p 9 9 特征子集选择 到最优解。 3 2 2 特征子集的评价标准 评价标准的主要作用是评价一个特征或一个特征子集对具有不同决 策标号例子的区分能力u 4 1 25 1 。不同的评价标准具有不同的优化偏向,如何 选择评价标准应根据特征子集选择的具体应用而定。现在被广泛采用的评 价函数主要有5 大类: 基于距离度量的评价函数( d i s t a n c em e a s u r e s ) 它通常也被称为可分离性( s e p a r a b i l i t y ) ,度量分歧( d i v e r g e n c e ) 度量或 区别性( d i s c r i m i n a t i o n ) 度量。各类样本之问可以分开是因为它们位于特征 空间中的不同区域,显然这些区域之间距离越大类别可分性就越大。对于 两类问题,w l 和m 中任一点与w 2 中的每一点都有一个距离,把所有这些距离 相加求平均,就可用这个均值代表两类之间的距离。在多维空问中有很多 种距离度量,典型的是欧氏距离,马氏距离等。 基于一致性度量的评价函数( c o n s i s t e n c ym e a s u r e s ) 这类度量方法是比较新的,并且近来受到了很多人的关注。这种方法 明显不同于其它的方法,因为它在选择特征子集时强烈依赖于训练集和最 小特征偏向的用法,最小特征偏向指的是尽可能少的特征的一致性假定。 这种方法的目的是找出满足可接受的不一致性比例的最小特征集合,其中 的不一致性比例可由用户来设置。一致性度量适用于离散特征,对连续特 征,需要首先进行离散化。而且由于采用一致性度量评估的特征选择算法 需要考虑各种特征子集组合下,各种特征的值的组合形式,因此对于高维 数据,其计算代价很高。 基于信息度量的评价函数( i n f o r m a t i o nm e a s u r e ) 信息测度准则是为了衡量后验概率分布的集中程度而规定的个定 量准则。信息论是信息测度准则的理论基础。从特征获取的角度来看,利 用具有最小不确定性的那些特征来进行分类是最有利的。该评价准则利用 信息论中互信息和熵的概念,计算待评估的特征一子集s 和输出类别c 之间 的互信息量,作为对特征子集优劣性的一个评价。常用的熵函数有s h a n n o n 熵、r e n y i 熵和条件熵等。 基于依赖性度量的评价函数( d e p e n d e n c em e a s u r e s ) 依赖性度量也称为相关性( c o r r e l a t i o n ) 度量,它是指从一个变量的值去 预测另外一个变量的值的能力。这个系数是一个分类的依赖性度量,它可 重庆邮电大学硕士论文第三章基于免疫算法的k d d c u p 9 9 特征子集选择 以被用作发现一个特征和某一类之间的相关性。如果特征j 和类c 之间的 相关性高于特征】,和类c 之问的相关性,则选择特征x 。当然,所有的基 于依赖性度量的评价函数又都可以分成基于距离和信息的度量的评价函 数。 基于分类准确率度量的评价函数( c l a s s i f i e re r r o rr a t em e a s u r e s ) 通常使用这种类型评价函数的方法也叫做包容法( w r a p p e rm e t h o d s ) 。 既然该文的目的是设计分类器,那么很自然地可以想到用分类器的分类准 确率作为标准,就是说,使分类器的分类准确率最大的那组特征就应当是 一组最好的特征。 3 2 3 特征选择算法伪代码 统一的特征选择算法模型【2 5 1 的描述如下: 输入:s :训练数据集,每个样本用特征集f 表示,i f i = n ,:评价函数 g s :特征子集产生方法 输出:羁删:最优特征子集 第一步:初始化: 瞩,= s t a r t ( f ) ; f s b t 2f s 嘶; 第二步:d ob e g i n ( 1 ) f s = s e a r c h ( g s ,s ,f ) ;生成特征子集集合 ( 2 ) i f ( d ( f s ) ,( 喁耐) ) 只乙= f s ; 评价并比较当前特征子集 e n du n t i ls t o p ( j ,f s ) ;满足终止条件 第三步:o u t p u t 喁积 给定数据集s ,且每个样本的特征维数为,算法从一个选定的特征子 集殿开始搜索,这时巩,得到是初始的特征子集,则瞩。盯= 巩,而在某 些情况下,初始点可能是特征子集的集合i 瞩,l l ,如遗传算法中,初始群 体中包含了多个个体,就需要概据判断准则,从中选择若干个较优子集, 用于以后的交叉、变异,然后概据一定的搜索策略在特征空间进行搜索。 概据选定的评价准则对每个产生的特征子集进行评价,并与以前最好的特 征子集进行比较,如果更好,则作为当前最好的子集。整个搜索过程一直 持续到满足特定的终止条件。算法输出的是相对于选定评价准则的最优特 征子集。 重庆邮电大学硕士论文第三章基于免疫算法的k d d c u p 9 9 特征子集选择 3 3 免疫算法及其优化算法 免疫算法是基于自然免疫系统的学习算法,是人工免疫系统研究的主 要内容之一。人工免疫系统是模仿自然免疫系统功能的一种智能方法,它 实现一种受生物免疫系统启发,通过学习外界物质的自然防御机理的学习 技术,提供噪声忍耐、无教师学习、自组织、记忆等进化学习机理,结合 了分类器、神经网络和机器推理等系统的一些优点,因此具有提供新颖的 解决问题方法的潜力。其研究成果涉及到控制、数据处理、优化学习、故 障诊断和网络入侵检测等许多领域【2 6 。2 9 1 。 3 3 1 免疫算法的生物原型 免疫系统对侵入机体的非己成分,如细胞、病毒和各种病原体( 以及发 生了突变的自身细胞,如癌细胞) 具有精确地识别、适度地应答和有效地排 除的能力,免疫系统的功能主要由免疫细胞完成,免疫细胞主要有淋巴细 胞( 包括t 淋巴细胞、b 淋巴细胞) 和巨噬细胞【3 0 】。 免疫系统可分为先天性免疫系统和适应性免疫系统,先天性免疫系统 是生物在种系发育和进化过程中逐渐建立起来的一系列天然防御功能,其 特点是与生俱有,能传给下一代,无特异性,对各种病原体都有一定的防 御功能。适应性免疫系统则是在个体生命过程中慢慢建立起来的,当免疫 系统与某种病原体产生“免疫初次响应”之后,能记住该病原体当再次遇 到它时,会产生“免疫再次响应”迅速而有效地消除该病原体。 从生物信息处理的角度来看,免疫系统具有以下的特性: 多样性 多样性是免疫系统的重要特征之一。免疫学的初步研究表明,通过细 胞的分裂和分化作用,体细胞超变异,抗体的可变区与不变区的基因重组 等方式,免疫系统可产生大量的不同抗体来抵御各种抗原,从而使免疫抗 体库具有丰富的多样性。 免疫自我调节 免疫系统具有维持免疫平衡的机制,能将免疫响应的强度限定在一定 水平上。通过对抗体的抑制和促进作用,能自我调节产生适当数量的必要 抗体。 免疫记忆特性 1 4 重庆邮电大学硕士论文 第三章基于免疫算法的k d d c u p 9 9 特征子集选择 产生抗体的小部分细胞会作为长寿的记忆细胞而被保存下来,当再次 遇到同类抗原,相应的记忆细胞会迅速激发而产生大量的抗体。这一特性 在医学临床中应用为接种疫苗,将某些传染病的低活性疫苗注射到未感染 者身上,刺激接受者产生抗体,从而产生对此类传染病的抵抗能力。 分布式系统 免疫系统是一个典型的分布式系统,由许多局部相互作用的免疫细胞 组成来完成对全局的免疫保护功能,并没有一个集中控制中心,因而也具 有容错功能,不会象集中控制系统那样因为控制中心的小失误,造成全局 功能的瘫痪。 动态适应特性 几百万年以来免疫系统都在与病原体不断竞争的过程中逐渐进化,这 种免疫系统与病原体的相互适应的过程具有明显的动态特性,两者相互竞 争共同进化。 多时间尺度进化系统 免疫系统的变化包括从只有几毫秒的亚分子事件到几分钟,几年的细 胞群体变化,以及需要无数代才能完成的改变,免疫系统实际上是一个随 环境改变而不断完善的多时间尺度进化系统。 3 3 2 常见的免疫优化算法 从广义的角度而言,凡是具有生物免疫系统独有的学习、记忆、识别 和动态平衡等功能的算法都可以称作免疫算法。从编码的形式上,算法大 体可以分为基于熵的免疫算法 3 l 】和基于距离的免疫算法【32 1 。在实际应用领 域方面,算法大体可分为免疫网络建模,免疫辨识和免疫优化三种形式【3 引。 免疫网络建模算法借鉴了生物免疫系统的分布式,自适应和动态平 衡功能,主要应用在机器人、控制工程等领域。包括j e r n e 提出独特性网络 模型,f a r m e r 将此模型应用于工程设计中【3 4 j ,1 9 9 6 年h u n t 提出的基于b 细 胞网络模型的免疫算法【3 引。 免疫辨识算法借鉴了生物免疫系统“自己”和“非己”的特殊识别功 能,主要应用在故障诊断,计算机病毒检测等领域。经典算法包括由f o r r e
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 电子竞技赛事裁判培训与考核指南
- 2026小学教资面试道法答辩高频考题题库
- 初中生物教资面试答辩易错题题库及解析
- 高中英语教资面试试讲高频考题题库
- 企业级数据丢失与恢复工具手册
- 2026事业单位计算机岗面试高频考题试卷及解析
- 索取售后服务评价结果的联系函(4篇)
- 初中英语教资面试答辩题库及参考答案
- 2026事业单位档案岗面试高频考题题库及答案
- 项目进度报告及预算调整通知函4篇
- 肾动脉栓塞介入术
- 《邮轮烹饪英语》-《邮轮烹饪英语》-Appendixes
- 魅力辽宁课件
- 天津市2021-2024年中考满分作文59篇
- 口腔正畸接诊流程技巧
- 军队职工抚恤管理办法
- GB/T 39542.3-2025技术制图活动铅笔第3部分:黑铅芯HB铅芯弯曲强度
- 班级历程回顾
- 《ERP软件实训》教学大纲
- 森林旅游学习通超星期末考试答案章节答案2024年
- 县乡教师选调进城考试-教育法律法规题库含答案(突破训练)
评论
0/150
提交评论