No description available.

No description available.

<p> Many safety-critical software applications are hard real-time systems. They have stringent timing requirements that have to be met. We present descriptions of timing behaviors that include precise definitions as well as analysis of how functional timing requirements (FTRs) interact with performance timing requirements (PTRs), and how these concepts can be used by software designers. The definitions explicitly show how to specify timing requirements with tolerances on time durations. </p> <p> This thesis shows the importance of specifying both FTRs and PTRs, by revealing the fact that their interaction directly determines the final implementability of real-time systems. By studying this interaction under three environmental assumptions, we find that the implementability results of the timing properties are different in each environment, but they are closely related. The results allow us to predict the system's implementability without developing or verifying the actual implementation. This also shows that we can sometimes significantly reduce the sampling frequency on the target platform, and still implement the timing requirement correctly. </p> <p> We present a component-based approach to formalizing common timing requirements and provide a pre-verified implementation of one of these requirements. The verification is performed using the theorem proving tool PVS. This allows domain experts to specify the tolerance in each individual timing requirement precisely. The pre-verified implementation of a timing requirement is demonstrated by applying the method in two examples. These examples show that both the design and verification effort are reduced significantly using a pre-verified template. </p> <p> A primary focus of this thesis is on how to include tolerances on timing durations in the specification, implementation and verification of timing behaviors in hard real-time applications. </p> / Thesis / Doctor of Philosophy (PhD)

While increasing number of vehicles on urban roadways create uncontrolled congestion, connectivity among vehicles, traffic lights and other road-side units provide abundant data that paves avenues for novel smart traffic control mechanisms to mitigate traffic congestion and delays. However, increasingly complex vehicular applications have outpaced the computational capabilities of on-board processing units, therefore requiring novel offloading schemes onto additional resources located by the road-side. Adding connectivity and other computational resources on legacy traffic infrastructure may also introduce security vulnerabilities. To ensure that the timeliness and resource constraints of the vehicles using the roadways as well as the applications being deployed on the traffic infrastructure are met, the transportation systems needs to be more predictable. This dissertation discusses three areas that focus on improving the predictability and performance of the connected traffic infrastructure. Firstly, a holistic traffic control strategy is presented that ensures predictable traffic flow by minimizing traffic delays, accounting for unexpected traffic conditions and ensuring timely emergency vehicle traversal through an urban road network. Secondly, a vehicular edge resource management strategy is discussed that incorporates connected traffic lights data to meet timeliness requirements of the vehicular applications. Finally, security vulnerabilities in existing traffic controllers are studied and countermeasures are provided to ensure predictable traffic flow while thwarting attacks on the traffic infrastructure. / Doctor of Philosophy / Exponentially increasing vehicles especially in urban areas create pollution, delays and uncontrolled traffic congestion. However, improved traffic infrastructure brings connectivity among the vehicles, traffic lights, road-side detectors and other equipment, which can be leveraged to design new and advanced traffic control techniques. The initial work in this dissertation provides a traffic control technique that (i) reduces traffic wait times for the vehicles in urban areas, (ii) ensures safe and quick movements of emergency vehicles even through crowded areas, and (iii) ensures that the traffic keeps moving even under unexpected lane closures or roadblocks. As technology advances, connected vehicles are becoming increasingly automated. This allows the car manufacturers to design novel in-vehicle features where the passengers can now stream media-rich content, play augmented reality (AR)-based games and/or get high definition information about the surroundings on their car's display, while the car is driven through the urban traffic. This is made possible by providing additional computing resources along the road-side that the vehicles can utilize wirelessly to ensure passenger's comfort and improved experience of in-vehicle features. In this dissertation, a technique is provided to manage the computational resources which will allow vehicles (and its passengers) to use multiple features simultaneously. As the traffic infrastructure becomes increasingly inter-connected, it also allows malicious actors to exploit vulnerabilities such as modifying traffic lights, interfering with road-side sensors, etc. This can lead to increased traffic wait times and eventually bring down the traffic network. In the final work, one such vulnerability in traffic infrastructure is studied and mitigating measures are provided so that the traffic keeps moving even when an attack is detected. In all, this dissertation aims to improve safety, security and overall experience of the drivers, passengers and the pedestrians using the connected traffic infrastructure.

