Preimage Computation is a fundamental step in Formal Verification of VLSI designs. Conventional OBDD-based methods for Formal Verification suffer from spatial explosion, since large designs can blow up in terms of memory. On the other hand, SAT/ATPG based methods are less demanding on memory. But the run-time can be huge for these methods, since they must explore an exponential search space. In order to reduce this temporal explosion of SAT/ATPG based methods, efficient learning techniques are needed. Conventional ATPG aims at computing a single solution for its objective. In preimage computation, we must enumerate all solutions for the target state during the search. Similar sub-problems often occur during preimage computation that can be identified by the internal state of the circuit. Therefore, it is highly desirable to learn from these search-states and avoid repeated search of identical solution/conflict subspaces, for better performance. In this thesis, we present a new ZBDD based method to compactly store and efficiently search previously explored search-states. We learn from these search-states and avoid repeating subsets and supersets of previously encountered search spaces. Both solution and conflict subspaces are pruned based on simple set operations using ZBDDs. We integrate our techniques into a PODEM based ATPG engine and demonstrate their efficiency on ISCAS '89 benchmark circuits. Experimental results show that upto 90% of the search-space is pruned due to the proposed techniques and we are able to compute preimages for target states where a state-of-the-art technique fails. / Master of Science

Integrated circuits have traveled a long way from being a general purpose microprocessor to an application specific circuit. It has become an integral part of the modern era of technology that we live in. As the applications and their complexities are increasing rapidly every day, so are the sizes of these circuits. With the increase in the design size, the associated testing effort to verify these designs is also increased. The goal of this thesis is to leverage some of the static analysis techniques to reduce the effort of testing and verification at the register transfer level. Studying a design at register transfer level gives exposure to the relational information for the design which is inaccessible at the structural level. In this thesis, we present a way to generate a Data Dependency Graph and a Control Flow Graph out of a register transfer level description of a circuit description. Next, the generated graphs are used to perform relation mining to improve the test generation process in terms of speed, branch coverage and number of test vectors generated. The generated control flow graph gives valuable information about the flow of information through the circuit design. We are using this information to create a framework to improve the branch reachability analysis mainly in terms of the speed. We show the efficiency of our methods by running them through a suite of ITC'99 benchmark circuits. / Master of Science / In this era of modern technology, digital circuits and microprocessors have become an unavoidable part of everyone’s life. The role of these circuits is becoming more and more critical as they are running a lot of critical services for us. Testing and verifying the design has been a very important aspect in the designing of these circuits. With the increasing number of its applications and the advancement of the technology, the size and complexity of the designs have also increased. It has imposed a need to test the design at a stage when it is easy to test and easy to fix also. There have been a lot of research focused on automatically generating the test pattern at an early stage of development and the work presented in this thesis is an effort to take it one step further in the process. The method proposed in this work is taking advantage of the fact that a design speaks for itself and can give a lot of information if looked at carefully. We present a way to extract important information about the data dependency and its flow through the design. With the help of this information, we are generating relations between the design elements which can aid the test generation process to achieve its goal more efficiently. We are also using this information to help in proving that some part of the design is inaccessible. We show the efficiency of our method by running them through benchmark designs.

Avec l’évolution des technologies vers la haute intégration, il devient de plus en plus difficile de localiser les défaillances fonctionnelles situées dans la partie logique des circuits intégrés. En effet, la résolution spatiale fournie par les techniques actuelles n'est pas suffisante. Pour répondre à cette problématique, cette thèse propose une nouvelle approche qui combine le diagnostic ATPG et les techniques optiques. Cette méthode a fait ses preuves sur de nombreux cas d'analyses pour l'amélioration des rendements de production. La méthode utilisant les techniques optiques statiques et dynamiques, une contribution à l'amélioration de l'utilisation de ces techniques a également été apportée par cette thèse. / Nowadays, with the increasing complexity of new VLSI circuits, currents techniques used for functional logic failure localization reach their limits . To overcome these limitations, a new methodology has been established. This methodology, combines ATPG diagnostic and opticals techniques in order to improve accuracy of fault isolation and defect localization. This work contributes also to improve the use of dynamics and statics opticals techniques.

The ever increasing complexity and size of digital circuits complemented by Deep Sub Micron (DSM) technology trends today pose challenges to the efficient Design For Test (DFT) methodologies. Innovation is required not only in designing the digital circuits, but also in automatic test pattern generation (ATPG) to ensure that the pattern set screens all the targeted faults while still complying with the Automatic Test Equipment (ATE) memory constraints. DSM technology trends push the requirements of ATPG to not only include the conventional static defects but also to include test patterns for dynamic defects. The current industry practices consider test pattern generation for transition faults to screen dynamic defects. It has been observed that just screening for transition faults alone is not sufficient in light of the continuing DSM technology trends. Shrinking technology nodes have pushed DFT engineers to include Small Delay Defect (SDD) test patterns in the production flow. The current industry standard ATPG tools are evolving and SDD ATPG is not the most economical option in terms of both test generation CPU time and pattern volume. New techniques must be explored in order to ensure that a quality test pattern set can be generated which includes patterns for stuck-at, transition and SDD faults, all the while ensuring that the pattern volume remains economical. This thesis explores the use of a “Top-Off” ATPG methodology to generate an optimal test pattern set which can effectively screen the required fault models while containing the pattern volume within a reasonable limit.

Process variations is one of the most challenging phenomena in deep submicron. Delay fault testing becomes more complicated because gate delays are not fixed but instead, they are statistical quantities due to the variations in the transistor characteristics. On the other hand, testing for hardware Trojan is also challenging in the presence of process variations because it can easily mask the impact of the inserted Trojan. This work consists of two parts. In the first part, an approach to detect ultra-low-power no-payload Trojans by analyzing IDDT waveforms at each gate in the presence of process variations is presented. The approach uses a novel ATPG to insert a small number of current sensors to analyze the behavior of individual gates at the IDDT waveform. The second part focuses on identifying a test set that maximizes the defect coverage for path delay fault. The proposed approach utilizes Monte-Carlo simulation efficiently and uses a machine-learning algorithm to select a small test set with high detect coverage.

Manufacturers of digital circuits test their products to find defective parts so they are not sold to customers. Despite extensive testing, some of their products that are defective pass the testing process. To combat this problem, manufacturers have developed a metric called defective part level. This metric measures the percentage of parts that passed the testing that are actually defective. While this is useful for the manufacturer, the customer would like to know how long it will take for a manufacturing defect to affect circuit operation. In order for a defect to be detected during circuit operation, it must be excited and observed at the same time. This research shows the correlation between defect detection during automatic test pattern generation (ATPG) testing and normal operation for both combinational and sequential circuits. This information is then used to formulate a mathematical model to predict the expected latency to failure due to manufacturing defects.

Test power is an important issue in deep submicron semiconductor testing. Too much power supply noise and too much power dissipation can result in excessive temperature rise, both leading to overkill during delay test. Scan-based test has been widely adopted as one of the most commonly used VLSI testing method. The test power during scan testing comprises shift power and capture power. The power consumed in the shift cycle dominates the total power dissipation. It is crucial for IC manufacturing companies to achieve near constant power consumption for a given timing window in order to keep the chip under test (CUT) at a near constant temperature, to make it easy to characterize the circuit behavior and prevent delay test over kill. To achieve constant test power, first, we built a fast and accurate power model, which can estimate the shift power without logic simulation of the circuit. We also proposed an efficient and low power X-bit Filling process, which could potentially reduce both the shift power and capture power. Then, we introduced an efficient test pattern reordering algorithm, which achieves near constant power between groups of patterns. The number of patterns in a group is determined by the thermal constant of the chip. Experimental results show that our proposed power model has very good correlation. Our proposed X-Fill process achieved both minimum shift power and capture power. The algorithm supports multiple scan chains and can achieve constant power within different regions of the chip. The greedy test pattern reordering algorithm can reduce the power variation from 29-126 percent to 8-10 percent or even lower if we reduce the power variance threshold. Excessive noise can significantly affect the timing performance of Deep Sub-Micron (DSM) designs and cause non-trivial additional delay. In delay test generation, test compaction and test fill techniques can produce excessive power supply noise. This can result in delay test overkill. Prior approaches to power supply noise aware delay test compaction are too costly due to many logic simulations, and are limited to static compaction. We proposed a realistic low cost delay test compaction flow that guardbands the delay using a sequence of estimation metrics to keep the circuit under test supply noise more like functional mode. This flow has been implemented in both static compaction and dynamic compaction. We analyzed the relationship between delay and voltage drop, and the relationship between effective weighted switching activity (WSA) and voltage drop. Based on these correlations, we introduce the low cost delay test pattern compaction framework considering power supply noise. Experimental results on ISCAS89 circuits show that our low cost framework is up to ten times faster than the prior high cost framework. Simulation results also verify that the low cost model can correctly guardband every path‟s extra noise-induced delay. We discussed the rules to set different constraints in the levelized framework. The veto process used in the compaction can be also applied to other constraints, such as power and temperature.

Manufacturers of digital circuits test their products to find defective parts so they are not sold to customers. Despite extensive testing, some of their products that are defective pass the testing process. To combat this problem, manufacturers have developed a metric called defective part level. This metric measures the percentage of parts that passed the testing that are actually defective. While this is useful for the manufacturer, the customer would like to know how long it will take for a manufacturing defect to affect circuit operation. In order for a defect to be detected during circuit operation, it must be excited and observed at the same time. This research shows the correlation between defect detection during automatic test pattern generation (ATPG) testing and normal operation for both combinational and sequential circuits. This information is then used to formulate a mathematical model to predict the expected latency to failure due to manufacturing defects.

