Emmanuel Ledinot

Michel Nakhle

Philippe Robin

Software Factory Testing Tools: an Analysis Framework

Keywords: Software verification and validation, test generation, test execution, static analysis, constraint solving, tool comparison

Introduction

This paper compares seven tools devoted to software verification and validation that are being developed by several participants of MoDriVal project 1 . These tools are classified according to different criteria: the kind of data they process, the services they provide, their underpinning technology and foundations, and the stages of system or software testing process they are relevant to. These tools are:

• Four test generators developed respectively by CEA, Esterel Technologies and University of Orsay. Two of them apply to data-flow programs (MTC Solver, sALLUSTe). The third one is dedicated to state-transition systems (AGATHA), and the fourth one to binary code (OSMOSE).

• A test execution engine (TTS), which is developed by Trialog. • Two static analyzers : FLUCTUAT developed by CEA to estimate rounding errors, and Penjili developed by EADS-IW to detect string buffer overflows. Section 2 presents the classification framework for testing tools that will be used as a reference to position the tools with respect to the testing activities.

Section 3 is a description of the tools from a technological viewpoint, i.e. by focusing on their inner parts and foundations. Section 4 provides additional background on test case definition and coverage criteria that Section 5 refers to. 1 MoDriVal is a subproject of "Usine Logicielle" (Software Factory) project carried out within the French System@tic Cluster, funded by DGE, CG78, CG91, CG92 and CRIF. Section 5 is the core part of the paper, presenting the mapping of the tools on four classification diagrams based on criteria discussed in sections 2 and 4. Section 6 summarises lessons learnt from case studies carried out with the tools by CS, Dassault Aviation, EDF, Hispano Suiza, MBDA and Thales in the course of the MoDriVal project. Then we conclude on the trends for testing tools in the commercial marketplace and the opportunity for the MoDriVal tools presented in this paper to go the market.

Classification framework

The state of the art related to model-based testing tools emphasizes two categories of testing approach:

• Functional testing or "black box"

• Structural testing or "white box". The tools can further be gathered into three families:

• Tools dealing with asynchronous systems,

• Tools dealing with synchronous systems,

• Tools dedicated to data handling. Eventually testing can be deterministic or statistical and may use different techniques:

• Systems of labelled transitions (TGV, STG…) • Constraints solving (BZ-TT/Leirios, AGATHA, GATeL…) • Finite states machines (AsmL Tool Test, SpecExplorer…).

The specialized site http://www.stickminds.com/ references more than 268 testing tools. These tools have been investigated [START_REF] Nakhlé | Document de Travail CS, Projet Usine Logicielle/SP MoDrival, Tâche 2.1/MOD-CS-1 (Le besoin, l'état[END_REF] and have been classified [START_REF] Xanthakis | Le test des logiciels[END_REF] into test design tools, graphical user interface test tools, performance testing tools, test management tools, test implementation tools, test evaluation tools and static analysis tools (see Figure 1 below).

FIGURE 1: CLASSIFICATION OF TESTING TOOLS

Here is a short description of the main categories:

• Analysis: tools that analyse programs without running them; metrics tools fall in this category. It is worth underlying that the limits between the categories are out of focus, because many tools, can belong to several categories.

MoDriVal testing tools and technologies

Let us start with the four test generators. In spite of apparently strong differences, they rely on the same basic idea and use the same core technology.

Test generation of binary code

The testing of legacy binary code may be unavoidable in some circumstances related to certification or management of hardware obsolescence when there is no possibility to develop a new software on the new hardware unit (the old hardware unit is then virtualized on the new one). Specified by EDF and developed by CEA, OSMOSE is designed to handle the binary code of any microprocessor provided that the processor instruction set can be translated into OSMOSE generic instruction set. OSMOSE provides standard reverse engineering functions on binary code (control and data flow analysis, call graph display,…) and generates binary test sets driven by structural coverage criteria. Presently, there is only one predefined coverage criterion (all instruction coverage), but the criteria will be user-definable via an appropriate GUI in the future. The test cases generated can be executed symbolically by OSMOSE to "test the generated tests".

Test generation for symbolic transition systems

AGATHA, developed by CEA, is dedicated to modelling and analysis of networks of communicating transition systems. Reachability analysis of the global state space is performed symbolically, i.e. without a complete instantiation of state or action variables. By using predicates over free state variables, AGATHA symbolic states may represent infinite sets of actual states. AGATHA is used to model automata-oriented specifications or requirements, possibly translated from formal UML activity or sequence diagrams. Verification of safety properties and generation of test cases are the two main capabilities of the tool.

Enhancement of model-level test coverage

Model Test Coverage (MTC) is currently available as a module of Esterel Technologies SCADE Suite. While submitting a model to user-defined tests, MTC is able to log the nodes and the node parts activated by the test scenarios. MTC Solver is a prototype add-on to MTC which is developed by CEA and Esterel Technologies. It aims at facilitating the way to obtain a 100% model-level structural coverage. Given a current coverage ratio, MTC Solver generates additional tests to activate the remaining non-activated parts that are suspected to be possible "dead" nodes. It is also possible to define "observers", in a manner similar to what is done for model-checking of safety properties, and to ask the tool to generate test cases that both increase the model coverage and satisfy the observers.

Statistic test generation of data-flow programs

sALLUSTe is a test generator for data-flow programs developed by CEA and Orsay University/LRI. sALLUSTe handles also structural coverage criteria, but oppositely to MTC solver, it explores randomly the structure of a data-flow model (i.e. a SCADE model in practice). At present the probability distribution mapped on the nodes of the model network of equations is uniform, but in future versions of the tool it is planned that "weights" (testing effort objectives) on structural points of a model (nodes, equations etc.) might be user-defined in order to adjust, i.e. to bias, the statistical coverage.

The four test generators presented here process three different kinds of objects:

• Control flow graphs labelled by binary instructions, • Parallel compositions of symbolic statetransition systems, • Networks of conditioned equations, Three of them are deterministic test generators while the last one is stochastic. However, in spite of significant differences, the tools are based on similar principles and they use similar ways to compute the tests they generate. They proceed as follows :

1. First an execution path is computed on a structure that depends on the structural criterion selected (graph-based coverage, loop unfolding bounds, etc.) and the Boolean conditions met along this path are collected.

In AGATHA, MTC Solver and sALLUSTe the "paths" are traces or multi-cycle sequences of synchronous steps. An user-bounded and user-focused unfolding of cycles (SCADE) or interleaved transitions (AGATHA) is performed. In OSMOSE, a path is a branch of the control flow tree. 2. Second the set of Boolean conditions (predicates over free variables that are the path local reachability conditions) is submitted to a constraint solver that tests if this set of constraints might be satisfied.

When the constraints are satisfied, the constraint solver produces a set of solution intervals for the constrained variables. Any value chosen in these intervals ensures the accessibility of the path.

Eventually every input variable of the model

(AGATHA, MTC Solver, sALLUSTe) or the binary program (OSMOSE) is given an actual value which is randomly chosen in the solution intervals. Constraint solving is the key technology used in step 2 above [START_REF] Gouraud | A new way of automating statistical testing methods[END_REF], [START_REF] Marre | Test sequences generation from lustre descriptions: Gatel[END_REF]. GATeL, which includes the Eclipse constraint solver, or Eclipse per se, is the common core component used by the four test generation tools presented in this paper.

TTCN-3 test generation and execution

TTS is a test execution engine that performs tests on programs hosted in a workstation or in embedded devices. TTS complies with a standard test methodology used by the telecom domain (ISO 9646, TTCN) and uses a black-box testing approach. The latest version of the standard known as TTCN-3 shall be used by the automotive industry in the future to specify the conformance tests of basic software components. Within the MoDriVal project, a new version of TTS compliant to TTCN-3 was developed and integrated with AGATHA test generator described above in order to provide and experiment a model-to-test workflow covering test generation and test execution.

The last two tools (FLUCTUAT and Penjili) considered in this paper are static analysers. These tools provide exhaustiveness of analysis (proofs) to the expense of over-approximation (false negatives) and computational complexity (analysis time and space footprint). Thus they can be considered as verification tools. It is interesting to note that constraint solving (in case of sound and complete constraint solvers) also provides exhaustiveness in satisfiability analysis. There the test generators based on constraint solving such as those described above may be considered as reachability verification tools as well.

Static analysis of rounding errors

FLUCTUAT developed by CEA propagates through ANSI C source code error terms which (over)approximate the rounding errors made by floating point computation. Floating point computation is supposed to conform to IEEE 754 specification. The C source codes may be annotated at some critical control points to provide application-specific information on the value range of given key variables. Because of decidability and computational complexity issues, the accuracy .vs. efficiency tradeoff is currently such that FLUCTUAT may fail to infer precise enough bounds or intervals. Annotations are taken into account by FLUCTUAT and are instrumental in controlling over-approximations. A graphical user interface displays interval or error bars on the source code.

