In Test Pattern Generation using Boolean Proof Engines, we give an introduction to ATPG. The basic concept and classical ATPG algorithms are reviewed. Then, the formulation as a SAT problem is considered. As the underlying engine, modern SAT solvers and their use on circuit related problems are comprehensively discussed. Advanced techniques for SAT-based ATPG are introduced and evaluated in the context of an industrial environment. The chapters of the book cover efficient instance generation, encoding of multiple-valued logic, usage of various fault models, and detailed experiments on multi-million gate designs. The book describes the state of the art in the field, highlights research aspects, and shows directions for future work.
This book provides an overview of automatic test pattern generation (ATPG) and introduces novel techniques to complement classical ATPG, based on Boolean Satisfiability (SAT). A fast and highly fault efficient SAT-based ATPG framework is presented which is also able to generate high-quality delay tests such as robust path delay tests, as well as tests with long propagation paths to detect small delay defects. The aim of the techniques and methodologies presented in this book is to improve SAT-based ATPG, in order to make it applicable in industrial practice. Readers will learn to improve the performance and robustness of the overall test generation process, so that the ATPG algorithm reliably will generate test patterns for most targeted faults in acceptable run time to meet the high fault coverage demands of industry. The techniques and improvements presented in this book provide the following advantages: Provides a comprehensive introduction to test generation and Boolean Satisfiability (SAT); Describes a highly fault efficient SAT-based ATPG framework; Introduces circuit-oriented SAT solving techniques, which make use of structural information and are able to accelerate the search process significantly; Provides SAT formulations for the prevalent delay faults models, in addition to the classical stuck-at fault model; Includes an industrial perspective on the state-of-the-art in the testing, along with SAT; two topics typically distinguished from each other.
This book introduces several novel approaches to pave the way for the next generation of integrated circuits, which can be successfully and reliably integrated, even in safety-critical applications. The authors describe new measures to address the rising challenges in the field of design for testability, debug, and reliability, as strictly required for state-of-the-art circuit designs. In particular, this book combines formal techniques, such as the Satisfiability (SAT) problem and the Bounded Model Checking (BMC), to address the arising challenges concerning the increase in test data volume, as well as test application time and the required reliability. All methods are discussed in detail and evaluated extensively, while considering industry-relevant benchmark candidates. All measures have been integrated into a common framework, which implements standardized software/hardware interfaces.
This book describes reliable and efficient design automation techniques for the design and implementation of an approximate computing system. The authors address the important facets of approximate computing hardware design - from formal verification and error guarantees to synthesis and test of approximation systems. They provide algorithms and methodologies based on classical formal verification, synthesis and test techniques for an approximate computing IC design flow. This is one of the first books in Approximate Computing that addresses the design automation aspects, aiming for not only sketching the possibility, but providing a comprehensive overview of different tasks and especially how they can be implemented.
This book constitutes the refereed proceedings of the 16th International Conference on Theory and Applications of Satisfiability Testing, SAT 2013, held in Helsinki, Finland in July 2013. The 21 regular papers, 5 short papers, and 5 tool papers presented together with 3 invited talks were carefully reviewed and selected from 71 submissions (850 regular, 15 short and 16 tool papers). The focus of the papers in on following topics: maximum satisfiability, encodings and applications, solver techniques and algorithms, clique-width and SAT, propositional proof complexity, parameterized complexity.
This book presents 8 papers accompanying the lectures of leading researchers given at the 6th edition of the International School on Formal Methods for the Design of Computer, Communication and Software Systems (SFM 2006). SFM 2006 was devoted to formal techniques for hardware verification and covers several aspects of the hardware design process, including hardware design languages and simulation, property specification formalisms, automatic test pattern generation, symbolic trajectory evaluation, and more.
This carefully edited book contains contributions of prominent and active researchers and scholars in the broadly perceived area of intelligent systems. The book is unique both with respect to the width of coverage of tools and techniques, and to the variety of problems that could be solved by the tools and techniques presented. The editors have been able to gather a very good collection of relevant and original papers by prominent representatives of many areas, relevant both to the theory and practice of intelligent systems, artificial intelligence, computational intelligence, soft computing, and the like. The contributions have been divided into 7 parts presenting first more fundamental and theoretical contributions, and then applications in relevant areas.
What the experts have to say about Model-Based Testing for Embedded Systems: "This book is exactly what is needed at the exact right time in this fast-growing area. From its beginnings over 10 years ago of deriving tests from UML statecharts, model-based testing has matured into a topic with both breadth and depth. Testing embedded systems is a natural application of MBT, and this book hits the nail exactly on the head. Numerous topics are presented clearly, thoroughly, and concisely in this cutting-edge book. The authors are world-class leading experts in this area and teach us well-used and validated techniques, along with new ideas for solving hard problems. "It is rare that a book can take recent research advances and present them in a form ready for practical use, but this book accomplishes that and more. I am anxious to recommend this in my consulting and to teach a new class to my students." —Dr. Jeff Offutt, professor of software engineering, George Mason University, Fairfax, Virginia, USA "This handbook is the best resource I am aware of on the automated testing of embedded systems. It is thorough, comprehensive, and authoritative. It covers all important technical and scientific aspects but also provides highly interesting insights into the state of practice of model-based testing for embedded systems." —Dr. Lionel C. Briand, IEEE Fellow, Simula Research Laboratory, Lysaker, Norway, and professor at the University of Oslo, Norway "As model-based testing is entering the mainstream, such a comprehensive and intelligible book is a must-read for anyone looking for more information about improved testing methods for embedded systems. Illustrated with numerous aspects of these techniques from many contributors, it gives a clear picture of what the state of the art is today." —Dr. Bruno Legeard, CTO of Smartesting, professor of Software Engineering at the University of Franche-Comté, Besançon, France, and co-author of Practical Model-Based Testing
