E.Encrenaz-Tiphène, 04/11/05, séminaire TIMA 1 Vérification de systèmes matériels avec les DDD Systèmes spécifiés à un haut niveau dabstraction DDD : Structure

1E.Encrenaz-Tiphène, 04/11/05, séminaire TIMA

Vérification de systèmes matérielsavec les DDD

Systèmes spécifiés à un haut niveau d’abstraction

DDD : Structure de données exploitant le partage et la hiérarchie

Emmanuelle Encrenaz-Tiphène

Maître de Conférences à l’Université Paris VI – LIP6

En délégation CNRS au Laboratoire Spécification et Vérification (LSV) ENS-Cachan

En collaboration avec Vincent Beaudenon


Préambule – Hardware / Software Codesign

• Application : réseau de tâches communicantes – liens privés avec bufferisation (réseaux de Khan)– particularisation : données entières – buffers bornés – sélection

• Exploration architecturale (différentes possibilités d’implantation des tâches)

• Implantation matérielle (synthèse de haut niveau / synthèse des communications)

• Chaîne de conception Disydent [Pétrot Augé et al, 03]


Vérification fonctionnelle de systèmes matériels

• Simulations presque uniquement

• Equivalence-Checking pour des blocs combinatoires / RTL• Symbolic Model-Checking pour des petits blocs (10 KG)• Méthodes « semi-formelles » prennent le pas sur SMC

– LTL sur séquences bornées moniteurs incorporés dans la simulation

– CTL à profondeur bornée déroulement explicite de l’arbre d’exécution

• Démonstrations assistées (architectures spécifiques : cœurs de processeurs / traitement du signal)


Notre objectif

• Construire un Model-Checker Symbolique pour des systèmes décrits sous forme de graphe de tâches.

• Représentation symbolique d’ensembles d’états du système + opérations ensemblistes (, , )– Données entières / structurées– Canaux de taille variable

• Opérateurs Post et Pré sur la représentation symbolique de l’ensemble des états, associés à la sémantique des actions du graphe de tâches.


Plan de l’exposé

• Modélisation de systèmes dans un sous-ensemble de ProMeLa

• Représentation symbolique : Structure de donnée DDD – Représentation des ensembles d’états

– Opérations ensemblistes

– Homomorphismes

– Homomorphismes pour instructions ProMeLa

– Introduction de la hiérarchie

• Application à la vérification de propriétés CTL– Exemples classiques

– Réseau VCI-SPIN

• Conclusion


La plate-forme de vérification ProMeLa-SPIN

• Langage ProMeLa : description d’applications concurrentes, dynamiques, asynchrones, communication par buffers bornés et variables partagées

• Vérification de propriétés de sûreté et de vivacité par exploration du graphe des états accessibles– Représentation explicite des états– Réduction de l’espace à analyser (techniques d’ordre partiel /

compactage)

• Applicable pour des systèmes "séquentiels" comportant 106 à 107 états

[G. Holzmann 97]


Un sous-ensemble de ProMeLa

• Variables globales – Types scalaires (basés sur entier) / Type produit– Tableaux– Canaux (bornés)

• Processus concurrents– Variables locales– Instructions gardées (affectations, lecture / écriture) – Choix indéterministe– Répétition indéterministe

• Pas d’instanciation dynamique de processus (run est exclu)• Les processus n’ont pas de paramètres


Exemple de description

proctype proc_port_in0_0(){ MOT mess; bit reserve; bit current_clock=0;

mtype sortie_down; bit jeton = 1;

do :: (clock == current_clock) -> current_clock = !current_clock;

x0_d0_spin_data_in?mess-> if :: (((mess.addest >> level_num0_0) & 3) == level_id0_0) -> /* Traitement des ports DOWN. */ sortie_down = (mess.addest >> (level_num0_0-1)) & 1;

if :: (sortie_down == 0) -> poss_out0_0?jeton; do :: x0_d0_spin_data_out!mess; if :: mess.tag == FIN -> atomic{poss_out0_0!jeton; goto SUITE_DOWN;} :: else -> x0_d0_spin_data_in?mess; fi;…

}

