Threshold cryptosystems (TCs), developed to eliminate single points of failure in applications such as key management-as-a-service, signature schemes, encrypted data storage and even blockchain applications, rely on the assumption that an adversary does not corrupt more than a fixed number of nodes in a network. This assumption, once broken, can lead to the entire system being compromised. In this paper, we present a systems-level solution, viz., a reboot-based framework, Groundhog, that adds a layer of resiliency on top of threshold cryptosystems (as well as others); our framework ensures the system can be protected against malicious (mobile) adversaries that can corrupt up all but one device in the network. Groundhog ensures that a sufficient number of honest devices is always available to ensure the availability of the entire system. Our framework is general-izable to multiple threshold cryptosystems - we demonstrate this by integrating it with two well-known TC protocols - the Distributed Symmetric key Encryption system (DiSE) and the Boneh, Lynn and Shacham Distributed Signatures (BLS) system. In fact, Groundhog may have applicability in systems beyond those based on threshold cryptography - we demonstrate this on a simpler cryptographic protocol that we developed named PassAround11In fact, this protocol was suggested by a USENIX Security reviewer that we then refined, implemented and evaluated in conjunction with Groundhog (see §6). . We developed a (generalizable) container-based framework that can be used to combine Groundhog (and its guarantees) with cryptographic protocols and evaluated our system using, ($a$) case studies of real world attacks as well as ($b$) extensive measurements by implementing the aforementioned DiSE, BLS and PassAround protocols on Groundhog. We show that Groundhog is able to guarantee high availability with minimal overheads (less than 7%). In some instances, Groundhog actually improves the performance of the TC schemes!22While it seems counter-intuitive, we explain the reasoning in §5.

Passive Infra-Red (PIR) sensors are ubiquitous and have applications ranging from automatic lighting and heating control in smart buildings, towel dispensers in washrooms, security alarms (for intrusion detection) to human detection robots (for search and rescue). Unfortunately, PIR sensors are prone to failures during deployment due to reasons such as environmental damage, incorrect installation and component degradation among others that can lead to incorrect or faulty data. Currently, such failures are typically detected using either : (a) heavily engineered data-driven, statistical approaches that can have high false positive rates due to unseen data patterns or (b) expensive, unscalable methods that use additional hardware such as video cameras or a golden reference sensor. In this work, we first create a taxonomy for the most common PIR sensor failures and analyze these failures from the perspective of sensor physics. We then present PIRMedic— a physics-driven, edge-based approach to detect and diagnose the failures in a PIR sensor using an intrinsic hardware signal viz., the analog output from the pyroelectric element in the sensor. Using this hardware signal in conjunction with frequency analysis and supervised machine learning methods, we obtain a high accuracy of 98-99% in failure detection and diagnosis. We evaluate our methods using multiple real-world deployments , in four distinct locations, in different environment and usage conditions.

Modern Internet-of-Things devices are vulnerable to attacks targeting outgoing actuation commands that modify their physical behaviors. We present a “selective checking” mechanism that uses game-theoretic modeling to identify the suitable subset of commands to be checked in order to deter an adversary. This mechanism is coupled with a “delay-aware” trusted execution environment to ensure that only verified actuation commands are ever sent to the physical system, thus maintaining the safety and integrity of the system. Our proposed selective checking and trusted execution (SCATE) framework is implemented on an off-the-shelf ARM platform running embedded Linux and tested on four realistic IoT-specific cyber-physical systems (a ground rover, a flight controller, a robotic arm and an automated syringe pump).

Timing correctness is crucial in a multi-criticality real-time system, such as an autonomous driving system. It has been recently shown that these systems can be vulnerable to timing inference attacks, mainly due to their predictable behavioral patterns. Existing solutions like schedule randomization cannot protect against such attacks, often limited by the system’s real-time nature. This article presents “ SchedGuard++ ”: a temporal protection framework for Linux-based real-time systems that protects against posterior schedule-based attacks by preventing untrusted tasks from executing during specific time intervals. SchedGuard++ supports multi-core platforms and is implemented using Linux containers and a customized Linux kernel real-time scheduler. We provide schedulability analysis assuming the Logical Execution Time (LET) paradigm, which enforces I/O predictability. The proposed response time analysis takes into account the interference from trusted and untrusted tasks and the impact of the protection mechanism. We demonstrate the effectiveness of our system using a realistic radio-controlled rover platform. Not only is “ SchedGuard++ ” able to protect against the posterior schedule-based attacks, but it also ensures that the real-time tasks/containers meet their temporal requirements.

