Testing Against Non-deterministic FSMs: A Probabilistic Approach for Test Suite Minimization

Abstract

The paper is devoted to model based testing against non-deterministic specifications. Such test derivation strategies are well developed, for example against non-deterministic Finite State Machines, however the length of the corresponding test suite can be exponential w.r.t. the number of specification states. We therefore discuss how a test suite can be minimized or reduced when certain level of guarantee concerning its fault coverage is still preserved. The main idea behind the approach is to augment the specification by assigning probabilities for the non-deterministic transitions and later on evaluate the probability of each test sequence to detect the relevant faulty implementation. Given a probability P which is user-defined, we propose an approach for minimizing a given exhaustive test suite TS such that, it stays exhaustive with the probability no less than P.

The work was partially supported by Erasmus program.

1 Introduction

Model based testing has been actively developing in the past decades; the interested reader can find various recent works, in particular, when checking the proceedings of related conferences such as the International Conference on Testing Software and Systems (ICTSS), the International Symposium on Software Testing and Analysis (ISSTA), the Workshop on Model-Based Testing (MBT), the International Conference on Software Testing, Verification and Validation (ICST), etc. Finite State Machine (FSM) based testing assumes that the specification of the System Under Test (SUT) and its implementations are given as FSMs and usually the possible implementations share the same input/output alphabets with this specification FSM. In this paper, we study non-deterministic FSMs as related specifications. We note that various (preset and adaptive) testing strategies have been previously proposed for such machines, considering not only the test suite derivation but also learning the specification, test suite minimization and complexity estimation for the aforementioned tasks (see for example, [2, 4, 5, 10]).

In this paper, we consider a white box testing approach, where all the possible faulty implementations are explicitly enumerated [4, 7]. A complete test suite is built in such a way that each faulty implementation is killed (detected) by some test case of the test suite (test suite exhaustiveness). Such a test suite can be derived, for example, via adding to the test suite each sequence that distinguishes a potential faulty implementation from the specification machine. However, when the conformance relation is represented by non-separability¹, the length of a separating sequence can be exponential (w.r.t. the number of the specification states) [8], and this makes the approach unpractical, even if the fault coverage can be guaranteed. We propose to preserve the fault coverage up to a given level of certainty through augmenting the specification FSM with probabilities. Indeed, whenever for a given input at a given state two or more outputs are possible, these outputs can appear with certain probability. Note that in this paper, we do not discuss how such probabilities are assigned or obtained; they can be provided due to some additional knowledge of an SUT, or its stochastic behavior which can be revealed, for example, during the system monitoring. We only assume that the augmentation of the specification with probabilities is possible.

Once the specification FSM is augmented with probabilities for each non-deterministic transition, a given complete test suite can be filtered, i.e., the sequences that are derived for detecting some faulty implementations can be deleted depending on the likelihood of being detected by other test sequences. The level of such likelihood is determined by a user defined probability P. We propose a method for calculating the related likelihood and also discuss how a given exhaustive test suite can be minimized in such a way that it stays exhaustive at least with probability P. Note that we are not aware of any works for test suite minimization with guaranteed fault coverage against probabilistic non-deterministic FSMs and this is thus, the first attempt.

2 Preliminaries

When testing against FSMs, guaranteed fault coverage can be achieved when a corresponding fault model is properly defined. A fault model [6] is a triple $\langle \mathcal {S}, @, FD\rangle$ where $\mathcal {S}$ is the specification of the system behavior, @ represents the conformance relation between an implementation $\mathcal {I}_j$ under test and the specification $\mathcal {S}$, while FD is a fault domain which limits the set of possible implementations, i.e., $\mathcal {I}_j \in FD$. We are interested in an exhaustive test suite, i.e., a test suite that detects each implementation $\mathcal {I}_j \in FD$ that is not conforming to $\mathcal {S}$ (). Moreover, we work under the white box testing methodology, which means that the implementations from FD are explicitly enumerated, $FD = \{\mathcal {I}_1, \mathcal {I}_2, \dots , \mathcal {I}_k\}$. Usually, each $\mathcal {I}_j\in FD$ corresponds to a potential faulty implementation and thus, represents a mutant (transfer and/or output) of the specification $\mathcal {S}$. In this work, @ is the non-separability relation ($\cong$) which we further adjust to probabilistic non-separability while the specification is represented by an initialized complete non-deterministic observable FSM $\mathcal {S}$.

