摘要

现有的 Web 测试生成器从 Web 应用程序的导航模型中得出测试路径，通过手动或随机生成的输入值来完成。但是，手动测试数据选择的成本较高，而在不可行的输入序列中往往会产生随机生成的结果，但被测试中的应用程序拒绝了。只有在尝试执行大量测试执行后，随机和基于搜索的生成才能达到所需的模型覆盖级别，并且在执行过程中，需要与浏览器进行交互才能降低所需的覆盖率。在这项工作中，我们提出了一种新颖的 Web 测试生成算法，该算法根据之前的测试从多样性中预先选择了最有希望的候选测试案例。

1 简介

当今可用的现代 Web 应用程序提供了与本地桌面应用程序相同的高级用户交互功能，同时消除了站点部署，安装和更新所需的实例。例如，单页 Web 应用程序（SPA）通过动态更新文档对象模型（DOM）来实现动态响应，并通过 JAVAScript 功能来实现用户友好性。

为了测试这种复杂的软件系统，工程师通常采用诸如 Selenium 之类的测试自动化框架。在这种情况下，测试人员使用测试脚本来验证被测应用程序（AUT）的正确功能，该脚本可自动执行最终用户将在 Web 应用程序的图形用户界面（GUI）上执行的手动操作的集合，例如，通过单击来完成的交付活动。测试人员使用此类测试脚本以及必要的输入数据实施针对业务的测试场景。因此，每个测试案例都应沿着网络应用程序的导航图执行特定的测试路径。

尽管在自动测试生成方面已有研究进展，但在网络领域中仅提出了一些工具，遗憾的是，其仍然适用于当今可用的复杂系统 相当有限。 因此，迄今为止，诸如硒等系统级测试用例的开发仍大部分是手动执行的。

由于事件和相关数据的特定顺序，必须生成 Web 测试用例以确保启动，因此自动生成 Web 测试用例四倍速度超长。存在动态网页和事件基力的常用格式他们之间的皮疹。那么是 啊。测试路径（也称为抽象测试用例）是从模型中派生出来的，以确保能够覆盖航空图形，例如，第一次访问或语义交互事件。要生成可执行测试，测试路径需要指定适当的输入数据，这些数据可以手动或随机生成。

但是，这些方法有一些缺点，限制了它们在实践中的适用性。首先，随机输入生成使现有方法非常无效，因为它们可能（1）反复行使 AUT 的相同部分，而没有探索可能暴露出先前未知故障的新行为，或者（2） 产生不可行的测试，这会违反约束和对 AUT 的先决条件。在充分发现导航图之前，需要生成大量随机测试用例的缺点，这是非常低效的。此外，由于与浏览器的交互作用，Web 测试的执行时间很短，这在限制时序限制的情况下进一步支持了现有测试生成技术的适用性。 这样，所提到的技术主要依靠手动输入生成，这显示了昂贵的成本，并且受限于测试人员可用的测试资源（例如时间）。

 

图 1 PetClinic Web 应用程序的简化导航模型。 状态之间的转换用相应的动作标记，可以对其进行参数化。 粗体显示的路径表示覆盖率最大化的测试路径的实例，该测试路径是基于多样性的技术生成的。

在本文中，我们提出了生成系统级 web 测试用例的新的解决方案。我们的方法的目标是生成一组测试用例，使航空图的覆盖范围和输入数据的使用多样化，以应对在实践中不可执行或不产生任何覆盖改进的不可行情况。

评估新产生的测试案例的质量时，评估新产生的测试案例的质量时，关键的观点是评估新产生的测试案例的质量，只需评估其与先前执行的候选人之间的差异。基于多样性的测试生成降低了输入空间的局部最优区域的容量，其中相似的测试用例几乎覆盖了相同的环境和导航，并且在浏览器执行中只选择了其中的几个不同的场景和日期。

我们实现了名为 DIG（基于多样性的生成器）的工具，它会自动提取一个 Web 应用程序的通用模型，按照页面对象设计模式对每个网页中可能执行的操作进行基于代码的抽象。然后，选择测试用例（即。，可能） 的路径和输入）是基于神经系统的多样而产生的，完全有效地覆盖了血液。

