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

测试数据的自动生成技术 随机测试数据生成方法 自适应随机生成方法统计测试约束求解方法 符号执行技术 基于搜索的测试数据生成方法 本节要点 随机测试是通过在输入域中通过随机选择的方式来产生测试数据 测试人员按自己的想法随手产生的测试用例也可以认为是随机测试 随机测试无处不在 几乎所有的测试数据生成方法最终都需要结合随机测试方法 以产生较好的测试数据分布 优点 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 认为随机测试是效率最低的方法 因为它没有使用任何信息 由于随机测试的简单特性 依然在各种测试中广泛应用 后来有人比较分割测试 Partitiontesting 和随机测试的效率 发现不恰当的分割测试比随机测试的效果还差 分割测试和随机测试比较的简单介绍 随机测试的效率问题 随机测试所生成的测试数据在发现错误方面是低效率的 为此 有各种改进的方法 主要的思想是 根据某些信息 为随机测试提供生成的指导 自适应随机测试 AdaptiveRandomTesting 根据失效输入一般会集中出现在输入空间的某个局部区域的特征 提出将测试用例尽量均匀地分布在整个输入空间 从而提高测试用例发现错误的效率 概率测试 根据用户的需求 为对输入空间进行划分 不同部分用不同的概率产生测试用例 统计测试 先使用随机测试 当进行到一定程度时停止 再使用其他测试方法产生测试用例 对随机测试的改进 在被测程序中 失效输入通常会集中在输入空间的某几个地方 被称为失效区域 失效区域形状被归类为3种 自适应随机测试 自适应随机测试的基本思想 每当生成一个新的测试用例的时候 尽量远离原有的测试用例 一些具体办法 1 基于距离的 FSCS Fixedsizeofcandidateset 先随机生成几个测试用例 候选集 计算这些测试用例和已经生成的测试用例的距离 选择距离最大的那个作为新的测试用例 2 基于排除域的 RRT RejectedRegiontesting 在每一个已生成的测试用例的附近指定一块排除域 随机产生一个测试用例 如果这个测试用例不在任何一个排除域中 那么它就成为新的测试用例 自适应随机测试 一些具体的方法3 基于分割的 利用已生成的测试用例把整个输入空间分割成若干个部分 从最大的那个部分中选择测试用例 4 基于概率函数的 通过设定概率函数 将距离现有的测试用例较远的输入空间的点的概率设大 越近的越小 自适应随机测试 自适应随机测试的优点与随机测试相比 能够大幅度提高所生成测试用例的效率 不需要额外增加信息 因为自适应随机测试运用的是测试中的一般规律 自适应随机测试的缺点计算复杂度大幅度提高 通常达到O n2 甚至更高 在实践应用中效果不好 自适应随机测试 在自适应随机测试研究中得到的一个重要结论 即使我们知道失效区域的形状 大小 方向等信息 但我们不知道失效区域的位置 那么我们无论用什么方法进行测试 发现失效的概率也只能达到随机测试方法的一倍 而ART在理想的状态下 逼近这个极限值 自适应随机测试 对自适应随机测试的一些改进由于自适应随机测试的计算复杂度太高 有一些方法改进了自适应随机测试的生成效率 基于遗忘的方法 forgetting 在生成过程中 仅考虑最近生成的若干个测试用例 如100个 基于镜像的方法 mirroring 在生成过程中 将输入空间划分为对称的几个部分 仅对某个空间进行测试用例生成 当生成新的用例后 就映射到其他几个空间 自适应随机测试 由于随机测试的简单快捷 通常先使用随机测试生成一批数据 再使用其他方法弥补随机测试遗漏的部分 例如 在进行路径覆盖的测试过程中 先使用随机测试生成方法生成测试用例 当路径被覆盖了预定部分之后 如85 或路径覆盖增长速度放慢 则再对剩下的路径进行计算 产生覆盖剩下路径的用例 统计测试 在测试用例生成过程当中 大多数测试覆盖要求可以归结为一个或多个逻辑表达式 约束条件 因此 产生达到覆盖要求的测试用例的问题就转化成为求解满足约束条件的值的过程 例 一个合法三角形的约束条件是a b c a c b b c a 求解该表达式 即找到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 数值约束条件 形如Exp1ropExp2的约束称为数值约束 其中Exp1与Exp2为数学表达式 如2x yz rop为一数学上的关系操作符 包括 混合约束条件 混合约束条件由布尔变量及数值约束与逻辑连接符组成 它们按照与命题逻辑公式同样的规则形成组合体 例如a x y 3 x z 4 约束求解 分类 3 一个数值约束有 成立 和 不成立 两种情况 分别对应于这个数值约束的值为 真 和 假 那么混合约束条件的值就如同布尔约束条件的值一样 也只能取 真 或者 假 从而求解混合约束问题的目的就是为其中的数值和布尔变量赋值 使得该问题中的每个混合约束条件的值为 真 如果能够找到这样的布尔变量值和数值变量值 则称该混合约束问题能够成立 或称是可行的 Feasible 否则称为不能够成立 或称是不可行的 Infeasible 约束求解 分类 3 有限约束问题的求解方法可以分为完备算法与不完备算法两种 所谓完备算法是指能够完全确定某约束问题是有解的还是无解的算法 而不完备的算法则在未找到解时不能确定该约束问题无解 完备算法 完备算法中最常用的是回溯法 该方法先为约束问题中的部分变量赋值 在这个部分赋值的基础上为其余的变量赋值 如果在这个部分赋值的基础上 下一个待赋值的变量找不到使得约束成立的解 则需要改变这个部分赋值中所赋的值 约束求解 求解方法 1 局部搜索法的基本思想是 从随机选定的解开始 不断对其进行微小的改变 局部改进 直到满意为止 所谓的满意是指要么得到一个解 要么改进的次数大于设定的最大值 对于后一种情况 我们就得不到该约束问题到底是有解还是无解的结论 著名的局部搜索算法包括 顾钧的算法 贪心搜索过程GSAT 禁忌搜索 Tabusearch 和拟人拟物法等 其它的还包括爬山法 模拟退火等 约束求解 求解方法 1 数值约束问题的求解方法数值约束可化为如下的基本形式 fi x 0 i 1 phj x 0 j 1 q如果数值约束中的等式和不等式约束都是线性的 则称之为线性数值约束问题 否则称之为非线性数值约束问题 线性数值约束问题的求解可用单纯形法 Simplexmethod 该方法已经十分成熟 约束求解 求解算法 2 非线性数值约束问题的求解1 数值法 基于高斯 牛顿法求解非线性方程 2 符号计算法 将待求解的非线性代数方程组化为一个或多个等价的三角型方程组 3 柱形代数分解 设约束h中出现的变元个数为r 将r维欧氏空间剖分成 块 使得对 块 中个别点进行检验就可以判定h成立与否 4 区间分析 为了解决计算机只能表示有限位数字 以及其它与此相关的实际问题而产生的 它的基本思想是对实数的扩展 用一个区间而不是单独的一个数来表示数 例如数a用区间的表示方法为a aI aS aI a aS 它的意义在于 区间 aI aS 中一定包含a的精确值 而且经过合理的数学运算 这个区间可以足够小 约束求解 求解算法 2 混合约束问题的求解方法1 区间分析法 2 逻辑与数值相结合的方法 分为两个步骤替换和还原 替换 替换是指用一个新的布尔变量来替换混合约束问题中的每个数值约束 从而得到一个布尔约束问题 并对该布尔约束问题进行求解 还原 将替换阶段结束时获得的布尔值 将相应的布尔变量还原为该数值约束本身并进行约束求解 替换和还原需要不断进行回溯 启发式搜索算法 约束求解 求解算法 3 启发式搜索算法 启发式搜索实际上起源于人工智能的研究 在求解一些很难的问题过程中 往往会把问题转换成为一个在问题空间中进行搜索的问题 启发式搜索是根据以往搜索的结果所得到的信息 产生下一步搜索动作的一大类算法 启发式搜索算法是处理NP hard问题的有效途径 现有的常用的算法有 爬山法退火算法遗传算法 搜索求解及爬山法 模拟退火算法 与爬山法类似 都有价值函数 都从当前解试探邻域 如果有更好的可能 用邻域值代替当前值 引入概率t是控制参数 即 温度 当试探解比当前解好时 p 1 当试探解比当前解差时 1 p 0 开始t值较高 活动范围较大 t随时间逐渐下降 遗传 基因 进化 算法 从生物学中的进化借鉴而来的 基本概念个体 个体空间种群 种群空间适应值函数选择 杂交 变异 删除 标准遗传算法 K 0 随机产生初始种群X 0 x1 0 xn 0 独立地从当前种群中选取n对母体 独立的对n对母体进行杂交得到n个中间个体 独立的对n个中间个体进行变异得到下一代种群 检验停止标准 若满足则停止 否则k k 1 并返回2 杰出选择算法 K 0 随机产生初始种群X 0 x1 0 xn 0 独立地从当前种群中选取n 1对母体 独立的对n 1对母体进行杂交得到n 1个中间个体 独立的对n 1个中间个体进行变异得到下一代种群的前n 1个个体 即从k代种群中选出最优的个体xi k 目标函数最大 令xn k 1 xi k 检验停止标准 若满足则停止 否则k k 1 并返回2 稳定遗传算法 K 0 随机产生初始种群X 0 x1 0 xn 0 从当前种群中选取1个母体 对所选的母体进行杂交得到1个新个体 从当前种群中删除一个个体 用新个体替换它 从而得到下一代种群 检验停止标准 若满足则停止 否则k k 1 并返回2 应用遗传算法的工作 1 编码 把问题转换成为在个体空间进行搜索的问题 2 设定目标函数 选择函数 杂交算子 变异算子 删除算子 3 选定具体的遗传算法 4 选定初始种群 进行计算 在进行程序分析的过程中 使用符号而不是实际的值代入到程序中进行运算的过程 从而能够分析出特定路径的约束条件和计算公式 符号执行技术的用途测试数据自动生成 逆向工程 路径可达性分析 符号执行技术 生成被测程序的流程图 该流程图代表目标程序可能的执行路径 遍历流程图中的某条特定路径 遍历过程中 每一个输入变量用一个符号而不是一个具体的值代