李克文，雷永秀，張震濤

(中國(guó)石油大學(xué)(華東) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 青島 266580)

0 引 言

隨著科學(xué)技術(shù)的發(fā)展，構(gòu)件式軟件系統(tǒng)開(kāi)發(fā)成為一種主流的軟件開(kāi)發(fā)方式[1]。構(gòu)件位于軟件系統(tǒng)的不同位置，并且每個(gè)構(gòu)件在系統(tǒng)中的作用也不盡相同，如果構(gòu)件失效對(duì)整個(gè)軟件系統(tǒng)的影響是不同的，因此需要根據(jù)軟件的網(wǎng)絡(luò)結(jié)構(gòu)計(jì)算每個(gè)構(gòu)件的影響因子。國(guó)內(nèi)外研究者提出結(jié)合復(fù)雜網(wǎng)絡(luò)理論對(duì)軟件工程領(lǐng)域的相關(guān)問(wèn)題進(jìn)行研究，目前，使用復(fù)雜網(wǎng)絡(luò)理論對(duì)軟件工程領(lǐng)域的研究多數(shù)使用其節(jié)點(diǎn)的要性評(píng)估方法，得到構(gòu)件的影響因子。

Bhattacharya等[2]使用復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的度衡量節(jié)點(diǎn)的重要性，即與該節(jié)點(diǎn)連接的邊數(shù)目越多，該節(jié)點(diǎn)越重要。Subelj等[3]認(rèn)為節(jié)點(diǎn)介數(shù)可以度量復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性，即經(jīng)過(guò)該節(jié)點(diǎn)最短路徑的數(shù)量越多表示該節(jié)點(diǎn)越重要。Maksim Kitsak等[4]利用K-shell分解方法劃分復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)的重要性，通過(guò)遞歸的刪除值小于或等于k的節(jié)點(diǎn)及連邊(k為整數(shù))，重要性大的節(jié)點(diǎn)后刪除。這些方法從不同的角度評(píng)估了復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)的重要性，但是這些方法主要針對(duì)無(wú)向無(wú)權(quán)網(wǎng)絡(luò)，而構(gòu)件式軟件系統(tǒng)被認(rèn)為是有向加權(quán)的網(wǎng)絡(luò)結(jié)構(gòu)。

本文針對(duì)以上問(wèn)題，提出了一種基于構(gòu)件影響因子的軟件可靠性評(píng)估方法，使用改進(jìn)的PageRank算法評(píng)估有向加權(quán)軟件網(wǎng)絡(luò)中構(gòu)件的影響因子，然后提出基于構(gòu)件影響因子的軟件可靠性評(píng)估方法。

1 研究基礎(chǔ)

1.1 基于PageRank算法的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估

PageRank算法是谷歌的創(chuàng)始人提出的，使用PageRank值評(píng)估節(jié)點(diǎn)的重要性。其基本思想為：一個(gè)節(jié)點(diǎn)的重要性與指向它的鄰居節(jié)點(diǎn)的重要性相關(guān)。對(duì)于有向網(wǎng)絡(luò)G=(V,E)，V={v1,v2,…vn} 表示節(jié)點(diǎn)的集合，E={e1,e2…em}?V×V表示節(jié)點(diǎn)之間是否有邊相連，PageRank算法的數(shù)學(xué)公式表示為

(1)

式中:PR(vi) 表示復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)vi的PageRank值，其值越大代表節(jié)點(diǎn)vi在整個(gè)復(fù)雜網(wǎng)絡(luò)中越重要；PR(vj) 為連接到節(jié)點(diǎn)vi的節(jié)點(diǎn)vj的PageRank值；O(vj) 為節(jié)點(diǎn)vj的出度。由PageRank算法的公式可知，指向節(jié)點(diǎn)vi的節(jié)點(diǎn)數(shù)量越多，節(jié)點(diǎn)vi的PageRank值越大，即其重要性越高；并且指向節(jié)點(diǎn)vi的節(jié)點(diǎn)的重要性越高，節(jié)點(diǎn)vi的PageRank值也越大。

1.2 構(gòu)件式軟件可靠性理論

