李珍，田俊峰，常卓，馬曉雪

?

基于檢查點的分布式軟件監(jiān)控與可信性評價

李珍1，田俊峰1，常卓1，馬曉雪2

（1. 河北大學(xué)計算機科學(xué)與技術(shù)學(xué)院，河北保定 071000；2. 河北大學(xué)計算機教學(xué)部，河北保定 071000）

基于檢查點的傳統(tǒng)軟件可信性評價方法以及目前針對分布式軟件的交互關(guān)聯(lián)規(guī)則，對于具有復(fù)雜交互行為的分布式軟件均不適用。采用伴隨式分布式軟件監(jiān)控機制，在節(jié)點內(nèi)織入3類檢查點，引入適應(yīng)復(fù)雜交互場景的交互關(guān)聯(lián)規(guī)則。通過將節(jié)點分解為多層模塊結(jié)構(gòu)，進行基于檢查點結(jié)構(gòu)樹的節(jié)點實例可信性以及基于節(jié)點的分布式軟件可信性評價。實驗表明能以較小的監(jiān)控開銷，更準確地評價分布式軟件實例的可信性，能夠處理無限路徑，且不存在大狀態(tài)空間問題。

分布式軟件；可信性；檢查點；交互；行為監(jiān)控

1 引言

分布式軟件系統(tǒng)在金融、交通、航空、國防、工業(yè)控制等領(lǐng)域中起著越來越重要的作用，如電信和金融領(lǐng)域的服務(wù)系統(tǒng)、交通控制系統(tǒng)以及電子商務(wù)系統(tǒng)等已廣泛滲透到人們的工作和生活中。隨著分布式系統(tǒng)的規(guī)模越來越大、功能越來越復(fù)雜，人們對其可用性、可靠性和安全性等可信性質(zhì)給予了更高的期望和要求。

在開放、動態(tài)的網(wǎng)絡(luò)環(huán)境下，多個軟件實體（如構(gòu)件、Agent、Web服務(wù)等）按需聚合，在滿足約束的條件下相互協(xié)同來完成計算任務(wù)。大型分布式軟件系統(tǒng)的深層次Bug多數(shù)是由于復(fù)雜的并發(fā)交互引起的[1]，由于功能邏輯復(fù)雜、節(jié)點間協(xié)作交互頻繁，導(dǎo)致軟件運行時行為復(fù)雜且難控。然而分布式軟件系統(tǒng)運行時，每個節(jié)點的行為和節(jié)點間的交互必然涉及一系列的信息和狀態(tài)變化，因此，通過這些信息對分布式軟件運行時行為進行分析，是監(jiān)控軟件自身狀態(tài)的有效途徑，是保證分布式軟件可信運行的重要支撐方法。

檢查點能夠保存和恢復(fù)程序的運行狀態(tài)，在進程遷移、容錯、卷回調(diào)試等領(lǐng)域有著重要的應(yīng)用。通過在軟件行為軌跡中植入若干檢查點，一些學(xué)者將檢查點應(yīng)用于軟件的行為監(jiān)控及可信性評價。楊曉暉等[2]以行為軌跡和檢查點場景來刻畫軟件行為的動態(tài)特性，通過計算系統(tǒng)調(diào)用上下文值以及構(gòu)造系統(tǒng)調(diào)用參數(shù)關(guān)系約束規(guī)則來評測行為軌跡和檢查點場景的偏離程度，構(gòu)建基于軟件行為自動機的動態(tài)可信評測模型。劉玉玲等[3]通過累計多個有疑似風險的檢查點，利用風險評估策略，判定有疑似風險的檢查點，并采用獎懲或處罰機制來得到軟件行為的可信度。田俊峰等[4]通過動態(tài)監(jiān)測行為，對軟件及其模塊在一段時間內(nèi)運行的可信狀況進行研究，提出了基于馬爾可夫的檢查點可信評估模型。然而這些方法都不是針對分布式軟件設(shè)計的，對分布式軟件復(fù)雜交互行為的可信性評價無能為力。伴隨式的分布式軟件系統(tǒng)監(jiān)控方法（如MERF[5]、PIP[1]），由于系統(tǒng)運行和監(jiān)控相互獨立、可擴展性強，廣泛應(yīng)用到大規(guī)模的分布式軟件系統(tǒng)。如何利用現(xiàn)有的分布式軟件監(jiān)控技術(shù)，基于檢查點思想，提出適用于分布式軟件行為的可信性評價方法顯得尤為重要。

近年來，分布式軟件的可信性尤其是對分布式軟件中交互行為可信性的研究受到了學(xué)者們廣泛的關(guān)注和重視。文志誠等[6]針對分布式軟件運行時的外在表現(xiàn)特征，根據(jù)具體交互場景建立貝葉斯網(wǎng)模型，在上下文環(huán)境中通過監(jiān)測相關(guān)的數(shù)據(jù)來對軟件行為運行時可信性進行分析。彭成等[7]提出了基于網(wǎng)絡(luò)化軟件交互行為的動態(tài)建模方法，給出一種基于不變量約束規(guī)則的挖掘方法，從監(jiān)控收集的軟件交互行為日志中挖掘出6類不變模式。Wang等[8]提出了構(gòu)件交互模式軟件可靠性模型，給出了不滿足隨機馬爾可夫性質(zhì)的交互模式和軟件體系結(jié)構(gòu)的表示方法。Yang等[9]提出了基于隨機Petri網(wǎng)的構(gòu)件軟件安全性模型和評價方法，在軟件設(shè)計階段對軟件安全性進行預(yù)測。Tyagi等[10]結(jié)合神經(jīng)網(wǎng)絡(luò)和模糊邏輯2種軟計算技術(shù)來評估構(gòu)件軟件的可靠性。Chen等[11]針對網(wǎng)構(gòu)軟件提出了一種基于交互的需求監(jiān)控方法，通過監(jiān)控網(wǎng)構(gòu)軟件運行時的行為來檢測與軟件需求規(guī)范的偏離，其交互規(guī)則主要考查交互執(zhí)行的先后順序。上述研究中分布式軟件交互間的關(guān)聯(lián)規(guī)則都局限于無條件下的因果和并發(fā)類型，規(guī)則的不準確、不全面無法適應(yīng)復(fù)雜交互場景的可信性分析。

