多目标测试用例优先级排序研究进展*

杨 芳, 丁晓明

(西南大学 计算机与信息科学学院，重庆 400715)

多目标测试用例优先级排序研究进展*

杨 芳, 丁晓明**

(西南大学 计算机与信息科学学院，重庆 400715)

单目标测试用例优先级排序具有片面性的缺点，为解决问题出现了多目标测试用例优先级排序；多目标测试用例优先级排序是根据多个优化目标给出测试用例的执行次序，从而提高软件测试效率，并降低回归测试开销；在介绍多目标测试用例优先级排序基本概念的基础上，总结了目前求解问题的主要方法，指出其存在的问题，给出了多目标测试用例优先级排序问题的未来研究方向。

回归测试；测试用例优先级排序；优化目标；加权法；帕累托最优；进展

回归测试是软件生命周期中不可或缺的过程，是一种重要的保证软件正确性的手段[1]。但随着软件的更新换代和软件规模的增大，回归测试时重新执行所有测试用例不现实，所以对测试用例进行预处理尤为重要。测试用例优先级排序(Test Case Prioritization,TCP)是一种根据给定的优化目标来寻找最优测试用例执行次序的软件回归测试技术。为了同时满足多个优化目标，出现了多目标测试用例优先级排序(Multi Objective Test Case Prioriti-zation,MOTCP)，其在解决回归测试问题上取得了良好的效果。

1 相关概念

1.1 多目标测试用例优先级排序

Elbaum和Rothermel等[2]对TCP问题的定义为：给定测试用例集T，PT为T的全排列集合，其包含T中所有可能的测试用例执行序列，排序目标函数f，其定义域为PT，值域为实数，寻找T′∈PT,使得∀T″∈PT∧T″≠T′有f(T′)≥f(T″)。

由以上描述可知，将一个特定执行次序作为函数f的输入，输出为与排序目标相关的值，则一般情况下输出值越大，排序结果越好。

根据单个优化目标对测试用例进行排序往往具有片面性。比如根据代码覆盖率进行排序，测试用例1的代码覆盖率为50%，其优先级设为1，错误检测数为0；测试用例2的代码覆盖率为5%，其优先级设为2，错误检测数为1。测试用例1的优先级更高，但测试用例2的错误检测数更多。因此，在实际的软件测试过程中，通常需要同时满足多个优化目标，给出综合权衡后的优先排序方案。Elbaum等人[3]提出了综合考虑测试耗费和错误严重度的TCP方法，引入单位覆盖消耗比率，结合错误严重度来评估测试用例的检错能力。Zhang X等人[4]综合需求重要度和需求耗费，讨论了广义需求概念下测试用例的评估和排序问题。

MOTCP是在TCP的基础上出现的一种新的排序方法，其一般性描述[5]如下。

1.2 优化目标

MOTCP主要是研究不同测试用例优化目标的组合与实际错误检测能力之间的关系。常见的优化目标有：平均决策覆盖率(Average Percentage Decision Coverage，APDC)、条件/分支覆盖准则(Modified Condition/Decision Coverage，MC/DC)、平均语句覆盖率(Average Percentage of Block Coverage，APBC)[6]、平均代码覆盖率(Average Percentage of Statement Coverage，APSC)、错误检测率(Average Percentage of Fault Detect,APFD)、有效执行时间(Effective Execution Time，EET)等。

石宇楠等[7]提出了一种新的排序准则——平均变异杀死率(Average Percentage of Mutation Kill，PAMK)，即“在较短的时间内杀死更多的变异”，从而在一定程度上提高发现错误的能力。

2 研究现状分析

MOTCP技术与传统的TCP技术相比主要区别在于两方面的改变，一是在优化目标的个数选取上采用两个及以上，二是在排序方法上采用加权法或者帕累托最优。

2.1 基于加权法的多目标测试用例优先级排序技术

加权法即在MOTCP问题上直接对多个优化目标进行权值分配后求和，根据加权求和后的权值对测试用例排序，从而转化为单目标测试用例优先级排序法。在排序算法上大多采用爬山算法、贪心算法、遗传算法、蚁群算法等启发式搜索算法[8]。

