Transcript SENG 521

SENG 521
Software Reliability &
Testing
Software Reliability Models
(Part 2b)
Department of Electrical & Computer Engineering, University of Calgary
B.H. Far
（[email protected]）
http://www.enel.ucalgary.ca/~far/Lectures/SENG521/02b/
SENG521 (Fall 2002)
[email protected]
1
Contents








Basic Features of the Software Reliability Models
Single Failure Model
Reliability Growth Model
Exponential Failure Class Models
Weibull and Gamma Failure Class Models
Infinite Failure Category Models
Bayesian Models
Early Life-Cycle Prediction Models
SENG521 (Fall 2002)
[email protected]
2
Goal

It is important to be able to




Predict probability of failure of a component or
system
Estimate the mean time to the next failure
Predict number of (remaining) failures
during the development.
Such tasks are the target of the reliability
management models.
SENG521 (Fall 2002)
[email protected]
3
Background
Randomness & Probability
SENG521 (Fall 2002)
[email protected]
4
Randomness /1

Random actions:




Introduction of defects into the code
Execution of the test-cases
We should define some random processes to
represent the randomness
How to handle randomness?



Collect failure data through testing
Find a distribution function that is a best-fit for the
collected data
Make assumptions about the presence of errors and
reliability
SENG521 (Fall 2002)
[email protected]
5
Randomness /2

What is a random variable?


A random variable x on a sample space S is a rule
that assigns a numerical value to each outcome of
S (a function of S into a set of real numbers)
In reliability modeling what can be
represented by random variable?


Time of failure
Number of failures
SENG521 (Fall 2002)
[email protected]
6
Probability Distribution /1


Suppose that a random variable X assigns a
finite number of values to a sample space S
Then X induces a distribution function f that
assigns probabilities to the points in Rx
Rx ={x1, x2, x3, …, xn}
f(xk) = P( X=xk)
SENG521 (Fall 2002)
[email protected]
7
Probability Distribution /2
The set of ordered pairs [xk, f(xk)] is usually
represented by a table or a graph (histogram)
Frequency
(Failure/time unit)

20
15
10
5
0
1
1.5
2
2.5
3
3.5
4
4.5
5
Time (days)

The expected value of X, denoted by E(X) is
defined by
E(X) = x1 f(x1) + x2 f(x2) + …+ xn f(xn)
SENG521 (Fall 2002)
[email protected]
8
Probability Distribution /3





Let M(t) be a random process representing the
number of failures at time t
The mean function μ(t) represents the expected
number of failures at time t
μ(t) = E(M(t))
Failure intensity is the rate of change of the
expected number of failures with respect to time
λ(t) = d μ(t) / dt
(t) is the number of failures per unit time
(t) is an instantaneous value
SENG521 (Fall 2002)
[email protected]
9
Probability Distribution /4

Discrete distributions:



Binomial distribution
Poisson distribution
Continuous distributions:







Normal / Gaussian distribution
Lognormal distribution
Weibull distribution
Rayleigh distribution
Exponential distribution
Gamma distribution
2 distribution
SENG521 (Fall 2002)
[email protected]
10
Binomial Distribution /1



Gives probability of exact number
of successes in n independent
trials, when probability of success
p on single trial is a constant.
Situations with only 2 outcomes
(success or failure)
Probability remains the same for
all independent trials (Bernoulli
trials)
SENG521 (Fall 2002)
[email protected]
Jakob Bernoulli
(1645-1705)
11
Binomial Distribution /1

Probability of exactly x successes:
 n  x n x
n
x n x
f x   !
p q    p q
!
x n  x 
 x
!
n
f(x)
p
q
: number of trials
: probability of x successes in n trials
: probability of success
: probability of failure
p + q =1
SENG521 (Fall 2002)
[email protected]
12
Binomial Distribution /2

Probability of at least r successes:
 n  x n x
