数据驱动的软件可靠性模型研究

1、数据驱动的软件可靠性模型研究杨波，黄洪钟，郭夙昌电子科技大学机械电子工程学院，四川成都(610054)E-mail：摘 要：传统的软件可靠性增长模型通常基于一系列不符合实际情况的假设，因而其适用性和准确性受到了较大的影响。近年来，数据驱动的软件可靠性建模方法受到了广泛的重视，一些文献提出了基于人工神经网络和基于支持向量机的软件可靠性模型。由于数据驱动的软件可靠性模型不对软件的内部错误及失效过程做任何假设，因而其适用范围较传统的软件可靠性增长模型更广。对于数据驱动的软件可靠性模型，其使用的软件失效数据对模型的预测精度有很大的影响，但现有的文献未对此进行研究。本文提出了一种基于支持向量机的软件可靠

2、性模型，并指出对数据驱动的软件可靠性模型，应使用累计失效数据而不应使用失效间隔数据；应使用最近的部分失效数据而不应使用所有观测到的失效数据。本文同时还提出了一种基于遗传算法的模型参数优化方法。应用三组现有文献中的实际软件测试数据，对所提出的软件可靠性模型与现有的数据驱动的软件可靠性模型进行了对比研究。结果表明，本文所提出的软件可靠性模型具有较好的预测精度。关键词：软件可靠性；失效数据分析；支持向量机；人工神经网络；失效预测中图分类号：TP311.5 文献标识码：A 文章编号： 16737180（2007）100. 引言当今世界计算机被广泛地应用于各个领域，包括科学计算、工业控制、电子商务、医疗

3、设备、家用电器、游戏娱乐等。随着计算机系统在生产、生活中的高度渗透，其可靠性问题变得日益突出。对于某些系统，如飞行控制系统、医疗设备、银行或股票交易系统等，可靠性更是系统设计时的首要考虑因素，系统一旦失效，将会带来巨大的经济损失和人员伤亡。但是据统计，在目前已有记录的系统失效事故中，由于软件的失效而造成的事故占绝大多数1。著名的例子如1996年欧洲航天局首次发射阿丽亚娜5号火箭失败以及危及全球的“千年虫”事件等。计算机系统中软件的可靠性保障已成为学术界和工业界高度关注的一个问题，并且也是制约计算机系统进一步发展的一个瓶颈。从20世纪70年代开始，人们在软件可靠性的建模、分析、评估、预测等方面开

4、展了大量的研究，提出了各种软件可靠性模型 (Software Reliability Models, SRMs)14。软件可靠性模型大体上可分为两类5,6：解析模型 (Analytical Model) 和数据驱动的模型 (Data-driven Model)。解析模型即为传统的软件可靠性增长模型 (Software Reliability Growth Model, SRGM)，包括非齐次泊松过程模型、马尔可夫模型等。这类模型需要对软件内部错误及失效过程的特性做出很多假设，然后采用某种随机过程对其进行描述。例如Geol-Okumoto模型34假设软件失效过程是一个非齐次泊松过程，并且每观察到

5、一次软件失效，其对应的软件内部错误可以被准确地排除。Jelinski-Moranda模型34则假设软件失效过程是一个马尔可夫过程，并且每个软件内部错误对软件失效率的贡献是相同的。各种解析模型所做的假设不尽相同，但这些假设都或多或少地与软件失效过程的实际情况有所不符。因此，解析模型的适用性和准确性受到了较大的影响；并且在实际的工程应用中，模型的选择是比较困难的。针对解析模型的不足，近年来数据驱动的软件可靠性建模方法受到了越来越多的重视，一些专家学者业已提出了一些数据驱动的软件可靠性模型。这类模型通常不需要1本课题得到国家自然科学基金 (60672165)，教育部高等学校博士学科点专项科研基金 (

6、20060614016)，高等学校全国优秀博士学位论文作者专项基金 (200232)的资助。-1-对软件的失效过程做任何假设，而只是基于观测到的软件失效数据，将其视为一个时间序列进行建模与分析，并对软件将来的失效行为进行预测。由于数据驱动的软件可靠性模型不对软件内部错误及失效过程做任何不符合实际的假设，因而其适用范围较传统的解析模型更广，并且不存在实际应用中的模型选择问题56。数据驱动的软件可靠性模型包括基于时间序列分析的模型78x1x2xix2x3(a)xi、基于人工神经网络的模型和基于支持向量机 (Support Vector Machine) 的模型等。人工神经网络具有自组织、自适应、自