System auditing is an essential tool for detecting malicious events and conducting forensic analysis. Although used extensively on general-purpose systems, auditing frameworks have not been designed with consideration for the unique constraints and properties of Real-Time Systems (RTS). System auditing could provide tremendous benefits for security-critical RTS. However, a naive deployment of auditing on RTS could violate the temporal requirements of the system while also rendering auditing incomplete and ineffectual. To ensure effective auditing that meets the computational needs of recording complete audit information while adhering to the temporal requirements of the RTS, it is essential to carefully integrate auditing into the real-time (RT) schedule. This work adapts the Linux Audit framework for use in RT Linux by leveraging the common properties of such systems, such as special purpose and predictability.Ellipsis, an efficient system for auditing RTS, is devised that learns the expected benign behaviors of the system and generates succinct descriptions of the expected activity. Evaluations using varied RT applications show thatEllipsisreduces the volume of audit records generated during benign activity by up to 97.55% while recording detailed logs for suspicious activities. Empirical analyses establish that the auditing infrastructure adheres to the properties of predictability and isolation that are important to RTS. Furthermore, the schedulability of RT tasksets under audit is comprehensively analyzed to enable the safe integration of auditing in RT task schedules.

Operating system (OS) extensions are more popular than ever. For example, Linux BPF is marketed as a "superpower" that allows user programs to be downloaded into the kernel, verified to be safe and executed at kernel hook points. So, BPF extensions have high performance and are often placed at performance-critical paths for tracing and filtering.

Modern embedded real-time systems (RTS) are increasingly facing more security threats than the past. A simplistic straightforward integration of security mechanisms might not be able to guarantee thesafetyand predictability of such systems. In this article, we focus on integrating security mechanisms into RTS (especiallylegacyRTS). We introduceContego-C, an analytical model to integrate security tasks into RTS that will allow system designers to improve the security posture without affecting temporal and control constraints of the existing real-time control tasks. We also define ametric(named tightness of periodic monitoring) to measure the effectiveness of such integration. We demonstrate our ideas using a proof-of-concept implementation on an ARM-based rover platform and show that Contego-C can improve security without degrading control performance.

Scheduler side-channels can leak critical information in real-time systems, thus posing serious threats to many safety-critical applications. The main culprit is the inherent determinism in the runtime timing behavior of such systems, e.g., the (expected) periodic behavior of critical tasks. In this paper, we introduce the notion of "schedule indistinguishability/", inspired by work in differential privacy, that introduces diversity into the schedules of such systems while offering analyzable security guarantees. We achieve this by adding a sufficiently large (controlled) noise to the task schedules in order to break their deterministic execution patterns. An "epsilon-Scheduler" then implements schedule indistinguishability in real-time Linux. We evaluate our system using two real applications: (a) an autonomous rover running on a real hardware platform (Raspberry Pi) and (b) a video streaming application that sends data across large geographic distances. Our results show that the epsilon-Scheduler offers better protection against scheduler side-channel attacks in real-time systems while still maintaining good performance and quality-of-service(QoS) requirements.

Safety-critical networks often have stringent real-time requirements; they must also be resilient to failures. In this paper, we propose the RealFlow framework that uses commodity software-defined networks (SDNs) to realize networks with end-to-end timing guarantees, while also: (a) increasing resiliency against link/switch failures and (b) increasing network utilization. The use of SDNs in this space also improves the management capabilities of the system due to the global visibility into the network. RealFlow is implemented as a northbound SDN controller application compatible with standard OpenFlow protocols with little to no runtime overheads. We demonstrate feasibility on a real hardware testbed (Pica8 SDN switches+Raspberry Pi endhosts) and a practical avionics case study. Our evaluations show that RealFlow can accommodate 63% more network flows with safety-critical guarantees when compared to current designs and up to 18% when link resiliency (via backup paths) is also considered.

