Amico Settefrati

Pascal De Micheli

Ludovic Maire

Benjamin Scholtes

Nathalie Bozzolo

Charbel Moussa

Etienne Perchat

Marc Bernacki
email: marc.bernacki@mines-paristech.fr

Maire Ludovic

Prediction of the grain size evolution during thermal treatments at the mesoscopic scale: a numerical framework and industrial examples

Keywords: Mesoscale modeling, Level Set numerical method, Finite element modeling, Grain growth, Smith-Zener pinning

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Mechanical and functional properties of metallic materials are strongly related to their microstructures, which are themselves inherited from thermal and mechanical processing. A precise control of the grain size evolution during these thermomechanical and thermal treatments is one of the key factors for reaching the required final in-use material properties, particularly for the aerospace and nuclear industries. An accurate prediction of the grain size is thus of prime importance. The goal is to correctly describe the main physical mechanisms occurring in metals i.e. grain boundary (GB) migration, work-hardening, recovery, nucleation and grain growth related to dynamic, static or metadynamic recrystallization.

Macroscopic and homogenized metallurgical models are widely used, mainly due to their low computational cost [START_REF] Bernard | A two-site mean field model of discontinuous dynamic recrystallization[END_REF][START_REF] Mukherjee | Modelling of microstructure and flow stress evolution during hot forging[END_REF]. If this mean field framework is quite convenient, it can be synonymous for a given material of a large amount of experiments with advanced laboratory devices. Moreover, the homogenization of the microstructure does not permit to capture some very local phenomena. In order to overcome these issues, lower-scale models (called full field models) have been developed over the last decades with the aim to simulate explicitly the microstructural evolution [START_REF] Rollett | A hybrid model for mesoscopic simulation of recrystallization[END_REF][START_REF] Piękoś | Generalized Vertex Model -Study of Recrystallization in Copper[END_REF][START_REF] Chen | Phase-field models for microstructure evolution[END_REF]. The idea behind these "mesoscale" simulations is that the morphology and the topology of the GB network play a non-negligible role in the evolution of the microstructure. In these approaches, simulations are performed on Representative Volume Elements (RVEs) where the microstructural features are explicitly represented. Boundary conditions applied to the RVE are representative of what suffered a material point at the macroscopic scale (thermal or thermomechanical cycle).

Recently a new full field approach, based on a LS description of the interfaces in a FE context has been introduced to model primary recrystallization, including the nucleation stage, and has been extended to take into account the grain growth stage of monophasic polycrystalline structures [START_REF] Bernacki | Finite element model of primary recrystallization in polycrystalline aggregates using a level set framework[END_REF][START_REF] Bernacki | Level set framework for the finite-element modelling of recrystal-lization and grain growth in polycrystalline materials[END_REF][START_REF] Cruz-Fabiano | Assessment of simplified 2D grain growth models from numerical experiments based on a level set framework[END_REF].

Moreover in this LS context, Smith-Zener pinning (SZP) phenomenon can be taken into account in a natural way [START_REF] Agnoli | Development of a level set methodology to simulate grain growth in the presence of real secondary phase particles and stored energy-application to a nickel-base superalloy[END_REF]. Modeling at the mesoscopic scale can thus be a help for understanding complex microstructural phenomena such as abnormal grain growth; it can also be used to optimize/calibrate higher scale models through numerical experiments leading to a real multiscale approach. Full field models are generally associated with high computation times. Recent major developments and improvements made on the LS approach [START_REF] Shakoor | An efficient and parallel level set reinitialization method -application to micromechanics and microstructural evolutions[END_REF][START_REF] Scholtes | New finite element developments for the full field modeling of microstructural evolutions using the level-set method[END_REF] make possible its use in an industrial context.

After introducing the FE-LS numerical model in the next section, some examples of large scale simulations in 2D and 3D are presented. This paper focuses on thermal treatments.

Numerical model description

Level Set (LS) function. The microstructural evolution is given by the displacement of interfaces (grain boundaries for example). The model considered here works around a LS description of the interfaces in a FE framework. This method has the advantage of avoiding the difficult problem of tracking interfaces. Indeed a LS function ψ is defined over a domain Ω as the signed distance function to the interface of a sub-domain G of Ω. The values of ψ are calculated at each mesh node and the sign is defined as positive inside G and negative outside:

∀𝑡 # 𝜓(𝑥, 𝑡) = ±𝑑,𝑥, G(𝑡)-, 𝑥 ∈ 𝛺 G(𝑡) = {𝑥 ∈ 𝛺, 𝜓(𝑥, 𝑡) = 0} (1)
where d(.,.) corresponds to the Euclidean distance. The interface is implicitly given by the level 0 of the function ψ.

Theoretically, each grain of a polycrystal must be represented by its own LS function. In practice, non-neighbouring grains in the initial microstructure (separated by a certain number of grains) can be grouped to form global LS (GLS) functions. This approach allows using a small number of functions Np compared to the total number of grains constituting the microstructure Ng and thus limits the numerical cost. The interface of each GLS function is then displaced by solving a set of convective-diffusive equations [START_REF] Bernacki | Level set framework for the finite-element modelling of recrystal-lization and grain growth in polycrystalline materials[END_REF]:

∀𝑝 ∈ 41, … , 𝑁 8 9: < => ? (@,A) =A -𝑚𝛾∆𝜓 8 (𝑥, 𝑡) + 𝑣 H . ∇𝜓 8 (𝑥, 𝑡) = 0, 𝜓 8 (𝑥, 𝑡 = 0) = 𝜓 8 K (𝑥) (2)
where m and γ are respectively the GB mobility and energy. The diffusive term refers to capillarity effects while the convective one is related to stored energy gradients throughout the microstructure.

Reinitialisation procedure. The distance function must be reinitialized at each time step in order to keep the metric property ∥∇ψp∥ = 1 during all the simulation. Indeed, even if reinitialization is favourable for the regularity of the LS function, this treatment is especially crucial in order to verify that the capillarity effects are properly described by the diffusive part of Eq. ( 2). The classical approach used in [START_REF] Bernacki | Level set framework for the finite-element modelling of recrystal-lization and grain growth in polycrystalline materials[END_REF][START_REF] Cruz-Fabiano | Assessment of simplified 2D grain growth models from numerical experiments based on a level set framework[END_REF][START_REF] Agnoli | Development of a level set methodology to simulate grain growth in the presence of real secondary phase particles and stored energy-application to a nickel-base superalloy[END_REF] consists in solving a Hamilton-Jacobi (HJ) equation for each GLS function.

This method corrects iteratively the LS functions until their respective metric properties are restored. Based on the resolution of a large number of partial differential equations systems, the HJ method can require a lot of iterations for achieving convergence. An efficient and parallel reinitialization algorithm based on a direct approach and using optimized searching procedures has been recently developed [START_REF] Shakoor | An efficient and parallel level set reinitialization method -application to micromechanics and microstructural evolutions[END_REF]. Based on the exact analytic reconstruction of the distance function, this method leads to significant computational cost reductions.

Recoloring algorithm.

The numerical costs for solving Eq. ( 2) depend linearly on the number of GLS functions. The initial separation between grains belonging to the same GLS function must be chosen small enough to limit the computation time and sufficiently high to avoid a numerical coalescence (the grains belonging to the same GLS function can no longer be distinguished if they meet each other). To address this issue, an efficient grain recoloring algorithm has been recently developed [START_REF] Scholtes | New finite element developments for the full field modeling of microstructural evolutions using the level-set method[END_REF] in order to handle dynamically the distribution of the grains inside the GLS functions. This methodology is composed of two major steps: (i) the separation of the connected components on the FE mesh and (ii) the swapping algorithm which detects the risk of coalescence and reassigns the grains in other GLS functions if needed.

