張 捷，陸 陽，劉廣亮

（1．合肥工業(yè)大學計算機與信息學院，安徽合肥230009；2．安徽師范大學數(shù)學計算機科學學院，安徽蕪湖241003）

基于結構分析的軟件可靠性評估代數(shù)方法

張 捷1，2，陸 陽1，劉廣亮1

（1．合肥工業(yè)大學計算機與信息學院，安徽合肥230009；2．安徽師范大學數(shù)學計算機科學學院，安徽蕪湖241003）

針對含有多種結構風格的復雜軟件系統(tǒng)，提出一種可靠性評估代數(shù)方法。該方法基于軟件體系結構代數(shù)建模思想，通過分析構件間交互的特點，使用代數(shù)范式形式抽象軟件的基本結構風格。明確了范式向系統(tǒng)狀態(tài)空間的映射關系，由此建立可靠性參數(shù)計算準則，并實現(xiàn)了系統(tǒng)可靠性評估的完整流程。因為代數(shù)語言的高度形式化特征，流程具有結構嵌套處理以及自動完成計算的顯著優(yōu)點。最后通過對一個實際軟件系統(tǒng)的可靠性分析，驗證了代數(shù)方法的適用性與有效性。

軟件可靠性；系統(tǒng)可靠性；軟件結構風格；復雜軟件系統(tǒng)

0 引 言

可靠性是軟件的重要質量指標之一。過去數(shù)十年間，對軟件系統(tǒng)可靠性的研究主要集中于如何有效地建立可靠性模型，以及從模型出發(fā)如何準確地評估系統(tǒng)的可靠度。目前此領域的主流方法分為兩類：一類是基于軟件測試期間所獲得的失效數(shù)據(jù)而建立的可靠性增長模型（software reliability growth model，SRGM）［12］；另一類是在系統(tǒng)設計階段建立的基于結構的軟件可靠性模型（architecture-based software reliability model，ABSRM）［34］。SRGM類方法認為隨著軟件測試的進行，軟件系統(tǒng)的故障會被不斷檢出并修復，從而使整個系統(tǒng)的可靠性具有不斷增長的特性。以G-O模型、J-M模型及對數(shù)泊松分布模型等為代表的SRGM已經(jīng)廣泛應用在軟件測試階段的可靠性評估與預測中，成為開發(fā)后期衡量軟件項目質量的重要依據(jù)。

隨著軟件設計思想的演變，聚集大量可重用構件（同組件）成為軟件開發(fā)的趨勢，這使得ABSRM開始出現(xiàn)并逐漸成為軟件可靠性研究的重要方向。ABSRM類方法相較于SRGM類，最大的不同在于它是白盒方法（而SRGM通常認為是黑盒方法），考慮了軟件內部結構的信息，模型建立在軟件開發(fā)的早期階段，這使得可靠性評估在軟件設計階段就可以進行，對避免在開發(fā)后期因結構設計不當而返回修改所產生的代價有著重要意義，而這種代價往往是巨大的。

Littlewood B首先在文獻［5］中使用半馬爾可夫過程（semi-Markov process，SMP）對軟件結構建模，并率先提出構件可靠性和構件間控制轉移概率是決定系統(tǒng)可靠性的兩個關鍵因素。隨后Cheung R C于文獻［6］給出了他的重要模型，這一模型基于離散時間馬爾可夫鏈（discrete time Markov chain，DTMC），結構中含有吸收態(tài)（相對于SMP它是可約的），將系統(tǒng)成功執(zhí)行的概率刻畫為從初始構件轉移到結束構件的概率，解決了系統(tǒng)可靠性與構件可靠性及構件間控制轉移概率的函數(shù)關系問題?；贒TMC更好的描述性質，他推導出單個構件可靠性對系統(tǒng)可靠性的敏感度公式，用以刻畫關鍵位置構件的可靠性變動對整個系統(tǒng)可靠性的影響程度。而Laprie J C［7］使用連續(xù)時間馬爾可夫鏈（continuous time Markov chain，CTMC）將構件執(zhí)行時間均值作為參數(shù)引入模型，用以反映系統(tǒng)執(zhí)行穩(wěn)態(tài)。這之后出現(xiàn)的ABSRM類方法基本都遵循這一路線。

軟件規(guī)模在不斷增長，軟件結構中所呈現(xiàn)的復雜性也在迅速增加。在Cheung R C的經(jīng)典模型中［6］，僅討論了含有順序 分支單一結構風格的簡單軟件系統(tǒng)，這顯然已不適合當前復雜軟件結構的需要。對此Wang W L等［8］討論了若干種特設軟件結構下的具體可靠性評價方法。Liu C等［9］提出混合軟件可靠性模型概念，增加了調用 返回結構風格。之后，王強等［10］又增加了并行、中斷冗余和容錯結構風格，并分析了這些基本軟件結構風格在可靠性評價中的普適性。同時，一些學者也從描述能力上對ABSRM類方法進行改進。如陸文等［11］使用Petri網(wǎng)描述軟件體系結構，并基于此分解和計算復雜軟件系統(tǒng)的可靠性。趙會群等［12］使用抽象代數(shù)工具和體系結構描述語言（architecture description language，ADL）來描述構件間的依賴關系，使結構風格得以抽象化，并據(jù)此提出可靠性范式的概念，他在SMP模型中證明了該范式的正確性。

