08-05-2013, 04:43 PM
Constraint-Based Automatic Test Data Generation
Constraint-Based Automatic.pdf (Size: 1.14 MB / Downloads: 40)
Abstract
This paper presents a new technique for automatically
generating test data. The technique is based on mutation
analysis and creates test data that approximates relative adequacy.
The technique is a fault-based technique that uses algebraic
constraints to describe test cases designed to find particular
types of faults. A set of tools, collectively called Godzilla, has been
implemented that automatically generates constraints and solves
them to create test cases for unit and module testing. Godzilla
has been integrated with the Mothra testing system and has been
used as an effective way to generate test data that kill program
mutants. The paper includes an initial list of constraints and
discusses some of the problems that have been solved to develop
the complete implementation of the technique.
INTRODUCTION
SO FTWARE testing is the primary method by which testers establish confidence in the correctness of software. This
confidence is ordinarily established by executing the software
on test data chosen by some systematic testing procedure.
In recent years, the phrase “fault-based testing” has been
applied to techniques that choose test data that attempt to
show the presence (or absence) of specific faults during
unit testing. Techniques have been developed that determine
whether test data can detect specific faults (i.e., mutation
analysis [ 12]), and the theoretical properties of fault-based
testing have been explored [5], [27]. One of the most difficult
and expensive parts of applying these techniques has been the
actual generation of test data-which has traditionally been
done by hand. The work described in this paper represents
what we believe to be the first attempt to automatically
generate test data that meet the fault-based testing criteria.
Background
We use the following notation and assumptions. First, we
assume that all programs satisfy functional specifications. If
P is a program, then P(t) denotes the value of the function
computed by P at the point t. The set of all points at which
P defines a definite value is the domain of P. The letter D is
usually used to denote the domain of a program.
Generating Adequate Test Sets
In the past decade, several acceptors for relative-adequate
test sets have been implemented in the form of mutation
analysis systems. Early systems included PIMS [12] and
EXPER [l]. The most recent mutation analysis system is the
Mothra testing system [lo]. These systems have all created the
incorrect programs in @ by applying mutation operators to the
test program. Each program in @ is referred to as a mutant of
the original program. Mutation systems carry out an interactive
dialogue with the tester to find test data that executes correctly
on the original program and that causes each mutant program
to fail. Test data that causes a mutant program to fail is said
to kill the mutant.
ADEQUACY-BASETDE ST CASE CONSTRAINTS
A test case filter that generates test cases to kill mutants
needs to have one simple, broad characteristic: it must generate
test data that makes a difference in the mutant’s
behavior. That is, since the mutant is represented by a single
change to the source program, the execution state of the
mutant program must differ from that of the original program
after some execution of the mutated statement. We state this
characteristic as the necessiry condition:
Theorem: Given a program P and a mutant program M
that is formed by changing a statement S in P, for a test case
t to kill M, it is necessary that the state of M immediately
following some execution of S be different from the state of
P at the same point.
KILLING MUTANTS
Generating test data with or without a mutation system is
a difficult task that poses complex problems. Practical testdata-
generation techniques attempt to choose a subset of the
input space according to some testing criteria. The assumption
behind any criteria for generating test data is that the subset
of inputs chosen will find a large portion of the faults in the
program as well as help the tester establish some confidence in
the software. Test cases that score well on a mutation system
will have just those properties, because the test data is close to
being adequate relative to the mutation operators. Specifically,
the test data will find most, if not all, faults represented by the
mutation operators.
CONCLUSIONS
Although mutation analysis has repeatedly been demonstrated
to be an effective method for testing software [15],
[ 171, one shortcoming of the technique has always been that
it does not, by itself, generate test data. In this paper we
have presented an automatic test data generation technique
that solves this problem in a truly general way. By generating
test data specifically to kill mutant programs, we get test data
with the same quality as data generated interactively, but with
none of the pain and expense of that interaction.
Adequacy has long been promising as a theoretical basis for
testing software. The fact that our first attempt to implement
a system to produce mutation-adequate test data has yielded
a tool that is so successful is exciting. The development of
this technology is still in its infancy, yet it already seems to
provide better test data than other testing techniques. This is
not because it is revolutionary, but because it is evolutionary.
Constraint-based testing incorporates other testing techniques
directly. Because of the mutation analysis basis of CBT, the
test data generated includes the fault-detection capabilities of
such testing methods as branch coverage, predicate domain
analysis, and extrema1 values testing. The experiments that
have been performed with Godzilla encourage us that CBT will
create high-quality test cases that score well on the mutation
system.