Due to the critical challenges and complexity of modern software systems developed over the last decade, there has arisen an ever increasing attention to look for products with high reliability at reasonable costs. Software development process moves toward component-based design, and architecture based approach in software reliability modeling is widely used. However, in lots of models for software reliability assessment the assumption of independent software runs is a simplification of real software behaviour. This paper describes two software reliability models that use high-order Markov chains thus taking into account dependencies among software component runs for more accurate software reliability assessment. The efficiency and accuracy of developed models is investigated by the example of several software products. It is shown that using the software reliability models based on the high-order Markov chains results in the software reliability assessment accuracy up to 10-20%.
Computer systems are widely used in modern industry for control and automation purposes. All of these systems are controlled by software. Thus, software is used in air traffic control, nuclear power plants, automated patients monitoring etc. Therefore high requirements for software reliability are demanded because failures of such systems can lead not only to significant financial losses, but also threaten human life and health. Although techniques that allow assessing and ensuring the specified hardware reliability requirements have been developed, there are no common approaches for software systems assessment.
According to STD-729, software reliability is defined as the probability of failurefree software operation for a specified period of time in a specified environment [1, 2]. Although Software Reliability is defined as a probabilistic function, and comes with the notion of time, it should be noted that, contrast to traditional hardware reliability, software reliability is not a direct function of time [1]. Electronic and mechanical parts may become "old" and wear out with time and usage, but software will not rust or wear-out during its life cycle. Software will not change over time unless intentionally changed or upgraded.
The history of software reliability assessment methods and tools began in the 60s of last century. A number of researchers [3-7] worked on issues of development and research of software reliability analysis and assessment models and methods that would allow reducing the costs required for software testing stage. New software reliability assessment models that reflect the internal structure of the application and interaction of its components [6], called architectural-based models, are being developed because of increasing complexity of software systems and the result of expanding their functional purpose.
In known models based on architectural approach [6, 7] the theory of first order Markov chains is used with the assumption that the software components runs are independent. This assumption is not always true due to the complexity of modern software architecture and huge set of usage scenarios this assumption [8, 9]. Therefore, for the development of adequate software reliability assessment models, which will improve the testing process (e.g. allow to reduce the needed resources), one should consider the high-order Markov chains, which allow to take into account the interdependence of components runs [10].
This paper describes the software reliability assessment models based on architectural approach, which use discrete and continuous time high-order Markov chains and their comparison based on real world data. Nowadays architecture-based software reliability models have been well studied in theory, but there is lack of papers describing their practical applications. Developing of high-order models for software reliability assessment is not described enough in literature as well. Thus, the development of new architecture-based software reliability assessment models that take into account the dependencies among software component runs along with their application to real world data is still a problem waiting for solution. 2 Software Reliability Model with Discrete Time High-Order Markov Chain
This model considers absorbing Markov process that implies the existence of one or more absorbing states, i.e. states that, once entered, cannot be left.
The developed software reliability assessment model [10] is hierarchical, that is initially software architecture parameters are calculated based on software usage model [11] using the theory of Markov processes, and then the behaviour of each component failures is taken into account.
The discrete time HOMC software reliability model can be described using the following components – Ci is the graph with vertices corresponding to software components, while edges indicates the program control flow ( i 1, N , where N is the number of program components); P pij..kl is the high-order transition proba
In turn, the reliabilities of each component ( Rl ) using high-order Markov chains are calculated by
N R Rl l1
.
Rl exp ( Vij .. kltij .. kl ij . k l (t)dt) 0 bility matrix ( pij..kl – transition probability from component і to component l depending on being in previous K components); Q qij..kl is the initial probability vector; i t is the failure rate of i -th software component.
According to this model the reliability of the whole system is calculated as
(
To calculate Vij..kl – the expected number of visits a component l depending on being in previous K components – one has to solve the following system of linear equations:
N 1 V j..kl qij..k Vij..k pij..kl i1 , here tij..kl denotes the time spent at the component l depending on being in previous K components. 3 Software Reliability Model with Continuous Time HighOrder Markov Chain
Using discrete-time model has a number of significant simplifications and restrictions. Thus, this model takes into account only the number of visits to i -th component without taking into account of the distribution function of this random variable (while taking it into account the expected value should be used). In addition, it is clear that at any given time t the software failure is generally caused by the failure of the software component, which is executed at a given time (in case of sequential connection of software components in Reliability Block Diagram). Thus, to increase the degree of adequacy of the software reliability architectural model the continuous time Markov chains should be used.
The continuous time HOMC software reliability model can be described using the following components – Ci is the graph with vertices corresponding to software components, while edges indicates the program control flow ( i 1, N , where N is the number of program components); A aij is the high-order transition probability matrix i, j 1, N (the values of matrix elements aij depends on the way of getting into the state i ); P pi t is the probability vector, where pi t is the probability being in state Ci at time t ; i t is the failure rate of i -th software component.
In this case, the failure rate of a software system consisting of N components can
be written as [12]
(
N t pi t i t here i t is the failure rate of i -th component, pi t is the probability of i -th component execution at time t .
Components failure rates i t can be obtained from the results of unit testing using known software reliability models, for example ones based on an inhomogeneous Poisson process [13].
If the flow control between the components of the software is presented as a Markov process with continuous time, assuming that the i -th state of the process is the execution of i -th component, the time dependences of the probabilities being in i -th state ( pi t ) can be obtained by solving the system of equations of the Kolmogorov– Chapman [14] for this process: dpi t dt ij (t) p j (t) ji (t) p j (t), i S jS jS , here ij (t) is the transition intensity from component і to component j at time t, and S denotes the set of all system states. In general the transition intensities ij (t) depends on the transition probabilities aij and could be calculated from latter.
To take into account the interdependence of execution of software component (and consequently changes of transition probability from i -th state) depending on the way of getting to the current state, the high-order Markov chain should be used (the order K of the model determines the accounted length of the path). In a case of high-order Markov chains the actual problem is to calculate the transition probabilities depending on the program control flow background.
It is well known that a high order Markov chain can be represented as a first order chain by appropriate redefining the state space [15]. For software implementation of models that use high-order chains, it is necessary to have the formalized algorithm for this representation. Using the analogy with the known Erlang phase method [16] a high-order Markov process can be represented as an equivalent first-order process with additional virtual states. Each state of the original graph Ci (geometric diagram, showing the possible states of the system and the possible transitions of the system from one state to another) is split into such number of virtual states as many different paths of length K to this state exist. Thus the problem solution essentially is reduced to using of graph theory. Therefore, to calculate the number miKj of chains of K-th order from state i to state j the following expression based on the Floyd method can be used: j1
S miKj mK 1 eil m1 il lj , here eij are the elements of the identity matrix.
Using (
For calculation of software reliability measures, based on the obtained relationship
(
- reliability function P(t) – the probability that no failure will occur within the time interval [0, t] – can be calculated as mean operating time to failure Tl
t P(t) exp ( ( )d )
0 0
T1 P( )d 4 Determination of the Markov Chain Order for Software Reliability Assessment
In this paper it is proposed to use AIC and BIC criteria [17] since they are not a
hypothesis test and they don’t use the significance level. Although these criteria give
consistent results and don’t depend on the estimated model order. They are efficiently
(
In general AIC criterion [19] is calculated by the following expression: AIC 2k 2ln(L) , here k is the number of independent parameters in the model, and L is the model’s maximum likelihood function.
If the value of this software model’s maximum likelihood function is substituted in
the expression (
AIC (K ) 2N K (N 1) 2 ln(
pij..kl nij..kl ) , i, j,.., k,l
In the case of using the BIC criterion for the Markov chain optimal order
determination in the case of software reliability modeling, the expression similar to AIC
criterion (
As it can be seen from (
An alternative to AIC criterion is ВІС [21], which takes into account the number of elements in observable sequence and expressed as
BIC(K) 2 ln(L) ln(n)k.
BIC (K ) 2N K (N 1) ln(n) 2
nij..kl ln pij..kl .
i, j,.., k,l
It is worth noted that the BIC criterion should be used at the small sample size of empirical data concerning the software usage, because it imposes stronger penalties even when the sample size n>8.
Thus, after determining the order of Markov chain, the well-known classical Markov tools can be used for software reliability assessment as it was described above. 0,90 0,85 R , ity0,80 li b a li e R 0,75 0,70
To study the efficiency of the developed software reliability assessment model that uses the discrete time high-order Markov chains, the reliabilities of the five software systems, developed by one of the authors, were calculated using the first and the high order Markov chain models. The average amount of software components in tested software systems is 10. The results of reliability calculations using the first and the high-order models are shown in Fig. 1 along with the reliability obtained from unit testing data.
1 2
3
4 5
The probability transition matrix and the initial probability vector of the Markov chain were calculated and are summarized in Table 2 and Table 3 correspondingly.
The initial graph Ci indicating the program components and control flow, as well as graph Ci of the equivalent second order (see Table 4) Markov process are shown in Fig. 2 and 3 correspondingly. The notations in these figures are as follows: I correspond to Input state, C – to Calculation, O – to Output, and E to Exit state (see Table 2); indexes indicates the previous state in control flow history (thus state OC means that the current state Output has been reached from previous state Calculation).
E Ii
E Io
Oc Oo
Ic Ci creases by more than 60 a.u. the difference between values of t obtained from both models almost tends to be negligible. Reducing the difference of t values, obtained from the first and the second-order models, to zero at high times can be explained by decreasing of the t value itself and by the absence of differences in the software behaviour description by two models in this case. In the case of t both models suggest that system is in the “Exit” state (see Fig. 2, 3) and, accordingly, its failure rate is limited by this component failure rate. Differences of t behaviour on the initial evolution stages of software system can be entirely explained by differences in the software system behaviour description by different models, where the first-order model ignores the interdependence of software component runs, and therefore the probabilities of components executing are different at given time t for both models. Thus, it could be argued that software reliability model based on the high order Markov chain describes the software system behaviour more adequately and determines its reliability measures more accurately.
0 10 20
30 t, a.u.
40 90 100
This conclusion is confirmed by the analysis of software system reliability function
time dependence obtained using equation (
understood if taking into account the interval estimation of reliability for the range 0, t [15], and its deviation evidently increases with interval length increasing.
So, we can conclude that ignoring the interdependence of software components runs could results in increasing inaccuracy of software reliability measures estimation up to 20%.
Another measure of reliability, which was used to determine the developed
highorder model effectiveness and adequacy, is the mean operating time to failure T1 . The
value of mean operating time to failure calculated by the expression (
1,0 0,8 ) 0,6 t ( P 0,4 0,2 1 - first order model 2 - second order model 1
2 50 t, a.u. 0 10 20 30 40 60 70 80 90 100
Therefore, the usage of software reliability models based on the high-order Markov chains even with a small components number (in this case there was 4 component software, see Fig. 2) and complexity (in this case the optimal model order is 2, see Table 4) results in the increase of model adequacy and the software reliability assessment accuracy on 10–20%. The value of such growth of reliability estimation accuracy is especially important in the case of complex hardware and software systems in which the mistake of software component reliability estimation can repeatedly affect the accuracy of whole system reliability assessment. Using the high-order models for more complex software systems could results in more significant improvements of reliability assessment.
In this paper the software reliability models using discrete and continuous time high-order Markov chains, which enable consideration the dependencies among software components runs, have been developed. Software reliability assessment based on the high-order discrete time Markov chains allows to increase the software reliability measures accuracy up to 6 %, and high-order continuous time Markov chain – up to 10–20%. The advantage of high-order discrete time Markov chains model for software reliability analysis is small computing resources needed even for software with a lot of components, while the advantages of high-order continuous time Markov chains model are independence from the sampling step (in the case of discrete time model it may cause inaccurate transition probabilities calculation), and also automatic consideration of transitions pii that avoids unnecessary computations. Practical aspects of estimating input parameters for the models as well as studying the dependence of the software reliability on its characteristics (components number, the average number of variables in the component, components cohesion etc.) will be described elsewhere. 13. Seniv, M., Yakovyna, V., Chabanyuk, Ya., Fedasyuk, D.: The Method of Reliability Prediction and Estimation Based on Model with Dynamic Index of Project Size. Computing 10, 97–107 (2011) (in Ukrainian) 14. Polovko A., Gurov, S.: Fundamentals of the Reliability Theory. Practical work. BHV
Peterburg (2006) (in Russian) 15. Markov Models, Hidden and Otherwise, http://kochanski.org/gpk/teaching/0401Oxford/HMM.pdf 16. Volochiy, B.Yu., Ozirkovskii, L.D., Kulyk, I.V.: Formalization of Discrete-Continuous Stochastic Systems Model Building using Erlang Phases Method. Vidbir i Obrobka Informatsii 36, 39–47 (2012) (in Ukrainian) 17. Burnham, P.: Model Selection and Multimodel Inference: a Practical Information
Theoretic Approach. Springer, Heidelberg (2002) 18. Liu, T.: Application of Markov Chains to Analyze and Predict the Time Series. Modern
Applied Science 4(