Security is gaining increasing importance in automotive systems, driven by technical innovations. For example, automotive vehicles become more open systems, allowing the communication with other traffic participants and road infrastructure. Also, automotive vehicles are provided with increased autonomy which raises severe safety concerns, and consequently also security concerns—both concerns that interweave in such systems. In this paper we present a qualitative cybersecurity analysis by comparing different time-triggered (TT) communication networks. While TT communication networks have been analysed extensively for dependability, the contribution of this work is to identify security-related benefits that TT communication networks can provide. In particular, their mechanisms for spacial and temporal encapsulation of network traffic are instrumental to improve network security. The security arguments can be used as a design guide for implementing critical communication in flexible network standards like TSN.

The power that stems from modern DRAM devices represents a significant portion of the overall system power in modern computing systems. In multi-core systems, the competing cores share the same memory banks. The memory contention between these cores may lead to activate a large DRAM row only to access a small portion of data. This row over-fetching problem wastes a significant DRAM activation power with a slight performance gain.

MPLS has been in the forefront of high-speed Wide Area Networks (WANs), for almost two decades [1], [12]. The performance advantages in implementing Multi-Protocol Label Switching (MPLS) are mainly its superior speed based on fast label switching and its capability to perform Fast Reroute rapidly when failure(s) occur - in theory under 50 ms [16], [17], which makes MPLS also interesting for real-time applications. We investigate the aforementioned advantages of MPLS by creating two real testbeds using actual routers that commercial Internet Service Providers (ISPs) use, one with a ring and one with a partial mesh architecture. In those two testbeds we compare the performance of MPLS channels versus normal routing, both using the Open Shortest Path First (OSPF) routing protocol. The speed of the Fast Reroute mechanism for MPLS when failures are occurring is investigated. Firstly, baseline experiments are performed consisting of MPLS versus normal routing. Results are evaluated and compared using both single and dual failure scenarios within the two architectures. Our results confirm recovery times within 50 ms.

Nodes connected to a time-triggered (TT) network can access the network interface in two different ways, synchronously or asynchronously, which greatly impacts communication timing and message lifespans (i.e., the time from writing a message to its send buffer till the time when the message is read by the receiver). In this paper we present a clear timing model to reason about the timing variation possible with TT interfaces. This model facilitates the quantitative analysis of the message lifespans of synchronous and asynchronous TT interfaces. Further, we develop a tool to search for node and network configurations that minimise or maximise message lifespans. We show that choosing the right configuration for synchronous interface access can reduce message lifespan significantly (we observed a factor of 9 even for small scenarios). While industrial practice typically is to choose a slot allocation a priory, we show that optimising the slot allocation in coordination with task scheduling gives an extra edge in obtaining minimal message lifespans. For nodes with synchronous interface access, the tool determines the parameters needed to obtain minimal message lifespan and jitter.

In a safety-critical system each service has a specific level of safety criticality. Safety standards use classifications like Safety Integrity Levels (SIL), to describe the design requirements for the individual services of a system. Techniques like redundancy can be used to achieve a higher overall dependability than the used individual components provide. Using the notion of SIL, this can be called SIL arithmetic.In this paper we describe the concept of SIL arithmetic and point out how different safety standards provide hints for their support of using SIL arithmetic. We highlight the principal benefits of SIL arithmetic and provide simple examples. But the use of SIL arithmetic in a concrete system design can also have its pitfalls, which we also discuss in this paper. We specifically discuss these issues in the context of scheduling techniques for mixed-criticality systems, where resource shortages are to be handled by the scheduler.

Time-triggered communication facilitates the construction of multi-component real-time systems whose components are in control of their temporal behaviour. However, the interface of a time-triggered communication system has to be accessed with care, to avoid that the temporal independence of components gets lost. This paper shows two interfacing strategies, one for asynchronous interface access (in two variants, one being the new Rate-bounded Non-Blocking Communication protocol) and one for time-aware, synchronized interface access, that allow components to maintain temporal independence. The paper describes and compares these interfacing strategies.

Time-triggered communication facilitates the construction of multi-component real-time systems whose components are in control of their temporal behavior. However, the interface of a time-triggered communication system has to be accessed with care, to avoid that the temporal independence of components gets lost. This paper shows two interfacing strategies, one for asynchonous interface access (in two variants, one being the new Rate-Bounded Non-Blocking Communication protocol) and one for time-aware, synchronized interface access, that allow components to maintain temporal independence. The paper describes and compares the interfacing strategies.

