基于变异测试的RESTful Web服务测试数据优化生成方法

刘 靖 陈文杰

(内蒙古大学计算机学院, 呼和浩特 010021)

基于变异测试的RESTful Web服务测试数据优化生成方法

刘 靖 陈文杰

(内蒙古大学计算机学院, 呼和浩特 010021)

为提升基于REST的Web服务系统测试数据生成效率及可用性,提出了一种基于变异测试的测试数据优化生成方法.将RESTful Web服务对应的 Web应用描述语言(WADL)增加数据类型约束,并利用该约束生成初始测试数据.对约束关系进行变异生成变异体,在消除等价变异体并利用聚类实现变异体集约简的基础上,结合贪心算法优化筛选初始测试数据,生成无冗余的RESTful Web服务可用测试数据集.基于Hadoop平台技术,实现了针对RESTful Web服务系统测试数据自动生成的支撑软件.测试执行结果表明,在有效保证测试数据可用且无冗余的基础上,极大缩减了测试数据集规模和测试数据生成时间,完成了针对RESTful Web服务系统的自动化测试数据优化生成,提升了测试生成效率.

测试数据生成;RESTful Web服务;WADL;变异测试

移动 Web服务在电子医疗、突发灾害实时监控等方面具有良好的应用前景[1].部署存在功能隐患或行为缺陷的移动Web服务,势必造成相关服务的运行错误和功能失效.因此,在大范围部署移动Web服务前完成全面的功能测试是至关重要的,而自动生成无冗余、有效可用的测试数据是提升Web服务系统的测试生成效率、保证测试整体效果的基础和关键,能够有效解决测试人员在手工生成测试数据时引入的人为错误和盲目性,并降低测试成本.

实现移动Web服务可选用SOAP或REST两种方式.现有相关研究大都以基于SOAP的WSDL为依据,研究测试数据的生成方法和优化选择.文献[2]基于服务合约来扩展WSDL,设计双方设计合约并根据合约各自展开测试,但该方法需要耗费大量的计算资源,且产生测试数据的类型有限.文献[3]以WSDL中的XSD数据描述为基础,运用约束满足问题技术求解可嵌入测试数据的XML测试执行模板.文献[4]以WSDL等文档为输入抽取变量类型等约束,运用满足性模理论求解工具生成满足不同覆盖标准的测试数据.文献[5-6]研究了组合Web服务中的测试生成及优化选择方法.文献[7]提出了RESTful Web服务的测试框架,为软件测试者提供了集成软件测试过程,但并没有给出详细的测试数据生成方法.RESTful Web服务更适合部署于移动设备上,响应时间和吞吐量等性能都优于SOAP式Web服务[8].

本文采用更适合RESTful Web服务的WADL描述[9]作为测试数据生成的基础,提出了一种基于变异测试的测试数据优化生成方法,并研发了基于Hadoop的测试数据自动生成支撑软件ATD4MW,采用基于遗传算法的聚类技术并结合贪心算法,生成无冗余且规模极大缩减的可用测试数据集.

1 基于WADL扩展的测试数据生成

WADL描述了RESTful Web服务系统所支持的所有资源及对这些资源所执行的操作.用户根据Web服务对应的WADL描述了解其包含的所有资源及服务调用方法.WADL描述文档通常包括4个部分:资源集、资源连接关系、资源操作方法(对资源操作的HTTP方法)及资源表述(资源的MIME类型及其XML Schema).本节首先给出WADL描述扩展方法,即如何增加数据类型约束,然后利用等价类划分及边界分析、错误推测和随机生成等方法,实现了基于约束关系的初始测试数据自动生成.

1.1 WADL中对数据类型约束的扩展

