基于天牛須搜索的軟件測試數據擴增方法

王曙燕，胡乾花，孫家澤

（西安郵電大學 計算機學院，西安 710121）

0 概述

回歸測試是指測試人員對演化后的新版本程序重新進行測試，確認修改部分沒有影響未修改部分的功能［1］。測試用例集擴增強調利用原測試數據信息和程序演化信息輔助生成新的測試數據，以期提高生成效率并獲得更具針對性的測試用例［2］。

測試數據擴增概念由HARDER 等［3］提出，之后國內外研究人員對其進行大量研究并取得一定的研究成果。吳川等［4］提出基于分析路徑相關性來建立回歸測試數據生成模型，雖然目標路徑的覆蓋率較高，但對于不同的被測程序，需要根據程序的特征設置不同的控制參數。YOO 等［5］將測試數據分為失效和未失效兩類，且僅修改程序中的簡單運算符。XU等［6］研究表明使用已有測試數據可以提高測試數據集擴增效率。QI 等［7］利用符號執行技術和狀態傳遞樹CEPT［8］確保測試數據可以覆蓋修改后程序的變化節點，JIANG 等［9］通過分析軟件信息圖擴增測試數據，但QI 和JIANG 等的研究均未利用原測試數據集。鞏敦衛等［10］根據與目標路徑的相似度選取初始種群，采用遺傳算法生成測試數據，雖然合理地利用了原測試用例，但是并未將程序的演化信息與交叉算子相結合。殷鵬川等［11］利用原測試用例跳過重疊初始子路徑，對后續目標子路徑進行concolic 測試，但該方法受限于約數求解器。王曙燕等［12］利用路徑相似度識別新增路徑并選取初始種群，采用自適應粒子群算法生成測試用例，但該方法不適用于大規模軟件測試。吳川等［13］基于路徑與測試數據之間的關系，決定需要擴增的測試數據，但該方法未利用原測試用例。XU 等［14］研究表明已有測試用例的使用方式對回歸測試的效率有較大的影響。王曙燕等［15］從方法級別和語句級別提取覆蓋目標，將原測試用例和正交種群作為初始種群，雖然利用了原測試數據，但并沒有對其進行選擇，數據冗余性較大。對于上述研究存在的問題，需要一種與程序演化信息密切結合、能充分利用原測試用例且適用于較多程序的測試用例擴增算法，以在降低回歸測試成本的同時提高擴增效率。

基于符號執行的軟件測試方法受限于本身的高復雜度，難以適用于大規模軟件測試，同時由于影響回歸測試效果的主要因素是測試用例生成算法，而元啟發式算法能有效提高測試用例擴增效率［16-17］。天牛須搜索（Beetle Antennae Search，BAS）算法是一種新型的元啟發式算法［18-19］，具有參數少且魯棒性強等優點，自提出以來受到了學術界的廣泛應用并取得了一系列的成果，但在測試用例擴增應用中鮮有公開的文獻。本文在文獻［15］研究的基礎上，提出基于天牛須搜索算法的軟件測試數據擴增方法MBAS。結合軟件演化信息，基于原測試用例集的覆蓋信息選取部分測試用例作為初始的進化種群，根據分支距離和分支嵌套深度設計適應度函數，采用改進的天牛須搜索算法對有序目標方法集進行測試數據的擴增，以期提高原測試用例的利用率和程序擴增的效率。

1 有序目標方法集獲取

利用已有的測試數據執行新舊程序，根據程序覆蓋與執行信息得到需測試的目標方法集合。獲取程序的方法調用圖并將其用鄰接矩陣存儲，計算方法執行概率和權值，得到方法包含錯誤的影響度，獲取優先覆蓋的目標方法。

1.1 程序覆蓋與執行信息獲取

一個程序包括m個方法M={f1,f2,…,fm}，對程序執行測試用例后，得到的方法覆蓋信息與執行信息用矩陣A表示如下：

在矩陣A中，測試數據為t1,t2,…,tn，tij(1≤i≤m,1≤j≤n)表示測試用例tj對于fi方法的覆蓋情況，如果tj覆蓋了fi，則tij=1，否則tij=0。tj的執行結果為u=[u1j,u2j,…,uij,…,umj]-1，uij表 示tj對fi的執行結果，如果成功，則uij=1，否則uij=0。

測試用例在新舊版本程序中的方法覆蓋與執行情況表示為A和A′，通過對同一測試用例的覆蓋信息和執行信息做異或運算，得到目標方法集C=

1.2 目標方法集排序

獲取程序的方法調用圖，方法調用圖是一個有向圖，其中每個節點都附加一個權值。建立方法調用圖的鄰接矩陣，若存在調用關系，則矩陣元素為1，否則為0。對矩陣進行遍歷，統計每個方法可調用的方法個數。

1.2.1 目標方法包含錯誤的概率

通過目標方法在新舊版本程序上的執行概率得到其包含錯誤的概率。假定方法集相互獨立，初始方法f1的執行概 率P(f1)=1，若fi調用fa…fb等wi個方法，則fa的執行概率P(fa)表示如下：