軟件結構的復雜性在于基本結構風格的多樣性，并且新的結構風格仍在不斷產生［89，13］。ABSRM類方法需要不斷擴充和調整以適應這些新增的結構風格。同時注意到，目前的ABSRM方法尚不能處理基本結構的嵌套問題。文獻［10］比較完整地討論了若干類基本結構風格的可靠性計算方法，但是并沒有涉及由基本結構嵌套組合形成的復雜子結構的可靠性計算問題，而這種復雜子結構在軟件體系結構設計中經(jīng)常出現(xiàn)。本文使用文獻［10］中對軟件基本結構的分類，立足于在較高的抽象層上對軟件系統(tǒng)體系結構作形式化描述，原因有二：一是新的結構風格的增加在抽象層上并不一定需要增加新的描述方法以適應；二是形式化方法往往具有描述結構嵌套的能力。

另一個問題是對復雜軟件的可靠性評估計算是否可以自動完成。對比最近出現(xiàn)的典型ABSRM類模型或方法［8，1417］可以發(fā)現(xiàn)，它們無一例外都是對目標系統(tǒng)直接建立馬爾可夫鏈（DTMC或CTMC），之后手工計算出整個系統(tǒng)的可靠度。這一過程勢必會隨著軟件系統(tǒng)規(guī)模的增加而愈發(fā)困難。文獻［18］使用了統(tǒng)一建模語言（unified modeling language，UML）對可靠性模型進行轉換，通過引入UML記號使其具備自動計算的能力。但其轉換而成的模型過于臃腫而不易用，需要一整套UML環(huán)境和工具的支持，并且該模型仍缺乏對可泛用的基本結構風格以及結構嵌套的描述。在軟件開發(fā)早期，特別是在體系結構設計階段，如果伴隨每一次結構的修改都能實時自動地計算出最終整個系統(tǒng)的可靠度，這無疑十分有益于設計者的正確決策。

針對以上，本文的工作主要有：

（1）使用代數(shù)方法對軟件體系結構建模，模型以代數(shù)表達式集合的形式體現(xiàn)。這些表達式或為范式（用以表達基本結構風格），或為范式的嵌套組合（用以表達復雜子結構）。

（2）定義基本結構范式向狀態(tài)空間的映射關系，并給出其可靠性計算方法。

（3）給出自動解析代數(shù)表達式集合的流程，依據(jù)映射關系計算生成系統(tǒng)狀態(tài)隨機轉移矩陣，并據(jù)此計算出整個系統(tǒng)的可靠度。

代數(shù)模型對軟件體系結構的描述準確而簡潔，本文首先介紹了該模型以及經(jīng)典的結構分析類軟件可靠性模型理論；然后使用代數(shù)方法描述不同的軟件結構風格，并提出基于代數(shù)范式的可靠性計算方法；接著給出整體的可靠性評估流程，該流程可自動完成；最后用一個實例來驗證可靠性評估代數(shù)方法的有效性。

1 相關工作

1.1 基于結構分析的可靠性評估方法

大多數(shù)ABSRM類方法都建立在文獻［6］的經(jīng)典DTMC模型上。該模型假設單個構件的可靠度已知，構件的失效行為彼此獨立，而且構件間的控制轉移關系滿足馬爾可夫性質，即轉移目標僅取決于當前執(zhí)行構件。圖1給出了由10個構件組成的控制轉移圖。圖中每個結點Ci表示一個單獨構件，其可靠度為常量Ri。有向弧〈Ci，Cj〉表示一個可能存在的由Ci至Cj的控制轉移，用pi，j表示該轉移的發(fā)生概率。定義一步隨機轉移矩陣如下：

式中，Q為n×n矩陣，其中元素Q（i，j）＝Ri·pi，j，表示系統(tǒng)在構件Ci無錯執(zhí)行后成功轉移至Cj的概率。注意到若弧〈Ci，Cj〉本身并不存在，則pi，j為0。

圖1 構件控制轉移圖

考慮Q的k級冪Qk，即k步轉移矩陣，則其元素表示由Ci經(jīng)過k步成功到達Cj的概率。令Neumann級數(shù)

式中，I表示單位矩陣。則N（i，j）表示所有經(jīng)由Ci出發(fā)經(jīng)過若干步成功到達Cj的概率之和。據(jù)此，整個系統(tǒng)的可靠度可由下式計算：

即理解為系統(tǒng)由初始構件C1出發(fā)經(jīng)過若干步成功到達終止構件Cn，并成功執(zhí)行Cn的概率。

