Time series are a fundamental building block of modern data analysis due to their cost-effectiveness in data collection and versatility in capturing a variety of dynamic phenomena over time. In many applications, the measured proxy variable represents an activity or state of the underlying system of interest. However, high-level information about the system is not directly accessible from raw time series data, which typically consist of sequentially recorded values over time rather than explicit system states. Conducting analysis on time series data often requires identifying the core patterns associated with different possible states. This identification step can enable forecasting, relationship mining, policy verification, or integrity assessment of the system of interest. When a system is neither observable (i.e., its states or activity cannot be accessed at any time) nor controllable (i.e., its states or activity cannot be scheduled), mining key patterns must rely on unsupervised methods. Moreover, when assuming that the system is always in one state, the solution must maximize coverage of the input time series rather than simply returning the best matches. In this paper, we propose a novel approach for mining recurrent patterns from time series, with a focus on maximizing time series coverage. The method first generates a list of candidate patterns and their occurrences using a well-established matrix profile algorithm. Then, a translation layer produces an ensemble of constraints compiled into a model that describes a solution while preventing overlapping occurrences. Finally, a constraint solver generates a solution in the form of a set of core patterns, which are selected based on predefined constraints on the Number of Patterns (NoP) and coverage conditions. We evaluate this approach on a dataset of power consumption time series representing the activity of a computer, as well as synthetic pattern-based time series.

Modern firmware development is done in a fast-paced, time-constrained environment. This pressure tempts developers to use generative AI to write code for them to save time. While this is a powerful tool with careful developer review, these reviews are commonly sacrificed to meet deadlines. This results in AI-written code existing verbatim, deployed in the firmware of devices finding their way into our cyber-physical environment. In the absence of developer oversight, we suggest that generative AI-written code does not sufficiently account for common software weaknesses. In this work, we explore a collection of modern Large Language Models (LLMs) and use them to generate code based on popular network standards. We fuzz this code to discover vulnerabilities in the code generated by the LLMs. We organize these vulnerabilities according to the Common Weakness Enumeration (CWE) and use them to develop a three-axis taxonomy of common LLM-generated weaknesses. Finally, we provide suggested input categories to more easily exploit these weaknesses in a black-box setting, as a first step towards fuzz testing for LLM-generated code in embedded systems networking.

The lack of any sender authentication mechanism in place makes Controller Area Network (CAN) vulnerable to security threats. For instance, an attacker can impersonate an Electronic Control Unit (ECU) on the bus and send spoofed messages unobtrusively with the identifier of the impersonated ECU. To address this problem, we propose a novel source authentication technique that uses power consumption measurements of the ECU to authenticate the source of a message. A transmission of an ECU affects the power consumption and a characteristic pattern will appear. Our technique exploits the power consumption of each ECU during the transmission of a message to determine whether the message actually originated from the purported sender. We evaluate our approach in both a lab setup and a real vehicle. We also evaluate our approach against factors that can impact the power consumption measurement of the ECUs. The results of the evaluation show that the proposed technique is applicable in a broad range of operating conditions with reasonable computational power requirements and attaining good accuracy.

Side channel analysis offers several advantages over traditional machine monitoring methods. The low intrusiveness, independence with the host, data reliability and difficulty to bypass are compelling arguments for using involuntary emissions as input for enforcing security policies. However, side-channel information often comes in the form of unlabeled time series of a proxy variable of the activity. Enabling the definition and enforcement of high-level security policies requires extracting the state or activity of the system from the input data. We present in this paper a novel time series, one-shot pattern locator and classifier called Machine Activity Detector (MAD) specifically designed and evaluated for side-channel analysis. We evaluate MAD in two case studies on a variety of machines and datasets where it outperforms other traditional state detection solutions and presents formidable performances for security rules enforcement. Results of state detection with MAD enable the definition and verification of high-level security rules to detect various attacks without any interaction with the monitored machine.

The current security mechanisms for embedded systems often rely on Intrusion Detection System (IDS) running on the system itself. This provides the detector with relevant internal resources but also exposes it to being bypassed by an attacker. If the host is compromised, its IDS can not be trusted anymore and becomes useless. Power consumption offers an accurate and trusted representation of the system’s state that can be leveraged to verify its integrity during the boot sequence. We present a novel IDS that uses the side-channel power consumption of a target device to protect it against various firmware and hardware attacks. The proposed Boot Process Verifier (BPV) uses a combination of rule-based and machine-learning-based side-channel analysis to monitor and evaluate the integrity of different networking equipment with an overall accuracy of 0,942. The BPV is part of a new layer of cybersecurity mechanisms that leverage the physical emissions of devices for protection.

Modern cars are becoming more accessible targets for cyberattacks due to the proliferation of wireless communication channels. The intra-vehicle Controller Area Network (CAN) bus lacks authentication, which exposes critical components to interference from less secure, wirelessly compromised modules. To address this issue, we propose vProfile, a sender authentication system based on voltage fingerprints of Electronic Control Units (ECUs). vProfile exploits the physical properties of ECU output voltages on the CAN bus to determine the authenticity of bus messages, which enables the detection of both hijacked ECUs and external devices connected to the bus. We show the potential of vProfile using experiments on two production vehicles with precision and recall scores of over 99.99%. The improved identification rates and more straightforward design of vProfile make it an attractive improvement over existing methods.

One of the significant challenges of deep neural networks is that the complex nature of the network prevents human comprehension of the outcome of the network. Consequently, the applicability of complex machine learning models is limited in the safety-critical domains, which incurs risk to life and property. To fully exploit the capabilities of complex neural networks, we propose a non-intrusive interpretability technique that uses the input and output of the model to generate a saliency map. The method works by empirically optimizing a randomly initialized input mask by localizing and weighing individual pixels according to their sensitivity towards the target class. Our experiments show that the proposed model interpretability approach performs better than the existing saliency map-based approaches methods at localizing the relevant input pixels. Furthermore, to obtain a global perspective on the target-specific explanation, we propose a saliency map reconstruction approach to generate acceptable variations of the salient inputs from the space of input data distribution for which the model outcome remains unaltered. Experiments show that our interpretability method can reconstruct the salient part of the input with a classification accuracy of 89%.

Embedded safety-critical systems are essential for today's society as we rely on them in all aspects of our life. Should safety-critical systems fail to meet their specified function, then they have the potential to cause harm to people, cause loss of capital infrastructure, or cause significant damage to the environment. Safety-critical systems are becoming increasingly complex; the more complex, the higher the risk of safety hazards for the public. With the increase of automation in driving and other areas, the complexity and criticality of the software will continue to increase drastically. Computer assistance will become essential for humans to get a deep understanding of programs underlying modern systems. Mining specifications and properties from program traces is a promising approach to help humans understand modern complex programs. Understanding temporal dependencies in relation to performance is one aspect of such an endeavour. A specification mined from a system trace can allow the developer to understand, among others, task dependencies, activation patterns, and response triggers. The artefacts produced by mining are useful for system designers, developers, safety managers, and can even provide input for other tools. This talk introduces the concepts behind mining traces of embedded software programs and discusses the challenges of building practical tools.

Most real-world datasets, and particularly those collected from physical systems, are full of noise, packet loss, and other imperfections. However, most specification mining, anomaly detection and other such algorithms assume, or even require, perfect data quality to function properly. Such algorithms may work in lab conditions when given clean, controlled data, but will fail in the field when given imperfect data. We propose a method for accurately reconstructing discrete temporal or sequential system traces affected by data loss, using Long Short-Term Memory Networks (LSTMs). The model works by learning to predict the next event in a sequence of events, and uses its own output as an input to continue predicting future events. As a result, this method can be used for data restoration even with streamed data. Such a method can reconstruct even long sequence of missing events, and can also help validate and improve data quality for noisy data. The output of the model will be a close reconstruction of the true data, and can be fed to algorithms that rely on clean data. We demonstrate our method by reconstructing automotive CAN traces consisting of long sequences of discrete events. We show that given even small parts of a CAN trace, our LSTM model can predict future events with an accuracy of almost 90%, and can successfully reconstruct large portions of the original trace, greatly outperforming a Markov Model benchmark. We separately feed the original, lossy, and reconstructed traces into a specification mining framework to perform downstream analysis of the effect of our method on state-of-the-art models that use these traces for understanding the behavior of complex systems.

Dynamic evaluation of a computer program is done by analyzing the data generated by it during the execution. The program is considered correct and efficient if it meets a set of pre-specified temporal properties. Temporal properties define the order of occurrence and timing constraints on event occurrence. These properties become all the more important in the case of safety-critical real-time systems where a delayed response to a request may lead to a fault in the system. In the context of real-time systems, it is thus desirable to mine timing information and a set of dominant properties from system execution traces for testing, verification, anomaly detection, and debugging purposes.We propose a framework to automatically mine timing characteristics for properties that are in the form of timed regular expressions (TREs) from system traces. The framework estimates a set of dominant and most frequently occurring properties and their timing characteristics. The framework is evaluated on traces from industrial safety-critical real-time applications (a deployed autonomous hexacopter system) using traces with more than 1 Million entries.

International audience

Hardware energy efficiency has been one of the prominent objectives of system design in the last two decades. However, with the recent explosion in mobile computing and the increasing demand for green data centers, software energy efficiency has also risen to be an equally important factor. The majority of classic concurrency control algorithms were designed in an era when energy efficiency was not an important dimension in algorithm design. Concurrency control algorithms are applied to solve a wide range of problems from kernel-level primitives in operating systems to networking devices and web services. These primitives and services are constantly and heavily invoked in any computing system and by a larger scale in networking devices and data centers. Thus, even a small change in their energy spectrum can make a huge impact on overall energy consumption for long periods of time. This paper focuses on the classic producer-consumer problem. First, we study the energy profile of a set of existing producer-consumer algorithms. In particular, we present evidence that although these algorithms share the same functional goals, their behavior with respect to energy consumption are drastically different. Then, we present a dynamic algorithm for the multiple producer-consumer problem, where consumers in a multicore system use learning mechanisms to predict the rate of production, and effectively utilize this prediction to attempt to latch onto previously scheduled CPU wake-ups. Such group latching increases the idle time between consumer activations resulting in more CPU idle time and, hence, lower average CPU frequency. This in turn reduces energy consumption. We enable consumers to dynamically reserve more pre-allocated memory in cases where the production rate is too high. Consumers may compete for the extra space and dynamically release it when it is no longer needed. Our experiments show that our algorithm provides a 38 percent decrease in energy consumption compared to a mainstream semaphore-based producer-consumer implementation when running 10 parallel consumers. We validate the effectiveness of our algorithm with a set of thorough experiments on varying parameters of scalability. Finally, we present our recommendations on when our algorithm is most beneficial.

System tracing, runtime monitoring, execution reconstruction are useful techniques for protecting the safety and integrity of systems. Furthermore, with time-aware or overhead-aware techniques being available, these techniques can also be used to monitor and secure production systems. As operating systems gain in popularity, even in deeply embedded systems, these techniques face the challenge to support multitasking. In this paper, we propose a novel non-intrusive technique, which efficiently reconstructs the execution trace of non-preemptive multitasking system by observing power consumption characteristics. Our technique uses the control-flow graph (CFG) of the application program to identify the most likely block of code that the system is executing at any given point in time. For the purpose of the experimental evaluation, we first instrument the source code to obtain power consumption information for each basic block, which is used as the training data for our Dynamic Time Warping and k-Nearest Neighbours (k-NN) classifier. Once the system is trained, this technique is used to identify live code-block execution (LCBE). We show that the technique can reconstruct the execution flow of programs in a multi-tasking environment with high accuracy.

Real-time embedded systems have evolved from simple, self-contained single-processor computers to distributed multiprocessor systems that are extremely hard to develop and maintain. Execution tracing has proved itself to be a useful technology to gain a detailed knowledge of runtime behavior of software systems. However, the size and complexity of execution traces generated by modern embedded systems make manual trace analysis impossible. Therefore, software developers need tools to extract high-level system models from raw trace data. In this paper, we address the problem of mining task precedence graphs (TPG) from embedded system traces. A TPG can be helpful in performing several crucial software development and maintenance activities: understanding legacy systems, finding runtime bugs, and detect and diagnose anomalies in running systems. We rely on the recurrent nature of real-time systems to solve the TPG mining problem. We propose algorithms to train a TPG on a set of system traces, as well as an algorithm to detect anomalies in trace streams using a TPG. We evaluate our algorithms on industrial execution traces generated on production cars.

Temporal properties define the order of occurrence and timing constraints on event occurrence. Such specifications are important for safety-critical real-time systems. We propose a framework for automatically mining temporal properties that are in the form of timed regular expressions (TREs) from system traces. Using an abstract structure of the property, the framework constructs a finite state machine to serve as an acceptor. We analytically derive speedup for the fragment and confirm the speedup using empirical validation with synthetic traces. The framework is evaluated on industrial-strength safety-critical real-time applications using traces with more than 1 million entries.

Embedded systems often use digital filtering after analog-to-digital conversion when signal conditioning is required. However, digital filters are computationally demanding, making them unsuitable for low-power microcontrollers.

Developers of performance sensitive production software are in a dilemma: performance regression tests are too costly to run at each commit, but skipping the tests delays and complicates performance regression detection. Ideally, developers would have a system that predicts whether a given commit is likely to impact performance and suggests which tests to run to detect a potential performance regression. Prior approaches towards this problem require static or dynamic analyses that limit their generality and applicability. This paper presents an approach that is simple and general, and that works surprisingly well for real applications.

In a message-passing system (MPS), components communicate through messages. However, both the time and order in which messages are delivered depend on the execution environment. The resulting nondeterminism may lead to concurrency defects such as message races, making it difficult to thoroughly test and debug MPS. This paper presents a new framework for testing components of an MPS for faults that involve the violation of any implicit user-intended receiving order of messages. The framework purposefully assesses possible interleavings by reordering incoming messages before delivering them to the tested target component. We evaluate three methods to support the reordering process: the blocking method intercepts and blocks each message until all its dependencies have occurred, the buffering method buffers a message until either its dependencies are observed or a predefined timeout expires, and the adaptive buffering dynamically adjusts its flushing period. All three methods are implemented inside QNX Neutrino, a popular embedded real-time operating system. The evaluation shows a 4x speedup over random testing with minimal run time overhead and only a few kilobytes of memory overhead. These results confirms the effectiveness and capability of the framework to uncover faults in real-world applications.

Software specifications are useful for software validation, model checking, runtime verification, debugging, monitoring, etc. In context of safety-critical real-time systems, temporal properties play an important role. However, temporal properties are rarely present due to the complexity and evolutionary nature of software systems. We propose Timed Regular Expression Mining (TREM) a hosted tool for specification mining using timed regular expressions (TREs). It is designed for easy and robust mining of dominant temporal properties. TREM uses an abstract structure of the property; the framework constructs a finite state machine to serve as an acceptor. TREM is scalable, easy to access/use, and platform independent specification mining framework. The tool is tested on industrial strength software system traces such as the QNX real-time operating system using traces with more than 1.5 Million entries. The tool demonstration video can be accessed here: youtu.be/cSd_aj3_LH8.

Software systems with quality of service (QoS), such as database management systems and web servers, are ubiquitous. Such systems must meet strict performance requirements. Instrumentation is a useful technique for the analysis and debugging of QoS systems. Dynamic binary instrumentation (DBI) extracts runtime information to comprehend system's behavior and detect performance bottlenecks. However, existing DBI tools are intrusive; adding unacceptable delay to the program execution. Such delay alters the performance requirements and degrades the overall quality and the user experience of the system. Moreover, the delay may change the system behavior, thus, producing misleading run-time information. This paper presents QDIME, a QoS-aware dynamic binary instrumentation technique that respects system's performance requirements. QDIME takes a user-defined QoS threshold as an input and periodically gathers QoS feedback from the system under analysis to decide its instrumentation budget. We implemented QDIME on top of PIN, a popular DBI framework. We evaluated QDIME with Gzip, MySQL server, Apache HTTP server, and Redis. The experiments show that QDIME respects the user-defined QoS threshold and, thus, improves the performance of the monitored application by manifolds. QDIME is able to provide up to 100% instrumentation coverage with an average of 92% when compared to PIN. Moreover, QDIME reduces the slow-down factor of the instrumented application by 1.41, 5.67, and 10.26 folds for Sys-trace, Call-trace, and Branch-profile respectively. A release of QDIME is available for download at https://github.com/pansy-arafa/qdime.

Program assertions typically operate on available program state such as global and local variables. To support sophisticated assert statements such as invariants on control flow or inter-process communication patterns, developers must design and maintain supporting infrastructure. It is non-obvious how to realize this infrastructure: how to maintain the data, how to access it, how to use it in assertions, how to keep the overhead low enough for embedded systems, and how to manage assertions across a distributed system. This work demonstrates the utility of assertions on interaction history among distributed system components and solves the challenges of efficiently maintaining interaction data while providing an expressive interface for assertions. Our toolchain enables developers to program assertions on interaction history written in regular expressions that incorporate inter-process and inter-thread behavior amongst multiple components in a distributed system. We demonstrate that the interaction tracking and property verification systems incur negligible overhead, measured with several benchmarks. This work discusses our toolchain with a real-world safety-critical embedded system.

Modern systems are growing in complexity beyond deep comprehension of developers. Increasing difficulties of keeping software projects on schedule and increasing recall rates are symptoms of this development. Consequently, developers need new methods and tools to build embedded systems, such as tools that dynamically analyze systems and recover comprehensible specifications of particular aspects. In this paper, we address the problem of discovering temporal behavior of real-time systems by mining periodic task sets and their temporal characteristics from system execution traces. We leverage the periodic nature of real-time systems to achieve this goal in an automatic way. We propose PeTaMi (PEriodic TAsk MIner) - a novel approach and a tool to mine periodic tasks along with information on their periods and response time profiles from execution traces of real-time systems. PeTaMi embraces an important observation we make about operation of periodic tasks: their individual jobs are usually followed by intervals of task inactivity of a considerable duration. We evaluated PeTaMi on two case studies (unmanned aerial vehicle and a commercial car in operation) using traces containing tens of thousands of recorded execution events.

Many researchers have studied the behaviour of successful developers while debugging desktop software. In this paper, we investigate the embedded-software debugging by intermediate programmers through an exploratory study. The bugs are semantic low-level errors, and the participants are students who completed a real-time operating systems course in addition to five other programming courses. We compare between the behaviour involved in successful debugging attempts versus unsuccessful ones. We describe some characteristics of smooth and successful debugging behaviour.

Many software systems provide configuration options relevant to users, which are often called features. Features influence functional properties of software systems as well as non-functional ones, such as performance and memory consumption. Researchers have successfully demonstrated the correlation between feature selection and performance. However, the generality of these performance models across different hardware platforms has not yet been evaluated.

No abstract available.

Modern embedded systems are becoming more reliant on real-valued arithmetic as they employ mathematically complex vision algorithms and sensor signal processing. Double-precision floating point is the most commonly used precision in computer vision algorithm implementations. A single-precision floating point can provide a performance boost due to less memory transfers, less cache occupancy, and relatively faster mathematical operations on some architectures. However, adopting it can result in loss of accuracy. Identifying which parts of the program can run in single-precision floating point with low impact on error is a manual and tedious process. In this paper, we propose an automatic approach to identify parts of the program that have a low impact on error using shadow-value analysis. Our approach provides the user with a performance/error tradeoff, using which the user can decide how much accuracy can be sacrificed in return for performance improvement. We illustrate the impact of the approach using a well known implementation of Apriltag detection used in robotics vision. We demonstrate that an average 1.3x speedup can be achieved with no impact on tag detection, and a 1.7x speedup with only 4% false negatives.

Real-time embedded systems are a significant class of applications, poised to grow even further as automated vehicles and the Internet of Things become a reality. An important problem for these systems is to detect anomalies during operation. Anomaly detection is a form of classification, which can be driven by data collected from the system at execution time. We propose inter-arrival curves as a novel analytic modelling technique for discrete event traces. Our approach relates to the existing technique of arrival curves and expands the technique to anomaly detection. Inter-arrival curves analyze the behaviour of events within a trace by providing upper and lower bounds to their inter-arrival occurrence. We exploit inter-arrival curves in a classification framework that detects deviations within these bounds for anomaly detection. Also, we show how inter-arrival curves act as good features to extract recurrent behaviour that these systems often exhibit. We demonstrate the feasibility and viability of the fully implemented approach with an industrial automotive case study (CAN traces) as well as a deployed aerospace case study (RTOS kernel traces).

Software instrumentation is a key technique in many stages of the development process. Instrumentation is particularly important for profiling, debugging, performance evaluation, and security analysis of real-time and embedded systems. Unfortunately, typical software-based instrumentation methods, while useful to extract high-level information from programs, concentrate on preserving only logical correctness and are thus inadequate for time-sensitive applications for which timing must also be preserved.

Multi-mode systems work in configurations, but face the challenge of ensuring timing guarantees during mode changes. In a multi-mode system, a mode-change request occurs when the system wants to operate in a new mode, but is already running in one. One mode may include some tasks that are same as that of another mode. Therefore, the new mode may have tasks that are same as the old mode. Changing modes in such a way to skip some already completed tasks can decrease the workload of the new mode. Traditional protocols for changing modes always look forward in time to schedule tasks, although using already completed tasks may avoid re-executing them in the new mode. Reusing common tasks reduces the time to re-execute them while switching modes. In this paper, we introduce the concept and design considerations for a mode-change technique that may use completed tasks stored in checkpoints to avoid unnecessary re-execution and facilitate faster execution of new mode tasks. Through an example case-study, experimental results demonstrate that the overhead of using checkpoints is low, and using rollback facilitates faster execution of new mode tasks if completed tasks stored in checkpoints can be reused.

Software attestation seeks to verify the authenticity of a system without the aid of trusted hardware, and has important applications in the field of security. Such attestation schemes are of particular interest in the embedded domain, where simplicity and limited resources constrain more complex security solutions. At the same time, these properties enable attestation approaches that rely on predictable side-effects. Most software attestation schemes aim to verify the integrity of memory using a combination of cryptographic schemes, internal side-effects like TLB misses, and known timing constraints. However, little attention has been paid to leveraging non-traditional side-effects, in particular, externally observable side-effects such as power consumption. In this paper we introduce a method for software attestation using power consumption as the side-effect. We show how to circumvent the undecidable nature of program execution for this purpose and present a static compiler transformation which implements the technique. Our approach is less intrusive than traditional software attestation because the system does not require interruption to compute a cryptographic checksum. It is particularly well suited to real-time systems where consistent timing is more important than speed.

Summary Empirical systems research is facing a dilemma. Minor aspects of an experimental setup can have a significant impact on its associated performance measurements and potentially invalidate conclusions drawn from them. Examples of such influences, often called hidden factors, include binary link order, process environment size, compiler generated randomized symbol names, or group scheduler assignments. The growth in complexity and size of modern systems will further aggravate this dilemma, especially with the given time pressure of producing results. How can one trust any reported empirical analysis of a new idea or concept in computer science? DataMill is a community‐based services‐oriented open benchmarking infrastructure for rigorous performance evaluation. DataMill facilitates producing robust, reliable, and reproducible results. The infrastructure incorporates the latest results on hidden factors and automates the variation of these factors. DataMill is also of interest for research on performance evaluation. The infrastructure supports quantifying the effect of hidden factors, disseminating the research results beyond mere reporting. It provides a platform for investigating interactions and composition of hidden factors. This paper discusses experience earned through creating and using an open benchmarking infrastructure. Multiple research groups participate and have used DataMill. Furthermore, DataMill has been used for a performance competition at the International Conference on Runtime Verification (RV) 2014 and is currently hosting the RV 2015 competition. This paper includes a summary of our experience hosting the first RV competition. Copyright © 2015 John Wiley & Sons, Ltd.

Real-time Ethernet (RTE) is widely recognized for its potential to provide a unified communication backbone for next-generation heterogeneous distributed systems. However, most of the existing research in RTE technologies has traditionally focused on formal models and theoretical analyzes of timing properties, usually omitting the associated implementation challenges for testing them in practice. This gap between theory and practice prevents experimental validation of the claimed properties, which in turn hinders the pace of innovation and adoption of the technology in industrial settings. This paper aims at narrowing the theory-practice gap by characterizing a comprehensive open-source RTE framework that explores emerging challenges in real-time networking, including the provision of ultra-low latency and jitter, dynamic bandwidth management, and segmentation within large networks. This work integrates research on formal abstractions for dynamic time-division multiple access arbitration and technological insights from modern hardware infrastructure, and uses a representative distributed video processing application to provide reproducible evidence of the achieved properties in multihop Ethernet settings. By leveraging readily available technology and an open-source design, the proposed framework facilitates further exploration and experimental validation of properties that are beyond the scope of current commercial technologies, encouraging evidence-based discussions to accelerate development and adoption of new standards for next-generation industrial networks.

