基于ME-PGNMF的异常流量检测方法

,,

(火箭军工程大学 信息工程系,西安 710025)

0 概述

随着网络技术的发展和普及,网络流量的规模越来越大,类型也越来越多,网络安全问题日益突出。但不论何种网络异常都会对网络流量产生影响,因此,网络流量异常检测的研究越来越受到重视。网络流量异常检测是指通过对网络流量历史活动的观测建立网络流量的正常模式,和当前网络流量活动比较发现异常。其优点是可以发现新的异常,但也存在不少问题。

当前骨干网的网络活动特点是流量大、流速快、数据维数高,要进行数据检测,数据的降维处理成为一个必要的过程。文献[1]采用基于主成分分析(Principal Component Analysis,PCA)的子空间方法,利用PCA对数据降维的能力将流量矩阵分离为正常子空间和异常子空间,通过设置阈值,对大流量的异常取得较好的检测效果。文献[2]同时考虑流量的时间和空间相关性,综合利用小波变换具有的多尺度建模能力和PCA具有的降维能力对正常流量进行建模,实现异常检测。但PCA方法仍存在较多问题:PCA追求的是全局最优解,导致对局部特征提取不充分,影响检测精度;系数向量中存在负值,但流量不可能为负,可解释性差;PCA方法的效果受主成分的选择和阈值设定的影响很大。鉴于以上问题,文献[3]将非负矩阵分解(Non-negative Matrix Factorization,NMF) 方法用于异常流量检测。主要特点是采用非负子空间方法提取流量矩阵中的主要时变模式,构成正常子空间,得到重构矩阵和残余矩阵,然后应用Q图进行异常点检测。该方法有更强的特征提取能力,由于其非负性,可解释性也更强,实验表明比PCA方法在检测精度方面有明显提高。

传统的基于统计的网络流量异常检测方法多是对流量特性进行分析[4]。文献[5]总结了基于熵的异常流量检测的优点:在数据流上有高效的熵值计算算法,且有足够的精度保证;基于熵的检测方法提供了一种更细粒度的信息,能够检测出更加隐蔽的异常类型;采样对基于熵的检测方法精度影响并不明显;正常情况下熵值相对流量幅值更稳定。

文献[6]用增量投影非负矩阵分解对NMF方法进行改进,提高了NMF的效率。文献[7]虽利用了流量的熵值特征,但仅利用流量幅值的熵,流量数据利用不充分。为此,本文提出一种将特征熵和NMF相结合的方法对此类异常流量检测方法进行改进。

1 多维熵矩阵和PGNMF算法

1.1 多维熵矩阵

信息熵是信息论中用于度量信息量的一个概念,信息熵标志着所含信息量的多少,是对系统不确定性的描述。用信息熵来描述网络流量的特征,对流量数据预处理,不仅增强了对网络流量异常的检测能力,而且方便了流量异常的分类。

基于熵的异常检测系统的主要思想是:一旦有异常流量发生,总体流量的熵值应该会随之发生变化,通过熵值的变化能够检测出该异常。文献[8]把流量聚集成网络流,针对每个流在源/目IP,源/目端口维度上分别计算熵值,然后采用PCA方法进行异常检测;文献[9]提出在高速IP网络上利用熵值来检测蠕虫爆发和流量异常,均取得较好的效果。文献[10]基于最大熵原理,通过比较当前分布和基准分布的差异来进行异常检测。文献[11]在多个不同维度上采用熵度量流量数据的分布特征,在每个时间窗口上把不同维度熵值序列排列成检测向量,提出多窗口关联检测算法,既降低了计算复杂度,也提高了检测效率。以上方法从不同层面都验证了熵特征在异常流量检测方面的良好性能。

