Golog is a powerful programming language for logic-based agents. The primitives of the language are actions whose preconditions and effects are defined in a Situation Calculus action theory using first-order logic. To describe possible courses of actions the programmer can freely combine imperative control structures with constructs for non-deterministic choice, leaving it to the system to resolve the non-determinism in a suitable manner. Golog has been successfully used for high-level decision making in the area of cognitive robotics. Obviously, it is important to verify certain properties of a Golog program before executing it on a physical robot. However, due to the high expressiveness of the language the verification problem is in general undecidable. In this thesis, we study the verification problem for Golog programs over actions defined in action languages based on Description Logics and explore the boundary between decidable and undecidable fragments.

Diese Arbeit untersucht den Einfluss von Daten auf das Verhalten und die Korrektheit eines verteilten Systems. Ein verteiltes System besteht aus mehreren Services. Ein Service ist eine selbständige, plattformunabhängige Einheit, die anderen Services eine bestimmte Funktionalität über eine wohldefinierte Schnittstelle zur Verfügung stellt. In dieser Arbeit betrachten wir die Interaktion von jeweils genau zwei Services miteinander. Zwei Services, die erfolgreich miteinander zusammenarbeiten können, nennen wir Partner. Ein Service heißt bedienbar, wenn er mindestens einen Partner hat. Ziel der Arbeit ist es, zu untersuchen, wann zwei Services Partner sind, und für einen Service zu entscheiden, ob dieser bedienbar ist. Aufgrund der Daten kann der Zustandsraum eines Service sehr groß oder sogar unendlich groß werden. Wir untersuchen zwei Klassen von Services mit unendlich vielen Zuständen. Für diese Klassen stellen wir Algorithmen vor, welche zu einem gegebenen Service einen Partner synthetisieren, falls ein solcher existiert. Auf diese Weise entscheiden wir konstruktiv die Bedienbarkeit eines Service. Weiterhin stellen wir Transformationsregeln für Partner vor und untersuchen, wie viel Speicherplatz ein Partner eines Services mindestens benötigt. / This thesis studies the influence of data on the behavior and the correctness of a distributed system. A distributed system consists of several services. A service is a self-contained, platform-independent entity which provides a certain functionality to other services via a well-defined interface.In this thesis, we consider the interaction of exactly two services. Two services that can successfully cooperate with each other are called partners. We call a service controllable, if the service has at least one partner. The goal of this thesis is to study the conditions for which two services are partners and to decide whether a given service is controllable. Due to the data, the state space of a service may be very large or even infinite. We investigate two classes of services with infinitely many states. For these classes, we present algorithms that synthesize a partner of a service, if it exists. This allows us to decide the controllability of a service constructively. Furthermore, we present transformation rules for partners and investigate the minimum amount of memory that a partner of a service needs.