基于體系結(jié)構(gòu)進行分布式軟件可信性評價的方法可以借鑒基于體系結(jié)構(gòu)的軟件可靠性模型，主要包括基于狀態(tài)和基于路徑2種方法[12]。基于狀態(tài)的模型[13,14]可以分析解決潛在的無限條路徑的系統(tǒng)，但在對復(fù)雜系統(tǒng)建模時會產(chǎn)生難以處理的大狀態(tài)空間，使計算和分析非常復(fù)雜甚至不可行?；诼窂降哪Ｐ蚚15,16]考慮程序的可能執(zhí)行路徑，因為路徑的數(shù)目受到測試期間觀察的限制，只能用來分析解決有限條路徑的系統(tǒng)。盡管這2種方法存在各自的優(yōu)缺點，但對復(fù)雜的分布式軟件，現(xiàn)有的研究很少將2種方法有效地結(jié)合起來。

針對上述問題，本文基于文獻[5]中伴隨式的分布式軟件監(jiān)控的實現(xiàn)機制，在節(jié)點內(nèi)植入檢查點，引入適應(yīng)復(fù)雜交互場景的交互關(guān)聯(lián)規(guī)則，提出了檢查點可信性及檢查點間結(jié)構(gòu)可信性的評價方法；通過將節(jié)點分解為多層模塊結(jié)構(gòu)，提出了基于檢查點結(jié)構(gòu)樹的節(jié)點及其實例可信性評價方法，并在此基礎(chǔ)上評價分布式軟件及其實例的可信性。

2 分布式軟件行為分析框架

定義1(分布式軟件) 分布式軟件定義為在由通信網(wǎng)絡(luò)互連的多個節(jié)點上通過通信和動作協(xié)調(diào)來執(zhí)行任務(wù)的軟件，表示為一個三元組=<,,>，為節(jié)點集合={Node|=1,2,3,…}，為節(jié)點間交互的集合={iaction|=1,2,3,…}，為節(jié)點間的交互規(guī)則集。分布式軟件運行時的一條運行軌跡稱為一個分布式軟件實例。分布式軟件運行時，可能有多個分布式軟件實例并發(fā)執(zhí)行。

定義2(節(jié)點) 節(jié)點定義為分布式軟件中通過通信網(wǎng)絡(luò)互連來協(xié)同工作的計算機，表示為=<,,,0,,>，其中，={cp|= 1,2,3,…}為檢查點集合；={ tr|,{1,2,…}}為轉(zhuǎn)移集合，tr表示cp向cp的轉(zhuǎn)移（，），和中元素用空格相間；為節(jié)點中檢查點間的結(jié)構(gòu)，由順序S、并行P、選擇B和循環(huán)L組合而成；為起始檢查點集合；為終止檢查點集合；={p|{1, 2,…}}為轉(zhuǎn)移tr發(fā)生概率的集合，。節(jié)點內(nèi)的一條運行軌跡稱為一個節(jié)點實例，節(jié)點實例可表示為一個順序或并發(fā)執(zhí)行的檢查點序列。分布式軟件運行時，可能有多個相同或不同的節(jié)點實例并發(fā)執(zhí)行。

節(jié)點中設(shè)置若干檢查點，通過對分布式軟件運行時檢查點及其屬性的監(jiān)控，來對節(jié)點行為的可信性進行評價。檢查點包括以下3類。

1) 功能檢查點。在節(jié)點的一個獨立基本功能結(jié)束處設(shè)置，需記錄功能檢查點的屬性信息，包括檢查點功能、上下文、參數(shù)策略、時間間距、內(nèi)存占用率、CPU占用率等。功能檢查點的設(shè)置粒度決定了分布式軟件行為檢查的粒度，也就決定了分布式軟件行為可信的程度，需要和運行效率進行平衡。

2) 分支檢查點。在節(jié)點行為分支處設(shè)置，屬性主要是分支的條件信息。

3) 交互檢查點。當分布式軟件運行需要節(jié)點間交互時，在節(jié)點每個交互發(fā)送的起始位置設(shè)置交互檢查點，來捕獲當前交互的屬性信息（交互的屬性詳見定義3）。

本文對分布式軟件節(jié)點中的檢查點結(jié)構(gòu)進行抽象，采用Petri網(wǎng)中的庫所表示檢查點，用遷移表示檢查點間的轉(zhuǎn)移。為了構(gòu)造檢查點間的結(jié)構(gòu)，定義如下基本組合：sequence、AND-split、AND-join、OR-split、OR-join，如圖1所示。若cp為cp的前一檢查點，則稱cp為cp的前向檢查點，cp為cp的后向檢查點。設(shè)檢查點cp,cp分別是cp,cp的共同前向和后向檢查點。

