GRT：基於編排程序分析的自動測試生成器其他頭條網

2020-04-12 17:16:00 慕測科技

摘要

在兼具高使用性和高度自動化的同時，現有的隨機測試技術往往存在代碼覆蓋率低、檢測能力弱的問題，導致在面對實際軟件應用時往往表現不佳。大多數隨機測試工具採用純黑盒方法，往往不會利用被測軟件的特定信息。如果能夠挖掘並利用被測軟件的特定信息來引導隨機測試過程，那麼將能夠協助隨機測試工具克服檢測能力弱的問題。

引導型隨機測試(GRT, Guided Random Test)實現了上述想法。GRT 採用靜態分析技術，從被測軟件中提取出一些相關信息，並進一步將運行時信息用於指導整個測試生成過程。GRT 具有高度的可配置性，它的六個程序分析組件均實現為獨立的插件，且插件參數均可按需調整。除生成測試用例外，GRT 還可以幫助用戶自動創建測試覆蓋率報告。作者將在本文中介紹他們在 GRT 工具開發方面的經驗，並通過兩種具體的應用場景對 GRT 的用法進行演示。

關鍵詞：自動測試生成；隨機測試；bug 檢測；靜態分析；動態分析

1 引言

單元測試是軟件開發過程中的一項重要的質量保證技術，但手動編寫單元測試用例往往會佔用大量的人力資源。構建單元測試通常需要三步：創建測試輸入、執行測試以及檢查測試輸出。如果一個易於使用的測試生成工具可以在自動化執行這三個步驟中的一個或多個的前提下，同時兼顧測試有效性（例如：具備較高的代碼覆蓋能力或較強的缺陷檢測能力），並且能夠為實際軟件系統的開發過程提供一定幫助，那麼就可以認為這個測試工具是有價值的。

在面向對象程序的單元測試流程中，被測軟件(SUT, Software Under Test)內的方法是（測試的）基本實體。為了能夠測試被測方法(MUT, Method Under Test) m 的目標行為，測試輸入需要與方法 m 的參數類型相兼容，以驅動待測方法 m。從基本數據值（構建複雜對象狀態的基本元素）出發，面向對象測試技術將增量地構建輸入對象。基本數據值將被用作調用對象構造器和方法所需的參數，以創建更為複雜的對象狀態。同時，通過對方法的調用序列的擴展，面向對象測試技術可以生成更多樣的對象狀態，從而可以為大部分 MUT 提供所需的輸入。測試生成技術最終生成的測試用例通常包括三個部分：初始基本數據（或常量）值、方法序列以及斷言。由於生成斷言與經典測試預言(Oracle)問題相似，需要對程序行為進行大量的預測，以支持斷言語句的產生，因此大多數自動測試技術都將研究重心放在尋找更合適的初始值以及創建更有效的方法序列上。

但是，由於可能的初始值和方法調用進行排列組合會導致測試生成的狀態空間十分巨大，大部分軟件系統的窮盡測試是不切實際的。因此，隨機測試一般會選擇生成可以儘可能執行到 MUT 中不同路徑的測試序列。但正因如此，隨機測試技術在處理實際應用項目時，往往會出現代碼覆蓋率偏低的情況。為了提升隨機測試的效果，反饋引導的隨機測試(FRT, Feed-back Random Test)技術隨機地選擇 MUT，通過不斷重用已生成的方法序列（將返回對象作為下一階段 MUT 輸入），迭代並增量地構建出更長、更復雜的測試序列。這一過程將不斷重複，直到到達工具預設的時間限制。然而即便如此，在某些應用場景下，FRT 的代碼覆蓋率仍然不盡如人意。

作者提出了一種名為 GRT 的全自動測試生成技術，能夠生成具有高代碼覆蓋率的測試用例。GRT 借用了 FRT 的設計思路，利用方法執行的結果迭代地指導測試生成；同時又採用編排程序分析（靜態和動態程序分析的組合）技術，解決了 FRT 和其他隨機測試技術中存在的一些問題。GRT 僅需要 SUT 和必要的依賴庫即可工作，對一些程序規範、歷史測試用例這樣的額外信息則沒有任何需求。

2 GRT: 使用編排程序分析的自動測試生成器

在設計 GRT 的過程中，作者團隊發現了一些可能影響 FRT 測試有效性的常見因素：

初始值的選取：雖然隨機測試大體上採用隨機策略產生測試輸入，但是如果想要生成複雜有效的輸入對象，合適的初始值（特別是基本數據值）非常重要。合適的初始值是構建良好輸入對象的基礎。

待測方法(MUT)的選取：為了達成更高的代碼覆蓋率，工具在生成新的測試用例時自然應該以未被覆蓋的 MUT 為目標，這樣新生成的用例才可以儘可能地覆蓋尚未被執行過的代碼。運行時的覆蓋率信息可用於將整個測試生成過程導向代碼覆蓋率不高的 MUT。

