Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

paper - Probabilistic algorithms for large scale systems

151 pages

paper - Probabilistic algorithms for large scale systems

Publié par :
Ajouté le : 21 juillet 2011
Lecture(s) : 69
Signaler un abus

Vous aimerez aussi

´UNIVERSITE PARIS-SUD XI
`THESE
pourobtenirlegradede
´DOCTEUR DE L’UNIVERSITE PARIS-SUD XI
prepar´ ee´ au LABORATOIRE DE RECHERCHE EN INFORMATIQUE
danslecadrede l’Ecole Doctorale d’Informatique de Paris Sud”
present´ ee´ etsoutenuepubliquement
par
ThomasLARGILLIER
le29novembre2010
Probabilisticalgorithmsforlarge
scalesystems
Directeurs de these` :
M.JoffroyBeauquieretSylvainPeyronnet
JURY
Mr. Brian D. DAVISON Rapporteur
Mr. Aristides GIONIS
Mr. Serge ABITEBOUL Examinateur
Mr. Fabio CRESTANI
Mr. Joffroy BEAUQUIER Directeurdethese`
Mr. Sylvain PEYRONNETdethese`CONTENTS
Contents 2
1 FrenchSummary 7
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.1 Lestricheurssurlatoile . . . . . . . . . . . . . . . . . 8
1.1.2 Lessystemes` a` grandeechelle´ . . . . . . . . . . . . . . 9
1.2 Declassement´ duWebspam . . . . . . . . . . . . . . . . . . . . 10
1.2.1 LeWebspam . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.2 LuttercontreleWebspam . . . . . . . . . . . . . . . . . 11
1.2.3 Resultats´ . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Lesreseaux´ decapteursmobiles . . . . . . . . . . . . . . . . . 12
1.3.1 Definition´ etdefis´ . . . . . . . . . . . . . . . . . . . . . 12
1.3.2 L’algorithmeRaWMS . . . . . . . . . . . . . . . . . . 13
1.3.3 Notreproposition . . . . . . . . . . . . . . . . . . . . . 14
1.4 Testpourlesapplicationsa` grandeechelle´ . . . . . . . . . . . . 15
1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2 Preamble 19
2.1 HandlingmalicioususersontheWeb . . . . . . . . . . . . . . . 20
2.1.1 Diminishing the influence of malicious users of social
networks . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.1.2 ReducingtheboostingeffectofWebspam . . . . . . . . 21
2.2 Largescalenetworks . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.1 Improvingdatadisseminationinsensornetworks . . . . 22
2.2.2 Realisticevaluationofparallelanddistributedapplications 22
23
I FightingmaliciousbehavioursontheWeb 25
3 Introduction 27
3.1 Collaborativenewswebsites . . . . . . . . . . . . . . . . . . . 29
3.2 Fightingsocialspam . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 WebSpampresentation . . . . . . . . . . . . . . . . . . . . . . 31
3.4 FightingWebspam . . . . . . . . . . . . . . . . . . . . . . . . 34
3.5 Randomwalks . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.6 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.6.1 Edgebetweennesscentrality . . . . . . . . . . . . . . . 39
3.6.2 Markovclusteringtechnique . . . . . . . . . . . . . . . 41
4 Maliciousbehavioursinsocialnetworks 45
4.1 SpotRankalgorithm . . . . . . . . . . . . . . . . . . . . . . . . 46
4.1.1 Frameworkandprinciple . . . . . . . . . . . . . . . . . 46
4.1.2 Proposingaspot . . . . . . . . . . . . . . . . . . . . . 48
4.1.3 Votingforaspot . . . . . . . . . . . . . . . . . . . . . 48
4.1.4 Detectingcabals . . . . . . . . . . . . . . . . . . . . . . 52
4.2 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2.1 Loganalysisofspotrank.fr . . . . . . . . . . . . . . . . 54
4.2.2 HumanEvaluation . . . . . . . . . . . . . . . . . . . . 61
4.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5 DemotingWebSpam 67
5.1 ClusteringMethods . . . . . . . . . . . . . . . . . . . . . . . . 68
5.2 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.3 StatisticalTest . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6 DetectingWebSpam 79
6.1 RandomwalksagainstWebspam . . . . . . . . . . . . . . . . . 80
6.2 Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 884 CONTENTS
II Analysis & probabilistic solutions for large scale sys
tems 91
7 Introduction 93
7.1 Messagepropagationinsensornetworks . . . . . . . . . . . . . 94
7.1.1 SensorNetworks . . . . . . . . . . . . . . . . . . . . . 94
7.1.2 Howtoefficientlypropagatemessagesinsensornetworks 96
7.1.3 Relatedwork: datadisseminationinWSNs . . . . . . . 98
7.2 Largescaleapplications . . . . . . . . . . . . . . . . . . . . . . 99
7.2.1 Cluster&Grids . . . . . . . . . . . . . . . . . . . . . . 99
7.2.2 Managingfailuresinlarge scalesystems . . . . . . . . . 100
7.2.3 Evaluationoflarge scaleapplications . . . . . . . . . . 101
7.2.4 Existingsolutionsforlarge scaleapplicationsdevelopment103
8 QoSinsensornetworks 105
8.1 Suppledescription . . . . . . . . . . . . . . . . . . . . . . . . . 106
8.2 Rationaleandsystemmodel . . . . . . . . . . . . . . . . . . . 107
8.3 Supple: formalpresentation . . . . . . . . . . . . . . . . . . . . 108
8.3.1 Treeconstruction . . . . . . . . . . . . . . . . . . . . . 108
8.3.2 Weightdistribution . . . . . . . . . . . . . . . . . . . . 109
8.3.3 Datadissemination . . . . . . . . . . . . . . . . . . . . 110
8.3.3.1 Formalanalysis . . . . . . . . . . . . . . . . . 112
8.3.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 114
8.4 Performanceanalysis . . . . . . . . . . . . . . . . . . . . . . . 115
8.4.1 Evaluationmethodology . . . . . . . . . . . . . . . . . 115
8.4.1.1 Experimentalsetup . . . . . . . . . . . . . . . 115
8.4.1.2 Simulationparameters . . . . . . . . . . . . . 116
8.4.1.3 Evaluationmetrics . . . . . . . . . . . . . . . 116
8.4.2 Simulatedresults . . . . . . . . . . . . . . . . . . . . . 117
8.4.2.1 Communicationoverhead . . . . . . . . . . . 118
8.4.2.2 Efficiencyindatagathering . . . . . . . . . . 120
8.4.2.3 Lossresilience . . . . . . . . . . . . . . . . . 122
8.4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 123
9 Testforlargescaleapplications 125
9.1 V DSPlatformDescription . . . . . . . . . . . . . . . . . . . . 125
9.1.1 Virtualization Environment for Large scale Distributed
Systems . . . . . . . . . . . . . . . . . . . . . . . . . . 1265
9.1.2 Low levelNetworkVirtualization . . . . . . . . . . . . 127
9.2 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
9.2.1 ImpactoftheLow LevelNetworkEmulation . . . . . . 129
9.2.2 TCPBrokenConnectionDetectionMechanism . . . . . 130
9.2.3 StressofFault TolerantApplications . . . . . . . . . . . 132
9.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
IIIConclusion 137
10 139
10.1 Socialspam . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
10.2 Webspamdemotion . . . . . . . . . . . . . . . . . . . . . . . . 139
10.3 Wdetection . . . . . . . . . . . . . . . . . . . . . . . . 140
10.4 Supple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
10.5 V ds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
Bibliography 1411
FRENCH SUMMARY
1.1 Introduction
De nos jours, les systemes` informatiques ont une taille sans cesse croissante
pour repondre´ aux besoins des utilisateurs. Que ce soit dans le domaine du
calcul scientifique ou` de plus en plus d’ordinateurs sont relies´ pour repondre´ a`
des problemes` sans cesse plus complexes ou dans le domaine du loisir avec un
Internetgrandissantpoursatisfairetoujourspluslacuriosite´ desutilisateurs.
Les defis´ qui concernent les reseaux´ a` grande echelle´ sont nombreux: pou
voirgarantirauxutilisateursd’unclusterqueleurcalcularriveraa` termeetsans
erreur dans un temps raisonnable, distribuer des donnees´ entre petites entites´
intelligentesefficacementouencoreproteger´ leWebcontrelestricheurs.
Le but de ma these` est d’apporter des reponses´ pour les systemes` a` grande
´ ´ ´echelleafindegarantirl’experienceutilisateurlaplusagreablepossible.
Lestravauxrealis´ es´ auseindecettethese` vontdelaconceptiond’algorithmes
a` la realisation´ de modules pour le noyau d’un systeme` (GNU/Linux). Les do
mainesetudi´ es´ vontdesspammeurssurleWebauxbancsd’essaipourlesappli
cationsa` tres` grandeechelle.´
7
C H A P T E R8 CHAPTER1. FRENCHSUMMARY
1.1.1 Lestricheurssurlatoile
De nos jours l’Internet est un endroit immense ou` chaque jour des millions
d’internautes font des milliards de requetes.ˆ Afin de les aider, les moteurs de
recherches classent les pages sur des criteres` independants´ de la pertinence a` la
requeteˆ afinderetournerlespageslespluspopulairesa` l’utilisateur.
LeWebspamestunenjeuimportanteconomiquement´ carilpermetauxspam
meursdesepositionneridealement´ surlesrequetesˆ a` fortbutlucratif. Des` lorsil
est primordial pour les moteurs de recherche de se debarrasser´ des tricheurs ou
a` toutlemoinsdelesreleguer´ auxdernieres` pagesderesultats.´
J’ai travaille´ sur la detection´ et le declassement´ du Webspam et dans cette
these` je presente´ deux methodes´ pour lutter contre le Webspam. Ces deux
methodes´ sont rapides et economes´ en memoire,´ ce qui est primordial lorsque
l’ontravaillesurungraphedelatailleduWeb. J’aidev´ eloppe´ cesmethodes´ avec
SylvainPeyronnet,celaadonne´ lieua` unepublicationa` laneuvieme` conference´
internationale Web Intelligence en 2010 [61] et a` un deuxieme` article publie´
au premier workshop international Web Intelligent Systems and Services en
2010[62]
Les Webspammeurs cherchent a` maximiser leur exposition sur la Toile afin
d’augmenter leurs revenus. Les moteurs de recherche ne sont pas la seule cible
des tricheurs. Avec l’arrivee´ du Web 2.0, les spammeurs peuvent avoir plus
d’influence sur les contenus trouves´ sur le Web, notamment au travers des sites
collaboratifs.
Les sites d’informations collaboratifs sont des sites Web ou` les utilisateurs
proposenteux m emesˆ lesliensversdesinformationsetpeuventvoterpourcelles
qu’ilsvoudraientvoirenpremiere` page. Lebutdestricheursestalorsd’atteindre
la premiere` page pour maximiser leur exposition. Il est donc important de blo
quer les tentatives de ces tricheurs afin de rendre nulles leurs attaques sur le
systeme.`
AvecSylvainPeyronnet,nousavonsmisaupointunschema´ devoterobuste
pour lutter contre les tricheurs sur les sites sociaux d’information. La methode´
s’appelle SpotRank et elle a et´ e´ utilisee´ dans un site Web du memeˆ nom mis
au point par Guillaume Peyronnet. Ce travail a et´ e´ present´ e´ lors du quatrieme`
WorkshoponInformationCredibilityOntheWeb[60].1.1. INTRODUCTION 9
1.1.2 Lessystemes` a` grandeechelle´
Le nombre de machines requis pour mener a` bien un calcul a` tendance a` aug
menter au fil des annees,´ ceci afin de faire perdurer la loi de Moore. On a donc
vu apparaˆıtre les clusters puis les grilles de calcul afin de pouvoir mener a` bien
lescalculsscientifiques.
Dev´ elopper des applications a` cette echelle´ est evidemment´ plus complique´
lorsdelaconceptionmaisaussilorsdestests. Ilfautetreˆ certaindemaˆıtriserun
maximumdeparametres` afindepouvoircomprendreetreproduirelesconditions
experimentales.´
Durantcettethese,` j’aitoutd’abordparticipe´a`l’elaboration´ d’unbancd’essai
pourlesapplicationsparalleles` etdistribuees´ a` grandeechelle.´ L’objectifetait´ de
fournir un emulateur´ afin de posseder´ un controleˆ complet de l’environnement
pourtesterlesapplicationsetpasunmodele` decelles ci.
Benjamin Quetier´ avait realis´ e´ une plateforme ou` les machines etaient´ vir-
tualisees´ graceˆ a` la technologie Xen [5] et ou` le reseau´ passait par des ma
chines FreeBSD. J’ai etendu´ ce banc d’essai en y ajoutant de la virtualisation
reseau´ niveaubasavecleprotocoleEtherIP[52]. Ils’agitd’untravailjointavec
FranckCappello,MathieuJan,ThomasHerault,´ SylvainPeyronnetetBenjamin
Quetier´ ayantdonne´ lieua` unepublicationa` lasixieme` conference´ internationale
ACM Computing Frontiers [47] ainsi qu’a` un chapitre de livre publie´ chez IOS
Press[46].
´J’ai ensuite rejoint un groupe de travail compose d’Aline Carneiro Viana,
Thomas Herault,´ Sylvain Peyronnet et Fatiha Za¨ıdi sur les reseaux´ de capteurs.
Dans ces reseaux´ qui peuvent etreˆ tres` etendus,´ les unites´ de calcul sont tres`
limitees´ enpuissanceetenmemoire,´ deplusleurautonomieestaussiunfacteur
important car si un trop grand nombre d’entre elles tombent en panne cela peut
deconnecter´ lereseau.´
Nous avons propose´ ensemble un nouveau protocole de dissemination´ des
donnees´ dans les reseaux´ de capteurs avec collecteur mobile. Notre protocole
requiert l’echange´ d’un nombre de messages exponentiellement plus faible que
ce qui pouvait etreˆ fait avant. L’article concernant ce protocole sera present´ e´ a`
latreizieme` conference´ internationaleACMModeling,AnalysisandSimulation
ofWirelessandMobileSystems[17].10 CHAPTER1. FRENCHSUMMARY
´1.2 DeclassementduWebspam
1.2.1 LeWebspam
LeWebspamdesigne´ l’ensembledestechniquesmalhonnetesˆ pouraccroˆıtreson
classement dans les moteurs de recherche. En effet, il est facile mais aisement´
detectable´ d’augmenter artificiellement sa pertinence concernant une requeteˆ
pour un moteur de recherche. De plus les spammeurs cherchent le plus sou
venta` ameliorer´ leclassementdepagespertinentesetinteressantes.´ Eneffetsur
leWebonnegagnepasd’argentdirectementaveclespagesdespam.
Lesspammeursconcentrentleplussouventleursattaquessurlesalgorithmes
de popularite´ des moteurs de recherche. Ces algorithmes bien connus tel le
PageRank [80] de Google ou` l’algorithme HITS [57] implement´ e´ dans des mo
teurs anglophones tres` utilises´ comme http://www.ask.com. L’algorithme de
Google donne un score de popularite´ a priori a` toutes les pages. L
HITS quant a` lui classe les pages qui arrivent en resultats´ a` une requete.ˆ Dans
un cas comme dans l’autre, le calcul de popularite´ est effectue´ sur des criteres`
purementstructurelsetnefaitpasappelaucontenudespages.
Les deux algorithmes se basent sur les liens rec¸us par les pages web pour
ev´ aluer leur popularite´ (PageRank) ou leur authorite´ (HITS). La philosophie
derriere` cette maniere` de calculer la popularite´ est la suivante, lorsqu’un site
AfaitunlienversunsiteB,AvotepourBindiquantauxsurfeursqu’ilspeuvent
ytrouverducontenuinteressant´ quimerite´ d’etreˆ vu.
Lesspammeursonttres` vitecomprisqu’iletait´ faciled’ameliorer´ artificielle
ment sa popularite.´ En effet il suffit de creer´ soi m emeˆ beaucoup de pages web
qui vont voter pour la page cible. De ce fait on recup´ ere` beaucoup de votes.
´´ `Cespagescreeesdansceseulbutnerec¸oiventquantaellespasdevotesdoncle
leur ne vaut quasiment rien. Toutefois en en creant´ suffisamment il est possible
d’ameliorer´ substantiellementmaisfrauduleusementsonscore.
Recevoir beaucoup de votes de petits votants n’est pas une strategie´ opti
male pour maximiser son score de popularite.´ Zoltan Gyongyi et al ont etudi´ e´
la structure a` mettre en place pour maximiser la popularite´ d’une page dans le
cadreduPageRankdans[38]. ChristobalddeKerchovealuiresolu´ leprobleme`
de maximiser le pagerank d’un ensemble de pages. Il propose l’architecture a`
mettreenplacedans[26].
Cestactiquesoptimalesontet´ e´ utilisees´ parlepasse´ a` grandeechelle´ parles
spammeurs afin d’ameliorer´ leur score. Toutefois les moteurs de recherche ont
rapidement mis en place des contremesures afin de detecter´ ces comportements

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin