Fault-Model-Based Test Generation for Embedded Software

1 Introduction

Over the last decade, cars have become a kind of mobile software platform. There are tens of processors (Electronic Control Units, ECU) on board of a vehicle; they are communicating with each other via several bus systems, and software has a major influence on the performance and safety of a vehicle. The software embedded in the car subsystems becomes increasingly complex, and it comes in many variants, reflecting the context of different types of vehicles, the manufacturer-specific physical realization, versions over time etc. Testing such embedded software becomes increasingly challenging and has been moving away from test drives under various conditions to automated tests performed on test benches which can partly or totally simulated the car as a physical system.

But for the reasons stated above, namely complexity of the software and its variation, generating the test suites becomes demanding and time consuming and demands for computer support. Automating the generation of such tests based on a specification of the desired behavior of the software together with the physical system promises benefits regarding both the required efforts and the completeness of the result.

In [Struss 94], we presented the theoretical and technical foundations for automated test generation for physical systems based on (relational) models of their (nominal and faulty) behavior.

An extension of this approach to cover also software would be highly beneficial, because it would provide a coherent solution to testing both physical systems and their embedded software. More concretely, the software test could start from a specification of the intended behavior of the entire system (including physical components and software), and also the tests could reflect the particular nature of the embedded software, namely using stimuli and observations of the physical system rather than directly of the software system.

The case study described in this paper concerns a real-life example (the measurement and computation of the fuel level in a vehicle tank) based on the requirement specification document of a car manufacturer.

We continue by summarizing the basis for our relationbased implementation of test generation. In order to extend it to software, the requirement specification has to be turned into a relational representation. In the respective document, the skeleton of this specification is provided in a state-chart manner. Therefore, section 3 of this paper proposes a behavior specification as a special finite state machine, and section 4 presents the transformation into a relational representation.

A major challenge in the application of the test generation algorithm to software is to provide relevant and appropriate fault models against which the software should be tested (section 5). The final sections present results of the case study and discuss problems and insights.

2 The Background: Model-based Test Generation

The goal of this work is not to develop a new test generation algorithm, but apply it to (devices with embedded) software systems. Therefore, we only briefly summarize the theoretical and technical foundations and refer to [Struss 94, 07] for more details.

Testing attempts to influence a system in a way that reveals information for discriminating between different hypotheses about the system (e.g. about the kind of fault that is present).

Definition (Discriminating Test Input)

Let TI = {ti} be the set of possible test inputs (stimuli), OBS = {obs} the set of possible observations (system responses), and H = {hi} a set of hypotheses.

ti ∈ TI is called a definitely discriminating test input for H if

(i) ∀ hi ∈H ∃ obs ∈OBS ti ∧ hi ∧ obs ⊥ , and

(ii) ∀ hi ∈ H ∀ obs ∈ OBS

if ti ∧ hi ∧ obs ⊥

then ∀ hj ≠ hi ti ∧ hj ∧ obs ⊥.

ti is a possibly discriminating test input if

• (ii´) ∀ hi ∈ H ∃ obs ∈ OBS such that

ti ∧ hi ∧ obs ⊥ and ∀ hj ≠ hi ti ∧ hj ∧ obs ⊥. Testing for confirming (or refuting) a particular hypothesis h0 out of the set H requires only discrimination between h0 and any other hypothesis.

Definition (Confirming Test Input Set)

{tik} = TI´ ⊂ TI is called a discriminating test input set for H = {hi} and h0 ∈ H if

∀ hj with h0≠ hj ∃ tik ∈ TI´ such that

tik is a (definitely or possibly) discriminating test input for {h0, hj}.

It is called definitely confirming if all tik are definitely discriminating, and possibly confirming otherwise. It is called minimal if it has no proper subset TI´´⊂ TI´ which is discriminating.

Remark

Refutation of all hypotheses hj ≠ h0 implies h0 only, if we assume that the set H is complete, i.e. ∨i hi

[Struss 94] treats test generation for physical systems, with hypotheses concerning their (correct or possible faulty) behavior, which is assumed to be characterized by a vector vS = (v1, v2, v3, … , vn) of system variables with domains

