【NCTS峰会回顾】李元春：强化学习在自动测试中的应用

2019年10月26日，由Testin主办的第二届NCTS中国云测试行业峰会在京召开，此次峰会以“AI+未来”为主题，汇聚来自国内外测试领域的知名专家学者、领先企业决策者、高层技术管理者、媒体从业者等，共同探讨高端云测试技术，帮助测试从业者了解最前沿行业趋势，及最新的行业实践。

会上，北京大学计算机系博士李元春做《强化学习在自动测试中的应用》主题演讲。李元春介绍了关于GUI测试相关的研究并指出，“将强化学习应用到GUI测试的难点主要是状态的表示和奖励函数的设计，即如何将交互界面中的图像、文本等多模态特征进行有效的编码，以及如何将测试的目标转化成对测试输入的奖励。”

以下为李元春演讲实录：

各位同行大家好！很荣幸在这里分享我做的关于GUI测试相关的工作，我叫李元春。我研究的方向是移动应用的隐私和安全，做隐私安全相关分析时，我经常用到静态分析或者动态分析的技术，在动态分析中，如何对应用进行动态的测试，使得应用能够覆盖足够多的代码，触发足够多的隐私安全的敏感行为，直接决定了隐私安全分析结果的完整性。因此，接触到GUI测试的研究方向，也做了微小的探索性工作。我今天和大家分享的内容更多的是偏技术落地。

首先介绍一下GUI测试的背景，基于软件的图形界面，生成交互动作序列作为测试的用例。主要的应用场景是两种，一种是GUI的遍历测试，即如何对软件的功能进行充分的探索，第二是功能测试，比如对一个应用的登陆功能进行测试，生成的测试用例可能就是输入账户名，输入密码，点击登陆。

根据这两个场景，我分别使用深度学习和强化学习技术进行了探索。

首先是基于深度学习的GUI遍历测试。自动的GUI遍历测试主要有两种主流的策略，一种是随机的策略，比如安卓的官方工具Monkey就是随机的策略，这些工具在测试应用的时候是像猴子一样看不懂应用具体的GUI和代码，生成完全与代码内容无关的测试用例。第二种是基于模型的策略，对代码进行静态分析或动态分析，建立起一个模型，用这个模型去指导输入。比如右边的图有一些学术论文中的工具，通过分析代码的执行路径，用符号执行求解路径到达方式，这样能生成一个更加有针对性的测试用例。这些方法的共同点，都是在测试的易用性和测试效率之间做一个权衡。比如Monkey就是追求易用性而牺牲效率，对任何应用都可以快速的测试，但是缺点也特别明显，随机测试用例很难去解释、拓展和重现。基于模型的策略，通过分析代码，生成用例，主要缺点是需要对代码进行分析。现在很多应用的代码都特别复杂，有很多种语言混合，用了各种高级语言的特性，使得静态分析难度很大。还有，黑盒测试时拿不到源代码，或者代码进行了加密，这种情况下很难用基于模型的静态分析的方法来做。现在主流的方法是在这两者之间的平衡，同样是基于模型生成测试用例，但这个模型不是对代码进行分析建模，而是对应用执行过程中界面转换关系进行建模，仅仅作为记忆的功能，在之后的生成测试用例的时候避免无效的输入。

这就是刚才所说的第三种方法，常用的一种界面转换图的模型，比如在这个模型里面，每个节点都是界面的状态，每一条边都是状态之间的转换关系，构造出这样模型之后，可以对应用进行测试。右面的图是我之前做的一个工具DroidBot，可以针对任意应用，在黑盒情况下把界面转换图构造出来。基于界面转换图，任何人可以编写遍历测试的策略，例如可以设计深度优先，宽度优先，随机探测，或者启发式规则等等。

然而，使用这些简单的规则探索应用功能的效率往往不高，算法往往无法快速地到达应用中重要的界面和功能。我们想到一个很奇妙的点，当进行人工测试的时候，不管是真实的测试人员，还是用户，他们虽然对代码没有任何理解，他们往往可以很高效的对应用界面进行探索。我们思考了一下其中的原因，主要是两点，第一点，不同应用的GUI交互模式是存在共性的，比如说不管什么应用，都有一些搜索功能，很多应用都是一个向下滑的瀑布式的信息流的结构，就算是功能没有相似性，交互模式也是有相似性的。第二个原因，很多人虽然之前没有测试经验，但是使用过很多应用，潜意识中学习到了各种各样的交互模式。那么，我们想，能不能用机器学习的方法把人使用应用的交互模式学出来，用这样的交互模式形成机器学习模型，用这个模型去指导自动测试数的生成。当然这里有很多挑战，例如如何对软件GUI的状态和动作进行机器表示；如何设计模型把GUI的这些交互模式进行高效的捕捉等等。

基于这个想法，我们做了一个工作，叫Humanoid，主要架构如下，首先在离线学习阶段，假设收集了很多真实用户的交互数据，这些交互数据不是来自于被测应用，可以来自于任何应用。在离线的用户交互记录数据里面进行学习，把学出来的东西捕捉在交互模型里面，然后用这个模型不断的去指导测试UI交互数据的生成。

这是我们在Humanoid如何解决交互界面状态和动作表示的方法，把每一个UI状态表示为一个UI的结构图，我们忽略了UI里面的图像和文本信息，仅仅是每一个UI上面文本的区域是哪些，图片的区域是哪些。这样做的目的，可以在有限的数据里面收集到更多更简化的UI特征，在机器学习的时候更容易被泛化。在表示交互动作的时候，我们是由两个部分组成，第一是交互动作的类型，包括点击，滑动、输入等等。第二个元素是交互动作的位置，这个交互动作发生在界面上的位置，也是直接用X、Y坐标来表示，但是往往需要把孤立用户点击的点，转化成一个以这个点为核心的分布图，在学习的时候，每一个数据点都不是孤立的而是分布的，更容易进行学习。

有了上面的两种表示之后，就明确了模型输入和输出之间的映射关系，当前界面情境context，包含了当面界面S，还有最近若干次交互。输出是两个概率分布，包括交互位置概率分布和交互动作类型概率分布，基于这两个概率分布可以计算出每个交互动作的概率。

这是我们使用的深度学习模型用来捕捉界面情境和界面交互动作之间的关系，大家可以看到用了很多CNN捕捉界面上的图像信息。我们使用了4个交互序列，除了当前的交互界面状态之外，还使用了之前的三次交互历史，我们把这四个交互动作输入一个LSTM，提取出界面交互特征之后，把这个特征重新映射到原来交互输入上，要生成的交互动作位置的概率分布。

这是我们模型训练之后真实使用的伪代码，测试的时候我们随机的选择进行探索，或者对模型进行利用，如果进行探索，使用刚才的模型生成交互动作，然后执行交互动作。如果是进行利用的话，根据界面转换图导航回之前的某一个界面。

Humanoid实验评估，我们使用的是Rico dataset，涉及很多用户使用应用时的交互记录。我们用这些数据给UI转换模型进行训练。我们与6个代表性工具进行对比，一个是Monkey，还有PUMA等。

学习交互模式的效果，这个模型能够把真实用户交互动作预测到更高的概率，我们的模型能够把真实用户使用的交互动作排到前面，说明我们的模型是有效学到了交互信息。把这个模型应用到真实测试中，虽然这些测试工具之间的覆盖率差异不是很大，但是Humanoid能达到最高的代码行覆盖率，对于市场流行应用也能达到比较高的界面覆盖率。这是Humanoid和其他工具进行覆盖率提升速度的评测结果，可以看到红色的线是Humanoid的结果，它是能够比较快的达到较高的覆盖率，而且这个曲线还有继续上涨的趋势。

第二部分，基于强化学习进行UI功能测试。先介绍UI功能测试的背景，我们的目的是生成一系列UI的交互动作，对软件的特定功能进行验证，比如刚才举的登陆的例子，测试用例第一行是open App，第二行是输入一个电子邮件地址，下面一个代码是在密码框里输入密码，最后点击登陆按钮。人工编写的测试用例是耗时耗力的，人工要手工进行测试修复，这是有很大效率问题。右面展示了主流工具，人工测试的样本，比如这个Sikuli工具，已经把测试用例编写变得很简单了，但是对于没有测试经验的，想写这样的代码还是比较复杂的。我们想追求的目标是，给定测试用例的文本描述，基于这个文本描述自动生成测试的脚本。比如对于Lyft/Uber网站，一个测试用例描述可能是“估算从某一个位置到另外一个位置的打车费用”，我们希望通过理解自然语言，以及理解软件的交互界面，生成右下角这个测试脚本。在强化学习问题里面有一个测试执行环境，这个测试执行环境包括Web浏览器和Reward模型，还有一个强化学习的agent，与测试执行环境进行交付，最后得到最终的测试脚本。

强化学习里面很重要的一个就是强化学习环境environment，强化学习环境给定执行任务的初始状态，告诉模型agent当前状态下可以执行哪些动作，当agent在当前状态中执行一个动作，返回该动作的奖励reward和新的状态。将强化学习应用到GUI测试的难点主要是状态的表示和奖励函数的设计，即如何将交互界面中的图像、文本等多模态特征进行有效的编码，以及如何将测试的目标转化成对测试输入的奖励。在测试中，agent观察到的状态就是当前界面UI结构，可执行的动作就是当前界面中所有可行交互输入的集合，测试环境需要允许agent执行一个动作，返回对于该动作的奖励。设计强化学习环境的奖励机制（reward function）的时候，设计目标是给正确的动作序列赋予更高的Reward，这样强化学习才可以找到正确的测试用例。我们这里的观察是，如果一个交互动作序列是正确的测试用例，一般满足以下三个指标：一个是动作应该是和任务参数匹配的。比如我刚才说的A到B，两点的打车费用，AB就是这个任务的参数，我们肯定有两个动作跟这两个参数是相匹配的。第二是UI的文本和描述的句子是重合的。第三是动作序列需要符合真实用户的交互习惯，比如生成测试用例的时候，不能说在页面底部点一下，中间点一下，跳来跳去的，这样很有可能是不正确的，我们需要加一些约束，使得测试的时候agent可以对UI进行正确的交互。

现在主流的用强化学习算法之一是Q network，用深度神经网络估计一个Q函数，Q函数以当前状态s和选取的动作a为参数，返回当前状态s下执行动作a的价值。在我们的模型中，把状态s和交互动作a，分别提取图像信息和文本信息，并进行交叉融合，作为Q network的输入，，最终去估算Q值。

这是强化学习算法最终生成的样例，从A到B打车费用的测试用例，可以生成三个脚本，每个脚本都有一些最终的Reward分值。

我们对基于强化学习的测试输入生成方法进行了评估，选取了十大类网站，一共73个网站，在这些网站上定义了41个测试描述，比如“在波士顿预订一个下午8点四人的桌子”就是一个测试用例描述，把这些作为测试用例，然后就得到了172个测试用例描述和网站的组合，我们的目标是对于每一个组合生成一个测试脚本。最后我们评估的时候，让我们的强化学习算法针对每一个测试用例描述和网站跑一小时，得到最高的交互训练，然后进行人工评估。

这是我们最后评估的结果，top 1的准确率是65.7%，top 5的准确率是76.6%，我们与常见的搜索算法进行了比较，能够看到强化学习能达到比较高的优势。