Cette thèse porte sur la synthèse de superviseurs pour des systèmes a événements discrets temps-réel (SEDTRs) modélisés par des automates temporises (ATs). Comme l'espace d'états d'un AT est en général infini, et que la théorie du contrôle supervise de RAMADGE et WONHAM, que nous avons adaptée, est opérationnelle pour des automates a états finis (AEFs), nous avons utilisé l'approche consistant à transformer les ATs modélisant le procédé et la spécification sous la forme d'AEFs. Nous avons donc tout d'abord étendu et amélioré une méthode de transformation des ATs en AEFs particuliers appelés automates Set-Exp (ASEs). Cette méthode de transformation, appelée SetExp, permet de réduire le problème d'explosion des états et est appropriée pour le contrôle supervise de SEDTRs. Nous avons ensuite amélioré et étendu une méthode de contrôle centralise fondée sur SetExp, c'est-à-dire que les ATs modélisant le procédé et la spécification sont d'abord transformes en ASEs et le problème est résolu en adaptant la théorie de RAMADGE et WONHAM aux ASEs. Pour la résolution du problème de contrôle centralise, nous avons identifié les conditions d'existence de solution et avons proposé une procédure algorithmique pour la synthèse du superviseur le moins restrictif. Suite à cela, nous avons développé une méthode de contrôle modulaire, fondée sur SetExp et la méthode de contrôle centralise. Pour le contrôle modulaire également, nous avons identifié les conditions d'existence de solution et propose une procédure de synthèse de superviseurs modulaires les moins restrictifs. D'autre part, nous avons étendu la méthode de contrôle centralise fondée sur SetExp au cas où le superviseur a une observation partielle des événements du procédé. Pour cette méthode de contrôle sous observation partielle des événements, nous avons identifié les conditions d'existence de solution et propose une procédure pour synthétiser un superviseur sous observation partielle. Enfin, nous avons réalisé un outil logiciel appelé SEAtool, qui implémente la transformation SetExp et les méthodes de contrôle centralise et modulaire. Nous avons étudié, à l'aide de SEAtool, l'application de nos méthodes de contrôles centralise et modulaire a des systèmes concrets simples.

L'analyse d'une chaîne de production manufacturière complète, composée de plusieurs systèmes bouclés temporisés, en utilisant des modèles détaillés est presque impossible à cause des problèmes liés aux tailles des modèles. Une solution pour contourner ces difficultés consiste à utiliser des techniques d'analyse multi-échelles utilisant à la fois des modèles détaillés des système bouclés, lorsque nécessaire, mais aussi des modèles abstraits de certains systèmes bouclés dès que possible. Afin de garantir les résultats lors d'analyses multi-échelles, il convient de garantir que les modèles détaillés des systèmes bouclés ne permettent pas d'évolutions indésirables ne représentant pas un comportement réaliste des système bouclés, et que les modèles abstraits des système bouclés utilisés pendant l'analyse ont un comportement identique aux modèles détaillés de ces mêmes systèmes bouclés. La première contribution de ces travaux est une méthodologie de conception de modèles détaillés, utilisant des automates temporisés, de systèmes bouclés temporisés permettant de supprimer les évolutions irréalistes. Les solutions proposées pour y parvenir se basent sur une conception modulaire, des mécanismes d'urgence et des variables partagées. La seconde contribution de ces travaux est axée sur la vérification de l'équivalence entre les modèles détaillé et abstrait d'un même système bouclé. Pour ce faire, une équivalence conforme aux exigences d'une analyse multi-échelles est retenue, puis une méthode basée sur un automate observateur-séquenceur couplé à un model-checker est décrite. Enfin, la prise en compte d'une équivalence avec tolérances (en valeur et/ou temporelle) est détaillée. / The analysis of a complete industrial production line, composed of several closed-loop systems, using detailed models is almost impossible due to size-related issues. A solution consists in performing a multi-scale analysis which uses some abstract models in place of detailed ones. In order to guarantee the analysis result, the detailed models need to have a correct behavior, and the abstract model of a closed-loop system has to be equivalent to the detailed model of the same closed-loop system. The first contribution details the construction process and the solutions used to build a correct --exempt from unrealistic evolutions-- model of a timed closed-loop system. This is achieved by using an urgency semantics upon timed automata with synchronization variables. The second contribution consists in proposing an equivalence which is suitable for the multi-scale analysis and then in proposing a technique --using formal methods-- to prove the equivalence between the abstract and detailed models.

