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:

A and B and C
A B C   expected result
t t t   t
F t t   F
t F t   F
t t F   F

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

A or B or C
A B C   expected result
f f f   f
T f f   T
f T f   T
f f T   T

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)).1

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 variant2, 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.)

A && B && C T f f f f f f f
!A && B && C f / X f / f / T / X f / f / f / f /
A && !B && C f / X f / T / X f / f / f / f / f /
A && B && !C f / X T / X f / f / f / f / f / f /
A && B || C T / T / X T / X T / X f / f / T / X f /
A || B && C T / T / X T / X T / X T / X f / f / f /
A && B T / T / X f / f / f / f / f / f /
A && C T / f / T / X f / f / f / f / f /
B && C T / f / f / T / X f / f / f / f /

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.

1 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.

2 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]

About Brian Marick
I consult mainly on Agile software development, with a special focus on how testing fits in.

Contact me here: marick@exampler.com.




Agile Testing Directions
Tests and examples
Technology-facing programmer support
Business-facing team support
Business-facing product critiques
Technology-facing product critiques
Testers on agile projects

Permalink to this list


Working your way out of the automated GUI testing tarpit
  1. Three ways of writing the same test
  2. A test should deduce its setup path
  3. Convert the suite one failure at a time
  4. You should be able to get to any page in one step
  5. Extract fast tests about single pages
  6. Link checking without clicking on links
  7. Workflow tests remain GUI tests
Permalink to this list


Design-Driven Test-Driven Design
Creating a test
Making it (barely) run
Views and presenters appear
Hooking up the real GUI


Popular Articles
A roadmap for testing on an agile project: When consulting on testing in Agile projects, I like to call this plan "what I'm biased toward."

Tacit knowledge: Experts often have no theory of their work. They simply perform skillfully.

Process and personality: Every article on methodology implicitly begins "Let's talk about me."


Related Weblogs

Wayne Allen
James Bach
Laurent Bossavit
William Caputo
Mike Clark
Rachel Davies
Esther Derby
Michael Feathers
Developer Testing
Chad Fowler
Martin Fowler
Alan Francis
Elisabeth Hendrickson
Grig Gheorghiu
Andy Hunt
Ben Hyde
Ron Jeffries
Jonathan Kohl
Dave Liebreich
Jeff Patton
Bret Pettichord
Hiring Johanna Rothman
Managing Johanna Rothman
Kevin Rutherford
Christian Sepulveda
James Shore
Jeff Sutherland
Pragmatic Dave Thomas
Glenn Vanderburg
Greg Vaughn
Eugene Wallingford
Jim Weirich


Where to Find Me

Software Practice Advancement


All of 2006
All of 2005
All of 2004
All of 2003



Agile Alliance Logo