郭海鷗，李 靜

(1.河南教育學(xué)院學(xué)報(bào)編輯部，河南鄭州 450014;2.黃河科技學(xué)院現(xiàn)代教育技術(shù)中心，河南鄭州 450063)

基于復(fù)雜網(wǎng)絡(luò)理論的互聯(lián)網(wǎng)病毒傳播的控制技術(shù)分析

郭海鷗1，李 靜2

(1.河南教育學(xué)院學(xué)報(bào)編輯部，河南鄭州 450014;2.黃河科技學(xué)院現(xiàn)代教育技術(shù)中心，河南鄭州 450063)

以具有小世界和無標(biāo)度的拓?fù)浣Y(jié)構(gòu)特征的互聯(lián)網(wǎng)為研究對象，在流行病學(xué)模型基礎(chǔ)上進(jìn)一步考慮了網(wǎng)絡(luò)連接、關(guān)聯(lián)性等因素，利用復(fù)雜網(wǎng)絡(luò)理論細(xì)致分析了互聯(lián)網(wǎng)病毒傳播的局域控制技術(shù).

復(fù)雜網(wǎng)絡(luò);互聯(lián)網(wǎng);計(jì)算機(jī)病毒;小世界;無標(biāo)度

0 引言

0.1 復(fù)雜網(wǎng)絡(luò)

近年來，復(fù)雜網(wǎng)絡(luò)的研究已越來越深入，研究者有數(shù)學(xué)、物理學(xué)、計(jì)算機(jī)網(wǎng)絡(luò)等不同領(lǐng)域的學(xué)者.在復(fù)雜網(wǎng)絡(luò)中把個體直接抽象為頂點(diǎn)，相互作用視為邊，把網(wǎng)絡(luò)的統(tǒng)計(jì)性質(zhì)稱為靜態(tài)幾何量;把具有特定幾何性質(zhì)的網(wǎng)絡(luò)機(jī)制的探索稱為網(wǎng)絡(luò)演化機(jī)制模型;把建立在網(wǎng)絡(luò)上的一些模型，例如傳染病等動態(tài)過程稱為網(wǎng)絡(luò)上的動力學(xué)性質(zhì);把各種攻擊網(wǎng)絡(luò)的方式與響應(yīng)稱為網(wǎng)絡(luò)的結(jié)構(gòu)穩(wěn)定性［1］.統(tǒng)計(jì)物理與圖論都是研究復(fù)雜網(wǎng)絡(luò)的有力工具.

0.2 互聯(lián)網(wǎng)結(jié)構(gòu)

目前主要有兩種描繪互聯(lián)網(wǎng)的結(jié)構(gòu)的方式.一種基于路由器，把每一個路由器看做節(jié)點(diǎn)，邊表示路由器之間的連接.另一種基于自治系統(tǒng)(AS)，AS的子網(wǎng)絡(luò)采用不同內(nèi)部路由算法.每個AS代表一個節(jié)點(diǎn)，BGP對等連接兩個AS，則表示這兩個AS之間有一條邊相連.互聯(lián)網(wǎng)是一種非均勻網(wǎng)絡(luò)并且節(jié)點(diǎn)的度有很大的波動性，表現(xiàn)出很強(qiáng)的冪律分布的特點(diǎn).目前互聯(lián)網(wǎng)拓?fù)渲饕腔贐arabási和Albert提出來的復(fù)雜網(wǎng)絡(luò)的BA演化模型及其改進(jìn)型的局部演化模型［2］，有路由器和自治域兩種不同層次來描述計(jì)算機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu).

0.3 基于流行病學(xué)傳播模型的計(jì)算機(jī)病毒傳播模型

