一種開放環(huán)境下的軟件可靠性評估方法

1、一種開放環(huán)境下的軟件可靠性評估方法*)陸 文1，2 徐 鋒1，2 呂 建1，2（南京大學(xué)計算機軟件新技術(shù)國家重點實驗室， 江蘇南京 210093）1（南京大學(xué)計算機軟件研究所， 江蘇南京 210093）2摘 要 目前的軟件系統(tǒng)運行環(huán)境正朝著更加開放的方向發(fā)展，這種開放性對原有的軟件開發(fā)技術(shù)，包括軟件可靠性評估方法提出了挑戰(zhàn)。一些基于軟件測試和模擬的方法由于效率上的不足而不再適用；而另一些方法，例如基于狀態(tài)的可靠性評估方法，雖然在效率上有了很大的提高，但在適用范圍上又存在著不足，比如對含并行結(jié)構(gòu)的系統(tǒng)就不能很好的處理。為此，該文在基于狀態(tài)的可靠性評估方法的基礎(chǔ)上，提出了一種改進的可靠性評估方法，

2、以兼顧效率和適用范圍兩個方面。該方法首先描述了如何用Petri網(wǎng)作為軟件體系結(jié)構(gòu)的描述工具，使得各種復(fù)雜結(jié)構(gòu)的系統(tǒng)都能被很好的描述，并方便具體計算過程的介紹；接著介紹了一種自底向上的可靠性計算過程，來高效并準確的計算出系統(tǒng)的可靠性，該過程能對并行結(jié)構(gòu)進行分解和綜合計算；同時，該方法還可以估算出組件對系統(tǒng)的重要性，從而大大的增強了可靠性評估在軟件開發(fā)中所起的作用。關(guān)鍵詞 軟件可靠性，開放環(huán)境，體系結(jié)構(gòu)，組件重要性An Approach of Software Reliability Evaluation in the Open EnvironmentLU Wen1，2 XU Feng1，2 LU

3、 Jian1，2( State Key Laboratory for Novel Software Technology，Nanjing University，Nanjing，Jiangsu 210093，China)1(Institute of Computer Software，Nanjing University，Nanjing，Jiangsu 210093，China)2+Corresponding author: Phn: +86-013851771715, Fax: +86-25-83593283, E-mail: xf, Abstract Nowadays software en

4、vironment has been more and more open than before, the openness of environment has greatly influenced many existing software development techniques, including software reliability evaluation. Due to the weakness in efficiency, methods based on testing or simulations are not competent in the open env

5、ironment; other methods, such as the state-based methods, are more efficient, but are unable to deal with the systems with concurrency. So this paper tries to put forward an improved reliability evaluation method which can do better in both efficiency and applicability. This method first describes h

6、ow to use Petri nets as software architecture description; and then introduces a bottom-up way to calculate the systems reliability, the calculation process can be done efficiently and accurately, and can also deal with systems with concurrency, which can hardly be handled by existing methods; the m

7、ethod can also generate information reflecting the components importance to the whole system, which can make software reliability evaluation play a more important role in software development.Keywords Software reliability, Open environment, Software architecture, Component importance1 引言在過去的二十年里，Int

8、ernet的迅猛發(fā)展大大影響了我們生活的各個方面，這其中也包括了計算機軟件的開發(fā)和使用。隨著計算機技術(shù)，尤其是分布式面向?qū)ο蠹夹g(shù)的發(fā)展，如EJB，.NET和Web Services等1，各種軟件實體開始以開放、自主的軟件服務(wù)形式存在于Internet的各個節(jié)點上，并通過協(xié)同機制進行跨網(wǎng)絡(luò)的互連、互通、協(xié)作和聯(lián)盟2，這樣，Internet就逐漸成為一個軟件開發(fā)、運行和維護的環(huán)境和基礎(chǔ)。由于Internet本身的開放性和分布性，使得建立在其基礎(chǔ)上的軟件系統(tǒng)與傳統(tǒng)的有所不同，因此會引發(fā)一些問題。其中一個就是：由于對整個環(huán)境只有部分的信息并且無法對其進行控制，因而很難確保組合而成的系統(tǒng)具有較高的可靠性

9、，從而很難得到用戶的信任。類似的問題也出現(xiàn)在了Web Services的發(fā)展與普及過程中，因此，很多工作在這方面展開。Ran用QoS擴展了服務(wù)發(fā)現(xiàn)來選擇具有較高質(zhì)量的服務(wù)3；Sahai等人利用SLA的規(guī)約來保證服務(wù)的質(zhì)量4；Liu提出了利用信任評估和信任傳遞來進行服務(wù)選擇和組裝的框架5。然而，這些方法主要涉及的是如何對構(gòu)成系統(tǒng)的組件進行評估，而對于組合而成的系統(tǒng)的可靠性則鮮有涉及。而在傳統(tǒng)的方法中，基于測試和模擬的方法由于要進行詳盡的分析和計算，因而其效率比較低下，很難適應(yīng)動態(tài)多變的開放環(huán)境；基于體系結(jié)構(gòu)的可靠性評估方法6-9雖然在效率上有所進步，然而他們在Internet這種環(huán)境下還存在著缺

10、陷，一方面這些方法很難處理帶并行結(jié)構(gòu)的系統(tǒng)10，其所采用的軟件體系結(jié)構(gòu)描述方法也不能很好的描述這種結(jié)構(gòu)，因而在適用范圍上還存在著缺陷；另一方面他們的效率還需要進一步提高，尤其是在增量更新方面；同時，這些方法主要側(cè)重于對系統(tǒng)的評估結(jié)果，很少能產(chǎn)生關(guān)于組件的評估信息，因而在軟件開發(fā)過程中只能提供有限的信息。為了解決上述問題，本文試圖對一種特殊的基于體系結(jié)構(gòu)的可靠性評估方法，即基于狀態(tài)的方法進行改進。一方面，利用開放環(huán)境下的軟件系統(tǒng)結(jié)構(gòu)簡單明了的特征，通過一種自底向上的方式來計算可靠性，以進一步增強效率和增量計算的能力；另一方面，通過對系統(tǒng)中的并行結(jié)構(gòu)進行分解，并分別加以計算，最后再綜合的方式來增強

11、方法的適用范圍；同時，在整個計算過程中，還利用計算出來的各部分的可靠性信息來計算每個組件的重要性，來增強方法的作用。通過這三個方面的改進，可以使得開發(fā)并運行在Internet上的軟件系統(tǒng)的可靠性可以被準確快速的計算出來，并能隨著環(huán)境和軟件系統(tǒng)本身的變化而變化，同時組件重要性這一參數(shù)還能為系統(tǒng)的演化過程提供有效的參考。本文組織如下。在第二部分會介紹一下相關(guān)工作，并詳細闡述傳統(tǒng)方法的不足以及對改進方法的要求；第三部分給出了一個利用PetriNet 來描述軟件體系結(jié)構(gòu)的方法；第四部分介紹了詳細的可靠性評估過程；第五部分，我們給出了一個簡單的例子來進一步展現(xiàn)這個評估過程，并驗證方法的有效性和正確性；最

12、后，是對本文的總結(jié)和后期工作的展望。2 開放環(huán)境下現(xiàn)有軟件可靠性評估技術(shù)的分析過去的三十年里，在軟件可靠性評估這一領(lǐng)域已經(jīng)有了很多的方法和技術(shù)。其中一種是黑盒的方式，這種方式將整個系統(tǒng)看作一個單一的個體并且不考慮其內(nèi)部結(jié)構(gòu)，例如各種軟件可靠性增長模型11,12，這些模型通過軟件測試中得到的一些統(tǒng)計數(shù)據(jù)來預(yù)測軟件的可靠性，由于對軟件測試的依賴，使得其在效率上和可操作性方面都不適合開放環(huán)境的需要；另一種是白盒的方式，這種方式會根據(jù)軟件系統(tǒng)的體系結(jié)構(gòu)信息來將各個組件的可靠性進行綜合計算，以得到系統(tǒng)的可靠性6-9。白盒的方式又可以進一步的分為兩類：基于路徑的方法和基于狀態(tài)的方法6?；诼窂降姆椒ㄍㄟ^計

13、算軟件所有可能執(zhí)行路徑的可靠性，然后加以綜合來得到整個軟件的可靠性，但這種方法不適合于具有無限路徑的系統(tǒng)，因而存在著一定的局限性，盡管Dolbec和Shepard試圖采取用組件的使用率來計算可靠性這一方法來解決這個問題，但會帶來精度上的損失9；相對來說，基于狀態(tài)的方法則更優(yōu)越并且更加流行一些，它們利用控制流程圖來表示軟件系統(tǒng)的內(nèi)部結(jié)構(gòu)，并用分析的方式來計算整個系統(tǒng)的可靠性7，這些方法通常有兩個假設(shè)：組件間的獨立性和組件間控制轉(zhuǎn)移的Markov性，前者表示組件間的失效行為是相互獨立的，而后者則表示控制的轉(zhuǎn)移只取決于當前的狀態(tài)，而不受歷史行為的影響。這兩個假設(shè)在大部分情況中都很難滿足，因而在適用范

14、圍上有著局限性。幸運的是，這些假設(shè)在開放環(huán)境下是常常得到保證的，因為開放環(huán)境下的組件是松耦合的，因而具有較高的獨立性。因此，和其它的方法相比，基于狀態(tài)的方法更加適合用來解決開放環(huán)境下軟件可靠性的評估問題。然而，基于狀態(tài)的方法實際上還存在著一些不足。由于這些方法最初是在過程化的程序設(shè)計時代產(chǎn)生的，因而常常假設(shè)在任一給定的時刻，只有一個組件正在執(zhí)行，因此這些方法無法適用于多個組件同時運行的情況10，而這些情況在開放環(huán)境下是經(jīng)常出現(xiàn)且不可避免的；更糟糕的是，它們常常使用控制流程圖來表示程序的結(jié)構(gòu)，這就使得對并行結(jié)構(gòu)的描述很不方便，就更不用說在此基礎(chǔ)上進行進一步的分析了。因此從適用范圍來說，基于狀態(tài)的

15、方法無法完美的適應(yīng)開放環(huán)境。除此之外，開放環(huán)境還在其它方面帶來了一些新的需求l 較高的效率。在開放環(huán)境中，軟件系統(tǒng)是由不同的組件動態(tài)并臨時的組合而成，因此對其進行詳細徹底的分析是不實際、不經(jīng)濟的；同時，環(huán)境的多變性也要求評估方法能盡快完成，以保證所得結(jié)果依然是有效的。因此，效率是最重要的。l 足夠的精確度。高效率的要求必然對評估結(jié)果的精確度帶來了影響，但評估方法仍然要給出足夠精確地結(jié)果，不然會使得用戶得到錯誤的信息，做出錯誤的判斷。l 能產(chǎn)生關(guān)于組件的評估結(jié)果。開放環(huán)境下的系統(tǒng)的典型特征是，整個系統(tǒng)的功能是要靠各個獨立組件之間的協(xié)作和聯(lián)盟來實現(xiàn)的，因而組件所占據(jù)的地位越來越重要。因此，開放環(huán)境