Real-time systems engineers face a daunting duty: they must ensure that each task in their system can always meet its deadline. To analyse schedulability they must know the worst-case execution time (WCET) of each task. However, determining exact WCETs is practically infeasible in cost-constrained industrial settings involving real-life code and COTS hardware. Static analysis tools that could yield sufficiently tight WCET bounds are often unavailable. As a result, interest in portable analysis approaches like measurement-based timing analysis is growing. We present an approach based on integer linear programming (ILP) for calculating a WCET estimate from a given database of timed execution traces. Unlike previous work, our method specifically aims at reducing overestimation, by means of an automatic classification of code executions into scenarios with differing worst-case behaviour. To ease the integration into existing analysis tool chains, our method is based on the implicit path enumeration technique. It can thus reuse flow facts from other analysis tools and produces ILP problems that can be solved by off-the-shelf solvers.

Graph partitioning is an important problem in computer science and is of NP-hard complexity. In practice it is usually solved using heuristics. In this article we introduce the use of graph partitioning to partition the workload of stream programs to optimise the throughput on heterogeneous distributed platforms. Existing graph partitioning heuristics are not adequate for this problem domain. In this article we present two new heuristics to capture the problem space of graph partitioning for stream programs to optimise throughput. The first algorithm is an adaptation of the well-known Kernighan-Lin algorithm, called KL-Adapted (KLA), which is relatively slow. As a second algorithm we have developed the Congestion Avoidance (CA) partitioning algorithm, which performs reconfiguration moves optimised to our problem type. We compare both KLA and CA with the generic meta-heuristic Simulated Annealing (SA). All three methods achieve similar throughput results for most cases, but with significant differences in calculation time. For small graphs KLA is faster than SA, but KLA is slower for larger graphs. CA on the other hand is always orders of magnitudes faster than both KLA and SA, even for large graphs. This makes CA potentially useful for re-partitioning of systems during runtime.

Standard real-time models do not consider the fact that a chosen technical deadline is different from the critical latency where the service utility becomes zero. This is in mismatch with engineering practice. In this paper we propose a tolerance-based refinement of the real-time model. By doing so we make the process of deriving the estimation of the critical latency explicit. The difference between the technical deadline and the critical latency is a measure for the safety margin of the system. This safety margin is important for both, soft real-time and hard real-time systems, though with different quantities and qualities. Furthermore, we explain why the critical latency can hardly be quantified by a concrete value. However, we demonstrate how to derive reasonable estimates for it. We use a concrete application to show how the distinctive knowledge of the critical latency and the technical deadline are useful for real-time scheduling.

Models for real-time computing are available with different timing requirements. With the ongoing trend towards integration of services of different degrees of timing strictness on one single platform, there is a need to specify computing models for such scenarios. In this paper we study the requirements to specify mixed criticality real-time systems (MCRTS). Mixed criticality systems have been studied intensively over the last years. Existing formulations of the scheduling problem for mixed criticality systems do not consider the different timing strictness requirements of the tasks. In this paper we argue that mixed criticality properties as well as real-time properties have to be considered together in order to provide the maximal utility of a system. Based on that argument we present a list of ingredients required for the specification of MCRTS. We outline conceptually, how a system can take advantage of having MCRTS specifications available. We present some examples to show the usefulness of specifying MCRTS properties for real-life systems.

Code-coverage-based testing is a widely-used testing strategy with the aim of providing a meaningful decision criterion for the adequacy of a test suite. Code-coverage-based testing is also mandated for the development of safety-critical applications; for example, the DO178b document requires the application of the modified condition/decision coverage. One critical issue of code-coverage testing is that structural code coverage criteria are typically applied to source code whereas the generated machine code may result in a different code structure because of code optimizations performed by a compiler. In this work, we present the automatic calculation of coverage profiles describing which structural code-coverage criteria are preserved by which code optimization, independently of the concrete test suite. These coverage profiles allow to easily extend compilers with the feature of preserving any given code-coverage criteria by enabling only those code optimizations that preserve it. Furthermore, we describe the integration of these coverage profile into the compiler GCC. With these coverage profiles, we answer the question of how much code optimization is possible without compromising the error-detection likelihood of a given test suite. Experimental results conclude that the performance cost to achieve preservation of structural code coverage in GCC is rather low. Copyright © 2012 John Wiley & Sons, Ltd.