Mesh adaptation. The model works in 2D and in 3D. Realistic predictions necessitate a sharp description of the interfaces. This issue is achieved thanks to an anisotropic mesh adaptation around the interfaces (figure 1). As the interface moves, periodic remeshing is performed such that the refinement zone always coincides with the interface position. This technique allows improving precision and reducing computation times in 2D. (by using experimental micrographs for example) or from a statistical method. For the latter, efficient high density packing algorithms have been developed to respect a given grain size distribution [START_REF] Hitti | Precise generation of complex statistical represen-tative volume elements (RVEs) in a finite element context[END_REF][START_REF] Hitti | Optimized Dropping and Rolling (ODR) method for packing of polydisperse spheres[END_REF] (see Figure 2). Boundary conditions applied to the RVE are representative of what suffered a material point at the macroscopic scale (thermomechanical cycle of the point considered).

Different 2D and 3D large-scale simulations enabled by the new major developments described previously, and which would not have been performed in acceptable computation times before, are illustrated below. Pure grain growth. In case of pure grain growth, the convective term of Eq. ( 2) vanishes and microstructural evolution is only driven by GBs mean curvature. Figures 3 and4 represent the microstructural evolution of a 304L austenitic stainless steel subjected to an isothermal heat treatment at 1050°C. Simulations are performed respectively on a 2D and a 3D polycrystal. In both cases, the microstructural evolution is only driven by the reduction of the total GBs length/area.

With isotropic GB mobility and energy, the well-known Burke and Turnbull equation [START_REF] Burke | Recrystallization and grain growth[END_REF] is used to validate the results obtained through these full field simulations. The comparison is plotted on figure 3 showing a good agreement between both models.

t = T

Smith-Zener pinning (SZP) phenomenon. In order to limit the final grain size which can be detrimental for the mechanical properties, a classical method consists in precipitating second phase particles (SPP). These particles hinder the grain boundaries (GB) motion thanks to the dragging force exerted on GBs. The LS method is particularly interesting for the modeling of SZP [START_REF] Zener | Grains, Phases and Interfaces Interpretation of Microstructures[END_REF] since no assumption is required concerning the shape or the dragging force exerted by the SPP. The interaction angle α between the GB and a precipitate is dictated by the balance of the surface tensions according to sin 𝛼 = ,𝛾 Q 8 -𝛾 R 8 -/𝛾, where 𝛾 R 8 , 𝛾 Q 8 and 𝛾 are respectively the surface tensions associated with the interfaces Γ R 8 , Γ Q 8 and Γ RQ (figure 5(a)). This constraint can be simply imposed by the mean of a boundary condition in the considered LS framework:

∇> ‖∇>‖ . 𝑛 W⃗ = ∇𝜓. 𝑛 W⃗ = sin 𝛼. (3)
When a GB passes through a particle, its shape thus adapts to satisfy Eq. ( 3), which modifies its local curvature and therefore its kinetic. If this approach is usually efficient, under specific conditions, abnormal grain growth (AGG) may occur. AGG can be described as the selective growth of only a few grains while other grains do not grow in the microstructure. It may occur as a result of a heterogeneous stored energy field leading to a driving force for some grain boundaries that overcomes the SZP force, or as a result of GB energy anisotropy, or as a result of a Based on the work described in [START_REF] Agnoli | Development of a level set methodology to simulate grain growth in the presence of real secondary phase particles and stored energy-application to a nickel-base superalloy[END_REF], the recent numerical developments [START_REF] Shakoor | An efficient and parallel level set reinitialization method -application to micromechanics and microstructural evolutions[END_REF][START_REF] Scholtes | New finite element developments for the full field modeling of microstructural evolutions using the level-set method[END_REF] allowed performing 2D and 3D simulations as shown in figures 6 and 7. SPP are considered inert and are represented as holes in the FE mesh (white disks in figure 5(b), black disks in figure 6(a) and green spheres in figure 7) [START_REF] Scholtes | Full field modeling of the Zener pinning phenomenon in a level set framework -discussion of classical limiting mean grain size equation[END_REF]. In such a way, incoherent or coherent particle/grain interfaces can be considered through appropriate boundary conditions and the dragging effect is naturally modeled by the modification of the local curvature when the GB passes through the particles. The full field approach described here has also been applied to the modeling of static [START_REF] Scholtes | 3D level set modeling of static recrystallization considering stored energy fields[END_REF][START_REF] Ilin | Full field modeling of recrystallization: Effect of intragranular strain gradients on grain boundary shape and kinetics[END_REF] and dynamic [START_REF] Maire | Modeling of dynamic and post-dynamic recrystallization by coupling a full field approach to phenomenological laws[END_REF] recrystallization. In that case, the driving force for grain boundaries motion is given by both grain boundaries mean curvature and stored energy gradients between neighbouring grains (recrystallized or non-recrystallized). Preferential sites for nucleation of newly recrystallized grains can also be controlled by a suitable choice of nucleation criteria (topological and/or stored energy based).

Conclusion

A full field approach using the level set method in a finite element context has been used to simulate the microstructural evolution during thermal treatments. Modeling at the mesoscopic scale can be a help for understanding complex microstructural phenomena but it can also be used to optimize/calibrate higher scale models (like mean field models [START_REF] Scholtes | Full field modeling of the Zener pinning phenomenon in a level set framework -discussion of classical limiting mean grain size equation[END_REF][START_REF] Maire | A new topological approach for the mean field modeling of dynamic recrystallization[END_REF]). These simulations allow describing in a natural way the materials in terms of microstructural features. The recent improvements done to reduce the high computation times generally associated with these models make possible now their use for industrial applications though the DIGIMU ® software.

Figure 1 .

 1 Figure 1. Polycrystal description in 3D with the used finite element mesh (anisotropic meshing near grain boundaries).

Figure 2 .

 2 Figure 2. 2D RVE generation (500 grains) (left) respecting a given grain size distribution (right).

Figure 3 .Figure 4 .

 34 Figure 3. (a) Initial 304L 2D polycrystal (50000 grains); (b) Microstructural evolution during an isothermal heat treatment (1050°C): comparison with the Burke and Turnbull model [11, 14].

Figure 5 .

 5 Figure 5. (a) Scheme illustrating the SPP/GB interaction; (b) View of a FE mesh used for the Zener pinning simulations. The voids in the mesh (white disks) represent the SPP [16].

Figure 6 Figure 6 .Figure 7 .

 667 Figure 6 shows an example of 2D simulations performed with the DIGIMU ® software. An isothermal treatment at 985°C during 30min is applied on an Inconel® 718 superalloy. At this temperature, the alloy contains δ precipitates at thermodynamic equilibrium, considered as SPP in the simulation. A two-dimensional RVE composed of 800 grains of γ phase is generated with a mean grain size of 8µm (figure6(a)). 1% surface fraction of δ phase is considered with a mean particle size of 400nm. The mean grain size evolution during the isothermal treatment is plotted figure 6(b). In order to evaluate the strong dragging effect exerted by SPP on GBs, results of a similar simulation without adding SPP in the RVE are also plotted.

Acknowledgments

The authors thank the Framatome, ArcelorMittal, ASCOMETAL, AUBERT & DUVAL, CEA, SAFRAN, TIMET and Constellium companies and the ANR for their financial support through the DIGIMU consortium and ANR industrial Chair.


Quang-Vinh Dang
email: vinh.dang@tmc.nl

Outlier detection on network flow analysis

Keywords: outlier detection, classification, ddos detection

whether they are published or not. The documents may come