Kim等人[9]将历史上各阶段测试历史信息赋予不同的权值，然后把各权值加权求和，综合考虑测试用例的各项因素。王子元等[10-11]综合考虑测试用例的组合权重和执行开销从而对测试用例集进行排序。Srikanth等[12]在对测试用例排序时同时考虑了缺陷检测率、配置开销和环境搭建时间。牟永敏等[13]分别对函数调用路径覆盖能力和覆盖路径检错指标定义权值后，通过求和对测试用例进行排序。但这种加权法不够智能，权值分配受人的主观影响大，错误检测率不稳定。

Krishna等[14]综合测试时间、代码覆盖率来计算遗传算法中的适应度值，并对各阶段的适应度值加权求和，从而提高错误检测率。Chen等[15]将各优化目标进行权值分配后求和，把多目标优先级排序转化成二次分配问题，且用蚁群算法来实现。Singh等[16]基于改进蚁群算法对各优化目标进行权值分配呈现了一种在有限时间内取得更大错误覆盖率的方法。这种采用遗传算法或蚁群算法来搜索更优测试用例的方法有一定的智能性，但仍然是对各优化目标进行简单的权值分配后求和，且算法本身的执行效率受各个参数的影响很大，算法效率有待提高。

常龙辉等[17]提出一种基于历史信息的测试用例优先级排序方法，分别给缺陷发现率、测试用例稳定性设置权重，综合这两个因素设置优先级值，并在测试过程中动态自适应地调整测试用例优先级，实现了尽早发现软件缺陷的目的。方法里的动态调整优先级算法中range值的设定倾向于经验值，不够精确。张娜等[18]从需求的角度来研究测试用例优先级排序问题，分别对测试用例重要度、测试用例失效率和需求覆盖率这3个测试用例优先级影响因子定义权值，设计了一种基于多目标优化的测试用例优先级在线调整策略，实现了在尽早达到测试覆盖率的同时，尽早检测到更多的、严重等级较高的软件缺陷的目的。

郑锦勤等[19]先对测试用例进行选择，然后根据绝对贡献度、缺陷检测能力、缺陷影响度的加权求和值对测试用例排序，再在测试过程中动态调整优先级。这种方法在第一步测试用例选择的过程中可能会遗漏能够发现错误的测试用例。

2.2 基于帕累托最优的多目标测试用例优先级排序技术

基于帕累托最优的MOTCP是指在保证测试有效性的前提下，同时考虑多个优化目标，通过计算Pareto最优解集给出一组可供选择的最优测试用例排序方案。Yoo等[20]在测试用例选择中引入Pareto方法，选取代码覆盖率、测试用例执行成本、历史错误检测率为优化目标，用多目标优化方法来设置测试用例优先级。证实了适用于单目标优化的贪心算法对多目标优化不适用。

目前，基于帕累托最优的测试用例优先级排序研究还比较少，且已有的研究所采用的算法大多为群体智能搜索算法，如进化算法，蚁群算法。通过种群迭代得到一系列最优解集，然后权衡实际情况后从中选择一个较合理的排序。

2.2.1 进化算法

进化算法是通过模拟生物进化过程来求解问题的一类智能算法，在很多领域的实际优化问题中都得到了应用，但它的执行效率深受种群规模和测试用例集规模的影响。

Walcott等[21]采用遗传算法先选出花费资源较少的测试用例子集，然后对该测试用例子集按平均代码覆盖率进行排序，有效提高了时间限制下的测试用例集错误检测率。

程俊等[22]研究了基于NSGA-Ⅱ的多目标测试用例预优化技术，方法同时将平均代码覆盖率和有效执行时间作为优化目标，并给出了一种基于CPU+GPU异构模式的并行适应度评估策略来解决适应度评估的耗时问题。但这种策略中GPU的计算资源没有得到充分利用，其采用的是粗粒度的任务划分方案，扩展性还有待提高。边毅等[23]采用先进的GPU图形卡通用并行计算技术，提出了面向CPU+GPU异构计算下的多目标测试用例优先排序技术，在NSGA-Ⅱ中实现了测试用例集预优化，极大地提高了计算效率。

石宇楠等[7]提出了一种基于竞争模式的多目标协同进化算法。采用平均代码覆盖率和平均变异杀死率作为优化目标来进行适应度度量，提高了算法的错误检测率；利用竞争性的协同进化思想加快了算法收敛速度。但方法的交叉操作过程复杂，且需要对种群进行多次迭代，在用例池规模或被测程序代码量大的情况下效率会下降。

Yuchi H等[24]从最近一次的回归测试信息中选取测试成本、错误严重度两个优化目标，运用改进遗传算法使找到的执行序列在单位测试成本中检测到的故障严重程度最高。但方法完全没有考虑源代码，没有从源头考虑软件中可能出错的地方。