In this paper we present a design of a stream scheduler aiming at optimising throughput and latency of streaming programs with dynamic program structures. The scheduler uses heuristics based on the demand of data in communications streams. As we address dynamic structures of streaming programs, the particular challenge is that static scheduling based on formal constraints or probabilities is not applicable.

For hard real-time systems, static code analysis is needed to derive a safe bound on the worst-case execution time (WCET). Virtually all prior work has focused on the accuracy of WCET analysis without regard to the speed of analysis. The resulting algorithms are often too slow to be integrated into the development cycle, requiring WCET analysis to be postponed until a final verification phase. In this paper, we propose interactive WCET analysis as a new method to provide near-instantaneous WCET feedback to the developer during software programming. We show that interactive WCET analysis is feasible using tree-based WCET calculation. The feedback is realized with a plugin for the Java editor jEdit, where the WCET values are back-annotated to the Java source at the statement level. Comparison of this tree-based approach with the implicit path enumeration technique (IPET) shows that tree-based analysis scales better with respect to program size and gives similar WCET values.

Measurement-based timing analysis (MBTA) is a hybrid approach that combines execution-time measurements with static program analysis techniques to obtain an estimate of the worst-case execution time (WCET) of a program. The most challenging part of MBTA is test data generation. Choosing an adequate set of test vectors determines safety and efficiency of the overall analysis. So far, there are no feasible criteria that determine how well the worst-case temporal behavior of program parts is covered by a given test-suite. In this paper we introduce a relative safety metric that compares test suites with respect to how well the observed worst-case behavior of program parts is exercised. Using this metric, we empirically show that common code coverage criteria from the domain of functional testing can produce unsafe WCET estimates in the context of MBTA for systems with a processor like the TriCore 1796. Further, we use the relative safety metric to examine coverage criteria that require all feasible pairs of, e.g., basic blocks to be exercised in combination. These are shown to be superior to code coverage criteria from the domain of functional testing, but there is still a chance that an unsafe WCET estimate is derived by MBTA in our experimental setup. Based on the outcomes of our evaluation we introduce and examine Balanced Path Generation, an input data generation technique that combines the advantages of all evaluated coverage criteria and random input data generation.

The goal of measurement-based WCET estimation (MBWE) is to derive an estimate of the worst-case execution time (WCET) of a given piece of software on a particular target platform by executing the software on the target hardware and analyzing the obtained time-stamped execution traces. In this paper we introduce context-sensitive MBWE, an approach that can reduce pessimism by making use of state information that is exposed through individual control-flow decisions. We show how to extend the popular IPET method, to obtain tighter WCET estimates. We provide confirmative empirical results that demonstrate the effectiveness of our approach.

Worst-case execution time (WCET) analysis is concerned with computing a precise-as-possible bound for the maximum time the execution of a program can take. This information is indispensable for developing safety-critical real-time systems, e. g., in the avionics and automotive fields. Starting with the initial works of Chen, Mok, Puschner, Shaw, and others in the mid and late 1980s, WCET analysis turned into a well-established and vibrant field of research and development in academia and industry. The increasing number and diversity of hardware and software platforms and the ongoing rapid technological advancement became drivers for the development of a wide array of distinct methods and tools for WCET analysis. The precision, generality, and efficiency of these methods and tools depend much on the expressiveness and usability of the annotation languages that are used to describe feasible and infeasible program paths. In this article we survey the annotation languages which we consider formative for the field. By investigating and comparing their individual strengths and limitations with respect to a set of pivotal criteria, we provide a coherent overview of the state of the art. Identifying open issues, we encourage further research. This way, our approach is orthogonal and complementary to a recent approach of Wilhelm et al. who provide a thorough survey of WCET analysis methods and tools that have been developed and used in academia and industry.

Divide-and-conquer approaches to worst-case execution-time analysis (WCET analysis) pose a safety risk when applied to code for complex modern processors: Interferences between the hardware acceleration mechanisms of these processors lead to timing anomalies, i.e., a local timing change causes an either larger or inverse change of the global timing. This phenomenon may result in dangerous WCET underestimation. This paper presents intermediate results of our work on strategies for eliminating timing anomalies. These strategies are purely based on the modification of software, i.e., they do not require any changes to hardware. In an effort to eliminate the timing anomalies originating from the processor's out-of-order instruction pipeline, we explored different methods of inserting instructions in the program code that render the dynamic instruction scheduler inoperative. We explain how the proposed strategies remove the timing anomalies caused by the pipeline. In the absence of working solutions for timing analysis for these complex processors, we chose portable metrics from compiler construction to assess the properties of our algorithms.

