FR2914081A1 - Procede de protection de documents numeriques contre des utilisations non autorisees. - Google Patents

Abstract

On identifie pour un document numérique à protéger constituant un code source un langage de programmation L défini par une grammaire GL; on associe audit langage de programmation L un module de grammaire à actions ; on réalise une caractérisation structurelle du code en une seule passe d'analyse syntaxique à partir du module de grammaire à actions ; on construit un dictionnaire de grammaire GDL associé au langage de programmation et comprenant un ensemble de termes structurels tels que chacun de ces termes est associé à une règle ou un ensemble de règles; on transforme le code source en une séquence structurelle (RL, TL, GDL) comprenant l'ensemble des termes structurels et le dictionnaire GDL de grammaire du langage L ; on procède de la même manière à la transformation d'un document numérique à analyser en une séquence structurelle (RL, TL, GDL) et on mesure le taux de plagiat entre le code source du document numérique à protéger et le code source du document numérique à analyser à l'aide d'une quantification du taux d'alignement entre les séquences structurelles respectives des codes sources du document numérique à protéger et du document numérique à analyser.

Description

Procédé de protection de documents numériques contre des utilisations non

autorisées Domaine de l'invention La présente invention a pour objet un procédé de protection de documents numériques contre des utilisations non autorisées.

Dans un monde dominé par la technologie de l'information, les 10 logiciels jouent un rôle majeur dans la prospérité d'une entreprise et ils sont considérés comme la colonne dorsale de son activité. Ils matérialisent souvent le savoir faire et la propriété intellectuelle d'une entreprise. Ainsi un logiciel créé par une entreprise représente un patrimoine et un actif très important pour cette dernière. Malgré cette importance ce patrimoine 15 est souvent peu ou mal protégé. Il est primordial pour une entreprise de veiller à ce que ses logiciels ne soient pas "totalement" ou "partiellement" diffusés sans son accord. Ceci afin que son facteur différentiateur (par rapport à la concurrence) et sa valeur ajoutée pour ses clients ne soient mis en cause. 20 Malheureusement il n'existe pas encore de moyens techniques permettant à ces entreprises d'être averties à chaque tentative de diffusion illicite de leurs logiciels.

Art antérieur 25 Dans le cas où un logiciel a été signalé comme potentiellement une reprise d'un autre logiciel, la confrontation entre le logiciel d''origine et le logiciel suspect est souvent effectuée par un expert humain qui a pour vocation de déterminer l'ampleur du piratage. Cette expertise est 30 effectuée sur des éléments de base constituant un logiciel, tel que l'architecture des programrnes, la documentation associée au logiciel, et le code objet résultant de la compilation de son code source. Ce dernier représente le constituant le plus exploité lors des expertises. Les documents code source sont structurés selon une grammaire5 précise, où chaque ligne joue un rôle dans le résultat de l'exécution du programme qui lui est associé, et par conséquent elle est porteuse de plusieurs sources d'informations. On a déjà envisagé de transformer le contenu d'un code source écrit dans un langage de programmation de haut niveau en un code écrit dans un langage d'un niveau d'abstraction moins élevé par rapport à celui du langage source, tout en préservant la signification du code. Il existe trois domaines d'application où l'accès par le contenu au code source est une étape nécessaire. Le premier domaine est le remaniement des logiciels car l'évolution constante de ces derniers nécessite une maintenance continue de leurs codes source. La duplication du code est le principal problème rencontré lors de la maintenance où la quantité du code dupliqué est en générale entre 5% et 10% et peut aller jusqu'à 50 h. Le développement d'outils de détection du code dupliqué s'avère nécessaire afin de faciliter les opérations de remaniement des logiciels pour d'éventuelles nouvelles fonctionnalités. Le second domaine est l'identification de l'auteur d'un programme en se basant sur un ensemble de métriques caractérisant le style de programmation que peut contenir le code source. Parmi les applications qui peuvent bénéficier de cette identification, on peut citer le milieu juridique et universitaire notamment pour les réclamations des droits d'auteur, le milieu industriel et plus précisément les systèmes de veille sécuritaire en temps réel. La tâche principale de ce genre de systèmes consiste à détecter les intrusions dont le style de programmation est différent des styles des programmeurs locaux. Le troisième domaine est la détection de cas de plagiats clans le code. Parker et Hamblen définissent le plagiat du code source comrne étant une reproduction d'un code à partir d'un code existant, avec un nombre restreint de changements.

L'évolution d'Internet et les moteurs de recherche cornme Google, sont deux facteurs majeurs qui facilitent l'obtention du code source, favorisant ainsi l'apparition et la multiplication des logiciels Open-Source, et par conséquent, l'accès libre au code source rend possible le plagiat du logiciel sans respecter les licences associées.