DOM(vS) = DOM(v1) × DOM(v2) × … × DOM(vn).

Then a hypothesis hi ∈ H is given as a relation

For conformity testing, h0 is given by R0 = ROK, the model of correct behavior. Observations are value assignments to a subvector of the variables, vobs, and also the stimuli are described by assigning values to a vector vcause of susceptible ("causal" or input) variables. We make the reasonable assumption that we always know the applied stimulus which means the causal variables are a subvector of the observable ones: vcause ⊆ vobs.

The basic idea underlying model-based test generation ([Struss 94]) is that the construction of test inputs is done by computing them from the observable differences of the relations that represent the various hypotheses. Figure 1 illustrates this. Firstly, for testing, only the observables matter. Accordingly, Fig. 1 presents only the projections, pobs(Ri), pobs(Rj), of two relations, R1 and R2, (possibly defined over a large set of variables) to the observable variables. The vertical axis represents the causal variables, whereas the horizontal axis shows the other observable variables (representing the observable system response).

To construct a (definitely) discriminating test input, we have to avoid stimuli that can lead to the same observable system response for both relations (the shaded region in Fig. 1). This provides the intuition behind

Lemma 1

If hi=Ri, hj=Rj, TI=DOM(vcause), and OBS=DOM(vobs), then

is the set of definitely discriminating test inputs for {hi, hj}.

Please, note that we assume that the projections of Ri and Rj cover the entire domain of the causal variables which corresponds to condition (i) in the definition of the test input.

The sets DTIij for all pairs {hi, hj} provide the space for constructing (minimal) discriminating test input sets.

Lemma 2

The (minimal) hitting sets of the set {DTI0j} are the (minimal) definitely confirming test input sets for H, h0.

A hitting set of a set of sets {Ai} is defined by having a nonempty intersection with each Ai. (Please, note that Lemma 2 has only the purpose to characterize all discriminating test input sets. Since we need only one test input to perform the test, we are not bothered by the complexity of computing all hitting sets.)

This way, the number of tests constructed can be less than the number of hypotheses different from h0. If the tests have a fixed cost associated, then the cheapest test set can be found among the minimal sets.

3 State Charts for Specification of Software Requirements

Extending the solution sketched above to software testing raises some fundamental issues. Firstly, it assumes a behavior description in terms of relations. (Embedded) software, however, is usually specified and described in terms of its (discrete) dynamic features. Secondly, and even more fundamentally, in this case testing is not concerned with faults in a physical device, but bugs in the design of an artifact. In the work described here, we address the second problem by

• starting from the specification and model faults as (classes of) deviations from this specification, and the first one by

• transforming a widely used representation of such specifications into a relational representation.

State charts and finite state machines (FSM) are frequently used in specifications of software requirements. Figure 2 shows a FSM extracted from a requirement specification produced by an automotive manufacturer. The machine describes a process to detect refueling of a passenger car: if the car stops for more than 8 seconds and if a remarkably higher tank filling is detected then the software sets the output flag RFD (ReFilling Detected) to true. Otherwise RFD is always false.

Let us define the used type of FSM in a more formal way: an automata m a = (E,(I,O,L),(S,A),T,s 0 ,l 0 ) is described by

• the set E of events e1, …, enE,
• the ordered set I of input variables i1,… ,inI,
• the ordered set O of output variables o1, …, onO,
• the ordered set L of local variables l1, …, lnL,
• the set S of control states s1, …, snS,
• the set A of state expressions a1, …, anS defining a relation δa,i ⊂ dom(I) x dom(L) x dom(O) x dom(L) for each state si,
• the set T of transitions T1, …, TnT with Ti ⊂ S x P(dom(E) x dom(I) x dom(L)) x S where P(X) denotes to the power set of X,
• the initial control state s 0 and
• the vector l 0 with the initial values of L.

Each machine has a special local variable l1 called stime indicating the time elapsed since the machine has entered the actual control state. It is special because each time the control state is switched, the variable is reset automatically. Every variable v in I, O or L has a finite domain dom(v).

