使用程序切片来提高集群测试选择的效率和有效性

摘要

集群测试选择是在回归测试中选择现有测试套件子集的一种成功的新方法。本文介绍了程序切片，以提高集群测试选择技术的效率和有效性。在修改后的代码上计算静态切片。程序切片对每个测试用例的执行配置文件进行过滤，以突出显示受修改影响的软件部分，称为切片过滤。切片过滤可减少用于集群分析的数据维度，从而可显著节省集群测试选择的成本。实验结果表明，切片过滤技术可以显著降低集群测试选择的成本，并且可以适度地提高集群测试选择的有效性。因此，通过过滤集群测试选择具有更大的潜在可伸缩性来处理大型软件。

介绍

回归测试是软件开发生命周期的重要阶段。但由于回归测试的成本很高，因此，通过选择要运行的现有测试套件的子集，采用测试选择技术来降低重新测试修改后的程序的成本。

近年来，在回归测试选择中引入了集群分析，称为集群测试选择（CTS）。集群分析是将一组元素分配为若干子集（称为集群），同一集群中的这些元素在某种意义上相似。在回归测试中，将集群分析用于执行配置文件。 CTS 背后的基本思想是将具有类似行为的测试用例分组到同一集群中。预计可以将故障揭示测试用例分组到同一集群中。最后，使用某种采样策略来选择原始测试套件的子集。

现有的大部分关于 CTS 的努力使用简单的执行配置文件，函数调用配置文件来进行集群分析。在某些情况下，函数调用配置文件可能难以捕获测试用例的详细行为。另一方面，大型软件可能包含数万甚至数百万条语句。如果使用详细的执行配置文件（例如语句覆盖率配置文件），则可能会导致无法对高维数据进行集群分析。

在本文中，我们将完成并扩展切片过滤技术。针对 CTS，提出了一种依赖域的降维技术。引入了一种常见的程序分析技术，即程序切片，以删除与修改无关的软件部分，称为切片过滤。它可以减小执行配置文件（例如语句）的尺寸，以进行有效的集群分析，为 CTS 处理大型软件提供了更多潜在的可扩展性。另一方面，程序切片可以删除与修改无关的代码，从而 CTS 可以突出显示受修改影响的软件部分。

背景

在本文的其余部分中，我们使用以下表示法：P表示程序的原始版本，P’表示的修改版本，T = {t1,t2,…,tn}表示P的原始测试套件，T’表示关于P’的T的子集。P(t)和P’ (t)分别表示带有测试用例t的P和P’的测试结果。为了指导测试选择，我们将收集一些实体覆盖率信息。令E={e1,e2,…,em}，其中ei 表示第i个实体，例如语句，块等。在执行所有测试用例之后，将构建覆盖矩阵C = T × E。n × m矩阵是一个 0-1 矩阵，如果测试用例ti执行了实体ej，则ci,j = 1, 否则ci,j = 0。Ci表示C中的第i行并且Ci被称为 ti 的特征。

定义 1（回归测试选择） 给定程序P及其修改后的版本P’，问题在于选择原始测试套件T的子集T’。期望T’可以检测到P’中的修改所引入的故障。

如果测试用例在程序中能检测到故障，则表明该测试用例能揭示错误。当且仅当测试用例执行修改后的代码或执行先前已删除的代码时，才可以进行修改。在回归测试选择中有一个假设：对于每个测试用例t∈T，P(t)是正确的。因此，当且仅当 P(t)≠P’ (t)时，t才是能揭示故障的测试用例。我们使用TF 表示T中所有能揭示故障的测试用例的集合，使用TM 表示T中所有经过修改的测试用例的集合，不难发现TF ? TM ? T。

如果测试选择技术可以选择所有揭示故障的测试用例，那么它就可以称为“安全”，即可以选择子集T’ ? TF_。显然，_TM 是安全的，因为TF ? TM_。Rothermel 等人提出了一种安全的选择技术构造了程序P及其修改版本P’的控制流程图，并使用这些图从T中选择TM 。在某些情况下，_TM 比TF 大得多。TM中有许多冗余测试用例，在一定时间范围内运行TM 中的所有测试用例仍然不可行。

