網絡化軟件系統故障傳播分析與可靠性評估

薛利興，左德承，張 展

(哈爾濱工業大學 計算機科學與技術學院，黑龍江 哈爾濱 150001)

0 引 言

網絡化軟件(networked software)[1]是部署在Internet環境中的軟件系統的抽象，通常由若干個部署在不同服務器上的、能夠完成一項或幾項功能并對外提供服務的獨立模塊(如：Web服務、各種網絡信息資源等)組成，它們通過Internet網絡進行通信交互、彼此協作共同完成一項復雜的工作。與傳統基于構件的軟件(component-based software)類似，網絡化軟件系統同樣采用分治的思想將復雜任務劃分給多個不同模塊來完成；且網絡中的每個模塊都具有模塊化、信息隱藏、可重用等特性，這些模塊也稱為網絡化構件(networked component)。當前常見的云應用[2](cloud application)、面向服務體系結構[3](service-oriented architecture)、網構軟件[4](Internetware)等均為網絡化軟件的具體實現方式。

與本地化軟件系統不同，網絡軟件系統中的構件通過互聯網進行相互調用和數據傳輸，過程比傳統軟件更為復雜難控。一方面，不穩定的Internet不僅給軟件系統的可靠性帶來一定的負面影響，構件部署在遠端服務器之上難以獲取運行狀態也使交互行為變得更加復雜。另一方面，構建系統更多使用的是互聯網上已有的網絡構件，可能是由不同組織或個人開發的免費構件，也可能是付費使用的商業化構件，這些構件的質量參差不齊難以完全控制，失效后會向后續構件輸出錯誤的數據，從而引發軟件系統內的故障傳播。

本文依據網絡化軟件系統交互方式的特點，定義了符合實際系統的失效模式；分析了構件執行過程及構件間的網絡交互過程，并考慮故障傳播建立系統可靠性模型，詳細列出了建模和求解的步驟；最后結合一個案例驗證了模型的準確性。

1 相關工作

Cheung[5]將軟件系統的可靠性表示為各個獨立模塊的可靠性和使用剖面的函數，提出了一種基于馬爾可夫鏈的軟件可靠性建模方法。通過模型求解和敏感性分析，發現執行頻率高的模塊的可靠性對系統整體可靠性有重要意義。據我們所知，該模型是最早應用狀態法對結構化軟件可靠性建模的方法。Wang等[6]對不同軟件結構進行可靠性建模，包括：串行順序結構、并行結構、主備容錯結構、調用-返回結構等。很多研究都是以Cheung和Wang等的工作為基礎實施的，例如：Isa等[7]引入了任務和資源等因素對系統可靠性進行評估；Brosch等[8]考慮了外部服務、軟件運行環境等因素對系統可靠性的影響；Zheng等[9]將Web服務的歷史失效數據與用戶進行關聯分析，提取新用戶的位置、查找相似的歷史數據、預測各Web服務的失效率，再根據軟件架構預測系統全局可靠性；Distefano等[10]則分析了SOA不同服務組合的可靠性。遺憾的是，這些工作都忽略了系統內的故障傳播。

Cortellessa和Grassi[11]考慮了故障傳播對系統的影響，認為構件中發生的錯誤不一定會導致系統的失效，其有可能在后續構件的執行過程中被屏蔽，只有當錯誤傳播到系統接口時才導致系統失效。為此，他們提出了一種考慮錯誤傳播的軟件可靠性建模方法，但只考慮了單一的數據錯誤，與很多實際情況不符，而且Avizienis等[12]也強調多種失效模式應該得到重視。Filieri等[13]遵循了Avizienis的觀點，提出了一種考慮多種失效模式和錯誤傳播的構件軟件可靠性分析方法，但其只在抽象層次上考慮不同的失效模式、不涉及任何具體的失效模式和具體的系統。Pham和Defago[14]從錯誤檢測的角度將失效模式具體化，同時考慮了順序結構、并發結構、主備容錯結構的執行，對構件軟件可靠性進行分析與預測。隨后，Pham和Defago[15]又在后續工作中詳細討論了軟件中多種容錯結構的建模與可靠性分析。

現有的軟件可靠性模型/分析方法更多關注的是本地化的構件軟件，沒有考慮網絡化構件之間的基于網絡的不穩定交互過程。此外，網絡化構件多數部署在遠端第三方服務器之上，我們很難像本地軟件一樣判斷其運行狀態，因此我們只能從外部觀察其行為、對失效模式進行定義。本文從客觀實際出發，定義了兩種常見失效模式，并提出一種針對網絡化軟件的可靠性建模方法，不僅對構件執行過程和網絡交互過程進行了建模，也考慮了系統內的故障傳播問題。

2 網絡化軟件失效模式

一個構件的失效可以從多個不同角度進行定義，如：域(domain)、一致性(consistency)、可檢測性(detectability)等，其中最常見的是域的角度。構件的輸出由兩部分組成：值域(content/value domain)和時域(timing domain)。理論上，根據構件輸出結果的值域和時域正確與否，可以將失效劃分為：值域錯誤引發的失效、時域錯誤引發的失效、值域和時域同時出錯引發的失效[12]，具體還可以再進行細分，如圖1所示。

圖1 理論中的失效模式分類

在多數的研究工作中，經典的失效分類應用并不多，特別是完全按照這個進行分類的幾乎沒有。主要因為多數系統對時域錯誤并不敏感，時域中的錯誤經常被忽略。通常情況下，只要系統在使用者可容忍的時間范圍給出結果即可，人們更多關注失效的直觀現象，如：停止運行(fail-stop)、停機(halt)等，有的甚至關注停止運行失效時是否給出相關信號。

在網絡化軟件系統中，構件多數運行在他人維護的服務器上，無論系統設計者還是用戶都無法詳細獲知構件的運行狀態，更多時候是通過等待時間的長短來判定構件是否失效。當構件沒有在特定的時間內返回結果，即視其發生了失效，我們稱之為超時失效(timeout failure)。若構件在指定的時間內給出了結果，則需要判斷輸出內容是否正確，進而得知是正確輸出還是發生了值域失效(content failure)。

具體地，將這些失效模式的進行形式化定義。我們將網絡化構件單次執行的結果定義為一個序對

其中，v是構件輸出的內容，即值域結果；t為收到網絡構件給出結果所需要的時間。

定義構件單次執行對應的設計輸出為

其中，V是所有可接受的輸出結果的集合，T*為構件正常執行所需的最長時間或用戶可以等待的最長時間。

當構件的輸出滿足下列條件時視為正確輸出，可以表示為

v∈V且t≤T*

當構件的執行時間超過規定時間，則視其發生了超時失效(timeout failure)，形式化表示是

t>t*

若構件在規定的時間內給出結果，我們需要檢查結果是否正確，若輸出不滿足設計規定的輸出則視為值域失效(數據錯誤)

v?V且t≤T*

事實上，很多系統中的系統失效都是通過時間長短來進行判斷。例如：在嵌入式系統中，通常會采用看門狗(watchdog)技術判斷系統是否失效。看門狗的本質為一個特殊計數器，當處理器沒有在規定的時間內對計數器進行清0，則計數器會發生溢出引發相應的中斷對系統進行重啟。在大型主機系統或高可用集群系統中，多采用心跳檢測(heartbeat detection)技術判斷一個子系統或節點是否失效。心跳檢測的本質與看門狗類似，系統需要在規定的時間發送特定的信號；否則，系統會被視為已經宕機或其中運行的關鍵服務已經發生失效。而在使用TCP協議進行網絡傳輸過程中，若沒有在指定的時間內收到對方的數據或接收確認，即視為本次傳輸失敗，將重新發送數據。以上這幾種情況都可以采用超時失效進行定義和描述。

為了更明確的、直觀的展示正確輸出(未失效)、值域失效、超時失效三者之間的關系，我們將它們在時間軸上進行表示，如圖2所示。

圖2 構件的3種輸出結果

3 故障傳播與可靠性模型

在本節中，我們首先對構件執行過程和構件之間的網絡交互過程分別進行分析和可靠性參數定義，之后利用馬爾可夫鏈建立軟件可靠性模型，并給出詳細建模步驟和求解方法。

3.1 構件執行過程分析