Les méthodes et approches permettant de représenter le contenu d'un code source, doivent conserver le maximum possible l'information que véhicule le code. A l'inverse des documents textuels en langages naturels, le contenu des documents code source peut être projeté dans des espaces de représentation différents. Cette différence réside dans le fait d'utiliser des approches variées, telles que les approches statistiques, conceptuelles ou structurelles. Les particularités d'un code source, offrent un grand choix de modèles permettant de caractériser son contenu. Deux principales approches émergent de cette variété de modèles : 10 des approches basées sur l'information purement statistique, et des approches basées sur l'information structurelle. Le principe des méthodes basées sur le modèle vectoriel se fonde sur le calcul d'un ensemble de métriques qui singularisent chaque code source. Tous les codes sont donc caractérisés par un vecteur de m valeurs et 15 représentés dans un espace à m dimensions. L'ensemble de ces vecteurs est utilisé par un système de reconnaissance de forme qui consiste à calculer les distances statistiques et à mesurer la corrélation entre ces vecteurs caractéristiques. Dans le cas d'une grande base, où l'ensemble de ses codes est représenté par un nuage de points dans l'espace vectoriel, 20 l'utilisation des différentes méthodes de classification et de clusterisation s'avère indispensable dans le but d'avoir une recherche rapide et pertinente. D'autre part, les vecteurs caractéristiques doivent être normalisés, afin d'avoir une clusterisation et une comparaison uniforme, où toutes les 25 métriques qui composent ces vecteurs y participent. On peut citer quelques métriques qui ont été utilisées dans les travaux antérieurs: La complexité du code : cette complexité est reflétée par un ensemble de métriques définies par Halstead. Ces métriques représentent des mesures quantitatives des opérateurs et opérandes qui constituent le 30 code source. La mesure de complexité proposée en 1976 par Thomas ].McCabe. Cette mesure connue sous le nom de complexité cyclomatique, est fondée sur le nombre cyclomatique de la théorie des graphes. Elle caractérise la connectivité entre les éléments du code, qui est représentée par un graphe reflétant le comportement du programme associé au code. Les métriques utilisées par Faidhi et Robinson dans la caractérisation des programmes Pascal, tel que le nombre total de caractères par ligne, la longueur moyenne des fonctions et des procédures, le pourcentage des blocs itératifs, le nombre total d'expressions, etc. D'autres métriques peuvent être ajoutées et combinées entre elles afin de mieux caractériser un code source. Dans l'approche basée sur les modèles structurels, le but est d'exploiter les propriétés structurelles du code source. Les deux principaux modèles de représentation de l'information structurelle sont les graphes conceptuels et les graphes de dépendances et de contrôle de flux de données. Les outils basés sur le modèle vectoriel, ne sont pas assez performants pour être robustes aux différentes techniques de plagiats. Les vecteurs caractéristiques peuvent être altérés par un simple ajout de quelques instructions au code plagié. Un autre inconvénient de ce type de modèle est dû au fait que deux codes ayant des vecteurs proches mais dont le contenu sémantique est différent, seront considérés comme un cas de plagiat. On peut expliquer cet inconvénient par l'absence de l'information structurelle et sémantique dans les représentations basées sur le modèle vectoriel. Par contre les outils de détection de plagiats basés sur les approches structurelles sont moins sensibles aux changements que peut subir un code plagié. Mais la difficulté réside dans le fait d'utiliser des structures complexes pour représenter un code source, et de trouver les techniques adéquates pour quantifier la similarité entre ces structures. Ce qui fait augmenter considérablement le coût de calcul, en particulier pour les approches basées sur les arbres et sur les graphes.

Le modèle de graphes conceptuels proposé par John Sowa est un modèle de représentation des connaissances où chaque graphe est un graphe biparti-étiqueté et composé de deux types de sommets : des sommets étiquetés par des noms de concept ( représentant des entités, des attributs, des états et des événements), et des sommets étiquetés par des noms de relations conceptuelles qui définissent les liens entre les concepts. Gilad Mishne et Maarten de Rijke utilisent les graphes conceptuels pour représenter le contenu structurel d'un code, où les concepts sont représentés par les blocs d'instructions et les opérations qui sont permises par le langage, alors que les relations sont représentées par les liens structurels qui peuvent exister entre les concepts. Les graphes de dépendance et de contrôle de flux permettent d'analyser et d'étudier la trace d'un programme associé à un code. Cette trace est considérée comme une suite d'informations qui reflète l'évolution de l'état de ce programme au cours de son exécution. Parmi les travaux de recherche s'étant intéressés aux graphes de dépendance et de contrôle de flux, on peut citer les travaux de Pfeiffer, où il a propose des algorithmes qui caractérisent et estiment les dépendances d'un code, afin d'étudier et d'analyser le comportement du programme qui lui est associé.

Les graphes de dépendance sont construits à partir d'une analyse basée sur la décomposition du code source en structures de contrôle telles que les blocs itératifs, les blocs conditionnels ou les blocs d'instructions simples. Ainsi la structure d'un graphe de dépendance décrit dans quel ordre les instructions élémentaires doivent être exécutées par le processus associé à un code. Basé sur l'analyse syntaxique du code, un graphe de contrôle de flux de données est un graphe orienté et étiqueté. Les noeuds de ce type de graphe sont constitués des éléments de base du code, et les arcs connectant les noeuds sont étiquetés selon la nature du flux de données existant entre ces noeuds. Il existe différentes techniques de transformation du code source qui sont souvent utilisées lors des opérations de plagiat. Ces techniques permettent de différencier le contenu d'un code plagié par rapport à celui du code original tout en conservant les mêmes fonctionnalités d'origines.

Les outils de détection de plagiat doivent être robustes à ces transformations afin de mieux détecter les cas de plagiats. La difficulté de la tâche de détection dépend de la complexité des modifications apportées au code original. Ces transformations varient des plus simples au plus complexes, allant du simple copier coller à la réécriture de quelques parties du code. On peut distinguer deux types de transformations :

A) Les transformations du premier type sont de nature lexicalle, parmi ces transformations on peut citer : l'attribution de nouveaux noms aux identifiants (variables, fonctions) : Les noms des identifiants qui ont un nom significatif sont remplacés par des noms générés d'une manière aléatoire, comme l'illustre le Tableau 1 ci-dessous.

La substitution des chaînes de caractères constantes par des chaînes de codes (code Ascii, Unicode, etc) tel que le contenu soit conservé. La modification des Commentaires : l'une des transformations que peut subir un code original est la suppression de tous les commentaires du code (ou l'insertion de nouveaux commentaires).

Dans d'autres cas ils sont modifiés manuellement mais tout en préservant le même sens que l'original.

B) Les transformations du second type sont de nature structurelle nécessitant une connaissance du langage et une forte dépendance à la grammaire qui le définit. Parmi les transformations structurelles les plus couramment utilisées on peut citer : Le changement de l'ordre des blocs d'instructions, de telle sorte que le comportement du programme ne soit pas affecté. la réécriture des expressions (permutation entre les opérandes et les opérateurs). Le changement du type des variables. L'ajout redondant d'instructions, de blocs d'instructions ou de variables, à condition que le comportement du programme ne soit pas modifié.

La dégénérescence du flux de contrôle, comme illustré dans le tableau 2 ci-dessous. La substitution des structures de contrôle itératives ou conditionnelles par d'autres structures de contrôle équivalentes. Par exemple un bloc itératif de type "While" est transformé en un bloc itératif de type "For". - La substitution des appels de fonctions par les corps de ces fonctions. Ces transformations peuvent être regroupées en fonction de leur niveau de complexité comme le spécifient les travaux de Faidhi et Robinsons où elles sont représentées par un spectre à six niveaux. Du niveau 1 au niveau 3 les transformations sont de nature lexicale, du niveau 4 au niveau 5 les transformations concernent la structure et le flux de contrôle, alors que le niveau 6 regroupe toutes les transformations possibles qui sont de nature sémantique telle que la réécriture des expressions. Les caractérisations obtenues par les approches basées sur les modèles vectoriels ainsi que celles basées sur les modèles structurels permettent de ne traiter efficacement que les transformations de niveaux 1 à 3. 20 Code original Code transformé 1 #ifndef 11010 2 #define 11010 1 #ifndef PI_H 2 #define PI_H 3 #ifndef PI 3 #ifndef 11 4 #define PI(4*atan(1)) 4 #define 11(4*atan(1)) 5 #endif 5 #endif 6 #define deg2rad(d) d*PI/180 6 #define 01(110) 110*11/180 7 #define rad2deg(r) r*180/PI 7 #define 00(111) 111*180/11 8 #endif /* PI_H */ 8 #endif /* 11010 */ Tableau 1 25 30 Code original Code transformé 1 int main(){ 1 int main(){ 2 float x=-2.0,y=1.2,z; 2 float x=-2.0,y=1.2,z; 3 z=fabs(x); int br=1; 4 y++; intit: x+=y; switch(br){ 6 z=x+y; case 1: 7 printf("%f,%f,%f",x,y,z); 3 z=fabs(x); 8 return 0; 4 y++; 9 } br=2; 5 goto in:it; case 2: x+=y; 6 z=x+y; 7 printf("%f,%f,%f",x,y,z); } 8 return 0; 9 } Tableau 2 15 Objet et description succincte de l'invention

