基于分組的蛻變測試的優化方法*

安韻涵 張海波

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

?

基于分組的蛻變測試的優化方法*

安韻涵 張海波

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

蛻變測試中的路徑覆蓋準則在實際應用中難以實現。文中利用路徑相似度對程序進行分組,先測試每個分組程序的相同路徑部分,在分組程序中利用分組程序的特殊性質尋找蛻變關系。以三角形面積計算程序為例進行分析,實驗結果表明：文中方法能有效提高測試的效率,相比于針對整體程序的蛻變關系,文中的蛻變關系尋找方法在程序錯誤檢測方面更加高效,且能更迅速定位到程序的錯誤路徑。

蛻變測試; 蛻變關系; 分組; 錯誤定位

Class Number TP311.5

1 引言

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

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

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

2 相關概念與原理

2.1 蛻變測試

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

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

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

2.2 分組

考慮兩條目標路徑Pi、Pj,Pi、Pj的節點數分別為ni、nj,從兩條路徑的開始節點開始比較,直到發現兩條路徑第一個不相同的節點為止,相同的節點數記為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]來衡量目標路徑之間的相似程度。若s(Pi,Pj)≥S0,說明路徑Pi、Pj相似度較高,可以分成一組,依照此方法對程序所有路徑進行分組。一般來說,程序分組的組數會小于程序的路徑數。

2.3 遺傳算法

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

圖1 遺傳算法步驟圖

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

3 基于分組的蛻變測試優化策略

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

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

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

4 實驗驗證

以三角形面積的計算程序為例驗證,程序首先判斷三角形是等腰三角形、等腰直角三角形、等邊三角形還是一般三角形,然后計算三角形面積。圖2是三角形面積計算程序的流程圖。

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

由表1可以發現,程序中很多路徑存在著相同的路徑部分,先按照第二節的分組策略進行分組。取閾值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沒有符合分組策略的,單獨記為E組。

圖2 三角形面積計算流程圖

路徑名實現功能路徑執行語句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

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

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

按照2.3節遺傳算法步驟在相同條件下進行5次試驗,得到的實驗數據如表2所示。

為了體現本文分組后應用遺傳算法的優越性,本文又在相同條件下與不分組的遺傳算法進行了對比實驗,得到實驗結果如表3所示。

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

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

表2 遺傳算法獲得測試用例代數

表3 分組與不分組條件下程序運行時間

根據三角形性質,文獻[5]中構造了6條蛻變關系MR1-MR6,作為對比,本文構造10條蛻變關系MR7-MR16,如表4所示。其中MR1-MR6是從程序整體出發尋找的蛻變關系,MR7-MR16是從程序分組后的子程序出發尋找的針對子程序的蛻變關系。

表4 蛻變關系

續表4。

MRiRbRbf蛻變區域測試盲區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:所有蛻變關系的定義域前提都是{(a,b,c)|(a+b>c)∧(b+c>a)∧(a+c>b)},即a、b、c可以構成三角形;2:MR1—MR3、MR4—MR6、MR8—MR10、MR11—MR13、MR14—MR16是對稱蛻變關系。

圖3 蛻變關系MR14構造原理

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

1) 第12、15、18節點對應的代碼中的“/2”替換成“*2”；

2) 將第25、31、37節點對應的代碼中的“/2”替換成“*2”；

3) 將第27、33、39節點對應的代碼中的“/4”替換成“/2”；

4) 將第41節點對應的代碼中的“/4”替換成“/2”；

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

在前面使用遺傳算法得到的測試用例中選擇測試用例,每個變異選擇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)

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

表5 各蛻變關系測試的MS值

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

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

5 結語

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

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

2) 考慮使用錯誤定位技術進一步提高錯誤定位的準確度。

3) 考慮程序的路徑變化,可以考慮使用狀態遷移圖來尋找蛻變關系進行更有效的蛻變測試。

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

[2] 董國偉,聶長海,徐寶文.基于程序路徑分析的有效蛻變測試[J].計算機學報,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] 董國偉,徐寶文,陳林,等.蛻變測試技術綜述[J].計算機科學與探索,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].清華大學學報:自然科學版,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] 王小平,曹立明.遺傳算法-理論、應用與軟件實現[M].西安:西安交通大學出版社,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