Cette thèse étudie l’enforcement de propriétés temporisées à l’exécution en présence d’évènements incontrôlables. Les travaux se placent dans le cadre plus général de la vérification à l’exécution qui vise à surveiller l’exécution d’un système afin de s’assurer qu’elle respecte certaines propriétés. Ces propriétés peuvent être spécifiées à l’aide de formules logiques, ou au moyen d’autres modèles formels, parfois équivalents, comme des automates. Nous nous intéressons à l’enforcement à l’exécution de propriétés spécifiées par des automates temporisés. Tout comme la vérification à l’exécution, l’enforcement à l’exécution surveille l’exécution d’un système, la différence étant qu’un mécanisme d’enforcement réalise certaines modifications sur l’exécution afin de la contraindre à satisfaire la propriété souhaitée. Nous étudions plus particulièrement l’enforcement à l’exécution lorsque certains évènements de l’exécution sont incontrôlables, c’est-à-dire qu’ils ne peuvent pas être modifiés par un mécanisme d’enforcement. Nous définissons des algorithmes de synthèse de mécanismes d’enforcement décrits de manières fonctionnelle puis opérationnelle, à partir de propriétés temporisées régulières (pouvant être représentées par des automates temporisés). Ainsi, deux mécanismes d’enforcement équivalents sont définis, le premier présentant une approche correcte sans considération d’implémentation, alors que le second utilise une approche basée sur la théorie des jeux permettant de précalculer certains comportements, ce qui permet de meilleures performances. Une implémentation utilisant ce précalcul est également présentée et évaluée. Les résultats sont encourageant quant à la faisabilité de l’enforcement à l’exécution en temps réel, avec des temps supplémentaires suffisamment courts sur de petites propriétés pour permettre une utilisation de tels systèmes. / This thesis studies the runtime enforcement of timed properties when some events are uncontrollable. This work falls in the domain of runtime verification, which includes all the techniques and tools based on or related to the monitoring of system executions with respect to requirement properties. These properties can be specified using different models such as logic formulae or automata. We consider timed regular properties, that can be represented by timed automata. As for runtime verification, a runtime enforcement mechanism watches the executions of a system, but instead of just outputting a verdict, it modifies the execution so that it satisfies the property. We are interested in runtime enforcement with uncontrollable events. An uncontrollable event is an event that an enforcement mechanism can not modify. We describe the synthesis of enforcement mechanisms, in both a functional and an operational way, that enforce some desired timed regular property. We define two equivalent enforcement mechanisms, the first one being simple, without considering complexity aspects, whereas the second one has a better time complexity thanks to the use of game theory; the latter being better suited for implementation. We also detail a tool that implements the second enforcement mechanism, as well as some performance considerations. The overhead introduced by the use of our tool seems low enough to be used in some real-time application scenarios.

Many automotive systems are real-time systems, which means that not only correct operationsbut also appropriate timings are their main requirements. Considering the in uence that end-to-end delay might have on the performance of the systems, the calculation of it is of necessity.Abundant techniques have actually been proposed, and some of them have already been applied intopractical systems. In spite of this, some further work still needs to be done. The target of thisthesis is to evaluate and compare two end-to-end timing analysis methods from dierent aspectssuch as data age, consumption time, and then decide which method is a prior choice for end-to-end timing analysis. The experiments can be divided into three blocks, system generation andend-to-end delay calculation by two methods respectively. The experiments focus on two kinds ofperformance parameters, data age and the consumption time that these two methods cost duringtheir execution. By changing the system generating parameters like task number and periods, thechanges of performances of the two methods are analyzed. The performances of the two dierentmethods are also compared when they are applied into the same automotive systems. According tothe results of the experiments, the second method can calculate more accurate data age and consumeless time than the rst method does.

Cette thèse revisite les algorithmes standards pour les problèmes d'accessibilité et de vivacité des automates temporisés. L'algorithme standard pour tester l'accessibilité consiste à utiliser l'inclusion de zones pour explorer efficacement un arbre de recherche abstrait. Cependant, l'ordre du parcours du graphe a une forte incidence sur l'efficacité de l'algorithme. Dans cette thèse nous introduisons deux stratégies, nommées ranking et waiting, et une combinaison des deux. De nombreux exemples montrent que la combinaison des deux stratégies aide l'algorithme d'accessibilité à éviter des explorations non nécessaires. Le problème de vivacité est couramment vérifiées par l'analyse des cycles dans l'automate temporisé. Contrairement à l'algorithme d'accessibilité, l'algorithme pour l'analyse de vivacité ne peut pas librement utiliser l'inclusion de zones. Par conséquent, il y a des situations où l'algorithme doit faire une longue exploration avant de conclure l'existence d'un cycle. Nous proposons une analyse accélérée des cycles, nommées w-iterability checking, qui permet d'améliorer la performance de l'algorithme de vivacité des automates temporisés. En plus, nous proposons une modélisation du mécanisme de démarrage du protocole FlexRay. La modélisation permet à vérifier le mécanisme dans configurations différents du réseau FlexRay. Nous présentons également un outil de visualisation qui aide à mieux comprendre le fonctionnement des algorithmes d'analyse. / This thesis revisits the standard algorithms for reachability and liveness analysis of timed automata. The standard algorithm for reachability analysis consists in using zone inclusion to efficiently explore a finite abstract zone graph of a timed automaton. It has been observed that the search order may strongly affect the performance of the algorithm. For the same algorithm, one search order may introduce a lot more exploration than another. In order to deal with the search order problem, we propose two strategies, named ranking strategy and waiting strategy, and a combination of the two. We show on a number of examples, the combining strategy helps to reduce unnecessary exploration in the standard algorithms. The standard algorithm for liveness analysis consists in looking for reachability of cycles in timed automata. But unlike the algorithm for safety analysis, the algorithm for liveness analysis cannot freely use zone inclusion. Consequently, there are situations where the algorithm has to perform a long exploration before reporting the result. In this thesis, we propose an accelerated checking for cycles in timed automata, named !-iterability checking, to improve the performance of the state-of-the-art algorithm for liveness analysis of timed automata. Furthermore, we present a new model for the startup procedure of FlexRay. The model allows to verify the procedure on different configurations of FlexRay networks. It also allows to evaluate the performance of our new strategies for safety analysis of timed automata. In addition, we present a methodology that uses visualization tools to get more insights into the execution of the algorithms.

