Model-Based Optimization of Testing through Reduction of Stimuli

1 Introduction

Testing of physical systems is a frequent task in industry: During or after manufacturing of a product it has to be checked whether the process worked properly and the product behaves as designed. Under operation, wearing und breaking of parts may lead to system failures, and it has to be investigated whether and where a fault occurred and of what kind it is. Even though some testing, particularly in manufacturing, is performed automatically and requires no or limited human intervention, saving time and efforts spent on testing is an economical requirement. This becomes more important with the amount of necessary human actions, such as disassembly of parts of a vehicle in a workshop, and the cost of downtime of large equipment.

Designing effective test sets or sequences is a demanding and time consuming task, particularly when the systems to be tested come in many variants such as cars and their subsystems. In [Struss 94], we presented the theoretical foundations and implemented algorithms to generate tests for a device based on behavior models of its components.

Designing efficient tests is a challenge for the reasons stated above. Our solution presented in [Struss 94] addressed this in one way: it searches for tests that could serve several purposes at once, i.e ruling out more than one hypothesis. This increases efficiency of testing by reducing the number of tests. However, it was ignorant of another source of efficiency: the reduction of the efforts spent on an individual test. More precisely: so far, the question answered was "Given a set of possible stimuli to a system and a set of observables, how can we stimulate the system such that the observables reveal information about the actual behavior mode of the system?" Now, we address the problem of determining minimal sets of stimuli. When combined with an estimation of costs of the respective actions, the solution will contribute to cost-optimal testing. However, this paper is neither addressing costs nor the task of organizing the tests in a sequence or tree, which are different issues.

In the following section, we will introduce a formal definition and representation of tests based on a relational representation of the behavior model of a system or, more generally, the hypotheses to be tested. The basis for this is the manipulation of finite relations as they are given by quali-tative behavior models.

Section 3 provides the formal foundations for test reduction by defining and characterizing redundancy in tests in terms of variables that are irrelevant for a particular test. The algorithms are presented in section 4. Finally, we discuss the practical impact of the solution and the open problems.

2 The Background: Model-based Test Generation

In the most general way, testing aims at finding out which hypothesis out of a set H is correct (if any) by stimulating a system such that the available observations of the system responses to the stimuli refute all but one hypotheses (or even all of them).

This is captured by the following definition.

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 ⊥.

In this definition, condition (i) expresses that there exists an observable system response for each hypothesis under the test input. It also implies that test inputs are consistent with all hypotheses. i.e. we are able to apply the stimulus, because it is causally independent of the hypotheses. Condition (ii) formulates the requirement that the resulting observation guarantees that at most one hypothesis will not be refuted, while (ii') states that each hypothesis may generate an observation that refutes all others.

Usually, one stimulus is not enough to perform the discrimination task which motivates the following definition.

Definition (Discriminating Test Input Set)

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

∀ hi, hj with hi ≠ hj ∃ tik ∈ TI´ such that

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

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

Such logical characterizations (see also [McIlraith-Reiter 92]) are too general to serve as a basis for the development of an appropriate representation and algorithms for test generation. Here, the hypotheses correspond to assumptions about the correct or possible faulty behavior of the system to be tested. They are usually given by equations and implemented by constraints, and test inputs and observations can be described as value assignments to system variables.

The system behavior 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(v3) × … × DOM(vn). Then a hypothesis hi ∈ H is given as a relation

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:

Since the focus of this paper is not on test generation and our solution to test reduction is independent of the way the tests were produced, we only briefly summarize the foundation for automated model-based test generation and refer to for [Struss 94] details. The basic idea is to construct test inputs 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, Figure 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 (which represent the observable response of the system).

To construct a (definitely) discriminating test input, we have to avoid stimuli that can lead to the same observable system response for both relations, i.e. stimuli that may lead to an observation in the intersection

shaded in Figure 1. These test inputs we find by projecting the intersection to the causal variables:

The complement of this is the complete set of all test inputs that are guaranteed to produce different system responses under the two hypotheses:

Lemma 1

If hi=Ri, hj=Rj, TI=DOM(vcause), and OBS=DOM(vobs), then DTIij is the set of all 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.

We only mention the fact, that, when applying tests in practice, one may have to avoid certain stimuli because they carry the risk of damaging or destroying the system or to create catastrophic effects as long as certain faults have not been ruled out. In this case, the admissible test inputs are given by some set Radm ⊆ DOM(vcause), and we obtain

In a similar way as DTIij, we can compute the set of test inputs that are guaranteed to create indistinguishable observable responses under both hypotheses, i.e. they cannot produce observations in the difference of the relations:

(pobs(Ri) \ pobs(Rj)) ∪ (pobs(Rj) \ pobs(Ri)).

Then the non-discriminating test inputs are

NTIij =

DOM(vcause)\ pcause((pobs(Rj)\ pobs(Ri)) ∪ (pobs(Ri)\ pobs(Rj))) All other test inputs may or may not lead to discrimination.

Lemma 2

The set of all possibly discriminating test inputs for a pair of hypotheses {hi, hj} is given by

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

Lemma 3

The (minimal) hitting sets of the set {DTIij} are the (minimal) definitely discriminating test input sets.

A hitting set of a set of sets {Ai} is defined by having a non-empty intersection with each Ai. (Please, note that Lemma 3 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 necessary pairwise discrimination between n hypotheses, n 2 - n. If the tests have a fixed cost associated, then the cheapest test set can be found among the minimal sets. However, it is worth noting that the test input sets are the minimal ones that guarantee the discrimination among the hypotheses in H. In practice, only a subset of the tests may have to be executed, because some of them refute more hypotheses than guaranteed (because they are a possibly discriminating test for some other pair of hypotheses) and render other tests unnecessary.

The computation is based on operations on relations, such as intersection and projection, and will usually practically work only on finite relations. Qualitative abstraction can generate such representations for continuous models and, hence, enable a broad applicability of the algorithm. The many existing test generation algorithms for digital circuits are specializations of it (provided they are sound and complete). Of course, they can exploit the special Boolean domain and, hence, may be more efficient than our general algorithm.

The algorithm has been implemented based on commercial software components of OCC'M's RAZ'R ([OCC'M 05]) which provide a representation and operations of relations as ordered multiple decision diagrams (OMDD). The input is given by constraint models of correct and faulty behavior of components taken from a library which are aggregated according to a structural description. These models are the same ones that can and have been used for model-based diagnosis and detectability and discriminability analysis.

