TY - BOOK A1 - Dyck, Johannes A1 - Giese, Holger T1 - k-Inductive invariant checking for graph transformation systems N2 - While offering significant expressive power, graph transformation systems often come with rather limited capabilities for automated analysis, particularly if systems with many possible initial graphs and large or infinite state spaces are concerned. One approach that tries to overcome these limitations is inductive invariant checking. However, the verification of inductive invariants often requires extensive knowledge about the system in question and faces the approach-inherent challenges of locality and lack of context. To address that, this report discusses k-inductive invariant checking for graph transformation systems as a generalization of inductive invariants. The additional context acquired by taking multiple (k) steps into account is the key difference to inductive invariant checking and is often enough to establish the desired invariants without requiring the iterative development of additional properties. To analyze possibly infinite systems in a finite fashion, we introduce a symbolic encoding for transformation traces using a restricted form of nested application conditions. As its central contribution, this report then presents a formal approach and algorithm to verify graph constraints as k-inductive invariants. We prove the approach's correctness and demonstrate its applicability by means of several examples evaluated with a prototypical implementation of our algorithm. N2 - Während Graphtransformationssysteme einerseits einen ausdrucksstarken Formalismus bereitstellen, existieren andererseits nur eingeschränkte Möglichkeiten für die automatische Analyse. Dies gilt insbesondere für die Analyse von Systemen mit einer Vielzahl an initialen Graphen oder mit großen oder unendlichen Zustandsräumen. Ein möglicher Ansatz, um diese Einschränkungen zu umgehen, sind induktive Invarianten. Allerdings erfordert die Verifkation induktiver Invarianten oft erweitertes Wissen über das zu verifizierende System; weiterhin muss diese Verifikationstechnik mit den spezifischen Problemen der Lokalität und des Mangels an Kontextwissen umgehen. Dieser Bericht betrachtet k-induktive Invarianten - eine Verallgemeinerung induktiver Invarienten - für Graphtransformationssysteme als einen möglichen Ansatz, um diese Probleme anzugehen. Zusätzliches Kontextwissen, das durch die Analyse mehrerer (k) Schritte gewonnen werden kann, macht den entscheidenden Unterschied zu induktiven Invarianten aus und genügt oft, um die gewünschten Invarianten ohne die iterative Entwicklung zusätzlicher Eigenschaften zu verifizieren. Um unendliche Systeme in endlicher Zeit zu analysieren, führen wir eine symbolische Kodierung von Transformationssequenzen ein, die auf verschachtelten Anwendungsbedingungen basiert. Unser zentraler Beitrag ist dann ein formaler Ansatz und Algorithmus zur Verifikation von Graphbedingungen als k-induktive Invarianten. Wir führen einen formalen Beweis, um die Korrektheit unseres Verfahrens nachzuweisen, und demonstrieren die Anwendbarkeit des Verfahrens an mehreren Beispielen, die mit einer prototypischen Implementierung verifiziert wurden. T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 119 KW - formal verification KW - static analysis KW - graph transformation KW - typed graph transformation systems KW - graph constraints KW - nested application conditions KW - k-inductive invariants KW - k-induction KW - k-inductive invariant checking KW - transformation sequences KW - s/t-pattern sequences KW - formale Verifikation KW - statische Analyse KW - Graphtransformationen KW - Graphtransformationssysteme KW - Graphbedingungen KW - verschachtelte Anwednungsbedingungen KW - k-induktive Invarianten KW - k-Induktion KW - k-induktives Invariant-Checking KW - Transformationssequenzen KW - Sequenzen von s/t-Pattern Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-397044 SN - 978-3-86956-406-7 SN - 1613-5652 SN - 2191-1665 IS - 119 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - BOOK A1 - Dyck, Johannes A1 - Giese, Holger T1 - Inductive invariant checking with partial negative application conditions N2 - Graph transformation systems are a powerful formal model to capture model transformations or systems with infinite state space, among others. However, this expressive power comes at the cost of rather limited automated analysis capabilities. The general case of unbounded many initial graphs or infinite state spaces is only supported by approaches with rather limited scalability or expressiveness. In this report we improve an existing approach for the automated verification of inductive invariants for graph transformation systems. By employing partial negative application conditions to represent and check many alternative conditions in a more compact manner, we can check examples with rules and constraints of substantially higher complexity. We also substantially extend the expressive power by supporting more complex negative application conditions and provide higher accuracy by employing advanced implication checks. The improvements are evaluated and compared with another applicable tool by considering three case studies. N2 - Graphtransformationssysteme stellen ein ausdrucksstarkes formales Modell zur Verfügung, um Modelltransformationen und Systeme mit unendlichem Zustandsraum zu beschreiben. Allerdings sorgt diese Ausdrucksstärke für signifikante Einschränkungen bei der automatischen Analyse. Ansätze, die die Analyse allgemeiner Systeme mit unendlichem Zustandsraum oder beliebig vielen initialen Graphen unterstützen, sind in ihrer Skalierbarkeit oder Ausdrucksstärke stark eingeschränkt. In diesem Bericht beschreiben wir Verbesserungen eines existierenden Ansatzes für die automatische Verifikation induktiver Invarianten in Graphtransformationssystemen. Durch die Verwendung partieller negativer Anwendungsbedingungen für die Repräsentation und Überprüfung einer Vielzahl an Bedingungen in kompakterer Form können Regeln und Bedingungen von deutlich höhrerer Komplexität verifiziert werden. Weiterhin wird die Ausdrucksstärke des Ansatzes beträchtlich erhöht, indem die Verwendung komplexerer negativer Anwendungsbedingungen und erweiterter Implikationstests ermöglicht wird. Alle diese Verbesserungen werden evaluiert und mit einem anderen anwendbaren Werkzeug anhand von drei Fallstudien verglichen. T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 98 KW - verification KW - inductive invariant checking KW - graph transformation KW - partial application conditions KW - Verifikation KW - induktives Invariant Checking KW - Graphtransformationen KW - partielle Anwendungsbedingungen Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-77748 SN - 978-3-86956-333-6 SN - 1613-5652 SN - 2191-1665 IS - 98 PB - Universitätsverlag Potsdam CY - Potsdam ER -