2014

 back to the year overview

• Matthias Sauer, Ilia Polian, Michael E. Imhof, Abdullah Mumtaz, Eric Schneider, Alexander Czutro, Hans-Joachim Wunderlich, Bernd Becker
  Variation-Aware Deterministic ATPG
  2014 IEEE European Test Symposium , pages: 1 - 6
  » show abstract« hide abstract
  Abstract

  In technologies affected by variability, the detection status of a small-delay fault may vary among manufactured circuit instances. The same fault may be detected, missed or provably undetectable in different circuit instances. We introduce the first complete flow to accurately evaluate and systematically maximize the test quality under variability. As the number of possible circuit instances is infinite, we employ statistical analysis to obtain a test set that achieves a fault-efficiency target with an user-defined confidence level. The algorithm combines a classical path-oriented test-generation procedure with a novel waveformaccurate engine that can formally prove that a small-delay fault is not detectable and does not count towards fault efficiency. Extensive simulation results demonstrate the performance of the generated test sets for industrial circuits affected by uncorrelated and correlated variations.

2013

 back to the year overview

• Linus Feiten, Matthias Sauer, Tobias Schubert, Alexander Czutro, Victor Tomashevich, Eberhard Böhl, Ilia Polian, Bernd Becker
  #SAT for Vulnerability Analysis of Security Components
  2013 (Workshop-Paper, Informal Proceedings) IEEE European Test Symposium
  » show abstract« hide abstract
  Abstract

  Vulnerability to malicious fault attacks is an emerging concern for hardware circuits that process sensitive data.We describe a new methodology to assess the vulnerability to such attacks, taking into account built-in protection mechanisms. Our method is based on accurate modeling of fault effects and their detection status expressed as Boolean satisfiability (SAT) formulae. Vulnerability is quantified based on the number of solutions of such formulae, which are computed by an eficient #SAT solver. We demonstrate the applicability of this method by analyzing a sequential pseudo random number generator and a combinatorial multiplier circuit both protected by robust error-detecting codes.
• Matthias Sauer, Alexander Czutro, Tobias Schubert, Stefan Hillebrecht, Ilia Polian, Bernd Becker
  SAT-based Analysis of Sensitisable Paths
  2013 Test of Computers, volume: 30, issue: 4, pages: 81 - 88
  » show abstract« hide abstract
  Abstract

  A common trend in the past has been to detect delay defects in nanoscale technologies through the longest sensitisable paths. This approach does not hold up for non-trivial defects due to modeling inaccuracies. This article supports tests through all paths of customized length, using current SAT-solving advances.

2012

 back to the year overview

• Alexander Czutro, Michael Imhof, Jie Jiang, Abdullah Mumtaz, Matthias Sauer, Bernd Becker, Ilia Polian, Hans-Joachim Wunderlich
  Variation-Aware Fault Grading
  2012 IEEE Asian Test Symp., pages: 344 - 349
• Linus Feiten, Matthias Sauer, Tobias Schubert, Alexander Czutro, Eberhard Böhl, Ilia Polian, Bernd Becker
  #SAT-Based Vulnerability Analysis of Security Components -- A Case Study
  2012 IEEE International Symposium on Defect and Fault Tolerance (DFT), pages: 49 - 54
  » show abstract« hide abstract
  Abstract

  In this paper we describe a new approach to assess a circuit's vulnerability to fault attacks. This is achieved through analysis of the circuit's design specification, making use of modern SAT solving techniques. For each injectable fault, a corresponding SAT instance is generated. Every satisfying solution for such an instance is equivalent to a circuit state and an input assignment for which the fault affcts the circuit's outputs such that the error is not detected by the embedded fault detection. The number of solutions is precisely calculated by a #SAT solver and can be translated into an exact vulnerability measure. We demonstrate the applicability of this method for design space exploration by giving detailed results for various implementations of a deterministic random bit generator.
