焦作大学范文参考

所属栏目：焦作大学学报
发布时间：2014-08-21 14:57:32 更新时间：2014-08-21 14:27:32

　　随着计算机软硬件的迅猛发展，计算机网络之上的应用日益广泛，在享受互联网带来的各种便利的同时，人们面临着更严重的网络入侵的威胁。网络上随处可见的黑客软件使得入侵行为与日俱增，统计数据表明，每年网络入侵事件的数量呈指数形式增长。与此同时，网络入侵更显示出多样性，智能性，隐蔽性等特点，这使得仅靠传统的杀毒软件、防火墙等静态防御技术无法保证网络的安全。

　　摘要：提出了一种聚类学习与增量SVM训练相结合的的入侵检测方法，采用聚类分析、样本修剪与增量学习相结合的方式，通过聚合相似的训练样本以支持多类别分类，通过去除相似的样本而只取其代表点，从而减少参加训练的样本数量，提高学习效率，同时采用基于广义KKT判决的增量学习方法，有效改善了多类别入侵检测场合下样本数据集过于庞大，学习速度过慢且难以保障SVM入侵检测能力持续优化的问题。

　　关键词：焦作大学毕业论文,支持向量机,入侵检测,聚类,非线性分类

　　An Novel Proposal For Intrusion Detections Based on Clustering Analysis and Increamental Support Vector Machine

　　WANG Ya-bin

　　(Jiangsu Tcnet Technology Co.， LTD.， Suzhou 215000，China)

　　Abstract： An novel incremental SVM intrusion detection algorithm based on Clustering Learning is proposed in this paper. By using the clustring analysis and data pruning， the purpose of efficient simplification and multi-classification for trainning samples is achieved. An improved algorithm of incremental SVM trainning based on generalized KKT condition is also presented. Our simulation result shows that this method could effectively improve the trainning and classification speed caused by datasets updating， while at the same time the classification precision is guaranteed.

　　Key words： SVM; Intrusion Detection; Clustering; non-Linear Classification

　　入侵检测系统(Intrusin Detection System，IDS)与传统的防火墙相比，是一种积极主动的安全防护技术，提供了对内部攻击、外部攻击和误操作的实时保护。它能很好的弥补防火墙的不足，可以对系统中未授权访问或异常现象、活动与时间进行审计、追踪、识别和检验的安全过程。它可以识别出系统是否被入侵，从而做出及时的反应，切断网络连接、记录时间和报警，提醒系统管理员采取相应的措施，避免系统受到进一步的侵害。

　　入侵检测问题实质上可被视为一个区分入侵行为与正常行为的分类问题。这一问题在机器学习、最优化等领域获得了深入研究。其中，基于VC维理论和风险最小化原理的支持向量机(Support Vector Machine)技术日益受到了人们的关注，SVM在解决小样本、非线性及高维模式识别问题中具有的特有优势，使得其非常适合用以解决入侵检测分类问题。然而在实际应用中，面对层出不穷的海量入侵行为，如何在有效保障SVM训练效率、以便及时响应入侵事件的同时，实现其学习、推广能力的持续强化与提升，以满足快速应对新兴威胁的需要，其目前已成为SVM应用于入侵检测实用场合所必须解决的两个关键问题。

　　针对上述问题，目前学术界已进行了大量研究，Mukkamala等人[1]利用SVM技术实现了入侵检测，并与神经网络方法进行了比较，获得了良好结果;Syed等[2]对样本支持向量集进行了分析，首次提出一种SVM增量学习算法;段丹青等[3]提出了一种基于粗糙集与SVM的入侵检测算法，有效地解决了训练样本降维问题;于静等[4]将 PCA主成分分析应用于特征样本处理中，以提升SVM训练效率;张永俊等[5]则采用了一种简化二进制差别矩阵与云模型的方式，来对SVM训练样本进行增量式属性约简。这些工作均在不同程度上改善了SVM应用于入侵检测场合中的学习、分类效率。

　　本文提出了一种聚类学习与增量SVM训练相结合的的入侵检测方法，采用聚类分析、样本修剪与增量学习相结合的方式，通过聚合相似的训练样本以支持多类别分类，通过去除相似的样本而只取其代表点，从而减少参加训练的样本数量，提高学习效率，同时采用基于广义KKT判决的增量学习方法，从而有效改善了多类别入侵检测场合下样本数据集过于庞大，学习速度过慢且难以保障SVM入侵检测能力持续优化的问题。

　　1 支持向量机与聚类分析简介

　　1.1 支持向量机模型

　　假设已知训练样本[{xi，yi}，yi=±1，i=1，2，...n]，其中xi为样本的特征向量输入，yi为分类结果，n为样本数。当[yi=1]时为正类，即正常;[yi=-1]时为负类，即异常。SVM方法就是通过寻求一个最优分类超平面[ω，x+b=0]，使得其对于所有训练样本满足：　　[yi[ω，x+b]-1]

　　其中，[ω]为输入数据的权重矢量，b为分类超平面的偏置。上式可转化为一个二次凸优化问题，该问题表述如下：

　　其中，C为惩罚因子，[ξi]为松弛因子，利用拉格朗日乘数法对上述问题进行最优化求解，可将上式转换为对偶问题：

　　式中[αi]为拉格朗日算子。在针对上式优化问题的解中，存在部分[αi]不为0，其所对应的训练样本即为“支持向量”。同时，上式将[ω]的最优化求取问题，转换为了[α]的参数优化问题，并可通过[α]解得[ω]为：

　　在式对偶问题求解的基础上，可得到SVM线性判别函数为：

　　对于线性不可分的数据，可以使用非线性映射函数[?]将输入数据从原低维空间变换到高维特征空间，使得原空间中线性不可分的样本数据变得高维线性可分，然后再求其最优决策平面。故有扩展后的广义SVM判决函数为：

　　式中的K被称之为与[?]所对应的核函数。

　　1.2 广义KKT条件

　　针对式()对偶问题的最优化问题求解需要用到最优性KKT条件(Karush-Kuhn-Tucker)，该条件是SVM凸二次规划获得全局最优解的充分必要条件，其表述如下：

　　对于所有i，以下条件成立：

　　[yif(xi)1， ai=0yif(xi)=1， 0　　由上述条件可看出，[ai=0]对应的样本点(xi，yi)是被正确分开的点，当[0　　针对一个已有的SVM分类器，可证明[6]，如果新增样本不违背KKT条件，则加入这个样本将不会对当前分类器产生影响，而违背KTT条件的样本参与训练的话将有可能改变原问题的解。同时还可证明[7]，当新增样本中存在违背KKT条件的样本时，原有的非支持向量有可能转化成新的支持向量。上述结论为基于新增样本的增量SVM训练提供了基础依据。

　　1.3 聚类分析方法

　　聚类分析(Clustering)是一种将样本集合粗分组成为由类似的对象组成的多个类的分析过程。目前已经存在着大量的聚类算法[8]，算法的选择多取决于数据类型、聚类目的和应用范围，其典型聚类算法一般可分为基于划分的方法、基于层次的方法、基于网格的方法、基于密度的方法及基于模型的方法等。

　　K-Means算法是其中应用得最为广泛的一种划分方法。其核心思想在于：首先从样本数据集中随机选取k个样本作为k个类的初始中心，剩余样本点根据最小距离原则，分配给与之距离最近的那个中心点，然后计算每个类的平均值作为新的聚类中心点，反复迭代以上过程，直至平方误差准则函数收敛为止。平方误差准则函数被定义为：

　　其中，E为样本空间中所有样本的平方误差之和，x为所有属于类Ci的样本，mi是类Ci中所有样本的平均值。

　　值得指出的是，K-Means算法较大依赖于对初始聚类中心点的选取，不同中心点的初始选取有可能会导致不同的聚类结果及聚类效率，同时有可能使得算法终止于局部最优解。

　　2 基于聚类的多分类SVM入侵检测方法

　　2.1 整体模型框架

　　考虑到在实际应用中，入侵检测系统不仅需要判断异常行为是否存在，同时还需要判断具体异常行为的类属与所属类别异常行为的普遍性，该文提出了一种基于聚类分析的多分类SVM入侵检测方法，其所采用的处理步骤如下：

　　1) 首先针对训练样本集中的样本进行异构数据处理，将其属性特征进行数据值化与归一化

　　2) 采用改进型的密度聚类及K-Means聚类方法，消除样本中的噪声点和干扰点，同时划分为m个聚类，每一聚类代表着一类具有相似特征的网络行为;

　　3) 针对每个聚类样本集合，计算其正负类别的最相邻样本集合，并进行相应的样本裁剪，以在保障学习所得分类器精度的同时，减少样本冗余，提高分类器学习效率;

　　4) 针对每一聚类，将其最相邻样本集合作为训练样本进行学习，为每一聚类均生成一个SVM分类器，用以判别本聚类中的异常行为;

　　5) 针对后继新增的已标记样本数据，首先根据密度与特征距离判断其所属聚类，选择相应的SVM分类器，然后以广义KKT条件为增量学习依据，分析新增样本对当前聚类分类器的影响，并实现对已有分类器的更新修正;