隨著數(shù)十年軟件技術(shù)的發(fā)展，目前的軟件可靠性評(píng)估模型已有上百種，總的來(lái)說(shuō)可以分為黑盒、白盒方法?；诤诤械能浖煽啃栽u(píng)估方法，使用軟件開(kāi)發(fā)后期收集到的軟件系統(tǒng)歷史失效數(shù)據(jù)，使用統(tǒng)計(jì)學(xué)的方法進(jìn)行建模，對(duì)軟件系統(tǒng)的可靠性進(jìn)行評(píng)估，這種方法在評(píng)估過(guò)程中只分析運(yùn)行環(huán)境與系統(tǒng)的交互[5]，將軟件系統(tǒng)作為一個(gè)整體，不考慮軟件的內(nèi)部結(jié)構(gòu)，該模型評(píng)估的效率低、結(jié)果的準(zhǔn)確性差。近年來(lái)，面向?qū)ο蟮臉?gòu)件式軟件不斷發(fā)展，這種基于黑盒的軟件評(píng)估模型逐漸淘汰，基于構(gòu)件的軟件可靠性評(píng)估模型受到更多的關(guān)注[1,6]。與傳統(tǒng)的基于黑盒的軟件可靠性評(píng)估模型相比，這種基于白盒的評(píng)估模型，能夠?qū)④浖膬?nèi)部結(jié)構(gòu)信息與構(gòu)件的可靠性考慮在內(nèi)，還能夠在軟件設(shè)計(jì)的早期評(píng)估其可靠性，因此，基于白盒的方法可以更加準(zhǔn)確、合理的對(duì)軟件系統(tǒng)可靠性進(jìn)行評(píng)估。

目前基于白盒的可靠性評(píng)估模型，一般是依據(jù)Cheung[5]提出的軟件可靠性評(píng)估思想。Cheung的模型把軟件系統(tǒng)構(gòu)建為基于離散時(shí)間的馬爾科夫模型，使用網(wǎng)絡(luò)結(jié)構(gòu)表示軟件系統(tǒng)結(jié)構(gòu)，rvi代表構(gòu)件vi的可靠性，p(vi,vj) 代表構(gòu)件vi轉(zhuǎn)移到構(gòu)件vj的概率，若這兩個(gè)構(gòu)件之間不存在轉(zhuǎn)移關(guān)系，則p(vi,vj)=0， 可得到控制轉(zhuǎn)移矩陣為

(2)

R=S(1,n)rvn

(3)

當(dāng)Q為有限矩陣時(shí)S=(I-Q)-1， 則軟件系統(tǒng)可靠性可表示為

R=S(1,n)rvn=((I-Q)-1)(1,n)rvn

(4)

2 基于構(gòu)件影響因子的軟件可靠性評(píng)估方法

2.1 基于PageRank算法的構(gòu)件影響因子計(jì)算方法

隨著互聯(lián)網(wǎng)技術(shù)的進(jìn)步，也逐漸提升了軟件系統(tǒng)功能和結(jié)構(gòu)的復(fù)雜度，復(fù)雜性變成構(gòu)件式軟件系統(tǒng)的基本屬性之一[7]，通常把大型軟件系統(tǒng)當(dāng)作一個(gè)復(fù)雜系統(tǒng)。國(guó)內(nèi)外研究者使用復(fù)雜網(wǎng)絡(luò)的理論與統(tǒng)計(jì)學(xué)的方法分析構(gòu)件式軟件系統(tǒng)的結(jié)構(gòu)特性，研究結(jié)果表明，構(gòu)件式軟件系統(tǒng)結(jié)構(gòu)具有復(fù)雜網(wǎng)絡(luò)的特性，可以將軟件系統(tǒng)的結(jié)構(gòu)抽象為一個(gè)復(fù)雜網(wǎng)絡(luò)模型。如何結(jié)合復(fù)雜網(wǎng)絡(luò)理論對(duì)軟件系統(tǒng)性能及結(jié)構(gòu)進(jìn)行分析，國(guó)內(nèi)外研究者已積累了大量的研究成果[8-10]。