variables locales

garde

affectation

lecture dans un canal

écriture dans un canal


Représentation symbolique d’états

Diagrammes de Décision de Données (DDD)

Structure de donnée pour représenter les ensembles d’états.(LIP6 / LaBRI ): arbres partagés.

• projet Clovis [DGA 01]• Application aux réseaux de Petri étendus [ATPN 02] [FORTE 04] [FORTE 05]

• Variables décisionnelles de type fini• Représentation des chemins menant à 1 ou T• Exploitation du partage des sous-arbres isomorphes• Opérations ensemblistes : parcours attelé des 2 DDD (polynômial) • Modification « la plus locale possible » : homomorphisme


DDD : Structure

• Nœuds : variables• Arcs : valeur dans les entiers• Contrainte: un seul arc d’une étiquette donnée en sortie d’un nœud

Interprétation : ensemble de mots (affectations) menant au nœud 1Efficacité : partage

a

b c

c

1

11

1 2

1 2 1

1

a

b

c

1

12

1

2

1

partage


DDD : Normalisation

• Les chemins invalides ne sont pas représentés • Conséquence : domaine des variables inconnu a priori• Représentation de l’ensemble vide nœud terminal 0

Représentation canonique des DDD (classe d’équivalence)

a

b c

c

1

11

1 2

1 2 1

1

a

b

c

1

12

1

2

1

normalisation

0

0

0

0

partage


DDD : Opérations ensemblistes (1)

Un DDD est un ensemble de mots : Opérations ensemblistes + * \

Exemple :

A

A * B

B

a a

1

bb

c

2,3 4

1 2,6

3,4

1

bb

c

1,3 2,4

1 6

3

c

2

4

A*B

1

a

bb

c

3 4

1 6

3

c

4


DDD : Opérations ensemblistes (2)

Un DDD est un ensemble de mots : Opération de concaténation .

Exemple :

A

A . B

...

v0

1

...

v1

1

...

v0

...

v1

1B


DDD : Homomorphisme

• Définition : d, d’ deux DDD bien définisUn homomorphisme est une fonction telle que :

(0) = 0 (d) + (d’) = (d + d’)

réunionréunion

1

d d’

1

d d’


Homomorphismes inductifs

Homomorphisme défini localement

(0) = 0(1) = constante(d) = définition locale à la racine de d et ses valuations

Exemple : affectation d’une valeur constante var=val

e

x….

e

val….

val

Si e == var

e

….

…. Sinon

var=val

var=val var=val


SetCst(var,val) (1) = T (une erreur)

e — Id si e == var

SetCst(var,val) (e,x) =

e — SetCst(var,val) sinon


val

x

Affectation v1 = Constante


Autres homomorphismes inductifs

• SetVar (v1,v2)

• SetVarExpr (var, expr)

• SelVarCst (var, const)

• SelExp (expr)

• …


DDD pour les programmes ProMeLa

Instruction ProMeLa = construction de deux homomorphismes

Post: calcule les successeurs par l’application d’une instruction

Pré : calcule les prédécesseurs potentiels résultants de l’exécution d’une instruction

Un état du programme :• variables globales• chaque processus en cours d’exécution

• son compteur ordinal• ses variables locales

Etat initial = concaténation de toutes les variables dans un ordre figé


Homomorphismes inductifs Promela-DDD

• Affectation gardée1. exp_g -> x := 5;2. …

• Indéterminisme1. if :: exp_g1 -> (2.) … :: exp_g2 -> (3.) … fi;4. …

• Ecriture dans un canal1. c!x2. …

SetCst(pc,2) o SetCst(x,5) o SelExp(pc==1 exp_g)