针对RESTful Web服务系统的测试,主要根据WADL中param元素的type属性来生成测试数据.该属性虽然能够描述参数的数据类型,但缺少对类型的约束,因而需要扩展WADL,增加类型约束,以便生成更为有效的测试数据.由于type中的数据类型是在相应的XML Schema中描述的,因此需要在XML Schema上添加restriction元素,以精确描述数据类型的约束关系.XML Schema中的基本数据类型包括数值型(Int,Float,Double等)、字符串型(String)及布尔型(Boolean).不同数据类型所对应的约束不同.数值型约束描述了该类型数据的最大值和最小值;字符串型约束描述了字符串的精确长度或最大最小长度;枚举型约束描述了一个由字符串型、布尔型或数值型元素所组成的元素集合.布尔型数据仅包含2个值,不需要添加额外的约束.

1.2 测试数据的生成策略

1.2.1 简单类型测试数据

首先提取加在简单数据类型上的约束关系;然后根据约束条件,利用等价类划分及边界分析、错误推测和随机生成等方法来生成测试数据.如果数据类型的约束条件不完整,则将该类型数据的默认取值范围作为补充.对于数值型约束,令其最大、最小值分别为VMAX和VMIN,编译器允许取值的上、下界分别为Bup和Bdown,则可生成的测试数据为rand(Bdown,VMIN),VMIN-1,VMIN,VMIN+1,rand(VMIN,VMAX),VMAX-1,VMAX,VMAX+1,rand(VMAX,Bup),0,-1等,其中rand函数随机生成约束范围内的数值.对于字符串型约束,令字符串的最小、最大长度分别为LMIN和LMAX,则生成的测试数据为randStr(LMIN-1),randStr(LMIN),randStr(LMIN+1),randStr(rand(LMIN,LMAX)),randStr(LMAX-1),randStr(LMAX),randStr(LMAX+1)、空串等,其中randStr函数随机生成字符长度约束范围内的字符串.对于布尔类型,测试数据为T和F,分别表示布尔类型的真值和假值.枚举类型一般先选择集合中的首尾2个元素,再在剩余数据中随机选一个数据.

1.2.2 复合类型测试数据

复合类型可基于简单类型或已有复合类型嵌套构成,其中子类型元素的组合方式需要由次序指示器指定.次序指示器分为All,Choice和Sequence三种.其中,All指示器规定复合类型中所有子元素必须且仅出现一次,可以按照任何次序出现,不必与XML Schema中的定义一致;Choice指示器规定在复合类型的全部子元素中仅能随机出现一个;Sequence指示器规定复合类型中每一个元素必须出现一次,次序与XML Schema中规定的一样.在复合型测试数据的生成中,先确定子类型元素的组合方式.若采用All指示器,先随机生成一个子类型元素的序列,并为序列中的每一个子类型生成测试数据集,然后根据序列中元素的次序对子集计算笛卡尔积,从而得到复合类型的测试集.若采用Choice指示器,则在所有子类型中任意指定一个子类型元素,由此生成的测试数据集即为复合类型的测试数据集.若采用Sequence指示器,则为所有子元素逐一生成子测试数据集,然后根据XML Schema中规定的次序对子集计算笛卡尔积,从而得到复合类型的测试数据集.

1.3 测试数据生成算法

本文提出了一个自动生成简单和复合类型测试数据的算法.

