基于函数调用路径的测试用例优先级排序

牟永敏，李慧丽

(北京信息科技大学计算机学院，北京 100101)

1 概述

软件的调试、升级与维护往往需要更改部分代码，为了验证修改后的程序是否引发新的问题或对未修改的部分造成影响，就需要频繁地对软件进行回归测试[1]。

回归测试中最简单的方法就是全部重测，但是实际情况是更改的代码往往只是系统中很小的一部分，对整个系统的重测会耗费大量的时间，造成人力和物力的浪费，因此实际工作中一般采用选择性回归测试方法[2-3]。选择性回归测试是当源代码修改后，仅对那些跟源代码变化相关的模块进行测试。

测试用例的选择、测试用例集约简以及测试用例优先级排序等技术是回归测试研究的关键问题。其中，测试用例优先级技术认为不同测试用例对于测试目标的完成有着不同的贡献程度，为了能够更快地达成测试目标，有必要将不同的测试用例进行比较和排序，然后优先执行相对重要的测试用例[4]。目前测试用例优先级排序技术可分为覆盖率技术和非覆盖率技术[5]。

基于覆盖的测试用例优先级技术根据测试用例的历史覆盖信息，设计优先级排序方法，但其考虑的优先级影响因素过于单一。为此，本文提出一种基于函数调用路径的测试用例集优化方法。以函数调用路径覆盖分析为基础，分析函数调用路径中影响测试用例优先级的因素，设计测试用例优先集量化方法，并且根据测试执行情况动态调整优先级，以进一步优化优先级排序。

2 基本概念

2.1 基于函数调用路径的覆盖分析

路径覆盖测试是一种针对白盒测试的常用充分性准则，它观察程序运行的整个路径[6]。但是即使是规模很小的程序，包含的逻辑路径数量也是相当大的，而在大型程序中进行完全的路径测试几乎是不可能的[7-8]。基于函数调用路径的覆盖分析技术是在保证每个函数完成单元测试的前提下，将覆盖分析粒度由语句级扩展到函数级，分析函数调用的控制逻辑关系，这样既能避免路径的爆炸式增长，又可以保证测试的充分性。

RegressiontestC1.0[9]是自主开发的基于函数调用路径的覆盖分析工具，利用该工具可以得到全局静态路径集和测试用例执行对应的动态路径。其整体思路是：通过对软件源代码的静态分析，绘制带有控制逻辑的函数调用关系图，给出所有可能的函数调用路径，称为全局静态路径集[10]；对函数首尾和控制逻辑关键字进行插装预处理，输入测试用例，执行预处理后的程序，根据装点信息得到该测试用例对应的动态函数调用路径，下面给出相关的定义。

定义1函数调用路径是指根据函数调用关系得到的由程序入口点到出口点的一个函数名序列，表示为Pi={Vi0,Vi1,…,Vim}，Vij为函数名；Vij和Vij+1的相邻关系表示Vij调用了Vij+1。

定义2静态路径是指对源代码进行静态分析，根据函数调用关系得到函数调用路径。全局静态路径集是全部静态路径的集合，表示为B(S,C)={P1,P2,…,Pn}，其中，S是源代码；C是函数调用关系准则；Pi是函数调用路径。

定义3动态路径是指输入测试数据后，程序动态执行时实际执行的函数调用路径，表示为L(S,ti)={P1,P2,…}，

其中，S是指插装后的源代码；ti指测试用例。

例如，若源代码为：

其中包含函数：main，scanf，add，f2，multi。根据函数调用关系，得到4条函数调用路径形如P1={main,scanf}，P2={main,scanf,add}，P3={main,scanf,f2}，P4={main,scanf,multi}。此程序的全局静态路径集S={P1,P2,P3,P4}。当输入测试数据a=2时，程序执行对应的动态路径为P3和P4，如图1所示。

图1 函数调用路径

基于函数调用路径的回归测试用例集确定的基本思想是：对新旧版本源程序进行比较，采集函数变更点数据，函数变更点是指产生了变更的函数。在全局静态路径集中标出所有经过变更点的路径，称为变更路径集[11]。回归测试时覆盖全部变更路径集，既能测试变更模块，也能保证受变更模块影响的相关模块的正确性。因此，变更路径集即回归测试的测试需求，每一条变更路径即一条测试需求。覆盖变更路径集中的一条或多条路径的测试用例即回归测试用例集。

例如上例中的函数minus和multi发生了变更，minus和multi即变更函数。路径P3和P4即变更路径集。P3和P4分别对应测试需求2个测试需求。若有如表1所示的测试用例-函数调用路径关系，则回归测试用例集为t3,t4,t5,t6。其中，×表示测试用例ti覆盖函数调用路径Pj。

表1 测试用例-函数调用路径关系

2.2 测试用例优先级技术

