Sichtgraphen: Ein Konzept zur gezielten Untersuchung von Kontrollflussstrukturen

Language
de
Document Type
Doctoral Thesis
Issue Date
2004-07-29
Issue Year
2004
Authors
Goßens, Stefan
Editor
Abstract

The thesis describes a concept for the abstraction of control flow graphs, view graphs, and some of its possible applications. Many computer science applications, especially in validation and verification, are directly or indirectly based on control flow analysis. Often, certain actions in the control flow are of special interest, e.g. input and output actions. These actions define a view of the graph. Their possible sequences are represented as view graphs in the presented approach, which are view focused abstractions of the control flow graph. There are many imaginable applications for view graphs. The thesis introduces the basic concepts as well as two special views, behavioural view and reliability view. These are the views with respect to input and output statements resp. the statements that constitute explicit fault tolerance mechanisms. The corresponding view graphs are behavioural graphs and reliability graphs. Metrics based on behavioural graphs can serve as a basis of test case evaluations. This thesis introduces such a metric, behavioural diversity. An approach for modeling fault detection abilities of programs is developed and used in an experimental evaluation of the metric. Using reliability graphs, the fault tolerance architecture of a system can be examined and verified. The thesis describes a corresponding approach. Additionally, a concept similar to the view graph approach to generate test designs is presented.

Abstract

Die vorliegende Arbeit beschreibt ein Konzept zur Abstraktion von Kontrollflussstrukturen, die Sichtgraphen, und mögliche Anwendungen. Viele Aufgabenstellungen der Informatik, speziell im Validierungs und Verifikationsbereich, basieren direkt oder indirekt auf der Analyse von Kontrollflüssen. Oft interessieren dabei besonders bestimmte Aktionen im Kontrollfluss des Systems, beispielsweise Ein und Ausgaben. Diese Aktionsmengen definieren eine Sicht auf den Graphen. Die möglichen Abfolgen der Aktionen werden im vorgestellten Ansatz kompakt als Sichtgraph repräsentiert, der so eine gezielte Abstraktion des Kontrollflussgraphen darstellt. Es gibt viele denkbare Anwendungen für Sichtgraphen. Die Arbeit stellt neben den Grundlagen exemplarisch zwei spezielle Sichten vor, die Verhaltenssicht und die Zuverlässigkeitssicht. Dies sind die Sichten bezüglich der Ein und Ausgabeanweisungen bzw. der Anweisungen, die zur Realisierung expliziter Fehlertoleranz dienen. Die entsprechenden Sichtgraphen sind Verhaltensgraphen und Zuverlässigkeitsgraphen. Verhaltensgraphbasierte Metriken können zur Bewertung von Testfallmengen dienen. In der Arbeit wird eine solche Kenngrösse, die Verhaltensdiversität, vorgestellt. Ein Ansatz zur Modellierung der Fehleraufdeckungsfähigkeiten von Programmen wird entwickelt und in einer experimentellen Untersuchung der Verhaltensdiversität benutzt. Anhand der Zuverlässigkeitssicht lässt sich die Fehlertoleranzarchitektur eines Systems prüfen. Die Arbeit betrachtet ein entsprechendes Verfahren Zusätzlich wird ein an Sichtgraphen angelehntes Konzept zum Entwurf von Tests aus automatenbasierten Spezifikationen beschrieben.

DOI
Document's Licence
Faculties & Collections
Zugehörige ORCIDs