Aufbereitung von Shapeanalyseausgaben zur Visualisierung der abstrakten Programmausführung

Abstract

Diese Arbeit behandelt einen Ansatz zur Algorithmenvisualisierung von zeigerbasierten Programmen. Während traditionell die Programmausführung für konkrete Daten visualisiert wird, stützt sich dieser Ansatz auf die abstrakte Programmausführung. Dazu wird vorab mittels Shapeanalyse, einer auf Logik basierenden parametrischen statischen Programmanalysetechnik, eine Beschreibung der an den Programmpunkten auftretenden abstrakten Heapstrukturen berechnet. Diese Shapegraphenmengen sind jedoch in der Regel für eine direkte Visualisierung zu groß. Ein zentrales Thema dieser Arbeit ist die Entwicklung von Methoden, die Analyseausgabe vor der eigentlichen Visualisierung aufzubereiten. Sie führen sowohl zu einer Reduktion der Komplexität als auch zu einer gesteigerten Wirksamkeit der Visualisierung. Im Vordergrund stehen Methoden zur Strukturierung der Analyseausgabe. Ein Ähnlichkeitskonzept gestattet es, bezüglich verschiedener parametrischer Ähnlichkeitsbegriffe zu abstrahieren. Auf diese Weise werden ähnliche Heapstrukturen und ähnliche Programmausführungen identiziert und zusammengefasst. Mit gleicher Absicht wird ein Konzept zur Ausnutzung von Symmetrie eingeführt. Ergänzend werden Methoden vorgestellt, welche die in einer Menge von Shapegraphen enthaltenen Informationen verdichten. Zu den darüber hinaus behandelten Themen gehören Methoden, die Hilfestellungen bei der Traversierung durch die abstrakte Programmausführung bieten.

This work presents an approach to algorithm visualisation of pointer based programs. While traditionally the execution of a program is visualised for concrete data, our approach is based on abstract program execution. Using shape analysis, which is a logic based parametric static program analysis technique, a description of the abstract heap situations that can occur at each program point is computed in advance. However, the resulting sets of shape graphs are generally too large to be visualised directly. A central topic of this work is the development of methods for preparing the analysis output before the actual visualisation. This results in complexity reduction as well as in increased efficiency with respect to visualisation. The focus lies on methods for structuring the analysis output. A similarity concept allows abstraction with respect to various parametric similarity notions. This way similar heap structures and similar execution paths are identied and summarised. With the same purpose in mind, a concept of taking advantage of symmetry is introduced. Additionally, methods are presented that condense the information contained in sets of shape graphs. Further topics include methods that assist in the traversal of the abstract program execution.