面向軟件演化的可靠性分析代數(shù)方法

張捷 陸陽 張本宏 劉廣亮

軟件演化一直是軟件工程領(lǐng)域的挑戰(zhàn)性問題.由于客戶需求、環(huán)境變化、技術(shù)進(jìn)步等原因,軟件有著更新演化的現(xiàn)實需要,由此帶來的開發(fā)及管理問題可能非常復(fù)雜.針對軟件演化的定量分析已經(jīng)被公認(rèn)是橫亙軟件生命周期的最復(fù)雜問題之一,而軟件架構(gòu)(Software architecture,SA) 的提出為問題的表述與解決提供了方向.近年來,通過使用SA相關(guān)方法和工具已較好解決了軟件演化所帶來的障礙、成本等問題,并且涌現(xiàn)出一些新的觀點如演化風(fēng)格、演化路徑等[1?3].但在對軟件演化過程的精確描述和完整建模上,并沒有出現(xiàn)公認(rèn)的一般性方法.需要說明的是,目前針對演化的研究都是過程性研究,它基于架構(gòu)工程師對軟件更迭過程的完整監(jiān)控,若此工作僅依賴編碼人員,會不可避免地出現(xiàn)架構(gòu)侵蝕或架構(gòu)偏移問題[4].一個可行思路是對現(xiàn)有的SA工具進(jìn)行推廣和擴(kuò)充,使之能夠適用于面向軟件演化的過程性分析需要.SA 發(fā)展至今,其工具和方法的易用性一直是尚待解決的難題,如何準(zhǔn)確、高效地描述演化需求和過程,進(jìn)而使得架構(gòu)設(shè)計者和開發(fā)者都可以快速掌握和應(yīng)用,有很實際的意義.

另一方面,脫離架構(gòu)指導(dǎo)的代碼演變極易導(dǎo)致軟件設(shè)計與實現(xiàn)的錯位,而要修正此類問題往往代價巨大.以目前用戶最多的學(xué)習(xí)管理軟件Moodle為例,它在演化過程中曾經(jīng)歷過重大變化以及大量問題的修復(fù)[5].雖然擁有龐大的開發(fā)者社群和完整的開發(fā)過程記錄,但是此開源項目尚沒有清晰的架構(gòu)設(shè)計和演化方案描述.每當(dāng)新版本發(fā)布,僅用文字記錄下哪些新開發(fā)的組件被加入,哪些組件被更改,工程方法的缺失使得版本更迭脫離了SA 設(shè)計指導(dǎo),很可能最終導(dǎo)致代碼實現(xiàn)架構(gòu)與設(shè)計架構(gòu)的差異.研究已經(jīng)證實這些差異或稱錯位情形,對軟件系統(tǒng)的質(zhì)量指標(biāo)如可用性、可維護(hù)性、可靠性等將產(chǎn)生非常負(fù)面的影響[6].

最近的軟件演化研究多集中于實證分析,通過軟件度量和失效數(shù)據(jù)等在演化過程中的變化揭示一般規(guī)律.如文獻(xiàn)[7]提出通過分析驅(qū)動演化的錯誤報告及變更請求等以評估演化過程質(zhì)量,其方法完全基于對過程度量數(shù)據(jù)的標(biāo)準(zhǔn)化衡量,利于工具實現(xiàn).文獻(xiàn)[8]利用復(fù)雜網(wǎng)絡(luò)對Linux 操作系統(tǒng)演化過程進(jìn)行實證研究,通過對前后近1 300 個發(fā)布版本中所有C 函數(shù)及其相互調(diào)用關(guān)系構(gòu)建有向網(wǎng)絡(luò),展現(xiàn)了網(wǎng)絡(luò)在規(guī)模、入/出度、聚類系數(shù)等不同拓?fù)湫再|(zhì)下的演化過程.利用復(fù)雜網(wǎng)絡(luò)拓?fù)鋵傩苑治?作者揭示了函數(shù)模塊的各類演化形式,并指出主要組件函數(shù)模塊演化的統(tǒng)計學(xué)規(guī)律.而文獻(xiàn)[9]在對2002年～2016 年Linux 各版本的Bug 報告進(jìn)行分類整合基礎(chǔ)上,重點關(guān)注了故障觸發(fā)在版本演化過程中的規(guī)律性特征,指明Linux 組件模塊在測試時的重要性排列以及聚類系數(shù)對衡量錯誤類型比例的作用.上述研究使用的模型或方法具有新穎性與可操作性,但其關(guān)注的重點在對既有演化過程的數(shù)據(jù)分析,對演化過程及演化行為本身的描述并沒有論及.此外,文獻(xiàn)[10]通過構(gòu)造Markov 過程用以表示運行在多重環(huán)境下的系統(tǒng)演化,用于系統(tǒng)可靠性及環(huán)境可靠性的數(shù)值分析.文獻(xiàn)[11]關(guān)注了使用演化博弈論解決復(fù)雜網(wǎng)絡(luò)環(huán)境下個體間間接互惠及合作演化的問題,對演化行為研究提供了新的思路.在文獻(xiàn)[3]中,作者提出了一種基于QVT 語言的方法,將源碼層面的演化行為轉(zhuǎn)換到SA 層面以緩解架構(gòu)與代碼的失配問題.上述方法并不面向演化過程建模,且方法的易用性對開發(fā)者而言也并非友好.本文旨在使用輕量且抽象程度更高的代數(shù)方法建立軟件演化過程的序列化描述,側(cè)重于分析序列中演化行為對軟件系統(tǒng)整體的影響,并結(jié)合代數(shù)描述的可計算性實時得出量化結(jié)果.

