基于自适应高斯混合模型的软件测试用例集约简算法研究

杨永国

(中国人民解放军91550部队，辽宁 大连 116023)

0 引言

软件规模越大，其逻辑复杂性越高，对这些软件的可靠性要求也就越高。软件的隐藏错误能够造成其自身运行的失败。也就是说软件的隐藏错误是影响软件可靠性的最关键因素之一[1]。对于小规模的软件，工程实践中大多采用人工设置断点的方法来进行测试，以查找出错误。不过人工方法判断错误位置较为复杂，且难度较大，不适用于大规模的软件测试。因此，为了更加精准且高效地查找和消除软件错误，专家学者们开展了广泛的研究，提出了一些解决方法，并研发出对软件进行单元、静态和动态测试的工具软件。这些方法和测试软件，都要求测试用例集尽可能覆盖全面，只有这样才能精准地定位错误，提高测试的有效性[2-4]。但测试用例集包含的用例数量应该尽量约简，以降低测试成本。

刘锋等人提出基于向量相似度的测试用例集约简方法[5]。张蕊等人提出一种基于搜索树的用例约简方法，求得约简问题的全局最优解[6]。谢经纬在测试用例集约简中引入需求分析，提出了两阶段用例集优化方法，分为需求切片和用例集优化两个步骤[7]。张晨光等人提出一种在线测试用例集约简方法，将测试集约简嵌入测试生成流程内，测试生成过程为测试集约简提供了测试序列与测试目标之间的满足关系[8]。杨羊等人通过定义和合并基于ASM模型测试生成的等价迁移和等价状态，减少了无效访问状态和无效迁移路径的数量，实现了测试用例集空间的约简[9]。苏小红等人采用面向错误定位需求的测试用例约简方法，降低错误定位的复杂度，提高错误定位的精度[10]。

这些用来约简测试用例集的方法还存在一些主要问题如下：1)如何建模测试用例集之间的关系，以提高查找软件错误的准确度；2)如何实现参数设置的简化，或者实现自适应的参数设置。为了解决这些问题，本文提出了一种基于自适应高斯混合模型的用例约简算法。该算法引入高斯混合模型，寻找测试用例间的关系，抽取满足测试需求的测试用例，实现用例集的约简；同时通过自适应策略，简化参数设置。

1 高斯混合模型

软件测试用例集数据的概率分布通常很复杂，因此引入高斯混合模型来模拟逼近和约简软件测试用例集，以简化问题[11-14]。高斯混合模型(GMM，gaussian mixture model)是M个高斯模型(聚类簇)的加权和，其对数据的M类概率密度分布进行高斯估计。每个高斯概率密度函数都与一个类对应。训练时采用了期望最大(EM，expectation maximization)算法。

设每个样本都对应于一个类，也就是对应于一个高斯概率密度函数，而整个样本集对应M个高斯概率密度函数。但具体每个样本xi对应于哪个高斯概率密度函数不确定，在GMM中，每个高斯概率密度函数所占的权重φj也不确定。式(1)所示为GMM:

(1)

每一个高斯概率密度函数，也就是单高斯模型都有3个参数φj、μj、∑j。进行高斯混合模型建模时，就要确定3N个参数。

需要通过样本集X={x1,xi,…,xN}来估计GMM的所有参数[15]Φ=(φ1,φj,…，φM)T，样本xj的概率如式(2)所示:

(2)

其中:Cj为协方差矩阵。

对GMM参数进行估计，目前最多采用的是EM算法，其具体流程如下[15-19]：

2)后验概率估计步骤。用式(3)估计φj的后验概率:

(3)

3)最大化步骤。根据式(4)对权值φj进行更新:

(4)

根据式(5)对均值μj进行更新:

(5)

根据式(6)对方差矩阵Cj进行更新:

(6)

4)收敛条件。迭代计算步骤2)和步骤3)，权值φj、均值μj和方差矩阵Cj会不断地更新，当p(X|Φ)-p(X|Φ)′<ε时停止进行迭代。p(X|Φ)′为更新权值φj、μj均值和方差矩阵Cj后根据式(3)计算的值，ε为阈值，一般ε=10-5。