易知矩陣Q的譜半徑ρ（Q）＜1，故級數(shù)N收斂，于是有

需要指出的是，文獻［6］的模型中構件間的相互關系只有順序－分支一種，而且假設單個構件可靠度固定不可變動的做法也忽略了系統(tǒng)操作剖面信息等帶來的影響，這之后出現(xiàn)的模型和方法都對此做出了很多改進。

1.2 網(wǎng)構軟件體系結構代數(shù)模型

有研究表明，使用代數(shù)理論建立的體系結構模型，通常具有高度的形式化特征，易得出量化分析結果，這為在開發(fā)早期階段分析系統(tǒng)的可靠性、可維護性、可演化性及可復用性等非功能性屬性方面提供了可能［21］。本文采用文獻［22］中提出的網(wǎng)構軟件體系結構代數(shù)模型。它的優(yōu)勢在于：

（1）使用代數(shù)算子抽象軟件體系結構中的連接子，使得對軟件結構的描述具有高度抽象的形式化特征；

（2）相對于進程代數(shù)，該模型理論使用的代數(shù)語言更加簡潔，易于擴充，而且模型含義準確清晰，便于后續(xù)進行可靠性相關分析。

為敘述扼要，這里只列出代數(shù)模型的定義。

定義1［22］設論域為U，一個U上的軟件體系結構是三元組＜C，O，Ω＞，其中C為構件集合，O為所使用連接子集合，Ω為確定的體系結構風格。

代數(shù)模型中的連接子形式上表現(xiàn)為代數(shù)算子，分別有：“激發(fā)”⊕，“使用”?，“選擇”＋和“協(xié)同”Θ。設有構件A，B∈C，表達式A⊕B由構件和算子組成，它的涵義為構件A對構件B進行了一次激發(fā)，反映了構件間最基本的一種交互方式。激發(fā)動作完成后，系統(tǒng)的控制狀態(tài)將由A傳遞到B。根據(jù)構件間交互方式的不同，補充了算子“并行”‖、“冗余”Δ和“中斷容錯”Ψ。關于這些算子，第2節(jié)會在基本結構范式中逐個討論它們的作用機制。

稱表達式A⊕B為激發(fā)運算范式，記作Role＝A⊕B。而集合Ω是由若干Role組成，即為一個表達式的集合。

用一個實際算例來說明代數(shù)模型如何描述實際的軟件體系結構。該算例來自文獻［10］，屬于安全關鍵系統(tǒng)，其中含有10個構件模塊，圖2給出了它們之間的控制轉移關系。C1是初始模塊；C2與C3分別對應兩類不同的功能模塊，它們都需轉移至核心業(yè)務模塊C4；C5作為C4的一個中斷容錯而存在，功能完全等同于C4，僅當C4出現(xiàn)故障時才接管進程；核心模塊下達的一部分任務會被分解并交由C6與C7并行處理，另一部分任務交由C8處理；而C6、C7和C8都需要使用業(yè)務模塊C9提供的功能；最終結果需經(jīng)由輸出模塊C10處理。

1848年，歐米茄創(chuàng)始者路易士·勃蘭特開設了自己的制表公司，自那時起，他始終致力于生產精準的機心。1894年，勃蘭特兄弟制造出19令機心，并命名為“歐米茄”。這一革命性機心在行業(yè)內廣受贊譽，“歐米茄”也因此成為了公司的品牌名稱，寓意著“完美、卓越與成就”。

圖2 算例構件控制轉移圖

對該實例，如果只采用文獻［6］的DTMC模型來求解系統(tǒng)可靠性，構件間的所有交互關系都將被處理為順序－分支結構，即圖2中所有的有向弧都被認為是控制轉移。如前文所述，顯然這并不合理。例如C2與C5之間的控制轉移多數(shù)情況下并不會發(fā)生，僅當C4失效時才會發(fā)生。而C5作為C4的一個容錯備份，這一關系并不能在圖2中得到直接體現(xiàn)，從而忽略了設計時它們之間確實有連接子存在的事實。C6與C7亦是如此。當然也可以在構件控制轉移圖上添加記號以注明這些構件間的某種連接子的存在，但是不妨換一種思路，如果一開始就使用代數(shù)模型的方法進行體系結構設計會如何。

根據(jù)定義1，該算例的的代數(shù)模型描述如下：

在集合Ω中，只使用了7個表達式就足以描述結構設計意圖。這些表達式中使用了括號，清楚表明了子結構之間的嵌套層次和組合關系，如此便很自然地解決了復雜子結構嵌套的描述問題。如表達式Role4＝（C4ΨC5）⊕（C6‖C7＋C8），它反映了兩個子結構之間的控制傳遞關系。子結構C4ΨC5為基本的中斷容錯運算范式，而子結構C6‖C7＋C8則是復雜表達式，表明了控制流在并行運算塊C6‖C7與C8之間的分支選擇關系。根據(jù)耦合度的高低，這里認為算子‖的優(yōu)先級大于算子＋。事實上，選擇運算是耦合度最低的，在對代數(shù)模型的后續(xù)處理中，需要將選擇運算展開。