sequence：檢查點cp,cp,cp按順序依次執(zhí)行；

AND-split：通過tr由cp轉(zhuǎn)移到cp和cp；

AND-join：通過tr,k由cp和cp轉(zhuǎn)移到cp；

OR-split： cp通過tr轉(zhuǎn)移到cp，或通過tr轉(zhuǎn)移到cp；

OR-join：cp通過tr,k轉(zhuǎn)移到cp，或cp通過tr,k轉(zhuǎn)移到cp。

定義3(交互)交互定義為分布式軟件中節(jié)點間的一次通信，表示為=<,,,,,,,>。其中，每個元素為交互的一個屬性。和分別表示發(fā)送方和接收方；為交互時發(fā)送的消息名稱；為交互的類型，包括2種交互：同步交互和異步交互，同步交互后都跟著一個返回消息，返回接收方接收該交互的時刻，發(fā)送方收到返回消息后才繼續(xù)后面的操作，而異步消息后無返回消息；為參數(shù)策略，可以是關(guān)于單一參數(shù)的關(guān)系，采用枚舉方式列出允許出現(xiàn)的參數(shù)值，也可以是關(guān)于2個交互參數(shù)之間的關(guān)系；為交互觸發(fā)的條件；和分別表示交互的發(fā)送時刻和接收時刻，異步消息無需記錄接收時刻。一次分布式軟件運行時節(jié)點間的交互稱為交互實例。本文假定節(jié)點間交互開始后即可順利結(jié)束。

下面給出分布式軟件行為可信性分析的框架，如圖2所示。對每個節(jié)點，設(shè)置一個節(jié)點監(jiān)控器，在節(jié)點中部署監(jiān)控探針（probe），在運行時獲取檢查點的屬性值（對交互檢查點，還需獲取交互間關(guān)聯(lián)），緩存在本地存儲介質(zhì)（例如磁盤）中，經(jīng)過本地Agent異步匯集到節(jié)點分析器。對每個節(jié)點，設(shè)置一個節(jié)點分析器，負責從各節(jié)點監(jiān)控器收集該節(jié)點內(nèi)的監(jiān)控信息，實時地生成該節(jié)點實例的可信性報告，并通過記錄器將收集的監(jiān)控信息保存起來，當進行節(jié)點可信性分析時再從記錄器中提取多次運行的監(jiān)控信息。對整個分布式軟件，設(shè)置一個軟件分析器，負責從節(jié)點分析器收集節(jié)點實例可信性報告或節(jié)點可信性報告，生成分布式軟件實例可信性報告或分布式軟件可信性分析報告。節(jié)點分析器或軟件分析器都可以將可信性分析結(jié)果通過顯示/報警器顯示給系統(tǒng)管理員，當某節(jié)點或軟件分析結(jié)果為不可信時，通過顯示/報警器報警，系統(tǒng)管理和維護人員可依據(jù)分析結(jié)果對節(jié)點實施調(diào)控。

分布式軟件行為的監(jiān)控是通過編寫監(jiān)控探針，采用面向方面編程AOP編織工具[5]將監(jiān)控方面代碼注入分布式軟件檢查點處，生成具備被監(jiān)控能力的系統(tǒng)。探針代碼集中在一個獨立的文件中，較好地實現(xiàn)了方面分割，降低軟件維護的代價。同時，通過對檢查點的監(jiān)控與原軟件并發(fā)執(zhí)行，降低監(jiān)控帶來的時間開銷。分布式軟件行為的可信性分析過程由節(jié)點分析器和軟件分析器負責完成，流程如圖3所示。首先評價分布式軟件中各節(jié)點的檢查點可信性，在此基礎(chǔ)上可以得到各節(jié)點實例的可信性以及檢查點間結(jié)構(gòu)的可信性。基于節(jié)點實例可信性即可評價分布式軟件實例的可信性；基于檢查點間結(jié)構(gòu)的可信性來評價節(jié)點的可信性，據(jù)此進行分布式軟件的可信性評價。

3 分布式軟件行為的可信性分析

3.1 檢查點的可信性

檢查點的屬性根據(jù)對檢查點可信性的判斷是否確定分為2種：確定性屬性和模糊屬性。確定性屬性對檢查點可信性的判斷是確定的，一旦偏離正常值，則能直接決定檢查點的可信性不在可接受范圍，可信性的值為0或1；而模糊屬性無法用準確的數(shù)字表示，允許存在一定范圍的誤差，具有一定的模糊性，可信性的值為[0,1]。

功能檢查點中的檢查點功能、上下文、參數(shù)策略屬性屬于確定性屬性，時間間距、內(nèi)存占用率、CPU占用率屬性屬于模糊屬性；分支檢查點和交互檢查點的屬性均屬于確定性屬性。有關(guān)根據(jù)確定性屬性和模糊屬性評價檢查點可信性的方法，詳見文獻[17,18]。

交互檢查點的可信性除了取決于交互檢查點的屬性外，還取決于交互關(guān)聯(lián)的可信性。只有當交互檢查點屬性和交互關(guān)聯(lián)均可信時，該交互檢查點才可信，因此交互檢查點的可信性可表示為交互檢查點屬性的可信性和交互關(guān)聯(lián)可信性的乘積。下面重點介紹交互關(guān)聯(lián)可信性的評價方法。交互關(guān)聯(lián)規(guī)則有以下4種，如圖4所示。

1) 因果

交互1發(fā)生后的下一交互為2，則兩交互為因果關(guān)聯(lián)，包括同步因果（

2) 并發(fā)

