基于历史数据和多目标优化的测试用例排序方法

李兴佳，杨秋辉，洪 玫，潘春霞，刘瑞航

（四川大学 计算机学院，成都 610065）

0 引言

回归测试是对修改后的软件进行重新测试，以确保未因修改代码而引入新的缺陷。由于软件不断演化，回归测试中的测试用例集会变得逐渐庞大与复杂，导致测试成本不断增大。在持续集成开发环境下，产品迭代速度不断加快，增大了回归测试成本，如在Google 中，开发人员平均每秒钟提交一次代码，每天需要执行超过1.5 亿次测试［1］，测试成本较高。如何有效对测试用例集进行优化、减少测试用例执行成本、提升回归测试效益，吸引了众多国内外学者进行研究。

回归测试用例优化技术可分为测试套件最小化技术、测试用例选择技术和测试用例排序技术［2］。测试用例排序是按照某种规则安排测试用例的执行次序，使具有高优先级的测试用例更早执行，以尽快检测出缺陷，提升回归测试效率。

本文在已有研究的基础上，提出了一种基于历史数据和多目标优化的测试用例排序方法。首先在历史测试数据分析阶段，将测试不同功能且具有不同代码覆盖范围的测试用例进行区分，同时挖掘测试用例间的关联规则；然后在多目标排序阶段，在聚类结果的基础上，使用多目标优化技术对测试用例集排序，以将相似的测试用例分隔开；最后在动态调整阶段，根据测试用例间的执行失败关联规则，动态调整测试用例执行顺序。本文方法旨在提升测试的缺陷检测速率，使具有多样性和更有可能检测到缺陷的测试用例优先执行，从而使测试人员更快发现缺陷，提升回归测试效益。

1 相关工作

测试用例排序技术可分为使用静态信息的排序技术、使用动态信息的排序技术和使用混合信息的测试用例排序技术［3］。

Xiao 等［4］使用支持向量机预测测试用例检测到缺陷的可能性，并对测试用例聚类，最后进行簇内排序和簇间排序。Najafi 等［5］对揭示更多缺陷和平均执行时间更少的测试用例赋予更高的优先级。Noor 等［6］使用多种距离度量方法计算测试用例相似性，并优先执行和历史执行失败的测试用例相似的测试用例。Busjaeger 等［7］根据测试用例的代码覆盖率、内容相似度、失败历史等信息，使用支持向量机对测试用例排序。De Oliveira Neto 等［8］根据测试用例在测试需求、测试依赖和测试步骤方面的相似性，去除相似性高的测试用例，减少了测试用例数量和测试执行时间，同时保证了测试用例的多样性。Carlson 等［9］使用层次聚类算法对测试用例进行聚类，然后对每一类测试用例进行排序，生成最终的排序序列。Thomas 等［10］利用语义主题模型生成测试用例的主题分布，然后计算测试用例间的相似性，在排序过程中，将与已排序用例集具有更低相似性的测试用例优先排序。Pradhan等［11］提出了一种利用关联规则和多目标搜索的黑盒测试用例排序方法，首先挖掘测试用例的关联规则，然后使用非支配排序遗传算法（Non-dominated Sorting Genetic AlgorithmⅡ，NSGA-Ⅱ）对测试用例排序，在按照该顺序执行过程中，根据关联规则，动态调整执行顺序。

目前的测试用例排序技术在判断测试用例相似性时，仅利用了单一的静态信息或动态信息；在利用多目标排序技术时，没有考虑测试用例冗余的问题，不利于提升排序序列的揭错速率。针对现有方法存在的不足，本文提出了一种基于历史数据和多目标优化的测试用例排序方法。

2 本文方法

为了提高检测速率，尽早发现错误，排序序列应满足以下要求：1）让测试不同功能且具有不同代码覆盖范围的测试用例尽早执行；2）在一定时间内尽可能执行更多的测试用例；3）使可能检测到缺陷的测试用例尽早执行。为了满足以上要求，所提方法的整体流程包括三个阶段，分别为：历史测试数据分析、多目标排序和动态调整执行次序，整体流程如图1 所示。