SetCst(pc,2) o SelExp(pc==1 exp_g1) +SetCst(pc,3) o SelExp(pc==1 exp_g2)

SetCst(pc,2) o SetVarFifo(c,x) o SelCst(pc==1)


Calcul de l’ensemble des états accessibles

New = Init;Reached = ;While New loop

tmp = NewForall process p loop

Forall instruction i loop

To = Postp,i(tmp);tmp = To + tmp;

EndloopEndloopNew = tmp \ reachedReached = tmp + reached

EndloopReturn Reached


Evaluation de formules CTL

Opérateur Pré :

Pb : Toutes les opérations ne sont pas inversibles : x = 4;

Approche classique (2 à 3 passes) :

• élargissement à toutes les valeurs possibles, puis

• restriction aux états accessibles

Opérateur ad-hoc en 1 passe

Evaluation de "EF p"


Comparaison avec les BDD

• Opérateurs Postp,i et Prép,i implantés sur la bibliothèque BuDDy [Lind-Nielsen, Reif Andersen CAV 99]– Représentation des opérations arithmétiques sur des vecteurs de bits

– Domaine des variables déterminé a priori (type déclaré)

• Traitements pour réaliser Postp,i(E) si i décrit x = y– Un seul jeu de variable

– Abstraction de x dans E : E|x

– Construction de G = (x y) = (x y) ( x y)

– Contrainte de E|x par G : E|x G


Résultats sur exemples classiques (DDD plats)

• Dichotomie méthode énumérative / méthode symbolique

– Systèmes fortement séquentiels jusqu’à 106 ou 107 états : SPIN donne de meilleurs résultats. (sliding window, Peterson, Bakery)

– Systèmes fortement concurrents jusqu’à 1010 états (au delà si très réguliers) : BDD et DDD donnent de meilleurs résultats. (Philosophes, élection sur anneau)

• BDD vs DDD

– BDD avec réordonnancement dynamique et DDD statique sont comparables.

– Lorsqu’un « bon ordre » peut être exploité, les DDD statiques présentent de meilleures performances que BDD ou DDD ordre qcq.

– Limitations des DDD : ordre / gestion des expressions / longueur des chemins


Introduction de la hiérarchie dans les DDD (1)

HDD : Les valuations des arcs sont des DDD

c

d

1 2

2 3 2 3

4 5 4 5

2 11

a

b b

c c c

d

2

c

d

1

3

4 5

2 11

a

b

c

d 1

1

i

DDD HDD


Introduction de la hiérarchie dans les DDD (2)

• Les HDD sont des DDD qui bénéficient :– Augmentation du partage,

– Réduction de la longueur des chemins de la racine vers 1.

• Ajustement des homomorphismes– Propagation de l’homomorphisme

au nœud suivant au même niveau de la hiérarchie,

au nœud racine du DDD de niveau de hiérarchie inférieur

– Occasionnellement, nécessité d’aplanir localement la hiérarchie


HDD pour Programme ProMeLa

variable produit

…

…

variables globales

processus

variable scalaire

canal

compteur ordinal

variables locales

Lors du calcul de l’ensemble des états accessibles,réordonner le franchissement des instructions

pour saturer les couches basses du HDD

Saturation

Hiérarchisation de l’état


Résultats sur exemples classiques (HDD)

• Confirment la tendance observée avec les DDD plats :

– SPIN reste meilleur sur les systèmes très séquentiels (Sliding window, Peterson, Bakery)

– HDD + saturation sont bien meilleurs que les BDD ou les DDD plats sur des systèmes très parallèles (jusqu’à 1000 philosophes, jusqu’à 100 électeurs sur l’anneau)


Réseau VCI-SPIN (1)

VCI-SPIN

wrappers

SPIN

network

I3 I4 T3 T4

Apparition d’un interblocage


Réseau VCI-SPIN (2)

VCI-SPIN

wrappers

SPIN

network

I3 I4 T3 T4

Evitement de l’interblocage : séparer les requêtes et réponses sur les liens descendants


Vérification avec SPIN et HDD

• Modèle ProMeLa– Pour chaque routeur :

• 1 processus par port d’entrée (4)

• 1 mécanisme d’exclusivité d’accès par port de sortie (4)

– Pour chaque initiateur :• 2 processus (1 émetteur requête / 1 récepteur réponse)

– Pour chaque cible :• 1 processus

– Messages bufferisés en entrées de chaque port (buffers de taille 1)


Vérification avec SPIN

• Propriété de vivacité «émetteur 0 pourra toujours émettre un nouveau message »

• Configuration à 2 routeurs, initiateurs et cibles fixés

• Synchronisation des processus

• Taille des messages fixée (1 à 7 paquets)

Vivacité, n=6 : propriété vérifiée en 36000 s et 100 MB

Accessibilité, n = 6 : construit en 512 s et 9 MB


Vérification avec HDD

• Propriété de sûreté :Absence d’état puits

• Configurations à 2 et 4 routeurs, initiateurs et cibles variables

• Taille des messages variable (de 1 à 7 paquets)

Pour la configuration restreinte :Accessibilité, n=6, synchrone, 2 routeurs : 33 s, 139 MB

Pour les configurations plus libres :Accessibilité, n=1 à 7, asynchrone, 4 routeurs, config libre : 7881 s et 492 MB

ou : 519 s et 1,5 GB


Conclusion

• Construction d’un model-checker pour des systèmes statiques décrits en ProMeLa

• DDD : Représentation intéressante pour les systèmes présentant un fort parallélisme– Hiérarchie– Saturation

• Analyse complémentaire à l’outil SPIN– Certains systèmes sont analysés très rapidement par SPIN et pas

de résultats avec HDD, et réciproquement– Propriétés de vivacité / de sûreté


Perspectives

• Amélioration de l’algorithmique sur les HDDÉviter les applatissements locaux

• Augmenter la prise en compte de la hiérarchieDécoupage dichotomique du système

• Extension à des systèmes dynamiques



Résultats sur exemples classiques (DDD plats)[BET – Majestic 04]

• Calcul d’accessibilité + une propriété " AG AF but atteint « Temps de calcul (en s) / Mémoire nécessaire (en MB)

• PhilosophesSPIN BDD DDD DDD-O

15 : 2251/1067 380+1200/96 18 K+-/397 54+5/30

50: -/- -/- -/- 8006/996

• Election sur anneauSPIN BDD DDD DDD-O

6 : 262/144 5056+5394/144 34+5/11 37+3/11

10: -/- -/- 4533+-/663 716+-/77


Résultats sur exemples classiques (DDD plats)

• Sliding windowSPIN BDD DDD DDD-O

2 : 0/8 552+221/102 486+142/18 662+206/173 : 29/450 65 K +63 K /332 480 K + - /565 480 K +

-/4754 : -/- -/- -/- -/-

• Exclusion PetersonSPIN BDD DDD

3 : 0/6 17+39 /93 7+4/65 : -/- 470 K + - /900 -/-

• BakerySPIN BDD DDD

4 : 0/5 50+0/94 17+0/95 : 1385/6 1231+0/93 379+5/466 : -/- -/- 61901+47/455


Résultats sur exemples classiques (HDD)

Calcul d’accessibilité uniquement• Philosophes

DDD DDD-O HDD HDD-sat15 : 18 K+-/397 54+5/30 25/16 0/250: -/- 8006/996 3308/532 1/91000: -/- -/- -/- 258/1343

• Election sur anneauDDD DDD-O HDD HDD-sat

6 : 34+5/11 37+3/11 6/4 0/410: 4533+-/663 716+-/77 333/61 2/1420: -/- -/- 9891/771 14/65100 : -/- -/- -/- 443/1866

