Differential program semantics

Sémantique différentielle des programmes Les programmes informatiques sont rarement écrits d'un seul coup, et sont au contraire composés de changements successifs. Il est également fréquent qu'un logiciel soit mis à jour après sa sortie initiale. De tels changements peuvent avoir lieu pour diverses raisons, comme l'ajout de fonctionnalités ou la correction de bugs. Il est en tout cas important d'être capable de représenter ces changements et de raisonner à leur propos pour s'assurer qu'ils implémentent les changements voulus.En pratique, les différences entre programmes sont très souvent représentées comme des différences textuelles sur le code source, listant les lignes de textes ajoutées, supprimées ou modifiées. Cette représentation, bien qu'exacte, ne dit rien de leurs conséquences sémantiques. Pour cette raison, il existe un besoin pour de meilleures représentations des différences sémantiques entre programmes.Notre première contribution est un algorithme de construction de programmes de corrélation, c'est-à-dire, des programmes entrelaçant les instructions de deux autres programmes de telle sorte qu'ils simulent leur sémantiques. Ces programmes de corrélation peuvent alors être analysés pour calculer une sur-approximation des différences sémantiques entre les deux programmes d'entrée. Ce travail est directement inspiré d'un article de Partush et Yahav, qui décrit un algorithme similaire, mais incorrect en présence de boucles avec des instructions `break` ou `continue`. Pour garantir la correction de notre algorithme, nous l'avons formalisé et prouvé à l'aide de l'assistant de preuve Coq.Notre seconde et plus importante contribution est un cadre formel permettant de décrire précisément et de formellement vérifier des différences sémantiques. Ce cadre, complètement formalisé en Coq, représente la différence entre deux programmes à l'aide d'un troisième programme que nous appelons oracle. Contrairement à un programme de corrélation, un oracle n'entrelace pas nécessairement les instructions des deux programmes à comparer, et peut « sauter » des calculs intermédiaires.Un tel oracle est généralement écrit dans un langage de programmation différent des programmes à comparer, ce qui permet de concevoir des langages d'oracles spécifiques à certaines classes de différences, capables de mettre en relation des programmes qui plantent avec des programmes qui s'exécutent correctement.Nous avons conçu de tels langages d'oracles pour couvrir un large éventail de différences sur un langage impératif jouet. Nous avons également prouvé que notre cadre est au moins aussi expressif que celui de la Logique Relationnelle de Hoare en encodant plusieurs variantes de cette dernière sous forme de langages d'oracles, prouvant leur correction dans la foulée.