基于通聯(lián)累積量的動態(tài)網(wǎng)絡異常檢測算法

賀　亮，褚衍杰，韓杰思

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

?

基于通聯(lián)累積量的動態(tài)網(wǎng)絡異常檢測算法

賀亮，褚衍杰，韓杰思

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

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

關鍵詞：動態(tài)復雜網(wǎng)絡；異常檢測；通聯(lián)累計量；線性回歸

0引言

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

網(wǎng)絡異常是與網(wǎng)絡正常狀態(tài)相對的概念，異常檢測的一個基本思想，是通過網(wǎng)絡長期穩(wěn)定的數(shù)據(jù)對網(wǎng)絡的正常行為進行建模，找出短期內(nèi)與該模型偏離較為嚴重的網(wǎng)絡行為作為網(wǎng)絡異常[1]。

網(wǎng)絡中的異常種類較多，文獻[2]將其分為三類，包括：點異常，即局部異常；上下文異常，即異常與事件發(fā)生的時刻有關；聯(lián)合異常，即一段時間內(nèi)的異常。文獻[3]通過時間序列分析的方法提取數(shù)據(jù)的微觀特征和異常?？梢酝ㄟ^網(wǎng)絡的特征參數(shù)對異常現(xiàn)象進行檢測，即測量網(wǎng)絡的結構特征監(jiān)測網(wǎng)絡結構是否發(fā)生了顯著變化，從而發(fā)現(xiàn)異常。

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

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

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

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

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

1冪律分布模型

1.1節(jié)點數(shù)與邊數(shù)的分布模型

社交網(wǎng)絡、Internet等典型網(wǎng)絡中，網(wǎng)絡節(jié)點數(shù)多，節(jié)點之間通聯(lián)規(guī)模大。已有研究表明，復雜網(wǎng)絡中節(jié)點數(shù)與邊數(shù)之間的關系服從冪律分布模型[20]，即：

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

logE(t)=a0logN(t)+b0

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

p(x=k)=cx-γ

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

1.2節(jié)點數(shù)與通聯(lián)累積量的分布模型

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

為了針對異常的高頻次通聯(lián)行為進行檢測，本文在iLRAD基礎上提出cLRAD方法，即對于網(wǎng)絡通信，對一段時間窗口內(nèi)的節(jié)點之間的通信次數(shù)進行累加，作為通聯(lián)累積量。可以證明，通聯(lián)累積量與節(jié)點仍然滿足冪律分布關系。采用相同的方法可以對頻繁發(fā)生通信的異常事件進行檢測。

對于具有N個節(jié)點的復雜網(wǎng)絡，假設任意兩個節(jié)點之間產(chǎn)生通聯(lián)的概率為p，并且兩個節(jié)點之間可以產(chǎn)生多次通聯(lián)，則任意兩個節(jié)點之間通聯(lián)累積量的期望值為：

因此對于N個節(jié)點的網(wǎng)絡具有的通聯(lián)累積量之和的期望值為：

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

2基于通聯(lián)累積量的動態(tài)網(wǎng)絡異常檢測算法(cLRAD)

2.1cLRAD算法原理

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

2.2針對小規(guī)模網(wǎng)絡狀態(tài)的考慮

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

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

圖1　LRAD算法回歸性質(zhì)及截斷數(shù)據(jù)示意

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

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

輸入，網(wǎng)絡規(guī)模的最小邊數(shù)e_min

輸出，網(wǎng)絡規(guī)模的點數(shù)閾值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針對重點節(jié)點對的考慮

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

2.4cLRAD算法流程

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

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

輸出：異常時間段

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

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

fortin {t0,t1,…tN}:

ifTi≤t

Gi.add_edges(Si,Di)

2)統(tǒng)計各個時段內(nèi)網(wǎng)絡中節(jié)點個數(shù)以及通聯(lián)次數(shù)，當遇到重要節(jié)點之間通信時，需要考慮節(jié)點的權值。

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中的數(shù)據(jù)取對數(shù)。

log_n = log(node_list)

log_e = log(edge_list)

4)截斷較小規(guī)模的網(wǎng)絡數(shù)據(jù)。

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

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

3實驗結果

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

在不截斷小規(guī)模數(shù)據(jù)情況下，cLRAD異常檢測算法結果如圖2所示，有個別節(jié)點可以被判定出是異常節(jié)點。說明這些節(jié)點在一天之內(nèi)發(fā)生了頻繁通信，該現(xiàn)象與網(wǎng)絡受到攻擊類似，而LRAD算法不能檢測出該異常。

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

圖2節(jié)點數(shù)與通聯(lián)累積量的回歸關系

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

圖3　人為增加通聯(lián)次數(shù)的異常檢測效果

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

表2　通信節(jié)點對和權值對應關系

圖4加權通信后的網(wǎng)絡異常檢測效果

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

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

圖5　截斷數(shù)據(jù)異常檢測結果

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

上面的實驗中，對數(shù)據(jù)的預處理是將1天內(nèi)的數(shù)據(jù)作為一個通聯(lián)網(wǎng)絡進行異常檢測的，檢測結果以天數(shù)為粒度，還可以以周為單位，進行異常檢測，而此時的檢測結果表明，有些異?？赡馨l(fā)生漏警。由于本算法采用的線性回歸方法計算復雜度低，計算速度塊，因此，在實際處理問題時，可以遍歷不同時窗粒度，給出多粒度異常檢測結果。

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

4結語

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

參考文獻：

[1]文拯, 梁建武, 陳英. 關聯(lián)規(guī)則算法的研究[J]. 計算機技術與發(fā)展, 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]孟嘯.動態(tài)復雜網(wǎng)絡中的異常檢測問題的研究[D]. 哈爾濱：哈爾濱工業(yè)大學計算機科學與技術學院,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網(wǎng)絡建設思路與策略[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—),男,碩士研究生,主要研究方向為網(wǎng)絡異常檢測；

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

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

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