張李梅，牟永敏，張志華，崔展齊

(北京信息科技大學(xué)網(wǎng)絡(luò)文化與數(shù)字傳播北京市重點(diǎn)實(shí)驗(yàn)室，北京 100101)

回歸測試作為軟件開發(fā)和維護(hù)周期中非常重要的一個(gè)階段，產(chǎn)品的不斷迭代更新導(dǎo)致測試的成本越來越高[1]。如何在有限的資源以及保證測試質(zhì)量的前提下，對回歸測試用例進(jìn)行優(yōu)化，已經(jīng)成為軟件工程領(lǐng)域的研究熱點(diǎn)之一[2]?；貧w測試的優(yōu)化技術(shù)主要圍繞著測試用例的約簡，測試用例的選擇，測試用例的優(yōu)先級排序等主題進(jìn)行研究[3]。

回歸測試用例的約簡技術(shù)通過識別并去除冗余的測試用例，以達(dá)到減少測試用例的目的[4]?；貧w測試用例選擇技術(shù)通過從測試用例集中選取與變更相關(guān)的測試用例子集，從而降低測試用例集的規(guī)模[5]?；貧w測試用例的優(yōu)先級排序技術(shù)根據(jù)某種規(guī)則對測試用例的執(zhí)行次序排序，提高測試的效率[6]。同時(shí)，為解決單目標(biāo)排序往往具有的片面性問題，研究者提出了多目標(biāo)測試用例優(yōu)先級排序方法，對多個(gè)優(yōu)化目標(biāo)進(jìn)行權(quán)衡，從而更加全面有效的對測試用例進(jìn)行排序。

傳統(tǒng)的單獨(dú)針對某一主題的研究缺乏全面性思考，容易失去有效的測試用例或保留冗余的測試用例，近年來混合優(yōu)化方法得到越來越多人的關(guān)注[7]。在基于函數(shù)調(diào)用路徑(function call path,FCP)對代碼進(jìn)行變更影響分析的基礎(chǔ)上，結(jié)合回歸測試用例選擇及優(yōu)先級排序，提出一種測試用例初次選擇-排序-再次選擇的測試用例混合優(yōu)化方法。

1 測試用例的混合優(yōu)化方法

近年來，中外關(guān)于回歸測試用例混合優(yōu)化方法的研究已有大量報(bào)道。2011年，Mirarab等[8]先利用整數(shù)線性規(guī)劃方法對測試用例進(jìn)行選擇，然后使用貪心算法最大化最小覆蓋率，從而對所選擇的測試用例排序，該方法雖然能在覆蓋率方面達(dá)到較好的效果，但沒有考慮到缺陷、成本等方面的因素。2012年，Beszédes等[9]將基于代碼變更的覆蓋信息進(jìn)行測試用例選擇的方法引入開源項(xiàng)目WebKit，并比較了不同的優(yōu)先排序策略在缺陷檢測等方面的有效性，可從中選擇出更有效的策略，但沒有考慮在其他平臺上的適用性。2014年，Elbaum等[10]為保障項(xiàng)目的成本效益提出，提出了在提交代碼的預(yù)提交階段，使用測試用例的選擇技術(shù)選擇測試用例集的子套件進(jìn)行模塊測試，在隨后的提交后測試階段對測試用例進(jìn)行優(yōu)先級排序，這種方法能夠確保更快速的報(bào)告故障，但不適合進(jìn)行推廣，因?yàn)椴煌瑱C(jī)構(gòu)的質(zhì)量控制流程可能不同。2016年，鄭錦勤等[11]針對代碼變更中的其中一種只存在修改的情形，提出以最小化覆蓋關(guān)聯(lián)函數(shù)對為選擇原則，并利用測試用例的絕對貢獻(xiàn)度、缺陷檢測能力和缺陷影響度進(jìn)行排序，這種方法未考慮在添加或刪除功能的情形下如何處理。2017年，Spieker等[12]提出根據(jù)測試的歷史信息進(jìn)行強(qiáng)化學(xué)習(xí)，從而進(jìn)行測試用例的選擇和排序，該方法只考慮測試歷史數(shù)據(jù)。2017年，Marijan等[13]先基于時(shí)間、覆蓋率、成本等約束最小化測試用例集，然后基于缺陷檢測能力和需求覆蓋進(jìn)行多目標(biāo)優(yōu)先級排序，該方法有效縮減了測試用例集的規(guī)模，但沒有考慮到縮減后的測試用例集的執(zhí)行時(shí)間。

