State generation and automated class testing

The maturity of object-oriented methods has led to the wide availability of container classes: classes that encapsulate classical data structures and algorithms. Container classes are included in the C++ and Java standard lib raries, and in many proprietary libraries. The wide availability and use of these classes makes reliability important, and testing plays a central rol e in achieving that reliability. The large number of cases necessary for th orough testing of container classes makes automated testing essential. This paper presents a novel approach for automated testing of container classes based on combinatorial algorithms for state generation. The approach is il lustrated with black-box and white-box test drivers for a class implemented with the red-black tree data structure, used widely in industry and, in pa rticular, in the C++ Standard Template Library. The white-box driver is bas ed on a new algorithm for red-black tree generation. The drivers are evalua ted experimentally, providing quantitative measures of their effectiveness in terms of block and path coverage. The results clearly show that the appr oach is affordable in terms of development cost and execution time, and eff ective with respect to coverage achieved. The results also provide insight into the relative advantages of black-box and white-box drivers, and into t he difficult problem of infeasible paths. Copyright (C) 2000 John Whey & So ns, Ltd.