Chap 7 1

Chapitre 7

Vérification de modèles:

Automates de Büchi et SPIN(Holzmann Chap. 6)

(réserve à la biblio)

http://w3.uqo.ca/luigi/INF6001/

INF6001 Chap 7 2

Propriétés d’états et exécutions (chaînes)

X=13 X=X/2+1 X>0

X=X/2

X≤0

s0

Nous pouvons affirmer des propriétés pour:

Des états: p.ex. à l’état s1, X=13 toujours (invariant)pas besoin de logique temporelle ici

Des exécutions, p.ex. x≤0 ou x≤0, mais pas x≤0.Observez que dans ce cas le contrôle est sur les transitions.

s1 s2 s3

X: entier et / a résultat entier

(tronqué)

.État d’acceptation

INF6001 Chap 7 3

Comment vérifier les propriétés temporelles?

Nous avons une machine dont nous pouvons observer certaines propriétés, p.ex. qu’une variable a toujours une certaine valeur ou une propriété temporelle

Solution: exécuter la machine en parallèle avec une autre machine qui

observe et vérifie ces propriétés – composition synchrone nous pouvons aussi vérifier une propriété négative, c.-à.-d.

que la machine ne satisfait pas une propriété never automata

INF6001 Chap 7 4

Vérification de modèle

Modèle à vérifierAutomate exprimant

des propriétés à vérifier

Composition synchrone

On peut dire que les deux côtés sont des modèles: L’automate est un modèle d’une propriété logique à vérifier

INF6001 Chap 7 5

Exemple

s1

p

AB pour vérifier p

Cet AB synchronise avec un autre automate seulement si la propriété p reste toujours vraie, à toutes les transitions

Si elle reste toujours vraie, il est content...

INF6001 Chap 7 6

Acceptation dans les automates de Büchi

Pour chaque expression de logique temporelle, il y a un AB qui accepte les chaînes qui satisfont cette expression Il existe un algorithme pour effectuer cette construction, pas

discuté dans ce coursUn automate régulier accepte toutes les chaînes qui

conduisent à un état final

Un AB accepte toutes les chaînes infinies qui passent un nombre infini de fois par un état final

INF6001 Chap 7 7

Exemple

s0 s1

p

p

vrai

AB pour vérifierp

Cet AB est prêt à accepter des transitions où p est faux,mais il est content seulement quand p devient vrai.

Exercice:

INF6001 Chap 7 8

X=13 X=X/2+1 X>0

X≤0

s0 s1 s2 s3 X: entier et / a résultat entier

(tronqué)

Prouver x≤0 pour ce modèle

s0 s1

x≤0

x≤0

vrai

Automate de Büchi à utiliser

X=X/2

Schéma de Solution x≤0

INF6001 Chap 7 9

s0,s0X=13, ¬X≤0

s1,s0

X=1, ¬X≤0

s2,s0

s2,s0

X=7, ¬X≤0

s3,s0 s2,s1

X=0, X≤0 X=0, vrai

X=13, vrai

s0,s1

s1,s1

Etc.

Après ça, le système continue normalement mais la propriété est satisfaite, l’AB reste en état s1

X=7, ¬X≤0

X=1, ¬X≤0

X=7, vrai

X=13 X=X/2+1 X>0

X≤0

s0 s1 s2 s3

X=X/2

s0 s1

x≤0

x≤0

vrai

Composition synchrone

Comme dans la composition synchrone, deux transitions peuvent être composées quand elles sont compatibles, p.ex.

INF6001 Chap 7 10

X=7, ¬X≤0

INF6001 Chap 7 11

Incomplétude des AB

L’AB de gauche ne considère pas le cas de recevoir un pCeci simplifie la compréhension et la vérification, car les

transitions qui ne conduisent pas au résultat désiré ne sont pas prises en considération

s1

p

s1

p

s2 p

=

p

réjet!

INF6001 Chap 7 12

Non-déterminisme …

Considérez la propriété:

soleil (enfin toujours soleil) Après un certain moment, il y aura toujours du soleil Mais à partir de quand?

Si un jour il y aura du soleil, ce n’est pas nécessairement le début de l’époque du soleil…

Donc advenant une journée de soleil, il faut en même temps Considérer la possibilité qu’elle soit la première journée de soleil de

l’époque du soleil Ou la possibilité que non, l’époque du soleil viendra plus tard

INF6001 Chap 7 13

Exemple de nondéterminisme

AB pour vérifier que p (enfin toujours p)