F r      p q
x 0  x 
r
n : number of trials
f(x) : probability of x
successes in n trials
p : probability of success
q : probability of failure
p + q =1
F(r) : probability of obtaining
r or fewer successes in
n trials
SENG521 (Fall 2002)
Calculating F(r) becomes increasingly
difficult as n (sample set) gets larger
It is possible to find an approximate
solution by means of a normal
distribution
[email protected]
13
Example: Binomial Distribution

Acceptance sampling:
 A lot is accepted if not more than 2 defectives are
found in a sample of 6. The defect probability is 25%.
 Probability of having exactly 2 defects in the lot is:
6
f 2    0.252  0.754  0.297
 2

Probability of having more than 4 defects in the lot is:
 6
F r  4  F 5  F 6    0.255  0.751  0.256  0.0046
5
SENG521 (Fall 2002)
[email protected]
14
Poisson Distribution /1



Some events are rather rare, they don’t happen
that often. Still, over a period of time, we want
to say something about the nature of rare
events.
Poisson distribution is special case of binomial
distribution (either p or q is very small and n
very large)
Conditions under which a Poisson distribution
holds



Simeon Poisson
(1781-1840)
counts of rare events
all events are independent
average rate does not change over the period of
interest
SENG521 (Fall 2002)
[email protected]
15
Poisson Distribution /2

Poisson distribution is a special case of
binomial distribution (either p or q is very
small and n very large): =np
x
μ μ
f(x)  e
x!
x  0,1,2,...
: mean rate of occurrence (in statistics literature is
usually denoted by )
x : observed number of failures
SENG521 (Fall 2002)
[email protected]
16
Example: Poisson Distribution

Suppose that the defect rate is only 2%
find the probability that there are 3 defective
items in a sample of 100 items.
  np  100  0.02  2
2
2  e 23  e 2
pf x  3 !
 0.18
 0.18
!
3
3
3
SENG521 (Fall 2002)
[email protected]
17
Exponential Failure
Time Models
SENG521 (Fall 2002)
[email protected]
19
Exponential Failure Time Models



Assumes finite failure models
Functional form of failure intensity function
is exponential
Binominal type:



All faults have a constant hazard rate z(t) = 
Hazard rate for the i-th fault is a function of the
remaining number of faults
Failure intensity is  t   N e t
SENG521 (Fall 2002)
[email protected]
20
Various Reliability Models

Exponential Failure Time Models






Jelinski-Moranda model (JM)
Nonhomogeneous Poisson Process model
(NHPP)
Schneidewind model
Musa’s Basic Execution Time model (BET)
Hyperexponential model (HE)
Others
SENG521 (Fall 2002)
[email protected]
21
Jelinski-Moranda Model /1


Jelinski-Moranda model follows exponential
distribution but differs from the Geometric model in
that the parameter used is proportional to the
remaining number of faults rather than a constant.
All faults equally contribute to the reliability of the
system
Hazard Rate z(t):
Probability density
function divided by
reliability function.
 is a constant
SENG521 (Fall 2002)
[email protected]
22
Jelinski-Moranda Model /1

Assumptions:






The rate of fault detection is proportional to the current fault content
of the software.
The fault detection rate remains constant over the intervals between
faults.
A fault is corrected instantaneously without introducing new faults
into the software.
Every fault has the same chance of being encountered within a
severity class as any other fault in that class.
The failures are independent.
Data requirement:


Either actual failure times: t1, t2, …, tn
Or elapsed time between failures: xi = ti – ti-1
SENG521 (Fall 2002)
[email protected]
23
Jelinski-Moranda Model /2


Meantime between failures at time t
MTTF = 1/  (N-(i-1))
Mean failures experienced
 t   N 1  e

t
Failure intensity function
 t   N e
SENG521 (Fall 2002)
t
[email protected]

N total
number of
faults
(constant)
Parameters to
estimate using
collected data
are: N and 24
Non Homogeneous Poisson
Process Model /1



