Testing from a state based specification
Many systems have some internal state that affects
and is affected by operations of the system.
Such systems are typically specified using state based
languages such as Statecharts, SDL, and Xmachines.
Systems specified using such languages may be
tested by applying methods based on
deterministic finite state machines (DFSMs) or
nondeterministic finite state machine (NFSM).
These test techniques are usually applied after the
specification has been converted into a DFSM or NFSM
by either expanding out the data (possibly after putting bounds on the types)
or by applying some abstraction.
The widespread use of state based systems,
and the importance of their correctness,
has led to much interest in testing from
DFSMs and NFSMs. Nondeterminism in the specification is not unusual.
Typically this comes either from
some abstraction that has been applied or there being a number of
acceptable behaviours in response to some input sequence.
However, most work has focused on testing from DFSMs rather than NFSMs.
When testing from an FSM M it is usual to assume that the
implementation under test (IUT) behaves likes some unknown element
of a given fault model.
Usually this fault model is the set, F,
FSMs with the same input and output
alphabets as M and no more than $m$ states
(some predetermined m).
Then a test suite is a checking experiment
if and only if it distinguishes
every element of F, that does not conform to M, from M.
Ideally, the test suite used is a checking experiment
but this is not always feasible  in such cases we typically
produce a test sequence that tests each transition of M.
Work in this area has considered a number of problems
including the following.
 Producing an efficient (minimum length) test sequence, from an FSM M,
that tests all of the transitions of M.
 Producing an efficient checking from an FSM M.
 Producing a (possibly adaptive) checking experiment
when testing from an NFSM.
 Testing from a specification written using a statebased
language (such as Statechart, SDL, or Xmachines) without encountering
problems (such as infeasible paths) through any abstractions applied.
 Locating a fault once a failure has been observed:
since the internal state is not directly observable, a
failure could be the result of a transition producing the
wrong output or a previous transition moving us to the
wrong state. Thus, additional testing may be required in
order to determine which transitions are erroneous and
we would like to minimise the amount of additional testing.

R. M. Hierons, Checking Experiments for Stream Xmachines,
Theoretical Computer Science (to appear).

R. M. Hierons and H. Ural, Generating a Checking Sequence with a minimum number of reset transitions, Automated Software Engineering, 17 3, pp. 217250, 2010.

Mercedes G. Merayo, Manuel Núñez, and Robert M. Hierons, Testing timed systems modeled by Stream XMachines,
Software and Systems Modeling (to appear).

R. M. Hierons:
Verdict Functions in Testing with a Fault Domain or Test Hypotheses,
ACM Transactions on Software Engineering and Methodology, 18 4, 2009.

R. M. Hierons and M. G. Merayo:
Mutation Testing from Probabilistic and Stochastic Finite State Machines,
Journal of Systems and Software, 82 11, pp. 18041818, 2009.

R. M. Hierons, M. G. Merayo, and M. Núñez:
Testing from a Stochastic Timed System with a Fault Model,
Journal of Logic and Algebraic Programming , 78 2, pp. 98115, 2009.

R. M. Hierons and F. Ipate:
Testing a deterministic implementation against a noncontrollable nondeterministic stream Xmachine,
Formal Aspects of Computing, 20 6, pp. 597617, 2008.

C. RobinsonMallett, R. M. Hierons, J. Poore, and P. Liggesmeyer:
Software Integration Testing based on Communication Coverage Criteria and Partial Model Generation,
Software Quality Journal, 16 2, pp. 185211, 2008.

Q. Guo, R. M. Hierons, M. Harman, and K. Derderian:
Heuristics for fault diagnosing when testing from finite state machines,
The Journal of Software Testing, Verification and Reliability, 17 1, pp. 4157, 2007.

R. M. Hierons and H. Ural:
Optimizing the Length of Checking Sequences,
IEEE Transactions on Computers,
55 5, pp. 618629, 2006.

Q. Guo, R. M. Hierons, M. Harman, and K. Derderian:
Improved Test Quality Using Robust Unique Input/Output Circuit Sequences (UIOCs),
Information and Software Technology, 48 8, pp. 696707, 2006.

K. Derderian, R. M. Hierons, M. Harman, and Q. Guo:
Automated Unique Input Output sequence generation for conformance testing,
The Computer Journal, 49 3, pp. 331344, 2006.

R. M. Hierons:
Separating Sequence Overlap for Automated Test Sequence Generation,
Automated Software Engineering,
13 2, pp. 283302, 2006.

Q. Guo, R. M. Hierons, M. Harman, and K. Derderian:
Constructing Multiple Unique Input/Output Sequences Using Metaheuristic Optimisation Techniques,
IEE Proceedings – Software, 152 3, pp.127140, 2005.

R. M. Hierons:
Testing from a NonDeterministic Finite State Machine Using Adaptive State Counting,
IEEE Transactions on Computers, 53 10, pp. 13301342, 2004.

R. M. Hierons:
Using a minimal number of resets when testing from a finite state machine,
Information Processing Letters, 90 6, pp. 287292, 2004.

R. M. Hierons, T.H. Kim, and H. Ural:
On The Testability of SDL Specifications,
Computer Networks, 44 5, pp. 681700, 2004.

R. M. Hierons:
Generating Candidates when Testing a Deterministic Implementation against a Nondeterministic Finite State Machine,
The Computer Journal,
46 3, pp.307318, 2003.

R. M. Hierons and H. Ural:
Reduced Length Checking Sequences
,
IEEE Transactions on Computers,
51 9, pp. 11111117, 2002. Erratum in 58 2, Feb 2009.

R. M. Hierons:
Checking States and Transitions of a set of Communicating Finite State Machines
,
Microprocessors and Microsystems,
Special Issue on Testing and testing techniques for
realtime embedded software systems,
24 9, pp. 443452, 2001.

R. M. Hierons, S. Sadeghipour, and H. Singh:
Testing a System specified using Statecharts and Z,
Information and Software Technology,
43 2, pp. 137149, 2001.

R.M. Hierons:
Minimizing the cost of Fault Location when testing from a Finite State Machine,
Computer Communications,
22 2, pp. 120127, 1999.

R.M. Hierons:
Adaptive Testing of a Deterministic Implementation Against
a Nondeterministic Finite State Machine,
The Computer Journal, 41 5, pp. 349355, 1998.

R.M. Hierons:
Testing from semiindependent communicating finite state machines with a slow environment,
IEE Proceedings on Software Engineering,
144 56, pp. 291295, 1997.

R.M. Hierons:
Testing From a Finite State Machine: Extending Invertibility to Sequences,
The Computer Journal, 40 4, pp. 220230, 1997.

R.M. Hierons:
Extending Test Sequence Overlap by Invertibility,
The Computer Journal, 39 4, pp. 325330, 1996.
Back to Rob Hierons'
home page
Last updated: June 2010.
Disclaimer The contents of this page falls
outside the responsibility of Brunel University.