Implementierung eines existierenden Verfahrens zum Program-Slicing für nebenläufige Software und Erstellung eines Benchmarks mit Wettlaufsitationen

Title:Implementierung eines existierenden Verfahrens zum Program-Slicing für nebenläufige Software und Erstellung eines Benchmarks mit Wettlaufsitationen
Type:bachelor thesis
Advisors:Baer, M.; Philippsen, M.
Prerequisits:
Topic:

Hintergrund:
In paralleler Software ist es schwierig, darin enthaltene Fehler zu finden, da der Ablauf nicht deterministisch ist und die Verschränkungen der Ablauffäden schwer vorstellbar sind. Sowohl für den Entwickler, als auch für automatische Analysen stellt die Komplexität eine Herausforderung dar.

Problemstellung:
Ziel dieser Arbeit ist es, das zu testende Programm zu verkleinern, um die Komplexität zu verringern. Dabei darf aber natürlich das fehlerhafte Verhalten nicht entfernt werden. Für sequentielle Programme wurde bereits Program Slicing entwickelt - eine Technik, die es erlaubt, Teile aus Programmen auszuschneiden, die keinen Einfluss auf die untersuchten Eigenschaften haben. Hierbei wird normalerweise ein Programmabhängigkeitsgraph (Program Dependency Graph, PDG) aufgebaut, der Informationen darüber enthält, welche Anweisungen daten- oder kontrollflussabhängig zu welchen anderen Anweisungen sind. Anhand dieses Graphen lassen sich dann relativ einfach die relevanten Stellen identifizieren. Auch für parallele Software wurden zwei Techniken vorgestellt, jedoch nur für einen Teil der jeweiligen Sprachkonstrukte und ohne geeignete Evaluation.
Im Rahmen dieser Arbeit soll ein Werkzeug entwickelt werden, das ein Verfahren des Program Slicings implementiert, und dieses soll anhand von öffentlich verfügbaren Programmen evaluiert werden.

Aufgabenstellung:
Diese Arbeit besteht aus drei Abschnitten. Zum einen soll ein bestehendes Verfahren zum Program-Slicing für nebenläufige Software implementiert werden. Außerdem soll eine Sammlung von (bereits gefundenen) Wettlaufsituationen aus öffentlich zugänglichen Projekten zu einer Art Benchmark zusammengestellt werden. Damit lassen sich in Zukunft Werkzeuge anhand ihrer Geschwindigkeit und Genauigkeit bewerten und vergleichen. Als letztes soll das implementierte Verfahren noch anhand der Sammlung evaluiert werden.

Empfohlene Kenntnisse/Interessen:
Parallelität, Übersetzerbau, Graphalgorithmen

Literatur:

watermark seal