Static analysis of string buffer overflows

Penjili is a static analyser whose development started at EADS Innovation Work within MoDriVal project. It is dedicated to the detection of potential security attacks through string buffer overflows. Penjili processes ANSI C source code files of programs that make extensive calls to string handling libraries. The tool relies on the definition of an abstract domain specially designed for the purpose of tracking efficiently dangerous memory read/write operations in character array manipulation.

Mapping testing tools w.r.t. testing process

Testing Processes

In software engineering processes, inspection and testing activities can be organized in stages according to the V-model (see Figure 2). Component design means that the structure of each individual component is designed. The components have to collaborate with each other and cannot be considered as standalone items. The dependencies between components must be designed too. Components are often designed in an objectoriented way in terms of classes and their relationships. The functional logic is split between interfaces and dependency implementation. The execution environment of the components and the test plan for the components needs to be defined too. The whole testing process depends on who performs the tests, i.e. a component provider, an integrator or a component customer. A provider needs black and white box testing techniques. An integrator needs only black box testing techniques to perform interface testing, A customer uses black box techniques for acceptance testing. The testing process should be assisted with specialized testing tools. The categories of testing tools presented in Section 1 may be mapped onto the V-model of testing as shown below (see Figure 3). Equivalence partitioning: In most cases, the system cannot be exhaustively tested, so the input space must be somehow partitioned. Equivalence partitioning is a test case selection technique in which the test designer examines the entire input space defined for the system under test and looks for sets of input that are processed "identically". Identical behaviour means that test inputs belonging to one equivalence class traverse the same path of execution through the system. Equivalence partitioning is based on the following assumptions:

• If the system works correctly with one test input in an equivalence class, the system works correctly with every input in that equivalence class • Oppositely, if a test input in an equivalence class detects an error, all other test inputs in the equivalence class will find the same error. Equivalence classes are defined from an analysis of the requirement specification document. It is important to note that equivalence partitioning is always based on the test designer's intuition and thus may be imperfect. The guidelines for the equivalence partitioning analysis are:

• If the input specifies a range of values, one valid (within the range) and two invalid (one outside each end of the range) equivalence classes are defined

White box testing techniques

If the source code is available, white box testing techniques can be used. White box techniques ensure that the internal logic of the system is adequately tested. In white box testing, test cases are derived through a careful examination of the source code of the component. White box testing can find errors that are deeply hidden in the source code details. White box testing is used at the component testing stage (see Figure 2). When testing the component at source code level, both the control-flow and the data-flow of the component can be tested. Control-flow testing: Control-flow testing means that different paths according to the control-flow of the component are followed. A standard representation for the control-flow of a component is a flow graph, which abstracts the execution of the component into a graph-like structure. The nodes of a flow graph stand for the statements of the component and the edges stand for the control transfer between the statements. Statements where the control diverges such as conditional statements or loops are the most important items from the control-flow testing point of view. The adequacy of control-flow testing is measured in terms of coverage. The coverage indicates how extensively the system is executed with a given set of test cases. The basic types of coverage are:

• Statement coverage, where each statement is executed at least once. This is the weakest criterion and does not normally ensure a faultless code. 100% statement coverage is usually too expensive and hard to achieve, especially if the source code includes "dead code". • Path coverage, where every possible execution path is traversed. Exhaustive path coverage is generally impractical and impossible because loops increase the amount of execution paths • Branch coverage, where each statement is executed at least once and each decision in the program takes all possible outcomes at least once. Branch coverage criterion is stronger than statement coverage because if all the edges in a flow graph are traversed, then all the nodes are traversed as well.

Branch coverage is also known as decision coverage.

• Condition coverage, where each statement is executed at least once and every condition in a decision in the program takes all possible outcomes at least once. Complete condition coverage does not necessarily imply complete branch coverage so they do compensate each other • Multiple condition coverage, where each statement is executed at least once and all possible combinations of condition outcomes in each decision occur at least once. This is the strongest criterion that requires to test the component with more test cases and in a more detail manner than the other criteria. Composite types of coverage may also be introduced such as Modified Condition Decision Coverage (MC/DC) which is recommended as a complement to functional tests by the DO-178B standard used in the aircraft industry. The idea behind MC/DC is as follows. For each condition occurring in a program, a test suite is required that ensures that for each atom in the condition there exist two test cases that yield different results when independently toggling the atom under consideration. Such test suites may not always exist. If a MC/DC test suite exists, then there are n + 1 test cases for each condition that consists of n literals. Data-flow testing: Data-flow testing methods explore the events related to the status of variables during the component execution. The key event related to a variable is the assignment of value to the variable.

Classification of MoDriVal tools

Figures 4a and 4b present a mapping of MoDriVal tools on aforementioned categories. Along the Y axis of figure 4a, we distinguish between tools dedicated to sequential code or synchronous models and tools handling asynchrony. Along the X axis, we distinguish between tools supporting functional testing and tools supporting structural testing. The name of the tools are post-fixed with (s), (m) or (c) when the tests they generate or execute are performed respectively at system-level, model-level or code-level.

Figure 4a: First classification TTS performs system-level functional testing of embedded devices (for instance through their network and protocol interfaces). It can be used also to perform code-level functional testing of a software component on a workstation.

AGATHA operates only at model level, on symbolic transition systems communicating asynchronously through message queues.

The other tools presented deal with sequential code (FLUCTUAT, Penjili, OSMOSE) or synchronous concurrent models of sequential code (sALLUSTe, MTC Solver).

Regarding the structural .vs. functional partitioning, let us add a few comments:

• MTC solver is positioned "across the vertical frontier" on the figure above because depending on whether observers are used or not, the tests generated are purely structural or not. When used in a DO178 context for instance, the tests generated to improve model coverage have to be back traceable to some software requirements. In order to do so, these requirements have to be formalized as observers linked to the tested model so that they enforce constraints (i.e. "functional meaning") on the generated I/O sequences.

• The discussion on MTC Solver is also relevant for sALLUSTe.

• AGATHA lies also across the vertical frontier because the tests generated using reachability conditions may be structural or functional, depending on the "flavour" of the reachability predicate.

• FLUCTUAT might have also been positioned near the vertical frontier because some functional properties may be demonstrated by proving (through abstract interpretation) that the range of some variables are within given bounds. For example, equality between two floating-point expressions exp1 and exp2 may be proved by showing that variable epsilon is bounded to [-10 -6 , -6 ] where epsilon is assigned in the code to (exp1 -exp2). However, numerical precision is most of the time handled as a non-functional property. Moreover, current over-approximation issues on loops and conditionals may make functional properties hard to prove with FLUCTUAT. This is why it is eventually positioned on the structural side.

The second classification map below (Figure 4b) is self-explanatory. Most of the tools developed and evaluated in the project are deterministic white box testing tools.

Figure 4b: Second classification

We now discuss the figure 5a below that presents the positioning of the tools with respect to the system and software development stages of the V-model of testing.

AGATHA is positioned at the system or software requirement capture stage. Using UML class and activity diagrams to formalize the captured requirements, or possibly to perform software analysis, AGATHA can import the UML models and generate requirement test cases from these models. Then we positioned MTC Solver along both branches of the V-process. In principle, Model Test Coverage does not apply to implementation and code verification. However when the software code is generated by the qualified version of SCADE (known as KCG), certification credits may be obtained so that the unitary tests performed at model-level need not be replayed at code-level. Thus MTC Solver may also apply (indirectly) to code testing since model coverage may supersede generated-code coverage in these particular circumstances.

sALLUSTe was positioned on the left-hand side of the process for the sake of clarity. However since MTC Solver and sALLUSTe rely on the same constraint solver and may process the same SCADE models, sALLUSTe might be added on the righthand side as well.

FLUCTUAT, OSMOSE and Penjili are dedicated to software verification at the coding stage and are positioned accordingly in figure 5a.

The experiments made with the current version of FLUCTUAT by Dassault Aviation, Hispano Suiza and MBDA showed that the C code programs need very often to be modified to get the best out of the analyzer. Such modifications are unacceptable by DO-178 compliant software verification process and this the reason why for the time being we consider FLUCTUAT as a tool to be used only when it is still possible to choose how to write the code. When FLUCTUAT maturity level increases, this tool will become suitable for unit and integration testing stages as well.

OSMOSE and Penjili are also regarded as tools supporting the coding stage since none of them execute tests.

OSMOSE provides facilities to "check" the binary tests it generates, in the sense that these tests are evaluated through symbolic interpretation of the binary code, as if it was executed by the intended hardware.

time error analysis, stack analysis, code coverage analysis and of course in-circuit debugging or emulation (Greenhills, iSystem, Lauterbach, etc.).

Conclusion

How could the MoDriVal tools fit in the landscape of commercial tools ? This is both a question of functionality and technical maturity.

TTS is a tool whose maturity is currently high enough to allow to integrate it into industrial testbenches. The TTCN-3 version of TTS developed during the MoDriVal project provide functionalities similar to OpenTTCN and TT-Workbench tools. A way for TTS/TTCN-3 to reach the market would be to integrate it as a plug-in to existing integrated test environment in order to support the future conformance testing of AUTOSAR software components. Since TTS/TTCN-3 was developed as an Eclipse plug-in, the integration would be facilitated for Eclipse-based environment.

All other MoDriVal tools presented in this paper are still research prototypes. The integration of these tools as plug-in to Eclipse-based environment is also a possible way to the market. These tools however still need to maturate.

Penjili and FLUCTUAT may be compared to equivalent static analysis tools provided by Klockwork and LDRA environment. No commercial tools mentioned above match the capabilities of MTC Solver and sALLUSTe yet. Similarly commercial products providing binary code reverse engineering capabilities exist, but to our best knowledge coverage-driven test case generation at binary code level is a distinctive feature of OSMOSE.

Figure 2 :

 2 Figure 2: V-Model of software testing The V-model integrates together testing and design activities by showing, how the testing activities on the right-hand side verify the outcome of design activities on the left-hand side. A test plan corresponds to each stage of the software construction. Requirement analysis is the stage where the software engineer thinks about the information obtained during the initial stage of requirement elicitation. Requirement specification documents and design documents are inspected carefully before the coding stage begins. Checklists are the basic tools used for the inspection of requirements.Requirements give guidelines for the subsequent construction stages as well as the criteria to be used for the software acceptance. The acceptance test plan is produced at the requirement elicitation stage. The acceptance test plan helps users testing the system and checking with acceptance criteria whether their requirements are fulfilled. Then the design stage of the software architecture can be divided into the following activities:• Functionality-based architecture design, which decomposes the architecture into

Figure 3 :

 3 Figure 3: Mapping of testing tool categories on the V-model of testing

Figure 5a :

 5a Figure 5a: Mapping of MoDriVal tools on the Vmodel of testing

However, whether static analyzers such as FLUCTUAT, OSMOSE and Penjili may supersede part of the testing activities in the future or not is currently a matter of debate in the working groups preparing revision C of DO-178.

As TTS is devoted to system-level integration and acceptance tests, it is positioned accordingly on the upper right part of the verification branch.

of MoDriVal tool experimentations

Let us give a quick overview of the MoDriVal project case studies that put the tools at work. Case studies were relevant to avionics software, critical control software for nuclear power plants and automotive embedded software.

AGATHA was experimented in two different ways by EDF and Thales Research & Technologies.

EDF aimed at analyzing system requirements through UML modeling and test case generation while Thales R&T attempted to set up a process where software design tests were derived in a semiautomatic way from AGATHA-generated requirement tests.

OSMOSE was evaluated by EDF and Hispano-Suiza. EDF expects OSMOSE to help facing hardware obsolescence and binary porting issues while Hispano-Suiza is concerned with DO-178 mandatory tests of optimized binary codes when source traceability is broken by compiler optimization.

Dassault Aviation, Hispano Suiza and MBDA used FLUCTUAT on many different mathematical algorithms to assess the functional impact of rounding errors, to prove stability, robustness or convergence properties. Understanding the foundational background of the tool and defining a methodology to tune the numerous parameters of the abstract interpreter were unanimously recognized as critical issues.

CS experienced sALLUSTe on automotive embedded software. Dassault Aviation, Hispano Suiza and MBDA are currently assessing sALLUSTe on avionics SCADE models.

Commercial tool landscape

The landscape of commercial test environments has experienced some significant changes recently. There is a major trend towards integrated environment that span over the various categories of test activities presented in Figure 1 at the beginning of the paper. These environment provide numerous tools that allow designers to perform a wholeprogram inter-procedural analysis on C/C++/Java code and to identify complex programming bugs that can result in system crashes, memory corruption, and other serious problems. As examples of such integrated test environment, we have selected the following tools:

• Klocwork, a set of leading static analysis tools to "cure" defects and security vulnerabilities in C/C++/Java code.


F Ougier

F Terrier

EDONA: an Open Integration Platform for Automotive Systems Development Tools

Keywords: Automotive open tool platform, component development, design for safety, model based validation

Launched in autumn 2007, EDONA is a French collaborative effort of automotive manufacturers and suppliers, research laboratories and software vendors. It was built in order to guarantee seamless inter-operation of existing commercial tools and advanced academic technologies necessary to develop automotive software-based systems. This project aims at developing open development environments supporting the full set of future AUTOSAR™ specifications, as well as the forthcoming ISO 26262 standard for safety of electronics components for the automotive industry. The article describes the environment frameworks based on a tool repository and a set of interfaces backed by the Eclipse environment, and how tooled solutions will be built for dependability and hard real time support across the whole V-cycle, namely in the following areas: • System specification and requirement traceability • Functional and temporal validation • Safe design of real-time and deterministic solutions • Integration of MMI component under safety constraints It concludes on discussing the orientation of the exploitation strategy considered for the project results.

Introduction

A vital goal for automakers and parts manufacturers is to control the quality of embedded systems. Indeed, surviving in global markets, but also increasing market share requires the implementation of differentiating innovations. This leads to significantly increase the complexity and interactions of the developed features. Since most of them are based on the implementation of electronic and software technologies, the volume and complexity of this software is undergoing a very significant growth. The quality risk there is either to prevent the maturation of innovations involved (thus no tenders on the market -not increased turnover 'affairs), or to generate perceptible non-quality of the products (thus to generate a poor image -decline in sales).

The growth of technological and economic weight of the automotive electronics as well as its increasing complexity requires, in order to guarantee the cost, quality and timeliness of implementation, a comprehensive approach: from product feature specification to electronics and software design and validation. The challenge for the automotive industry is to control these electronic-board computer architectures, in order to:

offer a dependability at level of the state of the art (with dependability objectives allocation and evidence demonstration in accordance with ISO 26262 standard recommendations); have the flexibility to provide different configurations (the diversity of features depending on the variety of target markets); have an ability to dissociate electronics and software developments and integrate them into multi-stakeholders (manufacturers, suppliers) processes. According to these objectives, the automotive industry has launched two important standardisation actions:

AUTOSAR TM , a standard defining platform architectures, and formats to design, integrate execute and operate software components; ISO 26262, a standard providing automotive risk classes and recommendations regarding all lifecycle activities for safety-related systems comprised of electrical, electronic, and software elements. The challenge is now to provide efficient processes to each actor of the development of automotive embedded software components according to those standards. Moreover, the wide variety of applications and stakeholders involved in the process cycle leads to integrate a large variety of practices and tools within the constraints and orientations of these standards.

To deal with the consequent tool interoperation complexity, the Num@tec Automotive [1] consortium has set up the EDONA platform project in order to provide an open framework from which dedicated development environments can be instantiated or derived for the needs of each development context. Next section will discuss some key elements of the automotive standard context. The project approach and framework platform are then presented, followed by four short focuses on complementary development processes:

Component architecture modeling process Safety critical component design Matlab®/Simulink® model based validation Man Machine Interface design Finally, to conclude, the paper will discuss the perspectives of exploitation of the various projects technologies.

Two standards for automotive software

The AUTOSAR TM and the ISO 26262 standards are two very complementary and structuring standards for the development of automotive embedded software components.

AUTOSAR TM a "business oriented" standard for software component implementation

The AUTOSAR TM consortium has been created to define a standardized way to support component based development of software systems. It focuses on component integration on Electronic Computing Units (ECU), on inter-ECU communications and component reuse or exchangeability. For that purpose, it defines clear interfaces and communications means among components upon a layered execution infrastructure.

Copyright AUTOSARTM [2] In the development process, AUTOSAR TM starts at the deployment stage. This means that it specifies how to describe component interfaces, and which underlying architecture will support communication and execution of the components. This gives strong specifications on the last stage tools in the development chain such as the operating system, the communication network or the deployment and configuration tools. However the rest of the development tools remain totally open. Actually, the AUTOSAR TM consortium sets only broad lines of action and outlines technology that will have to be controlled by 2010. Because the deployment of AUTOSAR TM systems (2009,2015) will gradually give the opportunity to independently develop the hardware and the software, it is mandatory to ensure that it can be supported by the different partners in the chain of specification, design, test and validation with numerous interactions and technical exchanges. For that, the productivity control of the whole chain of development is a major issue to support the competitiveness of all the players in the field. There is a need, in particular to: trace, smoothen and optimize the entire development process; provide flexibility with respect to the wide variety of configurations; have a structure adapted to the different players in the field (manufacturers, equipment suppliers of tier one, two, etc.); ensure validation and dependability of the equipment at the required level.

Copyright AUTOSAR TM [2]
Today the process of developing on-board computers is based on different tools for modeling, production, validation and implementation of functions, software and hardware. These tools and technologies are for the most optimized for automotive and based on heterogeneous formalisms that, moreover, are variable in terms of activities and steps in the process. In the vast majority, the poor interoperability between these tools does not allow users to obtain an integrated development chain ensuring continuity, from the expression of the requirements down to the validation of a system integrating various components. Some internal projects in the transportation domain, however, show that the establishment of a host platform allowing the building of integrated development environments that meet the needs of the various players is a major factor in the control and improvement of productivity, but also the quality and safety of these products. Setting up such a platform for the automotive domain according to AUTOSAR TM orientation is one of the two main objectives of EDONA. The second one is a stronger integration of safety concerns in the development process. One main evolution provided by ISO26262 is the adoption of a customer risk-based approach for the determination of the risks at the vehicle level. This has lead to provide automotive-specific analysis methods to identify the safety integrity level (ASIL) associated with each undesired effects. These ASIL are used for assigning qualitative and quantitative targets to functions to be implemented by E/E automotive systems. The standard provides ASIL-dependent requirements for the whole lifecycle of E/E system (incl. H/w and S/w components).

The

Impact of safety analysis on the development cycle -(figure from [3])

As an ISO standard, the 26262 does not specify formally whether to use given development or validation tools of formalisms. However, the recommendations made for the development of the safety-related systems emphasize the interest to use model based testing techniques and advantages of using generation, configuration and calibration tools to produce the code. Moreover, as for all safety critical systems, it is clear that compliance to this standard requires a tight control of the requirement traceability along the whole development process and will benefit from using deterministic computation models for the highest critical functions and components.

Integration of tools and technologies supporting these formalisms thus becomes the second main objective of EDONA.

EDONA approach

Obtaining integrated development chains open to several leading companies grouped together in a common approach requires to be based on: a standardization (de facto, commercial or normative) of the interfaces and formalisms, interfacing upon these standards the commercial and internal tools, and developing complementary component tools to meet specific needs. It must be accompanied by substantial work on the data structures and their organizations to enable the construction of libraries of reusable components and applications and to facilitate exchanges between groups working on similar projects. The platform should enable the construction of tool chains with easy adaptation and customization through parameters or proprietary extension creation for companies seeking to automate certain types of development (e.g.: engine computers). It must be constructed in the form of tool components, at a fine level of granularity. It must ensure sustainability through the simple ability to change or through the replacement of application modules when technological changes or changes in methodology occur, without jeopardizing previous investments in the applications. EDONA proposes to make possible the implementation of such tool chains through the construction of an open platform for the realization of business dedicated and modular development chains, covering the entire system development cycle and adaptable to the different needs of the actors and business of the automotive industry. In parallel, several projects are underway that will provide bricks for such tools chains either focused on AUTOSAR TM component based development or on integrating the ISO 26262 in development cycle. EDONA approach is to federate, integrate and capitalize all these elementary results in order to combine them into efficient and business dedicated tool chains.

As illustrated by the following figure, it will intensively reuse results from projects implemented in Num@tec Automotive under the System@tic competitive cluster either for automotive specific technologies (such as: MeMVaTEx, Scarlet, HeCoSim, SysPEO, D2OS [1], [START_REF]Modeling Methods for Validation and Traceability of software Requirements)[END_REF], [START_REF]Heterogeneous co-simulation & Hybrid simulation of Systems)[END_REF]), or providing generic technologies partly applicable to the automotive domain (e.g.: Usine Logicielle [6]). It will also benefit from results of projects developed in other competitive clusters (such as O4A from "Automobile Haut de Gamme" cluster [7] or TOPCASED from Aerospace Valley cluster [8]) or in other collaboration frameworks (such as the OpenEmbeDD platform of RNTL French program, the ATESST IST European project or the TIMMO ITEA European project). The EDONA project is located downstream from these various projects, and includes the goal of integrating for the AUTOSAR TM computers the different outcomes of these projects.

EDONA relation with existing projects and initiatives

Approach

The form chosen for the implementation of EDONA is the creation of a reference technology platform and its specialization based on clear specific needs of particular business sectors. Each specialized platform will be built on the three following elements:

an expression of needs and functional definitions driven by an industrial partner particularly interested in the technology, and carried out jointly by different laboratories and industrial partners; a coherent integration supporting and improving existing work processes. Integration is performed from the generic platform extended by different tool modules provided by the laboratories and SMEs (depending on technology maturity regarding the objectives and standard compliance, these tool modules will be available at the launch of the project, or result from the projects mentioned above, or will be extended / enhanced during the EDONA project itself); a full-scale experiment conducted by at least one industrial for each specific platform. The project will be conducted to enable iterative integration and tool chain delivery during its whole duration (3 years). To be compliant to AUTOSAR TM standard, each integrated tool will be associated with its adaptation to the exploitation of AUTOSAR TM architecture and data format. In addition, to allow compliance with ISO 26262 recommendations, a specific focus has been made in order to support model based validation and testing and automatic code generation.

O4A

II T o o l s p e c i f i c a t i o n s S p e c . e v o l u t i o n s

TOPCASED

Action Language Editor (integrated in Papyrus)

Automotive stakes & perpetuation

« OPEES »

Automotive stakes & perpetuation

« OPEES » « OPEES » MARTE (final)

MARTE (final)

ADL

EAST-ADL2 (AUTOSAR™ extension)

Papyrus modeler (UML & EAST ADL)

ADL ADL

EAST-ADL2 (AUTOSAR™ extension)

Papyrus modeler (UML & EAST ADL)

Major technical challenges

The EDONA project is a project for integration of technology platforms based on the studies, projects and technologies that are already completed or underway. We can consider that the majority of technical challenges for the realization of these platforms have been achieved or will be achieved in the context of the various "source" projects on which EDONA is based. Thus, the major challenge is on the integration of different bricks to provide technological environments more effective and better tailored to the needs of different actors. That must be addressed from two inseparable and complementary axes: 1: The constitution of a common basis for both technologies (interfaces, formats, communication services, management of consistency, etc.) and concepts (reference meta-models, organizational elements of development and exchange processes, etc.). The conceptual basis will be built on the standards of the automotive domain: AUTOSAR TM and ISO 26262. The first defines a technical target for the deployment of software components and the second criteria for characterizing functions they provide according to their levels of criticality. The hard point here is to trace the design constraints that arise from these standards in the modeling, validation and production environments, while ensuring maximum independence with the modeling formalisms upstream. This is the role of the integration platform subproject (WP5).

2:

Integration and finalization of technological bricks issued by upstream projects and dedicated to the automotive domain. In particular: introduction of the concept of software component (especially in accordance with its definition given by AUTOSAR TM ) in the initial phases of the deployment (design, verification) and in the validation methodologies (simulation, verification, test). This will be addressed in a comprehensive manner by WP1 -Requirement modeling for AUTOSAR TM components. processing of safety requirements at each step and setting up of involved technology supports (models, compilers, execution infrastructures, etc.). This item, is processed by the WP2 -Critical system development. integration of the various tools and used formalisms (such as, Matlab®, C Language, UML) through interoperation interfaces and bridges ensuring semantic consistency of information and correctness of verification / validation or code production. This will be addressed mainly in WP3 -Functional testing of Matlab® / Simulink® algorithms. reliable design and validation of automotive HMI is a new topic addressed by Num@tec Automotive; the challenge is to ensure flexibility and completeness of the modeling of the HMI, in particular, on the behavioural aspects and to ntegrate it into the development process tools for effective and incremental validation. It is th purpose of the WP4 -HMI design case tool.

EDONA project organisation

Industrial applications

Tooled up processes WP 0 -« Management » -Promotion, dissemination and perpetuation strategy

Requirement modeling for AUTOSAR™ components WP 1

WP 4 WP 5 -« Interoperation and integration platform » -Requirements definition -Interoperability and interchange architecture for automotive development processes and tools

Integration platform

The general principle of the integration platform is to provide access to a common storage space accessible by any tool chain from vertical subprojects.

Global architecture

For that, the first step is to have a common metamodel to define the data exchanged and integrated between the partners in a project for an automotive electronics system. It will be built from the existing elements, namely:

Incoming AUTOSAR TM meta-model (V3) [2],
EAST-ADL 2 meta-model for automotive architecture description, defined from UML and SysML meta-models and already aligned to the AUTOSAR TM meta-model [START_REF]Enhancing the EAST-ADL architecture description language for safety related system design upon AUTOSAR TM )[END_REF], [START_REF] Cuenot | Managing Complexity of Automotive Electronics Using the EAST-ADL[END_REF]. Timing aspects provided by the UML MARTE profile [START_REF]UML profile for Modeling and analyzing Real Time Embedded systems)[END_REF] that will be integrated at various levels into both the second phase versions of AUTOSAR TM meta-model and the next upgrade of EAST-ADL 2 itself. Safety aspects integrating concepts from an UML extension for QoS, Fault Tolerance and Safety Analysis provided by Usine Logicielle [6].

They will be integrated also to both the second phase versions of AUTOSAR TM meta-model and the next upgrade of EAST-ADL 2. Complex object and GUI definition aspects coming from the second phase versions of AUTOSAR TM meta-model, eventually extended for the needs of the project.

