Reliability
An Introduction
|
|
Prof. David Bernstein
James Madison University
|
|
| Computer Science Department |
| bernstdh@jmu.edu |
|
Definitions
- Rugged:
- Reliable - Low probability of failure under normal
operating conditions
- Robust - Able to operate under a wide variety of condtions
- Safe - Able to minmize the damage resulting from failure
- (Probabilistic) Reliability:
- The probability that a system will perform its required functions
(without failure) in a particular environment
for a particular amount of time
Different Kinds of Systems
- Non-Repairable:
- The system can't be repaired after it fails
- Our concern is with measures like the probability of
a failure and the remaining life
- Repairable:
- The system can be repaired after it fails
- Our concern is with measures like the probability that
it won't fail, the time between failures, and the
availability
Failure Patterns
- Increasing Failure Rate:
- Usually a result of deterioration
- Decreasing Failure Rate:
- Usually a result of "hardening" or "burn-in"
- Usually temporary
- Constant Failure Rate:
- Usually a result of "stress"/"overload" (i.e., beyond
normal operating conditions)
Differences between Hardware and Software
|
Hardware
|
Software
|
| Components can "burn in" and "wear out" |
Components do not "burn in" or "wear out" |
| Variation across "copies" |
No variation across "copies" |
Mathematical Preliminaries
- The Setting:
- A system that we are considering over
a time interval \([0,t]\)
- Our Concern:
- \(R\) - the reliability of the system
over the interval
Some Notation
- Component Performance:
- \(X_i\) is 1 if the component performs adequately
over the interval and 0 otherwise
- System Performance:
- \(\phi(X_1, X_2, \ldots, X_n)\) is 1 if the system
performs adequately over the interval and 0 otherwise
Archetypical Systems
- Series Systems:
- The system fails if any of its components fails
- \(\phi(X_1, X_2, \ldots, X_n) =
\min\{X_1, X_2, \ldots, X_n\}\)
- Parallel Systems:
- The system fails if all of its components fails
- \(\phi(X_1, X_2, \ldots, X_n) =
\max\{X_1, X_2, \ldots, X_n\}\)
Reliability of Archetypical Systems
- Series System:
- \(R = P\{\min(X_1, X_2, \ldots, X_n) = 1\} =
P\{X_1=1, X_2=1, \ldots, X_n=1\}\)
- If the components are independent,
\(R = P\{X_1=1\} \cdot P\{X_2=1\} \cdots \cdot P\{X_n=1\}\)
- Parallel Systems:
- \(R = P\{ \max\{X_1, X_2, \ldots, X_n\} = 1\} =
1 - P\{X_1=0, X_2=0, \ldots, X_n=0\}\)
- If the components are independent,
\(R = 1 - (1-P\{X_1=1\}) \cdot (1-P\{X_2=1\}) \cdots \cdot
(1-P\{X_n=1\})\)
Examples Involving Archetypical Systems
- Series System:
- Suppose we have two networks that are connected by a single
path consisting of four routers
- Suppose further that the routers have probabilities of
working of 0.9, 0.8, 0.9, and 0.7.
- The reliability of the path working is
\(R = 0.9 \cdot 0.8 \cdot 0.9 \cdot 0.7 = 0.45\)
- Parallel System:
- Suppose we have an electronic commerce site that has four
servers all providing the same services
- Suppose further that the servers have probabilities of
working of 0.9, 0.8, 0.9, and 0.7.
- The reliability of the site working is
\(R = 1 - (1-0.9) \cdot (1-0.8) \cdot (1-0.9) \cdot (1-0.7)
= 1 - (.1)(.2)(.1)(.3) = 1 - 0.0006 = 0.9994\)
\(k\) Out of \(n\) Systems
- Defined:
- The system operates adequately if any \(k\) out of
\(n\) components operate adequately
- An Implication:
-
\(\phi(X_1,X_2,\ldots,X_n) = \left\{
\begin{array}{l l}
\text{1 if }\sum_{i=1}^{n}X_i \geq k \\
\text{0 if }\sum_{i=1}^{n}X_i \lt k
\end{array}
\right.
\)
Reliability of \(k\) Out of \(n\) Systems
- In General:
- Finding the reliability for such systems is very
complicated
- An Important Special Case:
- All of the components are independent and have the same
probability of failure, \(p\). In this case,
\(\sum_{i=1}^{k}X_i\) has a binomial distribution so:
- \(R = \sum_{i=k}^{n}
\left( \begin{array}{c}n \\ i\end{array} \right)
p^i (1 - p)^{n-i}
\)
- Recall:
-
\(\left( \begin{array}{c}n \\ i\end{array} \right) =
\frac{n!}{i!(n-i)!}\)
An Example of a \(k\) Out of \(n\) System
- The System:
- Suppose we have a disk array that can continue to work
adequately if any 4 out of 8 disks is working adequately
- Suppose further that each disk has a probability of
0.95 of working adequately
- The Reliability:
- \(R = \sum_{i=4}^{8}
\left( \begin{array}{c}8 \\ i\end{array} \right)
(0.95)^i (0.05)^{8-i} = 0.9999
\)
Reliability of Networks
- More General Systems:
- We would like to consider the reliability of systems
that can be represented as graphs
- An Example:
-
- Traffic can move from A to D if 1 and 4 are operating,
or if 2 and 5 are operating, or if 1 and 3 and 5 are operating
Reliability of Networks (cont.)
- An Observation:
- Since there are 5 edges and each can be working or not,
there are \(2^5 = 32\) realizations to consider
- The System Reliability:
- Determine the probability of each realization
- Add the probabilities of the realizations that contain a path
Reliability of Networks - A Better Way
- Minimal Paths:
- A minimal set of components that by functioning ensure the
function of the system
- Minimal Cuts:
- A minimal set of components that by failing ensure the
failure of the system
- Finding the Reliability using Minmal Paths:
- The system will operate if all of the components
in at least one of the minimal paths operate
- Finding the Reliability using Minmal Cuts:
- The system will fail if and only if all the components in at
least one of the minmal cuts fail
Dynamic Software Reliability Models
- Objective:
- Predict the failure rate as a function of the number of
defects/faults in the system
- Determine the amount of testing time (and subsequent debugging)
required to reduce the failure rate to a given threshold
- The Process being Modeled:
- The software initially has an unknown number of defects/faults
- It is tested for some amount of time during which failures
occur
- When a failure occurs the defect/fault is fixed (which is
assumed to require no time for simplicity) and no new
defects/faults are introduced
Dynamic Software Reliability Models (cont.)
- Notation:
- \(N(t)\) denotes the number of defects/faults
at time \(t\)
- \(\lambda(t)\) denotes the failure rate at time
\(t\)
- \(c\) denotes a constant
- \(M(t) = N(0) - N(t)\) denotes the number of
defects/faults found
(and corrected) in the interval \([0, t]\)
- An Important Caveat:
- The accuracy of these models is not known
The Jelinski-Moranda Model
- Assumptions:
- The failure rate is described by a Poisson process that
varies with time, specifically,
\(\lambda(t) = c N(t)\)
- The testing time between failures is exponentially
distributed
- The Model:
- \(R(t) = e^{-\lambda(0) t} = e^{-cN(0) t}\)
- Given a failure at time \(\tau\), the probability that the
interval \([\tau, \tau+t]\) will be failure free is
\(R(t|\tau) = e^{-cN(\tau) t}\)
- Criticism:
- It assumes "all faults are created equal" (i.e., all faults
contribute equally to the failure rate)
The Jelinski-Moranda Model (cont.)
- An Example:
- \(N(0) = 40\)
- \(c = 0.025\)
- What We Want to Know:
- The reliability (i.e., the probability that the system
will not have a failure) in the first day of testing
- The reliability (i.e., the probability that the system
will not have a failure) in the first three days of testing
- Applying the Model:
- \(R(1) = e^{-cN(0) \cdot 1} = e^{-0.025 \cdot 40 \cdot 1}
= 0.368\)
- \(R(3) = e^{-cN(0) \cdot 3} = e^{-0.025 \cdot 40 \cdot 3}
= 0.050\)
The Musa-Okumoto Model
- Assumptions:
- \(N(0) = \infty\)
- \(\lambda(0)\) is known and finite
- It is exponentially more difficult to find/cause failures
over time, specifically
\(\lambda(t) = \lambda(0) e^{-c E[M(t)]}\)
- Some Math (You Don't Need to Know):
- The Differential Equation:
- \(\frac{dE[M(t)]}{dt} = \lambda(0) e^{-c E[M(t)]}\)
- The Solution:
- \(E[M(t)] = \frac{\ln(\lambda(0)ct + 1)}{c}\)
- \(\lambda(t) = \frac{\lambda(0)}{\lambda(0)ct + 1}\)
- So:
- \(R(t) = e^{-\int_0^t \lambda(x)dx} = e^{-E[M(t)]}\)
- \(R(t|\tau) = e^{-\int_{\tau}^{\tau+t} \lambda(x)dx} =
e^{-E[M(\tau+t)]+E[M(\tau)]}\)
- The Result:
- \(R(t) = (1 + \lambda(0) c t)^{-\frac{1}{c}}\)
- \(R(t|\tau) = \left( 1 + \frac{\lambda(0)ct}{1+\lambda(0)c\tau} \right)^{-\frac{1}{c}}\)
The Musa-Okumoto Model (cont.)
- An Example:
- \(\lambda(0) = 1\)
- \(c = 0.025\)
- What We Want to Know:
- The reliability (i.e., the probability that the system
will not have a failure) in the first day of testing
- The reliability (i.e., the probability that the system
will not have a failure) in the first three days of testing
- Applying the Model:
- \(R(1) = (1 + \lambda(0) c \cdot 1)^{-\frac{1}{c}}
= (1 + 1 \cdot 0.025 \cdot 1)^{-\frac{1}{0.025}} = 0.372\)
- \(R(3) = (1 + \lambda(0) c \cdot 3)^{-\frac{1}{c}}
= (1 + 1 \cdot 0.025 \cdot 3)^{-\frac{1}{0.025}} = 0.055\)