问题背景

近年来，移动运用程序的数量呈现爆炸性增加，随之而来的是用户对运用程序质量的高要求。保证运用程序的质量关于维护用户忠诚度和业务成功至关重要。但是传统的人工测验方法存在一些应战，包含耗费大量时刻和资源、可扩展性和可维护性的限制等，因而移动运用的主动化测验东西应运而生。跟着人工智能时代的到来，软件测验范畴不断向智能化发展，其间主动测验生成的才能一直是学术和工业界共同关注的研究热门，依托主动生成测验能较大程度减少测验脚本的编写与维护作业量。

在实践运用中，工业级运用程序经常需求进行更新以习惯不断变化的用户需求，例如，工业厂商一般每周都会发布一个新的中心运用版别，但是选用现有的主动化测验东西在这种状况下效果一般，它们仅仅是简单地在移动运用上从头运转一次测验，缺少对人类经验和常识的运用。Fastbot正是一款结合了强化学习和依据模型决议计划算法的主动化安卓测验东西，它由字节跳动软件工程实验室（se-research.bytedance.com/）团队提出，旨在运用强…

下面将逐一介绍东西的作业流程、中心概念、算法原理、规划完成以及常用装备，深入了解其在提升移动运用测验功率的才能。

作业流程

Fastbot 是一种运用强化学习的可复用的依据模型的主动化安卓测验东西。它接受一个给定的运用程序版别，以 APK 文件的方法作为输入，并输出掩盖报告和找到的溃散。Fastbot 的作业流程包含两个主要阶段，如图所示：

（a） 测验前的设置。a1 对 APK 文件进行反编译，收集控件的静态文本信息。a2 在一组设备上安装 APK，一起 a3 加载从前测验运转中的前史测验数据填充模型。

（b） 引导式 UI 探究。b1 从被测运用程序中获取当时的 GUI 页面，b2 辨认和笼统出当时页面上的可用 hyper-event（超事情，一组具有相同特点的事情，将在下文详细解说）。b3 挑选一个详细的 UI 事情，该事情有或许增加 Activity 掩盖率，b4 履行该事情。履行结束后，b5 更新前史测验数据、概率模型，一起 b6 更新强化学习智能体。

这些过程将循环迭代，直到运用完时刻预算。

中心概念

Hyper-event 超事情，表明概率模型中的事情，是一组具有相同特点的事情调集，这儿的特点只考虑以下四种：activity，text，resource id，action types。运用超事情对事情进行笼统能够在下降大型运用中的复杂性的一起平衡模型的可扩展性和准确性。
Probabilistic Model 概率模型 $M=(E,A,)M=(\mathcal{E} ,\mathcal{A},\delta)$ ，一个三元组，用于存储 event-Activity 的跳转关系。其间， $E\mathcal{E}$ 是一组 hyper-event 调集， $A\mathcal{A}$ 表明被测运用的 Activities 调集， $\delta$ 表转移函数，记载每一个 hyper-event 抵达一个 activity 的概率。
Q 表，强化学习中要害组成部分，用于记载每个对应状态下的 Q 值。
$P(e,A_i)$ 表明履行一个 hyper-event 之后抵达某个 Activity 的概率。
$P_M(e_i)$ 在概率模型 M 中挑选事情 $e_i$ 的概率。
$P_Q(e_i)$ 在 Q 表中 $e_i$ 对应的 q 值，即强化学习智能体挑选履行事情 $e_i$ 的概率值。
$E(ei)\mathbb{E}(e_i)$ 表明经过履行时刻 $ei(ei∈Ec)e_i(e_i\in\mathcal{E}_c)$ 抵达进步 Activity 掩盖率方针的期望值，期望值越大，阐明事情 e 能抵达新的 Activity 的概率越大。

技能和算法原理

Fastbot 的要害思想是运用存储在概率模型中的先验常识，去有效地辅导 GUI 测验。为了完成这一点，要害过程是决议在当时 GUI 页面上挑选哪个 UI 事情，能够快速地进步 Activity 掩盖率。详细而言，给定一个 GUI 页面，Fastbot 提取当时一切可用的超事情，并选用以下两种战略协同组合去挑选履行的事情：（1）依据模型的事情挑选，（2）依据学习的事情挑选。

1. 依据概率模型的事情挑选

模型的构建： 概率模型 M 从前史探究数据中构建，每个经过履行超时刻 e 抵达的 Activity $A_i$ 的概率核算公式如下：

$P(e,Ai)=N(e,Ai)N(e)P(e,A_i)=\frac{N(e,A_i)}{N(e)}$