This work investigates selecting paths for communication flows when deploying a hard real-time application on a chip-multiprocessor system. This chip-multiprocessor system uses a priority-aware real-time network-on-chip interconnect between the processors. Given a mapping of the computation tasks onto the chip-multiprocessor, the problem we address in this work is to discover paths the communication flows take such that hard real-time deadlines of flows are met. Furthermore, we must ensure that deadlines are met even in the presence of direct and indirect interference from other flows sharing network links on the path. To achieve this, our algorithm utilizes a stage-level analysis for real-time communication to determine the impact of a network link being used by a flow, and its effect on other flows sharing the link. The path selection algorithm uses heuristics such as selecting links with least interference, and considering lower-priority flows when dedicating links to paths of higher-priority flows since an optimal one is intractable. The algorithm also considers constraints on the number of virtual channels at each router port in the network. The statistically significant experimental results show an improvement in schedulability by 5% and 12% over existing path selection algorithms such as Minimum Interference Routing and Widest Shortest Path algorithms, respectively. We also present a set-top box case study to further illustrate the benefits of using the proposed algorithm.

Automata-based models of embedded systems are useful and attractive for many reasons: they are intuitive, precise, at a high level of abstraction, tool independent and can be simulated and analyzed. They also have the advantage of facilitating readability and system comprehension in the case of large systems. This paper proposes an approach for mining automata-based models from input/output execution traces of embedded control systems. The models mined by our approach are hybrid automata models, which capture discrete as well as continuous system behavior. Specifically this paper proposes a framework for analyzing multiple input/output traces by identifying steps like segmentation, clustering, generation of event traces, and automata inference. The framework is general enough to admit multiple techniques or future enhancements of these steps. We demonstrate the power of the framework by using some specific existing methods and tools in two case studies. Our initial results are encouraging and should spur further research in the domain.

Security and privacy are growing concerns in modern embedded software, given the increasing level of connectivity as well as complexity and features in embedded devices. Use of cryptographic techniques is often a requirement on which the security of the device relies. However, important challenges arise when potential attackers have physical access to the device. Side-channel analysis, including simple power analysis (SPA), is a class of powerful non-intrusive attacks that are suitable for adversaries with physical access to the device. Countermeasures exist, but they typically involve a considerable performance penalty, and some of them in turn introduce a vulnerability to induced fault attacks. In this work, we present several new efficient cryptographic exponentiation algorithms that work by splitting the exponent in two halves for simultaneous processing while using special representations derived from signed-digit encoding that improve computational efficiency. A key detail in the design of these algorithms is that they are compatible with the idea of buffering the operations to provide resistance to SPA. Experimental results are presented, including implementations of the proposed methods with both modular integer exponentiation and elliptic curve (ECC) scalar multiplication. We also performed statistical analysis of the traces, showing that trace segments for different exponent bits are statistically indistinguishable. Our proposed techniques also exhibit better resistance against fault attacks and combined fault and side-channel attacks, compared to previous SPA-resistant techniques.

With the growing demand in embedded systems, safety and non-safety critical parts are integrated together although guaranteeing safety is a hard problem to tackle due to the complexity of possible interactions between components involving communication. However, it is sufficiently recognized that separation of computation and communication can reduce the complexity of guaranteeing safety involved in interactions between components. In this work, we propose to use component interfaces derived from periodic resource supplies that can meet the demand of components experiencing bounded delays. The advantage of using interfaces is to provide minimal information of components without requiring the entire task specifications to generate a multi-mode communication schedule. We use integer linear programming to find assignments in generating schedules that are guaranteed to have low average mode-change delay. A video monitoring case study demonstrates the advantages on using our approach in generating communication schedules.

Real-time embedded programs are time sensitive and, to trace such programs, the instrumentation mechanism must honor the programs' timing constraints. We present a time-aware instrumentation technique that injects program code with slack-based conditional instrumentation. The central idea is to execute instrumentation code only when its execution does not increase the worst-case execution time beyond a program's deadline. This occurs at run-time. Unlike previous efforts, this work allows instrumenting on the path that results in the worst-case execution time of the program. We propose a software, and a hardware method of allowing for slack-based conditional instrumentation. We evaluate and compare these two alternatives using a common benchmark suite for real-time systems. Our results show that, on average, the two proposed methods achieve 57% and 80% instrumentation coverage, respectively, compared to only a 3% coverage by previous work.

Changing the development environment can have severe impacts on the system behavior such as the execution-time performance. Since it can be costly to migrate a software application, engineers would like to predict the performance parameters of the application under the new environment with as little effort as possible. In this paper, we concentrate on model-driven development and provide a methodology to estimate the execution-time performance of application models under different toolchains. Our approach has low cost compared to the migration effort of an entire application. As part of the approach, we provide methods for characterizing model-driven applications, an algorithm for generating application-specific microbenchmarks, and results on using different methods for estimating the performance. In the work, we focus on SCADE as the development toolchain and use a Cruise Control and a Water Level application as case studies to confirm the technical feasibility and viability of our technique.

The goal of runtime monitoring is to inspect the well-being of a system by employing a monitor process that reads the state of the system during execution and evaluates a set of properties expressed in some specification language. The main challenge in runtime monitoring is dealing with the costs imposed in terms of resource utilization. In the context of cyber-physical systems, it is crucial for a software monitoring solution to be time predictable to improve scheduling, as well as support composition of monitoring solutions with an overall predictable behavior. Moreover, a small memory footprint is often required in components of cyber-physical systems, especially in deeply embedded systems. In this article, we propose a novel control-theoretic software monitoring solution for coordinating time predictability and memory utilization in runtime monitoring of systems that interact with the physical world. The controllers attempt to reduce monitoring jitter and maximize memory utilization while simultaneously ensuring the soundness of evaluation of properties. For systems where multiple properties are required to be monitored simultaneously, we construct a buffer sharing mechanism in which controllers dynamically share the memory space to negate the effect of bursts of environment actions, thus reducing jitter due to transient high loads. To validate our design choices, we present three case studies: (1) a Bluetooth mobile payment system, which shows a sporadic rate of events during peak hours; (2) a laser beam stabilizer for target tracking, and (3) a monitoring system for air/fuel ratio in a car engine exhaust and the CAM inlet position in the engine’s cylinders. The experimental results of the case studies demonstrate up to 40% improvement in time predictability of the monitoring solution when compared to a basic event-triggered approach. Moreover, memory utilization reaches an average of 90% when using our dynamic buffer resizing mechanism.

A key problem in designing multi-mode real-time systems is the generation of schedules to reduce the complexities of transforming the model semantics to code. Moreover, distributed multi-mode applications are prone to suffer from delays incurred during mode changes. We therefore aim to generate communication schedules that have low average mode-change delay for multi-mode real-time distributed applications. In this paper, we use optimization constraints associated to timing requirements to generate state-based schedules for multi-mode communication systems, and illustrate the workflow for generating schedules from specifications through a real-time video monitoring case-study. Our experiments in the case-study demonstrate that schedules generated using the proposed method reduce the average mode-change delay in relation to a randomized algorithm and the well-known EDF scheduling algorithm.

Given a set of historic good traces, trace-based anomaly detection deals with the problem of determining whether or not a specific trace represents a normal execution scenario. Most current approaches mainly focus on application areas outside of the embedded systems domain and thus do not take advantage of the intrinsic properties of this domain.

With the growth of complexity in the embedded domain, the use of distributed systems to support multiple realtime applications has become commonplace. These applications may share processor and network resources, and real-time scheduling policies can guarantee that these applications do not interfere with each other's ability to meet their temporal constraints. We believe that these applications should also be able to transparently share services and chains of services, without the coupling that such sharing typically implies. To solve this problem, we propose D-RES, a resource management system that guarantees temporal isolation between service-sharing applications in a distributed system. D-RES transparently tracks which application uses which service, billing the correct application even in case of nested service calls. We implemented D-RES, and demonstrate its ability to isolate service-sharing applications even in case of overload.

