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 ，

Fastbot：行進中的智能 Monkey