基于通聯累積量的動態網絡異常檢測算法

賀　亮，褚衍杰，韓杰思

(盲信號處理重點實驗室，四川 成都 610041)

?

基于通聯累積量的動態網絡異常檢測算法

賀亮，褚衍杰，韓杰思

(盲信號處理重點實驗室，四川 成都 610041)

摘要：在網絡運維管理領域，最受關注的問題之一是如何及時發現網絡異常。針對現有方法難以發現異常的高頻次通聯行為的問題，提出一種基于統計模型的高頻通聯異常檢測方法，以冪律分布模型來描述網絡中節點數與頻繁通信次數之間的關系，通過線性回歸方法進行擬合，并將回歸誤差超出置信度范圍的網絡狀態判定為異常。此外，針對網絡中存在重點關注節點對的情況，給出其權重預分配方案；針對規模較小的網絡狀態，考慮其不完全服從冪律分布，給出樣本預篩選策略，用于降低對異常網絡狀態的虛警率。最終實驗結果表明，該方法在低頻次通聯異常與高頻次通聯異常條件下，均表現出較高的檢測率。

關鍵詞：動態復雜網絡；異常檢測；通聯累計量；線性回歸

0引言

隨著互聯網規模的急劇膨脹，網絡攻擊、計算機病毒等惡意行為造成的危害愈加嚴重，有必要針對這些網絡異常行為，研究快速、準確的檢測方法，以方便網絡管理者迅速發現網絡異常。在動態復雜網絡中，網絡節點數以及節點之間的通聯關系隨時間變化。一方面，異常檢測需要從眾多網絡節點中發現異常節點，從而維護網絡安全；另一方面，需要從網絡總體上判斷當前網絡是否異常，從而進一步采取相應措施，例如某局域網通聯數突然增加可能表示該網絡遭受到了網絡惡意攻擊入侵，網絡管理員需要進一步排查網絡中受到入侵的節點。

網絡異常是與網絡正常狀態相對的概念，異常檢測的一個基本思想，是通過網絡長期穩定的數據對網絡的正常行為進行建模，找出短期內與該模型偏離較為嚴重的網絡行為作為網絡異常[1]。

網絡中的異常種類較多，文獻[2]將其分為三類，包括：點異常，即局部異常；上下文異常，即異常與事件發生的時刻有關；聯合異常，即一段時間內的異常。文獻[3]通過時間序列分析的方法提取數據的微觀特征和異常。可以通過網絡的特征參數對異?，F象進行檢測，即測量網絡的結構特征監測網絡結構是否發生了顯著變化，從而發現異常。

網絡在運行時，一段時間內的通聯次數具有一定的規律，當通聯次數有顯著增加或減少時，說明網絡發生異常。例如，網絡中主機遭受病毒攻擊后，會頻繁發送數據包，引起網絡異常?？梢酝ㄟ^網絡正常運行時的數據總結網絡中通聯規律，設計異常檢測機制判斷網絡通聯異常。異常檢測機制可以應用到許多領域，例如，網絡管理員可以通過異常檢測機制及時發現網絡異常，從而對網絡中的異?，F象進行處理，監察部門可以通過網絡通聯異常，捕獲重要節點的行為。從數據獲取的角度看，收集網絡中的數據后可以進一步剔除異常數據，獲得較為合理的網絡數據，方便對網絡行為進行建模分析。

異常檢測方法主要分為兩類：基于統計模型的方法和基于距離的非參數化方法。統計模型方法主要是對網絡中的一些參數如結點的度、網絡中流量狀況等進行建模，得到模型參數后，找出不符合模型的數據點作為異常點[4]，非參數方法則是對網路進行聚類分析后判別網絡異常情況[5]。

