改进蚁群算法优化支持向量机的网络入侵检测

王雪松+梁昔明

摘要：针对支持向量机参数优化问题，为了提高网络入侵检测率，提出一种变异蚁群算法优化支持向量机的网络入侵检测模型（MACOSVM）。首先采用蚁群搜索路径节点代表支持向量机参数，并将网络入侵检测率为目标函数，然后通过蚁群算法的全局寻优能力和反馈机制寻找最优参数，并对蚂蚁进行高斯变异，克服蚁群陷入局部极值，最后将最优路径上的节点连接起来得到SVM的最优参数，建立最优网络入侵检测模型。采用KDD99数据集对模型进行仿真实验，仿真结果表明，MACOSVM的网络入侵检测速度要快于其它网络入侵检测模型，而且提高了网络入侵检测率。

1引言：

入侵检测系统（intrusion detection system，IDS）作为防火墙之后的第二道安全闸门，能够发现网络入侵行为，因此网络入侵检测已成为网络安全领域的研究热点[1]。网络入侵检测分为误用检测（misuse intrusion detection，MID）和异常检测（anomaly intrusion detection，AID）两类[2]。误用检测技术只可以检测已知入侵行为，不能对未知或变入侵行为进行检测，而异常检测可以较好对未知入侵行为进行检测，成为入侵检测中的主要研究方向[3]。传统网络入侵异常检测算法有：模式匹配算法、BM算法、QS算法等，这些算法均属于单模式的网络入侵检测算法，难以适应现代大规模网络安全检测要求[4]。近年来，随着人工智能技术的发展，出现了隐马尔可夫模型、支持向量机和神经网络等入侵检测模型，其中支持向量机（support vector machine，SVM）较好的克服了神经网络等传统机器学习算法的过拟合、泛化推广能力差等缺陷，对于高维、小样本的网络入侵检测具有明显优势[5-7]。大量实验表明，基于SVM的网络入侵检测模型性能与其参数：惩罚因子C和核函数参数等直接相关。为了获得较优SVM参数，学者们提出采用遗传算法（GA）、粒子群算法（PSO），在一定程度上优化了SVM的入侵检测性能[8-10]。蚁群算法（ant colony optimization algorithm，ACO）是一种源于大自然中生物世界的新仿生类算法，吸收了蚂蚁的行为特性，通过其内在的搜索机制，易于与其他启发式方法相结合[11，12]。

为了提高网络入侵检测率，提出一种变异蚁群算法（mutation ant colony optimization algorithm，MACO优化支持向量机的网络入侵检测模型（MACO-SVM），并通过仿真实验对其有效性进行检验。

变异蚁群算法

蚁群算法是由意大利学者M Dorigo等人在1991年受到蚂蚁搜索食物过程中依据同伴遗留下的信息激素进行最短路径选择的启发而提出的一种新的仿生优化计算方法，具有正反馈、分布式计算和贪婪启发式搜索等特点，但是基本蚁群算法存在过早收敛以及局部聚集等问题，为此，本文探路过程中，对蚂蚁进行高斯变异，打破蚁群严重聚集的情况（局部极值），产生一种变异蚁群算法（MACO），以便探索新的路径，提高问题求解的效率。

MACO算法优化SVM参数原理

采用MACO算法对SVM的参数C和σ优化过程，节点值表示C和σ，以入侵检测率作为目标函数，激素物质遗留在蚂蚁所走过的每个节点上，MACO算法所搜索出的最终路径表示最优网络入侵模型参数。SVM 参数优化的蚁群系统根据目标函数值来更新信息素的浓度，目标函数中包含各蚂蚁所爬行过的全部节点信息以及所建模型的网络入侵检测率。待优化的变量为SVM的参数C和σ，程序终止时，从蚁群的最优化路径中得到相对应的SVM的参数C和σ值，原理如图1所示。

MACO算法优化SVM参数过程

1）设蚁群规模为m，每只蚂蚁k均有一维数组pathk。其中依次存放第k只蚂蚁经过n个节点的纵坐标，n为所优化参数的总有效位，这些纵坐标连接在一起组成该蚂蚁的爬行路径。

2）全部蚂蚁置于起始点O，循环次数N=0，时间计数器t=0，最大迭代次数为：Nmax，初始化节点上信息量△τ（xi，yi，j，0），并设Δτ（xi，yi，j）=0。

3）设置变量i=1。

4）根据式（7）计算蚂蚁的转移概率，在线段Li上，根据概率以赌轮算法选择每只蚂蚁下一个转移节点，并将蚂蚁转移到相应节点上，并将该节点的纵坐标存入pathk的第i个元素中。

5）i=i+1，如果i>n，跳转到步骤6），不然跳转到步骤4）继续爬行。

6）根据数组pathk计算该路径对应的C和σ。

7）将训练集平均分成k个子集S1，S2，…，Sk。

8）SVM根据获得的{C，σ}对训练集进行学习，计算kfold交叉验证的检测率。

9）以kfold交叉验证中最优检测率作为适应度值，检测率最高对应路径作为本次循环的最优路径。

10）N=N+1，t=t+n，更新每个节点上的信息浓度，pathk中的全部元素置零。

11）对蚂蚁进行高斯变异，打破蚁群严重聚集的情况（局部极值），以便探索新的路径，并将新的路径与原有路径进行比较，选出最优蚂蚁。

12）如果迭代次数大于最大迭代数，则表示算法结束，并计算输出最优路径对应的SVM参数C和σ值。

13）SVM根据最优C和σ值对训练集重新学习，建立最优的网络入侵检测模型。

网络入侵检测多分类器构建

网络入侵检测实质上一个多分类问题，但SVM只能求解两分类问题，必须通过组合策略构建网络入侵检测器，本文采用有向无环图将两分类的SVM组合在一起，构造的网络入侵检测器如图2所示。

在CPU 2.8 GHz，RAM 1 GB 环境上，采用Libsvm 2，98实现仿真实验。按照一般的做法，实验采用KDD CUP 99数据集中的10%的数据（约10万条记录）中随机抽取的的正常连接记录作为训练样本。MACO算法的参数为：蚂蚁数m=10，最大迭代次数Nmax=100，Q=100，α=2，β=4。

为了使MACO-SVM模型检测更具说服力，在相同条件下，采用遗传算法优化SVM（GA-SVM）和基本蚁群算优化SVM（ACO-SVM）作为对比实验。模型性能评价指标为：检测率、误报率和运行速度。检测率和误报率定义如下：

检测结果对比

GA、ACO、MACO算法对SVM参数选择的结果见表3。然后采用表3的参数建立相应的网络入侵检测模型，GASVM、ACOSVM和MACOSVM的检测结果见表3。从表3可知，相对于对比模型GASVM、ACOSVM，MACOSVM的中支持向量数更少，但检测结果最佳，这表明 MACO算法比GA、ACO在SVM参数优化方面具有更好的较强的全局搜索能力，获得更优的SVM参数C，σ，可以降低网络入侵检测误报率，有效提高了网络入侵检测率。

运行速度对比

为了检测模型的运行速度，采用模型对验证集的检测时间（秒，s）作为衡量指标，各模型的检测时间见图3。从图3可知，相对于GASVM、ACOSVM，MACOSVM检测速度大幅度提高，主要由于MACOSVM减少了支持向量点数量，收敛速度加快，满足了现代网络入侵检测系统的实时性要求。

结论：基于SVM的网络入侵检测模型泛化能力与其参数选取密切相关，为了解决了SVM参数优化难题，提出一种基于MACOSVM的网络入侵检测模型。采用蚁群搜索路径节点表示SVM参数，将最优路径上的节点连接起来就可以得到SVM的最优参数C，σ值。仿真实验结果表明，MACOSVM可以获得较优的SVM参数，不仅可以加快网络入侵检测速度，同时提高了网络入侵的检测率，误报率明显降低。