生物學(xué)中對病毒傳播的研究是一個重要研究領(lǐng)域，已經(jīng)建立了流行病學(xué)傳播模型.在20世紀(jì)90年代初期一些科學(xué)家就注意到病毒(生物病毒及計(jì)算機(jī)病毒)有一些共性，在流行病學(xué)模型基礎(chǔ)上考慮網(wǎng)絡(luò)連接、關(guān)聯(lián)性等因素，把生物學(xué)中流行病學(xué)傳播模型引入到計(jì)算機(jī)病毒的研究之中，基于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)分析計(jì)算機(jī)病毒的傳播，流行病學(xué)模型的基本思想是計(jì)算機(jī)病毒傳播模型的重要基礎(chǔ)［3］.

1 基于復(fù)雜網(wǎng)絡(luò)理論的互聯(lián)網(wǎng)安全技術(shù)研究

在互聯(lián)網(wǎng)安全研究領(lǐng)域中，病毒防范的研究，主要采取合理的反病毒和預(yù)防策略，通過一定措施減慢病毒傳播、切斷病毒傳播鏈、降低病毒危害，目前還是一個沒有解決的問題.

1.1 復(fù)雜網(wǎng)絡(luò)中的病毒防范技術(shù)

復(fù)雜網(wǎng)絡(luò)中的病毒傳播是當(dāng)前復(fù)雜網(wǎng)絡(luò)研究的一個熱點(diǎn)問題［4］.復(fù)雜網(wǎng)絡(luò)具有小世界和無標(biāo)度的拓?fù)浣Y(jié)構(gòu)，互聯(lián)網(wǎng)對隨機(jī)錯誤有很強(qiáng)的魯棒性，不過在惡意攻擊下表現(xiàn)得比較脆弱.有時僅僅只是很微少的病毒感染源，如果不加以認(rèn)真控制，就可能產(chǎn)生大規(guī)模的病毒流行.目前，針對免疫策略做了許多研究，根據(jù)節(jié)點(diǎn)的度來選擇重要的免疫節(jié)點(diǎn).典型的免疫控制策略有隨機(jī)免疫(網(wǎng)絡(luò)中免疫節(jié)點(diǎn)完全隨機(jī)選取)，目標(biāo)免疫(對少量度大的節(jié)點(diǎn)免疫)，熟人免疫(免疫節(jié)點(diǎn)是隨機(jī)選出的節(jié)點(diǎn)的鄰居).不過即使對網(wǎng)絡(luò)的大量節(jié)點(diǎn)進(jìn)行免疫，仍不能徹底阻止病毒的傳播.

無論哪種免疫策略，都以節(jié)點(diǎn)的度為標(biāo)準(zhǔn).實(shí)際上可以從另外一個角度出發(fā)，從感染源出發(fā)，不考慮節(jié)點(diǎn)的度.在感染源周圍進(jìn)行局域控制，控制范圍如何選擇成為關(guān)鍵.控制包含預(yù)防、隔離、免疫、殺毒等各種應(yīng)對措施.在理想小世界網(wǎng)絡(luò)、無標(biāo)度網(wǎng)絡(luò)和隨機(jī)圖網(wǎng)絡(luò)中，要抑制病毒的大范圍傳播，只要對距離感染源d步范圍內(nèi)的節(jié)點(diǎn)進(jìn)行控制即可，一般存在很小的路徑長度范圍d.小世界網(wǎng)絡(luò)在d=3時通過少量的控制節(jié)點(diǎn)就可以達(dá)到零感染的最優(yōu)效果.對于距離相對近的節(jié)點(diǎn)較集中時，網(wǎng)絡(luò)拓?fù)湓谙喈?dāng)程度上可以抑制病毒的傳播，局域控制的效果更好.

各種網(wǎng)絡(luò)模型所產(chǎn)生的結(jié)構(gòu)與真實(shí)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)一般會存在一些差異，有關(guān)互聯(lián)網(wǎng)局域免疫模型實(shí)證研究目前尚無報(bào)道.在規(guī)模較小的互聯(lián)網(wǎng)中，具有無標(biāo)度和小世界的拓?fù)浣Y(jié)構(gòu)特征的互聯(lián)網(wǎng)局域免疫模型自身特點(diǎn)鮮明，應(yīng)用復(fù)雜網(wǎng)絡(luò)理論研究互聯(lián)網(wǎng)的局域免疫模型有重要價(jià)值.

