基于稀疏编码和SVM的协同入侵检测*

崔 振 ，陈柏生

(1.华侨大学 计算机科学与技术学院，福建 厦门361021；2.中国科学院 计算技术研究所，北京100190)

将所有的网络行为分成正常行为和异常行为两类，这样入侵检测问题就可以转化成模式分类问题。入侵检测的关键是正常和异常行为模式库的建立。目前常用的入侵检测方法有基于贝叶斯推理的入侵检测[1]、基于模式匹配的入侵检测[2]、基于神经网络的入侵检测[3]和基于数据挖掘的入侵检测[4]，以上方法对数据的要求较高或需要的数据量较大。支持向量机是建立在统计学习理论上的一种新的机器学习方法，由于其在小样本、高维、非线性等方面的优势和较好的推广能力，已经在入侵检测中得到应用[5]。总体上，支持向量机可分为误用检测和异常检测两大类，误用检测准确度高，但难以应对未知攻击；异常检测则常常面临误报率过高的问题。另外，如何应对大规模的高速数据流检测、如何实现在线学习、如何减少或消除噪声数据的影响，是入侵检测系统面临的主要挑战。

近年来，稀疏表示相关理论已成为研究的热点。常用的信号分解方式通常是非冗余的正交变换，如离散余弦变换、小波变换等。这类方式缺乏灵活性，并且许多混合信号在单一的正交基变换中无法得到有效的稀疏表示。基于超完备字典的信号稀疏分解是一种新的信号表示理论，它采用冗余原子来构造字典，而不是采用传统的正交基，这样使字典更富有表现力，同时为信号自适应的稀疏扩展提供了空间。通过这种超完备字典把数据变换到另一空间，即进行稀疏编码，会带来更好的分类效果[6]，原因是稀疏表示系数从某种意义上带有一定的判别信息[7]。稀疏表示已应用于一些具体的领域:学习非参数化字典来进行图像超分辨率或图像重建[8]；利用稀疏表示系数重构图像，用重构误差进行(遮挡)人脸识别[7]等。这些应用领域主要集中在图像处理和压缩感知中。

本文将稀疏编码方法应用于入侵检测。在过完备词典学习和编码的过程中加入l1范数约束，同时最小化重构残差和非零个数，在去除一定噪声的同时也促使映射的特征本身具有稀疏性。这种稀疏性使得学习到的系数特征拥有更好的判别性，即学习后的特征在分类空间更易于划分，同时后端结合强大的分类器——支持向量机来进行入侵检测。实验中，本文所提的方法与直接用SVM的方法进行了比较，显示了稀疏映射的特征更富有表示力和判别力，验证了所提方法的有效性。

1 稀疏表示理论

1.1 词典学习

构建字典归纳起来有两种方法[9]：(1)基于数据模型建立稀疏字典，如一些小波函数；(2)从训练集中学习一个字典。本文采用后一种方法构建字典。由于数据的规模很大，采用较流行的字典训练方法——SVD分解来迭代构建词典，即 K-SVD[10]方法。

K-SVD算法由K-均值聚类算法推广而来，是一种迭代方法，一方面用当前字典对训练集信号进行稀疏编码，另一方面更新字典的原子以期使得字典更好地表示信号。这种联合的更新加速了算法的收敛。K-SVD算法是灵活的，可以和任何一种追踪算法一起工作。K-SVD的目标函数：

其中，Y=(y1，y2， …，yN)，yi∈Rn是第 i个样本，D=[d1，d2，…，dk]∈Rn×K是词典，K 是原子数量，X 是稀疏系数，||·||0是l0范数。

K-SVD算法分为两步:

(1)固定D，更新稀疏系数X。可以通过任何稀疏编码算法求解，如 LARS、OMP、BP等。

(2)同时更新D和X。采用SVD分解用最大奇异值对应的特征向量来更新字典。记字典D第k列为dk，对应的稀疏系数为xiR(X的第 i行)，式(1)可表示为：

然后对 Ek应用 SVD 分解：Ek=U△V。 令 dk=U(：，1)，=△(1，1)×V(：，1)T。

重复上述两步到规定的迭代次数为止。

1.2 稀疏求解

给定超完备字典 D∈Rn×K，其中 n＜K。 测试样本 y∈Rn，把测试样本 y表示成字典原子项{di}(i=1，…，m)的稀疏线性组合，将目标形式化为如下的目标函数：

