IP黑名單關聯聚類算法對惡意簇檢測的優化研究

劉 云， 肖 添

(昆明理工大學信息工程與自動化學院， 昆明 650500)

1 引 言

互聯網上的許多惡意行為已經演變成由多組IP地址共同執行的非常復雜的操作.電子垃圾郵件、分布式密碼猜測攻擊和惡意軟件分發網絡是此類攻擊的一些例子.攻擊者通常使用一組IP地址登錄到受攻擊的網絡帳戶以執行各種惡意任務[1-3].這種來自一組IP地址的集體行為通常會在網絡的各個位置留下痕跡，使得防御者能夠使用數據分析技術將這些IP地址集群連接在一起.

Stringhini等人提出基于模塊優化的迭代聚類算法(Iterative Clustering Algorithm Based on Modularity Optimization， ICAMO)[1].通過聚合數月的數據，能可靠地識別惡意的帳戶群集.Mathur等人提出了基于聚類的內邊界推斷算法(Clustering-Based Approach to Infer Internal Boundaries， CAIIB)[4].通過計算IP地址在IP地址空間上的接近度，并使用IP黑名單識別出潛在的惡意簇.Arya等人提出了一種基于動態屬性的聲譽算法(Dynamic Attribute Based Reputation, DABR)[5]，從已知惡意IP地址中提取數據生成聲譽等級，并根據閾值識別惡意IP地址.

ICAMO算法未能找到一個合適的閾值刪除IP簇中松散連接的分支，導致簇中IP地址數過大.CAIIB算法并沒有考慮黑名單質量的影響，且只在聚類完成后才使用IP黑名單.DABR算法由于生成聲譽等級使用的特征較少，導致算法只能應用于特定網絡.在ICAMO算法，CAIIB算法和DABR算法的研究基礎上，本文提出了IP黑名單關聯聚類算法(IP Blacklist Association Clustering Algorithm ，IPBACA)，通過一種新的聚類框架從網絡交互的數據集中識別執行惡意任務的IP簇.首先利用定義的相似性度量構建IP-IP無向圖，然后，利用測量統計相關性來測量IP黑名單與IP的相關性，并使用給定的IP黑名單來找到最佳閾值刪除相關性弱的邊緣得出IP簇，再判斷IP簇的標準化殘差是否大于3，最終得出與IP黑名單高度相關聯的惡意簇.從數學上證明了即使是質量普通的黑名單也可以用來精確地檢測惡意簇.仿真結果表明，即使是一個精度普通的IP黑名單也足以使所提出的算法準確地識別惡意IP簇，對比ICAMO算法，CAIIB算法和DABR算法，IP黑名單關聯聚類算法在精確率、召回率、F1指標[6]和歸一化互信息[7]等4個主要性能指標方面均有明顯改善，證明IPBACA算法顯著提高了檢測惡意簇的整體能力.

2 IP黑名單關聯聚類

2.1 IP黑名單關聯聚類框架

圖1是 IP黑名單關聯聚類框架圖，利用惡意網絡帳戶在論壇上發布垃圾評論、制造垃圾郵件等惡意任務[8-10]展示了不同的場景，IP地址可以通過數據分析方法連接在一起，共同執行一個任務.在兩個IP地址之間定義一個適當的相似性度量，就可以將給定的數據集表示為無向圖.構建無向圖之后，提取IP地址簇實質上是在區分簇邊緣和噪聲邊緣.為解決此問題，提出了一個聚類方法，如下所示.

圖1 IP黑名單聚類框架圖

(1) 從圖中刪除所有“弱邊”，其中“弱邊”被定義為權重小于閾值的邊.

(2) 將結果圖的連接部分輸出為IP簇.

為選擇一個合適的閾值來產生有意義的簇，本文通過使用IP黑名單來找到最佳閾值.選擇的最佳閾值是為了最大化黑名單和由聚類過程產生的惡意簇之間的統計相關性.因為IP簇和黑名單之間的相關性越強，簇惡意的證據就越強.所以通過最大限度地提高這種統計相關性，可以使所提出的聚類方案輸出具有最強統計證據的惡意簇.

