TY - BOOK A1 - Krause, Christian A1 - Giese, Holger T1 - Quantitative modeling and analysis of service-oriented real-time systems using interval probabilistic timed automata N2 - One of the key challenges in service-oriented systems engineering is the prediction and assurance of non-functional properties, such as the reliability and the availability of composite interorganizational services. Such systems are often characterized by a variety of inherent uncertainties, which must be addressed in the modeling and the analysis approach. The different relevant types of uncertainties can be categorized into (1) epistemic uncertainties due to incomplete knowledge and (2) randomization as explicitly used in protocols or as a result of physical processes. In this report, we study a probabilistic timed model which allows us to quantitatively reason about nonfunctional properties for a restricted class of service-oriented real-time systems using formal methods. To properly motivate the choice for the used approach, we devise a requirements catalogue for the modeling and the analysis of probabilistic real-time systems with uncertainties and provide evidence that the uncertainties of type (1) and (2) in the targeted systems have a major impact on the used models and require distinguished analysis approaches. The formal model we use in this report are Interval Probabilistic Timed Automata (IPTA). Based on the outlined requirements, we give evidence that this model provides both enough expressiveness for a realistic and modular specifiation of the targeted class of systems, and suitable formal methods for analyzing properties, such as safety and reliability properties in a quantitative manner. As technical means for the quantitative analysis, we build on probabilistic model checking, specifically on probabilistic time-bounded reachability analysis and computation of expected reachability rewards and costs. To carry out the quantitative analysis using probabilistic model checking, we developed an extension of the Prism tool for modeling and analyzing IPTA. Our extension of Prism introduces a means for modeling probabilistic uncertainty in the form of probability intervals, as required for IPTA. For analyzing IPTA, our Prism extension moreover adds support for probabilistic reachability checking and computation of expected rewards and costs. We discuss the performance of our extended version of Prism and compare the interval-based IPTA approach to models with fixed probabilities. N2 - Eine der wichtigsten Herausforderungen in der Entwicklung von Service-orientierten Systemen ist die Vorhersage und die Zusicherung von nicht-funktionalen Eigenschaften, wie Ausfallsicherheit und Verfügbarkeit von zusammengesetzten, interorganisationellen Diensten. Diese Systeme sind oft charakterisiert durch eine Vielzahl von inhärenten Unsicherheiten, welche sowohl in der Modellierung als auch in der Analyse eine Rolle spielen. Die verschiedenen relevanten Arten von Unsicherheiten können eingeteilt werden in (1) epistemische Unsicherheiten aufgrund von unvollständigem Wissen und (2) Zufall als Mittel in Protokollen oder als Resultat von physikalischen Prozessen. In diesem Bericht wird ein probabilistisches, Zeit-behaftetes Modell untersucht, welches es ermöglicht quantitative Aussagen über nicht-funktionale Eigenschaften von einer eingeschränkten Klasse von Service-orientierten Echtzeitsystemen mittels formaler Methoden zu treffen. Zur Motivation und Einordnung wird ein Anforderungskatalog für probabilistische Echtzeitsysteme mit Unsicherheiten erstellt und gezeigt, dass die Unsicherheiten vom Typ (1) und (2) in den untersuchten Systemen einen Ein uss auf die Wahl der Modellierungs- und der Analysemethode haben. Als formales Modell werden Interval Probabilistic Timed Automata (IPTA) benutzt. Basierend auf den erarbeiteten Anforderungen wird gezeigt, dass dieses Modell sowohl ausreichende Ausdrucksstärke für eine realistische und modulare Spezifikation als auch geeignete formale Methoden zur Bestimmung von quantitativen Sicherheits- und Zuverlässlichkeitseigenschaften bietet. Als technisches Mittel für die quantitative Analyse wird probabilistisches Model Checking, speziell probabilistische Zeit-beschränkte Erreichbarkeitsanalyse und Bestimmung von Erwartungswerten für Kosten und Vergütungen eingesetzt. Um die quantitative Analyse mittels probabilistischem Model Checking durchzuführen, wird eine Erweiterung des Prism-Werkzeugs zur Modellierung und Analyse von IPTA eingeführt. Die präsentierte Erweiterung von Prism ermöglicht die Modellierung von probabilistischen Unsicherheiten mittelsWahrscheinlichkeitsintervallen, wie sie für IPTA benötigt werden. Zur Verifikation wird probabilistische Erreichbarkeitsanalyse und die Berechnung von Erwartungswerten durch das Werkzeug unterstützt. Es wird die Performanz der Prism-Erweiterung untersucht und der Intervall-basierte IPTA-Ansatz mit Modellen mit festen Wahrscheinlichkeitswerten verglichen. T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 56 KW - Service-orientierte Systme KW - Echtzeitsysteme KW - Quantitative Analysen KW - Formale Verifikation KW - service-oriented systems KW - real-time systems KW - quantitative analysis KW - formal verification methods Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-57845 SN - 978-3-86956-171-4 PB - Universitätsverlah Potsdam CY - Potsdam ER - TY - JOUR A1 - Buchwald, Sebastian A1 - Wagelaar, Dennis A1 - Dan, Li A1 - Hegedues, Abel A1 - Herrmannsdoerfer, Markus A1 - Horn, Tassilo A1 - Kalnina, Elina A1 - Krause, Christian A1 - Lano, Kevin A1 - Lepper, Markus A1 - Rensink, Arend A1 - Rose, Louis A1 - Waetzoldt, Sebastian A1 - Mazanek, Steffen T1 - A survey and comparison of transformation tools based on the transformation tool contest JF - Science of computer programming N2 - Model transformation is one of the key tasks in model-driven engineering and relies on the efficient matching and modification of graph-based data structures; its sibling graph rewriting has been used to successfully model problems in a variety of domains. Over the last years, a wide range of graph and model transformation tools have been developed all of them with their own particular strengths and typical application domains. In this paper, we give a survey and a comparison of the model and graph transformation tools that participated at the Transformation Tool Contest 2011. The reader gains an overview of the field and its tools, based on the illustrative solutions submitted to a Hello World task, and a comparison alongside a detailed taxonomy. The article is of interest to researchers in the field of model and graph transformation, as well as to software engineers with a transformation task at hand who have to choose a tool fitting to their needs. All solutions referenced in this article provide a SHARE demo. It supported the peer-review process for the contest, and now allows the reader to test the tools online. KW - Graph rewriting KW - Model transformation KW - Tool survey KW - Transformation tool contest Y1 - 2014 U6 - https://doi.org/10.1016/j.scico.2013.10.009 SN - 0167-6423 SN - 1872-7964 VL - 85 SP - 41 EP - 99 PB - Elsevier CY - Amsterdam ER - TY - BOOK A1 - Maximova, Maria A1 - Giese, Holger A1 - Krause, Christian T1 - Probabilistic timed graph transformation systems T1 - Probabilistische zeitbehaftete Graphtransformationssysteme N2 - Today, software has become an intrinsic part of complex distributed embedded real-time systems. The next generation of embedded real-time systems will interconnect the today unconnected systems via complex software parts and the service-oriented paradigm. Therefore besides timed behavior and probabilistic behaviour also structure dynamics, where the architecture can be subject to changes at run-time, e.g. when dynamic binding of service end-points is employed or complex collaborations are established dynamically, is required. However, a modeling and analysis approach that combines all these necessary aspects does not exist so far. To fill the identified gap, we propose Probabilistic Timed Graph Transformation Systems (PTGTSs) as a high-level description language that supports all the necessary aspects of structure dynamics, timed behavior, and probabilistic behavior. We introduce the formal model of PTGTSs in this paper and present a mapping of models with finite state spaces to probabilistic timed automata (PTA) that allows to use the PRISM model checker to analyze PTGTS models with respect to PTCTL properties. N2 - Software gehört heutzutage zu einem wesentlichen Bestandteil von komplexen eingebetteten Echtzeitsystemen. Die nächste Generation von eingebetteten Echtzeitsystemen wird in der Zukunft die bisher nicht verbundenen Systeme durch komplexe Softwarelösungen unter der Verwendung des serviceorientierten Paradigmas verbinden. Deswegen wird neben der Beschreibung des zeitbehafteten und probabilistischen Verhaltens auch die Betrachtung der Strukturdynamik benötigt, um die Modellierung der Architekturänderungen während der Laufzeit zu ermöglichen, wie z. B. die dynamische Anbindung von den Endpunkten der Services oder die dynamische Erstellung der komplexen Kollaborationen. Allerdings gibt es noch keinen Ansatz für die Modellierung und Analyse, der all diese drei notwendigen Aspekte kombiniert. Um die identifizierte Lücke zu schließen, führen wir probabilistische zeitbehaftete Graphtransformationssysteme (kurz PTGTS) ein, die als abstrakte Beschreibungssprache dienen und die notwendigen Aspekte der Strukturdynamik, des zeitbehafteten Verhaltens und des probabilistischen Verhaltens unterstützen. Außerdem stellen wir den Formalismus der probabilistischen zeitbehafteten Graphtransformationssysteme vor und definieren eine Abbildung zwischen den Modellen mit endlichen Zustandsräumen und probabilistischen zeitbehafteten Automaten, die die Nutzung des PRISM Modell-Checkers für die Analyse der PTGTS Modelle in Bezug auf PTCTL Eigenschaften ermöglichen. T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 118 KW - graph transformations KW - probabilistic timed automata KW - PTCTL KW - PRISM model checker KW - HENSHIN KW - Graphtransformationen KW - probabilistische zeitbehaftete Automaten KW - PTCTL KW - PRISM Modell-Checker KW - HENSHIN Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-397055 SN - 978-3-86956-405-0 SN - 1613-5652 SN - 2191-1665 IS - 118 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Maximova, Maria A1 - Giese, Holger A1 - Krause, Christian T1 - Probabilistic timed graph transformation systems JF - Journal of Logical and Algebraic Methods in Programming N2 - Today, software has become an intrinsic part of complex distributed embedded real-time systems. The next generation of embedded real-time systems will interconnect the today unconnected systems via complex software parts and the service-oriented paradigm. Due to these interconnections, the architecture of systems can be subject to changes at run-time, e.g. when dynamic binding of service end-points is employed or complex collaborations are established dynamically. However, suitable formalisms and techniques that allow for modeling and analysis of timed and probabilistic behavior of such systems as well as of their structure dynamics do not exist so far. To fill the identified gap, we propose Probabilistic Timed Graph Transformation Systems (PTGTSs) as a high-level description language that supports all the necessary aspects of structure dynamics, timed behavior, and probabilistic behavior. We introduce the formal model of PTGTSs in this paper as well as present and formally verify a mapping of models with finite state spaces to probabilistic timed automata (PTA) that allows to use the PRISM model checker to analyze PTGTS models with respect to PTCTL properties. (C) 2018 Elsevier Inc. All rights reserved. KW - Graph transformations KW - Probabilistic timed automata KW - PTCTL KW - PRISM model checker KW - HENSHIN Y1 - 2018 U6 - https://doi.org/10.1016/j.jlamp.2018.09.003 SN - 2352-2208 VL - 101 SP - 110 EP - 131 PB - Elsevier CY - New York ER -