把采集到的Netflow流量数据当作离散信息源,把数据中的各个属性看作是一组随机事件,就可以对它的信息熵进行分析。假设某一时段内目的IP的集合用X表示,i表示有i个不同的目的IP,ni表示第i个目的IP出现的次数:X={ni,i=1,2,…,N}。那么该时段内目的IP(X)的信息熵定义如式(1)所示,本文使用信息熵的指标有源/目的IP、源/目的端口,如下:

(1)

不同指标熵的计算方法可参考式(1)。表1反映的是不同异常对流量各属性熵值的影响。

为充分利用流量的时间和空间相关性,在多维特征熵的基础上构建多维熵矩阵。传统流量矩阵描述一个网络中所有源节点和目的节点(Origin-Destination, OD)对之间的流量情况,主要反映了目标网络各OD对之间流量分布情况。主要包括链路级、路由级和PoP(Point of Presence)级流量矩阵。单一时刻的流量矩阵表示为一个m行的列向量:(x1,x2,…,xn)T,其中。m表示OD对的数量。不同的列代表不同时刻。则在有m个OD对的网络中所有n个时刻的流量矩阵如式(2)所示,矩阵Xmn表示第m个OD对在n时刻的流量情况,多维熵矩阵就是将流量指标修改为源/目的IP熵,源/目的端口熵等指标得到四维熵矩阵。

(2)

1.2 PGNMF算法

NMF[12]起源于主成分分析,1999年Lee和Seung在Nature上发表了NMF算法,该算法是在矩阵中所有元素均为非负的条件下对其实现非负分解.具有可解释性、占用存储空间少等优点。NMF可以定义为给定一个n×m阶非负矩阵Vg和一个正整数r,将矩阵Vg分解为n×r阶的矩阵Wg和r×m阶的矩阵Hg的乘积,如式(3)所示为得到近似的分解结果,需要定义一个目标函数:

Vm×n≈Wm×r×Hr×n

(3)

(4)

来量化矩阵Vg与矩阵Wg×Hg的逼近程度,如式(4)所示。式(4)需满足矩阵Wia≥0,Hbj≥0,∀i,a,b,j,是一个带约束的非线性规划问题。利用迭代的方法求解矩阵Wg和Hg。文献[3]给出了带约束条件下用拉格朗日算子解得的矩阵Wg和Hg的更新方程,如下:

(5)

NMF算法可描述如下:

1)初始化矩阵Wia≥0,Hbj≥0,∀i,a,b,j。

2)设置基矩阵维数r和最大迭代次数k,更新矩阵Wg和Hg,更新规则为式(5)。

3)循环执行式(5),至算法收敛。

但NMF算法复杂度高,不利于异常流量检测对实时性的要求,因此,采用投影梯度(Projected Gradient, PG)优化方法降低NMF迭代的复杂度。PGNMF方法具物理意义明确、稀疏性好、以及耗时少等特点,但梯度投影法使用另外的迭代规则。文献[9]提出的一种梯度投影法,使迭代的复杂度大为降低且更新得到的解收敛。算法基本思想如下:

将式(4)改写为如下形式:

(6)

(7)

(8)

1)初始化矩阵Wia≥0,Hbj≥0,∀i,a,b,j。

2)设置基矩阵维数r和最大迭代次数k,通过迭代条件式(8),利用梯度投影方法求解式(6)、式(7),得到矩阵Wg和Hg的更新关系。

3)重复步骤(2),至算法收敛,得到矩阵Wg和Hg。

2 基于ME-PGNMF异常流量检测模型

基于ME-PGNMF的异常流量检测方法主要分为构建多维熵矩阵、获取残差矩阵、异常点检测。如图1所示为异常流量检测的基本流程。

图1 异常流量检测基本流程

2.1 多维熵矩阵构建

若矩阵Xm×n表示待检测的目标网络流量矩阵,则m表示目标网络的OD对的数量,n表示检测时间段内的采样周期数。根据信息熵定义,求出网络流量在n个周期内源/目的IP、源/目的端口4个属性的熵值序列,并标准化处理,得到4个大小为m×n的标准化熵矩阵。将4个维度矩阵依次按行相接得到一个4m×n的多维熵矩阵,用矩阵V4m×n表示。矩阵V4m×n的列向量表示某一检测周期内不同OD对4种属性熵值的变化,行向量表示某一OD对不同周期某一属性熵值变化。

