International audience

In safety-critical systems many software components of different criticalities or assurance levels need to interact in a timely manner to keep the system and environment safe. Nowadays, these systems are challenged by technological progress resulting in rapid increases in both software complexity and processing demands. Efficiently designing safety-critical systems subject to stringent timing requirements is therefore a challenge and a necessity. In this article, we consider the mixed-criticality execution model and homogeneous multi-core processors. We begin by defining a task model incorporating mixed-criticality, real-time and precedence constraints in the form of directed acyclic graphs. A meta-heuristic to solve the scheduling problem of this task model is then defined and proved to respect deadlines, even when the system needs to give more processing power to the most critical tasks. The state-of-the-art techniques capable of scheduling a similar task model have only been developed for dual-criticality systems. Conversely, the meta-heuristic we propose has been generalized to support an arbitrary number of criticality levels. We instantiated our meta-heuristic adopting scheduling algorithms such as G-EDF, G-LLF, or G-EDZL for each level of criticality. The experiments show excellent results in terms of acceptance ratio and number of preemptions.

The interactions among concurrent tasks pose a challenge in the design of real-time multi-core systems, where blocking delays that tasks may experience while accessing shared memory have to be taken into consideration. Various memory arbitration schemes have been devised that address these issues, by providing trade-offs between predictability, average-case performance, and analyzability. Time-Division Multiplexing (TDM) is a well-known arbitration scheme due to its simplicity and analyzability. However, it suffers from low resource utilization due to its non-work-conserving nature. We proposed in our recent work dynamic schemes based on TDM, showing work-conserving behavior in practice, while retaining the guarantees of TDM. These approaches have only been evaluated in a restricted setting. Their applicability in a preemptive setting appears problematic, since they may induce long memory blocking times depending on execution history. These blocking delays may induce significant jitter and consequently increase the tasks' response times. This work explores means to manage and, finally, bound these blocking delays. Three different schemes are explored and compared with regard to their analyzability, impact on response-time analysis, implementation complexity, and runtime behavior. Experiments show that the various approaches behave virtually identically at runtime. This allows to retain the approach combining low implementation complexity with analyzability.

In the critical systems domain, Mixed Criticality Systems (MCS) improve considerably the usage of computation resources by running tasks with different levels of criticality on multi-core processors. To ensure the safety of MCS, services provided by low criticality tasks are degraded or stopped whenever high criticality tasks need more computation time than initially credited. The evaluation of this degradation is hardly considered in the literature although low criticality services are of prime importance for the quality of service (QoS) of critical systems. In this paper, we propose a method to evaluate the availability of low criticality services, i.e. how often these services are delivered in MCS. We also propose a task model that improves this availability, demonstrated thanks to our evaluation method on an illustrative example of MCS.

Multi-core architectures pose many challenges in real-time systems, which arise from contention between concurrent accesses to shared memory. Among the available memory arbitration policies, Time Division Multiplexing (TDM) ensures a predictable behavior by bounding access latencies and guaranteed bandwidth to tasks independently from the other tasks. To do so, TDM guarantees exclusive access to the shared memory in a fixed time window. TDM, however, provides a low resource utilization as it is non-work-conserving. Besides, it is very inefficient for resources having highly variable latencies, such as sharing the access to a DRAM memory. The constant length of a TDM slot is, hence, highly pessimistic and causes an underutilization of the memory. To address these limitations, we present dynamic arbitration schemes that are based on TDM. However, instead of arbitrating at the level of TDM slots, our approach operates at the granularity of clock cycles by exploiting slack time accumulated from preceding requests. This allows the arbiter to reorder memory requests, exploit the actual access latencies of requests, and thus improve memory utilization. We demonstrate that our policies are analyzable as they preserve the guarantees of TDM in the worst case, while our experiments show an improved memory utilization on average.