Power efficiency has been one of the main objectives of hardware design in the last two decades. However, with the recent explosion of mobile computing and the increasing demand for green data centers, software power efficiency has also risen to be an equally important factor. We argue that most classic concurrency control algorithms were designed in an era when power efficiency was not an important dimension in algorithm design. Such algorithms are applied to solve a wide range of problems from kernel-level primitives in operating systems to networking devices and web services. These primitives and services are constantly and heavily invoked in any computer system and by larger scale in networking devices and data centers. Thus, even a small change in their power spectrum can make a huge impact on overall power consumption in long periods of time. This paper focuses on the classic producer-consumer problem. First, we study the power efficiency of different existing implementations of the producer-consumer problem. In particular, we present evidence that these implementations behave drastically differently with respect to power consumption. Secondly, we present a dynamic algorithm for the multiple producer-consumer problem, where consumers in a multicore system use learning mechanisms to predict the rate of production, and effectively utilize this prediction to attempt to latch onto previously scheduled CPU wake-ups. Such group latching results in minimizing the overall number of CPU wakeups and in effect, power consumption. We enable consumers to dynamically reserve more pre-allocated memory in cases where the production rate is too high. Consumers may compete for the extra space and dynamically release it when it is no longer needed. Our experiments show that our algorithm provides up to 40% decrease in the number of CPU wakeups, and 30% decrease in power consumption. We validate the scalability of our algorithm with an increasing number of consumers.

Traditional compilers ignore processor specifications, thousands of pages of which are available for modern processors. To bridge this gap, em-SPADE analyzes processor specifications and creates processor-specific rules to reduce low-level programming errors. This work shows the potential of automatically analyzing processor- and other hardware specifications to detect low-level programming errors at compile time.

mTags is an efficient mechanism that augments inter-thread messages with lightweight metadata. We introduce and discuss a case study that we have conducted in the use of mTags for realizing a kind of mandatory security. Although mTags can be implemented for any message passing thread-based system, we consider an implementation of it in the POSIX-compliant QNX Neutrino, a commercial microkernel-based system. The approach to mandatory security that we adopt is Usable Mandatory Integrity Protection, which has been proposed in recent research. We call our adaptation of Usable Mandatory Integrity Protection using mTags, μMIP. We discuss the challenges we faced, and our design and implementation that overcomes these challenges. We discuss the performance of our implementation for well-established benchmarks. We conclude with the observation that mTags can be useful and practical to realize mandatory security in realistic systems. Copyright © 2013 John Wiley & Sons, Ltd.

Safety-critical distributed real-time applications operating with strict temporal constraints rely on deterministic networks with low latency and jitter. Traditional fieldbus systems deliver these guarantees, but they have limited compatibility with open infrastructures and limited support for high transmission rates. Ethernet technology rises as a low-cost, high-speed, and ubiquitous alternative to fieldbus systems; however, standard Ethernet requires special arbitration mechanisms to support real-time traffic because of the standard's inherent nondeterministic behavior. This work explores the associated tradeoffs for three different solutions for real-time communication over switched Ethernet. The paper presents and discusses three architectures that modify different network components, enhancing them with additional customized modules to support time-triggered communication based on Network Code. Using the NetFPGA platform as the unified prototyping technology for all the components, we developed an open-source framework to characterize each solution using experimental data for the latency, jitter, throughput, robustness, and cost in logical resources. The results provide insights to help future developers of real-time communication technology decide which components to modify according to the requirements of their applications.

Research has shown that correctly conducting and analysing computer performance experiments is difficult. This paper investigates what is necessary to conduct successful computer performance evaluation by attempting to repeat a prior experiment: the comparison between two Linux schedulers.

For more than one decade, researchers have considered Ethernet as a natural replacement to legacy fieldbuses in modern distributed applications. However, Ethernet components require special modifications and hardware support to provide strict timing guarantees. In general, the high-cost of deploying hardware components limits the experimental validation of proposed solutions in real-world applications. Despite the vast literature, only a few solutions report real implementations, and they are all closed to the research community, hindering further development for constantly evolving applications. This paper introduces Atacama, an on-going effort on deploying the first hardware-accelerated and open-source framework for mixed-criticality communication on multi-hop networks. Specialized modules exploit the principles of traditional fieldbus systems to coordinate communication tasks on real-time stations, and can be easily integrated to and coexist with Commercial Off The Shelf (COTS) devices operating with best-effort traffic. Experimental characterization of implemented prototypes report minimal jitter on 1Gbps links, and show that real-time guarantees are resilient to injected best-effort traffic. The framework is available as an open-source project, enabling researchers to verify the results, explore, test, and deploy new networking solutions for modern distributed systems in real-world scenarios.

Real-time applications have deadline constraints. The system should provision sufficient resources for the application to meet the deadlines, and use supply and demand bound functions to analyze the schedulability of workloads. The concept of the demand bound function describes the upper bound on the resources required by the application, while the supply-bound function specifies the lower bound on the resources supplied to the tasks. If the system provides fewer resources than required, the application will experience an overload. Most work concentrates on designing systems that cannot experience short periods of overloads. This work explores resource provisioning for control applications that can tolerate overloads. It introduces analysis techniques for supply and demand bound functions that specifically consider overloads and delays in a periodic resource model. With this extended model, the work addresses three problems: (1) determine the worst-case delay for a given resource demand and supply under a periodic resource model, (2) find a periodic resource supply for a given workload and worst-case tolerable delay, and (3) for a control system with a given robustness criterion, identify a periodic resource supply with a worst-case delay.

Program analysis tools are essential for understanding programs, analyzing performance, and optimizing code. Some of these tools use code instrumentation to extract information at runtime. The instrumentation process can alter program behavior such as timing behavior and memory consumption. Time-sensitive programs, however, must meet specific timing constraints and thus require that the instrumentation process, for instance, bounds the timing overhead. Time-aware instrumentation techniques try to honor the timing constraints of such programs. All previous techniques, however, support only static source-code instrumentation methods. Hence, they become impractical beyond microcontroller code for instrumenting large programs along with all their library dependencies. In this work, we propose DIME, a time-aware dynamic binary instrumentation technique that adds an adjustable bound on the timing overhead to the program under analysis. We implement DIME using the dynamic instrumentation framework, Pin. Quantitative evaluation of the three implementation alternatives shows an average reduction of the instrumentation overhead by 12, 7, and 3 folds compared to native Pin. Instrumenting the VLC media player and a laser beam stabilization experiment demonstrate the practicality and scalability of DIME.

Ethernet is widely recognized as an attractive networking technology for modern distributed real-time systems. However, standard Ethernet components require specific modifications and hardware support to provide strict latency guarantees necessary for safety-critical applications. Although this is a well-stated fact, the design of hardware components for real-time communication remains mostly unexplored. This becomes evident from the few solutions reporting prototypes and experimental validation, which hinders the consolidation of Ethernet in real-world distributed applications. This paper presents Atacama, the first open-source framework based on reconfigurable hardware for mixed-criticality communication in multi-segmented Ethernet networks. Atacama uses specialized modules for time-triggered communication of real-time data, which seamlessly integrate with a standard infrastructure using regular best-effort traffic. Atacama enables low and highly predictable communication latency on multi-segmented 1Gbps networks, easy optimization of devices for specific application scenarios, and rapid prototyping of new protocol characteristics. Researchers can use the open-source design to verify our results and build upon the framework, which aims to accelerate the development, validation, and adoption of Ethernet-based solutions in real-time applications.

Runtime verification is a monitoring technique to gain assurance about well-being of a program at run time. Most existing approaches use sequential monitors; i.e., when the state of the program with respect to an event of interest changes, the monitor interrupts the program execution, evaluates a set of logical properties, and finally resumes the program execution. In this paper, we propose a GPU-based method for design and implementation of monitors that enjoy two levels of parallelism: the monitor (1) works along with the program in parallel, and (2) evaluates a set of properties in a parallel fashion as well. Our parallel monitoring algorithms effectively exploit the many-core platform available in the GPU. In addition to parallel processing, our approach benefits from a true separation of monitoring and functional concerns, as it isolates the monitor in the GPU. Our method is fully implemented and experimental results show significant reduction in monitoring overhead, monitoring interference, and power consumption due to leveraging the GPU technology.

