E Goubault

M Martel

S Putot

Some future challenges in the validation of control systems

Keywords: floating-point numbers, imprecision errors, static analysis, abstract interpretation

Starting with our work on the characterization of the imprecision error in programs using floating-point-numbers, by abstract interpretation, this paper shows that there are numerous perspectives, if one wants to fully qualify the numerical quality of control systems, as found in the aeronautical and automotive industry, for instance. Some very common functions (e.g. integrators) are hard to statically analyse, because their numerical correctness depend on a finegrained specification of the classes of input signals they handle. This gets even more complex in the case of e.g. PID controllers, which interact in closed loop with an external environment, since their input signals are in part the consequence of their own computation, similarly for the imprecision errors. We show examples of non-trivial bad and good numerical behaviours, discuss the results of our methods, and present our current research directions, that should hopefully help characterize the imprecision error of such control systems.

Introduction

The research work in computer systems at CEA originally started with the N4 generations of nuclear plants controlled by software (and not hardwired as previous generations). In particular, the emergency stop in such nuclear plants is the most critical part, which required huge validation efforts, fostering new research both in conception and verification methods, and still accounting for part of our current developments, under the auspices of IRSN. Our validation activity naturally applies to other critical control systems, such as the ones in the automotive and aeronautics industry. We will most notably take as an example of our current research the Fluctuat tool, currently evaluated and used both by IRSN and Airbus.

Fluctuat is a static analyser by abstract interpretation, which helps determine the discrepancy in the numerical computations in a control system, due to the use of an imperfect arithmetic, the IEEE 754 floating-point numbers (and more recently, fixed-point numbers as well), instead of using the ideal real numbers. It takes as input a piece of software (written in ANSI C, or in assembler, for the TMS320C3X), some assertions describing the range and precision of potential numerical inputs to this program, and gives as a result an estimate of the range and precision of all variables of the program, at some location in the program, for all possible inputs as specified, and without executing it. Furthermore, this estimate, as guaranteed by the general theory of abstract interpretation [START_REF]A unified lattice model for static analysis of programs by construction of approximations of fixed points[END_REF], is "sure", meaning that it is always an over-approximation of the set of possible values and imprecision errors that may arise during all potential (maybe infinite) executions of the program. Both the underlying theory and the tools themselves are described in [START_REF]Asserting the Precision of Floating-Point Computations: a Simple Abstract Interpreter[END_REF], [START_REF]Propagation of Roundoff Errors in Finite Precision Computations: a Semantics Approach[END_REF], [START_REF] Putot | Static Analysis-Based Validation of Floating-Point Computations[END_REF], [START_REF] Martel | Validation of Assembler Programs for DSPs: A Static Analyzer[END_REF]. They have been successfully applied to some representative industrial control systems, but these case studies lead us to consider new challenges, both on the practical and theoretical sides.

FLUCTUAT

The tool

The aim of Fluctuat is to either detect automatically a possible catastrophic loss of precision, and its source, or to prove that the precision of all computations remains in an acceptable range.

Indeed, the origin of the main losses of precision is most of the time very localized. Fluctuat relies on semantics that decompose the error between the results of the same computation achieved respectively with floating-point and real numbers, in a sum of error terms corresponding to the elementary operations of this computation, and a higher order term, most of the time negligible, that agglomerates higher order errors. We give in this section a short overview of how floating-point operations are interpreted with the first semantics we implemented, based on this idea.

) ( ) ( , r r r R r o o ↑ - = ↓ ∈ ∀ .
Assume that the control points of a program are annotated by unique labels L l ∈ , and that ℑ denotes the union of L and a special word hi used to denote all terms of order higher or equal to 2. We . For addition and subtraction, the errors are added or subtracted component-wise :

i i l y x o l l y l x l y x o l f f f f y x ε ε ω ω ) ( ) ( ) ( + ↓ + + + + =↑ + ∑ ℑ ∈
The multiplication introduces higher order errors:

. ) ( ) ( ) ( 2 1 2 1 , i i l y x o l l hi y l x l l l x l y y l x y x o l f f f f f f y x ε ε ω ω ε ω ω ↓ + + + + =↑ × ∑ ∑ ℑ ∈ ℑ ∈ ℑ ∈
The analyser is built on this idea, using intervals to get computable supersets of the coefficients, in an abstract interpretation framework [START_REF]A unified lattice model for static analysis of programs by construction of approximations of fixed points[END_REF]. The use of intervals allows on one hand to consider sets of values for variables, and on the other hand to include the rounding errors committed by the analysis. Indeed, static analysis consists in computing some properties of a program without executing it, for possibly large or infinite sets of inputs. Here, we compute a superset of all possible values x f and errors x l ω for each variable x at any iteration of the loops, on the nodes of the programs to analyze. These computations are implemented using MPFR [START_REF]Multiprecision library[END_REF], a library that allows floating-point computations with arbitrary precision.

The analyser has been finely tuned: it comprises an alias analyser, specific fix point iteration schemes, precise widening operators, mechanisms for automatically subdividing input interval values etc. Modular integer arithmetic is also considered, as well as casts between floating-point and integer, and bitwise operations on integers. Potential error terms are propagated between floating-point and integers.

A language extension is understood by the analyser, that allows the user to specify ranges of possible values and errors of inputs (and soon, the ranges of the gradient of values over time), instead of giving them fixed values.

Finally, the analysis relying on this domain does not use correlation between variables, and this may lead to large over-approximations. We thus have recently proposed weakly relational domains based on the same idea of keeping track of the origin of errors, but that use linear correlations between variables [START_REF] Goubault | Weakly relational domains for floating-point computation analysis[END_REF]. The results on the example presented in the next section were obtained with this relational analysis for the computation of values. The relational analysis for the computation of errors is being currently implemented.

Examples

Consider for example the following piece of code that computes the inverse of an input by a Newton iterative method. casts the double precision number A into an array of two integers. Then, the exponent of the input is got from the first integer of the array, by bitwise operations. Thus an initial estimate of the inverse, necessary for a good convergence of the Newton algorithm, is got from the exponent. Then a nonlinear iteration is computed until the difference between two successive iterates is bounded by epsilon.

In the framework of embedded systems, it is very important to qualify the behaviour of such an algorithm for all possible inputs. The first crucial point is to bound the possible number of iterations for any input in a range (in order to satisfy real-time constraints). And the second point that may be of importance is to see if the termination criterion is sensible, in the sense that if it is too low, the precision required may be obtained on the floatingpoint result, but not for the real result.

For example here, for all possible inputs between 20.0 and 30.0, our analyser finds that the algorithm always terminates in a number of iterations between 5 and 9, and states that the floating-point value of the output is in the interval [3.333333e-2,5.000000e-2] with a maximum error between the real and the floating-point computation in [-4.21443e-13,4.21443e -13]. We can note that the analyzer does not overestimate here the number of iterations, as executions show that respectively 5 iterations with an input equal to 20.0, and 9 iterations with an input equal to 30.0, are needed. Also, for the values, their bound indeed correspond to a close approximation of the inverse of the inputs. As for the error, it is for the moment slightly over-estimated, but we are currently working on a relational domain that will improve the results.

It should be noted that this error is not the absolute error between the result and the real value of the inverse. Fluctuat bounds the error due to the use of floating-point numbers, and cannot consider the error due to the algorithm itself, which for example here gives only an approximation of the inverse of the input.

The language of assertions understood by Fluctuat also allows to perturb the input with an initial error. For example if the input now has an error betweene-5 and e-5, then we get that the output has its error in [-9.95e-4, 9.94e-4] so the initial error is propagated without particular amplification, as the algorithm is stable (even if again the error is overestimated).

In this short example where errors come from a few lines, we only deal with value and global error, but for larger scale errors, the error graphs showing the origin of the main errors in the source code is useful in order to look more precisely at these few problematic lines.

Let us now examine the same example but using simple precision floating-point numbers instead of double precision. The analyser does not manage to prove convergence of the algorithm in a finite number of iterations, the number of iterations obtained is possibly infinite. However, this may either be due to the fact that the algorithm indeed cannot converge, or to the fact that the precision of the analysis is not sufficient. In order to have a more refined insight on that point, a possibility is to use a special mode of the analyzer we call symbolic execution. This mode allows to see the behaviour (evolution of value and errors), still with our abstract semantics, but for one particular value of the input (instead of a set of inputs like intervals), potentially perturbed by an error interval. The symbolic execution is also often less costly than static analysis. We have thus tried symbolic execution for 1000 input values in the range [20.0,30.0], and for the first 517 values tried, indeed the number of iteration remains bounded in [START_REF]Multiprecision library[END_REF][START_REF]A unified lattice model for static analysis of programs by construction of approximations of fixed points[END_REF]. However, for the 518 th value, A = 25.18, the algorithm does not converge, and the difference between two successive iterates alternates between -3.725290e-09 and 3.725290e-09. This behaviour was confirmed by actual execution on machine (decomposing every arithmetic operation in order to avoid the use of registers for intermediate computations).

Moreover, even in cases when the algorithm seems to converge properly, the accuracy of the result may be questionable : for example, for input A = 25.46999931335449219, the algorithm converges in 6 iterations, and the difference between two floatingpoint iterates is zero. But the analyzer also gives the information that there is an rounding error on this difference equal to 2.0199e-09, which is 20 times greater than the stopping criterion epsilon. One can thus wonder at the meaning of the criterion in this case.

Finally, if we relax the stopping criterion for example to epsilon=1e-7, then Fluctuat is able to find that the algorithm will always converge with between 4 and 12 iterations.

The complexity of control systems

Fluctuat mostly considers as for now only one part of the complexity of the problem. Typically, the inputs to the programs we want to check come, at some point, from an external input. As for now, we only deal with the interface between the physical and the software worlds at the level of the discretization of physical quantities (say, input from analogical sensors, measuring physical quantities such as speed, acceleration, position in space, temperature, etc.), which are made of real numbers in general, into integers (through quantization) or fixed-point or floating-point numbers. This is just one part of the problem: one also has to consider the discretization in time, or sampling of the data (as considered in "hybrid systems" theory [START_REF] Alur | The algorithmic analysis of hybrid systems[END_REF] but in general to a lesser extent than what we are planning to do). As for now, this is done in a rather simple way, partly because we mainly deal with synchronous systems, and partly because most of the systems we have been studying are somehow quite robust to the types of signal they can handle. For instance, in the previous example, we specified the range of the values and errors of inputs, and this was enough to get a good estimate of the numerical quality of the code. In the very near future, we will also have assertions to prescribe the range of the gradient of the inputs over time, which is a first step towards a better formalisation of the physical environment. This is quite new to static analysis, since the need has not been felt so much up to now. Typically, as reported in Astrée's experiments (static analyser for run-time errors developed by ENS and X [START_REF] Blanchet | Design and implementation of a special-purpose static program analyser for safety critical real-time embedded software[END_REF]), simple range assertions on cyclic inputs, not even giving some constraints on their time evolution, can be sufficient for proving absence of (software) bugs.

In the case of precision analysis, this is not true for even simple pieces of code, typical of components in control systems. Integrators are such components. They generally take as input a value, add it up to a current value, and use thresholds to limit the value they compute. Integrators are called in general with new inputs over time, cyclically. Indeed, it is very simple to prove (automatically, in a static analyser, for instance using the interval abstraction) that the variable containing the result will not overflow, if the threshold mechanism is well designed. Now, when it comes to the potential drift between the floating-point and the real values, things are much more difficult: imagine that the floating-point value representing the input signal always has a negative bias with respect to its actual physical value. This bias might add up substantially and lead to a very important imprecision error (of the order up to the value of the threshold itself). The difficulty is in general that the "real signal" has to be known quite precisely in order to find out that the rounding (quantization) and sampling introduce, for instance, a zero average bias. We give and explain below examples of such phenomena, and ideas about lines of research concerning static analysis in such contexts:

; if (intgrx > SUP) intgrx = SUP; if (intgrx < INF) intgrx = INF; } float f(int i) { … } void main() {
int i; for (i=0;i<N;i++) intgr(f(i)); } In the code above, intgr is a function that integrates (using the rectangle method) a given function f depending on a sample time i*h (h being the sampling step). Integration is carried out up to some threshold defined by the interval [INF,SUP]. Suppose f(i)=cos(2πih). This can be the result of the sampling at times ih of an external physical environment agreeing with the following ordinary differential equation (ODE) -for instance coming from the modelling of some electronic oscillator circuit with negligible impedance, or after the transient period: For point I, this is only true if the input signal is sampled at a sufficient rate. For instance, if h=1, the result would diverge to infinity, but any sampling with In order to illustrate point II, for