Real-time computing systems are those that are designed to achieve computing goals by certain deadlines. Real-time computing systems are present in everything from cars to airplanes, pacemakers to industrial-control systems, and other pieces of critical infrastructure. With the increasing interconnectivity of these systems, system security issues and the constant threat of manipulation by malicious external attackers that have plagued general computing systems, now threaten the integrity and safety of real-time systems. This dissertation discusses three different defense techniques that focuses on the role that real-time scheduling theory can play to reduce runtime cost, and guarantee correctness when applying these defense strategies to real-time systems. The first work introduces a novel timing aware defense strategy for the CAN bus that utilizes TrustZone on state-of-the-art ARMv8-M microcontrollers. The second reduces the runtime cost of control-flow integrity (CFI), a popular system security defense technique, by correctly modeling when a real-time system performs I/O, and exploiting the model to schedule CFI procedures efficiently. Finally, the third studies and provides a lightweight mitigation strategy for a recently discovered vulnerability within mixed criticality real-time systems. / Doctor of Philosophy / Real-time computing systems are those that are designed to achieve computing goals within certain timing constraints. Real-time computing systems are present in everything from cars to airplanes, pacemakers to industrial-control systems, and other pieces of critical infrastructure. With the increasing interconnectivity of these systems, system security issues and the constant threat of manipulation by malicious external attackers that have plagued general computing systems, now threaten the integrity and safety of real-time systems. This dissertation discusses three different defense techniques that focuses on the role that real-time scheduling theory can play to reduce runtime cost, and guarantee correctness when applying these defense strategies to real-time systems. The first work introduces a novel timing aware defense strategy for the Controller Area Network (CAN). CAN is a popular communication system that is at the heart of every modern passenger vehicle and is indispensable for the safe operation of various components such as the engine and transmission systems, and due to its simplicity, may be vulnerable to a variety of attacks. We leverage security advancements in modern processor design to provide a lightweight and predictable (in terms of time taken to perform the operation) defense technique for some of these vulnerabilities. The second work applies a technique called Control-Flow Integrity (CFI) to real-time systems. CFI is a general-purpose defense technique to prevent attackers from modifying software execution, and applying such techniques to real-time systems, particularly those with limited hardware capabilities, may be infeasible. By applying real-time scheduling theory, we propose a strategy to apply CFI to such systems, while reducing its overhead, or cost, without compromising the security guarantees CFI inherently provides. Finally, safety-critical systems may consist of a mix of operations, each having a different level of importance (criticality) with respect to the safe operation of the system. However, due to the complexity of modeling such systems, the models themselves may be vulnerable to attacks. Through simulations we study one such vulnerability and propose a modification to mitigate it.

