杜慶峰， 馮國(guó)堯， 錢浩然

(同濟(jì)大學(xué) 軟件學(xué)院，上海 201804)

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

杜慶峰， 馮國(guó)堯， 錢浩然

(同濟(jì)大學(xué) 軟件學(xué)院，上海 201804)

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

回歸測(cè)試； 路徑片段； 優(yōu)先級(jí)模型； 覆蓋指標(biāo)

隨著信息技術(shù)的迅猛發(fā)展，軟件已經(jīng)被應(yīng)用于各個(gè)領(lǐng)域,同時(shí)軟件的競(jìng)爭(zhēng)也日益激烈,保證軟件的質(zhì)量就變得尤為重要.軟件測(cè)試作為軟件質(zhì)量的可靠保障，在軟件的整個(gè)生命周期中占有越來(lái)越重要的地位.軟件的調(diào)試、升級(jí)與維護(hù)往往需要更改部分代碼，為了驗(yàn)證修改后的程序是否引發(fā)新的問題或?qū)ξ葱薷牡牟糠质欠裨斐捎绊?，就需要頻繁地對(duì)軟件進(jìn)行回歸測(cè)試.

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

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

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

1 問題提出

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

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

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

表1 測(cè)試用例檢錯(cuò)表示例Tab.1 Error detection table of test case

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

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

2 回歸測(cè)試優(yōu)先級(jí)模型

2.1 相關(guān)定義

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

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

圖1 組件調(diào)用路徑示例Fig.1 Example of component call path diagram

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

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

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

2.2 優(yōu)先級(jí)模型構(gòu)建

2.2.1 模型理論

回歸測(cè)試路徑優(yōu)先級(jí)模型是將功能看成一個(gè)組件結(jié)點(diǎn)的形式.根據(jù)組件結(jié)點(diǎn)之間的相互調(diào)用關(guān)系，將各個(gè)組件進(jìn)行集成，得到組件調(diào)用路徑圖.圖1就是一個(gè)組件調(diào)用路徑圖.

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

表2 測(cè)試用例集和路徑片段滿足的二元關(guān)系實(shí)例Tab.2 Examples of binary relations between test suite and path segments

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

2.2.2 模型的數(shù)學(xué)表達(dá)

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

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

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

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

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

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

3 模型算法及驗(yàn)證

3.1 算法思想

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

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

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

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

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

3.2 算法邏輯

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

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 算法復(fù)雜度分析

3.3.1 時(shí)間復(fù)雜度

3.3.2 空間復(fù)雜度

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

3.4 算法驗(yàn)證

3.4.1 優(yōu)先級(jí)模型的測(cè)評(píng)標(biāo)準(zhǔn)

軟件測(cè)試的目的是設(shè)計(jì)出高質(zhì)量的測(cè)試用例來(lái)盡可能多地檢測(cè)出被測(cè)軟件內(nèi)部存在的缺陷.在設(shè)計(jì)測(cè)試用例優(yōu)先級(jí)的評(píng)測(cè)指標(biāo)時(shí)，需要體現(xiàn)出測(cè)試用例的缺陷檢測(cè)速率.

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

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

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

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

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

3.4.2 試驗(yàn)設(shè)計(jì)與分析

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

圖2 組件調(diào)用路徑Fig.2 Component call path diagram

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

圖3 修改后的組件調(diào)用路徑Fig.3 Modified component call path diagram

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

表3 測(cè)試用例檢錯(cuò)表Tab.3 Error table of test case

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

3.4.3 試驗(yàn)結(jié)果

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

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

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

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

4 結(jié)語(yǔ)

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

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

[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] 安金霞，王國(guó)慶，李樹芳，等.基于多維度覆蓋率的軟件測(cè)試動(dòng)態(tài)評(píng)價(jià)方法[J].軟件學(xué)報(bào)，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] 杜慶峰. 高級(jí)軟件測(cè)試技術(shù)[M].北京：清華大學(xué)出版社，2011.

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

[7] 李華瑩，胡兢玉.回歸測(cè)試用例優(yōu)先級(jí)排序技術(shù)研究[J].計(jì)算機(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] 陳翔，陳繼紅，鞠小林，等.回歸測(cè)試中測(cè)試用例優(yōu)先排序技術(shù)述評(píng)[J].軟件學(xué)報(bào)，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ù)調(diào)用路徑的測(cè)試用例優(yōu)先級(jí)排序[J].計(jì)算機(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

國(guó)家自然科學(xué)基金(41171303)

杜慶峰(1968—)，男，教授，博士生導(dǎo)師，工學(xué)博士，主要研究方向?yàn)檐浖y(cè)試、計(jì)算機(jī)相關(guān)學(xué)科交叉領(lǐng)域. E-mail： du_cloud@#edu.cn

TP311.5

A