Exploration Through Example

Example-driven development, Agile testing, context-driven testing, Agile programming, Ruby, and other things of interest to Brian Marick

191.8

⇒

167.2

⇒

186.2

183.6

184.0

183.2

184.6

Wed, 27 Sep 2006

More on boolean expressions

My examples below use a simple rule for deciding what values of a boolean expression to test. I should probably describe it and justify it.

Given an expression with all ands like X1 and X2 and ... and Xn, you use these test values:

1. One case: all the Xi's are true.

2. N cases. In each, all the Xi's are true except for one that's false. (A different one every time.) The way I think about it is that, for each Xi, there's an example that shows the whole expression is false exactly and only because of it.

So the table for (A and B and C) would be this:

The case for or-expressions is similar: just flip all the trues and falses:

The reasoning behind these rules is based on mutation testing, the name for a long thread of academic research on testing. The way I state it (which is different in an unimportant way from how it's usually put) is that mutation testing involves assuming that the code is incorrect in some definable way, then asking for a test suite that can distinguish the incorrect code you have from the correct code you should have.

Now, for any given program, there are an infinite number of variants, so mutation testing depends on picking a definition-of-incorrectness that (a) lets you generate a reasonably small set of alternatives, but (b) gives you confidence that you've caught all the plausible errors. The usual approach is to assume one-token errors.

For example, suppose you are given (A and B or C). Maybe it should be (A or B and C) or (A and not B or C) or (A and (B or C)).¹

One-token errors aren't the only ones you could make. For example, you might completely forget that D ought to be involved in the expression—it should be (A and B and C and D). That's a fault of omission, and mechanical techniques aren't good at them. Nevertheless, one-token errors seem to work pretty well for boolean expressions.

Suppose you have the original (A and B or C) and a variant (not A and B or C). The test value (A=true,B=true,C=true) distinguishes the two, because the given expression yields true while the possibly-more-correct variant would yield false. So, when you run the original program and its variant², that test case will produce one answer in the original and a different one in the variant. One of them's got to be wrong. If it's the original program, you've found a bug. If it's the variant, you know that variant cannot be the correct program (the original is not incorrect in that way). In the jargon, the mutant is killed.

Trying all the possible combinations of variable values will either find a one-token error or kill all the mutants. But you never have to try all of them. There will be some test inputs that don't add anything: any mutant they kill will be killed by some other test input. So you can construct a minimal set for any given expression.

If you look at the table below, you can see that the rule for and-expressions I gave above is justified; the cases I give kill all the mutants. (In the table, the first row is for the expression as given; each row below it is a mutant. The X's in a cell means that column's test case kills that mutant.)

Remember all this assumes that tests powerful enough to catch one-token errors will catch more complicated (but still plausible) errors. A way to convince yourself is to try and find a variant of (A and B and C) that won't be caught by these test cases. Ask yourself if it's at all plausible that you'd make such an error. (Remember: we've already conceded faults of omission.)

These rules are easy to memorize. The cases for expressions that mix and and or are not. A long time ago, I wrote a program that generates probably-minimal test sets for any given boolean expression (including relational operators like a<b). Timothy Coulter and Curtis Pettit, students of Cem Kaner, made it more capable and gave it a web UI. Here it is: http://www.oneofthewolves.com/multi/applet.html.

When using the style I described earlier, I don't think you need multi, because I'm tentatively advocating always breaking tables that combine ands and ors into separate tables that do not.

¹ I can't remember if the transformations I used when working all this out included substituting one variable for another (like (A and B and A)). Multi, described after this footnote, doesn't. I don't think it would make a difference—certainly it doesn't in this particular example—but I'm not going to bother to check.

² I'm leaving what it means to "run a program" vague. That gets to the difference of whether the mutation is "weak" or "strong". See this post by Ivan Moore. I didn't find much in the online literature about mutation testing; if you want to know more, you'll have to go to the library. There are some starting references at the end of this paper (PDF).

## Posted at 08:36 in category /fit [permalink] [top]