1.2 基于復(fù)雜網(wǎng)絡(luò)理論的流行病學(xué)模型

Newman等人研究了小網(wǎng)絡(luò)上的傳染病模型［5］，在這個模型中，感染者比例存在一個閾值，但要比規(guī)則網(wǎng)絡(luò)小很多.而對于無標(biāo)度網(wǎng)絡(luò)上傳染病模型，無論SIS還是SIR模型，沒有類似的閾值［2］，即只要有傳染病發(fā)生，就會大范圍傳播.因此，不能完全依賴于醫(yī)療衛(wèi)生水平的提高來控制這種網(wǎng)絡(luò)上的傳染病，需要改變網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，典型方法是隔離傳染源，即強(qiáng)行阻斷某些聯(lián)接，去掉一些頂點(diǎn).通常網(wǎng)絡(luò)中去邊與去點(diǎn)稱為對網(wǎng)絡(luò)的攻擊，所以，不同攻擊方式下的網(wǎng)絡(luò)結(jié)構(gòu)穩(wěn)定性是與網(wǎng)絡(luò)物理模型密切相關(guān)的.隨機(jī)性的增加使網(wǎng)絡(luò)中流行病的傳播閾值降低，有利流行病的傳播.在隨機(jī)網(wǎng)絡(luò)的增長中，隨著網(wǎng)絡(luò)尺寸的增大，流行病的傳播閾值逐漸減小，其衰減速率也逐漸變小，表現(xiàn)收斂的趨勢.

如果無標(biāo)度網(wǎng)絡(luò)尺寸無限大，網(wǎng)絡(luò)的結(jié)構(gòu)在空間或時間上將無序，度分布具有冪律性，流行病傳播閾值將不存在.

對于WS模型，流行病的傳播呈現(xiàn)出明顯的相變行為，閾值非零，不依賴于網(wǎng)絡(luò)的尺寸;然而，在隨機(jī)增長網(wǎng)絡(luò)中，傳播閾值將依賴于網(wǎng)絡(luò)的尺寸大小，隨著網(wǎng)絡(luò)尺寸的增大而逐漸減小，其衰減的速率也變小.對有限尺寸的網(wǎng)絡(luò)，也有非零的傳播閾值.傳播閾值隨著系統(tǒng)尺寸的增大也是逐漸減小的.

1.3 基于復(fù)雜網(wǎng)絡(luò)理論的流行病學(xué)模型的互聯(lián)網(wǎng)反病毒技術(shù)

在生物學(xué)流行病學(xué)模型中，模型基本的狀態(tài)包括3部分:S:易染狀態(tài);I:被感染狀態(tài);R:被移除狀態(tài)(免疫狀態(tài)).常常用狀態(tài)之間的轉(zhuǎn)換過程來命名模型.SIR模型:易染群體被感染，然后恢復(fù)健康并具有免疫性.SIS模型:如果易染群體被感染后，又返回到易染狀態(tài).網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)嚴(yán)重影響傳播速率，在局域(local)和稀疏(sparse)兩種結(jié)構(gòu)的圖中病毒的傳播有許多不同之處.病毒傳播速率在稀疏結(jié)構(gòu)中慢，病毒傳播擴(kuò)散的概率也小，病毒傳播也沒有優(yōu)先方向.

