Chapter 4

Test-Case Design

Moving beyond the psychological issues discussed in Chapter 2, the most important consideration in program testing is the design and creation of effective test cases.

Testing, however creative and seemingly complete, cannot guarantee the absence of all errors. Test-case design is so important because complete testing is impossible. Put another way, a test of any program must be necessarily incomplete. The obvious strategy, then, is to try to make tests as complete as possible.

Given constraints on time and cost, the key issue of testing becomes:

What subset of all possible test cases has the highest probability of detecting the most errors?

The study of test-case design methodologies supplies answers to this question.

In general, the least effective methodology of all is random-input testing—the process of testing a program by selecting, at random, some subset of all possible input values. In terms of the likelihood of detecting the most errors, a randomly selected collection of test cases has little chance of being an optimal, or even close to optimal, subset. Therefore, in this chapter, we want to develop a set of thought processes that enable you to select test data more intelligently.

Chapter 2 showed that exhaustive black-box and white-box testing are, in general, impossible; at the same time, it suggested that a reasonable testing strategy might feature elements of both. This is the strategy developed in this chapter. You can develop a reasonably rigorous test by using certain black-box–oriented test-case design methodologies and then supplementing these test cases by examining the logic of the program, using white-box methods.

The methodologies discussed in this chapter are:

Although we will discuss these methods separately, we recommend that you use a combination of most, if not all, of them to design a rigorous test of a program, since each method has distinct strengths and weaknesses. One method may find errors another method overlooks, for example.

Nobody ever promised that software testing would be easy. To quote an old sage, “If you thought designing and coding that program was hard, you ain't seen nothing yet.”

The recommended procedure is to develop test cases using the black-box methods and then develop supplementary test cases, as necessary, with white-box methods. We'll discuss the more widely known white-box methods first.

White-Box Testing

White-box testing is concerned with the degree to which test cases exercise or cover the logic (source code) of the program. As we saw in Chapter 2, the ultimate white-box test is the execution of every path in the program; but complete path testing is not a realistic goal for a program with loops.

Logic Coverage Testing

If you back completely away from path testing, it may seem that a worthy goal would be to execute every statement in the program at least once. Unfortunately, this is a weak criterion for a reasonable white-box test. This concept is illustrated in Figure 4.1. Assume that this figure represents a small program to be tested. The equivalent Java code snippet follows:

Figure 4.1 A Small Program to Be Tested.

public void foo(int A,int B,int X) {

if(A>1 && B==0) {

X=X/A;

}

if(A==2 || X>1) {

X=X+1;

}

}

You could execute every statement by writing a single test case that traverses path ace. That is, by setting A=2, B=0, and X=3 at point a, every statement would be executed once (actually, X could be assigned any integer value >1).

Unfortunately, this criterion is a rather poor one. For instance, perhaps the first decision should be an or rather than an and. If so, this error would go undetected. Perhaps the second decision should have stated X>0; this error would not be detected. Also, there is a path through the program in which X goes unchanged (the path abd). If this were an error, it would go undetected. In other words, the statement coverage criterion is so weak that it generally is useless.

A stronger logic coverage criterion is known as decision coverage or branch coverage. This criterion states that you must write enough test cases that each decision has a true and a false outcome at least once. In other words, each branch direction must be traversed at least once. Examples of branch or decision statements are switch-case, do-while, and if-else statements. Multipath GOTO statements qualify in some programming languages such as Fortran.

Decision coverage usually can satisfy statement coverage. Since every statement is on some subpath emanating either from a branch statement or from the entry point of the program, every statement must be executed if every branch direction is executed. There are, however, at least three exceptions:

• Programs with no decisions.
• Programs or subroutines/methods with multiple entry points. A given statement might be executed only if the program is entered at a particular entry point.
• Statements within ON-units. Traversing every branch direction will not necessarily cause all ON-units to be executed.

Since we have deemed statement coverage to be a necessary condition, decision coverage, a seemingly better criterion, should be defined to include statement coverage. Hence, decision coverage requires that each decision have a true and a false outcome, and that each statement be executed at least once. An alternative and easier way of expressing it is that each decision has a true and a false outcome, and that each point of entry (including ON-units) be invoked at least once.

This discussion considers only two-way decisions or branches and has to be modified for programs that contain multipath decisions. Examples are Java programs containing switch-case statements, Fortran programs containing arithmetic (three-way) IF statements or computed or arithmetic GOTO statements, and COBOL programs containing altered GOTO statements or GO-TO-DEPENDING-ON statements. For such programs, the criterion is exercising each possible outcome of all decisions at least once and invoking each point of entry to the program or subroutine at least once.

In Figure 4.1, decision coverage can be met by two test cases covering paths ace and abd or, alternatively, acd and abe. If we choose the latter alternative, the two test-case inputs are A=3, B=0, X=3 and A=2, B=1, and X=1.

Decision coverage is a stronger criterion than statement coverage, but it still is rather weak. For instance, there is only a 50 percent chance that we would explore the path where x is not changed (i.e., only if we chose the former alternative). If the second decision were in error (if it should have said X<1 instead of X>1), the mistake would not be detected by the two test cases in the previous example.

A criterion that is sometimes stronger than decision coverage is condition coverage. In this case, you write enough test cases to ensure that each condition in a decision takes on all possible outcomes at least once. But, as with decision coverage, this does not always lead to the execution of each statement, so an addition to the criterion is that each point of entry to the program or subroutine, as well as ON-units, be invoked at least once. For instance, the branching statement:

DO K=0 to 50 WHILE (J+K<QUEST)

contains two conditions: Is K less than or equal to 50, and is J+K less than QUEST? Hence, test cases would be required for the situations K<=50, K>50 (to reach the last iteration of the loop), J+K<QUEST, and J+K>=QUEST.

Figure 4.1 has four conditions: A>1, B=0, A=2, and X>1. Hence, enough test cases are needed to force the situations where A>1, A<=1, B=0, and B<>0 are present at point a and where A=2, A<>2, X>1, and X<=1 are present at point b. A sufficient number of test cases satisfying the criterion, and the paths traversed by each, are:

A=2, B=0, X=4 ace

A=1, B=1, X=1adb

Note that although the same number of test cases was generated for this example, condition coverage usually is superior to decision coverage in that it may (but does not always) cause every individual condition in a decision to be executed with both outcomes, whereas decision coverage does not. For instance, in the same branching statement

DO K=0 to 50 WHILE (J+K<QUEST)

is a two-way branch (execute the loop body or skip it). If you are using decision testing, the criterion can be satisfied by letting the loop run from K=0 to 51, without ever exploring the circumstance where the WHILE clause becomes false. With the condition criterion, however, a test case would be needed to generate a false outcome for the conditions J+K<QUEST.

Although the condition coverage criterion appears, at first glance, to satisfy the decision coverage criterion, it does not always do so. If the decision IF(A & B) is being tested, the condition coverage criterion would let you write two test cases—A is true, B is false, and A is false, B is true—but this would not cause the THEN clause of the IF to execute. The condition coverage tests for the earlier example covered all decision outcomes, but this was only by chance. For instance, two alternative test cases

A=1, B=0, X=3 A=2, B=1, X=1

cover all condition outcomes but only two of the four decision outcomes (both of them cover path abe and, hence, do not exercise the true outcome of the first decision and the false outcome of the second decision).

The obvious way out of this dilemma is a criterion called decision/ condition coverage. It requires sufficient test cases such that each condition in a decision takes on all possible outcomes at least once, each decision takes on all possible outcomes at least once, and each point of entry is invoked at least once.

A weakness with decision/condition coverage is that although it may appear to exercise all outcomes of all conditions, it frequently does not, because certain conditions mask other conditions. To see this, examine Figure 4.2. The flowchart in this figure is the way a compiler would generate machine code for the program in Figure 4.1. The multicondition decisions in the source program have been broken into individual decisions and branches because most machines do not have a single instruction that makes multicondition decisions. A more thorough test coverage, then, appears to be the exercising of all possible outcomes of each primitive decision. The two previous decision coverage test cases do not accomplish this; they fail to exercise the false outcome of decision H and the true outcome of decision K.

Figure 4.2 Machine Code for the Program in Figure 4.1.

The reason, as shown in Figure 4.2, is that results of conditions in the and and the or expressions can mask or block the evaluation of other conditions. For instance, if an and condition is false, none of the subsequent conditions in the expression need be evaluated. Likewise, if an or condition is true, none of the subsequent conditions need be evaluated. Hence, errors in logical expressions are not necessarily revealed by the condition coverage and decision/condition coverage criteria.

A criterion that covers this problem, and then some, is multiple-condition coverage. This criterion requires that you write sufficient test cases such that all possible combinations of condition outcomes in each decision, and all points of entry, are invoked at least once. For instance, consider the following sequence of pseudo-code.

NOTFOUND=TRUE;

DO I=1 to TABSIZE WHILE (NOTFOUND); /*SEARCH TABLE*/

. . .searching logic. . .;

END

The four situations to be tested are:

It should be easy to see that a set of test cases satisfying the multiple-condition criterion also satisfies the decision coverage, condition coverage, and decision/condition coverage criteria.

Returning to Figure 4.1, test cases must cover eight combinations:

Note Recall from the Java code snippet presented earlier that test cases 5 through 8 express values at the point of the second if statement. Since X may be altered above this if statement, the values needed at this if statement must be backed up through the logic to find the corresponding input values.

