Factorisation de chaînes de lexèmes

 Aperçu général

Problématique et motivations

La recherche de similarité sur un ensemble de chaînes de lexèmes peut être menée soit par des méthodes de comparaison globale, soit par la recherche de similitudes sur toutes les paires de l’ensemble. Dans le second cas la complexité temporelle est plus défavorable même si cela permet l’usage de méthodes algorithmiques tel que l’alignement de séquences (cf chapitre 5) permettant la recherche de correspondances approchées. Pour la comparaison globale, des structures d’indexation de suffixes (cf chapitre 6) permettent la recherche de groupes de facteurs répétés et donc de groupes de correspondances exactes. Toutefois la recherche de facteurs répétés bruts comporte certaines limitations : elle ne tient notamment pas compte de relations d’inclusion ou de chevauchement entre occurrences reportées. En effet, si xyz participe aux facteurs répétés xy et yz, il serait intéressant de considérer le chevauchement de ces deux facteurs : y. La factorisation doit donc être réalisée à plusieurs niveaux. D’autre part, il serait avantageux de pouvoir localiser des similarités et déduire une métrique afférente offrant une résistance aux opérations de factorisation et de développement de fonctions. À cet effet, nous considérons comme unité syntaxique de comparaison la fonction. Deux fonctions doivent être considérées comme similaires si celles-ci permettent l’exécution de la même séquence d’instructions, quelles que soient les fonctions intermédiaires appelées. Dans un premier temps, nous cherchons à obtenir un graphe d’appels factorisé de l’ensemble des projets traités. Le graphe d’appels factorisé sera ensuite analysé afin de déduire une métrique de similarité entre fonctions basée sur leur couverture de code commune. 7.1.2 Quelques définitions préalables Définition 7.1. (Lexèmes primitifs et lexèmes d’appel) Une fonction est représentée par une séquence de lexèmes composée de lexèmes primitifs et de lexèmes d’appel. Les lexèmes primitifs (Σ p ) sont dérivés du lexique du langage traité tandis que les lexèmes d’appel (Σ c ) représentent chacun un appel vers une fonction spécifique du projet. L’ensemble des projets étudiés est ainsi préalablement représenté sous la forme de fonctions de séquences de lexèmes primitifs et d’appel, ce qui implique la connaissance du graphe d’appels des projets (cf 3.2.3). Une analyse syntaxique légère est donc nécessaire pour le découpage des projets en fonctions et une résolution des appels de fonctions doit être menée. Cette étape peut être rendue plus difficile voire impossible par l’usage de certains procédés d’obfuscation visant à masquer les liens d’appel (cf 4.9.1). Les lexèmes primitifs peuvent correspondre aux différents termes du lexique du langage avec un certain niveau d’abstraction. Généralement les identificateurs et types sont abstraits afin de gérer les obfuscations à base de renommage de types ou de variables. Certains motsclés peuvent être confondus par un unique représentant. D’autres mots-clés, méta-informatifs, peuvent être également tout simplement ignorés (comme par exemple les modificateurs de visibilité de certains langages). 

Factorisation de chaînes de lexèmes

Les liens d’appel vers des fonctions de bibliothèque, i.e. des fonctions dont l’implantation n’est pas présente au sein des projets, sont représentés par un lexème primitif spécifique à chaque fonction appelée. Il est en effet nécessaire de limiter le processus de factorisation au niveau des fonctions de projet dans un souci de maîtrise de la complexité. Il n’est néanmoins pas inimaginable qu’un obfuscateur puisse développer un appel d’une fonction de bibliothèque par le code source de son implantation lorsque celui-ci est disponible. L’utilisation d’un modèle unidimensionnel par séquences de lexèmes primitifs et d’appels est gênant pour la manipulation d’appels de fonction imbriqués. L’arbre des appels de fonction correspondant à une expression est donc préalablement linéarisé par des instructions simples d’affectation des appels imbriqués à des variables temporaires. Ainsi l’expression a = min(f(k1), g(k2, h(k3))) est linéarisé par tmp1 = f(k1) ; tmp2 = h(k3) ; tmp3 = g(k2, tmp2) ; a = min(tmp1, tmp3) ;. Il n’existe cependant pas de forme linéarisée unique. Définition 7.2. (Fonctions primitives et fonctions composées) Nous distinguons deux types de fonctions de séquences de lexèmes : 1. les fonctions primitives constituées uniquement de lexèmes primitifs sur Σ p∗ ; 2. les fonctions composées constituées uniquement de lexèmes d’appel sur Σ c∗ Pour la suite, nous considérons uniquement des fonctions primitives et composées. Une fonction mixte est donc préalablement transformée en fonctions composée par l’externalisation des séquences de lexèmes consécutifs pour créer de nouvelles fonctions primitives.

Aperçu de la méthode de factorisation

Afin d’obtenir le graphe d’appels factorisé d’un ensemble de projets, nous réalisons la factorisation des chaînes de lexèmes primitifs consécutifs des projets considérés. Cette factorisation est réalisée par la détermination de facteurs répétés maximaux sur les chaînes de lexèmes primitifs : un tel facteur est remplacé par un lexème d’appel dans sa chaîne originale, et, si nécessaire, une nouvelle fonction contenant ce facteur est externalisée. Par exemple, les chaînes de lexèmes primitifs f1 = abcdefgh et f2 = ijkabcdebcd disposent d’un facteur répété abcde qui est externalisé dans une fonction f3 = abcde. Chaînes de lexèmes primitifs et d’appels n’étant pas mélangées, nous obtenons f1 = f3f ′ 1 et f2 = f ′ 2 f3f ′′ 2 avec f ′ 1 = fgh, f′ 2 = ijk,f′ 3 = bcd. Il s’avère qu’une seule itération de factorisation est généralement insuffisante : les fonctions issues de facteurs communs et celles issues du découpage peuvent potentiellement accueillir elles-aussi, des facteurs répétés. Pour l’exemple traité, f3 aurait pu être factorisé en af′ 3 e. Il est toutefois nécessaire de fixer un seuil minimal t à la longueur des facteurs répétés factorisés afin d’éviter la création de fonctions liées à des chaînes de lexèmes trivialement répétées en nombre dans le code (déclarations de variable, instruction fréquentes…). Lorsque l’itération courante de factorisation ne permet pas de trouver un facteur répété de longueur d’au-moins t, l’algorithme est arrêté. Nous obtenons alors finalement un jeu de fonctions feuilles qui sont des chaînes de lexèmes primitifs ainsi que de fonctions internes composées de lexèmes d’appel. Nous en déduisons un graphe d’appels factorisé que nous utilisons afin de visualiser les zones de code similaires 7.1. Aperçu général 112 entre projets ainsi que pour calculer une métrique de similarité entre fonctions du code. Cette métrique a pour vocation d’offrir une résistance acceptable aux opérations d’obfuscation par ajout ou suppression de code inutile ainsi que par la factorisation ou le développement de fonctions