定理1［22］激發(fā)運算對選擇運算滿足分配律，即

證明見文獻［22］，這里略去。

根據(jù)定理1，Role4可以展開為（C4ΨC5）⊕（C6‖C7）和（C4ΨC5）⊕C8兩個式子。

顯然Ω中的代數(shù)表達式屬于形式語言范疇，可以使用形式語言的語法分析技術來對它們進行解析?？梢宰C明由有限個算符加上括號所構成的表達式符合上下文無關文法，采用通用的LR分析算法即可完成對這些表達式的掃描與識別。本文第3節(jié)給出解析表達式集合Ω的流程，其目的在于最終生成類似第1.1節(jié)的一步隨機轉移矩陣，以計算出整個系統(tǒng)的可靠度。

2 基本結構風格范式的可靠性計算

代數(shù)模型是對軟件體系結構的高度抽象，能夠準確地描述構件間的交互機制。在代數(shù)模型設計完成后，需要有一套可靠性計算的準則。這一準則從基本的軟件結構風格出發(fā)，形式上表現(xiàn)為由不同代數(shù)算子構成的運算表達式，稱之為基本結構風格范式。計算準則必須是可泛用的，所以范式必須足夠精簡，即不能再被繼續(xù)展開。

本節(jié)討論幾種不同的風格范式，基本涵蓋了目前在ABSRM類方法中出現(xiàn)的軟件結構風格。對這些范式的可靠性計算，使用形如

的映射來完成。式中C為構件集合，而S為系統(tǒng)狀態(tài)結點集合。狀態(tài)結點Si∈S可能對應單個構件，也可能對應若干構件的組合，當系統(tǒng)處于某個狀態(tài)結點上時，控制轉移不會發(fā)生，即認為系統(tǒng)處于一個相對穩(wěn)定的可靠性水平上。

映射^f的主要功能有兩個：一是生成相關狀態(tài)結點并計算其可靠性參數(shù)；二是生成或者更新一步隨機轉移矩陣Q中的元素。矩陣Q形式上等同第1.1節(jié)的隨機轉移矩陣，只是這里的行列坐標對應狀態(tài)結點而非構件。

下文將從基本的軟件結構風格出發(fā)，分別給出它們對應的結構風格代數(shù)范式，以及這些范式的可靠性計算方法。

2.1 順序 分支結構

順序 分支結構是最簡單的軟件結構風格。如圖3（a）所示，構件C1發(fā)出的轉移可在由C2到Ci的若干構件中進行選擇。任一時刻只有當前構件在執(zhí)行，執(zhí)行完成后才會轉移到后續(xù)構件。在代數(shù)模型中，激發(fā)運算是表示控制轉移動作的唯一運算，該運算有嚴格的前后邏輯關系故不滿足交換率?？梢詫D3（a）的結構描述為

顯然，括號內選擇運算用以描述多分支的情況。由定理1，上式可以展開為多式，表示各條由C1到達Cn的不同路徑。當表達式中僅含有激發(fā)和選擇算子時，每個構件都應對應一個系統(tǒng)狀態(tài)結點，如圖3（b）所示。

圖3 順序 分支結構

實際使用代數(shù)模型時，為了便于后續(xù)操作不建議把表達式寫成上述連續(xù)激發(fā)的形式，而應是從左至右兩兩組成一個雙目運算表達式。設有激發(fā)運算范式

式中，A，B∈C；Role1為該范式標記（下同）。記p（Role1）＝pA，B，以表示該激發(fā)范式的發(fā)生概率參數(shù)，等同于構件A向構件B的控制轉移概率。

對雙目表達式Role ，定義映射

（1）對應構件A，B生成狀態(tài)結點SA，SB，若所輸入構件在集合S已存在對應結點，則不需生成新的結點。

（2）更新狀態(tài)結點的可靠性參數(shù)

式中，υ（A），υ（B）表示構件的執(zhí)行頻度數(shù)學期望值。

（3）更新一步隨機轉移矩陣Q中的元素

特別地，認為激發(fā)運算是唯一導致控制轉移的運算，對應系統(tǒng)狀態(tài)的變遷。函數(shù)被定義為只能處理雙目運算的情形。代數(shù)模型在設計時，應當將所有激發(fā)運算寫成雙目而非多目的形式，以便于處理p（Role）參數(shù)。

2.2 調用 返回結構

此結構風格指當前構件為完成某一任務而需調用其他構件的功能。如圖4（a）所示，C1調用C2完成任務后，再將控制傳遞給C3。需要指出的是，傳統(tǒng)的過程調用并不滿足面向構件設計典范，因為這將導致構件實現(xiàn)非獨立，從而不能滿足DTMC模型的失效獨立假設［8］。

