Model checking of component connectors

Izadi, M. (2011)

Doctoral Thesis

We present a framework for automata theoretic model checking of coordination systems specified in Reo coordination language. To this goal, we introduce Buchi automata of records (BAR) and their augmented version (ABAR) as an operational modeling formalism that covers several intended forms of behavior of Reo connectors, such as fairness, I/O synchronization, and context dependency. To specify the properties to be verified, we introduce an action based linear temporal logic, interpreted over the executions of augmented Buchi automata of records, and show how the formulas can be translated into ABARs. This translation can be done either inductively, or by using an on-the-fly method. To deal with the large state spaces, we show that ABARs can be implemented using ordered binary decision diagrams (OBDD). For this purpose, we also introduce the necessary modifications over the basic model checking algorithm that can be applied directly over OBDD structures. Our implementation and a number of case studies that we carried out show the applicability of our method over large state spaces. We also show that the state explosion problem can be tackled by compositional minimization methods using some suitable equivalence relations. In fact, we show two equivalences that are congruencies with respect to the connector composition operators and such that they both preserves linear time temporal logic properties.

• Symbolic model checking
• Model checking
• Formal verification
• Coordination models
• Compositional minimization
• Component connectors
• Automata theory

• All authors: Izadi, M.
• Supervisor: Arbab, F.; Movaghar, A.
• Co-supervisor: Bonsangue, M.M.
• Qualification: Doctor (dr.)
• Awarding Institution: Faculty of Science, Leiden University
• Date: 2011-11-06
• Title of host publication: IPA Dissertation Series
• Name: 2011-22