动态可靠性约束的多阶段测试资源分配研究

占德志，张国富，2，3，苏兆品，2，3，岳 峰，2

（1.合肥工业大学计算机与信息学院，合肥 230601；2.合肥工业大学工业安全与应急技术安徽省重点实验室，合肥 230601；3.安全关键工业测控技术教育部工程研究中心，合肥 230601）

0 概述

软件测试的目的是检测软件故障、发现和纠正软件缺陷从而提高软件的可靠性，其对软件项目开发至关重要［1-3］。对于一个软件开发项目而言，有接近一半的软件开发资源耗费于软件测试［4］。实际可分配的测试资源往往有限，因此，在软件测试中，软件项目经理的首要任务是制定合理且高效的测试资源分配方案，实现以最小代价（指测试成本和测试资源消耗）获得最大软件可靠性［5-7］的目的。

近年来，为了在软件可靠性、测试成本和测试资源之间实现一个理想的均衡，测试资源分配被描述为一个多目标优化问题，以最大程度地提高软件可靠性并尽可能地降低测试成本和测试资源消耗［8-10］。部分多目标进化算法（Multi-ObjectiveEvolutionary Algorithms，MOEAs）被用于解决多目标测试资源分配问题，如非支配排序遗传算法［11-12］和加权归一化多目标差分进化算法［13］等。与单目标优化算法只输出单个解相比，MOEAs可以得到一个Pareto最优解集，从而为用户提供多种选择，这些不同的选择分别对应可靠性、成本和测试时间之间不同的折中方案，因此，可以帮助用户对整个测试周期进行更加合理的安排［14］。

但是，上述研究均针对静态优化环境，都是简单地假设软件测试只有一个完整的静态阶段。在实际的软件测试过程中，整个测试周期往往会被划分成若干个测试阶段，在不同测试阶段用户可能有不同的需求，这就需要根据每个阶段的测试需求动态制定不同的测试资源分配方案。为此，LEUNG［15］利用拉格朗日乘子法最小化每个阶段的平均错误数，该方法属于单目标多阶段测试资源分配方案。在多阶段多目标测试资源分配（Multi-Stage Multi-ObjectiveTesting Resource Allocation，MSMOTRA）方面，陆阳等人［16］利用多目标差分进化算法，在每个阶段根据不同的测试时间总量来实现最大化可靠性和最小化测试成本的目的，但是，该方法忽略了一个重要细节，即软件中的模块在经历了上一阶段的测试后其关键模块参数（如剩余错误数、错误检测率等）都已经发生变化，如果还是按照初始参数进行优化，将缺少前一测试阶段的测试结果反馈，从而导致算法不能达到更深层的收敛，给出的解往往严重偏离实际最优解。为了解决这一问题，牛福强［17］首先根据上一阶段的测试资源分配方案和测试结果对模块参数进行重新估计，然后利用新的模块参数和第三代广义多目标差分进化（Generalized Differential Evolution 3，GDE3）算法［18］在当前阶段进行优化。但是，该方法在选择每个阶段的最优方案时偏好性太强，只考虑最优非支配解集中可靠性最高的解，而没有考虑测试成本和测试时间，不能充分体现多目标优化的优势。

虽然已有研究可以很好地解决多目标测试资源分配问题，但是通常只关注测试时间总量约束，没有考虑用户对软件的可靠性需求，导致在解集中存在许多可靠性非常低的测试资源分配方案，这些无用解带来了巨大的计算开销和信息冗余，也背离了研究多目标测试资源分配问题的初衷。

本文从用户对软件可靠性需求的角度出发，构建一种动态可靠性约束的多阶段多目标测试资源分配模型，基于每个阶段不同的可靠性约束来为各个模块分配一个测试时间下限，以降低搜索空间。基于GDE3、参数估计、种群重新初始化和最优方案选择，提出一种多阶段多目标测试资源分配算法，以在满足用户对软件可靠性需求的同时为用户提供满意的解集。

1 问题描述