These combinations to be tested do not necessarily imply that eight test cases are needed. In fact, they can be covered by four test cases. The test-case input values, and the combinations they cover, are as follows:

The fact that there are four test cases and four distinct paths in Figure 4.1 is just coincidence. In fact, these four test cases do not cover every path; they miss the path acd. For instance, you would need eight test cases for the following decision:

if(x==y && length(z)==0 && FLAG) {

j=1;

else

i=1;

}

although it contains only two paths. In the case of loops, the number of test cases required by the multiple-condition criterion is normally much less than the number of paths.

In summary, for programs containing only one condition per decision, a minimum test criterion is a sufficient number of test cases to: (1) invoke all outcomes of each decision at least once, and (2) invoke each point of entry (such as entry point or ON-unit) at least once, to ensure that all statements are executed at least once. For programs containing decisions having multiple conditions, the minimum criterion is a sufficient number of test cases to invoke all possible combinations of condition outcomes in each decision, and all points of entry to the program, at least once. (The word “possible” is inserted because some combinations may be found to be impossible to create.)

Black-Box Testing

As we discussed in Chapter 2, black-box (data-driven or input/output driven) testing is based on program specifications. The goal is to find areas wherein the program does not behave according to its specifications.

Equivalence Partitioning

Chapter 2 described a good test case as one that has a reasonable probability of finding an error; it also stated that an exhaustive input test of a program is impossible. Hence, when testing a program, you are limited to a small subset of all possible inputs. Of course, then, you want to select the “right” subset, that is, the subset with the highest probability of finding the most errors.

One way of locating this subset is to realize that a well-selected test case also should have two other properties:

These properties, although they appear to be similar, describe two distinct considerations. The first implies that each test case should invoke as many different input considerations as possible to minimize the total number of test cases necessary. The second implies that you should try to partition the input domain of a program into a finite number of equivalence classes such that you can reasonably assume (but, of course, not be absolutely sure) that a test of a representative value of each class is equivalent to a test of any other value. That is, if one test case in an equivalence class detects an error, all other test cases in the equivalence class would be expected to find the same error. Conversely, if a test case did not detect an error, we would expect that no other test cases in the equivalence class would fall within another equivalence class, since equivalence classes may overlap one another.

These two considerations form a black-box methodology known as equivalence partitioning. The second consideration is used to develop a set of “interesting” conditions to be tested. The first consideration is then used to develop a minimal set of test cases covering these conditions.

An example of an equivalence class in the triangle program of Chapter 1 is the set “three equal-valued numbers having integer values greater than zero.” By identifying this as an equivalence class, we are stating that if no error is found by a test of one element of the set, it is unlikely that an error would be found by a test of another element of the set. In other words, our testing time is best spent elsewhere: in different equivalence classes.

Test-case design by equivalence partitioning proceeds in two steps:

Identifying the Equivalence Classes

The equivalence classes are identified by taking each input condition (usually a sentence or phrase in the specification) and partitioning it into two or more groups. You can use the table in Figure 4.3 to do this. Notice that two types of equivalence classes are identified: valid equivalence classes represent valid inputs to the program, and invalid equivalence classes represent all other possible states of the condition (i.e., erroneous input values). Thus, we are adhering to principle 5, discussed in Chapter 2, which stated you must focus attention on invalid or unexpected conditions.

Figure 4.3 A Form for Enumerating Equivalence Classes.

Given an input or external condition, identifying the equivalence classes is largely a heuristic process. Follow these guidelines:

If there is any reason to believe that the program does not handle elements in an equivalence class identically, split the equivalence class into smaller equivalence classes. We will illustrate an example of this process shortly.

Identifying the Test Cases

The second step is the use of equivalence classes to identify the test cases. The process is as follows:

The reason that individual test cases cover invalid cases is that certain erroneous-input checks mask or supersede other erroneous-input checks. For instance, if the specification states “enter book type (HARDCOVER, SOFTCOVER, or LOOSE) and amount (1–999),” the test case, (XYZ 0), expressing two error conditions (invalid book type and amount) will probably not exercise the check for the amount, since the program may say “XYZ IS UNKNOWN BOOK TYPE” and not bother to examine the remainder of the input.

An Example

As an example, assume that we are developing a compiler for a subset of the Fortran language, and we wish to test the syntax checking of the DIMENSION statement. The specification is listed below. (Note: This is not the full Fortran DIMENSION statement; it has been edited considerably to make it textbook size. Do not be deluded into thinking that the testing of actual programs is as easy as the examples in this book.) In the specification, items in italics indicate syntactic units for which specific entities must be substituted in actual statements; brackets are used to indicate option items; and an ellipsis indicates that the preceding item may appear multiple times in succession.