生成輸入數據的方法的選取：面向對象測試執行以方法級測試作為測試單元，這些方法通常以複雜對象為輸入參數。“如何選擇正確的方法來生成有效的序列（即返回對象）”是隨機測試過程中較為困難的核心問題。作者主要從以下兩個方面篩選選入序列的方法：

方法的屬性：方法簽名(Method Signature)刻畫了方法的主要屬性，包含方法的返回類型和參數列表。為了使設計更加靈活（即，允許在運行時傳入與方法聲明參數類型相兼容的參數），面向對象程序經常採用超類型而不是確定的子類型作為參數聲明。因此，同時考慮靜態和動態類型信息可以保證更加捕獲到方法屬性更加準確。此外，方法的純度（即運行這些方法會不會影響程序的運行狀態，產生副作用）也是與測試生成相關的重要方法屬性。
方法的依賴關係：通常情況下，想要在測試生成過程中同時考慮所有的適用方法（MUT 及其相關方法）是不切實際的，因為這樣做會將大量的資源浪費在非目標方法的測試上。但在方法池規模受限（例如，方法池中僅包含 MUT）的情況下，一些必要的特定類型對象無法通過 FRT 創建，這使得依賴於此類對象的所有 MUT 都無法被測試。因此，需要選取合適的可用方法池，由此才可以通過探索方法之間依賴關係對相關方法進行識別。

方法序列的組成：FRT 通過連接已有的方法序列產生新的方法序列。現有的工具通常通過隨機選擇返回可兼容類型對象的方法序列的方式，不斷拼接以構建新的方法序列。事實上，良好的生成策略可以在均衡幾個測試成本效益相關因素的前提下（例如方法序列的執行時間、方法序列覆蓋未執行代碼的可能性等），對測試序列生成任務進行優化。

圖 1：GRT 工作流概述

為了解決隨機測試和 FRT 中存在的問題、同時開源軟件以進一步完善 GRT 技術，作者在本文中展示了 GRT 的體系結構，如圖 1 所示。首先，GRT 對 MUT 執行靜態分析，以提取方法運行所需的信息；然後，以動態分析為嚮導，GRT 在方法運行時進行測試生成。GRT 工作流程中的運行階段以 FRT 為基礎，並在每個 FRT 的工作步驟中插入了 GRT 組件。具體來說，GRT 一共由六個組件構成，這些組件分別被安排在特定的工作步驟中，以便提取程序靜態或動態的信息，並在工作中彼此協作、相互補充。本小節的剩餘部分將分別對每個 GRT 組件的設計和實現進行介紹。

Constant Mining(CM)利用靜態分析手段從 SUT 中提取各種常量，並由此擴充基本數據類型的初始集合。CM 挖掘得到的常數值可以幫助工具創建更加多樣的（輸入）對象，以覆蓋待測程序中的更多分支。利用解釋器框架 ASM，我們將 CM 實現為一個抽象解釋器。該組件分析每個被測類(CUT, Class Under Test)的 Java 字節碼，並執行常量傳播(propagation)和常量摺疊(folding)。由於常量挖掘分析的是 Java 字節碼而不是源代碼，因此即使無法獲取 SUT 的源代碼，CM 也可以照常工作。

為了保證組件的可擴展性，CM 將提取出的常量分成全局常量和本地常量兩個級別進行管理。針對全局常量，CM 按照優先級從高到低的順序對其進行排序，被其他類使用的次數越多的全局常量的優先級越高。這樣就能讓使用頻率較高的常量更多地參與到測試輸入的過程中去；而本地常量往往是 GRT 在測試生成過程中從 MUT 的聲明類（即 CUT）中提取出來的。這麼做的原因在於：MUT 的聲明類中的常量通常與 MUT 有較高的相關性，因此可以更有效地覆蓋到特定分支。

Impurity 提供了一些可以修改對象狀態的方法，主要通過混淆輸入的方式提高 CM 的工作效果；同時，輸入混淆操作本身的效果也會因為 CM 挖掘到更好的常量而提高。在假設 CM 挖掘出的常量已經基本滿足一些分支條件的情況下，Impurity 採用高斯分佈處理基本數據值。執行高斯分佈所需的偏差值、以及參與輸入混淆的參數比，將作為參數傳入 Impurity，在使用過程中，用戶可以根據 SUT 的特性對這些參數進行調整。此外，Impurity 通過隨機插入、替換或刪除字符，以及將給定字符串替換成其子串的方式，對字符串常量參數進行混淆。

