1

Spécification d’un modèle de protocole : Promela

Azza Ouled Zaid

Institut Supérieur d’Informatique

2ème année Cycle Ingénieur

2

Analyse/Vérification des modèles

Dans la conception des systèmes distribués, les protocoles de communication, les applications client-serveur, etc, on se trouve confronter par des erreurs non détectées dans les phases de la conception, codage, compilation et «debugging».

De telles erreurs ont des effets catastrophiques en tant que sécurité et économique en même temps, d’où la nécessité extrêmement importante de l’analyse et vérifications des modèles.

3

Qu'est ce que la vérification ?

La vérification est l'opération qui, dans la pratique, tente de s'assurer qu'une implémentation est compatible avec la spécification

Specification(What we want)

Implementation(What we get)

Desin verification

4

Différents types d’erreurs

Deadlock : état accessible non désirable où tous les processus sont bloqués. Il s'agit des états autres que ceux marqués du label ``end''.

Non-progress cycles : désignent des cycles passant par aucun état marqué par le label ``progress''.

Livelocks : désignent des cycles passant par au moins un état marqué par le label ``accept'‘.

Violations de contraintes: Capacité maximale des files: Si la capacité maximum d’une file

est atteinte et d’autres messages arrivent, qu’est-ce qu’on doit faire avec celles-là

Violations des limites de vecteurs: affectation des valeurs non acceptées par les vecteurs

5

Différents types d’erreurs (suite)

Le calcul de la vitesse: L’estimation de la vitesse de l’application peut être différente de la vitesse réelle de l’application implantée (en action).

Exactitude logique Performance temps-réel : parfois, l’application perd de son

exactitude logique ou bien se soumet à des dégradations de sa performance en temps réel après un intervalle de temps.

6

Analyse des modèles , Model Checking

Est-ce que le modèle M vérifie la propriété φ dans tous les cas après l’explosion d’états : oui ou non, si non, tracer l’erreur.

byte n;proctype Aap() { do :: n++ :: noot!MIES od}

Modèle M

[] (n<3)

Propriété

Model Checker

Espace d’états

NON,+ tracerjusqu’àl’erreur

|M

Explosion d’états: l’espace d’états grandit exponentiellement mais

sera toujours un nombre fini.

OUI,la propriété est satisfaite

7

Analyse moderne et analyse classique

Dans l’industrie informatique on distingue deux approches différentes d’analyse de modèles : Approche traditionnelle :

• Dans le processus de conception, on crée un modèle abstrait du processus avant de commencer l’implémentation.

• L’analyse est faite sur ce modèle.• L’implémentation est obtenue à partir du modèle par un

procédé de raffinement.

Approche dite ‘moderne’ :• Le modèle est obtenu à partir de l’implémentation par un

procédé d’abstraction qui est automatisable.

8

Approches Classique et “Moderne”

To cope with the state space explosion.

ModelChecker

AbstractVerification Model

(initial) Design

Implementation

(manual)abstractions

refinementtechniques

Modern Approach

abstraction techniques

AbstractVerification Model

Implementation

C, Java

Abstraction is the key activityin both approaches.

Classic Approach

9

Promela/SPIN: un système pour l’analyse des modèles

Promela/SPIN est un système développé à partir du début des années 1990 par Gerhard Holzmann, un chercheur d’AT&T Labs

Il est un des analyseurs de modèles les plus connus et efficaces

10

Promela

Protocol/Process Meta Language Influencé par C

Mais il est un langage pour la spécification de modèles

Pas un langage d’implémentation

De compréhension facile pour les développeurs

Admet la communication Par variables globales partagées Synchrone (rendez-vous), directe Asynchrone, par canaux de communication fifo

11

Promela

Un programme Promela est une liste de déclarations de processus, de canaux et des variables

12

Atouts de ce système

Automatique, sans intervention humaine Après la définition du problème

Implantation très efficace en C Interface conviviale Excellent appui Il combine un grand nombre de connaissances

sur le sujet Plusieurs chercheurs chevronnés ont participé à

son développement

13

SPIN

Spin est un outil pour la vérification et la simulation des systèmes concurrents, en particulier les protocoles de communication.

Pour être étudié, un système est d'abord décrit en Promela, le langage de modélisation de Spin.

SPIN est l’analyseur (model checker) d’un modèle spécifié

14

Simulation en Promela/SPIN

