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 X_{1}
and X_{2} and ... and X_{n} , you use these
test values:
One case: all the X_{i} 's are true .
N cases. In each, all
the X_{i} 's are true except
for one that's false . (A different one every time.)
The way I think about it is that, for
each X_{i} , 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
definitionofincorrectness 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 onetoken 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}
Onetoken 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, onetoken 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
possiblymorecorrect variant would yield false . So,
when you run the original program and its variant^{2}, 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 onetoken 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
onetoken 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 probablyminimal 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]
