Rseaux & Protocoles

Le langage de spcification de protocole Promelaet le simulateur-vrificateur spin

Les premires sections de ce document dcrivent sommairement le langage Promela et loutil de simulation etde vrification spin. Un descriptif beaucoup plus complet (et en anglais) pourra tre trouv sur :http://cm.bell-labs.com/cm/cs/what/spin/index.html

Promela signifie Protocol Meta Language. Il sagit dun langage qui permet de modliser des systmes distri-bus, des processus qui se droulent en parallle et qui se communiquent travers des canaux.

Un modle de protocole crit en Promela peut tre simul et vrifi par le logiciel spin et son interface graphiquexspin. Ces logiciels permettent dtudier un protocole de faon exhaustive et de trouver toutes les possibilits derreurquil renferme, par exemple les deadlocks, les boucles etc.

Ainsi ni Promela ni spin ni xspin ne permettent de raliser des programmes de communication proprement dits.Mais lorsquun protocole de communication a t modlis sous Promela et quil a t prouv quil ne contient aucuneerreur, alors limplantation effective du protocole dans un programme sen dduit de faon assez directe.

1 Le langage Promela1.1 Les types de donnes

Les types de donnes sont dcrits dans le tableau suivant.Nom du type Equivalent C Gamme de valeurs

bit ou bool champ de bits {0, 1}byte unsigned char [0, 255]short short

[215 1, 215 1]int int

[231 1, 231 1]

bit et bool sont exactement synonymes et reprsentent un nombre qui ne peut prendre que les valeurs 0 et 1.On peut galement utiliser les tableaux, qui sont dfinis comme en C. Par exemple linstruction :

byte state[30];est une dclaration dun tableau appel state et compos de trente entiers positifs compris entre 0 et 255. Luti-

lisation de ces tableaux (la lecture de leur valeur et leur affectation) seffectue galement comme en C.Enfin le type channel nexiste pas dans le langage C. En Promela, ce type reprsente un canal de transmission. Il

sera prsent un peu plus loin.

1.2 ExcutabilitEn Promela toutes les instructions sont soit excutables, soit bloquantes. Certaines instructions sont toujours ex-

cutables, dautres sont toujours bloquantes, mais la plupart peuvent tre lun ou lautre en fonction des conditions. En

1

particulier, une instruction bloquante peut tre rendue excutable (et vice-versa) par certains vnements.Par exemple en C la squence :

while(a!=b); /* attend que a soit egal a b */a = a+1; /* ensuite augemente a de 1 */

bloque lexcution du programme si a est diffrent de b. Le programme ne peut reprendre son cours que lorsque asera devenu gal b.

En Promela, cette squence scrit simplement :(a==b); a=a+1;

Le sparateur -> est exactement quivalent ;. Il permet simplement, dans certains cas, de rendre lesprotocoles plus lisibles, notamment pour insister sur un enchanement causal. Par exemple la squence prcdentescrit aussi :

(a==b) -> a=a+1;ce qui peut tre interprt comme ds que a sera gal b, a sera incrment de 1.Les affectations, comme a=2; ou encore a=a+1; etc sont toujours excutables.Linstruction skip est une instruction toujours excutable, mais qui ne fait rien et ne rend aucune valeur.Les instructions 1; ou encore n; (o n reprsente un nombre non-nul) sont galement des instructions (qui ne

servent pas grand chose, certes) mais qui sont toujours excutables.0; est une autre instruction, tout aussi utile, mais qui nest jamais excutable.

1.3 Les processus1.3.1 Les types de processus

Le comportement de tous les processus est dfini par une dclaration proctype. Par exemple la dclarationsuivante dfinit un type de processus appel A avec une seule variable locale state.

proctype A(){

byte state;state = 3;

}La syntaxe est proche de celle des procdures dans les langages comme pascal ou C. Pourtant, comme nous le

verrons ces dfinitions ont un rle trs diffrent de celui des procdures.

1.3.2 Instanciation de processus

A limage du langage C et de la fonction principale main, tous les protocoles spcifis par Promela commencentpar lexcution dun processus principal appel init. En gnral, ce processus principal a pour rle de lancer desprocessus dont le comportement a t dfini par les dclarations proctype. Par exemple :

proctype A(){

byte state;state = 3;

}

init{

run A();}

lance lexcution dun processus de type A(). Mais init peut lancer autant de processus de type diffrent, ou demme type, ventuellement en leur donnant des arguments diffrents. Par exemple :

