软件失效时序数据的灰色拟合及多步预测算法

摘要： 关键词： 中图分类号： 文献标志码： A文章编号： 2095-2163

Abstract： For the reliability model of the software system， its main function is to accurately predict the occurrence of a subsequent software failure time. The paper studies grey fitting problem of the software failure time series data， and proposes the corresponding multistep prediction algorithm. First of all， based on the condition of a fitting accuracy， apply grey theory GM （1， 1） model for the software failure time series data to establish the corresponding piecewise fitting model； then， use the orthogonal polynomial function to estimate fitting residual error at the end of the sequence， and utilize the estimate result for correcting and compensating grey prediction model at the end of the sequence； in the end， apply the combined forecasting model based on compensation to realize multistep projections for the occurrence of software failure time. The experiment verifies the correctness and effectiveness of the algorithm.

0引言

在軟件可靠性的分析与建模过程中，其首要任务就是建立一个精确易用的预测模型，以便对软件系统的各种可靠状况做出精确的预测。根据预测目标的不同，软件可靠性的预测模型通常可以分为两种：静态模型和动态模型。其中，静态模型主要是利用软件系统的各种复杂性参数来预测该软件所隐藏的缺陷总数；而动态模型则是基于软件测试过程中所获得的失效时序数据，借助数理统计的方法来预测下一次软件失效的发生时间[1-3]。由于软件失效时序数据较为容易获取，故动态模型在实际应用中得到了更为广泛的应用。

目前，软件可靠性的动态模型按其使用的建模方法划分，又可分为统计分析方法和时序数据辨识方法两大类[4-5]。其中，统计分析方法是在假设某些条件成立的情况下，应用特定的函数分布来描述软件失效时间的发生过程。以基于非齐次泊松过程（non-homogeneous poisson process， NHPP）的预测方法为例，由于该类方法具有预测精度高且结构简单的优点，故其成为软件可靠性的经典统计分析方法[6-8]。相对地，时序数据辨识方法则无需指定任何先决条件的假设，而是利用软件失效时序数据的前后相依关系，直接将时序数据辨识方法应用于建模研究中。例如，马飒飒等通过对软件失效时序数据设计提出多尺度分解，并对分解后所得到的不同数据成分进行单独的建模，进而得到了一种适应性较好的软件可靠性预测模型[9]；贾治宇等基于非平稳时序数据辨识方法，运用自回归积分滑动平均模型 （auto-regressive integrated moving average model， ARIMA）对软件失效时序数据进行建模，从而得到了一种简捷易用的软件可靠性预测模型[10]。此外，由于时序数据辨识方法在建模过程中能较好地关注了数据的动态特性，故在辨识精度上较统计分析方法更具有优势。

在实际应用中，用户往往需要预测下一次、甚至后续多次的软件失效的发生时间，即需要进行多步预测。据此，本文拟基于分段的灰色预测模型，设计实现一种具有误差补偿机制的软件失效序列的多步预测算法，并在软件可靠性评测领域的公开数据集中验证算法的正确性和有效性。

1问题描述

软件失效时序数据是指软件系统在规定的环境中其各次无失效运行的持续时间，以数学的形式进行描述，有：Y=Yt， t∈N+（1）其中，Yt为一随机变量，用于记录软件的各次无失效运行的持续时间，t为正整数。

基于一定的样本数量n，便可以通过最小二乘或极大似然等方法估算出式（3）中的各有关待定参数，在此基础上，令t=n+1，n+2，…，并代入式（3）和式（2）进行计算，便可以预测出该软件系统的下一次及后续多次的无失效运行的持续时间。然而，随着预测步数的增加，上述预测模型的预测结果将严重地偏离真实值，究其原因有：式（3）中的各有关待定参数虽然能使已有样本的拟合误差为最小值，但过多的外延预测造成了预测精度无法保证；另一方面，随机噪声项的估计值从第二步开始也引用了部分的预测值，此时，固有的误差累积效应也加剧了整体预测性能迅速变差。

2灰色分段拟合及多步预测算法的设计

针对上述问题，本文拟设计一种具有误差补偿机制的软件失效时序数据的多步预测算法。算法的主要思想是，基于灰色理论的GM（1，1）模型为软件失效时序数据Yt建立合适的分段拟合模型，并对末段子序列的拟合误差施行正交多项式函数的预测和补偿，在此基础上，对软件失效发生时间进行多步预测。

2.1基于GM（1，1）模型的时序数据的分段拟合endprint

