趙鶴，高婉玲

（四川大學計算機學院，成都 610064）

基于模型的軟件測試用例生成方法比較研究

趙鶴，高婉玲

（四川大學計算機學院，成都 610064）

隨著軟件系統(tǒng)的規(guī)模和復雜度的增加，軟件測試的自動化提上日程，軟件測試用例的自動化生成成為降低測試成本的重要途徑。模型檢測技術和工具的出現(xiàn)，使得軟件測試用例的生成更加自動化。本文對基于模型檢測技術的測試用例自動生成方法進行評估，與傳統(tǒng)的基于有限狀態(tài)機（FSM）模型的測試用例自動生成方法進行比較，采用系統(tǒng)文獻綜述和可控實驗的方法，進行定性和定量的比較分析。結果顯示，基于模型檢測技術的測試用例自動生成方法在自動化程度、測試覆蓋率、測試成本等方面都具有優(yōu)勢，是一種可以應用和進一步研究的測試用例自動生成方案。

軟件自動化測試；測試用例自動生成；基于模型的測試用例生成；模型檢測；有限狀態(tài)機

0 引言

軟件自動化測試是把人工的測試行為轉化為自動執(zhí)行的一種過程，一般使用特殊的軟件（與被測軟件分離）控制測試的執(zhí)行，以及實際結果與預測結果的比較[1]。軟件自動化測試主要用于回歸測試，目的是分擔在保證軟件質(zhì)量的前提下，縮短測試周期，降低測試成本。測試用例是一個描述輸入、執(zhí)行操作以及期望輸出的文檔，用于判斷程序的某個屬性是否能夠正常的執(zhí)行。測試用例的自動生成是指使用形式化方法，自動化的構建測試用例，是軟件自動化測試的關鍵和難點。

基于模型的測試用例自動生成是一種重要的方法，包括傳統(tǒng)的基于模型的方法和新的基于模型檢測技術的方法。軟件模型是用形式化的方法對軟件特征的抽象和刻畫，常見的、可用于測試用例生成的軟件模型包括：FSM模型、UML模型以及Markov模型等。模型檢測采用狀態(tài)空間搜索的方法檢測一個給定的模型是否滿足某個特定的屬性[2]。模型檢測技術通過分析模型的整個狀態(tài)空間來判斷給定的模型是否滿足某個屬性，如果屬性沒有得到滿足，模型檢測將會生成反例。對于測試而言，反例可以被看作是測試用例。

本文的研究范圍及目標是：對功能測試環(huán)境下基于FSM模型的測試用例生成方法以及基于模型檢測的測試用例生成方法進行比較，進而對基于模型檢測的測試用例生成方法進行評估。

1 測試用例自動生成方法的定性分析

本文在評估基于模型檢測技術的測試用例自動生成方法時，采用系統(tǒng)文獻綜述[3]方法，對現(xiàn)有文獻中的相關內(nèi)容進行綜述，從定性的角度評估方法。

圖1 文獻年代分布對比圖

如圖1，基于FSM模型的測試用例生成方法起源較早，2006之后發(fā)展趨于平緩，目前已較為成熟。模型檢測技術應用于測試用例生成起源于1996年，從2001年之后發(fā)展很快，目前相關研究也較多。

表1 基于FSM模型的方法部分文獻作者分布表

表2 基于模型檢測的方法部分文獻作者分布表

從表1和表2可以看出：在基于FSM模型方法相關的220篇文獻中，發(fā)表過一篇文獻的占總數(shù)的47.27%，2篇的占26.82%，發(fā)表過7篇文獻的作者僅占總數(shù)的0.91%。在基于模型檢測技術相關的206篇文獻中，發(fā)表過一篇文獻的占總數(shù)的72.33%，發(fā)表過7篇文獻的作者僅占總數(shù)的0.49%。說明很多學者都有對這個話題進行研究，但是專注于此方面的作者卻很少，還沒有形成一個核心的作者群。

圖2基于FSM/模型檢測的測試用例生成中文獻數(shù)量排名前幾位的作者及篇數(shù)。

