Christian Ferdinand
email: ferdinand@absint.com

Reinhold Heckmann
email: heckmann@absint.com

Jean Souyris
email: jean.souyris@airbus.com

Keywords: Safety, Estimation of Stack Usage, Timing Validation, Schedulability Analysis, WCET (worst-case execution time) Prediction

HAL is

Introduction

Static analyzers based on abstract interpretation are tools aiming at the automatic detection of run-time properties by analyzing the source, assembly or binary code of a program. From Airbus' point of view, the first interesting properties covered by static analyzers available on the market, or as prototypes coming from research, are absence of run-time errors, maximum stack usage and Worst-Case Execution Time (WCET). This paper will focus on the two latter.

Stack analyzers

The failure of a safety-critical application on an embedded processor may lead to severe damage. A possible cause of catastrophic failure is stack overflow that usually leads to run-time errors that are difficult to diagnose. The problem is that the memory area for the stack must be reserved by the programmer. Underestimation of the maximum stack usage leads to stack overflow, while overestimation means wasting memory resources. Measuring the maximum stack usage with a debugger is no solution since one only obtains a result for a single program run with fixed input. Even repeated measurements with various inputs cannot guarantee that the maximum stack usage is ever observed. Some, but not all compilers provide information about stack usage, but this requires the availability of the source code, and the information becomes invalid when the generated code is optimized by hand or by some automatic tool. The main job of stack analyzers is to compute an upper bound of the maximum stack consumption of a program by statically analyzing its binary. The way this upper bound is computed makes it both safe and precise, thanks to the theory of abstract interpretation. By "safe", it is understood that the analysis result really is an upper bound of the maximum stack depth for all possible executions of the program; by "precise", we mean: the maximum stack consumption computed by the tool is lower than the one computed by classical and usually very conservative methods.

Stacks are used to store return addresses, function parameters, local variables, and intermediate results. Since it is difficult to predict on source-code level the amount of data stored on the stack by the compiler, StackAnalyzer operates on the generated assembler files or executables that contain the necessary information. Therefore the tool must be adapted to the microprocessor the analyzed program is compiled/assembled for. For covering most of its needs, Airbus is currently validating AbsInt's stack analyzers for the X86, Motorola PowerPC, and Texas TMS320C3x families. In addition, AbsInt offers stack analyzers for C166/ST10, Arm7 TDMI, and HC12 processors.

The picture shows the call graph of a small example application for PowerPC 755. Upon request, StackAnalyzer shows the control-flow graphs of the routines at basic-block level or instruction level, annotated with local stack analysis results. The results at instructions are determined by assuming a stack level of 0 at routine entry, and then taking the effects of each instruction into account. The result at a basic block is the join of the results for its instructions. Similarly, the local result at a routine is the join of the results for its basic blocks and the value 0 assumed at routine entry. Here, the join of a collection of intervals and numbers is the smallest interval containing all these intervals and numbers. StackAnalyzer is a tool useful for developers of applications for embedded systems. Used properly, it reduced the production effort and avoids run-time errors due to stack overflow. Critical program parts are easily identified by the color of the result boxes. This gives useful hints for optimizing the stack usage of the application.

StackAnalyzer can also be used to guarantee the absence of stack overflow for quality control and certification of software. Thanks to AbsInt's stack analysers, at least 10 avionics applications safely compute the amount of memory they reserve for their stacks. A significant example is a six year old x86 application in which the maximum stack usages -one per thread -were computed by monitoring the stacks at test time and then by doubling the maximum value observed for each stack. In spite of doubling the measured values, it is not possible to prove that an upper bound of the stack consumption has been determined in this way. Now, with AbsInt's stack analyzer, it can be stated that the upper bounds stack for the stack consumption computed by the tool -one per thread stack -are safe and, as they are all close to (from above: they are safe!) the measured ones before doubling, almost half of the memory previously dedicated to the stacks is now available for another usage.

Worst-Case Execution Time analyzers (aiT family) Timing Validation

Computers controlling potentially hazardous machinery are expected to always execute in time. Consequently, for the modelling and planning of embedded systems it is essential that their timing behavior be validated. For several reasons timing validation is challenging:

• The increasing performance of the microcontrollers allows to put more and more functionality on a single embedded control unit. This means that there is a trend to more and more tasks in a real-time system with complicated dependencies and scheduling requirements and multiple levels of interrupts. The complex interaction of different functions on one microcontroller is often managed by a real-time operating system (RTOS). It is typically not possible nor practical to test the system with all possible inputs and all distributions over time of "external events" that might lead to an interrupt. • Software is typically written in some high level language like C, C++, Java, or Ada. Optimizing compilers make it difficult for the developers to precisely estimate the execution time of their code. • The software is typically developed in teams. Furthermore, the share of 3rd party software like RTOS and communication libraries is increasing. The timing behavior of the interacting software components is rarely known. • Modern processor components like caches and pipelines complicate the task of determining the WCET considerably, since the execution time of a single instruction may depend on the execution history. Realtime systems are typically composed of a set of tasks with specified deadlines (mostly dictated by the surrounding physical environment). A schedulability analysis has to be performed in order to guarantee that all timing constraints will be met (timing validation) [START_REF] Stankovic | Real-Time and Embedded Systems[END_REF]. This requires that the system be designed in a way that schedulability analysis is possible. There exist many results and analysis methods for real-time scheduling, see e.g. [START_REF] Liu | Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment[END_REF][START_REF] Sha | Priority Inheritance Protocols: An Approach to Real-Time Synchronization[END_REF][START_REF] Xu | Scheduling Processes with Release Times, Deadlines, Precedence, and Exclusion Relations[END_REF][START_REF] Ramamritham | Efficient Scheduling Algorithms for Real-Time Multiprocessor Systems[END_REF][START_REF] Stoyenko | Analyzing Hard-Real-Time Programs For Guaranteed Schedulability[END_REF][START_REF] Halang | Real-Time Systems[END_REF][START_REF] Audsley | Applying New Scheduling Theory to Static Priority Pre-Emptive Scheduling[END_REF][START_REF] Stankovic | Implications of Classical Scheduling Results for Real-Time Systems[END_REF][START_REF] Gerber | Guaranteeing Real-Time Requirements with Resource-Based Calibration of Periodic Processes[END_REF]. Another approach to design (complex) safety critical real-time systems is the time-triggered approach in contrast to the event-triggered approach. In a time-triggered system all actions are performed at times that have been fixed during system design, i.e., a static schedule for all tasks is determined before the system runs. The time-triggered approach has successfully been used e.g. to implement fly-by-wire systems for aircrafts. In combination with timetriggered communication busses (TTA, FlexRay, TTCAN, SAFEbus, ...) and time-triggered operating systems (e.g. OSEKtime) it is possible to design safety-critical distributed real-time systems. The time-triggered approach is recently becoming more used in the automotive area, e.g. for X-by-wire applications. Schedulability analysis for event-triggered systems and determining a static schedule for time-triggered systems require the worst-case execution time of each task in the system to be known prior to its execution. Since this is not computable in general, estimates of the WCET have to be calculated. These estimates have to be safe, i.e., they must never underestimate the real execution time. Furthermore, they should be tight, i.e., the overestimate should be as small as possible.

Worst Case Execution Time Prediction

There is typically a large gap between the cycle times of modern microprocessors and the access times of main memory. Caches and branch target buffers are used to overcome this gap in virtually all performance-oriented processors (including high-performance microcontrollers and DSPs). Pipelines enable acceleration by overlapping the executions of different instructions. The consequence is that the execution behavior of the instructions cannot be analysed separately since this depends on the execution history. Cache memories usually work very well, but under some circumstances minimal changes in the program code or program input may lead to dramatic changes in cache behavior. For (hard) real-time systems, this is undesirable and possibly even hazardous. The widely used classical methods of predicting execution times are not generally applicable. Software monitoring or the dual loop benchmark change the code, what in turn has impact on the cache behavior. Hardware simulation, emulation, or direct measurement with logic analyzers can only determine the execution time for one input. This cannot be used to infer the execution times for all possible inputs in general. Making the safe-yet for the most part-unrealistic assumption that all memory references lead to cache misses results in the execution time being overestimated by several hundred percent.

WCET Computation