‘vrai’ accepte p et autres mais après un certain p, il n’accepte que des p après

Cet AB est nondéterministe, mais avec raison …

s0 s1

vrai

p

p

INF6001 Chap 7 14

Comparer avec AB déterministe

s0 s1

¬p

p

p

L’AB ci-dessous n’est pas bon pour p Car s’il y a un 1er p qui n’est pas suivi par p il rejette.Il faut dans ce cas continuer à chercher un p futur après lequel p

Cet AB montre aussi les limites de l’expressivité des opérateurs , car ce qu’il exprime (après le 1er p, toujours p) n’est pas exprimable avec ces opérateurs seulement.

faut utiliser U: ¬ p U p

INF6001 Chap 7 15

Nondéterminisme des AB

Le nondéterminisme est une caractéristique importante des AB

s0 s1

true

p

p

p

Il est important de comprendre qu’une transition étiquetée vrai peut toujours être prise, même s’il y a des autres transitions possibles.

Quand un p est rencontré, l’automate peut ou bien boucler sur s0, ou bien changer à s1.

Ceci est justifié par le fait que s’il y a des p initiaux après lesquels p est faux, la propriété n’est pas nécessairement fausse!

Donc des p peuvent être ignorés et la propriété peut encore être vraie plus tard

finalement toujours p

Exemple concret de fonctionnement de nondéterminisme

INF6001 Chap 7 16

p

q

p

Nous voulons vérifier si p ici s0 s1

true

p

p

Nous commençons dans l’état global (m0,s0).

La machine à vérifier produit son premier p: Nous ne savons pas

si nous devons l’apparier avec un p (m1,s1).

ou avec un true (m1,s0).

Nous devons considérer les deux possibilitésPlus tard nous saurons que l’apparier avec un true était le bon choixLe q suivant sera aussi apparié avec un true, puis enfin on peut apparier les p avec les p

m0

m1

m2

Exécution non-déterministe avec échec de parcours

INF6001 Chap 7 17

m0,s0

m1,s1

p, p

m1,s0

p, true

m2,s1

q, true

p, p

p

q

p

s0 s1

true

p

pm0

m1

m2 p

Exercices

Faites-vous des autres exemples

INF6001 Chap 7 18

INF6001 Chap 7 19

Transformation Büchi aut. déterm.

Étant donné un automate Büchi ou semblable, il est toujours possible de donner un automate ‘régulier’ et déterministe équivalent

Cependant ce dernier pourrait être beaucoup plus complexe Avant tout, il faut compléter l’automate, y incluant toutes les transitions et états

non spécifiés En deuxième, il faut enlever le nondéterminisme Si une transition p peut aller à un état s1 ou à un état s2, nous la faisons aller à

l’état {s1,s2} Donc l’ensemble des états d’un automate déterministe D équivalent à un

automate nondéterministe ND, qui a |ND| états, peut avoir jusqu’à 2|ND| -1 états Son ensemble d’états est l’ensemble de tous les sous-ensembles de ND -1 car l’ensemble vide n’est pas un état…

Construction en principe exponentielle (pourquoi?)

V. un manuel quelconque de théorie des automates

La même exécution, mais avec automate déterministe

INF6001 Chap 7 20

m0,s0

m1,s0

m1, s1

p,p p, true

m2,s1

q, true

p, p

Nous voyons ici de manière implicite que l’état m1, s1 n’a pas de suite

Exercice

Trouver un automate déterministe qui fait le même travail que l’AB pour p

Vous verrez qu’il existe, mais il est plus compliqué

INF6001 Chap 7 21

INF6001 Chap 7 22

Autre exemple impliquant U (until fort)

s0 s1

p

q

vrai

p U q

Deux cas limites

AB pour la tautologie: vrai, ou vrai, ou vrai ou pp etc. Cet AB accepte toujours tout.

AB pour la contradiction: faux, ou faux, ou faux ou pp etc. Il n’y a pas d’AB pour la contradiction: il est vide Il n’y a pas de modèles pour les systèmes contradictoires Il n’est pas possible de vérifier un système contradictoire

INF6001 Chap 7 23

s1

vrai