8 1 = h
, the sampling sequence is of period 8:

1, 2 2 , 0, 2 2 - , -1, 2 2 - , 0 , 2 2
; the imprecision error coming only from the rounding of 2 2 (the corresponding floating-point number is slightly less than the real number, by about 1.21e-8).

The rounding error for

1 2 2 2 2 1 = -         +
This means that the imprecision error on intgrx is the following sequence of period 8: 0, -5.938e-9; -5.938e-9, 0, 0, -1.51e-9, -1.51e-9, 0, which is bounded indeed, as can be seen in the figure below:

Of course any unfortunate error in the sampling time (or more general irregular sampling times, such as the ones considered in works in applied mathematics, such as [START_REF] Rivoira | Recursive Non Parametric Spectral Estimation From Irregularly Sampled Observations[END_REF]), or due to the sensor, might entail an important drift between the computed integral and the real integral. For instance, suppose that at every period (of 8 samples), sample number 4 (which should be taken at time (8k+3)h is in fact taken at time (8k+3)h+ε where ε is of the order of 1.71e-8. For this sampling time t, f(t) is equal to the floating-point number, closest to the real number 2 2 -, hence the imprecision error is zero for the computation of f at this precise time. But this produces a positive drift between the real number and the floating-point computation of the integral, which will take, after a finite number of iterations, the real number to the SUP threshold whereas the floating-point number will be periodic always less than 0.214 approximatively. See the figure below to see the slow drift of the imprecision error:

The fact is that any simple static analyser, based on standard intervals for instance, will be able to prove I, but II will be in general quite hard. Fluctuat is able to find that if the sampling is exact for a given h, and for the precise signal we have been looking at (with an extremely precise estimate of the solution of the ODE, using for instance the algorithm [START_REF]Analyse statique par interpretation abstraite de systèmes hybrids discrets-continus[END_REF]) then "unfolding" the loop h 1 times, periodically, will allow for giving very accurate bounds on the imprecision error. For general input sampling times, or more general types of signals, it will have no other solution than bound the imprecision error by the whole interval size SUP-INF. It will be right (not that pessimistic since this might really happen) but one might hope for better results, since in general an integrator is just a small part, buried deep in a control command code. This calls for the following:

• a careful study of the imprecision error in the sampling of some classical (but general) classes of signals, or of solutions to some classical ODEs • probabilistic estimates of the imprecision error in more general cases, in order to be less pessimistic, and give an indication of the "average case", since the worst case might be very often erroneous. For instance, for our last statement: if we model the perturbation of the sampling time as independent gaussian random variables with zero average and small variance, this will result in a zero average and small variance difference between the real integral of the perturbed discrete signal and the real integral of the periodic discrete signal. We conjecture that under some mild assumptions, this will also be the case between the real integral and the floating-point integral of the perturbed discrete signal.

As for the former point, one can readily see that there are functions that always behave badly with respect to the estimate of their integrals. For instance, if f is a decreasing function converging towards zero, but whose integral (from 0 to x, any positive real) is not bounded, like

1 1 ) ( + = x x f
the drift between the real number and the floatingpoint number computation of its integral is always very important, as we will show shortly. Below are the pictures of the computed integral in the floatingpoint numbers, and, respectively, of the imprecision error made for 10000000 iterations:

Then for the imprecision errors (the last part of the curve is actually increasing for ever, until the SUP threshold):

Consider any sampling of such a function f, such that for all N, there is always an infinite number of samples after N (plus infinity is an accumulation point of the sequence of samples). Then, because f is converging towards 0, and as it is always positive (it is decreasing towards zero), there is an X such that for all x greater than X, f(x) is less than half of the smallest positive floating-point number (of a given type). Hence for all subsequent samples, the signal will be rounded to zero, hence the integral as computed by our code, in the floating-point numbers, will converge in a finite time, to a finite number. Notice now that the integral of f from X to any further t will diverge to plus infinity when t goes to infinity. For a decreasing and positive function, the discrete integral as given by the algorithm programmed in our code, always gives an upperapproximation (in the real numbers), of the real integral, hence will also diverge to plus infinity. This entails that the imprecision error can grow arbitrarily high (up to the thresholds given by the code).

Future challenges

This gives but a simplified view of the problems one might encounter when trying to automatically verify typical PID control systems [START_REF] Automatique | Elements d'[END_REF], very much used in industrial codes. More generally, in most control systems, feedback loops are created, linking the output of the code to the input, at some further step, in a more or less direct way. For instance, the output of a control system goes through actuators, that interact with the physical environment, and in turn, will modify the values that the sensors will input to the control system, later on. We have already seen in the last section that the verification of such systems can only be precise enough if the "semantics" of the physical environment is modelled accurately, for instance using models involving some ODE or PDE. But this involved only the "separate" resolution of ODEs before trying to solve the (discrete) abstract semantical equations given by the code under analysis. For programs which interact also through actuators on the environment (that is, every real life control system), this is not enough: we need to be able to solve the discrete and continuous equations jointly. This poses new challenges to the field of automatic validation of systems, integrated in their environment, since methods for solving these discrete and continuous systems are in general fairly different! It is already interesting to note that some control theorists have also begun to make the way in the reverse direction, integrating software in their models of the physical world [START_REF]Safety verification of hybrid systems using barrier certificates[END_REF], [START_REF]A framework for worst-case and stochastic safety verification using barrier certificates[END_REF]. It is probable that the two communities will meet on a joint solution.

Take the following example. Water is poured into a tank of water at a given rate Fi, and a controller can act on the output flow Fo, possibly faster than the output flow (as shown in the figure below):

Hence the level u of the tank is governed by the ODE:

o i F F dt du - =
The controller will try to adjust the outgoing flow through an action on the valve, so that it can make the level reach and stabilize at the objective level yc. It will take as input, at periodic time ticks, the current level of the water (not knowing the input flow Fi of course) so that to determine whether it has to open more or close more the valve. Typical controllers (see [START_REF] Automatique | Elements d'[END_REF]) take as new value of the flow Fo at the time tick i, controlled by the value i u , a coefficient K multiplied by i e , the difference between the current level y and the objective level yc. These very simple controllers are called proportional controllers (P controllers). They can be controlled also with an extra term, using a correction term based on the time derivative of i e (to have a PD controller). Finally, one can also add up a factor of the integral over time of i e (to have a general PID controller). We refer the reader to [START_REF] Automatique | Elements d'[END_REF] for instance, for more about the respective interests of these different controllers. Note that PID controllers are heavily used in industry in the large, this is not a purely academic example.

An implementation of a PID controller can be easily encoded as follows, using the sum of i e over time to compute the integral (see our integrator of Section 3) and The different variables involved in the code below are:

• yn is the current value (at sample time n) of the level of the tank, • taui is the integration time of the PID controller, • taud is the derivation time of the PID controller, • K is the gain of the controller,

• yc is the level value that the controller should converge to, • ui (as computed by the main function), is the value of the flow of water that the controller imposes on the valve, at time i. This example is complex for a static analyser, as already was the integrator in Section 3, which it contains. So we only study here the numerical behaviour for one execution only, using Fluctuat and the same semantics as explained in Section 1 (this is a symbolic execution in the corresponding abstract domain). The graph below shows the value of the command ui over time, as automatically given by Fluctuat :

while the figure below pictures the evolution over time of the measure ei of the difference between the current level of water and the objective level:

Notice that numerical experiments show that this scheme is well behaved in general, as shown in our particular run of the algorithm, in the figure below (imprecision error of the difference between the level yi objective yc over time):

Notice that the errors at the end are going to zero, and are transient, due to the very low value of ei=yi-yc at these iterations (around the ulp(1) from the 70 th iteration on). The first iterates are actually computed exactly (the floating-point number is equal to the real number) because the first few iterates are of the form n -2 (the first ones are 0.5, 0.5, -0.25, -0.125 etc.) and thus the integral, derivative and gain computation (since the gain is also of this form: 0.5) have a small finite bit expansion in the floating-point number format. It is only after about 70 iterations, when close enough to the ulp, that some bits are lost in the rounding to nearest mode, but this still converges towards 0.

Unfortunately, this is but an approximation of the system we should prove correct (in particular, as for the imprecision errors in the control mechanism). In the real system, function y is a sampling at some more or less precise times of the current level of the tank, modelled (in the real numbers) as the solution of the differential equation above. We can make two remarks here:

• Fo is equal to the current flow command (given by ui) at the last clock tick -which is only a floating-point number approximating the value of the real command that should have taken place. Also the actuator (the valve) may not be very precise, and a new error is created there. This affects at the next sampling time the value of y. Because of the feedback loop, the imprecision error of the computation of ui will affect later inputs, possibly drifting dramatically (there is an integrator, as in last section, in the code!). But now, the characterization of the input signals, even probabilistically, is very hard to make, since the input depends on the computation. • Here, the ODE describing the external physical world is very simple, it is easy to simulate its solution in the same formalism as for the controller code (this is what we did here to analyse the code through our current version of Fluctuat). This is unfortunately not the case in general, and one has to design mixed ODE-discrete systems solvers, in order to be able to answer the verification problem (see for instance [START_REF]Analyse statique par interpretation abstraite de systèmes hybrids discrets-continus[END_REF] or [START_REF]Guaranteed error bounds for ordinary differential equation[END_REF]).

Notice that once again, it is the integrator part of the code which creates the main problem for Fluctuat: if we just use a P or PD controller, then we can prove automatically that there is no big imprecision error, in the particular case when the outside physical world is simulated by a C function as the one we had for the PID controller.

Conclusion

We have seen that Fluctuat is able to assert the precision of many floating-point computations in industrial, representative, control systems. Our current and future work is driven by two related objectives: to improve the precision of the analyses and to deal with larger classes of problems. These directions often are convergent since, for example, a more accurate domain enables the analyser to treat new classes of algorithms while improving the precision of the results in general. Obviously, as for other static analysers, a trade-off between precision and performances has to be carefully chosen.

A main difficulty comes from the fact that programs contain information on the evolution of floating-point values but not on the error terms. For example, the threshold performed by the integrator of Section 3 does not allow one to limit the error on the accumulator. So, in order to enable Fluctuat to infer such properties, we aim at designing new domains. For example, we are currently introducing linear correlations between variables, to limit the usual drawbacks of interval arithmetic (wrapping effect) on the error terms [START_REF] Goubault | Weakly relational domains for floating-point computation analysis[END_REF]. We also plan to compute information on the derivatives of the errors with respect to the floating-point values, by (safe) automatic differentiation, to correlate the floatingpoint values to the error terms.

New classes of problems have already been mentioned in this article. The analysis of hybrid systems, described in Section 4, is quite a challenging direction. Besides the definition of the analysis itself, it requires the design of safe numerical algorithms to find sure solutions to equation systems (typically ODE or PDE). Basically, for the safety and precision of the analysis, these algorithms have to output fine over-approximations and under-approximations of the real solution. For instance, in the case of the integrator of Section 3, a current implementation of the abstract domain of O.

Bouissou [START_REF]Analyse statique par interpretation abstraite de systèmes hybrids discrets-continus[END_REF] can already prove the boundedness of the variable intgrx for the cosine function, assuming the sampling is done at exact periodic times.

Next, our interest for introducing random variables to model some error terms was illustrated in Section 3 to cope with problems where, in the worst case, some error terms may indeed grow infinitely, for example if round-off errors do not cancel each other, even if this scenario is very unrealistic. In these cases, we plan to use new analyses based on probabilistic abstract domains [START_REF]An abstract Monte-Carlo Method for the Analysis of Probabilistic Programs[END_REF]. Another mid-term objective is to analyse mathematically more difficult problems. More precisely, we aim at designing new analysis frameworks to cope with numerical intensive codes, used for simulations (by opposition to control systems). However, the properties ensuring the stability of this kind of algorithms usually are much more complicated than in the case of control systems. Special purpose domains, possibly specific to some classes of numerical methods will probably be needed for these applications.

Another important research direction concerns the validation of the conformance of an implementation with respect to a model and this problem can be considered at different levels of abstraction. In practice, control systems usually are designed using high-level, often block diagram-based, languages like SCADE of SIMULINK and, then, are translated into C or assembler (by hand or automatically). If C code is used, it ultimately has to be compiled into assembler.

In any case, one has to assert that an implementation conforms to a model (C w.r.t. SCADE or SIMULINK, assembler w.r.t. C, etc.). These translations are error prone for numerical precision since floating-point computations are very sensitive, for example, to the evaluation order of the operations and to the different numbers of bits available in registers and memory locations. Hence, implementation details may significantly change the quality of a code, even if it mathematically computes what the specification requires in the reals. This makes us investigate different topics: first, the analysis of control systems described by block diagrams is a necessary intermediate objective. Second, we plan to use techniques to compare invariants at different levels of abstractions. This approach was successfully applied to run-time errors [START_REF]Invariant Translation-Based Certification of Assembly Codes, X. Rival[END_REF] but numerical precision introduces new problems, since we cannot expect to obtain exactly the same error terms in the model and the implementation. Finally, we investigate ways to make our analysers (C and assembler) collaborate, at least to analyse C codes with inlined assembler routines and, at longer term, to help solving the

  Let F be either the set of simple or double precision floating-point numbers. Let the rounded value of a real number, with respect to the rounding mode o.

  represent a variable x at some point in the program, the global error of the first-order error introduced by the operation labelled l, of this error term and l ε a formal variable labelling operation l. The result of an arithmetic operation i l • contains the propagation of existing errors on the operands, plus a new round-off error term

  double xi, xsi, A, temp; signed int *PtrA, *Ptrxi, cond, exp, i; double epsilon = e-10 ; A = __BUILTIN_DAED_DBETWEEN(20.0,30.0); PtrA = (signed int *) (&A); Ptrxi = (signed int *) (&xi)20) -1023; xi = 1; Ptrxi[0] = ((1023-exp) << 20); cond = 1; i = 0; while (cond) { xsi = 2*xi-A*xi*xi; temp = xsi-xi; cond = ((temp > epsilon) || (temp <epsilon)); xi = xsi; i++; } The special assertion A = __BUILTIN_DAED_DBETWEEN(20.0,30.0) tells the analyzer that double precision input A can take its value between 20.0 and 30.0. Then the operation PtrA = (signed int *) (&A)

#

  define SUP 20 #define INF -20 #define h 1/8.0 #define N 100 static float intgrx=0.0; void intgr(float xi) { intgrx += xi*h

  power of 2, it is easy to see that: I. intgrx is finite on any trace of execution (and for every N); indeed, it is of the order of imprecision error due to the floating-point truncation error, in the round to nearest mode is also bounded.

  do (this is related to Shannon's theorem).

  is of about -5.938e-9. Also, it is a property of the IEEE 754 standard[START_REF]What every computer scientist should know about floating-point arithmetic[END_REF] that, in particular, for )-x=1 in the rounding to the nearest mode. Hence:

  discretization of the time derivative of i e . Our PID controller is implemented in the main function below; it implements the following iterative scheme:

  -yi; sumej = epi; for (i=1;i<100;i++) { yi = y(i); ei = yc-yi; sumej = sumej+ei; ui = K*(ei+sumej*T/taui+taud/T*(eiepi)); epi = ei; } }

conformance problem. For example, under some assumptions, any arithmetic C expression could be translated in assembler before applying a mixed analysis.

Finally, we aim at defining more robust safety properties concerning the numerical precision of programs. Current criteria consist of proving that no error term overpasses a given limit, expressed as an absolute or relative quantity. But such criteria remain weak: for example an error of one percent may be, most of the time negligible, while being critical in some situations. In the context of hybrid systems, we plan to define more robust criteria based on the actions performed by a program on the environment. For example, an alarm has to be activated in the same cases, independently of which arithmetic is used, and independently of the precision of the computations.

Last but not least, in the search for realistic modelling and verification of systems involving software, some particular events have to be taken into account: for instance, faults of sensors, or actuators [START_REF]Distributed Algorithms[END_REF], since most control systems are inherently designed to be robust to some forms of accidents, and a complete proof should integrate the proof of the relevant software (and hardware) mechanisms. We advocate that other interactions with software than the ones with the physical world should be considered, namely the interaction with hardware (through OS, or simpler apparatus, like simple drivers). An ultimate goal, would be to include in the proof of a control system the human factor (which gives some inputs to the software in particular, for instance a pilot of a plane, or a driver of a car), but this has unfortunately far less clear scientific grounds, although models could and should include some basic factors like minimum response time of a human being, the possibility of an illegal command issued by the human being (such as turn off the key while driving), which can be formalized.