2.2基于正交多项式的拟合误差的补偿

如前所述，基于GM（1，1）模型将可以把软件失效时序数据划分为数段子序列，易知，对后续的软件失效发生时间的预测应在末段子序列中设计展开。为进一步提高预测精度，这里将应用正交多项式函数来估算末段子序列其GM（1，1）模型的拟合残差，在此基础上，对原GM（1，1）模型进行补偿，进而构建具有误差补偿机制的组合预测模型。

若软件失效时序数据被划分为m段子序列，令末段子序列（设该子序列的长度为v）其GM（1，1）模型的拟合残差序列为em，则有：emt=ymt-y^mt t=1， 2， …， v（12）由于在高次多项式的曲线拟合过程中，往往会遇到病态方程组的求解问题，据此，这里将基于正交多项式对上述的残差序列emt进行拟合。

2.3算法的设计

研究至此， 可设计得到如下的软件失效时序数据的多步预测算法。算法的步骤内容表述如下。

算法名称：软件失效时序数据的多步预测算法

输入：长度为n的时序数据Yt，平均绝对百分误差MAPE的阈值ε，各分段子序列的最小样本长度Δ，预测步数step；

输出：软件失效序列的各step步的预测值。

步骤1从Yt的最左端选取Δ个右邻样本数据构成Ysubt子序列，p=Δ；

步骤2利用式（6）对Ysubt进行一次累加生成处理得到y（1）subt，将y（1）subt代入式（9）求出待估参数a，b，将a，b代入式（5）得到y^（1）subt，利用式（10）对y^（1）subt进行一次逆累加生成处理得到y^subt；

步骤3利用式（11）计算y^subt的平均绝对百分误差MAPE，若MAPE≤ε成立，转步骤4；否则，转步骤5；

步骤4P=P+1，若P≤n，向Ysubt中添加一个右邻样本数据，转步骤2；否则，转步骤6；

步骤5保存分界点P并清空Ysubt， p=p+Δ，若P≤n，以P为起点选取Δ个右邻样本数据构成新的Ysubt子序列，转步骤2；否则，转步骤6；

步骤6以新近的P值为分界点，输出末段软件失效子序列ymt，基于式（15）～（16）的正交多项式迭代法计算ymt的残差序列emt的估计值，并得到e^mt；

步骤7用补偿后的组合预测模型（ymt+e^mt）输出step个后续的软件失效的发生时间，算法结束。

3实验及结果分析

为了验证本文算法的正确性及有效性，这里将选取国际知名软件可靠性工程学者 Lyu发布的失效数据集SYS2.DAT为基础来参与研发相关的多步预测实验。实验在PC机上设计发生，其硬件配置为：Intel 酷睿i5 4570四核CPU、Kingmax DDR3 16 GB RAM、Western Digital 500 G Hard Disk；操作系统与开发环境为，Microsoft Windows 10、Microsoft Visual Studio 2010集成开发环境中的C++。在实验过程中，着重围绕现有算法与本文算法在多步预测时的辨识误差和计算开销等性能指标，并对相关结果提供了详尽的讨论与分析。

3.1实验过程与方法

失效数据集SYS2.DAT中共有86个样本序列，在实验过程中，取失效数据集的前80个序列进行建模，并用建模所得的预测模型对后续的六个序列进行预测。实验中需要进行对比的算法有：文献[9]算法、文献[10]算法及本文算法。

从图1的拟合误差曲线可知，在对已知样本序列的建模过程中，文献[9]算法的拟合精度是最高的，本文算法次之，而文献[10]算法则位列第三，上述各种算法的平均绝对百分误差MAPE均在10%以内，故都属于高精度拟合。而从图2的多步预测误差曲线易知，上述各种算法对第一步的预测精度是基本相同的，但从预测的第二步起，文献[9]和文献[10]算法的预测精度均出现了明显的振荡，且振荡现象随着预测步数的增加而加剧，当中，又以文献[10]算法的振荡现象更为显著；与之形成对比的是，本文算法其多步预测的误差曲线仅在零值上做非常微弱（MAPE≤9.46%）的波动。事实上，文献[9]和文献[10]算法在建模过程中，各自得到的预测模型只保证了在已知样本序列范围内其拟合误差是最小的，但没有对外延预测进行任何的处理；而本文算法首先基于某一精度的条件下，通过灰色GM（1，1）模型对已有样本序列进行分段拟合，目的就是避免预测模型出现数据饱和的情况，在此基础上，引入正交多项式对末段GM（1，1）模型的拟合误差进行估计和补偿，这样，补偿后的预测模型对外延预测的误差趋势便能及时加以修正，从而使得本文算法的多步预测能力具有一定的鲁棒性。