2.2.2 蚁群算法

蚁群算法是通过模拟蚂蚁觅食行为来求解问题的一种群体智能算法，在多目标优化问题中得到了广泛应用，它的执行效率也会随着种群规模和测试用例集规模的增大而下降。

顾聪慧等[25]提出一种基于蚁群优化算法的MOTCP方法，改进了多目标解集优劣的评价方法，选取的两个优化目标分别是有效执行时间、平均语句覆盖率。方法随着程序规模和蚁群规模的增大执行时间花费会急剧增加。邢行等[26]针对蚁群算法求解MOTCP问题时收敛速度慢、易陷入局部最优问题，提出一种基于上位基因段的信息素更新策略，选取有效执行时间、平均语句覆盖率为优化目标，在求解MOTCP问题上取得了显著效果。

2.2.3 粒子群算法

粒子群算法是受飞鸟集群活动的启发而提出的一种智能算法，与其他群体智能算法相比较，粒子群算法在处理多目标优化问题上很有优势。其内部信息交互机制简单，收敛速度快，需要调整的参数少，全局搜索能力强。

陈云飞等[5]提出了一种基于粒子群优化算法的MOTCP方法，设计了粒子的表示和状态更新方式，选取了两个优化目标：有效执行时间、平均语句覆盖率，实验结果证实在MOTCP问题上效果很好。但方法使用遗传算法中的交叉操作作为群间交互手段，计算量大，效率有待进一步提高。

3 多目标测试用例优先级排序评价指标

MOTCP与传统的TCP一样，其最终目的都是为了提高测试用例集的错误检测速率。为了比较不同测试用例优先级排序方法的性能，需要通过实验来对各排序方法进行评价。目前，最广泛应用的评价指标是APFD，该指标能有效评估测试用例优先级排序的平均错误检测效率。

APFD由Rothermel等率先提出。给定测试用例集T，T中有n个测试用例，设现已检测出m个缺陷，给定测试用例执行序列后，TFi表示检测到缺陷i的第一个测试用例在执行序列中的位置。APFD的计算公式[27]如下:

(1)

考虑测试用例的执行开销和缺陷危害程度，Elbaum等提出了改进的评价指标PAPFDC[3]。当各测试用例的执行开销和缺陷危害程度一样时，式(1)就是化简后的式(2)。ti表示第i个测试用例的执行开销，fi表示第i个缺陷的危害程度。PAPFDC的计算公式如下:

(2)

PAPFD和PAPFDC评价指标的取值范围都是0～100%，其值越大，则错误检测率越高，排序效果越好。它们的取值上限为100%，但实际上很难达到这个值，这些评价指标主要用于不同排序策略之间的性能比较[28]。

4 研究发展方向

为满足实际软件测试需求，如何找到更为有效的测试用例优先级排序方法，尤其是多目标测试用例优先级方法已成为当前软件测试领域中的关键问题和研究热点。到目前为止的研究表明，进一步的研究工作可从以下几个方面展开。

(1) 现有的大多数多目标测试用例优先级排序研究主要集中在加权法，但加权法不是严格意义上的MOTCP。加权法中各优化目标的权值分配不智能，受人的主观影响大；或者测试中采用的动态优先级调整算法复杂，时间复杂度高。可以就如何进行高效智能地权值分配进行改进，也可以减少算法的时间复杂度。

(2) 用帕累托最优的方法进行多目标测试用例优先级排序的研究还比较少，且大多采用进化算法、蚁群算法，采用其他智能搜索算法的还很少。可以探究其他智能搜索算法在问题上的应用效果，改进其他群体智能算法使其适用于测试用例优先级排序，更好地提高测试用例优先级排序效率。

(3) 用帕累托最优的方法进行多目标测试用例优先级排序时，大多数研究选取的优化目标是平均代码覆盖率和有效执行时间，但影响测试用例排序效率的因素远不止这2个。可以研究其他优化目标对测试用例优先级排序效率的影响。

(4) 用帕累托最优的方法进行多目标测试用例优先级排序时，大多数研究只采用了2个优化目标。探究3个及3个以上优化目标对测试用例优先级排序效率的影响具有重要意义。

(5) 建设多目标测试用例优先级排序通用平台，平台可以根据具体被测软件选择优化目标的个数及具体优化目标，自动对测试用例进行排序，并计算排序后的错误检测效率。