The proper composition of independently developed components of an embedded real- time system is complicated due to the fact that besides the functional behavior also the non-functional properties and in particular the timing have to be compatible. Nowadays related compatibility problems have to be addressed in a cumbersome integration and configuration phase at the end of the development process, that in the worst case may fail. Therefore, a number of formal approaches have been developed, which try to guide the upfront decomposition of the embedded real-time system into components such that integration problems related to timing properties can be excluded and that suitable configurations can be found. However, the proposed solutions require a number of strong assumptions that can be hardly fulfilled or the required analysis does not scale well. In this paper, we present an approach based on timed automata that can provide the required guarantees for the later integration without strong assumptions, which are difficult to match in practice. The approach provides a modular reasoning scheme that permits to establish the required guarantees for the integration employing only local checks, which therefore also scales. It is also possible to determine potential configuration settings by means of timed game synthesis. / Die korrekte Komposition individuell entwickelter Komponenten von eingebetteten Realzeitsystemen ist eine Herausforderung, da neben funktionalen Eigenschaften auch nicht funktionale Eigenschaften berücksichtigt werden müssen. Ein Beispiel hierfür ist die Kompatibilität von Realzeiteigenschaften, welche eine entscheidende Rolle in eingebetteten Systemen spielen. Heutzutage wird die Kompatibilität derartiger Eigenschaften in einer aufwändigen Integrations- und Konfigurationstests am Ende des Entwicklungsprozesses geprüft, wobei diese Tests im schlechtesten Fall fehlschlagen. Aus diesem Grund wurde eine Zahl an formalen Verfahren Entwickelt, welche eine frühzeitige Analyse von Realzeiteigenschaften von Komponenten erlauben, sodass Inkompatibilitäten von Realzeiteigenschaften in späteren Phasen ausgeschlossen werden können. Existierenden Verfahren verlangen jedoch, dass eine Reihe von Bedingungen erfüllt sein muss, welche von realen Systemen nur schwer zu erfüllen sind, oder aber, die verwendeten Analyseverfahren skalieren nicht für größere Systeme. In dieser Arbeit wird ein Ansatz vorgestellt, welcher auf dem formalen Modell des Timed Automaton basiert und der keine Bedingungen verlangt, die von einem realen System nur schwer erfüllt werden können. Der in dieser Arbeit vorgestellte Ansatz enthält ein Framework, welches eine modulare Analyse erlaubt, bei der ausschließlich miteinender kommunizierende Komponenten paarweise überprüft werden müssen. Somit wird eine skalierbare Analyse von Realzeiteigenschaften ermöglicht, die keine Bedingungen verlangt, welche nur bedingt von realen Systemen erfüllt werden können.

Die modellgetriebene Entwicklung (MDD) ist ein Ansatz, um formale Modelle automatisiert in ausführbare Software zu übersetzen. Obwohl dieses Vorgehen die Häufigkeit von Fehlern im generierten Quellcode verringert, können immer noch die Ausgangsmodelle fehlerhaft sein. Deshalb sind zusätzliche Prüfverfahren, wie z.B. die Verwendung eines Model Checkers sinnvoll. Er stellt automatisiert sicher, dass ein Modell alle gestellten Anforderungen erfüllt. Das Ziel dieser Arbeit ist daher die Integration eines Model Checkers in den modellgetriebenen Entwicklungsprozess, um die Qualität von Software-Produkten zu verbessern. Zu diesem Zweck wird das sogenannte DSL Verification Framework (DVF) vorgestellt. Es stellt Entwicklern vorgefertigte Sprachkonstrukte zur Verfügung, um die Implementierung von Parsern und Transformatoren zu erleichtern. Des Weiteren berücksichtigt es auch die "State Space Explosion", damit auch größere Modelle verifizierbar bleiben. Um die praktische Nutzung des DVF zu evaluieren, werden zwei Industriefallstudien durchgeführt.