Acknowledgement

The authors acknowledge the contribution of their colleagues to this work, and in particular A. Chapoutot (see [START_REF]Analyse statique pour la precision numérique, A. Chapoutot[END_REF]) and O. Bouissou.


A Kaske

G François

M Maier

Alexander Burst

Virtual Prototyping for validation of functional architectures

Keywords: Architecture -Languages, Process, Methods and Tools -Safety, Security -Standardization, AUTOSAR

This paper will present a new approach how to use virtual prototyping to validate functional architectures. The approach points out how functional architecture can be set up and tested in order to get highly validated data before making final architectural/design decisions. The introduction will speak about the current facts, the constrains and the tendencies to create a common and understandable picture in which the proposed solution may be implemented. Then we will give a description and definition of MiLMiL / SiLSiL / HiL, rapid prototyping and virtual prototyping to avoid confusion. The main part will discuss functional and logical architecture, the mapping of both as well a the variants that have to be considered. It will be shown how validation by virtual prototyping can help to define and proof architectural decision. Finally we will give a short outlook on how to migrate from virtual prototyping systems via rapid prototyping via fullpass and bypass to HiL applications. The conclusion summarizes the advantages compared to the current situation.

Introduction

The current situation in the automotive industry is marked by a strong movement to new development processes that will guarantee higher quality of (especially) the electronics part (hard and software) of the vehicles. From a very general point of view two major problems are identified, diagnostics (badly linked with functional development and -due to long time missing standardization -incoherent usage of data etc.) and incomplete functional specification and validation. Diagnostics aspects are not part of this paper. Functional development, independent whether it is in Powertrain/Drivetrain, Chassis or Body Electronics suffers today from late validation of functional architecture decisions. Sometimes these decisions are first tested with or after integration of all subsystems in the vehicle (this is especially true for rare variants of a vehicle). Errors discovered in this late development stage are either very costly to fix or even unsolvable Two tendencies enforce these problems:

• First, the upcoming interdomain functions, e.g., for driving assistance such as Lane Departure Warning (Chassis, Powertrain and Body Electronics ECUs are involved) and • Second, the tendency to reduce the overall number of ECUs creates the force to integrate functionality from different ECUs (even from different ECU suppliers) into one ECU which creates additional problems like IP protection, responsibility and common software architecture.

Several initiatives are currently on the road where AUTOSAR is certainly the most important with the highest impact on the whole development cycle. We will show how our approach will deal with these different constrains and how it will provide a cost effective method to get higher quality, less errors and well tested functional specifications.

Definitions

This paragraph will explain and define what we understand with the mentioned terms.

2.1

MiL -Model-

Env . Model

Module m3

Module m1

Module m2

Module m3

Component c3

Module m1

Component c1

Module m2

Virtual Function Network

Virtual Function Bus

Component c2

-VIRTUAL OSEK

Module m3

Module m1

Module m2

Virtual communication drivers Semi-fullpass RP systems are somehow very special bypass systems since all applicative software is executed on the RP system and the ECU is just used for signal conditioning and low level I/O management.

Electronic Vehicle Architecture

This paragraph is dedicated to give a brief introduction of the 3 major steps of the development of electronic vehicle architectures.

Functional Architecture

During functional development the OEM has to take several architectural decisions. First the OEM sets up the functions to be available in the vehicle.

Additionally the OEM starts to define the variants that will exist for the vehicle (variants can be specific to regional markets, to functional components such as engine/gearbox, to coachwork etc.). In parallel to the functional architecture an ECU network the logical or electronic architecture has to be designed. This network has to deal with constrains like:

• number of variants

• scalability

• redundancy -security

• cabling efforts

• reuse of existing (sub-) systems

• etc.

Mapping of Functional and Electronic Architecture

Finally the functional architecture must be mapped to the electronic architecture, i.e. the ECU network(s).

Most problematic is here the number of variants that may exist for a vehicle family (up to 2000 software / hardware combinations = variants). Due to the fact that only a very limited number can be tested with current methods 2 it becomes clear that at lot of errors are discovered first when a variant is build in a real vehicle for an end customer which is too late and very expensive if errors are detected.