　　6) 对于持续输入的测试样本数据，将首先判断其属于哪个聚类，然后再选用相应的SVM分类器进行分类，最终得出多类别的入侵检测结果判定。　　2.2 改进型K-Means样本聚类

　　本文采用了一种基于节点分布的判断方式进行聚类初始中心点的选取，继而在选取中心点基础上进行相应的K-Means聚类。

　　设当前样本集合M中有N个样本点，其中每一样本点x可用n维向量表示为(x1，x2，….xn)，其中n为特征属性的维度;则可定义样本点[xi]与[xj]之间的欧式空间距离为：

　　定义样本点[xi]的分布密度为DS([xi])，则有：

　　其中[num[D(xi)　　基于上述定义，则有改进型K-Means聚类算法步骤如下：

　　1) 选取样本的密度半径r=mean(x)/N0.18，其中mean(x)为样本集合中所有样本距离的平均值;N0.18为一可调经验阈值;

　　2) 针对全体样本计算其分布密度，然后计算所有样本密度平均，并将每一个大于平均值的样本点放在备选集合S中;

　　3) 挑拣S中密度最大的样本作为初始聚类中心点c1，将其从S中取出，并放入初始聚类中心点集合T中;

　　4) 从S中寻找下一个初始聚类中心点c2，且其需满足如下条件：[D(c2，c1)>τ]，且其密度尽可能的大;其中[τ]取整个样本空间最大样本距离的1/m，m为聚类个数;将c2从S中移出，并放入初始聚类中心点集合T;

　　5) 重复4)，直至找到m个初始聚类中心点为止。

　　6) 设初始聚类中心点为{c1，c2，…cm}，t为当前的聚类迭代步骤;

　　7) 将所有待分类的样本逐个按“离中心点距离最近”的原则划分至m个类中;

　　8) 重新计算m个聚类的中心点;以当前聚类中所有样本的几何平均值作为新的聚类中心;

　　9) 如对于m个聚类中心点在重新计算前后均未发生变化，则算法终止;否则转至7)进一步迭代，直至所有聚类中心点收敛为止;

　　10) 输出m个聚类节点集合作为聚类处理的结果。

　　与通常K-Means算法不同，以上算法采用了一种基于样本节点分布的确定性初始中心点选取方法，通过根据样本密度和间距来择优选取初始中心点，从而以启发式方式避免了传统K-Means算法选取初始中心点的过度随机性，进而有效保障了后继聚类分析结果的质量。

　　2.3 最相邻样本集合裁剪

　　本文采用一种基于最相邻样本集合的裁剪方式，以减少样本集合冗余，提升学习效率。

　　考虑两类别分类场合，设x+为正类样本，而x-则为样本集中的负类样本，不妨设，，则两者之间的欧式空间距离为：

　　我们可针对正类中每一个样本x'+，计算出其与所有负类样本x'-之间的距离，然后标记出其中距离最小的那一个。由这些距离最小的负类样本所构成的集合被称之为正类的最相邻样本集合M+。反过来，我们也可针对负类所属样本，求取出其所对应的最相邻样本集合M-，且其集合中的每一个样本均属于正类。

　　根据SVM最优分隔界面的性质可知，在两类别分类场合下，其SVM所对应的支撑向量必包含在M+ ∪ M-中。即，在进行SVM训练时，我们可排除那些未被包含在最相邻样本集合中的节点，而不会对所得的SVM分类器产生任何影响，这是因为这些节点不可能位于SVM最优分隔界面之上，所以它们不可能成为支撑向量。通过上述裁剪方式，可以极大地压缩参与后继SVM训练的样本数据，从而显著提高训练性能。

　　值得指出的是，在增量学习场合下，非最相邻样本数据并没有被完全删除，而仅只是将其从当前训练集合中排除。这主要是因为，尽管这些样本在当前学习阶段中不可能成为支撑向量，但这却并不意味着在后继增量学习阶段中，其也不可能成为支撑向量。因此，为使得上述裁剪方法能适用于增量SVM学习场合，我们采取了一种以空间换时间的策略，即保存下聚类中所有样本与样本之间的距离，以便在每个增量学习阶段中快速引用并排序，进而快速地裁剪出当前学习阶段所需的实际训练样本集合。实际应用中，尽管上述策略将不可避免地导致内存等资源占用的增长，然而在已事先划分聚类的场合下，这一影响被限制在单个聚类范围之内，因而可以极大地减轻。综合而言，我们认为这种存储空间与训练性能的折衷是值得的。

　　2.4 增量SVM训练更新

　　本文采取了一种基于最相邻样本集合的增量学习方式，来更新聚类对应的SVM分类器。