• Matthias Sauer, Stefan Kupferschmid, Alexander Czutro, Sudhakar M. Reddy, Bernd Becker
  Analysis of Reachable Sensitisable Paths in Sequential Circuits with SAT and Craig Interpolation
  2012 Int'l Conf. on VLSI Design
  » show abstract« hide abstract
  Abstract

  Test pattern generation for sequential circuits benefits from scanning strategies as these allow the justification of arbitrary circuit states. However, some of these states may be unreachable during normal operation. This results in non-functional operation which may lead to abnormal circuit behaviour and result in over-testing. In this work, we present a versatile approach that combines a highly adaptable SAT-based path-enumeration algorithm with a model-checking solver for invariant properties that relies on the theory of Craig interpolants to prove the unreachability of circuit states. The method enumerates a set of longest sensitisable paths and yields test sequences of minimal length able to sensitise the found paths starting from a given circuit state. We present detailed experimental results on the reach ability of sensitisable paths in ITC 99 circuits.
• Matthias Sauer, Stefan Kupferschmid, Alexander Czutro, Ilia Polian, Sudhakar M. Reddy, Bernd Becker
  Functional Justification in Sequential Circuits using SAT and Craig Interpolation
  2012 GI/ITG Workshop “Testmethoden und Zuverlässigkeit von Schaltungen und Systemen”
• Matthias Sauer, Stefan Kupferschmid, Alexander Czutro, Ilia Polian, Sudhakar M. Reddy, Bernd Becker
  Functional Test of Small-Delay Faults using SAT and Craig Interpolation
  2012 Int'l Test Conf., pages: 1 - 8
  » show abstract« hide abstract
  Abstract

  We present SATSEQ, a timing-aware ATPG system for small-delay faults in non-scan circuits. The tool identifies the longest paths suitable for functional fault propagation and generates the shortest possible sub-sequences per fault. Based on advanced model-checking techniques, SATSEQ provides detection of small-delay faults through the longest functional paths. All test sequences start at the circuit's initial state; therefore, overtesting is avoided. Moreover, potential invalidation of the fault detection is taken into account. Experimental results show high detection and better performance than scan testing in terms of test application time and overtesting-avoidance.
• Alexander Czutro, Matthias Sauer, Ilia Polian, Bernd Becker
  Multi-Conditional ATPG using SAT with Preferences
  2012 GI/ITG Workshop “Testmethoden und Zuverlässigkeit von Schaltungen und Systemen”
• Alexander Czutro, Matthias Sauer, Ilia Polian, Bernd Becker
  Multi-Conditional SAT-ATPG for Power-Droop Testing
  2012 IEEE European Test Symp.
  » show abstract« hide abstract
  Abstract

  Power droop is a non-trivial signal-integrity-related effect triggered by specific power-supply conditions. High-frequency and low-frequency power droop may lead to failure of an IC during application time, but they usually remain undetected by state-of-the-art manufacturing test methods, as the fault excitation imposes particular conditions on global switching activity over several time frames. Hence, ATPG for power-droop test (PD-ATPG) is an extremely hard problem that has not yet been solved optimally. In this paper, we use a SAT-based ATPG engine that employs a mechanism known as SAT-solving with qualitative preferences to generate a solution guaranteed to be optimal for a given set of optimisation criteria, however at the expense of high SAT-solving times. Therefore, a well-balanced set of criteria has to be chosen for the SAT-formulation in order to get as good solutions as possible without rendering the SAT-instances impracticably hard. We explore several strategies and evaluate them experimentally.