Outlier detection on network flow analysis

Introduction

A denial-of-service (DoS) attack is characterized "by an explicit attempt by attackers to prevent the legitimate use of a service" [START_REF] Mirkovic | A taxonomy of ddos attack and ddos defense mechanisms[END_REF]. If the attackers coordinate the DDos traffic from multiple sources to perform the attack, it will be Distributed Denial-of-Service (DDos) [START_REF] Koay | A new multi classifier system using entropy-based features in ddos attack detection[END_REF].

Multiple studies have analyzed the detection and prevention strategies of DDoS attacks by using classification algorithms [Douligeris and Mitrokotsa, 2004;Fouladi et al, 2016;[START_REF] Koay | A new multi classifier system using entropy-based features in ddos attack detection[END_REF][START_REF] Alsirhani | Ddos attack detection system: Utilizing classification algorithms with apache spark[END_REF]. While these methods achieved a lot of success, they suffer from imbalanced dataset problem [START_REF] Krawczyk | Learning from imbalanced data: open challenges and future directions[END_REF] and lack of detecting unfamiliar flows. For instance, these techniques mail fail to detect a new DDoS attack technique that they did not see during the training period. Furthermore, supervised classification algorithms usually exhaust of data.

Outlier detection algorithms [START_REF] Aggarwal | Outlier Analysis[END_REF] try to distinguish outlier points from normal traffic data. Hence, the techniques might be performed in unsupervised manner [START_REF] Campos | Cdmc2018 dataset: Ddos attacks detection for enterprise network security[END_REF]. Furthermore, outlier detection algorithms can deal well with extremed imbalanced dataset, such as 1:1000 ratio [START_REF] Krawczyk | Learning from imbalanced data: open challenges and future directions[END_REF].

In this paper we evaluate the performance of outlier detection algorithms on detecting DDos traffic. Our work is related to other evaluation studies, such as of [START_REF] Hodge | An evaluation of classification and outlier detection algorithms[END_REF]. However, the authors of [START_REF] Hodge | An evaluation of classification and outlier detection algorithms[END_REF] do not analyze the performance in case of imbalanced datasets.

Evaluation

Algorithms

We evaluated the following algorithms:

-CBLOF (Clustering-Based Local Outlier Factor) [START_REF] He | Discovering cluster-based local outliers[END_REF]].

-HBOS (Histogram-Based Outlier Score) [START_REF] Goldstein | Histogram-based outlier score (hbos): A fast unsupervised anomaly detection algorithm[END_REF].

-IForest Isolation Forest [START_REF] Liu | Isolation forest[END_REF].

-k-NN (k Nearest Neighbors) [START_REF] Ramaswamy | Efficient algorithms for mining outliers from large data sets[END_REF]].

-MCD (Minimum Covariance Determinant) [START_REF] Rousseeuw | A fast algorithm for the minimum covariance determinant estimator[END_REF]]. -OCSVM (One-Class SVM) [START_REF] Ma | Time-series novelty detection using one-class support vector machines[END_REF]].

-PCA (Principal Component Analysis) [START_REF] Shyu | A novel anomaly detection scheme based on principal component classifier[END_REF]].

Dataset

We used the dataset provided by [Ghorbani and Lashkari, 2018] that contains 464, 976 samples that are assigned the labels "Attack" or "Benign". We consider these labels as ground truth. A set of 76 features is provided. Some of the features are:

-Flow.Duration -Tot.Fwd.Pkts (Total Forward Packets) -Tot.Bwd.Pkts (Total Backward Packets) -Fwd.Pkt.Len.Max -Fwd.Pkt.Len.Min

The "Attack" traffic contains 3.76% of the whole dataset (17, 462 samples). In order to evaluate the performance of the outlier detection algorithms, we create different datasets with different "Attack" Ratio, range from 0.01 to 0.99.

To change the class ratio, we applied the following function to select a subset of the dataset: #d i v i d e t r a i n / t e s t t r a i n = r e s . sample ( f r a c = 0 . 7 , r a n d o m s t a t e =200) t e s t = r e s . drop ( t r a i n . i n d e x ) return ( t r a i n , t e s t )

Results

In this section we present the performance in term of AU C and Accuracy scores of each algorithms. Overall, while the benign ratio increases the Accuracy scores increase for all algorithms, that can be explained by the imbalanced of the dataset. Another observation is that the performance of the algorithms are very similar between training and testing set due to the fact that these algorithms are all unsupervised. In term of AU C score we could see that IForest and PCA algorithms achieved the best scores while the benign ratio increases.

Conclusions

In this paper we evaluate the performance of unsupervised outlier detection algorithms in detecting DDoS attacks. We showed that the outlier detection algorithms perform, particularly Isolation Forest or PCA-based algorithms, perform best if the proportion of outlier instances is small. This contrasts with popular classification algorithms. In the future we will focus on analyzing Isolation Forest and PCA algorithms in other scenarios.

  def m a k e d a t a s e t ( b e n i g n r a t i o = 0 . 9 , d f a t t a c k = d f a t t a c k , d f b e n i g n = d f b e n i g n ) : N a t t a c k = len ( d f a t t a c k . i n d e x ) N benign = len ( d f b e n i g n . i n d e x ) n a t t a c k = N benign / ( b e n i g n r a t i o / (1-b e n i g n r a t i o ) ) s a m p l e d f a t t a c k = d f a t t a c k . sample ( int ( n a t t a c k ) , r e p l a c e=F a l s e ) r e s = pd . c o n c a t ( [ d f b e n i g n , s a m p l e d f a t t a c k ] ) r e s = s h u f f l e ( r e s ) r e s = r e s [ [ c o l f o r c o l in r e s i f not len ( set ( d f [ c o l ] ) ) = = 1 ] ]

Fig

  Fig. 1: CBLOF


Malte Falk
email: malte-falk@gmx.de

Stefan Walter
email: swalter@dspace.de

Achim Rettberg
email: achim.rettberg@iess.org

A UML profile to couple the production code generator TargetLink with UML design tools

When modelling architecture of complex embedded systems proper architecture languages and tools are necessary. UML [1] has become a proven and well accepted design language to express system as well as software architecture. For definition of internal behavior of components composed and specified during software design, Simulink is commonly used, especially for automotive and aerospace applications. As common practise, code is generated directly from such behavior models. Therefore, code generators such as TargetLink [2] are used. In this paper we propose a UML profile to describe specific properties necessary to adapt UML models to the code generator TargetLink.

Motivation

To cope with today's growing complexity of requirements in embedded systems development adequate development methods are crucial to develop high quality systems. Todays embedded systems often consists of distributed functionalities where software components could run on the same or on a different hardware platform within the distributed system. To define such complex system structures an architectural design phase in the development process is essential. As a de-facto standard language to be used in software and system architecture modelling the Unified Modelling Language (UML) [START_REF]Unified Modeling Language (UML) Resource Page[END_REF] and the System Modelling Language (SysML) [START_REF]OMG Systems Modeling Language[END_REF] is widely used in different fields. At a certain step during development of embedded systems, one have to model and implement the behavior of the defined software components. A common tool for behaviour modelling is Simulink from The Mathworks [4]. Especially in the automotive industry but also for development of airborne software both modeling environments UML and Simulink are used extensively. After modelling the behavior of a software component, in best case the embedded code to be integrated on the electronic control unit is directly generated from the behavior model, in this paper from Simulink. Generating code from Simulink software specifications which is then directly used on electronic control units is de-facto standard in state of the art development processes especially in the automotive industry. The technique of autocode generation is well accepted and widely used especially in safety critical projects. One of the major tools used by the industry is TargetLink from dSPACE GmbH [START_REF]dSPACE TargetLink -Automatische Seriencode-Generierung[END_REF]. In this paper we propose a mapping between UML component architecture models and TargetLink models.