圖4 調用 返回結構

圖4（a）的結構關系可以描述如下：

式中，C1?C2反映了C1與C2間的調用關系；?為使用運算的算子，稱C1對C2構成一個使用運算。

設有使用運算范式

為滿足失效獨立假設，需要對Role2作如下演化處理：

式中，X表示所有被A所激發(fā)連接的構件或子式。在圖4（a）的情形下，X即為構件C3。而B′表示當前執(zhí)行構件A在完成對B的正確調用并返回后，所到達的結點，該結點位于A內部，稱B′為A的內部結點，它的可靠性參數(shù)與A相同。

對演化式Role21，定義映射

其工作有：

（1）對應A，B′生成狀態(tài)結點SA，SB′。

（2）更新可靠性參數(shù)RSA＝RSB′＝Rυ（A）A。

（3）更新矩陣元素

式中，p（Role21）＝p（Role2），即Role21式的發(fā)生概率參數(shù)與原式相同。注意到由狀態(tài)結點SA成功到達SB′，僅與構件B的成功執(zhí)行和調用關系的發(fā)生概率有關，反映了SB′實際仍處在當前執(zhí)行構件是A的狀態(tài)。

因為X可能不唯一，故Role22式可能不只一個。其發(fā)生概率參數(shù)p（Role22）＝1，表明到達內部結點所處的狀態(tài)后，系統(tǒng)狀態(tài)將無條件向所有可能的后續(xù)狀態(tài)轉移。新增的Role22式仍使用映射函數(shù)^f1處理。

圖4（a）中的調用結構在演化完成后新增加二式

式中，C′2為內部結點。圖4（b）給出了演化后所對應的狀態(tài)結點轉移關系。

2.3 并行結構與協(xié)同結構

將并行結構與協(xié)同結構放在一起考慮，在代數(shù)模型中分別對應并行運算與協(xié)同運算。如圖5（a）所示，當前執(zhí)行構件C1會將任務交由構件組C2C3…Ci共同完成。構件組內若是并行連接，則描述為

若是協(xié)同連接則描述為

并行與協(xié)同結構的區(qū)別在于：并行結構是任務先分解成子任務交由構件組內的每個構件獨立完成，之后合并子任務形成結果；而協(xié)同結構是任務的執(zhí)行需要構件組內相互協(xié)作完成，中間可能需要構件間相互激發(fā)多次。相同點在于任務執(zhí)行時若組內某個構件失效，則整個任務失敗。故構件組對應一個系統(tǒng)狀態(tài)結點，圖5（b）反映了這一點。

圖5 并行／協(xié)同結構

設有并行運算范式

和協(xié)同運算范式

對二式定義映射

處理，f^3的工作有：

2.4 中斷容錯結構

此結構指當前執(zhí)行構件失效時，系統(tǒng)將啟動中斷機制將控制權收回，轉而傳遞到備份構件繼續(xù)執(zhí)行相同的任務。如圖6（a）所示，當執(zhí)行構件C2失效時，控制權將由C1收回，并轉而交由C2的一個備份C3。若C3仍失效，則交由C4執(zhí)行，…，直到所有的備份構件都失效，則任務失敗。中斷容錯結構具備很強的錯誤恢復能力，適用于可靠性要求較高的軟件系統(tǒng)。代數(shù)模型中，使用算子Ψ來表示這一結構，圖6（a）可描述為

圖6 中斷容錯結構

設有中斷容錯范式

對Role5，定義映射

其工作有：

（1）僅生成一個狀態(tài)結點SA。

（2）更新可靠性參數(shù)

式中，n為范式中的構件數(shù)目。

如圖6（b）所示，結構（C2ΨC3Ψ…ΨCi）僅對應了一個狀態(tài)結點，但其可靠性程度顯然大于單個構件C2獨立完成任務的情形。

2.5 冗余結構

最后討論的是冗余結構風格，它兼顧了可靠性與實時性的雙重要求。如圖7（a）所示，在同一時間內共有n個完全相同的構件C2在執(zhí)行相同任務，n個C2有可能都成功執(zhí)行，也有可能都失敗。設在n個構件中若至少有m個成功（通常取m≥n／2），則整體冗余結構執(zhí)行成功，否則認為是失敗。用算子Δ表示冗余關系，圖7（a）可描述如下：

圖7 冗余結構

設有冗余范式

由n個A連接而成。對Role6，定義映射

其工作有：

（1）僅生成一個狀態(tài)結點SA。

（2）更新可靠性參數(shù)

其中，n／2≤m≤n。

3 代數(shù)模型的可靠性評估

第2節(jié)中，對不同的軟件結構風格，分別給出了相對應的代數(shù)范式描述，并定義了映射～在系統(tǒng)狀態(tài)空間上計算這些范式的可靠性參數(shù)?；诖?，本節(jié)將討論一個完整的體系結構代數(shù)模型的可靠性評估方法，有如下的流程。