統計模型方法中，文獻[6]采用了自回歸滑動平均模型(ARMA模型)，通過觀測網絡參數，劃分時間段構成時間序列，利用時間序列挖掘出的規律來找出異常數據。文獻[7-8]對時間序列進行相似性度量，從而根據兩個時間序列的距離來判斷是否為同一個時間序列數據，文獻[9-10]在此基礎上進行聚類分析，找出異常時間序列。文獻[11]提出的隨機圖模型中，給出網絡中結點度數服從泊松分布這一結論，文獻[12]提出的優選選擇模型，指出復雜網絡的節點度數分布是冪律分布，文獻[13]在大量數據集上面統計出圖的兩個基本規律：冪律特征以及有效直徑隨時間減小。文獻[14]在給出圖的相似度定義基礎上定義圖之間的距離，通過距離來判斷圖結構是否異常。文獻[15]通過挖掘網絡的模式，使用序列模式挖掘算法，挖掘網絡中頻繁出現并且具有先后關系的網絡拓撲結構，從而能夠挖掘出網絡演化規律[16]，找出相應的異常。

文獻[17]提出LRAD算法(Linear Regression Anomaly Detection)和iLRAD算法(Iterative Linear Regression Anomaly Detection)，將網絡通聯頻次發生顯著變化作為網絡異常，對網絡正常狀態下節點和邊數進行回歸建模，距離模型較遠的數據點作為異常數據點，iLRAD是LRAD的迭代版本，在每次迭代中，都刪除當前的異常點重新進行建模。但是，該方法只對網絡中兩個節點是否通信進行統計，并沒有考慮節點之間頻繁通信的情況，因此不能檢測該類異常。

本文在iLRAD算法的基礎上，設計檢測頻繁通聯異常的方法，將網絡中通聯頻次發生顯著變化作為網絡異常，提出通聯累積量檢測的LRAD算法 (cumulant Linear Regression Anomaly Detection，cLRAD)，考慮網絡中節點之間通信頻次作為通聯累積量進行異常檢測，還可以針對個別重要節點的通信設計權值，當該節點之間發生頻繁通信時，相應的異常可能性變大。例如，傳統MSTP(Multi-Service Transfer Platform)網絡不支持流量的統計與復用并存在多點到多點業務[18]無法進行通過流量進行異常檢測，本文方法可對此類網絡進行檢測。本文接下來的內容安排如下：首先，以冪律分布模型對網絡節點數與通聯累積量之間的關系進行建模，并在理論上證明其合理性；在此基礎上，給出cLRAD算法流程；最后，通過Enron公司郵件數據庫[19]進行實驗驗證并與iLRAD算法進行對比。

1冪律分布模型

1.1節點數與邊數的分布模型

社交網絡、Internet等典型網絡中，網絡節點數多，節點之間通聯規模大。已有研究表明，復雜網絡中節點數與邊數之間的關系服從冪律分布模型[20]，即：

其中，c,α均為常數，兩邊取對數得到：

logE(t)=a0logN(t)+b0

從而可以進行線性回歸分析對復雜網絡進行建模。另一方面，復雜網絡的度數分布滿足冪律(power law)[21]：

p(x=k)=cx-γ

文獻[22]給出了復雜網絡在允許節點自連接和節點間多次連接時的冪律分布推導。文獻[23]給出了復雜網絡在不允許節點之間只能單連接情況下冪律分布的推導。因此，可以根據復雜網絡中節點數與邊數的分布關系，判斷網絡是否異常。

1.2節點數與通聯累積量的分布模型

文獻[17]中提出iLRAD方法，該方法利用回歸模型，將網絡的節點個數，邊的個數以及節點的度等參數作為衡量網絡異常的指標。已有研究指出網絡中節點和邊的個數滿足冪律分布，在做適當變換后，可以利用線性回歸對兩個參數進行回歸分析。而實際網絡數據中，對于通聯關系，兩個節點可能會在短時間內頻繁通信，該頻繁通信可能代表著網絡異常，例如網絡遭受ARP攻擊后，一些節點會頻繁向其他節點發送數據請求通信，而上面的iLRAD方法對于發生在同一個窗口內的頻繁通信事件僅作一次統計，可能對丟失兩點之間頻繁通信導致的異常現象的漏警。