在構(gòu)件式軟件系統(tǒng)中，利用已有的構(gòu)件組裝開(kāi)發(fā)軟件系統(tǒng)，可以將構(gòu)件視為網(wǎng)絡(luò)中的節(jié)點(diǎn)，構(gòu)件之間的連接為有向邊，軟件系統(tǒng)就成為復(fù)雜的關(guān)系網(wǎng)[11]。基于PageRank算法的思想，若構(gòu)件vi調(diào)用了構(gòu)件vk， 則構(gòu)件vk的重要性分配給了構(gòu)件vi， 構(gòu)件vk的被調(diào)用次數(shù)也決定了構(gòu)件vi的重要性[12]。但是構(gòu)件式軟件系統(tǒng)中有輸入/輸出構(gòu)件，而復(fù)雜網(wǎng)絡(luò)中沒(méi)有輸入/輸出節(jié)點(diǎn)的概念，并且PageRank算法用于有向復(fù)雜網(wǎng)絡(luò)，而軟件系統(tǒng)網(wǎng)絡(luò)是有向加權(quán)的復(fù)雜網(wǎng)絡(luò)，所以需要加入邊的權(quán)重對(duì)節(jié)點(diǎn)的影響，使用改進(jìn)的PageRank算法評(píng)估構(gòu)件的影響因子。為了提高構(gòu)件重要性計(jì)算的準(zhǔn)確性，首先將構(gòu)件分為輸入/輸出構(gòu)件節(jié)點(diǎn)及普通構(gòu)件，分別計(jì)算構(gòu)件的重要性，在計(jì)算普通構(gòu)件重要性時(shí)采用改進(jìn)的PageRank算法，然后與構(gòu)件式軟件系統(tǒng)的可靠性評(píng)估模型結(jié)合，對(duì)整個(gè)軟件系統(tǒng)的可靠性進(jìn)行評(píng)估，并用于指導(dǎo)、優(yōu)化軟件系統(tǒng)的可靠性。

評(píng)估輸入/輸出構(gòu)件的影響因子公式為

(5)

其中，E(vi) 為完整運(yùn)行軟件系統(tǒng)時(shí)構(gòu)件vi的執(zhí)行次數(shù)的數(shù)學(xué)期望，該值可以通過(guò)分析操作剖面得到；m為軟件系統(tǒng)中輸入構(gòu)件或者輸出構(gòu)件的數(shù)量。特別說(shuō)明，當(dāng)輸入/輸出構(gòu)件執(zhí)行次數(shù)的數(shù)學(xué)期望等于輸入/輸出構(gòu)件總的執(zhí)行次數(shù)時(shí)，輸入/輸出構(gòu)件的影響因子為1，如：該軟件系統(tǒng)只有一個(gè)輸入/輸出構(gòu)件；運(yùn)行整個(gè)軟件系統(tǒng)時(shí)只有一個(gè)輸入/輸出構(gòu)件被執(zhí)行。由公式可知，輸入/輸出構(gòu)件的重要性與其執(zhí)行次數(shù)的數(shù)學(xué)期望成正相關(guān)，即輸入/輸出構(gòu)件在軟件系統(tǒng)中執(zhí)行的次數(shù)越多，說(shuō)明構(gòu)件的影響因子越大，對(duì)軟件系統(tǒng)的影響越高。

基于PageRank算法對(duì)軟件系統(tǒng)網(wǎng)絡(luò)中普通構(gòu)件的影響因子進(jìn)行評(píng)估，以一個(gè)有向圖來(lái)表示軟件系統(tǒng)的結(jié)構(gòu)，其中每個(gè)節(jié)點(diǎn)vi(i=1,2…n) 表示一個(gè)構(gòu)件，有向邊 (vk,vi) 表示構(gòu)件vk到vi的可能轉(zhuǎn)移，p(vk,vi) 表示構(gòu)件vk到構(gòu)件vi的轉(zhuǎn)移概率。評(píng)估普通構(gòu)件vi影響因子的計(jì)算公式為

(6)

公式中使用構(gòu)件vk到構(gòu)件vi的控制轉(zhuǎn)移概率p(vk,vi)， 相當(dāng)于引入了加權(quán)網(wǎng)絡(luò)中邊的權(quán)重，改進(jìn)了傳統(tǒng)PageRank算法中重要性平均分配的不合理性。通過(guò)對(duì)不同構(gòu)件的轉(zhuǎn)移賦予不同的權(quán)重，提高重要構(gòu)件的影響因子SPR值，降低不重要構(gòu)件的影響因子SPR值。

