La vérification en ligne de spécifications formelles permet de créer des détecteurs d'erreur dont le pouvoir de détection dépend en grande partie du formalisme vérifié à l'exécution. Plus le formalisme est puissant plus la séparation entre les exécutions correctes et erronées peut être précise. Cependant, l'utilisation des vérifieurs en-ligne dans le but de détecter des erreurs est entravée par deux problèmes récurrents : le coût à l'exécution de ces vérifications, et le flou entourant les propriétés sémantiques exactes des signaux d'erreur ainsi générés. L'objectif de cette thèse est de clarifier les conditions d'utilisation de tels détecteurs dans le cadre d'applications " temps réel " critiques. Dans ce but, nous avons donné l'interprétation formelle de la notion d'erreur comportementale " temps réel". Nous définissions la propriété de détection " au plus tôt " qui permet de d'identifier la classe des détecteurs qui optimisent la latence de détection. Pour illustrer cette classe de détecteurs, nous proposons un prototype qui vérifie un comportement décrit par un automate temporisé. La propriété de détection au plus tôt est atteinte en raisonnant sur l'abstraction temporelle de l'automate et non sur l'automate lui-même. Nos contributions se déclinent dans trois domaines, la formalisation de la détection au plus tôt, sa traduction pour la synthèse de détecteurs d'erreur à partir d'automate temporisés, puis le déploiement concret de ces détecteurs sur une plate-forme de développement temps réel, Xenomai.

Le langage UML est devenu un standard de fait, y compris pour le développement de systèmes critiques. Néanmoins, les outils actuels apportent peu d'aide pour exploiter et vérifier les modèles proposés, surtout en cours de développement. Cette thèse se concentre sur l'aide à la construction d'architectures en UML durant les phases d'analyse et de conception de systèmes réactifs. Elle vise à développer un cadre théorique et pragmatique pour mettre en œuvre une approche incrémentale. Ce cadre fournit un outil permettant de vérifier les architectures durant leur modélisation. Les architectures sont modélisées par des diagrammes UML de structures composites alors que les composants primitifs sont présentés par une combinaison de diagrammes de machines d'états et de diagramme d'activités. Ce travail offre les moyens de vérifier d'une part si une nouvelle architecture est un raffinement, une extension ou un incrément de celle définie durant les étapes précédentes, et d'autre part si un composant est compatible avec un environnement ou s'il est substituable par un autre. L'analyse des architectures impose de leur donner une sémantique formelle. Concernant les composants primitifs, nous leur associons une sémantique en LTS (Labelled Transition Systems) ce qui nous a conduit à définir une procédure de transformation automatique de machines d'états et diagrammes d'activités en LTS. Concernant les composants composites, nous leur associons un LTS en transformant un diagramme de structure composite en une spécification Exp.Open, puis en générant la fusion des LTS grâce à la boîte à outils CADP. Dans un second temps, nous avons mis en œuvre des techniques de vérifications de relations de conformité de LTS que sont les préordres de raffinement, d'extension, et d'incrément. Nous avons également défini et implanté une relation de compatibilité et de substituabilité. L'ensemble de ces techniques de construction incrémentale se positionne selon deux axes. L'axe vertical représente le niveau d'abstraction. L'évolution d'une architecture peut se faire sur cet axe dans deux sens : i) par des techniques de raffinement dans le sens descendant et ii) par des techniques d'abstraction dans le sens ascendant. L'axe horizontal représente le niveau de couverture des exigences. L'évolution d'une architecture peut se faire sur cet axe selon deux sens : i) par des techniques d'extension et ii) par des techniques de restriction. Ces travaux ont été réalisés de façon théorique et pratique : ils ont donné lieu au développement d'un outil dédié à la construction incrémentale de modèles UML, appelé IDCM (Incremental Development of Conforming Models), regroupant la transformation de modèles et la mise en œuvre de l'ensemble des relations incrémentales. Ceci a été validé sur diverses études de cas. / UML is becoming a de facto standard, including for development of dependable systems. However, current tools offer little help to take benefit of proposed models and to verify them, especially during development phases. This thesis focuses on supporting construction of UML architectures of reactive systems. It aims at developing a theoretic and pragmatic framework to implement the incremental approach. The framework provides tools to verify the coherenceof architectures during the modelling phase. Architectures are modelled by UML diagram of composite structures while primitive components are represented by a combination of state machine diagram and activity diagram. This work provides a means to verify in one hand if a new architecture is a refinement, an extension or an increment of those defined in the previous steps, and in another hand, if a component is compatible with an environment or if it is substitutableby another.In order to analyse UML architectures, we must give them a formal semantics. We associated primitive components with LTS (Labelled Transition Systems) which led us to define a procedure for automatic transformation of state machines and activities diagrams into LTS. We associated composite components with LTS by transforming a diagram of composite structure into Exp.Open specification, then by generating LTS fusion with the toolbox CADP. We have implemented verification techniques of conformance relations on LTS such as the preorders: refinement, extension, and increment. We also defined and implemented compatibility relation and substitutability relation. All these incremental construction techniques are positioned along two axes. The vertical axis represents the level of bstraction.The development of an architecture following this axis in two directions: i) refinement techniques in the downward direction and ii) abstraction techniques in the upward direction. The horizontal axis represents the coverage level of requirements. The development of architectures can be realized following this axis in two directions : i) extension direction and ii) restrictiondirection.This work has been carried out in theory and practice : it has led to the development of a dedicated tool for incremental construction of UML models, called IDCM (Incremental Development of Conforming Models), grouping the transformation of models and the implementation of a set of incremental relations. This has been validated on various case studies.