7、学习等特点，并且能充分逼近任意复杂的非线性关系，因而在模式识别、信号处理、自动控制、知识工程等方面得到了广泛的应用。在软件可靠性建模领域，也有学者提出了基于人工神经网络的软件可靠性模型5,6,913xi(b)i+1x图1 基于人工神经网络和基于支持向量机的软件可靠性模型的基本框架Fig.1 Framework of SVM-based and ANN-basedSRMs在运用这类模型进行软件可靠性预测时，分两个步骤进行：1) 模型训练。若目前共观测到i个软件失效数据，即x1, x2, xi，则以x1,x2, xi1作为模型的输入、以xi作为模型。但是，人工神经网络也具有一些内在的缺点，如数据过

8、拟合 (over-fitting) 以及学习算法的效率不高等问题。支持向量机1416是在统计学习理论基础上发展起来的一种新的机器学习方法。支持向量机又称为支持向量网络，具有理论完备、适应性强、全局优化、训练时间短、泛化性能好等优点。支持向量机已在数据分类、回归估计、函数逼近等领域得到了成功的应用。在软件可靠性建模领域，也有学者做了有益的尝试1718。基于人工神经网络和基于支持向量机的软件可靠性模型的基本框架如图1所示。的期望输出，对模型进行训练，确定模型中的参数。如图1 (a) 所示。2) 预测。在模型的参数确定以后，以x2, x3, xi作为模型的输入，对软件的下如图1 (b) 所一个失效点

9、xi+1的值进行预测。示。随着软件测试的进行，当有新的软件失效数据被记录时，需要重新构建模型并对模型进行训练，然后再对将来的软件失效进行预测。例如，当记录到第i+1个软件失效数据时，则以x1, x2, xi作为模型的输入、以xi+1作为模型的期望输出对模型进行训练，然后用训练好的模型对下一个失效点xi+2的值进行预测。如此反复进行下去。可以看出，这类软件可靠性模型不对软件的失效过程做任何假设，而是基于观测到的软件失效数据，通过模型的训练将软件失效过程的内在规律学习到模型中17，然后模型根据该规律对下一次软件失效做出预测。因此，基于人工神经网络和基于支持向量机的软件可靠性模型都属于数据驱动的软件

10、-2-可靠性模型。由于软件失效过程的内在规律是通过对失效数据的学习而固化入模型中的，因此失效数据的选择对模型的预测精度有很大影响。软件的失效数据可分为“累计失效数据”和“失效间隔数据”两种。累计失效数据如软件失效时间Ti (i=1,2,"，定义T0=0)、到指定时刻为止总共观测到的软件失效数等；失效间隔数据如软件失效时间间隔i (第i次和第i-1次软件失效之间的时间间隔，i=1,2,") 等。如图2所示。Vapnik14提出了一种回归函数，通过对一组训练数据的学习，该函数可以反映出一个系统或过程的输入量与输出量之间的映射关系。训练样本集为(xi,yi)li=1，其中xi为输

11、入量，yi为输出量 (期望输出)，l为样本数。用于回归估计的支持向量机可表示为：f(x)=(x)+b (3)该函数将输入样式中(x)为内积函数，本空间映射到高维线性特征空间；和b为常数。支持向量机采用结构风险最小化原理 (Structural Risk Minimization Principle)，和b的值可以通过最小化以下的结构风险函数得到：1C2R=+2ll图2 软件失效时间和软件失效时间间隔Fig.2 Software failure times and inter-failure times|yi=1if(xi)|(4)式中，C为常数，|yif(xi)|为损失函数：0(|yif(xi

12、)|)|yif(xi)|=yfxyfx|()|(|()|>)iiii累计失效数据和失效间隔数据可以相互转换：i=TiTi1 (i=1,2,") (1)Ti=j (i=1,2,") (2)j=1i式(4)的拉格朗日对偶式为：L(i,)=yi(i)(i+i*)*i*ii=1i=1ll对任何一个数据驱动的软件可靠性模型，在使用失效数据时都需要考虑以下两个问题：1. 使用所有已观测到的软件失效数据，还是只使用最近的部分失效数据？2. 使用累计失效数据，还是使用失效间隔数据？现有文献中发表的数据驱动的软件可靠性模型，有的使用累计失效数据5,6,17，有的则使用失效间隔数据18。

