杜慶峰， 馮國堯， 錢浩然

(同濟大學 軟件學院，上海 201804)

回歸測試路徑優(yōu)先級模型

杜慶峰， 馮國堯， 錢浩然

(同濟大學 軟件學院，上海 201804)

為了提高回歸測試的效率，根據(jù)組件間的調用圖，找出可能的路徑片段，通過測試用例的執(zhí)行歷史進而計算出路徑片段的覆蓋指數(shù)，最后對覆蓋指數(shù)進行排序，提出了一種測試用例的優(yōu)先級模型.用此模型可以高效地進行回歸測試，及時發(fā)現(xiàn)程序中的錯誤.

回歸測試； 路徑片段； 優(yōu)先級模型； 覆蓋指標

隨著信息技術的迅猛發(fā)展，軟件已經(jīng)被應用于各個領域,同時軟件的競爭也日益激烈,保證軟件的質量就變得尤為重要.軟件測試作為軟件質量的可靠保障，在軟件的整個生命周期中占有越來越重要的地位.軟件的調試、升級與維護往往需要更改部分代碼，為了驗證修改后的程序是否引發(fā)新的問題或對未修改的部分是否造成影響，就需要頻繁地對軟件進行回歸測試.

回歸測試可以發(fā)生在軟件測試的任何一個級別，由于在軟件測試中隨著軟件組件的增加、組件的修改或組件的刪除需要對其做大量的回歸測試.回歸測試可以使用之前的測試用例集，也可以針對具體情形對新增的功能編寫新的測試用例，刪除部分冗余的測試用例.那么，如何提高測試用例的使用效率、如何優(yōu)先使用以往的測試用例是測試用例優(yōu)先級技術的關注重點.測試用例優(yōu)先級技術認為不同測試用例對于測試目標的完成有著不同的貢獻程度，為了能夠更快地達成測試目標，有必要將不同的測試用例進行比較和排序，然后優(yōu)先執(zhí)行相對重要的測試用例.

Wong等[1]最先提出了在回歸測試選擇技術的基礎上對測試用例集進行最小化或優(yōu)先級處理，通過判定累計覆蓋率等問題對測試用例進行排序.在此之后，越來越多的學者將測試用例的優(yōu)先級技術運用到回歸測試當中.Kim等[2]研究了綜合考慮各種測試歷史的優(yōu)先級技術.Jeffrey等[3]研究了基于切片的測試用例優(yōu)先級技術.

因此，針對如何選擇和使用測試用例，應該結合該測試用例的歷史覆蓋情況設定其優(yōu)先級,從而縮短測試的時間，減少所產(chǎn)生的開銷.

1 問題提出

Rothermel等[4]將測試用例優(yōu)先級問題抽象為尋找測試用例全排列中的最優(yōu)集合問題.給定測試用例集T，T的全排列集合PT，從PT到實數(shù)的函數(shù)f，求一個T′∈PT，使得?T″,T″∈PT且T″≠T′且f(T′)≥f(T″) .換句話說,如果一組測試用例按照特定的順序執(zhí)行,那么該組測試用例使得目標函數(shù)f有更高的“適宜度”值.一般認為,更高的適宜度值代表更好的測試用例優(yōu)先級排序.

在理想情況下,測試用例應該盡可能早地最大化錯誤檢測能力(即，提高錯誤檢測的速率),因此，優(yōu)化測試用例集，通過調整測試用例順序[5]，可以最大化提高錯誤檢測能力以便更早地向程序員提供反饋信息，從而使他們更早地定位和修復錯誤.

例如，某被測程序中測試用例和對應的檢錯情況如表1所示,表示測試用例t是否覆蓋了程序缺陷f,其中“√”表示t覆蓋了f.在回歸測試中如果按照t1～t7的順序執(zhí)行,那么直到執(zhí)行測試用例t3的時候才能檢測到第1個錯誤，同時只有執(zhí)行到t7的時候才能檢測到所有的錯誤缺陷.如果根據(jù)t3，t4，t5，t7,t6，t1，t2的執(zhí)行順序執(zhí)行測試用例，那么就能更快地發(fā)現(xiàn)程序中的錯誤，同時能更快地檢測出所有的錯誤，這能大大減少測試成本.

