6 STATE TRANSITION TESTING

STATEFUL AND STATELESS SYSTEMS

In the previous chapter, we considered test techniques for stateless software. Statelessness means computational independency on any preceding events in a sequence of interactions. A stateless application decouples the computations from the states; it is dependent only on the input parameters that are supplied. Simple examples are:

In these cases, a stateless system/function returns the same value for the same arguments. The computations are replaceable without changing the behaviour of the application.

On the other hand, stateful applications have internal states. These internal states need some place for storage (allocated memory, database, etc.). When a stateful function is called several times, then it may behave differently. From the test design point of view, it is more difficult to test since it must be treated together with the preceding events. An operating system is stateful. If you set your screen resolution, next time you switch on your machine, this resolution is preserved.

STATES, TRANSITIONS, CONDITIONS

Most complex systems are stateful. Many of them are event-driven (or reactive) in which they wait continuously for some external or internal event (mouse click, time tick, data packet, button press, etc.), and after recognising the event, react to them by performing some computation or by triggering other software components. Such systems can have more than one state and exhibit different behaviours in different states. There can be various transitions between the states.

There are two main ways to represent stateful systems: using state transition diagrams (graphs) or state transition tables. In the first case, the nodes represent states and the edges represent transitions. If the system is in state s1, and an input event/trigger E occurs, then the system changes its state to s2 via the transition t, producing the output action O (see Figure 6.1).

Figure 6.1 State transition diagram. A transition t occurs from state s1 to s2, which is triggered by some input event E and resulting in an output action O

Roughly speaking, a transition consists of a start state + an input event + an action + a next state. In an extended model, the transition and the resulting state may also depend on some conditions. For example, by clicking on the ‘+’ button next to some food to be ordered, if the maximum number of the ordered item has been reached, then nothing happens, while in other cases the ordered amount is incremented. Such guard conditions are usually denoted by Event/[condition]/Action.

It is important to note that for any given state an event can cause an action (or set of actions), but the same event – from a different state – may cause a different action and transitions to a different state. In practice, an action set may include programming elements, that is code.

There are two common ways to arrange state transition data in a table.

Table 6.1 State–event notation for a state transition table

Table 6.2 State–state notation for a state transition table

Note that an action may consist of independent, simple actions. Valid transitions are transitions described in the model (see Figure 6.1 and Tables 6.1 and 6.2). However, there can be some undefined (‘−‘) transitions in both tables. These transitions may mean that the specification is incomplete; therefore the tester should analyse undefined transitions thoroughly.

In practice, incomplete specifications can be handled in two ways: (1) the system does not change its state, and there is no output (the undefined transition meets the specification) or (2) there should be a transition to an error state (each event should be handled). An invalid transition refers to the transition that transforms the system into a state that causes the incorrect or undefined behaviour of the system, indicating that such transitions are not feasible. In some cases, it is useful to use a transition without any output (e.g. allocating a resource that is not available, or a timeout happens). We call these null transitions. Null transitions can have guards (for example, [timer = 3]). Note that undefined or null transitions are not necessarily invalid.

A state transition graph always has a start and may have one or more end nodes. Each node has to be accessible from a start node, and loops in the graph are allowed.

EXAMPLE: ROBODOG

Imagine a robot dog that barks, wags its tail and sometimes interacts with a robot cat. We will demonstrate the usage of state transition testing with the behaviour analysis of such an item.

Preconditions: the RoboDog is switched on, all of its sensors are functioning.

States:

Input (events):

Output (actions):

Transitions:

The state diagram and the associated state table are in Figure 6.2 and Table 6.3, respectively.

The state transition table (Table 6.3) shows some undefined transitions. If the RoboDog barks (the automaton is in state s2), the command ‘speak’ or spotting a RoboCat have nothing to activate. If the RoboDog is in a normal state, the command ‘quiet’ has no effect either. We extend the state machine with null transitions (Table 6.4).

Figure 6.2 State diagram for the ‘RoboDog’ example

