馬迎輝，彭成，張文佳，滿君豐

　　(湖南工業(yè)大學(xué) 計(jì)算機(jī)與通信學(xué)院,湖南 株洲 412000)

　　摘要：隨著網(wǎng)絡(luò)化軟件應(yīng)用領(lǐng)域的逐步擴(kuò)大，軟件業(yè)對軟件的安全性、可靠性提出了更高的要求。軟件一旦出現(xiàn)故障，會(huì)給人們的生活、工作帶來不便，甚至造成嚴(yán)重的危害。因此，研究故障在網(wǎng)絡(luò)化軟件中引起的異常行為迫在眉睫。依據(jù)復(fù)雜網(wǎng)絡(luò)上的SIR模型，對網(wǎng)絡(luò)化軟件中異常行為的傳播過程進(jìn)行了理論分析和數(shù)值模擬，表明了復(fù)雜網(wǎng)絡(luò)特性對異常行為傳播的重要影響。

　　關(guān)鍵詞：網(wǎng)絡(luò)化軟件；復(fù)雜網(wǎng)絡(luò)；軟件故障；異常行為

0引言

　　軟件復(fù)雜性的增加直接導(dǎo)致軟件故障的增加。軟件發(fā)生故障或者異常是由于一些內(nèi)外部的因素，致使軟件中類、方法、函數(shù)等出現(xiàn)錯(cuò)誤，不能夠完成軟件應(yīng)有的功能。如果一個(gè)或者多個(gè)個(gè)體發(fā)生故障，那么這個(gè)故障就會(huì)隨著調(diào)用和依附關(guān)系傳播到其他的個(gè)體甚至導(dǎo)致整個(gè)系統(tǒng)無法正常運(yùn)行，最終導(dǎo)致整個(gè)系統(tǒng)的崩潰。這種使系統(tǒng)失效的行為被稱為異常行為。目前，各種因素都在引領(lǐng)著軟件技術(shù)的重大改革，軟件的形態(tài)也明顯呈現(xiàn)出網(wǎng)絡(luò)化趨勢，隨著復(fù)雜網(wǎng)絡(luò)技術(shù)、服務(wù)技術(shù)的迅速發(fā)展，網(wǎng)絡(luò)化軟件［1］已然成為了現(xiàn)代軟件系統(tǒng)的主要形態(tài)?？偟膩碚f，網(wǎng)絡(luò)化軟件就是以因特網(wǎng)為載體、以互聯(lián)網(wǎng)上的各種資源信息為元素、以各個(gè)元素之間的相互協(xié)同和互操作為構(gòu)造手段、行為與拓?fù)浣Y(jié)構(gòu)能夠動(dòng)態(tài)演變的密集型混合軟件系統(tǒng)［2］。另外，網(wǎng)絡(luò)化軟件系統(tǒng)不但組成元素間的交互、代碼數(shù)量比較龐大，而且數(shù)據(jù)訪問、存取規(guī)模和硬件設(shè)備也大大超過了傳統(tǒng)的軟件。規(guī)模和數(shù)量在各維度上大規(guī)模增加，這不僅使得對軟件系統(tǒng)的理解和改造難度增加，而且也使得軟件故障對系統(tǒng)的破壞能力更加嚴(yán)重［3］，因此，研究網(wǎng)絡(luò)化軟件系統(tǒng)中異常行為的傳播迫在眉睫，以期在軟件系統(tǒng)崩潰前能夠得到有效的控制，從而維持系統(tǒng)安全有效地運(yùn)行。

　　目前，研究網(wǎng)絡(luò)動(dòng)力學(xué)主要是依據(jù)病毒傳播的行為，近來也取得了很大的發(fā)展。另外，研究病毒傳播最廣泛的模型是SIS模型［45］與SIR模型［6］，而無標(biāo)度網(wǎng)絡(luò)［78］則是使用最多的網(wǎng)絡(luò)模型。在復(fù)雜網(wǎng)絡(luò)［9］里，每個(gè)單位節(jié)點(diǎn)代表一個(gè)單獨(dú)的個(gè)體，任意選取其中的一個(gè)節(jié)點(diǎn)作為感染源，節(jié)點(diǎn)與節(jié)點(diǎn)之間的連線代表病毒的傳播路徑。在小世界網(wǎng)絡(luò)［1011］中廣泛使用的是SIS模型，并且，其和SIR模型主要關(guān)注的是感染幾率閾值的問題。