式(3)可在多项式时间内求解。

目前，求解超完备稀疏表示最优化问题的稀疏优化方法主要有贪婪算法、全局优化算法以及其他算法[11]。贪婪算法通过选取字典中与信号最匹配的项，迭代地构造出信号的逼近。全局优化方法是指在满足一定的优化条件下，使得某个特殊的目标函数最小，典型的目标函数是凸函数，并且任何局部最小值也是全局最小值。

本文使用的是Efron等提出的LARS变量选取方法[12]。算法大致描述如下：

首先稀疏系数设置为0。然后在词典里查找与响应变量相关最大的输入变量，在响应变量的投影方向选取最大的步长，使得其余的某一个输入变量与当前的输入变量有同样的相关性（在当前的重构残差情况下）。这时候选取了两个变量，由这两个变量组成一个子空间，重构残差在子空间上的投影方向继续前进直到第三个变量进入最相关的集合。这样持续下去直到设定的阈值为止。

LARS计算的好处是LARS路径逐点线性，LARS的目标函数值是逐步下降的。

2 算法流程

至此，给出基于稀疏编码和SVM(简记为SR_SVM)的入侵检测算法流程：

(1)数据预处理

首先把符号类型数值化，然后用下式标准化：Zji=(xji-m(xi))/σ(xi)。 其 中 ，m(xi)表 示 第 i个 属 性 的 平 均值，σ(xi)为第 i个属性的标准差，xji表示第 j条记录的第i个属性，Zji为标准化后的属性值。然后计算标准化度量值，最后把每条记录对应向量单位化，以便于训练字典。

(2)训练字典

设训练集为 Train，对 Train用 K-SVD算法[10]训练，超完备字典为 D，D∈Rn×K，m为数据记录维数，n为词典原子项数。

(3)对训练集求解稀疏表示

对集合 Train中每个输入的训练样本 y，y∈Rn使用LARS算法[12]最小化 l1范数，求解 y相应于 D的稀疏表示x∈RK，并加入到集合 Train_SR。

(4)构建支持向量机模型

使用集合Train_SR的数据训练，构建支持向量机模型用于分类检测。

(5)决策分类

设测试集为Test，对每个测试样本y∈Rn使用式(3)最小化l1范数，求解y相应于D的稀疏表示x∈RK。使用多类支持向量机对x决策类别作为测试样本y的类别。

3 实验与分析

实验采用入侵检测领域共同认可及广泛使用的基准评测数据集——KDD Cup 1999进行测试。

3.1 实验数据及预处理

实验中使用的训练集和测试集分别从KDD99数据集10%的训练子集和测试子集中抽取。为了检验分类器模型的泛化能力，训练集包含22种攻击，测试集包含39种攻击，训练集中未出现的17种攻击占到整个测试集的10%左右。

KDD Cup 1999中涉及3种协议的数据，分别是TCP、UDP和ICMP。为了更精确地构建冗余字典，加快训练速度，实现并行检测，构建3个检测代理，分别是TCP检测代理、UDP检测代理和ICMP检测代理(在实际应用中可能拥有更多种类的数据流，可以进行扩展)。根据网络数据流的特点，可以把待检测数据流进行分类(下面分为 3类：TCP、UDP和 ICMP，在实际应用中可以扩展)，这样做的前提是假设一次入侵行为不会使用多种网络协议进行通信[13]。针对不同的网络协议，经数据预处理后，就可以去掉一些冗余的属性（在某协议下有些属性的取值是完全相同的）。最后TCP选取了37个属性，UDP选取了20个，ICMP选取了16个。

3.2 对比实验

实验参数设置：TCP、UDP和ICMP字典的原子项数分别为60、40和 40；K-SVD算法迭代20次，稀疏比率约为10%；SVM采用RBF核函数。

3.2.1协同检测实验

训练集和测试集抽取情况如表1所示。

表1 数据集抽取情况

为了说明算法的有效性，将SR_SVM与SVM进行了对比。实验结果如表2所示，可以看到，基于稀疏表示的入侵检测对三种代理都有较高的检测率和较低的误报率。

表2 协同检测实验结果

另外一个值得注意的现象是UDP数据集和ICMP数据集属于严重不平衡数据集。对于支持向量机来说，这种情况会影响支持向量机超平面的建立。而SR_SVM对于不平衡数据集有较好的鲁棒性。

3.2.2 不平衡数据实验

