AETG 算法 - 组合测试中的优化

发表于 更新于
介绍了组合测试中的 AETG 算法及其实现，来减少组合测试的用例总数并依然能够发现大部分问题。源代码于：https://github.com/beet233/AETG

Intro

假设一个待测试的系统，有 k 个输入/系统参数，每个参数有 Vi (1<=i<=k) 个情况，那么覆盖所有情况的测试组数就来到了所有 Vi 的乘积，这个结果就非常糟糕了。

有没有这样一种可能，我们只需要测其中的一小部分组合，就能测出大部分的错误呢？

单缺陷假设

失效极少是由两个（或多个）缺陷的同时发生引起的。

Kuhn 和 Reilly 分析了 Mozilla 浏览器的 错误报告记录，发现：
超过 70% 的错误是由 2 个以内的参数相互作用触发的；
超过 90% 的错误是由 3 个以内的参数相互作用触发的。

换言之，当我们的测试用例保证：
覆盖任意 2 个变量的所有等价类组合，我们就能避免 70% 的错误；
覆盖任意 3 个变量的所有等价类组合，我们就能避免 90% 的错误。

T-way Coverage

由单缺陷假设引出，覆盖 t 个变量的所有等价类组合而进行的测试用例设计，我们称之为 t-way coverage。

我们只需要找到一批测试组，他们覆盖了所有 t 个变量的等价类组合，当 t >= 2，就能避免大部分的错误，无疑是实惠的选择，并且后面的结果中我们将看到，这让需要测试的组数大大地减少。当然，缺陷就是如果有错误由 n > t 个变量的特定值组合触发时，我们就检查不到了。

基于这个思想的组合生成算法有很多：

Greedy Algorithms:

  • AETG - Automatic Efficient Test Case Generator
  • TCG - Test Case Generator
  • DDA - Deterministic Density Algorithm
  • IPO - In Parameter Order

Heuristic/Meta-heuristic Search:

  • Hill Climbing
  • Simulated Annealing
  • Genetic Algorithms
  • Tabu Search

下面详细介绍一下 AETG 算法并实现它。

AETG

为生成一个 Cover Array，也就是包括所有 T 个变量的等价类组合的用例集，假设系统总共有 K 个参数，T 即为这个 Cover Array 的强度，遵循以下步骤：

  1. 每个参数有有限的多个可能的取值。假设一开始有未覆盖对 Uncovered Pairs（以下简称 ucps）集和覆盖对 Covered Pairs（以下简称 cps）集。 ucps 初期即为所有 T 个变量的等价类组合，而 cps 初期为空。

    注意，pair 看起来像是一个二元的概念，但这里也包括 T > 2 的场景，也称其为 pair。

  2. 按以下方法生成新的测试用例：

    • 设定一个候选组数量，记为 M，因为下面的过程会用到随机数，所以我们每次生成一个正式的测试用例加入 Cover Array 前，都先生成 M 个候选测试用例，在其中选择效果最好的。候选测试用例生成过程如下：
      • 一开始候选测试用例为空，为了确定第一个参数和它的取值，遍历每一个参数的所有可能取值，选择在未覆盖对集中出现频率最高的那一个参数和它的取值，将其确定并纳入候选测试用例中。
      • 对于之后的参数进行确定。当还有参数没有确定时，假设已经确定了 t - 1 个参数，接下来随机从未确定的参数中选取一个记为 kt，此时分两种情况：
        1. t <= T: 此时候选测试组的参数数量还达不到指定的强度。遍历该参数的所有可能取值，将每个取值和已经确定的所有参数进行组合，此时的组合仍然比一个 ucps 还小。遍历所有 ucps ，得出包含这个组合的 ucps 数量。选取包含这个组合的 ucps 数量最大的情况下，该参数的取值，作为该参数的实际值。
        2. t > T: 此时候选测试组的参数数量达到了指定的强度。遍历该参数的所有可能取值，对于每一个可能取值，需要从 t - 1 个已经确定的参数中选择 T - 1 个，和当前取值进行组合，得到一个大小和 ucps 相当的组合，判断是否是 ucps 之一。由于有（从 t-1 中选 T-1）个选取方案，将覆盖的 ucps 加起来得到总数。选取 ucps 总数最大的情况下，该参数的取值，作为该参数的实际值。
    • 对于这 M 个候选的测试用例，选择其中覆盖了新的 ucps 数量最多的那个，作为真实的测试用例加入到 Cover Array 中去。

  3. 重复上述生成测试用例的过程，直到 ucps 为空，即实现 T-way Coverage。

实现上的细节

测试用例和 ucps 的数据形式

我使用 [4, 3, 0, 2, 1] 这样的列表来表示一个 5 个参数的测试用例，其中的值 a 表示该参数取其可能的取值中第 a + 1 项（例如 0 表示取这个参数的第 1 个可能取值）。

