王曙燕，胡乾花，孫家澤

（西安郵電大學(xué) 計算機(jī)學(xué)院，西安 710121）

0 概述

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

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

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

1 有序目標(biāo)方法集獲取

利用已有的測試數(shù)據(jù)執(zhí)行新舊程序，根據(jù)程序覆蓋與執(zhí)行信息得到需測試的目標(biāo)方法集合。獲取程序的方法調(diào)用圖并將其用鄰接矩陣存儲，計算方法執(zhí)行概率和權(quán)值，得到方法包含錯誤的影響度，獲取優(yōu)先覆蓋的目標(biāo)方法。

1.1 程序覆蓋與執(zhí)行信息獲取

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

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

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

1.2 目標(biāo)方法集排序

獲取程序的方法調(diào)用圖，方法調(diào)用圖是一個有向圖，其中每個節(jié)點都附加一個權(quán)值。建立方法調(diào)用圖的鄰接矩陣，若存在調(diào)用關(guān)系，則矩陣元素為1，否則為0。對矩陣進(jìn)行遍歷，統(tǒng)計每個方法可調(diào)用的方法個數(shù)。

1.2.1 目標(biāo)方法包含錯誤的概率

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

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

1.2.2 目標(biāo)方法包含錯誤的影響度

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

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

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

2 測試數(shù)據(jù)集擴(kuò)增

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

圖1 MBAS 模型Fig.1 MBAS model

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

2.1 初始種群選擇

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

2.2 適應(yīng)度函數(shù)

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

其中：Dp為通過程序流程圖靜態(tài)分析得到分支節(jié)點p的嵌套深度；q為被測程序針對給定目標(biāo)路徑的分支判定數(shù)目。通過上式計算出Gp為分支節(jié)點p的權(quán)重。

根據(jù)分支距離函數(shù)和分支嵌套深度設(shè)計適應(yīng)度函數(shù)：

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

2.3 改進(jìn)的天牛須搜索算法

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

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

當(dāng)前位置天牛根據(jù)規(guī)則移動到下一個位置：

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

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

若達(dá)到最大迭代次數(shù)或測試數(shù)據(jù)覆蓋目標(biāo)路徑，則輸出測試數(shù)據(jù)，選取C′中下一個目標(biāo)方法，將已測試目標(biāo)方法成功的測試用例和根據(jù)程序執(zhí)行信息選取的測試用例作為初始測試數(shù)據(jù)，繼續(xù)進(jìn)行擴(kuò)增，直至所有目標(biāo)方法都被測試。

2.4 算法步驟

基于天牛須搜索的測試數(shù)據(jù)擴(kuò)增算法的具體步驟如下：

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

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

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

步驟2對目標(biāo)方法集進(jìn)行排序，逐個選取目標(biāo)路徑，進(jìn)行分支函數(shù)的插樁。

步驟3根據(jù)程序執(zhí)行信息選取部分測試用例。

步驟4判斷是否滿足終止條件（測試用例覆蓋目標(biāo)路徑或達(dá)到最大迭代次數(shù)），若滿足，則轉(zhuǎn)步驟9。

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

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

步驟7根據(jù)Metropolis 準(zhǔn)則更新天牛下一步位置。

步驟8更新步長，轉(zhuǎn)步驟4。

步驟9算法結(jié)束，輸出測試數(shù)據(jù)集。

3 實驗與結(jié)果分析

3.1 實驗設(shè)置

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

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

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

表2 對比方法參數(shù)設(shè)置Table 2 Parameters setting of the comparison methods

3.2 實驗結(jié)果

實驗選擇GA 和PSO 方法與本文MBAS 方法進(jìn)行比較，在相同的環(huán)境下記錄每種方法的迭代次數(shù)和運行時間，并計算實驗數(shù)據(jù)的均值和標(biāo)準(zhǔn)差，實驗結(jié)果如表3 和表4 所示。

表3 3 種方法擴(kuò)增測試數(shù)據(jù)的迭代次數(shù)Table 3 The number of iteration of three methods to augment test data

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

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

對實驗結(jié)果中的迭代次數(shù)進(jìn)行計算：

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

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

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

根據(jù)表3 和表4 中的標(biāo)準(zhǔn)差，對于被測程序，MBAS 方法迭代次數(shù)的平均標(biāo)準(zhǔn)差為4.15，均小于GA 方法的平均標(biāo)準(zhǔn)差25.62 和PSO 方法的平均標(biāo)準(zhǔn)差7.85；MBAS 方法運行時間的平均標(biāo)準(zhǔn)差為0.163，均小于GA 方法的平均標(biāo)準(zhǔn)差0.511 和PSO 方法的平均標(biāo)準(zhǔn)差0.197，即MBAS 方法具有更好的穩(wěn)定性。

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

圖3 3 種方法的目標(biāo)路徑覆蓋率對比結(jié)果Fig.3 Comparison results of target path coverage of three methods

由圖3 可知，MBAS 方法的折線位置位于GA 和PSO 方法的上方，當(dāng)?shù)螖?shù)相同時，MBAS 方法對目標(biāo)路徑的覆蓋率最大；當(dāng)目標(biāo)路徑覆蓋率相同時，以100%為例，MBAS 方法所需的迭代次數(shù)最少，優(yōu)先完成路徑覆蓋，即MBAS 方法在迭代次數(shù)和目標(biāo)路徑覆蓋率方面均具有一定的性能優(yōu)勢。

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

4 結(jié)束語

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