方法

回归测试选择的一个主要挑战是如何选择近似于TF 的T’。CTS 是成功的技术之一。虽然由于集群分析的不确定性和抽样策略的随机性，CTS 是不安全的，这种不安全性意味着我们的方法可能会错过TF 中的一些揭示错误的测试案例。但是，在资源有限的测试场景中，运行通过安全回归测试选择技术所选择的所有测试案例是不切实际的。另一方面，所有故障揭示测试用例的适当子集足以在许多情况下检测和调试错误。在本文中，我们采用 CTS 框架，并通过程序切片对特征进行过滤，以提高 CTS 的效率和有效性。

1. 框架

CTS 可以通过某些特定的行为功能将相似的测试用例分组到同一集群中。然后，将从每个集群中抽取一些测试用例，以形成回归测试套件T’。如图 1，CTS 包含以下步骤：

(1)运行T：T中的所有测试用例都在程序P上执行测试用例的执行配置文件将被收集以用于后续步骤。在此步骤中，可以为每个测试用例生成许多类型的配置文件，例如函数调用配置文件，语句/块覆盖率配置文件等。

(2)过滤：执行配置文件包含一组在运行期间执行的实体（语句或块等）。对于大型软件，特征维度|Ci |（即 m）可能很大，因此在实践中无法处理。因此，每个特征Ci将被过滤到一个小的子集，以提高下一步的集群分析性能。在本文中，我们使用程序切片来过滤每个测试用例的特征。

(3)集群分析：集群分析的输入是在步骤 2 中过滤后的特征。集群之前应计算每对特征间的距离。选择一种集群算法，将T中的测试用例分组为一些集群。群集技术将具有类似执行配置文件的测试用例放在同一集群中。

(4)采样：本文使用一种有效的自适应采样策略。首先，它从每个集群中随机选择一些测试用例。然后，执行这些测试用例以验证它们是否通过。如果一个测试用例失败，则同一集群中的所有其他测试用例将被选择为T’。

图 1 集群测试选择的一个框架

2. 切片过滤

对于 T 中的每个测试用例ti，都有一个对应的特征Ci，其中Ci = {ci1,ci2,…,cim }。Ci为 1 或 0 来表示是否由ti执行。集群分析的效率和有效性在很大程度上取决于特征的大小和质量。我们使用语句覆盖率配置文件和块覆盖率配置文件来构造测试用例的特征，即Ci中的实体cij表示一条语句或一个块。但是，在大型软件中，删除一些无用的实体可以提高 CTS 的效率和有效性。

程序切片将删除对感兴趣的方面没有影响的程序部分来简化程序的技术之一。在本文中，我们使用静态切片来过滤测试用例的特征。对于语句s和一组变量{v}，程序P的切片S相对于切片标准仅包?s,{v}?含P在s处捕获{v}的计算所需的语句。在本文中，我们构造了两种切片形式：后向切片和前向切片。向后切片包含程序的语句，这些语句可能会对切片标准产生影响。前向切片包含受切片标准影响的程序语句。为了确定修改的影响，我们使用后向切片和前向切片的并集作为最终切片S，S是所有语句的一个子集。

我们考虑了 3 种不同的P’的变更：定义变更，使用变更和控制变更。定义变更是赋值语句左侧的更改；使用变更是指赋值语句右侧的更改。给定P中的si语句：x = z在P’中更改为y = z，使用以下 3 个切片的并集：在?si,{x}?处的前向切片；?si,{y}?处的前向切片；?si,{z}?处的后向切片。以使用变更为例，如果一条语句 si ,从P中的 x = y 更改为P’中的x = z ，则?si,{x}?处的前向切片，?si,{z}?处的后向切片的并集将会被使用；控制变更定义如下：更改会影响原始控制流，即为控制更改。控制更改需要特殊处理。我们分 3 个步骤来计算控制更改的切片：（1）我们计算了变更语句的后向切片。（2）我们计算所有与已更改语句先关的控制依赖，并计算相应的前向切片。（3)如果步骤 2 中未包含修改后的语句，则添加该语句。

表 1 切片过滤示例

我们构建了一个简单的程序来演示使用程序切片进行切片过滤的必要性，如表 1 所示。假设语句s5 “while(a≥0)” 更改为”while(a>0)”。具有切片标准?s5,{a}?的程序切片S是语句集S={s1,s2,s3,s5,s6,s7,s8}。给定三个测试用例：t1=(1,6), t2=(2,0), t3=(7,6), 表 1 中显示了测试用例的执行配置文件（此处为语句覆盖配置文件）。 t1 和t3 相似，因为它们在执行配置文件中共享许多语句。 t2 与t1 和t3 都不相同，因为它的执行路径与t1 和t3 都完全不同。因此，在集群分析中，t1 和 t3 比 t2 和 t3 更相似。但是，如果我们关注的是程序切片，而不是程序中的所有语句，那么结果会大不相同。我们计算S和每个特征Ci的交集，如表中的“· ”所示。通过过滤，t2 和t3 的特征实际上是相同的，并且t2 和t3 之间的差异也被放大了，因为那些与 s5 无关的语句被过滤掉了。由于S是程序中有关修改的语句的子集，因此可以减小特征的尺寸并且仍然保留受影响的部分。

程序片S可以看作是修改的影响的代表。因此，使用S来过滤测试用例的执行配置文件，可以使功能变得更紧凑，并且与修改有关。为了滤除关于修改的不受影响的语句，我们使用特征Ci和切片S的交集，用 Ci’ 表示。静态切片和执行配置文件的这种交集可以视为轻量级动态切片。动态切片比静态切片更精确。但动态切片的计算通常比静态切片更复杂且耗时。执行配置文件（例如涵盖的语句）是在回归测试期间收集的。借助低成本的静态切片，可以轻松计算受修改影响的软件部分。

实现

在本节中，我们将描述 CTS 过滤技术的详细实现，包括执行配置文件收集，过滤，集群分析和采样，而且将说明实验中一些关键参数的设置。

1. 执行文件集合

我们分别基于语句覆盖率和块覆盖率来实施我们的方法。原始测试套件T在程序P上执行。使用 GNU 调用覆盖分析器来收集覆盖信息。该覆盖信息将被分别存储为一个覆盖范围矩阵M。通过 CTS 技术在原始矩阵或生成的矩阵上进行过滤。在下一节中，我们将使用矩阵的大小来评估各种 CTS 技术的效率。我们还存储了从语句到块的映射信息，以供进一步分析。为简单起见，我们主要讨论基于语句覆盖率的实现。基于块覆盖的实现是相似的。

2. 筛选

覆盖矩阵的质量在 CTS 技术的有效性中起着关键作用。为了获得足够的过滤效果，我们分三个步骤实施了整个过滤过程：过滤的预处理，切片过滤和过滤的后处理。

2.1 过滤预处理

如第二节所述，TF ? TM，即没有修改遍历的测试用例一定不能成为暴露故障的用例。因此，可以安全地删除这些测试用例。这就是所谓的安全回归测试选择。安全选择的过程是这样的：

(1) 构造了原始程序和修改后程序的控制流程图。

(2) 以深度优先的顺序同步遍历两个图，以标识修改后的节点，这意味着相应的边具有风险。

(3) 选择穿越风险边缘的测试用例。

使用这种安全选择技术，尽管其中包含所有显示错误的测试用例，但大多数情况下仍有许多的冗余测试用例。在我们的实验中，我们使用了工具 DejaVu 选择遍历修改的测试用例作为过滤的预处理。在这一步中，我们通过安全选择从M中获得了一个新矩阵M1。也就是说，我们仅将遍历修改的测试用例及其功能保留在M中。