Les automates temporisés sont un formalisme qui permet de modéliser, vérifier, et synthétiser des systèmes temps-réels. Ils sont dotés d’une sémantique abstraite et mathé- matique, qui permet de formaliser et résoudre plusieurs problèmes de vérification et de synthèse. Cependant, les automates temporisés sont utilisés pour concevoir des modèles, plutôt que décrire des systèmes temps-réels entiers. Ainsi, une fois la phase de conception terminée, il reste à déterminer si les comportements du modèle correspondent à ceux d’un vrai système. Une étape importante de l’implémentation consiste à s’assurer de la robustesse du système. On considère une notion de robustesse sur les automates tem- porisés qui exige que les comportements soient préservés quand le modèle est sujet à des perturbations bornées. Dans cette thèse, plusieurs approches sont étudiées : Dans l’analyse de robustesse, on se demande si un automate temporisés donné préserve ses com- portements sous divers types de perturbations, et on cherche à calculer un majorant sur les perturbations tolérées. La synthèse robuste s’intéresse au calcul d’une loi de contrôle (ou une stratégie) qui guide le système, et tolère des perturbations d’une magnitude calculable. Enfin, dans l’implémentation robuste, on s’intéresse à transformer automatiquement un modèle donné pour le rendre robuste, tout en préservant ses comportements. Plusieurs modèles de perturbations sont considérés : erreurs de mesure de temps (élargissement de gardes), élimination des comportements limites (contraction de gardes), et la restriction du domaine du temps aux valeurs discrètes. On formalise également les problèmes de synthèse robuste comme des jeux entre le contrôleur et un environnement qui perturbe systèmatiquement tout délai choisi par une quantité bornée. Ces problèmes sont étudiés pour les automates temporisés, ainsi que leurs extensions- les jeux temporisés, et les automates et jeux temporisés pondérés. Plusieurs algorithmes d’analyse de robustesse parametrée contre l’élargissement de gardes et la contraction de gardes sont proposés. Deux variantes de la sémantique de jeu pour le problème de synthèse robuste sont également étudiées pour les automates temporisés et leurs extensions. Un logiciel d’analyse de robustesse contre la contraction de gardes, ainsi que des résultats expérimentaux sont présentés. Le problème de l’implémentation robuste est étudié dans deux contextes différents. Tous les algorithmes calculent également un majorant sur les perturbations que le modèle donné est capable de tolérer. / Timed automata are a formalism to model, verify, and synthesize real-time systems. They have the advantage of having an abstract mathematical semantics, which allow formalizing and solving several verification and synthesis problems. However, timed automata are intended to design models, rather than completely describe real systems. Therefore, once the design phase is over, it remains to check whether the behavior of an actual implementation corresponds to that of the timed automaton model. An important step before implementing a system design is ensuring its robustness. This thesis considers a notion of robustness that asks whether the behavior of a given timed automaton is preserved, or can be made so, when it is subject to small perturbations. Several approaches are considered: Robustness analysis seeks to decide whether a given timed automaton tolerates perturbations, and in that case to compute the (maximum) amount of tolerated perturbations. In robust synthesis, a given system needs to be controlled by a law (or strategy) which tolerates perturbations upto some computable amount. In robust implementation, one seeks to automatically transform a given timed automaton model so that it tolerates perturbations by construction. Several perturbation models are considered, ranging from introducing error in time measures (guard enlargement), forbidding behaviors that are too close to boundaries (guard shrinking), and restricting the time domain to a discrete sampling. We also formalize robust synthesis problems as games, where the control law plays against the environment which can systematically perturb the chosen moves, by some bounded amount. These problems are studied on timed automata and their variants, namely, timed games, and weighted timed automata and games. Algorithms for the parameterized robustness analysis against guard enlargements, and guard shrinkings are presented. The robust synthesis problem is studied for two variants of the game semantics, for timed automata, games, and their weighted extensions. A software tool for robustness analysis against guard shrinkings is presented, and experimental results are discussed. The robust implementation problem is also studied in two different settings. In all algorithms, an upper bound on perturbations that the given timed automaton tolerates can be computed.

Cette thèse revisite les problèmes d'accessibilité et de vivacité pour les au-tomates temporisés.L'accessibilité est couramment résolue par le calcul d'un arbre de recherche abstrait. L'abstraction est paramétrée par des bornes provenant des gardes de l'automate. Nous montrons que l'abstraction a 4LU de Behrmann et al. est la plus grande abstraction saine et complète pour les bornes LU. N' étant pas convexe, elle n'est pas mise en oeuvre dans les outils. Nous introduisons une méthode qui permet son utilisation éfficace. Finalement, nous proposons une optimisation des bornes à la volée exploitant le calcul de l'arbre.Le problème de vivacité requiert de détecter les exécutions Zenon/non-Zenon. Une solution standard ajoute une horloge à l'automate. Nous montrons qu'elle conduit a une explosion combinatoire. Nous proposons une solution qui évite ce problème pour une grande classe d'abstractions. Pour les abstractions LU nous montrons que détecter ces exécutions est un problèmeNP-complet. / We consider the classic model of timed automata introduced by Alurand Dill. Two fundamental properties one would like to check in this modelare reachability and liveness. This thesis revisits these classical problems.The reachability problem for timed automata asks if there exists a run ofthe automaton from the initial state to a given final state. The standard solutionto this problem constructs a search tree whose nodes are abstractionsof zones. For effectiveness, abstractions are parameterized by maximal lowerand upper bounds (LU-bounds) occurring in the guards of the automaton.Such abstractions are also termed as LU-abstractions. The a4LU abstractiondefined by Behrmann et al is the coarsest known LU-abstraction. Althoughit is potentially most productive to use the a4LU abstraction, it has not beenused in implementations as it could lead to non-convex sets. We show howone could use the a4LU abstraction efficiently in implementations. Moreover,we prove that a4LU abstraction is optimal: given only the LU-bound information,it is the coarsest possible abstraction that is sound and completefor reachability. We then concentrate on ways to get better LU-bounds. Inthe standard procedure the LU-bounds are obtained from a static analysisof the automaton. We propose a new method to obtain better LU-boundson-the-fly during exploration of the zone graph. The potential gains of proposedimprovements are validated by experimental results on some standardverification case studies.The liveness problem deals with infinite executions of timed automata.An infinite execution is said to be Zeno if it spans only a finite amountof time. Such runs are considered unrealistic. While considering infiniteexecutions, one has to eliminate Zeno runs or dually, find runs that arenon-Zeno. The B¨uchi non-emptiness problem for timed automata asks ifthere exists a non-Zeno run visiting an accepting state infinitely often. Thestandard solution to this problem adds an extra clock to take care of non-Zenoness. We show that this solution might lead to an exponential blowupin the search space. We propose a method avoiding this blowup for a wideclass of abstractions weaker than LU-abstractions. We show that such amethod does not exist for LU-abstractions unless P=NP. Another questionrelated to infinite executions of timed automata is to decide the existenceof Zeno runs. We provide the first complete solution to this problem. Itworks for a wide class of abstractions weaker than LU. Yet again, we showthe solution could lead to a blowup for LU-abstractions, unless P=NP.

