基于構件的可信軟件系統冗余機制及可靠性分析①

郁 湧,黃宇鑫,陳 浩

1(云南大學 軟件學院,昆明 650091)2(云南省軟件工程重點實驗室,昆明 650091)

當今,以高速通信、海量存儲和高性能計算為核心的信息基礎設施已經廣泛深入地滲透到經濟、政治、軍事和社會文化生活的各個層面,成為現代生產力發展和人類文明進步不可或缺的強大工具.在眾多應用背景的推動下,軟件的復雜度和規模都在以前所未有的速度在不斷延伸,在金融、國防、政府和通信等關鍵領域的各種復雜應用需求背景下,軟件是否可信已經成為衡量軟件系統的重要指標.然而,作為計算機技術的核心和基礎之一的軟件系統,其生產現狀和質量一直不能令人滿意,尤其是應用于航空航天、核電及國防等領域的安全關鍵軟件系統,其失效常常會對人類和環境造成嚴重的乃至災難性的后果.早在1991年,Laprie就從安全關鍵系統的研究出發提出了軟件可依賴性(Dependability)的概念[1].1997年美國國家科學技術委員會在《高可信系統的研究挑戰》中明確提出了高可信性(High Confidence)的概念[2].我國學者陳火旺、王戟等認為高可信軟件在系統提供服務時應能滿足一系列可靠安全性、實時性、可靠性、容錯性、保密性等關鍵性質[3].可信軟件作為軟件領域最具挑戰性和價值的研究課題之一,引起了國內外學者的高度重視.

軟件容錯是提高系統可信性的一種實現技術之一,其相關的研究方面主要分為兩大類:軟件冗余和時間冗余[4-6].軟件冗余是在系統設計時,增補一些部件或模塊,使得即使其中一個部件發生故障,而整個系統照樣完成規定的任務.從冗余的范圍來看,分為元件冗余、部件冗余、子系統冗余等.從部件聯接形式來分,可分為并聯、旁聯、表決系統等.多版本編程利用完成同一功能的不同實現之間的多樣性互補容錯,也是一種常見的軟件冗余容錯方法.而時間冗余方面則是基于失敗重做(Retry-on-failure)的思想,如在系統進行設計和實現時設置檢查點和回滾機制,當發生故障就回滾到適當的檢查點重新執行[7].Reis等人在編譯器級別通過指令復制和合并對軟件進行版本冗余從而可以在設置的同步點檢查指令的一致性,具有較好的容錯效果和執行效率,但其實現較為復雜[6].文獻[8]通過動態監控和回滾技術,建立了合適的還原點來對系統進行監控,使系統能夠及時恢復到預先的還原點.文獻[9]為提高軟件的可靠性和生存能力,分析了模塊化對可靠性的影響提出一種基于進化計算的可進化模塊冗余軟件混合容錯模型.文獻[10]設計了一種基于網絡控制的可編程控制器冗余系統,使得雙機軟件冗余系統更加穩定.文獻[11]給出了一種基于三取二冗余結構的安全計算機系統.

在現代軟件工程技術中,系統構件化已經成為軟件技術總體發展趨勢之一[12],基于構件的軟件開發技術尤其得到了廣泛發展[13].為了能夠提高基于構件的軟件系統的可信性,本文在分析系統結構冗余和可信性關系的基礎上在基于構件的軟件系統中提出一種構件結構冗余的方法并對其可靠性進行性能分析.

1 軟件結構冗余及其對可信性的影響

軟件系統的可信性質是指該系統需要滿足的關鍵性質,包括可靠性(reliability)、可靠安全性(safety)、保密安全性(security)、生存性(survivability)、容錯性(fault tolerance)等等,當軟件一旦違背這些關鍵性質會造成不可容忍的損失時,稱這些性質為系統的高可信性質[3].構建的軟件系統不夠可信的原因就是故障的存在,故障的存在說明軟件系統內部有缺陷的部件.軟件系統故障的種類很多,退化故障就是其中常見的一種.當系統內的一個部件發生失效,不再工作了,則認為發生了退化故障.軟件系統中的退化故障可能是活動的,也可能是休眠的;可能是瞬時性的,也可能是永久性的故障.為了降低軟件故障的發生率,如果能夠識別或者在進行系統設計時確定系統中可能發生故障的關鍵部件,預先進行調節,并確保失效部件的影響不會帶來使系統發生失效的輸出,系統本身就不會失效.