代數(shù)表達式屬于形式語言范疇，對表達式集合Ω的掃描與識別基于形式語言的語法分析技術。在輸入信息完整的前提下，上述流程可自動完成對整個系統(tǒng)可靠度的計算。這些信息包含：單個構件的可靠度和執(zhí)行頻度值、構件間的控制轉移概率。

回到第1.2節(jié)中的算例。該例中存在使用運算的情況

而使用運算不符合ABSRM理論的構件間失效獨立假設，故需要對這一類表達式作預處理。同時，為了簡化后續(xù)處理，需要將Ω中的所有選擇運算展開。如

將被展開為C1⊕C2與C1⊕C3兩個式子，以便于處理構件間的控制轉移概率。算法1給出了預處理的過程。

算法1代數(shù)模型預處理

輸入＜C，O，Ω＞

輸出＜C′，O′，Ω′＞

初始化C′＝C，O′＝O，Ω′＝Ω

步驟1從Ω中取表達式Rolei，若Rolei中含有選擇算子，則將其展開為

的形式。Ω′中增加Rolei1，Rolei2，…，Ω′中刪除Rolei。

步驟2重復步驟1直至取完所有表達式。

步驟3O′中刪除算子＋。

步驟4從Ω中取表達式Rolei，若Rolei含有使用算子，則對其演化。Ω′中增加演化式Rolei1（需標記）與Rolei2，Ω′中刪除Rolei，C′中增加內部結點Bi。

步驟5重復步驟4直至取完所有表達式。

步驟6O′中刪除算子?。

經(jīng)過算法1的預處理后，該算例的代數(shù)模型如下：

注意到O′已經(jīng)不包含使用和選擇算子，C′中增加了內部結點B1，B2，而Ω′中增加了由使用表達式演化的Role7、Role8、Role9與Role10。Role7與Roel9均已標記，以表明它們區(qū)別于其他的激發(fā)表達式，需使用映射單獨處理。

對于Role5＝（C4ΨC5）⊕（C6‖C7）這樣的嵌套表達式，語法分析器會按算符優(yōu)先級先從括號內開始解析。按結構耦合程度的高低，算子‖、Θ、Δ與Ψ處于同一級，它們優(yōu)先于算子⊕處理。同時，為了避免二義性，并行、中斷容錯與冗余結構在實際描述時應加以括號。考慮如下式子：

其可理解為子結構AΘB與C的并行連接，也可理解為A與子結構B‖C的協(xié)同連接，這樣便產生了二義。故應當加以括號，例如寫成

的形式，以確保所描述結構是確定無歧義的。

算法2狀態(tài)結點及轉移矩陣生成

輸入＜C′，O′，Ω′＞

輸出S，Q

初始化建立n×n的零矩陣Q，n是C′中構件的數(shù)目。

步驟1從Ω′中取表達式Rolei，若Rolei含有并行／協(xié)同、中斷容錯及冗余子式，則對應使用映射及處理子式，生成狀態(tài)結點Si，以結點Si替換子式。

步驟2重復步驟1直至取完所有表達式。

步驟3從Ω′中取表達式Rolei，若Rolei為標記的演化式，使用^f2處理，否則使用處理，生成狀態(tài)結點并更新矩陣Q中對應元素。

步驟4重復步驟3直至取完所有表達式。

在步驟1中，一個LR分析器負責掃描與識別是否存在括號及相關算子。限于篇幅，這里不再敘述形式語言的LR分析算法。步驟1中會以生成的狀態(tài)結點替換括號所表達的子式，以保證在步驟3開始時Ω′中只存有激發(fā)表達式。另外，僅在步驟3中才會更新矩陣Q的元素，符合只有激發(fā)運算才會進行構件間控制轉移的事實?？紤]到所有構件都可能對應一個狀態(tài)結點的情形，Q被初始化為n×n的矩陣，它的行列坐標初始時都對應一個構件，最終生成的Q中，可能有些行和列仍全為0并沒有被更新，因為可能出現(xiàn)多個構件僅產生一個狀態(tài)結點的情形，例如一個并行結構中的構件。

在軟件開發(fā)的早期，使用代數(shù)方法設計軟件體系結構模型時，根據(jù)本節(jié)提出的流程可實時、自動地計算出模型的整體可靠度。而以往的ABSRM類方法并不能伴隨設計過程進行可靠性的自動計算，這是代數(shù)方法的形式化描述能力所帶來的優(yōu)勢。

4 有效性驗證

表1給出了第1.2節(jié)中算例的單個構件可靠度、執(zhí)行頻度，以及構件間控制轉移概率。該算例屬于工業(yè)安全關鍵系統(tǒng)，經(jīng)實際測試，其可靠度估計值為0.865［10］。需要說明的是，以上數(shù)據(jù)來自系統(tǒng)實際運行時的模塊檢測及失效數(shù)據(jù)，可以認為是系統(tǒng)的穩(wěn)定屬性參數(shù)。

