The proper composition of independently developed components of an embedded real- time system is complicated due to the fact that besides the functional behavior also the non-functional properties and in particular the timing have to be compatible. Nowadays related compatibility problems have to be addressed in a cumbersome integration and configuration phase at the end of the development process, that in the worst case may fail. Therefore, a number of formal approaches have been developed, which try to guide the upfront decomposition of the embedded real-time system into components such that integration problems related to timing properties can be excluded and that suitable configurations can be found. However, the proposed solutions require a number of strong assumptions that can be hardly fulfilled or the required analysis does not scale well. In this paper, we present an approach based on timed automata that can provide the required guarantees for the later integration without strong assumptions, which are difficult to match in practice. The approach provides a modular reasoning scheme that permits to establish the required guarantees for the integration employing only local checks, which therefore also scales. It is also possible to determine potential configuration settings by means of timed game synthesis. / Die korrekte Komposition individuell entwickelter Komponenten von eingebetteten Realzeitsystemen ist eine Herausforderung, da neben funktionalen Eigenschaften auch nicht funktionale Eigenschaften berücksichtigt werden müssen. Ein Beispiel hierfür ist die Kompatibilität von Realzeiteigenschaften, welche eine entscheidende Rolle in eingebetteten Systemen spielen. Heutzutage wird die Kompatibilität derartiger Eigenschaften in einer aufwändigen Integrations- und Konfigurationstests am Ende des Entwicklungsprozesses geprüft, wobei diese Tests im schlechtesten Fall fehlschlagen. Aus diesem Grund wurde eine Zahl an formalen Verfahren Entwickelt, welche eine frühzeitige Analyse von Realzeiteigenschaften von Komponenten erlauben, sodass Inkompatibilitäten von Realzeiteigenschaften in späteren Phasen ausgeschlossen werden können. Existierenden Verfahren verlangen jedoch, dass eine Reihe von Bedingungen erfüllt sein muss, welche von realen Systemen nur schwer zu erfüllen sind, oder aber, die verwendeten Analyseverfahren skalieren nicht für größere Systeme. In dieser Arbeit wird ein Ansatz vorgestellt, welcher auf dem formalen Modell des Timed Automaton basiert und der keine Bedingungen verlangt, die von einem realen System nur schwer erfüllt werden können. Der in dieser Arbeit vorgestellte Ansatz enthält ein Framework, welches eine modulare Analyse erlaubt, bei der ausschließlich miteinender kommunizierende Komponenten paarweise überprüft werden müssen. Somit wird eine skalierbare Analyse von Realzeiteigenschaften ermöglicht, die keine Bedingungen verlangt, welche nur bedingt von realen Systemen erfüllt werden können.

<p align="justify">Computer Science is currently facing a grand challenge : finding good design practices for embedded systems. Embedded systems are essentially computers interacting with some physical process. You could find one in a braking systems or in a nuclear power plant for example. They present several design difficulties : first they are reactive systems, interacting indefinitely with their environment. Second,they must satisfy real-time constraints specifying when they should respond, and not only how. Finally, their environment is often deeply continuous, presenting complex dynamics. The formal models of choice for specifying such systems are timed and hybrid automata for which model checking is pretty well studied.</p> <p align="justify">In a first part of this thesis, we study a complete design approach, including verification and code generation, for timed automata. We have to define a new semantics for timed automata, the AASAP semantics, that preserves the decidability properties for model checking and at the same time is implementable. Our notion of implementability is completely novel, and relies on the simulation of a semantics that is obviously implementable on a real platform. We wrote tools for the analysis and code generation and exemplify them on a case study about the well known Philips Audio Control Protocol.</p> <p align="justify">In a second part of this thesis, we study the problem of controller synthesis for an environment specified as a hybrid automaton. We give a new solution for discrete controllers having only an imperfect information about the state of the system. In the process, we defined a new algorithm, based on the monotonicity of the controllable predecessors operator, for efficiently finding a controller and we show some promising applications on a classical problem : the universality test for finite automata.

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.

Web services are increasingly gaining acceptance as a framework for facilitating application-to-application interactions within and across enterprises. It is commonly accepted that a service description should include not only the interface, but also the business protocol supported by the service. The present work focuses on the formalization of the important category of protocols that include time-related constraints (called timed protocols), and the impact of time on compatibility and replaceability analysis. We formalized the following timing constraints: CInvoke constraints define time windows of availability while MInvoke constraints define expirations deadlines. We extended techniques for compatibility and replaceability analysis between timed protocols by using a semantic-preserving mapping between timed protocols and timed automata, leading to the novel class of protocol timed automata (PTA). Specifically, PTA exhibit silent transitions that cannot be removed in general, yet they are closed under complementation, making every type of compatibility or replaceability analysis decidable. Finally, we implemented our approach in the context of a larger project called ServiceMosaic, a model-driven framework for web service life-cycle management.

Le développement croissant de systèmes embarqués de consommation, où les composants numériques, analogiques et logiciels sont combinés sur une même puce, résulte en une augmentation de la complexité des processus de conception et de vérification. La validation de tels systèmes analogiques et à signaux-mixtes reste largement basée sur des techniques de simulation, qui sont souvent combinées avec des méthodes d'analyse de nature ad-hoc. Cette thèse est motivée par l'exportation de méthodes formelles basées sur des propriétés, vers leur application à la validation de systèmes analogiques et à signaux mixtes, considérés à leur niveaux d'abstraction continu et temporisé.<br />Etant-donné que la vérification formelle de systèmes continus non-triviaux reste très difficile, nous nous tournons vers une méthode de validation plus légère appelée le monitoring basé sur des propriétés. Nous définissons signal temporal logic STL comme langage de spécification de haut niveau qui permet d'exprimer des propriétés temporelles de signaux continus et temporisés. STL est une extension de la logique de temps-réel metric interval temporal logic MITL, où les signaux continus sont transformés en signaux Booléens avec des prédicats numériques, et les relations temporelles entre ces signaux son exprimées avec les opérateurs temporels habituels dont les propositions atomiques correspondent à ces prédicats. Nous développons deux procédures de monitoring, une offline et une incrémantale, qui permettent de vérifier si les traces de simulations sont correctes par rapport aux propriétés STL. Les deux procédures sont implantées en outil de monitoring analogique AMT. Notre approche de monitoring basé sur des propriétés est appliquée, en utilisant AMT, à deux études de cas réalistes, où nous étudions des propriétés d'une mémoire de type FLASH et d'une interface de mémoire DDR2. <br />Nous considérons aussi le problème de vérification formelle de systèmes temporisés, et développons une traduction modulaire des formules MITL avec les opérateurs futurs et passés, vers des automates temporisés. La construction que nous proposons est basée sur les testeurs temporels, une classe spécifique d'automates avec les entrées et les sorties qui réalisent la fonction séquentielle définie par la sémantique des opérateurs MITL. Nous montrons d'abord comment chaque formule MITL peut être exprimée avec six opérateurs basiques (trois opérateurs passés et trois futurs) et nous proposons une construction de testeurs temporels à partir de ces opérateurs. Les testeurs temporels pour des formules MITL arbitraires sont obtenus en composant ces testeurs élémentaires.<br />Finalement, nous développons une procédure pour la synthèse automatique de contrôleurs à partir des spécifications de haut niveau exprimées avec le fragment borné de metric temporal logic (MTL). Nous proposons une traduction des propriétés spécifiées dans cette logique temporisée vers des automates temporisés déterministes, en supposant la variabilité bornée. Ensuite, nous pouvons appliquer à ces automates les algorithmes habituels de synthèse de sûreté pour construire un contrôleur qui satisfait la spécification par construction.

<p>Embedded systems are used in many technical products of today. The tendency also points to the fact that they are in many ways becoming more and more complex as technology advances. Systems like advanced avionics, air bags, ABS brakes or any real-time embedded system requires reliability, correctness and timeliness. This puts hard pressure on designers, analyzers and developers. The need for high performance and non failing systems has therefore led to a growing interest in modeling and verification of component-based embedded systems in order to reduce costs and simplify design and development. The solution proposed by the Embedded Systems Lab at Linköping University is the modeling language PRES+, Petri Net based Representation for Embedded Systems.</p><p>PRES+ models are then translated into timed automata, TA, which is used by the UPPAAL verification tool. To be able to verify timing properties the translated TA model must be instrumented with certain timers, called clocks. These clocks must be reset in a manner reflected by the property to be verified.</p><p>This thesis will provide a solution to the problem and also give the reader necessary information in order to understand the theoretical background needed. The thesis will also show the reader the importance of modeling and time verification in the development of embedded systems. A simple example is used to describe and visualize the benefit regarding real-time embedded systems as well as the importance of the ability to verify these systems.</p><p>The conclusion drawn stresses the fact that high development costs, possible gain of human lives and the problems in developing complex systems only emphasize the need for easy to handle and intuitive verification methods.</p>

<p>Real-time systems are required to answer to external stimuli within a specified time-period. For this to be possible, the systems behaviour must be predictable. The use of active databases in real-time systems introduces unpredictability in the system, e.g. due to their use of active rules. The behaviour in active databases is usually specified in ECA-rules. Sets of ECA-rules are hard to analyse, which implies that the behaviour of the ECA-rule set is hard to predict.</p><p>The purpose of this project is to evaluate the ability to support the development of a predictable ECA-rule set. Using a formal method for the specification task is desirable, since a formal specification is analysable and can be proven correct. In this project, timed-automata are used for specifying the systems behaviour. A method for deriving predictable ECA-rules from a timed-automaton specification is developed, and successfully applied on a case-study specification. For this case-study specification, a set of ECA-rules preserving the analysed behaviour of the timed-automata specification is derived.</p>

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.

In modern times, human life is intrinsically depending on real-time embedded systems (RTES) with increasingly safety-critical and mission-critical features, for instance, in domains such as automotive and avionics. These systems are characterized by stringent functional requirements and require predictable timing behavior. However, the complexity of RTES has been ever increasing requiring systematic development methods. To address these concerns, model-based frameworks and component-based design methodologies have emerged as a feasible solution. Further, system artifacts such as requirements/specifications, architectural designs as well as behavioral models like statemachine views are integrated within the development process. However, several challenges remain to be addressed, out of which two are especially important: expressiveness, to represent the real-time and causality behavior, and analyzability, to support verification of functional and timing behavior. As the main research contribution, this thesis presents design and verification techniques for model-based development of RTES, addressing expressiveness and analyzability for architectural and behavioral models. To begin with, we have proposed a systematic design process to support component-based development. Next, we have provided a real-time semantic basis, in order to support expressiveness and verification for structural and behavioral models. This is achieved by defining an intuitive formal semantics for real-time component models, using ProCom, a component model developed at our research centre, and also using the CCSL (Clock Constraint Specification Language), an expressive language for specification of timed causality behavior. This paves the way for formal verification of both architectural and behavioral models, using model checking, as we show in this work, by transforming the models into timed automata and performing verification using UPPAAL, a model checking tool based on timed automata. Finally, the research contributions are validated using representative examples of RTES as well as an industrial case-study. / ARROWS

In 1994, Alur and Dill introduced timed automata as a simple mathematical model for modelling the behaviour of real-time systems. In this thesis, we extend timed automata with weights. More detailed, we equip both the states and transitions of a timed automaton with weights taken from an appropriate mathematical structure. The weight of a transition determines the weight for taking this transition, and the weight of a state determines the weight for letting time elapse in this state. Since the weight for staying in a state depends on time, this model, called weighted timed automata, has many interesting applications, for instance, in operations research and scheduling. We give characterizations for the behaviours of weighted timed automata in terms of rational expressions and logical formulas. These formalisms are useful for the specification of real-time systems with continuous resource consumption. We further investigate the relation between the behaviours of weighted timed automata and timed automata. Finally, we present important decidability results for weighted timed automata.