為了針對異常的高頻次通聯行為進行檢測，本文在iLRAD基礎上提出cLRAD方法，即對于網絡通信，對一段時間窗口內的節點之間的通信次數進行累加，作為通聯累積量?？梢宰C明，通聯累積量與節點仍然滿足冪律分布關系。采用相同的方法可以對頻繁發生通信的異常事件進行檢測。

對于具有N個節點的復雜網絡，假設任意兩個節點之間產生通聯的概率為p，并且兩個節點之間可以產生多次通聯，則任意兩個節點之間通聯累積量的期望值為：

因此對于N個節點的網絡具有的通聯累積量之和的期望值為：

對于復雜網絡，節點個數一般較大，因此可以認為E～cNα，即復雜網絡的通聯次數與節點數在取對數后仍然滿足線性關系。因此可以采用線性回歸的方法計算系統模型，從而找出距離模型較遠的異常點。

2基于通聯累積量的動態網絡異常檢測算法(cLRAD)

2.1cLRAD算法原理

cLRAD與iLRAD算法的基本原理大致相同，iLRAD是對網絡中節點之間的通聯關系和節點數進行回歸建模，而cLRAD則是對通聯累積量與節點數的關系進行建模。cLRAD算法首先統計各個時間窗內網絡的通聯累積量，對通聯累積量和節點數取對數后進行線性回歸，記通聯累積量取對數后的序列為{y1,y2,…yn}，節點數取對數后的序列為{x1,x2,…xn}，則線行回歸計算如下：

2.2針對小規模網絡狀態的考慮

對于上面的冪律分布律，在網絡中節點數較多時可以較好的滿足，而在節點數較少時，網絡的通聯累積量并不能很好的滿足上面的統計規律，數據分散性較大，采用此時的數據進行回歸分析是不合適的。本文提出結合網絡總體規模判斷當節點數較少時對網絡數據截斷，不作為模型的回歸數據。

如圖1所示，采用的是enron數據庫，模型較好的滿足線性關系，在回歸分析時，由于小規模數據不能很好滿足統計特性，該部分數據對回歸結果影響較大，可以看出模型在網絡大規模時具有一定的偏離。

圖1　LRAD算法回歸性質及截斷數據示意

在采用iLRAD算法進行回歸分析時，由于網絡規模較大時的數據點被判定為異常點，在迭代過程中逐漸被刪除，刪除后會導致回歸直線進一步偏離，最終導致回歸直線偏離較遠。

本文提出的小規模網絡節點刪除策略如下：由用戶指定一個網絡規模的最小值，主要為網絡中通聯累積量的大小，遍歷所有時段內的網絡，將滿足該通聯累積量的最小節點個數以及最多節點個數的均值作為門限，在回歸分析時，不考慮節點數小于該門限的網絡，對所有超出門限節點數的網絡進行回歸分析。設計該截斷小規模網絡策略的原因主要是為了解決圖1所示的情況回歸偏離的情況，該截斷方法可以有效避免小規模網絡數據點離散較大的現象，只保留虛線右上角區域的稠密數據點。截斷數據的截斷閾值選擇如下：

輸入，網絡規模的最小邊數e_min

輸出，網絡規模的點數閾值n_threshold

forGin {G1,G2,…GM}:

if e_min≤G.number_of_edges

n_list.append(G.number_of_nodes)

nγ= 0.5(max(n_list)+min(n_list))

2.3針對重點節點對的考慮

在復雜網絡中，某兩對節點之間的通信可能是非常重要的，當某兩個節點之間發生通聯時，其對應異常的可能性比較大，此時需要對節點對之間的通信情況進行加權。對于重要的節點，采用權值高來表示其相應的重要程度，一旦發生通聯則引起異常的可能性大。然而，網絡的權重會影響冪律分布，從而導致回歸模型不準確，因此需要盡量少的設置加權邊，使其對整體統計量影響不會很大。

2.4cLRAD算法流程

