Implementierung und Evaluierung einer Hierarchie von Verfahren zum semantischen Vergleich von Code-Fragmenten

Student:Adrian Kretschmer
Title:Implementierung und Evaluierung einer Hierarchie von Verfahren zum semantischen Vergleich von Code-Fragmenten
Type:bachelor thesis
Advisors:Kreutzer, P.; Kamp, M.; Philippsen, M.
State:submitted on November 3, 2016
Prerequisits:
Topic:

Hintergrund
Software-Projekte enthalten oftmals Code-Fragmente, die dem gleichen Zweck dienen. Einerseits kann es sich dabei um Implementierungen von Standard-Algorithmen handeln, die in verschiedenen Projekten vorgenommen wurden, andererseits kann es auch in einem Projekt zur unbeabsichtigten Reimplementierung von Funktionalität kommen. Um den Wartungsaufwand für Software-Projekte zu reduzieren, ist es hilfreich, solche semantisch ähnlichen Code-Fragmente finden zu können, damit diese in eine gemeinsam genutzte Bibliothek ausgelagert werden. Auf diese Weise wird der Wartungsaufwand für den einzelnen Entwickler reduziert. Während sich die Erkennung von syntaktisch ähnlichen Code-Fragmenten bereits in der Praxis etabliert hat, ist die Identifizierung syntaktisch verschiedener, aber semantisch ähnlicher Code-Fragmente noch Gegenstand aktueller Forschung.

Thema
Am Lehrstuhl wurde ein neues Verfahren entwickelt, das die semantische Ähnlichkeit von Code-Fragmenten bestimmen kann. Da das Verfahren auf einer symbolischen Ausführung der Fragmente beruht, liefert dieses zwar sehr genaue Ergebnisse, hat jedoch auch eine sehr hohe Rechenzeit.

Ziel dieser Arbeit ist deshalb die Entwicklung eines Verfahrens, das die mit Hilfe der symbolischen Ausführung bestimmten Ergebnisse möglichst gut approximiert, dabei jedoch einen geringeren Laufzeitaufwand hat.

In einem ersten Schritt sollen dazu zunächst mehrere verschiedene Mechanismen für den semantischen Vergleich von Code-Fragmenten konzipiert und implementiert werden. Ein solcher Komparator könnte beispielsweise auf einem Vergleich des Program Dependence Graph der Code-Fragmente (siehe Nguyen et al.) beruhen oder die jeweils vorkommenden Kontrollstrukturen vergleichen. Neben dem Entwurf eigener Verfahren ist es Teil der Arbeit, in der Literatur nach Möglichkeiten für den semantischen Vergleich von Code-Fragmenten zu suchen und eine Auswahl von geeigneten Mechanismen zu treffen.

Um noch bessere Ergebnisse zu erhalten, ist im zweiten Teil der Arbeit ein Verfahren zu entwickeln, mit dem die im ersten Schritt entworfenen Komparatoren kombiniert werden können. Hierbei soll mit Hilfe von Verfahren aus dem Maschinellen Lernen eine Hierarchie an Komparatoren gefunden werden, die die durch die symbolische Ausführung berechneten Ähnlichkeitswerte möglichst gut approximiert.

Das entwickelte Verfahren soll im Rahmen der Arbeit durch Anwendung auf Open-Source-Software-Archive evaluiert werden.

Meilensteine

  • Literaturrecherche zum semantischen Vergleich von Code-Fragmenten
  • Entwurf und Implementierung von Basis-Komparatoren
  • Entwurf und Implementierung von Verfahren zur Kombination der Basis-Komparatoren
  • Evaluation anhand von Open-Source-Projekten
  • Ausarbeitung

Literatur

  • Kamp, Marius: Entwicklung eines Werkzeugs zum Vergleich von Code-Fragmenten durch symbolische Ausführung. Masterarbeit, Lehrstuhl für Informatik 2, Friedrich-Alexander-Universität Erlangen-Nürnberg, Oktober 2014.
  • Kreutzer, Patrick: Evaluierung von Verfahren zur Detektion von Gruppen ähnlicher Quelltext-Änderungen. Masterarbeit, Lehrstuhl für Informatik 2, Friedrich-Alexander-Universität Erlangen-Nürnberg, November 2015.
  • Bauer, Veronika; Volke, Tobias; Jurgens, Elmar: A Novel Approach to Detect Unintentional Re-implementations. In: ICSME'14: International Conference on Software Maintenance and Evolution.
  • Nguyen, Anh; Nguyen, Hoan; Nguyen, Tien: A Large-Scale Study On Repetitiveness, Containment, and Composability of Routines in Source Code. In: MSR'16: International Conference on Mining Software Repositories
  • Aggarwal, Charu: Data Mining: The Textbook, Springer, 2015
watermark seal