一种基于Chebyshev的网络流量异常检测方法

胡　平　叶　坤　刘瑞琴

(南京工业大学电子与信息工程学院　江苏 南京 211816)



一种基于Chebyshev的网络流量异常检测方法

胡平叶坤刘瑞琴

(南京工业大学电子与信息工程学院江苏 南京 211816)

摘要网络安全问题已日趋频繁出现在人们的生产与生活当中，并越来越受到重视。为了能及时有效地预警网络异常，提出一种基于网络流量的异常检测方法，并针对流量数据的特性而采用时间序列的检测方式。在滑动窗口内先对序列进行格拉布斯坏点数据预处理，再利用欧式距离提前判定和切比雪夫多项式系数判定相结合方法，对其进行快速异常检测。仿真实验分析表明：在一定条件下，该算法在保证较好的检测精度的前提下，仍具有较快的检测速度，可以满足实时检测的需要。

关键词网络流量数据异常数据切比雪夫多项式时间序列格拉布斯准则

0引言

信息科技飞速发展，智能化、便捷化的计算机技术越来越受到人们的关注。而计算机网络作为信息时代的产物，在科技高速发展的同时被迅速普及，人们对其的需求也日益增加，其规模也在不断地扩大。但互联网作为一个面向大众的开放系统，对信息的保密和系统安全的考虑并不完善，因而网络的安全问题日趋严峻，并且解决难度也越来越大。因此如何能较好地保证网络系统的稳定运行，成为一项至关重要的问题。

在网络安全领域中，检测、响应入侵[1]和攻击预测已经得到人们的广泛关注。目前，大多数网络入侵检测都是对数据进行事后分析，即攻击发生后，才能有所反应。这样很不利于异常的及时检测，也不利于网络的有效管理。因此，对于网络问题较好的解决方法之一就是采用安全预警的方式进行网络监测和管理，即试图在攻击发生之前，对其攻击发生的数量、趋势及时空特性进行预测。本文主要以网络流量作为衡量标准，通过对流量的实时监测[2]来发现异常，并提前预警，从而可以及时处理，防止网络流量异常向周围传播。又因网络流量具有数据流大且流速快的特点，为了解决这个问题，本文结合网络流量的时序特性，提出一种基于时间序列的网络异常检测方法，并将切比雪夫思想应用到时间序列的检测中，利用Chebyshev系数来进行快速检索，从而发现网络的异常时间段。

1相关研究

基于流量的异常检测分析方法主要分为静态检测和动态检测。静态检测主要根据预设的阈值进行判定。阈值可以为恒定阈值，也可以为自适应阈值。Maxion等人[3]应用自适应阈值方法，检测卡内基梅隆大学校园子网利用率和用户流量使用等数据，并设定阈值。一旦超出这个阈值，即判定为异常存在。Yusuke等人[4]应用类似方法，通过检测网络负载和数据包等观测数值，检测广播风暴等故障异常。而动态检测方法中，常用的有GLR(Generalizedlized likelihood Ratio)检测方法。如Fouzi 等人[5]使用基于PCA (Principal Component Analysis)的GLR假定检测，对比两个连续滑动窗口内流量，对滑动窗口内流量进行转换，拟合相似模型，进行统计故障检测。另一种是基于指数平滑技术的检测方法[6]。这种方法是基于简单统计模型进行预测，与回归模型不同的是，这种检测无需自身序列以外的序列信息，计算量较小，无需大量数据，只适用于序列值围绕自身均值上下波动的序列。还有一种是小波异常检测方法。钱叶魁等人[7]利用小波变换，对网络流量矩阵数据进行多尺度分析相关性，利用PCA方法证实流量矩阵数据在每个时间尺度上均具有空间相关性，从而进行全网络异常检测。面向安全检测法用的也很多，如Brian等人[8]提出的二元马尔科夫链检测算法，通过连续的时间序列表征状态，预测未来可能出现异常，从而进行安全检测。

