一種基于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