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
Loading...
Thumbnail Image
Name

paper_58.pdf

Type

Postprint

Version

Accepted version

Access type

openaccess

Size

421.09 KB

Format

Adobe PDF

Checksum (MD5)

ada130dd1c3ed5d950d7527a649dbd79

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