基于Ｍａｒｋｏｖ鏈使用模型的組件復用的統計測試

摘要：提出了用Markov鏈使用模型來模擬具體環境中組件的使用方式，對組件的復用進行統計測試，詳細論述了提出的組件復用統計測試的思想框架和測試步驟，并進一步指出了每個測試步驟具體的研究細節。最后給出了提出的方法與現有方法的對比分析，說明提出的方法是組件復用自動化測試的一種經濟可行的方法。

關鍵詞：Markov鏈使用模型； 組件復用； 統計測試； 自動化測試

中圖分類號：TP311文獻標志碼：A

文章編號：1001－3695(2008)04－1051－03

組件軟件系統的開發已經成為當今軟件開發方法中的研究熱點。對于復雜、大型軟件系統的開發，不再是單純地從頭開始進行開發，而是從現有組件庫中選用或購買滿足要求的組件，按照已經定義好的軟件體系結構，通過基于組件的軟件工程過程對這些組件進行裝配來開發一個軟件系統。今天，雖然通過復用現有的組件可以節省軟件開發的時間和工作量，但是在大部分情況下，組件用戶對商用組件沒有進行分析和測試就進行復用。由于以下三個原因，如果對組件不進行一定程度的測試，組件的復用可能存在潛在的危險：a)組件被開發時，測試集中于它們假定的目標環境，而組件被復用時，它們新的使用環境可能不同于它們最初的目標環境；b)組件被復用時，接受標準也可能不同，如組件被復用在有嚴格安全性要求的環境中，組件的可靠性要求較高；c)在具體的環境中使用的可能是組件的一個功能子集。歐洲的Ariane 5發射失敗的例子就是一個很好的教訓。Ariane 5發射失敗的原因就是復用了Ariane 4系統中的組件，而沒有重新進行測試。所以，即使組件在最初的環境下已經通過了測試，在新的環境下復用組件仍然可能存在問題。

雖然目前CORBA、EJB、COM等組件技術在工業界得到了廣泛的應用，但這一領域的研究還遠沒有完善，很多研究課題有待解決[1]。例如，文獻[2]提出了組件復用測試的技術挑戰，即在新的復用環境下，如何產生組件復用的測試用例？如何完成組件的充分性測試？當復用的組件升級或部分修改時，如何高效地測試更新的部分而減少冗余測試？軟件工程師手工分析和完成組件復用的測試是非常耗時的工作，如何用一種經濟可行的方法使組件復用的自動化測試成為可能？只有很好地解決了這些問題，組件軟件系統的可靠性得到了保證，組件復用帶來的優勢才會得到充分地體現。

由于大量商用組件的源代碼不公開，這給組件復用的測試帶來很大困難。目前，已有一些文獻專注于組件復用的測試，而現有的組件復用的測試方法都沒有很好地解決這些問題，本文在第3章進行了討論。

1基于Markov鏈使用模型的統計測試原理

在軟件統計測試中，軟件測試被看做是一個統計方法的問題。它產生軟件所有可能使用的一個子集，并以這個子集所表現的性能作為依據來考慮軟件的整體使用性能，以度量軟件的可靠性，即通過樣本推斷總體。

統計測試最成功的就是基于Markov鏈使用模型的統計測試。基于使用模型的統計測試更經濟有效，并且能獲得軟件的高可靠性[3]。在實際項目中的應用表明，基于Markov鏈使用模型的統計測試方法可以成功地測試軟件。文獻[4]給出了基于Markov鏈使用模型的統計測試的成功應用案例的一個列表。

描述軟件使用的Markov鏈使用模型定義如下：軟件Markov鏈使用模型定義為一個五元組M=〈S，Γ，δ，s0，f〉。其中：S是軟件使用的狀態集合；

Γ是轉換標記的集合，狀態轉換標記通常有轉換輸入和轉換概率構成；

δ表示軟件執行過程中軟件狀態之間的轉移函數，δ：S×Γ→S；

s0∈S，是初始狀態，它代表軟件激活的狀態；

f∈S，是終止狀態，它代表軟件終止執行時進入的狀態。

另外，對狀態s∈S，如果δ(s，γj)=s′。其中：s′∈S，那么∑j(γi×probability)=1。

Markov鏈使用模型可以刻畫軟件的使用過程，它將軟件的使用特征以數學模型的方法表示出來。軟件的每一次使用都從Markov鏈的初態開始經過若干個中間態，最后到達終態。一個簡單的Markov鏈使用模型的圖形化表示如圖1所示。

用Markov鏈來描述軟件的使用方式，任何下一個發生的事件只與當前的狀態有關，不涉及歷史信息。只有滿足這個條件才可以使用數學的方法對Markov鏈進行分析和驗證，觀察軟件預期的使用，指導測試計劃。筆者可以根據Markov鏈使用模型產生軟件的隨機測試用例，并基于測試的充分性標準完成統計測試計劃并執行隨機測試用例，最后按照數學和統計學模型對測試結果進行分析，獲取軟件的可靠性度量。

2組件復用的統計測試框架的提出

關于軟件組件(software component)存在多種定義，目前被業界普遍接受的是由Clemens Szyperski[5]定義的，即一個軟件組件就是一個組合單元，它具有一組按契約或合同說明的特定的接口和清晰的上下文依賴關系。一個軟件組件可以被獨立地部署，以便被第三方組裝。本文將軟件組件簡稱為組件。

為了度量復用組件的可靠性，在新的上下文環境中覆蓋重要的組件使用模式，以及完成組件的黑盒測試以驗證在新的復用環境中組件功能和行為。筆者提出了基于組件規格說明的組件復用的統計測試框架（圖2），以便于對組件進行自動化測試和度量其可靠性。表1闡明了本文的方案可以很好地解決引言中提出的組件復用測試的技術難題。

在統計測試的框架下，本文提出了基于Markov鏈使用模型的組件復用的統計測試步驟：

a)選擇一種在軟件分析和設計中用途較廣的組件的規格說明，如軟件結構描述語言（architecture description language，ADL）描述的組件的規格說明或UML描述的組件的規格說明等。用組件的規格說明以及組件在新的環境中的使用信息作為構建Markov鏈使用模型的原始信息，必要時可加入合理的統計測試約束條件。

b)由步驟a)中獲取的信息構建Markov鏈使用模型。

c)用數學的方法對Markov鏈使用模型進行分析和驗證，指導測試計劃的進行，對Markov鏈分析的結果可能導致重新建立Markov鏈或對其使用模型的轉換概率重新賦值。

d)由Markov鏈使用模型產生測試用例。

e)給出合理的測試停止的標準。

f)分析測試結果，用統計原理對組件復用進行可靠性評估。

表1解決組件復用測試技術難題的方法

面向用戶的組件復用測試的技術難題本文的解決方法

在新的復用環境下，如何產生組件復用的測試用例采用和使用模型關聯的概率來產生隨機測試用例，并在測試期間根據需要動態調整與關鍵操作相關的轉移弧上的概率

在新的復用環境下，如何完成組件的充分性測試采用使用鏈與測試鏈之間的差異以及組件復用的可靠性指標共同來作為測試停止的標準

當復用的組件升級或部分修改時，如何高效地測試更新的部分而減少冗余測試1)商用組件升級時，在原來維護的Markov鏈使用模型的基礎上進行修改和調整，增加組件的使用狀態或/和調整使用模型轉換弧上的概率，體現軟件修改部分的使用，在原來已產生的測試用例的基礎上進一步生成測試用例

2)用戶定制或部分修改商用組件時，定制后的組件是復用組件和修改部分的一個合成。對于組件修改的部分，由于知道源碼，可以結合源代碼的信息來重新構造組件復用的Markov鏈使用模型

如何用一種經濟可行的方法使組件復用的自動化測試成為可能只要提供組件規格說明和組件復用的具體環境的相關信息，本文測試的每一個步驟都可以自動化。基于使用模型的統計測試是經濟有效的[5]，從已有的規格說明技術到基于Markov鏈使用模型的統計測試，該測試過程可以自動化，它在測試領域提供了獨特的技術和經濟的前景[6]，所以本文的方案是可行的

