Introduction

Test ideas are based on fault models, notions of which faults are plausible in software and how those faults can best be uncovered. This guideline shows how to create test ideas from boolean and relational expressions. It first motivates the techniques by looking at code, then describes how to apply them if the code hasn't been written yet or is otherwise unavailable.

Boolean Expressions

Consider the following code snippet, taken from an (imaginary) system for managing bomb detonation. It's part of the safety system and controls whether the "detonate bomb" button push is obeyed.

if (publicIsClear || technicianClear) {
    bomb.detonate();
}

The code is wrong. The || should be an &&. That mistake will have bad effects. Instead of detonating the bomb when both the bomb technician and public are clear, the system will detonate when either is clear.

What test would find this bug?

Consider a test in which the button is pushed when both the technician and public are clear. The code will allow the bomb to be detonated. But-and this is important-the correct code (the one that uses an &&) would do the same. So the test is useless at finding this fault.

Similarly, this incorrect code behaves correctly when both the technician and public are next to the bomb: the bomb is not detonated.

To find the bug, you have to have a case in which the code as written evaluates differently than the code that should have been written. For example, the public must be clear, but the bomb technician is still next to the bomb. Here are all the tests in table form:

The two middle tests are both useful for finding this particular fault. Note, however, that they're redundant: since either will find the fault, you needn't run both.

There are other ways in which the expression might be wrong. Here are two lists of common mistakes in boolean expressions. The faults on the left are all caught by the technique discussed here. The faults on the right might not be. So this technique doesn't catch all the faults we might like, but it's still useful.

How are these ideas used? Suppose you're given a boolean expression like a&&!b. You could construct a truth table like this one:

If you crunched through all the possibilities, you'd find that the first, second, and fourth possibilities are all that's needed. The third expression will find no faults that won't be found by one of the others, so you needn't try it. (As the expressions grow more complicated, the savings due to unneeded cases grow quickly.)

Of course, no one sane would build such a table. Fortunately, you don't have to. It's easy to memorize the required cases for simple expressions. (See the next section.) For more complex expressions, such as A&&B||C, see Test Ideas for Mixtures of ANDs and ORs, which lists test ideas for expressions with two or three operators. For even more complex expressions, a program can be used to generate test ideas.

Tables for Simple Boolean Expressions

If the expression is A&&B, test with:

If the expression is A||B, test with:

If the expression is A₁ && A₂ && ... && A_n, test with:

If the expression is A₁ || A₂ || ... || A_n, test with:

If the expression is A, test with:

So, when you need to test a&&!b, you can apply the first table above, invert the sense of b (because it's negated), and get this list of Test Ideas:

• A true, B false
• A true, B true
• A false, B false

Relational Expressions

Here's another example of code with a fault:

if (finished < required) {
    siren.sound();
}

The < should be a <=. Such mistakes are fairly common. As with boolean expressions, you can construct a table of test values and see which ones detect the fault:

More generally, the fault can be detected whenever finished=required. From analyses of plausible faults, we can get these rules for test ideas:

If the expression is A<B or A>=B, test with

If the expression is A>B or A<=B, test with

What does "slightly" mean? If A and B are integers, A should be one less than or larger than B. If they are floating point numbers, A should be a number quite close to B. (It's probably not necessary that it be the the closest floating point number to B.)

Rules for Combined Boolean and Relational Expressions

Most relational operators occur within boolean expressions, as in this example:

if (finished < required) {
    siren.sound();
}

The rules for relational expressions would lead to these test ideas:

1. finished is equal to required
2. finished is slightly less than required

The rules for boolean expressions would lead to these:

1. finished < required should be true
2. finished < required should be false

But if finished is slightly less than required, finished < required is true, so there's no point in writing down the latter.

And if finished equals required, finished < required is false, so there's no point in writing down that latter one either.

So, if a relational expression contains no boolean operators (&& and ||), ignore the fact that it's also a boolean expression.

Things are a bit more complicated with combinations of boolean and relational operators, like this one:

if (count<5 || always) {
   siren.sound();
}

From the relational expression, you get:

• count slightly less than 5
• count equal to 5

From the boolean expression, you get:

• count<5 true, always false
• count<5 false, always true
• count<5 false, always false

These can be combined into three more specific test ideas. (Here, note that count is an integer.)

1. count=4, always false
2. count=5, always true
3. count=5, always false

Notice that count=5 is used twice. It might seem better to use it only once, to allow the use of some other value-after all, why test count with 5 twice? Wouldn't it be better to try it once with 5 and another time with some other value such that count<5 is false? It would be, but it's dangerous to try. That's because it's easy to make a mistake. Suppose you tried the following:

1. count=4, always false
2. count=5, always true
3. count<5 false, always false

Suppose that there's a fault that can only be caught with count=5. What that means is that the value 5 will cause count<5 to produce false in the second test, when the correct code would have produced true. However, that false value is immediately or'd with the value of always, which is true. That means the value of the whole expression is correct, even though the value of the relational subexpression was wrong. The fault will go undiscovered.

The fault doesn't go undiscovered if it's the other count=5 that is left less specific.

Similar problems happen when the relational expression is on the right-hand side of the boolean operator.

Because it's hard to know which subexpressions have to be exact and which can be general, it's best to make them all exact. The alternative is to use the boolean expression program mentioned above. It produces correct test ideas for arbitrary mixed boolean-and-relational expressions.

Test ideas without Code

As explained in Concept: Test-first Design, it's usually preferable to design tests before implementing code. So, although the techniques are motivated by code examples, they'll usually be applied without code. How?

Certain design artifacts, such as statecharts and sequence diagrams, use boolean expressions as guards. Those cases are straightforward-simply add the test ideas from the boolean expressions to the artifact's test idea checklist. See Guideline: Test Ideas for Statechart and Activity Diagrams.

The trickier case is when boolean expressions are implicit rather than explicit. That's often the case in descriptions of APIs. Here's an example. Consider this method:

List matchList(Directory d1, Directory d1,
       FilenameFilter excluder);

The description of this method's behavior might read like this:

Returns a List of the absolute pathnames of all files that appear in both Directories. Subdirectories are descended. [...] Filenames that match the excluder are excluded from the returned list. The excluder only applies to the top-level directories, not to filenames in subdirectories.

The words "and" and "or" do not appear. But when is a filename included in the return list? When it appears in the first directory and it appears in the second directory and it's either in a lower level directory or it's not specifically excluded. In code:

if (appearsInFirst && appearsInSecond &&
    (inLowerLevel || !excluded)) {
  add to list
}

Here are the test ideas for that expression, given in tabular form:

The general approach for discovering implicit boolean expressions from text is to first list the actions described (such as "returns a matching name"). Then write a boolean expression that describes the cases in which an action is taken. Derive test ideas from all the expressions.

There's room for disagreement in that process. For example, one person might write down the boolean expression used above. Another might say that there are really two distinct actions: first, the program discovers matching names, then it filters them out. So, instead of one expression, there are two:

discover a match:

happens when a file is in the first directory and a file with the same name is in the second directory

filter a match:

happens when the matching files are in the top level and the name matches the excluder

These different approaches can lead to different test ideas and thus different tests. But the differences are most likely not particularly important. That is, the time spent worrying about which expression is right, and trying alternatives, would be better spent on other techniques and producing more tests. If you're curious about what the sorts of differences might be, read on.

The second person would get two sets of test ideas.

test ideas about discovering a match:

• file in first directory, file in second directory (true, true)
• file in first directory, file not in second directory (true, false)
• file not in first directory, file in second directory (false, true)

test ideas about filtering a match (once one has been discovered):

• matching files are in the top level, the name matches the excluder (true, true)
• matching files are in the top level, the name doesn't match the excluder (true, false)
• matching files are in some lower level, the name matches the excluder (false, true)

Suppose those two sets of test ideas are combined. The ones in the second set only matter when the file is in both directories, so they can only be combined with the first idea in the first set. That gives us the following:

Two of the test ideas about discovering a match do not appear in that table. We can add them like this:

The blank cells indicate that the columns are irrelevant.

This table now looks rather similar to the first person's table. The similarity can be emphasized by using the same terminology. The first person's table has a column called "inLower", and the second person's has one called "in top level". They can be converted by flipping the sense of the values. Doing that, we get this version of the second table:

The first three rows are identical to the first person's table. The last two differ only in that this version doesn't specify values that the first does. This amounts to an assumption about the way the code was written. The first assumed a complicated boolean expression:

if (appearsInFirst && appearsInSecond &&
    (inLowerLevel || !excluded)) {
  add to list
}

The second assumes nested boolean expressions:

if (appearsInFirst && appearsInSecond) {
    // found match.
    if (inTopLevel && excluded) {
// filter it
    }
}     

The difference between the two is that the test ideas for the first detect two faults that the ideas for the second do not, because those faults don't apply.

1. In the first implementation, there can be a misparenthesization fault. Are the parentheses around the || correct or incorrect? Since the second implementation has no || and no parentheses, the fault cannot exist.
2. The test requirements for the first implementation check whether the second && should be an ||. In the second implementation, that explicit && is replaced by the implicit && of the nested if statements. There's no ||-for-&& fault, per se. (It might be the case that the nesting is incorrect, but this technique does not address that.)