多准则优化的规模约束型测试用例选择

吴先平

（复旦大学附属上海市第五人民医院 上海200000）

多准则优化的规模约束型测试用例选择

吴先平

（复旦大学附属上海市第五人民医院 上海200000）

软件修改之后可以重新测试之前的所有用例来发现错误，但是这种方法耗费巨大，为了减少测试用例数量，优化测试工作，本文提出了一种全新的用例选择方法，即从现有的测试用例集中挑选一定数量的用例并进行重新排序。该方法塑造了一个线性规划问题，采用两个代码覆盖准则并放宽约束来发现接近最优方案的用例，然后对这些用例使用投票机制获得最优用例集，最后采用最大化最小覆盖的贪心算法进行迭代排序。实验表明在大部分案例中，新方法的性能相比现有方法有显著的改进，而且一致性更好。

软件回归测试；测试用例选择；线性规划

软件系统会不断更新来满足用户新的使用需求，每次更新都需要软件回归测试来发现错误。研究表明提高测试效率最好的途径是减少测试集用例[1-6]，主要有两种方法：回归测试选择（RTS）和回归测试排序（RTP）。RTS和RTP技术的相关研究有两个公有的结论：第一，技术的相对性能随不同的程序而变化[1-2]，因此需要寻求一致性更好的方法。第二，某些实例的方案和假设的最优方案之间存在着差距[3-4]，表明现有的准则和算法不充分，而使用多准则方法有助于缓解这个问题[5]。

回归测试技术成本效用模型的一个重要因素是时间约束，传统RTP或者RTS的解决方案在时间约束下可能不是最优方案。事先获得一个时间约束来选出一个测试子集并排序非常有必要，即从原有的测试集中选出给定数量的测试子集，在所有这种规模的子集中其记分函数是最优的。

1 软件回归测试相关工作

1.1 回归测试用例选择研究

目前的回归测试选择技术分为3种：最小化、安全化和基于覆盖的选择。最小化技术选择最小测试用例集来满足被修改代码部分的最小覆盖准则。如1977年Fischer使用zeroone整数规划找到测试用例的最小子集来覆盖软件系统的每一个元素[8]。最小化技术有效的减少了测试集规模，但是可能漏掉某些可以发现错误的用例[9]。为了尽量消除这种失误，Rothermel，Harrold提出了安全RTS技术[10]，使测试集的规模边际递减，同时保证了较高的精确性[2-11]。基于覆盖的RTS技术选择满足覆盖率要求的测试用例[12-14]，例如数据流覆盖技术[12]选择所有因为代码修改导致数据交互的用例。这类技术的成本通常处于最小化和安全化技术之间，但是都不能直接控制测试用例的数量。

各种RTS技术的优劣可以用成本效益分析模型来评估。研究表明[1-16]，没有任何一种技术能在各种情况下始终有最好的成本效益，根据产品的特性和测试流程的差异需选用不同的测试技术。因此迫使研究人员研究多准则方法来解决这个问题。

Yoo，Harman提出了帕累托最优化的多准则选择方法[5]。通过遗传算法来找到帕累托最优方案点解决两种选择问题：基于最小执行时间和最大代码覆盖的二维问题以及基于最小执行时间、最大代码覆盖和历史错误覆盖的三维问题。测试人员需要根据实际情况从这些最优方案点中选择最终方案，但是在已知时间有限的情况下，帕累托方法并没有太多优势。

1.2 回归测试用例排序研究

研究者提出了多种排序技术并进行了实验研究，其中大部分使用贪心算法来优化错误相关的准则如代码覆盖，对测试用例进行重新排序。为了提高代码覆盖技术的性能，研究人员引入了其他参数如变化，错误索引[3]及相关片区或者增加反馈机制，研究表明各技术性能存在显著差异，且在不同的程序中也不一致。