With the inputs (i 1 , …, i n ) and the events (e 1 , …, e n ) the machine produces the outputs (o 1 , …, o n ) according to the following operating sequence:

1. Set t = 0.
2. Evaluate the state expression ai of the current state s t =si to calculate the new values of the output and local variables : (i t+1 , l t , o t+1 , l t+1 ) ∈ δa,i
3. If T contains a transition Ti=(ssrc, IF, sdst) with ssrc=s t and (e t+1 ,i t+1 ,l t+1 )∈IF then set s t+1 =sdst, otherwise set s t+1 =s t .
4. If s t+1≠ s t then reset stime.
5. Set t=t+1
6. Jump to Step 2.

In our example, the FSM has two input variables car moves and time, one output variable RFD, stime as a the only local variable and the events nothing, car starts moving, car stops and increased tank filling. The variable time is set according to the time elapsed since the previous event occurred. Its value is always added to the stime variable, which could be used in a precondition of a transition.

Dependent on the chosen set of input variables I and the events E, the test generation system needs more information in order to produce meaningful tests, because the values of some variables might depend on the occurrence of an event. E.g. if car moves t =true then the event car starts moving can not occur next. In our example, the following rules are necessary:

car moves t = false ∧ car moves t+1 = true⇔ e t = car starts moving

car moves t =true ∧ car moves t+1 =false ⇔ e t =car stops

In the next section, we describe how the FSM is transformed into a relational representation.

4 Transformation of a FSM into a Compositional, Relational Representation

The conversion of a FSM of the described type produces a compositional model, i.e. a model that preserves the structure and the elements of the FSM. As a consequence, a modification of one part of the FSM results in the modification of only one part of the compositional model (As it will turn out this is not fully accomplished for fundamental reasons). The compositional model also provides the possibility of relating "defects" to the various elements (and also to record and trace their effects e.g. in diagnosis).

The basic step is the transformation of the entire FSM into a component C1Step and its internal structure (Figure 3). C1Step takes the state s t , values of local variables l t , the input vector i t+1 , and the event e t+1 and generates the subsequent state s t+1 , the new values of local variables l t+1 , and the output vector o t+1 , reproducing the calculations of the FSM in one step (one iteration in the listed operation sequence). C1Step consists of the two components CState and CTrans. The former encodes the state expressions δa,i, while CTrans represents the transitions Ti.

CState constrains s t , l t , l t+1 , o t+1 and i t+1 independently from the next event e t+1 . It contains nS atomic components Cai, one for each state expression ai, which are placed in parallel (Figure 4). The expressions are conditioned by their s t

t

i t+1

CState

o t+1

Figure 3: C1Step and its internal structure

e t+1

i t+1

CTn

CTDefault

Figure 5: CTrans and its internal structure

respective state and, hence, exactly one component Cai defines the proper values of the variables. Hence, a change in one ai results in the modification of only one component and a maximum of locality is achieved.

Cai determines l t+1 and o t+1 depending on s t , l t and i t+1 according to ai. The relational model RCai of such an atomic component is:

CTrans correlates all the variables except the output o t+1 and consists of nT parallel atomic components CTi, one for each transition, and a component CTDefault (Figure 5). Exactly one component CTi determines s t+1 depending on s t , l t+1 , i t+1 and e t+1 according to Ti. The relational model RCTi of these atomic components are:

In all cases where no transition is executed, the atomic component CTDefault defines the values according to the automata definition: the state does not change, s t+1 = s t . Therefore its relation is

Now one iteration of the operating sequence can be simulated. To simulate n iterations, C1Step is copied n times and placed in series. But this shows also a limitation: the model can simulate only a fixed number of steps, and the more C1Step components are interconnected the bigger the model (the relation of the entire model) grows.

The number of steps needed for test generation depends on the respective FSM and the failure. In order to discriminate the ok-model from the failure model, n has to be at least as long as the shortest path in which effects of the fault becomes observable. One solution to this problem could be to start with a small number of steps and increase it until the system produces some tests.