使用 [-1, -1, 0, -1, 1] 这样的列表来表示一个 2 元的变量覆盖对，其中的 -1 表示该参数未被选择。

当存在重复的局部最优时，随机选择

因为 AETG 本身是一个贪心的算法，上述过程中也可以看出它有好几个取局部最优的过程。尤其在上述的算法描述中 t <= T 这个过程中，t == T 时，会发现，因为此时无论是选取哪个参数取值，最优情况只有 刚好是一个 ucps ，也就是说最多只被 1 个 ucps 包含。此时会出现大量的重复的局部最优解，然而在全局情况下，这些局部最优解有着巨大的性能差异，所以我们不能使用：

1
2
3
if ucps_count > max_ucps_count:
    max_ucps_count = ucps_count
    best_param_value = now_param_value

这种形式来取值，导致在同样的情况下，永远只会取最早出现的那个值，略过了后续的重复的局部最优解。

所以我做了这样的优化，当遇到重复的局部最优解时，将其加入一个列表，最后使用 random.choice(best_param_values) 来随机选取其一。因为 AETG 中，是从 M 个由随机过程生成的候选测试用例中选取最优来作为真实的测试用例，当 M 这个数量足够时，我们就能依靠随机选取重复的局部最优的贪心来更加接近全局的最优。

这个处理的效果是非常显著的，生成的结果对比如下：

未采用随机选择重复的局部最优：

品牌 能效等级 支持IPv6 类型 处理器 厚度 机身材质 内存容量 屏幕尺寸 Pairs
mechrevo 五级能效 no 高性能轻薄本 intel 奔腾 20.0mm 以上 含碳纤维 128GB 18.4英寸 36
mechrevo 五级能效 yes 高性能轻薄本 intel 奔腾 20.0mm 以上 含碳纤维 128GB 17.3英寸 15
mechrevo 五级能效 no 高性能轻薄本 intel 奔腾 20.0mm 以上 复合材质 128GB 17英寸 15
mechrevo 五级能效 no 高性能轻薄本 intel 奔腾 20.0mm 以上 金属+复合材质 128GB 16.0-16.9英寸 15
mechrevo 五级能效 no 高性能轻薄本 intel 奔腾 20.0mm 以上 金属 128GB 15.0-15.9英寸 15
mechrevo 五级能效 no 高性能轻薄本 intel 奔腾 18.1-20.0mm 含碳纤维 128GB 14.0-14.9英寸 15
mechrevo 五级能效 no 高性能轻薄本 intel 奔腾 15.1-18.0mm 含碳纤维 128GB 13.0-13.9英寸 15
mechrevo 五级能效 no 高性能轻薄本 intel 奔腾 15.0mm 及以下 含碳纤维 128GB 13.0英寸以下 15
mechrevo 三级能效 no 高性能轻薄本 intel 奔腾 20.0mm 以上 含碳纤维 64GB 18.4英寸 15
mechrevo 二级能效 no 高性能轻薄本 intel 奔腾 20.0mm 以上 含碳纤维 128GB 18.4英寸 8
mechrevo 一级能效 no 高性能轻薄本 intel 奔腾 20.0mm 以上 含碳纤维 128GB 18.4英寸 8
mechrevo 五级能效 no 高端游戏本 intel 奔腾 20.0mm 以上 含碳纤维 128GB 18.4英寸 8
mechrevo 五级能效 no 高端轻薄本 intel 奔腾 20.0mm 以上 含碳纤维 128GB 18.4英寸 8
mechrevo 五级能效 no 游戏本 intel 奔腾 20.0mm 以上 含碳纤维 128GB 18.4英寸 8
mechrevo 五级能效 no 轻薄本 intel 奔腾 20.0mm 以上 含碳纤维 128GB 18.4英寸 8
mi 五级能效 yes 高性能轻薄本 intel 奔腾 20.0mm 以上 含碳纤维 128GB 18.4英寸 9
mechrevo 五级能效 no 高性能轻薄本 intel 奔腾 20.0mm 以上 复合材质 64GB 17.3英寸 5
mechrevo 五级能效 no 高性能轻薄本 intel 至强 20.0mm 以上 金属+复合材质 128GB 18.4英寸 9
mechrevo 五级能效 no 高性能轻薄本 intel 奔腾 20.0mm 以上 金属 64GB 17英寸 3
mechrevo 五级能效 no 高性能轻薄本 intel 奔腾 18.1-20.0mm 含碳纤维 64GB 16.0-16.9英寸 4
mechrevo 五级能效 no 高性能轻薄本 intel 奔腾 15.1-18.0mm 含碳纤维 64GB 15.0-15.9英寸 4
mechrevo 五级能效 no 高性能轻薄本 intel 奔腾 15.0mm 及以下 含碳纤维 64GB 14.0-14.9英寸 3
acer 五级能效 yes 高性能轻薄本 intel 奔腾 20.0mm 以上 含碳纤维 128GB 18.4英寸 8
mi 三级能效 no 高性能轻薄本 intel 奔腾 20.0mm 以上 含碳纤维 128GB 18.4英寸 3