其间， $N(e,A_i)$ 表明经过事情 e 抵达 $A_i$ 的次数， $N (e)$ 表明在一切之前的测验运转中 $e_i$ 被履行的总次数。留意，如果一个超事情 $e$ 能够抵达 k 个 Activities $A_1,A_2,…A_k$ ，则 $∑i=1kP(e,Ai)=1\sum_{i=1}^{k}P(e,A_i)=1$ 建立。

为了平衡模型对未知动作的探究和已知高回报动作的运用，避免陷入局部最优的僵局，依据模型的事情挑选包含两种模式：模型扩展和模型运用。

模型扩展： 如果当时 GUI 页面中的某些超事情没有包含在概率模型中，Fastbot 将发动扩展战略，随机挑选一个没有履行的超事情。在实践中有两种或许的状况：1）从前的测验运转或许没有掩盖一切的超事情，2）当时测验运用程序版别中增加了一些新的功能。该模式能够协助扩展模型并优先探究潜在的新功能。

模型运用： 如果当时 GUI 页面中的一切超事情都已包含在概率模型中，Fastbot 将发动运用战略，挑选一个具有更高概率的事情，来走到当时测验运转中没有被掩盖的 Activity。设 $A_t$ 为当时测验运转中已掩盖的 Activity 调集， $Ec\mathcal{E}_c$ 为当时 GUI 页面中的超事情调集，经过履行 $ei(ei∈Ec)e_i(e_i\in\mathcal{E}_c)$ 进步 Activity 掩盖率的期望值 $E(ei)\mathbb{E}(e_i)$ 的核算如下：

$E(ei)=∑A∉AtP(ei,A),0≤i≤∣Ec∣\mathbb{E}(e_i)=\sum_{A\notin \mathcal{A}_t}P(e_i,A),0\lei\le|\mathcal{E}_c|$

经过核算履行每个超事情后能够进步 Activity 掩盖率的期望值，Fastbot 运用概率模型作为先验信息，按照概率 $P_M(e_i)$ 进行挑选。核算 $P_M(e_i)$ 公式如下：

$PM(ei)=exp(E(ei))/∑ei∈Ecexp(E(ei))P_M(e_i)=exp(\frac{\mathbb{E}(e_i) }{\alpha } ) / \sum_{e_i\in \mathcal{E}_c}exp(\frac{\mathbb{E}(e_i) }{\alpha })$

$P_M(e_i)$ 的核算选用了依据 softmaxe 公式（激活函数）的调整，并经过设置超参数来操控模式的随机性。为了公平性，每个超事情最多被挑选次。经过运用概率模型作为先验信息，Fastbot 的模型运用模式能够在短时刻内快速改善活动掩盖。该算法的实践中，咱们设置为 0.8，为 1，以平衡随机性和公平性。

Fastbot 的算法原理在于运用从前的常识和概率模型，经过模型扩展和模型运用两种战略模式挑选事情，以快速进步 GUI 测验的 Activity 掩盖率。该算法的规划使得 GUI 测验能够更高效地进行，并能够习惯不同的运用场景。

2. 依据强化学习的事情挑选

前面概率模型只能表达一步的辅导信息，而强化学习技能能够将一步扩展为多步的辅导信息。Fastbot 选用了 Sarsa N-Step 算法作为奖赏函数去核算和更新 Q 值。

Q 表扩展。强化学习智能体的要害组成部分是 Q 表，其间包含 Q 值，它表明履行每个超事情能够抵达新的 Activity 的或许性。在测验过程中，不管运用哪种事情挑选战略，在 t 时刻下挑选的超事情 $e_t$ 在当时 GUI 页面上的 Q 值，记为（），经过以下公式更新 $Q(et)+(Gt,t+n−Q(et))Q(e_t)+\alpha (G_{t,t+n}-Q(e_t))$ ，该公式考虑 n 步之后的长远收益。其间 $G_{t,t+n}$ 是经过 Sarsa N-step 方法核算的 n 步后的累积收益，即 Sarsa N-Step 会推迟到时刻步为 t+N 时再进行更新。在此过程中记载每一个状态的奖赏，运用这些记载好的信息更新 q 值。也便是用 t+1～t+N-1 的 r 值和 t+N 的 Q 值核算 G，并运用这个核算好的 G 和 t 时刻的 Q 值更新 Q 值：

$Gt,t+n=rt+1+rt+2+…+nQ(et+n)G_{t,t+n}=r_{t+1}+\gamma r_{t+2}+…+\gamma^{n}Q(e_{t+n})$

