原文：Guided bug crush: Assist manual gui testing of android apps via hint moves

TL; DR

针对安卓 APP 普通的人工测试覆盖率低，重复性高，效率低。

作者推出工具 NaviDroid 辅助测试人员进行探索。工具首先构建 STG (State Transition Graph)，然后在 STG 上运行动态规划算法规划路径以最少步数实现图覆盖，最后借助悬浮窗提示测试人员对 APP 进行探索。

与基线自动化测试工具进行比较，NaviDroid 达到了更高 activity 和 STG 覆盖率。在现实 APP 上开展人工测试，比较有无 NaviDroid 辅助的测试效果，发现 NaviDroid 辅助下的人工测试覆盖率更高，找到的 bug 更多，消耗时间更少。

工作的主要贡献在于：

基于视觉的人工测试辅助工具 NaviDroid，减少被略过的功能和重复探索
结合了动态分析、静态分析和状态合并的 STG 构建方法
基于动态规划的 STG 探索路径规划方法
在现实 APP 上开展的有效性检验

动机

作者进行了一个前期的 empirical study，招募了 10 名测试人员对 85 个随机选择的开源 APP 进行测试并记录测试过程，发现：

人工测试覆盖率相对较低，但测试人员对自己的覆盖率盲目自信
人工测试存在大量重复操作，测试人员在测试时会犹豫下一步测试操作

低覆盖率和犹豫现象体现了人工测试过程中指引的必要性。重复操作现象启发作者设计一个状态转换图来记录访问过的状态并减少重复。

方法

STG 提取

定义

STGaction 是 STG 的增强版本，图节点为 state，边为触发 state 转换的 Action

笔记不加区分地使用 STG 代表 STGaction

本工作认为每个不同的 UI 页面是一个 state，并使用 UI 层级树来表示一个 state，非叶子节点是一个 layout，叶子节点是一个 UI 组件。一个 activity 可能包含多个 state 。

本工作使用接收 action 的 GUI 组件 ID 表示一个 action

静态方法

构建 AST，寻找 intent() 方法，主要有两种情形：

组件 onClick 时直接调用 intent() 方法
组件 onClick 时通过其他方法间接调用 intent() 方法

动态方法

使用工具自动化探索页面，每个 state 关联到一个 XML UI 层级布局文件，每个 action 关联到一个触发 state 转换的 UI 组件。

一些动态渲染的组件可能无法获取 ID，使用它们的 text 属性，或坐标来代表。

上下文敏感的 state 合并

合并具有相同运行时 UI XML 层级文件的 state
合并具有相似的前一和后一 state 的 state

动态规划算法

在 STG 上通过动态规划算法规划出一条覆盖所有 state，经过尽量少重复 state 的路径。

实际上求解的是经过所有 state 的尽量短的路径。这个定义跟目标更一致，因为我们希望完成遍历整张图所用的时间最短，也就是步数最少

直接贴原文定义

形式化定义

原文这里写的 DP 的定义怪怪的，我理解是

$DP_{jV}$ 是从初始节点出发，只经过状态集 $V$ 到达状态 $j$ 的最短路径

动态规划算法

悬浮窗操作指引

编译并运行 APP，实时检测当前所处 state，根据规划好的路径使用悬浮窗提示用户下一步

主要包含点击、长按、返回三种操作

实验

覆盖率测试

作者测试了 NaviDroid 的 activity 和 state 覆盖率并与baseline（1个静态方法，3个自动化方法）比较。activity 的 ground truth 从 AndroidManifest.xml 获取，state 的 ground truth 由两名经验丰富的开发人员标注。

作者同样测试了不同路径规划策略（NaviDroid, DFS, BFS, Random）的效果。

实验结果

讨论

基线方法表现不佳，因为它们都采取了随机探索的策略。

NaviDroid 覆盖率收敛快，在自动化测试方法中更快达到最佳覆盖率。

基线路径规划策略表现不佳，因为它们在STG上更容易掉进环。

NaviDroid 未能覆盖一些小组件 activity，这些 activity 的启动往往需要更多的操作，并且获取小组件的坐标通常更困难。