Related Work

Various research work deal with mapping of Matlab/Simulink models to UML like [START_REF] Sjöstedt | Mapping Simulink to UML in the design of embedded systems: Investigating scenarios and transformations 6[END_REF]. In contrast to this paper, [START_REF] Sjöstedt | Mapping Simulink to UML in the design of embedded systems: Investigating scenarios and transformations 6[END_REF] discusses a possibility to illustrate the Matlab/Simulink models and the behaviour of it in UML and replaces Simulink hereby.

Other publications discuss a possibility to describe systems with UML and redescribe it in Matlab/Simulink. In [6] it is discussed how software architectures which are described in UML could be transformed to simulation models which are described with Matlab/Simulink. These publications describe a similar approach compared to this paper. In contrast to other publications this paper describes a possibility to map a TargetLink model, which is based on Matlab/Simulink, to UML. The benefit is to reuse properties such as interface description, etc. from an architecture model and annotate it to a TargetLink model, which is later used for automatic code generation.

TargetLink

TargetLink is a Toolbox for Matlab/Simulink in order to generate series production code by a push of a button from a Simulink model. Beside generation of regular ANSI-C code for fixed point or floating point processors it is also possible to generate code for certain processor/compiler combinations. To enhance a Simulink model to a TargetLink model used for code generation, certain parameters need to be set, to describe how the code generated by TargetLink looks like. To maintain all parameters for all blocks within the TargetLink model the TargetLink Data Dictionary is used. The TargetLink Data Dictionary represents a data container in order to describe all elements. These elements represent information for the model design, the code generation and the implementation of a model on an electronic control unit. TargetLink elements are described by various properties and can be referenced by TargetLink models. In the following section we will introduce and discuss the relevant TargetLink elements used for UML mapping.

TargetLink Data Dictionary elements

The TargetLink Data Dictionary is used to parameterize and describe all elements used in TargetLink models. Below all elements which are relevant to be mapped to UML are specified. A more in-depth and formal description of the various element properties can be found in [7] and [START_REF] Falk | Definition eines Profils zur Kopplung des Seriencode-Generators Tar-getLink an UML-Werkzeuge[END_REF].

Pool The TargetLink Data Dictionary is divided into three areas Config, Pool, and Subsystem. In this paper only the Pool -area is considered. This area contains all data elements which are required for code generation. Examples of elements in the Pool area are scaling values of fixpoint variables the or type definition of variables.

Blocks Blocks are the main elements in TargetLink Data Dictionary and therefore essential for the code generation. Based on the Block description, Simulink Blocks could be generated directly from the TargetLink Data Dictionary. Even though various types of Blocks are available inside the TargetLink Data Dictionary, this paper focusses only on Blocks of type TL Function. Those Blocks represent the base architecture of the software component to be developed.

Signature and SignaturePort A Signature contains Signature-Ports, whereas Signature-Ports are divided in in-, out-, and user -ports. Signatures are used to describe which in-and out-ports are available at the TL Function Block. In contrast to in-and out-ports, user-ports are freely configurable for different use cases, e.g. calibration-ports.With ports it is possible to connect TL Function Blocks with Variables, either incoming or outgoing.

Variable Variables are used to exchange information between different TL Function Blocks. The properties of variables define the appearance within the generated code. The actual type of Variable is defined by a Typedef element as described in the following paragraphs . A min, max range can be set by a reference to a Scaling element as described in the following paragraphs.

Typedef The Typedef element specifies the datatype of a Variable element. In the TargetLink Data Dictionary Typedefs are referenced by Variables.

Scaling A Scaling is used to define the value range of a Variable. This is necessary in case of fixed-point code generation. Furthermore, it is possible to define values for Least Significant Bit (LSB), Offset, and , physical unit within the Scaling properties.

Module The characteristics of the code modules in the generated code are specified by Module elements, e.g. the memory location. Properties of these elements are TargetLink specific and do not have any implication on architecture level. Due to this fact it is not considered in scope of this paper.

FunctionClass FunctionClass properties define how the generated code for a referenced TL Function Block would look like. Because FunctionClasses are usually predefined, they are not considered in the further course of this paper.

VariableClass VariableClasses are similar elements compared to Function-Classes. The difference is that VariableClasses specify Variables in the generated code. Because VariableClasses are usually predefined, they are not considered in the further course of this paper.

TargetLink Data Dictionary model In the context of this paper a Tar-getLink Data Dictionary model is a finite set of all above described elements. In section 4 of this paper a mapping of TargetLink Data Dictionary model to UML is described.

Relationship between TargetLink elements

This section describes the relationship between the TargetLink Data Dictionary elements as specified in section 3.1. This description could be later used to derive the connection between the different UML elements in an UML profile. An analysis of the dependencies could be realised by a tree structure diagram with breadth-first search. It is obviously depicted in figure 1 that Variables are independent from other TargetLink Data Dictionary elements. This means a Variable could exist without a TL Function Block, e.g. global Variables. Figure 1 also indicates that Variables and TL Function Blocks are split into different branches. This implies that those two elements need to be considered differently when defining the UML profile.

Another fact of the tree structure shows that a TL Function Block is linked to Variables over a Signature and Signature-Port, whereas one Signature-Port of a Signature is linked to exactly one Variable. On the other hand a Variable could be linked to different Signature-Ports.

Prototype TargetLink model in UML

Based on the previous definitions, in this section a prototype for describing TargetLink models in UML is suggested. The section is subdivided into two subsections. The first subsection explains the UML diagram type selected to be used for expressing the TargetLink model elements. In the second subsection it is described which element of the selected UML diagram type is mapped to a specific element of the TargetLink Data Dictionary.

Composite structure diagram

With composite structure diagrams it is possible to describe the internal structure of a class or the collaboration between different classes. It is similar to the component diagram and therefore as described in [START_REF] Booch | The Unified Modeling Language User Guide[END_REF] on page 93 it could be combined with such diagram types. In addition, a composite structure diagram provides two different views on a system. The first view is the structural-dynamic view which focusses on the function of the system and which parts are needed for the functions. The second view is shown in figure 2 In a first step the system is partitioned into various subsystems. In the following these different subsystems are divided into various components. Each component comprises several classes with attributes. This way to describe systems can be found on system level (Hardware) or on software level (GUI split into application, windows, etc.) [8, p. 194].

The metaclasses of the composite structure diagram are classes, parts, ports, interfaces and connectors. In the following all relevant elements are shortly described. A class is a kind of construction plan for an object. Parts are used to split a class into subsets. Parts could be extended by ports in order to implement interaction points for communication between elements. To connect different ports of parts connectors are used. In the following section a possible prototype which describes how TargetLink Data Dictionary elements are mapped to UML elements is presented [9, p. 125ff].

Prototype

The prototype differentiates between a system and variable level. The distinction was made based on results of the previously described tree structure diagram analysis. On system level it is possible to describe TL Function Blocks, Signatures and Signature-Ports. Whereas on variable level Variables, Typedefs and Scalings are described. In figure 3 and 4 both, the system level and variable level is depicted. Signature-Ports enable communication between TL Function Blocks using Variables, as shown in figure 1. On Variable level all variables a TL Function Block could contain are specified.

As shown in figure 1 With mapping UML Parts to Signatures and TL Function Blocks, UML Interfaces to Scalings and Typedefs, UML Class to Variables and UML Ports to Signature-Ports all profile relevant TargetLink elements are described in the UML profile. These elements are a subset of all TargetLink elements.

Definition of the TargetLink UML Profile

