Experimental Investigation of the Program Clone Detection Algorithms Effectiveness / Eksperymentalne badanie skuteczności algorytmów wykrywania klonów programów

Abstract

The paper reviews existing algorithms and methods for detecting program clones. The authors conducted a series of experiments on detecting clones in the texts of educational project programs written in C++. For this purpose, a software application was created - a program clone analyzer. It implements the Jaccard Similarity, Running-Karp-Rabin Greedy-String-Tiling (RKR-GST) Similarity and Winnow (Winnowing) Similarity algorithms and provides the ability to perform 1:1 and N:M program text comparisons. During the experiment, the application was used to measure the running time of the algorithms and evaluate the time efficiency based on SR-estimates. The results obtained allow for a reasonable choice of clone detection algorithms taking into account their time efficiency in a given software and hardware environment.

W rozdziale dokonano przeglądu istniejących algorytmów i metod wykrywania klonów programowych. Autorzy przeprowadzili szereg eksperymentów nad wykrywaniem klonów w tekstach programów edukacyjnych napisanych w języku C++. W tym celu stworzono aplikację – analizator klonów programowych. Implementuje ona algorytmy podobieństwa Jaccarda, podobieństwa Running-Karp-Rabin Greedy-String-Tiling (RKR- -GST) oraz podobieństwa Winnow (Winnowing) i umożliwia przeprowadzanie porównań tekstów programów w proporcjach 1:1 i N:M. W trakcie eksperymentu aplikacja została wykorzystana do pomiaru czasu działania algorytmów i oceny efektywności czasowej na podstawie estymacji SR. Uzyskane wyniki pozwalają na rozsądny wybór algorytmów wykrywania klonów, biorąc pod uwagę ich wydajność czasową w danym środowisku programowym i sprzętowym.