Software Testing and Quality Assurance

Theory and Practice

Chapter 10
Test Generation from FSM Models

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 1
 Outline of the Chapter
• State-oriented Model • Characterizing Sequence
• Points of Control and Observation • Test Architectures
• Finite-state Machine (FSM) • Testing and Test Control Notation 3
• Test Generation from an FSM (TTCN-3)
• Transition Tour Method
• Extended Finite-state Machines
• Testing with State Verification
• Test Generation from EFSM Models
• Unique Input/Output Sequence
• Additional Coverage Criteria for
System Testing
• Distinguishing Sequence
• Summary

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 2
 State-oriented Model
• Software systems
– State-oriented (Examples: Operating Systems)
– Stateless (Example: compiler)
• State-oriented system: two parts
– Control portion
– Data portion

Figure 10.1: Spectrum of software systems.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 3
 State-oriented Model
• The control portion of a system is
often modeled as an FSM.

Figure 10.4: FSM model of a dual-boot • Figure 10.5: The interactions between
laptop computer. a system and its environment are
modeled as an FSM.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 4
 Points of Control and Observation
• A PCO is a point of interaction
between a system and it users. PCO IN/OUT

Hook IN

Keypad IN

Ringer OUT

Speaker OUT

Mouthpiece IN

Figure 10.6: PCOs on a telephone Table 10.1: PCOs for testing a telephone
PBX.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 5
 Points of Control and Observation

• Figure 5.7: FSM model of a private branch exchange (PBX)

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 6
 Finite-state Machine (FSM)
• A finite-state machine
M = <S, I, O, s0, δ, λ>, where
• S is a set of states.
• I is a set of inputs.
• O is a set of outputs.
• s0 is the initial state.
• δ: S x I  S (next state function)
• λ: S x I  O (output function)

Figure 10.8: FSM model of a private

branch exchange (PBX).

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 7
 Test Generation from an FSM
• Let M be the FSM model of a system and IM be its implementation.
• An important testing task is to confirm if IM behaves like M.
• Conformance testing: Ensure by means of testing that IM conforms
to its spec. M.
• A general procedure for conformance testing
– Derive sequences of state-transitions from M.
• Turn each state-transition into a test sequence.
• Test IM with a test sequence to observe whether or not IM possesses the
corresponding transition sequence.
– The conformance of IM with M can be verified by choosing enough state-
transition sequences.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 8
 Transition Tour (TT) Method
• TT: It is a sequence of state-transitions
from the initial state to the final state.
• Example: From Figure 10.8
<OH, LP:OFH, LP:DT,AD>, <AD, LP:ONH, LP: -,
OH>

Figure 10.9: Interaction of a test sequence

with an SUT.

• Ideas in turning a TT into a test case.

– The input/output in a test case are
derives from a TT.
– Unexpected inputs must be processed.
– Indefinite waits must be avoided. Figure 10.10: Derived test case from
the transition tour.
Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 9
 Transition Tour (TT) Method
• Coverage metrics for FSM based testing
– State coverage
• Choose enough number of TTs to be able to cover each state at least
once.
– You can choose 3 TTs to cover all the states, but just 11 of the transitions.
– Transition coverage
• Choose enough number of TTs to be able to cover each state-transition
at least once.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 10
 Testing with State Verification
• Two functions associated with a state- • State verification with
transition – Unique Input/Output (UIO) sequences
– Output function: Easy to verify in the – Distinguishing sequences
TT method.
– Characterizing sequences
– Next-state function: Ignored in the TT
method (drawback of the TT method).

Figure 10.11: Conceptual model of a test

case with state verification.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 11
 Unique Input/Output Sequence
• Let X be an input sequence applied in a state s, and Y be the
corresponding output sequence.
• X/Y is a UIO sequence for s if no other state produces output
sequence Y in response to input X. Thus, X/Y is unique to s.
• Four assumptions about an FSM
– Completely specified
– Deterministic
– Reduced
– Strongly connected

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 12
 Unique Input/Output Sequence