La simulation d'une spécification Promela est réalisée par l'outil SPIN.

Elle permet d'observer pas à pas le fonctionnement d'un protocole, et de contrôler l'absence de comportement indésirable.

La simulation n'est pas exhaustive dans la mesure ou la séquence à exécuter est choisie de manière interactive ou bien aléatoirement.

Les seuls critères vérifiés au cours de la simulation sont les assertions et les états terminaux invalides. En cas d'erreur, la simulation est arrêtée et l'état des processus est affiché (variables, files, registres d'instructions, ...).

15

Déclaration de variables :

On indique le type (un des bit, byte, short, or int), le nom de la variable et optionnellement sa valeur

initiale.

bool b1 = false, b2 = false; bit k = 0; Les variables de type tableau sont déclarées

comme en C, par exemple : bit porteouverte[3];

16

Déclaration de canaux  On l'introduit par le mot clé chan, suivi du nom du canal et

optionnellement de la longueur du fifo et du type des messages qui circulent.

Par exemple :

chan Ouvreporte=[0] of {byte, bit}, Transfert=[2] of {bit, short, chan};

ouvreporte est un canal synchrone, car sa longueur est 0, ce qui correspond à un rendez-vous ; sur ce canal circulent des messages ayant une partie byte et une

partie bit.

Transfert est un canal asynchrone, car il peut stocker (au plus) deux messages.

17

Déclaration de processus : La forme la plus simple de déclaration de processus est :

proctype nom ( paramètres_formels ) { instructions } Un processus est instancié en utilisant l'instruction run :

run nom ( paramètres_actuels ) Par exemple :

proctype P (bit i) { ... } proctype porte (byte i) { ... } proctype ascenseur () { ... }

18

Opérations sur les canaux 

Sur un canal on peut • envoyer (opération ``!'')

• ou recevoir (opération ``?'') des messages.

Par exemple : ouvreporte!i,0; ouvreporte?i,1; ouvreporte?eval(etage),1

• La fonction ``eval'' force l'égalité des valeurs reçues avec etage, la variable etage n'est pas changée.

19

Expressions 

Un expression peut être utilisée comme une instruction si elle ne fait pas des effet de bord (opérations ``--'' et ``++'' de C).

Dans ce cas, elle est exécutable quand sa valeur devient vraie (par le changement des valeurs des variables partagées).

Par exemple : (a == b); est équivalent à :

while (a != b) skip;

20

Instruction ``init'' 

L'exécution du système commence par le processus init (c'est le main de Promela).

Par exemple :

init { run porte(1); run porte(2); run porte(3); run

ascenseur() }

21

Instruction ``atomic''

 L'exécution d'une séquence d'instructions préfixée par ``atomic'' peut être rendue indivisible, c'est-à-dire sans l'entrelacement des actions des autres processus.

Par exemple : atomic { run porte(1); run porte(2);

run porte(3); run ascenseur() }

22

Instruction ``if''

 Une branche de l'instruction ``if'' est exécutable si la première instruction de la branche, appelée aussi sa garde, est vraie.

L'instruction ``if'' bloque jusque à ce qu'une branche devient exécutable. Si plusieurs branches sont exécutables, l'une est choisie aléatoirement (non-déterminisme).

L'exemple suivant incrémente ou décrémente la valeur de count une fois. if

:: count = count + 1 :: count = count - 1

fi

23

Instruction ``do'' 

Similaire à l'instruction ``if'', sauf que l'instruction est exécutée et puis la sélection est répétée jusqu’à l'exécution d'une instruction ``break''. proctype ascenseur () {

byte etage = 1;

do

:: (etage != 3) -> etage++

:: (etage != 1) -> etage--

:: ouvreporte!etage,1; ouvreporte?eval(etage),0

od

}

24

Modèle Promela

Un modèle Promela consiste de :

Déclaration des types

Déclaration des canaux

Déclaration des variables globales

Déclaration des processus

[processus init]behaviour of the processes:local variables + statements

- simple vars- structured vars- vars can be accessed by all processes

initialises variables andstarts processes

chan ch = [dim] of {type, …} asynchronous: dim > 0 rendez-vous: dim == 0

mtype, constants,typedefs (records)

25

mtype = {REQ,ACK};typedef Msg { byte a[2]; mtype tp;} ;chan toR = [1] of {Msg};bool flag;