Les protocoles cryptographiques jouent un rôle majeur dans les applications ou l'intégrité des données, la confidentialité, l'authenticité et autres propriétés sont essentielles. Ils sont utilisés par exemple dans le commerce électronique, la téléphonie mobile, le vote électronique. Dans la première partie de la thèse nous montrons que le problème d'atteignabilité pour des protocoles cryptographiques temporisés bornés est décidable est NP-complet. Notre procédure se base sur une logique de Hoare complète pour des protocoles cryptographiques bornés et un langage de propriétés très expressif. Dans la deuxième partie, en utilisant des techniques d'interprétation abstraite, nous appliquons cette méthode pour vérifier des propriétés de secret pour les protocoles cryptographiques dans un modèle général. Nous traitons un nombre non borné de sessions, de participants et de nonces ainsi que des messages de taille arbitraire. Nous proposons un algorithme qui calcule un invariant inductif en utilisant des patterns comme représentation symbolique. Cette méthode a été implanté dans l'outil Hermes et validée sur plusieurs études de cas.

Les langages formels sont des séquences sur un ensemble discret de symboles appelé alphabet. On les spécifie souvent par des formules dans une certaine logique, par des expressions rationnelles ou bien par des automates discrets de types variés. La théorie actuelle est principalement qualitative, dans le sens où ses objets sont des séquence sur un temps discret, non-métrique, dans le sens où l'acceptation d'une séquence sur un automate dépend du fait que l'on visite ou non un état accepteur, et enfin dans le sens où la comparaison de langages est plus souvent considérée en termes d'inclusion, plutôt qu'en termes de mesures quantitatives. Cette thèse contribue à l'étude de ces aspects souvent négligés en présentant des résultats fondamentaux dans trois nouvelles classes de problèmes quantitatifs sur les langages formels. Dans la première partie, nous étudions une classe de problèmes d'ordonnancement qui combine les aspects structurels associés aux dépendances entre tâches avec les aspects dynamiques liés au fait qu'un flux de requêtes arrive en continu pendant l'exécution. Nous montrons que, dans cette classe de problèmes, certains flux, pourtant admissibles dans le sens que les requêtes ne représentent pas plus de travail que ce que les machines peuvent traiter, ne peuvent pas être ordonnancé avec une latence bornée. Cependant nous développons une politique d'ordonnancement que peut garantir une accumulation de retard bornée pour tout flux de requêtes admissible, même sans le connaître à l'avance. Nous montrons que si les flux sont sous-critiques, alors cette même politique peut garantir une latence bornée. En vérification quantitative, les états et transitions d'un système peuvent être associés à des coûts, et ceux-ci utilisés pour associer des coûts moyens aux comportements infinis. Dans cette seconde partie, nous proposons de définir des omega-langages par des requêtes booléennes sur les coûts moyens. Des spécifications concernant des moyennes, tels que " le taux de perte moyen de messages est inférieur à un certain seuil " ne sont pas omega-régulières, mais exprimables dans notre modèle. Ainsi, nous étudions l'expressivité et la complexité de Borel de telles spécifications. Nous montrons que pour la clôture par intersection, il est nécessaire de considérer des coûts multi-dimensionnels. Nous mettons en évidence que dans le cas général, les conditions d'acceptation portent sur l'ensemble des points d'accumulation de la séquence des coûts moyens des préfixes d'une exécution, et nous donnons une caractérisation précise de tels ensembles. Nous proposons une classe de langages de coût moyen à seuils multiples, comparant les coordonnées minimales et minimales des points de cet ensemble à des constantes. Nous montrons enfin que cette classe est close par opérations booléennes et analysable. Enfin, dans le dernier volet, nous définissons deux mesures pour un langage temporisé : le volume de ses sous-langages de mots à nombre d'événements fixe et l'entropie (vitesse de croissance), mesure asymptotique pour un nombre non borné d'événements. Ces mesures peuvent être utilisées pour la comparaison quantitative de langages, et l'entropie peut être vue comme la quantité d'information par événement dans un mot typique du langage temporisé. Pour les langages acceptés par des automates temporisés déterministes, nous donnons une formule exacte pour le volume. Ensuite, nous caractérisons l'entropie, en utilisant des méthodes d'analyse fonctionnelle, en tant que logarithme du rayon spectral d'un opérateur intégral positif. Nous établissons plusieurs méthodes pour calculer l'entropie : une symbolique pour les automates que nos appelons " à une horloge et demie ", et deux numériques : une utilisant les techniques d'analyse fonctionnelle, l'autre basée sur la discrétisation. Nous donnons une interprétation de l'entropie en théorie de l'information en termes de complexité de Kolmogorov.