我们的工作做出了以下主要贡献：

• 基于创新的 Web 应用程序的系统级测试用例生成器。
• 用于识别覆盖率和输入最大化的候选测试用例的算法。测试用例之间的听觉距离算法可以最大限度地减少浏览器执行所需的听觉距离。
• 我们的方法在称为 DIG 的工具中的实现，该工具自动提取由页面对象抽象组成的导航模型，并生成最大化导航序列和输入数据多样性的测试用例。
• 对六个开源 Web 应用程序进行 DIG 测试的经验评估。DIG 生成的具有较高覆盖率和故障检测率的测试套件的速度明显高于基于搜寻和基于搜索的测试生成器。

2 背景

我们提供了可以理解本文其余部分的网络测试概念。我们提供了有关 Web 应用程序，其特性和属性的通用模型的背景信息，并探讨了如何使用该信息来实现自动测试用例的生成。

2.1 导航模型

Web 应用程序的导航模型可以表示为状态流图（SFG），其中节点是网页的动态 DOM 状态，并且边缘之间是基于事件的转换。

定义 1（状态流图）。 Web 应用程序 W 的状态流图 SFG 是带标签的有向图，用 4 元组表示，其中：

（1）r 是表示 W 已完全加载到浏览器中时初始 DOM 状态的根节点（称为索引）。

（2）V 是表示节点的一组顶点。每个 v∈V 代表 W 的抽象 DOM 状态。

（3）E 是顶点之间的一组有向边，我们称其为动作。每个（v1，v2）|g|a∈E 表示当且仅当通过执行节点 v1 中的动作 a 达到了节点 v2 并且满足守护 g，才可能在两个节点 v1，v2 之间进行转换。

（4）在边（v1，v2）|g|a∈E 上给出一组保护。

（5）SFG 可以具有多边并且是循环的。

2.2 航空模型示例

图 1 显示了 PetClinic 的简化导航模型，这是一个允许兽医管理关于其客户和 pet 中心的信息的 web 应用程序，该应用程序与实验相同根据我们的评估。图中显示了八个表各州，每个州之间都有几个可能发生的转移。

其次，根据可行性的定义现象，分析了影响自动测试用例生成的新实例。

2.3 可行性

在给定的摘要 DOM 状态下，可能采取的行动 E 可能受到一个或多个保安人员的限制（又称前提条件）。

定义 2（守卫）。 在特定应用状态下，guardд（s，a，i）是布尔值，作用于动作 a 的可能输入值 i∈I。

为了使状态 n 和动作的目标状态（通常是另一个状态 n'或 n 本身）之间的转换，需要使防护人员满意。 应用程序状态 s 包括全局变量值，DOM 和跨用户交互保持可用的任何持久性数据。

因此，防护依赖项的可满足性是：（1）为给定操作 a，as 生成的输入值 i∈（2）由先前用户交互序列产生的应用程序的内部业务状态。

例如，在图 1 的所有者状态中，操作显示所有者允许向所有者信息状态导航。作为对此措施的保护，建议在执行操作之前，应用程序中必须存在由输入所有者名称标识的所有者。 （出于可读性考虑，在图中省略了防护罩。）因此，防护罩不仅取决于分配给显示所有者操作的输入所有者名称的特定值，而且还取决于应用程序的内部业务逻辑状态。实际上，必须由先前执行的操作（例如，由所有者执行）将显示的所有者事先插入到应用程序中。

回顾一下，如果在给定的应用程序状态下警戒输入值失真，那么我们认为这种过渡是可行的；否则是不可行的。

2.4 测试生成问题

给定 Web 应用程序的导航模型，Web 测试生成器的目标是自动提取动作序列并生成适当的输入，以全面行使应用程序的行为，从而潜在地覆盖导航模型中的所有转换。

定义 3（测试路径）。 测试路径是一系列测试状态，这些状态与未指定输入值的相应动作序列配对。

然后，可以通过使用测试路径实例化具体的输入值来定义最新情况。

定义 4（测试用例）。 测试用例是特定测试路径中相应动作序列的具体值序列。

