In real-time systems with data-dependent tasks, ensuring both correctness and timeliness is critical not only for individual task executions but also for data processing across cause-effect chains. When these systems are deployed on multiprocessor platforms, tasks belonging to the same chain might be distributed over multiple nodes. In such situations, data received from other nodes may be unreliable, as those nodes could be compromised by faults or malicious attacks. Prior research on fault-tolerant cause-effect chains has largely focused on crash faults and often fails to ensure that task deadlines are met during fault recovery. This paper presents a method that tolerates node failures caused by both faults and malicious intrusions, while ensuring task deadlines in multi-processor (or multi-core) realtime systems through active replication. Our approach leverages majority voting on outputs from replicated tasks across different nodes, enabling each task to validate incoming data before processing it further along the chain. Additionally, for systems using active replication, we present a formal job-level end-toend latency analysis for cause-effect chains. To reduce the end-to-end latency of task chains, we propose a replica-to-node mapping strategy that enables improved worst-case response times. Experimental evaluations demonstrate that our latencyaware mapping reduces end-to-end latency compared to the commonly used worst-fit decreasing heuristic, although it may slightly reduce task acceptance ratios at high total utilizations.

Replication and diversification are commonly used fault-tolerance techniques to mask accidental faults or malicious behavior of compromised nodes in cyber-physical systems. In event-driven systems, executing diversified replicated tasks across multiple nodes can result in their different execution orders. Implementing a total order protocol for job execution across all nodes ensures consistency and facilitates recovery in case of failures. However, achieving total order comes with significant costs due to the high communication and coordination demands among nodes. Existing solutions require coordination either before each job execution or at each job release. Moreover, some total order protocols may lead to unbounded priority inversion on certain nodes in order to maintain a global execution order. Malicious nodes can deliberately exploit these protocols to launch priority inversion attacks, thereby jeopardizing the timeliness of tasks on healthy nodes in time-critical applications. We propose a total order execution protocol that guarantees bounds on the priority inversion tasks experience and ensures that tasks meet their deadlines in real-time systems. Our approach withstands priority inversion attacks and leverages common knowledge among nodes rather than relying on communication, allowing them to progress independently while still ensuring a consistent execution order of job replicas across nodes upon their release. Although inter-node communication is not required, the method can benefit from exchanged progress data to reduce job response times. It is compatible with coarsely synchronized clocks and, unlike other total order approaches, which are for non-preemptive scheduling, uses progress milestones to enable task preemption. We evaluate our method against existing approaches based on acceptance ratio and response times, and study how job response times vary with increasing communication delays when the approach is used.

Simulation is an important tool for the verification of modern complex time-critical communication systems, especially when worst-case schedulability analysis is not available. Evaluating worst-case traversal times via simulation traditionally involves resource-intensive long simulations that are poorly parallelizable. Recent research has demonstrated that aggregating many short simulations with randomized starting conditions yields substantial improvements over this classical approach in terms of likelihood of observing very large communication latencies. In this study, we explore the potential of many-objective optimization to further enhance the efficiency of the aggregation approach.To this end we further reduce the length of the aggregated simulations and perform many-objective optimization to set the starting conditions, namely the node start offsets and initial flow scheduling order. Our approach consists in modelling the approximation of worst-case traversal times as a many-objective Pareto optimization problem in the context of real-time Ethernet networks. Performance evaluation, conducted on different industrially relevant use cases from the automotive and aerospace domains, shows up to 46.42% increased end-to-end latencies for a 50 times shorter total simulation time, in comparison to the traditional approach of running single long simulations.

Satellite imagery solutions are widely used to study and monitor different regions of the Earth. However, a single satellite image can cover only a limited area. In cases where a larger area of interest is studied, several images must be stitched together to create a single larger image, called a mosaic, that can cover the area. Today, with the increasing number of satellite images available for commercial use, selecting the images to build the mosaic is challenging, especially when the user wants to optimize one or more parameters, such as the total cost and the cloud coverage percentage in the mosaic. More precisely, for this problem the input is an area of interest, several satellite images intersecting the area, a list of requirements relative to the image and the mosaic, such as cloud coverage percentage, image resolution, and a list of objectives to optimize. We contribute to the constraint and mixed integer lineal programming formulation of this new problem, which we call the satellite image mosaic selection problem, which is a multi-objective extension of the polygon cover problem. We propose a dataset of realistic and challenging instances, where the images were captured by the satellite constellations SPOT, Pléiades and Pléiades Neo. We evaluate and compare the two proposed models and show their efficiency for large instances, up to 200 images.

