一種適用于路徑測試的新適應(yīng)值函數(shù)研究

王云霞

(江蘇省淮安體育運動學(xué)校， 江蘇 淮安 223001)

0 引言

軟件測試是保證軟件質(zhì)量的重要手段，但是隨著軟件規(guī)模和數(shù)量的增加，軟件測試的難度越來越大. 軟件測試是一項耗時耗力且昂貴的工作，據(jù)統(tǒng)計軟件測試成本占軟件開發(fā)成本的50%以上.自動化測試可以有效降低測試成本，提高測試質(zhì)量，而測試數(shù)據(jù)的好壞直接決定自動化測試的效果，因此如何生成高質(zhì)量的測試數(shù)據(jù)一直是研究人員的研究重點.1990年Korel等人把遺傳算法用于測試數(shù)據(jù)的生成[1]，之后越來越多的智能算法被用于測試數(shù)據(jù)的生成，并形成了軟件測試的新研究分支:基于搜索的軟件測試方法研究.該方法通過定義適應(yīng)值函數(shù)把測試數(shù)據(jù)生成問題轉(zhuǎn)化為優(yōu)化問題，因此適應(yīng)值函數(shù)的好壞直接影響了測試數(shù)據(jù)生成的效率和效果，決定了測試數(shù)據(jù)的質(zhì)量.本文以路徑測試為覆蓋準(zhǔn)則，針對路徑測試的特點提出一種的新的適應(yīng)值函數(shù)，以期獲得更高的測試數(shù)據(jù)生成效率.新的適應(yīng)值函數(shù)可以應(yīng)用于多種智能算法，如遺傳算法、模擬退火算法、爬山算法、粒子群優(yōu)化算法等.粒子群優(yōu)化算法(Particle Swarm Optimization, PSO)[2].由于具有概念簡單、容易實現(xiàn)、收斂速度快、參數(shù)設(shè)置少等特點，被廣泛應(yīng)用于進(jìn)化計算和智能優(yōu)化領(lǐng)域，受到學(xué)術(shù)界的廣泛重視.但其在測試數(shù)據(jù)自動生成方面的研究還有待進(jìn)一步加強和深入，因此，本文選擇粒子群優(yōu)化算法來檢驗新適應(yīng)值函數(shù)的效果.

1 預(yù)備知識

在使用智能算法解決測試數(shù)據(jù)生成問題的過程中，智能算法依據(jù)適應(yīng)值來對進(jìn)化過程進(jìn)行調(diào)整，適應(yīng)值函數(shù)的設(shè)計就成為求解問題的關(guān)鍵，因此，針對基于覆蓋的測試數(shù)據(jù)生成問題，學(xué)者們提出了很多種適應(yīng)值函數(shù)[1,3-5].典型的適應(yīng)值函數(shù)有分支距離、水平接近度以及二者的結(jié)合.

1.1 分支距離

分支距離被用來表示測試數(shù)據(jù)和目標(biāo)分支的偏離程度，其最早由Korel提出，其后Tracey對其進(jìn)行了改進(jìn).Tracey針對不同的關(guān)系謂詞設(shè)計了不同的目標(biāo)函數(shù)，具體如表1所示.當(dāng)分支關(guān)系謂詞為真的時候，目標(biāo)函數(shù)為零，否則為正數(shù).

1.2 水平接近度

水平接近度表示輸入變量x的執(zhí)行路徑偏離測試目標(biāo)的程度，記為Appr(x).假設(shè)輸入變量x執(zhí)行的路徑為p(x)，目標(biāo)路徑為p1，其節(jié)點個數(shù)表示為|p1|，比較p(x)與p1的各個節(jié)點，統(tǒng)計p(x)沒有穿越p1中節(jié)點的數(shù)量，記為α(x)，用其除以目標(biāo)路徑p1的節(jié)點個數(shù)|p1|即得到x的水平接近度，具體

表1 Tracey設(shè)計的針對不同謂詞的目標(biāo)函數(shù)[3]

計算如下：

(1)

1.3 結(jié)合分支距離和水平接近度的方法

很多學(xué)者采用結(jié)合分支距離和水平接近度的方法，Ahmed等人[4]采用水平接近度appr與分支距離dist之和作為個體適應(yīng)度. 即輸入變量x的適應(yīng)度采用下式計算

fit(x)=appr(x)+dist(x)

(2)

此外，謝曉園等[5]以路徑相似度為基礎(chǔ)來計算適應(yīng)值，輸入變量x的適應(yīng)度fit(x)的計算如下，

fit(x)=|p1|-similary(p1,p(x))

(3)

其中similary(p1,p(x))表示輸入變量x的執(zhí)行路徑和目標(biāo)路徑上相同節(jié)點的數(shù)量.

該方法用測試數(shù)據(jù)沒有遍歷目標(biāo)路徑上的分支節(jié)點數(shù)量作為適應(yīng)值，但這種計算方式忽略了目標(biāo)路徑上節(jié)點的有序性，認(rèn)為目標(biāo)路徑上所有的分支節(jié)點的權(quán)重都是相同的.

2 新適應(yīng)值函數(shù)的構(gòu)建