2

int b=3;

proctype A(int a){

byte x;x = a+b;

}

proctype B(int m){

byte y=0;(m==3) -> y=(y + b)%8;

}

init{

run A(2); run B(3); run B(5);}

Dans cette spcification, b est une variable globale, alors que x et y sont des variables locales chacun desprocessus.

Le processus init lance trois processus, lun de type A() et les deux autres de type B(). Ces processus ne sontpas excuts squentiellement, lun aprs lautre, mais en parallle. Le premier processus, de type A, affecte la sommea+b (cest dire 3+2=5) la variable locale x et ensuite se termine.

Le second processus, de type et le troisime processus, sont tous les deux de type B, mais sont lancs avec desparamtres diffrents. Chacun compare le paramtre dentre avec 3. Sil y a galit, alors la valeur de la variable yest augment de b modulo 8, et sil ny a pas galit, alors le processus reste bloqu. Le second processus est lancavec un paramtre dentre gal 3. Dans ce processus, la valeur de y est effectivement augment, et le processus setermine. En revanche le troisime processus est lanc avec un paramtre dentre de 5. Donc la condition (m==3)nest jamais excutable. Donc le troisime processus reste bloqu sur cette instruction, sans pouvoir tre dbloqu.

Le fait de lancer un processus de type A(), cest dire le fait dcrire run A() constitue une instanciation dece type de processus. Autrement dit, une dclaration proctype ne fait que dfinir le comportement dun type deprocessus. Il ne dfinit pas le processus lui-mme.

1.3.3 Processus concurrents

Tous les processus lancs par des instanciations run sexcutent non pas de manire squentielle (A puis B puis...) mais de manire concurrente. Par exemple, lanons trois processus A, B et C contenant chacun trois instructionsinstrA1, instrA2, instrA3, instrB1, etc.

Lorsque les processus sexcutent de manire squentielle, alors lordre dexcution des instructions est celuidonn dans le tableau suivant.

3

processus A processus B processus C

instrA1instrA2instrA3

instrB1instrB2instrB3

instrC1instrC2instrC3

Par contre, lorsque les processus sexcutent de faon concurrente, on ne connat pas a priori lordre dans lequelles instructions seront executes dans les diffrents processus. Lordre peut trs bien tre lordre squentiel, mais lesinstructions pourront aussi tre entrelacs plus ou moins rgulirement. Voici un exemple.

processus A processus B processus C

instrA1instrC1

instrA2instrB1instrB2instrB3

instrC2instrC3

instrA3

Il en rsulte que, de la mme manire que pour les systmes distribus, si on ntudie pas explicitement la syn-chronisation des processus, on pourra observer des rsultats alatoires. En voici un exemple.

byte state = 1;

proctype A(){ (state==1) -> state = state+1; }

proctype B(){ (state==1) -> state = state-1; }

init{ run A(); run B();}

state est une variable globale. Si A commence et termine avant B, alors la valeur de state ne sera plus de 1 et B restera ternellement bloqu

linstruction (state==1) qui ne deviendra jamais excutable. La valeur finale de state sera donc de 2. Si cest B qui commence et termine avant A, alors cest ce dernier qui restera bloqu et la valeur de state sera

de 0. Enfin si les deux processus excutent linstruction (state==1) avant de changer la valeur de state, alors

aucun des deux processus ne restera bloqu et la valeur de la variable state sera de 1.Ainsi on peut voir que malgr une syntaxe voisine, les dclarations proctype ne dfinissent pas des procdures

ou des fonctions comme en C ou en Pascal.

4

1.3.4 Squences atomiques

Le problme vu dans lexemple prcdent de tester-affecter est bien connu. Un des moyens de contrler ce typede problme en Promela est dutiliser les squences atomiques. En enfermant un ensemble dinstructions dans un blocprfix atomic, on peut sassurer que ces instructions seront excutes comme un tout indivisible, sans que dautresinstructions venant dautre processus sintercalent entre eux. Par exemple dans lexemple prcdent, on pourra crire :

byte state = 1;

proctype A(){ atomic

{ (state==1) -> state = state+1; }}

proctype B(){ atomic

{ (state==1) -> state = state-1; }}

init{ run A(); run B();}

