熊金石 ,李建華

(空軍工程大學(xué)信息與導(dǎo)航學(xué)院,西安710077)

隨著信息系統(tǒng)的廣泛應(yīng)用,信息系統(tǒng)的安全性成為關(guān)注的焦點(diǎn)。系統(tǒng)學(xué)認(rèn)為系統(tǒng)結(jié)構(gòu)決定功能,保持著系統(tǒng)元素之間交互基本性質(zhì)的網(wǎng)絡(luò)模型是描述復(fù)雜系統(tǒng)的最有效模型[1]。研究網(wǎng)絡(luò)化信息系統(tǒng)網(wǎng)絡(luò)模型拓?fù)浣Y(jié)構(gòu)的抗毀性,對于評估信息系統(tǒng)安全性能具有重要意義。

目前,網(wǎng)絡(luò)抗毀性研究主要基于兩大理論:圖論和統(tǒng)計物理[2]。傳統(tǒng)圖論中有很多圖的不變量被用來刻畫小規(guī)模簡單網(wǎng)絡(luò)的抗毀性,如連通度、堅韌度、完整度、粘連度等。近年來,網(wǎng)絡(luò)研究的焦點(diǎn)從研究小規(guī)模簡單網(wǎng)絡(luò)的精確性質(zhì)轉(zhuǎn)變?yōu)檠芯看笠?guī)模復(fù)雜網(wǎng)絡(luò)的統(tǒng)計屬性,統(tǒng)計物理的很多方法開始被廣泛應(yīng)用到復(fù)雜網(wǎng)絡(luò)研究中。

1 網(wǎng)絡(luò)抗毀性

要研究抗毀性問題,首先得搞清楚抗毀性的定義。網(wǎng)絡(luò)抗毀性(invulnerability)的定義比較多,如美國國家標(biāo)準(zhǔn)化組織給出的抗毀性定義是:在發(fā)生自然和人為故障的情況下,網(wǎng)絡(luò)能夠利用各種恢復(fù)技術(shù)維修或恢復(fù)到可接受水平的能力、利用網(wǎng)絡(luò)的各種預(yù)防性技術(shù)防止和減緩網(wǎng)絡(luò)業(yè)務(wù)損傷的能力。比較公認(rèn)的定義是Ellison等人給出的:網(wǎng)絡(luò)抗毀性是指網(wǎng)絡(luò)系統(tǒng)在遭受攻擊、故障和意外事故時仍能夠及時完成其關(guān)鍵任務(wù)的能力。

網(wǎng)絡(luò)的抗毀性是從圖論的概念中提出來的,在通信網(wǎng)可靠性分析中得到了廣泛應(yīng)用[3]?？箽詮木W(wǎng)絡(luò)連通性的角度描述網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對通信網(wǎng)可靠性的影響,它是可靠性的一種確定性測度,實質(zhì)是研究網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的可靠性,是網(wǎng)絡(luò)可靠性的一種靜態(tài)指標(biāo)。對于一個網(wǎng)絡(luò),抗毀性是指至少需要破壞幾個節(jié)點(diǎn)或幾條鏈路才能中斷部分節(jié)點(diǎn)之間的通信,即指出破壞一個網(wǎng)絡(luò)的困難程度。

2 網(wǎng)絡(luò)化信息系統(tǒng)的圖論表示

網(wǎng)絡(luò)模型是在合理簡化網(wǎng)絡(luò)化信息系統(tǒng)后,利用適當(dāng)表現(xiàn)形式對主要特征描繪得到的分析對象。網(wǎng)絡(luò)模型一般具有3種功能[4]:首先,提供一個框架,恰當(dāng)?shù)卣砗徒y(tǒng)計觀察數(shù)據(jù),對真實網(wǎng)絡(luò)的行為、結(jié)構(gòu)和演化做出解釋,即解釋功能;其次,根據(jù)真實網(wǎng)絡(luò)現(xiàn)在的行為,預(yù)測未來行為特性,即預(yù)測功能;最后,按照目標(biāo)規(guī)則影響和改變網(wǎng)絡(luò)行為特性和演化進(jìn)程,即規(guī)范功能。

網(wǎng)絡(luò)可以用圖G=(V,E)表示,假設(shè)G有n個節(jié)點(diǎn),m條邊,用 V={v1,v2,…,vn}表示G的節(jié)點(diǎn)集合,E={e1,e2,…,em} B×V表示邊的集合。圖G的鄰接矩陣A=[aij],其中:

矩陣中的各元素為0或1,其中0代表兩節(jié)點(diǎn)之間無直接連接,1代表兩節(jié)點(diǎn)之間有直接連接。

