Antonio Monzón

José-Luis Fernández-Sánchez

An Ontological Representation of the Characteristic Problems of Real-Time Systems

Keywords: Software Architecture, Real-Time, UML, Concurrency, Deadlock

 to support concurrency problems detection.

Introduction

Software Architecture Modelling is a relevant subject for the production of real-time systems. The development of AADLs in the last years has permitted to represent both structure and behaviour of such systems with very few details of the implementation. The utilisation of UML notation to represent software architectures in combination with Model Driven Engineering ideas has become usual in the field [START_REF] Tanguy | Model driven engineering for embedded real-time systems[END_REF]. Regarding this new approach to the problems of software architectures, some authors [START_REF] Egyed | Instant Consistency Checking for the UML[END_REF] have highlighted the intrinsic consistency problems of UML and have proposed rules to assure consistency of models based on UML abstractions. Other approaches to software architecture [START_REF] Oquendo | Formally Modelling Software Architectures with the UML 2.0 Profile for π-ADL[END_REF] focus on the notational concerns and the importance of visual capabilities to help engineers representing systems. An architectural style [START_REF] Drake | Description of the MAST Model[END_REF][10] is a consistent set of modelling abstractions with architecting rules to plug constructive elements to build system models. This approach is very promising because the style wellformedness rules assure a minimum consistency level. Nevertheless, the capability of representing certain aspects of the system is not powerful enough to make an architectural style really useful. In addition to the notational or syntactic capabilities of a style, it is also required to provide guidelines and rules to help software architects to produce reliable models concerning to particular problem domains. In the field of real-time and embedded software, formal methods have been developed to specify and verify system properties. One of the objectives of such formal methods can be, for instance, deadlock avoidance [START_REF] Alves | A Topological Formal Treatment for Scenario-based Software Specification of Concurrent Real-time Systems[END_REF][4] [START_REF] Huang | Predictable real-time software synthesis[END_REF]. The main drawback of formal methods is that they are intrinsically complex and difficult to apply in industrial environments. In this context, PPOOA architectural style [10] has been selected because it combines UML notation, MDE concerns, it allows software structural analysis and it is particularly useful to explicitly modelling concurrency aspects. In addition to the engineering knowledge required to assess the quality of a model, it is also worth providing computer-aided architectural tools to support the automation of the engineering rules. Although many CASE tools exist in the market to support the software design activities, most of them focus only on the notation issues with very little concern on the engineering rules support. There are a few commercial tools in the market [START_REF]Real-Time Studio[END_REF] [START_REF] Telelogic | Rhapsody System Designer[END_REF] supporting real-time characteristics, but with no specific feature to analyse concurrency problems. For this reason a gap exists to cover the engineering support in appropriate modelling tools. In order to ease the process to understand the problem context where the problems take place, an ontological approach has been followed. The proposed ontology classifies the problems in two main categories: concurrency and structural problems.

PPOOA Architectural Style

A software architectural style encapsulates decisions about its building elements and emphasizes important constraints on the elements and their relations. The PPOOA (Pipelines of Processes in Object Oriented Architectures) architectural style for RTS provides constructive elements such as components and coordination mechanisms [10]. Constraints on building elements are represented in the metamodel and by guidelines. These guidelines not only represent the semantics of the style, they are also helpful for the software architect using the style. The UML stereotypes are extended with the elements of the PPOOA style (periodic and aperiodic processes, controller objects, and coordination mechanisms). UML Activity diagrams are also adapted for PPOOA style requirements, specifically modelling resources and considering scheduling points [START_REF] Fernandez | Extending UML for Real-Time Component Based Architectures[END_REF]. The PPOOA architecture diagram is used instead of the UML component diagram to describe the structural view of the RTS architecture. Coordination mechanisms, used as connectors, are also represented in the architecture diagram. The RTS behaviour view is supported by the "Causal Flow of Activities (CFA)" representation. A CFA represents a system internal view of the flow of activities performed by the system in response to an event. PPOOA uses the UML activity diagram with partitions to support allocation of activities to the architecture component instances. For the purposes of this paper, these are the relevant abstractions used in PPOOA for explicit concurrency modelling:

Taxonomy of Architectural Problems

Although the problems identified in the proposed taxonomy are well known in real-time systems community and have been extensively treated in the past, there is a lack in the consideration of all of them as a consistent set of engineering problems to be detected and mitigated in the architecture definition phase. Main stress is here on the classification of the problems (see Figure 1) versus the classical approach of handling them as isolated problems in very particular conditions and usually at late implementation stages. The first category is further classified into three subcategories: Deadlock, Starvation and Priority Inversion. Although the detailed justification for this selection is explained in a specific section, these problems have been particularly chosen because they are especially dangerous for the operation of system under time-constraints, as they cannot be detected in design time. They usually appear in execution time, even if the implementation is free of defects. In addition to the classification, the main factors for the occurrence of such problems have been identified in the metamodel. They are discussed in detail in this paper. In the structural problems category two main subcategories are proposed: Lack of Cohesion and High Dependency. Both concepts are relevant for the proper design of architectural components. The second one is further sub-divided into other two categories: High Coupling and Wrong Hierarchy. The relevant information for the development of this work comes from the following inputs (captured from PPOOA models): Low cohesion components should be divided into others more cohesive. This factor has system robustness and maintainability implications, so it is clearly under the scope of this work.

In PPOOA, cohesion involves the responsibilities allocation to components. A component is considered cohesive if its behaviour is internally cohesive. The behaviour of a component is characterized by its interface, that is the set of all the operations contained in the components within the building element. The responsibilities are implemented in operations within components, according to the activities allocation represented in the CFAs. A component can be considered noncohesive when its constituents are non-cohesive. At an aggregated level, a building element can be considered non-cohesive when some operations of its interface have no relation with the others.

Low Cohesion Assessment in PPOOA

An algorithm outline to detect low cohesion in PPOOA models is proposed here: 1. Check the operations that implement the interface of an architectural element in the PPOOA static model and consider those that use attributes of different internal components. 2. If the total amount of such disjoined operations is high, then there is a lack of cohesion. 3. Assign a percentage value to the lack of cohesion, considering the number of disjoined operations with respect to the total number of operations.

High Dependency -High Coupling

In Component Based Design, coupling is a property applicable to a set of components, which represents the number of dependencies among the individual components of a subsystem. A component depends on another when an operation of it needs to invoke an operation (or to access an attribute) of the other to perform its internal computation. When many components depend on only one, it is considered that there is a high coupling in the set. Therefore, the set is very sensitive to changes in the invoked component. Low coupling is desirable, and high coupling should be avoided by distributing the responsibility of the invoked component among the rest of components. Once again, this factor has impact on the maintainability of the system.

High Coupling Assessment in PPOOA

An algorithm outline to assess high coupling in PPOOA models is proposed here: 1. Check the PPOOA static model and count the number of dependencies of each building element. 2. If there is one building element with more than 50% of the average dependency ratio, then the model could be considered highly dependent. 3. Assign a percentage value to the coupling factor, considering the number of high dependency components with respect to the total number of components in the model.

High Dependency -Wrong Hierarchy

Hierarchy is a general mechanism for the organization of a system in different aggregation layers, to deal with complexity at each level. It is a powerful mechanism while designing systems, but should be used according to the following rules: with the immediate lower level, not two levels below. Although this one could be considered a less relevant factor, it has influence on the overall design consistency, and thus can also affect the maintainability.

Wrong Hierarchy Assessment in PPOOA

An algorithm outline to assess wrong hierarchy in PPOOA models is proposed here:

1. Check the hierarchy consistency rules in the PPOOA static model. 2. If the total number of violated rules is high then the hierarchy can be considered inappropriate. 3. Assign a percentage value to the wrong hierarchy factor, considering the number of violated rules with respect to the total number of rules.

Concurrency Problems

This kind of problem deals with the coordination of tasks in a multitasking scenario. Multitasking is a computing paradigm considering tasks that execute in parallel, sharing common resources (i.e. CPU, memory, database, etc.). At a given time only one task is permitted to be using the shared resource. Therefore multitasking computing entails using scheduling mechanisms to decide which task may be running at the resource at a given time and when other waiting tasks can get their turn to use the resource. A first kind of multi-tasking (known as cooperative) permits releasing resources only to the tasks belonging them. The issue with this kind is low efficiency. A common alternative to this strategy is pre-emptive multitasking. Pre-emption is the ability of an operating system (RTOS) to pre-empt or interrupt the currently scheduled task in favour of another task. In this case the context switch does not depend on the active task but on the RTOS. Making a multitasking system pre-emptive is positive as it allows the RTOS to guarantee that each task accesses the shared resources, but it has also some drawbacks that should be addressed to properly design a system. The most dangerous implication of pre-emption is the race condition. A race condition is in general the result of nondeterministic ordering of a set of events [START_REF] Tanenbaum | Modern Operating Systems[END_REF]. In computing, a race condition is an undesirable situation that occurs when a task attempts to perform two or more operations at the same time, but because of its nature, the operations must be performed in the proper sequence, otherwise the race condition entails negative consequences such as data corruption. In non pre-emptive systems, there is no risk of data corruption as only one task can access a resource until completion. But in preemptive systems, the context switch forced by the RTOS may derive in the usage of corrupted data by some task. The most common way to handle race condition implications in pre-emptive systems is the mutual exclusion of resources. Mutual exclusion takes place when only the active task can access the resource at a given time. When a resource is protected for mutual exclusion, the rest of tasks are paused until the active task finishes to use the resource. The typical mechanisms to implement mutual exclusion are the binary semaphores and mutexes. Although it seems that the most severe problem associated to the race condition is solved with the mutual exclusion mechanism, some additional problems arise when using this technique, particularly: Starvation, Deadlock and Priority Inversion (Priority Inversion). All of them lead to execution time penalties and are very difficult to detect and prevent unless a proper architecture is created to handle them.

