聚类分析技术在软件测试中的应用

聚类分析技术在软件测试中的应用

1. 引言

回归测试的目的是保证修改过后的软件没有引入新的错误。但是随着软件的演化，回归测试用例集不断增大，为了控制成本，回归测试用例选择技术应运而生。近年来，聚类分析技术被运用到回归测试用例选择问题中。其基本思想为：根据测试用例的历史执行剖面进行聚类，将具有相似的函数覆盖、能够发现相同故障的测试用例聚为一个簇。然后通过取样策略从每一簇中选出一定比例的测试用例组成新的测试用例集。将半监督学习引入到聚类技术中，提出的判别型半监督K-means聚类方法（Discriminative Semi-supervised K-means，简称DSKM），该方法通过从回归测试的历史执行记录中挖掘出隐藏的成对约束信息，同时利用大量的无标签样本和少量的有标签样本进行学习，从而优化聚类的结果，进一步优化测试用例选择的结果。通过相应的实验发现，相对于普通的K-means算法，DSKM方法在保持较高的召回率和代码覆盖率的前提下，准确率和约简率都有明显的提高。

在软件开发的过程中，软件系统及其环境在不断地进行变化。增强功能、纠正错误、新增或者删除功能，都需要修改代码并触发软件的演化。为了确保演化后的软件能够正确运行并且新的改变没有引入新的错误，必须对软件进行回归测试^[1]。统计数据表明，回归测试开销一般占整个软件测试预算的80%以上，占整个软件维护预算的50%以上，因此有效的回归测试是非常重要的^[2]。然而，随着软件的不断演化，测试用例集不断增大，由于资源有限，几乎不可能运行所有的测试用例。为了提高回归测试的运行效率，许多策略被提出，其中最主要的一种技术是回归测试用例选择技术^[3]（Regression Test Case Selection，简称RTS）。

近年来，数据挖掘中的聚类技术被用于解决回归测试用例选择问题。其基本思想是：根据测试用例的历史执行剖面进行聚类，将具有相似的函数覆盖、能够发现相同故障的测试用例聚为一个簇。同一簇中的测试用例具有相似的行为，而不同簇中的测试用例的行为差异较大。若一个测试用例能检测某一故障，则属于同一簇的其他测试用例通常也能检测到这一故障^[1]。在回归测试时，只需从每一簇中选取一定比例的测试用例组成新的测试用例集，新测试用例集的精度和覆盖率在很大程度上依赖于聚类结果，而聚类结果依赖于聚类算法的选取。传统的K-means聚类算法是无监督的，对选取的K值和初始的簇中心都非常敏感，可能会产生局部最优的聚类结果，从而导致选择出的测试用例无法满足较高的准确率和覆盖率。为了优化聚类结果，论文提出一种判别型半监督K-means聚类方法（Discriminative Semi-supervised K-means，简称DSKM），将半监督聚类运用到回归测试用例选择中。在保证测试用例覆盖率的同时，减少测试用例，从而缩减回归测试的成本，提高回归测试的效率。

1. 国内外研究概况

针对RTS问题的研究，众多研究人员提出了很多的解决方案^[4]。Rothermel和Harrolad首次对RTS问题进行了总结并提出一种统一评估框架^{[3, 5]}，随后提出一种基于控制流图的RTS技术并开发出DejaVu工具。Beydeda和Gruhn基于Rothermel等人的研究工作，通过将黑盒测试中的数据流信息添加到类控制流图来对面向对象程序进行测试^[6]。Harrold和Sofia提出了一种适用于单元测试阶段的增量数据流分析法^[7]。Gupta等人基于数据流分析法，应用程序切片技术识别出与代码修改存在依赖关系的定义使用对（Definition-Use Pair）^{[8, 9]}，该方法在执行时间和存储空间上均具有一定优势。H. K. N. Leung 等人则在软件集成的回归测试中引入"防火墙"技术^[11]。

近年来，随着计算机软硬件性能的不断提高，有不少学者将聚类技术用于RTS问题。Dickinson 等人提出基于执行剖面聚类的测试用例选择，挖掘出测试用例之间隐藏的联系^[10]。Masri等人进行了一项实证研究，用来验证聚类过滤技术的有效性^[11]。Zhang等人在Rothermel的基础上，通过对遍历测试修改的执行剖面进行聚类，增强了安全选择技术^[1]。Shin等人提出了基于聚类的测试用例优先级技术，用来减少成对比较的数量^[12]。C. Songyu等人率先将半监督聚类运用到回归测试用例选择的问题上，利用测试用例的函数覆盖信息对测试用例进行聚类，从而减少测试用例^[13]。