前人研究中混合優(yōu)化方法主要是基于語句粒度分析代碼。基于此，根據(jù)提取出的信息設(shè)計(jì)方案實(shí)現(xiàn)優(yōu)化，將代碼分析粒度由語句擴(kuò)展到函數(shù)，既能避免路徑的爆炸式增長，又可以保證測試完全[14]。在基于函數(shù)調(diào)用路徑進(jìn)行變更影響分析的基礎(chǔ)上，將測試用例的選擇和優(yōu)先級排序兩個(gè)主題相結(jié)合，充分利用兩個(gè)主題的優(yōu)勢，在對測試用例的執(zhí)行優(yōu)先級進(jìn)行排序的同時(shí)，減少測試用例的數(shù)量，從而達(dá)到混合優(yōu)化的目的。

2 基于FCP的測試用例混合優(yōu)化方法

基于FCP的回歸測試用例混合優(yōu)化方法主要分為以下三個(gè)步驟。

步驟1對代碼在函數(shù)粒度上進(jìn)行變更影響分析，生成變更影響路徑集和變更影響關(guān)鍵子路徑集，關(guān)聯(lián)初始測試用例集與函數(shù)調(diào)用路徑集，選擇出其中覆蓋了變更影響路徑的測試用例。

步驟2因步驟1選擇出的測試用例集中，存在部分覆蓋相同變更影響關(guān)鍵子路徑集的測試用例，故先利用測試用例的變更覆蓋率、故障發(fā)生率、缺陷影響率、執(zhí)行開銷率四個(gè)指標(biāo)加權(quán)求和的結(jié)果，進(jìn)行優(yōu)先級排序，并根據(jù)測試用例的執(zhí)行信息動態(tài)調(diào)整。

步驟3對步驟2生成的測試用例集進(jìn)行再次選擇，從覆蓋了相同變更影響關(guān)鍵子路徑集的測試用例中，選擇出排序相對靠前的測試用例，形成最終的測試用例集。

根據(jù)這三個(gè)步驟，可生成基于FCP的測試用例混合優(yōu)化方法的整體框架流程，如圖1所示。

圖1 混合優(yōu)化方法整體框架流程Fig.1 Hybrid optimization method overall framework process

2.1 測試用例的初次選擇

測試用例的選擇技術(shù)通過分析代碼變更，確定程序中可能受影響的部分，進(jìn)而選擇出能夠覆蓋變更部分及可能受影響的部分的測試用例。本文所提出的測試用例選擇技術(shù)是先分析源程序中函數(shù)變更的情況以及可能受影響的函數(shù)，并將這些函數(shù)映射到函數(shù)調(diào)用路徑上，確定變更影響路徑集以及變更影響關(guān)鍵子路徑集；然后根據(jù)FCP與測試用例的對應(yīng)關(guān)系，從初始測試用例集中選擇覆蓋了變更影響路徑集的測試用例。

2.1.1 初次選擇基本概念

為更好地理解測試用例的初次選擇，對其中所涉及的基本概念及其定義進(jìn)行闡述。

定義1函數(shù)粒度的代碼變更。將源代碼表示成G=(V,E),對于?Vi∈V(G),?Ei∈E(G)。函數(shù)集用V(G)={V1,V2,…,Vn}表示，V1、Vn為函數(shù)節(jié)點(diǎn)，對應(yīng)程序中的每個(gè)函數(shù)；E(G)={Ei=(Vi,Vj)|Vi,Vj∈V(G)}，Vi為Vj的父節(jié)點(diǎn)，表示函數(shù)調(diào)用關(guān)系圖中有向邊的集合，反映了函數(shù)間的調(diào)用關(guān)系或順序執(zhí)行關(guān)系。定義基于G的編輯操作ACTION為以下三種。

插入：INSERT(Vi,Vj,k)表示將函數(shù)節(jié)點(diǎn)Vi插入Vj的第k個(gè)子節(jié)點(diǎn)處。

刪除：DELETE(Vi)表示刪除函數(shù)節(jié)點(diǎn)Vi。

修改：MODIFY(Vi)表示修改函數(shù)節(jié)點(diǎn)Vi的內(nèi)部。

定義2變更函數(shù)集。變更函數(shù)是指經(jīng)過定義1中三種變更行為的函數(shù)。變更函數(shù)集可表示為CFS(change function set)={CFi=(Vi,ACTION)|Vi∈V(G),ACTION∈{INSERT(Vi,Vj,k)，DELETE(Vi)，MODIFY(Vi)}},CFi表示CFS中的變更函數(shù)節(jié)點(diǎn)。

定義3函數(shù)調(diào)用路徑。函數(shù)調(diào)用路徑是函數(shù)調(diào)用圖G中的一條路徑，即以函數(shù)為基本單位，程序的一次執(zhí)行軌跡[15]?？杀硎緸镕CP(function call path)=(Vi,Vi+1,…,Vq),其中{Vi,Vi+1,…,Vq}?V(G),{(Vi,Vi+1),(Vi+1,Vi+2),…,(Vq-1,Vq)}?E(G)。

2.1.2 初次選擇算法設(shè)計(jì)

根據(jù)定義2可知，變更行為可分為三種：插入、刪除、修改，生成變更影響路徑集的方法有兩種。

(1)靜態(tài)分析變更前后兩個(gè)版本的源代碼，分別生成相對應(yīng)的全局函數(shù)調(diào)用路徑集，兩者相比較，不同的即為變更影響路徑。

(2)靜態(tài)分析變更后的源代碼，生成對應(yīng)的全局函數(shù)調(diào)用路徑集，變更函數(shù)所在的函數(shù)調(diào)用路徑即為變更影響路徑。

這兩種方法各有利弊，第一種方法不能分析出函數(shù)內(nèi)部發(fā)生修改的情況，第二種方法不能分析出刪除函數(shù)節(jié)點(diǎn)的情況，所以，可結(jié)合兩種方法設(shè)計(jì)變更影響分析算法(change impact analysis,CIA)。CIA算法描述如下：

Input:變更前的函數(shù)調(diào)用路徑集FCPS

變更后的函數(shù)調(diào)用路徑集FCPS_C

變更函數(shù)集CFS

Output:變更影響路徑集IFCPS

變更影響關(guān)鍵子路徑集ICFCPS

Begin

IFCPS←?,ICFCPS←?

//生成變更影響路徑集

foreach fcp in FCPS_C do//遍歷所有變更后的函數(shù)調(diào)用路徑

if fcp∈FCPS then//判斷變更前的函數(shù)調(diào)用路徑集中是否包括該函數(shù)調(diào)用路徑

IFCPS←IFCPS+{fcp}//不包含，則直接加入變更影響路徑集中

else//否則，根據(jù)變更函數(shù)生成變更影響路徑

IFCPS←Add(CFS,fcp)

end if

end foreach

//生成變更影響關(guān)鍵子路徑集

foreach ifcp in IFCPS do//遍歷所有的變更影響路徑

foreach cf in CFS do//遍歷所有的變更函數(shù)

if cf ∈ ifcp then//判斷該變更影響路徑是否包含該變更函數(shù)

ICFCPS←Add(ifcp,cf,ICFCPS)//根據(jù)該變更函數(shù)及變更影響路徑生成變更影響關(guān)鍵子路徑，并加入變更影響關(guān)鍵子路徑集中

end if

end foreach

end foreach

return IFCPS,ICFCPS

End

利用CIA算法生成變更影響路徑集后，動態(tài)執(zhí)行初始測試用例集，生成其相對應(yīng)的FCP集[16]。將變更影響路徑與FCP進(jìn)行精確匹配，找到能夠覆蓋變更影響路徑集的測試用例即可。測試用例初次選擇算法(test case first section,TFS)描述如下：

Input:變更前的函數(shù)調(diào)用路徑集FCPS

變更后的函數(shù)調(diào)用路徑集FCPS_C

變更函數(shù)集CFS

初始測試用例集T

Output:初次選擇后的測試用例集T_FS

初次選擇后的測試用例集對應(yīng)的FCP集T_FS_FCPS

Begin

T_FS←?,T_FCPS←?,T_FS_FCPS←?

IFCPS←CIA(FCPS,FCPS_C,CFS)

//生成初始測試用例集中每個(gè)測試用例對應(yīng)的FCP集

T_FCPS←Generate_T_FCPS(T)

//生成初次選擇后的測試用例集

fori=0 toi=T.length() do//遍歷所有的測試用例