算法1 GenTestData输入:参数P. 输出:P的初始测试数据集Tinit.Tinit={}; IF(IsSimpleType(P)){Tp=GetType(P);Rd=InitialRegion(Tp);//返回类型在编译中能处理的范围Rs=GetRestriction(Tp);//获取DataType定义的约束Rd=Rd∩CalRange(Rs);//计算在该约束下的取值区间 //采用等价类划分及边界分析、错误推测和随机方法 //产生简单数据类型的测试数据Tinit=GenForSimple(Rd);} ELSE {TD={};//保存每个子元素生成的测试数据集 //按照3种不同复合类型规则生成测试数据 FOR each SubElement ofPTD=GenTestData(SubElement); IF (IsSequence(P))Tinit=GenSequenceData(TD); ELSE IF (IsAll(P))Tinit=GenAllData(TD); ELSE IF (IsChoice(P))Tinit=GenChoiceData(TD);}

2 基于变异的测试数据优化筛选

测试数据生成过程中由All和Sequence指示器构成的复合类型数据都需要计算笛卡尔积,随着子类型个数的不断增加,最终产生的测试数据集的数据量会呈指数增长,且包含很多重复低效的冗余数据.对测试数据进行筛选,可以消除大量低效冗余的数据,精简测试数据集,从而节约了测试时间和成本.本文利用变异测试技术,为WADL中数据类型增加约束条件,根据Web服务的特征设计变异算子,再将变异算子作用于被测Web服务的程序上得到变异体,通过运行变异体来筛选出无冗余且有效可用的测试数据.

2.1 变异体生成

WADL体现了RESTful Web服务系统的内部逻辑功能,约束的变异等价于Web服务内部逻辑功能的变异.因此,有效可用的测试数据是指能够杀死变异体的测试数据,这些数据能够识别Web服务内部逻辑功能错误.进行约束变异的目的是筛选出识别错误能力强(即杀死变异体多)的数据,剔除重复冗余的数据.

设计变异算子是变异测试技术的关键和基础.在一般的变异测试执行中,变异体的个数与程序代码量的平方成正比,即使最简单的一个程序也会产生大量的变异体,因此执行和存储变异体会耗费大量的内存计算资源.虽然约束变异测试的规模小于一般变异测试,但如果定义了大量低效的变异算子,仍然会产生数量巨大的变异体集合,浪费大量的计算资源.鉴于此,必须定义有效的变异算子来减少变异体的生成数量,从而降低测试开销.针对RESTful Web服务系统的WADL约束特征,本文定义了7个相应的变异算子(见表1).

表1 扩展WADL的变异算子

下面举例说明如何运用上述变异算子产生相应的约束变异体.例如,某Web服务方法的一个参数为x,其约束为Vmin=0,Vmax=30,则参数x的取值范围为030}.使用CAD删除或添加一个约束,得到变异体集{x>0,x<30}.假设该方法存在另一个参数y,约束为Vmin=5,Vmax=7,则参数y的取值范围为5

2.2 等价变异体检测

影响变异测试效果的主要原因是等价变异体的存在.等价变异体不仅会降低变异测试的充分度,长期驻留内存还会耗费大量的计算资源.因此,必须剔除变异体集中的等价变异体,以提高测试效率和变异充分度.此外,手工检测等价变异体耗时耗力且容易出错,因此需要实现等价变异体的自动检测.本文将基于约束的等价变异体检测[10]应用于等价变异体的检测中.

设M是约束C的一个变异体,测试数据d要将变异体杀死,必须满足以下2个条件:

1) 必要性条件,即d在变异处使得M和C产生不同的状态.若状态相同,由于M和C仅在变异处不相同,其他地方完全相同,则M和C的最终状态必然也相同,那么该测试数据d无法杀死变异体M.

2) 可达性条件,即d在M上运行必须能执行到变异处,并可以从该变异处执行到程序结束.这是因为M和C仅在变异处不同,如果d不能执行到变异处,最终状态必然相同;此外,即使在变异处产生了不同状态,如果变异处到程序结束不可达,即不同状态不能传递到程序结束,那么最终状态也必然相同.

假设存在一个测试数据集S能够同时满足必要性和可达性条件.若S不为空集,那么变异体能够被杀死;若S为空集,则变异体为等价变异体,在功能上等价于原始约束.

2.3 变异体聚类

运用变异算子会产生大量的变异体.虽然2.2节中已剔除了等价变异体,但变异体的数量仍然十分巨大,其中许多变异体具有相似的功能,无助于测试数据的筛选,故有必要精简变异体集.在测试数据筛选过程中,需要将数量庞大的测试数据集输入到变异体集上,变异体集的执行会耗费大量的时间和计算机资源.为了减少变异测试的代价,需要在不影响检测力度的情况下执行更少的变异体,对变异集进行约简.因此,本文采用了一种基于遗传算法的聚类技术来实现变异体的约简.

