基于分組的蛻變測試的優(yōu)化方法*

安韻涵 張海波

(武漢數(shù)字工程研究所 武漢 430205)

?

基于分組的蛻變測試的優(yōu)化方法*

安韻涵 張海波

(武漢數(shù)字工程研究所 武漢 430205)

蛻變測試中的路徑覆蓋準(zhǔn)則在實(shí)際應(yīng)用中難以實(shí)現(xiàn)。文中利用路徑相似度對程序進(jìn)行分組,先測試每個分組程序的相同路徑部分,在分組程序中利用分組程序的特殊性質(zhì)尋找蛻變關(guān)系。以三角形面積計(jì)算程序?yàn)槔M(jìn)行分析,實(shí)驗(yàn)結(jié)果表明：文中方法能有效提高測試的效率,相比于針對整體程序的蛻變關(guān)系,文中的蛻變關(guān)系尋找方法在程序錯誤檢測方面更加高效,且能更迅速定位到程序的錯誤路徑。

蛻變測試; 蛻變關(guān)系; 分組; 錯誤定位

Class Number TP311.5

1 引言

隨著計(jì)算機(jī)應(yīng)用的發(fā)展,軟件質(zhì)量已經(jīng)越來越引起人們的重視,軟件測試作為保證軟件質(zhì)量的重要技術(shù)也逐漸成為人們關(guān)注的重點(diǎn)。傳統(tǒng)的軟件測試通過對比測試輸出與預(yù)期輸出來判斷軟件的質(zhì)量,但在傳統(tǒng)測試過程中經(jīng)常會碰到oracle問題[1]。為了解決oracle問題,Chen等在1998年提出蛻變測試的概念[2],該方法不需要構(gòu)造預(yù)期輸出,只需要通過檢查多次執(zhí)行程序的輸入輸出之間是否滿足蛻變關(guān)系來測試程序的質(zhì)量。

目前,蛻變測試研究主要集中在測試用例的生成、蛻變關(guān)系選取的策略以及蛻變測試的實(shí)用性方面,文獻(xiàn)[3]提出迭代蛻變測試來生成測試用例,文獻(xiàn)[4]提出路徑覆蓋準(zhǔn)則,但是這些方法在實(shí)際應(yīng)用中不夠高效,尤其在復(fù)雜程序中,難以找到符合全路徑覆蓋的測試用例集,即使找到符合條件的測試用例集,其開銷也是昂貴的。

本文提出將測試程序分組,利用程序路徑的相似度,將程序分成若干個分組程序,每個分組程序都有部分相同路徑,對分組程序的相同路徑部分先進(jìn)行測試,這樣可以減少程序重復(fù)路徑的重復(fù)測試與運(yùn)行。在分組程序中利用蛻變關(guān)系測試程序,可以利用分組程序部分具有而整體程序沒有的特殊性質(zhì)尋找蛻變關(guān)系,使蛻變關(guān)系更具有針對性。本文的方法在滿足路徑覆蓋要求下能明顯提高測試效率,并能在分組程序中利用分組程序的特殊性質(zhì),能找到更多且更具有針對性的蛻變關(guān)系,還能更迅速地定位到程序的錯誤路徑,縮小程序錯誤的定位范圍,從而降低錯誤修正的成本。

2 相關(guān)概念與原理

2.1 蛻變測試

蛻變關(guān)系[4]:P是計(jì)算一個函數(shù)f的一個程序,X1,X2，…，Xn是P的n個輸入變量,其對應(yīng)的輸出為f(X1),f(X2),…,f(Xn),這n個輸入變量之間滿足關(guān)系R,輸出之間滿足關(guān)系Rf。T1,T2，…,Tn是待測程序P的n個測試輸入值,滿足關(guān)系R,則其對應(yīng)的測試輸出是P(T1),P(T2),…,P(Tn),它們應(yīng)當(dāng)滿足關(guān)系Rf。即輸入R(T1,T2,…,Tn),輸出應(yīng)為Rf(P(T1),P(T2),…,P(Tn))。若滿足R(T1,T2，…,Tn)?Rf(P(T1),P(T2),…,P(Tn)),則稱(R,Rf)是待測程序P的蛻變關(guān)系MR。比如說,某一個程序是計(jì)算三角函數(shù)sin的值。sin函數(shù)具有性質(zhì)sin(x)=sin(x+2π)。為了驗(yàn)證程序的正確性,構(gòu)造測試輸入(X1,X2)滿足關(guān)系X1=X2+2π或者X2=X1+2π,然后分別運(yùn)行程序,檢查sin(X1)與sin(X2)是否相等即可,無須知道sin(X1)與sin(X2)的預(yù)期輸出。