軟件系統需要對退化故障進行處理,系統的容錯是處理退化故障的方法之一.容錯性就是指軟件在故障出現時保證提供服務的能力,對退化故障進行容錯的一種處理方式就是依靠冗余.所謂軟件的冗余技術主要就是指在軟件設計和實現中,除了完成系統本身所需的功能外,為了能夠提高系統的性能及可靠性等而額外增加一些合理的部件和程序代碼的技術.

基于構件的可信軟件系統中,構件是具有一定規模、相對獨立、可替換的單元,它具有較穩定的組成模式,完成一項確定、可區分的功能,并遵從和提供一套接口以及這些接口的實現.構件是軟件系統的構成要素,同時也是軟件的承載體,一個構件應該包括兩個部分:接口和實現.其中接口部分定義了構件所提供的功能并規范了功能的使用方法;而實現部分包括了構件所能提供的一系列相關操作.在基于構件的可信軟件結構設計中,構件冗余就是對可能會出現故障的關鍵構件進行多個備份;但是,冗余并不意味著簡單的備份,冗余意味著一個構件有多個功能相同的構件是可用的,超過提供服務所需的部件數量,當其中一些構件發生失效時,其他的冗余部件可以繼續提供服務,從而保證軟件系統運行的可信性.在系統中,如果兩個構件A1和構件A2所實現的功能和對應接口完全一樣,則稱構件A1和構件A2是相互冗余的構件,相互冗余的構件的規約和消息傳遞機制必修一致.一個存在冗余構件的系統在合理調用的情況下不僅不會影響系統的實現,而且會提高系統的容錯能力,滿足系統可信性的要求.相同冗余構件的運行要在確定的系統環境和相同輸入的情況下,才能得以正確運行;否則,存在外界的影響會產生錯誤的結果.當一個構件產生故障時,繼續提供服務的構件需要進行數據和環境的檢測和重新配置來保證系統運行的一致性.

為了保證基于構件的可信軟件系統中的構件冗余結構的可靠性在運行過程中能夠得到合理有效地驗證,需要具有一個稱之為信任根的構件,信任根構件是系統的可信啟動模塊,可以存放構件的標識和編號、構件的信息摘要以及構件冗余信息的存儲等重要數據,同時也可以用來對冗余構件的運行情況就行實時檢測,從而判斷各個構件運行是否正常.基于冗余機制的可信軟件框架如圖1所示.

圖1 基于冗余機制的可信軟件框架

2 單個構件的雙模冗余結構及性能分析

一個具有雙模冗余結構的系統是指在系統中存在兩個完全冗余的構件;在此系統中,兩個相同構件并行運行,并將結果進行檢測.兩個在相同輸入和相同環境的情況下運行,所產生的運行結果應該是一樣的.一種普遍使用的簡單雙模冗余結構如圖2所示.

圖2 構件的雙冗余結構

在基于構件的軟件系統中,對于系統中的關鍵或者核心構件,為了保證運行過程中所產生的故障能夠被及時發現,提高系統容錯階段的檢測能力,可以對其進行雙模冗余結構設計.

在進行雙模冗余結構的設計時,兩個完全冗余的構件A1和構件A2的輸入必須相同,即在進行消息傳遞時,需要把同一消息傳遞給冗余的構件.雙模冗余結構的錯誤檢測是通過比較兩個冗余構件的輸出結果來完成的.如果輸出不同,那么就是發生了錯誤.但是,通過錯誤檢測無法確定是哪個構件發生了故障.如果輸出的結果完全相同,則說明系統沒有發生故障,此時只需要把其中一個輸出傳遞給下一個構件即可.

一個雙模冗余結構會對系統的可信性產生影響,因為單個構件的運行結果無論是否正確都不可能完成故障和錯誤檢測,錯誤狀態產生而未被檢測出來,將會給系統帶來無限的負面影響,而雙模冗余結構是一種最簡單提供了錯誤檢測的能力的方法.

