基于程序规则说明的自动测试用例生成

收稿日期:2005211209作者简介:金虎(1974-),男,2003级博士研究生,研究方向为计算机网络,网络安全,软件下载.文章编号:　049026756(2006)0420768205基于程序规则说明的自动测试用例生成金　虎2,李志蜀2,李　奇1(1.四川师范大学软件重点实验室,成都610066;2.四川大学计算机学院,成都610064;3.成都信息工程学院计算机系,成都610041)摘要:自动测试过程中,在特定测试标准下生成的测试用例的质量优劣,将极大地影响测试的性能和结果.作者结合基于程序规则说明的两种测试方法———随机测试技术和决策表技术,利用决策表形成完备的测试标准,保证随机生成的测试用例的充分性,完成测试用例的自动生成过程.研究内容分为如下4个部分:(1)基于软件规则说明的自动测试技术分析;(2)对程序规则说明生成决策表方法的测试标准;(3)结合随机测试数据生成和决策表技术对自动生成测试用例进行分析,比随机生成测试用例方法有更好的效果.关键词:规则说明;决策表;自动软件测试中图分类号:TP393 文献标识码:A软件测试是在特定条件和标准下对软件进行验证的行为.通过构造测试数据运行软件以找出软件中的缺陷和错误是种基本的测试方法.手工构造测试数据费时而且工作量大,因此自动测试技术受到广泛关注.自动测试通常包括3个部分[1]:(1)测试用例的自动生成;(2)使用测试用例对测试程序的执行;(3)将运行结果与测试预测比较得到测试结果评测.在基于程序规则说明的自动测试技术研究中,自动测试过程还没形成公认的标准,存在下述的问题:(1)测试标准的选择;(2)测试用例生成的充分性;(3)自动测试过程的设计.这些问题增加了自动测试过程实现的困难.没有确定的测试标准,就无法判定测试用例集的充分性,也就不能决定自动测试过程该何时结束.针对上述问题,我们利用功能测试方法中的决策表技术帮助选择测试标准,用以对测试用例充分性的图1　基于程序规则说明的软件测试过程Fig.1　S pecification 2based SW testing process保证,并作为自动测试过程的结束条件.1　基于软件规则说明的自动测试技术 测试是在特定的条件和标准下的一系列行为.在基于程序规则说明的测试过程中,程序规则说明是测试的基础,程序的实现和测试都根据规则说明.基于程序规则说明的测试过程如图1所示.基于程序规则说明的测试方法近来受到广泛的关注,具有开放、灵活和易于过程控制等许多优点.但传统程序规则说明的表示并不严密,甚至可以是自然语言描述,难以实现自动测试过程.实际研究中,常用有三种形式化的表示方法:基于模型的规则2006年8月第43卷第4期四川大学学报(自然科学版)Journal of Sichuan University (Natural Science Edition )Aug.2006Vol.43　No.4说明测试技术,代表性语言是Z 与VDM ;基于状态的规则说明测试技术,强调对软件系统的状态和状态转移的描述;基于属性的规则说明测试技术,强调对于功能模块关系的语法分析.我们使用第一种方法进行描述.2　决策表技术用于测试用例充分性判定测试用例被定义为输入/输出对,输入是出现在程序输入指令中的变量,输出则是程序的运行结果或行为.自动测试过程中,从形式化的软件规则说明生成测试用例是一个关键问题,不完备的测试用例无法保证测试结果的可靠性,将直接影响测试结果的有效性.定义1　设程序Q 的所有输入变量为x 1,x 2,…,x n ,其中x i ∈Dx i .则称D =Dx 1×Dx 2×…×Dx n 为程序Q 的输入域空间.程序Q 一次实际的合法输入对应于输入域D 空间上的一点x ∈D [2].对于确定的程序,其输入变量空间的数据集合通常是无限的.采用穷举输入域空间的方法,虽然可以保证完备性,却因为此空间太大而缺乏可行性,还将导致产生大量的冗余测试用例.自动生成测试用例总是在一定的策略和标准下进行.代码测试技术中测试标准相对成熟,有明确的测试指标.比如代码执行路径的覆盖率,DD 路径覆盖,突变测试标准等.但在基于程序规则说明测试方法中,并没有像代码测试中这样明确和公认的测试标准,因此,需要确定能有效判断测试用例充分性的标准.程序规则说明是以外部观点来看待软件,被测试程序被看作是从程序的输入空间到输出空间的作用函数FUNC :D ϖF ,D 是定义1中的输入域,F 是程序的行为或结果的全集.基于程序规则说明的测试就是验证被测试程序能否完整和正确实现规则说明所描述的功能.定义2　设程序Q 在测试数据集T 上执行,并且实现了功能F ,如果满足Πt ∈T :if Q (t )=F (t )]Πt ∈D :Q (t )=F (t ),则称测试数据集T 是可靠的,其中T <D.功能测试是把程序看作从输入变量空间到输出变量空间的函数f :(X 1,X 2,…,X m )ϖ(Y 1,Y 2,…,Y n ).随机测试数据生成器[3]函数在被测试程序的规则说明中构造输入变量空间的子集T <D ,使被测试程序Q 在测试数据集上运行,以保证结果能实现程序规则说明的所有功能.随机测试数据生成函数产生的测试用例并不是充分的.测试用例集能确定程序的所有功能都被实现,但是,它并不能保证这些功能都是被正确实现的.例如,被测试程序正确实现情况下应有Q (t 1)=F (t 1),Q (t 2)=F (t 2),但实际实现中却为Q (t 2)=F (t 1),Q (t 1)=F (t 2).由此可见,仅从输入域和输出域并不能保证测试的充分性,显然还需要更多的测试信息.定义3　设程序Q 的规则说明中P (X 1,X 2,…,X n )是程序输入变量必须满足的命题逻辑条件,如果测试数据集T 是可靠的,并且在T 上能满足P ,则T 是测试充分的.形式化的规则说明不仅能得到程序的输入和输出变量空间,还以命题逻辑为基础,将程序的实现条件表示为逻辑表达式.例如,当输入变量I =(X 1=x 1,X 2=x 2,…,X m =x m )时,如果满足条件P 1(X 1,X 2,…,X m ),则程序实现功能F 1.对于测试用例来说,如果能实现规则说明中的所有条件组合和功能覆盖,则测试数据集就是充分的.因此对测试充分性标准从对输入域空间的判定转换为对具体命题逻辑公式值的覆盖.为被测试程序构造充分的测试用例集合,可通过扩大程序规则说明中的命题逻辑条件表达式限制来实现.命题逻辑条件是其子句机械产生出的所有组合的子集.定理1　设程序为Q ,其输入域空间为D ,实现的功能为 F.如果测试用例集T ’是完备的,则T ’必然是测试充分的.证明　如果测试集合T ’不是测试充分的,则程序Q 在测试用例集T ’上的执行,或者不能实现规则967第4期金虎等:基于程序规则说明的自动测试用例生成077四川大学学报(自然科学版)第43卷说明中的程序功能的覆盖,则测试用例集是不完备的;或者不能满足命题逻辑的限制,有可能是错误的内部实现而得到正确的结果.所以,测试用例集T’是完备的,则必然也是测试充分的.在程序输入变量空间上取值,使所有程序规则说明中的命题逻辑条件都能实现,所以必然可从规则说明得到充分的测试用例集合.对于测试用例充分性的判定可转换为测试用例对规则说明命题逻辑条件的覆盖.在所有的功能测试方法中,决策表[4]技术是最严格的,常用于表示和分析复杂的逻辑关系,具有逻辑严密性.对于形式化表示的程序规则说明,从命题逻辑的分析角度,决策表技术正好能完整表示规则说明中的条件命题公式.对程序规则说明生成决策表,能够形成测试用例充分性的判定标准.定义4　设决策表为D T,规则说明的命题逻辑条件为P,程序实现的功能为 F.则决策表D T根据P 形成的规则称为决策测试规则集D T({R}):P∧F<D T({R})).使用决策测试规则集来表示程序必须在满足内部命题逻辑的限制的条件下实现程序的功能.考虑程序规则说明中所有可能的条件值组合与实现的功能:(c1.O P.c2.O P.….O P.c n)AND F,则能够形成完备的测试规则,因此能够形成测试用例的完备判定标准.定理2　设程序为Q,规则说明的命题逻辑条件为P,决策表D T根据P形成的决策测试规则集D T ({R}),如果随机测试用例生成器产生的测试数据用例集满足D T({R}),那么这个随机测试用例集对于被测试程序是完备的.决策测试规则集D T({R})采用决策表方式,完成逻辑限制条件的机械完备组合方式,形成测试充分的满足条件,以得到定义3中测试充分数据集的超集,因此它是完备的.决策表技术非常适合基于规则说明的测试方法,也适合于自动测试过程的完成.算法:SWTA G()输入:程序形式化的规则说明文件s;输出:测试结果r;BEGIN:1)　PARSER(s,D T R[],X[])　/3由形式化的规则说明获得程序的对应决策表规则集D T R[]和输入域空间X[]3/2)　random G en(X[])　/3随机方式对输入变量在域上赋值3/3)　exec(X[],program,F[])　/3在X[]上对程序一次执行3/4)　if(testDTR(X[],F[],D T R[]){　/3判断运行是否覆盖规则集3/ if(visitied all D T R[])执行5)　/3若所有规则都已覆盖,测试结束3/else重复2)3)4)} else Record Program Error　/3程序实现存在与形式化规则不符合情况3/5)　return rEND算法中,D T R[]为决策测试规则集;X[]为程序输入变量对应的结构数组,包含变量名和变量域;F[]是程序实现的功能集.SWTA G是程序根据形式化规则说明,采用随机生成测试用例方式,自动检测程序执行的过程.测试用例的充分性是以规则说明形成的测试条件集的覆盖为标准,作为自动过程的结束条件.算法可检测出程序的实现与形式化规则说明不一致的错误.3　自动生成测试用例分析 Triangle 程序在测试技术中是一个被广泛使用的例子程序.在非形式化表示的程序规则说明中描述为:程序输入3个整数表示三角形的三条边的大小,在程序计算处理后输出三角形的性状:等边、等腰、普通三角形或非三角形.为了完成测试用例自动生成过程,首先要为Triangle程序生成形式化表示的规则说图2　有效三角形的形式化规则说明表示Fig.2　Formal specification for triangle 明,其次根据规则说明为程序在输入域自动产生随机测试用例数据,结合决策表技术分析随机产生的测试用例是否有效,最后完成对测试结果的分析.图2是Z 标记的Triangle 程序形式化的规则说明. Z 是种类型语言[5],每个变量都有特定的类型,规则说明中的变量都将被实际的编程语言的数据类型所实现.在图2的程序规则说明中,有效的三角形输入域是N ×N ×N 的正整型变量空间,对于变量空间上的任意有序组(x ,y ,z ).图3是形式化的测试用例视图.图3　形式化表示的测试用例视图Fig.3　Schema of the test case TRIAN G L E ::=EQU |ISO |SCAL |INVAL ID 在图3的视图中,确定了程序测试所需要满足的命题逻辑公式.当满足测试条件的测试用例产生时,必然会形成对应的程序输出结果.对所有的测试用例进行划分,如果测试用例满足了测试覆盖条件,却没有产生期望的测试执行结果,则表明被测试程序的功能实现与规则说明存在差异,就可以发现程序存在差错.如果测试用例不完备,则通过对条件命题和输出域的覆盖就能发现测试用例集的不充分性.以triangle 程序为例,对程序引入错误,采用SWTA G 算法和以经验方式判断结束条件的随机生成测试用例[]两种方法来进行试验,结果如附表所示.附表　随机方式和决策测试规则集的测试能力比较Table Comp.Of RAN and SWTA G test capabilityFunction CoverageFunction 2Error Coverage Misclassification Logic error RANDOMUncompleted Uncompleted Unable detect Unable detect SWTA G Completed Completed All detected All detected 采用经验判断的随机生成测试用例方法是不严格的,不能保证生成的数据用例的完备性.在没有完成完备的功能检测时就可能达到结束条件,导致功能检测的遗漏.另外,由于对程序实现上的错误以及误分类等情况不能提供更多的信息,因此这种方式的实际检测能力很低.SWTA G 采用形式化的规则说明为基础,具有严格的测试控制条件,可以克服上述问题,整个测试过程也易于实现自动化.177第4期金虎等:基于程序规则说明的自动测试用例生成277四川大学学报(自然科学版)第43卷4　结语我们分析了基于程序规则说明的测试用例自动生成的过程,详细讨论了对于测试用例有效性的判断标准,并使用决策表方式来实现对随机生成的测试用例集的充分性判定,最后给出一个示例来说明自动生成测试用例的过程.参考文献:[1]　Poston R M.Automating Specification2Based S oftware Testing[M].[S.l]:IEEE Computer S ociety Press,1996.[2]　K orel B.Automated S oftware Test Data G eneration[J].IEEE Transactions on S oftware Engineering,1990,16(8):870.[3]　Richard A D. A.Jefferson of futt.Constraint2Based Automatic Test Data G eneration[J].IEEE Transactions on S oftwareEngineering,1991,17(9):900.[4]　Jorgensen P C.S oftware Testing:A Craftsman’s Approach(2nd ed)[M].[S.l.]:CRC Press LLC,2002.[5]　Bowen J.Formal S pecification and Documentation Using Z:A Case Study Approach[M].[S.l.]:Intl Thomson ComputerPr(Sd),1996.Specif ication2based T est C ase Automatic G enerationJ IN Hu,L I Zhi2shu,L I Qi(1.The State K ey Lab.of Software Lab.,Sichuan Normal University,Chengdu610066,China;2.College of Computer,Sichuan University,Chengdu610064,China;3.Dept.of Computer Sci.,Chengdu Univ.of Info.Tech.,Chengdu610041,China)Abstract:In the process of automatic SW testing,the quality of the test case generated under specific criteria will affect the performance and result of the testing greatly.This paper combines two specification2based test2 ing methods which are random testing and decision table technique.Decision is table to form maturity testing criteria ensures sufficiency of testing case generated randomly,and accomplishes the process of testing case au2 tomated generating.All research includes3sections:(1)Analyses Specification2based automated softwaretest2 ing technique.(2)G enerate testing criteria using decision table method for program specification.(3)Analy2 ses automated generating testing case combined with random testing data generator and decision table tech2 nique,andthe results shows better performance than random test case generator method.K ey w ords:specification;decision table;automatic software testing。