崔強 譚敏生 王靜

南華大學計算機科學與技術(shù)學院 湖南 421001

0 前言

隨著復雜網(wǎng)絡研究的興起，作為復雜網(wǎng)絡最重要的課題之一，對復雜網(wǎng)絡攻擊與修復策略的研究的重大理論意義和應用價值日益凸顯出來，人們開始關(guān)注：這些復雜的網(wǎng)絡到底有多可靠？在網(wǎng)絡遭受攻擊后如何高效快速的修復網(wǎng)絡？例如2008年1月25日，在持續(xù)了十多天的冰雪天氣后，湖南、浙江、安徽、江蘇、福建、湖北、四川、重慶、貴州、云南、廣西、廣東等電網(wǎng)的電力設施均遭到不同程度破壞，局部地區(qū)由于電力設施毀壞嚴重使電力供應中斷達數(shù)天之久。電網(wǎng)和交通的癱瘓使一些縣城、鄉(xiāng)鎮(zhèn)成了孤島，交通癱瘓、電力中斷、供水停止、燃料告急、食物緊張。那么當出現(xiàn)此種情況后如何快速修復我們的生命線網(wǎng)絡就變得尤其重要。

1 攻擊策略

復雜網(wǎng)絡通常面臨兩種攻擊：隨機性攻擊(Random attack)和選擇性攻擊(Selective attack)。所謂隨機性攻擊就是網(wǎng)絡節(jié)點(邊)以某種概率被隨機的破壞；而選擇性攻擊是網(wǎng)絡節(jié)點(邊)按一定的策略被破壞，一般按照節(jié)點的度值大小依次去除節(jié)點。一般來說，網(wǎng)絡自身原因引起的故障屬于隨機性攻擊，而蓄意的破壞則屬于選擇性攻擊。例如，敵人在選擇攻擊目標時，總是先選擇重要的軍事目標，而不是隨機破壞。所以研究攻擊策略的效率，時效性就變得很有意義。

1.1 基于不完全網(wǎng)絡拓撲信息的有目的攻擊

有關(guān)攻擊策略的仿真研究中，比較全面的要數(shù)Holme等的研究工作。他們將攻擊策略分為節(jié)點攻擊與邊攻擊兩種方式。每種攻擊又包括四種不同的策略：①ID移除策略。對初始網(wǎng)絡按節(jié)點或邊的度大小順序來移除節(jié)點或邊；②IB移除策略。對初始網(wǎng)絡按照節(jié)點或邊的介數(shù)大小順序來移除節(jié)點或邊；③RD移除策略。每次移除的節(jié)點或邊是當前網(wǎng)絡中節(jié)點或邊的度最大的節(jié)點；④RB移除策略。每次移除的節(jié)點或邊是當前網(wǎng)絡中節(jié)點或邊介數(shù)最大的節(jié)點。ER模型對節(jié)點的基于度的攻擊比基于介數(shù)的攻擊效果好，使用重新計算的信息比基于原始信息的危害性更強 ；而對邊的攻擊RB遠比其他策略更具破壞性。無尺度網(wǎng)絡對節(jié)點移除比ER模型更敏感，在攻擊初期四種策略的差異性不明顯，隨著移除的繼續(xù)進行，攻擊對網(wǎng)絡的破壞程度按以下順序排列：RB>RD>ID>IB；而且對邊的攻擊情況同節(jié)點攻擊相似。作者還對Internet等真實網(wǎng)絡作了數(shù)字分析，驗證了Albert等的結(jié)論。

1.2 基于局部網(wǎng)絡拓撲信息的分布式攻擊

分布式攻擊能逐步在網(wǎng)絡上傳播，攻擊已經(jīng)“淪陷”節(jié)點的鄰節(jié)點，且下一個攻擊目標的選擇僅僅需要節(jié)點的局部信息——被攻擊節(jié)點的鄰節(jié)點的度值信息。如果一個節(jié)點被攻擊，本文稱之為“淪陷”節(jié)點，否則稱之為“存活”節(jié)點。

本文基于Internet真實子網(wǎng)和BA網(wǎng)絡模型(網(wǎng)絡模型同上)，對以下3種分布式攻擊策略的攻擊效率進行仿真測試：

（1）貪婪順序攻擊：選擇與上一步被攻擊節(jié)點相連的最大度值“存活”節(jié)點作為攻擊目標。如果沒有這樣的節(jié)點存在，則隨機選擇一個“存活”節(jié)點作為攻擊目標。

（2）協(xié)同攻擊：搜索“淪陷”節(jié)點的“存活”鄰節(jié)點，在它們中選擇一個最大度值的“存活”節(jié)點作為攻擊目標。如果沒有這樣的節(jié)點存在，則隨機選擇一個“存活”節(jié)點繼續(xù)展開攻擊。

