Search space reduction through clustering in test generation

An important factor of performance in test generation is the number of decisions in the search space. The more decisions are made in order to find a test the larger is the search space. This paper introduces an algorithm for the reduction of the number of decisions. Unlike classical test generation methods which perform their search on a netlist of gates, this algorithm works at a higher level. The gates of the circuit to test are partitioned into clusters. The search performed at the cluster level becomes a progressive translation of a set of value assignments to another set of value assignments that steps over cluster boundaries. To be able to step over cluster boundaries sensitization and propagation conditions are used. Experimental data demonstrate the effectiveness of the algorithm in reducing the number of decisions