基于函数调用路径的测试用例混合优化方法

张李梅，牟永敏，张志华，崔展齐

(北京信息科技大学网络文化与数字传播北京市重点实验室，北京 100101)

回归测试作为软件开发和维护周期中非常重要的一个阶段，产品的不断迭代更新导致测试的成本越来越高[1]。如何在有限的资源以及保证测试质量的前提下，对回归测试用例进行优化，已经成为软件工程领域的研究热点之一[2]。回归测试的优化技术主要围绕着测试用例的约简，测试用例的选择，测试用例的优先级排序等主题进行研究[3]。

回归测试用例的约简技术通过识别并去除冗余的测试用例，以达到减少测试用例的目的[4]。回归测试用例选择技术通过从测试用例集中选取与变更相关的测试用例子集，从而降低测试用例集的规模[5]。回归测试用例的优先级排序技术根据某种规则对测试用例的执行次序排序，提高测试的效率[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]。可表示为FCP(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的变更影响分析的基础上，提出一种测试用例混合优化方法。首先选择出覆盖了变更影响路径集的测试用例，然后利用测试用例的执行信息对测试用例的变更覆盖率、故障发生率、缺陷影响率和执行开销率重新赋值，进而动态调整排序，最后从覆盖了相同变更影响关键子路径的测试用例中选择出排序更靠前的测试用例，三步生成最后的测试用例集。实验结果证明，本文方法可以有效减少测试用例的数量，同时可以避免损失一部分更有价值的测试用例，减少了额外开销，提高了回归测试的效率。