SAT-Based Logic Locking Test Pattern Generator for Detecting Stuck-at Faults in Integrated Circuits

This method converts stuck-at faults into key-controlled gates and uses SAT solvers to derive distinguishing input patterns, producing efficient test vectors that achieve full detection of all nonredundant stuck-at faults with fewer tests.

Background

Integrated circuits (ICs) increasingly power critical systems across automotive, aerospace and consumer electronics domains. As process geometries shrink and circuit complexity grows into billions of gates, even minor physical defects manifest as stuck‐at faults that can compromise device functionality, reliability or safety. Exhaustive testing of every fault site is thus crucial to ensure high yield and robust performance. Automated test pattern generation (ATPG) techniques have historically provided a systematic route for generating input vectors that excite and propagate single stuck‐at faults to observable outputs, yet the ballooning search space in modern netlists imposes severe computational burdens.

Conventional ATPG algorithms relying on path sensitization and backtracking, such as the D‐Algorithm and PODEM, often encounter exponential runtime due to deep fanout trees and high logic depth. Redundant faults go undetected or require costly formal analysis, while the sheer volume of vectors needed for complete coverage inflates test application time and memory footprints. Even SAT‐based ATPG formulations, though capable of improved pruning, suffer from numerous solver conflicts and cannot efficiently handle multiple fault interactions in a unified solve, leading to suboptimal coverage and protracted processing times.

Technology

This technology converts each stuck-at fault into a logic “lock” by inserting a key-controlled gate—an AND gate for stuck-at-0 and an OR gate for stuck-at-1—so that the correct key setting recreates faulty behavior while any other setting restores fault-free operation. To distinguish fanout branches, buffers are inserted to assign unique net names. A SAT-based miter is built from two copies of the locked circuit under different key assignments; solving this miter produces distinguishing input patterns (DIPs) that serve as test vectors, or else marks a fault redundant. In single-fault mode each fault is locked and solved independently, while in multiple-fault mode many faults are encoded under separate key bits so that a single DIP can detect multiple faults. Patterns may be seeded by initial commercial ATPG output and filtered via fault simulation to ensure full coverage of all non-redundant stuck-at faults.

The approach stands out by repurposing the SAT attack from logic locking for test pattern generation, avoiding symmetric XOR/XNOR gates and instead using asymmetric AND/OR gates to accurately model fault behavior. Unique net names for branch buffers guarantee correct SAT inputs, and encoding multiple faults in a single miter drastically reduces the total number of patterns needed. This method achieves 100% non-redundant stuck-at coverage, automatically identifies redundant faults, and overcomes the backtracking and runtime issues that hinder both traditional ATPG algorithms and earlier SAT-based techniques, making it highly scalable for complex circuits.

Benefits

  • Achieves 100% coverage of all non-redundant stuck-at faults
  • Automatically identifies and excludes redundant faults
  • Reduces the total number of test patterns (especially via multiple-fault targeting)
  • Decreases overall testing time by eliminating redundant tests
  • Overcomes limitations of traditional ATPG tools on complex circuits
  • Leverages SAT-based miter approach for efficient test pattern generation

Applications

  • ASIC test pattern generation
  • Automated test vector generation
  • FPGA fault detection testing
  • IC manufacturing test optimization
  • Hardware quality control automation

Additional info

Key-based fault modeling converts each stuck-at defect into a key-controlled gate—AND for sa0, OR for sa1—with buffers fanning out unique nets. A SAT-based miter of two keyed circuit copies under different key vectors yields distinguishing input patterns (DIPs) that target faults. In single-fault mode each fault is locked and solved independently; in multi-fault mode multiple faults share key bits so one DIP can detect several. Initial ATPG seeding and fault simulation refine full non-redundant coverage.