Fastbot:行進中的智能 Monkey

發表于:2020-11-16 09:53  作者:字節跳動技術團隊   來源:掘金

字體: | 上一篇 | 下一篇 |我要投稿 | 推薦標簽: APP測試 軟件測試技術

  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 算法示例圖
  單步 UCB 算法耗時少,且其引入訪問次數平衡項后,很好的阻止了局部循環的發生,使動作決策更加分散化。此算法的一個缺點是其只考慮了當前一步以內的 UCB 最優動作,若將 N 步以內的可執行動作都加入考慮范圍,選擇結果可能有所不同。為此,我們同時介紹 N 步的 UCB 算法,該算法會遍歷當前動作及該動作以后的 N-1 步以內所有可執行的動作,將所有動作的優先級乘上衰減系數并累加,最終的結果最為當前動作的 UCB 值。N 步 UCB 算法的公式由公式 2 所示:
  盡管 N 步 UCB 算法考慮了更多的步驟,但在時間復雜度上也做出了犧牲。由于需要對未來 N 步的動作做出預測,我們需要額外的 N 的指數級別的耗時。因此,N 的值最好漸進增長。
  3.2 MTree 算法
  然而,不論是單步 UCB 算法或是 N 步 UCB 算法,都只是利用了一步或 N 步以內的信息,而非利用到整個模型上的信息。由于環路的存在,模型上的反向傳播無法順利進行。我們希望能夠實現全局的方向傳播,將新訪問到的頁面信息一直傳遞到起始節點。當覆蓋到新的 Activity 時,我們希望路徑上的每個節點都得到更新。因此,我們考慮將有向有環圖模型裁剪為樹狀結構,從而避免環路帶來的干擾。樹的節點代表著模型中的 State,在節點中,我們保存上一步的 Action,記錄上一步的 State 作為父節點,記錄下一步可以到達的 State 為子節點。使用 MTree 算法后各子節點的優先級由公式 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 流程扮演重要的基礎服務角色。我們相信,越來越多的智能化測試工具,將極大的改善國內傳統測試行業。

  本文內容不用于商業目的,如涉及知識產權問題,請權利人聯系博為峰小編(021-64471599-8017),我們將立即處理

評 論

論壇新帖

頂部 底部


建議使用IE 6.0以上瀏覽器,800×600以上分辨率,法律顧問:上海瀛東律師事務所 張楠律師
版權所有 上海博為峰軟件技術股份有限公司 Copyright©51testing.com 2003-2020, 滬ICP備05003035號
投訴及意見反饋:webmaster@51testing.com; 業務聯系:service@51testing.com 021-64471599-8017

滬公網安備 31010102002173號

51Testing官方微信

51Testing官方微博

掃一掃 測試知識全知道

日本av