軟件工程活動的主要目的在于開發(fā)和維護(hù)高質(zhì)量的軟件系統(tǒng),對軟件演化的定量分析應(yīng)以提高軟件產(chǎn)品質(zhì)量為出發(fā)點.評價軟件質(zhì)量的指標(biāo)與方法眾多,本文選取可靠性指標(biāo)進(jìn)行研究,這是因為:1) 結(jié)構(gòu)化軟件可靠性模型(區(qū)別于傳統(tǒng)增長類模型)與SA 有直接相關(guān)性,它可伴隨結(jié)構(gòu)的演變工作,適用于架構(gòu)工程師預(yù)先評估整個演化過程的質(zhì)量發(fā)展趨勢;2) 可靠性的計算基于對軟件結(jié)構(gòu)的精確分析,這與其他軟件質(zhì)量指標(biāo)相同或相近(如可維護(hù)性),使得研究不失一般性特點.特別地,當(dāng)對象為一類安全關(guān)鍵軟件系統(tǒng)時,因其對版本更迭前后的質(zhì)量抖動更加敏感,相應(yīng)的演化需求及演化進(jìn)程需要更嚴(yán)格的評估及監(jiān)控,而可靠性作為最關(guān)鍵的非功能性指標(biāo)具有重要價值.基于此,本文站在可靠性的角度分析軟件演化過程及其對軟件質(zhì)量的影響,主要解決以下三方面的問題:

1) 建立模型以準(zhǔn)確描述軟件結(jié)構(gòu)的演化;

2) 演化過程中對軟件可靠性的實時計算;

3) 對演化關(guān)鍵步驟及趨勢的分析.

結(jié)構(gòu)化軟件可靠性建模研究始于Littlewood[12]的SMP (Semi-Markov process) 模型,他首先提出單個組件成功執(zhí)行概率(或稱組件可靠性) 和在工作流上的組件間控制轉(zhuǎn)移概率是決定系統(tǒng)整體可靠性的兩個關(guān)鍵因素.Cheung[13]在此基礎(chǔ)上給出DTMC(Discrete time Markov chain)模型,它明確了二者與系統(tǒng)可靠性之間的函數(shù)關(guān)系.DTMC 模型相較SMP 具有強(qiáng)Markov 性質(zhì),但它僅將組件執(zhí)行時間看作單位時間并忽略其在建模中的作用.隨后Laprie[14]使用CTMC (Continuous time Markov chain) 將組件執(zhí)行時間均值作為建模參數(shù)引入,用于刻畫系統(tǒng)執(zhí)行穩(wěn)態(tài).需要指出的是,在CTMC 模型中執(zhí)行時間必須服從指數(shù)分布以滿足Markov 性質(zhì),而近來有研究認(rèn)為,這一限定在更復(fù)雜的應(yīng)用場景中已不合時宜.如Zheng 等[15]在分析Web 服務(wù)的性能與可靠性時回歸了SMP 方法,其強(qiáng)調(diào)在單個服務(wù)上的逗留時間滿足一般分布,并通過在轉(zhuǎn)移時間點(或稱更新點) 上建立DTMC,以計算多種結(jié)構(gòu)類型的組合服務(wù)可靠性和單個/組合服務(wù)的響應(yīng)時間均值、方差,結(jié)果可用于可靠性及性能瓶頸分析.進(jìn)一步地,通過將一維SMP 泛化至二維MRGP(Markov regenerative process),可描述服務(wù)端、用戶端在不同場景、策略、行為下的組合狀態(tài)遷移,其在用戶感知的服務(wù)性能評估上優(yōu)于傳統(tǒng)CTMC 模型[16].

上述模型和方法的差異在對組件執(zhí)行時間的處理上,而本文主要討論軟件演化可靠性分析一般性方法,傾向使用相對簡便的DTMC 模型,以突出需要解決的核心問題是對軟件演化的描述與可靠性實時分析.而解決問題的關(guān)鍵在于引入代數(shù)方法.通過代數(shù)方法將軟件演化過程序列化,并跟蹤分析序列中每一步操作,使得整個演化過程受到完整監(jiān)控;同時代數(shù)方法本身的精確、輕量、易用等特征也確保了架構(gòu)設(shè)計者的意圖能夠被開發(fā)人員準(zhǔn)確理解,且不會造成他們太多額外的負(fù)擔(dān).本文余下的內(nèi)容組織如下:第1 節(jié)將介紹相關(guān)知識背景,包括軟件結(jié)構(gòu)化可靠性分析的主流方法以及簡單增量式演化的計算;第2 節(jié)給出了結(jié)構(gòu)演化的實例,說明對其描述的困難程度;第3 節(jié)討論如何使用代數(shù)方法構(gòu)建面向演化過程的序列化模型;兩個算例在第4 節(jié)中被深入討論,以驗證代數(shù)方法的有效性和易用性.

1 DTMC 模型與增量式演化