表1 測試用例檢錯表示例Tab.1 Error detection table of test case

在現(xiàn)階段，回歸測試時主要是根據(jù)需求手動選取測試用例順序，其效率比較低下;或者是僅僅根據(jù)測試用例對路徑的覆蓋率來決定測試用例的優(yōu)先級，其嚴謹性有待考量.針對以上的不足，在進行路徑片段覆蓋指數(shù)分析的基礎上,研究測試用例優(yōu)先級的模型.

綜上，若構建一個基于路徑片段覆蓋指數(shù)的優(yōu)先級模型，需解決以下的問題：①對于路徑片段和測試用例的關系進行分析，并得出各個路徑片段的詳細歷史覆蓋信息.②根據(jù)路徑片段的歷史覆蓋信息，得出各個路徑片段的覆蓋指數(shù)，生成路徑片段的遞減集，并分析遞減集和測試用例優(yōu)先級模型的關系.

2 回歸測試優(yōu)先級模型

2.1 相關定義

回歸測試優(yōu)先級模型主要是對組件調用路徑進行分析，組件調用路徑中包含函數(shù)結點(也稱之為組件結點)和路徑片段.通過分析路徑片段的覆蓋指數(shù)，進一步得出相關測試用例的優(yōu)先級.為了方便對函數(shù)調用路徑和對路徑片段的覆蓋進行分析，現(xiàn)作定義如下.

定義1 組件調用路徑圖.假設在軟件測試中每一個組件是一個結點，對于組件之間相互的調用，可以得到一個從程序入口結點到出口結點的有向調用圖,可以表示為P={N1,N2,…,Ni,…,Nn}，其中Ni為組件結點.Ni和Ni+1的相鄰關系表示Ni+1調用了Ni，則稱P為組件調用路徑圖.圖1表示從結點1開始到結點9結束的組件調用路徑圖.

圖1 組件調用路徑示例Fig.1 Example of component call path diagram

定義2 路徑片段和路徑片段集.假設在組件的調用路徑圖中，若組件結點Ni到結點Nj存在一條連通的路徑，則這條路徑稱為Ni到Nj的路徑片段，路徑片段中結點數(shù)目不定.組件調用路徑圖中的所有路徑片段構成路徑片段集,可以表示為Sm={s1,s2,…,si,…,sm},其中Sm為路徑片段集，si為路徑片段.

定義3 路徑片段覆蓋指數(shù).在執(zhí)行一個測試用例集后，每一個測試用例可能會覆蓋若干個路徑片段，同時一個路徑片段也可能被若干測試用例覆蓋，假設si為其中一個路徑片段，那么覆蓋si所對應的測試用例數(shù)目之和稱為si的覆蓋指數(shù)，記為Ci,m，其中i表示第i個路徑片段，m為所有的路徑片段數(shù)目.

定義4 路徑片段遞減集.假設在執(zhí)行測試用例集之后，根據(jù)路徑片段的覆蓋指數(shù)大小得出一個路徑片段集合Sd={sd1,sd2,…,sdi,…,sdm},其滿足Cd1,m>Cd2,m>…>Cdm,m，則稱為路徑片段遞減集.

2.2 優(yōu)先級模型構建

2.2.1 模型理論

回歸測試路徑優(yōu)先級模型是將功能看成一個組件結點的形式.根據(jù)組件結點之間的相互調用關系，將各個組件進行集成，得到組件調用路徑圖.圖1就是一個組件調用路徑圖.

在組件的調用路徑圖中，結點之間的連通形成很多路徑片段，其中每條路徑片段包含若干結點.例如圖1中結點2，5，7就構成了1個3個結點的路徑片段.通過執(zhí)行歷史測試用例集，進而可分析各路徑片段的覆蓋指數(shù),其中路徑片段和測試用例滿足二元關系(如表2)可表示G(T,S)nm矩陣形式.

表2 測試用例集和路徑片段滿足的二元關系實例Tab.2 Examples of binary relations between test suite and path segments

該模型根據(jù)組件調用路徑圖，結合圖論思想，遍歷出路徑片段的數(shù)目.根據(jù)測試用例集和路徑片段的關系，計算出每個路徑片段的覆蓋指數(shù).對所有路徑片段的覆蓋指數(shù)進行比較，得出一個路徑片段遞減集.通過分析路徑片段遞減集中覆蓋指數(shù)高的路徑片段所對應的測試用例得出測試用例的優(yōu)先級模型,同時在之后的回歸測試中采用動態(tài)調整策略研究補充測試用例的優(yōu)先級模型.對路徑片段覆蓋指數(shù)低的測試用例適當刪除，同時添加覆蓋指數(shù)高的測試用例，以不斷完善模型.

2.2.2 模型的數(shù)學表達

在進行回歸測試之前，需要滿足執(zhí)行完測試用例集時，組件調用路徑圖中的所有路徑片段都是被覆蓋的，即要求覆蓋程序中所有可能的路徑[6].這樣以確保測試用例集是完整的、有效的.

假設測試用例集為T={t1,t2,…,tn}，路徑片段集是S={s1,s2,…,sm}，在回歸測試之前對于每個sj∈S，在T中至少有一個測試用例ti能夠覆蓋sj.同時測試用例集T與路徑片段集S滿足二元關系，用符號可表示為矩陣G(T,S)nm.假設測試用例ti能覆蓋路徑片段sj(1≤i≤n,1≤j≤m)，則G(ti,sj)=1,否則G(ti,sj)=0.當?ti使S中的任意一個路徑片段sj使得G(ti,sj)=1,i∈[1,n],則此測試用例集是有效的.

假設實際中的路徑片段為m個,那么路徑片段sj(1≤j≤m)的覆蓋指數(shù)可以表示為Cj,m,其中路徑片段和測試用例滿足二元關系G(T,S)nm=(gij).

此矩陣的C1,m=2,C2,m=3,C3,m=1,…,Cm,m=1.

在根據(jù)以上矩陣G(T,S)nm得出每一個路徑片段的Ci,m值時，對所有路徑片段Ci,m值進行排序和統(tǒng)計，得出一個Ci,m遞減的路徑片段集合.那么在回歸測試中，需要優(yōu)先對Ci,m值高的路徑片段設計測試用例或者從已有的測試用例集中選取Ci,m值高的路徑片段的對應測試用例，提高其優(yōu)先級別.假設一個路徑片段遞減集合是{s2,s3,s1,s4}，那么優(yōu)先賦予s2更高的優(yōu)先級，那么覆蓋s2的測試用例對應的級別較高；假設覆蓋s2的測試用例有若干條，那么需要比較這些測試用例是否覆蓋其他高覆蓋指數(shù)的路徑片段，若一條測試t1用例除了覆蓋s2還覆蓋了一個s3，而另一個測試用例t2覆蓋了s2和s1，則t1測試用例優(yōu)先級高于t2.

在路徑片段遞減集合中存在相同覆蓋指數(shù)的路徑片段si，sj，若si∈sj，則有效路徑片段為sij=si∪sj=sj.若si?sj，則需分析覆蓋si，sj的測試用例是否覆蓋其他路徑片段，依次比較覆蓋指數(shù)，確定優(yōu)先級.若2個測試用例覆蓋的所有片段的覆蓋指數(shù)都是相同的，此時需要確定最高覆蓋指數(shù)路徑片段的si和sj組件數(shù)目.比如si(n1,n2,…,nx),sj(n1,n2,…,ny)，若x>y，則表示si片段對程序的貢獻大，因此相應的優(yōu)先級較高.

3 模型算法及驗證

3.1 算法思想

(1) 根據(jù)分析相關程序的集成，確定程序中組件的個數(shù)，進而分析函數(shù)組件之間的調用關系，生成組件調用路徑圖.假設組件調用路徑圖中有m個組件，根據(jù)組件的個數(shù)以及特定的邏輯調用關系得出該組件調用圖中的實際路徑片段.