2個或多個交互同時執(zhí)行，或至少重疊執(zhí)行。當1?[2,,2?]或2?[1?,1?]時，交互1與交互2為并發(fā)關(guān)聯(lián)，表示為1||2。

3) 互斥

當條件1滿足時，執(zhí)行交互1；當條件2滿足時，執(zhí)行交互2，則兩交互為互斥關(guān)聯(lián)，表示為+([1]1, [2]2)。

4) 重復(fù)

當條件1滿足時，循環(huán)執(zhí)行交互1，直到條件1不滿足為止，循環(huán)執(zhí)行的交互為重復(fù)關(guān)聯(lián)，表示為*[1] (1)。

分布式軟件運行時，可能有多個分布式軟件實例并發(fā)執(zhí)行。每個節(jié)點動態(tài)維護一張分布式軟件實例表，表中的一條記錄對應(yīng)一個分布式軟件實例，該表的記錄包括如下表項：標識、以該節(jié)點為接收方的交互和以該節(jié)點為發(fā)送方的交互。當一個分布式軟件實例運行時，經(jīng)過某個節(jié)點，則在該節(jié)點的分布式軟件實例表中增加一條記錄，當分布式軟件實例運行結(jié)束時，刪除各節(jié)點中對應(yīng)標識的記錄。多個節(jié)點中具有相同標識的記錄構(gòu)成一個分布式軟件實例。在同一分布式軟件實例上的交互，需滿足對應(yīng)的交互關(guān)聯(lián)規(guī)則。若與交互關(guān)聯(lián)規(guī)則不匹配，則交互關(guān)聯(lián)的可信性值為0，判為不可信，并給出原因；否則交互間關(guān)聯(lián)的可信性值為1，判為可信。交互關(guān)聯(lián)的可信性分析算法如下。

算法1 交互間關(guān)聯(lián)的可信性分析算法

輸入：交互檢查點ic的交互集合IS={ iaction|=1,2,3,…}，交互規(guī)則集和一次分布式軟件運行中的交互實例集合IS'={ iaction'|=1,2,3,…}。

輸出：交互檢查點ic的交互間關(guān)聯(lián)的可信性值（0或1），若可信性值為0，報告不可信的原因。

2) 查找中含iaction的規(guī)則子集RS；

4) 查找與iaction'在同一分布式軟件實例中的iaction'；

6) 報告iaction'和iaction'執(zhí)行順序異常；

7) RETURN 0；

8) END FOR

10) 查找與iaction'在同一分布式軟件實例中的iaction'；

12) 報告iaction'和iaction'執(zhí)行順序異常；

13) RETURN 0；

14) END FOR

16) 查找與iaction'在同一分布式軟件實例中的iaction'；

18) 報告iaction'和iaction'沒有并發(fā)執(zhí)行；

19) RETURN 0；

20) END FOR

22) IF==FALSE THEN

23) 報告iaction'在錯誤的條件下執(zhí)行；

24) RETURN 0；

25) IF 執(zhí)行次數(shù)>1 THEN

26) 報告執(zhí)行次數(shù)異常；

27) RETURN 0；

28) END FOR

30) IF== FALSE THEN

31) 報告iaction'在錯誤的條件下執(zhí)行；

32) RETURN 0；

33) END FOR

34) END FOR

35) RETURN 1；

36) END

3.2 檢查點間的結(jié)構(gòu)及其可信性

一個分布式軟件節(jié)點中，檢查點存在以下結(jié)構(gòu)：順序、并行、分支和循環(huán)。對于順序、并行和分支結(jié)構(gòu)，即具有有限條路徑的結(jié)構(gòu)，本文采用基于路徑的模型[15,16]計算結(jié)構(gòu)的可信性；對于具有潛在的無限路徑的循環(huán)結(jié)構(gòu)，采用基于狀態(tài)的模型[13,14]計算循環(huán)結(jié)構(gòu)的可信性。檢查點()的可信性記為。

1) 順序結(jié)構(gòu)（sequence）

具有順序結(jié)構(gòu)的檢查點按順序依次執(zhí)行，如圖5(a)所示。檢查點序列的可信性為各檢查點可信性的乘積，該序列發(fā)生的概率為各轉(zhuǎn)移概率的乘積，則順序結(jié)構(gòu)的可信性可表示為檢查點序列的可信性與該序列轉(zhuǎn)移概率的乘積。圖5(a)所示的順序結(jié)構(gòu)可信性為

2) 并行結(jié)構(gòu)（parallel）

在并發(fā)環(huán)境下，常通過多個模塊并發(fā)執(zhí)行來提高系統(tǒng)的性能。并發(fā)結(jié)構(gòu)的可信性可表示為并發(fā)執(zhí)行的各檢查點可信性的乘積。如圖5(b)中的點劃線框所示的并行結(jié)構(gòu)的可信性為

3) 分支結(jié)構(gòu)（branch）

具有分支結(jié)構(gòu)的檢查點某一時刻只有一個分支執(zhí)行，如圖5(c)中的點劃線框所示的分支結(jié)構(gòu)。每條分支是一個順序結(jié)構(gòu)，依據(jù)式(1)來計算各分支的可信性，而分支結(jié)構(gòu)的可信性為各分支可信性的和。點劃線框表示的分支結(jié)構(gòu)的可信性為

4) 循環(huán)結(jié)構(gòu)（loop）