Thanks to Mixed-Criticality (MC) scheduling, high and low-criticality tasks can share the same execution platform, improving considerably the usage of computation resources. Even if the execution platform is shared with low-criticality tasks, deadlines of high-criticality tasks must be respected. This is usually enforced thanks to operational modes of the system: if necessary, a high-criticality execution mode allocates more time to high-criticality tasks at the expense of low-criticality tasks' execution. Nonetheless, most MC scheduling policies in the literature have only considered independent task sets. For safety-critical real-time systems, this is a strong limitation: models used to describe reactive safety-critical software often consider dependencies among tasks or jobs. In this paper, we define a meta-heuristic to schedule multiprocessor systems composed of multi-periodic Directed Acyclic Graphs of MC tasks. This meta-heuristic computes the scheduling of the system in the high-criticality mode first. The computation of the low-criticality scheduling respects a condition on high-criticality tasks' jobs, ensuring that high-criticality tasks never miss their deadlines. An efficient implementation of this meta-heuristic is presented. In high-criticality mode, high-criticality tasks are scheduled as late as possible. Then two global scheduling tables are produced, one per criticality mode. Experimental results demonstrate our method outperforms approaches of the literature in terms of acceptance rate for randomly generated systems.

Mixed-criticality systems emerged with the aim of reconciling safety requirements and efficient use of multi-processor or uniprocessor platforms. On multi-processors, recent works on mixed-criticality have produced impressive results in terms of speed-up factor. But these solutions, based on Pfair-like scheduling algorithms, entail too many preemptions and migrations to be effectively used in real systems. As RUN is an optimal scheduling algorithm that is known to limit this problem, we propose MxC-RUN, an adaptation of RUN to mixed-criticality systems. We redefine RUN's primal servers as modal servers that allocate the overestimated time budget of their higher criticality tasks to execute lower criticality ones. These servers can be handled by RUN without any modification and preserve its performances in terms of preemptions and migrations. MxC-RUN earns a speed-up factor smaller than other multi-processors EDF-based mixed-criticality scheduling algorithms.

Model transformation has become now well established as an approach to control and automate the production of the software targeted at large or embedded systems. However, this approach still lacks the ability to be fully automated and to take into account the possibly very large number of Non Functional properties (NFPs) required by the system. Starting from a design written in an architecture description language (AADL), a large number of valid transformations are candidates to be applied, with the aim to refine this design, in a step wise manner, towards its implementation. These transformations may be interdependent, and their selection should take the complex dependency relation into account. The selection should also take into account the impact on NFPs, especially knowing that NFPs may very often be in conflict. In this paper, we propose an approach that automates (i) the identification of model transformation alternatives (MTAs) taking into account their dependencies, and (ii) the selection of MTAs, based on evolutionary algorithms (EAs), that produce the best output models with respect to NFPs. Experiments on a case study provide evidence that the approach can be successfully applied for code generation of real time embedded applications.

As real-time systems have become more and more complex, architects rely on abstract models of computation in order to design and analyse these systems. In order to ease the production of source code that respects such models of computation, developper can take advantage of code generators and/or middleware. However, when analyzing an abstract model of computation, timing overheads due to generated code or middleware components are not taken into account. Answering this issue is even more problematic in the domain of embedded systems because of the variability of execution platforms. To tackle this problem, we present in this paper a model refinement and timing analysis framework: abstract models of computation are first transformed in more precise models, which include the timing characteristics of the execution platform. These refined models are then used for a more precise timing analysis. The experiment results we present in this paper show that our method can deal with realistic software architecture of real-time systems.

The design of hard real-time embedded systems has to comply with strong requirements with respect to time determinism and resource consumption. However, interacting tasks may induce pessimism in schedulability analysis or introduce significant overheads in memory usage. In this paper, we restrict the execution and communication models to enforce an efficient and predictable implementation. To ensure determinism, a message sent by an emitting task is delivered at its deadline. We take advantage of a wait-free specialized message queues to provide predictable and efficient implementation. The integration of such mechanisms is assisted by a model driven engineering framework1.