2.2 残差矩阵获取

若将多维熵矩阵中第i个位置的向量看做是d维空间的点,每一个点的状态特征用多维熵特征表示。多维熵矩阵可以用r维的子空间表示,满足条件的r维子空间为多维熵矩阵的特征子空间,而r维子空间可以通过PGNMF算法进行构建。选取子空间维数r和迭代次数k,通过构建r维特征子空间,得到残差距阵。残差矩阵的获取分2个步骤:提取正常成分和获取残余成分。

首先提取正常成分,对多维熵矩阵V进行PGNMF算法分解之后可以获得矩阵W和矩阵H,其中基矩阵Wg=(w1,w2,…,wr)的每一列代表的是r维子空间的基向量,系数矩阵Hg=(h1,h2,…,hn)中的每一列表示的是r维子空间的系数向量,而每一个基向量捕获的是目标网络各OD对的一种状态模式。矩阵Vg≈Wg×Hg代表的是目标网络的正常状态成分。

2.3 异常点检测

得到残差矩阵后,如果某周期内发生了异常,其对应的残差向量也会发生明显变化。本文引入Q统计量来监测残差向量的变化,Q统计量的时序图亦称平方预测误差(Squared Prediction Error,SPE)图[14],是多元统计过程控制图的一种,主要监测输入多变量的数据结构是否变化,残差向量中包含源/目的IP、源/目的端口熵4个变量,每个残差向量代表一个采样点。

Q统计量在i时刻的值Qi是个标量,用残余向量中所有元素的平方和(SSE)来衡量,当检验水平为α时,控制限Qα可按式(9)计算:

(9)

其中,λj为多维熵矩阵V第j个特征值,cα是正态分布中1-α分位数,α通常取0.001。若Qi

分析以上3个步骤可以发现基于ME-PGNMF的异常流量检测方法有以下3个关键问题:1)PGNMF算法的效果受初始参数r和k影响较大,如何选取合理的参数保证检测效果。2)r维特征子空间是否能还原出流量的正常状态模式,从而保证得到的残余矩阵包含了异常状态模式。3)用Q统计量对残余向量进行多元统计过程控制是否能检测出异常。对于问题1)可通过矩阵还原性来选取参数,问题2)一方面取决于矩阵还原性,同时取决于检测效果,而问题3主要取决于检测效果。综上,在进行实验设计和分析时要从以上3个问题进行综合考虑,不仅要分析最终的检测效果,还要关注过程中的矩阵还原性指标。

3 实测数据实验及结果分析

3.1 实验数据与方法

为了验证分析ME-PGNMF算法在异常流量检测方面的有效性,实验实测数据来自Abilene骨干网在2009年3月1日—2009年3月7日一周所采集的流量矩阵数据。该网络是美国的IP骨干网络,每个节点对应一个城市,由12个节点组成,共有12×12=144条OD流,所有节点通过配置NetFlow来收集真实OD流。其中,采集间隔为5 min,这样一周所采集的次数为7×24×60/5=2 016,而OD流的数目为144个,因此,该OD流矩阵为一个144×2016的矩阵。在OD流矩阵的基础上,计算源/目的IP、源/目的端口4个同样大小的熵矩阵,标准化处理后,按行相接得到576×2 016的多维熵矩阵。表2所示为本文实验的具体数据集形式。

但Abilene数据集中并无明显异常,因此采用人为注入异常流量的方法进行实验。为方便和PCA、NMF等方法对比,采用和文献[3]相似的异常注入方式。在实验中,采样点之间间隔为5 min,异常注入过程如下:从第300个采样点到第800个采样点期间,每隔50个采样点轮流依次注入一次低速DDOS攻击和一次DDOS攻击,并且2种攻击都持续30 min(持续6个采样点);从第1 000个～第1 500个采样点里,每隔50个采样点注入一次端口扫描,攻击持续时间为30 min(持续6个采样点);从第1 700个～第1 900个采样点期间,持续注入蠕虫攻击,包括个感染到爆发的完整过程(持续200个采样点)。

