DEPENDABILITY MODELLING AND EVALUATION

Contents (preliminary)

Audience
Preparatory meeting
Registration
Overview of the seminar
Instructor
Assistant
Literature

Audience

This seminar addresses Master or Bachelor students in Computer Science.


Preparatory meeting

There will be a preparatory meeting on April 14 at 17:30 in E 1 3, room 528.

Everyone interested in this seminar should attend the meeting.


Registration

If you want to participate in the Seminar, please apply at our Course Management System. You may have to sign up for a student account first. For questions or comments please contact the teaching assistant.


Overview of the seminar

In this seminar, the modelling and evaluation of dependable systems is discussed. As an introduction, we copy a paragraph from the book:

    Dependability: basic concepts and terminology : in English, French, German, Italian and Japanese / J. C. Laprie

    (ed.). – Wien : Springer, 1992. – (Dependable computing and fault-tolerant systems ; 5)

Dependability is defined as the trustworthines of a computer system such that reliance can justifiably be placed on the service it delivers.

“Dependable” has several aspects:


with respect to the readiness for usage, dependable means available;
with respect to the continuity of service, dependable means reliable;
with respect to the avoidance of catastrophic consequences on the environment, dependable means safe;
with respect to the prevention of unauthorized access and/or handling of information, dependable means secure.

To evaluate the dependability of a system we need to first create a model of the system. This model of course has to approximate the real system. But we must also be able to analyze the model to find out the dependability of the system. In this seminar we will discuss a number of different formalisms used to model dependable systems. We have divided the formalisms into three categories. Suggest reading material for the different topics is listed here.


Dependability specific models focus on modeling structures and phenomena that often appear in dependable models, such as the use of spare components and the propagation of faults through a system. The advantage of dependability specific models is that they are usually easy to use and compositional. Models are built by connecting predefined building blocks. The disadvantage is then that we are restricted to whatever building blocks are provided to us. Also dependability specific models can usually not be analyzed directly. Instead they are often transformed to a low-level mathematical model. Examples of dependability specific formalisms are:


Fault trees (FT): A simple failure specification method based on boolean logic.
Reliability Block Diagrams (RBD): A simple structure-based reliability specification method.
Dynamic fault trees (DFT): An extension to FTs which introduces dynamic spare management, functional dependencies and fault-ordering.
State-Event fault trees (SEFT): Another extension to FTs based on state charts.
Dynamic reliability block diagrams (DRBD): An extension to RBDs which introduces the concept of dependency between system components.
OpenSESAME A dependability modeling environment supporting inter-component dependencies.

Low-level models describe the behavior of systems in great detail. They are usually based on automata theory and Markovian stochastics. The advantage of this is that these models are usually very expressive and can be readily analyzed. The disadvantage is that it can be difficult to create a low-level model of a large system because the model will also be very large. A number of low-level formalisms are given below:


Continuous-time Markov chains (CTMC): A stochastic model based on labelled transition systems and exponential distributions.
Generalized stochastic petri-nets (GSPN): A stochastic extension of petri-nets.
Stochastic activity networks (SAN): A variation on stochastic petri-nets, which is geared more towards dependability modeling.
Stochastic process algebra (SPA): A process algebra with stochastic processes.
Interactive Markov chains (IMC): A compositional stochastic extension to labelled transition systems.

Architectural approaches focus on the structure of the system being described. The idea is to start with a very abstract view of the system and then to refome this view to lower levels of abstraction. Analysis of architectural models is based on the one-model-multiple-analysis idea. The goal is to have a single model of a system on which we can perform many different types of analysis. The advantage of architectural models that they are usually very well structured and can be used in sophisticated software/hardware development methods. The disadvantage is that it is often quite difficult to analyze architectural models, which is also very true for the dependability aspects of such models. Below are listed a few architectural methodologies which allow the specification of dependability features:


System AVailability Estimator (SAVE): A dependability analysis tool which uses also uses architectural models to describe systems.
Unified Modeling Language (UML): A language that encompasses a great many aspects of computer systems. UML contains meta-languages which allow new (dependability) aspects to be added to existing models.
Architecture Analysis and Design Language (AADL): Another very broad architectural modeling language. A recent addition to AADL is the Error Annex which allows the modeling of dependability aspects.

Instructor

Holger Hermanns

 


Assistant

Pepijn Crouzen


Literature

Here, you will find some proposed literature for the seminar.

You have to use at least one source in addition to the ones proposed by us. If you find some proposal is not sensible, please consult with your teacher.


RBD: Rausand, M., Hoyland, A.: System Reliability Theory: Models, Statistical Methods, and Applications. 3rd edn. Wiley-IEEE (2003)
FT: W. Vesely, Fault Tree Handbook with Aerospace Applications, NASA (available here)
Extended FT: K. Buchacker, Modelling with extended fault trees (available here)
DFT: J.B. Dugan and S.J. Bavuso and M.A. Boyd, Dynamic Fault Tree models for Fault-Tolerant Computer Systems, IEEE transactions on reliability, volume 41, issue 3, 1992 (available on request)
DRBD: S. Distefano and A. Puliafito, Modeling Dependability of Dynamic Computing Systems, Third International Conference on Intelligent Computing (LNCS 4682), 2007
SEFT: B. Kaiser and C. Gramlich, State-Event-Fault-Trees - A Safety Analysis Model for Software Controlled Systems, SAFECOMP 2004 (LNCS 3219), 2004
OpenSESAME: K. Lampka and M. Siegle and M. Walter, An Easy-to-Use, Efficient Tool-Chain to Analyze the Availability of Telecommunication Equipment, FMICS 2006 (LNCS 4346)
CTMC: B. Haverkort, Markovian Models for Performance and Dependability Evaluation, LNCS 2090, 2001
SPA: J. Hillston and M. Ribaudo. Stochastic process algebras: a new approach to performance modeling. In K. Bagchi and G. Zobrist, editors, Modeling and Simulation of Advanced Computer Systems. Gordon Breach, 1998 (available here)
GSPN: M. Ajmone Marsan, G. Balbo, G. Conte, S. Donatelli and G. Franceschinis, Modelling with Generalized Stochastic Petri Nets, Wiley Series in Parallel Computing, 1995 (available here)
SAN: William H. Sanders and John F. Meyer, Stochastic Activity Networks: Formal Definitions and Concepts, Lecture Notes in Computer Science, Volume 2090, 2001
IMC: E. Brinksma and H. Hermanns, Process Algebra and Markov Chains, LNCS 2090, 2001
AADL: A.-E. Rugina, System Dependability Evaluation using AADL, Available here.
SAVE: A. Goyal, Estimating System Availability and Reliability, Proceedings of the 21st conference on Winter simulation (WSC), 1989
UML: I. Majzik and A. Pataricza and A. Bondavalli, Stochastic Dependability Analysis of System Architecture Based on UML Models, Architecting Dependable Systems (LNCS 2677), 2003