16、下的可靠性評估方法還應(yīng)該提供關(guān)于組件的信息來幫助系統(tǒng)的優(yōu)化和改進，從而在多變的環(huán)境中保持較高的質(zhì)量。然而現(xiàn)有的方法通常通過一個詳細的分析來得到非常精確地結(jié)果，因此在效率上比較低下，這與開放環(huán)境下更加看重效率的要求正好相反。同時，它們往往只得到關(guān)于系統(tǒng)可靠性的信息，而很少產(chǎn)生關(guān)于組件的信息。本文的余下部分將試圖解決這些問題。3 軟件體系結(jié)構(gòu)的描述軟件的體系結(jié)構(gòu)，包含了對構(gòu)成軟件系統(tǒng)的組件的描述，組件間的交互，組件間組合的模式，以及對這些組合模式的約束13，這些都為針對整個軟件系統(tǒng)的可靠性評估提供了有益和必需的信息。一方面，它包含了整個系統(tǒng)的結(jié)構(gòu)信息，而系統(tǒng)的結(jié)構(gòu)是軟件可靠性的一個重要影響因素14

17、,15；另一方面，它還展示了系統(tǒng)在運行時刻是如何活動的動態(tài)信息，這是我們用來預(yù)測軟件運行時刻行為（包括軟件可靠性）的重要依據(jù)。圖1 體系結(jié)構(gòu)描述示例要想充分并有效的利用體系結(jié)構(gòu)信息，就需要使用一種合理并方便的描述手段。一般來說，體系結(jié)構(gòu)的描述能力會影響到基于其的評估方法的適用范圍和易用程度。例如，Wang等人用狀態(tài)圖來表示體系結(jié)構(gòu)8，它們的方法只適用于一些預(yù)定義的經(jīng)典的結(jié)構(gòu)風(fēng)格；Gokhale提出的可靠性評估方法無法處理帶并行結(jié)構(gòu)的系統(tǒng)，其使用的帶概率的控制流程圖7也很難對并行這種結(jié)構(gòu)進行描述；OWL-S使用了幾種基本的控制結(jié)構(gòu)來描述組合服務(wù)的過程模型，這種方法可以描述絕大部分系統(tǒng)的結(jié)構(gòu)16，

18、但對一些復(fù)雜結(jié)構(gòu)(例如遞歸，嵌套循環(huán)的跳出）卻束手無策?？紤]到傳統(tǒng)方法的不足，本文借鑒了Aalst在工作流方面的工作17，決定嘗試用Petri網(wǎng)來作為體系結(jié)構(gòu)的描述工具。Petri網(wǎng)看起來與流程控制圖很像，但它能處理包括并行結(jié)構(gòu)在內(nèi)的各種復(fù)雜結(jié)構(gòu)，并且是一種被廣為研究和使用的工具。圖1是一個用Petri網(wǎng)來描述軟件體系結(jié)構(gòu)的例子。其中Petri網(wǎng)中的絕大部分變遷用來描述軟件的各個組件（還有一部分變遷用作控制結(jié)構(gòu)，如后文所述），在這里，變遷也可以代表一個子系統(tǒng)，當需要查看系統(tǒng)的簡化模型時，可以將代表子系統(tǒng)的圖形部分化歸為一個變遷；反之，當要查看某個子系統(tǒng)的細節(jié)內(nèi)容時，可以用更細節(jié)的內(nèi)容代替相應(yīng)的

19、變遷。在體系結(jié)構(gòu)的Petri網(wǎng)描述中，庫所表示了不同組件之間控制轉(zhuǎn)移的中間狀態(tài)，在某個庫所里有一個令牌表示控制將轉(zhuǎn)移到后續(xù)的組件，顯然，令牌在圖中的傳遞過程代表了運行時刻軟件的執(zhí)行路徑。在實際使用中，體系結(jié)構(gòu)的Petri網(wǎng)表示形式可以利用幾種典型的結(jié)構(gòu)通過自底向上的方式構(gòu)造而成：1) 順序順序是最常用的一種結(jié)構(gòu)，它代表了各個組件依次執(zhí)行，圖 2(a)是順序結(jié)構(gòu)的表示方式。2) 分支分支表明程序?qū)膸讞l候選路徑中選出一條來執(zhí)行，而具體選擇哪一條，取決于運行時刻的程序上下文信息。顯然這種軟件系統(tǒng)運行時刻的行為會對整個系統(tǒng)運行的成功與否有著明顯的影響，但是我們卻無法預(yù)測到這種行為，不過我們可以估計每

20、個分支被執(zhí)行的概率，這些概率足以讓我們對系統(tǒng)的可靠性進行評估。圖 2(b)是分支的描述形式，每個分支的概率都標注在相應(yīng)的弧上。3) 循環(huán)循環(huán)常常被用來表示某個組件將被重復(fù)的執(zhí)行。圖2 (c)描述了循環(huán)結(jié)構(gòu)。在這里，也有一些概率信息，這些信息表示控制流離開和回到循環(huán)體的概率。4) 并行并行表示幾個組件都會被執(zhí)行。在圖 2(d)中, 變遷B和C表示兩個會被一起執(zhí)行的組件；而變遷A和D則用來描述程序執(zhí)行路徑的分裂和合并，其中D不是必須的，這表示所有的路徑一直延續(xù)到結(jié)束，這種情況也是比較常見的，例如Unix類系統(tǒng)中的fork調(diào)用會造成這種結(jié)果。5) 調(diào)用調(diào)用也是一種經(jīng)典的結(jié)構(gòu)，它出現(xiàn)在各種程序開發(fā)方法

21、中，如過程式編程中的函數(shù)，面向?qū)ο笾械姆椒ǖ?，并且是分布式環(huán)境中組件間相互交互的一種主要手段。而對調(diào)用的描述也比較復(fù)雜，假設(shè)組件A調(diào)用了組件B，如果知道A的內(nèi)部結(jié)構(gòu)，那么我們可以用這個內(nèi)部結(jié)構(gòu)的Petri圖表示替代對應(yīng)A的變遷；否則，我們可以簡單的把A和B看成是順序執(zhí)行的，這將不會影響到后面對可靠性的評估結(jié)果。6) goto雖然goto是一種不推薦的控制結(jié)構(gòu)，但其仍有一定的價值。因為有一些復(fù)雜結(jié)構(gòu)，例如遞歸，異常處理等，很難用上面的五種結(jié)構(gòu)來表示，而用goto來表示就比較簡單和方便。goto的Petri網(wǎng)表示也比較簡單，只是將跳轉(zhuǎn)的組件之間用一個庫所連接起來即可，因此可由圖 2(a) 來表示。

22、圖2 幾種典型結(jié)構(gòu)的Petri網(wǎng)描述通過這幾種控制結(jié)構(gòu)，我們便可以繪制出描述整個軟件系統(tǒng)的Petri網(wǎng)來，通常，我們在最前端和最后端各增加一個庫所，分別來表示軟件系統(tǒng)的開始和結(jié)束狀態(tài)。圖1便描述了由8個組件組成的軟件系統(tǒng)。從圖1可以發(fā)現(xiàn)，Petri網(wǎng)描述在圖形上與控制流程圖很相似，因此一些基于流程圖的方法可以很容易的轉(zhuǎn)移到Petri網(wǎng)上面來；而在Petri網(wǎng)方面，已經(jīng)有很多工作用于系統(tǒng)行為屬性的分析與驗證17,18，這些工作可以作為系統(tǒng)評估的一部分來提供更多關(guān)于系統(tǒng)的信息，因而可以使得我們的方法可以和這些工作能很好的共存，并作為對軟件系統(tǒng)進行全面分析的一部分。同時，這種圖形化表示方法也能很容易

23、的從實際的系統(tǒng)中得到，以及與其它表示方法相互轉(zhuǎn)換，如OWL-S18。而在體系結(jié)構(gòu)的提取方面，由于開放環(huán)境下的軟件系統(tǒng)中，組件具有較高的獨立性，它們之間的關(guān)系也呈現(xiàn)出松散耦合的特性，因而我們能很容易的從軟件系統(tǒng)的實現(xiàn)或者規(guī)約說明中分辨出不同的組件，并分析出它們之間的關(guān)系，從而得到類似圖1那樣的Petri表示，但其中的分支概率這類體現(xiàn)軟件運行時刻行為的動態(tài)信息，則很難直接獲取。在傳統(tǒng)的軟件開發(fā)中，這些概率信息可由軟件測試來得到，而在開放環(huán)境的軟件系統(tǒng)中，測試往往是不可行的。這時候，我們可以在系統(tǒng)運行的初期設(shè)置一個初始值，這些初始值可以由專家來指定，或者是一個預(yù)定的值。在程序的運行階段，我們可以監(jiān)控

24、并統(tǒng)計系統(tǒng)的運行行為。當積累的信息達到一定程度時，可以利用這些充足的、準確的信息對系統(tǒng)進行重新評估以獲得更準確、更實時的結(jié)果，因此可以說，本文提出的可靠性評估方法在軟件系統(tǒng)的運行時刻會產(chǎn)生出更加準確、有意義的結(jié)果。關(guān)于這部份的工作目前還做得比較簡單，有待于在今后進行詳細的研究和討論。4 軟件可靠性評估方法在本節(jié)，我們將首先介紹可靠性評估方法所生成的各種結(jié)果，然后再詳細介紹該方法是如何來得到這些評估結(jié)果的。4.1 評估結(jié)果4.1.1 對系統(tǒng)的評估結(jié)果首先，評估方法必須給出關(guān)于系統(tǒng)的可靠性。在我們的方法中，采用了悲觀估計的方式來估計軟件的可靠性。定義1. 軟件系統(tǒng)的可靠性是對整個系統(tǒng)成功執(zhí)行的期望

25、，而系統(tǒng)的成功執(zhí)行意味著所執(zhí)行的所有組件必須全部按用戶的期望執(zhí)行（需要注意的是，冗余備份中的組件可以允許部分失效，這時可把整個冗余備份結(jié)構(gòu)看成一個組件）。假設(shè)系統(tǒng)由來表示，組件為C1、C2Cn，各個組件在系統(tǒng)一次運行過程中的運行次數(shù)為變量t1、t2 tn，則系統(tǒng)的可靠性可由公式(1)給出： (1)由于開放環(huán)境中各個組件之間往往是相互獨立的，因此可以對公式進行簡化來得到公式(2)，以使得在整個計算過程中可以對各個組件分別進行計算，這樣就大大降低了計算的復(fù)雜程度。 (2)由該公式可以看出，系統(tǒng)的可靠性取決于各個組件的可靠性和它們的平均運行次數(shù)，而平均次數(shù)的獲取是比較麻煩的，本節(jié)余下部分將介紹如何將

26、這部分工作進行簡化，以方便計算。4.1.2 對組件的評估結(jié)果開放環(huán)境下的可靠性評估還需要考慮各個組件對系統(tǒng)可靠性的影響，即組件的重要性。文獻19對此進行了簡單的分析，可以看出組件的重要性主要取決于組件自身的可靠性和運行剖面（主要是組件的運行次數(shù)），但該文并沒有給出系統(tǒng)的計算方法。文獻20通過方差來計算組件的重要性，但系統(tǒng)的成功失敗是一個伯努利隨機變量，這一類變量的方差是由期望決定的，因此方差這種指標只側(cè)重于組件可靠性大小對系統(tǒng)可靠性的影響。Siegrist提出了用偏導(dǎo)數(shù)來表示組件的重要性21，但其采用的計算方法僅僅考慮了每個組件的平均運行次數(shù)，而不考慮它自身的可靠性大小，因而無法給出全面的結(jié)果