Assumes that the cumulative number of
failures detected at any time follows a
Poisson distribution.
Time periods can be unequal
Data requirement:


Fault counts on each testing interval: f1, f2, …, fn
Completion time of each period: t1, t2, …, tn
SENG521 (Fall 2002)
[email protected]
25
Non Homogeneous Poisson
Process Model /2

Assumptions:





Every failure has the same chance of being detected as
any other failure.
The cumulative number of failures detected at any time
follows a Poisson distribution with mean (t).
That mean is such that the expected number of failures in
any small time interval about t is proportional to the
number of undetected failures at time t.
The mean is assumed to be a bounded non-decreasing
function with (t) approaching in the limit, as the length
of testing goes to infinity.
Perfect debugging is assumed.
SENG521 (Fall 2002)
[email protected]
26
Non Homogeneous Poisson
Process Model /3


Mean failures experienced
 t   N 1  e
 bt

Failure intensity function
 t   Nbe
SENG521 (Fall 2002)
 bt
[email protected]
Parameters to
estimate using
collected data
are: N and b
27
Schneidewind Model



Assumes that the current fault rate might be a better
predictor of the future behaviour than the observed
rate in the distant past
Suppose that there are n units of time all of fixed
length
Has 3 variations:



Utilize all individual fault counts from all n time periods
Ignore fault counts from 1 to s-1 periods (forget the
distant past)
Use cumulative fault count for 1 to s-1 periods and
individual fault counts for s to n
SENG521 (Fall 2002)
[email protected]
28
Musa Basic Model /1


One of the most widely used software reliability
models.
Uses execution time rather than calendar time.
0 and 1 are
parameters. 0 is
equal to the number of
faults in the system
and 1 is a fault
reduction factor.
SENG521 (Fall 2002)
[email protected]
29
Musa Basic Model /2

Assumptions:






The detections of failures are independent of one another.
The software failures are observed (i.e. the total number
of failures has an upper bound).
The execution times (measured in CPU time) between
failures are piecewise exponentially distributed.
The hazard rate is proportional to the number of faults
remaining in the program.
The fault correction rate is proportional to the failure
occurrence rate.
Perfect debugging is assumed.
SENG521 (Fall 2002)
[email protected]
30
Musa Basic Model /3

Meantime between failures at time t

C

MTTF(t)  MTTF0 exp 
 n0 MTTF0

Mean failures experienced
 t    0 1  e

 1t
Failure intensity function
 t    0 1 e
 1t


t 

n0 = total number of
errors in the
program
MTTF0=MTTF at
the start of testing
C= test compression
factor
SENG521 (Fall 2002)
[email protected]
31
Musa Basic Model /4

Number of errors at time t


C

mber of errors n(t)  n0 1  exp  
 n0 MTTF0



t 

n0 = total number of
errors in the
program
Reliability
t 

R(t)  exp  

 MTTF 
MTTF0=MTTF at
the start of testing
C= test compression
factor
SENG521 (Fall 2002)
[email protected]
32
Hyper-exponential Model /1


The basic idea is that the different sections (or
classes) of the software experience an exponential
failure rate; however, the rates vary over these
sections to reflect their different natures. This could
be due to different programming groups doing the
different parts, old versus new code, sections
written in different languages, etc.
We thus reflect the sum of these different
exponential growth curves, not by another
exponential, but by a hyper-exponential growth
curve.
SENG521 (Fall 2002)
[email protected]
33
Hyper-exponential Model /2

Data requirement:



Fault counts on each testing interval: f1, f2, …, fn
Completion time of each period: t1, t2, …, tn
Failure intensity function
 t   N
K
 it
p

e
 i i
i 1
0  pi  1
SENG521 (Fall 2002)
K
p
i 1
i
1
[email protected]
0  i  1
34
SENG521 (Fall 2002)
[email protected]
35