5. Principles of Model Checking. Baier_ Joost (2008) (5. Principles of Model Checking. Baier_ Joost (2008).pdf)

Principles of Model CheckingChristel Baier and Joost-Pieter Katoen Our growing dependence on increasingly complex computer and software systems necessitates the development offormalisms, techniques, and tools for assessing functional properties of these systems. One such technique that hasemerged in the last twenty years is model checking, which systematically (and automatically) checks whether a modelof a given system satisfies a desired property such as deadlock freedom, invariants, or request-response properties.

Thisautomated technique for verification and debugging has developed into a mature and widely used approach with manyapplications. Principles of Model Checking offers a comprehensive introduction to model checking that is not only atext suitable for classroom use but also a valuable reference for researchers and practitioners in the field. The book begins with the basic principles for modeling concurrent and communicating systems, introduces differentclasses of properties (including safety and liveness), presents the notion of fairness, and provides automata-basedalgorithms for these properties. It introduces the temporal logics LTL and CTL, compares them, and covers algorithmsfor verifying these logics, discussing real-time systems as well as systems subject to random phenomena. Separatechapters treat such efficiency-improving techniques as abstraction and symbolic manipulation.

The book includes anextensive set of examples (most of which run through several chapters) and a complete set of basic results accompaniedby detailed proofs. Each chapter concludes with a summary, bibliographic notes, and an extensive list of exercises ofboth practical and theoretical nature.“This book offers one of the most comprehensive introductions to logic model checking techniques available today.

Theauthors have found a way to explain both basic concepts and foundational theory thoroughly and in crystal-clear prose.Highly recommended for anyone who wants to learn about this important new field, or brush up on their knowledge ofthe current state of the art.” Gerard J. Holzmann, NASA/JPL Laboratory for Reliable Software“Principles of Model Checking, by two principals of model-checking research, offers an extensive and thorough coverageof the state of art in computer-aided verification. With its coverage of timed and probabilistic systems, the reader getsa textbook exposition of some of the most advanced topics in model-checking research. Obviously, one cannot expectto cover this heavy volume in a regular graduate course; rather, one can base several graduate courses on this book,which belongs on the bookshelf of every model-checking researcher.” Moshe Vardi, Director, Computer and Information Technology Institute, Rice University The MIT Press | Massachusetts Institute of Technology Cambridge, Massachusetts 02142 | http://mitpress.mit.edu 978-0-262-02649-9Baier and Katoen Christel Baier is Professor and Chair for Algebraic and Logical Foundations of Computer Science in the Faculty ofComputer Science at the Technical University of Dresden.

Joost-Pieter Katoen is Professor at the RWTH AachenUniversity and leads the Software Modeling and Verification Group within the Department of Computer Science. He isaffiliated with the Formal Methods and Tools Group at the University of Twente.Principles of Model Checking computer sciencePrinciples of Model CheckingChristel Baier and Joost-Pieter KatoenPrinciples of Model CheckingiPrinciples ofModel CheckingChristel BaierJoost-Pieter KatoenThe MIT PressCambridge, MassachusettsLondon, EnglandcMassachusettsInstitute of TechnologyAll rights reserved. No part of this book may be reproduced in any form by any electronic of mechanical means (including photocopying, recording, or information storageand retrieval) without permission in writing from the publisher.MIT Press books may be purchased at special quantity discounts for business or salespromotional use. For information, please email special sales@mitpress.mit.edu orwrite to Special Sales Department, The MIT Press, 55 Hayward Street, Cambridge, MA02142.This book was set in Aachen and Dresden by Christel Baier and Joost-Pieter Katoen.Printed and bound in the United States of America.Library of Congress Cataloging-in-Publication DataBaier, Christel.Principles of model checking / Christel Baier and Joost-Pieter Katoen ; foreword by KimGuldstrand Larsen.p.

cm.Includes bibliographical references and index.ISBN 978-0-262-02649-9 (hardcover : alk. paper) 1. Computer systems–Verification. 2.Computer software–Verification. I.Katoen, Joost-Pieter. II. Title.QA76.76.V47B35 2008004.2’4–dc22200703760310 9 8 7 6 5 4 3 2 1To Michael, Gerda, Inge, and KarlTo Erna, Fons, Joost, and TomvContentsForewordxiiiPrefacexv1 System Verification1.1 Model Checking . .