若被調用方法的執行概率不為0 時，則疊加概率值，直至計算至最后一個節點。計算新舊程序中目標方法ck(1≤k≤m)的執行概率P(ck)和P′(ck)，目標方法ck包含錯誤的概率P″(ck)表示如下：

1.2.2 目標方法包含錯誤的影響度

將方法調用圖中所有非葉子節點的權值N(fi)初始化為0，所有葉子節點的權值為1。若fi調用fa…fb等wi個方法，則fi的 方法權值N(fi)表示如下：

計算新程序中目標方法ck的權值N(ck)，將權值和包含錯誤的概率進行乘積得到目標方法包含錯誤的影響度S(ck)：

將S(ck)值按遞減的順序進行排列，得到有序目標方法集C'，并對其依次生成測試數據。

2 測試數據集擴增

基于天牛須搜索算法的軟件測試數據擴增方法可分為預處理和測試用例擴增兩個模塊，如圖1所示。

圖1 MBAS 模型Fig.1 MBAS model

預處理模塊主要包括程序靜態分析和獲取目標方法集，抽取方法調用圖，使用原測試用例執行新舊程序，得到程序執行信息，獲得目標方法集并對目標方法進行排序。測試用例擴增模塊首先根據方法覆蓋信息從原測試用例集中選取部分用例作為初始種群，再通過改進的天牛須搜索算法的位置更新公式引導天牛向最優解進化，最終生成覆蓋目標路徑的測試數據。

2.1 初始種群選擇

將原測試用例集在新程序中執行，得到程序執行信息矩陣，對于目標方法ck，將所有覆蓋該方法的測試用例作為擴增的初始測試數據，若無測試數據覆蓋該方法，則將在舊程序中覆蓋該方法的用例添加至初始種群。

2.2 適應度函數

使用代碼分析工具Soot 得到C'中每個方法的控制流程圖，根據路徑的分支節點數獲得需要覆蓋的路徑集，在目標路徑的每個分支節點前插入分支距離函數Hp，表示第p個分支的分支距離。分支距離是一種常見的啟發式方法，用于指導輸入數據進行搜索，以解決分支的邏輯謂詞中的約束問題［20］。通過分支嵌套深度調整不同分支節點權重：

其中：Dp為通過程序流程圖靜態分析得到分支節點p的嵌套深度；q為被測程序針對給定目標路徑的分支判定數目。通過上式計算出Gp為分支節點p的權重。

根據分支距離函數和分支嵌套深度設計適應度函數：

其中：ε是一個極小的常量以保證分母不為0，在此處設置ε=0.01。若F(x)的值越小，則表示越接近目標，因此目標路徑覆蓋問題可轉換為適應度函數最小化問題。

2.3 改進的天牛須搜索算法

在D維解空間中，天牛位置x=(x1,x2,…,xD)，其左右兩觸須的位置為：

其中：x為當前位置；l為天牛質心與觸須間的距離；xl為左須的位置；xr為右須的位置；d為天牛的隨機朝向；r=rands(n,5)是一個隨機向量。在本文中，天牛的朝向為右須指向左須。天牛通過不斷對比xr與xl附近位置的適應度，向適應度低的方向進行移動。

當前位置天牛根據規則移動到下一個位置：

其中：s為可變步長；F(xl)為左須的氣味強度，氣味強度即適應度函數；F(xr)為右須的氣味強度，若F（xl）>F(xr)，Sign(·)取1，天 牛在d的方向 上以步 長s移 動，反之，則向d的反方向移動。

在本文中，使用Metropolis準則更新天牛的下一步位置，若新位置x′的適應值小于x的適應值，則接受x′為當前位置，反之，則以隨機概率接受x′。步長遵循：其中：F為當前個體的適應值；Fave為去掉最大最小適應值后剩余個體適應值的平均數，稱為假平均適應值；Fmax為最大適應值；Fmin為最小適應值。若F≤Fave，則此時個體的性能良好，減小步長，反之，增大步長。

若達到最大迭代次數或測試數據覆蓋目標路徑，則輸出測試數據，選取C′中下一個目標方法，將已測試目標方法成功的測試用例和根據程序執行信息選取的測試用例作為初始測試數據，繼續進行擴增，直至所有目標方法都被測試。

2.4 算法步驟

基于天牛須搜索的測試數據擴增算法的具體步驟如下：

輸入舊版本程序P的測試用例集T，新版本程序P′

輸出覆蓋P′的測試用例集T′

步驟1抽取方法調用圖，使用原測試用例集運行新舊程序，獲得程序的執行信息，得到需覆蓋的目標方法集。

步驟2對目標方法集進行排序，逐個選取目標路徑，進行分支函數的插樁。

步驟3根據程序執行信息選取部分測試用例。

步驟4判斷是否滿足終止條件（測試用例覆蓋目標路徑或達到最大迭代次數），若滿足，則轉步驟9。

步驟5計算測試用例的適應值，確定全局最大適應值、最小適應值和假平均適應值。

步驟6利用位置更新方程預測天牛的位置。