One of the hardest aspects of embedded software development is that of debugging, especially when faulty behavior is observed at the production or deployment stage. Non-intrusive observation of the system's behavior is often insufficient to infer the cause of the problem and identify and fix the bug. In this work, we present a novel approach for non-intrusive program tracing aimed at assisting developers in the task of debugging embedded systems at deployment or production stage, where standard debugging tools are usually no longer available. The technique is rooted in cryptography, in particular the area of side-channel attacks. Our proposed technique expands the scope of these cryptographic techniques so that we recover the sequence of operations from power consumption observations (power traces). To this end, we use digital signal processing techniques (in particular, spectral analysis) combined with pattern recognition techniques to determine blocks of source code being executed given the observed power trace. One of the important highlights of our contribution is the fact that the system works on a standard PC, capturing the power traces through the recording input of the sound card. Experimental results are presented and confirm that the approach is viable.

This work addresses the challenge of computing worst-case response times of hard real-time applications deployed on multiprocessor systems. In particular, the worst-case response time analysis (WCRTA) focuses on the communication between distributed tasks of hard real-time applications. The proposed WCRTA models the communication as a pipelined communication resource model. This model incorporates the effect of pipelining, and the parallel transmission of data. Applications of such a model include multiprocessor systems that use complex interconnects such as network-on-chips (NoC)s with priorities. In this paper, we present an exponential analysis, and a polynomial analysis, and prove its correctness. As an application, we apply the pipelined communication resource model to priority-aware NoCs, and we compare the proposed analyses against prior analysis techniques. Our experimental evaluation on two instances of 4 × 4 and 8 × 8 NoCs with 512,000 synthetic benchmarks shows 48.3% and 66.7% improvement in schedulability for the two NoC sizes over prior work.

Tracing is a well-established method for debugging programs. Current approaches aim only at preserving functional correctness during the instrumentation. Preservation of functional correctness is a necessary feature of all instrumentation tools. However, few existing instrumentation tools preserve extra-functional properties of a program. Specific classes of software are unable to leverage software instrumentation; e.g., timing for real-time systems, memory consumption for embedded software, and tracing bandwidth for on-board software. We present the first instrumentation framework, INSTEP, that preserves logical correctness and a rich set of extra-functional properties. INSTEP derives instrumentation alternatives based on the developer's instrumentation intent (II), abstracts the program and prunes the search space, and then instruments the program based on constraints and cost models of competing properties. We demonstrate and experiment with a fully automated framework of INSTEP with different IIs and extra-functional properties.We also experiment with a large automotive case study to show the scalability of INSTEP.

We introduce the tool RiTHM (Runtime Time-triggered Heterogeneous Monitoring). RiTHM takes a C program under inspection and a set of LTL properties as input and generates an instrumented C program that is verified at run time by a time-triggered monitor. RiTHM provides two techniques based on static analysis and control theory to minimize instrumentation of the input C program and monitoring intervention. The monitor's verification decision procedure is sound and complete and exploits the GPU many-core technology to speedup and encapsulate monitoring tasks.

Empirical systems research is facing a dilemma. Minor aspects of an experimental setup can have a significant impact on its associated performance measurements and potentially invalidate conclusions drawn from them. Examples of such influences, often called hidden factors, include binary link order, process environment size, compiler generated randomized symbol names, or group scheduler assignments. The growth in complexity and size of modern systems will further aggravate this dilemma, especially with the given time pressure of producing results. So how can one trust any reported empirical analysis of a new idea or concept in computer science?

Schedulability analysis of hierarchical real-time embedded systems involves defining interfaces that represent the underlying system faithfully and then compositionally analyzing those interfaces. Whereas commonly used abstractions, such as periodic and sporadic tasks and their interfaces, are simple and well studied, results for more complex and expressive abstractions and interfaces based on task graphs and automata are limited. One contributory factor may be the hardness of compositional schedulability analysis with task graphs and automata. Recently, conditional task models, such as the recurring branching task model, have been introduced with the goal of reaching a middle ground in the trade-off between expressivity and ease of analysis. Consequently, techniques for compositional analysis with conditional models have also been proposed, and each offer different advantages. In this work, we revisit those techniques, compare their advantages using an automotive case study, and identify limitations that would need to be addressed before adopting these techniques for use with real-world problems.

We present a path selection algorithm that is used when deploying hard real-time traffic flows onto a chip-multiprocessor system. This chip-multiprocessor system uses a priority-based real-time network-on-chip interconnect between the multiple processors. The problem we address is the following: given a mapping of the tasks onto a chip-multiprocessor system, we need to determine the paths that the traffic flows take such that the flows meet there deadlines. Furthermore, we must ensure that the deadline is met even in the presence of direct and indirect interference from other flows sharing network links on the path. To achieve this, our algorithm utilizes a link-level analysis to determine the impact of a link being used by a flow, and its affect on other flows sharing the link. Our experimental results show that we can improve schedulability by about 8% and 15% over Minimum Interference Routing and Widest Shortest Path algorithms, respectively.

Time-triggered runtime verification aims at tackling two defects associated with runtime overhead: unboundedness and unpredictability. In this approach, a monitor runs in parallel with the program under inspection and periodically samples the program state to evaluate a set of properties. The fact that the monitoring tasks place only at predictable time ticks makes the approach predictable and especially suitable for embedded systems.

Instrumentation is a valuable technique to gain insight into a program's behavior. Safety-critical real-time embedded applications are time sensitive and so instrumentation techniques for this domain must especially consider timing. This work establishes the basis for measuring the effectiveness of approaches for time-aware instrumentation in addition to coverage. We define the ETP shift effectiveness metric and define its optimality criterion. We identify locations in the program where program transformation techniques can be applied to increase the instrumentability of the program. We subsequently use the proposed metric to evaluate two transformation methods that improve the effectiveness and coverage of current techniques for time-aware instrumentation by a factor of five.

Runtime monitoring aims at analyzing the well-being of a system at run time in order to detect errors and steer the system towards a healthy behavior. Such monitoring is a complementary technique to other approaches for ensuring correctness, such as formal verification and testing. In time-triggered runtime monitoring, a monitor runs as a separate process in parallel with an application program under scrutiny and samples the program's state periodically to evaluate a set of properties. Applying this technique in a computing system results in obtaining bounded and predictable overhead. Gaining such characteristics for overhead is highly desirable for designing and engineering time-critical applications, such as safety-critical embedded systems. However, a time-triggered monitor requires certain synchronization features at operating system level and may suffer from various concurrency and synchronization dependencies and overheads as well as possible unreliability of synchronization primitives in a real-time setting. In this paper, we propose a new method, where the program under inspection is instrumented, so that it self-samples its state in a periodic fashion without requiring assistance from an external monitor or internal timer. We call this technique time-triggered self-monitoring. First, we formulate an optimization problem for minimizing the number of points in a program, where self-sampling instrumentation instructions must be inserted. We show that this problem is NP-complete. Consequently, we propose a SAT-based solution and a heuristic to cope with the exponential complexity. Our experimental results show that a time-triggered self-monitored program performs significantly better than the same program monitored by an external time-triggered monitor.

Modern industrial networked control systems(NCSs) tend to be complicated and have dynamic workload by holding a variety of applications via a shared network. The static network scheduling algorithms fit most NCSs due to their deterministic characteristics and timing guarantees, but they cannot handle dynamic workloads for lack of making on the-fly decisions. The conditional state-based scheduling adds the dynamism in the static scheduling algorithms by automata or more explicitly state chart like formalisms with conditional transitions. In this paper, we propose CSS scheme that applies the conditional state-based scheduling to dynamically schedule different applications in the industrial NCSs. CSS aims at the time-triggered network in the NCSs and uses time division multiple access (TDMA) method to let the applications access the network. To enhance the scalability of the NCSs, we design CSS as a decentralized scheme where each application in NCSs has a local scheduler to make its schedule decisions. Appropriate algorithms are applied to ensure the scheduling decisions made by the local schedulers are consistent and the desired system performance can be achieved. Simulation results demonstrate the effectiveness of the proposed scheme compared to the static TDMA used in real-time networks.

State consistency in safety-critical distributed systems is mandatory for synchronizing distributed decisions as found in dynamic time division multiple access (TDMA) schedules in the presence of faults. A TDMA schedule that supports networked systems making decisions at run time is sensitive to transient faults, because stations can make incorrect local decisions at run time and cause state inconsistency and collisions. We refer to this type of TDMA schedule as a dynamic TDMA schedule. Faulty decisions are especially undesirable for safety-critical systems with hard real-time constraints. Hence, real-time communication schedules must have the capability of detecting state inconsistency within a fixed amount of time. In this paper, we show through experimentation that state inconsistency is a real problem, and we propose a solution for resolving state inconsistency in TDMA schedules.