　　鑒于此，本文依據(jù)復(fù)雜網(wǎng)絡(luò)中對病毒傳播行為的研究，利用SIR模型，對網(wǎng)絡(luò)化軟件系統(tǒng)中的異常行為傳播過程進(jìn)行理論分析和數(shù)值模擬，并對影響病毒傳播的因素的感染幾率、度分布、集聚系數(shù)等參數(shù)進(jìn)行分析比較，得出這些參數(shù)對網(wǎng)絡(luò)化軟件系統(tǒng)中異常行為傳播的影響具有相同的效果。研究異常行為的傳播可以為異常行為的控制提供有意義的指導(dǎo)。對異常行為的研究是十分有價(jià)值的。

1相關(guān)工作

　　軟件異常作為影響軟件正常運(yùn)行的重要因素，它的一些相關(guān)研究引起了研究人員的廣泛關(guān)注。由于人為的原因，故障在很多人工復(fù)雜系統(tǒng)中都有出現(xiàn)。很多領(lǐng)域都有對故障的研究，例如通信網(wǎng)絡(luò)故障、電路故障、電力系統(tǒng)故障等，提出了許多研究成果和技術(shù)。

　　現(xiàn)階段一些相關(guān)人員主要基于軟件的靜態(tài)拓?fù)鋱D，從各個(gè)層次對軟件故障進(jìn)行研究。王建等［12］利用軟件中函數(shù)間的交互關(guān)系，通過模型的建立去模擬軟件的故障傳播，進(jìn)而研究軟件中存在的級(jí)聯(lián)故障。最后，通過對現(xiàn)實(shí)中軟件進(jìn)行模擬實(shí)驗(yàn)，分析了影響級(jí)聯(lián)故障傳播的因素，并研討了形成這些影響的原因。周寬久等［13］人通過對軟件執(zhí)行路徑的提取，建立軟件的加權(quán)網(wǎng)絡(luò)，利用耦合映像格子（Coupled MapLattice，CML）模型［14］，研究大型軟件系統(tǒng)故障的傳播過程，并且在此基礎(chǔ)上提出了一種依據(jù)關(guān)鍵路徑進(jìn)行軟件測試的方法。Damien Challet，Andrea Lombardoni等［15］人在Linux系統(tǒng)環(huán)境下，基于各個(gè)軟件包間的相互依存關(guān)系，對單一故障進(jìn)行討論分析。Mohamed A與Zulkernine M等人也是在組件級(jí)別對軟件故障傳播及其對軟件可靠性的影響進(jìn)行了討論分析，同時(shí)也提出了一種基于架構(gòu)服務(wù)路徑（Architectural Service Routes，ASR）的軟件故障傳播技術(shù)，并且分析確認(rèn)了故障在構(gòu)建中傳播的下限與上限，最后得出架構(gòu)與系統(tǒng)可靠性間的聯(lián)系。

2網(wǎng)絡(luò)化軟件異常傳播理論分析

　　可以把網(wǎng)絡(luò)化軟件系統(tǒng)作為一個(gè)復(fù)雜的網(wǎng)絡(luò)，假設(shè)這個(gè)復(fù)雜的網(wǎng)中有n個(gè)節(jié)點(diǎn)，首先選擇其中一個(gè)作為感染個(gè)體（I），若異常則沿著節(jié)點(diǎn)間的連線進(jìn)行傳播，假定感染個(gè)體（I）只能將異常傳播到其鄰居節(jié)點(diǎn)。設(shè)鄰居節(jié)點(diǎn)被傳播感染的概率為φ，感染個(gè)體（I）轉(zhuǎn)化為免疫個(gè)體（R）的概率為τ。假定τ=1，意思就是說感染個(gè)體只能維持一個(gè)時(shí)間步長。

