Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Formal verification of infinite-state BIP models
 
conference paper

Formal verification of infinite-state BIP models

Bliudze, Simon  
•
Cimatti, Alessandro
•
Jaber, Mohamad
Show more
Finkbeiner, Bernd
•
Pu, Geguang
Show more
2015
Proceedings of the 13th International Symposium on Automated Technology for Verification and Analysis
13th International Symposium on Automated Technology for Verification and Analysis

We propose two expressive and complementary techniques for the verification of safety properties of infinite-state BIP models. Both our techniques deal with the full BIP specification, while the existing approaches impose con- siderable restrictions: they either verify finite-state systems or they do not handle the transfer of data on the interactions and priorities. Firstly, we propose an instantiation of the ESST (Explicit Scheduler Symbolic Thread) framework to verify BIP models. The key insight is to apply symbolic reasoning to analyze the behavior of the system described by the BIP compo- nents, and an explicit-state search to analyze the behavior of the system induced by the BIP interactions and priorities. The combination of symbolic and explicit exploration techniques allow to benefit from abstraction, useful when reasoning about data, and from partial order reduction, useful to mitigate the state space explosion due to concurrency. Secondly, we propose an encoding from a BIP model into a symbolic, infinite- state transition system. This technique allows us to leverage the state of the art verification algorithms for the analysis of infinite-state systems. We implemented both techniques and we evaluated their performance against the existing approaches. The results show the effectiveness of our approaches with respect to the state of the art, and their complementarity for the analysis of safe and unsafe BIP models.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-319-24953-7_25
Author(s)
Bliudze, Simon  
Cimatti, Alessandro
Jaber, Mohamad
Mover, Sergio
Roveri, Marco
Saab, Wajeb  
Qiang, Wang
Editors
Finkbeiner, Bernd
•
Pu, Geguang
•
Zhang, Lijun
Date Issued

2015

Publisher

Springer

Published in
Proceedings of the 13th International Symposium on Automated Technology for Verification and Analysis
ISBN of the book

978-3-319-24952-0

Series title/Series vol.

Lecture Notes in Computer Science; 9364

Volume

9364

Start page

326

Subjects

Formal verification

•

Model Checking

•

BIP

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
RISD  
Event nameEvent placeEvent date
13th International Symposium on Automated Technology for Verification and Analysis

Shanghai, China

October 12–15, 2015

Available on Infoscience
September 9, 2015
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/117734
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés