Hubert Wassner

Professeur d'informatique

10 03 2007

Le « dégrugeur », un programme de détection de fraude issu de la recherche en informatique théorique

J'ai implémenté un outils de détection de fraude. Je n'en suis qu'aux premiers résultats mais je pense qu'ils méritent votre attention que vous soyez fan d'algorithmique ou que vous en ayez horreur...
Actualité : 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) ...

Notez ce billet : 55 vote(s)

Vous avez trouvez intéréssant ce billet? Abonnez-vous au flux RSS pour être tenu informé des prochains!

Trackbacks

Aucun trackback.

Les trackbacks pour ce billet sont fermés.

Commentaires

Aucun commentaire pour le moment.

Ajouter un commentaire

Les commentaires pour ce billet sont fermés.