Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
Methodes Formelles etDeveloppement de logiciels Surs
Cours 1 : introduction a la verification deductive
Sandrine [email protected]
M1 informatique,parcours genie logiciel et IR
9 janvier 2014
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 1 / 29
Informations pratiques
Equipe pedagogique
Sandrine Blazy
Alan Schmitt
Vincent Picard
Calendrier
Debut des TD et TP : la semaine prochaine
Au total : 7C, 6 TD et 8 TP
http://etudiant.istic.univ-rennes1/current/m1info/MFDS
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 2 / 29
L’U.E. MFDS
Objectif commun au cours d’ACF : initiation aux methodes formelles
Savoir ecrire des specifications a l’aide de formules logiques
Savoir utiliser des outils automatiques demontrant des proprietesrelatives a des programmes
Complementarite / ACF
Langage de programmation imperatif
Les proprietes a prouver sont plus fortes que celles vues en ACF
Verification deductive avec l’outil Why3
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 3 / 29
Omnipresence du logiciel ... et de ses defauts
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 4 / 29
Qualite du logiciel
La qualite des specifications est de plus en plus reglementaire.
Exemples :
Signature electronique
Criteres communsI EAL1 / EAL2 : teste fonctionnellement / structurellementI . . .I EAL7 : conception verifiee de facon formelle et systeme teste
DO-178C (2012)
ISO-26262 (2011)
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 5 / 29
Comment concevoir des systemes fiables en ingenierie ?(d’apres le cours de W.Ahrendt, ainsi que la suite)
Quelques strategies bien connues en genie civil :
Calculs precis/estimations des forces, stress, etc.
Redondance materielle (� construire un peu plus solide �)
Conception robuste (une erreur isolee n’est pas catastrophique)
Separation claire entre les sous-systemesN’importe quel avion vole avec des dizaines de defauts mineursconnus.
La conception suit des pratiques ayant fait leurs preuves.
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 6 / 29
Cette demarche ne s’applique pas au logiciel
Un logiciel calcule des fonctions non continues.Modifier un seul bit peut changer completement le comportement dusysteme.
La redondance ne permet pas d’eviter les bugs.Le developpement redondant de logiciels n’est utilisable que dans descas extremes.
Pas de separation clairement identifiee des sous-systemesUne erreur locale peut avoir un impact sur le systeme entier.
Complexite de la conception d’un logiciel
Manque de sensibilisation des developpeurs a la correction du logiciel
Rendement vs. fiabilite
Les pratiques de conception de logiciels surs sont encore immaturespour des logiciels complexes, en particulier les systemes distribues.
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 7 / 29
Methodes formelles : un scenario
methodes rigoureuses utilisees pour concevoir et developper dessystemes
logique mathematique et symbolique ⇒ formelRemarque : formel 6= theorique
augmentent la confiance en un systeme
deux aspects :I implementation d’un systemeI specification d’un systeme
modele formel des deux ⇒ utilisation d’outils pour demontrer surmachine que le modele formel d’execution satisfait les specificationsformelles
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 8 / 29
Methodes formelles : une vision
Les methodes formelles
sont complementaires par rapport aux methodes d’analyse et deconception,
sont adaptees pour decouvrir des bugs(dans le code et dans les specifications),
reduisent le temps de developpement (tests compris),
permettent d’assurer certaines proprietes du modele du systeme,
devraient dans l’ideal etre le plus automatisees possible.
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 9 / 29
Specification — Que devrait faire un systeme ?
Proprietes elementaires deI surete
Rien de mauvais n’arrivera jamais (ex., exclusion mutuelle).I vivacite
Quelque chose de bien devrait finir par arriver.
Proprietes generales de systemes distribues/concurrents
I absence d’interblocage, absence de famine, equite
Proprietes non fonctionnelles
I execution, occupation memoire, utilisabilite, . . .
Specification complete du comportementI Le code satisfait un contrat qui decrit ses fonctionnalites.I coherence des donnees, invariants du systeme
(en particulier representations des donnees efficaces)I modularite, encapsulationI equivalence entre programmesI relation de raffinement
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 10 / 29
Les methodes formelles n’ont pas pour objectif
de montrer la � correction � d’un systeme entier
de remplacer completement le test
I Les methodes formelles operent sur des modeles, du code source ou dubytecode.
I De nombreuses proprietes ne sont pas formalisables.
de remplacer les bonnes pratiques de conception
Remarques
Il n’existe pas de systeme correct qui soit mal specifie et mal concu.
Verifier formellement un code spaghetti mal specifie n’a pas de sens.
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 11 / 29
Mais . . .
Une preuve formelle peut remplacer de nombreux cas de tests (uneinfinite).
Les methodes formelles ameliorent la qualite des specifications(meme sans verification formelle).
Les methodes formelles garantissent des proprietes specifiques dusysteme modelise.
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 12 / 29
Et si la preuve echoue ?
Raisons possibles :
La strategie de l’outil de preuve automatique peut etre trop faible.
Lors d’une preuve manuelle, des formules n’ont pas eteconvenablement instanciees.
La formule a prouver n’est pas valide !
Ne pas hesiter a apprendre de ses erreurs !
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 13 / 29
Un exemple : programme de tri
public static Integer[] sort(Integer [] a){ ... }
Test
sort({3,2,5})= {2,3,5}sort({ })= { }sort({17})= {17}
Specification
Pre a est un tableauPost trie le tableau a
Est-ce une bonne specification ?
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 14 / 29
Un exemple de specification : programme de tri
public static Integer[] sort(Integer [] a){ ... }
Specification
Pre a est un tableau non nul d’entiersPost calcule la reference non modifiee a contenant une permutation trieede l’ancien contenu de a
sort({ 2,1,2}) == {1,2,2,17}sort({ 2,1,2}) == {1,1,2}sort(null) declenche NullPointerException
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 15 / 29
Specifications
Metaphore du contrat entre un client et un fournisseur
Fournisseur (implementeur) : une fonction
Client : une fonction appelante
Contrat : des paires de proprietes pre/post definissant les obligationsmutuelles entre le fournisseur et le client
Signification d’un contrat
Specification d’une fonction f : precondition + postcondition
Si un appelant de f satisfait la precondition, alors il est garanti que lapostcondition est satisfaite lorsque f a ete executee.
Mauvaises interpretations
Tout appelant de f doit satisfaire la precondition.
Lorsque la precondition est satisfaite, alors f est executee.
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 16 / 29
Outillage (essentiel !)
Pourquoi utiliser un outil ?
Automatiser les taches repetitives
Eviter les erreurs mineures, etc.
Traiter des programmes de grande taille/complexite
Rendre la verification certifiable
Outil utilise dans ce cours : Why3 (http://why3.lri.fr)
utilise pour la verification deductive de programmes C et Java
developpe depuis une dizaine d’annees (equipe TOCCATA, LRI -INRIA)
utilise par Frama-C (http://frama-c.com),un outil industriel open source
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 17 / 29
Remerciements
Les planches suivantes sont celles du cours de Jean-Christophe Filliatre.
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 18 / 29
Verification deductive
programme+ preuve
specifications
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 19 / 29
Rappel historique
A.M. Turing. Checking a large routine. 1949.
Demo : checking a large routine.why
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 20 / 29
Rappel historique
Tony Hoare. Proof a program : FIND. Comm. of theACM, 1971.
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 21 / 29
Quels programmes ? Quelles specifications ?
Programmes
pseudo-code, langage realiste, DSL
petit, vaste
Specifications
Surete : le programme ne plante pas
Absence de debordement arithmetique
Propriete fonctionnelle complexe (ex. � trie un tableau �)
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 22 / 29
Quelle logique ?
Une logique trop riche ne permet pas d’automatiser les preuves.
Une logique trop pauvre ne permet ni de modeliser l’execution deprogrammes realistes, ni de specifier des programmes quelconques.
Un exemple de compromis
logique du premier ordre + egalite + arithmetique
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 23 / 29
Quelle preuves ?
Une aubaine : les demonstrateurs de theoremes
Assistants de preuve : Coq, PVS, Isabelle, etc.
Prouveurs TPTP : Vampire, Eprover, SPASS, etc.
Solveurs SMT : CVC3, Z3, Yices, Alt-Ergo, etc.
Prouveurs dedies : Gappa, etc.
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 24 / 29
Extraction de conditions de verification
Une technique bien connue : plus faible preconditions (vue en L3 !) -Dijkstra 1971, Barnett/Leino 2005
L’implementer pour un langage realiste demande beaucoup de travail.
Une autre approche : concevoir un langage plus simple a partir duquel sontextraites les conditions de verifications.
Deux exemples
Boogie (Microsoft Research)
Why3
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 25 / 29
Why3
Un langage de programmation, WhyML
polymorphisme
filtrage
exceptions
structures de donnees mutables
Une logique polymorphe du premier ordre
types de donnees algebriques
definitions recursives
predicats inductifs et coinductifs
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 26 / 29
Architecture
file.why
file.mlw
WhyML
VCgen
Why
transform/translate
print/run
Coq Alt-Ergo Gappa Z3 etc.
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 27 / 29
Applications
Trois utilisations possibles de Why3
Langage logiqueFront-end a de nombreux demonstrateurs de theoremes
Langage de programmation permettant de prouver des algorithmes
Langage intermediairepour verifier des programmes ecrits en C, Java, Ada, etc.
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 28 / 29
Quelques systemes utilisant Why3
S. Blazy (ISTIC-IRISA) M1 - MFDS 9 janvier 2014 29 / 29