Real-time systems have recently been shown to be vulnerable to timing inference attacks, mainly due to their predictable behavioral patterns. Existing solutions such as schedule randomization lack the ability to protect against such attacks, often limited by the system's real-time nature. This paper presents “SchedGuard”: a temporal protection framework for Linux-based hard real-time systems that protects against posterior scheduler side-channel attacks by preventing untrusted tasks from executing during specific time segments. SchedGuard is integrated into the Linux kernel using cgroups, making it amenable to use with container frameworks. We demonstrate the effectiveness of our system using a realistic radio-controlled rover platform and synthetically generated workloads. Not only is SchedGuard able to protect against the attacks mentioned above, but it also ensures that the real-time tasks/containers meet their temporal requirements.

We propose HYDRA-C, a design-time evaluation framework for integrating monitoring mechanisms in multicore real-time systems (RTS). Our goal is to ensure that security (or other monitoring) mechanisms execute in a "continuous" manner - i.e., as often as possible, across cores. This is to ensure that any such mechanisms run with few interruptions, if any. HYDRA-C is intended to allow designers of RTS to integrate monitoring mechanisms without perturbing existing timing properties or execution orders. We demonstrate the framework using a proofof-concept implementation with intrusion detection mechanisms as security tasks. We develop and use both, (a) a custom intrusion detection system (IDS) as well as (b) Tripwire - an open source data integrity checking tool. We compare the performance of HYDRA-C with a state-of-the-art multicore RT security integration approach and find that our method does not impact the schedulability and, on average, can detect intrusions 19.05% faster without impacting the performance of RT tasks.

Unikernels leverage library OS architectures to run isolated workloads on the cloud. They have garnered attention in part due to their promised performance characteristics such as small image size, fast boot time, low memory footprint and application performance. However, those that aimed at generality fall short of the application compatibility, robustness and, more importantly, community that is available for Linux. In this paper, we describe and evaluate Lupine Linux, a standard Linux system that---through kernel configuration specialization and system call overhead elimination---achieves unikernel-like performance, in fact outperforming at least one reference unikernel in all of the above dimensions. At the same time, Lupine can run any application (since it is Linux) when faced with more general workloads, whereas many unikernels simply crash. We demonstrate a graceful degradation of unikernel-like performance properties.

We demonstrate the presence of a novel scheduler side-channel in preemptive, fixed-priority real-time systems (RTS); examples of such systems can be found in automotive systems, avionic systems, power plants and industrial control systems among others. This side-channel can leak important timing information such as the future arrival times of real-time tasks. This information can then be used to launch devastating attacks, two of which are demonstrated here (on real hardware platforms). Note that it is not easy to capture this timing information due to runtime variations in the schedules, the presence of multiple other tasks in the system and the typical constraints (e.g., deadlines) in the design of RTS. Our ScheduLeak algorithms demonstrate how to effectively exploit this side-channel. A complete implementation is presented on real operating systems (in Real-time Linux and FreeRTOS). Timing information leaked by ScheduLeak can significantly aid other, more advanced, attacks in better accomplishing their goals.

Safety violations in programmable logic controllers (PLCs), caused either by faults or attacks, have recently garnered significant attention. However, prior efforts at PLC code vetting suffer from many drawbacks. Static analyses and verification cause significant false positives and cannot reveal specific runtime contexts. Dynamic analyses and symbolic execution, on the other hand, fail due to their inability to handle real-world PLC programs that are event-driven and timing sensitive. In this paper, we propose VetPLC, a temporal context-aware, program analysis-based approach to produce timed event sequences that can be used for automatic safety vetting. To this end, we (a) perform static program analysis to create timed event causality graphs in order to understand causal relations among events in PLC code and (b) mine temporal invariants from data traces collected in Industrial Control System (ICS) testbeds to quantitatively gauge temporal dependencies that are constrained by machine operations. Our VetPLC prototype has been implemented in 15K lines of code. We evaluate it on 10 real-world scenarios from two different ICS settings. Our experiments show that VetPLC outperforms state-of-the-art techniques and can generate event sequences that can be used to automatically detect hidden safety violations.

Physical plants that form the core of the cyber-physical systems (CPSs) often have stringent safety requirements and, recent attacks have shown that cyber intrusions can cause damage to these plant. In this paper, we demonstrate how to ensure the safety of the physical plant even when the platform is compromised. We leverage the fact that due to physical inertia, an adversary cannot destabilize the plant (even with complete control over the software) instantaneously. In fact, it often takes finite (even considerable time). This paper provides the analytical framework that utilizes this property to compute safe operational windows in run-time during which the safety of the plant is guaranteed. To ensure the correctness of the computations in runtime, we discuss two approaches to ensure the integrity of these computations in an untrusted environment: 1) full platform-wide restarts coupled with a root-of-trust timer and 2) utilizing trusted execution environment features available in hardware. We demonstrate our approach using two realistic systems-a 3 degree-of-freedom helicopter and a simulated warehouse temperature management unit and show that our system is robust against multiple emulated attacks-essentially the attackers are not able to compromise the safety of the CPS.