2 Test and validation is mostly done via the test vehicle fleets with about 100-400 vehicles. That means a maximum of about 400 variants could be theoretically tested. There may occur a number of problems when applying different mappings like:

• Bus overload due to communications between software modules, that are no more on the same ECU.

• General or sporadic ECU overload like scheduling problems (task activation missed, deadline not reached etc.). • Bus communication may introduce a delay that may cause some algorithms to become unstable which may end up in a bad reactivity of a component, e.g. electro-mechanical door openers.

• Additional bus communications may block

communications with other ECUs due to priority problems 3 which show suddenly an erroneous behavior (without any changes on this particular ECU).

Validation by Virtual Prototyping

Virtual Prototyping can give people the chance to simulate very early any functional architecture with few effort (hardware costs and time). Virtual prototyping makes this possible especially when it is combined with standardized software architecture such as AUTOSAR proposes it. Using a standardized software architecture is a key to distribute easily software between the virtual ECUs (simulated by a standard PC) as well as on other hardware execution platforms (rapid prototyping systems or ECUs). These virtual ECUs have already a real time behavior that is relatively close to the final ECU (at least when comparing it to current simulation methods) and even more important, they are using the same/similar basic software to insure that all applications are dealing with the same mechanisms independent whether they are executed 3 Most used CAN drivers do not deal correctly with priority handling of CAN messages which leads to an unpredictable network behavior.

in a VP environment or on a RP system or on a real ECU.

Virtual Prototyping Systems

The very first step in prototyping a functional system is to integrate all functionality together with the environment model. This gives information about general aspects of the functionality • does in principle the function do what the developer expects, • does the co-working of functions work as expected, • etc. This first step does not necessarily answer questions about the look & feel of the function for the end customer because mostly at this point nothing happens in real-time -due to the fact that it is just a MiL application. A next step could be to introduce "real-time" in the sense that all functions and environment models are executed in real-time. This helps to identify problems of, e.g., look & feel for an end customer -pressing a button should lead to an immediate reaction of the system (vehicle). Immediate is unfortunately a relative term because the perception of human beings of "immediate" depends whether it is an acoustic, a vision or a mechanical feedback. In general we can say that a feedback should be given with less than 250ms in order to be perceived as immediate. This step can be cut into 2 steps, a first one just creating a real-time MiL application and a second step converting this to a SiL application. For large projects this may introduce a certain additional effort but it helps enormously to identify to root cause of an error because each step modifies just one parameter.

• MiL to real-time Mil -modified parameter is the introduction of real-time • Real-time MiL to SiL -modified parameter is the introduction of basic software Next important step is to distribute the modules/functions to a dedicated (simulated) ECU and to create by this a real (pseudo) ECU-network.

• SiL to distributed SiL -modified parameter is the introduction of bus communications and its associated delays etc. At that point all modules/functions mapped to the same ECU have to be integrated together with the BSW to get the executable code for a pseudo or real ECU. It is important to understand that the proposed virtual prototyping environment is highly scalable. That means it is possible to simulate more than one ECU on only one PC as well as one ECU on one PC which makes it easy to setup variants automatically as well as to test them automatically. To do this it is necessary that the distribution and integration platform provides an automation interface like COM API for example. For the test environment it is not important to know on which ECU a function is executed. The test script just needs to know that a function together with its measurements and calibrations exists. Therefore it is completely transparent to the test environment and no modification is necessary to execute the test scripts on different functional architecture variants. By this means it is possible to test all variants in an early development phase (over night, during the week end) and to discover the major part of errors related to architectural decisions quite easily4 .

Migration of VP systems to RP systems

Another source of problems is the non-continuous use of tools and methods during the development process. Normally multiple conversion/migration of data and description formats is necessary because the MiL/SiL tool environment is quite different and incompatible to the RP environment and even worse, different to the one of ECU software development environment.

The proposed approach is able to overcome most of the mentioned insufficiencies because it can assure that the same software architecture as well as the same software components (at least the hardware independent ones) are the same. A migration from a SiL system (independent whether it is distributed or not) to a RP system makes for the proposed integration platform no other difference than compiling all sources (C-code) for a different target which is in this case a RP system.

Generic Distribution and Integration Platform

The main assumption (as already mentioned) for a generic distribution and integration platform is that it should be possible to convert a functional specification into C-code (pure ANSI C). This is true for almost all currently used BMT tools. An additional assumption (as already mentioned) is that it should be possible to use a standardized software architecture independent of the execution platform (execution platform can be the PC, a RP system or an ECU). This seems to be true with the upcoming AUTOSAR standard and the software architecture imposed by the standard.

Finally such an integration platform has to use as much as possible well established standards to make reuse of existing tools and data and to be therefore investment save. This is also necessary to integrate the platform easily into existing tool chains and processes.

With the INTECRIO Product Family, ETAS offers a prototyping environment which already supports the integration of functions modelled in either Matlab/Simulink or ASCET or written in ANSI C-Code 5 . INTECRIO may serve as a starting point for the proposed integration platform.

For the integration of a module/function 3 different files are necessary:

• C-code (ANSI) the executable representation of the functional specification or even its real implementation 6 . • A2L (ASAM MCD-2MC) the description of internal variables of the C-code (functional specification or implemented software) that can be measured and/or calibrated (e.g. via standard MC tools ). • SCOOP-IX (XML -ETAS) 7 the description of messages send and/or received by the component/function as well as its internal behavior, the scheduling information. When using these 3 files for each component then the proposed integration platform is able to configure complex software systems just by connecting message ports between different components. This defines the data/message flow. 5 INCODIO by Systecs -available mid 2006current planning. 6 Optional, in order to provide better know-how protection it will also integration already precompiled binary code-then integration becomes target specific. 7 Additionally AUTOSAR software component descriptions will be supported in the future. It is important to understand that the proposed approach does not mean that all modules/ functions need to be available in the same format (e.g. as Simulink model). In contrary -this approach is able to integrate simultaneously application software components generated by Simulink with those generated by ASCET with hand-written C-code or Ccode from any other C-code generator8 . Due to the fact that the approach integrates on C-code level it is easily possible that the integration platform is independent of the tools and version used to generate this C-code. The possibility to integrate models/functions (respectively their C-code) from several e.g. Matlab/Simulink version in parallel makes the cooperation between several partners of a development much easier then today, where they have to agree on a specific tool version.

The possibility to integrate models/functions with existing C-code avoids the necessity to create e.g. Simulink or Statemate models for legacy code which might be available even as real ECU code. This is an important feature to enable the introduction of the proposed integration platform because the necessary pre-requirements are pretty low. Mostly the integration of a MiL/SiL approache as described above into broader company processes is blocked by the effort to be spend to develop models for all existing (electronic) functionality of a vehicle, which is normally about several decades of man years9 . Another important step is the definition of the scheduling behavior. In the proposed integration platform this is possible via a graphical representation of the underlying OSEK OS. The big advantage to use right from the beginning an OSEK OS is (even for PC based simulation in MiL/SiL applications) that only those OSEK OS features are used which will be also available on the final target (ECU). No break between MiL/SiL configuration and RP system/ECU configuration. If a different OS/scheduler would be used, special modeling and configuration rules need to be applied in order to guarantee that the MiL/SiL simulation can be transferred easily to the RP system/ECU which would make the process more fault-prone. The integration platform finally provides all necessary hardware configuration and generates the glue code 10 to create a totally standardized software architecture (based on AUTOSAR when AUTOSAR has finished its work).

Additionally the proposed integration platform offers some other interesting features like the dynamic reconfiguration of the message/data flow. For the ECU a similar feature is known as internal bypass but the integration platform is much more flexible for such a reconfiguration.

Migration to HiL systems

This integration platform supports RP systems as well as VP system. From a top level view it makes no difference whether the system is a virtual prototyping system or a real distributed rapid prototyping system or even a mixture between both.

10 Glue code is a small code fragment to adapt API calls etc.. This makes it easy to go even one step further and to migrate a (distributed) SiL system into a HiL system. The HiL system may be setup with RP systems running as fullpass systems as shown below. Any other setup with ECUs or with bypass systems is also possible. This makes it easily possible to adapt each sub-system to its degree of maturity -ECUs where ECU are already available, bypass systems where most of an ECU is stable and only some new functionality needs to be integrated and fullpass systems which are still in a very early development state. This possibility to migrate individually each subsystem from one simulation level to the next is another dimension of scalability that this integration platform will propose.