2．1組件Markov鏈使用模型的自動構建算法

盡管統計測試得到了廣泛的認可，但是由于使用模型通常由程序員依賴經驗直接從軟件規范創建，缺乏成熟的軟件使用模型的建立方法，限制了統計測試技術的使用和發展，Markov鏈使用模型的自動構造方法是統計測試獲得廣泛應用的關鍵。國內外對這方面的研究還處于起步階段，主要的研究工作集中在使用面向對象軟件開發和設計中構造的UML模型(即UML用例圖、狀態圖、序列圖等)來生成Markov使用模型[7~10]，對面向對象軟件進行統計測試。

筆者的想法是研究基于組件的規格說明自動生成Markov鏈使用模型的技術。可以通過為Markov鏈使用模型的弧賦予轉換概率來體現該組件新的使用環境。使用模型中的狀態代表組件的使用狀態，使用模型中的弧通常代表運用到軟組件上的輸入，輸入可以來自用戶、系統或其他的組件。當組件復用在新的環境下時，可以創建一個新的Markov鏈使用模型來模擬組件新的使用環境。

假設用戶提供的組件的規格說明是以組件狀態轉換圖的形式給出（文獻[11]提出的組件軟件的測試技術就是假設組件的規格說明以組件狀態機的形式給出）。例如有一商用組件cdPhonograph模擬便攜式的CD唱機，cdPhonograph有三個狀態：stopped、playing和paused；在任何一種狀態下，包括三個可能發生的事件：pause_is_pressed、stop_is_pressed和play_is_pressed。組件cdPhonograph規格說明的狀態轉換如圖3所示。

上述組件的規格說明中的狀態和輸入可以直接轉換為組件使用圖中的狀態和輸入；至于狀態之間的轉換概率，可以根據組件使用的具體環境獲取。例如筆者可以通過軟件原型、類似軟件系統的運行、模擬數據的監控信息或是通過老版本軟件的使用經驗獲取組件使用的相關概率信息。最終自動構建的Markov鏈使用模型如圖4所示。

如今，UML是面向對象軟件系統分析和設計的標準建模語言，而UML應用在組件軟件系統的規格說明才是剛剛開始[1]。筆者正在研究基于UML描述的組件的規格說明自動構造Markov鏈使用模型的算法。

2．2測試用例的產生方法

目前比較流行的基于使用模型產生測試用例方法是隨機抽樣的方式產生測試用例，在統計方法中它是非常流行的黒盒測試方法。由于它采用與使用模型關聯的概率來產生測試用例，所以很接近軟件的真實使用。這種思想的一個擴展就是在測試期間動態改變轉移弧上的概率，如推測一些易于引發故障的關鍵操作可能需要額外的測試，那么就可以動態調整與關鍵操作相關的轉移弧上的概率。筆者將會在此基礎之上研究更加智能的測試用例產生方法，研究故障模式，動態調整轉移概率，以便使組件復用的Markov鏈使用模型更好地滿足測試需求。

2．3測試的充分性

組件復用的測試充分性問題的研究，即決定組件復用測試何時停止。測試何時停止通常基于一些標準，例如：

a)可靠性度量被用來作為測試充分性的標準，即當測試的可靠性達到可接受的點時，軟件測試停止。

b)測試序列產生后，可以基于測試的歷史信息和相應的故障數據信息構建代表軟件測試環境的Markov測試鏈，然后通過使用鏈和測試鏈的相似度作為測試停止的標準。

c)基于狀態、弧或路徑覆蓋度的模型覆蓋標準作為測試停止的標準。

目前，基于使用的統計測試常采用上述三種方法中的一種作為測試停止的標準。在組件復用的統計測試中本文將研究使用多個停止標準，如在下面這種情況下，已完成的測試需要進一步評估，如果測試鏈和使用鏈之間的相似性度量表明測試過程近似匹配軟件的預期使用，然而軟件可靠性評估的偏差較大。所以對于組件復用的充分性測試，筆者將采用使用鏈和測試鏈之間的差異以及組件復用的可靠性指標共同來作為測試停止的標準。