測試盲區(qū)[5]:若MR是程序P滿足的蛻變關(guān)系,對任意輸入變量I∈δ?DR(MR),DR(MR)表示蛻變關(guān)系MR的定義域,無論將P置于何種變異,I與I滿足MR的衍生輸入FU(I,MR)以及它們對應(yīng)的輸出都滿足蛻變關(guān)系MR,則稱δ為MR的測試盲區(qū),記為Dbl(MR)。

蛻變關(guān)系的蛻變區(qū)域[6]:對某一蛻變關(guān)系MR,?I1∈δ?DR(MR),則DR(MR)-Dbl(MR)叫做MR的蛻變區(qū)域。

2.2 分組

考慮兩條目標(biāo)路徑Pi、Pj,Pi、Pj的節(jié)點(diǎn)數(shù)分別為ni、nj,從兩條路徑的開始節(jié)點(diǎn)開始比較,直到發(fā)現(xiàn)兩條路徑第一個不相同的節(jié)點(diǎn)為止,相同的節(jié)點(diǎn)數(shù)記為same(Pi,Pj)=nk,若兩條路徑完全相同,則same(Pi,Pj)=ni=nj。兩條路徑的相似度[7]如式(1)所示:

(1)

從公式可以看出,s(Pi,Pj)∈[0,1],且s(Pi,Pj)的值越大,說明路徑Pi、Pj之間的相似程度越大。給定一個閾值S0∈[0,1]來衡量目標(biāo)路徑之間的相似程度。若s(Pi,Pj)≥S0,說明路徑Pi、Pj相似度較高,可以分成一組,依照此方法對程序所有路徑進(jìn)行分組。一般來說,程序分組的組數(shù)會小于程序的路徑數(shù)。

2.3 遺傳算法

遺傳算法從問題可能解集一個種群開始計(jì)算。一個種群是通過基因編碼得到的一定數(shù)目的個體的集合。在每一代根據(jù)適應(yīng)度大小來挑選個體,然后通過交叉和變異得到下一代,即新的種群。如此循環(huán)執(zhí)行,直到滿足優(yōu)化準(zhǔn)則為止。遺傳算法的具體步驟如圖1所示[8～9]。

圖1 遺傳算法步驟圖

從理論上來說,使用遺傳算法產(chǎn)生測試用例集時,需要覆蓋的路徑越多,算法所需要的執(zhí)行時間越多[10],程序分組后,每一組子程序的相同路徑視為一條路徑,這大大減少了程序的路徑數(shù),從而大大減少了算法執(zhí)行時間。

3 基于分組的蛻變測試優(yōu)化策略

