陈天宇，吴 凡，马世杰，李 雷

(南京邮电大学，江苏 南京 210023)

基于CS和LS-SVM的入侵检测算法

陈天宇，吴 凡，马世杰，李 雷

(南京邮电大学，江苏 南京 210023)

由于入侵检测中具有原始数据量大、维度较高、冗余度较大等特点,导致传统的入侵检测算法面对海量数据时检测识别度低，运行时间长，性能较差。为此，文中提出了一种将压缩感知和最小二乘支持向量机应用于入侵检测系统的方法。其创新点主要在于：引入压缩采样技术提取原始数据特征，在保留原数据主要特征的前提下，将高维数据转化为低维数据；利用最小二乘支持向量机直接在观测域中训练和分类数据，且核函数通过组合核函数构建。仿真结果表明，运用压缩感知进行特征提取能够极大保留原始特征，而最小二乘支持向量机能够在不损失精度的前提下加速分类。该方法能够较大地减少训练时间，并可以有效提高检测精度。

压缩感知；最小二乘法；支持向量机；入侵检测

1 概 述

随着经济社会的发展，互联网被广泛应用于社会的各行各业。然而，人们在享受互联网带来的便利和高效的同时，其本身却充斥着安全隐患，对财产安全和隐私造成了巨大威胁。在这样的社会大环境下，入侵检测系统(IntrusionDetectionSystem，IDS)成为当下的热门研究领域[1],其本质上是个分类问题[2]。目前，入侵检测主要通过机器学习、数据挖掘、神经网络等方式完成[3-8]，其一般流程为提取入侵行为或正常行为的数据特征，构建出一个特征数据库，从中进行模式匹配，从而完成入侵检测。然而，一方面，随着网络技术的发展，宽带不断提高，受限于奈奎斯特采样定理，实时采样对软硬件的要求不断提高；另一方面，采用机器学习的方法进行入侵检测时，必然会面对样本数据相关性大、维数高，训练重复样本多，训练时间过长并且入侵样本标记困难等问题[2]。

近年来，由D.Donoho等在矩阵分析、统计理论、优化理论等研究的基础上，提出了一种新的信息采样理论—压缩感知理论(CompressedSensing,CS)[9-12]。该理论指出，若信号在某个变换域内是稀疏的，则该信号就可以用一个与变换基不相关的观测矩阵实现从高维到低维的映射，并可以将低维信号重构，从而恢复出完整的信息。

在压缩感知理论中，基于l0范数最小化的重构算法是NP-hard问题，即使将问题转化为l1范数最小化问题，计算复杂度仍为O(N3)[13]，其中N为信号长度。

上述算法都无法避免对信号进行重构，同时传统的基于压缩感知的入侵检测在低信噪比下检测效果不佳。

支持向量机[14](SupportVectorMachine,SVM)以统计学为基础，通过寻求结构风险最小化来实现经验风险和置信范围的最小化，广泛应用于统计分类中，适用于线性可分以及线性不可分的问题，在较小的训练样本时也能获得良好的分类效果。

基于以上原因，文中将原始入侵检测数据进行预处理后，选取合适的观测矩阵和稀疏基进行压缩采样并归一化，进而将观测域下的低维数据通过最小二乘支持向量机建立检测分类器，完成入侵检测。在最小二乘支持向量机中，采用组合核函数的形式，寻求获得最近似实际的分类模型。仿真结果表明，与经典的机器学习方法和压缩感知算法相比，文中提出的算法可以有效改善支持向量的稀疏性，提高系统的鲁棒性，检测性能大幅提高，且利用组合核函数实现的分类结果较一般核函数的分类结果更精确。

2 压缩感知和支持向量机理论

2.1 压缩感知

(1)

式(1)表明，S,X其实表示的是同一个信号，只不过S为信号在Φ域中的表现形式，X为其在时域中的表现形式。在Φ域中，假设X的加权系数列S中有K个非零系数，则X可以用这K个非零系数来表示，称信号X的稀疏度为K。当K≪N时，就称信号X具有稀疏性。

y=ψX=ψΦS=ΘS

(2)

其中：ψ为观测矩阵；Θ=ψΦ是一个M×N维的压缩传感矩阵。

由于ψ是事先选定的确定矩阵，不随信号X变化，因此该测量过程具有非自适应性。

综上所述，压缩感知理论共包括如下三方面：

第一，对于信号X，找到其稀疏正交基Φ，使得该信号在Φ上稀疏表示。