13、此外，有的模型使用所有已观测到失效数据17，有的则使用最近的部分失效数据。而对使用某种失效数据的具体原因及其对模型预测精度的影响，现有的文献均未进行研究。本文提出一种基于支持向量机的软件可靠性模型，并对以上提出的模型使用失效数据的两个问题进行深入的研究。1ll(5) (ii*)(j*j)K(xi,xj)2i=1j=1其约束条件为：(i=1lii*)=00i,i*C (i=1,2,",l)式(5)中K(xi,xj)为核函数 (KernelFunction)，通常采用多项式或高斯核函数。i和i*为拉格朗日乘子，它们满足ii*=0 (i=1,2,",l)。i和i*的值可以通过式(

14、5)得到。i和i*的值被确定之后，回归函数(3)变为：f(x)=(ii*)K(xi,xj)+b (6)i=1l由式(6)可知，尽管通过非线性函数将样本数据映射到具有高维甚至为无穷维的特-3-1. 支持向量机简介征空间，但在计算时并不需要显式地求解该非线性函数，而只须要确定核函数，从而避免了高维特征空间引起的维数灾难问题。由于篇幅限制，本节只对支持向量机做了简要的介绍。读者可参阅文献1416以对支持向量机进行更深入的了解。所提出的软件可靠性模型中，采用高斯核函数，即：(xixj)2K(xi,xj)=exp (7) 2在基于支持向量机的可靠性模型中1719有3个参数的值需要确定，即C，22. 一种

15、基于支持向量机的软件可靠性模型本文提出了一种基于支持向量机的软件可靠性模型，如图3所示。对比图1和图3可以看出，该模型的基本框架与现有的数据驱动的软件可靠性模型的基本框架是类似的，但是该模型具有以下两个特点：和，见式(4) 和 (7)。这些参数的取值对模型的预测精度有很大影响，因此需要采用优化算法来确定它们的最优值。文献18和19分别采用模拟退火算法和遗传算法来确定这三个参数的最优值。在本文所提出的模型中，除了这三个参数以外，还有一个参数，即w的值需要确定。我们采用如图4所示优化算法来确定这四个参数的最优值。这是一个双重循环算法，其中外循环对w所有可能的取值进行遍历；而内循环用遗传算法来确定在

16、w取某个值时的最优C，2和值；该遗传算法与文献19中的算法是相同的。最后，我们选择具有最小训练平方误差的w值及其对应的最优C，1) 在模型的训练过程中并不采用所有记录的软件失效数据，而是只采用最近的w+1个失效数据 (w=1,2,"i1)，如图3 (a) 所示。同样，在用训练后的模型进行预测时，也只用最近的w个数据作为模型的输入，对下一个软件失效点的值进行预测，如图3 (b) 所示。可以看出，如果取w=i1，则表示使用所有的软件失效数据，即退化为图1所示的模型。2和值作为模型的参数值。在以上的参数优化过程中，训练平方误差 (Squared Error, SE) 的定义如下：若已观测到

17、i个软件失效数据，即x1, x2, xi，则：i)2 (8) SE=(xix2) 该模型所使用的软件失效数据为累计失效数据，而不是失效间隔数据。需要指出的是，图4所示的算法对w值的优化过程实际上是一个全值搜索的过程，因而算法的计算量较大。但是由于一般情况下观测到的软件失效数据的数目是有限的(通常为100个以内)，因此该算法在实际中还是可行的。图3 一种基于支持向量机的软件可靠性模型 Fig. 3 An SVM-based software reliability model一般而言，在支持向量机中采用高斯核因此在本文函数会带来较高的预测精度19，-4-在本节中，我们将本文所提出的软件可靠性模型

18、应用于三组实际软件开发项目的测试数据上，并对该模型与现有的数据驱动的软件可靠性模型的预测精度进行比较研究。定义模型的预测均方误差 (Mean Squared Error, MSE) 如下：1MSE=nij=i+1(xnjj)2x (9)MSE表示在观测到n个失效数据时，用前i个数据模型进行训练，然后用训练好的模型对第i+1个到第n个失效数据进行预测，预测值与真实值差的均方值。该值越小，说明模型的预测精度越高。3.1 参数w的取值我们首先研究引言中提出的第一个问题，即在数据驱动的软件可靠性模型中，应该使用所有已观测到的软件失效数据，还是只使用最近的部分失效数据？这个问题可以归结为参数w的最佳取值

