基于元胞退火算法的僵尸網絡傳播特征研究

趙攀，江宇波，邱玲

（四川理工學院計算機學院，四川自貢643000）

基于元胞退火算法的僵尸網絡傳播特征研究

趙攀，江宇波，邱玲

（四川理工學院計算機學院，四川自貢643000）

為了有效研究僵尸網絡傳播過程中的特征變化，基于元胞退火算法提出了一種新的刻畫方法BDCA。該方法通過定義了僵尸網絡中普通節點、易感染節點和感染節點之間的轉化關系，建立平衡條件下的最優目標函數，并利用元胞退火算法求出最優解。最后，利用NS2進行仿真實驗，深入分析了影響BDCA算法的關鍵因素，同時通過對比其它算法之間的性能狀況。結果表明，該算法具有較好的適應性。

僵尸網絡；感染；特征；元胞退火算法

引言

近年來，僵尸網絡（Botnet）成為計算機網絡安全的重要威脅，它是一種通過傳播僵尸程序控制主機，并由一對多的命令與控制信道所組成的網絡［1_3］。這種一對多的控制關系使攻擊者以極低代價實現控制大量資源的目的，并可以輕易發動諸如垃圾郵件和分布式拒絕服務等攻擊，造成數據竊取和服務器癱瘓等危害。它是從傳統惡意代碼形態和后門工具演化而來的。

僵尸網絡主要由僵尸程序和僵尸網絡控制器構成，作為僵尸網絡核心的控制機制主要采用的協議有IRC、P2P和HTTP［4_7］。而目前針對僵尸網絡的檢測方法主要有三種：蜜罐技術、流量分析技術和終端信息的檢測技術。蜜罐是防御者部署在網絡中用以引誘攻擊者上鉤的陷阱主機，其前提必須讓蜜罐絕對隱蔽地加入到僵尸網絡中，并且需要保證蜜罐不會被攻擊者反檢測；流量分析技術則是檢測人員通過網絡分析軟件，對異常流量進行檢測；而基于終端信息的檢測技術，主要利用僵尸終端的一些重要信息進行反饋和分析。柴勝等［S］通過詳細分析P2P僵尸網絡的網絡特征和生命周期，提出了一種新的基于改進的SPRINT決策樹和相似度函數的在線綜合檢測方法。臧天寧等［9］針對僵尸網絡之間潛在具有的隱藏關系，提取了內部通信的主機通信量、數據流數量、數據分組負載等特征，建立了僵尸網絡之間的相似度評價模型。王勁松等人［10］首先從僵尸網絡的傳播、攻擊以及命令與控制等方面介紹了僵尸網絡工作機制的發展，然后從監測、工作機制分析、特征分析、檢測和主動遏制對僵尸網絡防御方面的研究進行總結和分析，并對防御方法的局限、僵尸網絡的發展趨勢進行了討論。陳端兵［11］通過挖掘網絡中的關鍵節點和社區結構，建立了一種基于社會網絡分析的P2P僵尸網絡反制策略，有效控制僵尸網絡病毒的傳播。錢權［12］在詳細分析兩種典型的結構化P2P協議Chord和Kademlia的基礎上，結合雙因子免疫機制、主機在線率等因素建立了結構化P2P僵尸網絡的傳播模型，深入研究了這兩種典型的結構化P2P網絡中僵尸的傳播原理。

針對上述問題，本文首先給出了僵尸網絡中各類節點之間的轉化關系，并建立符合僵尸網絡傳播的數學模型，同時利用元胞退火算法對上述模型進行求解，獲得平衡關系下的最優解。最后，通過NS2進行仿真實驗，深入研究了影響該方法的關鍵因素。

1 僵尸網絡特征

假設初始時刻，某網絡G中存在的N個節點均未被僵尸程序感染。在每個單位時間內節點的變化率為ΔN，那么經過時間步長t后，網絡G中的節點數量為N（t）=N+∑tΔN（t）。將這些節點劃分為普通節點、易感節點和感染節點。三類節點之間的轉化關系為：普通節點被僵尸程序植入后以概率α變成易感節點，易感節點在被入侵后以概率β變化成感染節點，而感染節點和易感節點在清除掉僵尸程序后分別以概率γ和δ恢復為普通節點。這四類轉化關系的概率計算公式：

式（1）采用節點度和平均概率α計算普通節點i向易感染節點轉化的概率αi，其中Di表示易感染節點i的度，表示網絡中所有節點的度，這兩者比例越大其感染可能性將變大，這說明網絡中如果某個普通節點的相鄰節點越多，那么它受到感染的幾率將增大。

2 目標函數

由上述的三類節點之間的轉化關系，進行數學描述。假設在某時刻t網絡中的總節點數為N（t），普通節點數量為A（t），易感節點數量為B（t），感染節點數量為C（t），并且易感節點數量與總節點數量正相關。在單位時間內某感染節點i能探測到的節點數等于其度數節點i能探測到的易感節點數可表示為，那么單位時間內感染節點i能夠感染的易感節點數為。為了獲得比較安全的網絡環境，感染節點和易感節點的數量應該趨于0。對此，本文建立如下目標函數：

約束條件為：

其中，式（6）描述了單位時間內易感節點轉化為普通節點或者感染節點的變化率，式（7）描述了感染節點轉化為普通節點的變化率，式（S）描述了在單位時間內普通節點轉化為易感節點以及感染節點和易感節點轉化為普通節點的變化率。

3 算法描述

對于上述建立的數學模型，是一個非線性最優問題。而元胞自動機是一種時間和空間離散、狀態有限的多維系統，多應用于非線性空間。所以，本文利用元胞退火算法（Botnet Detecting algorithm based on Cellular Annealing，BDCA）對模型進行求解。

定義Moore型元胞結構（圖1），中心黑色圓圈代表當前元胞，與周圍S個元胞相鄰。中心元胞下一時刻狀態將選擇周圍S個元胞和自身狀態中的最優值。這里將中心元胞視作抗體，其適應度z（x）狀態值如下：

根據元胞適應度、變異概率p和交叉概率q，定義交叉和變異過程中所采用的元胞演化規則：

圖1元胞結構示意圖

（1）在當前時刻，令中心元胞i和臨域元胞j的適應度分別為z（i）和z（j），其差Δz=z（i）-z（j），判斷交叉概率p與rand（）之間的關系，若p≤rand（），保持當前元胞狀態；否則當前元胞執行變異操作，根據式（S）產生新的子抗體r1：

其中，rand（）為0到1之間的隨機數；

（2）判斷交叉概率q與rand（）之間的關系，如果q≤rand（），保持當前元胞狀態；否則根據式（9）對抗體i和j執行交叉操作，獲得子抗體i1和j1：

（3）在下一時刻更新所有元胞狀態：

本文結合元胞退火算法給出上述數學模型的求解算法（Botnet Detecting algorithm based on Cellular Annea_ ling，BDCA）。具體描述如下：

（1）在開始時刻T，初始化網絡拓撲結構，隨機生成網絡節點數目N，以及普通節點、易感染節點和感染節點初始所占比例，并確定種群規模R、抗體群規模為M、初始溫度t0、變異概率p和交叉概率q、迭代次數m等參數。

（2）這里將每個節點視作抗體，根據式（12）計算抗體群中每個抗體i的適應度值，用來表示抗體與抗原之間的匹配程度。

（3）按照式（16）對第i個抗體進行克隆操作，獲得規模為M1的新抗體群η：

其中，“=”表示向下取整，θ表示克隆系數。

（4）根據元胞演化規則對新抗體群η1中抗體r執行變異操作，并產生新的子抗體r1以及臨時抗體群η2，同時將r1作為當前最優解。

（5）根據元胞演化規則對臨時抗體群η2的抗體r1和r2隨機執行交叉操作，獲得子抗體r3和r4，以及新的抗體群η3。

判斷當前溫度t是否為零，如果不為零，則令i+1，t=t（N-i）/n，跳轉到步驟（3）；否則表示退火過程完成，此時得到的抗體群η3即為下一時刻最優的目標函數F（k），跳轉到步驟（7）。

（7）令m=m+1，判斷當前循環是否結束，如果是則跳轉到步驟（2），繼續預測下一時刻最優的目標函數F（k），否則跳轉到步驟（S）。

（S）輸出當前的最優解，即為穩定狀態下感染節點和易感染節點的最小值。

（9）算法結束。

4 仿真實驗

為了驗證上述算法的有效性，這里利用NS2進行仿真實驗。在NS2中首先建立如圖2所示的網絡拓撲圖。

圖2仿真拓撲圖

設置其參數：節點數目為150個，鏈路容量為15 MbPs，各節點緩存大小為256 Packets，延時10 ms，數據包大小為512 Byte。同時，令種群規模R=200，抗體群規模為M=20、初始溫度t0=1、變異概率p=0.04，交叉概率q=0.5，最大迭代次數m=200。在表1中列出了文獻［16］所采集的不同網絡流量屬性信息，這里將本文提出的BDCA算法與文獻［16］提出的BDCFA（Botnet Detectingmethod based on Clustering Flow Attributes）算法進行比較分析。假設初始時刻不存在僵尸程序，在t= 10時僵尸程序出現，有一個節點被感染，此時沒有恢復的節點。首先在節點A、D、E和F處按照表1給出的網頁瀏覽、在線游戲、P2P應用和僵尸網絡數據流特征來產生數據源。

圖3中顯示了這兩種算法感染節點數的變化趨勢。隨著仿真時間的增加，曲線整體先呈現上升趨勢，隨后降低直至平穩。在開始階段，感染節點較少，并且連接度較小，僵尸程序的傳播能力較低，整個網絡的感染節點數增長緩慢。大約在t=30時，網絡有相當一部分節點被感染，此時匯聚節點的連接度遠高于開始階段，導致網絡中感染節點的連接度迅速增加，并達到最大值（t=50時）。同時，針對僵尸程序的防治措施在網絡中開發發揮作用，恢復為普通節點的數量不斷增加，感染節點的連接度隨之下降，因此僵尸程序的傳播能力下降，使感染節點的數量逐漸減少，最后達到一種平衡狀態。而在同一仿真時間下，BDCA算法對應曲線的感染節點數較BDCFA算法更低，這說明BDCA算法具有更好的抵抗僵尸程序的能力。

表1不同網絡流量屬性信息

圖3感染節點數對比情況

其次，再對變異概率p和初始溫度t0這兩個影響BDCA算法性能的關鍵因素進行研究。圖4給出了不同變異概率p下感染節點數的變化趨勢。在仿真初期，變異概率p越小對應的感染節點數個數越少，但是在仿真后期仿真曲線發生突變，變異概率p越大對應的感染節點數個數越少。這是由于初期網絡中節點被感染的情況較少，而仿真后期，單位面積內的感染節點分布增加，此時增大變異程度越大，查找出感染節點進行恢復的概率就越大，而在前期增大變異程度會過多消耗系統資源。

圖5給出了不同初始溫度t0下感染節點數的變化趨勢。在初期初始溫度越小，對應曲線的感染節點數越大；而在仿真后期情況發生了突變，初始溫度越大，對應曲線的感染節點數越大。這是因為初期感染僵尸程序的節點較少，如果初始溫度越大，系統趨于穩定的速度越快，感染節點恢復效率將增加；當處于仿真后期，感染節點增多，初始溫度越大系統尋優過程的開銷越大，清除感染節點的幾率減小。

圖4不同變異概率下感染節點數比較

圖5不同初始溫度下感染節點數比較

5 結束語

本文針對僵尸網絡傳播特點提出了一種新的刻畫方法BDCA。該方法首先定義了普通節點、易感染節點和感染節點之間的轉化關系，并建立了平衡條件下的目標函數和數學模型。同時，結合元胞退火算法，將網絡節點集合看作抗體種群，普通節點、易感染節點和感染節點看作不同抗體，對目標函數進行求解。最后，通過NS2進行仿真實驗，對比研究了BDCA算法與其它算法之間的性能差異，結果表明該算法具有較好的適應性。在后續研究中，可以考慮結合蜜罐檢測和流檢測方法對分布式P2P僵尸網絡傳播特點進行刻畫，以此建立完善的評價體系結構。