L'invention vise à remédier aux inconvénients précités et à permettre de pouvoir caractériser un code source de telle sorte qu'il soit ensuite possible de détecter de façon automatique différentes variantes de 20 plagiats. Ces buts sont atteints, conformément à l'invention, grâce à un procédé de protection de documents numériques contre des utilisations non autorisées, caractérisé en ce que l'on identifie pour un document numérique à protéger constituant un code source un langage de 25 programmation L défini par une grammaire GL; on associe audit langage de programmation L un module de grammaire à actions tel que : a)La grammaire GL est constituée d'un ensemble de règles noté R={R,,R2,...,R } b)Le module de grammaire à actions est constitué d'un ensemble 30 d'actions noté AC={säs2,...s,ä} tel que : • s, = {action,, action2,4di est l'ensemble des actions associées à la règle R, • mn ; on réalise une caractérisation structurelle du code en une seule passe 5 10 d'analyse syntaxique à partir du module de grammaire à actions ; on construit un dictionnaire de grammaire GDL associé au langage de programmation et comprenant un ensemble de termes structurels tels que chacun de ces termes est associé à une règle ou un ensemble de règles ; on transforme le code source en une séquence structurelle (RL, TL, GDL) comprenant l'ensemble des termes structurels et le dictionnaire GDL de grammaire du langage L ; on procède de la même manière à la transformation d'un document numérique à analyser en une séquence structurelle (RL, TL, GDL) et on mesure le taux de plagiat entre le code source du document numérique à protéger et le code source du document numérique à analyser à l'aide d'une quantification du taux d'alignement entre les séquences structurelles respectives des codes sources du document numérique à protéger et du document numérique à analyser.

Les trois principales composantes qui singularisent les langages de programmation par rapport aux autres langages sont : les déclarations, les instructions et les expressions. Ces composantes sont considérées comme des "Points Critiques" dans un code source, d'où la nécessité d'exploiter l'information contenue à ce niveau du code.

Les déclarations peuvent être des types de données, des variables, des fonctions ou des prédicats. Pour les expressions une grande variété est permise en programmation, telles que les expressions relationnelles, logiques, arithmétiques et d'autres qui sont spécifiques à chaque langage (par exemple les expressions de type "Cast" en C/C++). La troisième composante peut être de nature atomique tel que les instructions d'entrées/sorties, ou de nature composée tel que les blocs itératifs. Ces Points Critiques sont représentés dans le code par un ensemble de lignes dont la suppression peut causer des changements dans le comportement (ou le résultat) du programme généré par ce code.

On peut constater qu'au niveau des Points Critiques cités précédemment il existe deux sources d'informations, et qui sont communes à tous les langages de programmation : La première source émerge à la suite d'une analyse du flux de données existant entre les Segments Indépendants du code. On appelle ici Segment Indépendant tout bloc d'instructions qui peut être utilisé séparément dans un autre contexte. Deux variantes d'analyse se présentent, une analyse intraprocédurale qui traite le flux entre les entités élémentaires d'un Segment Indépendant, et une analyse interprocédurale qui prend en considération le flux inhérent aux communications de ces Segments Indépendants. A partir de l'analyse des différents flux de données, les propriétés structurelles d'un code source sont alors déduites. Ces propriétés permettent de caractériser l'information véhiculée par les entités élémentaires d'un code source quel que soit le langage utilisé. Pour les langages impératifs les entités élémentaires d'un Segment Indépendant peuvent être des variables, des fonctions, des paramètres de fonction, des objets, etc. Pour les langages fonctionnels elles représentent les fonctions et les expressions, et enfin dans le cas des langages logiques elles représentent les prédicats, les symboles et l'ensemble des relations permises par ce type de langage. La deuxième source d'informations émerge d'une particularité commune à tous les langages de programmation. Cette particularité est représentée par l'aspect régulier du lexique et de la syntaxe des langages permettant de caractériser les codes bien formés. Cependant chaque langage de programmation possède ses propres particularités, impliquant une grammaire spécifique. En partant de ces grammaires une caractérisation structurelle basée sur la notion de "Dictionnaire de Grammaire" est réalisable quel que soit le modèle du langage de programmation (impératif, fonctionnel ou logique). Cette réalisation nécessite l'introduction de la notion de "Grammaire à Actions" qui est concrétisée par un module qui sera présenté plus en détail ci-dessous. Une grammaire d'un langage permet d'effectuer une analyse lexicale et syntaxique du code dans le but de vérifier si ce dernier respecte bien la syntaxe du langage. Cette analyse est effectuée sans aucune interprétation du code. De ce fait, et pour accéder au contenu structurel d'un code, la grammaire doit permettre une traduction de ce code du langage de programmation vers le langage de caractérisation. Ainsi la grammaire doit être harmonisée avec un ensemble d'actions dites de "caractérisation", d'où la notion de "Grammaire à Actions". La logique de cette notion consiste à donner un sens à l'analyse syntaxique du code source et pouvoir ainsi incorporer une interprétation et une traçabilité de cette analyse dans un contexte de caractérisation. L'idée de base se résume donc dans l'association de chaque règle de grammaire à un ensemble d'actions. Ces actions contribuent à la construction des structures caractéristiques appelées "Séquences Structurelles", comme l'illustre la Figure 1. Chaque terme ou suite de termes appartenant à ces séquences, doit refléter un concept structurel discriminant permettant ainsi de singulariser un code lors de sa caractérisation structurelle. Les deux principales particularités des langages de programmation sont l'aspect régulier de la syntaxe et la notion de flux de données. Ces deux particularités permettent d'établir une correspondance entre le contenu structurelle du code et sa structure caractéristique.