　　设聚类A初始训练样本集E及其训练所得的分类器为V;属于聚类A的新增样本集E’及其训练所得的分类器为V’。令，其中为违背V的广义KKT条件的样本集，为满足V的广义KKT条件的样本集;与之类似的，令，其中为违背V’的广义KKT条件的样本集，为满足V’的广义KKT条件的样本集。其算法步骤如下：　　1) 检查E’中是否存在违背V的广义KKT条件的样本，如无，则算法终止，输出V为增量训练结果;如有，则将E’划分为与;

　　2) 计算E’中正负类的最相邻集合，并基于此计算其分类器V’;

　　3) 检测E中是否存在违背V’的广义KKT条件样本，如无，算法停止，输出V’为增量训练结果;如有，则将E划分为与;

　　4) 合并、以及E、E’的支撑向量集，针对其合集进行正负类最相邻集合裁剪，继而对该合并集合进行训练，并输出其分类器为增量学习结果。

　　3 实验与分析

　　本文采用了KDDCup99测试数据集[9]对上述方法进行了验证，其样本共计41个特征属性，共计DOS(拒绝服务攻击)、R2L(远程权限获取)、U2R(用户权限提升攻击)、Probing(端口及漏洞扫描)等4大类攻击行为。

　　仿真实验采用Libsvm[10]与C++实现，其采用了RBF核函数，其中取0.98。整个实现采用了交叉对比的方式，其比较对象为一般的全样本SVM学习器。其实现结果如下表所示。

　　表1 一般SVM算法仿真实验结果

　　[训练样本数\&训练时间(s)\&测试时间(ms)\&分类准确度(%)\&50\&0.094\&0.994\&99.21\&1000\&0.297\&0.1219\&99.75\&20000\&8.437\&0.3047\&99.95\&100000\&232.141\&0.5766\&99.98\&]

　　表2 基于聚类分析的增量支撑向量机仿真实验结果

　　[训练样本数\&聚类数量\&训练时间(s)\& 测试时间(ms)\&分类准确度(%)\&100000\&10\&29.763\&0.1206\&99.946\&100000\&50\&44.721\&0.0832\&99.958\&100000\&100\&126.813\&0.0921\&99.971\&]

　　由表可见，在训练样本数为100000的场合下，该文算法的训练时间与测试时间均大大低于一般SVM全量学习算法，与此同时，其分类准确率在聚类数量足够的情况下，也基本达到了标准SVM算法同等的水平。同时还值得指出的是，随着聚类数量的增多，该文算法所得分类检测率是递增的，这与我们的直觉是相符的。上述实验充分说明了本文方法在大训练样本量场景下的有效性与适用性。

　　4 结论与下一步工作

　　本文提出了一种基于聚类分析的增量SVM相结合的的多类型入侵检测学习方法，该方法通过采用了一种基于样本分布的改

　　(下转第4432页)

　　(上接第4420页)

　　进K-Means聚类方式来针对训练样本进行归类，同时提出了一种基于最相邻样本集合的训练样本裁剪方法，并将上述裁剪方式与广义KKT条件判定相结合，提出了一个多类别增量SVM学习方法。分析与实验表明，上述方法可显著改善大训练样本量下SVM分类器训练时间长、学习速度慢的问题，同时有效保障了系统检测能力的持续优化与更新。

　　下一步工作包括：进一步评估新增样本对聚类分析结果的影响，以进一步提升多类别SVM训练、检测性能;尝试结合采用超球、软边界等其他裁剪算法，优化最相邻样本集合的样本拣选与数据存储，在降低内存消耗的同时保持其较高的学习检测效率。

　　参考文献：

　　[1] Mukkamala S，Janowski G.Identifying important features for intrusion detection using support vector machines and neural networks[J].Proceedings of Applications and the Internet， 2003， 14(4).

　　[2] Syed N， Liu H. Sung K Incremental Learning with Support Vector Machines[J].Proceedings of IJCAI Conference， Sweden， 2000.

　　[3] 段丹青.入侵检测算法及关键技术[D].长沙：中南大学学位论文， 2007.

　　[4] 于静，王辉.改进支持向量机在网络入侵中的应用[J].微电子学与计算机， 2012， 29(3).

　　[5] 张永俊，牟琦，毕孝儒.基于云模型的增量SVM入侵检测方法[J].计算机应用与软件， 2013， 30(3).

　　[6] 周伟达，张莉，焦李成.支撑矢量机推广能力分析[J].电子学报， 200l：590-594.

　　[7] 王晓丹，郑春颖，吴崇明. 一种新的SVM对等增量学习算法[J].计算机应用， 2006， 26 (10).

　　[8] 范明，孟小峰.数据挖掘概念与技术[M].北京：机械工业出版社， 2008.