Constructing Test Cases

Let us investigate how to identify and construct test cases for a class. First, we will look at how to identify test cases from a class specification expressed in OCL. Then we will look at test case construction from a state transition diagram.

Test cases are usually identified from the class specification, which can be expressed in a variety of ways. These include OCL, natural language, and/or state transition diagrams. Test cases can be identified from a class implementation, but using only that approach will propagate errors the class developer has made in interpreting the specification during implementation to the test software. We prefer to develop test cases initially from the specification and then augment them with additional cases as needed to test boundaries introduced by the implementation. If a specification does not exist for a class to be tested, then we "reverse engineer" one and have it reviewed by the developers before we start testing.

Most of the examples in this chapter will be based on testing the Velocity and PuckSupply classes from Brickles. A puck supply is a collection of pucks that have not yet been put into play. A velocity represents the movement of a movable sprite on a playfield based on attributes of a speed (expressed in playfield units per unit time) and a direction (expressed as an angle in degrees, with 0 designating east or right, 90 designating north or up, and so on) (see Figure 5.1). The speed attribute is broken into two components: speed_x speed in the x direction (left-right) and speed_y speed in the y direction (up-down). While the speed attribute is always a non-negative value, the components of a velocity's speed can be negative. The value of speed_x is negative if a velocity's direction is heading left. The value of speed_y is negative if the direction is down. Speed and Direction are abstract types ultimately defined as integer values.

Figure 5.1. A velocity is a vector characterized by a speed and a direction Q

A class model for Velocity is shown in Figure 5.2. Its OCL specification is shown in Figure 5.3. The invariant for the class constrains the value for direction and speed as well as the relationships between the values of those attributes, including the speed_x, and speed_y components. Because these attributes are integer-valued, the invariant relaxes the ideal relationship described by the Pythagorean theorem.

Figure 5.2. The Velocity class as specified in the UML model

Figure 5.3. OCL specification for the Velocity class

The design of Velocity includes the setSpeed() and setDirection() modifiers to improve runtime efficiency by eliminating the need to create a new instance every time one or both attribute values change.

Test Case Construction from Pre- and Postconditions

The general idea for identifying test cases from preconditions and postconditions for an operation is to identify requirements for test cases for all possible combinations of situations in which a precondition can hold and postconditions can be achieved. Then create test cases to address these requirements. From the requirements, create test cases with specific input values, including typical values and boundary values, and determine the correct outputs. Finally, add test cases to address what happens when a precondition is violated (see sidebar).

To identify general test case requirements from pre- and postconditions, we can analyze each of the logical connectives in an OCL condition and list the test cases that result from the structure of that condition. Figure 5.4 and Figure 5.5 list the requirements for test cases that result from various forms of logical expressions in preconditions and postconditions, respectively. Figure 5.4 identifies additional test cases that result from an implicit use of defensive programming. Notice the significant increase in the number of test case requirements over the contract approach.

Figure 5.4. Contribution to the test suite by preconditions

Figure 5.5. Contribution to the test suite by postconditions

Use these two figures to find requirements for the minimum number of test cases^[3] needed to test an operation specified using all combinations of preconditions and postconditions. Follow these steps:

^[3] Minimum because they typically do not account for cases in equivalence classes of values.

1. Identify a list of precondition contributions specified in the entry in Figure 5.4 that matches the form of the precondition.

2. Identify a list of postcondition contributions specified in the entry in Figure 5.5 that matches the form of the postcondition.

3. Form test case requirements by making all possible combinations of entries from the contributions lists. One way is to substitute each input constraint from the first list for each occurrence of Pre in the second list.

4. Eliminate any conditions generated by the table that are not meaningful. For example, a precondition of, say, (color = red) or (color = blue) will generate a test case in which (color = red) and (color = blue), which cannot satisfied.^[4]

   ^[4] It could be argued that a more accurate precondition is (color = red) xor (color = blue), which states that one or the other, but not both, must be true. In this case, a tester might suggest such a change to the developers to improve the specification.

Test Cases for Failed Preconditions