In our approach [START_REF] Ferdinand | Reliable and precise WCET determination for a real-life processor[END_REF] the determination of the WCET of a program task is composed of several phases: Value Analysis: computation of address ranges for instructions accessing memory. Cache Analysis: classification of memory references as cache misses or hits [START_REF] Ferdinand | Cache Behavior Prediction for Real-Time Systems[END_REF]. Pipeline Analysis: prediction of the behavior of the program on the processor pipeline [START_REF] Langenbach | Pipeline Modeling for Timing Analysis[END_REF]. Path Analysis: the determination of a worst-case execution path of the program [START_REF] Theiling | Combining Abstract Interpretation and ILP for Microarchitecture Modelling and Program Path Analysis[END_REF]. The results of the value analysis are used by the cache analysis to predict the behavior of the (data) cache. The results of cache analysis are used within pipeline analysis allowing the prediction of pipeline stalls due to cache misses. The combined results of the cache and pipeline analyses are used to compute the execution times of program paths. The separation of WCET determination into several phases has the additional effect that different methods tailored to the subtasks can be used. Value analysis, cache analysis, and pipeline analysis are done by abstract interpretation [START_REF] Cousot | Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints[END_REF], a semantics-based method for static program analysis. Integer linear programming is used for path analysis.

Reconstruction of the Control Flow from Binary Programs

The starting point of our analysis framework is a binary program and additional user-provided information about numbers of loop iterations, upper bounds for recursion, etc. In the first step a parser reads the compiler output and reconstructs the control flow [START_REF] Theiling | Extracting Safe and Precise Control Flow from Binaries[END_REF][START_REF] Theiling | Generating Decision Trees for Decoding Binaries[END_REF]. This requires some knowledge about the underlying hardware, e.g., which instructions represent branches or calls. The reconstructed control-flow is annotated with the information needed by subsequent analyses and then translated into CRL (Control-Flow Representation Language). This annotated control flow graph serves as the input for micro-architecture analysis.

Pipeline Analysis

Pipeline analysis models the pipeline behavior to determine execution times for a sequential flow (basic block) of instructions, as done in [START_REF] Langenbach | Pipeline Modeling for Timing Analysis[END_REF][START_REF] Schneider | Pipeline Behavior Prediction for Superscalar Processors by Abstract Interpretation[END_REF]. It takes into account the current pipeline state(s), in particular resource occupancies, contents of prefetch queues, grouping of instructions, and classification of memory references as cache hits or misses. The result is an execution time for each instruction in each distinguished execution context.

Path Analysis

Using the results of the micro-architecture analyses, path analysis determines a safe estimate of the WCET. The program's control-flow is modelled by an integer linear program [START_REF] Theiling | Combining Abstract Interpretation and ILP for Microarchitecture Modelling and Program Path Analysis[END_REF][START_REF] Theiling | ILP-based Interprocedural Path Analysis[END_REF] so that the solution to the objective function is the predicted worst-case execution time for the input program. A special mapping of variable names to basic blocks in the integer linear program enables execution and traversal counts for every basic block and edge to be computed.

Analysis of Loops and Recursive Procedures

Loops and recursive procedures are of special interest since programs spend most of their runtime there. Treating them naively when analysing programs for their cache and pipeline behavior will result in a high loss of precision. The following observation can be made frequently: the first execution of the loop body usually loads the cache and subsequent executions find most of their referenced memory blocks in the cache. Hence, the first iteration of the loop often encounters cache contents quite different from that of later iterations. This has to be taken into account when analysing the behavior of a loop on the cache. A naive analysis would combine the abstract cache states from the entry to the loop and from the return from the loop body, thereby losing most of the contents. Therefore, it is useful to distinguish the first iteration of loops from the others. A method has been designed and implemented in the program analyzer generator PAG [START_REF] Alt | Generation of Efficient Interprocedural Analyzers with PAG[END_REF], which virtually unrolls loops, the so-called VIVU approach. Memory references are now considered in different execution contexts, essentially nestings of first and non-first iterations of loops.

User annotations

Apart from the executable, aiT needs user input to find a result at all, or to improve the precision of the result. The most important user annotations specify the targets of computed calls and branches and the maximum iteration counts of loops (there are many other possible annotations). Originally, program points had to be identified by their address in these annotations. This is cumbersome and error-prone since addresses may change after recompilation. Now a more high-level specification language was introduced for referring to program points symbolically (e.g. the second loop in routine R) or via source code annotations.

aiT -WCET Analyzers

The techniques described above have been incorporated into AbsInt's aiT WCET analyzer tools. They get as input:

• an executable (in ELF format). The code is generated with the Diab Data C compiler from a restricted subset of ANSI-C (no dynamic data structures, no setjmp/longjmp), • user annotations, giving the call targets for indirect function calls and upper bounds on the iteration counts of all loops, • a description of the (external) memories and buses (i.e. a list of memory areas with minimal and maximal access times), and • a task (identified by a start address). A task denotes a sequentially executed piece of code (no threads, no parallelism, and no waiting for external events). This should not be confused with a task in an operating system that might include code for synchronization or communication. The WCET analyzers compute an upper bound of the runtime of the task (assuming no interference from the outside). Effects of interrupts, IO and timer (co-)processors are not reflected in the predicted runtime and have to be considered separately (e.g. by a quantitative analysis).

In addition to the raw information about the WCET, several aspects can be visualised by the aiSee tool [8] to view detailed information delivered by the analysis.

The pictures above show the graphical representation of the call graph for two small examples. The calls (edges) that contribute to the worst-case runtime are marked by the color red. The computed WCET is given in CPU cycles and in microseconds provided that the cycle time of the processor has been specified (as in the left picture). Of the two pictures below, the left one shows the basic block graph of a loop. max # describes the maximal number of traversals of an edge in the worst case. max t describes the maximal execution time of the basic block from which the edge originates (taking into account that the basic block is left via the edge). The worst-case path, the iteration numbers and timings are determined automatically by aiT. The right picture shows the contribution of the various execution contexts of the loop. In this example, the user has asked aiT to distinguish between the first iteration (Context 0), the second iteration (Context 1), and all other iterations (Context 2). The large picture above shows the possible pipeline states for a basic block in this example. Such pictures are shown by aiT upon special demand. The grey boxes correspond to the instructions of the basic block, and the yellow rectangles are individual pipeline states. Their cyclewise evolution is indicated by the strokes connecting them. Each layer in the trees corresponds to one CPU cycle. Branches in the trees are caused by conditions that could not be statically evaluated, e.g. a memory access that could not be classified as a guaranteed cache hit or guaranteed cache miss. The picture below shows some part of the picture above in greater magnification. You can see three individual pipeline states, each displaying a diagram of the architecture of the CPU (in this case a PowerPC 555) showing the occupancy of the various pipeline states with the instructions currently being executed.

Evaluation of aiT by Airbus

The main job of aiT is to compute an upper bound for the Worst-Case Execution Time of a program by analysing its binary. Like for stack analyzers, the way this upper bound is computed makes it both safe and precise. Again, aiT has to be instantiated for each microprocessor for allowing it to analyze binaries produced for a particular CPU, but also for taking into account the inner behavior of the CPU when it executes the instructions of the analyzed program. For modern architecture, modelling the cache and complex pipelines (superscalar in the PowerPC 755) and bus interfaces is the only way for computing a safe and precise WCET. For covering most of its needs, Airbus is currently validating aiT tools for the following targets: Motorola ColdFire 5307, Motorola PowerPC 755, and Texas TMS320C33. (aiT is also available for Arm7, HCS12, and PowerPC 555.) Basically the principles that allow aiT to compute a safe and precise upper bound of the Worst-Case Execution Time are the following:

1. Abstract Interpretation makes it possible to compute a safe upper bound of the WCET for all possible executions (i.e., for all possible inputs of the program); 2. The Abstract Domains on which the analysis is designed allows aiT to compute a WCET close to the real one (but still greater than...); 3. The inner working of the microprocessor is conservatively (for safety) and precisely modeled, again by Abstract Interpretation; 4. The restrictions the analysed program must conform to are clearly identified at tool's design time and also clearly stated in the user's manual. Airbus' first experience in AbsInt's WCET technology comes from the experimental usage of aiT ColdFire 5307 on a 340 flight control program for which the traditional WCET computation method was already applied. So, it was possible to compare both techniques and to conclude that by using aiT, once validated, one could allow to safely free about 10% of CPU power, due to the tighter WCET computed by aiT. The following table compares the estimated WCETs produced with Airbus's traditional method and aiT's results. The code analyzed didn't have to be instrumented in order to apply the tool. No changes in the development process of the programs to be analyzed were necessary. The results of the evaluation are very encouraging. We believe that the WCET tool not only can be used in verifying that WCET constraints are met but also in earlier stages of the development process as well. At a stage when the software is already available, but working hardware is not, the tool can be used for a performance evaluation. Based on the contributions of the program parts to the WCET one can make design decisions, e.g., with respect to static scheduling or code/data placement. The effects on the cache and pipeline can be viewed using the visualization options of the tool and causes for unexpected local timing behavior identified. Currently, AbsInt is adapting its aiT for PPC 755 to the timings of a proprietary chipset. Consequently, the results already obtained are based on an inappropriate model of these timings. Nevertheless, the first experiments made on benchmark code made Airbus choose aiT as the basis of the WCET demonstration for some critical A380 avionics computers.

Common considerations about both families of tools

None of the tools mentioned above would be as efficient as they are, or simply would not exist at all, if they were not based on the theory of Abstract Interpretation. Indeed, this theory makes them to be sound (i.e., producing safe results) at least in their design. The soundness of these tools is also based on the hardware and sometimes software models they rely on. If these models are correct, the soundness of Abstract Interpretation fully applies. A special issue is therefore for the user to get sure that the analyzed programs conform to the set of restrictions (see user's manual), and to validate the hardware model; it must be noticed that AbsInt supports the user for this validation at both tool and methodological levels.

  The red box at the top indicates the stack usage of the entire program. The yellow and orange boxes stand for routines, and the arrows in-between indicate routine calls. The stack analysis results for the routines appear in the boxes to the right of the routine names. Each result box carries two results: a global result, coming first, and a local result, following in angular brackets, -16] and local result [-8, 0]. Each result is an interval of possible stack pointer values. Intervals of the form [n, n] are abbreviated to n. The result node for a routine is displayed in red if the lower end of its global result interval equals the lower end of the interval for the entire program. All other result nodes at routines are displayed in pink. Since the stack grows by decreasing the stack pointer, all the results in the picture are negative. The local result at a routine R indicates the stack usage in R considered on its own: It is an interval showing the possible range of stack pointer values within the routine, assuming value 0 at routine entry. The global result for routine R indicates the stack usage of R in the context of the whole application. It is an interval providing bounds for the values of the stack pointer while the processor is executing instructions of R, for all call paths from the entry point to R. Thus, the global result at routine R does not include the stack usage of the routines called by R. For instance, routine prime has a global result of [-24, -16] because the two calls of prime in main have stack level -16, and prime itself has local stack usage [-8, 0]. Routine divides has a global result of [-32, -24] because its local stack usage is 0 and it is called in prime at the accumulated stack level (-16)+(-8) = -24 and in even at the accumulated stack level (-16)+(-8)+(-8) = -32.

Biographical data for the

  authors Christian FERDINAND (AbsInt): Born 1965, Ferdinand studied 1985-1990 computer science and electrical engineering at Saarland University. 1991-1998 he was academic research staff member at the chair for compiler construction and programming languages at Saarland University and participated in the ESPRIT projects PROSPECTRA (PROgramming by SPECification and TRAnsformation) and COMPARE (COMPiler generation for PARallEl machines) and in the Sonderforschungsbereich 124 (VLSI und Parallelität). In 1997, he received his Ph.D on "Cache Behavior Prediction for Real-Time Systems". C. Ferdinand received a student scholarship and a Ph.D.-student scholarship of the Siemens AG and received the Dr. Eduard Martin Preis in 1999 (award for best

-22 -23 January 2004

Ph.D. Thesis in computer science at Saarland University). He is a co-founder of AbsInt Angewandte Informatik GmbH and since February 1998 managing director of AbsInt. His work is focused on code generation for digital signal processors and on timing analysis for real-time systems. Reinhold HECKMANN (AbsInt) studied Computer Science at the University of the Saarland in Saarbrücken, where he received the Dr. rer. nat. degree in 1991. After being Lecturing Assistant at the University of the Saarland and Research Fellow at Imperial College, London, Reinhold Heckmann became Senior Researcher at AbsInt Angewandte Informatik GmbH. His major research areas include programming languages and compiler construction, document processing, semantics of programming languages and domain theory, exact real arithmetic, and static analysis of real-time systems, in particular cache and pipeline analysis. Jean SOUYRIS (Airbus) is a member of the Software Verification Group of Airbus France and in charge of the research activities for the application of formal program static analysis. Research efforts conducted for more than five years yield first partial but industrially applicable results. Integration of the early tools is now effective in the verification framework used for on-going aircraft developments (safety-critical software). On-going research projects are based on abstract interpretation where efforts target the extension of the early results. As first education, he holds an engineer degree from the INSA engineer school.


Julien Delange

Peter Feiler

Supporting the ARP4761 Safety Assessment Process with AADL

Cyber-physical systems, used in domains such as avionics or medical devices, perform critical functions where a fault might have catastrophic consequences (mission failure, severe injuries, etc.). Their development is guided by rigorous practice standards to avoid any error. However, as software importance continues to grow, integration and validation activities are becoming overwhelming. Late discovery of errors introduced in requirements and architecture design have resulted in costly rework, making up as much as 70% of the total software system cost. To overcome these issues, architecture-centric model-based approaches abstract system concerns into models that are analyzed to detect errors, issues or defects that are usually detected lately in the development process. This predictive analysis approach is automated by tools, avoiding any tedious manual efforts. In this paper, we present our model-based approach for capture and analyze system safety and reliability. We have added an error behavior annotation to SAE AADL, a standard for modeling embedded software system architectures. We also implemented analysis methods to automate safety analysis and production of safety assessment reports, as requested by safety recommended practices standards (such as ARP4761).

Introduction Context

Cyber-physical systems perform critical functions under constrained and potentially hostile circumstances. Because errors can have catastrophic consequences [START_REF] Leveson | An investigation of thetherac-25 accidents[END_REF], they must be designed carefully and validated/certified according to a rigorous process to prove assurance of correct operation and increase confidence of system design. Verification criteria depend on applications criticality: the most demanding standards require validating and inspecting software code to prove evidence of behavior correctness.

Much functionality is now implemented with software [START_REF] Leveson | An investigation of thetherac-25 accidents[END_REF], which has many advantages: easier upgrade and customization, affordability for building and ease of adaptation to particular needs. However, this trend increases system complexity of software components collocated on the same networked execution platform. This creates new challenges due to software-induced fault root causes that are difficult to test for [START_REF] Feiler | Challenges in validating safety-critical embedded systems[END_REF]. For example, one noncritical component may overrun its deadline so that critical function does not have enough computing resource.

Current Problem

Recommended practice standards for system safety assessment and certification, such as ARP4761 [START_REF]ARP4761 -Guidelines and Methods for Conducting the Safety Assessment Process on Civil Airborne Systems and Equipment[END_REF] or DO-178B/C [START_REF]Software considerations in airborne systems and equipment certification[END_REF], provide guidance for validation and verification of safety-critical software and systems. In current practice the safety assessment process is is labor-intensive, mostly relying on engineer's ability to correctly interpret a textual specification of the system. In addition, most errors are introduced during requirements and architecture design phases [START_REF]The Economic Impacts of Inadequate Infrastructure for Software Testing[END_REF] but are likely not detected until integration or operational phases. Resulting rework efforts late in the development process at 100-1000 times the cost of in-phase correction make such systems increasingly not affordable and delay in product delivery [START_REF] Hagen | Delivering military software affordably[END_REF].

System safety requirements are often not refined into software safety requirements and safety analysis does not extend into identifying software induced hazards and into verifying software design against these safety requirements to ensure that potential software errors are avoided or correctly handled. For example, for safety purposes, a software subsystem must be checked to ensure that it does not send more than its bandwidth allocation on a shared network in order to assure timely delivery of data between other subsystems on the same network. Another example is to ensure that a change in the deployment configuration of software onto hardware to balance the workload across processors does not violate assumptions about non-collocation of software subsystems on the same processor or the isolation of subsystems with different criticality level in a mixed criticality application system.

A formalized definition of each component allows integration issues to be detected analytically during the design process, rather than system integration test. This would thus address one issue to reduce the re-work efforts and keep software production affordable [START_REF] Hagen | Delivering military software affordably[END_REF][START_REF]The Economic Impacts of Inadequate Infrastructure for Software Testing[END_REF].

Approach

To address these issues, we propose to automate the safety validation process and generate validation materials from formal specifications. To do so, we propose an architecture centric modeling framework that captures the system and software architecture annotated with safety-related requirements and auto produce certification documents [START_REF]ARP4761 -Guidelines and Methods for Conducting the Safety Assessment Process on Civil Airborne Systems and Equipment[END_REF]. This would increase stakeholders' confidence in system reliability, safety and correctness.