Chipkarten sind ein fester Bestandteil unseres täglichen Lebens, das immer stärker von der Zuverlässigkeit derartiger Sicherheitssysteme abhängt, zum Beispiel Bezahlkarten, elektronische Gesundheitskarten oder Ausweisdokumente. Eine Sicherheitspolitik beschreibt die wichtigsten Sicherheitsziele und Sicherheitsfunktionen eines Systems und bildet die Grundlage für dessen zuverlässige Entwicklung. In der Arbeit konzentrieren wir uns auf multi-applikative Chipkartenbetriebssysteme und betrachten neue zusätzliche Sicherheitsziele, die dem Schutz der Kartenanwendungen dienen. Da die Qualität des Betriebssystems von der umgesetzten Sicherheitspolitik abhängt, ist deren Korrektheit von entscheidender Bedeutung. Mit einer Formalisierung können Zweideutigkeiten in der Interpretation ausgeschlossen und formale Beweistechniken angewendet werden. Bisherige formale Verifikationen von Sicherheitspolitiken beinhalten im allgemeinen den Nachweis von Safety-Eigenschaften. Wir verlangen zusätzlich die Betrachtung von Security-Eigenschaften, wobei aus heutiger Sicht beide Arten von Eigenschaften stets getrennt in unterschiedlichen Formalismen verifiziert werden. Die Arbeit stellt eine gemeinsame Spezifikations- und Verifikationsmethodik mit Hilfe von Observer-Modellen vor, die sowohl den Nachweis von Safety-Eigenschaften in einem TLA-Modell als auch den Nachweis von Security-Eigenschaften kryptografischer Protokolle in einem induktiven Modell erlaubt. Da wir alle Spezifikationen und Verifikationen im Werkzeug VSE-II durchführen, bietet das formale Modell der Sicherheitspolitik nicht nur einen abstrakten Blick auf das System, sondern dient gleichzeitig als abstrakte Systemspezifikation, die es in weiteren Entwicklungsschritten in VSE-II zu verfeinern gilt. Die vorgestellte Methodik der Integration beider Systemmodelle in VSE-II führt somit zu einer erhöhten und nachweisbaren Qualität von Sicherheitspolitiken und von Sicherheitssystemen. / Security systems that use smart cards are nowadays an important part of our daily life, which becomes increasingly dependent on the reliability of such systems, for example cash cards, electronic health cards or identification documents. Since a security policy states both the main security objectives and the security functions of a certain security system, it is the basis for the reliable system development. This work focuses on multi-applicative smart card operating systems and addresses new security objectives regarding the applications running on the card. As the quality of the operating system is determined by the underlying security policy, its correctness is of crucial importance. A formalization of it first provides an unambiguous interpretation and second allows for the analysis with mathematical precision. The formal verification of a security policy generally requires the verification of so-called safety properties; but in the proposed security policy we are additionally confronting security properties. At present, safety and security properties of formal system models are verified separately using different formalisms. In this work we first formalize a security policy in a TLA system specification to analyze safety properties and then separately verify security properties using an inductive model of cryptographic protocols. We provide a framework for combining both models with the help of an observer methodology. Since all specifications and proofs are performed with the tool VSE-II, the verified formal model of the security policy is not just an abstract view on the security system but becomes its high level specification, which shall be refined in further development steps also to be performed with the tool. Hence, the integration of the two approaches within the tool VSE-II leads to a new quality level of security policies and ultimately of the development of security systems.

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. / 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.

DNA-basierte Systeme beschreiben formal ein alternatives Berechnungskonzept, beruhend auf der Anwendung molekularbiologischer Operationen. Der Grundgedanke ist dabei die Entwicklung alternativer und universeller Rechnerarchitekturen. Infolge der zugrunde liegenden maximalen Parallelität sowie der hohen Komplexität entsprechender Systeme ist die Korrektheit jedoch schwer zu beweisen. Um dies zu ermöglichen werden in der Arbeit zunächst für drei verschiedene Systemklassen mit unterschiedlichen Berechnungsparadigmen strukturelle operationelle Semantiken definiert und bekannte Formalismen der Prozesstheorie adaptiert. Nachfolgend werden Tableaubeweissysteme beschrieben, mithilfe derer einerseits Invarianten und andererseits die jeweilige Korrektheit von DNA-basierten Systemen mit universeller Berechnungsstärke bewiesen werden können. Durch Anwendung dieser Konzepte konnte für drei universelle Systeme die Korrektheit gezeigt und für ein System widerlegt werden.

DNA-basierte Systeme beschreiben formal ein alternatives Berechnungskonzept, beruhend auf der Anwendung molekularbiologischer Operationen. Der Grundgedanke ist dabei die Entwicklung alternativer und universeller Rechnerarchitekturen. Infolge der zugrunde liegenden maximalen Parallelität sowie der hohen Komplexität entsprechender Systeme ist die Korrektheit jedoch schwer zu beweisen. Um dies zu ermöglichen werden in der Arbeit zunächst für drei verschiedene Systemklassen mit unterschiedlichen Berechnungsparadigmen strukturelle operationelle Semantiken definiert und bekannte Formalismen der Prozesstheorie adaptiert. Nachfolgend werden Tableaubeweissysteme beschrieben, mithilfe derer einerseits Invarianten und andererseits die jeweilige Korrektheit von DNA-basierten Systemen mit universeller Berechnungsstärke bewiesen werden können. Durch Anwendung dieser Konzepte konnte für drei universelle Systeme die Korrektheit gezeigt und für ein System widerlegt werden.