与惯例相同［11-13］，本文基于经典的并串联模块软件系统研究测试资源分配问题。如图1所示，软件系统包括m∈N个子系统，每个子系统Sj(j∈(1，2，…，m))包含nj∈N个模块。测试资源分配的目的是给系统中的每个模块Mjk(k∈(1，2，…，nj))分配合适的测试资源，以提高系统的整体可靠性。

图1 并串联模块软件系统结构Fig.1 Structue of parallel-series modular software system

在软件测试过程中，主流的测试资源分配问题均是针对测试时间分配［11-13］，考虑如何合理分配软件测试人员的总工作时间（即软件测试人员数乘以每个测试人员的工作时间，通常以小时为单位）。与多数已有研究相同［11-13］，本文也依据测试时间来分析测试资源分配问题。不失一般性，本文采用文献［17］中测试阶段的划分方式，假设总的测试时间T*被划分成p∈N个连续的测试阶段，其中，第i∈（1，2，…，p）个阶段的测试时间预分配量为，满设模块Mjk在阶段i分配到的测试时间为，则阶段i的实际分配总量Ti应该小于前i个阶段的预分配量之和减去前i-1个阶段的实际分配量之和［17］，计算如下：

在前面每个阶段选取的分配方案不一定恰好用完预分配量，因此，可能在每个阶段都有少量的剩余测试时间可供下一阶段使用。

子系统Sj是由nj个子模块并联组成的，当子模块都不工作时，该子系统寿命结束，可以根据Mjk模块的可靠性求出子系统Sj在第i个测试阶段的可靠性［17］，计算如下：定义，第i个测试阶段的系统可靠性Ri可定义如下：

根据文献［17］中对并串联模块软件系统的可靠性

综上，本文所研究的动态可靠性约束的多阶段多目标测试资源分配问题（DRC-MSMOTRA）可以形式化表示为：

在每个测试阶段需要满足不同的可靠性约束和测试时间约束，因此，式（6）是一个典型的动态约束多目标优化问题，解决该问题的难点是每个阶段的解空间都大不相同，传统的优化方法很难适应搜索空间的动态变化，因此，本文采用适应性更高的多目标进化算法进行求解。

2 多阶段多目标测试资源分配算法设计

本文选择广义多目标差分进化算法GDE3［18］作为DRC-MSMOTRA问题的基本求解框架，这是因为GDE3在针对3个目标优化问题时相比非支配排序遗传算法［11-12］速度更快，需要设置的参数更少，算法收敛性更好。关于GDE3的详细介绍可参考文献［18］，本文结合基本GDE3，提出多阶段动态可靠性约束处理算法MS-DRC-GDE3。MS-DRC-GDE3算法的每个个体采用一维实数编码，编码中的每一个基因位代表一个模块被投入的测试时间。每个个体的优劣用式（6）中的f1、f2、f33个函数同时进行评估。

MS-DRC-GDE3算法流程如图2所示，具体步骤为：

步骤1判断i是否已达到最大阶段数p，如果已达到，则结束算法；否则，执行步骤2。

步骤2判断当前阶段是否为第1个阶段，如果不是，则根据前面阶段的测试结果对所有模块重新进行参数估计，然后根据新的模块参数对种群重新进行初始化以生成父代种群。

步骤3对种群执行选择、差分变异和交叉等进化操作以生成子代种群，再将父代和子代种群一起进行非支配排序和拥挤度计算，选择最优的个体组成新的父代种群。

步骤4判断算法是否达到本阶段的最大迭代次数，如果未达到，则执行步骤3；否则，对最后的最优解集执行加权归一化处理，选择适应度最小的解作为阶段i的最优分配方案，当阶段i测试完毕，进入下一阶段，i=i+1，执行步骤1。

图2 MS-DRC-GDE3算法流程Fig.2 Procedure of MS-DRC-GDE3 algorithm

2.1 模块参数估计

在多阶段测试资源分配中，前面阶段的测试结果会直接影响模块的关键参数，包括剩余错误总数与错误检测率因此，在一个测试阶段i执行完毕后，需要对i+1阶段的模块参数重新进行估计，否则会误导算法的进化。在软件测试中，通常的做法是收集在每个模块上消耗的测试时间和检测出的错误数，然后利用这些数据对模块的参数进行极大似然估计［17］，计算如下：

