Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Recommandée par l'auteur Systèmes d'information

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/

Cette page vous a-t-elle été utile ? Notez-la :
moyenne 4,0 sur 1 vote

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 S, des états initiaux S_0, une relation de transition R \subseteq S\times S (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 :

  • \mathbf X\,p : p est vraie à l’état suivant ;
  • \mathbf F\,p : p est vraie un jour (dans le futur) ;
  • \mathbf G\,p : p est vraie toujours (globalement) ;
  • p\ \mathbf U\ q : p est vraie jusqu’à ce que q devienne vraie, et q 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 : \mathbf A (pour tous les chemins) ou \mathbf E (il existe un chemin). Ainsi \mathbf{AG}\,p dit « dans tout état atteignable p est vraie » (une propriété de sûreté : rien de mal n’arrive jamais), \mathbf{EF}\,p « il existe un moyen d’atteindre p », \mathbf{AF}\,p « sur tout chemin p est vraie un jour » (une propriété de vivacité : quelque chose de bien arrive un jour), \mathbf{AG}(r \to \mathbf{AF}\,c) « toute requête r est servie un jour ».

Quatre opérateurs CTL sur l'arbre de calcul
Les nœuds rouges sont les états où p est vraie. AG p : p est vraie dans tout état de tout chemin. EF p : au moins un chemin atteint p. AF p : sur tout chemin on rencontre p un jour. EG p : il existe un chemin le long duquel p est toujours vraie.

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 \mathbf{EF}\,p est le plus petit point fixe de l’équation Z = P \cup \text{pre}(Z), où P sont les états où p est vraie et \text{pre}(Z) les états qui ont au moins un successeur dans Z ; on l’obtient en itérant Z_0 = P, Z_{k+1} = P \cup \text{pre}(Z_k) jusqu’à ce que plus rien ne change.

Démonstration. Par récurrence, Z_k est l’ensemble des états d’où l’on atteint P en au plus k pas : c’est vrai pour k = 0, et un état atteint P en au plus k + 1 pas s’il est déjà dans P ou s’il a un successeur qui y arrive en au plus k. La suite est croissante et les états sont en nombre fini, donc elle se stabilise après au plus |S| pas, sur l’ensemble des états d’où P est atteignable en un nombre quelconque de pas : exactement \mathbf{EF}\,p. Tout autre point fixe contient P et est fermé par \text{pre}, donc il contient tous les Z_k : celui-ci est le plus petit. ∎

Les autres opérateurs se ramènent à ceux-ci : \mathbf{AG}\,p = \lnot\mathbf{EF}\lnot p ; \mathbf{EG}\,p est le plus grand point fixe de Z = P \cap \text{pre}(Z) ; \mathbf{AF}\,p = \lnot\mathbf{EG}\lnot p. 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 s 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é \mathbf{AG}\,\lnot(crit_1 \land crit_2) 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.

Le contre-exemple du protocole naïf
Les états des deux processus dans les six pas du contre-exemple trouvé par NuSMV : le processus 1 vérifie et se prépare, le processus 2 vérifie avant que le premier ait levé son drapeau, et au pas 6 tous deux sont dans la section critique.

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 :

  • \mathbf{AG}\,\lnot(crit_1 \land crit_2) est vraie : l’exclusion mutuelle est garantie ;
  • \mathbf{AG}(wait_1 \to \mathbf{AF}\,crit_1) est vraie, et la formule LTL équivalente \mathbf G(wait_1 \to \mathbf F\,crit_1) 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 true

Le 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 \mathbf{EF} 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 \mathbf{EF}(crit_1 \land crit_2).

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x