Table 1: Concurrency Factors

The factors affecting these problems (see Table 1) are: 1. Mutual exclusion condition: When two or more tasks are trying to use a shared resource, and a mutex for this resource is activated, only one task can use the resource and the rest must wait until the active task releases the resource. 2. Hold-and-wait condition: Tasks already holding resources are permitted to request new resources. 3. Non pre-emption condition: This condition takes place when only the task holding a resource can release it. 4. Circular wait condition: It happens when tasks are in a circular chain and waiting for a resource held by the next task in the chain. 5. Priority factor: High priority tasks lock lower priority ones to access resources.

Deadlock

Formal definition of deadlock is: "A set of tasks is deadlocked if each task in the set is waiting for an event that only another task in the set can cause." [START_REF] Tanenbaum | Modern Operating Systems[END_REF] In computing world, deadlock refers to a specific condition when two tasks are each waiting for the other to release a resource, or more than two tasks are waiting for resources in a circular chain. According to Coffman [START_REF] Coffman | System deadlocks[END_REF], the four necessary and sufficient conditions for deadlock are: Mutual Exclusion, Hold and Wait, Non Pre-emption and Circular Wait. The simplest example of process deadlock can be represented by two processes (A and B) trying to access two shared resources (R and S). In order to highlight the deadlock, Holt's graphs [START_REF] Holt | Some Deadlock Properties on Computer Systems[END_REF] can be used to show the mutual dependency (cycle) of both processes. There are essentially three design decisions that may influence the four necessary and sufficient conditions for deadlock (see Figure 3): resource constraints, coordination protocol and process dependency. A resource constraint is an intrinsic characteristic of the resource that may affect its synchronisation behaviour (i.e. RAM memory is a preemptable resource). The coordination protocol describes the way a resource may be accessed by different tasks regarding, for instance, the exclusion or task ordering policy of a coordination mechanism. This protocol defines in fact the coordination mechanism operation. The task dependency represents the need of some tasks to use the computation results from other tasks. The algorithm outline proposed to assess deadlock risk in PPOOA models is: 1. Search dependency cycles in architectural diagrams with protected resources.

2. If a cycle exists, check the CFAs to find sequence protocol information about the type of dependency of each task.

3. When each task in the cycle holds at least one resource and wants another, then deadlock may occur. 4. Assign a percentage value to the risk of deadlock based on the amount of dependency cycles detected. If no cycle is detected, then deadlock risk is zero.

Starvation

Starvation is a multitasking problem, where a task is perpetually denied to access the resources it needs for its execution [START_REF] Dijkstra | Hierarchical ordering of sequential processes[END_REF].

Starvation is similar in its effects to deadlock, as the consequence is that a task does not run. In the case of deadlock the cause of this situation is task interdependence. Nevertheless, starvation occurs when a high priority task holds a resource other with lower priority needs. If no external event happens the high priority task may not release the resource and the low priority one remains waiting indefinitely.

The problem now lies on the scheduling policy. Scheduling is supposed to allocate resources so that no task lacks necessary resources perpetually. But a wrong allocation policy may cause task starvation. For this reason it is necessary to detect the occurrence risk of this problem. This situation may happen if there are several tasks of high priority that use one protected resource and just one of low priority depending on it. The low priority one may remain indefinitely waiting because the semaphore shall never let it run, due to higher priority tasks in the waiting queue.

Starvation Assessment in PPOOA

An algorithm outline to assess starvation in PPOOA models is proposed here: 1. Check the priority values of each task in a PPOOA static model and consider those protected resources where there are at least one low priority and one high priority task trying to access them. 2. Check if all the semaphores protecting the identified resources (in the CFAs) have a Release activity per each Acquire activity. If not, a potential risk of task starvation exists.

3. Assign a percentage value to the starvation risk according to the number of resources with high and low priority tasks and with no releasing activities in their CFAs, with respect to the total number of resources in the model.

Priority Inversion

Conceptually, priority inversion occurs when a low priority task holds permanently a shared resource needed by another high priority task.

A practical definition of priority inversion is [START_REF] Barr | Embedded Systems Glossary[END_REF]: "An unwanted software situation in which a high-priority task is delayed while waiting for access to a shared resource that is not even being used at the time. For all practical purposes, the priority of this task has been lowered during the delay period. Priority inversion arises when a medium-priority task preempts a lower priority task using a shared resource on which the higher priority task is pending. If the higher priority task is otherwise ready to run, but a medium-priority task is currently running instead, a priority inversion is said to occur." Priority inversion is not a problem itself, because the immediate consequence is just that priority precedence of tasks is temporarily inverted. The real problem related to priority inversion takes place when the task under inversion must meet a critical deadline. This may cause a catastrophic system failure and for this reason it is important to identify potential occurrence of such problem to be mitigated at early design stages. Typical workarounds to mitigate priority inversion deal with the temporary modification of task's priority while accessing protected resources. There are classically three priority allocation protocols that handle priority inversion issue: Priority Ceiling Protocol, Priority Inheritance Protocol and Highest Locker Protocol [START_REF] Douglass | Real-Time Design Patterns -Robust Scalable Architecture for Real-Time Systems[END_REF]. The objective of such protocols is not avoiding priority inversion to happen, but keeping it bounded to assure that high priority tasks meet their critical deadlines. Priority inversion is an execution time problem very difficult to identify in design. Regarding the fact that only structural information is considered in PPOOA static diagrams, the objective of this work is just to highlight the potential risk of priority inversion in preliminary outlines of an RTS architecture.

Priority Inversion Assessment in PPOOA

As priority inversion is a problem associated to relative priorities of tasks accessing to protected resources in execution time, the only information valuable to identify occurrence risk is the task priority attribute.

An algorithm outline to assess Priority Inversion potential risk in PPOOA models is proposed here: 1. Identify all the tasks accessing protected resources in the PPOOA structural diagrams (only those tasks with dependency relations on resource building elements, protected with semaphores are susceptible to be in danger to suffer priority inversion).

2. Check the priority values of the tasks with dependencies on common resources. If there are tasks with high and low priority values trying to access a shared resource, and simultaneously there are one or more tasks of medium priority running (not necessarily accessing the shared resource), there is a potential risk of priority inversion.

3. Assign a percentage value to the priority inversion risk according to the total number of resources with such tasks.

Engineering Guidelines

The objective of this work is to propose mechanisms to detect occurrence possibility of the problematic situations described in this paper with no need to execute software or to specify execution times.

Once detected the problems, some engineering guidelines are proposed to reduce the likelihood of such problems. Some engineering guidelines to produce reliable system models, regarding the problems identified in this work, can be summarised as follows:

• Deadlock: Avoid cycles when protected resources are shared by several tasks concurrently.

Supporting Tool

PPOOA architectural style is currently supported under Microsoft-Visio®. This tool is flexible enough to extend its functionality to support additional engineering features to assess the problems identified in this work.

The strategy selected was to use an XML export add-on to generate an intermediate file that contains the dependencies and additional time-related information necessary for the algorithms to assess the models. An example of such XML file is shown in Figure 6. This feature is also used to export PPOOA -Visio models to RMA tools for schedulability analysis (i.e., Cheddar RMA analyser [START_REF]Cheddar RMA Analyser Tool[END_REF]). The Architecture Monitor is conceived as a tool to help system architects to assess the structural and concurrency robustness of their designs. But perhaps the most important aspect is that it enables them to compare the relative robustness of several design alternatives, in order to better make a decision on the most appropriate one.

Conclusions

A set of techniques of static analysis has been proposed to detect some characteristic problems of real-time systems, without performing any code execution or simulation. The objective is to early detect problems and to propose guidelines to modify designs in order to mitigate their occurrence. This paper has highlighted the relevance of both structural and concurrency problems on the quality of real-time systems models. Main conclusions are:

• The traditional approach of trying to solve separately concurrency problems at late stages of the system life-cycle is counter producing in terms of rework effort and final product quality. • The utilisation of a high level architecture modelling notation enables the identification of important concurrency problems at very early stages of the system design lifecycle to make decisions on them. • The ontological approach proposed provides a better understanding of the typical problems focused, allowing the detection of many of them through the usage of static analysis techniques. In order to effectively detect the problems identified in the ontology, a CASE tool shall be created to automatically analyse architectural models. This tool shall also implement the engineering guidelines to propose the designers the improvements in their models required to mitigate the problems addressed, and shall allow them to perform trade-off analysis among different architectural solutions.