foreach fcp in T_FCPS[ido//遍歷該測試用例對應(yīng)的FCP

if fcp ∈ IFCPS then//判斷該FCP是否為變更影響路徑

T_FS←T_FS+T[i]//將該測試用例加入初次選擇后的測試用例集中

T_FS_FCPS←T_FS_FCPS+Search(T_FCPS,T[i])//將該測試用例對應(yīng)的FCP集加入初次選擇后的測試用例集所對應(yīng)的FCP集中

break

end if

end foreach

end for

return T_FS,T_FS_FCPS

End

2.2 多目標(biāo)測試用例優(yōu)先級排序

初始測試用例集在經(jīng)過初次選擇后，在一定程度上減少了測試用例的數(shù)量，但仍存在部分冗余的測試用例，這些用例覆蓋了相同的變更影響關(guān)鍵子路徑，如果從中隨機(jī)選擇其中一個(gè)，很有可能損失更有價(jià)值的測試用例，故先對測試用例進(jìn)行排序。

測試用例的優(yōu)先級排序是指選取有效的優(yōu)先級排序指標(biāo)，用以生成最優(yōu)的測試用例執(zhí)行次序。使用變更覆蓋率、故障發(fā)生率、缺陷影響率、執(zhí)行開銷率四個(gè)指標(biāo)加權(quán)求和的結(jié)果對測試用例排序，并設(shè)計(jì)了能夠根據(jù)測試用例的執(zhí)行信息動態(tài)調(diào)整優(yōu)先級的算法。

2.2.1 優(yōu)先級排序指標(biāo)

從不同角度出發(fā)設(shè)計(jì)了四個(gè)優(yōu)先級排序指標(biāo)，其相關(guān)定義如下。

定義6測試用例的變更覆蓋率。測試用例的變更覆蓋率是指測試用例ti在執(zhí)行過程中覆蓋的變更函數(shù)及可能受影響的函數(shù)的個(gè)數(shù)，與所有的變更函數(shù)及可能受影響的函數(shù)個(gè)數(shù)的比值，可用式(1)表示。

(1)

式(1)中:Cti為測試用例ti在執(zhí)行過程中覆蓋的變更函數(shù)及可能受影響的函數(shù)集；C為變更函數(shù)及可能受影響的全部函數(shù)的集合。

定義7測試用例的故障發(fā)生率。測試用例的故障發(fā)生率指的是測試用例發(fā)生故障的執(zhí)行次數(shù)與總的執(zhí)行次數(shù)的比值?？捎檬?2)表示：

(2)

式(2)中:FEti為測試用例ti發(fā)生故障的執(zhí)行次數(shù)；Eti為測試用例ti總的執(zhí)行次數(shù)。

定義8測試用例缺陷影響率。測試用例缺陷影響率指的是測試用例ti在執(zhí)行過程中檢測到的缺陷對程序執(zhí)行的影響程度，即由于缺陷的存在導(dǎo)致不能被覆蓋的變更函數(shù)及可能受變更函數(shù)影響的函數(shù)的個(gè)數(shù)，在所有的因缺陷影響而未能覆蓋變更函數(shù)及可能受影響的函數(shù)個(gè)數(shù)中的占比?？捎檬?3)表示。

(3)

式(3)中:FCti為測試用例ti因檢測到缺陷而不能覆蓋的變更函數(shù)及可能受變更函數(shù)影響的函數(shù)集；FC為總的因缺陷影響而未能覆蓋的變更函數(shù)及可能受影響的函數(shù)集。

定義9測試用例執(zhí)行開銷率。測試用例執(zhí)行開銷率指的是執(zhí)行測試用例ti所花費(fèi)的代價(jià)，可用單位時(shí)間內(nèi)的函數(shù)覆蓋率表示，如式(4)所示：

(4)

式(4)中:Mti為測試用例ti覆蓋的函數(shù)集；Sti為測試用例ti的執(zhí)行時(shí)間。

定義10測試用例優(yōu)先級排序綜合指標(biāo)。測試用例優(yōu)先級排序綜合指標(biāo)指的是將定義6～定義9中的指標(biāo)進(jìn)行加權(quán)求和的結(jié)果,可表示為

Dti=ω1DC|ti+ω2DFE|ti+ω3DFC|ti+ω4DMS|ti

(5)

式(5)中:ω1、ω2、ω3、ω4分別為變更覆蓋率、故障發(fā)生率、缺陷影響率和執(zhí)行開銷率的權(quán)重，且ω1+ω2+ω3+ω4=1。