2.2 种群初始化

在DRC-MSMOTRA问题中，每个阶段的可靠性约束和测试时间约束均不相同，因此，在种群进化前需要对种群按照新的约束空间重新进行初始化。鉴于每个阶段的迭代次数不可能无限大，因此，如何在较少的迭代次数内迅速搜索到较好的解是首先需要解决的问题。一个最直接的做法就是在种群初始化时尽量让种群靠近最优解集区域，为此，本文通过模型分析来降低搜索空间。以第i个测试阶段为例，因为可靠性的取值为［0，1］之间的实数，由式（2）的连乘积可以得到如下的必要条件：

在子系统Sj中，至少要有一个模块分配的测试时间满足上式，本文将该测试时间下限记为：

本文在种群初始化时利用上述条件尽量让种群靠近最优解集区域。对于第1个测试阶段，个体编码中每个模块对应的基因位随机初始化为：

对于第i＞1个阶段，由于前一阶段的分配方案对于本阶段具有一定指导作用，比如可以显示哪些模块比较耗时。基于此，本文根据前一阶段方案的分配比例来进行初始化，如下：

容易验证通过式（9）和式（10）或式（11）初始化的个体都满足测试时间的上下界约束。需要指出的是，上述初始化过程并不能保证每个个体都满足可靠性约束下界，因为式（8）只是一个必要条件。本文目的是尽可能地让个体靠近满足可靠性需求的区域，从而让个体迅速逼近最优解集，加快算法的收敛。

2.3 加权归一化处理

在每一个测试阶段，当种群进化到最大迭代次数时，MS-DRC-GDE3算法会输出一个最优解集，用户需要从解集中挑选一个解作为当前阶段的测试时间分配方案。传统的做法是选择解集中可靠性目标值最大的解，但这种选择方式偏好性太强，忽略了测试成本和测试时间消耗的平衡。本文采用文献［13］中的加权归一化方法来选取最优解。加权归一化方法可以简单快速地衡量多目标解的优劣，该方法在衡量解的分布性方面有较大优势，同时可兼顾收敛性，已在多目标优化问题的求解中得到广泛应用［19-20］。

加权归一化方法首先对解集中的每一个目标进行min-max归一化，以消除3个目标之间的统计误差，其次利用复合目标适应度函数将多目标整合成复合单目标其中，wy为目标y的加权值，f(x)表示第x个多目标解的适应度值。由于本文的目的是权衡可靠性、测试成本和测试时间3个目标，因此适应度函数表示为：

最后，比较每个解的适应度值，选取适应度值最小的解作为当前阶段的最优测试资源分配方案。

2.4 时间复杂度分析

时间复杂度直接影响算法的收敛速度以及运行时间。MS-DRC-GDE3算法的基本流程如图2所示，假设种群的规模为N，优化的目标个数为M，在种群初始化以及选择、交叉和变异阶段只处理最高等级的N个个体，该操作的时间复杂度为O(N)。在非支配排序和拥挤度计算阶段算法的时间复杂度与原有的GDE3算法保持一致，为O(MN·lbN)［18］。加权归一化处理阶段也仅处理最高等级的N个个体，同理，其复杂度也是O(N)。另外，本文所提算法为多阶段算法，其总阶段数为P，每个阶段的迭代次数为Gmax。综上，MS-DRC-GDE3算法的总时间复杂度为O(P·Gmax·MN·lbN)。

3 实验结果与分析

3.1 实验参数和评价指标

为了验证本文所提模型和算法的有效性，模拟2个并串联模块软件系统进行测试。第1个系统共有11个子系统、30个模块，称为复杂系统，第2个系统共有16个子系统、50个模块，称为大型系统。系统模型参数信息如表1所示，系统中的初始模块参数范围如表2所示，测试阶段相关参数如表3所示。对于每个系统，根据表2所给的范围随机生成10组初始模块参数，与表3所给的约束参数一起构成相应的实验测试实例，且每个实例在Intel Core i7CPU、10 GB RAM个人计算机上独立运行30次。