The increased capabilities of modern real-time systems (RTS) expose them to various security threats. Recently, frameworks that integrate security tasks without perturbing the real-time tasks have been proposed, but they only target single core systems. However, modern RTS are migrating towards multicore platforms. This makes the problem of integrating security mechanisms more complex, as designers now have multiple choices for where to allocate the security tasks. In this paper we propose HYDRA, a design space exploration algorithm that finds an allocation of security tasks for multicore RTS using the concept of opportunistic execution. HYDRA allows security tasks to operate with existing real-time tasks without perturbing system parameters or normal execution patterns, while still meeting the desired monitoring frequency for intrusion detection. Our evaluation uses a representative real-time control system (along with synthetic task sets for a broader exploration) to illustrate the efficacy of HYDRA.

The Internet-of-Things (IoT) is a large and complex domain. These systems are often constructed using a very diverse set of hardware, software and protocols. This, combined with the ever increasing number of IoT solutions/services that are rushed to market means that most such systems are rife with security holes. Recent incidents (e.g., the Mirai botnet) further highlight such security issues. With emerging technologies such as blockchain and software-defined networks (SDNs), new security solutions are possible in the IoT domain. In this paper we will explore future trends in IoT security: (a) the use of blockchains in IoT security, (b) data provenance for sensor information, (c) reliable and secure transport mechanisms using SDNs (d) scalable authentication and remote attestation mechanisms for IoT devices and (e) threat modeling and risk/maturity assessment frameworks for the domain.

Despite the isolation mechanisms that are available to cloud service providers, like virtual machines and containers, the problem of side-channel vulnerabilities due to shared caches and multicore processors remains a threat. We present a hardware-software mechanism that improves the isolation of cloud processes in the presence of shared caches on multicore chips. Our technique can enable cache-side-channel free computing for Linux-based containers and virtual machines by com-bining the Intel CAT architecture that enables cache partitioning with novel scheduling techniques and state cleansing mechanisms. We evaluate our system using a CPU-bound workload and demonstrate cache-side-channel-free computation that is correct by construction. Our system allows Simultaneous Multithreading to remain enabled and does not require application level changes.

Embedded real-time systems (RTS) are pervasive. Many modern RTS are exposed to unknown security flaws, and threats to RTS are growing in both number and sophistication. However, until recently, cyber-security considerations were an afterthought in the design of such systems. Any security mechanisms integrated into RTS must (a) co-exist with the real-time tasks in the system and (b) operate without impacting the timing and safety constraints of the control logic. We introduce Contego, an approach to integrating security tasks into RTS without affecting temporal requirements. Contego is specifically designed for legacy systems, viz., the real-time control systems in which major alterations of the system parameters for constituent tasks is not always feasible. Contego combines the concept of opportunistic execution with hierarchical scheduling to maintain compatibility with legacy systems while still providing flexibility by allowing security tasks to operate in different modes. We also define a metric to measure the effectiveness of such integration. We evaluate Contego using synthetic workloads as well as with an implementation on a realistic embedded platform (an open-source ARM CPU running real-time Linux).

Real-time systems (RTS) require end-to-end delay guarantees for the delivery of network packets. In this paper, we propose a framework to reduce the management and integration overheads for such real-time (RT) network flows by leveraging the capabilities of software-defined networking (SDN) - capabilities that include global visibility and management of the network. Given the specifications of flows that must meet hard real-time requirements, our framework synthesizes paths through the network. To guarantee that these flows meet both, their bandwidth and end-to-end timing requirements, our framework solves a multi-constraint optimization problem using a heuristic algorithm. We use exhaustive emulations and experiments on hardware switches to demonstrate our techniques and feasibility of our approach. As a result of this work, SDNs become “delay-aware” and thus can be adapted for use in safety-critical and other delay-sensitive applications.