軟件可靠性分析的關(guān)鍵在于模型的選擇.傳統(tǒng)的軟件可靠性增長類模型基于測試期失效數(shù)據(jù),并不適用于軟件結(jié)構(gòu)演化時的可靠性分析.這里只介紹主流的結(jié)構(gòu)化模型分析方法,其基本模型為Cheung 的DTMC 模型[13].下文以歐洲航天局ESA 的小型控制系統(tǒng)軟件[17]為例進(jìn)行說明.

圖1 ESA 軟件組件遷移圖Fig.1 The component transition diagram of ESA software

由圖1 示，該軟件系統(tǒng)含有4 個主要組件N1～N4,圖中組件節(jié)點反映了系統(tǒng)執(zhí)行的4 個穩(wěn)態(tài),節(jié)點間的控制轉(zhuǎn)移以有向弧表示,弧上標(biāo)注轉(zhuǎn)移概率.注意到圖1 中包含兩個吸收態(tài)分別表示組件失效后到達(dá)以及成功執(zhí)行到達(dá)的狀態(tài)節(jié)點.去除節(jié)點后,可建立DTMC 一步隨機(jī)轉(zhuǎn)移矩陣Q如下:

其元素Qi,j表示了在Markov 過程中從狀態(tài)節(jié)點i轉(zhuǎn)移至節(jié)點j的轉(zhuǎn)移概率.如Q1,2=R1P1,2,它反映由節(jié)點N1經(jīng)一步轉(zhuǎn)移至節(jié)點N2的概率等于成功執(zhí)行N1組件的概率R1與轉(zhuǎn)移分支概率P1,2的乘積.矩陣Q的n次冪Qn為n步隨機(jī)轉(zhuǎn)移矩陣,其元素反映了由節(jié)點i經(jīng)n步轉(zhuǎn)移至節(jié)點j的概率.而Q的Neumann 級數(shù)S表達(dá)了由N1經(jīng)所有可能步數(shù)成功到達(dá)N4的概率和,即

其中,I為單位矩陣,并且易知級數(shù)收斂.對ESA 軟件系統(tǒng),其整體可靠性計算為

即由節(jié)點N1出發(fā)成功到達(dá)N4,并正確執(zhí)行N4的概率.

由式(2),可認(rèn)為Rsys為單個組件可靠度Ri的函數(shù).稱Bi為系統(tǒng)整體可靠性對組件Ni的敏感度,有

一個明顯的結(jié)論是B4=S1,4,但其余并不容易得出.

DTMC 模型可以直接計算一類簡單的增量式演化,增量指的是單個組件因為改動而導(dǎo)致的可靠度增加或降低[18].令A(yù)=I -Q,B=M4,1,其中,M4,1為元素A4,1的余子式.考查組件N3獲得增量δ后的情形,演化后S1,4可計算為

式(4) 即為N3增量演化后的整體可靠性計算方法.對單個組件的簡單增量式演化行為,可靠性分析的重點在于由增量幅度與整體可靠性變化幅度的關(guān)系,這顯然與式(3) 的Bi有關(guān).

考慮余子式一般情形,令U=Mn,1,可展開整理為

其中,Ci,j為元素Ui,j的代數(shù)余子式,規(guī)模為(n-2)×(n-2).

對矩陣A=I -Q,可整理為

其中,Di,j為元素Ai,j的代數(shù)余子式,規(guī)模為(n-1)×(n-1).綜合式(5) 和式(6),對式(3) 加以改進(jìn),得到

此為單組件增量式演化后的敏感度,推導(dǎo)過程這里不再展開.可知計算過程非常復(fù)雜,并且時間復(fù)雜度在O(n3) 量級,這意味著隨著轉(zhuǎn)移矩陣Q規(guī)模的增長,計算負(fù)荷問題將凸顯.

2 軟件結(jié)構(gòu)的演化

區(qū)別于簡單增量式演化,本節(jié)討論更一般的情形.軟件系統(tǒng)在發(fā)布后會不斷調(diào)整其體系結(jié)構(gòu)以適應(yīng)需求或者運行環(huán)境的變化.這些調(diào)整即演化行為可能來自軟件的自適應(yīng)機(jī)制(例如服務(wù)組件的動態(tài)匹配),也可能來自軟件版本的更新(出于功能修補(bǔ)、性能優(yōu)化等目的).站在結(jié)構(gòu)度量的角度,我們希望可以完整跟蹤軟件的演化行為,以確定軟件某些關(guān)鍵性能指標(biāo)(可靠性、可用性、可維護(hù)性等) 的變化趨勢,并定位那些導(dǎo)致整體性能抖動劇烈的單個組件或局部結(jié)構(gòu)模塊.

以上一節(jié)ESA 系統(tǒng)為例.圖2 標(biāo)注了各組件可靠度及組件間轉(zhuǎn)移概率,數(shù)據(jù)來自文獻(xiàn)[17].假設(shè)該軟件在運行期間發(fā)生了演化,其主要模塊Parsing、Computing 及Formatting 得到了更新,同時系統(tǒng)結(jié)構(gòu)也因為組件接口更迭和局部性能優(yōu)化發(fā)生改變.圖3 表示其在演化發(fā)生后的情形.陰影表示組件N1～N3已被更新,可靠度也相應(yīng)發(fā)生變化:解析模塊因算法改進(jìn)可靠度得以提升(增加0.04);格式模塊因接口增加導(dǎo)致可靠度下降(減少0.02);組件N5作為N2的復(fù)制被加入到結(jié)構(gòu)中,用來分擔(dān)系統(tǒng)實時計算的壓力,并且為了進(jìn)一步優(yōu)化性能,N2與N5耦合為并行結(jié)構(gòu),同時N2(及N5) 因為并行功能擴(kuò)展導(dǎo)致其可靠度降低(均減少0.01).

