Test Case Generation using KBS Strategy

1 Introduction

KBS-testing is a recent field of study [Morell 1988, Miller 1989, Ayel 1993, Gupta 1991]. Some execution monitoring tools, like WllNESS [VALID, 1991], provide information about the KBS running on a given problem. Other tools exist to help in the evaluation of the KBS results, such as CONTROLLER [VALID, 1991] and VORTEX [Cross eta/, 1990].SYCOJET is a different type of tool: it automatically builds test cases for a KBS; these test cases are then used to study the behaviour of the KBS, its performance and many other validation topics. Other test case generators are described in [Zlatareva eta/, 1993].

To build test cases, SYCOJET first analyses the KB itself. This analysis is based on building ATMS-like labels; these labels are an adaptation of De Kleer's [De Kleer, 1986].

SYCOJET uses specific expert knowledge in order to propose pertinent test cases. To reinforce the pertinence of the test itself, SYCOJET may use different coverage criteria, freely chosen by the user. When the KBS inference engine exhaustively derives everything that can be derived, the required level of the chosen criteria will be reached when all the selected test cases have been run with the KBS. Thus, when SYCOJET proposes a set of test cases, the level of the chosen criteria will be reached only with this hypothesis concerning KBS strategy.

If the KBS inference strategy can effectively be used in test case generation, the test cases will be of better "quality". Moreover, it will ensure that the required level of the chosen

Ruddy Lelouche

Departement d 'Informatique UNIVERSITE LAVAL Quebec G 1 K 7P4 CANADA

criteria will actually be reached when running the test cases with the KBS. In this paper, we propose two different approaches in order to account for the KBS strategy when selecting the test cases.

The first section presents the basic principles behind SYCOJET [Vignollet, 1991]. It shows why labels might be used to exhaustively "summarize" the deduction capabilities of a knowledge base (KB), and how these labels can be used in order to define test cases. Finally, section 2 demonstrates how some knowledge of the inference engine strategy can be useful to guide the construction of test cases respecting the assigned criteria, and presents two approaches to taking this strategy into account, depending on whether it is formally described and accessible or not

2 Construction of test cases

In this paper, we present simplified label building for KBSs using a propositional formalism. However, the method can be generalized to KBSs using a first order logic formalism, as can be seen in [Ayel eta/, 1993].

2.1 KBS formalism

Each KBS considered in this paper includes:

• a factual part describing the domain, or domain fact base,
• a factual part describing the problem that the KBS has to solve, or problem fact base,
• a deductive part describing the expertise required to solve a problem.

Definitions.

• A fact is a proposition.
• A fact is a problem fact if it may appear in a problem fact base.
• The deductive part of the KBS is a set of monotonic rules of the form

IF condition part THEN consequent part 1

which can only assert new facts.

• A fact is terminal if it appears in a consequent part of a rule and if it does not appear in the condition part of any rule.

The condition part is a conjunction of propositions, whereas the consequent part is a proposition (using a conjunction of propositions in the consequent part of the rule would not fundamentally change the method).

2.4.2 Test case building method

To build the test cases, the first step consists in constructing the deduction labels for each terminal fact of the KB as described above. In this way, we obtain all realistic problem fact bases of the KBS.

As a second step, the test cases are chosen from this set of problem fact bases. This choice is guided by the quality criteria retained but we still have to determine the contribution of each deduction environment to a given coverage criterion.

Definitions.

· The contribution of an environment to a coverage criterion is the number of KB components to be covered according to that criterion that have not yet been counted in the set of test cases under development

· The contribution of a terminal fact to a coverage criterion is the maximum contribution of all the deduction environments in its deduction label.

Each newly chosen test case will be one for which the environment from which it is extracted yields a contribution that is maximal.

Example. -Using the example in 2.2, if the quality criterion retained is rule coverage, the first deduction environment chosen will be <{FJ, F2, F3, FB}, {RI , R2, RS}> because it maximizes the number of rules fired. The corresponding test case is the set of problem facts in this environment, i. e. the set {FJ , F2, F3, FB}.

3. Using inference engine strategy: two approaches

There are many different possible strategies in the control mechanism of a KBS. J.P. Laurent in [Laurent I984] gives a general presentation, and we shall certainly not deal with all of them here. However, we can start investigating this field in a general manner.

