Differential program semantics
Sémantique différentielle de programme
Résumé
Computer programs are rarely written in one fell swoop. Instead, they are written in a series of incremental changes.
It is also frequent for software to get updated after its initial release. Such changes can occur for various reasons,
such as adding features, fixing bugs, or improving performances for instance. It is therefore important to be able
to represent and reason about those changes, making sure that they indeed implement the intended modifications.
In practice, program differences are very commonly represented as textual differences between a pair of source files,
listing text lines that have been deleted, inserted or modified. This representation, while exact, does not address the
semantic implications of those textual changes. Therefore, there is a need for better representations of the semantics
of program differences.
Our first contribution is an algorithm for the construction of a correlating program, that is, a program interleaving the instructions of two input programs in such a way that it simulates their semantics. Further static analysis can be performed on such correlating programs to compute an over-approximation of the semantic differences between the two input programs. This work draws direct inspiration from an article by Partush and Yahav[32], that describes a correlating program construction algorithm which we show to be unsound on loops that include b r e a k or c o n t i n u e statements. To guarantee its soundness, our alternative algorithm is formalized and mechanically checked within the Coq proof assistant.
Our second and most important contribution is a formal framework allowing to precisely describe and formally verify semantic changes. This framework, fully formalized in Coq, represents the difference between two programs by a third program called an oracle. Unlike a correlating program, such an oracle is not required to interleave instructions of the programs under comparison, and may “skip” intermediate computation steps. In fact, such an oracle is typically written in a different programming language than the programs it relates, which allows designing correlating oracle languages specific to certain classes of program differences, and capable of relating crashing programs with non-crashing ones.
We design such oracle languages to cover a wide range of program differences on a toy imperative language. We also prove that our framework is at least as expressive as Relational Hoare Logic by encoding several variants as correlating oracle languages, proving their soundness in the process.
La comparaison de programmes informatiques est au coeur des pratiques actuelles de développement logiciel : en effet, les programmes informatiques n’étant pas écrits d’un seul coup, mais par des modifications successives souvent effectuées par plusieurs programmeurs, il est essentiel de pouvoir comprendre chacune de ces modifications.
Des outils, tels que d i f f et p a t c h existent pour traiter des différences entre programmes. Cependant, ces outils représentent les différences comme la liste des lignes modifiées, ajoutées ou supprimées du code source d’un programme, et ne traitent pas de sa sémantique.
Il convient donc de trouver des façons de représenter et raisonner à propos des différences entre programmes au niveau sémantique, ce à quoi cette thèse s’attelle.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...