2．4組件復用的可靠性評估技術

基于Markov鏈使用模型的可靠性計算模型常用的有：

a)柏努利采樣模型，這些模型基于成功和非成功測試的數量計算可靠性。

b)故障狀態模型，這些模型包括Markov測試鏈。當測試揭露沒有故障時，這些模型沒有提供故障的概率，而且也沒有考慮先前的測試信息。

c)基于弧的貝葉斯模型。基于Markov鏈使用模型的測試有若干種可靠性模型，但是每一種都有特定的限制，而基于弧的貝葉斯可靠性模型在實際應用中獲得了廣泛的支持。筆者將在基于弧的貝葉斯模型的基礎上來計算組件復用的可靠性，進一步研究適合組件復用的可靠性指標。

3與現有方法的對比分析

目前，在基于組件的軟件工程領域中，人們大多側重于基于組件的軟件開發方法和技術方面的研究，但是組件軟件系統的測試技術仍然沒有很好地發展[12]，只有少數論文專注于組件軟件的測試。現有的組件復用的測試方法如表2所示。

表2現有的組件復用的測試方法

編號現有的組件復用的測試技術測試原理及組件的開發者需要提供的信息方法的限制

1基于元數據(metadata)的測試方法[13]要求組件的開發提供一些生成測試用例的元數據信息制定元數據的標準非常困難；元數據方法未成為一種業內標準，缺乏組件提供者的支持；缺乏充分性測試模型

2組件內嵌測試(built－in

test)[14，15]要求組件的開發者提供組件源代碼中用于內嵌測試的成員函數需要組件源碼，而大部分商用組件的源碼是不公開的；缺乏充分性測試模型

3component test bench[16]組件開發者提供一個組件測試規范，并制訂了一系列步驟的測試操作缺乏充分性測試模型

4component interac－tion testing[17]首先基于組件的規格說明創建組件的使用模型，建立每個構件的形式化測試需求，然后由測試需求生成單元測試用例缺乏創建組件使用模型的系統化創建方法；缺乏充分性測試模型

5boundary value analysis[16]將組件的輸入值和輸出值劃分為一定數量的帶有邊界規則的集合。使用邊界值分析測試工具來產生測試用例如不能保證輸入變量是真正獨立的，這類方法將不會產生令人滿意的測試用例

所有現存的測試用例產生方法都有其自己的優點，但普遍存在應用面狹窄、缺乏組件復用的充分性測試模型、沒有相關的計算可靠性的技術以及自動化程度不高等缺陷。

統計測試是剛剛投入工業實踐的一個新的研究領域，從已有的規格說明技術到基于Markov鏈使用模型的統計測試，該測試過程可以自動化，它在測試領域提供了獨特的技術和經濟前景[10]。到目前為止，組件復用的統計測試僅有極少論文涉及[18~20]。Rakesh Shukla等人[18，19]為組件可靠性評估提出了一個概念框架，但它要求用戶輸入組件復用的操作剖面、產生的測試用例的數量或組件要求的可靠性指標，這在一定程度上限制了組件可靠性評估的自動化程度。為組件復用操作剖面提供一種系統化的構建方法是一個有待解決的難點。另外，對于組件測試的充分性問題作者也沒有討論。文獻[20]提出了基于Markov鏈使用模型的軟件復用的統計測試方法，但是并沒有討論創建使用模型的系統化的具體算法。在這篇論文中，使用模型和測試模型之間的差異被用來作為組件復用測試的停止標準。使用模型和測試模型之間差異的度量用的是簡單的線性衰減，更多的度量方法需要研究。另外對于組件復用的可靠性度量沒有討論。

4結束語

對組件用戶而言，用組件來裝配軟件系統要成為一個切實可行的有效實踐，組件復用的可靠性測試是一個必

不可少的步驟。組件復用的統計測試根據用戶對組件的使用方式展開，對那些使用頻繁的操作會進行更多的測試，因此可以有效地發現組件中那些對所裝配的軟件系統可靠性影響較大的錯誤，以評價組件在實際運行中的可靠性。組件復用的統計測試可以在具體應用環境下自動分析組件的可靠性，自動決定組件是否能被復用，這對于測試工程師而言將具有重要意義。

