Hdr
Année : 2023
Résumé
Separation Logic brought a major breakthrough in the area of program verification. Since its introduction, Separation Logic has made its way into a number of practical tools that are used on a daily basis for verifying programs, ranging from operating systems kernels and file systems to data structures and graph algorithms. These programs are written in a wide variety of programming languages at different abstraction levels, ranging from machine code and assembly, to C, Java, OCaml, and Rust, just to name a few. Numerous extensions to Separation Logic have been proposed over the past two decades. In this habilitation manuscript, I present an overview of my own contributions---and that of my co-authors---over the period from 2009 to 2022. The manuscript is organized in three main parts. The first part describes a foundational set up of sequential Separation Logic, with the logic being proved sound with respect to a semantics mechanized in an interactive proof assistant. The presentation targets a imperative lambda-calculus, sufficiently minimalistic to allow for an easy-to-teach presentation of the theory, yet sufficiently rich to support the verification of realistic programs. The second part presents the technique of characteristic formulae, which enables smooth proofs of practical programs in a proof assistant. Compared with the characteristic formulae introduced in my PhD thesis, I here give a simplified presentation based on weakest preconditions and, most importantly, I show how to justify characteristic formulae in a foundational manner. The third part of this manuscript describes extensions to Separation Logic for resource analysis: time credits for establishing amortized execution bounds, big-O notation to support asymptotic reasoning, and space credits to establish space bounds in the presence of a garbage collector. The manuscript ends with two closing chapters. One provides a survey of publications on Separation Logic for sequential programs. The other covers research perspectives.
Origine | Fichiers produits par l'(les) auteur(s) |
---|---|
Licence |
Copyright (Tous droits réservés)
|
Arthur Charguéraud : Connectez-vous pour contacter le contributeur
https://inria.hal.science/tel-04076725
Soumis le : vendredi 21 avril 2023-09:07:32
Dernière modification le : jeudi 14 novembre 2024-15:58:07
Archivage à long terme le : samedi 22 juillet 2023-18:11:42
Dates et versions
Licence
Copyright (Tous droits réservés)
- HAL Id : tel-04076725 , version 1
Citer
Arthur Charguéraud. A Modern Eye on Separation Logic for Sequential Programs. Computer Science [cs]. Université de Strasbourg, 2023. ⟨tel-04076725⟩
Collections
159
Consultations
270
Téléchargements