2.2 測量統計相關性的定義

定義1測量統計相關性： 假設給出了一個黑名單“B”和一個數據集“N”.為了測量從數據集“N”中提取的IP簇“C”與黑名單“B”之間的依賴關系，首先為數據集中的每個IP地址定義以下具有二進制結果的事件對.

(1) 事件1: 數據集N中的IP地址在IP簇C中.

(2) 事件2: 數據集N中的IP地址在黑名單B中.

零假設下IP簇“C”是良性的，且事件1和事件2是獨立的.但是對于惡意簇，希望這些事件具有可測量的相關性.通過計算在零假設下的標準化殘差，測量這些事件之間的相關性，本質上衡量了在零假設下，簇C中IP地址在黑名單B中的頻率[6].因此，越高的標準化殘值表明事件具有更強的相關性.標準化殘差定義為

(1)

零假設表示集群C是良性的，事件1和事件2是獨立的.因此在零假設下，IP地址在集群C和黑名單B中的預期次數如下式所示.

其中，N表示數據集中的IP地址數；B表示數據集中黑名單IP地址數；C表示集群C的大小，IP地址在C中的概率寫為p1=C/N，IP地址在黑名單B中的概率為p2=B/N.將這些插入等式(1)中，可以將有n個IP地址在黑名單B中的集群C的標準化殘差計算為

(2)

3 IP黑名單關聯聚類算法

3.1 IP黑名單關聯聚類算法說明

IP黑名單關聯聚類算法主要包括預處理、尋找最佳閾值以及利用IP黑名單識別惡意簇三步.

在兩個IP地址之間定義一個適當的相似性度量，就可以將給定的數據集表示為無向圖.相似性度量SM(Similarity Measure)定義如下.

SM=α

(3)

其中，α是兩個IP地址在一天內登錄相同帳戶的數量，即邊緣權重.由于動態IP地址分配、主機被清理等原因，IP地址在惡意和非惡意之間頻繁切換[11-13]，因此識別出的惡意IP地址簇可能很快變得不活動或不再是惡意的.為此，對每天收集的數據集分析，而不像以前的工作對幾個月的聚合數據進行分析.

IPBACA算法中IP-IP無向圖的推理圖如圖2所示.

1) 從節點(IP地址)構造完整的(即完全連通的)無向圖.

2) 利用SM定義得出所有邊緣的權重α，并刪除α為零的邊，構建IP-IP無向圖.

3) 基于得出的最佳閾值，將節點間α小于最佳閾值的邊緣除去，從而獲得IP簇，IPBACA算法步驟如下.

步驟1預處理過程如圖2(a)和(b)所示，其中,節點表示IP地址，兩個節點之間邊緣的權重表示對應IP地址之間的相似性度量值，在IP-IP無向圖上可以得出兩種邊.一種是由于IP地址簇共同行為而存在的邊緣；另一種是由于各種原因和隨機事件產生的大量噪聲邊緣.因為惡意簇的邊緣代表具有集體惡意行為的關系，所以期望惡意簇邊緣的權重比噪聲邊緣大很多.

圖2 IPBACA算法中IP-IP無向圖的推理圖

步驟2尋找最佳閾值是通過利用統計相關性的度量，為所提出的聚類方案選擇最佳閾值.為了最大限度地證明這些簇是惡意的，聚類方案需要生成的惡意IP簇具有最高的標準化殘差.同時，因為使用較大的簇區分惡意和良性簇要更加準確，所以不希望聚類方案產生較小的簇.通過最大化所有簇的平均標準化殘差，可以滿足以上要求.這個目標函數如下式.

(4)