Exemples impliquant opérateurs propositionnels(utilisant http://www.lsv.ens-cachan.fr/~gastin/ltl2ba/index.php)

INF6001 Chap 7 24

F p || F q = F (p || q) p || Fq

G F p && G q = G ( F p && q ) G ( F p || q )

Quelques surprises … (possiblement)

Utilisant l’outil vous pourrez vérifier que: p U q peut être vrai sans aucun p p -> q a besoin seulement de q pour être vrai, mais il est

aussi vrai si p est faux dorénavant p -> ○q est vrai dans deux cas:

p est dorénavant faux ou q est vrai dans le prochain état

La logique temporelle n’est pas vraiment intuitive au début …

INF6001 Chap 7 25

INF6001 Chap 726

Efficacité de calcul

Nous ne prenons pas en considération pour l’instant les aspects d’efficacité de calcul

Cependant la présence de nondéterminisme implique le besoin de retour en arrière si on a pris la mauvaise branche… ou bien de tenir en compte de toutes les branches possible à chaque pas

Tenir compte de ces possibilités cause inefficacité dans le calcul

s0 s1

true

p

p

INF6001 Chap 7 27

Exemple

s0 s1vrai

p

p toujours finalement p(infiniment souvent p)

vrai

Accepte seulement quand il continuera d’y avoir des p dans le futur

INF6001 Chap 7 28

Parfois le nondéterminisme n’est pas nécessaire

s0 s1¬p

p

p toujours finalement p(infiniment souvent p)

¬p p

INF6001 Chap 7 29

Exemple: utiliser les équivalences

p = p

Un p doit être trouvé, après on peut trouver autre chose, mais il faut retourner sur p

s0 s1

vrai

vrai

p

toujours finalement p

INF6001 Chap 7 30

Exemple (pas très intuitif, mais…)

(p q) = ( p q)

Dorénavant, un p est suivi toujours par un q.

Utilisant la formule de droite, nous voyons que:

à cause du fait que (faux vrai) = vrai, p n’a pas besoin de se produire afin que q se produise et rende la formule vraie

INF6001 Chap 7 31

Exemple continuation

(p q) = ( p q)

s0 s1

p q

vrai

q

vrai

Accepte tant que p q est vrai, peut aussi passer à un état où un q doit se produire plus tard

Dorénavant, un p est toujours suivi par un q

Pour bien comprendre…

Pour bien comprendre l’AB précédent, considérez le fait que un q peut se produire tout seul, même sans p

Mais dès qu’un p se vérifie, l’automate passe à s1, qui n’est pas un état d’acceptation

Il retourne et peut rester dans l’état d’acceptation seulement après un q

À ce moment là, nous retournons à l’état initial dans lequel nous pourrons avoir (ou non …) des autres p et q

INF6001 Chap 7 32

INF6001 Chap 7 33

Autres exemples

D’autres exemples plus complexes sont dans le livre de Holzmann, Chap. 6

En pratique, on a rarement besoin d’utiliser des formules complexes Ou on simplifie l’assertion pour les éviter...

Un programme pour trouver un AB pour une formule LTL: http://www.lsv.ens-cachan.fr/~gastin/ltl2ba/

Büchi store, base de données d’AB: http://buchi.im.ntu.edu.tw/

Puissance: LTL et AB

Le formalisme des AB est plus puissant que celui de la LTL On peut construire des AB qui ne peuvent pas être exprimés

en LTL Intuitivement, ceci peut être justifié par le fait qu’en LTL on

ne peut définir que des propriétés de comportement générales, tandis que avec un AB on peut spécifier des comportements détaillés complexes et à plusieurs stages Exercice: Faites vos expériences à ce sujet! Cherchez à définir

des AB qui n’ont pas un correspondant en LTL

INF6001 Chap 7 34

INF6001 Chap 7 35

Mais la construction du modèle est le problème!

Problème fondamental: Soit S l’automate global (modèle) du système en considération S est construit à partir des différentes composantes du système Nous avons vu (Chapitre 2) que le problème de construire S peut être

de complexité exponentielle à cause du fait que nous devons considérer l’entrelacement des actions des composantes de S

Bonne nouvelle, S n’a pas besoin d’être construit complet auparavant Il peut être construit au fur et à mesure qu’il est composé avec

l’automate de Büchi et n’a pas besoin d’être gardé entièrement en mémoire

‘on the fly model checking’

Deux manières de prouver ou refuser une propriété

Prouver que tous les comportements du système satisfont la propriété

Chercher un comportement du système qui satisfait la négation de la propriété! (un contrexemple) Cette deuxième stratégie pourrait aboutir plus rapidement,

car dès qu’un contrexemple est trouvé, nous savons que la propriété

est fausse et nous n’avons pas besoin de continuer

si on veut s’assurer que quelqu’un est honnête, il pourrait être difficile de le démontrer en principe donc on lui propose des comportements possibles et on attend de voir si jamais il se comporte de

manière malhonnête … ce processus est une sorte de test systématique.

INF6001 Chap 7 36

Comportements honnêtes

Comportements malhonnêtes

Test d’honnêtété: deux manières de contrôler

INF6001 Chap 7

Comport. de A

37

Comport. de A

Dans ce cas, on examine tousles comportements de A et pour chacun on détermine s’il est honnête

Dans ce cas, on cherche s’ily a des comportement contraires: il suffit d’en trouver un seul

L’importance des contrexemples

Il pourrait être possible de construire le modèle complet d’un système et de contrôler qu’un ensemble de propriétés est toujours valable, dans toute évolution possible du système. Dans ce cas, super!

Sinon, les model checkers d’aujourd’hui permettent de développer le système pas par pas (on the fly) et de contrôler la violation de propriétés à chaque pas. Si à un certain point on trouve une violation, ceci est un contre-

exemple à la propriété, une erreur qu’il faut corriger C’est encore une trouvaille importante.

INF6001 Chap 7 38

INF6001 Chap 7 39

Propriétés d’un système Pour prouver qu’ un système jouit des propriétés spécifiées par des

expression de logique temporelle, il faut montrer que tous les comportements du système ont ces propriétés

Nous appelons ‘langage’ d’un automate l’ensemble de chaînes, l’ensemble des comportements, qu’il accepte

Propriétés ou exigences positives Toutes les exécutions du système satisfont aux propriétés Pour prouver une exigence positive, nous devons prouver que le langage du

système est inclus dans le langage de l’AB qui exprime l’exigence Propriétés ou exigences négatives

Aucune exécution du système ne satisfait aux propriétés Le langage du système et le langage de l’exigence doivent avoir intersection

vide Si l’intersection est non vide, les exécutions dans l’intersection sont des contre-

exemples, montrant dans quelles situations la propriété est violée

Exemple simple

Supposons qu’on veuille contrôler que dans un système:

x<4Nous pourrions chercher à développer le modèle complet

pour voir si ceci est toujours vraiOu nous pouvons chercher un contre-exemple après

chaque pas de création du modèle, utilisant

¬ x ≥ 4Au moment où nous trouvons la violation de cette propriété

(x=5, p.ex.), nous avons trouvé un contre-exemple et donc probablement une erreur à corriger.

INF6001 Chap 7 40

INF6001 Chap 7 41

Never claims: exigences négatives

Donc il est plus efficace de contrôler l’absence de comportements défendus plutôt que de contrôler tous les comportements permis

L’AB approprié est obtenu par négation d’une formule de logique temporelle

INF6001 Chap 7 42

Exemple basé sur la formula précédente:

(p q) = ( p q)

Dorénavant, un p est suivi toujours par un q

Cette formule est fausse s’il y aura un p et puis aucun q

INF6001 Chap 7 43

Automate négation: never automata

Supposons que nous voulions qu’un comportement niant la formule précédente soit détecté:

(p q) = par définition de ( p q) = par loi de dualité ( p q) = par loi de De Morgan(p q) = par dualité

(p q)

s0 s1

true

p q

q

Si un comportement tombe dans l’état s1, il n’est pas conforme aux exigences

INF6001 Chap 7 44

Un système à vérifier

Exercice: calculer la machine globale de P1 et P2(ils ne communiquent pas).

(source: H.v.d.Schoot)

INF6001 Chap 7 45

Une propriété à vérifier

Nous désirons voir si f = w dFaisant la négation (never claim)¬f = ¬(w d) =¬(¬w d) =w ¬ d =¬f =w ¬ dUn AB Büchi pour A¬f est celui-ci où = true = a b c d v wS\{d} = ¬d = a b c v w S\{d,w} = ¬d ¬w = a b c v

¬d¬w

¬d true

d s’est produit et ¬f est faux, f est vrai

Notation utilisée dans cet exemple

Σ est l’ensemble de toutes les actions possibles Donc Σ est équivalent à true, prend tout Si = {a, b,c, d}, alors Σ est (a v b v c v d)

Σ \ {a,b} est l’ensemble de toutes les actions possibles moins d et w, donc il prend tout moins d et w, il est donc (¬a ¬b)

INF6001 Chap 7 46

INF6001 Chap 7 47

Exemple (source: H.v.d.Schoot)

Nous désirons voir si

¬f =w ¬ d¬f est vrai pour P1XP2

ssi A¬f accepte au moins une des chaînes de P1XP2

Voici la composition de P1,P2, et A¬f Les états finaux sont des états où w s’est produit, et non d, car P1 a tombé dans un cycle de {a,b}

V.cycles en jaune.

La propriété ¬f est vraie, étant donné que nous venons de trouver des exemples pour ¬f .

Donc la propriété f est fausse dans P1XP2.

INF6001 Chap 7 48

Cycles d’acceptation

Selon la définition d’acceptation dans les automates de Büchi, seulement les chaînes infinies qui passent un nombre infini de fois par un état final sont acceptées

Seulement ces chaînes sont des contre-exemples Donc dans P1XP2 nous ne sommes pas intéressés aux calculs qui finissent

dans l’état (13,22)

Un exemple de cycle d’acceptation: v; w; a; b; a; b; a; b … Exercice: trouver les autres

INF6001 Chap 7 49

Preuve d’exigences négatives

Étant donné un système S et une formule LTL f à contrôler pour S Construire un AB A¬f pour la négation de f

Il n’accepte que les chaînes qui satisfont ¬f, qui violent f Calculer la composition synchrone des machines S et A¬f Contrôler si le langage accepté par cet automate est vide

S’il est vide, toutes les exécutions de S satisfont f S’il a des exécutions, il y a au moins une exécution dans S qui est

un contre-exemple pour f En pratique, la composition synchrone souvent n’a pas

besoin d’être calculée dans sa totalité car dès qu’on trouve un contre-exemple on a prouvé que l’exigence n’est pas satisfaite

INF6001 Chap 7 50

Efficacité de ces procédures

Par un argument théorique on montre que, pour un système S qui contient |S| états et un AB Af qui vérifie une propriété f et contient |Af| états

Le nombre d’états à considérer pour la preuve d’inclusion est entre |Af| + |S| et |Af| x |S|

Le nombre d’états à considérer pour la preuve d’intersection vide est entre 0 et |Af| x |S|

En fait, la preuve de l’intersection vide peut aboutir tout de suite (un contrexemple est trouvé au tout début)

Pour cette raison, la méthode utilisée par SPIN est celle de prouver l’exigence négative, l’intersection vide

Comportementshonnêtes

Comportementsmalhonnêtes

Comport. de A

Comport. de A

Dans notre exemple

Notez que dans l’exemple, pour trouver que la propriété never est satisfaite, il est suffisant de compléter la partie jaune du diagramme de composition

Les autres états n’ont pas besoin d’être visitésRéduction de complexité d’approx. 50% par rapport à

exploration complète Il est suffisant de visiter 6 états sur 12

INF6001 Chap 7 51

INF6001 Chap 7 52

En mots…

Gerard J. Holzmann : The Model Checker SPIN. IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 23, NO. 5, MAY 1997

A positive claim requires us to prove that the language of the system (i.e., all its executions) is included in the language of the claim. A negative claim, on the other hand, requires us to prove that the intersection of the language of the system and of the claim is empty. The size of the state space for a language inclusion proof is at most the size of the Cartesian product of the (automata representing) system and claim, and at least the size of their sum. The worst-case state space size to prove emptiness of a language intersection is still the size of the Cartesian product of system and claim, but, in the best case, it is zero. Note that if no initial portion of the invalid behavior represented by the claim appears in the system, the intersection contains no states. SPIN, therefore, works with negative correctness claims and solves the verification problem by language intersection.

Comportementshonnêtes

Comportementsmalhonnêtes

Comport. de A

Comport. de A

INF6001 Chap 7 53

Exploration de l’espace d’états global

Si une exécution erronée est détectée, l’exploration de l’espace d’états peut être arrêtée

Sinon, l’exploration doit continuer jusqu’à ce que tous les états auront été explorés À moins que l’algorithme n’excède le temps ou la mémoire

disponible…

Nous devons donc utiliser un mécanisme qui soit capable de déterminer si nous venons de générer un état déjà généré précédemment

INF6001 Chap 7 54

Algorithme “supertrace”

SPIN est fourni d’une méthode extrêmement efficace d’analyser les états d’énormes machines à états

Concernant le problème de contrôler que tous les états ont été explorés Un bit par état: exploré ou non Algorithme d’hachage pour mettre en correspondance un état du système avec

l’adresse du bit qui le représenteL’adresse dira ‘vrai’ si l’état correspondent a été exploré, ‘faux’ sinon.Cependant nous pouvons avoir des faux résultats à cause des

‘doubles affectations’ possibles dans les algorithmes de hachagePour une histoire complète, v.

http://www.spinroot.com/spin/Doc/Book91_PDF/ch11.pdf Section 11.4

INF6001 Chap 7 55

Autre problème: obtenir l’AB optimal

Un problème moins important, mais aussi important, est d’avoir un AB optimal

Les algorithmes connus de génération d’AB à partir de formules de logique temporelle ne garantissent pas l’optimalité de l’AB généré

Sujet de recherche encore ouvert…Même la définition d’optimalité n’est pas claire

INF6001 Chap 7 56

AB déterministes et non

w ¬ d

s0 s1

d

w d

d

À noter que l’AB de gauche est déterministe, ce qui simplifie le calcul de la composition

L’AB à droite est nondéterministe, il est plus facile à comprendre mais le calcul de la composition peut être plus complexe

=

Représentation de la machine never en SPIN

INF6001 Chap 7 57

s0 s1

d

w d

d

never {S0_init : if :: (!d) -> goto S0_init :: (w && !d) -> goto accept_S1 fi; accept_S1 : if :: (!d) -> goto accept_S1 fi; }

INF6001 Chap 7 58

Stutter extension rule: extension bègue?

Pour prendre en considération le case des chaînes finiesOn peut supposer que toute exécution finie soit étendue

par une séquence infinie d’événements vides qui ne causent pas de changements d’état: Événements ε: le bégaiement

De cette manière, une propriété est vraie pour l’exécution étendue si elle est vraie pour l’exécution finie originale P.ex. p est vrai pour une exécution qui contient une seule

transition pour laquelle p est vrai

a a a

ε

INF6001 Chap 7 59

Exercice: Exemple avec non-déterminisme

Étudier l’exemple à la page 558 et suivantes du livre de Holzmann sur SPIN Basé cependant sur des concepts un peu différents de ceux

que nous avons vu dans ce cours

Notez qu’à partir de l’état (s0,s0,2,s0) il faut considérer deux possibilités. À cause de la transition true dans l’automate de Büchi qui est

toujours possible.

INF6001 Chap 7 60

Remerciements…

Pour la partie suivante de ce cours, j’ai utilisé les notes de: Theo Ruys

http://wwwhome.cs.utwente.nl/~ruys/

INF6001 Chap 7 61

Analyse de modèles, Model Checking

byte n;proctype Aap() { do :: n++ :: noot!MIES od}

Modèle M

[] (n<3)

Propriété

Analyseur

Espace d’états

OUIPropriétésatisfaite

NON,+ contre_exemple

|M

Explosion d’états.

INF6001 Chap 7 62

Définition[Clarke & Emerson 1981]

“Model checking is an automated technique that, given a finite-state model of a system and a logical property, systematically checks whether this property holds for (a given initial state in) that model.”

INF6001 Chap 7 63

À quel point faisons-nous cette analyse

Approche traditionnelle: Dans le processus de conception, on crée un modèle abstrait du processus

avant de commencer l’implantation L’analyse est faite sur ce modèle L’implantation est puis obtenue à partir du modèle par un procédé de

raffinement Approche dite ‘moderne’:

Le modèle est obtenu à partir de l’implémentation par un procédé d’abstraction Qui est automatisable, au moins en principe

Cette dernière approche a été rendue nécessaire par le fait que les développeurs ne veulent pas faire des détours dans leur travail

Elle demande des algorithmes extrêmement efficaces car les modèles obtenus à partir de l’implantation contiennent beaucoup de détails

INF6001 Chap 7 64

To cope with the state space explosion.

Approches Classique et “Moderne”

ModelChecker

AbstractVerification Model

(initial) Design

Implementation

(manual)abstractions

refinementtechniques

‘Modern’ Approach

abstraction techniques

AbstractVerification Model

Implementation

C, Java

Abstraction is the key activityin both approaches.

Classic Approach

INF6001 Chap 7 65

Promela et SPIN

Promela est un langage pour la spécification des systèmes répartis

SPIN est l’analyseur (model checker) et son point de départ est la théorie que nous venons de discuter

INF6001 Chap 7 66

Promela/SPIN: un système pour l’analyse des modèles

Promela/SPIN est un système développé à partir du début des années 1990 par Gerhard Holzmann, un chercheur d’AT&T Labs 1991 version initiale 1995 réductions d’ordre partiel 1997 minimisation de l’AB 2003 inclusion de code C et Breadth-First Search …

Il est un des analyseurs de modèles les plus connus et efficaces

INF6001 Chap 7 67

Atouts de ce système

Automatique, sans intervention humaine Après la définition du problème

Implantation très efficace en CInterface convivialeExcellent appuiIl combine un grand nombre de connaissances sur le sujet

Plusieurs chercheurs chevronnés ont participé à son dévéloppement Reconnu par l’ACM entre les réalisations majeures en

informatique Software System Award avec Unix, TeX, Tcl/TK, Java

INF6001 Chap 7 68

Promela

Protocol/Process Meta LanguageInfluencé par le CSP de HoareEt par C

Mais il est un langage pour la spécification de modèles Pas un langage d’implantation

De compréhension facile pour les implémenteursAdmet la communication

Par variables globales partagées Synchrone, directe Asynchrone, par canaux

INF6001 Chap 7 69

Promela Model

A Promela model consist of:

type declarations

channel declarations

global variable declarations

process declarations

[init process]

behaviour of the processes:local variables + statements

- simple vars- structured vars- vars can be accessed by all processes

initialises variables andstarts processes

chan ch = [dim] of {type, …} asynchronous: dim > 0 rendez-vous: dim == 0

mtype, constants,typedefs (records)

INF6001 Chap 7 70

mtype = {REQ,ACK};typedef Msg { byte a[2]; mtype tp;} ;chan toR = [1] of {Msg};bool flag;

proctype Sender() { Msg m; ... m.a[0]=2; m.a[1]=7; m.tp = REQ; toR ! m;}

proctype Receiver(byte n) { Msg m; ... toR ? m; }

init { run Sender(); run Receiver(2); }

Promela Model

A Promela model corresponds to a (usually very large, but) finite transition system, so

no unbounded data no unbounded channels no unbounded processes no unbounded process creation

channel declaration

creates processes

global variable

local variable

message types (constants)

“record” declaration

Example of a Promela model

Inputs/outputs

INF6001 Chap 7 71

Processes (1)

A process type (proctype) consist of a name a list of formal parameters local variable declarations bodyproctype Sender(chan in; chan out) { bit sndB, rcvB; do :: out ! MSG, sndB -> in ? ACK, rcvB; if :: sndB == rcvB -> sndB = 1-sndB :: else -> skip fi od}

name

local variables

body

formal parameters

The body consist of a sequence of statements.

Une sortie et puis ->

INF6001 Chap 7 72

StatementsThe body of a process consists of a sequence of

statements. A statement is either executable: the statement can

be executed immediately. blocked: the statement cannot be executed.

An assignment is always executable.An expression is also a statement; it is executable if it

evaluates to non-zero.2 < 3 always executablex < 27 only executable if value of x is smaller 273 + x executable if x is not equal to –3

executable/blockeddepends on the global

state of the system.

INF6001 Chap 7 73

Statements (2)

The skip statement is always executable. “does nothing”, only changes process’ process counter

A run statement is only executable if a new process can be created (remember: the number of processes is bounded).int x;proctype Aap() { int y=1; skip; run Noot(); x=2; x>2 && y==1; skip;}

Can only become executable if some other process makes x greater than 2.

Executable if Noot can be created…

Statements are separated by a semi-colon: “;”.

or by the equivalent “->”

INF6001 Chap 7 74

Statements (3)

assert(<expr>); The assert-statement is always executable. If <expr> evaluates to zero, SPIN will exit with an error, as the <expr>

“has been violated”. The assert-statement is often used within Promela models, to check

whether certain properties are always valid in a state.

proctype monitor() { assert(n <= 3);}

proctype receiver() { byte msg; ... toReceiver ? msg; assert(msg != ERROR); ...}

INF6001 Chap 7 75

Interleaving Semantics

Promela processes execute concurrently.

Non-deterministic scheduling of the processes.

Processes are interleaved (statements of different processes do not occur at the same time). exception: rendez-vous communication.

All statements are atomic; each statement is executed without interleaving with other processes.

Each process may have several different possible actions enabled at each point of execution. only one choice is made, non-deterministically.

= randomly

INF6001 Chap 7 76

Bit alterné en SPIN http://spinroot.com/spin/Man/Manual.html

1 #define MAX5 2 3 mtype = { mesg, ack, nak, err }; 4

5 proctype sender(chan in, out) 6 { byte o, s, r; 7 8 o=MAX-1; 9 do 10 :: o = (o+1)%MAX; /* next msg */ 11 again: if 12 :: out!mesg(o,s) /* send */ 13 :: out!err(0,0) /* distort */ 14 :: skip /* or lose */ 15 fi; 16 if 17 :: timeout -> goto again 18 :: in?err(0,0) -> goto again 19 :: in?nak(r,0) -> goto again 20 :: in?ack(r,0) -> 21 if 22 :: (r == s) -> goto progress 23 :: (r != s) -> goto again 24 fi 25 fi; 26 progress: s = 1-s /* toggle seqno */ 27 od 28 } 29

30 proctype receiver(chan in, out) 31 { byte i; /* actual input */ 32 byte s; /* actual seqno */ 33 byte es; /* expected seqno */ 34 byte ei; /* expected input */ 35 36 do 37 :: in?mesg(i, s) -> 38 if 39 :: (s == es) -> 40 assert(i == ei); 41 progress: es = 1 - es; 42 ei = (ei + 1)%MAX; 43 if 44 /* send, * :: out!ack(s,0) 45 /* distort */ :: out!err(0,0) 46 /* or lose :: skip 47 fi 48 :: (s != es) -> 49 if 50 /* send, */ :: out!nak(s,0) 51 /* distort */ :: out!err(0,0) 52 /* or lose */ :: skip 53 fi 54 fi 55 :: in?err -> 56 out!nak(s,0) 57 od 58 } 59 60 init { 61 chan s_r = [1] of { mtype,byte,byte }; 62 chan r_s = [1] of { mtype,byte,byte }; 63 atomic { 64 run sender(r_s, s_r); 65 run receiver(s_r, r_s) 66 } 67 }

We want to verify that data that is sent can only be delivered to the receiver without any deletions or reorderings, despite the possibility of arbitrary message loss. The assertion on line 40 verifies precisely that. Note that if it were ever possible for the protocol to fail to meet the above requirement, the assertion can be violated(autres détails intéressants dans le site)

INF6001 Chap 7 77

Xspin in a nutshellXspin allows the user to

edit Promela models (+ syntax check) simulate Promela models

random interactive guided

verify Promela models exhaustive bitstate hashing model

additional features Xspin suggest abstractions to a Promela model (slicing) Xspin can draw automata for each process LTL property manager Help system (with verification/simulation guidelines)

with dialog boxes to setvarious options and directivesto tune the verification process

INF6001 Chap 7 78

Conclusions sur SPIN

Bases théoriques très solides Logique temporelle linéaire et automates de Büchi

Outil très performantL’outil de vérification le plus utilisé dans notre domaine

Excellent survol pratique sur SPIN et plusieurs des concepts que nous avons vu: http://plan9.bell-labs.com/sys/doc/spin.html

Exemples très pratiques

Vérification de la conception d’un four microondes: Est-il possible que dans des situations particulières le four

puisse cuir avec la porte ouverte?

Vérification de la conception d’un avion: Est-il possible que les freins moteur puissent être activés

avant que l’avion touche le sol?

Conception de matériel Etc. etc.

INF6001 Chap 7 79

Reconnaissance

Les vastes applications du Model Checking ont motivé l’octroi du prix Turing à trois de ses inventeurs principaux: Sifakis, Clarke, Emerson

INF6001 Chap 7 80

INF6001 Chap 7 81

Application de la logique temporelle

Il faut savoir que: La logique temporelle linéaire LTL que nous venons de

discuter n’est qu’une des logiques temporelles qui ont été étudiées Il y a aussi la logique linéaire à branchements Computational Tree

Logic, le calcul, etc. Elle ou ces autres logiques peuvent être utilisées pour

n’importe quel système pour lequel il est possible de construire un automate global Donc avec SDL, LOTOS, Réseaux de Petri…

Structures de Kripke

Au lieu des automates de Büchi, on utilise parfois des structures semblables qui s’appellent ‘structures de Kripke’.

Différence principale est que les assertions logiques dans les automates de Büchi se trouvent sur les arêtes, dans les structures de Kripke se trouvent sur les états.

Un type de structure peut être transformé dans l’autre.Le point important est que certaines analyses peuvent

être faites plus facilement sur une structure que sur l’autre.

INF6001 Chap 7 82

INF6001 Chap 7 83

Example(mais ce n’est pas toujours aussi simple que ça)

Kripke

p,q

p

Büchi: p,qvrai

vrai

p

p

Ceci est {p,q}

Source: Notes de cours de Ofer Strichman, Technion