Table 6.3 State–event notation for the ‘RoboDog’ example with undefined transitions

Table 6.4 State–event notation for the ‘RoboDog’ example

Let’s alter the RoboDog specification with the following:

The state table changes (as shown in Table 6.5) where there are new actions, namely

Table 6.5 State–event notation for the extended ‘RoboDog’ example

We note that PettingNo should be global for the system and initiated to zero at the beginning (precondition). See the resulting state diagram (Figure 6.3).

Figure 6.3 State diagram for the extended ‘RoboDog’ example

Altogether we have two states, four events and five possible actions. Observe that the guard conditions for the petting number cover the whole domain, that is 0 ≤ PettingNo < 3 or PettingNo = 3; other values are not possible.

VALIDATE YOUR STATE TRANSITION GRAPH

When the state transition graph (or table) has been created the test designer must carefully analyse and validate it.

The following guidelines help in analysing the completeness and consistency of the state transition graph model.

Practically speaking:

When we test a stateful system (system under test, SUT), sometimes it is desirable to fulfil certain properties:

All of these properties can be present reliably or unreliably. The following checklist extends the previous guidelines:

Satisfying a test selection criterion, we shall cover the nodes/edges/paths of the state transition graph. Also we have to consider the semantics of the graph (the specification) as well. For example, in the extended RoboDog example, the transition t6 can happen only after petting twice the flustered RoboDog.

There are different fault models available to the stateful systems.

Validating the state machine against control faults

When testing an implementation against a state machine, the following typical control faults should be examined.

TEST SELECTION CRITERIA FOR STATE TRANSITION TESTING

State transition testing is measured mainly for valid transitions. There are many different test selection criteria regarding the transition-based method. First, we explain only the methods, then we show their thoroughness.

Test selection criteria for transition-based models

The examples in this subsection come from Figure 6.2, and we always aim to achieve full (100 per cent) coverage. We use the usual ‘big oh’ notation for describing the time complexities for calculating the tests.

Classical criteria

The following criteria are related to the states, events and transition sequences:

The following criteria are related to traversing the possible loops:

The following is not really a criterion, but it is a useful non-deterministic technique for traversing a graph.

We have to discuss the ‘minimality’ of the constructed sets. Before optimising the test sets, a target function should first be determined. This can be the expected running time, some restrictions on the number of the test cases, the number of transitions in a test case, the average length of the tests and so on. This optimisation can be hard, as with pairwise testing, whose task is nondeterministic polynomial (NP)-complete (Lei and Tai, 1998). In practice, however, it is enough to approach close to the optimum value.

All-transition-state and all-transition–transition criteria

Unfortunately, simple criteria are sometimes weak; strong criteria may lead to exponential explosion. The main question is as follows: Is there any criterion between them that is both reliable and manageable? Here we introduce two criteria, which we think of as both reliable and ‘cheap enough’ to use in practice.

The rationale behind these criteria is the following:

With these three requirements the first test selection criterion is the following:

ALL-TRANSITION-STATE CRITERION

For a given transition t let’s denote the set of all reachable states by RS(t) for which there is a path via the transition t to any element of RS(t). Then, satisfying the criterion means that

Note that reachability mainly means available paths in the state transition graph, but may mean feasibility (executability) in the case of test generation. Note as well that satisfying the all-transition-state criterion also satisfies the all-transitions criterion.

Now let’s consider our RoboDog example and investigate the test (steps) to satisfy this criterion. The graph is strongly connected; moreover, by deleting any transition except t4, it remains strongly connected. Hence, the sequence

s1-t2-s1-t1-s2-t5-s2-t4-s1-t3-s2-t4-s1

covers the (t, s) paths for all transition t and s ϵ RS(t), and the sequences

s1-t1-s2-t4-s1, s1-t3-s2-t4-s1

cover the (!t, s) paths. The appropriate test set is

{[pet, speak, pet, quiet, cat, quiet], [speak, quiet], [cat, quiet]}.

