强化学习：基于好奇心驱动的强化学习的Web自动测试

题目：Automatic Web Testing Using Curiosity-Driven Reinforcement Learning出处：International Conference on Software Engineering (ICSE，2021)，高性能计算机高水平会议。摘要：Web测试长期以来被认为是一项众所周知的困难任务。即使在今天，web测试仍然严重依赖于手动操作，而自动

燕双嘤

1497人浏览 · 2019-09-30 20:57:27

燕双嘤 · 2019-09-30 20:57:27 发布

题目：Automatic Web Testing Using Curiosity-Driven Reinforcement Learning

出处：International Conference on Software Engineering (ICSE，2021)，高性能计算机高水平会议。

摘要：Web测试长期以来被认为是一项众所周知的困难任务。即使在今天，web测试仍然严重依赖于手动操作，而自动化web测试远未达到人的水平。web测试面临的主要挑战包括动态内容更新和隐藏在复杂用户交互和特定输入值下的深层bug，这些bug只能由巨大搜索空间中的特定动作序列触发。在本文中，我们提出了一种自动端到端web测试框架WebExplor，以实现对web应用程序的自适应探索。WebExplor采用好奇心驱动的强化学习来生成满足时序逻辑关系的高质量动作序列（测试用例）。此外，WebExplor在在线测试过程中增量构建了一个自动机，为进一步提高测试效率提供了高级指导。我们对六个真实项目（一个商业SaaS web应用程序）的WebExplor进行了全面评估，并对全球前50个web应用程序进行了实地研究。结果表明，在大多数情况下，WebExplor可以实现比现有最先进的web测试技术更高的故障检测率、代码覆盖率和效率。WebExplor还检测到商业web应用程序中的12个以前未知的故障，开发人员已经确认并修复了这些故障。此外，我们的研究进一步发现了3466个异常和错误。

1，引言

过去的几十年见证了网络技术前所未有的快速发展和创新。如今，web应用程序已变得与本机桌面应用程序一样强大。它们非常方便，也不需要复杂的安装。然而，由于web应用程序在客户端和服务器端以不同语言（例如HTML、JavaScript、C#和Java）实现了复杂的业务逻辑，因此很难对其进行测试。一般来说，浏览的网页越多，覆盖的状态越多，发现缺陷的可能性就越高。因此，人们提出了各种方法，通过生成测试用例来实现充分的探索。借助自动化框架（如Selenium[1]）进行手动设计是创建测试用例的有用方法。测试人员需要创建测试脚本，模拟用户在web应用程序图形用户界面（GUI）上的操作（例如，单击按钮和填写表单）[2、3、4、5、6、7、8、9、10]。然而，这种手工工作是劳动密集型的，成本高昂，测试的有效性在很大程度上取决于人类测试人员的领域知识。此外，web应用程序经常发展，手动编写的测试用例通常需要在测试新版本之前进行大量修改[11，12]。

基于随机的方法[13，14]生成伪随机操作来模糊web应用程序。尽管在实际开发中被广泛采用，但这种方法的缺点是显而易见的。也就是说，它们通常会创建无效的测试用例，比如对按钮执行输入操作。此外，测试是不平衡的，一些难以访问的网页可能永远不会被探索。

基于模型的方法【15、16、17、18、19】为被测试的web应用程序构建导航模型，然后通过随机或复杂的搜索策略相应地生成测试用例。尽管导航模型提供了指导，但现有的方法仍存在一些局限性。首先，构建的导航模型可能只覆盖web应用程序的一部分，限制了生成的测试用例的探索能力。如图1所示，无法测试第6页和第7页，因为它们不包括在导航模型中。此外，构建高质量模型通常需要领域知识[15]。此外，web应用程序的内容通常是动态更新的（例如，通过JavaScript代码执行），静态导航模型无法轻松捕获这些内容。其次，在web应用程序中，动作的长序列（例如，路径0→ 1.→ 2.→ 3）通常需要完成某些任务，如填写和提交表单。现实世界web应用程序的业务逻辑可以任意复杂。例如，只有在正确导航第5页时，才能访问第7页。对于随机或基于搜索的策略来说，生成有效的动作序列可能是一个挑战。

图1：浏览网页的直观可视化。

为了应对上述挑战，需要进行有效的端到端自动测试。最近，强化学习（Enhancement learning，RL）展示了其学习策略以测试复杂游戏[21、22、23、24]或Android应用程序[25、26、27]并与之交互的潜力，这为在自动web测试中应用RL提供了可能性。然而，由于以下原因，现有技术无法轻松地用于测试web应用程序。首先，测试领域不同，这使得RL建模完全不同。例如，奖励函数可能不同。游戏通常有具体的目标要实现（例如，赢得游戏或最大化分数），而在web测试中则不是这样。状态定义和抽象也不同。游戏【23】根据API的输出定义状态，Android测试【25】使用现有工具UIAutomator【28】提取结构作为状态，这两种方法都不适用于web测试。其次，RL面临的一个根本挑战是如何进行有效的勘探，尤其是在环境空间巨大的情况下【29，30】。现有技术[21、23、31]主要通过简单的奖励函数来指导探索，这对于具有复杂业务逻辑和频繁动态更新的web应用程序来说可能是无效的。因此，需要对基于RL的web测试进行更有效的探索。