（3）限下界平行攻擊：不同于每步只攻擊一個與“淪陷”節(jié)點相鄰的最大度值節(jié)點，而是攻擊所有滿足以下兩個條件的“存活”節(jié)點：與“淪陷”節(jié)點鄰接；度值在預先設定的界值之上。

圖1 貪婪順序攻擊和協(xié)同攻擊的攻擊效率

圖1比較了貪婪順序攻擊和協(xié)同攻擊各自的攻擊效率。結(jié)果表明，貪婪順序攻擊并不能高效地擊垮整個網(wǎng)絡，相反，僅利用局部信息的協(xié)同攻擊卻能得到與有目的攻擊差不多的崩潰閾值。這個觀察結(jié)果可以這樣理解，在貪婪順序攻擊中，因為沒有中心節(jié)點與剛剛淪陷的節(jié)點相鄰，大量攻擊步驟都不得不攻擊許多小度值的節(jié)點。在協(xié)同攻擊中，每一步能夠在比較多的節(jié)點中選擇下一步的攻擊目標，因此，很少會需要攻擊小度值的節(jié)點。協(xié)同攻擊最主要的缺點就是，為了找到下一個攻擊目標，在攻擊前要收集所有“淪陷”節(jié)點的度值信息。

圖2 平行攻擊的攻擊效率

為了減少攻擊前節(jié)點間非常復雜的協(xié)作和信息交換，本文提出了限下界的平行攻擊。這種攻擊方式非常類似于現(xiàn)實世界的攻擊。為了避免攻擊許多低度值的節(jié)點，本文設定的下界值分別是4和10，也就是說與上一步被攻擊節(jié)點鄰接的節(jié)點的度值大于4和10時，才會被攻擊。

仿真結(jié)果如圖2所示。在Internet模型中，下界值為10的攻擊和有目的攻擊一樣高效，崩潰閾值從3.8%只輕微上升到4.1%。假如設置的下界值是4，在網(wǎng)絡崩潰前，攻擊節(jié)點數(shù)增多(崩潰閾值變?yōu)?.7%)，并且由于每一步攻擊的節(jié)點數(shù)增多，攻擊的步驟減少。在BA模型中觀察的結(jié)果是不同的，如果下界值設定為4，崩潰閾值非常接近于有目的攻擊(崩潰閾值為16%)。當下界值設定為10，攻擊將在17步后終止，因為這時所有“淪陷”節(jié)點的存活鄰節(jié)點的度值都低于下界值，此時，網(wǎng)絡還存在較大的連通子圖。

可以這樣理解所觀察到的結(jié)果，僅僅掌握Internet局部網(wǎng)絡拓撲信息，只攻擊度值相對大的節(jié)點，同樣可以摧毀整個網(wǎng)絡。從圖2可以看出，在早期，網(wǎng)絡分解速度較慢，在某些步驟以后，分解的速度急劇加快。因此，為了保護Internet免遭這種分布式攻擊的破壞，關(guān)鍵在于盡早識別并阻止攻擊。此外，選擇合適的閾值對攻擊方非常重要：太低的閾值需要攻擊更多度值小的節(jié)點，使攻擊速度變慢，攻擊時間延長，這樣一來防御方有機會加強保護，甚至對攻擊者予以反擊；而設定太高的閾值使攻擊的破壞程度降低，甚至不可能摧毀整個網(wǎng)絡。

2 復雜網(wǎng)絡修復策略

目前國際和國內(nèi)雖然對網(wǎng)絡的修復性有一定研究但對復雜網(wǎng)絡遭到破壞的研究還只局限于研究復雜網(wǎng)絡的魯棒性，即復雜網(wǎng)絡對外界的破壞的承受能力。即使一些文章中涉及到復雜網(wǎng)絡的修復性研究但其修復策略和一般網(wǎng)絡的修復策略也沒什么區(qū)別，而我們首次針對復雜網(wǎng)絡的冪率分布特性提出了一種基于馬太效應的復雜網(wǎng)絡修復策略。

2.1 相關(guān)研究

（1）在文獻[3]中總結(jié)了基于拓撲信息的修復策略，在此種修復策略中分析拓撲圖論與網(wǎng)絡生存性的關(guān)系，介紹拓撲圖論算法在網(wǎng)絡修復中的實際應用，對基于網(wǎng)絡分割的故障修復算法、基于拓撲結(jié)構(gòu)的修復路徑選擇算法、用于鏈路故障保護的P-Cycle 算法等進行比較，研究和探討了目前網(wǎng)絡修復中亟待解決的問題。網(wǎng)絡的修復與網(wǎng)絡的生存性密切相關(guān)，但從目前的研究成果來看，兩者的結(jié)合還不夠，而且大多數(shù)研究考慮的拓撲結(jié)構(gòu)簡單、故障種類單一。目前的網(wǎng)絡拓撲研究在物理拓撲和邏輯拓撲上是混淆的。這就導致了基于網(wǎng)絡拓撲結(jié)構(gòu)的修復算法難以用實驗仿真也難于實現(xiàn)，而且從大型實際網(wǎng)絡中測量其全部拓撲也存在一定的難度這就導致了此種修復策略的實用性不高。

