Deductive Verification via Ghost Debugging
Vérification déductive via débogage fantôme
Résumé
We present a verification approach based on auxiliary programs, which we call ghost debuggers.
This approach leads to notable verification gains when the structure of the program does not match the
execution structure, notably when that latter structure is recursive. We present a theoretical foundation
of our approach over a flavor of transfinite games, which let us specify and prove fine-grained properties
about infinite behaviors of programs. By making use of the game structure, we also show that our approach
can be applied to relational properties like simulation between programs. Our approach is backed by a
mechanized development in the Why3 tool, which formally proves sound the Hoare-style logic backbone
of our approach.
Nous présentons une nouvelle approche de vérification de programmes que nous appelons
Débogage Fantôme. Cette approche apporte des gains notables lorsque la structure syntaxique du code
source du programme à vérifier ne correspond pas à la structure de son exécution, notamment lorsque cette
dernière est récursive. Nous présentons un fondement théorique de notre approche sur une variante de
jeux transfinis, qui nous permet de spécifier et prouver des propriétés fines sur les comportements infinis
des programmes. En utilisant la structure du jeu, nous montrons également que notre approche peut être
appliquée à des propriétés relationnelles comme la simulation entre les programmes. Notre approche
est formalisée par un développement dans l’outil Why3, qui nous permet de valider mécaniquement la
correction de la logique à la Hoare qui sous-tend notre approche.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...