Sascha Klüppelholz

Verification of Branching-Time and Alternating-Time Properties for Exogenous Coordination Models

Dokumente und Dateien


Bitte nutzen Sie beim Zitieren immer folgende Url:

Kurzfassung in Englisch

Information and communication systems enter an increasing number of areas of daily lives. Our reliance and dependence on the functioning of such systems is rapidly growing together with the costs and the impact of system failures. At the same time the complexity of hardware and software systems extends to new limits as modern hardware architectures become more and more parallel, dynamic and heterogenous. These trends demand for a closer integration of formal methods and system engineering to show the correctness of complex systems within the design phase of large projects.

The goal of this thesis is to introduce a formal holistic approach for modeling, analysis and synthesis of parallel systems that potentially addresses complex system behavior at any layer of the hardware/software stack. Due to the complexity of modern hardware and software systems, we aim to have a hierarchical modeling framework that allows to specify the behavior of a parallel system at various levels of abstraction and that facilitates designing complex systems in an iterative refinement procedure, in which more detailed behavior is added successively to the system description. In this context, the major challenge is to provide modeling formalisms that are expressive enough to address all of the above issues and are at the same time amenable to the application of formal methods for proving that the system behavior conforms to its specification. In particular, we are interested in specification formalisms that allow to apply formal verification techniques such that the underlying model checking problems are still decidable within reasonable time and space bounds.

The presented work relies on an exogenous modeling approach that allows a clear separation of coordination and computation and provides an operational semantic model where formal methods such as model checking are well suited and applicable. The channel-based exogenous coordination language Reo is used as modeling formalism as it supports hierarchical modeling in an iterative top-down refinement procedure. It facilitates reusability, exchangeability, and heterogeneity of components and forms the basis to apply formal verification methods. At the same time Reo has a clear formal semantics based on automata, which serve as foundation to apply formal methods such as model checking.

In this thesis new modeling languages are presented that allow specifying complex systems in terms of Reo and automata models which yield the basis for a holistic approach on modeling, verification and synthesis of parallel systems. The second main contribution of this thesis are tailored branching-time and alternating time temporal logics as well as corresponding model checking algorithms. The thesis includes results on the theoretical complexity of the underlying model checking problems as well as practical results. For the latter the presented approach has been implemented in the symbolic verification tool set Vereofy. The implementation within Vereofy and evaluation of the branching-time and alternating-time model checker is the third main contribution of this thesis.

weitere Metadaten

Reo, RSL, CARML, Vereofy, constraint automata, Verifikation, temporale Logiken, branching time, alternating time, model checking, exogene Koordination, Modellierung, Analyse, parallele Systeme
Reo, RSL, CARML, Vereofy, constraint automata, verification, temporal logics, branching time, alternating time, model checking, exogeneous coordination, modeling, analysis, parallel systems
DDC Klassifikation004
RVK KlassifikationST 136
HochschuleTechnische Universität Dresden
FakultätFakultät Informatik
ProfessurProfessur für Algebraische und logische Grundlagen der Informatik
BetreuerProf. Dr. rer. nat. Christel Baier
GutachterProf. Dr. rer. nat. Christel Baier
Prof. Dr. Farhad Arbab
Tag d. Einreichung (bei der Fakultät)31.01.2012
Tag d. Verteidigung / Kolloquiums / Prüfung19.03.2012
Veröffentlichungsdatum (online)24.04.2012
persistente URNurn:nbn:de:bsz:14-qucosa-86211

Hinweis zum Urheberrecht

Diese Website ist eine Installation von Qucosa - Quality Content of Saxony!
Sächsische Landesbibliothek Staats- und Universitätsbibliothek Dresden