[1] RAMANATHAN M K,KOYUTURK M,GRAMA A,et al.PHALANX:A Graph-Theoretic Framework for Test Case Prioritization[C]∥Proceedings of the 2008 ACM Sympo-sium on Applied Computing (SAC 2005),New York:2008:667-673

[2] ROTHERMEL G,UNTCH R H,CHU C.Prioritizing Test Cases for Regression Testing[J].IEEE Transactions on Software Engineering,2001,27(10):929-948

[3] ELBAUM S,MALISHEVSKY A G,ROTHERMEL G.Incorporating Varying Test Costs and Fault Severities into Test Case Prioritization[C]∥Proceedings of the Intern-ational Conference on Software Engineering,2001:329-338

[4] ZHANG X,NIE C,XU B,et al.Test Case Prioritization Based on Varying Testing Requirement Priorities And Testcase Costs[C]∥Proceedings of the International Conference on Quality Software,2007:15-24

[5] 陈云飞,李征,赵瑞莲.基于PSO的多目标测试用例预优化[J].计算机科学,2014,41(5):72-77

CHEN Y F,LI Z,ZHAO R L.Applying PSO to Multi-Objective Test Cases Prioritization[J].Computer Science,2014,41(5):72-77

[6] 仝海燕,吕洪善,贾爽.白盒测试之基本路径测试技术探析[J].重庆工商大学学报(自然科学版),2014,31(1):65-68

TONG H Y,LU H S,JIA S.Analysis of Basic Path Testing Technique Based on White Box Test[J].Journal of Chongqing Technology and Business University (Natural Science Edition),2014,31(1):65-68

[7] 石宇楠,李征,龚沛.基于多目标协同进化的测试用例优先排序[J].计算机科学,2015,42(12):124-129

SHI Y N,LI Z,GONG P.Multi-Objective Coevolutionary Test Case Prioritization[J].Computer Science, 2015,42(12):124-129

[8] 陈阳梅,丁晓明.测试用例集约简方法综述[J].重庆工商大学学报(自然科学版),2012,29(3):70-74

CHEN Y M,DING X M.Review of Test Suite Reduction Method[J].Journal of Chongqing Technology and Business University (Natural Science Edition),2012,29(3):70-74

[9] KIM J M,PORTER A.A History-based Test Prioritization Technique for Regression Testing in Resource Constrained Environments[C]∥The International Conference Software Engineering,2002:119-129

[10] WANG Z Y,XU B W,CHEN L,et al.Cost-Effective Combinatorial Test Case Prioritization for Varying Combination Weights[C]∥Proceedings of the Int’l Conference on Software & Knowledge Engineering,2010:273-278

[11] WANG Z Y,CHEN L,XU B W,et al.Cost-Cognizant Combinatorial Test Case Prioritization[J].Int’l Journal of Software Engineering and Knowledge Engineering,2011,21(6):829-854

[12] SRIKANTH H,COHEN M B,QU X.Reducing Field Failures in System Configurable IEEE Press Software:Cost-based Prioritization[C]∥Proceedings of the Int’l Conference on Software Reliability Engineering,2009:61-70

[13] 牟永敏,李慧丽.基于函数调用路径的测试用例优先级排序[J].计算机工程,2014,40(7):242-246

MU Y M,LI H L.Test Case Prioritization Based on Function Calling Paths[J].Computer Engineering,2014,40(7):242-246

[14] KRISHNA M R,SAHAAYA A A.Regression Test Suite Prioritization Using Genetic Algorithms[J].International Journal of Hybrid Information Technology,2009,2(3):35-52

[15] CHEN G Y,ROGERS J.Arranging Software Test Cases Through an Optimization Method[C]∥Proceedings of the 2010 Conference on Technology Management for Global Economic Growth (PICMET’10),Phuket,Thailand,2010:1-5

[16] SINGH Y,KAUR A,SURI B.Test Case Prioritization Using Ant Colony Optimization[J].ACM Sigsoft Software Engineering Notes,2010,35(4):1-7

[17] 常龙辉,缪淮扣,肖蕾.基于历史信息的自适应测试用例优先级技术[J].计算机科学,2015,42(9):154-158

CHANG L H,MIAO H K,XIAO L.Self-Adaptive Test Case Prioritization Based on History Information[J].Computer Science,2015,42(9):154-158

[18] 张娜,姚澜,包晓安,等.多目标优化的测试用例优先级在线调整策略[J].软件学报,2015,26(10):2451-2464