• Jie Jiang, Matthias Sauer, Alexander Czutro, Bernd Becker, Ilia Polian
  On the Optimality of K Longest Path Generation Algorithm Under Memory Constraints
  2012 Conf. on Design, Automation and Test in Europe, pages: 418 - 423
  » show abstract« hide abstract
  Abstract

  Adequate coverage of small-delay defects in circuits affected by statistical process variations requires identification and sensitization of multiple paths through potential defect sites. Existing K longest path generation (KLPG) algorithms use a data structure called path store to prune the search space by restricting the number of sub-paths considered at the same time. While this restriction speeds up the KLPG process, the algorithms lose their optimality and do not guarantee that the K longest sensitizable paths are indeed found. We investigate, for the first time, the effects of missing some of the longest paths on the defect coverage. We systematically quantify how setting different limits on the path-store size affects the numbers and relative lengths of identified paths, as well as the run-times of the algorithm. We also introduce a new optimal KLPG algorithm that works iteratively and pinpointedly addresses defect locations for which the path-store size limit has been exceeded in previous iterations. We compare this algorithm with a naïve KLPG approach that achieves optimality by setting the path-store size limit to a very large value. Extensive experiments are reported for 45nm-technology data.
• Matthias Sauer, Alexander Czutro, Bernd Becker, Ilia Polian
  On the Quality of Test Vectors for Post-Silicon Characterization
  2012 IEEE European Test Symp.
  » show abstract« hide abstract
  Abstract

  Post-silicon validation, i.e., physical characterization of a small number of fabricated circuit instances before start of high-volume manufacturing, has become an essential step in integrated circuit production. Post-silicon validation is required to identify intricate logic or electrical bugs which could not be found during pre-silicon verification. In addition, physical characterization is useful to determine the performance distribution of the manufactured circuit instances and to derive performance yield. Test vectors used for this step are subject to different requirements compared to vectors for simulation-based verification or for manufacturing test. In particular, they must sensitize a very comprehensive set of paths in the circuit, assuming massive variations and possible modeling deficiencies. An inadequate test vector set may result in overly optimistic yield estimates and wrong manufacturing decisions. On the other hand, the size of the test vector set is less important than in verification or manufacturing test. In this paper, we systematically investigate the relationship between the quality of the employed test vectors and the accuracy of yield-performance predictions. We use a highly efficient SAT-based algorithm to generate comprehensive test vector sets based on simple model assumptions and validate these test sets using simulated circuit instances which incorporate effects of process variations. The obtained vector sets can also serve as a basis for adaptive manufacturing test.
• Alexander Czutro, Matthias Sauer, Tobias Schubert, Ilia Polian, Bernd Becker
  SAT-ATPG Using Preferences for Improved Detection of Complex Defect Mechanisms
  2012 VLSI Test Symp.
  » show abstract« hide abstract
  Abstract

  Failures caused by phenomena such as crosstalk or power-supply noise are gaining in importance in advanced nanoscale technologies. The detection of such complex defects benefits from the satisfaction of certain constraints, for instance justifying specific transitions on neighbouring lines of the defect location. We present a SAT-based ATPG-tool that supports the enhanced conditional multiple-stuck-at fault model (ECMS@). This model can specify multiple fault locations along with a set of hard conditions imposed on arbitrary lines; hard conditions must hold in order for the fault effect to become active. Additionally, optimisation constraints that may be required for best coverage can be specified via a set of soft conditions. The introduced tool justifies as many of these conditions as possible, using a mechanism known as SAT with preferences. Several applications are discussed and evaluated by extensive experimental data. Furthermore, a novel fault-clustering technique is introduced, thanks to which the time required to classify all stuck-at faults in a suite of industrial benchmarks was reduced by up to 65%.
• Matthias Sauer, Alexander Czutro, Ilia Polian, Bernd Becker
  Small-Delay-Fault ATPG with Waveform Accuracy
  2012 Int'l Conf. on CAD, pages: 30 - 36
  » show abstract« hide abstract
  Abstract

  The detection of small-delay faults is traditionally performed by sensitizing transitions on a path of sufficient length from an input to an output of the circuit going through the fault site. While this approach allows efficient test generation algorithms, it may result in false positives and false negatives as well, i.e. undetected faults are classified as detected or detectable faults are classified as undetectable. We present an automatic test pattern generation algorithm which considers waveforms and their propagation on each relevant line of the circuit. The model incorporates individual delays for each gate and filtering of small glitches. The algorithm is based on an optimized encoding of the test generation problem by a Boolean satisfiability (SAT) instance and is implemented in the tool WaveSAT. Experimental results for ISCAS-85, ITC-99 and industrial circuits show that no known definition of path sensitization can eliminate false positives and false negatives at the same time, thus resulting in inadequate small-delay fault detection. WaveSAT generates a test if the fault is testable and is also capable of automatically generating a formal redundancy proof for undetectable small-delay faults; to the best of our knowledge this is the first such algorithm that is both scalable and complete.