A DIMENSION statement is used to specify the dimensions of arrays. The form of the DIMENSION statement is

DIMENSION ad[,ad]...

where ad is an array descriptor of the form

n(d[,d]...)

where n is the symbolic name of the array and d is a dimension declarator. Symbolic names can be one to six letters or digits, the first of which must be a letter. The minimum and maximum numbers of dimension declarations that can be specified for an array are one and seven, respectively. The form of a dimension declarator is

[lb: ]ub

where lb and ub are the lower and upper dimension bounds. A bound may be a constant in the range −65534 to 65535 or the name of an integer variable (but not an array element name). If lb is not specified, it is assumed to be 1. The value of ub must be greater than or equal to lb. If lb is specified, its value may be negative, 0, or positive. As for all statements, the DIMENSION statement may be continued over multiple lines.

The first step is to identify the input conditions and, from these, locate the equivalence classes. These are tabulated in Table 4.1. The numbers in the table are unique identifiers of the equivalence classes.

Table 4.1 Equivalence Classes

The next step is to write a test case covering one or more valid equivalence classes. For instance, the test case

DIMENSION A(2)

covers classes 1, 4, 7, 10, 12, 15, 24, 28, 29, and 43.

The next step is to devise one or more test cases covering the remaining valid equivalence classes. One test case of the form

