State-Transition Testing

Colonel Cleatus Yorbville had been one seriously bored astronaut for the first few months of his diplomatic mission on the third planet of the Frangelicus XIV system, but all that had changed on the day he'd discovered that his tiny, multipedal and infinitely hospitable alien hosts were not only edible but tasted remarkably like that stuff that's left on the pan after you've made cinnamon buns and burned them a little.

— Mark Silcox

Introduction

State-Transition diagrams, like decision tables, are another excellent tool to capture certain types of system requirements and to document internal system design. These diagrams document the events that come into and are processed by a system as well as the system's responses. Unlike decision tables, they specify very little in terms of processing rules. When a system must remember something about what has happened before or when valid and invalid orders of operations exist, state-transition diagrams are excellent tools to record this information.

These diagrams are also vital tools in the tester's personal toolbox. Unfortunately, many analysts, designers, programmers, and testers are not familiar with this technique.

Technique

State Transition Diagrams

It is easier to introduce state-transition diagrams by example rather than by formal definition. Since neither Brown & Donaldson nor the Stateless University Registration System has substantial state-transition based requirements let's consider a different example. To get to Stateless U, we need an airline reservation. Let's call our favorite carrier (Grace L. Ferguson Airline & Storm Door Company) to make a reservation. We provide some information including departure and destination cities, dates, and times. A reservation agent, acting as our interface to the airline's reservation system, uses that information to make a reservation. At that point, the Reservation is in the Made state. In addition, the system creates and starts a timer. Each reservation has certain rules about when the reservation must be paid for. These rules are based on destination, class of service, dates, etc. If this timer expires before the reservation is paid for, the reservation is cancelled by the system. In state-transition notation this information is recorded as:

Figure 7-1: The Reservation is Made.

The circle represents one state of the Reservation—in this case the Made state. The arrow shows the transition into the Made state. The description on the arrow, giveInfo, is an event that comes into the system from the outside world. The command after the "/" denotes an action of the system; in this case startPayTimer. The black dot indicates the starting point of the diagram.

Sometime after the Reservation is made, but (hopefully) before the PayTimer expires, the Reservation is paid for. This is represented by the arrow labeled PayMoney. When the Reservation is paid it transitions from the Made state to the Paid state.

Figure 7-2: The Reservation transitions to the Paid state.

Before we proceed let's define the terms more formally:

• State (represented by a circle)—A state is a condition in which a system is waiting for one or more events. States "remember" inputs the system has received in the past and define how the system should respond to subsequent events when they occur. These events may cause state-transitions and/or initiate actions. The state is generally represented by the values of one or more variables within a system.
• Transition (represented by an arrow)—A transition represents a change from one state to another caused by an event.
• Event (represented by a label on a transition)—An event is something that causes the system to change state. Generally, it is an event in the outside world that enters the system through its interface. Sometimes it is generated within the system such as Timer expires or Quantity on Hand goes below Reorder Point. Events are considered to be instantaneous. Events can be independent or causally related (event B cannot take place before event A). When an event occurs, the system can change state or remain in the same state and/or execute an action. Events may have parameters associated with them. For example, Pay Money may indicate Cash, Check, Debit Card, or Credit Card.
• Action (represented by a command following a "/")—An action is an operation initiated because of a state change. It could be print a Ticket, display a Screen, turn on a Motor, etc. Often these actions cause something to be created that are outputs of the system. Note that actions occur on transitions between states. The states themselves are passive.
• The entry point on the diagram is shown by a black dot while the exit point is shown by a bulls-eye symbol.

This notation was created by Mealy. An alternate notation has been defined by Moore but is less frequently used. For a much more in-depth discussion of state-transition diagrams see Fowler and Scott's book, UML Distilled: A Brief Guide To The Standard Object Modeling Language. It discusses more complex issues such as partitioned and nested state-transition diagrams.