使用聚类技术解决RTS问题，可以在保证测试用例的错误检测能力和覆盖率的前提下，提高测试用例的约简率^[1,14]。但目前已有的方法大部分都是非监督的，利用无标签数据进行训练和组织数据，聚类的结果依赖于目标函数的设定和参数的输入，而这些参数往往是需要人工设置的。由于软件系统的复杂性和多样性，在参数设置方面比较困难，获得的聚类效果也难以得到保证。尹学松等人提出了基于成对约束的判别型半监督聚类分析方法^[15]。这种聚类方法用于解决回归测试用例选择问题，可以优化回归测试用例选择的结果。

1. 聚类分析技术基本原理

一、组合测试模型

某待测软件系统（Softwear Under Testing,SUT）有n个参数，这些参数可以是外部输入、内部事件或者配置参数。对n个输入参数中任意t个参

数的所有取值组合进行覆盖，称为覆盖强度为t的组合测试。当t＝2时，称为两两组合测试。在最终生成的测试用例集中，所有软件系统外部参数可能取值的两两组合至少覆盖一次。假设有一个待测软件系统，该系统有4个参数，每个参数包含3个因子。如果采用穷举测试方式，需要3⁴＝81个测试用例才能覆盖所有的可能参数取值组合，而如果采用两两覆盖组合测试，只需要9个测试用例就可以实现两两覆盖，检测出大部分的软件错误。

二、基于蚁群算法的组合测试

    蚁群算法蚁群算法是根据蚁群觅食活动规律建立的一个利用群体智能进行优化搜索的算法。蚁群算法包括两个阶段：适应阶段和协作阶段。算法本身是根据一定规则随机寻找最优解。

（1）刚开始蚂蚁随机选择路径，每条从出发节点到结束节点的路径都对应于一个解决方案，并且附有该路径的增益。

（2）当每只蚂蚁到达结束节点时，在路径的每条边上释放信息素，信息素的取值为信息素挥发与蚂蚁释放信息素的综合。

（3）蚂蚁在选择路径时按照概率去选择增益较大的边。某一路径经过的蚂蚁越多，后面的蚂蚁选择该路径的概率越大。最终，所有蚂蚁会选择一条增益较大的路径，这是一个最优或接近最优的解。

基于蚁群算法的组合测试优化方法将蚁群算法应用到组合测试中，采用one-test-at-a-time策略，以获得最高总增益（即最优测试质量）为目标生成测试用例。对每只蚂蚁选择的路径进行排序，将增益最大的作为当前最优解。蚁群算法具有一定的并行性，蚂蚁的搜索过程彼此独立，可以减少计算时间。此外，蚁群算法具有正反馈特性，通过判断路径信息素浓度选择较短路径。这样可以保证在较少的时间内生成有效的测试用例，减小测试用例集规模，降低测试成本。假设某测试用例集有n个参数F＝（f₁,f₂,…,f₃），每个参数有m个属性V_i＝（V_i1,V_i2,…,V_im）。每个属性对应有表示其重要程度的权值W_im。

基于蚁群的组合测试用例生成算法步骤如下：

步骤1　输入蚂蚁数、信息素矩阵，禁忌表置零。蚂蚁最初随机选择下一节点并将其记录到禁忌表中，修改所经过路径的信息素浓度。

步骤2　当蚂蚁选择节点不在禁忌表中时，该节点可以访问。依据转移概率式^[12]

计算下一节点，其中ｈ表示可访问节点，τ_ij(t)表示ｔ时刻边（i,j）的信息素浓度，η_ij(t)表示边(i,j)相应的启发式的值。α和β分别反映了信息素浓度和启发式的影响程度。

步骤3　蚂蚁完成一次节点遍历后，根据蚂蚁选择的路径，按照

更新信息素矩阵，其中ρ表示在t到t+n这段时间信息素的挥发速度

L_k是第k只蚂蚁路径的长度。

步骤４　所有蚂蚁巡回完毕后，对生成的候选解进行排序，依据最优解更新禁忌表。

步骤5　按步骤2至步骤4不断循环，直到所选择的路径获得最高增益。

三、划分聚类算法

K-means算法k-means算法是数据挖掘中著名的划分聚类算法，它根据某一目标函数将给定的数据划分为k个簇，簇内对象相似，而与其他簇中的对象差异较大。k-means算法把簇内点的均值作为簇的中心。在聚类过程中先随机选择k个聚类中心，通过计算余下的点与中心点的欧式距离划分所有数据，之后不断迭代改变簇内的变差。分别求出各个簇上一次迭代后所生成聚类簇的均值作为新的聚类中心，重新对所有数据进行分类，直到分配的k个簇不再发生变化或满足迭代次数。