27、。在本文提出的方法中，依然采用了偏導(dǎo)數(shù)來描述組件的重要性，其定義如下：定義2. 軟件系統(tǒng)中組件的重要性是指系統(tǒng)可靠性相對于該組件可靠性的變化率，其值越大，則說明該組件對系統(tǒng)的影響越大，因而具有較高的重要程度。假設(shè)系統(tǒng)由來表示，則組件A相對于該系統(tǒng)的重要性可由公式(3)得出： (3)從該公式可以看出，所產(chǎn)生的重要性首先是依賴于組件的運行次數(shù)的，因為軟件的可靠性是由組件可靠性作為變量的函數(shù)，其具體的計算是依賴于其運行次數(shù)的，因而最后得到的偏導(dǎo)值也受其影響；另一方面，組件可靠性的改變雖然不會使得自身重要性產(chǎn)生變化，但會影響到其它組件的重要性計算，因而在組件之間的比較中仍會產(chǎn)生影響，因此可以說組件可靠

28、性大小會間接影響其在整個系統(tǒng)中的重要程度。在下一節(jié)，我們將通過對實驗結(jié)果的分析來驗證這一點。4.2 評估過程4.2.1 系統(tǒng)的分解眾所周知，現(xiàn)有的軟件系統(tǒng)是以一種自底向上的方式逐層的構(gòu)造而成，而每一層的構(gòu)造方式都比較簡單，呈現(xiàn)出幾種典型的模式。直觀上來看，可以按照軟件系統(tǒng)的構(gòu)造方式來逐層的計算系統(tǒng)的可靠性，這樣能大大的減少計算規(guī)模和計算復(fù)雜度。假設(shè)系統(tǒng)包含組件C1、C2Cn，各個組件的運行次數(shù)變量為t1、t2tn，而這n個組件又可分別組成m個子系統(tǒng)S1、S2Sm，這m個子系統(tǒng)的運行次數(shù)變量為u1、u2um，則根據(jù)(1)，我們可以得到子系統(tǒng)Si的可靠性為，同時，整個系統(tǒng)的可靠性可用如下方式進行計

29、算： (*) (4)其中(*)的推導(dǎo)可參考文獻20的附錄。同時，公式(3)也可寫為 (5)4.2.2 簡單子系統(tǒng)的計算在軟件的構(gòu)造過程中，最常見的是幾種典型的構(gòu)造方式，可以對這幾種構(gòu)造方式分別進行討論以得到對公式(2)和(3) 進行特化后的結(jié)果。1) 順序結(jié)構(gòu)在順序結(jié)構(gòu)的子系統(tǒng)，各個組件依次執(zhí)行，因此，每個組件都執(zhí)行一次。假設(shè)子系統(tǒng)S由組件C1、C2Cn構(gòu)成，則運用公式(2)和(3)可得到： (6)2) 分支結(jié)構(gòu)在分支結(jié)構(gòu)中，每次運行時，會以一定的概率選擇其中一個分支來運行，假設(shè)子系統(tǒng)S由組件C1、C2Cn構(gòu)成，各組件執(zhí)行的概率為P(C1)、P(C2)P(Cn)，而這些概率信息又代表了每個組件

30、平均被運行的次數(shù)，因而可得：. (7)3) 循環(huán)循環(huán)可分為兩種。一種是固定次數(shù)的循環(huán)，表示循環(huán)體執(zhí)行的次數(shù)是確定的，假設(shè)循環(huán)體A會被執(zhí)行n次，則可以得到： (8)還有一種循環(huán)是基于條件控制的循環(huán)，循環(huán)體會一直被執(zhí)行直到某個終止條件被滿足。假設(shè)循環(huán)體為A，控制流返回A的概率為P(A)，則我們得到整個子系統(tǒng)S的可靠性以及A的重要性為： (9)4) 并行并行結(jié)構(gòu)的可靠性很難判斷，因為這個結(jié)構(gòu)本身并沒有明確的定義，有的情況下并行結(jié)構(gòu)要求所有的組件都要成功完成，而有的情況下只要求其中的幾個組件成功完成。鑒于這個原因，本文僅對其中兩種基本的種類進行討論。第一種是與并行，其含義是只有當并行結(jié)構(gòu)的所有組件都成

31、功運行時，整個并行結(jié)構(gòu)才能稱為是成功的，這經(jīng)常出現(xiàn)在為提高性能而采取并發(fā)操作的情況下。假設(shè)系統(tǒng)S由組件C1、C2Cn構(gòu)成，則可用(6)計算出與并行的可靠性和其中組件的重要性。另一種是或并行，它要求只要有一個組件能成功運行即可。假設(shè)子系統(tǒng)S由組件C1、C2Cn構(gòu)成，則可由(10)計算出或并行的可靠性和其中組件的重要性： (10)與并行和或并行是兩個基本的并行結(jié)構(gòu)，其它的復(fù)雜的情況，例如“至少兩個組件成功”等，都可以通過與并行和或并行的復(fù)合來得到。4.2.3 復(fù)雜子系統(tǒng)的計算在大多數(shù)的情況下，軟件系統(tǒng)每層的構(gòu)造方式可以由上述幾種模式來描述。然而還存在其它一些復(fù)雜的結(jié)構(gòu)難以應(yīng)付，主要是一些“goto

32、”類型的控制結(jié)構(gòu)，例如嵌套循環(huán)的跳出，異常處理等。在這種情況下，我們可以利用傳統(tǒng)的基于狀態(tài)的可靠性評估方法來處理，當然還需進行一些改進來應(yīng)對傳統(tǒng)方法無法處理帶并行結(jié)構(gòu)系統(tǒng)的問題。總的說來，這部分計算包括了三個部分：（一） 將系統(tǒng)分解為一系列的“進程”圖3 生成的虛組件和進程為了使用基于狀態(tài)的方法，首先應(yīng)該把系統(tǒng)里的并行部分分離出來，單獨計算。為了達到這個目的，我們可以把每個最外層的并行結(jié)構(gòu)（意指不包含在其它并行結(jié)構(gòu)里）用一個虛組件來替代，這樣我們就得到了一個不含并行結(jié)構(gòu)的系統(tǒng)，稱之為“進程”。而對每個虛組件來說，其并行結(jié)構(gòu)的每個部分都是相互獨立的，可以遞歸的轉(zhuǎn)化為一系列的進程。詳細的過程如下：

