Pour satisfaire les exigences du marché, les outils de vérification formelle doivent permettre aux concepteurs de vérifier des descriptions complexes et de raisonner sur des domaines de valeurs grands ou infinis. Il est nécessaire de se concentrer sur la correction d'algorithmes et sur les propriétés mathématiques essentielles des blocks à concevoir. La plupart des outils de vérification formelle comme les "Model-checkers" sont restrictifs car ils ne peuvent travailler avec des niveaux plus haut que le "RTL", et ils sont également limités sur le nombre total d'états. Les démonstrateurs de théorèmes ne souffrent pas de ces restrictions, mais ne sont pas automatiques et requièrent des méthodes pour faciliter leur utilisation systématique. Cette thèse aborde la vérification formelle de descriptions VHDL au moyen du démonstrateur ACL2. Nous proposons un environnement combinant simulation symbolique et démonstrateur de théorèmes pour l'analyse formelle de descriptions de haut niveau d'abstraction. Plus précisément, notre approche consiste à développer des méthodes<br />- pour formaliser un sous-ensemble de VHDL,<br />- pour "diriger" le démonstrateur pour effectuer de la simulation symbolique<br />- pour utiliser ces résultats pour les preuves.<br />Un outil a été développé combinant des traducteurs (VHDL vers ACL2), des moteurs de simulation symbolique et de preuves, et une interface utilisateur. Les définitions et les théorèmes sont générés automatiquement. Un même modèle généré est ainsi utilisé pour toutes les tâches. Nous aspirons à fournir au concepteur une méthodologie pour insérer la vérification formelle le plus tôt possible dans le cycle de conception. Le démonstrateur est utilisé pour des manipulations symboliques et pour prouver qu'ils sont équivalents à une fonction spécifiée. Le résultat de cette thèse est de rendre la technique de démonstration de théorèmes acceptable dans une équipe de concepteur du point de vue de la facilité d'utilisation, et de diminuer le temps de vérification.

Cette thèse développe des outils permettant de prouver qu’un système dynamique est sûr. En supposant qu’une partie de l’espace d’état est dangereuse, un système dynamique est dit sûr lorsque son état n’atteint jamais cette partie dangereuse au cours du temps, quel que soit l’état initial appartenant à un ensemble d’états initiaux admissibles et quel que soit le niveau de perturbation restant dans un domaine admissible. Les outils proposés cherchent à établir des preuves de sûreté pour des systèmes décrits par des modèles dynamiques non-linéaires et des modèles dynamiques hybrides. Prouver qu’un système dynamique est sûr en calculant explicitement l’ensemble des trajectoires possibles du système lorsque le modèle dynamique est non-linéaire et perturbé reste une tâche très difficile. C’est pourquoi cette thèse aborde ce problème à l’aide de fonctions barrières paramétrées. Une barrière, lorsqu’elle existe, permet de partitionner l’espace d’état et d’isoler l’ensemble des trajectoires possibles de l’état du système de la partie dangereuse de l’espace d’état. La fonction paramétrique décrivant la barrière doit satisfaire un certain nombre de contraintes impliquant la dynamique du modèle, l’ensemble des états initiaux possibles, et l’ensemble dangereux. Ces contraintes ne sont pas convexes en général, ce qui complique la recherche de fonctions barrières satisfaisantes. Précédemment, seules des fonctions barrières polynomiales ont été considérées pour des modèles dynamiques polynomiaux. Cette thèse considère des systèmes dynamiques relativement généraux avec des barrières paramétriques quelconques. Les solutions présentées exploitent des outils de satisfaction de contraintes sur des domaines continus et des outils issus de l’analyse par intervalles. Dans un premier temps, cette thèse considère des systèmes dynamiques non-linéaires à temps continu. Le problème de conception d’une barrière paramétrique est formulé comme un problème de satisfaction des contraintes sur des domaines réels avec des variables quantifiées de manière existentielle et universelle. L’algorithme CSC-FPS a été adapté afin de résoudre le problème de synthèse de barrière. Cet algorithme combine une exploration de l’espace des paramètres de la barrière et une phase de vérification des propriétés de la barrière. A l’aide de contracteurs, il est possible de significativement accélérer la recherche de solutions. Dans un second temps, ces résultats sont étendus au cas de systèmes décrits par des modèles dynamiques hybrides. La propriété de sûreté doit être prouvée lors de l’évolution à temps continu du système dynamique, mais aussi pendant les transitions du système. Ceci nécessite l’introduction de contraintes supplémentaires qui lient les fonctions barrières associées à chaque mode à temps continu entre elles. Réaliser la synthèse de toutes les fonctions barrières pour les différents modes simultanément n’est envisageable que pour des systèmes de très petite dimension avec peu de modes. Une approche séquentielle a été proposée. Les contraintes liées aux transitions sont introduites progressivement entre les modes pour lesquels une barrière a déjà été obtenue. Lorsque certaines contraintes de transition ne sont pas satisfaites, une méthode de backtracking doit être mise en œuvre afin de synthétiser des barrières offrant une meilleure prise en compte des contraintes de transition non satisfaites. Ces approches ont été évaluées et comparées avec des techniques de l’état de l’art sur des systèmes décrits par des modèles à temps continu et des modèles hybrides. / This thesis addresses the problem of proving the safety of systems described by non-linear dynamical models and hybrid dynamical models. A system is said to be safe if all trajectories of its state do not reach an unsafe region. Proving the safety of systems by explicitly computing all its trajectories when its dynamic is non-linear or when its behavior is described by an hybrid model with non-linear dynamics remains a challenging task. This thesis considers the barrier function approach to prove the safety of a system. A barrier function, when it exists, partitions the state space and isolates the trajectories of the system starting from any possible initial values of the state and the unsafe part of the state space. The set of constraints, which have to be satisfied by a barrier function are usually non-convex, rendering the search of satisfying barrier functions hard. Previously, only polynomial barrier functions were taken in consideration and for systems with polynomial dynamics. This thesis considers relatively general dynamical systems with generic non-linear barrier functions. The solutions presented are based on template barrier functions, constraint satisfaction problems, and interval analysis. The first part of the thesis focuses on non-linear dynamical systems. The barrier function design problem is formulated as a constraint satisfaction problem that can be solved using tools from interval analysis. This formulation allows one to prove the safety of a non-linear dynamical system by finding the parameters of a template barrier function such that all constraints are satisfied using the FPS-CSC algorithm, which has been adapted and supplemented with contractors to improve its efficiency. The second part of the thesis is dedicated to the design of barrier functions for systems described by hybrid dynamical models. Safety properties have to be proven during the continuous-time evolution of the system, but also during transitions. This leads to additional constraints that have to be satisfied by candidate barrier functions. Solving all the constraints simultaneously to find all the barrier functions is usually computationally intractable. In the proposed approach, the algorithm explores all the locations sequentially. Transition constraints are introduced progressively between the already explored locations. Backtracking to previous location is considered when transition constraints are not satisfied. The efficiency of the proposed approaches has been compared with state-of-the-art solutions.

