Exploration implicite et explicite de l’espace d’états atteignables de circuits logiques Esterel

Exploration implicite et explicitede lespace dtats atteignablesde circuits logiques Esterel12 dcembre 2002Yannis BRESDirecteur de thse : Grard BERRY

PlanIntroduction :Contexte de travail, lapproche ractive synchrone, Esterel, automates et circuits, calcul despace dtats atteignables, BDDsI - Approche purement implicite :Un vrificateur formel proposant linputization ou labstraction de variablesII - Approche numerativeUn moteur polyvalent pour lexploration de lespace dtats atteignables :Gnration dautomatesVrification formelleGnration de squences de tests exhaustivesConclusion et perspectives

Lapproche ractive synchroneBase sur le modle smantique des Machines dEtats Finis (FSM)Programme ractif :Excution dcoupe en ractions (instants), temps discrtisProgramme synchrone :Simplification thorique : temps de raction nul, diffusion instantaneAnalyse de lenvironnement puis raction cet environnementLarge domaine dapplication :Systmes temps-relContrle/supervision de processus industrielsSystmes embarqusContrleurs matriels

EsterelUn langage ractif, synchrone, impratif dominance flot de contrleModules/blocs excuts en parallle ou en squenceModules/blocs peuvent tre prempts, suspendus et reprisCommunication par le biais de signaux instantanment diffuss (broadcast)Smantique formellemodule Synchronize :

inputA, B;outputO;

[ await A || await B ] ;emit O

end module

Automates explicitesReprsentation pivot des modles en Esterel v1, v2, v3 : automatesmodule Synchronize :

inputA, B;outputO;


end moduleLes automates peuvent tre exponentiels : en temps de construction en espace de stockage

CircuitsReprsentation pivot des modles depuis Esterel v4 : circuits logiquesTemps de gnration et taille linaire avec le code source

Automates vs. CircuitsRajoutons un signal C dans le programme prcdent

Vrification formelle par observateurmodule Synchronize :

inputA, B;outputO;


end moduleabortawait O ;emit BUGwhen A||Observateur excut en parallle du programme vrifierProprits de sret :"quelque chose de mal narrive jamais"Proprits de vivacit :"quelque chose de notable arrivera tt ou tard"Rpondre formellement la question : "BUG peut-il tre mis ?"

Calcul despace dtats atteignablescalcul de lespace dtats atteignables (Reachable State Space, RSS)Pierre angulaire pour de nombreuses applications :

Calcul despace dtats atteignablesDiffrentes approches du calcul du RSS :Reprsentation "en oignon", par niveaux de profondeur :Etat initialEtat atteignables en 1 tickEtat atteignables en 2 ticksEtat atteignables en 3 ticks

approcheanalyse des tatsanalyse des transitionspurement impliciteBDDsnumrativeimpliciteexpliciteexplicite

Diagrammes de Dcisions Binaires (BDDs)Ordre des variables constant dans tout larbre (ici : x1 < y1 < x2 < y2)Nud de variable (x1, x2, y1, y2)Nud terminal (constante 0 ou 1)Chemin "lorsque faux"Chemin "lorsque vrai"x1y1y1x2x2x2x2y2y2y2y2y2y2y2y21001000000001001(x1 y1) (x2 y2)

Diagrammes de Dcisions Binaires (BDDs)Plusieurs rgles de simplification :x1y1y1x2x2x2x2y2y2y2y2y2y2y2y210010000000010011)0Suppression des tests inutiles(x1 y1) (x2 y2)

Diagrammes de Dcisions Binaires (BDDs)Plusieurs rgles de simplification :x1y1y1x2x2y2y2y2y21001010011)02)Suppression des tests inutilesPartage des nuds/arbres isomorphes(x1 y1) (x2 y2)

Diagrammes de Dcisions Binaires (BDDs)Plusieurs rgles de simplification :1)2)3)x2x2x2y2y2y2y2y2y210010000000001x1y1y1x2y2y210Suppression des tests inutilesPartage des nuds/arbres isomorphesMarquage des arcs pour partage des nuds opposs (non reprsent)(x1 y1) (x2 y2)

Diagrammes de Dcisions Binaires (BDDs)Complexits dans le pire des cas en temps et en espace :Dans la plupart des cas :Algorithmes trs efficaces pour la manipulations de fonctions boolennesReprsentation trs compacte de fonctions boolennesReprsentation densembles via leur fonction caractristiqueReprsentation des fonctions associes aux portes du circuitUsages :

=, -constante, quadratique, substitutionsexponentielle

Calcul despace dtats avec des BDDsExponentiellement complexe selon le nombre de variables impliques :1 variable de BBD par entreVariable intermdiaire : doit tre , napparat pas dans les rsultats1 variable de BDD par variable dtat (registre) Objectif : rduire le nombre de variables dtat !Variable persistante : doit tre , apparat dans les rsultats

Rduction du nombre de variablesUne technique usuelle de rduction du nombre de variables dtat :Remplacer les variables dtats par des entres libres (inputization)Moins de variables substituerTout autant de variables Notre approche : abstraire les variables via une logique tri-value (0,1,d)Les variables abstraire sont remplaces par la constante d (indiffrent)Moins de variables substituerMoins de variables Logique tri-value (0,1,d) :+++=Les variables sont prquantifies

0110dd

01d0000101dd0dd

01d001d1111dd1d

vv0v1010101d00

Inputization et abstraction : exempleinputA, B;outputO;

[ await A || await B ] ;emit Oinputizationabstraction

Sur-approximationInputization et abstraction relchent les contraintes entre les variablesSur-approximation conservative par rapport au RSSEffet boule de neigeLinputization conserve la corrlation entre les instances de variablesr r i i = 0r r i i = 1Labstraction perd la corrlation entre les instances de variablesr r d d = dr r d d = dVrif. formelle : pas de validations errones, rfutations errones+-

Sur-approximationInputization et abstraction relchent les contraintes entre les variablesSur-approximation, conservative par rapport au RSSEffet boule de neigeLinputization conserve la corrlation entre les instances de variablesr r i i = 0r r i i = 1Labstraction perd la corrlation entre les instances de variablesr r d d = dr r d d = dVrif. formelle : pas de validations errones, rfutations erronesSource supplmentaire de sur-approximation au sein du calcul despace dtats en logique tri-value : largissement densembles+--

Larbre de slection Esterel[ await I1 ; do something ; await I2 ; do something || await I3 ; do something ] ; await I4 ; do something1234##

Notre vrificateur formel : evclEsterel Verification Command LineFonctionnalits principales :Rduction de la sur-approximation laide dinfos structurellesBote blanche (observateurs intgrs) / Bote noire (observateurs externes)Plus de 30 000 lignes de C++ (et plus de 21 000 lignes de librairie commune)Inputization et abstraction de variablesExperimentations :(Gestion du carburant du Mirage 2000-9, Systme dalarme de lA380)Labstraction peut-tre jusqu 26 fois plus rapide que linputizationLorsque la sur-approximation semballe, les calculs cessent trs tt Rien perdre tenter !

Calcul despace dtats atteignablesDiffrentes approches du calcul du RSS :Reprsentation "en oignon", par niveaux de profondeur :Etat initialEtat atteignables en 1 tickEtat atteignables en 2 ticksEtat atteignables en 3 ticks

approcheanalyse des tatsanalyse des transitionspurement impliciteBDDsnumrativeimpliciteexpliciteexplicite

Calcul despace dtats par numrationUn moteur polyvalent pour lexploration de lespace dtats atteignables :Etats analyss individuellement par propagation de donnes dans le circuitApproche pure explicite :Transition analyses par branchements rcursifs sur les entresApproche hybride implicite/explicite :Transitions analyses par propagation de BDDsGnration dautomatesSupport transparent des circuits cycliques (constructifs)Plusieurs heuristiques visant viter lexplosion en temps ou en espace trs bonnes performancesPlus de 18 000 lignes de C++ (et plus de 21 000 lignes de librairie commune)Vrification formelleGnration de squences de test

Gnration dautomatesRisque dexplosion la fois en temps et en tailleMaximum de flot de contrle calcul lors de la compilationImplmentation gnralement trs efficaceSeules les expressions dpendant des donnes restent valuerReprsentation pivot des modles en Esterel v1, v2, v3 : automatesReprsentation pivot des modles depuis Esterel v4 : circuits logiquesGnration dautomates nglige depuis la v4 :Gnrateur v4 trs peu performantLes automates rendent explicites de nombreuses infos sur les modlesPratiquement linaires avec la taille du codeToutefois, les avantages des automates demeurent !Uniquement partir de circuits acycliques

Gnration dautomatesApproche numerative pratiquement invitableApproche purement explicite prfrable lapproche hybrideComment gnrer un automate ?Notre gnerateur dautomates, scoc :Largement plus performant que le gnrateur v4Intgr au compilateur Esterel depuis la v5_91(trop de cofactorisations de BDDs ncessaires)(pour le respect de la causalit des actions)Dsormais commercialis par Esterel Technologies

Application la vrification formelleApproche purement implicite invitable pour la grande majorit des modlesApproche purement implicite :Comportement trs peu prvisible, risque dexplosionUniquement appliquable aux circuits acycliquesTrs sensible aux registres redondantsApproche numrative :Comportement gnralement trs rgulierSupport transparent des circuits cycliquesInsensible aux registres redondants ou la profondeur du modleGnralement beaucoup plus lent, uniquement utilisable sur cas prcis :Modles profonds (SAT )Modles forts taux de registres redondants (BDDs )

Vrification formelle exprimentationsBanc de test purement linaire (profondeur : 243 ; tats : 243)Bus de donnes de Texas Instruments (profondeur : 181 ; tats : 652 948)

SAT (Prover)approche implicite pureapproche explicite pureapproche implicite / expliciterien aprs >3h39mn1.6s1.8s< 40 Mo8.5 Moconso. mmoire insignifiante

SAT (Prover)approche implicite pureapproche explicite pureapproche implicite / expliciterien aprs plusieurs heures17mn : (profondeur 9)2h 33mn3h 09mn???2 Go104 Mo110 Mo

Gnration de squences de tests exhaustivesModle smantique des machines dtats finisDiffrents objectifs de couverture :Couverture des tatsCouverture des chemins menant lmission de certains signauxCouverture de transitions gnration de squences de tests exhaustives possible

Gnration de squences de tests exhaustivesApproche Esterel Technologies : implicite pureCalcul de RSS standard (sauf couverture de transitions)Transitions construites par calculs dimages inversesMise jour des donnes de couverture mise jour de BDDsRelle couverture de transition non implmenteSeulement couverture de paire dtats connectsApproche numrative plus adapte et insensible lobjectif de couvertureDoublement des variables dtats

Couverture dtats Exprimentations

ConclusionUn outil de vrification formelle base sur une approche purement impliciteUn moteur dexploration de lespace dtats atteignablesGnration dautomates explicitesVrification formelleRemplacement de variables par des entres libresAbstraction de variables laide dune logique tri-valueRduction de la sur-approximation laide dinformations structurellesVrification en bote blanche ou noireAnalyse numrative des tatsGnration de squences de tests exhaustivesAnalyse explicite ou implicite des transitionsPolyvalent :

PerspectivesApproche implicite :Heuristiques de pondration des variables de Quer/Cabodi et al. ?Automatiser la slection des variables inputizer/abstraireCombiner abstraction de variables et dcomposition du calcul du RSSApproche numrative :Compacter la table des tats connusPrioritization de lanalyse des tats (bug chasing)En cas de sur-approximation excessive, raffiner labstractionAnalyse 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.

Documents

Exploration implicite et explicite de l’espace d’états atteignables de circuits logiques Esterel