雙模冗余結構的可靠性分析:假設兩個完全冗余的構件A1和構件A2獨立運行,兩個構件產生故障的概率相同都為p,由于構件A1和構件A2建立的是個并聯系統,則系統運行中檢測出故障的概率為兩個完全冗余的構件A1和構件A2運行中,一個產生故障而另一個沒有產生故障而整體被檢測成產生故障的概率為

從雙模冗余結構的性能分析結果可以看出,該結構與不用冗余結構相比可能會增加系統整體被檢測出故障的概率,因為無法判斷哪個構件產生故障,所以一個構件故障而另一個沒有故障產生時的結果會判定為系統產生故障.

對于雙模冗余結構,如果在系統運行過程中能夠收集系統產生故障的可能環境或情況,在對應情況下才進行兩個完全冗余的構件的調用,否則只需要進行其中一個構件的調用,這樣就可以提高運行效率.

3 組合構件的雙模冗余結構及性能分析

軟件系統中的構件可能具有多種關系,比如并聯、串聯等,對于多個需要進行冗余處理的關鍵構件,為了能夠得到更好的效果,可以對其進行冗余的組合.本論文主要對兩個構件的并聯、串聯的組合關系進行分析,對多個構件的關系可以進行相似處理.

3.1 兩個串聯構件的雙模冗余方式及性能分析

對于兩個串聯構件的冗余主要有兩種方式,如圖3和圖4所示,圖中相同冗余構件用不同的下標表示,如構件A1構件A2和構件A3是三個相同的冗余構件,構件B1和構件B2是兩個相同的冗余構件,其他以此類推.

對于串聯構件雙模冗余方式一,兩個構件串聯運行之后再檢測其運行結果是否相同來確定是否有故障發生,把兩個構件看成一個整體來檢測,檢測數量會變少,但是就算檢測出存在故障,也不知道是哪個構件造成的故障.

圖3 串聯構件雙模冗余方式一

圖4 串聯構件雙模冗余方式二

若構件A1和構件A2的故障概率為p1,構件B1和構件B2的故障概率為p2,且構件A1和構件A2、構件B1和構件B2的運行都是獨立的,則構件A1和構件B1串聯時產生故障的概率為:

此時,構件A1、構件A2、構件B1和構件B2中只要有一個構件產生故障,檢測器就是認為系統發生故障,其概率為:

對于串聯構件雙模冗余方式二,兩個串聯的構件分別運行之后就檢測其運行結果是否相同來確定是否有故障發生,把兩個構件分開來進行檢測,檢測數量會增加,可以根據檢測結果知道是構件A1或A2還是構件B1或B2造成了系統故障.

對應方式2的串聯構件雙模冗余,若構件A1和構件A2,構件B1和構件B2分別進行檢測,運行中檢測出故障的概率分別為

對于兩個冗余檢測之間是串聯關系,此時,構件A1和構件A2檢測出故障就不用運行構件B1和構件B2,因此構件B1和構件B2也不需要檢測.只有構件A1和構件A2運行無故障時才需要運行構件B1和構件B2并對其進行檢測.因此,運行中檢測出產生故障的概率為:

從上可知道,串聯構件采取哪種冗余方式與串聯的兩個構件產生故障的概率有關,可以根據情況進行選擇.

3.2 兩個并串聯構件的雙模冗余方式及性能分析

對于兩個并聯構件的雙模冗余主要有兩種方式,如圖5和圖6所示.

對于并聯構件雙模冗余方式一,兩個并聯關系的構件A1和構件B1以及并聯關系的構件A2和構件B2先并聯運行,之后再把兩組并聯構件運行的結果進行檢測來確定是否有故障發生,此時把兩個并聯關系的構件看成一個整體來檢測,檢測數量會變少,但是只要構件A1、構件A2、構件B1和構件B2中一個構件發生故障,都會認為系統出現故障.就算檢測出存在故障,也不知道是構件A1或A2還是構件B1或B2造成的故障.

圖5 并聯構件雙模冗余方式一

圖6 并聯構件雙模冗余方式二

若構件A1和構件A2的故障概率為p1,構件B1和構件B2的故障概率為p2,且構件A1、構件A2、構件B1和構件B2的運行都是獨立的.雖然構件A1和構件B1是并聯關系,但是其中只要一個產生故障,均認為系統產生故障,因此構件A1和構件B1并聯時產生故障的概率為:

此情況下,兩組并聯構件運行結果不一致,經檢測器檢測認為出現故障的概率為:

對于并聯構件雙模冗余方式二,先對構件A1和構件A2以及構件B1和構件B2進行冗余處理,構件A1和構件A2以及構件B1和構件B2的故障檢測互不影響,根據各次檢測的結果來確定是那組構件產生故障.

若構件A1和構件A2的故障概率為p1,構件B1和構件B2的故障概率為p2,且構件A1、構件A2、構件B1和構件B2的運行都是獨立的,則構件A1和構件A2并聯時產生故障的概率為:

此情況下,只要一個檢測器檢測出故障,均認為出現故障,其概率為:

4 構件的三取二冗余結構及其擴展

4.1 三取二冗余結構

構件的雙模冗余結構只能檢測出系統是否出現故障卻不能判斷具體哪個構件出現故障,而三取二冗余結構是一種基于三取二表決原理的三模冗余架構,如圖7所示.

圖7 構件的三取二冗余結構

三取二冗余結構不僅能夠檢測出系統的故障,而且能夠按照表決原理來確定哪個出現故障,其檢測和處理有2種方式.

方式一是先只運行其中的兩個冗余構件,如果運行結果一致則直接運行下一構件;如果運行結果不一致,說明至少其中一個構件產生故障,此時再運行第三個冗余構件,若三個冗余構件運行結果中有兩個結果是相同的,則把它當成正確結果傳輸給下一個構件,否則就認為產生了故障.

方式二是在該結構中,同時運行三個冗余構件,當且僅當 2個以上的構件同時出現故障時( 發生概率較低)才會認為出現故障,即三個冗余構件運行結果中,只要有2個及以上結果一致就把該結果當成正確結果傳輸給下一個構件.

三取二冗余結構不僅可以有效保證冗余構件的退化故障而導致的錯誤能夠被檢測出來,而且在故障產生的情況下判斷正確的運行結果.這一特點與雙模冗余結構中的錯誤檢測形成鮮明對比,如果三個冗余構件中只有一個產生故障,三取二冗余結構都可以檢測出來并給出正確的運行結果,因此,三取二冗余結構可以對軟件的故障結構進行屏蔽.

在三取二冗余結構中,假設三個完全冗余的構件A1、構件A2和構件A3獨立運行,它們產生故障的概率相同都為p,構件A1、構件A2和構件A3建立的是并聯系統,則系統運行中檢測出故障的概率為此時出現故障被檢測出來的概率將會大幅增加.

三個完全冗余的構件A1、構件A2和構件A3運行中,三取二冗余結構被認為產生故障的概率為

4.2 三取二冗余結構的擴展

為了提高系統可靠性,也可采用四重化冗余結構和二乘三取二冗余結構.四重化冗余結構主要使用四個完全相同的構件來搭建冗余結構,通過一定的邏輯關系來使可信性全面提高的一種技術,其如圖8所示.

圖8 四重化冗余結構

四個構件被分為兩組,每組有兩個構件和一個檢測器,整個四重化冗余結構即由這兩個相同的系組成,每個系的運行與檢測方式與雙模冗余結構相同.在系統運行過程中,只有一系有計算輸出而另一系為備用,當工作的系失效之后,才進行不同系之間的切換.

二乘三取二冗余結構原理與四重化冗余結構相似,冗余系統也由兩個系組成,只不過每個系就是一個三取二冗余結構.

四重化冗余結構和二乘三取二冗余結構能夠提高系統的可靠性和安全性,但是大量冗余結構也會使得冗余機制實現起來比較復雜,增加了系統運行的成本.

對于三取二冗余結構也可以擴展成為n-模冗余的結構,如圖9所示.該結構運行結果的檢測和正確運行結果的判定方式與三取二冗余結構相似,可以采取少數服從多數原則.

圖9 構件 n 模冗余結構