Facing a growing complexity, embedded systems design relies on model-based approaches to ease the exploration of a design space. A key aspect of such exploration is performance evaluation, mainly depending on usage of the hardware resources. In model-driven engineering, hardware resources usage is often approximated by static properties. In this paper, we propose an extensible modeling framework, to describe with different levels of detail the hardware resource usage. Our method relies on the AADL to describe the whole system, and SystemC to refine the execution platform description. In this paper we expose how we generate and compose SystemC models from the execution platform model described in AADL. We also present promising experimental results obtained on an avionics use-case.

SUMMARY Safety‐critical systems are used in many domains (military, avionics, aerospace, etc.) and handle critical data in hostile environments. To prevent data access by unauthorized subjects, they must protect and isolate information so that only allowed entities can read or write information. However, because of their increased number of functionalities, safety‐critical systems design becomes more complex; this increases difficulties in the design and the verification of security functions and potential error in their implementation. The multiple independent levels of security (MILS) approach introduces rules and guidelines for the design of secure systems. It isolates data according to their security levels, reducing system complexity to ease development. However, there is no approach addressing the whole development of MILS systems from high‐level specification (application components with their security levels) to the final implementation (code that executes application functions and provide security mechanisms). This paper presents a complete development approach for the design, verification and implementation of MILS architectures. It aims at providing a complete framework to build secure applications based on MILS guidelines. We describe security concerns using a modeling language, verify security requirements and automatically implement the system code generation techniques and a MILS‐compliant operating system that provides security functions. Copyright © 2012 John Wiley & Sons, Ltd.

SUMMARY The complexity of modern embedded systems increases as they incorporate new concerns such as distribution and mobility. These new features need to be considered as early as possible in the software development life cycle. Model driven engineering promotes an intensive use of models and is now widely seen as a solution to master the development of complex systems such as embedded ones. Component‐based software engineering is another major trend that gains acceptance in the embedded world because of its properties such as reuse, modularity, and flexibility. This article proposes the Flex‐eWare component model (FCM) for designing and implementing modern embedded systems. The FCM unifies model driven engineering and component‐based software engineering and has been evaluated in several application domains with different requirements: wireless sensor networks, distributed client/server applications, and control systems for electrical devices. This approach highlights a new concept: flexibility points that arise at several stages of the development process, that is, in the model (design phase), in the execution platform, and during the execution itself. This flexibility points are captured with model libraries that can extend the FCM. Copyright © 2011 John Wiley & Sons, Ltd.

AADL is a modeling language to design and analyze High-Integrity Distributed and Real-time systems. Embedded sub-languages published as AADL annexes extend an AADL model to enhance analysis. The behavior annex specifies the behavior of an AADL application model. Thus, an implantation of this annex allows to perform behavior analysis. In addition, as there are several AADL annexes, the implementation of generic mechanisms to support each one of them is challenging. The behavior annex is a valid candidate to illustrate these challenges by combining several sub-languages. In this paper we expose our experiment to support the behavior annex in the reference AADL tool set OSATE2. This one, supports the AADL version 2 by providing a front-end and a set of analysis plug-ins to analyze an AADL model.

In this paper, we present different modeling and execution frameworks that allow us to efficiently analyze, design and verify complex systems, mainly to cope with the specific concerns of the Real-time and embedded systems (RTE) domain. First we depict a UML /MARTE based methodology for executable RTE systems modeling with a framework and its underlying model transformations required to execute UML models conforming to the MARTE standard. The advantages of adopting a more generic action language with formal features are highlighted, in order to raise the level of abstraction with formal features. Then, we investigate how MARTE, with its Time Model facilities, can be made to represent faithfully AADL periodic/aperiodic tasks communicating through event or data ports, in an approach to end-to-end flow latency analysis. An analytical framework allows us to optimize port-based communication by generating a run time executive that utilizes shared data areas where appropriate, while ensuring the timing semantic assumed by the control application. An analysis of the AADL mode change protocol is also provided, exposing a translation process that takes as an input an AADL model and produces as an output a time Petri net. We show how an AADL model transformation provides a formal model for model checking activities and we suggest that model transformation provides useful support to improve the integration of formal verification in an industrial engineering process. As a case study we use an implementation of a UDP /IP protocol stack.