DIMENSION A 12345 (I,9,J4XXXX,65535,1,KLM,

X,1000, BBB(-65534:100,0:1000,10:10, I:65535)

covers the remaining classes. The invalid input equivalence classes, and a test case representing each, are:

(3):DIMENSION

(5):DIMENSION

(10)

(6):DIMENSION A234567(2)

(9):DIMENSION A.1(2)

(11): DIMENSION 1A(10)

(13): DIMENSION B

(14): DIMENSION B(4,4,4,4,4,4,4,4)

(17): DIMENSION B(4,A(2))

(18): DIMENSION B(4,7)

(21): DIMENSION C(I.,10)

(23): DIMENSION C(10,1J)

(25): DIMENSION D(- 65535:1)

(26): DIMENSION D(65536)

(31): DIMENSION D(4:3)

(37): DIMENSION D(A(2):4)

(38): D(.:4)

(43): DIMENSION D(0)

Hence, the equivalence classes have been covered by 17 test cases. You may want to consider how these test cases would compare to a set of test cases derived in an ad hoc manner.

Although equivalence partitioning is vastly superior to a random selection of test cases, it still has deficiencies. It overlooks certain types of high-yield test cases, for example. The next two methodologies, boundary value analysis and cause-effect graphing, cover many of these deficiencies.

Boundary Value Analysis

Experience shows that test cases that explore boundary conditions have a higher payoff than test cases that do not. Boundary conditions are those situations directly on, above, and beneath the edges of input equivalence classes and output equivalence classes. Boundary value analysis differs from equivalence partitioning in two respects:

It is difficult to present a “cookbook” for boundary value analysis, since it requires a degree of creativity and a certain amount of specialization toward the problem at hand. (Hence, like many other aspects of testing, it is more a state of mind than anything else.) However, a few general guidelines are in order:

The triangle analysis program of Chapter 1 can illustrate the need for boundary value analysis. For the input values to represent a triangle, they must be integers greater than 0 where the sum of any two is greater than the third. If you were defining equivalent partitions, you might define one where this condition is met and another where the sum of two of the integers is not greater than the third. Hence, two possible test cases might be 3–4–5 and 1–2–4. However, we have missed a likely error. That is, if an expression in the program were coded as A+B>=C instead of A+B>C, the program would erroneously tell us that 1–2–3 represents a valid scalene triangle. Hence, the important difference between boundary value analysis and equivalence partitioning is that boundary value analysis explores situations on and around the edges of the equivalence partitions.

As an example of a boundary value analysis, consider the following program specification:

MTEST is a program that grades multiple-choice examinations. The input is a data file named OCR, with multiple records that are 80 characters long. Per the file specification, the first record is a title used as a title on each output report. The next set of records describes the correct answers on the exam. These records contain a “2” as the last character in column 80. In the first record of this set, the number of questions is listed in columns 1–3 (a value of 1–999). Columns 10–59 contain the correct answers for questions 1–50 (any character is valid as an answer). Subsequent records contain, in columns 10–59, the correct answers for questions 51–100, 101–150, and so on.

The third set of records describes the answers of each student; each of these records contains a “3” in column 80. For each student, the first record contains the student's name or number in columns 1–9 (any characters); columns 10–59 contain the student's answers for questions 1–50. If the test has more than 50 questions, subsequent records for the student contain answers 51–100, 101–150, and so on, in columns 10–59. The maximum number of students is 200. The input data are illustrated in Figure 4.4. The four output records are:

Figure 4.4 Input to the MTEST Program.

We can begin by methodically reading the specification, looking for input conditions. The first boundary input condition is an empty input file. The second input condition is the title record; boundary conditions are a missing title record and the shortest and longest possible titles. The next input conditions are the presence of correct-answer records and the number-of-questions field on the first answer record. The equivalence class for the number of questions is not 1–999, because something special happens at each multiple of 50 (i.e., multiple records are needed). A reasonable partitioning of this into equivalence classes is 1–50 and 51–999. Hence, we need test cases where the number-of-questions field is set to 0, 1, 50, 51, and 999. This covers most of the boundary conditions for the number of correct-answer records; however, three more interesting situations are the absence of answer records and having one too many and one too few answer records (e.g., the number of questions is 60, but there are three answer records in one case and one answer record in the other case). The unique test cases identified so far are:

The next input conditions are related to the students' answers. The boundary value test cases here appear to be:

You also can derive a useful set of test cases by examining the output boundaries, although some of the output boundaries (e.g., empty report 1) are covered by the existing test cases. The boundary conditions of reports 1 and 2 are:

The boundary conditions from report 3 (mean, median, and standard deviation) are:

Tests 33 and 34 also cover the boundaries of the median. Another useful test case is the situation where there are 0 students (looking for a division by 0 in computing the mean), but this is identical to test case 14.

An examination of report 4 yields the following boundary value tests:

An experienced programmer would probably agree at this point that many of these 42 test cases represent common errors that might have been made in developing this program, yet most of these errors probably would go undetected if a random or ad hoc test-case generation method were used. Boundary value analysis, if practiced correctly, is one of the most useful test-case design methods. However, it often is used ineffectively because the technique, on the surface, sounds simple. You should understand that boundary conditions may be very subtle and, hence, identification of them requires a lot of thought.

Cause-Effect Graphing

One weakness of boundary value analysis and equivalence partitioning is that they do not explore combinations of input circumstances. For instance, perhaps the MTEST program of the previous section fails when the product of the number of questions and the number of students exceeds some limit (the program runs out of memory, for example). Boundary value testing would not necessarily detect such an error.

The testing of input combinations is not a simple task because even if you equivalence-partition the input conditions, the number of combinations usually is astronomical. If you have no systematic way of selecting a subset of input conditions, you'll probably select an arbitrary subset of conditions, which could lead to an ineffective test.

Cause-effect graphing aids in selecting, in a systematic way, a high-yield set of test cases. It has a beneficial side effect in pointing out incompleteness and ambiguities in the specification.

A cause-effect graph is a formal language into which a natural-language specification is translated. The graph actually is a digital logic circuit (a combinatorial logic network), but instead of standard electronics notation, a somewhat simpler notation is used. No knowledge of electronics is necessary other than an understanding of Boolean logic (i.e., of the logic operators and, or, and not).

The following process is used to derive test cases:

The basic notation for the graph is shown in Figure 4.5. Think of each node as having the value 0 or 1; 0 represents the “absent” state and 1 represents the “present” state.

Figure 4.5 Basic Cause-Effect Graph Symbols.

• The identity function states that if a is 1, b is 1; else b is 0.
• The not function states that if a is 1, b is 0, else b is 1.
• The or function states that if a or b or c is 1, d is 1; else d is 0.
• The and function states that if both a and b are 1, c is 1; else c is 0.

The latter two functions (or and and) are allowed to have any number of inputs.

To illustrate a small graph, consider the following specification:

The causes are:

and the effects are:

The cause-effect graph is shown in Figure 4.6. Notice the intermediate node 11 that was created. You should confirm that the graph represents the specification by setting all possible states of the causes and verifying that the effects are set to the correct values. For readers familiar with logic diagrams, Figure 4.7 is the equivalent logic circuit.

Figure 4.6 Sample Cause-Effect Graph.

Figure 4.7 Logic Diagram Equivalent to Figure 4.6.

Although the graph in Figure 4.6 represents the specification, it does contain an impossible combination of causes—it is impossible for both causes 1 and 2 to be set to 1 simultaneously. In most programs, certain combinations of causes are impossible because of syntactic or environmental considerations (a character cannot be an “A” and a “B” simultaneously). To account for these, the notation in Figure 4.8 is used. The E constraint states that it must always be true that, at most, one of a and b can be 1 (a and b cannot be 1 simultaneously). The I constraint states that at least one of a, b, and c must always be 1 (a, b, and c cannot be 0 simultaneously). The O constraint states that one, and only one, of a and b must be 1. The R constraint states that for a to be 1, b must be 1 (i.e., it is impossible for a to be 1 and b to be 0).

Figure 4.8 Constraint Symbols.

There frequently is a need for a constraint among effects. The M constraint in Figure 4.9 states that if effect a is 1, effect b is forced to 0.

Figure 4.9 Symbol for “Masks” Constraint.

Returning to the preceding simple example, we see that it is physically impossible for causes 1 and 2 to be present simultaneously, but it is possible for neither to be present. Hence, they are linked with the E constraint, as shown in Figure 4.10.

Figure 4.10 Sample Cause-Effect Graph with “Exclusive” Constraint.

To illustrate how cause-effect graphing is used to derive test cases, we use the following specification for a debugging command in an interactive system.

The DISPLAY command is used to view from a terminal window the contents of memory locations. The command syntax is shown in Figure 4.11. Brackets represent alternative optional operands. Capital letters represent operand keywords. Lowercase letters represent operand values (actual values are to be substituted). Underlined operands represent the default values (i.e., the value used when the operand is omitted).

Figure 4.11 Syntax of the DISPLAY Command.

The first operand (hexloc1) specifies the address of the first byte whose contents are to be displayed. The address may be one to six hexadecimal digits (0–9, A–F) in length. If it is not specified, the address 0 is assumed. The address must be within the actual memory range of the machine.

The second operand specifies the amount of memory to be displayed. If hexloc2 is specified, it defines the address of the last byte in the range of locations to be displayed. It may be one to six hexadecimal digits in length. The address must be greater than or equal to the starting address (hexloc1). Also, hexloc2 must be within the actual memory range of the machine. If END is specified, memory is displayed up through the last actual byte in the machine. If bytecount is specified, it defines the number of bytes of memory to be displayed (starting with the location specified in hexloc1). The operand bytecount is a hexadecimal integer (one to six digits). The sum of bytecount and hexloc1 must not exceed the actual memory size plus 1, and bytecount must have a value of at least 1.

When memory contents are displayed, the output format on the screen is one or more lines of the format

xxxxxx = word1 word2  word3  word4

where xxxxxx is the hexadecimal address of word1. An integral number of words (four-byte sequences, where the address of the first byte in the word is a multiple of 4) is always displayed, regardless of the value of hexloc1 or the amount of memory to be displayed. All output lines will always contain four words (16 bytes). The first byte of the displayed range will fall within the first word.

The error messages that can be produced are

As examples:

DISPLAY

displays the first four words in memory (default starting address of 0, default byte count of 1);

DISPLAY77F

displays the word containing the byte at address 77F, and the three subsequent words;

DISPLAY77F-407A

displays the words containing the bytes in the address range 775–407A;

DISPLAY77F.6

displays the words containing the six bytes starting at location 77F; and

DISPLAY50FF-END

displays the words containing the bytes in the address range 50FF to the end of memory.

The first step is a careful analysis of the specification to identify the causes and effects. The causes are as follows:

Each cause has been given an arbitrary unique number. Notice that four causes (5 through 8) are necessary for the second operand because the second operand could be (1) END, (2) hexloc2, (3) byte-count, (4) absent, and (5) none of the above. The effects are as follows:

The next step is the development of the graph. The cause nodes are listed vertically on the left side of the sheet of paper; the effect nodes are listed vertically on the right side. The semantic content of the specification is carefully analyzed to interconnect the causes and effects (i.e., to show under what conditions an effect is present).

Figure 4.12 shows an initial version of the graph. Intermediate node 32 represents a syntactically valid first operand; node 35 represents a syntactically valid second operand. Node 36 represents a syntactically valid command. If node 36 is 1, effect 91 (the error message) does not appear. If node 36 is 0, effect 91 is present.

Figure 4.12 Beginning of the Graph for the DISPLAY Command.

The full graph is shown in Figure 4.13. You should explore it carefully to convince yourself that it accurately reflects the specification.

Figure 4.13 Full Cause-Effect Graph without Constraints.

If Figure 4.13 were used to derive the test cases, many impossible-to-create test cases would be derived. The reason is that certain combinations of causes are impossible because of syntactic constraints. For instance, causes 2 and 3 cannot be present unless cause 1 is present. Cause 4 cannot be present unless both causes 2 and 3 are present. Figure 4.14 contains the complete graph with the constraint conditions. Notice that, at most, one of the causes 5, 6, 7, and 8 can be present. All other cause constraints are the requires condition. Notice that cause 17 (multiple output lines) requires the not of cause 8 (second operand is omitted); cause 17 can be present only when cause 8 is absent. Again, you should explore the constraint conditions carefully.

Figure 4.14 Complete Cause-Effect Graph of the DISPLAY Command.

The next step is the generation of a limited-entry decision table. For readers familiar with decision tables, the causes are the conditions and the effects are the actions. The procedure used is as follows:

In performing step 2, the considerations are as follows:

These complicated considerations are summarized in Figure 4.15, and Figure 4.16 is used as an example.

Figure 4.15 Considerations Used When Tracing the Graph.

Figure 4.16 Sample Graph to Illustrate the Tracing Considerations.

Assume that we want to locate all input conditions that cause the output state to be 0. Consideration 3 states that we should list only one circumstance where nodes 5 and 6 are 0. Consideration 2 states that for the state where node 5 is 1 and node 6 is 0, we should list only one circumstance where node 5 is 1, rather than enumerating all possible ways that node 5 can be 1. Likewise, for the state where node 5 is 0 and node 6 is 1, we should list only one circumstance where node 6 is 1 (although there is only one in this example). Consideration 1 states that where node 5 should be set to 1, we should not set nodes 1 and 2 to 1 simultaneously. Hence, we would arrive at five states of nodes 1 through 4; for example, the values:

rather than the 13 possible states of nodes 1 through 4 that lead to a 0 output state.

These considerations may appear to be capricious, but they have an important purpose: to lessen the combined effects of the graph. They eliminate situations that tend to be low-yield test cases. If low-yield test cases are not eliminated, a large cause-effect graph will produce an astronomical number of test cases. If the number of test cases is too large to be practical, you will select some subset, but there is no guarantee that the low-yield test cases will be the ones eliminated. Hence, it is better to eliminate them during the analysis of the graph.

We will now convert the cause-effect graph in Figure 4.14 into the decision table. Effect 91 will be selected first. Effect 91 is present if node 36 is 0. Node 36 is 0 if nodes 32 and 35 are 0,0; 0,1; or 1,0; and considerations 2 and 3 apply here. By tracing back to the causes, and considering the constraints among causes, you can find the combinations of causes that lead to effect 91 being present, although doing so is a laborious process.

The resultant decision table, under the condition that effect 91 is present, is shown in Figure 4.17 (columns 1 through 11). Columns (tests) 1 through 3 represent the conditions where node 32 is 0 and node 35 is 1. Columns 4 through 10 represent the conditions where node 32 is 1 and node 35 is 0. Using consideration 3, only one situation (column 11) out of a possible 21 situations where nodes 32 and 35 are 0 is identified. Blanks in the table represent “don't care” situations (i.e., the state of the cause is irrelevant) or indicate that the state of a cause is obvious because of the states of other dependent causes (e.g., in column 1, we know that causes 5, 7, and 8 must be 0 because they exist in an “at most one” situation with cause 6).

Figure 4.17 First Half of the Resultant Decision Table.

Columns 12 through 15 represent the situations where effect 92 is present. Columns 16 and 17 represent the situations where effect 93 is present. Figure 4.18 represents the remainder of the decision table.

Figure 4.18 Second Half of the Resultant Decision Table.

The last step is to convert the decision table into 38 test cases. A set of 38 test cases is listed here. The number or numbers beside each test case designate the effects that are expected to be present. Assume that the last location in memory on the machine being used is 7FFF.

Note that where two or more different test cases invoked, for the most part, the same set of causes, different values for the causes were selected to slightly improve the yield of the test cases. Also note that, because of the actual storage size, test case 22 is impossible (it will yield effect 95 instead of 94, as noted in test case 33). Hence, 37 test cases have been identified.

Remarks

Cause-effect graphing is a systematic method of generating test cases representing combinations of conditions. The alternative would be to make an ad hoc selection of combinations; but in doing so, it is likely that you would overlook many of the “interesting” test cases identified by the cause-effect graph.

Since cause-effect graphing requires the translation of a specification into a Boolean logic network, it gives you a different perspective on, and additional insight into, the specification. In fact, the development of a cause-effect graph is a good way to uncover ambiguities and incompleteness in specifications. For instance, the astute reader may have noticed that this process has uncovered a problem in the specification of the DISPLAY command. The specification states that all output lines contain four words. This cannot be true in all cases; it cannot occur for test cases 18 and 26 because the starting address is less than 16 bytes away from the end of memory.

Although cause-effect graphing does produce a set of useful test cases, it normally does not produce all of the useful test cases that might be identified. For instance, in the example we said nothing about verifying that the displayed memory values are identical to the values in memory and determining whether the program can display every possible value in a memory location. Also, the cause-effect graph does not adequately explore boundary conditions. Of course, you could attempt to cover boundary conditions during the process. For instance, instead of identifying the single cause

hexloc2>=hexloc1

you could identify two causes:

The problem in doing this, however, is that it complicates the graph tremendously and leads to an excessively large number of test cases. For this reason it is best to consider a separate boundary value analysis. For instance, the following boundary conditions can be identified for the DISPLAY specification:

Note that this does not imply that you would write 60 (37 + 23) test cases. Since the cause-effect graph gives us leeway in selecting specific values for operands, the boundary conditions could be blended into the test cases derived from the cause-effect graph. In this example, by rewriting some of the original 37 test cases, all 23 boundary conditions could be covered without any additional test cases. Thus, we arrive at a small but potent set of test cases that satisfy both objectives.

Note that cause-effect graphing is consistent with several of the testing principles in Chapter 2. Identifying the expected output of each test case is an inherent part of the technique (each column in the decision table indicates the expected effects). Also note that it encourages us to look for unwanted side effects. For instance, column (test) 1 specifies that we should expect effect 91 to be present and that effects 92 through 97 should be absent.

The most difficult aspect of the technique is the conversion of the graph into the decision table. This process is algorithmic, implying that you could automate it by writing a program; several commercial programs exist to help with the conversion.

Error Guessing

It has often been noted that some people seem to be naturally adept at program testing. Without using any particular methodology such as boundary value analysis of cause-effect graphing, these people seem to have a knack for sniffing out errors.

One explanation for this is that these people are practicing—subconsciously more often than not—a test-case design technique that could be termed error guessing. Given a particular program, they surmise—both by intuition and experience—certain probable types of errors and then write test cases to expose those errors.

It is difficult to give a procedure for the error-guessing technique since it is largely an intuitive and ad hoc process. The basic idea is to enumerate a list of possible errors or error-prone situations and then write test cases based on the list. For instance, the presence of the value 0 in a program's input is an error-prone situation. Therefore, you might write test cases for which particular input values have a 0 value and for which particular output values are forced to 0. Also, where a variable number of inputs or outputs can be present (e.g., the number of entries in a list to be searched), the cases of “none” and “one” (e.g., empty list, list containing just one entry) are error-prone situations. Another idea is to identify test cases associated with assumptions that the programmer might have made when reading the specification (i.e., factors that were omitted from the specification, either by accident or because the writer felt them to be obvious).

Since a procedure for error guessing cannot be given, the next-best alternative is to discuss the spirit of the practice, and the best way to do this is by presenting examples. If you are testing a sorting subroutine, the following are situations to explore:

• The input list is empty.
• The input list contains one entry.
• All entries in the input list have the same value.
• The input list is already sorted.

In other words, you enumerate those special cases that may have been overlooked when the program was designed. If you are testing a binary search subroutine, you might try the situations where: (1) there is only one entry in the table being searched; (2) the table size is a power of 2 (e.g., 16); and (3) the table size is one less than and one greater than a power of 2 (e.g., 15 or 17).

Consider the MTEST program in the section on boundary value analysis. The following additional tests come to mind when using the error-guessing technique:

• Does the program accept “blank” as an answer?
• A type-2 (answer) record appears in the set of type-3 (student) records.
• A record without a 2 or 3 in the last column appears as other than the initial (title) record.
• Two students have the same name or number.
• Since a median is computed differently depending on whether there is an odd or an even number of items, test the program for an even number of students and an odd number of students.
• The number-of-questions field has a negative value.

Error-guessing tests that come to mind for the DISPLAY command of the previous section are as follows:

The Strategy

The test-case design methodologies discussed in this chapter can be combined into an overall strategy. The reason for combining them should be obvious by now: Each contributes a particular set of useful test cases, but none of them by itself contributes a thorough set of test cases. A reasonable strategy is as follows:

Again, the use of this strategy will not guarantee that all errors will be found, but it has been found to represent a reasonable compromise. Also, it represents a considerable amount of hard work, but as we said at the beginning of this chapter, no one has ever claimed that program testing is easy.

Summary

Once you have agreed that aggressive software testing is a worthy addition to your development efforts, the next step is to design test cases that will exercise your application sufficiently to produce satisfactory test results. In most cases, consider a combination of black-box and white-box methodologies to ensure that you have designed rigorous program testing.

Test case design techniques discussed in this chapter include:

• Logic coverage. Tests that exercise all decision point outcomes at least once, and ensure that all statements or entry points are executed at least once.
• Equivalence partitioning. Defines condition or error classes to help reduce the number of finite tests. Assumes that a test of a representative value within a class also tests all values or conditions within that class.
• Boundary value analysis. Tests each edge condition of an equivalence class; also considers output equivalence classes as well as input classes.
• Cause-effect graphing. Produces Boolean graphical representations of potential test case results to aid in selecting efficient and complete test cases.
• Error guessing. Produces test cases based on intuitive and expert knowledge of test team members to define potential software errors to facilitate efficient test case design.

Extensive, in-depth testing is not easy; nor will the most extensive test case design assure that every error will be uncovered. That said, developers willing to go beyond cursory testing, who will dedicate sufficient time to test case design, analyze carefully the test results, and act decisively on the findings, will be rewarded with functional, reliable software that is reasonably error free.