Sometimes even this test selection criterion is weak. For a stronger criterion, we have to consider each (t, t’) pairs. The related definition is the following:

ALL-TRANSITION–TRANSITION CRITERION

For a given transition t let’s denote the set of all reachable transitions from t by RT(t) for which there is a path via the transition t to any element of RT(t). In the case of looping, t ϵ RT(t). Then, the coverage means that

Complexity: without the third condition, the number of test cases is quadratic in the worst case since we shall cover pairs of transitions. The existence of boundaries may increase the complexity proportionally to their maximal value.

How can we satisfy this stronger criterion for the extended RoboDog? Since the state transition graph of the RoboDog is Eulerian, that is we start from s and traversing each edge only once we can go back to s, the path

s1-t1-s2-t4-s1-t2-s1-t3-s2-t5-s2-t4-s1-t2-s1-t1-s2-t4-s1-t3-s2-t5-s2-t4-s1

satisfies the first criterion, and partly the second, that is

(!t1, t1), (!t2, t1), (!t3, t1), (!t4, t1), (!t5, t1), (!t2, t4), (!t3, t4), (!t4, t4), (!t5, t4), (!t2, t2), (!t3, t2), (!t5, t2), (!t3, t3), (!t5, t3), (!t5, t5).

The rest can be satisfied with the paths

s1-t2-s1-t3-s2-t4-s1-t1-s2-t4-s1, s1-t3-s2-t5-s2-t4-s1 and s1-t1-s2-t5-s2-t4-s1

since in these cases the following pairs are valid:

(!t1, t2), (!t4, t2), (!t4, t3), (!t1, t3), (!t2, t3), (!t1, t4), (!t1, t5), (!t2, t5), (!t4, t5), (!t3, t5).

The test set is

{[speak, quiet, pet, cat, pet, quiet, pet, speak, quiet, cat, pet, quiet], [pet, cat, quiet, speak, quiet], [cat, pet, quiet], [speak, pet, quiet]}.

Recall that the Chow coverage test set becomes exponentially larger with growing n. We note that the all-transition-state and the all-transition–transition criteria measures may serve as a bridge between the linearity and the exponentiality. These two criteria aim at examining defects that cannot be unfolded by Chow’s switching criteria, that is when the defects are ‘far away’ from each other. The boundary value guard is related to boundary value analysis.

Thoroughness of the criteria

Recall that the extended RoboDog state transition graph contains two states, four events, and six transitions. The extra precondition of this state transition diagram is that the global variable PettingNo is defined as zero. Let’s suppose that the behaviour shown in Figure 6.4 has been implemented.

There are three changes (faults) compared to the specified behaviour. In transition t3 there is a missing initialisation, and instead of three, after the fourth time petting, the flustered RoboDog stops barking, wags its tail and goes quiet (these faults are in the transitions t5 and t6). Of course, the black-box tester does not know about this. Suppose that the tester designs the test cases for satisfying the all-states, all-events, all-actions, all-transitions criteria according to the model shown in Figure 6.3.

Figure 6.4 Programmed behaviour of the ‘RoboDog’. The difference from the specified behaviour is underlined

Table 6.6 shows a simple short test. The test does not show any faults. The faults are in combination, that is the missing initialisation causes RoboDog to quiet at step 8. OK, we think, very good, let’s check the 1-switch criterion by Chow. The clever tester observes that the transition pairs t1–t6 and t3–t6 are impossible (because of the specification), therefore they omit them from the test design. To spare time, the tester divides the previous test into two parts: ShortTest = [t2, ShorterTest]. Then, their result is the following test:

Table 6.6 Short test for the extended ‘RoboDog’ example

{[ShortTest-ShorterTest-t3-t4], [t2-t3-t4-t1-t4-t2], [ShorterTest-t2]}.

It is easy to check that this test set fulfils the 1-switch coverage criteria, but does not find the faults. The reason is that we have a 2-switch fault, hence, only the 2-switch criteria would be able to find it.