閾值和平均標準化殘差的關系非常復雜，雖然可使用如梯度上升法等數值方法求解，但最終解決方案是通過對一系列可能的閾值進行窮盡搜索來找到最佳閾值.在此情況下，窮盡搜索是最實際的解決方案，尋找最佳閾值的偽代碼如算法1所示.

算法1：尋找最佳閾值算法

輸入：IP-IP圖(G)，候選閾值列表(T)，t*←0，β*←0

輸出：t*：最佳閾值

Begin

1) fort∈Tdo

2)G′←將G中權重小于t的邊緣去除

3) 計算G′的平均標準化殘差β

4) ifβ>β*then

5)β*←β

6)t*←t

7) end

8) end

9) 找到最佳閾值t*

End

上述過程找到給定數據集的最佳閾值，就應用所提出的聚類方案來獲得IP簇列表如圖2(c)所示，但這些IP簇并非所有都是惡意的.下面將介紹如何使用給定的IP黑名單進一步識別IP簇列表中的惡意簇.

圖3 IP黑名單關聯聚類算法流程圖

步驟3圖3是IP黑名單關聯聚類算法流程圖的最后部分.根據之前測量統計相關性的定義，數據集N中簇C的標準化殘差(R)表示C是惡意簇的證據強度.由于R是通過標準誤差歸一化的，所以R=r表示觀察到的這兩個事件共現的次數在零假設下偏離其預期值的標準偏差為r.因此，R>3被認為是兩個事件相關的非常有力的證據，因為在零假設下偶然地觀察這一事件的概率小于0.3%[14].因此，為確定IP地址簇是否是惡意的，使用式(2)計算簇的標準化殘差，判斷其標準化殘差是否大于3，若是則聲明簇是惡意的.從而利用IP黑名單識別出具有高度準確率的惡意簇.

3.2 IP黑名單質量對算法影響評估

為分析IP黑名單的質量是如何影響標準化殘差，從而影響算法的檢測精確率，下面具體研究各種黑名單質量的標準化殘差的預期值.簇的大小也會影響檢測精確率，它在一定程度上取決于最佳聚類方案中使用的閾值.雖然在這一過程中可能存在一定程度的噪聲，但是為了研究黑名單質量的影響，假設最佳聚類方案能夠從數據中完美地提取IP簇.為描述黑名單的質量，將黑名單的真陽性率定義為

TPR=Pr(IP is in blacklist B|IP is Malicious)

黑名單的假陽性率為

FPR=Pr(IP is in blacklist B|IP is Benign)

良性和惡意的IP地址都有可能是誤報的，但為簡單起見，假設假陽性和真陽性是獨立且同分布.

如果簇C是良性的，那么C中列入黑名單的IP地址是由于誤報造成的，因此無論TPR和FPR為何值，標準化殘差的預期值都是E[R]=0，并且C中是黑名單IP地址的預期數量如下.

如果簇C是惡意的，那么C中是黑名單IP地址的預期數量將是

E[n]=|C|×FPR

由于數據集N中的良性IP遠比惡意IP多，因此數據集N中的IP地址處于黑名單B中的概率約等于黑名單的假陽性率(即p2=FPR).因此，將這些與方程(2)相結合，可以將標準化殘差的期望值寫為

(5)

由上式可得，當簇是惡意時，預期的標準化殘差會隨著黑名單的真陽性率和假陽性率之間差值的增加而增加，也會隨著簇的大小增加而增加.即

(1) 如果使用更準確的IP黑名單，可以更準確地識別惡意IP簇.

(2) 較大的簇比較小的簇具有更準確的識別度.

圖4 不同黑名單真、假陽性率和不同簇大小的預期標準化殘差的數值分析

為證明黑名單并不一定要非常精確才能準確地識別惡意集群.設數據集的大小N=1×105，圖4表現了不同簇大小和不同黑名單真、假陽性的預期標準化殘差.

