Le « dégrugeur », un programme de détection de fraude issu de la recherche en informatique théorique
cours déplacé | Des info' pour l'éval' » [3798] lecturesActualité : Il y a maintenant un logiciel fonctionnel, voyez cet article pour plus d'information.
La distance informationnelle issue de la rechercher en bioinformatique et informatique théorique, permet de calculer une distance (dans le sens mathématique du terme) entre n'importe quel paire de fichiers. On peut donc s'en servir pour détecter une fraude typique de travaux pratique en informatique la « pompe ». C'est le fait de prendre le code d'un camarade et de le « maquiller » pour faire croire qu'il s'agit d'un travail original. Cette opération consiste à modifier le code de manière à le rendre visuellement différent de l'original mais sans rien changer de son fonctionnement. Il y a mille et une façon de faire cela mais en pratique ceux qui le font n'ont pas un bon niveau (sinon il ne frauderaient pas). Il est cependant difficile de détecter deux codes similaire quand on en regarde plusieurs dizaines, même si le « maquillage » est grossier. Ainsi en pratique la fraude est finalement difficile et pénible à détecter, même si une fois détectée elle s'avère souvent facile à prouver : en une ou deux question on voit très vite si une personne comprend ou non un code qu'elle est supposé avoir écrit
La mesure de la distance informationnelle peut nous aider à détecter cette fraude. Regardez dans la dernière version du support de cours du module d'algorithmique avancée (partie « compression de donnés » environ p.15) pour voir comment on peut facilement calculer cette distance.
On peut alors simplement regarder les distances entre les fichiers, sélectionner les fichiers les plus proches et les regarder en détail pour savoir si il y a réellement eu fraude ou non. Cette manière de faire, même si elle constitue déjà un progrès dans la lutte anti-fraude, peut-être insuffisante pour les raisons suivantes.
Les programmes de TP visent tous le même but il est donc normal qu'ils puissent être plus ou moins proche les uns des autres.
Un code commun donné de base (comme c'est parfois le cas de certain TP) « fausse » naturellement les calculs de distance.
Il est donc difficile de fixer un seuil de distance permettant de faire une détection fraude efficace dans tous les cas.
Une solution est d'essayer d'avoir une vue d'ensemble, pour trouver automatiquement un seuil de détection. Pour cela on fait implicitement la supposition suivante : la majorité des codes sont des « originaux » et le nombre de fraudes (si il y en a) est à priori faible. On peut imaginer que chaque fichier à analyser est un point dans un espace vectoriel ainsi l'ensemble des fichiers est assimilable à un nuage de point. La distance informationnelle représente la distance entre ces points. Il serait très intéressant de visualiser ce nuage de points. A priori, si il y a de la fraude on le repérera visuellement en constatant qu'un certain nombre de points sont beaucoup plus resserrés que la moyenne des autres points. Cette vision globale permettra d'un coup d'oeil d'estimer ce qu'est une distance « raisonnable » entre deux fichier, et donc de trouver naturellement un seuil de détection de fraude.
Cette idée est séduisante mais cela est problématique pour plusieurs raisons :
On a les distances entre les points, pas les coordonnées.
La dimension de l'espace considéré est élevée.
Il y a des moyens d'estimer les coordonnées à partir des distances, le premier problème est donc contournable Le deuxième est plus embarrassant On n'est assuré de pouvoir trouver les coordonnées exactes, ne contredisant pas l'information de distance qu'a partir de n-1 où n est le nombre de fichiers à analyser. En pratique cela fait plusieurs dizaines... Or on ne peut visualiser de manière claire et intuitive que des coordonnées en dimension inférieure ou égale à 3.
La première approche est de mesurer l'erreur commise en n'autorisant que 3 dimensions, avec de la chance si cette erreur est faible, cela veux dire qu'on à réussit à faire une représentation à peu près correcte en dimension 3. Cela fonctionne raisonnablement bien mais a ses limites... On ne peut analyser qu'un nombre limité de fichiers. Mais cela montre déjà avec quelle facilité on peut détecter de la fraude. J'ai pris les fichiers des TP du module LAB2412 que j'ai numérotés et auquel j'ai ajouté un code fraudé. Ce code est une copie du code numéro 4 que j'ai édité :
Changement d'une bonne partie des noms de variables et fonctions
Modification des commentaires
Modifications de l'indentation
Dans l'image ci-dessous vous pouvez visualiser la « proximité » de ces programmes.
On constate qu'il y a deux points (donc deux programmes) qui sont
notablement plus proche l'un de l'autre que toute autre paire de
points/programmes. C'est bien évidement le code_4 et le
code_Fraude qui sont le plus proches.
Cela marche donc bien quand il y a peu de documents à traiter mais on ne peut pas, comme cela, visualiser de « vrais » nuages de points c'est à dire analyser d'un coup un lot important de fichiers. Cela est du à la dimension est trop grande pour être correctement représenté en dimension 3. Un peu comme quand on représente une carte du monde à plat (3D->2D) on sait que la taille des pays proches des pôles n'est pas à l'échelle des tailles des pays des tropiques. On peut pourtant utiliser ces cartes pour un certain nombres de chose même si d'un certain point de vu elles sont fausses. Nous avons la un problème similaire. Ce type de représentation reste donc possible si on accepte un certain nombre de déformations contrôlées...
Typiquement ici ce qui nous intéresse c'est les distances faibles (correspondant aux fraudes suspectées) on peut donc modifier l'algorithme de calcul des coordonnées pour se focaliser sur ces points et tolérer une plus grande erreur sur les distances plus importantes. On peut regarder la distribution des distances entre les fichiers, et décider que les distances supérieures à un certain seuil n'ont pas besoin d'être respectées (tant qu'elle sont supérieures à la distance minimale exigée).
Voici la courbe de distribution des distances informationnelles sur l'exemple considéré :
L'axe des x représente la distance informationnelle.
L'axe des y représente le nombre de paires de points ayant cette distance.
On décide de « négliger » les distances supérieures à 0.23, ce qui semble raisonnable pour détecter une éventuelle fraude car cela représente les 45 plus petites distances entre points.
Voilà ce que ça donne :
A première vue cela fait un peu fouillis, car il y a beaucoup de données : 30 points. On voit ensuite qu'une paire de points vraiment plus proche que les autres, à tel point que les labels des points s'écrivent l'un sur l'autre (code4 et codeFraude). Les quelques autres paires de points qui ont l'air proches ne le sont en fait pas (par exemple code_26 et code_21). Il ne s'agit que d'un effet de projection de 3D vers 2D. Pour s'en apercevoir il suffit de rechercher ces points dans cette autre vue du même nuage de points pour s'apercevoir qu'il sont en fait passablement éloignés.
Notez que les points code4 et codeFraude sont toujours aussi près l'un de l'autre.
Si vous voulez avoir une meilleure vue de ce nuage de points
utilisez le logiciel gnuplot
pour visualiser vous même ces données. Si vous êtes
sous Linux, ce logiciel est déjà probablement installé
sur votre machine. Pour visualiser le nuage de point téléchargez
ce fichier
puis tapez gnuplot, après un bref affichage de texte, vous
pourrez taper : load "nuagePoints.txt"
une fenêtre
s'affiche alors. Cliquez (laissez le bouton gauche enfoncé)
dans la fenêtre et bougez la souris , le nuage de points
tournera sur lui même pour que vous le scrutiez sous tous les
angles.
Pour conclure :
C'est un outil très puissant pour détecter la fraude en TP ou toute autre activité pédagogique où le rendu est un fichier.
Note : seul les codes « qui compilent » on été utilisés pour cet expérience car la mesure de comparaison à été faite sur les exécutables.
Biensur j'utiliserai ce programme de détection à l'avenir...
Voici les prochaines étapes de ce projet :
Je suis à la recherche de personnes pouvant m'aider à faire un « screencast » pour présenter le logiciel et ses capacités.
Je suis à la recherche de compétences spécifiques en interface graphique en Java.
Je suis aussi à la rechercher d'archive de fichiers de rendu de projets pour tester sur d'autres exemples.
codes
rapports
etc...
Merci de voter pour ce billet, en cliquant sur les étoiles
ci-dessous, que l'article vous ait plu (>=5), ou non (<5) ...
Commentaires
Le jeudi 15 mars 2007 à 01:51, par Robert ERRA
Je dis peut-être une bêtise mais si tu prends les données de la représentation en 3D et que tu fait, comme l'a proposé Julien Cornebise, une ACP sur les 3 dimensions pour n'en retenir que deux ? Du coup tu as une carte 2D, plus facile à visualiser. Ce n'est pas trop cher , on pourrait même partir de 4 ou 5 dimensions au départ pour n'en retenir que 2? Je n'ai pas compris non plus la remarque sur le seuil implicite, l'ACP se contente de dire quelles sont les dimensions importantes (si je me souviens bien). ps: la phrase "On a les distances entre les points, pas les coordonnées." me fait penser au problème de graphe dont tu m'avais parlé il y a quelques années. Julien avait testé un algo sympa (mais j'ai perdu le fichier Mathematica), cela peut-il resservir ?
Le jeudi 15 mars 2007 à 14:28, par Julien Cornebise
Hmmm, dans les mails échangés, je proposais plutôt une ACP sur les n-1 dimensions - bien que le passage par les coordonnées me chagrine un peu, il faut que la distance vérifie certaines hypothèses pour être sûr d'avoir existence et unicité de la solution (aux rotations et symétries près).
Le coup du seuil portait sur la Classification Hiérarchique Descendante (par fission des classes, partant de l'ensemble et arrivant aux singletons). La CHA (classification Ascendante, fusion des classes en partant des singletons et en arrivant à l'ensemble) permet de contourner ce pb de seuil - avec le choix du nombre de classes en fonction du saut d'un critère faisant intervenir la variance inter-classes et intra-classes. Voir aussi en fonction de la stratégie d'aggrégation adoptée. Je pense que cette méthode peut vraiment être intéressante.
Concernant le fichier Mathematica, je dois encore l'avoir - il se basait sur l'idée de Robert de minimiser l'énergie dans un système de ressort, via simulation des lois de Hooke. Ca vaut ce que ça vaut, mais c'est la même idée que dans les routines d'affichage de graphes du package Combinatorica conçu par Skiena pour Mathematica.
Ca peut éventuellement resservir, mais c'était une optimisation numérique, avec risques de tomber sur des minima locaux.
Le jeudi 15 mars 2007 à 16:38, par Hubert WASSNER
Il y a plein de remarques importantes et complexes ici, je vais essayer de repréciser les remarques et d'y répondre.
Pour la distance informationnelle , il s'agit d'une distance au sens mathématique du terme, la cohérence de cette distance est donc assurée en dimension (n-1) (ou n est le nombre de fichiers à analyser). La seule particularité c'est qu'il s'agit d'une distance bornée dans [0;1], ca peut être perturbant si on réflechit avec la distance euclidienne standard mais sur le fond ca ne chage pas grand chose, il suffit de se dire que plus les fichiers sont differents, plus la distance qui les sépare s'approche de 1.
Pour ce qui est de l'ACP (Analyse en Composante Principale), cela vise à réduire le nombre de dimensions d'un lot de donnés en minimisant l'erreur due à la perte de dimension en privilegiant les directions principales : ca peut être interessant, en général cela permet une reduction de peu de dimensions, tout en ayant un contrôle "uniforme de l'erreur" (aucun point n'est privilégié lors de l'approximation). Or dans ce cas précis on à une forte réduction de dimension à opérer 30D->3D , et on peut se permettre une plus grande erreur sur les grandes distances car elles nous interessent peu, et ne peut pas se permettre de déformations sur les distances faibles car c'est pile ce qu'on visualiser analyser ici. J'en conclu que même si c'est une approche naturelle d'analyse de donnée je pense que l'ACP est ici peu interessante, ou disons peu adapté.
Pour ce qui est du seuil implicite, une représentation sous forme d'arbre est une representation discrète dans le sens ou 2 éléments (fichiers) sont soit dans la même branche soit il n'y sont pas, ou bien sont dans des branches proches, mais dans tous les cas les notions d'appartenances ne sont pas continues. Donc quand on présente un arbre (quelque soit la manière dont il a été construit) on propose de visualiser une décision de classification qui a été prise par un algorithme. C'est typiquement ce qu'il faut éviter je pense pour ce type de programme. Il faut que ce soit un humain, capable d'intégrer tout le contexte de l'analyse, de décider si une paire de points est "trop" proche ou non. Pour cela il faut donc que l'affichage reste continu et non discrèt. Voila pourquoi je préfère la visualisation par un nuage de point à un arbre pour ce type précis d'application.
Ajouter un commentaire