蚁群算法的组合测试用例生成技术虽然能够有效的减少测试用例，但其基本思想仍然是黑盒测试。黑盒测试没有清晰简明的规格，缺乏对程序结构的考虑。从白盒测试角度进行分析时，测试用例可能会出现冗余。在白盒测试中，逻辑覆盖包括语句覆盖、判断覆盖、条件覆盖、判断／条件覆盖、条件组合覆盖和路径覆盖。本文以6种覆盖方法为依据，结合覆盖方案的不同要求，对已经生成的测试用例进行聚类优化。

假设某待测系统有n个输入参数，每个参数有m个可选项。通过蚁群算法后可以生成Ｚ 个测试用例，每个测试用例都含有ｎ 个参数。现使用

k-means聚类方法对Ｚ 个测试用例进行分类。由于测试用例集与一般的数据不同，它们没有固定的量化标准，因此测试用例聚类划分标准的选择尤为重要。对判定条件执行进行标准化记录，根据测试用例在程序运行时不同逻辑覆盖准则对判定条件执行结果的要求不同，将测试用例转化为由0-1表示的路径数组，0表示没有经过该路径，1表示经过该路径。转化后，Z个测试用例由Z个路径数组表示。

语句覆盖要求程序中每条语句至少被执行一次。判断覆盖要求每个判断至少取一次为真，取一次为假，即程序中每个if条件的分支至少要执行一次。条件覆盖要求判断中每个条件的每种可能性至少运行一遍，如果if条件中包含多个判断语句，每条语句为真为假的情况都应区分开，成为不同的划分路径。判断／条件覆盖满足了判断覆盖准则，同时也满足条件覆盖准则。条件组合覆盖要求判断中各条件结果可能性的组合至少出现一次。路径覆盖可以对程序进行彻底的测试，设计用例测试所有可能的判定路径。

以判断／条件覆盖为例，假设程序中有i个判断条件，每个条件有成立或者不成立两条路径，即每个测试用例有2i项。这样，每个测试用例所选择的判断路径都可以唯一表示。在进行聚类时，将每个测试用例与作为簇中心的测试用例相异或所求的选择路径差异程度Ｄ 作为对测试用例进行分类的量化标准。当用例经过的路径相同或者相似时，参数D大小相近。在基于判断／条件的聚类分析中，D是有效的分类依据。实际软件测试过程中，可以依据测试的现实状况，如程序结构、时间紧迫性、规格

要求等指定所需测试用例的个数k。依照k-means的一般算法将用例集划分为k类即可得到k个簇。在各个簇中进行抽样，得到约简后的测试用例集。

算法的流程如图1所示。

1. 聚类分析技术在软件测试中的具体应用

基于DSKM的测试用例选择方法主要包括数据提取、约束推导、数据降维、数据聚类、用例取样五个部分。DSKM方法首先通过分析测试用例对函数的覆盖情况得到原始数据集，即测试用例与其覆盖函数的二进制向量组成的二维表。然后将从测试用例执行历史记录中挖掘出的成对约束作为输入，使用SSDR (Semi-Supervised Dimensionality Reduction)算法^[18]得到投影矩阵，在投影空间内对原始数据聚类得到聚类标号。接着再将聚类标号作为输入，利用线性判别分析（Linear Discriminant Analysis，简称LDA）选择子空间，在子空间上对数据集进行投影，得到新的数据集，即降维过后的二维表 。最后使用K-means算法对新的数据集进行聚类，将测试用例聚为K簇，使用自适应的取样策略从每一簇中选出一定比率的测试用例组成新的测试用例集。该方法结合SSDR方法和LDA方法对聚类结果进行优化。

图 41

下面具体描述各步骤。

(1)数据提取

本阶段进行原始数据集收集。在测试用例执行过程中，其执行结果会被记录。使用代码覆盖率分析工具对每个测试用例的代码覆盖情况进行分析。使用一个二进制向量表示测试用例的函数覆盖，每一位都记录对应函数在测试用例执行过程中是否被覆盖，如果某个函数被覆盖，该位被置为1，否则，置为0。最终得到测试用例与其覆盖的函数组成的二维表，即原始数据集。得到的原始数据集表示为，其中表示测试用例i对应的函数覆盖的二进制向量，每个代表一个数据对象。

(2)约束推导

得到原始数据集X以后，使用测试用例执行历史记录推导出成对约束信息。在半监督聚类中，通过数据标签或者数据间的约束的形式使用有限的监督。论文使用两种类型的成对约束（Pairwise Constraints）来表示测试用例之间的约束关系^[18]。

1. Must-link：两个测试用例必须在同一簇中。
2. Cannot-link：两个测试用例必须在不同的簇中。

   经过约束推导，得到约束集M和C。M代表Must-link约束集，C代表Cannot-link约束集。

(3)数据降维

在对测试用例进行聚类以前，结合SSDR方法和LDA方法对提取的数据集进行降维处理。首先，利用SSDR方法求出投影矩阵W，在投影空间内对数据集聚类得到聚类标号。然后利用LDA方法选择子空间。在子空间上对数据集进行投影，得到新的数据集，即降维过后的二维表 。

• SSDR（Semi-Supervised Dimensionality Reduction）

将原始数据集X、约束集M和C作为输入，利用SSDR算法^[18]生成变换矩阵，然后使用W矩阵将原始数据集X转换为低维度数据集，其中，Y可以在保持原始数据集X的数据结构不变的同时具有更适合的距离空间。新的距离空间的数据对象更适合用于聚类。

SSDR算法通过公式1求解W矩阵，所求W矩阵为使目标函数最大化的W的值，其中：

公式 1

公式1中，表示数据集X中所有数据对象的数量，表示属于Cannot-link约束集中的数据对象的数量，表示属于Must-link约束集中的数据对象的数量。第一项表示所有数据对象的平均平方距离，第二项和第三项表示包含在成对约束集中的所有数据对象的平均平方距离。为了得到的最大值，尽可能使包含在Cannot-link约束集中的数据实例的平均平方距离最大，同时包含在Must-link约束集中的数据实例的平均平方距离最小。通过公式1，将Cannot-link约束集中数据实例间的距离增大，同时将Must-link约束集中的数据实例间的距离减小，从而保证属于Must-link约束集中的测试用例被聚到同一簇中，而属于Cannot-link约束集中的测试用例被聚到不同簇中。在上式中，使用了两个参数α和β，用来平衡约束的权重，α与β的比值会影响到聚类的结果。

经过SSDR方法求出投影矩阵W以后，利用W矩阵将原始数据集X投影到低维空间，得到数据集Y，并使用传统的K-means聚类算法对数据集Y进行聚类，得到每个测试用例的聚类标号组成的向量Labels，便于下一步使用LDA选择子空间。

• LDA（Linear Discriminant Analysis）

LDA的目的是最大化类间距离，最小化类內距离。使用SSDR方法后得到的聚类标号向量Labels和数据集Y作为LDA方法的输入，进行有监督的维数约简处理，得到降维过后的新数据集X'，用于下一步K-means聚类算法的输入。

LDA是监督维数约减方法，它寻找一个最优的投影方向，使得在投影空间中的不同类数据对象之间距离远，而相同类数据对象之间距离近。LDA的目标函数如下:

公式 2

公式2中类间散布矩阵和类內散布矩阵可以分别表示如下：

公式 3

公式 4

    公式3和公式4中，是类数，是全部样本的均值，是第类样本均值，是第类样本数。

(4)聚类

原始数据集X进行降维处理得到新数据集X'后，使用K-means算法对X'聚类。得到测试用例的K个聚类。K-means聚类算法的典型步骤如下^[19]：

1. 初始化：在多维空间中放置K个初始点，代表每个簇的中心点。初始化中心点的不同直接影响到测试用例选择的结果，所以最好的选择就是两两中心点的距离尽量远。
2. 聚类：根据数据对象的均值，将每个数据对象放置到其最相似的簇中。
3. 更新：当有新的数据对象加入分组中后，对分组的中心点进行更新。
4. 循环：重复聚类和更新的步骤直到每个簇的中心点不再明显改变。

(5)用例取样

经过k-means算法聚类以后，原测试用例集被聚到K个簇中。最后从每一簇中选出测试用例建立新的回归测试用例集。取样策略有很多种，常见的有自适应取样策略^{[10, 20]}、动态取样策略^[21]、随机取样策略^[16]等。本文选择自适应取样策略，首先按照一定比例，如10%，从每一簇中随机选取少量测试用例，每一簇中至少选出一个测试用例，如果某个测试用例覆盖了修改的函数，则直接将其放到新的测试用例集中。如果选出的测试用例为可以发现故障的测试用例，则与其在同一簇中的全部测试用例将被选出来组成新的测试用例集。

参考文献

[1]    Z. Chen, C. Zhenyu, Z. Zhihong, Y. Shali, Z. Jinyu, and X. Baowen, "An Improved Regression Test Selection Technique by Clustering Execution Profiles," Proceedings of the Tenth International Conference on Quality Software (QSIC 2010), pp. 171-9, 2010 2010.

