逆向模型测试中的测试用例集生成方法

王 立 新

(安徽建筑大学 电子与信息工程学院，安徽 合肥 230022)



逆向模型测试中的测试用例集生成方法

王 立 新

(安徽建筑大学 电子与信息工程学院，安徽 合肥 230022)

简要介绍了逆向建模测试的相关概念；给出了逆向建模测试的过程；系统介绍了逆向建模测试过程中测试用例生成的方法；提出了一种利用参数约束关系的逆向建模测试用例集精简方法，并给出了该方法的相关实验数据。

逆向建模；软件测试；组合覆盖测试

对于开发时间较早的现在仍在应用的软件和组件，很多都存在这样那样的问题，归纳起来包括：文档完整性欠缺，存在信息不一致问题，有的软件还多次打补丁，给软件使用造成比较多的麻烦。然而，这些历史遗产又不能完全抛弃，有时候是需要建立模型的以便于扩充功能、修正错误等，但由于上述问题，要使用一般的正向建立模型的方法是不可行的，这就产生了如何建立模型的问题。

而逆向模型测试[1]就是从欠缺完整性的文档，在可能存在不一致的信息中构造出测试用例，再运行测试用例并获取系统的动态信息，最终构建出系统的动态模型，在多次与用户目标需求迭代比较和修正后，获得系统或组件的模型以及其它信息。

1 逆向建模测试的过程

逆向测试过程一般可分为以下几个阶段，如图1所示。

图1 逆向测试过程

(1)从使用手册、设计说明等不完整的文档中提取测试用例，这个步骤是逆向测试第一步；

(2)测试这些用例；

(3)获取运行测试用例过程中的运行结果和动态数据，存储于结果数据数据库，为后面的系统分析起支撑作用；

(4)对测试的结果数据进行梳理并进行整理后存储在库中，这是由于动态的状态变化数据信息很大，需要数据库来存储和处理；

(5)处理测试数据，获取初步的系统模型；

(6)根据现有文档和所预测的初步模型比对，对初步模型进行修正以及精细化；

(7)对修正后系统模型进行分析，重新从分析结果中得到新的用例；

(8)这步是在前面步骤之后，用新的用例转(2)再测试。

多次的迭代测试之后，修改出错和偏差，逐渐逼近满足需要的模型和规格，直至达到用户的需求为止。

从逆向建模的测试过程来看，测试用例是逆向建模的基础和关键。但是由于没有文档或者文档不完全，造成了测试用例的生成困难。因此对于逆向建模的测试用例集的获取就是一个比较棘手的问题。

2 逆向建模的测试用例获取和组合爆炸

一般情况下，根据逆向工程[2]的步骤，我们可以首先从文档中获取相关的输入和输出信息，然后再组织成为测试用例，这是首先想到的可利用信息，除此之外，我们还可以从多处获取用于生成测试用例的信息，比如系统的界面和胶水代码等。这些信息的获取就是我们生成初始测试用例的基础，也是我们精细化模型的基础。

我们分析这些信息以后，利用这些信息来组合、进行系统或者组件的黑盒测试是最为方便的。也就是对系统或组件的输入信息进行组合，然后运行系统或组件，考察输出的信息或者状态结果信息。也即对输入信息进行组合从而获取测试用例集是最为可行和有效的方法。

组合测试[3]也称为组合覆盖测试，根据不同的组合参数数目k(1≤k≤n)，可分为：(a)单参数覆盖、(b)双参数组合覆盖、 (c)n维参数全组合覆盖等。在组合覆盖测试中，全组合覆盖测试是最完全和最彻底的。

通常情况下，如输入参数很少的情况下，那么全组合覆盖测试集的测试用例数目是可以接受的，但对于组合参数数目较多的情况下，参数组合爆炸的难题就出现了，很多情况下，就是由于测试组合用例数目太大而使得测试工作不可能完成。

