Model checking avec NuSMV : logiques CTL et LTL, algorithme de point fixe et vérification de l'exclusion mutuelle
Le model checking expliqué simplement : structures de Kripke, logiques temporelles CTL et LTL, algorithme de point fixe démontré, BDD et model checking borné, un protocole d'exclusion mutuelle erroné et celui de Peterson vérifiés avec NuSMV, avec le contre-exemple et le rôle de l'équité.
https://www.electronics-engineering.com/fr/model-checking-nusmv-ctl-ltl-exclusion-mutuelle-peterson/
Un programme concurrent, un protocole de communication, le contrôleur d’un ascenseur ou d’un feu de circulation peuvent fonctionner pendant des mois puis se bloquer dans une combinaison d’événements qu’aucun test n’avait essayée. Les méthodes formelles vérifient un système de façon exhaustive, en démontrant qu’une propriété vaut dans toutes les exécutions possibles. Il y a deux grandes voies : la démonstration automatique de théorèmes, où le système et la propriété sont des formules d’une logique et où l’on construit une preuve, puissante mais qui a souvent besoin de l’aide de l’utilisateur ; et le model checking, où le système est une machine à états finis, les propriétés sont des formules de logique temporelle, et un algorithme explore tous les états atteignables. Cette leçon explique le model checking et les logiques CTL et LTL, déduit l’algorithme de point fixe, et l’utilise avec NuSMV, le model checker symbolique développé par la FBK et les universités de Trente, de Gênes et Carnegie Mellon, sur un classique : l’exclusion mutuelle entre deux processus.
L’idée en mots simples
Imaginez devoir vérifier qu’un carrefour à deux feux ne montre jamais le vert aux deux routes. Essayer à la main quelques suites d’événements ne suffit pas : l’erreur pourrait se cacher dans une combinaison rare. Le model checking construit la carte de toutes les situations où le système peut se trouver (les états) et de tous les passages possibles entre elles, et la parcourt entièrement à la recherche d’une situation interdite. S’il en trouve une, il renvoie le contre-exemple : la suite exacte de pas qui mène à l’erreur, précieuse pour corriger la conception. S’il n’en trouve pas, la propriété est démontrée pour toutes les exécutions.
Le modèle : les structures de Kripke
Le système est décrit comme une structure de Kripke : un ensemble fini d’états
, des états initiaux
, une relation de transition
(de chaque état on peut aller à un ou plusieurs états suivants) et, pour chaque état, l’ensemble des propositions atomiques vraies en lui (par exemple « le processus 1 est dans sa section critique »). Les exécutions sont les chemins infinis qui partent d’un état initial ; en les dessinant tous à partir d’un état, on obtient l’arbre de calcul.
Les logiques temporelles CTL et LTL
Les opérateurs temporels parlent de ce qui arrive le long d’un chemin :
:
est vraie à l’état suivant ;
:
est vraie un jour (dans le futur) ;
:
est vraie toujours (globalement) ;
:
est vraie jusqu’à ce que
devienne vraie, et
devient vraie un jour.
La LTL (logique temporelle linéaire) évalue ces formules sur chaque chemin : une formule LTL est vraie si elle l’est sur tous les chemins. La CTL (logique d’arbre de calcul) met un quantificateur de chemin devant chaque opérateur :
(pour tous les chemins) ou
(il existe un chemin). Ainsi
dit « dans tout état atteignable
est vraie » (une propriété de sûreté : rien de mal n’arrive jamais),
« il existe un moyen d’atteindre
»,
« sur tout chemin
est vraie un jour » (une propriété de vivacité : quelque chose de bien arrive un jour),
« toute requête
est servie un jour ».

