Model checking is a technique for verifying finite state concurrent systems such as sequential circuit designs and communication protocols. It has a number of advantages over traditional approaches that are based on simulation, testing, and deductive reasoning. In particular, model checking is automatic and usually quite fast. Also, if the design contains an error, model checking will produce a counterexample that can be used to pinpoint the source of the error. The method, which was awarded the 1998 ACM Paris Kanellakis Award for Theory and Practice, has been used successfully in practice to verify real industrial designs, and companies are beginning to market commercial model checkers.
The main challenge in model checking is dealing with the state space explosion problem. This problem occurs in systems with many components that can interact with each other or systems with data structures that can assume many different values. In such cases the number of global states can be enormous. Researchers have made considerable progress on this problem over the last ten years.
This is the first comprehensive presentation of the theory and practice of model checking. The book, which includes basic as well as state-of-the-art techniques, algorithms, and tools, can be used both as an introduction to the subject and as a reference for researchers.
About the Authors
Edmund M. Clarke, a pioneer of the automated method called Model Checking, is FORE Systems Professor of Computer Science and Professor of Electrical and Computer Engineering at Carnegie Mellon University, and a winner of the 2007 Turing Award given by the Association for Computing Machinery.
Doron Peled is Professor of Computer Science at the University of Warwick, Coventry, UK.
“This is the first comprehensive textbook on model checking authored by researchers who have considerably contributed to its theoretical foundations as well as to its acceptance as the main industrial verification technique. This publication offers an excellent introduction and provides good coverage of the state of the art on model checking. I believe it is timely for students, practitioners, researchers, and teachers who are interested in theoretical and practical aspects of verification.”
—Joseph Sifakis, Director of Verimag
“This book is a well-organized and highly readable treatment of all the major topics relating to model checking. It is the first to bring together such a wide range of materials on the subject, and is essential reading for anyone interested in formal verification.”
—Ken McMillan, Cadence Berkeley Laboratories
“Model checking is a revolutionary approach to the design-validation problem. This book, by three leading researchers in algorithmic verification, is the first lengthy exposition of this important technology. It is guaranteed to become a standard reference for years to come.”
—Moshe Y. Vardi, Department of Computer Science, Rice University
“Model Checking is bound to be the pre-eminent source for research, teaching, and industrial practice on this important subject. The authors include the foremost experts. This is the first truly comprehensive treatment of a line of research that has gone from conception to industrial practice in only two decades.”
—R. P. Kurshan, Distinguished Member Technical Staff, Bell Laboratories