Figure 1 :

 1 Figure 1: Taxonomy of Architectural Problems Architectural problems are primarily classified in two main categories, regarding their relation to tasks synchronisation: Concurrency and Structural Problems. The first category is further classified into three subcategories: Deadlock, Starvation and Priority Inversion. Although the detailed justification for this selection is explained in a specific section, these problems have been particularly chosen because they are especially dangerous for the operation of system under time-constraints, as they cannot be detected in design time. They usually appear in execution time, even if the implementation is free of defects. In addition to the classification, the main factors for the occurrence of such problems have been identified in the metamodel. They are discussed in detail in this paper. In the structural problems category two main subcategories are proposed: Lack of Cohesion and High Dependency. Both concepts are relevant for the proper design of architectural components. The second one is further sub-divided into other two categories: High Coupling and Wrong Hierarchy. The relevant information for the development of this work comes from the following inputs (captured from PPOOA models): • Dependencies: Usage relations among architectural components (UML-PPOOA Architectural View). • Attributes: Values of the real-time attributes defined for the components (UML-PPOOA Architectural View). • Semantic Information: Problem Domain related information (i.e., responsibilities implemented by a component).

Figure 2 :

 2 Figure 2: Holt's Graph

Figure 3 :

 3 Figure 3: Deadlock Characterization Circular waiting depends essentially on the tasks interdependency. Tasks must be in a dependency cycle to have a circular waiting. Hold and wait condition depends on the coordination protocol as it describes the way tasks are permitted to access resources. Non-preemption and mutual exclusion conditions may depend on resource constraints and on the coordination protocol. 5.1.1 Deadlock Assessment in PPOOA Figure 4 represents a set of tasks and resources with a characteristic deadlock risk. In PPOOA, tasks are represented through architectural elements of the type "Process" and resources in the diagram are represented by the

Figure 4 :

 4 Figure 4: Deadlock in a PPOOA Architectural View Structural diagram must be complemented with a CFA diagram (Figure5) to evidence that hold-andwait condition takes place. In the diagram it is necessary that the tasks in the cycle (D, E and G) hold and want the resources in sequence. This sequence involves that each task in the cycle is waiting and holding the resources. For the purposes of this work the most relevant evidence of deadlock risk is the cycle detection in the structural diagram. If no cycle exists in this kind of diagrams, no deadlock may occur. The proposed characterization takes this fact into account to check first for cycles. In real world designs the identification of cycles is not so obvious as in the example. For this reason cycle detection must be implemented in an algorithm.

Figure 5 :

 5 Figure 5: Deadlocked Processes in a CFA

Figure 6 :

 6 Figure 6: XML File Example An HMI prototype of the engineering tool to support the automatic assessment of the problems is shown in Figure 7.

Figure 7 :

 7 Figure 7: Architecture Monitor Tool


Sylvain Baro

A High Availability Vital Computer for Railway Applications: Architecture & Safety Principles

Keywords: Availability, Safety, Redundancy, Computer, Railway Applications

The computers used for Railway Automation have increasing their level of safety and availability, especially for providing expected answer to Unattended Train Operation.

To achieve these demanding requirements, relevant answers have to be addressed. In this article, we first present the architecture of our computer, based on a vital coding processing, and its embedded redundancy feature, which both allow the achievement of an efficient architecture providing the high availability requested by the above mentioned Railway Applications. We then present the principles used in the safety design and used to bring out the safety evidences. We will specifically highlight the safety and performance issues raised by assembling two single vital computers into a redundant configuration. Nevertheless, we have to stress that in our choice of design, the redundancy is used only to address the availability goal.

Introduction

The computers used for Railway Automation have increasing needs on safety and availability. In the case of Unattended (Manless) Train Operation those requirements became unconditional; the availability goals are very high to avoid any major disruption of operation. Such operation cannot afford a total stop of traffic due to any single failure. In addition to these high availability requirements, the complexity of functions and the system performances are increasing significantly. To achieve these demanding requirements, an appropriate answer has to be given. The computer design cannot be anymore seen as a single computer with a redundancy, but as a pair of computers providing a vital fault tolerant system. Our redundancy protocol based on fault tolerant principle makes two redundant computer units work as symmetrically as possible. The achievement of the consistency of the two units makes possible to switch to any computer at anytime, without taking any care, neither at the application level nor at the system level. This valuable point has the benefit of reducing the complexity of the system and the safety analyses. We can say that the switching process is seamless from the functional part of the application and from the system point of view. In order to understand the specificities of our redundancy protocol, we first introduce the architecture of our computer, based on a vital coding processing (Sect. 2), without the redundant architecture. We then present our previous redundancy principles (Sect. 3). We finally introduce the integrated redundancy feature, which provides the high availability requested by the above mentioned Railway Applications (Sect. 4), starting from the principles and goals, then switching to the inner design. For conclusion, we address the benefits and limitations of our vital fault tolerant system.

Vital Computer Overview

The DIGISAFE© XME vital computer is the upgrade of the DIGISAFE© platform, used on railways system automation since 1989: SACEM systems [5], then on METEOR (Paris L14, in Unattended Train Operation) in 1998, and New-York Canarsie Line in 2005. This vital computer is based on vital coding techniques using a single processor. These techniques guarantee that any computation which does not comply with the relevant specified software will be detected in a safe manner. In other words, either the source code is compiled, linked, uploaded, and executed as intended; or the vital computer detects the error (with a very high probability) and set itself in a safe mode.

Architecture

The DIGISAFE vital computer is the platform used in CBTC railway applications for the onboard vital controller and for the wayside vital controller. This computer is used to fulfill SIL4 sub-systems requirements [2]. The DIGISAFE© architecture has been described precisely in [4]. For the comprehension of this paper, we nevertheless provide a short description hereafter. In order to fulfill this role, DIGISAFE© secures all the processing from the inputs to the outputs, including the different layers of the software architecture. The vital analog wired inputs are processed by dedicated vital boards, which convert the input signal into a coded time-stamped message, which in turn is sent to the inner layers of processing. The acquisition and the coding of the inputs are both consistent with the SIL4 safety level requirements. Cyclically, the vital application is triggered. The inputs are then used in regular computations which produce finally the outputs. In order to check that these computations are handled properly with respect to the source code, all vital data are coded. Each vital variable consists in two fields. The first field is the functional part X f , which contains the requested value of the variable (an integer, boolean, array...) and it is processed by regular computation. The second field is the coded part X c of the variable, it contains all the information required to secure the computations and values, it is processed by dedicated vital algorithms. The coded part contains a static signature representative from the occurrence of the variable and of the operations used on the variable, an arithmetic part representative from X f , and a timestamp in order to guarantee the freshness of the variable.

Figure 2: Logical tool-and execution-chain Any data, message, equipment is called off-code when the variable (X f, ,X c ) is not consistent with regard to the code, and in-code when it is. To make easy the use of such coded variables, and to use them as regular variable at the application level, primitive operations on these data (OPELs) are defined in order to manipulate the code itself. This also brings the benefit of encapsulating the manipulation of the code in a dedicated part of the computer.

To make the check easier, a specific tracer is used. It allows propagating the code status. If one computation leads to an off-code status, the tracer remains off-code. Vital digital messages are transmitted between equipment. These messages are transmitted through non-vital layer seen as black boxes, but are packed in a specific form, called a vital message. The packing function uses a specific code in order to check the integrity of the message Only vital applications are able to modify or create a message without damaging it. A damaged (off-code) message is detected by the receiver, thanks to the code. Given equipment are only able to pack in-code messages if they are themselves in-code. The analog wired outputs are first worked out by the Vital Application, and then are sent to the DIGISAFE bus, in order to command through the vital output boards, the vital output signal. The vital output data is sent with its code and a time-stamped. The output board applies functionally the output. A vital checking is made at any time in order to verify the consistency of the actual status of the output and the expected status considered at the application level. To do so, the dynamic controller (CKD) reads vitally the code of the actual status and checks if the value complies with the expected value. If a discrepancy is detected, the outputs are de-energized (vitally guaranteed). Dedicated sensors can be used with the DIGISAFE computer. The most common are the odometer (coded phonic wheel, or optical speed sensor) and the transponder reader. Both are vital, precise, and

Properties

The safety properties of this architecture are numerous:

The safety proof of the computer does not rely on the digital component of the computer (processor, memory, network, etc.) but only on the protection offered by the code, which complies with the SIL4 safety levels requirements; This safety principle guarantees that any error which may occur on any vital part of the application, would lead to an error in the vital outputs (and the messages). It will cause these outputs to be offcode. This also leads to the fine property that all the software and data which have an impact on the values of the vital outputs are required to use the OPELs. In other words, the software parts which do not use the OPELs do not need to be considered during the safety analyses on the application. The principles used for the time-stamping of the outputs code have the property that this code can only be consistent with the values of the outputs if the outputs are applied at the proper time. This allows (together with a vital clock) to guarantee that the proper cycle time is enforced.

To sum up, if anything leads to an error during the processing of the cycle, the outputs will be off-code, and de-energized: one DIGISAFE computer guarantees alone the safety. This is indeed sufficient to guarantee the safety behavior of our applications. Nevertheless, the railway applications become more and more complicated, and need more than a simple control/command calculator: the computers involved in the operation of a line cannot be reset without severely impairing the system availability of the line. This is particularly true for Unattended Train Operation, when a reset of an onboard computer could paralyze the train in a tunnel, until manual recovery handled by an operator. For this reason, redundancy is required to prevent a single failure to impact the passenger service.

Applicative Redundancy