In this paper, we present a notion of observability and controllability in the context of software testing and debugging. Our view of observability is based on the ability of developers, testers, and debuggers to trace back a data dependency chain and observe the value of a variable by starting from a set of variables that are naturally observable (e.g., input/output variables). Likewise, our view of controllability enables one to modify and control the value of a variable through a data dependency chain by starting from a set of variables that can be modified (e.g., input variables). Consequently, the problem that we study in this paper is to identify the minimum number of variables that have to be made observable/controllable in order for a tester or debugger to observe/control the value of another set of variables of interest, given the source code. We show that our problem is an instance of the well-known abstract diagnosis problem, where the objective is to find the minimum number of faulty components in a digital circuit, given the system description and value of input/output variables. We show that our problem is NP-complete even if the length of data dependencies is at most 2. In order to cope with the inevitable exponential complexity, we propose a mapping from the general problem, where the length of data dependency chains is unknown a priori, to integer linear programming. Our method is fully implemented in a tool chain for MISRA-C compliant source codes. Our experiments with several real-world applications show that in average, a significant number of debugging points can be reduced using our methods. This result is our motivation to apply our approach in debugging and instrumentation of embedded software, where changes must be minimal as they can perturb the timing constraints and resource consumption. Another interesting application of our results is in data logging of non-terminating embedded systems, where axillary data storage devices are slow and have limited size.

Debugging is an important phase in the embedded software development cycle because of its high proportion in the overall cost in the product development. Debugging is difficult for real-time applications as such programs are time-sensitive and must meet deadlines in often a resource constrained environment.

We propose a technique to automatically synthesize programs and schedules for hard real-time distributed (embedded) systems from synchronous data-flow models. Our technique connects the SynDEx scheduling tool and the Network Code toolchain in a seamless flow of automatic model transformations that go all the way from specification to implementation.

A real-time communication medium must provide a special coordination mechanism to guarantee bounded communication delays. Implementing this mechanism in software offers flexibility but reduces reliability and performance. On the other hand, customized hardware solutions deliver high throughput and predictability, but they increase the implementation cost and are unable to adapt to the specific needs of individual applications. In this work, we introduce a switch that implements a programmable dedicated time-triggered packet switching mechanism on top of Ethernet. The switch, called the Network Code Switch bases on the NetFPGA system and executes flexible but verifiable state-based schedules encoded in the Network Code programming language. This permits the user to tailor the communication behavior to the needs of the distributed application with verifiable performance. We discuss our experience starting at the designing to the implementation of the prototype, and describe how we exploited modularity and code reutilization to reduce the implementation costs and increase the flexibility of the architecture. We also validate our design by evaluating the overhead and throughput of the implemented prototype.

Modular robots are a powerful concept for robotics. A modular robot consists of many individual modules so it can adjust its configuration to the problem. However, the fact that a modular robot consists of many individual modules makes it a highly distributed, highly concurrent real-time system, which are notoriously hard to program. In this work, we present our programming framework for writing control applications for modular robots. The framework includes a toolset that allows a model-based programming approach for control application of modular robots with code generation and verification. The framework is characterized by the following three features. First, it provides a complex programming model that is based on standard finite state machines extended in syntax and semantics to support communication, variables, and actions. Second, the framework provides compositionality at the hardware and at the software level and allows building the modular robot and its control application from small building blocks. And third, the framework supports formal verification of the control application to aid the gait and task developer in identifying problems and bugs before the deployment and testing on the physical robot.

For its high overall cost during product development, program debugging is an important aspect of system development. Debugging is a hard and complex activity, especially in time-sensitive systems which have limited resources and demanding timing constraints. System tracing is a frequently used technique for debugging embedded systems. A specific use of system tracing is to monitor and debug control-flow problems in programs. However, it is difficult to implement because of the potentially high overhead it might introduce to the system and the changes which can occur to the system behavior due to tracing. To solve the above problems, in this work, we present a sampling-based approach to execution monitoring which specifically helps developers debug time-sensitive systems such as real-time applications. We build the system model and propose three theorems to determine the sampling period in different scenarios. We also design seven heuristics and an instrumentation framework to extend the sampling period which can reduce the monitoring overhead and achieve an optimal tradeoff between accuracy and overhead introduced by instrumentation. Using this monitoring framework, we can use the information extracted through sampling to reconstruct the system state and execution paths to locate the deviation.

Hybrid systems have emerged as an appropriate formalism to model embedded systems as they capture the theme of continuous dynamics with discrete control. Under this paradigm, distributed embedded systems can be modeled as a network of communicating hybrid automata. Several techniques for code generation from these models have also been proposed and commercially implemented. Providing formal guarantees of the generated code with respect to the model, however, has turned out to be a hard problem. While the model is set in continuous time with concurrent execution and instantaneous switching, the code running on an inherently discrete platform, can be affected by the sampling interval, round-off errors, and communication delays between the sensor, controller, and actuators. Consequently, semantic differences between the model and its code can arise with potentially different system behavior. This paper proposes a criterion for faithful implementation of the hybrid-systems model with a focus on its switching semantics. We discuss different techniques to ensure a faithful implementation of the model, and test the feasibility of our concepts by implementing a model heater system. In this heater case study, we successfully eliminate all fault transitions and, thereby, generate code with correct behavior complying with the specification.

Software instrumentation is a key technique in many stages of the development process. It is particularly important for debugging embedded systems. Instrumented programs produce data traces which enable the developer to locate the origins of misbehaviors in the system under test. However, producing data traces incurs runtime overhead in the form of additional computation resources for capturing and copying the data. The instrumentation may therefore interfere with the system's timing and perturb its behavior. In this work, we propose an instrumentation technique for applications with temporal constraints, specifically targeting background/foreground or cyclic executive systems. Our framework permits reasoning about space and time and enables the composition of software instrumentations. In particular, we propose a definition for trace reliability, which enables us to instrument real-time applications which aggressively push their time budgets. Using the framework, we present a method with low perturbation by optimizing the number of insertion points and trace buffer size with respect to code size and time budgets. Finally, we apply the theory to two concrete case studies: we instrument the OpenEC firmware for the keyboard controller of the One Laptop Per Child project, as well as an implementation of a flash file system.

Complex real-time embedded systems should be compositional and deterministic in the resource, time, and value domains. Determinism eases the engineering of correct systems and compositionality simplifies the assembly of complex systems out of smaller modules. This paper describes the PEACOD framework that is developed to support deterministic behavior for resource consumption, value passing, and timing. The paper introduces the notions of determinism in the context of the resource, value, and temporal domains, and present the resource-scope language construct that can be used to program such deterministic behaviors. Furthermore, the paper also provides semantics for the resource scope construct and uses these semantics to show that the program behavior is preserved under composition. The paper briefly describes the current implementation of PEACOD.

During the system development, developers often must correct wrong behavior in the software---an activity colloquially called program debugging. Debugging is a complex activity, especially in real-time embedded systems because such systems interact with the physical world and make heavy use of interrupts for timing and driving I/O devices.

Software instrumentation is a key technique in many stages of the development process. It is of particular importance for debugging embedded systems. Instrumented programs produce data traces which enable the developer to locate the origins of misbehaviours in the system under test. However, producing data traces incurs runtime overhead in the form of additional computation resources for capturing and copying the data. The instrumentation may therefore interfere with the system's timing and perturb its behavior. In the worst case, this perturbation leads to new system behaviours that prevent the developer from locating the original misbehaviours. In this work, we propose an instrumentation technique for applications with temporal constraints, specifically targetting background/foreground systems. Our framework permits reasoning about space and time for software instrumentations. In particular, we propose a definition for trace reliability, which enables us to instrument real-time applications which aggressively push their time budgets. Using the framework, we present a method with low perturbation by optimizing the number of insertion points and trace buffer size for code size and time budgets. Finally, we apply the theory to a concrete case study and instrument the OpenEC firmware for the keyboard controller of the One Laptop Per Child project.

Distributed real-time applications implement distributed applications with timeliness requirements. Such systems require a deterministic communication medium with bounded communication delays. Ethernet is a widely used commodity network with many appliances and network components and represents a natural fit for real-time application; unfortunately, standard Ethernet provides no bounded communication delays. Conditional state-based communication schedules provide expressive means for specifying and executing with choice points, while staying verifiable. Such schedules implement an arbitration scheme and provide the developer with means to fit the arbitration scheme to the application demands instead of requiring the developer to tweak the application to fit a predefined scheme. An evaluation of this approach as software prototypes showed that jitter and execution overhead may diminish the gains. This work successfully addresses this problem with a synthesized soft processor. We present results around the development of the soft processor, the design choices, and the measurements on throughput and robustness.