(3) 根據(jù)以上二維數(shù)組可以得出每一個路徑片段的Ci,m值，對所有路徑片段Ci,m值進行排序和統(tǒng)計，得出一個Ci,m遞減的路徑片段集合.在回歸測試中，優(yōu)先對Ci,m值高的路徑片段設計測試用例或者從已有的測試用例集中選取Ci,m值高的路徑片段的對應測試用例，提高其優(yōu)先級別.

(4) 對排序好后的路徑片段進行分析.排序后Ci,m值高的路徑片段表示被T覆蓋的次數(shù)多,因此在進行回歸測試的時候，賦予覆蓋該路徑片段的測試用例更高的優(yōu)先級.這樣便能在很短的時間內優(yōu)先測試出函數(shù)間的關鍵路徑.當Ci,m值相同的時候，存在以下情況：

若路徑片段si和路徑片段sj對應的覆蓋指數(shù)相同，且si是sj的子片段，那么有效的路徑片段為sj.在該情況下只需要考慮路徑片段sj的情況，而無需再考慮路徑片段si的情況.

若路徑片段si和路徑片段sj對應的覆蓋指數(shù)相同，但是si不是sj的子片段，那么需要對覆蓋該路徑片段的若干測試用例進行進一步比較.假設C4,m=C7,m=10，那么就需要對覆蓋s4,s7片段的測試用例進行比較.假設有10條測試用例覆蓋s4,s7,則比較這10條測試用例是否覆蓋其他Ci,m值高(比10略低)的片段，按照這10條測試用例對其他路徑片段的覆蓋情況，對應Ci,m值高的測試用例優(yōu)先級高.最后如果2條測試用例覆蓋的所有片段的覆蓋指數(shù)都是相同的，那么需要確定最高路徑片段的組件數(shù)目，組件數(shù)目多則對程序的貢獻大，因此相應的優(yōu)先級較高.

3.2 算法邏輯

為了驗證以上模型算法，將偽代碼整理如下.

Procedure Test-case

Input :T, Integrated program

Output: T of the high priority

Begin

generate component call path graph

get the segment path from component call path graph

build a matrixG(T,S)n*m

if T coversi

A[i][j]=1

else

A[i][j]=0 /*storage relationship between test cases and path segments*/

calculate the number of ‘1’ in the matrix column namedCi,m

sortCi,mvalue

ifCi,mis the max

give thetihigher priority

else ifCi,m=Cj,m

Ifsi∪sj=sj

just concernsj

else

for(i=n,j=n;i>0,j>0;i--,j--)

ifCi,m>Cj,m

give thetihigher priority thantj

else ifCi,m=Cj,m

compare the n number of thesiandsj

ifni>nj

give thetihigher priority thantj

all T have priority and put it into a list

End

3.3 算法復雜度分析

3.3.1 時間復雜度

3.3.2 空間復雜度

根據(jù)組件調用路徑圖中所得的路徑片段的空間復雜度為O(n)構造矩陣的空間復雜度為O(n2)，排序空間復雜度為O(1)，故此模型的空間復雜度為：O(n)+O(n2)≈O(n2).

3.4 算法驗證

3.4.1 優(yōu)先級模型的測評標準

軟件測試的目的是設計出高質量的測試用例來盡可能多地檢測出被測軟件內部存在的缺陷.在設計測試用例優(yōu)先級的評測指標時，需要體現(xiàn)出測試用例的缺陷檢測速率.

APFD[7-9]為缺陷檢測加權平均百分比.假設測試用例集T中包含n個測試用例，該測試用例集合能夠檢測出的錯誤集合為F，其中F包含m個錯誤，則測試用例集T的一個順序集T′的APFD值可以用如下公式表達：

式中:Ri為順序集T′中第1個檢測出錯誤i的測試用例在T中的位置.?APFD的取值范圍在0～1之間.在不同的測試用例順序集中，?APFD越高表示對應測試用例優(yōu)先級集的檢測錯誤的效率相對越高.

例如測試用例檢測表如表1所示,那么若按照t1～t7的順序執(zhí)行測試用例，則該執(zhí)行順序集的?APFD為