33、1) 對系統(tǒng)的Petri網(wǎng)圖進行處理，首先找到最外層的并行結(jié)構(gòu)，這可以通過首先找到從起始庫所出發(fā)所遇到的第一個分裂變遷（可能有多個，可對每個分別處理）和其對應(yīng)的合并變遷（如果沒有，則以結(jié)束庫所代替），例如圖4-2(d)中的A和D，然后找到所有源自于分裂變遷但又出現(xiàn)在合并變遷前面的各個庫所，變遷和弧，這些便是最外層并行結(jié)構(gòu)所包含的部分，例如在圖1中，所有在變遷t4和變遷t7之間的部分。用一個變遷來代替這個并行結(jié)構(gòu)，用來表示虛組件。這樣，我們就得到了一個不含并行結(jié)構(gòu)的Petri圖，可稱為進程，可以對這個進程中的所有成分加以標記，以表明這些部分已經(jīng)出現(xiàn)在一個生成的進程中了。然后進入步驟2。2) 虛組

34、件的內(nèi)部結(jié)構(gòu)可以被分為幾條獨立的路徑，對每條路徑，我們可以識別出與其相關(guān)的庫所，變遷和弧，這些內(nèi)容便是該路徑的Petri表示，通過步驟3來對每條路徑進行處理。3) 步驟3所做的工作與步驟1相同，只是稍微有點差別，因為在處理過程中可能會碰到一些已經(jīng)出現(xiàn)在其它進程里的變遷或庫所。假設(shè)我們在試圖構(gòu)造進程Pi，在構(gòu)造過程中遇見了一個庫所p（也可能是一個變遷，在這種情況下，我們可以在這個變遷前面加一個輔助的庫所p），而p已經(jīng)出現(xiàn)在了先前生成的進程Pj中。這時，我們對Pj的內(nèi)容進行分析，找出所有源自于且僅源自于p的變遷，庫所和弧，這一部分可以被單獨的作為一個進程，記做Pk，同時p出現(xiàn)在Pi和Pj的部分也可

35、以用Pk來代替。通過以上的工作，我們可以從原始的系統(tǒng)表示中得到一系列的進程和虛組件，這些進程和虛組件也有相應(yīng)的Petri表示。圖3表示了對圖1進行分析后的結(jié)果，可以看出所做的工作僅僅是對原圖進行了劃分，分成幾個相對獨立的部分（當然還要添加一些額外的庫所和變遷來保證每部分是正確的Petri圖）。在圖3中，生成的進程在左邊，而虛組件的表示在右邊。（二） 計算每一個進程的可靠性這一步將利用基于狀態(tài)的方法來計算每個進程的可靠性。假設(shè)進程S由組件C1、C2Cn構(gòu)成，可以得到組件之間的轉(zhuǎn)移概率矩陣Q，其中Qij表示組件Cj在組件Ci之后緊接著執(zhí)行的概率?？梢钥闯?Qk為執(zhí)行k步之后的轉(zhuǎn)移概率?？梢宰C明當t

36、趨于無窮大時收斂，因此就存在矩陣 M = (IQ)1 = I + Q + Q2 + . . . =。假設(shè)組件C1是代表起始狀態(tài)的組件，而Cn是代表終止狀態(tài)的組件，則元素M1i表示組件Ci的平均執(zhí)行次數(shù)，利用這個信息，我們可以計算進程的可靠性： (*) (11)這里(*)的推導(dǎo)也要參考20。（三） 利用進程的可靠性來計算整個系統(tǒng)的可靠性在大多數(shù)情況下，進程之間的關(guān)系比較簡單，可以用一顆樹來表示，在這種情況下，系統(tǒng)的可靠性可以利用前面的方法，按照樹的結(jié)構(gòu)自底向上的計算來得到。然而在極少數(shù)情況下，進程之間的關(guān)系比較復(fù)雜，很難用一棵樹來表示，例如，在圖3中，可以看出對P1可靠性的計算依賴于V2的可靠性

37、，而V2可靠性的計算依賴于P1的可靠性，這種互相包含以及可能出現(xiàn)的自包含的關(guān)系將使得逐層的計算方法束手無策。在這種情況下，假設(shè)我們用Vi來代表虛組件，用Pi來表示進程，Ci表示各個原子組件，則進程的可靠性計算可以由(11)來表示，而虛組件的可靠性可由公式(6)和(10)來表示，這樣，我們就得到了一個方程組：R(P1) =f1R(V1), , R(Vn), R(C1), , R(Cn), R(P1), , R(Pn)R(P2) = f2R(V1), , R(Vn), R(C1), , R(Cn), R(P1), , R(Pn)R(Pn) = fnR(V1), , R(Vn), R(C1), ,

38、R(Cn), R(P1), , R(Pn)R(V1) = g1R(P1), , R(Pn)R(V2) = g2R(P1), , R(Pn)R(Vn) = gnR(P1), , R(Pn)通過解這個方程組，就可以得到各個虛組件以及進程的信任值了。而對重要性的計算也可以采用這種列方程組求解的方式。4.2.4 綜合計算前面描述了對各種控制結(jié)構(gòu)進行計算的方法。這樣，當我們把整個軟件的結(jié)構(gòu)用一顆樹來表示（其中根節(jié)點代表整個系統(tǒng)，中間節(jié)點表示具有以上各種控制結(jié)構(gòu)的子系統(tǒng)，而葉節(jié)點是各個原子組件），就可以按照公式很容易的自底向上的計算出整個軟件系統(tǒng)的可靠性R()。而每個組件的重要性也能很容易的計算出來，假設(shè)