路徑覆蓋是測試覆蓋準(zhǔn)則中最嚴(yán)格的一種[6],現(xiàn)有的文獻(xiàn)中提出幾種蛻變測試的全路徑覆蓋準(zhǔn)則,但是這些準(zhǔn)則在實(shí)際應(yīng)用中實(shí)用性較差,在路徑覆蓋效率上較低。為了提高軟件測試時路徑覆蓋的效率,本文提出將程序利用程序相似度進(jìn)行分組,使得每小段程序包含的路徑較少或僅包含某一路徑的一部分,這樣就將一個大的路徑覆蓋問題分解成若干個小問題,從而降低路徑覆蓋的難度,提高路徑覆蓋的效率。假如程序P有N條路徑,根據(jù)第2節(jié)分組策略將P分成M組(一般來說M

程序分組后,每一組程序都有相同的部分路徑,首先對這部分路徑進(jìn)行測試,待相同部分的路徑測試結(jié)束后,再對后面部分的路徑進(jìn)行測試。這樣相同部分路徑的錯誤可以提前發(fā)現(xiàn),且錯誤的定位范圍也由整個程序減少到相同程序部分。因此也可以提高測試效率和程序錯誤定位的準(zhǔn)確度。

程序被分成若干個分組程序后,相比于整個程序而言,每一個分組程序涉及到的程序功能變得相對簡單,因此在整體程序利用蛻變關(guān)系以外可以利用分組程序的特殊性質(zhì)為分組程序?qū)ふ姨厥獾耐懽冴P(guān)系。由于分組程序的蛻變關(guān)系只針對該分組程序,這就使得在尋找蛻變關(guān)系時不僅可以利用滿足整體程序性質(zhì)來尋找蛻變關(guān)系,也可以利用僅滿足分組程序的特殊性質(zhì)來尋找蛻變關(guān)系,這樣給蛻變關(guān)系的選取提供了更多選擇的空間。同時利用分組程序的特殊性質(zhì)尋找的蛻變關(guān)系只涉及該分組程序部分的路徑,因此可以有效提高測試時程序錯誤的定位準(zhǔn)確度。

4 實(shí)驗(yàn)驗(yàn)證

以三角形面積的計(jì)算程序?yàn)槔?yàn)證,程序首先判斷三角形是等腰三角形、等腰直角三角形、等邊三角形還是一般三角形,然后計(jì)算三角形面積。圖2是三角形面積計(jì)算程序的流程圖。

該程序共有41個可執(zhí)行語句,由圖中41個節(jié)點(diǎn)表示,11條測試路徑。其中每條路徑的功能及其執(zhí)行的語句如表1所示。

由表1可以發(fā)現(xiàn),程序中很多路徑存在著相同的路徑部分,先按照第二節(jié)的分組策略進(jìn)行分組。取閾值S0=0.5。A1、A2、A3、A4這四條路徑的相同路徑是1,2,3,5,7,9,10,相似度s(A1,A2)=0.7>0.5,s(A1,A3)≈0.64>0.5,s(A1,A4)≈0.58>0.5將A1、A2、A3、A4四條路徑分為一組,記為A組。B1、B2這兩條路徑的相同路徑是1,2,3,4,5,7,9,22,23,相似度s(B1,B2)≈0.82>0.5,將B1、B2兩條路徑分為一組,記為B組。C1、C2這兩條路徑的相同路徑是1,2,3,5,7,9,22,28,29,相似度s(C1,C2)=0.75>0.5,將C1、C2兩條路徑分為一組,記為C組。D1、D2這兩條路徑的相同路徑是1,2,3,5,7,8,9,22,28,34,35,相似度s(D1,D2)≈0.85>0.5,將D1、D2兩條路徑分為一組,記為D組。最后一條路徑1,2,3,4,5,6,7,8,9,22,28,34,40,41沒有符合分組策略的,單獨(dú)記為E組。

圖2 三角形面積計(jì)算流程圖

路徑名實(shí)現(xiàn)功能路徑執(zhí)行語句A1a、b邊為直角邊的一般直角三角形1.2.3.5.7.9.10.11.12A2a、c邊為直角邊的一般直角三角形1.2.3.5.7.9.10.13.14.15A3b、c邊為直角邊的一般直角三角形1.2.3.5.7.9.10.13.16.17.18A4一般三角形1.2.3.5.7.9.10.13.16.19.20.21B1a、b邊為直角邊的等腰直角三角形1.2.3.4.5.7.9.22.23.24.25B2a、b邊為腰的等腰三角形1.2.3.4.5.7.9.22.23.26.27C1a、c邊為直角邊的等腰直角三角形1.2.3.5.6.7.9.22.28.29.30.31C2a、c邊為腰的等腰三角形1.2.3.5.6.7.9.22.28.29.32.33D1b、c邊為直角邊的等腰直角三角形1.2.3.5.7.8.9.22.28.34.35.36.37D2b、c邊為腰的等腰三角形1.2.3.5.7.8.9.22.28.34.35.38.39E等邊三角形1.2.3.4.5.6.7.8.9.22.28.34.40.41