[2]    H. K. N. Leung and L. White, "Insights into regression testing [software testing]," in Software Maintenance, 1989., Proceedings., Conference on, 1989, pp. 60-69.

[3]    G. Rothermel and M. J. Harrold, "Analyzing regression test selection techniques," Software Engineering, IEEE Transactions on, vol. 22, pp. 529-551, 1996.

[4]    章晓芳, 陈林, 徐宝文, and 聂长海, "测试用例集约简问题研究及其进展," 计算机科学与探索, pp. 235-247, 2008.

[5]    G. Rothermel and M. J. Harrold, "A framework for evaluating regression test selection techniques," in Software Engineering, 1994. Proceedings. ICSE-16., 16th International Conference on, 1994, pp. 201-210.

[6]    S. Beydeda and V. Gruhn, "Integrating white- and black-box techniques for class-level regression testing," in Computer Software and Applications Conference, 2001. COMPSAC 2001. 25th Annual International, 2001, pp. 357-362.

[7]    M. J. Harrold and M. L. Souffa, "An incremental approach to unit testing during maintenance," in Software Maintenance, 1988., Proceedings of the Conference on, 1988, pp. 362-367.

[8]    R. Gupta, M. J. Harrold, and M. L. Soffa, "An approach to regression testing using slicing," in Software Maintenance, 1992. Proceerdings., Conference on, 1992, pp. 299-308.

[9]    R. Gupta, M. J. Harrold, and M. L. Soffa, "Program slicing-based regression testing techniques," Journal of Software Testing Verification and Reliability, vol. 6, pp. 83-111, 1996.

[10]    W. Dickinson, D. Leon, and A. Fodgurski, "Finding failures by cluster analysis of execution profiles," in Software Engineering, 2001. ICSE 2001. Proceedings of the 23rd International Conference on, 2001, pp. 339-348.

[11]    W. Masri, A. Podgurski, and D. Leon, "An empirical study of test case filtering techniques based on exercising information flows," Software Engineering, IEEE Transactions on, vol. 33, pp. 454-477, 2007.

[12]    S. Yoo, M. Harman, P. Tonella, and A. Susi, "Clustering test cases to achieve effective and scalable prioritisation incorporating expert knowledge," in Proceedings of the eighteenth international symposium on Software testing and analysis, 2009, pp. 201-212.

[13]    C. Songyu, C. Zhenyu, Z. Zhihong, X. Baowen, and F. Yang, "Using semi-supervised clustering to improve regression test selection techniques," Proceedings 2011 IEEE Fourth International Conference on Software Testing, Verification and Validation (ICST 2011), pp. 1-10, 2011 2011.

[14]    S. Parsa, A. Khalilian, and Y. Fazlalizadeh, "A new algorithm to Test Suite Reduction based on cluster analysis," in Computer Science and Information Technology, 2009. ICCSIT 2009. 2nd IEEE International Conference on, 2009, pp. 189-193.

[15]    尹学松, 胡思良, and 陈松灿, "基于成对约束的判别型半监督聚类分析," 软件学报, pp. 2791-2802, 2008.

[16]    K. Muthyala and R. Naidu, "A novel approach to test suite reduction using data mining," Indian Journal of Computer Science and Engineering, vol. 2, pp. 500-505, 2011.

[17]    A. Ilkhani and G. Abaee, "Extraction test cases by using data mining; reducing the cost of testing," in Computer Information Systems and Industrial Management Applications (CISIM), 2010 International Conference on, 2010, pp. 620-625.

[18]    D. Zhang, Z.-H. Zhou, and S. Chen, "Semi-Supervised Dimensionality Reduction," in SDM, 2007, pp. 629-634.

[19]    P. Yulei, X. Xiaozhen, and A. S. Namin, Identifying Effective Test Cases through K-means Clustering for Enhancing Regression Testing, 2013.

[20]    Z. Chen, C. Zhenyu, Z. Zhihong, Y. Shali, Z. Jinyu, and X. Baowen, "An Improved Regression Test Selection Technique by Clustering Execution Profiles," in Quality Software (QSIC), 2010 10th International Conference on, 2010, pp. 171-179.

[21]    Y. Shali, C. Zhenyu, Z. Zhihong, Z. Chen, and Z. Yuming, "A Dynamic Test Cluster Sampling Strategy by Leveraging Execution Spectra Information," in Software Testing, Verification and Validation (ICST), 2010 Third International Conference on, 2010, pp. 147-154.

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！