李克文，雷永秀，張震濤

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

0 引 言

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

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

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

1 研究基礎

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

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

(1)

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

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

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

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

(2)

R=S(1,n)rvn

(3)

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

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

(4)

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

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

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

在構(gòu)件式軟件系統(tǒng)中，利用已有的構(gòu)件組裝開發(fā)軟件系統(tǒng)，可以將構(gòu)件視為網(wǎng)絡中的節(jié)點，構(gòu)件之間的連接為有向邊，軟件系統(tǒng)就成為復雜的關系網(wǎng)[11]?；赑ageRank算法的思想，若構(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)件，而復雜網(wǎng)絡中沒有輸入/輸出節(jié)點的概念，并且PageRank算法用于有向復雜網(wǎng)絡，而軟件系統(tǒng)網(wǎng)絡是有向加權(quán)的復雜網(wǎng)絡，所以需要加入邊的權(quán)重對節(jié)點的影響，使用改進的PageRank算法評估構(gòu)件的影響因子。為了提高構(gòu)件重要性計算的準確性，首先將構(gòu)件分為輸入/輸出構(gòu)件節(jié)點及普通構(gòu)件，分別計算構(gòu)件的重要性，在計算普通構(gòu)件重要性時采用改進的PageRank算法，然后與構(gòu)件式軟件系統(tǒng)的可靠性評估模型結(jié)合，對整個軟件系統(tǒng)的可靠性進行評估，并用于指導、優(yōu)化軟件系統(tǒng)的可靠性。

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

(5)

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

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

(6)

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

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

Ai+1=M*Ai

(7)

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

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

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

(8)

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

(9)

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

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

3 實驗與分析

3.1 實驗對象

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

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

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

由于該仿真系統(tǒng)軟件結(jié)構(gòu)中只有一個輸入/輸出構(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)進行迭代，迭代48次后滿足終止條件 |Ai+1-Ai|<0.00001， 得到各構(gòu)件vi(1,2,…10) 的影響因子A， 為了使輸入/輸出構(gòu)件的影響因子為1，對影響因子A進行歸一化得到A′。 各構(gòu)件的影響因子計算結(jié)果見表3。

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

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

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

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

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

3.3 構(gòu)件式軟件系統(tǒng)可靠性評估實驗

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

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

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

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

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

4 結(jié)束語

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