Méthodes Formelles et Développement de logiciels Sûrs

Methodes Formelles etDeveloppement de logiciels Surs

Cours 1 : introduction a la verification deductive

Sandrine BlazySandrine.Blazy@univ-rennes1.fr

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