Despite numerous advances, building High-Integrity Embedded systems remains a complex task. They come with strong requirements to ensure safety, schedulability or security properties, one needs to combine multiple analysis to validate each of them. Model-Based Engineering is an accepted solution to address such complexity: analytical models are derived from an abstraction of the system to be built. Yet, ensuring that all abstractions are semantically consistent, remains an issue, e.g. when performing model checking for assessing safety, and then for schedulability using timed automata, and then when generating code. Complexity stems from the high-level view of the model compared to the low-level mechanisms used. In this paper, we present our approach based on AADL and its behavioral annex to refine iteratively an architecture description. Both application and runtime components are transformed into basic AADL constructs which have a strict counterpart in classical programming languages or patterns for verification. We detail the benefits of this process to enhance analysis and code generation. This work has been integrated to the AADL-tool support OSATE2.

Distributed Real-Time Embedded (DRE) systems have critical requirements that need to be verified. They are either related to functional (e. g. stability of a furnace controller) or non-functional (e. g. meeting deadlines) aspects. Model-Driven Engineering (MDE) tools have emerged to ease DRE systems design. These tools are also capable of generating code. However, these tools either focus on the functional aspects or on the runtime architecture. Hence, the development cycle is partitioned into pieces with heterogeneous modeling notations and poor coordination. In this paper, we propose a MDE-based process to create DRE systems without manual coding. We show how to integrate functional and architecture concerns in a unified process. We use industry-proven modeling languages to design functional elements of the system, and automatically integrate them using our AADL toolchain.

This paper describes the required model transformations for a seamless use of the models which are architecturing real-time systems. At the highest level of abstraction, we stand in the analysis phase, which consists in producing the set of static and dynamic models of the system. We use the MDA process that allows MARTE PIMs models transformation into AADL PSMs. Therefore we have chosen ATL for generating AADL models from models that belong to a subset of MARTE which corresponds to the (same) main concepts in AADL.

AADL is an architecture description language intended for model-based engineering of high-integrity systems. The AADL Behavior Annex is an extension allowing the refinement of behavioral aspects described through AADL. When implementing Distributed Real-time Embedded system, fault tolerance concerns are integrated by applying replication patterns. We considered a simplified design of the primary backup replication pattern to express the modeling capabilities of AADL and its annex. Our contribution intends to give accurate description of the synchronization mechanisms integrated in this example.

Designing reconfigurable yet critical embedded and complex systems (i.e. systems composed of different subsystems) requires making these systems adaptable while guaranteeing that they operate with respect to predefined safety properties. When it comes to complex systems, component-based software engineering methods provide solutions to master this complexity (ldquodivide to conquerrdquo). In addition, architecture description languages provide solutions to design and analyze critical and reconfigurable embedded systems. In this paper we propose a methodology that combines the benefits of these two approaches by leaning on both AADL and Lightweigth CCM standards. This methodology is materialized through a complete design process and an associated framework, MyCCM-HI, dedicated to designing reconfigurable, critical, and complex embedded systems.

The strong convergence of modeling languages, development processes and methodologies for developing real-time systems underlines a set of requirements for a more methodical approach. This paper presents the issues related to the lack of method in the field of software engineering for real-time systems (in particular, avionic systems). We mainly describe what converge in the new methodologies that are quite adopted but not implemented as methods. The unified process is analyzed and revisited in order to support the new types of requirements that we have identified to require the integration of formal methods, a proof-based system engineering approach in the first steps, and a refocusing on the model-driven development.

Since UML 1.4 (the Unified Modeling Language, version 1.4), executable UML relies on the Precise Action Semantics for UML. The role of the action semantics is to provide the specification of actions. The UML has actions and activities, but no standard concrete syntax for describing them. Therefore, an action language is required to map higher- level constructs to the actions. This action language has to encompass both primitive actions and the control mechanisms provided by behaviors. In our paper, we present the advantages of adopting a more generic action language, in order to raise the level of abstraction. For the particular do- maine of Distributed Real-time Embedded (DRE) Systems, we have identified a need for formal verifications that leads us to implement a generic action language with formal features.