Ainsi à chaque langage de programmation L défini par une grammaire notée GL, on peut lui associer un module de Grammaire à Actions tel que :

1. La grammaire GL est constituée d'un ensemble de règles noté R={i ,R2,...j,} 2. Le module de Grammaire à Action est constitué d'un ensemble d'actions noté ac={säs2,... tel que : • S. _ {action, , action2,...}, vi =1,..., m est l'ensemble des actions associées à la règle R. • mn La nature séquentielle des structures caractéristiques émerge de la ressemblance conceptuelle et fonctionnelle qui existe entre le compilateur et le module de Grammaire à Actions. Par sa définition un compilateur permet de traduire un code source en un autre code écrit en langage machine, ce langage est en général de nature séquentielle et il est représenté par une succession d'instructions. De la même manière il est possible qu'un module de Grammaire à Actions puisse traduire le contenu du code en une séquence de symboles caractéristiques quel que soit le modèle du langage source. On notera que le principal avantage du module de Grammaire à Actions est le fait de pouvoir réaliser une caractérisation structurelle du code en une seule passe d'analyse syntaxique.

La caractérisation structurelle consiste à calculer une trace de l'analyse syntaxique du code. Cette trace est définie par un sous ensemble de règles de grammaire reflétant la manière dont le code est analysé syntaxiquement. Le sous ensemble contient donc les règles de grammaire qui ont été utilisées lors de l'analyse syntaxique, durant laquelle les actions de caractérisation qui sont associées à ces règles sont exécutées. Ces actions consistent à insérer des termes caractéristiques dans la "Séquence Structurelle" reflétant ainsi les concepts structurels contenus dans chacune des règles. Par exemple, "un bloc itératif" et "une condition d'arrêt" sont deux concepts qui émergent des trois règles de grammaire qui définissent respectivement les structures de contrôle du type "While", "For" et "Do". D'où la nécessité d'associer à ces trois règles les mêmes actions de caractérisation et les mêmes Termes Structurels qui expriment ces deux concepts.

De ce fait il est construit un Dictionnaire de Grammaire associé à chaque langage de programmation. Ce dictionnaire est constitué d'un ensemble de termes appelés 'Termes Structurels", tel que chacun de ces termes est associé à une règle ou un ensemble de règles. Pour chaque langage L défini par une grammaire GL constituée d'un ensemble de règles noté R, il est associé un Dictionnaire de Grammaire GDL permettant la mise en correspondance entre les règles et les termes :

GDF : R -* Ensemble de Termes Structurels R;

La caractérisation de l'aspect lexical et syntaxique du code permet d'extraire une topologie du contenu de ce dernier. Cette topologie reflète les liens structurels pouvant exister entre les différents concepts qui émergent d'une ou de plusieurs règles de grammaire tels que les fonctions, les listes des arguments, les blocs d'instructions atomiques, etc. Cette caractérisation doit être robuste aux altérations que peut contenir un code plagié par rapport au code original, d'où la nécessité d'associer les règles de grammaires aux Termes Structurels d'une manière pertinente. La caractérisation structurelle d'un code écrit dans un langage L peut être assimilée à un automate fini, déterministe, et défini par le triplet (R1, TL,GDL) avec :

RL : est l'ensemble des règles de la grammaire GL T~ : est l'ensemble des Termes Structurels GDF :est le Dictionnaire de Grammaire du langage L permettant de calculer la trace de l'analyse syntaxique du code et de pouvoir ainsi alimenter la Séquence Structurelle au fur et à mesure que les règles de grammaire sont utilisées durant l'analyse.

Après avoir présenté l'approche de caractérisation qui consiste à transformer un code source en un ensemble de Séquences Structurelles, il est mis en oeuvre une deuxième phase qui permet de mesurer le taux de plagiat entre deux codes source. Ceci peut être effectué par une quantification du taux d'alignement entre les Séquences Structurelles respectives.

La mesure de similarité entre deux séquences, considérée comme étant une abstraction au taux de plagiat, doit être robuste aux transformations que peut contenir une version plagiée du code, telles que les permutations et les duplications des segments de code, les insert:ions et les suppressions des lignes de code, etc.

Dans le but d'avoir une mesure qui reflète le plus pertinemrnent possible la ressemblance entre deux codes source, il est défini trois principales

contraintes qui doivent être satisfaites lors de la mesure du taux de plagiat 1. Les sous-séquences communes doivent être détectées sans tenir compte de leur position respective dans chacune des deux Séquences Structurelles. Autrement dit, la détection des plagiats doit être peu sensible aux permutations entres blocs d'instructions.

2. Les sous-séquences les plus longues doivent contribuer le plus dans le calcul du taux de plagiat, mais en même temps les sous- séquences noyées dans de longues séquences ne doivent pas être omises. Cette contrainte est due au fait que les longues sous-séquences sont plus fiables et plus pertinentes, alors que les sous-séquences courtes sont souvent source de bruit et de faux plagiats. 3. Éviter la redondance et le chevauchement entre les sous-séquences communes, c'est-à-dire que dans le cas où des segments indépendants d'un code original ont été repris d'une manière redondante dans le code plagié, il faut éviter que cette redondance apparaisse dans l'ensemble des sous-séquences communes, ce qui fait augmenter le taux de plagiat impertinemment, et inversement, c'est-à-dire dans le cas où les segments redondants ne sont pas des plagiats, ce qui fait baisser le taux de plagiat.

Une comparaison de séquence basée sur la technique de matrice de points connue sous le nom de "Dotplot", se révèle la plus adéquate à satisfaire ces trois contraintes. Cette technique est très informative du point de vue visuel La matrice de points permet donc une représentation visuelle de l'alignement entre deux Séquences Structurelles. Ces deux séquences sont placées le long des axes d'un graphique à deux dimensions, où chaque point (id) traduit une similarité entre le fine terme et le fine terme dans les deux séquences.

Brève description des dessins

D'autres caractéristiques et avantages de l'invention ressortiront de la description suivante de modes particuliers de réalisation, donnés à titre d'exemples, en référence aux dessins annexés, sur lesquels : -la figure 1 est un schéma bloc montrant schématiquement la structure d'un module de grammaire à actions utilisé dans le cadre de la présente invention, - la figure 2 est un schéma illustrant la mesure de similarité entre deux séquences structurelles A et B, selon une étape du procédé selon 30 l'invention, - la figure 3 montre deux courbes représentant les fréquences d'apparition des termes structurels dans des séquences caractéristiques de deux bases de codes Java, et - la figure 4 montre les différents niveauxdu spectre des techniques de plagiat d'un code source.

Description détaillée de modes particuliers de réalisation de l'invention 5 Afin de pouvoir contrôler la diffusion des logiciels la présente invention assure une caractérisation particulière du contenu des documents code source pour mesurer la similarité entre le contenu d'un document numérique à protéger et celui d'un document numérique à 10 analyser et pouvoir ainsi détecter l'existence de cas de plagiat. La caractérisation du contenu des documents code source est une tâche très complexe en raison de la similitude qui existe entre les différents codes sources des projets informatiques. De plus, il existe une multitude de techniques de plagiat pouvant être exploitées pour rendre les plagiats 15 difficiles à détecter. La présente invention propose une approche de caractérisation basée sur un Dictionnaire de Grammaire et sur la notion de Grammaire à Actions. Ces deux notions sont concrétisées par un module permettant d'accéder au contenu structurel du code par le biais de la grammaire du langage dont ce code est écrit. Les actions de ce module 20 consistent à traduire un code du langage source vers un langage de caractérisation où le code est représenté par une séquence caractéristique. Une technique d'alignement de séquences est appliquée par la suite pour mesurer le taux de similarité entre deux séquences caractéristiques à deux codes distincts. Ce taux est considéré comme une 25 abstraction au taux de plagiat détecté entre les deux codes en question. Comme on peut le voir sur la figure 1, qui symbolise un module de grammaire à actions, pour chaque langage de programmation constituant un langage source, tel que par exemple C++ ou Java, il est établi une grammaire qui comprend un ensemble de règles. 30 Chaque grammaire est harmonisée avec un ensemble d'actions dites de caractérisation. Ces actions contribuent à la construction des structures caractéristiques dénommées séquences structurelles . Il est alors défini un langage de caractérisation ou langage cible à partir des séquences caractéristiques, qui se substitue au langage de programmation ou langage source pour mesurer le taux de plagiat entre deux codes sources en effectuant une quantification du taux d'alignement entre les séquences structurelles respectives. Comme on l'a déjà indiqué plus haut, il est possible d'effectuer une 5 comparaison de séquence en se fondant sur la technique de matrice de points connue sous le nom de Dotplot . La matrice de points permet une représentation visuelle de l'alignement entre deux Séquences Structurelles. Ces deux séquences sont placées le long des axes d'un graphique à deux dimensions,, où chaque 10 point (ij) traduit une similarité entre le fine terme et le fine terme dans les deux séquences. Ainsi une matrice de point permettant de mesurer le taux de similarité entre deux Séquences Structurelles A et B est définie par l'équation (3). Les séquences A et B sont respectivement définies par les équations (1) et 15 (2) : A=<,az,...,aä > (1) B =< b, , b2 ,..., bm > (2) D=(d~)1i=1...n,j=1...m 1 Si a; = bj (3) Tel que du = 0 Sinon On définit deux métriques qui sont calculées à partir de la matrice de points, permettant de quantifier les zones de similarité et de pouvoir ainsi 20 calculer le taux de plagiat entre deux codes. Ces deux métriques informent sur les longueurs de toutes les sous-séquences communes entre deux Séquences Structurelles, et informent en même ternps sur les modifications effectuées sur la version originale du code. Par exemple une diagonale discontinue traduit une copie exacte avec des modifications, une 25 copie redondante d'un segment de code se traduit par des diagonales en parallèles, etc. Les deux métriques sont représentées par deux vecteurs d'estimations " VMH , VMv " qui sont calculés à partir des projections horizontale et verticale des éléments de 0a matrice Dn,m. Les deux vecteurs sont définis respectivement par les équations (4) et (5) : VMH (n) = vm, Avec : vm, _ > du (4) i=1 VM,, (m) = vm; Avec: vm, _ E d 1; (5) J =~ Les éléments successifs non nuls de chacun des deux vecteurs d'estimation représentent les sous-séquences qui sont en concordance entre les deux Séquences Structurelles A et B, et appelées sous-séquences positives, notées Seg4", SegB+. Ces sous-séquences communes représentent des concepts structurels similaires au niveau des deux codes source caractérisés par les séquences A et B.