Our discussion of class specification in Chapter 2 described defensive programming and contracts. Under defensive programming, a class implementation includes code in each method to verify the associated precondition holds. Under the contract approach, no such code is included because any client requesting an operation is assumed to have ensured that the precondition holds for that request.

In many cases, the defensive programming approach is implicit in a specification that is, the class specification is written using the same preconditions, postconditions, and invariants as would be used for a contract approach. There is an understanding that each violated precondition results in some standard action, such as abnormally terminating program execution, throwing a standard exception, or displaying a message in an error log.

Testers must be aware of any implicit handling of violated conditions. If implicit handling is part of a class specification, testers should generate test cases to verify the correct processing of that implicit part of the specifications. In testing Velocity::setDirection(), for example, we would need to add additional test cases for the operation to cover the possibilities that a direction is negative or greater than 359. If the designers take a contract programming perspective on a class, the implementers still might include code for debugging purposes to perform runtime checking of preconditions and/or postconditions. If test cases are needed to check this debugging code, take care to identify such test cases in the test driver so that they can be disabled when the debugging code is disabled.

If a precondition or a postcondition has a more complex form than is shown in the table for example, involving three disjuncts then the processes described in Steps 1 and 2 will have to be applied recursively that is, broken into smaller pieces with the rules applied to the pieces, and then applied together as the pieces are recombined with operators. Fortunately, widely accepted object-oriented design principles keep most preconditions and postconditions simple.

Figure 5.6 and Figure 5.7 show examples of how to use these tables for two of the operations in the Velocity class.

Figure 5.6. Identifying test cases for Velocity::setDirection()

Figure 5.7. Identifying test cases for Velocity::reverseX()

Test Case Construction from State Transition Diagrams

State transition diagrams show the behavior associated with instances of a class graphically. These diagrams can supplement written specifications or comprise the entire specification. A state transition diagram for the PuckSupply class is given in Figure 5.8. A puck supply holds the pucks that have not yet been put into play during a Brickles match. OCL for the class is also shown in the figure so you can compare the forms of specification.

Figure 5.8. The PuckSupply class's state transition diagram and OCL specification

Describing Test Cases

While it is easy to define a test case as a pair (input, output), it is not so easy to describe in a succinct way what input and output are for a specific test case. An input involves an object under test (OUT) in a given state with values specified for all attributes; for zero or more objects in specified states that are in associations with the OUT (perhaps helping to define that object's state); for a sequence of one or more messages (or other events) to be sent to the OUT; and for zero or more objects (and values) that serve as parameters to messages. An output involves the resulting state of the OUT, the resulting state of any objects in association with the OUT, a result returned from the last message sent as input, and the resulting state of any objects passed as parameters to messages. Note that the class of an OUT can be one of the objects associated with it.

We use a text-based notation for describing test cases. We use a table having a column for inputs and one for outputs. Each column is subdivided as shown. The text in each column except for Events is an adaptation of OCL. The Events column uses programming language notation. Events include messages and object creation.

Input		Output
State	Events	State	Exceptions Thrown
none	OUT = new Velocity;	OUT.speed = 0 and OUT.direction = 0 and OUT.speedX = 0 and OUT.speedY = 0	none
OUT:Velocity [speed=100, direction=90]	OUT.setDirection(45)	OUT.speed=1000, OUT.direction=45, OUT.speedX=707, OUT.speedY=707	none

The first test case listed is for the default constructor. The second is for setDirection(). By convention, we use the name OUT to refer to the object under test. The notation OUT:Velocity[speed=100, direction=90] denotes that OUT is an instance of Velocity with attribute values as specified in the brackets. If attribute values are unspecified, then they are irrelevant for the test case.

We can generate code for a test case in a straightforward way. For each test case, write code to achieve the input state, then write code to generate the events, and then write code to check the result.

We can use the same general approach to generating test cases that we described for using pre- and postconditions. Each transition on the diagram represents a requirement for one or more test cases. The diagram in Figure 5.8 has six transitions between states, one transition representing construction, and two representing destruction nine transitions total.^[5] Thus, we have nine requirements for test cases. We satisfy these requirements by selecting representative values and boundary values on each side of a transition. If a transition is guarded, then you should select boundary values for the guard condition, too.

^[5] A transition on the superstate PuckSupply distributes to each of the two substates, yielding two transitions.

Boundary values for states are determined based on the range of attribute values associated with a state. Each state is defined in terms of attribute values. In PuckSupply, the Empty state is associated with a size attribute value of zero. The Not Empty state is associated with a nonzero size attribute value. We want to be sure to include a test case to check that a PuckSupply instance does not behave as though it is empty when its size is one.

For most of us, generating test cases from state transition diagrams is more intuitive than generating them from pre- and postconditions. The behavior associated with a class is more evident from the diagrams, and it is easy to identify the requirements for test cases since they come directly from the transitions. However, we must be careful to understand completely the way states are defined in terms of attribute values, and how events affect specific values within a given state. Consider, for example, the Not Empty state in PuckSupply. From the diagram alone, we are left to guess that each time a puck is removed, the size decreases by one. This is explicit in the OCL specification. At the extreme, consider Velocity, which has only one state and twelve transitions. It is difficult to identify all test cases from that simple diagram alone. When testing based on state transition diagrams, make sure you investigate the boundaries and results of each transition as you generate test cases.

Adequacy of Test Suites for a Class

Ideally, we could exhaustively test every class, that is, test with all possible values to ensure each class meets its specification. In practice, exhaustive testing is either impossible or requires considerable effort. Nonetheless, it is wise to exhaustively test certain classes. Consider, for example, the Velocity class in Brickles. If it does not operate correctly, the system has no chance of operating correctly. The benefits of exhaustive testing in this case outweigh the cost of writing a test driver to run more test cases.

Exhaustive testing is usually infeasible or impractical under time and resource constraints, so we need to test a class enough. Without exhaustive testing, we cannot be sure every aspect of a class meets its specification, but we can apply some measure of adequacy to give us a high level of confidence in the quality of the test suite. Three commonly used measures of adequacy are state-based coverage, constraint-based coverage, and code-based coverage. Meeting these measures minimally will result in different test suites. Using all three measures for a test suite will improve the level of confidence in testing adequately.

State-Based Coverage

State-based coverage is based on how many of the transitions in a state transition diagram are covered by the test suite. If one or more transitions is not covered, then the class has not been tested adequately and more test cases should be generated to cover those transitions. If test cases are generated from a state transition diagram as we described, then the test cases achieve this measure. If test cases were generated from pre- and postconditions, then analyzing the test cases in terms of which transitions they cover is quite useful for finding missed test cases.

Boundary Conditions

In testing a component, it is often the case that a small change in input value results in a significant change in the response of the software. The input value at which a large change occurs is referred to as a boundary. Boundaries must be identified when test cases are identified. Test cases must be generated to check input values close to each boundary. The response of the system to inputs occurring between two adjacent boundaries is generally equivalent. A relatively small number of test case inputs can be taken from that set for adequate testing, but a test case must be generated for each side of and (possibly) for each boundary.

Some boundaries are easy to identify from a state transition diagram from the guards placed on state transitions a test case for the true condition and one for the false condition. Other boundaries are not so obvious from a state transition diagram because they do not effect a state change, but do affect a response. Consider, for example, a method to compute a Julian date. Clearly, the value associated with March 1 depends on whether the year is a leap year.

Some boundaries can only be identified from code itself because they are derived from an algorithm used to implement a specification and not from the specification itself. A standard example is a function to sort an array of integer values in nondecreasing (ascending) order. With respect to the size of an array to be sorted, boundary conditions are as follows:

• an array containing no elements

• an array containing exactly one element

• an array containing exactly two elements the smallest array that can actually be sorted

• an array of a large number of elements

With respect to the ordering of elements in an array to be sorted, they can be arranged as follows:

• in a random order

• as the same value

• in a sorted order

• in reverse of their sorted order

Finally, we can consider the aspect of the actual values in an array to be sorted, which can be unique, the same, or partly unique and partly the same.

The values can range from the smallest boundary value to the largest. These three aspects generate a fairly large number of test cases.

Even if all transitions are covered once, adequate testing is doubtful because states usually embrace a range of values for various object attributes. We need to test values over those ranges. Testing is needed for typical values and boundary values.

We must also be concerned about how operations interact with respect to transitions. If there are two transitions T₁ and T₂ into a state and one transition T₃ out of a state, then the test cases for T₃ might pass when the input state is set up using T₁, but not when T₂ is used. We can address this problem using a measure of adequacy based on coverage of all pairs of transitions in the state transition diagram. In our example, we would test the combinations of T₁-T₃ and T₂-T₃.

Constraint-Based Coverage

Parallel to adequacy based on state transitions, we can express adequacy in terms of how many pairs of pre- and postconditions have been covered. If for example, the preconditions for an operation are pre₁ or pre₂ and the postconditions are post₁ or post₂, then we make sure the test suite contains cases for all the valid combinations pre₁=true, pre₂=false, post₁=true, post₂=false; pre₁=false, pre₂=true, post₁=true, post₂=false, and so on.

Recall the steps we described earlier for finding test case requirements when generating test cases from pre- and postconditions. If one test case is generated to satisfy each requirement, then the test suite meets this measure of adequacy.

In a way similar to what we described for using pair-wise sequences of transitions in state-based coverage, we can use sequences of operations based on analysis of preconditions and postconditions. For each operation op that is not an accessor, identify the operators op₁, op₂, and so on, for which the preconditions are met when the postconditions for op hold. Then execute the test cases for op-op₁, op-op2, and so on.

Code-Based Coverage

A third measure of adequacy can be based on how much of the code that implements the class is executed across all test cases in the suite. It is a good idea to determine that every line of (or path through) the code implementing a class was executed at least once when all test cases have completed execution. Tools for making such measurements are available commercially. If certain lines of code (or paths) have not been reached, then the test suite needs to be expanded with test cases that do reach those lines (paths) or the code needs to be corrected to remove unreachable lines.

Even with full code coverage, the test suite for a class might not be adequate because it might not exercise interactions between methods as we described in state-based and constraint-based coverage. Use of one of those other metrics to determine adequacy is important. However, measuring in terms of code coverage is also important (see sidebar). One implementation-level technique for determining the adequacy of a test suite is measuring code coverage for sequences of operations. If all statements (paths) are not executed, generate more test cases to reach them.

A Need for Implementation-Based Testing

In testing a function to sort an array (see Boundary Conditions on page 180), we might want to use a sampling of test cases in order to reduce the testing effort. (Pair-wise sampling is discussed in the next chapter.) The following test case inputs provide a good cross section of the possibilities:

• an array of zero elements

• an array of exactly one element

• an array containing exactly two elements that are out of order

• an array of 100 elements that contain 100 different values, some negative and some positive, arranged in a random order

• an array of 101 elements that all contain the same value

• an array of 50 elements that contain values that are already sorted

• an array of 72 elements that contain values that are in exactly the reverse of their sorted order

The choices of sizes 101, 100, 50, and 72 are arbitrary. An array of any reasonable size would seem to suffice. We decided to use different sizes just to get a better sampling. Some inputs are ordered randomly, already ordered, and reverse ordered. These cases seem to cover the specification reasonably well. If the function can pass these test cases, then we can be reasonably confident that it can sort any array. Of course, exhaustive testing would make us more confident.

However, we cannot ever be fully confident a component meets its specification based purely on test cases derived from a specification. Consider a scenario in which this sort function has been implemented so that all arrays of a size under 1024 are sorted using a bubble-sort algorithm, and all larger arrays are sorted using a quicksort algorithm. Then, by using these test cases, the code for this function would not be tested adequately. A size of 1024 comprises a boundary imposed by the implementation that is not identifiable from the specification. Thus, more test cases that use arrays containing 1024 and more elements are needed.