Kuhn et al. (2008) determined that up to 97 per cent of software faults can be detected by at most two variables interacting. These criteria consider pairs, which influence each other. Chow’s switch coverage considers only adjacent transitions, but erroneous influence may come from remote transitions as well. The all-transition-state criterion considers arbitrary (transition, state) pairs; the all-transition–transition criterion arbitrary (transition, transition) pairs. The method could be extended to triples, but pairs are usually enough.

Let’s summarise why the proposed criterion is useful. Regarding EFSMs, in some cases, guard condition variable assignments (initialisations) are in the wrong places. To detect this problem, we should cover an execution path excluding a transition with this assignment. Traversing every (!t, s) or (!t1, t2) will reveal the bug. Considering the last criterion, guard condition boundaries should be handled with boundary value analysis techniques.

EXAMPLE: COLLATZ CONJECTURE

Finite-state machines are used to model complex logic in dynamic systems, such as automatic transmissions, robotic systems and mobile phones. This complex logic includes operations like scheduling tasks, supervising how to switch between different modes of operation, recovery logic and so on.

The following example presents complex logic with elementary operations. We show how to model it with a state transition graph, and we analyse some loop-related test selection criteria.

Preconditions: there is a global integer variable n, initially set to zero. The variable n can arbitrarily be large. The input is a positive integer.

States:

Input (event):

Output (action):

Transitions:

The Collatz machine is in Figure 6.5.

Figure 6.5 Collatz machine

Let’s check the functioning. When the input is 1, 3 or 5 the processing goes through s1-t1-s2-t2 and the output is a message about termination. When the input is 2 or 4, the processing is via s1-t3-s3-t4 and there is a termination message again. Let the input be the magic number 42. Then the processing is the following: s1-t3(n = 42)-s3-t6 (n = 21)-s2-t5(n = 64)-s3-t7(n = 32)-s3-t7(n = 16)-s3-t7(n = 8)-s3-t7(n = 4)-s3-t4 and the output is the termination message. The termination was checked for integers up to 87 × 2⁶⁰ by Roosendaal (2018).

The test data 2 (traversing t3-t4) and 3 (traversing t1-t2) traverses all loop-free paths since t1-t5-t4 and t3-t6-t2 are impossible to get around without looping. Let’s analyse the all-round-trip paths criterion. The only simple paths in the graph are t1-t2, t3-t4, t3-t6-t2 and t1-t5-t4. Hence, the tests for this criterion are identical to the all-loop-free paths tests. To get tests for the all-one-loop path criterion, we have to add one loop for the possible loop-free paths. The transition sequence t3-t7-t4 is reliable; the test data is (for example) 8. The sequence t3-t6-t5-t4 is unreliable. The sequence t3-t7-t6-t2 is reliable with test data = 6. The sequence t1-t5-t7-t4 is unreliable as well as the sequence t1-t5-t6-t2.

WHEN MULTIPLE TECHNIQUES ARE USED TOGETHER

This may be a surprise, but it’s difficult to find any description or examples on how to apply more test design techniques together. Here is a short introduction where we demonstrate using multiple techniques through our example. Usually we combine two techniques, therefore we will demonstrate this case; however you can easily extend it.

In this section we consider a specific, simplified part of the specification ‘Two lifts in a 10-storey building’ described in Chapter 4. The slightly reduced specification can be tested independently from the other parts. The most important requirement in this case says that all the guests should be served (sooner or later). For example, if the lift goes down from the upper floor, and the guest − who called it first − is standing on the fifth floor, but after a few seconds a family calls the lift at the sixth floor, then the lift may become full, and the guest at five cannot enter. The specification guarantees that a similar situation cannot happen (except when the lifts never become empty, but this case is unrealistic).

Here we have omitted some of the steps in the original specification (see Chapter 4).

Here we do not consider priorities.

This is a good example as different test design techniques are applied together. Clearly, the model is reactive since it contains states such as vacant, moving or standing lifts (waiting for the guests to leave and/or enter).

