LIU Xiaomei and XIE Naiming

1.College of Economics and Management,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China;2.College of Science,Jiujiang University,Jiujiang 332005,China

Abstract: Due to the randomness and time dependence of the factors affecting software reliability,most software reliability models are treated as stochastic processes,and the non-homogeneous Poisson process (NHPP) is the most used one.However,the failure behavior of software does not follow the NHPP in a statistically rigorous manner,and the pure random method might be not enough to describe the software failure behavior.To solve these problems,this paper proposes a new integrated approach that combines stochastic process and grey system theory to describe the failure behavior of software.A grey NHPP software reliability model is put forward in a discrete form,and a grey-based approach for estimating software reliability under the NHPP is proposed as a nonlinear multi-objective programming problem.Finally,four grey NHPP software reliability models are applied to four real datasets,the dynamic R-square and predictive relative error are calculated.Comparing with the original single NHPP software reliability model,it is found that the modeling using the integrated approach has a higher prediction accuracy of software reliability.Therefore,there is the characteristics of grey uncertain information in the NHPP software reliability models,and exploiting the latent grey uncertain information might lead to more accurate software reliability estimation.

Keywords:software reliability model,stochastic process,uncertainty system,non-homogeneous Poisson process,grey system theory.

1.Introduction

With the rapid development of information technology and the increasing scale of software system,the research of software reliability becomes necessary.Unlike hardware reliability systems,there is no physical mechanism for software failure.The development and design of software are all made by people,software inevitably occurs failure.In order to ensure the quality of the software,large numbers of carefully selected testing cases are used to expose the faults as quickly and effectively as possible.How much testing can make the software achieve acceptable quality depends on the evaluation technology of software reliability.Therefore,it is very important to evaluate software reliability for software engineer.

Software reliability evaluation is usually completed by software reliability modeling,which is to estimate software reliability according to the observed failure data by the statistical method.The research on software reliability modeling started from the Jelinski-Moranda (J-M)model [1].Since the 1970s,software reliability modeling has developed rapidly,and many well-known models of different viewpoints have emerged.Stochastic process is one of the main frameworks for developing software reliability models.Nelson data domain model [2],Musa execution time model [3],and the Goel-Okumoto (G-O) failure counting model [4],were all presented based on the non-homogenous Poisson process (NHPP).Among these models,the G-O model is the most famous model.It assumes that the fault detection rate is a constant and the debugging is perfect.Although this hypothesis deviates from the real testing process greatly,it is an important reference for the follow-up research.Many software reliability models are proposed based on the G-O model by considering various elements that affect software reliability,such as incomplete debugging,fault detection rate,testing-effort,and change point [5?8].Markov processes are also used to software reliability modeling by setting the transition probability between states as the input parameter.Jelinski et al.[9]first used Markov process to software reliability estimation.Kremer [10]studied software reliability as birth and death process.Qu [11]analyzed software reliability in the air traffic control system using Markov processes.Another family of software reliability models is Bayesian model.The first Bayesian inference software reliability model is Littlewood-Verrall model [12].Other different Bayesian inference software reliability models were proposed under different assumptions of prior distribution [13?15].Software reliability models based on time-series forecasting method are also widely studied.Singpurwda [16]first used time series analysis for software reliability estimation.Ho et al.[17]studied reliability prediction of repairable system based on the autoregressive moving average (ARMA) model.Besides,combination models with other methods are presented to improve the prediction.Aly et al.[18]used genetic programming (GP) to build models to predict the number of errors.Jayadeep et al.[19]used a hybrid method composed of auto-regressive integrated moving average (ARIMA) and neural network to predict the software reliability.In recent years,the research on software reliability has developed to machine learning.Karunanithi et al.[20]first used neural network to research software reliability.Now,neural network has been applied in software reliability estimation for nearly 30 years,and numerous different machine learning algorithms have been explored.Qi [21]evaluated software reliability based on the backpropagation neural network.Kiran et al.[22]created a software reliability model from a heterogeneous ensemble of several different neural networks.Roy et al.[23]proposed an artificial neural network for software reliability modeling by a novel particle swarm optimization algorithm.Chaos theory is also used in software reliability modeling.Zou et al.[24]studied three well known software reliability models by extracting a fractal dimension.Shao [25]created a software reliability model to find reliable estimates of chaotic invariants.Yazdanbakhsh et al.[26]employed the nonlinear time series analysis to test for chaotic behavior in software reliability models.

