一种非参数化SRGM预测能力的研究

惠子青, 刘晓燕, 严 馨

(昆明理工大学 信息工程与自动化学院， 云南 昆明 650500)

软件可靠性是软件工程领域一个重要分支，在软件保障中具有重要作用[1]。软件可靠性是影响软件质量的最重要因素，评价软件可靠性的方法之一是分析软件的测试过程[2]。为了能够准确评估软件的可靠性，现已开发出上百种应用于实际项目的软件可靠性增长模型(Software Reliability Growth Models，SRGM)。开发出的这些模型都是基于各种各样的假设，所以模型的通用性和预测精度不高。其中最经典的非齐次泊松过程(non-homogeneous Poisson process，NHPP)类软件可靠性增长模型，它的假设条件[3]是：1)软件失效遵循一个NHPP过程；2)在任何时刻软件的失效都是由软件中存在的故障引起的；3)在任何时间序列构成的时间区间中检测到的故障数是相互独立的；4)在任何时刻软件的失效强度与软件中存在的故障数成正比。由于非参数化可靠性增长模型不需要估计参数，且不需要做出条件假设，只需要将历史故障数据作为输入，通过机器学习的相关算法训练非参数化模型，因此非参数化可靠性增长模型可以获得更高的预测精度和更强的通用性。

非参数化的SRGM使用机器学习技术中的人工神经网络、遗传编程和支持向量机(Support Vector Machine，SVM)相关的技术知识来深入了解和预测软件可靠性。其中支持向量机是基于结构风险最小化原则，寻求最小化泛化误差(训练误差和置信区间)的上界，这样具有更高的泛化能力。而经验风险误差原则仅最小化训练误差，支持向量机另一个重要特点是训练支持向量机等同于解线性约束的二次型规划问题。这样SVM有全局最优的唯一解[4]。基于支持向量回归(Support Vactor Regerssion，SVR)技术的非参数化SRGM在软件测试领域已经被广泛应用且展现出了良好的学习性能，但是在实际应用时也存在一些局限性。第一个问题是在训练数据集很小的情况下，训练集不能充分学习和构建正确的可靠性预测模型，这将会导致偏差较大甚至错误的预测结果。第二个问题是在软件测试过程中被检测到的第一个故障对软件可靠性的影响与最后一个不同。比如在软件测试早期阶段发现的故障大都是“简单”故障，对软件可靠性影响不大，后期的故障如果盲目删除，将有可能引入新的故障，会导致软件发生实质性变化，这与模型当中失效次数独立性的假设条件是相违背的。上述第一个问题的解决方法是假设训练集的元素是不均匀的概率分布，并将其用于最小化风险度量的优化问题。第二个问题的解决方法是通过为训练集的元素分配不同的权重。其中一种简单的方法是分配排序权重，在软件测试的初期将小权重分配给训练集的第一个元素，在软件测试的后期将较大的权重分配给后面元素。

针对上述问题，本文提出了一种基于SVR的非参数化的软件可靠性增长模型(BT-SRGM)，其核心思想是通过一系列特殊规则产生的权重来代替分配给训练数据元素的精确权重。针对少量的训练数据集，根据极小极大策略，构建一组可选择的分布集合，并在选择区间的上界进行最小化计算，最终得到模型参数。

1 支持向量机回归

回归分析的目标是估计Rm中一组采样点x(x1,x2,…,xn)与目标值y(y1,y2,…,yn)之间函数f(x)的依赖关系。首先假设数据集S={(x1,y1),(x2,y2),…,(xn,yn)}，其中xi∈Rm表示包含m个特征的特征向量，yi∈Rm表示映射输出值，其中〈·,·〉表示内积。支持向量机可以用(1)式所示的函数来拟合训练数据：

f(x)=〈a,φ(x)〉+b,

(1)

其中a=(a1,a2,…,am)和b是函数f(x)的参数。φ(x)是Rm→G的一个非线性映射,G表示一个高维特征空间。

经验风险是对训练集中所有的样本点损失函数的平均最小化，其中损失函数表示预测值f(x)与实际值y之间的差[5]。经验风险越小说明模型f(x)对训练集的拟合程度越好。标准的SVR技术是假设训练点的概率分布为非参数的概率分布函数，其使用导致经验预期风险为

(2)

其中l是不敏感参数ε的损失函数，其定义为

(3)

(4)

这里给出不精确加权的两个性质：①权值是非负的;②w1+w2+…+wn=1。

C>0是一个常数且决定了f(x)的平滑度与ε的差量，通过系数a和b值的最小化来估计规范化风险函数：

(5)

(6)

支持向量机不直接求解φ(xi)和φ(xj)，而是用核函数代替它。核方法避免了非线性映射φ(·)的具体形式，而且不需要特征空间的内积运算。只要满足Mercer条件[6]的函数都可作为核函数，这样就可以转化为对偶优化问题：

(7)

(8)

其中σ是确定几何结构的内核参数，回归函数f(x)可以用拉格朗日乘数法表示：

(9)

(10)

如果固定系数a、b的值，变量w和约束条件P会有一个线性规划集合。因为P是凸的，所以在集合的极值点之间可以找到最优解。如果极值点的个数为n个,则可以将上述问题转化为标准最优化问题

(11)

(12)

2 权重的产生与分配方法

基于SVR技术的非参数化SRGM在实际应用中存在两种缺陷：1)在训练数据集较少的情况下，ε-污染模型的产生可以加强非参数化模型的学习深度；2)在软件测试过程中被检测到的第一个故障对软件可靠性的影响与最后一个不同，在调试过程中通过权重的分配凸显获得数据的重要性。利用数学中取交集的思想，将ε-污染模型和动态权值分配方法相结合，这样就构建了一种通用性更好、预测精度更高的非参数化的SRGM，我们将这种新结合的SRGM命名为BT-SRGM。