Les systèmes temps-réel critiques sont de plus en plus complexes, et les exigences fonctionnelles et non-fonctionnelles ne cessent plus de croître. Le flot de conception de tels systèmes doit assurer, parmi d'autres propriétés, le déterminisme fonctionnel et la prévisibilité temporelle. Le déterminisme fonctionnel est inhérent aux modèles de calcul flot de données (ex. KPN, SDF, etc.) ; c'est pour cela qu'ils sont largement utilisés pour modéliser les systèmes embarqués de traitement de flux. Un effort considérable a été accompli pour résoudre le problème d'ordonnancement statique périodique et à mémoire de communication bornée des graphes flots de données. Cependant, les systèmes embarqués temps-réel optent de plus en plus pour l'utilisation de systèmes d'exploitation temps-réel et de stratégies d'ordonnancement dynamique pour gérer les tâches et les ressources critiques. Cette thèse aborde le problème d'ordonnancement temps-réel dynamique des graphes flots de données ; ce problème consiste à assigner chaque acteur dans un graphe à une tâche temps-réel périodique (i.e. calcul des périodes, des phases, etc.) de façon à : (1) assurer l'ordonnançabilité des tâches sur une architecture et pour une stratégie d'ordonnancement (ex. RM, EDF) données ; (2) exclure statiquement les exceptions d'overflow et d'underflow sur les buffers de communication ; et (3) optimiser les performances du système (ex. maximisation du débit, minimisation des tailles des buffers).

