1 Exploration implicite et explicite de lespace détats atteignables de circuits logiques Esterel 12...

1

Exploration implicite et explicitede l’espace d’états atteignables

de circuits logiques Esterel

12 décembre 2002

Yannis BRES

Directeur de thèse : Gérard BERRY

2Plan

Introduction :

Contexte de travail, l’approche réactive synchrone, Esterel, automates et circuits, calcul d’espace d’états atteignables, BDDs

I - Approche purement implicite :

Un vérificateur formel proposant l’inputization ou l’abstraction de variables

II - Approche énumerative

Un moteur polyvalent pour l’exploration de l’espace d’états atteignables :

Génération d’automates

Vérification formelle

Génération de séquences de tests exhaustives

Conclusion et perspectives

3L’approche réactive synchrone

Basée sur le modèle sémantique des Machines d’Etats Finis (FSM)

Programme réactif :

Exécution découpée en réactions (instants), temps discrétisé

Programme synchrone :

Simplification théorique : temps de réaction nul, diffusion instantanée

Analyse de l’environnement puis réaction à cet environnement

Large domaine d’application :

Systèmes temps-réel

Contrôle/supervision de processus industriels

Systèmes embarqués

Contrôleurs matériels

…

4Esterel

Un langage réactif, synchrone, impératif à dominance flot de contrôle

Modules/blocs exécutés en parallèle ou en séquence

Modules/blocs peuvent être préemptés, suspendus et repris

Communication par le biais de signaux instantanément diffusés (broadcast)

Sémantique formelle

module Synchronize :

input A, B;output O;

[ await A || await B ] ;emit O

end module

5Automates explicites

Représentation pivot des modèles en Esterel v1, v2, v3 : automates

module Synchronize :

input A, B;output O;

[ await A || await B ] ;emit O

end module

Les automates peuvent être exponentiels :

en temps de construction

en espace de stockage

6Circuits

Représentation pivot des modèles depuis Esterel v4 : circuits logiques

Temps de génération et taille linéaire avec le code source

7Automates vs. Circuits

Rajoutons un signal C dans le programme précédent…

8Automates vs. Circuits

Rajoutons un signal C dans le programme précédent…

9Vérification formelle par observateur

module Synchronize :

input A, B;output O;

[ await A || await B ] ;emit O

end module

abortawait O ;emit BUG

when A||

Observateur exécuté en parallèle du programme à vérifier

Propriétés de sûreté :

"quelque chose de mal n’arrive jamais"

Propriétés de vivacité :

"quelque chose de notable arrivera tôt ou tard"

Répondre formellement à la question : "BUG peut-il être émis ?"

10Calcul d’espace d’états atteignables

calcul de l’espaced’états atteignables

(Reachable StateSpace, RSS)

Pierre angulaire pour de nombreuses applications :

générationd’automates

générationde séquences

de tests exhaustives

vérificationformelle

vérificationd’équivalencede machines

11Calcul d’espace d’états atteignables

approcheanalyse

des étatsanalyse

des transitions

purement implicite BDDs

énumérativeimplicite

explicite explicite

Différentes approches du calcul du RSS :

Représentation "en oignon", par niveaux de profondeur :

Etat initial

Etat atteignables en 1 tick

Etat atteignables en 2 ticks

Etat atteignables en 3 ticks

…

12Diagrammes de Décisions Binaires (BDDs)

Ordre des variables constant dans tout l’arbre (ici : x1 < y1 < x2 < y2)

Nœud de variable (x1, x2, y1, y2)

Nœud terminal (constante 0 ou 1)

Chemin "lorsque faux"

Chemin "lorsque vrai"

x1

y1 y1

x2 x2 x2 x2

y2 y2 y2 y2 y2 y2 y2 y2

1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1

(x1 y1) (x2 y2)

13Diagrammes de Décisions Binaires (BDDs)

Plusieurs règles de simplification :

x1

y1 y1

x2 x2 x2 x2

y2 y2 y2 y2 y2 y2 y2 y2

1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1

1)

0

Suppression des tests inutiles

(x1 y1) (x2 y2)

14Diagrammes de Décisions Binaires (BDDs)

Plusieurs règles de simplification :

x1

y1 y1

x2 x2

y2 y2 y2 y2

1 0 0 1

0

1 0 0 1

1)

0

2)

Suppression des tests inutiles

Partage des nœuds/arbres isomorphes

(x1 y1) (x2 y2)

15Diagrammes de Décisions Binaires (BDDs)

Plusieurs règles de simplification :

1)

2)

3)

x2 x2 x2

y2 y2 y2 y2 y2 y2

1 0 0 1 0 0 0 0 0 0 0 0 0 1

x1

y1 y1

x2

y2 y2

1 0

Suppression des tests inutiles

Partage des nœuds/arbres isomorphes

Marquage des arcs pour partage des nœuds opposés (non représenté)

(x1 y1) (x2 y2)

16Diagrammes de Décisions Binaires (BDDs)

Complexités dans le pire des cas en temps et en espace :

Dans la plupart des cas :

Algorithmes très efficaces pour la manipulations de fonctions booléennes

Représentation très compacte de fonctions booléennes

Représentation d’ensembles via leur fonction caractéristique

Représentation des fonctions associées aux portes du circuit

Usages :

=, - constante

, quadratique

, substitutions exponentielle

17Calcul d’espace d’états avec des BDDs

Exponentiellement complexe selon le nombre de variables impliquées :

1 variable de BBD par entrée

Variable intermédiaire : doit être , n’apparaît pas dans les résultats

1 variable de BDD par variable d’état (registre)

Objectif : réduire le nombre de variables d’état !

Variable persistante : doit être , apparaît dans les résultats

18Plan

Introduction :

Contexte de travail, l’approche réactive synchrone, Esterel, automates et circuits, calcul d’espace d’états atteignables, BDDs

I - Approche purement implicite :

Un vérificateur formel proposant l’inputization ou l’abstraction de variables

II - Approche énumerative

Un moteur polyvalent pour l’exploration de l’espace d’états atteignables :

Génération d’automates

Vérification formelle

Génération de séquences de tests exhaustives

Conclusion et perspectives

19Réduction du nombre de variables

Une technique usuelle de réduction du nombre de variables d’état :

Remplacer les variables d’états par des entrées libres (inputization)

Moins de variables à substituer

Tout autant de variables à

Notre approche : abstraire les variables via une logique tri-valuée (0,1,d)

Les variables à abstraire sont remplacées par la constante d (indifférent)

Moins de variables à substituer

Moins de variables à

Logique tri-valuée (0,1,d) :

0 1

1 0

d d

0 1 d

0 0 0 0

1 0 1 d

d 0 d d

0 1 d

0 0 1 d

1 1 1 1

d d 1 d

v v0 v1

0 1 0

1 0 1

d 0 0

+

++

=

Les variables sont préquantifiées

20Inputization et abstraction : exemple

input A, B;output O;

[ await A || await B ] ;emit O

inputization abstraction

21Sur-approximation

Inputization et abstraction relâchent les contraintes entre les variables Sur-approximation conservative par rapport au RSS

Effet “boule de neige”L’inputization conserve la corrélation entre les instances de variables

r r i i = 0 r r i i = 1L’abstraction perd la corrélation entre les instances de variables

r r d d = d r r d d = d

Vérif. formelle : pas de validations erronées, réfutations erronées

+

-

22Sur-approximation

Inputization et abstraction relâchent les contraintes entre les variables Sur-approximation, conservative par rapport au RSS

Effet “boule de neige”L’inputization conserve la corrélation entre les instances de variables

r r i i = 0 r r i i = 1L’abstraction perd la corrélation entre les instances de variables