We implement such a framework by adding a specification of faults and hazards, error propagation and mitigation behavior to architecture models expressed in the SAE International Architecture Analysis and Design Language (AADL) standard [START_REF]AS5506 -Architecture Analysis and Design Language[END_REF] and its Error Model Annex standard [START_REF]AADL Error Model Annex[END_REF]. These annotations enhance the existing architecture model with information that supports the various safety and reliability practices of the ARP4761 standard from the same architecture model and complement other form of software system analysis as well as software system builds from validated models. This is shown in Figure 1. The paper is organized as follows. We first give an overview of AADL and the ARP4761 [START_REF]ARP4761 -Guidelines and Methods for Conducting the Safety Assessment Process on Civil Airborne Systems and Equipment[END_REF] standards. Then we introduce the Error Modeling extension of AADL for representing safety concerns. This is followed by a description of the tool support for automating certification practices required by ARP4761 [START_REF]ARP4761 -Guidelines and Methods for Conducting the Safety Assessment Process on Civil Airborne Systems and Equipment[END_REF]. Finally, we illustrate the application of our approach with a case study.

Related Work

Existing literature [START_REF] Leveson | An investigation of thetherac-25 accidents[END_REF][START_REF] Ben-Ari | The bug that destroyed a rocket[END_REF] shows evidence that software errors and bugs might have catastrophic consequences. Several methods and approaches address this concern: some [START_REF]ARP4761 -Guidelines and Methods for Conducting the Safety Assessment Process on Civil Airborne Systems and Equipment[END_REF] focus on hazards as result of failure events and their propagations(and evaluate system safety using Fault-Tree Analysis -FTA-or Failure Mode and Effects Analysis -FMEA), while others [START_REF] Leveson | A new approach to hazard analysis for complex systems[END_REF] focus on safety-related constraints that must be satisfied by a system design.

Our contribution in this paper aims to support safety evaluation (such as ARP4761 [START_REF]ARP4761 -Guidelines and Methods for Conducting the Safety Assessment Process on Civil Airborne Systems and Equipment[END_REF]) from an architecture model and ensure system consistency across different notation and analysis. To do so, we reuse an existing industry standard architecture language [START_REF]AS5506 -Architecture Analysis and Design Language[END_REF] and extend it to support safety evaluation. Similar extensions exist for expressing constraints on architecture models.

Architecture Analysis Design Language

The Architecture Analysis and Design Language (AADL) [START_REF]AS5506 -Architecture Analysis and Design Language[END_REF] is a modeling language standardized by SAE International. It defines a notation for describing embedded software, its deployment on a hardware platform, and its interaction with a physical system within a single and consistent architecture model.

The core language specifies several categories of components. For each one the modeler defines a component type to represent its external interface, and one or more component implementations to represent a blue print in terms of subcomponents. For example, the task and communication architecture of the embedded software is

Latency Analysis

Code Generation modeled with thread and process components interconnected with port connections, shared data access and remote service call. The hardware platform is modeled as an interconnected set of processor, bus, and memory components. A device component represents a physical subsystem with both logical and physical interfaces to the embedded software system and its hardware platform. The system component is used to organize the architecture into a multi-level hierarchy. Users model the dynamics of the architecture in terms of operational modes and different runtime configurations through the mode concept. Users further characterize components through standardized properties, e.g., by specifying the period, deadline, worst-case execution time for threads.

The language is extensible; users may adapt it to their needs using two mechanisms:

1. User-defined properties. New properties can be defined by users to extend the characteristics of the component. This is a convenient way to add specific architecture criteria into the model (for example, criticality of a subprogram or task) 2. Annex languages. Specialized languages can be attached to AADL [START_REF]AS5506 -Architecture Analysis and Design Language[END_REF] components to augment the component description and specify additional characteristics and requirements (for example, specifying the component behavior). They are referred to as annex languages, meaning that they are added as an additional piece of the component. In this paper we will discuss the Error Model Annex language.

The AADL model, annotated with properties and annex language clauses is the basis for analysis of functional and non-functional properties along multiple dimensions from the same source, and for generating implementations, as shown in Figure 2. AADL has already been successfully used to validate several quality attributes such as Security [START_REF] Hansson | Modeling and validating security and confidentiality in system architectures[END_REF][START_REF] Feiler | Challenges in validating safety-critical embedded systems[END_REF], Performance or Latency [START_REF] Feiler | Flow latency analysis with the Architecture Analysis and Design Language (AADL) -TNCMU[END_REF]. Supporting analysis functions have been designed in the Open Source AADL Tool Environment (OSATE) [3], an Eclipse-based framework.

In order to support safety validation, our contribution to the language and its associated tools are:

1. Augmenting the original Error Model Annex language for AADL with safety semantics and a fault ontology to support the modeling of error behaviors.

Developing new tools that automatically produce safety validation materials from AADL models with

Error Model annotations.

Some existing work partially addresses the automation of safety evaluation using the original Error Model Annex standard (for example by generating failure effect analysis [START_REF] Ern | Characterization of failure effects on aadl models[END_REF] and Fault-Tree Analysis [START_REF] Rugina | Software dependability modeling using an industry standard architecture description language[END_REF][START_REF]ARP4761 -Guidelines and Methods for Conducting the Safety Assessment Process on Civil Airborne Systems and Equipment[END_REF]). However, the support addresses a subset of the required documentation. Covering other needs is a new challenge and requires appropriate semantics and associated tools.

The next section presents the ARP4761 [START_REF]ARP4761 -Guidelines and Methods for Conducting the Safety Assessment Process on Civil Airborne Systems and Equipment[END_REF] safety standard, detailing the necessary constructs to add in AADL models for its support.

SAE ARP4761

SAE ARP4761 is a standard recommended practice for evaluating system safety and reliability. It defines a process, identifies applicable methods/approaches and illustrates their use to a case-study related to the avionics domain.

The process consists of a Functional Hazard Assessment (FHA) of the global system (e.g. the Aircraft). It is the input to a Preliminary System Safety Assessment (PSSA) and System Safety Assessment (SSA) of each sub-system.

The PSSA consists of a FHA and Fault-Tree Analysis (FTA) of the sub-system under investigation. FTA provides a convenient view of system fault hierarchy and dependencies, highlighting the root cause of each failure.

Establishing it for each sub-system (for example, loss of power) in relation with the overall system failures (for example, loss of the braking system of the aircraft due a failure of power supply) helps in understanding the impact and propagation of each fault in the architecture.

The SSA is a continuation of the PSSA that provides evidence that metrics, values, and data established and obtained in the PSSA could be verified and validated. To do so, several methods may apply. Among them, the use of formal specification is recommended. It could be used to analyze, simulate and verify system characteristics.

The AADL Error Model Annex

The Error Model Annex is a standardized extension to the core language for adding component safety-related information to AADL models. This annex allows users to specify error behavior state machines whose transitions are triggered by error events and whose effects are identified as outgoing and incoming error propagations. A first version of the Error-Model Annex was published in 2006 [START_REF] Rugina | Software dependability modeling using an industry standard architecture description language[END_REF], this effort is a revision that extends its notation and semantics. The enhanced Error Model Annex language supports architecture fault modeling in several ways:

• Focus on types of errors: An error type system that allows the user to characterize fault occurrences, error state and error propagation in a consistent manner. A set of standardized types to characterize error propagations represents a common fault ontology. • Focus on error propagation between components: For each component the user can specify outgoing and incoming error propagations of error types being propagated and of error types expected to be contained. The error propagation paths between components are determined by connections and deployment bindings. In addition, each component includes a specification of whether it is the source of an error propagation, the sink of an error propagation, or passes on incoming error propagations, possibly transforming the error type into a different one. This level of architecture fault model specification allows for hazard identification, fault impact analysis, and stochastic fault analysis.

•

Error Types and Fault Ontology

The error type mechanism identifies and classifies errors into type hierarchies. Types within the same type hierarchy cannot occur at the same time. As shown in Figure 3 and Listing 1, timing error has two sub-types: late delivery and early delivery, which are mutually exclusive.

An error type set is used to specify sets of possible error types. Listing 1 shows an error type set that consists of all subtypes of TimingError and a value error of type InvalidValue. These error type set are used to specify possible error event types and error propagation types. Since the error types are part of a type system, type checking of these type sets ensures that any error type being propagated out of a component can be handled by other components this component interacts with. For example, one component may specify MySet as outgoing error propagations, while another component indicates that it expects only TimingError as incoming error propagation. The Error Model Annex includes a standard set of error types to represent an ontology of commonly propagated effects. The ontology draws on previous work on formally specifying error propagation behavior [START_REF] Paige | Models in software engineering. Chapter FPTC: Automated Safety Analysis for Domain-Specific Languages[END_REF][START_REF] Powell | Failure mode assumptions and assumption coverage[END_REF]. The ontology consists of the following hierarchies of error types:

• Omission and commission errors in the service provided by a component or of individual service items (messages, commands, etc.), • Timing errors and value errors on individual items being communicated, • Rate and sequence errors for streams of service items (e.g., streams of sensor readings),

• Replication errors in the form of asymmetric value, timing, and omission errors in redundant systems, and Timing Error

Late Delivery Early Delivery

Myset : type set {TimingError, InvalidValue} ;

Listing 1 -Error-Type Set Example

• Concurrency errors when accessing shared logical or physical resources.

Errors that occur inside a component, e.g., a software component in a fault containment unit such as a protected address space or partition, manifest themselves to other components as error propagation of one of the above error types. The error types of the fault ontology are defined in an error type library. Modelers can extend this set of error types, and define aliases, e.g. NoPower as alias for ServiceOmission. Modelers can also define their own error type hierarchies, for example, error types to characterize error events to characterize errors in software components, such as stack overflow, array out of bound, or divide by zero.

Component Error Events and Propagation

The annex introduces the concept of error event that represents an internal error occurring within a component when a fault is activated. This event may propagate to the other components along error propagation paths. These are the connections between the components and the deployment bindings between software and hardware components. Note that users can also specify recover events to model the ability of a component to return to a working condition due to fault management and repair events to model the result of a repair activity that involves replacing system parts. Error propagations are specified for incoming and outgoing component features, such as ports and access features, as well as for bindings. Outgoing propagations specify the error types that are expected to be propagated out and error types that are expected to be contained by the component. Incoming propagation specifications indicate the types of errors that a component is willing to accept and those that it expects not to be propagated. In addition the modeler can specify error flows for components. An error flow is an error source (a component internal error event results in a propagation), an error sink (the received error propagation is contained or masked by the component), or an error path (the component passes the error through as an outgoing propagation or it may transform it into a different propagated error type).The error events, propagations, and flows can have properties that indicate a hazard characterization and a probability of occurrence. This provides a basis for early safety analysis similar to the Fault Propagation and Transformation Calculus (FPTC) [START_REF] Paige | Models in software engineering. Chapter FPTC: Automated Safety Analysis for Domain-Specific Languages[END_REF].

Component Error Behavior

The error behavior of an individual component is characterized by an error behavior state machine. Such state machines can be defined as reusable items in an error model library. A component state defines a particular state of the component regarding its error behavior. A basic state machine would contain two states: Operational (active when the component is operating without any error) and Failed (active once an error is triggered). A transition defines the condition under which a state change occurs. It is composed of a source state (the initial state of the component),a destination state (the final state after the transition is triggered)and a condition (error events that need to be triggered/activated to activate the transition). Using or previous example, two transitions could be added:

1. One from Operational to Failure triggered when the Failure error event is activated.

2. One from Failure to Operational triggered when the Recover event is activated.

Figure 4 -Error Behavior State Machine

Listing 2 illustrates the textual declaration of the state machine and Figure 4 shows its corresponding graphical representation. Component error behavior is specified by:

• identifying an error behavior state machine in an error model library,

• specifying component-specific transitions in terms of incoming error propagations,

• specifying conditions under which an outgoing error propagation occurs,

• specifying conditions under which an error state or error propagation is detected by the actual system.

Operational Failed

Recovery Failure This is done in an annex subclause declared inside a component type or component implementation. These declarations specify possible mappings of error types from an error event or incoming propagation to a resulting error type of a transition destination state, the error type of an outgoing propagation, or the error code used by the actual system to report a detected error condition.

Composite Error Behavior

The error behavior of a system component can also be specified in terms of the error behavior of its parts. For example, a coffee machine is in the Failed mode when one of its sub-part (the boiler or the filtering system) is Failing. The Error Model Annex language supports this through composite error behavior specifications.

For example, if a system contains two redundant sensors, the main system will be in the failure error state if both sensors are failing. Otherwise, it will still be in the operational state. Listing 3 shows how to specify such a state machine using the textual description of the language.

Predefined Error Properties

The Error Model Annex introduces properties to capture error specific characteristics. It utilizes the property mechanism of the core AADL language for that purpose. This means that modelers can define additional Error Model specific properties beyond those predefined in the standard document. In particular, the following properties are of interest in this paper:

• Hazards: contains several fields describing the fault characteristics: failure and effect descriptions, severity, likelihood, operational phase, environment, risk, comments, etc. This property allows multiple hazard characterizations to be associated with an error source, outgoing propagation, error state, and can be different for specific error types. This property is processed to produce the FHA report. • OccurrenceDistribution: specifies the distribution method used to compute the error event distribution (fixed, exponential, etc.) and its associated parameters (occurrence rate, probability, etc.).

Supporting the Safety Evaluation Process

We automate the safety analysis process by processing the architecture fault model (i.e., the core AADL models enhanced with Error Model clauses), generating appropriate analysis models, such as fault propagation graphs, Markov models and fault trees, and producing documentation required by ARP4761 (for the Preliminary System Safety Assessment -PSSA -and the System Safety Assessment -SSA):

• Fault Hazard Assessment (FHA): a spreadsheet document list and document all potential errors that may occur in the architecture • Fault-Tree Analysis (FTA): a hierarchical (tree) view of errors propagations dependencies in the system (showing that are the conditions for a fault to occur) • Formal Methods with Markov Analysis (MA): a mapping to a specific notation that is amenable to validate and verify system safety properties (for example, that failure probability of a component). For this purpose, we export the AADL notation into a Markov Chain model. • Failure Mode and Effects Analysis (FMEA): a document that show all error paths within the architecture (how an error within component may impact the others).fault.

error

Functional Hazard Assessment (FHA)

The Functional Hazard Assessment (FHA) document consists in an examination of system functions and a list of all potential failure. It identifies and classifies failure conditions according to their severity. For each identify failure, the FHA report would report design constraints, annunciation of failure condition and other relevant information.

In terms of implementation, this is a document such as a spreadsheet that enumerates faults/failure, its potential contributors and their associated information (description, condition, operational phases, effects, etc.).Generating the FHA from the AADL model can then be achieved by processing the model and extracting information (properties) related to elements that may generate an error (error event, error propagation, etc.). Then, the tool retrieves relevant association and builds a document summarizing and constituting the FHA.

Fault Tree Analysis (FTA)

The ARP4761 standard describes the FTA as a failure analysis that focuses on one particular undesired event and provides a method for determining its causes. The FTA shows the hierarchical errors occurrences that lead to a top event. For example, the FTA for the loss of portable and self-powered device can be the loss of power (an error event) that can be decomposed into other error events such as loss of primary and redundant power sources (e.g. batteries).Our tool interprets the composite error behavior specification to automatically generate the fault tree from a given state to generate a fault tree representation. Given a specific error state of a component, the tool analyzes all contributors and adds them into the tree.

Example

We apply our approach to a case study that contains several components with error model annotations. The following sections describe its translation into AADL and the use of our tools to support ARP4761 safety process.

Overview and System Description

The system is composed of three sensors, three processors connected by a bus and two actuators. The three sensors are operated by the same processor (input processor), which retrieves data and send it to the main processor through the bus. The main processor does some computation on the data and sends the results to the output processor (through the same bus) that operates the actuator devices. The high-level architecture is shown in Figure 5. The system specification lists the following potential errors:

• Sensors have a permanent failure every month • Actuators have a permanent failure every two months • Processors have two kind of failures: o A permanent failure every year o A transient failure every day, which is recovered in about30 seconds Finally, the overall system is considered in the Failed state if one of the following condition occurs:

• One processor is in the Failed mode (permanent fault)

• Both actuators are in the Failed mode • Two sensors are in the Failed mode

AADL Model

This architecture is then translated into an AADL model (as shown in Figure 6) using the following components:

• Processors are mapped into AADL processor components.

• AADL processor components are connected through a shared bus represented by an AADL bus component using AADL bus access. • Sensors are mapped into AADL device components. They send data to the processors using a dedicated bus (such as a PWM or a serial bus) -mapped into a required bus access feature. • Actuators are mapped into AADL device components and receive data from the output processor using the same bus (PWN or serial bus) -mapped into a required bus access feature. The main system aggregates all these components altogether to represent the hierarchical architecture.

Architecture Fault Model

We add error information to the sensors, actuators, and processors. For the sensors and actuators, we define a basic state machine with two states (Operational and Failed) and one error event (Failure).When the Failure error event is triggered, the component switches from Operational to Failed. Once in the Failed state, it cannot recover as this error is permanent. We associate the state machine with the AADL device type for the sensors and the actuators. We also associate the property OccurrenceDistribution with the Failure event in order to match error occurrence specifications (considering that the time granularity is the second unit): 1.97e-7 for the actuator (one fault every two months) and 3.85e-7 for the sensor (one fault every month). This component error behavior applies to every sensor instance and actuator instances. As for the sensor and actuator, we add the OccurenceDistribution property with the following elements:

• Failure error event with a value of 3.17e-8 (one permanent fault per year)

• ResetEvent error event with a value of 0.03 (recover of a transient fault within 30 seconds)

• FailureTransient error event with a value of 1.15e-5 (one transient fault er day)

The error behavior of the top-level system is specified using a state machine with two states: Operational and Failed. The error state is specified from the state of sub-components using a composite error behavior specification that specifies the active state of the system in terms of the states of its subcomponents, as shown in Listing 4. Finally, we associate the Hazard, property with the error source declarations.

Supporting the ARP4761 Safety Assessment Process Functional Hazard Assessment

Our toolset processes the model to generate the FHA report which enumerates error events and propagation within the architecture that represent hazards. Only hazards with high severity level, reflecting high potential for accident, are included in the report. Being part of the PSSA of the ARP4761, it clearly identifies each component that contributes to a system failure. Using the previously defined AADL model of the embedded control systems, this document lists all error sources occurring from sensors, processors or actuators. Each row corresponds to an error type that can be an error source with its associated component and textual information provided by the Hazards property, including severity and likelihood of a hazard. An extract of the FHA report for this case-study is shown in Figure 8.

Fault Tree Analysis

Another document material used during the PSSA of the ARP4761 is the FTA. To support this analysis, our tools generate the FTA from the AADL model. It represents the decomposition of an error event into a tree with all subevents. To do so, we use the composite error behavior of the system, as defined in listing 4.The failure conditions that trigger a switch of the main system to the failed error state are translated into the Fault-Tree. An extract of the generated Fault-Tree is shown in Figure 9, showing all error events that contribute to switch the top-level system into the Failed error state.

Conclusion

Cyber-Physical must be carefully designed and validated: as an error potentially means mission failure or loss of life, hazards must be evaluated and eliminated. For that reason, development of such systems requires following rigorous practice standard to evaluate system safety and show evidence of absence of critical failure. This effort requires the production of various reports that are loosely coupled, which may lead to inconsistencies. In addition, this practice is labor intensive and error-prone.

To overcome these issues, we have presented an approach to support the safety and reliability evaluation process using architecture (AADL) models. This architecture-centric method leverages the same model for different analyses, resulting in increased consistency between analysis results. Tools automate the generation of documentation materials for supporting the different aspects of the validation process: Fault and Hazard Assessment, Fault-Tree Analysis, etc. We have shown how the Error Model Annex of AADL provides several mechanisms to describe errors/faults, their propagations. They provide a convenient flexibility for systems designers, allowing them to associate error behavior specifications with elements of the model. Also, using the same model for validating different architecture criteria would increase stakeholders' confidence in the correctness of the architecture by showing evidence of requirements enforcement.

Figure 1 -

 1 Figure 1 -Architecture-Centric Model Based Method for System Safety Evaluation Figure 2 -AADL ecosystem for Software System Design and Implementation

  Focus on error behavior of a component: For each component the user can specify an error event, i.e., activation of component-specific faults, recover and repair events, their occurrence probability, how they together with incoming error propagations affect the error state of the component, under what conditions outgoing error propagations occur, and when error behavior is detected and addressed by the component. • Focus on the composite error behavior of a component: For each component with subcomponents the user can specify under what conditions in terms of subcomponent error states the component is in a particular error state. This mapping of subcomponent error state into a component error state abstraction reflects fault tree logic and allows for architecture fault analysis at different levels of the architecture hierarchy. The following paragraphs introduce the main concepts of the error-model annex: faults types, error events, propagations points and the error state machine for specifying the component error behavior.

Figure 3 -

 3 Figure 3 -Error-Type Hierarchy

Figure 5 -Figure 6 -

 56 Figure 5 -Overview of the Embedded Case Study

Figure 7 -

 7 Figure 7 -Error Behavior State Machine for the Processor ComponentsFor the processors, we specify a state machine with three states (Operational, Failed and TransientFailure) and three error events (Failure, FailureTransient and ResetEvent). The corresponding state machine is shown in Figure7:•The FailureTransient error event represents the occurrence of a transient event with the component switching to the TransientFailure state. • The recovery of a transient failure is represented by the ResetEvent error event that switches the component from the TransientFailure to the Operational state. • When the Failure error event is triggered, the component switches to the Failed state. As this is a permanent error, it never recovers from it.

Figure 8 -Figure 9 -

 89 Figure 8 -Generated Functional Hazard Analysis

Listing 4 -

 4 Failed or a2.Failed ]-> Failed ; [(s1.Failed and s2.Failed)or(s1.Failed and s3.Failed)or(s3.Failed and s2.Failed)]-> Failed ; [po.Failed or pm.Failed or pi.Failed ]-> Failed ; end composite ; Composite Error Behavior of the Overall System

System Architecture with Safety Information AADL models System Analysis Safety Evaluation Software Build AADL Requirements validation Performance Analysis Consistency Validation Security Analysis

Error Behavior State Machine Listing 3 -Example of a Composite Error Behavior These

  safety analysis functions are included in the Open Source AADL Toolkit Environment (OSATE) [3], our Eclipsebased AADL modeling framework. It is freely available under an Open-Source license (the Eclipse Public License). OSATE utilizes interfaces with existing safety analysis tools (as OpenFTA [14] for the FTA) and can be adapted to established in-house tool suites.The next sections illustrate the support of the FHA, FTA generation. The other methods are supported in a similar fashion and have been demonstrated on the wheel braking systems example that accompanies the SAE ARP4761 standard document [Delange].

	behavior Simple	composite error behavior
	events failure : error event ;	states
	recov : error event ;	[ sensor1.Failed and
	states	sensor2.Failed ]-> Failed ;
	Operational : initial state ;	[ sensor1.Operational or
	Failed : state ; transitions end behavior ; t2 : Failed -[recov]-> Operational; t1 : Operational -[ failure ]-> Failed;	sensor2.Operational ]-> Operational; end composite ;
	Listing 2 -

Acknowledgements

Copyright 2013 Carnegie Mellon University. This material is based upon work funded and supported by the Department of Defense under Contract No. FA8721 05-C-0003 with Carnegie Mellon University for the operation of the Software Engineering Institute, a federally funded research and development center. NO WARRANTY. THIS CARNEGIE MELLON UNIVERSITY AND SOFTWARE ENGINEERING INSTITUTE MATERIAL IS FURNISHED ON AN "AS-IS" BASIS. CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY KIND, EITHER EXPRESSED OR IMPLIED, AS TO ANY MATTER INCLUDING, BUT NOT LIMITED TO, WARRANTY OF FITNESS FOR PURPOSE OR MERCHANTABILITY, EXCLUSIVITY, OR RESULTS OBTAINED FROM USE OF THE MATERIAL. CARNEGIE MELLON UNIVERSITY DOES NOT MAKE ANY WARRANTY OF ANY KIND WITH RESPECT TO FREEDOM FROM PATENT, TRADEMARK, OR COPYRIGHT INFRINGEMENT. This material has been approved for public release and unlimited distribution. Carnegie Mellon ® is registered in the U.S. Patent and Trademark Office by Carnegie Mellon University. DM-0000789


Julien Delange
email: jdelange@sei.cmu.edu

Peter Feiler

Design and Analysis of Multi-Core Architecture for Cyber-Physical Systems

Keywords: multi-core, ARINC653, model-based engineering, AADL

Cyber-Physical Systems are becoming software intensive, collocating many functions on a single processor and requiring a significant processing capacity which increased over the years. In recent years, improving processing performance has been achieved by adding more processing cores on the same chip rather than increasing its frequency. This new design also introduces issues: interaction among cores may impact software performance and might also arm software isolation layers, such as the one defined in ARINC653. For that reason, software using multi-core architecture must be carefully designed and specified with hardware and software aspects. This would help to analyze the system and detect potential design issue. This paper proposes an approach to represent multi-core architectures and their association with software artifacts, such as the ones used for cyber-physical systems (e.g., the ARINC653 platform). For that purpose, we use the AADL language and define specific modeling patterns with new properties.

Introduction 1.Context