考虑到web应用程序的动态性和高度交互性，非常需要一种有效的无模型web测试技术。在本文中，我们提出了一个新的web测试框架WebExplor，它执行端到端的自动化web测试。WebExplor利用RL对web应用程序执行自适应搜索并生成高质量的操作序列，这可能是发现新页面的先决操作（例如，提交前填写表单）。特别是，WebExplor在不断训练智能体策略的同时进行动态测试（而不是只在训练后使用的常规AI解决方案）。为了在测试过程中实现高覆盖率和高效率，我们首先提出了基于HTML页面的状态抽象。然后，我们提出了一个好奇心驱动的奖励函数，它为RL的探索提供了低级指导，使得学习到的策略能够探索web应用程序的更多行为。为了避免陷入局部最优，特别是在学习空间巨大的情况下，我们进一步提出了一种确定性有限自动机（DFA）引导的探索策略，为RL高效地探索web应用提供了高级指导。特别是，DFA记录了RL勘探期间访问的过渡和状态，并不断更新。当RL陷入困境时（即在给定的时间预算内找不到新状态），WebExplor根据好奇心从DFA中选择一条路径并引导RL沿着这条道路进一步探索。低级指导（来自奖励功能）和高级指导（来自DFA）在实现有效的web测试中都起着重要作用。为了证明我们的技术的有效性，我们实现了WebExplor，并对六个真实项目的研究基准[15]和一个商业SaaS web应用程序进行了大规模评估。我们还对全球排名前50位的web应用程序进行了一项野外研究[32]。本文的贡献总结如下：

我们提出了一种新的web测试框架WebExplor，以高效地测试真实世界的web应用程序。据我们所知，WebExplor是第一个利用强化学习的端到端web测试框架。
我们提出了好奇心驱动的奖励函数和DFA来指导RL有效地探索web应用程序的各种行为。
我们在六个开源web应用程序、一个商业web应用程序和前50个真实web应用程序上全面评估WebExplor。在商业应用程序中，WebExplor发现了12个以前未知的故障，包括逻辑和安全缺陷，并由开发人员确认和修复。此外，在前50个web应用程序中发现了3466个异常和错误。

2，相关工作

2.1，Web应用程序和强化学习

典型的web应用程序要求最终用户输入一系列操作（例如，单击）进行交互，这反过来会改变web应用程序的状态（例如，URL或GUI）。该过程可以建模为马尔可夫决策过程（MDP）[33]。MDP可以定义为4元组 $<S,A,R,P>$ ，其中 $S,A$ 分别表示状态集和动作集。如图2所示，智能体（测试人员）在时间范围内与环境（浏览器）交互。在时间戳t处，智能体观察状态 $s_t\in S$ ，并在执行 $a_t \in A$ 之后，智能体立即收到奖励 $r_t=R(s_t,a_t)$ ，环境可以更改为新状态 $s_{t+1}\sim P(s_t,a_t)$ 。 $R(\cdot)$ 和 $P(\cdot)$ 是奖励函数和概率转移函数，它们都只依赖于前面的 $s_t$ 和 $a_t$ 。

图2，网络交互是一个马尔可夫决策过程。

智能地，智能体选择操作 $a\sim \pi(s)$ 根据概率策略函数 $\pi(\cdot)$ 执行。与环境交互的智能体会产生如下轨迹：

$traj=(s_0,a_0,r_0,...,,s_t,a_t,r_t)$

其中，下标表示有限时间范围内的不同时间戳。每个轨迹都有一个回路，定义为 $\sum_{t=0}^T\gamma^tr_t$ ，奖励折扣系数 $\gamma \in[0,1)$ 。一般来说，RL的目标是找到一条收益最大的最优轨迹，而不是不同的轨迹。然而，这通常不是web测试的目标，web测试旨在探索不同的轨迹和状态。因此，需要一个自适应奖励函数来引导RL持续生成不同的轨迹，这将在第III-C节中详细介绍。

2.2，问题定义

一般来说，对于一个web应用程序，测试的目标是生成操作序列以及适当的输入，以便探索应用程序的不同状态和行为，可能涵盖更多逻辑应用程序场景【15】。

定义1（Web状态）：状态 $s$ 是对Web应用程序当前状态（例如HTML页面）的描述。从人类的角度来看，捕获HTML页面变化的图像（即屏幕截图）是web状态的自然表示。然而，由于动画的广泛使用，图像可能无法可靠地表示web状态（例如，两个完全不同的图像可能对应于web应用程序的相同状态）。相比之下，HTML页面的代码更为精确，因为它对HTML页面的URL和结构特征进行了编码。因此，我们通过分析HTML页面的代码提出了一种新的状态表示（见第III-B节）。除非另有说明，否则具体的HTML页面实例称为状态。

定义2（操作）：操作 $a$ 是给定web状态（即HTML页面）中的有效操作。给定web状态，我们关注可操作的DOM元素（例如，链接、按钮或输入框），这些元素上的操作可能导致应用程序状态的更改（例如，提交表单或URL跳转）。值得一提的是，不同的状态可能包含不同的操作DOM集。例如，在图3中，主页有5个有效操作（即导航栏中的元素），而“添加所有者”页面有6个以上的有效操作（输入框和按钮）。

图3，添加新所有者的操作顺序

定义3（测试用例）：测试用例是一系列动作 $(a_0,...,a_t,...)$ 和必要的输入值。例如，在图3中，“添加所有者”功能由三部分组成：导航到添加页面、填写表单和单击提交按钮。图3显示了一个用于测试“添加所有者”功能的可行操作序列（红色）。该序列与必要的输入一起构成一个测试用例 $(a_0,...,a_7)$ 。当在可输入元素上操作时，我们的技术将提供一个合适的值，以使测试用例继续，这将在第III-B节中详细介绍。与现有工作类似【15】，我们说，如果在测试用例执行过程中抛出异常或错误，测试用例将失败，包括JavaScript运行时异常、客户端错误或服务器错误，这些可以通过返回的状态代码进行分析【34】。为简单起见，我们在后续章节中将异常和错误称为失败。

