王云霞

(江蘇省淮安體育運(yùn)動(dòng)學(xué)校， 江蘇 淮安 223001)

0 引言

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

1 預(yù)備知識(shí)

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

1.1 分支距離

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

1.2 水平接近度

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

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

計(jì)算如下：

(1)

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

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

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

(2)

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

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

(3)

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

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

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

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

2.1 分支距離的計(jì)算

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

(4)

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

2.2 水平接近度計(jì)算

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

(5)

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

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

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

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

實(shí)驗(yàn)環(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 被測(cè)程序

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

表2 被測(cè)程序列表

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

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

表3 PSO算法參數(shù)

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

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

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

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

4 結(jié)論

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