作者 |孫海英華東師范大學軟件工程學院講師

蘇亭 華東師范大學軟件工程學院教授

版塊 |鑒源論壇 · 觀模

測試用例自動生成，簡稱測試生成（Test Generation），是指針對給定的被測對象，例如代碼單元、接口、系統等，使用相關算法計算測試用例集合的方法。測試生成的本質是測試設計自動化，無需研發人員參與測試，全部由計算機替代人類完成。測試生成方法與當前在產業界中廣泛應用的基于測試框架的自動化測試技術有著本質的差別。后者是測試執行的自動化，還需要依靠研發人員設計測試用例。

從對測試生成問題進行數學建模的角度看，當前主流的測試生成方法可分為基于隨機的測試生成、基于符號執行的測試生成、基于搜索的測試生成和基于模型檢測的測試生成。基于搜索的測試生成將測試生成問題建模為最優化問題，其核心思想是針對期望達到的測試目標，以相關目標(成本)函數為指引，使用搜索算法在輸入域中尋找最優解作為測試用例。

01概述

基于搜索的測試生成（Search-Based Software Testing, SBST）產生于1976年[1]，由于當時測試生成領域關注于基于符號執行的解決方案，因此，在其提出后的十幾年里，SBST并未得到重視和發展。直到1990年，研究人員Korel在其發表的論文中，提出SBST可以有效解決當時在符號執行方法中難于處理的復雜數據結構符號化運算的問題[2]，SBST才被關注并得以深入研究，應用于各種測試活動中。

02方法說明

結構測試是面向代碼的測試方法之一，被廣泛應用于工業實踐。其中，分支覆蓋是結構測試中最為知名的測試覆蓋準則之一。結構測試是最早應用SBST的測試活動，也是產生SBST這一方法的源起點。因其奠基性地位，我們以Korel的SBST方法為切入點，說明SBST的核心思想。

2.1 分支函數

Korel方法以滿足分支覆蓋為測試生成目標。注意到，代碼中產生分支的循環判斷條件和選擇判斷條件等分支謂詞可以被轉換為符合其邏輯關系的一系列簡單的關系表達式：

其中，E1和E2是算術表達式。我們將簡單的關系表達式稱為分支表達式。為了覆蓋分支，可以采用最優化方法計算使得分支表示式判定結果為真時的輸入數據。具體地說，結合最優化理論中成本函數的含義可知，以分支覆蓋為目標的成本函數如果構造為能夠衡量候選輸入與期望覆蓋分支之間的遠近，那么，其中距離最近的輸入即為分支表達式的解。基于此，Korel定義了分支函數：

不同形式的分支表達式有不同形式的分支函數，如表1所示。分支函數具有如下特性：

1）當分支函數的值為正值（0如果rel是<）時，分支表達式不成立，該分支的取值為假；

2）當分支函數的值為負值（0如果rel是<=）時，分支表達式成立，該分支的取值為真。

因此，滿足分支覆蓋的測試生成問題就轉為找到使得分支函數值為負值的輸入。

表1 Korel定義的分支函數

2.2 測試生成過程

以分支覆蓋為測試目標的SBST就是在分支函數指導下，搜索距離期望分支最近的輸入數據的過程，基本的搜索過程包含以下步驟：

1）生成被測代碼的控制流圖；

2）計算滿足分支覆蓋的路徑集合；

3）任選一條期望覆蓋的路徑；

4）隨機生成一組輸入數據并執行，記錄該輸入執行時的路徑信息，將路徑信息與期望覆蓋的路徑進行比對，找到兩者之間發生偏差的分支，為該分支構造分支表達式；

5）逐一改變輸入變量的值進行嘗試, 直至找到使得分支表達式的值為負（0如果rel是<=）時的輸入，即為所需的測試輸入數據；

6）重復3)-5)，直到2)中所有路徑都被覆蓋。

為了說明SBST的主要思想，圖1給出了能夠覆蓋示例代碼中某條路徑(10-11-12-13)的測試輸入的搜索計算過程。需要說明的是，為了清晰簡便，示例采用了最基本的直接搜索算法，不包含對搜索過程的優化方法，也不包含計算測試預期結果(Test Oracle)的方法。現代的SBST方法采用的搜索優化算法和成本函數遠先進和復雜于示例中的方法。

圖1 計算覆蓋期望路徑的測試輸入數據示例

03主流方法