Nous considérons une sous classe d'automates temporisés probabilistes où les contraintes temporelles au niveau des gardes et des invariants sont exprimées par des paramètres. Cette sous classe est appelée la classe des automates Temporisés Probabilistes Paramétrés Semi Déterminés (ATPP Semi Déterminés). Cette classe d'automates se définit en particulier par l'attribution d'une unique distribution à chaque état et par des gardes de la forme x<=a où a est un paramètre ou un entier naturel. Nous imposons de plus deux propriétés sur ces automates qui sont celles de non blocage et fortement non zenon. Notre travail vise à calculer le temps moyen maximal de convergence vers un état dit absorbant q_end dans ce type d'automates. L'unique méthode traitant déjà ce type de problème fait appel à la discrétisation du temps et à l'application de techniques de programmation linéaire. Elle est cependant exponentielle car elle dépend du nombre d'horloges et de la plus grande constante à laquelle sont comparées les horloges, lors de la discrétisation. Le graphe résultant peut être de taille exponentielle. Pour tout ATPP Semi Déterminé, on définit un automate totalement déterministe, appelé ATPP Déterminé, en remplaçant toute garde de la forme x<=a par une garde de la forme x=a. Le temps d'attente en chaque état est ainsi fixé par la valuation de l'état initial qui remet toutes les horloges à zéro. Nous démontrons que le temps moyen de convergence vers q_end dans l'ATPP Déterminé est égal au temps moyen maximal de convergence dans l'ATPP Semi Déterminé dont il découle. Pour calculer le temps moyen de convergence vers q_end nous construisons à partir de l'ATPP Déterminé un graphe appelé "graphe des macro-steps" qui contient de façon concise l'information nécessaire au calcul du coût moyen de convergence vers q_end. Ce graphe est de taille polynomiale et se construit en temps polynomial. Le calcul du temps moyen de convergence dans le graphe des macro-steps est solution d'un système linéaire, comme dans le cas des chaînes de Markov avec coûts. On résout ce système linéaire en temps polynomial, ce qui permet d'obtenir finalement le temps moyen maximal de convergence vers q_end dans l'ATPP Semi Déterminé. Nous appliquons enfin cette méthode à certains protocoles de communication, notamment BRP (Bounded Retransmission Protocol) et CSMA/CD (Carrier Sense Multiple Access with Collision Detection).

L'avantage majeur qu'offrent les services Web est le fait qu'ils reposent sur des standards et les technologies du Web pour interagir en s'échangeant des messages. A part les séquences de messages, d'autres facteurs affectent l'interopérabilité des services Web, telles que les contraintes temporelles qui spécifient les délais nécessaires pour échanger des messages. La thèse rapportée dans ce manuscrit étudie l'impact de ces propriétés dans la composition de services Web. La considération de telles propriétés soulève plusieurs problèmes auxquels on a essayé d'apporter une solution. Le premier aspect consiste à définir un modèle qui tienne compte des abstractions nécessaires afin de pouvoir analyser et synthétiser une composition, à savoir les messages, les données, les contraintes de données, les propriétés temporelles et l'aspect asynchrone des communications des services. En se basant sur ce modèle, le deuxième problème consiste à proposer une approche d'analyse de compatibilité. Cette analyse vise à caractériser la compatibilité ou la non-compatibilité des services Web et ce en prenant en considération les abstractions précédemment citées. Nous étudions particulièrement l'impact des propriétés temporelles dans une chorégraphie dans laquelle les services Web supportent des communications asynchrones. Nous proposons une démarche basée sur le model checking qui permet de détecter les éventuels conflits temporisés qui peuvent surgir dans une chorégraphie. Finalement, le dernier problème auquel nous nous intéressons est celui de la construction d'une composition qui essaie de répondre au besoin du client et ce en prenant en compte les aspects temporels. L'approche que l'on propose est basée sur la génération d'un médiateur pour essayer, quand c'est possible, de contourner les incompatibilités temporisées et non-temporisées qui peuvent surgir lors d'une collaboration. Des mécanismes et des algorithmes ont été développés afin de mettre en oeuvre ces objectifs.