［1]Zhang Z H，Kadobayashi Y.A holistic perspective on understanding and breaking botnets:challenges and coun_ termeasures［J].Journal of the National Institute of Infor_ mation and Communications Technology，2008，55(2_3):43_59.

［2]Sun Y D，Li D.Overview of botnet［J].Computer Appli_ cations，2006，26(7):1628_1630.

［3]諸葛建偉，韓心慧，周勇林，等.僵尸網絡研究［J].軟件學報，2008，19(3):702_715.

［4]王天佐，王懷民，劉波，等.僵尸網絡中的關鍵問題［J].計算機學報，2012，35(6):1192_1208.

［5]李潤恒，王明華，賈焰.基于通信特征提取和IP聚集的僵尸網絡相似性度量模型［J].計算機學報，2010，33(1):45_54.

［6]Holz T，Steiner M，Dahl F，et al.Measurement and mitiga_ tion of peer_to_peer_based botnets:a case study on storm worm［C]//Proceeding of the 1st UsenixWorkshop on Large_Scale Exploits and Emergent Threats，San Fran_ cisco，April 9，2008:1_9.

［7]王海龍，胡寧，龔正虎.Bot_CODA:僵尸網絡協同檢測體系結構［J].通信學報，2009，30(10A):15_22.

［8]柴勝，胡亮，梁波.一種p2p Botnet在線檢測方法研究［J].電子學報，2011，39(4):906_912.

［9]臧天寧，云曉春，張永錚，等.基于通信特征和D_S證據理論分析僵尸網絡相似度［J].通信學報，2011，32 (4):66_76.

［10]王勁松，劉帆，張健.基于組特征過濾器的僵尸主機檢測方法的研究［J].通信學報，2010，31(2):29_35.

［11]陳端兵，萬英，田軍偉，等.一種基于社會網絡分析的P2P僵尸網絡反制策略［J].計算機科學，2009，36 (6):101.

［12]錢權，蕭超杰，張瑞.結構化對等網絡中P2P僵尸網絡傳播模型［J].軟件學報，2012，23(12):3161_ 3174.

［13]譚虓，劉自山，李凌宇.基于模擬退火遺傳算法的IIR數字濾波器參數優化設計［J].四川理工學院學報:自然科學版，2010，24(4):426_430.

［14]崔之熠，王茂芝，劉國濤，等.螞蟻算法在TSP問題求解的應用［J].四川理工學院學報:自然科學版，2011，24(3):334_337.

［15]魯宇明，黎明，李凌.一種具有演化規則的元胞遺傳算法［J].電子學報，2010，38(7):1603_1607.

［16]蘇欣，張大方，羅章琪，等.基于Command and Control通信信道流量屬性聚類的僵尸網絡檢測方法［J].電子與信息學報，2012，34(8):1993_1999.

Study of Botnet Spread Characteristic Based on Cellular Annealing Algorithm

ZHAO Pan，JIANG Yubo，QIU Ling
（School of ComPuter Science，Sichuan University of Science&Engineering，Zigong 643000，China）

In order to research the characteristic changes in Botnet sPread Process effectively，a novel dePicted method BDCA is ProPosed based on cellular annealing algorithm.In thismethod，the transformation relationshiPs between ordinary nodes，suscePtible nodes and infected nodes are defined，and the oPtimal objective function under equilibrium conditions is built.Then，the oPtimal solution is solved by using cellular annealing algorithm.Finally，a simulation exPerimentwith NS2 is conducted to analyse the key factors influencing the BDCA algorithm in dePth.Meanwhile comPared to the Performance of other algorithms，the results show that，BDCA has better adaPtability.

Botnet；infect；characteristic；cellular annealing algorithm

TP393

A

1673_1549(2014)02_0032_05

10.11863/j.suse.2014.02.07

2013_11_11

四川省教育廳重點項目（13ZA011S）；人工智能四川省重點實驗室開放基金項目（2012RYY02）；四川理工學院培育項目（2012PY13）

趙攀（1976_），男，四川自貢人，副教授，碩士，主要從事計算機網絡通信和數據處理方面的研究，（E_mail）zhaoPanS27@gmail.com