图1 本文方法的整体流程Fig.1 Overall flow of the proposed method

2.1 基于文本主题和代码覆盖相似性对测试用例聚类

已有研究［9］证明，如果测试用例具有一些共同的属性（如代码覆盖范围），那么同一组中的测试用例可能具有类似的故障检测能力。Carlson 等［9］通过实验对比了仅使用代码覆盖率、代码复杂性、有关实际故障的历史数据对测试用例进行排序和将上述指标分别与聚类算法结合后对测试用例排序两种方式的平均故障检测率（Average Percentage of Faults Detected，APFD），结果表明，结合聚类算法后APFD 值有明显提升，其中代码覆盖率指标效果更好。因此将聚类算法应用于测试用例优先级排序技术，可以提升排序效果。

基于文本主题相似性的方法从测试用例静态文本的角度出发，考虑了测试用例在功能上的相似性，提升了排序效果［10］。但是仍旧存在以下问题：对于如基于文本主题相似性的局限性示例中的被测方法和测试用例，测试用例1 和测试用例2 只有参数不同，从文本相似性角度分析，这两个测试用例属于同一类；但是这两个测试用例测试的代码块完全不同，不应归为同类测试用例。因此本文同时考虑了基于代码覆盖的相似性，从测试用例动态执行信息的角度出发，考虑测试用例语句级别代码覆盖范围的相同程度。为更全面地评价测试用例的相似性，在分别计算出基于文本主题和基于代码覆盖的相似性后，将这两种相似性进行加权结合。

基于文本主题相似性的局限性示例如下。

基于文本主题的测试用例相似性计算方法如下：将预处理后的测试用例文本信息集Tpre=｛tp1，tp2，…，tpn｝（tpi代表测试用例ti的文本信息，n为测试用例总数）使用隐含狄利克雷分布（Latent Dirichlet Allocation，LDA）模型进行主题建模，得到D=｛d1，d2，…，dn｝，其中di表示测试用例ti的主题分布；topicj表示主题j。然后将主题分布di视为向量并计算向量之间的距离以度量测试用例的相似性，距离值越小，测试用例越相似。最终得到的相似矩阵是一个对称矩阵，其中disij即为测试用例ti与tj之间的距离值。基于文本主题的测试用例相似性计算流程如图2 所示。

图2 基于文本主题的测试用例相似性计算流程Fig.2 Test case similarity computing process based on text topic

已有研究［12-13］证明，语句级别覆盖在测试用例排序技术中表现最好；因此，本文采用语句级别的覆盖来计算测试用例代码覆盖的相似性。首先，统计测试用例执行后的语句覆盖情况TC=｛tc1，tc2，…，tcn｝，其中tci表示测试用例ti覆盖的语句集合；然后，使用杰卡德距离［14］度量两个测试用例间的相似性，两个测试用例语句覆盖范围重合越大，杰卡德距离越小，也就代表两个测试用例越相似。最终得到一个与图2 中结构相同的相似矩阵。

将这两种动静态相似性结合的表达式如式（1）所示：

其中：Similarityfinal是加权计算后的相似矩阵；Similaritytopic是基于文本主题的相似矩阵；Similaritycoverage是基于代码覆盖的相似矩阵；α是权重系数。

最后，根据加权结合后的测试用例之间的相似性距离矩阵，使用层次聚类算法将测试用例集中的测试用例划分为不同的类。聚类结果为C=｛c1，c2，…，cz｝，其中ci代表第i个类簇。

2.2 测试用例的关联规则挖掘

测试用例之间可能存在这样的关系：在历史执行中，当一个测试用例执行失败时，其余一个或多个测试用例往往同时也失败；那么可以认为这个测试用例和与它经常同时失败的测试用例之间存在关联规则，表示为ti→（ti1，ti2，…，tik），意思为当ti执行失败时，ti1，ti2，…，tik往往也失败，并且认为每个失败的测试用例都是由一个单独的错误引起的［11］。研究［5，11，15-16］表明利用这些隐含的关系，可以提升回归测试的有效性。