所用的權(quán)重系數(shù)是先隨機(jī)選取50組，用以模擬實(shí)際測試中各種不同權(quán)重的選取情況，然后在實(shí)驗(yàn)中不斷比較調(diào)整，從而得出的一組能夠取得相對較好的實(shí)驗(yàn)效果的權(quán)重。在實(shí)際項(xiàng)目中，可根據(jù)不同側(cè)重，靈活調(diào)整權(quán)值。

2.2.2 多目標(biāo)排序算法設(shè)計(jì)

多目標(biāo)優(yōu)先級排序算法主要分為兩種，基于加權(quán)法的算法和基于Pareto最優(yōu)的求解算法[17]。直接求解Pareto最優(yōu)解集的方法雖然能在一定程度上實(shí)現(xiàn)目標(biāo)，但容易陷入局部最優(yōu)，且該方法的執(zhí)行效率深受測試用例數(shù)量的影響。而基于加權(quán)法的排序方法更加簡單易懂，且易于在實(shí)際項(xiàng)目中推廣。

因此，借鑒加權(quán)法中的啟發(fā)式貪婪算法的思想，并基于Additional策略設(shè)計(jì)了多目標(biāo)動態(tài)調(diào)整優(yōu)先級排序算法MODAP。

(1)根據(jù)初次選擇后的測試用例集T_FS對當(dāng)前未被覆蓋的變更影響路徑集IFCPS_UC的覆蓋情況計(jì)算變更覆蓋率，對測試用例的變更覆蓋率、故障發(fā)生率、缺陷影響率和執(zhí)行開銷率加權(quán)求和，進(jìn)行初始排序。

(2)執(zhí)行排在第一位的測試用例，將其加入排序后的測試用例集T_MDAP，并從T_FS中去掉。

(3)根據(jù)該測試用例的執(zhí)行信息，重新對排序指標(biāo)賦值計(jì)算，調(diào)整T_MDAP中測試用例的順序，從未被覆蓋的變更影響路徑集IFCPS_UC中去除該測試用例覆蓋的變更影響路徑。

(4)判斷IFCPS_UC是否為空，不為空，則返回第(1)步，否則，當(dāng)前的T_MDAP即為排序結(jié)果。多目標(biāo)動態(tài)調(diào)整優(yōu)先級(multi-objective dynamic adjusting priority,MODAP)算法描述如下。

Input:初次選擇后的測試用例集T_FS

變更影響路徑集IFCPS

Output:動態(tài)調(diào)整排序后的測試用例集T_MDAP

Begin

T_MDAP←?,Priority_FS←?,Priority_MDAP←?,IFCPS_UC←IFCPS

while IFCPS_UC≠? do

foreachtin T_FS do//遍歷初次選擇后的所有的測試用例

Priority_FS←Add(t,CalculateG(t),IFCPS_UC)//計(jì)算優(yōu)先級排序綜合指標(biāo)

end foreach

T_FS←Sort(T_FS,Priority_FS)//根據(jù)優(yōu)先級排序綜合指標(biāo)對測試用例從高到低排序

t←First{T_FS}//找到排在第一位的測試用例

T_MDAP←T_MDAP+{t}//將該測試用例加入排序后的測試用例集中

T_FS←T_FS-{t}//從初次選擇后的測試用例集中刪除該測試用例

Priority_MDAP←Add(Update_Priority(t,CalculateG(Execute(t))))//根據(jù)執(zhí)行信息重新計(jì)算排序指標(biāo)

T_MDAP←Sort(T_MDAP,Priority_MDAP)//調(diào)整排序

IFCPS_UC←IFCPS_UC-{t.ifcps}//去掉該測試用例覆蓋的變更影響路徑

end while

return T_MDAP

End

2.3 測試用例的再次選擇

變更影響關(guān)鍵子路徑，是變更影響路徑中與變更關(guān)系更加密切的函數(shù)調(diào)用路徑段。兩者是多對多的關(guān)系。一條變更影響路徑可能包括多條變更影響關(guān)鍵子路徑，一條變更影響關(guān)鍵子路徑也可能包含于多條變更影響路徑中。所以，排序后的測試用例集中可能仍然存在部分冗余的測試用例，這些測試用例覆蓋了相同的變更影響關(guān)鍵子路徑，因此需要進(jìn)行再次選擇。