非基本數據類型的複雜對象的混淆操作時具有一定的挑戰性的，因為這個混淆化過程需要組件能夠識別出哪些方法可以使對象的狀態發生改變（也就是具備一定的副作用）。作者採用純度分析(Purity Analysis)技術來確定某個 MUT 是否具有副作用，並將有副作用的方法挑選出來。當一個複雜對象被選為測試輸入並且需要混淆處理時，工具會在這個複雜對象傳遞給 MUT 之前，執行該複雜對象中定義的雜質化方法（即會產生副作用的方法），使這個複雜對象產生變異。現階段 GRT 採用 ReIm 和 ReImInfer 框架實現 Impurity。ReIm 和 ReImInfer 框架可以分析出 SUT 的純度信息，並能夠推斷出 SUT 中帶有副作用的方法；同時，該框架不要求對 SUT 進行昂貴的、完整的程序分析，而採用一種基於類型系統的算法便可完成對方法的純度信息的推測。

Elephant Brain(EB)通過使用運行時的精確類型來對存儲在對象池中的所有對象進行管理。利用反射機制，EB 可以執行方法序列，並獲取到對應的返回對象；之後，通過分析這些返回的對象，EB 可以獲得運行時對象的精確類型信息；最後，工具將以精確類型信息為鍵，將方法序列對應存儲到對象池中。每當 MUT 需要靜態類型為 T 的輸入時，工具將在對象池中搜索，並返回與類型 T 相兼容（T 類型，或 T 子類型）的對象序列。按照用戶自定義的比率（默認比率為 0.5），工具將隨機地從這些對象中選取類型為 T 或者為 T 子類型的對象。 EB 可以找到哪些僅靠靜態類型信息無法生成的對象，從而能夠為其他組件（如 Impurity 和 Detective）提供更加精確的類型信息，由此可以提高這些組件的執行效果。

Detective 用於構造那些測試 MUT 需要的、但又無法在主對象池中直接找到的對象。Detective 首先對所有 MUT 執行靜態分析，以確定這些 MUT 的輸入和輸出之間存在的類型依賴，並在運行時利用這些類型依賴按需地構造缺少的輸入對象。比如當需要類型為 T 的對象作為測試輸入時，Detective 首先會隨機構造類型為 T 或 T 的子類型（如果 T 是一個接口或抽象類）的對象；然後，Detective 將分析 T 中所有可以返回對應對象的方法，並遞歸地挑選出返回值對象的類型與上一個方法的參數類型相兼容的方法。找到所有相關方法後，Detective 將按照以下拓撲結構執行這些方法：首先執行不依賴於其他方法返回值的方法。如果某個方法可以成功生成當前 MUT 所需求的、類型為 T 的對象，那麼這個對象將被保存在主對象池中，以備未來使用。除類型為 T 的對象外，執行方法生成的其他對象將被保留在第二對象池中，為之後快速查詢這些對象做好準備；同時，使用第二對象池可以可避免不相關的對象（中間對象）汙染主對象池。

Orienteering 通過分析每個方法序列的執行時間和序列長度（即方法調用語句的數量）來估算方法序列的執行成本。基於這兩種信息，工具可以為每個序列計算出相應的權重。這樣定義出來的權重可以使成本較低的方法序列具有較高的被選擇概率，同時還兼顧了那些生成了有趣新對象、但執行代價昂貴方法序列的位次。Orienteering 加快了 GRT 的整個測試生成過程。

Bloodhound 會智能地選擇那些覆蓋率低的 MUT。通過覆蓋更多的 MUT 代碼，工具可以到達更多的程序狀態。這個過程會潛在地創建一些新的對象，使得工具可以進一步提高測試效果。Bloodhound 會記錄目標 MUT 集的覆蓋率信息，併為其中每一個 MUT 計算相應的權重。根據 MUT 的權重，工具將隨機選擇下一個待測的 MUT。然而，通常情況下，在每個方法序列執行完畢後都重新監測代碼覆蓋率是非常不明智的；並且，總是選擇代碼覆蓋率低的 MUT 也會導致測試過程出現一些問題。這是由於某些 MUT 中可能包含一些本身就非常難以覆蓋到的分支，而強行測試這樣的分支是非常不划算的。為了解決以上問題，Bloodhound 會週期性地為每個 MUT 重算覆蓋權重，並由此來判斷下一輪測試到底是選擇“代碼覆蓋率低的”還是“被選取次數較少”的 MUT。

Bloodhound 使用運行穩定的覆蓋率評估工具 JaCoCo 來監視代碼覆蓋率。由於 JaCoCo 並不支持在線覆蓋分析，因此作者對 JaCoCo 進行了修改。修改後，每個被覆蓋的代碼片段和已執行方法序列的分支都可以被存儲下來，並供給下一步分析。當測試生成開始時，Bloodhhound 會使用探針加載並插樁 CUT，以收集工具所需要的代碼覆蓋率信息。如果代碼的相應部分被執行，則該片段中的探針將把這段代碼標記為“已被執行過的測試用例覆蓋”。