Efficient generation of test patterns using Boolean satisfiability

A combinational circuit can be tested for the presence of a single stuck-at fault by applying a set of inputs that excite a verifiable output response in that circuit. If the fault is present, the output will be different than it would be if the fault were not present. Given a circuit, the goal of an automatic test pattern generation system is to generate a set of input sets that will detect every possible single stuck-at fault in the circuit. These two papers describe a new method for generating test patterns: the Boolean satisfiability method. The new method is quite general and allows for the addition of any heuristic used by the structural search methods. The Boolean satisfiability method has produced excellent results on popular test pattern generation benchmarks. The first paper, Efficient Generation of Test Patterns Using Boolean Difference, gives an overview of a successful test pattern generation system using the Boolean satisfiability method. The second paper, A Framework for Evaluating Test Pattern Generation Strategies, describes potential test pattern generation heuristics and their efficacy in the Boolean satisfiability system.