程爱辉 高茂庭

上海海事大学信息工程学院 上海 200135

0 引言

对入侵检测的研究早在20世纪80年代就开始了，但真正受到重视是随着Internet兴起之后。1980年，James Aderson提出了入侵检测的概念。入侵检测系统(Intrusion Detection System,IDS)通过监测和分析网络流量、系统审计记录等，来发现和判断入侵行为和正常行为，并发出入侵报警，提醒系统管理员采取相应的措施。

入侵检测技术主要分为两大类型：异常入侵检测和误用入侵检测。异常入侵检测试图用定量方式描述可接受的行为特征，用来区分非正常的或者潜在的入侵行为；误用入侵检测能直接检查不利的或不可接受的行为。也就是说，误用检测要建立的是入侵的行为模式，误用检测利用了已知的攻击模式，这样对已知的入侵模式识别率高，但其无法检测新的攻击行为；而异常检测建立的是正常行为模式；但正常模式定义十分复杂，导致误报率偏高。而目前来说，由于异常检测能够检测出未知的攻击，现在成为研究的热点。

入侵检测的技术已经在很多方面得到应用，支持向量机、神经网络、模糊集理论、遗传算法和免疫理论等都已经在入侵检测技术中应用。而本文采用了将聚类算法与最小二乘法支持向量机相结合的方法，利用聚类算法对入侵检测样本进行修剪，将靠近聚类中心的数据集合作为训练与测试的样本集，以减少算法的运行时间，提高算法效率。

1 LS-SVM

支持向量机(Support Vector Machine,SVM)是由Vapnik等人提出的一种基于结构风险最小化原则和样本本身的统计学习算法。它的学习策略是保持经验风险值固定而最小化置信范围。其原理是利用非线性函数把输入数据空间映射到高维特征空间，然后在此空间中构造分类间隔最大的最优分类超平面。

最小二乘法支持向量机(Least Squares Support Vector Machine,LS-SVM)是在标准支持向量机上的一种扩展，由J.A.K SuyKens和J. Vandewalle提出。它采用最小二乘线性系统误差平方和作为损失函数，将求解过程变成一组等式方程，加快了求解速度。

设训练样本 D = {(xk, yk)|k = 1 ,2,… ,N },其中，xk∈Rn为输入数据，yk∈R是输出类别。在ω空间(原始空间)中的最小二乘支持向量机分类问题可以描述为：

约束条件：

其中， w ,b,ek与SVM含义相同，γ表示惩罚参数。

定义拉格朗日函数：

其中，拉格朗日乘子kRα∈。对上式进行优化，并使用KKT条件：

上式可以化为矩阵方程：

其中

同时将Mercer条件带入到

因此，式(1)的分类问题通过式(5)和式(6)的线性问题得到最终解，而不是解二次规划问题。而核函数可以有多种，如高斯径向基核函数、多项式核函数、多层感知器核函数和线性核函数等。

2 选取有效的聚类中心集合

支持向量机具有完备的理论基础和较好的学习机能，但存在对噪声敏感问题，虽然模糊支持向量机的提出解决了这些问题，但是支持向量机是在大量的样本中进行寻找，支持向量机分类器会受到样本数量，维度等因素的影响。

聚类分析主要功能是挖掘空间中相近的数据。利用 K-最邻近法对数据集合进行有效剪枝，其聚类中心集合的选取算法原理如图1所示。

图1 聚类中心集合的原理图

如果两个类分别记为1p和2p，两个聚类中心集合分别表示为：

选取两类数据中距离 ( C1i, C1j)最近的两个聚类中心：

分别作为有效聚类中心集合1PC和2PC的第一个元素，如果一个聚类中心到1PC中的每个元素的距离平均值大于到2PC中每个元素的距离的平均值，则选取该聚类中心加入

如果 d ≥ 0 则 k = 1 ,将 Ckl加入到 P C2中，如果 d ＜ 0 则k= 2 ，将 Ckl加入到 P C1中。重复上面的过程，根据有效聚类中心的条件，直到所有聚类中心处理完毕，此时， P C1和PC2中的元素就是靠近边界的有效聚类中心集。把选择出来的数据集作为训练数据集。