參考文獻：

[1]BERTOLINO A， MARCHETTI E， POLINI A. Integration of components to test software components[J]. Electronic Notes in Theorecical Computer Science， 2003，82(6):44－54.

[2]JERRY Z G， JACOB H S， JACOB T， et al. Testing and quality assurance for component－based software[M]. Norwood， MA: Artech House， Inc， 2003.

[3]PROWELL S J， TRAMMELL C J，LINNER R C， et al. Cleanroom software engineering: technolony and process[M].[S.l.]: Addison－Wesley Professional， 1999.

[4]SAYRE K. Improved techniques for software testing based on Markov chain usage models[D]. Knoxville: University of Tennessee， 1999.

[5]CLEMENS S. Component software: beyond object－oriented programming[M].[S.l.]: Addison－Wesley Professional， 2003.

[6]RAMACHANDRAN M. Testing software components using boundary value analysis[C]//Proc of the 29th EUROMICRO Conference on New Waves in System Architecture. Washington DC: IEEE Compu－ter Society， 2003.

[7]YAN Jiong， WANG Ji， CHEN Huo－wang. Deriving software statistical testing model from UML model[C]//Proc of the 3rd International Conference on Quality Software. Washington DC: IEEE Computer Society， 2003.

[8]HUBNER M， PHILIPPOW I， RIEBISCH M. Statistical usage testing based on UML[C]//Proc of the 7th World Multiconferences on Systemics， Cybemetics and Informatics. 2003.

[9]RIEBISCH M， PHILIPPOW I， GTZEM. UML－based statistical test case generation[C]//Lecture Notes in Computer Science. London: Springer， 2003.

[10]DULZ W， ZHEN Fen－hua. MateLo－statistical usage testing by annotated sequence diagrams， markov chains and TTCN－3[C]//Proc of the 3rd International Conference on Quality Software. Washington DC: IEEE Computer Society， 2003.

[11]BEYDEDA S， GRUHN V. An integrated testing technique for component－based software[C]//Proc ofACS/IEEE International Con－ference on Computer Systems and Applications. Washington DC: IEEE Computer Society， 2001:328－334.

[12]LIU W， DASIEWICZ P. Formal test requirements for component interactions[C]//Proc ofIEEE Canadian Conference on Electrical and Computer Engineering. Edmonton:[s.n.]， 1999.

[13]ORSO A， HARROLD M J， ROSENBLUM D. Using component metacontent to support the regression testing of component－based software[C]//Proc of IEEE International Conference on Software Maintenance. Washington DC: IEEE Computer Society， 2000:716－725.

[14]WANG Ying－xu， KING G， WICKBURG A H. A method for built－in tests in component－based software maintenance[C]//Proc of the 3rd European Conference on Software Maintenance and Reengineering. Washington DC: IEEE Computer Society， 1999:18－189.

[15]GROSS H G， SCHIEFERDECKER I， DIN G. Model－based built－in tests[C]//Proc of Workshop on Model Based Testing. 2004.

[16]BUNDELL G A， LEE G， MORRIS J， et al. A software component verification tool[C]//Proc of International Conference on Software Methods and Tools. Washington DC: IEEE Computer Society， 2000:137－146.

[17]WU Ye， PAN Dai， CHEN M H. Techniques for testing component－based software[C]//Proc of the 7th IEEE International Conference on Engineering of Complex Computer Systems. Washington DC: IEEE Computer Society， 2001:222－232.

[18]SHUKLA R， STROOPER P， CARRINGTON D. A framework for reliability assessment of software components[C]//Proc of Lecture Notes in Computer Science. Berlin: Springer－Verlag， 2004:272－279.

[19]SHUKLA R， STROOPER P， CARRINGTON D. Tool support for statistical testing of software components[C]//Proc of the 12th Asia－Pacific Software Engineering Conference. Washington DC: IEEE Computer Society， 2005:719－728.

[20]KIM J. Automatic testing for software reuse[D]. Melbourne: Computer Sciences， 2003.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”