例如，在 PetClinic 中，作为一个简单的测试路径，该路径可为 pet 添加新的访问路径，该路径包括测试状态序列⟨Index, Find, AddOwner, Owners, OwnerInfo, NewVisit⟩。相关的执行顺序是由⟨goToFind, addNewOwner, add, displayOwner, addNewVisit⟩提供的。

在此操作序列中，需要指定三个输入值：（1）info，所有者的数据要插入，由状态 AddOwner 的操作添加，（2）ownerName，所有者的名称，由状态所有者的操作显示所有者要求，以及（3）pet，要访问的 Pet 的数据状态，由操作 addNewVisist 要求。 动作 addNewVisit 有一个前提条件保护，该前提条件是由宠物标识的宠物必须在执行该动作之前存在。由于考虑的红色测试路径否是在执行 addNewVisit 之前通过任何动作添加的，因此对于输入宠物的任何可能值，均不能采用选择的测试路径。 因此，我们说这样的路径是不可行的。

定义 5（测试路径可行性）。 如果存在一个满足所有与测试路径中的动作有关的防护措施的输入参数-值分配，则有一条测试路径是可行的； 否则是不可行的。

2.5 现有的测试生成方法

将采用不同的策略来从导航模型中生成测试案例。在本节中，我们简单讨论了最显着的现有解决方案以及其局限性，这些动机促使人们需要更高效的方法。在第 3 节中，我们将着眼于我们基于新颖性的测试。

2.5.1 图访问方法。 广度优先和深度优先图访问算法已应用于 Web 应用程序的导航模型以得出测试路径（也称为抽象测试用例，即状态序列和动作序列使具体的输入数据无法执行）。 在工具 ATUSA 中，建议随机输入数据生成以填补测试路径和具体测试用例之间的差距。然而，随机生成的输入通常很少有机会生成可行的测试用例，因此，它们通常需要大量的输入生成和相应的测试执行。此外，ATUSA 生成了 32 个测试集，因为即使是简单的 5 抽象函数创建大量的测试状态，并相应地产生大量的测试路径。

2.5.2 基于语义的方法。或者，测试路径可以限制在那些进行语义相关的交互，即事件序列，其中事件的顺序影响交互结束时达到的状态。这种方法已经成功地应用于应用程序，但它产生了一系列严格的测试用例（语义交互事件序列），这些测试用例需要对输入数据进行大量的指定才能使其可执行。

2.5.3 基于搜索的方法。基于搜索的技术对输入空间进行迭代采样，选择最合适的候选测试用例，并选择使用遗传搜索运算符创建新测试用例。由于这些测试有效地引导生成更多的输入空间的测试用例，因此它们适用于系统级测试，一个有效的配合功能可以根据活动模型中提供的近似信息来定义。研究人员已经表明，这种方法可以引导搜索生成不受路径不可行性问题影响的测试用例。然而，这种方法需要为每个操作手动指定所有保护，这项任务对于测试人员来说既耗时又费力。事实上，这些信息依赖于 Web 应用程序的业务逻辑和有内涵的行为，而且 USCA 无法生成完全自动。另外，对功能的评估通常是因为在重新进行相同的测试之前，需要在浏览器中生成和执行大量候选测试。

2.5.4 摘要。虽然所有讨论的方法都为所需的输入值提供了渐近收敛的理论保证，但是当应用于 Web 应用程序时，它们的执行时间性能较差，例如，标准 Java 桌面应用程序。有一种说法是，为什么人们总是需要花费大量精力和精力来解决这个问题，这是因为在整个测试过程中，（2）都考虑到了局部因素的重要性。同样不可行的），因此增加了测试代算法的运行时间，却没有完全覆盖整个系统。本节中讨论的局限性（测试者的规模，计算成本高，需要正式的护卫规范）证明了对替代算法的研究是合理的，可能更合理，并且算法更自动化。

 

图 2 系统级 Web 测试生成方法

3 基于多样性的最佳生成方式

在概念上，我们通过适当的测试模型推导了我们的方法的主要步骤。图 2 描述了我们的方法的主要步骤。 面向对象的类，它们在网页上以可执行的方式公开这些操作。 最后，我们的测试生成器使用测试动作与输入数据之间的新度量距离来生成可以完全执行应用的测试。我们的方法不需要在安全的模型上指定防护软性动作。

我们现在将详细介绍方法的每一步，以及测试之间的距离的计算，这是在我们的运行示例中得到的例证。

3.1 测试模型提取

第一步，获取 Web 应用程序的导航模型。这可以通过手动探索 Web 应用程序功能来手动执行，或手动执行。我们采用这种方法：我们使用 Web 爬虫自动探索 Web 应用程序的状态空间（请参阅第 3.5 节，详细说明此模型的状态，然后在此状态下研究此模型的详细说明）。

然后爬虫检索到的一种通用模型可以生成一种基于中间代码的抽象，该抽象可以方便地支持基于多样性的自动测试用例的生成。我们使用页面对象（以下称为 POs）将其表示为 DOM，并按照其指示的方式将它们按照设计的方式按每种模型所指示的方式进行了模拟。 例如，在运行示例宠物诊所时，AddOwner 状态将由其自己的类表示，包含三个方法（add，goToIndex 和 goToFind）。

选择状态代表 PO 的动机是双重的：（1）在 Web 测试自动化中使用众所周知的页面对象并利用其模式，以增强测试用例的开发和可维护性，以及（2）它们可以从具有良好准确性的导航模型自动创建。

3.2 基于多样性的路径和输入生成

受到自适应随机测试的启发，该假设使得可以假定连续的故障区域，网络应用程序也可能具有连续的不可行区域。 相应地，在 Web 应用程序的情况下，测试用例多样性的主要优势是可以在整个范围内探索搜索空间，使导航序列采样的区域多样化。这预计将有助于逃脱本地解决方案，并避免产生可行的测试路径，从而避免了对各种可能的研究（即，多样的）的探索性的发现。 而来自连续区域的输入可能会暴露相同的程序故障。

基于多样性的测试案例生成的第二个优势是，相对于现有的随机性和基于搜索的方法，其效率更高。实际上，通过评估在以前生成的测试案例中的多样性并评估这种潜在的评估案例的质量，并使用这种度量来评估其潜在的潜力，从而增加了对各种行为的探索。

有趣的是，如第 3.3 节所述，可以在没有实际执行候选测试用例的情况下进行这种评估。算法 1 描述了基于多样性的路径和输入生成的整个过程。测试生成从一组无条件的测试开始，因此首先生成了随机的测试。该算法生成一组候选测试用例 C，实例化候选测试路径并带有具体的输入向量（第 8-10 行）。为了选择最有前途的候选者，将计算每个候选测试用例与当前已执行的测试用例集 Texec 之间的距离（第 11-15 行），并且仅执行最远的测试用例（第 16 行）。将测试用例限制为可行的前缀，以防其包括一个差异（第 17-18 行）。每当执行该测试的路径与实例之间的差异时，就会发生差异。测试用例仅添加到最终测试套件中，以增加导航模型 M 的覆盖率（第 19-20 行）。

算法 2 显示了如何创建候选测试路径。 在我们的表示中，V 表示 AST 序列，表示以 X 为输入向量序列的方法序列。 V，A 和 X 在主循环（第 5-11 行）中通过根据导航模型 M 在状态 v 可用的概率中随机选择具有统一概率的边沿⟩v，v'⟩a 来增量创建。

这些选择受到实际上必须从 v'保持目标方法的约束。最后，随机选择输入值的向量作为参数（第 8 行）。

3.3 测试案例之间的距离

算法 1 需要一个距离度量来评估测试用例之间的差异。 与面向对象的或数字应用程序测试不同，由于距离函数 ρ 还必须考虑到构成这种情况的作用序列，因此输入设置不能仅取决于输入值。因此，我们考虑到两个情况之间的差异性，考虑到不同情况之间的差异，我们设计了两个测试用例之间的旅行距离，并且， 通过使动作序列多样化，以及与之相关的输入值，我们推测我们可以逃离可行的测试路径区域，并且可以使应用行为多样化。