Comme tout logiciel, les compilateurs, et tout particulièrement les compilateurs optimisant, peuvent être défectueux. Il est donc possible qu'ils changent la sémantique du programme compilé, et par conséquent ses propriétés. Dans le cadre de développement de logiciels critiques, où des méthodes formelles sont utilisées pour s'assurer qu'un programme satisfait certaines propriétés, et cela avant qu'il soit compilé, cela pose un problème de fond. Une solution à ce problème est de vérifier le compilateur en s'assurant qu'il préserve la sémantique des programmes compilés. Dans cette thèse, nous évaluons une méthode nouvelle pour développer des passes de compilations sûres: la vérification formelle de validateurs de traduction. D'une part, cette méthode utilise la vérification formelle à l'aide d'assistant de preuve afin d'offrir le maximum de garanties de sûreté sur le compilateur. D'autre part, elle repose sur l'utilisation de la validation de traduction, où chaque exécution du compilateur est validée a posteriori, une méthode de vérification plus pragmatique qui a permis de vérifier des optimisations avancées. Nous montrons que cette approche nouvelle du problème de la vérification de compilateur est viable, et même avantageuse dans certains cas, à travers quatre exemples d'optimisations réalistes et agressives: le list scheduling, le trace scheduling, le lazy code motion et enfin le software pipelining.

Ce travail porte sur la programmation et la verification des systemes reactifs. Il consiste dans une premiere partie en la definition d'un langage mixte imperatif/declaratif, nomme ArgoLus, fonde sur les langages synchrones Argos et Lustre. Argos est un langage imperatif a base d'automates paralleles et hierarchises. Lustre est un langage declaratif fonde sur le modele flots de donnees. Le langage ArgoLus permet de melanger au niveau source ces deux langages. La definition des traductions structurelles d'ArgoLus en Argos ou en Lustre offre deux solutions interessantes pour mettre en oeuvre ce langage, tout en profitant des environnements deja existants. Dans un deuxieme temps la semantique d'Argos en termes de graphes temporises a ete definie. Initialement, celle-ci est definie en termes de systemes de transitions etiquetees. L'inconvenient de ce modele est lie au phenomene d'explosion du nombre d'etats qui limite les possibilites de verification formelle. Une des causes de cette explosion est la presence dans les programmes de compteurs d'occurrences d'evenement. Les graphes temporises sont des automates etendus avec des compteurs de temps, dont la taille est independante des valeurs limites des compteurs du programme. Par consequent, ils sont moins sensibles au phenomene d'explosion du nombre d'etats, d'ou une amelioration des possibilites de verification formelle. De plus, il est possible grace a ce modele d'exprimer des proprietes quantitatives faisant reference au temps. Enfin, un troisieme aspect de ce travail porte sur l'utilisation pour les systemes reactifs d'outils de verification formelle, non concus exactement pour ce type de systemes.