為研究真陽性率的影響，如圖4圓形標記點所示，將黑名單假陽性率設置為10%，觀察到低真陽性率，例如黑名單真陽性率為40%，預期標準化殘差也很快超過臨界值3.因此，一個具有10%假陽性率和40%真陽性率的普通黑名單可以用來準確識別大小大于9的大多數惡意簇.此外，即使是真陽性率=30%和假陽性率=10%的質量非常差的黑名單，也可以用來準確識別惡意簇，只要簇的大小大于80.

另一方面，為了研究假陽性率的影響，如圖4三角形標記點所示，將黑名單真陽性率設置為60%，觀察到低假陽性率，例如FPR=10%，黑名單可用于準確識別大小最小為5的惡意簇.對于較大的假陽性率，如FPR=30%，惡意簇大小必須大于20就使用黑名單可靠地識別惡意簇.

圖4都顯示了標準化殘差的預期值，上面的論點是在預期意義上提出的.使用黑名單檢測惡意簇的實際概率等于標準化殘差大于3的概率.利用方程(1)，這個概率可以寫為

與式(4)組合后，相當于

Pr[n>|C|FPR+

這個概率可以計算出來，n是簇C中列入黑名單的IP地址數量，并且是二項式分布的，例如：

利用這些方程，設簇大小為50，繪制了圖5中各種黑名單真、假陽性率正確檢測惡意簇的概率(即Pr[r>3]).由圖5可知，更好的黑名單產生更準確的結果.例如，一個TPR=50%和FPR=20%的普通黑名單檢查的準確率約為91%.

圖5 針對不同的黑名單真、假陽性率正確檢測惡意簇的概率

4 仿真分析

4.1 數據集及評價指標

與類似論文一致，為了驗證所提出的算法，選取通用數據集，即微博的登錄服務器上收集到真實登錄事件的數據集[15]，并根據查詢Spamhaus[16]得到IP黑名單.

使用在連續14 d內觀察到的每個登錄事件的IP地址和匿名帳戶ID，且只考慮通過SMTP或IMAP協議以及桌面瀏覽器成功登錄的事件.在公有云平臺上使用具有2 GHz 64位QEMU虛擬CPU的虛擬主機，并使用networkx python library[17]提取連接的組件.

為測量聚類性能，文中選用精確率(Precision)、召回率(Recall)、F1指標和歸一化互信息(NMI)作為聚類算法評價指標，其定義如下.

TP表示正確判定屬于此簇的IP數；FP表示錯誤的判定屬于此簇的IP數；FN表示錯誤判定不屬于此簇的IP數，將精確率和召回率相結合構成了F1指標，更全面的對聚類性能進行評價.

其中,H(X)是X的熵，I(X∶Y)是H(X)和H(Y)之間的互信息量.

4.2 尋找最佳閾值

對于給定的一天，首先構建IP-IP圖，其中節點是IP地址，如果相應的IP地址用于在當天至少登錄一個公用帳戶，則兩個節點之間有一個邊緣.登錄的普通帳戶的實際數量由邊緣權重表示.在刪除獨立節點(即沒有邊緣的IP地址)之后，一天生成的圖有超過50萬個節點和160萬個邊緣.

建立了IP-IP圖，就可以找到從圖中提取IP簇的最佳閾值.為找到最佳閾值，計算方程(4)中給定的一系列閾值的目標函數，并選擇了使目標函數最大化的最佳閾值.在找到最佳閾值后，從圖中去除所有權重小于最佳閾值的邊緣.最后，將結果圖中連接的部分輸出為IP簇.忽略大小小于5的集群，因為無法準確計算此類小集群的標準化殘差.在移除這些小集群之后，通常每天會得到幾百個簇.

找到最佳閾值的實際CPU時間因可用計算資源的不同而有很大的差異，典型一天的數據在(0,30)范圍內的最佳閾值進行單線程搜索大約需要60 s.

為描述這個優化過程，在圖6中繪制了一個典型日期的閾值范圍的目標函數.

圖6 尋找最佳閾值

如圖6所示，在這一天的最佳閾值是13，這意味著一對IP地址必須登錄13個以上相同的帳戶才能連接到圖上，從而位于同一個簇.

4.3 算法對比仿真分析

在使用這些閾值執行最佳聚類之后，將標準化殘差大于3的簇聲明為每天得到的惡意簇.為仿真對比，將所提IPBACA算法與ICAMO算法，CAIIB算法和DABR算法進行對比，用精確率、召回率、F1指標和歸一化互信息等4個主要性能指標來評估四種算法的性能.

如圖7所示，所提出的IPBACA算法在14 d內平均精確率最高并且大幅領先其余3個算法，DABR算法的平均精確率接近40%，而ICAMO算法和CAIIB算法精確率相近，其中CAIIB算法表現最差.

圖7 4種不同算法的精確率對比圖

如圖8所示，IPBACA算法平均召回率最高，DABR算法次之，ICAMO算法和CAIIB算法表現相近，CAIIB算法召回率最低.

圖8 4種不同算法的召回率對比圖

如圖9所示，IPBACA算法的平均F1指標最高，ICAMO算法和CAIIB算法表現相近，其中CAIIB算法F1指標最低.

如圖10所示，IPBACA算法的平均歸一化互信息最高，DABR算法高于ICAMO算法，而CAIIB算法低于以上3種算法.

通過手動觀察檢測出的簇時，IPBACA算法由于刪除了IP簇中松散連接的分支，輸出了與黑名單高度相關聯的核心結構.ICAMO算法和CAIIB算法不涉及這樣的修剪，從而產生具有更多IP地址的簇，其中一些IP地址的連接相當松散.而DABR算法也使用閾值用于修剪，在一定程度上使性能有所提升.

圖9 4種不同算法的F1指標對比圖

圖10 4種不同算法的NMI對比圖

4.4 IP黑名單質量對算法影響評估

通過仿真實驗，逐步降低黑名單的質量并測量算法的檢測性能.

為降低黑名單的質量，首先在數據集中找到一天內所有黑名單IP.然后從黑名單中刪除這些黑名單IP的某些部分.為保持黑名單IP的數量不變，從整個數據集中隨機選擇相同數量的IP，并將其添加到黑名單中.這樣就大大降低了黑名單的真實陽性率.另一方面，由于隨機選擇的IP地址的數量遠小于數據集中所有IP地址的數量，因此假陽性率不會受到太大影響，只會增加百分之幾.由于實驗有隨機成分，為了平均出不可控因素，重復相同的實驗25次，并得出平均值.在圖11中繪制了使用不同黑名單腐敗率時，算法在精確率和召回率的變化.如圖可知，隨著更多黑名單被刪除，召回率逐步下降，但精度基本保持在75%～80%，直到80%的黑名單IP被刪除，精確率才大幅度下降.盡管根據黑名單的質量變低，IPBACA算法可能會遺漏一些惡意簇，但它檢測到的那些簇很可能是惡意的，證明了第3節中數學理論分析是合理.

圖11 黑名單腐敗率對算法精確率與召回率的影響

為了發現在互聯網中執行復雜惡意活動的惡意IP地址簇，本文提出一種IP黑名單關聯聚類算法(IPBACA)，通過一種新的聚類框架從網絡交互的數據集中識別執行惡意任務的IP地址簇，首先構建IP-IP無向圖，然后利用測量統計相關性來測量IP黑名單與IP的相關性，并使用給定的IP黑名單來找到最佳的閾值得出惡意簇，再判斷其標準化殘差是否達到標準，最終識別出高精度的惡意簇得出結果.仿真結果表明，即使是一個普通精度的黑名單也足以使所提出的方案準確識別惡意IP地址簇，對比ICAMO算法，CAIIB算法和DABR算法，IP黑名單關聯聚類算法在精確率、召回率、F1指標和歸一化互信息等4個主要性能指標方面均有明顯改善，證明IP黑名單關聯聚類算法顯著提高了檢測惡意簇的整體能力.