Our previous architecture (DIGISAFE for the Meteor -Paris L14) already used redundancy. On this platform, redundancy is handled through two redundant computers (each one being a DIGISAFE computer), among which at most one can be active (vitally guaranteed by the hardware). Both units are able to communicate through a serial link. The outputs are merged within a hardware OR gate. In all the Vital Application, in every safety functions the following is required:

• Defining the function behavior, when the unit is active.

• Defining the function behavior, when the unit is passive.

• Transmitting the proper data to the redundant unit, in order to guarantee that the passive unit has the proper information to be able to switch to the active state.

• Analyzing in order to find if a sequence of switching over is able to lead to an unsafe behavior of the system.

This leads to the interleaving of the functional part of the application with the redundancy processing; adding complexity to the design and making more difficult the safety analyses of the functions. After Meteor, another approach was investigated, in order to implement a completely integrated redundancy solution, relying on the same hardware, and completely seamless at the application level.

Integrated Redundancy

The main principle governing the design of the integrated redundancy function is the complete separation between the redundancy management and the software application. This leads to an encapsulation of the applicative software in the redundancy manager (Sec_Red), as seen on Fig. 3. All the inputs are provided to Sec_Red which is able to modify them depending on the values of these same inputs for the remote unit, and depending on its internal state (redundancy mode). Each application then computes its outputs, modifying its internal states, but this computation only happen if allowed by redundancy. Lastly, the outputs are provided to Sec_Red to decide if permissive outputs are generally allowed, and if a given output must be force to a restrictive state. The goals of the integrated redundancy protocol are: 1. to be able to maintain a service in case of any single failure in the data processing chain; 2. to guarantee that the switching between both equipment are always safe (ensuring the consistence in the behavior of both units); 3. to separate the applicative processing from the redundancy algorithms (the applicative software is never aware if it is currently active or passive); 4. to become an "off the shelf" solution, usable on all our Railway Automation projects; 5. and of course, to be safe, compliant with SIL4 requirements, and certified by an independent assessor.

Overview of the functionalities

Sec_Red is governed by two modes: isolated or redundant. While isolated, only one unit (the Active unit) is running the Applicative Software and allowed to apply permissive outputs. While redundant, both units (Active and Passive) are running the Applicative Software, and both are applying their wired outputs, while only the Active unit sends messages to remote equipment. In this mode, it is essential to prevent inconsistent behavior or decisions of both units. Moreover, whatever the mode is, commutation between both Active/Passive states must always be safe:

• if the current mode does not authorize commutation, the equipment must fall back into a safe restrictive mode;

• the behavior of the newly Active unit must be consistent with the "promises" made by the former Active unit.

In order to maintain safety, the Applicative Software must also be executed at each cycle (on at least one unit), with fresh inputs and with a correct applicative context. The computed outputs must be applied in the cycle in which they are computed.

Assumptions

In order not to depend on the underlying applications, some assumptions must be made on the equipment and applicative software, especially on the semantic of the Inputs/Outputs. The first assumption (linked to our DIGISAFE platform), guarantees that being redundant is not necessary for safety.

H1: Each unit, on its own, always behaves safely. The redundancy protocol must be able to alter the I/O in a safe way. In particular, it must always be safe to change the value of a binary wired input or output to False, and it is always safe to lose a message.

H2: All binary wired I/O are "oriented" within the system: True being a permissive value and False being a restrictive value. H3: Discarding or losing a message (input or output) is always safe. Lastly, the initialization state of the applicative software must always be safe.

H4: The behavior of the Applicative Software must be safe (restrictive) at initialization time.

Hardware architecture

This redundancy protocol is also designed for a specific hardware architecture made up of two redundant units, each one being a DIGISAFE computer as described above in Sect. 2. Each of these computers are linked to its own wired inputs (which must generally be provided by the same equipment) and to the inter-equipment network (used for I/O messages).

One dedicated binary input is the Active/Passive input. This input is provided by a specific device guaranteeing (vitally) that the Active/Passive input can be Active (i.e. True) on at most one of the units at the same time.

The wired binary outputs of both redundant units are sent through an OR gate, which has the effect of choosing the most permissive. These two computers are linked together by a serial link used for the exchange of inter-units messages.

Both computers are also synchronized very precisely (~ 10 -5 s). However, this synchronization is not vitally guaranteed. It is of course necessary for the equipment to operate properly, but is not considered, as soon as safety is concerned. As for the safety part, the only property that is known is that the hardware clocks of both computers are safety clocks. The relative drift of both clocks is therefore vitally bound by a given threshold.

Synchronization and time

As mentioned in Sect. 4.4, the synchronization is very precise, but is not to be used for safety (simple failures may lead to a loss of synchronization). As far as safety is concerned, there is therefore no hardware synchronization. Nevertheless, in order to be allowed to compare the I/O of both units, a minimal synchronization is due. In order to enforce this, a counter is managed on each unit, namely the Vital Logic Clock (VLC). At initialization time, the passive unit synchronizes its own Vital Logic Clock to the active's one. At the beginning of each cycle, a message is exchanged between both units to compare both VLC. All messages sent between both units are also timestamped with the VLC. Hence despite there is no synchronization, it is guaranteed that as soon as the asynchronism exceeds one cycle, both units are unable to communicate with each other. This is sufficient to trigger the Passivation, in order to switch back to isolated (unredounded) mode, as described below in Sect. 4.9 4.6 Vital Inputs Two kinds of Vital Inputs must be handled by Sec_Red: wired binary inputs which can only be True or False; and Vital messages, sent by other equipment, which can contain any kind of values. These messages usually contain a vital header, with data such as an emission time-stamp, the identity of the sender and addressee, etc. As for the wired binary inputs, Sec_Red only distinguished redounded inputs from "unredundant" inputs. These "unredundant" inputs are left as is, and should usually be used only by the redundancy. Examples of these are the Active/Passive binary input, or the current state of the unit. On the other hand, redounded binary inputs are generally supposed to be the same for each unit. The inputs are exchanged (via the serial link), and each unit compare its own inputs with the remote unit's inputs. If a discrepancy is detected, it could either be because of a small asynchronism (lower that one cycle, as seen above), either because of a failure in the input acquisition. Because the acquisition of the inputs is vitally guaranteed by the DIGISAFE hardware, the only possible failure is to see the input at False while it should be True. Therefore in case of discrepancy, the permissive input is kept on both units, and sent to both Vital Applications. The particular case of an asynchronism together with a one cycle length restrictive input is detected, in order to prevent any restrictive state to be masked (see Fig. 3 As for the Vital Messages, they are compared between both units. If one of the units missed some messages, they are therefore sent, in order to ensure that all units will see all messages (a message is always considered as permissive data). Of course, either for the wired binary inputs, or for the message, this process of comparing and providing the more permissive data may sometime fail (e.g. serial link error). In this case, either restrictive inputs or local inputs are provided to the unit. This will cause that the Vital Applications of both units will not receive the same inputs, which in turn will lead to a discrepancy in the applicative contexts of both units. At the end, this will probably cause a discrepancy in the outputs emitted by both units. The redundancy protocol will not prevent the discrepancy to appear in the context. It will only react by controlling the inconsistent outputs, and by triggering a Passivation if the discrepancy lasts. This is described in Sect. 4.8 and 4.9. It is therefore never dangerous to introduce a discrepancy in the context, as soon as the inputs provided to each unit are fresh and correct.

below).

Application and Context

As seen above, it is not dangerous to introduce a discrepancy in the (variable) states of both units. There is nevertheless a property needed to define if the context is safe or not. The context can be defined as the set of all the vital variables handled by the Vital Applications, together with their values. A context is called well formed at the beginning of the cycle n, if one of the following conditions is true:

• either it is the initialization context of the Vital Application;

• or it was well formed at the beginning of the cycle n -1, the Vital Application has been executed during the cycle n -1, with fresh inputs;

• or the local unit is passive, the remote unit is active, the context of the remote unit at the beginning of the cycle n is well formed, and is equal to the context of the passive unit at cycle n.

This notion of well formed context is representative of an application which executes itself cycle after cycle, without ever missing to react to restrictive inputs. This leads to three different cases. At initialization time, as soon as the unit detects it is active, it is allowed to start executing the Vital Application. It is however checked that its context is the initialization context. The active unit must continue to execute the Vital Application at each cycle, to maintain a well formed context.

In the other hand, the passive unit does not execute the Vital Application. But as soon as both units are ready, the active unit starts to send "context slices" to the passive unit, which copies them. This process usually takes several cycles. This process is made such that after the transmission is finished, if variable of the context changed their values, the difference is then sent to the other unit. This may also take several cycles to finish. If the performance of the serial link is too low and the context evolves too quickly, it can even become a never ending story! This way of transmitting context is close to [1]. All this transmission and copy process is not vitally guaranteed. As soon as the transmission is finished, a "photography" representative of the contexts is taken. From this point, the passive unit starts to execute the Vital Application at each cycle. Its outputs are however not applied (maybe an error occurred during the copy of the context), but are compared at each cycle to the active unit's outputs. During a few following cycles, the "photos" are then compared, using a vital algorithm. If at the end of this comparison, the algorithm concludes that the "photos" where equal, both units are allowed to switch into redounded mode: from now, the passive unit start to apply its own outputs, and commutation is allowed and safe. It must also be noted that all this process is managed by the redundancy software itself. The only data available to the Vital Application is a boolean value indicating whether or not it must be executed! Even if both contexts are well formed, a discrepancy may appear between both units (usually because of a slight divergence between inputs which was not compensated by the protocol). It is therefore necessary to cover hazards at output level, as explained in the next section.