测试用例优先级技术认为不同测试用例对于测试目标的完成有不同的贡献程度，在回归测试时将测试用例按其重要程度进行优先级排序后使用，能更快地达成测试目标。

例如，某被测程序中测试用例的缺陷检测情况如表2所示。其中，×表示测试用例Ti检测出错误Fj。如果按照T1-T10的顺序执行测试用例，显然直到执行到T3才会检测出错误，且只有所有测试用例全部被执行才能检测出所有的错误。显然T4,T7,T9,T10可以检测出全部的错误，如果按照T3-T4-T7-T9-T10-T1-T2-T5-T6-T8的顺序执行，测试用例能够更早地检测到程序的错误。

表2 测试用例缺陷检测情况

但是在测试用例被执行前，测试用例所检测出的错误是无法预知的，研究发现依据一定的覆盖准则和测试用例执行的历史信息，尽快达到覆盖标准能提高测试用例的检错率。测试用例优先级技术就是依据测试的历史信息，以代码覆盖率或检错效率等为标准，为每个待复用的测试用例赋予一个优先级，并在回归测试过程中按优先级顺序选取和执行这些测试用例。

测试用例优先级技术的核心问题是如何确定和表述测试用例的重要程度[12]，目前主要是根据测试用例历史覆盖率排序测试用例优先级，即优先运行覆盖能力较强的测试用例。但是传统的优先级排序方法方法都只选取代码覆盖信息作为测试用例的特征加以度量，而忽略了其他影响测试用例优先级的因素，且缺乏动态性。

3 优先级排序算法

3.1 测试用例优先级量化方法

基于函数调用路径的测试用例优先级排序方法以测试用例对函数调用路径的历史覆盖信息作为优先级的一个影响因子，在此基础上分析函数调用路径与检错结果的关系，提取单元测试时函数中检测出缺陷的个数和函数的扇入系数2个特征作为优先级的影响因子对优先级进行排序。

为了便于描述，给出以下相关定义：

定义4(测试覆盖矩阵)测试用例集 T={t1,t2,…,tn}，变更路径集，即测试需求集 P={P1,P2,…,Pm}，则测试覆盖矩阵tCM是一个m×n阶矩阵，当ti在执行过程中执行到了函数调用路径路径Pj时，元素δij=1，否则δij=0。

定义5(测试用例的覆盖路径集)测试用例ti的覆盖路径集 P(ti)(P(ti)∈P)是一个函数调用路径集，其中包含执行测试用例ti时所执行到的所有P中的函数调用路径。

定义6(函数调用路径的执行用例集)Pj的执行用例集t(Pj)(t(Pj)∈T)是一个测试用例集，为测试用例集T中所有能够覆盖路径Pj的测试用例。

(1)测试用例函数调用路径覆盖能力影响因子

测试用例ti函数调用路径覆盖能力是指，测试用例ti的覆盖路径集 P（ti）中的路径条数 |P（ti）|。在回归测试过程中，挑选覆盖能力强的测试用例优先执行，能尽快达到覆盖标准，满足测试覆盖需求。因此，将测试用例函数调用路径覆盖能力应用于优先级排序中，使覆盖能力强的测试用例有较高的优先级，保证其更早地被执行以有效提高测试效率。用下式量化计算第i个测试用例ti的函数调用路径覆盖能力对优先级的影响值

其中，Ni为测试用例ti执行到的路径条数 |P（ti）|，即测试用例ti的函数调用路径覆盖能力；max{N}为所有测试用例中函数调用路径覆盖能力的最大值。式(1)将测试用例函数调用路径覆盖能力影响值量化至0～1的数值区间。

(2)测试用例覆盖路径检错指标影响因子

软件测试的二八原则指出，软件中约20%的系统模块包含了约80%的软件缺陷。因此，单元测试时检测出错误较多的模块应作为重点测试的模块。模块的扇入系数是指，直接调用该模块的上级模块的个数。测试经验表明，一个模块出现错误很可能会引起调用该模块的其他模块出错，高扇入的模块会引起这种错误的迅速扩散。在C语言中单元测试的一个模块通常是指一个函数。因此，本文将单元测试时函数中检测出错误的个数和函数的扇入系数应用于优先级排序中。用式(2)、式(3)量化其对第i个测试用例ti优先级的影响值

1)函数调用路径检错指标

若已知函数调用路径 Pk={Vk0,Vk1,…,Vkm)，则路径Pk的函数调用路径检错指标量化值为：

其中，Vkl∈Pk，且在回归测试的单元测试阶段函数Vkj中至少检测出一处错误；Ekj为单元测试时函数Vkj中所检测出的错误个数；max{E}指在回归测试的单元测试阶段所有被测函数中检测出的错误个数最大值；CVkj为函数vkj的扇入值；max{CV}是指在回归测试的单元测试阶段，所有至少检测出一处错误的函数中函数扇入值的最大值。式(2)将函数调用路径检错指标量化至0～1的数值区间，使得错误个数多、扇入系数高的函数所在的函数调用路径有更高的量化值。