表1 構件可靠度、執(zhí)行頻度及控制轉移概率

該軟件系統(tǒng)早于網(wǎng)構軟件體系結構代數(shù)模型出現(xiàn)，故沒有原始的代數(shù)模型設計。已在第1.2節(jié)中給出了它的代數(shù)模型＜C，O，Ω＞，并在第3節(jié)給出預處理后的＜C′，O′，Ω′＞。

基于第2節(jié)中討論的計算準則，代數(shù)模型在使用算法2后，生成如下系統(tǒng)狀態(tài)一步隨機轉移矩陣：

注意矩陣Q已刪去了順序位置相同并且全為0的行和列，因為這些行和列并不對應實際的狀態(tài)結點。矩陣Q的行列坐標實際對應狀態(tài)結點集合如下：點 對應子結構 ；結點 對應子結構

式中，結S4C4ΨC5S5C6‖C7；而S6與S8則對應了兩個演化式中的內部結點。

表2列出了算例的代數(shù)模型經(jīng)過預處理后，在算法2處理流程中需要計算的相關可靠性參數(shù)?？梢钥闯?，系統(tǒng)狀態(tài)結點與構件并非一一對應，可能出現(xiàn)多個構件對應一個狀態(tài)結點的情況。而狀態(tài)結點可靠度R的計算受到所涉構件可靠度、執(zhí)行頻度及結構風格類型等多個因素的影響。

表2 可靠性評估流程中的相關參數(shù)

圖8明確表示了最終生成的狀態(tài)結點之間的轉移關系。其中系統(tǒng)的初始狀態(tài)為結點S1，當經(jīng)過若干步狀態(tài)遷移到達狀態(tài)結點S9，并成功執(zhí)行S9所對應的構件模塊后，即認為完成了整個系統(tǒng)的一次成功執(zhí)行。

圖8 算例系統(tǒng)狀態(tài)結點關系圖

依據(jù)所得矩陣Q和式（2）、式（3），系統(tǒng)可靠度計算如下：

表3列出了幾種主流ABSRM類方法對該算例的可靠性評估值，計算平臺為Matlab 6.0。

表3 各建模方法可靠性評估值比較

對比可以看出，文獻［6］的模型因為忽略了軟件結構風格的影響，對該軟件系統(tǒng)的評估結果不理性（0.820 8）。文獻［9］的模型優(yōu)勢在于能夠處理確定性轉移與概率性轉移兩類結構，但仍然無法準確反映更多的結構風格，故結果較差（0.814 7）。而文獻［10］與文獻［11］的建模方法評估結果與實際較接近，其中文獻［10］引入了更多的軟件結構風格，而文獻［11］則使用了Petri網(wǎng)以增強模型對結構和執(zhí)行路徑的描述能力。使用本文的代數(shù)方法得到的結果比較理想（0.858 2），與實際評估值的誤差僅在1%以內，說明此方法是有效的。

5 結 論