In the previous section a possibility on how to specify TargetLink Data Dictionary elements in UML was described. To enable specifying TargetLink Data Dictionary relevant elements in UML composite structure diagrams, the semantics of those diagrams need to be extended. In UML such kind of extensions are defined in UML profiles, mainly consisting of stereotypes, tagged values and constraints. Stereotypes expand the UML metaclasses and represent the extended elements. Tagged values expand stereotypes by properties as name-value pairs. Constraints define additional constraints for the stereotypes and enable users to check a model by the specified constraints. In the further course of this paper first the structure of different packages of the TargetLink Data Dictionary UML profile is described. In a second step the structure of the profile is illustrated. A more in-depth description of the UML profile can be found in [START_REF] Falk | Definition eines Profils zur Kopplung des Seriencode-Generators Tar-getLink an UML-Werkzeuge[END_REF].

Package structure

This subsection describes the structure of the various packages of the TargetLink Data Dictionary UML profile. Different UML packages partition the various re-quired elements of the UML profile. Figure 5 shows the structure of the Tar-getLink Data Dictionary profile with different packages. The figure shows a subdivision of the structure in four different UML packages. The package UML 2.x provides all metaclasses of the UML version 2.x. Because the TargetLink Data Dictionary profile expands the semantics of a composite structure diagram it is essential to use UML 2 or higher [START_REF] Rupp | Stefan Queins: UML 2 glasklar -Praxiswissen fr die UML-Modellierung[END_REF].

The UML 2 metaclasses used by the package TL-DD-Profil are provided via <<reference>>-connection to the package UML 2.x. This connection enables to expand metaclasses, such as ports or classes, with stereotypes. This kind of connection is called metamodel-reference because all metaclasses of UML 2.x which are provided with the <<metamodel>>-package are referenced by the profile package.

The definition of the profile itself can be found in the package TL-DD-Profil. The stereotype <<profile>> is used to declare that the package contains UML profiles. The TL-DD-Profil represents the key package within the package diagram. It contains all required metaclass extensions such as stereotypes, tagged values representing the TargetLink Data Dictionary properties and additional constraints. Using the <<import>>-connection the TL-DD-Profil package imports different predefined elements from the Definition-package.

As mentioned above, the Definition-package describes different elements to be used in the TL-DD-Profil. Among others, basic data types of the TargetLink Data Dictionary are determined in this package. For example, predefined elements such as VariableClasses are defined in this package. The Fuelsys-package represents the actual application model which is described by applying the Tar-getLink UML profile.

Profile structure

The following section explains the internal structure of the profile package TL-DD-Profil based on the previous prototype. The different metaclasses in the profile package are extended by stereotypes. The different metaclasses are provided by the <<reference>>-connection between profile package and UML 2.X package which is illustrated in figure 5. The different extensions of metaclasses by stereotypes are depicted in figure 6. This paper concentrates on the structure and the dependencies between the different stereotypes. A precise description of the UML profile is given in [START_REF] Falk | Definition eines Profils zur Kopplung des Seriencode-Generators Tar-getLink an UML-Werkzeuge[END_REF]. The different <<use>>-connections, as depicted in figure 5, represent the associations between the different stereotypes. Furthermore, the connection shows which elements are in communication. For example the figure obviously shows the connection between TL Function Blocks and different ports (e.g. TLInport, SLInport, ).

Moreover, figure 5 shows which metaclass is extended by which stereotype. The prototype in 4.2 defines Scaling elements as a UML class. Therefore, the metaclass Class is extended by the stereotype Scaling. Another example is the stereotype Typedef which extends the metaclass Class as well. The Scaling element and the Typedef element will be provided by both extensions in the UML profile. Another element that is provided by the UML profile is the stereotype Variable. In 4.2 Variable elements are defined as interchangeable elements that carries information. These elements are mapped to UML interfaces. Therefore, the UML metaclass interface is extended by the stereotype Variable. The so called variable level that is described in section 4 only contains those three element types.

TL Function Blocks, Signatures, and all kinds of Signature-Ports are applied on system level. Each TL Function Block specifies a part of the entire system in the prototype and are therefore mapped to UML Parts. Thus, in figure 6 it is depicted that the metaclass Part is extended by stereotyp TL Function Block.

Various stereotypes, representing different kind of communication ports, extend the metaclass Port. In UML, ports specify interaction points of parts and its environment. In the profile ports are used to represent the different Signature-Ports. Signature-Ports are interaction points of TL Function Blocks used to consume and provide Variables. Signature-Ports can represent in-, out-, or user-ports. This is the reason why the metaclass Port is extended by different stereotypes. In detail the stereotypes differentiate only by its names. With the various Signature-Port stereotypes a user can directly recognize the kind of the Signature-Port.

The stereotype FBConnection extends the metaclass Connector. Signature-Ports can be connected to each other via FBConnection. These connections can not be mapped to the TargetLink Data Dictionary but in UML it shows the connection between all elements via ports. A user could easily recognize the interconnection between different TL Function Blocks. Those connections represent the information flow within a system. A more detailed description of the UML profile can be found in [START_REF] Falk | Definition eines Profils zur Kopplung des Seriencode-Generators Tar-getLink an UML-Werkzeuge[END_REF]. The following section gives an overview on how to couple UML tools and the TargetLink Data Dictionary to exchange information.

Information exchange UML -TargetLink Data Dictionary

With the UML profile defined in this paper it is possible to already add Tar-getLink Data Dictionary properties which will be used in a later step for production code generation to UML elements during system design. However an automatic exchange of those properties between the UML model specified during design phase and the TargetLink Data Dictionary is not yet possible. A common format to exchange information between programs and software tools is XML. Also the TargetLink Data Dictionary is able to import XML files containing a specific data structure. By importing XML files into the TargetLink Data Dictionary it is possible to either expand or overwrite available elements.

A standard for exchanging models between UML tools is the XML Metadata Interchange (XMI) which is published by the Object Management Group (OMG). The import and export of this XML based data format is supported by all major UML tools. XMI files describe complete UML diagrams in textual form. Even if XMI is a standard data format, each UML tool implements its own interpretation of this standard, which slightly differs in structure of properties and used XMI vocabulary. In other words although XMI is a standard, each XMI-file exported from a different UML tool looks different. For this reason it is difficult to design a generic compiler for the transformation between XMI and TargetLink Data Dictionary XML.

In the following section we briefly describe the steps undertaken to design a transformation between UML XMI and TargetLink Data Dictionary XML. Due to the variations in the XMI standard as mentioned in the previous section, we focussed our analysis on the two most commonly used tools in the industry, Enterprise Architect [START_REF]Enterprise Architect -Model Driven UML Tools[END_REF] and Rational Rhapsody [START_REF]Rational Rhapsody family[END_REF]. As a first step we have implemented the previously described UML profile in both tools. Based on this profile we design a demo system that includes all in section 5 defined elements. In the second step the demo model was exported to XMI, using the standard export mechanism of the UML tools. Based on the exported XMI files we have to analyse the structure and the different vocabularies of both files. On the basis of analysis results a grammar is developed which describes the relevant items of the XMI export of both UML tools.

After the gramatic was derived from the XMI export, now the TargetLink Data Dictionary XML file is analysed. For each export, the structure and the vocabulary of this file is always the same. Therefore, it is sufficient to consider all in section 3.1 defined TargetLink Data Dictionary elements. Also for the TargetLink Data Dictionary export a grammar is defined, which is similar to the one developed for the XMI export. By specifying transformation rules the XMI grammar is mapped to the XML grammar of the TargetLink Data Dictionary. The transformation rules describe an unambiguous mapping between the information of the TargetLink Data Dictionary and the XMI file.