Since the assumption behind SYCOJET, i.e. that the KBS being tested exhaustively derives all that can be derived [Vignollet, I99I], does not hold in general, it might be of interest to investigate the situations where the actual strategy can be used to prune the search trees while building deduction environments. In other words, it might not be necessary to construct environments that will never be used by the actual system when it is run. However, this possibility is kept as a longer term approach, and the remainder of this paper deals exclusively with what can be done when exhaustively constructing the KB labels, as done in SYCOJET.

In order to take into account the inference engine strategy when deriving test cases from the computed labels, one can distinguish two different approaches. In the first (3.I), the strategy is known, formally expressed, and can be exploited; in such a case it may be taken into account in the choice of test cases, as is shown with a particular strategy. In the second (3.2), the strategy is not known, or cannot be automatically exploited, and we use a more empirical approach.

3.1 Known and exploitable strategy

The case wherein the inference engine strategy is known is intellectually more challenging, because it could possibly lead to some kind of automatic generation (i.e. "intelligent selection") of actual test cases. However, there are few chances indeed that it can actually be of general use, i.e. for all existing strategies.

Still, for particular inference engine strategies, strategy­ specific knowledge can sometimes be used and lead to interesting results independent from the domain knowledge or from the validation knowledge itself. That allows us to go beyond the SYCOJET case where all possible deductible facts are derived. Such is the case, for example, when the conflicts are solved using weights on the deduction elements (e.g. rules) and the system stops as soon as the first terminal fact is reached, as we shall now demonstrate. ·

3.1.1 Strategy hypotheses

In order to simplify our discussion, we still assume that the KB deduction formalism is of the propositional logic type. Moreover, we now also assume that we deal with a KBS where:

· each rule is marked with some interest coefficient (or weight), and any conflict is solved by always firing the rule with the highest coefficient (note that the multiple maximwn case is only theoretic, since either it is solved by executing some sub-procedure based on another condition, or the actual conflict resolution is implementation dependent 7 ; we therefore assume that there is always only one highest coefficient ruleS);

· the system stops as soon as a terminal fact has been reached.

Incidentally, let us remark that, under these assumptions, some satisfaction criteria may prove to be unattainable.

For example, if there are two rules in the KB with the same fact(s) as premise(s), the rule with the lower coefficient will never be fired. Therefore a test criterion specifying "execute every rule at least once" cannot be met The same holds true if the rule with the higher coefficient has the form Rl: SPI ~ SCI (where SPI is the set of premise facts and SCI is the set of derived facts), and the rule with the lower coefficient has the form R2: SPI u SF ~ SC2, for some non empty set of facts SF. With the test criterion above, in order to eliminate this problem, we would have to verify that the premise set of facts of any rule is never included in the premise set of facts of another rule with a lower coefficient9 (but this can be done automatically).

3.1.2 A first result: potentially confticting environments

Lemma. - Under the strategy hypotheses in 2.1.I, when executing the KBS, the problem facts of an environment Ex might lead to using another environment Ey *- Ex only if the problem facts ofEy are included in those of Ex.

7 Actually, if no sub-procedure exists, the first - or the last - rule with the highest coefficient will be fired, depending on the implementation.

8 Note that this assumption cannot be automatically verified.

9 The above conclusion shows that, in spite of the distinction traditionally made between verification and testing, the two aspects may be inter-related.

2.2Example

This example illustrates our method used to build test cases with a propositional formalism. Let us assume that we have the following rule base:

Rl:FJ, F2-+ F4 2

R2:F3, F4, F9-+ Efi

R3:FJ, F3-+ F7

R4:F2, F7-+ El.Q

R5:F8-+ F9

where the problem facts are italicized and the terminal facts are underlined3.

Then, for each terminal fact 1F (F6 and FlO), we build the problem fact bases which can lead to 1F deduction. Furthermore to build test cases we need to associate to each problem fact base the rules used to deduce 1F from it. The couple of the problem fact base and the rule list is called the deduction environment of TF. All the deduction environments of a terminal fact constitute its deduction label. For our example, we have:

If the user's objective is to use 60% of the rules when running test cases, we propose one test case which is: (Fl, F2, F3, !8}. In this case, rules R1, R2 and R5 are supposed to be ftred when the KBS runs. However if the KBS inference engine uses a specific strategy, the;e rules might not be fired.

In the following sections we present the formalized method to build the deduction label of a terminal fact and to build test cases taking into account quality criteria.

2.3 Building ATMS-like labels

The objec~ve of label building is to make explicit all the problem~. 1.e. all the problem fact bases, through which the KB termmal facts can be derived. Our building method is a variation of De Kleer's ATMS labels [De Kleer, 1986]; in fact, . we adapt thC? A TM.S concepts to our problem by defimng the deducuon envtronments and the deduction label of a terminal fact

Definitions.

• A deduction environment of a terminal fact 1F is a couple of the form <SPF, SR>, where SPF is a set of problem facts and SR a minimal set of rules used to derive 1F from SPp4.
• A set of problem facts is also called a problem fact base.
• The deduction· label of a terminal facJ 1F is the set of all its' deduction environments.

2 Note that a derivable fiact' may also be a problem filet

3 Th~ definitions of these special facts are given in the next secuon.

4 Note that 'SPF has al8o te be suffi~;iently large to allow the deduction , of TF-, but such thal withdrawing any facts from SP.F would no .longer allow the deduction of TF. In-other words, it constitutes IIi minimal .problem fact base.

Each terminal fact may have several deduction environments; the set of these environments is then the deduction label of the terminal fact

To construct the deduction label of a terminal fact TF we have to build. the search tree of 1F, by backward chai;ing. We thus obtam all the potential problem fact bases allowing deduction of TF.

Each of these potential problem fact bases does not necessarily correspond to a real problem fact base. Thus, the set of all real problem fact bases is included in the set of all potential problem fact bases. In order to refine this last set, the domain expert is asked to define constraints to reinforce the realism of its elements, in order to build a set of realistic problems5. We will not develop this aspect here but the reader. may refer to [Ayel & Vignollet 1992]. In the followmg, we suppose that the only deduction environments that are built are those containing a realistic problem fact OOse.

The next section shows how these deduction labels can be used to build pertinent test cases, i.e. test cases that detect a maximum number of errors, as implemented in SYCOJET.

2.4 The construction

