Simon Schliecker
email: schliecker@symtavision.com

Jonas Diemer
email: diemer@symtavision.com

Kai Richter
email: richter@symtavision.com

What's the Bus Load? Real-Time Metrics for Automotive Ethernet Networks

Keywords: Automotive Ethernet, Real-Time, Architecture Design, Tools

Ethernet is the emerging technology for automotive networking. With data rates of 1GBit/s and more, Ethernet can enable new car functions and services. Leading car manufacturers and system suppliers have started introducing Ethernet to cars for advanced driver assistance systems (ADAS) like object tracking and surround-view, and they added connectivity of consumer devices such as phones, music players, etc.. Currently, car manufacturers world-wide assess new concepts that let us use a single switched Ethernet network for streaming, connectivity, and control data at the same time, with the (technical) potential of replacing CAN and FlexRay in all domains some day. This introduction of Ethernet into the existing CAN/FlexRay/MOST-dominated E/E architectures creates obvious new challenges. One top-priority requirement is the early analyzability of their real-time capability. This comes as no surprise as analyzing the real-time performance of CAN and FlexRay is a standard step in network design today. It tells us upfront, whether a planned network configuration will satisfy the real-time requirements (using metrics such as bus load, signal latency, etc.); and it points us to bottlenecks so we can fix them in early design phases. The whole aspect of "realtime" has become a must-have in network design within the last 5 years.

In this paper, we present different load and latency metrics for assessing real-time metrics for automotive Ethernet networks, and we demonstrate how these metrics help optimizing Ethernet configurations on a representative use case.

Introduction to Established Real-Time Metrics

Ethernet is (compared to CAN and FlexRay) "ultra fast" with up to 1GBit/s (and maybe even more in the future). But speed alone is not enough. Whenever (some of the) data is subject to timing constraints, we must be able to assess the network's genuine, core real-time properties in order to reliably avoid timing-related problems later in the field. These requirements can be very different. Video data is typically bandwidthsensitive, audio data is jitter-sensitive and control data is latency-sensitive. Because of this mixture, Ethernet timing assessments will be even more complex than in CAN/FlexRay-based networks, so we need real-time analysis even more. We therefore we focus on Ethernet networks for mixed, heterogeneous data incl. video and audio but also control data (for which today CAN, FR, LIN are used). In contrast, pure video stream transmission has other, significantly less complex real-time requirements, and appropriate standards exist already (e.g. MOST). Therefore, we do not include MOST in out considerations as it is unlikely that MOST will be used for mixed transmission of video and control data in the future. However, it should be noted that the metrics can be applied to any other network technology.

Knowing (forecasting) the real-time properties early has become a necessity for network design. Thus, we must have a minimum of knowledge about the timing behavior of the messages. Measuring the behavior on a real system is usually not possible at an early design stage. So we must rely on other methodologies like simulation and model-based timing analysis for which we need a timing model of our bus or network. For automotive Ethernet, these methods are available (e.g. [START_REF] Diemer | Formal Worst-Case Timing Analysis of Ethernet Topologies with Strict-Priority and AVB Switching[END_REF], [START_REF] Thiele | Formal Worst-Case Timing Analysis of Weighted Round Robin Scheduling for Ethernet[END_REF]) and accessible in tools (e.g. [10]). These methodologies are already in use by automotive OEMs like VW [START_REF] Stein | Ethernet Quality of Service @ Volkswagen[END_REF], BMW [START_REF] Gunnarsson | Trends and New Challenges In Automotive E/E Architectures[END_REF], and Daimler [6] and also industrial users [7]. Thus, timing data can be obtained efficiently for varying use cases and system configurations.

Once the timing data is available, it has to be interpreted. For this, metrics are required that condense the relevant information into an easily graspable format. In the domain of CAN and FlexRay networks, the bus load is the most prominently used metric. It captures the used bandwidth, in percentage of a certain observation interval. This value is used to highlight changes in workload of a bus over different releases, to find a good segmentation of a new network, and sometimes -with the known and accepted limitations -even assess whether the architecture can be trusted to work correctly in the field. The bus load is a very rough performance indicator with many limitations. The bus load alone cannot tell us if any particular message will exhibit a certain timing problem. To assess this, other metrics can be used:

 the response time is the "effective latency" of a message, measured from the point in time that the message is generated (in COM layer) until it is fully transmitted over the bus  the jitter is (roughly speaking) the variation in the response time of messages of the same CAN Id, i.e. variations in their "observable cycle time".

These metrics represent genuine, core real-time properties of individual messages, rather than just the network as a whole. These metrics are applied in mostly every reasonable bus timing assessment of CAN and FlexRay buses. Based on core metrics, a set of advanced metrics can be established:

 the end-to-end latency. This metric extends the message response time concept to include elements like gateways or end-point COM layer or application delays (on sender and receiver side)  the slack. This metric provides the remaining time between the latency of a signal and the timing requirements mandated by its function (i.e. the signal's deadline). It allows easily identifying where in the network headroom exists.

These (and many more) metrics can be derived by measurement, simulation or formal analysis, which are available in commercial tools as [10].

In this paper, we will not explain the details of any analysis, Rather, we summarizes our experience with applying such real-time metrics in network design practice. We illustrate examples and indicate guidelines for exploiting timing data using the popular metrics from a network design practitioner's perspective.

The rest of the paper is organized as follows: In Section 2, we introduce the network timing model that allows the derivation of timing data. We present Ethernet timing metrics in Section 0, along with an example use case to which we apply the metrics. In Section 4, we discuss how the metrics can be used to optimize the network design, before we conclude in Section 5.

ECU

Network Timing Model

The network timing model provides us with basic data to be able to forecast the metrics that we have just mentioned. The timing model captures the essence, the core of the timing behavior.

Actually, a timing model must answer four questions:

1. How many messages (more general: "time consumers") do we have? 2. How often does each one arrive? 3. How much time does it consume then, when it arrives? 4. How will collisions be resolved, when more than one arrives at a time?

While there can also be other important information, these four questions are the most relevant ones. If we look at CAN networks, we find all information in the core network configuration. Everything is there, the list of frames and signals (question 1), the cycle times (question 2), their data length (question 3), and their CAN ID (question 4). Based on this information (plus the option of adding more dynamic information), in-depth assessments can be done manually or automatically by so called scheduling analysis tools. In other words, such tools take the timing model as input and generate the metrics as output.

We will not go into any details of CAN here, but we want to illustrate the importance of a timing model that allows answering four simple but essential questions. If one of them cannot be answered, we will not be able to determine even the core, genuine timing properties of our network systems. Without a timing model, we cannot apply real-time metrics; and without such metrics, over-engineering the entire network is the only solution -which is a very risky and costly work-around.

What about Ethernet?

The four questions help us remembering what "really counts" in terms of the real-time behavior.

While the fundamental approach is essentially the same as for CAN, LIN or FlexRay analysis, such a standard procedure is not yet established for Ethernet-based networks for automotive applications. In order to understand the situation fully, we will now look into a few details of Ethernet networks (for further details, see [START_REF] Thiele | Cooperating on Real-Time Capable Ethernet Architecture in Vehicles[END_REF]). In particular, we will point to two specific differences to CAN (and FlexRay) networks: collisions and message sizes.

Collisions

CAN and FlexRay are based on the use of a shared communication medium. All connected nodes listen to the bus and broadcast their messages according to a predefined arbitration scheme (or schedule). CAN arbitration is based on priorities (the CAN IDs), FlexRay schedules rely on fixed time slots in the static segment and mini-slots in the dynamic segment. On switched Ethernet, there is no such shared medium. Each node has full control over its outgoing Ethernet links. These links are private (and typically full duplex), not shared. This means that there is no collision and no arbitration on the medium (link) itself; a fundamental difference to CAN or FlexRay. But does that mean there are no collisions (remember question 4)? Not at all! In fact, the collisions appear in the switches; more precisely in the outgoing links from the switches to the end nodes (or to other switches), when two or more messages (or streams) target the same receiver, which can be an end node ECU or another switch.

Figure 1 illustrates the collision scenarios in CAN and Ethernet. On CAN, all messages can potentially collide with each other because they use the same shared medium. In the corresponding Ethernet network, messages can VLAN (IEEE 802.1q) adds a priority scheme to the switching rules (with FIFO-scheduling within each priority level). The good news is that VLAN switches behave deterministic in their way of resolving collisions by a standardized scheduling based on priorities. On the downside, there are only 8 priority levels (3 bits), which significantly limit their use for adjusting the switch configuration to the specific timing requirements at hand. As a comparison: CAN defines up to 29 priority bits (resulting in over 500 million priority levels), and FlexRay cycles can be configured with literally countless slots.

With only prioritization, there is a risk that high priority traffic consumes all bandwidth, leading to long buffering times of lower-priority traffic. Ethernet AVB [9] extends the VLAN priority scheme by shaping capabilities. This allows allocating a certain bandwidth for real-time traffic (the higher priorities) while still guaranteeing that also non-real-time traffic will get through.

Message Sizes and Layers

The second major difference between CAN/FlexRay and Ethernet is the payload size and the layering concept. CAN offers at most 8 bytes, FlexRay 254 bytes, and Ethernet 1500 bytes (MAC frame) and 64kB for a UDP packet. Also the protocol overhead is significant. While it is roughly 8 byte on CAN, it can be 30 byte on Ethernet UDP frames. This is of particular importance when we start including control data (which typically consists of few bits up to bytes) into the Ethernet network. Just as an example: if we turn each CAN frame into exactly one Ethernet frame, then we will triple the network load (8+8 byte vs. 8+8+30 byte) and also cause additional load for packing and unpacking at the sender and receiver. In this situation, multiplexing appears as a reasonable solution. Several proposals have been made: A simpler one that relies on a static frame layout, similar to what is established in CAN and FlexRay today. And a second one that adds another ISO-OSI layer on top of the UDP/TCP protocol, called SomeIP. This was originally proposed by BMW and is now made publicly available as part of the AUTOSAR specification.

New Metrics for Ethernet

In this section, we present the metrics along with an example use case. Figure 2 shows the example use case, which is created based on experience with different realworld applications and contains many aspects of such real-world use cases. The example network consists of three switches with multiple ECUs. In particular, there are four Cameras connected to one of the switches that stream video to a vision ECU for processing. The system contains over 60 messages including low-bandwidth, regular control traffic, audio, video and best-effort traffic. The total injected bandwidth amounts to over 330Mbit/s. Of course, we cannot provide detailed insight into a specific customer system, but the key properties in this example match the realworld situations quite well.

Load Metrics

In order to assess the utilization of a given network configuration, one can take a look at the share of time that the network is actually "used" by a function for communication of data. In traditional, e.g. CAN-based networks, this is represented by the bus load, which can easily be observed by measurement in the field, or also be derived based on models of the workload (i.e. which frames are sent how often). But this metric does not apply to typical Ethernet configurations that consist of multiple links and switches, each of which will exhibit different (local) load situations (see above).

To be able to derive similar metrics for multi-hop networks, we will therefore revisit the relevant definition of workload and use together with a description of the topology and resources in order to reason about the network's overall utilization.

The basic value to quantification the workload that a network is expected to handle is the data rate per data stream: A data stream represents a logical end-to-end communication between two ECUs, and its data rate is the average amount of data sent in a given time interval. Typical values range from a few bits per second (e.g. for low priority status messages) to some 100 Bytes per second (e.g. for control function data sent in some Byte every 10 ms) up to several Megabytes per second (e.g. for video streams). An overview over all data rates imposed on the system provides an important overview over the "resource consumers" in the system. In case of any timing bottlenecks, this can guide the engineer to focus on the data intensive functions first.

By combining the data rate per stream with the information about the sending and receiving ECUs, the aggregate point-to-point data rate can be easily computed. It represents the amount of data that is exchanges between two end nodes (ECUs) of the system. This metric is important for designing an appropriate network topology, in which heavily communicating ECUs (or other networking segments) should be located relatively close to each other. Figure 3 depicts the aggregate point-to-point data rate on a logarithmic scale for the example network. One can see that the most data in this system is produced by the four cameras (CAM 1,2,3,4). In addition, there are some broadcast messages sent by the central gateway ECU (likely status messages from the other network segments). Finally, there is some heterogeneous point-to-point communication between a small number of other ECUs. Figure 4 shows the same data in a graph representation that allows an easier identification of the significant communication partners. The workload information above can be put into relation to the actual network configuration, i.e. the topology, routing information, and link speeds, in order to compute the actual aggregate load on per port 1 . This provides a top level view on the utilization of the system, and allows pinpointing hot spots (heavily loaded ports), but also reserves for possible function extensions. Every data stream that passes over a number of hops in the network will be influenced by the conflicting traffic at each hop. The higher the load at a certain port, the higher the potential impact (delay). Thus, for each endto-end communication, the port with the highest 1 We prefer the term "port load" over "link load", because links in switched Ethernet networks are typically full-duplex, and the "port" allows to indicate the direction.

load indicates the amount of potential distortions that a certain stream can experience. This leads to the squeeze load diagram: it is the maximum load of any port that a data stream passes over on its way from sender to receiver ECU. Figure 5 shows the squeeze load for the example system. It can be seen, that quite a few communication partners observe a squeeze load of around 22%. The highest squeeze load is observed by streams going to the vision ECU, which amounts to about 28%.

Latency Metrics

While the load-based metrics introduced above allow identifying the utilization of systems, they actually provide little information about the realtime capability. It is a known fact from CAN design that even on a lowly loaded bus, messages may not be received in time if the deadline is short. To investigate this, one must be able to reason about message latencies in the system. Furthermore, we assume that the timing constraints imposed by the functions have been broken down to timing constraints for individual messages.

The end-to-end latency represents the delay between the injection of a message to the network from the end-node and the reception of that message at the destination end-node, including all intermediate delays at the ports and switches and of course the transmission times themselves. These latencies can be directly compared to the timing constraints as imposed by the function, i.e. the deadline. This allows assessing the quality of a certain transmission for the function level. The same information is considered by the relative latency, which puts the end-to-end latency in relation to the messages deadline for easier identification of critical messages. For example, a message with a latency of 3ms and a deadline of 100ms has a relative latency of 3%. If the same message had a deadline of 5ms, its relative latency would be 60%, which can be perceived as much more critical. Another similar comparative view is the message slack that is defined by the difference between the deadline and the latency. A small or even negative slack indicates that the timely transmission of this message is jeopardized.

Figure 6 shows the relative latencies of all messages in the example system. For three message (highlighted), the relative latency is larger than 100% (1.0), thus they can likely not be communicated in time. This relative view is gaining importance, because it shows in one chart which messages are critical and which are not. As a summary of this view for evaluation of a complete configuration, one can even condense this chart into a relative latency histogram (Figure 3). This shows the total amount of messages that are "safe", e.g. because their relative latency is smaller than e.g. 0.4, and those that may cause trouble during runtime, because the relative latency is close to or beyond 1.

Maximum Relative Latency

The above metrics are well suited to provide an overview over the system behavior, timing quality, and timing reserves and pinpoint the source of problems. They do however not maintain the simplicity of the established bus load metric. In order have a comparable metric that also represents the timing quality, the information needs to be further condensed.

From perspective of real-time system, the most outstanding aspect of the above considerations is the maximum relative latency (MRL), which expresses the maximum ratio between the endto-end latency and the deadline over all messages (at least for those that have a deadline). The interpretation of the MRL is relatively simple:

 If MRL > 1 then there is a timing problem for at least one message.  If MRL < 1 then one can assume that all timing critical messages are transmitted in time.  If MRL is much smaller than 1 then the system is generously dimensioned, maybe one can take a more detailed look in order to save some resources.

Of course, the MRL can also be computed for different service classes separately. For example, demanding an MRL < 1 may be required only for the safety critical messages, while higher values are tolerated for other streams. Obviously, the MRL in the example is 2.5.

Applying the Metrics for Network Optimization

While load-based metrics only provide a rough indication about the system timing and resource utilization, the latency-based metrics provide sound information about the timing quality of a network implementation. Using the relative latency and the message data rates, one can now easily identify the critical messages, and which messages should be reconsidered to improve the design. We can quickly demonstrate this using the above example. To improve the design and its timing quality, we had to reduce the latencies of some messages significantly. The lat ency diagrams helped us identifying the most critical messages quickly.

For the corresponding traffic, we have elevated the VLAN priority (and we required the switch to provide 802.1q VLAN capabilities). This way, we could reduce the latency of critical communication significantly, below the given deadlines. The drawback is of course that other messages may be negatively impacted by this reprioritization. Thus, we executed another timing analysis to see, if the overall system timing was improved by this decision. In our example, there was no negative impact on any other stream (see Figure 8). The optimized system now has an MRL of 0.9 (down from 2.5 originally) and can now be considered sufficiently dimensioned.

We can generalize this way of assessment and optimization into few key steps: On important aspect is the availability of tools that automate as much of this procedure as possible. Without such tools, it will be an academic exercise for timing experts only. With efficient tooling, we can apply the procedure in an industry environment with network designers that have only basic knowledge in timing issues.

Conclusion

Ethernet is about to become the key automotive communication (backbone) technology for the next decades with heterogeneous, mixed traffic including audio, video and control data. One of the top-priority requirements for the broad introduction of Ethernet in vehicles is the early analyzability of the real-time capability of a given Ethernet configuration (and its optimization). In the very near future (at some OEMs already now), Ethernet is transitioning from the research departments into the pre-series developments departments with strong maturity requirements on methods, processes and tools, including timing analysis.

In this paper, we have presented different load and latency metrics for assessing real-time properties for automotive Ethernet networks, and we have demonstrated how these metrics help optimizing Ethernet configurations on a representative use case. We have sketched out a generalized assessment procedure that is used today already by large automotive OEMs such as BMW, Daimler, Volkswagen and others. All these OEMs report that one key step for effective and efficient network timing design is the availability of clear metrics, be it for CAN, FlexRay, Lin, and now Ethernet.

Figure 2 .

 2 Figure 2. Topology of the Example Use Case

Figure 3 .Figure 4 .

 34 Figure 3. Aggregate point-to-point data rate for the example Ethernet system

Figure 5 .

 5 Figure 5. Squeeze load for the example system

Figure 7 .

 7 Figure 7. Relative latency histogram

Figure 1 Collisions on CAN and Ethernet networks only

  collide when they have the same receiver and go through the same outgoing port of a switch.

	The actual arbitration happens inside the
	switches. The switches include buffers to store
	messages during collision periods and transmit
	them later. And they are responsible for selecting
	which one to transmit. In order to answer
	question 4, we need to understand how this
	storing and selecting works. Interestingly, the
	Ethernet standard IEEE 802.3 does not define
	any specific rules for the switches. Just as a
	comparison: CAN and FlexRay define an
	arbitration scheme at the core of the standard,
	while Ethernet does not. This means that each
	standard switch manufacturer can freely choose
	an arbitration rule set, which might not even be
	documented publicly. This renders standard
	Ethernet	unusable	reliable	real-time
	communication, simply because it is unclear
	what happens in the event of collisions.
	Real-time capable extensions to standard
	Ethernet (with downwards compatibility) have
	been proposed including VLAN (IEEE 802.1q),
	AVB (IEEE 802.1AS, 802.1Qat, 802.1Qav, and
	801.2BA). Other solutions (proprietary and/or
	without downwards-compatibility) include ARINC
	664 (known as AFDX), TTEthernet (from
	TTTech), Ethercat and others, see e.g. [1]. For
	cost and interconnectivity reasons, the
	automotive industry seeks a downward-
	compatible solution which offers (a minimum of)
	real-time predictability, with VLAN and AVB
	being candidates under investigation.

[6] Streichert, T., Seyler, J. , Schuhmacher, P., Brendle, R.


Johan Eriksson
email: johan.eriksson@ltu.se

Simon Aittamaa
email: simon.aittamaa@ltu.se

Per Lindgren
email: per.lindgren@ltu.se

Refined SRP Stack Memory Analysis by Exploiting Critical Sections for Shared Resources

Embedded (real-time) systems often operate on platforms with limited memory resources. In particular, the size of the random access memory (RAM) may be a limiting factor. Scheduling under the Stack Resource Policy offers (among other benefits) single stack execution, which reduces the memory requirement in cases where shared resources limits potential preemptions.

In this paper we refine previous results on stack memory analysis for SRP based systems. For a task J we associate the section of code in between a resource request and release of R to a sub-task J R . If J R is implemented as a function, the stack usage of J R can be accounted for locally (and not part of the initial allocation for J as done in previously published work.)

The proposed method has been been implemented and evaluated on a set of synthetic benchmarks. Our experiments show a clear impact of per sub-task stack allocation to reducing stack memory requirement. The proposed stack memory analyzer makes no approximations, still run-time is shown to be in the range of 1 minute, for 50 tasks and 250 subtasks. At the same time the accuracy of our method is improved in comparison to previous work.

Introduction

Embedded systems often operate under both timing and resource constraints. Tasks (activities) in such systems are typically concurrent, triggered by some event (emitted by the environment, e.g. a hardware timer, or raised internally). Preemptive scheduling may improve responsiveness for such systems [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]. Preemption amounts to storing the context of the preempted task and restoring (or creating) the context of the task to execute. A common abstraction is to associate each task to a thread, with a pre-allocated memory region for the execution stack [START_REF] Barry | FreeRTOS reference manual: API functions and configuration options[END_REF]. The total stack space usage is simply calculated from the sum of the (maximum) stack usage for each thread. Context switches can be done in arbitrary order (which allows for full flexibility for scheduling).

However, by limiting/restricting the flexibility of the scheduler (and refining the analysis), the assessed (worst case) stack memory usage can be reduced.

An alternative approach for preemptive execution of task sets with shared resources is offered by the Stack Resource Policy (SRP) [START_REF] Baker | A stack-based resource allocation policy for realtime processes[END_REF], under which tasks (or jobs) execute on a single stack. Hence, using SRP stack space for individual jobs do not need to be pre-allocated. The total amount of memory required will be less or equal to that of a thread based equivalent, and may in the presence of shared resources be significantly lower. SRP imposes the restriction that tasks/threads may never run preemptively w.r.t to each other if assigned the same priority, and that a task A will never preempt another task B that holds a resource that would force A to wait until B releases the resource (i.e, a task, when executing, will be able to finish without having to wait for any other task).

Recent work [START_REF] Hänninen | Analysing stack usage in preemptive shared stack systems[END_REF] incorporate job offsets (temporal dependencies) in the analysis to improve the precision (taking only the feasible set of preemptions into account) when assessing the worst case stack depth. The work of [START_REF] Hänninen | Analysing stack usage in preemptive shared stack systems[END_REF] includes an approximative algorithm, speeding up calculations, such to allow larger task-sets to be analysed.

In this paper we further refine the results on offset analysis by considering stack usage on a per sub-task basis (extending the per task basis analysis of [START_REF] Hänninen | Analysing stack usage in preemptive shared stack systems[END_REF].) For a task J we associate the section of code in between a resource request and release of R to a sub-task J R , which in turn may contain a hierarchy of sub-tasks. If J R is implemented as a function, the stack usage of J R can be accounted for locally. As an sub-task J R , holding the resource R is only subject to a subset of possible pre-emptions for an outer task, the maximum required stack space will be reduced (in comparison to considering the stack space for a task J where all J R s are inlined).

The (potential) impact of the proposed method is evaluated on a set of synthetically generated test cases. The experiments show that significant reductions can be obtained by accounting for stack usage on per sub-task basis compared to per task basis previously presented. Furthermore, on another set of experiments we showcase the exponentially growing execution time (measured in number of iterations) when varying the number of tasks. Despite the complexity, our experiments validate the feasibility the proposed method. Our experimental implementation uses about a minute run-time on a 3GHz core 2 duo (single threaded implementation) to calculate stack depth of 50 main tasks with a total number of 250 sub-tasks, which in practise suffices for many embedded applications.

In order to reduce the execution time, we deploy a simple cache scheme. Even with only two cached results for each task, the execution time (number of iterations) is reduced by a factor of more than 20. Notice, while caching reduces execution time in practise, the exponential complexity still remains. In contrast to [START_REF] Hänninen | Analysing stack usage in preemptive shared stack systems[END_REF] the proposed method does not introduce any internal approximations,

i.e. it gives the exact solution for the given input. However, for larger task-sets an exact approach becomes computationally intractable and approximative solutions may be developed for assessing stack depth on basis of subtasks and is a set topic for future work.

Formal System Model

As a basis, we use the formal system model with static offsets [START_REF] Tindell | Using Offset Information to Analyse Static Priority Pre-emptively Scheduled Task Sets[END_REF], where we have k transactions, each Γ i activated with a minimum inter-arrival time T i , and consists of |Γ i | number of tasks, where each task is define by a tuple where, C denotes the execution time, O the offset for release (relative to the release of the transaction), D its relative deadline, J maximum jitter, B maximum blocking from lower priority tasks, P priority, and S its stack usage.

Γ := { Γ 1 , T 1 , . . . , Γ k , T k } Γ i := {τ i1 , . . . , τ i|Γi| } τ ij := C ij , O ij , D ij , J ij , B ij , P ij , S ij (1)
We assume the same restrictions as in [START_REF] Tindell | Using Offset Information to Analyse Static Priority Pre-emptively Scheduled Task Sets[END_REF] unless else stated (e.g., the task set is scheduleable).

In this model, the stack usage is defined on a per-task basis. We refine each task to consist of a main task and set of sub-tasks (associated with a local stack space and resource) in a hierarchical manner. This model goes hand in hand with the task model defined by Baker for the Stack Resource Policy [START_REF] Baker | A stack-based resource allocation policy for realtime processes[END_REF]. We assume single unit resources, and define the preemption level equal to the priority. We statically compute the (current) resource ceilings as described in [START_REF] Eriksson | Real-Time For the Masses, Step 1: Programming API and Static Priority SRP Kernel Primitives[END_REF]. We define our tasks with sub-tasks as:

τ ij[x] := C ij , O ij , D ij , J ij , B ij , P R ij[x] , S ij[x] , sub ij[x]
(2)

sub ij[x] := {τ ij[x,1] , . . . , τ ij[x,m] } (3)
E.g., the definitions

τ a[] := Ca, Oa, Da, Ja, Ba, P R a[] , S a[] , sub a[] sub a[] := {τ a[1] , τ a[2] } τ a[1] := C a[1] , O a[1] , D a[1] , Ja, Ba, P R a[1] , S a[1] , sub a[1] τ a[2] := C a[2] , O a[2] , D a[1] , Ja, Ba, P R a[2] , S a[2] , {} sub a[1] := {τ a[1,1] , τ a[1,2] } τ a[1,1] := C a[1,1] , O a[1,1] , D a[1,1] , Ja, Ba, P R a[1,1] , S a[1,1] , {} τ a[1,2] := C a[1,2] , O a[1,2] , D a[1,2] , Ja, Ba, P R a[1,2] , S a[1,2] , {} S a[] := 16 P R a[] := P a[] = 1 S a[1] := 24 P R a[1] := r1 = 2 S a[2] := 20 P R a[2] := r2 = 3 S a[1,1] := 32 P R a[1,1] := r3 = 4 S a[1,2] := 8 P R [1,2] := r2 = 3 (4)
In the example τ a , has the base priority 1, and hence pre-emption level 1 (P R a[] = 1). The task has two immediate sub-tasks {τ a [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] , τ a [START_REF] Barry | FreeRTOS reference manual: API functions and configuration options[END_REF] }, where τ a [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] holds the resource r 1 for the duration C a [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] . As τ a [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] is a sub-task, release jitter and blocking are inherited from the parent task J a . Deadline and offset can be calculated using information from the list of sub-tasks and the parent task. An approximation is obtained by simply inheriting the parents execution window. A refinement of the deadline

D a[1] = D a -C a[2]
, takes the execution time of subsequent sub-tasks into account, similarly a refinement of the offset O a [START_REF] Barry | FreeRTOS reference manual: API functions and configuration options[END_REF] = O a + C a [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] , takes the execution time of preceding sub-tasks into account. Further refinements may be possible but is not scope for the presented work.

The (sub) task τ a [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] in turn consists of two sub-tasks {τ a [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF][START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] , τ a[1,2] }, holding the resources r 3 and r 2 , giving pre-emptions levels P R a[1,1] = 4, and P R a[1,2] = 3 respectively. Deadlines and offsets are derived as described above.

Preemption criteria

Our method builds on the job admission criteria from Baker [START_REF] Baker | A stack-based resource allocation policy for realtime processes[END_REF], and can be formulated as an extension of equation 6 in [START_REF] Hänninen | Analysing stack usage in preemptive shared stack systems[END_REF]. We define W ijx as the scheduling window for a (sub) task τ ijx , where start(W ijx ) and end(W ijx ) gives the bounding (integer) values relative to the release of Γ i . Basic computations for start and end are given in [START_REF] Eriksson | Srp-dm scheduling of componentbased embedded real-time software[END_REF], but may be further improved on by utilising the refined deadlines and offsets as discussed above.

The preemption criteria is defined in [START_REF] Tindell | Using Offset Information to Analyse Static Priority Pre-emptively Scheduled Task Sets[END_REF].

τtix ≺ τtiy ≡ τtiy ∈ subtix τtix ≺ τ tj[] ≡ (start(Wtix) < start(W tj[] ) < end(Wtix) ∧ P Rtix < P R tj[] ) τtix ≺ τ uj[] ≡ P Rtix < P R uj[] (5)
E.g., in Equation 4, τ a [] may be preempted by the critical sections (sub-tasks) τ a [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] and τ a [START_REF] Barry | FreeRTOS reference manual: API functions and configuration options[END_REF] (associated with r 1 and r 2 respectively), but not by the critical sections τ a [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF][START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] and τ a [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF][START_REF] Barry | FreeRTOS reference manual: API functions and configuration options[END_REF] (associated with r 3 and r 2 respectively) since they are not in the set sub a[] of immediate siblings to τ a []. τ a [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF][START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] and τ a [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF][START_REF] Barry | FreeRTOS reference manual: API functions and configuration options[END_REF] cannot be executed unless τ a [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] (the critical section r 1 ) is executing, hence they cannot preempt τ a [] directly. This corresponds to the first criterion of Equation 5.

Assume we have another task τ b []:

τ b[] := C b , O b , D b , J b , B b , P R b[] , S b[] , {} S b[] := 16 P R a[] := P b[] = 4 (6)
Assume that t a and t b , belongs to the same transaction and that (start [START_REF] Hänninen | Analysing stack usage in preemptive shared stack systems[END_REF]. This corresponds to the second criterion of Equation 5.

(W ax ) < start(W b[] ) < end(W ax ) holds for x = {[], [1], [1, 1]}, only t a [] and t a [1] may be preempted, since (P R a[1,1] = 4) < (P R b =
Assume that t a and t b , belongs to the different transactions, then t a [], t a [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF], t a [1, 2] and t a [START_REF] Barry | FreeRTOS reference manual: API functions and configuration options[END_REF] may be preempted. This corresponds to the third criterion of Equation 5.

Implementation and Evaluation

The iterative implementation of the algorithm follows directly from the definition of the pre-emtion criteria, exhaustively searching for the worst case pre-emption pattern w.r.t., to accumulated stack depth.

To reduce computation time, we introduce a simple caching mechanism. The cache reduces the number of tests required by storing the last test done on a single task and if the same possible preemption paths are present the cached result is used. Further optimisations can be explored, e.g., deploying dynamic programming building on partial results, but it is beyond the scope of this paper. However, the time complexity is by the definition of the problem O(2 n * 2 p ), where n is the number of tasks (including sub-tasks) and p the number of preemptions. In practise p is bound by the number of hardware interrupt priority levels. The memory complexity is linear to the task-set and the number of cache entries per task (for the experiments we used the latest two results).

Our evaluation shows that it is feasible to use this exact test for realistically sized task sets. For example a test of 50 main tasks and 250 sub-tasks (critical sections) takes about 1 minute on a 3GHz core2-duo using unoptimised single threaded python code with only simple caching and pre-calculations.

Example

For the given example we showcase the different stack estimation algorithms. Using the system model described in Section 2 and the system defined by ( 4) and (3) as example system, we demonstrate a number of approaches to estimating the maximum stack usage.

Method 1, SPL

In [START_REF] Hänninen | Analysing stack usage in preemptive shared stack systems[END_REF] (eq (1)), an algorithm, called SPL, for estimating stack usage for an SRP system is defined. The strength of this algorithm is the computational complexity, which is linear, but its estimate is overly pessimistic.

The algorithm works by identifying the task with maximum stack usage for each priority level and then sum all identified tasks.

The input to the algorithm is the priority level and maximum stack usage of all tasks in the system:

τ i := P R i , S i (7)
τa := 1, 72

τ b := 4, 16 (8)
The input, extracted from the example system, to the algorithm is shown in (8) and the result is 72 + 16 = 88.

Method 2, exhaustive search

This algorithm extracts the lower bound for the stack usage if resource information is omitted. It is a recursive algorithm which exhaustively searches all valid preemption paths and returns the maximum (accumulated) stackdepth of all paths.

The input to the algorithm is all tasks in the system:

τ i := P P i , S i (9)
P P i is the set of task that might preempt i, it is computed using Equation 6in [START_REF] Hänninen | Analysing stack usage in preemptive shared stack systems[END_REF]. For the given example system the input is:

τa := {τ b }, 72 τ b := {0}, 16 (10)
The exhaustive search search shows that the most expensive path to be: τ a ≺ τ b With the accumulated stack depth of 72 + 16 = 88.

Method 3, SPL with resource information

This method extends SPL to include subtask information. The input to the algorithm is the priority level and maximum stack usage of all tasks and sub-tasks in the system:

τ i[x] := P R i[x] , S i[x]
(11)

For the given example system the input is:

The identified tasks (the task with maximum stack usage for each preemption level) are: τ a , τ a [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF], τ a [START_REF] Barry | FreeRTOS reference manual: API functions and configuration options[END_REF], τ a [1, 1] stack usage can be calculated as 16 + 24 + 20 + 32 = 92. Note, that in this case the result is worse than method 1, however in average this is not the case (see chapter 5).

Method 4, exhaustive search with resource information

Here we extend method 2 to utilize subtasks, i.e the input to the algorithm is computed as:

τ i[x] := P P i[x] , S i[x] , sub ij[x] (13)
P P i[x]
is the set of task that might preempt i[x], it is computed using eq [START_REF] Tindell | Using Offset Information to Analyse Static Priority Pre-emptively Scheduled Task Sets[END_REF]. For the given system model the input computes to: Applying (13) to the example system yields (14).

τa := {τ b }, 16, {τ a[1] , τ a[2] } τ a[1] := {τ b }, 24, {τ a[1,1] , τ a[1,2] } τ a[2] := {τ b }, 20, {} τ a[1,1] := {}, 32, {} τ a[1,2] := {τ b }, 8, {} τ b := {}, 16, {} (14)
The exhaustive search of the extended model yields that the worst-case stack usage is given by the path: τ a ≺ τ a [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] ≺ τ a [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF][START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] With the accumulated stack depth of 16 + 24 + 32 = 72. Method 4 is safe and tight, (it gives the true upper bound of the memory usage).

Synthetic Benchmarks

In order to evaluate the proposed approach to stack memory analysis, we synthesise a set of benchmarks. We generate 100 test cases per experiment to get statistical material for drawing initial conclusions. For the experiments, we have fixed the number of unique priority levels to 16. The number of tasks are spanned in between 1 and 40. Each task has a base priority between 1 and 16 (evenly distributed), between 1 and 10 critical sections (evenly distributed), where each critical section claims a resource with ceiling 0 to 3 higher than the base priority (saturating to 16). Each section of code allocates 5 stack units. The number of transactions in each test case is log 2 (n), (n number of tasks) with the distribution: 50% of tasks in transaction 1, 25% in 2, 12.5% in 3 etc. (until all tasks are assigned). The probability of overlapping in between tasks belonging to the same transaction is 70% (if not else stated).

Execution time is indicated in terms of number of iterations. Average results are shown as firm lines, while shaded areas denote the first standard deviation.

Experiment 1, Potential Stack Reduction

In a first set of experiments we showcase granularity of analysis, Figure 1. Method 1: The uppermost (pink) shows the SPL behaviour (summing up the maximum stack usage in each priority level) [START_REF] Hänninen | Analysing stack usage in preemptive shared stack systems[END_REF], which clearly shows the worst estimate (over approximation). Method 2: The next (counting from top/worst case) marked red, show the case where we assume that functions are inlined, i.e., stack space for sub-tasks are claimed as part of the parenting task. This is an exact method, however the input model is an over approximation since we assume that all stack (including sub-tasks) is allocated at the lowest preemption level (the base priority of the task). Method 3: The next (marked green), show the case where we consider sub-tasks as being functions, i.e., local allocation for each sub-task, and the maximum stack usage per preemtion level is accumulated. However, this is still an approximation, while we do not consider nonpreemption information in-between tasks, and we do not consider relations between tasks and subtasks. Method 4: Bottom-most, (blue in figure), we show exact solution utilising non-preemption information and local stack allocation. The trend is clear, the exact solution for the task set is reducing the estimated stack space by a factor of 6 in comparison to SPL, and a factor of 3 to the per-task approach (used as a basis for the approximation work in [START_REF] Hänninen | Analysing stack usage in preemptive shared stack systems[END_REF]). Utilzing the non-preemption information and relations between subtasks and tasks improves the precision by more than a factor of two (blue compared to green).

Experiment 2, Effect of nonpreemptions

In the second set of experiments we show the effect of non-preemptions. We vary the probability of overlapping timing windows in between tasks in the same transaction from 0% to a 100% (Figure 2). Method 1: (purple) and Method 3: (green) do not utilise non-preemption information. Method 2: (red) relies only on the nonpreemption information. Method 4: (blue), utilises both non-preemption and local (per sub-task) stack.

Experiment 3, Uncached Execution Time

The third set of experiments (Figure 3) we showcase the execution time of the uncached implementation. Methods 2: (red) and 4: (blue) show exponential growth in number of iterations, while the Methods 1: and 3: are linear.

Experiment 4, Cached Execution time

The final set of experiments (Figure 4) we show the effect of simple caching of two latest results (with varying non-preemption set) computed for each task. In the experiment we use 40 tasks and vary the probability of overlapping timing windows. We observe a reduction by more than 20 times. The reason the number of iterations are reduced when closing 100% overlapping, is that the non-overlapping set shrinks towards the empty set, and hence the probability of cache hits increases. We expect more sophisticates caching and dynamic programming techniques to further reduce the execution time.

Conclusions and Future Work

We conclude that per-sub task stack analysis has significant impact to stack usage analysis, and that exact analysis is possible for task sets of practical use (50 tasks and 250 sub-tasks in a minute on an ordinary desktop). Further improvements can be made both in the direction of obtaining tighter results, and at the same time reducing execution time. This is possible by refining the pre-calculation of non-preemption sets (non-overlapping scheduling windows). (In the presented experimental implementation, we simply inherit the scheduling window.) While the solver in itself is exact the pre-calculation of scheduling windows is an over-estimation. The refinement will further reduce the execution time, since the non-preemption set will be extended (such preclude calculation of non-feasible preemptions). Future work also includes elaborating the trade-off in between in-lining of sub-tasks and sub-tasks as functions. The former reduces (constant) overhead of both CPU and stack for storing and restoring the (altered) set of registers (activation record), while the latter reduces the (dynamic) accumulated stack growth for sub-tasks.

Figure 1 :

 1 Figure 1: Calculated stack memory usage with the different algorithms. (X: Num of tasks, Y: Usage)

Figure 2 :

 2 Figure 2: Varying probability of overlapping of tasks in a transaction. (X: Probability Y: Stack memory) Top to bottom: Method 1[

Figure 3 :

 3 Figure 3: Uncached execution time, the number of tasks is varied from 1 to 40. 70 % chance of overlapping between tasks within a transaction.

Figure 4 :

 4 Figure 4: Cached execution time. The number of tasks is set to 40, and the probability of overlapping between tasks within a transaction is varied between 0% and 100 %.

Co-funded by the European Union, European Regional Development Fund (ERDF)


Patrice Thebault

Thierry Suquet

Michael Duffy

Benoit Viaud

Pascal Will

Julien Codron

Sébastien Lamoliate

Engineering of complex avionics systems simulations using a model based approach

With avionics system complexity increasing rapidly, the use of simulation throughout the system development lifecycle is a key enabler to achieve system maturity at Entry Into Service. However, simulations themselves are also complex systems whose development requires a high level of collaboration between multiple skills (IT, Plant modelling, Control, Embedded Software, etc). Therefore, having a functional simulation with the required level of fidelity and available at the right moment is always a tough challenge. To tackle these challenges, the INtegrated SImulation into Design project (INSIDE) was initiated by Airbus in 2009 to organize this collaboration at early definition of simulation architectures and simulation model components.

The approach is based on a Model Driven Engineering using System Modelling Language SysML to support architecture definition. The introduction will describe the problem in detail and then the paper will explain the proposed solution and how it improves the performance of the simulation development process. Finally, the feedback and future improvements are presented.

Introduction

The following explains the engineering process of simulation products which are enabling tools used to perform verification and validation activities for a system of interest. In this case, the system of interest is considered to be an avionics system (cf. Figure 1).

Figure 1 -High level simulation entities

The objective of the simulation

The overall objective of the simulation is to verify and validate the system of interest operating into simulated but realistic environment conditions.

Simulation can be used for:  Requirements validation to ensure that the requirements for a product are sufficiently correct and complete to satisfy the needs of the customer, safety & program;  Design Verification to provide evidence that the design, during the descending part of the V diagram is compliant with the requirements;  Product Verification to ensure that the product meets the requirements;  Product Validation to demonstrate that the product meets the needs of the customer.

The system of interest

In the simulation, the system of interest can be either virtualized or real.

Figure 2 -V-cycle model

The system of interest is virtualized on the left hand side of the V development cycle (cf. Figure 2), when the system itself is under design. Simulation is then used to perform validation of the specification and verification of the design of the system of interest. At this stage, the system of interest integrated with the simulation product may be implemented by prototypes, which partially or totally cover the system of interest functional perimeter.

When the system of interest becomes a product, i.e. on the right hand side of the V development cycle, simulation is used to perform product verification and validation, particularly to explore the system of interest operational environment in extreme conditions (such as failure conditions, limits of the domain of use, …).

The simulation product

A simulation product in Airbus is generally described as a simulation application deployed on a simulation platform, and interfaced with the system of interest.

When the System of Interest is virtualized, we generally consider it as part of the simulation application (cf. Figure 3).

Figure 3 -Simulation product architecture

To enable such architecture representation, it is required to define a common understanding on how the simulator platform shall execute the simulation application. For a wide part of Airbus simulation products, this is defined by an internal Airbus standard.

The Airbus Simulation Model (ASM)

This standard was issued in early 2000 to support exchange and reuse of simulation components across Airbus simulation platforms. It defines the concept of an "Airbus Simulation Model" and how it shall be executed on a simulation platform.

The execution scheme of an ASM relies on a periodic call of a main entry point by the simulation platform, during which it processes outputs from given inputs. Specifying who is providing the inputs and who is using the outputs is the role of the simulation application. How the outputs from one ASM are provided to inputs of another one, is the role of the simulation platform.

From the delivery point of view, although the Airbus Procedure states that an ASM shall be provided as C or Fortran source code, they are increasingly delivered in tool specific modelling languages (such as Simulink, SCADE, …), or sometimes directly as binary executable files.

The simulation application

The role assigned to the simulation application is to simulate the operational environment of the system of interest.

The simulation application development is based on the knowledge of the operational environment of the system of interest, which is, in the avionics context, composed of equipment whose behaviour is governed by physical law (Aircraft motion, electrical, hydraulic system) and other avionic systems.

The simulation application comprises a set of ASM and associated configuration files which specify the connections between ASMs, and their scheduling properties.

The simulation platform

The simulation platform consists of an IT infrastructure and the simulation software. Three main objectives are assigned to the simulation platform. Firstly, it schedules and monitors the execution of the ASMs with respect to time constraints of logical or real time simulation. Secondly, it implements the communication between ASMs. Thirdly, it provides the end user with control and observation facilities to operate the simulation.

In addition, when system of interest is a real product, specific facilities are also included in the simulation platform to enable signal adaptation and transportation from real world to simulated world.

Statement of problem

The simulation product is used during the design of a system of interest. For this reason, it not only needs to be updated continuously to follow each design change, but also to offer to the simulation end user (i.e. the developer of the system of interest) new simulation capabilities required for V&V objectives.

It is mainly the simulation application which supports this required agility. As mentioned before, the simulation application relies on integration of ASMs. It is the first foundation of a component model, but it lacks certain aspects such as those concerning the composition of models into a simulation application.

To work around these drawbacks, the simulation application development process is performed by Simulation platform teams, but they still need to capture information from simulation component developers, which hinders overall efficiency.

The objective of INSIDE is to provide a solution to enable real autonomy to Simulation application providers and independence from Simulation platform teams.

Before presenting this proposed approach, Part 2 of this paper presents in detail the simulation application development process, and the challenges to make it reactive.

Part 3 and 4 expose the proposed approach based on MDE and SysML to capture the different aspects of the simulation application.

Part 5 explains the difficulties encountered to deploy this approach and the means to solve it using adequate tools.

Part 6 presents the initial feedback and the perspectives.

Part 7 concludes by considering potential extensions to cover the overall documentation needs (through models) of a simulation product.

Simulation application development process

The simulation application development process is the cornerstone of the simulation product development process (cf. Figure 4).

Figure 4 -Simulation application development process

The first objective of this process, "Design", is to specify the simulation content and to define which simulation model can provide this content. This includes the definition of the functional and performance objectives of the simulation models and also the specification of their interfaces.

The second objective, "Integrate", is to ensure the technical coherency between the simulation models and the simulation platform on which they will be deployed.

Many actors are involved in these processes and efficient collaboration is a major key to achieve the objective of reactivity required by the end user of the simulation product.

Design simulation applications

Several activities are necessary for the design of a simulation application. Firstly, end users must identify their objectives of used. This enables the required functions and performance of the simulation to be specified. The simulation application architecture is then defined as a set of ASMs connected together, and all required functions can be allocated to the ASMs.

A typical simulation application could contain up to 100 simulation models with a total of 200 000 inputs and outputs connected together. These are the key factors which lead to the complexity of the simulation application. This complexity could never be managed manually. It is therefore critical to structure information so that the correct design subset can be edited autonomously by the user.

Reuse simulation model

Obviously, each development of ASM takes time and costs money, therefore the simulation application designer should identify the reusable ones.

The reuse of ASM across simulation applications reduces cost and time, but it also brings constraints during the assembly phase when they have to be connected together. Only the component specialists have the knowledge to specify the connections, and several specialists are required to integrate a whole simulation application (Cf. Figure 5).

ASM implementation

Once the simulation application is logically designed, each ASM has to be developed within its own lifecycle and its specific methods.

Therefore, each ASM has its own definition, managed in a separated view from the one built inside the simulation application.

Traditionally, these two aspects are covered by separate documents: one is the Model Functional and Performance Requirement to describe the ASM from the simulation application designer point of view, the second is the Model Specification to describe the ASM from its developer point of view.

This distinction enables the acquirer of the ASM to keep an abstract view on it, while the developer can provides further details on its implementation, as for example its packaging properties which depend on the type of methodology and tools used during its development. The ASM implementation can then be delivered as a Simulink, Scade or C-Code model as long as they comply with the Airbus procedure execution semantics.

It is the simulation platform responsibility to finally take into account each ASM with adequate production and deployment procedures via model transformations.

MDE approach to support simulation application development

As mentioned above, many actors collaborate to develop a simulation application. Therefore, we need a shared language to support their communications.

SysML had been previously selected in another R&T Airbus project [START_REF]Mise en oeuvre de SysML pour l'ingénierie des Produits Avioniques et de Simulation à Airbus -16ème journée Thématique[END_REF] as a language to support specification and design activities, and it was decided to adopt it. The contribution was then to demonstrate that it can be used efficiently to capture the design of complex simulation applications, and how we could make a bridge with legacy formalisms.

Let's first introduce the concepts that are needed for the formalization of the complete design of a simulation application architecture.

Simulation application domain model

In addition to "ASM" component, two other types of components have been considered.

The "PackageOfModels" component was added to support the architecture of the Simulation application, and to introduce a level of encapsulation, into the simulation application.

The concept of "SimulationDataBus" was added to enable capture of the connexions between different ASMs. [2] and following the EIA632 [START_REF]Processes for Engineering a System[END_REF] guidelines. Again, it is useful to present what concepts are intended to be captured prior to presenting how they are captured using SysML language.

At this stage of the project, capturing the structural aspect of the simulation was the primary focus while most of the behaviours are hidden inside the simulation components. There are both external and internal structures to capture.

External structure definition is used to describe the three types of Simulation component (cf. As mentioned in previous section, the main difficulties for the development of simulation applications relates to the capture of the connections specification between ASMs. For that, one of the critical elements are the interfaces. Because interface definition is a shared information between two connected components, defined at architecture level but also used also at implementation level, it cannot be managed within the SCLogicalDefinition. Therefore, it needs to be managed in a specific view which is imported by the logical one : the SCDataInterfaceView.

Mapping of concept with SysML language

In order to describe the simulation components within the SysML model, only a subset of the language is used.

First of all, it is required to support the organization of the information into different views such as the SCLogicalDefinition, SCPhysicalDefinition and SCDataInterfaceView. This is provided by the "uml::package" concept.

Then, for the description of the simulation components itself, a profile was developed to specialized the SysML language with the simulation domain concept.

Figure 12 -SysML profile for simulation definition

The advantage of the profile solution was to be able to develop a checker on design rules for the different simulation components. For instance, an ASM component has two FunctionalDataPort with specific names.

While SCLogicalDefinition is a type definition, it has been decided to represent it with a "sysml::block". Then, the Internal Block Diagram (IBD) is used to define the internal structure of the PackageOfModel, with "uml::part" used to represent the different SCInstances. Inside the IBD, the "uml::connector" is used to connect the port of the different instances of SimulationComponent.

To specify the SCDataPort and SCInterface two modelling solutions were available. Using atomic flow ports or using flow ports typed by flow specification.

Both solutions require adding flow ports on the block which represents the simulation model; however the solution based on flow specification offers the major advantage in our case to separate the list of exchange flow from the structure of the simulation model, and then was manageable in a separated package. This package is then imported in the different SCLogicalDefinition.

The content of the SCInterface is detailed with SysML::FlowProperties which are typed by predefined SysML::ValueType, corresponding to primitive allowed type by the Airbus Procedure for ASM.

MDE and life cycle management

The design process described above reaches another level of complexity when it comes to managing the simulation evolution with time. Each component used in the simulation, starting with the ASM, will evolve over its life-cycle in order to integrate new functionalities, bug fixes, etc. There is a real need and challenge in supporting the simulation designer with the upgrade of components when building a new version of the simulation application. To give more autonomy to the resolver and minimize the number of requests to the designer during the process, INSIDE proposes to define the interface compliancy with a range of versions (e.g. [3.0.0; 4.0.0[). In the above example, the simulation designer could express that the interface B1 between B and C could be any version from V3.1 to V3.9.

Given that level of freedom, the resolver can directly propose a matching solution.

More can also be done for the resolver by using semantic versioning [START_REF] Preston-Werner | Semantic Versioning[END_REF]: the resolver can then infer a first level of compliancy between the elements from the name of the version (e.g. component C using version V3.1 of interface B1 shall also be able to use any 3.X version). This track has not yet been fully explored in INSIDE; considering the context, it will probably require an automatic versioning mechanism to support users when they publish their new component definition.

Tooling to support simulation application design

When the approach was experimented with real end users, a certain resistance was initially encountered .

Two types of difficulties were raised. Firstly, SysML was another language to learn and perceived as far from the business domain language.

Secondly, SysML model edition was perceived as a heavy process, with many operations required to specify simple properties.

A part of the solution came with the Eclipse technical framework [5] chosen to develop the project and especially with the Eclipse Modeling Framework. On one side there are existing implementations of SysML [START_REF] Topcased | The Open Source Toolkit for Critical systems[END_REF] on top of EMF and on the other side, there are several graphical technologies on top of EMF that allow to view and edit an EMF model more simply.

Considering the context, we needed more than just one graphical paradigm to view and edit our model: boxes and lines are well adapted for the overall architecture description, tabular editors are almost mandatory when it comes to managing interfaces with many thousands of signals and finally, mainly for the purposes of improving ergonomics, the main elements (ASMs, interfaces, …) shall be easily browsed from the project view.

Following the proven Model-View-Controller pattern, it is relatively easy with EMF to propose different views on parts of the same model. Obeo Designer Erreur ! Source du renvoi introuvable. was a firstclass candidate to build consistent, visually pleasant and rich views; it was completed with lower level rendering technologies for large signals tables and management of the elements directly from the project representation tree.

In the Airbus context, there were legacy tools that could/should be used to edit some specific parts of the model; in particular, the edition of the connections between the signals in the databus was already provided by an existing tool. Using EMF, it was relatively easy to use Model-to-Text technologies such as Acceleo [START_REF]Acceleo[END_REF] to generate the required inputs for the legacy editors: e.g. the "edit databus" action in INSIDE transparently generates the configuration files and launches the external editor, allowing the user to refine the SysML model started in INSIDE.

Experimentation feedback

The approach has been deployed on a lab test environment only but experimentation was realized on a fully representative application case corresponding to a simulation product.

The simulation application deployed on this simulation product is composed of 109 ASMs which have more than 14 000 connections. The ASM providers work in five different organizations, belonging to the different Aircraft System design domains.

The objective of this application case is to perform multi system design validation, on Bleed, Engine and Warning system. For such objective, it is required to have high reactivity on the simulation application update after each system design change.

To enable such reactivity, the best way is to let the person who knows best, do what needs to be done: that is, the system designer, who is behind the design change.

But, when the changes are potentially originating from several design teams, it is required to ensure that on one hand they can collaborate together to update the whole simulation when the change impacts at a multi-system level and on the other hand that they can quickly iterate on their own part of the simulation when the change has no impact outside their system. This is the typical use case for which our approach aim at providing a solution, and therefore, it was the perfect setting for verification. Five major criteria were chosen to assess the solution: autonomy, reactivity, workload, quality, ergonomics.

In order to perform the assessment, the simulation application was first designed (cf. Figure 14) by the INSIDE team, and then during a workshops with end users, realistic changes scenarios on the simulation application were executed so that end users can first understand the proposed principles, then project their uses into a future process, and finally assess if the project objectives were achieved.

Figure 14 -Application case overview

Globally, the feedbacks from end users were very positive. They have assessed the added value of the solution in terms of improved autonomy for updating a simulation application.

On the side of reactivity, it was considered easy in terms of ability to easily integrate the update of a subset of the simulation application done by another team. In the legacy approach, this operation is always difficult, especially when there are concurrent modifications of the simulation application, which imply time consuming and error-prone merge operations. With the proposed approach, thanks to the ability to encapsulate ASM into PackageOfModels and also to the capability provided to easily collaborate on the definition of the interfaces, end users have confirmed that the operation would be far simpler.

For quality, we could not quantify objectively the level of improvement. Nevertheless, it was widely admitted that the autonomy given to the system designer, the primary owner of the knowledge, to update the simulation, would reduce the risk of introducing error.

Regarding ergonomics, since it was only a prototype approach, all the possible "shortcuts" were not implemented in the tool. But, there were no major questions or concerns from end users regarding possible difficulties to understand the key capabilities of the tool. However, the need for some fairly straightforward specific training has been identified. Another very positive feedback was the ability to increase reusability of simulation application artefacts. Thank to the concept of PackageOfModel it becomes possible to reuse a larger subset of simulation applications, while before it was only possible at the ASM level. This opportunity was identified in particular for reuse from single-system simulation platforms to multi system platforms.

Conclusion

This paper presents the results of a project aimed at improving the global efficiency of a system simulation design in a context where the simulation itself has become a complex system, involving many different teams. A Model Driven approach has been set up which has enabled the formalization of the existing organisations, processes, tools and simulation models materials with a focus on:  Collaboration: with a clear and formal separation of the simulation components specifications from their implementations, the simulation application designer can work on the definition and integration of the simulation components in a relatively independent way while the component providers can work with more formal specifications.

 Reuse: with the ability to compose simulation models into bigger models, it is possible to capitalize the definition and integration work related to these composite models.

Despite the fact that the project was built over the Airbus Procedure for ASM that gives guidelines on the structure and interfaces for an elementary simulation model, we believe that what has been designed to address the above mentioned issues is not specific to the Airbus environment and could be adapted to other contexts with the same benefits.

While the first steps in a transition towards more Model Driven Engineering are not always obviouswith a certain amount of energy spent just to describe what already exists -, it is then a strong basis on top of which it is possible to build high added-value features easily. To achieve even greater benefits, the framework started in this project should be extended with two additional MDE approaches: firstly, before the simulation design activities, to support capture of simulation needs (functional and performance), and secondly to specify the deployment of the simulation application on a simulation platform.

The final objective is to have a seamless process that enables rapid development of the simulation product, with high reactivity on the provision of updated simulation applications.

(

  Source: Clarus Concept of Operations)

Figure 5 -

 5 Figure5-Problem of connection specification Furthermore, interfaces of models are not always compatible, which requires signal adaptation (cf. Figure6).

Figure 6

 6

Figure 6 -

 6 Figure 6 -Problem of signal adaptation

Figure 7 -

 7 Figure 7-Type of simulation components Each simulation component is characterized by a definition and an implementation. The concept of SimulationComponent was introduced to reuse these properties throughout the development process (cf. below).

Figure 8 -

 8 Figure 8 -Simulation component types Each SimulationComponent includes a SCDefinition which contains the specification of the component from two points of view: the logical definition and the physical definition as already proposed in another Airbus R&T project[2] and following the EIA632

Figure 9 -

 9 Figure 9 -Simulation Component definition The logical definition is used to describe how the Simulation Component is breakdown into several sub simulation component and how they are connected together.The physical definition allows connection of the definition of the component with its concrete implementation. For instance, it is possible to implement an ASM with Simulink, Scade or C Code but whatever the final technical choice, it is documented into the "PhysicalDefinition".

Figure 10 -

 10 Figure 10 -Implementation for ASMs Method to describe Simulation component It was decided to capture the SCDefinition within the SysML model organized in several packages including one for the "SCLogicalDefinition" and another for the "SCPhysicalDefinition".

Figure 1 )

 1 from a usage point of view. It provides the list of "SCDataPort" which corresponds to the interaction points of the simulation component. Each "SCDataPort" is specified with a "SCDataInterface" which provides the list of data that flows in or out of the simulation component via the SCDataPort. Internal structure is only used to describe the internal organization of the PackageOfModels. It provides the list of instances of simulation component which composed the PackageOfModels, and how they are connected together through their SCDataPort. Each instance of simulation component is typed by a SCDefinition which corresponds to the definition of a required Simulation Component from the point of view of the PackageOfModels designer.

Figure 11 -

 11 Figure 11 -Concept to be captured in SysML

Figure 13 -

 13 Figure 13 -Basic component interactions In the situation illustrated above, the designer has started a simulation architecture definition involving three identified components; from this specification, the INSIDE framework is able to find and proposes existing implementations for these components that satisfy the versioned interface constraints. At some point, the version of interface A1 needs to be upgraded to version 2.4.0. In the example, INSIDE finds a matching implementation for component A, but not for component B: the implementation compliant with the upgraded version of A1 also provides an upgraded version 3.5 of its own interface B1. INSIDE then proposes an implementation solution to the simulation designer that implies another change of interface, in addition to the initial desired upgrade; the simulation designer has to decide whether to go with the proposed solution or to request the development of a new specific version of B satisfying the interface constraints. To support this use case, INSIDE relies on:  A clear distinction between simulation architecture needs and components implementations through versioned interfaces;  A common repository where all elements are stored and referenced;  A resolver function, triggered in the edition environment, which can browse the repository to find and propose the elements that satisfy the constraints of the architecture definition.


Peter M Kruse Berner

Mattner

Jörg Reiner
email: joerg.reiner@berner-mattner.com

Systematic Design and Automated Execution of Embedded System Tests

During the development of embedded systems, tests are performed on various test platforms, such as hardware-in-the-loop platforms in order to find faults. Test cases must be specified to verify the properties demanded of the system on these test platforms. The main challenge is to find relevant test cases, since in most cases not all possible test cases can be found and executed. Combinatorial testing can solve this task systematically.

In this paper, we describe the integrated test design and test automation using the industrial testing tools CTE XL Professional and MESSINA. In a case study with an antilock braking system, we demonstrate the operation of the system.

INTRODUCTION

A great number of today's products are based on the deployment of embedded systems. In industrial applications, embedded systems are predominantly used for controlling and monitoring technical processes.

In order to be able to find faults in the embedded system under development before its deployment into the target environment, tests are usually carried out on various in-the-loop test platforms. In-the-loop means that there is bidirectional interaction between the embedded system and its environment: the environment stimulates the sensors of the system, and in turn the system affects the environment using its actuators. Depending on the artifacts that are modeled and simulated, different in-the-loop test approaches are distinguished.

While a Model-in-the-loop (MiL) testing allows early tests with a model based approach; Software-in-the-loop (SiL) testing aims at testing executable artifacts of software components. With Hardware-in-the-loop (HiL) tests, the soft-ware integrated into the target hardware (e.g. an embedded controller) is examined. In all these cases the environment of the system under test is simulated.

Test cases must be created to verify the specified properties of the developed system on the different test platforms. Exhaustive testing is usually not possible due to the enormous amount of possible input situations and combinations of input signals. Care must therefore be taken to select relevant test cases, as the quality of the overall test directly depends on it. It is therefore necessary to follow a systematically approach, e.g. in terms of combinatorial testing.

In this paper, we describe the integration of the industrial testing tools MESSINA and CTE XL Professional.

MESSINA

MESSINA [1] is a testing environment for the test of embedded systems. It allows the connection to the embedded devices with their various interfaces, like electrical connections (e.g. analogue and digital signals) or bus systems (e.g. CAN) as well as sensor interfaces (e.g. cameras). MESSINA allows the implementation of hardware-and software-independent test sequences specified using different notations such as UML or Java. Using abstraction layers allows universal test execution on MiL, SiL and HiL platforms. One of these layers is the signal pool containing all system signals provided by the connected devices or software. The signal pool allows easy read and write access to all the signals used by the system under test (SUT) or the simulation environment.

Several approaches are available in MESSINA for the creation of test cases. Search-based testing approaches for example using evolutionary algorithms are described in [START_REF] Kruse | A highly configurable test system for evolutionary blackbox testing of embedded systems[END_REF]. Another approach is the application of Combinatorial Testing provided by CTE XL Professional.

CTE XL Professional

CTE XL Professional [START_REF] Berner | CTE XL Professional[END_REF] is a popular tool for systematic combinatorial test design. It implements and supports the test design technique called Classification Tree Method [START_REF] Grochtmann | Classification trees for partition testing[END_REF].

Basically the method consists of classifying the combinatorial aspects relevant for the SUT into classifications and then decomposing each into disjoint classes. Found classes can again be classified in different ways, so called refinements. This creates a tree made of classes and classifications, a Classification Tree. By means of the classification tree, the CTE XL Professional then generates test cases by combining the individual classes of the various classifications. For a test generation with pairwise combination coverage, a test suite is obtained, that uses every class pair from disjoint classifications at least once in a test case. Since large trees can generate many test cases due to the combinatorial explosion, CTE XL Professional offers prioritization of classes in a tree and hence the generated test cases will have a corresponding prioritization [START_REF] Kruse | Automated test case generation using classification trees[END_REF].

APPROACH

We are illustrating, how a classification tree structure with test cases can be created and exported to MESSINA for execution.

The general idea is to implement a general test case in MESSINA, which is then parameterized several times with test cases from CTE XL Professional.

Test Object: Anti-lock Braking System

The anti-lock braking system (ABS) is a system which prevents the wheels of a vehicle from locking while braking, in order to allow the driver to maintain steering control under heavy braking conditions and, in most situations, to shorten braking distances. Sensors of the ABS measure the speed at which the wheels are turning. If the speed decreases rapidly, the electronic control system reports blocking danger. The pressure of the brake hydraulics is reduced immediately and then raised again to a point slightly below the blocking threshold. This process is repeated several times per second. The goal of the anti-locking control system is to maintain the slip of the wheels at a level which guarantees the highest braking power and the highest steerability of the vehicle.

Test Implementation

The first step is the creation of a system setup in MESSINA. The runtime environment consists of the SUT as well as environment simulation models. In our configuration, we start with a MiL test, since actual hardware is not yet available. Sensors and actors are also simulated in our configuration. For simulating driving and braking maneuvers, a car simulation model is connected to the SUT using the signal pool. Test cases also connect to the signal pool, so they are able to read, trigger, manipulate and assess all data flow between the SUT and the simulation environment. The complete setup is given in Figure 1.

A MESSINA test case implementation typically consists of three sections, a pre-condition part (used for initialization), the actual test action and a post-condition part (used for cleanup). In the pre-condition part, the system is brought to a meaningful starting point, e.g. the speed is reduced to zero. public int run() { kl15.setValue(true) kl30.setValue(true) throttle.setValue(50); ASSERT(speed.waitValue(50, 60000), "Timeout-acceleration"); throttle.setValue(0); int startPos = distance.getValue(); brakeIntensity.setValue(100); ASSERT(speed.waitValue(0, 60000), "Timeout-brake"); int stopPos = distance.getValue(); int total = stopPos -startPos; ASSERT(total > 27, "FAIL: Distance too long with " + total + "m."); return 0; // 0 means PASS }

Listing 2: Actual test execution

In the test implementation (the run-method), the car is then accelerated to a given speed (50m/s), then a full brake is performed (with 100% brake intensity). When the car has come to a full stop, the braking distance is evaluated. If it is below a given threshold (27m), the test case passes. Otherwise, the test case produces a failure. public boolean postCondition() { brakeIntensity.setValue(0); return true; } }

Listing 3: Post-condition and cleanup

In the post-condition part, the brake is released.

Test Generalization

The concrete values in the test case can also be extracted so that the test case can be parameterized. Thus, different Speeds, Brake Intensities and so on can be tested using the same test template. For the combination of different parameter values, we use the CTE XL Professional.

Test Variation

The CTE XL Professional project is used to illustrate the campaign test cases and their parameters as a tree structure. Figure 2 shows the classification tree structure as created in CTE XL Professional.

All parameters (Speed, BrakeDistance, BrakeIntesity, KL30_Status, KL15_Status, ManeuverDurantion, ManeuverDataset) and their respective values are graphically displayed to illustrate their connection to the test cases. The test case groups each contain test cases which use different parameter settings as defined by the tree structure. These parameter values will be assigned to the MESSINA test case for execution of the test.

The CTE XL Professional export creates campaign structures in the MESSINA project based on the classification tree. The parameters for each test case execution within each campaign are then also defined in the classification tree.

The test case group (Braking Distance Tests) will be exported as a campaign into MESSINA. The actual export then consists of specifying the MESSINA project folder and selecting the template test case.

After a refresh of the project folder has been done in MESSINA, the project structure is updated (Figure 3). The new campaigns have been added. The test case (selected during the export process) is added to each campaign with the corresponding parameter settings as defined in the CTE XL Professional project.

The parameter values for each test case (within each campaign) can be examined by double clicking on the parameter name. The values correspond to those defined in the CTE XL Professional project.

Test Execution

The campaigns can then be executed in the usual way. All different configurations of the master test case are executed then one by one. In our example, this would be all three test cases. By the means of the MESSINA hardware abstraction layer the test cases can be run on all test configurations from MiL to HiL.

For the execution of test cases in a HiL setup, with actual hardware of the system under test, the MESSINA configuration would look slightly different (Figure 4). In the upper part, the ABS Module (SUT) is missing, as it is replaced by an ABS Electronic Control Unit (ECU). When the SUT evolves to an embedded system, as in our case, the access is done by hardware access (e.g. bus system or digital I/O or analogue I/O). MES-SINA provides adapters between these interfaces and the signal pool. I.e. that environment models and test cases can be reused without modifications. This combines both, the systematic test case generation and the consistent verification from early stages of the development process to the complete system test. The test reports of the executed test runs contain all relevant configuration information including the parameter set generated by CTE XL Professional. Reusable test cases on various integration levels (e.g. MiL, SiL, HiL) reduce creation and maintenance efforts and therefore cuts cost in embedded software development.

BEYOND PARAMETERIZATION

In this work, a master test case is to be implemented in MESSINA by the test engineer which is then parameterized using the CTE XL Professional. While this approach is already of great help for the test engineer, it does not benefit from all available test generation facilities of CTE XL Professional, i.e. the generation of semantically correct test sequences [START_REF] Kruse | Test Sequence Generation from Classification Trees[END_REF].

For testing state-based systems with continuous actions, test cases must therefore reflect these properties of the SUT in a certain order. The outcome of one test case is used as the input for the next test case. The composition of several test cases into a larger test scenario, so called test sequence, and their generation remains a challenging task. Furthermore, test steps as part of test sequences cannot be composed in any arbitrary order as it is required for some configurations of the software that other things have been done first.

In Figure 5, an example tree for driving maneuvers of a car is given. Different steering wheel angles and speeds are available.

Since the different configurations are only available depending on previous states of the car (e.g. steering to left is not directly reachable if steering is currently to right), not all possible tests can be performed in any arbitrary order. Therefore, the tester can assign allowed transitions to the classes of the classification tree.

The resulting valid transitions for Steering can be seen in Figure 6. Initially, the steering is neutral, straight forward (indicated by green background of the class). From neutral, the steering wheel can be turned to left and right, and also back from left and right, but there is no direct connection between left and right.

The available transitions for the car's speed are given in Figure 7. Initially, the car is always standing still (stop, again indicated by green background). It can accelerate to slow, medium and fast, but only in that order, and decelerate in reverse order from fast to medium to slow.

The allowed transitions can then be used for test sequence generation in CTE XL Professional.

The resulting test sequence is given in Figure 8. The sequence covers each transition at least once. The steering wheel is turned from neutral to the left, back to neutral, to the right and back to neutral, covering all four transitions for steering (as given in Figure 6). For the speed of the car, the sequence uses all possible transitions by accelerating from the stopped car to fast speed traversing low and medium speed and decelerates back to stop using medium and low speed again. The sequence containing of seven steps covers all possible six transitions of speed (as given in Figure 7).

For further use in MESSINA, the resulting sequence currently needs to be implemented in Java manually. By assigning Java statements to the corresponding elements of the classification tree (i.e. setter-/getter-methods to the classifications, concrete values to classes) the whole process can be further automatized. We are also evaluating the use of different coverage criteria for the actual generation of sequences.

SEARCH-BASED TESTING

The use of search-based techniques for functional testing of embedded systems has been described in [START_REF] Kruse | A highly configurable test system for evolutionary blackbox testing of embedded systems[END_REF].

Evolutionary testing is based on meta-heuristic search techniques such as evolutionary algorithms. An evolutionary algorithm is an optimization technique based on the principles of the Darwinian theory of evolution. It implements an iteratively process of evaluation, selection, crossover, mutation and population update, which is repeated unless a termination criterion applies, such as that the ideal solution is found. With evolutionary testing, the test objective considered is transformed into an optimization problem. The input domain of the test object forms the search space in which an evolutionary algorithm searches for test data that fulfils the respective test objective.

Through the EvoTest project, an extensible and open automated evolutionary testing architecture and framework was developed [START_REF] Dimitar | Evotest-Framework for customizable implementation of Evolutionary Testing[END_REF] that provides general components and interfaces to facilitate the automatic generation, execution, monitoring and evaluation of test cases using evolutionary computation.

Empirical evaluation in an industrial context using MESSINA has been evaluated in [START_REF] Vos | Evolutionary functional black-box testing in an industrial setting[END_REF]. In summery the study identifies the creation of appropriate fitness functions the most challenging task, although results indicate that evolutionary functional testing using MESSINA is scalable and applicable.

CONCLUSSION

In this paper, we presented an approach for systematic test design and test automation of MiL, SiL and HiL tests. We have laid out a simple system configuration for MESSINA consisting of a SUT and an environment simulation. An existing single test case is then parameterized allowing the use of CTE XL Professional for systematic test case design. Resulting test suites are exported from CTE XL Professional to MESSINA for execution and evaluation. The repeated instantiation of the master test cases reduces the manual effort of test case creation and maintenance.

For future work, we see a more tightened integration of both tools, to ease the systematic specification of embedded system tests and their automated execution. This might include actual Java test case generation from CTE XL Professional instead of parameterizing existing test cases. The distinction between pre-condition, test action and post-condition requires special attention, which might be handled more naturally with the test sequence generation facilities [START_REF] Kruse | Test Sequence Generation from Classification Trees[END_REF] of CTE XL Professional.

Post evaluation is another topic we would investigate further. CTE XL Professional supports the analysis of test results for specified test case to assess the influence of individual parameter values (the class) on test success or failure. Having a test suite with test results available allows for an in-depth root-cause-analysis.

We will also continue on the Search-based Software Testing track, as already described in [START_REF] Kruse | A highly configurable test system for evolutionary blackbox testing of embedded systems[END_REF].

Figure 1 :

 1 Figure 1: MESSINA MiL test environment configuration

Figure 2 :

 2 Figure 2: Classification Tree

Figure 4 :Figure 3 :

 43 Figure 4: MESSINA HiL test environment configuration

Figure 5 :Figure 6 :

 56 Figure 5: Classification Tree for Driving Car

Figure 7 :Figure 8 :

 78 Figure 7: Allowed Transitions for Speed