第10章a测试用例的自动生成

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,测试数据的自动生成技术,随机测试数据生成方法；,自适应随机生成方法,统计测试,约束求解方法；,符号执行技术；,基于搜索的测试数据生成方法。,本节要点,随机测试是通过在输入域中通过随机选择的方式来产生测试数据。测试人员按自己的想法随手产生的测试用例也可以认为是随机测试。,随机测试无处不在：几乎所有的测试数据生成方法最终都需要结合随机测试方法，以产生较好的测试数据分布。,优点：,1,）简单：不需要过多的信息；不需要开发复杂的程序；一般而言，算法复杂度为,o(n),。,2,）适应性广，几乎可以用于所有的测试方案中。（因为不需要过多的信息）。,3,）开销低，可以作为其他测试方法的补充。（算法复杂度已经到了最低的极限）。,随机测试,缺点：,1,）测试数据发现程序失效的效率较低；,2,）难以确定测试的效果和停止测试的时机；,3,）需要大量开销来计算所产生大量的测试数据的预期输出。（,Oracle,问题）,随机测试的用途,1,）在没有足够的信息支持其他测试方法时；,2,）如果能够有办法不使用预期结果进行测试的验证，如：冒烟测试、参考测试、蜕化测试等；,3,）作为其他测试方法的支持；,4,）在刚开始进行测试时，初步发现错误。,随机测试,随机测试的实现：对于简单的程序输入，如整数、实数等，可以直接产生随机数据。其他数据类型，需要进行数据的映射和转换。,复杂数据类型的随机数据生成,1,）对被测软件的输入空间进行建模，为测试数据的随机生成创造条件。,2,）产生随机数，映射到输入空间的某个点，将该点转换为一个测试数据。,随机测试,输入空间建模问题：,1,）每一个可能的输入在空间中都有一个对应的点；空间中每一个点都对应一个输入。,2,）注意各种类型的数据在空间中分布的情况。例如，避免过多地生成失效数据。,3,）注意计算机产生的随机数是实数，需要建立一种简单、方便的映射算法，把随机生成的数据（可能是多个数据）映射为输入数据。,4,）所建立的空间模型，和程序需要的数据可能有差异，如忽略了某些重要的约束条件，需要对生成的测试数据进行再加工。,随机测试,例：为某个输入为二叉树的程序构造测试用例,1,）二叉树的先根序列和中根序列将唯一确定一棵二叉树；因此可以将二叉树的空间结构映射为一个,1,.,n,的随机序列。这个随机序列对应一棵二叉树的中根序列，而这棵二叉树的先根序列是,1,.,n,。,2,）生成过程分为三个步骤，首先随机生成一个整数,n,，代表树的结点数目；生成长度为,n,的随机序列；根据随机序列构造一个二叉树。,随机测试,在很久以前，有人,(Mayers),认为随机测试是效率最低的方法，因为它没有使用任何信息。,由于随机测试的简单特性，依然在各种测试中广泛应用。,后来有人比较分割测试（,Partition testing,）和随机测试的效率，发现不恰当的分割测试比随机测试的效果还差。,分割测试和随机测试比较的简单介绍。,随机测试的效率问题,随机测试所生成的测试数据在发现错误方面是低效率的。为此，有各种改进的方法。主要的思想是：根据某些信息，为随机测试提供生成的指导。,自适应随机测试,(Adaptive Random Testing),：根据失效输入一般会集中出现在输入空间的某个局部区域的特征，提出将测试用例尽量均匀地分布在整个输入空间，从而提高测试用例发现错误的效率。,概率测试：根据用户的需求，为对输入空间进行划分，不同部分用不同的概率产生测试用例。,统计测试：先使用随机测试，当进行到一定程度时停止，再使用其他测试方法产生测试用例。,对随机测试的改进,在被测程序中，失效输入通常会集中在输入空间的某几个地方，被称为失效区域。失效区域形状被归类为,3,种。,自适应随机测试,自适应随机测试的基本思想：每当生成一个新的测试用例的时候，尽量远离原有的测试用例。,一些具体办法：,1,）基于距离的，,FSCS(Fixed size of candidate set),，先随机生成几个测试用例（候选集），计算这些测试用例和已经生成的测试用例的距离，选择距离最大的那个作为新的测试用例。,2,）基于排除域的，,RRT(Rejected Region testing),，在每一个已生成的测试用例的附近指定一块排除域，随机产生一个测试用例，如果这个测试用例不在任何一个排除域中，那么它就成为新的测试用例。,自适应随机测试,一些具体的方法,3,）基于分割的，利用已生成的测试用例把整个输入空间分割成若干个部分，从最大的那个部分中选择测试用例。,4,）基于概率函数的，通过设定概率函数，将距离现有的测试用例较远的输入空间的点的概率设大，越近的越小。,自适应随机测试,自适应随机测试的优点,与随机测试相比，能够大幅度提高所生成测试用例的效率；,不需要额外增加信息。因为自适应随机测试运用的是测试中的一般规律。,自适应随机测试的缺点,计算复杂度大幅度提高：通常达到,O(n,2,),甚至更高。,在实践应用中效果不好。,自适应随机测试,在自适应随机测试研究中得到的一个重要结论：即使我们知道失效区域的形状、大小、方向等信息，但我们不知道失效区域的位置。那么我们无论用什么方法进行测试，发现失效的概率也只能达到随机测试方法的一倍。,而,ART,在理想的状态下，逼近这个极限值。,自适应随机测试,对自适应随机测试的一些改进,由于自适应随机测试的计算复杂度太高，有一些方法改进了自适应随机测试的生成效率。,基于遗忘的方法,(forgetting),。在生成过程中，仅考虑最近生成的若干个测试用例（如,100,个）。,基于镜像的方法（,mirroring,）。在生成过程中，将输入空间划分为对称的几个部分，仅对某个空间进行测试用例生成。当生成新的用例后，就映射到其他几个空间。,自适应随机测试,由于随机测试的简单快捷，通常先使用随机测试生成一批数据，再使用其他方法弥补随机测试遗漏的部分。,例如：在进行路径覆盖的测试过程中，先使用随机测试生成方法生成测试用例，当路径被覆盖了预定部分之后（如,85%,）或路径覆盖增长速度放慢。则再对剩下的路径进行计算，产生覆盖剩下路径的用例。,统计测试,在测试用例生成过程当中，大多数测试覆盖要求可以归结为一个或多个逻辑表达式（约束条件）。因此，产生达到覆盖要求的测试用例的问题就转化成为求解满足约束条件的值的过程。,例：一个合法三角形的约束条件是,a+bc&a+cb&b+ca,。求解该表达式，即找到,abc,三个整数（实数），使得该表达式为真，则,abc,构成一个三角形的三边。,上述问题即为一个典型的约束求解问题。,约束求解问题是,NP-Hard,问题。,约束求解与软件测试,形式化地讲，约束问题由以下三个基本元素组成：变量,V,，变量的域,D,以及约束,C.,变量的域,D,是变量可能取值的集合，变量,Vi,只能在它的域,Di,中进行取值；约束,C,描述了变量,V,之间必须满足的关系,.,求解约束问题就是在各变量的域,D,中找到一个,(,或所有的,),值,S,使得各变量之间满足约束,C.,根据约束问题中变量的域,D,的不同，约束问题可以分为：,布尔约束问题；,有限约束问题；,数值约束问题,/,混合约束问题。,约束求解,基本概念,布尔约束问题：布尔约束问题要求,V,中的各变量只能在,0,或,1,上取值，即布尔约束问题的域,D,为,0,，,1.,它的约束,C,实际上就是一组命题逻辑公式,.,求解布尔约束问题的目的就是为该问题中的布尔变量赋值，使得该问题中的每一个布尔约束条件的值为“真”。,有限约束问题，就是变量只能在有限域上取值,.,在有限约束问题中，通常不考虑约束的具体形式，而采用列出所有满足该条件的变量取值组合的形式,.,N,皇后问题、鸽笼问题、图着色问题等都属于有限约束问题,.,实际上，布尔约束问题可以看作是有限约束问题的特例,.,约束求解,分类（,1,）,混合约束问题：由一个或一组混合约束条件组成的问题称为混合约束问题,.,混合约束问题中的变量可以在多个域中取值，比如变量可以取布尔值、可以在有限数值域及无限数值域上取值等,.,混合约束问题实质上是对布尔约束问题的一种扩展,.,约束求解,分类（,2,）,数值约束条件：形如,Exp1 rop Exp2,的约,束称为数值约束，其中,Exp1,与,Exp2,为数学表达,式，如,2,x yz,；,rop,为一数学上的关系操作符，包,括,=,; ;=.,混合约束条件：混合约束条件由布尔变量及数值约束与逻辑连接符组成，它们按照与命题逻辑公式同样的规则形成组合体,.,例如,a (x - y ,3),(x + z = 4).,约束求解,分类（,3,）,一个数值约束有,“,成立,”,和,“,不成立,”,两种情况，分别对应于这个数值约束的值为,真,“,和,假,”,，那么混合约束条件的值就如同布尔约束条件的值一样，也只能取,真,“,或者,假,”.,从而求解混合约束问题的目的就是为其中的数值和布尔变量赋值，使得该问题中的每个混合约束条件的值为,真,“.,如果能够找到这样的布尔变量值和数值变量值，则称该混合约束问题能够成立，或称是可行的,(Feasible),，否则称为不能够成立，或称是不可行的,(Infeasible).,约束求解,分类（,3,）,有限约束问题的求解方法可以分为完备算法与不完备算法两种,.,所谓完备算法是指能够完全确定某约束问题是有解的还是无解的算法；而不完备的算法则在未找到解时不能确定该约束问题无解,.,完备算法：完备算法中最常用的是回溯法，该方法先为约束问题中的部分变量赋值， 在这个部分赋值的基础上为其余的变量赋值,.,如果在这个部分赋值的基础上， 下一个待赋值的变量找不到使得约束成立的解， 则需要改变这个部分赋值中所赋的值,.,约束求解,求解方法（,1,）,局部搜索法的基本思想是：从随机选定的解开始，不断对其进行微小的改变,(,局部改进,),，直到满意为止,.,所谓的满意是指要么得到一个解，要么改进的次数大于设定的最大值,.,对于后一种情况，我们就得不到该约束问题到底是有解还是无解的结论,.,著名的局部搜索算法包括：顾钧的算法、贪心搜索过程,GSAT,、禁忌搜索,(Tabu search),和拟人拟物法等,.,其它的还包括爬山法、模拟退火等,.,约束求解,求解方法（,1,）,数值约束问题的求解方法,数值约束可化为如下的基本形式：,fi(x) = 0; i = 1 : : : p,hj(x) = 0; j = 1 : : : q,如果数值约束中的等式和不等式约束都是线性的，则称之为线性数值约束问题，否则称之为非线性数值约束问题,.,线性数值约束问题的求解可用单纯形法,(Simplex method).,该方法已经十分成熟,.,约束求解,求解算法（,2,）,非线性数值约束问题的求解,1),数值法：基于高斯,-,牛顿法求解非线性方程；,2),符号计算法：将待求解的非线性代数方程组化为一个或多个等价的三角型方程组,.,3),柱形代数分解：设约束,h,中出现的变元个数为,r,，将,r,维欧氏空间剖分成,“,块,”,，使得对,“,块,”,中个别点进行检验就可以判定,h,成立与否,.,4),区间分析：为了解决计算机只能表示有限位数字，以及其它与此相关的实际问题而产生的,.,它的基本思想是对实数的扩展，用一个区间而不是单独的一个数来表示数,.,例如数,a,用区间的表示方法为,a,= ,a,I,; a,S,，,a,I,=ap0,。,开始,t,值较高，活动范围较大，,t,随时间逐渐下降。,遗传（基因,/,进化）算法,从生物学中的进化借鉴而来的。,基本概念,个体,/,个体空间,种群,/,种群空间,适应值函数,选择,/,杂交,/,变异,/,删除,标准遗传算法,K=0,，随机产生初始种群,X(0)=(x,1,(0),x,n,(0),独立地从当前种群中选取,n,对母体；,独立的对,n,对母体进行杂交得到,n,个中间个体；,独立的对,n,个中间个体进行变异得到下一代种群；,检验停止标准，若满足则停止，否则,k=k+1,，并返回,2,；,杰出选择算法,K=0,，随机产生初始种群,X(0)=(x,1,(0),x,n,(0),独立地从当前种群中选取,n-1,对母体；,独立的对,n-1,对母体进行杂交得到,n-1,个中间个体；,独立的对,n-1,个中间个体进行变异得到下一代种群的前,n-1,个个体；,即从,k,代种群中选出最优的个体,x,i,(k),（目标函数最大），令,x,n,(k+1)=x,i,(k),。,检验停止标准，若满足则停止，否则,k=k+1,，并返回,2,；,稳定遗传算法,K=0,，随机产生初始种群,X(0)=(x,1,(0),x,n,(0),从当前种群中选取,1,个母体；,对所选的母体进行杂交得到,1,个新个体；,从当前种群中删除一个个体，用新个体替换它，从而得到下一代种群；,检验停止标准，若满足则停止，否则,k=k+1,，并返回,2,；,应用遗传算法的工作,1,、编码：把问题转换成为在个体空间进行搜索的问题；,2,、设定目标函数（选择函数）、杂交算子、变异算子、删除算子；,3,、选定具体的遗传算法；,4,、选定初始种群，进行计算；,在进行程序分析的过程中，使用符号而不是实际的值代入到程序中进行运算的过程。从而能够分析出特定路径的约束条件和计算公式。,符号执行技术的用途,测试数据自动生成；,逆向工程；,路径可达性分析,符号执行技术,生成被测程序的流程图，该流程图代表目标程序可能的执行路径。,遍历流程图中的某条特定路径，遍历过程中，,每一个输入变量用一个符号而不是一个具体的值代替，进行程序的计算,。,每一个语句经过计算后，输入变量的值有可能发生改变，成为某个计算表达式，在下一个语句中用这个计算表达式代替该变量进行计算。重复这个过程，直到程序结束。,当符号执行遍历了某条路径后，产生的输出变量将是一个由输入变量符号和常量构成的表达式。而路径中所有分支语句将构成一系列判定条件析取构成的路径表达式。,符号执行的基本流程,例：三角形程序的符号执行,例：某路径的符号执行过程,对存在循环，特别是循环次数不定的程序，难以分析程序的执行过程；,对复杂数据结构，如数组、指针等难以通过符号表达其运算；,由符号执行技术生成的条件约束，求解时时一个,NP-hard,问题。,符号执行技术的难点,