使用矩陣方法計(jì)算各類構(gòu)件的影響因子，將上述式(5)及式(6)合并為一個(gè)公式。若構(gòu)件v1為輸入構(gòu)件，則任意構(gòu)件不會(huì)轉(zhuǎn)移到構(gòu)件v1， 即p(vi,v1)=0， 此時(shí)使用PageRank算法得到構(gòu)件v1的影響因子為0；若構(gòu)件vn為輸出構(gòu)件則構(gòu)件vn不會(huì)轉(zhuǎn)移到任意構(gòu)件，即p(vn,vi)=0， 而此時(shí)所有構(gòu)件的重要性都會(huì)轉(zhuǎn)移到輸出構(gòu)件vn， 其它任意構(gòu)件的影響因子都為0。所以，使用矩陣型的PageRank算法時(shí)，需要引入一個(gè)參數(shù)q， 使輸出構(gòu)件的重要性能夠轉(zhuǎn)移到輸入構(gòu)件，避免出現(xiàn)影響因子為0的情況。矩陣方法計(jì)算各類構(gòu)件影響因子的公式為

Ai+1=M*Ai

(7)

2.2 基于構(gòu)件影響因子的構(gòu)件式軟件可靠性評(píng)估

Cheung的模型[5]在計(jì)算軟件系統(tǒng)的可靠性時(shí)沒(méi)有考慮構(gòu)件的重要性，軟件系統(tǒng)中處于不同的位置的不同構(gòu)件，不同構(gòu)件在失效時(shí)對(duì)軟件系統(tǒng)的影響也有差別，所以需要引入構(gòu)件影響因子來(lái)評(píng)估軟件系統(tǒng)的可靠性。

基于Cheung提出的軟件可靠性評(píng)估方法，本文將通過(guò)PageRank算法得到的構(gòu)件影響因子引入到軟件可靠性評(píng)估模型中，提出了基于構(gòu)件影響因子的軟件系統(tǒng)可靠性評(píng)估方法。引入影響因子后的控制轉(zhuǎn)移矩陣為

(8)

軟件系統(tǒng)的可靠性表示為

(9)

基于構(gòu)件影響因子的軟件可靠性評(píng)估方法執(zhí)行步驟如圖1所示。

圖1 基于構(gòu)件影響因子的軟件可靠性評(píng)估流程

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

3.1 實(shí)驗(yàn)對(duì)象

為了驗(yàn)證本文提出的軟件可靠性評(píng)估方法的性能，以文獻(xiàn)[13]中的某仿真軟件系統(tǒng)為實(shí)驗(yàn)對(duì)象，該仿真系統(tǒng)在軟件可靠性評(píng)估領(lǐng)域被廣泛引用。圖2為仿真軟件系統(tǒng)的體系結(jié)構(gòu)圖，其中構(gòu)件v1為輸入構(gòu)件，v10為輸出構(gòu)件，構(gòu)件間的轉(zhuǎn)移概率p(vi,vj) 見(jiàn)表1，根據(jù)文獻(xiàn)[14]構(gòu)件vi的可靠性rvi見(jiàn)表2。

圖2 仿真系統(tǒng)體系結(jié)構(gòu)

3.2 基于PageRank算法構(gòu)件影響因子有效性分析

由于該仿真系統(tǒng)軟件結(jié)構(gòu)中只有一個(gè)輸入/輸出構(gòu)件，則輸入構(gòu)件v1的影響因子α1與輸出構(gòu)件v10的影響因子α10都為1，即α1=p(v10,v1)α10且α1=α10， 為了保證輸出構(gòu)件與輸入構(gòu)件的影響因子相等，所以矩陣M中的參數(shù)q=p(v10,v1)=1， 則矩陣M為

取A0=(0.1,0.1,…,0.1)T，δ=0.00001， 按照式(7)進(jìn)行迭代，迭代48次后滿足終止條件 |Ai+1-Ai|<0.00001， 得到各構(gòu)件vi(1,2,…10) 的影響因子A， 為了使輸入/輸出構(gòu)件的影響因子為1，對(duì)影響因子A進(jìn)行歸一化得到A′。 各構(gòu)件的影響因子計(jì)算結(jié)果見(jiàn)表3。

表1 構(gòu)件間轉(zhuǎn)移概率

表2 構(gòu)件可靠性