同時,對于三取二冗余結構和n模冗余結構都可以考慮構件之間的并串聯關系,但是具體分析方式與上面的原理相似,故在此就不在重復分析.

在具有冗余機制的可信軟件系統中,可以采用奇偶校驗、錯誤檢測、完整性檢測和HASH函數等方式來對冗余構件運行結果進行檢測,同時根據檢測的結果來確定構件在運行過程中是否存在失效問題.當系統中的一個構件產生故障或者失效時,可以利用恢復塊策略、檢查點技術等方法來對其進行替換或者恢復,從而保證系統的可信性.

5 檢驗與分析

如果一個基于構件的軟件系統中核心構件有兩個,分別為構件A和構件B,它們在運行過程中產生故障的概率分別為pA=0.3和pB=0.2,則當對其進行單個構件的雙模冗余結構、兩個串聯構件的雙模冗余方式(方式一、方式二)以及三取二冗余結構時,其冗余系統對應的概率如表1所示.

從表1中可以看出,在不同構件發生故障的情況下,單個構件的雙模冗余結構和兩個串聯構件的雙模冗余方式雖然不能確定系統中哪個構件產生了故障,但是能夠提高故障概率檢測的效果,而三取二冗余結構能夠很好地提高系統的可靠性,降低系統發生故障的概率.

表1 不同冗余模式下的概率對應值

6 結論

可信軟件作為計算機軟件研究領域最具價值和最具挑戰性的核心課題之一,引起了國內外政府組織、科學界和工業界的高度重視.我們構建的軟件系統不夠可信的原因就是故障的存在,故障的存在說明軟件系統內部有缺陷的部件.為了降低軟件故障的發生率,同時能夠檢測出系統是否產生故障和確定哪些部件產生故障可以采用系統的容錯的方法,而對系統故障進行容錯要依靠冗余.為此,本文在基于構件的可信軟件結構設計中加入冗余機制,也就是對可能出現故障的關鍵和核心構件進行冗余處理,使得當冗余中的其中一些構件發生失效時,其他的冗余部件可以繼續提供服務,從而保證軟件系統運行的可信性.

1 Laprie JC.Dependability:Basic Concepts and Terminology.Vienna:Springe-Verlag,1991.

2 NSTC. Research challenges in high confidence systems.Proceedings of the Committee on Computing,Information,and Communications Workshop.1997.

3 陳火旺,王戟,董威.高可信軟件工程技術.電子學報,2003,31(A12):1933–1938.

4 Saha GK. Software based fault tolerance:A survey.Ubiquity,2006,7(25):1–15.

5 Reis GA,Chang J,Vachharajani N,et al. Softwarecontrolled fault tolerance.ACM Transactions on Architecture and Code Optimization,2005,2(4):366–396.[doi:10.1145/1113841]

6 Reis GA,Chang J,Vachharajani N,et al.SWIFT:Software implemented fault tolerance.Proceedings of the International Symposium on Code Generation and Optimization.Washington DC,USA.2005.243–254.

7 Xie ZP,Sun HY,Saluja K.A survey of software fault tolerance techniques.http://www.pld.ttu.ee/IAF0030/Paper_4.pdf.[2011-05-22].

8 Sathre J,Zambreno J.Automated software attack recovery using rollback and huddle.Design Automation for Embedded Systems,2008,12(3):243 –260.[doi:10.1007/s10617-008-9020-4]

9 何加浪,張琨,孟錦,等.可進化模塊冗余軟件混合容錯模型.南京理工大學學報,2012,36(2):272–277,284.

10 張立眾.一種雙總線雙控制器軟件冗余系統的設計.陜西理工學院學報 (自然科學版),2014,30(3):41–46.

11 黃濤,陳祥獻,黃海.基于三取二冗余結構的安全計算機系統.計算機工程,2011,37(18):254–257.[doi:10.3969/j.issn.1000-3428.2011.18.085]

12 楊芙清.軟件工程技術發展思索.軟件學報,2005,16(1):1–7.

13 Atkinson C,Bunse C,Gross HG,et al.Component-based Software Development for Embedded Systems. Berlin Heidelberg:Springer-Verlag,2005.