We present here the main features and lessons learned from the first edition of what has now become the ECRTS industrial challenge, together with the final description of the challenge and a comparative overview of the proposed solutions. This verification challenge, proposed by Thales, was first discussed in 2014 as part of a dedicated workshop (FMTV, a satellite event of the FM 2014 conference), and solutions were discussed for the first time at the WATERS 2015 workshop. The use case for the verification challenge is an aerial video tracking system. A specificity of this system lies in the fact that periods are constant but known with a limited precision only. The first part of the challenge focuses on the video frame processing system. It consists in computing maximum values of the end-to-end latency of the frames sent by the camera to the display, for two different buffer sizes, and then the minimum duration between two consecutive frame losses. The second challenge is about computing end-to-end latencies on the tracking and camera control for two different values of jitter. Solutions based on five different tools - Fiacre/Tina, CPAL (simulation and analysis), IMITATOR, UPPAAL and MAST - were submitted for discussion at WATERS 2015. While none of these solutions provided a full answer to the challenge, a combination of several of them did allow to draw some conclusions.

Megatrends such as Highly Automated Driving (HAD) (SAE ≥ Level 3), electrification, and connectivity are reshaping the automotive industry. Together with the new technologies, the business models will also evolve, opening up new possibilities and new fields of competition. To cope with the ongoing advances, new Electric/Electronic (E/E) architecture patterns are emerging in the sector, distributing the vehicle functions across several processing devices and enhancing the connectivity between them via Ethernet-based networks. Upcoming systems will demand Safety-Related Availability (SaRA) requirements in mixed-critical E/E architectures that challenge the concept of freedom from interference defined in ISO 26262. This work explores the concepts of SaRA system development according to ISO 26262, building a framework based on model-based systems engineering to evaluate feasible next-generation automotive E/E architecture designs with a multi-objective analysis. Additionally, we propose a pattern template for SaRA systems to automate the architecture synthesis. To illustrate the framework created, we evaluate a set of automotive E/E architectures synthesized to support mixed-critical vehicle features, including SaRA SAE Level-3 functions, considering the communication networks’ performance as well as hardware and safety-related development costs. This work presents a methodology for original equipment manufacturers and Tier-1 suppliers that enables them to make the trade-offs arising in the design of E/E architectures based on quantified information.

Machine learning has been recently applied in real-time systems to predict whether Ethernet network configurations are feasible in terms of meeting deadline constraints without executing conventional schedulability analysis. However, the existing prediction techniques require domain expertise to choose the relevant input features and do not perform consistently when topologies or traffic patterns differ significantly from the ones in the training data. To overcome these problems, we propose a Graph Neural Network (GNN) prediction model that synthesizes relevant features directly from the raw data. This deep learning model possesses the ability to exploit relations among flows, links, and queues in switched Ethernet networks and generalizes to unseen topologies and traffic patterns. We also explore the use of ensembles of GNNs and show that it enhances the robustness of the predictions. An evaluation on heterogeneous testing sets comprising realistic automotive networks shows that ensembles of 32 GNN models feature a prediction accuracy ranging from 79.3% to 90% for Ethernet networks using priorities as the Quality-of-Service mechanism. The use of ensemble models provides a speedup factor ranging from 77 to 1,715 compared to schedulability analysis, which allows a far more extensive design space exploration.

Preventive and reactive maintenance require the collection of an ever-increasing amount of information from industrial plants and other complex systems such as those based on robotized cells, a need that can be fulfilled by means of a suitable event notification mechanism. At the same time, timing and delivery reliability requirements in those scenarios are typically less demanding than those in other cases, thus enabling the adoption of best-effort notification approaches. This paper presents, evaluates, and compares some of those approaches, based on either standard Controller Area Network (CAN) messaging or a recently proposed protocol extension called CAN with eXtensible in-frame Reply (CAN XR). In the second case, the combined use of Bloom filters is also envisaged to increase flexibility. Results show that the latter approaches are advantageous in a range of event generation rates and network topologies of practical relevance.

The ever-growing complexity of present-day software systems raises new and more stringent requirements on their availability, pushing designers to make use of sophisticated fault tolerance techniques far beyond the areas they were traditionally conceived for, and bringing new challenges to both the modelling and implementation phases. In this paper, we propose a design pattern to model in a domain-specific language one of the prominent fault-tolerant techniques, namely the N-version programming. It can be integrated seamlessly into existing applications to enhance their functional correctness, while still preserving the timing characteristics, in particular the sampling times. Besides, it is also designed in a way to ease the automatic code generation. A counterpart of the same framework is also implemented in a lower-level programming language, for use when direct model execution is impractical, like in severely resource-limited embedded targets.

