基于函數調用路徑的測試用例混合優化方法

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

(北京信息科技大學網絡文化與數字傳播北京市重點實驗室，北京 100101)

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

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

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

1 測試用例的混合優化方法

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

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

2 基于FCP的測試用例混合優化方法

基于FCP的回歸測試用例混合優化方法主要分為以下三個步驟。

步驟1對代碼在函數粒度上進行變更影響分析，生成變更影響路徑集和變更影響關鍵子路徑集，關聯初始測試用例集與函數調用路徑集，選擇出其中覆蓋了變更影響路徑的測試用例。

步驟2因步驟1選擇出的測試用例集中，存在部分覆蓋相同變更影響關鍵子路徑集的測試用例，故先利用測試用例的變更覆蓋率、故障發生率、缺陷影響率、執行開銷率四個指標加權求和的結果，進行優先級排序，并根據測試用例的執行信息動態調整。

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

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

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

2.1 測試用例的初次選擇

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

2.1.1 初次選擇基本概念

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

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

插入：INSERT(Vi,Vj,k)表示將函數節點Vi插入Vj的第k個子節點處。

刪除：DELETE(Vi)表示刪除函數節點Vi。

修改：MODIFY(Vi)表示修改函數節點Vi的內部。

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

定義3函數調用路徑。函數調用路徑是函數調用圖G中的一條路徑，即以函數為基本單位，程序的一次執行軌跡[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 初次選擇算法設計

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

(1)靜態分析變更前后兩個版本的源代碼，分別生成相對應的全局函數調用路徑集，兩者相比較，不同的即為變更影響路徑。

(2)靜態分析變更后的源代碼，生成對應的全局函數調用路徑集，變更函數所在的函數調用路徑即為變更影響路徑。

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

Input:變更前的函數調用路徑集FCPS

變更后的函數調用路徑集FCPS_C

變更函數集CFS

Output:變更影響路徑集IFCPS

變更影響關鍵子路徑集ICFCPS

Begin

IFCPS←?,ICFCPS←?

//生成變更影響路徑集

foreach fcp in FCPS_C do//遍歷所有變更后的函數調用路徑

if fcp∈FCPS then//判斷變更前的函數調用路徑集中是否包括該函數調用路徑

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

else//否則，根據變更函數生成變更影響路徑

IFCPS←Add(CFS,fcp)

end if

end foreach

//生成變更影響關鍵子路徑集

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

foreach cf in CFS do//遍歷所有的變更函數

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

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

end if

end foreach

end foreach

return IFCPS,ICFCPS

End

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

Input:變更前的函數調用路徑集FCPS

變更后的函數調用路徑集FCPS_C

變更函數集CFS

初始測試用例集T

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

初次選擇后的測試用例集對應的FCP集T_FS_FCPS

Begin

T_FS←?,T_FCPS←?,T_FS_FCPS←?

IFCPS←CIA(FCPS,FCPS_C,CFS)

//生成初始測試用例集中每個測試用例對應的FCP集

T_FCPS←Generate_T_FCPS(T)

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

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

foreach fcp in T_FCPS[ido//遍歷該測試用例對應的FCP

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

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

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

break

end if

end foreach

end for

return T_FS,T_FS_FCPS

End

2.2 多目標測試用例優先級排序

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

測試用例的優先級排序是指選取有效的優先級排序指標，用以生成最優的測試用例執行次序。使用變更覆蓋率、故障發生率、缺陷影響率、執行開銷率四個指標加權求和的結果對測試用例排序，并設計了能夠根據測試用例的執行信息動態調整優先級的算法。

2.2.1 優先級排序指標

從不同角度出發設計了四個優先級排序指標，其相關定義如下。

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

(1)

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

定義7測試用例的故障發生率。測試用例的故障發生率指的是測試用例發生故障的執行次數與總的執行次數的比值。可用式(2)表示：

(2)

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

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

(3)

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

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

(4)

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

定義10測試用例優先級排序綜合指標。測試用例優先級排序綜合指標指的是將定義6～定義9中的指標進行加權求和的結果,可表示為

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

(5)

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

所用的權重系數是先隨機選取50組，用以模擬實際測試中各種不同權重的選取情況，然后在實驗中不斷比較調整，從而得出的一組能夠取得相對較好的實驗效果的權重。在實際項目中，可根據不同側重，靈活調整權值。

2.2.2 多目標排序算法設計

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

因此，借鑒加權法中的啟發式貪婪算法的思想，并基于Additional策略設計了多目標動態調整優先級排序算法MODAP。

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

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

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

(4)判斷IFCPS_UC是否為空，不為空，則返回第(1)步，否則，當前的T_MDAP即為排序結果。多目標動態調整優先級(multi-objective dynamic adjusting priority,MODAP)算法描述如下。

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

變更影響路徑集IFCPS

Output:動態調整排序后的測試用例集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)//計算優先級排序綜合指標

end foreach

T_FS←Sort(T_FS,Priority_FS)//根據優先級排序綜合指標對測試用例從高到低排序

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

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

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

Priority_MDAP←Add(Update_Priority(t,CalculateG(Execute(t))))//根據執行信息重新計算排序指標

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

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

end while

return T_MDAP

End

2.3 測試用例的再次選擇

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

測試用例的再次選擇可從相關概念和算法設計兩方面敘述。

2.3.1 再次選擇相關概念

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

(6)

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

(7)

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

(8)

2.3.2 再次選擇算法設計

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

Input:動態調整排序后的測試用例集T_MDAP

初次選擇后的測試用例集對應的FCP集T_FS_FCPS

變更影響路徑集IFCPS

變更影響關鍵子路徑集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)

//生成關鍵變更包含矩陣CI

CI←Generate_CI(IFCPS,ICFCPS)

//根據T_IFCP及CI，生成用例變更關鍵影響覆蓋矩陣

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_RS←T_RS+{t}//將該測試用例加入再次選擇后的測試用例集中

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

ICFCPS_UC←ICFCPS_UC-{icfcps}//去掉統計出的變更影響關鍵子路徑

end while

return T_RS

End

3 實驗與評測

3.1 實驗數據與評測指標

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

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

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

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

(9)

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

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

(10)

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

3.2 實驗對比與結果分析

設計實驗從兩方面出發對本文方法的有效性進行驗證。一方面，所提混合優化方法分為三個步驟，可比較每一個步驟執行后的結果，分析三個步驟依次執行是否能逐步增強優化；另一方面，選擇文獻[8]和文獻[11]所提方法與本文方法進行實驗對比，驗證本文方法是否能取得更好的優化效果。

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

3.2.1 混合優化方法的三個步驟的優化效果實驗對比

所提出的混合優化方法分為三步，每一步都在前一步的基礎上進行，可驗證每一步是否能比前一步的優化效果更好。實驗的對比結果如圖2所示。

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

3.2.2 與已有方法的對比

本文方法與文獻[8]、文獻[11]方法都為混合優化方法，可將這三種方法都在函數粒度上進行對比實驗，以驗證本文方法的有效性。結果如圖3所示。

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

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

4 結論

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