表1 系统模型参数信息Table 1 System model parameters information

表2 初始模块参数范围Table 2 Initial parameters range of modules

表3 测试阶段相关参数Table 3 Related parameters of testing stage

为了验证本文所提MS-DRC-GDE3算法的有效性，将其与文献［17］中的多阶段测试资源分配算法MS-GDE3进行对比分析。为了对比的公平性，加权归一化过程中的w1、w2、w3采用文献［13］中的推荐设置｛0.1，0.4，0.5｝，MS-DRC-GDE3算法的其他参数与MS-GDE3算法保持一致，种群规模为100，交叉概率为0.9，变异概率为0.7。

为了对比不同算法所得分配方案的优劣，本文采用经典的覆盖值（Coverage Value，CV）［21］指标来评估不同算法的收敛性。覆盖值提供了一种最直接的比较方式，假设A和B分别是2种不同的算法所获得的解集，A中一个解的所有目标值都不比B中另一个解的所有目标值差，则认为前者覆盖了后者。CV（A，B）表示B被A中解集所覆盖的百分比，即B中被A覆盖的解的个数与B中解的总数的比值。若CV（A，B）大于CV（B，A），则意味着A中的解相比B更优。在计算时，为了使算法在每个实例中获得的解集更具统计学意义，首先将每个算法对应每个实例运行30次的解组合在一起，然后去掉重复的解，最后计算每个算法组合解集之间的CV值［22］。此外，为了衡量算法的整体性能，本文采用较流行的超体积值指标［11，13］。超体积表示非支配解集和参考点之间的空间体积大小，其可以从整体上衡量解集的收敛性和多样性，超体积值越高表示解集的整体质量越高。在计算超体积时，参考点的选择至关重要。对于每个实例，本文合并所有算法30次运行所获得的解集，然后去掉重复解并根据非支配关系对所有解进行排序，去掉所有被支配的解，最后将剩余非支配解集中每个目标的最大值略微放大作为最终的参考点［22］。

3.2 不同模型的对比

与文献［17］中的多阶段模型MSMOTRA不同，本文DRC-MSMOTRA模型为了满足用户的可靠性需求，在每个阶段都有不同的可靠性约束，本次实验将分析上述2种模型的优劣。根据表1的2个模拟系统各随机生成10个不同的实例，为了对比的公平性，基于与MSMOTRA模型契合的MS-GDE3算法进行测试。

2种模型所得解集的覆盖值结果如表4所示，其中，A和B分别表示DRC-MSMOTRA模型和MSMOTRA模型，较优的覆盖值用加粗字体表示。从表4可以看出，在复杂系统中，与MSMOTRA模型获得的解相比，DRC-MSMOTRA模型在3个阶段中解的覆盖值分别提高约97个、42个和48个百分点，平均提高了约62个百分点。对于大型系统，与MSMOTRA模型获得的解相比，DRC-MSMOTRA模型在3个阶段中解的覆盖值分别提高约90个、61个和26个百分点，平均提高了约59个百分点。上述实验结果表明，在不同软件系统不同参数的条件下，与MSMOTRA模型相比，DRC-MSMOTRA模型可以获得更优的解，更能满足用户的可靠性需求。

表4 2种模型的覆盖值对比结果Table 4 Comparison results of coverage values of two models

需要指出的是，在第2阶段和第3阶段，在极个别实例上会出现CV（A，B）与CV（B，A）相差不是很大的情况，尤其是在大型系统的第3阶段，这说明MS-GDE3算法在DRC-MSMOTRA模型上有时也能获得理想的解集，因此，有必要进一步测试分析MS-GDE3算法在DRC-MSMOTRA模型上的综合表现。

3.3 不同算法的对比

