Le chameau et le serpent rentrent dans un bar : vérification quasi-automatique de code OCaml en logique de séparation

Charlène Gros, Mário Pereira · 2024

Read Le chameau et le serpent rentrent dans un bar : vérification quasi-automatique de code OCaml en logique de séparation by Charlène Gros, Mário Pereira (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-14894.txt.

Introduction

Charlène Gros and Mário Pereira present a bridge between two program-checking tools in a 2024 paper, written in French with an English summary. OCaml programs can carry notes that state what the code should do. Their bridge turns those noted programs into a second language built for checking memory-safe code. The goal is to widen an existing checker with a new back end. Heap-dependent programs, which reshape shared memory, are the target class. The paper also extends the note language to cover separation logic features.

Catalog record

CREATORCharlène Gros, Mário Pereira
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-14894

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Le chameau et le serpent rentrent dans un bar : vérification quasi-automatique de code OCaml en logique de séparation Charlène Gros, Mário Pereira Abstract Cet article présente une traduction de programmes OCaml spécifiés en Gospel vers Viper, un langage intermédiaire de preuves formelles supportant la logique de séparation. L’objectif pratique est d’ajouter à Cameleer un nouveau backend pour prouver des programmes OCaml manipulant le tas. La spécification logique de tels programmes OCaml est décrite dans le langage Gospel et nous détaillons ici les extensions apportées pour le support de la logique de séparation en Viper. 1 Introduction Gospel (Generic OCaml Specification Language) [ CFLP19 ] est un langage de spécification conçu pour OCaml permettant l’annotation de programmes avec des contrats formels. Celles-ci spécifient les invariants des types, les pré-conditions et post-conditions des fonctions, les effets, ainsi que les exceptions levées par une fonction. La syntaxe non intrusive de Gospel facilite la génération de documentation détaillée, permet la génération de tests à l’aide de l’outil Ortac [ FP21 ] et intègre un support de preuve formelle via Cameleer [ PR21 ] pour les programmes OCaml. Les annotations Gospel offrent un moyen fiable de formaliser les comportements attendus d’un programme OCaml. Elles sont intégrées dans le code source, ce qui fournit une description claire et non ambiguë du comportement des modules et des fonctions, garantissant ainsi que la documentation reste en phase avec l’implémentation. Cela facilite la compréhension et la maintenance du code en offrant une référence formelle aux développeurs. Pour la vérification formelle des programmes OCaml, l’outil Cameleer s’appuie sur Gospel pour annoter le code OCaml et le traduit ensuite dans le langage WhyML, utilisé par la plateforme de vérification déductive Why3 [ FP13 ] . Cette dernière s’appuie sur le calcul des plus faibles pré-conditions, une méthode de vérification déductive qui génère des conjectures logiques pour chaque programme et qui, une fois vérifiées, garantissent qu’un programme est conforme à sa spécification. Cette méthode permet de démontrer des propriétés comme les invariants et les conditions de validité d’un programme, en produisant des obligations de preuve transmises à des solveurs automatiques tels qu’Alt-Ergo, Z3, CVC5 et bien d’autres. Toutefois, bien que Why3 gère une forme de mutabilité, elle est limitée lorsqu’il s’agit de traiter des structures mutables récursives. En effet, le calcul des plus faibles pré-conditions et le système de types et d’effets de Why3 [ FGP16 ] imposent la gestion statique de l’ aliasing , ce qui empêche notamment l’utilisation de champs à la fois récursifs et mutables au sein de types ou de structures de données. L’exemple présenté ci-dessous illustre la définition d’une liste chaînée en WhyML. ⬇ type t = Nil | Cons cell with cell = { mutable content : int ; mutable next : cell } ⬇ Error: Recursive types cannot have mutable fields Le type cell est rejeté par Why3, qui interdit un type récursif à contenir un champ mutable pointant vers lui-même. Les outils basés sur la logique de séparation [ Rey02 ] permettent de résoudre une grande partie de ces problèmes. Le principe fondamental est de raisonner sur des portions disjointes de mémoire à l’aide de l’opérateur de conjonction séparante. Bien que Why3 impose des restrictions via un suivi statique des alias, ce qui permet de déterminer précisément quelles modifications affectent une valeur mutable, il ne peut pas exprimer explicitement la séparation ou la propriété ( ownership ) de ces portions de mémoire. En revanche, la logique de séparation garantit grâce à la distinction des portions de mémoire et la fameuse frame rule , qu’aucune modification externe n’a eu lieu. L’intégration de cette logique comme nouveau backend dans Cameleer permet d’élargir la vérification à un éventail plus vaste de programmes OCaml annotés avec Gospel. Un mécanisme de traduction de code OCaml annoté avec Gospel vers la logique de séparation est déjà en cours de développement 1 1 1 voir https://github.com/ocaml-gospel/gospel2cfml . Celui-ci traduit le programme OCaml annoté en CFML [ Cha11 ] , une extension de Rocq (anciennement Coq) dédiée à la logique de séparation. Cependant, faire une preuve avec CFML demande toujours une connaissance de l’assistant de preuve Rocq et cette traduction est limitée aux interfaces OCaml. L’extension proposée ici est une traduction vers le langage intermédiaire Viper, qui nous permet de conduire une preuve quasi-automatique de la correction d’un programme. Viper (Verification Infrastructure for Permission-based Reasoning) [ MSS16 ] est un outil basé sur la logique de séparation et une de ses variantes : les Implicit Dynamic Frames [ SJP09 , PS12 ] . Il propose un langage intermédiaire ainsi que deux backends de vérification : l’un basé sur l’exécution symbolique et l’autre sur la génération de conditions de vérification. Ces deux approches s’appuient sur le solveur SMT “Z3” pour résoudre les obligations de preuve. Le langage intermédiaire Viper est un langage impératif et séquentiel, offrant des fonctionnalités de haut niveau pour formuler des problèmes de vérification, tout en étant suffisamment flexible pour automatiser la vérification dans divers langages de programmation. Il est notamment utilisé pour Rust, Python et Go à travers les frontends respectifs Prusti [ AMPS19 ] , Nagini [ EM18 ] , et Gobra [ WAC+21 ] . Le développement présenté dans cet article est une extension de l’outil Cameleer pour traduire les programmes OCaml annotés vers Viper. Dans la suite nous nous référerons à cette extension sous le nom de gospel2viper . Remarque préliminaire. L’extension présentée ici est un travail toujours en cours de développement. Nous ne traitons qu’un sous-ensemble réduit d’OCaml, qu’on pourrait dire proche d’ ocaml-light : en particulier, définitions et appels de fonctions, variables locales, type algébriques (mais avec des records en argument), structure conditionnelle, filtrage, affectation de champs mutables. Par conséquent, nous ne supportons ni les boucles ni les tableaux. En ce qui concerne les définitions de types, nous ne traitons pas les types polymorphiques. Nous n’autorisons, pour l’instant, que des entiers comme type des éléments d’une structure de données. Enfin, côté spécification, nous n’utilisons que des séquences mathématiques comme modèle logique. 2 Présentation de gospel2viper Actuellement, Cameleer prend en charge la traduction vers WhyML, utilisé par Why3. L’extension gospel2viper vise à résoudre certaines limitations imposées par l’utilisation de Why3. Il est toutefois nécessaire d’étendre aussi le langage Gospel avec des constructions classiques de logique séparation, e.g. , la notion de possession des champs d’un record . Dans cette section nous introduisons au fur et à mesure les concepts les plus importants de Gospel et Viper utilisés dans notre traduction. L’explication est complétée dans la Section 3 , lorsque ces mêmes concepts sont utilisés dans une étude de cas. En Viper, les données mutables sont des références déclarées en tant que champs par le mot-clé field , et les structures de données sont décrites par des assertions dans des prédicats de représentation via le mot-clé predicate . C’est dans ce prédicat qu’est notamment décrit le footprint de mémoire d’une structure, ainsi que sa relation avec un modèle logique. L’opérateur && agit comme la conjonction séparante de la logique de séparation. En tant qu’abstraction de son contenu, Viper impose l’ouverture explicite d’un prédicat de représentation par l’opération de dépliage ( unfold ), afin de révéler son contenu et accéder aux permissions en mémoire. La fonction

Read the complete text