與本地軟件構件相同，網絡化構件中一樣會存在設計缺陷和編碼錯誤，當它們被執行時便引發了構件內部錯誤，此時構件可能立即停止執行，也可能繼續執行。在執行過程中，該錯誤有可能被屏蔽，只有當錯誤到達構件接口時才導致該構件失效。類似地，一個構件的失效也并非一定導致整個系統的失效，錯誤可能在其它構件中被屏蔽，只有錯誤傳播到系統接口時才會引發系統失效。在構件的執行過程中，我們考慮以下5種故障傳播情況：

第1種情況：在一個構件執行過程中，由于內部故障產生了錯誤，進而導致構件的執行時間超過規定時間的上限，即發生了超時失效，此時我們認為該構件無法完成其設計所規定的功能、無法給出執行結果。因此，該失效導致系統無法繼續執行，直接導致系統失效。

第2種情況：構件在執行過程中，由于內部故障產生了錯誤，但構件在規定的時間內給出了結果，只是輸出結果的內容不正確，此時發生了值域失效。盡管該構件失效，但系統依然繼續執行，該錯誤輸出被傳播給后續構件。

第3種情況：當前續的構件產生錯誤輸出(值域不正確)時，后面的構件不得不以錯誤的輸入開始執行。在構件的執行過程中，錯誤可能被構件中的邏輯運算、比較運算等操作屏蔽，使得構件最終產生正確的輸出結果。

第4種情況：構件接收錯誤的輸入(值域不正確)開始執行，錯誤導致該構件在執行過程中導致死鎖、死循環或崩潰等，導致該構件無法在規定的時間內輸出結果，從而產生超時失效，并導致系統無法繼續運行引發系統失效。

第5種情況：構件接收錯誤的輸入(值域不正確)開始執行，但在執行過程中，錯誤既沒有被屏蔽，也沒有導致該構件執行超時，最終構件在規定的時間內輸出了結果，但結果的內容依然不正確。

根據這幾種情況，我們從正確輸入和(值域)錯誤輸入兩個角度定義構件的可靠性參數，如圖3所示。

正確輸入：對于一個網絡化構件Ci，在執行過程中由于多種原因可能在內部產生一個錯誤。該錯誤可能會引發死鎖、死循環甚至程序崩潰，進而導致構件無法按時交付輸出，產生超時失效，這種情況的概率記為tep(Ci)；該錯誤也可能并不影響構件的運行時間，只影響構件的輸出內容，這種情況的概率定義為cep(Ci)。此外，構件Ci也可能不輸出任何錯誤，該情況的概率記為cop(Ci)。正確的輸出包含兩種情況，在內部發生錯誤但被屏蔽或者根本沒有發生錯誤，但我們更關心輸出情況，無需了解內部的細節。根據上面的定義，顯然有：cop(Ci)+tep(Ci)+cep(Ci)=1。

圖3 構件的可靠性參數

(值域)錯誤輸入：對于一個網絡化構件Ci，接收值域錯誤的輸入并在執行過程中將該錯誤屏蔽的概率記為mp(Ci)；該錯誤也有可能引發該構件的超時失效，即發生失效轉換，這種情況的概率定義為tp(Ci)；此外，該錯誤可能沒有被屏蔽也沒有發生類型轉換，而是從構件的輸出接口傳播出去，這種情況的概率記為epp(Ci)。顯然有：mp(Ci)+tp(Ci)+epp(Ci)=1。

3.2 網絡交互過程分析

與傳統本地化軟件不同，網絡化軟件中構件之間通過Internet連接進行數據傳輸，由于網絡的不穩定性，在可靠性建模過程中我們必須考慮構件之間網絡交互對整體的影響。

基于現有Internet協議架構，構件之間的數據傳輸可使用TCP協議或UDP協議。TCP協議本身能夠保證數據可靠地、按順序交付目標主機，當數據在傳輸過程中發生錯誤時，TCP協議自身會進行數據重傳。而UDP協議是一種不可靠性的傳輸協議，通常系統設計者會增加一些相關機制來保證數據的正確傳輸。因此，綜合TCP協議自身的機制和使用UDP協議的設計習慣，我們可以認為網絡構件之間的數據傳輸中不會導致數據錯誤，但可能因為在規定的時間內未收到正確的數據而產生超時失效，從而導致整個軟件系統的立即失效。