圖2 ESA 軟件組件遷移圖(標(biāo)注可靠性信息)Fig.2 The component transition diagram of ESA software (labeled with reliability information)

圖3 較圖2 有多處更改,這些更改并非同時發(fā)生,而是遵循一個演化過程來進(jìn)行.過程中的每一步都由一個或多個操作組成,而這些操作(下文稱演化原子操作) 都會成為影響系統(tǒng)整體可靠性的小的變量.如果忽略過程直接使用DTMC 模型,對軟件開發(fā)并沒有實際的指導(dǎo)意義.我們認(rèn)為針對軟件演化的可靠性分析應(yīng)兼具宏觀與微觀的視角:微觀上,定位演化過程中這些小粒度原子操作以及它們所對應(yīng)的組件模塊和局部結(jié)構(gòu),可暴露軟件系統(tǒng)演化時的潛在風(fēng)險,將有利于分析影響整體可靠性的關(guān)鍵因素;宏觀上,將過程看作操作序列的累積,可用于分析完整演化進(jìn)程的可靠性趨勢.

圖3 ESA 軟件組件遷移圖(演化后)Fig.3 The component transition diagram of ESA software (after evolution)

滿足上述需求的前提是對演化過程的理解與表達(dá).事實上,追蹤和描述軟件系統(tǒng)中模塊及模塊間關(guān)系的變化過程一直是軟件可視化技術(shù)的研究熱點,可視化技術(shù)可以幫助開發(fā)者兼具靜態(tài)、動態(tài)及演化的視角以分析結(jié)構(gòu)和代碼[19].但當(dāng)前可視化技術(shù)僅聚焦于多視角分析,因計算和描述能力的限制尚無法揭示演化過程中的潛在效用變化,故仍然不適用于完整分析軟件演化過程[20].圖4 給出了一個針對圖3 演化版本的系列圖,使用了可視化技術(shù)中常見的小格圖[21](Small multiples) 表達(dá).

小格圖顯示了軟件結(jié)構(gòu)沿時間t連續(xù)變化的過程:在t=2 時刻,模塊N1、N3已經(jīng)完成了更新;在t=3 時刻加入了N2的復(fù)制N5,同時也相應(yīng)增加了模塊間關(guān)系(邊).有時為了清晰反映單步變化過程,也可以在兩個時刻間插入中間態(tài)(可使用動畫),例如這里的t=2→3.需要說明的是,即使插入中間態(tài)的動畫過渡,也無法準(zhǔn)確描述出潛在關(guān)鍵信息.如這里t=4,相較于前一時刻新增了模塊N2與N5之間的并行關(guān)系,但是這種特殊的耦合結(jié)構(gòu)在圖中沒有明確表達(dá),而這又是影響系統(tǒng)整體可靠性的關(guān)鍵信息.諸如小格圖(包括其改進(jìn))、Difference maps[22]以及Glyphs[23]等可視化方法,在描述演化進(jìn)程時都存有類似問題,并且它們都無法回避占用計算空間大、仍需手動對圖識別比較等缺點.

下節(jié)將引入一種代數(shù)方法,它更輕量化易于描述和計算,能準(zhǔn)確表達(dá)演化步驟和過程.

圖4 ESA 軟件演化過程的小格圖表示Fig.4 Evolution process of ESA software represented by the small multiples

3 代數(shù)方法

將圖2 所示的軟件結(jié)構(gòu)定義為三元組〈C,O,Ω〉,其中,C為組件模塊集,O為使用連接子集,Ω為模塊關(guān)系集.它的完整含義如下:

稱上述三元組〈C,O,Ω〉為ESA 軟件結(jié)構(gòu)代數(shù)模型,其中關(guān)系集Ω含6 個代數(shù)表達(dá)式.這里沿用文獻(xiàn)[24]的定義,將連接子定義為代數(shù)算子形式,關(guān)系集即為由組件模塊和代數(shù)算子連接而成的表達(dá)式集合.此例中僅含激發(fā)算子⊕,它被用來表述組件模塊間最基本的交互方式.如Ω中的第1 個表達(dá)式Role1=N1⊕N2,其涵義為N1對N2進(jìn)行了一次激發(fā),激發(fā)動作完成后,系統(tǒng)執(zhí)行穩(wěn)態(tài)將由N1遷移至N2.更多的算子可參考筆者前期所做的工作[25].

