Abductive reasoning modulo theories and an application to program verification

Le travail présenté dans cette thèse introduit une méthode générique pour calculer les impliqués premiers d'une formule logique donnée dans une théorie décidable. Il s'agit intuitivement des conséquences clausales les plus générales de cette formule modulo cette théorie. Cette méthode fonctionne en ajoutant récursivement à un ensemble initialement vide des littéraux extraits d'un ensemble d'hypothèses présélectionnées, et ce jusqu'à ce qu'elle puisse démontrer que la disjonction des littéraux de cet ensemble est une conséquence de la formule sur laquelle elle travaille. On démontrera la terminaison, la correction et la complétude de cet algorithme. Cela confirmera qu'il calcule effectivement des impliqués de la formule de départ et qu'il retourne tous les impliqués premiers qui peuvent être construits à partir de l'ensemble d'hypothèses de départ. On construira ensuite à partir de cette méthode un algorithme l'appliquant à la génération d'invariants de boucles de programmes que l'on cherche à vérifier. On présentera également une implémentation C++ de ces deux méthodes, regroupées dans une infrastructure logicielle baptisée Abdulot. Cette implémentation sera utilisée pour évaluer expérimentalement les deux méthodes. On découvrira à cette occasion qu'elles sont capables de générer des solutions pour une large classe de problèmes.Cette thèse présente également un travail introductif sur la minimisation de modèles en logique de séparation et son implémentation. La méthode décrite pourrait également être utilisée pour résoudre des instances de bi-abduction en logique de séparation, à l'aide d'un algorithme qui sera décrit mais pas implémenté.This thesis introduces a generic method to compute the prime implicates of a logical formula, i.e., the most general clausal consequences of a given logical formula, in any given decidable theory. The principle used is to recursively add to an initially empty set, literals taken from a preselected set of hypotheses until it can be proven that the disjunction of these literals is a consequence of the formula under consideration. Proofs of the termination, correctness and completeness of this algorithm are provided, which ensures that the clauses the method computes are indeed implicates and that all the prime implicates that can be constructed from the initial set are indeed returned. This algorithm is then applied in the context of program verification, in which it is used to generate loop invariants that permit to verify assertions on programs. The Abdulot framework, a C++ implementation of the system, is also introduced. Technical considerations required for the design of such systems are detailed, such as their insertion within a well-furnished ecosystem of provers and SMT-Solvers. This implemented framework will be used to perform an experimental evaluation of the method and will show its practical relevance, as it can be used to solve a large scope of problems.This thesis also presents introductory work on an implicant minimizer and applies it in the context of separation logic. The method described in this part could also be used to perform bi-abduction in separation logic, with an algorithm that is described but has not been implemented