分析程序可以知道,程序開始部分是對三角形進(jìn)行分類,即上面每組路徑的相同部分。在這一部分利用遺傳算法生成測試用例,這不僅可以高效實(shí)現(xiàn)這部分的路徑覆蓋,而且還為后面部分的路徑生成更有效的測試用例集。為了有效檢測這部分程序,需要對這部分程序進(jìn)行部分修改,在A組相同程序后添加輸出打印語句System.out.println(“一般三角形”),在B組相同程序后添加輸出打印語句System.out.println(“a=b的等腰三角形”),在C組相同程序后添加輸出打印語句System.out.println(“a=c的等腰三角形”),在D組相同程序后添加輸出打印語句System.out.println(“b=c的等腰三角形”)。為了將得到的測試用例進(jìn)行分組以便更好地被后面的測試?yán)?同時為了后面分組程序在尋找蛻變關(guān)系時更好地顯現(xiàn)本文方法的優(yōu)勢,于是只將E組的1.2.3.4.5.6.7.8.9.22.28.34.40這部分路徑提前進(jìn)行測試。

選擇程序值域?yàn)閇0,255],種群大小為100,個體參數(shù)采用二進(jìn)制編碼方式[11],因此每個個體參數(shù)可以用8位二進(jìn)制表示,級聯(lián)后每個個體用長為24位的(0-1)串表示。設(shè)置選擇、交叉、變異概率分別為0.3、0.8、0.05,最大進(jìn)化代數(shù)為300。

按照2.3節(jié)遺傳算法步驟在相同條件下進(jìn)行5次試驗(yàn),得到的實(shí)驗(yàn)數(shù)據(jù)如表2所示。

為了體現(xiàn)本文分組后應(yīng)用遺傳算法的優(yōu)越性,本文又在相同條件下與不分組的遺傳算法進(jìn)行了對比實(shí)驗(yàn),得到實(shí)驗(yàn)結(jié)果如表3所示。

由表3可以看出,相比于不分組采用遺傳算法

獲得測試用例并測試程序所用的時間,本文方法所用的時間明顯要少。本文采用的程序是一個非常小的程序,相信在復(fù)雜程序中本文方法的優(yōu)越性會更突出。

表2 遺傳算法獲得測試用例代數(shù)

表3 分組與不分組條件下程序運(yùn)行時間

根據(jù)三角形性質(zhì),文獻(xiàn)[5]中構(gòu)造了6條蛻變關(guān)系MR1-MR6,作為對比,本文構(gòu)造10條蛻變關(guān)系MR7-MR16,如表4所示。其中MR1-MR6是從程序整體出發(fā)尋找的蛻變關(guān)系,MR7-MR16是從程序分組后的子程序出發(fā)尋找的針對子程序的蛻變關(guān)系。

表4 蛻變關(guān)系

續(xù)表4。

MRiRbRbf蛻變區(qū)域測試盲區(qū)MR9(a',b',c')=(a+1,b2+2a+2c+2,c+1)area(a',b',c')=area(a,b,c)+a+1/2{(a,b,c)|a=c∧a2+c2=b2}MR10(a',b',c')=(a2+2b+2c+2,b+1,c+1)area(a',b',c')=area(a,b,c)+b+1/2{(a,b,c)|b=c∧b2+c2=a2}MR11(a',b',c')=(a+1,b+1,c2+2a+2b+2)area(a',b',c')=area(a,b,c)+(a+b)/2+1/2{(a,b,c)|a2+b2=c2}MR12(a',b',c')=(a+1,b2+2a+2c+2,c+1)area(a',b',c')=area(a,b,c)+(a+c)/2+1/2{(a,b,c)|a2+c2=b2}MR13(a',b',c')=(a2+2b+2c+2,b+1,c+1)area(a',b',c')=area(a,b,c)+(b+c)/2+12{(a,b,c)|b2+c2=a2}MR14(a',b',c')=(4a2-3c24,4b2-3c24,c)area(a',b',c')=2*area(a,b,c){(a,b,c)|a=b}MR15(a',b',c')=(4a2-3b24,b,4c2-3b24)area(a',b',c')=2*area(a,b,c){(a,b,c)|a=c}MR16(a',b',c')=(a,4b2-3a24,4c2-3a24)area(a',b',c')=2*area(a,b,c){(a,b,c)|b=c}注:1:所有蛻變關(guān)系的定義域前提都是{(a,b,c)|(a+b>c)∧(b+c>a)∧(a+c>b)},即a、b、c可以構(gòu)成三角形;2:MR1—MR3、MR4—MR6、MR8—MR10、MR11—MR13、MR14—MR16是對稱蛻變關(guān)系。