39、a是一個原子組件，整個系統(tǒng)在最上層是由組件C1、C2Cn構(gòu)成的，那么可以利用公式(12)來計算a在整個系統(tǒng)中的重要性D(,a)，這里D(Ci,a)可以被遞歸的計算出來。 (12)4.2.5 可靠性計算方法小結(jié)從上面的分析可以看出，通過對并行結(jié)構(gòu)以先分解再綜合的方式進行處理，使得傳統(tǒng)的基于狀態(tài)的評估方法在適用范圍上得到了增強。而效率方面，對簡單子系統(tǒng)的處理中，由于有效的利用了開放環(huán)境下系統(tǒng)結(jié)構(gòu)簡單清晰的特點，計算復(fù)雜度是O(n)（n是組件的個數(shù)）；而對復(fù)雜子系統(tǒng)處理中，采用的是基于狀態(tài)的評估方法，因而計算復(fù)雜度依然是O(n3)，這是由于主要的資源會被消耗在逆矩陣的計算上。由于在整個系統(tǒng)中，復(fù)雜子

40、系統(tǒng)出現(xiàn)的概率比較低，因此可以近似的認為整個方法是線性的復(fù)雜度，這樣，就比單純的采用基于狀態(tài)的方法要高效的多。這個方法同時也非常適合于多變的開放環(huán)境所要求的增量更新。當某個組件的可靠性發(fā)生了變化，這時只需要對代表那個組件的葉節(jié)點到根的路徑進行重新計算，因而計算復(fù)雜度是O(logn)，而在傳統(tǒng)的方法中，則往往需要從頭開始計算；同時，我們可以忽視那些重要性較低的節(jié)點的變化，因為他們的改變不會對系統(tǒng)造成實質(zhì)性的影響，這一點在我們的實驗結(jié)果中可以看出，通過這種集中注意力在少數(shù)組件上的方式，可以進一步增強增量更新的效率。而當系統(tǒng)的結(jié)構(gòu)發(fā)生了改變，如果這個變動較小，那么只需要對包含這部分結(jié)構(gòu)的子樹進行重新

41、估算即可，這樣只需要做少量的工作。而最差情況下，系統(tǒng)的結(jié)構(gòu)變動非常大，這時就必須要對整個系統(tǒng)進行重新評估。5 實驗與分析本節(jié)將針對圖1所表示的系統(tǒng)給出可靠性評估的示例，計算出系統(tǒng)的可靠性和各個組件的重要性，并對結(jié)果加以分析，以考察本文所提出方法的正確性和有效性。在這個例子中，位于上面部分的并行定義為一個與并行，而下面一個定義為或并行，這樣這個例子就包括了各種控制結(jié)構(gòu)?？梢钥闯觯撓到y(tǒng)最頂層的結(jié)構(gòu)是非常復(fù)雜的，所以我們對其采用復(fù)雜子系統(tǒng)的計算方法。在進行了第一步的工作后，我們可以得到如圖3所示的一些進程和虛組件，其中P1，P2，P3和V1的結(jié)構(gòu)都比較清晰，可以用簡單子系統(tǒng)的計算方法來處理；而P4

42、的結(jié)構(gòu)并不清晰，但其沒有并行部分，因此可以直接采用復(fù)雜子系統(tǒng)計算方法中的第二部分來進行計算。假設(shè)每個組件的可靠性為0.9，那么我們可以構(gòu)造出代表P1（即整個系統(tǒng)）的一棵樹來，如圖4所示。通過自底向上的計算，我們得到樹中各個內(nèi)節(jié)點的可靠性表示，并標在每個節(jié)點的旁邊。最后，我們可以得到P1的可靠性，即： (13)圖4 系統(tǒng)的樹狀結(jié)構(gòu)接下來對P4進行處理，通過計算我們可以得到t4，t5，t6和t7的平均執(zhí)行次數(shù)分別為1.9375，3.125，1.25，1。這樣，P4的可靠性可以用(11)來計算，結(jié)果為0.4628。同時，V2的可靠性可以用來(10)計算，結(jié)果為：表1 組件重要性及其改進后對系統(tǒng)的影響

43、componentt1t2t3t4t5t6t7t8dependence0.89840.68240.43680.18950.30560.12230.09780.8984Improved reliability8%7.9%4.8%2.8%3.3%1.9%1.7%8% (14)公式(13)和(14)構(gòu)成了一個方程組，通過簡單的計算，我們可以得到最終系統(tǒng)的可靠性為0.6326，這與模擬實驗中得到的結(jié)果0.6393非常接近，這說明整個方法在提高了效率的同時，只會引起很小幅度的精確度下降。而組件重要性也可以用類似的方法計算出來，表1列出了計算得出的每個組件的重要性。可以發(fā)現(xiàn)，這些結(jié)果與我們的直觀感覺保持一

44、致，t2比t3執(zhí)行的更加頻繁，因而具有較高的重要性；t6是在一個or并行結(jié)構(gòu)里面，而這個結(jié)構(gòu)通常是用作冗余備份的，從而可以減輕其組件失效的影響，可以從表中看出，t6的重要性要相對于其它組件低得多；在表格的第三行描述了當某個組件的可靠性改善5%之后整個系統(tǒng)可靠性的提升幅度，可以看出對重要性高的組件的改進會給系統(tǒng)可靠性帶來更大的提高，同時那些重要性比較低的一些組件（如t6和t7）對系統(tǒng)的影響很微小，因而可以在更新計算中省略，這能減輕系統(tǒng)監(jiān)控的負擔，并節(jié)省計算資源。圖5和圖6進一步分析了重要性這一參數(shù)。圖5表示了當t2的可靠性增加時，其與t3的重要性比值會不斷下降，這反映了較低可靠性的組件會擁有較高

