The automated generation of test cases for heap allocated, complex, structures is particularly difficult. Various state of the art tools tackle this problem by bounded exhaustive exploration of potential test cases, using constraint solving mechanisms based on techniques such as search, model checking, symbolic execution and combinations of these.

In this talk, we will describe some technical issues associated with effectively generating bounded exhaustive test suites using constraint solving ( e.g. the elimination of isomorphic structures), and how these are tackled in practice. We will also present a technique for improving the generation, which employs a test criterion for pruning the search: a test criterion is incorporated in the constraint based mechanism so that the exploration of potential test cases can be pruned without missing coverable classes of inputs. We present the technique, together with some case studies illustrating its performance for some black box testing criteria.