Search

Constraint programming offers efficient languages andtools for solving combinatorial and computationally hard problems such as the ones proposed in program verification. In this thesis, we tackle two families of program verification problems using constraint programming.In both contexts, we first propose a formal evaluation of our contributions before realizing some experiments.The first contribution is about a synchronous reactive language, represented by a block-diagram algebra. Such programs operate on infinite streams and model real-time processes. We propose a constraint model together with a new global constraint. Our new filtering algorithm is inspired from Abstract Interpretation. It computes over-approximations of the infinite stream values computed by the block-diagrams. We evaluated our verification process on the FAUST language (a language for processing real-time audio streams) and we tested it on examples from the FAUST standard library. The second contribution considers probabilistic processes represented by Parametric Interval Markov Chains, a specification formalism that extends Markov Chains. We propose constraint models for checking qualitative and quantitative reachability properties. Our models for the qualitative case improve the state of the art models, while for the quantitative case our models are the first ones. We implemented and evaluated our verification constraint models as mixed integer linear programs and satisfiability modulo theory programs. Experiments have been realized on a PRISM based benchmark.; La programmation par contraintes offre des langages et des outils permettant de résoudre des problèmes à forte combinatoire et à la complexité élevée tels que ceux qui existent en vérification de programmes. Dans cette thèse nous résolvons deux familles de problèmes de la vérification de programmes. Dans chaque cas de figure nous commençons par une étude formelle du problème avant de proposer des modèles en contraintes puis de réaliser des expérimentations. La première contribution concerne un langage réactif synchrone représentable par une algèbre de diagramme de blocs. Les programmes utilisent des flux infinis et modélisent des systèmes temps réel. Nous proposons un modèle en contraintes muni d’une nouvelle contrainte globale ainsi que ses algorithmes de filtrage inspirés de l’interprétation abstraite. Cette contrainte permet de calculer des sur-approximations des valeurs des flux des diagrammes de blocs. Nous évaluons notre processus de vérification sur le langage FAUST, qui est un langage dédié à la génération de flux audio. La seconde contribution concerne les systèmes probabilistes représentés par des chaînes de Markov à intervalles paramétrés, un formalisme de spécification qui étend les chaînes de Markov. Nous proposons des modèles en contraintes pour vérifier des propriétés qualitatives et quantitatives. Nos modèles dans le cas qualitatif améliorent l’état de l’art tandis que ceux dans le cas quantitatif sont les premiers proposés à ce jour. Nous avons implémenté nos modèles en contraintes en problèmes de programmation linéaire en nombres entiers et en problèmes de satisfaction modulo des théories. Les expériences sont réalisées à partir d’un jeu d’essais de la bibliothèque PRISM.

National audience; La programmation par contraintes s'attaque en gé-néraì a desprobì emes statiques, sans notion de temps. Cependant, les méthodes de réduction de domaines pourraient par exemplê etre utiles dans desprobì emes portant sur des flux. C'est le cas de la vérification de programmes temps-réel, avec des variables dont les valeurs peuvent changer a chaque pas de temps. Dans cet article, nous nous intéressons a la vérification de domaines de variables (flux) dans le cadre d'un langage de diagrammes de blocs. Nous proposons une méthode de réduction de domaines de ces flux, pour encadrer finement les valeurs prises au cours du temps. En particulier, nous proposons un nouvel algorithme pour calculer un point fixe dans le cas des boucles temporelles. Nous présentons ensuite une application au langage FAUST, un langage fonctionnel temps réel pour le traitement audio et nous testons notre approche sur différents programmes FAUST standards. Abstract Constraint programming usually deals with static problems. However, domain reduction method could be useful in stream-based problems. This is the case in formal verification of real time programs for which variables can be assigned different values at every single time. In this paper, we focus on domain checking of stream variables in the context of block diagram languages. We propose a reduction algorithm for streams in order to tightly reduce their domains all over the time. Particularly , we propose a new technique to compute fix points of temporal loops. Finally, we apply our method to the FAUST language, which is a real time language for processing and generating audio streams. We also test some standards FAUST programs.

National audience