Temporal Verification of Reactive Systems
Safety
Published on 4. August 1995
Book
Hardback
XVIII, 512 pages
978-0-387-94459-3 (ISBN)
Description
This book is about the verification of reactive systems. A reactive system is a system that maintains an ongoing interaction with its environment, as opposed to computing some final value on termination. The family of reactive systems includes many classes of programs whose correct and reliable construction is con sidered to be particularly challenging, including concurrent programs, embedded and process control programs, and operating systems. Typical examples of such systems are an air traffic control system, programs controlling mechanical devices such as a train, or perpetually ongoing processes such as a nuclear reactor. With the expanding use of computers in safety-critical areas, where failure is potentially disastrous, correctness is crucial. This has led to the introduction of formal verification techniques, which give both users and designers of software and hardware systems greater confidence that the systems they build meet the desired specifications. Framework The approach promoted in this book is based on the use of temporal logic for specifying properties of reactive systems, and develops an extensive verification methodology for proving that a system meets its temporal specification. Reactive programs must be specified in terms of their ongoing behavior, and temporal logic provides an expressive and natural language for specifying this behavior. Our framework for specifying and verifying temporal properties of reactive systems is based on the following four components: 1. A computational model to describe the behavior of reactive systems. The model adopted in this book is that of a Fair Transition System (FTS).
More details
Edition
1995 ed.
Language
English
Place of publication
New York
United States
Target group
Professional and scholarly
Research
Illustrations
XVIII, 512 p.
Dimensions
Height: 260 mm
Width: 183 mm
Thickness: 35 mm
Weight
1192 gr
ISBN-13
978-0-387-94459-3 (9780387944593)
DOI
10.1007/978-1-4612-4222-2
Schweitzer Classification
Other editions
Additional editions
Book
08/2012
Springer
€117.69
Shipment within 15-20 days
Content
0: Preliminary Concepts.- 0.1 Fair Transition System.- 0.2 A Programming Language (SPL): Syntax.- 0.3 A Programming Language (SPL): Semantics.- 0.4 Modules.- 0.5 Temporal Logic.- 0.6 Specification of Properties.- 0.7 Overview of the Verification Framework.- Problems.- Bibliographic Remarks.- 1: Invariance: Proof Methods.- 1.1 Preliminary Notions.- 1.2 Invariance Rule.- 1.3 Finding Inductive Assertions: The Bottom-Up Approach.- 1.4 Finding Inductive Assertions: The Top-Down Approach.- 1.5 Refining Invariants.- Problems.- Bibliographic Remarks.- 2: Invariance: Applications.- 2.1 Parameterized Programs.- 2.2 Single-Resource Allocation.- 2.3 Multiple-Resource Allocation.- 2.4 Constructing Linear Invariants.- 2.5 Completeness.- 2.6 Finite-State Algorithmic Verification.- Problems.- Bibliographic Remarks.- 3: Precedence.- 3.1 Waiting-for Rule.- 3.2 Nested Waiting-for Rule.- 3.3 Verification Diagrams.- 3.4 Overtaking Analysis for a Resource Allocator.- * 3.5 Completeness.- * 3.6 Finite-State Algorithmic Verification.- Problems.- Bibliographic Remarks.- 4: General Safety.- 4.1 Invariance Rule for Past Formulas.- 4.2 Applications of the Past Invariance Rule.- 4.3 Compositional Verification.- 4.4 Causality Rule.- 4.5 Backward Analysis.- 4.6 Order-Preservation Properties.- 4.7 History Variables.- 4.8 Back-to Rule.- * 4.9 Completeness.- * 4.10 Finite-State Algorithmic Verification.- Problems.- Bibliographic Remarks.- 5: Algorithmic Verification of General Formulas.- 5.1 Satisfiability of a Temporal Formula.- 5.2 Satisfiability over a Finite-State Program.- 5.3 Validity over a Finite-State Program: Examples.- 5.4 Incremental Tableau Construction.- 5.5 Particle Tableaux.- Problems.- Bibliographic Remarks.- References.- Index to Symbols.- General Index.