Informatique

PJE A - analyse de plagiat

L'objectif du PJE est de développer un logiciel, en équipe, en utilisant des outils de travail collaboratif. Dans le cadre du PJE "analyse de plagiat", le logiciel développé a pour but de mesurer la ressemblance entre deux codes. Soulignons que les méthodes mises en œuvre dans ce type d'outil ne servent pas uniquement pour détecter la triche entre étudiants mais peut avoir des utilisations dans l'étude de l'évolution des codes. Le développement d'un logiciel pour traiter ce problème sera l'occasion de découvrir des méthodes de traitement du texte.

Compétences acquises

• travail collaboratif
• gestion de projet
• utilisation d'API

Connaissances acquises

• analyse de texte
• algorithmes de recherche de mots dans un texte
• algorithmes de comparaison de texte

Mode de travail

Le projet est développé en groupes de 4 ou 5 étudiants. Chaque groupe développe sous un dépôt GIT. L'évaluation en cours de projet et de la version finale se fera par clone à une heure donnée (voir planning sur le portail). Les séances de cours/TD servent à mener une réflexion sur les développements algorithmiques du projet. Des notions sont apportées par les enseignants sans nécessairement expliciter comment elles peuvent être utilisées dans le projet. A chaque début de séance de TP, chaque groupe fait le point avec l'enseignant en quelques minutes, en présentant les réussites, les difficultés rencontrées et la répartition du travail pour la semaine à venir. Une évaluation publique des développements effectués est également présentée à chaque début de séance.

Responsables

• Mikaël Salson
• Jean-Stéphane Varré

Volume horaire

3h30 de TD/TP par semaine sur 10 semaines

Crédits

5 ECTS

Documents et ressources

Git

• Le livre Pro Git (en français) : lire 1.3, 1.4, 2 (en omettant 2.5 et 2.6), 3 (en omettant 3.5)
• Refcard des commandes Git
• Les basiques de Git en quelques minutes (cours interactif) : try Git

Maven

• voir portail COO onglet documents

R

Liens utiles

• Dessinner des graphes avec igraph
• Kmeans et un peu plus d'explications
• Clustering hierarchique
• Cluster analysis, en bref
• Cluster analysis, un peu plus détaillé

De jolis graphiques

## on va utiliser la bibliothèque ggplot2

## la premiere fois, on installe ggplot2, une seule fois
#install.packages("ggplot2")

## une fois installée, il faut charger la librairie, à chaque fois
library(ggplot2)

## il faut commencer par charger les données
df <- read.csv("res_exemple4.txt",sep=" ",stringsAsFactors=FALSE)
## on peut préciser des noms pour les colonnes
names(df) <- c("file1","And","file2","sim")

## on ne garde seulement que les champs interessants pour nous
df = df[,c("file1","file2","sim")]

## on supprime les ':' à la fin de la colonne file2
get = function(x) gsub("(.*):", '\\1', x)
df$file2 <- get(df$file2)

## on transforme la chaîne contenant la similarité en nombre
get = function(x) gsub("(.*)%", '\\1', x)
df$sim <- get(df$sim)
df$sim <- as.numeric(df$sim)

##
## representations basiques
##

## on dessine simplement les points
qplot(file1,sim,data=df)

## on dessine une simple courbe, avec le nom du fichier 1 sur l'axe des x
qplot(df$file1,df$sim,geom="line")

## dessiner un bargraph
barplot(df$sim,names.arg=df$file1)
## avec ggplot
ggplot(df,aes(x=file1,y=sim)) + geom_bar(stat="identity")

##
## on veut voir la distribution des ressemblances
##

## dessiner un histograme
qplot(df$sim)
## avec ggplot
ggplot(df, aes(x=sim)) + geom_histogram(binwidth=10)
## pour passer l'axe des y en log
ggplot(df, aes(x=sim)) + geom_histogram(binwidth=10) + scale_y_log10()