The steadily growing embedded-systems market comprises many application domains in which real-time constraints must be satisfied. To guarantee that these constraints are met, the analysis of the worst-case execution time (WCET) of software components is mandatory. In general WCET analysis needs additional control-flow information, which may be provided manually by the user or calculated automatically by program analysis. For flexibility and simplicity reasons it is desirable to specify the flow information at the same level at which the program is developed, i.e., at the source level. In contrast, to obtain precise WCET bounds the WCET analysis has to be performed at machine-code level. Mapping and transforming the flow information from the source-level down to the machine code, where flow information is used in the WCET analysis, is challenging, even more so if the compiler generates highly optimized code. In this article we present a method for transforming flow information from source code to machine code. To obtain a mapping that is safe and accurate, flow information is transformed in parallel to code transformations performed by an optimizing compiler. This mapping is not only useful for transforming manual code annotations but also if platform-independent flow information is automatically calculated at the source level. We show that our method can be applied to every type of semantics-preserving code transformation. The precision of this flow-information transformation allows its users to calculate tight WCET bounds.

This paper explores timing anomalies in WCET analysis.Timing anomalies add to the complexity of WCET analysis and make it hard to apply divide-and-conquer strategies to simplify the WCET assessment. So far, timing anomalies have been described as a problem that occurs when the WCET of a control-flow graph is computed from the WCETs of its subgraphs, i.e., from a series decomposition. This paper extends the state of the art by (i) showing that timing anomalies can as well occur in a parallel decomposition of the WCET problem, i.e., when complexity is reduced by splitting the hardware state space and performing a separate WCET analysis for hardware components that work in parallel, (ii) proving that the potential occurrence of parallel timing anomalies makes the parallel decomposition technique unsafe (i.e., one cannot guarantee that the calculated WCET bound does not underestimate the WCET), and (iii) identifying special cases of parallel timing anomalies for which the parallel decomposition technique is safe. The latter provides an important hint to hardware designers on their way to constructing predictable hardware components.

This position paper discusses the possibility to combine organic computing and model-driven design.

Reusable libraries are problematic for real-time software in Java. Using Java's standard class library, for example, demands meticulous coding and testing to avoid response time spikes and garbage collection. We propose two design requirements for reusable libraries in real-time systems: worst-case execution time (WCET) bounds and worst- case memory consumption bounds. Furthermore, WCET cannot be known if blocking method calls are used. We have applied these requirements to the design of three Java-based prototypes: a set of collection classes, a networking stack, and trigonometric functions. Our prototypes show that reusable libraries can meet these requirements and thus be viable for real-time systems.

The analysis of the worst-case execution time (WCET) requires detailed knowledge of the program behavior. In practice it is still not possible to obtain all needed information automatically. In this paper we present the current state of the art of WCET analysis and point to the main problems to be solved. The most eminent problem is the state problem, i.e., the precise determination of possible processor states at different program locations. The path problem refers to the fact that current tools are not able to calculate all (in)feasible paths automatically. We discuss how the main open problems manifest themselves in static and in measurement-based WCET analysis methods.

Recent technologies such as the real-time specification for Java promise to bring Java's advantages to real-time systems. While these technologies have made Java more predictable, they lack a crucial element: support for determining the worst-case execution time (WCET). Without knowledge of WCET, the correct temporal behavior of a Java program cannot be guaranteed. Although considerable research has been applied to the theory of WCET analysis, implementations are much less common, particularly for Java. Recognizing this deficiency, we have created an open-source, extensible tool that supports WCET analysis of Java programs. Designed for flexibility, it is built around a plug- in model that allows features to be incorporated as needed. Users can plug in various processor models, loop bound detectors, and WCET analysis algorithms without having to understand or alter the tool's internals.

Embedded systems are often used in safety-critical environments. Thus, thorough testing of them is mandatory. A quite active research area is the automatic test-case generation for testing embedded systems. To achieve high retargetability of the testing framework, thetest-case generation has to be done at source-code level. However, it is challenging to guarantee that the test-cases obtained from the source code are also valid at the object-code level, since even in safety-critical domains programs are optimized during compilation, i.e., the compiler may also introduce new control-flow decisions to the program.

Static worst-case execution time (WCET) analysis is done by modeling the hardware behavior. In this paper we describe a WCET analysis technique to analyze systems with function caches, a special kind of instruction cache that caches whole functions only. This cache was designed with the aim to be more predictable for the worst-case than existing instruction caches. Within this paper we developed a cache analysis technique for the function cache. One of the new concepts of this analysis technique is the local persistence analysis, which allows to precisely model the function cache.