算法类型计算耗时/ms建立预测模型的耗时多步预测的平均耗时本文算法188.745.98文献[9]算法367.569.32文献[10]算法102.333.15在实验过程中，文献[9]算法的建模流程是最为复杂的，该算法首先是引用小波方法对已有序列来进行多尺度分解，然后分别用AR模型和RBF神经网络对分解出的各种数据进行参数估计，所以其计算耗时远多于参加对比试验的其他两种算法。对于本文算法而言，其计算用时则主要是消耗在灰色子序列的划分过程中，（1-AGO）、矩阵求逆及（1-IAGO）等运算过程占用了本文算法较多的计算时间。相对地，文献[10]算法在经过若干次差分運算后，直接对近似的平稳时序数据进行自回归滑动平均模型（auto-regressive moving average model， ARMA） 的参数估计，故其花费的计算耗时是最小的。此外，表2中的多步预测的平均耗时是指，进行1～6步预测时所花费计算时间的平均值，根据各种算法所得的预测模型其复杂程度的不同，这里，多步预测的平均耗时与建立预测模型的耗时有着正比例的关系。endprint

综上所述，本文算法在花费少量的额外计算耗时后，即已获得了良好的多步预测能力，据此可证，本文算法是正确和有效的。

4结束语

对于某一预测模型而言，多步预测的鲁棒性能表征了该模型是否具有良好的外延预测能力。本次研究提出了一种改进的鲁棒多步预测算法，改进算法的有效性在权威的软件失效数据集中得到了验证。后续面临的主要工作有，提升现有的灰色系统GM（1，1）模型的拟合精度，同时，也需要探讨更为高效的矩阵快速求逆方法，以便进一步提升算法的预测精度和计算效能。

参考文献：

[1] 徐仁佐，谢曼，郑人杰. 软件可靠性模型及应用[M]. 北京：清华大学出版社，1994.

[2] 赵靖. 软件可靠性模型及应用[M]. 哈尔滨： 哈尔滨工程大学出版社，2007.

[3] 郭平. 软件可靠性工程中的计算智能方法[M]. 北京： 科学出版社，2012.

[4] 楼俊钢，江建慧，帅春燕，等. 软件可靠性模型研究进展[J]. 计算机科学，2010，37（9）：13-19，27.

[5] 耿技，聂鹏，秦志光. 软件可靠性模型现状与研究[J]. 电子科技大学学报，2013，42（4）：565-570.

[6] 张宁红. NHPP类软件可靠性增长模型的统一及其性能分析[J]. 系统工程与电子技术，1999，21（8）：74-77.

[7] 何焱，张来顺，刘伟，等. 一种基于离散时间的NHPP软件可靠性增长模型[J]. 计算机应用研究，2011，28（7）：2569-2572.

[8]ZHANG Jie，LU Yang， YANG Shu， et al. NHPPbased software reliability model considering testing effort and multivariate fault detection rate[J]. Journal of Systems Engineering and Electronics， 2016，27（1）： 260-270.

[9] 马飒飒，王光平，赵守伟. 基于时间序列的软件可靠性预测模型研究[J]. 计算机工程与设计，2007，28（11）：2520-2523.

[10]贾治宇，康锐. 软件可靠性预测的ARIMA方法研究[J]. 计算机工程与应用，2008，44（35）：17-19.

[11]何书元. 应用时间序列分析[M]. 北京： 北京大学出版社，2003.

[12]黄雄波. 多周期时序数据的傅氏级数拟合算法[J]. 计算机系统应用，2015，24（7）：142-148.

[13]黄雄波. 基于自相关函数的非平稳时序数据的辨识改进[J]. 微型机与应用，2016，35（13）：10-14，18.

[14]刘思峰，杨英杰. 灰色系统研究进展（2004-2014）[J]. 南京航空航天大学学报，2015，47（1）：1-18.

[15]党耀国，王俊杰，康文芳. 灰色预测技术研究进展综述[J]. 上海电机学院学报，2015，18（1）：1-7，18.

[16]鄭咸义，姚仰新，雷秀仁，等. 应用数值分析[M].广州： 华南理工大学出版社，2008.

[17]李庆扬，关治，白峰彬.数值计算原理[M]. 北京： 清华大学出版社，2005.endprint