4.8

Vital Outputs As for the vital inputs, the outputs are either binary wired outputs, or messages sent to some remote equipment. Each unit sends its outputs to the remote one, and these inputs are then processed. If the unit is not allowed to apply its outputs, the wired outputs are forced to restrictive state, and the sending of the message is forbidden (this is for example the case if the unit is passive and isolated). In the other cases, the outputs are compared in order to detect discrepancy. Discrepancy on the Vital Output may appear for two reasons, mostly, it will be due to a divergence in the contexts. Sometime, it will also be caused by a failure in the boards responsible for the application of the vital wired outputs. In this case, the failure will be covered by the hardware OR gate which chose the permissive output between both (each unit being intrinsically safe, it is not hazardous to apply an OR in case of failure). The other case of discrepancy appears when there is a divergence between both applicative contexts. Three kind of hazard needs to be considered:

Hazard 1: outputs are erroneous w.r.t. the expected behavior. Example: the inputs indicate that an event occurs, which should cause the train to brake (application of a restrictive output "No Emergency Braking"), but due to a discrepancy, the output is not commanded to restrictive. This hazard is prevented by the following:

• the inputs are fresh and guaranteed to be safe;

• either the applicative context is well formed, or the outputs are forced to restrictive values;

• the execution of the Vital Application is guaranteed to be safe.

These three properties together guarantee that if the Emergency Braking is not applied on one of the units, it is necessarily because it does not need to be applied: therefore the error is done by the unit which commands the braking. Hence it is safe not to apply this braking.

Hazard 2: the wired outputs are correct, but the discrepancy introduces a dangerous antagonism.

Example:

The train is stopped in station, and the doors are closed. Unit A decides that the train should leave the station, therefore it Authorizes Traction. On the other hand, Unit B decides that the train should allow the passenger exchange, therefore it Unlocks the Doors.

Each of this behavior would be correct and safe on its own, but the OR gate would cause the equipment to allow both traction and door opening! In order to avoid this case, on each unit, Sec_Red compares the output of the local unit with the output of the remote unit (receive via the serial link). If no discrepancy occurs, the outputs of the local unit are applied as is. If a discrepancy is detected, for each output where this discrepancy exists, the transition from restrictive to permissive is forbidden (see Fig. 4). Hence if one the unit A was permissive and stays permissive (it was previously Authorizing Traction), while unit B switches to restrictive, the output of A (then the OR) is still permissive. But if A is not allowing to Unlock the Doors, and B did not, but now try to Unlock, the discrepancy will prevent B to switch to permissive. The Unlocking of the Doors is therefore prevented until the end of the discrepancy. It is easy to prove that this forbidding is sufficient to avoid the case of antagonistic outputs: a dangerous discrepancy can only occur at cycle n if it exists at cycle n -1, but it does not exists at cycle 0 when all the outputs are restrictive. In this case, the consequence of the forcing to restrictive is that the train will not be able to start up, neither to open door, until both units agree, or the passive unit is passivated (~ 1 s).

Hazard 3: unit B does not enforce the behavior promised by unit A.

Example:

The wayside equipment sends a (not vital) message to the onboard equipment asking if it can stop before a given limit. Unit A is active, and receives the message. It decides that stopping is possible. Therefore it memorizes a mandatory stop before the limit, and sends back to the wayside controller a vital message to acknowledge the fact that the train will stop. Unit B is passive, and does not receive the message (or decides that this stop is not possible). Therefore it does not memorize the stop and does not answer to the wayside equipment. When the wayside controller receives the message from Unit A, it is allowed e.g. to move a switch in downstream the acknowledged limit. But Unit A fails, a commutation is triggered, and B becomes active and isolated. The limit will not be enforced, and the train will probably run of the rails! In this case, the safety is enforced by Sec_Red by the specific processing of the vital output messages: a message is allowed to be send only if both units are trying to send it, and both messages are equal. In our example above, Sec_Red will therefore prevent A to send the message: even if the limit is overrun, the wayside would not have move the switch point because no permissive data would have been received.

Even if discrepancy on the outputs is covered, it is not good for the system to let them last: messages are not sent, wired outputs cannot move to permissive... the system cannot properly function while it occurs. It is therefore necessary when it occur to fall back in isolated mode when a unit alone (preferably the one that function properly) can take all the decisions. This is the purpose of the passivation function.

4.9

Passivation When the discrepancy on the outputs is lasting more than a few cycles (parameter), the process of passivation is triggered. The purpose of this process is to ensure that at the end, both units will be isolated. The passivation must occur quickly, in order to limit the number messages that will be lost during the discrepancy (if too many messages are lost, the addressee will consider that the communication is lost, and will step in a safe and restrictive mode). In the other hand, must also leave a sufficiently long time for a commutation to occur if needed: the commutation could take a few cycles before being effective. This is necessary if the active unit fails, and a discrepancy occur. The passivation must also guarantee that in all case (including the loss of the serial link, several commutations...) the passive unit will be isolated before the active unit. If the active unit is isolated before the passive, it will not control its output as requested in the Sect. 4.8. The passive unit will do its own control (against restrictive outputs) thus forbidding transitions from restrictive to permissive, but the active unit will have no limitation. The process of passivation is therefore conducted using state machines that are triggered in case of discrepancy, but also when a unit is not able to receive the inter-unit message used for the transmission of Sec_Red commands and states.

Conclusion

Sec_Red has been used for the first time on the onboard and wayside controllers for the resignalling into a CBTC system of the New York City Metro line L (Canarsie). It has since been used on two different kinds of equipment with a different design in both driverless metro lines (VAL) of the Roissy-Charles De Gaulle Airport in France. This succeeded in proving that the goal to develop an "off the shelf" product to manage the redundancy in our vital systems is reached. An issue remains on the processing of some particular inputs: the tachometers. These devices provide the on-board controller with precise (and safe) data on the kinematics of the train. Each kind of tachometer has particular properties on the timing of the data it provides. For availability purpose, it is also better to wire redundant tachometers on the redundant units, but this raises two issues:

1. The tachometers are precise, but subject to complex error models. Therefore the inputs provided by all the tachometers (at one given time) will never be equal. It is necessary for each new kind of tachometer to develop a specific add-on to Sec_Red, which will handle the merge of the data provided by the sensors attached to each unit. 2. In order to reach good system performances, it is unacceptable to consider that in safety, the sensors of each unit are out of synchronization of one full cycle. It is therefore necessary to provide a way to check the quality of the synchronization between both units with a far better precision that one whole cycle, and with a confidence level compliant with safety applications (SIL4).

The other main issue was that even if the redundancy protocol was seamless for the application part, at specification level, it was not as true as we hoped at implementation level. The reintegration part is costly for the CPU and our applications are bound to run in a limited cycle time. Fine optimization was therefore required in order to allow our applications to run flawlessly, these optimizations where also correlated to the way of handling the reintegration. For example, big arrays of time-out variables decremented at each cycle generate evolutions of the context that could prevent the reintegration to finish (see Sect. 4.7). It is better here to memorize the end time of the time-out, and to compare it at each cycle to the current time. Nevertheless, these complexities are insignificant, compared to the difficulty of handling the whole redundancy processing at applicative level!

Acknowledgement

It is necessary to acknowledge here the work of all Siemens Transportation Systems teams, who work on the design, implementation and safety of the integrated redundancy protocol. This in particular includes David Dumont, Didier Essamé and Benoît Fumery.

Figure 1 :

 1 Figure 1: Architecture without redundancy

Figure 3 :

 3 Figure 3: Logical architecture of the redundancy

Figure 3 :

 3 Figure 3: Masking of a restrictive input

  Figure 4: Inconsistent wired outputs

CPU Vital Processing Unit I/O boards I/O boards I/O boards I/O boards Specific I/O boards PhW , TW link.. COTS Compact PCI bus DIGISAFE bus I/O Executing ……. Source file x:= x+y ……. Executable code 325F674E20 20300DFF0 Compiling Computer Unit Loading The vital coding covers all these steps

	involved in the process of computing the train
	position and speed.
	Of course, apart from these vital I/O and software
	computations, DIGISAFE allows the handlings of
	non-vital streams, as well as the execution of non-
	vital task.

  Hennebert and G. Guilho: "SACEM: a Fault Tolerant System for Train Speed Control", proceedings of 23 rd int. conf. on Fault-Tolerant Computing (FTCS-23),Toulouse, France, 1993.

	[1]	A. Bondavalli and al.: "State restoration in a COTS-
		based N-modular architecture", proceedings of
		Object-Oriented Real-Time Distributed Computing,
		(ISORC 98), 1998
	[2]	CENELEC:	"Railway	Applications	-	The
		Specification and Demonstration of Reliability,
		Availability, Maintainability and Safety (RAMS)", EN
		50126, 1999.
	[3]	CENELEC:	"Railway	Applications	-
		Communication, signalling and processing systems
		-Safety related electronic for signalling", EN
		50129, 2003.
	[4]	P. Forin: "Vital Coded Microprocessor: Principles
		and Applications for Various Transit Systems",
		proceedings of IFAC-GCCT, Paris, France, 1989.
	[5]	C.