Cette thèse se situe dans le contexte des réseaux de communication temps-réel et son objectif est de proposer une architecture de communication pour la sous-couche MAC, qui définit des mécanismes pour assurer les contraintes temporelles du trafic temps-réel. Tout d'abord, une classification des protocoles MAC temps-réel existants, en mettant en exergue l'aspect ordonnancement de flux de messages ou ordonnancement de stations, est effectuée. En particulier, le protocole "jeton temporisé" et des mécanismes de la norme "ISA SP-50 / IEC-65C" sont détaillés. Ensuite, des contributions sur les mécanismes d'ordonnancement et les mécanismes protocolaires sont développées, à la fois en termes conceptuels et en termes de réflexions sur les normes existantes: proposition d'un algorithme non-préemptif ED avec, en particulier, une extension des conditions classiques d'ordonnançabilité; définition d'un algorithme de changement de mode de fonctionnement pour un système ordonnancé par l'algorithme RM; définition d'un protocole appelé "jeton temporisé régulier" qui améliore les performances temps-réel du protocole "jeton temporisé"; définition des conditions d'ordonnançabilité du trafic apériodique urgent dans le réseau FIP et proposition de deux profils de fonctionnement temps-réel pour le réseau Profibus. Enfin, nous proposons, modélisons avec le modèle "Réseaux de Petri Temporisés Stochastiques" et évaluons une architecture de communication pour la sous-couche MAC de réseaux locaux temps-réel. Cette architecture met en ¿uvre, de manière centralisée, un ordonnancement conjoint des trafics périodique et apériodique temps-réel, sur la base d'un algorithme non-préemptif pour le trafic périodique et d'une technique de jeton temporisé pour le trafic apériodique temps-réel. L'analyse permet, d'une part, d'évaluer l'ordonnancement en termes de taux d'utilisation permis et des limites de l'ordonnançabilité et, d'autre part, de montrer tout l'intérêt des modèles "Réseaux de Petri Temporisés Stochastiques" pour représenter et évaluer automatiquement l'ordonnançabilité d'un ensemble de configurations de flux de messages.

Ce travail propose une méthode pour l'analyse de systèmes temps-reél. <br />Cette méthode est basée sur la compilation des spécifications<br />vers des graphes temporisés, à partir desquels il est possible<br />de vérifier des propriétés et de générer du code exécutable.<br /><br />Les graphes temporisés sont des automates étendus avec des<br />variables, appelées horloges, qui permettent de décrire les<br />contraintes temporelles. <br /><br />Un algorithme de compilation est développé pour l'algèbre<br />de processus temporisés ATP, qui est une extension des <br />algèbres de processus avec des opérateurs temporels comme <br />le ``timeout'' et le ``watchdog''. L'intérêt de l'algorithme est <br />que la taille du graphe obtenu est indépendante des valeurs <br />des paramètres des opérateurs temporels.<br /><br />Les propriétés temps-reél sur les graphes temporisés sont <br />décrites par des formules de la logique TCTL. <br />Il est montré que les opérateurs temporels<br />de TCTL s'expriment en termes de points fixes à l'aide d'un <br />opérateur ``d'état suivant'' défini de façon appropriée.<br />De plus, ce travail propose un algorithme de vérification qui<br />consiste à évaluer symboliquement l'ensemble caractéristique<br />d'une formule comme une disjonction de contraintes linéaires<br />sur les horloges.<br /><br />Les algorithmes de compilation et de vérification développés <br />ont été implémentés dans l'outil KRONOS, <br />utilisé pour analyser des applications temps-reél <br />significatives. Les résultats obtenus confirment l'intérêt<br />pratique de l'approche proposée.