Entwicklung eines Werkzeugs zum Vergleich von Code-Fragmenten durch symbolische Ausführung

BearbeiterIn:Marius Kamp
Titel:Entwicklung eines Werkzeugs zum Vergleich von Code-Fragmenten durch symbolische Ausführung
Typ:masters thesis
Betreuer:Dotzler, G.; Philippsen, M.
Status:abgeschlossen am 1. Oktober 2014
Vorausetzungen:
Thema:

Hintergrund

Software wird im Laufe der Zeit ständig verändert. Der Grund für die Änderungen sind vielfältig. Häufig wurden Fehler gefunden, die behoben werden müssen, oder die API von verwendeten Modulen hat sich geändert und die eigene Software muss angepasst werden. In vielen Fällen taucht ein Fehler nicht nur an einer Stelle auf, sondern an mehreren. API-Änderungen erzwingen oft ebenfalls viele sich mehr oder weniger ähnelnde Code-Anpassungen. Um Zeit zu sparen und um mögliche Fehler zu vermeiden, wäre gerade in diesen Fällen ein Werkzeug hilfreich, das dem Programmierer die Änderungen abnimmt. Ein Weg dies zu realisieren ist das am Lehrstuhl entwickelte Code-Optimierungswerkzeug, das alle Stellen im Projekt mit den zu modifizierenden Stellen aufzeigt und für jede Stelle den neu angepassten Quellcode als Verbesserung vorschlägt. Da viele Bibliotheken in mehr als einem Projekt verwendet werden und sich viele ähnliche Fehler in anderen unabhängigen Projekten wiederfinden, können die einmal gemachten Änderungen von einem Code-Optimierungswerkzeug gelernt und dann auch in anderen Projekten oder Projektteilen angewandt werden.

Thema
Am Lehrstuhl wurde ein Werkzeug zur Extraktion von Code-Änderungsmustern aus git-Archiven entwickelt. Innerhalb dieser Arbeit soll durch symbolische Code-Ausführung untersucht werden, ob durch die Anwendung eines der Änderungsmuster, semantisch identischer Code erzeugt wird. Dies soll durch die Ausführung des Code-Abschnitts vor der Transformation und der Ausführung des Code-Abschnitts nach der Transformation erreicht werden.

Hier ein einfaches Beispiel:

a)
int i = 0;
int t = 0;
while (i < 3) {
..i++;
..t = 42;
}
(Code vor der Transformation)

Symbolisches Ausführungsergebnis:
i = i + 1 + 1 && t = const-value-2

b)
int i = 0;
int t = 42;
while (i < 3) {
..i++;
}
(Code nach der Transformation)

Symbolisches Ausführungsergebnis:
i = i + 1 + 1 && t = const-value-2

c)
int i = 0;
int t = 42;
while (i < q) {
..i++;
}
(Code nach der Transformation)

Symbolisches Ausführungsergebnis:
i = i + mul(loop-count-times, i++) && t = const-value-2

Die Beispiele a) und b) zeigen zwei Code-Stücke, die vom Werkzeug durch das Ausführungsergebnis als identisch erkannt werden sollen. Im nächsten Meilenstein der Arbeit, soll eine Heuristik entwickelt werden, die auch angibt, wie sehr sich zwei Ausführungsergebnisse (z.B. a) und c)) ähneln, wenn sie nicht identisch sind. Am Ende soll das Programm mit bereits bekannten Mustern evaluiert werden.

Meilensteine

  • Implementierung der symbolischen Ausführung von Code-Teilstücken
  • Entwicklung einer geeigneten Heuristik zum Vergleich der Ausführungsergebnisse
  • Evaluierung der Algorithmen an Hand von in Open Source Projekten gefundenen Mustern
  • Ausarbeitung

Literatur

watermark seal