第二，找到一个M×N的测量矩阵ψ，使其与Φ满足非相关性，即在对信号X进行压缩和降维的过程中，基本不损失原信号X中的重要信息，该概念等价于Θ满足约束等距条件[15](RestrictedIsometryProperty,RIP)，也就是说,对∀s∈RN,有

(3)

其中，ε为失真因子。

第三，提取原信号X中的特征信息后，采取适当的重构算法和分类算法，恢复数据信息并进行检测。

2.2 支持向量机

支持向量机是一种强大的机器学习工具，已经在模式识别、数据挖掘等方面广泛应用。由于压缩感知技术在重构时采用的算法复杂度较高，而Calderbank等证明了利用SVM将观测域上的压缩信号直接分类，其性能与对原信号直接使用SVM的精度类似[16]，故文中采用将观测域下的信号直接利用SVM对数据进行训练和分类。

假设样本集为:(xi,yi),i=1,2,…,n,x∈Rd,y∈{-1,1}是类别标号。在一个d维的空间中，在处理非线性问题时，先寻找某个非线性映射Π:Rd→H,x→π(x)，将原空间Rd中的数据x映射到一个高维特征空间中，接着通过引入某种符合Mercer条件的核函数K(xi,xj)，使支持向量机可以在高维核空间中直接利用线性函数进行线性分类。那么在高维空间中所用的分类函数如下所示：

(4)

其中：ai>0是Lagrange因子；b是域值。

目前使用率最高的核函数有如下三种：

(1)多项式核函数(Poly)。

K(x,xi)=[(x·xi)+l]q

(5)

(2)Gauss径向基核函数(RBF)。

K(x,xi)=exp(-‖x-xi‖2/σ2)

(6)

(3)Sigmoid核函数(Sigmoid)。

K(x,xi)=tanh[v(x×xi)+c]

(7)

其中，v>0,c<0。

为使分类性能最佳，文中采用改进交叉验证[17]的方法寻找最优参数。

3 基于压缩感知和支持向量机的入侵检测算法

3.1 稀疏基和随机观测矩阵的选取

基于对入侵检测数据的认识，文中的稀疏基采用Gabor紧框架字典[18]，其概念为：设a和b是给定的正数，对于∀g∈L2:L2(R)，称函数族。

ψj,k(x):=ei2πkbxg(x-ja),j,k∈Z

(8)

为经过函数g得到的Gabor函数系。