3 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)抗毀性測度

抗毀性測度是網(wǎng)絡(luò)抗毀性的度量指標(biāo),選取的指標(biāo)是否合理對于客觀評估網(wǎng)絡(luò)化指揮信息系統(tǒng)抗毀能力而言是至關(guān)重要的[2]。

給定一個圖G,用V(G)和E(G)分別表示它的頂點(diǎn)集合和邊集合。圖G的點(diǎn)割集C V(G)是指去掉頂點(diǎn)子集C后,圖G就不連通了;圖G的邊割集C E(G)是指去掉邊子集C后,圖G就不連通了。如果一個圖 G是連通的,那么它的連通性如何?一般的刻畫方法是點(diǎn)連通度和邊連通度來進(jìn)行刻畫的[5-6]。但是隨著問題的深入研究,人們發(fā)現(xiàn)連通度并不考慮一旦圖被破壞后,余下的子圖的連通情況。所以后來人們提出用圖的糙度、散度以及完整度來刻畫圖的連通性,再后來提出了系統(tǒng)的核與核度的方法來刻畫圖的連通性[7-8]。

首先給出系統(tǒng)的核和核度的定義。

定義1 對于給定系統(tǒng)X,假設(shè)去掉或者破壞掉該系統(tǒng)的若干個主要素,對于該系統(tǒng)的破壞性最大,則把這“若干個主要素”稱為該系統(tǒng)的核,記為S＊。

定義2 對于給定系統(tǒng) X,若該系統(tǒng)的核為S＊,則記該系統(tǒng)的核度為h(X):

其中,ω(X)表示系統(tǒng)X的連通分支數(shù)。

準(zhǔn)則1 對于一個給定的系統(tǒng)X,該系統(tǒng)的核S＊必須滿足:

其中,S′是由X中若干個主要素構(gòu)成。

由于網(wǎng)絡(luò)化信息系統(tǒng)的連通性完全取決于其拓?fù)鋱DG的連通性,而根據(jù)網(wǎng)絡(luò)抗毀性的定義,對于抗毀性度量的選擇可采用網(wǎng)絡(luò)連通性的方法,而網(wǎng)絡(luò)的連通性又可以用網(wǎng)絡(luò)的核和核度來刻畫。因此,用網(wǎng)絡(luò)化信息系統(tǒng)所對應(yīng)的拓?fù)浣Y(jié)構(gòu)圖的核和核度來刻畫網(wǎng)絡(luò)化信息系統(tǒng)的抗毀性問題。

下面給出圖的核與核度的定義。

定義3 對于給定的圖G,定義該圖的核度,記為h(G):

定義4 對于給定的圖G,若S＊滿足

則稱S＊為圖G的核。其中 ω(G)表示圖G的連通分支數(shù)。

準(zhǔn)則2 對于圖G1和G2而言,如果h(G1)

準(zhǔn)則3 具有p個頂點(diǎn)、q條邊的連通圖可具有的最小的核度為(也就是抗毀性最好的圖)

4 實例分析

圖1為某網(wǎng)絡(luò)化信息系統(tǒng)拓?fù)浣Y(jié)構(gòu)(局部)。其中,圓圈“★”代表各信息實體,連線代表兩信息實體之間有直接的信息聯(lián)系。為方便后續(xù)討論,將各信息實體進(jìn)行依次編號。

圖1 某網(wǎng)絡(luò)化信息系統(tǒng)拓?fù)浣Y(jié)構(gòu)(局部)Fig.1 Topological structure of a networked information system(partial)

很明顯,這是一個由20個頂點(diǎn)、29條邊構(gòu)成的拓?fù)鋱D。由準(zhǔn)則3,此連通圖可具有的最小的核度為(也就是抗毀性最好的圖)

我們可以計算該網(wǎng)絡(luò)化信息系統(tǒng)拓?fù)浣Y(jié)構(gòu)圖的核度,由定義3、定義4很容易計算出來:

從計算結(jié)果可以看出,該網(wǎng)絡(luò)化信息系統(tǒng)的拓?fù)浣Y(jié)構(gòu)并不是核度意義下抗毀性最好的拓?fù)浣Y(jié)構(gòu)。節(jié)點(diǎn)13對于該系統(tǒng)抗毀性而言是主要的矛盾,是這個網(wǎng)絡(luò)化信息系統(tǒng)的“核”。一旦該“核”處于癱瘓,信息系統(tǒng)的完整性就遭到破壞,最直觀的表現(xiàn)就是節(jié)點(diǎn)17成為懸浮點(diǎn),失去與整個系統(tǒng)其他實體之間的聯(lián)系。