It is important to note that the required operations on the relations are applied to the observable variables only (including the causal variables). The projection of the entire relation Ri to this space can be understood as producing a black box model that directly relates the stimuli and the observable response. In many relevant applications, this space will be predefined and small. For instance, when testing of car subsystems exploits the on-board actuators and sensors only, this may involve some 10 - 20 variables or so. The entire workshop diagnosis task has more potential probing points, but still involves only a small subset of the variables in the entire behavior relation Ri.

Finally, we mention that probabilities (of hypotheses and observations) can be used to optimize test sets ([Struss 94a], [Vatcheva-de Jong-Mars 02]).

3 Different Kinds of Irrelevant Causal Variables

In the tests characterized by Lemma 1, test inputs are tuples of values for all available causal variables, and the guarantee for discrimination is related to all specified observables. However, it may be the case, that a generated test is redundant in the sense that already of subset of inputs and/or observations would provide the same information for discrimination. This is important, because costs are often related to the number of stimuli and observation actions. If we can reduce individual tests to the necessary stimuli and/or observations only, this will contribute to reducing costs for testing.

In the following, we will provide the foundations for reducing the set of input variables. More details can be found in [Strobel 04].

Let DTIij ⊆ DOM(vcause) be the set of definitely discriminating test inputs. The question is whether there is a subvector v'cause ⊆ vcause that can be ignored in some way without losing discrimination information provided by the test. Rather than computing the set of test inputs for various subsets of the causal variables to answer this question, we will identify irrelevant causal variables by analyzing DTIij.

A closer look reveals that a causal variable can be irrelevant in different ways that have a different impact on the generation and application of tests. Let us first illustrate these cases by simple examples and then define them formally.

Suppose you want to test whether the light bulb L in the tiny circuit of Figure 2 works or is defect (open). The possible stimuli are opening and closing of switches S1 and S2, and L can be observed. If we assume that resistor R is not too small, all one has to do is close S1 and observe whether or not L is lit (assuming there is a voltage supply). For this test, the position of S2 is totally irrelevant: whatever its state may be, it does not influence the actions we have to perform.

Regarding the circuit in Figure 3, we can observe the following: the position of switch S1 is irrelevant in the sense that we can test lamp L regardless of whether it is up or down. However, it is not totally irrelevant: in contrast to the first case, the appropriate test inputs depend on the position. For S1 up, S2 must be closed; otherwise, S3 has to be closed. This means, the position of S1 has to be known in order to perform a test, but it does not have to be influenced which allows for omission of an action. We call such a variable weakly irrelevant (in the lack of a better term).

The same circuit can be used to illustrate a third kind of irrelevance of a causal variable: the position of S2 is irrelevant if S1 is in down position. Hence, it is not totally irrelevant, but only under certain conditions. This is still

practically important, because once the condition is satisfied, we can save by avoiding actions related to S2's position. This variable is conditionally irrelevant, and so is S3's position, of course.