K-means聚类算法的效果与聚类数目K相关,但K值较难确定,本文采用遗传算法自适应地产生K值,并求得该K值下较好的聚类中心,以计算优化的聚类结果.在基于遗传算法的聚类技术中,令D为样本数据的数量,则变异体由长度为D的2进制数字串来表示,染色体由长度为KD的2进制数字串来表示.适应度函数由每个变异体到对应聚类中心的距离和来表示,其值越小越好.随机选择k个变异体作为初始聚类中心,对其余变异体进行聚类处理,得到的结果即为种群的个体,每个个体的形成相当于当前K值下的一次K-means聚类.种群初始化后,通过不断进化,得到当前k值下最好的聚类中心.上述算法思想可描述为如下的GenMutants算法.

算法2 GenMutants输入:聚类数目K;初始染色体集数量MS;样本数据集DS; 适应度距离阈值CS;初始变异体集合Minit.

输出:约简后的变异体集合Mopt.

BEGIN:

Schromes={};//染色体集Scur_opt_means={};//当代最优的聚类中心 //染色体集初始化 FOR(i=1 toMS)Schromes=Schromes∪concat (EncOneMutant (DS),K,Minit); //产生最佳的染色体 DO {Schromes=Crossover (Schromes);Schromes=Mutation (Schromes);Scur_opt_means=Selection (fitness(Schromes)); Evolve_to_nextGen(); } WHILE (fitness(Scur_opt_means)!=0) //探测是否有更优的染色体 IF (fitness(Scur_opt_means)-fitness(Spre_opt_means)>CS) {K=K+1;Spre_opt_means=Scur_opt_means; goto BEGIN; } ELSE {Vopt_clusters=Clustering_KMeans(K,Scur_opt_means);Mopt=RandomSelect(Vopt_clusters,Minit); }

2.4 数据筛选

测试数据杀死的变异体越多,识别错误的能力越强.本文基于贪心算法,提出了一个优化筛选出有效可用且无冗余的测试数据算法OptmizeTestData.