Cyber-physical systems (CPS), as used in military or avionics domains, become increasingly software-reliant and operate many functions. Software defects may have minor (temporary disturbance) or major impact (mission failure), depending on execution environment, system criticality, and other criteria. Enforcement of continuity of operation is difficult because software components interact and may impact each other. Actual military aircraft systems contain more than 1.7M lines of code [START_REF]Lockheed Martin F-22 Raptor[END_REF], and new civil aircraft feature more than 4M lines of code [2]. Thus, design and validate software by using traditional design techniques is an overwhelming task.

One solution consists of isolating software functions according different criteria (criticality level, component provider, etc.) so that one cannot interfere with another. Thus, each function can be analyzed separately, easing the overall validation process. For that purpose, the ARINC653 [3] standard (for avionics systems) defines a specific runtime that isolates system functions from each other.

However, as such systems continue to grow and they now require a significant processing power. This trend was traditionally addressed by upgrading hardware and increasing the processor speed, but is now achieved by using multi-core architectures with processors containing several processing cores on the same chip. As these cores share resources (memory, caches, buses), they may interact each other so that one function executing on one core may affect others executing on remaining cores. This can impact the underlying software architecture by breaking software isolation as defined in ARINC653 [3].

Problem and Approach

Software executing on one core may generate disturbance and impact functions executing on other cores, even when using specific runtime with isolation services such as ARINC653 [3]. This may affect different business drivers: from a reliability perspective, a function issuing several requests on a shared bus may postpone the execution of a function that is using the same resource so that it overruns its deadline. From a security perspective, a function classified at a low security level may also read data from a software component classified at a higher security level if their processing cores use shared memories. These issues are dependent on both software and hardware architectures as well as the system business goals. Thus, there is no standard and general solution, and these issues must be evaluated on a per-project basis.

For that reason, modeling multi-core processors and their association to the software and architecture (such as ARINC653 [3]) would help system designers to review, analyze, and detect potential issues when using multi-core processors. This would also help represent different system criteria, such as use of shared resources (caches, buses, devices, etc.) allocation strategies of software on multiple cores impact on software scheduling allocation of mixed-criticality levels on several cores

We propose an approach to model such architectures with appropriate patterns using the Architecture Analysis and Design Language (AADL) [START_REF]SAE International: AS5506 -Architecture Analysis and Design Language[END_REF], a language that already supports analysis tools for CPS design and analysis. It is compatible with the core language and its extensions (such as the ARINC653 annex [START_REF]SAE International: SAE Architecture Analysis and Design Language (AADL) Annex[END_REF]) so that use of multi-core architectures does not require a new model and can be added as a component refinement. The paper is organized as follows:

1. Overview of the related work: CPS software architectures (such as the ARINC653

[3] partitioned architecture), multi-core processors, and AADL 2. Modeling partitioned multi-core systems with AADL 3. Application with a case study 4. Conclusion and perspectives 2 Related Work

Multi-Core Architectures

Until recently, increasing processing capability of processors consisted of increasing their frequencies or adding more transistors on the same chip. This trend has been used for years, but the process has reached its limits; the number of transistors being collocated in the same area have some physical limitations. One solution consists of reusing the symmetric multiprocessing (SMP) architecture that executes software functions in parallel. Collocated processing cores also share resources (buses, memory, caches, etc.), which may create disturbance between concurrent cores. Most multi-core processors have their own cache (L1) and share resources (such as the second cache (L2)) through one or several dedicated buses, as shown in Figure 1.

Unlike single-core architecture, applications performance with multi-core processors mostly depends on software: a specific scheduler for multi-cores, data dependencies between tasks, use of lock mechanisms between concurrent threads, etc. Sharing resources may create problems [START_REF] Paolieri | Hardware support for WCET analysis of hard real-time multicore systems[END_REF][START_REF] Schliecker | System level performance analysis for real-time automotive multicore and network architectures[END_REF][START_REF] Anderson | Real-time scheduling on multicore platforms[END_REF], especially if a core issues many memory access requests that increase bus latency.

On the other hand, having several cores may be of special interest, especially when isolating applications (such as in ARINC653 [3]). Each software partition may be allocated to a separate partition, ensuring time isolation. However, this may create disturbance, especially because some resources are still shared (such as the L2 cache) and may break the partitioning policy. Several research efforts have already been performed in that context.

ARINC653 and Partitioned Runtime

ARINC653 [3] is an industrial avionics standard published by Aeronautical Radio. It defines a set of services and a standardized interface to isolate software applications into partitions. Each partition is independent with its own resources and appears to be running as if it were allocated to a single processor. The isolation policy is enforced by an underlying kernel (as shown in Figure 2) in terms of space and time:

-Space: Each partition is associated to a unique address space (memory segment) to store code and data. One partition cannot read/write other segments. -Time: Time frames are allocated to each partition to execute their threads and cannot be overrun. In addition, each partition uses its own scheduling policy because the overall system has two scheduling layers: kernel level (scheduling of partitions) and partition level (scheduling of partitions tasks).

Most of the time, the kernel-level scheduler uses a static scheduling protocol that executes partitions at a fixed rate called the major time frame. An example of such isolation is shown in Figure 3 with two partitions being executed consecutively according to a fixed and pre-configured timeline. Because partitions are isolated into their memory space and cannot share memory, communications are implemented with a dedicated inter-partition communication service. Cross-partition communication channels are pre-configured at design time so that no partition can create a communication path that has not been explicitly declared.

Partition 1 Partition 2 Isolation Kernel

Finally, the standard defines a service to detect, recover, and isolate fault occurrence and propagation. A fault can occur at different level: kernel, partition, or task. Upon fault occurrence, a dedicated function is executed to fix the error.

ARINC653 defines a set of common faults/exceptions (that can be extended by each specific ARINC653-compliant OS) that may arise in the system. They range from software fault (e.g., division by zero) to hardware fault (e.g., loss of power). The system provides the flexibility to detect and recover fault at different levels so that the system designer can easily implement a system health-monitoring policy.

As new systems are currently switching from single-to multi-core processors, one major concern is to ensure isolation enforcement with new hardware components. To do so, users need methods and tools to model an ARINC653 software architecture (with partitions, tasks, communication channels, etc.) and its association on the hardware platform using either using single-or multi-core processors. Thus, this representation could then be supported by analysis tools to check scheduling feasibility and any potential issue that may break ARINC653 isolation principles.

AADL

AADL [START_REF]SAE International: AS5506 -Architecture Analysis and Design Language[END_REF] is a modeling language standardized by the Society of Automotive Engineers (SAE). It defines a notation for describing architecture hardware and software concerns within a single and consistent model. The language uses a component-based approach, with each system artifact being defined as a component. The core language specifies several components (processor, process, bus, thread, etc.). Each one defines its interfaces and characteristics. Components are aggregated (with one component containing subcomponents; for example, a task includes several subprograms or a process contains several tasks) and connected (for example, a processor accesses a bus or a memory, or two tasks are connected to exchange values/data). Component-specific characteristics are parameterized using properties (for example, period of a task, size of a memory, speed of a processor). The components composition constitutes the system architecture.

The language is extensible; users may adapt it to their needs using two mechanisms:

1. User-defined properties. New properties can be defined to extend the components' characteristics. This is a convenient way to add specific architecture criteria into the model (for example, criticality of a subprogram or task)

2. Annex languages. Third-party languages [START_REF] Rugina | An architecture-based dependability modeling framework using AADL[END_REF][START_REF] Frana | The AADL behaviour annex -experiments and roadmap[END_REF] can be attached to AADL components to augment their description and specify additional characteristics and requirements (for example, specifying the component behavior [START_REF] Frana | The AADL behaviour annex -experiments and roadmap[END_REF] by attaching a state-machine). They are referred to as annex languages, constituting additional pieces of information related to the component.

AADL provides two views to represent models:

1. The graphical view outlines components' hierarchy and dependencies (bindings, connection, bus access, etc.). While not providing all architecture details, it is very useful for documenting the architecture. 2. The textual view shows the complete model description, with component interfaces, properties, and languages annexes. It is appropriate for users to capture system-internal details and for tools to process and analyze the system architecture from models. The language is supported by several tools for analyzing system requirements or producing the implementation, as shown in Figure 4. AADL has already been successfully used to validate several quality attributes such as security [START_REF] Hansson | Modeling and validating security and confidentiality in system architectures[END_REF], performance, and latency [START_REF] Feiler | Flow latency analysis with the Architecture Analysis and Design Language (AADL) -tn cmu/sei-2007-tn-010[END_REF]. Supporting analysis functions have been implemented in the Open Source AADL Tool Environment (OSATE) [13], an Eclipse-based tool that supports AADL.