An FSM is a 5-tuple $\mathcal {S} = \langle S, I, O, h_S, s_0\rangle$ where S is a finite nonempty set of states with the designated initial state $s_0\in S$, I and O are finite input and output alphabets, and $h_S \subseteq S \times I \times O \times S$ is a transition relation. The FSM $\mathcal {S}$ is non-deterministic if for some pair $(s, i) \in S \times I$, there exist several pairs $(o, s') \in O \times S$ such that $(s, i, o, s') \in h_S$; otherwise, the FSM is deterministic. The FSM $\mathcal {S}$ is observable if for every two transitions $(s, i, o, s_1)$, $(s, i, o, s_2) \in h_S$ it holds that $s_1 = s_2$; otherwise, the FSM is non-observable. The FSM $\mathcal {S}$ is complete if for every pair $(s, i) \in S \times I$, there exists a transition $(s, i, o, s') \in h_S$; otherwise, the FSM is partial (partially specified).

Let each $\mathcal {I}_j \in FD$ and $\mathcal {S}$ share the same input alphabet I. We say that if there exists a separating sequence $\alpha \in I^*$ for $\mathcal {I}_j$ and $\mathcal {S}$, i.e., the set of output reactions of $\mathcal {I}_j$ and $\mathcal {S}$ to $\alpha$ do not intersect, i.e., $out(\mathcal {I}_j, \alpha ) \cap out(\mathcal {S}, \alpha ) = \emptyset$, where $out(\mathcal {I}_j, \alpha )$ (resp. $out(\mathcal {S}, \alpha )$) is the set of output responses on $\alpha$ at the initial state of the FSM $\mathcal {I}_j$ (resp. FSM $\mathcal {S}$). Otherwise, $\mathcal {I}_j$ is non-separable from the specification machine $\mathcal {S}$. Note that TS is an exhaustive test suite w.r.t. the fault model $\langle \mathcal {S}, \cong , FD = \{\mathcal {I}_1, \mathcal {I}_2, \dots , \mathcal {I}_k\}\rangle$, if for each $\mathcal {I}_j \in FD$, there always exists such $\alpha _j \in TS$ that separates $\mathcal {I}_j$ from $\mathcal {S}$.

Deriving such complete test suite TS is possible and this problem has been well studied previously (see, for example [4, 10]). However, the length of the corresponding separating sequence (even for a given mutant) can be exponential w.r.t. the number of states of the specification FSM $\mathcal {S}$. Therefore, an iterative test suite derivation even for the white box testing approach can return a test suite of exponential length. Correspondingly, in this paper, we discuss how such test suite (length) can be reduced via introducing probabilities to the specification FSM and a given level of certainty about the TS exhaustiveness.

3 Introducing the Probabilities in the Specification

Given the specification machine $\mathcal {S} = \langle S, I, O, h_S, s_0\rangle$, we augment each non-deterministic transition $(s, i, o, s') \in h_S$ with the probability p. The probabilistic specification is thus the FSM $\mathcal {S} = \langle S, I, O, h_S, s_0, pr\rangle$, where pr is the function that defines the probability for the output o to be produced at state s under input i, $pr: S \times I \times O \longrightarrow [0,1]$. Note that, we restrict the assignation of pr in such a way that $\forall s \in S\;\forall i \in I \sum _{o \in O} pr(s, i, o) = 1$. The function pr can be extended over input/output sequences from $(IO)^{*}$; given an input/output sequence $\alpha /\beta = (\alpha '/\beta ').(i/o)$, $pr(s_0, \alpha , \beta )$ = $pr(s_0, \alpha ', \beta ') * pr(s, i, o)$, where s is the $\alpha '/\beta '$-successor of the state $s_0$ of the specification FSM $\mathcal {S}$; if the trace $\alpha '/\beta '$ is not defined at state $s_0$ then this probability equals 0. Note also, that for the defined sequence $\gamma$ such a successor is unique due to the observability of the specification FSM $\mathcal {S}$. Note as well, that as usual $pr(s,\varepsilon ,\varepsilon ) = 1$.

As an example, consider the FSM in Fig. 1 where transitions at states 1 and 2 are non-deterministic and augmented with probabilities.

Fig. 1.

An example probabilistic FSM $\mathcal {S}$

Fig. 2.

An implementation FSM $\mathcal {I}_1 \in FD$

The notion of a probabilistic FSM has been introduced before, as well as the notion of distinguishability (as non-equivalence) for such machines (see for example, [1, 3, 9]). However, in this work, we consider the non-separability conformance relation that we adjust, having such an augmented probabilistic specification FSM $\mathcal {S}$.

For a fault model $\langle \mathcal {S}, \cong , \{\mathcal {I}_1, \mathcal {I}_2, \dots , \mathcal {I}_k\}\rangle$ we thus define a probabilistic separability for a given implementation $\mathcal {I}_j$ from the specification $\mathcal {S}$. Given P as a user defined probability², a sequence $\alpha \in I^{*}$ is a P-probably separating sequence for $\mathcal {I}_j$ and $\mathcal {S}$, if $\sum _{\beta \in out(\mathcal {I}_j, \alpha ) \cap out(\mathcal {S}, \alpha )} pr(s_0, \alpha , \beta ) \le 1 - P$. Note that $\mathcal {I}_j$ is not probabilistic, and $pr(s_0, \alpha , \beta )$ is the probability to observe $\beta$ when $\alpha$ is applied at the initial state $s_0$ of $\mathcal {S}$. For the considered example FSM $\mathcal {S}$ (shown in Fig. 1), and a potential implementation $\mathcal {I}_1$ shown in Fig. 2, by direct inspection one can observe that $\alpha = i_1 i_2$ is a 0.8-probably separating sequence.

For a fault model $\langle \mathcal {S}, \cong , FD = \{\mathcal {I}_1, \mathcal {I}_2, \dots , \mathcal {I}_k\}\rangle$, we say that the test suite P-TS is P-probably exhaustive if $\forall \mathcal {I}_j \in FD$ $\exists \alpha \in$ P-TS such that $\alpha$ is a P-probably separating sequence for $\mathcal {I}_j$ and $\mathcal {S}$. We aim at deriving such test suites for user defined probabilities via filtering a given exhaustive test suite TS for the fault model $\langle \mathcal {S}, \cong , FD = \{\mathcal {I}_1, \mathcal {I}_2, \dots , \mathcal {I}_k\}\rangle$.

4 Minimizing an Exhaustive Test Suite Against $\langle \mathcal {S}, \cong , \{\mathcal {I}_1, \mathcal {I}_2, \dots , \mathcal {I}_k\}\rangle$

Given an exhaustive test suite $TS = \{\alpha _1, \dots , \alpha _l\}$ derived for the fault model $\langle \mathcal {S}, \cong , FD = \{\mathcal {I}_1, \mathcal {I}_2, \dots , \mathcal {I}_k\}\rangle$, given also a user defined probability P, we propose to derive a test suite P-TS $\subseteq TS$, aiming at reducing |P-TS| (in size), and which is P-probably exhaustive for $\langle \mathcal {S}, \cong , FD = \{\mathcal {I}_1, \mathcal {I}_2, \dots , \mathcal {I}_k\}\rangle$. In order to do so, we propose to build a matrix M whose rows correspond to the test sequences of TS while columns correspond to all the implementations from FD. $m_{i,j}$ contains the maximal guaranteed probability $p_{i,j}$ for the sequence $\alpha _i$ (in lexicographical order) to separate the implementation $I_j$ (also in lexicographical order) from the specification FSM $\mathcal {S}$. This probability is calculated as $p_{i,j} = 1 - \sum _{\beta \in out(\mathcal {I}_j, \alpha _i) \cap out(\mathcal {S}, \alpha _i)} pr(s_0, \alpha _i, \beta )$.

Note that, by construction, each column of the matrix M contains at least one 1, as the test suite TS is exhaustive. After M is derived what is left to do is to build a minimal cover of it, such that a subset P-TS corresponding to the rows covers all columns $\{\mathcal {I}_1, \mathcal {I}_2, \dots , \mathcal {I}_k\}$, where each probability $p_{i,j} \ge P$. The latter means that for each potential faulty implementation from FD there exists at least one test sequence from P-TS that P-probably separates it from the specification $\mathcal {S}$.

We omit the discussion about how such a row cover can be constructed - it can be done through an explicit combinatorial enumeration or various (combinatorial) optimization strategies can be applied. The solution to the problem always exists and in the worst case scenario, when nothing could be minimized, P-$TS= TS$.

Consider again the example FSM $\mathcal {S}$, and the $FD = \{\mathcal {I}_1, \mathcal {I}_2, \mathcal {I}_3\}$, where $\mathcal {I}_1$ is the mutant from Fig. 2; it is separated from $\mathcal {S}$ via $\alpha = i_1i_2i_1\in TS$. $\mathcal {I}_2$ shown in Fig. 3 is separated from $\mathcal {S}$ via the application of $\alpha = i_1i_1$, and 0.2-probably separated via $\alpha = i_1i_2$. Finally, the mutant $\mathcal {I}_3$ is shown in Fig. 4. The corresponding separating sequence is $\alpha = i_1i_2$.

Fig. 3.

An implementation FSM $\mathcal {I}_2 \in FD$

Fig. 4.

An implementation FSM $\mathcal {I}_3 \in FD$

Assume that the $TS = \{i_1i_1, i_1i_2, i_1i_2i_1\}$; the matrix M for the example FSM, mutants $\mathcal {I}_1,\mathcal {I}_2$ and $\mathcal {I}_3$ and this test suite is the following: $\begin{pmatrix} 0.97 &{} 1 &{} 0.2 \\ 0.8 &{} 0.2 &{} 1\\ 1 &{} 0.36 &{} 1 \\ \end{pmatrix}$.

As an example, note that the M cover that only consists of first two rows provides 0.97-probably exhaustive³ P-TS = $\{i_1i_1, i_1i_2\}$. The last test sequence thus can be omitted, preserving the exhaustiveness with the probability 0.97.

5 Conclusion

In this paper, we discussed a possibility of reducing an exhaustive test suite built for a non-deterministic specification, via augmenting this specification with probabilities. The proposed technique relies on a user defined probability P that each potential faulty implementation will be detected (with this probability). The same approach can be applied for a test suite with adaptive separating sequences. In this case, the probability of a test case is the minimum probability of all test case traces. Note also that the proposed approach can also be applied for filtering a non-exhaustive test suite, as long as the sequences left, respect the P-separability relation with the specification.

As a future work, we plan to extend this short paper by considering other fault models, as the proposed technique only considers the non-separability conformance relation and only relies on the white box testing assumption. At the same time, we plan to investigate the model learning strategies for obtaining the probabilities of interest. Finally, as for test derivation, it is interesting to consider how an augmented specification can be used for choosing input sequences, which are more efficient for distinguishing faulty implementations from the specification.