測試用例的再次選擇可從相關(guān)概念和算法設(shè)計(jì)兩方面敘述。

2.3.1 再次選擇相關(guān)概念

定義11用例變更關(guān)鍵影響覆蓋矩陣。用例變更關(guān)鍵影響覆蓋矩陣T_ICFCP是一個(gè)|T|×|ICFCPS|二進(jìn)制矩陣，表示測試用例集T={t1,t2,…,tn}到變更影響關(guān)鍵子路徑集ICFCPS的覆蓋關(guān)系，矩陣元素如式(6)定義：

(6)

定義12用例變更影響覆蓋矩陣。用例變更影響覆蓋矩陣T_IFCP表示測試用例集T到變更影響路徑集IFCPS的覆蓋關(guān)系，矩陣元素如式(7)定義：

(7)

定義13關(guān)鍵變更包含矩陣。關(guān)鍵變更包含矩陣CI表示變更影響路徑集IFCPS到變更影響關(guān)鍵子路徑集ICFCPS的包含關(guān)系，矩陣元素如式(8)定義：

(8)

2.3.2 再次選擇算法設(shè)計(jì)

根據(jù)概念設(shè)計(jì)測試用例再次選擇算法(test case re-selection,TRS)其算法思想是：先生成用例變更關(guān)鍵影響覆蓋矩陣，通過用例變更關(guān)鍵影響覆蓋矩陣獲得任意一個(gè)測試用例覆蓋的變更影響關(guān)鍵子路徑集，同時(shí)，獲取到任意一個(gè)變更影響關(guān)鍵子路徑的執(zhí)行測試用例集，然后從覆蓋了相同變更影響關(guān)鍵子路徑的測試用例中選擇排序相對靠前的測試用例。TRS算法描述如下：

Input:動態(tài)調(diào)整排序后的測試用例集T_MDAP

初次選擇后的測試用例集對應(yīng)的FCP集T_FS_FCPS

變更影響路徑集IFCPS

變更影響關(guān)鍵子路徑集ICFCPS

Output:再次選擇后生成的測試用例集T_RS

Begin

//初始化

ICFCPS_UC←ICFCPS,T_MDAP_FCPS←?

//生成用例變更影響覆蓋矩陣T_IFCP

T_MDAP_FCPS←Sort(Update(T_FS_FCPS,T_MDAP))

T_IFCP←Generate_T_IFCP(T_MDAP_FCPS,IFCPS)

//生成關(guān)鍵變更包含矩陣CI

CI←Generate_CI(IFCPS,ICFCPS)

//根據(jù)T_IFCP及CI，生成用例變更關(guān)鍵影響覆蓋矩陣

T_ICFCP←Generate_T_ICFCP(T_IFCP,CI)

//選擇

while ICFCPS_UC≠? do

t←First(T_MDAP)//找到排名第一的測試用例

icfcps←Get_icfcps(t,T_ICFCP,ICFCPS_UC)//統(tǒng)計(jì)該測試用例在未被覆蓋的變更影響關(guān)鍵子路徑集中覆蓋的變更影響關(guān)鍵子路徑

T_RS←T_RS+{t}//將該測試用例加入再次選擇后的測試用例集中

T_MDAP←T_MDAP-{t}//從排序后的測試用例集中去掉該測試用例

ICFCPS_UC←ICFCPS_UC-{icfcps}//去掉統(tǒng)計(jì)出的變更影響關(guān)鍵子路徑

end while

return T_RS

End

3 實(shí)驗(yàn)與評測

3.1 實(shí)驗(yàn)數(shù)據(jù)與評測指標(biāo)

為驗(yàn)證所提出方法的有效性，選擇SIR(Software-artifact Infrastructure Repository)庫中的評測程序Siemens Suite和gzip及其相應(yīng)的測試用例集進(jìn)行實(shí)驗(yàn)對比,其具體相關(guān)信息如表1所示。

表1 評測程序基本信息Table 1 Evaluation programs basic information

所提出的混合優(yōu)化方法的目的是在減少測試用例數(shù)量的同時(shí)，盡量避免降低測試用例集的錯誤檢測能力，因此采用約簡率R和平均缺陷檢測率APFDC(average percentage of fault detectionCost-cognizant)作為度量標(biāo)準(zhǔn)。

