基于元胞退火算法的僵尸網(wǎng)絡(luò)傳播特征研究

趙攀，江宇波，邱玲

（四川理工學(xué)院計(jì)算機(jī)學(xué)院，四川自貢643000）

基于元胞退火算法的僵尸網(wǎng)絡(luò)傳播特征研究

趙攀，江宇波，邱玲

（四川理工學(xué)院計(jì)算機(jī)學(xué)院，四川自貢643000）

為了有效研究僵尸網(wǎng)絡(luò)傳播過程中的特征變化，基于元胞退火算法提出了一種新的刻畫方法BDCA。該方法通過定義了僵尸網(wǎng)絡(luò)中普通節(jié)點(diǎn)、易感染節(jié)點(diǎn)和感染節(jié)點(diǎn)之間的轉(zhuǎn)化關(guān)系，建立平衡條件下的最優(yōu)目標(biāo)函數(shù)，并利用元胞退火算法求出最優(yōu)解。最后，利用NS2進(jìn)行仿真實(shí)驗(yàn)，深入分析了影響B(tài)DCA算法的關(guān)鍵因素，同時(shí)通過對比其它算法之間的性能狀況。結(jié)果表明，該算法具有較好的適應(yīng)性。

僵尸網(wǎng)絡(luò)；感染；特征；元胞退火算法

引言

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

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

針對上述問題，本文首先給出了僵尸網(wǎng)絡(luò)中各類節(jié)點(diǎn)之間的轉(zhuǎn)化關(guān)系，并建立符合僵尸網(wǎng)絡(luò)傳播的數(shù)學(xué)模型，同時(shí)利用元胞退火算法對上述模型進(jìn)行求解，獲得平衡關(guān)系下的最優(yōu)解。最后，通過NS2進(jìn)行仿真實(shí)驗(yàn)，深入研究了影響該方法的關(guān)鍵因素。

1 僵尸網(wǎng)絡(luò)特征

假設(shè)初始時(shí)刻，某網(wǎng)絡(luò)G中存在的N個(gè)節(jié)點(diǎn)均未被僵尸程序感染。在每個(gè)單位時(shí)間內(nèi)節(jié)點(diǎn)的變化率為ΔN，那么經(jīng)過時(shí)間步長t后，網(wǎng)絡(luò)G中的節(jié)點(diǎn)數(shù)量為N（t）=N+∑tΔN（t）。將這些節(jié)點(diǎn)劃分為普通節(jié)點(diǎn)、易感節(jié)點(diǎn)和感染節(jié)點(diǎn)。三類節(jié)點(diǎn)之間的轉(zhuǎn)化關(guān)系為：普通節(jié)點(diǎn)被僵尸程序植入后以概率α變成易感節(jié)點(diǎn)，易感節(jié)點(diǎn)在被入侵后以概率β變化成感染節(jié)點(diǎn)，而感染節(jié)點(diǎn)和易感節(jié)點(diǎn)在清除掉僵尸程序后分別以概率γ和δ恢復(fù)為普通節(jié)點(diǎn)。這四類轉(zhuǎn)化關(guān)系的概率計(jì)算公式：

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

2 目標(biāo)函數(shù)

由上述的三類節(jié)點(diǎn)之間的轉(zhuǎn)化關(guān)系，進(jìn)行數(shù)學(xué)描述。假設(shè)在某時(shí)刻t網(wǎng)絡(luò)中的總節(jié)點(diǎn)數(shù)為N（t），普通節(jié)點(diǎn)數(shù)量為A（t），易感節(jié)點(diǎn)數(shù)量為B（t），感染節(jié)點(diǎn)數(shù)量為C（t），并且易感節(jié)點(diǎn)數(shù)量與總節(jié)點(diǎn)數(shù)量正相關(guān)。在單位時(shí)間內(nèi)某感染節(jié)點(diǎn)i能探測到的節(jié)點(diǎn)數(shù)等于其度數(shù)節(jié)點(diǎn)i能探測到的易感節(jié)點(diǎn)數(shù)可表示為，那么單位時(shí)間內(nèi)感染節(jié)點(diǎn)i能夠感染的易感節(jié)點(diǎn)數(shù)為。為了獲得比較安全的網(wǎng)絡(luò)環(huán)境，感染節(jié)點(diǎn)和易感節(jié)點(diǎn)的數(shù)量應(yīng)該趨于0。對此，本文建立如下目標(biāo)函數(shù)：

約束條件為：

其中，式（6）描述了單位時(shí)間內(nèi)易感節(jié)點(diǎn)轉(zhuǎn)化為普通節(jié)點(diǎn)或者感染節(jié)點(diǎn)的變化率，式（7）描述了感染節(jié)點(diǎn)轉(zhuǎn)化為普通節(jié)點(diǎn)的變化率，式（S）描述了在單位時(shí)間內(nèi)普通節(jié)點(diǎn)轉(zhuǎn)化為易感節(jié)點(diǎn)以及感染節(jié)點(diǎn)和易感節(jié)點(diǎn)轉(zhuǎn)化為普通節(jié)點(diǎn)的變化率。

3 算法描述

對于上述建立的數(shù)學(xué)模型，是一個(gè)非線性最優(yōu)問題。而元胞自動(dòng)機(jī)是一種時(shí)間和空間離散、狀態(tài)有限的多維系統(tǒng)，多應(yīng)用于非線性空間。所以，本文利用元胞退火算法（Botnet Detecting algorithm based on Cellular Annealing，BDCA）對模型進(jìn)行求解。

定義Moore型元胞結(jié)構(gòu)（圖1），中心黑色圓圈代表當(dāng)前元胞，與周圍S個(gè)元胞相鄰。中心元胞下一時(shí)刻狀態(tài)將選擇周圍S個(gè)元胞和自身狀態(tài)中的最優(yōu)值。這里將中心元胞視作抗體，其適應(yīng)度z（x）狀態(tài)值如下：

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

圖1元胞結(jié)構(gòu)示意圖

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

其中，rand（）為0到1之間的隨機(jī)數(shù)；

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

（3）在下一時(shí)刻更新所有元胞狀態(tài)：

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

（1）在開始時(shí)刻T，初始化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，隨機(jī)生成網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目N，以及普通節(jié)點(diǎn)、易感染節(jié)點(diǎn)和感染節(jié)點(diǎn)初始所占比例，并確定種群規(guī)模R、抗體群規(guī)模為M、初始溫度t0、變異概率p和交叉概率q、迭代次數(shù)m等參數(shù)。

（2）這里將每個(gè)節(jié)點(diǎn)視作抗體，根據(jù)式（12）計(jì)算抗體群中每個(gè)抗體i的適應(yīng)度值，用來表示抗體與抗原之間的匹配程度。

（3）按照式（16）對第i個(gè)抗體進(jìn)行克隆操作，獲得規(guī)模為M1的新抗體群η：

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

（4）根據(jù)元胞演化規(guī)則對新抗體群η1中抗體r執(zhí)行變異操作，并產(chǎn)生新的子抗體r1以及臨時(shí)抗體群η2，同時(shí)將r1作為當(dāng)前最優(yōu)解。

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

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

（7）令m=m+1，判斷當(dāng)前循環(huán)是否結(jié)束，如果是則跳轉(zhuǎn)到步驟（2），繼續(xù)預(yù)測下一時(shí)刻最優(yōu)的目標(biāo)函數(shù)F（k），否則跳轉(zhuǎn)到步驟（S）。

（S）輸出當(dāng)前的最優(yōu)解，即為穩(wěn)定狀態(tài)下感染節(jié)點(diǎn)和易感染節(jié)點(diǎn)的最小值。

（9）算法結(jié)束。

4 仿真實(shí)驗(yàn)

為了驗(yàn)證上述算法的有效性，這里利用NS2進(jìn)行仿真實(shí)驗(yàn)。在NS2中首先建立如圖2所示的網(wǎng)絡(luò)拓?fù)鋱D。

圖2仿真拓?fù)鋱D

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

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

表1不同網(wǎng)絡(luò)流量屬性信息

圖3感染節(jié)點(diǎn)數(shù)對比情況

其次，再對變異概率p和初始溫度t0這兩個(gè)影響B(tài)DCA算法性能的關(guān)鍵因素進(jìn)行研究。圖4給出了不同變異概率p下感染節(jié)點(diǎn)數(shù)的變化趨勢。在仿真初期，變異概率p越小對應(yīng)的感染節(jié)點(diǎn)數(shù)個(gè)數(shù)越少，但是在仿真后期仿真曲線發(fā)生突變，變異概率p越大對應(yīng)的感染節(jié)點(diǎn)數(shù)個(gè)數(shù)越少。這是由于初期網(wǎng)絡(luò)中節(jié)點(diǎn)被感染的情況較少，而仿真后期，單位面積內(nèi)的感染節(jié)點(diǎn)分布增加，此時(shí)增大變異程度越大，查找出感染節(jié)點(diǎn)進(jìn)行恢復(fù)的概率就越大，而在前期增大變異程度會(huì)過多消耗系統(tǒng)資源。

圖5給出了不同初始溫度t0下感染節(jié)點(diǎn)數(shù)的變化趨勢。在初期初始溫度越小，對應(yīng)曲線的感染節(jié)點(diǎn)數(shù)越大；而在仿真后期情況發(fā)生了突變，初始溫度越大，對應(yīng)曲線的感染節(jié)點(diǎn)數(shù)越大。這是因?yàn)槌跗诟腥窘┦绦虻墓?jié)點(diǎn)較少，如果初始溫度越大，系統(tǒng)趨于穩(wěn)定的速度越快，感染節(jié)點(diǎn)恢復(fù)效率將增加；當(dāng)處于仿真后期，感染節(jié)點(diǎn)增多，初始溫度越大系統(tǒng)尋優(yōu)過程的開銷越大，清除感染節(jié)點(diǎn)的幾率減小。

圖4不同變異概率下感染節(jié)點(diǎn)數(shù)比較

圖5不同初始溫度下感染節(jié)點(diǎn)數(shù)比較

5 結(jié)束語

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

［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]諸葛建偉，韓心慧，周勇林，等.僵尸網(wǎng)絡(luò)研究［J].軟件學(xué)報(bào)，2008，19(3):702_715.

［4]王天佐，王懷民，劉波，等.僵尸網(wǎng)絡(luò)中的關(guān)鍵問題［J].計(jì)算機(jī)學(xué)報(bào)，2012，35(6):1192_1208.

［5]李潤恒，王明華，賈焰.基于通信特征提取和IP聚集的僵尸網(wǎng)絡(luò)相似性度量模型［J].計(jì)算機(jī)學(xué)報(bào)，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:僵尸網(wǎng)絡(luò)協(xié)同檢測體系結(jié)構(gòu)［J].通信學(xué)報(bào)，2009，30(10A):15_22.

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

［9]臧天寧，云曉春，張永錚，等.基于通信特征和D_S證據(jù)理論分析僵尸網(wǎng)絡(luò)相似度［J].通信學(xué)報(bào)，2011，32 (4):66_76.

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

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

［12]錢權(quán)，蕭超杰，張瑞.結(jié)構(gòu)化對等網(wǎng)絡(luò)中P2P僵尸網(wǎng)絡(luò)傳播模型［J].軟件學(xué)報(bào)，2012，23(12):3161_ 3174.

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

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

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

［16]蘇欣，張大方，羅章琪，等.基于Command and Control通信信道流量屬性聚類的僵尸網(wǎng)絡(luò)檢測方法［J].電子與信息學(xué)報(bào)，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

四川省教育廳重點(diǎn)項(xiàng)目（13ZA011S）；人工智能四川省重點(diǎn)實(shí)驗(yàn)室開放基金項(xiàng)目（2012RYY02）；四川理工學(xué)院培育項(xiàng)目（2012PY13）

趙攀（1976_），男，四川自貢人，副教授，碩士，主要從事計(jì)算機(jī)網(wǎng)絡(luò)通信和數(shù)據(jù)處理方面的研究，（E_mail）zhaoPanS27@gmail.com