La vérification de modèles est le processus de vérification algorithmique qui explore l'espace d'états d'un modèle formel pour déterminer s'il satisfait une spécification donnée, souvent exprimée en logiques temporelles ou modales.

Principe

Parcourir de manière exhaustive ou symbolique les états atteignables du modèle selon la sémantique du système, évaluer la spécification à chaque état ou trace pertinent(e), et renvoyer les résultats de satisfaction ou des contre-exemples lorsque des propriétés échouent.

Démonstration

Vérifier un protocole à états finis par rapport à une propriété de sécurité en LTL en construisant le graphe des états atteignables par parcours en largeur ou via BDD symboliques et signaler une trace de contre-exemple en cas de violation de sécurité.

Mauvaise application

Appliquer naïvement la vérification de modèles à des systèmes à espace d'états effectivement infini sans abstraction correcte conduit à des résultats erronés ; prendre une trace de contre-exemple pour une preuve d'implémentation sans considérer les écarts de modélisation est trompeur.

Conséquence

La vérification de modèles produit des contre-exemples concrets pour les propriétés violées et un haut niveau d'assurance pour les modèles à états finis ; elle automatise la détection de bogues, la vérification de régressions et la vérification de modèles de conception sous des sémantiques spécifiées.

Inversion

L'approche inverse est la vérification déductive ou le théorème démonstratif, où l'on construit des preuves symboliques de correction plutôt que d'explorer exhaustivement des espaces d'états ; la simulation est une alternative plus faible qui échantillonne des comportements sans être exhaustive.

Limite

La vérification de modèles s'applique aux espaces d'états finis ou effectifemment énumérables, aux modèles à sémantique bien définie et aux propriétés exprimées dans des logiques vérifiables ; elle exclut les systèmes à état infini non abstraits et les spécifications informelles sauf si elles sont encodées.

Tension sémantique

Il existe une tension entre l'exploration d'espace d'états de la vérification de modèles et le raisonnement symbolique des preuves : la vérification de modèles fournit des contre-exemples et des traces concrètes tandis que la preuve donne des garanties générales mais pas forcément des contre-exemples.

Synthèse

La vérification de modèles est une méthode algorithmique souvent exhaustive qui évalue si un modèle formel satisfait une spécification en parcourant ou en représentant symboliquement son espace d'états et en renvoyant des résultats de satisfaction ou des contre-exemples diagnostiques.