As a last step an algorithm was implemented that is able to compile the XMI grammar in the XML grammar. If the grammar is expressed in an adequate language, e.g. antlr [13], a parser generator could be used to generate this algorithm automatically. The definition of the grammar and the transformation rules is not focus of this paper. A detailed declaration of these grammars can be found in [START_REF] Falk | Definition eines Profils zur Kopplung des Seriencode-Generators Tar-getLink an UML-Werkzeuge[END_REF].

Conclusion and future work

This paper summarizes a possibility to describe TargetLink Data Dictionary elements in UML to provide a smoother transition between software architecture definition and functional component design. Therefore, a UML profile was defined which provides various TargetLink Data Dictionary elements to be used in UML diagrams. The specified UML profile extends semantics of the composite structure diagram. Using this UML profile it is possible to connect UML tools to the production code generator TargetLink. This coupling is an important step in development of complex software architectures where software design tools such as UML as well as automatic code generators such as TargetLink became a defacto standard. The smooth transition between UML tools and TargetLink supports the consistent exchange of software components and its interfaces between different engineering teams, responsible for software architecture and software component design.. Following this approach, each development team could import their subsystems from the entire software architecture description automat-ically into the TargetLink Data Dictionary to describe the functional behaviour with Matlab / Simulink and generate production code with TargetLink.

With the concept described in this paper we could not solve the problem that every UML tool needs its own compiler due to the ambiguous definition of XMI structure and vocabulary. A generic methodology of transforming UML XMI files to TargetLink Data Dictionary readable XML files is subject to future work.

This paper is a rough overview about the topic. More in-depth information on different aspects e.g. details on grammar specification and complete definition of the UML profile can be found in [START_REF] Falk | Definition eines Profils zur Kopplung des Seriencode-Generators Tar-getLink an UML-Werkzeuge[END_REF].

Fig. 1 .Figure 1

 11 Fig. 1. Tree structure diagram of the Pool area

  as a class diagram.

Fig. 2 .

 2 Fig.2. static view[8, p. 194]

Fig. 3 .

 3 Fig. 3. System level in UML

Fig. 5 .

 5 Fig. 5. Package structure

Fig. 6 .

 6 Fig. 6. Profile structure

  , on Variable level it is possible to describe Variables and its dependencies. Furthermore, specification of variable types (Typedefs) Variable level in UML and scalings are done on Variable level. Figure4shows an excerpt from a specification of Variable, Typedef and Scaling elements on Variable level used for communication between different TL Function Blocks via Ports. In the TargetLink context Variables specify the interface of TL Function Blocks. Therefore, in this concept Variable elements are mapped to UML interfaces.Typedefs and Scalings represent a construction plan for Variables in Tar-getLink Data Dictionary. These elements describe the appearance of Variables in the production code. In UML classes have a similar functionality. They influence objects and provide so some kind of construction plan by attributes and operations[9, S.32]. For this reason Scaling and Typedef elements are represented by classes.

	<<Interface>>	<<Class>>	<<Class>>
	throttle	uint8	VOID SCALING
	Fig. 4.


Tayfun Gezgin

Björn Koopmann

Achim Rettberg

Combining an Iterative State-based Timing Analysis with a Renement Checking Technique

Keywords: Real-time Systems, Scheduling Analysis, Re-Validation, Timing Analysis, State-based Timing Analysis

The analysis of real-time properties is crucial in safety critical areas like in automotive applications. Systems have to work in a timely manner to oer correct services. Most of the applications in this domain are distributed over several computation units, inter-connected by bus systems. In previous works we have introduced a state-based analysis approach to validate end-to-end deadlines for distributed systems. The approach is based on the computation of the state spaces of all resources, such as processors and buses, in an iterative fashion. For this, abstraction and composition operations were dened to adequately handle task and resource dependencies. During the design process of a system changes occur typically on both the specication and implementation level, such that already performed analyses of the system have to be repeated. In this work, we extend our timing analysis with a renement checking approach, detail when it is appropriate to be used, and compare the analysis times with the computation times to perform the renement check.

Introduction

In recent years the co-operations and inter-connections between individual, geographically distributed systems heavily increased. Also in safety critical areas the signicance of these topics increased. As an example, much eort has been invested in the development of Car-to-Car communications with the aim to increase the safety in trac and optimize trac ows. Another example is the dynamic partitioning of the airspace with respect to time investigated in the SESAR (Single European Sky ATM Research) program. The recent partitioning of the airspace is performed in a static manner with respect to time, i.e. the trajectories are not changed during the whole landing approach and the takeo.

The shift to a dynamic partitioning, which is called 4D-trajectories, involves a much more intensive co-operation between the tower and each airplane.

For the correct functionality of safety-critical functions of such systems, timing constraints are one crucial aspect. The nal product has to satisfy those constraints, as the violation of a requirement could result in high costs or even threats to human life. Nissan for example had to recall the vehicles of its premium segment cars due to some delays in the emergency program of their new steerby-wire system. Such a problem could have been avoided, if an early analysis on timing constraints would have been performed. Unfortunately, many changes occur during the design process, such that already performed analyses have to be repeated. Our approach targets these problems.

In [START_REF] Gezgin | State-based scheduling analysis for distributed real-time systems[END_REF] we worked out a state-based approach for the analysis of timing properties. In analogy to model checking methods, we consider the full state space, where all task interleavings are preserved. In order to alleviate the problem of state space explosion due to state unfolding, the state space of an architecture is constructed in an iterative manner. Abstraction methods are applied to keep the interfaces between components as small as possible, while composition operations are used to combine a set of triggering sources of a component.

On top of this we worked out an impact analysis approach to minimize revalidation eorts of timing properties needed when the considered system is modied [START_REF] Gezgin | Impact analysis for timing requirements on real-time systems[END_REF]. Adaptations of the architecture of an already existing and analyzed system could be for example the addition of new tasks that are allocated to the existing system. To minimize the eort of a re-validation, it is desirable to reuse the previous results of the analysis that did not change. With this, only the parts are re-validated, which were aected by the architectural changes.

This work is a consecutive extension of our previous work [START_REF] Gezgin | Impact analysis for timing requirements on real-time systems[END_REF]. We illustrate the implementation of the impact analysis. We describe in which cases a renement check can be applied to reduce the re-verication times when changes occur. We evaluate our approach by a set of test systems demonstrating the computation times needed to perform a full timing analysis and the times needed to perform the impact analysis consisting of the loading and storing of state spaces, and the renement check between state spaces. Further, we discuss the benet of applying abstractions of resource interfaces for the renement relation.

Related Work

Timing analysis on distributed systems is a very large research area. Thus, we cover only the most relevant works for our approach. The classical approach is a holistic one, as it was worked out in e. g. [START_REF] Tindell | Holistic schedulability analysis for distributed hard real-time systems[END_REF][START_REF] Gutierrez | On the schedulability analysis for distributed hard real-time systems[END_REF]. Local analysis is performed evaluating xed-point equations. These approaches are very fast and able to handle large systems. Unfortunately, the analytical approaches deliver pessimistic results if inter-ECU task dependencies exist. In [START_REF] Thiele | Embedded software in network processors -models and algorithms[END_REF] activation patterns for tasks are described by upper and lower arrival curves realizing a compositional analysis method. Based on this work a compositional scheduling analysis tool, called SymTA/S, was created by SymtaVision [START_REF] Henia | System level performance analysis -the symta/s approach[END_REF]. The concept has been developed by Richter et al. The main idea behind SymTa/S is to transform event streams whenever needed and to exploit classical scheduling algorithms for local analysis. Another related approach is the modular performance analysis (MPA) [START_REF] Wandeler | Modular Performance Analysis and Interface-Based Design for Embedded Real-Time Systems[END_REF] which is based on a formalism with many similarities to event streams named Real-Time Calculus. Arrival functions are used to model the computation that is requested by a process, and service functions are used to model the amount of computation that can be delivered by a resource. In [START_REF] Lampka | Analytic real-time analysis and timed automata: a hybrid method for analyzing embedded real-time systems[END_REF], the MPA approach has been combined with timed automata while oering methods that allow to transform the model of one formalism to another. CARTS is another tool for compositional real-time scheduling analysis [START_REF] Phan | Carts: A tool for compositional analysis of real-time systems[END_REF]. Schedulability is checked for tasks whose resource usage is bounded by periodic resource models developed by Lee et al. Composition is done on the resource model level resulting again in periodic resource models by using abstractions.