Utility Accrual (UA) scheduling is a method of dynamic real-time scheduling that is designed to respond to overload conditions by producing a feasible schedule that heuristically maximizes a pre-defined metric of utility. Whereas utility accrual schedulers have traditionally focused on CPU overload, this dissertation explores memory overload conditions during which the aggregate memory demand exceeds a system's available memory bandwidth. Real-time systems are typically implemented in C or other languages that use explicit dynamic memory management. Taking advantage of modern type-safe languages, such as Java, necessitates the use of garbage collection (GC). The timeliness requirements of real-time systems, however, impose specific demands on the garbage collector. Garbage collection introduces a significant source of unpredictability in the execution timeline of a task because it unexpectedly interjects pauses of arbitrary length, at arbitrary points in time, with an arbitrary frequency. To construct a feasible schedule, a real-time scheduler must have the ability to predict the collector's activities and plan for them accordingly. We have devised CADUS (Collector-Aware Dynamic Utility Scheduler), a utility accrual algorithm that tightly links CPU scheduling with the memory requirements -and the corresponding garbage collection activities - of real-time tasks. By constructing and storing memory time allocation profiles, we address the problem of GC activation strategy. We estimate GC latency by using a real-time collector and modeling its behavior. We project GC frequency by planning, at schedule construction time, the memory bandwidth available to the collector. CADUS can point the collector's activities to any specific task in the system. The runtime system provides this ability by maintaining separate logical heaps for all tasks. We demonstrate the viability of CADUS through extensive simulation studies. We evaluated the behavior of CADUS under a wide range of CPU and memory load conditions and utility distributions. We compared its performance against an existing GC-unaware UA scheduler and found that CADUS consistently outperformed its GC-unaware counterpart. We investigated and identified the reasons for the superior performance of CADUS and quantified our results. Most significantly, we found that in an overloaded dynamic soft real-time system, a scheduler's preemption decisions have a highly significant impact on GC latency. A dynamic real-time scheduler therefore must predict the impact of its preemption decisions on GC latency in order to construct time-feasible schedules. / Ph. D.

Dynamic real-time distributed systems are characterized by significant run-time uncertainties at the mission and system levels. Typically, processing and communication latencies in such systems do not have known upper bounds and event and task arrivals and failure occurrences are non-deterministically distributed. This thesis proposes adaptive resource management heuristic techniques for periodic tasks in dynamic real-time distributed systems with the (soft real-time) objective of minimizing missed deadline ratios. The proposed resource management techniques continuously monitor the application tasks at run-time for adherence to the desired real-time requirements, detects timing failures or trends for impending failures (due to workload fluctuations), and dynamically allocate resources by replicating subtasks of application tasks for load sharing. We present "predictive" resource allocation algorithms that determine the number of subtask replicas that are required for adapting the application to a given workload situation using statistical regression theory. The algorithms use regression equations that forecast subtask timeliness as a function of external load parameters such as number of sensor reports and internal resource load parameters such as CPU utilization. The regression equations are determined off-line and on-line from application profiles that are collected off-line and on-line, respectively. To evaluate the performance of the predictive algorithms, we consider algorithms that determine the number of subtask replicas using empirically determined functions. The empirical functions compute the number of replicas as a function of the rate of change in the application workload during a "window" of past task periods. We implemented the resource management algorithms as part of a middleware infrastructure and measured the performance of the algorithms using a real-time benchmark. The experimental results indicate that the predictive, regression theory-based algorithms generally produce lower missed deadline ratios than the empirical strategies under the workload conditions that were studied. / Master of Science

International Telemetering Conference Proceedings / November 04-07, 1991 / Riviera Hotel and Convention Center, Las Vegas, Nevada / Real-time data processing of telemetry data has evolved from a highly centralized single large scale computer system to multiple mini-computers or super mini-computers tied together in a loosely coupled distributed network. Each mini-computer or super mini-computer essentially performing a single function in the real-time processing sequence of events. The reasons in the past for this evolution are many and varied. This paper will review some of the more significant factors in that evolution and will present some alternatives to a fully distributed mini-computer network that appear to offer significant real-time data processing advantages.

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.

This work tries to remedy the practical part of teaching development of software for real-time systems. It does so by creation of a platform on which students can practically learn aspects of development of software for real-time systems. % (feedback control, low level programming). The resulting platform consists of a plant, a visualizer and a controller. The plant represents an industrial machine, the visualizer displays the current state of the plant. The controller drives the plant. Students learn by developing a program for the controller. The resulting platform is realized as a hardware-in-the-loop simulation -- the controller's processor and devices are real hardware, and the plant is a simulated device. The platform has a low cost, low space requirements and it is not easily breakable. Powered by TCPDF (www.tcpdf.org)