由表3可得構(gòu)件v5、v1、v10的影響因子最高，其中構(gòu)件v1為輸入構(gòu)件，v10為輸出構(gòu)件，其發(fā)生失效對(duì)整個(gè)軟件系統(tǒng)理應(yīng)有比較大的影響，即其影響因子應(yīng)該比較大。構(gòu)件v5的影響因子最大，它位于軟件系統(tǒng)的中心位置，它的失效影響到的構(gòu)件數(shù)量比較多，所以為整個(gè)系統(tǒng)的影響也比較大。為了驗(yàn)證影響因子評(píng)估的有效性，通過(guò)Cheung模型對(duì)提高構(gòu)件可靠性對(duì)軟件系統(tǒng)可靠性優(yōu)化效果進(jìn)行分析，由于構(gòu)件v5與構(gòu)件v8的可靠性相同，所以基于Cheung模型驗(yàn)證構(gòu)件v5、v8對(duì)軟件系統(tǒng)可靠性的優(yōu)化效果如圖3所示。

由圖3可得，提高構(gòu)件v5的可靠性比提高構(gòu)件v8的可靠性對(duì)整個(gè)軟件可靠性的影響更有效，由此可見(jiàn)，優(yōu)化影響因子大的構(gòu)件能夠更大效率地提高軟件系統(tǒng)的可靠性。因此，利用本文提出的構(gòu)件影響因子度量方法可以指導(dǎo)軟件系統(tǒng)可靠性的優(yōu)化。

表3 各構(gòu)件影響因子

3.3 構(gòu)件式軟件系統(tǒng)可靠性評(píng)估實(shí)驗(yàn)

使用式(9)對(duì)該仿真系統(tǒng)的可靠性進(jìn)行評(píng)估，首先根據(jù)表1～表3中構(gòu)件的可靠性、構(gòu)件間的轉(zhuǎn)移概率、構(gòu)件的影響因子及式(8)，可以得到控制轉(zhuǎn)移矩陣Q為

圖3 基于Cheung模型的軟件系統(tǒng)可靠性優(yōu)化效果

針對(duì)圖1中的軟件結(jié)構(gòu)，根據(jù)文獻(xiàn)[13]提出的實(shí)際軟件系統(tǒng)可靠性為0.8426，將本文的計(jì)算結(jié)果與幾種不同的軟件可靠性評(píng)估方法進(jìn)行比較，對(duì)比結(jié)果見(jiàn)表4。

表4 幾種可靠性評(píng)估方法對(duì)比

由表4可得，使用本文方法得到的該仿真系統(tǒng)的可靠性評(píng)估結(jié)果的誤差最小，僅為1.31%，因此，采用本文的構(gòu)件影響因子計(jì)算方法，評(píng)估軟件系統(tǒng)的可靠性能夠更加符合實(shí)際，并且能夠判斷出對(duì)整個(gè)軟件系統(tǒng)影響性大的構(gòu)件，便于指導(dǎo)優(yōu)化整個(gè)軟件系統(tǒng)。

4 結(jié)束語(yǔ)

隨著構(gòu)件式軟件開(kāi)發(fā)技術(shù)的發(fā)展，對(duì)構(gòu)件式軟件系統(tǒng)的可靠性評(píng)估也成為目前研究的重要方向之一，但是常用的Cheung模型在評(píng)估軟件系統(tǒng)的可靠性時(shí)，沒(méi)有考慮到構(gòu)件重要性對(duì)整個(gè)軟件系統(tǒng)的影響。因此，本文提出了一種基于構(gòu)件影響因子的軟件可靠性評(píng)估方法，使用引入了構(gòu)件轉(zhuǎn)移概率的加權(quán)PageRank算法評(píng)估構(gòu)件的影響因子，并將影響因子引入到軟件可靠性評(píng)估模型中，通過(guò)仿真系統(tǒng)驗(yàn)證該方法的有效性，并且所提出的方法在軟件開(kāi)發(fā)前期能夠指導(dǎo)軟件系統(tǒng)的優(yōu)化。本文提出的軟件可靠性評(píng)估方法沒(méi)有考慮不同結(jié)構(gòu)風(fēng)格對(duì)軟件系統(tǒng)可靠性的影響，今后將進(jìn)一步對(duì)基于構(gòu)件影響因子及結(jié)構(gòu)分析的軟件可靠性評(píng)估方法進(jìn)行研究。