<  Retour au portail Polytechnique Montréal

Analyse des propriétés structurelles et computationnelles des clones logiciels

Thierry M. Lavoie

Mémoire de maîtrise (2011)

[img]
Affichage préliminaire
Télécharger (543kB)
Citer ce document: Lavoie, T. M. (2011). Analyse des propriétés structurelles et computationnelles des clones logiciels (Mémoire de maîtrise, École Polytechnique de Montréal). Tiré de https://publications.polymtl.ca/660/
Afficher le résumé Cacher le résumé

Résumé

RÉSUMÉ La détection des clones est une discipline dynamique du génie logiciel consacrée à la recherche et l’analyse de similitude à l’intérieur des logiciels. Ces similitudes peuvent être à l’intérieur de tous les artefacts d’un produit logiciel, mais cette discipline se consacre principalement à celles présentes dans le code source. Les travaux présentés dans ce mémoire sont consacrés à l’étude de certaines propriétés structurelles et computationnelles des clones logiciels syntaxiques et lexicaux ; les clones sémantiques ne sont pas formellement abordés dans ces travaux. Dans un premier temps, une analyse des relations structurelles entre les clones a été réalisée. Les clones considérés sont produit par la méthode de détection des clones basée sur les métriques d’AST. Contrairement à la très grande majorité des autres travaux présents dans la littérature, qui s’intéressent exclusivement aux fonctions ou aux méthodes comme unité minimale de clonage, ces travaux s’intéressent à la fois aux relations impliquant des fonctions et des blocs, engendrant ainsi trois relations d’intérêt : les clones fonction à fonction, bloc à bloc et fonction à bloc. Les conclusions de l’étude indiquent clairement l’intérêt de s’intéresser à ces relations et l’insuffisance de la réduction de l’espace de recherche composé de tous les fragments de code d’un programme à celui restreint aux fonctions. Les résultats présentés dépendent seulement partiellement de la méthode ; l’intérêt des relations présentées est indépendant tandis que les résultats spécifiques présentés sont dépendants. Dans un second temps, une étude a été réalisée sur l’applicabilité d’algorithmes écrits sur GPU pour le problème de postfiltrage des clones. Le filtrage est une pratique répandue dans les outils de détection de clonage pour améliorer la précision des résultats. La technique choisie ici est celle du filtrage avec le calcul de la plus longue sous-séquence commune (LCS). Cet algorithme se parallélise aisément et se porte sans heurt sur une architecture GPU; il est donc un candidat idéal. La conversion de l’algorithme classique de programmation dynamique pour le calcul de la LCS est présenté avec plusieurs considérations techniques pour faciliter son implémentation. Les résultats de l’application de l’algorithme sur deux systèmes de grande taille, Tomcat et Eclipse, sont présentés. Les temps d’exécution de l’algorithme sur GPU sont inférieurs à ceux obtenus sur CPU, même si le facteur d’accélération total est relativement petit (de l’ordre de 1.2). Cette accélération est inférieure aux attentes et quelques pistes d’explication sont fournies. Dans un dernier temps, la réalisation d’oracles automatisés basés sur la distance de Levenshtein est présentée. Pour la détection des clones, un oracle consiste en un ensemble de clones jugé exact pour fin de comparaison de différents outils. Ce résultat est une grande nouveauté puisqu’il prouve l’applicabilité de la distance de Levenshtein sur de grands systèmes en utilisant une quantité raisonnable de ressources. Pour arriver à calculer ces oracles, les fragments des systèmes sont insérés dans un arbre de métriques qui se construit en répartissant les fragments en fonction de leur distance de Levenshtein. L’utilisation des arbres de métriques dans des expériences de détection des clones est une nouveauté et les oracles obtenus sont prometteurs. Différentes statistiques sur les oracles sont présentées. On remarque selon ces chiffres que le nombre de pairs de clones est très petit par rapport au nombre de paires total possible dans un système. Cela explique le gain de performance notable de la nouvelle méthode présentée par rapport à une recherche exhaustive.---------- ABSTRACT Clone detection is a widely known research area of software engineering, which goal is to enhance programs understanding and detect potential bugs as well as re-factoring opportunities. The focus of this research area is on finding and analyzing self-similarities in source code. This thesis focuses on structural and computational properties of clones. First, a structural classification scheme of clones is presented. Many studies have researched properties of function clones. These studies did not take in consideration the possible presence of clones in smaller or bigger computational unit. Moreover, they relied on the hypothesis that clone code preserves completely the syntactic structure between fragments. To challenge this hypothesis, classification scheme and algorithm are presented in this work and are applied to clone sets of different systems. Results show that clones can belong to at least three types of structural relationship: method-method, block-block, and method-block. Examples are provided and support the usefulness of such classification. As a result, it mitigates the choice of performing clone analysis only on functions and suggest to focus on other computational units. Second, an attempt to port some clone-related computation to GPU is presented. To enhance results quality, it is often required to filter clone analysis results with precise but computationally expensive algorithm. The length of the longest common sub-sequence is a good candidate for such a filter and is used by many in the literature. However, its computational cost is prohibitive in many cases. To overcome the cost, a port on GPU of the algorithm specialized for clone detection is proposed. The observed execution times suggest however that little gain is obtained for clone filtering problems. Discussion of this unexpected result is provided along with ideas of other possible GPU applications to clone detections. Finally, an original algorithm to compute clone oracles is presented. An oracle is a set of clones presumed to be of good quality and used to benchmark clone detection tools results quality. This result is of great importance to the clone community as it provides the first automatically-generated oracle based on an objective algebraic criterion. It also gives insight on computational difficulties of computing good clone results. The key point of the technique is to observe the computational bottleneck of exhaustive search is the space search size and not the distance computation, even for complex distance. Using this knowledge, a metric tree-based algorithm is presented to compute oracles. Details of the computed oracles are presented. After these topics discussions, the thesis is concluded with future research possibilities.

Document en libre accès dans PolyPublie
Département: Département de génie informatique et génie logiciel
Directeur de mémoire/thèse: Ettore Merlo
Date du dépôt: 17 nov. 2011 15:33
Dernière modification: 01 sept. 2017 17:33
Adresse URL de PolyPublie: https://publications.polymtl.ca/660/

Statistiques

Total des téléchargements à partir de PolyPublie

Téléchargements par année

Provenance des téléchargements

Actions réservées au personnel