本文使用Apriori 算法［17］挖掘历史执行信息中存在的关联规则，将每次执行结果中所有失败的测试用例看作一个事务，将事务中每一个失败过的测试用例看作一个项。该算法过程主要分为两步：1）通过迭代检索出测试用例执行信息数据库中支持度不小于设定阈值的项集，这些项集被称作频繁项集；2）从频繁项集中获取置信度不小于设定阈值的关联规则。支持度公式如式（2）所示：

其中：number(AB)表示同时出现测试用例A和B的事务的总数；number(AllRecord)表示总事务数；support(A→B)表示关联规则(A→B)的支持度，即A和B同时发生的概率。

置信度公式如式（3）所示：

其中：number(AB)表示同时出现测试用例A和B的事务的总数；number(A) 表示出现测试用例A的事务总数；confidence(A→B)表示关联规则(A→B)的置信度，即在A发生的情况下B发生的条件概率。

在挖掘到的关联规则中可能存在这样的情况：某些存在关联规则的测试用例揭示的是相同的缺陷，这种情况并不能有效提升揭错效率，因此需要进行筛选。筛选过程的核心思想是：若两个测试用例揭示相同的缺陷次数超过共同失败次数的一半，那么在A揭示这个缺陷后，就没有必要立即执行关联的测试用例B了；因为B在很大概率下也会揭示相同的缺陷，因此应将其视为无效。在挖掘关联规则后，对这种类型的关联规则进行筛选，本文仅保留有效的关联规则，用于调整测试用例执行次序。最终得到关联规则集合如R=｛t1→（t2，t3），t21→（t12），…，ti→（ti1，ti2，…，tik）｝。

2.3 多目标排序和动态调整执行次序

Epitropakis 等［18］通过对比使用多目标优化算法和其他方法的排序效果，证明了使用多目标优化算法解决测试用例排序问题的有效性。多目标优化问题是求出使各个目标尽可能最优的解，这种解通常是一组Pareto 最优解。多目标优化［19］问题的表达式如式（4）所示：

其中：x=(x1，x2，…，xh) ∈Ω是h维决策变量，Ω是决策空间，表示每一维决策向量的上下界；e是子目标数；f1(x)至fe(x)是各个子目标优化函数。

本文采用带精英策略的非支配排序遗传算法NSGA-Ⅱ［20］在每个类簇内进行多目标排序。该算法具有运行速度快、解集收敛性好的优点，目前在多目标测试用例优先级排序领域中应用较为广泛。首先在每个类簇内进行多目标排序，得到，TS_ci表示类簇ci的排序序列；然后依次从每个排序序列中抽取测试用例，生成最终的排序序列TS。

本文中使用的优化子目标分别为代码覆盖率最大化、历史执行失败率最大化以及执行时间最小化，在迭代过程中，越满足这三个目标的个体，越容易被保留下来。

代码覆盖率最大化的函数表达式如式（5）所示：

其中：SCti表示测试用例ti的语句覆盖数量；h代表排序测试用例集的数量；i代表测试用例在排序序列中位置；ssc为测试用例集中所有测试用例语句覆盖数量的和。

历史执行失败率最大化的函数表达式如式（6）所示：

其中：FRti表示测试用例ti的历史执行失败率；sfr为测试用例集中所有测试用例FR值的和；其余参数含义同式（5）中参数一致。

执行时间最小化的函数表达式如式（7）所示，

其中：TIMEti表示测试用例ti的执行时间；st表示执行时间总和；其余参数含义同式（5）中参数一致。

生成最终排序序列的过程为：循环遍历每个类簇内的排序序列TS_ci，对于第j轮遍历，若TS_ci的长度大于等于j，则抽取第j个测试用例添加到TS的末尾；否则，跳过TS_ci，直至遍历完所有的测试用例，得到最终的排序序列TS={t1，t2，…，tn}。最终的排序序列靠前部分既保留了多样性，又保留了每一类中最有可能发现缺陷的测试用例，增大了快速发现不同缺陷的机会。