作為對軟件體系結(jié)構(gòu)的高度抽象,代數(shù)模型優(yōu)勢在于輕量化和可計算性方面.當(dāng)相關(guān)參數(shù)信息完整時,使用現(xiàn)有形式語言分析技術(shù)對關(guān)系集(即表達(dá)式集) 進(jìn)行一趟掃描,即可完整計算系統(tǒng)整體可靠性數(shù)值.筆者于文獻(xiàn)[25]中驗證了一個語法分析器,其算法基于使用廣泛的LR(1) 分析,并針對代數(shù)模型進(jìn)行優(yōu)化以保證可掃描并識別出Ω中所有表達(dá)式.在此基礎(chǔ)上,圖5 給出了本文的可靠性自動分析流程.在建立代數(shù)模型之后,流程可對模型進(jìn)行預(yù)處理和掃描解析.掃描過程中每當(dāng)匹配成功一個基本結(jié)構(gòu)范式,在狀態(tài)空間對應(yīng)更新系統(tǒng)狀態(tài)節(jié)點;當(dāng)掃描結(jié)束,一個狀態(tài)空間上的DTMC 全部節(jié)點信息獲取完成,參照式(2) 即可完成一次整體可靠性計算.需要說明的是,一次可靠性計算并不意味著流程終止,每當(dāng)新的演化需求產(chǎn)生,其代數(shù)形式表達(dá)將用以更新現(xiàn)有代數(shù)模型,流程將自動重走一趟以完成針對此次演化的可靠性實時計算.

限于篇幅,對代數(shù)模型的預(yù)處理及掃描解析算法不再重述.下文詳細(xì)解釋框架中對演化處理的部分.對應(yīng)圖3,首先將ESA 軟件系統(tǒng)演化后代數(shù)模型表示如下:這里算子‖表示并行耦合關(guān)系.

圖5 面向軟件演化的可靠性分析流程Fig.5 The reliability analysis process for software evolution

如前所述,認(rèn)為從圖2 至圖3 必然經(jīng)歷一個演化過程.站在結(jié)構(gòu)分析的角度,演化過程可看成由若干原子操作組成的行為序列.為了方便討論,首先給出如下記號:

1)Ai,結(jié)構(gòu)中間版本,對應(yīng)第i步演化步驟相對前一版本Ai?1的更改,其中,A0為初始版本,An為演化完成版本;

2)Qi,對應(yīng)版本Ai的整體軟件質(zhì)量度量(這里只討論可靠性,以Ri代替);

3)Di=|Qi -Qi?1|,用來表示相鄰版本質(zhì)量之差,這里總是取正值以描述演化過程中的可靠性抖動程度.圖6 反映了上述記號之間的關(guān)系.

圖6 軟件演化過程的版本表示Fig.6 The version-expression in software evolution process

在具體演化操作方面,文獻(xiàn)[26]在軟件質(zhì)量相關(guān)度量基礎(chǔ)上給出了演化原子操作分類,但其并不適用于基于結(jié)構(gòu)分析的可靠性建模.文獻(xiàn)[7]從故障數(shù)、變動率以及人工成本等角度對演化操作進(jìn)行數(shù)據(jù)分析與度量,但其仍非面向過程的方法,無法精確描述演化行為.因此本文給出如表1 所示演化原子操作分類及定義,用以面向建模的精確性及可計算性.

表1 強(qiáng)調(diào)了演化操作定義的原子性,即操作不可再分.每種操作都將對應(yīng)更新代數(shù)模型的三個集合C、O及Ω.如增加組件AM,其對應(yīng)了組件集C中元素的增加,而移除組件間依賴RMD 會使得關(guān)系集Ω中的表達(dá)式被移除.

表1 演化原子操作分類Table 1 Classification of evolutionary atomic operations

注意到原子操作間具有較強(qiáng)關(guān)聯(lián)性,一種操作往往會關(guān)聯(lián)另一種操作,如結(jié)構(gòu)中增加了新的組件模塊,因其必然參與系統(tǒng)執(zhí)行穩(wěn)態(tài)的控制轉(zhuǎn)移,故會導(dǎo)致模塊間依賴關(guān)系的更新.單個演化步驟中不應(yīng)只對應(yīng)單個原子操作,有時也須考慮若干原子操作相關(guān)聯(lián)的情況.

結(jié)合上文演化前代數(shù)模型〈C,O,Ω〉和演化后模型〈C′,O′,Ω′〉,可對演化過程作如下描述:

其中,A6為演化完成版本.注意這里A4步完成后,應(yīng)將Ω集中所有N2及N5處替換為N2‖N5并刪除冗余項.

中間版本A1、A2及A4關(guān)聯(lián)原子操作UM,對應(yīng)簡單的增量式演化.注意除了A1外,其余不能直接套用式(4) 計算可靠性,因為版本A2、A4已經(jīng)“身處”演化進(jìn)程之中,它們均是對前一版本更改而非對初始版本更改.相對地,包括處理A5中更復(fù)雜的結(jié)構(gòu)演化情形,本文提出流程框架展現(xiàn)了良好的適用性:通過對表達(dá)式集合Ω的一趟掃描,各中間版本的計算可實時自動完成.就演化過程建模而言,代數(shù)方法相對小格圖等其它方法強(qiáng)調(diào)了過程描述的精確性與完整性.

根據(jù)上述演化模型并結(jié)合由圖2 演化至圖3 的具體數(shù)據(jù)變動,流程自動計算從A0至A6各版本系統(tǒng)整體可靠性.圖7 反映了可靠性數(shù)值在演化進(jìn)程中的趨勢,可以看到:在A4版本之前,系統(tǒng)整體可靠性維持在一個較穩(wěn)定水平;當(dāng)?shù)竭_(dá)A5版本后,可靠性數(shù)值顯著下降,這是由于并行結(jié)構(gòu)的引入使得組件間耦合度增加,從而對可靠性造成負(fù)面影響.圖8 顯示演化時的版本抖動程度,其數(shù)值意義為相鄰版本的可靠性差值:D5明顯區(qū)別于其余值,反映了由版本A4演變至版本A5的原子操作是影響整個演化過程的關(guān)鍵;D1、D2與D4對應(yīng)了簡單增量式演化(對應(yīng)UM 操作),其值一定程度上可揭示組件的重要度,與式(7) 所計算的敏感度值相似,但計算難度大幅降低.

