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