HOME | DEUTSCH | IMPRESSUM | KIT

Task Description: Interactive Program Analysis

Zurück zur Übersicht

Worum geht es?

Ziel dieses PSE-Projektes ist es, eine Desktop GUI zur Darstellung von Programmanalysen zu entwickeln. Das Programm liest Code ein und zeigt den Steuerflußgraphen dazu an. Nun kann der Benutzer eine Datenflussanalyse angeben (Verband, Richtung, Transferfunktion). Anschließend zeigt die GUI in Einzelschritten animiert die Analyse. Das Werkzeug ist für den Einsatz in der Lehre gedacht. Insbesondere auf Anschaulichkeit soll geachtet werden.

Gewünschte Funktionalitäten im Einzelnen

  • Einlesen von Code (Java, C, Ruby oder anderes). Ein einfaches Subset aus Arithmetik und bedingten/unbedingten Sprüngen reicht aus.
  • Optional: Verschiedene Sprachen oder Dateien im dot-Format einlesen
  • Layouten und Anzeigen des Steuerflußgraphen.
  • Angabe der auszuführenden Programmanalyse.
    Möglich sein soll auf jeden Fall:
    • Constant Folding
    • Reaching Definitions
    • Const Bits
    • Taint Analysis/IFC für Arme.
  • Optional: Implementierung einer eigenen Datenflussanalyse zur Laufzeit möglich, z.B. durch on-the-fly Kompilieren einer Java-Klasse oder Einbetten einer Skriptsprache. Die Wahl der Datenflussanalysesprache ist hier frei.
  • Direktes Ausrechnen des Fixpunkts der Analyse.
  • Animiertes schrittweises Anzeigen der Analyse.
  • Optional: Verschiedene Fixpunktalgorithmen (Worklist, Naiv, etc)

Einsatz von Technologien zur Umsetzung

Die Anwendung muss in einer statisch typisierten OO-Sprache geschrieben werden. Die Wahl der Sprache ist jenseits dessen frei, Java bietet sich jedoch an.

Bibliotheken

Die folgenden Bibliotheken erscheinen uns nützlich. Diese Liste ist allerdings weder vollständig noch ist die Benutzung einer dieser Bibliotheken verpflichtend.

Zwischensprachen

  • Soot: Statisches Analyse-Framework für die JVM.
    Bietet sich an zum Einlesen von class-Dateien und zum Erzeugen der CFG Datenstruktur.
    Soot bietet auch Infrastruktur für Datenflussanalyse (diese wurde aber nicht von uns auf angemessenheit getestet).
  • JRuby: Auf der JVM basierende Implementierung von Ruby.
    JRuby scheint einen CFG aufzubauen, könnte sich also als Eingabesprache eignen.

(Skript-)Sprachen zum Einbetten neuer Analysen

Graphlayouting

  • JUNG: Ein Graphzeichnungsframework für Java, schon etwas älter
  • Gephi: Ein Grapheneditor, dessen Kern auch als Library verfügbar ist

Bewertung

Die Benotung Ihres Systems richtet sich nach folgenden Kriterien:

  • Qualität aller abgegebenen Dokumente und Artefakte

  • Qualität der Kolloquien (10 Minuten Vortrag)

  • Qualität der Abschlusspräsentation

  • Erfüllung der minimalen Leistungsmerkmale (s.o.)

  • sinnvolle Erweiterungen über diese Merkmale hinaus

  • Robustheit des erstellten Programms

  • Teamarbeit (TSE)

Diese Liste hat keine Reihenfolge, die einer Gewichtung entspricht. Es gibt sicherlich weitere Punkte, die als selbstverständlich gelten und sich bei Nichterfüllen negativ auswirken (z.B. ist die Geschwindigkeit der implementierten Algorithmen sekundär, aber jedem sollte klar sein, dass das Errechnen einer Lösung oder das Generieren nicht 10 Tage dauern darf).

Weitere Pflichten

  • Anmeldung per Studienportal für PSE und TSE

  • Anwesenheit bei den wöchentlichen Treffen mit dem Betreuer

  • Team-internes Management (z.B. Phasenverantwortliche, Versionskontrolle)

  • Artefakte 1–2 Tage vor Kolloquium beim Betreuer