为了提升执行序列的缺陷检测速度，当测试用例执行时，根据测试用例间的执行失败关联规则动态调整测试用例执行次序，让更可能检测到缺陷的测试用例优先执行。

使用关联规则动态调整测试用例排序次序的主要流程为：在按排序序列TS执行过程中，若当前测试用例ti执行失败且有关联规则ti→（ti1，ti2，…，tik），则立即执行ti1，ti2，…，tik中尚未执行的测试用例，然后再依次执行TS序列中剩余测试用例，直至达到终止条件或测试用例全部执行完毕。以哈希表的形式存储测试用例和关联规则，其中每个测试用例仅被执行1 次，时间复杂度为O（n），n为测试用例总数；获取k个相关联的测试用例的时间复杂度为O（k），总时间复杂度为O（nk）；需要存储的变量有排序序列、关联规则和根据关联规则调整的测试用例，因此空间复杂度是O（n）。动态调整过程如算法1 所示。

3 实验与结果分析

3.1 实验对象

SIR（Software-artifact Infrastructure Repository）库［21］是 一个广泛应用于回归测试用例集优化研究的开源数据库。本文从SIR 库和GitHub 共获取5 个Java 开源项目作为实验对象。表1 介绍了实验的项目信息，其中：“新版本缺陷数”代表每个项目最新版本所包含的缺陷数；“历史缺陷数”代表项目在历史版本中所揭示缺陷的总数；“历史版本数”也为“历史执行记录数”，是将测试用例在每个历史版本上的执行结果作为一次执行记录。获取自SIR 库的ant、derby 和jboss 项目历史版本数相对较少，因此将缺陷数较多的版本划分为多个版本，以增加历史版本数。

表1 实验项目信息Tab.1 Information of experimental projects

3.2 评估指标

评价指标选择平均故障检测率（APFD）和基于成本的平均故障检测率（APFD cost-cognizant，APFDc）。APFD 是指测试套件在执行过程中检测到缺陷的百分比，该评价指标被广泛地应用于评估测试用例排序技术，计算方法如式（8）所示：

其中：TFi表示首次揭示第i个缺陷的测试用例在排序序列中的位置；m为缺陷的总个数；n代表测试用例数量。检测到不同缺陷的测试用例越排在前面，APFD 值越大，说明排序序列的揭错速度越快，对应的排序方法效果也越好。

APFDc 增加了对测试用例成本和缺陷严重程度的度量。文献［18，22］对传统的APFDc 进行简化，仅考虑测试用例执行时间，将缺陷严重程度都视为1。本文采用简化后的APFDc 指标，其计算公式如式（9）所示：

其中：m、n、TFi表达的含义与式（8）中一致；TIMEj代表执行第j个测试用例所花费时间。与APFD 值一样，APFDc 值越大，对应排序方法效果越好。

3.3 实验设计

首先使用层次聚类算法对测试用例集聚类，经实验验证，α值为0.7 时效果最好；使用Aprior 算法挖掘关联规则，设置最小置信度minconf为0.8；由于不同项目具有的历史执行记录数不同，对应的项集频繁程度不同，设置最小支持度minsup的取值范围为0.1～0.5。然后使用NSGA-Ⅱ在每个类簇内对测试用例排序，再生成最终的排序序列。最后动态调整测试用例执行次序，直至所有测试用例执行完毕或达到终止条件。统计执行结果的APFD 值和APFDc 值。

为验证本文方法的有效性，在5 个Java 项目上将本文方法与下述几种方法的排序结果进行对比。

1）随机排序方法。将测试用例集以随机顺序执行，并统计执行结果的APFD 值和APFDc 值；由于该方法存在随机性因素，因此记录30 次执行结果进行比较。

2）文献［9］方法。执行Carlson 等［9］提出的基于聚类的排序方法，并统计执行结果的APFD 值和APFDc 值；由于该方法不存在随机性因素，该方法仅需执行一次。