传统贪心算法简化了RTP问题的搜索，但是不能确保最优解决方案。Li等研究了基于搜索的非贪心算法，不评估对错误检测率的影响而关注最大化覆盖率，提出了3种技术（2优贪心算法，遗传算法，爬山法）并和两个传统的基于覆盖的技术（贪心和附加贪心算法）进行了对比，但是结果表明贪心算法是非常有效的。

2 新方法提出

2.1 问题描述

已知：一个程序Pv，它的测试用例集合T={T1，…，Tn}；Pv+1表示新版本程序，由M个元素构成，A={a1，…，aM}。定义数字L≤N，函数Fv+1是从一个测试用例集合得到一个正的分级数量，问题：

寻找S⊆T，使其满足|S|=L，且∀S′⊆L，|S′|=L⇒FV+1（S′）≤Fv+1（S）。

定义ZM={1，…，M}表示从1到M的整数集合，ZM={1，…，N}表示从1到N的整数集合。我们使用索引来简化软件元素和测试用例。（例如：m∈ZM指第m个软件元素，并且n∈ZN指第m个测试用例）同时，在将集合作为参数时，我们使用元素的索引来替代集合。

为了解决SRTS问题，我们提出了多准则非贪心优化方法。以下从优化准则和优化算法两个方面进行描述。

2.2 优化准则

通常我们定义记分函数F为检测到的错误数目，由于错误数目是未知的，因此还需要建立其他的得分函数，并与错误数目具有某种统计关系。给定一个测试集S⊂ZN，定义测试集S对程序单元集合A测试能力为一个正的标量，记为D（S），并假定：

1）D（S）能相对精确地表示测试集S对程序集合A的错误检测能力；

2）D（S）的值可以得到，并且与之联系的搜索问题可以用数学表达式表述.

我们将它称为D函数，一个典型的D函数就是S中测试用例的代码覆盖率。令dm（S）表示测试集S对程序单元集合A中第m个单元的错误测试能力。假设

其中，δm（sn）表示第n个测试用例sn∈S对第m个程序单元αm∈A的错误测试能力。如前所述，在本文中定义δm（sn）为sn∈S对αm∈A的代码覆盖率，那么测试集（S）对每个程序单元（m）的代码覆盖率是每个测试用例（n）对此程序单元的代码覆盖率（δm（sn））的总和。我们定义两个D函数：

wm是一系列权重，强调各个程序单元在软件测试中的重要性。例如本文中使用的程序单元检测出错误的可能性、或者该程序单元在软件功能中的作用。

Dmin函数（式3）最大化所有程序单元上的最小代码覆盖率，与贪婪算法中反馈机理作用类似，使代码覆盖率在系统程序单元中的分布更均匀，从而提高了测试集的错误检测能力。最大化最小覆盖率易生成多种优化结果，为进一步缩小解决方案的范围，我们增加了第二个函数Dsum，并且与第一个D函数弱相关，这样可以实现优化问题的0-1IP编程设计，通过运用权重wm可以为各个程序单元设置优先级。

假设只关注于选取L个测试用例最大化Dsum，其中wm取1。结果为Dsum（{1，3，5，7}）=721+716+596+540=2573（L=4）；Dsum（{1，3，5，7}）=2573+187=2760（L=5）；Dsum（{1，3，4，5，6，7}）= 2760+160=2920（L=6）。

可以看到L的增加仅带来D值少量的变化。而L=4时，相应的d1（{1，3，5，7}）=15+2+5+30=52，d2（{1，3，5，7}）=101，以及d3（{1，3，5，7}）=2420。此时Dmin（{1，3，5，7}）=min（52，101，2420）=52。如果将用例4取代5，得到Dsum（{1，3，5，7}）=2164和Dmin（{1，3，5，7}）=129。此时Dmin从52变到129（将近两倍），代价是Dsum从2420减为2164。Dmin增长两倍意味着可以保证每单个程序单元至少有相对于以前两倍的代码覆盖率。略微下降表明某些程序单元被覆盖少了，但那些单元却可被其他测试用例覆盖。例如，用例5覆盖单元3最多，同时单元3也被用例1，3，7覆盖。所以用例5发现的错误也极可能被其他用例发现。

上述案例表明采用单一D函数，相当一大部分的测试用例增加仅能对D值增长产生微弱的贡献。采用多个D函数在数学上有两大好处：第一，有时候很多优化方案会得到相同D值，另一个选择准则有助于决定最终方案。第二，优化单一D函数可能出现上限，此时另一个D函数可有助于超越D值上限。为了同时优化两个D函数，我们需要相应的优化算法来支持。

2.3 优化算法

优化多准则的算法至少具有以下性质：

2）可用于搜索一个给定规模D约束的优化问题；

3）能同时处理两个目标函数。

传统贪婪算法已经用于解决RTP问题。优点是规模可变，满足第一个性质，但是贪婪算法对规模约束不敏感，因此不能用于优化特定规模的问题。此外，贪婪算法不具有回溯选择的功能，所以一个差的选择可能进入最终的方案。因此文中提出了一个多准则非贪婪选择算法，在两个特定的目标函数要求下，选择规模约束的测试用例集，然后提出了一个贪婪算法对规模测试用例进行排序。

3 实验设计

3.1 非独立变量及参数设置

在问题1中，非独立变量是错误检出率（FDR），即测试集检出错误的百分比。在问题2中，我们关注被发现的错误数和错误检出率，相应的由FDR和平均错误检出率（APFD）来体现[3]。

对于权重wm，令无修改的类权重为0，比平均修改水平高的类为1，而低于平均修改水平的类为0.5。

多次实验表明，λ1的步长应足够小以充分覆盖问题空间，l值的范围对LP问题的求解非常重要，范围过窄则可能求解点远离Pareto前沿，范围过宽又会导致运行时间急剧增加。我们定义λ1以步长0.01在区域内变化λ2=1-λ1，。搜索算法在l∈[10，100]范围内运行。另外对程序单元进行了3个层次的划分以便取得最好的结果。

3.2 用于对比的其他技术

3.2.1 基于覆盖的排序技术

RTP算法作为SRTS问题的一个解决方案，基于覆盖利用简单的准则和算法，成本效益明显。我们采用了两个基于覆盖的技术用于方法层面的比较，即全覆盖（MTC）和额外覆盖（MAC）[4，18]。

3.2.2 基于贝叶斯（BN）网络的技术

采用多准则的基于贝叶斯网络的方法（BN-based）是较复杂RTP技术。文中比较了两个基于贝叶斯网络的技术：BN和BNA。BNA是采用了反馈机理的BN。

3.2.3 时间可知排序技术

已知时间的排序技术可以简化为STRT问题。如Walcott等的时间明确方法（WTA），该方法基于遗传算法，使用单一覆盖准则并考虑覆盖率之间的重叠。我们对WTA技术稍作修改以采用本文中的覆盖数据，输入参数基于黑箱层面，遵循其建议设置参数为：30个体，50代，70%的交叉和10%的变异，并定义第一个用例的执行时间为一个单位。时间已知问题规定了用例数的上界而不是一个确切的数值，在对比实验中的用例数总是低于期望值l-2，因此我们运行l+2数值来解决上述问题。

4 实验配置

文中实验运行SIR的5个开放Java源码：Ant，Nanoxml（Nano），Galileo，Xml-security（Xml），和Jmeter，这些代码已广泛地应用于回归测试的经验研究。

Andrews以及Do和Rothermel对Java程序测试集排序问题的变异错误进行了研究，我们采用相同的变异错误集，并使用SIR中可用的追踪代码（由Sofa工具生成）作为块级别的覆盖数据；每个类中被覆盖的块百分比作为类级别的覆盖数据。

方法级别的覆盖数据沿用Do等的做法[4]，即每个方法所产生的至少一个修改块，被标记为被覆盖，否则被标记为不被覆盖，该数据通过字节代码分析工具Sandmark来获得。

