鑒源論壇 · 觀模丨基于搜索的測(cè)試生成

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

蘇亭 華東師范大學(xué)軟件工程學(xué)院教授

版塊 |鑒源論壇 · 觀模

測(cè)試用例自動(dòng)生成，簡(jiǎn)稱測(cè)試生成（Test Generation），是指針對(duì)給定的被測(cè)對(duì)象，例如代碼單元、接口、系統(tǒng)等，使用相關(guān)算法計(jì)算測(cè)試用例集合的方法。測(cè)試生成的本質(zhì)是測(cè)試設(shè)計(jì)自動(dòng)化，無(wú)需研發(fā)人員參與測(cè)試，全部由計(jì)算機(jī)替代人類完成。測(cè)試生成方法與當(dāng)前在產(chǎn)業(yè)界中廣泛應(yīng)用的基于測(cè)試框架的自動(dòng)化測(cè)試技術(shù)有著本質(zhì)的差別。后者是測(cè)試執(zhí)行的自動(dòng)化，還需要依靠研發(fā)人員設(shè)計(jì)測(cè)試用例。

從對(duì)測(cè)試生成問(wèn)題進(jìn)行數(shù)學(xué)建模的角度看，當(dāng)前主流的測(cè)試生成方法可分為基于隨機(jī)的測(cè)試生成、基于符號(hào)執(zhí)行的測(cè)試生成、基于搜索的測(cè)試生成和基于模型檢測(cè)的測(cè)試生成?；谒阉鞯臏y(cè)試生成將測(cè)試生成問(wèn)題建模為最優(yōu)化問(wèn)題，其核心思想是針對(duì)期望達(dá)到的測(cè)試目標(biāo)，以相關(guān)目標(biāo)(成本)函數(shù)為指引，使用搜索算法在輸入域中尋找最優(yōu)解作為測(cè)試用例。

01概述

基于搜索的測(cè)試生成（Search-Based Software Testing, SBST）產(chǎn)生于1976年[1]，由于當(dāng)時(shí)測(cè)試生成領(lǐng)域關(guān)注于基于符號(hào)執(zhí)行的解決方案，因此，在其提出后的十幾年里，SBST并未得到重視和發(fā)展。直到1990年，研究人員Korel在其發(fā)表的論文中，提出SBST可以有效解決當(dāng)時(shí)在符號(hào)執(zhí)行方法中難于處理的復(fù)雜數(shù)據(jù)結(jié)構(gòu)符號(hào)化運(yùn)算的問(wèn)題[2]，SBST才被關(guān)注并得以深入研究，應(yīng)用于各種測(cè)試活動(dòng)中。

02方法說(shuō)明

結(jié)構(gòu)測(cè)試是面向代碼的測(cè)試方法之一，被廣泛應(yīng)用于工業(yè)實(shí)踐。其中，分支覆蓋是結(jié)構(gòu)測(cè)試中最為知名的測(cè)試覆蓋準(zhǔn)則之一。結(jié)構(gòu)測(cè)試是最早應(yīng)用SBST的測(cè)試活動(dòng)，也是產(chǎn)生SBST這一方法的源起點(diǎn)。因其奠基性地位，我們以Korel的SBST方法為切入點(diǎn)，說(shuō)明SBST的核心思想。

2.1 分支函數(shù)

Korel方法以滿足分支覆蓋為測(cè)試生成目標(biāo)。注意到，代碼中產(chǎn)生分支的循環(huán)判斷條件和選擇判斷條件等分支謂詞可以被轉(zhuǎn)換為符合其邏輯關(guān)系的一系列簡(jiǎn)單的關(guān)系表達(dá)式：

其中，E1和E2是算術(shù)表達(dá)式。我們將簡(jiǎn)單的關(guān)系表達(dá)式稱為分支表達(dá)式。為了覆蓋分支，可以采用最優(yōu)化方法計(jì)算使得分支表示式判定結(jié)果為真時(shí)的輸入數(shù)據(jù)。具體地說(shuō)，結(jié)合最優(yōu)化理論中成本函數(shù)的含義可知，以分支覆蓋為目標(biāo)的成本函數(shù)如果構(gòu)造為能夠衡量候選輸入與期望覆蓋分支之間的遠(yuǎn)近，那么，其中距離最近的輸入即為分支表達(dá)式的解?；诖?，Korel定義了分支函數(shù)：

不同形式的分支表達(dá)式有不同形式的分支函數(shù)，如表1所示。分支函數(shù)具有如下特性：

1）當(dāng)分支函數(shù)的值為正值（0如果rel是<）時(shí)，分支表達(dá)式不成立，該分支的取值為假；

2）當(dāng)分支函數(shù)的值為負(fù)值（0如果rel是<=）時(shí)，分支表達(dá)式成立，該分支的取值為真。

因此，滿足分支覆蓋的測(cè)試生成問(wèn)題就轉(zhuǎn)為找到使得分支函數(shù)值為負(fù)值的輸入。

表1 Korel定義的分支函數(shù)

2.2 測(cè)試生成過(guò)程

以分支覆蓋為測(cè)試目標(biāo)的SBST就是在分支函數(shù)指導(dǎo)下，搜索距離期望分支最近的輸入數(shù)據(jù)的過(guò)程，基本的搜索過(guò)程包含以下步驟：

1）生成被測(cè)代碼的控制流圖；

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

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

4）隨機(jī)生成一組輸入數(shù)據(jù)并執(zhí)行，記錄該輸入執(zhí)行時(shí)的路徑信息，將路徑信息與期望覆蓋的路徑進(jìn)行比對(duì)，找到兩者之間發(fā)生偏差的分支，為該分支構(gòu)造分支表達(dá)式；

5）逐一改變輸入變量的值進(jìn)行嘗試, 直至找到使得分支表達(dá)式的值為負(fù)（0如果rel是<=）時(shí)的輸入，即為所需的測(cè)試輸入數(shù)據(jù)；

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

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

圖1 計(jì)算覆蓋期望路徑的測(cè)試輸入數(shù)據(jù)示例

03主流方法

搜索最優(yōu)解的算法和成本函數(shù)的構(gòu)造是SBST的核心技術(shù)。常用的搜索最優(yōu)解的算法有爬山算法、模擬退火算法和遺傳算法。爬山算法、模擬退火屬于局部搜索策略，因?yàn)檫@兩種方法每次只考慮一個(gè)答案，且只在答案的受限毗鄰區(qū)附近移動(dòng)，遺傳算法則屬于全局搜索，同時(shí)考察搜索域中多個(gè)樣本點(diǎn)，是當(dāng)前SBST的主流。圖3給出了基于遺傳算法的SBST的主要流程。

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

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

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

04主要挑戰(zhàn)

環(huán)境交互問(wèn)題是面向代碼的SBST面臨的主要困難之一[3][7]。該問(wèn)題涉及代碼中包含與操作系統(tǒng)、文件系統(tǒng)、網(wǎng)絡(luò)系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)的相關(guān)交互。環(huán)境交互問(wèn)題通常采用測(cè)試替身的方案[8][9]。但是，由于代碼重構(gòu)和使用測(cè)試替身后會(huì)存在測(cè)試代碼執(zhí)行了被測(cè)代碼實(shí)際不可能執(zhí)行的路徑等情況，因而會(huì)產(chǎn)生誤報(bào)。對(duì)于誤報(bào)目前并沒(méi)有徹底的解決方案，只存在緩解的方法，一是規(guī)避導(dǎo)致誤報(bào)的原因，二是只在必要的時(shí)候使用測(cè)試替身技術(shù)[9]。

參考文獻(xiàn)：

[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.

審核編輯黃昊宇