Les circuits intégrés ne sont pas à l'abri d'interférences naturelles ou malveillantes qui peuvent provoquer des fautes transitoires conduisant à des erreurs (Soft errors) et potentiellement à un comportement erroné. Ceci doit être maîtrisé surtout dans le cas des systèmes critiques qui imposent des contraintes de sûreté et/ou de sécurité. Pour optimiser les stratégies de protection de tels systèmes, il est fondamental d'identifier les éléments les plus critiques. L'évaluation de la criticité de chaque bloc permet de limiter les protections aux blocs les plus sensibles. Cette thèse a pour objectif de proposer des approches permettant d'analyser, tôt dans le flot de conception, la robustesse d'un système numérique. Le critère clé utilisé est la durée de vie des données stockées dans les registres, pour une application donnée. Dans le cas des systèmes à base de microprocesseur, une approche analytique a été développée et validée autour d'un microprocesseur SparcV8 (LEON3). Celle-ci repose sur une nouvelle méthodologie permettant de raffiner les évaluations de criticité des registres. Ensuite, une approche complémentaire et plus générique a été mise en place pour calculer la criticité des différents points mémoires à partir d'une description synthétisable. L'outil mettant en œuvre cette approche a été éprouvé sur des systèmes significatifs tels que des accélérateurs matériels de chiffrement et un système matériel/logiciel basé sur le processeur LEON3. Des campagnes d'injection de fautes ont permis de valider les deux approches proposées dans cette thèse. En outre, ces approches se caractérisent par leur généralité, leur efficacité en termes de précision et de rapidité, ainsi que leur faible coût de mise en œuvre et leur capacité à ré-exploiter les environnements de validation fonctionnelle. / Integrated circuits are not immune to natural or malicious interferences that may cause transient faults which lead to errors (soft errors) and potentially to wrong behavior. This must be mastered particularly in the case of critical systems which impose safety and/or security constraints. To optimize protection strategies of such systems, it is essential to identify the most critical elements. The assessment of the criticality of each block allows limiting the protection to the most sensitive blocks. This thesis aims at proposing approaches in order to analyze, early in the design flow, the robustness of a digital system. The key criterion used is the lifetime of data stored in the registers for a given application. In the case of microprocessor-based systems, an analytical approach has been developed and validated on a SparcV8 microprocessor (LEON3). This approach is based on a new methodology to refine assessments of registers criticality. Then a more generic and complementary approach was implemented to compute the criticality of all flip-flops from a synthesizable description. The tool implementing this approach was tested on significant systems such as hardware crypto accelerators and a hardware/software system based on the LEON3 processor. Fault injection campaigns have validated the two approaches proposed in this thesis. In addition, these approaches are characterized by their generality, their efficiency in terms of accuracy and speed and a low-cost implementation. Another benefit is also their ability to re-use the functional verification environments.

Les systèmes réactifs sont de plus en plus présents dans de nombreux secteurs d´activité tels que l´automobile, les télécommunications et l´aéronautique. Ces systèmes réalisent des tâches complexes qui sont souvent critiques. Au vu des conséquences catastrophiques que pourrait entraîner une défaillance dans ces systèmes, suite à la présence de fautes matérielles (processeurs et média de communication), il est essentiel de prendre en compte la tolérance aux fautes dans leur conception. En outre, plusieurs domaines exigent une évaluation quantitative du comportement de ces systèmes par rapport à l'occurrence et à l'activation des fautes. Afin de concevoir des systèmes sûrs de fonctionnement, j'ai proposé dans cette thèse trois méthodologies de conception basées sur la théorie d'ordonnancement et la redondance active et passive des composants logiciels du système. Ces trois méthodologies permettent de résoudre le problème de la génération automatique de distribution et d'ordonnancements temps réel, fiables et tolérants aux fautes. Ce problème étant NP-difficile, ces trois méthodologies sont basées sur des heuristiques de type ordonnancement de liste. Plus particulièrement, les deux premières méthodologies traitent le problème de la tolérance aux fautes matérielles des processeurs et des media de communication, respectivement pour des architectures à liaisons point-à-point et des architectures à liaison bus. La troisième méthodologie traite le problème de l'évaluation quantitative d'une distribution/ordonnancement en terme de fiabilité à l'aide d'une heuristique bi-critère originale. Ces méthodologies offrent de bonnes performances sur des graphes d'algorithme et d'architecture générés aléatoirement.