For this example, we show you step by step how to design test cases involving STT, EP and BVA together. The first step is to create the state transition diagram.

Preconditions: the starting state is when both lifts are vacant.

States:

Inputs (event)

Note that if not all the guests leave a lift, then there shall be a guest request. Here we do not consider the non-functional requirement when a guest is not able to get out or press a button. Remember an outside guest calls a lift; a guest inside the cabin requests the lift to stop at a chosen floor.

Outputs:

Transitions:

Note that ‘acceptable call’ means that:

The system is concurrent since ‘it includes a number of execution flows that can progress simultaneously, and that interact with each other’ (Bianchi et al., 2017). Extension of state diagrams are Harel (and Unified Modelling Language (UML)) statecharts (see the ‘Theoretical background’ section later in this chapter). Concurrency in statecharts can be shown explicitly using ‘fork’ and ‘join’. A fork is represented by a bar with more outgoing arrows; a join is represented by a bar with more incoming arrows.

Here we have two parallel sub-systems: one for Lift1 and the other for Lift2. For simplicity we cut the state transition diagram into two parts (Lift1 and Lift2 are L1 and L2, respectively, see Figures 6.6a and 6.6b). The figures are almost symmetric (t2 does not have a ‘pair’).

Figure 6.6a State transition graph for ‘Two lifts in a 10-storey building’ – Lift1

Let’s consider some examples.

Up to now we have not considered testing concurrent systems. There are several test selection criteria for concurrent systems (Bianchi et al., 2017). Here we consider a very simple criterion that requires all states to be held in parallel. For example, if Lift1 is moving, then Lift2 shall (1) stand (2) move, (3) remain vacant.

Figure 6.6b State transition graph for ‘Two lifts in a 10-storey building’ – Lift2

We can extend the all-state-transition criterion for concurrent systems in a way that each (transition, state) pair is executed for all concurrent execution flows.

According to this criterion we have the following test steps for Figure 6.6a, and remember that the two sub-diagrams are similar as L1 → L2 and L2 → L1.

The test path for the concurrent case (ST-Tpath2) is described by two parallel sequences containing the states such as s6 L1 is standing and transitions such as t5 – there are remaining guest requests.

ST-Tpath1: simple, see Table 6.7.

ST-Tpath2: both lifts are vacant at the beginning and the end of this test path, see Table 6.8.

Table 6.7 State transition test for ‘Two lifts in a 10-storey building’, ST-Tpath1

s1 L1, L2 are vacant

t1 – to different floor

s4 L1 is moving  t4 – guest target is approached

s6 L1 is standing  t5 – there are remaining guest requests

s4 L1 is moving  t4 – guest target is approached

s6 L1 is standing  t6 – all guests leave L1

s1 L1, L2 are vacant

Table 6.8 State transition test for ‘Two lifts in a 10-storey building’, ST-Tpath2

Lift1	Lift2
s1 L1, L2 are vacant t1 – to different floor
s4 L1 is moving  t3 – acceptable guest call to next floor	s3 L2 vacant
s6 L1 is standing  t5 – there are remaining guest requests
s4 L1 is moving  t3 – acceptable guest call to the next floor
s6 L1 is standing  t5 – there are remaining guest requests
s4 L1 is moving
t4 – guest target is approached	t18 – guest call from the same floor
s6 L1 is standing	s7 L2 is standing
t6 – all guests leave L1	t15 – there are remaining guest requests
s2 L1 is vacant	s5 L2 is moving
	t14 – guest target is approached
t7 – guest call from different floor	s7 L2 is standing
s4 L1 is moving	t16 – all guests leave L2
t3 – acceptable guest call to next floor	s3 L2 vacant
s6 L1 is standing
t5 – there are remaining guest requests	t17 – guest call from different floor
s4 L1 is moving	s5 L2 is moving
t4 – guest target is approached	t13 – acceptable guest call to next floor
s6 L1 is standing	s7 L2 is standing
t6 – all guests leave L1	t15 – there are remaining guest requests
s2 L1 is vacant	s5 L1 is moving
	t13 – acceptable guest call to the next floor
	s7 L2 is standing
	t15 – there are remaining guest requests