2011

 back to the year overview

• Jie Jiang, Matthias Sauer, Alexander Czutro, Bernd Becker, Ilia Polian
  On the Optimality of K Longest Path Generation
  2011 Workshop on RTL and High Level Testing
• Matthias Sauer, Alexander Czutro, Ilia Polian, Bernd Becker
  Estimation of Component Criticality in Early Design Steps
  2011 IEEE Int'l Online Testing Symp., pages: 104 - 110
• Matthias Sauer, Jie Jiang, Alexander Czutro, Ilia Polian, Bernd Becker
  Efficient SAT-Based Search for Longest Sensitisable Paths
  2011 Test Symposium (ATS), 2011 20th Asian, pages: 108 - 113
  » show abstract« hide abstract
  Abstract

  We present a versatile method that enumerates all or a user-specified number of longest sensitisable paths in the whole circuit or through specific components. The path information can be used for design and test of circuits affected by statistical process variations. The algorithm encodes all aspects of the path search as an instance of the Boolean Satisfiability Problem (SAT), which allows the method not only to benefit from recent advances in SAT-solving technology, but also to avoid some of the drawbacks of previous structural approaches. Experimental results for academic and industrial benchmark circuits demonstrate the method's accuracy and scalability.
• Matthias Sauer, Alexander Czutro, Tobias Schubert, Stefan Hillebrecht, Ilia Polian, Bernd Becker
  SAT-Based Analysis of Sensitisable Paths
  2011 IEEE Design and Diagnostics of Electronic Circuits and Systems, pages: 93 - 98
  » show abstract« hide abstract
  Abstract

  Manufacturing defects in nanoscale technologies have highly complex timing behaviour that is also affected by process variations. While conventional wisdom suggests that it is optimal to detect a delay defect through the longest sensitisable path, non-trivial defect behaviour along with modelling inaccuracies necessitate consideration of paths of well-controlled length during test generation. We present a generic methodology that yields tests through all sensitisable paths of user-specified length. The resulting tests can be employed within the framework of adaptive testing. The methodology is based on encoding the problem as a Boolean-satisfiability (SAT) instance and thereby leverages recent advances in SAT-solving technology.

2010

 back to the year overview

• Alexander Czutro, Ilia Polian, Matthew Lewis, Piet Engelke, Sudhakar M. Reddy, Bernd Becker
  Thread-Parallel Integrated Test Pattern Generator Utilizing Satisfiability Analysis
  2010 International Journal of Parallel Programming, volume: 38, issue: 3-4, pages: 185 - 202
  » show abstract« hide abstract
  Abstract

  Efficient utilization of the inherent parallelism of multi-core architectures is a grand challenge in the field of electronic design automation (EDA). One EDA algorithm associated with a high computational cost is automatic test pattern generation (ATPG). We present the ATPG tool TIGUAN based on a thread-parallel SAT solver. Due to a tight integration of the SAT engine into the ATPG algorithm and a carefully chosen mix of various optimization techniques, multi-million-gate industrial circuits are handled without aborts. TIGUAN supports both conventional single-stuck-at faults and sophisticated conditional multiple stuck-at faults which allows to generate patterns for non-standard fault models. We demonstrate how TIGUAN can be combined with conventional structural ATPG to extract full benefit of the intrinsic strengths of both approaches.

2009

 back to the year overview