若根據(jù)t3，t4，t5，t7,t6，t1，t2的順序執(zhí)行,那么該執(zhí)行順序的?APFD為

由以上可知，按照上述測試用例的優(yōu)先級順序執(zhí)行測試可以提高錯誤的檢測效率.

3.4.2 試驗設計與分析

試驗采用的測試工具是selenium IDE軟件.通過搭建selenium測試環(huán)境進行相關測試.本次試驗的數(shù)據(jù)是時態(tài)GIS(Geographic Information System)系統(tǒng)中的部分數(shù)據(jù).首先根據(jù)項目畫出組件調用路徑圖.其結果如圖2所示.

圖2 組件調用路徑Fig.2 Component call path diagram

通過圖論的遍歷可知不重復的有效路徑片段數(shù)目是33條.在該試驗中，設計了10條測試用例.測試項編號為SVG_TC_001.該測試用例表中的測試用例覆蓋了全部路徑，同時對重點功能設計相應多的測試用例，用以滿足測試用例的設計條件.執(zhí)行完所有測試用例之后，經(jīng)過算法分析統(tǒng)計可知：0→3路徑片段被測試用例覆蓋了8次，為最高覆蓋指數(shù)的路徑片段，0→3→5 和3→5的路徑片段覆蓋指數(shù)為4次，但是根據(jù)算法sij=si∪sj=sj可知，只需要考慮0→3→5的路徑片段覆蓋指數(shù)，而無需再考慮路徑3→5的覆蓋指數(shù).同理0→3→4→9，0→3→4，3→4，3→4→9，4→9路徑片段覆蓋指數(shù)都為3次，其只需考慮0→3→4→9的覆蓋指數(shù).根據(jù)算法依次可知0→3→5→8→9的路徑片段覆蓋指數(shù)為3次，0→1→2→9的覆蓋指數(shù)為2次，0→3→6→9和0→3→5→7→9的覆蓋指數(shù)為1次.測試發(fā)現(xiàn)編輯地圖和比對地圖2個功能模塊存在缺陷.然后對該項目添加若干功能進行相關回歸測試.在對項目進行相關修改后的組件調用圖如圖3所示.

圖3 修改后的組件調用路徑Fig.3 Modified component call path diagram

根據(jù)回歸測試路徑優(yōu)先級算法模型可知：路徑0→3→5→8→9對應的測試用例是優(yōu)先級最高的測試用例，因此在對修改后的項目組件調用圖進行回歸測試時應該根據(jù)0→3→5→8→9對應的測試用例做部分修改，然后優(yōu)先進行測試.因此在回歸測試中應該優(yōu)先使用0→10→11→3→5→8→9 和0→11→3→5→8→9路徑所對應的測試用例.同理其次的測試順序應該依照算法得出的回歸測試優(yōu)先級從高到低的順序進行選取.依次進行測試后可以得出表3.

表3 測試用例檢錯表Tab.3 Error table of test case

由此可得初始階段的?APFD為0.2，新階段的?APFD為0.6.因此在進行回歸測試時使用測試用例優(yōu)先級選取的測試用例可以大大提高檢錯效率.

3.4.3 試驗結果

在回歸測試中，測試用例優(yōu)先級技術旨在找到一種高效的測試用例執(zhí)行序列，按照測試用例序列的執(zhí)行順序進行測試能提高錯誤的檢錯效率.表4是對其他5組程序進行試驗得出的數(shù)據(jù)，能充分反映優(yōu)先級模型的檢錯效率.其中數(shù)據(jù)來源于缺陷測試項目組和時態(tài)GIS系統(tǒng).

圖4是表4反映的初始的?APFD和排序后?APFD的對比圖，能直觀反映在執(zhí)行模型算法前后缺陷檢測加權平均百分比的變化.

圖4 模型執(zhí)行前后APFD值對比Fig.4 APFD comparison chart before and after model execution

