AGArmaël Guéneau

Armaël Guéneau

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Armaël Guéneau has a total of 22 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Mechanized verification of the correctness and asymptotic complexity of programs : the right answer at the right time

    by Armaël Gueneau

    Vérification mécanisée de la correction et complexité asymptotique de programmes: Cette thèse s’intéresse à la question de démontrer rigoureusement que l’implantation d’un algorithme donné est non seulement correcte (elle renvoie bien le bon résultat dans tous les cas possibles), mais aussi possède la bonne complexité asymptotique (elle calcule toujours ce résultat en le temps attendu).Pour les chercheurs en algorithmique, caractériser la performance d’un algorithme se fait généralement en indiquant sa complexité asymptotique, notamment à l’aide de la notation “grand O” due à Landau. Nous détaillons, tout d’abord informellement, pourquoi de telles bornes de complexité asymptotiques sont également utiles en tant que spécifications formelles. La raison est que celles-ci permettent de raisonner de façon modulaire à propos du coût d’un programme : une borne en O s’abstrait de l’expression exacte du coût du programme, et par là des divers détails d’implantation. Par ailleurs, nous illustrons, à l’aide d’exemples simples, un certain nombre de difficultés liées à l’utilisation rigoureuse de la notation O, et qu’il est facile de négliger lors d’un raisonnement informel.Ces considérations sont mises en pratique en formalisant d’une part la notation O dans l’assistant de preuve Coq, et d’autre part en étendant CFML, un outil existant dédié à la vérification de programmes, afin de permettre à l’utilisateur d’élaborer des démonstrations robustes et modulaires établissant des bornes de complexité asymptotiques. Nous étendons la logique de séparation avec crédits temps—qui permet de raisonner à la fois sur des propriétés de correction et de complexité en temps—avec la notion de crédits temps négatifs. Ces derniers augmentent l’expressivité de la logique, donnent accès à des principes de raisonnement commodes et permettent d’exprimer certaines spécifications de manière plus élégante. Au niveau des spécifications, nous montrons comment des bornes de complexité asymptotique avec O s’expriment en logique de séparation avec crédits temps. Afin d’être capable d’établir de telles spécifications, nous développons une méthodologie qui permet à l’utilisateur de développer des démonstrations qui soient à la fois robustes et menées à un niveau d’abstraction satisfaisant. Celle-ci s’appuie sur deux principes clefs : d’une part, un mécanisme permettant de collecter et remettre à plus tard certaines contraintes durant une démonstration interactive, et par ailleurs, un mécanisme permettant de synthétiser semi-automatiquement une expression de coût, et ce sans perte de généralité.Nous démontrons l’utilité et l’efficacité de notre approche en nous attaquant à un certain nombre d’études de cas. Celles-ci comprennent des algorithmes dont l’analyse de complexité est relativement simple (par exemple, une recherche dichotomique, déjà hors de portée de la plupart des approches automatisées) et des structures de données (comme les “binary random access lists” d’Okasaki). Dans notre étude de cas la plus significative, nous établissons la correction et la complexité asymptotique d’un algorithme incrémental de détection de cycles publié récemment. Nous démontrons ainsi que notre méthodologie passe à l’échelle, permet de traiter des algorithmes complexes, donc l’analyse de complexité s’appuie sur des invariants fonctionnels subtils, et peut vérifier du code qu’il est au final possible d’utiliser au sein de programmes réellement utiles et utilisés.

  • Open Access

    Using Ghost Ownership to Verify Union-Find and Persistent Arrays in Rust

    by Arnaud Golfouse, Armaël Guéneau, Jacques-Henri Jourdan


  • Open Access

    Cerise: Program Verification on a Capability Machine in the Presence of Untrusted Code

    by Aïna Linn Georges, Armaël Guéneau, Thomas Van Strydonck, Amin Timany, Alix Trieu, Dominique Devriese, Lars Birkedal

    A capability machine is a type of CPU allowing fine-grained privilege separation using capabilities , machine words that represent certain kinds of authority. We present a mathematical model and accompanying proof methods that can be used for formal verification of functional correctness of programs running on a capability machine, even when they invoke and are invoked by unknown (and possibly malicious) code. We use a program logic called Cerise for reasoning about known code, and an associated logical relation, for reasoning about unknown code. The logical relation formally captures the capability safety guarantees provided by the capability machine. The Cerise program logic, logical relation, and all the examples considered in the paper have been mechanized using the Iris program logic framework in the Coq proof assistant. The methodology we present underlies recent work of the authors on formal reasoning about capability machines [Georges et al. 2021 ; Skorstengaard et al. 2019a ; Van Strydonck et al. 2022 ], but was left somewhat implicit in those publications. In this paper we present a pedagogical introduction to the methodology, in a simpler setting (no exotic capabilities), and starting from minimal examples. We work our way up to new results about a heap-based calling convention and implementations of sophisticated object-capability patterns of the kind previously studied for high-level languages with object-capabilities, demonstrating that the methodology scales to such reasoning.


  • Top Cited Papers
    Open Access

    Thunks and Debits in Separation Logic with Time Credits

    by François Pottier, Armaël Guéneau, Jacques-Henri Jourdan, Glen Mével

    A thunk is a mutable data structure that offers a simple memoization service: it stores either a suspended computation or the result of this computation. Okasaki [1999] presents many data structures that exploit thunks to achieve good amortized time complexity. He analyzes their complexity by associating a debit with every thunk. A debit can be paid off in several increments; a thunk whose debit has been fully paid off can be forced. Quite strikingly, a debit is associated also with future thunks, which do not yet exist in memory. Some of the debit of a faraway future thunk can be transferred to a nearer future thunk. We present a complete machine-checked reconstruction of Okasaki’s reasoning rules in Iris $ , a rich separation logic with time credits. We demonstrate the applicability of the rules by verifying a few operations on streams as well as several of Okasaki’s data structures, namely the physicist’s queue, implicit queues, and the banker’s queue.


  • Open Access

    The Logical Essence of Well-Bracketed Control Flow

    by Amin Timany, Armaël Guéneau, Lars Birkedal

    A program is said to be well-bracketed if every called function must return before its caller can resume execution. This is often the case. Well-bracketedness has been captured semantically as a condition on strategies in fully abstract games models and multiple prior works have studied well-bracketedness by showing correctness/security properties of programs where such properties depend on the well-bracketed nature of control flow. The latter category of prior works have all used involved relational models with explicit state-transition systems capturing the relevant parts of the control flow of the program. In this paper we present the first Hoare-style program logic based on separation logic for reasoning about well-bracketedness and use it to show correctness of well-bracketed programs both directly and also through defining unary and binary logical relations models based on this program logic. All results presented in this paper are formalized on top of the Iris framework and mechanized in the Coq proof assistant.


  • Open Access

    Melocoton: A Program Logic for Verified Interoperability Between OCaml and C

    by Armaël Guéneau, Johannes Hostert, Simon Spies, Michael Sammler, Lars Birkedal, Derek Dreyer

    In recent years, there has been tremendous progress on developing program logics for verifying the correctness of programs in a rich and diverse array of languages. Thus far, however, such logics have assumed that programs are written entirely in a single programming language. In practice, this assumption rarely holds since programs are often composed of components written in different programming languages, which interact with one another via some kind of foreign function interface (FFI). In this paper, we take the first steps towards the goal of developing program logics for multi-language verification. Specifically, we present Melocoton, a multi-language program verification system for reasoning about OCaml, C, and their interactions through the OCaml FFI. Melocoton consists of the first formal semantics of (a large subset of) the OCaml FFI—previously only described in prose in the OCaml manual—as well as the first program logic to reason about the interactions of program components written in OCaml and C. Melocoton is fully mechanized in Coq on top of the Iris separation logic framework.


  • Open Access

    Theorems for free from separation logic specifications

    by Lars Birkedal, Thomas Dinsdale-Young, Armaël Guéneau, Guilhem Jaber, Kasper Svendsen, Nikos Tzevelekos

    Separation logic specifications with abstract predicates intuitively enforce a discipline that constrains when and how calls may be made between a client and a library. Thus a separation logic specification of a library intuitively enforces a protocol on the trace of interactions between a client and the library. We show how to formalize this intuition and demonstrate how to derive "free theorems" about such interaction traces from abstract separation logic specifications. We present several examples of free theorems. In particular, we prove that a so-called logically atomic concurrent separation logic specification of a concurrent module operation implies that the operation is linearizable. All the results presented in this paper have been mechanized and formally proved in the Coq proof assistant using the Iris higher-order concurrent separation logic framework.


  • Verified Characteristic Formulae for CakeML

    by Armaël Guéneau, Magnus O. Myreen, Ramana Kumar, Michael Norrish


  • Open Access

    The ins and outs of iteration in Mezzo

    by Armaël Guéneau, François Pottier, Jonathan Protzenko

    This is a talk proposal for HOPE 2013. Using iteration over a collection as a case study, we wish to illustrate the strengths and weaknesses of the prototype programming language Mezzo.