Scalable techniques for formal verification

This book is about formal veri?cation, that is, the use of mathematical reasoning to ensure correct execution of computing systems. With the increasing use of c- puting systems in safety-critical and security-critical applications, it is becoming increasingly important for our well-being to ensure that those systems execute c- rectly. Over the last decade, formal veri?cation has made signi?cant headway in the analysis of industrial systems, particularly in the realm of veri?cation of hardware. A key advantage of formal veri?cation is that it provides a mathematical guarantee of their correctness (up to the accuracy of formal models and correctness of r- soning tools). In the process, the analysis can expose subtle design errors. Formal veri?cation is particularly effective in ?nding corner-case bugs that are dif?cult to detect through traditional simulation and testing. Nevertheless, and in spite of its promise, the application of formal veri?cation has so far been limited in an ind- trial design validation tool ?ow. The dif?culties in its large-scale adoption include the following (1) deductive veri?cation using theorem provers often involves - cessive and prohibitive manual effort and (2) automated decision procedures (e. g. , model checking) can quickly hit the bounds of available time and memory. This book presents recent advances in formal veri?cation techniques and d- cusses the applicability of the techniques in ensuring the reliability of large-scale systems. We deal with the veri?cation of a range of computing systems, from - quential programsto concurrentprotocolsand pipelined machines. Front Matter....Pages i-xiv Front Matter....Pages 8-8 Introduction....Pages 1-5 Front Matter....Pages 8-8 Overview of Formal Verification....Pages 9-23 Introduction to ACL2....Pages 25-49 Front Matter....Pages 52-52 Sequential Programs....Pages 53-64 Operational Semantics and Assertional Reasoning....Pages 65-79 Connecting Different Proof Styles....Pages 81-92 Front Matter....Pages 94-94 Reactive Systems....Pages 95-107 Verifying Concurrent Protocols Using Refinements....Pages 109-130 Pipelined Machines....Pages 131-145 Front Matter....Pages 148-148 Invariant Proving....Pages 149-157 Predicate Abstraction via Rewriting....Pages 159-171 Front Matter....Pages 174-174 Integrating Deductive and Algorithmic Reasoning....Pages 175-177 A Compositional Model Checking Procedure....Pages 179-194 Connecting External Deduction Tools with ACL2....Pages 195-216 Front Matter....Pages 218-218 Summary and Conclusion....Pages 219-221 Back Matter....Pages 223-243 This book presents state-of-the-art approaches to formal verification techniques to seamlessly integrate different formal verification methods within a single logical foundation. It should benefit researchers and practitioners looking to get a broad overview of the spectrum of formal verification techniques, as well as approaches to combining such techniques within a single framework. Coverage includes a range of case studies showing how such combination is fruitful in developing a scalable verification methodology for industrial designs. This book outlines both theoretical and practical issues involved in integrating different reasoning methods to work in concert, and current approaches to their resolution This book should benefit researchers and practitioners looking to get a broad overview of the spectrum of formal verification techniques, as well as approaches to combining different techniques within a single framework. The book discusses both theoretical and practical issues involved in integrating different reasoning methods to work in concert, and current approaches to their resolution This book presents state-of-the-art approaches in formal verification and methods to seamlessly integrate different formal verification techniques within a single logical foundation. It demonstrates methods for scaling up formal verification for large-scale computing systems using a mixture of theorem proving and decision procedures -Explores techniques for combining model checking and theorem proving, and the associated logical and engineering challenges. Creates a general interface connecting the ACL2 theorem prover with arbitrary external deduction tools -Formalizes the notion of stuttering trace containment and shows its applicability in reasoning about reactive systems. Shows how to use this notion effectively to verify concurrent protocols and pipelined machines The book assumes no previous knowledge of formal reasoning and logic, and includes several case studies to facilitate appreciation of the diversity of domains in which the techniques can be applied. --Book Jacket -Develops an extendible, deductive procedure to compute predicate abstractions, that can be effectively implemented in a theorem prover for proving invariants of reactive systems -Develops a compositional approach based on symbolic simulation to apply assertional reasoning for verification of operationally modeled sequential programs -Discusses disparate reasoning techniques and how they work with each other in solving different application problems