Search

International audience; In multiple domains, large amounts of data are daily generated and combined to be analyzed. The interpretation of these analyses requires to track back the provenance of combined data with respect to initial, raw data. The correctness of the provenance is crucial in many critical domains, such as medicine to prescribe treatments. In this article, we propose the first provenance-aware extended relational algebra formalized in a proof assistant (Coq), for a non trivial subset of database queries: queries containing aggregates, null values, and correlated sub-queries. The formalization is validated by an adequacy proof with respect to standard evaluation of queries. This development is a first step towards a posteriori certification of provenance for data manipulation, with strong guaranties.

National audience; ProbZelus est un langage synchrone probabiliste qui permet de décrire des modèles probabilistes réactifs en interaction avec un environnement observable. Des méthodes d'inférences réactives permettent d'apprendre en ligne les distributions associées aux paramètres non-observés du modèle à partir d'observations statistiques. Ce problème n'a, en général, pas de solution analytique simple. Pour obtenir des estimations précises, une méthode classique consiste à analyser les résultats obtenus par de nombreuses exécutions indépendantes du modèle. Ces méthodes sont coûteuses, mais ont l'avantage de pouvoir être massivement parallélisées. Nous proposons d'utiliser JAX pour paralléliser les méthodes d'inférence réactive de ProbZelus. JAX est une bibliothèque récente qui permet de paralléliser automatiquement du code Python qui peut ensuite être exécuté de manière efficace et transparente sur CPU, GPU, ou TPU. Dans cet article, nous décrivons un nouveau moteur d'inférence réactive parallèle implémenté en JAX et le nouveau backend JAX associé pour ProbZelus. Nous montrons sur des exemples existants que notre nouvelle implémentation surpasse l'implémentation séquentielle originale pour un nombre de particules élevé.

National audience; Software Heritage est un projet initié par Inria ayant pour but d'archiver l'ensemble des logiciels libres disponibles sur internet. Dans cet article nous présentons Software Heritage et décrivons nos travaux en lien avec l'écosystème OCaml, opam et Software Heritage. Ces travaux comprennent notamment l'ajout à Software Heritage de modules permettant l'archivage des paquets présents sur opam, le développement d'une bibliothèque OCaml permettent de travailler avec les identifiants Software Heritage, l'ajout à opam de la possibilité de récupérer sur Software Heritage des paquets qui ne sont plus disponibles et enfin la correction du dépôt opam officiel afin de retrouver les paquets déjà manquants. Aujourd'hui, 3516 paquets opam sont déjà archivés sur Software Heritage.

National audience; Futures and promises are respectively a read-only and a write-once pointer to a placeholder in memory. They are used to transfer information between threads in the context of asynchronous concurrent programming. Futures and promises simplify the implementation of synchronisation mechanisms between threads. Nonetheless they can be error prone as data races may arise when references are shared and transferred. We aim at providing a formal tool to detect those errors. Hence, in this paper we propose a proof of concept by implementing the future/promise mechanism in Viper: a verification infrastructure, that provides a way to reason about resource ownership in programs.

National audience; Steel est un framework pour développer et prouver des programmes concurrents écrits en F , un langage de programmation avec types dépendants ainsi qu'un assistant de preuve. Inspiré par Iris, Steel repose sur une logique de séparation concurrente imprédicative qui inclut un modèle mémoire fondé sur des monoïdes commutatifs partiels et permet l'utilisation d'invariants alloués dynamiquement pour raisonner sur des interactions concurrentes sans recourir à des verrous ("locks"). Afin d'offrir une vérification semi-automatique, Steel sépare les obligations de preuves générées en deux parties : une procédure de décision partielle, implémentée à l'aide du moteur de tactiques de F , raisonne sur la logique de séparation tandis qu'un solveur SMT permet de décharger automatiquement des obligations de preuves exprimées en logique du premier ordre, par exemple liées à de l'arithmétique. Dans cette démonstration, nous présentons plusieurs bibliothèques vérifiées qui illustrent l'expressivité et la programmabilité de Steel.

National audience; Cet article présente Mitten, un outil pour décrire finement et jouer des scénarios sur une implémentation de Tenderbake-le prochain protocole de consensus à la pBFT de la blockchain Tezos. Mitten est paramétrable pour filtrer et examiner les messages selon des scénarios particuliers écrits dans un DSL construit sur OCaml. Grâce à Mitten, nous avons pu écrire et simuler des scénarios subtils pour reproduire des comportements difficilement atteignables en temps normal. Nous avons également pu simuler des situations permettant d'exhiber des bugs dans l'implémentation en cours et de tester des correctifs proposés.