The testability of integrated circuits becomes worse with transistor dimensions reaching nanometer scales. Testing, the process of ensuring that circuits are fabricated without defects, becomes inevitably part of the design process; a technique called design for test (DFT). Asynchronous circuits have a number of desirable properties making them suitable for the challenges posed by modern technologies, but are severely limited by the unavailability of EDA tools for DFT and automatic test-pattern generation (ATPG). This thesis is motivated towards developing test generation methodologies for asynchronous circuits. In total four methods were developed which are aimed at two different fault models: stuck-at faults at the basic logic gate level and transistor-level faults. The methods were evaluated using a set of benchmark circuits and compared favorably to previously published work. First, ABALLAST is a partial-scan DFT method adapting the well-known BALLAST technique for asynchronous circuits where balanced structures are used to guide the selection of the state-holding elements that will be scanned. The test inputs are automatically provided by a novel test pattern generator, which uses time frame unrolling to deal with the remaining, non-scanned sequential C-elements. The second method, called AGLOB, uses algorithms from strongly-connected components in graph graph theory as a method for finding the optimal position of breaking the loops in the asynchronous circuit and adding scan registers. The corresponding ATPG method converts cyclic circuits into acyclic for which standard tools can provide test patterns. These patterns are then automatically converted for use in the original cyclic circuits. The third method, ASCP, employs a new cycle enumeration method to find the loops present in a circuit. Enumerated cycles are then processed using an efficient set covering heuristic to select the scan elements for the circuit to be tested.Applying these methods to the benchmark circuits shows an improvement in fault coverage compared to previous work, which, for some circuits, was substantial. As no single method consistently outperforms the others in all benchmarks, they are all valuable as a designer’s suite of tools for testing. Moreover, since they are all scan-based, they are compatible and thus can be simultaneously used in different parts of a larger circuit. In the final method, ATRANTE, the main motivation of developing ATPG is supplemented by transistor level test generation. It is developed for asynchronous circuits designed using a State Transition Graph (STG) as their specification. The transistor-level circuit faults are efficiently mapped onto faults that modify the original STG. For each potential STG fault, the ATPG tool provides a sequence of test vectors that expose the difference in behavior to the output ports. The fault coverage obtained was 52-72 % higher than the coverage obtained using the gate level tests. Overall, four different design for test (DFT) methods for automatic test pattern generation (ATPG) for asynchronous circuits at both gate and transistor level were introduced in this thesis. A circuit extraction method for representing the asynchronous circuits at a higher level of abstraction was also implemented. Developing new methods for the test generation of asynchronous circuits in this thesis facilitates the test generation for asynchronous designs using the CAD tools available for testing the synchronous designs. Lessons learned and the research questions raised due to this work will impact the future work to probe the possibilities of developing robust CAD tools for testing the future asynchronous designs.

O projeto, seja ele de software ou hardware, envolve uma série de atividades que, apesar das técnicas, ferramentas e métodos empregados, não estão livres de erros que podem levar ao mau funcionamento do produto final. Estes erros podem ocorrer durante a especificação do projeto, como também em estágios finais do desenvolvimento ou no processo de manufatura. A fim de minimizar prejuízos é necessário garantir a qualidade do sistema a partir da verificação do projeto, da validação de protótipo e do teste de fabricação. Por muito tempo o teste de hardware e o teste de software foram estudados como disciplinas completamente independentes. Porém, similaridades entre o desenvolvimento de software e o projeto de hardware já foram exploradas com sucesso em adaptações de técnicas originalmente desenvolvidas para um sendo utilizadas por outro. Um exemplo é a cobertura de código, que foi inicialmente desenvolvida para o teste de software, e agora é comumente utilizada na verificação de hardware. Visto que dispositivos são descritos em linguagem de descrição de hardware, e estas possuem características semelhantes às linguagens de programação, parece uma boa alternativa valer-se desta semelhança para utilizar os métodos propostos pela engenharia de software para garantir a qualidade do hardware desenvolvido. Utilizar tais métodos para gerar padrões de teste para dispositivos de hardware descritos em HDL (Hardware Description Language) e identificar nestas descrições características que, alteradas, aumentem a testabilidade dos mesmos, são os principais objetivos desta tese. / Both software and hardware designs require several tasks to increase reliability and ensure high quality of the final system. Although different techniques, tools and methods can be applied, error free products are difficult to be achieved. Errors may occur on design specification, on development stages and also during manufacturing process. To increase system quality and minimize costs it is mandatory to perform design verification, prototype validation and manufacturing test. For a long time hardware and software tests were studied as disciplines completely apart. However, similarities between software development and hardware design have already been explored successfully by adapting techniques originally developed for one of them, and applying to the other. For instance, code coverage concept and methods were firstly developed for software testing, but nowadays are commonly used in hardware verification. Due to the high similarity observed between software programming languages and hardware description languages (HDL), it seems to be a valuable approach applying software engineering techniques to help ensuring a high quality hardware device. Therefore, the main purpose of this thesis is to use such techniques to extract test patterns from HDL descriptions of hardware devices and to identify at these descriptions means to increase hardware testability.