Fonctions de hachage sur l’espace des sous-arbres

Quelques méthodes de hachage de sous-arbres

Métriques

Les métriques sur des unités structurelles du code source sont des mesures permettant de quantifier certaines propriétés du code. Elles s’expriment le plus souvent dans un espace vectoriel réel. Nous passons maintenant en revue quelques unes des métriques les plus couramment utilisées. Métriques de quantification de la complexité du code et du style de programmation Mesurer la complexité du code source a toujours été une préoccupation majeure en ingénierie logicielle. Ces métriques permettraient d’estimer la complexité du code et donc son coût de maintenabilité. Nous présentons ici les métriques de Halstead et la métrique de complexité cyclomatique pour finir sur une métrique basée sur le vecteur de comptage des types de nœuds. La figure 9.1 présente deux versions d’un court code de calcul de moyenne sur lesquels les métriques présentées ont été appliquées. Métriques de Halstead Les métriques de Halstead [108] sont calculées à partir du comptage des opérateurs et opérandes totaux et distincts présents dans l’unité structurelle analysée : le vecteur V = (α, α,β, ¯ β¯) de l’unité comportant α opérateurs distincts, α¯ opérateurs totaux, β opérandes distincts et β¯ opérandes totaux est calculé. Des mesures de longueur (α¯ + β¯), de vocabulaire (α+β), de volume ((¯α+β¯) log2 (α+β)), de difficulté (αβ¯ 2β ) et d’effort (produit du volume et de la difficulté) sont dérivées de ce vecteur. Les opérateurs sont alors définis comme l’ensemble des opérateurs arithmétiques, des appels de fonction et des opérations d’affectation. Les opérandes sont quant à eux les variables locales, membres de structures et constantes. Il est aisé de constater que l’ajout ou la suppression de code inutile ainsi que la réécriture d’expressions peut avoir un impact important sur le vecteur V . D’autre part, il existe des risques importants que plusieurs unités structurelles de vecteurs accidentellement proches n’abritent aucune similarité réelle. 

Complexité cyclomatique de McCabe

McCabe a proposé une métrique [110] sur le graphe de contrôle de flux d’une unité structurelle. Un tel graphe représente l’ensemble des instructions d’un programme (nœuds), deux instructions étant liées par une arête s’il existe un chemin d’exécution où ces deux instructions sont exécutées séquentiellement. La complexité cyclomatique C est définie par C = E − N + 2P où E est le nombre d’arêtes, N le nombre de nœuds et P le nombre de composantes connexes du graphe. Cette valeur reflète le nombre d’expressions conditionnelles issues de structures de contrôles présentes dans le code. Si la complexité cyclomatique peut être difficilement réduite, une augmentation artificielle par l’ajout de structures de contrôle inutiles (cf 4.6) est possible. Au-delà d’une analyse statique, une détermination de la complexité cyclomatique dynamique par le suivi des chemins d’exécution serait plus fiable pour localiser les conditionnelles suspectées invariantes. D’autre part, cette métrique dispose d’un pouvoir discriminateur réduit : l’espace de valeurs de complexité cyclomatique est trop faible afin de pouvoir disposer de groupes de sous-arbres d’effectifs suffisamment petits. Il est en effet rare de trouver des fonctions dont la complexité cyclomatique est supérieure à 20.

Vecteur de comptage de nœuds ou de sous-arbres

Étant donnée une unité structurelle représentée par un arbre de syntaxe, il est possible d’exprimer le nombre de chaque type de nœuds présents au sein de cet arbre : nous pouvons ainsi en extraire un vecteur de comptage de nœuds. La taille de ce vecteur, représentant le 9.1. Quelques méthodes de hachage de sous-arbres 156 nombre de types de nœud différents peut être réduite par une opération d’abstraction des types : nous traiterons de ce procédé en 9.2. Ce vecteur de comptage peut être généralisé au comptage des différents sous-arbres de taille ou de hauteur bornée. Cette technique est notamment employée par l’outil de recherche de similitudes Deckard [70] qui génère pour chaque sous-arbre à hacher un vecteur caractéristique comptant les petits sous-arbres inclus. Les différents sous-arbres vectorisés sont ensuite regroupés en utilisant une technique de hachage localement sensible (Locality Sensitive Hashing, LSH) [52]. Cette technique permet de regrouper des vecteurs de distance faible et donc des sous-arbres suffisamment voisins dans l’espace vectoriel des effectifs de sous-arbres caractéristiques. Tout comme la cardinalité du nombre de k-grams pour k suffisamment faible est assez réduite par rapport à la cardinalité théorique des |Σ| k k-grams, il existe également un nombre limité de petits arbres, qu’ils soient définis par une taille k ou une hauteur h limite. Il est toutefois nécessaire de maintenir la taille ou la hauteur limite suffisamment basse pour restreindre la taille des vecteurs à manipuler. L’utilisation d’un vecteur de comptage est totalement insensible aux opérations de transposition de code. Ce comportement ensembliste peut également induire des cas de structures non-similaires ayant un vecteur de comptage identique ou proche selon une fonction de hachage localement sensible. D’autre part, des modifications localisées comme la réécriture d’expressions peuvent modifier le type des petits sous-arbres considérés pour le comptage et donc le vecteur généré. L’ajout ou la suppression de code inutile peut également avoir une influence sur le vecteur. Le vecteur de comptage peut également être projeté sur une unique valeur entière en sommant ses valeurs coefficientées par un représentant entier aléatoire de chacun des types (cf 9.1.2). Cette méthode se rapproche alors d’un hachage exact dans la mesure où les valeurs ne peuvent être comparées autrement que par une égalité stricte.