t8 – guest call from the same floor	s5 L2 is moving
s6 L1 is standing	t14 – guest target is approached
t5 – there are remaining guest requests	s7 L2 is standing
s4 L1 is moving	t16 – all guests leave L1
t4 – guest target is approached	s3 L2 is vacant
s6 L1 is standing
t6 – all guests leave L1
s2 L1 vacant	t19 – L1 becomes vacant
t9 – L2 becomes vacant
s1 L1, L2 are vacant

Here, the left column contains the movement of Lift1 (L1) and the right one contains the movement of Lift2 (L2). Lift1 is vacant four times (1) at the beginning, (4) at the end and (2), (3) to test guest calls from different floors (2), and a guest call from the same floor (3). Lift2 is vacant three times (1) for testing guest calls from the same floor, (2) testing a guest call from different floors and (3) when both lifts become vacant. The vacancies happen at different times, hence the concurrent test selection criterion is satisfied.

We can see that except for t2, all the transitions are covered. We traverse ST-Tpath2, then ST-Tpath4 in a similar way, which result in the ‘traditional’ all-state transition criterion being satisfied. This is because in traversing ST-Tpath4, all the states are covered after t2 and all other transitions in ST-Tpath2. We have the 4^th test path ST-Tpath3, which is symmetric with ST-Tpath1.

Now let’s consider the EP and BVA part. We have two lifts, Lift1 and Lift2. The third ‘participant’ is the guest calling them. There are several different locations of this {Lift1, Lift2, guest} triple. There are several elements of this triple; however, we can classify them. For example, the cases (Lift1=2, Lift2=9, guest=3) are similar to (Lift1=2, Lift2=8, guest=4) as in both cases Lift1 shall start. In this way the elements in the triple can be classified into four EPs:

Let’s extend the EPs with boundary values. Though three points are required for each EP, because of overlap, eight test cases are enough. The test inputs are shown in Table 6.9.

Table 6.9 BVA test input for ‘Two lifts in a 10-storey building’, ST-Tpath1

There are also equivalence partitions related to the guests: whether they can be picked up or not by a moving lift. These EPs shall be tested in a way that if a guest cannot be picked up, then the other lift shall start. There are other EPs to test whether the moving lift stops or the other will start:

Note that ‘approaching’ floor x means moving to floor x and possibly standing between moving to y and moving from y to x. We do not consider the EPs when one lift is vacant, and the guest is on the same or different level. This is because we have covered these cases by covering the related transitions.

The next step is to combine the test design techniques. Here we start from STT and map a BVA test to it. We design our first test case based on ST-Tpath2 (see Table 6.10). Here the events occurring at a state are to the right of the state, for example Lift1 is standing at (floor) 7 when Guest1 pushes (floor) 1.

Table 6.10 BVA test input for ‘Two lifts in a 10-storey building’, ST-Tpath2

Besides the EP3 ON point, we have covered EP11, EP12, EP15 and EP16. We can easily cover the EP1 ON point, EP13, EP14, EP17 and EP18 in ST-Tpath4. We can cover the remaining two ON points by ST-Tpath1 and ST-Tpath2. Finally, we should test the remaining four IN points by four simple test cases avoiding concurrency.

Summarising, when combining more techniques, a possible process is the following:

STATE TRANSITION TESTING IN TVM EXAMPLE

Let’s consider the following part of the example TVM specification.

We model the ticket selection process of the TVM with a state transition graph. The first step is to create the state transition diagram. Usually, this is the simplest task. To do this, you must read the specification at least twice, maybe more times, and very carefully. You cannot create the correct graph until you really know this part of the specification.

If you know it well, you can start the design.