## dessiner un boxplot
## auparavant il faut que la colonne des nom de fichier soit factorisé
str(df)
dfv = df[,c("file1","sim")]
dfv$file1 <- as.factor(dfv$file1)
str(dfv)
plot(dfv$file1,dfv$sim)
## avec ggplot
ggplot(dfv, aes(x=file1,y=sim)) + geom_boxplot()
## et pas besoin de transformer en vecteur !
ggplot(df, aes(x=file1,y=sim)) + geom_boxplot()

## on retrouve toutes les comparaisons
ggplot(df, aes(x=interaction(file1,file2),y=sim)) + geom_boxplot()

### on affiche les fichiers qui ont une moyenne superieure à 5, avec de la couleur
df5 = df
df5$pos <- df5$sim >= 5
ggplot(df5, aes(x=file1,y=sim,fill=pos)) + geom_boxplot()

## retour sur le bargraph
## avec des couleurs >= 5
ggplot(df5, aes(x=file1,y=sim,fill=pos)) + geom_bar(stat="identity")
## en empilant pour chaque fichier
ggplot(df5, aes(x=file1,y=sim,fill=file2)) + geom_bar(stat="identity")
ggplot(df5, aes(x=file1,y=sim,fill=file2)) + geom_bar(stat="identity") + geom_text(aes(y=sim,label=sim),colour="Black")

## graphes
library(igraph)
d = df[df$sim >= 5,]
g <- graph_from_data_frame(d,directed=FALSE)
plot(g,vertex.size=4,vertex.label.cex=0.5) 
plot(g,vertex.size=14,edge.label=paste(E(g)$sim,"%"))

## transformation en matrice
f = function(x) ((100-x)/100)
df1 = df
df1[3] = lapply(df1[3],FUN=f)
un1 = unique(unlist(df1[1:2]))
df1[1:2] = lapply(df1[1:2], factor, levels=un1)
m1 = xtabs(sim~file1+file2, df1)
d = as.dist(m1+t(m1))
m = as.matrix(d)

## matrice de ressemblance
library(corrplot)
corrplot(m,na.label=" ",tl.cex=1,type="upper",cl.lim=c(0,1))


## sortir les graphes dans des fichiers
png("plot1.png")
ggplot(df,aes(x=file1,y=sim)) + geom_bar(stat="identity")
dev.off()  

Preparation des données

les données initiales exple8.txt

# obtention du CSV
cat exple8.txt | sed -e 's/and//g' | tr ':' ' ' | tr '%' ' ' > exple8.csv

# chargement du dataframe
mydata = read.csv("exple8.csv",sep="", header=FALSE)
names(mydata) = c("file1","file2","sim")

# installation des librairies (à faire une fois)
install.packages(igraph)

# chargement des librairies
library(igraph)

Construire le graphe de similarité

# creation du graphe de similarité
df = mydata[(mydata$sim >= 10),]
g <- graph.data.frame(df, directed=FALSE)
plot(g,vertex.size=4,vertex.label.cex=0.5)  

Mettre les composantes en couleur

# calcul et coloriage des composantes
comps <- components(g)$membership
colbar <- rainbow(max(comps)+1)
V(g)$color <- colbar[comps+1]
plot(g, layout=layout_with_fr, vertex.size=5, vertex.label=NA)  

Transformation en une matrice de distance

# transformation en matrice de distance
f = function(x) ((100-x)/100)
df1 = df
df1[3] = lapply(df1[3],FUN=f)
un1 = unique(unlist(df1[1:2]))
df1[1:2] = lapply(df1[1:2], factor, levels=un1)
m1 = xtabs(sim~file1+file2, df1)
d = as.dist(m1+t(m1))  

Construction d'un clusetring hierarchique

# clustering hierarchique
library(cluster)  
hc = hclust(d)
plot(hc)
rect.hclust(hc, k=9, border="red")  

Clustering des paires ayant le même niveau de ressemblance

C'est juste un exemple qui ici ne signifie vraiement pas grand chose.

d = dist(df1)
fit = kmeans(d,8)
clusplot(df1, fit$cluster, color=TRUE, shade=TRUE,labels=2, lines=0)  

Pour une sortie graphique dans un fichier

Avant de faire le plot il faut dire à R qu'on redirige celui-ci dans un fichier:

png("monimage.png")

Puis on lance le plot. Et ensuite on ferme le fichier PNG.

dev.off()

Supports de cours

• Fingerprinting, winnowing, Karp & Rabin
• Alignement

Articles scientifiques

• Matija Novak, 2016, Review of source-code plagiarism detection in academia. In Information and Communication Technology, Electronics and Microelectronics (MIPRO), 2016 39th International Convention on (pp. 796-801). IEEE.
• KARP R.M., RABIN M.O., 1987, Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2):249-260., exemple
• SCHLEIMER et al., 2003, Winnowing: local algorithms for document fingerprinting, SIGMOD'03 Proceedings of the 2003 ACM SIGMOD international conference on Management of data Pages 76-85.

Jeux de données

Résultats

Description des benchmarks

1. exemple 0
2. exemple 1 : modification de noms de variables, ajout de commentaires, réorganisation de lignes de code
3. exemple 2 : variations autour de la structure d'une classe, méthodes dans des ordres différents mais le contenu reste identique
4. exemple 3 : une interface et des classes implémentants celle-ci, différentes implémentations provenant de TP étudiants
5. exemple 4 : une classe, différentes implémentations provenant d'un TP étudiant, mais sans ressemblance évidente entre les différentes implantations
6. exemple 5 : proposé par l'équipe Wallaby en 2016/2017
7. exemple 6 : proposé par l'équipe Wallaby en 2016/2017
8. exemple 7 : proposé par l'équipe VEMP (deux gros fichiers) en 2016/2017
9. exemple 8 : toutes les classes d'un projet étudiant
10. exemple 9 : toutes les classes d'un projet étudiant

Evolution des commits par équipe (maj le 11/10/2018)

Evolution du nombre de merge requests

Evolution de la couverture de code

Livrables

1. Livrable 1
2. Livrable 2
3. Livrable 3
4. Livrable 4
5. Livrable 5
6. Livrable 6

TEAM Inglorious Basterds

**** Version v1.0 ****
**** Compiling package ****
**** Launching benchmarks ****
**** Running exemple0 ****
**** Running exemple0_17-18 ****
**** Running exemple0_18-19 ****
**** Running exemple1 ****
**** Running exemple2 ****
**** Running exemple3 ****
**** Running exemple4 ****

TEAM PlagiatChecker
**** Version v1.0 ****
**** Compiling package ****
**** Creating JAR ****
**** Launching benchmarks ****
**** Running exemple0 ****
**** Running exemple0_17-18 ****
**** Running exemple0_18-19 ****
**** Running exemple1 ****
**** Running exemple2 ****
**** Running exemple3 ****
**** Running exemple4 ****

TEAM PSG

**** Version v1.0 ****
**** Compiling package ****
**** Launching tests ****
**** Creating JAR ****
**** Launching benchmarks ****
**** Running exemple0 ****
aucun attribut manifest principal dans target/yapt-v1.0.jar

exemple0	Inglorious Basterds	PlagiatChecker	secrettool
exemple0_17-18	Inglorious Basterds	PlagiatChecker	secrettool
exemple0_18-19	Inglorious Basterds	PlagiatChecker	secrettool
exemple1	Inglorious Basterds	PlagiatChecker	secrettool
exemple2	Inglorious Basterds	PlagiatChecker	secrettool
exemple3	Inglorious Basterds	PlagiatChecker	secrettool
exemple4	Inglorious Basterds	PlagiatChecker	secrettool