改进测试算法：软件测试中的数学方法

新的测试设计方法并不总是同时出现。现代测试实践的很大一部分是通过适应数学模型的细致的理论和实验工作而发展起来的。尽管成为一名优秀的测试人员不一定要成为一名数学家，但了解测试方法背后的理论基础可能是有益的。

最大化覆盖范围并最小化测试用例数量

可以应用数学逻辑来优化系统的代码覆盖率。让我们考虑一个简单的示例，其中包含两个分支和条件中的冗长逻辑公式的“if”语句：

 if ( (& a2) & (!(a2 || a4) ) || a3 ) { # action 1 } else { # action 2 }

为了涵盖这两个分支，有必要了解公式的结构。人们可能会想，能做什么呢？您始终可以详尽地测试这段代码（逻辑公式），从而产生 16 次测试。然而，这个数量相当多，应该努力减少测试数量。使用修改条件/决策覆盖 (MC/DC) 方法可以减少测试数量（产生 11-12 个测试）。如果分支机构覆盖率足以测试风险，则只需要进行两次测试，但尚不清楚是哪些测试。

为了解决这个问题，可以将布尔代数应用于逻辑公式：

 if( (& a2) & (! (a2 || a4) ) || a3 ) = = ( (& a2) & ( (!a2 || !a4) ) || a3 ) = = ( a1 & a2 & !a2 & !a4 || a3 ) = = 0 || a3 = a3

对原公式进行变换后，可以看出只有一个变量a3实际上影响真值。因此，获取测试用例变得更加简单（一个使用 a3 == false ，另一个使用a3 == false ）。此外，很明显代码没有经过优化，因为复杂的逻辑表达式仅依赖于一个变量是很奇怪的。不幸的是，这种情况在现实中很常见，而且提供的示例也相对简单。

综上所述：

• 2 测试是否使用详尽测试

• 2 MC/DC 方法测试

• 2 测试是否应用分支覆盖

  
  

一般来说，逻辑表达式可以使用代数、数学方法和算法来简化（最小化）。类似的方法至少有3种。如上所述，使用布尔代数的直接变换总是有效的。可以找到并应用表达最小化方法，该方法不仅依赖于数学和逻辑，而且还依赖于领域的特性来考虑特定领域的特征。

优化成对测试

成对测试方法涉及生成测试集，这种方式不是通过详尽的测试来测试输入参数的所有可能组合（这可能既耗时又耗费资源），而是设计测试集，以便每个参数值与每个参数值相结合。其他测试参数的值至少一次。这显着减少了测试用例的数量。

这是一种行之有效且经常使用的方法。然而，不幸的是，随着系统变得更加复杂，这种方法并不总是有效。问题出现了：成对测试是否足以彻底测试具有大量输入参数的复杂系统？这个问题引起了许多测试专业人士和研究人员的兴趣，其中包括美国国家标准与技术研究所 (NIST)。

• Pairwise finds 65-97% of errors
• 3-way finds 89-99% of errors
• 4-way finds 96-100% of errors
• 5-way finds 96-100% of errors
• 6-way finds 100% of errors

研究表明，成对测试在 65-97% 的情况下会发现错误。如果我们开始组合的不是参数对，而是三元组或四元组，即使用 k 路测试，我们会得到更多数量的测试，但也会发现更多错误。

例如，假设系统有两个参数，每个参数三个值，以及三个参数，每个参数两个值：

• Pairwise: 10 tests with 14% coverage
• 3-way: 18 tests with 25% coverage
• 4-way: 36 tests with 50% coverage
• 5-way: 72 tests with 100% coverage

您可以选择令人满意的测试覆盖率水平和可接受的测试用例数量。

成对的基础是包含 n 元组（对、三元组、四元组……）相同次数的值的正交数组。

成对和 k 路测试的常用基础是OA(N, V^k, t) ，其中：

• N 是行数

• k 是列数

• V 是列中不同值的数量

• t 是强度（t=2 表示成对）

  
  

在 OA 中，每组 t 列包含相同次数的所有 t 元组。

最好使用覆盖矩阵来代替正交矩阵。这些矩阵与正交矩阵的不同之处在于，每组值至少出现一次，而不是“相同的次数”。在这种情况下，测试会稍微少一些。覆盖矩阵可能会出现不正确的测试用例，但总的来说，测试过程要快得多。因此，测试过程显着简化。

CA(N, V^k, t)，其中：

• N 是行数
• k 是列数
• V 是列中不同值的数量
• t 是强度（t=2 表示成对）

在CA中，每组t列至少包含一次所有t元组。使用覆盖矩阵可以从成对测试转移到 k 路测试，而无需显着增加测试数量。

系统状态和更改系统状态的测试

通常（几乎总是），系统有两种以上的状态：“工作”和“不工作”。让我们考虑一下有股票订单的部分州。买入或卖出股票的订单必须经过一系列状态才能完成交易。首先，创建订单，然后由交易所确认，随后进行大量小额购买交易，最后购买或出售所需数量的股票。股票订单的所有状态都会反映在交易系统中，当然，所有转换和状态都必须经过测试。

几乎总是，要么测试所有状态，要么测试所有转换，但更常见的是，两者都经过验证。全面覆盖是可以实现的，但会耗费时间、成本和资源。

图和有限自动机

让我们考虑旅行商 (commi voyager) 问题和 de Bruijn 算法。理解该算法允许获得一组最优或足够最优的短路径就足够了，这些短路径可以在图中遍历以完全覆盖它（严格来说，可以使用完成类似功能的任何其他算法，或者可以发明一种自定义算法）。

• 首先，获取系统的初始状态并构建一个新图，其中顶点对应于原始图中的转换。
• 接下来，覆盖新图的顶点，即旧图的过渡。
• 有些路径是显而易见的并且结果非常短（这对于测试系统的状态和转换非常方便）。
• 继续修建其他道路。结果，它们可能会变得太长（这不好）。

让我们考虑以下示例来分析情况：

测试人员一共有三名。第一个将执行第一个测试，第二个将执行第二个测试，第三个将执行第三个测试。前两个将很快完成前两个测试，因为路径很短（与第三个相比，因为前两条路径很短），但最后一个将花费很长时间（因为第三条路径非常长）长的）。

如果应用de Bruijn算法，第三个序列可以被“切割”成几个较短的序列，并且所有测试的执行可以有效地并行化。

我们最终可以进行更多的测试，但在并行执行的情况下，测试将更快地完成，因为测试更短。

此外，随着测试的增多，其执行也更加灵活。所有测试可以同时运行，或者可以删除不感兴趣和不太重要的测试。可以将更高的优先级分配给通过系统最重要状态的测试。有很多方法可以利用算法的结果。

作为一个优点，该算法不使用特定领域的东西；它适用于系统的绝对抽象状态和转换。

在这种技术中，很大程度上取决于算法的使用方式。在最极端的情况下，测试人员可能对状态之间转换背后的逻辑一无所知。在这种情况下，长的状态转换链将被算法“切割”成几个短的状态转换链。其中一些链条可能会变得毫无意义。因此，需要评估获得的链的合理性以及对测试来说重要且有意义的链。无意义且不重要，但改变系统状态的可能路径可以提供对系统的哪个部分需要修改的理解，并且确切地是哪个部分将是显而易见的。

主要结论可考虑如下：

• 最小化逻辑表达式的算法可以以最小的努力提供最大的测试覆盖率。并不总是需要使用最小化算法——有时这是浪费时间；存在通用的方法。
• 通过一小组简短的测试用例可以实现完整的测试覆盖，这些测试用例易于并行化、自动化、灵活和独立。
• 对实际情况下应用程序使用情况的统计数据分析可以优化和调整现有的测试设计技术并实现必要的测试覆盖率，从而保证应用程序质量。
• 成对测试的修改允许比标准算法进行更深入的测试，测试覆盖范围更大，并且资源几乎相同。
• 在标准测试设计技术效率较低的情况下，某些算法可能会有效。
• 组合测试设计技术的失败存在一些挑战。
• 所获得的算法可以轻松适应不同的系统，并且不需要该领域的特殊知识。

至于小缺点，值得注意的是：

• 有些算法并不适用于所有情况，并且有效且相关；在许多情况下，标准测试设计技术同样有效，有时甚至更有效。
• 应用算法需要一些数学知识，有时还需要更多的时间来应用，因此它在许多情况下也可能成为至关重要的因素。