19、。实例1. 在本实例中，我们采用文献5发表的一组软件测试数据。该数据来自于一个实际软件开发项目，包括28个星期的测试数据，数据形式为到每个星期为止观测到的累计软件失效数。我们对三种数据驱动的软件可靠性模型进行研究，分别是：基于人工神经网络的软件可靠性模型5 (称为模型A)、基于支持向量机的软件可靠性模型17 (称为模型B)、本文所提出的软件可靠性模型 (称为模型C)。模型A和模型B均使用所有已观测到的软件失效数据，而模型C仅使用最近的部分软件失效数据。分别计算这三种软件可靠性模型对第628个星期的累计软件失效数的预测均方误差，其结果如表1所示。可以看出，模型 C的预测均方误差是最小的。 图4

20、模型参数优化算法流程图Fig. 4 Flow chart of the optimization algorithm formodel parameters3. 实例研究-5-表1 基于文献5发表的测试数据的研究 Table 1. Empirical Study Based on Software FailureData in 5模型A 模型B模型C预测均方误差 (第628个星期)66.92 50.95 36.52据。本文所提出的软件可靠性模型正是采用了这种方式。3.2 失效数据类型在本节中，我们研究引言中提出的第二个问题，即在数据驱动的软件可靠性模型中，应该使用累计失效数据，还是使用失效间隔

21、数据？我们通过以下的实例来对此进行研究。实例3. 在本实例中，我们采用文献18发表的一组软件测试数据。该数据来自于贝尔实验室的一个网络遥测系统，包括22个软件失效间隔时间，如图5 (a) 所示。文献实例2. 在本实例中，我们采用文献20发表的一组软件测试数据，该数据来自于一个实际软件开发项目，包括19个星期的测试数据，数据形式为到每个星期为止观测到的累计软件失效数。我们同样将以上三种数据驱动的软件可靠性模型应用于这组数据上，得到的模型预测均方误差如表2所示。可以看出，模型C的预测均方误差仍然是最小的。18提出了一种基于支持向量机的软件可靠性模型 (称为模型D)，采用软件失效间隔时间作为模型使用

22、的数据。文献18使用前18个观测到的软件失效间隔时间对模型进行训练，然后用训练后的模型对第1922个软件失效间隔时间进行预测。我们将本文所提出的软件可靠性模型应用于该组数据上。由于我们使用的是累计失效数据，因此首先通过式 (2) 将失效数据进行了转换。转换后的软件失效数据如图5表2 基于文献20发表的测试数据的研究 Table 2. Empirical Study Based on SoftwareFailure Data in 20模型A 模型B模型C预测均方误差 (第519个星期)10.73 21.72 7.35根据实例1和实例2的研究结果，我们认为，在数据驱动的软件可靠性模型中，应该使用

23、最近的部分失效数据，而不应使用全部的失效数据，否则模型的预测精度会受到影响。具体使用多少个最近失效数据，即w的取值，可以用图4所示的算法得出。该结论是符合软件工程的实际情况的。通常在软件的测试过程中，由于测试人员的熟练程度变化、中途更换测试人员等因素的影响，软件失效过程的特性不是平稳的，而是随时间变化的。早期的软件失效数据反映的是软件失效过程的早期特性；只有近期的软件失效数据才反映的是软件失效过程的近期特性以及发展趋势。如果使用早期的软件失效数据，则使得软件可靠性模型被迫去适应软件失效过程的早期特性，反而会影响模型对软件失效过程的近期特性及发展趋势的学习，从而降低模型对将来软件失效行为的预测精

24、度。因此，在数据驱动的软件可靠性模型中，应该只使用最近的部分失效数-6-(b) 所示。我们分别计算了这两种软件可靠性模型对第1922个失效点的预测均方误差，其结果如表3所示。可以看出，本文所提出的软件可靠性模型的预测均方误差较小。因此我们认为，在数据驱动的软件可靠性模型中，应该使用累计失效数据，而不应使用失效间隔数据，否则模型的预测精度会受到影响。该结论也是符合软件工程的实际情况的。众所周知，软件失效间隔数据 (如失效间隔时间) 具有很大的不稳定性，通常会发生一个数据与前一个数据差别很大的情况，即数据存在多处突变，如图5 (a) 所示的数据。对这样的数据，无论是人工神经网络还是支持向量机，都是

25、很难拟合的。而软件累计失效数据很少发生突变的情况，其增长模式相对稳定，如图5 (b) 所示的数据，因此人工神经网络和支持向量机能够更好地对其拟合，从而使模型具有较高的预测精度。表3 基于文献18发表的测试数据的研究 Table 3. Empirical Study Based on SoftwareFailure Data in 18 模型C 模型D 预测均方误差 (第1922个失效点)预测精度。实例研究所得出的结论对软件可靠性的建模与预测具有一定的指导意义。在以后的工作中，我们将研究进一步提高数据驱动的软件可靠性模型预测精度的方法。例如，是否可以不采用最近的w+1个失效数据，而是采用某几个观

