Das Ziel dieser Arbeit ist die Erforschung möglicher Synergien zwischen Petri-Netz-Theorie und Reverse Engineering. Dass solche Synergien möglich sind, liegt nicht auf der Hand, zu verschieden sind die Grundannahmen in den beiden Gebieten. Diese Gegensätzlichkeit bringe ich mit zwei unterschiedlichen Modellierungs-Paradigmen in Verbindung, nämlich mit Folding und Clustering.
Clustering gruppiert Nachbarschaften und entspricht der ingenieur-mässigen Konstruktion von komplexen System aus Teilsystemen. Es ist somit ein Grundprinzip von Reverse Engineering und unabdingbar für jedes Praxis-taugliche Petri-Netz-Werkzeug. In Petri-Netzen kombinieren Foldings Stellen mit Stellen, Transitionen mit Transitionen und Kanten mit Kanten. Sie gruppieren somit ähnliche Funktionen, ermöglichen es Verhaltenseigenschaften zu übertragen und haben weitreichende Verbindungen zu anderen Modellen der Nebenläufigkeit.
Diese Arbeit führt einen folding-basierten Petri-Netz Algorithmus für Reverse Engineering ein. Kernstück ist die Reduktion eines unstrukturierten Netzes in ein gefärbtes Netz. Die beiden Netze sind durch einen Folding-Morphismus verbunden, der eine kompakte Beschreibung des Ursprungsnetzes beinhaltet. Der Grundalgorithmus ist anpassungsfähig, z.B. kann er mit verschiedenen Anwendungsheuristiken kombiniert werden. Hervorragend für einen Reverse-Engineering-Algorithmus ist die Effizienz. Die Kosten sind beinahe linear in der Grösse des Ausgangsnetzes.
Petri-Netz-Modelle können ein kompaktes und intuitives Bild des Zusammenspieles von strukturellen, funktionalen und dynamischen Aspekten eines Systems zeigen. Neu daran ist es, Petri-Netze für Fragen, die wenig mit Nebenläufigkeit zu tun haben, zu verwenden. Mit geeigneten solchen Übersetzungen wird der Reduktionsalgorithmus allgemein anwendbar, nicht nur für Petri-Netze. Das ergibt eine neue, mächtige Reverse Engineering Methode. An einem konkreten Beispiel wird gezeigt, wie aus elementaren Implementations-Informationen eine abstrakte Architektur wiedergewonnen werden kann. Die berechnete Färbung des reduzierten Netzes spezifiziert den Zusammenhang von Architektur und Implementation und spiegelt das Datenmodell wider.
Der Reverse-Engineering-Teil dieser Dissertation befasst sich mit folding-basierten Methoden, weil sie neue Möglichkeiten enthalten, während clustering-basierte Petri-Netz-Methoden viele Ähnlichkeiten mit bekannten Reverse-Engineering Techniken teilen. Aber selbstverständlich soll nicht Folding gegen Clustering ausgespielt werden, sondern ein sinnvolles Zusammenspiel gesucht werden. Theoretischen Grundlagen dafür werden im ersten Teil dieser Dissertation gelegt.
Viele aus der Literatur bekannte Klassen von Petri-Netzen können in folding- und clustering-basierte unterteilt werden. Was jedoch fehlt, ist eine wohldefinierte Verbindung zwischen den beiden Gruppen. Erst eine solche erlaubt die Stärken beider Ansätze zu kombinieren - auch in praktischen Anwendungen.
Eine solche Verbindung wird hier vorgestellt und zwar in der Form einer Adjunktion - einer starken Zweiweg-Beziehung aus der Kategorientheorie. Es wird gezeigt, dass die verbundenen Kategorien die typischen Stärken von clustering- bzw. folding-basierten Petri-Netz-Klassen aufweisen. Darauf aufgebaute Kategorien und Adjunktionen bilden eine Formalisierung der Dichotomie von Struktur und Verhalten - einem grundlegenden Petri-Netz Prinzip, das meines Wissens noch nie kategorientheoretisch formuliert worden ist.
Für die Praxis von Bedeutung ist, dass diese Konzepte relativ einfach in bestehende Petri-Netz-Werkzeuge integriert werden können. Das ermöglicht diese durch kategorische Mittel wie Morphismen, universelle Konstruktionen oder Übertragung von Semantik zu bereichern. Gefärbte Netze werden verblüffend einfach definiert, nämlich als spezielle Kommakategorien, d.h. im wesentlichen als folding-basierte Morphismen. Ein Beispiel für den praktischen Wert dieses Ansatzes ist der eingeführte Reduktionsalgorithmus: Er ist eine Iteration von (co)universellen Konstruktionen und die berechnete Reduktion hat selbst wieder (co)universelle Eigenschaften.
The aim of this work is to conduct research into synergies between Petri-net theory and reverse engineering. The existence of such synergies is not obvious because each sector is based on different assumptions. These differences relate to two modelling paradigms: clustering and folding.
Clustering merges neighboured nodes and corresponds to the construction of complex systems from subsystems. It is widely used in software engineering and in practical applications of Petri nets. Foldings only merge transitions with transitions, places with places and arcs with arcs. They group similar functionality. Hence they preserve behaviour, allow the transfer of semantics and provide deep theoretical insights by means of far-reaching connections to other models of concurrency.
A folding-based Petri-net algorithm for reverse engineering is introduced. It recovers a coloured net from an unstructured flat Petri net. The two nets are connected by a folding which amounts to a compact specification of the source net. The algorithm is both flexible and scalable, and this work shows how application heuristics can be integrated into it. Its cost is almost linear with respect to the size of the input net, which is remarkable in the field of reverse engineering.
Petri nets may serve as an intuitive model of the interplay of the structural, functional and dynamic aspects of a system. Various methods of modelling aspects apart from concurrency by Petri nets represent an innovation. With such a translation, the algorithm may also analyse legacy systems outside the realms of Petri nets. The result is a novel and powerful method of reverse engineering. A specific example shows how a high-level design may be recovered from low-level implementation information. Moreover, the recovered colouring contains a complete specification inclusive of the data model.
The reverse engineering part of this work concentrates on folding-based Petri-net methods because they contain new features. On the other hand, clustering-based techniques share many similarities with known methods. For best results, however, clustering and folding should be appropriately combined. The foundations for such combinations are laid down in the first part of this thesis.
Many Petri-net classes known from the literature may be grouped into folding-based and clustering-based types. However, no well-defined link exists between them which would allow the strengths of both approaches to be combined, especially for practical applications.
Such a link is presented here in the form of an adjunction, which is a strong two-way relationship taken from category theory. It links folding-based and clustering-based categories. It is shown that these categories have properties typical of folding-based and clustering-based Petri-nets respectively. Further compatible adjunctions express the Petri-net dichotomy of structure and behaviour. To the best of the author’s knowledge, this basic principle of Petri-net theory has not yet been formulated categorically.
For practical applications, it is important that these concepts can be integrated fairly easily with existing Petri-net tools. This will enrich them with the power of a categorical machinery, e.g. with morphisms, universal constructions and the transfer of behaviour. Coloured nets are simply defined as special comma categories, i.e. essentially folding morphisms. The reduction algorithm introduced here is a proof of the practical value of this approach: it is an iteration of couniversal constructions and the reduction itself has couniversal properties.
Petri nets; reverse software engineering; clustering; folding; structure; behaviour; semantics; occurrence nets; category theory; design metaphor.