從圖2可以看出：Vijaykumar，N.L（7篇）和Huaikou，Miao.（7篇）這兩位作者在基于FSM模型方法中出現(xiàn)的頻次相對較高，F(xiàn)raser，G.（6篇）和Liping，Li.、Saab, D.G.、Wotawa,F.（5篇）這幾位作者在基于模型檢測方法中出現(xiàn)的頻次相對較高，說明這幾位作者及其團隊對這兩個領域相關的研究較多，它們所編寫的文獻對于這兩類方法具有一定的指導意義。

圖2 基于FSM/模型檢測的測試用例生成中文獻數(shù)量排名前幾位的作者及篇數(shù)

2 測試用例自動生成方法的定性分析結果

發(fā)展歷程。基于FSM的測試用例生成方法是最早出現(xiàn)并得到應用的，目前已經(jīng)具有比較成熟的理論基礎。七十年代末開始，各類基于FSM、EFSM模型的測試用例生成算法逐步出現(xiàn)，主要有T方法、U方法、D方法、W方法等。基于模型檢測的測試用例生成方法出現(xiàn)較晚，但是發(fā)展較快，目前的應用也比較廣泛。1996年Callahan[4]等人最早提出了使用模型檢測來自動生成測試用例，隨后越來越多的方法被提出并得到了應用。針對數(shù)字系統(tǒng)，一個基于模型檢測的保證高效覆蓋的測試用例覆蓋方法被提出[5]。Wijesekera等人利用模型檢測生成的反例和測試用例之間的形式化關系，用CTL公式得到測試需求，將測試用例集和與需求有關的反例進行覆蓋，從而可以獲得滿足測試準則的測試集[6]。John Rushby提供了使用模型檢測生成用于檢測軟/硬件的有效的測試集的方法[7]。

工具及自動化程度。基于模型檢測的方法自動化程度更高。目前，基于模型檢測的測試用例生成工具包括NuSMV、Spin、UPPAAL、CoVer、SAL等；基于FSM的測試用例生成的工具包括GOTCHA、TCBean、toolSET_Certify、ConformanceKit、Phact、TVEDA、RFT、Rational Robot等。

應用領域。均可應用到通信協(xié)議、Web應用、實時系統(tǒng)、控制系統(tǒng)、嵌入式系統(tǒng)中，基于模型檢測的方法的應用逐漸擴大到軟件的開發(fā)設計和系統(tǒng)的安全特性驗證，但是基于FSM的方法在工業(yè)界中的實際應用較少。

優(yōu)缺點?；谀Ｐ蜋z測的方法自動化程度高，能夠產(chǎn)生反例，可以減少測試時間、提高測試效率。但在測試用例生成過程中會出現(xiàn)狀態(tài)爆炸問題[8]，也有可能產(chǎn)生大量的冗余[9]，另外時間的引入也會增加測試模型的復雜性?；贔SM的方法跟模型檢測一樣也可能產(chǎn)生大量的冗余，不僅如此，使用該方法生成測試用例還需要測試人員具備一定的理論基礎，且缺乏通用的工具支持[10]；但是基于FSM的方法簡單[11]、敏捷，有成熟的理論基礎。

3 測試用例自動生成方法的定量比較分析

本文采用比較實驗，一方面，在針對同一個系統(tǒng)、生成同樣數(shù)量（長度）的測試用例條件下，比較兩種方法生成的測試用例的狀態(tài)覆蓋率、遷移覆蓋率、遷移對覆蓋率。另一方面，在針對同一個系統(tǒng)、保證測試覆蓋率相同的情況下，比較兩種方法生成的測試用例的數(shù)量（長度），即在測試成本上的差異。

3.1 實驗對象及工具選擇

被測系統(tǒng)的選擇考慮典型實例，覆蓋狀態(tài)及遷移的類型、有環(huán)/無環(huán)、簡單模型、復雜模型、真實模型等，具體模型圖3-7所示。

圖3 model1簡單模型[10]

圖4 model2中間模型

圖5 model3 Web應用實例—招聘信息發(fā)布系統(tǒng)