步驟7根據Metropolis 準則更新天牛下一步位置。

步驟8更新步長，轉步驟4。

步驟9算法結束，輸出測試數據集。

3 實驗與結果分析

3.1 實驗設置

為驗證MBAS 方法的數據擴增效果，選用西門子工業程序集中的Schedule 和Tcas、三角形判定程序Triangle 以及基準程序NextDay 作為實驗中的測試程序，這些程序被廣泛應用于驗證不同測試方法的有效性［21］。被測程序的基本信息如表1 所示。

表1 被測程序的基本信息Table 1 Basic information of the programs under test

在實驗中應用Eclipse IDE for Eclipse Committers（Mars.2）編程實現天牛須算法和測試程序。針對不同程序運行算法30 次，取實驗結果的均值進行比較。實驗對比方法為基于遺傳算法（Genetic Algorithm，GA）的測試數據擴增方法（下文簡稱為GA方法）和基于粒子群優化（Particle Swarm Optimization，PSO）算法的測試數據擴增方法（下文簡稱為PSO 方法），具體參數設置如表2 所示。

表2 對比方法參數設置Table 2 Parameters setting of the comparison methods

3.2 實驗結果

實驗選擇GA 和PSO 方法與本文MBAS 方法進行比較，在相同的環境下記錄每種方法的迭代次數和運行時間，并計算實驗數據的均值和標準差，實驗結果如表3 和表4 所示。

表3 3 種方法擴增測試數據的迭代次數Table 3 The number of iteration of three methods to augment test data

表4 3 種方法擴增測試數據的運行時間Table 4 The running time of three methods to augment test data s

以程序NextDay 為例，在表3 中，GA 方法需迭代39.0 次，PSO 方 法需迭代27.1 次，MBAS 方法僅需迭代17.8 次即可生成覆蓋目標路徑的測試數據。在表4 中，GA 方法的運行時間為1.033 s，PSO 方法的運行時間為0.481 s，而MBAS 方法的運行時間僅為0.261 s。在迭代次數和運行時間上MBAS 方法明顯優于其他方法。

對實驗結果中的迭代次數進行計算：

其中：v(A|B)為方法A相對于方法B提高的效率；e表示方法的迭代次數。MBAS 方法相對GA 和PSO 方法的擴增效率提升結果如圖2 所示。

圖2 MBAS 方法相對GA 和PSO 方法的擴增效率提升結果Fig.2 Improvement results of augmentation efficiency for MBAS method compared to GA and PSO method

在圖2 中，MBAS 方法的擴增效率均高于GA 和PSO 方法。對于輸入實參個數少的被測程序Triangle 和NextDay，提升的平均擴增效率分別為48.11%和44.33%，而對于Schedule 和Tcas，提升的平均擴增效率僅為28.48%和28.42%，即測試數據處于低維空間時擴增效率提升的更明顯。對于測試數據擴增效率，MBAS 方法比GA 方法約平均提升了49.91%，比PSO 方法約平均提升了24.76%。

根據表3 和表4 中的標準差，對于被測程序，MBAS 方法迭代次數的平均標準差為4.15，均小于GA 方法的平均標準差25.62 和PSO 方法的平均標準差7.85；MBAS 方法運行時間的平均標準差為0.163，均小于GA 方法的平均標準差0.511 和PSO 方法的平均標準差0.197，即MBAS 方法具有更好的穩定性。

通過測試數據的迭代次數和目標路徑覆蓋率來評價不同回歸測試數據擴增方法的能力，以程序Triangle 為例，3 種方法的目標路徑覆蓋率如圖3所示。

圖3 3 種方法的目標路徑覆蓋率對比結果Fig.3 Comparison results of target path coverage of three methods

由圖3 可知，MBAS 方法的折線位置位于GA 和PSO 方法的上方，當迭代次數相同時，MBAS 方法對目標路徑的覆蓋率最大；當目標路徑覆蓋率相同時，以100%為例，MBAS 方法所需的迭代次數最少，優先完成路徑覆蓋，即MBAS 方法在迭代次數和目標路徑覆蓋率方面均具有一定的性能優勢。

通過上述分析可知，對于被測程序，MBAS 方法可以有效利用原測試集，快速演化生成覆蓋目標路徑的測試集。

4 結束語

本文提出一種基于天牛須搜索的軟件測試數據擴增方法MBAS，采用目標方法覆蓋信息分析需要測試的方法，通過計算目標方法包含錯誤的影響度，對包含錯誤影響度大的目標方法進行優先分析生成測試數據集，并利用原測試數據集的目標方法覆蓋信息來衡量測試數據的優劣，最終使用天牛須搜索算法演化測試用例使其覆蓋目標路徑。通過對多個程序進行測試，并將該方法與基于GA 和PSO 的測試數據擴增方法進行比較，實驗結果表明，MBAS 方法在測試數據的擴增效率和穩定性上均具有明顯的性能優勢。但由于天牛須搜索算法未能較好解決高維空間中解的收斂速度較慢的問題，因此后續將對此做進一步改進，提升MBAS 方法在高維空間中的擴增效率。