Уточнение недетерминированного эталонного автомата при условном тестировании .pdf The need for adaptive tests for nondeterministic machines has widely been discussed in various work, see, e.g., [1 - 10], [13, 14], [17 - 21]. When testing a nondeterministic implementation FSM each input sequence used in a given test needs to be repeatedly executed to make sure that all the implemented traces with this input sequence are observed. The number of repetitive applications of a sequence of input stimuli to satisfy the all-the-weather, aka complete testing assumption [11], is application dependent; however, it is even unknown when it is sufficient to terminate this process in a general case. To the best of our knowledge, the work of Hwang et al. [8] is the only attempt in determining the repetition numbers of test sequences in a probabilistic setting. However, there has been little work done on minimizing the number of input stimuli of a given test that need to be executed against a given possibly nondeterministic implementationFSM.In this paper, we consider the offline testing of nondeterministic FSMs. As opposed to online testing, where test generation and execution are merged into a single process, see, e.g., [3], [14], in offline testing, tests are first generated from a given specification and then executed against a given implementation. This type of testing avoids repetitive test generation especially when several implementations (or its versions) have to be tested against a given specification. In this setting, the overall testing efforts can be reduced by minimizing a part of given tests that needs to be executed against a particular implementation.If both, a specification and its implementations are allowed to be nondeterministic then the reduction relation between FSMs is a natural choice for a conformance relation, since an Implementation Under Test (IUT) is allowed to be less nondeterministic than its specification. Several publications in the area use the notion of a test from the case of deterministic specification FSMs; where tests are simply input sequences. This creates a number of problems in defining an adaptive test and formalizing its adaptive execution.For this reason, an adaptive test case is presented as a tree in [2, 4 - 7, 9, 17], where in each node only a single input triggers outgoing transitions.Hierons in [4, 5], derives an adaptive test assuming that implementation FSMs are deterministic. The idea is to use candidate machines which may model the behavior of an implementation FSM, in other words, to refine the fault domain which contains all possible implementation machines. As a result, the algorithm terminates when an implementation FSM fails the test or is recognized up to distinguishable states. Thus, this approach deals with the problem of identification of an implementation FSM, while the initial problem statement concerns just checking of the implementation which is usually less expensive than machine identification. Hierons and Ural [7] also address the problem of adaptive execution of test sequences against a deterministic implementation. The proposed approach consists in finding such an ordering of input sequences that minimizes the total number of input sequences that needs to be executed. In [6], Hierons extends the approach for the case when an implementation FSM can be non-deterministic. In this paper, in order to terminate traces of a test earlier than in [16] Hierons refines not the fault domain but the product of the specification and an implementation FSM when the latter already produced expected output responses to some input sequences. Termination rules and algorithms in [4 - 6] depend on the number of states of an implementation FSM, and should be completely reconsidered when extending the methods proposed there to another fault domain. In [17], we elaborated an approach to test generation using the notion of a test as a tree FSM. A complete test is defined as sound and exhaustive, i.e., each conforming IUT (a reduction of the specification FSM) has to pass the test, while each non-conforming implementation (not a reduction of the specification FSM) of the fault domain has to fail the test.All the known methods for deriving tests with respect to the reduction relation keep the same original specification FSM during test generation, while in this paper, we propose to refine the specification FSM by removing traces absent in the implementation, which has already passed some subtest of a given complete (sound and exhaustive) test. A refined specification usually becomes more deterministic and thus, a shorter complete test may exist for the refined specification FSM. The test execution process can be terminated as soon as the executed so far subtest is complete for the current refined version of the specification. The sufficient conditions for the completeness of a test with respect to the reduction relation when the upper bound on the number of states of an IUT is known, formulated in the paper can be used for this purpose. This approach does not differentiate between deterministic and nondeterministic implementation FSMs and can be easily extended to other fault domains with respect to which sufficient conditions for the test completeness are known. A proposed approach is based on checking experiments with FSMs, which are usually known to be shorter that the identification experiments; however, additional research is needed to compare the effectiveness of the proposed approach and that of the approach in [4] when an implementation FSM is deterministic.The paper is organized as follows. Section 2 contains basic definitions related to nondeterministic finite state machines including the reduction relation. Section 3 defines a test as a nondeterministic acyclic FSM. A method for adaptive test execution of a given complete test against a given possibly nondeterministic implementation FSM which is based on a consecutive refinement of a given specification is elaborated and illustrated on an example in Section 4. Section 5 concludes the paper.1. DefinitionsDefinition 1. A Finite State Machine (FSM) A is a 5-tuple (S, s0, I, O, h), where•·S is a finite set of states with the initial state s0;•I and O are finite non-empty disjoint sets of inputs and outputs, respectively;•·h is a behavior function h: S x I -> 2SxO, where 2SxO is the powerset of S x O. The function h has two projections h1 and h2: for each (s, a) e S x I, it holds that h:(s, a) = = {s'| 3o e O s.t. (s', o) e h(s, a)} and h2(s, a) = {o | 3s' e S s.t. (s', o) e h(s, a)}.•·We slightly abuse the notation h by referring to the behavior function extended to input words.•·An input a is a defined input at state s if h(s, a) ф 0; otherwise, an input a is•·undefined at state s.•·A word a e (IxO)* of the automaton Ax in state s is a trace of A in state s; let Tr(s) denote the set of all traces of A in state s, while Tr(A) denote the set of traces of A in the initial state. Given a trace set T, we denote Max(T) the set that contains completed trace of the set T, i.e., those traces are not proper prefixes of the other traces of T. Given sequence a e (IxO)*, the input projection of a, denoted a;I, is a sequence obtained from a by erasing symbols in O. Input sequence ß e I* is a defined input sequence in state s of A if there exists a e Tr(s) s.t. ß = a;I. We use Q(s) to denote the set of all defined input sequences for state s and Q(A) for the state s0, i.e., for A. Q(A) = Tr(A);I = I* holds for any complete machine A, while for a partial FSM Q(A) с I*.•·We use the following categorization of state machines.•Definition 2. FSM A = (S, s0, I, O, h) is•·completely specified (a complete FSM) if h(s, a) =/= 0 for all (s, a) e S x I;•·partially specified (a partial FSM) if h(s, a) = 0 for some (s, a) e S x I;•trace-harmonized if for each sequence aa e Q(A) input a is defined at each stateh1(s0, a);•·trivial, if S = {s0} and h(s0, a) = 0 for all a e I;•state deterministic if |h:(s, a)| < 1 for all (s, a) e S x I;•output deterministic if |h2(s, a)| < 1 for all (s, a) e S x I;•deterministic if |h(s, a)| < 1, i.e., if it is state and output deterministic;•nondeterministic if |h(s, a)| > 1 for some (s, a) e S x I;•·observable if the automatonAx = (S, s0, I x O, 5), where 5(s, (a,o)) = s' iff (s', o) e h(s, a), is deterministic;•·acyclic if its transition diagram is acyclic;•·output-complete if for each pair (s, a), h(s, a) = 0 or h2(s, a) = O;•·regular if it is observable, output-complete, acyclic and has at each state at most one defined input; the set of its traces is called regular.•·We define several relations between states of observable and traced-harmonized•·FSMs.•·Definition 3. Given observable and traced-harmonize FSM A = (S, s0, I, O, h) and s,•·t e S,•·s and t are (trace-) equivalent, s = t, if Tr(s) = Tr(t);•·t is quasi-equivalent to s, t 3 s, if Q(t) z> Q(s) and {ß | ß e Tr(s) & ß;I = a} = = {ß | ß e Tr(t) & ßiI = a} for each a e Q(s);•·t is trace-included into (is a reduction of) s, t < s, if Tr(t) с Tr(s);•·s is not a reduction of t, written s t, if Tr(s) £ Tr(t); if s is not a reduction of t•·and there exists an input sequence a e Q(s) n Q(t) s.t. {ß | ß e Tr(s) & ß;I = a} £•·{ß | ß e Tr(t) & ß;I = a} we use the notation s ^a t in order to refer to the input sequence a that evidences that s is not a reduction of t; in this case, we say that a trace ß e Tr(s) that is not a trace at state t, i.e., ß г Tr(t), distinguishes s from t;•·s and t are r-distinguishable, s * t, if there exists a regular set T of traces s.t. Max(T) n Tr(s) n Tr(t) = 0, called a set r-distinguishing s and t; then the set of traces T n Tr(s) is the r-distinguishing set of s w.r.t. t, denoted d(s, t), and T n Tr(t) is the•·r-distinguishing set of t w.r.t. s, denoted d(t, s); we also use the notation s *T t when we need to refer to the set T of traces r-distinguishing s and t.•·The notion of r-distinguishability (or adaptive distinguishability) is used in several work, e.g., [15 - 17, 2, 6]; below we briefly sketch how states can be efficiently checked for the r-distinguishability and how corresponding r-distinguishing sets can be determined. As usual, for a trace a e Tr(s), s-after-a denotes the state reached by A when it executes the trace a from state s. If s is the initial state s0 then instead of s0-after-a we write A-after-a.•·Definition 4. Given an FSM A = (S, s0, I, O, h), states s, t e S,•·s and t are r(1)-distinguishable if there exists input a s.t. h2(s, a) n h2(t, a) = 0;•·given k > 1, s and t are r(k)-distinguishable, if the states are r(k - 1)-distinguish-able or there exists an input a e I s.t. for each trace (a,b), b e h2(s, a) n h2(t, a), states s-after-(a,b) and t-after-(a,b) are r(k - 1)-distinguishable.•·Proposition 1. States s and t are r-distinguishable if there exists k > 0 s.t. states s and t are r(k)-distinguishable.•·If h2(s, a) n h2(t, a) = 0 for some input a then the set of traces {(a,b) | b e O} r-distinguishes states s and t. If the states s and t are r(k)-distinguishable, but not r(k - 1)-distinguishable and there exists an input a e I s.t. for each b e h2(s, a) n h2(t, a), states s-after-(a,b) and t-after-(a,b) are r(k - 1)-distinguishable, while d(s-after-(a,b), t-after-(a,b)) and d(t-after-(a,b), s-after-(a,b)) are their r-distinguishing sets, respectively, then the set of traces d(s, t) = {(a,b) | b e h2(s, a)} u {(a,b)y | b e (h2(s, a) n h2(t, a)) л у e d(s-after-(a,b), t-after-(a,b))} is a r-distinguishing set of s w.r.t. t and d(t, s) = {(a,b) | b e h2(t, a)} u {(a,b)y | b e (h2(s, a) n h2(t, a)) л у e d(t-after-(a,b), s-after-(a,b))} is that of t w.r.t. s [16, 17].•·The above relations could also be applied to states from different machines. Considering the disjoint union of these machines, we have B r A, if and only if t0 r s0, where r e {

Скачать электронную версию публикации