具有循環(huán)結(jié)構(gòu)的檢查點循環(huán)執(zhí)行的次數(shù)大于等于1。為了更方便計算循環(huán)結(jié)構(gòu)的可信性，本文在圖5(d)所示的循環(huán)結(jié)構(gòu)前后分別增加入口檢查點entry和出口檢查點exit，這2個檢查點的可信性，圖6所示循環(huán)結(jié)構(gòu)的可信性為

下面給出循環(huán)結(jié)構(gòu)可信性的計算過程。假設(shè)檢查點間的交互具有Markov性質(zhì)，軟件體系結(jié)構(gòu)采用離散時間Markov鏈（DTMC）表示。增加可信狀態(tài)T和不可信狀態(tài)U，如圖7所示。令表示檢查點可信，并由到的轉(zhuǎn)移概率。

轉(zhuǎn)移概率矩陣為

矩陣的次冪的第1行第+2列元素為從檢查點entry經(jīng)步轉(zhuǎn)移到檢查點exit的概率。步數(shù)的可能取值范圍為。當至少有一個檢查點時，有==0。

由此得

(5)

3.3 分布式軟件的可信性

下面以圖8所示的一個分布式軟件在某節(jié)點上的檢查點結(jié)構(gòu)為例，進行節(jié)點的可信性分析。首先將節(jié)點按如下規(guī)則劃分為若干層，每層包含若干模塊：1）一個模塊中包含2個或2個以上檢查點（具有一個檢查點的循環(huán)結(jié)構(gòu)需多次執(zhí)行該檢查點，此種情況認為包含多個檢查點）；2）一個模塊直接包含（即相鄰下層）的模塊或檢查點僅以一種結(jié)構(gòu)存在。圖9用點劃線標出了各層模塊。模塊或檢查點間的結(jié)構(gòu)S：順序，P：并發(fā)，B：分支，L：循環(huán)。為方便起見，本文將第0層記為，將第層中具有順序結(jié)構(gòu)的第個模塊記為()，下標的第1位表示層數(shù)，第2位表示該層的模塊號。其他結(jié)構(gòu)類似表示。對于分支和循環(huán)結(jié)構(gòu)，需在相鄰層檢查點對應(yīng)連接邊上標明條件。圖9對應(yīng)的檢查點結(jié)構(gòu)樹如圖10所示。

在節(jié)點的一次運行過程中，各檢查點要么是順序，要么是并發(fā)到達的。只有保證每個檢查點都可信時，整個節(jié)點才可信。因此，對于Node，節(jié)點實例的可信性等于節(jié)點一次運行過程中經(jīng)過的所有檢查點（葉子）的可信性的乘積?；跈z查點結(jié)構(gòu)樹的節(jié)點實例可信性評價算法如下。

算法2 基于檢查點結(jié)構(gòu)樹的節(jié)點實例可信性評價算法

輸入：節(jié)點Node的檢查點結(jié)構(gòu)樹的根指針。

輸出：節(jié)點實例的可信性insi，并報告不可信的檢查點。

1)insi=1； //初始化Node節(jié)點實例的可信性

2) InitStack()；//初始化棧

3) Push(,)； //入棧

4) WHILE StackEmpty()==FALSE DO //棧不空

5) Pop(,)；//棧頂指針出棧

6) IF->==’S’ THEN //順序結(jié)構(gòu)

7) FOR EACH->child以從右到左順序；

8) Push(,->child)；

9) END FOR

10) IF->==’P’ THEN //并發(fā)結(jié)構(gòu)

11) FOR EACH->child以任一指定順序；

12) Push(,->child)；

13) END FOR

14) IF->==’B’ THEN //分支結(jié)構(gòu)

15) 查找滿足當前條件cond的孩子->child；

16) Push(,->child)；

17) IF->==’L’ THEN //循環(huán)結(jié)構(gòu)

18) WHILEcond==TRUE DO

19) FOR EACH->child以從右到左順序；

20) Push(,->child)；

21) END FOR

22) END WHILE

23) ELSE //檢查點

24) 根據(jù)3.1節(jié)方法評價當前檢查點的可信性；

25) IF

26) 報告當前檢查點不可信；

27)insi=insi；

28) END WHILE

29) RETURNinsi；

30) END

其中，檢查點cp的可信性t可以用多次運行得到的檢查點可信性的均值來進行估計，得到節(jié)點的可信性估計為

根據(jù)木桶理論[19]，分布式軟件實例的可信性取決于分布式軟件一次運行過程中最小的節(jié)點實例可信性，即。分布式軟件的可信性為各節(jié)點的可信性的最小值，即。

4 實驗與分析

以一個典型的分布式電子商務(wù)應(yīng)用——網(wǎng)上購物系統(tǒng)為例進行實驗。該系統(tǒng)是一個分布式客戶端-服務(wù)器系統(tǒng)，采用C#語言，基于MVC（model-view-controller）架構(gòu)模式開發(fā)。本文以網(wǎng)上購物系統(tǒng)中“下訂單”功能模塊為例，本文方法對系統(tǒng)其他模塊均適用。“下訂單”功能模塊涉及到4個構(gòu)件：Customer、Controller、Model和Supplier，它們分布在不同的節(jié)點上，節(jié)點間通過交互實現(xiàn)下訂單功能，其順序如圖11所示。為了區(qū)分各交互，圖中在交互名前加了序號。包括3個場景。

場景1 客戶下訂單，供銷商發(fā)貨。

場景2 客戶下訂單后，在供銷商發(fā)貨前修改訂單，訂單成功修改，供銷商發(fā)貨。

場景3 客戶下訂單，供銷商發(fā)貨后客戶修改訂單，修改被拒絕。