3.2 参数分析与选择

非负矩阵分解算法的一个非常重要的参数是基矩阵维数r的选择,参数r主要影响分解后的矩阵对原矩阵的还原性,是影响最终检测结果的重要因素。且参数r的选择受数据集特性影响较大。迭代次数k虽然在足够大的情况下能确保算法收敛,但k值过大会使算法的复杂性增大。鉴于以上情况以及数据集的相似性,对基于流量矩阵的NMF方法,参数选择参考文献[3],对基于流量熵矩阵的PGNMF方法,参数选择参考文献[15],本文重点分析基于多维熵矩阵的PGNMF方法的参数选择。

矩阵的还原性通常用式(10)来衡量:

(10)

为确定基矩阵维数r和合理的迭代次数k,为确保d收敛,首先设置最大的迭代次数k为500,r从2递增至20,寻求最优矩阵还原性的r。。实验对象为标准化后的576×2 016的多维熵矩阵,实验结果如图2所示。

图2 矩阵还原性d与维数r的关系

从图2和图3可以看出,基矩阵维数r设为12时,矩阵还原性d已基本稳定即d收敛,且此时收敛所需时间t还没有明显增加。结合图4,d收敛时所需的迭代次数k均未超过200,因此,最大迭代次数500未对实验造成影响。综合以上结果选取参数r为12,k为200。

图3 d收敛时,收敛时间t与维数r的关系

图4 d收敛时,不同维数r与迭代次数k的关系

3.3 实验结果及分析

对基于NMF的检测算法选择合适的基矩阵维数r和迭代次数k后,按表2算法与实验数据形式得到图3和表3、表4的实验结果。图3中直线代表控制限Qα,α取0.001,圆圈代表残余向量的Qi。表3检测率指标参考文献[16],为检测到的异常点与注入异常点的比,表4中误报率为注入异常时段内正常采样点报为异常的次数与正常采样点的比。

表3 不同方法对注入异常的检测率 %

表4 不同方法对注入异常的误报率 %

通过分析表3和图5～图8可以发现对于低速DDOS攻击,PCA方法检测效果最差,检测率接近于0,NMF和PGNMF方法检测效果也不明显检测率不足20%,分析原因主要是此类攻击并未明显引起流量变化,而这3种方法都是以流量为基础。对于端口扫描和普通DDOS攻击,几种方法都能不同程度的检测出来,其中,以ME-PGNMF方法效果最好,原因是该方法既有NMF方法局部特征提取能力强的优势,又以多维熵为基础,对异常流量的分辨能力有很大提高。最后,比较对蠕虫攻击的检测可以发现,PCA方法对攻击最不敏感,在第1 700个采样点攻击已出现,图5直到第1 780个采样点左右才有检测到的迹象,图6和图7中虽然在第1 700采样点已能检测到异常但并不稳定,依然有很多漏报点发生,直至第1 750采样点才稳定报出异常,只有ME-PGNMF方法最快对蠕虫攻击做出反应,且漏报点很少,分析原因,与蠕虫攻击在起始阶段对流量变化影响不大有关。

图5 PCA方法异常流量检测效果

图6 NMF方法异常流量检测效果

图7 PGNMF方法异常流量检测效果

图8 ME-PGNMF方法异常流量检测效果

为准确评价几种方法对注入异常的检测效果,分析表4的误报率可以看出,基于流量的方法对低速DDOS攻击不敏感,检测率和误报率都很低,对其他攻击流量,ME-PGNMF方法检测率有明显提高,误报率也没有明显上升。综合考虑3种攻击,ME-PGMF方法检测率有明显提高,同时误报率并无明显提升。对于蠕虫攻击,由于每一个采样点都注入异常,因此不存在把正常采样点报为异常点,即误报问题。