• Systèmes séquentiels : Amélioration par rapport aux DDD plats mais moins bons que SPIN


DDD : Approximation

• Contrainte : un seul arc d’une étiquette donnée en sortie d’un nœud• Conséquence : des opérations peuvent conduire à des résultats

indéterminés• Représentation de l’approximation nœud terminal T

• Bonnes propriétés algébriques des opérations

a

a

b

1

1

1 2

1 2

1

T

• DDD bien défini : absence de nœud terminal T

• Relation « mieux-défini » :relation d’ordre sur les DDD


DDD : Opérations (2)

Exemple d’opération faisant apparaître une approximation

a

a c

c

1

1 2

1

2

3

0

a

a a

c

1

1 2

1

2

3

0

+ =

a

a

c

1

1 2

1

2

0

T


DDD : Homomorphismes

• Définition : d, d’ deux DDD bien définisUn homomorphisme est une fonction telle que :

(0) = 0 (d) + (d’) = (d + d’)

• Exemplesd * IdId \ dId . d1 + 2

1 o 2

• Cas général : d, d’ deux DDD (0) = 0

(d) + (d’) (d + d’)d d’ (d) (d’)


DDD : Homomorphismes inductifs (1)

• Famille d’homomorphismes i définis localementi (0) = 0i (T) = Ti (1) = ci (une constante)i (d) = définition locale à la racine de d et à ses valuations

• Exemple

SetCst(var, val)(1) = T

SetCst(var, val)(e, x) =

e — Id si e = var

e — SetCst(var,val) sinon

val

x



SetCst(b,2)

a

b c

1

1 2

0 1

= SetCst(b,2) (a — b — 1 ) +

SetCst(b,2) (a — c — 1 ) 1

0

2

1

SetCst(b,2) (a — b — 1 ) = a — SetCst(b,2)(b — 1 )

= a — b — Id(1)

= a — b — 1

01 1

1

1

0

2

2

SetCst(b,2) (a — c — 1 ) = a — SetCst(b,2)(c — 1 )

= a — c — SetCst(b,2)(1)

= a — c — T

12 2

2

2

1

1

1



SetVar(var1, var2)(1) = 1

SetVar(var1, var2)(e, x) =

Down(var1, var2) si e = var1

e — SetCst(var1, x) si e = var2

e — SetVar(var1, var2) sinon

x

x

Down(var1, var2)(1) = T

Down(var1, var2)(e, x) = var1 — e — Id si e = var2

Up(e, x) o Down(var1, var2) sinon

x x

Up(var, val)(1) = T

Up(var, val)(e, x) = e — var — Id x val

Exemple : var1 = var2 SetVar

Down

Up



SetVar(b, d) (a — b — c — d — 1)

a — SetVar(b, d) (b — c — d — 1)

a — Down(b, d) (c — d — 1)

a — Up(c, 3) o Down(b, d) (d — 1)

a — Up(c, 3) (b — d — Id(1))

a — Up(c, 3) (b — d — 1)

a — b — c — d — 1

1 2 3 4

1 2 3 4

1 3 4

41

1 4 4

1 4 4

1 4 43

Exemple d’exécution de SetVar : b = d



SetVar(v1,v2) (1) = T (une erreur)

Down(v1,v2) si e == v1

SetVar(v1,v2) (e,x) = e — SetCst(v1,x)si e == v2

e — SetVar(v1,v2) sinon

Down(v1,v2 ) (1) = T

Down (v1,v2) (e,x) = v1 — e — Id si e == v2

Up(e, x) o Down(v1, v2) sinon

Up(var, val)(1) = T

Up(var, val)(e, x) = e — var — Id

Affectation V1 = V2

Documents

E.Encrenaz-Tiphène, 04/11/05, séminaire TIMA 1 Vérification de systèmes matériels avec les DDD Systèmes spécifiés à un haut niveau dabstraction DDD : Structure