引用

C. Zhang, Z. Chen, Z. Zhao, S. Yan, J. Zhang and B. Xu, "An Improved Regression Test Selection Technique by Clustering Execution Profiles," 2010 10th International Conference on Quality Software, 2010, pp. 171-179, doi: 10.1109/QSIC.2010.16.

摘要

为了提高回归测试的效率，人们提出了许多测试选择技术，从庞大的测试集中提取小子集，以近似原始测试集对修改后的代码的故障检测能力。本文提出了一种新的回归测试选择技术，通过对修改的执行特征文件(遍历测试用例)进行聚类。聚类分析可以对具有相似特征的程序执行进行分组，从而更好地理解程序行为，以正确的方式选择测试用例，有效地减少测试集。设计并实现了一些实际程序的实验。实验结果表明，与现有的选择技术相比，我们的方法可以产生更小的测试套件，其中包含大多数故障揭示测试用例。

介绍 回归测试选择是选择原始测试集的子集，该子集对修改后的代码有足够的故障检测能力。给定一个程序的修改版本，现有的回归测试选择技术主要关注于如何选择遍历修改的测试用例，称为修改遍历测试用例，以便它们可以揭示错误。对于这些技术，使用一小部分测试集来降低回归测试的成本是可取的。然而，有一个潜在的风险，那就是忽略了那些揭示错误的测试用例。选择和运行测试用例所需的时间和这些测试用例的故障检测能力之间的权衡是回归测试选择的核心。我们提出了一种新的基于聚类执行特征文件的回归测试选择技术，在这里称为聚类选择技术。该技术基于程序的控制流信息，使用聚类分析方法处理历史测试执行特征文件，并根据聚类结果选择测试用例。

方法 我们研究了 Rothermel 和 Harrold 在[15]中提出的一种著名的安全技术。我们将其应用到一个名为 space[17]的主题项目中。它是数组定义语言的解释器，用于大型航空航天应用程序。它有一个原始版本和 38 个修改版本，带有 13585 个测试用例的测试套件。通过修改一行或多行代码，每个修改后的版本都包含一个错误。图 1、图 2 显示了 Rothermel 技术对每个修改版本的选择精度。

我们的聚类选择技术将聚类分析方法应用于安全选择技术的结果。聚类分析是统计数据分析的一种常用技术，该技术的基本原理是这样的:由于在同一个集群中的对象是相似的，如果我们以某种方式度量测试用例的执行，并使用集群分析来对它们进行集群，那么在同一个集群中的测试用例有一些类似的执行特征。如果修改后的程序中有一个错误，那么显示错误的测试用例可能是相似的，因为它们都显示了错误，有不正确的执行。聚类之后，故障揭示测试用例被组装起来，并与大多数非故障揭示测试用例隔离开来，因为它们并不相似。因此，我们可以用预定义的策略轻松地检查每个集群，并删除大量非故障暴露的测试用例。

A． 执行特征文件的收集

我们使用 DejaVu 实现测试选择技术。该工具的工作流程是:首先构造原程序和修改后程序的控制流程图。然后，以深度优先的顺序对两个图进行同步遍历，以识别修改的节点，这意味着相应的边是有风险的。最后，选择遍历风险边缘的测试用例。工具 DejaVu 选择所有修改遍历测试用例，其中包括所有故障揭示测试用例。首先我们需要收集覆盖信息形成测试历史，然后我们扩展 DejaVu，紧接着添加一个过程从测试历史中提取函数执行特征。

B． 聚类过程

对测试用例进行特征分析后，将所有测试用例转化为度量形式，并作为待聚类的对象进行处理。每个函数都用一个向量表示，比如 X: <x1, x2, …, xn> ，其中 xi 表示每个函数的执行信息，等于 1 或 0。对象的数量等于选择的测试用例的数量。为了模仿 Liu 等人提出的[11]模型，我们将这一步称为指纹识别。指纹识别完成后，需要计算测试用例之间的距离进行聚类。我们选择的距离函数是 n 维欧几里得距离，因为它是常见的，易于计算。如果两个测试用例被配置为 X: <x1, x2, …, xn>和 Y: <y1, y2, …, yn>，它们之间的距离为:

，如果 x = y, d = 0，否则为 1。对象的所有属性都是 2 值、1 或 0，因此度量实际上是二进制度量。距离是通过对这些属性应用欧几里得距离公式来计算的。

C．选择策略

选择策略首先检查每个集群。我们首先从每个聚类中随机选取一定比例的测试用例，如 2.5%、5%、10%，至少选取 1 个测试用例。然后，每个选择的测试用例通过比较执行原始和修改的程序与这个测试用例所产生的输出来评估。只要输出是不同的,这意味着相应的测试用例发现失败,我们期望也许更多的测试用例在同一集群显示错误因为它们类似于这个测试用例失败,因此,我们选择这个集群中的所有测试用例的选择结果。如果所选的测试用例中没有一个失败，我们认为这个集群中的任何其他测试用例都不太可能显示错误。因此，我们丢弃这个集群中的所有测试用例。检查完所有集群后，选择一些集群，丢弃一些集群，最终生成最终结果。

实验过程

首先，我们构建了增强的 DejaVu，并将其应用于每个主题程序的每个修改版本及其原始版本，以选择测试用例，以及获取我们将处理的它们的功能执行特征。然后用简单的 K-means 算法对执行轮廓进行聚类。该算法是在 Weka[20]的帮助下实现的。它提供了编写集群过程的 API。聚类之后，我们运行我们编写的选择过程。该过程通过随机选取一定比例的测试用例对每个簇进行检查，最后按照我们的思路丢弃一些簇。最后，收集有用数据，计算评价模型。

我们构建了 3 个模型，一个用于计算故障检测能力，一个用于计算选择精度和一个用于计算测试集约简。

1） 召回检测

2） 精度检测

3） 衰减检测

4） 联系

我们提出一个计算过程的召回期望的公式。假设聚类后有 k 个簇。对于任何聚类 i，都有 mi 个测试用例，其中有 fi 故障揭示测试用例和 ni 非故障揭示测试用例。在选择过程中，假设在每个集群中选择了 p%的测试用例进行检查。我们将 ci 定义为 mi * p%的轮，最小值为 1。那么召回期望(简称 RE)的计算方法如下:

图 3 显示了程序选择的不同 p%值对应的不同版本空间项目的召回期望。图中还给出了各版本在不同 p%上的平均期望召回值。

实验结果

图 4 用箱线图描述了聚类选择技术对空间项目各修改版本的召回结果。每个箱线图代表我们技术对每个版本的召回度量的统计数据。如图所示，几乎在所有的版本中，我们的技术可以统计地选择大部分的故障揭示测试用例，超过 80%。因此，这意味着我们的技术可以选择大多数显示故障的测试用例，以便能够很容易地发现和调试故障。图 5 显示了两种技术对每个修改版本的选择精度结果。再次给出基本方法的结果进行比较。精度检测指示了所选测试集中有用测试用例的比率。每个箱线图表示我们的技术对每个版本的选择精度的统计，相应的粗体点表示基本安全技术的选择精度。我们可以看到，我们的技术显著地提高了选择精度，这意味着它删除了很多非故障揭示的测试用例。从(5)开始，假定每个版本的测试套件比基本版本的测试套件更少。图 6 证实了这一推断，在图中使用了类似的箱线图来表示结果测试集的大小，即通过我们的技术进行的缩减度量，粗体点表示基本点的结果。通过我们的技术，测试套件大小的差异意味着测试套件更小。综上所述，对于图 4、5 和 6，聚类选择技术的好处是显而易见的。几乎对于所有的版本，大多数错误暴露的测试用例都被挑出来，并且有很大的召回值。另一方面，更高的精度表明，我们选择的测试用例组成最终的测试集比安全选择技术的结果要少得多。

图 7、图 8 和图 9 分别显示了其他程序在所有修改版本上的聚类选择技术的相关信息。然而，为了简单起见，我们只是以直方图的形式给出平均结果。平均的结果也可以解释其益处。

在图 7 中，条形图代表了我们对这些程序所用技术的召回。在图 8 中，条形图全部分为两部分，灰色部分代表基本安全技术的精度，整体代表我们技术的精度。白色部分是我们的技术在基本安全技术之上的改进。在图 9 中，相反的，条形图的灰色部分代表了我们技术的结果测试集大小，而整体代表了基本安全技术的相同信息。

结论和未来的工作

聚类选择技术可以显著减少测试集的大小，前提是能够找到大多数故障暴露的测试用例。因此，有足够的故障检测能力可以进一步降低回归测试的代价。这种技术有效地处理了测试套件减少和故障检测能力之间的权衡，在大型程序上表现得更好。我们的技术有几个有前景的方向。首先，由于实验结果是令人鼓舞的，应该计划和做更多的实验，更多的基本技术，程序和测试套件，以支持理论。此外，一些变量，如选择策略中选择的测试用例的比例，应该被讨论。这些变量的不同值将被期望和研究。第二，程序的测量，函数执行概要，可能很简单。它会影响结果。使用不同的测量方法可以得到不同的结果。例如，我们可以记录函数在相应的执行过程中被调用的次数，或者我们可以记录语句的执行概要。我们会考虑这些问题，并通过进一步的实验来验证，无论结果是否更好。最后，可以对聚类算法进行修改。我们将尝试其他算法得到更多的实证结果，并将它们进行比较，以找到最适合我们技术的算法。