2 基于自适应高斯混合模型

但采用的高斯混合模型聚类簇数目通常是经验值，很容易造成聚类准确度的降低。具体到软件测试用例集约简的场景，经验聚类簇数目对用例集多变的适应性较差，无法做到自适应。因此本文对高斯混合模型进行改进，使其可以自适应的确定聚类簇数目。

改进的思想为：使用K-means初始化EM，自适应地确定聚类簇数目，在此过程中能够评判聚类结果，同时给出式高斯混合模型的所有参数，这些参数作为各个聚类簇进行新一轮迭代计算的参数，最终得到的结果更趋于最优解[15]。

针对软件测试用例集约简研究，为解决现有高斯混合模型聚类算法只能使用经验聚类簇数目值的缺陷，根据上述改进思想，本文使用了自适应高斯混合模型算法，算法的具体实现步骤如下所述，实现流程如图1所述。

图1 自适应高斯混合模型的实现流程

1)先按经验设置M0个聚类簇，按照第1章节中的步骤(1)进行初始化协方差矩阵Cj、每个高斯概率密度函数所占的权重φj和均值μj，并用EM算法对模型进行优化，计算出初始化聚类结果。

2)在后续迭代计算的过程中，计算出第i个样本xi属于第j个聚类簇的概率pi,j。根据式(7)计算最大的(pi,j)max与排第二的(pi,jmax-1)的比值ri。第i个样本xi聚类到某个聚类簇，要求(pi,j)max相对于(pi,j)max-1要有明显的差别，即(pi,j)max应当比(pi,j)max-1大很多。也就是可以用ri来衡量聚类结果的优劣。ri越小，聚类结果越好；ri越大，聚类结果越差。

3)设定阈值Thr。通过给定Th的值，能够衡量类聚类结果是否满足要求。当ri≤Thr时，第i个样本xi可以归类为(pi,j)max对应的聚类簇；当ri>Thr时，第i个样本xi不适合归类为目前的所有聚类簇，需要增加聚类簇数目。聚类簇数目不能无限的增加下去，否则就失去了聚类的意义，需要设定一个最大聚类簇数目值Mmax。当聚类簇数目数目达到Mmax时，则第i个样本可以归类为(pi,j)max对应的聚类簇，而不再新增聚类簇的数目。

4)当聚类簇数目增加后，需要对新模型的参数进行初始化调整。迭代的重新执行步骤1)～3)，当聚类簇数目不再增加，或者达到最大时，完成模型训练，得到模型参数。

5)当步骤4)得到的模型中，存在φj很小的聚类簇,即φj≤Thφ时，可将该聚类簇删除，并将该聚类簇对应的样本xj归类到倒数第二次迭代时(pi,j)max对应的聚类簇中。因为聚类簇的φj≤Thφ时，可以认为该聚类簇的代表性不足。然后对模型进行计算，得到最终的模型CL，及模型参数。

3 实验结果与分析

3.1 实验数据集

本文采用使用广泛并且便于比较的西门子软件测试用例集[1,20]。该由Siemens Corporate Research的专家开发，含有7类程序代码Print_tokens1、Print_tokens2、Schedule1、Schedule2、Replace、tacs和tot_info，每类程序代码有1个无错误版本和一些含有错误的版本。软件测试用例集中每类程序代码的行数、初始测试用例数、程序中错误数、测试用例数如表1所示[1]。针对每类程序代码，该软件测试用例集使用了5种类型编程语言进行的代码编写，满足常用编程语言需求的代码需求。

表1 软件测试用例约简用数据集

3.2 评价标准

实验中，采用约简率、错误检测率和错误检测丢失率这三个指标来评价实验结果，以验证算法的有效性、正确性和稳定性。

3.2.1 约简率

约简率计算如式(8)所示，为现有软件测试用例集中的测试用例数目与约简后软件测试用例集中的测试用例数目的差值，比上现有软件测试用例集中的测试用例数目，得到的比值[1]。

(8)

其中:RR为约简率，|USN|表示现有软件测试用例集中的测试用例数目；|USN′|表示约简后软件测试用例集中的测试用例数目。