Primitive operations on coded data (from the French OPération ELémentaire) Passivation: Sec_Red process that lead to isolated mode Sec_Red:

The redundancy manager software (from SECurity REDundancy) SIL4:

Safety Integrity Level 4, the highest level of requirements for safety applications [2] Unit:

Each redundant computer VCP:

Vital Coded Processor VLC:

Vital Logic Clock Vital:

Any device or concept whose failures may lead to an unsafe behavior of the system Vital Application: The vital part of the software executed on the computer Wayside:

The Wayside controller (as opposed to the on-board controller) is the part of the system which tracks the train on the track (using data sent by the trains themselves) and allocates them "movement limits".


D Laroudie

An End-to-End Model Based Tool Chain for Architecture Exploration

Keywords: Tools Chain, Model Based Development, E/E Architecture

This paper will present how it is possible to federate the usage of the design tools around a framework based on an Eclipse Front-End to describe, simulate and test real time embedded systems enabling users to deeply explore their E/E designs.

Introduction

In the world of E/E (Electrical/Electronic) design, the methodologies of the software development were for a long time established around different and complementary activities which follow in general the V cycle: System Design / General Design / Detailed Design / Implementation / Unitary Test / Integration Tests / Delivery. Engineers with different technical skills (System Architects, Software Designers, Test engineers,...) whom support the various engineering activities throughout the development cycle and more largely throughout the system development process, use various methodologies supported by various tools.

Nowadays, in « Embedded World », engineers have to cope with the design of highly sophisticated systems whose the main features are:

• Expected high level functionalities which are extremely complex, • Future systems integrating ready-to-use components (i.e. : IP component ; e.g. Autosar SWC),

• Many software components communicating and distributed on many computation units (ECU..).

In this situation, tasks previously sequential have to be performed in parallel. It also required for engineers to collaborate on tasks such: Design, Simulation, Test and Integration with intent to increase the re-use along the V cycle.

Accordingly, the approach, which consists in federating the use of the tools of E/E model based design around a system level framework, is innovating.

In particular, this paper will show how it makes it possible to increase the re-use, the quality and the automation of the low value and time consuming tasks.

The E/E architecture

The current embedded systems contain a collection of consistent electronic components realizing functions. The E/E architecture is the synthesis of this assembling. Each high level function supported by this architecture is based on:

• A functional view, • A hardware view,
• A mapping of the functional view on the hardware view.

This collection of views is one of the possible representation of the targeted E/E architecture. These views can be described statically (e.g.: a sketch) and dynamically (e.g.: a behavioral model).

They bring each a part of the response. Ones compared to the others have to be consistent to insure a correct design and associated to the « modeling/simulation » principle, each of the views can be validated.

The functional view of the E/E architecture

The static functional view can be described using tools like Visio, Word, PowerPoint, Simulink or StateMate (empty subsystems) or others, in a graphical way. Engineers can also use tabular based tools like Excel or others to describe such a view.

Once this view has been described, some consistent rules can be applied at this level (e.g.: « No flow in the air ») to help designers to validate and verify this design level and improve the quality of this design step.

The dynamic functional view can be simulated by using tools like Simulink or StatMate. These latter are totally fitted to this task. As the functional view, the static hardware view can be described in a graphical way using tools like Visio, Word, PowerPoint and engineers can also use tabular based solutions. Some consistent rules can also be defined and applied (e.g.: « All ECUs connected to at least one network »).

The simulation of such a view needs a dedicated tool which integrates behavioral models of ECUs, Sensors, Actuators, Networks and Wires.

These models must describe accurately these components from the HW level (numerical/analogical behavior) to the SW one (low level software). These models should cover:

The mapping view of the E/E architecture

This view summarizes how functions are allocated on ECUs (on tasks) and how flows inter-ECUs are allocated on Networks (on signals, in frames). As before, the static description can be achieved in a graphical way or by using tabular based solutions.

Here, it is necessary to have a bridge with networks communication matrix and a tabular view seems to be well adapted to describe the set of mapping information:

• Allocation of functions on tasks,

• Allocation of flow on networks,

• Selection of tasks activation period,

• …

Consistent rules can also be applied also (e.g.: « all functions have to be integrated into software tasks »). At this stage, the static design can be considered as finished.

The simulation of the mapping view needs a dedicated tool. It has to integrate at the same time, models from the functional and the hardware view.

It has to be well-adapted to simulate both the functional level and the non-functional one (OS, networks, HW) and interaction between the two (i.e.:« the software on its platform »). Here, one of the use case is to proceed to one allocation choice to another very easily and without «breaking everything ».

At this stage, it's out of question to design E/E System level models by hand. To succeed in this task, only technologies like model generationtransformation, can achieve this goal.

ECU #4

Input This collaborative System engineering framework is built on 4 great principles: flexibility, opening, facility of deployment and facility of maintenance and leans on 3 pillars: This solution brings answers to the general problem "Does the System fit in the box?"

• A System level Authoring Tool, • A Simulation Tool, • A Test Authoring Tool.

A well defined process

This framework is based on a well defined process including the static and dynamic description of the 3 complementary views of an E/E architecture (functional, hardware and mapping).

The System Architect Tool leans on different descriptions including a Functional Description (functions and flows), a Hardware Description (ECUs, Networks, Sensors/actuators) and Mapping of the Functional Description on the Hardware one, not forgetting, the communication matrix and the interfaces of the behavioural description.

This System tool has been designed to easily enable not to re-enter project data of the design process, but importing them from tools like Simulink, StateMate, Scade, Rhapsody, etc. This is the cornerstone of this tool.

The System modelling phase primarily allows users to increase the quality by improving data consistency and re-use. The technical foundation of the tool is a UML metamodel containing the objects and their links (interrelation). This UML class model is designed to be closest possible from systems to represent. The model concepts group thus:

• The notion of functional view,

• The notion of hardware view,

• The notion of mapping.

The tool is developed in the Open source Eclipse (EMF) environment. Associated to the static description of the E/E system, the dynamic description gives the user the possibility to simulate the chosen E/E architecture by using models of different levels:

EE Data Editor

Architecture

• behavioral models of functions, • behavioral models of E/E System environment, • behavioral models of communication media, • behavioral models of ECUs.

(E/E System/software vision)

and by using engineering techniques of models transformation to generate the final model for simulation.

To create this simulation model, the inputs are the static architecture and the behavioral descriptions (functional/non functional levels). The activities perform during the simulation phase covered tests for normal/damaged and dysfunctional modes by faults injection means, in summary: Performances Analysis and Architecture Exploration.

The simulator

The simulator used by the framework is based on Geensys's solution: RT-Builder, which is a eventdriven simulator/debugger engine and allows users on one hand, to study by simulation the dynamic behaviour of their real time application software architecture (virtual prototype of the targeted application), on the other hand to reach early definition of optimal architecture choices (performances analysis).

The simulation allows multiple iterations on system performance evaluations; in a quick, simple and cost-effective manner, performance estimations of different types can be assessed, at different stages in the development cycle.

• Point to point response time,

• CPUs loads, • Load estimation for communications.

• ….

Users can either help define performance budgets requested by project teams in the early phase of system specification or help reevaluate impact of ECOs on the overall system performance during downstream development phases.

The comprehensive virtual prototype of the targeted application built by model generation, enable users to analyse various performance aspects of their system, eventually observe and "reason" on their application at different levels -functional level -untimed-as well as application execution level, taking into account functional and non functional architecture artefacts. That is to say:

• Monitor the execution of the functional parts, • Monitor the execution of the timed functional parts,

• Do performances analysis.

A fault injection mode further extends analysis capabilities at system level -RT-Builder fault analysis specifically looks at degraded modes and their effects on interactions between the application software and its execution platform (correlation between CPU states, networks and application), but also the nominal/degraded modes, do failures analysis and help in the diagnostic validation.

Architecture Exploration and Performances analysis

The RT-Builder event-driven simulator can be controlled interactively, randomly or by user scenarios. An integrated debugger gives the user possibilities like: step-by-step simulation, numerical traces generation, breakpoints, tokens display and complex observer creation capabilities (assertions).

A batch mode is also available. The debugger has also the possibility to monitor the flow of events and/or data between graphical components.

Simulation of the Scheduling

The simulation engine implemented in the tool is based on an event-driven simulation associated to simulated real time. In this context, GANT diagrams can be used to monitor the temporal behaviour of OS tasks, that is to say, the scheduling on the ECUs. It is possible to observe how the tasks are running, how the tasks are pre-empted, how the tasks are exchanging data, events… At this step, the simulator used in conjunction with the debbuger, can allow the user to detect interlocking problems because of the scheduling.

Figure 1: Simulation of the real time scheduling on several ECUs.

Simulation of the Communication

The simulation of bus communications helps to emphasize frames transfer time, queuing time during transmission and reception in FIFOs, but also give the timing execution and bus load. As the communication impacts the task scheduling (e.g.: by locking a task which waits for an event), these information can, of course, concern the user who tries to optimize its task distribution on ECUs of its architecture.

The Test Authoring Tool

The Test oriented Authoring Tool leans on one idea, the re-usabililty: test cases created at the design step, have to be reusable during integration and validation phases.