2.2 切片过滤

在此步骤中，我们使用程序切片执行两种类型的过滤：列过滤和行过滤。给定P’中的修改语句，我们为每个语句?si,{x}?设置了相应的切片标准。分别计算前向切片和后向切片。然后，前向切片和后向切片的并集形成程序切片S。矩阵M1被S逐列过滤。然后在矩阵S中获得新矩阵M2，该矩阵是通过使用S进行列过滤从M1 获得的。对M2进行进一步的行过滤。程序片段S和特征Ci 之间的公共部分在某种意义上表示ti 的故障检测能力。我们设置了一个阈值，称为过滤率FR ，以确定过滤的操作。如果程序片段S和执行配置文件Ci 的交集很低，则ti 与修改的相关性很低。形式上，如果|S∩Ci |/|S|<_FR_，则将从矩阵中滤除Ci。在我们的实验中，我们根据的经验将FR设为 0.3。然后我们通过行过滤从M2 得到了一个新的矩阵M3。

2.3 过滤后处理

在此步骤中，我们进行了简单的列过滤以进一步压缩矩阵。我们观察到所有测试用例都执行了某些语句（例如表 1 中的语句s1），并且某些测试案例未执行某些语句。从某种意义上说，使用这样的语句作为特征元素无法区分测试用例之间的行为。因此，这些语句已从矩阵中滤除。最后，我们得到了一个新的 n’×m’ 矩阵M’，它是通过列过滤从M3 获得的。

3. 集群分析

在集群分析阶段，将测试用例ti 表示为特征Ci’。用欧几里得距离作为每个特征对Ci’和Cj’的距离函数，如下所示:

在我们的实验中，采用简单的 K-means 算法作为集群算法。我们采用了广泛使用的机器学习工具 Weka 进行集群分析。 K-means 算法需要初始集群号作为参数。在我们的方法中，该数是根据测试用例的数目设置的，即 M’ 中的行数 n’ 。令CN表示该初始集群数，然后 CN = n’ * p ，其中 0 < p < 1 。在我们的实验中，我们根据的经验，设置 p = 0.025。

采样

我们使用了一种流行的策略，即自适应采样策略，在我们的方法中。我们首先以预定的采样率采样了一定数量的测试用例，以下用SR表示。然后，运行具有这些选定功能的抽样测试用例，以检查它们是否在显示错误。如果找到了揭示故障的测试用例，则该选中的采样用例所在的整个集群都将被选择。这种策略有利于小型集群，并且有很高的可能性选择故障揭示测试用例。在我们的实验中，我们将设置 SR = 0.1 ，并重复执行 10 次采样任务以计算相应的平均值。

实验

我们使用来自软件架构基础结构存储库（SIR）的主要程序space，作为我们的主要项目。space包含 5902 行代码和 1533 个基本块。总共 38 个修改版本以及一个基本程序。由于没有或少数测试用例可以检测到这些故障，因此排除了 8 个版本。在我们的实验中使用了 30 个修改版本。对于每个版本，基本程序都会增加一个实际错误。总共提供了 13585 个测试用例。

CTS 技术在处理小型程序时有一定的局限性。这是因为小程序上测试用例的执行配置文件趋于相似，因此很难通过执行配置文件来区分它们。因此，在 SIR 中的西门子程序在我们的实验中未被采用，因为它们的尺寸太小。

1. 效率分析

在 CTS 的过程中，集群分析的成本是整个成本的主要部分，尤其是对于大型软件而言。在我们的 CTS 技术中使用了 K-means。K-means 的时间复杂度是适度的，基本上与n（元素数（即此处的测试用例））和m（属性数（即此处的语句或块））呈线性关系。通过过滤技术有望大大减小n和m。

1.1 措施