其间， $\gamma$ 为扣头因子，表明考虑时刻对未来奖赏的影响，更加偏重当下的奖赏， $r_{t+1}$ 表明事情 $e_t$ 履行之后的下一时刻的奖赏，核算公式如下：

$rt+1=E(et)N(et)+1+VN(At)+1r_{t+1}=\frac{\mathbb{E}(e_t) }{\sqrt{N(e_t)+1} }+\frac{V}{\sqrt{N(A_t)+1} }$

其间，V 值表明 $A_t$ 的价值，即 $A_t$ 中有多少能够抵达新的 Activity 的有价值事情，分母部分都用根式来调整期望值，使得拜访和履行次数较少事情和 Activity 都能有更多的权重，避免过度依靠前史经验丧失多样性。

V 值的详细核算公式如下：

$V=nh+0.5∗nc+∑ei∈EcE(ei)V=n_h+0.5*n_c+\sum_{e_i\in \mathcal{E}_c }\mathbb{E}(e_i)$

其间， $n_h$ 表明当时页面中不在概率模型 M 中的超事情的数量， $n_c$ 表明下一个页面中，现已被 M 模型加入但是在本次测验中没有被履行过的超事情的数量。 $∑ei∈EcE(ei)\sum_{e_i\in \mathcal{E}_c }\mathbb{E}(e_i)$ 表明履行事情能够进步 Activity 掩盖率的累积期望值。

Q 表运用。当 Q 表更新完后，经过以下公式核算得到每个超事情 $e_i$ 被挑选的概率：

$PQ(ei)=exp(Q(ei))/∑ei∈Ecexp(Q(ei))P_Q(e_i)=exp(\frac{Q(e_i)}{\beta } )/\sum _{e_i\in \mathcal{E}_c }exp(\frac{Q(e_i)}{\beta } )$

其间， $\beta$ 是一个超参数，用于调整战略的随机性。在实践中，被设置为 0.1。

3. 事例解说

为了加深了解，下面用头条运用来对算法的几种决议计划进行解说：

概率模型的探究与运用模式

经过对前史数据记载对概率模型 M 初始化，见图 b，发动头条运用后，进入 home Activity1，当时页面能够笼统为 3 个 hyper-event，这三个事情都被包含在模型中，因而 Fastbot 回发动模型运用战略挑选事情，看图 b 左边部分，能够知道 e3 有 90%的概率留在 Activity1，因而更倾向于挑选 e1 和 e2，假定挑选 e1 后，抵达 Activity2，在 Activity2 中 e4 现已在模型中，而且 100%回到 Activity1，一起 e5，e6 不再模型中，此刻 Fastbot 将发动探究模式，随机挑选 e5 或者 e6，如果挑选 e5，抵达 Activity3，此刻模型增加一条 e5-Activity3 的概率值 100%，一起由于 e1 的履行次数加 1，因而 e1 的概率也要改变，e1-Activity2 的概率变为 0.7/1.1=63.6%，e1-Activity5 的概率变为 36.4%，更新为图 b 右半部分。

Q 表的更新运用

在图 a 中，Activity2，e4，e6 没有被履行过，一起 e6 不在模型内，因而 e1 的奖赏更高，类似的，e7，e8 也是新的事情，因而 e5 的奖赏会更高，假定 e1，e2，e3 都会履行过很屡次，而且 Activity2，3，4 都被掩盖了，此刻将运用 Q 表中的值去核算事情挑选的概率，在当时 Activity1 中，由于 e1 的奖赏最高阐明他能够抵达更深的 Activity，因而挑选 e1 作为下一个事情履行。

规划完成

Fastbot 开源版包含客户端和本地服务端两部分，客户端担任监听 UI 事情，接纳和注入相应的动作，服务端担任核算和决议计划。详细而言，在每个设备上运转 Fastbot 客户端，经过监控 GUI 页面信息发送给服务端，服务端接纳信息依据算法决议计划回来挑选的事情，客户端接纳事情并履行操作。

客户端运用 Java 言语编写，用于获取 GUI 信息，读取服务端决议计划，并将决议计划转化为设备能够履行的代码，然后操作设备；本地服务端，即与 Java 层相对应的底层 C/C++代码层，以动态链接库（.so 文件）的方法与 Java 层经过 JNI 接口进行交互，它用于完成用户偏好的读取，模型的学习和任务决议计划，并将决议计划结果转化为 JSON 格局的信息传递给 Java 层。

