趙鶴，高婉玲

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610064）

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

趙鶴，高婉玲

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610064）

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

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

0 引言

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

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

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

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

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

圖1 文獻(xiàn)年代分布對比圖

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

表1 基于FSM模型的方法部分文獻(xiàn)作者分布表

表2 基于模型檢測的方法部分文獻(xiàn)作者分布表

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

圖2基于FSM/模型檢測的測試用例生成中文獻(xiàn)數(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)的頻次相對較高，說明這幾位作者及其團(tuán)隊(duì)對這兩個(gè)領(lǐng)域相關(guān)的研究較多，它們所編寫的文獻(xiàn)對于這兩類方法具有一定的指導(dǎo)意義。

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

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

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

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

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

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

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

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

3.1 實(shí)驗(yàn)對象及工具選擇

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

圖3 model1簡單模型[10]

圖4 model2中間模型

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

圖6 model4 Soft Drink vending machine[13]

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

3.2 實(shí)驗(yàn)過程設(shè)計(jì)

（1）實(shí)驗(yàn)一：在測試成本相同的情況下，比較測試覆蓋率

圖7 model5 specialFSMNoLoops—a trichotomous model

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

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

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

（2）實(shí)驗(yàn)二：在測試覆蓋率相同的情況下，比較測試成本

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

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

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

4 測試用例自動生成方法的定量比較實(shí)驗(yàn)結(jié)果及分析

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

（1）實(shí)驗(yàn)一：在測試成本相同的情況下，比較測試覆蓋率

對5個(gè)對象分別進(jìn)行實(shí)驗(yàn)，得到如表3-7所示的結(jié)果，經(jīng)分析可知：

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

在model5實(shí)驗(yàn)中，因?yàn)槠渲邪臓顟B(tài)及遷移較多，所以達(dá)到全覆蓋的測試成本較高，很難達(dá)到全覆蓋。Model5是ModelJUnit自帶的例子，在測試成本為8.4的時(shí)候，ModelJUnit的狀態(tài)、遷移以及遷移對覆蓋率都比UPPAAL高，但是隨著測試成本的增加，ModelJU-nit的狀態(tài)、遷移以及遷移對覆蓋率都低于UPPAAL。

表3 model1覆蓋率對比結(jié)果

表4 model2覆蓋率對比結(jié)果

表5 model3覆蓋率對比結(jié)果

表6 model4覆蓋率對比結(jié)果

表7 model5覆蓋率對比結(jié)果

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

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

（2）實(shí)驗(yàn)二：在測試覆蓋率相同的情況下，比較測試成本

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

圖8 覆蓋率相同時(shí)的測試成本比較

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

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

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

5 結(jié)語

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

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

[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的測試?yán)碚?、方法及評估[J].計(jì)算機(jī)學(xué)報(bào),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]郭華,莊雷,張習(xí)勇.UPPAAL：一種適合自動驗(yàn)證實(shí)時(shí)系統(tǒng)的工具[J].微計(jì)算機(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-），女，吉林長春人，本科，研究方向?yàn)檐浖|(zhì)量保障與測試

2016-12-06

2017-01-20

高婉玲（1992-），女，河南新鄉(xiāng)人，本科，研究方向?yàn)檐浖|(zhì)量保障與測試