Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26587
Titel: Synthesis and control of infinite-state systems with partial observability
VerfasserIn: Dimitrova, Rayna
Sprache: Englisch
Erscheinungsjahr: 2013
Kontrollierte Schlagwörter: Formale Methode
Verifikation
Spieltheorie
Freie Schlagwörter: synthesis
control
infinite-state systems
counterexample-guided abstraction refinement
DDC-Sachgruppe: 004 Informatik
Dokumenttyp: Dissertation
Abstract: Complex computer systems play an important role in every part of everyday life and their correctness is often vital to human safety. In light of the recent advances in the area of formal methods and the increasing availability and maturity of tools and techniques, the use of verification techniques to show that a system satisfies a specified property is about to become an integral part of the development process. To minimize the development costs, formal methods must be applied as early as possible, before the entire system is fully developed, or even at the stage when only its specification is available. The goal of synthesis is to automatically construct an implementation guaranteed to fulfill the provided specification, and, if no implementation exists, to report that the given requirements cannot be realized. When synthesizing an individual component within a system and its external environment, the synthesis procedure must take into account the component’s interface and deliver implementations that comply with it. For example, what a component can observe about its environment may be restricted by imprecise sensors or inaccessible communication channels. In addition, sufficiently precise models of a component’s environment are typically infinite-state, for example due to modeling real time or unbounded communication buffers. This thesis presents novel synthesis methods that respect the given interface limitations of the synthesized system components and are applicable to infinite-state models. The studied computational model is that of infinite-state two-player games under incomplete information. The contributions are structured into three parts, corresponding to a classification of such games according to the interface between the synthesized component and its environment. In the first part, we obtain decidability results for a class of game structures where the player corresponding to the synthesized component has a given finite set of possible observations and a finite set of possible actions. A prominent type of systems for which the interface of a component naturally defines a finite set of observations are Lossy Channel Systems. We provide symbolic game solving and strategy synthesis algorithms for lossy channel games under incomplete information with safety and reachability winning conditions. Our second contribution is a counterexample-guided abstraction refinement scheme for solving infinite-state under incomplete information in which the actions available to the component are still finitely many, but no finite set of possible observations is given. This situation is common, for example, in the synthesis of mutex protocols or robot controllers. In this setting, the observations correspond to observation predicates, which are logical formulas, and their computation is an integral part of our synthesis procedure. The resulting game solving method is applicable to games that are out of the scope of other available techniques. Last we study systems in which, in addition to the possibly infinite set of observation predicates, the component can choose between infinitely many possible actions. Timed games under incomplete information are a fundamental class of games for which this is the case. We extend the abstraction-refinement procedure to develop the first systematic method for the synthesis of observation predicates for timed control. Automatically refining the set of candidate observations based on counterexamples demonstrates better potential than brute-force enumeration of observation sets, in particular for systems where fine granularity of the observations is necessary.
Komplexe Computer Systeme spielen eine wichtige Rolle in jedem Teil des Alltags und ihre Korrektheit ist oft entscheidend für die menschliche Sicherheit. Angesichts der neuesten Fortschritte auf dem Gebiet der formalen Methoden und die zunehmende Verfügbarkeit und Reife von Tools und Verfahren, wird die Verwendung von Techniken zur Prüfung, dass ein System eine bestimmte Eigenschaft erfüllt, zu einem integralen Bestandteil des Entwicklungsprozesses. Um die Entwicklungskosten zu minimieren, sollen formale Methoden so früh wie möglich angewendet werden, bevor das System vollständig entwickelt ist, oder sogar in der Phase, wenn nur seine Spezifikation zur Verfügung steht. Das Ziel von Synthese ist, automatisch eine Implementierung zu konstruieren, die garantiert die gegebene Spezifikation erfüllt. Falls keine solche Implementierung existiert, soll die Unrealisierbarkeit der Spezifikation ausgewiesen werden. Bei der Synthese einer einzelnen Komponente innerhalb eines Systems und seiner äußeren Umgebung müssen synthetisierte Implementierungen die Schnittstelle der Komponente berücksichtigen. Beispielsweise kann eine Komponente ihre Umgebung nur über wenige, unpräzise Sensoren beobachten. Darüber hinaus haben präzise Modelle einer Umgebung einer Komponente normalerweise einen unendlichen Zustandsraum, z.B. durch die Modellierung von Realzeit oder durch unbegrenzte Kommunikationspuffer. Diese Dissertation stellt neuartige Syntheseverfahren für Modelle mit unendlichem Zustandsraum vor, die die Einschränkungen berücksichtigen, die durch die Schnittstelle der synthetisierten Systemkomponenten gegeben sind. Das grundlegende Berechnungsmodell sind Spiele mit zwei Spielern und einem unendlichen Zustandsraum. Der Beitrag der Dissertation ist in drei Teile gegliedert. Der erste Teil der Dissertation liefert Entscheidbarkeitsresultate für eine Klasse von Spielen, in der der Spieler, der die Systemkomponente repräsentiert, eine endliche Menge von Beobachtungen und Aktionen hat. Ein prominenter Repräsentant dieser Klasse sind Lossy Channel Systeme. Es werden symbolische Algorithmen zur Strategiesynthese für Lossy Channel Spiele unter unvollständiger Information mit Sicherheits und Erreichbarkeits-Gewinnzielen präsentiert. Der zweite Beitrag besteht aus einem Gegenbeispiel-geführten Abstraktionsverfeinerungs-Schema zum Lösen von Spielen mit unendlichem Zustandsraum unter unvollständiger Information, in denen die Komponente endlich viele Aktionen hat aber keine endliche Menge von möglichen Beobachtungen gegeben ist. Diese Situation ist weit verbreitet z.B. bei der Synthese von Mutex-Protokollen oder Robotersteuerungen. In diesem Kontext entsprechen die Beobachtungen Beobachtungsprädikaten, die durch logische Formeln repräsentiert sind, wobei deren Berechnung ein integraler Bestandteil des Syntheseverfahrens ist. Das resultierende Verfahren kann zum Lösen von Spielen benutzt werden, die mit keiner verfügbaren Technik gelöst werden können. Letztlich werden Systeme untersucht, in denen die Komponente unendlich viele Beobachtungsprädikate hat und zwischen unendlich vielen Aktionen auswählen kann. Gezeitete Spiele unter unvollständiger Information sind eine grundlegende Klasse von Spielen, bei denen dies der Fall ist. Wir erweitern das Abstraktionsverfeinerungs-Schema, um die erste systematische Methode zur Synthese von Beobachtungsprädikaten für gezeitete Controller zu entwickeln. Es wird demonstriert, dass eine Verfeinerung der Beobachtungen, basierend auf Gegenbeispielen, ein höheres Potential aufzeigt als eine Brute-Force-Aufzählung der Beobachtungen, insbesondere für Systeme, bei denen eine feine Granularität der Beobachtungen notwendig ist.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-59467
hdl:20.500.11880/26643
http://dx.doi.org/10.22028/D291-26587
Erstgutachter: Finkbeiner, Bernd
Tag der mündlichen Prüfung: 12-Jun-2014
Datum des Eintrags: 12-Dez-2014
Fakultät: MI - Fakultät für Mathematik und Informatik
Fachrichtung: MI - Informatik
Sammlung:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Dateien zu diesem Datensatz:
Datei Beschreibung GrößeFormat 
thesis.pdf1,52 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.