Figure 2 :

 2 Figure 2: Schematic representation of a SiL application

Figure 4 :

 4 Figure 4: Schematic description of functions and inter-domain functions

Figure 5 :

 5 Figure 5: Schematic presentation of the physical ECU network

  Figure 6: Mapping between functional and electronic world

Figure 7 :

 7 Figure 7: Overview of the entire SiL (distributed) system

Figure 9 :

 9 Figure 9: Graphical OSEK-OS configuration in INTECRIO.

  Figure 10: distributed SiL-system

Figure 11 :

 11 Figure 11: Final migration to HiL application

If the executed test scripts push the systems to its limits.

E.g. TargetLink or Statemate/Rhapsody in Micro C etc.

Estimation:

-200 electronic functions per vehicle -development of a tested/validated model for an existing functionality is in average between ½..1 man year.

Conclusion

The virtual prototyping approach combined with a distribution and integration platform enables very early validation of functional architecture decisions. This permits to identify weaknesses and errors of the architectural decision, to fix them or to modify the architecture when it is still possible and especially much less expensive then with the current approaches. The proposed integration platform offers a multidimensional scalability which makes an easy integration into existing company processes possible. Thanks to the integration on C-code level the integration platform becomes independent of BMTs and their versions. It is open to any other manually or automatically generated C-code as well. Finally the independence from and transparency of the hardware execution platform gives the customers a high flexibility to chose adapted means for their problem. Overall the virtual prototyping approach will help to increase the overall quality of the electronics systems in vehicle what is currently the main concern of most OEMs.

Acknowledgement

The authors acknowledge the contribution of their colleagues of the whole ETAS Group to this work as well as the related customers confident to work with us on these sensible topics.

Glossary


Eliminating Embedded Software Defects in a Virtual System Integration Laboratory

Keywords: Embedded, IV&V, Simulation, Test, Software, System, V&V, VSIL, Verification

Research has shown that finding software faults early in the development cycle not only improves software assurance, but also reduces software development expense and time. The root causes of the majority of embedded system software defects discovered during hardware integration test have been attributed to errors in understanding and implementing requirements. The independence that typically exists between the system and software development processes provides ample opportunity for the introduction of these types of faults. This paper shows a viable method of verifying object software using the same tests created to verify the system design from which the software was developed. After passing the same tests used to verify the system design, it can be said that the software has correctly implemented all of the known and tested system requirements.

This method enables the discovery of functional faults prior to the integration test phase of a project.

Introduction

New complex embedded systems are quick to take advantage of the unrelenting pace of advancement in computer hardware performance and capacity. Along with the increase in hardware capability has come a considerably greater increase in the functionality and complexity of control software. Unfortunately, the methods & tools we use to develop and test systems and software have not kept up with the trend. This is evidenced by the number of software faults that pass undetected into the integration and operational phases of contemporary projects. This is of concern for two important reasons. In the case of software in control of safety-or missioncritical systems, allowing a failure to pass undetected into the operational phase of a project may put lives and/or critical missions at risk. In all cases the more faults that pass undetected into integration test and beyond, the more the project will cost and the longer it will take to complete. This article presents a new, closed-loop method of simulating and verifying embedded system designs and their controlling software in a pure virtual system integration laboratory environment.

We have demonstrated and validated this method in a recently concluded research effort sponsored by the NASA Office of Safety & Mission Assurance under their Software Assurance Research Program (SARP) [START_REF] Bennett | The Use of a Virtual System Simulator and Executable Specifications to Enhance Software Validation, Verification, and Safety Assurance -Final Report[END_REF]. Our investigation showed: 1. A new method of specifying, executing, and verifying an entire system design in a pure virtual environment. 2. How uninstrumented embedded object software can be verified in a virtual system environment. 3. How the same tests used to verify the system design may be used to verify the controlling software. It follows from item 3 that if the software passes the same tests used to verify the system design then it correctly implements the known and tested system requirements. As a result, we now have a viable means of discovering requirements-induced software faults prior to the integration test phase of a project. This is significant because it has been shown that early discovery of faults reduces both project cost and duration.

Background

Root causes of software faults

The root causes of the majority of software defects discovered in integration test during the development of an embedded system have been attributed to errors in understanding and implementing requirements (see sidebar: "JPL Root-Cause Analysis of Spacecraft Software Defects" on page 2). These may be the system and/or the software requirements. We assert that this is largely a result of the independence that exists between the requirements development and the software development processes. The JPL report findings are echoed in reports of numerous other researchers such as Leveson [START_REF] Leveson | Safeware -System, Safety and Computers[END_REF] [3], Ellis [START_REF] Ellis | Achieving Safety in Complex Control Systems[END_REF], Thompson [START_REF] Thompson | A Framework for Static Analysis and Simulation of System-level Inter-component Communication[END_REF], et al. Consider some of the many avenues where requirements-related problems might be introduced:

• Assumptions/ambiguities affecting interpretation of customer descriptions of desired system behavior. • The difficulty of fully understanding the realworld environment in which the system will interact. • The difficulty in anticipating all of the possible modes and states that the system may A. Ted Bennett To compound the problem, we generally cannot know at the onset of a project if we have accurately modeled the realworld system behavior. As a project advances, however, so does our understanding of the system. Additional faults may be introduced when subsequent refinements to the system model are not adequately communicated to the software development teams.

To be more effective at creating software with a high level of assurance, not only must we reduce the number of errors attributable to misunderstanding & misimplementing requirements, but we must also improve communication between and among system & implementation teams.

Shortcomings of federated

development methods Contemporary embedded systems development projects are typically conducted in a federated manner. In other words, the system and software development activities are conducted essentially independent of each other. To illustrate this point, Figure 2 depicts the three principal loops comprising a typical project process. We will ignore hardware development activities since they are not germane to this discussion. The first loop is where the system design is created. The system designers may make use of modeling, simulation, prototyping, specification, and other tools to satisfy the need to validate control algorithms, component interactions, etc. The system architects validate and verify their design through analysis, possibly tests, and possibly by similarity with reused components.

They then document the requirements for the implementation teams to follow.

When satisfied with

JPL Root-Cause Analysis of Spacecraft Software Defects

In 1992, Dr. Robyn Lutz conducted an analysis for the Jet Propulsion Laboratory (JPL) to determine the root causes of the 387 software defects discovered during the integration test phase of the Voyager and Galileo spacecraft development efforts. The software controlling these spacecraft is distributed among several embedded computers with roughly 18,000 and 22,000 lines of source code respectively.

Lutz reported that the programming faults discovered on the two projects are distributed as shown in figure 1.

The fault classifications given in figure 1 are defined as follows:

• Functional faults comprise the three subclasses listed below: a. Operating faults: omission of, or unnecessary operations; b. Conditional faults: incorrect condition or limit values; and c. Behavioral faults: incorrect behavior, not conforming to requirements. • Interface faults are those related to interactions with other system components such as transfer of data or control.

• Internal faults are defined as coding faults internal to a software module The data show that 98% of the combined total software problems were classified as functional or interface faults that are directly attributable to errors in understanding & implementing requirements, and inadequate communication between development teams. Only 2% were due to software module coding errors [START_REF] Lutz | Analyzing Software Errors in Safety-Critical, Embedded Systems[END_REF].

The conclusions of the JPL report point to the need for improved focus in the following areas:

1. Interfaces between the software and the system domains 2. Identification of safety-critical hazards early in the requirements analysis their design (or when time runs out), the system team delivers the system specification package to the implementation teams.

Entering the second loop shown in Figure 2, the software implementation team interprets the relevant requirements -whether written in natural language, specification design language, or executable specifications -derives software requirements, and creates its design. The software developers write their own tests to verify conformance to the requirements as they have interpreted them. They may use some form of simulation, hardware development boards, inspection, analysis, or similarity comparison to facilitate verification of their code.

When a major part of the system functionality has been coded, the software team creates a build. The software is loaded into its target hardware where integration test begins in the laboratory. Connected to test equipment, simulators, and perhaps other system elements, the control software is stimulated by the hardware environment under the control of custom test software. Bugs discovered during integration test are filed as problem reports and passed back to the development team to resolve, thereby completing the third loop. We see the independence that exists between the system and software loops in this development process as the primary reason for the propagation of software faults into integration test. Further, this independent process may breed duplicity of effort where the software and system teams write their own tests to verify the same behavior at the system and software levels. Our research has shown a method of connecting the system and software development loops that allows tests written for system verification to be used to verify the software itself. This enables the software to be thoroughly debugged in a pure virtual environment before it ever gets to the hardware integration phase.

Coupling the System & SW development loops

Figure 3 illustrates our approach to connecting the system and software development loops. This new approach retains the system and software development loops but eliminates the loop where the hardware integration lab is used for software debug activities.

As before, your project begins with the development of a system design using various tools for algorithm development etc. However, in lieu of passing the design and requirements to the implementation teams as a collection of disparate specifications, the entire system and the environment in which it interacts is simulated using a form of executable specifications (ES). All parts in the simulation are bounded like their real-world counterparts so that the interface behavior of each element can be correctly modeled and specified. Parts are created with builtin failure modes that may be activated under test control.

Having modeled the behavior of the entire system environment, you now have a complete virtual system integration laboratory (VSIL) in which to validate and verify your system design. The next step is to create a suite of tests based upon nominal and off-nominal scenarios for which the system has been designed to react. Our testing philosophy is to exercise the system by driving the environment as realistically as possible, and monitoring the system behavior in response. This is generally not a viable approach for hardware system integration laboratory setups due to the costs or difficulty involved in procuring, creating, and synchronously controlling all the disparate pieces of hardware and simulators necessary to realistically drive the target system.

The completed and verified VSIL is then passed, along with the system-level tests and any supplemental written requirements, to the development teams. The teams create hardware and software designs from the specified processing, communication, interface, control, and other requirements. As soon as the hardware architecture has been established, the target embedded controller for which the software is being developed must be simulated with sufficient fidelity to run the 3).

The DE gives the SW team the ability test the SW it develops (Fig. 3, step 1) in the VSIL (Fig. 3, steps 2-4). After replacing the controller ES with the DE, the software being developed may be compiled and loaded into the DE at any time for testing in the VSIL. All of the tests created to verify the system design can be used, without modification, for software verification. Additional tests must be added to verify that software has correctly implemented lower-level requirements whose detail hasn't been addressed at the system level (e.g. built-in-test, etc.).

After running the desired tests, the software development team analyzes the results and determines the cause of any failures. The team then corrects any identified faults, recompiles the revised modules, and retests the build in the VSIL (Fig. 3, steps 1-4). In practice, step 3 is performed once since the DE becomes an integral part of the VSIL following replacement of its ES counterpart. The VSIL is tightly coupled with the integrated SW development environment used by the SW teamthereby facilitating the code/compile/load/verify process. Some of the problems discovered may require the attention of the system designers. When this necessitates a system design change, the VSIL is revised & tested and redistributed to the SW development teams. In this manner, the software is always developed & tested in the most current system design -thereby eliminating the possibility of SW problems being introduced due to miscommunication of system design changes. The SW design/code/verify/debug loop is repeatedly executed until the final build passes all tests and until all paths through the code have been exercised in the VSIL. The software has thus been thoroughly verified and is ready for integration testing with the real flight hardware. It is worth noting that since the object code itself is tested in the VSIL, the real-time operating system (RTOS), any reused/COTS modules, and all newly developed software are verified together in the virtual target environment. The VSIL itself is an MS Windows-compatible application that interfaces with standard integrated development environment (IDE) tools. A VSIL is as easily used as a typical lab test setup (e.g. emulator, simulators, target hardware), and readily distributed to all project development personnel. Since the entire system and environment are modeled in the VSIL, modifications & refinements can be coded, validated, verified, and distributed to the entire team. VSIL revisions and verification tests may be controlled using standard configuration management tools & techniques. Lastly, the VSIL is purely virtual i.e. no hardware is required other than the Windows-based PC on which it runs.

Discussion

We have presented a new method of embedded systems and software V&V that closes the loop between system & software development activities. In so doing, the system and software development processes can now be connected through common verification tests. Finding and repairing software faults early in the project development cycle can lead to substantial savings (see sidebar: "Economics of Faultfinding" on page 5).

For example, requirements and communication induced errors like 98% of those discovered during the integration phase of the Voyager & Galileo spacecraft software project, can be found and repaired at one or perhaps more orders of magnitude lower cost.

Implications

Below is a summary list of some of the ways that the methods presented in this article may be of economic benefit to embedded software development: a. Discovery of system errors early in the development cycle where it is least costly to correct them. b. Reduce interpretation-induced SW faults due to ambiguities in system requirements. c. Improve ability for dynamic, non-invasive test of system & software response to failure conditions. d. Reduce software faults caused by breakdown in communication of system requirements changes. e. New capacity for empirical software V&V in cases where analysis was only viable means, for example: realistic fault injection & failure mode testing, complex digital signal processor designs, et al. f. Provide a highly viable means of verifying automatically generated code, reused software, and RTOS. Creating a system design with the type of ES discussed herein results in a verifiable system architecture that is readily translated into component-, and interface-level designs. When contracting out the development of subsystem software, the system-level verification tests can provide an excellent way to assure that the contractor has developed the software correctly. Because ES parts may be created with intrinsic failure modes that can be invoked dynamically under

Economics of Faultfinding

Estimates of the cost to find and correct software faults at each of the principal stages of a project have been publicized and widely referenced since 1976 when Boehm first published his study [START_REF] Boehm | Software Engineering[END_REF] on the subject. Cost numbers vary depending on the type of application for which the software is being developed but the common thread they all exhibit is the substantial increase in project costs caused by carrying problems from one development stage to the next. A report released in May 2002 by the National Institute of Standards & Technology (NIST) [START_REF] Tassey | The Economic Impacts of Inadequate Infrastructure for Software Testing[END_REF] contains a thorough analysis concluding that inadequate software testing costs the United States an estimated $59.5 billion annually. The 309-page NIST report is a well-considered treatise on the economic impact of inadequate software testing. While these numbers are extrapolated from software developed for the financial services and transportation applications (CAD, CAM, etc.) sectors, the message applies even more significantly to industries engaged in developing software for safety and mission critical applications such as aerospace, medical, defense, automotive, etc. Failures of safety/mission-critical software may result in harm to, or loss of human life and/or mission objectives such as in the case of the Therac-25 radiation overdose accidents [START_REF] Leveson | Safeware -System, Safety and Computers[END_REF] and the Ariane-5 maiden launch failure [START_REF] Leveson | The Role of Software in Spacecraft Accidents[END_REF]. The Therac-25 software caused severe radiation burns in numerous cancer patients before it was implicated. The cost of allowing the Ariane-5 software defect to pass into the operational phase has been estimated to be as high as $5 billion alone. NASA recently sponsored a study to evaluate the economic benefit of conducting Independent Validation & Verification (IV&V) during the development of safety-critical embedded systems [START_REF] Dabney | Return on Investment of Independent Verification and Validation Study Preliminary Phase 2B Report[END_REF]. This study presented cost-to-repair figures focused specifically on embedded systems projects. Figure 4 shows the relative cost to repair factorsconsidered to be conservative estimates for embedded systems -used in this study. The graph in Figure 4 tells us that an error introduced in the requirements phase will cost five times more to correct in the design phase than in the phase in which it was introduced. Correspondingly, it will cost ten times more to repair in the code phase, 50 times more in the test phase, 130 times more in the integration phase, and 368 times more when repaired during the operational phase. The graph also gives the cost multipliers for problems introduced in the design, code, test, and integration phases of the development cycle. test control, the system designer can empirically verify the specified system response to a variety of off-nominal conditions. This ability allows greater latitude in the type and number of tests that can be conducted when compared with what is economically viable in a hardware integration lab.

Verifying the VSIL

The VSIL is, in fact, a model of both the system being developed and the environment in which it is designed to interact. Before it can be of use we must have confidence that the VSIL represents its target adequately.

We have adopted an effective approach that is perhaps best described as "test-as-you-go." As parts are simulated to implement specific requirements, system-level tests are created at the same time to verify that they behave correctly. Part functionality may be developed and tested incrementally as requirements are implemented. At the end of this process, all VSIL parts have been implemented & verified and a basic set of systemlevel tests have been developed. Parts developed to a high-fidelity level may require a supplemental verification activity where the realworld equivalent part is used for comparison purposes. In the case of developing an instructionset-level CPU simulation, we run test code designed to verify instruction execution on a hardware development board and compare the results with the outcome of running the same code on the simulated part. The CPU parts we've developed are not cycleaccurate but are refined to where the instructions execute within an average of four percent of the hardware performance (works well for embedded software verification). This is in keeping with our philosophy of not implementing greater fidelity than necessary.

VSIL Development Tool

We developed our first avionics simulator more than a decade ago to save time verifying software modifications and to avoid contention for lab test resources. This initiative spawned the creation of IcoSim  , our general-purpose simulator development tool, and its companion SW developer's kit (SDK). In the second quarter of 2006, we plan to make IcoSim freely available to the general public by creating an open source project [11] whose use will be governed under either a General Public License (GPL) [START_REF] General | [END_REF] and/or a Lesser General Public License (LGPL) [13].

Tool Description

We currently give IcoSim away to our customers and since it is destined to become an open source project, the descriptive details provided herein are intended to promote an understanding how we accomplish what we've presented. Written in C++ and C, IcoSim allows the use of diverse part types ranging from low to high abstraction levels. It also supports the use of mixed mode parts such as analog, digital, mechanical, hydraulic, magnetic, electro-magnetic, et al. IcoSim is well suited to creating a VSIL for use in developing embedded systems & software because the simulated parts may be bounded exactly like their real-world counterparts. In other words the inputs and outputs of each virtual part are readily modeled after the behavior of their real-world part's digital, analog, mechanical, etc. I/O.

Once its behavior is verified, a virtual part may be identified with the same part number as its counterpart, and repeatedly used wherever system designs specify.

VSIL Parts Libraries

In addition to the NASA research that validated the methodology presented, this tool has been used to create VSILs for software verification on more than two-dozen avionics projects over the past decade. It is scalable to any size system and has been used for verification of software in single and dual-redundant avionics systems ranging in criticality from Radio Technical Communications for Aeronautics (RTCA) Defense Order (DO)-178B, level A (safety-critical) to level D (low criticality). It has also been used for verification of embedded digital signal processor (DSP) software implementing Kalman filter algorithms.

Our parts library includes instruction-set level simulations of many microprocessors in use today such as the MPC555, MPC750, MC68000, MC68332, DSP56005, DSP56302, DSP56309, I80196, I8051, I8096, I8097, I8798, et al. Numerous additional peripheral and "glue" parts are in the library as well as a host of actuators and sensors that have been created in support of various VSIL projects. We have also created a collection of parts that simulate many different data buses and protocols e.g.: ARINC 419, ARINC 739, MIL-STD-1553, TTP, ASCB, CSDB, AFDX, Ethernet, SPI, PCI, CAN, etc. To support testing with a VSIL, we have simulated standard laboratory test equipment such as oscilloscopes, signal generators, and the functional capability of microprocessor emulators. The VSIL is an ideal environment for gathering dynamic software metrics without instrumenting either the target operating system or the software.

Code path coverage, MCDC reports, throughput analysis, timing analysis, and many other helpful reports are readily produced in this environment with the addition of instructions to the test script.

Costs of VSIL Development

A VSIL is made by interconnecting objects at the lowest level of abstraction to make successively higher levels of functional parts until the required environment is complete. This hierarchical, modular approach maximizes the potential for part reuse on subsequent development projects. To be efficient at making a VSIL, each part is simulated only to the level of fidelity necessary to achieve ones goals. For example an aircraft rudder is attached to a sensor that reports its angular position to avionics subsystems as required. The sensor has a mechanical link to the rudder, has inertial properties, may have inductive coils, an armature, be excited by a 400 Hz reference, etc. While we could model all of these characteristics with great precision, it would be a waste of effort if our system only required the correct transfer function of rudder angle to sensor output at a given update rate. Since part fidelity is directly proportional to effort, being selective about where to incorporate higher fidelity is key to cost-effective VSIL creation. It is difficult to quantify the costs of creating a VSIL for system and SW development because of the large number of variables involved such as: Because of the part-oriented nature of the VSIL, the cost of creating a simulator for a given project will vary in proportion to the number and complexity of new parts that must be created.

Many new embedded designs reuse proven design elements from prior projects so the cost of developing simulators diminishes with successive applications.

Supplemental VSIL Benefits

The benefit of using a VSIL for embedded systems & software development increases with project size, with system complexity, and with geographic diversity of organizations and personnel contributing to the project. In addition to the cost benefits of early SW fault discovery, a VSIL can support a project in other important ways. Some of these benefits are directly measurable but others may have less tangible value. For example:

• When contracting out development of a subsystem, supplying the vendor with a VSIL and its system test suite can be a highly effective means of verifying that the SW conforms to the requirements. While not a rigorous analysis, one avionics company's post-project review of having used a VSIL for verification of their dual-redundant avionics SW revealed some attractive cost-benefits. Based on their findings they concluded that future projects could expect a 24% schedule savings, $130,000 direct savings on laboratory equipment, and realize an overall cost savings of 14% on an average $4.5 Million project. These estimates do not include the benefits of using a VSIL throughout the operational life of a product. There are many factors that influence the cost but a typical VSIL can be developed for about 5-10 percent of the overall project cost. This places the return on investment in the range of 40-180 percent for the above project. Experiences will no doubt vary from project to project, however, these estimates can provide useful guidance when assessing the life-cycle cost/benefit of using a VSIL for development.

Summary

The new method of embedded systems and software V&V presented here goes far beyond an incremental improvement to the status quo. While not a panacea, it does provide a cost-effective, proven means of:

• Ensuring that the target software has implemented all known and tested system requirements -prior to hardware integration. • Verifying automatically generated code, reused software, and the RTOS. • Verifying response of systems & software to a wide range of realistic, dynamic failures and offnominal scenarios. • Re-verifying software following system revisions & updates. • Ensuring that hardware redesigned for obsolescence is compatible with the software. • Verifying that new and upgraded peripherals and subsystems function correctly with the target system. The approach described provides a bridge between algorithm & model development tools, and the realworld system environment in which embedded algorithms must function. This method is a highly viable way to address a number of problems that hamper efficient embedded systems & software development.

Acknowledgement

We would like to thank the NASA Office of Safety and Mission Assurance for funding this effort under their Software Assurance Research Program, and the excellent team at the NASA IV&V Facility for their interest, support, and guidance during the course of our investigation.

Figure 3 :

 3 Figure 3: Closed-Loop Software Verification in Virtual System Integration Lab

Figure 4 :

 4 Figure 4: Relative Cost of Software Fault Propagation

•

  Number of parts to be simulated • Number of CPUs to be simulated • Experience of simulation engineer(s)

test teams apprised of changes to requirements 6. Inclusion of requirements for "defensive design" SYSTEM Design/Analyze/Test Model, Simulate, Prototype, ES, etc. SW Interpretation Requirements Debug Build Integration Test Design/Analyze/Test SYSTEM Design/Analyze/Test Model, Simulate, Prototype, ES, etc. SW Interpretation Requirements Debug Build Integration Test Design/Analyze/Test

	Internal 2% Internal 2%
	Interface Interface
	24% 24%
	Functional Functional
	74% 74%
	Figure 1: Fault Distribution
	3. Use of formal [and unambiguous] specification techniques
	4. Promotion of informal communication among teams
	5. Keeping development & Figure 2: Federated development process

  Re-verifying SW on obsolescence-driven hardware design changes. • Verification of system compatibility with upgrades to peripheral or subsystem units. • Eliminating or reducing reliance on test equipment set-ups that must be maintained to support SW changes following entry into service.

	• Development teams in local and remote
	locations can quickly re-verify their SW following
	system revisions that have been implemented &
	tested in a VSIL. Using standard configuration
	control procedures, the latest system revision
	can be distributed to all teams as soon as it is
	available.
	• Providing a VSIL to every programmer promotes
	a broader, "big-picture" understanding of the
	system. Every programmer tests on the whole
	system, every time.
	• Testing in a VSIL reduces the dependence on
	laboratory test stations; consequently, fewer are
	required.
	• Less dependence on laboratory test equipment
	reduces resource-contention delays during
	development.
	• A VSIL may be helpful in the operational phase
	of a project for:
	• Software re-verification following upgrade
	modifications with full regression testing.
	•

Glossary

AFDX:

Avionics