The high degree of predictability in real-time systems makes it possible for adversaries to launch timing inference attacks such as those based on side-channels and covert-channels. We present TaskShuffler, a schedule obfuscation method aimed at randomizing the schedule for such systems while still providing the real-time guarantees that are necessary for their safe operation. This paper also analyzes the effect of these mechanisms by presenting schedule entropy - a metric to measure the uncertainty (as perceived by attackers) introduced by TaskShuffler. These mechanisms will increase the difficulty for would-be attackers thus improving the overall security guarantees for real-time systems.

Due to physical isolation as well as use of proprietary hardware and protocols, traditional real-time systems (RTS) were considered to be invulnerable to security breaches and external attacks. This assumption is being challenged by recent attacks that highlight vulnerabilities in RTS. Besides, a straightforward integration of security mechanisms might compromise the safety and predictability guarantees of such systems. In this paper, we focus on integrating security mechanisms into RTS (especially legacy RTS) and define a metric to measure the effectiveness of such integration. We combine opportunistic execution with hierarchical scheduling to maintain compatibility with legacy systems while still providing flexibility. The proposed approach is shown to increase the security posture of RTS without impacting their temporal (and hence, safety) constraints.

The sophistication of malicious adversaries is increasing every day and most defenses are often easily overcome by such attackers. Many existing defensive mechanisms often make differing assumptions about the underlying systems and use varied architectures to implement their solutions. This often leads to fragmentation among solutions and could even open up additional vulnerabilities in the system.

In this paper, we introduce a novel mechanism that identifies abnormal system-wide behaviors using the predictable nature of real-time embedded applications. We introduce Memory Heat Map (MHM) to characterize the memory behavior of the operating system. Our machine learning algorithms automatically (a) summarize the information contained in the MHMs and then (b) detect deviations from the normal memory behavior patterns. These methods are implemented on top of a multicore processor architecture to aid in the process of monitoring and detection. The techniques are evaluated using multiple attack scenarios including kernel rootkits and shellcode. To the best of our knowledge, this is the first work that uses aggregated memory behavior for detecting system anomalies especially the concept of memory heat maps.

Traditionally real-time systems and security have been considered as separate domains. Recent attacks on various systems with real-time properties have shown the need for a redesign of such systems to include security as a first class principle. In this paper, we propose a general model for capturing security constraints between tasks in a real-time system. This model is then used in conjunction with real-time scheduling algorithms to prevent the leakage of information via storage channels on implicitly shared resources. We expand upon a mechanism to enforce these constraints viz., cleaning up of shared resource state, and provide schedulability conditions based on fixed priority scheduling with both preemptive and non-preemptive tasks. We perform extensive evaluations, both theoretical and experimental, the latter on a hardware-in-the-loop simulator of an unmanned aerial vehicle (UAV) that executes on a demonstration platform.

Real-time systems (RTS) were typically considered to be invulnerable to external attacks, mainly due to their use of proprietary hardware and protocols, as well as physical isolation. As a result, RTS and security have traditionally been separate domains. These assumptions are being challenged by a series of recent events that highlight the vulnerabilities in RTS. In this paper we focus on integrating security as a first class principle in the design of RTS: we show that certain security requirements can be specified as real-time scheduling constraints. Using information leakage as a motivating problem, we illustrate our techniques with fixed-priority (FP) real-time schedulers. We evaluate our approach and discuss tradeoffs. Our evaluation shows that many real-time task sets can be scheduled under the proposed constraints without significant performance impact.

Security violations are becoming more common in real-time systems - an area that was considered to be invulnerable in the past - as evidenced by the recent W32.Stuxnet and Duqu worms. A failure to protect such systems from malicious entities could result in significant harm to both humans as well as the environment. The increasing use of multicore architectures in such systems exacerbates the problem since shared resources on these processors increase the risk of being compromised. In this paper, we present the SecureCore framework that, coupled with novel monitoring techniques, is able to improve the security of realtime embedded systems. We aim to detect malicious activities by analyzing and observing the inherent properties of the real-time system using statistical analyses of their execution profiles. With careful analysis based on these profiles, we are able to detect malicious code execution as soon as it happens and also ensure that the physical system remains safe.