Sound criteria for partial order reduction for probabilistic concurrent systems have been presented in the literature. Their realization relies on a depth-first search-based approach for generating the reduced model. The drawback of this dynamic approach is that it can hardly be combined with other techniques to tackle the state explosion problem, e.g., symbolic probabilistic model checking with multi-terminal variants of binary decision diagrams. Following the approach presented by Kurshan et al. for non-probabilistic systems, we study partial order reduction techniques for probabilistic concurrent systems that can be realized by a static analysis. The idea is to inject the reduction criteria into the control flow graphs of the processes of the system to be analyzed. We provide the theoretical foundations of static partial order reduction for probabilistic concurrent systems and present algorithms to realize them. Finally, we report on some experimental results.

In der formalen Verifikation digitaler Schaltkreise hat sich die Methodik der vollständigen Verifikation anhand spezieller Operationseigenschaften bewährt. Operationseigenschaften beschreiben das Verhalten einer Schaltung in einem festen Zeitintervall und können sequentiell miteinander verknüpft werden, um so das Gesamtverhalten zu spezifizieren. Zusätzlich beweist eine formale Vollständigkeitsprüfung, dass die Menge der Eigenschaften für jede Folge von Eingangssignalwerten die Ausgänge der zu verifizierenden Schaltung eindeutig und lückenlos determiniert. In dieser Arbeit wird untersucht, wie aus Operationseigenschaften, deren Vollständigkeit erfolgreich bewiesen wurde, automatisiert eine Schaltungsbeschreibung abgeleitet werden kann. Gegenüber der traditionellen Entwurfsmethodik auf Register-Transfer-Ebene (RTL) bietet dieses Verfahren zwei Vorteile. Zum einen vermeidet der Vollständigkeitsbeweis viele Arten von Entwurfsfehlern, zum anderen ähnelt eine Beschreibung mit Hilfe von Operationseigenschaften den in Spezifikationen häufig genutzten Zeitdiagrammen, sodass die Entwurfsebene der Spezifikationsebene angenähert wird und Fehler durch manuelle Verfeinerungsschritte vermieden werden. Das Entwurfswerkzeug vhisyn führt die High-Level-Synthese (HLS) einer vollständigen Menge von Operationseigenschaften zu einer Beschreibung auf RTL durch. Die Ergebnisse zeigen, dass sowohl die verwendeten Synthesealgorithmen, als auch die erzeugten Schaltungen effizient sind und somit die Realisierung größerer Beispiele zulassen. Anhand zweier Fallstudien kann dies praktisch nachgewiesen werden. / The complete verification approach using special operation properties is an accepted methodology for the formal verification of digital circuits. Operation properties describe the behavior of a circuit during a certain time interval. They can be sequentially concatenated in order to specify the overall behavior. Additionally, a formal completeness check proves that the sequence of properties consistently determines the exact value of the output signals for every valid sequence of input signal values. This work examines how a circuit description can be automatically derived from a set of operation properties whose completeness has been proven. In contrast to the traditional design flow at register-transfer level (RTL), this method offers two advantages. First, the prove of completeness helps to avoid many design errors. Second, the design of operation properties resembles the design of timing diagrams often used in textual specifications. Therefore, the design level is closer to the specification level and errors caused by refinement steps are avoided. The design tool vhisyn performs the high-level synthesis from a complete set of operation properties to a description at RTL. The results show that both the synthesis algorithms and the generated circuit descriptions are efficient and allow the design of larger applications. This is demonstrated by means of two case studies.