圖6 model4 Soft Drink vending machine[13]

分別選取ModelJunit和UPPAAL[14]作為傳統(tǒng)的基于模型的方法和模型檢測方法的工具代表，ModelJUnit開源工具以圖形化的界面更加直觀的展現(xiàn)狀態(tài)之間的變化，相對于其他工具而言，可以實現(xiàn)更多類型的覆蓋，可以控制生成測試序列的速度，使用非常方便，可與Eclipse軟件結合使用。UPPAAL在時間和空間上的性能是比較高[15]，而且可以模擬生成不同的測試序列，并控制生成測試序列的速度。

3.2 實驗過程設計

（1）實驗一：在測試成本相同的情況下，比較測試覆蓋率

圖7 model5 specialFSMNoLoops—a trichotomous model

①輸入被測模型，確定要生成的測試用例的總長度；

②在ModelJUnit的測試設置中輸入已確定的測試用例總長度并選擇隨機算法，自動生成不同數(shù)目和長度的測試用例；在UPPAAL中使用模擬器，生成測試用例；

③利用ModelJUnit自動生成相應的測試用例總長度下的覆蓋率；記錄下UPPAAL生成的測試序列所覆蓋的遷移對的數(shù)量以及被測模型中遷移對的總數(shù)，通過“覆蓋的遷移對數(shù)目/總的遷移對數(shù)目”來獲取最終的覆蓋率。

（2）實驗二：在測試覆蓋率相同的情況下，比較測試成本

①根據(jù)上述步驟生成測試用例，并得到相應的狀態(tài)覆蓋率、遷移覆蓋率以及遷移對覆蓋率；

②分別記錄每組實驗中兩類方法具有相同的狀態(tài)覆蓋率、遷移覆蓋率、遷移對覆蓋率時測試用例的個數(shù)及總長度；

③根據(jù)所記錄的測試用例個數(shù)和總長度得出測試成本，并對測試成本進行比較。

4 測試用例自動生成方法的定量比較實驗結果及分析

采用隨機方法對被測系統(tǒng)進行多次實驗，統(tǒng)計分析兩種方法的結果，在生成序列的覆蓋率及測試成本方面對兩種工具的結果進行對比。

（1）實驗一：在測試成本相同的情況下，比較測試覆蓋率

對5個對象分別進行實驗，得到如表3-7所示的結果，經(jīng)分析可知：

在model1中，當測試成本為3.4時，ModelJUnit的狀態(tài)覆蓋率為66.67%、遷移覆蓋率為50%、遷移對覆蓋率為25%，對應UPPAAL的分別為100%、66.67%、25%；可以看出UPPAAL的狀態(tài)和遷移覆蓋率都高于ModelJUnit，遷移對覆蓋率與ModelJUnit相等。隨著測試成本的增加，UPPAAL狀態(tài)和遷移覆蓋率依舊高于ModelJUnit，當測試成本大于等于8.2時，UPPAAL的遷移覆蓋率也高于ModelJUnit。即在測試成本相同的情況下，UPPAAL的狀態(tài)、遷移以及遷移對覆蓋率都比ModelJUnit高。

在model5實驗中，因為其中包含的狀態(tài)及遷移較多，所以達到全覆蓋的測試成本較高，很難達到全覆蓋。Model5是ModelJUnit自帶的例子，在測試成本為8.4的時候，ModelJUnit的狀態(tài)、遷移以及遷移對覆蓋率都比UPPAAL高，但是隨著測試成本的增加，ModelJU-nit的狀態(tài)、遷移以及遷移對覆蓋率都低于UPPAAL。

表3 model1覆蓋率對比結果

表4 model2覆蓋率對比結果

表5 model3覆蓋率對比結果

表6 model4覆蓋率對比結果

表7 model5覆蓋率對比結果

從model-model5中不同測試成本下所得出的狀態(tài)、遷移以及遷移對覆蓋率的平均值可以看出：除model4中UPPAAL的遷移覆蓋率以及遷移對覆蓋率比ModelJUnit低之外，UPPAAL的狀態(tài)、遷移以及遷移對覆蓋率的平均值都比ModelJUnit高。