實驗中共有如下節(jié)點并發(fā)執(zhí)行：運行Customer的節(jié)點30個，運行Controller和Model的節(jié)點各2個，運行Supplier的節(jié)點5個，節(jié)點的系統(tǒng)配置為CPU為IntelCore 2 Duo E7500 2.93 GHz，內(nèi)存為2 GB。

4.1 交互間關(guān)聯(lián)的可信性分析方法比較

以構(gòu)件Controller所在節(jié)點為例，由于本文重點是分布式軟件的交互，因此僅考慮交互檢查點，有功能檢查點和分支檢查點時類似，檢查點結(jié)構(gòu)樹如圖12所示。當多個Customer并發(fā)執(zhí)行時，形成多個分布式軟件實例，下面以一個分布式軟件為例，依次訪問的交互為：,,, ([change order after shipment]),,,,,。

本文方法與文獻[7]和文獻[11]中交互間關(guān)聯(lián)的可信性分析比較如表1所示。該分布式軟件實例滿足文獻[7]和文獻[11]的交互關(guān)聯(lián)規(guī)則，交互關(guān)聯(lián)可信性值誤判為1（可信）。實際上，在[change order after shipment]條件下，的后續(xù)交互應(yīng)為。這個軌跡的偏離可以由本文算法1根據(jù)交互規(guī)則* [change order after shipment] (

表1 交互間關(guān)聯(lián)的可信性分析方法比較

4.2 節(jié)點可信性評價方法比較

表2給出了基于體系結(jié)構(gòu)的各類分布式軟件節(jié)點可信性評價方法（基于路徑的方法[15,16]、基于狀態(tài)的方法[13,14]和本文基于檢查點結(jié)構(gòu)樹方法）的比較，下面從以下幾方面進行分析。

1) 容納全部節(jié)點實例和處理無限路徑

基于路徑的方法由于路徑的數(shù)目受到測試期間觀察的限制，對于無限條路徑的系統(tǒng)，無法覆蓋全部路徑，不能容納全部的節(jié)點實例?；跔顟B(tài)的方法和基于檢查點結(jié)構(gòu)樹的方法能夠容納全部節(jié)點運行軌跡，能夠處理潛在的無限路徑（即循環(huán)結(jié)構(gòu)），不存在基于路徑的方法只能用來分析解決有限條路徑系統(tǒng)的問題。

對于構(gòu)件Controller所在節(jié)點，由于節(jié)點中存在循環(huán)結(jié)構(gòu)，基于路徑的方法無法計算節(jié)點的可信性，本文基于檢查點結(jié)構(gòu)樹，節(jié)點可信性可由式(8)得出，其中，t()為檢查點的可信性，,,,,,可依據(jù)3.2節(jié)給出的檢查點結(jié)構(gòu)公式計算得出

2) 處理大狀態(tài)空間

基于狀態(tài)的方法在對復(fù)雜系統(tǒng)建模時會產(chǎn)生難以處理的大狀態(tài)空間，使計算和分析非常復(fù)雜甚至不可行。本文基于檢查點結(jié)構(gòu)樹的方法通過將節(jié)點劃分模塊分層，基于檢查點間結(jié)構(gòu)計算節(jié)點可信性，不存在大狀態(tài)空間問題。

對于圖8所示的節(jié)點的檢查點結(jié)構(gòu)，基于狀態(tài)的方法中狀態(tài)數(shù)為檢查點的數(shù)目即11，而本文方法只有循環(huán)結(jié)構(gòu)中使用基于狀態(tài)的模型，其他結(jié)構(gòu)采用基于路徑的模型。如圖10所示，L1,1有3個孩子，因此基于狀態(tài)模型計算時狀態(tài)數(shù)為3，遠遠小于整個分布式軟件基于狀態(tài)方法計算的狀態(tài)數(shù)。

3) 適用場合

基于路徑的方法能夠方便地進行節(jié)點實例的可信性評價，但由于對無限路徑的系統(tǒng)無法覆蓋全部路徑，使基于各節(jié)點實例進行節(jié)點可信性的評價不再適用?；跔顟B(tài)的方法可以分析解決潛在的無限條路徑的系統(tǒng)，適用于評價節(jié)點的可信性，但由于不針對某條運行軌跡，所以不適用于進行節(jié)點實例的可信性評價。而本文提出的檢查點結(jié)構(gòu)樹能夠容納并表征節(jié)點內(nèi)的全部運行軌跡，即所有的節(jié)點實例，因此不僅可以用于進行節(jié)點實例的可信性評價，還可以基于檢查點結(jié)構(gòu)樹進行節(jié)點的可信性評價。

對4.1節(jié)提到的分布式軟件實例，交互檢查點3的可信性值為0，由基于檢查點結(jié)構(gòu)樹的節(jié)點實例可信性評價算法（算法2）得到Controller的節(jié)點實例可信性值為0，準確判為不可信。對于構(gòu)件Controller所在節(jié)點的可信性，可以依據(jù)式(8)計算得出。

表2 分布式軟件節(jié)點可信性評價方法的比較

4.3 運行效率分析

為了對檢查點進行監(jiān)控，會在檢查點處織入探針，相應(yīng)地增加了運行時開銷，主要包括：1）獲取檢查點屬性信息的開銷；2）將檢查點屬性信息經(jīng)網(wǎng)絡(luò)傳輸?shù)焦?jié)點分析器的開銷。在運行平臺一定的情況下，探針所消耗的時間基本是常量，不會改變原有程序的計算復(fù)雜度。探針獲取監(jiān)控信息后，傳輸給節(jié)點分析器，這部分處理可以在不同的處理器上完成，并且處理邏輯和軟件的運行邏輯沒有關(guān)聯(lián)性，所以不會給程序功能邏輯的運行帶來額外開銷。

