Structural Invariants for Parametric Verification of Systems with Almost Linear Architectures - IMAG Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2019

Structural Invariants for Parametric Verification of Systems with Almost Linear Architectures

Dorel Marius Bozga
  • Fonction : Auteur
Radu Iosif
  • Fonction : Auteur
Joseph Sifakis
  • Fonction : Auteur

Résumé

We consider concurrent systems consisting of a finite but unknown number of components , that are replicated instances of a given set of finite state automata. The components communicate by executing interactions which are simultaneous atomic state changes of a set of components. We specify both the type of interactions (e.g. rendezvous , broadcast) and the topology (i.e. architecture) of the system (e.g. pipeline, ring) via a decidable interaction logic, which is embedded in the classical weak sequential calculus of one successor (WS1S). Proving correctness of such system for safety properties , such as deadlock freedom or mutual exclusion, requires the inference of an induc-tive invariant that subsumes the set of reachable states and avoids the unsafe states. Our method synthesizes such invariants directly from the formula describing the interactions , without costly fixed point iterations. We applied our technique to the verification of several textbook examples, such as dining philosophers, mutual exclusion protocols and concurrent systems with preemption and priorities.
Fichier principal
Vignette du fichier
draft (1).pdf (262.67 Ko) Télécharger le fichier
Loading...

Dates et versions

hal-02388025 , version 1 (02-12-2019)

Identifiants

  • HAL Id : hal-02388025 , version 1

Citer

Dorel Marius Bozga, Radu Iosif, Joseph Sifakis. Structural Invariants for Parametric Verification of Systems with Almost Linear Architectures. 2019. ⟨hal-02388025⟩
37 Consultations
21 Téléchargements

Partager

Gmail Facebook X LinkedIn More