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.

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.

Safe and efficient traffic control remains a challenging task with the continued increase in the number of vehicles, especially in urban areas. This manuscript focuses on traffic control at intersections, since urban roads with closely spaced intersections are often prone to queue spillbacks, which disrupt traffic flows across the entire network and increase congestion. While various intelligent traffic control solutions exist for autonomous systems, they are not applicable to or ineffective against human-operated vehicles or mixed traffic. On the other hand, existing approaches to manage intersections with human-operated vehicles, cannot adequately adjust to dynamic traffic conditions. This manuscript presents a technology-agnostic adaptive real-time server based approach to dynamically determine signal timings at an intersection based on changing traffic conditions and queue lengths (i.e., wait times) to minimize, if not eliminate, spillbacks without unnecessarily increasing delays associated with intersection crossings. We also provide timeliness guarantee bounds by analyzing the travel time delays, hence making our approach more dependable and predictable. The proposed approach was validated in simulations and on a realistic hardware testbed with robots mimicking human driving behaviors. Compared to the pre-timed traffic control and an adaptive scheduling based traffic control, our algorithm is able to avoid spillbacks under highly dynamic traffic conditions and improve the average crossing delay in most cases by 10--50 %. / Master of Science / Safe and efficient traffic control remains a challenging task with the continued increase in the number of vehicles, especially in urban areas. This manuscript focuses on traffic control at intersections, since urban roads with closely spaced intersections are often prone to congestion that blocks other intersection upstream, which disrupt traffic flows across the entire network. While various intelligent traffic control solutions exist for autonomous systems, they are not applicable to or ineffective against human-operated vehicles or mixed traffic. On the other hand, existing approaches to manage intersections with human-operated vehicles, cannot adequately adjust to dynamic traffic conditions. This work presents a technologyagnostic adaptive approach to dynamically determine signal timings at an intersection based on changing traffic conditions and queue lengths (i.e., wait times) to minimize, if not eliminate, spillbacks without unnecessarily increasing delays associated with intersection crossings. We also provide theoretical bounds to guarantee the performance of our approach in terms of the travel delays that may incur on the vehicles in the system, hence making our approach more dependable and predictable. The proposed approach was validated in simulations and on a realistic hardware testbed which uses robots to mimic human driving behaviour in an urban environment. Comparisons with widely deployed and state-of-the-art traffic control techniques show that our approach is able to minimize spillbacks as well as improve on the average crossing delay in most cases.

This dissertation explores several challenges that plague the hardware-software co-design of popular resource constrained real-time embedded systems. We specifically tackle existing real-world problems, and address them through our design solutions which are highly scalable, and have practical feasibility as verified through our solution implementation on real-world hardware. We address the problem of poor battery life in mobile embedded devices caused due to side-by-side execution of multiple applications in split-screen mode. Existing industry solutions either restricts the number of applications that can run simultaneously, limit their functionality, and/or increase the hardware capacity of the battery associated with the system. We exploit the gap in research on performance and power trade-off in smartphones to propose an integrated energy management solution, that judiciously minimizes the system-wide energy consumption with negligible effect on its quality of service (QoS). Another important real-world requirement in today's interconnected world is the need for security. In the domain of real-time computing, it is not only necessary to secure the system but also maintain its timeliness. Some example security mechanisms that may be used in a hard real-time system include, but are not limited to, security keys, protection of intellectual property (IP) of firmware and application software, one time password (OTP) for software certification on-the-fly, and authenticated computational off-loading. Existing design solutions require expensive, custom-built hardware with long time-to-market or time-to-deployment cycle. A readily available alternative is the use of trusted execution environment (TEE) on commercial off-the-shelf (COTS) embedded processors. However, utilizing TEE creates multiple challenges from a real-time perspective, which includes additional time overhead resulting in possible deadline misses. Second, trusted execution may adversely affect the deterministic execution of the system, as tasks running inside a TEE may need to communicate with other tasks that are executing on the native real-time operating system. We propose three different solutions to address the need for a new task model that can capture the complex relationship between performance and predictability for real-time tasks that require secure execution inside TEE. We also present novel task assignment and scheduling frameworks for real-time trusted execution on COTS processors to improve task set schedulability. We extensively assess the pros and cons of our proposed approaches in comparison to the state-of-the-art techniques in custom-built real-world hardware for feasibility, and simulated environments to test our solutions' scalability. / Doctor of Philosophy / Today's real-world problems demand real-time solutions. These solutions need to be practically feasible, and scale well with increasing end user demands. They also need to maintain a balance between system performance and predictability, while achieving minimum energy consumption. A recent example of technological design problem involves ways to improve the battery lifetime of mobile embedded devices, for example, smartphones, while still achieving the required performance objectives. For instance, smartphones that run Android OS has the capability to run multiple applications concurrently using a newly introduced split-screen mode of execution, where applications can run side-by-side at the same time on screen while using the same shared resources (e.g., CPU, memory bandwidth, peripheral devices etc.). While this can improve the overall performance of the system, it can also lead to increased energy consumption, thereby directly affecting the battery life. Another technological design problem involves ways to protect confidential proprietary information from being siphoned out of devices by external attackers. Let us consider a surveillance unmanned aerial vehicle (UAV) as an example. The UAV must perform sensitive tasks, such as obtaining coordinates of interest for surveillance, within a given time duration, also known as task deadline. However, an attacker may learn how the UAV communicates with ground control, and take control of the UAV, along with the sensitive information it carries. Therefore, it is crucial to protect such sensitive information from access by an unauthorized party, while maintaining the system's task deadlines. In this dissertation, we explore these two real-world design problems in depth, observe the challenges associated with them, while presenting several solutions to tackle the issues. We extensively assess the pros and cons of our proposed approaches in comparison to the state-of- the-art techniques in custom-built real-world hardware, and simulated environments to test our solutions' scalability.

Real-time channels are established between a source and a destination to guarantee in-time delivery of real-time messages in multi-hop networks. In this thesis, we propose two schemes to establish real-time channels for soft real-time applications whose timeliness properties are characterized using Jensen's Time Utility Functions (TUFs) that are non-increasing. The two algorithms are (1) Localized Decision for Utility accrual Channel Establishment (LocDUCE) and (2) Global Decision for Utility accrual Channel Establishment (GloDUCE). Since finding a feasible path optimizing multiple constraints is an NP-Complete problem, these schemes heuristically attempt to maximize the system-wide accrued utility. The channel establishment algorithms assume the existence of a utility-aware packet scheduling algorithm at the interfaces. The route selection is based on delay estimation performed at the source, destination, and all routers in the path, from source to destination. We simulate the algorithms, measure and compare their performance with open shortest path first (OSPF). Our simulation experiments show that for most of the cases considered LocDUCE and GloDUCE perform better than OSPF. We also implement the schemes in a proof-of-concept style routing module and measure the performance of the schemes and compare them to OSPF. Our experiments on the implementation follow the same trend as the simulation study and show that LocDUCE and GloDUCE have a distinct advantage over OSPF and accrue higher system-wide utility. These schemes also react better to variation in the loading of the links. Among the two proposed approaches, we observe that GloDUCE performs better than LocDUCE under conditions of increased downstream link loads. / Master of Science

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)