proctype Sender() { Msg m; ... m.a[0]=2; m.a[1]=7; m.tp = REQ; toR ! m;}

proctype Receiver(byte n) { Msg m; ... toR ? m; }

init { run Sender(); run Receiver(2); }

Modèle Promela

A Promela model corresponds to a (usually very large, but) finite transition system, so

no unbounded data no unbounded channels no unbounded processes no unbounded process creation

channel declaration

creates processes

global variable

local variable

message types (constants)

“record” declaration

Example of a Promela model

Inputs/outputs

26

Processus (1)

Un type de processus (proctype) consiste de Un nom Une liste de paramètres formelles Déclaration des variables locales Un corps

proctype Sender(chan in; chan out) { bit sndB, rcvB; do :: out ! MSG, sndB -> in ? ACK, rcvB; if :: sndB == rcvB -> sndB = 1-sndB :: else -> skip fi od}

name

local variables

body

formal parameters

The body consist of a sequence of statements.

27

Formulation du problème (instructions)

Le corps d’un processus consiste d’une séquence d’instructions ou spécifications. Une instruction est ou bien exécutable: la formulation peut être exécutée immédiatement bloquée : la formulation ne peut pas être exécutée.

Une affectation est toujours exécutable.Une expression est aussi une instruction; elle est

exécutable si elle est évaluée à une valeur non nulle.2 < 3 toujours exécutablex < 27 exécutable si la valeur de x est inferieure à 273 + x exécutable si x n’est pas égale à –3

executable/blockeddepends on the global

state of the system.

28

Formulations du problème (2)

skip est toujours exécutable. “ne fait rien”, elle change uniquement le compteur du

processusrun est uniquement exécutable si un nouveau

processus peut être crée (Rappel : le nombre des processus est limité).

int x;proctype Aap() { int y=1; skip; run Noot(); x=2; x>2 && y==1; skip;}

Can only become executable if some other process makes x greater than 2.

Executable if Noot can be created…

Statements are separated by a semi-colon: “;”.

or by the equivalent “->”

29

Formulations du problème (3)

assert(<expr>); Assert est toujours executable. Si <expr> est evaluée à zéro, SPIN arrêtera avec un message d’erreur,

comme l’ <expr> “a été violée”. Assert est souvent utilisée avec les modèles Promela, pour vérifier si

dans un état certaines propriétés sont valides ou pas.

proctype monitor() { assert(n <= 3);}

proctype receiver() { byte msg; ... toReceiver ? msg; assert(msg != ERROR); ...}

We will later see that this is not the preferred way to check for invariance.

30

Sémantiques interactives Les processus Promela s’exécutent simultanément. Planification non-deterministe des processus. Les processus sont interactifs

exception: communication rendez-vous. Toutes les instructions sont atomic; chaque instruction

est exécutée sans interaction avec les autres processus.

Chaque processus peut avoir plusieurs actions différentes possibles activées à chaque point de l’exécution. Un seul choix est pris en compte, d’une manière non

déterministe.

31

Promela: exemple 1

Processus: ’’Hello World’’

    active proctype main ( )

    {

          printf(’’hello world\n’’)

    } 

Simulation run:

$ spin hello.pml

hello world

1 process created

$   

init {      printf(’’hello world\n”) } Vérification run:$ spin –a hello.pml$ gcc –o pan pan.c$ ./pan… depth reached 2, errors 0$  Pas de ;  

32

Vérification avec SPIN

SPIN génère avec l'option -a un analyseur d'un programme PROMELA sous la forme d'un programme c (pan.c).

Cet analyseur, une fois compilé et exécuté, explore tous les états accessibles du programme PROMELA.

Exemple : $ spin -a phil

$ cc -o pan pan.c

$ a.out

Si une erreur est détectée lors de l'analyse, une trace est sauvgardée dans le fichier pan.trail. Cette trace est visualisable avec spin en utilisant l'option -t.

Exemple : $ spin -t -p -g phil

33

Remarques Une seule valeur par message

qname?msg

plusieurs valeurs par message qname!expr1,expr2,expr3 qname?var1,var2,var3

Par convention, le premier champ du message et toujours utilisé pour spécifier le message

Une alternative pour les opérations d’émission et réception consiste à spécifier le type du message, suivi de la liste des champs du message

qname!expr1(expr2,expr3)

Optionnellement, certains arguments dans l’opération de réception peuvent être des constantes