ZHANG N,YAO L,BAO X A,et al.Multi-Objective Optimization Based on-line Adjustment Strategy of Test Case Prioritization[J].Journal of Software,2015,26(10):2451-2464

[19] 郑锦勤,牟永敏.基于函数调用路径的回归测试用例选择排序方法研究[J].计算机应用研究,2016,33(7):2063-2067

ZHENG J Q,MU Y M.Regression Test Case Selection and Prioritization based on Functions Calling Path[J].Application Research of Computers,2016,33(7):2063-2067

[20] YO S,HARMAN M.Pareto Efficient Multi-objective Test Case Selection[C]∥Proceedings of the 2007 Int’l Symp on Software Testing and Analysis,2007:140-150

[21] WALCOTT K,SOFFA M,KAPFHAMMER G,et al.Time-aware Test Suite Prioritization[C]∥Proceedings of the International Symposium on Software Testing and Analysis,2006:1-12

[22] 程俊,李征,赵瑞莲.CPU+GPU异构并行多目标测试用例预优化技术[C]∥第七届中国测试学术会议(CTC2012),2012:116-121

CHENG J,LI Z,ZHAO R L.CPU+GPU Heterogeneous Parallel Multi-Objective Test Case Prioritization[C]∥The Seventh China Test Conference (CTC2012),2012:116-121

[23] 边毅,袁方,郭俊霞,等.面向CPU+GPU异构计算的多目标测试用例优先排序[J].软件学报，2016,27(4):943-954

BIAN Y,YUAN F,GUO J X,et al.CPU+GPU Heterogeneous Computing Orientated Multi-Objective Test Case Prioritization[J].Journal of Software,2016,27(4):943-954

[24] HUANG Y C,PENG K L.A History-based Cost-Cognizant Test Case Prioritization Technique in Regression Testing[J].The Journal of Systems and Software,2012,85:626-637

[25] 顾聪慧,李征,赵瑞莲.基于ACO的测试用例预优化及参数影响分析[J].计算机科学与探索,2014,8(12):1463-1473

GU C H,LI Z,ZHAO R L.ACO Based Test Case Prioritization and Impact Analysis of Parameters[J]. Journal of Frontiers of Computer Science and Technology,2014,8(12):1463-1473

[26] 邢行,尚颖,赵瑞莲,等.面向多目标测试用例优先级排序的蚁群算法信息素更新策略[J].计算机应用,2016,36(9):2497-2502

XING X,SHANG Y,ZHAO R L,et al.Pheromone Updating Strategy of Ant Colony Algorithm for Multi-Objective Test Case Prioritization[J].Journal of Computer Application,2016,36(9):2497-2502

[27] ELBAUM S,MALISHEVSKY A G,ROTHERMEL G.Prioritizing Test Cases for Regression Testing[C]∥Proceedings of the Int’l Symp on Software Testing and Analysis,2000:102-112

[28] 陈翔,陈继红,鞠小林,等.回归测试中的测试用例优先排序技术述评[J].软件学报,2013,24(8):1695-1712

CHEN X,CHEN J H,JU X L,et al.Survey of Test Case Prioritization Techniques for Regression Testing[J].Journal of Software,2013,24(8):1695-1712

责任编辑：田 静

Research Progress in Multi-Objective Test Case Prioritization

YANG Fang, DING Xiao-ming

(School of Computer and Information Science, Southwest University,Chongqing 400715, China)

Single objective Test Case Prioritization has the one-sided disadvantage.In order to solve this problem,the multi-objective test case prioritization is proposed.The multi-objective test case prioritization is to give the execution order of test cases based on multiple optimal objectives,so as to improve the efficiency of software testing and reduce the cost of regression testing.On the basis of introducing the basic concept of multi-objective test case prioritization,the main methods to solve the problem are summarized and the existing problems are pointed out.Finally,the future research direction of multi-objective test case prioritization is given.

regression testing; test case prioritization; optimal objective; weighted method; Pareto optimal; progress

10.16055/j.issn.1672-058X.2017.0003.012

2016-11-20;

2016-12-22. * 基金项目：国家自然科学基金(61003203).

杨芳(1990-)，女，重庆人，硕士研究生，从事软件测试研究.

**通讯作者：丁晓明(1966-)，男，重庆人，副教授，博士，从事软件测试研究.E-mail:xmding@swu.edu.cn.

TP311

A

1672-058X(2017)03-0065-06