圖7 ESA 軟件演化過程可靠性變化趨勢Fig.7 The reliability trends in evolution process of ESA software

圖8 演化版本間抖動程度Fig.8 The reliability distance between evolution versions

4 算例研究

本節(jié)使用兩個算例以驗證本文提出代數(shù)方法的有效性與實用性.

4.1 算例1

4.1.1 數(shù)據(jù)介紹及參數(shù)設(shè)置

算例1 數(shù)據(jù)來自文獻(xiàn)[27],該算例因具有典型性故被廣泛應(yīng)用于可靠性模型驗證.最近對該算例的研究仍在持續(xù),如在文獻(xiàn)[28]中被用以比較一類DTMC 模型的性能.圖9 中標(biāo)明了算例1 的可靠性相關(guān)參數(shù)設(shè)置,包括單組件Ni的可靠性數(shù)值Ri,以及組件間控制轉(zhuǎn)移概率Pi,j.圖9 含該系統(tǒng)的初始結(jié)構(gòu)設(shè)計:系統(tǒng)含15 個組件模塊,初始設(shè)計時并不含特殊結(jié)構(gòu),即組件間僅以最基本的激發(fā)方式進(jìn)行交互.為進(jìn)行算例的演化驗證,這里設(shè)定系統(tǒng)最終發(fā)布時,含有并行、容錯及調(diào)用返回三種特殊結(jié)構(gòu)類型,它們分別是:模塊N3、N4構(gòu)成并行結(jié)構(gòu)、模塊N10對N9構(gòu)成容錯結(jié)構(gòu)、模塊N11、N8以及N8、N5構(gòu)成調(diào)用返回結(jié)構(gòu).

4.1.2 方法運行及階段性結(jié)果

根據(jù)系統(tǒng)初始結(jié)構(gòu)設(shè)計,建立代數(shù)模型如下:

圖9 算例1 初始結(jié)構(gòu)與相關(guān)參數(shù)Fig.9 The reliability trends in evolution process of ESA software

經(jīng)流程框架自動掃描并計算,初始結(jié)構(gòu)整體可靠性數(shù)值為0.8762.令初始結(jié)構(gòu)版本A0為演化起點,以最終發(fā)布版本A17為演化終點,將演化過程作如下描述:

這里‖為并行算子,Ψ 為容錯算子.

中間版本A1～A15對應(yīng)單個組件的簡單增量式演化.設(shè)定因平臺遷移使用了新的事件系統(tǒng),所有組件實現(xiàn)發(fā)生變化,導(dǎo)致可靠度平均下降了0.005.版本A16、A17中使用了CM 操作,分別對應(yīng)N3、N4以及N9、N10進(jìn)行結(jié)構(gòu)耦合后的情形.表2 中列出演化過程的中間計算結(jié)果.其中各演化版本可靠性Ri的計算由流程框架自動完成,圖10 表達(dá)演化過程的可靠性趨勢.因為組件平均可靠度的降低,系統(tǒng)整體可靠性呈下行趨勢,當(dāng)?shù)竭_(dá)最低點A16版本后,因為A17中引入容錯機(jī)制的原因使得可靠性最終有所回升.

圖10 算例1 演化可靠性變化趨勢Fig.10 Reliability trends in evolution of Case 1

4.1.3 最終結(jié)果及分析

就面向過程的可靠性評價而言,本文傾向于使用類似圖10 的可靠性趨勢序列表達(dá)結(jié)果,以代替對最終版本的單次可靠性計算.除趨勢外,將演化過程序列化的另一優(yōu)勢在于敏感度分析,即指出在演化過程中造成整體可靠性抖動明顯的關(guān)鍵步驟及其背后關(guān)聯(lián)的原子操作.如代數(shù)方法描述,中間版本A1～A15對應(yīng)UM 原子操作,即單個組件更新的情形.因為組件可靠度平均下降幅度相同,故相鄰版本質(zhì)量差值D1～D15很大程度上可反映被更新組件N1～N15的重要程度.為說明其有效性,表2 中也給出了可靠性關(guān)鍵程度(Criticality) 的計算結(jié)果,它由下式定義:

其中,?Ri為單個組件Ni的可靠性變化增量,?Rsys對應(yīng)因此引起的系統(tǒng)整體可靠性增量.當(dāng)組件的平均可靠度增量幅度非常小時(≤0.005),Ci能夠近似代替敏感度Bi,而相較于Ci,計算Bi的代價通常要大的多.

