基于深度强化学习的UI遍历

1.

2.

3.

4. O1 O2 O3 O4 项目背景解决方案技术实现未来工作

5. 项目背景

6. Android UI遍历测试 Android SDK中的Monkey长时间频繁快速的对 app界面进行各种操作，从而检测app的稳定性，辅助手工测试人员发现不易发现的问题。基于Monkey的思路，逐渐形成了一种自动化测试方法称为UI遍历测试。 > adb install adapter > adb install testApk UI遍历测试通过不断与app UI界面做交互，以期在有限的时间内获取更高的代码覆盖率、 adapter >_ 找出更多的bug。 Test APK

7. 传统遍历测试方法 Test Script Test Execution Test Automation 人工测试人力成本、时间成本高自动化脚本测试通用性差，脚本维护成本比较大基于Monkey的随机性测试测试效果差，大量无效的输入遍历测试痛点：随着app功能越来越复杂，耗费大量人力和时间成本，而且效果并不好

8. 基于模型的测试基于模型的测试(model-based testing,MBT)技术能够将测试活动进行抽象成模型，依靠不同的算法自动 Test Requirement Selection Modelling 生成测试用例，这能大大减少测试脚本的编写与维护工作量。 Test Generaton 模型构建（Modeling）测试需求选择（Test Requirements Selection）测试用例生成(Test Generation) Test Concretization 测试具体化(Test Concretization) 执行测试(Test Execution) Test Execution

9. MBT的优点和难点难点优点  自动生成测试用例  通用的模型不容易设计  减少大部分冗余输入  状态空间爆炸很难解决  覆盖度更高  通用性高，维护成本低  黑盒测试

10. 解决方案

11. 深度强化学习自AlphaGO在围棋上取得的成功，深度强化学习算法得到各领域的关注，特别是在环境规则比较清楚的问题上，深度强化学习算法能够取得非常好的效果。

12. 解决思路通用模型有向图模型马尔可夫决策过程深度强化学习状态空间爆炸神经网络

13. QiAPE is All You Need QiAPE(奇猿)是基于模型的测试，在构建模型的基础上应用深度强化学习算法，对APP进行深度的遍历测试，同时监控后台信息，生成测试报告。基于有向图模型算法：DQN、PPO、UCT、多智能体UCT

14. 我们的优势  抽象的图模型大大减少了状态空间数量  防止了Feed 页等无限动态刷新的页面  更智能的强化学习算法  多进程分布式架构  所需环境依赖少  支持各种Android版本，不同分辨率设备

15. 云设备平台依托于360开测平台，有300多台机型可供使用，满足用户对测试手机数量和机型的需求上线极库云平台

16. 可配置化脚本  自动登录功能  过滤不需要遍历的控件  屏蔽自动升级  屏蔽跳出app

17. 技术实现

18. State构建 UI页面其实是一种树状结构的数据，其节点是每一个控件。每个控件一般包含‘resource-id’、‘scrollable’、 ‘clickable’、‘bounds’等信息。通过提取这些信息将页面抽象构建成一个state。

19. 有向图模型构建将已探索的界面建模为有向图，用于记忆已探索的状态节点：UI界面 state7 边：动作事件（click、scroll、back...） state1 event 1 state2 event 2 state3 event 3 event 7 event 8 event 11 event 6 state9 state4 state6 event 4 event 5 event 9 state5 event 10 state8

20. 工作流程架构服务端 data 移动端 socket adapter viewtree image logcat info ... app adb 动作事件数据处理 viewtree转换图输入数据处理有向图模型强化学习算法框架 … … …

21. DQN DNN：神经网络计算 Q 值 Experience Replay（经历回放）：记忆库 Policy 状态S t 每一个action 的Q值 Q(S t ,a t ;w) (切断相关性) 奖励设置 (S t ,a t ) Q network(预测Q网络) 每N个step 复制model 正奖励：当产生新的Activity、新的 state、页面有变化 Replay Memory (回放记忆库) a t (用于重复学习) Target Network：暂时冻结 q_target 参数存储(S t ,a t ,r t ,S t+1 ) Environment(环境) 根据Loss function 来更新NN参数在a t 的Q Q(S t ,a t ;w) S t+1 Target Q network (目标Q网络) Target Q值 Max at+1 Q(S t+1 ,a t+1 ;w’) 奖励惩罚：当前state被访问的次数 Loss function=(r t +γMax at+1 Q(S t+1 ,a t+1 )-Q(S t ,a t )) r t

22. PPO PPO(Proximal Policy Optimization)近端策略优化算法在训练过程中新旧策略的的变化差异如果过大则不利于学习。

23. conv 3x3,32 Critic 3x3,64 神经网络 Actor heatmap V

24. 输出事件转换将每个子view对应位置所有点的概率值求平均，即得到该子view的概率值

25. 实验评估结果测试了抖音app，与字节跳动Fastbot、北大深度学习框架Humanoid、DFS算法比较

26. UCT（MCTS）算法 Monte Carlo Tree Search，是一种人工智能问题中做出最优决策的方法，一般是在组合博弈中的行动（move）规划形式。它结合了随机模拟的一般性和树搜索的准确性。 AlphaGo三大利器：蒙特卡洛树搜索、卷积神经网络、强化学习 UCT 可以被描述为 MCTS 的一个特例：UCT = MCTS + UCB。

27. UCT（MCTS）算法选择 Selection：从根节点 R 开始，递归选择最优的子节点，直到达到叶子节点 L。扩展 Expansion：如果 L 不是一个终止节点，那么就创建一个或者更多的子节点，选择其中一个 C。模拟 Simulation：从 C 开始运行一个模拟的输出，直到博弈游戏结束。反向传播 Backpropagation：用模拟的结果输出更新当前行动序列。

28. 实验评估结果测试抖音app

29. 多智能体UCT算法多个agent共享同一个树模型，相互协作从同一个起点出发结束时各自遍历到不同区域

30. 实验评估结果测试今日头条app

31. 未来工作

32. 未来工作  更复杂的网络结构，提升算法性能  提高模型的通用性和泛化性  多平台：IOS、PC  业务拓展，比如游戏自动化测试、app敏感行为检测、模型重用、图像UI异常检测……不仅仅是一个Moneky类工具

33. 360技术 THANKS 360质量效能