在網絡化軟件系統中，不僅構件是系統中的基本元素，構件之間的基于Internet的交互過程也是系統中的重要組成部分。在本文中，我們將構件之間的交互過程視為系統中特殊的構件，并進行可靠性參數定義，如圖4所示。對于網絡化構件Ci與Cj之間的交互過程Iij，在一次交互數據傳輸的過程中有兩種情況：一種是數據在規定的時間內從構件Ci出發被Iij正確傳輸到達構件Cj，這種情況的概率記為cop(Iij)；另一種情況是Iij沒有在規定的時間內將構件Ci所輸出的數據保持一致的交付給構件Cj，即在數據傳輸的過程中發生了超時失效，這種情況的概率定義為tep(Iij)。顯然可知：cop(Iij)+tep(Iij)=1。

圖4 構件間網絡交互過程的可靠性參數

3.3 可靠性模型

一個軟件系統的可靠性不僅依賴于每個構件的可靠性，還受這些構件的使用情況影響。構件使用情況通常用使用剖面(usage profile)來表示[5,6]。

假設系統中有n個構件，分別記為C1,C2…Cn，當構件Ci運行完畢后系統運行構件Cj的概率定義為Pij，所有這樣的概率之集合{Pij}稱為構件使用剖面。Pij可以根據系統的功能和設計進行預估，也可以在系統運行的過程中進行統計，具體計算方法為

其中，frqij是當構件Ci執行完畢后系統運行構件Cj的統計頻率，如果構件Ci執行完畢后系統從未立刻運行過構件Cj，則有frqij=0，從而Pij=0；n為系統內網絡化構件的數量。對于任意的構件Ci，有∑jPij=1。

我們利用馬爾可夫鏈建立系統可靠性模型,假設系統從構件C1開始運行，在構件Cn運行結束后系統運行完畢，具體的建模步驟如下：

對于每個構件Ci，添加兩個狀態CC(i)和CE(i)，分別表示構件接收正確輸入和錯誤輸入的執行過程；

對于每個網絡交互過程Iij；添加兩個狀態IC(i,j)和IE(i,j)，分別表示構件Ci產生正確輸出和錯誤輸出時數據從Ci傳輸到Cj的過程；

設置一個狀態TE，表示因構件發生超時失效而引發的系統失效；

設置兩個狀態STARTC和STARTE，分別表示系統接收正確輸入開始運行和接收錯誤輸入開始運行；

設置兩個狀態ENDC和ENDE，分別表示系統結束運行時輸出正確結果和系統結束運行時輸出錯誤結果；

狀態TE，ENDC和ENDE為吸收態，自轉移概率為1；

從狀態IC(i,j)到CC(j)的轉移概率為cop(Iij)，從狀態IC(i,j)到TE的轉移概率為tep(Iij)；

從狀態IE(i,j)到CE(j)的轉移概率為cop(Iij)，從狀態IE(i,j)到TE的轉移概率為tep(Iij)；

從狀態CC(i)到IC(i,j)的轉移概率為Pijcop(Ci)，從狀態CC(i)到IE(i,j)的轉移概率為Pijcep(Ci)；從狀態CE(i)到IE(i,j)的轉移概率為Pijepp(Ci)，從狀態CE(i)到IC(i,j)的轉移概率為Pijmp(Ci)；

從狀態CC(i)到TE的轉移概率為tep(Ci)，從狀態CE(i)到TE的轉移概率為tp(Ci)；

從狀態STARTC到CC(1)的轉移概率為1，從狀態STARTE到CE(1)的轉移概率也為1；

從狀態CC(n)到ENDC的轉移概率為cop(Cn)，從狀態CC(n)到ENDE的轉移概率為cep(Cn)；

從狀態CE(n)到ENDE的轉移概率為epp(Cn)，從狀態CE(n)到ENDC的轉移概率為mp(Cn)；

從狀態CC(n)到TE的轉移概率為tep(Cn)，從狀態CE(n)到TE的轉移概率為tp(Cn)；

在這個馬爾可夫模型中，系統從狀態STARTC或STARTE開始運行，進入3個吸收態TE，ENDC，ENDE之一即運行結束。STARTC表示系統接收正確輸入開始運行，STARTE表示系統接收錯誤輸入開始運行，一旦進入狀態TE表示某個構件或網絡交互過程發生超時失效直接導致系統失效，進入狀態ENDE表示有數據錯誤最終傳播到系統接口，進入狀態ENDC表示系統最終給出了正確的輸出結果。

