Implementierung und Erweiterung eines Verfahrens zum Program-Slicing für nebenläufige Software

Title:Implementierung und Erweiterung eines Verfahrens zum Program-Slicing für nebenläufige Software
Type:masters 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 [1], [2], jedoch nur für einen Teil der jeweiligen Sprachkonstrukte und ohne geeignete Evaluation. Im Rahmen dieser Arbeit soll ein Werkzeug entwickelt werden, das Program Slicing für moderne nebenläufige Java Programme implementiert. Die bisher verwendeten Datenstrukturen und Algorithmen sollen dafür geeignet erweitert und angepasst werden, sodass sie mit gängigen Nebenläufigkeitskonzepten von Java zurecht kommen.

Arbeitsabschnitte:

  • Kurzer Vergleich verschiedener Verfahren zum Program Slicing für parallele Software
  • Auswahl und Anpassung eines geeigneten Ansatzes für den gewünschten Einsatzzweck
  • Evaluation über Anweisungseinsparung und Laufzeit auch bei größerer Software

Empfohlene Kenntnisse:
Übersetzerbau, Datenstrukturen, Graphalgorithmen (Anwendung und Funktionsweise)

Literatur:

watermark seal