Embedded systems with real-time constraints depend on a priori knowledge of worst-case execution times (WCETs) to determine if tasks meet deadlines. Static timing analysis derives bounds on WCETs but requires statically known loop bounds. This work removes the constraint on known loop bounds through parametric analysis expressing WCETs as functions. Tighter WCETs are dynamically discovered to exploit slack by dynamic voltage scaling (DVS) saving 60% to 82% energy over DVS-oblivious techniques and showing savings close to more costly dynamic-priority DVS algorithms. Overall, parametric analysis expands the class of real-time applications to programs with loop-invariant dynamic loop bounds while retaining tight WCET bounds.

Embedded processors have become increasingly complex, resulting in variable execution behavior and reduced timing predictability. On such processors, safe timing specifications expressed as bounds on the worst-case execution time (WCET) are generally too loose due to conservative assumptions about complex architectural features, timing anomalies and programmatic complexities. Hence, exploiting the latest architectures may not be an option for embedded systems with hard real-time constraints where deadline misses cannot be tolerated.

Multicores are becoming ubiquitous, not only in general-purpose but also embedded computing. This trend is a reflexion of contemporary embedded applications posing steadily increasing demands in processing power. On such platforms, prediction of timing behavior to ensure that deadlines of real-time tasks can be met is becoming increasingly difficult. While real-time multicore scheduling approaches help to assure deadlines based on firm theoretical properties, their reliance on task migration poses a significant challenge to timing predictability in practice. Task migration actually (a) reduces timing predictability for contemporary multicores due to cache warm-up overheads while (b) increasing traffic on the network-on-chip (NoC) interconnect.This paper puts forth a fundamentally new approach to increase the timing predictability of multicore architectures aimed at task migration in embedded environments. A task migration between two cores imposes cache warm-up overheads on the migration target, which can lead to missed deadlines for tight real-time schedules. We propose novel micro-architectural support to migrate cache lines. Our scheme shows dramatically increased predictability in the presence of cross-core migration.Experimental results for schedules demonstrate that our scheme enables real-time tasks to meet their deadlines in the presence of task migration. Our results illustrate that increases in execution time due to migration is reduced by our scheme to levels that may prevent deadline misses of real-time tasks that would otherwise occur. Our mechanism imposes an overhead at a fraction of the task's execution time, yet this overhead can be steered to fill idle slots in the schedule, i.e., it does not contribute to the execution time of the migrated task. Overall, our novel migration scheme provides a unique mechanism capable of significantly increasing timing predictability in the wake of task migration.

In complex hard real-time systems with tight constraints on system resources, small changes in one component of a system can cause a cascade of adverse effects on other parts of the system. We address the inherent complexity of making architectural decisions by raising the level of abstraction at which the analysis is performed. Our analysis approach gives the system architect a rigorous method for quickly determining which system architectures should be pursued, and it allows the architect to track and manage the cascading effects of subsystem/component changes in a comprehensive, quantitative manner. The end product is a virtual architecture analysis that systematically incorporates the inherent coupling among interacting system components that share limited system resources.

Embedded services and applications that interact with the real world often,over time, need to run on different kinds of hardware (low-costmicrocontrollers to powerful multicore processors). It is difficult to writeone program that would work reliably on such a wide range of devices. This isespecially true when the application must be temporally predictable and robust,which is usually be the case since the physical world works in real-time.Thus, any application interacting with such a system, must also work inreal-time.In this paper we introduce a representation of the temporal behavior ofdistributed real-time applications as colored graphs that capture the timingof temporally continuous sections of execution and dependencies between them,creating a partial order. We then introduce a method of extracting the graphfrom existing applications using a combination of analysis techniques. Once thegraph has been created, we introduce a number of graph transformations thatextract ``meaning'' from the graph. The knowledge thus gained, can be utilizedfor scheduling and for adjusting the level of parallelism suitable to the specifichardware, for identifying hot spots, false parallelism, or even candidates foradditional concurrency. The importance of these contributions is evident whenwe see that such graphs can be sequentialized to our partiture model andcan then be used as input for offline, online, or even distributed real-timescheduling. Finally we present results from analysis of a complete TCP/IP stackin addition to smaller test applications which show that our use of differentanalysis models result in a reduction of the complexities of graphs. Animportant outcome is that increasing the expression of concurrency can reducethe level of parallelism required, saving memory on deeply embedded platforms,while keeping the program parallelizable whenever complete serializability isnot required. We also show that applications which were previously consideredto be too complex for characterization of their worst-case behavior are nowanalyzable due to the combination of analysis techniques that we utilize.

