基于天牛須搜索的軟件測(cè)試數(shù)據(jù)擴(kuò)增方法

王曙燕，胡乾花，孫家澤

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

0 概述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 MBAS 模型Fig.1 MBAS model

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

2.1 初始種群選擇

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

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

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

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

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

其中：ε是一個(gè)極小的常量以保證分母不為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)是一個(gè)隨機(jī)向量。在本文中，天牛的朝向?yàn)橛翼氈赶蜃箜殹Ｌ炫Ｍㄟ^不斷對(duì)比xr與xl附近位置的適應(yīng)度，向適應(yīng)度低的方向進(jìn)行移動(dòng)。

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

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

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

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

2.4 算法步驟

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

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

輸出覆蓋P′的測(cè)試用例集T′

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)置

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

表4 3 種方法擴(kuò)增測(cè)試數(shù)據(jù)的運(yùn)行時(shí)間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)路徑的測(cè)試數(shù)據(jù)。在表4 中，GA 方法的運(yùn)行時(shí)間為1.033 s，PSO 方法的運(yùn)行時(shí)間為0.481 s，而MBAS 方法的運(yùn)行時(shí)間僅為0.261 s。在迭代次數(shù)和運(yùn)行時(shí)間上MBAS 方法明顯優(yōu)于其他方法。

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

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

圖2 MBAS 方法相對(duì)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 方法。對(duì)于輸入實(shí)參個(gè)數(shù)少的被測(cè)程序Triangle 和NextDay，提升的平均擴(kuò)增效率分別為48.11%和44.33%，而對(duì)于Schedule 和Tcas，提升的平均擴(kuò)增效率僅為28.48%和28.42%，即測(cè)試數(shù)據(jù)處于低維空間時(shí)擴(kuò)增效率提升的更明顯。對(duì)于測(cè)試數(shù)據(jù)擴(kuò)增效率，MBAS 方法比GA 方法約平均提升了49.91%，比PSO 方法約平均提升了24.76%。

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

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

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

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

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

4 結(jié)束語(yǔ)

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