Hardware Reference
In-Depth Information
According to Proposition
16.2
, for each I/O sequence in the above set there
exists an external test suite that detects each faulty implementation FSM with
this I/O sequence. As an example, consider a faulty FSM
Imp
producing the internal
I/O sequence
u
1
u
1
=
v
2
v
2
; notice that it is faulty because the FSM
Largest
produces
the I/O sequence
u
1
u
1
=
v
2
v
1
. Under the external input
i
2
,
Context
issues
u
1
(and goes
to
t
1
); under
u
1
,
Imp
issues
v
2
; under
v
2
,
Context
issues
o
2
(and goes to
t
0
). Under the
second input
i
2
,
Context
issues once again
u
1
(and goes to
t
1
); under
u
1
,
Imp
issues
again
v
2
; under
v
2
,
Context
issues a faulty output
o
2
(instead of the correct output
o
1
). Therefore, each implementation FSM
Imp
with the I/O sequence
u
1
u
1
=
v
2
v
2
is detected by an external test case
i
2
i
2
. Thus,
TS
ext
.
u
1
u
1
=
v
2
v
2
/ Dfi
2
i
2
g
;thisis
certified by the fact that
Spec
produces
fi
2
i
2
=o
2
o
1
g
, whereas due to the faulty
Imp
the composition
Context
˘
Imp
produces
fi
2
i
2
=o
2
o
2
g
. Summmarizing, the simulation
goes as follows:
Context
issues
i
2
=
u
1
, the faulty
Emb
issues
u
1
=
v
2
,
Context
issues
v
2
=o
2
,
Context
issues
i
2
=
u
1
, the faulty
Emb
issues
u
1
=
v
2
,
Context
issues
v
2
=o
2
.
To find an external test suite for a given internal sequence say
u
1
u
1
=
v
2
v
2
(which
in turn is derived from an internal test
u
1
u
1
), one can compose the automaton
A.
u
1
v
2
u
1
v
2
/
accepting the word
u
1
v
2
u
1
v
2
with the FSM
Context
converted into an
automaton, and find in the composition an external sequence which is needed to
reach the final accepting state of
A.
u
1
v
2
u
1
v
2
/
; in this case one gets the external
sequence
i
2
i
2
.
When translating the above set of internal I/O sequences into external test cases
the following complete external test suite is obtained:
TS
ext
Dfi
2
i
2
i
2
i
2
;i
2
i
2
i
1
i
2
;i
1
i
2
i
2
g:
The test suite has three test cases with a total length of 11.
Note that following a black-box testing approach, a complete test suite with 192
test cases and a total length of 1664 can be derived, using the method of [108].
It detects errors in the same component assuming that the fault domain for the
FSM
Spec
with three states has all FSMs with up to four states, since some faulty
implementations of the embedded component with up to two states can induce a
composed FSM with four states.
The reduction achieved by deriving tests based on the largest solution of the
corresponding FSM equation is due to the fact that some of these FSMs cannot be
decomposed into a composition with the component FSM
Context
, and thus the fault
domain includes infeasible machines, i.e., the black-box testing approach is unable
to exploit the information about the restriction imposed by the composition with the
context.
We underline that there are two fault domains for FSMs to which the previous
discussions may refer according to the context. The first one is defined for the FSM
Emb
, as the set of all FSMs with at most 2 states over the alphabets
U
and
V
.The
second one is defined from the composed machine
Spec
as the set of all FSMs with
at most 4 states over the alphabets
I
and
O
. The second set includes all possible
products of the
Context
and each FSMs with at most 2 states over the alphabets
U
Search WWH ::
Custom Search