3.4 参数选择对实验结果的影响

在3.2节中分析了ME-PGNMF方法中参数选择对算法的影响,为直观体现参数r和k对实验结果的影响,通过设计不同的参数得到图9～图10所示的实验结果。可以看出,实验结果与参数分析基本一致。r为12,k为120(小于实验预设值200)都达到了实验的最佳效果,如果参数变大虽能达到检测效果,但运算的时间复杂度就会增加。

图9 k为200时,r与检测率的关系

图10 r为12时,k与检测率的关系

4 结束语

利用熵特征对异常流量的敏感性和PGNMF算法局部特征提取能力强、收敛速度快的特性,本文提出基于多维熵和PGNMF的网络异常流量检测方法。实验结果表明,与基于流量的检测方法相比,该方法对低流量异常更敏感,有利于发现隐蔽的流低速攻击,可以在蠕虫爆发的早期阶段及时发现,提高了检测率。下一步将改进数据输入形式,通过增量或其他方法,达到在线检测的目的。

[1] LAKHINA A,CROVELLA M,DIOT C.Mining Anomalies Using Traffic Feature Distributions[J].Conference on Applications,2005,35(4):217-228.

[2] 钱叶魁,陈 鸣,叶立新,等.基于多尺度主成份的全网络异常检测方法[J].软件学报,2012,23(2):361-377.

[3] 魏祥麟,陈 鸣,张国敏.NMF-NAD:基于NMF的全网络流量异常检测方法[J].通信学报,2012,33(4):54-61.

[4] 王 浩.针对TCP的低速DDoS解析及防御策略[J].计算机工程,2009,35(13):122-124.

[5] 郑黎明.大规模通信网络流量异常检测与优化[D].长沙:国防科学技术大学,2012.

[6] 柏 骏,夏靖波,吴吉祥,等.ODA-IPNMF:一种在线全网络流量异常检测方法[J].哈尔滨工业大学学报,2015,47(5):104-109.

[7] 王晓鸽.基于PGM-NMF的网络流量异常检测研究[J].电子科技,2014,27(5):175-178.

[8] ANUKOOLL,MARK C,CHRISTOPHE D.Mining Anomalies Using Traffic Feature Distributions[C]//Proceedings of ACM SIUCOMM’05.New York,USA:ACM Press,2005:217-228.

[9] WAGNER A,PLANNER B.Entropy Based Worm and Anomaly Detection in Fast IP Networks[C]//Proceedings of the 14th IEEE International Workshops on Enabling Technologies:Infrastructure for Collaborative Enterprise.Washington D.C.,USA:IEEE Press,2005:172-177.

[10] YU Gu,ANDREW M,DON T.Detecting Anomalies in Network Traffic Using Maximum Entropy Estimation[C]//Proceedings of the 5th ACM SIUCOMM Conference on Internet Measurement.New York,USA:ACM Press,2005:345-350.

[11] 郑黎明,邹 鹏,韩伟红,等.基于多维嫡值分类的骨干网流量异常检测研究[J].计算机研究与发展,2012,49(9):1972-1981.

[12] LEE D,SEUNG H S.Learning the Parts of Objects by Non-negative Matrix Factorization[J].Nature,1999,401(6755):788-791.

[13] LINC J.Projected Gradient Methods for Non-negative Matrix Factorization[J].Neural Computation,2007,19(10):2756-2779.

[14] 王兆军,邹长亮,李忠华,等.统计质量控制图理论与方法[M].北京:科学出版社,2013.

[15] 王晓鸽.基于流量矩阵的网络入侵检测研究[D].兰州:兰州交通大学,2014.

[16] 许 倩,程东年.基于层次聚类的网络流量异常分类算法[J].计算机工程,2012,38(23):131-136.