Another approach is based on model-checking: In [START_REF] David | Model-based framework for schedulability analysis using uppaal 4[END_REF] non-preemptive schedulers are modeled in terms of timed automata. The advantage of this approach is that one gets exact solutions with respect to the modeled scheduling problem. Since the state space of the analyzed system is preserved, checking complex properties like safety is possible. Unfortunately, state-based approaches do not scale well. The authors of [START_REF] Hendriks | Timed automata based analysis of embedded system architectures[END_REF] also use timed automata to model preemptive scheduling and verify timing properties by using Uppaal. As a front-end they employ sequence diagrams, from which timed automata are derived. In [START_REF] Perathoner | Inuence of dierent system abstractions on the performance analysis of distributed real-time systems[END_REF] these automaton models were reused and the results were compared to other techniques such as MPA or SymTA/S. In [START_REF] Fersman | Timed automata with asynchronous processes: schedulability and decidability[END_REF] timed automata are extended by clocks which may be subtracted by a natural number to handle preemption in a more natural way. The authors derive a sub-class of this formalism, where the reachability is preserved.

Outline First, we illustrate the considered problem domain. In Section 3 we will detail our general analysis approach in a condensed form. In Section 4 we introduce our implemented impact analysis methodology. Section 5 evaluates our concept and compares plain verication times and renement checking times. Finally, we conclude the work and give an outlook for future work.

Problem Domain

We are interested in safety-critical real-time systems which are typically used in the automotive domain. Typically, the design of the overall system is performed by the original equipment manufacturer (OEM). The OEM designs the software components in form of logical architectures by using, e.g., Autosar software components (SWC), inter-connected by a high level virtual function bus (VFB) like illustrated in the left part of Figure 1. The components and parts of this system are then realized by the suppliers. In order to get adequate realizations from each supplier, the OEM has to specify the extra-functional properties and interfaces unambiguously. This is realized by the usage of so called contracts [START_REF] Benveniste | Multiple viewpoint contract-based specication and design[END_REF]. Contracts are pairs consisting of an assumption (A) and a guarantee (G). The assumption species how the context of the component, i. e. the environment from the point of view of the component, should behave. Only if the assumption holds, then the component will behave as guaranteed. To specify the assumptions and guarantees various formalisms like pattern-based languages could be used. Contracts follow the principle of separation of concerns, i.e., a contract does not just specify a guarantee about the behavior of a component, but also an assumption about the behavior of the environment in which the component will be integrated. If all suppliers deliver the implementations of the SWCs, the OEM has to verify whether all SWCs t together, i.e., he has to perform the consistency check in a black box manner, and whether some higher level requirements ranging over several SWCs are realized by the decomposition structure.

After the implementation of all SWCs the logical architecture has to be allocated to the hardware architecture, consisting of electronic control units (ECUs) which are inter-connected by bus systems. At this design stage technical details such as resource consumptions and timing latencies have to be veried. To perform such analyses, typically the architecture is abstracted in an appropriate manner. The abstraction we perform for our analysis is illustrated in the right part of Figure 1: ECUs and bus systems are treated logically equivalent in the sense that both represent computation units on which a set of tasks are allocated. The order of executions of the tasks is determined by the corresponding scheduling policy like xed priority scheduling. Dependent tasks are directly connected, tasks with no input edges are considered to work independent from other tasks. A task is characterized by a tuple τ = (bcet, wcet, pr), where bcet, wcet ∈ N ≥0 , bcet ≤ wcet, are the best and worst case execution times with respect to the resource the task is allocated to, and pr ∈ N ≥0 is the xed priority of the task. We will refer to the elements of a task by indexing, e.g. bcet τ for task τ . The set of all tasks is called T . Independent tasks are triggered by events of a corresponding event stream (ES). An event stream ES = (p, j) is characterized by a period p and a jitter j with p, j ∈ N ≥ . Such streams can be characterized by upper and lower occurrence curves as introduced in the real-time calculus [START_REF] Thiele | Real-time calculus for scheduling hard real-time systems[END_REF]. In this work we restrict to event streams where j τ < p τ for all τ ∈ T. Like stated above we will further assume that dependent tasks are directly connected. timing information for tasks allocated to the corresponding resource, and endto-end latencies between a set of tasks. In contrast to standard model-checking, our approach does work in an iterative fashion. The interfaces between resources are tried to be kept as minimal as possible. Note that we assume cyclic free systems. Parts of systems with cycles have to be handled in a holistic fashion.

To build the state space of a computation resource, we have to determine its input behavior, which denes the activation times of all allocated tasks. State spaces are represented by symbolic transition systems (STS): the states determine a range of valuations of clock variables, and include the information, which task is currently running, is interrupted, or in the ready queue. A resource can have multiple sources for its inputs: the independent tasks are triggered by event streams, while dependent tasks are triggered when the tasks on which they depend, terminate. Thus, we get multiple input state spaces. To determine a single input state space for each resource, we have to combine all these inputs.

When the input is determined, the next step is to build the state space of the resource itself. For this, the input STS, the behavior of the scheduling policy, and the execution times and priorities of the allocated tasks are taken into account. The approach to compute the state space is illustrated in Fig. 3, where two tasks hp, lp are allocated to a single resource with a xed priority scheduling policy. For each task a clock c p which traces the periodic activation is needed. Further, we need a clock c c to determine when a task is nished. If we are interested in the exact response times of a task instance, we need multiple clocks c r , one for each instance of a task.

The computed state space of a resource is then used as an input for dependent resources, i. e. for resources on which dependent tasks are allocated. To keep the interface between the resources as small as possible, parts of the state space that are not relevant for the input behavior of the dependent resources are abstracted.

Consider the example in Fig. 2, which consists of three resources where on each resource two tasks are allocated. The tasks task5 and task6 on resource Resource3 depend on task2 on resource Resource1 and task3 on resource Resource2 respectively. Tasks task1,...,task4 are activated by event streams, thus the inputs for both Resource1 and Resource2 are directly given and their state spaces can be computed (illustrated in the left part of the gure). Next, the input of Resource3 has to be determined, which depends on both the state space of Resource1 and Resource2. As timing information for the tasks task1 and task4 is not relevant for Resource3, the corresponding STSs can be reduced by abstracting from states encapsulating information about these tasks. After this minimization, the product of both STSs is computed (indicated by the right part of the gure).

The details of our timing analysis including the composition operation, the minimization, and the resource construction can be found in [START_REF] Gezgin | State-based scheduling analysis for distributed real-time systems[END_REF]. [START_REF] Gutierrez | On the schedulability analysis for distributed hard real-time systems[END_REF] Impact Analysis Methodology

During the design process changes aecting the architecture of a system occur, such as adding a new task on an existing resource, the merge of two tasks in a single one, or even the change of the complete implementation. If such changes occur, already performed analyses have to be repeated, increasing the time needed to verify the functionality and properties of the design, and thus increasing the time to market.

To minimize the eort of a re-validation, it is desirable to reuse the previous results of the analysis that did not change. With this, only the parts are revalidated, which were aected by the architectural changes. It is required to perform an impact analysis, when changing or maintaining software because it allows to judge the amount of work required to implement a change, proposes software artifacts which should be changed, and helps to identify test cases which should be re-executed to ensure that the change was implemented correctly [START_REF] Lehnert | A review of software change impact analysis[END_REF].

As our timing analysis approach works in an iterative manner (and not holistically), we are able to determine whether the interface of dependent resources is aected through the concept of our renement analysis: we are able to check if the new interface between dependent resources renes the old interface. In such a case a re-validation of dependent resources can be omitted. The denition of an appropriate renement relation was the topic of our previous work [START_REF] Gezgin | Impact analysis for timing requirements on real-time systems[END_REF].

In the next section, we illustrate our implementation approach of the impact analysis. We demonstrate in which cases a complete re-verication of a component is necessary, in which cases a renement check is performed, and when verication steps can be omitted. Thereafter we discuss the advantages of our approach when using further abstraction techniques on the interfaces of resources.

Concept

The concept of the implementation of our impact analysis is illustrated in Figure 8 in terms of an UML activity diagram.

Each resource has a status ag for its resource state space called outputIs-Consistent, initially set to false. The idea of this ag is to inform dependent resources whether some non-renement changes concerning the resource state space occurred (and thus the resource state space has to be recomputed).

First, it is checked whether some inputs of the resource has changed (check-InputStatus). If changes occurred, the check evaluates to false and the input STS (computeInputSTS ) followed by the computation of the resource state space itself (computeResourceSTS )is performed as usual. As the resource STS is newly computed, the ag outputIsConsistent is set to false to signalize dependent resources that this input has changed. Last, the resource STS is stored appropriately. If on the other hand the output STSs of all resources, from which the current resource depends on, did not change, checkInputStatus evaluates to true. Then it is checked whether an already computed resource STS of this resource exists (from previous verication steps, where the resource STS was saved). If not, it has to be computed as described above. Else, it is checked whether structural changes have occurred, i.e. changes concerning the scheduling policy of the resource, the number of allocated tasks and their properties like priorities and execution times. If these properties did not change, the resource STS will also be not aected. Thus, the existing STS can be restored (loaded from le system).

The ag outputIsConsistent is set to true indicating that nothing changed on the output.

If else some changes on the resource occurred checkInputStatus will evaluate to false. In this case, we have to re-compute the resource STS, load the previously computed resource STS and do a renement check between both STSs.

If the renement check evaluates to true, outputIsConsistent is also set to true indicating that the resource STS changed in a good manner. Else it is set to false. Note that before the re-computation of the resource STS the input STS of the resource has also to be re-computed because if properties of independent tasks change the input STS is also aected.

Combination with Abstractions

Generally an impact analysis is useful in combination with analysis techniques that involve abstractions. This is also a typical scenario for analytic techniques such as in [START_REF] Richter | Scheduling Analysis Integration for Heterogeneous Multiprocessor SoC[END_REF]. These techniques are based on the assumption that every interface behavior can be characterized by event streams. To obtain event streams for the outputs of a resource, the actual task behavior is generally over-approximated. Hence changes in the behavior of a particular resource might indeed have an impact on the already computed exact state-space representing its output behavior, but might not have an impact on the over-approximated output behavior of the resource. This can be exploited by our impact analysis. We consider event streams as the maximal abstraction of the timing behavior of a task, as these only contain information about best-and worst-case responsetimes, without any information, in which cases the corresponding response times occurs. For example a task could have a large response time when it is interrupted by an high priority task which is allocated on the same resource, and an small response time, when no interrupts occur.

Though our analysis approach is an exact analysis in general, it can be combined with abstraction techniques in order to reduce the state space of the interface transition systems. Such abstractions were the topic of our previous works [START_REF] Gezgin | Evaluation of a state-based real-time scheduling analysis technique[END_REF].

An abstraction indeed might aect the schedulability of a depending resource, and hence may cause false negative results. On the other hand, suitable abstraction techniques may pave the way to omit re-validations. [START_REF] Thiele | Embedded software in network processors -models and algorithms[END_REF] Evaluation

In this chapter we will evaluate our methodology by the usage of the three test systems illustrated in Figure 4. Tasks with no input edge are considered as to be independent, i.e. triggered by event streams. The scheduling policies of each ECU is xed priority with interruption, and the policy of the CAN bus is also xed priority but (of course) without interruption. The parameters of the tasks are detailed in the table of Figure 5, where p is the period of a task, ecec. is the execution time which may be a single value or an interval, if bcet = wcet, and pr is the priority of a task.

In our evaluation we compare the time needed for an analysis of each resource and the times needed to store and load a corresponding state space, and check the renement of the state spaces of the resources. The idea is to demonstrate that the analyses times of the resources is always much larger than the times needed to store and to load the state spaces, and to check whether if a change occurred the old state space is a renement of the new one.

Note that all times were measured on the same machine to preserve comparability. Each check has been performed ve times. The times illustrated here are the average times of all measurements.

The measured times are illustrated in the table of Figure 6. As an example: To analyze the timings of ECU 2 of System2 we need 6, 75 seconds. In contrast to this, the renement check of the of state spaces (new and old) of ECU 2 only takes 0, 015 seconds. The cell Sum is the sum of the cells Renement, Load and Store and is used to compare the times needed to perform these three steps against the plain verication time.

As an example we illustrated some cases graphically in Figure 7.

The result of our evaluation is that the larger the state space of a resource is (and therefore the verication time of that resource), the larger the dierence between the verication time and the computation times needed to load, save, and check the renement of the old and new state spaces is. Thus, for larger systems our renement methodology is a real gain for our analysis approach. Note that of course, if the renement check fails, i.e. the new state space of a resource is not a renement, than we have extra analysis times which we would not have if we always perform the plain verication directly. But fortunately these renement checking times are not that large. Actually the complexity of the renement check is n(n -1) where n is the number of states.

Conclusion and Outlook

We illustrated the implementation of our impact analysis approach which is applied when architectural changes occur during the design state of a system. We evaluated our approach by measuring the computation times needed to perform the full verication, the storage and load of state spaces, and the computation of the renement check, and compared these times. The result is that for larger systems our renement methodology is a real gain for our analysis approach. Currently, we investigate new abstraction techniques which will yield more accurate results than the classical analysis techniques and will boost the scalability of our approach.

Fig. 1 .

 1 Fig. 1. General concept of modeling and analysis.

Fig. 2 .

 2 Fig. 2. Timing analysis approach; Left: Computation of resource state spaces; Right: Computation of output interfaces.hp lp

Fig. 3 .

 3 Fig. 3. Two tasks hp, lp and the interrupt scenarios. The clocks refer to the task lp. Clocks in curved brackets indicate a reset, P is the period of lp.

Fig. 4 .

 4 Fig. 4. Test systems.

Fig. 5 .

 5 Fig. 5. Task parameters.

Fig. 6 .

 6 Fig. 6. Measured average computation times.

Fig. 7 .

 7 Fig. 7. Computation times for a) ECU 1 in System1 (left), b) ECU 2 on System2 (center), and c) ECU 3 on System3.

Fig. 8 .

 8 Fig. 8. Methodology of the Impact Analysis (timing analysis combined with renement check).

State-based Timing AnalysisOur timing analysis approach is based on model-checking. For each computation resource its state space is computed. Such a state space encapsulates the relevant