在Ahmed等人研究中，把路徑上每個分支節(jié)點的適應(yīng)值之和作為路徑的適應(yīng)值，沒有考慮到路徑中的分支節(jié)點是有序的. 路徑中的每個節(jié)點具有相同的權(quán)值，但是當(dāng)兩條路徑中分離節(jié)點(分離節(jié)點是指包含具有不同輸出結(jié)果的條件分支的節(jié)點)數(shù)目相同的時候，分離節(jié)點靠后，則兩條路徑越匹配，這兩條路徑之間的適應(yīng)值應(yīng)該更小. 因此為了符合路徑覆蓋的這種特征，提高智能算法生成測試數(shù)據(jù)的效率，重新定義了面向路徑的適應(yīng)值函數(shù)，具體如下：

2.1 分支距離的計算

Korel和Tracey提出的分支距離計算方法都是假設(shè)目標(biāo)分支為分支語句的真分支，如果目標(biāo)分支是條件語句的假分支，則需要對目標(biāo)函數(shù)進(jìn)行轉(zhuǎn)換.當(dāng)分別執(zhí)行同一個分支語句的不同分支的時候，必須修改插樁的目標(biāo)函數(shù)的計算方法，為了簡單起見，本文使用的目標(biāo)函數(shù)為,

(4)

對測試數(shù)據(jù)的執(zhí)行路徑和目標(biāo)路徑的分支節(jié)點進(jìn)行逐個比較，如果相同，則目標(biāo)函數(shù)設(shè)為0，如果不相同，則目標(biāo)函數(shù)設(shè)置為abs(a-b)+K，其中K表示一個大于0的整數(shù).這種方法的優(yōu)點是不需要考慮目標(biāo)分支的真假，使得同一個分支語句只需要插樁一次計算目標(biāo)函數(shù)的語句，降低了插樁的工作量.

2.2 水平接近度計算

為了體現(xiàn)路徑中節(jié)點的有序性，水平接近度app計算如下所示，

(5)

Px表示測試數(shù)據(jù)x的執(zhí)行路徑；app(Px,P)表示路徑Px和目標(biāo)路徑P之間的水平接近度；w是權(quán)值，為了擴大水平接近度之間的差異，本文中取值為目標(biāo)路徑長度L；L是目標(biāo)路徑中的節(jié)點數(shù)；N是路徑Px和目標(biāo)路徑P共有的節(jié)點的數(shù)量；i是分離節(jié)點在目標(biāo)路徑上的序號.

在新的定義中，測試數(shù)據(jù)的執(zhí)行路徑和目標(biāo)路徑上的相同節(jié)點越靠前，其值越小，表明兩條路徑越相似，測試數(shù)據(jù)偏離目標(biāo)路徑越小，反之則偏離越大.

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

為了評估新適應(yīng)值函數(shù)的效果，選擇了6個基準(zhǔn)程序進(jìn)行實驗,把新適應(yīng)值應(yīng)用于6個被測程序，并和Ahmed等人的適應(yīng)值函數(shù)進(jìn)行比較，以證明新適應(yīng)值函數(shù)的效果.

實驗環(huán)境為,CPU：Intel Core i3-4150 3.5GHZ；內(nèi)存：2 GB；Windows操作系統(tǒng)：Windows7 32位；編程語言：C語言；編程環(huán)境：Dev-C++ 5.11.

3.1 被測程序

被測程序的具體信息, 如表2所示：

表2 被測程序列表

3.2 參數(shù)設(shè)置

本文所用的PSO算法的參數(shù)如表3所示：

表3 PSO算法參數(shù)

3.3 實驗結(jié)果

實驗采用相同的原始種群，每個被測程序均運行算法100次，比較使用新舊不同適應(yīng)值的PSO算法需要的評估次數(shù)和運行時間，其中評估次數(shù)為100次運行的平均值，運行時間為100次運行所需時間的總和.實驗結(jié)果如表4所示：

表4 不同被測程序下不同適應(yīng)值函數(shù)的比較

由表4可以證明對于所選被測程序，本文提出的新的適應(yīng)值函數(shù)比Ahmed等人的適應(yīng)值函數(shù)能更有效地引導(dǎo)搜索接近目標(biāo)，具有更高的效率和更好的性能.以Insert-Sort程序為例，使用本文適應(yīng)值函數(shù)的方法所需的評估次數(shù)和運行時間分別是16843和4.125s，使用Ahmed適應(yīng)值函數(shù)的方法分別需要79847和18.086s，前者是后者的21.09%和22.81%.

4 結(jié)論

基于搜索的測試數(shù)據(jù)生成方法可以利用智能算法來生成測試數(shù)據(jù)，提高測試數(shù)據(jù)生成的自動化程度，提高了測試數(shù)據(jù)的生成效率.適應(yīng)值函數(shù)是把測試問題轉(zhuǎn)化為優(yōu)化問題的關(guān)鍵，其好壞直接決定了測試數(shù)據(jù)的質(zhì)量和效果.本文針對路徑測試的特點提出一種新的適應(yīng)值函數(shù)，該函數(shù)考慮了目標(biāo)路徑上分支節(jié)點的有序性，實驗證實該方法比Ahmed等人提出的方法有更好的效率和性能.