3.3.1 距离公式。 直观地讲，我们的距离公式包含两个术语，第一是测量要比较的两个测试用例中动作序列之间的距离，第二是测量两个序列中匹配动作所使用的输入值之间的距离。要计算第一项，距离函数 α 报告这两个序列中不匹配动作的数量。 根据每个匹配的动作，我们计算其参数值之间的标准化距离 β。

给定两个测试用例（ti，tj），其中 ti =⟨Vi，Ai，Xi⟩和 tj =⟨Vj，Aj，Xj⟩，距离 ρ（ti，tj）由公式（1），（2）给出：

 

在等式 1 中，符号 Vx :: Ay 表示这两个动作序列都由其动作 Ai，Aj 和适用的状态 Vi，Vj 标识。 这有助于消除使用相同名称表示不同动作的情况下的歧义。

函数 α 表示序列编辑距离，它确定两个序列中不匹配元素的数量（例如，当比较 a，b，b，c，to，e，b 时，4 = |⟨a，b⟩| + |⟨e，f⟩| ，c，f⟩）。 当比较⟨a，b，b，c⟩和⟨e，b 时，LCS 是最长公共子序列中的匹配索引的集合（例如，{（2,2），（4,3）} ，c，f⟩）。函数 β 计算两个匹配动作（分别在 Vi :: Ai 和 Vj :: Aj 中分别由 k1 和 k2 索引）的两个参数值序列 Xi [k1]，Xj [k2]之间的距离。最后，函数 δ 计算两个基本输入值软件类型之间的标准化距离（请参见表 1 ）。

等式 1 的第二项与两个序列中的动作 Ai [k1]，Aj [k2]相匹配。相应地，两个输入向量 Xi [k1]和 Xj [k2]具有相同的基数。函数 β 计算参数值 x 与两个匹配动作 y 的平均距离。 函数 δ 的运算根据操作中使用的参数类型而变化（请参见表 1）。输入距离 δ 在 0 和 1 之间进行归一化。对于字符串或数字类型，使用 Arcuri 等人提出的函数 η（x）= x/(x + 1)进行归一化。将值映射到范围[0,1]。

公式 1 类似于分支覆盖度的拟合函数的计算，通常在基于搜索的测试中采用。 在这种情况下，适应度函数的两个项分别是逼近水平和标准化分支距离。我们与该定义共享一个概念，即使第一项（动作序列距离）占主导地位，而仅在第一项不具有判别力的情况下重新排列为第二项（输入值距离）。实际上，α 的范围为 N，而 β 的范围为零，而零的范围为零 这样，每个动作对的对 ρ 的贡献就不会大于 1。直觉主义者认为，对动作的主要贡献来自于动作序列的距离，而每个匹配对的输入值距离则几乎是最小的非零动作序列（即，1）的贡献。

 

表 1 输入距离计算

3.4 实现

我们实现了一种名为 DIG（基于多样性的生成器）的 Java 工具，该工具公开可用。要检索 PO 测试模型，DIG 依赖于 Apogen。最后，在基于 EvoSuite 的实例上实现基于多样性的测试发生器，并在方法上进行了扩展，以评估 PO 模型。 最后，只有最多样化的候选者才能通过 Selenium Web Driver 无头执行模式执行。

4 经验验证

4.1 研究问题

我们针对以下研究问题进行了解答：

RQ1（效果）：基于分集，搜索和爬网的随机测试生成如何在状态覆盖率，代码覆盖率和故障检测方面进行比较？

RQ2（效率）：基于多样性和搜索的测试生成如何随时间推移进行效率比较？

RQ3（Distance Computation）：基于多样性的测试生成过程中的距离计算有什么意义？

RQ4（Manual POs）：在基于多样性和基于搜索的测试生成方法中使用手动定义的 PO 有什么作用？

4.2 主题系统

表 2 总结了受试者的主要特征。

 

表 2 实验主题

4.3 过程和计量

过程和计量数据如表 3 所示。

 

