The Inverse Method: Parametric Verification of Real-time Embedded Systems

The Inverse Method: Parametric Verification of Real-time Embedded Systems

by
Released March 2013
Publisher(s): Wiley
ISBN: 9781848214477

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to live online training experiences, plus books, videos, and digital content from O’Reilly and nearly 200 trusted publishing partners.

Start your free trial

Book description

This book introduces state-of-the-art verification techniques for real-time embedded systems, based on the inverse method for parametric timed automata. It reviews popular formalisms for the specification and verification of timed concurrent systems and, in particular, timed automata as well as several extensions such as timed automata equipped with stopwatches, linear hybrid automata and affine hybrid automata.

The inverse method is introduced, and its benefits for guaranteeing robustness in real-time systems are shown. Then, it is shown how an iteration of the inverse method can solve the good parameters problem for parametric timed automata by computing a behavioral cartography of the system. Different extensions are proposed particularly for hybrid systems and applications to scheduling problems using timed automata with stopwatches. Various examples, both from the literature and industry, illustrate the techniques throughout the book.

Various parametric verifications are performed, in particular of abstractions of a memory circuit sold by the chipset manufacturer ST-Microelectronics, as well as of the prospective flight control system of the next generation of spacecraft designed by ASTRIUM Space Transportation.

Contents:

1. Parametric Timed Automata.

2. The Inverse Method for Parametric Timed Automata.

3. The Inverse Method in Practice: Application to Case Studies.

4. Behavioral Cartography of Timed Automata.

5. Parameter Synthesis for Hybrid Automata.

6. Application to the Robustness Analysis of Scheduling Problems.

7. Conclusion and Perspectives.

Table of contents

  1. Cover
  2. Contents
  3. Title page
  4. Copyright page
  5. Preface
  6. Acknowledgments
  7. Introduction
    1. I.1. Motivation
    2. I.2. The good parameters problem
    3. I.3. Content and organization of the book
  8. Chapter 1: Parametric Timed Automata
    1. 1.1. Constraints on clocks and parameters
    2. 1.2. Labeled transition systems
    3. 1.3. Timed automata
    4. 1.4. Parametric timed automata
    5. 1.5. Related work
  9. Chapter 2: The Inverse Method for Parametric Timed Automata
    1. 2.1. The inverse problem
    2. 2.2. The inverse method algorithm
    3. 2.3. Variants of the inverse method
    4. 2.4. Related work
  10. Chapter 3: The Inverse Method in Practice: Application to Case Studies
    1. 3.1. IMITATOR
    2. 3.2. Flip-flop
    3. 3.3. SR-Latch
    4. 3.4. AND–OR
    5. 3.5. IEEE 1394 Root Contention Protocol
    6. 3.6. Bounded Retransmission Protocol
    7. 3.7. CSMA/CD protocol
    8. 3.8. The SPSMALL memory
    9. 3.9. Networked automation system
    10. 3.10. Tools related to IMITATOR
  11. Chapter 4: Behavioral Cartography of Timed Automata
    1. 4.1. The behavioral cartography algorithm
    2. 4.2. Properties
    3. 4.3. Case studies
    4. 4.4. Related work
  12. Chapter 5: Parameter Synthesis for Hybrid Automata
    1. 5.1. Hybrid automata with parameters
    2. 5.2. Algorithms for hybrid automata
    3. 5.3. Implementation
    4. 5.4. Discussion
    5. 5.5. Related work
  13. Chapter 6: Application to the Robustness Analysis of Scheduling Problems
    1. 6.1. Preliminaries
    2. 6.2. Scheduling analysis using the inverse method
    3. 6.3. Application to scheduling problems
    4. 6.4. Discussion
    5. 6.5. Related work
  14. Chapter 7: Conclusion and Perspectives
    1. 7.1. Trace-based inverse method and partial orders
    2. 7.2. Preservation of temporal logics
    3. 7.3. Application to other formalisms
  15. Bibliography
  16. Index

Product information

  • Title: The Inverse Method: Parametric Verification of Real-time Embedded Systems
  • Author(s):
  • Release date: March 2013
  • Publisher(s): Wiley
  • ISBN: 9781848214477