引用:
Pietro Braione, Giovanni Denaro, SUSHI: A Test Generator for Programs with Complex Structured Inputs, ACM/IEEE 40th International Conference on Software Engineering: Companion Proceedings, 2018, 21-24
摘要：
隨機的和基於搜索的測試生成器基於程序 API 生成實際的測試用例，但是經常缺少依賴複雜數據結構實例的結構化測試目標； 符號執行可以精確地描述那些依賴關係，但不計算方法序列以實例化它們。 我們介紹 SUSHI，這是一種用於具有複雜結構輸入的程序的高覆蓋率測試用例生成器。 SUSHI 利用符號執行來生成精確描述程序路徑和輸入數據結構之間關係的路徑條件，並將路徑條件轉換為基於搜索的測試生成問題的適應度函數。 搜索問題的解決方案是合法的方法序列，該方法序列實例化結構化的輸入以執行由路徑條件標識的程序路徑。 我們的實驗表明，SUSHI 可以很好地補充當前的自動測試生成工具。
關鍵詞：自動測試用例生成，符號執行，基於搜索的軟件工程
1.介紹
自動生成測試用例減輕了編寫測試的負擔。當前的測試生成器利用隨機測試，基於搜索的測試和符號執行。 隨機測試生成器通過對方法序列進行隨機採樣來合成測試用例，以通過其公共接口來運行被測程序。基於搜索的測試生成器利用適合特定代碼元素（例如程序分支）執行的適應度函數來指導隨機選擇。隨機和基於搜索的測試生成器都忽略程序控制流和輸入數據結構之間的關係。結果，他們可以成功地合成實例化簡單數據結構的方法序列，但不能令人滿意地處理只能由複雜輸入數據結構觸發的測試目標。
圖 1 中第 14 行的分支體現了對數據結構的複雜依賴。程序採用兩個進程列表（第 3 行），將主列表中的進程設置為具有高優先級（第 4-5 行），構建一個新列表，其中包括主列表的所有進程（第 6 行），可能還有次級列表中的所有進程（第 7-10 行），最後通過首先執行高優先級的進程（第 11-13 行）來處理結果列表，同時推遲其他進程（第 14 行）。在第 14 行執行延遲代碼的測試用例必須使用一個比物理單元更多進程數量（8 個）的主列表以及一個至少有一個低優先級進程的次級列表才能調用方法 execPool,。最先進的隨機和基於搜索的測試生成器（如 Randoop 和 EvoSuite）在 12 小時內沒有覆蓋圖 1 中第 14 行的分支：純隨機抽樣發現所需輸入的概率可忽略不計;儘管基於搜索的算法沒有指導來識別它，但要滿足分支條件 p.getPriority
一些符號執行器生成的路徑條件精確地表徵了對輸入數據結構的約束，以執行給定的程序路徑，例如，圖 1 中第 14 行的分支的路徑條件。它們不會直接生成可執行的測試用例，這些用例會實例化滿足路徑條件的具體數據結構。一些測試生成器通過生成一些繞過程序接口並直接操作內存的測試來解決此問題，但是最近的研究表明，這種做法導致了許多不切實際甚至有時是非法的測試用例。其他符號執行器則利用靜態分析來確定滿足路徑條件的方法序列。他們成功地生成了實例化簡單數據結構的測試用例，但由於理論上的侷限性以及平衡其靜態分析的效率與精度的困難而未能處理複雜的數據結構。
圖 1 樣例程序 execPool()
本文介紹了 SUSHI，這是一種測試生成器，它可以有效地生成由合法方法調用序列組成的測試用例，這些測試用例將會測試複雜結構輸入依賴的程序。SUSHI 實例化了我們在最近的論文中介紹的方法。SUSHI（i）符號執行程序獲取能代表程序路徑與輸入數據結構之間依存關係的路徑條件，（ii）選擇適當的路徑條件子集以解決某些覆蓋目標，（iii）將選定的路徑條件轉換成適合度函數，該函數量化輸入狀態與滿足路徑條件的距離，並且（iv）利用適合度函數進行元啟發式搜索以生成滿足路徑條件的方法調用的合法序列。
本文通過詳細研究 SUSHI 工具的設計和實現來開展研究論文。 本文（i）闡述了該工具的模塊化架構，（ii）指定了 SUSHI 用於在選定的覆蓋率標準上最大化覆蓋結果的路徑選擇算法（iii）說明了利用利用由路徑條件派生的適應度函數所指導的 EvoSuite 測試生成器的 SUSHI 元啟發式搜索階段（iv）描述了 SUSHI 用於減輕不可行路徑對測試收縮過程的影響的反饋循環，以及（v）討論了最終用戶如何使用 SUSHI 自動生成高覆蓋率測試用例
2. SUSHI 設計
SUSHI 是為 Java 程序服務的開源測試生成器，它生成了高分支覆蓋率的測試套件。圖 2 說明了 SUSHI 的模塊化體系結構：路徑發現器利用程序路徑的符號執行去發現程序執行控件並且計算程序路徑的執行條件。 路徑選擇器將如何選擇路徑子集以最大化分支覆蓋範圍的任務轉換為線性編程問題，可通過專用庫解決。 路徑評估器實現了我們最近提出的方法，該方法將路徑條件轉換為可執行的評估條件，從而量化了某一具體狀態到滿足相應路徑條件的狀態之間的距離。方法序列生成器使用基於搜索的引擎生成選定路徑條件的具體測試用例，該引擎將評估器用作適應度函數。
圖 2 SUSHI 體系結構
2.1 路徑發現器
SUSHI 利用符號執行器 JBSE 既以深度優先的順序遍歷程序路徑（直至某些用戶定義的邊界），並計算相應的路徑條件。 JBS 負責處理符號執行，幷包括一組技術來解釋結構化輸入的結構不變性。
SUSHI 利用 JBSE 收集路徑條件和覆蓋率信息，即在符號執行過程中遍歷的程序分支集。例如，對於圖 1 中的程序，JBSE 通過在第 14 行描述執行分支的輸入集的路徑條件計算了一條遍歷第 14 行的分支的路徑。
2.2 路徑選擇器
路徑選擇器通過將路徑選擇任務公式化並解決為線性編程問題，從而識別出足夠的路徑子集來覆蓋程序分支。該路徑選擇器：
（1）將覆蓋率信息轉換為係數 cij 的矩陣，使得每一行 i 對應於一條探索路徑，每列 j 對應於一條探索分支（如果第 i 條路徑覆蓋第 j 條分支，則係數 cij 為 1，否則為 0 ）
（2）將每個探索的路徑與變量 si 關聯，求解器將該變量 si 設置為 0 或 1，以指示給定路徑是否屬於選擇路徑，並且
（3）使用 GLPK 求解器找到變量的最佳分配，該分配可最大程度地減少選定路徑的數量，該選定數量 paths=∑si,同時保證所有分支的覆蓋率滿足要求,該要求表示為一組線性約束 ∑cij*si >0，對於每個分支 j。產生的分配指示最大化分支覆蓋範圍的路徑子集
SUSHI 目前可以最大程度地擴大分支覆蓋範圍，可以通過修改 Path Explorer 組件輕鬆地適應其他結構化測試標準，從而在探索的路徑與目標代碼元素之間生成合適的映射。
2.3 路徑評估生成器
路徑評估器生成器將選定的路徑條件轉換為距離評估器程序，該程序計算滿足路徑條件中所有子句的測試用例 t 的距離。簡而言之，評估程序檢查與測試用例 t 相對應的執行狀態，以驗證其是否符合路徑條件中的執行條件。
評估程序是 SUSHI 調用的可執行的方法，SUSHI 使用測試用例 t 當前傳遞給被測程序的輸入來調用它。 如果輸入滿足相應路徑條件中的所有子句，則評估器將返回最小距離 0，否則返回大於 0 的距離。 每個不滿足的路徑條件子句都會使返回的距離增加（0，1]，對於嚴重不符合該子句的輸入，其值越來越接近 1。
例如，對於第 2.1 節中的路徑條件，一個測試用例在進程主列表中有 9 個進程，在次要列表中有 1 個低優先級進程，因為它滿足路徑條件中的所有子句，所以它的最佳距離為 0。 相反，在主列表中有 8 個進程的測試用例的距離 α> 0，因為它不滿足條件 primary.size> 8; 一個在主列表中具有七個進程的測試用例的求值距離為 β>α，因為它錯過的相同子句的數量更大，依此類推。 我們向讀者推薦“Combining symbolic execution and search-based testing for programs with complex heap inputs”一文，以獲取評估器的詳細數學定義。
路徑評估生成器是 SUSHI 的核心技術特性。 與傳統的符號執行程序不同，SUSHI 僅生成與方法調用的合法序列相對應的測試用例：SUSHI 將路徑條件轉換為元啟發式搜索過程的適應度函數，該搜索過程將搜索引導至滿足路徑條件的可達程序狀態的方法序列。
2.4 方法序列生成器
方法序列生成器將路徑條件距離評估器集成到元啟發式搜索過程中，以生成滿足相應路徑條件的實例化程序狀態的方法調用序列。
方法序列生成器利用 EvoSuite 工具作為基於遺傳算法的元啟發式搜索引擎。 圖 3 說明了搜索算法及其與路徑條件距離評估器的集成。搜索算法從隨機填充的方法序列的集合可是，然後逐步進行新的迭代。方法序列生成器通過採用進化算子生成的新方法序列（稱為後代）擴展當前代，從而構建了新一代序列。標準的進化算子包括突變（隨機改變，添加或刪除語句）和交叉（交叉），交叉結合了兩個方法序列。
圖 3 通過路徑條件匹配的搜索算法
對於每個新生成的後代，該算法都會計算一個適應度值，該適應度值表示從當前狀態開始到能夠生成一種方法序列的距離，該方法序列在滿足路徑條件中所有子句的狀態下調用目標方法，從而執行相應的程序路徑。搜索算法通過執行方法序列來計算適合度值。如果方法序列未調用目標方法，則測試執行程序將返回最大距離值，因為方法序列無法通過構造的方法覆蓋目標路徑。否則，在攔截對目標方法的調用後，測試執行程序將使用與目標方法調用相同的參數來執行路徑條件距離評估器，並根據評估器返回的距離值來設置適合度值。在多次調用目標方法的情況下，結果適合度值是所有調用中的最佳值。
該算法在確定具有最佳適應度的方法序列後返回測試用例。例如，當使用表示第 2.1 節中討論的路徑條件的評估器時，方法序列生成器將產生圖 4 中的測試用例，該用例成功覆蓋了圖 1 中第 14 行的分支。EvoSuite 的執行受到時間預算的限制，並且當搜索時間超出預計時間時，方法序列生成器可能不會針對路徑條件返回測試用例。
圖 4 針對圖 1 中的程序的一個 SUSHI 測試用例
2.5 處理不可行的路徑
僅當所選路徑條件對應於可行路徑（即有效程序行為）時，方法序列生成器才會生成具體的測試用例。 但是，由於無法確定某些公式的可滿足性，因此路徑發現器可能會保守地計算一些無法滿足的路徑條件。但是，路徑發現器可能會忽略某些隱式程序不變式，併產生違反這些約束的路徑條件。
SUSHI 通過兩種補充機制來減輕不可行路徑的影響：
（1）它依靠 JBSE 的支持來利用開發人員提供的前提條件和不變式的規範；
（2）它實現了一個反饋循環，以監視方法調用序列的路徑條件的具體化。 如果“方法序列生成器”未能具體化路徑條件，則 SUSHI 會在路徑選擇器（圖 2）中重新遍歷，以考慮有助於實現最佳覆蓋範圍的替代路徑條件。
反饋迴路得益於方法序列生成器的並行部署，可提高生成過程的效率：SUSHI 實例化 EvoSuite 過程池，以通過其相應的距離評估器在選定的路徑條件下同時工作。 每當 EvoSuite 流程成功生成路徑條件的測試用例時，它都會將所覆蓋的分支通知路徑選擇器。在每次迭代中，路徑選擇器都會優化一個簡化的問題，該問題不考慮覆蓋的分支以及先前選擇的路徑條件。
3.使用 SUSHI
SUSHI 既可以從命令行獨立訪問，也可以作為某些開發環境（即 EclipseIDE）的插件進行訪問。 開發人員可以通過將所需選項指定為擴展接口 Sushi.configure.ParametersModifier 的 Java 類來執行 SUSHI，然後使用此類選項啟動 SUSHI。 SUSHI 相關選項指定被測方法（或類）的簽名，程序的二進制文件和相關性以及 SUSHI 存儲生成的測試用例的輸出目錄。開發人員還可以指定選項以自定義要並行生成的 EvoSuite 進程池的大小，在路徑選擇階段要考慮的一組特定目標分支以及從基礎工具 JBSE 和 EvoSuite 接受的任何自定義選項，包括符號執行期間使用的不變量以及兩種工具的時間預算。SUSHI 生成可執行的 JUnit 測試用例。
SUSHI 在中間輸出上具有很高的可見性，從而可以監視測試生成過程的所有階段並檢查中間結果。中間輸出包括（i）符號執行跟蹤，每個都用 trace-id 標識，該跟蹤 ID 允許用戶使用 JBSE 重播該特定路徑的符號執行，（ii）路徑的覆蓋率信息，（iii）路徑選擇器選擇的路徑條件；（iv）路徑評估生成器構建的路徑條件距離評估器的 Java 代碼；以及（v）運行每個 EvoSuite 實例時生成的日誌文件。這些中間輸出對於調試 SUSHI 和檢查結果都是有價值的信息。中間輸出通過提供有關觀察到的行為的信息來支持調試，並通過例如支持對選定但未具體化的符號執行跟蹤的檢查來發現缺失的數據結構不變式，從而提高最終結果的實用性，並通過完善用於符號執行的不變式和前提條件來提高測試生成過程的有效性。
4.評估
我們通過為一組基準程序生成測試用例來評估 SUSHI，這些基準程序使用非平凡的數據結構作為輸入。我們將 SUSHI 生成的測試用例的分支覆蓋範圍與 JBSE，Seeker 和 EvoSuite 生成的測試用例的覆蓋範圍進行了比較。 JBSE 通過直接操作堆內存來生成測試用例。Seeker 利用靜態分析來構建方法序列，從而將符號執行器 Pex 引向未覆蓋的分支。 EvoSuite 利用到未覆蓋分支的距離作為適應度函數來實現基於搜索的測試。我們對配置有少量（部分）不變變量和全面（準確）不變變量的符號執行器進行了實驗。
表 1 報告了所生成測試套件的分支覆蓋範圍。我們將實驗設置，相應的複製程序包和結果的細粒度分析的所有詳細信息推薦給讀者。結果表明，SUSHI 在所有實驗中均不斷改善了符號執行的整體其他實施方式（JBSE 和 Seeker），並且針對 EvoSuite 形成了相關的互補分支，並具有部分和準確的不變性。此外，SUSHI 是生成測試套件的唯一工具，該套件可以揭示程序中的錯誤。結果還表明，不變量的準確性對 SUSHI 的有效性產生了顯著影響：與精確不變量相比，與部分不變量一起使用時，SUSHI 始終達到相等或更高的覆蓋率。我們計劃致力於不變量的自動生成，並進一步利用與 EvoSuite 的互補性來增強測試生成器的有效性。
表 1 使用 SUSHI 和其他同類工具的分支覆蓋率
5.結論
我們介紹了 SUSHI，這是一種新穎的 Java 開源測試生成器，專為具有複雜結構化輸入的程序量身定製。Java 程序基準測試的初步結果表明，SUSHI 有潛力改進自動測試生成器的技術水平。
致謝
本文由南京大學軟件學院 2020 級碩士生曹振飛翻譯轉述。
感謝國家重點研發計劃（2018YFB1003900）和國家自然科學基金（61832009，61932012）支持！
閱讀更多 慕測科技 的文章