Ainsi la mesure de similarité entre les séquences A et B, notée Sim(A,B) est définie par l'équation (6) : t E Seq;A+ E I Seq,8+ Seg AI ISeq H (6) Avec : Seq 4+ est lame sous séquence positive extraite du vecteur VMH et Segf+ est lame sous séquence positive extraite du vecteur VMv. La Figure 2 résume la mesure de similarité entre les deux Séquences Structurelles A et B : On présentera maintenant une analyse et une synthèse de l'approche de caractérisation selon l'invention en citant les avantages qu'elle apporte pour la problématique des plagiats du code source. Ensuite on évaluera la robustesse des Séquences Structurelles aux différentes techniques de transformations utilisées couramment lors des opérations de plagiats. La translation d'un code source du langage d'origine vers un autre langage différent est aussi utilisée comme une technique de plagiat. Dans la majorité des cas, le langage de plagiat est du même type que le langage d'origine, par exemple un code écrit en Java peut être plagié par une translation vers un code écrit en C++, ou d'un code écrit en Pascal m Sim(A, B) = max r t vers un autre code écrit en C. De ce fait il est important de caractériser d'une manière identique deux codes écrits dans deux langages différents afin de contrer les cas de plagiats utilisant la technique de translation. L'architecture modulaire du système selon l'invention et en particulier celle du module de Grammaire à Actions offre la possibilité d'effectuer une caractérisation multilangage. En utilisant les grammaires correspondantes, deux codes similaires écrits en langages différents peuvent être représentés dans le même espace de séquence. Soit deux langages de programmation LI et L2 définis respectivement par les triplets (RLI,TLI,GDLI) et (RLZ,TLZ,GDLZ). Deux rnodules de Grammaire à Actions associés à L1 et L2 produisent des Séquences Structurelles similaires pour deux codes Ca et Cu écrits en langage L1 et L2, si ces deux langages sont du même type, c'est-à-dire qu'il existe un sous ensemble de Termes Structurels en commun entre les deux langages (équation (7)). GD1., n GD, 2 ≠ { } (7) Une approche de caractérisation basée sur la grammaire du langage et indépendante de la représentation textuelle du code permet de renforcer la pertinence des Séquences Structurelles vis-à-vis de la structure du code et en particulier la syntaxe du langage. Afin de caractériser les structures de contrôle similaires ,de la même manière, chaque Terme Structurel doit être associé à l'ensemble des règles de grammaires qui reflètent le même concept. On peut citer par exemple les blocs itératifs de type "For", "While" et "Do" qui sont représentés par le même Terme Structurel. Le fait d'associer le même Terme Structurel aux opérations de contrôle du même type, permet plus de robustesse et de pertinence dans les Séquences Structurelles en particulier pour contrer les techniques de transformation qui consistent à remplacer des structures de contrôle par d'autres qui leur sont: similaires. La construction du Dictionnaire de Grammaire est une étape importante dans la caractérisation structurelle, en particulier pour l'optimisation des coûts de calcul des Séquences Structurelles, du point de vue temps d'exécution et utilisation de la mémoire. Dans cette perspective, une étude sur les règles de grammaire du langage est nécessaire afin que le Dictionnaire de Grammaire associé à ce langage ne contienne que les règles qui contribuent le plus à la caractérisation du code, c'est-à-dire les règles les plus discriminantes. Ceci permet de réduire la taille du Dictionnaire de Grammaire, ainsi que la complexité des Séquences Structurelles. A titre d'exemple, il a été effectué une caractérisation structurelle sur deux bases de codes Java. La première base représente la source de JDK 1.4.0, et la seconde base est constituée d'un ensemble de codes développés de façon spécifique. Les courbes de la Figure 3 représentent les fréquences d'apparition des Termes Structurels clans les séquences caractéristiques des deux bases. On constate que pour les deux bases, les termes les plus fréquents et plus redondants apparaissent dans les Séquences Structurelles de la majorité des codes appartenant aux deux bases et que les deux courbes représentent la même allure. Les termes dont la fréquence est la plus élevée, correspondent aux règles de grammaire décrivant l'initialisation d'une variable, les blocs de gestion des exceptions "Try ... Catch", et les définitions de fonctions. De ce fait, il est avantageux de n'utiliser qu'un sous ensemble de Termes Structurels, qui ne contiendra aucun des termes fréquents (c'est-à-dire qui sont associés aux règles de grammaire les plus utilisées lors de l'analyse syntaxique), et par conséquent on peut optimiser les coûts des opérations d'alignement de séquences du fait qu'il y aura moins de redondance dans les Séquences Structurelles. On évaluera maintenant la robustesse des Séquences Structurelles vis-à-vis des différentes techniques de plagiats qui tentent de rendre le code illisible et de le différencier de l'original. Ces techniques ont été classées en six niveaux par Faidhi et Robinsons, comme l'illustre la Figure 3: A titre d'exemple, un code java (un code de parcours d'un arbre binaire) a été modifié selon les six niveaux définis dans la figure 3. On a ensuite calculé le taux de plagiat entre les codes modifiés correspondant à chaque niveau et la version originale de ce code. Les modifications effectuées sur le code original sont comme suit : Niveau 0 : Aucune modification. Niveau 1 : Modification des commentaires, ajout de nouveaux commentaires, suppression de commentaires et modification des chaînes de caractères dans les messages de sortie. Niveau 2 : Changements des noms de variables (9 variables) + les changements du niveau 1. Niveau 3 : Changements des déclarations et de leur position dans le code (remplacer deux constantes par deux nouvelles variables déclarées, changement des positions de déclaration entre trois variables) + les changements du niveau 2. Niveau 4 : Remplacer deux blocs itératifs "For" par deux blocs "While", et un block itératif "While" par un block "For" + les changements du niveau 3. Niveau 5 : Changement de la modularité (création de deux nouvelles fonctions, changement de position entre deux fonctions existantes) + les changements du niveau 4. Niveau 6: Changements de deux expressions logiques et permutation entre le contenu du block "If' et "Else" en modifiant l'expression d'évaluation du test "If' + les changements du niveau 5. On peut illustrer les résultats de calcul du taux de plagiat entre le code original et les versions modifiées. A chaque niveau de transformation un taux d'alignement dans les Séquences Structurelles est calculé reflétant ainsi le taux de plagiat entre les deux codes (l'original et le code transformé). On constate que le taux de plagiat calculé à partir des Séquences Structurelle est de l'ordre de 100% pour les niveaux 0, 1 et 2 et reste 30 important pour les niveaux supérieurs (de l'ordre de 70% pour le niveau 3 et de 60% pour le niveau 4). Le procédé de caractérisation des documents de type code source, qui est basé sur la notion de "Dictionnaire de Grammaire", permet de caractériser l'information lexicale et syntaxique d'un code source par des structures séquentielles. Ces structures conservent l'information structurelle véhiculée par le code même s'il a subi plusieurs niveaux de transformations. Une autre particularité du procédé réside dans le fait que l'on peut réaliser une caractérisation multilangages et que l'on peut ainsi détecter des codes plagiés et translatés dans d'autres langages. Les Séquences Structurelles sont assez robustes aux techniques de transformations qui sont couramment utilisées lors des opérations de plagiats. L'approche de la matrice de points offre une robustesse dans la 10 détection des plagiats. 15 20 25 30

Claims (1)

REVENDICATIONS

1.Procédé de protection de documents numériques contre des utilisations non autorisées, caractérisé en ce que l'on identifie pour un document numérique à protéger constituant un code source un langage de programmation L défini par une grammaire GL; on associe audit langage de programmation L un module de grammaire à actions tel que : a)La grammaire GG est constituée d'un ensemble de règles noté R={RäR2,...,Rä} b)Le module de grammaire à actions est constitué d'un ensemble d'actions noté AC={säs2,... tel que : • s; _ {action,di =1,...,m est l'ensemble des actions associées à la règle R, • m<_n ; on réalise une caractérisation structurelle du code en une seule passe d'analyse syntaxique à partir du module de grammaire à actions ; on construit un dictionnaire de grammaire GDL associé au langage de programmation et comprenant un ensemble de termes structurels tels que chacun de ces termes est associé à une règle ou un ensemble de règles ; on transforme le code source en une séquence structurelle (RL, TL, GDL) comprenant l'ensemble des termes structurels et le dictionnaire GDL de grammaire du langage L ; on procède de la même manière à la transformation d'un document numérique à analyser en une séquence structurelle (RL, TL, GDL) et on mesure le taux de plagiat entre le code source du document numérique à protéger et le code source du document numérique à analyser à l'aide d'une quantification du taux d'alignement entre les séquences structurelles respectives des codes sources du document numérique à protéger et du document numérique à analyser.