以上所提的研究方法大多是针对数据流量的事后分析或是低维数据的检测，且计算的复杂度相对较高。而网络的时间序列流具有动态增长、高维、甚至是无限等特点。因此对序列中的数据只能一遍扫描，对时间间隔较远的数据采取逐步遗忘，即对序列数据的重视程度由近及远地降低。结合以上研究的优缺点，本文提出了一种基于时间序列的异常检测分析方法。主要采用时间滑动窗口机制对各站点的序列进行采集，并在每个窗口先对序列坏点进行处理。再采用基于欧氏距离的提前判定思想，利用切比雪夫系数进行序列间的匹配对比，若发现异常就记录下来。最后判定各站点在特定时段内的异常情况。

2问题描述

一般地，对网络用户的流量等相关情况的监测是以时间为标准进行的，并且这种流量型数据具有海量性、速度快等特点。因此，对这种具有时序特征[9]的数据，可以作如下定义：

定义1(时间序列)假设一个用户的检测数据在时刻ti以数值si的形式到达，则在时间T内，这些数据按照固定时间顺序排列得到的数据列值的集合，可记为：

S={(si,ti)|1≤i≤N}

={(s1,t1),(s2,t2),…,(si,ti),…,(sN,tN)}ti∈T

(1)

通常情况下，用户的网络流量数据由于其自身的无限性和不可重现性，数据一旦流过，我们就很难再获取到之前的数据信息进行检测。针对该情况，本文采用滑动窗口技术，利用窗口的滑动对数据进行类似分段的操作。这种近似查询的方法非常符合网络流量的检测处理，因为用户常常关心的是最近一段时间的信息情况而不是所有的数据信息情况。所以久远的数据对于最后的结果反而不具备一定的影响力。

滑动窗口技术在流型数据上有较为广泛的应用，并按照需求的不同主要分为三种类型：基于元组的滑动窗口、基于分区的滑动窗口和基于时间的滑动窗口。而在现实环境中，对用户流量数据序列都是以时间为单位进行监测的。因此本文采用时间滑动窗口，对流量数据在区域上进行限定，使查询操作被限定在一个窗口的范围内。一个基于时间的滑动窗口可被简单定义为：

定义2(时间滑动窗口)为了捕获到用户最新到达的网络流量数据信息，可将滑动窗口的输出与时间参数T的关系表示为：

R(τ)={S|∈S∧(τ′≤τ)∧(τ′≥max{τ-T,0})}

(2)

在定义2的关系式中，τ是滑动窗口的时间戳。当T=0时，R(τ)由流量数据序列S中带有τ的元素组成；当T=∞时，R(τ)由S中所有时间戳τ的元素组成，换句话说，流序列是没有通过时间滑动窗口进行处理的。

