李克文，雷永秀，張震濤

(中國石油大學(華東) 計算機科學與技術學院，山東 青島 266580)

0 引 言

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

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

本文針對以上問題，提出了一種基于構件影響因子的軟件可靠性評估方法，使用改進的PageRank算法評估有向加權軟件網絡中構件的影響因子，然后提出基于構件影響因子的軟件可靠性評估方法。

1 研究基礎

1.1 基于PageRank算法的復雜網絡節(jié)點重要性評估

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

(1)

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

1.2 構件式軟件可靠性理論

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

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

(2)

R=S(1,n)rvn

(3)

當Q為有限矩陣時S=(I-Q)-1， 則軟件系統可靠性可表示為

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

(4)

2 基于構件影響因子的軟件可靠性評估方法

2.1 基于PageRank算法的構件影響因子計算方法

隨著互聯網技術的進步，也逐漸提升了軟件系統功能和結構的復雜度，復雜性變成構件式軟件系統的基本屬性之一[7]，通常把大型軟件系統當作一個復雜系統。國內外研究者使用復雜網絡的理論與統計學的方法分析構件式軟件系統的結構特性，研究結果表明，構件式軟件系統結構具有復雜網絡的特性，可以將軟件系統的結構抽象為一個復雜網絡模型。如何結合復雜網絡理論對軟件系統性能及結構進行分析，國內外研究者已積累了大量的研究成果[8-10]。

在構件式軟件系統中，利用已有的構件組裝開發(fā)軟件系統，可以將構件視為網絡中的節(jié)點，構件之間的連接為有向邊，軟件系統就成為復雜的關系網[11]?；赑ageRank算法的思想，若構件vi調用了構件vk， 則構件vk的重要性分配給了構件vi， 構件vk的被調用次數也決定了構件vi的重要性[12]。但是構件式軟件系統中有輸入/輸出構件，而復雜網絡中沒有輸入/輸出節(jié)點的概念，并且PageRank算法用于有向復雜網絡，而軟件系統網絡是有向加權的復雜網絡，所以需要加入邊的權重對節(jié)點的影響，使用改進的PageRank算法評估構件的影響因子。為了提高構件重要性計算的準確性，首先將構件分為輸入/輸出構件節(jié)點及普通構件，分別計算構件的重要性，在計算普通構件重要性時采用改進的PageRank算法，然后與構件式軟件系統的可靠性評估模型結合，對整個軟件系統的可靠性進行評估，并用于指導、優(yōu)化軟件系統的可靠性。

評估輸入/輸出構件的影響因子公式為

(5)

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

基于PageRank算法對軟件系統網絡中普通構件的影響因子進行評估，以一個有向圖來表示軟件系統的結構，其中每個節(jié)點vi(i=1,2…n) 表示一個構件，有向邊 (vk,vi) 表示構件vk到vi的可能轉移，p(vk,vi) 表示構件vk到構件vi的轉移概率。評估普通構件vi影響因子的計算公式為

(6)

公式中使用構件vk到構件vi的控制轉移概率p(vk,vi)， 相當于引入了加權網絡中邊的權重，改進了傳統PageRank算法中重要性平均分配的不合理性。通過對不同構件的轉移賦予不同的權重，提高重要構件的影響因子SPR值，降低不重要構件的影響因子SPR值。

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

Ai+1=M*Ai

(7)

2.2 基于構件影響因子的構件式軟件可靠性評估

Cheung的模型[5]在計算軟件系統的可靠性時沒有考慮構件的重要性，軟件系統中處于不同的位置的不同構件，不同構件在失效時對軟件系統的影響也有差別，所以需要引入構件影響因子來評估軟件系統的可靠性。

基于Cheung提出的軟件可靠性評估方法，本文將通過PageRank算法得到的構件影響因子引入到軟件可靠性評估模型中，提出了基于構件影響因子的軟件系統可靠性評估方法。引入影響因子后的控制轉移矩陣為

(8)

軟件系統的可靠性表示為

(9)

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

圖1 基于構件影響因子的軟件可靠性評估流程

3 實驗與分析

3.1 實驗對象

為了驗證本文提出的軟件可靠性評估方法的性能，以文獻[13]中的某仿真軟件系統為實驗對象，該仿真系統在軟件可靠性評估領域被廣泛引用。圖2為仿真軟件系統的體系結構圖，其中構件v1為輸入構件，v10為輸出構件，構件間的轉移概率p(vi,vj) 見表1，根據文獻[14]構件vi的可靠性rvi見表2。

圖2 仿真系統體系結構

3.2 基于PageRank算法構件影響因子有效性分析

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

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

表1 構件間轉移概率

表2 構件可靠性

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

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

表3 各構件影響因子

3.3 構件式軟件系統可靠性評估實驗

使用式(9)對該仿真系統的可靠性進行評估，首先根據表1～表3中構件的可靠性、構件間的轉移概率、構件的影響因子及式(8)，可以得到控制轉移矩陣Q為

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

針對圖1中的軟件結構，根據文獻[13]提出的實際軟件系統可靠性為0.8426，將本文的計算結果與幾種不同的軟件可靠性評估方法進行比較，對比結果見表4。

表4 幾種可靠性評估方法對比

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

4 結束語

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