To generalize the intuition gained from the examples and to formalize them: for some subvector v'cause ⊆ vcause we distinguish the following cases (for which Figure 4 shows abstract examples): for all value assignments from DOM(v'cause), DTIij can contain

1. the same set of stimuli for the remaining causal variables (total irrelevance)
2. some set of stimuli for the remaining causal variables (weak irrelevance)
3. the same set of stimuli for the remaining causal variables under some restriction of the values of the remaining causal variables (conditional irrelevance).

Figure 4 displays the sets DTI in the plain of causal variables (not the plain of all observables as Figure 1), where the vertical axis corresponds to the irrelevant variable (or subvector of variables) v'cause, while the horizontal axis represents the remaining ones. In case (i), DTI is the cross product of the entire domain of v'cause and a certain value assignment to the remaining variables. Case (ii) can be characterized by the fact that the projection of DTI to v'cause covers the entire domain. And case (iii) implies that DTI has a subset that is obtained as the cross product DOM( v'cause) and a set of tuples of the remaining variables (indicated by dotted lines in Figure 4).

This motivates the following definitions:

Definition (Irrelevance of causal variables)

Let DTI ⊂ DOM(vcause) be the complete set of definitely discriminating test inputs for two hypotheses. A subset of causal variables v'cause ⊆ vcause is called:

• (i) totally irrelevant if DTI = pvcause\v'cause (DTI) x DOM(v'cause)
• (ii) weakly irrelevant if

pv'cause (DTI) = DOM(v'cause)

• (iii) conditionally irrelevant if there is a non-empty subset DTI'⊂ DTI such that

As suggested by Figure 4, there are implication relations among the three types of irrelevance, which can be easily proved based on the above definition.

Lemma 4

If v'cause is totally irrelevant

v'cause is also conditionally irrelevant.

If v'cause is conditionally irrelevant

v'cause is also weakly irrelevant.

The goal of identifying sets of irrelevant causal variables seems to imply that one has to consider the power set of the causal variables. However, this is not the case due to the following lemma.

Lemma 5

(v1) and (v2) are both totally irrelevant

⇔ v'cause = (v1, v2) is totally irrelevant.

(v1) and (v2) are both weakly irrelevant

⇔ v'cause = (v1, v2) is weakly irrelevant.

This allows us to investigate this kind of irrelevance independently for each variable and then comprise them in one set, which makes the check linear in the number of causal variables. However, a similar lemma does not apply to conditionally irrelevant variables.

Remark

If (v1) and (v2) are both conditionally irrelevant, then v'cause = (v1, v2) is not necessarily conditionally irrelevant.

Obviously, to establish conditional irrelevance of the pair of variables, the conditions for the irrelevance of the two variables would have to have a non-empty intersection. But Figure 3 provides an example in which they are even exclusive: the position of S2 is irrelevant under conditions that require a particular state of S3 and vice versa.

4 Test Reduction

Based on the definitions and lemmata in the previous section, we developed algorithms for the automated reduction of tests. Whether they have been generated by an algorithm like the one sketched in section 2 or by human experts is irrelevant, as long as they can be represented in the relational style.

Firstly, we exploit lemma 5: we start with the test input set for a maximal set of causal variables and then analyze irrelevance of each single causal variable.

Secondly, we check for weak irrelevance first, because lemma 4 allows ruling out also the other kinds of irrelevance in the negative case. This check can be based directly on the definition of weak irrelevance and is formally described as follows.

Lemma 6

Let vk be a causal variable, pk the projection to this variable, and DTI a set of definitely discriminating test inputs.

If pk (DTI) = DOM (vk) then vk is weakly irrelevant to DTI. If pk (DTI) ≠ DOM (vk) then vk is not weakly, conditionally, or totally

irrelevant to DTI.

In case of a weakly irrelevant variable we can check for conditional and total irrelevance. To get the idea underlying this test, a glance at the abstract example of Figure 4 may be helpful. We have to check whether there exists a non-empty DTI´ ⊂ DTI such that

p-k (DTI´ ) × Dom(Vk) ⊂ DTI´,

where p-k is the projection to the causal variables except vk: vcause\ {vk}.

We do so by computing the projection of the maximal DTI´

DTI´-k := p-k (DTI´)

and checking whether it is empty, and we compute it by computing its complement.

DTI´-k comprises all value assignments to vcause\{vk} that when combined with arbitrary values of vk always yield a test input of DTI. Hence, its complement contains all value assignments that can be combined with at least one value of vk to yield a test input that does not lie in DTI, but in its complement:

DOM(vcause\{vk})\ DTI´-k = {v-k,0 ∈DOM(vcause\{vk}) ∃ vk,0 ∈DOM(vk) ∧ v-k,0 ° vk,0 ∈ DOM(vcause)\ DTI}.

But this is the projection of the complement of DTI: p-k (DOM(vcause)\ DTI).

This yields the following lemma which underlies the second check.

Lemma 7

Let vk be a causal variable, p-k the projection to the other causal variables, and DTI a non-empty set of definitely discriminating test inputs. Furthermore, let

DTI´-k := DOM(vcause\ {vk})\ p-k ( DOM(vcause)\ DTI ). If DTI´-k = ∅ then vk is not conditionally or totally irrelevant to DTI. If DTI´-k ≠ ∅ then vk is conditionally irrelevant to DTI If DTI´-k = p-k (DTI) the vk is totally irrelevant to DTI.

Please note that DTI´-k represents the condition under which vk is irrelevant. This can be used for investigating the relationship of these conditions for different causal variables. The third implication of the lemma simply reflects the fact that total irrelevance is obtained if the condition comprises all value assignments to the other causal variables that occur in DTI.

This establishes an algorithm for determining whether a causal variable is irrelevant and if so, of what type:

IF pk (DTI) = DOM(vk) THEN IF DTI´-k = ∅ THEN "WEAKLY IRRELEVANT" ELSE IF DTI´-k = p-k (DTI) THEN "TOTALLY IRRELEVANT" ELSE "IRRELEVANT UNDER DTI´-k" ELSE "NOT IRRELEVANT"

Based on the results of this algorithm, the irrelevant variables can be removed from DTI by projection yielding a simplified and cheaper test input set.

What we have presented for the case of definitely discriminating test input sets can obviously be applied in the same way to possibly discriminating test inputs.

5 Discussion and Future Challenges

The generation of a set of test input sets (with or without the reduction described here) provides the starting point for different further processing and use of this information. One can select one test input from each set and generate a fixed sequence or decision tree of tests to be applied. The information could also be used in a dynamic way by making the choice of the next test dependent on the current situation. A characterization of the situation can involve two aspects: firstly, the hypotheses actually refuted so far. We emphasize again, that this is not completely fixed by the tests executed so far, because some of them may have refuted all hypotheses that they can discriminate, and also they may have refuted more hypotheses than were guaranteed to be refuted. Secondly, one can choose the next test based on the current state of the system in order to minimize the number of stimuli that have to be changed.

The different types of irrelevance have a different impact on these strategies. Obviously, totally irrelevant variables can be eliminated from the respective test inputs, i.e. they do not have to be considered for the respective test actions. However, unless they are irrelevant to all test input sets in the set, they have to be observed during the testing, because they may be weakly irrelevant to some other test input sets and, hence, their value has to be known in order to determine the appropriate values for the other causal variables.

Weakly irrelevant variables do not have to be influenced either in the respective test, but the appropriate values for the other variables have to be determined by restricting DTI for the next step to the current values of the weakly irrelevant variables.

For conditionally irrelevant variables, it has to be checked whether the irrelevance condition DTI´-k is satisfied in the current situation, and if so, they do not have to be touched, and an arbitrary assignment of values out of DTI´-k can be chosen for the relevant variables.

In this paper, we focused on the reduction of the number and costs of stimuli actions. This is justified because their costs are often higher than those of observing the system response. Reducing also the cost associated with observations is nevertheless a task that needs to be addressed. However, the solution for the causal variables does not simply carry over, and the tasks are not independent: in principle, a reduction of the set of observables may require the presence of certain stimuli and vice versa.

Another challenge is to investigate how serious a fundamental limitation of our approach is (and to overcome it if necessary and possible): the behavior representation in terms of relations and, hence, a rather static view on the system to be tested. If dynamic features are relevant, they can be accommodated by including derivatives in the set of model variables. Another solution is to base the behavior representation on transitions. Since they can be represented again by relations (linking the states "before" and "after") the described representations and algorithms remain applicable.

We have explored the latter solution by transforming models given as finite state machines into such a representation with the goal of extending the solution to testing of software [Esser-Struss 07]. This provides a challenge in itself, mainly because of the difficulty in establishing appropriate fault hypotheses: While for many physical devices, such hypotheses are determined by the ways the components wear and fail, the ways in which software can fail spans an infinite space and may include structural faults. An extension of the test generation and reduction methods to include software would be highly attractive because it would allow testing embedded software and its physical context in an integrated way.

Acknowledgements

Thanks to Torsten Strobel who implemented the algorithm, Oskar Dressler for discussions and support of this work, and the Model-based Systems and Qualitative Modeling Group at the Technical University of Munich. This work was supported in part by Audi AG, Ingolstadt.