The test cases are provided to verify correct system behaviour. Whenever the results obtained by the KBS do not fit the results expected by the expert, the presence of at least one error has been detected in the KB. Then the debugging task (unde~ the t:xpert's control) is respons~ble for locating and correctmg thts error (or these errors); thts last task is not our topic here.

2.4.1 Test quality criteria

A.s long as the .KBS results are accepted by the expert, testmg goes on, t.e. adequate test cases are fed into the system, until the latter is believed to have been sufficiently tested. This decision can be difficult to make and therefore in order to help in decision-making, we propose using quality criteria.

In general, these quality criteria are coverage criteria such as:

• coverage of facts, like problem facts, terminal facts, etc.;
• coverage of rules, or of groups of rules;
• coverage of paths6.

Note that coverage is not necessarily exhaustive, and that it may be of a mixed nature (e.g. coverage of 75% of the rules and 90% of the terminal facts). In any case the retained criteria can then be used: '

• to chose the test cases,
• to assess the quality of any test case, according to the components of the KB that will be used during the execution of tl'lat test case by the KBS.

5 The real problems-are included in the realistic ones because we cannot be sure that the expert's constraints are sufficient to guaranty the realism of the askable fact bases. These constraints may ~reatly reduce: the set of potential problem fact bases, but m geaeral y1eld only a superset of re'al problems· ; it is this superset that we call the set of realistic problems.

6 At this staae of our research. we consider only monotonic KBSs. That means that path coverage is the same as groups of rules coverage.

Proof - The proof is trivial considering the completeness of the labels.

Example.- Using the same example as before (see 2.2), one can see from the labels only that:

• if facts Fl, F2, F3 only are assumed to hold, the system will always use the deduction environment E10 = <{Fl, F2, F 3}, {R3, R4 }> and derive FlO; in fact, F6 cannot be derived because F8 would be needed as a problem fact;
• if facts Fl, F2, F3, and FB are assumed to hold, depending on the rule firing order, the system might either use the environment E6 = <{Fl, F2, F3, FB}, {Rl, R2, R5}> and derive F6, or use the environment E10 = <{F 1, F2, F3}, {R3, R4 }>and derive FlO.

The above lemma justifies the following definition:

Definition. - A deduction environment Ey is said to be potentially conflicting with another one Ex :;:. Ey whenever the problem facts ofEy are included in those of Ex.

Example. - In the above example, the environment E10 = <{F_J, F2, F3}, {R3, R4 }>is potentially conflicting with the environment E6 = <{Fl, F2, F3, FB}, {Rl, R2, R5}>.

Note that the concept of potentially conflicting environments is not symmetric, since the set inclusion relation is not.

The lemma can then be formulated as: the problem facts of an environment Ex might lead to using another environment Ey :;:. Ex only if Ey is potentially conflicting with Ex. Interestingly enough, it may be used in two different ways:

• with a terminal fact coverage criterion, if Ex and Ey are in the labels of two different terminal facts TFx :;:. TFy. then an actual conflict might lead to deriving TFy rather than TFx (that is the case with the example above);
• with a rule coverage criterion, even if Ex and Ey are in the same label (i.e. they lead to the same terminal fact), the derivation path of Ey might be followed rather than that of Ex.

However, the condition is only a necessary but not a sufficient one; even if it holds, the system might still use Ex as expected, which is a relatively weak result. Can we strengthen it, taking the interest coefficients into account ? Fortunately we can, and the result which we arrive at is the following:

Theorem. - Let Ex = <SPFx. SRx> be an environment and Ey = <SPFy. SRy> be another one potentially conflicting w1th Ex. Let mx and my be the minimum of the coefficients of the rules in SRx and in SRy respectively. Then, under the strategy hypotheses 3.11, executing the KBS with SPFx will use Ey rather than Ex iff my > mx.

Proof -If SPFy ~ SPFx. SPFx contains a set of problem facts needed to use the environment Ey. executing the system with SPFx will successively fire rules from SRx and rules from SRy (and possibly some other rules coming from other deduction environments) in a given order, according to the conflict resolution strategy given above (i.e. whenever several rules can be fired, the one with the highest coefficient is fired first).

Let us first assume that my > mx. and prove that Ey is used rather than Ex. i.e. that the rules in SRy are fired first and that assuming the opposite leads to a contradiction. Let us assume that the system uses Ex. i.e . . that the rules in SRx are fired first. Let Rmx e SRx be a rule with coefficient mx (there must be one by definition). Rmx is on the derivation path made up of the rules in SRx (using the environment Ex). When Rmx is to be fired, all the rules Rj e SRy (needed to use the environment Ey) have been fired, since they all have a coefficient Cj ~my> mx. Therefore Ey has been used and the system has stopped without firing Rmx. which contradicts the fact that it uses Ex and fires all the rules in SRx.

Conversely, suppose that the KBS uses Ey rather than Ex, i.e. fires all the rules in SRy before firing all the rules in SRx. We could similarly show that the hypothesis mx >my leads to a contradiction, but (for a change) we are to prove directly that my> mx. Indeed, there exists a firing order in SRx alone when using Ex. and a firing order in SRy alone when using Ey. When the system has used Ey. the next rule Ri e SRx which would have been fired if the system had not stopped has a coefficient Ci ~ mx (by definition of mx). If it has not been fired, it is because all other conflicting rules Rj e SRy had a coefficient Cj > Ci (because of the conflict resolution strategy; remember that the case Cj = Ci has been excluded as purely theoretic). The minimum my of these Cj also satisfies my > Ci. Therefore my > Ci ~ mx. and the proof is complete. +

Notation. - Since the theorem above shows the importance of the minimal coefficient of the rules in the deduction path associated with any deduction environment, it might be desirable, when constructing the deduction labels, to compute this minimal coefficient along with the set of problem facts and the set of rules of the environment, and integrate it as part of the deduction environment. Thus, under the strategy hypotheses above, we shall write

E = <SPF, SR, m>

when we want to make this minimal coefficient explicit and associate it with the environment E.

Example . - With the same example (see 2.2 and 3.1.2), assume that we are to run the system on the set {Fl, F2, F3, FB}, i.e. the problem facts corresponding to E6 = <{Fl, F2, F3, FB}, {Rl, R2, R5}>.

First suppose that the rule interest coefficients are:

Rl: 10; R2: 15; R3: 20; R4: 12; R5: 30.

Note that the rule R5, which uses the fact F8 as a premise (F8 is the discriminating fact between the sets of problem facts of E6 and Elo), has the highest interest coefficient. However, the system will successfully frre the rules R5, R3, R4 in that order, and stop after deriving the terminal fact FlO, i.e. after using ElQ.

The reasons are that

• 1° E10 is potentially conflicting with£(),
• 2° m10 =min (20, 12) > m6 =min (10, 15, 30),

and, by the theorem above, E 1 o is used rather than E6 (the conflict is effective). Thus {Fl,F2,F3,FB} should not be proposed as a test case since it would not yield its "theoretical" contribution to the quality criteria (rule coverage for instance). Instead, one should look for another environment, i.e. the one giving the best theoretical contribution among the environments not already selected or marked as unattainable.

Now suppose that the coefficient of R4 is 8 rather than 12 leaving the other coefficients unchanged. Then the rules wili be fired in the order R5, R3, Rl, R2, and the system stops after reaching F6, i.e. after using £(). Here:

• E 10 is still potentially conflicting with E6,
• but m10 =min (20, 8) < m6 =min (10, 15, 30),

and, by the theorem above, E6 is used as expected and not E10 (the conflict is not effective).

Again note the generality of the above lemma and theorem: either can be indistinctly applied for rule coverage or for terminal fact coverage, as has been shown above for the lemma.

Also note that, in the above theorem, nothing is asserted in a sit~atio~ wher~ several. environments Ey potentially confhct wtth a gtven environment Ex. Thts is why the corollary below deals precisely with this point.

3.1.3 Using this result for choosing test cases.

As explained in 2.4, all test cases are chosen inside the set of realistic problem fact bases. At each choice point, i.e. whenever SYCOJET is to add a new test case to the set under construction, it selects the deduction environment with ~he maximal contribution. As already pointed out, this choice IS made assuming that the KBS derives all that it can from a problem fact base.

However, when a test case is run by a KBS using a non e~haustive de.duction strategy, the system might use a different environment, and therefore take a different derivation path than the one expected from the chosen environment, or reach a different terminal fact than the one corresponding to the chosen environment, etc. Since this may happen at each choice point, the overall result might show a large gap between the criteria level actually reached in executing the set of test cases with the KBS and the SYCOJET-predicted level for the same criteria.

Indeed, when choosing a test case, we must know whether the environment it comes from will be the one actually used when running it on the system. Thus at each stage of test case building, we have to choose the environment which will actually be used and with the highest possible contribution.

If the KBS uses rule weights and stops at the first terminal fact encountered (strategy hypotheses 3.1.1), the lemma in 3.12 shows that, if SYCOJET selects an environment E, a degradation can only come from an environment potentially conflicting with E. Moreover, the theorem in 3.1.2 gives a nece~s~~:ry and. sufficient ~ondition for a potentially confhcung environment to yteld an actual conflict, i.e. to prevent E from being actually used when running the system.

To be sure that a selected environment E would be effectively used in a running session, we have to find all environments actually conflicting with E. The following corollary to the theorem in 3.12 allows to decide if the selected environment E should be used.

Corollary. - Let E = <SPF, SR, m> be a deduction environment. Let

be the set of all deduction environments potentially conflicting with E. Then, under the strategy hypotheses 3 .11 , executing the KBS with SPF as problem facts will use SR iff, for every Ei E CES(E), mi < m.

Proof. - If the system running SPF actually uses E, then every environment Ei potentially conflicting with E is not in actual conflict, and therefore mi < m by the theorem in 3.1.2.

Conversely, if for every Ei = <SPFi. SRi. mi> potentially conflicting with E, mi < m holds, then by the theorem in 3.12 none of the Ei will be used. Since no other environment is potentially conflicting with E, E will be used. ·

This corollary shows that if, for any deduction environment E = <SPF, SR, m> selected by SYCOJET, there exists one deduction environment Ei = <SPFi, SRi, mi> potentially conflicting with E and such that mi > m, then we should not use SPF as the next test case to be included in the set of test cases under construction. In other words, the existence of such an Ei implies that E, which has been selected because of its potential contribution to the retained quality criteria, cannot actually yield this "theoretical" contribution to these criteria when running the system.

3.2 The strategy is not known, or not exploitable

The second approach deals with the situations in which nothing particular is known about the KBS inference strategy. In those situations, even though the inference engine strategy cannot be exploited as such, we still have some quality criteria (see 2.4.1) for defining a set of "good", or of "the best", test cases, with respect to these criteria. We then may define two procedures as follows.

The first procedure is an algorithm defined over the existing KB:

1° Compute the deduction labels as shown in section 1.

• 2° Define the criteria satisfaction indices (e.g. the various coverage counters) according to the retained test criteria and initialize them.

3° WHILE the criteria satisfaction indices are not satisfied AND there are pertinent environments available in the labels:

• Choose a pertinent environment in the computed deduction labels, using the underlying test criteria as a guide for this choice (using the SYCOJET mechanism for choosing a test case).
• Define a test case from this environment, and execute it on the KBS.

• IF the results are correct, i. e. agree with the expert's opinion or conclusion, THEN:
• Analyze the execution traces to update the criteria satisfaction indices.
• Mark any environment(s) in the labels which become unnecessary (i.e. executing the corresponding test would not improve the criteria satisfaction indices).

ELSE {the expert disagree with the obtained results} End the procedure {there is something wrong in the KB; procedure 2 must be performed next}.

· END WHILE.

4 2 IF the criteria satisfaction indices are satisfied THEN

The KBS has been successfully tested {the satisfaction criteria are met} .

ELSE {there is no pertinent environment left in the labels}

Testing the KBS is impossible with respect to the defined test criteria.

END of first procedure (over the existing KB).

The second procedure takes place whenever the existing KB proves erroneous somewhere, i.e. when a test case uncovers an erroneous behavior of the KBS. It consists in correcting the KB with the help of the domain expert. This correction cannot be formalized without the adequate domain knowledge, and is therefore outside the scope of this article. Once the KB has been modified, the first procedure above must be run again on the KBS with the new KB.

Conclusion

In the area of test case generation for knowledge-based systems, SYCOJET is an automatic test case building system which has given significant results on several KBSs10. The method it uses in this test case construction consists first in building the deduction label of each terminal fact of the knowledge base. These labels provide the set of all potential problem fact bases. Then the actual test cases are extracted from this set, according to the coverage criteria chosen by the user. SYCOJET is operational for KBSs using a first order formalism [Aye! et al, 1993]. However, it makes the hypothesis that the inference engine of the KBS deduces all it can. If that is not the case, the criteria level obtained in executing the set of test cases proposed by SYCOJET might be significantly lower than the SYCOJET-predicted level for the same criteria. Thus, taking into account the inference engine strategy will lead to better test case generation.

In this paper, we have proposed two approaches which take the inference engine strategy into account differently.

In the first approach, we suppose that the strategy is known and that it is used to help choose the test cases. This approach cannot actually concern all existing expressible strategies, but we have shown that it can work for some particular strategies. Indeed, we have established some results for a KBS which uses rule weights and stops at the first terminal fact encountered. First, we have introduced the notion of a deduction environment that potentially conflicts with another. We have exhibited and proven a lemma which shows that if an environment E is selected, a degradation can only come from an environment potentially conflicting with E. Moreover, we have established a theorem which gives a necessary and sufficient condition for a potentially conflicting environment to yield an actual conflict, i.e. to prevent E from being used when running the system. These results can lead to more intelligent test case selection.

10 One of them, called GIBUS, comes from the European Spatial Agency (in the scope of ViVa (ESPRIT Ill Project)).

The second approach to the choice of test cases can always be taken, in particular when the strategy is not explicitly known, or when it is not exploitable. It is a more pragmatic one: a test case will be chosen according to the level of the required criteria already reached by the execution of previous test cases.

The first approach is intellectually more satisfactory but very limited in scope. Our study has shown that, even for a KBS with a well defined but simple strategy, it requires a specific, fairly complex method.

One potentially interesting path for further research could be to examine some other strategies, and investigate whether strategy-specific procedures can be established. Another one would be to try to adequately use the strategy-specific knowledge to prune the search trees used in deduction label construction.