圖11 中為了與前15 個D1～D15作對比,一組Criticality 值C1～ C15以曲線形式呈現(xiàn)(經(jīng)過適當(dāng)放大).觀察Criticality 曲線變化與下方的Distance 圖形基本一致.除去起始節(jié)點組件N1與終止節(jié)點組件N15外,組件N13的Criticality 值(C13=0.87296) 最大而組件N12其次(C12=0.79360),這與D13(0.00417) 及D12(0.00387) 是吻合的.這表明演化過程含多個簡單增量式演化步驟時,通過計算Distance 值(增量幅度不同時考慮Di/?Ri比值) 評估不同組件的可靠性關(guān)鍵程度是有效的.而計算Criticality 值幾乎沒有代價,它僅是為分析演化過程保留的中間結(jié)果.

圖11 體現(xiàn)了演化過程的可靠性抖動情況.可看到處于最后的D16、D17明顯高出其余Distance值一個量級,這說明涉及結(jié)構(gòu)的演化原子操作(SM、CM) 對系統(tǒng)整體可靠性的影響往往最為關(guān)鍵.其中又以D17的值最為突出,這是因為容錯結(jié)構(gòu)本身即具有高可靠特征,如果對結(jié)構(gòu)中關(guān)鍵節(jié)點(可靠性敏感的) 組件進(jìn)行容錯結(jié)構(gòu)的演化設(shè)計,可對系統(tǒng)整體可靠性提升起顯著作用.從架構(gòu)設(shè)計者立場,需要與編碼人員一起嚴(yán)格監(jiān)控以使演化過程中的質(zhì)量抖動幅度被限制在合理的區(qū)間內(nèi).序列化的代數(shù)建模方法針對了上述需求,并且方法本身是簡潔、易用的.

表2 算例1 演化過程計算結(jié)果Table 2 Evolution process calculation results of Case 1

圖11 算例1 版本抖動與組件關(guān)鍵程度Fig.11 Version distance and component criticality of Case 1

4.2 算例2

4.2.1 數(shù)據(jù)介紹及參數(shù)設(shè)置

算例2 來自一個大型交換機(jī)系統(tǒng)的軟件結(jié)構(gòu)設(shè)計,它最早被文獻(xiàn)[13]所引用,并同樣因其結(jié)構(gòu)具有代表性多被用來比較和驗證結(jié)構(gòu)化軟件可靠性模型.在文獻(xiàn)[29]中,作者對該算例從相關(guān)性、敏感度等角度進(jìn)行了深入分析與討論,并與一類基于路徑可靠性模型作出比較.圖12 中標(biāo)明了算例2 的可靠性相關(guān)參數(shù)設(shè)置,同時也給出了系統(tǒng)的初始結(jié)構(gòu)設(shè)計.該系統(tǒng)含有10 個組件模塊,初始設(shè)計不含有特殊結(jié)構(gòu).在算例2 的演化驗證中,將重點關(guān)注組件間的控制轉(zhuǎn)移變化對可靠性影響.這里設(shè)定系統(tǒng)結(jié)構(gòu)關(guān)鍵組件N1、N2及N5在最終發(fā)布前控制轉(zhuǎn)移分支概率發(fā)生變化,在演化過程中將對這一行為建模并分析分支的可靠性敏感度.

4.2.2 方法運行及階段性結(jié)果

根據(jù)系統(tǒng)初始結(jié)構(gòu)設(shè)計,可建立代數(shù)模型如下:

圖12 算例2 初始結(jié)構(gòu)與相關(guān)參數(shù)Fig.12 The reliability trends in evolution process of ESA software

對此算例設(shè)定二階段演化過程:首先在版本A1～A10中使組件N1～N10可靠度依次下降0.01(對應(yīng)UM 原子操作),通過實時計算版本可靠性及相鄰版本Distance 值,識別出結(jié)構(gòu)中的關(guān)鍵組件節(jié)點;其次對關(guān)鍵組件,調(diào)整與之相關(guān)的控制轉(zhuǎn)移概率(對應(yīng)UMD 原子操作),以分析節(jié)點轉(zhuǎn)移分支的偏重對整體可靠性影響的程度.演化過程如下:

根據(jù)設(shè)定,前10 個中間版本A1～A10被看作第一階段,后4 個版本A11～A14看作第二階段.參照表3 中各版本可靠性數(shù)值,圖13 給出了演化過程的整體趨勢.可看到系統(tǒng)可靠性在第一部分呈逐步快速下降趨勢,符合預(yù)期.圖14 中給出了相應(yīng)Distance 值D1～D10,經(jīng)比較易知軟件結(jié)構(gòu)中N1、N2、N3、N5及N10屬于相對可靠性敏感的重要節(jié)點組件.其中,D5(0.01074) 甚至超過了起始節(jié)點D1(0.00837) 及終止節(jié)點D10(0.00789),說明其在結(jié)構(gòu)中的關(guān)鍵程度.同樣地,為了說明D1～D10值的有效性,在圖14 中也附以Criticality 值C1～C10(經(jīng)放大處理),觀察易知其曲線與Distance 圖形基本保持一致,說明使用Distance 值分析組件節(jié)點的可靠性敏感度是有效的.

圖13 算例2 演化可靠性變化趨勢Fig.13 Reliability trends in evolution of Case 2

4.2.3 最終結(jié)果及分析

在第一階段演化過程計算結(jié)果基礎(chǔ)上,從中篩選出可靠性敏感程度最高的組件N1、N2及N5.因在這些組件上的變動更易于引發(fā)明顯的可靠性抖動,利于于后續(xù)演化分析.