为了进一步测试SR_SVM的鲁棒性，在TCP数据集上进行不平衡数据集的测验。

测试集不变，继续使用表1中对于TCP抽取的数据集，训练集分6种情况随机抽取，如表3所示。实验结果见表4。从表4可以看到，当数据失衡后，相比于数据平衡的情况，检测率有了较大程度的下降，但误报率波动很小，这可能是因为不平衡数据集影响了支持向量机超平面的建立。从结果可以看出，SR_SVM方法减弱了不平衡数据集对SVM的影响，SR_SVM的检测率较SVM有较大程度的提高，误报率基本上与SVM持平。无论是正常记录多于攻击记录还是相反情况，SR_SVM在检测率上基本平稳，而SVM的表现则明显差了很多。

表3 TCP不平衡记录抽取情况

表4 不平衡数据实验结果

3.3 讨论

在分类前，用稀疏编码方法自动提取稀疏特征，而稀疏性符合人类的视觉机理[7]。稀疏性带来好的性能，这在许多文献中已有所体现[7，8]。分析原因主要有两点：

(1)从重构的角度来看，目标函数的第一项是重构残差，最小化重构残差使得系数几乎与原来的样本具有相同的表示能力。

(2)从稀疏的角度来看，使得在保证重构能力的条件下编码稀疏尽量稀疏，即对一些原子具有敏感性，这符合人类的视觉机理[7]。另外，稀疏性起到部分去噪作用，这在大量的图像修复文献中已得到证实[8，14]。因此，稀疏性促使很强的判别力。

本文将稀疏编码与多类支持向量机结合应用到网络入侵中的数据分类，初步的实验结果已显示稀疏性所带来的好处。学习得到的过完备词典可以丰富地表示所有的样本，在词典上稀疏编码也可以有效地学习到样本的判别力特征。在接下来的实验中,会加入更多的实时数据来完善系统,构建可以应用到实际的实时高效的入侵检测系统。

[1]焦从信，王崇骏，陈世福.基于完全无向图的贝叶斯分类器在入侵检测中的应用[J].计算机科学，2008，35(9)：83-86.

[2]姜庆民，吴宁，刘伟华.面向入侵检测系统的模式匹配算法研究[J].西安交通大学学报，2009，43(2)：58-62.

[3]刘衍珩,田大新,余雪岗，等.基于分布式学习的大规模网络入侵检测算法[J].软件学报，2008，19(4)：993-1003.

[4]刘在强，林东岱，冯登国.一种用于网络取证分析的模糊决策树推理方法[J].软件学报，2007，18(10)：2635-2644.

[5]CHEN R C，CHEN S P.An intrusion detection based on support vector machines with a voting weight schema[J].IEA/AIE 2007：1148-1157.

[6]YANG J，YU K，HUANG T.Efficient highly over-complete sparse coding using a mixture model[C].The 11th European Conference on Computer Vision(ECCV)，Crete，2010.

[7]WRIGHT J，YANG A，GANESH A，et al.Robust face recognition via sparse representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence(PAMI)，2009，31(2)：210-227.

[8]YANG J，YU K，HUANG T，et al.Image super-resolution as sparse representation of raw image patches[C].In：IEEE Conference on Computer Vision and Pattern Recognition，(2008)，Anchorage，AK.

[9]RUBINSTEIN R，BRUCKSTEIN A M，ELAD M.Dictionaries for dparse tepresentation modeling[C].Proceedings of the IEEE，2010，98(6).

[10]Aharon M，ELAD M，BRUCKSTEIN A M.The K-SVD：an algorithm for fesigning of overcomplete dictionaries for sparse representation[J].IEEE Trans.on Signal Processing，2006，54(11)：4311-4322.

[11]ZIBULEVSKY M，ELAD M.L1-L2 optimization in signal and image processing[J].IEEE Signal Processing Magazine，2010，27(3)：78-88.

[12]EFRON B，JOHNSTONE I，HASTIE T，et al.Least angle regression[J].Ann.Statist，2004，32(2)：407-499.

[13]TENG S H，DU H L，WU N Q，et al.A cooperative network intrusion detection based on fuzzy SVMs[J].Journal of Network，2010，5(4)：475-483.

[14]MAIRAL J，BACH F，PONCE J，et al.Non-local sparse models for image restoration[C].International Conference on Computer Vision，Tokyo，Japan，2009.