Distributed real-time applications implement distributed applications with timeliness requirements. Such systems require a deterministic communication medium with bounded communication delays. Ethernet is a widely used commodity network with a large number of appliances and network components and represents a natural fit for real-time application; unfortunately, standard Ethernet provides no bounded communication delays. Network Code Processor is a soft processor implementation for real-time communication on Ethernet. The system provides a smart network-card functionality and can be seen as a co-processor for time-triggered communication. Its most distinguishing feature, the programmability of the processor via the Network Code language, allows developers to write adaptive but verifiable communication schedules tailored to the application needs. In this work we present results around the development of the soft processor, discuss the specific challenges of how to build a reliable and fast communication system, the tradeoffs involved when moving from a generic software prototype to a programmable hardware implementation.

Conditional real-time task models, which are generalizations of periodic, sporadic, and multi-frame tasks, represent real world applications more accurately. These models can be classified based on a tradeoff in two dimensions - expressivity and hardness of schedulability analysis. In this work, we introduce a class of conditional task models and derive efficient schedulability analysis techniques for them. These models are more expressive than existing models for which efficient analysis techniques are known. In this work, we also lay the groundwork for schedulability analysis of hierarchical scheduling frameworks with conditional task models. We propose techniques that abstract timing requirements of conditional task models, and support compositional analysis using these abstractions.

A critical resource in a distributed real-time system is its shared communication medium. Unrestrained concurrent access to the network can lead to collisions that reduce the system's reliability. Therefore in this area, one goal is to develop effective models for coordinating and controlling access to the shared medium and its channels.\nNetwork Code is a verifiable, executable model for coordinating and controlling access to a shared communication medium in a distributed real-time system. In this paper, we investigate the problem of building an application by composing multiple Network Code programs. To reason about the composition, we model Network Code programs as Tree Schedules (TS) and then consider the composition of schedules that describe how the network is accessed by different applications. Specifically, we first define the notions of compatibility and composability of tree schedules, and then provide algorithms for their composition and reason about overhead of composition. We illustrate the techniques by considering the composition of two control applications.

The design of safety-critical systems has typically adopted static techniques to simplify error detection and fault tolerance. However, economic pressure to reduce costs is exposing the limitations of those techniques in terms of efficiency in the use of system resources. In some industrial domains, such as the automotive, this pressure is too high, and other approaches to safety must be found, e.g., capable of providing some kind of fault tolerance but with graceful degradation to lower costs, or also capable of adapting to instantaneous requirements to better use the computational/communication resources.

Distributed hard real-time systems require predictable communication at the network level and verifiable communication behavior at the application level. At the network level, communication between nodes must be guaranteed to happen within bounded time and one common approach is to restrict the network access by enforcing a time-division multiple access (TDMA) schedule. At the application level, the application's communication behavior should be verified to ensure that the application uses the predictable communication in the intended way. Network code is a domain-specific programming language to write a predictable verifiable distributed communication for distributed real-time applications. In this paper, we present the syntax and semantics of network code, how we can implement different scheduling policies, and how we can use tools such as model checking to formally verify the properties of network code programs. We also present an implementation of a runtime system for executing network code on top of RTLinux and measure the overhead incurred from the runtime system.

Distributed real-time systems require a predictable and verifiable mechanism to control the communication medium. Current real-time communication protocols are typically in-dependent of the application and have intrinsic limitations that impede customizing or optimizing them for the application. Therefore, either the developer must adapt her application and work around these subtleties or she must limit the capabilities of the application being developed.Network Code, in contrast, is a more expressive and exible model that specifies real-time communication schedules as programs. By providing a programmable media access layer on the basis of TDMA, Network Code permits creating application-specific protocols that suit the particular needs of the application. However, this gain in exibility also incurs additional costs such as increased communication and run-time overhead. Therefore, engineering an application with network code necessitates that these costs are analyzed, quantified, and weighted against the benefit.In this work, we propose a framework to analyze network-code programs for commonly used metrics such as overhead, schedulability, and average waiting time. We introduce Timed Tree Communication Schedules, based on timed automata to model such programs and define metrics in the context of deterministic and probabilistic communication schedules. To demonstrate the utility of our framework, we study an inverted pendulum system and show that we can decrease the cumulative numeric error in the model's implementation through analyzing and improving the schedule based on the presented metrics.

Embedded systems are usually an integral component of a larger system and are used to control and/or directly monitor this system by using special hardware devices. The complexity of the whole system, which the embedded control system monitors, increases steadily. Consequently, the initial version of the control software that is used at the time of deployment may be inadequate and may need to be updated. Often this requires the whole system to be shut down to have the software replaced. This is not a desirable solution. In this work, we propose a non-blocking mechanism embedded into an infrastructure for RTLinuxPro for deterministic replacement of system functionality, task timing, and data-flow for hard real-time systems. We explain the mechanism, discuss its implementation using RTLinuxPro, and present a case study of a stop watch in which we replace single functionality and timing behavior at runtime without compromising the timeliness of tasks or the correctness of the output values. The contribution is to show how such a mechanism can work, how it can be implemented, and what problems arise in multi-mode real-time applications.

Hybrid systems are an appropriate formalism to model embedded systems as they capture the theme of continuous dynamics with discrete control. A simple extension, a network of communicating hybrid automata, allows for modeling distributed embedded systems. Although it is possible to generate code from such models, it is difficult to provide formal guarantees in the code with respect to the model. One of the reasons for this is that, the model is set in continuous time and concurrent execution with instantaneous communication, whereas the generated code is set in discrete time with delayed communication. This can introduce semantic differences between the model and the code such as missed transitions, faulty transitions, and altered continuous behavior. The goal of faithful code generation is to minimize these differences.In this paper, we propose a relaxed criteria of faithfulness, coined relative faithful implementation. Based on this criteria, we propose dynamically adjusting the guard at runtime using estimates of errors for preventing faulty transitions. We also identify a sufficient condition to ensure no missed transitions in the code.

A shared communication medium is characterized by multiple entities that use this medium by reading and writing from and to it. Write operations on the shared communication medium must be coordinated and collision-avoidance schemes are one technique to achieve this; for example time-division multiple access (TDMA). Common solutions for TDMA include descriptive tables or algorithm-based client/server mechanisms. Yet, they are all limited in their expressiveness: at the beginning of the communication period at most one write operation can be scheduled for a specific time slot. In this work, we propose a system that allows for scheduling several write operations for the same time slot but guarantee that at most one will be performed though. It does not deal with scheduling algorithms per se, it deals with describing and implementing a computed schedule. The consequences of this added expressiveness allow for parallel and stateful communication schedules merged and serialized in an ad-hoc way. The contribution is the proposed more-expressive yet still value and time-deterministic way of describing communication schedules for time-triggered communication plus a description of its implementation in an interpreter implemented as infrastructure in RTLinuxPro.

Embedded computers are increasingly tighter integrated with each other forming distributed embedded systems that interact through a shared communication medium. Often these embedded systems perform services for safety-critical operations that require deterministic computation and predictable communication. However, since these systems are embedded, they must cope with limited resources. One fundamental challenge is to make efficient use of the shared communication medium, especially in the timed model, in which communication tends to cumulate at the end of harmonic periods of tasks. In this article, we present an approach that uses Microtasks for splitting computation and communication into several sequentially executed steps to allow for better balanced load on the communication medium in the timed model. We discuss the approach and describe its implementation in OSEK/Works with TTCAN.

Pervasive computing environments accommodate interconnected and communicating mobile devices. Mobility is a vital aspect of everyday life and technology must offer support for moving users, objects, and devices. Their growing number has strong implications on the bandwidth of wireless and wired networks. Network bandwidth becomes a scare resource and its efficient use is crucial for the quality of service in pervasive computing. In this article we study process models for detecting location changes of moving objects and their effect on the network bandwidth. We simulate a scenario of 10/sup 4/ moving objects for a period of 10/sup 7/ time cycles while monitoring the quality of service with respect to network bandwidth for different location detection strategies. The simulation shows that the class of strategies implementing a synchronous model offers better quality of service than the timed model. We conclude the article with a set of guidelines for the application of the strategies we have investigated.