通常情況下，系統的可靠性定義為系統接收正確輸入并給出正確輸出結果的概率[13,14]。對應于我們的馬爾可夫模型，系統可靠性等價于從狀態STARTC出發到達狀態ENDC的概率。

將馬爾可夫模型對應的轉移矩陣寫成如下形式

其中，子陣I為的3×3單位矩陣；子陣Q為方陣，且不包含與3個吸收態ENDC，ENDE和TE相關的轉移概率；子陣R表示從其它狀態到3個吸收態的一步轉移概率，且R的3列從左到右分別表示ENDC，ENDE和TE。

設V=v(x,y)=(I-Q)-1R，從狀態ENDC出發到STARTC的概率為v(1,1)，因此系統的可靠性為R=v(1,1)

4 實驗驗證

本節通過一個案例來驗證本文所提方法的正確性，并與現有方法進行對比。

如圖5所示，系統中有5個網絡化構件，表1和表2分別列出了構件接收正確輸入和錯誤輸入時的可靠性參數值，表3列出了各構件之間網絡交互過程的可靠性參數。

根據軟件系統的結構，建立對應的可靠性模型，將各構件的可靠性參數值、各網絡交互過程的可靠性參數值以及使用剖面概率值帶入模型之中，計算得到系統的可靠性為0.980 086。

圖5 實例系統的架構及構件的使用剖面

構件ceptepcop=1-cep-tepC10.000 1010.000 4130.999 486C20.000 2890.000 5160.999 195C30.000 3730.000 5340.999 093C40.000 2970.000 5030.999 201C50.000 4340.000 5540.999 012

表2 構件接收錯誤輸入時可靠性參數值

表3 網絡交互過程的可靠性參數值

在實際系統中驗證我們的模型是非常困難的，因為在軟件系統中失效是小概率事件，可能需要花費相當長的時間才能觀察到一次失效。為此，本文與現有的構件軟件可靠性分析研究[7,8,14-16]一致，采用仿真實驗來進行模型驗證。對于目標系統中的每一個構件，實現一個名義(dummy)構件，即接口與原構件定義完全一致，但其內部只依據該構件可靠性參數定義的概率隨機產生正確輸出、錯誤輸出及超時失效。對于構件間的各個交互過程，我們將其視為特殊構件，同樣實現一個名義構件來模擬它們的工作過程。將各個名義構件按照目標系統架構和使用剖面進行組合連接，形成一個目標系統的仿真測試平臺。在測試平臺中，調用系統N次，觀察系統輸出，記錄產生正確輸出的次數NC，最終系統的可靠性為R=NC/N。

在本文的仿真實驗中，共調用系統1 000 000次，即N=1 000 000，獲得正確輸出的次數為980 943，即Nc=980 943，因此系統的可靠性為0.980 943。本文模型計算得到系統的可靠性與仿真實驗得到結果只相差0.000 857，誤差率為0.874‰，可以認為本文模型足夠接近仿真實驗的結果。

Brosch等[16]提出的可靠性模型同樣考慮了網絡對軟件系統的影響，應用該模型計算得到的系統可靠性為0.969 328，與仿真實驗結果相差0.011 615，誤差率為11.841‰，具體的對比結果見表4。此外，本文模型與Brosch模型的對比見表5。

Brosch模型將網絡化軟件劃分為軟件層和網絡層，將系統整體可靠性視為它們二者可靠性的乘積；使用該方法的必須先得到網絡層的可靠性，顯然不適用于廣域網或基于Internet的網絡軟件。本文將構件之間的各個網絡交互過程視為相互獨立的特殊構件，通過與使用剖面相結合建立離散時間馬爾可夫模型，不僅符合廣域網或Internet路由的特性，也可用于局域網內交互過程的抽象，適用范圍更廣。此外，Brosch模型中的可靠性參數沒有給出明確定義，本文模型所用到的可靠性參數均來源于工程實踐、給出了明確的定義，具有更強的可操作性和現實意義。

表4 仿真結果與模型計算的比較

表5 本文模型與Brosch模型的對比

5 結束語

