1. 背景
近年來，App 的玩法變得越來越多，功能也愈加複雜。App 的穩定性與健壯性也變得更加重要，因其帶來的更好的使用者體驗能讓 App 在激烈的競爭市場中脫穎而出。正因如此，針對 App 的穩定性與健壯性，相關的自動測試技術也成為軟體工程和智慧化測試的熱門研究方向。
1.1 自動測試生成簡介自動測試生成（Automated Testing Generation）技術，也叫 AIG（Automated Input Generation）技術。傳統的自動化方式，比如錄製與回放（Record & Replay），依賴於測試人員編寫測試指令碼。同時，跟隨著測試需求的改變，測試人員需要耗費一定的時間維護和調整相應的測試指令碼。與錄製回放的方式相比，將測試活動依賴的通用服務進行抽象，依靠自動的方式生成測試活動需要的操作，能較大程度減少測試指令碼的編寫與維護工作量。
目前，典型的 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 系統的工作流程圖，圖中展示了客戶端與服務端分離的工作方式。
位元組的實際測試場景中，往往需要同時對多個打包好的 App 進行測試。因此，Fastbot 系統還支援實際業務場景的多工並行，以對不同 App 或 App 的不同版本進行測試任務。以每個任務為單位，服務端會有唯一的任務模型與之對應。同時，我們支援為任務配置自定義事件，以實現賬號登入，特殊場景訪問等功能。服務端的每個任務對應多個客戶端裝置，每個裝置上，我們會配置好一套相應的客戶端程式碼，實現客戶端代理的功能。客戶端代理的主要功能包括：監控頁面 GUI 資訊傳送給服務端，以及接收服務端傳送的動作並在裝置上實現。
與之對應的，在服務端也有服務端代理 Agent。每個服務端 Agent 為一臺裝置負責，接收其頁面資訊，對其進行封裝，產生 State 節點，服務端 Agent 會根據當前的 State 資訊，根據分配好的指定演算法，與任務模型互動做出動作決策，並將決策出的動作傳送回給客戶端 Agent。
在此過程中，我們將 State 和 Action 更新到了服務端的任務模型中，並記錄下了是否發生崩潰，覆蓋率資訊，通往當前節點的有效路徑等多種資訊，用以實現資料分析，路徑回放和測試生成。
2.2 Fastbot 模型介紹如前文所述，我們將頁面的 GUI 資訊抽象成模型中的 State，將執行的動作抽象成模型中的 Action，通過 State 作為圖的節點，Action 作為圖的邊，連線形成有向有環圖模型。圖 3 展示了有向有環圖的區域性示例，其中箭頭虛線代表著執行動作，連線起了各個節點。
多機協同時，模型如圖 4 所示，其中每種顏色代表一個 Agent 的行動軌跡。
如何將頁面的 GUI 資訊抽象成模型中的 State 也是我們面臨的一大難題。我們需要保證粒度不要太細，以至於頁面稍有變化（如極其小幅的滑動，或同類型按鍵順序上的變化）就被定義為全新的 State，導致 State 數量爆炸，記憶體佔用過高。同時，我們又不能做過於寬泛的抽象，至少要保障決策出的動作可以找到對應的執行控制元件。通過長期的觀察測試，我們得到的效果最好的抽象方式為通過頁面的 Activity 名，控制元件上可執行的動作型別，以及控制元件樹一維化後的排列分佈進行 State 類的構建。
3. Fastbot AI-Core 介紹對於靜態 Native App 上的測試，如計算器或日曆 App，其狀態有限，動作的結果相對統一，很少出現統一動作導向不同結果的情況，這種情況下傳統的 DFS、BFS 演算法仍有不錯的遍歷效率。
為了實現更有效率的遍歷探索，我們在 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 值，所以我們仍會優先嚐試未訪問過的動作。
單步 UCB 演算法耗時少，且其引入訪問次數平衡項後，很好的阻止了局部迴圈的發生，使動作決策更加分散化。此演算法的一個缺點是其只考慮了當前一步以內的 UCB 最優動作，若將 N 步以內的可執行動作都加入考慮範圍，選擇結果可能有所不同。為此，我們同時介紹 N 步的 UCB 演算法，該演算法會遍歷當前動作及該動作以後的 N-1 步以內所有可執行的動作，將所有動作的優先順序乘上衰減係數並累加，最終的結果最為當前動作的 UCB 值。N 步 UCB 演算法的公式由公式 2 所示：
儘管 N 步 UCB 演算法考慮了更多的步驟，但在時間複雜度上也做出了犧牲。由於需要對未來 N 步的動作做出預測，我們需要額外的 N 的指數級別的耗時。因此，N 的值最好漸進增長。
此外，隨著裝置數的增加，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 有效率。
5. 總結目前，Fastbot 已廣泛應用於位元組客戶端類產品的穩定性測試與相容性測試。每日啟動任務數超過 300 次，每日平均發現 5000 個以上的崩潰，並有超過 100 個新捕獲的崩潰。藉助 Fastbot 的能力，我們在發版前就可以修復大部分的 crash，確保線上使用者的使用體驗。同時，Fastbot 在整個 DevOps 流程扮演重要的基礎服務角色。我們相信，越來越多的智慧化測試工具，將極大的改善國內傳統測試行業。
6. 加入我們位元組跳動Quality Lab，是位元組跳動旗下的工程效能理論研究與技術預研團隊。我們立足於人工智慧前沿技術，通過機器學習與深度學習等領域的技術創新，為軟體品質與工程效能提供更多的高效測試服務。在成為全球頂尖的智慧工具團隊道路上，希冀為品質領域帶來更多的智慧化手段。
在這裡，你可以利用NLP技術玩轉智慧客服，實現機器與人的對話，提升運營工作效率；也可以用機器視覺與強化學習，創造具有超強能力的測試機器人，並在數以千計的裝置上驗證你的演算法；還可以實踐各種教科書上的測試理論，去幫助業務提升測試效率，組合測試、程式分析，還有精準測試，都等著你來探索；更可以與國內外頂尖機構進行交流合作，與世界各地的學者一起探索更多軟體工程領域的可能性。歡迎各位有識之士加入我們。簡歷投遞郵箱： tech@bytedance.com ；郵件標題： 姓名 - 工作年限 - Quality Lab 。