算法3 OptmizeTestData输入:初始测试数据集Tinit,变异体集合M1. 输出:最终测试数据集Tfinal,被Tfinal杀死的变异体集合M2.S=GetSize(Tinit); FOR (q=1 toS) {Dq=GetData(Tinit,q);//从数据集Tinit中获取第q个数据 //在M1上运行Dq,返回被杀的变异体集合KMutantqKMutantq=MutationTest(Dq,M1); }Tfinal={};M2={}; DO { //从KMutant-M2集合里选择杀死变异体个数最多的子集KMutantmax=MAX(KMutant-M2); //数据Dmax为杀死变异体最多的对应数据Tfinal=Tfinal∪Dmax;M2=M2∪KMutantmax; } WHILE (KMutantmaxis not Null)

KMutant={KMutant1,KMutant2,…,KMutants}为当前Tfinal所能杀死的变异体集合.KMutant-M2表示从KMutant中每一个子集删去M2中已被杀死的变异体元素,得到当前Tfinal尚不能杀死的变异体集合.经过循环筛选便可得到优化后的最终测试数据集.需要说明的是,算法OptmizeTestData并不是单纯选择那些杀死变异体最多的测试数据.例如,测试数据T1能够杀死变异体1,2,3,4,9,11;测试数据T2能够杀死1,2,3,4,9;测试数据T3能够杀死13,14,17.采用该算法最终选择的测试数据是T1和T3,而非T1和T2.原因在于,虽然T2杀死变异体的个数比T3多,但对于任意一个T2杀死的变异体,T1都能将其杀死,而T3能杀死新的变异体,故T3的错误检测能力强于T2.

3 测试执行实验及效果分析

本文以一个网上购物RESTful Web服务系统为应用实例,采用ATD4MW软件来生成该服务的测试数据.该Web服务系统包含3个资源:商品资源Pres、用户资源Ures和购买服务资源Bres.通过UserRes资源来管理用户帐户,采用Pres资源的GetProduct方法函数检索商品,利用Bres资源的BuyProcess方法函数购买商品.下文以BuyProcess方法为例,该方法的输入数据为一组名为Product的复合类型,包括String类型的商品名称Pname和Int类型的购买数量Pcount.扩展后复合类型的描述如下:

实验执行硬件为2.5 GHz i7处理器、4 GB内存.共设计如下3组实验:① 购买1种商品;② 购买2种商品;③ 购买3种商品.购买1,2,3种商品分别需输入2,4,6个参数.

实验后的测试生成效果见表2.由表可知,随着输入参数个数的增加,初始测试数据的个数呈指数增长,但采用本文提出的测试数据优化筛选方法可以在保证测试数据可用且无冗余的基础上极大地缩小测试数据集,淘汰掉绝大部分冗余数据.同时,当测试数据量较大时,利用ATD4MW的分布式处理可以有效减短数据筛选时间.

表2 测试生成效果

等价变异检测效果见表3.由表可知,随着输入参数个数的增加,变异充分度出现一定幅度的下降,下降的原因是产生了一定数量的等价变异体.等价变异体的存在不仅会降低变异测试的充分度,而且长期驻留内存还会耗费一定的计算资源和存储资源,因此需要对等价变异体进行剔除,使变异充分度得到提升.但变异充分度未达到100%,原因可能是部分等价变异体没有检测到或由于测试数据不够充分导致该被杀死的变异体没有被杀死或误认为等价变异体.

表3 变异充分度比较 %

随着变异体个数的增加,聚类花费的时间也迅速增加.但由表4可知,经过聚类后变异体个数减少,会直接导致变异测试的时间开销大为降低,故为聚类操作花费的额外时间开销是可接受的.

表4 变异体聚类效果

此外,本文还对GetProduct检索商品方法完成了与上述BuyProcess方法相类似的测试数据生成及优化过程,即设计出一组检索1种商品的实验,获得初始测试数据58个、筛选后测试数据6个,变异充分度为100%.实验结果证明了本文所提方法及支撑工具软件的有效性和可用性.

4 结论

1) 提出了一种基于变异测试技术的RESTful Web服务测试数据优化生成方法，对服务WADL 描述增加数据类型约束，并对约束关系进行变异.

2) 采用聚类技术完成变异体集的约简，并利用贪心算法对初始测试数据进行优化筛选，从而可生成无冗余、有效可用的测试数据集，进而研发了基于Hadoop的测试数据自动生成支撑软件ATD4MW，实现了针对RESTful Web服务的无冗余测试数据集的自动生成.

3) 利用所提的数据优化生成方法及ATD4MW支撑软件，在保证测试数据可用且无冗余的基础上，能够极大缩减测试数据集的规模和测试数据生成时间.

References)

[1]李刚, 孙红梅, 李智, 等. 资源受限Web服务[J]. 计算机学报, 2010, 33(2): 193-207. DOI:10.3724/SP.J.1016.2010.00193. Li Gang, Sun Hongmei, Li Zhi, et al. Resource constrained web services[J].ChineseJournalofComputers, 2010, 33(2): 193-207. DOI:10.3724/SP.J.1016.2010.00193.(in Chinese)

[2]姜瑛, 辛国茂, 单锦辉, 等. 一种Web服务的测试数据自动生成方法[J]. 计算机学报, 2005, 28(4): 568-577. DOI:10.3321/j.issn:0254-4164.2005.04.015. Jiang Ying, Xin Guomao, Shan Jinhui, et al. A method of automated test data generation for web service[J].ChineseJournalofComputers, 2005, 28(4): 568-577. DOI:10.3321/j.issn:0254-4164.2005.04.015.(in Chinese)