Above reviews show the software reliability research methods are varied,and there has been no consensus on the mechanism of software failure.In general,the software reliability models based on the NHPP are the most widely studied because of the simple mathematical structure and the easily implementation.However,software internal structure is highly complex,and the NHPP software reliability models sometimes occur a serious bias from the actual value.Cai [27?29]has conducted meaningful research on the problems of the NHPP software reliability models.He verified that the software reliability behavior does not follow the NHPP in a statistically rigorous manner and pointed out the modeling framework of software reliability should not only consider the stochastic as a form of uncertainty,but also consider other forms of uncertainty.Thus,he proposed a fuzzy software reliability model by setting software failure time as a fuzzy variable.

The viewpoint of Cai does not adopt any assumptions related to the probability distribution and is to use another uncertainty theory (fuzzy set) instead of randomness to construct the software reliability model framework.Considering that a single uncertain system theory may not be enough to describe the failure behavior of software,it may be better to estimate software reliability with various uncertainty theories at the same time.This paper investigates the characteristics of grey uncertain information in NHPP software reliability models and proposes an integrated approach combining stochastic process and grey system theory to estimate software reliability.

The main work of this paper lies in the following two aspects:

(i) Several grey NHPP software reliability models are proposed;

(ii) A grey-based approach for estimating software reliability under the NHPP is presented.

This paper is organized as follows:Section 2 reviews software reliability estimation methods based on the NHPP.Section 3 introduces grey system theory and the related work on its applications in software reliability estimation.Section 4 proposes several grey NHPP software reliability models.Section 5 presents a grey-based approach for estimating software reliability under the NHPP.Section 6 tests the effectiveness of the grey-based estimating approach under the NHPP through four real datasets.Section 7 makes conclusions.

2.Software reliability estimation based on the NHPP

Software reliability model based on the NHPP describes software failure by a counting process and assumes the occurrence of failures obeys the nonhomogeneous Poisson process.

Denote {N(t),t≥0} as the actual number of failures by timet,a counting process {N(t),t≥0} is called the NHPP if the following assumptions are satisfied [30].

wherem(t) is called the cumulative number of failures and expressed as,λ(t) is the number of failures of unit time att.

According to (iv),the reliability in [t,t+x) can be calculated by

Equation (1) shows the software reliability in specified time can be estimated with the cumulative function of failuresm(t).Therefore,an important step in the NHPP software reliability models is to establish the cumulative function of failuresm(t) by the failure data collected in the testing process.However,the failure data collected is only to represent a sample path,and the differences between different sample paths are significant.We adopt the simulation results of 40 trails of Cai’s two controlled software experiments to describe this phenomenon.The detailed data can be seen in [27].As shown in Fig.1,the sample paths are very close to each other in the early stage,but become more and more dispersed in the later stage.

Fig.1 Analysis of 40 trials from Cai’s control experiments

He et al.[31]has pointed out software reliability can only be evaluated when software producers think software products are stable and mature,that is to say,the real sample paths of software failure are scattered with each other.Besides,the collected failure data is discrete,and the accuracy of extrapolation prediction cannot be guaranteed by pure simulation of failure data by using the continuous functionm(t).Therefore,it may not be able to describe the failure behavior of software only according to the NHPP software reliability model.In view of this,we introduce grey system theory to the NHPP software reliability modeling and not to pursue higher fitting accuracy.We assume software failure approximately follows the NHPP,and want to know whether there is the grey uncertain information in software system reliability.

3.Grey system theory and its related works on software reliability estimation

Grey system theory,like probability statistics,fuzzy mathematics and rough set theory,is an approach for studying uncertain systems.It was first proposed by Chinese scholar Professor Deng [32].Different from other uncertainty theories,grey system theory focuses on the uncertainty problems of small data sets and poor information.One of the main tasks of grey system theory is to uncover the mathematical relationships or the change laws of system variables based on the available data,in which each stochastic variable is regarded as a grey quantity changing within a fixed region or within a certain time frame.

In essence,grey system theory is to seek an organic equilibrium between quantitative predictions and qualitative analyses.The main adopted method is to construct a suitable accumulated operator to preprocess the data to eliminate the influence of data sequence distortion before quantitative modeling analysis.For example,as shown in Fig.2,the original data sequences do not show any definite regularity,and after processing by different accumulated operators,they show different change trend.