2)测试用例的覆盖路径检错指标

测试用例ti的覆盖路径检错指标是指测试用例ti的覆盖路径集中所有元素的函数调用路径检错指标平均值：

其中，n为ti覆盖路径集中的元素个数。式(2)、式(3)使检测出错误概率较高的测试用例有更高的优先级量化值，保证尽早地检测出尽量多的错误。

(3)测试用例优先级量化取值

综合测试用例函数调用路径覆盖能力和测试用例覆盖路径检错指标，第i个测试用例ti的优先级取值Vi为：

3.2 测试用例优先级优化算法

测试用例的执行将不断地覆盖函数调用路径，因此，在测试执行过程中变更路径集可以分为2个部分，尚未被任何执行过的测试用例覆盖的未覆盖路径集testRt_UC，以及已经至少被一个执行过的测试用例覆盖的覆盖路径集testRt_C。如果每次选择的测试用例tj使tj尽可能多地满足未覆盖路径集，而不关注其对覆盖路径集的覆盖情况，则这种测试用例优先级选择方法将能更快速地覆盖所有的变更路径集。因此，本文在测试用例执行过程中，根据测试用例对变更路径集的覆盖情况动态调整测试用例函数调用路径覆盖能力：，其中，为动态函数调用路径覆盖能力取值；为|P(ti)∩ testRt_ UC|，即测试用例ti执行到的尚未被任何已执行过的测试用例覆盖的函数调用路径条数。

测试用例优先级优化算法在测试用例执行过程中，根据覆盖覆盖路径集和未覆盖路径集的变化，计算动态函数调用路径覆盖能力取值，从而动态调整测试用例优先集量化值，使优先级排序方法尽快覆盖所有测试需求(函数调用路径)，算法描述如下：

输入 T为回归测试用例集；P为变更路径集；tCM为测试覆盖矩阵

输出 排序后的测试用例集T’

变量 testRt_UC为未覆盖路径集；testC_UR为未执行测试用例集

Begin

/*初始化*/

sort(T);//根据测试用例优先级量化值对T中测试用例排序testRt_UC=P;testC_UR=T;

/*测试用例集优化排序*/

while(testC_UR≠φ)

run(t1);//执行测试用例testC_UR中排序第一的测试用例，//即尚未执行的测试用例中优先级取值最高的测试用例

testC_UR=testC_UR–t1;

if(testRt_UC≠φ)

if(P(t1)∩ testRt_UC≠φ)

/*遍历测试用例t1的覆盖路径集，实现优先级的动态调整*/

for each(Pj∈(P(t1) ∩ testRt_UC))

/*动态调整Pj的执行用例集t(Pj)中所有测试用例的优先级量化值*/

for each(tk∈t(Pj))

modify(Vk);//动态调整测试用例tk的优先级量化值

end for;end for;

sort(testC_UR);

end if;

else

/*若未覆盖路径集为空，则按优先级取值依次执行所有测

试用例*/

for each(ti∈testC_UR)

run(ti);end for;

testC_UR=φ

end if;

testRt_UC=testRt_UC-P(t1);end while;

在最外层的while循环中，首先执行当前测试用例优先级取值最高的测试用例t1，并在未执行测试用例集testC_UR移除该测试用例。若未覆盖路径集为空，则说明所有变更路径都已经至少被覆盖一次，此时未覆盖路径集不会再发生变化，测试用例的优先级取值也就不会再发生变化，因此按优先级取值依次执行所有测试用例；若未覆盖路径集非空，则遍历测试用例t1的覆盖路径集P(t1)与未覆盖路径集testRT_UC的交集，动态地调整每条路径的执行用例集中的测试用例优先级取值。最后在未覆盖路径集中testRt_UC移除测试用例t1覆盖路径集P(t1)。循环执行整个过程，直至所有测试用例都被执行。

4 实验与评测

4.1 优先级排序方法度量标准

测试用例优先级排序方法的目标是为了提高测试的缺陷检测率，尽早发现程序中的错误。文献[12]提出了APFD度量标准作为优先级排序方法的度量指标。

APFD即缺陷检测加权平均百分比，若测试用例集T包含n个测试用例，该测试用例集能够检测出的错误集合F中包含m个错误，则测试用例集T的一个顺序集T′的APFD值定义为：

其中，T1F为顺序集T′中第一个检测出错误i的测试用例在T中的位置。

APFD的取值范围是0～1。APFD的值越高，表示对应测试用例顺序集缺陷检测率越高。