Figure 10.12: Finite-state

machine G1.

Table 10.7: UIO sequences of

minimal lengths obtained
from Figure 10.14. Figure 10.14: Identification of UIO sequences on the UIO
tree of Figure 10.13 (Fig. 10.13 is similar to Fig. 10.14).

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 13
 Distinguishing Sequence
• Let X be an input sequence.
• X is a distinguishing sequence for an FSM, if each state produces a
unique (i.e. different) output sequence in response to X.
• Four assumptions about an FSM
– Completely specified
– Deterministic
– Reduced
– Strongly connected

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 14
 Distinguishing Sequence

Figure 10.15: Finite-state machine G2.

Table 10.9: Output of FSM G2 in

response to input sequence 11 in
different states.

Figure 10.16: Distinguishing sequence

tree for G2 in Figure 10.15.
Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 15
 Characterizing Sequence
• Some FSMs do not have a D-sequence.
– State verification is still possible.
– Use characterizing sets.
• Characterizing Sets (CS)
– A CS for a state s is a set of input sequences
such that, when each sequence is applied to
the FSM in s, the set of output sequences is
unique.
– Thus s is uniquely identified.

Figure 10.17: An FSM that does not possess a Figure 10.18: DS-tree for FSM (Figure 10.17).
distinguishing sequence.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 16
 Characterizing Sequence

Figure 10.10: Output sequences generated by the FSM of Figure 10.17 as a

response to W1.

Figure 10.11: Output sequences generated by the FSM of Figure 10.17 as a

response to W2.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 17
 Characterizing Sequence

Figure 10.12: Test sequences for the state transition (D, A, a/x) of the FSM in Fig.
10.17.
Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 18
 Test Architectures
• A test architecture is a certain
configuration of
– an Implementation Under Test
(IUT)
– one or more test entities,
– one or two PCOs, and
– a communication service provide.
• Common test architectures
– Local Architecture
– Distributed Architecture
– Coordinated Architecture
– Remote Architecture

Figure 10.19: Abstraction of an (N)-Entity

in the OSI reference architecture

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 19
 Test Architectures
• Local Architecture • Distributed Architecture

Figure 10.22: Local architecture. Figure 10.23: Distributed architecture.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 20
 Test Architectures
• Coordinated Architecture • Remote Architecture

Figure 10.24: Coordinated architecture. Figure 10.25: Remote architecture.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 21
 Testing and Test Control Notation 3 (TTCN-3)
• TTCN-3
– A language for specifying test cases.
– Predecessors were TTCN-1 and TTCN-2 (Tree and Tabular Combined
Notation)
– Standardized by ETSI (European Telecom. Standards Institute)
• Core features of TTCN-3
– Module
– Data types
– Templates
– Ports
– Components
– Test Cases

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 22
 Testing and Test Control Notation 3 (TTCN-3)
• Module

Figure 10.26: The structure of a module in TTCN-3.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 23
 Testing and Test Control Notation 3 (TTCN-3)
• Types, subtypes, and messages

Figure 10.27: Definitions of two subtypes.

Figure 10.28: A parameterized template for constructing a message to be sent.

Figure 10.29: A parameterized template for constructing a message to be sent.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 24
 Testing and Test Control Notation 3 (TTCN-3)
• Ports

Figure 10.30: Testing an application called SFC calculator (a) and a

port between the tester and the SFC calculator (b).
Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 25
 Testing and Test Control Notation 3 (TTCN-3)
• Ports and components

Figure 10.31: Defining a port type.

Figure 10.32: Associating a port with a component.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 26
 Testing and Test Control Notation 3 (TTCN-3)
• Ports and components

Figure 10.33: A test case for testing the square root function calculator.
Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 27
 Testing and Test Control Notation 3 (TTCN-3)
• Test case execution

Figure 10.34: Executing a test case.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 28
 Extended Finite-state Machines