L’algorithme : les points fixes
Le model checking CTL calcule, pour chaque sous-formule, l’ensemble des états où elle est vraie, à partir des propositions atomiques. Les opérateurs temporels utilisent des points fixes.
Théorème. L’ensemble des états qui satisfont
est le plus petit point fixe de l’équation
, où
sont les états où
est vraie et
les états qui ont au moins un successeur dans
; on l’obtient en itérant
,
jusqu’à ce que plus rien ne change.
Démonstration. Par récurrence,
est l’ensemble des états d’où l’on atteint
en au plus
pas : c’est vrai pour
, et un état atteint
en au plus
pas s’il est déjà dans
ou s’il a un successeur qui y arrive en au plus
. La suite est croissante et les états sont en nombre fini, donc elle se stabilise après au plus
pas, sur l’ensemble des états d’où
est atteignable en un nombre quelconque de pas : exactement
. Tout autre point fixe contient
et est fermé par
, donc il contient tous les
: celui-ci est le plus petit. ∎
Les autres opérateurs se ramènent à ceux-ci :
;
est le plus grand point fixe de
;
. Le coût est linéaire en le nombre d’états et de transitions.
L’explosion des états. Le problème est que les états croissent exponentiellement avec les variables : 20 variables booléennes donnent un million d’états, 300 en donnent plus que les atomes de l’univers. NuSMV utilise deux remèdes : le model checking symbolique, qui représente les ensembles d’états comme des formules booléennes compressées avec des BDD (binary decision diagrams), et le model checking borné, qui cherche des contre-exemples de longueur limitée en transformant le problème en une formule pour un solveur SAT.
Un exemple : l’exclusion mutuelle
Deux processus partagent une ressource (une imprimante, une variable) et ne doivent jamais se trouver ensemble dans la section critique. Chaque processus a un drapeau qu’il lève quand il veut entrer. Un ordonnanceur choisit à chaque instant quel processus avance d’un pas : la variable
du modèle représente ce choix, laissé libre (non déterministe) pour que NuSMV examine tous les entrelacements possibles.
Le protocole naïf. Chaque processus vérifie que le drapeau de l’autre est baissé, puis lève le sien et entre. Il semble correct, mais NuSMV répond que la propriété
est fausse et montre un contre-exemple de 6 pas : le processus 1 vérifie (le drapeau de l’autre est baissé), puis l’ordonnanceur laisse le processus 2 vérifier aussi (le drapeau du premier est encore baissé), et tous deux entrent. Le défaut est que « vérifier » et « lever le drapeau » sont deux pas séparés.

L’algorithme de Peterson (1981) ajoute une variable de tour : chaque processus lève son drapeau, puis donne le tour à l’autre, et attend que l’autre ne veuille pas entrer ou que le tour soit le sien. NuSMV vérifie que :
est vraie : l’exclusion mutuelle est garantie ;
est vraie, et la formule LTL équivalente
l’est aussi : celui qui attend finit par entrer ;- les états atteignables sont 68 sur 400 possibles.
L’importance de l’équité. La deuxième propriété n’est vraie qu’avec les clauses FAIRNESS s = 1 et FAIRNESS s = 2, qui ne considèrent que les exécutions où l’ordonnanceur laisse chaque processus avancer une infinité de fois. En les retirant, NuSMV trouve un contre-exemple : le processus 1 attend, et l’ordonnanceur ne fait avancer que le processus 2 pour toujours, qui reste inactif. Ce n’est pas un défaut du protocole mais du modèle de l’ordonnanceur : le model checking oblige aussi à expliciter ces hypothèses.
Une application : vérifier un site web
Les mêmes idées s’appliquent à des objets très différents d’un protocole. Dans le mémoire de fin d’études dont ce sujet est né (Politecnico di Bari, 2002), un site web est automatiquement transformé en un modèle NuSMV, et les propriétés qu’un bon site devrait avoir sont écrites en CTL. Le programme développé, DaWeb, lit les pages, construit le modèle et lance le model checker.
L’idée est de voir le site comme une machine à états : la variable Paging dit sur quelle page se trouve le visiteur, la variable State dit si l’on est en train de regarder une page (page) ou de suivre un lien (link). Chaque lien de la page est une transition possible ; le choix est non déterministe, parce que le visiteur peut cliquer sur n’importe quel lien. Les propriétés typiques du mémoire sont :
- atteignabilité de la page d’accueil : de toute page on peut revenir à l’index,
AG (State = page -> EF Paging = index); - cohérence des liens : tout lien mène à une page existante,
AG (State = link -> EX State = page); - contraintes de parcours : par exemple, dans une boutique en ligne, on n’atteint le paiement que par l’identification ;
- propriétés du contenu des pages (pages internes ou externes, statiques ou dynamiques, taille maximale, date de mise à jour), vérifiées de la même façon avec des variables supplémentaires.
Voici une petite boutique en ligne dans le style du mémoire, avec deux erreurs mises exprès : la page du produit a un lien vers offers, qui n’existe pas, et la page de confirmation de la commande n’a aucun lien.
MODULE main
VAR
State : {page, link};
Paging : {index, catalogue, product, cart, login, payment, confirmation, contacts, offers};
ASSIGN
init(State) := page;
init(Paging) := index;
next(State) := case
State = page : link; -- a link is clicked
State = link & Paging = offers : link; -- missing page: stuck on the link
TRUE : page; -- the link leads to an existing page
esac;
next(Paging) := case
State = link : Paging; -- at the destination the page does not change
Paging = index : {catalogue, contacts, login};
Paging = catalogue : {product, index};
Paging = product : {cart, catalogue, offers}; -- offers does not exist: broken link
Paging = cart : {login, catalogue};
Paging = login : {payment, index};
Paging = payment : {confirmation, cart};
Paging = confirmation : confirmation; -- page without links
Paging = contacts : index;
TRUE : Paging;
esac;
SPEC AG (State = page -> EF (State = page & Paging = index))
SPEC AG (State = link -> EX (State = page))
SPEC AG (Paging = cart -> !E [ !(Paging = login) U (Paging = payment) ])NuSMV trouve les deux erreurs et les explique par un contre-exemple :
- la première propriété est fausse : le contre-exemple est le chemin index, login, payment, confirmation ; de la page de confirmation il n’y a aucun moyen de revenir à la page d’accueil ;
- la deuxième est fausse : le chemin index, catalogue, product, offers atteint un lien qui ne mène à aucune page ;
- la troisième est vraie : depuis le panier, il n’y a aucun chemin qui atteigne le paiement sans passer par l’identification.
L’avantage sur un simple programme qui vérifie les liens un par un est que les propriétés portent sur des parcours et non sur des pages isolées : « après le panier on passe toujours par l’identification » ne se vérifie pas en regardant une page à la fois. Pour les sites dynamiques, le mémoire ajoute des paramètres (par exemple l’utilisateur identifié) et vérifie les propriétés pour chaque valeur.
Le model checking en pratique
Le model checking est utilisé dans la conception des circuits numériques (après le célèbre bogue de la division du Pentium en 1994, Intel a adopté systématiquement la vérification formelle pour les unités arithmétiques et les protocoles de caches), dans les protocoles de communication, dans les logiciels embarqués des avions et des trains et dans les systèmes de commande industriels. Edmund Clarke, Allen Emerson et Joseph Sifakis ont reçu le prix Turing en 2007 pour l’avoir inventé. Les limites sont l’explosion des états et la nécessité d’un modèle fini fidèle : on vérifie le modèle, non le code réel, sauf si l’on utilise des outils qui extraient le modèle du code.
Résumé
- Le model checking explore tous les états atteignables d’un système fini et vérifie des propriétés de logique temporelle, en renvoyant un contre-exemple quand elles sont fausses.
- La CTL quantifie sur les chemins (A, E) et sur le temps (X, F, G, U) ; la LTL évalue les formules sur chaque chemin.
- L’algorithme calcule des ensembles d’états avec des points fixes : le plus petit pour EF et EU, le plus grand pour EG.
- NuSMV représente les ensembles d’états avec des BDD et cherche des contre-exemples avec le model checking borné.
- Dans l’exemple, le protocole naïf viole l’exclusion mutuelle en 6 pas ; celui de Peterson est sûr et vivant, sous l’hypothèse d’un ordonnanceur équitable.
- La même méthode vérifie un site web : pages et liens deviennent états et transitions, et NuSMV trouve les liens brisés, les pages en impasse et les parcours interdits.
Le mémoire complet, avec le programme DaWeb, les modèles de sites et toutes les spécifications, peut se lire ici : mémoire complet (PDF, en italien).
Le code
Le modèle de Peterson pour NuSMV (fichier peterson.smv). On le vérifie avec NuSMV peterson.smv ; le modèle naïf est le même, avec les états idle, check, setf, crit et sans la variable de tour.
-- Peterson's algorithm: "I want to enter" flag and turn variable t
MODULE main
VAR
pc1 : {idle, flag, turn, wait, crit};
pc2 : {idle, flag, turn, wait, crit};
f1 : boolean;
f2 : boolean;
t : {1, 2};
s : {1, 2}; -- the process that takes a step at this instant
ASSIGN
init(pc1) := idle; init(pc2) := idle;
init(f1) := FALSE; init(f2) := FALSE; init(t) := 1;
next(pc1) := case
s = 1 & pc1 = idle : {idle, flag};
s = 1 & pc1 = flag : turn;
s = 1 & pc1 = turn : wait;
s = 1 & pc1 = wait & (!f2 | t = 1) : crit;
s = 1 & pc1 = crit : idle;
TRUE : pc1;
esac;
next(f1) := case
s = 1 & pc1 = flag : TRUE;
s = 1 & pc1 = crit : FALSE;
TRUE : f1;
esac;
next(pc2) := case
s = 2 & pc2 = idle : {idle, flag};
s = 2 & pc2 = flag : turn;
s = 2 & pc2 = turn : wait;
s = 2 & pc2 = wait & (!f1 | t = 2) : crit;
s = 2 & pc2 = crit : idle;
TRUE : pc2;
esac;
next(f2) := case
s = 2 & pc2 = flag : TRUE;
s = 2 & pc2 = crit : FALSE;
TRUE : f2;
esac;
next(t) := case
s = 1 & pc1 = turn : 2; -- give the turn to the other
s = 2 & pc2 = turn : 1;
TRUE : t;
esac;
FAIRNESS s = 1
FAIRNESS s = 2
SPEC AG !(pc1 = crit & pc2 = crit)
SPEC AG (pc1 = wait -> AF pc1 = crit)
LTLSPEC G (pc1 = wait -> F pc1 = crit)La sortie de NuSMV :
-- specification AG !(pc1 = crit & pc2 = crit) is true
-- specification AG (pc1 = wait -> AF pc1 = crit) is true
-- specification G (pc1 = wait -> F pc1 = crit) is trueLe même algorithme en Python, avec les états explorés un à un (model checking à états explicites) : parcours en largeur des états atteignables, recherche du plus court contre-exemple et calcul de
comme plus petit point fixe.
from collections import deque
# Explicit-state model checking: the same two NuSMV models, states as tuples (pc1, pc2, f1, f2, t, s)
def step_peterson(st, i):
"""Moves of process i (1 or 2) in state st; returns the possible next (pc_i, f_i, t)."""
pc, f, t = st[i - 1], st[1 + i], st[4]
other_f, me, other = st[4 - i], i, 3 - i
if pc == "idle":
return [("idle", f, t), ("flag", f, t)]
if pc == "flag":
return [("turn", True, t)]
if pc == "turn":
return [("wait", f, other)]
if pc == "wait":
return [("crit", f, t)] if (not other_f or t == me) else [("wait", f, t)]
return [("idle", False, t)] # crit: leaves and lowers its flag
def step_naive(st, i):
pc, f, t = st[i - 1], st[1 + i], st[4]
other_f = st[4 - i]
if pc == "idle":
return [("idle", f, t), ("check", f, t)]
if pc == "check":
return [("setf", f, t)] if not other_f else [("check", f, t)]
if pc == "setf":
return [("crit", True, t)]
return [("idle", False, t)]
def successors(st, step):
s = st[5] # the process that moves now
out = []
for pc, f, t in step(st, s):
new = list(st)
new[s - 1], new[1 + s], new[4] = pc, f, t
for s_next in (1, 2): # the next process is chosen nondeterministically
new[5] = s_next
out.append(tuple(new))
return out
def explore(step):
init = [("idle", "idle", False, False, 1, s) for s in (1, 2)]
parent = {x: None for x in init}
queue = deque(init)
while queue: # breadth-first search: the first bad state found has the shortest path
x = queue.popleft()
for y in successors(x, step):
if y not in parent:
parent[y] = x
queue.append(y)
return parent
def EF(states, step, goal):
"""Set of states from which goal can be reached: least fixpoint Z = goal ∪ pre(Z)."""
Z = {x for x in states if goal(x)}
while True:
new = Z | {x for x in states if any(y in Z for y in successors(x, step))}
if new == Z:
return Z
Z = new
bad = lambda x: x[0] == "crit" and x[1] == "crit"
for name, step in (("naive", step_naive), ("Peterson", step_peterson)):
parent = explore(step)
states = set(parent)
viol = [x for x in states if bad(x)]
print(f"{name}: {len(states)} reachable states; AG !(crit1 & crit2) {'false' if viol else 'true'}")
if viol:
x, path = viol[0], []
while x is not None:
path.append(x); x = parent[x]
print(" counterexample of", len(path) - 1, "steps:", " -> ".join(f"{p[0]}/{p[1]}" for p in reversed(path)))
good_init = all(x not in EF(states, step, bad) for x in states if x[:5] == ("idle", "idle", False, False, 1))
print(" initial states outside EF(crit1 & crit2):", good_init)En l’exécutant, on obtient pour le protocole naïf 32 états atteignables, la propriété fausse et le contre-exemple de 6 pas idle/idle, check/idle, setf/idle, setf/check, setf/setf, crit/setf, crit/crit ; pour Peterson 68 états atteignables, comme dans NuSMV, et la propriété vraie, avec l’état initial en dehors de l’ensemble
.






Sono l'autore di questa pagina su «Model checking con NuSMV: logiche CTL e LTL, algoritmo a punto fisso e verifica della mutua esclusione». Se qualcosa non è chiaro, se vi serve un esempio in più o volete approfondire un punto, scrivetelo qui sotto nei commenti: rispondo personalmente. Se la pagina vi è stata utile, lasciate un voto con le stelle in cima all'articolo.I am the author of this page on “Model checking with NuSMV: CTL and LTL logics, fixpoint algorithm and verification of mutual exclusion”. If something is unclear, if you need another example or want to go deeper into a point, write it in the comments below: I answer personally. If the page was useful, leave a star rating at the top of the article.