在LRAD算法的基礎上，考慮網絡中節點頻繁通信的異常檢測問題，結合實際數據特點，設定數據截斷閾值并預置重要節點，相應的cLRAD算法流程如下所示：

輸入：業務通聯事件序列{(S0,D0)|t0,(S1,D1)|t1,…,(SN,DN)|tN}，窗口長度，節點之間通信的重要程度

輸出：異常時間段

1)按照窗口長度，劃分通聯事件序列。

根據窗口長度劃分時間段分段點{T0,T1,…TM}

fortin {t0,t1,…tN}:

ifTi≤t

Gi.add_edges(Si,Di)

2)統計各個時段內網絡中節點個數以及通聯次數，當遇到重要節點之間通信時，需要考慮節點的權值。

node_list.append(G.number_of_nodes())

for (u,v) inG.edges():

edge_count+=G(u,v) *weight(u,v)

edge_list.append(edge_count)

3)對node_list和edge_list中的數據取對數。

log_n = log(node_list)

log_e = log(edge_list)

4)截斷較小規模的網絡數據。

for (n,e) in zip(log_n, log_e):

ifn>nγ:

part_log_n.append(n)

part_log_e.append(e)

5)對part_log_n和part_log_e進行線性回歸。

6)計算不符合回歸直線的點標記為異常點。

for (i, (n,e)) in enumerate(zip(log_n, log_e)):

anomalous.append(i)

返回:anomalous

輸入為各個時刻的通聯數據，首先根據窗口將數據劃分到各個時段，時段內的通聯關系構成網絡，當節點對之間存在多次通聯時，需要考慮節點重要程度加權處理通聯累積量。然后對各個時段的網絡節點和通聯累積量取對數，截斷較小規模網絡數據，進行線行回歸。將各個時段的數據點帶入回歸直線，偏離回歸直線超過回歸偏差的數據所對應的時間段標記為異常時間段。

3實驗結果

采用Enron語料庫作為數據對象，挖掘其中的異常結果。Enron語料庫是Enron公司公開的數據庫，包含158個用戶在1979年12月31日到2001年7月12日之間發送的619,446條郵件信息。本文的仿真實驗將時間段設定為一天。

在不截斷小規模數據情況下，cLRAD異常檢測算法結果如圖2所示，有個別節點可以被判定出是異常節點。說明這些節點在一天之內發生了頻繁通信，該現象與網絡受到攻擊類似，而LRAD算法不能檢測出該異常。

下面人為地加入通信異常，查看異常檢測結果。對節點schottla@us.cibc.com和deborahlowe@akllp.com的通信人為增加20%，可以認為增加的這部分通信是異常，進行異常檢測的結果如圖3所示。

圖2節點數與通聯累積量的回歸關系

可以看出，在節點之間通信數量發生變化時，cLRAD算法可以較好的檢測出網絡異常，而LRAD方法對于兩節點之間的頻繁通信只做一次記錄，因此LRAD方法對此類異常無反應。

圖3　人為增加通聯次數的異常檢測效果

設置表2中所示節點對之間的通信作為重點監控對象，當表中節點之間發生通信時，認為異常情況較為嚴重，實驗結果如圖4所示。

表2　通信節點對和權值對應關系

圖4加權通信后的網絡異常檢測效果

對于權值較大的節點對之間的通信，其偏離系統回歸模型較遠，cLRAD算法可以較好的檢測出此類異常。而LRAD對待所有通聯行為是等同處理的，因此不能處理該類特殊通聯問題的情況。

將規模小的數據進行截斷，選取數據在最大通聯數的20%以下的網絡規模被截斷，此時的網絡回歸模型如圖5所示?？梢钥闯?，與圖2相比，此時回歸直線能夠較好的表征網絡節點和通聯次數之間的變化關系，回歸直線在分布密集的數據中。

圖5　截斷數據異常檢測結果