表 3 所有对象和方法的 RQ1，RQ2 和 RQ3 的有效性，效率和距离计算结果（自动 POs）。 粗体字的值表示 DIG 与 SubWeb 之间的统计上显着差异。 星号表示 DIGS + 1 和 DIGS 之间的统计显着性差异。 NC 表示不可比较的值，因为测试生成在给定的预算之前终止。

RQ1：基于分集和搜索的方法比基于爬行的随机方法实现了更高的状态覆盖、代码覆盖和故障检测。尽管效果相当好，但基于多样性的应用程序实现了良好的效果，因为它是完全自动化的。

RQ2：基于分集的方法比基于搜索的方法实现更高的覆盖率和故障检测率。

RQ3：距离计算带来的开销被效率和自动化方面的好处所掩盖。此外，所提出的距离度量的输入分量可以被丢弃，而几乎没有相关的惩罚。

RQ4：通过使用手动定义的 POs，基于多样性的方法在生成的测试套件所达到的结构覆盖方面优于基于搜索的方法。

4.4 对有效性的威胁

在我们的评估中使用有限数量的主题系统，就结果的可概括性而言，构成了外部有效性威胁。 我们试图通过选择六个使用现实世界的 JavaScript 框架开发的主题系统来缓解这种威胁，这些主题系统都包含不同的域，尽管为了更好地解决泛化威胁，我们还是选择了其他主题系统。

内部有效性的威胁可能来自实验的混杂因素。我们在现实世界的 Web 应用程序上，以相同的参数设置（例如，时间预算间隔）比较了所有竞争算法。手动的 PO 开发任务面临对有效性的威胁，因此必须遵循严格的系统性过程来阻止这种有效性。

结论有效性与否定性和统计测试的正确使用有关。为了减轻设定值的耗损，每次实验都要进行 15 次并使用非参数的 Mann-Whitney Utest 进行统计测试。

考虑到结果的可重复性，可以在线获取 DIG 和所有主题系统的源代码，从而使评估可重复且结果可重复。

5 讨论

5.1 有效性和自动化

通过将 PO 与测试生成相结合，基于多样性和搜索的方法比基于最新的基于爬网的 PO 不可知方法具有更高的状态覆盖率，代码覆盖率和故障检测。

由于需要指定手动前提条件，因此将 DIWebisally 自动化，而 SubWebisonly 则半自动化。 我们的结果表明，DIG 可以通过自动生成 PO 和测试用例，从而为测试人员节省大量时间。必要时，测试人员可以细化生成的 PO，使其没有动作或过渡，并重复测试的生成。

此外，由我们的方法生成的测试服务是基于页面对象设计模式的，这在可维护性方面具有已知优势。

5.2 效率

我们的效率证明我们的方法是可取的，特别是在严格的测试时间或在开发过程中经常执行测试用例的情况下。实际上，基于多样性的方法要比基于软件的开发方法和软件对 XP 的信任程度要高得多，这要比基于软件的方法和方法对这种方法的信心大得多。

5.3 效益可行性

在连续可行区域的猜想下，促进多样性不仅有利于彻底探索应用程序的行为，而且有利于自动生成测试用例的可行性。相反，基于搜索的方法使用保护性模型作为通用模型，可以指导用户进行搜索以找到满意的输入。

5.4 与手动 PO 的比较

Apogen 自动生成的 PO 通常要比手动开发的 PO 简单，因为要进行测试的操作的数量和复杂性。Apogen 根据从每个测试状态静态提取的操作创建方法。因此，在大多数情况下，这些方法可能会遗漏在 Web GUI 上可能会产生的复杂交互（对于策略 GUI 而言是不可能的）。 ，DIG 可以生成的可能的测试路径/案例的数量会降低。

尽管存在这些局限性，自动化 POs 在考虑的应用程序子集下仍可与手动 POs 竞争。测试人员可以采用一种有趣的选择，对自动生成的 PO 进行细化，从而以较低的开发成本实现与手动 PO 相同的性能。 总体而言，我们的经验结果表明，当可以使用高质量的 PO 时，基于多样性的方法要比其他所有方法都更有效（状态和分支覆盖率）和效率（达到覆盖率）。

致谢

本文由南京大学软件学院 iSE 实验室 2020 级硕士生王旭翻译转述