26、测到的软件研究结果表明，这种方法对提高模型的预测1644.05 762.39 失效数据来对模型进行训练？我们的初步精度是可行的。参考文献1 Lyu M R (ed.) Handbook of Software Reliability Engineering M. New York: McGraw-Hill, 1996. 2 Musa J D, Iannino A, Okumoto K. Software Reliability: Measurement, Prediction, Application M. New York: McGraw-Hill, 1987. 3 Xie M. Softw

27、are Reliability Modeling M. Singapore: World Scientific Publisher, 1991. 4 Pham H. Software Reliability M. Singapore: Springer-Verlag, 2000. 5 Hu Q P, Dai Y S, Xie M, et al. Early software reliability prediction with extended ANN model A. Proceedings of the 30th Annual International Computer Softwar

28、e and Applications Conference C. IEEE Computer Society Press, 2006,2: 234239. 6 Hu Q P, Xie M, Ng S H, et al. Robust recurrent neural network modeling for software fault detection and correction prediction J. Reliability Engineering and System Safety, 2007, 92(3): 332340. 7 Burtschy B, Albeanu G, Bo

29、ros D N, et al. Improving software reliability forecasting J. Microelectronics and Reliability, 1997, 37(6): 901907. 8 Guo J, Liu, H, Yang, X, et al. A software reliability time series growth model with Kalman filter J. WSEAS Transactions on Computers, 2006, 5(1): 17. 9 Khoshgoftaar T M, Szabo R M.

30、Using neural networks to predict software faults during testing J. IEEE Transactions on Reliability, 1996, 45(3): 456462.10 Sitte R. Comparison of software-reliability- growth predictions: neural networks vs. parametric-recalibration J. IEEE Transactions on Reliability, 1999, 48(3): 285291.11 Cai K

31、Y, Cai L, Wang W D, et al. On the neural network approach in software reliability modeling J. Journal of Systems and Software, 2001, 58(1): 4762.12 Ho S L, Xie M, Goh T N. A study of the connectionist models for software reliability prediction J. Computer and Mathematics with Applications, 2003, 46(

32、7): 10371045.i5101520(a)i5101520(b)图5 软件失效数据(a) 失效间隔时间18 (b) 失效时间Fig. 4 Software failure data(a) Inter-failure times18 (b) Failure times4. 结论本文提出了一种基于支持向量机的软件可靠性模型。该模型使用累计失效数据而不是失效间隔数据；并且仅使用最近的部分失效数据而不是使用所有观测到的失效数据。本文还提出了一种基于遗传算法的模型参数优化方法。通过三个实例研究，结果表明本文所提出软件可靠性模型具有较好的-7-13 Tian L, Noore A. Evolutio

33、nary neural network modeling for software cumulative failure time prediction J. Reliability Engineering and System Safety, 2005, 87(1): 4551.14 Vapnik V. The Nature of Statistical Learning Theory M. New York: Springer-Verlag, 1995.15 Cristianini N, Shawe-Taylor, J. An Introduction to Support Vector

34、Machines and Other Kernel-Based Learning Methods M. London: Cambridge University Press, 2000.16 邓乃扬, 田英杰. 数据挖掘中的新方法: 支持向量机 M. 北京: 科学出版社, 2004.17 Tian L, Noore A. Dynamic software reliability prediction: an approach based on support vector machines J. International Journal of Reliability,Quality and

35、Safety Engineering, 2005, 12(4): 309321.18 Pai P F, Hong W C. Software reliability forecasting by support vector machines with simulated annealing algorithms J. Journal of Systems and Software, 2006, 79(6): 747755.19 Chen K Y. Forecasting systems reliability based on support vector regression with g

36、enetic algorithms J. Reliability Engineering and System Safety, 2007, 92(4): 423432.20 Wood A. Predicting software reliability J. Computer, 1996, 29(11): 6977.Research on data-driven software reliability modelsYang Bo, Huang Hongzhong, Guo SuchangSchool of Mechatronics Engineering, University of Ele

37、ctronic Science and Technology of China,Chengdu (610054)AbstractTraditional software reliability growth models (SRGMs) are generally based on several impractical assumptions, which to a large extend limits their applicability and accuracy. In recent years, data-driven approach to software reliability modeling has attracted a lot of attention, and several artificial neural