Métriques de similarité

 Métriques directes pour la comparaison d’arbres de syntaxe

Les arbres de syntaxe, comme explicité en 9.1.1, peuvent faire l’objet d’une quantification vectorielle de certaines propriétés syntaxiques et sémantiques. Ces métriques sont facilement modifiables par certains procédés d’obfuscation.

En revanche, lorsque du code copié sans volonté obfuscatoire est recherché, celles-ci peuvent présenter un intérêt afin de constituer des groupements préalables dont les paires pourront être analysées avec plus d’attention. La détermination de distance d’édition sur les arbres (cf 5.5) permet parallèlement la détermination de correspondances approchées avec fossés au prix d’une complexité temporelle quadratique en lexèmes traités. Le calcul de distance d’édition est donc utilisable plutôt dans une optique d’approfondissement de la comparaison d’unités que pour une préselection de celles-ci.

Métriques directes pour la comparaison de chaînes de lexèmes

Quantifier la similarité entre deux chaînes de lexèmes peut être réalisé en utilisant plusieurs types de distance dont leur distance de Hamming ou leur distance d’édition. La distance de Hamming [12] nécessite la simple comparaison de lexèmes de même indice alors que la distance d’édition requiert l’utilisation de méthodes d’alignement par programmation dynamique comme décrites dans le chapitre 5, de complexité temporelle quadratique.

Lorsque la détermination de la similarité deux à deux de k chaînes de n lexèmes est requise, calculer la distance d’édition pour toutes les paires nécessite O(k 2n 2 ) opérations. La distance de Hamming n’est, elle, pas adapté à la comparaison de chaînes pouvant faire l’objet d’insertion ou de suppression de lexèmes. La table de suffixes d’un ensemble de chaînes peut être mise à profit pour quantifier leur similarité. Ainsi, lorsque deux suffixes de chaînes différentes sont proches dans la table de suffixes et partagent un préfixe commun de longueur L, les chaînes sous-jacentes partagent au moins un facteur de longueur L.

Des chaînes partageant de multiples suffixes proches 227 12. Métriques de similarité dans la table de suffixes partagent autant de facteurs communs. De cette observation, nous déduisons deux heuristiques de calcul de matrice de similarité sur un ensemble de k chaînes. La première, inspirée de [17] quantifie les alternances dans la table de suffixes. Quant à la seconde, elle permet le calcul d’une matrice de similarité creuse, seules les paires de chaînes de similarité notable étant considérées.

Quantification des alternances sur table de suffixes

Pourquoi quantifier l’alternance ? Considérons deux chaînes de lexèmes u et v dont la table de suffixes t = SA ({u, v}) est calculée. Si u et v possèdent des suffixes communs de longueur non nulle, ceux-ci sont ordonnés dans t selon l’ordre lexicographique de u et v. Si u = v, par convention, les suffixes de u précèdent ceux de v dans la table t. Dans cette situation, il y a alternance parfaite de suffixes égaux de u et de v. Si l’on substitue à chaque suffixe sa chaîne d’appartenance dans la table, nous obtenons t ′ = (u)(v)(u)(v)· · ·(u)(v). De manière générale, t ′ est de la forme (u) i1 (v) j1 (u) i2 (v) j2 · · ·(u) iz (v) jz avec tous les ik et jk non nuls pour k ∈ [1..z], sauf éventuellement pour i1 et jz.

Quantification des suffixes sur fenêtre

Déterminer exhaustivement les valeurs de similarité d’une matrice pour un ensemble conséquent de chaînes est particulièrement coûteux : il pourrait être préférable de ne s’intéresser qu’aux valeurs de similarité pour les paires de chaînes présentant le plus haut niveau de ressemblance. À cet effet nous introduisons une métrique quantifiant la similitude entre deux chaînes par la proximité, bornée par une fenêtre, de leurs suffixes dans la table de suffixes.

Découpage de deux chaînes en facteurs communs.

Afin d’introduire la métrique, nous considérons le problème du découpage de chaînes en facteurs commun. Il s’agit pour deux chaînes u et v de trouver une décomposition en facteurs communs maximisant la couverture. Celle-ci n’est pas unique : une stratégie exposée par l’algorithme de Greedy String Tiling exposé en 8.4 consiste à identifier les facteurs communs du plus long au plus court. Plus qu’aux facteurs eux-mêmes, nous nous intéressons à leur couverture en nombre de lexèmes des deux chaînes. À cet effet nous proposons la méthode suivante.