（电路与系统专业论文）基于支持向量机与主动学习的入侵检测[电路与系统专业优秀论文].pdf

摘要 摘要 随着计算机及i n t e m e t 的日益普及，信息安全已经引起人们的广泛关注。入 侵检测是继传统安全防护措施之后出现的新技术。它通过相关技术手段及时地检 查出可能发生的入侵行为，从而增强了目标系统的安全保障能力。 基于机器学习的入侵检测技术是网络安全领域研究的热点和难点内容，它通 过对带有入侵信息的训练数据集学习，得到一个用于判别系统运行状态的检测模 型。但目前仍然存在着建立检测模型的训练样本数要求过多、训练样本标注代价 大等问题。 支持向量机是一种泛化能力很强的区分性模型，是目前模式识别领域的研究 热点。本文将支持向量机用于入侵检测，并且采用主动学习的方法，选择使用少 量高质量的训练样本进行建模从而高效地完成入侵检测任务。主要的研究内容如 下： 1 讨论了基于支持向量机的入侵检测模型的各环节，包括预处理，训练算 法，决策响应等。通过实验手段分析了核参数、惩罚系数及训练集规模对检测性 能的影响，并以实际数据反映出对建立检测模型起作用的训练样本仅占整个训练 集的很小比例。 2 深入研究了支持向量机主动学习算法中的初始训练集构建方法和样本选 择策略，并提出了一种改进的支持向量机主动学习算法，算法的改进主要体现在 两个方面：( 1 ) 将候选样本集进行核聚类，通过选择聚类中心样本构建初始训练 集。( 2 ) 以距离准则为基础，提出了一种概率样本选择策略作为待标注样本的选 择方法。 3 为解决入侵检测系统中存在着对建立检测模型所需数据要求高、训练样 本标注代价大的问题，提出了一种基于s v m 主动学习的入侵检测方法，并分析了 该方法的计算复杂度。入侵检测实验表明，将主动学习应用于s v m 检测模型，可 在保证检测性能的前提下，大大减少训练s v m 所需的标注样本数，从而降低建立 检测模型的标注代价。 关键词：入侵检测支持向量机主动学习统计学习理论样本复杂度核聚类 a b s t r a c t a b s t r a c t w i t ht h ep o p u l a r i t yo ft h ec o m p u t e ra n di n t e r n e t ，i n f o r m a t i o ns e c u r i t yh a s g a i n m o r ea n dm o r ef o c u s i n t r u s i o nd e t e c t i o ni sas u c c e e d i n gp r o t e c t i o nm e t h o da f t e r s o m et r a d i t i o n a l s e c u r i t ym e t h o d i tt r i e st of i n do u tc u r r e n ti n t r u s i o n 、i t hs o m e t e c h n i q u e s a sac o n s e q u e n t ，t h es a f e t yo ft h et a r g e ts y s t e mg e t sg r e a ti m p r o v e m e n t i n t r u s i o nd e t e c t i o nb a s e do nm a c h i n el e a r n i n gh a sb e e na na c t i v ea n dd i f f i c u i t r e s e a r c ht o p i ci nt h ef i e l do fn e t w o r k s e c u r i t y i te s t a b l i s ht h ed e t e c t i o nm o d e lt l l r o u g h g e t t i n gi n f o r m a t i o nf r o mt r a i n i n gd a t a , w h i c hi sf o rs e p a r a t i n gn o r m a ls t a t ef r o m i n t r u s i o ns t a t e h o w e v e r , t h e r es t i l le x i s ts o m eu n r e s o l v e da n ds c a r c e l ya d d r e s s e d p r o b l e m ss u c ha st h ed i f f i c u l t i e si no b t a i n i n ga d e q u a t eq u a l i f i e da t t a c kd a t af o rt h e c l a s s i f i e r st om o d e lt h ea t t a c kp a t t e r n s ，t h ed a t a a c q u i s i t i o nt a s ki sa l w a y st i m e c o n s u m i n ga n dg r e a t l yr e l i e so nt h ed o m a i ne x p e a s ，e t c s u p p o r tv e c t o rm a c h i n e si sad i s t i n g u i s hm o d e lw i t hg r e a tg e n e r a l i z a t i o na b i l i t y , a n di st h ep a r e mr e c o g n i t i o nr e s e a r c hf o c u sr e c e n t l y b a s e do nt h e s e ，w e p r o p o s ea l l i n t r u s i o nd e t e c t i o nm e t h o db a s e do ns v m m o r e o v e r , t h ea c t i v el e a r n i n gm e t h o dw a s i n t r o d u c e dt os e l e c tt h em o s t q u a l i f i e dd a t af o rt r a i n i n ga n dt h u sa s s i s ts v m e f f e c t i v e l yi nf u l f i l l i n gt h ei n t r u s i o nd e t e c t i o nt a s k t h em a i nc o n t e n to fs t u d v i n v o l v e di nt h i sp a p e ra sf e l l o w s ： 1 s t u d i e so nt h ev a r i o u sa s p e c to fi n t r u s i o nd e t e c t i o nb a s e do ns v m i n c l u d i n g p r e 。p r o c e s s i n g ，t r a i n i n ga l g o r i t h ma n dr e s p o n s e t h ei n f l u e n c eo fk e m e lf u n c t i o n p u b l i s hc o n s t a n ta n dt r a i n i n gs e ts i z eo nd e t e c t i o np e r f o r m a n c ew e r ea n a l y z e dt h r o u g h t h ee x p e r i m e n t a n dt h er e s u l t si n d i c a t et h a to n l yas m a l lf r a c t i o no ft r a i m n gs a m p l e s i sh e l p f u li ne s t a b l i s h i n gt h ed e t e c t i o nm o d e l 2 d i s c u s st h ei n i t i a lt r a i n i n gs e tc o n s t r u c t i o nm e t h o da n dq u e r yf u n c t i o ni ns v m a c t i v el e a r n i n g a n da l li m p r o v e ds v ma c t i v el e a r n i n ga l g o r i t h mw a sp r o p o s e d i t c o n s t r u c t st h ei n i t i a lt r a i n i n gs e tt h r o u g hk e m e l b a s e dc l u s t e r i n g ，w i t ht h es c h e m eo f p r o b a b i l i s t i cq u e r yb a s e do nt h ed i s t a n c ec r i t e r i aa st h er u l eo fa c t i v es a m p l es e l e c t i n g 3 i no r d e rt os o l v et h ed i f f i c u l t i e ss u c ha so b t a i n i n ga d e q u a t ea t t a c kd a t af o rt h e c l a s s i f i e r st om o d e lt h ea t t a c kp a t t e m sa n dc o s t l ys a m p l ea n n o t a t i o n , a ni n t r u s i o n d e t e c t i o nm e t h o db a s e do ns v ma c t i v el e a r n i n gw a sp r o p o s e d t h ee x p e r i m e n tr e s u l t s h o w st h a to u rm e t h o dc a nr e d u c et r a i n i n gs a m p l e su n d e rt h es a m e p e r f o r m a n c e k e yw o r d s ：i n t r u s i o nd e t e c t i o n ，s u p p o r tv e c t o rm a c h i n e s ，a c t i v el e a r n i n g ，s t a t i s t i c a l l e a r n i n gt h e o r y , s a m p l ec o m p l e x i t y , k e r n e l - b a s e dc l u s t e r i n g i i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除己特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 作者签名：盘至区蠢 签字日期： 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学 技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国 家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅，可以将学位论文编入有关数据库进行检索，可以采用影印、缩印 或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容 和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 d 么开口保密( 年) 爿 、一一 作者签名： 筮壹垒叠 签字日期： 第一章绪论 1 1 研究背景与意义 第一章绪论 i n t e r n e t 已经成为信息社会最为重要的基础设施之一，它深刻影响和改变着 我们的l ：作和生活方式。作为信息交流的工具，i n t e m e t 的开放性和互联性使得 资源的共享与信息的交流变得即高效又便捷。但同时它也被企图占有、偷窃、 甚至毁坏他人计算机信息系统资源的入侵者所利用，给联网的信息资源带来了 严重的安全威胁。 网络安全从其本质上来讲就是网络上的信息安全，包含了保密性、完整性 和可用性这3 个基本的安全目标( b i s h o p ，2 0 0 5 ) ： ( 1 ) 保密性。要求信息只能够被那些获得授权访问它的合法用户存取，防止 系统内信息的非法泄漏： ( 2 ) 完整性，包括数据的完整性( 即信息的内容) 和来源的完整性( 即数据的 来源，常称为认证) 。要求保证数据的可信度，防止非法的或者未经授权的数据 删改。 ( 3 ) 可用性。则意味着对信息或资源的期望使用能力要加以保障。即对授权 用户，系统应尽量避免系统资源被耗尽或服务被拒绝的情况出现。 为了保证网络上的信息安全，人们分别从理论和实践的角度来设计信息安 全系统。从_ 开始，人们就企图在安全计算的理论基础上先构筑某种安全的系 统模型，如著名的b e l l l a p a d u l a 安全操作系统模型、完整性模型等，然后利用 多种方法去实现。然而这些模型未必是绝对安全的模型，有的还仅仅是初步的 构想，具体的形式化设计、安全分析证明和实际系统的安全性测试还需要进一 步的研究和探讨。 继而，人们制定了一系列的安全准则和评测标准，用来构筑一个相对稳固 的安全系统，其中包括了著名的可信计算机安全评估准则( t c s e c ) ，俗称橘皮 书。它是由美国国防部国家计算机安全中心( n c s c ) 在1 9 8 5 年发布的，在信息 安全的发展史中具有里程碑意义。橘皮书中使用了可信计算机基础( t r u s t e d c o m p u t i n gb a s e ，t c b ) 这一概念，即计算机硬件与支持不可信应用及不可信用 第一章绪沦 户的操作系统的组合体。这个准则的发布对操作系统、数据库等方面的安全发 展起到了很大的推动作用。其后，针对越来越严重的网络安全问题以及保护各 种信息系统的安全需求，产生了“可适应网络安全模型”和“动态安全模型”。 其中利咕匕较具有代表性的就是p 2 d r 模型，如图1 1 所示。 0 ( 3 1 1 ) f - l ，2 ，3 ， 、 因此，满足上述条件且使| | w l l 2 最小的分类面就是最大间隔分类面( b o s e re t a j ，1 9 9 2 ) 。 综合以上，最大间隔分类面的求解问题即转化为如下的二次约束优化问题： 为此，我们可以应用l a g r a n g e 乘子法，定义如下的l a g r a n g e 函数： ( w ，口，6 ) ：i 导w w 一i 口，( y ，( w 为+ 6 ) 一1 ) ( 3 1 3 ) 其中，q 0 为l a g r a n g e 乘子，我们的问题就是对w 和b 求l a g r a n g e 函数的极 小值( c r i s t i a n i n i e ta l ，2 0 0 4 ) 。 把式( 3 1 3 ) 分别对w 和b 求偏微分并令它们等于0 ，就可以把原问题转化为 相应的对偶问题： m 觚( 口) ：圭q 一导圭y , y j a , a j ( 毛_ ) ，- l ，j = l s f 只哆= o ( 3 1 4 ) 珥0，i = 1 ，2 ，z 若口为最优解，则w = y i a , x i ，即最优分类面的权系数向量是训练样本的线 2 0 2 0 0 一 一6 ： + 川 噶 i 桫 一l 2 以 咖 姒 第= 市墓丁- 支持向世机的入侵检测 性组合。 这是一个不等式约束下二次函数最值问题，存在唯一解。且根据 k u h n t u c k e r 条件，这个优化问题的解须满足 q ( 只( w + b ) 一1 ) = 0 ，i = 1 ，2 ， ( 3 1 5 ) 这意味着仪仅是函数问隔为l 的输入样本点置，也就是最靠近超平而的点，对 应的口：非零。所有其他样本点对应的口? 为零( 蒋金山，2 0 0 5 ) 。因此在权系数向 量的表达式中，只有这些点包括在内，这就是成为支持向量的原因。 求解，卜述优化问题得到的最优分类判别函数为： ， f ( x ，“，b ) = s g n 只z ( 一x ) + 6 ( 3 1 6 ) f = i 由于非支持向量对应的口? 均为零，因此( 3 1 6 ) 式中的求和实际上只对支持向量 进行。 3 3 2 广义最大间隔分类面 最大问隔分类面是一个重要的概念，但在诸多实际中不能直接运用，这是 因为在特征数据中往往含有噪声，数据可能是近似线性可分的。我们需要一个 解决此类问题的方法：一般可以通过引入松弛变量，可以在条件： 。 耋三i 芝2 j + 尹 n 忉 毒0 ，= 1 ，3 ， 、 的约束下，获得一个广义的最大间隔分类面作为问题的解。其优化下列目标： ( w ，孝) = 知w l l 2 + c 专 ( 3 1 8 ) 广义最大间隔分类面的对偶问题与线性可分情况下几乎相同，只是公式( 3 1 4 ) 中的第二条约束条件变为 0 q c ( 3 1 9 ) 式( 3 1 7 ) 和式( 3 1 8 ) 中，考是非负的松弛变量，它是作为一个数据点和理想可 分情况下的偏差的一种惩罚。c 为某个指定的常数，实际上起控制对错分样本 2 l 第二：章基丁i 支持向鲑饥的入f 2 检测 惩罚的程度的作用，c 越大对错误的惩罚越重。 3 3 3 支持向量机 线性学习器能力有限，难以解决现实世界的复杂应用。换言之，就是系统 输入输f 之l u j 的函数关系通常不能由简单的线性函数纽合产生，往往需要研究 数据的更抽象特征。 核为此类问题提供了一条解决途径。对于非线性问题，可以将数据映射到 高维特征空刚，将其转化成该高维特征空间中的线性问题，并且线性学习器对 偶空| 日j 的表达方式使得这个步骤的隐式操作成为可能。如式( 3 1 6 ) 描述，分类 判别函数只涉及训练样本之问的内积运算，而式( 3 1 4 ) 也反映出优化问题的求 解也只涉及内积运算。 这样，我们可以通过选择恰当的核函数代替内积运算，可以隐式地将训练 数据非线性映射到高维空间，而无需知道变换的具体形式。根据泛函的有关理 论，只要一种核函数k ( _ ，一) 满足m e r c e r 条件，它就对应某一变换空间中的内 积k ( ，) = 伊( ) 伊( ) ，如定理3 1 所述( v a p n i k ，1 9 9 5 ) 。 定理3 1 ( m e r c e r ) ：要保证厶下的对称函数k ( ，) 能以正的系数口， 0 展 开成 k ( _ ，_ ) = 口，仍( 一) 仍( _ ) t = l ( e pk ( 葺，_ ) 描述了在某个特征空间中内积运算) 的充要条件是：对使得 ，9 2 ( 甜) 幽 0 成立。 因此，在线性判别函数中采用适当的核函数k ( 薯，) 代替内积运算就可以 实现某一非线性变换后的线性分类，而计算复杂度却没有随维数增加，此时的 优化函数为： 2 2 第三章基于支持向量机的入侵检测 而分类函数也变为： 形( 口) = q 一+ x y j y , a , a j k ( x j ，x j ) ( 3 2 0 ) i = i- j ，= i ， f ( x ，口，6 ) = s g n y , a ：k ( x i ，x ) + 6 ( 3 2 1 ) 构造式( 3 2 1 ) 类型的决策函数的学习机器就叫做支持向量机( 张学工，2 0 0 0 ) 。 支持向量机中不同的核函数将形成不同的算法，目前研究最多的核函数主 要有三类： ( 1 ) 多项式核函数 k ( ，x ) = ( 毛x ) + 1 r ( 2 ) 径向基核函数 鬈( 一，x ) = e x p ( 一gl ix , 一x1 1 2 ) ( 3 ) s i g m o i d 核函数 k ( 薯，力= t a n h ( r ( x f 力+ f ) 综合以上，支持向量机的基本思想可以概括为：首先利用满足m e r c e r 条件 的核函数将输入空间非线性映射到一个高维特征空间( 也称核空间) ，然后在核 空间构造一个最大间隔超平面作为分类面。与传统方法完全不同的是，统计学 习理论使用核的概念将输入空间升维，并且避免了算法的计算复杂性随维数增 加而上升。 3 3 4 支持向量机的训练算法 支持向量机具有着坚实的理论基础，表现出优异的泛化性能。但在支持向 量机的训练中，特别是针对大规模训练集，二次优化问题( q u a d r a t i c p r o g r a m m i n g ，q p ) 的求解制约着s v m 在实际中的进一步应用。 经典的二次优化算法在求解s v m 问题时难以令人满意，这主要有两个原 因：第一，s v m 需要计算和存储核函数矩阵，所耗费的空间与样本数成平方关 系。当样本较多时，会消耗掉大量的内存空间。第二，s v m 在求解其优化问题 时，需要进行大量的矩阵迭代运算。 2 3 第三章基于支持向量机的入侵检测 近年来，人们针对s v m 二次优化问题的特殊之处，提出了许多新算法， 如分块法、分解法及s m o 算法，其共同思想都是循环迭代，将原问题分解成 为若干子问题，按照某种迭代策略，通过反复求解子问题，最终使结果收敛到 原问题的最优解。 3 3 4 1 分块法及分解技术 c h u n k i n g 分块算法依据这样的事实：支持向量机的分类超平面仅仅由支持 向量构建，而与非支持向量没有关系。其计算方法如下：将s v m 的二次优化 问题分解为一系列变量数较少的子问题，重复求解子问题并记录下解中的支持 向量，将其加入到新的子问题中。每个子问题都以上次的解为初值，直至所有 的子问题都求解完成( c o r t e sa n dv a p n i k ，1 9 9 5 ) 。 分解法也采用了类似的求解算法，但它克服了分块法那种求解规模随支持 向量增加而增加的的情形，其计算方法如下：将训练集分为工作集和非工作集， 并且将工作集的规模固定某个常数g ，这样将原优化问题转化为一系列的小规 模优化问题( o s u n ae ta l ，1 9 9 7 ) 。如何选择工作集是该方法的关键，一般根据 k k t 条件背离程度选择工作集，也可采用可行方向法选择工作集( j o a c h i m s ， 1 9 9 9 ) 3 。3 。4 2s m 0 算法 为了避免分解法中重复调用优化代码而造成的额外开销，s m o 算法将工作 集大小q 限定为2 ，以获得二次优化子问题的解析解。该算法含有一个两层嵌 套循环过程，在外环中采用启发式方法寻找违背k k t 最优条件的样本，在内环 中对该样本的相应l a g r a n g e 乘子进行分析求解，完成一次优化计算。不断重复 此过程，直至所有样本都满足k k t 条件( p l a t t ，1 9 9 9 ) 。 s m o 算法将工作样本集的规模减少为两个，增加了算法的迭代次数，但避 免了在每次迭代中调用二次优化求解代码，总的计算速度反而有所上升。并且， s m o 算法也无须存储大矩阵，节约了大量的存储单元。 3 4 支持向量机应用于入侵检测 基于支持向量机的入侵检测系统，以收集、观测到网络数据( 或操作系统的 2 4 第三章基于支持向量机的入侵检测 审计数据) 为训练样本，从中寻找潜在的规律，从而建立能检测出异常行为模式 的区分性模型。 图3 3 基于s v m 的入侵检测系统结构图 基于支持向量机的入侵检测系统，主要由数据采集模块，预处理模块，支 持向量机分类器和决策响应模块组成，如图3 3 所示。 ( 1 ) 数据采集模块主要负责收集含有入侵信息的数据，比如网络数据包、 系统日志，程序执行中的异常行为以及系统目录的异常变化信息。 ( 2 ) 预处理器将采集得到数据转换成支持向量机能够处理的数字特征向量， 这部分的工作包括数值化、规范化和特征提取。 数值化：将原始数据中的非数值特征赋予数值标号，从而能以离散的数值 表示该特征的取值。 规范化：从式( 3 2 1 ) 及常见的r b f 核、多项式核、s i g m o i d 核可以看出，较 大取值区间上的属性相比较小取值区间的属性对计算的影响更大。为防止较小 取值区间上属性所提供的分类信息被较大取值区间上的属性所提供的分类信息 所“淹没 ，数据规范化尤为重要。具体的规范化方法包括以下两种。 方法1 ：首先计算出每维属性的均值和标准偏差， 胱a n ( x j ) 2 吉善# ( 3 2 2 ) s 幻 d a r d ( x j ) = y 1 窆闰( x _ m e a n ( x j ) ) 2 ( 3 1 2 3 ) 其中，彩代表样本f 中的第，维属性，疗代表样本总数。 然后，我们将样本如下转化产生新的属性值。 胎峭= 嚣s t a n a a r a ( 3 2 4 ) i x 7i 2 5 第三章基于支持向量机的入侵检测 方法2 ：首先计算出每维属性的最大值和最小值 m a x ( x 7 ) = v