我们对每一个程序版本建立了规模随机（至少15）的100个变异群，并基于全局变异矩阵为每一个变异群建立个体错误矩阵。运行每一个错误矩阵100次来检测每一个涉及的技术。

5 实验结果

5.1 规模约束选择

针对问题1我们对比了IP方法及其他方法的错误检测率。在Ant程序中所有技术的结果相近。在Nano程序中，WTA技术在L=50及25的时间约束下表现最好。Galileo程序中，IP技术在两种规模约束下都明显好于其他技术。Jmeter程序中，IP在L=25时稍稍好于其他技术。在Xml程序中，IP和WTA技术比其他技术要好。总体来说，IP技术在大多数程序中的表现最好。

5.2 用例选择及排序

该问题主要探究RTS结合RTP技术是否比单独的RTP技术更好。图1至图5表明了不同测试用例中各技术对错误的探测率，我们共研究了5种技术（IP+Gmin，Gmin，BNA，MAC及WTA）并观察到了2个现象，一是IP+Gmin技术的曲线在一半的案例中都是处于Gmin曲线之上，对于其他案例的结果很接近。因此我们可以说IP+Gmin的技术比单独的Gmin技术要好。

图1 Ant程序各技术错误检测率

更有趣的发现是除了Nano程序，其他程序中当时，IP（25）+Gmin比IP（50）+Gmin的方法明显要优，而在Nano程序中，这两种方法一样。这种规律同样适用于WTA方法。这个结果表明，IP技术及WTA技术成功的将测试用例的规模缩小在要求的范围之内。WTA选择及排序同时进行，而IP+ Gmin技术先选择再排序。

图2 Nano程序各技术错误检测率

图3 Galileo程序各技术错误检测率

图4 Jmeter程序各技术错误检测率

图5 Xml程序各技术错误检测率

5.3 实验局限性

实验中的非独立变量是简单源于直觉的，另外本文专注于解决LP问题的一致性方法，执行时间不是我们主要讨论的问题，因此仅以IP技术为例对执行时间进行了粗略的考量。实验中的技术基于不同平台，由不同水平的专家所开发，将来的研究可在相同的平台和专家水平上进行运行时间的比较。

6 结束语

为了优化软件回归测试的测试集，提高测试的有效性，文中构建了一个线性规划（IP）问题，采用最大-最小准则和覆盖数准则，针对IP问题提出了一种近似和次优的数学解决方案，然后提出了一个投票机制，来选出最终的解决方案，最后提出了一个贪心算法来对选出的测试用例子集进行排序。

通过采用SIR程序库中的5个JAVA程序对以上3种技术进行了实验评价并和现有技术进行了比较。实验表明，文中提出的方法在所研究的40%的案例中的性能最高，在另外40%的案例中表现较好，而在剩下的20%的案例中表现一般。更重要的是文中提出的方法比现有其他方法表现了更好的一致性。

基于文中提出的方法将来可以采用其他多准则对规模约束问题进行更深入的研究，而且多准则方法可以用于其他算法：如贪心算法可以始于单个算法，遇到限制的情况下再引入更多的算法，或者选择新用例的时候在不同准则中进行切换。当我们理解了不同技术性能差异的原因之后，研究人员可以针对某个特定的环境创造自己的算法来选择最适合的准则。

除此之外，我们还可以在更广泛的规模约束水平以及其他控制技术，其他的程序或者考虑到了早期的错误检测率及未完成的测试等综合情况中进行更深入的研究。我们研究了IP+Gmin的技术，还可以进一步研究IP+其他RTP技术的组合性能。我们没有考虑到单个测试用例运行的执行时间，也没有考虑到执行提出的方法的时间需求，将来可以就这些未考虑的因素进行更广泛的研究。

[1]H.Do and G.Rothermel.An Empirical Study of Regression Testing Techniques Incorporating Context and Lifetime Factors and Improved Cost-Benefit Models[C]//Proc.Int’l Symp. Foundations of Software Eng.，2006：141-151.

