Semantische Code-Suche mittels Funktionssynthese

Student:Christian Spangler
Title:Semantische Code-Suche mittels Funktionssynthese
Type:bachelor thesis
Advisors:Kreutzer, P.; Kamp, M.; Philippsen, M.
State:submitted on December 21, 2017
Prerequisits:
Topic:

Hintergrund
Bei der Software-Entwicklung kommt es häufig vor, dass die zu implementierende Funktionalität bereits in der Vergangenheit von anderen Entwicklern implementiert und beispielsweise in Form von Open-Source-Bibliotheken veröffentlicht wurde. Statt diese Funktionalität erneut zu entwickeln, ist es oft ratsam, die bereits vorhandene Realisierung zu verwenden, beispielsweise um den Aufwand für die Entwicklung der Software zu reduzieren.
Bevor jedoch eine solche Implementierung verwendet werden kann, muss diese zunächst einmal gefunden werden. Zu diesem Zweck existieren Code-Suchmaschinen, die die Entwickler bei dieser Aufgabe unterstützen sollen. Etablierte Verfahren stützen sich dabei insbesondere auf syntaktische Merkmale, d.h. der Nutzer gibt beispielsweise eine Reihe von Schlüsselwörtern (Variablennamen, ...) an, nach denen die Suchmaschine suchen soll. Die Semantik des zu suchenden Codes bleibt dabei hingegen häufig unberücksichtigt, was die Qualität der präsentierten Suchergebnisse negativ beeinflussen kann. Zum einen werden in der Regel relevante, aber syntaktisch unterschiedlich implementierte Realisierungen nicht gefunden ("false negatives"), zum anderen werden unter Umständen syntaktisch ähnliche, aber semantisch unterschiedliche (und damit irrelevante) Ergebnisse präsentiert ("false positives").
Die Suche nach Code-Fragmenten auf Basis ihrer Semantik ist Gegenstand aktueller Forschung.

Thema
Am Lehrstuhl wird derzeit an einem Werkzeug entwickelt, das die semantische Ähnlichkeit von Code-Fragmenten bestimmen kann. Das Werkzeug verwendet dazu eine Reihe sog. Basiskomparatoren, die zwei Code-Fragmente jeweils hinsichtlich einer bestimmten Eigenschaft miteinander vergleichen (bspw. die Struktur der jeweiligen Kontrollflussgraphen oder die in den Fragmenten verwendeten Datentypen) und daraus einen Ähnlichkeitswert berechnen. Durch die Kombination mehrerer solcher Basiskomparatoren entsteht eine Hierarchie von Komparatoren, die einen kombinierten Ähnlichkeitswert berechnet. Um Hierarchien zu finden, die bekannte semantische Ähnlichkeitswerte möglichst genau approximieren, wird ein Verfahren aus dem Maschinellen Lernen eingesetzt. Die so gefundenen Hierarchien können anschließend eingesetzt werden, um in großen Software-Archiven nach Paaren semantisch ähnlicher Code-Fragmente zu suchen.
Ziel dieser Arbeit ist es, das implementierte Verfahren zur Ähnlichkeitsbestimmung um eine Möglichkeit zur semantischen Suche von Code-Fragmenten zu erweitern. Der Nutzer soll dabei eine Suchanfrage in Form von exemplarischen Eingabe-/Ausgabe-Paaren formulieren können. Das Werkzeug soll daraufhin in gegebenen Software-Archiven nach entsprechenden Code-Fragmenten suchen und diese als Ergebnis präsentieren.
Weil das bestehende Verfahren jeweils zwei Code-Fragmente miteinander vergleicht, muss zunächst aus der Spezifikation der Eingabe-/Ausgabe-Paare eine Java-Methode synthetisiert werden, die das durch die Beispiele beschriebene Verhalten möglichst genau realisiert. Mit Hilfe des Verfahrens zur Ähnlichkeitsbestimmung kann die so erzeugte Methode dann mit den Methoden aus den gegebenen Software-Archiven verglichen werden, um semantisch ähnliche Implementierungen zu detektieren.
Im Rahmen der Arbeit soll zunächst die Literatur nach möglichen Verfahren zur Synthese von Code-Fragmenten durchsucht werden. Ein geeignet erscheinendes Verfahren soll anschließend prototypisch implementiert und die Anwendbarkeit des Verfahrens in Zusammenspiel mit der Ähnlichkeitsberechnung durch die Anwendung auf Open-Source-Archive evaluiert werden. Teil der Arbeit ist es dabei auch, eine Möglichkeit zur Spezifikation von Eingabe-/Ausgabe-Paaren zu entwerfen und zu implementieren. Die gewählte Darstellung soll dabei auch die Spezifikation zusammengesetzter Datentypen (Arrays, Objekte) erlauben.

Meilensteine

  • Literaturrecherche nach Möglichkeiten zur Synthese von Code-Fragmenten
  • Implementierung eines Verfahrens zur Spezifikation von Eingabe-/Ausgabe-Paaren
  • Implementierung eines geeignet erscheinenden Verfahrens zur Code-Synthese
  • Evaluation anhand von Open-Source-Projekten
  • Ausarbeitung

Literatur

  • Kretschmer, Adrian: Implementierung und Evaluierung einer Hierarchie von Verfahren zum semantischen Vergleich von Code-Fragmenten. Bachelorarbeit, Lehrstuhl für Informatik 2, Friedrich-Alexander-Universität Erlangen-Nürnberg, 2016.
  • Gulwani, Sumit: Synthesis from Examples: Interaction Models and Algorithms. In: SYNASC'12: International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, 2012, pp. 8–14.
  • Reiss, Steven P.: Semantics-Based Code Search. In: ICSE'09: International Conference on Software Engineering, 2009, pp. 243-253.
  • Stolee, Kathryn T.; Elbaum, Sebastian; Dobos, Daniel: Solving the Search for Source Code. In: TOSEM'14: Transactions on Software Engineering and Methodology, 2014, 23(3), pp. 26:1-26:45.
watermark seal