Consolidation de correspondances

La recherche de facteurs répétés de sous-arbres frères telle que présentée dans le chapitre précédent montre en pratique ses limites, même avec l’usage de certains profils d’abstraction. Si certains profils permettent de gérer des cas d’obfuscation comme la réécriture d’expressions (abstraction des petits sous-arbres) ou la modification de structures de contrôle (suppression des nœuds représentant ces structures), d’autres opérations d’éditions conduisent à l’obtention de valeurs de hachage différentes pour un sous-arbre et son clone obfusqué.En particulier, l’ajout ou la suppression de code inutile n’est pas systématiquement décelable lors d’une étape de normalisation de l’arbre de syntaxe. Il en est de même pour certaines opérations de transposition de code. Ces opérations conduisent à l’ajout, la suppression ou le déplacement de sous-arbres de volume plus ou moins important.= si(¬cond, sinon, alors). Même l’utilisation d’un profil d’abstraction éliminant les structures conditionnelles (abstr(A) = (cond, alors, sinon, abstr(AUn ensemble d’instructions inter-dépendantes d’une fonction peut être externalisée dans une nouvelle fonction qui sera appelée depuis la fonction source.

L’externalisation (ou factorisation) se matérialise sur l’arbre de syntaxe par la migration des instructions de la fonction source vers la fonction externalisée avec l’introduction de paramètres de fonction correspondant auxL’opération réciproque de développement consiste à remplacer l’appel d’une fonction par le corps de ladite fonction. Le corps de la fonction nécessite généralement quelques adaptations au contexte local : changement de noms de variables locales, remplacement des instructions de retour par des affectations, remplacement des identificateurs des paramètres par leur valeur d’argument (cf figure 7.1)… Ces petites modifications ne permettent souvent pas d’obtenir une correspondance exacte entre le corps développé et le corps original : des fossés de non- correspondance sont présents. Il s’agit de regrouper ces correspondances séparées par des fossés en une unique correspondance.L’extension de correspondances sur des arbres de syntaxe est quant à elle un sujet qui été peu exploré. On pourra citer la méthode de propagation de correspondances utilisée par CloneDr [91]. Celle-ci consiste, lorsque deux arbres (ou chaînes d’arbres frères) ont été reportés comme similaires, à tenter de prolonger systématiquement la correspondance à leurs parents.

Les sous-arbres ayant pour racine respective chacun des deux parents sont donc comparés en utilisant une méthode d’alignement sur arbres comme celles décrites en section 5.5. Si cette approche permet la détection en tant que clones de deux arbres possédant au moins un sous- arbre identique avec des modifications sur les autres sous-arbres frères, plusieurs niveaux de propagation pourraient être nécessaires pour permettre la mise en valeur de certains clones. D’autre part, le coût de détermination de distance d’édition entre deux arbres peut devenir prohibitif pour de grands sous-arbres.Cobena [42] a également utilisé des méthodes de propagation à des nœuds parent pour la recherche de paires de sous-arbres correspondants dans des arbres de documents XML. La problématique demeure néanmoins assez différente de la notre car consistant à déterminer un delta entre différentes versions d’un même document XML, chaque sous-arbre ne pouvant cor- respondre au plus qu’avec un seul sous-arbre de l’autre version. Dans le cadre de la recherche de correspondances sur des sous-arbres de syntaxe provenant d’analyse de code source, l’uti- lisation de clones chevauchants n’est pas sans intérêt, une même zone de code pouvant être dupliquée au sein d’un même projet, voire d’une même unité de compilation.paires constituent des germes qui serviront de base à l’extension des correspondances. L’heu- ristique de consolidation de correspondances utilise alors deux étapes principales.

L’étape de fusion consiste à regrouper les correspondances dont l’exemplaire sur l’arbre requête est proche. La seconde, l’étape de propagation, consiste à étendre une correspondance couvrant un volume important d’une fratrie de sous-arbres d’un arbre de la base à son sur-arbre parent. Ces deux étapes sont menées itérativement depuis les germes de forte profondeur des arbres de la base vers les germes de faible profondeur : elles permettent d’agglutiner des germes au sein de correspondances de volume croissant. Les étapes de fusion et propagation permettent non seulement la consolidation de sous-arbres frères, ce qui était déjà proposé d’une certaine manière par [91] ou en 10.4.4 lorsque les sous-arbres étaient consécutifs dans la fratrie, mais également le regroupement de sous-arbres cousins plus ou moins éloignés.Nous nous intéressons ensuite à la consolidation des correspondances à travers les graphes d’appels afin de gérer des opérations d’obfuscation par développement ou factorisation de fonctions. Ainsi, si une correspondance occupe un volume conséquent d’une fonction, celle-ci pourra être propagée à l’ensemble de la fonction et par la suite à ses fonctions appelantes.