图2是一个学生信息注册界面。如果性别2个选项，出生年有46个选项，月份12个选项，日平均30个选项，籍贯34个选项，市(区)平均有12个选项，学院有7个选项，系平均3个选项，专业有24个选项，学籍状况有3个选项，那么我们初步计算一下，输入选项的全组合大概有2.0431595*E10，这时的情形就是组合爆炸，对于这样一个天文数字的组合信息，组合测试不可能进行的。

那么为了软件测试高效性和可行性，R. Mandl[4]首次提出了双参数组合(成对组合)测试概念，即对参数的所有取值进行两两组合，在满足覆盖准则要求的情况下，生成元素的两两组合覆盖测试用例集来测试软件。Kuhn D. R.等则发现大约20 %～40 %的系统或者组件出错或者故障是由某单个参数引起的，七成左右的出错或故障由某2个参数引起的，而九成以上出错或故障是由2或3个参数作用引起的[5]；而Cohen[6]、史亮[7]等人也取得了不少的研究成果。成对组合覆盖测试用例集的生成最有名的方法包括AETG[8]、IPO和PSST[9]等。

图2 学生学位审查系统注册界面

3 基于参数约束的精简方法

3.1 无效参数组合的概念

尽管单参数覆盖测试和成对组合覆盖测试或者三参数组合覆盖测试能以数目可以接受的测试用例来测试待测的软件系统或组件，但很多情况下也需要更全面的测试，也有参数较多的情况下，成对组合覆盖的用例数目也是不能令人满意的，于是很多研究者提出了各种精简组合测试用例集的方法。在图2的界面中，我们可以看到一些参数组合是不成立的，即不可能用来进行测试的，如1999年2月30日(1999，2，30)就是无效组合，这是因为在系统或者组件程序内部大多已经有代码对此进行约束了，而在一些组合测试方法中，测试用例的生成大多数未考虑有参数依赖的情况。而在用没有考虑参数约束的组合测试用例集中，就会包含无效的参数组合的用例，如果利用输入参数的约束关系消除这些测试用例，可以减少测试用例集中的用例数，提高测试的效率，这对测试是很有利的。

输入选取图2中的性别(男，女)、出生年(1951等46个)、学籍状况(在读、休学、毕业)、学院(电信等7个)和专业(计算机科学与技术等24个)5个参数的情况下，如果生成全组合覆盖测试用例，其测试用例数目是不可接受。我们采用微软公司的PICT软件生成的2维组合用例，尽管输入参数不多，但最终的成对组合测试用例是1584个，这其中含有部分无效的2维输入参数组合，需要对其进行精简。

图2中，在籍贯的省和市中就存在参数之间的约束关系，如选取江苏省，那么合肥就不能在组合测试用例中产生，这时因为模块内的代码体现了约束关系，使得省和省内的城市关联起来，在界面的下拉列表中选取了江苏省后，就不会在市的下拉列表中出现非江苏省的城市。同样，年、月和日的下拉列表中也会体现约束关系，如(1999年，2月，29日)、(1999年，2月，30日)和(1999年，2月，31日)等这样的输入参数的组合等。那么如果我们输入的测试用例中包含(江苏省，合肥市)或(2月，30日)这样的组合，那么在界面上输入不了，也就是不可能进行测试。更进一步地说，就是需要我们在k维参数组合测试用例来测试集生成以后，需要检查是否包含了无效的参数组合，如果有的话，需要在测试用例集中剔除。也即我们可以基于参数间的约束关系，能够不同程度地精简测试用例集。对于上文中的无效参数组合也可以用来测试胶水代码的正确性，将另文研究。

3.2 输入参数之间的依赖关系

那么怎样找出这些输入参数之间的约束关系呢？通过图2中的输入参数进行了约束关系的分析，我们选择了几个关键性的输入参数对它们进行组合测试，并获取它们之间的约束关系。

我们对输入参数约束关系进行符号化标记：例如xy表示输入参数值x约束y参数值(属oneone)；如x∧yz表示输入参数值x和y共同约束参数值z(属manyone型)；如zx∧y表示输入参数z约束x和y( 属onemany)；如x∧yz∧w表示x和y值约束输入参数值z和w(manymany属)。

在具体的图2的界面中，有“南京”“苏州”和“扬州”等城市受到“江苏”的约束；在出生日期的年月日输入参数组合上，“日(1-31)”受到“月(1-12)”的一些月份的约束，比如：1-28日在所有的月份都有效，可以成对组合，但29日不但受到月份为“2”的约束，还受到年份的约束，但30日和31日只是在其它月份出现，不会出现在“2”月份。而2月29日的出现，如果认定它是合法的，那么还要检查年份是否是闰年，闰年符合条件a：能被4整除而不能被100整除；b：能被400整除。故月和日组合(2，30)和(2，31)就是无效的成对组合，年月日组合(2015，2，29 )也是无效的三组合。

3.3 利用约束关系的精简测试用例集

输入参数约束关系可以用来对k维组合测试用例集进行精简。主要有两种方式：第一种方式是首先生成输入参数的全组合的集合，此时，这些组合集中有无效参数的组合，需要逐一检查剔除，然后根据覆盖率的要求，再从中删除一些组合；

第二种方式是在算法生成k维组合用例的同时，及时测校当前k维的参数组合是否含有无效的约束关系，如包含无效约束，则重新生成k维的参数组合，如不包含无效组合，则是最终的测试用例集的一员，直到达到组合覆盖率的要求为止。

第一种方式算法条理清晰，实现起来比较简单，但算法的时间复杂度较高，特别是输入参数比较多的情况下，往往时效上不可接受。第二种方式，需要在检测当前的参数组合是否有效的同时，也检查组合覆盖率，时效性相对较好。

第二种精简组合用例方式的算法如下：

(1)根据输入参数之间依赖集，生成无效参数组合集；

(2)生成k维参数组合；

(3)对该k维参数组合进行如下步骤：

a.检测每个无效参数组合是否在该参数组合中；

b.如果该参数组合中有无效参数组合就剔除，并且转(2)；

c.否则就把该组合加到测试用例集中，并且检查组合覆盖率是否达到，如果没有达到要求的覆盖率则转2；否则转4；

(4)程序结束。

4 实验研究

在第2节的图2中，包含2个Text文本框、10个ComboBox单选下拉列表，还有2个按钮，包括：性别，出生年、月、日，籍贯的省、市，学院、系、专业和学籍状况。出生日期(年月日)，省和市(区)的约束关系在被测的系统程序中或模块之间已经体现，在界面上就不会输入这些无效组合。在上述实验实例中，我们就参数之间的约束关系对其中6个输入控件的参数值之间进行细致严密的分析，分析出它们之间的约束类型，并且由此能生成k维的输入参数依赖关系集。

具体的约束关系见表1：例如：日期中的日受到月份的约束，日也受到年份的约束；籍贯中的市受到省的约束；不同的系分属不同的学院，故系受到学院的约束；而专业分属不同的系来招生管理，因此专业受到系的约束；学籍状况包含在读、休学和毕业，一般学校都有学生在校修学的最长期限，不可能有超过6年还在读的现象等，因此学籍状况受到出生年月日的约束等；当前学历和出生年月日有约束关系等。这些约束关系不仅可以帮助软件和组件使用者正确地使用，还可以在逆向构建模型时，对组合测试用例的精简起到很大的帮助。

表1 学籍查询系统学生界面的输入参数约束关系

我们在以上的这些约束关系中，抽出了一些约束关系，并对相关输入参数进行相应的取值：(1)性别(S)：男，女；(2)出生年(Y)： 1951,1952,1953,…,1988,2016； (3)学籍状况(SS)：在读，毕业，休学；(4)当前学历(E)：高中，中专，大专，本科，双学士，硕士；(5)专业(P)：计算机科学与技术，网络工程，土木工程，经济管理，园林设计，材料工程，动画设计，机械工程，自动化，财务管理……(专业24个)；(6)学院(X):电信学院, 机电学院, 材化学院, 管理学院, 法政学院, 数理学院, 建筑土木学院。

在这个实例系统界面中，为测试的高效和方便，利用这些输入参数的约束关系，要把全组合测试用例集和二维组合测试用例集中包含无效组合的用例剔除出来，实验结果如下：

实验1：全组合测试用例生成和精简： 全组合用例数A：21*461*31*61*241*1=39744 约束关系数： 4 精简后用例数R：约等于39 744-19 008-5 184=15 552 R/A (%)：39.1

实验2：成对组合测试用例生成和精简： 生成的成对组合用例数P：1 584 约束关系数：4 成对组合用例集中包含无效参数组合的用例数：552 不影响覆盖率而剔除的无效用例数：305 精简后用例数R：1 279 R/P (%)：<80.7

上述实验的测试用例数还是比较大的，本实验只是用来说明用输入参数的依赖关系可以精简测试用例集。实验结果表明，利用此方法可在测试用例数目上，使全组合和二维组合用例集得到不同程度地精简。本实验中，用例集精简后的用例数和精简前的用例数之比分别为39.1%和小于80.7%，这说明该方法具有实用价值。

5 总结

在逆向建模测试过程中，测试用例的生成和精简是一个不可回避的问题。在本文中详细地叙述了通过各种方式可以获得系统和组件的输入信息，并利用参数约束关系来精简成对组合测试用例集。从实验数据来看，在一些情况下利用输入参数的约束关系来精简组合测试用例集的方法是可行的。

[1] BERTOLION A. Software testing research:Achievements,challenges,dreams[C]. New York：Future of Software Engineering,IEEE,2007:85-103.

[2] 刘明. 软件逆向工程分析技术研究及应用[J].航空计算技术,2011,41(2):93-95,104.

[3] NORITAKA K,TATSUHIRO T,TOHRU K.A new method for constructing pair-wise covering designs for software testing[J].Information Processing Letters,2002,81(2):85-91.

[4] MANDL R.Orthogonal latin squares:An application of experimental design to compiler testing[J].Communications of the ACM，1985,28(10):1054-1058.

[5] KUHN D R,WALLACE D R.Software fault interactions and implications for software testing[J].IEEE Transactions on Software Engineering,2004,30(6):418-421.

[6] COHEN D,DALAL S R,FREDMAN M L,et al.The AETG system:An approach to testing based on combinatorial design[J].IEEE Transaction on Software Engineering,1997,23(7):437-444.

[7] 史亮.基于解空间树的组合测试用例生成[J].计算机学报,2006,29(6):849-857.

[8] TAI K C,YU L.A test generation strategy for pairwise testing[J].IEEE Transactions on Software Engineering,2002,28(1):109-111.

[9] 于秀山,于洪敏.软件测试新技术技术与实践[M].北京:电子工业出版社,2006:13-17.

Test Case Generation Method in Reverse-model Test

WANG Lixin

(School of Electronic and Information Engineering, Anhui Jianzhu University, Hefei Anhui 230022, China)

Firstly the concept of reverse modeling test is briefly introduced, and then the process of reverse modeling and testing is described. The method of test case generation in the process of reverse modeling is presented, and a reduction method of test suite based on parameter constraint is also given. At last the experimental data of this method are shown.

reverse modeling; software testing; combined coverage testing

2017-03-17

安徽省教育厅自然科学基金(KJ2011B041)；安徽建筑大学博士及引进人才基金资助项目(建院函(2012)33号)；安徽省教育厅自然科学研究重点项目(KJ2016A155)

王立新(1966-)，男，安徽合肥人，副教授，博士，主要从事软件测试研究。E-mail:wlxhs@ahjzu.edu.cn

TP301.6

A

1004-2237(2017)03-0022-05

10.3969/j.issn.1004-2237.2017.03.005