Each vector (s 0 ,l 0 ,i 1 ,e 1 ,...,i n ,e n ) represents a possible test input ti of a n-step-model. Thus, ti comprises n parts, one for each time step and, hence, expresses a temporal sequence of stimuli. The same holds for every observation: obs = (o 1 ,...,o n ).

A violation of locality becomes evident when the set of transitions is changed, e.g. by deleting, adding, or modifying one. In such cases, not only the respective CTi component has to be removed, added, or changed, but also the default behavior in CTDefault has to be updated.

5 Fault Models

As described in section 2, our approach to testing is based on trying to confirm the correct behavior by refuting the models of possible faulty behaviors. When testing systems that are composed of physical components only, these models are obtained in a natural way from the fault models of elementary components, which usually have a small set of (qualitatively different) foreseeable misbehaviors due to the underlying physics. Faults due to additional interactions among components are either neglected or have to be anticipated and manifested in the model. In summary, for physical systems, the specific realization of the system determines the possible kinds of misbehavior, and testing compares them to a situation where all components work properly.

In software testing (but also in debugging designs of hardware), this does not apply. First, the space of possible faults is not restricted by physical laws, but only by the creativity of the software developer when making mistakes. This space is infinite, and the occurrence of structural faults is the rule rather than an exception. Second, the assumption that correct functioning of all (software) components assures the achievement of the intended overall behavior does not hold. This marks an important difference between testing physical artifacts and software (and also hardware design). For the former, we can usually assume it was designed correctly (which is why correct components together will perform correctly), but for the latter we cannot. It is just the opposite: testing aims at revealing design faults.

In our application, the situation is complicated by the fact that it starts from the functional requirements rather than a

e t+1

CTrans s t+1

l t+1

(l t+1 ,s t )

e t+1

i t+1

CT1

CT2

...

s t+1

detailed software design or even the code which might suggest certain types of bugs to check for (e.g. no termination of a while loop). On the positive side, this may lead to a smaller, qualitatively characterized set of possible misbehaviors.

In our example about the detection of fuel refilling, a failure one might think of is that the software does not poll the car's movement during driving and therefore does not detect a stop. This means the machine stays in its current control state instead of performing T3. The Transition T3 could be seen as deleted. The construction of such a failure model could be achieved by applying the following operator on the ok-model:

remove-if-condition: (m a , Ti) (m a ') where m a ' = m a [IFi ∅] and Ti=(s t ,IFi,s t+1 ).

Operation m a [A B] results in a FSM m a' which is equal to m a except that element A is substituted with B.

Another faulty behavior would occur, if the software treats an increased tank level after 8sec in standstill exactly as if the car starts moving. W.r.t. the FSM, this means executing T6 instead of T7. The proper failure model can be constructed by the operator

move-if-condition-to: (m a ,Ti, Tj)

(m a ')

where m a ' = m a [IFi IFi∪ IFj, IFj ∅] and Ti=(s t ,IFi,s t+1 ).

Similarly, other faults can be specified, which for instance, change the source or destination state, or modify the state expression.

6 Results

In this section, the discrimination of the failure models

• mdelT3 = remove-if-condition(mok,T3)
• mdelT5 = remove-if-condition(mok,T5)

from the ok model is discussed. A relational model that simulates 7 steps of the FSM is used here.

To discriminate the two models mok and mdelT5, 36 different types of tests are generated. Figure 6 lists them, where '*' stands for any value in the domain of the respective variable. The input sequence of the first test could be formulated more naturally as following:

1. starting from the initial state one waits 4s long,
2. then the car starts moving and
3. directly after this, it stops again and
4. one waits again 4s.
5. After waiting a third time 4s,
6. a significant increase of the tank filling is detected.

In test 2, the second and the third event occurring are "increased tank filling". These events are unnecessary. Without these two steps the test input still discriminates the fault from the ok model. The reason that the system generates these is the fixed number of steps of the relational model. So some

steps have to be filled with events having no effects but serving as placeholders. This explains why so many different tests are generated. Eliminating unnecessary stimuli is addressed in [Struss 07].

Only two types of tests are generated to discriminate the two models mok and mdelT3. They are also among the tests of the previous discrimination: one is the first test discussed above, the other causes the trajectory shown in Figure 7.

Tests discriminating between both pairs (mok from mdelT3 as well from mdelT5) are the two from the second discrimination, because these are also in the generated set of the second one. In our example, this is not surprising. To distinguish between an ok automata and a fault automata where any transition is deleted, one of these both has always to reach S6, because this is the only state where the output is different to the one of the others.

7 RelatedWork

Classical approaches generates tests optimized in respect to a certain coverage criteria like state, transition or MCDC coverage [Beizer 95]. In our approach, with carefully chosen sets of failure models tests will be generated that achieve also classical coverage criteria.

To obtain a state coverage, for example, a set of failure models Mfail could be constructed as follows. For each state si, there exists one failure model mfail,i in Mfail which differs from the ok-model in the output of state expression ai only. The outputs of these two models are complementary. For the case that mok is a deterministic automaton, the equivalence is proven in [Esser 05].

Also the diagnoser of [Sampath 96] could be used for test generation (although the authors are not aware of any publication describing this): In this approach a diagnoser is generated from the system model, both FSMs, for calculating diagnosis and diagnosability. The transitions of a diagnoser are labeled with observable events, whereas the states are labeled with the behavior modes consistent with the events that occurred so far. For test generation, the set of observable events could be split into causal and non-causal observable events. Then, the task is to find a causal event sequence where each diagnoser path consistent with these causal events and any possible non-causal observables have either only a ok-label or no ok-label at all. Each sequence of causal and observable events is a valid test for the modeled failures. We expect that the two approaches can be transformed into each other. An analysis and comparison of the efficiency would be interesting.

8 Discussion

The problem which is central to our approach is finding appropriate fault models representing realistic and relevant faults. On the one hand, they are difficult to obtain for software and even more so, when one starts from a functional specification, as we do. This may seem to be a disadvantage in comparison with the other testing heuristics, like coverage criteria. However, it is not true that they do not involve fault models. In fact, they are based on assumptions about possible faults, but these are implicit. The fact that our approach makes them explicit is a major advantage and the basis for more progress. It also bears the potential to generate tests whose power and coverage grows together with the refinement of the specification during the development process.

We consider the results of this experiment as encouraging and will continue this work in a project with Audi AG. It has raised a number of issues that need to be addressed in this project.

A basic one concerns the question whether the current modeling formalism, a specific type of finite state machine, is appropriate. This has several aspects: First, it has to be checked whether it is expressive enough to capture the requirements on embedded software. Second, the impact of the representation on the complexity of the algorithm has to be analyzed (Handling absolute time is an important issue, as stated below). These aspects have to be confronted with the most important guideline: appropriateness for current practice.

4

Figure 7: trajectory of the FSM for a test input discriminating mok frommdelT3

Our project is not an academic exercise, but aims at tools that can be easily used in the actual work process. Current requirement specifications at the development stage that matters in our context comprise mainly natural language text together with a few formal or semi-formal elements, such as state charts (provided they are written at all!). Assuming the existence of formal, executable specifications is unrealistic. Any formal representation of the requirements as we need them as an input to our tools needs to take into account whether they can be produced in the current process, by the staff given its education and background, and the limited efforts that can be spent in a real project where meeting deadlines and reducing development time has top priority. Whenever the use of new tools and additional work is required, this needs a rigorous justification by a significant pay-off (in our case in the time spent on testing and the quality of its results).

On the technical side, an adequate handling of time is needed. In our example, time elapsing in a particular state (e.g. "8s with no motion") seems to be local. However, the respective event has to be stated in a way that can be interpreted properly in other states as well, which may have been reached due to a fault. Introducing global absolute time tends to enforce using the smallest time increments required for some state and event, which appears prohibitive.

Acknowledgements

Thanks to Torsten Strobel who implemented the algorithm, Oskar Dressler for discussions and support of this work, the Model-based Systems and Qualitative Modeling Group at the Technical University of Munich and the reviewers for their helpful comments. We also thank Audi AG, Ingolstadt, and, in particular, Reinhard Schieber for support of this work.