Building middleware for distributed applications is a complex task, mixing antagonistic concerns: heterogeneity, performance, reliability, quality of services. Optimization and fine-tuning of middleware for a particular application is even a harder task, usually done manually or through complex design patterns. The advent of "schizophrenic'' middleware which separates concerns between distribution model, communication protocols, and their implementation by refining the definition and role of "personalities'' brought some elements to solve this problem by enabling full tailoring of the middleware by the developer. In this paper we extend this approach to full automation by generating middleware from an architectural model of the system expressed in a modeling language. This enables precise tuning and configuration of the middleware by generating exactly the required code, prior to runtime. We finally show how this approach fits the requirements of high-integrity or real-time distributed systems.

Building distributed deal-time embedded systems requires a stringent methodology, from early requirement capture to full implementation. However, there is a strong link between the requirements and the final implementation (e.g., scheduling and resource dimensioning). Therefore, a rapid prototyping process based on automation of tedious and error-prone tasks (analysis and code generation) is required to speed up the development cycle. In this article, we show how the AADL ( Architecture Analysis and Design Language ), which appeared in late 2004, helps solve these issues thanks to a dedicated tool suite. We then detail the prototyping process and its current implementation: Ocarina.

Architecture models are built in parallel with applicative models, all along the development process. Since they equally refer to software and hardware components in which they are implemented, these models call for more heterogeneous design languages, with a larger granularity range too. At the level of design and verification languages, some standards have risen up, like UML, AADL, but none of them is driven by a standard methodology. To be able to follow the requirements traceability, at each step of the life cycle, we need a methodology that states for bidirectional links between each granularity level and each development level. In this article, we propose an approach based on systematic reuse of low-level concepts (borrowed from an algorithm language like +CAL and a programming language like Ada) into encapsulated algorithm structures which are implemented into the highest conceptual levels of development (e.g. from the UML and AADL component models). These structures are only activated and enriched as they advanced with the life cycle. Therefore, some new concepts presents from the beginning of the design, will play an important role in the further development steps without being explicitly expressed from the beginning.

Requirements of high integrity systems now encompass distribution mechanisms along with strong functional and non-functional features (run-time support for hardware, dependability, safety, analyzability). In this paper, we show how model processing help addressing such needs. We present a generic distribution model suitable for high integrity systems, and demonstrate how a high-level modeling deployment view allows one to greatly reduce the model complexity. Finally, we conclude by assessing a case study

Heterogeneous non-functional requirements of DRE system put a limit on middleware engineering; building an application-tailored middleware becomes a challenge. In this paper, we show how we use the PolyORB middleware and its architecture as a framework to implement DDS, the data distribution services (DDS) recently published by the OMG. We demonstrate how the architecture proposed by PolyORB enables a rapid implementation of this specification, and allows for extreme tailorability to support application requirements

Distributed real-time embedded systems (DRE) increasingly rely on COTS middleware to meet their distribution needs. Yet, there is a technology gap between the design of COTS middleware and the high-integrity constraints of real-time engineering. This puts a limit on the adoption of middleware by system families such as space or avionics. In this paper, we present our current work on the "schizophrenic middleware architecture", a highly tailorable middleware architecture, and its implementation PolyORB. We illustrate how it allows for support of real-time engineering guidelines, enforces determinism, allows for modeling and verification.

This paper describes how GLADE, our implementation of the Ada 95 Distributed Systems Annex, can be used to build large object-oriented real-time distributed systems. In addition to the powerful distribution features included in the Ada 95 language itself, we provide extensions to help the programmer build robust and failsafe distributed applications.

Presents a new algorithm for distributed shared virtual memory dedicated to diskless embedded systems. In this context, we adapt an existing algorithm in order to include a page replacement mechanism. We also propose a memory partition to optimize memory space use. In conclusion, our algorithm has a complexity comparable with the initial one.>