The Inverse Method: Parametric Verification of Real-time by Etienne André

By Etienne André

This e-book introduces cutting-edge verification thoughts for real-time embedded structures, in accordance with the inverse procedure for parametric timed automata. It reports renowned formalisms for the specification and verification of timed concurrent platforms and, specifically, timed automata in addition to a number of extensions corresponding to timed automata outfitted with stopwatches, linear hybrid automata and affine hybrid automata.
The inverse procedure is brought, and its advantages for ensuring robustness in real-time structures are proven. Then, it truly is proven how an new release of the inverse process can remedy the nice parameters challenge for parametric timed automata by way of computing a behavioral cartography of the procedure. varied extensions are proposed quite for hybrid platforms and purposes to scheduling difficulties utilizing timed automata with stopwatches. numerous examples, either from the literature and undefined, illustrate the suggestions through the book.
Various parametric verifications are played, particularly of abstractions of a reminiscence circuit bought via the chipset producer ST-Microelectronics, in addition to of the potential flight regulate method of the following iteration of spacecraft designed through ASTRIUM area Transportation.

Contents:

1. Parametric Timed Automata.
2. The Inverse process for Parametric Timed Automata.
3. The Inverse procedure in perform: program to Case Studies.
4. Behavioral Cartography of Timed Automata.
5. Parameter Synthesis for Hybrid Automata.
6. software to the Robustness research of Scheduling Problems.
7. end and Perspectives.

About the Authors

Étienne André is affiliate Professor within the Laboratoire d’Informatique de Paris Nord, within the collage of Paris thirteen (Sorbonne Paris Cité) in France. His present examine pursuits concentrate on the verification of real-time systems.
Romain Soulat is presently finishing his PhD on the LSV laboratory at ENS-Cachan in France, targeting the modeling and verification of hybrid temporal systems.

Show description

Read Online or Download The Inverse Method: Parametric Verification of Real-time Unbedded Systems PDF

Similar microprocessors & system design books

Designing Embedded Systems with PIC Microcontrollers: Principles and Applications

This ebook is a hands-on advent to the rules and perform of embedded approach layout utilizing the PIC microcontroller. filled with beneficial examples and illustrations, it offers an in-depth remedy of microcontroller layout, programming in either meeting language and C, and lines complex themes corresponding to networking and real-time working platforms.

Logic and Language Models for Computer Science

This article makes in-depth explorations of a wide diversity of theoretical issues in desktop technological know-how. It plunges into the functions of the summary techniques on the way to confront and handle the skepticism of readers, and instill in them an appreciation for the usefulness of thought. A two-part presentation integrates good judgment and formal language—both with functions.

Extra resources for The Inverse Method: Parametric Verification of Real-time Unbedded Systems

Sample text

1. Principle We introduce in the following the inverse method [AND 09c], which is a solution to the inverse problem stated above. The inverse method consists of generating runs starting from the initial state, and removing states incompatible with the reference values by appropriately refining the current constraint K0 on the parameters. The generation procedure is then restarted until a new incompatible state is produced, and so on, iteratively until no incompatible state is generated. 1. t. t.

Any reader interested in time-abstract bisimulation can refer to, for example [TRI 01]. – The inverse method does not actually preserve properties expressed using the timed CTL (TCTL) logic either. Recall that TCTL [ALU 93a] is a timed extension of CTL to the timed case, allowing to express properties specifying both the branching behavior and interval of time within which events may occur. TCTL properties are not preserved by the inverse method for two reasons. First, TCTL is a timed extension of CTL, based on the branching structure of the system.

7, we present in a graphical way the computation of the successor constraint of a state (q, C). First, C is intersected with the guard g of the transition. Then, the clocks that must be reset by the transition (as in ρ) are projected onto zero. Then, the constraint is intersected with the invariant of the destination location I(q ′ ). Time elapsing is then applied. The resulting constraint C ′ is finally obtained by intersecting again with the invariant of the destination location I(q ′ ). – A step of the semantics of a parametric timed automaton A(K) will be referred to as a symbolic step of A(K).

Download PDF sample

Rated 4.66 of 5 – based on 48 votes