First, make a draft version by considering all the states, events and actions, then the ‘forward’ and ‘backward’ transitions one by one. The design is always an iterative process – it is not a problem if the draft version is not complete or is inconsistent. Approach the final version step by step. Finally, validate the graph.

Precondition: the TVM shows the initial ticket selection screen. The number of tickets is set to zero (NrT := 0) and the ticket type value is empty (TicketType := ‘ ’).

States:

Input (events):

Output (actions):

Transitions:

The state transition graph of the TVM can be seen in Figure 6.7.

The next task is to choose the test selection criterion and to create the test cases based on the graph. In our case, the all-transition-state criterion seems to be the most promising. The others have either too weak fault-detection capabilities or need too many test cases.

We can see that the graph is symmetric for the ticket types available to buy. Clearly, for all transitions t, except t13, t14 and t15, the reachable states are RS(t) = {s1, s2, s3, s4, s5}. The following three tests cover those (t, s) pairs for which from each transition t there is a path to all the elements of RS(t). For clarity, we use the names of the transitions and the abbreviation of the states as follows: St, 24, Short, Success and Init:

Tpath1 = Init – incStan – St – incStan – St – decStan – Init – incStan – St – decStan – Init – incShort – Short – decShort – Init – inc24 – 24 – selectPay – Payment

Tpath2 = Init – incShort – Short – incShort – Short – decShort – Init – incShort – Short – decShort – Init – inc24 – 24 – dec24 – Init – incStan – St – selectPay – Payment

Tpath3 = Init – inc24 – 24 – inc24 – 24 – dec24 – Init – inc24 – 24 – dec24 – Init – incStan – St – decSt – Init – incShort – Short – selectPay – Payment

From the first test only (t13: selectPay, s5: Payment), (t14: selectPay, s5: Payment), from the second only (t14: selectPay, s5: Payment), (t15: selectPay, s5: Payment), from the third only, the pairs (t13: selectPay, s5: Payment), (t14: selectPay, s5: Payment) are missing. Considering all these three paths, we satisfied (1) in the definition. Regarding the second criterion, it is easy to see that the path (t1: incStan-s2: St-t13: selectPay-s5: Payment) avoids all transitions except t1: incStan and t13: selectPay and reaches s2: St and s5: Payment. Extending the three tests above with the following basic paths, criterion (2) fulfils in the all-transition-state definition:

Figure 6.7 Ticket selection transition graph for the TVM

Tpath4 = Init – incStan – St – selectPay – Payment

Tpath5 = Init – incShort – Short – selectPay – Payment

Tpath6 = Init – inc24 – 24 – selectPay – Payment

Now we concentrate on the boundary values and extend our tests. This means, for example, that we try to increment the number of tickets above 10 and decrement it below 0. Even if it was successful, we could continue the testing. For automated tests, after the failed code is fixed, it is re-executed.

When the same event E happens n-times consecutively, we will shorten it by nx, for example E7x (apply the event E seven times). The six test cases are in Tables 6.11a–6.11f. Within these tables, Stan ticket stands for Standard ticket.

Table 6.11a State transition tests for the TVM-Test-1

Table 6.11b State transition tests for the TVM-Test-2

Table 6.11c State transition tests for the TVM-Test-3

Table 6.11d State transition tests for the TVM-Test-4

Name: TVM-Test-4
Steps	1	2
Events	incStan	selectPay
Trans. no.	t1	t13
States (from/to)	s1/s2	s2/s5
Expected result	1 Stan ticket	1 Stan ticket
Observed result

Table 6.11e State transition tests for the TVM-Test-5

Name: TVM-Test-5
Steps	1	2
Events	incShort	selectPay
Trans. no.	t2	t14
States (from/to)	s1/s3	s3/s5
Expected result	1 Short ticket	1 Short ticket
Observed result

Table 6.11f State transition tests for the TVM-Test-6

Name: TVM-Test-6
Steps	1	2
Events	inc24	selectPay
Trans. no.	t3	t15
States (from/to)	s1/s4	s4/s5
Expected result	1 24h ticket	1 24h ticket
Observed result