計(jì)算機(jī)之間經(jīng)常通過電子郵件等進(jìn)行程序或文檔的交換，這些交換關(guān)系通常是在一個組群中的，這種網(wǎng)絡(luò)連接存在非均勻性，對數(shù)據(jù)交換有重要影響.計(jì)算機(jī)病毒的傳播在這種網(wǎng)絡(luò)中是有優(yōu)先方向的，顯然這里是局域結(jié)構(gòu).這種模型是一種分析計(jì)算機(jī)病毒傳播的很有效模型.隨機(jī)網(wǎng)絡(luò)上的傳播行為與小世界網(wǎng)絡(luò)上的十分相似.在冪律網(wǎng)絡(luò)中，可能是冪律分布網(wǎng)絡(luò)的平均路徑長度較小和節(jié)點(diǎn)的度差異較大，病毒的傳播速率要快得多.病毒一開始都是感染度大的節(jié)點(diǎn)，這些度大的節(jié)點(diǎn)會迅速傳播更多的病毒副本，從而產(chǎn)生“放大效應(yīng)”.冪律分布網(wǎng)絡(luò)在非重復(fù)感染的情況下最終未被感染的節(jié)點(diǎn)比隨機(jī)網(wǎng)絡(luò)和小世界網(wǎng)絡(luò)多.這3類不同拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)具有接近的平均度，不過冪律網(wǎng)絡(luò)被感染的概率較小，冪律網(wǎng)絡(luò)最終被感染的節(jié)點(diǎn)數(shù)較少，這是因?yàn)閮缏删W(wǎng)絡(luò)小于平均度的節(jié)點(diǎn)更多.互聯(lián)網(wǎng)是關(guān)聯(lián)網(wǎng)絡(luò)，互聯(lián)網(wǎng)的傳播生命期通常比非關(guān)聯(lián)網(wǎng)絡(luò)長，不過對于有限大小企業(yè)內(nèi)部關(guān)聯(lián)網(wǎng)絡(luò)，其傳播速率臨界值要比互聯(lián)網(wǎng)大一些，它們都比非關(guān)聯(lián)網(wǎng)絡(luò)有更強(qiáng)的魯棒性.抑制互聯(lián)網(wǎng)病毒的一種重要方法是免疫.目前這仍是一個沒有解決的問題.選擇免疫(目標(biāo)免疫)和隨機(jī)免疫(均勻免疫)是目前主要的兩種互聯(lián)網(wǎng)病毒免疫策略.隨機(jī)免疫對度小的節(jié)點(diǎn)(相對安全)和度大的節(jié)點(diǎn)(被感染的風(fēng)險(xiǎn)高)是平等對待的，通常適合隨機(jī)網(wǎng)絡(luò)，進(jìn)行免疫時沒有優(yōu)先順序，隨機(jī)地選擇節(jié)點(diǎn).隨機(jī)免疫法在小世界網(wǎng)絡(luò)中作用非常有限，隨機(jī)免疫法能夠局部抑制感染，但速度慢.在無限小世界網(wǎng)絡(luò)中，不存在臨界問題，臨界值g=1，隨機(jī)免疫法要免疫所有節(jié)點(diǎn)才能達(dá)到免疫徹底，這是無法實(shí)現(xiàn)的，隨機(jī)免疫不能保證最終消滅感染.互聯(lián)網(wǎng)是一種小世界網(wǎng)絡(luò)，采用隨機(jī)免疫即使對其上多數(shù)節(jié)點(diǎn)都進(jìn)行隨機(jī)免疫，也不能阻止計(jì)算機(jī)病毒的發(fā)生.

目標(biāo)免疫利用互聯(lián)網(wǎng)絡(luò)的非均勻性特點(diǎn)選擇節(jié)點(diǎn)，呈現(xiàn)小世界網(wǎng)絡(luò)特征的互聯(lián)網(wǎng)，具有一些度大的節(jié)點(diǎn)，選取這些度大的節(jié)點(diǎn)進(jìn)行目標(biāo)免疫，它們所連的眾多邊就可以從網(wǎng)絡(luò)中去掉，重構(gòu)了互聯(lián)網(wǎng)網(wǎng)絡(luò)的結(jié)構(gòu)，從而阻止大部分網(wǎng)絡(luò)病毒的傳播.目標(biāo)免疫的免疫臨界值要比隨機(jī)網(wǎng)絡(luò)的免疫臨界值小很多.