　　這里用I（t）表示網(wǎng)絡(luò)里被感染個(gè)體的總數(shù)。一段時(shí)間后，感染節(jié)點(diǎn)（I）離感染源越來越遠(yuǎn)，被感染的節(jié)點(diǎn)數(shù)目逐漸增多。在有限的時(shí)間里，I（t）逐漸減少，當(dāng)I（t）最終等于零時(shí)，則異常傳播過程結(jié)束。由此可知，φ越大，傳播的時(shí)間越長，被感染個(gè)體也越多；當(dāng)φ=1時(shí)，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都會(huì)被感染。

　　依據(jù)擴(kuò)散定義，可以得出異常傳播的公式：

　　其中，Li(t)表示每個(gè)感染節(jié)點(diǎn)到感染源的最短距離。

　　正如前面所說，網(wǎng)絡(luò)中的三角結(jié)構(gòu)與環(huán)形結(jié)構(gòu)會(huì)對異常行為傳播造成影響。下面用圖1所示同心圓來證明。

　　圖1中，圓心表示異常源點(diǎn)，最內(nèi)層上的節(jié)點(diǎn)與圓心的間距Li(t)=1，第二層上的節(jié)點(diǎn)與圓心的距離Li(t)=2，依次類推。當(dāng)不同層之間有連接時(shí)，某層上的異常個(gè)體就可能傳播到同層或者是比其更低的一層，第二層上的異常點(diǎn)就有可能傳播到同層、第一層或者第三層上的個(gè)體，不過前兩種情況會(huì)使得〈L2(t)〉=tη中的η小于2。所以，網(wǎng)絡(luò)化軟件的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)就決定了異常傳播指數(shù)η的大小。

　　一般而言，描述網(wǎng)絡(luò)結(jié)構(gòu)比較重要的兩個(gè)參數(shù)是集聚系數(shù)C和度分布P（k）。前者表示某個(gè)節(jié)點(diǎn)的兩個(gè)鄰居節(jié)點(diǎn)仍為鄰居的可能性，后者表示網(wǎng)絡(luò)中度相同的所有節(jié)點(diǎn)的密度。集聚系數(shù)越大表明網(wǎng)絡(luò)中的三角結(jié)構(gòu)越多。下面就研究這兩個(gè)參數(shù)對異常傳播指數(shù)η的影響。

　　在某一時(shí)刻t，感染個(gè)體具有不同的Li(t)。假設(shè)Li(t)以δ1(t)的概率取t值，Li(t)以δ2(t)的概率取t－1，…，Li(t)以δt(t)的概率取1。那么〈L2(t)〉可表示為：

　　假定式（3）可寫為：

　　〈L2(t)〉～tX（4）

　　在異常傳播過程中，δi(t)是由節(jié)點(diǎn)感染概率φ、集聚系數(shù)C與度分布P(k)共同決定的。這里只討論網(wǎng)絡(luò)結(jié)構(gòu)對傳播指數(shù)的影響，因此假設(shè)φ為定值。集聚系數(shù)C的值越大，表明網(wǎng)絡(luò)中的三角結(jié)構(gòu)越多，異常傳播的幾率就很小。因此，η的值隨C增大而減小。而對于度分布P(k)，假如網(wǎng)絡(luò)為BA無標(biāo)度網(wǎng)絡(luò)，那么對于度大的節(jié)點(diǎn)而言，則很容易被感染，并會(huì)將此異常傳播給其他更多節(jié)點(diǎn)。假如網(wǎng)絡(luò)為小世界網(wǎng)絡(luò)，那么異常的傳播是循序漸進(jìn)的，被感染的節(jié)點(diǎn)相對來說比較少。如果把異常行為傳播的過程分為兩個(gè)部分，一個(gè)是直接向前傳播，另一個(gè)是三角形路線傳播。沿三角形傳播又可分為向前和向后兩種，并且概率相同。綜上所述，在網(wǎng)絡(luò)化軟件中異常行為傳播指數(shù)η是大于1的。

3實(shí)驗(yàn)分析

