Automated inference of classifications and dependencies for combinatorial testing

Abstract

Even for small programs, the input space is huge - often unbounded. Partition testing divides the input space into disjoint equivalence classes and combinatorial testing selects a subset of all possible input class combinations, according to criteria such as pairwise coverage. The down side of this approach is that the partitioning of the input space into equivalence classes (input classification) is done manually. It is expensive and requires deep domain and implementation understanding. In this paper, we propose a novel approach to classify test inputs and their dependencies automatically. Firstly, random (or automatically generated) input vectors are sent to the system under test (SUT). For each input vector, an observed “hit vector” is produced by monitoring the execution of the SUT. Secondly, hit vectors are grouped into clusters using machine learning. Each cluster contains similar hit vectors, i.e., similar behaviors, and from them we obtain corresponding clusters of input vectors. Input classes are then extracted for each input parameter straightforwardly. Our experiments with a number of subjects show good results as the automatically generated classifications are the same or very close to the expected ones.