Vers un outil de vérification formelle légere pour OCaml

Résumé : Si l'on décrit , par une grammaire, l'ensemble des entrées possibles d'un programme fonc-tionnel, peut-on connaˆtre la grammaire des sorties de celui-ci ? Il existe des outils en réécriturè a même de répondrè a cette question, pour certaines fonctions. On peut utiliser ce genre de cal-cul pour détecter des bugs ou, ` a l'inverse, pour prouver des propriétés sur ces fonctions. Dans cet article, nous présentons un travail en cours visant a concevoir un outil de vérification for-melle lég ere pour OCaml. Si l'essentiel des résultats théoriques et outils de réécriture existent déj a, leur application a la vérification de programmes OCaml réalistes nécessite de résoudre un certains nombre deprobì emes. Nous donnerons l'architecture d'un interpr ete abstrait pour OCaml, basés sur ces principes et outils, et nous verrons quelles sont les briques manquantes pour finaliser son développement. 1 Une vérification aussi automatique que l' inférence de type Certains langages de programmation fortement typés (comme Haskell, OCaml, Scala et F#) disposent d'un mécanisme d' inférence de type. Ce mécanisme permet, entre autres, de détecter automatiquement certains types d'erreurs dans les programmes. Pour vérifier plus que le bon typage d'un programme, il est possible de définir des propriétés et, ensuite, de les prouver a l'aide d'un assistant de preuve ou d'un prouveur automatique. Cependant, la formulation de ces propriétés en logique et la construction de la preuverequì erent généralement une certaine expertise. On s' intéresse icì a une famille restreinte de propriétés : des propriétés "régulì eres " portant sur les structures manipulées par ces programmes. On décrit , par une grammaire (d'arbres,régulì ere), l'ensemble de structures données en entréè a une fonction et on cherchè a construire la grammaire des structures pouvant etre obtenues en sortie (ou une approximation). La grammaire de sortie pourra révéler un bug potentiel dans le programme ou, ` a l'inverse, montrer que celui-ci vérifie une propriétérégulì ere. La famille de propriétés démontrables de cette façon est restreinte, même si elle dépasse ce que l'on peut exprimer par typage simple. On peut par exemple distinguer la liste vide de la liste non vide. Une telle distinction est egalement faisable avec des GADTs (Generalized Algebraic DataTypes) mais, ` a notre connaissance, pas le type de raisonnement sur des structures récursives que l'on propose ici. Il existe d'autres approches o` u le syst eme de type est enrichi par des formules logiques et de l' arithmétique [17, 3]. Cependant ces techniques nécessitent généralement d'annoter le programme pour que la vérification de type réussisse. Les propriétés que nous considérons ici sont volontairement plus simples pour eviter au maximum le travail d'annotation. Pour ces propriétés , l'objectif est de proposer une forme de vérification formelle " lég ere ". La vérification est formelle car elle démontre que les résultats d'une fonction ont une certaine forme. La vérification est lég ere car, d'une part, la preuve est automatique, et d'autre part, il n'est pas nécessaire de définir la propriété attendue par une formule logique mais simplement d'observer le résultat d'un calcul abstrait.
Type de document :
Communication dans un congrès
AFADL, 2015, Bordeaux, France. pp.6
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01194538
Contributeur : Thomas Genet <>
Soumis le : lundi 7 septembre 2015 - 11:05:36
Dernière modification le : mercredi 16 mai 2018 - 11:23:28
Document(s) archivé(s) le : mardi 8 décembre 2015 - 11:44:40

Fichier

GenetKordyVansyngel-AFADL15.pd...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01194538, version 1

Citation

Thomas Genet, Barbara Kordy, Amaury Vansyngel. Vers un outil de vérification formelle légere pour OCaml. AFADL, 2015, Bordeaux, France. pp.6. 〈hal-01194538〉

Partager

Métriques

Consultations de la notice

706

Téléchargements de fichiers

90