定义4（Web测试）：对于Web应用程序，测试人员的目标是学习自适应策略 $\pi$ ，以连续生成用于Web探索和故障检测的测试用例。直观地说，发现的状态越多，发现故障的可能性就越高。因此，web测试的目标是生成能够到达更多不同状态的测试用例，在这些状态上可以发现故障。值得一提的是，发现能够触发业务逻辑（例如，创建数据）的测试用例对于测试至关重要，因为这可能是发现新场景（例如，编辑数据）的先决条件。

3，自动WEB测试

3.1，WebExplor概述

简而言之，WebExplor是一个端到端框架，旨在以在线方式实现自动web测试。它的目标是自动生成不同的操作序列，以探索测试中的web应用程序的更多行为。为了实现这一点，WebExplor利用好奇心驱动的强化学习（RL）不断优化策略，该策略可以生成不同的测试用例。特别是，RL训练和web测试是交织在一起的，这与通常在部署前执行培训的AI解决方案不同。图4显示了WebExplor的概述，它包括三个主要组件：

预处理组件将HTML页面映射到抽象状态。其主要目的是避免网页动态更新导致的状态爆炸，以便有效地学习好的策略。
好奇心驱动的策略学习组件旨在学习可以探索web应用程序不同状态的策略。
DFA引导的探测组件通过维护一个不断更新的确定性有限自动机（DFA），记录所有访问状态及其频率，进一步提高了RL探测的效率。当RL无法在特定时间预算中发现新状态时，WebExplor将基于DFA的全局信息选择一个新颖的状态作为下一个探索的起点，以免被困在本地Optima周围。

图4，WebExplor的工作流

算法1给出了我们方法的细节。WebExplor将目标web应用程序 $env$ 和预处理函数 $\varphi$ 作为输入，并输出一组失败的测试用例 $F$ 。WebExplor首先初始化策略 $\pi$ 、DFA M和失败的测试集F（第1行）。然后，它不断测试web应用程序，直到预定义的时间预算用完为止（第2行）。在测试期间，为了避免到达无法跳转到其他页面并继续的“卡住的网页”，我们限制了一个测试用例的最大步骤数（第7行）。在达到最大数量后，我们重置web应用程序：跳转到默认主页 $p^{'}$ （第3行），设置初始操作序列，其中仅包含一个空操作 $\varepsilon$ （第4行），并获取初始状态 $s^{'}$ （第5行）。每个测试用例都从初始状态开始，即主页（第6行）。WebExplor通过在当前页面 $p^{'}$ （第8行）上执行当前操作序列动作来执行动态测试（例如，提交表单）。在执行过程中，WebExplor监视浏览器控制台的状态，以便自动捕获故障。环境返回一个新的HTML页面 $p$ 和错误状态。如果发现错误，测试用例将添加到失败的测试集中（第10行）。WebExplor对当前页面进行编码，并返回相应的状态 $s$ 和状态 $s^{'}$ 中的有效操作 $va$ （第11行）。如果WebExplor无法在一定时间内识别新状态，则RL可能会进入局部最优。WebExplor检查记录全局访问信息的DFA $d$ ，并选择一个访问较少的跟踪（第14行）。它返回轨迹 $t$ 和动作序列 $act$ ，从中可以恢复跟踪。然后，web应用程序重置为主页（第15行），当前步骤的数量设置为轨迹 $t$ 的长度（第16行）。

探索一个状态 $s$ 后，WebExplor计算好奇心奖励 $r$ （第18行）。策略 $\pi$ 使用当前的转换 $(s^{'},a,s)$ 及其奖励 $r$ （第20行）进行训练。此外，DFA $d$ 和当前测试用例将使用转换更新（第21-22行）。通过将当前状态 $s$ 馈送给策略 $\pi$ 来选择下一个操作（第23行）。然后，更新上一个状态和HTML页面（第24-25行）。

3.2，预处理

预处理：对于通过强化学习进行的策略学习，我们需要定义状态表示。一种简单的方法是利用网页表示（例如GUI或HTML）。然而，如果采用这种方法，由于web应用程序的动态特性，状态的数量可能非常大，甚至是无限的。例如，如果用户操作不同（例如，不同的表单值或无限滚动页面），HTML文档可能会不同。因此，采用HTML文档作为状态常常会遇到状态爆炸问题，导致RL的效率低下[35]。为了克服这种局限性，我们提出了一种新的状态表示。直觉告诉我们，关注相同业务逻辑的HTML页面应该合并到一个状态中。例如，在网页中，表格的内容可能不断更新（例如，通过添加或删除项目）。虽然HTML文档可能会有很大不同，但这些页面看起来仍然相似，并且处理相同的用户交互。我们不会将这些页面视为不同的状态。

给定一个HTML页面，我们使用其URL和HTML文档作为业务逻辑的近似值。很直观，如果两个页面具有相同的URL，并且它们的HTML文档非常相似，则它们更有可能关注相同的业务逻辑。我们认为类似的页面代表相同的状态，算法2描述了如何区分不同的页面。其基本思想是计算两个页面的HTML结构相似度。如果结构相似性（通过标签比较[36]）高于阈值，则它们更有可能集中在相同的业务逻辑上，并应被视为相同的状态。算法2将HTML页面的代码作为输入，并输出当前页面中的状态 $s$ 以及一组有效操作 $va$ 。在测试期间，我们使用 $S$ 表示现有状态。

我们采用浏览器内置协议[37]过滤一些元素（例如，无渲染或不可见），只保留可以操作的元素，即本页上的有效操作（第2行）。这些元素包括可单击的按钮、链接、输入框、选择器。接下来，我们检查当前页面 $p$ 与之前状态中的页面之间的相似性，直到找到一个相似的状态。具体来说，对于每个之前的状态 $s$ ，我们获取其页面信息（第4行），并计算 $p$ 与 $s$ 中页面之间的相似度，如下所示。首先，我们比较了它们的URL。直觉上，如果URL不一样，页面往往会执行不同的业务逻辑。因此，我们不认为它们是相同的状态（第5行）。否则，我们计算两个HTML文档之间的相似度（第7行）。更具体地说，我们将HTML文档转换为标记序列，并采用格式塔模式匹配算法来计算两个序列之间的相似度。如果相似度高于预定义阈值，则返回先前存在的状态 $s$ 和 $va$ （第9行）。请注意，我们提取HTML文档中的所有标记，而不进行任何过滤，这样HTML中的任何功能信息都不会丢失。如果当前页面与任何现有状态不匹配，我们将使用当前页面的代码（第10行）创建一个新状态 $s$ ，将其添加到 $s$ 中并返回结果。值得注意的是，不同的URL可能代表相同的业务逻辑，从而创建与相同业务逻辑相对应的多个状态（第5行）。然而，这样的通信几乎不会造成性能损失，也不会影响WebExplor的可靠性。

同时，WebExplor专注于生成动作的主张而不是输入值，即使输入值也会影响测试过程。要与先前的工作[15，38]保持一致，并执行测试程序，当在输入元素上操作时，将根据W3C标准[39]生成随机值。请注意，WebExplor可以利用字典或用户指定值来增强测试功能，这将作为未来工作进行研究。

3.3，通过好奇驱动RL进行测试

通过好奇驱动RL进行测试：WebExplor利用RL通过直接与web应用程序交互来实现端到端测试。具体来说，目的是学习一种策略（即 $\pi$ ），该策略提供了一种生成不同测试用例的探索策略。为了实现这样的政策，我们需要定义一个有效的奖励函数来确定最优的政策。奖励函数。常见的RL任务（例如，游戏玩法）通常具有具体的目标，例如赢得游戏或获得高分，从而简化奖励功能的设计[40，41]。但是，在Web测试中，奖励功能设计变得具有挑战性，因为目标是模糊的，即探索尽可能多的Web应用程序行为。此外，可以动态更新Web应用程序，表明该目标也应动态调整。为了应对这一挑战，我们利用好奇心的概念，这一概念是为了解决RL中的粗略奖励问题而提出的【42，43】。具体而言，我们设计了一个好奇心驱动的奖励函数，该函数采用了一种通用的自适应机制来指导探索，从而可以达到不同的状态。对于好奇测量（算法1中的第18行），在测试期间，WebExplor维护一个访问计数表，以记录每次转换的次数（用 $N(s^{'},a,s)$ 表示）。好奇心由MBIE-EB来衡量【44】：

$curiosity(s^{'},a,s)=\frac{1}{\sqrt{N(s^{'},a,s)}}$

$N(s^{'},a,s)$ 被初始化为1。每次当状态 $s^{'}$ 通过执行动作 $a$ 转变为 $s$ 时，相应的 $N(s^{'},a,s)$ 增加1。

Q-learning：WebExplor利用无模型RL算法Q-learning[45]优化策略，并提供好奇心驱动的奖励。Q-learning有一个函数 $Q:S\times a \rightarrow R$ ，返回状态动作对的Q值。每次从以前的状态 $s^{'}$ （即， $(s^{'},a,s)$ ）到达新状态 $s$ 时，我们更新Q函数（算法1中的第20行）：

$Q(s^{'},a)=curiosity(s^{'},a)+\lambda max_{a^{'}}Q(s,a^{'})$

式中 $\lambda \in [0,1]$ 是一个折扣系数。Q函数保持动作之间的时间关系，因为Q值将递归地传播到先前状态中的值。

基于Q函数，策略 $\pi$ 使用Gumbel Softmax方法测量状态 $s$ 中有效动作的权重【46】：

$p(a)=\frac{exp\left ( \frac{Q(s,a)+g_{a }}{\tau} \right )}{\sum_{a_i\in A}exp\left ( \frac{Q(s,a_i)+g_{i}}{\tau}\right )}$

式中， $A$ 是状态 $s$ 下的有效作用集， $\tau=1$ 是温度系数， $g(\cdot)$ 是从 $Gumbel(0,1)$ 分布中采样的i.i.d噪声。具有更高Q值的动作更有可能被选择用于交互（算法1中的第23行）。

这使WebExplorer能够在探索和利用之间取得平衡。发现新状态的操作将获得较高的好奇心奖励，并且更有可能被选中执行。这种特性确保了有效的利用，因为这种行为很有可能发现不同的行为。同时，好奇心随着动作的执行而降低，从而选择其他执行较少的动作来执行。这有助于充分的探索，并有助于在web应用程序中找到复杂的业务逻辑，我们将在评估中演示这一点。

图5，好奇心模型的直观说明

实例图5说明了基于好奇心的RL如何用于web测试，以及它如何探索复杂的业务逻辑。假设WebExplor从根状态 $s_0$ 开始，并执行不同的操作 $a\sim \pi(s)$ 执行。执行操作会导致状态转换，例如， $a_{(0,1)}$ 会导致 $s_0\rightarrow s_1$ 。最初，选择 $a_{(0,1)},a_{(0,4)},a_{(0,6)}$ 的概率是相同的。假设 $s_3$ 首先通过红色路径覆盖（图5（a）），然后 $Q(s_2,a_{(0,4)}),Q(s_1,a_{(1,2)}),Q(s_0,a_{(0,1)})$ 的值将通过路径反向传播更新。通过这种方式，时间关系（沿着这条路径）被构建并编码在策略 $\pi$ 中。好奇心奖励 $curiosity(s_0,a_{(0,1)},s_1)$ 降低。在图5（b）和图5（c）中，选择动作 $a_{(0,4)},a_{(0,6)}$ （具有更高的好奇心）。请注意，在达到 $s_6$ 后，由于特定的业务逻辑，一些以前无效的操作（例如， $a_{(1,7)}$ ）可能会变为有效。例如，表中的项目只有在添加后才能删除。在这种情况下，随着 $curiosity(s_0,a_{(0,6)},s_6)$ 的降低， $a_{(0,1)},a_{(0,4)}$ 重新获得被选中的机会，这对于探索新激活的状态（即 $s_7$ ）至关重要，从而打开一个新的未触及区域进行探索。

3.4，DFA引导探索

DFA引导探索：探索被广泛认为是强化学习中最具挑战性的问题之一[33、42、43]。在web应用程序中，通常通过按特定顺序执行操作（例如，办公自动化（OA）系统中的审批流程）来触发功能。随着行动的顺序越来越长，探索变得更具挑战性。尽管好奇心驱动的奖励函数为行动选择提供了指导，但由于其随机性，RL选择其他行动的概率仍然很低，尤其是在一长串行动中，这会中断目标函数的测试。考虑图6中的示例，策略 $\pi$ 的概率为0.9，选择正确的操作（红色箭头）表示 $s_{m+1}$ 。然而，到达 $s_{m+1}$ 的可能性只有 $0.9^5=0.53$ ，因为只要策略采取行动，路径就会中断。路径越长，中断可能发生的频率就越高，从而更难实现理想的过渡，尤其是在面临长路径时。

图6，长路径过渡的直观说明

为了应对这一挑战，我们建议在测试期间构建一个动态确定性有限自动机（DFA），这为推进RL勘探提供了高水平的指导。具体来说，如果一段时间后找不到新的状态，WebExplor会开始从DFA中找到一个好奇心最大的过渡。然后，检测可以到达该过渡的最短路径，使得RL可以直接到达该过渡。

定义5（DFA）：确定性有限自动机（DFA）M是一个5元组 $(S,A,\delta ,s_0,F)$ ，其中 $S$ 是一组有限的状态， $A$ 是一组动作， $\delta :=S\times A \rightarrow S$ 是一组过渡， $s_0$ 是初始状态， $F$ 是一组有限的状态，不能过渡到其他状态。

在测试过程中，一旦探索到新的转变 $(s^{'},a,s)$ ，DFA将被更新，即 $\delta :=\delta\cup \left \{ (s^{'},a,s) \right \}$ （算法1的第21行）。算法3提出了好奇心驱动的轨迹选择的基本思想。从DFA中，我们首先选择好奇心最高的轨迹 $(s_m,a_m,s_{m+1})$ 。然后，我们采用Dijkstra算法[47]来确定能够到达目标 $(s_m,a_m,s_{m+1})$ 的最短跟踪。使用此跟踪，RL可以直接还原到目标转换。直觉上，有些过渡可能非常深刻，因此RL很难实现。对于这些转换，WebExplor利用DFA进一步提高了探索效率和测试效率。

从理论上讲，非确定性有限自动机可以更准确地表示随机环境的动态性。然而，由于以下原因，我们使用DFA：1）自动机用于指导选择一条可行的勘探路径。由于动态因素（如网络），DFA中的一条路径可能不可行，但不会影响WebExplor的可靠性，因为动态执行会忽略这些不可行的路径；2）非确定性有限自动机的构造成本可能更高，尤其是在估计转移概率方面。考虑到自动机构造的效率和粒度之间的权衡，DFA对于WebExplor来说是一个足够好的解决方案。

4，实验评估

我们已经基于Python 3.7.6和PyTorch 1.5.0实现了WebExplor，代码超过5000行1。为了证明WebExplor的有效性和效率，我们对以下四个研究问题进行了实证评估。

RQ1（代码覆盖率）：WebExplor在代码覆盖率方面的探索能力如何？
RQ2（故障检测）：WebExplor检测web应用程序故障的效果如何？
RQ3（DFA探索）：DFA在测试期间指导勘探的有效性如何？
RQ4（可伸缩性）：WebExplor在测试真实世界的web应用程序方面有多有效？

4.1，实验设置

1）基准：我们的大规模评估使用了三个基准，包括之前工作中的一个研究基准[15]，用于将WebExplor与最先进的技术进行比较，一个用于评估WebExplor可扩展性的前50个真实世界web应用的基准[32]，以及一个用于进行详细案例研究的工业web应用程序。

研究基准：我们采用了一个基准，其中包含六个流行的GitHub项目（每颗有50颗星）[15]。这些项目使用六个最popular的JavaScript框架：Dimeshift（Backbone.js），PageKit（vue.js），Splittypie（Ember.js），Phoenix-Trello（Phoenix/Re-recat），retroboard（retroboard）和petclinicic ardicic of（Angularjs）。
真实世界的web应用程序：根据排名[32]，我们选择了世界上排名前50位的web应用程序进行评估。为了研究可伸缩性，我们直接利用WebExplorer对这些应用程序进行端到端测试，而无需进行微调。
工业web应用程序：进一步的案例研究采用了复杂的软件即服务（SaaS）系统。出于匿名审查的原因，我们省略了系统名称。

2） Web应用程序故障：在后续实验中，我们收集浏览器控制台中报告的系统级故障（定义见第II-B节），以研究相关方法的故障检测能力。请注意，用户级故障可能会也可能不会导致系统级故障，这取决于系统的健壮性。例如，如果web系统能够很好地处理用户级故障（例如，严格的输入字段检查），则不会发生系统级故障。否则，WebExplor将触发并捕获故障。为了确定故障的根本原因（如用户或系统），我们采用手动分析。值得强调的是，所有发现的故障都是手动检查的，以确保抛出的异常和错误实际上是故障（即没有假警报）。

3）基线方法：为了评估WebExplor的有效性，我们选择三种最先进的方法作为基线进行比较研究。这些基线包括基于模型到无模型的算法。此外，采用了一种适应Monkey（13）思想的随机策略作为基线。此外，为了评估利用DFA的优势，还实施了一种WebExplor变体用于消融评估。

DIG【15】是一种基于导航模型的方法，利用基于多样性的测试用例生成器进行web测试。
SUBWEB【5】是一种基于导航模型的方法，考虑到未覆盖的分支，并使用基于搜索的策略来实现web测试。
Crawljax【14】是一种无导航模型的方法，可以动态发现和聚类页面，并采用基于爬行的随机测试用例生成器进行web测试随机[13]是一种无模型的方法，随机选择一种可用的操作来探索web状态。
WebExplor（无DFA）是没有DFA指导的WebExplor的一个变体。

4）配置：对于所有实验，我们为每个工具提供相同的时间预算（即30分钟）。为了从统计学角度抵消随机性，我们将每个实验重复15次，并计算平均结果。对于预处理中的相似度，我们设置了0.8作为阈值。如果在2分钟内没有发现新状态，DFA将为WebExplor提供高级指导。对于RL中的贴现因子，我们在所有实验中设定λ=0.95。我们对花费300多个CPU小时进行了全面评估，即6个项目*7个设置（5个工具）*0.5（单轮小时预算）*共15次重复。此外，在测试期间，导致外部链接的操作（通过域检查）将在测试期间记录，标记为无效操作，并且不会在后续测试中执行。

4.2，代码覆盖率（RQ1）

为了进行全面比较，对于DIG和SUBWEB，我们使用导航模型，该模型分别基于自动和手动生成的页面对象（由APO和MPO表示）。为了消除实施偏差，APO和MPO都直接采用了之前工作中的方法【15】。分支机构覆盖率比较JavaScript代码的在六个Web应用程序上进行。表I总结了15次运行的平均结果，其中粗数字表示最佳结果。总体而言，我们有以下发现。

在大多数情况下，基于模型的方法DIG和SUBWEB可以实现比无模型方法Crawljax和Random更好的分支覆盖率。这是因为导航模型可以提供更多的信息（例如web结构），这有利于有效的测试。然而，一个反事实的发现是，无模型WebExplorer在代码覆盖率方面取得了竞争性的性能，在4/6的web应用程序中（表i中的粗体数字）显著优于基于模型的方法（即，通过Mann-Whitney U检验[50]在0.05置信水平下计算）。它不仅在代码覆盖率方面展示了WebExplor的探索能力，而且还展示了通过无模型测试方式可以获得的健壮性。

此外，我们还对WebExplor生成的测试用例进行了深入分析，以了解为什么WebExplor作为一种无模型算法，可以获得比其他无模型算法（即crawjax和Random）更好的性能。以Petclinic为例（如图3所示），我们发现WebExplor可以生成正确的操作序列（即，在添加所有者之前填写表单值），以实现有效的测试。通常，对于基于随机的无模型算法来说，生成这种逻辑相关的序列动作是很困难的。然而，通过利用好奇心驱动的RL，WebExplor可以捕获这种关系，并将这种“知识”编码到策略中，以创建没有导航模型的有效测试用例。

此外，与基于模型的算法（即DIG和SUBWEB）相比，我们发现WebExplor在四个主题上的表现要好得多，在其他主题上的表现也类似。我们调查了原因，发现SplitType和Retroboard中的一些页面需要复杂的输入，很难随机生成。例如，只有在使用非标准W3C格式（如mmdd）键入时间值后，才能发现SplitType中的“事务”页面。然而，WebExplor遵循W3C标准[39]，在没有人类知识的情况下无法生成此类输入。同时，我们分析了DIG和SUBWEB中的APO和MPO，发现这两种导航模型都已使用人工知识进行了微调，从而实现了非标准输入生成，以实现更高的覆盖率。详细结果和分析见【49】。在其余四个受试者中，这种非标准输入几乎不存在，WebExplor取得了更好的结果。

RQ1的答案：与基于模型的方法相比，WebExplor在大多数情况下在没有导航模型或先验知识的情况下实现了更好的代码覆盖率和健壮性。

4.3，故障检测（RQ2）

我们继续分析每个基线在排除故障方面的能力（定义见第IV-A2节）。表I显示了在分配的测试时间内发现的平均故障数的统计结果（见第IV-A4节）。由于在整个测试过程中可以多次发现一个故障，因此我们仅统计所有方法的唯一故障。总的来说，我们有以下发现。

首先，与其他基线相比，随机方法的性能相对较差，这与简单的随机探索对大型web应用程序无效的直觉是一致的。基于模型的方法可以发现比随机方法更多的故障，但表现出不稳定性。

在所有基础线中，Webexplor发现最多的故障（表I中的粗体数），大大超过了其他方法（即，由Mann-Whitney U测试计算为0.05置信度）。这不仅揭示了失败检测中的竞争性演奏，而且还揭示了WebExplor的一般性。

另一个违反直觉的发现是，在SplitType和Retroboard主题中，虽然WebExplor实现的代码覆盖率低于DIG（见表一），但它仍然检测到更多的失败（见表一）。我们分析了WebExplor和DIG生成的测试用例，比较了日志（参见[49]中的详细日志），发现WebExplor通过生成包含非法操作序列的测试用例发现了更多的服务器请求错误（例如错误代码400和500）。直观地说，与每个操作相关的代码很容易被独立执行所覆盖。然而，一些故障仅由非法操作命令触发，这表明仅仅通过提高代码覆盖率来检测故障似乎是无效的。此外，在APO和MPO中，DIG将具有特定顺序的操作序列组合为宏操作，忽略了不同的命令或仅执行部分序列可能导致潜在故障的事实。这解释了为什么WebExplor在生成有效测试用例方面表现更好。

表1平均分支覆盖率和故障检测相关基线与相应标准偏差的比较。（粗体显示的值表示15次运行的最佳平均结果。）

RQ2的答案：与其他基线相比，WebExplor在故障检测方面取得了最佳性能，同时不需要人工知识或微调导航模型，显示出其跨不同主题的潜力。

4.4，DFA指南（RQ3）

本节研究DFA如何通过高级指导提高测试效率。比较WebExplor和WebExplor（无DFA）的故障检测率和效率。图7说明了结果，其中x轴是测试时间，y轴（#Failures和#Coverage）分别是发现的故障的平均数量和代码覆盖率。为了避免统计偏差，使用15次运行对结果进行平均，粗体线和阴影区域表示平均值和标准偏差。

首先，在图7（上图）中，我们观察到WebExplor不仅可以发现比没有DFA的故障更多的故障，而且可以提高故障检测效率（蓝线上升更快）。与此同时，DFA在发现故障的数量方面取得了早期的性能提升，尤其是在dimeshift、pagekit和petclinic受试者中。所有这些优势都得益于DFA指导下的更好勘探。以petclinic主题为例，WebExplor发现的许多故障都有很长的执行跟踪，其中包含许多需要按特定顺序执行的操作。

图7：针对平均发现故障数（顶部）、代码覆盖率（底部）和测试效率（15次运行）对DFA进行评估。使用15次运行对结果进行平均，而实线和阴影分别表示平均值和标准偏差。

考虑此页面过渡跟踪为例：主页→ 所有者-列表→ 所有者信息→ 宠物清单→ 宠物信息→ 访问信息页面。只有在进入访问信息页面并提交具有无效值的表单时，才能发现许多失败。WebExplor可以通过DFA指导有效地实现这一过渡，并开始后续测试。否则，过程中的任何中断都会导致访问另一个页面，降低测试效率（如图5）。因此，这样的高层指导有效地引导了有希望的测试方向，WebExplor通过这些方向可以实现高效的web测试。

另一个发现是，DFA可以在故障发现和代码覆盖率方面实现更稳定的性能。如图7所示，使用DFA的标准偏差（阴影区域）小于不使用DFA的标准偏差（阴影区域）。这种差异在pagekit、phoenix和petclinic受试者中尤为明显。

RQ3的答案：DFA通过为有效勘探和高效率提供高水平指导，补充了好奇驱动的RL。WebExplor在故障检测率、代码覆盖率和稳定性方面实现了更好的性能。

4.5，真实世界Web应用程序评估（RQ4）

RQ4旨在评估Webexplor对现实世界Web应用程序的有效性。根据Alexa等级列表[32]，选择了前50个最受欢迎的Web应用程序进行评估。总体而言，Webexplor发现了3,466个失败。手动检查后，我们发现这些故障包括1,889个JavaScript故障，147个服务器故障（即状态代码≥500）和1,430其他其他故障（[49]中的更多详细信息）。此外，我们分析了检测到的故障的URL，发现83.71％的故障来自原始Web应用程序，而其余的则来自第三方库。这表明原始Web应用程序中确实存在大多数故障，从而导致迫切需要端到端测试，例如webExplor。

另一方面，我们发现故障可能是由客户端或服务器端造成的，包括静态资源加载错误、由于不常见操作序列导致的JavaScript错误，以及由于访问不同服务器导致的跨站点错误（详情请参阅[49]），这证明了WebExplor在检测真实web应用程序中的故障方面的有效性。此外，WebExplor没有利用任何手动调整的参数，在各种现代web应用程序中显示出很高的可扩展性。更多分析和故障截图，包括网页和控制台输出，可在我们的网站上找到[49]。

此外，还使用了一个商业SaaS平台（超过一百万行代码）作为详细的案例研究。WebExplor成功发现了12个未屏蔽的故障，这些故障由开发人员确认并修复。我们对发现的故障的一些具体案例进行如下分析。

异步呈现：以下代码段显示了发现的故障，其中灰线是新添加的修复解决方案。元素（即“kg container”）是异步渲染的，完成渲染之前是空指针。因此，一旦访问此类空指针（第3行），就会触发故障。这一发现还表明，开发人员在web应用程序中使用异步技术时应该注意。

安全缺陷：以下示例显示了导致安全缺陷的模块加载故障。具体来说，当WebExplor在浏览器中的“在线编辑器”上操作时，服务器会尝试通过遍历所有文件夹（第3行）来加载不存在的模块“brace/mode/c cpp”。

因此，如图8所示，服务器向客户端公开所有文件夹和文件夹结构，恶意攻击者可能会利用这些文件夹和结构进行攻击，并导致安全问题。“在线编辑器”很难找到，但WebExplor通过有效的探索发现了它。

图8，敏感服务器信息的暴露

除此之外，WebExplor还发现了其他一些失败。例如，密码重置API在收到无效的电子邮件输入后会引发内部异常（400个错误请求）。此外，当WebExplor执行选项卡切换行为时，会引发事件处理程序错误，这会导致不正确的数据呈现。此外，如果请求负载不包含无法处理的产品或组织ID，则搜索API会抛出一个错误（500内部服务器错误）。更多的分析和细节可以在我们的网站上找到【49】。

RQ4的答案：WebExplor以端到端的方式测试现代web应用程序，无需额外的手动操作（例如，构建导航模型）。此外，从实际应用程序中检测到的3000多个故障进一步证明了WebExplor在故障检测中的有效性。

4.6，对有效性的威胁

在测试和web交互过程中，随机性可能是一个主要威胁。我们通过对每个测试配置重复15次并平均结果来减少这种威胁。此外，我们提出的oracle可能并不完整，因此Web-Explorer可能会错过一些其他未知的故障，如UI错误或其他类型的错误。当WebExplor执行黑盒web测试时，假定服务器端代码不可用。因此，只报告客户端代码（例如JavaScript）的覆盖率，而WebExplor在代码覆盖率方面的评估可能不全面。用于训练策略的RL算法的选择可能存在偏差。我们通过选择用于web测试的标准RL算法来缓解这个问题。此外，超参数可能是一种潜在威胁。这些超参数的选择取决于领域知识，并且可能存在偏差。此外，web应用程序的选择可能会有偏差。为了解决这一问题，采用了一个研究基准和各种现实世界的web应用程序，包括活跃的商业网站，进行评估。

5，相关工作

已经提出了许多技术来自动化web测试。在下面，我们将简要讨论最相关的解决方案及其局限性，这促使我们需要一种新颖高效的web测试技术。

基于模型的测试。基于模型的技术是实现自动web测试的主要范例【15、5、38、51】。这种技术先构建模型来描述web应用程序的行为，然后从模型中派生测试用例来发现bug。例如，DIG【15】、SubWeb【5】和ATUSA【38】等方法从导航模型中提取路径，其中采用遗传算法进行路径选择和输入生成。此外，Wertgen[51]提出了一种增量两步算法，其中导航模型的生成和测试用例交织在一起。总的来说，基于模型的技术显示出快速生成测试用例的优势，因为不需要web交互。然而，导航模型可能只涵盖web应用程序的某些行为，而其他行为则无法测试。此外，建立高质量模型需要专家领域知识。这种局限性激发了对无模型测试技术的需求。据我们所知，WebExplor是第一种基于RL的技术，它可以对真实世界的应用程序执行端到端的自动化web测试，并实现与最先进技术相比的竞争性能。

测试用例生成。测试用例生成包括构建测试路径和相应的输入值【15】。给定一个导航模型，测试路径可以通过基于搜索的方法生成[5，52]，输入可以使用随机或进化算法生成[15，53]。在许多情况下，基于搜索的技术需要显式地解决路径可行性问题，从而导致测试用例候选的大量执行。基于搜索的算法还需要评估每个测试用例的适应度值，这是非常昂贵的，因为在收敛之前，需要在浏览器中生成和执行大量候选值[54]。现有的自动测试用例生成技术要么忽略路径可行性或者要求大量执行。至于输入值，在大多数情况下，随机策略[38，53]可以生成可行的输入。此外，符号执行技术（如Apollo【55】、Jalangi【56】和SymJS【57】）使用系统策略生成特定输入，以覆盖难以获取的代码。然而，生成这些特定的输入并不是WebExplor的主要关注点，所有高级输入生成技术都可以集成到WebExplor中，以进一步提高性能。最近，也有一些关于测试深度学习模型的研究[49、58、59、60]，可以用来测试强化学习模型。

基于强化学习的测试。近年来，RL也被应用于帮助软件测试。例如，Wuji[23]利用RL和多目标优化进行游戏测试，这与web应用程序有很大不同。B̉ottinger等人[61]介绍了第一个基于RL的模糊器，用于学习高回报种子突变，以测试传统软件。Retecs【62】使用RL来促进回归测试中的测试优先级和选择。此外，RL还被用于移动测试技术中【63、25、26、27】，范围从用于崩溃检测的QBE【63】到GUI测试【26、27】。最近的Q测试【25】通过利用好奇奖励（类似于WebExplor）实现了最佳的移动测试性能。WebExplor和Q-testing都是基于Q-learning构建的，然而，由于Android和Web应用程序的不同特点，这两部作品所面临的挑战是不同的。在WebExplor中，我们为web测试精心设计了状态表示和适当的奖励，这与Q测试不同。此外，我们还发现，仅使用Q学习是无效的。因此，WebExplor中提出了DFA增强探索，这也是与Q测试的一个关键区别。与RL和web域最相关的现有研究是Artemis【64】和DOM-Q-NET【65】，它们利用RL执行明确定义的基于web的任务。与完成明确的任务不同，WebExplor通过使用好奇心驱动的RL探索不同的行为来进行web测试，这在以前是没有解决过的。

6，结论

本文提出了一种新的基于RL的web自动测试方法WebExplor。WebExplor利用好奇心驱动的RL实现高效和自适应的探索。同时，DFA被提议提供高水平的指导，以进一步提高测试效率。实验表明，WebExplorer在代码覆盖率和故障检测方面都优于现有的web测试技术。未来，我们计划使用分层RL扩展WebExplor，以便更好地进行探索，并从DFA中提取业务场景，从而实现故障定位。