Nous rappelons tout d'abord le principe des procedures de decision classiques,qui reposent sur des algorithmes de raffinement de partitions. Cette approche necessite de construire au prealable les relations de transition des deux systemes a comparer, ce qui constitue une limitation en pratique. Nous proposons par consequent un algorithme original, base sur un parcours en profondeur du produit synchrone des deux systèmes, qui permet d'effectuer la comparaison ``a la volee'', sans jamais construire ni mémoriser explicitementles deux relations de transition. L'algorithme de comparaison ``a la volée'' a ete mis en œuvre au sein du logiciel de verification Aldebaran dans le cas de différentes relations : la bisimulation forte, l'équivalence observationnelle, la tau*a-bisimulation, la delay bisimulation et la bisimulation de branchement, ainsi que le preordre et l'equivalence de surete. Son application a la verification de plusieurs programmes Lotos de taille realiste a confirme l'interet pratique de notre approche par rapport aux methodes classiques. Enfin, nous nous interessons egalement a la generation d'un diagnostic lorsque les deux systemes de transitions etiquetees a comparer ne sont pas equivalents : les procedures de decision implementees dans Aldebaran fournissent le cas echeant un ensemble de sequences d'execution discriminantes, minimales pour une relation d'ordre donnee.

Ce travail porte sur la verification formelle de programmes paralleles. Parmi les methodes habituellement utilisees, nous nous interessons aux methodes basees sur la construction d'un modele du programme a verifier; la verification proprement dite s'effectue sur ce modele. Cette approche est limitee par l'explosion de la taille du modele, des que le programme traite est de complexite realiste. Notre but est l'etude et la mise en oeuvre de techniques permettant d'effectuer la verification malgre cette explosion. Les techniques que nous presentons sont liees par une caracteristique commune : l'utilisation de methodes symboliques de representation du modele. Nous etudions en premier lieu des techniques de reduction de modeles. Ces reductions s'operent par rapport a des relations d'equivalence basees sur la notion de bisimulation. Nous etudions en particulier un algorithme de minimisation de modele (\em pendant ) sa generation(Generation de Modele Minimal). Dans une seconde partie, nous nous interessons a deux techniques symboliques de representation de modeles. Il s'agit d'une part de Graphes de Decision Binaires, qui permettent la manipulation efficace de formules booleennes, et d'autre part de systemes d'inequations lineaires, connus sous le nom de polyedres convexes, pour la manipulation de variables entieres. L'utilisation de ces techniques permet de representer et manipuler des modeles de taille souvent prohibitive pour des methodes enumeratives classiques. Nous presentons la mise en oeuvre de methodes de comparaison et reduction de modeles aves les Graphes de Decision Binaires, avec en particulier l'algorithme de Generation de Modele Minimal. L'application de l'outil correspondant a plusieurs exemples de programmes lotos a permis de montrer l'interet, mais aussi les limites de l'utilisation de cette representation symbolique. Enfin, nous presentons une methode d'analyse statique de protocoles, basee sur l'utilisation des polyedres convexes. Cette analyse permet le calcul d'approximations superieures d'invariants du programme et de verifier la veracite de proprietes definies en termes de variables du programme.

Le processus de certification de logiciels est dans la plupart des<br /> cas une tâche laborieuse et coûteuse qui nécessite aussi bien des<br /> méthodes mathématiques, pour exprimer sans ambiguïté et de façon<br /> structurée le comportement attendu du logiciel, que des outils<br /> automatiques pour vérifier ses propriétés. Parmi les techniques de<br /> preuve, la récurrence est parfaitement adaptée pour raisonner sur<br /> des structures de données infinies, comme les entiers et les<br /> listes, ou des systèmes paramétrés.<br /> <br /> Cette thèse comprend deux parties, l'une théorique, l'autre<br /> applicative. La première partie est centrée autour d'un nouveau<br /> concept, l'\emph(ensemble couvrant contextuel) (ECC). Le principe<br /> de preuve par récurrence avec ECC est exprimé par un système<br /> d'inférence abstrait qui introduit des conditions suffisantes pour<br /> son application correcte. La conception modulaire de règles<br /> d'inférence concrètes est un avantage de cette approche. Comme<br /> étude de cas, nous spécifions le système d'inférence du<br /> démonstrateur SPIKE en tant qu'instance de ce système.<br /> <br /> Dans la deuxième partie, nous analysons tout d'abord le problème<br /> d'interactions de services téléphoniques. Nous proposons une<br /> méthodologie pour les détecter et les résoudre, reposant sur des<br /> techniques basées sur la réécriture conditionnelle et la<br /> récurrence. Dans une autre application, nous obtenons, à l'aide<br /> du démonstrateur PVS, la première preuve formelle de l'équivalence<br /> entre deux algorithmes de conformité du protocole ABR. Puis,<br /> nous utilisons SPIKE pour vérifier complètement automatiquement<br /> la majorité des 80 lemmes de cette preuve.