Defining a global and common conceptual reference

The technical architecture is based on the Eclipse Equinox platform and on EMF as a model repository. Tool interoperation example for model based testing

Business instantiations of the platform

The EDONA platform is used as a basis to build dedicated tool chains for particular purposes and context usages. Four of them have been defined in the project. This initial set of tool chains will be enriched later by additional focused projects and platform promotion activities.

From requirements to AUTOSAR component architectures

The first vertical sub-project aims to provide a coherent and continuous tool chain for modeling requirements and refining models starting at a high level and until obtaining a detailed architecture description in terms of AUTOSAR TM components ready for deployment. This will be achieved through the integration of a range of existing tools and results of ongoing projects and, in particular, through the industrial transfer of an open source modeler supporting the EAST-ADL2 architecture description language resulting from the project IST ATESST. EAST-ADL2 aims coverage of the needs and viewpoints specific to the automotive trades from modeling requirements to the implementation models. At the implementation level it is based on the AUTOSAR TM meta-model. This standard covers the last steps of the development process. Its entities populate architectures at the Implementation Level and are referenced from higher levels by requirements, variability constructs or traceability

Relations between EAST-ADL and AUTOSAR TM

Technically, the EAST-ADL 2 language is constructed in the form of a dedicated UML profile based on the AUTOSAR TM meta-model [START_REF] Cuenot | Managing Complexity of Automotive Electronics Using the EAST-ADL[END_REF]. The modeler itself was developed by the CEA LIST on the basis of the open source UML 2 modeler, Papyrus [START_REF]UML 2 modeling tool[END_REF]. EDONA will ensure tight interoperation between the EAST-ADL 2 modeler and AUTOSAR TM authoring tool, in order to be able to generate an executable application with the platform. The management of refining models of requirements and traceability will be achieved by integration of RNTL MemVaTEx project results [START_REF] Albinet | Model-based methodology for requirements traceability in embedded systems, 3rd ECMDA workshop on traceability[END_REF]. MemVaTEx develops a requirement modeling and traceability methodology that will be aligned for using EAST-ADL 2. The TRAMway tool under development in the TOPCASED project will equip this traceability [8]. This is extended by the integration of complementary elements: analyzing model schedulability (this item will benefit from the results related to the standardization of MARTE and results of the ITEA project TIMMO) [START_REF] Espinoza | Towards a UML-Based Modeling Standard for Schedulability Analysis of Real-Time Systems[END_REF]; extending the architecture description language to integrate real-time deterministic specifications according to the OASIS technology used in WP2 for the development of safety critical systems. formalisation of heterogeneous execution model for simulation or formal analysis on basis of the UML profile for modeling computation and communication models [6], [START_REF]Tackling heterogeneity for embedded system development)[END_REF], [START_REF] Hardebolle | Execution Framework for Models of Computation[END_REF]. studying the ability to generate tests from EAST -ADL2 architecture models having heterogeneous component modeling formalisms; this is based on results from Usine Logicielle [6] (test generation from UML models), WP3 (test generation from Matlab® models) and HeCoSim (Heterogeneous component simulation) [START_REF]Heterogeneous co-simulation & Hybrid simulation of Systems)[END_REF].

Safety critical system design

The purpose of WP2 is to ensure the safe implementation of a specification of critical functions.

Implementation will be based on the OASIS tool chain developed by the CEA LIST [START_REF] Chabrol | Deterministic Distributed Safety-Critical Real-Time Systems within the Oasis Approach[END_REF] providing a time deterministic programming model and language, an optimized compiler and safe execution with its kernel. This approach is complemented according to several points of view:

Because the specifications provided for the applications are already established in Matlab® / Simulink®, bridges between specification expressed in Matlab® / Simulink® and the OASIS programming language will be developed by Monditech.

The Matlab® / Simulink® implementation model is based on a model of the computing environment: it is used at design time for simulating the execution of real-time applications, in order to analyze their dynamics. Threfore, the current environmental models, as provided by Sherpa Engineering, must be upgraded in order to provide AUTOSAR TM compliant computing and I/0 models. At the machine implementation level, it remains necessary to check the resolution and accuracy of the digital processing technology compared to the original specifications. This last point can be analyzed using CEA LIST's approach implemented in the Fluctuat tool [START_REF] Putot | Static Analysis of the Accuracy in Control Systems: Principles and Experiments[END_REF]. It allows assessment of resolution/accuracy constraints propagated in a program, namely, in a format like Matlab® / Simulink® after its translation into C. These resolution constraints typically come from accuracy constraints identified in the functional design.

Early validation

The WP3 sub-project aims to integrate a set of tools to achieve validation of Matlab® / Simulink® models. They will establish test cases of both discrete and continuous models developed and implemented on AUTOSAR TM calculators. This work is totally complementary to those of WP2 by focusing on functional and structural validation instead of on the verification of the accuracy of digital processing. The technical approach adopted has been developed by the CEA LIST and implemented in the AGATHA tool [START_REF] Gaston | Symbolic execution techniques for test purpose definition[END_REF]. It consists of using formal techniques (such as symbolic execution) to build automated simulation scenarios (or concrete tests) and representative behaviors of the system, and to demonstrate certain properties on the models tested. Completeness of the simulation can be reached, because the "partitioning" directed by symbolic execution on all possible simulations avoids the combinatorial explosion which might have occurred when using the methods of traditional numerical simulation [START_REF] Labbé | Slicing Communicating Automata Specifications for Efficient Model Reduction[END_REF]. The proposed work is the integration of symbolic simulation on the fully discrete or hybrid model to deal with realistic models as built by the automotive suppliers. It will reuse some results of the SysPEO Eureka project, in particular as regards the treatment of hybrid systems represented in Matlab® / Simulink®.

AUTOSAR Human Machine Interface design

The WP4 sub-project is to design a tool chain for graphical HMI software development. The goal is to improve, standardize and make inter-operable elements of the different tools to create automobile GUI, all within the constraints of the strong adherence to AUTOSAR TM standards. Particular focus will be kept on the standardization work ongoing in AUTOSAR TM regarding data formats (XML), HMI component APIs and architectures. Issues related to the internationalization of HMI will be managed: here we will seek to identify the attributes / information to be translated (meta-model) in order to use these descriptions through automated translations using EDONA platform tools. The tool chain will spread over two axes:

Prototyping of innovative applications for prototype cars in the area of intelligent transport systems. These vehicles are equipped with many sensors for analysis. In this context, the execution engine of Intempora ( RT Maps® [23] also used for HMI experiment in the IHS1O project) will be used and integrated to EDONA platform.