在每個模型的不同測試成本實驗中，當測試成本較低時，ModelJUnit有時會比UPPAAL生成測試用例的各種覆蓋率高，可能說明當生成的測試用例數(shù)量少且測試用例的長度較短時，ModelJUnit效果更好。當生成測試用例的數(shù)量增多及長度增加之后，UPPAAL的效果更好。

（2）實驗二：在測試覆蓋率相同的情況下，比較測試成本

如圖8-10所示，由于每個模型的狀態(tài)及遷移數(shù)量不同，所以對每個模型選擇不同狀態(tài)、遷移和遷移對覆蓋率作為標準。每組實驗中，在相同的狀態(tài)覆蓋率以及相同的遷移覆蓋率的情況下，UPPAAL的測試成本小于ModelJUnit；在相同的遷移對覆蓋率的條件下，UPPAAL的測試成本小于ModelJUnit，并且其中UPPAAL生成的的測試用例個數(shù)及測試用例總長度都比ModelJUnit小，說明達到相同的覆蓋率時UPPAAL所需要生成的測試用例更少且更短，更節(jié)約測試成本。當模型的規(guī)模較小時，使用兩種方法的測試成本相差較小，當模型比較復雜時，兩種方法的測試成本差異比較明顯，如model5。

圖8 覆蓋率相同時的測試成本比較

圖9 遷移覆蓋率相同時的測試成本比較

圖10 遷移對覆蓋率相同時的測試成本比較

在簡單模型model1中，模型檢測方法具有更高的狀態(tài)、遷移以及遷移對覆蓋率，同時更節(jié)約測試成本；在中間模型model2中，傳統(tǒng)的方法的遷移對覆蓋率在測試成本較低時比模型檢測方法略高，除此之外，模型檢測方法具有更高的狀態(tài)和遷移覆蓋率，同時更節(jié)約測試成本；在描述簡單Web功能的model3中，得出的實驗結果與model1基本一致；在描述簡單嵌入式系統(tǒng)功能的model4中，傳統(tǒng)的方法的遷移與遷移對覆蓋率整體而言比模型檢測方法略高，模型檢測方法具有更高的狀態(tài)覆蓋率，兩類方法的測試成本差異較小；在較為復雜的model5中，狀態(tài)、遷移和遷移對覆蓋率與生成測試用例的數(shù)目有關，在生成的測試用例數(shù)量極少時，傳統(tǒng)的方法生成測試用例的覆蓋率較高，除此之外，模型檢測方法生成測試用例的覆蓋率更高，整體上模型檢測方法在節(jié)約測試成本方面具有明顯的優(yōu)勢。

5 結語

模型檢測自動化程度高，具有良好的發(fā)展前景，而傳統(tǒng)的方法簡單、通用、具有成熟的理論基礎，但兩類方法都存在狀態(tài)爆炸和冗余問題。兩類方法都可以根據(jù)需求生成測試用例，模型檢測方法還可以針對某個特性生成反例；基于FSM的方法出現(xiàn)較早，且目前已經(jīng)具有比較成熟的理論支撐，模型檢測方法雖然出現(xiàn)較晚，但是發(fā)展較快，且目前的應用也比較廣泛；兩類方法的應用領域都比較廣泛且具有較多的工具支撐，在自動化方面模型檢測方法具有一定的優(yōu)勢；應用這兩類方法都可以簡化測試用例生成的過程，但是也存在一定的問題如冗余、狀態(tài)爆炸等。

就覆蓋率而言，在模型相對較大但測試成本較小時，可以考慮采用基于FSM的方法，其他情況下，模型檢測方法可以得到更高的覆蓋率。就測試成本而言，在隨機情況下且被測系統(tǒng)規(guī)模較小時，兩類方法的測試成本差別不大，可以根據(jù)其他需求進行選擇，但如果系統(tǒng)規(guī)模相對較大，建議選用模型檢測方法以減少測試成本。總之，基于模型檢測的方法是一個可以應用和進一步研究的測試用例自動生成方案。