圖3 蛻變關(guān)系MR14構(gòu)造原理

為了能夠判斷子程序蛻變關(guān)系的有效性,把5條變異[12]分別置入三角形面積計(jì)算程序中,5條變異分別為：

1) 第12、15、18節(jié)點(diǎn)對應(yīng)的代碼中的“/2”替換成“*2”；

2) 將第25、31、37節(jié)點(diǎn)對應(yīng)的代碼中的“/2”替換成“*2”；

3) 將第27、33、39節(jié)點(diǎn)對應(yīng)的代碼中的“/4”替換成“/2”；

4) 將第41節(jié)點(diǎn)對應(yīng)的代碼中的“/4”替換成“/2”；

5) 將第12、15、18、25、31、37節(jié)點(diǎn)對應(yīng)的代碼中的“/2”刪除,同時將第27、33、39、41行代碼中的“/4”替換成“/2”(即將所有非一般三角形的面積擴(kuò)大一倍)；

在前面使用遺傳算法得到的測試用例中選擇測試用例,每個變異選擇25個用例,其中等邊三角形2個,等腰三角形6個(a=b、a=c、b=c各兩個),等腰直角三角形6個(a=b、a=c、b=c各兩個),一般直角三角形6個(a、b；a、c；b、c為直角邊各兩個),一般三角形5個,以此保證每條路徑都被覆蓋到。

在變異分析中,用變異檢測率MS[7]來度量測試用例集TC檢測變異的能力,MS定義如式(2)所示。

(2)

分析所有蛻變關(guān)系可知,MR1-MR3、MR4-MR6、MR8-MR10、MR11-MR13、MR14-MR16是對稱蛻變關(guān)系,因此將所有蛻變關(guān)系分成6組。測試得到的值如表5所示。

表5 各蛻變關(guān)系測試的MS值

從表5中可以看出,MR1-MR3這一組蛻變關(guān)系的檢測能力非常差,所有的測試用例都通過了。MR4-MR6的檢測能力稍好一些,但是相對來說仍然較弱,并且即使檢測出變異體,也無法定位變異在程序中的位置。而MR7、MR8-MR10、MR11-MR13、MR14-MR16四組蛻變關(guān)系分別涉及等邊三角形、等腰直角三角形、一般直角三角形和一般等腰三角形,其相關(guān)的測試用例數(shù)分別為2個、6個、6個和6個,均檢測出變異,且變異檢測率為100%,且每一個測試用例檢測出的變異體均可定位到程序所在的路徑部分,提高了程序的變異定位的準(zhǔn)確度。

程序相同的部分在每一條路徑測試中都會被測試到,這樣大大增加了測試的時間,因此考慮將這些路徑的相同部分先進(jìn)行測試。在測試路徑相同部分的程序后再測試每條路徑的后面部分,這樣不僅可以提高測試效率,而且可以提高程序錯誤定位的準(zhǔn)確度。

5 結(jié)語

本文提出利用程序相似度將程序分成若干個分組程序,先測試分組程序的相同路徑部分。利用遺傳算法生成測試用例集,由于程序相同路徑部分完全可以視為同一條路徑,相當(dāng)于減少了程序測試的路徑數(shù),因此大大提高了整個程序測試過程中的測試效率。在分組程序中,不僅能利用整體程序具有的性質(zhì)尋找蛻變關(guān)系,還能利用分組程序具有而整體程序沒有的特殊性質(zhì)找到更多的蛻變關(guān)系。程序分組后,分組程序的測試只涉及該分組程序,因此可以更迅速地定位到程序的錯誤,降低程序錯誤修正的成本。在今后還需對本文的工作做進(jìn)一步的研究與改進(jìn)：

1) 考慮到含有大量復(fù)雜循環(huán)體以及非線性復(fù)合謂詞條件的程序,本文的分組策略不夠高效,可以考慮采用聚類分組的方法來解決。

2) 考慮使用錯誤定位技術(shù)進(jìn)一步提高錯誤定位的準(zhǔn)確度。

3) 考慮程序的路徑變化,可以考慮使用狀態(tài)遷移圖來尋找蛻變關(guān)系進(jìn)行更有效的蛻變測試。

[1] Weyuker E J. On Testing Non-Testable Programs[J]. Computer Journal,1982,25(4):465-470.

[2] 董國偉,聶長海,徐寶文.基于程序路徑分析的有效蛻變測試[J].計(jì)算機(jī)學(xué)報,2009,32(5):1002-1013. DONG Gguowei, NEI Changhai, XU Baowen. Effective transformation test based on program path analysis[J]. Chinese Journal of Computers,2009,32(5):1002-1013.

[3] Wu P .Iterative metamorphic testing[C]//Proceedings of the 29th Annual International Computer Software and Applications Conference(COMPSAC’ 05).Edinburgh, UK,2005:19-24.

[4] CHEN T Y,CHEUNG S C,YIU S M.Metamorphic testing: A new approach for generating next test cases,HKUST-CS98- 01[D].Hong Kong: Hong Kong University of Science and Technology,Department of Computer Science and Engineering,1998.

[5] 董國偉,徐寶文,陳林,等.蛻變測試技術(shù)綜述[J].計(jì)算機(jī)科學(xué)與探索,2009,3(2):130-14. DONG Guowei, XU Baowen, CHEN Lin. Review of metamorphic testing technology[J]. Journal of Frontiers of Computer Science & Technology,2009,3(2):130-14.

[6] 董國偉,郭濤,張普含,等.基于路徑分析和迭代蛻變測試的Bug檢測[J].清華大學(xué)學(xué)報:自然科學(xué)版,2014(1):60-67. DONG Guowei, GUO Tao, ZHANG Puhan, etc. Bug detection based on path analysis and iterative transformation test [J] . Journal of Tsinghua University(Science and Technology,2014(1):60-67.

[7] Yao X, Gong D. Genetic algorithm-based test data generation for multiple paths via individual sharing[J]. Computational Intelligence & Neuroscience, 2014,2014.

[8] Jorgensen P C. Software Testing: A Craftsman’s Approach[M]. CRC Press, Inc. 1995.

[9] 王小平,曹立明.遺傳算法-理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社,2002:14. WANG Xiaoping, CAO Liming. Genetic algorithm theory, application and software implementation[M]. Xi’an: Xi’an Jiaotong University Press,2002:14.

[10] Peng W U, Shi X C, Tang J J, et al. Metamorphic Testing and Special Case Testing: A Case Study[J]. Journal of Software,2005,16(7):1210-1220.[11] Hamlet D. Software Quality, Software Process, and Software Testing[J]. Advances in Computers,1995,41(8):191-229.

[12] Gong D, Zhang W, Yao X. Evolutionary generation of test data for many paths coverage based on grouping[J]. Journal of Systems & Software,2011,84(12):2222-2233.

Optimization Method of Metamorphic Testing Based on Grouping

AN Yunhan ZHANG Haibo

(Wuhan Digital Engineering Institute, Wuhan 430205)

In practical application, path-coverage criterion in metamorphic testing is difficult to achieve. This paper uses the path similarity to group which can reduce the repetition rate testing and running of the redundant path, uses the special nature of the group to find metamorphic relation which can find more metamorphic relations in the group. Triangle area calculation program as an example for analysis. The results show that the method in this paper can improve the efficiency of the test more effectively. Compared to the metamorphic relation pointing at the overall procedure, the ways of finding metamorphic relation in this paper are more efficient in the mistake detection and quicker location in the wrong path of the procedure.

metamorphic testing, metamorphic relation, grouping, fault localization

2016年5月17日,

2016年7月1日

安韻涵,女,碩士研究生,研究方向：軟件測試。張海波,男,博士,研究員,研究方向：軟件測試、信息安全。

TP311.5

10.3969/j.issn.1672-9722.2016.11.025