Fastbot 的完成继承 Monkey 原生框架，下图展现了 Fastbot 扩展的代码简要结构图，在 java 层新增了来自 Fastbot 算法回来的事情源 MonkeySourceApeNative 类，对 GUI 树的获取，以及对 Android 不同的系统的兼容的 Adapter 适配接口，此外，为了支持自定义操作的解析和履行对 Monkey 的原始事情进行了封装。

常用装备

1. 装备自定义事情

Fastbot 支持自定义事情序列，适用于场景掩盖不全，经过人工装备抵达 Fastbot 遍历不到的场景。

装备过程：

新建 max.xpath.actions 文件（文件名称固定不能更改）
参照事例格局指定控件和相应的动作。其间：
1. prob：产生概率，”prob”：1，代表产生概率为 100%
2. activity：所属场景
3. times：重复次数，默以为 1 即可
4. actions：详细需求履行的事情序列，其间要指名每个操作目标的 xpath，对应的动作 action，和与下一个事情间隔的时刻 throttle（ms），留意 xpath 写法
动作类型（必须大写）：
1. CLICK：点击，想要输入内容在 action 下弥补 text，如果有 text 则履行文本输入
2. LONG_CLICK：长按
3. BACK：回来
4. SCROLL_TOP_DOWN：从上向下滚动
5. SCROLL_BOTTOM_UP：从下向上滑动
6. SCROLL_LEFT_RIGHT：从左向右滑动
7. SCROLL_RIGHT_LEFT：从右向左滑动
装备完成后，将装备文件推送到手机端： adb push 途径+max.xpath.actions /sdcard

下面以 AmazeFileManager 为例：

第一种状况：当事情履行不触及 Activity 的跳转时，只需将一切的事情序列写在一个目标中。

如图所示，actions 字段里的 4 个动作别离对应下图中红框标出的动作，（1）点击菜单按钮翻开菜单栏，（2）点击 recent file 按钮抵达相应文件目录，（3）点击加号按钮，翻开浮选选项，（4）点击 File 按钮翻开新建文件对话框。

[
    {
        "prob":1,
        "activity":"com.amaze.filemanager.ui.activities.MainActivity",
        "times":1,
        "actions":[
            {
                "xpath":"//*[@content-desc='Navigate up']",
                "action":"CLICK",
                "throttle": 2000
            },
            {
                "xpath":"//*[@resource-id='com.amaze.filemanager:id/design_menu_item_text' and @text='Recent files']",
                "action":"CLICK",
                "throttle": 2000
            },
            {
                "xpath":"//*[@resource-id='com.amaze.filemanager:id/sd_main_fab']",
                "action":"CLICK",
                "throttle": 2000
            },
            {
                "xpath":"//*[@resource-id='com.amaze.filemanager:id/menu_new_file']",
                "action":"CLICK",
                "throttle": 2000
            }
        ]
    }
]

第二种状况：当事情履行触及到 Activity 的跳转时，要将对应不同 Activity 的事情序列独自存放。

下图展现了从 MainActivity 跳转到 PreferencesActivity 的例子。

能够看到在装备文件中有两个目标，别离对应 MainActivity 和 PreferencesActivity 两个页面下需求履行的事情序列。

[
    {
        "prob":1,
        "activity":"com.amaze.filemanager.ui.activities.MainActivity",
        "times":1,
        "actions":[
            {
                "xpath":"//*[@content-desc='Navigate up']",
                "action":"CLICK",
                "throttle": 2000
            },
            {
                "xpath":"//*[@resource-id='com.amaze.filemanager:id/design_navigation_view']",
                "action":"SCROLL_BOTTOM_UP",
                "throttle": 2000
            },
            {
                "xpath":"//*[@text='Settings' and @resource-id=['com.amaze.filemanager:id/design_menu_item_text']",
                "action":"CLICK",
                "throttle": 2000
            }
        ]
    },
    {
         "prob":1,
         "activity":"com.amaze.filemanager.ui.activities.PreferencesActivity",
         "times":1,
         "actions":[
                 {
                     "xpath":"//*[@resource-id='android:id/title' and @text='Appearance']",
                     "action":"CLICK",
                     "throttle": 2000
                 }
             ]
    }
]

带文本输入的状况

装备格局： 在 action 字段挑选“CLICK”，一起增加“text”字段存储需求输入的文本。

以抖音为例，运用以下装备信息能够指定完成输入账户信息的操作。两个动作，别离对应点击 use phone 按钮和输入文本。