[1]Kolawa,A.H.,Dorota.Automated Defect Prevention:Best Practices in Software Management[M].2007,Wiley-IEEE Computer Society Press.

[2]Clarke EM,G.O.,Peled D,model checking[M].2001:Cambridge:MIT Press.

[3]Athor.A Systematic Review of Model Based Testing Tool Support[R]

[4]John Callahan,F.S.,Steve Easterbrook.Automated Software Testing Using Model-Checking.in SPIN Workshop，1996[C].

[5]Franco Fummi,G.P.,Andrea Fedeli,Umberto Rossi,Franco Toto.On the Use of a High-Level Fault Model to Check Properties Incompleteness.in 1 st ACM/IEEE International Conference on Formal Methods and Models for Co-Design（MEMOCODE'03）.[C].p.145-152.

[6]Wijesekera,D.,Ammann,Paul,Sun,Lingya,Fraser,Gordon.Relating Counterexamples to Test cases in CTL Model Checking Specifications.in 3rd International Workshop Advances in Model Based Testing,AMOST 2007.July 9,2007-September 12,2007[C].London,United kingdom,Association for Computing Machinery.p.75-84.

[7]Rushby,J.Formal Methods for Test Case Generation.in SRI International.2011.7[C].US

[8]Ammann,G.F.F.W.P.,Issues in Using Model Checkers for Test Case Generation[J].Journal of Systems&Software,2009.

[9]Fraser,G，F(xiàn).Wotawa.Improving Model-Checkers for Software Testing.in Quality Software,2007.QSIC'07.Seventh International Conference on.2007[C].p.25-31.

[10]劉攀等.基于FSM的測試理論、方法及評估[J].計算機學報,2011（06）:965-984.

[11]Santiago,V.,et al.An Environment for Automated Test Case Generation from Statechart-based and Finite State Machine-based Behavioral Models.in Software Testing Verification and Validation Workshop,2008.ICSTW'08.IEEE International Conference on，2008[C].63-72.

[12]Juristo,N.,A.Moreno,S.Vegas,Reviewing 25 Years of Testing Technique Experiments[J].Empirical Software Engineering,2004.9（1-2）:7-44.

[13]Swain,R.P.,Vikas;Kumar Behera,Prafulla;Prasad Mohapatra,Durga,Automatic Test case Generation From UML State Chart Diagram[J].International Journal of Computer Applications,2012.42（7）:26-36.

[14]Aggarwal,M.and S.Sabharwal.Test Case Generation from UML State Machine Diagram:A Survey.in 2012 3rd International Conference on Computer and Communication Technology,ICCCT 2012.2012[C].Allahabad,UP,India:IEEE Computer Society.p.133-140.

[15]郭華,莊雷,張習勇.UPPAAL：一種適合自動驗證實時系統(tǒng)的工具[J].微計算機信息,2006（15）:52-54+190.

A Comparison of Methods for Software Test Case Generation Based on Model

ZHAO He，GAO Wan-ling

（College of Computer Science,Sichuan University,Chengdu 610064）

With the increase of scale and complexity of software systems,software test automation is on the agenda,the software test cases generation is an important way to reduce the test cost.It is possible to generate test cases more automatically due to the emergence of model checking techniques and tools.Compares software test case generation approaches based on model checking with the approaches based on Finite State Machine(FSM)model,combines systematic literature review and controlled experimental method to do qualitative and quantitative analysis.Evaluates that the model checking technology has advantages on the degree of automation,flexibility,test coverage and test cost over traditional methods.Using model checking to generate software test cases automatically is a feasible and effective method.

Software Test Automation;Automatic Test Case Generation;Model-Based Test Case Generation;Model Checking;Finite State Machine

1007-1423（2017）04-0020-07

10.3969/j.issn.1007-1423.2017.04.005

趙鶴（1992-），女，吉林長春人，本科，研究方向為軟件質(zhì)量保障與測試

2016-12-06

2017-01-20

高婉玲（1992-），女，河南新鄉(xiāng)人，本科，研究方向為軟件質(zhì)量保障與測試