Analyse statique de programmes et interprétation...

Analyse statique de programmes et interprétation abstraite

Olivier Bouissou

• Intervenants :

• cours et TP assurés par Olivier Bouissou (olivier.bouissou@cea.fr) - CEA LIST.

• Déroulement : 7 séances de 2*2 heures

• séances 1 et 2 : 4 heures de cours.

• séances 3 à 5 : 2 heures de cours et 2 heures de TP

• séance 6 et 7 : 4 heures de TP

Organisation du cours.

2

Date : 29/01/13 04/02/13(lundi) 12/02/13 19/02/13 26/02/13 05/03/13 12/03/13

Cours :

Introduction-

Sémantique concrète

-Sémantique

abstraite

Domaines abstraits

-Intervalles et

octagones -

Itérateur

Analyse de programmes

avec pointeurs.

Combinaison d’analyses

- Produit réduit

Cours d’ouverture - -

TP : - -Domaine

des intervalles

Itérateur -

Widening

Domaine des booléens

- Produit réduit

Au choix Au choix

Organisation du cours : plan du cours.

3

Organisation du cours.

• http://www.lix.polytechnique.fr/~bouissou/cours_ia.html

4

• Objectif : apprendre à construire un analyseur statique par interprétation abstraite.

• introduire les bases théoriques nécessaires (et pas plus).

• introduire, par la pratique et l’exemple, les techniques classiques pour obtenir un analyseur performant et précis.

• Approche pragmatique :

• ce cours ne vise pas à être exhaustif sur la théorie de l’interprétation abstraite.

• on donnera une approche possible, volontairement limitée, permettant de définir un type d’analyse statique.

• on essaiera de donner, en même temps que les résultats théoriques, des techniques de programmation aidant à la construction d’un analyseur.

Organisation du cours : les cours.

5

• Transparents :

• après chaque séance sur le site web.

• certains transparents sont incomplets et seront terminés en cours.

• certaines preuves seront faites au tableau.

Organisation du cours : support de cours.

6

• Objectif :

• mise en pratique des solutions apportées en cours.

• avoir un aperçu des difficultés techniques liées à la réalisation d’un analyseur statique.

• Programmation en OCAML (connaissance de OCAML requise).

• Utilisation de la technologie NEWSPEAK développée chez EADS-IW.

c.f. http://penjili.org/newspeak.html

• A la fin du semestre, vous aurez codé un analyseur statique de programmes C.

Organisation du cours : les TP.

7

• Evaluation pratique : le projet

• à la fin du cours, projet à rendre plus des jalons après certaines séances de TP.

• objectif du projet : coder un analyseur statique par interprétation abstraite.

• les TPs servent de préparation au projet.

• vous pourrez choisir, à partir de la 4ème séance, un thème à approfondir (domaines, itérateur, produit réduit...)

• Evaluation théorique :

• contrôle continu (QCM au début de chaque séance).

• contrôle final (présentation d’article).

Organisation du cours : évaluation.

8

Stages.

• Toujours possible si intéressés.

9

Master STL - NI505 - IA

static const NUM TRANSF2_B06_C3 = 7.830931E static const NUM TRANSF2_B06_C4 = 1.362407 static const NUM TRANSF2_B06_C5 = -6.844878 static const NUM LIM_A1_E2 = 8.000000E+00 static const NUM LIM_A1_E3 = -8.000000E+0 static const NUM K_A2_E2 = -6.236000E-01;static const NUM AFFECT_N_1_E1 = 2.000000E static const NUM SWITCH_N_E93_E1 = 3.500000 static const NUM SWITCH_N_A6_E1 = 0.000000 static const BOO AFFECT_B_1_E1 = FALSE; static NUM PADN5; /*Mod JS*/

/*

SUB(1,PLDQCMMMOY,PDQMM,X611Z01)

*/

SUB(1,PDQCMMMOY,PDQMM,X611Z01)

/*

SUB(1,PDQCMMMOY,0,X611Z01)

*/

/*Fin Mod JS*/

K(A1,X611Z01,K_A1_E2,X611Z02)

AFFECT_B(1,AFFECT_B_1_E1,BOFFACS1)

TRANSF2(B06,X611Z02,X611Z02,X611Z02,BOF Z17,TRANSF2_B06_C1, \

TRANSF2_B06_C2,TRANSF2_B06_C3,TRANSF2 ANSF2_B06_C5)

LIM(A1,X611Z17,LIM_A1_E2,LIM_A1_E3,PLEPS ADD(2,PFOSV,PLEPS,X611Z16)

K(A2,PDQMM,K_A2_E2,X611Z03)

AFFECT_N(1,AFFECT_N_1_E1,X611Z04)

INVNUM(1,X611Z04,PADN5)

?Cours 1

Problématique de la vérification automatique de

programmes.

Quelques bugs célèbres. (1)

• 04 juin 1996, premier vol du nouveau lanceur Ariane 5.

• Après 37 secondes de vol, le lanceur dévie de son chemin, puis explose.

• Perte sèche pour Ariane Espace : 700M€

• Résultat de l’enquête :

• conversion non protégée d’un nombre flottant vers un entier non-signé

• l’ordinateur de vol a considéré que l’altitude était négative

11

Quelques bugs célèbres. (2)• 25 février 1991, les missiles Patriot

protègent les militaires américains.

• Dans la nuit, un des missile rate sa cible (un Scud irakien)

• Bilan humain : 28 soldats américains tués.

• Résultat de l’enquête :

• pour intercepter un missile, il faut avoir une mesure du temps.

• le calcul du temps était effectué en nombre flottant

• une erreur de 10-4% a entraîné une déviation de 137 mètres.

12

Quelques bugs célèbres. (3)

• 14 août 2003, coupure de courant dans le Nord-Est des Etats-Unis.

• 256 centrales électriques s’arrêtent touchant 55 millions de personnes.

• Résultat de l’enquête :

• problème physique sur une des centrales.

• propagation à tout le réseau car le système d’alerte était en panne

• panne du système d’alerte : race condition.

13

Quelques bugs célèbres. (4)

• Septembre 1997, le USS Yorktown CG est immobilisé en pleine mer

• Les propulseurs sont en panne et le bateau restera plusieurs heures à l’arrêt.

• Coût pour aller le chercher : 1M$

• Résultat de l’enquête :

• système informatique gère à distance la propulsion des moteurs

• une faute de frappe d’un opérateur entraîne une division par zéro

14

Quelques bugs célèbres. (5)

• Démonstration par Volvo de son système de freinage d’urgence.

15

Quelques bugs célèbres. (5)

• Démonstration par Volvo de son système de freinage d’urgence.

15

Quelques bugs célèbres. (5)

• Démonstration par Volvo de son système de freinage d’urgence.

15

Quelques bugs célèbres. (5)

• Démonstration par Volvo de son système de freinage d’urgence.

15

Que nous apprennent ces exemples ?

• Les systèmes sont de plus en plus complexes :

• plusieurs millions de lignes de code.

• plusieurs processus interagissant entre eux.

• Les bugs peuvent venir de partout :

• erreur de spécification.

• erreur de précision numérique.

• mauvaise utilisation par un utilisateur.

16

Comment éviter ces bugs ?• Matériel plus tolérant :

• redondance des calculateurs (tolérance aux pannes),

• diagnostique en ligne (détection des pannes).

• Code mieux conçu :

• développement suivant des normes strictes (plusieurs équipes indépendantes, pas d’utilisation de bibliothèques externes, ...),

• relecture manuel de tout le code écrit.

17

Comment éviter ces bugs ?• Matériel plus tolérant :

• redondance des calculateurs (tolérance aux pannes),

• diagnostique en ligne (détection des pannes).

• Code mieux conçu :

• développement suivant des normes strictes (plusieurs équipes indépendantes, pas d’utilisation de bibliothèques externes, ...),

• relecture manuel de tout le code écrit.

17

Année

OS

LoC (million)

1993 1994 1996 2000 2001 2005Windows

NT 3.1Windows

NT 3.5Windows

NT 4.0Windows

2000Windows XP Windows

Vista Beta 2

6 10 16 29 40 50

Comment éviter ces bugs ?• Matériel plus tolérant :

• redondance des calculateurs (tolérance aux pannes),

• diagnostique en ligne (détection des pannes).

• Code mieux conçu :

• développement suivant des normes strictes (plusieurs équipes indépendantes, pas d’utilisation de bibliothèques externes, ...),

• relecture manuel de tout le code écrit.

17

Il est donc nécessaire de disposer d’outils automatiques de vérification de programmes permettant de trouver des bugs et/ou de prouver leur absence.

Vérification de programmes.

• Définition : assurer qu’un programme :

• fait ce qu’il doit faire.

• ne fait pas ce qu’il ne doit pas faire.

• Toujours par rapport à un critère d’observation :

• spécification complète, formelle du programme (par ex: la fonction calcule la factorielle du nombre donné en argument).

• jeu d’objectifs à atteindre (par ex: le programme intercepte tous les missiles pendant 1000h).

• jeu de propriétés à respecter (par ex: le programme ne fait aucune division par zéro).

• Problématique de la vérification : étant donné un programme et un ensemble de propriétés, prouver que le programme vérifie ces propriétés

18

Exemples de propriétés :

•

• Temps d’exécution < 10ms.

•

Un exemple très classique.

• Trois techniques de vérification :

• test.

• preuve totale.

• preuve partielle (model-checking et interprétation abstraite).

int fact(int n) { int r,i; r = 1;i=1; for (i=2; i<=n; i++) { r=r*i; } return r;}

∀n ∈ [0, 232 − 1], fact(n) = n!

∀n ∈ [0, 100], r ≥ 0

19

Exemples de propriétés :

•

• Temps d’exécution < 10ms.

•

Un exemple très classique.

• Trois techniques de vérification :

• test.

• preuve totale.

• preuve partielle (model-checking et interprétation abstraite).

int fact(int n) { int r,i; r = 1;i=1; for (i=2; i<=n; i++) { r=r*i; } return r;}

∀n ∈ [0, 232 − 1], fact(n) = n!

∀n ∈ [0, 100], r ≥ 0

19

Analyse dynamique

Analyse statique

Exemples de propriétés :

•

• Temps d’exécution < 10ms.

•

Un exemple très classique.

• Trois techniques de vérification :

• test.

• preuve totale.

• preuve partielle (model-checking et interprétation abstraite).

int fact(int n) { int r,i; r = 1;i=1; for (i=2; i<=n; i++) { r=r*i; } return r;}

∀n ∈ [0, 232 − 1], fact(n) = n!

∀n ∈ [0, 100], r ≥ 0

19

Analyse dynamique

Analyse statique

Utilisées industriellement

Analyse dynamique : test.• On construit des scénarios de tests :

• manuellement.

• automatiquement via des critères de couverture du code...

• On joue les tests puis on vérifie les résultats :

• manuellement.

• automatiquement via des observateurs.

• Test exhaustif impossible pour les systèmes industriels complexes.

• On peut seulement trouver des bugs et jamais prouver leur absence.

E.W. Dijkstra: «Program testing can be used to show the presence of bugs, but never to show their absence!»

20

Test: exemples.

21

int fact(int n) { int r,i; r = 1;i=1; for (i=2; i<=n; i++) { r=r*i; } return r;}

int abs(int n) { int r; if (n>=0) r=n; else r=-n; return r;}

• Spécifications : 0<n<20• Jeu de tests : n=0,2,19• Sorties: r=0,2,109641728

int fact(int n) { int r,i; r = 1;i=1; for (i=2; i<=n; i++) { r=r*i; } return r;}

• Spécifications : n:int• Jeu de tests : n=0,-1,1,MIN_INT,MAX_INT• Sorties: r=0,1,1,-MIN_INT,MAX_INT

Test: exemples.

21

int abs(int n) { int r; if (n>=0) r=n; else r=-n; return r;}

• Spécifications : 0<n<20• Jeu de tests : n=0,2,19• Sorties: r=0,2,109641728

int fact(int n) { int r,i; r = 1;i=1; for (i=2; i<=n; i++) { r=r*i; } return r;}

• Spécifications : n:int• Jeu de tests : n=0,-1,1,MIN_INT,MAX_INT• Sorties: r=0,1,1,-MIN_INT,MAX_INT

Analyse statique : indécidabilité.

(Equivalent) Peut-on construire une machine (i.e. un programme) qui, étant donné un programme P et une propriété H, renvoie 1 si P vérifie H et 0 sinon ?

• Non: pour toute propriété non triviale, ce problème est indécidable, c’est le théorème de Rice (preuve au tableau).

• Cependant :

• on n’écrit pas n’importe quel programme (par exemple pas ceux utilisés pour démontrer l’indécidabilité) et on ne regarde pas n’importe quelle propriété.

• on va donc pouvoir faire de la vérification partielle : on va prouver certaines propriétés sur un certain type de programmes.

(Rappel) Il est donc nécessaire de disposer d’outils automatiques de vérification de programmes permettant de prouver l’absence de bugs.

22

// {n > 1} (hypothèse) // {r=i!} // {r=(i-1)!} // {r=i!} // {r=i!,i=n}

• Idée : (Hoare, Floyd, fin des années 70)

• une propriété est une formule logique. Exemple :

• les entrées sont exprimées comme une formule logique. Exemple :

• le programme est vu comme une implication entre les deux formules.

Analyse statique : preuve de programmes.

23

∀n, fact(n) = n!

∀n, 1 ≤ n

int fact(int n) { int r,i; r = 1;i=1; for (i=2; i<=n; i++) { r=r*i; } return r; }

// {n > 1} (hypothèse) // {r=i!} // {r=(i-1)!} // {r=i!} // {r=i!,i=n}

Exemple : prouver que

• Idée : (Hoare, Floyd, fin des années 70)

• une propriété est une formule logique. Exemple :

• les entrées sont exprimées comme une formule logique. Exemple :

• le programme est vu comme une implication entre les deux formules.

Analyse statique : preuve de programmes.

fact(n) = n!

23

∀n, fact(n) = n!

∀n, 1 ≤ n

int fact(int n) { int r,i; r = 1;i=1; for (i=2; i<=n; i++) { r=r*i; } return r; }

// {n > 1} (hypothèse) // {r=i!} // {r=(i-1)!} // {r=i!} // {r=i!,i=n}

// {fact(n)=n!}

Exemple : prouver que

• Idée : (Hoare, Floyd, fin des années 70)

• une propriété est une formule logique. Exemple :

• les entrées sont exprimées comme une formule logique. Exemple :

• le programme est vu comme une implication entre les deux formules.

Analyse statique : preuve de programmes.

fact(n) = n!

23

∀n, fact(n) = n!

∀n, 1 ≤ n

int fact(int n) { int r,i; r = 1;i=1; for (i=2; i<=n; i++) { r=r*i; } return r; }

// {n > 1} (hypothèse) // {fact(n)=n!}

Exemple : prouver que

• Idée : (Hoare, Floyd, fin des années 70)

• une propriété est une formule logique. Exemple :

• les entrées sont exprimées comme une formule logique. Exemple :

• le programme est vu comme une implication entre les deux formules.

Analyse statique : preuve de programmes.

fact(n) = n!

23

∀n, fact(n) = n!

∀n, 1 ≤ n

int fact(int n) { int r,i; r = 1;i=1; for (i=2; i<=n; i++) { r=r*i; } return r; }

// {n > 1} (hypothèse) // {r=i!}

// {fact(n)=n!}

Exemple : prouver que

• Idée : (Hoare, Floyd, fin des années 70)

• une propriété est une formule logique. Exemple :

• les entrées sont exprimées comme une formule logique. Exemple :

• le programme est vu comme une implication entre les deux formules.

Analyse statique : preuve de programmes.

fact(n) = n!

23

∀n, fact(n) = n!

∀n, 1 ≤ n

int fact(int n) { int r,i; r = 1;i=1; for (i=2; i<=n; i++) { r=r*i; } return r; }

// {n > 1} (hypothèse) // {r=i!} // {r=(i-1)!}

// {fact(n)=n!}

Exemple : prouver que

• Idée : (Hoare, Floyd, fin des années 70)

• une propriété est une formule logique. Exemple :

• les entrées sont exprimées comme une formule logique. Exemple :

• le programme est vu comme une implication entre les deux formules.

Analyse statique : preuve de programmes.

fact(n) = n!

23

∀n, fact(n) = n!

∀n, 1 ≤ n

int fact(int n) { int r,i; r = 1;i=1; for (i=2; i<=n; i++) { r=r*i; } return r; }

// {n > 1} (hypothèse) // {r=i!} // {r=(i-1)!} // {r=i!}

// {fact(n)=n!}

Exemple : prouver que

• Idée : (Hoare, Floyd, fin des années 70)

• une propriété est une formule logique. Exemple :

• les entrées sont exprimées comme une formule logique. Exemple :

• le programme est vu comme une implication entre les deux formules.

Analyse statique : preuve de programmes.

fact(n) = n!

Invariant de boucle.

23

∀n, fact(n) = n!

∀n, 1 ≤ n

int fact(int n) { int r,i; r = 1;i=1; for (i=2; i<=n; i++) { r=r*i; } return r; }

// {n > 1} (hypothèse) // {r=i!} // {r=(i-1)!} // {r=i!} // {r=i!,i=n}

// {fact(n)=n!}

Exemple : prouver que

• Idée : (Hoare, Floyd, fin des années 70)

• une propriété est une formule logique. Exemple :

• les entrées sont exprimées comme une formule logique. Exemple :

• le programme est vu comme une implication entre les deux formules.

Analyse statique : preuve de programmes.

fact(n) = n!

Invariant de boucle.

Si on prouve la terminaison

23

∀n, fact(n) = n!

∀n, 1 ≤ n

int fact(int n) { int r,i; r = 1;i=1; for (i=2; i<=n; i++) { r=r*i; } return r; }

// {n > 1} (hypothèse) // {r=i!} // {r=(i-1)!} // {r=i!} // {r=i!,i=n}

// {fact(n)=n!}

Exemple : prouver que

• Idée : (Hoare, Floyd, fin des années 70)

• une propriété est une formule logique. Exemple :

• les entrées sont exprimées comme une formule logique. Exemple :

• le programme est vu comme une implication entre les deux formules.

Analyse statique : preuve de programmes.

fact(n) = n!

Invariant de boucle.

Si on prouve la terminaison

23

∀n, fact(n) = n!

∀n, 1 ≤ n

• Idée : (Hoare, Floyd, fin des années 70)

• une propriété est une formule logique. Exemple :

• les entrées sont exprimées comme une formule logique. Exemple :

• le programme est vu comme une implication entre les deux formules.

Analyse statique : preuve de programmes.

24

• Difficultés :

• trouver la bonne logique pour exprimer les propriétés qu’on veut prouver.

• automatiser la propagation des formules logiques. Souvent «à l’envers» par de le calcul de weakest precondition.

• prouver la terminaison des boucles.

∀n, fact(n) = n!

∀n, 1 ≤ n

• Idée : (Emerson, Clarke, Sifakis, prix Turing en 2007)

• initialement utilisé pour vérifier le comportement de systèmes de transitions

• une propriété = un ensemble d’états à atteindre ou éviter.

• on parcourt exhaustivement le système pour vérifier la propriété.

Analyse statique : model-checking.

25

• Idée : (Emerson, Clarke, Sifakis, prix Turing en 2007)

• initialement utilisé pour vérifier le comportement de systèmes de transitions

• une propriété = un ensemble d’états à atteindre ou éviter.

• on parcourt exhaustivement le système pour vérifier la propriété.

Analyse statique : model-checking.

Etat initial.

25

• Idée : (Emerson, Clarke, Sifakis, prix Turing en 2007)

• initialement utilisé pour vérifier le comportement de systèmes de transitions

• une propriété = un ensemble d’états à atteindre ou éviter.

• on parcourt exhaustivement le système pour vérifier la propriété.

Analyse statique : model-checking.

Etat initial.

Etat interdit.

25

• Idée : (Emerson, Clarke, Sifakis, prix Turing en 2007)

• initialement utilisé pour vérifier le comportement de systèmes de transitions

• une propriété = un ensemble d’états à atteindre ou éviter.

• on parcourt exhaustivement le système pour vérifier la propriété.

Analyse statique : model-checking.

Etat initial.

Etat interdit.

Etats accessibles.

25

• Idée : (Emerson, Clarke, Sifakis, prix Turing en 2007)

• initialement utilisé pour vérifier le comportement de systèmes de transitions

• une propriété = un ensemble d’états à atteindre ou éviter.

• on parcourt exhaustivement le système pour vérifier la propriété.

Analyse statique : model-checking.

Etat initial.

Etat interdit.

Etats accessibles.

25

• Idée : (Emerson, Clarke, Sifakis, prix Turing en 2007)

• initialement utilisé pour vérifier le comportement de systèmes de transitions

• une propriété = un ensemble d’états à atteindre ou éviter.

• on parcourt exhaustivement le système pour vérifier la propriété.

Analyse statique : model-checking.

Etat initial.

Etat interdit.

Etats accessibles.

25

• Idée : (Emerson, Clarke, Sifakis, prix Turing en 2007)

• initialement utilisé pour vérifier le comportement de systèmes de transitions

• une propriété = un ensemble d’états à atteindre ou éviter.

• on parcourt exhaustivement le système pour vérifier la propriété.

Analyse statique : model-checking.

26

• Pour l’analyse de programme :

• le software model checking applique ces techniques à l’analyse de programme.

• on construit un système de transition à partir du programme (cf cours 2).

• Problème : explosion du nombre d’états. Pour un programme de 106 lignes de code et 104 variables, environ 1024 états possibles.

int fact(int n) { // n!=0 int r,i; r = 2;i=1; for (i=3; i<=n; i++) { r=r*i; } return r; // r != 0}

• Idée : (Cousot, Cousot, 1977)

• on n’a pas besoin de l’état exact d’un programme pour prouver des propriétés.

• on peut, dans certains cas, perdre de l’information de manière conservative.

Analyse statique : interprétation abstraite.

Propriété à prouver : montrer que r n’est pas nul

27

int fact(int n) { // n!=0 int r,i; r = 2;i=1; for (i=3; i<=n; i++) { r=r*i; } return r; // r != 0}

// n != 0

• Idée : (Cousot, Cousot, 1977)

• on n’a pas besoin de l’état exact d’un programme pour prouver des propriétés.

• on peut, dans certains cas, perdre de l’information de manière conservative.

Analyse statique : interprétation abstraite.

Propriété à prouver : montrer que r n’est pas nul

27

int fact(int n) { // n!=0 int r,i; r = 2;i=1; for (i=3; i<=n; i++) { r=r*i; } return r; // r != 0}

// n != 0 // n!=0, r!=0, i!=0

• Idée : (Cousot, Cousot, 1977)

• on n’a pas besoin de l’état exact d’un programme pour prouver des propriétés.

• on peut, dans certains cas, perdre de l’information de manière conservative.

Analyse statique : interprétation abstraite.

Propriété à prouver : montrer que r n’est pas nul

27

int fact(int n) { // n!=0 int r,i; r = 2;i=1; for (i=3; i<=n; i++) { r=r*i; } return r; // r != 0}

// n != 0 // n!=0, r!=0, i!=0 // n!=0, r!=0, i!=0

• Idée : (Cousot, Cousot, 1977)

• on n’a pas besoin de l’état exact d’un programme pour prouver des propriétés.

• on peut, dans certains cas, perdre de l’information de manière conservative.

Analyse statique : interprétation abstraite.

Propriété à prouver : montrer que r n’est pas nul

27

int fact(int n) { // n!=0 int r,i; r = 2;i=1; for (i=3; i<=n; i++) { r=r*i; } return r; // r != 0}

// n != 0 // n!=0, r!=0, i!=0 // n!=0, r!=0, i!=0 // n!=0, r?=0, i!=0

• Idée : (Cousot, Cousot, 1977)

• on n’a pas besoin de l’état exact d’un programme pour prouver des propriétés.

• on peut, dans certains cas, perdre de l’information de manière conservative.

Analyse statique : interprétation abstraite.

Propriété à prouver : montrer que r n’est pas nul

27

int fact(int n) { // n!=0 int r,i; r = 2;i=1; for (i=3; i<=n; i++) { r=r*i; } return r; // r != 0}

// n != 0 // n!=0, r!=0, i!=0 // n!=0, r!=0, i!=0 // n!=0, r?=0, i!=0

• Idée : (Cousot, Cousot, 1977)

• on n’a pas besoin de l’état exact d’un programme pour prouver des propriétés.

• on peut, dans certains cas, perdre de l’information de manière conservative.

Analyse statique : interprétation abstraite.

Propriété à prouver : montrer que r n’est pas nul

Trop peu précis : on ne peut pas conclure.

27

// n > 0

int fact(int n) { // n!=0 int r,i; r = 2;i=1; for (i=3; i<=n; i++) { r=r*i; } return r; // r != 0}

• Idée : (Cousot, Cousot, 1977)

• on n’a pas besoin de l’état exact d’un programme pour prouver des propriétés.

• on peut, dans certains cas, perdre de l’information de manière conservative.

Analyse statique : interprétation abstraite.

Propriété à prouver : montrer que r n’est pas nul

27

// n > 0 // n>0, r>0, i>0

int fact(int n) { // n!=0 int r,i; r = 2;i=1; for (i=3; i<=n; i++) { r=r*i; } return r; // r != 0}

• Idée : (Cousot, Cousot, 1977)

• on n’a pas besoin de l’état exact d’un programme pour prouver des propriétés.

• on peut, dans certains cas, perdre de l’information de manière conservative.

Analyse statique : interprétation abstraite.

Propriété à prouver : montrer que r n’est pas nul

27

// n > 0 // n>0, r>0, i>0 // n>0, r>0, i>0

int fact(int n) { // n!=0 int r,i; r = 2;i=1; for (i=3; i<=n; i++) { r=r*i; } return r; // r != 0}

• Idée : (Cousot, Cousot, 1977)

• on n’a pas besoin de l’état exact d’un programme pour prouver des propriétés.

• on peut, dans certains cas, perdre de l’information de manière conservative.

Analyse statique : interprétation abstraite.

Propriété à prouver : montrer que r n’est pas nul

27

// n > 0 // n>0, r>0, i>0 // n>0, r>0, i>0 // n>0, r>0, i>0

int fact(int n) { // n!=0 int r,i; r = 2;i=1; for (i=3; i<=n; i++) { r=r*i; } return r; // r != 0}

• Idée : (Cousot, Cousot, 1977)

• on n’a pas besoin de l’état exact d’un programme pour prouver des propriétés.

• on peut, dans certains cas, perdre de l’information de manière conservative.

Analyse statique : interprétation abstraite.

Propriété à prouver : montrer que r n’est pas nul

27

// n > 0 // n>0, r>0, i>0 // n>0, r>0, i>0 // n>0, r>0, i>0

int fact(int n) { // n!=0 int r,i; r = 2;i=1; for (i=3; i<=n; i++) { r=r*i; } return r; // r != 0}

• Idée : (Cousot, Cousot, 1977)

• on n’a pas besoin de l’état exact d’un programme pour prouver des propriétés.

• on peut, dans certains cas, perdre de l’information de manière conservative.

Analyse statique : interprétation abstraite.

Propriété à prouver : montrer que r n’est pas nul

Attention : fact(34)=0On a oublié des états du programme (en C,

les entiers sont codés sur 32 bits).

27

• Idée : (Cousot, Cousot, 1977)

• on n’a pas besoin de l’état exact d’un programme pour prouver des propriétés.

• on peut, dans certains cas, perdre de l’information de manière conservative.

Analyse statique : interprétation abstraite.

28

• Difficultés :

• choisir l’information que l’on veut garder.

• signe des variables ? intervalle de valeurs ? variable est constante ou pas ?

• choisir les propriétés que l’on peut prouver.

• s’assurer qu’on n’oublie aucun des états du programme .

Pour résumer : pour un programme à une variable.

P0(x

)

P1(x

)

Pn−

1(x

)

Pn(x

)

⇒ ⇒ ⇒ ⇒

Test Preuve formelle

Model-checking Interprétation abstraite

29

Master STL - IntAbs

Cours 1 bis

Une intuition de l’interprétation abstraite.

Approche de l’interprétation abstraite.

On ne peut pas définir un algorithme qui, pour tout programme P et toute propriété H, renvoie 1 si P vérifie H et 0 sinon.

31

Rappel, théorème de Rice

Etant donnée une propriété non triviale H, on ne peut pas définir un algorithme qui, pour tout programme P, renvoie 1 si P vérifie H et 0 sinon.

Encore pire

Une analyse statique par interprétation abstraite va donc :

• choisir une (ou plusieurs) propriété(s) à vérifier.

• définir une méthode d’analyse telle que, pour tout programme P:

• si le résultat est 0, alors P ne vérifie pas la propriété.

• si le résultat est 1, alors P vérifie la propriété.

• si le résultat est ?, alors on ne peut pas conclure.

Propriétés Le résultat du programme est strictement positif.

Analyse On ne regarde que le signe des variables.

Résultats

Exemples de propriétés et d’analyse.

32

int f(int n) { int r; r=n*n; r=-r; return r;}

int g(int n) { int r,i; r=1; i=0; while (i<=n) r=r+(i++); return r;}

int abs(int n) { int r; if (n>=0) r=n; else r=-n; return r;}

r<=0 r>0 r>=0

✓✗ ?

-5 <= n <= 5

Exemples de propriétés et d’analyse.

33

Propriétés Le programme termine en moins de 50ms.

Analyse On ne calcule que le temps d’exécution d’une instruction.

Résultats

int f(int n) { int r,i; for (i=0;i<=n,i++) r=fun(i); return r;}

t<=48 t<=64

✓ ?

-5 <= n <= 5fun s’exécute en moins de 8ms

int g(int n) { int r,i; n=n+2; for (i=0;i<=n,i++) r=fun(i); return r;}

Propriétés Il n’y a ni division par zéro ni dépassement de capacité.

Analyse On calcule des bornes sur les valeurs des variables à chaque instruction.

Résultats

Exemples de propriétés et d’analyse.

34

int f(int n) { int r,x; ... if (r<=0) x=fun(x)/r; ...}

void h(int n) { int r; while (1) { r=fun(r,n)/r; }}

r=0 1<=r<=10

✗

-5 <= n <= 5

int g(int n) { int r,x; ... if (r<=0) x=fun(x)/r; ...}

r<=0

? ✓

Suite du cours.

• Difficulté majeure : calcul automatique et rapide d’un invariant précis.

• Cette séance : on montre «avec les mains» comment on construit ces invariants.

• 4 prochaines séances : on formalise ce qu’on va faire pendant cette séance.

•Exemple récurrent.

•On suppose que

int fact(int n) { int r,i; r = 1; i=1; for (i=2; i<=n; i++) { r=r*i; } return r;}

n ∈ [1, 5]35

On s’intéresse désormais uniquement à prouver qu’un programme ne fait pas de run time error (RTE).Pour cela, on va essayer de déterminer un invariant numérique sur les variables du programme en chaque ligne de code.

n = 5

Cas facile : une exécution.

36

int fact(int n) { int r,i; r = 1; i=1; for (i=2; i<=n; i++) { r=r*i; } return r;}

• On sait que n=3 .

• Comment montrer qu’il n’y aura pas de RTE ?

• sans exécuter le programme.

n = 5

Cas facile : une exécution.

36

int fact(int n) { int r,i; r = 1; i=1; for (i=2; i<=n; i++) { r=r*i; } return r;}

• On sait que n=3 .

• Comment montrer qu’il n’y aura pas de RTE ?

• sans exécuter le programme.

• On va «simuler» l’exécution du programme en calculant la «trace d’exécution».

• Une trace est une succession d’états qui disent:

• à quel niveau du programme on est (quelle instruction va être exécutée).

• quelle est la valeur de chaque variable.

n = 5

Cas facile : une exécution.

36

int fact(int n) { int r,i; r = 1; i=1; for (i=2; i<=n; i++) { r=r*i; } return r;}

Traces d’exécution du programme.

• Etat de la machine :

• associe à i,n et r une valeur.

• retient le point de contrôle

• Exemple :

int fact(int n) {(0) int r,i;(1) r = 1; i=1;(2) for (i=2; i<=n; i++) {(3) r=r*i; }(4) return r;}

On appelle trace une suite d’états.

37

r := 1i := 2n := 1

Traces d’exécution du programme.

• Etat de la machine :

• associe à i,n et r une valeur.

• retient le point de contrôle

• Exemple :

int fact(int n) {(0) int r,i;(1) r = 1; i=1;(2) for (i=2; i<=n; i++) {(3) r=r*i; }(4) return r;}

On appelle trace une suite d’états.

37

r := 1i := 2n := 1

r := 24i := 5n := 5

r := 120i := 5n := 5

r := 120i := 6n := 5

r := 120i := 5n := 5

r := 1i := 2n := 5

r := 1i := 1n := 5

r := 2i := 2n := 5

r := 2i := 3n := 5

r := 6i := 3n := 5

r := 6i := 4n := 5

r := 24i := 4n := 5

r := ?i := ?n := 5

Il suffit donc de : 1. calculer l’ensemble des traces d’exécution d’un programme.

2. vérifier si une des traces va causer une RTE.

38

Problèmes :

• chaque trace est potentiellement infinie.

• il y a potentiellement un nombre infini de traces.

Solutions :

• on va en calculer une sur-approximation représentable. (abstraction)

• cette sur-approximation sera un invariant vrai pour toutes les traces.

«Pour toute trace, pour tout état de cette trace, on a r e [1,2] »r :=i := n :=

r ∈ [1, 120]

Plusieurs problèmes.

• Comment caractériser mathématiquement une trace : sémantique concrète.

• Comment unifier cet ensemble de traces en un objet mathématique : sémantique collectrice.

• Comment représenter (et calculer) de manière finie une sur-approximation de cet objet : sémantique abstraite.

On veut trouver un invariant valable pour toutes les traces d’exécution.

39

r := 6i := 3n := 5

r := ?i := ?n := 5

Sémantique concrète.

• Sémantique «à petit pas» : on formalise les «flèches» dans les traces d’exécution.

• On définit donc des fonctions de transition entre les états du système.

• Pour chaque élément du langage, on définit une transition de ce type.

• La sémantique du programme est alors la composition de ces transitions.

40

r=1; i=1; r=r*i;

r := 1i := 1n := 5

r := 2i := 3n := 5

Sémantique collectrice.• On peut regrouper, dans une trace, les états correspondants aux mêmes points de

contrôle.

• On travaille alors sur des ensembles d’états : Loc× P�Var→ Z

�

41

r := 1i := 2n := 5

r := 1i := 1n := 5

r := 2i := 2n := 5

r := 2i := 3n := 5

r := 6i := 3n := 5

r := 6i := 4n := 5

r := 24i := 4n := 5

r := 24i := 5n := 5

r := 120i := 5n := 5

r := 120i := 6n := 5

r := ?i := ?n := 5

r := 120i := 5n := 5

r := 1i := 2n := 5

r := 2i := 3n := 5

Sémantique collectrice.• On peut regrouper, dans une trace, les états correspondants aux mêmes points de

contrôle.

• On travaille alors sur des ensembles d’états : Loc× P�Var→ Z

�

41

r := 1i := 1n := 5

r := 2i := 2n := 5

r := 6i := 3n := 5

r := 6i := 4n := 5

r := 24i := 4n := 5

r := 24i := 5n := 5

r := 120i := 5n := 5

r := 120i := 6n := 5

r := ?i := ?n := 5

r := 120i := 5n := 5

r := 1i := 2n := 5

r := 2i := 3n := 5

Sémantique collectrice.• On peut regrouper, dans une trace, les états correspondants aux mêmes points de

contrôle.

• On travaille alors sur des ensembles d’états : Loc× P�Var→ Z

�

41

r := 1i := 1n := 5

r := 2i := 2n := 5

r := 6i := 4n := 5

r := 24i := 4n := 5

r := 24i := 5n := 5

r := 120i := 5n := 5

r := 120i := 6n := 5

r := ?i := ?n := 5

r := 2i := 2n := 5

r := 6i := 3n := 5

r := 120i := 5n := 5

r := 1i := 2n := 5

r := 2i := 3n := 5

r := 6i := 4n := 5

Sémantique collectrice.• On peut regrouper, dans une trace, les états correspondants aux mêmes points de

contrôle.

• On travaille alors sur des ensembles d’états : Loc× P�Var→ Z

�

41

r := 1i := 1n := 5

r := 2i := 2n := 5

r := 24i := 4n := 5

r := 24i := 5n := 5

r := 120i := 5n := 5

r := 120i := 6n := 5

r := ?i := ?n := 5

r := 2i := 2n := 5

r := 6i := 3n := 5

r := 120i := 5n := 5

r := 1i := 2n := 5

r := 2i := 3n := 5

r := 6i := 4n := 5

Sémantique collectrice.• On peut regrouper, dans une trace, les états correspondants aux mêmes points de

contrôle.

• On travaille alors sur des ensembles d’états : Loc× P�Var→ Z

�

41

r := 1i := 1n := 5

r := 2i := 2n := 5

r := 24i := 5n := 5

r := 120i := 5n := 5

r := 120i := 6n := 5

r := ?i := ?n := 5

r := 2i := 2n := 5

r := 6i := 3n := 5

r := 2i := 2n := 5

r := 6i := 3n := 5

r := 24i := 4n := 5

r := 120i := 5n := 5

r := 1i := 2n := 5

r := 2i := 3n := 5

r := 6i := 4n := 5

r := 24i := 5n := 5

Sémantique collectrice.• On peut regrouper, dans une trace, les états correspondants aux mêmes points de

contrôle.

• On travaille alors sur des ensembles d’états : Loc× P�Var→ Z

�

41

r := 1i := 1n := 5

r := 2i := 2n := 5

r := 120i := 5n := 5

r := 120i := 6n := 5

r := ?i := ?n := 5

r := 2i := 2n := 5

r := 6i := 3n := 5

r := 2i := 2n := 5

r := 6i := 3n := 5

r := 24i := 4n := 5

r := 120i := 5n := 5

r := 1i := 2n := 5

r := 2i := 3n := 5

r := 6i := 4n := 5

r := 24i := 5n := 5

Sémantique collectrice.• On peut regrouper, dans une trace, les états correspondants aux mêmes points de

contrôle.

• On travaille alors sur des ensembles d’états : Loc× P�Var→ Z

�

41

r := 1i := 1n := 5

r := 2i := 2n := 5

r := 120i := 6n := 5

r := ?i := ?n := 5

r := 2i := 2n := 5

r := 6i := 3n := 5

r := 2i := 2n := 5

r := 6i := 3n := 5

r := 24i := 4n := 5

r := 2i := 2n := 5

r := 6i := 3n := 5

r := 24i := 4n := 5

r := 120i := 5n := 5

r := 120i := 5n := 5

r := 1i := 2n := 5

r := 2i := 3n := 5

r := 6i := 4n := 5

r := 24i := 5n := 5

Sémantique collectrice.• On peut regrouper, dans une trace, les états correspondants aux mêmes points de

contrôle.

• On travaille alors sur des ensembles d’états : Loc× P�Var→ Z

�

41

r := 1i := 1n := 5

r := 2i := 2n := 5

r := 120i := 6n := 5

r := ?i := ?n := 5

r := 2i := 2n := 5

r := 6i := 3n := 5

r := 2i := 2n := 5

r := 6i := 3n := 5

r := 24i := 4n := 5

r := 2i := 2n := 5

r := 6i := 3n := 5

r := 24i := 4n := 5

r := 120i := 5n := 5

r := 1i := 2n := 5

r := 2i := 3n := 5

r := 6i := 4n := 5

r := 24i := 5n := 5

r := 120i := 6n := 5

Sémantique collectrice (2).

42

• On peut faire pareil pour toutes les traces, on obtient le même graphe.

• L’union de ces graphes constitue la sémantique collectrice du programme.

r := 1i := 1n := 1

r := 1i := 1n := 1

r := 1i := 2n := 1

r := 1i := 1n := 1

r := 1i := 2n := 1

r := ?i := ?n := 1

r := 1i := 1n := 2

r := 1i := 1n := 2

r := 1i := 2n := 2

r := 2i := 3n := 2

r := 1i := 1n := 2

r := 2i := 2n := 2

r := 2i := 3n := 2

r := ?i := ?n := 2

r := 1i := 1n := 3

r := 1i := 1n := 3

r := 1i := 2n := 3

r := 2i := 3n := 3

r := 6i := 4n := 3

r := 1i := 1n := 3

r := 2i := 2n := 3

r := 6i := 3n := 3

r := 6i := 4n := 3

r := ?i := ?n := 3

Sémantique collectrice (2).

42

• On peut faire pareil pour toutes les traces, on obtient le même graphe.

• L’union de ces graphes constitue la sémantique collectrice du programme.

r := 1i := 1n := 1

r := 1i := 1n := 1

r := 1i := 2n := 1

r := 1i := 1n := 1

r := 1i := 2n := 1

r := ?i := ?n := 1

r := 1i := 1n := 2

r := 1i := 1n := 2

r := 1i := 2n := 2

r := 2i := 3n := 2

r := 1i := 1n := 2

r := 2i := 2n := 2

r := 2i := 3n := 2

r := ?i := ?n := 2

r := 1i := 1n := 3

r := 1i := 1n := 3

r := 1i := 2n := 3

r := 2i := 3n := 3

r := 6i := 4n := 3

r := 1i := 1n := 3

r := 2i := 2n := 3

r := 6i := 3n := 3

r := 6i := 4n := 3

r := ?i := ?n := 3

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 1n := 1r := 1i := 2n := 1r := 1i := 1n := 2r := 1i := 2n := 2r := 2i := 3n := 2r := 1i := 1n := 3r := 1i := 2n := 3r := 2i := 3n := 3r := 6i := 4n := 3

r := 1i := 1n := 1r := 1i := 1n := 2r := 1i := 2n := 2

r := 1i := 1n := 3r := 1i := 2n := 3r := 2i := 3n := 3

r := 1i := 2n := 1

r := 2i := 3n := 2

r := 6i := 4n := 3

r := ?i := ?n := 1

r := ?i := ?n := 2

r := ?i := ?n := 3

Correction de la sémantique collectrice.• La sémantique concrète est «incluse» dans la sémantique collectrice.

• Elle contient toutes les traces, plus des traces impossibles.

43

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 1n := 1r := 1i := 2n := 1r := 1i := 1n := 2r := 1i := 2n := 2r := 2i := 3n := 2r := 1i := 1n := 3...

r := 1i := 1n := 1r := 1i := 1n := 2r := 1i := 2n := 2

r := 1i := 1n := 3r := 1i := 2n := 3r := 2i := 3n := 3

r := 1i := 2n := 1

r := 2i := 3n := 2

r := 6i := 4n := 3

r := ?i := ?n := 1

r := ?i := ?n := 2

r := ?i := ?n := 3

Correction de la sémantique collectrice.• La sémantique concrète est «incluse» dans la sémantique collectrice.

• Elle contient toutes les traces, plus des traces impossibles.

43

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 1n := 1r := 1i := 2n := 1r := 1i := 1n := 2r := 1i := 2n := 2r := 2i := 3n := 2r := 1i := 1n := 3...

r := 1i := 1n := 1r := 1i := 1n := 2r := 1i := 2n := 2

r := 1i := 1n := 3r := 1i := 2n := 3r := 2i := 3n := 3

r := 1i := 2n := 1

r := 2i := 3n := 2

r := 6i := 4n := 3

r := ?i := ?n := 1

r := ?i := ?n := 2

r := ?i := ?n := 3

r := 1i := 1n := 1

r := 1i := 1n := 1

r := 1i := 1n := 1

r := 1i := 2n := 1

r := 1i := 2n := 1

r := ?i := ?n := 1

Correction de la sémantique collectrice.• La sémantique concrète est «incluse» dans la sémantique collectrice.

• Elle contient toutes les traces, plus des traces impossibles.

43

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 1n := 1r := 1i := 2n := 1r := 1i := 1n := 2r := 1i := 2n := 2r := 2i := 3n := 2r := 1i := 1n := 3...

r := 1i := 1n := 1r := 1i := 1n := 2r := 1i := 2n := 2

r := 1i := 1n := 3r := 1i := 2n := 3r := 2i := 3n := 3

r := 1i := 2n := 1

r := 2i := 3n := 2

r := 6i := 4n := 3

r := ?i := ?n := 1

r := ?i := ?n := 2

r := ?i := ?n := 3

Correction de la sémantique collectrice.• La sémantique concrète est «incluse» dans la sémantique collectrice.

• Elle contient toutes les traces, plus des traces impossibles.

43

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 1n := 1r := 1i := 2n := 1r := 1i := 1n := 2r := 1i := 2n := 2r := 2i := 3n := 2r := 1i := 1n := 3...

r := 1i := 1n := 1r := 1i := 1n := 2r := 1i := 2n := 2

r := 1i := 1n := 3r := 1i := 2n := 3r := 2i := 3n := 3

r := 1i := 2n := 1

r := 2i := 3n := 2

r := 6i := 4n := 3

r := ?i := ?n := 1

r := ?i := ?n := 2

r := ?i := ?n := 3

r := 1i := 1n := 2

r := 1i := 2n := 2

r := 1i := 1n := 3

r := 1i := 1n := 2

r := 6i := 4n := 3

r := ?i := ?n := 3

r := 1i := 1n := 2

r := 1i := 1n := 1

Correction de la sémantique collectrice.• La sémantique concrète est «incluse» dans la sémantique collectrice.

• Elle contient toutes les traces, plus des traces impossibles.

43

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 1n := 1r := 1i := 2n := 1r := 1i := 1n := 2r := 1i := 2n := 2r := 2i := 3n := 2r := 1i := 1n := 3...

r := 1i := 1n := 1r := 1i := 1n := 2r := 1i := 2n := 2

r := 1i := 1n := 3r := 1i := 2n := 3r := 2i := 3n := 3

r := 1i := 2n := 1

r := 2i := 3n := 2

r := 6i := 4n := 3

r := ?i := ?n := 1

r := ?i := ?n := 2

r := ?i := ?n := 3

r := 1i := 1n := 2

r := 1i := 2n := 2

r := 1i := 1n := 3

r := 1i := 1n := 2

r := 6i := 4n := 3

r := ?i := ?n := 3

r := 1i := 1n := 2

r := 1i := 1n := 1

Si on trouve un invariant valable sur la sémantique collectrice, on aura un

invariant sur toutes les traces d’exécution.

Calcul de la sémantique collectrice.

On part du graphe de flot de contrôle et on propage les états (ex : ).

44

r := ?i := ?n := 1

r := ?i := ?n := 2

r := ?i := ?n := 3

n ∈ {1, 2, 3}

Calcul de la sémantique collectrice.

On part du graphe de flot de contrôle et on propage les états (ex : ).

44

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := ?i := ?n := 1

r := ?i := ?n := 2

r := ?i := ?n := 3

n ∈ {1, 2, 3}

Calcul de la sémantique collectrice.

On part du graphe de flot de contrôle et on propage les états (ex : ).

44

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := ?i := ?n := 1

r := ?i := ?n := 2

r := ?i := ?n := 3

n ∈ {1, 2, 3}

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

Calcul de la sémantique collectrice.

On part du graphe de flot de contrôle et on propage les états (ex : ).

44

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := ?i := ?n := 1

r := ?i := ?n := 2

r := ?i := ?n := 3

n ∈ {1, 2, 3}

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

Calcul de la sémantique collectrice.

On part du graphe de flot de contrôle et on propage les états (ex : ).

44

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := ?i := ?n := 1

r := ?i := ?n := 2

r := ?i := ?n := 3

n ∈ {1, 2, 3}

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 2n := 1

r := 1i := 2n := 2

r := 1i := 2n := 3

Calcul de la sémantique collectrice.

On part du graphe de flot de contrôle et on propage les états (ex : ).

44

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := ?i := ?n := 1

r := ?i := ?n := 2

r := ?i := ?n := 3

n ∈ {1, 2, 3}

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 2n := 1

r := 1i := 2n := 2

r := 1i := 2n := 3

r := 2i := 2n := 2

r := 2i := 2n := 3

r := 1i := 2n := 1

Calcul de la sémantique collectrice.

On part du graphe de flot de contrôle et on propage les états (ex : ).

44

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := ?i := ?n := 1

r := ?i := ?n := 2

r := ?i := ?n := 3

n ∈ {1, 2, 3}

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 2n := 1

r := 1i := 2n := 2

r := 1i := 2n := 3

r := 2i := 2n := 2

r := 2i := 2n := 3

r := 1i := 2n := 1

r := 2i := 3n := 2

r := 2i := 3n := 3

Calcul de la sémantique collectrice.

On part du graphe de flot de contrôle et on propage les états (ex : ).

44

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := ?i := ?n := 1

r := ?i := ?n := 2

r := ?i := ?n := 3

n ∈ {1, 2, 3}

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 2n := 1

r := 1i := 2n := 2

r := 1i := 2n := 3

r := 2i := 2n := 2

r := 2i := 2n := 3

r := 1i := 2n := 1

r := 2i := 3n := 2

r := 2i := 3n := 2

r := 2i := 3n := 3

r := 6i := 3n := 3

Calcul de la sémantique collectrice.

On part du graphe de flot de contrôle et on propage les états (ex : ).

44

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := ?i := ?n := 1

r := ?i := ?n := 2

r := ?i := ?n := 3

n ∈ {1, 2, 3}

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 2n := 1

r := 1i := 2n := 2

r := 1i := 2n := 3

r := 2i := 2n := 2

r := 2i := 2n := 3

r := 1i := 2n := 1

r := 2i := 3n := 2

r := 2i := 3n := 2

r := 2i := 3n := 3

r := 6i := 3n := 3

r := 6i := 4n := 3

Calcul de la sémantique collectrice.

On part du graphe de flot de contrôle et on propage les états (ex : ).

44

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := ?i := ?n := 1

r := ?i := ?n := 2

r := ?i := ?n := 3

n ∈ {1, 2, 3}

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 2n := 1

r := 1i := 2n := 2

r := 1i := 2n := 3

r := 2i := 2n := 2

r := 2i := 2n := 3

r := 1i := 2n := 1

r := 2i := 3n := 2

r := 6i := 4n := 3r := 2

i := 3n := 2

r := 2i := 3n := 3

r := 6i := 3n := 3

r := 6i := 4n := 3

Calcul de la sémantique collectrice.

On part du graphe de flot de contrôle et on propage les états (ex : ).

44

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := ?i := ?n := 1

r := ?i := ?n := 2

r := ?i := ?n := 3

n ∈ {1, 2, 3}

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 1n := 1

r := 1i := 1n := 2

r := 1i := 1n := 3

r := 1i := 2n := 1

r := 1i := 2n := 2

r := 1i := 2n := 3

r := 2i := 2n := 2

r := 2i := 2n := 3

r := 1i := 2n := 1

r := 2i := 3n := 2

r := 6i := 4n := 3r := 2

i := 3n := 2

r := 2i := 3n := 3

r := 6i := 3n := 3

r := 6i := 4n := 3

Problème : explosion combinatoire du nombre d’états.

Sémantique abstraite.• On regroupe dans un même objet mathématique un ensemble d’environnements

• Par exemple, (domaine des intervalles).

• On travaille donc maintenant avec des états abstraits :

P ∈ P�Var→ Z

�

{1, 2, 6, 24, 120} ⊆ [1, 120]

Loc×�Var→ I

�

Méthode de calcul : comme pour la sémantique collectrice, mais sur des états abstraits.

45

r := ⊥i := ⊥n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

r := [1, 1]i := [1, 2]n := [1, 3]

Sémantique abstraite.• On regroupe dans un même objet mathématique un ensemble d’environnements

• Par exemple, (domaine des intervalles).

• On travaille donc maintenant avec des états abstraits :

P ∈ P�Var→ Z

�

{1, 2, 6, 24, 120} ⊆ [1, 120]

Loc×�Var→ I

�

Méthode de calcul : comme pour la sémantique collectrice, mais sur des états abstraits.

45

r := ⊥i := ⊥n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

Sémantique abstraite.• On regroupe dans un même objet mathématique un ensemble d’environnements

• Par exemple, (domaine des intervalles).

• On travaille donc maintenant avec des états abstraits :

P ∈ P�Var→ Z

�

{1, 2, 6, 24, 120} ⊆ [1, 120]

Loc×�Var→ I

�

Méthode de calcul : comme pour la sémantique collectrice, mais sur des états abstraits.

45

r := ⊥i := ⊥n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

Sémantique abstraite.• On regroupe dans un même objet mathématique un ensemble d’environnements

• Par exemple, (domaine des intervalles).

• On travaille donc maintenant avec des états abstraits :

P ∈ P�Var→ Z

�

{1, 2, 6, 24, 120} ⊆ [1, 120]

Loc×�Var→ I

�

Méthode de calcul : comme pour la sémantique collectrice, mais sur des états abstraits.

45

r := ⊥i := ⊥n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

Sémantique abstraite.• On regroupe dans un même objet mathématique un ensemble d’environnements

• Par exemple, (domaine des intervalles).

• On travaille donc maintenant avec des états abstraits :

P ∈ P�Var→ Z

�

{1, 2, 6, 24, 120} ⊆ [1, 120]

Loc×�Var→ I

�

Méthode de calcul : comme pour la sémantique collectrice, mais sur des états abstraits.

45

r := ⊥i := ⊥n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

r := [1, 1]i := [1, 2]n := [1, 3]

r := [1, 1]i := [1, 2]n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

Sémantique abstraite.• On regroupe dans un même objet mathématique un ensemble d’environnements

• Par exemple, (domaine des intervalles).

• On travaille donc maintenant avec des états abstraits :

P ∈ P�Var→ Z

�

{1, 2, 6, 24, 120} ⊆ [1, 120]

Loc×�Var→ I

�

Méthode de calcul : comme pour la sémantique collectrice, mais sur des états abstraits.

45

r := ⊥i := ⊥n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

r := [1, 1]i := [1, 2]n := [1, 3]

r := [1, 1]i := [1, 2]n := [1, 3]

r := [1, 2]i := [1, 2]n := [1, 3]

r := [1, 2]i := [1, 2]n := [1, 3]

r := [1, 1]i := [1, 2]n := [1, 3]

r := [1, 1]i := [1, 2]n := [1, 3]

Sémantique abstraite.• On regroupe dans un même objet mathématique un ensemble d’environnements

• Par exemple, (domaine des intervalles).

• On travaille donc maintenant avec des états abstraits :

P ∈ P�Var→ Z

�

{1, 2, 6, 24, 120} ⊆ [1, 120]

Loc×�Var→ I

�

Méthode de calcul : comme pour la sémantique collectrice, mais sur des états abstraits.

45

r := ⊥i := ⊥n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

r := [1, 2]i := [1, 3]n := [1, 3]

r := [1, 2]i := [1, 3]n := [1, 3]

r := [1, 2]i := [1, 2]n := [1, 3]

r := [1, 2]i := [1, 2]n := [1, 3]

r := [1, 1]i := [1, 2]n := [1, 3]

r := [1, 1]i := [1, 2]n := [1, 3]

Sémantique abstraite.• On regroupe dans un même objet mathématique un ensemble d’environnements

• Par exemple, (domaine des intervalles).

• On travaille donc maintenant avec des états abstraits :

P ∈ P�Var→ Z

�

{1, 2, 6, 24, 120} ⊆ [1, 120]

Loc×�Var→ I

�

Méthode de calcul : comme pour la sémantique collectrice, mais sur des états abstraits.

45

r := ⊥i := ⊥n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

r := [1, 2]i := [1, 3]n := [1, 3]

r := [1, 2]i := [1, 3]n := [1, 3]

r := [1, 6]i := [1, 3]n := [1, 3]

r := [1, 6]i := [1, 3]n := [1, 3]

r := [1, 2]i := [1, 3]n := [1, 3]

r := [1, 2]i := [1, 3]n := [1, 3]

Sémantique abstraite.• On regroupe dans un même objet mathématique un ensemble d’environnements

• Par exemple, (domaine des intervalles).

• On travaille donc maintenant avec des états abstraits :

P ∈ P�Var→ Z

�

{1, 2, 6, 24, 120} ⊆ [1, 120]

Loc×�Var→ I

�

Méthode de calcul : comme pour la sémantique collectrice, mais sur des états abstraits.

45

r := ⊥i := ⊥n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

r := [1, 6]i := [1, 4]n := [1, 3]

r := [1, 6]i := [1, 4]n := [1, 3]

r := [1, 6]i := [1, 3]n := [1, 3]

r := [1, 6]i := [1, 3]n := [1, 3]

r := [1, 2]i := [1, 3]n := [1, 3]

r := [1, 2]i := [1, 3]n := [1, 3]

Sémantique abstraite.• On regroupe dans un même objet mathématique un ensemble d’environnements

• Par exemple, (domaine des intervalles).

• On travaille donc maintenant avec des états abstraits :

P ∈ P�Var→ Z

�

{1, 2, 6, 24, 120} ⊆ [1, 120]

Loc×�Var→ I

�

Méthode de calcul : comme pour la sémantique collectrice, mais sur des états abstraits.

45

r := ⊥i := ⊥n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

r := [1, 6]i := [1, 4]n := [1, 3]

r := [1, 6]i := [1, 4]n := [1, 3]

r := [1, 6]i := [1, 3]n := [1, 3]

r := [1, 6]i := [1, 3]n := [1, 3]

r := [1, 6]i := [1, 4]n := [1, 3]

r := [1, 6]i := [1, 4]n := [1, 3]

Sémantique abstraite.• On regroupe dans un même objet mathématique un ensemble d’environnements

• Par exemple, (domaine des intervalles).

• On travaille donc maintenant avec des états abstraits :

P ∈ P�Var→ Z

�

{1, 2, 6, 24, 120} ⊆ [1, 120]

Loc×�Var→ I

�

Méthode de calcul : comme pour la sémantique collectrice, mais sur des états abstraits.

Remarque : on obtient des traces qui n’étaient pas présentes dans la sémantique collectrice.

45

r := ⊥i := ⊥n := [1, 3]

r := [1, 1]i := [1, 1]n := [1, 3]

r := [1, 6]i := [1, 4]n := [1, 3]

r := [1, 6]i := [1, 4]n := [1, 3]

r := [1, 6]i := [1, 3]n := [1, 3]

r := [1, 6]i := [1, 3]n := [1, 3]

r := [1, 6]i := [1, 4]n := [1, 3]

r := [1, 6]i := [1, 4]n := [1, 3]

• Pour prouver une propriété sur un programme, on suit souvent (toujours?) le raisonnement suivant :

1. définition d’une sémantique concrète permettant de prouver la propriété sur une exécution.

2. définition d’une sémantique collectrice permettant de regrouper l’ensemble des exécutions.

3. définition d’une sémantique abstraite calculable qui sur-approxime la sémantique collectrice.

Pour résumer.

Sémantique concrète. Sémantique collectrice. Sémantique abstraite.

Une exécution Au moins toutes les exécutions.

Au moins toutes les exécutions.

NON CALCULABLE CALCULABLE

⊆ ⊆

46