45、的相對重要性的事實，因為這種組件比較容易成為整個系統(tǒng)的瓶頸；圖6則顯示了但t2的執(zhí)行次數(shù)增加時，其與t3的重要性比值會不斷上升，這就進一步驗證了組件重要性與其執(zhí)行次數(shù)的關(guān)系。從這兩張圖可以看出，我們的組件重要性這一評估結(jié)果是綜合考慮了組件可靠性和其運行次數(shù)這兩個方面的。 圖5 組件可靠性對其重要性的影響 圖6 組件運行次數(shù)對其重要性的影響6 總結(jié)與展望現(xiàn)有軟件系統(tǒng)的運行環(huán)境逐漸朝著更加開放的方向發(fā)展，在這種情況下如何對軟件的可靠性進行快速有效的衡量成為一個急需解決的問題。本文首先對傳統(tǒng)軟件可靠性評估方法的應(yīng)用范圍和效率等方面在新形勢下的不足進行了分析，然后提出了利用Petri網(wǎng)來作為軟件體系結(jié)

46、構(gòu)描述的工具，并對傳統(tǒng)的基于狀態(tài)的可靠性評估方法加以改進的思路，最終得到了一個能處理具有各種控制結(jié)構(gòu)的軟件系統(tǒng)的方法，該方法不但能快速并準確的得到評估結(jié)果，同時還能產(chǎn)生對組件重要性的衡量，來為系統(tǒng)的分析和優(yōu)化提供更多的參考。在今后的工作中，還需要通過實際項目中的應(yīng)用來進一步檢驗該方法的有效性和可操作性；同時，還需要研究如何獲取軟件運行行為的動態(tài)信息，從而對系統(tǒng)的評估結(jié)果進行實時更新，使其能夠及時的反映組件和體系結(jié)構(gòu)的變化；此外，本文給出了組件重要性這一評估結(jié)果，如何利用其來對系統(tǒng)的優(yōu)化和改進也是一個可以深入研究的方向。參 考 文 獻 1 IBM. Autonomic computing: IB

47、Ms perspective on the state of information technology. computing.pdf, 2001.2 呂建, 馬曉星, 陶先平, 徐鋒, 胡昊. 網(wǎng)構(gòu)軟件的研究與進展, 中國科學(xué)E輯, 2006, 36(10): 10371080.3 Shuping Ran. A model for web services discovery with QoS. ACM SIGecom Exchanges, v.4 n.1, p.1-10, Spring, 2003.4 Akhil Sahai, Vijay Machiraju, Mehmet Sayal,

48、 Aad P. A. van Moorsel, Fabio Casati. Automated SLA Monitoring for Web Services. Proceedings of the 13th IFIP/IEEE International Workshop on Distributed Systems: Operations and Management: Management Technologies for E-Commerce and E-Business Applications, p.28-41, October 21-23, 2002 23 M. L. 5 W.

49、Liu. Trustworthy service selection and composition-reducing the entropy of service-oriented web. In 3rd IEEE International Conference on Industrial Informatics (INDIN).6 Goseva-Popstojanova K, Mathur A.P, Trivedi K.S. Comparison of Architecture-Based Software Reliability Models. In Proceedings of th

50、e 12th IEEE International Symposium on Software Reliability Engineering (ISSRE-2001), 2001.7 Swapna S. Gokhale, Kishor S. Trivedi, W. Eric Wong and J. R. Horgan. An analytical approach to architecutre-based software reliability prediction. In IEEE International Computer Performance and Dependability

51、 Symposium 98.8 Wen-Li Wang, Ye Wu, Mei-Hwa Chen. An Architecture-Based Software Reliability Model. Proceedings of the 1999 Pacific Rim International Symposium on Dependable Computing, p.143, December 16-17, 1999.9 Jean Dolbec, Terry Shepard. A component based software reliability model. Proceedings

52、 of the 1995 conference of the Centre for Advanced Studies on Collaborative research, p.19, November 07-09, 1995, Toronto, Ontario, Canada.10 Gokhale, S.S. Architecture-based software reliability analysis: Overview and limitations. IEEE Transactions on Dependable and Secure Computing 4, 32-40 (2007)

53、.11 Goel A.L., Okumoto K. Time-Dependent Error-Detection Rate Models for Software Reliability and Other Performance Measures. IEEE Trans. on Reliability, 28(3):206-211,1979.12 Musa J.D., and Okumoto K. Logarithmic Poisson Execution Time Model for Software Reliability Measurement. In Proceedings of.

54、Compsac 1984, pp. 230-238,1984.13 M Shaw, D Garlan. Software Architecture: Perspectives on an Emerging Discipline. Prentice Hall, Apr. 1996.14 D. L. Parnas. The inuence of software structure on reliability. In Proc. 1975 Intl Conf. Reliable Software, pages 358362, Los Angeles, CA, April 1975.15 M. L

55、. Shooman. Structural models for software reliability prediction. In Proc. 2nd Intl Conf. Software Engineering, pages 268-280, San Fransisco, CA, October 1976.16 D. Martin, M. Burstein, J. Hobbs, O. Lassila, D. McDermott, S. McIlraith, S. Narayanan, M. Paolucci, B. Parsia, T. Payne, E. Sirin, N. Sri

56、nivasan, and K. Sycara. OWL-S: Semantic Markup for Web Services.17 van der Aalst W M P. The application of Petri nets to workflow management. The Journal of Circuits, Systems and Computers, 1998, 8(1): 216618 Eric Andonoff, Lotfi Bouzguenda, Chihab Hanachi. Specifying Workflow Web Services Using Pet

57、ri Nets with Objects and Generating of Their OWL-S Specifications. In Proceedings of the 6th International Conference on Electronic Commerce and Web Technologies (EC-Web'05), LNCS 3590, pages 41-52. Springer-Verlag, 2005.19 張廣梅,李曉維. 基于體系結(jié)構(gòu)的軟件可靠性參數(shù)早期預(yù)測. 計算機工程, 2005, 31(5):90-9220 S. Gokhale, Quantifying the Variance in Application Reliability, Proc. Pacific Ri