Software fault injection is a powerful technique to evaluate the robustness of an application and guide in the choice of fault-tolerant mechanisms. It however requires a lot of time and know-how to be properly implemented, which severely hinders its applicability. We believe software fault injection can be made more “affordable” by automating it and have it integrated within a model-driven engineering design flow. We first propose in this paper a framework supporting these objectives. Then, illustrating on the domain-specific language CPAL, we present injection patterns that can be embedded in the application code and discuss the types of faults each supports, as well as implementation issues.

Innovation in the field of embedded systems, and more broadly in cyber-physical systems, increasingly relies on software. The productivity gain in software development can hardly keep up with the demand for software despite the increasing adoption of Model-Driven Development (MDD). In this context, we believe that major productivity and quality improvements are still ahead of us through better programming languages and environments. CPAL, the Cyber-Physical Action Language, is a contribution in that direction with the objective to speed-up the development of embedded systems with dependability constraints. The objective of this paper is to present and illustrate the use-cases of the high-level abstractions offered to the developer in CPAL with respect to real-time scheduling, introspection mechanisms, native support of Finite State Machines (FSMs), abstracting the hardware and decoupling functional concerns from non-functional concerns.

CPAL is a new language to model, simulate, verify and program Cyber-Physical Systems (CPS). CPAL serves to describe both the functional behaviour of activities (i.e., the code of the function itself) as well as the functional architecture of the system (i.e., the set of functions, how they are activated, and the data flows among the functions). CPAL is meant to support two use-cases. Firstly, CPAL is a development and design-space exploration environment for CPS with main features being the formal description, the editing, graphical representation and simulation of CPS models. Secondly, CPAL is a real-time execution platform. The vision behind CPAL is that a model is executed and verified in simulation mode on a workstation and the same model can be later run on an embedded board with a timing-equivalent run-time behaviour. The design and development of CPAL have been organized around a set of realistic case-studies that will be demonstrated during the demonstration session. The CPAL case studies and experiments are inspired from the research and teaching carried out at University of Luxembourg, and RTAW's projects with partner and customer companies.

Summary form only given. Scheduling is crucial in real-time applications. For any real-time system, the desired scheduling policy can be selected based on the scheduling problem itself and the underlying system constraints. This work targets a novel optimization framework which automates the selection and configuration of the scheduling policy. The framework selects the best suited scheduling configuration for a partially specified task set and the given constraints. Our aim is to develop this framework such that the system designer only focuses on the high-level timing behavior of the system, where the implementation choices of the low level timing behavior are taken care of by the framework. The framework fits in the early design phases as a device to automate system synthesis and hide away from the designer the complexity of the underlying runtime environments. In the framework, the system synthesis step involving both analysis and optimization then generates a scheduling solution which at run-time is enforced by the execution environment. This work is a contribution towards a more automated design process building on the wide set of techniques and results developed within the real-time system community.

In the design of real-time systems, models are usual artifacts to capture and represent the various features of the system. They are later analyzed to check for their correctness. A key issue is to handle models and analyses in a systematic, consistent and efficient way. This paper presents an approach for the systematic and correct execution of analyses on real-time system models along with a proof-of-concept. The contribution aims at 1) directing the analyses targeting goals and 2) using contracts to reason about models, analyses and goals. An example of goal is to enrich a model with missing information or to obtain precise data to conclude about the system quality. In our approach, contracts are used to formally depict both the properties required and provided by the analyses, but also models and goals. Through the concept of contracts, we identify all the feasible paths to execute the analyses in order to reach a goal.

The analysis of the real-time properties of an embedded communication system relies on finding upper bounds on the Worst-Case Response Time (WCRT) of the messages that are exchanged among the nodes on the network. The classical WCRT analysis of Controller Area Network (CAN) implicitly assumes that at any given time, each node is able to enter its highest priority ready message into arbitration. However, in reality, CAN controllers may have some characteristics, such as non-abortable transmit buffers, which may break this assumption. This paper provides analysis for networks that contain nodes with non-abortable transmit buffers, as well as nodes that meet the requirements of the classical analysis. The impact on message WCRTs due to a limited number of transmission buffers with non-abortable behaviour is examined via two case-studies.

The response time distributions of the frames sent on a Controller Area Network (CAN) bus are of prime interest to dimension and validate automotive electronic architectures. However, the existing work on the timing behaviour of the CAN network does not take into account that all the data exchanges between the Electronic Control Units (ECUs) are driven by different and independent clocks which are subject to clock drifts. This paper proposes a model for clock drifts and describes their impact on the CAN frame response time distributions. By implementing the clock drifts in a CAN simulation tool, we show experimentally that the response time distributions converge, for drift values chosen randomly within the same range on all ECUs, whatever the initial phasings between the sending nodes. Furthermore, we show that, as a result of the clock drifts, the situations leading to the worst case response times are transient.