引入了两种简单的集群降低方法：降维和矩阵约简，以评估使用过滤技术的 CTS 的效率。降维在集群分析中得到了广泛的应用。但是对于 CTS，矩阵约简更为合适，因为 K-means 的时间复杂度在覆盖矩阵的大小上是线性的，即n × m。

降维：*m是原始实体的数量。m’* 是通过过滤得到的实体的数量。然后可以按以下方式计算降维（DR）：DR = m’ / m × 100%

较低的DR意味着可以在集群分析和 CTS 中节省更多成本。

矩阵约简：原始覆盖矩阵M的大小为n×m。通过过滤得到的覆盖矩阵M’ 的大小为 n’×m’ 。然后，矩阵约简（MR_）可以计算如下：_MR = (n’ × m’) / (n × m) × 100%

较低的MR意味着可以在集群分析以及 CTS 中节省更多成本。

1.2 结果

图 2 和图 3 分别给出了使用 CTS 中的语句覆盖的DRs和MRs。实验结果表明，该过滤技术可以大大降低DR和MR。DR和MR的平均值分别为 24.77％和 10.55％。大多数DRs从 15％到 30％。某些版本（1、21 和 25）的DRs大于 40％，但它们仍然适中。某些版本（2、3 和 4）的尺寸大大减小，并且小于 10％。实验结果表明，覆盖矩阵的大小可以大大减小。尽管两个版本（1 和 25）的MRs大于 40％，但大多数MRs小于 10％，甚至有一些版本（3、5、6、16、17、19 和 29)小于 1％。

图 4 和图 5 分别给出了使用 CTS 中的块覆盖的DRs和MRs。实验结果表明，该过滤技术也可以取得很好的效果以减少DR和MR。DR和MR的平均值分别为 39.75％和 16.56％。大多数DR小于 50％，两个DR（版本 2 和 3）小于 10％。大多数MR小于 10％，甚至有一些（版本 5、6、16 和 17）小于 1％。

图 2 至图 5 中的结果显示，对于每个版本矩阵简化MR*都小于降维DR，无论是语句覆盖还是块覆盖。DR仅受益于列过滤，而MR*受益于行过滤和列过滤。语句覆盖的结果比块覆盖的结果好。但是，我们不能说过滤技术对语句覆盖比对块覆盖更有用。语句的数量 5902 比块的数量 1533 大得多。大量实体具有减少的潜在可能。因此，我们认为过滤技术对于大型软件更有用。

2. 有效性分析

在前面的小节中，实验结果表明，过滤技术可以大大降低集群分析的成本以及 CTS 的成本。另一方面，期望也可以提高 CTS 的有效性，至少与不使用过滤技术的 CTS 相同。

2.1 度量

为了评估具有过滤功能的 CTS 技术以及其他 CTS 技术，我们构造了两种评估方法，一种用于减少测试套件，另一种用于全面评估故障检测能力。

减少测试套件：回归测试选择技术旨在减小测试套件的大小，从而可以节省执行和维护成本。如果通过某种技术选择了原始测试套件T和子集T’ ，则可以按以下方式计算测试套件缩减量：TR = |T’ | / |T|.

较小的TR意味着将大大减少测试套件。请注意，TR与上一小节中的DR和MR不同。 TR用于评估 CTS 技术的有效性。 DR和MR用于评估 CTS 技术的效率。

F值：回归测试选择的另一个主要目标是选择一个具有强大故障检测能力的子集。 TF 是所有故障揭示测试用例的集合。如果 CTS 技术选择了故障显示测试用例的子集，则用 T’F 表示。然后召回率定义为r?call = |TF’ | / |TF |，表示故障检测能力。精确率度量定义为precision = |TF’ | / |T’|, 用于限制冗余测试用例的数量。更高的召回率和精确率意味着更好的 CTS 结果。但是，召回率和精确率自然是矛盾的。改善一个通常会伤害另一个。我们使用 F 值来评估 CTS 技术的综合优势。 F 值依靠传统的信息检索方法，适用于通过考虑本文中相应的召回率和精确率来评估结果的方法：

由于召回率和精确率均在[0, 1] 范围内，F 值也在在[0, 1] 范围内。并且很容易发现 F 值随召回率和精确率的增加而增加。如前所示，召回率和精确率需要相对较大，因此我们希望 F 值较大，因为它与二者均相关，并且单调递增。因此，F 值可以很好地证明这些技术的综合优势。

2.2 结果

在本小节中，我们将比较具有过滤功能的 CTS 技术和不具有过滤功能的 CTS 技术的有效性。但是，原始的语句覆盖范围过大（13585 x 5902），无法在 24 小时内完成 30 个版本的 CTS 任务。因此，我们在实验中放弃了这种 CTS 技术的结果。我们将比较使用块，块+过滤和语句+过滤的 CTS 技术的有效性。

图 6 给出了使用块，块+过滤和语句+过滤的 CTS 技术的测试套件缩减TR的比较。实验结果表明，近一半的TRs几乎相同，而一半的过滤TR则比未过滤的TR更好（即更低）。总体而言，带过滤功能的 CTS 技术比不带适度过滤功能以减少测试套件的 CTS 技术具有更好的效果。使用语句覆盖率配置文件的 CTS 技术与使用块覆盖率配置文件的 CTS 技术取得了相似的效果。对结果的合理解释是，同一块中的语句具有相似的能力来区分测试用例的行为。

图 7 给出了使用块，块+过滤和语句+过滤的 CTS 技术的 F 值的比较。实验结果表明，大多数过滤 F 值要比不过滤 F 值要好（即更高）。某些版本的 F 值获得了更好的改进，例如版本 5、7、8、9、10、16、17 和 29。使用语句覆盖配置文件的 CTS 技术与使用块覆盖配置文件的 CTS 技术取得了相似的效果，因为同一块中的语句具有相似的能力来区分测试用例的行为。总体而言，从反映故障检测能力的 F 值来看，过滤技术可以大大提高 CTS 技术的有效性。

3. 对有效性的威胁

3.1 内部有效性

内部有效性的威胁是不受控制的因素，这些因素也对我们的结果有影响。威胁在于我们的 CTS 技术实施存在缺陷。为了减少这种威胁，我们在进行实验之前检查了所有实施代码。我们还使用了一些流行的工具，例如 gcov 和 Weka ，在我们的执行中减少了威胁。

3.2 外部有效性

外部有效性的威胁主要是我们主程序space的代表性。space已广泛用于许多现有研究中。为了减少这种威胁，我们在实验中使用了 30 种具有不同故障的版本和大量的测试用例。我们将用更多的主程序来进行系列实验，以使结果在将来具有更大的通用性。

3.3 构建有效性

在我们的实验中，建构有效性的威胁主要与评估措施有关。为了减少威胁，我们在相关研究领域中采用了普遍使用的措施。降维在集群分析以及其他机器学习领域中被广泛使用。 F 值通常用于信息检索领域。减少测试套件是软件测试中的常用术语。

结论

在本文中，我们提出了一种通过程序切片的新方法来改进 CTS 技术。程序切片技术用于过滤掉一些不相关的特征元素以及其他一些不相关的测试用例。设计并实施了对广泛使用的主程序space的实验。实验结果表明：

(1) 过滤技术可以显着降低 CTS 的降维和矩阵约简成本。

(2) 过滤技术可以适度提高 CTS 减少测试套件的效率。

(3) 过滤技术可以大大提高 CTS 故障检测能力的有效性。

基于以上观察，具有过滤功能的 CTS 技术具有潜在的可扩展性，可以处理大型软件。我们将进行更全面的实证研究，以比较将来与其他测试选择技术的效率和有效性。

致谢

本文由南京大学软件学院 2021 级硕士于亚东翻译转述。

本文所述的工作得到了国家自然科学基金（90818027，60803007，61003024，91018005），中国国家重大基础研究发展计划（973 计划：2009CB320703），中央大学基础研究基金的支持。

来源：慕测科技