In previous chapters were covered random testing, or fuzzing. In this lesson, we'll cover automated test generation that takes a more directed approach. Some methodologies and examples are:
- Systematic testing -
Koratis a tool that conducts systematic testing
- This test suite targets programs with linked data structures
- Feedback-directed random testing -
Randoopis a tool that conducts this type of testing.
- This test suite targets Java Classes and Libraries.
Procedures have an infinite number of possible test inputs, however, only a finite number of test inputs are worth testing against the program. An insight is that, for test generation, we often find that systematically testing all inputs up to a small size can uncover a majority of the bugs.
The small test case hypothesis is, if there is any test that causes the
program to fail, this is such a small test. If a list function works for lists
3, it probably works for all lists - the function is
oblivious to the length.
Korat targets applications / libraries with linked data structures.
Korat does is enumerate the types of each member of each data structure,
determining what values each Class and Node can contain.
Korat then generates
test structures for all possible shapes of a given data structure.
The basic algorithm that
Korat uses to test programs is as follows:
- User selects maximum input size
- Generate all possible inputs up to size
- Discard inputs where the
pre-conditionfor the function is
- Run program on remaining inputs
- Check results using the function's
To calculate the number of possible binary trees for
k nodes, the formula is:
(k + 1)^(2k + 1)
The formula above is an overestimation of the number of possible binary trees. Some of the tree shapes provided in the above equation are not even tree-shaped, and many of them are isomorphic - exactly the same shape as other possible combinations. In reality, there are only 9 distinct binary trees with at most 3 nodes.
Korat uses a specific technique to cull test inputs by instrumenting the
pre-condition of the function under test.
Korat adds code to the function's
actions, observing the fields accessed by the function. This allows them with
the ability to enumerate the precondition - if a field isn't accessed by a
precondition the precondition does not depend on the field.
Korat enumerates shapes by their associated vectors:
- In the initial test candidate, all fields are null
- The next shape is generated by:
- Expanding the last field accessed by the pre-condition
- Backtracking if all possibilities for a field are exhausted
The key idea in this methodology is that
Korat never expands parts of the test
input if it's not examined by the function's pre-condition.
Korat also checks
for and discards shapes that are isomorphic to previously generated shapes.
Korat is strong when we can enumerate all possibilities, for example a small
test case for four nodes, two edges per node.
Korat is good for:
- Linked data structures
- Small, easily specified procedures
- Unit testing
Korat is weaker for:
- Integers, Floating-point numbers, strings
Korat is also as weak as the pre-condition for a function under test. If the
pre-condition is not specific and thorough enough,
Korat will generate
less-than-useful test conditions.
The problem with uniform random testing is that it creates too many illegal or
Randoop aims to randomly create new tests guided by feedback
from previously generated tests.
Randoop's recipe is as follows:
- Build new sequences incrementally, extending past sequences
- As soon as a sequence is created, execute it
- Use execution results to guide test generation towards sequences that create new object states
- Illegal sequence - sequences that crash before the contract is checked, e.g. throw an exception
- Redundant sequence -
Randoopmaintains a set of all objects created in execution of each sequence. A sequence is redundant if an object created during its execution belongs to an object in the maintained set.