馬迎輝, 彭 成, 張文佳, 滿君豐
(湖南工業(yè)大學(xué) 計(jì)算機(jī)與通信學(xué)院,湖南 株洲 412000)
網(wǎng)絡(luò)化軟件中的異常行為傳播研究*
馬迎輝, 彭 成, 張文佳, 滿君豐
(湖南工業(yè)大學(xué) 計(jì)算機(jī)與通信學(xué)院,湖南 株洲 412000)
隨著網(wǎng)絡(luò)化軟件應(yīng)用領(lǐng)域的逐步擴(kuò)大,軟件業(yè)對(duì)軟件的安全性、可靠性提出了更高的要求。軟件一旦出現(xiàn)故障,會(huì)給人們的生活、工作帶來(lái)不便,甚至造成嚴(yán)重的危害。因此,研究故障在網(wǎng)絡(luò)化軟件中引起的異常行為迫在眉睫。依據(jù)復(fù)雜網(wǎng)絡(luò)上的SIR模型,對(duì)網(wǎng)絡(luò)化軟件中異常行為的傳播過(guò)程進(jìn)行了理論分析和數(shù)值模擬,表明了復(fù)雜網(wǎng)絡(luò)特性對(duì)異常行為傳播的重要影響。
網(wǎng)絡(luò)化軟件;復(fù)雜網(wǎng)絡(luò);軟件故障;異常行為
軟件復(fù)雜性的增加直接導(dǎo)致軟件故障的增加。軟件發(fā)生故障或者異常是由于一些內(nèi)外部的因素,致使軟件中類(lèi)、方法、函數(shù)等出現(xiàn)錯(cuò)誤,不能夠完成軟件應(yīng)有的功能。如果一個(gè)或者多個(gè)個(gè)體發(fā)生故障,那么這個(gè)故障就會(huì)隨著調(diào)用和依附關(guān)系傳播到其他的個(gè)體甚至導(dǎo)致整個(gè)系統(tǒng)無(wú)法正常運(yùn)行,最終導(dǎo)致整個(gè)系統(tǒng)的崩潰。這種使系統(tǒng)失效的行為被稱為異常行為。目前,各種因素都在引領(lǐng)著軟件技術(shù)的重大改革,軟件的形態(tài)也明顯呈現(xiàn)出網(wǎng)絡(luò)化趨勢(shì),隨著復(fù)雜網(wǎng)絡(luò)技術(shù)、服務(wù)技術(shù)的迅速發(fā)展,網(wǎng)絡(luò)化軟件[1]已然成為了現(xiàn)代軟件系統(tǒng)的主要形態(tài)??偟膩?lái)說(shuō),網(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ù)訪問(wèn)、存取規(guī)模和硬件設(shè)備也大大超過(guò)了傳統(tǒng)的軟件。規(guī)模和數(shù)量在各維度上大規(guī)模增加,這不僅使得對(duì)軟件系統(tǒng)的理解和改造難度增加,而且也使得軟件故障對(duì)系統(tǒng)的破壞能力更加嚴(yán)重[3],因此,研究網(wǎng)絡(luò)化軟件系統(tǒng)中異常行為的傳播迫在眉睫,以期在軟件系統(tǒng)崩潰前能夠得到有效的控制,從而維持系統(tǒng)安全有效地運(yùn)行。
目前,研究網(wǎng)絡(luò)動(dòng)力學(xué)主要是依據(jù)病毒傳播的行為,近來(lái)也取得了很大的發(fā)展。另外,研究病毒傳播最廣泛的模型是SIS模型[4-5]與SIR模型[6],而無(wú)標(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)注的是感染幾率閾值的問(wèn)題。
鑒于此,本文依據(jù)復(fù)雜網(wǎng)絡(luò)中對(duì)病毒傳播行為的研究,利用SIR模型,對(duì)網(wǎng)絡(luò)化軟件系統(tǒng)中的異常行為傳播過(guò)程進(jìn)行理論分析和數(shù)值模擬,并對(duì)影響病毒傳播的因素的感染幾率、度分布、集聚系數(shù)等參數(shù)進(jìn)行分析比較,得出這些參數(shù)對(duì)網(wǎng)絡(luò)化軟件系統(tǒng)中異常行為傳播的影響具有相同的效果。研究異常行為的傳播可以為異常行為的控制提供有意義的指導(dǎo)。對(duì)異常行為的研究是十分有價(jià)值的。
軟件異常作為影響軟件正常運(yùn)行的重要因素,它的一些相關(guān)研究引起了研究人員的廣泛關(guān)注。由于人為的原因,故障在很多人工復(fù)雜系統(tǒng)中都有出現(xiàn)。很多領(lǐng)域都有對(duì)故障的研究,例如通信網(wǎng)絡(luò)故障、電路故障、電力系統(tǒng)故障等,提出了許多研究成果和技術(shù)。
現(xiàn)階段一些相關(guān)人員主要基于軟件的靜態(tài)拓?fù)鋱D,從各個(gè)層次對(duì)軟件故障進(jìn)行研究。王建等[12]利用軟件中函數(shù)間的交互關(guān)系,通過(guò)模型的建立去模擬軟件的故障傳播,進(jìn)而研究軟件中存在的級(jí)聯(lián)故障。最后,通過(guò)對(duì)現(xiàn)實(shí)中軟件進(jìn)行模擬實(shí)驗(yàn),分析了影響級(jí)聯(lián)故障傳播的因素,并研討了形成這些影響的原因。周寬久等[13]人通過(guò)對(duì)軟件執(zhí)行路徑的提取,建立軟件的加權(quán)網(wǎng)絡(luò),利用耦合映像格子(Coupled MapLattice,CML)模型[14],研究大型軟件系統(tǒng)故障的傳播過(guò)程,并且在此基礎(chǔ)上提出了一種依據(jù)關(guān)鍵路徑進(jìn)行軟件測(cè)試的方法。Damien Challet,Andrea Lombardoni等[15]人在Linux系統(tǒng)環(huán)境下,基于各個(gè)軟件包間的相互依存關(guān)系,對(duì)單一故障進(jìn)行討論分析。Mohamed A與Zulkernine M等人也是在組件級(jí)別對(duì)軟件故障傳播及其對(duì)軟件可靠性的影響進(jìn)行了討論分析,同時(shí)也提出了一種基于架構(gòu)服務(wù)路徑(Architectural Service Routes,ASR)的軟件故障傳播技術(shù),并且分析確認(rèn)了故障在構(gòu)建中傳播的下限與上限,最后得出架構(gòu)與系統(tǒng)可靠性間的聯(lián)系。
可以把網(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,意思就是說(shuō)感染個(gè)體只能維持一個(gè)時(shí)間步長(zhǎng)。
這里用I(t)表示網(wǎng)絡(luò)里被感染個(gè)體的總數(shù)。一段時(shí)間后,感染節(jié)點(diǎn)(I)離感染源越來(lái)越遠(yuǎn),被感染的節(jié)點(diǎn)數(shù)目逐漸增多。在有限的時(shí)間里,I(t)逐漸減少,當(dāng)I(t)最終等于零時(shí),則異常傳播過(guò)程結(jié)束。由此可知,φ越大,傳播的時(shí)間越長(zhǎng),被感染個(gè)體也越多;當(dāng)φ=1時(shí),網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都會(huì)被感染。
依據(jù)擴(kuò)散定義,可以得出異常傳播的公式:
(1)
其中,Li(t)表示每個(gè)感染節(jié)點(diǎn)到感染源的最短距離。
正如前面所說(shuō),網(wǎng)絡(luò)中的三角結(jié)構(gòu)與環(huán)形結(jié)構(gòu)會(huì)對(duì)異常行為傳播造成影響。下面用圖1所示同心圓來(lái)證明。
圖1 傳播過(guò)程示意圖
圖1中,圓心表示異常源點(diǎn),最內(nèi)層上的節(jié)點(diǎn)與圓心的間距Li(t)=1,第二層上的節(jié)點(diǎn)與圓心的距離Li(t)=2,依次類(lèi)推。當(dāng)不同層之間有連接時(shí),某層上的異常個(gè)體就可能傳播到同層或者是比其更低的一層,第二層上的異常點(diǎn)就有可能傳播到同層、第一層或者第三層上的個(gè)體,不過(guò)前兩種情況會(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ù)對(duì)異常傳播指數(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)〉可表示為:
(2)
另外式(2)也可改寫(xiě)為:
=t2-mt+n
(3)
假定式(3)可寫(xiě)為:
〈L2(t)〉~tX
(4)
在異常傳播過(guò)程中,δi(t)是由節(jié)點(diǎn)感染概率φ、集聚系數(shù)C與度分布P(k)共同決定的。這里只討論網(wǎng)絡(luò)結(jié)構(gòu)對(duì)傳播指數(shù)的影響,因此假設(shè)φ為定值。集聚系數(shù)C的值越大,表明網(wǎng)絡(luò)中的三角結(jié)構(gòu)越多,異常傳播的幾率就很小。因此,η的值隨C增大而減小。而對(duì)于度分布P(k),假如網(wǎng)絡(luò)為BA無(wú)標(biāo)度網(wǎng)絡(luò),那么對(duì)于度大的節(jié)點(diǎn)而言,則很容易被感染,并會(huì)將此異常傳播給其他更多節(jié)點(diǎn)。假如網(wǎng)絡(luò)為小世界網(wǎng)絡(luò),那么異常的傳播是循序漸進(jìn)的,被感染的節(jié)點(diǎn)相對(duì)來(lái)說(shuō)比較少。如果把異常行為傳播的過(guò)程分為兩個(gè)部分,一個(gè)是直接向前傳播,另一個(gè)是三角形路線傳播。沿三角形傳播又可分為向前和向后兩種,并且概率相同。綜上所述,在網(wǎng)絡(luò)化軟件中異常行為傳播指數(shù)η是大于1的。
下面通過(guò)數(shù)值模擬來(lái)驗(yàn)證上述結(jié)論,本文中選用WS小世界網(wǎng)絡(luò)模型和HK模型。兩個(gè)模型中,都可以調(diào)節(jié)一定的參數(shù)來(lái)改變集聚系數(shù)C的大小。另外,對(duì)于固定不變的集聚系數(shù)C,WS模型與HK模型的度分布P(k)不同。所以,用這兩個(gè)模型來(lái)研究度分布P(k)和集聚系數(shù)C對(duì)傳播指數(shù)的影響。
對(duì)于WS小世界模型,其最初是一個(gè)具有N個(gè)節(jié)點(diǎn)的一維鏈,其中的各個(gè)節(jié)點(diǎn)與附近的X個(gè)節(jié)點(diǎn)相連,接著以概率ω?cái)嚅_(kā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)中可以看出,對(duì)于ω=0和1,兩條直線是重合的,η=2。而在圖2(b)中,兩條線開(kāi)始分離,只有ω=1這條線接近于
圖3中,實(shí)心圓、正方形、空心圓分別代表K=2、4、6。
圖2 小世界模型中〈L2(t)〉和t的關(guān)系圖
圖3 小世界網(wǎng)絡(luò)中
傳播是由δi(t)決定的,并且δi(t)是隨著時(shí)間而變化的。也就是說(shuō)δi(t)的分布情況決定著η值的大小。下面對(duì)δ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的分布趨勢(shì)是一樣的。
圖4 δ1(t)、-mt+b和t的關(guān)系圖
接下來(lái),具體可按照以下步驟來(lái)構(gòu)造HK模型:(1)起始狀態(tài),網(wǎng)絡(luò)中有a個(gè)不連接的個(gè)體;(2)在接下來(lái)的每一步里引入一個(gè)新的節(jié)點(diǎn),從這個(gè)節(jié)點(diǎn)開(kāi)始一共有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)上。此模型的度分布與無(wú)標(biāo)度模型一樣,當(dāng)Ut=0時(shí),這個(gè)模型就是無(wú)標(biāo)度模型。通過(guò)改變Ut,就可以得到不一樣的集聚系數(shù)。
圖5(a)顯示了集聚系數(shù)隨Ut的變化情況,同樣也在HK模型中做了異常行為傳播仿真,圖5(b)顯示了不同的Ut下,〈L2(t)〉隨t的變化情況。
另外,從圖5(b)可以看出,集聚系數(shù)的增大使η偏離了數(shù)值2,此結(jié)果和小世界模型相同。比較圖5(b)與圖4(b)可以看出,HK模型相對(duì)來(lái)說(shuō)偏離η=2的幅度更小,因此,也就驗(yàn)證了異常行為更容易在非均勻網(wǎng)絡(luò)中進(jìn)行傳播。同時(shí),不管是小世界網(wǎng)絡(luò)模型還是HK模型,η的值都是處于1和2之間的。
圖5 HK模型中
對(duì)網(wǎng)絡(luò)化軟件異常行為的傳播過(guò)程進(jìn)行研究,能夠提高網(wǎng)絡(luò)化軟件系統(tǒng)的穩(wěn)定性與可信性。本文利用SIR模型對(duì)網(wǎng)絡(luò)化軟件上的異常行為傳播過(guò)程進(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à)值的。
[1] 彭成,楊路明,滿君豐.網(wǎng)絡(luò)化軟件交互行為動(dòng)態(tài)建模[J].電子學(xué)報(bào),2013,41(2):314-320.
[2] 何克清,彭蓉,劉瑋,等.網(wǎng)絡(luò)式軟件[M].北京:科學(xué)出版社,2008.
[3] 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.
[4] PASTOR-SATORRAS R, VESPIGNANI A. Epidemic spreading in scale-free networks [J]. Phys. Rev. Lett,2011,86:3200-3203.
[5] 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.
[7] 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).
[9] 于靜雯,楊冰.基于MapReduce框架下的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法[J].微型機(jī)與應(yīng)用,2014,33(22):74-76.
[10] WATTS D J, STROGATZ S H. Collective dynamics of ‘small-word’ networks [J]. Nature, 1998(393):440-442.
[11] WATTS D J. The‘new’ science of networks [J]. Publ. Math. Inst. Hung. Acad. Sci., 1960(5):17-60.
[12]王健,劉衍珩,劉雪蓮,等.復(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.
[14] 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.
Research on network software abnormal behavior propagation
MaYinghui, Peng Cheng, Zhang Wenjia, Man Junfeng
(College of Computer and Communication, Hunan University of Technology ,Zhuzhou 412000,China)
With the gradual expansion of the application field of network software, the software industry has put forward higher requirements for the security and reliability of the software. Once the software failure, it will bring inconvenience to the people's life,work inconvenience,and even cause serious harm. Therefore, it is urgent to study the abnormal behavior caused by fault in the network software. According to the SIR model on complex networks, the spread of the abnormal behavior of networked software process has carried on the theoretical analysis and numerical simulation, showing that the feature of complex network to the spread of the abnormal behavior.
network software; complex networks; software failure; abnormal behavior
國(guó)家自然科學(xué)基金項(xiàng)目(61350011, 61379058);湖南省自然科學(xué)基金項(xiàng)目(14JJ2115);湖南省教育廳項(xiàng)目(14C0323);湖南工業(yè)大學(xué)自然科學(xué)基金項(xiàng)目(2014HZX16)
TP301.6
A
1674-7720(2016)05-0018-04
馬迎輝,彭成,張文佳,等. 網(wǎng)絡(luò)化軟件中的異常行為傳播研究[J].微型機(jī)與應(yīng)用,2016,35(5):18-21.
2015-11-09)
馬迎輝(1989-),男,碩士研究生,主要研究方向:網(wǎng)絡(luò)化軟件,軟件工程。
彭成(1982-),通信作者,男,博士,主要研究方向:網(wǎng)絡(luò)化軟件,可信軟件,軟件工程。E-mail:466962447@qq.com。