基于優化理論的復雜網絡節點攻擊策略

孫 昱 姚佩陽 張杰勇 付 凱

?

基于優化理論的復雜網絡節點攻擊策略

孫 昱*姚佩陽 張杰勇 付 凱

(空軍工程大學信息與導航學院 西安 710077)

該文在分析傳統復雜網絡節點攻擊策略不足的基礎上提出一種新的攻擊策略，該策略的思路是將節點攻擊序列的構造問題視為一個優化問題而非傳統的評估問題。為了實現該策略，設計了復雜網絡抗毀性測度用以衡量節點攻擊序列的攻擊效果，建立了以最大化攻擊效果為目標的節點攻擊序列構造模型，提出了基于禁忌搜索的模型求解算法。在真實網絡和模擬網絡上的實驗結果表明，新策略比其它復雜網絡節點攻擊策略更為有效和優越。

復雜網絡；攻擊策略；抗毀性測度；優化模型；禁忌搜索

1 引言

復雜網絡節點攻擊是通過破壞目標網絡中的節點以使目標網絡無法維持其基本功能的行為。在實施復雜網絡節點攻擊時，目標網絡中的節點按被破壞的先后次序可以構成一個序列，該序列稱為節點攻擊序列。復雜網絡節點攻擊策略規定了節點攻擊序列的構造方式，目的是使目標網絡在節點攻擊當中迅速崩潰。復雜網絡攻擊策略的發展有利于促進復雜網絡防護策略的完善，因此研究更為有效的復雜網絡節點攻擊策略具有重要意義。

目前關于復雜網絡節點攻擊策略的研究已取得不少成果[1]。經典的節點攻擊策略包括度優先攻擊策略[2]和介數優先攻擊策略[3]。為進一步提高這兩種策略的攻擊效果，文獻[4]認為可以綜合考慮節點的度大小及其第2鄰居的數量來實施攻擊。文獻[5]分別給節點的度和介數賦予權重并選擇二者加權和大的節點優先攻擊。文獻[6]則構造了雙重判斷準則，即先攻擊度大的節點，當節點的度相同時，攻擊其中介數大的節點。文獻[7]提出了一種鄰近攻擊策略，其基本思想是若某個節點受到攻擊，則其鄰居節點接下來更可能被攻擊。文獻[8]從破壞復雜網絡社團結構的角度出發，設計了一種針對高社團成員值節點的多靶向攻擊策略。文獻[9]和文獻[10]分別定義了Damage指標和中心性指標以衡量節點在網絡中的重要程度，然后優先攻擊網絡中重要程度高的節點。文獻[11]認為通用的節點重要度指標難以準確定義，因此引入優化原理來設計最佳的節點攻擊策略。

從目前的研究進展看，大部分節點攻擊策略都是基于重要度的理念來構造節點攻擊序列，即先選擇節點的某種結構特征例如度、介數等作為其重要性度量，然后根據網絡中各節點的重要程度將節點排序形成節點攻擊序列。此類節點攻擊策略往往各有優劣，這是因為復雜網絡的結構多種多樣(研究較多如隨機網絡、小世界網絡、無標度網絡，研究較少且未統一命名的網絡類型更是不計其數)，很難找到某種結構特征在所有網絡中都能較好地度量節點的重要性。文獻[11]認識到這一點，嘗試以優化的方式解決問題，不足之處是需要事先給出攻擊強度等信息。

為了設計更為有效實用的復雜網絡節點攻擊策略，本文基于優化理論來構造節點攻擊序列。首先給出衡量節點攻擊序列攻擊效果的測度指標，然后建立節點攻擊序列構造的優化模型并提出可行的求解算法，最后對比不同攻擊策略在真實網絡和模擬網絡上的攻擊效果以驗證新策略的有效性和優越性。

2 復雜網絡抗毀性測度

復雜網絡抗毀性測度用來衡量節點攻擊序列的攻擊效果。當事先構造一個節點攻擊序列并按照中的節點排序逐個攻擊網絡中的節點時，隨著攻擊的進行，網絡最大連通分量的規模將不斷降低，因此網絡在攻擊序列下的抗毀性測度通常被定義為[12]

為了克服其不足，本文首先設計能在更為細致的粒度上反映網絡整體連通狀況的指標，然后在此基礎上定義新的網絡抗毀性測度。在一個網絡中，若兩個節點之間存在一條可達路徑，則稱這對節點是連通的。網絡中連通的節點對數越多，網絡的整體連通程度越好。若網絡中共有個連通分量，第個連通分量包含的節點數為，則網絡中連通節點對的數量為，考慮到網絡中節點對的數量最多為(其中是中的節點總數)，因此定義網絡的可用性指標為

當網絡中的節點遭受攻擊而被移除出網絡時，網絡的可用性指標值不一定單調減少，如圖1所示的網絡中，若7號節點遭到攻擊而被移除，網絡的可用性指標值將由0.71變為1。網絡受到了攻擊其可用性反而更好了，這顯然與人們的直覺認識不相符合，也為網絡抗毀性測度的定義造成了困難。

圖1 網絡示例圖

由于將1個節點移除出網絡在效果上等價于將連接到該節點的邊都移除出網絡，因此為了使網絡可用性指標值隨著攻擊的進行而單調減少，作如下規定：當網絡中節點被攻擊時，并不將該節點移除出網絡，而是將網絡中連接到該節點的所有邊都移除出網絡。根據這一規定，當網絡中的孤立節點如圖1中的7號節點受到攻擊時，網絡可用性指標值將維持不變，當網絡中的非孤立節點如圖1中的1號節點至6號節點受到攻擊時，網絡可用性指標值將降低。

3 節點攻擊序列構造

禁忌搜索是一種求解組合優化問題的有效算法[15]，具有參數少、通用性強等特點，其基本思想是從一個初始解出發，然后在其鄰域中搜索較好的解并移動到該解，重復上述步驟直至算法滿足終止準則，為了避免搜索過程陷入循環，設置禁忌列表來禁忌可能導致循環發生的搜索行為。本文首先基于禁忌搜索設計式(4)中所建模型的求解算法，然后進一步優化算法性能。

3.1 模型求解

定義3 禁忌列表是用于記憶信息的一塊存儲區域，其每一個表項可以存儲模型的一個解。

基于禁忌搜索的模型求解算法具體步驟如下：

3.2 性能優化

為了進一步提高求解算法的性能，本文從初始解構造和鄰域搜索兩個方面來優化算法。

(1)初始解構造： 較好的初始解有利于提高算法的收斂速度。求解算法在步驟1中通過隨機的方式產生初始解難以保證初始解的質量，因此本文根據問題信息針對性地構造較好的初始解。在攻擊一個網絡時，攻擊其核心節點比攻擊邊緣節點造成的破壞性更大，故可以先評價網絡中各節點的中心性程度，然后再構造初始解。

根據節點的中心性程度構造初始解的方式如下。選擇一種節點中心性度量方式，計算網絡中所有節點的中心性測度值，將中心性程度最高的節點作為節點攻擊序列中的第1個目標，將該節點從網絡中移除，重新計算剩余節點的中心性測度值，其中中心性程度最高者作為節點攻擊序列中的第2個目標，重復上述步驟直至構造出一個完整的節點攻擊序列。若各種中心性度量方式構造出的初始解不同，則在搜索時采取并行搜索思想為每個初始解開啟一個搜索任務。

4 實驗驗證

本節通過實驗證明所提復雜網絡抗毀性測度的有效性以及節點攻擊策略的優越性。本文實驗平臺為Pentium(R) Dual-Core CPU 3.0 GHz計算機和MATLAB R2010a。

仿真實驗1 為對比式(1)中定義的傳統復雜網絡抗毀性測度和式(3)中定義的新復雜網絡抗毀性測度，利用隨機網絡模型，小世界網絡模型(重連概率為0.2)和無標度網絡模型生成節點數為50，邊數為100的模擬網絡，采用經典的介數優先攻擊策略和度數優先攻擊策略攻擊這些網絡，各類型網絡均進行30組實驗，計算網絡抗毀性測度的均值并進行歸一化處理，結果如圖2所示。