　　下面通過數(shù)值模擬來驗(yàn)證上述結(jié)論，本文中選用WS小世界網(wǎng)絡(luò)模型和HK模型。兩個(gè)模型中，都可以調(diào)節(jié)一定的參數(shù)來改變集聚系數(shù)C的大小。另外，對于固定不變的集聚系數(shù)C，WS模型與HK模型的度分布P(k)不同。所以，用這兩個(gè)模型來研究度分布P(k)和集聚系數(shù)C對傳播指數(shù)的影響。

　　對于WS小世界模型，其最初是一個(gè)具有N個(gè)節(jié)點(diǎn)的一維鏈，其中的各個(gè)節(jié)點(diǎn)與附近的X個(gè)節(jié)點(diǎn)相連，接著以概率ω?cái)嚅_并重新相連，但是新連接的節(jié)點(diǎn)從網(wǎng)絡(luò)中的其他節(jié)點(diǎn)中隨機(jī)選擇，避免自連接與重復(fù)連接。然后，在小世界網(wǎng)中隨機(jī)選取一個(gè)節(jié)點(diǎn)作為異常源點(diǎn)，讓此異常源點(diǎn)以φ的感染概率進(jìn)行傳播。最終，得出〈L2(t)〉與t的關(guān)系隨ω與X的變化而變化。

　　圖2中，圓圈和正方形分別表示ω=0，1。從圖2（a）中可以看出，對于ω=0和1，兩條直線是重合的，η=2。而在圖2（b）中，兩條線開始分離，只有ω=1這條線接近于<L2(t)>=t2。這主要是因?yàn)楫?dāng)ω=1時(shí)，網(wǎng)絡(luò)成為隨機(jī)網(wǎng)絡(luò)，其集聚系數(shù)比較小，從而使η接近2。當(dāng)1<ω<2時(shí)，網(wǎng)絡(luò)有了一定的集聚系數(shù)，η也就偏離了2。

　　圖3中，實(shí)心圓、正方形、空心圓分別代表K=2、4、6。

　　圖2小世界模型中〈L2(t)〉和t的關(guān)系圖

　　圖3小世界網(wǎng)絡(luò)中<L2(t)>和t的關(guān)系圖

　　傳播是由δi(t)決定的，并且δi(t)是隨著時(shí)間而變化的。也就是說δi(t)的分布情況決定著η值的大小。下面對δi(t)和t的關(guān)系進(jìn)行數(shù)據(jù)分析。圖4中上圖顯示了在不同ω值的情況下δ1(t)和t之間的聯(lián)系。圖中顯示，在最初的5個(gè)時(shí)間段里，隨著ω的增大，δ1(t)的減小速度變慢，意思是當(dāng)ω取最大值時(shí)，δ1(t)也最大。除了δ1(t)，同樣分析了δi(t)的分布情況，結(jié)果如圖4中下圖所示，可以看出δ1(t)與-mt+b的分布趨勢是一樣的。

　　接下來，具體可按照以下步驟來構(gòu)造HK模型：(1)起始狀態(tài)，網(wǎng)絡(luò)中有a個(gè)不連接的個(gè)體；(2)在接下來的每一步里引入一個(gè)新的節(jié)點(diǎn)，從這個(gè)節(jié)點(diǎn)開始一共有a條邊連接到初始的所有節(jié)點(diǎn)上。新引入的這個(gè)節(jié)點(diǎn)按照偏好依附機(jī)制連接到初始的某個(gè)節(jié)點(diǎn)上，假設(shè)這個(gè)節(jié)點(diǎn)為θ；新引入的這個(gè)節(jié)點(diǎn)的其他邊則以概率Ut隨機(jī)連接到θ的鄰居節(jié)點(diǎn)上，而以概率1－Ut按照依附偏好機(jī)制連接到起初的其他節(jié)點(diǎn)上。此模型的度分布與無標(biāo)度模型一樣，當(dāng)Ut=0時(shí)，這個(gè)模型就是無標(biāo)度模型。通過改變Ut，就可以得到不一樣的集聚系數(shù)。

　　圖5（a）顯示了集聚系數(shù)隨Ut的變化情況，同樣也在HK模型中做了異常行為傳播仿真，圖5（b）顯示了不同的Ut下，〈L2(t)〉隨t的變化情況。