Ainsi on peut sassurer que la valeur de state ne peut tre que 0 ou 2 et lun des processus restera bloqu.Attention ! Les squences atomiques ne rsolvent pas tous les problmes. En effet dans une squence atomique, toutesles instructions doivent tre excutables, sauf ventuellement la premire. Dans le cas, contraire, si une instructiondans la squence nest pas excutable, alors il sagira dun deadlock, car aucun autre processus ne pourra rendre cetteinstruction excutable et dbloquer la situation.

1.4 Transmission de messages1.4.1 La dfinition des canaux

Les canaux (channels) modlisent le transfert de donnes entre processus. On dfinit les canaux par des dcla-rations de ce type :

chan qname = [16] of {short}Ceci dfinit un canal qui peut contenir jusqu 16 messages de type short. Les canaux sont des types de donnes

comme les autres, dans le sens o on peut les passer en paramtre des processus.Chaque message peut avoir plus dun champ. Par exemple, dans le canal suivant :

chan qname = [16] of {byte, int, chan, byte}contient jusqu 16 message, chacun consistant en deux valeurs de 8 bits, une valeur de 32 bits et un nom de canal.

1.4.2 Lenvoi et la rception de messages

Linstructionqname!expr;

envoie la valeur de lexpression expr sur le canal que nous venons de crer. Plus prcisment, elle met expr lafin du canal.

qname?msg;reoit le message. Elle le retire du dbut du canal et lenregistre dans la variable msg. Les canaux transfrent les

messages dans lordre FIFO.Si plus dune seule valeur doit tre transfre dans un seul message, alors il faudra crire :

qname!expr1,expr2,expr3;qname?var1,var2,var3;

5

Lopration dmission nest excutable que lorsque le canal en question nest pas plein. De mme, lopration derception nest excutable que lorsque le canal en question nest pas vide.

Voici un exemple dans lequel le processus init lance deux processus A et B en leur donnant le mme canal enparamtre. Le processus A envoie lentier 123 au processus B qui lenregistre dans la variable x.

proctype A(chan q1){ q1!123; }

proctype B(chan q2){

int x;q2?x;

}

init{

chan q1 = [1] of {int};run A(q1); run B(q1);

}Enfin pour tester si un canal est vide ou non sans lire le message, on peut utiliser une instruction de type :qname?[var];

Une telle instruction rend 1 si le canal contient un message, et 0 dans les autres cas.Attention ! ! ! dans une squence de type :

qname?[var] -> qname?var;la seconde instruction nest pas ncessairement excutable. En effet entre lexcution de la premire instruction et

celle de la seconde, dautres instructions appartenant dautres processus peuvent tre excutes, et notamment cesinstructions peuvent vider le canal qname. Il nest pas non plus possible de recourir aux squences atomiques, cardans les squences atomiques, hormis la premire instruction toutes les instructions doivent toujours tre excutable.Or, la lecture dans un canal nest pas toujours excutable ce qui interdit lemploi de squences atomiques.

1.4.3 Synchronisation

Soit un canal de taille nulle :chan qname = [0] of {byte};

Avec un tel canal, les messages peuvent passer mais ils ne peuvent pas tre stocks. La lecture dans un tel canalest toujours bloquante, jusqu ce que, de lautre ct du canal un, autre processus soit prt crire quelque chose.De mme lcriture est bloquante jusqu ce que, de lautre ct du canal, un autre processus soit prt y lire quelquechose.

Ainsi, en utilisant des canaux de taille nulle un processus peut donner rendez-vous un autre processus unpoint prcis de leur volution respective, de manire pouvoir partir de ce point ensemble. Autrement dit, les canauxde taille nulle permettent de synchroniser plusieurs processus.

1.5 Flux de contrle1.5.1 La slection ou linstruction if

if:: (a!=b) -> option1;:: (a==b) -> option2;fi;

Si a est gal b, cest loption option2 qui sera excute et sinon, cest loption option1 qui sera excute.De manire plus gnrale, dans une instruction if on pourra avoir autant doptions quon le dsire :

6

if:: instr1 -> option1;:: instr2 -> option2;

...

:: instrN -> optionN;fi;

Au plus une option peut tre choisie. Si parmi les premires instructions instr1, instr2 ..., instrN : aucune instruction nest excutable, alors linstruction if dans son ensemble ne sera pas excutable. une seule instrI est excutable, alors toute les instructions contenues dans optionI seront excuts, mais

les autres options ne le seront pas. plusieurs voire toutes les instructions sont excutables, alors une des lignes est choisie au hasard et loption

correspondante est excute.