如圖5所示，截斷小規模網絡數據的回歸效果更加接近網絡模型，回歸直線沒有偏離數據集中區域，網絡異常檢測結果更加準確。然而如何選擇階段閾值是一個需要繼續研究的問題。

上面的實驗中，對數據的預處理是將1天內的數據作為一個通聯網絡進行異常檢測的，檢測結果以天數為粒度，還可以以周為單位，進行異常檢測，而此時的檢測結果表明，有些異常可能發生漏警。由于本算法采用的線性回歸方法計算復雜度低，計算速度塊，因此，在實際處理問題時，可以遍歷不同時窗粒度，給出多粒度異常檢測結果。

實驗結果表明，cLRAD算法可以找出網絡拓撲結構發生異常的情況，并且在用戶指定某些特殊節點通聯的情況下可以靈敏的找出網絡中的異常。然而，該方法需要進一步完善時間窗口長度以及截斷數據閾值的選擇問題。

4結語

本文針對LRAD算法對于節點多次通聯的異?，F象無法檢測的缺點，提出了cLRAD算法。首先給出了通聯累積量的定義并證明其滿足冪律分布規律，然后提出了利用該規律進行回歸建模方法。在回歸分析中，針對網絡規模較小時網絡數據分散，不能得到較好的回歸模型的問題，提出篩選網絡數據的策略，然后根據實際中存在的某些節點需要重點關注的場景，提出了cLRAD算法對于特殊節點的處理方法。實驗證明，cLRAD對于網絡中存在多次通聯的異常具有較好的檢測效果，而LRAD不能檢測出該類異常。

參考文獻：

[1]文拯, 梁建武, 陳英. 關聯規則算法的研究[J]. 計算機技術與發展, 2009, 5 (19):56-58.

WEN Zheng, LIANG Jian-wu, CHEN Ying. Research of Association Rules Algorithm[J].Computer Technology and Development, 2009,5(19):56-58.

[2]Varun Chandola, Arindam Banerjee, and Vipin Kumar. Anomaly Detection: A Survey[J]. ACM Computing Surveys, 2009, 41(3).

[3]CHENG Hai-bin,TAN Pan-ning, et al. Detection and Characterization of Anomalies Multivariate Time Series[C].SDM, 2009.

[4]LI X, LI Z, HAN J, et al. Temporal Outlier Detection in Vehicle Traffic Data[C]//Proceedings of the 25thInternational Conference on Data Engineering (ICDE2009). IEEE Computer Society, 2009:1319-1322.

[5]Breunig M, Kregel H, Ng R, et al. LOF: Identifying Density-based Local Outliers[J]. ACM SIGMOD Record, 2000, 29(2):104.

[6]LAI K,King G,Lau O. Arima: Arima Models for Time Series Data, 2007.

[7]DING Hui, Goce Trajcevski, etc. Querying and Mining of Time Series Data: Experimental Comparison of Representations and Distance Measures[C]. VLDB,2008.

[8]YANG Ki-yong and Cyrus Shahabi. A PCA-based Similarity Measure for Multivarite Time Series[C]. MMDB,2004.

[9]WENG Xiao-qing, SHEN Jun-yi. Outlier Mining for Multivariate Time Series based on Local Sparsity Coefficient[C]. Proceedings of the 6thWorld Congress on Intelligent Control and Automation, 2006.

[10]陳湘濤，李明亮，陳玉娟.基于時間序列相似性聚類的應用研究綜述[J].計算機工程與設計，2010，31(03):577-581.

CHEN Xiang-tao, LI Ming-liang, CHEN Yu-juan. Summaly of Application Research based on Clustering of Time Series Similarity[J]. Computer Engineering and Design, 2010,31(03):577-581.

[11]Erdos P, Renyi A. On the Evolution of Random Graphs[J]. Pub1. Math.Inst.Hung.Acad.Sci, 1960,5:17-16.

[12]Barabasi A, Albert R. Emergence of Scaling in Random Networks[J]. Science, 1999, 286(5439):509.