Embedded systems are often subject to constraints that require determinism to ensure that task deadlines are met. Such systems are referred to as real-time systems. Schedulability analysis provides a firm basis to ensure that tasks meet their deadlines for which knowledge of worst-case execution time (WCET) bounds is a critical piece of information. Static timing analysis techniques are used to derive these WCET bounds. A limiting factor for designing realtime systems is the class of processors that can be used. Typically, modern, complex processor pipelines cannot be used in real-time systems design. Contemporary processors with their advanced architectural features, such as out-of-order execution, branch prediction, speculation, prefetching, etc., cannot be statically analyzed to obtain tight WCET bounds for tasks. This is caused by the non-determinism of these features, which surfaces in full only at runtime. In this paper, we introduce a new paradigm to perform timing analysis of tasks for real-time systems running on modern processor architectures. We propose minor enhancements to the processor architecture to enable this process. These features, on interaction with software modules, are able to obtain tight, accurate timing analysis results for modern processors. We also briefly present analysis techniques that, combined with our timing analysis methods, reduce the complexity of worst-case estimations for loops. To the best of our knowledge, this method of constant interactions between hardware and software to calculate WCET bounds for out-of-order processors is the first of its kind.

Many embedded systems are subject to temporal constraints that require advance guarantees on meeting deadlines. Such systems rely on static analysis to safely bound worst-case execution (WCET) bounds of tasks. Designers of these systems are forced to avoid state-of-the-art processors due to their inherent architectural complexity (such as out-of-order instruction scheduling) that results in non-determinism.This work addresses this problem by providing novel pipeline analysis techniques for characterizing the worst-case behavior of real-time systems on modern processor architectures. We introduce methods to capture (ldquosnapshotrdquo) pipeline state and to subsequently perform a ldquomergerdquo of previously captured snapshots. We prove that our pipeline analysis correctly preserves worst-case timing behavior on out-of-order (OOO) processor pipelines. We further specifically show that anomalous pipeline effects, effectively dilating timing, are preserved by our method. To the best of our knowledge, this method of pipeline analysis and interactions between hardware/software for obtaining WCET bounds on OOO processors is the first of its kind.

Low-end embedded architectures, such as sensor nodes, have become popular in diverse fields, many of which impose real-time constraints. Currently, the Atmel Atmega processor family used by Berkeley Motes lacks support for deriving safe bounds on the WCET, which is a prerequisite for performing real-time schedulability analysis. Our work fills this gap by providing an analytical method to obtain WCET bounds for this processor architecture. Our first contribution is to analyze both C and NesC code, the latter of which is unprecedented. The second contribution is to model control hazards and variable-cycle instructions, both handled more efficiently by our approach than by previous ones and results in up to 77% improvement in bounding the WCET. The results demonstrate that our timing analysis framework is able to tightly and safely estimate the WCET of the benchmarks while simulator results are shown to not always provide safe WCET bounds. While motivated by the Atmel Atmega series of processors, results are equally applicable to low-end embedded processors. This work is, to the best of our knowledge, the first set of experiments where timing results are contrasted from execution on an actual processor, from a cycle-accurate simulator and from a static timing analyzer. Furthermore, making our timing analysis toolset available to the Atmel Atmega processor family is a significant contribution towards addressing a documented need for tool support for sensor node architectures commonly used in networked systems of embedded computers, or so-called EmNets.

Static timing analysis safely bounds worst-case execution times to determine if tasks can meet their deadlines in hard real-time systems. However, conventional timing analysis requires that the upper bound of loops be known statically, which limits its applicability. Parametric timing analysis methods remove this constraint by providing the WCET as a formula parameterized on loop bounds. This paper contributes a novel technique to allow parametric timing analysis to interact with dynamic real-time schedulers. By dynamically detecting actual loop bounds, a lower WCET bound can be calculated, on-the-fly, for the remaining execution of a task. We analyze the benefits from parametric analysis in terms of dynamically discovered slack in a schedule. We then assess the potential for dynamic power conservation by exploiting parametric loop bounds for ParaScale, our intra-task dynamic voltage scaling (DVS) approach. Our results demonstrate that the parametric approach to timing analysis provides 66%-80% additional savings in power consumption. We further show that using this approach combined with online intra-task DVS to exploit parametric execution times results in much lower power consumption. Hence, even in the absence of dynamic scheduling, significant savings in power can be obtained, e.g., in the case of cyclic executives.