本文根据表1的2个模拟系统随机生成10个不同的实例，基于本文DRC-MSMOTRA模型对比分析MS-DRC-GDE3算法和MS-GDE3算法的性能。2种算法得到的覆盖值结果如表5所示，其中，A和B分别表示MS-DRC-GDE3算法和MS-GDE3算法。从表5可以看出，在复杂系统中，与MS-GDE3算法相比，MS-DRC-GDE3算法在3个阶段中解的覆盖值分别提高约73个、66个和67个百分点，平均提高了约69个百分点。对于大型系统，与MS-GDE3算法相比，MS-DRC-GDE3算法在3个阶段中解的覆盖值分别提高约76个、75个和89个百分比，平均提高了约80个百分比。上述实验结果表明，在不同软件系统不同参数的条件下，MS-DRC-GDE3算法在每个阶段所获解的质量均高于MS-GDE3算法。

表5 2种算法的覆盖值对比结果Table 5 Comparison results of coverage values of two algorithms

为了进一步分析2种算法的整体性能，对比2种算法所得解集的超体积的均值和标准差，结果如表6、表7所示，括号内为标准差。从表6、表7可以看出，MS-DRCGDE3算法的超体积明显优于MS-GDE3算法，这说明MS-DRC-GDE3算法的解集整体质量更高。此外，标准差能够体现数据的波动幅度，在第1阶段，MS-DRCGDE3算法的超体积标准差比MS-GDE3算法小一个数量级，在第2、第3阶段，虽然MS-DRC-GDE3算法的超体积标准差比MS-GDE3算法略大，但是结合均值和标准差明显可以看出，MS-DRC-GDE3算法的超体积实际波动都比MS-GDE3算法小，这说明MS-DRC-GDE3算法比MS-GDE3算法更加稳定，可以在收敛性和多样性之间实现更好的平衡。造成上述结果的原因是MSDRC-GDE3算法根据每个阶段中用户的可靠性需求推导出每个模块的测试时间下限，根据该最低时间要求对种群进行初始化，从而使得整个种群迅速地向用户满意的解区域逼近。此外，MS-DRC-GDE3算法采用的加权归一化方法，可以取得可靠性、成本和测试时间三者之间的均衡，从而在每个阶段使种群有更多的空间去探索更好的解。

表6 2种算法在复杂系统中的超体积结果对比Table 6 Comparison of super volume results of two algorithms in complex system

表7 2种算法在大型系统中的超体积结果对比Table 7 Comparison of super volume results of two algorithms in large scale system

为了更加直观地解释超体积指标代表的含义，图3给出2种算法分别在复杂系统实例6、大型系统实例5上最后阶段的解集的分布，2种对比算法在这2种实例上的超体积值差异较大，可以更加清晰地展现超体积值的特点。从图3可以看出，与MS-GDE3算法相比，MS-DRC-GDE3算法得到的解在目标空间的分布更广，具有更好的多样性。此外，MS-DRCGDE3算法的收敛性比MS-GDE3算法更好，MSDRC-GDE3算法解集中有相当多的分配方案明显优于MS-GDE3算法，即前者具有更高的可靠性、更低的测试成本和更短的测试时间。

图3 2种算法所获解的分布Fig.3 Distribution of solutions obtained by two algorithms

4 结束语

基于多目标进化算法的多目标测试资源分配可以给用户在可靠性、成本和测试时间上提供较多折中的方案，从而使用户有更多的体验，但已有测试资源分配方案大多只考虑测试时间约束而忽略了用户的可靠性需求，导致解集中存在大量可靠性很低的方案，降低了用户满意度。本文针对多阶段测试资源分配问题，从用户对软件的可靠性需求角度出发，构建一种动态可靠性约束的多阶段多目标测试资源分配模型，基于模块参数估计、考虑时间下限的种群初始化、加权归一化、多目标差分进化算法，设计一种动态可靠性约束的多阶段多目标测试资源分配算法。实验结果表明，本文所提模型和算法具有有效性且能够取得良好的资源分配效果。下一步将考虑成本约束并尝试基于成本约束来分析和推演每个模块的测试时间上限，此外，还将改进算法中的拥挤度计算等环节，从而进一步提升算法的整体性能。