【论文转述】自适应随机测试:测试用例多样性的艺术

作者: 伊吖i | 来源:发表于2020-10-12 13:26 被阅读0次

自适应随机测试:测试用例多样性的艺术

image-20200911142409128

介绍：

随机测试概念简单，通常易于实现，能有效地检测故障，擅长以意想不到的方式运行系统(这可能不会发生在人类测试人员身上)，并且可能是源代码和规范不可用或不完整时唯一的实际选择。

随机测试：广泛，但低效。

作者提出——ART（自适应随机测试）

AIM：指导测试，提高随机测试效率。

核心：经验研究表明，程序的错误（program fault）往往与输入域中某一连续的输入失败区间相对应（记作失败模式 failure patterns）。ART即利用这种失败区间的连续性，来引导或是选择一组候选测试用例。

失败模式：

测试的本质：

从被测软件的可能输入集合（输入域）中抽样，并逐个执行抽取样本后判断。

输出不合预期的样本，意味着软件的失败（failure），软件失败的存在说明软件存在错误/故障（fault）（软件中具体代码的错误）。（故障与错误往往是多对一关系）

软件测试的本质目标:

选择合适的测试数据集，以最大化检测到的不同错误（faults）数量。

基于上述，在测试执行中，就需要考虑选择不同的会产生错误的失败模式。

ART 自适应随机测试:

给定一组先前执行的没有揭示任何故障的测试用例，远离这些旧测试用例的新测试用例更有可能揭示故障——换句话说，测试用例应该更均匀地分布在整个输入域中。

一个最基本的思路：

image-20200911152448988

生成k个候选用例，找与已有测试距离最远的候选用例。

image-20200911154250739

二维空间，选择第五个测试用例的过程。

（c2距离已有测试用例距离最远，因此将c2增加为t5）

评价指标：

用于比较这些方法的统计数据是检测第一次故障所需的平均测试次数，这通常被称为F-measure。

FSCS-ART要比一半的随机测试F值低30-50%

同作者的变体

RRT 限制随机测试 Restricted Random Testing

提出排斥域的概念，当测试用例在排斥域内则被排除。当随机生成的用例没有落在排斥域里，则将其加入测试。

分区ART ART by Partitioning

直接划分输入域为不同区，然后将测试用例平均分配到每一个分区。

拟随机测试 Quasi-Random Testing

基于点阵的ART Lattice-Based ART

以上变体的失败检测率表现都相似，不同的方法对某些特定的类型表现较好。

其他人的类似方法

Antirandom测试

区别：Antirandom测试几乎完全是确定性的；唯一的不确定性来自于集合中第一个测试用例的选择。此外，该方法需要提前选择测试用例的数量。

理论极限

基于失败模式连续性，确实存在提高随机测试性能效果的理论上限。

先考虑测试人员知道输入域中有一个单一的、连续的错误区域时的情况。

拉普拉斯的无差异原则(凯恩斯，2006)指出，如果决策者知道世界的可能状态，并且确实没有关于每个可能状态的合理性的信息，他们应该像每个状态具有同等可能性一样行动。在这种情况下，由于测试人员没有关于故障区域位置的信息，他们应该假设它同样可能位于输入域内的任何可能位置。

知道它连续，但不知道它在哪连续

设计一个选择测试用例的最优策略，并明确地表明它将有一个低于或等于任何其他策略的F度量(回想一下，F度量是一个平均值)。本质上，我们在整个输入域的规则间隔位置创建一个测试用例“网格”，并以任意顺序执行结果测试。在特定情况下，这样的策略可能会“走运”，并在第一个测试用例中显示失败。然而，在许多试验中，给定相同的失败率，这种策略的f检验至少是随机替换测试的f检验的一半。

也就意味着考虑错误模式连续性时，至多可在理论上达到50%的效率提高。

然后作者把这个推广的多个连续错误域也成立。

得到的结论or方向

ART的多种变体的效率提高都接近50%，一方面说明了不同的方法都已经接近理论最好效果，另一方面也表明错误模式连续性确实是一个紧密连续的区域。

之后的研究也就不该聚焦于进一步提高随机测试有效性的F值，而是研究开销更低的自动测试方法。

数值程序之外使用ART方法

为了将ART推广到一半的软件测试，有两个核心问题：

如何随机抽样
如何度量两个输入间距离

第一个问题不是ART固有，相关的研究相对成熟。所以核心在于第二个问题，如何度量差异大小。

距离的基本定义：

(a) D(p,q)≧0 [D(p,q)=0，当且仅当p=q] //恒正

(b) D(p,q)=D(q,p) //对称

(c) D(p,z)≦D(p,q)+D(q,z) //三角不等式

如果直接将所有的D（a,b)=0，则ART退化为一个普通的随机测试。