若存在常数A和B(0

(9)

则称函数族(见式(8))是L2的一个Gabor框架，并且称A和B为框架界。而‖·‖和<·>表示L2的范数和内积，当式(9)中A和B相等时称对应的框架为紧框架。

文中采用的观测矩阵为伯努利随机矩阵，其定义为：

对于矩阵Φ∈RM×N，矩阵中每个独立且同分布的元素都服从伯努利分布，即：

(10)

伯努利矩阵具有较强的随机性，因此符合RIP要求。

3.2 支持向量机的选取

文中采用最小二乘支持向量机(LS-SVM)的方法。LS-SVM是普通支持向量机的一种扩展，将最小二乘线性误差的平方和取作损失函数，从而求解一系列方程组。LS-SVM收敛速度快，计算速度得到提升，因而在非线性分类和模式识别中得到广泛应用。

Π为非线性映射，则最小二乘支持向量机的优化问题可以描述为：

(11)

其中：w为权值向量；γ为正则化系数；ek为实际值与真实值的误差。

约束条件为：

yk[ωTp(xk)+b]=1-ekk=1,2,…,N

另一方面，文中选用Poly+RBF构成组合核函数，其形式为：

K(x,xi)=α[(x·xi)+l]q+(1-α)× exp(-‖x-xi‖2/σ2)

(12)

式中，权系数α(0≤α≤1)作用是调节两种核函数在作用时的权重。

当求出优化问题的解ai之后，组合核函数LS-SVM模型的决策超平面可表示为：

(13)

3.3 系统建立及算法描述

文中的入侵检测系统共包含5个模块，具体如图1所示。

图1 入侵检测系统模块

具体实现步骤表述为：

Step1：数据预处理。将原始数据向量化表示。

Step2:文中采用随机伯努利矩阵作为测量矩阵，采用Gabor紧框架字典作为稀疏正交基。此时测量矩阵和稀疏基满足RIP条件，且利用它们构成的压缩传感矩阵能够有效地完成对原始数据的特征提取，得到低维向量。

Step3：将得到的特征数据归一化到[0,1]的区间内，避免特别大的数据在数据集中起主导作用，提高计算精度。归一化操作如下式：

yi'=(yi-min)/(max-min)

(14)

Step4：使用最小二乘支持向量机分类。作为对照，并分别选取RBF核函数和POLY+RBF组合核函数。

Step5：运用K折交叉验证(K-CV)的方法选择最优参数。将数据集平均分成10组，接着轮流将当中9组作为训练集，其中1组作为验证集(或叫测试集)，进行10次实验。依据每次实验的分类精度，来确定针对该数据集的最优参数。

Step6：利用最优参数对数据进行训练和预测，得出最优分类器和分类结果。

4 仿真实验

4.1 实验平台

实验所用平台为：IntelCorei5，CPU2.4GHz，4GBRAM,Windows8.1操作系统,Matlab2014a。

4.2 数据来源

为分析比较实验结果，文中采用KDDCUP99入侵检测数据集，对分别采用不同的特征提取策略，不同的支持向量机，以及不同核函数的情况下得到的入侵检测算法效率进行比较分析。KDD99数据集总共由500万条记录组成，文中攻击数据采用KDDCUP99中特征比较显著的四大类网络攻击：

(1)DenialOfService(DOS)；

(2)RemotetoLocal(R2L)；

(3)UsertoRoot(U2R);

(4)Surveillanceorprobe(Pride)。

由于数据量过大，文中只采用部分数据进行仿真实验，如表1所示。

表1 仿真实验用的样本数据

4.3 对比算法和性能指标

为使文中的CS-LSSVM算法检测结果更具说服力，引入KPCA-LSSVM,CS-SVM,LSSVM进行对比试验，并引入如下四个检测性能指标：

运行时间t。

4.4 结果与分析

图2～4展示了以KDDCPU99为实验数据，在五种算法中进行入侵检测的DR、FDR和LDR。通过对比，进一步研究了基于压缩感知的入侵检测下具备的优势和不足。

图2 不同算法的检测率

图3 不同算法的漏报率

图4 不同算法的误报率

对图2～图4进行分析，可得到如下结论：

(1)在CS-SVM算法中，使用POLY+RBF构成的组合核的性能指标明显优于单一核，可见组合核更能充分划分出数据的特性。

(2)CS-LSSVM的性能指标明显优于KPCA-LSSVM。这表明就特征提取的策略而言，在本问题中，运用CS的效果优于KPCA。

(3)CS-LSSVM的性能指标稍逊色于CS-SVM。这是运用了最小二乘理论，牺牲分类精度换取收敛速度所导致的必然结果；然而，CS-LSSVM的精确度足以满足一般要求。

(4)CS-LSSVM的性能指标与采用普通LSSVM的性能指标相接近。这说明文中采用的稀疏基和观测矩阵是合适的，能够充分提取原始数据的特征。

五种算法的运行时间如图5所示。

图5 训练与检测时间

由图5可知，采用CS-LSSVM算法，运行时间比KPCA-LSSVM更快，且远少于其他算法。这是由于运用压缩采样进行特征提取，极大地降低了数据维度，提高了数据稀疏性导致支持向量维度降低，样本的训练和分类速度快。结果表明了文中CS-LSSVM的巨大优势和运用价值。

5 结束语

文中提出了一种基于压缩感知并结合运用最小二乘支持向量机的入侵检测算法。该方法的创新点在于：通过选择恰当的稀疏基和观测矩阵，有效对网络数据压缩采样。特别在网络数据获取阶段，直接使用特征提取后的数据，用组合核LSSVM构建的分类器进行训练和入侵检测。仿真实验的结果表明，该方法与传统方法在DR、FDR和LDR上较为接近，但运行时间远优于传统的非压缩方法。另一方面，采用组合核函数构建的LSSVM在分类精度上明显优于单一的核函数。未来，还将进一步研究如何提高检测精度，以及在已经正确分类的前提下如何对压缩后的数据进行重构等问题。

[1]PerezFM,Mora-GimenoF,Marcos-JorqueraD,etal.Networkintrusiondetectionsystemembeddedonasmartsensor[J].IEEETransactionsonIndustrialElectronics,2011,58(3):722-732.

[2]HofmannA,SickB.Onlineintrusionalertaggregationwithgenerativedatastreammodeling[J].IEEETransactionsonDependableandSecureComputing,2011,8(2):282-294.

[3]PandaM，AbrahamA，PatraMR.Ahybridintelligentapproachfornetworkintrusiondetection[J].ProcediaEngineering,2012,30:1-9.

[4]YusufovnaSF.Integratingintrusiondetectionsystemanddatamining[C]//Procof2008internationalsymposiumonubiquitousmultimediacomputing.[s.l.]:[s.n.],2008:256-259.

[5]YiYang,WuJiansheng,XuWei.IncrementalSVMbasedonreservedsetfornetworkintrusiondetection[J].ExpertSystemswithApplications,2011,38(6):7698-7707.

[6] 陈桂林，王生光，徐静妹，等.基于GA和组合核的SVM入侵检测算法[J].计算机技术与发展,2015,25(2):148-151.

[7] 张 拓，王建平.基于CQPSO-LSSVM的网络入侵检测模型[J].计算机工程与应用,2015,51(2):113-116.

[8] 黄 亮，吴 帅，谭国律，等.基于EPSO-RVM的网络入侵检测模型[J].计算机工程与应用,2015,51(3):85-88.

[9]DonohoDL.Compressedsensing[J].IEEETransactionsonInformationTheory,2006,52(4):1289-1306.

[10]CandesEJ,RombergJ,TaoT.Robustuncertaintyprinciples:exactsignalreconstructionfromhighlyincompletefrequencyinformation[J].IEEETransactionsonInformationTheory,2006,52(2):489-509.

[11] 戴琼海，付长军，季向阳.压缩感知研究[J].计算机学报,2011,34(3):425-434.

[12] 焦李成，杨淑媛，刘 芳，等.压缩感知回顾与展望[J].电子学报,2011,39(7):1651-1662.

[13]DonohoD,TannerJ.Observeduniversalityofphasetransitionsinhigh-dimensionalgeometry,withimplicationsformoderndataanalysisandsignalprocessing[J].PhilosophicalTransactionsofTheRoyalSocietyAMathematicalPhysicalandEngineeringSciences,2009,367(1906):4273-4293.

[14] 郭丽娟，孙世宇，段修生.支持向量机及核函数研究[J].科学技术与工程,2008,8(2):487-490.

[15]ZhangT.SparserecoverywithorthogonalmatchingpursuitunderRIP[J].IEEETransactionsonInformationTheory,2011,57(9):6215-6221.

[16]TyS,AllenJD,LiuX.Detectionofmodifiedmatrixencodingusingmachinelearningandcompressedsensing[J].ProcofSPIE,2011,8063(13):1216-1217.

[17] 邓 蕊，马永军，刘尧猛.基于改进交叉验证算法的支持向量机多类识别[J].天津科技大学学报,2007,22(2):58-61.

[18]YangMeng,ZhangLei,ShiuSCK,etal.GaborfeaturebasedrobustrepresentationandclassificationforfacerecognitionwithGaborocclusiondictionary[J].PatternRecognition,2013,46(7):1865-1878.

IntrusionDetectionAlgorithmBasedonCompressedSensingandLeastSquareSupportVectorMachine

CHENTian-yu，WUFan，MAShi-jie，LILei

(NanjingUniversityofPostsandTelecommunications，Nanjing210023，China)

Duetoalargeamountofrawdata,andhighdimensionandredundancyinintrusiondetection,resultingintheproblemoflowrecognition,longoperationandbadperformancefortraditionalintrusiondetectionalgorithminthefaceofmassivedatadetection,amethodofcombiningcompressedsensingandleastsquaresupportvectormachinetoapplytointrusiondetectionsystemisputforward.Innovationasfollows:Introducingcompressivesamplingtoextractthefeaturefromtheoriginaldata,thehighdimensionaldataistransformedintoalowoneonthepremiseofretainingthemainfeaturefororiginaldata;Usingleastsquaresupportvectormachinetodirectlytrainandclassifydataintheobservationdomain,andthekernelfunctionisconstructedbythecombinationofkernelfunction.Simulationshowthatusingcompressedsensingtoextractthefeaturecansignificantlyreservetheoriginalfeature.Moreover,leastsquaresupportvectormachinecanacceleratethespeedofclassifyingwithoutlosingaccuracy.Thismethodcangreatlyreducethetrainingtime,andeffectivelyimprovetheaccuracyofdetection.

compressedsensing;leastsquaremethod;supportvectormachine;intrusiondetection

2015-04-21

2015-07-23

时间：2016-05-05

国家自然科学基金资助项目(61070234，61071167，61373137)；国家大学生创新创业训练计划项目(201410293021Z)

陈天宇(1994-)，男，研究方向为机器学习；李 雷，教授，博士生导师，研究方向为核方法、机器学习、模糊数理论和智能控制等。

http://www.cnki.net/kcms/detail/61.1450.TP.20160505.0814.024.html

TP

A

1673-629X(2016)05-0099-05

10.3969/j.issn.1673-629X.2016.05.021