Vu le développement important des micro-systèmes, leur utilisation sous forme de nappes dans les systèmes de commande-contrôle critiques est une vraie opportunité. Cela soulève néanmoins des défis, parmi lesquels, la définition d'un système de communication à haut niveau d'intégrité. <br />L'étude que nous avons effectuée sur des réseaux standard montre que les protections classiques à base de codes CRC ne permettent pas d'obtenir le niveau d'intégrité visé. <br />Pour l'atteindre, nous avons proposé une solution originale - fonction de contrôle évolutive - qui tire profit du fait que, pour les systèmes de commande-contrôle envisagés (systèmes à dynamique lente), l'intégrité est à considérer sur un lot de messages et non sur un seul message. La solution proposée a ensuite été validée via des simulations Matlab-Simulink. <br />Le cas d'étude utilisé est celui de systèmes de commande de vol du futur, en vue de pouvoir commander des nappes de milliers de micro-surfaces tels que des micro-spoilers.

Cette étude s’inscrit dans le domaine de l’intelligence artificielle, plus précisément au croisement des deux domaines que sont la planification autonome en environnement probabiliste et la vérification formelle probabiliste. Dans ce contexte, elle pose la question de la maîtrise de la complexité face à l’intégration de nouvelles technologies dans les systèmes critiques : comment garantir que l’ajout d’une intelligence à un système, sous la forme d’une autonomie, ne se fasse pas au détriment de la sécurité ? Pour répondre à cette problématique, cette étude a pour enjeu de développer un processus outillé, permettant de concevoir des systèmes auto-adaptatifs critiques, ce qui met en œuvre à la fois des méthodes de modélisation formelle des connaissances d’ingénierie, ainsi que des algorithmes de planification sûre et optimale des décisions du système. / This study takes place in the broad field of Artificial Intelligence, specifically at the intersection of two domains : Automated Planning and Formal Verification in probabilistic environment. In this context, it raises the question of the integration of new technologies in critical systems, and the complexity it entails : How to ensure that adding intelligence to a system, in the form of autonomy, is not done at the expense of safety ? To address this issue, this study aims to develop a tool-supported process for designing critical, self-adaptive systems. Throughout this document, innovations are therefore proposed in methods of formal modeling and in algorithms for safe and optimal planning.

Les langages synchrones tels que Signal, Lustre et Esterel sont dédiés à la conception de systèmes critiques. Leurs compilateurs, qui sont de très gros programmes complexes, peuvent a priori se révéler incorrects dans certains situations, ce qui donnerait lieu alors à des résultats de compilation erronés non détectés. Ces codes fautifs peuvent invalider des propriétés de sûreté qui ont été prouvées en appliquant des méthodes formelles sur les programmes sources. En adoptant une approche de validation de la traduction, cette thèse vise à prouver formellement la correction d'un compilateur optimisé et industriel de Signal. La preuve de correction représente dans un cadre sémantique commun le programme source et le code compilé, et formalise une relation entre eux pour exprimer la préservation des sémantiques du programme source dans le code compilé. / Synchronous languages such as Signal, Lustre and Esterel are dedicated to designing safety-critical systems. Their compilers are large and complicated programs that may be incorrect in some contexts, which might produce silently bad compiled code when compiling source programs. The bad compiled code can invalidate the safety properties that are guaranteed on the source programs by applying formal methods. Adopting the translation validation approach, this thesis aims at formally proving the correctness of the highly optimizing and industrial Signal compiler. The correctness proof represents both source program and compiled code in a common semantic framework, then formalizes a relation between the source program and its compiled code to express that the semantics of the source program are preserved in the compiled code.

Les langages synchrones tels que SIGNAL, LUSTRE et ESTEREL sont dédiés à la conception de systèmes critiques. Leurs compilateurs, qui sont de très gros programmes complexes, peuvent a priori se révéler incorrects dans certains situations, ce qui donnerait lieu alors à des résultats de compilation erronés non détectés. Ces codes fautifs peuvent invalider des propriétés de sûreté qui ont été prouvées en appliquant des méthodes formelles sur les programmes sources. En adoptant une approche de validation de la traduction, cette thèse vise à prouver formellement la correction d'un compilateur optimisé et industriel de SIGNAL. La preuve de correction représente dans un cadre sémantique commun le programme source et le code compilé, et formalise une relation entre eux pour exprimer la préservation des sémantiques du programme source dans le code compilé.