本文針對網絡化軟件系統提出一種可靠性建模方法，不僅考查了各構件及構件間網絡交互過程對系統的影響，也考慮了系統內的故障傳播。首先，根據網絡化構件的特點，提出了數據錯誤和超時失效兩種符合工程實踐的失效模式；經過對構件執行過程和網絡交互過程的詳細分析，從正確輸入和值域錯誤輸入兩種情況定義構件可靠性參數、將構件執行過程及故障傳播形式化，同時將網絡交互過程視為系統內的特殊構件定義可靠性參數、將網絡的影響形式化，最后利用馬爾可夫鏈建立網絡化軟件可靠性模型。實驗結果顯示，本文模型的結果足夠接近于仿真實驗結果；與現有模型相比，該模型適用范圍廣，且具有更強的可操作性和實踐意義。

參考文獻：

[1]MA Yutao,HE Keqing,LI Bing,et al.Empirical study on the characteristics of complex networks in networked software[J].Journal of Software,2011,22(3):381-407(in Chinese).[馬于濤,何克清,李兵,等.網絡化軟件的復雜網絡特性實證[J].軟件學報,2011,22(3):381-407.]

[2]Larus J.The cloud will change everything[C]//Proc of the 16th Int Conf on Architectural Support for Programming Languages and Operating Systems.New York:ACM,2011:1-2.

[3]Sward R,Boleng J.Service-oriented architecture (SOA) concepts and implementations[C]//Proc of the ACM Conf on High Integrity Language Technology.Boston:ACM,2012:11-12.

[4]Zhang J,Lei H.Research status and prospect of Internetware reliability[C]//Proc of the 4th Int Conf on Computer Science and Network Technology.Harbin:IEEE,2015:401-411.

[5]Cheung R.A user-oriented software reliability model[J].IEEE Trans on Software Engineering,1980,6(2):118-125.

[6]Wang W,Pan D,Chen M.Architecture-based software reliability modeling[J].Journal of Systems and Software,2006,79(1):132-146.

[7]Isa M,Jawawi D.A reliability estimation model using integrated tasks and resources[J].Journal of Theoretical and Applied Information Technology,2015,74(2):171-182.

[8]Brosch F,Koziolek H,Buhnova B,et al.Architecture-based reliability prediction with the palladio component model[J].IEEE Trans on Software Engineering,2012,38(6):1319-1339.

[9]Zheng Z,Ma H,Lyu M,et al.QoS-aware web service re-commendation by collaborative filtering[J].IEEE Trans on Services Computing,2011,4(2):140-152.

[10]Distefano S,Filieri A,Ghezzi C,et al.A compositional method for reliability analysis of workflows affected by multiple failure modes[C]//Proc of the 14th Int ACM SIGSOFT Symp on Component Based Software Engineering.Boulder:ACM,2011:149-158.

[11]Cortellessa V,Grassi V.A modeling approach to analyze the impact of error propagation on reliability of component-based systems[C]//Proc of the 10th Int Symp on Component-Based Software Engineering.Medford:Springer Verlag,2007:140-156.

[12]Avizienis A,Laprie J,Randell B,et al.Basic concepts and ta-xonomy of dependable and secure computing[J].IEEE Trans on Dependable and Secure Computing,2004,1(1):11-33.

[13]Filieri A,Ghezzi C,Grassi V,et al.Reliability analysis of component-based systems with multiple failure modes[C]//Proc of the 13th Int Symp on Component-Based Software Engineering.Prague:Springer Verlag,2011:1-20.

[14]Pham T,Defago X.Reliability prediction for component-based systems: Incorporating error propagation analysis and different execution models[C]//Proc of the 12th Int Conf on Quality Software.Xi’an:IEEE,2012:106-115.

[15]Pham T,Defago X.Reliability prediction for component-based software systems with architectural-level fault tolerance mechanisms[C]//Proc of the 8th Int Conf on Availability,Reliability and Security.Regensburg:IEEE,2013:11-20.

[16]Brosch F,Buhnova B,Koziolek H,et al.Reliability prediction for fault-tolerant software architectures[C]//Proc of the Joint ACM SIGSOFT Conf on Quality of Software Architectures & Int Symp on Architecting Critical Systems.Boulder:ACM,2011:75-84.