This example will be extended in the Gherkin-based test design chapter (Chapter 12) by paying for the tickets. In that case, STT and EP and BVA shall also be applied together.

METHOD EVALUATION

In this section we evaluate the state transition test design technique from various perspectives.

Applicability

The state transition testing technique can be applied when the system is defined in terms of a finite number of states and the transitions between the states are triggered by the rules of the system. Practically, the technique is usable for real applications involving states and transitions. This method is especially good for end-to-end testing of large systems, testing embedded systems, web applications, compilers, telecommunication protocols and so on.

Types of defects

The technique can detect integration and system errors even in large systems. Typical defects include incorrect or unsupported transitions, unreachable or non-existent states, omissions (there is no information about what the automaton should do in a certain situation) and inconsistent model descriptions. State transition testing can reveal some predicate errors as well.

Advantages and shortcomings of the method

The advantages of the state transition testing method are:

The limitations and shortcomings of the method are:

THEORETICAL BACKGROUND

A state machine is a mathematical model of computation. The roles of state machines in software testing are: (1) before starting the actual implementation, an executable state machine may simulate the model with event sequences as test cases, (2) supports testing against the specification and (3) supports automatic test generation (there should be an explicit mapping between the state machine elements and the elements of the implementation, e.g. classes, objects, attributes, etc.).

The behaviour of discrete systems can be described by different models. Labelled or unlabelled transition systems are used to describe dynamic processes with configurations representing states and transitions prescribing how to go from state to state. Transition systems are mathematically equivalent to abstract rewriting systems or with directed graphs. Finite-state machines differ from them in several ways, namely, FSMs have a finite set of states and transitions, and have start nodes and so on. FSMs have less computational power than Turing machines or pushdown automatons since their memories are limited by their finite number of states. State machines are used to give an abstract description of the system’s behaviour. This behaviour is analysed and represented as a series of events that can occur in one or more possible states. State diagrams are used to graphically represent those (finite-state) machines. Many forms of state diagrams exist, which are all slightly different.

Statecharts refer to Harel’s notation described in Harel (1987), which was proposed as a significant notational extension over traditional finite-state machines. Statecharts have been incorporated in the UML by introducing the concept of hierarchically nested states (logically connected subgraphs can cluster into a new super-state) and orthogonal regions (orthogonality means compatibility and independency in the given context). With this hierarchical clusterisation, the state transition testing becomes possible even for large systems. UML state machines have the characteristics of both Mealy and Moore machines.

Specification and Description Language (SDL) state machines from the ITU (International Telecommunication Union) include graphical symbols to describe the actions in the transitions (timers, sending, receiving messages, etc.). SDL combines together abstract data types, an action language and an executing semantic to make the machine executable.

While using an FSM for embedded system design, the inputs and outputs are Boolean data types, and the functions represent Boolean functions with Boolean operations. This model is enough to describe control systems without involving input or output data. When data is to be dealt with, EFSM is needed.

The applicability of state diagrams in testing was observed in the 1970s. One of the first and the most cited papers is the work of Chow (1978), who proposed a method of testing the correctness of control structures that can be modelled by a finite-state machine. Test results derived from the design are evaluated against the specification. No ‘executable’ prototype was required. Clearly, his testing method was an early test-first method. You can read more on this topic in Chapter 11.

KEY TAKEAWAYS

EXERCISES

E6.1 Construct test paths applying the all-transition–transition criterion for ‘TVM ticket selection’ (see TVM example earlier in the chapter and Figure 6.7).

E6.2 Ordering water from an online shop. The types of water can be still or sparkling. We can buy bottles of one type only. If nothing is selected, then the quantity of either of them can be increased. After one has been selected, only one of the water types with a non-zero amount can be increased or decreased by one. The maximum number of bottles to be ordered is five. If the selected number of bottles is greater than 0, then the buying process can start. The output is the type and number of the selected bottles.

Model the buying process for this example with a state transition graph and design tests for the following test selection criteria: