Principles of the Spin Model Checker

ISBN-13: 9781846287695 / Angielski / Miękka / 2008 / 220 str.

Mordechai Ben-Ari

Opis

Principles of Spin is an introductory book, the only requirement is a background in programming. Spin models are written in the Promela language which is easily learned by students and programmers. Spin is easy to install and use. The Spin model checker is not only a widely used professional tool but it is also a superb tool for teaching important concepts of computer science such as verification, concurrency and nondeterminism. The book introduces Spin-based software that the author has developed for teaching: jSpin - an integrated development environment for Spin; SpinSpider - uses output from Spin to automatically construct state diagrams of concurrent programs; VN is a tool for visualizing nondeterminism. Complete programs will demonstrate each construct and concept and these programs will be available on a companion website.

Spis treści

Foreword.- Preface.- Sequential Programming in PROMELA.- A First Program in PROMELA.- Random Simulation- Data Types.- Operators and Expressions.- Control Statements.- Repetitive Statements.- Jump Statements.- Verification of Sequential Programs.- Assertions.- Verifying a program in Spin.- Concurrency.- Interleaving.- Atomicity.- Interactive Simulation.- Interference between processes.- Sets of Processes.- Interference revisited.- Deterministic Sequences of Statements.- Verification with Assertions.- The critical section problem.- Synchroniztion.- Synchronization by blocking.- Executability of statements.- State transition diagrams.- Atomic sequences of statements.- Semaphores.- Nondeterminism in models of concurrent systems.- Termination of Processes.- Verification with Temporal Logic.- Beyond Assertions.- Introduction to linear temporal logic.- Safety properties.- Liveness properties.- Fairness.- Duality.- Verifying correctness without ghost variables.- Modeling a non-critical section.- Advanced temporal specifications.- Data and Program Structures.- Arrays.- Type Definitions.- The preprocessor.- Inline.- Channels.- Channels in PROMELA.- Rendezvous channels.- Buffered channels.- Checking the content of a channel.- Random receive*.- Sorted send*.- Copying the value of a message*.- Polling*.- Comparing rendezvous and buffered channels.- Nondeterminism*.- Nondeterministic finite automata.- VN: Visualizing Nondeterminism.- NP problems.- Advanced Topics in PROMELA*.- Specifiers for Variables.- Predefined variables.- Priority.- Modeling Exceptions.- Reading from standard input.- Embedded C code.- Advanced Topics in SPIN*.- How SPIN searches the state space.- Optimizing the performances of verifications.- Never claims.- Non-progress cycles.- Case Studies* .- Channels as data structures.- Nondeterministic algorithms.- Modeling a real-time scheduling algorithm.- Fischer’s algorithm.- Modeling distributed systems.- The Chandy-Lamport algorithm for global snapshots.- TheChandy-Lamport snapshot algorithm in PROMELA.- Verification of the snapshot algorithm.- Appendix A: Software Tools.- Appendix B: Links.- References.- Index

Blurb

The Spin model checker is a widely used professional software tool for specifying and verifying concurrent and distributed systems. Models, written in a simple language called Promela, can be simulated randomly or interactively. Spin can generate efficient verifiers that search for a counterexample to correctness specifications applied to a model.

Spin is also a superb tool for teaching important concepts of computer science such as verification, concurrency and nondeterminism. The Promela language is easy to learn, as is the linear temporal logic used for correctness specifications, and the techniques for simulating and verifying models.

Principles of Spin is an introductory book for students and practicing software engineers who wish to learn Promela and Spin. The presentation starts with the verification of sequential programs and proceeds in gradual stages to the verification of concurrent and then distributed programs. Complete programs are used to demonstrate each construct and concept, and the source code of these programs, together with that of longer case studies, are available on the companion website.

The book describes free software that the author has developed: jSpin—an integrated development environment for Spin, SpinSpider—a visualization tool that automatically constructs graphical state diagrams of concurrent programs, and VN—a Spin-based tool for visualizing nondeterminism of finite automata.

Mordechai Ben-Ari is an associate professor in the Department of Science Teaching of the Weizmann Institute of Science. He is the author of numerous textbooks on concurrency, programming languages and logic, and has developed software tools for teaching concurrency. In 2004, Ben-Ari received the ACM/SIGCSE Award for Outstanding Contributions to Computer Science Education.