Fig.2 Trend analysis of grey accumulated sequences

Up to now,grey system theory has been applied widely and has produced more effectiveness by combining with other approaches [33?36].Meanwhile,grey information modeling is also used to estimate software reliability[37?43].Gao et al.[37]first presented a software reliability model based on the GM(1,1) model of grey system theory.Ye et al.[38]and Mei [39]used Gao’s method to evaluate software reliability.Zhang et al.[40]evaluated software reliability by combing GM(1,1) model and neural network.Zhang et al.[41]proposed a software reliability model by combining support vector regression model and GM(1,1) model.Ma et al.[42]constructed a series of grey Markov chain models by combining GM(1,1) model and Markov chain.Huang [43]studied grey fitting problems of software failure data and proposed the multistep prediction algorithm.These related works show two common points.One is that the adopted technology of grey system theory is only limited to the GM(1,1) model.The other is that the presented combination models are only to modify the residual errors produced by the GM(1,1) model.

However,the analytical solution of GM(1,1) model is the monotonous exponential function,and it cannot simulate the software failure data with obvious nonlinear characteristics.Therefore,to better describe the failure behavior of software,it is necessary to extend the GM(1,1)model based on the characteristics of software failure data.

4.Grey software reliability models based on the NHPP

Due to the discreteness of data and the incompleteness of information,grey system model is established in the form of discrete difference equation representing approximately the continuous model.Therefore,we first proposed several grey software reliability models by discretizing the NHPP models based on the grey modeling mechanism.For illustrations,four traditional NHPP software reliability models are applied here,including the delayed S-shaped model [44],the inflection S-shaped model [45],the Yamada exponential model,and the Yamada Rayleigh model [46].These models are widely used and have a great influence on the development of software reliability research.

4.1 Grey delayed S-shaped software reliability model

The cumulative function of failuresm(t) of the delayed S-shaped software reliability model is expressed as

Its differential equation can be represented as

According to the grey modeling mechanism and using the undetermined grey background value coefficient θ,the discrete delayed S-shaped software reliability model is defined as

Assumem(tk)=nk(k=1,2,···,N),andnkdenotes the actual defects found by timetk,Ndenotes the total number of observed intervals.Thus,(4) becomes the following form:

Transform (5) to obtain the following discrete equations:

Equation (6) is called the grey delayed S-shaped software reliability model.

4.2 Grey inflection S-shaped software reliability model

The cumulative function of failuresm(t) of the inflection S-shaped software reliability model is expressed as

Its differential equation can be represented as

Similar to Subsection 4.1,the discrete inflection S-shaped software reliability model is defined as

Equation (10) is called the grey inflection S-shaped software reliability model.

4.3 Grey Yamada exponential software reliability model

The cumulative function of failuresm(t) of the Yamada exponential software reliability model is expressed as

Its differential equation can be represented as

Similar to Subsection 4.1,the discrete Yamada exponential software reliability model is defined as

Equation (14) is called the grey Yamada exponential software reliability model.

4.4 Grey Yamada Rayleigh software reliability model

The cumulative function of failuresm(t) of the Yamada Rayleigh software reliability model is expressed as

Similar to Subsection 4.1,the discrete Yamada Rayleigh software reliability model is defined as

In the same way,(18) is called the grey Yamada Rayleigh software reliability model.

Equations (6),(10),(14),and (18) are examples of several grey software reliability models proposed in this paper.It can be seen that they are discrete difference equations and approximately equal to the original continuous NHPP software reliability models.Therefore,these grey software reliability models still remain some characteristics of the NHPP,and the uniqueness is that they may simulate small and discrete data more realistically.

5.Grey-based approach for estimating software reliability under NHPP

Software failures may be highly correlated in the early stage of testing,while the number of failures would be closer to a constant in the later stages.So a single method of uncertain systems may not be enough to deal with the software failure process.This paper proposed a different approach than previous and describe the failure behavior of software based on multiple uncertainty theories of stochastic process and grey system.Specifically,it is assumed that the failure data not only has the characteristics of stochastic process,but also has the behavior characteristics of grey system.

In addition,with the development of software testing,the ultimate number of remaining failures will be reduced,and the amount of data will not be adequate.Such that,for the NHPP software reliability models,the maximum likelihood estimate (MLE) may not work well.Hirose [47]presented a typical example in which the predicted total failures emerge serious deviations.Such phenomena also occurred in other cases [48,49].In view of this,the model parameters are estimated by the nonlinear least square principle in this paper.Furthermore,different models and different training data may result in different grey background value coefficients,so the grey background value coefficient θ is also set as a variable in the interval [0,1]to search for the best coefficient.