一些导航条或菜单的 item ID 为数字而非有意义的 ID，NaviDroid 无法准确地获取这些组件的 ID

有效性测试

作者招募了 32 名测试人员并分成了实验组和对照组（有/无 NaviDroid 辅助），在 20 个 APP 上开展测试工作，在不超过 10 分钟的时间内尽可能多地探索所有 UI，找到尽可能多 bug。Bug 的 Ground Truth 由一名资深软件测试人员提供。Bug 仅包括 UI 显示 bug。

有效性测试结果

讨论

统计检测方法显示实验组的测试覆盖率、用时和找到的 bug 数量显著高于控制组，减少了重复和犹豫的时间。

有两个因素提升了覆盖率：

特殊的操作，例如长按
一些可以点击的组件设计得不好，容易让测试人员误以为它无法点击

讨论

NaviDroid 得到了参与测试人员的正面反馈

只要能获得 STG，NaviDroid 可以很容易泛化到其他平台，例如 iOS 和 web

NaviDroid 可能对终端用户也有帮助，例如提示用户完成复杂的系列操作

NaviDroid 仍存在一些限制：

STG 不完整。不同的开发者具有不同的码风，有些开发者的码风较差，会影响 NaviDroid 的准确度
交互方式和 UI 类型的限制。
- NaviDroid 暂时只考虑了点击事件。滚动，文本输入，以及在一个 state 上进行系列复杂操作来进行 state 转换未被纳入考虑。
- NaviDroid 对动画的支持不佳。

思考

关于视觉提示工具

私以为是本文最大的亮点。作者精准找到了人工测试的困境——人毕竟不是机器，不可能把自己做过的所有事情记的一清二楚，也会想当然，那么机器就可以提示测试人员避免走重复的路，以及下一步要做啥。

而且通过视觉来提示操作的思路真的很有意思。也正如作者提到的，APP 越来越复杂，功能越来越多，层级越来越深，终端用户或许也能从这个工具中受益。

~~有框你不打？~~

关于状态转换图和状态的定义

进一步地，借助 *TG 来组织操作路径和状态转换信息十分自然。在安卓 APP 中，有明确依据且统一定义的、粒度最细的 *TG 当属 ATG，因为 activity 信息可以直接从 AndroidManifest.xml 中提取出来，activity 之间的拓扑信息往往也可以通过 intent 来得到。但 ATG 的粒度显然是不够细的，因而具有更细粒度的 *TG 的定义在不同工作中百花齐放。

私以为状态的定义通常有两类方法，一类是通过图形界面来区分状态，另一类是本文所使用的软件工程方法（本文通过获取 XML 布局文件来区分状态）。

从图形界面入手更符合人类直觉，也不依赖平台和代码。缺点是需要人类认知的先验知识，自然也会有想当然的问题。而且现在 APP 的图形界面越来越复杂，特别是在游戏场景下，从图形界面入手非常具有挑战性。

CV 呢，快救一下啊 CV

从软件工程方法入手的优点是不重不漏，写的是啥就是啥。缺点是难以 handle 不同的码风（比如本文提到的），对特定版本/平台有依赖，在黑盒场景下可靠性也会降低。

二者是刚好相反的，虽然现在大模型出来以后大家都在转向 CV，但是最终也离不开软件代码本身作为 ground truth。

所以说这两个东西结合一下肯定很有搞头。

话又说回来，本文主要考虑的是点覆盖率，那边覆盖率怎么说？

啊？DP？

这篇工作的作者列表里绝对有搞过 OI 的。

跟旅行商问题挺像的。半旅行商问题？

引入动态规划和二进制状态压缩算法来处理 STG 上的信息确实很有意思。

但是状压的复杂度非常高，如果状态数量是 $n$ ，那本文的 DP 算法复杂度至少是 $O(2^n)$ 的。状态数量增加时算法用时会指数级增长，很难面对越来越复杂的应用，游戏这类就更不要说了。

或许可以尝试一下进一步对状态进行聚类分组，分别运行算法，或是引入一些启发式算法来做