3）文献［10］方法。执行Thomas 等［10］提出的基于主题模型的排序方法，并统计执行结果的APFD 和APFDc 值；由于使用LDA 模型推导测试用例主题分布时，使用了随机数种子，因此记录该方法30 次执行结果进行比较。

4）文献［11］方法。执行Pradhan 等［11］提出的基于关联规则和多目标优化的排序方法，并统计执行结果的APFD 和APFDc 值；由于多目标遗传算法具有随机性，因此记录该方法的30 次执行结果进行比较。

3.4 实验结果与分析

本文方法综合利用了测试用例的静态信息和动态信息。基于测试用例静态信息的处理主要包括计算测试用例文本主题和代码覆盖相似性、层次聚类与多目标排序，在测试用例本身未改变前，上述过程的结果可以重复使用。基于动态信息的处理主要包括关联规则挖掘与动态调整执行次序两个过程，其中动态调整执行次序到的时间复杂度为O（nk）。

3.4.1 APFD结果

表2 展示了在5 个项目上分别使用5 种排序方法所得到的平均APFD 值和APFDc 值。

表2 不同项目使用不同排序方法的平均APFD值和APFDc值对比Tab.2 Comparison of average APFD values and APFDc values of different projects using different prioritization methods

从表2 中可以看出，在大部分项目中，本文方法得到的APFD 值更高。尤其是在ant 项目中，本文方法相较于随机方法提升了24.13%，提升明显；相较于文献［9］、文献［10］和文献［11］方法，分别提升了15.53%、3.78%和10.35%。在derby 项目中，本文方法相较于除随机方法外的其他方法优势不明显，是因为该项目中部分测试用例能单独检测出较多的缺陷，这类测试用例被排在靠前位置时，总能导致排序结果的APFD 值较高。在jboss 项目中，相较于文献［10］和文献［11］方法提升不明显的原因也是如此。在commons-lang项目中，本文方法相较于文献［11］方法表现差一些，通过分析项目发现：该项目的测试用例间的相似性较差，而本文使用了相似性进行聚类，文献［11］方法未考虑相似性，因此本文方法排序效果更差。相较于对比方法，本文方法在所有项目上的APFD 平均值更高，分别提高了12.59%、5.98%、3.01%和2.95%。

3.4.2 APFDc值结果

从表2 中可以看出，在大部分项目中，本文方法得到的APFDc 值更高。与随机方法相比，本文方法得到的APFDc 值在各个项目中都提升明显，在commons-lang 项目中的提升率最高，达到27.29%。在derby 项目中，本文方法相较于文献［10］方法表现得差一些，通过分析发现：该项目的测试用例集中存在执行时间较长（约为98 s），但在历史执行结果中多次发现缺陷的测试用例；这两个性质在多目标排序阶段互相制约，导致本文方法在该项目上的效果比文献［10］方法的差。相较于文献［9］、文献［10］和文献［11］的方法，本文方法的APFDc 值在joda-time、commons-lang 和derby 项目上的最高提升率分别为14.28%、11.51%和12.76%。相较于对比方法，本文方法在所有项目上的APFDc 平均值更高，分别提高了17.17%、5.04%、5.08%和8.21%。综合上述情况，验证了本文方法的有效性。

4 结语

针对如何提升回归测试效益问题，提出了一种综合利用历史数据和执行中信息的测试用例排序方法。首先利用测试用例文本信息和历史执行信息，对测试用例进行聚类和关联规则挖掘；然后利用多目标优化算法对测试用例排序和调整；最后在执行过程中，根据测试用例的执行信息对序列进行进一步优化。通过与其他4 个方法对比可知，本文方法的APFD 和APFDc 值具有一定的提升。

另一方面，本文所提方法还存在一些不足，未来可深入进行研究，在多目标排序阶段，合理增加优化子目标，如在实际的工业项目中，还会考虑需求覆盖等目标，以进一步研究加入这些目标后的排序效果；本文实验所用数据集的历史记录不够庞大，对关联规则的挖掘具有一定的影响，未来可考虑在具有庞大历史执行记录的实际工业项目中验证本文的方法。