[3]Vanderveen P, Janzen M, Tappenden A F. A web service test generator[C]//2014IEEEInternationalConferenceonSoftwareMaintenanceandEvolution. Victoria, Canada, 2014: 516-520. DOI:10.1109/icsme.2014.85.

[4]Zhou L, Xu L, Xu B, et al. Generating test cases for composite web services by parsing XML documents and solving constraints [C]//2015IEEE39thAnnualComputerSoftwareandApplicationsConference. Taichung, China, 2015: 304-309. DOI:10.1109/compsac.2015.51.

[5]许蕾, 李言辉, 陈林, 等. 一种面向用户需求的Web服务测试方法[J]. 计算机学报, 2014, 37(3): 512-521. DOI:10.3724/SP.J.1016.2014.00512. Xu Lei, Li Yanhui, Chen Lin, et al. A testing method for web services focusing on user requirements[J].ChineseJournalofComputers, 2014, 37(3): 512-521. DOI:10.3724/SP.J.1016.2014.00512.(in Chinese)

[6]Ji S, Li B, Zhang P. Test case selection for data flow based regression testing of BPEL composite services [C]//2016IEEEInternationalConferenceonServicesComputing(SCC). San Francisco,CA, USA, 2016: 547-554. DOI:10.1109/scc.2016.77.

[7]Kao C H, Lin C C, Chen J N. Performance testing framework for REST-based web applications[C]//2013 13thInternationalConferenceonQualitySoftware. New York, USA, 2013: 349-354. DOI:10.1109/qsic.2013.32.

[8]Mizouni R, Serhani M A, Dssouli R, et al. Performance evaluation of mobile web services[C]//2011IEEENinthEuropeanConferenceonWebServices. New Orleans, Louisiana, USA, 2011: 184-191. DOI:10.1109/ecows.2011.12.

[9]Hadley M J. Web application description language (WADL)[EB/OL]. (2016-01-08)[2016-085-01]. https://wadl.java.net.

[10]Offutt A J, Pan J. Detecting equivalent mutants and the feasible path problem[C]//11thAnnualConferenceonComputerAssurance. New York, USA, 1996: 224-236.

Mutation testing based test data optimized generation method for RESTful web service

Liu Jing Chen Wenjie

(College of Computer Science, Inner Mongolia University, Hohhot 010021, China)

To promote the efficiency and feasibility of test data generation for the REST(respresentational state transfer) based web service system, a mutation testing based test data optimized generation method is proposed. The web application description language(WADL) corresponding for the RESTful web service system is extended with data type constrains, and the elementary test data sets are generated according to these constrains. Mutants are then generated by mutation testing towards constrain relationship. The equivalent mutants are eliminated and the mutant set reduction is performed by using clustering technology. The elementary test data sets are optimally selected by using the greedy algorithm to generate non-redundant and feasible test data sets for the RESTful web service system. A supporting software for automatic test date generation for the RESTful web service systems is developed based on Hadoop platform technology. The test execution results show that the scale of test data sets and test generation time are greatly reduced with the guarantee of non-redundancy and availability of the test data. The automatic and optimal test data generation for RESTful web service systems is achieved and the test generation is improved.

test data generation; RESTful web service; web application description language(WADL); mutation testing

10.3969/j.issn.1001-0505.2017.03.010

2016-10-05. 作者简介: 刘靖(1981—)，男，博士，副教授，liujing@imu.edu.cn.

国家自然科学基金资助项目(61262017, 61662051)、内蒙古自然科学基金资助项目(2015MS0611).

刘靖,陈文杰.基于变异测试的RESTful Web服务测试数据优化生成方法[J].东南大学学报(自然科学版),2017,47(3):472-477.

10.3969/j.issn.1001-0505.2017.03.010.

TP393

A

1001-0505(2017)03-0472-06