圖2 復雜網絡抗毀性測度對比

從圖2中可以看到，介數優先策略的攻擊效果要優于度數優先策略，在用傳統抗毀性測度衡量時，介數優先策略在隨機網絡、小世界網絡和無標度網絡上的攻擊效果要比度數優先策略分別優8.89%, 24.79%和4.65%，用新抗毀性測度衡量時，介數優先策略分別優10.69%, 29.79%和4.11%。新測度說明了介數優先策略在隨機網絡和小世界網絡上的攻擊效果比以往料想得要更為有效一些，而在無標度網絡上的攻擊效果要比以往料想得弱一些，這是因為在無標度網絡這種節點度接近冪律分布的網絡中，各攻擊策略都能比較容易地確定其重要節點，因此攻擊效果比較接近，而在隨機網絡和小世界網絡這類節點度近似泊松分布的網絡中，確定重要節點并不像在無標度網絡中那么簡單，此時介數優先策略作為全局性策略的攻擊效果就比度數優先策略這種局部性策略更容易顯現出來。圖2中的實驗結果表明新測度更加細致地刻畫了網絡的整體狀態，因此該測度是可行有效的。

仿真實驗2 為驗證本文所提攻擊策略的優越性，首先對比不同攻擊策略在圖3所示真實網絡上的攻擊效果，其中圖3(a)是西安市蓮湖區的城區道路網，圖3(b)是中國教育和科研計算機網(CERNET)的主干網絡。實驗結果如圖4所示。

從圖4中可以看到，無論采用哪種攻擊策略，隨著受攻擊節點數量的增加，網絡的可用性都越來越差，橫向對比這3種策略可以發現，本文提出的攻擊策略能使網絡的可用性指標值下降得更為迅速。由式(3)計算得到的城區道路網在本文攻擊策略、介數攻擊策略和度數攻擊策略下的抗毀性測度值分別為0.1195, 0.1247, 0.1730, CERNET主干網在這3種攻擊策略下的抗毀性測度值分別為0.0619, 0.0671, 0.0769，即本文所提策略在城區道路網上的攻擊效果要比介數優先策略和度數優先策略分別優4.17%和30.92%，在CERNET主干網上的攻擊效果分別優7.75%和19.51%。繼續在模擬網絡上進行驗證，利用隨機網絡模型，小世界網絡模型(重連概率為0.2)和無標度網絡模型生成節點數為50，邊數為100的模擬網絡，計算模擬網絡在不同攻擊策略下的抗毀性測度，各類型網絡均進行30組實驗，結果如圖5所示。

在圖5中，本文攻擊策略所得的數據分布相對于其它兩種攻擊策略而言總體偏低，其中隨機網絡在本文攻擊策略、介數攻擊策略和度數攻擊策略下的抗毀性測度均值為0.1347, 0.1495, 0.1674，小世界網絡在這3種攻擊策略下的抗毀性測度均值為0.1300, 0.1390, 0.1980，無標度網絡在這3種攻擊策略下的抗毀性測度均值為0.1034, 0.1113, 0.1161，即本文所提策略在隨機網絡上的攻擊效果比介數攻擊策略和度數攻擊策略分別優9.90%和19.53%，在小世界網絡上的攻擊效果分別優6.47%和34.34%，在無標度網絡上的攻擊效果分別優7.10%和10.94%。圖4和圖5中的實驗結果表明本文攻擊策略不僅優越，而且適用于不同類型的網絡之中，這證明基于優化思想的節點攻擊策略魯棒、高效。

圖3 真實網絡拓撲

圖4 真實網絡上的攻擊效果

圖5 模擬網絡上的攻擊效果

仿真實驗3 復雜網絡節點重要度排序與復雜網絡節點攻擊策略之間具有密切聯系，當將節點重要度排序結果視為一個節點攻擊序列時，這種重要度排序方法就轉化成了一種攻擊策略，當將攻擊策略構造出的節點攻擊序列視為一種重要度排序結果時，這種攻擊策略就轉化成了一種節點重要度排序方法。因此本文選取幾種典型的復雜網絡節點重要度排序方法作為節點攻擊策略來與本文攻擊策略進行對比。考慮到APAR網[20]是節點重要度排序中常用的實驗對象，故本文選擇APAR網實施攻擊，實驗結果如圖6所示。