當(dāng)前互聯(lián)網(wǎng)一些反病毒軟件的生命期還是相當(dāng)長的，文件掃描和防病毒更新的過程是一種隨機(jī)免疫過程，由于互聯(lián)網(wǎng)的小世界特征，在整個互聯(lián)網(wǎng)中，就是眾多節(jié)點(diǎn)都被免疫，從上面的分析，這些反病毒軟件也不能根除互聯(lián)網(wǎng)病毒的傳播.采用目標(biāo)免疫法是一種較好的方法，單采取上面方法獲取互聯(lián)網(wǎng)中各節(jié)點(diǎn)的度，特別是那些中心節(jié)點(diǎn)的度，以便對其進(jìn)行免疫，對于復(fù)雜的互聯(lián)網(wǎng)來說，這不是一件容易的事情.

在互聯(lián)網(wǎng)中，有少量的中心節(jié)點(diǎn)對互聯(lián)網(wǎng)的運(yùn)行起著重要的作用，這些節(jié)點(diǎn)的安全性是至關(guān)重要的，然而正是這些節(jié)點(diǎn)存在著很大的安全漏洞，這使得針對高節(jié)點(diǎn)度的中心節(jié)點(diǎn)的智能攻擊有時顯得很容易，從而互聯(lián)網(wǎng)顯得非常脆弱.實(shí)驗(yàn)表明只要5%～10%的中心節(jié)點(diǎn)同時受到攻擊并失效，整個互聯(lián)網(wǎng)將成一些相互隔絕的“信息孤島”，整個互聯(lián)網(wǎng)也就此癱瘓.互聯(lián)網(wǎng)動力學(xué)機(jī)制是什么呢?這個問題至今還沒有一個圓滿的答案，否則就有可能根據(jù)需要，設(shè)計(jì)出一個安全性更高、性能更為優(yōu)越的網(wǎng)絡(luò).

2 總結(jié)

對具有小世界和無標(biāo)度拓?fù)浣Y(jié)構(gòu)特征的互聯(lián)網(wǎng)，在流行病學(xué)模型基礎(chǔ)上考慮到網(wǎng)絡(luò)連接、關(guān)聯(lián)性等因素，可利用復(fù)雜網(wǎng)絡(luò)理論來研究計(jì)算機(jī)病毒傳播的臨界值問題.將是今后互聯(lián)網(wǎng)網(wǎng)絡(luò)安全研究的重要領(lǐng)域.

［1］ 汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用［M］.北京:清華大學(xué)出版社，2006.

［2］ BARABáSI A L，ALBERT R.Emergence of scaling in random networks［J］.Seience，1999，286(5439):509-512.

［3］ 徐丹，李翔，汪小帆.復(fù)雜網(wǎng)絡(luò)理論在互聯(lián)網(wǎng)病毒傳播研究中的應(yīng)用［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2004，1(3):10-26.

［4］ 徐丹，李翔，汪小帆.復(fù)雜網(wǎng)絡(luò)病毒傳播的局域控制研究［J］.物理學(xué)報(bào)，2007，56(3):1313-1317.

［5］ 吳金閃，狄增加.從統(tǒng)計(jì)物理學(xué)看復(fù)雜網(wǎng)絡(luò)研究［J］.物理學(xué)進(jìn)展，2004，24(1):18-46.

TP393.08

A

1007-0834(2011)02-0040-02

10.3969/j.issn.1007-0834.2011.02.014

2011-03-12

河南省科技攻關(guān)項(xiàng)目(112102310377)

郭海鷗(1964—)男，河南靈寶人，河南教育學(xué)院學(xué)報(bào)編輯部副教授，主要研究方向:復(fù)雜網(wǎng)絡(luò).