This thesis discusses autonomous vehicles. At first it contains describing development of these type of vehicles, how they work and discuss their future development. Further it describe tools which can be used for create model of autonomous vehicle. The thesis includes design, description of the development and testing of the model in the UPPAAL Stratego verification environment. The resulting model is a system of intercommunicating timed automata. The analysis of the model properties is based on the method of statistical verification. The model allows us to investigate behavior of an autonomous vehicle in situations which correspond to regular traffic.

This thesis is focused on distributed systems modeling using Petri nets. Distributed systems are increasingly being implemented in applications and computing systems, where their task is to ensure sufficient performance and stability for a large number of its users. When modeling a distributed systems, stochastic behavior of Petri nets is important, which will provide more realistic simulations. Therefore, this thesis focuses mainly on timed Petri nets. The theoretical part of this thesis summarizes distributed systems, their properties, types and available architectures, as well as Petri nets, their representation, types and the principle of an operation. In the practical part, two models were implemented, namely a horizontally scaled web application divided into several services with a distributed database and a large grid computing system, more precisely the BOINC platform with the Folding@home project. Both models were implemented using the PetNetSim library of Python. The goal of this thesis is to perform simulations on the created models for different scenarios of their behavior.

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.

Society relies on increasingly complex software and hardware systems, hence techniques capable of proving that they behave as expected are of great and growing interest. Formal verification procedures employ mathematically sound reasoning to address this need. This thesis proposes novel techniques for the verification and falsification of expressive specifications on timed and infinite-state systems. An expressive specification language allows the description of the intended behaviour of a system via compact formal statements written at an abstraction level that eases the review process. Falsifying a specification corresponds to identifying an execution of the system that violates the property (i.e. a witness). The capability of identifying witnesses is a key feature in the iterative refinement of the design of a system, since it provides a description of how a certain error can occur. The designer can analyse the witness and take correcting actions by refining either the description of the system or its specification. The contribution of this thesis is twofold. First, we propose a semantics for Metric Temporal Logic that considers four different models of time (discrete, dense, super-discrete and super-dense). We reduce its verification problem to finding an infinite fair execution (witness) for an infinite-state system with discrete time. Second, we define a novel SMT-based algorithm to identify such witnesses. The algorithm employs a general representation of such executions that is both informative to the designer and provides sufficient structure to automate the search of a witness. We apply the proposed techniques to benchmarks taken from software, infinite-state, timed and hybrid systems. The experimental results highlight that the proposed approaches compete and often outperform specific (application tailored) techniques currently used in the state of the art.

Cyber-physical systems (CPSs) are used in several industries, such as healthcare, automotive, manufacturing, and more. The fact that CPSs often contain components integrated via communication networks means that malicious actors can exploit vulnerabilities in these components through cyber attacks. CRYSTAL Framework has been shown in previous research to be able to detect cyber attacks on CPSs. However, this has only been proven in simulation. Our research builds upon these previous research as we aim to prove that CRYSTAL Framework is a viable method for monitoring real systems to detect abnormal behaviours.  The Tiny Twin is an abstract behavioral model that defines normal running behaviour of a system, which can then be used by to compare the current state of a monitored system to detect possible attacks and abnormal behaviours. We built a monitor that integrates such a Tiny Twin, working by passively listening on input and output of components in a monitored system. We designed and implemented two different scenarios, a security alarm system and a temperature control system (TCS), to test the CRYSTAL Framework. In testing both implemented scenarios our monitor successfully detected all but one attacks during runtime by comparing the system's current state with the expected state as defined in the Tiny Twin.

No description available.

Personal characteristics of speech rhythm in Russian newsreading Bc. Irena Čížková Abstract An issue of individual rhythmic characteristics of particular 5 native speakers of the Russian language, newsreaders from the BBC, is described in this thesis. A research of the given 5 speech recordings was conducted based on the academic concepts created by Ramus, Mehler and Nespor, and by Low and Grabe and also by Dellwo, so through a speech rhythm research based on rhythm correlates that are related to vocalic and intervocalic intervals. The recordings were processed in an analyting program called Praat and the extracted results were then evaluated in a statistical processor called STATISTICA. These materials were used for further analysis. The recordings were analysed based on several parameters: %V (proportion of vocalic intervals in one breath group), ∆C and ∆V (standard deviation of the vocalic and consonantal interval duration), PVI-V, PVI-C (Pairwise Variability Index of the vocalic and consonantal interval duration), Varco V and Varco C (variation coefficient of the vocalic and consonantal interval duration) and the difference between duration of stressed and unstressed vowels. Three parameters that were the most successful from the speakers' ability to differentiate point of view were selected through an...