In this paper, we introduce an approach for automated verification and testing of ANSI C programs for embedded systems. We automatically extract an automaton model from the C code of the SUT (system under test). This automaton model is on the one hand used for formal verification of the requirements defined in the system specification, on the other hand, we can derive test cases from this model, for both methods we use a model checker. We describe our techniques for test case generation, based on producing counterexamples with a model checker by formulating trap properties. The resulting test cases can then be applied to the SUT on different test levels. An important issue for model checking C-source code, is the correct modeling of the semantics of a C program for an embedded system. We focus on challenges and possible restrictions that appear, when model checking is used for the verification of C-source code. We specifically show how to deal with arithmetic expressions in the model checker NuSMV and how to preserve the numerical results in case of modeling the platform-specific semantics of C

Modern processors used in embedded systems are becoming increasingly powerful, having features like caches and pipelines to speedup execution. While execution speed of embedded software is generally increasing, it becomes more and more complex to verify the correct temporal behavior of software, running on this high-end embedded computer systems. To achieve time-predictability the authors introduced a very rigid software execution model with distribution being realized based on the time-triggered communication model. In this paper we analyze the time-predictability of a preempting task-activation, running on a hardware with direct-mapped instruction caches. As one result we analyze why a task-preemption driven by a clock interrupt is not suitable to guarantee time-predictability. As a second result, we present a time-predictable task-preemption driven by an instruction counter.

To communicate between heterogeneous computer systems, mechanisms for data conversion are necessary. In this paper we present a portable, asymmetric data conversion method that is suitable for remote testing frameworks in embedded systems development. The described method takes the resource limitations of embedded systems into account by doing the data conversion at the testing host. The method can be implemented as platform-independent source code and it avoids the need of recompiling the code of a communication partner if the code of the other communication partner is migrated to a different platform

We present a new measurement-based worst-case execution time (WCET) analysis method. Exhaustive end-to-end measurements are computationally intractable in most cases. Therefore, we propose to measure execution times of subparts of the application. We use heuristic methods and model checking to generate test data, forcing the execution of selected paths to perform run-time measurements. The measured times are used to calculate the WCET in a final computation step. As we operate on the source code level, our approach is platform independent except for the run-time measurements performed on the target host. We show the feasibility of the required steps and explain our approach by means of a case study.

Worst-case execution time (WCET) analysis has become an active research area over the last decade. Various techniques have been developed to improve the WCET calculation methods for numerous features of the hardware. In parallel, attention has been paid to integrate the analysis techniques into modern software engineering processes. In this paper we give an overview about the different aspects of WCET analysis. We clarify terms and categorise features of WCET analysis tools. Therefore we present a generic framework for WCET analysis and describe its fundamental operations. We present a classification scheme to test the applicability of WCET analysis tools for certain analysis requirements.

In today's technical world (e.g., in the automotive industry), more and more purely mechanical components get replaced by electro-mechanical ones. Thus the size and complexity of embedded systems steadily increases. To cope with this development, comfortable software engineering tools are being developed that allow a more functionality-oriented development of applications. The paper demonstrates how worst-case execution time (WCET) analysis is integrated into such a high-level application design and simulation tool MATLAB/Simulink-thus providing a higher-level interface to WCET analysis. The MATLAB/Simulink extensions compute and display worst-case timing data for all blocks of a MATLAB/Simulink simulation, which gives the developer of an application valuable feedback about the correct timing of the application being developed. The solution facilitates a fully-automated WCET analysis, i.e., in contrast to existing approaches the programmer does not have to provide path information.

Performing worst-case execution time (WCET) analysis on machine code with program path annotation provided at high-level source code level requires the transformation of path annotations from the source-code level to assembly/object-code level. This path-information transformation can be done outside or integrated into the compiler during code compilation. The first approach is easier to implement but lacks for the support of strong code optimizations performed by the compiler because the external tool would have to make guesses about optimizations. In this paper we present an approach for the program code compilation that integrates the transformation of program path information into the compiler. Path information is transformed through all compiler stages to the adequate path information for the corresponding assembly code level. The WCET analysis tool processes the program at assembly code level with the correctly transformed program-path information to obtain accurate runtime bounds. Several experiments were performed to demonstrate the importance of supporting the transformation of path-information in aggressively optimizing compilers.