• Alexander Czutro, Ilia Polian, Piet Engelke, Sudhakar M. Reddy, Bernd Becker
  Dynamic Compaction in SAT-Based ATPG
  2009 IEEE Asian Test Symp.
• Alexander Czutro, Bernd Becker, Ilia Polian
  Performance Evaluation of SAT-Based ATPG on Multi-Core Architectures
  2009 Test Symposium
• Marc Hunger, Sybille Hellebrand, Alexander Czutro, Ilia Polian, Bernd Becker
  Robustheitsanalyse stark fehlersicherer Schaltungen mit SAT-basierter Testmustererzeugung
  2009 GMM/ITG-Fachtagung “Zuverlässigkeit und Entwurf”
• Marc Hunger, Sybille Hellebrand, Alejandro Czutro, Ilia Polian, Bernd Becker
  ATPG-Based Grading of Strong Fault-Secureness
  2009 IEEE Int'l Online Testing Symp.
• Nicolas Houarche, Alejandro Czutro, Mariane Comte, Piet Engelke, Ilia Polian, Bernd Becker, Michel Renovell
  An Electrical Model for the Fault Simulation of Small-Delay Faults Caused by Crosstalk Aggravated Resistive Short Defects
  2009 VLSI Test Symp.
• Nicolas Houarche, Alejandro Czutro, Mariane Comte, Piet Engelke, Ilia Polian, Bernd Becker, Michel Renovell
  Deriving an Electrical Model for Delay Faults Caused by Crosstalk Aggravated Resistive Short Defects
  2009 Latin-American Test Workshop
• Alejandro Czutro, Bernd Becker, Ilia Polian
  Performance Evaluation of SAT-Based Automatic Test Pattern Generation on Multi-Core Architectures
  2009 GI/ITG Int'l Conf. on Architecture of Computing Systems, Many-Cores Workshop
• Alejandro Czutro, Bernd Becker, Ilia Polian
  Performance Evaluation of SAT-Based ATPG on Multi-Core Architectures
  2009 GI/ITG Workshop “Testmethoden und Zuverlässigkeit von Schaltungen und Systemen”
• Alejandro Czutro, Ilia Polian, Matthew Lewis, Piet Engelke, Sudhakar M. Reddy, Bernd Becker
  TIGUAN: Thread-parallel Integrated test pattern Generator Utilizing satisfiability ANalysis
  2009 Int'l Conf. on VLSI Design, pages: 227 - 232

2008

 back to the year overview

• Alejandro Czutro, Nicolas Houarche, Piet Engelke, Ilia Polian, Mariane Comte, Michel Renovell, Bernd Becker
  A Simulator of Small-Delay Faults Caused by Resistive-Open Defects
  2008 IEEE European Test Symp., pages: 113 - 118
• Alejandro Czutro, Ilia Polian, Matthew Lewis, Piet Engelke, Sudhakar M. Reddy, Bernd Becker
  TIGUAN: Thread-parallel Integrated test pattern Generator Utilizing satisfiability ANalysis
  2008 edaWorkshop

2007

 back to the year overview

• Ilia Polian, Alejandro Czutro, Sandip Kundu, Bernd Becker
  Power Droop Testing
  2007 Test of Computers, volume: 24, issue: 3, pages: 276 - 284

2006

 back to the year overview

• Ilia Polian, Alejandro Czutro, Sandip Kundu, Bernd Becker
  Power Droop Testing
  2006 Int'l Conf. on Computer Design, pages: 243 - 250

2005

 back to the year overview

• Ilia Polian, Alejandro Czutro, Bernd Becker
  Evolutionary Optimization in Code-Based Test Compression
  2005 Conf. on Design, Automation and Test in Europe, pages: 1124 - 1129

2004

 back to the year overview

• Ilia Polian, Bernd Becker, Alejandro Czutro
  Compression Methods for Path Delay Fault Test Pair Sets: A Comparative Study
  2004 IEEE European Test Symp., pages: 263 - 264