　　另外，從圖5（b）可以看出，集聚系數(shù)的增大使η偏離了數(shù)值2，此結(jié)果和小世界模型相同。比較圖5（b）與圖4（b）可以看出，HK模型相對來說偏離η=2的幅度更小，因此，也就驗(yàn)證了異常行為更容易在非均勻網(wǎng)絡(luò)中進(jìn)行傳播。同時(shí)，不管是小世界網(wǎng)絡(luò)模型還是HK模型，η的值都是處于1和2之間的。

4結(jié)束語

　　對網(wǎng)絡(luò)化軟件異常行為的傳播過程進(jìn)行研究，能夠提高網(wǎng)絡(luò)化軟件系統(tǒng)的穩(wěn)定性與可信性。本文利用SIR模型對網(wǎng)絡(luò)化軟件上的異常行為傳播過程進(jìn)行了理論分析和實(shí)驗(yàn)?zāi)M。當(dāng)感染幾率一定時(shí)，聚集系數(shù)C和度分布P(k)都會(huì)影響異常行為的傳播。異常行為的傳播指數(shù)η隨集聚系數(shù)C的增加而變小，隨著非均勻度的增強(qiáng)而變大。研究異常行為在網(wǎng)絡(luò)化軟件中的傳播可以為以后的異常行為控制提供有意義的指導(dǎo)。它作為網(wǎng)絡(luò)化軟件中異常行為研究的一部分，是十分有價(jià)值的。

　　參考文獻(xiàn)

　　［1］ 彭成，楊路明，滿君豐．網(wǎng)絡(luò)化軟件交互行為動(dòng)態(tài)建模［J］.電子學(xué)報(bào)，2013,41（2）：314320.

　　［2］ 何克清，彭蓉，劉瑋，等.網(wǎng)絡(luò)式軟件［M］.北京：科學(xué)出版社，2008.

　?。?］ HE K Q, PENG R, LIU J, et al. Design methodology of networked software evolution growth based on software patterns ［J］. Journal of Systems Science and Complexity, 2006, 19(2):157181.

　?。?］ PASTORSATORRAS R, VESPIGNANI A. Epidemic spreading in scalefree networks ［J］. Phys. Rev. Lett,2011,86:32003203.

　?。?］ PASTORSATORRAS R, VESPIGNANI A. Epidemics and immunization in scalefree networks ［M］. Berlin: Wiley- VCH,2003.

　　［6］ HETHCOTE H W.The mathematics of infectious diseases ［J］. SIAM Review, 2000, 42（4）: 599653.

　?。?］ COHEN R， HAVLIN S. Scalefree networks are ultrasmall［J］. Phys. Rev. Lett. 2003, 90:058701(14).

　　［8］ FRONEZAK A, FRONEZAK P, HOLYST J A.Meanfield theory for clustering coefficients in BarabasiAlbert networks［J］.Phys.Rev.E,2003,68:046126(14).

　?。?］ 于靜雯,楊冰.基于MapReduce框架下的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法［J］.微型機(jī)與應(yīng)用,2014,33(22):7476.

　?。?0］ WATTS D J, STROGATZ S H. Collective dynamics of ‘smallword’ networks ［J］. Nature, 1998(393):440442.

　?。?1］ WATTS D J. The‘new’ science of networks ［J］. Publ. Math. Inst. Hung. Acad. Sci., 1960(5):1760.

　?。?2］王健，劉衍珩，劉雪蓮,等.復(fù)雜軟件的級(jí)聯(lián)故障建模［J］.計(jì)算機(jī)學(xué)報(bào)，2011,34（6）：11371147.

　　［13］ 周寬久，蘭文輝，馮金金,等.基于耦合影響格子的軟件相繼故障研究［J］.計(jì)算機(jī)科學(xué)，2011,38(5):129131,174.

　?。?4］ KANEKO K. Perioddoubling of kinkantikink patterns, quasiperiodicity in antiferrolike structures and spatial intermittency in coupled map lattices ［J］. Prog. Theor. Phys, 1984, 72(3): 480486.

　　［15］ CHALLET D, LOMBARDONI A. Bug propagation and debugging in asymmetric software structures ［J］. Phys. Rev.E 2004,70(4):10151030.