Universität Stuttgart Institut für Softwaretechnik Abteilung Programmiersprachen Prof. Dr. Erhard Plödereder 30.07.2015 Diplomarbeit Erkennung semantischer Klone mittels Locality-Sensitive-Hashing charakteristischer Vektoren Detection of Semantic Clones by Locality-Sensitive Hashing of Characteristic Vectors Hintergrund Es gibt zahlreiche, unterschiedliche Verfahren zur Erkennung von Klonen in Programmquelltexten. In der aktuellen Forschung werden weitere Verfahren entwickelt, um auch funktional ähnliche Programmteile zu finden und semantische Äquivalenzen, die nicht als einfache strukturelle Übereinstimmungen erkennbar sind. Ein Ansatz eines Erkennungsverfahrens für semantische Klone wurde von Gabel, Jiang und Su vorgestellt und führt die Erkennung semantischer Klone auf eine spezielle AST-basierte Klonerkennung zurück, welche prototypisch in Form des Klonerkennungswerkzeugs Deckard umgesetzt ist. Deckard bildet Programmcodeteile auf sog. charakteristische Vektoren ab und erkennt Klone, indem im Vektorraum nah beieinander liegende Vektoren mittels Locality-Sensitive-Hashing zu Clustern gruppiert werden. Für die Erkennung semantischer Klone wurde die Vektorgenerierung von Deckard modifiziert und um einen weiteren Vektorgenerierungsschritt ergänzt, der zusätzliche charakterische Vektoren zur Repräsentation der Programmabhängigkeitsgraphen (PDGs) des Programmcodes erzeugt. Aufgabenstellung Um weitere Experimente mit dem Verfahren von Gabel, Jiang und Su und Vergleiche mit anderen Erkennungsverfahren für semantische Klone zu ermöglichen, soll der Klonerkennungsansatz im Rahmen dieser Diplomarbeit auf dem Programmanalysen-Framework Bauhaus aufsetzend nachimplementiert werden. Die Originalimplementierung des ASTbasierten Klonerkennungswerkzeugs Deckard ist offen einsehbar (unter Three-Clause-BSD-Lizenz) und kann für die Lösung der Aufgabe ggf. mit eingebunden oder als Anregungsquelle verwendet werden. Die Implementierungsmodifikationen und -erweiterungen zur Erkennung semantischer Klone sind nicht verfügbar und müssen aus dem dazu veröffentlichten Papier nachempfunden werden. Durch die Nachimplementierung in Bauhaus soll auch ermöglicht werden, dass zum einen Teile des Verfahrens leicht durch andere Strategien ersetzt und zum anderen Teile dieses Verfahrens in andere auf Bauhaus aufsetzende Klonerkenner übernommen werden können. Im Einzelnen sind folgende Funktionen zu realisieren: • Es ist zu evaluieren, inwieweit Teile der Originalimplementierung von Deckard in ein auf Bauhaus aufsetzendes Analyse-Tool integrierbar und auch für die Suche nach semantischen Klonen verwendbar sind. • Es ist entsprechend des Deckard-Ansatzes eine Generierung von charakteristischen Vektoren für AST-Teilbäume und Sequenzen von AST-Teilbäumen ausgehend von einem Bauhaus-IML-Graphen zu realisieren. Dabei soll konfigurierbar sein, welche IML-Knotentypen für die Zählung in den Vektoren herangezogen werden. • Es ist eine Clusterung einer gegebenen Menge charakteristischer Vektoren mittels Locality-Sensitive-Hashing zu implementieren, um eine Erkennung von Klonen zu realisieren. • Mit Hilfe der in den IML-Knoten gespeicherten Quelltextpositionen soll eine Rückprojektion der im Vektorraum aufgespürten Klone auf korrespondierende Quelltextteile erfolgen. • Zum zusätzlichen Aufspüren semantischer Klone ist eine Generierung weiterer charakteristischer Vektoren für die in Bauhaus bereitgestellte PDG-Sicht zu realisieren. Dem soll die im Papier von Gabel et al. beschriebene Auswahl interesanter PDG-Teilgraphen zugrunde liegen. Das resultierende Klonerkennungswerkzeug ist mit mindestens einem Open-Source-Softwaresystem zu validieren und mit dem in Bauhaus verfügbaren, AST-basierten Tool ccdiml hinsichtlich der Qualität der Klonerkennungsergebnisse und des Laufzeit- und Speicherbedarfs zu vergleichen. Es sind während der Bearbeitung ein Zwischenvortrag und zum Vorstellen der Ergebnisse ein Abschlussvortrag zu halten. Betreuer Prüfer Torsten Görg Tel: +49 (0)711 685-88317 Raum: 1.205 Email: [email protected] Prof. Dr. Erhard Plödereder Tel: +49 (0)711 685-88322 Raum: 1.211 Email: [email protected]
© Copyright 2024 ExpyDoc