例如测试用例缺陷检测情况如表2所示，若按照T1-T10顺序执行测试用例，则该顺序集的APFD值为：

若按照T1-T10-T3-T4-T7-T9-T10-T1-T2-T5-T6-T8的顺序执行，则该顺序集的APFD值为：

4.2 实验结果

基于函数调用路径的测试核心关注点是程序的规模，函数调用路径的条数等信息，因此选取了代码行数几十行到几百行、函数调用路径条数为数十条到上百条的5个实用C语言程序作为被测程序进行对比实验。

针对每一个被测程序执行3轮测试。第一轮执行未排序的测试用例集，第二轮执行仅使用优先级量化方法排序的测试用例集，第三轮执行使用测试用例优先级优化方法排序的测试用例集。被测程序的代码行数、函数调用路径条数、测试用例数、缺陷数以及3轮顺序集对应的APFD值如表3所示。

表3 优先级排序算法的实验数据

通过实验分析发现：

(1)使用优先级量化方法排序后的测试用例顺序集APFD值要高于未使用任何排序方法的测试用例顺序集APFD值，且两者差值较大，说明优先级量化方法能明显提高测试的缺陷检测率。

(2)使用测试用例优先级优化方法动态排序后的测试用例顺序集APFD值要高于仅使用优先级量化方法排序的顺序集APFD值，但是提升幅度不明显，一般能提高几个百分点。在测试用例数和缺陷数较少的情况下，该优化方法可能失效。例如被测程P1，第三轮APFD值和第二轮APFD值无差别。因为优化方法本身会有资源和时间的开销，在实际测试工程中要综合考虑软件规模、测试开销等问题决定是否选用优化方法。

(3)随着软件规模的增加，测试用例优先级量化方法和测试用例优先级优化方法对缺陷检测率的提升都更加稳定。

5 结束语

传统的基于覆盖的优先级技术仅考虑代码覆盖信息，而忽略了其他优先级影响因素。本文采用基于函数调用路径的测试用例优先级排序方法，将测试用例的历史覆盖信息和其他优先级影响因素应用于优先级量化排序。按照此方法排序测试用例，能尽快地检测到程序中的缺陷，使系统的调试修改工作尽早进行，降低风险。而根据测试执行动态调整优先级的优化方法，在测试用例数和缺陷数较多的测试中能进一步提高缺陷检测速度。

随着软件规模的不断扩大，软件系统的迭代开发导致测试用例不断被设计、修改和执行，其组成的测试用例集规模将更加庞大。如何寻找影响测试用例优先级的各种因素，并综合各种因素制定合理的优先级计算方法，进一步提高测试效率，并保证算法的成本开销是优先级研究的方向之一。

[1]郭晶晶,高建华.基于冗余测试用例的最小测试用例集生成方法[J].计算机工程,2010,36(1):45-48.

[2]彭园园.回归测试方法及测试用例优化研究[D].武汉:武汉理工大学,2009.

[3]Mu Yongmin,Zheng Yuhui,Zhang Zhihua,et al.The Algorithm of Infeasible Paths Extraction Oriented the Function Calling Relationship[J]. Chinese Journal of Electronics,2012,21(2):236-240.

[4]屈 波,聂长海,徐宝文.基于测试用例设计信息的回归测试优先级算法[J].计算机学报,2008,31(3):431-439.

[5]屈 波,聂长海,徐宝文.回归测试中测试用例优先级技术研究综述[J].计算机科学与探索,2009,3(3):225-233.

[6]Mu Yongmin,Wang Rui,Zhang Zhihua,et al.Automatic Test Method Research on the Word Part of Document Format Translator[J].Chinese Journal of Electronics,2013,22(1):55-60.

[7]侯 芸,顾 刚,高海昌,等.一种路径覆盖自动生成的改进方法[J].计算机工程,2007,33(4):67-69.

[8]杜庆峰,李 娜.白盒测试基路径算法[J].计算机工程,2009,35(15):100-102,123.

[9]张志华,牟永敏.基于函数调用的路径覆盖生成技术研究[J].电子学报,2010,38(8):1808-1811.

[10]Zheng Huiyu,Mu Yongmin,Zhang Zhihua.Research on the Static Function Call Path Generating Automatically[C]//Proc.of the 2nd IEEE International Conference on Information Management and Engineering.Chengdu,China:[s.n.],2010:405-409.

[11]Jiang Yu,Mu Yongmin,Zhang Zhihua.Modificatory Indentification Algorithm Research for Source Code Oriented[C]//Proc.of the 2nd International Workshop on Education Technology and Computer Science.Wuhan,China:[s.n.],2010:388-391.

[12]Rothermel G,Untch R H,Chu Chengyun,et al.Prioritizing Test Cases for Regression Testing[J].IEEE Transactions on Software Engineering,2001,27(10):929-948.