以“下訂單”功能模塊場景1中構(gòu)件Controller的交互檢查點為例，測試織入獲取交互檢查點屬性的探針后各交互檢查點帶來的時間開銷。假設(shè)織入獲取交互檢查點屬性的探針前，“下訂單”功能模塊場景1運行一次的時間為，織入后帶來的時間開銷為，相對未監(jiān)控情況，監(jiān)控所帶來的額外開銷百分比為。對某一交互，令獲取該交互檢查點屬性的時間開銷為get，交互的時間開銷為exe。本文將獲取交互檢查點屬性和節(jié)點交互并發(fā)執(zhí)行，當get≤exe時，獲取交互檢查點屬性引入的額外時間開銷為0；當get>exe時，獲取交互檢查點屬性引入的額外時間開銷為get?exe。實驗中共進行了5次測試，結(jié)果如表3所示。=2.83，即各交互額外時間開銷均值的和，= 1 108.93，引入交互檢查點監(jiān)控帶來的額外開銷為0.25%。可見，通過對交互檢查點的監(jiān)控與節(jié)點交互并發(fā)執(zhí)行，獲取交互檢查點屬性的時間開銷基本淹沒在執(zhí)行交互的運行時間內(nèi)，對分布式軟件的整體運行造成的影響很小。

表3 交互檢查點帶來的時間開銷(ms)

5 結(jié)束語

針對現(xiàn)有的分布式軟件交互關(guān)聯(lián)規(guī)則無法適應(yīng)復(fù)雜交互場景可信性分析，以及傳統(tǒng)的基于軟件體系結(jié)構(gòu)來評價分布式軟件可信性的方法存在的問題，本文在節(jié)點內(nèi)織入3種檢查點，引入了更準確的交互關(guān)聯(lián)規(guī)則，通過對檢查點屬性及節(jié)點間交互的監(jiān)控，來對檢查點可信性進行評價；通過將節(jié)點分解為多層結(jié)構(gòu)，實現(xiàn)了基于檢查點結(jié)構(gòu)樹的分布式軟件及其實例的可信性分析；并以小型分布式軟件為例進行了實驗，驗證了方法的可行性及有效性。

本文方法與基于檢查點的傳統(tǒng)軟件可信性評價機制相比，增加了交互檢查點，引入了適應(yīng)復(fù)雜交互場景的交互關(guān)聯(lián)規(guī)則，因此對于節(jié)點間協(xié)作交互頻繁的分布式軟件，如電信和金融領(lǐng)域的服務(wù)系統(tǒng)、交通控制系統(tǒng)以及電子商務(wù)系統(tǒng)等，更能突出本文方法的優(yōu)勢。對于節(jié)點間交互不頻繁的分布式軟件，監(jiān)控的處理則退化為針對傳統(tǒng)軟件的處理方法。

下一步的工作是在大規(guī)模分布式軟件上測試各類檢查點的設(shè)置粒度，針對具體需求在監(jiān)控開銷和監(jiān)控粒度上權(quán)衡；并測試本文方法是否隨分布式軟件規(guī)模的增大存在一定的局限性。

[1] REYNOLDS P, KILLIAN C, WIENER J L, et al. Pip: detecting the unexpected in distributed systems[C]//The 3rd Symposium on Networked Systems Design and Implementation. USENIX Association Berkeley, CA, USA, c2006: 115-128.

[2] 楊曉暉, 周學(xué)海, 田俊峰, 等. 一個新的軟件行為動態(tài)可信評測模型[J]. 小型微型計算機系統(tǒng)，2010,31(11): 2113-2120.

YANG X H, ZHOU X H, TIAN J F, et al. Novel dynamic trusted evaluation model of software behavior [J]. Journal of Chinese Computer Systems, 2010,31(11): 2113-2120.

[3] 劉玉玲, 杜瑞忠, 馮建磊, 等. 基于軟件行為的檢查點風險評估信任模型[J]. 西安電子科技大學(xué)學(xué)報（自然科學(xué)版），2012,39(1):179-184.

LIU Y L, DU R Z, FENG J L, et al. Trust model of software behaviors based on check point risk assessment [J]. Journal of Xidian University, 2012,39(1):179-184.

[4] 田俊峰, 張亞姣. 基于馬爾可夫的檢查點可信評估方法[J]. 通信學(xué)報，2015,36(1): 230-236.

TIAN J F, ZHANG Y J. Checkpoint trust evaluation method based on Markov [J]. Journal on Communications, 2015,36(1): 230-236.

[5] 劉東紅, 郭長國, 王懷民, 等. 監(jiān)控使能的分布式軟件系統(tǒng)構(gòu)造方法[J]. 軟件學(xué)報，2011,22(11):2610-2624.

LIU D H, GUO C G, WANG H M, et al. Monitoring enabled distributed software construction method[J]. Journal of Software, 2011, 22(11): 2610-2624.

[6] 文志誠, 李長云, 滿君豐. 基于貝葉斯網(wǎng)的分布式軟件行為運行時可信性分析[J]. 小型微型計算機系統(tǒng)，2012,33(3):504-511

WEN Z C, LI C Y, MAN J F. Analyzing running-time behavioral credibility for distributed software based on Bayesian network [J]. Journal of Chinese Computer Systems, 2012,33(3):504-511.