5 結(jié)束語

本文從網(wǎng)絡(luò)化信息系統(tǒng)拓?fù)浣Y(jié)構(gòu)的完整性出發(fā),引入系統(tǒng)的核與核度理論,對網(wǎng)絡(luò)化信息系統(tǒng)拓?fù)浣Y(jié)構(gòu)的抗毀性進(jìn)行分析。研究結(jié)果表明,網(wǎng)絡(luò)化信息系統(tǒng)的拓?fù)浣Y(jié)構(gòu)并不是核度意義下抗毀性最好的拓?fù)浣Y(jié)構(gòu)。這個結(jié)論符合網(wǎng)絡(luò)化信息系統(tǒng)拓?fù)浣Y(jié)構(gòu)特征與抗毀性的關(guān)系,同時要求必須充分重視網(wǎng)絡(luò)化信息系統(tǒng)核與核度的評估工作。通過盡早發(fā)現(xiàn)系統(tǒng)的核與核度,能夠采取措施重點(diǎn)保護(hù)這些系統(tǒng)的“核”來提高整個網(wǎng)絡(luò)化信息系統(tǒng)的抗毀性。

本文工作對網(wǎng)絡(luò)化信息系統(tǒng)拓?fù)浣Y(jié)構(gòu)設(shè)計和功能優(yōu)化有一定的參考價值和指導(dǎo)意義。本文下一步研究的重點(diǎn)是如何在核與核度理論下,通過優(yōu)化現(xiàn)有網(wǎng)絡(luò)拓?fù)?提高網(wǎng)絡(luò)化信息系統(tǒng)的抗毀能力。

[1]Albert R,Jeong H,Barabasi A L.Error andAttack Tolerance of Complex Networks[J].Nature,2000,406(6):378-382.

[2]吳俊,譚躍進(jìn).復(fù)雜網(wǎng)絡(luò)抗毀性測度研究[J].系統(tǒng)工程學(xué)報,2005,20(2):128-131.WU Jun,TAN Yue-jin.Study on measure of complex network invulnerability[J].Journal of Systems Engineering,2005,20(2):128-131.(in Chinese)

[3]路蘭,楊洪勇.互聯(lián)網(wǎng)絡(luò)模型及其抗毀性分析[J].東南大學(xué)學(xué)報(自然科學(xué)版),2009,39(Sup.1):168-171.LU Lan,YANG Hong-yong.Internet model and survivability analysis[J].Journal of Southeast University(Natural Science Edition),2009,39(Sup.1):168-171.(in Chinese)

[4]曾憲釗.網(wǎng)絡(luò)科學(xué)[M].北京:軍事科學(xué)出版社,2007.ZENG Xian-zhao.Network Science[M].Beijing:Press of Military Science,2007.(in Chinese)

[5]王欣,姚佩陽,周翔翔,等.網(wǎng)絡(luò)中心戰(zhàn)指揮信息系統(tǒng)抗毀性研究[J].計算機(jī)工程,2011,37(5):97-99,102.WANG Xin,YAO Pei-yang,ZHOU Xiang-xiang,et al.Research onCommand InformationSystem Invulnerability inNetwork-Centric Warfare[J].Computer Engineering,2011,37(5):97-99,102.(in Chinese)

[6]狄鵬,胡濤,胡斌,等.基于復(fù)雜網(wǎng)絡(luò)的作戰(zhàn)網(wǎng)絡(luò)模型抗毀性研究[J].系統(tǒng)仿真學(xué)報,2011,23(1):56-60.DI Peng,HU Tao,HU Bin,et al.Research on Invulnerability of Combat Net Model Based on Complex Networks[J].Journal of SystemSimulation,2011,23(1):56-60.(in Chinese)

[7]許進(jìn).系統(tǒng)的核與核度理論(VII)—子核與核度的計算[J].系統(tǒng)工程學(xué)報,1999,14(3):243-246,257.XU Jin.The Core andCoritivity of a System(Ⅶ)-Sub core and an Algorithm of Coritivity[J].Journal of Systems Engineering,1999,14(3):243-246,257.(in Chinese)

[8]張勝貴,王自果.系統(tǒng)的核度與邊連通度[J].系統(tǒng)工程與電子技術(shù),1995(6):42-49.ZHANG Sheng-gui,WANG Zi-guo.On the System Coritivity and Edge Connectivity[J].Systems Engineering and Electronics,1995(6):42-49.(in Chinese)