Fastbot：行进中的智能 Monkey
1. 背景
近年来，App 的玩法变得越来越多，功能也愈加复杂。App 的稳定性与健壮性也变得更加重要，因其带来的更好的用户体验能让 App 在激烈的竞争市场中脱颖而出。正因如此，针对 App 的稳定性与健壮性，相关的自动测试技术也成为软件工程和智能化测试的热门研究方向。
1.1 自动测试生成简介
自动测试生成（Automated Testing Generation）技术，也叫 AIG（Automated Input Generation）技术。传统的自动化方式，比如录制与回放（Record & Replay），依赖于测试人员编写测试脚本。同时，跟随着测试需求的改变，测试人员需要耗费一定的时间维护和调整相应的测试脚本。与录制回放的方式相比，将测试活动依赖的通用服务进行抽象，依靠自动的方式生成测试活动需要的操作，能较大程度减少测试脚本的编写与维护工作量。
目前，典型的 ATG 技术有：
程序分析（Code-Based Testing）； 基于模型的测试生成（Model-Based-Testing）； 组合测试（Combinatorial Testing）； 基于搜索的测试生成（Search-Based-Testing）， Facebook 的 Sapienz； 自适应随机测试（Adaptive Random Testing）；
图 1.ATG 技术简介
它们核心的逻辑聚焦在“如何生成”测试逻辑。以 MBT 为例，GUI 测试（客户端测试）过程中的某个页面，可以被定义为一个状态（State），利用该页面对应的 GUI 树，我们可以提取其中更有意义的操作，比如从 state1 通过 event3 可以到达 state3，从 state2 通过 event2 可以到达 state1。这样，测试生成的问题转化成对有向图的遍历问题。像 Monkey 之类的随机测试工具，由于缺少对于 Log 的更高层面的表述，常让开发者对其有担忧：
（1）由 Monkey 生成的测试序列不容易以文档的形式描述用例；
（2）比较难复现 Bug，缺少复现的详细步骤。
1.2 自动化测试工具
针对 App 的 ATG 技术主要包括两大类。
其一，是基于代码层面的白盒自动化测试工具。在这种情况下，我们通常需要获取 App 源码，对其分析后产生控制流图，并在此基础上通过测试生成手段产生测试用例。这种静态的白盒测试的方法虽然更加精确，但限制较多，对于无法获取源码的 App 无法有效的测试。另外，为达到较高的代码覆盖率，会不可避免的产生过多的测试用例。
其二，我们也可以基于 App 中的 GUI 信息进行黑盒测试。这种测试类型无需获取 App 源码，我们只需要在测试过程中监听手机页面的 UI 信息，完成动作注入，即可实现持续的交互型测试。本文中介绍到的 Fastbot 工具就是应用了这种方法。
当下流行的其他黑盒自动化测试工具包括：Facebook 研发的 Sapienz，它使用遗传算法和基于搜索的方式来生成测试用例；佐治亚理工大学开发的 Dynodroid，它把 App 看作一系列可执行的动作，并依次产生测试序列；以及上文提到的 Android 自带的随机测试工具 Monkey 等。此外，北大研发的 Droidbot 和 Humanoid 工具也使用了基于模型的 GUI 测试，其中 Humanoid 以用户行为为基准进行模仿，而 Droidbot 则是将页面和动作抽象为图模型，通过传统的 DFS 和 BFS 算法进行图的遍历，以达到高覆盖率。
然而，在我们的测试过程中发现，传统的图遍历算法在基于模型的 GUI 测试中效果不佳。原因在于：
图中存在大量的环路，使用基于 DFS 的算法极易陷入局部循环当中，只覆盖有限的页面而无法退出； 实际被测 App 基本都是动态且实时更新的，某些页面（如 Feed 页、搜索页等）存在严重的退出后无法重新到达的问题，简单的后退操作也无法保证能回到上一步的页面，下拉刷新等动作没有对应的后退操作等。
此外，如果将 App 模型存储于客户端，由于手机设备内存及性能限制，模型大小将严重受限，测试无法长时间进行。而且，由于大量的 AB 实验利用了设备的机型、OS 版本等数据，每台设备上能够遍历到的 State 数量也不尽相同。
因此，一方面，我们期望利用更丰富的机型设备，借助手机农场（device farm）来共同构建 App 模型，以指导未来的测试任务；另外一方面，我们优化了传统的图搜索算法，转用启发式搜索，以期在更短时间内获得更高的测试覆盖率。
本文将重点介绍字节跳动自研的智能化测试系统：Fastbot，它是一套基于模型（MBT）的智能化 GUI 测试服务。我们将测试任务转换为对 App 进行遍历搜索和构建有向有环图模型的搜索任务。同时，分拆了客户端和服务端，实现了海量设备上的多机协同执行 GUI 测试任务。在客户端做 GUI 信息监听上报和动作注入，在服务端做模型搭建和动作决策，并基于 UCB 公式设计了多套符合有向有环图遍历的算法，避免了局部死循环的情况，极大的提高了测试覆盖能力和测试效率。
2. Fastbot 的设计原理
2.1 Fastbot 的工作流程
如上文中提到的，基于模型的 GUI 测试会受到手机端的内存大小和计算能力的限制。Fastbot 整合了工作流程，将消耗大量内存与计算资源的部分部署到云端，在客户端只保留 UI 信息监听和动作注入的功能。图 2 为 Fastbot 系统的工作流程图，图中展示了客户端与服务端分离的工作方式。
图 2. Fastbot 工作流程图
字节的实际测试场景中，往往需要同时对多个打包好的 App 进行测试。因此，Fastbot 系统还支持实际业务场景的多任务并行，以对不同 App 或 App 的不同版本进行测试任务。以每个任务为单位，服务端会有唯一的任务模型与之对应。同时，我们支持为任务配置自定义事件，以实现账号登录，特殊场景访问等功能。服务端的每个任务对应多个客户端设备，每个设备上，我们会配置好一套相应的客户端代码，实现客户端代理的功能。客户端代理的主要功能包括：监控页面 GUI 信息发送给服务端，以及接收服务端发送的动作并在设备上实现。
与之对应的，在服务端也有服务端代理 Agent。每个服务端 Agent 为一台设备负责，接收其页面信息，对其进行封装，产生 State 节点，服务端 Agent 会根据当前的 State 信息，根据分配好的指定算法，与任务模型交互做出动作决策，并将决策出的动作发送回给客户端 Agent。
在此过程中，我们将 State 和 Action 更新到了服务端的任务模型中，并记录下了是否发生崩溃，覆盖率信息，通往当前节点的有效路径等多种信息，用以实现数据分析，路径回放和测试生成。
2.2 Fastbot 模型介绍
如前文所述，我们将页面的 GUI 信息抽象成模型中的 State，将执行的动作抽象成模型中的 Action，通过 State 作为图的节点，Action 作为图的边，连接形成有向有环图模型。图 3 展示了有向有环图的局部示例，其中箭头虚线代表着执行动作，连接起了各个节点。
图 3. 有向有环图的局部示例
多机协同时，模型如图 4 所示，其中每种颜色代表一个 Agent 的行动轨迹。
图 4. 有向有环图模型的全局示例
如何将页面的 GUI 信息抽象成模型中的 State 也是我们面临的一大难题。我们需要保证粒度不要太细，以至于页面稍有变化（如极其小幅的滑动，或同类型按键顺序上的变化）就被定义为全新的 State，导致 State 数量爆炸，内存占用过高。同时，我们又不能做过于宽泛的抽象，至少要保障决策出的动作可以找到对应的执行控件。通过长期的观察测试，我们得到的效果最好的抽象方式为通过页面的 Activity 名，控件上可执行的动作类型，以及控件树一维化后的排列分布进行 State 类的构建。
3. Fastbot AI-Core 介绍
对于静态 Native App 上的测试，如计算器或日历 App，其状态有限，动作的结果相对统一，很少出现统一动作导向不同结果的情况，这种情况下传统的 DFS、BFS 算法仍有不错的遍历效率。
然而，在动态的有向有环图模型上，这些传统遍历方法就有很大的局限性了。动态 App 中，相同的动作很可能导向不同的页面，例如进入今日头条 App 后点击推荐 tab，每次拿到的页面都是与之前不同的推荐内容；由于类似的原因，简单的后退操作也无法保证能回到上一步的页面。更严重的是局部循环问题，由于环路的存在，我们可能重新回到某个全部动作都已访问的 State 节点，若不对已访问的动作进行再次访问，则会丢失路径中未访问过的动作，过早的结束遍历测试。如果使用类似贪心算法的方案，在某页面下贪心的选取某个价值较高的动作，不断尝试遍历该动作下的所有可达路径，那我们可能过多的陷入一条局部最优的路径当中，若该高优动作导向了某个不再会出现的 Feed 页面，或多个局部最优动作形成循环链路，则我们会陷入局部循环而无法退出。实际上当前页面判断价值较低的动作下可能隐藏着更多的可覆盖的状态点，需要我们探索开发。
为了实现更有效率的遍历探索，我们在 Fastbot AI-core 中使用了多种启发式遍历算法，下面的部分将对其中三种有代表性的算法进行介绍。
3.1 单步或 N 步 UCB 算法
我们首先介绍基于 UCB（Upper Confidence Bound）公式的探索遍历算法，其中包括单步预测的 UCB 算法，以及 N 步预测的 UCB 算法。该算法的主要作用在于对平衡了探索和利用，我们希望尽可能多的去访问相对高优且访问次数相对较少的节点，这样以来，我们既利用了已访问节点提供的优先级信息，也对较少访问的节点进行了尝试。
Fastbot 模型中为 State 优先级赋予了比较复杂的计算公式。我们首先对每个动作，根据其动作类型定义了基础优先级，然后根据其是否已访问以及是否饱和附加上访问优先级，两者加和构成动作的优先级。在此基础上，State 的优先级来自于该页面下所有可执行动作的优先级的累加。
公式 1 即为单步的 UCB 公式，其中左项为优先级项，右项为访问次数项，两者相加产生结合后的 UCB 值，作为动作的选取标准。图 5 为公式 1 做了图例解释，在当前节点 Sc 下，对于已访问过的 Action：A1-A3，我们知道其目标节点，采用公式 1 计算得到 Action 的 UCB 值，对于其他未访问过的 Action，我们不知道目标节点是什么，则取 Action 自身的 priority 作为 UCB 结果，通常 Action 自身的 priority 高于多次访问后的 UCB 值，所以我们仍会优先尝试未访问过的动作。
图 5. 单步 UCB 算法示例图
公式 1
单步 UCB 算法耗时少，且其引入访问次数平衡项后，很好的阻止了局部循环的发生，使动作决策更加分散化。此算法的一个缺点是其只考虑了当前一步以内的 UCB 最优动作，若将 N 步以内的可执行动作都加入考虑范围，选择结果可能有所不同。为此，我们同时介绍 N 步的 UCB 算法，该算法会遍历当前动作及该动作以后的 N-1 步以内所有可执行的动作，将所有动作的优先级乘上衰减系数并累加，最终的结果最为当前动作的 UCB 值。N 步 UCB 算法的公式由公式 2 所示：
公式 2
尽管 N 步 UCB 算法考虑了更多的步骤，但在时间复杂度上也做出了牺牲。由于需要对未来 N 步的动作做出预测，我们需要额外的 N 的指数级别的耗时。因此，N 的值最好渐进增长。
3.2 MTree 算法
然而，不论是单步 UCB 算法或是 N 步 UCB 算法，都只是利用了一步或 N 步以内的信息，而非利用到整个模型上的信息。由于环路的存在，模型上的反向传播无法顺利进行。我们希望能够实现全局的方向传播，将新访问到的页面信息一直传递到起始节点。当覆盖到新的 Activity 时，我们希望路径上的每个节点都得到更新。因此，我们考虑将有向有环图模型裁剪为树状结构，从而避免环路带来的干扰。树的节点代表着模型中的 State，在节点中，我们保存上一步的 Action，记录上一步的 State 作为父节点，记录下一步可以到达的 State 为子节点。使用 MTree 算法后各子节点的优先级由公式 3 给出：
公式 3
3.3 NStepQ 算法
由于 feed 页等动态变化的页面存在，模型会不断增大，难以收敛。我们希望能够挖掘能够覆盖新 Activity 的 State 和 Action 的特征，对未访问的动作也能做出较好的推测。我们使用强化学习的方法，设计了 N 步 Q-Learning 算法和基于页面变化程度的 reward function，为页面下每个 Action 计算出相应的 Q 值，基于 Q 值选取最优动作。
4.Fastbot 的使用效果
为了验证工具的效果，我们将 Fastbot 与其他几款同类测试工具做了对比实验，其中包括 Android 自带的原生 Monkey，北大开发的 Droidbot 和模仿人类行为的 Humanoid。实验中涉及包括今日头条、抖音等多个 App，1 小时/3 小时，单台设备/多台设备等多个维度，Fastbot 的表现均大幅领先其他工具。表 1 中展示了各工具在单台设备运行今日头条 App 时的对比，可以看到，Fastbot 在单台设备上已表现出更好的性能，在相同时间内的安卓 Activity 覆盖率和代码覆盖率均好于其他工具。
此外，随着设备数的增加，Fastbot 的多机协同能力将带来更可观的性能优势。表 2 中展示了 3 台设备并行时，各工具的代码覆盖率增长情况，可以看到 3 台设备并行时，Fastbot 代码覆盖率由单机时的 19%增长至 35%，涨幅达到 84%；相比之下 Droidbot 和 Humanoid 在 3 台并行时的提升只有 20.41%和 24.97%，而 Monkey 也有 45.79%的代码覆盖率提升。
借助字节跳动公司强大的云计算能力，我们在一次任务中最多可以启动 500 台设备共同遍历，同时保障服务端不引发 OOM 问题。整体而言，可以看到，随着设备数的增加，单位时间的覆盖能力也不断提升。
此外，AI-Core 不同的算法也会带来不同的遍历效果。图 6 中展示了 Fastbot 在 20 台设备并行时的覆盖率变化趋势对比；同时，我们引入 Action 有效率的概念，以不重复的 Action 除以执行 Action 总数来做度量，进一步观察算法的效果
黄线展示的是深度优先遍历算法，可以看到经过短暂的覆盖率提升后，DFS 曲线基本停止了增长。从 Action 有效率数据中观察到，传统的 DFS 算法很快的陷入局部循环当中，不再触发新的动作。
紫线展示了随机遍历算法，由于不会陷入环路，该算法效果要好于 DFS。但由于其完全随机，不考虑动作价值的特点，覆盖能力依然远远落后于 Fastbot AI-core 中的算法。
之后我们来关注 Fastbot-AI-core 中的四种算法。蓝线和黑线分别展示了有向有环图上的单步 UCB 算法和 N 步 UCB 算法的效果。可以看到单步 UCB 有着很快的增长速度，且 Action 有效率高，但后劲较弱。相比之下 N 步 UCB 由于更高的单步耗时，前期覆盖率增长在 AI-core 算法中最为缓慢，但后期在单步 UCB 覆盖率趋于饱和时，N 步 UCB 借助其发现 N 步以内有价值的节点的能力，能够达到更高的上限。
绿线展示了 Q-Learning 算法，其动作有效率为四种算法中最低，但覆盖率表现强于单步和多步 UCB 算法，因其捕捉容易触发新 activity 的 State-Action 的特征，并大量执行。
红线展示了 MTree 算法，通过将有向有环图剪枝成树状结构，实现全局反向更新，该算法实现了最好的覆盖效果，且拥有最高的 Action 有效率。
图 6. 算法覆盖率对比图
5. 总结
目前，Fastbot 已广泛应用于字节客户端类产品的稳定性测试与兼容性测试。每日启动任务数超过 300 次，每日平均发现 5000 个以上的崩溃，并有超过 100 个新捕获的崩溃。借助 Fastbot 的能力，我们在发版前就可以修复大部分的 crash，确保线上用户的使用体验。同时，Fastbot 在整个 DevOps 流程扮演重要的基础服务角色。我们相信，越来越多的智能化测试工具，将极大的改善国内传统测试行业。
6. 加入我们
字节跳动 Quality Lab，是致力于面向互联网行业的工程效能理论研究与技术预研的新团队，我们的使命是成为全球顶尖的智能工具团队。我们致力于将前沿的 AI 技术应用到质量与工程效能领域。面向行业提供智能化测试工具，例如 Fastbot、基于强学的社交测试等测试服务。在成为全球顶尖的智能工具团队道路上，希冀为质量领域带来更多智能化手段。
在这里，你可以利用 NLP 技术玩转智能客服，实现机器与人的对话，提升运营工作效率；也可以用机器视觉与强学，创造具有超强能力的测试机器人，并在数以千计的设备上验证你的算法；还可以实践各种教科书上的测试理论，去帮助业务提升测试效率，组合测试、程序分析，还有精准测试，都等着你来探索；更可以与国内外顶尖机构进行交流合作，与世界各地的学者一起探索更多软件工程领域的可能性。欢迎各位有识之士加入我们。简历投递邮箱： tech@bytedance.com ；邮件标题： 姓名 - 工作年限 - Quality Lab 。
更多分享
欢迎关注「 字节跳动技术团队 」
简历投递联系邮箱「 tech@bytedance.com 」