距离设计准则：

两个输入具有共同故障行为的可能性的估计——距离越小，它们触发相同故障行为的可能性越大。

直觉是，计算的相似性是故障行为相似性的一个很好的预测因素。因此，为了在非数字环境中有效地应用ART，需要替代方法来测量由两个测试用例的执行所产生的计算的相似性。

作者等人提出的一种差异度量

它可以应用于广泛的软件输入类型，基于奥斯特兰德和巴尔克(1988)为类别划分方法提出的类别和选择的概念。类别划分方法是一种基于规范的测试方法。测试人员必须首先确定决定被测软件行为的参数和环境条件，即所谓的类别。对于每个类别，选择被定义为互斥的值集，这些值集预计会触发类似的计算。

直觉上，两个输入有不同选择的类别越多，它们触发的计算就越不同。因此，具有不同选择的类别计数可以用作差异度量。

红房子和黑狗——d=2

红房子和红狗——d=1

（物品和颜色的类别靠人为划分

面向对象软件的背景下的另一种类型的差异度量

它们首先定义了一些距离度量或元素类型，如数字、布尔值、字符串和引用。接下来，他们描述了如何测量复合对象之间的距离，由三个元素组成——基于两种对象类型之间差异的类型距离、字段距离(匹配字段之间的距离)和递归距离(匹配引用属性之间的距离)。

扩展方向

自适应随机序列 ARS

大意：随机测试通常作为与其他策略比较的基准，ART的提高效果接近最优，可以考虑将其作为替代随机测试的新基准。随机生成序列也通常作为基准，所以ARS也可以考虑作为随机生成序列替代的新基准。

应用：回归测试

回归测试中，一个大的测试套件可能会随着时间的推移而积累，甚至到了每次进行更改时都不一定能运行所有测试套件的程度。因此，基于许多不同的标准，已经开发了各种技术来区分测试套件元素的优先级。

作者认为ARS可能是一种简单、有效和相对低开销的选择。

标准的准随机序列生成算法只生成非常少的不同序列；增强现实测序可以用来产生大量不同的序列。

基于失败（failure）的测试

作者认为相较于其他方法，ART是一个显示设计出来的基于失败而非错误的方法。

基于故障的测试描述了一类测试策略，旨在证明程序中不存在或存在某种类型的故障。

定义：基于对失败模式的不同知识（形状，大小，位置，数量），来选择测试用例的方法，是一个基于失败的方法。

ART利用的就是失败模式的连续性信息，设计的的方法。

如果将连续性与其他信息相互结合补充，就可能产生更多相关的算法。（eg，失败通常在边界产生，选择边界结合连续性就可能是一个新的基于失败的测试技术

两类测试技术都要借助现有经验。

在基于故障的测试的情况下，经验研究可以提供必要的信息，以优先搜索特定的故障类别；如果一类故障在实践中经常发生，搜索它们显然是更高的优先级。同样，有效的基于故障的测试必须基于对典型故障模式的经验研究，包括它们的几何形状和分布。

从另一个角度来看，基于失败模式的测试可以被视为一种专门的搜索问题。在这种观点下，当测试被执行时，来自测试的反馈会引导我们继续寻找导致失败的输入。

核心思想即：利用已有的测试结果信息，来指导接下来的测试选择

软件测试理论

我们相信我们的方法是新颖的，并且可以作为一个模型来建立对失败信息和软件测试之间的关系的更深的理解。对各种覆盖标准进行了大量的理论分析。这些分析表明，实现一种类型的覆盖可能意味着另一种覆盖（语句覆盖&分支覆盖）

意思就是，作者为了验证ART相关变体已经达到理论最优值，提出的理论检验方法可以推广，用来评估任何一个基于某种假设or经验的测试策略或方法上，来计算这种策略的理论最优，从而确定是改改进方法，还是提高效率。

测试用例多样性的作用

ART的产生源自于某种关于“扩散/域”的经验直觉。

这种域的概念可以被拓展成某种形式的多样性。然后结论就可以自然的变成：测试用例在整个输入域中的均匀分布导致了计算的多样性。

ART实现了一种非常简单的形式——也许是最简单的形式——测试用例多样性。

比例抽样(PS)策略(Chen和Yu，1996)规定从每个分区中随机选择的测试用例的数量应该与相应的分区大小成比例。

作者认为：PS最早出于普遍更优的安全可靠的角度去改善随机测试，而ART则是出于失败的聚集的猜想来改善随机测试，两者殊途同归，原因在于最终关注的其实都是输入域的多样性。

ART的这种多样性，不仅体现在整个测试套件中，也体现在其中的任何一个时刻。对于每一个当前执行的自己，实际上ART都在关注能够带来最大局部多样性的选择，这也是ART能够更早发现故障的原因。