Scalable Techniques for Formal Verification

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.

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.

-Provides a tutorial introduction to the state of the art in formal verification;

-Discusses disparate reasoning techniques and how they work with each other in solving different application problems;

-Develops a compositional approach based on symbolic simulation to apply assertional reasoning for verification of operationally modeled sequential programs;

-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;

-Develops an extendible, deductive procedure to compute predicate abstractions, that can be effectively implemented in a theorem prover for proving invariants of reactive systems;

-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.

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.