約簡率R用于衡量測試用例數(shù)量減少的程度，其計(jì)算公式如式(9)所示：

(9)

式(9)中:T為初始測試用例集；T′為優(yōu)化后的測試用例集。R的值越大，表示優(yōu)化后的測試用例的數(shù)量越少，優(yōu)化效果越好。

APFDC用于度量測試用例集的平均錯誤檢測能力，該指標(biāo)對測試用例的執(zhí)行開銷和缺陷的危害程度進(jìn)行了綜合考量，計(jì)算公式如式(10)所示：

(10)

式(10)中：初始測試用例集為T,包含n個(gè)測試用例，m個(gè)缺陷。給定一個(gè)測試用例執(zhí)行次序，TFi表示首個(gè)可檢測到第i個(gè)缺陷的測試用例在該執(zhí)行次序中所處次序；ti代表第i個(gè)測試用例的執(zhí)行開銷；tj代表第j個(gè)測試用例的執(zhí)行開銷；fi代表第i個(gè)缺陷的危害程度。APFDC的值越大，表示測試用例集能更快檢測到更多更嚴(yán)重的缺陷。

3.2 實(shí)驗(yàn)對比與結(jié)果分析

設(shè)計(jì)實(shí)驗(yàn)從兩方面出發(fā)對本文方法的有效性進(jìn)行驗(yàn)證。一方面，所提混合優(yōu)化方法分為三個(gè)步驟，可比較每一個(gè)步驟執(zhí)行后的結(jié)果，分析三個(gè)步驟依次執(zhí)行是否能逐步增強(qiáng)優(yōu)化；另一方面，選擇文獻(xiàn)[8]和文獻(xiàn)[11]所提方法與本文方法進(jìn)行實(shí)驗(yàn)對比，驗(yàn)證本文方法是否能取得更好的優(yōu)化效果。

圖2 混合優(yōu)化方法三個(gè)步驟的簡約率和APFDCFig.2 Reduction rate and APFDC of the three steps fo hybrid optim zation

3.2.1 混合優(yōu)化方法的三個(gè)步驟的優(yōu)化效果實(shí)驗(yàn)對比

所提出的混合優(yōu)化方法分為三步，每一步都在前一步的基礎(chǔ)上進(jìn)行，可驗(yàn)證每一步是否能比前一步的優(yōu)化效果更好。實(shí)驗(yàn)的對比結(jié)果如圖2所示。

由圖2(a)可知，三個(gè)步驟下的約簡率逐漸升高，測試用例再次選擇后的測試用例數(shù)量最少；觀察圖2(b)可知，測試用例再次選擇后的APFDC與優(yōu)先級排序后的APFDC基本相同。由此可知，所提方法能在盡量避免損失有價(jià)值的測試用例的情況下，極大程度地減少測試用例的數(shù)量，提高回歸測試的效率。

3.2.2 與已有方法的對比

本文方法與文獻(xiàn)[8]、文獻(xiàn)[11]方法都為混合優(yōu)化方法，可將這三種方法都在函數(shù)粒度上進(jìn)行對比實(shí)驗(yàn)，以驗(yàn)證本文方法的有效性。結(jié)果如圖3所示。

圖3 三種方法的約簡率和APFDCFig.3 Reduction rate and APFDC of the three methods

由圖3可知，本文方法的約簡率略遜于文獻(xiàn)[11],但APFDC最高；文獻(xiàn)[11]方法因不能處理增加或刪除的情況，約簡率雖高，但全面性不足,故其APFDC低于本文方法。相對而言，本文方法的優(yōu)化效果最好。

4 結(jié)論

在對代碼進(jìn)行基于FCP的變更影響分析的基礎(chǔ)上，提出一種測試用例混合優(yōu)化方法。首先選擇出覆蓋了變更影響路徑集的測試用例，然后利用測試用例的執(zhí)行信息對測試用例的變更覆蓋率、故障發(fā)生率、缺陷影響率和執(zhí)行開銷率重新賦值，進(jìn)而動態(tài)調(diào)整排序，最后從覆蓋了相同變更影響關(guān)鍵子路徑的測試用例中選擇出排序更靠前的測試用例，三步生成最后的測試用例集。實(shí)驗(yàn)結(jié)果證明，本文方法可以有效減少測試用例的數(shù)量，同時(shí)可以避免損失一部分更有價(jià)值的測試用例，減少了額外開銷，提高了回歸測試的效率。