基于模型的软件测试用例生成方法比较研究

赵鹤，高婉玲

（四川大学计算机学院，成都 610064）

基于模型的软件测试用例生成方法比较研究

赵鹤，高婉玲

（四川大学计算机学院，成都 610064）

随着软件系统的规模和复杂度的增加，软件测试的自动化提上日程，软件测试用例的自动化生成成为降低测试成本的重要途径。模型检测技术和工具的出现，使得软件测试用例的生成更加自动化。本文对基于模型检测技术的测试用例自动生成方法进行评估，与传统的基于有限状态机（FSM）模型的测试用例自动生成方法进行比较，采用系统文献综述和可控实验的方法，进行定性和定量的比较分析。结果显示，基于模型检测技术的测试用例自动生成方法在自动化程度、测试覆盖率、测试成本等方面都具有优势，是一种可以应用和进一步研究的测试用例自动生成方案。

软件自动化测试；测试用例自动生成；基于模型的测试用例生成；模型检测；有限状态机

0 引言

软件自动化测试是把人工的测试行为转化为自动执行的一种过程，一般使用特殊的软件（与被测软件分离）控制测试的执行，以及实际结果与预测结果的比较[1]。软件自动化测试主要用于回归测试，目的是分担在保证软件质量的前提下，缩短测试周期，降低测试成本。测试用例是一个描述输入、执行操作以及期望输出的文档，用于判断程序的某个属性是否能够正常的执行。测试用例的自动生成是指使用形式化方法，自动化的构建测试用例，是软件自动化测试的关键和难点。

基于模型的测试用例自动生成是一种重要的方法，包括传统的基于模型的方法和新的基于模型检测技术的方法。软件模型是用形式化的方法对软件特征的抽象和刻画，常见的、可用于测试用例生成的软件模型包括：FSM模型、UML模型以及Markov模型等。模型检测采用状态空间搜索的方法检测一个给定的模型是否满足某个特定的属性[2]。模型检测技术通过分析模型的整个状态空间来判断给定的模型是否满足某个属性，如果属性没有得到满足，模型检测将会生成反例。对于测试而言，反例可以被看作是测试用例。

本文的研究范围及目标是：对功能测试环境下基于FSM模型的测试用例生成方法以及基于模型检测的测试用例生成方法进行比较，进而对基于模型检测的测试用例生成方法进行评估。

1 测试用例自动生成方法的定性分析

本文在评估基于模型检测技术的测试用例自动生成方法时，采用系统文献综述[3]方法，对现有文献中的相关内容进行综述，从定性的角度评估方法。

图1 文献年代分布对比图

如图1，基于FSM模型的测试用例生成方法起源较早，2006之后发展趋于平缓，目前已较为成熟。模型检测技术应用于测试用例生成起源于1996年，从2001年之后发展很快，目前相关研究也较多。

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

表2 基于模型检测的方法部分文献作者分布表

从表1和表2可以看出：在基于FSM模型方法相关的220篇文献中，发表过一篇文献的占总数的47.27%，2篇的占26.82%，发表过7篇文献的作者仅占总数的0.91%。在基于模型检测技术相关的206篇文献中，发表过一篇文献的占总数的72.33%，发表过7篇文献的作者仅占总数的0.49%。说明很多学者都有对这个话题进行研究，但是专注于此方面的作者却很少，还没有形成一个核心的作者群。

图2基于FSM/模型检测的测试用例生成中文献数量排名前几位的作者及篇数。

从图2可以看出：Vijaykumar，N.L（7篇）和Huaikou，Miao.（7篇）这两位作者在基于FSM模型方法中出现的频次相对较高，Fraser，G.（6篇）和Liping，Li.、Saab, D.G.、Wotawa,F.（5篇）这几位作者在基于模型检测方法中出现的频次相对较高，说明这几位作者及其团队对这两个领域相关的研究较多，它们所编写的文献对于这两类方法具有一定的指导意义。

图2 基于FSM/模型检测的测试用例生成中文献数量排名前几位的作者及篇数

2 测试用例自动生成方法的定性分析结果

发展历程。基于FSM的测试用例生成方法是最早出现并得到应用的，目前已经具有比较成熟的理论基础。七十年代末开始，各类基于FSM、EFSM模型的测试用例生成算法逐步出现，主要有T方法、U方法、D方法、W方法等。基于模型检测的测试用例生成方法出现较晚，但是发展较快，目前的应用也比较广泛。1996年Callahan[4]等人最早提出了使用模型检测来自动生成测试用例，随后越来越多的方法被提出并得到了应用。针对数字系统，一个基于模型检测的保证高效覆盖的测试用例覆盖方法被提出[5]。Wijesekera等人利用模型检测生成的反例和测试用例之间的形式化关系，用CTL公式得到测试需求，将测试用例集和与需求有关的反例进行覆盖，从而可以获得满足测试准则的测试集[6]。John Rushby提供了使用模型检测生成用于检测软/硬件的有效的测试集的方法[7]。

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

应用领域。均可应用到通信协议、Web应用、实时系统、控制系统、嵌入式系统中，基于模型检测的方法的应用逐渐扩大到软件的开发设计和系统的安全特性验证，但是基于FSM的方法在工业界中的实际应用较少。

优缺点。基于模型检测的方法自动化程度高，能够产生反例，可以减少测试时间、提高测试效率。但在测试用例生成过程中会出现状态爆炸问题[8]，也有可能产生大量的冗余[9]，另外时间的引入也会增加测试模型的复杂性。基于FSM的方法跟模型检测一样也可能产生大量的冗余，不仅如此，使用该方法生成测试用例还需要测试人员具备一定的理论基础，且缺乏通用的工具支持[10]；但是基于FSM的方法简单[11]、敏捷，有成熟的理论基础。

3 测试用例自动生成方法的定量比较分析

本文采用比较实验，一方面，在针对同一个系统、生成同样数量（长度）的测试用例条件下，比较两种方法生成的测试用例的状态覆盖率、迁移覆盖率、迁移对覆盖率。另一方面，在针对同一个系统、保证测试覆盖率相同的情况下，比较两种方法生成的测试用例的数量（长度），即在测试成本上的差异。

3.1 实验对象及工具选择

被测系统的选择考虑典型实例，覆盖状态及迁移的类型、有环/无环、简单模型、复杂模型、真实模型等，具体模型图3-7所示。

图3 model1简单模型[10]

图4 model2中间模型

图5 model3 Web应用实例—招聘信息发布系统

图6 model4 Soft Drink vending machine[13]

分别选取ModelJunit和UPPAAL[14]作为传统的基于模型的方法和模型检测方法的工具代表，ModelJUnit开源工具以图形化的界面更加直观的展现状态之间的变化，相对于其他工具而言，可以实现更多类型的覆盖，可以控制生成测试序列的速度，使用非常方便，可与Eclipse软件结合使用。UPPAAL在时间和空间上的性能是比较高[15]，而且可以模拟生成不同的测试序列，并控制生成测试序列的速度。

3.2 实验过程设计

（1）实验一：在测试成本相同的情况下，比较测试覆盖率

图7 model5 specialFSMNoLoops—a trichotomous model

①输入被测模型，确定要生成的测试用例的总长度；

②在ModelJUnit的测试设置中输入已确定的测试用例总长度并选择随机算法，自动生成不同数目和长度的测试用例；在UPPAAL中使用模拟器，生成测试用例；

③利用ModelJUnit自动生成相应的测试用例总长度下的覆盖率；记录下UPPAAL生成的测试序列所覆盖的迁移对的数量以及被测模型中迁移对的总数，通过“覆盖的迁移对数目/总的迁移对数目”来获取最终的覆盖率。

（2）实验二：在测试覆盖率相同的情况下，比较测试成本

①根据上述步骤生成测试用例，并得到相应的状态覆盖率、迁移覆盖率以及迁移对覆盖率；

②分别记录每组实验中两类方法具有相同的状态覆盖率、迁移覆盖率、迁移对覆盖率时测试用例的个数及总长度；

③根据所记录的测试用例个数和总长度得出测试成本，并对测试成本进行比较。

4 测试用例自动生成方法的定量比较实验结果及分析

采用随机方法对被测系统进行多次实验，统计分析两种方法的结果，在生成序列的覆盖率及测试成本方面对两种工具的结果进行对比。

（1）实验一：在测试成本相同的情况下，比较测试覆盖率

对5个对象分别进行实验，得到如表3-7所示的结果，经分析可知：

在model1中，当测试成本为3.4时，ModelJUnit的状态覆盖率为66.67%、迁移覆盖率为50%、迁移对覆盖率为25%，对应UPPAAL的分别为100%、66.67%、25%；可以看出UPPAAL的状态和迁移覆盖率都高于ModelJUnit，迁移对覆盖率与ModelJUnit相等。随着测试成本的增加，UPPAAL状态和迁移覆盖率依旧高于ModelJUnit，当测试成本大于等于8.2时，UPPAAL的迁移覆盖率也高于ModelJUnit。即在测试成本相同的情况下，UPPAAL的状态、迁移以及迁移对覆盖率都比ModelJUnit高。

在model5实验中，因为其中包含的状态及迁移较多，所以达到全覆盖的测试成本较高，很难达到全覆盖。Model5是ModelJUnit自带的例子，在测试成本为8.4的时候，ModelJUnit的状态、迁移以及迁移对覆盖率都比UPPAAL高，但是随着测试成本的增加，ModelJU-nit的状态、迁移以及迁移对覆盖率都低于UPPAAL。

表3 model1覆盖率对比结果

表4 model2覆盖率对比结果

表5 model3覆盖率对比结果

表6 model4覆盖率对比结果

表7 model5覆盖率对比结果

从model-model5中不同测试成本下所得出的状态、迁移以及迁移对覆盖率的平均值可以看出：除model4中UPPAAL的迁移覆盖率以及迁移对覆盖率比ModelJUnit低之外，UPPAAL的状态、迁移以及迁移对覆盖率的平均值都比ModelJUnit高。

在每个模型的不同测试成本实验中，当测试成本较低时，ModelJUnit有时会比UPPAAL生成测试用例的各种覆盖率高，可能说明当生成的测试用例数量少且测试用例的长度较短时，ModelJUnit效果更好。当生成测试用例的数量增多及长度增加之后，UPPAAL的效果更好。

（2）实验二：在测试覆盖率相同的情况下，比较测试成本

如图8-10所示，由于每个模型的状态及迁移数量不同，所以对每个模型选择不同状态、迁移和迁移对覆盖率作为标准。每组实验中，在相同的状态覆盖率以及相同的迁移覆盖率的情况下，UPPAAL的测试成本小于ModelJUnit；在相同的迁移对覆盖率的条件下，UPPAAL的测试成本小于ModelJUnit，并且其中UPPAAL生成的的测试用例个数及测试用例总长度都比ModelJUnit小，说明达到相同的覆盖率时UPPAAL所需要生成的测试用例更少且更短，更节约测试成本。当模型的规模较小时，使用两种方法的测试成本相差较小，当模型比较复杂时，两种方法的测试成本差异比较明显，如model5。

图8 覆盖率相同时的测试成本比较

图9 迁移覆盖率相同时的测试成本比较

图10 迁移对覆盖率相同时的测试成本比较

在简单模型model1中，模型检测方法具有更高的状态、迁移以及迁移对覆盖率，同时更节约测试成本；在中间模型model2中，传统的方法的迁移对覆盖率在测试成本较低时比模型检测方法略高，除此之外，模型检测方法具有更高的状态和迁移覆盖率，同时更节约测试成本；在描述简单Web功能的model3中，得出的实验结果与model1基本一致；在描述简单嵌入式系统功能的model4中，传统的方法的迁移与迁移对覆盖率整体而言比模型检测方法略高，模型检测方法具有更高的状态覆盖率，两类方法的测试成本差异较小；在较为复杂的model5中，状态、迁移和迁移对覆盖率与生成测试用例的数目有关，在生成的测试用例数量极少时，传统的方法生成测试用例的覆盖率较高，除此之外，模型检测方法生成测试用例的覆盖率更高，整体上模型检测方法在节约测试成本方面具有明显的优势。

5 结语

模型检测自动化程度高，具有良好的发展前景，而传统的方法简单、通用、具有成熟的理论基础，但两类方法都存在状态爆炸和冗余问题。两类方法都可以根据需求生成测试用例，模型检测方法还可以针对某个特性生成反例；基于FSM的方法出现较早，且目前已经具有比较成熟的理论支撑，模型检测方法虽然出现较晚，但是发展较快，且目前的应用也比较广泛；两类方法的应用领域都比较广泛且具有较多的工具支撑，在自动化方面模型检测方法具有一定的优势；应用这两类方法都可以简化测试用例生成的过程，但是也存在一定的问题如冗余、状态爆炸等。

就覆盖率而言，在模型相对较大但测试成本较小时，可以考虑采用基于FSM的方法，其他情况下，模型检测方法可以得到更高的覆盖率。就测试成本而言，在随机情况下且被测系统规模较小时，两类方法的测试成本差别不大，可以根据其他需求进行选择，但如果系统规模相对较大，建议选用模型检测方法以减少测试成本。总之，基于模型检测的方法是一个可以应用和进一步研究的测试用例自动生成方案。

[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.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：一种适合自动验证实时系统的工具[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-），女，吉林长春人，本科，研究方向为软件质量保障与测试

2016-12-06

2017-01-20

高婉玲（1992-），女，河南新乡人，本科，研究方向为软件质量保障与测试