[7] 彭成, 楊路明, 滿君豐. 網(wǎng)絡(luò)化軟件交互行為動態(tài)建模[J]. 電子學(xué)報，2013,41(2):314-320.

PENG C, YANG L M, MAN J F. Dynamic modeling of networked software interactive behavior[J]. Acta Electronica Sinica, 2013,41(2): 314-320.

[8] WANG Q, LU Y, XU Z J, et al. Software reliability model for component interaction mode[J]. Journal of Electronics(China), 2011, 28(4/5/6):632-642.

[9] YANG N H, YU H Q, QIAN Z L, et al. Modeling and quantitatively predicting software security based on stochastic Petri nets[J]. Mathematical and Computer Modeling, 2012,55(1-2):102-112.

[10] TYAGI K, SHARMA A. An adaptive neuro fuzzy model for estimating the reliability of component-based software systems[J]. Applied Computing and Informatics, 2014,10(s1-2):38-51.

[11] CHEN X H, LIU J, LIU Z M. Requirements monitoring for Internetware: an interaction based approach[J]. Science China: Information Science, 2013,56(8):1-15.

[12] GOKHALE S S. Architecture-based software reliability analysis: overview and limitations[J]. IEEE Transactions on Dependable and Secure Computing, 2007,4(1): 32-40.

[13] CHEUNG R C. A user-oriented software reliability model[J]. IEEE Transactions on Software Engineering, 1980,SE-6(2):118-125.

[14] GOKHALE S S, WONG W E, HORGAN J R, et al. An analytical approach to architecture-based software performance and reliability prediction[J]. Performance Evaluation, 2004,58(4):391-412.

[15] HSU C J, HUANG C Y. An adaptive reliability analysis using path testing for complex component-based software systems[J]. IEEE Transactions on Reliability, 2011,60(1):158-170.

[16] YACOUB S, CUKIC B, AMMAR H H. A scenario-based reliability analysis approach for component-based software [J]. IEEE Transactions Reliability, 2004,53(4):465-480.

[17] 李珍，田俊峰，趙鵬遠. 基于分級屬性的軟件監(jiān)控點可信行為模型[J]. 電子與信息學(xué)報，2012,34(6):1445-1451.

LI Z, TIAN J F, ZHAO P Y. A trustworthy behavior model for software monitoring point based on classification attributes[J]. Journal of Electronics & Information Technology, 2012,34(6):1445-1451.

[18] 李珍，田俊峰，楊曉暉. 基于檢查點分級屬性的軟件動態(tài)可信評測模型[J]. 計算機研究與發(fā)展，2013,50(11):2397-2405.

LI Z, TIAN J F, YANG X H. Dynamic trustworthiness evaluation model of software based on checkpoint’s classification attributes [J]. Journal of Computer Research and Development, 2013,50(11): 2397-2405.

[19] 邵建平，王玲. “拉長板”木桶原理及其運用研究[J]. 科技管理研究，2005,25(4):159-161.

SHAO J P, WANG L. Research on “stretched panels” bucket theory and its application [J]. Science and Technology Management Research, 2005,25(4):159-161.

Distributed software monitoring and trustworthiness evaluation based on checkpoints

LI Zhen1, TIAN Jun-feng1, CHANG Zhuo1, MA Xiao-xue2

(1. School of Computer Science and Technology, Hebei University, Baoding 071000, China; 2. Computer Department, Hebei University, Baoding 071000, China)

Traditional software trustworthiness evaluation based on checkpoints and the existing interaction association rules for distributed software were inapplicable to distributed software with complex interactions. According to this problem, an accompanying distributed software monitoring mechanism was used, and three types of checkpoints in nodes and interaction association rules were introduced for complex interaction scene. The trustworthiness of the node instance was evaluated based on checkpoint structure tree by dividing nodes into several modules, and then the trustworthiness of distributed software was evaluated based on nodes. The experimental results showed that the approaches could evaluate the trustworthiness of distributed software instance accurately with small monitoring cost, and could be suitable for infinitely long paths with no state explosion problem for trustworthiness evaluation of distributed software.

distributed software, trustworthiness, checkpoint, interaction, behavior monitoring

TP393.08

A

10.11959/j.issn.1000-436x.2016048

2015-01-25；

2015-11-02

國家自然科學(xué)基金資助項目（No.61170254）；河北省自然科學(xué)基金資助項目（No.F2015201089, No.F2014201099）；河北省高等學(xué)?？茖W(xué)技術(shù)研究青年基金項目（No.QN2016149）；河北大學(xué)自然科學(xué)研究計劃基金資助項目（No.2013-250）

The National Natural Science Foundation of China (No.61170254), The Natural Science Foundation of Hebei Province (No.F2015201089, No.F2014201099), The Youth Foundation of Hebei Educational Committee (No.QN2016149), The Science Foundation of Hebei University(No.2013-250)

李珍（1981-），女，河北保定人，河北大學(xué)副教授，主要研究方向為軟件安全、可信計算。

田俊峰（1965-），男，河北保定人，博士，河北大學(xué)教授、博士生導(dǎo)師，主要研究方向為信息安全、分布式計算、網(wǎng)絡(luò)技術(shù)。

常卓（1979-），男，河北保定人，河北大學(xué)講師，主要研究方向為可信計算、網(wǎng)絡(luò)技術(shù)。

馬曉雪（1974-），女，河北蔚縣人，河北大學(xué)副教授，主要研究方向為可信計算、網(wǎng)絡(luò)技術(shù)。