To enable this re-use, tests have to be written using a high-level language (a specification language and not a implementation one) ; a meta-model describing what a test case is, answers this requirement.

This tool has automatic model transformation means to make scenarios usable at the same time, for simulation tools or test benchs. The test cases edition is driven by the model (Model Based Testing).

This has as an interest to ease and make possible the test and the validation of the whole design model (thus containing models of ECUs -low and application levels-sensors, actuators, networks…) by System, Design, and Specification Engineers. It thus enables to perform definition works of test campaigns for the various levels of E/E architecture:

• Functional tests ,

• Communication tests,

• Services Layers tests,

• Nominal/Degraded tests,

• Diagnostic tests.

Positioning in the design flow

The described framework is positioned at the frontier of different skills of the Embedded Electronics.

System Engineers can simulate and analyze on its HW architecture model, the low level functions (communication, message switching, HW and SW modes, and middleware) and verify that the whole system behaves correctly. SW Design Engineers can test its design choices (grouping functions in a task, choice of the execution mode and the activation period of tasks…) and validate with Specification Engineers that the latter, do not have an influence on the functional requirements of the application.

Proof of concept

9.1 1 st Experimentation: One ECU: "Virtual results against real ones" To validate the level of accuracy of the simulation kernel of RT-Builder, a standard control/command law has been developped in Simulink and prototyped on a dSPACE HW.

Each function has been allocated to a task (event or timer-driven) and managed by a preemptive OS. The typical cycle time was the millisecond.

The functional results obtained in RT-Builder were accurate at 10 -12 , compared to the ones obtained on the dSPACE HW. 9.2 2 nd Experimentation: Several ECUs "Eases achievement of models of various configuration and distribution options very quickly."

This second example is based on a high level automotive application distributed on 6 ECUs, with 30 dedicated frames on 3 networks. Such application took around one men-year of work to be modelled in an Authoring tool. This modelization included:

• ECUs description (behaviour level) • Networks description (behaviour level) • Application level.

The final model was very complex to maintain and was representative of only one possibility of implementation (one possible mapping has been tested).

With the framework, such a work took around two month for one person to describe the whole system in the editor, to create the dedicated libraries and to generate a simulation model for RT-Builder.

It was very simple to generate models based on different mapping hypothesis and run the related simulation once the E/E model has been created and/or imported in part.

Conclusion

This paper illustrated each of the prime technology concepts of this framework of models generation, system description, functional description, hardware architecture description and mapping. It highlighted how can the different concepts be used to define a simple but comprehensive system metamodel, which -when combined with multifaceted models -make it possible to very quickly simulate the complete system, run what if analysis on various configuration and distribution options and give control back to development teams.

Glossary

  Figure 1: Functional view (The functional view is mainly composed of functions and functional flows.)

  Figure 3: Mapping view (The mapping consists of allocating functions and functional flows on architecture elements.)

Figure 4 :

 4 Figure 4: System tool import/export capabilities

Figure 2 :

 2 Figure 2 : Simulation of a Bus communication

Figure 3 :

 3 Figure 3 : Simulation of an application on its architecture.

  Denis is the pre-sales manager for "Model Based Design" products line in Geensys. He supports customers of Automotive, Aerospace, Defence and Space as an expert consultant and help them to deploy solutions around Verification and Validation concepts, offered by Geensys. denis.laroudie@geensys.com

	ECU: Electronic Control Unit
	CPU: Central Processing Unit
	FIFO: First In First Out
	EEPROM: Electrically Erasable Read Only Memory
	WCET: Worst Case Execution Time
	OS: Operating System
	EE: Embedded Electronics -Electrical/Electronic
	SW: Software
	HW: Hardware
	SCADE is a tool from Esterel Technologies,
	Simulink/Stateflow is a tool from The Mathworks,
	StateMate is a tool from I-Logix/Telelogic
	12. Biography
	Denis LAROUDIE
	(Author and Speaker)


Jim Krodel

Technology Changes In Aeronautical Systems

Keywords: Formal Methods, Object Oriented Technology, Model, Airborne Software, Software Technology, Software Approval

Guidance for producing airborne software today must be developed to the expectations of ED-12B/DO-178B "Software Considerations in Airborne Systems and Equipment Certification".[1] EASA and the FAA have formally recognized this 'objectivebased' aviation software guidance and it has proven to be extremely successful in the development of safe, in-service, operational aircraft containing software. Since its publication in 1992, ED-12B/DO-178B has gain respect as a standard that meets the goals of safety in the airborne community. However recent technology advances such as Object Oriented Technology, Model Based Design, Software Tools and Formal Methods have applied methods that require elaboration of how the ED-12B/DO-178B objectives will be met. This paper discusses the approach for introducing new technologies with legacy aviation standards.

Introduction

ED-12B/DO-178B has established the respect of the aviation community, but it has also gained respect in other domains such as rail, nuclear, and medical. Even today, after 15 years of use, the guidance in ED-12B/DO-178B remains a viable approach to support the certification of aviation systems. However the emergence of software related technologies over these past 15 years has 'stretched' how certification applicants apply these technologies given the original foundations laid in ED-12B/DO-178B.

International certification authorities have drafted several papers to assist with the application of these technology issues such as Object Oriented Technology, but this approach does not permit the general aviation software developer to participate in the paper or position development. Clearly, the certification authority wants to recognize how to properly apply these technologies, but because of the noteworthy safety record of ED-12B/DO-178B, they are cautious of new technology adoption. On the other hand some of these technologies can provide additional safety benefit in handling the large computer intensive systems being built into today's aircraft. This dilemma is being worked by the joint international group WG-71 / SC-205. This group is working to retain the successful core tenets of ED-12B/DO-178B, while permitting a mechanism to introduce technology specific or method specific supplemental guidance.

ED-12B/DO-178B

2.1 Early Development of ED-12B/DO-178B ED-12B/DO-178B provides a means of developing software for airborne systems and although other means are possible, the excellent aviation software safety record since ED-12B/DO-178B's inception demonstrates its effectiveness.

ED-12B/DO-178B was originally based on the FARs/JARs of both the US and European aviation regulatory authority and was developed jointly by RTCA, Inc. based in Washington, DC and EUROCAE based in Malakoff, France. Both RTCA and EUROCAE form special committees and working groups to develop guidance in producing aviation systems. In this case they jointly formed guidance to develop software in airborne systems and equipment. The aviation certification authorities have recognized the software guidance developed by these joint groups since the mid 1990's, but when we considers the several years it took to generate this guidance we can see that the guidance is based on software technology knowledge as it was in the mid 1980's.

To build an airborne certified system, several other standards are used including ARP-4761 (Safety Methods), ARP-4754 (System Development Process), DO-254 (Hardware Development Process), and of course ED-12B/DO-178B (Software Development Process). ED-12B/DO-178B is used once the system is defined and safety requirements are allocated to the software. Certifying a system is a multi-step process as defined by the previously mentioned documents. Figure 1 shows how these documents and steps interrelate. Step 1: With the aircraft requirements, determine the functions to be performed.

Step 2: Perform an Aircraft Functional Hazard Assessment (FHA) per ARP4761 and identify failure conditions and effects.

Step 3: These failure conditions and effects permit effective allocation of the system requirements

Step 4&5: With system functions established a system Functional Hazard Analysis can be performed to develop the systems architecture (redundancy, safe modes of operation, etc.)

Step 6: A Preliminary System Safety Assessment (PSSA) is then performed on the system architecture based on the system FHA to determine if the associated requirements and architecture meet safety objectives.

Step 7: Finally, the system (including the supporting software) can be implemented.

There are other considerations, throughout this process such as a Common Cause Analysis (CCA) on the system, its architecture and associated implementation to avoid any common mode errors. With these steps completed, a proper System Safety (SSA) Assessment and a demonstration of compliance to these guiding documents, the system can be certified.

It is clear with this view of the system development that software is simply part of the overall system and ED-12B/DO-178B simply guides developers what to do to permit usage of that software on the system. Indeed ED-12B/DO-178B tells the user "what" should be done to develop systems with software, but not "how". The how is defined by the developer via their plans.

A set of plans such as Plan for Software Aspects of Certification (PSAC), Software Quality Assurance Plan (SQAP), Software Configuration Management Plan (SCMP), Software Verification Plan (SVP), and Software Development Plan (SDP) provides insight into the approaches to defining how the user will meet the objectives of ED-12B/DO-178B as applied to the requirements, design, code and verification processes of the developing software.

Maturity of ED-12B/DO-178B

After several years of ED-12B/DO-178B use, it was clear that new software techniques were starting to stress the interpretation of its words and as such other standards documents were needed and created to further clarify and support ED-12B/DO-178B. For example in 2001, ED-94B/DO-248B was written and contains a set of discussion papers and frequently asked questions that assists in understanding the objectives to be met for those developing aviation software. [START_REF]B "Final Report for the Clarification of DO-178B Software Considerations in Airborne Systems and Equipment Certification[END_REF] In fact with the advent of new techniques since the inception of ED-12B/DO-178B, the task of approving software in certified system became very complex and the FAA developed their own document called the "FAA Job Aid" to assist them and others in understanding proper approaches to approving software in airborne systems.