2.1 不确定ε-污染模型

不确定ε-污染模型产生的权重集合P(ε,w)，其中w=(w1,…,wn)：

wi=(1-ε)pi+εhi，

(13)

2.2 比较产生的权重

我们给出两个条件：①w1≤w2≤…≤wn；②w1+w2+…+wn=1。

由以上式子可知，将权重w(w1,…,wn)的集合定义为M，则其有以下性质：①wi-wi-1≥0，i=2,…,n；②wi≥0,i=1,…,n。

需要特别说明的两种情况：①只有一个非零权重分布集合，最后一个加权向量起决定性作用；②权重分布呈现均匀分布。

2.3 两个权重的交集

图1 单纯形中两组权重的交点为n=3

在研究P(ε)和M的交集之前，用标准单位单纯型来考虑n=3时的交集，图1说明了单位单纯形中每个点都可能是加权向量，(w1,w2,w3)这个集合对应三角形ABC的限制区域。P(ε)是小三角形限制区域。它们的交叉点受阴影区的限制，由图可看出两个单独权重要比权重集大得多。交集的权重向单纯形的最后一个顶点移动，这就意味着最后一个元素要获得最大的权重，对于P(ε)来说，小单纯形限制了最后一个元素获得过大的权重值[8]。

上面给出了两个权重P(ε)和M的极值点交集，它们的交集保留了两组元素的共同优点，这是求解s=n规划问题的必要条件。每一个优化问题都由一个极值点w(k)(k=1,…,n)定义，因此，使用n个标准加权的SVR很容易求解极值点。

3 BT-SRGM的算法

用伪代码描述了BT-SRGM的工作过程，如下所示：

要求：S(训练集)，参数ε,σ=(σ1,…,σn)，C=(C1,…,Ct)

令f(Xn+1)

{S训练集，S测试集}：S←S训练集∪S测试集

i←1;j←1

Repeat

k←1

Repeat

w←wk

w,σi,Cj和S训练集代入(11)式中

k++

Untilk>n

MSE(i,j)←MSE(kopt(i,j),S测试集,σi,Cj,wkopt(i,j))i++；j++

Untili>r;j>t

(i,j)opt←arg min(i,j)MSE(i,j)

4 实 验

4.1 性能评价标准

参数估计中均方误差是指参数估计值与参数真值之差平方的期望值(Mean Square Error，MSE)，记为MSE[9]：

(14)

其中yi、f(xi)分别为实际失效故障数据和预测失效故障数据，ntest表示样本故障数据集中划分的测试数据集的大小，MSE值越小，模型的拟合性能和预测性能越好。这里需要指出的是，上述性能评价标准仅用于比较不同模型对同一数据集的应用。传统非参数化SRGM和BT-SRGM算法的相应误差表示为MSEst和MSEbt。将MSE之间的相对差值定义为RAMSE，公式为

(15)

4.2 数据处理

使用三个公开发表且已经被广泛接受的软件失效故障数据集进行实验，将每个数据集分为两个子集(训练集=80%，测试集=20%)，第一个子集(后文图中虚线左边部分)用于拟合训练模型，第二个子集(虚线右边部分)用于验证模型的预测能力。

第一组故障数据集(DS1)来自NTDS[10]，包含34个故障数据集，如图2所示。对于大多数调试时间数据并不表示可靠性增长，甚至可以观察到可靠性略微有所降低，在调试的后期阶段，数据才显示可靠性增长，数据显示出非常大的异方差性，当时用成对比较的权重集时可以更好地拟合故障结果，图3表明MSE对参数ε的依赖性，当ε=0.5时，MSE的差值最大，最大的RAMSE为15.2%，因此BT-SRGM的性能明显优于传统非参数化SRGM。

图2 两种SRGM故障预测结果 图3 MSE对参数ε的依赖性

第二组故障数据集(DS2)来自IBM开发的入门软件数据包[11]。该数据集包含15个观测值。结果如图4所示。图5表明MSE对参数ε的依赖性，当ε=0.4时，MSE的差值最大，最大的RAMSE为15.2%，虽然只是一个小数据集，但有明显的可靠性增长。

图4 两种SRGM故障预测结果 图5 MSE对参数ε的依赖性

第三组故障数据集(DS3)是使用直升机主旋翼叶片部件代码的数据，基于1995年10月至1999年9月收集的系统数据库[10]。该数据集包含52个观测值，如图6所示。通过观察发现失败次数的变化相当大。而且，可靠性增长几乎是没有增长的。由于训练数据集很大，两个模型(传统非参数化SRGM和BT-SRGM)的预测结果很接近。但观察图7，表明MSE对参数ε的依赖性，当ε=0.5时，MSE的差值最大，最大RAMSE为15.6%，因此与传统非参数化SRGM相比，BT-SRGM提供了相当大的改进。

图6 两种SRGM故障预测结果 图7 MSE对参数ε的依赖性

5 结 语

本文提出了一种新的非参数化的软件可靠性增长模型(BT-SRGM)，它可以看作是传统非参化模型的改进。通过三组被广泛应用的失效故障数据集(DS1、DS2和DS3)将所提出的BT-SRGM与现有的传统非参数化模型做了比较，实验结果显示了BT-SRGM的性能明显优于传统SRGM。该领域的研究仍处于初级阶段，未来我们将尝试将该方法扩展到传统的基于泊松过程的软件可靠性增长模型，用以改善NHPP类软件可靠性增长模型的预测精度和通用性。