In distributed real-time systems it is crucial to ensure the temporal validity of the data exchanged among the nodes. Classically, the frame worst case response time (WCRT) analyses, and the software tools which implement them, do not take into account the aperiodic traffic. One of the main reasons for this is that the aperiodic traffic is generally very difficult to characterize (i.e., the arrival patterns of the aperiodic frames). The consequence of this is that one tends to underestimate the WCRT, which may have an impact on the overall safety of the system. In this paper, we propose a probabilistic approach to model the aperiodic traffic and integrate it into response time analysis. The approach allows the system designer to choose the safety level of the analysis based on the system's dependability requirements. Compared to existing deterministic approaches the approach leads to more realistic WCRT evaluation and thus to a better dimensioning of the hardware platform.

In distributed real-time systems, meeting the real-time constraints is mandatory, but the satisfaction of other application-dependent criteria is most generally required as well. In particular, networked control systems (NCS) are known to be sensitive to communication delays such as frame response time jitters. Well-known medium access control (MAC) algorithms such as non-preemptive deadline monotonic (NP-DM) or non-preemptive earliest deadline first (NP-EDF) are efficient in terms of bandwidth usage, but they may perform poorly regarding other application-dependent performance criteria. This paper highlights a class of online scheduling policies targeted at scheduling frames at the MAC level, and it provides a schedulability analysis that is valid for all policies within the considered class. As it will be shown, these algorithms are implementable on COTS components (e.g., Controller Area Network controllers) and offer good trade-offs between feasibility and the satisfaction of other application-dependent criteria such as the response time jitter.

Battery lifetime, a primary design constraint for mobile embedded systems, has been shown to depend heavily on the load current profile. This paper explores how scheduling guidelines from battery models can help in extending battery capacity. It then presents a 'battery-aware scheduling' methodology for periodically arriving task graphs with real time deadlines and precedence constraints. Scheduling of even a single taskgraph while minimizing the weighted sum of a cost function has been shown to be NP-hard (Lawler, 1978). The presented methodology divides the problem in to two steps. First, a good DVS algorithm dynamically determines the minimum frequency of execution. Then, a greedy algorithm allows a near optimal priority function (Gruian, 2002) to choose the task which would maximize slack recovery. The methodology also ensures adherence of real time deadlines independent of the choice of the DVS algorithm and priority function used, while following battery guidelines to maximize battery lifetime. Battery simulations carried out on the profile generated by our methodology for a large set of taskgraphs show that battery life time is extended up to 23.3% as compared to existing dynamic scheduling schemes

In-vehicle embedded systems typically consist of a set of nodes exchanging applicative data ("signals") through a stack of communication protocols that includes a middleware layer. On each node, tasks, both applicative and middleware level, are subject to deadline constraints. Furthermore, signals must be produced sufficiently recently for being safely consumed on the receiver end (so-called "freshness constraint"). The goal of this study is to propose an approach for configuring nodes and communication protocols that takes these constraints into account. Precisely, the problem is, on the one hand, to set the characteristics of the middleware tasks and of the set of frames and, on the other hand, to find a feasible schedule on each node.

The use of networks for communications between the electronic control units (ECU) of a vehicle in production cars dates from the beginning of the 1990s. The specific requirements of the different car domains have led to the development of a large number of automotive networks such as Local Interconnect Network, J1850, CAN, TTP/C, FlexRay, media-oriented system transport, IDB1394, etc. This paper first introduces the context of in-vehicle embedded systems and, in particular, the requirements imposed on the communication systems. Then, a comprehensive review of the most widely used automotive networks, as well as the emerging ones, is given. Next, the current efforts of the automotive industry on middleware technologies, which may be of great help in mastering the heterogeneity, are reviewed. Finally, we highlight future trends in the development of automotive communication systems.

We present an algorithm for scheduling a set of nonrecurrent tasks (or jobs) with FIFO real-time constraints so as to minimize the total energy consumed when the tasks are performed on a dynamically variable voltage processor. Our algorithm runs in linear time and thus, in this case, is an improvement over the classical algorithm of Yao et al. It was inspired by considering the problem as a shortest-path problem. We also propose an algorithm to deal with the case where the processor has only a limited number of clock frequencies. This algorithm gives the optimum schedule with the minimum number of speed changes, which is important when the speed switching overhead cannot be neglected. All our algorithms are linear in the number of tasks if the arrivals and deadlines are sorted and otherwise need O ( N log N ) time. These complexities are shown to be the best possible. Finally, we extend our results to fluid tasks and to nonconvex cost functions.