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

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.