第二階段中有4 個中間版本A11～A14,分別對應(yīng)以N1、N2及N5為分支節(jié)點的UMD 原子操作.3 個節(jié)點都具有代表性:N1處于特殊的起始位置,N5具有最大Distance 值,而N2是結(jié)構(gòu)內(nèi)部僅次于N5 的可靠性關(guān)鍵節(jié)點.

對UMD 操作分析的困難在于多參數(shù)情形.從版本A11開始,設(shè)定N1的實現(xiàn)發(fā)生更改,將直接影響其與后續(xù)組件N1～N4之間的控制轉(zhuǎn)移關(guān)系,表現(xiàn)為相關(guān)分支概率的變化.在A11步,兩組激發(fā)表達(dá)式被關(guān)聯(lián)UMD 操作,使得分支轉(zhuǎn)移概率比值P1,2:P1,3:P1,4由0.6:0.2:0.2 更新為0.5:0.2:0.3,注意只有P1,2與P1,4作為參數(shù),而P1,3保持不變.圖15(a) 中曲線II 表達(dá)了版本可靠性R11在P1,2與P1,4作為參數(shù)情況下所有可能的取值.當(dāng)P1,4所占比越大時,R11值越高,實際A11版本較A10版本提升了可靠性.不考慮演化,曲線I 給出Rsys值與參數(shù)P1,2、P1,4之間的關(guān)系,它與曲線II 一致,說明了在演化過程中按曲線II 分析轉(zhuǎn)移概率影響是有效的.

圖14 算例2 版本抖動與組件關(guān)鍵程度Fig.14 Version distance and component criticality of Case 2

在A12步,比值P1,2:P1,3:P1,4經(jīng)演化更新為0.4:0.3:0.3.這一步中P1,2與P1,3作為參數(shù),P1,4保持不變.圖15(b) 中曲線IV 對應(yīng)R12所有可能取值,易知R12隨著P1,3占比增大而提升.同樣地,曲線III 表達(dá)了Rsys與參數(shù)P1,2、P1,3之間的關(guān)系,作為參照它與曲線IV 一致.版本A11、A12的兩步演化在現(xiàn)實情況下可能只對應(yīng)一步(由0.6:0.2:0.2 至0.4:0.3:0.3),增加1 個可變參數(shù)無疑加大了分析難度,亦不能給出兩兩比較的直觀結(jié)果.故這里設(shè)定演化操作可進(jìn)一步細(xì)分(如此處A11、A12),將更改限制在僅2 個參數(shù)可變的情況.組件節(jié)點擁有超過3個及以上的控制轉(zhuǎn)移分支都可按此分析.

根據(jù)表3,R13值較前一版本增加,說明對節(jié)點N2而言,后續(xù)控制轉(zhuǎn)移偏重N5分支則有利于可靠性提升.而R14值較前減少,說明對節(jié)點N5,控制轉(zhuǎn)移偏重N7將導(dǎo)致可靠性下降.通過觀察圖14中D11～D14部分,第二階段整體可靠性抖動程度相對平緩,但其中,D14(0.00497) 明顯大于D11(0.00234)、D12(0.00185) 及D13(0.00205).版本A14對轉(zhuǎn)移概率的更改幅度與之前版本相近,其影響程度卻明顯放大,從另一角度驗證了節(jié)點N5在整體結(jié)構(gòu)中是最關(guān)鍵的,這與文獻(xiàn)[29]中敏感度分析結(jié)論一致.

目前可靠性模型對控制轉(zhuǎn)移分支敏感度的分析仍然缺乏有效的方法,涉及對多參數(shù)的分析往往較為困難.一類基于路徑的可靠性模型[24,26,29]中使用了多個執(zhí)行路徑來對應(yīng)節(jié)點存有多個控制轉(zhuǎn)移的情形,但是這種方法計算流程繁瑣,不能簡明分析關(guān)鍵節(jié)點組件的分支敏感度.本文在序列化的演化過程中使用原子操作細(xì)化描述控制轉(zhuǎn)移概率的變化,每一步操作均通過實時掃描代數(shù)模型計算出可靠性變化,可監(jiān)測出影響整體可靠性的關(guān)鍵步驟,具有可操作性與現(xiàn)實意義.

表3 算例2 演化過程計算結(jié)果Table 3 Evolution process calculation results of Case 2

圖15 可靠性受分支概率參數(shù)變化的影響Fig.15 Reliability as a function of branch probability

5 結(jié)論

面向演化過程建模與分析一直是軟件工程領(lǐng)域的難點問題.使用代數(shù)方法描述軟件結(jié)構(gòu)是精確無二義的,且相較于圖形工具在可計算性上具有優(yōu)勢,適用于可靠性實時分析、計算.將演化過程序列化是本文的創(chuàng)新點.演化各中間版本(步驟) 可獨立建模,中間版本前后銜接為完整的演化過程,從而建立起過程化分析模型.本文方法的有效性與易用性得到了算例驗證,下一步,將在開源軟件項目上開展實證研究,通過對軟件更迭版本依序構(gòu)建演化代數(shù)模型,并基于設(shè)計文檔、源代碼及代碼度量數(shù)據(jù)獲取可靠性建模參數(shù),用以計算和分析可靠性變化趨勢,以及揭示軟件版本演化中的規(guī)律性特征和一些重要、易被忽視的中間環(huán)節(jié).