[13]Leskovec J, Kleinberg J, Faloutsos C. Graph over Time: Densification Laws, Shrinking Diameters and Possible Explanations[C]//Proceeding of the 11thACM SIGKDD International Conference on Knowledge Discovery in Data Mining(KDD’05). Chicago, Illinois, USA.: New York, USA, 2005:177-187.

[14]Bunke H,Dickinson P J, Kraetzl M, et al. A Graph-Theretic Approach to Enterprise Network Dynamics[M]. Birkhauser Boston, 2007.

[15]Lahiri M, Berger-Wolf T Y. Periodic Subgraph Mining in Dynamic Networks[J]. Knowlinf Syst. 2009,24(3):467-497.

[16]Berlingerio M, Bonchi F, Bringmann B, et al. Mining Graph Evolution Rules[C]//ECML/PKDD 2009. Springer Berlin Heidelberg, 2009:115-130.

[17]孟嘯.動態復雜網絡中的異常檢測問題的研究[D]. 哈爾濱：哈爾濱工業大學計算機科學與技術學院,2010.

MENG Xiao. Research on Anomaly Detection in Dynamic Complex Networks[D]. School of Compter Science and Technology, Harbin Institute of Technology. 2010.

[18]李聰,宋路.淺談IP RAN網絡建設思路與策略[J].通信技術,2015,48(01):75-81.

LI Cong, SONG Lu. Idea and Strategy of IP RAN Network Development[J]. Communications Technology, 2015, 48(01): 78-81.

[19]Jitesh S, Jafar A. The Enron Email Dataset Database Schema and Brief Statistical Report. University of Southern California Los Angeles[R]. CA 2004.01.

[20]Dorogovtsev S N, Mendes J F F, Samukhin A N. Structrue of Growing Networks with Preferential Linking[J]. PRL, 2000, 85:4633-4636.

[21]Barabasi A,Albert R.Scale-Free Networks: A Decade and Beyond[J]. Science,2009,325.

[22]Bollobas B, Riordan O M, Spencer J,et al. Degree Sequence of a Scale-Free Random Graph Process[J]. Random Structures and Algorithm, 2001, 18:279-290.

[23]Holme P, Kim B J. Growing Scale-Free Networks with Tunable Clustering[J]. PRE,2002,65:026107.

賀亮(1990—),男,碩士研究生,主要研究方向為網絡異常檢測；

褚衍杰(1982—),男,工程師,主要研究方向為智能信息處理；

韓杰思(1981—),男,工程師,主要研究方向為圖像處理，網絡異常檢測。

Anomaly Detection Algorithm based on Communicating

Cumulant in Dynamic Network

HE Liang，CHU Yan-jie，HAN Jie-si

(State Key Laboratory of Science and Technology on Blind Signal Processing, Chengdu Sichuan 610041,China)

Abstract：In network operation and maintenance fields, one of the biggest concerns is how to detect the network anomaly without delay. Aiming at the problem that the existing methods could hardly detect the anomaly in case of high-frequency communication, an anomaly detection method based on statistic model for high-frequency communication is proposed. In this method,the power-law distribution model is used to describe the relation of between the number of nodes and frequency communicating cumulant,this model is matched via linear regression,and the network state with regression error beyond the confidence coefficient is predicated as abnormal. In addition,for the heavy-concerned node pair in the network,a predistribution scheme of its weight assignment is given. However, in light of small-scale network status, which could not completely follow power-law distribution, a sample pre-selection strategy is suggested,so as to reduce the false alarm of abnormal behavior. Finally, experiment results indicate that the proposed method is of fairly high detection rate both in abnormal high-frequency and low-frequency communication.

Key words：dynamic complex networks; anomaly detection; communication cumulant; linear regression

作者簡介：

中圖分類號：TN 911

文獻標志碼：A

文章編號：1002-0802(2015)12-1400-06

收稿日期：2015-07-08；修回日期：2015-10-20Received date:2015-07-08；Revised date：2015-10-20

doi:10.3969/j.issn.1002-0802.2015.12.016