在网络监测时，都是在特定的时间间隔点进行相关数据信息的采集。因此在特定的时间段，监测的对象数是相等的，相当于对应的时间序列的长度也是相等的。若时间滑动窗口在特定时间长度T0的窗口下对流量序列进行滑动，将会截取长度w(w<

图1　监测网络的滑动窗口技术示意图

2.1数据预处理

(3)

定义3(坏点判定)假设在滑动窗口w范围内的一次监测的数据集合S中，置信区间α下对应的格拉布斯准则系数为g(w,α)(可由查表获得)，若在ti时刻网络流量数据si满足式(4)条件，则可被判定为坏点：

|si|>g(N,α)σ

(4)

其中，σ是对应集合的标准差，由上式得到的坏点si在实际检测中应剔除。但是为了便于后期的异常判定(保证在数量上相当)，在对比时，对于该坏点用整体序列的平均值来进行替补操作。对于剩下的集合中的数据继续重复使用格拉布斯准则进行坏点的判定，并进行均值替换，直至没有坏点为止。

2.2时间序列的切比雪夫逼近

在进行网络数据信息采集时，如果时间粒度足够细，则离散的序列数据点可被连续化[10]。这种对数据的线性化处理，不仅具有较强的直观性，还能更好更准确地将之与历史正常数据序列进行比较，从而检测出异常进行预警。

2.2.1切比雪夫多项式的相关介绍

为了更好地对序列进行线性逼近处理论述，首先介绍一下切比雪夫多项式的相关概念。

Pm(t)=cos(mcos-1(t))t∈[-1,1]

(5)

则由余弦函数的性质cosmθ+cos(m-2)θ=2cosθcos(m-1)θ，可将式(5)改写为：

Pm(t)=2tPm-1(t)-Pm-2(t)m≥2

(6)

定理1若Pm(t)是在t∈[-1,1]区间上的直交多项式，则两个直交多项式的内积满足：

证明令t=cosθ，由定义4中的式(5)，有：

(7)

由式(7)可知，任何一个函数可由切比雪夫多项式及相关系数叠加得到，且由相关的性质可知，取低次Chebyshev多项式作为数据的线性最小二次拟合的基函数效果较好。切式逼近法的同一级多项式是相同的，因此在做两个序列的相似性比较时，不需要将整个函数都求解出来，可以对比相关项的对应系数，近似地进行两序列的相似性(异常性)检索。

2.2.2时间序列的切比雪夫逼近

由于采集到的数据序列S={(si,ti)|1≤i≤N}是离散的。为了将其用切比雪夫多项式较好地表示出来，必须将时间域归整到要求的tci∈[-1,1]的区间内，并将离散序列表示为一个间隔函数的形式。以一个滑动窗口下采集到的序列长度w(即ti∈[t1,tw])作为参考，首先将区间[-1,1]划分为w个不相交的子区间，则可以作如式(8)转换：

(8)

(9)

一般地，在进行序列间相似性匹配检测时采用欧式距离的度量方式，即通过两序列在相同时刻一一对应的检测值间的距离累积和进行异常判定。本文也借鉴这种度量方式，并有如下定义。

(10)

推论1切比雪夫系数的欧式距离不大于序列间的欧式距离，即：

Discoe(CS,CQ)≤Diseuc(S,Q)

其中序列的欧式距离：

证明：

(11)

那么：

定义6(相异性判定)给定一个阈值ε，假设采集到的流量序列与对应标准数据库里的时间序列分别为S、Q，对于两序列的切比雪夫系数向量CS、CQ。若满足Discoe(CS,CQ)>ε条件，则当前序列S被认为是异常序列。

定理2(省略计算提前判定定理)若两序列的欧氏距离超过限定的阈值ε，则不需要进行切比雪夫系数的计算就可以判定该序列是异常序列。

证明：由推论1可知Discoe(CS,CQ)≤Diseuc(S,Q)，若Diseuc(S,Q)>ε，则必然有Discoe(CS,CQ)>ε，满足相异性的条件。因此可不用计算序列的切比雪夫系数，就可判定该序列为异常序列。

2.3算法描述

2.3.1算法步骤详述

第一阶段，在每个监测点处加一个如定义1的时间倾斜滑动窗口，通过该窗口对网络用户的流量使用情况进行实时监测。将滑动窗口内的流量序列按照定义3进行格拉布斯坏点判定。同时用本序列的均值进行坏点替换，对采集到的序列进行标准化，防止由于环境或其他机制导致监测的误差。

第二阶段，对于滑动窗口中经过坏点处理后的序列，根据定理2先进行Euclidean距离的预先判定：若超过阈值ε，则直接跳到下一窗口，并在该窗口内从第一阶段开始执行；若不大于阈值，则进行第三阶段切比雪夫思想的计算判定。

第三阶段，按照2.2.2节中的Chebyshev思想先将时间序列转化到[-1,1]的区间范围内，并按照步骤得到相关的连续函数φ(t)，同时计算出当前序列对应的切比雪夫系数CS。

第四阶段，将第三阶段中CS与标准库的CQ进行一一对应。根据定义5和推论1中的证明公式得出切比雪夫系数的欧氏距离Discoe(CS,CQ)，并进行定义6的阈值判定。若超过阈值ε，则被认为在当前滑动窗口的时间区间里发生流量的异常情况，从而判定该时间段内有网络异常，并进行上传预警；反之，则认为是无异常发生，继续进行监测。

2.3.2算法伪代码

假设被检测序列和标准库序列为S、Q，给定α，并查表得出相应的g(w,α)。

for ( k=1; k<= m; k++)

//m为窗口的总个数

{

Dist=0,flag=0;

for (i=0; i<= w;i++)

//w为窗口的大小

{

if (|si|>g(w,α)σ)

//格拉布斯判断

{

//均值替换

Dist +=(si-qi)2;

//计算欧式距离

if (Dist >ε) {flag =1; continue ;}

}

将ti转化到对应的[-1,1]时间区间Ii上；

将时间序列转换成Ii上的连续函数φs(t)；

将连续函数转换成切比雪夫多项式的各项Pj；

计算对应系数的距离差Dj+=[φs(ti)-φQ(ti)]Pj(ti)；

}

计算出Discoe(CS,CQ)；

if (Discoe(CS,CQ)>ε) flag=1；

//被标示为异常序列

}

3算法实验分析

本文采用Matlab 7.1进行一维网络流量数据的仿真实验。从逼近程度拟合度、精确度和检测时间效率等几个方面进行性能分析，来验证基于时间序列的网络流量异常检测算法的有效性。

3.1m阶不同取值的计算效率对比

为了能较好地验证本文所提算法的效率，对切比雪夫多项式的阶数m的取值的确定很有必要。因此，本小节对不同m取值下的逼近程度和计算时间效率(时间效率= 1-当前时间消耗/最大时间消耗)进行分析，以获得最佳阶数m。以30 s为一个滑动窗口对流量数据进行检测，并以[0,25]范围内的整数对该时间序列数据进行Chebyshev转换。由图2可看出，随着阶数的增加，CPU处理所消耗的时间会越来越长，致使计算时效逐渐变低。而逼近程度呈现一个类似抛物线的走势，并在m取值为5左右时，精确度达到90%以上。这是因为n较小时，拟合程度不够，而过大时，会引起与DWT(离散小波变换)[7]类似的高次振荡，甚至会产生极端病态的拟合效果。

图2　m阶取值对计算效率的影响

3.2精确度对比

以3.1节的仿真实验效果值(取m=5，以30 s滑动窗口)，对本文所提算法(N_Chebyshev)与其他几个相似性匹配算法在检测精度上进行对比。如图3所示的六组训练数据集的检测精度情况(检测精度是检测到的异常流量时间段序列个数与期望得到的异常序列个数之间的比值)，经典的DTW(Dynamic Time Warping)的检测精度是最高的。它主要是通过调整两序列时间点之间的对应关系，找出它们的最佳匹配路径，而不是像Euclidean距离那样需要两个点一一对应，从而弥补了欧式距离在相位变换上的缺陷。PAA[13]算法将每个等长分段内的均值作为该分段整体序列值，对于长序列的整体形态不能有一个较好的描述。这样在进行序列间距离计算时就会有较大的误差，并且在有坏点的情况下(数据集DS 5)，该种算法对序列的异常检测的错误率会更高。而本文所提的算法运用了Grrubs准则进行数据预处理。同时利用切比雪夫系数进行对比，在数据的拟合上有很好的效果，因此在滑动窗口大小内的序列检测精度与DTW算法基本保持一致。

图3　三种算法的检测精度

3.3时间消耗对比

如图4所示，是六组数据集在三种算法下的CPU时间消耗对比。经典的DTW算法的时间消耗最大，主要是因为它采用动态规划的方式对序列矩阵进行最优路径搜索，计算复杂度较高。虽然达到图3的检测精度，却是以时间消耗为代价的。而本文所提出的N_Chebyshev算法虽然没有PAA算法的运行速率快，但是对被监测序列采用了省略计算的欧式距离提前判定。在异常较明显的情况下，其判定速度接近或更优于PAA(数据集DS 4)，并且在取低阶Chebyshev系数时，在速度上有了一定的提升。比较三种算法的整体性能，N_Chebyshev算法既保证了检测精度，又较好地兼顾了时间效率。

图4　三种算法的CPU时间效率

4结语

本文提出了一种基于时间序列的网络流量异常检测算法。利用滑动窗口技术对流量数据进行实时监测，并在每个窗口内先对序列进行格拉布斯坏点数据预处理。再利用欧式距离提前判定和切比雪夫多项式系数判定相结合方法，对被监测流量序列进行快速异常检测。最后对整个站点进行总体判断。本算法在保持一定检测精度的情况下，保证了较高的检测速度。接下来的工作是将本文所提的算法与实际应用相结合，对m个窗口判断整个序列的相似度，判断某个站点的总体网络异常情况，并将多重属性、高维等因素考虑进去，从而使本文所提的算法能有更好的效用。

参考文献

[1] Sui Dan,Shang YanLing.Detection of Network Intrusion Based on a HMM Model[C]//Second International Conference on MultiMedia and Information Technology,Kaifeng,China,2010:286-289.

[2] 邹柏贤.一种网络异常实时检测方法[J].计算机学报,2003,26(8):940-947.

[3] Roy A Maxion,Frank E.Feather A Case Study of Ethernet Anomalies in a Distributed Computing Environment[J].IEEE Transactions on Reliability,1999,39(4):142-146.

[4] Yusuke Ide,Norio Konno,Naoki Masuda.Statistical Properties of a Generalized Threshold Network Model[J].Methodology and Computing in Applied Probability,2010,12(3):361-377.

[5] Fouzi Harrou,Mohamed N Nounou,Hazem N Nounou,et al.Statistical fault detection using PCA-based GLR hypothesis testing[J].Journal of Loss Prevention in the Process Industries,2013,26(1):129-139.

[6] Claudio Paulo Faustino,Camila Paiva Novaes,Carlos Alberto M Pinheiro,et al.Improving the performance of fuzzy rules-based forecasters through application of FCM algorithm[J].Artificial Intelligence Review,2014,41(2):287-300.

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

[8] Brian L Mark,Yariv Ephraim.An EM algorithm for continuous-time bivariate Markov chains[J].Computational Statistics & Data Analysis,2013,57(1):504-517.

[9] Tak-chung Fu.A review on time series data mining[J].Engineering Applications of Artificial Intelligence,2010,24(1):164-181.

[10] Hananeh Aliee,Hamid Reza Zarandi.A Fast and Accurate Fault Tree Analysis Based on Stochastic Logic Implemented on Field-Programmable Gate Arrays[J].IEEE Transaction on Reliability,2013,62(1):13-22.

[11] Cai Yuhan,Raymond Ng.Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials[C]//Proc. ACM SIGMOD, Paris, France,2004:599-610.

[12] John C Mason,David C Handscomb.Chebyshev Polynomials[M].Chapman & Hall/CRC,2003:131-133.

[13] Alessandro Cammerra,Themis Palpanas,Jin shieh,et al.iSAX 2.0:Indexing and Mining One Billion Time Series[C]//IEEE International Conference on Data Mining. Washington:IEEE,2010:1-13.

A NETWORK TRAFFIC ANOMALY DETECTION METHOD BASED ON CHEBYSHEV

Hu PingYe KunLiu Ruiqin

(SchoolofElectronicandInformationEngineering,NanjingUniversityofTechnology,Nanjing211816,Jiangsu,China)

AbstractNetwork security problem has been occurred in people’s production and life more frequently, and has attracted growing attention. For the purpose of effective forewarning the anomaly in networks, this paper proposes a network traffic-based anomaly detection algorithm. The algorithm adopts detection mode in time series for the characteristic of traffic data, and uses Grubbs criterion to preprocess the outlier data of the series within each sliding window first, then makes fast anomaly detection on it using the method of combining the early-judging with Euclidean distance and the judge with Chebyshev polynomials coefficient. The analysis of simulative experiment demonstrates that under certain conditions, the proposed algorithm has a faster detection speed while keeping preferable detection precision. It can meet the demands of real-time detection.

KeywordsNetwork traffic dataAbnormal dataChebyshev polynomialsTime seriesGrrubs criterion

收稿日期：2014-11-17。连云港市科技项目(SH1110)。胡平，教授，主研领域：网络系统，嵌入式系统。叶坤，硕士生。刘瑞琴，硕士生。

中图分类号TP301

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.05.032