基于树突细胞算法与对支持向量机的入侵检测
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于树突细胞算法与对支持向量机的入侵检测范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：针对入侵检测技术在处理大规模数据时存在的高误报率、低训练速度和低实时性的问题，提出了一种基于树突细胞算法与对支持向量机的入侵检测策略（DCTWSVM）。利用树突细胞算法（DCA）对威胁数据进行初始检测，在此基础上利用对支持向量机（TWSVM）进行检测结果的优化处理。为了验证策略的有效性，设计性能对比实验，实验结果表明，相较于DCA、支持向量机（SVM）、反向传播（BP）神经网络，DCTWSVM策略的检测精度提高了2.02%、2.30%、5.44%，误报率分别降低了0.26%、0.46%、0.90%，训练速度相较于SVM提高了两倍且只需耗费极少的训练时间，可以更好地适用于大规模数据下的实时入侵检测环境。
关键词：树突细胞算法；对支持向量机；入侵检测；大数据
中图分类号： TP393.08
文献标志码：A
0引言
入侵检测一直是计算机网络安全中重要的研究热点之一[1]。由于当前网络安全威胁形式呈现多样化，因黑客攻击、行业竞争等原因引发的安全问题无一不在威胁着计算机网络下的系统终端用户[2]。入侵检测系统（Intrusion Detection System， IDS）是一种集成了入侵行为过程的软件系统，并常与入侵防御系统（Intrusion Prevention System， IPS）并称为入侵检测防御系统（Intrusion Detection Prevention System， IDPS）。在网络环境中，入侵检测的延迟报警并不具备较高的实用性，但由于当前检测技术大都依赖于网络环境下产生的历史审计数据（Audit Data）进行分析，所以实时入侵检测的实现、提高检测正确率与效率也是当下重要的研究问题。
生物免疫系统（Immune System， IS）是生物体内保护生物免受病原体危害及保障生物稳态性的一种免疫机制[3]，该系统拥有动态性和自适应性等诸多特性。当病原体侵入人体后，将会引发免疫细胞的一系列活动来保障人体稳态性[4]。近些年通过对危险理论（Danger Theory， DT）的深入研究[5-6]，业界开始针对树突细胞（Dendritic Cell， DC）生物学来开拓免疫机制的新思路以应对日益严峻的安全形势[7]。由此衍生的树突细胞算法具备多项优势，如良好的实时性、较小的资源需求、较少的训练样本、精简的训练过程和优质的检测精度等。
将机器学习与数据挖掘技术应用在入侵检测领域已经取得了较好的成绩[8-10]。支持向量机（Support Vector Machine， SVM）技术作为其中的一项主流技术也取得了较多的研究成果[11-13]。SVM是根据Vapnik的统计学习理论产生，从二分类的研究衍生到多分类问题的研究，究其原理主要是通过求解空间超平面使分类距离最大化来解决分类最优解[14]。传统的SVM存在训练算法复杂度较高、计算时间较长等问题，因此应用SVM处理入侵检测问题时，需要对其进行算法层次的改进或寻找更为简单有效的核函数来简化运算，例如采用对支持向量机算法（TWin Support Vector Machine， TWSVM）来提升检测速度；另外也可以将SVM与其他算法进行结合优化，例如Shon利用遗传算法（Genetic Algorithm， GA）来优化传统算法[12]。
本文提出了一种基于树突细胞算法和对支持向量机（Dendritic Cell TWin Support Vector Machine， DCTWSVM）入侵检测策略。该策略有效提高入侵检测的检测准确率，降低误报率，并且在检测数据量大幅提升的情况下可以有效满足检测的实时性要求。
1树突细胞入侵检测模型
基于危险理论而衍生的树突细胞算法（Dendritic Cell Algorithm， DCA）在生物免疫学中突破了传统免疫理论中的“自我非我”（Selfnonself）免疫思路，转而采取针对危险信号（Danger Signal）的识别应答，这使得算法的适用条件比较广泛，如实时计算或半实时计算下的异步处理环境。
DC细胞对于存在于生物组织中的信息十分敏感，入侵检测的过程中，DC细胞的主要存在形式有3种：未成熟DC（immature DC，iDC）、半成熟DC（semimature DC，sDC）以及成熟DC（mature DC，mDC），通过界定DC的3种状态可以定义当前环境是否处于危险或者安全状态。DC细胞组成结构初始化信息包括：生命周期（lifespan）、初始signal值、信号转换权值矩阵（W）。DC进行状态转换的标准主要依据协同刺激信号（CoStimulatory Molecule，CSM）。算法的处理流程如图1所示。在图1中，输入的信息包括抗原（Antigen）与信号（Signal），信号即安全信号（Safe Signal）与Danger Signal；除此之外还包括病原体相关分子模型（Pathogenic Associate Molecular Pattern，PAMP）以及炎症因子（Inflammatory Cytokines，IC）。在对输入数据进行处理的过程中，作为专职抗原提呈细胞（Antigen Presenting Cell，APC）的树突状细胞负责采集Antigen产生的信息进行识别、分析、处理并提呈给相关免疫细胞，利用免疫细胞进行病原体入侵识别。
在iDC采集Antigen和Signal的过程中，输出信号的计算主要通过下述公式确定：
O[csm，semi，mat]=WCW
WC=WPCP+WSCS+（WDCD）（1+IC）
W=WP+WS+WD （1）
其中，O[csm，semi，mat]分别代表了CSM、sDC、mDC的输出值，WP是输入PAMP的权值，WS是输入安全信号的权值，WD是输入危险信号的权值，IC是炎症因子的值；CP是PAMP的输入浓度，CS是安全信号的输入浓度，CD是危险信号的输入浓度。相关的权值参考表1。假设状态转移参考阈值为Th，则当O[csm，semi，mat]大于Th时，发生状态转移、将信息输出，反之重新开始采集输入信息。
表格（有表名）
表1基于DCA的权值表
输入信号
信号权重
csmsemimat
WP202
WS101
WD22-2
DCA在异常检测中一项重要的判断标准是上下文成熟度抗原值（Mature Context Antigen Value，MCAV）。MCAV代表了在某种环境下完全成熟的抗原数量M与提呈的抗原总量Ag的比值，若MCAV的值接近于1，则抗原极有可能是异常的，因此MCAV用于评估输入抗原的异常度。通过界定不同的参考阈值，可以有效提升树突细胞算法的整体检测能力。
MCAV=M/Ag（2
MCAVavg=∑ iMi∑ iAgi1+∑ iAgi2（3
式（2）是MCAV求解的标准形式。式（3）是基于式（2）的变形形式，其意义是：由于采集的抗原上下文组合的多样性，若抗原数据在正常状态下收集到抗原上下文，则表示DC细胞处于半成熟状态（Agi1）；若在异常情况下的收集到的抗原上下文，则表示DC细胞处于成熟状态（Agi2）。MCAVavg代表了该组序列抗原值。
根据文献[7]的DCA形式化描述，树突细胞入侵检测基本的步骤分为3个阶段：初始化（第1）行～3）行）、入侵检测（第4）行～18）行）、结果分析（第19）行～23）行）。初始化过程需要设定DC细胞数量Cell（num）、算法迭代数Iteration（max）、以及状态转移阈值Th，经过数据处理、信号转换等过程，最后完成信息提呈，伪代码第13）行中的terminal condition依据式（1）中O[csm，semi，mat]的变化而定。
DCA的过程如下所示：
程序前
Input： time series data （antigen and signal）
Output： antigen type and MCAV
Set Cell（num）， Iteration（max）， Th
1）
for each DC do
2）
initiate DC
3）
endfor
4）
for Iteration（max） do
5）
if antigen then
6）
antigen profile update
7）
endif
8）
if signal then
9）
signal transformation
10）
for iDC do
11）
cell lifespan update
12）
signal profile update
13）
if termination condition then
14）
output record
15）
endif
16）
endfor
17）
endif
18）
endfor
19）
for output record do
20）
for antigen type do
21）
calculate MCAV
22）
endfor
23）
endfor
程序后
2基于对支持向量机的入侵检测优化
2.1对支持向量机与入侵检测
传统的SVM算法是监督式（supervised）的学习方法[11]，在解决非线性分类及高维模式识别等问题中表现出了特有的优势，在文献[11-13]中的研究表明将SVM方法应用于入侵检测场景可以收到相对满意的效果。由于支持向量机在训练算法复杂度上并不存在较大的优势，且算法计算时间较长，所以若直接利用其来进行入侵检测的离线分析尚且满足要求，但对于实时性等较高要求，该方法并不完全满足。关于TWSVM与入侵检测，在文献[15]中的研究表明对于传统SVM，TWSVM在训练时间上的优势可以有效平衡入侵检测的输出并提高检测率，但是对于实时性则并未作太多分析。
2.2基于对支持向量机的入侵检测优化
DCA在很大程度上弥补了TWSVM在实时性等方面的劣势，但是在输出结果时存在较高的误报率（False Positive Rate，FPR） [7]。经过分析可得，产生上述结果的原因主要有以下3点：1）DCA对于输入数据的序列有一定的依赖性；2）DCA对于抗原的危险性需要根据当前设定的参考阈值判断，且该阈值对于判断结果有直接影响；3）DCA对于判断识别率具有一定的随机性[7]。对于1）本文暂时不予深究，对于2）的影响将通过实验来进行参数优化，对于3）引起的影响将通过TWSVM来对DCA的检测结果作进一步优化，从而提高检测结果的准确率，降低误报率。
2.2.1对支持向量机
假设在TWSVM中需要的两类超平面分别用Α和B表示，则TWSVM的求解问题可以转化为两个非平行超平面（nonparallel hyperplane）问题的求解过程：
xTω（1）+λ（1）=0
xΤω（2）+λ（2）=0 （4
式（4）代表了正、负两类超平面的最终求解方程。这里，x是一个数据集合，ω∈Rn与λ∈R分别是两个超平面方程的系数；ω（1）与λ（1）属于正类的法向量和偏移量，ω（2）与λ（2）属于负类的法向量和偏移量。
TMSVM1：
minω（1），λ（1），q12（Aω（1）+e1λ（1））Τ（Aω（1）+e1λ（1））+c1eT2q
s.t. -（Bω（1）+e2λ（1））+q≥e2； q≥0（5
TMSVM2：
minω（2），λ（2），q12（Bω（2）+e2λ（2））T（Bω（2）+e2λ（2））+c2eT1q
s.t. -（Aω（2）+e1λ（2））+q≥e1； q≥0（6
式（5）的TMSVM1代表求解一个超平面使其拟合正类样本A而远离负类样本B；式（6）的TMSVM2代表求解一个超平面使其拟合负类样本B而远离正类样本A。q为松弛因子且其元素均为1，c1、c2>0为正负两类样本的惩罚因子，e1、e2>0且其元素均为1。对于测试样本x，计算并比较它到两个超平面的距离，即可判断该样本所属类别。
规定如下定义：
H=[Ae1]
G=[Be2]
u=[ω（1）λ（1）]
v=[ω（2）λ（2）] （7
根据式（7）中的定义，可以得到如下方程：
HTHu+GΤa=0
HTHv+GΤb=0 （8
在式（8）中，a和b作为拉格朗日乘子向量依据Wolfe对偶问题（DTWSVM）[16]的求解方式如下：
DTWSVM1：
minaeΤ2a-12aΤG（HΤH）-1GΤa
s.t. 0≤a≤c1e2（9
DTWSVM2：
minbeΤ1b-12bΤH（GΤG）-1HΤb
s.t. 0≤b≤c2e1（10
从式（9）和式（10）中解出a和b的值，接着根据式（8）可以求出u和v，最后利用式（1）和式（7）确定最终的超平面解。在给定样本x∈Rn后，可以根据式（11）来判断x的最终分类：
Classx=arg mink=1，2（ω（k）・x）+λ（k）（11）
其中|・|运算表示样本x到超平面的垂直距离。
传统的SVM算法训练问题本质上就是求解一个二次规划（Quadratic Programming，QP）问题，且时间复杂度在给定样本数为m后的上限为O（m3）[17]。比较而言，TWSVM算法将原本求解的大问题转成两个二次规划问题，缩小了每个子问题的规模。若每类样本规模数量为m/2，则近似的时间复杂度为O（m3/4），相较于传统SVM算法展现了绝对的时间优势。
2.2.2基于对支持向量机的入侵检测优化算法
鉴于TWSVM的分类精度高和训练速度快的优势，本文利用TWSVM对DCA的检测结果进行更深层次的优化处理，同时针对惩罚因子c1、c2通过实验进行参数优化，进一步提高算法性能。
检测优化的TWSVM描述如下（假设训练集样本中的种类为n）：
步骤1设置c1、c2的初始值。
步骤2训练算法。训练分类器TWSVM1， 得到两个超平面Π1和1； 第i个分类器TWSVMi将第i类训练样本的类别标记为+1，而降其余所有训练样本的类别标记为-1，得到的超平面是Πi和i；直至构建第n-1个分类器TWSVMn-1。
步骤3测试。将树突细胞检测结果样本经过所有TWSVM分类器进行分类，计算样本x到TWSVMi的两个超平面Πi和i的距离为d1和d2，若d1>d2，则样本x被判定为第i类，继续遍历直到样本中的所有数据都被判定类别后停止。
3实验与分析
本文采用的是KDD Cup （1999）的10%数据子集，KDD数据集是目前应用于计算机网络入侵检测研究中普遍采用的测试数据集。该数据集包含训练集数据4898431条和测试集数据311029条，除去正常数据之外，所有的攻击数据包括以下4类：拒绝服务（Denial of Service，DoS）、权限提升（User to Root，U2R）、远程权限获取（Remote to Local，R2L），以及端口漏洞扫描（Probe）。在训练集数据中，只有19.85%（约972781条数据）是正常网络流量数据，其他均为攻击数据；在测试集数据中，有19.48%（约60593条数据）是正常的网络流量数据而其他的均为攻击数据。在KDD Cup数据集中的每一条记录都可以用41种定量且定性的特征进行约束。本文从训练集中选出代表性数据86990条，从测试集中选出数据43130条，关于数据描述详见表2。同时作为算法对比测试，本文采取单独使用DCA、SVM、反向传播（Back Propagation，BP）神经网络，与本文使用的DCTWSVM一同进行数据的训练和测试。实验参数如下：Cell（num）=200，Iteration（max）=50，Th=0.65，c1=1000，c2=1000。实验环境是Intel Xeon CPU 2.60GHz，内存是32GB，所有策略算法均采用 C++实现。
表格（有表名）
由表3和表4中的平均水平来看，与DCA、SVM、BP神经网络相比，本文的DCTWSVM在检测精度方面分别提高了2.02%、2.30%、5.44%，在误报率方面分别降低了0.26%、0.46%、0.90%。
综合分析，DCTWSVM展现了较高的检测精度，在处理DoS、Probe时相比其他策略均有小幅提高，在处理R2L与U2R的检测精度相比SVM有一定提升、比DCA、BP神经网络有较大提升；与此同时DCTWSVM取得了较低的误报率，其中U2R和R2L的误报率相比DCA有十分明显的降低。
表格（有表名）
从图2中看到，DCA的训练时间很少、这主要与该算法需要较少的训练样本有关[7]。DCTWSVM的训练时间呈现了比SVM、BP神经网络算法更大的优势，尤其当训练数据规模较大时，训练速度几乎为SVM的两倍。
综合误报率、检测精度和训练时间可以得出：虽然DCA根据其基本原理可以在训练速度上占优[7]，但是本文提出的DCTWSVM可以在此基础之上进一步提高入侵检测的检测精度并有效降低误报率。在实际运用中，若对于实时性要求较高且用于检测DoS以及Probe攻击时，可以单独运用DCA；但是当数据规模较大且检测种类较多时，使用DCTWSVM可以在牺牲较少的训练时间基础上进一步提高检测精度，降低整体误报率，并最终提升检测的整体实时性，这使得DCTWSVM在复杂的应用场景中具备较高的参考价值。
4结语
本文鉴于DCA在处理入侵检测过程中具备的较高实时性的优势，结合TWSVM多类分类思想，提出了一种基于DCTWSVM的入侵检测策略。将DCA在入侵检测后可能存在的误报率较高的检测结果利用TWSVM训练效率高、分类精度高的特点进行结果优化。实验表明，DCTWSVM不仅保持了较高的检测精确度、较低的误报率，且在训练速度上相比一些传统算法有了显著提高，另外在实时性检测能力上有了明显提升，具有一定的实用价值。由于本文仅在KDD Cup数据集上进行了对比实验，在今后的工作中，要加强对于网络动态环境下产生的数据进行研究；加强DCA的优化，降低其检测的误报率；加强对TWSVM的优化，进一步减少其训练时间；另外考虑采取更为高效的分类算法与DCA进行组合解决复杂网络环境下的入侵检测问题。
参考文献：
[1] LIAO H， LIN C， LIN Y， et al. Intrusion detection system： a comprehensive review[J] . Journal of Network and Computer Applications， 2013， 36（1）： 16-24.
[2] KREUTZ D， RAMOS F M V， ESTEVES VERISSIMO P， et al. Softwaredefined networking： a comprehensive survey[J]. Proceedings of the IEEE， 2015， 103（1）： 14-76.
[3] AICKELIN U， DIPANKAR D. FENG G. Artificial immune systems[M]. Berlin： Springer， 2014： 187-211.
[4] HUA Y， LI T， HU X， et al. A survey of artificial immune system based intrusion detection[J]. The Scientific World Journal， 2014， 2014（3）： 156790.
[5] FANG X， WANG L， KANG J， et al. On dendritic cell algorithm and its theoretical investigation[J]. Computer Science， 2015， 42（2）： 131-133.（方贤进， 王丽， 康佳， 等. 树突细胞算法及其理论研究[J]. 计算机科学， 2015， 42（2）： 131-133.）
[6] SALMON H M， FARIAS C M D， LOUREIRO P， et al. Intrusion detection system for wireless sensor networks using danger theory immuneinspired techniques[J]. International Journal of Wireless Information Networks， 2013， 20（1）： 39-66.
[7] FENG G， GREENSMITH J， AICKELIN U. The dendritic cell algorithm for intrusion detection[M]. IGI Global： BioInspired Communications and Networking， 2011： 84-102.
[8] ZONG W， HUANG G， CHEN Y. Weighted extreme learning machine for imbalance learning[J]. Neurocomputing， 2013， 101（3）： 229-242.
[9] LIN W J， CHEN J J. Classimbalanced classifiers for highdimensional data[J]. Briefings in Bioinformatics， 2013， 14（1）： 13-26.
[10] HE Q， LI N， LUO W， et al. A survey of machine learning algorithms for big data[J]. Pattern Recognition and Artificial Intelligence， 2014， 27（4）： 327-336. （何清， 李宁， 罗文娟， 等. 大数据下的机器学习算法综述[J]. 模式识别与人工智能， 2014， 27（4）： 327-336.）
[11] JAEHAK Y， LEE H， KIM M S， et al. Traffic flooding attack detection with SNMP MIB using SVM[J]. Computer Communications， 2008， 31（17）： 4212-4219.
[12] JIANG C， ZHANG G， LI Z. Abnormal intrusion detection for embedded network system based on genetic algorithm optimised SVM[J]. Computer Applications and Software， 2011， 28（2）： 287-289. （姜春茂， 张国印， 李志聪. 基于遗传算法优化SVM的嵌入式网络系统异常入侵检测[J]. 计算机应用与软件， 2011， 28（2）： 287-289.）
[13] NIE P， ZANG L， LIU L. Application of multiclass classification algorithm based on twin support vector machine in intrusion detection[J]. Journal of Computer Applications， 2013， 33（2）： 426-429. （聂盼盼， 臧洌， 刘雷雷. 基于对支持向量机的多类分类算法在入侵检测中的应用[J]. 计算机应用， 2013， 33（2）： 426-429.）
[14] VLADIMIR V. The nature of statistical learning theory[M]. Berlin： Springer Science & Business Media， 2000： 2-6.
[15] HE J， ZHENG S. Intrusion detection model with twin support vector machines[J]. Journal of Shanghai Jiaotong University： Science， 2014， 19（4）： 448-454.
[16] MANGASARIAN O L. Nonlinear programming[M]. [S.l.]： Society for Industrial and Applied Mathematics， 1993： 10.
[17] KURT A K， HALL L O， GOLDGOF D B， et al. Fast support vector machines for continuous data[J]. IEEE Transactions on Systems， Man， and Cybernetics， 2009， 39（4）： 989-1001.