r r d d = d r r d d = d

Vérif. formelle : pas de validations erronées, réfutations erronées

Source supplémentaire de sur-approximation au sein du calcul d’espace d’états en logique tri-valuée : élargissement d’ensembles

+

--

En pratique, si la sur-approximation s’emballe, des réfutations erronées surviennent très rapidement et les calculs cessent

+

23L’arbre de sélection Esterel

[await I1 ;do something ;await I2 ;do something

||await I3 ;do something

] ;await I4 ;do something

1

2

3

4

#

#

Permet de réduire la sur-approximation de deux manières :

Renforcement des relations entre entrées pour les variables inputizées

Borne supérieure de l’espace d’états atteignables

24Notre vérificateur formel : evcl

Esterel Verification Command Line

Fonctionnalités principales :

Réduction de la sur-approximation à l’aide d’infos structurelles

Boîte blanche (observateurs intégrés) / Boîte noire (observateurs externes)

…

Plus de 30 000 lignes de C++ (et plus de 21 000 lignes de librairie commune)

Inputization et abstraction de variables

Experimentations :

(Gestion du carburant du Mirage 2000-9, Système d’alarme de l’A380)

L’abstraction peut-être jusqu’à 26 fois plus rapide que l’inputization

Lorsque la sur-approximation s’emballe, les calculs cessent très tôt

Rien à perdre à tenter !

25Plan

Introduction :

Contexte de travail, l’approche réactive synchrone, Esterel, automates et circuits, calcul d’espace d’états atteignables, BDDs

I - Approche purement implicite :

Un vérificateur formel proposant l’inputization ou l’abstraction de variables

II - Approche énumerative

Un moteur polyvalent pour l’exploration de l’espace d’états atteignables :

Génération d’automates

Vérification formelle

Génération de séquences de tests exhaustives

Conclusion et perspectives

26Calcul d’espace d’états atteignables

approcheanalyse

des étatsanalyse

des transitions

purement implicite BDDs

énumérativeimplicite

explicite explicite

Différentes approches du calcul du RSS :

Représentation "en oignon", par niveaux de profondeur :

Etat initial

Etat atteignables en 1 tick

Etat atteignables en 2 ticks

Etat atteignables en 3 ticks

…

27Calcul d’espace d’états par énumération

Un moteur polyvalent pour l’exploration de l’espace d’états atteignables :

Etats analysés individuellement par propagation de données dans le circuit

Approche pure explicite :

Transition analysées par branchements récursifs sur les entrées

Approche hybride implicite/explicite :

Transitions analysées par propagation de BDDs

Génération d’automates

Support transparent des circuits cycliques (constructifs)

Plusieurs heuristiques visant à éviter l’explosion en temps ou en espace

très bonnes performances

Plus de 18 000 lignes de C++ (et plus de 21 000 lignes de librairie commune)

Vérification formelle

Génération de séquences de test

28Génération d’automates

Risque d’explosion à la fois en temps et en taille

Maximum de flot de contrôle calculé lors de la compilation

Implémentation généralement très efficace

Seules les expressions dépendant des données restent à évaluer

Représentation pivot des modèles en Esterel v1, v2, v3 : automates

Représentation pivot des modèles depuis Esterel v4 : circuits logiques

Génération d’automates négligée depuis la v4 :

Générateur v4 très peu performant

Les automates rendent explicites de nombreuses infos sur les modèles

Pratiquement linéaires avec la taille du code

Toutefois, les avantages des automates demeurent !

Uniquement à partir de circuits acycliques

…

29Génération d’automates

Approche énumerative pratiquement inévitable

Approche purement explicite préférable à l’approche hybride

Comment générer un automate ?

Notre génerateur d’automates, scoc :

Largement plus performant que le générateur v4

Intégré au compilateur Esterel depuis la v5_91

(trop de cofactorisations de BDDs nécessaires)

(pour le respect de la causalité des actions)

Désormais commercialisé par Esterel Technologies

30Application à la vérification formelle

Approche purement implicite inévitable pour la grande majorité des modèles

Approche purement implicite :

Comportement très peu prévisible, risque d’explosion

Uniquement appliquable aux circuits acycliques

Très sensible aux registres redondants

Approche énumérative :

Comportement généralement très régulier

Support transparent des circuits cycliques

Insensible aux registres redondants ou à la profondeur du modèle

Généralement beaucoup plus lent, uniquement utilisable sur cas précis :

Modèles profonds (SAT )Modèles à forts taux de registres redondants (BDDs )

31Vérification formelle – expérimentations

Banc de test purement linéaire (profondeur : 243 ; états : 243)

Bus de données de Texas Instruments (profondeur : 181 ; états : 652 948)

SAT (Prover)approche

implicite pureapproche

explicite pureapproche

implicite / explicite

rien après >3h 39mn 1.6s 1.8s

< 40 Mo 8.5 Mo conso. mémoire insignifiante

SAT (Prover)approche

implicite pureapproche

explicite pureapproche

implicite / explicite

rien aprèsplusieurs heures

17mn : (profondeur 9)

2h 33mn 3h 09mn

??? 2 Go 104 Mo 110 Mo

32Génération de séquences de tests exhaustives

Modèle sémantique des machines d’états finis

Différents objectifs de couverture :

Couverture des états

Couverture des chemins menant à l’émission de certains signaux

Couverture de transitions

…

génération de séquences de tests exhaustives possible

33Génération de séquences de tests exhaustives

Approche Esterel Technologies : implicite pure

Calcul de RSS standard (sauf couverture de transitions)

Transitions construites par calculs d’images inverses

Mise à jour des données de couverture mise à jour de BDDs

Réelle couverture de transition non implémentée

Seulement couverture de paire d’états connectés

Approche énumérative plus adaptée et insensible à l’objectif de couverture

Doublement des variables d’états

34Couverture d’états – Expérimentations

modèle étatsapproche implicite

approche hybrideimplicite / explicite ratio

# séqu. temps # séqu. temps

NDA 10 4 0.10 4 0.03 3.5

Arbiter12 13 cyclique 1 0.03

NDA 21 8 0.09 8 0.03 3.5

Wristwatch 41 16 1.39 16 0.09 16

NDA 65 63 0.74 63 0.07 11

ATDS-100-C2 81 35 3.58 37 0.10 36

Renault 161 99 13.57 105 0.35 39

Testbench 243 tué après >>1h 1 3.16

TCINT 310 140 33.36 140 0.39 86

NDA 535 307 35.57 308 0.47 76

NDA 875 462 16.57 489 0.43 39

35Conclusion

Un outil de vérification formelle basée sur une approche purement implicite

Un moteur d’exploration de l’espace d’états atteignables

Génération d’automates explicites

Vérification formelle

Remplacement de variables par des entrées libres

Abstraction de variables à l’aide d’une logique tri-valuée

Réduction de la sur-approximation à l’aide d’informations structurelles

Vérification en boîte blanche ou noire

…

Analyse énumérative des états

Génération de séquences de tests exhaustives

Analyse explicite ou implicite des transitions

Polyvalent :

36Perspectives

Approche implicite :

Heuristiques de pondération des variables de Quer/Cabodi et al. ?

Automatiser la sélection des variables à inputizer/abstraire

Combiner abstraction de variables et décomposition du calcul du RSS

Approche énumérative :

Compacter la table des états connus

Prioritization de l’analyse des états (bug chasing)

En cas de sur-approximation excessive, raffiner l’abstraction

Analyse des contre-exemples de Clarke/Grumberg et al.

Approches de Cho/Govidaraju et al.

…

Bitstate hashing de Holzmann, hash compaction de Stern/Dill et al.

Yang/Dill et al.

…