通過試驗分析可知：使用路徑優(yōu)先級模型排序后的測試用例的APFD值要高于未排序測試用例的APFD值，且兩者有較大的差值，說明了提出的測試用例優(yōu)先級模型能明顯提高測試的缺陷的檢錯效率;同時隨著軟件規(guī)模的增加，測試用例優(yōu)先級模型的缺陷檢測率提升也愈發(fā)穩(wěn)定.

4 結語

傳統(tǒng)的基于覆蓋的優(yōu)先級技術是根據(jù)每條測試用例的覆蓋率進行排序然后來設定其測試用例的優(yōu)先級，而本文是根據(jù)若干測試用例所對應的每一條路徑片段的覆蓋指數(shù)確定重點需要測試的路徑片段，再根據(jù)此路徑片段反過來尋找對應的測試用例，進而賦予其對應的優(yōu)先級.

由于該優(yōu)先級模型是根據(jù)路徑覆蓋指數(shù)生成的，故能更好地反映測試用例的執(zhí)行記錄，從而發(fā)現(xiàn)系統(tǒng)中重點測試片段.其對應的測試用例執(zhí)行順序能明顯地提高項目回歸測試的效率.

[1] Wong W E, Horgan J R, London S,etal. A study of effective regression testing in practice[C]∥The Eighth International Symposium on Software Reliability Engineering.[S.l.]: IEEE Computer Society, 1997:264-274.

[2] Kim J M, Porter A. A history-based test prioritization technique for regression testing in resource constrained environments[C]∥International Conference on Software Engineering. New York:[s.n.], 2002:119-129.

[3] Jeffrey D, Gupta N. Test case prioritization using relevant slices[C]∥30th Annual International Computer Software and Applications Conference[S.l.]: IEEE, 2006: 411-420.

[4] Rothermel G, Untch R H, Chu C,etal. Prioritizing test cases for regression testing[J]. Acm Sigsoft Software Engineering Notes, 2000, 25(5):102.

[5] 安金霞，王國慶，李樹芳，等.基于多維度覆蓋率的軟件測試動態(tài)評價方法[J].軟件學報，2010,21(9):2135.

AN Jinxia, WANG Guoqing, LI Shufang,etal.Dynamic evaluation method based multi-dimensional test coverage for software testing[J].Journal of Software,2010,21(9):2135.

[6] 杜慶峰. 高級軟件測試技術[M].北京：清華大學出版社，2011.

DU Qingfeng.Advanced software testing techology[M].Beijing:Tsinghua University Press,2011.

[7] 李華瑩，胡兢玉.回歸測試用例優(yōu)先級排序技術研究[J].計算機仿真，2013,30(10):298.

LI Huaying, HU Jingyu.Research on test case prioritization for regression testing[J].Computerised Simulation, 2013,30(10):298.

[8] 陳翔，陳繼紅，鞠小林，等.回歸測試中測試用例優(yōu)先排序技術述評[J].軟件學報，2013,24(8):1695.

CHEN Xiang,CHEN Jihong,JU Xiaolin,etal.Survey of test case prioritization techniques for regression testing[J]. Journal of Software, 2013,24(8):1695.

[9] 牟永敏，李慧麗.基于函數(shù)調用路徑的測試用例優(yōu)先級排序[J].計算機工程，2014,40(7):243.

MOU Yongmin, LI Huili. Test case prioritization based on function calling paths[J]. Computer Engineering, 2014,40(7):243.

Path Priority Model of Regression Testing

DUQingfeng,FENGGuoyao,QIANHaoran

(School of Software Engineering, Tongji University, Shanghai 201804, China)

In order to improve the efficiency of regression testing, test case prioritization technology is particularly important. This paper is mainly to identify possible path segments by the call graph between components, to calculate path segments’ cover index by the execution history of test cases, and finally to put forward a priority model of test case based on the sort of the cover index.Through the research of this model, it can effectively carry out regression test, and detect the errors in the program timely.

regression testing; path segment; priority model; coverage index

2015-10-15

國家自然科學基金(41171303)

杜慶峰(1968—)，男，教授，博士生導師，工學博士，主要研究方向為軟件測試、計算機相關學科交叉領域. E-mail： du_cloud@#edu.cn

TP311.5

A