Principles of Model Checking - ifmo.ru

1 Principles of Model CheckingChristel Baier and Joost-Pieter Katoen The MIT Press | Massachusetts Institute of Technology Cambridge, Massachusetts 02142 | 978-0-262-02649-9 Principles of Model CheckingChristel Baier and Joost-Pieter KatoenPrinciples of Model Checking Baier and Katoen computer science Our growing dependence on increasingly complex computer and software systems necessitates the development of formalisms, techniques, and tools for assessing functional properties of these systems. One such technique that has emerged in the last twenty years is Model Checking , which systematically (and automatically) checks whether a Model of a given system satisfies a desired property such as deadlock freedom, invariants, or request-response properties. This automated technique for verification and debugging has developed into a mature and widely used approach with many applications .

2 Principles of Model Checking offers a comprehensive introduction to Model Checking that is not only a text 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 different classes of properties (including safety and liveness), presents the notion of fairness, and provides automata-based algorithms for these properties. It introduces the temporal logics LTL and CTL, compares them, and covers algorithms for verifying these logics, discussing real-time systems as well as systems subject to random phenomena. Separate chapters treat such efficiency-improving techniques as abstraction and symbolic manipulation. The book includes an extensive set of examples (most of which run through several chapters) and a complete set of basic results accompanied by detailed proofs.

3 Each chapter concludes with a summary, bibliographic notes, and an extensive list of exercises of both practical and theoretical nature. Christel Baier is Professor and Chair for Algebraic and Logical Foundations of Computer Science in the Faculty of Computer Science at the Technical University of Dresden. Joost-Pieter Katoen is Professor at the RWTH Aachen University and leads the Software Modeling and Verification Group within the Department of Computer Science. He is affiliated with the Formal Methods and Tools Group at the University of Twente. This book offers one of the most comprehensive introductions to logic Model Checking techniques available today. The authors 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 of the current state of the art.

4 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 coverage of the state of art in computer-aided verification. With its coverage of timed and probabilistic systems, the reader gets a textbook exposition of some of the most advanced topics in Model - Checking research. Obviously, one cannot expect to 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 UniversityPrinciples of Model CheckingiPrinciples ofModel CheckingChristel BaierJoost-Pieter KatoenThe MIT PressCambridge, MassachusettsLondon, Englandc Massachusetts Institute of TechnologyAll rights reserved.

5 No part of this book may be reproduced in any form by any elec-tronic of mechanical means (including photocopying, recording, or information storageand retrieval) without permission in writing from the Press books may be purchased at special quantity discounts for business or salespromotional use. For information, please to Special Sales Department, The MIT Press, 55 Hayward Street, Cambridge, book was set in Aachen and Dresden by Christel Baier and Joost-Pieter and bound in the United States of of Congress Cataloging-in-Publication DataBaier, of Model Checking / Christel Baier and Joost-Pieter Katoen ; foreword by KimGuldstrand bibliographical references and 978-0-262-02649-9 (hardcover : alk. paper) 1. Computer systems Verification. software Verification. , Joost-Pieter. II. 4 dc22200703760310987654321To Michael, Gerda, Inge, and KarlTo Erna, Fons, Joost, and TomvContentsForewordxiiiPrefacexv1 System CharacteristicsofModelChecking.

6 TheModel-CheckingProcess .. 162 Modelling Concurrent Executions .. Handshaking .. TheState-SpaceExplosionProblem .. Summary .. Exercises .. 823 Linear-Time Deadlock .. Linear-TimeBehavior .. PathsandStateGraph .. Linear-TimeProperties .. TraceEquivalenceandLinear-TimeProperties .. SafetyPropertiesandInvariants .. Fairness .. FairnessConstraints .. FairnessStrategies .. Summary .. Exercises ..1444 Regular AutomataonFiniteWords .. RegularSafetyProperties .. Automata on Infinite Words .. Nondeterministic B uchiAutomata .. Deterministic B uchiAutomata .. Generalized B uchiAutomata .. Model - Checking -RegularProperties .. Summary .. Exercises ..2195 Linear Temporal WeakUntil,Release,andPositiveNormalForm .. LTL Satisfiability and Validity Checking .

7 Summary .. Exercises ..3006 Computation Tree NormalFormsforCTL .. CTLM odelChecking .. BasicAlgorithm .. TheUntilandExistentialAlwaysOperator .. FairnessinCTL .. CounterexamplesandWitnesses .. CounterexamplesinCTL .. SwitchingFunctions .. Ordered Binary Decision Diagrams .. ImplementationofROBDD-BasedAlgorithms .. CTL .. Logic,Expressiveness, CTL Summary ..4337 Equivalences and BisimulationQuotient .. Action-BasedBisimulation .. Bisimulation and CTL Equivalence .. DeterminingtheInitialPartition .. AFirstPartitionRefinementAlgorithm .. AnEfficiencyImprovement .. SimulationEquivalence .. Bisimulation,Simulation,andTraceEquivale nce .. Simulation and CTL Stutter Trace and LTL\ Equivalence .. StutterBisimulation .. Divergence-SensitiveStutterBisimulation .. Stutter Bisimulation and CTL \ Summary.

8 5828 Partial Order DynamicPartialOrderReduction .. ComputingAmpleSets .. StaticPartialOrderReduction .. Summary .. Exercises ..6639 Timed TimeDivergence,Timelock, TCTL Model Checking .. RegionTransitionSystems .. The TCTL Model - Checking Algorithm .. Summary .. Exercises ..74010 Probabilistic .. Reachability Probabilities .. QualitativeProperties .. Probabilistic Computation Tree PCTLM odelChecking .. TheQualitativeFragmentofPCTL .. PCTL and Probabilistic PCTL .. Probabilistic Bisimulation .. Cost-Bounded Reachability .. Markov Decision Processes .. Reachability Probabilities .. PCTLM odelChecking .. LimitingProperties .. Linear-Time Properties and PCTL .. Fairness ..899A Appendix: FrequentlyUsedSymbolsandNotations .. FormalLanguages .. ComputationalComplexity ..925 Bibliography931 Index965 ForewordSociety is increasingly dependent on dedicated computer and software systems to assistus in almost every aspect of daily life.

9 Often we are not even aware that computers andsoftware are involved. Several control functions in modern cars are based on embeddedsoftware solutions, , braking, airbags, cruise control, and fuel injection. Mobile phones,communication systems, medical devices, audio and video systems, and consumer electron-ics in general are containing vast amounts of software. Also transport, production, andcontrol systems are increasingly applying embedded software solutions to gain flexibilityand common pattern is the constantly increasing complexity of systems, a trend which isaccelerated by the adaptation of wired and wireless networked solutions: in a moderncar the control functions are distributed over several processing units communicating overdedicated networks and buses. Yet computer- and software-based solutions are becom-ing ubiquitous and are to be found in several safety-critical systems. Therefore a mainchallenge for the field of computer science is to provide formalisms, techniques, and toolsthat will enable the efficient design of correct and well-functioning systems despite the last two decades or so a very attractive approach toward the correctness ofcomputer-based control systems is that of Model Checking .

10 Model Checking is a formalverification technique which allows for desired behavioral properties of a given system tobe verified on the basis of a suitable Model of the system through systematic inspectionof all states of the Model . The attractiveness of Model Checking comes from the fact thatit is completely automatic , the learning curve for a user is very gentle and that itoffers counterexamples in case a Model fails to satisfy a property serving as indispensabledebugging information. On top of this, the performance of Model - Checking tools has longsince proved mature as witnessed by a large number of successful industrial is my pleasure to recommend the excellent bookPrinciples of Model Checkingby Chris-tel Baier and Joost-Pieter Katoen as the definitive textbook on Model Checking , providingboth a comprehensive and a comprehensible account of this important topic. The bookcontains detailed and complete descriptions of first Principles of classical Linear TemporalLogic (LTL) and Computation Tree Logic (CTL) Model Checking .