（2）以一定的修復幾率重新連接遭到襲擊的節(jié)點和網(wǎng)絡中的其它節(jié)點。在其修復模型中是以一定的修復幾率來修復網(wǎng)絡的并沒有考慮復雜網(wǎng)絡本身的一些特性這就使得此種修復模型的針對性不強，而我們的修復策略充分考慮了復雜網(wǎng)絡的冪率特性及其在隨機重連時的馬太效應，所以我們的修復策略更具有針對性。

（3）網(wǎng)絡修復過程中的評價標準：最大效率法和Horn算法。對網(wǎng)絡修復算法提出了量化的評價標準。

2.2 基于馬太效應的復雜網(wǎng)絡修復方法

近年來在復雜網(wǎng)絡研究上的一重大發(fā)現(xiàn)是許多復雜網(wǎng)絡，包括Internet、WWW以及新陳代謝網(wǎng)絡等的鏈接度分布函數(shù)具有冪率形式。BA網(wǎng)絡模型能很好的反映這一特性，BA網(wǎng)絡模型的生成過程很好的考慮了實際網(wǎng)絡的以下兩個特性 ：

（1）增長(growth)特性：即網(wǎng)絡的規(guī)模不斷擴大。

（2）優(yōu)先連接(preferential attachment)特性：即新的節(jié)點更傾向于與那些具有較高連接度的“大”節(jié)點相連接。這種現(xiàn)象也稱為“馬太效應(Matthew effect)”。

我們從無標度網(wǎng)絡的馬太效應出發(fā)研究馬太效應在復雜網(wǎng)絡修復中的應用。我們主要考慮持續(xù)攻擊下的隨機刪除節(jié)點和有目的刪除節(jié)點(比如刪除網(wǎng)絡中的最大度值節(jié)點)，在這種攻擊中以比率r優(yōu)先選擇刪除一個節(jié)點的同時把一個節(jié)點重新連接到網(wǎng)絡上，我們假設新加入到網(wǎng)絡中的節(jié)點選擇網(wǎng)絡中度值最大的節(jié)點連接。失去鄰接點的節(jié)點不是坐以待斃而是重新連接其他節(jié)點來代替丟失的鄰節(jié)點；此外，被攻擊的節(jié)點作為新節(jié)點重新連接到網(wǎng)絡中。這樣，當攻擊網(wǎng)絡的最大度值節(jié)點時，補償動力學協(xié)議仍然能夠保護密率分布的指數(shù)。而且，我們的仿真顯示即使在很高比率的優(yōu)先攻擊下或攻擊網(wǎng)絡中的大度值節(jié)點時，只要新加入的節(jié)點擁有m≥2的隨機連接網(wǎng)絡就能夠保持一個很大的連接部分；這樣，失去的連接就不再是這個持續(xù)攻擊的損害結(jié)果。

我們是把構(gòu)建BA網(wǎng)絡的思想應用到冪率分布網(wǎng)絡的修復中能得到很好的效果，這不僅能得到很高的修復率而且還能優(yōu)化網(wǎng)絡的拓撲結(jié)構(gòu)。我們的方針結(jié)果顯示在此種修復方法下對internet網(wǎng)絡和BA網(wǎng)絡的修復率可達98%以上，即使攻擊網(wǎng)絡中的最大度值節(jié)點修復率也可達到95%以上。

3 結(jié)論

本文分別研究了基于不完全網(wǎng)絡拓撲信息的有目的攻擊和局部網(wǎng)絡拓撲信息的分布式攻擊下以及有關(guān)復雜網(wǎng)絡修復策略的相關(guān)研究并提出了基于馬太效應復雜網(wǎng)絡修復策略，該研究對于制定高效的攻擊策略和修復策略具有重要的意義特別是在軍事領域具有很高的實用價值。

[1] Watts D J,Strogatz S H.Collective dynamics of small-world networks[J].Nature.1998.

[2] Holme P, Kim B J, Yoon C N, et al. Attack vulnerability of complex networks[J]. Phys.Rev.E.2002.

[3] 繆志敏,丁力等.基于拓撲信息的網(wǎng)絡修復[J].計算機工程.2009.