New software techniques such as Object Oriented Technology, Model Based Design, Software Tools and Formal Methods have applied methods that require elaboration of how the ED-12B/DO-178B objectives will be met.

Object Oriented Technology

Compliance with the objectives of ED-12B/DO-178B is the primary means of obtaining approval of software used in civil aviation products. In 1992, when ED-12B/DO-178B was born, procedure programming was the predominant technique for organizing and coding computer programs. Consequently, ED-12B/DO-178B provides guidelines for software developed using a functional technique. OOT is a software development technique that is expressed in terms of objects and connections between those objects. Since object-oriented technology differs from the traditional functional approach to software development, satisfying some of the ED-12B/DO-178B objectives when using OOT may be unclear and/or complicated.

Although OOT is intended to promote productivity, increase reusability of software, and improve quality, uncertainty about how to comply with certification requirements has been a key obstacle to using OOT in airborne systems.

Due to this difficulty in applying ED-12B/DO-178B to the OOT domain, the FAA co-sponsored the Object-Oriented Technology in Aviation (OOTiA) project with the National Aeronautics and Space Administration (NASA) to address OOT challenges in aviation. The FAA, NASA, and other organizations developed workshops and this workshop committee produced a handbook specifically addressing object oriented technology. [START_REF]Draft Tools Supplement[END_REF] Issues with the technology that arose that were difficult to apply with ED-12B/DO-178B were the use of dynamic memory allocation / deallocation that is used in OOT primarily because it challenges the deterministic characteristics of airborne systems. Likewise traceability of the design and code, key to ED-12B/DO-178B's verification completeness objective, is difficult to demonstrate with OOT approaches.

Model Based Design

Model based design holds the hope of alleviating the burden of the costly development of today's aviation systems. Flight test or even tests conducted in special test equipment rigs are extremely costly and in many cases permit only 'black box' testing of the product under development, which typically does not fully test the robustness of the product.

If we can build a perfect model of the environment that the product will operate in, then we can more robustly test the product, its modes of operation and how it will detect and accommodate faults induced by the environment.

The "if" of the previous paragraph is in bold, and justifiably so, as it is a very big 'if'. If we can build a perfect model, then we could take credit for testing with that model and reduce the costly flight or rig test that are currently performed. And yet although we know that it is not likely, if we could build a perfect model, how would you determine the pedigree of the model? This is one aspect of product development that ED-12B/DO-178B did not address and as such clarification in this area is needed.

Formal Methods

Formal methods have always held the intrigue that we would be able to build a system so precise and exact that we know it would be correct. The foundations for such a claim are based on the specification of the system in a mathematical sense. Rushby defines formal methods as mathematically based techniques for the specification, development and verification of software and hardware systems that are based on formal logic, discrete mathematics, and computer-readable languages. [START_REF] Rushby | Formal Methods and the Certification of Critical Systems[END_REF] Formal methods allow properties of a system to be predicted from a mathematical model of the system.

We can think of formal methods in two parts, formal specification and formal verification. In formal specification we see the use of mathematics-based languages that provide precise, unambiguous descriptions of requirements and other development objects. In formal verification, we see deduction or proof that relies on a discipline that requires the explicit enumeration of all assumptions and reasoning steps. Formal verification also encompasses model checking, which is the process of automatically checking whether a given finite model of an object satisfies a given property.

Formal methods generally constitute a specification language and an accompanying tool or set of tools that are consistent, complete, and not ambiguous. The benefits promised by such languages and tools are the anticipated improvement of requirement quality, the reduction of specification errors and the permitting of verification techniques, which fully explore the behavior of a design.

Yet there are acknowledged limitations, such as not being able to fully establish the verification evidence for compatibility with the target hardware. Formal methods further cannot ensure that a formally specified requirement correctly meets its non-formal parent requirement(s) and it cannot verify anything that is not explicitly stated as a property. Along with this is a fear that formalizing requirements or designs may increase the effort required to specify them, particularly for complex systems. And finally although we would like to think we could precisely specify the system, somewhere in the life cycle, there will be at least some bit of informality. The assumptions made in translating requirements or designs from the informal to the formal may not be clear, or may misrepresent to some degree a sufficient model of the real system. "Traditional software development methods rely on human inspection and testing for validation and verification. Formal methods also uses testing, but they employ notations and languages that are amenable to rigorous analysis, and they exploit mechanical tools for reasoning about the properties of requirements, specifications, designs, and code. Practitioners have been skeptical about the practicality of formal methods. Increasingly, however, there is evidence that formal methods can yield systems of very high dependability in a costeffective manner, …." [START_REF]Software for Dependable Systems: Sufficient Evidence? Daniel Jackson[END_REF] ED-12B/DO-178B holds very little guidance in the area of formal methods. Formal methods are merely recognized as alternative methods that admittedly have limited applicability to the airborne community at the time when ED-12B/DO-178B was written. When using formal methods different forms of evidence may be used to substantiate its suitability in order to meet the intent of certain objectives from ED-12B/DO-178B, rather than the actual objectives. If a process is used to satisfy ED-12B/DO-178B that provides different evidence and does not directly meet the objectives, there is a need to demonstrate clearly that the alternate process is equivalent. The regulatory authorities have been rather uncomfortable with such a 'meet the intent' approach, and as such have been reticent to embrace formal methods as a recognized practice for airborne system and equipment development.

Software Development and Verification Tools

We have all recognized that developing systems without the assistance of computerized tools would be impossible. And the range of sophistication of these tools is broad. ED-12B/DO-178B encourages the use of such tools, but is cautious when the tools are used to reduce or eliminate the objectives set forth in ED-12B/DO-178B. ED-12B/DO-178B divides tools that take some form of 'credit' for an objective into two categories, that is, those tools (development) that can directly affect the target software such as an auto-code generator tool, and those tools (verification) that can affect the verification of the target system. ED-12B/DO_178B states that development type tools must be created to the same rigor as that software criticality level of the target system. It is clear that ED-12B/DO-178B wants to assure that any tool taking credit for objectives has been qualified, such that its operation is correct and can be relied upon. A similar approach is taken for verification tools, but the rigor is somewhat less.

The cost for developing tools to this rigor can be rather high and it has made tool developers reluctant to provide their tools as 'qualified' to this level because of this cost burden. As such, airborne system developers are left with further burdensome and costly development practices because they cannot take credit for using the tool. The industry has recognized that further guidance in the use of development and verification tools to reduce system development costs is in order to permit a more cost effective development yet still one that would yield a safe system. [START_REF]Draft Tools Supplement[END_REF]

Integrating New Technologies in Legacy Guidance

Since ED-12B/DO-178B's inception in 1992, it has become the foundation for all aviation-based systems that contain software components. Its track record is exceptional as noted before and as such the industry has been reluctant to make significant changes to it. An example of this is the work conducted by joint SC-190/WG-52, which clarified some of the issues with ED-12B/DO-178B, but was not permitted to change the core ED-12B/DO-178B document.

Even today, joint committee SC-205/WG-71 is trying to address the new technology needs of tools, formal methods, model-base design and object oriented technology yet in a manner that limits somewhat the scope of change to ED-12B/DO-178B.

The question arises is how can we keep the core tenants of successful guidance such as ED-12B/DO-178B yet still meet emerging technology needs? Further questions arise with regards to new technologies that may not even be recognized as viable approaches for the aviation domain. The solution that SC-205/WG-71 has devised is to minimally modify the core of ED-12B/DO-178B and provide a technology supplement that has a specific interface specification to the core document and objectives.

The approach taken is to amend the core document in such a way as to be receptive to the introduction of new technology. This is being accomplished by the production of a technology interface specification, which will define what must be addressed in a technology supplement to sufficiently address the new guidance a technology supplement may provide. Figure 2 pictorially shows the approach. Any issues that were raised with ED-12B/DO-178B were recorded in an issue list and the four aforementioned technologies were included on this issue list. The four technology supplements are being developed by sub-groups internal to SC-205/WG-71 that holds specialists in those areas of technology with a firm knowledge of the aviation domain and approval authority process. Each of the supplements being developed has participation from the certification authorities such that the guidance being developed will be one that the certification authorities can embrace.

Conclusion

A guidance document for developing software in airborne systems and equipment, namely ED-12B/DO-178B has become deeply ingrained in those organizations that develop such products. This guidance has become a common ground for the understanding of developing, verifying, integrating and approving this software such that there is a high level of confidence in the deployed system's ability to perform its tasks safely.

As new approaches and technologies arise in the software development domain of such embedded systems an effective means for integrating these technologies to the core tenets of ED-12B/DO-178B has occurred. Specific areas being worked include Software Tools Technology, Model-Based Development Technology, Object Oriented Technology and Formal Methods. The approach taken is to develop technology supplements that abide to an overall core document interface specification such that the core document can effectively be applied to the new technology. This approach of developing supplemental guidance to a core guidance document such as ED-12B/DO-178B provides a basis for keeping pace with new emergent technologies without the need to rewrite the core document as these new technologies emerge.

Figure 1 :

 1 Figure 1: ED-12B/DO-178B System Development

Figure 2 :

 2 Figure 2: Technology Integration in Core Guidance

Acknowledgement

The author acknowledges the contribution of Scott Beecher of Pratt & Whitney in the preparation of this work and the efforts of joint SC-205/WG-71 that have been developed to date.

Glossary