在圖6所示的4種攻擊策略中，本文攻擊策略能更快地使ARPA網的可用性降低，該網絡在本文攻擊策略、文獻[17]、文獻[18]和文獻[19]下的抗毀性測度分別為0.0857, 0.0980, 0.1095和0.1721，即本文所提策略的攻擊效果比其它策略分別優12.55%, 21.74%和50.20%。實驗結果表明本文所提策略同樣優于基于節點重要度排序思想導出的攻擊策略，換而言之，本文策略也能較好地應用于節點重要度排序工作中。

圖6 ARPA網上的攻擊效果

5 結束語

研究更為有效的復雜網絡攻擊策略是促進復雜網絡防護措施發展完善的重要途徑。本文分析了傳統攻擊策略存在的不足并引入優化思想設計了一種新策略，主要有以下幾點工作：(1)基于網絡可用性指標提出了節點攻擊序列攻擊效果的測度方式；(2)以最大化攻擊效果為目標建立了節點攻擊序列構造的優化模型；(3)基于禁忌搜索設計了模型的求解算法。不同類型網絡上的實驗結果證明了本文所提攻擊策略的有效性和優越性。本文下一步工作是在此基礎上研究網絡結構的抗毀性設計問題。

[1] JIANG Y and WANG Y B. Analysis of attack and defense strategies on complex networks[C]. Proceedings of International Conference on Sensor Network Security Technology and Privacy Communication System, Harbin, China, 2013: 58-62.

[2] ALBERT R, JEONG H, and BARABASI A L. Error and attack tolerance of complex networks[J]., 2000, 406: 378-382. doi: 10.1038/35019019.

[3] HOLME P, KIM B J, YOON C N,. Attack vulnerability of complex networks[J]., 2002, 65(5): 056109. doi: 10.1103/PhysRevE.65.056109.

[4] BELLINGERI M, CASSI D, and VINCENZI S. Efficiency of attack strategies on complex model and real-world networks [J]., 2014, 414: 174-180. doi: 10.1016/j.physa.2014. 06.079.

[5] NIE T Y, GUO Z, ZHAO K,. New attack strategies for complex networks[J]., 2015, 424: 248-253. doi: 10.1016/j.physa.2015.01.004.

[6] 聶廷遠, 郭征, 李坤龍. 復雜網絡的攻擊策略研究[J]. 計算機仿真, 2015, 32(7): 286-289. doi: 10.3969/j.issn.1006-9348. 2015.07.063.

NIE Tingyuan, GUO Zheng, and LI Kunlong. A study of attack strategies for complex networks[J]., 2015, 32(7): 286-289. doi: 10.3969/j.issn.1006- 9348.2015.07.063.

[7] XIAO S and XIAO G. On intentional attacks and protections in complex communication networks[C]. Proceedings of IEEE Global Telecommunications Conference, San Francisco, CA, USA, 2006: 1-5.

[8] 李濤, 裴文江. 針對重疊社團結構的復雜網絡多靶向攻擊策略[J]. 北京郵電大學學報, 2010, 33(3): 34-39. doi: 10.3969/ j.issn.1007-5321.2010.03.007.

LI Tao and PEI Wenjiang. Multi-targets attack strategy based on the overlapping community structure of complex networks[J]., 2010, 33(3): 34-39. doi: 10.3969/j.issn. 1007-5321.2010.03.007.

[9] WANG H, HUANG J Y, XU X M,. Damage attack on complex networks[J]., 2014, 408: 134-148. doi: 10. 1016/j.physa.2014.04.001.

[10] ANURAG S, RAHUL K, and YATINDRA N S. Impact of structural centrality based attacks in complex networks[J]., 2015, 46(2): 305-324. doi: 10.5506/ APhysPolB.46.305.

[11] DENG Y, WU J, and TAN Y J. Optimal attack strategy of complex networks based on tabu search[J]., 2016, 442: 74-81. doi: 10.1016/j.physa.2015.08.043.

[12] HERRNANN H J, SCHNEIDER C M, MOREIRA A A,. Onion-like network topology enhances robustness against malicious attacks[J].:, 2011, 1: P01027. doi: 10.1088/1742-5468/ 2011/01/P01027.

[13] SCHNEIDER C M, MOREIRA A A, ANDRADE J S,. Mitigation of malicious attacks on networks[J].,2011, 108(10): 3838-3841. doi: 10.1073/pnas. 1009440108.

[14] LOUZADA V H P, DAOLIO F, HERRMANN H J,. Smart rewiring for network robustness[J]., 2013, 1(2): 150-159. doi: 10.1093/comnet/xxx000.

[15] BURKE E K and KENDALL G. Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques[M]. New York: Springer, 2005: 165.

[16] LATORA V and MARCHIORI M. Efficient behavior of small-world networks[J]., 2001, 87(19): 198701. doi: 10.1103/PhysRevLett.87.198701.

[17] 陳勇, 胡愛群, 胡嘯. 通信網中節點重要性的評價方法[J]．通信學報, 2004, 25(8): 129-135. doi: 10.3321/ j.issn:1000-436X. 2004.08.018.

CHEN Yong, HU Aiqun, and HU Xiao. Evaluation method for node importance in communication networks[J]., 2004, 25(8): 129-135. doi: 10.3321/j.issn: 1000-436X.2004.08.018.

[18] 于會, 劉尊, 李勇軍. 基于多屬性決策的復雜網絡節點重要性綜合評價方法[J]. 物理學報, 2013, 62(2): 1-9. doi: 10.7498/ aps.62.020204.

YU Hui, LIU Zun, and LI Yongjun. Key nodes in complex networks identified by multi-attribute decision-making method[J]., 2013, 62(2): 1-9. doi: 10.7498 /aps.62.020204.

[19] 秦李, 楊子龍, 黃曙光. 復雜網絡的節點重要性綜合評價[J]. 計算機科學, 2015, 42(2): 60-64. doi: 10. 11896/j.issn.1002- 137X.2015.2.013.

QIN Li, YANG Zilong, and HUANG Shuguang. Synthesis evaluation method for node importance in complex networks [J]., 2015, 42(2): 60-64. doi: 10.11896/ j.issn.1002-137X.2015.2.013.

[20] PAGE L and PERRY J. Reliability polynomials and links importance in networks[J]., 1994, 43(1): 51-58. doi: QK.IEL.1994.0000024.0007056. 00285108.

Node Attack Strategy of Complex Networks Based on Optimization Theory

SUN Yu YAO Peiyang ZHANG Jieyong FU Kai

(,,’710077,)

This study proposes a new node attack strategy of complex networks by analyzing the disadvantages of traditional strategies. The idea of the new strategy is to treat the construction problem of node attack sequence as an optimal problem rather than an evaluation problem. To achieve this strategy, the study designs a survivability index of complex networks to measure the attack effect created by a node attack sequence, then establishes a construction model of node attack sequence with the goal to maximize attack effect, and further brings forward an algorithm based on tabu search to solve the model. Experiment results from real networks and simulated networks show that the new strategy is more effective than others.

Complex networks; Attack strategy; Survivability measurement; Optimization model; Tabu search

TP393; N949

A

1009-5896(2017)03-0518-07

10.11999/JEIT160396

2016-04-22；改回日期：2016-10-31；

2016-12-20

孫昱 suny.z@qq.com

國家自然科學基金(61573017)

The National Natural Science Foundation of China (61573017)

孫 昱： 男，1989年生，博士生，研究方向為指揮信息系統.

姚佩陽： 男，1960年生，教授，博士生導師，研究方向為指揮控制理論與技術.

張杰勇： 男，1983年生，講師，博士，研究方向為指揮控制系統建模與分析.

付 凱： 男，1987年生，博士生，研究方向為復雜系統建模與仿真.