The production of certified applications for vehicle sales, and therefore in compliance with constraints in terms of dependability and certification. In particular, the support of both AUTOSAR TM and the ISO 26262 standards must be taken into account. In this context, the used execution engine will be the SCADE Suite® tools of Esterel Technologies. In particular, the SCADE Display® tool [START_REF](Scade Suite and Scade Display development environments[END_REF] will be first certified to the existing IEC 61508 standard, so that the transition to the ISO 26262 certification can be done easily when that standard exists.

Exploitation strategy

The Num@tec Automotive project initiated since September 2003, is strictly focused on software development (tools and applications) which will provide the automobile industry in the short-term (1-3 years) with technological innovations, and in the mid term (2 --5 years) with the establishment of companies amplifying a respected position, proportional to the weight of the automobile industry in the economy. The objective of Num@tec Automotive is to create a European platform for innovation, research and development for the automotive industry in the field of software and complex systems. The realization of this platform is organized into two sets of activities:

Tools for the design of electronic systems ensuring the realization of software technology bricks for the automotive domain; Platforms for integrating these bricks and innovative results into the development of prototypes. The EDONA project is the first instance of the second set, "Integration platforms".

Num@tec Automotive organization

Its launch is strongly synchronized with the schedule of the two major standards for the domain: it can benefit from all the results of AUTOSAR TM phase 1, can contribute to some evolutions done in phase 2 and will still be active and ready to integrate the last results obtained at the end of the second phase. In parallel, works on ISO 26262 are sufficiently advanced to provide some guidelines and main orientations on how to deal with safety aspects regarding this standard.

EDONA synchronization with activities on standards

Value creation in EDONA is based on technology transfer in association with three key stakeholder types: industry users, technology and service providers and academics providing innovations. The EDONA consortium is well balanced to represent all these stakeholders, with almost all the key French players of the field. Regarding the exploitation rules fixed by AUTOSAR TM consortium, it is considered that all partners willing to exploit the results will become AUTOSAR TM members with the support of EDONA partners already being core and premium members.

  l s p e c i f i c a t i o n s S p e c . e v o l u t i o n s

  In addition to these AUTOSAR TM dedicated tools, EDONA platform provides a second set of more generic tools and tool interoperation bridges, all integrated to Eclipse and based on EMF repository usage. They are issued namely from Usine Logicielle, OpenEmbeDD or TOPCASED projects and provide, for instance:EAST-ADL2, an Open Source meta-model defined as an UML 2 profile[START_REF]Enhancing the EAST-ADL architecture description language for safety related system design upon AUTOSAR TM )[END_REF]; Papyrus, an Open Source UML editor with extensions for SysML, MARTE and EAST-ADL 2 profiles[START_REF]UML 2 modeling tool[END_REF]; ATL, an Open Source language and engine, from INRIA for model to model transformation [14]; Acceleo®, an Open Source plugin for model to text transformation based on templates and provided by Obeo []; UML to SCADE Suite® bridge developped by Esterel Technologies in Usine Logicielle project and integrated to Eclipse and Papyrus [6]. UML to Agatha bridge developped by CEA LIST in Usine Logicielle for automatic test generation from UML specification and instantiation at the TTCN-3 format [6]. The following figures illustrate with some of the integrated tools two examples of interoperation architecture. On the right part of next figure, an example is shown of tool interoperation for importing an UML system architecture model into the SCADE Suite® tool. In addition, on the left side, the figure of Acceleo® for C Misra code generation. Examples of tool interoperation around Eclipse platform and EMF repository The next figure illustrates interoperation for test generation. On the right part, it focuses on test generation from Matlab® models: 1. Models are created with the Matlab® editor under the constraint of making the model analyzable through formal execution; 2. They are imported in Eclipse-EMF and translated into an intermediate model based on extended finite state machines (EFSM); 3. This intermediate model is exploited by the Agatha test generator; 4. Results are translated into the adequate output format, e.g.: in the TTCN-3 format as done in the Usine Logicielle project and proposed for AUTOSAR TM implementation testing [6].

  behavioral semantics of EAST-ADL2 has been adapted to match the AUTOSAR behavioral concepts. -OperationalArchitecture -OS -COM -MW

  At least 32 technologies (components tools) will be integrated, transferred or developed in a context of strong industrial exploitation, with: 10 transfer of technology from laboratories; 15 innovations from technology providers; 3 innovations from laboratories; 4 common innovations from a joined work of the whole consortium. 13 of these technologies are foreseen to be exploited through open source or EDONA common source strategy creating a strong link between the project consortium and existing or emerging open source communities in the domain of embedded systems development, locally like the OPEES initiative or more widely with the Eclipse community. This is the challenge to be addressed in the next 3 years.

Critical system development WP 2 Functional testing of Matlab/Simulink® algorithms WP 3 HMI software design workbench

Acknowledgements

The authors acknowledge the contribution of all Edona project partners and especially from the subproject leaders and project steering committee members: L. Tossa (PSA -WP5), B. Sanchez (Continental -WP1), K. Maaziz (Delphi -WP2), P. Le Corre (Johnson Control -WP3), H. Dufau (Visteon -WP4), M. Frouin (Geensys -WP5).

Edona is partially funded by: "Direction générale des Entreprises" from the French Ministry of Industry, "Region Ile de France", "Conseil général des Yvelines", "Conseil général de l'Essonne", "Conseil général des Hauts-de-Seine", "Conseil général du Val d'Oise".


C Ferdinand

R Heckmann

T Le Sergent

D Lopes

B Martin

X Fornari

F Martin

Combining a High-Level Design Tool for Safety-Critical Systems with a Tool for WCET Analysis on Executables

Keywords: Model-based code generation, timing analysis, stack-usage analysis

Synthesizing code from model-based software specifications using automatic code generators such as the SCADE Suite allows design verification at early project stages and helps to avoid coding errors, thus reducing the need for low-level testing. Non-functional properties of the implementation such as execution time and memory consumption require specific analysis. Static program analysis tools like AbsInt's StackAnalyzer and timing analyzer aiT complete ideally the model-based design process with the verification of these properties. These tools can also give SCADE users a direct feedback on the effects of their design decisions on resource usage, allowing them to select more efficient designs and implementation methods. The SCADE tool, StackAnalyzer and aiT can be integrated in a way that the analysis results for code generated by the SCADE tool are conveniently accessible from within the SCADE development environment. We present the tools and their integration, preliminary results, and plans for integration with other tools for timing analysis.

Introduction

Software developers in the avionics sector face some specific challenges: Many software systems are safety-critical and, thus, must achieve high quality objectives. Model-based design aims at satisfying the high safety requirements in combination with good development productivity by starting with a software specification. The implementation process is not necessarily automatic. It is therefore still possible to introduce software defects through misinterpretation of design and specification documents or through human error during the manual coding process. Automatic code generators such as the one provided by SCADE are increasingly used to generate the implementation from the specification. By creating C code directly from the model-based specification, these code generators avoid the typical translation problems that occur in the implementation stage. Moreover, as the SCADE Suite code generator, SCADE KCG, is qual-ified as a development tool w.r.t. DO-178B level A, unit testing on the generated code can be avoided.

Many design and implementation errors are avoided by synthesizing code from specifications. However, non-functional properties such as absence of memory overflow and timer overruns are still an issue. To verify such properties of the implementation, unit tests and runtime measurements are currently widely used in the industry. These approaches have some limitations:

• To acquire a high level of confidence to have detected the worst-case (or close to worst-case) behaviors, a huge (often prohibitive) number of test cases needs to be considered.

• Testing to detect worst-case memory and /or timing behavior can be complex and timeconsuming. The results are often only available late in the development cycle and cannot be used to optimize the model during the development.

Recent advances in the area of static program analysis based on abstract interpretation led to the development of tools to automatically detect worstcase execution times (WCET) and worst-case stack usage like AbsInt's timing analyzer aiT and Stack-Analyzer (see [START_REF] Wilhelm | The worst-case execution time problem -overview of methods and survey of tools[END_REF] for a survey of timing analysis tools). Such tools that determine safe and precise bounds on resource usage can be very helpful for SCADE users.

In the context of safety-critical hard real-time applications, aiT and StackAnalyzer are used as verification tools, i.e., they are used to demonstrate and prove that pieces of code are guaranteed to always execute within limited time intervals and resource bounds.

In this paper, we propose to complement modelbased design processes with static program analysis tools. We argue that to develop hard real-time systems, model-driven development coupled with detailed analysis of the implemented software is much better suited than traditional development methods that rely on programming C code.

The users of SCADE usually work on a much more abstract level than the producers of manual code.

Our tight integration enables the SCADE user to conveniently access static analysis results from within the SCADE development environment. This gives SCADE users a direct feedback on the effects of their design decisions on the resource usage, allowing them to select more efficient designs and implementation methods.

In the following, we present the tools, the experimental integration, preliminary results and plans for further tool integration.

SCADE Language and Toolset

SCADE is a model-based design tool dedicated to the development of safety-critical embedded systems that require certification, for example subject to DO-178B, IEC 61508, EN 50128, or ISO 26262 standards. SCADE modeling capabilities cover the design, verification, and optimization of complex algorithms, control intensive applications, and graphic interfaces. Furthermore, the SCADE automatic code generator has been qualified to produce a portion of the evidence mandated by certification authorities, supporting a safety-critical process in a cost-effective manner.

The SCADE language provides a graphical and textual notation to express data-flow and controlflow. The data-flow is defined in a declarative way through equations and the control flow is expressed with control structures that go from simple "ifthen-else" like constructs to complex hierarchical and parallel state machines called Safe State Machines (SSM). In SCADE 6 both data-flow and SSM formalisms can be mixed and nested one into the other without limitation (see section 5), with both formalisms sharing the same fundamental interpretation and characteristics, namely:

• Explicit data typing,

• Explicit management of discrete time,

• Single assignment in data-flow,

• Concurrency solved through synchronous behavior and data and control dependencies, • Deterministic execution. The predefined SCADE operator FBY is a de-lay of n ticks, n being its first parameter; at initialization the output value is given by the second parameter, here 0. The operator defined in Figure 1 is a simple counter modulo the value modulo provided as input. The counter value is incremented at each tick in which input incr is true. Output rippleClock is true when the counter is reset by the modulo operator. An operator can be instantiated several times as in Figure 2. The instance number appears at the top right corner of the instance. Instance 1 of modCount increments the output at each tick (input incr is always true). Each time it is reset, it causes an increment in the second instance of modCount because the output rippleClock of the first instance is connected to the input incr of the second. Same for the 3 rd instance that counts only when the 2 nd instance reaches 60. The output of the operator countTime1 is a vector of 3 integers that represents the time in [seconds, minutes, hours] if it is called at every second. SCADE 6 introduces loops via iterator constructs as a means to perform computations on arrays. Iterators come in two families:

• Map iterators, which apply a SCADE 6 operator to a bunch of arrays of identical size as input, and produce a bunch of arrays of the same size as output. The SCADE 6 operator is applied to each array component independently. A map iterator can be used to compute the sum of two vectors for instance (c

[i] = a[i] + b[i]
). • Fold iterators, which apply a SCADE 6 operator to an array and an accumulator, iterating from the first array cell to the last one. Each computation is applied to the value of the current cell and the previous accumulator value, leading to a new accumulator value. The final result is the last accumulator value. A fold iterator can be used to sum up all the cell values of a given array (b = a

[0] + a[1] + • • • + a[n -1]).
Both families of iterators have variants that use a stop condition. As soon as the condition is false, the iteration stops. In all cases, the generated code is guaranteed to generate bounded loops that have statically determined iteration bounds. An additional iterator, mapfold, is a combination of map and fold. It can be used to implement the functionality of countTime1 in a more concise way (see Figure 3). The mapfold iterator, as all iterators, applies to an operator (here modCount), and is used with an iteration number of 3 in this case, as we want to instantiate modCount 3 times.

The first input of an operator under a mapfold is the accumulator input, while the first output is the accumulator output. With SCADE constant time_mod_vector defined as [60, 60, 24], the behavior of operator countTime2 is the same as the one from countTime1.

From a SCADE design, the SCADE code generator generates a set of C functions, forming a call graph from a root function that executes one step of computation. Another set of functions is also generated for the initialization of the memory that is the context on which the step function is applied.

To develop a complete embedded application, these functions (reset and cycle) must be called from a main function that also integrates calls to drivers, and interacts with the underlying Operating System. This code generated by SCADE is in general extended by hand-written user integration code. Then all that code must be compiled and linked to get an executable that can then be downloaded on the target.

The code generated by KCG from operator countTime2 is given below. 1 The reset and cycle functions call respectively the reset and cycle functions generated from operator modCount within a loop that implements the mapfold iterator.

(i = 0; i < 3; i++) { modCount(_L3, time_mod_vector[i], &outC->Context_modCount[i]); outC->s_m_h[i] = outC->Context_modCount[i].count; tmp=outC->Context_modCount[i].rippleClock; _L3=tmp; } }
SCADE KCG has several optimization options. One of the most interesting is the ability to inline the equations from any operators as first step of the compilation. This allows inter-operator optimizations. Generated code from countTime2 with modCount inlined is shown below.

(i = 0; i < 3; i++) { if (outC->init_1[i]) { last_count_1 = 0; } else { last_count_1 = outC->count_1[i]; } if (_L3) { raw_count_1 = 1+last_count_1; } else { raw_count_1 = last_count_1; } outC->count_1[i] = raw_count_1 % time_mod_vector[i]; tmp = raw_count_1 != outC->count_1[i]; outC->s_m_h[i] = outC->count_1[i]; outC->init_1[i] = kcg_false; _L3 = tmp; } }
In order to generate code that can be qualified against stringent rules such as the one from DO178B, KCG must ensure a high traceability between the model and the generated code. This feature directly benefits the SCADE-aiT coupling.

StackAnalyzer and aiT

aiT is AbsInt's timing analyzer, which can find upper bounds for the worst-case execution times (WCETs) of sequential tasks. StackAnalyzer can find upper bounds for the stack usage in an application. For a precise computation of WCET and stack usage, aiT and StackAnalyzer operate on the executable. Both tools exist in different versions, depending on the target architecture. The latest versions of aiT and StackAnalyzer share a GUI that offers ways to specify the memory architecture of the target, the location of source files, the name of the executable, the name of a separate parameter file called AIS file, the name of the report files to be written, etc., and the start point of the analysis (a routine name or an address). All this information can be stored in a project file. The AIS file may contain the clock rate of the target processor, upper bounds for the iteration numbers of loops, possible targets of computed calls, etc. The analyses of aiT/StackAnalyzer are mainly based on the executable. If available, aiT/StackAnalyzer can also read the source files for further information. The association between addresses in the executable and positions in the source files is obtained from the debug information in the executable. aiT determines the WCET of a given task in several phases [START_REF] Ferdinand | Reliable and precise WCET determination for a real-life processor[END_REF] (see Figure 4). In the first step a decoder reads the executable and reconstructs the control flow [START_REF] Theiling | Extracting Safe and Precise Control Flow from Binaries[END_REF]. Then, value analysis determines lower and upper bounds for the values in the processor registers for every program point and execution context, which lead to bounds for the addresses of memory accesses (important for cache analysis and if memory areas with different access times exist). Value analysis can also determine that certain conditions always evaluate to true or always evaluate to false. As consequence, certain paths controlled by such conditions are never executed. Thus value analysis can detect and mark some unreachable code.

WCET analysis requires that upper bounds for the iteration numbers of all loops be known. aiT tries to determine the number of loop iterations by loop bound analysis [START_REF] Ferdinand | New developments in WCET analysis[END_REF], but succeeds in doing so for simple loops only. Bounds for the remaining loops must be provided as specifications in the AIS file or annotations in the C source.