3 基于聚类的LS-SVM的入侵检测模型

基于LS-SVM的入侵检测模型如图2所示，其中包括了数据采集，数据预处理，SVM训练，SVM检测，SVM支持向量库。

图2 基于LS-SVM的入侵检测模型图

模型的处理流程为：首先由网络数据捕获网络应用层中的数据流，通过分析网络应用层记录，提取出每条网络连接的特征信息(可以直接使用KDD数据集)，将数据信息提交给数据库预处理模块进行处理，得到 SVM的输入向量；如果出于训练状态，则训练SVM，否则出于测试状态，这两个的结果存入到数据库中，并根据设置执行相应的响应操作，如向用户发出警报等。

为了提高支持向量机的学习速度，将支持向量机与聚类算法相结合，用K-means聚类算法对训练数据进行聚类，获得每个聚类的聚类中心集合，然后将聚类中心集合作为 LS-SVM的训练样本进行训练与测试。其算法流程图如图3所示。

图3 算法流程图

4 数据预处理

本文选用的样本数据时KDD CUP99数据集，该数据集可分为两类：正常数据(normal)和入侵数据(拒绝服务攻击DoS，扫描与探测Probe，未经授权的远程访问R2L，对本地超级用户的非法访问U2R)。数据的记录都是从TCP/IP连接中提取出的 41个特征。由于有些特征是字符型，首先对字符变量处理，将字符型变化为数值型。其次，需要将数据进行归一化，而采用的归一化函数为：

其中p为输入的数据，maxp和minp为输入数据的最大值和最小值，np归一化后的数据。

训练数据采用kddcup.data_10_percent_corrected，这种包含了10%正常数据的数据集。

为了减少数据的计算量，采用奇异值分解(SVD)，这是一种正交矩阵分解法，将原有的数据集降低维度。由此，选取了41个特征中的18个，得到新的数据集。

利用K-最邻近法对数据集合进行有效剪枝，用最靠近判别边界的聚类中心结合作为有效的数据样本集合。

5 实验结果与分析

实验中采用LS-SVM1.5工具箱，该工具箱包含了四种核函数。通过测试发现RBF核函数效果更好，采用下面三种函数来定量描述入侵检测方法的检查性能，有如下的定义：

准确率(precision)= 分类正确的样本数/总的样本数；

误报率(False alarm rate)= 正常行为被误认为异常行为的样本数/正常样本总数；

漏报率(Omission rate)= 异常行为被误认为正常行为的样本数/异常样本总数；

实验结果如表1所示。

表1 基于聚类的LS-SVM入侵检测算法性能

从上面的实验结果分析来看，采用聚类方法和LS-SVM相结合的方法，训练效率和准确率都有了提高。

6 结束语

LS-SVM具有基于结构化风险，克服传统学习方法的过拟合、局部最小点的缺点。本文将其应用到入侵检测之中，同时采用到聚类方法对数据集合进行预处理，采用KDDCUP’99数据集进行实验，发现LS-SVM检测速度快，大大降低了处理时间，效果明显。但是LS-SVM失去了SVM特有的稀疏性的优点。如何克服LS-SVM 的缺点，提高准确率，以及如何对其改进，是下一步的研究重点。

[1]Sn-Yun Wu,Ester Yen Data mining-based intrusion detectors Expert Systems with Applications.2009.

[2]Mathias M.Adankon, Mohamed Cheriet Model selection for the LS-SVM. Application to handwriting recognition Pattern Recognition.2009.

[3]Vapnik V . The nature of statistical learning theory[M].New York: Springer Verlag 1995.

[4]http://www.esat.kuleuven.be/sista/lssvmlab.

[5]J.A.K. Suykens, J. Vandewalle, Least Squares Support Vector Machines, World Scientific, Singapore.2002.

[6]http://kdd.ics.uci.edu/databases/kddcup99/kkcup99.html.

[7]边肇祺,张学工.模式识别(第二版).清华大学出版社.2005.

[8]任勋益,王汝传,谢永娟.基于支持向量机和最小二乘支持向量机的入侵检测比较.计算机科学.2008.

[9]韩家炜等著,范明,孟小峰译.数据挖掘:概念与技术.机械工业出版社.2008.