采用随机选择重复的局部最优：

品牌 能效等级 支持IPv6 类型 处理器 厚度 机身材质 内存容量 屏幕尺寸 Pairs
acer 三级能效 no 轻薄本 Apple M2 18.1-20.0mm 含碳纤维 24GB 15.0-15.9英寸 36
haier 一级能效 yes 高端轻薄本 intel i5 18.1-20.0mm 复合材质 32GB 13.0英寸以下 36
dell 二级能效 yes 高端游戏本 AMD R7 15.0mm 及以下 金属+复合材质 36GB 16.0-16.9英寸 36
lenovo 一级能效 no 游戏本 Apple M1 Max 20.0mm 以上 金属 64GB 17英寸 36
thinkpad 三级能效 yes 游戏本 龙芯 15.1-18.0mm 金属 48GB 17.3英寸 35
haier 五级能效 no 游戏本 intel i3 15.0mm 及以下 复合材质 20GB 18.4英寸 34
huawei 五级能效 yes 高性能轻薄本 AMD R3 20.0mm 以上 复合材质 16GB 17英寸 33
apple 一级能效 yes 轻薄本 AMD R9 15.0mm 及以下 含碳纤维 4GB 14.0-14.9英寸 33
hp 一级能效 no 高性能轻薄本 兆芯 15.1-18.0mm 金属 40GB 13.0-13.9英寸 32
huawei 五级能效 no 轻薄本 AMD 速龙 15.1-18.0mm 金属+复合材质 8GB 13.0英寸以下 32
mi 二级能效 no 高端游戏本 intel 奔腾 15.1-18.0mm 复合材质 4GB 13.0-13.9英寸 31
mechrevo 三级能效 yes 高端游戏本 麒麟 20.0mm 以上 金属+复合材质 32GB 13.0-13.9英寸 29
honor 五级能效 no 高端轻薄本 AMD R9 20.0mm 以上 金属 128GB 18.4英寸 29
asus 五级能效 yes 高端轻薄本 intel 奔腾 18.1-20.0mm 金属+复合材质 40GB 14.0-14.9英寸 28
acer 二级能效 yes 游戏本 Apple M1 Pro 15.1-18.0mm 含碳纤维 12GB 13.0-13.9英寸 26
lenovo 三级能效 yes 高端游戏本 高通 18.1-20.0mm 含碳纤维 6GB 18.4英寸 28
asus 二级能效 no 高性能轻薄本 intel 赛扬 18.1-20.0mm 金属+复合材质 128GB 17.3英寸 27
thinkpad 一级能效 yes 高端游戏本 intel i3 20.0mm 以上 含碳纤维 8GB 16.0-16.9英寸 25
haier 二级能效 no 高端轻薄本 AMD R5 15.1-18.0mm 金属 8GB 15.0-15.9英寸 24
mechrevo 三级能效 no 轻薄本 intel 至强 15.1-18.0mm 金属 12GB 16.0-16.9英寸 25
mi 二级能效 yes 高性能轻薄本 intel i5 20.0mm 以上 含碳纤维 64GB 17英寸 21
honor 五级能效 yes 高性能轻薄本 Apple M1 15.0mm 及以下 含碳纤维 6GB 16.0-16.9英寸 22
dell 三级能效 no 高端轻薄本 intel 赛扬 15.1-18.0mm 复合材质 24GB 14.0-14.9英寸 24
apple 五级能效 no 高端轻薄本 飞腾 18.1-20.0mm 含碳纤维 48GB 16.0-16.9英寸 23

我们可以观察到，不同测试用例间的参数取值重复的情况大大缓解，新覆盖的 ucps 数量的衰减慢了非常多，也就是每个用例可以新覆盖更多的 ucps，让总测试用例的数量大约又减少了 50% ~ 80%。

对于一个参数表为 [12, 4, 2, 5, 21, 4, 4, 13, 8] （共 9 个参数，数组中的数为每个参数的可能的取值的个数）的组合测试问题，取其 2-way 覆盖解：

测试用例数
全组合测试 16773120
AETG（贪心未优化） 1478
AETG（贪心优化） 302

心得

由于涉及到大量的数组计算和变换，我的 Python 实现在面对大量组合尤其是 3-way 及以上时，速度惨不忍睹（因为我的数组变换是全 Python 手写的）。如果需要更加高效的程序，也许 numpy 或直接换一个语言是更好的选择。

参考链接

为什么需要组合覆盖 why t-way coverage - turtle_fly - 博客园 (cnblogs.com)

The Automatic Efficient Test Generator (AETG) system | IEEE Conference Publication | IEEE Xplore