• Two conceptual components of a software system are
– Flow of control
– Manipulation of data
• Manipulate local variables.
• Start and stop timers.
• Create instances of processes.
• Compare values and make control-flow decisions.
• Access databases.
• There is a need for modeling a software system as an EFSM.
• We consider the Specification and Description Languages (SDL).
– The basic concepts in SDL are as follows:
• System
• Behavior
• Data
• Communication
Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 29
 Extended Finite-state Machines

Figure 10.35: Comparison of state-transitions of an FSM and an EFSM.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 30
 Test Generation from EFSM Models
• Let E be an EFSM and PE be a program implementing E.
• Goal: Test that PE behaves as E.
• Basic idea
– Phase 1: Identify a set of state-transition sequences such that each sequence
of state-transitions represents a common use sequence.
– Phase 2: Design a test case from each state-transition sequence.
• Phase 1
– Pay attention to the following.
• Perform tests to ensure that the system under test (SUT) produces
expected sequences of outcomes in response to input sequences.
• Perform tests to ensure that the system under test takes the right actions
when a timeout occurs.
• Perform tests to ensure that the system under test has appropriately
implemented other task blocks, such as resource allocation, database
accesses, etc.
– Coverage criteria: state coverage and transition coverage.
Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 31
 Test Generation from EFSM Models
• Phase 2
– Transform the inputs and outputs in a transition tour into outputs and
inputs, respectively.
– Augment the above core test behavior with “otherwise” events to be able to
handle exception events.
– Augment the above test behavior with timers.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 32
 Test Generation from EFSM Models

Figure 10.36: Controlled access to a door.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 33
 Test Generation from EFSM Models

Figure 10.37: SDL/GR door control system.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 34
 Test Generation from EFSM Models

Figure 10.38: Door control behavior • Figure 10.39: Door control behavior
specification (1 of 2). specification (2 of 2).
Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 35
 Test Generation from EFSM Models

GETDIGIT  … GETDIGIT  … GETDIGIT  …

DOOROPEN  GETDIGIT.

Figure 10.40: A transition tour from the

door control system of Figs. 10.38
and 10.39

• Figure 10.41: Testing the door control

system.
Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 36
 Test Generation from EFSM Models

Figure 10.42: Output and input behavior obtained from the transition tour of
Fig. 10.10.
Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 37
 Test Generation from EFSM Models

Figure 10.43: Test behavior obtained by refining the “if” part in Fig. 10.42.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 38
 Test Generation from EFSM Models

Figure 10.44: Test behavior that can receive unexpected events. This is derived
from Fig. 10.43.
Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 39
 Test Generation from EFSM Models

Figure 10.45: The core behavior (partial) of a test case for testing the door control system. This is
derived from Fig. 10.44. (See the book for the complete test case.)

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 40
 Additional Coverage Criteria for System Testing
• PCO coverage
– Select test cases such that the SUT receives an event at each input PCO and
produces an event at each output PCO.
• Sequence of events at PCOs
– Select test cases such that common sequences of inputs and outputs occur at
the PCOs.
• Events occurring in different contexts
– An event generated at a PCO may have different meanings at different times.
• Inopportune events
– Inopportune events are normal events which occur at an inappropriate time.

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 41
 Summary
• Software systems • TTCN-3
– Stateless – Data types
– State-oriented – Modules
• Control portion is modeled by an – Ports
FSM or an EFSM. – Templates
• Testing FSM based systems • Testing EFSM based systems
– Transition tour method – Identify transition sequences
– State verification method – Turn each sequence into a test case
• State verification techniques • Input/output  Output/input
– Distinguishing sequence • “Otherwise” events
– UIO sequence • Timers
– Characterizing sequence – Coverage metrics
• Coverage metrics • PCO coverage
– State coverage • Sequences of events at each PCO
– State-transition coverage • Events occurring in different contexts
• Test architectures • Inopportune events
– Local
– Distributes
– Coordinated
– Remote

Software Testing and QA Theory and Practice (Chapter 10: Test Generation from FSM Models) © Naik & Tripathy 42