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 X-machines. Systems specified using such languages may be tested by applying methods based on deterministic finite state machines (DFSMs) or non-deterministic 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. Non-determinism 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 state-based language (such as Statechart, SDL, or X-machines) 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 X-machines, 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. 217-250, 2010.
• Mercedes G. Merayo, Manuel Núñez, and Robert M. Hierons, Testing timed systems modeled by Stream X-Machines, 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. 1804-1818, 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. 98-115, 2009.
• R. M. Hierons and F. Ipate: Testing a deterministic implementation against a non-controllable non-deterministic stream X-machine, Formal Aspects of Computing, 20 6, pp. 597-617, 2008.
• C. Robinson-Mallett, 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. 185-211, 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. 41-57, 2007.
• R. M. Hierons and H. Ural: Optimizing the Length of Checking Sequences, IEEE Transactions on Computers, 55 5, pp. 618-629, 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. 696-707, 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. 331-344, 2006.
• R. M. Hierons: Separating Sequence Overlap for Automated Test Sequence Generation, Automated Software Engineering, 13 2, pp. 283-302, 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.127-140, 2005.
• R. M. Hierons: Testing from a Non-Deterministic Finite State Machine Using Adaptive State Counting, IEEE Transactions on Computers, 53 10, pp. 1330-1342, 2004.
• R. M. Hierons: Using a minimal number of resets when testing from a finite state machine, Information Processing Letters, 90 6, pp. 287-292, 2004.
• R. M. Hierons, T.-H. Kim, and H. Ural: On The Testability of SDL Specifications, Computer Networks, 44 5, pp. 681-700, 2004.
• R. M. Hierons: Generating Candidates when Testing a Deterministic Implementation against a Non-deterministic Finite State Machine, The Computer Journal, 46 3, pp.307-318, 2003.
• R. M. Hierons and H. Ural: Reduced Length Checking Sequences , IEEE Transactions on Computers, 51 9, pp. 1111-1117, 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 real-time embedded software systems, 24 9, pp. 443-452, 2001.
• R. M. Hierons, S. Sadeghipour, and H. Singh: Testing a System specified using Statecharts and Z, Information and Software Technology, 43 2, pp. 137-149, 2001.
• R.M. Hierons: Minimizing the cost of Fault Location when testing from a Finite State Machine, Computer Communications, 22 2, pp. 120-127, 1999.
• R.M. Hierons: Adaptive Testing of a Deterministic Implementation Against a Nondeterministic Finite State Machine, The Computer Journal, 41 5, pp. 349-355, 1998.
• R.M. Hierons: Testing from semi-independent communicating finite state machines with a slow environment, IEE Proceedings on Software Engineering, 144 5-6, pp. 291-295, 1997.
• R.M. Hierons: Testing From a Finite State Machine: Extending Invertibility to Sequences, The Computer Journal, 40 4, pp. 220-230, 1997.
• R.M. Hierons: Extending Test Sequence Overlap by Invertibility, The Computer Journal, 39 4, pp. 325-330, 1996.

Back to Rob Hierons' home page

Last updated: June 2010.