3.2.2 错误检测率

错误检测率计算如式(9)所示，为约简学习初始用例后，从测试用例中检测到的程序代码错误个数与测试用例中实际程序代码错误个数的比值[1]。

(9)

其中：EDR为错误检测率，EN表示现有软件测试用例集的测试用例包含的程序代码错误数；EN′表示使用约简算法学习初始用例后，从软件测试用例集的测试用例中检测出的程序代码错误数。

3.2.3 错误检测丢失率

错误检测丢失率计算如式(10)所示，为约简学习初始用例后，从测试用例中检测到的程序代码错误个数与测试用例中实际程序代码错误个数的差值，比上测试用例中实际程序代码错误个数，得到的比值[1]。

(10)

其中:ELR为错误检测丢失率。

由式(8)、式(9)和式(10)可以比较高斯混合模型、模糊K-Means聚类模型和本文提出算法的约简率、错误检测率和误差检测丢失率。

3.3 实验结果分析

为了验证本文提出的基于自适应高斯混合模型的软件测试用例集简约算法的性能，对比分析了本文提出算法、基于高斯混合模型的软件测试用例集简约算法和基于模糊K-Means聚类模型的软件测试用例集简约算法。

3.3.1 约简率分析

使用3种算法约简后，得到的软件测试用例集中的测试用例数量如表2所示[1]。

表2 约简后的初始用例数

3种算法约简率如表3所示[1]。通过分析，基于模糊K-Means聚类模型的软件测试用例集简约算法的约简率优于基于高斯混合模型的软件测试用例集简约算法。本文提出算法的约简率高于上述两种算法，其总约简率相对基于模糊K-Means聚类模型的软件测试用例集简约算法高11.46%，相对基于高斯混合模型的软件测试用例集简约算法高6.42%。约简率的提升，可以在一定程度上降低软件测试的复杂度，提高软件测试的效率。

表3 3种算法的约简率

3.3.2 错误检测率分析

使用3种算法约简后，从测试用例集中检测出来的程序代码错误数量如表4所示[1]。

表4 约简后的检测出的错误数

3种算法的错误检测率如表5所示。从表中数据可知，基于模糊K-Means聚类模型的软件测试用例集简约算法的错误检测率优于基于高斯混合模型的软件测试用例集简约算法。本文提出算法的错误检测率高于上述两种算法，其总错误检测率相对基于模糊K-Means聚类模型的软件测试用例集简约算法高34.53%，相对基于高斯混合模型的软件测试用例集简约算法高4.76%。使用本文提出算法能够检测出更多的错误数，可以提高软件测试的可靠性，进而提高被测软件的正确性。

表5 3种算法的错误检测率

3.3.3 错误检测丢失率分析

3种算法的错误检测丢失率如表6所示。

表6 3种算法的错误检测丢失率

从表中数据可知，基于模糊K-Means聚类模型的软件测试用例集简约算法的错误检测丢失率优于基于高斯混合模型的软件测试用例集简约算法。本文提出算法的错误检测丢失率低于上述两种算法。错误检测丢失率低，代表漏检的少错误数量，错误检测丢失率越低越好。相对其它两种算法，本文提出算法的错误检测丢失率最低，这体现了提出算法约简得到的测试用例集对程序代码错误的覆盖度较高。

4 结束语

软件测试用例集聚类和约简是一个时研时新且充满挑战的研究方向。当前软件测试用例集聚类、约简方法存在需要根据经验给出聚类簇数目，导致自适应性不强的问题。本文提出了一种改进的高斯混合模型算法应用于软件测试用例集约简，以自适应的确定聚类簇的数目，并评估聚类效果的优劣。

提出的自适应高斯混合模型算法的优点是：算法在初始化和迭代过程中无需固定聚类簇数目，可以根据不同软件测试用例集数据的特点自适应确定聚类簇数目，提升聚类的自适应性、准确性和泛化性，实现用例集最优约简化。实验结果表明，相对于高斯混合模型算法和模糊K-means聚类算法，提出算法的约简率和错误检测率更高。约简后虽然软件测试用例集规模精简，但覆盖率高。