Failure Evasion: Statistically Solving the NP Complete Problem of Testing Difficult-to-Detect Faults

Abstract

A circuit with n primary inputs (PIs) has N = 2n possible input vectors. A test vector to correctly detect a fault in that circuit must be among those 2n n-bit combinations. Clearly, this problem can be rephrased as a database search problem. It is colloquially known that using a pure random test generator to test for faults in a digital circuit is horribly inefficient. To overcome this inefficiency, various testing algorithms were successfully developed and implemented over the last 50 years. Classic algorithms like the D-algorithm, PODEM and FAN have long been foundations other algorithms have built upon to vastly improve the search time for test vectors.

Because searching for the last few faults that are hard to detect is mathematically NP complete, it can become computationally expensive to attain 100% fault coverage in a finite amount of time. Contemporary algorithms usually generate new test vectors based on properties of previous successful ones and hence enter a bottleneck when trying to find tests for these hard to detect stuck-at faults, as their test properties may not match previous test successes.

Since, all testing algorithms can be interpreted as unsorted database search methods, it is to our benefit if we choose to create a testing algorithm based on an efficient solution to database search. Currently, it has been shown that Grover’s quantum computing algorithm is the best solution to search a database of N elements with sub-linear O(√N) complexity, while most other algorithms are linear or O(N). Hence, it is clear that creating a testing algorithm that emulates Grover’s algorithm for finding test vectors could be a faster solution for VLSI testing.

We hypothesize that avoiding the properties of failed vectors by learning from each failure would lead to a solution in fewer iterations. We use a statistical method to maximize the “Mahalanobis distance” from the failed vectors while simultaneously reducing the distance to “activation/propagation vectors”. Our results show that this technique is very efficient in finding tests for these final hard to detect stuck-at faults.

For the b12 combinational benchmark circuit with 15 primary inputs (PIs), a random search, on average, took 16,367 iterations to find a test for a difficult to detect stuck-at fault. Our best algorithm was able to find a test, on average, in 311 iterations for the same fault. While it is not the best result when compared to a quantum search (which needs 181 iterations on average), it is still about two orders of magnitude better when compared to a random search and hence is significant. This work presents the idea and a detailed analysis of how our algorithm functions and results for several benchmark circuits.