[
    {
        "prob":1,
        "activity":"com.ss.android.ugc.aweme.account.login.auth.I18nSignUpActivityWithNoAnimation",
        "times":1,
        "actions":[
            {
                "xpath":"//*[@resource-id='com.zhiliaoapp.musically:id/ayo' and @text='Use phone / email / username']",
                "action":"CLICK",
                "throttle": 2000
            }
        ]
    },
{
        "prob":1,
        "activity":"com.ss.android.ugc.aweme.account.login.v2.ui.SignUpOrLoginActivity",
        "times":1,
        "actions":[
            {
                "xpath":"//*[@text='Phone number' and @resource-id=['com.zhiliaoapp.musically:id/e61']",
                "action":"CLICK",
                "text":"12341828506",
                "throttle": 2000
            }
        ]
    }
]

2. 屏蔽控件

Fastbot 支持手动装备需求屏蔽的控件或区域，比方测验过程中“半路”中途退出登录，屏蔽退出登录按钮。

装备过程：

新建 max.widget.black 文件（文件名称固定不可更改）
参照事例格局指定需求屏蔽的控件，格局如下：
1. activity：当 activity 与 currentactivity 共同时履行如下匹配
2. 屏蔽控件或区域共有三种方法：
  - bounds：屏蔽某个区域，在该区域内的控件或坐标不会被点击。
  - xpath：查找匹配的控件，屏蔽点击该控件。
  - xpath+bounds：查找匹配的控件，当控件存在时屏蔽指定的区域。
装备完成后，将装备文件推送到手机端： adb push 途径+max.widget.black /sdcard

下面以 AmazeFileManager 为例，展现怎么进行控件，区域以及树剪枝屏蔽：

屏蔽控件

如图（a）所示，红框标出来的黑色区域控件是手动装备的屏蔽控件。在这儿，运用 xpath 来指定需求被屏蔽的控件。

[
{
    "activity":"com.ss.android.ugc.aweme.main.MainActivity",
    "xpath":"//*[@content-desc='Navigate up']"
},
{
    "activity":"com.ss.android.ugc.aweme.main.MainActivity",
    "xpath":"//*[@content-desc='More options']"
}
]

屏蔽区域

如图（b）所示，红框标出来的黑色区域控件是手动装备的屏蔽区域。在这儿运用 bounds 来装备屏蔽区域。

[{    "activity":"com.ss.android.ugc.aweme.main.MainActivity",    "bounds":"[0,18],[240，60]"}]

树剪枝屏蔽

树剪枝屏蔽是指在 GUI 树中查找到对应控件，经过将控件特点的 enable 设置为 False，然后使控件屏蔽。

装备过程：

装备 max.tree.pruning 文件（文件名固定不可更改）
参照事例格局指定需求屏蔽的控件，格局如下：
1. activity：当 activity 与 currentactivity 共同时履行如下匹配
2. 剪枝方法：装备 xpath，查找匹配的控件，改变控件特点，然后使控件屏蔽。
装备完成后，将装备文件推送到手机端： adb push 途径+max.tree.pruning /sdcard

例子：仍以 AmazeFileManager 为例， 如上图（c）所示，被红框标出的黑色区域即为手动装备的树剪枝屏蔽控件，能够经过将控件的 enabled 特点变为 flase，也能够将其他特点变为空来完成屏蔽。

[
{
    "activity":"com.ss.android.ugc.aweme.main.MainActivity",
    "xpath":"//*[@content-desc='Navigate up']",
    "enabled":"false"
},
{
    "activity":"com.ss.android.ugc.aweme.main.MainActivity",
    "xpath":"//*[@content-desc='More options']",
    "enabled":"false"
},
{
    "activity":"com.ss.android.ugc.aweme.main.MainActivity",
    "xpath":"//*[@resource-id='com.amaze.filemanager:id/search'",
    "resourceid":"",
    "contentdesc":"",
    "text":"",
    "classname":""
}
]

Fastbot 开源版技术原理与架构

问题背景

作业流程

中心概念

技能和算法原理

1. 依据概率模型的事情挑选

2. 依据强化学习的事情挑选

3. 事例解说

规划完成

常用装备

1. 装备自定义事情

2. 屏蔽控件

更多信息

作者信息

Fastbot 开源版技术原理与架构

问题背景

作业流程

中心概念

技能和算法原理

1. 依据概率模型的事情挑选

2. 依据强化学习的事情挑选

3. 事例解说

规划完成

常用装备

1. 装备自定义事情

2. 屏蔽控件

更多信息

相关文章

C2000学习（1）–配置软件和第一个模板

静态编译的less如何动态换肤

带你走进Java数据结构与算法（三）

集帅(美)们，别再写 :key = “index” 啦！

作者信息