1.5.2 La rptition ou linstruction do

do:: count = count + 1;:: count = count - 1;:: (count == 0) -> break;od;

Ici, aussi longtemps que le processus naura pas rencontr un break (ou un goto comme on le verra) il rpterales actions dcrites ci-dessus pour linstruction if. Dans lexemple ci-dessus, les deux premires instructions sonttoujours excutables (ce sont des affectations) La troisime ne lest que si count est nul. Ainsi, la variable countsera alatoirement incrment ou dcrment au cours des cycles de do. La boucle ne pourra sarrter que lorsquecount est nul. Mais mme sil est nul, larrt ne sera pas ncessaire, puisque les deux autres instructions restenttoujours excutables.

1.5.3 La pseudo-instruction else

Aussi bien pour linstruction if que pour linstruction do, on peut utiliser une option spciale else. Elle nestexcutable que lorsque toutes les autres options ne le sont pas. Lexcution de linstruction else elle-mme na aucuneffet.

1.5.4 Le saut conditionnel ou linstruction goto

Cest un autre moyen de sortir dune boucle. Voici un exemple :proctype PGCD(int x,y)

{do:: (x>y) -> x = x-y:: (x x = y-x:: (x==y) -> goto doneod;

done:skip

}

1.5.5 La temporisation

Dans Promela, il ny a pas de notion de temps. On ne considre quune succession dtats. Donc il nest paspossible de raliser un vritable temporisateur. Mais il nest pas non plus souhaitable davoir recours un tel tempo-risateur, car il serait trs difficile de prouver la validit dun protocole avec un tel lment.

7

Dans Promela, on a recours une instruction spciale appele timeout qui nest excutable que lorsquon estarriv dans un tat o tous les processus du systme distribu sont bloqus. Par exemple :

do:: qname?var;:: timeout -> break;od

Dans la squence ci-dessus, si rien ne peut tre lu dans le canal qname et si tous les autres processus sont bloqus,alors timeout devient excutable et permet de sortir de la boucle.

2 VrificationLa section prcdente dcrivait comment on peut spcifier un protocole avec le langage Promela. Maintenant

voyons comment il est possible de savoir si un protocole est juste ou non.

2.1 Un protocole correctEn ralit, un protocole, dun point de vue intrinsque, nest ni correct, ni incorrect. Il a un certain comportement

et cest lutilisateur de spcifier ce quil entend par un comportement correct.Un protocole qui sarrte et nvolue plus est soit termin, soit bloqu (deadlock). Mais cest lutilisateur de

spcifier au vrificateur que cet tat nest pas ltat dans lequel le protocole devrait sarrter. Il en va de mme pour lebouclage et autres phnomnes. Dans la suite, nous allons dcrire comment un utilisateur peut spcifier le comporte-ment que son protocole devrait avoir.

2.2 AssertionsLinstruction assert est toujours excutable. Elle prend en argument une condition boolenne, par exemple

assert(state==1). Sil existe un tat possible du protocole dans lequel, lorsque assert est excute, la variablestate ne vaut pas 1, alors le vrificateur lance une erreur, et prsente le scnario qui conduit cette situation.

2.3 Les deadlocks et les labels endLorsquun processus se termine simplement en arrivant sa dernire accolade, alors on considrera par dfaut

quelle sest termin de manire correcte.Mais dans certains cas, la fin du processus ne correspond pas cette dernire accolade. Dans ce cas, le vrificateur

supposera, a priori, quil sagit dune fin incorrecte, lancera un message derreur et montrera un scnario menant cet tat dinterblocage. Pour spcifier quun tel tat nest pas un interblocage, mais un tat de fin correct, vous devrezmettre un label end : devant linstruction laquelle le processus sarrte.

2.4 Les labels progressPour spcifier au vrificateur quun drooulement correct du protocole doit toujours repasser par un point prcis,

on devra mettre un label progress devant ce point.Ainsi, pour le vrificateur, toute boucle infinie ne contenant pas cette instruction sera considre comme une erreur.

Le vrificateur montrera un scnario menant cette situation.

2.5 Les boucles et les labels acceptUn bouclage peut parfaitement tre un comportement correct. Mais pour spcifier quun bouclage nest pas un

comportement correct, on pourra utiliser un label accept.Ainsi, pour le vrificateur, toute boucle infinie contenant cette instruction sera considre comme une erreur de

protocole. Le vrificateur montrera un scnario menant cette situation de bouclage.

8