National audience; Le droit codifie et régit de nombreux aspects de la vie quotidienne. Si la plupart du temps les lois sont sujettes à interprétation, dans certains domaines la loi ne permet pas d'interprétation et vise essentiellement à décrire rigoureusement un calcul ou une procédure de décision, c'est-à-dire un algorithme. Catala est un nouveau langage conçu en collaboration avec des juristes qui permet une compilation depuis une spécification proche de la loi vers un code exécutable. Contrairement aux langages traditionnels, Catala est adapté aux raisonnements cas de base/exceptions présents dans la loi ; il intègre de la programmation littéraire du droit qui facilite les mises à jour du programme. Finalement, Catala compile vers une variété de langages cibles dont OCaml. Dans cette démonstration de prototype, nous montrerons comment exprimer une partie du calcul des allocations familiales dans Catala.

International audience; La vérification d’assertions à l’exécution est une technique consistant à vérifier la validité d’annotations formelles pendant l’exécution d’un programme. Bien qu’ancienne, cette technique reste encore peu étudiée d’un point de vue théorique. Cet article contribue à pallier ce manque en formalisant un vérificateur d’assertions à l’exécution pour des propriétés arithmétiques entières. La principale difficulté réside dans la modélisation d’un générateur de code pour les propriétés visées qui génère du code à la fois correct et efficace. Ainsi, le code généré repose sur des entiers machines lorsque le générateur peut prouver qu’il est correct de le faire et sur une bibliothèque spécialisée dans l’arithmétique exacte, correcte mais moins efficace, dans les autres cas. Il utilise pour cela un système de types dédié. En outre, la logique considérée pour les propriétés inclue des constructions d’ordre supérieur. L’article présente également une implémentation de ce générateur de code au sein d’EACSL, le greffon de Frama-C dédié à la vérification d’assertions à l’exécution, ainsi qu’une première évaluation expérimentale démontrant empiriquement l’efficacité du code généré.

National audience

National audience; L'arithmétique flottante est connue pour être un sujet difficile. Ses propriétés contreintuitives rendent l'écriture d'algorithmes manipulant les nombres flottants propice à de nombreuses erreurs. Des outils automatiques pour la vérification de programmes flottants existent mais ces outils faisant eux-mêmes usage de calculs en arithmétique flottante, on peut se poser la question de leur propre fiabilité. Dans cet article, nous proposons de vérifier formellement l'implémentation de raisonnements sur les nombres flottants dans le solveur de contraintes Colibri2. En particulier, nous présentons une méthodologie pour mener la preuve de correction de propagateurs de contraintes en utilisant l'assistant de preuve Coq. Nous discutons également de l'intégration des raisonnements prouvés à un développement logiciel complet en OCaml.

National audience; Dans un assistant de preuve comme Coq, un même objet mathématique peut souvent être formalisé par différentes structures de données. Par exemple, le type Z des entiers binaires, dans la bibliothèque standard de Coq, représente les entiers relatifs tout comme le type ssrint, des entiers unaires, fourni par la bibliothèque MathComp. En pratique, cette situation familière en programmation est un frein à la preuve formelle automatique. Dans cet article, nous présentons trakt, un outil dont l'objectif est de faciliter l'accès des utilisateurs de Coq aux tactiques d'automatisation, pour la représentation des théories décidables de leur choix. Cet outil construit une formule auxiliaire à partir d'un but utilisateur, et une preuve que cette dernière implique ce but initial. La formule auxiliaire est conçue pour être adaptée aux outils de preuve automatique (lia, SMTCoq, etc). Cet outil est extensible, grâce à une API permettant à l'utilisateur de définir plusieurs natures de plongements dans un jeu de structures de données de référence. Le méta-langage Coq-Elpi, utilisé pour l'implémentation, fournit des facilités bienvenues pour la gestion des lieurs et la mise en oeuvre des parcours de termes en jeu dans ces tactiques.

National audience; Cet article présente un système de vérification et d'inférence statique des tailles de tableaux dans un langage fonctionnel strict statiquement typé. Plutôt que de s'en remettre à des types dépendants, nous proposons un système de types proche de celui de ML. Le polymorphisme sert à définir des fonctions génériques en type et en taille. L'inférence permet une écriture plus légère des opérations classiques de traitement du signal-application point-à-point, accumulation, projection, transposée, convolution-et de leur composition ; c'est un atout clef de la solution proposée. Pour obtenir un bon compromis entre expressivité du langage des tailles et décidabilité de la vérification et de l'inférence, notre solution repose sur deux éléments : (i) un langage de types où les tailles sont des polynômes multi-variés et (ii) l'insertion de points de coercition explicites entre tailles dans le programme source. Lorsque le programme est bien typé, il s'exécute sans erreur de taille en dehors de ces points de coercition. Deux usages de la proposition faite ici peuvent être envisagés : (i) la génération de code défensif aux points de coercition ou, (ii) pour les applications critiques ou intensives, la vérification statique des coercitions en les limitant à des expressions évaluables à la compilation ou par d'autres moyens de vérification formelle. L'article définit le langage d'entrée, sa sémantique dynamique, son système de types et montre sa correction. Il est accompagné d'une implémentation en OCaml, dont le code source est accessible publiquement.