. . . . . . . . . .1.2 Characteristics of Model Checking .1.2.1 The Model-Checking Process1.2.2 Strengths and Weaknesses . .1.3 Bibliographic Notes . . . . . . . . . .................................................................................17111114162 Modelling Concurrent Systems2.1 Transition Systems . . . . . . . . . . . . . . . . .2.1.1 Executions . . . .

. . . . . . . . . . . . .2.1.2 Modeling Hardware and Software Systems2.2 Parallelism and Communication . . . . . . . . . .2.2.1 Concurrency and Interleaving . . . . . . .2.2.2 Communication via Shared Variables . . .2.2.3 Handshaking . . . . . . . . . . . . . . . .2.2.4 Channel Systems . . .

. . . . . . . . . . .2.2.5 NanoPromela . . . . . . . . . . . . . . . .2.2.6 Synchronous Parallelism . . . . . . . . . .2.3 The State-Space Explosion Problem . . . . . . .2.4 Summary . . . . . . . . . . . . . . . . . . . . . .2.5 Bibliographic Notes . . . . . . . . . . . . . . . . .2.6 Exercises . . . . . .

. . . . . . . . . . . . . . . ...................................................................................................................................................................................................................1919242635363947536375778080823 Linear-Time Properties3.1 Deadlock . . . . . . . . .

. . .3.2 Linear-Time Behavior . . . . .3.2.1 Paths and State Graph3.2.2 Traces . . . . . . . . . .3.2.3 Linear-Time Properties...........................................................................8989949597100...............vii.................................................................viiiCONTENTS3.33.43.53.63.73.83.2.4 Trace Equivalence and Linear-Time PropertiesSafety Properties and Invariants . .

. . . . . . . . . .3.3.1 Invariants . . . . . . . . . . . . . . . . . . . . .3.3.2 Safety Properties . . . . . . . . . . . . . . . . .3.3.3 Trace Equivalence and Safety Properties . . . .Liveness Properties . . . . . . . . . . . . . . . . . . . .3.4.1 Liveness Properties . . . . . . . .

. . . . . . . .3.4.2 Safety vs. Liveness Properties . . . . . . . . . .Fairness . . . . . . . . . . . . . . . . . . . . . . . . . .3.5.1 Fairness Constraints . . . . . . . . . . . . . . .3.5.2 Fairness Strategies . . . . . . . . . . . . . . . .3.5.3 Fairness and Safety . . . . . . . .

. . . . . . . .Summary . . . . . . . . . . . . . . . . . . . . . . . . .Bibliographic Notes . . . . . . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . .4 Regular Properties4.1 Automata on Finite Words . .

. . . . . . .4.2 Model-Checking Regular Safety Properties .4.2.1 Regular Safety Properties . . . . . .4.2.2 Verifying Regular Safety Properties .4.3 Automata on Infinite Words . . . . . . . . .4.3.1 ω-Regular Languages and Properties4.3.2 Nondeterministic Büchi Automata .4.3.3 Deterministic Büchi Automata . . .4.3.4 Generalized Büchi Automata . .

. .4.4 Model-Checking ω-Regular Properties . . .4.4.1 Persistence Properties and Product .4.4.2 Nested Depth-First Search . . . . . .4.5 Summary . . . . . . . . . . . . . . . . . . .4.6 Bibliographic Notes . . . . . . . . . . . . . .4.7 Exercises . . . . . . . . . . . . . . . . . . ..............................................5 Linear Temporal Logic5.1 Linear Temporal Logic . .

. . . . . . . . . . . . .5.1.1 Syntax . . . . . . . . . . . . . . . . . . . .5.1.2 Semantics . . . . . . . . . . . . . . . . . .5.1.3 Specifying Properties . . . . . . . . . . . .5.1.4 Equivalence of LTL Formulae . . . . . . .5.1.5 Weak Until, Release, and Positive Normal5.1.6 Fairness in LTL . . . . . . . .

. . . . . . .5.2 Automata-Based LTL Model Checking . . . . . ............................................................................. . . .. . . .. . . .. . . .. . . .Form. . . .. . . ............................................................................................................................................................................................................................................................................................................................................................................................................104107107111116120121122126129137139141143144...............151151159159163170170173188192198199203217218219........229229231235239247252257270CONTENTS5.35.45.5ix5.2.1 Complexity of the LTL Model-Checking Problem5.2.2 LTL Satisfiability and Validity Checking .

. . . .Summary . . . . . . . . . . . . . . . . . . . . . . . . . .Bibliographic Notes . . . . . . . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . ........................................................2872962982993006 Computation Tree Logic6.1 Introduction . . . .