,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,组合测试,绪论,软件系统的故障往往是由一些难以预料的系统因素及其相互作用而引起的，为了检测这些故障，必需设计一组测试用例，对系统因素的各种组合状况进展充分掩盖的测试。,通过对各个参数的不同输入数据进展组合，可以验证软件系统在不同条件下的行为。例如：对于微软的 Word 软件，其字体设置对话框总共有19个输入参数需要设置.,经过等价类划分和边界值处理后，假设进展全组合的测试，那么会产生上万个测试用例。,充分组合测试的最终测试用例数是浩大的，如何从中选择一个规模较小的、能更有效的找出软件故障的子集作为测试用例集是测试用例生成中一个很重要的问题。,绪论,依据争论统计说明，很多程序的错误都是由少数几个参数及参数之间的相互作用而导致。Willace 和 Kuhn 等人在美国国家标准与技术协会NIST期刊上发表的论文指出：经过大量的调查争论后觉察，在软件把握的医疗系统中，98%的故障是由变量对之间的交互所导致的；Kuhn 和 Reilly 等人在对 Mozilla 扫瞄器的错误报告进展分析和争论后说明：该系统的 70%以上的错误是由 2 个以内的参数相互作用而引发的，90%以上的错误是由 3个以内的参数相互作用而引发的。,绪论,组合测试其根本思想是从统计学的角度对测试试验进展设计。该方法设计的测试用例以参数及参数之间的交互为掩盖标准，虽然不能够进展完全的测试，但是利用该方法进展的测试得到的结果能够在确定程度上反映系统的内部规律，具有确定的代表性。,这种方法对由系统输入、外部大事等相互作用而产生的故障系统，具有较强的检错力气。,目前，对组合测试用例生成方法的争论主要包括：,两两组合测试用例生成技术,N 维组合测试用例生成技术,变力度组合测试用例生成技术,带优先级的组合测试用例生成技术,带约束的组合测试用例生成技术,组合测试中错误定位技术,绪论,两两组合掩盖测试用例生成例如,假设系统有3个因素，每个因素有3个不同的取值，分别为A1,A2,A3；B1,B2,B3；C1,C2,C3。对于测试用例 t=A1,B1,C1，其对应的两两组合表示是一个集合S=A1,B1,A1,C1,B1,C1，如以以下图：,测试用例 t=A1,B1,C1掩盖了A1,B1,A1,C1,B1,C13个两两组合元素。,两两组合掩盖测试举例,一个网络信息系统如表所示，需要进展兼容性测试，假设需要进展完全的测试，那么该系统需要 81 个测试用例，但是假设承受两两组合测试技术进展测试，只需要 9 个测试用例。,两两组合掩盖测试举例,两两组合掩盖测试举例,两两组合测试用例设计方法,生成最优的两两组合测试用例集的问题已经被证明是一个 NP 问题。,在实际的测试用例生成过程中，一般尝试用各种近似算法求解。这些方法大致可以分为如下几类：数学构造法、贪心算法、元启发式算法。,不同的测试用例集所掩盖的两两组合元素数量不同。在同样大小的测试用例集的条件下，掩盖的两两组合元素数量越多，说明该测试用例集的测试效果越好。,数学构造法,目前的数学构造方法根本上都是基于正交矩阵，并在此根底上开发了组合测试用例生成工具。比方：Bell 试验室研发的 CATS 工具，Williams 开发的 Tconfig 工具，IBM Haifa 争论院的 WHITCH 工程。,代数方法由于各种代数构造的限制，仅适用于成对组合掩盖测试用例的自动生成，不简洁被扩展到更高维数的组合掩盖的测试用例的自动生成中。,两两组合测试用例设计方法,开头时，由于A、B、C三个元素的最低水平数为2，我们则以因素为3，水平数为2来选择正交表，并进展用例的生成。此时测试用例集为(A1,B1,C1),(A1,B2,C2),(A2,B1,C2),(A2,B2,C2)。此时，未被掩盖的成对组合W=(A1,C3),(A2,C3),(B1,C3),(B2,C3)。在W中，A1消逝1次，A2消逝1次，B1消逝1次，B2消逝1次，C3消逝3次，因此，选择消逝次数最多的C3产生测试用例T5=(*,*,C3)。接下来，要从A1,A2中选择一个作为因素A的水平值。假设选择A1，则可以掩盖(A1,C3)；假设选择A2，则可以掩盖(A2,C3)。不妨选择A1,则T5=(A1,*,C3)。下面要从B1,B2中选择一个作为因素B的水平值。假设选择B1，则可以掩盖W中的(B1,C3)；假设选择B2，则可以掩盖W中的(B2,C3)。由于选择B1,B2所掩盖的W中的成对组合个数一样，不妨选择B2，即T5=(A1,B2,C3)，此时未被掩盖的成对组合集合W=(A2,C3),(B1,C3)。依据同样方法，可得到T6=(A2,B1,C3)。参与T6后，W为空。生成过程完毕。,正交设计法举例,存在缺乏：,1正交矩阵问题始终是组合数学界争论的问题，目前小规模的正交表已经被构造出来，但是对于大规模的正交矩阵的构造目前还没有很好的方法。,2现在学术界对于对称正交表的争论较多，对于混合水平的正交表的构造争论较少，而混合水平的正交表更加符合实际工程的组合测试需求。,3在正交矩阵中每个组合消逝的次数是一样的，这在组合测试中不是必需的，只需要每个组合被掩盖一次就可以，所以依据正交试验设计得到的两两组合测试用例集中可能含有冗余的测试用例。,正交设计法,贪心算法的思想是从空矩阵开头，逐行或者逐列地扩展矩阵，直到全部的t组合都被覆 盖。按 照 策 略 的 不 同，些 贪 心 算 法 可 以 分 为 使 用 逐 条 生 成 测 试 用 例one-test-at-a-time策略和逐参数扩展in-parameter-order策略两种不同的策略。其中，one-test-at-a-time策略是使用一维扩展的扩展方式，IPO策略是一种二维扩展的扩展方式。,贪心算法,基于one-test-at-a-time策略的算法,即一维扩展方式，是在构造掩盖数组时，依据贪心策略依次增加一行，使得这一行掩盖一些未掩盖的t元组，直到全部t元组都被掩盖。使用one-test-at-a-time策略，抱负的状况是使用全局贪心算法，即在每次选择测试用例时，选择能最大限度掩盖Uncover中组合的用例。,AETG是美国贝尔试验室的和等人依据启发式方法研制的测试数据生成工具。该工具可以依据测试要求，产生满足因素的成对组合掩盖或多个因素的组合掩盖测试数据。,AETG开头于一个空的测试用例集，每次往测试用例集参与一个测试用例。为了得到一个新的测试用例，首先依据贪心算产生一组候选用例，然后从中选择能够掩盖最多未被掩盖的成对组合的用例。,类似算法有：CAST,TCG,DDA,PSSA等。,基于one-test-at-a-time策略的算法,设某个被测系统有3个因素A、B、C，因素A有2个值A1和A2，因素B有2个值B1和B2，因素C有3个值C1、C2、C3。,依据AETG算法，测试用例生成过程如以以以下图所示。,基于one-test-at-a-time策略的算法,基于one-test-at-a-time策略的算法,2逐参数扩展策略,逐参数扩展策略与逐条用例扩展策略的不同之处在于逐参数扩展是以参数为单位进展扩展，假设只有一个参数需要扩展，那么直接添加到系统中即可，当有多个参数需要扩展时，就要对参数进展排序，然后将参数取值个数最多的一个的参数作为候选的参数。,由于每个参数都有不同的取值，使用贪心算法来选择适宜的参数值添加到相应的测试用例中，当照旧有未被掩盖的组合时，需要添加新的测试用例来掩盖这些漏掉的组合。,贪心算法,IPO 算法,美国北卡罗莱纳大学计算机系的 Y.Lei 和 提出一种基于参数挨次的渐进扩展的两两组合掩盖测试数据生成方法。与 AETG 算法不同，IPO 算法的根本思想是以参数为对象，初始时先生成满足组合掩盖的测试要求的用例集合 T，然后一个个扩展剩余的参数，直至全部的参数都被包涵到测试用例中，并在算法中时刻都尽可能使测试集个数大小保持最优。,贪心算法,IPO算法包括两个核心步骤：水平扩展和垂直扩展。在这两个维度的扩展上，算法依据确定的因素来预备参数扩展和取值的次序。以两两组合掩盖为例，从这两个维度来争论IPO算法的影响因素及可扩展点。,在水平扩展时，算法需要为矩阵增加一个参数列，给这一列上的每一项赋值，尽可能的掩盖更多的未掩盖t元组。因此，从以下三个影响因子：新增参数列的选择、已有测试用例集的扩展次序、新增参数的取值选择进展分析。,水平扩展后，算法可能还未完全掩盖已扩展参数的两两组合，因此，还需要进展垂直扩展，即增加新的测试用例以掩盖尚未掩盖的二元组。从上述例子中可以看出，垂直扩展是将尚未扩展的用例直接作为新增用例参与。这将形成新增用例中存在一些no-care位，如何在后续扩展中为这些no-care位赋值也将影响IPO算法的结果。,IPO 算法,IPO 算法举例,IPO 算法举例,贪心算法的根本思想是从小到大构造矩阵，直到全部的掩盖条件都得到满足另外一种查找最优的(或者较优的)掩盖数组的方法是，利用一个已有的数组，通过适宜的变换得到一个更优的掩盖矩阵这样，通过逐次变换得到较优的矩阵为了避开陷入局部最优，算法承受了一些启发式的策略，通过多样化或变异的方法跳出局部最优点,元启发式搜寻算法,元启发式算法主要可以分为两类：个体搜寻算法Individual Search和群体搜寻算法Population Search。其中，个体搜寻算法以单个可行解进展迭代，包括常见的爬山算法、模拟退火算法、洪水算法、禁忌搜寻算法等。群体搜寻算法以可行解的集合进展迭代，包括常见的遗传算法、蚁群算法等。,相对于贪心算法，元启发式搜寻算法能够给出较优的近似结果。但是大局部元启发式搜寻算法都需要同时变换多个矩阵，进展屡次变换，因而运行时间一般比较长。目前元启发式搜寻算法主要停留在争论阶段，很少有有用的工具承受启发式搜寻算法。,