Note that the state-transition diagram represents one specific entity (in this case a Reservation). It describes the states of a reservation, the events that affect the reservation, the transitions of the reservation from one state to another, and actions that are initiated by the reservation. A common mistake is to mix different entities into one state-transition diagram. An example might be mixing Reservation and Passenger with events and actions corresponding to each.

From the Paid state the Reservation transitions to the Ticketed state when the print command (an event) is issued. Note that in addition to entering the Ticketed state, a Ticket is output by the system.

Figure 7-3: The Reservation transitions to the Ticketed state.

From the Ticketed state we giveTicket to the gate agent to board the plane.

Figure 7-4: The Reservation transitions to the Used state.

After some other action or period of time, not indicated on this diagram, the state-transition path ends at the bulls-eye symbol.

Figure 7-5: The path ends.

Does this diagram show all the possible states, events, and transitions in the life of a Reservation? No. If the Reservation is not paid for in the time allotted (the PayTimer expires), it is cancelled for non-payment.

Figure 7-6: The PayTimer expires and the Reservation is cancelled for nonpayment.

Finished yet? No. Customers sometimes cancel their reservations. From the Made state the customer (through the reservation agent) asks to cancel the Reservation. A new state, Cancelled By Customer, is required.

Figure 7-7: Cancel the Reservation from the Made state.

In addition, a Reservation can be cancelled from the Paid state. In this case a Refund should be generated and leave the system. The resulting state again is Cancelled By Customer.

Figure 7-8: Cancellation from the Paid state.

One final addition. From the Ticketed state the customer can cancel the Reservation. In that case a Refund should be generated and the next state should be Cancelled by Customer. But this is not sufficient. The airline will generate a refund but only when it receives the printed Ticket from the customer. This introduces one new notational element—square brackets [] that contain a conditional that can be evaluated either True or False. This conditional acts as a guard allowing the transition only if the condition is true.

Figure 7-9: Cancellation from the Ticketed state.

Note that the diagram is still incomplete. No arrows and bulls-eyes emerge from the Cancelled states. Perhaps we could reinstate a reservation from the Cancelled NonPay state. We could continue expanding the diagram to include seat selection, flight cancellation, and other significant events affecting the reservation but this is sufficient to illustrate the technique.

As described, state-transition diagrams express complex system rules and interactions in a very compact notation. Hopefully, when this complexity exists, analysts and designers will have created state-transition diagrams to document system requirements and to guide their design.

State Transition Tables

A state-transition diagram is not the only way to document system behavior. The diagrams may be easier to comprehend, but state-transition tables may be easier to use in a complete and systematic manner. State-transition tables consist of four columns—Current State, Event, Action, and Next State.

Table 7-1: State-Transition table for Reservation.

Current State	Event	Action	Next State
null	giveInfo	startPayTimer	Made
null	payMoney	--	null
null	print	--	null
null	giveTicket	--	null
null	cancel	--	null
null	PayTimerExpires	--	null
Made	giveInfo	--	Made
Made	payMoney	--	Paid
Made	print	--	Made
Made	giveTicket	--	Made
Made	cancel	--	Can-Cust
Made	PayTimerExpires	--	Can-NonPay
Paid	giveInfo	--	Paid
Paid	payMoney	--	Paid
Paid	print	Ticket	Ticketed
Paid	giveTicket	--	Paid
Paid	cancel	Refund	Can-Cust
Paid	PayTimerExpires	--	Paid
Ticketed	giveInfo	--	Ticketed
Ticketed	payMoney	--	Ticketed
Ticketed	print	--	Ticketed
Ticketed	giveTicket	--	Used
Ticketed	cancel	Refund	Can-Cust
Ticketed	PayTimerExpires	--	Ticketed
Used	giveInfo	--	Used
Used	payMoney	--	Used
Used	print	--	Used
Used	giveTicket	--	Used
Used	cancel	--	Used
Used	PayTimerExpires	--	Used
Can-NonPay	giveInfo	--	Can-NonPay
Can-NonPay	payMoney	--	Can-NonPay
Can-NonPay	print	--	Can-NonPay
Can-NonPay	giveTicket	--	Can-NonPay
Can-NonPay	cancel	--	Can-NonPay
Can-NonPay	PayTimerExpires	--	Can-NonPay
Can-Cust	givelnfo	--	Can-Cust
Can-Cust	payMoney	--	Can-Cust
Can-Cust	print	--	Can-Cust
Can-Cust	giveTicket	--	Can-Cust
Can-Cust	cancel	--	Can-Cust
Can-Cust	PayTimerExpires	--	Can-Cust

The advantage of a state-transition table is that it lists all possible state-transition combinations, not just the valid ones. When testing critical, high-risk systems such as avionics or medical devices, testing every state-transition pair may be required, including those that are not valid. In addition, creating a state-transition table often unearths combinations that were not identified, documented, or dealt with in the requirements. It is highly beneficial to discover these defects before coding begins.

Key Point

The advantage of a state-transition table is that it lists all possible state-transition combinations, not just the valid ones.

Using a state-transition table can help detect defects in implementation that enable invalid paths from one state to another. The disadvantage of such tables is that they become very large very quickly as the number of states and events increases. In addition, the tables are generally sparse; that is, most of the cells are empty.

Creating Test Cases

Information in the state-transition diagrams can easily be used to create test cases. Four different levels of coverage can be defined:

1. Create a set of test cases such that all states are "visited" at least once under test. The set of three test cases shown below meets this requirement. Generally this is a weak level of test coverage.

   
   Figure 7-10: A set of test cases that "visit" each state.

2. Create a set of test cases such that all events are triggered at least once under test. Note that the test cases that cover each event can be the same as those that cover each state. Again, this is a weak level of coverage.

   
   Figure 7-11: A set of test cases that trigger all events at least once.

3. Create a set of test cases such that all paths are executed at least once under test. While this level is the most preferred because of its level of coverage, it may not be feasible. If the state-transition diagram has loops, then the number of possible paths may be infinite. For example, given a system with two states, A and B, where A transitions to B and B transitions to A. A few of the possible paths are:

   A→B

   A→B→A

   A→B→A→B→A→B

   A→B→A→B→A→B→A

   A→B→A→B→A→B→A→B→A→B

   ...

   and so on forever. Testing of loops such as this can be important if they may result in accumulating computational errors or resource loss (locks without corresponding releases, memory leaks, etc.).

   Key Point

   Testing every transition is usually the recommended level of coverage for a state-transition diagram.

4. Create a set of test cases such that all transitions are exercised at least once under test. This level of testing provides a good level of coverage without generating large numbers of tests. This level is generally the one recommended.

   
   Figure 7-12: A set of test cases that trigger all transitions at least once.

Test cases can also be read directly from the state-transition table. The gray rows in the following table show all the valid transitions.

Table 7-2: Testing all valid transitions from a State-transition table.

Current State	Event	Action	Next State
null	giveInfo	startPayTimer	Made
null	payMoney	--	null
null	print	--	null
null	giveTicket	--	null
null	cancel	--	null
null	PayTimerExpires	--	null
Made	giveInfo	--	Made
Made	payMoney	--	Paid
Made	print	--	Made
Made	giveTicket	--	Made
Made	cancel	--	Can-Cust
Made	PayTimerExpires	--	Can-NonPay
Paid	giveInfo	--	Paid
Paid	payMoney	--	Paid
Paid	print	Ticket	Ticketed
Paid	giveTicket	--	Paid
Paid	cancel	Refund	Can-Cust
Paid	PayTimerExpires	--	Paid
Ticketed	giveInfo	--	Ticketed
Ticketed	payMoney	--	Ticketed
Ticketed	print	--	Ticketed
Ticketed	giveTicket	--	Used
Ticketed	cancel	Refund	Can-Cust
Ticketed	PayTimerExpires	--	Ticketed
Used	giveInfo	--	Used
Used	payMoney	--	Used
Used	print	--	Used
Used	giveTicket	--	Used
Used	cancel	--	Used
Used	PayTimerExpires	--	Used
Can-NonPay	giveInfo	--	Can-NonPay
Can-NonPay	payMoney	--	Can-NonPay
Can-NonPay	print	--	Can-NonPay
Can-NonPay	giveTicket	--	Can-NonPay
Can-NonPay	cancel	--	Can-NonPay
Can-NonPay	PayTimerExpires	--	Can-NonPay
Can-Cust	givelnfo	--	Can-Cust
Can-Cust	payMoney	--	Can-Cust
Can-Cust	print	--	Can-Cust
Can-Cust	giveTicket	--	Can-Cust
Can-Cust	cancel	--	Can-Cust
Can-Cust	PayTimerExpires	--	Can-Cust

In addition, depending on the system risk, you may want to create test cases for some or all of the invalid state/event pairs to make sure the system has not implemented invalid paths.

Applicability and Limitations

State-Transition diagrams are excellent tools to capture certain system requirements, namely those that describe states and their associated transitions. These diagrams then can be used to direct our testing efforts by identifying the states, events, and transitions that should be tested.

State-Transition diagrams are not applicable when the system has no state or does not need to respond to real-time events from outside of the system. An example is a payroll program that reads an employee's time record, computes pay, subtracts deductions, saves the record, prints a paycheck, and repeats the process.

Summary

• State-Transition diagrams direct our testing efforts by identifying the states, events, actions, and transitions that should be tested. Together, these define how a system interacts with the outside world, the events it processes, and the valid and invalid order of these events.
• A state-transition diagram is not the only way to document system behavior. They may be easier to comprehend, but state-transition tables may be easier to use in a complete and systematic manner.
• The generally recommended level of testing using state-transition diagrams is to create a set of test cases such that all transitions are exercised at least once under test. In high-risk systems, you may want to create even more test cases, approaching all paths if possible.

Practice

1. This exercise refers to the Stateless University Registration System Web site described in Appendix B. Below is a state-transition diagram for the "enroll in a course" and "drop a course" process. Determine a set of test cases that you feel adequately cover the enroll and drop process.

   The following terms are used in the diagram:

   Events

   • create - Create a new course.
   • enroll - Add a student to the course.
   • drop - Drop a student from the course.

   Attributes

   • ID - The student identification number.
   • max - The maximum number of students a course can hold.
   • #enrolled - The number of students currently enrolled in the course.
   • #waiting - The number of students currently on the Wait List for this course.

   Tests

   • isEnrolled - Answers "is the student enrolled (on the Section List)?"
   • onWaitList - Answers "is the student on the WaitList?"

   Lists

   • SectionList - A list of students enrolled in the class.
   • WaitList - A list of students waiting to be enrolled in a full class.

   Symbols

   • ++ Increment by 1.
   • -- Decrement by 1.

Figure 7-13: State-transition diagram for enroll and drop a course at Stateless U.

References

Binder, Robert V. (1999). Testing Object-Oriented Systems: Models, Patterns, and Tools. Addison-Wesley.

Fowler, Martin and Kendall Scott (1999). UML Distilled: A Brief Guide to the Standard Object Modeling Language (2nd Edition). Addison-Wesley.

Harel, David. "Statecharts: a visual formalism for complex systems." Science of Computer Programming 8, 1987, pp 231–274.

Mealy, G.H. "A method for synthesizing sequential circuits." Bell System Technical Journal, 34(5): 1045–1079, 1955.

Moore, E.F. "Gedanken-experiments on sequential machines," Automata Studies (C. E. Shannon and J. McCarthy, eds.), pp. 129–153, Princeton, New Jersey: Princeton University Press, 1956.

Rumbaugh, James, et al. (1991). Object-Oriented Modeling and Design. Prentice-Hall.