基于增量学习的SVM-KNN网络入侵检测方法

付子爔,徐 洋,吴招娣,许丹丹,谢晓尧

(贵州师范大学 贵州省信息与计算科学重点实验室,贵阳 550001)

0 概述

随着互联网技术的迅速发展和广泛应用,网络安全问题日益突出,网络和与之相连的主机随时都可能遭受不同种类的攻击。为保障网络安全,研究者设计了多种入侵检测系统(Intrusion Detection System,IDS)。文献[1]通过将人工神经网络增加为除扫描用户、主机系统和目标系统配置文件异常检测组件之外的第3个组件,把机器学习算法应用于入侵检测领域。此后研究者将机器学习应用到入侵检测中,如支持向量机(Support Vetor Machine,SVM)[2]、K最近邻(K-Nearest Neighbor,KNN)[3]、决策树、随机森林和XGBoost等都凭借高识别率成为核心算法,但在后续的研究中均被发现存在不足。随着谷歌AlphaGo击败人类围棋选手李世石,深度学习成为人工智能领域的研究热点,也成为入侵检测中的重要技术[4]。

增量学习[5-6]是一种机器学习方法,其输入的数据被不断用于扩展现有模型的知识,即进一步训练模型。它代表了监督学习和无监督学习的动态技术,当训练数据逐渐增加或数据大小超出系统内存限制时,可以应用此方法对持续增加的数据监控和切片,并对切片后的部分数据进行训练,直到训练完所有数据。学习率控制新数据的适应速率,同时也控制系统与旧数据的相关性,然而对新知识的学习必然导致对旧知识的遗忘。可设置永不遗忘其所学习的知识,应用此类设置的算法被称为稳定的增量机器学习算法。

将深度学习算法应用于入侵检测可有效提高准确率并降低误报率,但深度学习算法复杂度较高,计算开销庞大,而在大数据应用场景下,多数安全设备不配备高性能显卡,即使应用深度学习算法也无法即时判断流量。与此相比,机器学习中的经典算法SVM和KNN算法具有算法简单、消耗资源少的优势。因此,本文在增量学习框架下将上述2种算法相结合,设计IL-SVM-KNN分类器,并使用KDD CUP99和NSL-KDD入侵检测数据集对其性能进行验证。

1 相关知识

1.1 SVM与KNN算法

SVM模型将实例表示为空间中的点,计算得出的映射以尽可能宽的间隔将各个类别的实例分开。当待分类的数据距离超平面较远时,SVM算法可准确分类,但当距离较近小于某阈值时,其分类效果并不理想[2,7]。在KNN分类中,对象的类别判定为K个最近邻居(K是正整数,通常较小)票数最多的类别。如果K=1,则对象的类别由最近的节点直接分配。KNN算法具有训练时间短、可轻松处理大数据和增量数据并且避免参数的过度拟合的优点。然而在数据不断增加的情况下,其产生的巨大的搜索空间导致算法耗时长,无法保证实时性。针对这一缺陷,本文将k维树作为数据结构,用以缩短分类所产生的耗时[8-9]。

1.2 k维树

k维树的数据结构可解决多维欧氏空间中的最近邻问题。k维树是一个二叉树,其中每个节点是一个k维点。k维树将数据集分层划分为小单元格以确保快速访问。本文对数据集按照不同维度递归地分配数据集,使用中间值作为每个级别的枢轴来构建k维树。每个非叶节点都是超平面,它将空间划分为2个部分,称为半空间。该超平面左侧的点由该节点的左子树表示,超平面右侧的点由右子树表示。左子树中显示的值小于该维度中的数据点,值更大的点位于右子树。将这些子树再次分成两半,并沿着不同的维度划分超平面[10]。

1.3 k维树中的K最近邻搜索

为从k维树T中搜索查询点Q的最近邻居,算法从最近邻居的估计点来遍历k维树并更新估计点。对于任何的非叶子节点,如果存在比当前最佳估计E更接近查询点Q的点,则它必须满足位于球心为Q、半径小于Q、E间距离的超球体中。如果这个超球体与当前节点的另一个半平面(即不是E的半平面)相交,那么结果就不在当前节点的子树中。当涉及K最近邻居查询时,需要维护容量为K的有界优先队列,以记录K个最近邻居的当前估计值,而不是单个估计点。一个新元素被添加到有界优先队列时,如果队列已满,那么具有最高优先级的元素将在插入发生之前从有界优先队列中删除。在KNN查询的情况下,离查询点Q更远的元素在有界优先队列中具有更高的优先级。

2 IL-SVM-KNN分类器设计

国内外研究者对KNN和SVM算法进行了大量的研究,提出的改进算法可解决部分难题。文献[11]引入双联支持向量机到入侵检测系统中,通过双联支持向量机构造2个较小的凸二次优化来解决分类问题。实验结果表明,基于双联支持向量机的入侵检测相比传统SVM算法,可以提高准确率,同时也可减少训练时间。文献[12]提出一种基于候选支持向量的增量SVM算法(CSV-ISVM),该算法实现了增量SVM分类的全过程。实验结果和性能分析表明,CSV-ISVM算法优于一般的ISVM分类算法,适用于实时网络入侵检测。文献[13]针对KNN算法在数据样本稀疏、类内数据频次差距较大的情况下分类不平衡的问题,提出稀有近邻算法KRNN,形成动态查询邻域,并进一步调整后验概率估计以偏向稀有类别的分类。KRNN算法显著提高了KNN对稀有类别的分类准确性,并且性能优于重新采样和成本敏感的学习策略。文献[14]通过研究传统KNN算法,设计基于增量学习的三支决策KNN算法,将数据分成数据流,进而利用基于三支决策KNN算法的模型处理数据。实验结果表明,该算法性能优于传统KNN算法和改进的2个KNN算法。

运用SVM和KNN算法实现增量学习可以提高分类性能,但2个算法本身各有缺陷。因此,本文在增量学习的框架下将这两种算法进行结合。增量学习具体体现在训练结束后和应用模型分类后依旧可以接收训练数据,在所学知识基础上继续学习,避免了在非增量学习算法中因学习新知识导致旧知识重复学习的问题。本文把待分类数据根据KNN算法和SVM算法所得的结果分为3种情况,再依据不同情况应用不同的分类策略。增量学习框架和本文设计的IL-SVM-KNN分类器模型如图1和图2所示。

图1 增量学习框架

图2 IL-SVM-KNN分类器模型

2.1 训练阶段

初始化训练数据集,提取数据集中每个数据的特征值,作为k维树的节点,生成KNN算法部分的平衡k维树。在SVM算法部分,依据数据的特征值聚类,每两个类之间找到合适的点,计算超平面和两点到超平面间的距离。此时的数据集是分类器最原始的知识库。将增量数据作为新学习的知识加入已存在的知识库中。依旧提取特征值,但要在k维树中找到每个数据合适的位置,插入节点并调整成平衡k维树。SVM算法部分同样依据特征值聚类,但要在2个类之间重新选取两点,更新超平面和两点到超平面的距离。

2.2 分类阶段

提取测试数据集中每个数据的特征值插入平衡k维树中,使用KNN算法搜索测试数据的K个最近节点,如果这些节点都有同样的标签,则完成一次分类,如图3中的A部分所示;如果这些节点中有不止一种标签,则使用SVM算法求出分隔2个类别的超平面,计算节点与超平面的距离,如果距离大于预设的阈值,使用SVM算法进行分类,如图3中的B部分所示;否则采用KNN算法投票分类,如图3中的C部分所示[15]。

图3 IL-SVM-KNN分类的3种情况

IL-SVM-KNN分类器的算法伪代码如下:

算法1KNN-SVM(test_data[ ],k_neighbors[ ],kdtree[ ],dist)

1.for i in test_data do

2.Insert into kdtree;

3.Searching k-nearest-neighbors;

4.if every k_neighbors[j].label is all the same then

5.Test_data[i].label=k_neighbors[j].label;

6.else if every k_neighbors[j].label is not all the same then

7.calculate the hyperplane;

8.calculate the distance between test_data[i] and hyperplane;

9.if the distance >dist then

10.use SVM classifier;

11.else if the distance <= dist then

12.use KNN classifier;

13.end if

14.end if

15.end for

3 实验与结果分析

3.1 实验数据

本文使用KDD CUP99和NSL-KDD数据集作为实验数据。KDD CUP99数据集内数据规模庞大,包含约5×106条训练数据和约3×105条测试数据,利于应用增量学习算法。每条数据为一个TCP或UDP的网络连接,每条连接的最后一项被标记为正常或异常,其中异常又分为4类,分别为DoS、R2L、U2R和Probing。每类又包含多种类型的攻击,共39种攻击,其中22种出现在训练数据中,17种出现在测试数据中。除去最后一项,每条连接有41项特征,包括9项连接类型特征、13项连接内容特征、9项时间流量特征和10项主机流量特征[16]。但KDD CUP99数据集有缺陷,主要是存在大量冗余记录,导致学习算法偏向于频繁记录,从而阻止算法学习在异常流量中占比较少的U2R攻击和R2L攻击。此外,在测试集中存在的这些重复记录将导致算法的评估结果产生偏差,即对频繁出现的记录有更高的检测率[17-19]。NSL-KDD数据集包含1.2×105条训练数据和2×104条测试数据,依然采用KDD CUP99的数据格式,但删除了KDD CUP99训练和测试数据的冗余,从而提高了判别算法优劣的区分度,同时也降低了实验成本。

3.2 实验环境

本文实验环境为:CPU主频为3.6 GHz的Intel Core i7-9700K,显卡为显存11 GB的Nvidia Geforce GTX 1080Ti,内存大小为16 GB的Ubuntu 18.04系统。

3.3 评价指标

本文通过混淆矩阵计算准确率A、精确率P和召回率R的数值,最终使用F1值F1作为分类器的评价指标。

其中:TP表示待分类样本为正,分类后标记为正;FN表示待分类样本为正,分类后标记为负;TN表示待分类样本为负,分类后标记为负;FP表示待分类样本为负,分类后标记为正。

F1值为精确率和召回率的调和平均值,其值在0～1之间,1代表最佳,0代表最差。本文实验所定义的混淆矩阵如图4所示。

图4 混淆矩阵定义

3.4 数据预处理

数据预处理包括降维、One-hot编码和合并分类3个部分。

1)降维。在将训练数据提供给机器学习算法之前,可通过降维来降低训练数据的维度。降维使数据占用更少的磁盘和内存空间,从而加快算法运行速度,降低计算成本,也可以降低分类错误的可能性。因此,在一般情况下,通过降维能使算法表现出更好的性能。对特征service通过合并特征进行降维,ntpu、urhi、tftpu、redi对应的标签都是normal,可以将其合并,而pmdump、http2784、harvest、aol、http_8001对应的标签都是satan,也可以将其合并。

2)One-hot编码。对protocoltype、service、flag3个特征进行One-hot编码,例如把特征protocoltype的3个值tcp、udp、icmp编码为001、010、100。

3)合并分类。根据官方提供的攻击分类划分,把正常流量和39种攻击类型共分为5类,分别为Normal、DoS、R2L、U2R、Probing,分别标记为0～4。

3.5 实验结果

3.5.1 KDD CUP99数据集实验结果对比

在KDD CUP99数据集上关于准确率的实验以每104条测试集数据计算准确率,各算法的准确率曲线如图5和图6所示,可以看出,IL-SVM-KNN算法的准确率高,在数据量达到2×105条之后准确率趋于稳定,最终计算出的平均准确率为0.999 84。IL-SVM-KNN算法与决策树、随机森林和XGBoost 3种机器学习算法的精确率如图7所示,可见本文算法也具有优势。各算法的具体性能指标如表1所示,可见IL-SVM-KNN算法的F1值为0.81,在4种算法中得分最高。决策树和随机森林在U2R攻击上的精确率表现不佳,而其他3种算法在U2R和R2L攻击分类方面的召回率的得分均低于0.2,明显低于IL-SVM-KNN算法的0.58。

图5 KDD CUP99数据集中IL-SVM-KNN、KNN与SVM算法的准确率

图6 KDD CUP99数据集中IL-SVM-KNN与3种机器学习算法的准确率

图7 KDD CUP99数据集中IL-SVM-KNN与3种机器学习算法的精确率

表1 KDD CUP99数据集中IL-SVM-KNN与3种机器学习算法的评价指标

为与经典深度学习算法中的卷积神经网络(Convolutional Neural Network,CNN)进行比较,本文实现了双层结构的卷积神经网络[20-22]。每层结构包括卷积层、优化函数和激活函数,本文使用批标准化函数作为优化函数,使用线性整流函数作为激活函数。在神经网络的最后使用最大池化作为池化层。考虑到多数入侵检测设备不会配备高性能显卡,本文分别使用CPU和GPU进行对比实验,实验结果如表2所示。可以看出,IL-SVM-KNN算法与用GPU运行的CNN算法相比,在准确率相近的情况下,耗时是CNN的1/2,占用内存仅为CNN的1/3。在用CPU运行CNN算法时,仅一次迭代就耗时20 min,响应速度过慢,不具备对比意义,因此,中止CNN在CPU上运行的实验。

表2 KDD CUP99数据集中IL-SVM-KNN与深度学习CNN算法的检测性能

由于KDD CUP99数据量庞大,NSL-KDD数据量少,因此关于运用增量学习能否提升准确率的研究仅在KDD CUP99数据集上进行。实验把KDD CUP99数据集中完整的训练数据分为4份,进行4次实验。第1次学习训练数据的1/4测试训练效果,计算准确率,之后的每次实验在原有学习成果的基础上继续学习1/4的训练数据,直至学完整个训练集。实验结果如图8所示,可以看出,随着所学习的训练数据增多,测试的准确率也随之提升,说明增量学习有助于提升分类器的准确率。本文实验增量学习的学习率设定为0.01,由于IL-SVM-KNN算法并非稳定的增量学习算法,在学习新知识的同时不可避免地造成对旧有知识的遗忘,因此增量学习算法即使学习了整个训练集,计算得出的准确率也会比非增量学习下同一算法的准确率稍有下降。但面对庞大的数据量,非增量学习算法静态学习需耗费大量内存,对设备硬件的要求较高。而增量学习算法实现了动态学习,可搭载在相对廉价的设备上,虽然要付出降低准确率的代价,但应用增量学习依然有意义。

图8 KDD CUP99数据集中IL-SVM-KNN算法与非增量SVM-KNN算法的准确率

3.5.2 NSL-KDD数据集实验结果对比

在NSL-KDD数据集上关于准确率的实验以每103条测试集数据计算准确率,各算法的准确率曲线如图9和图10所示。鉴于KDD CUP99数据集存在的局限性,IL-SVM-KNN算法、SVM和KNN算法检测的准确率均有不同程度的下降,但IL-SVM-KNN算法的准确率下降幅度最小,最终计算出的平均准确率为0.91045,而决策树、随机森林和XGBoost算法的平均准确率均在0.8左右。IL-SVM-KNN算法与3种机器学习算法的精确率如图11所示,可以看出,NSL-KDD数据集在大量删除存在于前三类攻击中的冗余记录后,后两类攻击记录占比增大,其他3种算法分类性能均有不同程度的提升。各算法的具体性能指标如表3所示,可见IL-SVM-KNN算法在NSL-KDD数据集的F1值为0.79,依然高于3种机器算法。

图9 NSL-KDD数据集中IL-SVM-KNN、KNN与SVM算法的准确率

图10 NSL-KDD数据集中IL-SVM-KNN与3种机器学习算法的准确率

图11 NSL-KDD数据集中IL-SVM-KNN与3种机器学习算法的精确率

表3 NSL-KDD数据集中IL-SVM-KNN与3种机器学习算法的评价指标

IL-SVM-KNN与深度学习CNN算法的检测性能如表4所示,可以看出,IL-SVM-KNN算法的准确率与CNN算法的准确率基本持平,相比于用GPU实现的CNN,极大地缩减了内存的占用空间,且耗时低。而在CPU上实现的CNN算法,由于算法其参数批规模(batch-size)的要求,模型只能从训练集中分批读入数据,因此尽管内存占用少,但在耗时上大幅增加。

表4 NSL-KDD数据集中IL-SVM-KNN与深度学习CNN算法的检测性能

4 结束语

本文在SVM和KNN算法基础上融合增量学习思想,提出适用于网络入侵检测的IL-SVM-KNN算法。实验结果表明,该算法的二分类准确率优于SVM和KNN算法,五分类准确率优于决策树、随机森林和XGBoost算法。本文算法可以避免时间与资源的矛盾,加快网络流量识别速度,满足入侵检测的实时性要求,具有准确率高、误报率低和轻量化的特点,适合部署在计算资源有限的场景。本文仅使用两层结构的卷积神经网络做对比实验,后续将采用其他深度学习算法进行比较。此外,当算法学习到不良数据时会造成系统性能下降,如何管控和处理此类数据,也将是下一步的研究方向。