qname?cons1,var2,cons2 La condition d’execution de cette opération est que toutes les valeurs affectées

à touts les champs de message spécifiées comme des constantes coïncident avec les valeurs du message qui sont à l’entête du canal

34

Remarques : initialisation des canaux chan a = [16] of { short }

Le canal peut stocker jusqu’à 16 messages du type short. chan c[3] = [4] of { byte }

Un vecteur de 3 canaux, chacun avec une capacité de 4 trames de message, chaque trame est constituée d’un champ de message de type byte.

Si le message contient plus qu’un champ, la déclaration sera:

chan qname = [16] of { byte, int, chan, byte } Un seul canal qui peut stocker jusqu’à16 messages,

Chaque message consiste de 4 champs

35

Promela: exemple

byte count;

proctype counter()

{ do

:: count = count + 1

:: count = count – 1

:: (count == 0) -> break

od

}

Cette boucle se termine que si count atteint zéro,

Pour terminer la boucle il faut modifier le code

proctype counter()

{ do

:: (count != 0) ->

if

:: count = count + 1

:: count = count – 1

fi

:: (count == 0) -> break

od

}

36

Promela: exemple

Proctype PGCD(int x, y)

{ do

:: (x > y) -> x = x – y

:: (x < y) -> y = y – x

:: (x == y) -> goto done

od;

done:

skip

}

37

Modélisation des timeouts

Timeout est une instruction prédéfinie abandonner l’attente d’une condition qui ne peut

plus se réaliser. Offre une sortie à partir d’un état bloqué. une condition prédéfinie artificielle qui devient vraie

que si les autres instructions dans le système distribué sont executables

Elle n’implique pas un intervalle de timeout mais une possibilité de timeout

Abstraction à partir de temporisateurcrucial pour la validation

38

Modélisation des timeouts

proctype watchdog(){ do

:: timeout -> guard!resetod

} Dans ce cas le timeout ne modélise pas l’erreur

causée par des timeouts prématurés dans un système distribué.

Si c’est nécessaire, cela peut être réalisé en redéfinissant le mot clé dans une macro#define timeout 1 /* activée tout le temps, delai arbitraire */

39

Promela: exemple 2

Objectif : formalisation du comportement de la couche inférieure

40

Promela: exemple 2 (suite)

Déclatration des type de messages

>> mtype = { data, control } /* data and acks */

Formalisation des canaux de messages entre A et B chan fromA = [N] of { byte, byte, bit }; /* data, udata, seqno */

chan toB = [N] of { byte, byte, bit }; /* data, udata, seqno */

chan fromB = [N] of { byte, bit }; /* control, seqno */

chan toA = [N] of { byte, bit }; /* control, seqno */

N est une constante qui spécifie la capacité du canal (dans ce cas N=1)

41

Modèle d’un canal idéal

proctype lower(chan fromA, toA, fromB, toB){ byte d; bit b; do :: fromA?data(d,b) -> toB!data(d,b) :: fromB?control(b) -> toA!control(b) od}

fromA?data(d,b) : une garde, l’opération de réception n’est exécutable que si un message du type demandé est inséré dans le canal fromA.

42

Exécutabilité en PROMELA

Chaque instruction est ou bien exécutable ou bien non exécutable.

Instructions de déclaration toujours exécutables Les conditions booléennes exécutables uniquement si elles sont vrais.

Toute instruction non exécutable peut bloquer l’exécution du processus.

Dans l’exemple précédant, l’état des canaux détermine l’une des deux gardes exécutables, à sélectionner par le processus

Si aucune garde n’est exécutable, le processus se bloque. Si les deux gardes sont exécutables, l’une d’entre elles sera sélectionnée

aléatoirement

43

Modèle d’un canal non idéal

1. proctype lower(chan fromA, toA, fromB, toB)2. { byte d; bit b;3. e4. do5. :: fromA?data(d,b) ->6. if7. :: toB!data(d,b) /* correct */8. :: toB!error /* distorted */9. fi10. :: fromB?control(b) ->11. if12. :: toA!control(b)13. :: toA!error14. fi15. od16. }

44

Modèle d’un canal non idéal

Pour modéliser la possibilité de perte de message, ajouter l’option skip skipskip est l’opération nulle de PROMELA. Toujours exécutable et sans effet.

La définition du processus lower donne une description du comportement du protocole utilisé à la couche inférieure, vérifiant les contraintes imposées par le concepteur du protocole.

Pour compléter la validation du protocole, il faut le combiner avec la déclaration des canaux et trouver une place ou un processus du type lower est instancié avec les canaux appropriés.

45

Modélisation de l’émetteur A1. proctype A(chan in, out)2. { byte mt; /* message de données */3. bit at; /* bit alterné */4. bit vr; /* bit de verificat° */5. e6. FETCH; /* chercher un nouv mess */7. out!data(mt,at); /* l’envoyer */8. do9. :: in?control(vr) -> /* attendre la réponse */10. if11. :: (vr == 1) -> /* emission correcte */12. FETCH; /* nouv message */13. at = 1-at /* complement à un */14. :: (vr == 0) -> /* envoyer erreur */15. skip /* ne pas chercher */16. fi;17. out!data(mt,at) 18. :: in?error(vr) -> /* recevoir erreur */19. out!data(mt,at) 20. od21. }

#define FETCH mt = (mt+1)%MAX

46

Modélisation du recepteur B1. proctype B(chan in, out)2. { byte mr; /* message de données */3. byte last_mr; /* nbr du dernier message sans erreur */4. bit ar; /* bit alterné */5. bit lar; /* ar du dernier message sans erreur */6. e7. do8. :: in?error(mr,ar) -> 9. out!control(0) 10. :: in?data(mr,ar) -> 11. out!control(1); 12. if 13. :: (ar == lar) -> 14. skip 15. :: (ar != lar) -> 16. ACCEPT; 17. lar = ar; 18. last_mr = mr19. fi20. od21. } #define ACCEPT assert(mr == (last_mr+1)%MAX)

47

Proctype: défini le comportement du processus,

Il ne spécifie pas le moment à partir duquel il va être

réalisé ou la façon avec laquelle il a été instancié

Chaque modèle de validation est défini par un processus initial (fonction main en C)

Modèle de l’exemple : déclare les canaux, instanciation de chacun des proctypes A, B, et lower

48

Modèle d’initiation : init1. #define N 22. #define MAX 83. #define FETCH mt = (mt+1)%MAX4. #define ACCEPT assert(mr == (last_mr+1)%MAX)5. e

6. mtype = { data, control, error };7. e

8. #include "lynch0.A "  9. #include "lynch0.B"10. #include "lynch0.C"11. e12. init {13. chan fromA = [N] of { byte, byte, bit };14. chan toB = [N] of { byte, byte, bit };15. chan fromB = [N] of { byte, bit };16. chan toA = [N] of { byte, bit };17. e18. atomic {19. run A(toA, fromA);20. run B(toB, fromB);21. run lower(fromA, toA, fromB, toB)22. }23. }

49

Simulation : SPIN

Utilisation par défaut SPIN : exécution aléatoire de la simulation du modèle de validation pas de vérification de la justesse

Les exceptions sont les erreurs non tolérées: blocage, réception non spécifiée, violation des

assertions. Dans ce cas l’exécution de la simulation

s’estompe si une violation d’assertion apparaisse

Il manque d’autres critères de justesse

50

Options disponibles Les principales options disponibles, entre autre pour la

simulation, sont les suivantes :

-p affiche les changements d'états des processus

-l affiche les valeurs des variables locales

-g affiche les valeurs des variables globales -r affiche les réceptions de messages -s affiche les émissions de messages -m indique qu'un message est perdu quand il est envoyé

dans un canal plein -t permet de consulter la trace qui conduit à une erreur

51

Conclusion

Description des règles de procédures d’un protocole avec le langage de spécification et modélisation PROMELA

Décrire les structures de description du comportement.

Dans ce qui va suivre nous allons étudier les structures du langage PROMELA, spécialement reliées au critère de justesse

Un langage de validation dispose de certaines structures non usuelles qui le rend plus adapté à la modélisation des systèmes distribués

Toutes les communications entre les processus prennent place ou bien à travers les messages ou les variables partagées

52

Conclusion

Chaque instruction en PROMELA peut potentiellement modéliser un délai (executable ou non)

L’interaction et la coordination entre les processus est la base du langage PROMELA

Pas de types de données abstraits mais quelques types de variables de base

Le modèle de validation est un niveau d’abstraction pour l’implémentation

L’abstraction maintien l’interaction d’un processus afin qu’il puisse être étudié d’une manière isolée