形式化方法一直是軟件及系統(tǒng)工程理論中的研究熱點。在軟件可靠性評估中引入代數(shù)方法，其優(yōu)勢在于對軟件基本結構風格的準確描述能力。本文的貢獻在基于代數(shù)范式構建了完整的可靠性計算準則與流程，使得軟件模型的可靠性評估可伴隨模型設計同時進行，這無疑在軟件開發(fā)早期有著重要的意義，設計人員可隨時評估模型的更改對整體可靠性帶來的影響，從而有效避免在開發(fā)中后期因結構設計不當?shù)仍缙谌毕荻鴮е碌难诱`。下一步，考慮在軟件的演化和動態(tài)結構更改對可靠性的影響方面對該代數(shù)方法作出改進。

［1］Lyu M R.Handbook of software reliability engineering［M］.New York：McGraw-Hill Press，1996.

［2］Musa J D.Software reliability engineering［M］.New York：McGraw-Hill Press，1998.

［3］Gokhale S S，Trivedi K S.Analytical models for architecture-based software reliability prediction：a unification framework［J］.IEEE Trans.on Software Engineering，2006，55（4）：578- 590.

［4］Gokhale S S.Architecture-based software reliability analysis：overview and limitation［J］.IEEE Trans.on Dependable and Secure Computing，2007，4（1）：30- 40.

［5］Littlewood B.Software reliability model for modular program structure［J］.IEEE Trans.on Reliability，1979，28（3）：241- 246.

［6］Cheung R C.A user-oriented software reliability model［J］.IEEE Trans.on Software Engineering，1980，6（2）：118- 125.

［7］Laprie J C.Dependability evaluation of software systems in operation［J］.IEEE Trans.on Software Engineering，1984，10（6）：701- 714.

［8］Wang W L，Wu Y，Chen M H.Architecture-based software reliability modeling［J］.Journal of Systems and Software，2006，79（1）：132- 146.

［9］Liu C，Liu B，Ruan L.A reliability model based on heterogeneous software architecture［C］∥Proc.of the 8th International Conference on Reliability，Maintainability and Safety，2009：728- 732.

［10］Wang Q，Lu Y，F(xiàn)ang H，et al.Complex software reliability evaluation method based on architecture analysis［J］.Journal of Systems Engineering，2013，28（2）：271- 284.（王強，陸陽，方歡，等.基于結構分析的復雜軟件可靠性評估方法［J］.系統(tǒng)工程學報，2013，28（2）：271- 284.）

［11］Lu W，Xu F，Lv J.An approach of software reliability evaluation in the open environment［J］.Chinese Journal of Computers，2010，33（3）：452- 462.（陸文，徐鋒，呂建.一種開放環(huán)境下的軟件可靠性評估方法［J］.計算機學報，2010，33（3）：452- 462.）

［12］Zhao H Q，Sun J，Wang G R，et al.Reliability model of component based software system［J］.Mini-Micro System，2002，23（8）：950- 954.（趙會群，孫晶，王國仁，等.基于組件的軟件可靠性模型［J］.小型微型計算機系統(tǒng)，2002，23（8）：950- 954.）

［13］Malek S，Mikicrakic M，Medvidovic N.A style aware architectural middleware for resource-constrained，distributed systems［J］.IEEE Trans.on Software Engineering，2005，31（3）：256- 272.

［14］Sato N，Trivedi K S.Accurate and efficient stochastic reliability analysis of composite services using their compact Markov reward model representations［C］∥Proc.of the IEEE International Conference on Services Computing，2007：114- 121.

［15］Sharma V，Trivedi K S.Quantifying software performance，reliability and security：an architecture-based approach［J］.Journal of Systems and Software，2007，80（4）：493- 509.

［16］Cheung L，Roshandel R，Medvidovic N，et al.Early prediction of software component reliability［C］∥Proc.of the 30th International Conference on Software Engineering，2008：111- 120.

［17］Lipton M W，Gokhale S S.Heuristic component placement for maximizing software reliability［M］∥Pham H.Recent Advances in Reliability and Quality in Design.Berlin：Springer，2008：309- 330.

［18］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.

［19］Allen R，Garlan D.A formal basis for architecttural connection［J］.IEEE／ACM Trans.on Software Engineering and Methodology，1997，6（3）：213- 249.

［20］Alessandro A，F(xiàn)lavio C，Marco B.A process algebraic approach to software architecture design［M］.London：Springer-Verlag，2010.

［21］Bernardo M，Inverardi P.Formal methods for software architectures［M］.Berlin：Springer-Verlag，2003.

［22］Zhao H Q，Sun J.An algebraic model of internetware software architecture［J］.Scientia Sinica（Informationis），2013，43（1）：161- 177.（趙會群，孫晶.網(wǎng)構軟件體系結構代數(shù)模型［J］.中國科學：信息科學，2013，43（1）：161--177.）

張 捷（198-0-，男，博士研究生，主要研究方向為可信計算、軟件與系統(tǒng)可靠性。

E-mail：zjzj2526＠hfut.edu.cn

陸 陽（1965- ），男，教授，博士，主要研究方向為計算機控制、傳感器網(wǎng)絡。

E-mail：luyang.hf＠126.com

劉廣亮（197-8- ），男，博士研究生，主要研究方向為復雜網(wǎng)絡、網(wǎng)絡可靠性。

E-mail：homecs＠126.com

Algebraic approach of software reliability estimation based on architecture analysis

ZHANG Jie1，2，LU Yang1，LIU Guang-liang1
（1.School of Computer and Information，Hefei University of Technology，Hefei 230009，China；2.School of Mathematics and Computer Science，Anhui Normal University，Wuhu 241003，China）

An algebraic approach of reliability estimation is proposed，which aims at the diversity of architecture styles in complex software systems．The approach is built on algebraic modeling for software architecture and analyzes the characteristic of component interaction．It provides abstract algebraic paradigms for basic structures．By setting up the mapping relation between the paradigms and the system states，the computational rules of reliability parameters and a process of the overall assessment for system reliability are established．Because of the formal features of the algebraic method applied，the process has significant advantages in dealing with the nested structure and calculating automatically．Finally，in order to illustrate the applicability and effectiveness of the proposed approach，the reliability analysis of an actual software system is presented．

software reliability；system reliability；software architecture style；complex software system

TB 114．3

A

10．3969／j．issn．1001-506X．2015．11．35

1001-506X（2015）11-2654-09

2014- 06- 16；

2015- 05- 14；網(wǎng)絡優(yōu)先出版日期：2015- 07- 09。

網(wǎng)絡優(yōu)先出版地址：http：／／www.cnki.net／kcms／detail／11.2422.TN.20150709.1646.002.html

國家自然科學基金（61070220）；教育部博士點基金（20120111110001）資助課題