搜索最優解的算法和成本函數的構造是SBST的核心技術。常用的搜索最優解的算法有爬山算法、模擬退火算法和遺傳算法。爬山算法、模擬退火屬于局部搜索策略，因為這兩種方法每次只考慮一個答案，且只在答案的受限毗鄰區附近移動，遺傳算法則屬于全局搜索，同時考察搜索域中多個樣本點，是當前SBST的主流。圖3給出了基于遺傳算法的SBST的主要流程。

圖2 基于遺傳算法的SBST主要流程

基于遺傳算法的SBST首先使用隨機方法產生第一代群體，接著對該群體中的個體進行適應性評估，根據選擇策略從中挑選出優質個體集合作為親代用以產生下一代群體。隨后，在對親代進行交叉、變異和重新組合后產生了繼承親代優良基因的子代。之后，子代進入適應性評估，重復上述行為，直至找到最優解或者資源耗盡。在該過程中，用于評估候選者，引導搜索進入有前景的搜索域的適應度函數(fitness function)是關鍵技術。

適應度函數具有問題相關性。不同的問題需要定義不同的適應度函數。例如，在最壞執行時間測試時，適應度函數被定義為系統執行時間；在自動泊車控制系統中，適應度函數定義為泊車期間，車輛與某個碰撞點之間的最短距離。在結構測試時，適應度函數常被定義為滿足期望的覆蓋準則，例如分支覆蓋[3]。當前被廣泛使用的以滿足分支覆蓋為目的的適應度函數由研究人員Wegener提出[4]。該適應度函數有兩個數值指標，一是接近層級（Approach Level），另一個是分支距離（Branch Distance）。接近層級是指沒有被給出的輸入執行路徑覆蓋的與目標點相關的控制節點數量。與目標點越接近，接近層級越低。分支距離用于衡量輸入執行期望分支的鄰近程度，采用了改進的分支函數定義[5]。最終的適應度值是將分支距離歸一化并加上接近層級的結果。分支距離的歸一化方法有多種，研究人員Arcuri評估和討論了這些方法對搜索算法的影響[6]。

04主要挑戰

環境交互問題是面向代碼的SBST面臨的主要困難之一[3][7]。該問題涉及代碼中包含與操作系統、文件系統、網絡系統、數據庫系統的相關交互。環境交互問題通常采用測試替身的方案[8][9]。但是，由于代碼重構和使用測試替身后會存在測試代碼執行了被測代碼實際不可能執行的路徑等情況，因而會產生誤報。對于誤報目前并沒有徹底的解決方案，只存在緩解的方法，一是規避導致誤報的原因，二是只在必要的時候使用測試替身技術[9]。

參考文獻：

[1] W. Miller and D. Spooner, “Automatic generation of floatingpoint test data,” IEEE Transactions on Software Engineering, vol. 2, no. 3, pp. 223–226, 1976.

[2] B. Korel, “Automated software test data generation,” IEEE Transactions on Software Engineering, vol. 16, no. 8, pp. 870–879, 1990.

[3] Phil McMinn. Search-Based Software Testing: Past, Present and Future. Proceedings - 4th IEEE International Conference on Software Testing, Verification, and Validation Workshops, 153 – 163, 2011.

[4] J. Wegener, A. Baresel, and H. Sthamer, “Evolutionary test environment for automatic structural testing,” Information and Software Technology, vol. 43, no. 14, pp. 841–854, 2001.

[5] N. Tracey, J. Clark, K. Mander, and J. McDermid, “An automated framework for structural test-data generation,” in Proceedings of the International Conference on Automated Software Engineering. Hawaii, USA: IEEE Computer Society Press, 1998, pp. 285–288.

[6] A. Arcuri, “It does matter how you normalise the branch distance in search based software testing,” in Proceedings of the International Conference on Software Testing, Verification and Validation. IEEE, to appear, 2010.

[7] A. Panichella, "Beyond Unit-Testing in Search-Based Test Case Generation: Challenges and Opportunities," 2019 IEEE/ACM 12th International Workshop on Search-Based Software Testing (SBST), pp. 7-8, 2019.[

8] A. Arcuri, G. Fraser, and J. P. Galeotti. Automated unit test generation for classes with environment dependencies. In IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 79–90, 2014.

[9] A. Arcuri, G. Fraser and R. Just, "Private API Access and Functional Mocking in Automated Unit Test Generation," 2017 IEEE International Conference on Software Testing, Verification and Validation (ICST), pp. 126-137, 2017.

審核編輯黃昊宇