If the target processor has caches, an optional cache analysis follows, which classifies the accesses to main memory into hits, misses, or accesses of unknown nature. Pipeline analysis models the pipeline behavior to determine execution times for sequential flows (basic blocks) of instructions as done in [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 by cache analysis. The result is an execution time for each basic block in each distinguished execution context. Using this information, path analysis determines a safe estimate of the WCET. The program's control flow is modeled by an integer linear program [START_REF] Yau-Tsun | Performance Analysis of Embedded Software Using Implicit Path Enumeration[END_REF][START_REF] Theiling | Combining abstract interpretation and ILP for microarchitecture modelling and program path analysis[END_REF] so that the solution to the objective function is the predicted worst-case execution time for the input program. 1. aiT can produce a graphical output showing the call graph of the analyzed part of the application, consisting of the routines and their calling relationships (see Figure 5). The routine boxes can be opened to show their control-flow graphs with WCET results or stack levels for basic blocks. Technically, aiT writes a description of these graphs in a GDL file, which can be visualized by AbsInt's graph browser aiSee. 2. aiT can write a text report meant to be human readable, and a more formal XML report. These reports contain detailed results for all analyzed routines in all calling contexts, including specific results for the first few iterations of loops vs. a result for the remaining iterations. The XML report file is used in the SCADE-aiT integration. For the first scenario, a simple integration code will be automatically generated by the SCADE/aiT integration in order to perform WCET/stack analysis directly from the SCADE IDE without the need for manually writing C code. For the second scenario, aiT and StackAnalyzer are used directly on the final application. Since feedback of the computed WCET information to the SCADE model should be provided when only parts of the application come from a SCADE design, we propose to use the SCADE/aiT integration also in this case, but without automatically generated integration code, using the final executable instead.

SCADE-aiT-Integration

Analyzability of the SCADE-generated code

Thanks to the good properties of the SCADE language, the code generated by SCADE KCG is very regular by nature and poses no special challenges for the analysis. Stack analysis does not cause any difficulties, as there is no recursion in SCADE generated code, so the stack size is always bounded and statically computable.

The WCET analysis by aiT requires that upper bounds for the iteration numbers of all loops are known. This is the case for all loops generated by SCADE KCG. The bounds are communicated to the aiT tool via AIS specifications (referring to a source code line), e.g., loop file 'name' line number max bound by default;

Workflow

The global workflow for the coupling is pictured in Figure 6. • This code is compiled and linked with user integration code to get an executable.

• aiT performs the WCET analysis on the executable and produces results for the routines in the executable, which correspond to C functions.

The traceability information that is also produced from the SCADE Code Generator provides the detailed relation from SCADE operators to generated C functions. This information is used for feeding back WCET results to the SCADE model.

The following issues are detailed in the next sections:

• Integration code generation

• Linking the information between the tools

• Reporting the information in the SCADE IDE

Integration code generation

As expressed in section 4.1, there are two different possibilities for the integration code:

1. A simple integration code that is automatically generated;

2. User code defined outside the SCADE environment.

Case 2 requires no special handling. aiT is used on the final executable.

In Case 1, additional C-files are generated from SCADE tools. This is implemented by the "wrapper" mechanism of SCADE tools, which is a means to extend the code generation action with other actions, in particular the generation of additional files like "capsule code" that defines a C main() function that calls the SCADE generated code.

As shown in section 2, SCADE KCG generates two functions per operator Op:

• Op_reset() that must be called once, before any cycle Op() is executed;

• Op() that performs one execution of the operator.

Usual application code looks like this: This is a non-ending loop that clearly has no finite WCET and can thus not be analyzed by aiT. Therefore, we generate an alternative code pattern for analysis with aiT. The minimal main code would look like: main() { // declarations Op_reset(); Op(); } But Op_reset() sets Boolean variables that are later on tested in Op() to distinguish between the first execution of the operator and any subsequent executions, then reset to false in Op().

main() { //
With the main code proposed above only the "true" part of the conditionals is used in the first execution of Op(), while later executions of Op() in the real application may also use the "false" part. Thus, this simple code can lead to wrong WCET results because aiT recognizes and uses data dependencies between the functions called. Calling Op() a second time in the "main" wrapper does not solve the problem because in deeper levels of the code, the first execution of an operator with memory can be delayed to several steps from the beginning.

To keep the independence between the Op_reset() and Op() functions and the volatile aspect of input and output contexts and to determine an overall WCET valid for all executions, it is possible to create an analyze function that takes two pointers to contexts, one for the Op_reset() function and the other for the Op() function.

analyze(CtxInType * initInCtx, CtxInType * cycleInCtx, CtxOutType * initOutCtx, CtxOutType * cycleOutCtx) { // declarations Op_reset (initInCtx, initOutCtx); Op (cycleInCtx, cycleOutCtx); } Using these contexts it is possible to distinguish between invariant data set in Op_reset() and used in all instances of Op(), and volatile data set in Op_reset(), but modified in Op() and thus used only in the first instance or first few instances of

Op().

A main function calling the analyze() function is also generated. Finally a complete makefile based on a makefile template provided by the user to set all cross compiler and linker paths and options is generated.

Linking the information between the tools

The results computed by aiT should be mapped back into the SCADE model so that SCADE users can see the results as additional information at the appropriate SCADE operators at the level of the model, without the need to look at the generated C code.

In order to show the SCADE-aiT coupling on a model with more than two operators, the example used hereafter is a car Cruise Control demo example designed with SCADE.

As detailed in previous sections, each SCADE operator is implemented as two C functions, one for the initialization of the operator and one for its normal cyclic execution. Depending on the compiler used or the options given to the compiler, the C function names may not be the same as the SCADE operator names; some compilers for instance put an underscore "_" before the name and /or shorten the identifier. This did not happen in the example presented in Figure 7; if it happens, an association between C names and assembly names must be maintained. This is done via a mapping file generated from KCG. In the example of Figure 7, operator CruiseSpeedMgt e.g., is mapped to C functions CruiseSpeedMgt_CruiseControl and CruiseSpeedMgt_reset_CruiseControl.

The XML report file produced by aiT contains WCET estimations for assembly routines. The mapping from assembly routine names to times is realized in an indirect way: the XML output file assigns internal identifiers to the routine names; in Figure 7 these are tqc for CruiseSpeedMgt_reset_CruiseControl and amc for CruiseSpeedMgt_CruiseControl. aiT's Figure 7: Linking assembly code to SCADE operators through C code WCET estimates for these routines can then be found via these routine identifiers (208 cycles for tqc and 661 cycles for amc). As shown in Figure 7, all the needed information is there to allow a direct feedback from the analysis made on the executable by aiT to the user design in the SCADE IDE.

Sessions and difference reports

Whatever is the chosen production method for the binary (with auto-generated main and makefile, or using "classical" means), it is interesting to be able to report the effect of changes in the SCADE design and /or in the KCG options. For this, users should be able to handle data obtained from several differ-ent launches of aiT from the SCADE IDE. For this reason, we have introduced the concept of sessions. A session is a set of data obtained from one aiT launch. It contains: • open a diff report by selecting two session items.

• SCADE KCG

Max Space:

The maximum stack usage of the function without parent stack usage.

CMax Space: The maximum stack usage of the function cumulated with parent stack usage.

The representation allows sorting each column. The report can be customized through an option mechanism offering the possibility to hide some columns (this has been done for the report shown in Figure 8).

Each operator definition can be located in the SCADE model by clicking on the "Show in model" icon. A detailed report of a specific SCADE operator can be opened by clicking on the corresponding link in the session report. This detailed report displays the information given by the session report and shows the WCET contribution of each child. The diff report (Figure 9) is structured in the same way as the session report, but for each data, the report displays the values for both sessions, and the (absolute and relative) difference between them.

The diff report can be customized in the same way as the session report.

The diff report shows precisely, at model level, the effect of the options set for SCADE KCG or the cross compiler. The example from Figure 9 shows the effect of selecting a higher optimization level in KCG, and inlining two more operators. Improvement is clear for all operators but three whose WCET slightly increased.

Evaluation on an industrial model

The technologies presented in this paper have been evaluated on real-size applications. We give here metrics on a Fuel Management Controller for a civil aircraft (more precise information cannot be disclosed). As a safety-critical application, the code must be certified against DO178B level A; it is a typical application for SCADE design, code being generated by SCADE KCG.

The aiT performed the WCET analysis in 15 seconds, the result being a WCET of 270,000 cycles. With a 40 MHz processor, this gives a WCET of 6.75 ms.

Planned Extensions

As described in section 2, SCADE 6 unifies dataflow and hierarchical state machines paradigms. For details on the semantics of such a unification, see [START_REF] Colac ¸o | A conservative extension of synchronous data-flow with state machines[END_REF][START_REF] Franc | SCADE 6 -A model based solution for safety critical software development[END_REF]. Figure 10 Combined with model-based design and automatic code generation, the potential of static analysis tools is increased greatly: More strict specification and development guidelines enforced by tools like SCADE allow for a high precision of the analyzer's estimates. The resulting combination allows for the development of more secure and better-performing systems while decreasing time-to-market through enhancing development productivity.

For the developer, the immediate and detailed feedback provided by mapping back aiT's results into the SCADE IDE helps to find the critical areas of the project where most of the resources are spent. The concept of diff reports also helps to decide between alternatives to solve a given problem. Using model-based design, different modeling techniques can lead to strongly varying code. Here, the infor-mation provided by aiT can help to prototype and develop software more rapidly.

Figure 1 :

 1 Figure 1: SCADE operator modCount

Figure 2 :

 2 Figure 2: SCADE operator countTime1

Figure 3 :

 3 Figure 3: SCADE operator countTime2

  void countTime2_reset(outC_countTime2 * outC){ kcg_int i; for (i = 0; i < 3; i++) { modCount_reset(&outC->Context_modCount[i]); } } void countTime2(outC_countTime2 * outC) { kcg_bool tmp; kcg_int i; / * P1::countTime2::_L3 * / kcg_bool _L3; _L3 = kcg_true; for

Figure 4 :

 4 Figure 4: Phases of WCET computation

Figure 5 :

 5 Figure 5: Phases of WCET computation

4. 1

 1 Use scenariosaiT and StackAnalyzer operate on the executable for a precise computation of WCET and stack usage. The coupling between SCADE and aiT/Stack-Analyzer should support the use of the WCET/stack computation in the following two scenarios: 1. at the design phase of the SCADE model, and, 2. together with the user-defined integration code.

Figure 6 :

 6 Figure 6: SCADE-aiT workflow

  options, • aiT options, • WCET data attached to nominal items from the SCADE call graph. Sessions allow the comparison of WCET results resulting from different runs with different SCADE modeling, KCG options, cross-compiler options, and aiT options. Sessions can be selected individually from a panel created in the SCADE IDE. From the created sessions, the following actions are possible:• open a session report window (described below), by double-clicking on a session;

Figure 8 :

 8 Figure 8: WCET analysis reportThe session report window (Figure8) gives an overview of aiT results corresponding to SCADE operators to be able to quickly locate bottleneck operators. The SCADE operators are listed in two tables, the first one for cycle functions and the other one

Figure 9 :

 9 Figure 9: Session diff report

  gives an example. This model is detailed in the SCADE Language tutorial[START_REF]SCADE language tutorial[END_REF]. It is the chronometer part of a standard digital watch model; the Chrono automaton that uses the modCount operator runs in parallel with the Display automaton.The code generated from SCADE KCG for such a model consists in nested C switches, basically with one case per automata state. C functions are generated only for non-inlined operators. For a model with a hierarchy of several levels of macro-states and dozens or even hundreds of states, aiT computes the WCET for the whole operator. In practice the worse case corresponds to one state for each of the parallel automata. If the WCET value must be improved, one needs to know which automaton's states must be redesigned or split. Generating an aiT parameterization file from the SCADE model, and completing the XML files for the linking operation should allow us to reach this goal.

Figure 10 :

 10 Figure 10: SCADE Unified Modeling Style

  SCADE model comprises about 80 operators, and the depth of instances reaches 9. The top-level operator has more than 20 inputs, several being arrays of 30 elements, and 9 outputs that are also arrays and one structure of arrays. The model contains about 50 iterators, i.e., 50 loops in the generated C code, some being nested loops.

SCADE KCG has been used with different options, in order to examine their influence on the WCET of the application via the diff feature of the SCADE-aiT coupling. If the highest KCG optimization level (level 3) is selected, and all operators are inlined except for the main 20 top-level operators, 6500 lines of C code are generated. The executable was built with the Wind River Compiler, with standard optimization level, for target PowerPC 555.

The formatting has been changed to let the code fit better to the given column width.

ERTS 2008 -January 29-31, February 1, 2008 -Toulouse

Acknowledgement

The authors acknowledge Jean-Louis Colac ¸o, one of the main designers of the SCADE 6 language, who made the first experiments with WCET analysis on code generated from SCADE KCG.

Collaboration between AbsInt GmbH and Esterel

Technologies has been supported by the FP6 STREP project INTEREST (INTEgrating euRopean Embedded Systems Tools).