Next,we will take the grey Yamada Rayleigh model as an example to describe the computational steps of the grey-based approach for estimating software reliability under the NHPP,and the other three grey models are similar.

The grey-based estimating approach under the NHPP can be treated as a nonlinear multi-objective programming problem,and the grey Yamada Rayleigh software reliability modeling under the NHPP can be expressed as follows:

wherenkdenotes as the actual defects found by timetk.There are four parametersa,b,c,θ that need to be estimated.We will estimate these four parameters in two stages.The computational steps can be summarized as follows:

Step 1Input the failure data into the grey Yamada Rayleigh software reliability model (i.e.,(18)).

Step 2Calculate the symbolic solutions of parametersa,baccording to the least square principle.

Step 3Substitute the symbolic solutions of parametersa,binto the Yamada Rayleigh software reliability model (i.e.,(15)).c,θ according to the nonlinear least square estimate.

Step 4Calculate the optimal solutions of parameters

Step 5Return to (18) to find the optimal solutions of parametersa,busing the parametersc,θ estimated in Step 4.

Step 6Substitute all parameters into the Yamada Rayleigh software reliability model to calculate the related software reliability measurements.

The nonlinear optimization in Step 4 needs to be done by some computer software.In this paper,the optimization is realized using the genetic algorithm (GA) by programming in Matlab.

6.Numerical experiments

This section is to test the effectiveness of the grey-based approach for estimating software reliability under the NHPP.Four numerical experiments are to predict dynamically the total number of failures in the software testing process using four datasets come from Wood [50].Meanwhile,the single NHPP software reliability model is estimated by the MLE and is used for comparisons.R-square is calculated dynamically to judge the fitting accuracy,and the relative error of prediction is calculated dynamically to compare the forecasting performance.Moreover,the predictive validity is judged by plotting the relative error of the normalized test time.

The relative error of prediction is defined as follows:Assume the actual number of defects observed isMby the end of test timeT.Use the failure data up to timetk(tk≤T) to get the predicted number of failuresm(T) byT,then the ratio (m(T)?M)/Mis called the relative error.This procedure repeated with varioustkyields the dynamical relative error.

Dataset 1There are 19 test weeks and the actual number of defects observed is 42 (that is,T=19,M=42).The predicted numbers of defects and the R-square under different test time are calculated by the single delayed S-shaped model and by the grey delayed S-shaped modeling under the NHPP.Table 1 listed these results,and Fig.3 plots the relative error of prediction and the R-square against the different percentage of data points.

As shown in Table 1,both the single delayed S-shaped model and the grey delayed S-shaped modeling under the NHPP have high R-square,the minimum R-square is over 0.953,and most of them are over 0.97,they can all simulate Dataset 1 well.However,the prediction obtained by the single delayed S-shaped model is poor at the beginning,especially at the eighth week.It is not until the 16th week that the prediction is stable.On the contrary,the prediction obtained by the grey delayed S-shaped modeling under the NHPP is relatively more stable,and converged after the ninth week.It is clearly seen from Fig.3 that the R-square curves of the single delayed S-shaped model and the grey delayed S-shaped modeling under the NHPP are straight and close to 1,and the relative error of the grey delayed S-shaped modeling under the NHPP approaches 0 after 45% of data points.However,the relative error of the single delayed S-shaped model fluctuates and tends to 0 until 85% of the data points.

Table 1 Comparison results for different estimates of delayed S-shaped model on Dataset 1

Fig.3 R-square and relative error curves of different estimates of delayed S-shaped model on Dataset 1

Dataset 2There are 20 test weeks and the actual number of defects observed is 100 (that is,T=20,M=100).The predicted numbers of defects and the R-square estimated by the single inflection S-shaped model and by the grey inflection S-shaped modeling under the NHPP for various test time are shown in Table 2.Similarly,Fig.4 plots the relative error of prediction and the R-square against the different percentage of data points.

Table 2 Comparison results for different estimates of inflection S-shaped model on Dataset 2

Fig.4 R-square and relative error curves of different estimates of inflection S-shaped model on Dataset 2

Table 2 shows both the single inflection S-shaped model and the grey inflection S-shaped modeling under the NHPP still have high R-square,the minimum R-square is over 0.9141,and most of them are over 0.96.However,the prediction of the single inflection S-shaped model is approximately equal to the actual defects until the 19th week.In contrast,the prediction obtained by the grey inflection S-shaped modeling under the NHPP is much more accurate,and is almost stable after the ninth week.Similarly,Fig.4 shows the R-squares of the single inflection S-shaped model and the grey inflection S-shaped modeling under the NHPP are all close to 1,and the relative error of the grey inflection S-shaped modeling under the NHPP approaches 0 after 45% of data points.However,the relative error of the single inflection S-shaped model seriously deviates from 0,and tends to 0 until 90% of the data points.Finally,the grey inflection S-shaped modeling under the NHPP converges earlier than the single inflection S-shaped model by 45% of data points.

Dataset 3There are 19 test weeks and the actual number of defects observed is 120 (that is,T=19,M=120).The predicted numbers of defects and the R-square estimated by the single Yamada exponential model and by the grey Yamada exponential modeling under the NHPP are shown in Table 3.Meanwhile,Fig.5 plots the relative error and the R-square against the different percentage of data points.

Fig.5 R-square and relative error curves of different estimates of Yamada exponential model on Dataset 3

Table 3 Comparison results for different estimates of Yamada exponential model on Dataset 3

Table 3 indicates the R-square of the single Yamada exponential model is still high,and the prediction converges after the 17th week.By contrast,the R-square of the grey Yamada exponential modeling under the NHPP is not high at the beginning,but after the 11th week,both the R-square and the prediction accuracy all converge.The above analysis is clear in Fig.5.The R-square curve of the single Yamada exponential model is a straight line close to 1,where its relative error seriously deviates from 0,and tends to 0 until the last data points.The R-square and the relative error of the grey Yamada exponential modeling under the NHPP have the same features,and the relative error converges after 50% of data points,earlier than the single Yamada exponential model by 40% of data points.

Dataset 4There are 12 test weeks and the actual number of defects observed is 61 (that is,T=12,M=61).The predicted numbers of defects and the R-square estimated by the single Yamada Rayleigh model and by the grey Yamada Rayleigh modeling under the NHPP are shown in Table 4.Similarly,Fig.6 plots the relative error and the R-square against the different percentage of data points.

In this dataset,the test week is relative small.Table 4 shows the R-square of the single Yamada Rayleigh model is high,and the predicted total defects is equal to the actual values after the ninth week.The difference is,the R-square of the grey Yamada Rayleigh modeling under the NHPP is not high at the beginning,but after the seventh week,the predicted number of failures is very close to the actual values,and the R-square also becomes high.Fig.6 clearly shows the above results.The R-square curve of the single Yamada Rayleigh model is a straight line close to 1,and its relative error seriously deviates from 0.It is very obvious that the relative error of the grey Yamada Rayleigh modeling under the NHPP converges much earlier than that of the single Yamada Rayleigh model.

Table 4 Comparison results for different estimates of Yamada Rayleigh model on Dataset 4

Fig.6 R-square and relative error curves of different estimates of Yamada Rayleigh model on Dataset 4

7.Conclusions

Neither the single stochastic process model nor the combined model for correcting residual errors can completely solve the problems in software reliability estimation.In this paper,we investigate the characteristics of grey uncertain information in the NHPP software reliability models.A new grey-based approach for estimating software reliability under the NHPP is presented and is applied to predict the total number of failures in the software testing process.The results of numerical experiments indicate the predictive relative error of these single NHPP software reliability models having high R-square fluctuated greatly in the early and middle testing stages,and sometimes even in the last testing stage.In contrast,the new grey-based estimating approach under the NHPP effectively improves this problem and can predict the final stage much earlier although without higher fitting accuracy.Results also show that the new grey-based estimating approach under the NHPP can almost offer a more accurate prediction of the future total number of failures at 50% of the test process,and the shorter the software testing time,the more obvious the effectiveness (for example,the experiment of Dataset 4).Therefore,this paper verifies that the modeling method of combining randomness and greyness might be better than that of single randomness in software reliability estimation.

In addition,the grey-based approach for estimating software reliability can be applicable to all NHPP software reliability models.Therefore,the grey-based approach for estimating software reliability under the NHPP is of practical significance in predicting the behavior of software future failures in the early testing process.