Vérification de modèles

Système de transition d'états pour un distributeur de boissons.

Le système est modélisé par un système de transition d'états. Il s'agit d'un graphe orienté : un sommet représente un état du système[9] et chaque arc représente une transition[10], c'est-à-dire une évolution possible du système d'un état donné vers un autre état. Chaque état du graphe orienté est étiqueté par l'ensemble des propositions atomiques vraies à ce point d'exécution (par exemple, i=2, le processeur 3 est en attente, etc.). Un tel graphe est aussi appelé une structure de Kripke.

On donne ici l'exemple d'un distributeur de boissons qui peut être dans 4 états[11] : attente d'une pièce de monnaie, sélection d'une boisson, distribution d'une bouteille d'eau minérale et distribution d'une bouteille de jus d'orange.

L'état du système est décrit par le niveau courant de l'ascenseur entre 0 et 3, l'état des appels (4 boutons, un par étage) et si l'ascenseur bouge et s'il patrouille vers le haut ou vers le bas[12] (il y a donc 4 × 2⁴ × 2 × 2 = 256 états).

La propriété à vérifier est écrite par une formule de logique temporelle. Par exemple, si l'on souhaite vérifier que x = 0 une infinité de fois, on peut écrire la formule GF(x = 0) qui se lit « toujours, dans le futur, x = 0 ». On distingue :

• les propriétés de sécurité (safety en anglais), comme « l'ascenseur bouge toujours avec les portes fermées » ;
• les propriétés de vivacité (liveneness en anglais), comme « si l'ascenseur est appelé à un certain étage, alors il ira à cet étage ».

Dwyer et al. ont identifié 55 types de spécification en logique temporelle linéaire qui apparaissent dans des applications industrielles[13].

Par exemple, (GFa → (G(s → F(e ou j))) (si la machine attend une infinité de fois une pièce, alors toujours, dès que l'on sélectionne une boisson, dans le futur, une boisson (eau minérale ou jus d'orange) est délivrée) est une propriété vraie pour le distributeur de boissons.

L'entrée du problème du model checking est un modèle (typiquement un système de transition d'états) et une propriété (typiquement écrite dans une logique temporelle). En sortie, on souhaite savoir si la propriété est vérifiée et, le cas échéant, un contre-exemple d'une exécution du système qui falsifie la propriété.

Pour des propriétés de sûreté (toujours, p est fausse), on peut faire un parcours en profondeur du graphe et vérifier que chaque état vérifie p. Des algorithmes d'étiquetage existent pour la logique temporelle arborescente (en) (CTL). D'autres méthodes sont fondées sur les automates. On transforme la négation de la formule à vérifier en un automate puis on fait le produit cartésien synchrone de l'automate et du modèle. On se ramène alors à tester si le langage de l'automate produit est vide ou non.

Parcourir (ou énumérer) explicitement tous les mondes de la structure de Kripke peut être coûteux, c'est pourquoi des méthodes symboliques, introduites par Ken McMillan et Ed Clarke,sont plus pertinentes. Une approche, répandue pour la vérification de propriétés exprimées dans la logique temporelle arborescente, est fondée sur la représentation symbolique du modèle. De nombreuses méthodes de représentation d'ensembles d'états ont vu le jour. La plus connue utilise les diagrammes de décision binaire (BDD).

Au lieu de considérer l'ensemble des traces d'exécution du système, on peut se limiter à des traces finies, de longueur bornée : c'est le model checking borné[14]. L'existence d'une trace vérifiant une certaine propriété est équivalente à la satisfiabilité d'une certaine formule booléenne. En effet, si un état du système est décrit par un k-uplet ${\displaystyle {\vec {x}}}$ de booléens, et que l'on s'intéresse aux traces de longueur bornée par un certain n, on se ramène au problème de la satisfiabilité d'une formule propositionnelle (problème SAT). Plus précisément, si une formule ${\displaystyle I}$ identifie les états initiaux du système, une formule ${\displaystyle F}$ les états dont on veut tester l'accessibilité, et une formule ${\displaystyle T}$ est une relation de transition, alors on considère la formule booléenne ${\displaystyle I({\vec {x}}_{1})\wedge T({\vec {x}}_{1},{\vec {x}}_{2})\wedge \dots \wedge T({\vec {x}}_{n-1},{\vec {x}}_{n})\wedge F({\vec {x}}_{n})}$ où ${\displaystyle {\vec {x}}_{i}}$ sont des propositions atomiques qui représentent l'état à l'étape i de l'exécution du système. Il existe divers logiciels, appelés solveurs SAT, qui peuvent décider « efficacement en pratique » le problème SAT. De plus, ces logiciels fournissent habituellement un exemple de valuation satisfaisant la formule en cas de succès. Certains peuvent produire des éléments d'une preuve de non-satisfiabilité en cas d'échec.

Une évolution récente est l'ajout, en sus de variables booléennes, de variables entières ou réelles. Les formules atomiques ne sont alors plus seulement les variables booléennes, mais des prédicats atomiques sur ces variables entières ou réelles, ou plus généralement des prédicats pris dans une théorie (par exemple ${\displaystyle x<5}$, etc.). On parle alors de satisfiabilité modulo une théorie (par exemple, on pourra considérer comme prédicats atomiques les égalités et inégalités linéaires).

Le modèle peut être plus riche que des automates finis. Il existe par exemple du model checking sur des automates temporisés. Aussi, le concept de model checking se généralise en logique mathématique. Par exemple, la vérification de structures avec une formule de la logique du premier ordre est PSPACE-complet ; de même pour une formule de la logique monadique du second ordre. La vérification de structures automatiques avec une formule du premier ordre est décidable.

Des techniques comme CEGAR (Counterexample-Guided Abstraction Refinement, « raffinement de l'abstraction guidé par les contre-exemples »)[15] permettent de transformer un programme (écrit en C par exemple) en un modèle abstrait puis de raffiner successivement le modèle s'il est trop grossier.

Il existe plusieurs logiques temporelles : LTL, CTL, CTL* ou le mu-calcul.

Dans les systèmes multi-agents, on s'intéresse à des propriétés épistémiques comme « l'agent sait que x = 0 » d'où l'utilisation de logique épistémique et de logiques qui mélangent logique temporelle et épistémique[16]. On s'intéresse à raisonner sur l'existence de stratégies dans un jeu : il existe des logiques pour écrire des propriétés sur les jeux comme « l'agent a une stratégie pour qu'un jour x = 0 » (alternating-time temporal logic (en))[17].

• Diagramme de décision binaire
• Automate de Buchi
• Logique temporelle
• Méthodes formelles
• Test logiciel
• Structure de Kripke
• Réduction par ordre partiel

• Gérard Berry La vérification de modèles (model checking), Leçon du Collège de France du 25 mars 2015.

• (en) E. M. Clarke, E. A. Emerson et A. P. Sistla, « Automatic verification of finite state concurrent systems using temporal logic », ACM Trans. on Programming Languages and Systems, vol. 8, n^o 2,‎ 1986, p. 244–263 (DOI 10.1145/5397.5399)
• (en) Kenneth L. McMillan, Symbolic Model Checking, Kluwer, 1993, 194 p. (ISBN 978-0-7923-9380-1 et 0-7923-9380-5, lire en ligne)
• (en) Edmund M. Clarke, Jr., Orna Grumberg et Doron A. Peled, Model Checking, Cambridge (Mass.), MIT Press, 1999, 314 p. (ISBN 0-262-03270-8)
• (en) Michael Huth et Mark Ryan, Logic in Computer Science : Modelling and Reasoning About Systems, CUP, 2004 (DOI 10.2277/052154310X)