A standard annex document (the ARINC653 annex [START_REF]SAE International: SAE Architecture Analysis and Design Language (AADL) Annex[END_REF]) provides guidance to model avionics architecture, as defined in the ARINC653 [3]. However, modeling of multicore applications has not been yet explored and no modeling pattern has been proposed. This makes the design of such systems more difficult because each model would represent the architecture in a different manner that is not suitable for all analysis tools.

Our contribution consists of proposing AADL modeling patterns for multi-core processors that are consistent with the existing standards documents, including the AR-INC653 annex [START_REF]SAE International: SAE Architecture Analysis and Design Language (AADL) Annex[END_REF]. Keeping compatibility with existing modeling patterns would also help the transition of models using single-core to multi-core processors and keep the potential changes to the minimum.

3 Model of Partitioned Multi-Core Architectures

Multi-Core Processors

Processor cores are hardware parts similar to physical processors: they access a bus to read/write into shared resources, have their own private resources, etc. Thus, a core is associated with an AADL processor component and a multi-core processor with an AADL system component containing multiple AADL processor subcomponents, each one representing a separate core. This modeling approach also provides flexibility: an AADL system can contain other components to represent heterogeneous architectures, such as system on chip (SoC), that include a network controller, USB bus, and other shared resources.

In order to specify processor requirements, we introduce a new dedicated AADL property to describe the following processor characteristics:

-Speed: using various metrics such as core frequency or instructions per second -Power Dissipation: using a range value for each core -Power Consumption: using a range value for each core, reflecting the power used at full speed or when using energy-saving mode

Binding with Isolation Runtime

The ARINC653 annex [START_REF]SAE International: SAE Architecture Analysis and Design Language (AADL) Annex[END_REF] for AADL mandates to model partitions at runtime using a virtual processor within a processor component. Then, the partition address space (AADL process that abstracts partition code and data) is associated with this runtime using the regular AADL property (Actual Processor Binding). Representing partitioned architectures on multi-core processors uses the same approach: the partition's runtime (virtual processor) is added to each core (processor) and its address space (process) bound to it. However, in the context of multi-core, a partition can be associated to several cores according to a particular policy (a partition being relocated from one core to another upon failure, redundancy, etc.). To specify this particular requirement, the following approaches are proposed:

1. Define the partition runtime (virtual processor) separately and bound it to the partitions' supporting cores (processor) with the Actual Processor Binding or Allowed Processor Binding properties. Then, we also associate it with the partition address space (process). This approach assumes that the underlying execution platform (Operating System) can relocate the partition execution context from one core to another. For one partition executed on two cores, this modeling pattern would use one virtual processor (associated with the partition address space -an AADL process component) bound to two processors, as shown on Figure 5. We also associate the memory segment to the virtual processor, not the process, which means that when relocating the partition, the same memory segment would be used. 2. Define as many runtimes (virtual processor) as required on each core (processor) and associate the partition address space (process) with each of them. This approach assumes that the underlying OS also isolates the different runtimes in separate memory segments (each one being associated with a separate virtual processor) and would relocate the context between partitions' runtimes when relocating the partition from one core to another. For one partition executed on two cores, this modeling pattern would use two virtual processors, each one contained within a core (processor). Then, the partition address space (process) is associated with both virtual processor components, as shown in Figure 6.

Users may distinguish the cores that can execute the partition from the one that is actually executing it. For that, the language defines two properties:

1. Allowed Processor Binding provides the list of cores that may execute the partition. These cores may be selected when relocating the partition. 2. Actual Processor Binding defines the list of cores that execute the partition.

As properties may be mode-specific, we can define bindings for each component mode, showing the different deployment strategies according to the system state.

Case Study

We established a model of a multi-core partitioned architecture. The graphical model is shown in Figure 7. The textual model is not included in this paper but is available online at the official OSATE examples repository [START_REF]AADL examples repository[END_REF] and documented on the official AADL wiki [START_REF]AADL official wiki[END_REF]. This architecture defines an architecture that is representative of an acquire-and-control system with three partitions:

1. Acquisition that retrieves raw values from sensors 2. Processing that receives the data and does some computation (filtering bad data, checking values according to predefined bounds, etc.) 3. Control that activates motors and/or thrusters according to the received command These partitions are then associated with a memory segment (space isolation of an ARINC653 architecture) and a dedicated runtime (dashed boxes in the middle-right). Then, these components are associated with the processor, which is represented using a single system component:

-The hardware memory component that hosts partitions memory segments is then connected to the processor using a bus access, which is shared among all cores. -Each partition is replicated on two cores. To capture this requirement in the model, we associate each partition runtime virtual processor with two cores (processor). When a failure is detected, the underlying operating system can be relocated from one core to another. In this architecture, six cores are used (two per while two are not associated with any partition. The processor represented is a P4080, an SoC that integrates eight cores on a single chip and provides dedicated functionalities with respect to software partitioning [START_REF] Freescale | P4080 QorIQ integrated processor hardware specifications[END_REF]. The textual AADL model representing a core is shown in Listing 1.1. The main benefits of using the processor AADL component to represent the core are shown by defining bus accesses (use of shared resources) and additional properties (as the speed that may vary according to internal modes).

Conclusion

Cyber-Physical Systems (CPS) become software intensive and requires more processing capacity. For that reason, use of multi-core processors will be mandatory. As this type of architecture may impact software execution, new technologies and tools are required to identify and avoid potential defects.

This paper presents an approach for designing multi-core architectures using AADL. We propose modeling patterns for describing multi-core processors with respect to their attributes. This component aggregation fits with methods and approaches specific to CPSs (such as ARINC653, an avionics standard for building partitioned architecture).

The resulting models would be used as inputs for analysis tools to simulate system execution and detect issues related to CPSs requirements, such as scheduling or security. For example, one application would consist of exporting the AADL notation to a scheduling analyzer to check the enforcement of timing constraints on each core, ensuring that task deadlines can be met according to a specific software allocation on each processor core.

Fig. 1 .

 1 Fig. 1. Example of a multi-core architecture

Fig. 2 .Fig. 3 .

 23 Fig. 2. Architecture of an ARINC653 system

Fig. 4 .

 4 Fig. 4. AADL ecosystem

Fig. 5 .Fig. 6 .

 56 Fig. 5. First modeling pattern for partitioned multi-core architectures

Fig. 7 .

 7 Fig. 7. AADL model of our case-study

processor e500mc f e a t u r e s l 3 Listing 1 . 1 .

 311 a c c e s s : requires bus access l3cachebus ; ram bus : requires bus access ram bus ; t e m p a l e r t : i n event port ; modes Nominal : i n i t i a l mode ; Degraded : mode ; p ro p e rt i e s P r o c e s s o r P r o p e r t i e s : : Speed => [ Freq => 0 . 0 Mhz . . 750.0 MHz; Kind => (FREQ ) ; ] i n modes ( Degraded ) ; P r o c e s s o r P r o p e r t i e s : : Speed => [ Freq => 0 . 0 Mhz . . 1 . 5 GHz ; Kind => (FREQ ) ; ] i n modes ( Nominal ) ; end e500mc ; processor implementation e500mc . g e n e r i c subcomponents dcache : memory M u l t i C o r e C a c h e : : cache {Byte Count => 32 000 ; } ; i c a c h e : memory M u l t i C o r e C a c h e : : cache {Byte Count => 32 000 ; } ; l2cache : memory M u l t i C o r e C a c h e : : cache {Byte Count => 128 000 ; } ; end e500mc . g e n e r i c ; Model or a core of the P4080 processor

Acknowledgments

Copyright 2013 Carnegie Mellon University. This material is based upon work funded and supported by the Department of Defense under Contract No. FA8721-05-C-0003 with Carnegie Mellon University for the operation of the Software Engineering Institute, a federally funded research and development center. NO WARRANTY. THIS CARNEGIE MELLON UNIVERSITY AND SOFTWARE ENGINEERING INSTITUTE MATERIAL IS FURNISHED ON AN "AS-IS" BA-SIS. CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY KIND, EITHER EXPRESSED OR IMPLIED, AS TO ANY MATTER INCLUDING, BUT NOT LIMITED TO, WARRANTY OF FITNESS FOR PURPOSE OR MER-CHANTABILITY, EXCLUSIVITY, OR RESULTS OBTAINED FROM USE OF THE MATERIAL. CARNEGIE MELLON UNIVERSITY DOES NOT MAKE ANY WAR-RANTY OF ANY KIND WITH RESPECT TO FREEDOM FROM PATENT, TRADE-MARK, OR COPYRIGHT INFRINGEMENT. This material has been approved for public release and unlimited distribution. Carnegie Mellon(r) is registered in the U.S. Patent and Trademark Office by Carnegie Mellon University.

DM-0000779