[2]T.L.Graves，M.J.Harrold，J.-M.Kim，et al.An Empirical Study of Regression Test Selection Techniques[C]//ACM Trans.Software Eng.and Methodology，2001，10（2）：184-208.

[3]S.Elbaum，A.G.Malishevsky，G.Rothermel.Test Case Prioritization:A Family of Empirical Studies[C]//IEEE Trans. Software Eng.，2002，28（2）：159-182.

[4]H.Do，G.Rothermel，A.Kinneer.Prioritizing JUnit Test Cases:An Empirical Assessment and Cost-Benefits Analysis [C]//Empirical Software Eng.:An Int’l J.，2006，11（1）：33-70.

[5]S.Yoo，M.Harman.Pareto Efficient Multi-Objective Test Case Selection[C]//Proc.Int’l Symp.Software Testing and Analysis，2007：140-150.

[6]H.Do，S.Mirarab，L.Tahvildari，et al.An Empirical Study of the Effect of Time Constraints on the Cost-Benefits of Regression Testing[C]//Proc.ACM SIGSOFT Int’l Symp.Foundations of Software Eng.，2008：71-82.

[7]H.Do，S.Elbaum，G.Rothermel.Supporting Controlled Ex-perimentation with Testing Techniques:An Infrastructure and Its Potential Impact[C]//Empirical Software Eng.:An Int’l J.，2005，10（4）：405-435.

[8]K.Fischer.A Test Case Selection Method for the Validation of Software Maintenance Modifications[C]//Proc.Int’l Computer Software and Applications Conf.，1977：421-426.

[9]T.L.Graves，M.J.Harrold，J.-M.Kim，et al.An Empirical Study of Regression Test Selection Techniques[C]//ACM Trans.Software Eng.and Methodology，2001，10（2）：184-208.

[10]G.Rothermel，M.J.Harrold.A Safe，Efficient Regression Test Selection Technique[C]//ACM Trans.Software Eng.and Methodology，1997，6（2）：173-210.

[11]G.Rothermel，M.J.Harrold.Analyzing Regression Test Selection Techniques[C]//IEEE Trans.Software Eng.，1996，22（8）：529-551.

[12]M.Harrold，M.Soffa.An Incremental Approach to Unit Testing during Maintenance[C]//Proc.Int’l Conf.Software Maintenance，1988：362-367.

[13]L.White，H.Leung.A Firewall Concept for Both Control-Flow and Data-Flow in Regression Integration Testing[C]// Proc.Int’l Conf.Software Maintenance，1992：262-271.

[14]D.Binkley.Semantics Guided Regression Test Cost Reduction[C]//IEEE Trans.Software Eng.，1997，23（8）：498-516.

[15]H.Leung，L.White.A Cost Model to Compare Regression Test Strategies[C]//Proc.Int’l Conf.Software Maintenance，1991：201-208.

[16]A.G.Malishevsky，G.Rothermel，S.Elbaum.Modeling the Cost-Benefits Tradeoffs for Regression Testing Techniques[C] //Proc.Int’l Conf.Software Maintenance，2002：204-213.

Multiple criteria optimization for scale constrained test case selection

WU Xian-ping
（The Fifth People’s Hospital of Shanghai Fudan University，Shanghai 200000，China）

One traditional approach to detect errors of software after modification is to rerun all the previous test cases，which is too costly.To optimize test and reduce test cost，we proposed a new approach which is to select a predefined quantity of test cases from existed cases and re-order them.This approach forms an IP problem，uses two coverage-based criteria and constraint relaxation to find cases close to best solution，then a voting mechanism is used to select the subset cases and then are prioritized with Maximize minimum coverage based Greedy algorithm in regression.The proposed approach was evaluated against other existing ones with experiment and the result showed that the new approach performed better in most cases with higher consistency.

software regression test；pareto optimality；test case selection；linear programming

TN99

A

1674－6236（2016）24-0049-04

2016-03-03 稿件编号：201603027

吴先平（1979—），女，湖北恩施人，硕士。研究方向：信息管理。