SURF-2

A TOOL FOR DEPENDABILITY EVALUATION
BASED ON MARKOV CHAINS
AND STOCHASTIC PETRI NETS

Version Française

Table of contents:

• ABSTRACT.
• Theoretical Background.
  • Model construction.
  • Model Mathematical processing.
• The Objects.
  • Generalized Stochastics Petri Nets.
  • Markov Chains.
  • Assigned Models.
  • Model Folders.
• The Tools.
  • Tools-Objects relationships.
  • To launch Tools.
  • Model Editors.
    • Petri Net Editor.
    • Markov Chain Editor.
  • Assigned Model Editor.
  • Model Folder Editor.
  • Results Editor.
• References.

ABSTRACT.

SURF-2 is a dependability evaluation tool for hardware and software systems, based on strict construction, validation and numerical resolution of Markov models.

System behaviour is modelized by either a Markov Chain or a Generalized Stochastic Petri Net (GSPN).

SURF-2 makes the comparison of dependability of various system architectures easy.

Reward structures can be added to the behavioural model and permit to get combined measures of dependability, performance or cost.

Table of contents.

THEORETICAL BACKGROUND.

Quantitative evaluation of system dependability can be divided in 2 steps:

1. Construction of the model describing the behaviour of the studied system based on elementary stochastic processes corresponding to the behaviour of the system components and of their interactions.
2. Mathematical Processing of the model to get analytics expressions or numerical values of the system dependability measures.

Table of contents.

Model construction.

SURF-2allows 2 types of modelization:

• Generalised Stochastic Petri Nets (i.e. GSPN), (see [Florin 85] for a description of GSPN). By computing marking invariants and firing invariants, user can validate his model.
• Markov Chains.

Theoretical Background. Table of contents.

Mathematical Processing.

It is fully automatic.

Dependability measures are obtained from the processing of the Markov Chain.

The transformation of the GSPN into a Markov chain in continuous time is based on the markings which sensibilize timed transitions:

1. Dimension variables assignment of a Generic GSPN.
   
2. Getting the symbolic Markov Chain.
   

Theoretical Background.Table of contents.

The Objects.

The tools provided by SURF-2 allow the creation and update of following objects:

• GSPNs,
• Markov Chains,
• Assigned Models,
• Model Folders.

Table of contents.

GSPNs and Markov Chains

A GSPN or a Markov Chain modelizes the behaviour of a system as perceived by the user under the following form:

• a graph,
• an initial probability vector of the Markov chain or of the underlying Markov chain in case of GSPN,
• one or several partitions: a partition defines the carhacteristics of a system necessary to compute the dependability measures. It is made of:
  • a class of failure states named "IMPROPER",
  • a class of dangerous states named "CATASTROPHIC".

  These two state classes allow the definition of most of the dependability measures, "CATASTROPHIC" class being used for safety measures. For a same model, it is possible to define several partitions in order to analyze various failure cases.

Model parameters can be numerical or symbolic expressions. A symbolic parameter is a local variable which is viewable only in the model wherein it has been defined. The combined use of symbolic parameters and the definition of several partitions for a same model permits to build generic models which can be stored in the SURF-2 database in order to be reused in other models.

Objets.Table of contents.

Assigned Model

An assigned model corresponds to the assignment of a value to each model parameter. This value can be a numerical value or a global value; in the latter, it can be common to different models. This global value concept is similar to the extern variable notion used in programming languages. Model genericity and the possibility to define several assigned models for a given model offer flexibility of modelization and allows to study the sensibility of a measure to different parameters.

Objects.Table of contents.

Model Folder

The modelization of several architectural solutions for comparative evaluation, needs the simultaneous evaluation of a dependability measure common to different solutions or to various sytem configurations. This is the role of Model Folder.

A Model Folder includes:

• the measure to compute,
• a set of assigned models involved in the computation,
• for each assigned model, a partition of the associated model according to the selected measure.

The assignment of a value (or of a set of numerical values in case of study of sensibility) to each global value is made at this step.

Figure below shows two examples of very simple use of global values to make comparative studies of architectures.

Other main objects of the databased managed by the supervisor of the application are Intermediate Results and Computation Results of a measure. Intermediate Results come from the processing of a Petri Net whose numerical and dimension variables have been assigned. That is:

• the marking graph,
• the equivalent Markov Chain under a text form,
• the list of marking and firing invariants,
• the possible conflicts for random selectors in case of transient markings which sensibilize several instantaneous transitions.

Computing results, for a given measure, are shown under numeric or graphic form and can be printed out in Postscript.

Objects.Table of contents.

The Tools.

Tools-Objects Relationships

To start Tools

Model Editors

Petri Net Editor

Markov Chain Editor

Assigned Model Editor

Model Folder Editor

Results Editor

Table of contents.

Tools-Objects Relationships

As shown below, SURF-2 provides a set of tools permitting the creation and update of objects:

ToolsTable of contents.

To launch tools

When SURF-2 is launched the window below appears:

When the cursor moves on MODEL command, the following menu is shown:

Then, the user can create a new Markov Chain (CREATE) or update an existing one (OPEN).

ToolsTable of contents.

Model Editors.

The Petri Net Editor and Markov Chain Editor are very similar. When an editor is started, following windows can be open:

an edit window

allowing to read, save and edit the selected model,

two working windows

allowing to read any model and to edit it but without saving.

Select and Copy functions allow to exchange components between windows. Working windows allow for instance:

• to load a "model" previously built which does not contains a consistent model but a set of "patterns" (i.e. "patterns" library),
• to save locally during model construction,
• . . .

When a Model Editor is started, one of the following window appears:

ou

ToolsTable of contents.

Petri Net Editor

Its aim is the creation, update and validation of the Petri Net, of the Partitions and of the Invariants of the model.

The Edit window looks like this:

.

PART command opens the Edit Partition window.

INV command opens the Edit Invariants window.

VALIDATION & SAVE command allows to save and validate the open model.

Validation checks the consistency of:

• Petri Net,
• expressions associated with places, transitions and edges of the Petri Net,
• partitions,
• invariants.

Markov Chain Editor.

Its aim is the creation, update and validation of the Markov chain and corresponding Partitions.

Edit Window looks like this:

.

PART command opens the Edit Partition window.

VALIDATION & SAVE command allows to save and validate the open model.

Validation checks the consistency of:

• Markov Chain,
• expressions associated with states and edges of the Markov Chain,
• partitions.

ToolsTable of contents.

Assigned Model Editor

Its aim is the creation or update of all the values of the parameters of the corresponding model:

ToolsTable of contents.

Model Folder Editor

• It allows to select a set of assigned models,

  

• to assign numerical values to global values,

  

• to select the measure.

  

ToolsTable of contents.

Results Editor

This tool provides to the user a powerful and flexible way to display results. User can select a subset of viewable results under the form of a set of curves.

ToolsTable of contents.

Table of contents.

REFERENCES .

SURF-2 tool

[Bachman 96]

SURF-2 User Guide

[Béounes 93]

C. Béounes et al., "SURF-2: A Program for Dependability Evaluation of Complex Hardware and Software Systems", in 23rd Int. Symp. on Fault-Tolerant Computing, Toulouse(France), pp. 668-673, 1993.

SURF-2 Applications

[Kanoun 96]

K. Kanoun and M. Borrel, "Dependability of Fault-tolerant Systems Explicit Modeling of the Interactions Between Hardware and Software Components", IEEE International Computer Performance and Dependability Symposium, (Urbana-Champaign, IL, USA), pp. , 1996.

[Kanoun 96]

K. Kanoun, M. Borrel, T. Moreteveille and A. Peytavin, "Modeling the Dependability of CAUTRA, a Subset of the French Air Traffic Control System", in 26th Int. Symp. Fault-Tolerant Computing (FTCS-26), (Sendai, Japan), pp. LAAS-Report,95-515.

Other Infomation

[Cox 68]

D.R. Cox et H.D. Miller, The Theory of Stochastic Proceses, Methuen, Londres, 1968.

[Howard 71]

R.A. Howard, Dynamic Probabilistic Systems, vol.II, Wiley, New-York, USA, 1971.

[Johnson 88]

A.M. Johnson Jr et M. Malek, "Survey of Software Tools for Evaluating Reliability, Availability and Serviceability", ACM Comp. Surveys, 20 (4), pp.227-269, Déc. 1988.

[Florin 85]

G. Florin et S. Natkin, "les réseaux de Petri Stochastiques", TSI. vol. 4, no 1, Fév. 1985.

[ Laprie 75]

J.-C. Laprie, "Prévision de la sureté de fonctionnement et architectures de structures numériques temps réelréparables", Doctorat d'Etat, Univ. Paul Sabatier, Toulouse, 1975.

Table of contents.

SURF-2 Main Page

How to get SURF-2