Embed Size (px)
Citation preview
Commentgénérerdeséchan0llonsuniformessurdesgrandesmassesdedonnées?
YannBusnel Crest(Ensai)/InriaRennes–BretagneAtlan5que
9e Colloque Francophone sur les SondagesGatineau, Canada
15Octobre2016
©YannBusnel,2016
L’escaladedelapuissance• Avant1950:lasta's'que
- quelquescentainesd’individusetquelquesvariables
- protocolestrictdelaboratoirepouruneétudescien5fique
• Années1960-1980:l’analysedesdonnées- quelquesdizainesdemilliersd’individusetquelquesdizainesdevariables
- recueilliesdefaçonrigoureusepouruneenquêteprécise
• Années1990-2000:ledatamining- plusieursmillionsd’individusetplusieurscentainesdevariables
- recueilliesdanslesystèmed’informa5ondesentreprisespourdel’aideàladécision
• Àpar6rdesannées2010:leBigData- plusieurscentainesdemillionsd’individusetplusieursmilliersdevariables
- detoustypes,recueilliesdanslesentreprises,lessystèmes,Internet,pourdel’aideàladécision,denouveauxservices
2
1950
1990
1970
1960
1980
2010
2000
©YannBusnel,2016
Quelqueschiffrespourseconvaincre
3
90 % des données existantes actuellement ont été
produite au cours des 2 dernières
années
2.500.000.000.000.000.000 octets par jour
10 m
illion
s de
dis
ques
Blu
-Ray
Données générées 4X plus vite que l’économie mondiale
1960
%
Les résultats sont tirés de l'Observatoire Big Data en France IDC 2014. Pour son Observatoire Big Data en France, IDC a interrogé en Juin 2014, 200 entreprises françaises de plus de 500 salariés dans tous les secteurs d’activité, dont les services financiers, la distribution, l'industrie, la santé, les services, le secteur public, les télécommunications et les médias.
Marché duBig Data desentreprises
Les solutions déployées
Répartition du marché du Big Data en 2014
285 M€
652 M€
24% 33% 43%
Logiciels Services Infrastructures
2014
2018
La dynamique du Big Data en France
Les bénéfices et enjeux du Big Data
Infographie sponsorisée par
Une nouvelle conception du temps réel
Importance de la mise en place d’outils Big Data autour des données
Très important
Investissement dans de nouvelles technologies de stockage pour faire
face à la croissance des données
Accès des utilisateurs à une solution Big data
en production
Utilisation / test d’une solution Big data dans
le cloud
Utilisation du Big Data pour intégrer les
informations sociales
Utilisation d’Hadoop
Construction de pilotes Hadoop
Utilisation d’une appliance base de données
Extrêmement important
Equipé En prrojet dans les 12 prochains mois
1859
+ 129%
Big Data
Données générées en interne
Données générées par des machines
(capteurs, RFID…)
Données externes
provenant de médias sociaux
Autres données externes
%
3236%
964%
%
32 44%
24 40 24 41%
24 47%
%
22 44%
19 38%
17 37
2741
HP - IDC / 2015
L’analyse en temps réel est un enjeu majeur pour 65% des métiers
33%65% 40%
Pour 40% des entreprises, le
temps de latence acceptable est inférieur à 10
minutes
Pour 1/3 des entreprises, aucun temps de latence acceptable pour
l’analyse de leurs données
60% de croissance des marges nets
possible
0,5 à 1% de la croissance de la
productivité annuelle
300 milliards $ d’économies
par an
0,7% de la croissance de la productivité
annuelle
Jusqu’à 50% de baisse des
coûts de développement
produit et d’assemblage
Jusqu’à 7% de baisse du fond de
roulement
100 milliards $ de revenus
supplémentaires pour les fournisseurs de
services
Jusqu’à 700 milliards pour les utilisateurs
finaux
250 milliards € d’économies
par an
0,5% de la croissance de la productivité
annuelle
Déjà de nombreux cas d’usage et des gains escomptés considérables
Secteur de la Santé aux US
Secteur du Retail aux US
ManufacturingLocalisation des données personnelles
(monde)
Administration du Secteur Public
en Europe
Les initiatives Big Data en forte progression
20%
33%
30%
30%
29%
25%
24%
24%
22%
22%
17%
16%
56%24%
Adoption et Projets Big Data
Adoption par secteurs d’activité
Evaluation etProjet Big Data
Adoption Big Data (solution en place / en cours)
Pas d'initiativesBig Data
Commerce
Transports
Services Financiers
Distribution
Santé
Manufacturing
Services
Utilities
Télécoms
Secteur Public
Education
©YannBusnel,2016
Variétédesdonnées
5
Info
rmat
ion
num
ériq
ue s
tock
ée
(exa
octe
ts)
1970 1980 1990 2000 2010
Données des Transactions CommercialesDonnées des Applications Web
Rupture
complexes, non-structurées
relationnelles
Il y a 10 ans : explosion du volume des données générées Les leaders du Web ont du trouver des technologies innovantes
©YannBusnel,2016
LeBigData: Buzzousujetdefond?• Depuisenviron5ans,leBigDatasusciteunintérêtgrandissantauprèsdesacteursdessystèmesd’informa9on- Éditeurs,DSI,intégrateurs,...
• Conceptdes4V- Apportedesaxesderéflexion
- Mais:pasdedéfini:onclaire
6
©YannBusnel,2016
DimensionsduBigData
7© T. Lombry
©YannBusnel,2016
Volume
«Uptoeleven»
8
Venue
VagueVocabulaire
VisibilitéVariabilité
Valeur
Validité
Véracité
Velocité
Variété
©YannBusnel,2016
Métrologiedesréseaux:Quelquesfaits
• Plusde90%desemailssontduspam• Desmilliersdebugslogicielsdécouvertparan- Environ3jourspourqu’unvirusexploitelafaille
- 30joursavantlamiseàdisposi:ond’unpatch
• Environ8000aDaquesparDoSparjour• Plusde150000aDaquesparphishingparan
9
©YannBusnel,2016
Lasurveillanceréseaux
• Courammentappeléeparsonéquivalentanglais:NetworkMonitoring
• Permetdedétecterlesanomaliesdefonc9onnement- Extrac:ondedonnéesper:nentes
• U9lité:métrologie,dimensionnementdynamique,détec9ondeDoS,...
10
©YannBusnel,2016
Surveillanceparhistorique
• Fondésurdesrésumésd’informa9onssurunepériodedetemps- Essen:elpourcomprendreetaméliorerlaperformance
- Indiquelebesoindemiseàjour/redimensionnement
- Jus:fielesdépensesnécessaires
11
©YannBusnel,2016
Surveillanceentemps-réel
• Observecon9nuellementlasitua9oncourante(aupire,récente)- U:lisépourcomprendrelesproblèmes/bugsencours
- Permetdegaran:runeréponserapideàunévènement(bug,aPaque,...)
• Plusconsommateurderessources• DifficileàmeDreenoeuvre
12
©YannBusnel,2016
Systèmesd’informa1onrépar1s
Info
13
©YannBusnel,2016
Systèmesd’informa1onrépar1s
Charge
14
©YannBusnel,2016
Systèmesd’informa1onrépar1s
Charge
Charge
Charge
Charge
Charge
15
©YannBusnel,2016
Systèmesd’informa1onrépar1s
16
©YannBusnel,2016
Systèmesd’informa1onrépar1s
17
©YannBusnel,2016
Modélisa1on
≡
A
O
Q
C
PN
J
I
E
G
K
RL
H
F
D
B
{B,D,F}
18
©YannBusnel,2016
DécentralisaBon• Avantage- Passageàl’échelleinhérent
- Capacitéd’auto-organisa:on
- Toléranceauxdéfaillances
• Inconvénient- Obten:ondesta:s:quesglobalesdifficile
- Surveillancedusystèmeextrêmementcomplexe
19
©YannBusnel,2016
Surveillanceentemps-réel: Besoind’échan8llonnage
20
©YannBusnel,2016
Tempsréel• Objec9f:obtenirdeséchan9llonsuniformesrécentsetencon9nu
• Serviced’échan9llonnageuniformecon9nu:Obtenirunfluxd’échan9llonuniforme- Abstraitparunefonc:ongetNode()quiretournel’adressed’unnoeudprésentdanslesystème
21
Echantillonnage uniformeRéseau
getNode()
id
©YannBusnel,2016
Propriétés• Uniformité- Garan&equechaquenœudpossèdelamêmeprobabilitéd’êtresélec&onnécommeéchan&llon
• Fraicheur- Adapta&oncon&nuedelapopula&ondusystème
• Efficacité- Faiblequan&témémoirenécessaire
- Tempsderéponsefaible
22
©YannBusnel,2016
Modèledefluxdedonnées
• Lefluxdedonnéesestissud’échan9llonsobtenus- viamarchealéatoire,protocoleépidémique,observa:ondesrouteurs,...
• Impossibledetoutmémorisertouslesiden9fiants
• Nonrésistantàdesadversairesmalveillants
23
©YannBusnel,2015
Unpeudeformalisme• Unfluxestunesequenced'items𝜎=<a1,a2,...>• Chaqueaiest9réd’untrèsgranduniversU={1,2,…,N}- e.g.IPv6addresses:N=2128
• Chaqueitempeutêtrereçuàplusieursreprisesdans𝜎• Unfluxdéfiniimplicitementunvecteurdefréquences(x1,x2,...)oùxiestlenombred’occurrences(oufréquence)del'itemireçujusqu'àprésentedans𝜎
• Levecteurdefréquencespeut-êtrevucommeladistribu9ondeprobabilitéempiriquede𝜎
24
p = (pi)i2U ou pi =xiP
j2U xj
©YannBusnel,2016
Modèlesd’adversaire• Capabledemanipulerungrandnombredenœuds
• AdaptesesaDaquesàlastratégied’échan9llonnage
• Objec9fdel’adversaire:biaiserleséchan9llonsdesnœudscorrects
25
getNode()
Taille C = constante
©YannBusnel,2016
EchanAllonnageuniforme:Versionomnisciente• Hypothèse:Pourchaqueitemjreçu,saprobabilitéd'occurrencepjestconnue
• Stratégieomnisciente- Sipjesttoutpe:t:onstockel’itemenmémoire
- Sinon,onl’ignorelaplupartdutemps
26
pjj
getNode()
Taille C = constante
©YannBusnel,2016
EchanAllonnageuniforme:Versionomnisciente• AlgorithmeendétailOninsèrejdanslamémoireavecuneprobabilité
aj=mini∈[N]pi/pj
Sijestinséré,onre:reunitemudelamémoireselon
ru=1/C
27
j
pjgetNode()
Taille C = constante
©YannBusnel,2016
EchanAllonnageuniforme:Versionomnisciente• AnalyseparchaînedeMarkov• Théorème: L’algorithmeomniscientgaran9el’uniformitéetlafraicheurenrégimesta9onnaire
28
j
pjgetNode()
Taille C = constante
©YannBusnel,2016
EchanAllonnageuniforme:Versionàl’aveugle
• Hypothèsetrès(trop)fortepourêtremiseenpra9que- Impossibledeprédireladistribu:ondesitems
• Nécessitéd’évaluerpienligne,pourtouti- Es:mateurdefréquence:Count-MinSketch
29
©YannBusnel,2016
Count-MinSketch[CM05]
• Es9ma9ondesfréquencesdetoutitem- (ε,δ)-approxima:on-addi:vedexi
• Main9end’unvecteurCdetaillek=2/ε• Choixd’unefonc9ondehachage2-universelle• Pourchaqueitemvduflux- C[h(v)]++ Calcul de 1/δ estimateurs
en parallèle et retour du minimum
30
[CM05]G.CormodeandS.Muthukrishnan,Animproveddatastreamsummary:thecount-minsketchanditsapplicaAons,inJournalofAlgorithms,vol.55,no.1,pp.58–75,2005.
©YannBusnel,2016
Qu’estcequ’unefoncAondehachage?
31
Fonction de hachage
Fonction de hachage
Fonction de hachage
Les sondages, c’est la vie !
Sondage
Le sondage, c’est la vie !
DFCD3419
CF682EA9
97620374
Entrée Haché
©YannBusnel,2016
H = {h : U ! [m]}
Qu’estcequ’unefoncAondehachage?
32
est universelle si 8x, y 2 U, x 6= y : Ph2H{h(x) = h(y)} 1
m
|U | = N|M | = m
©YannBusnel,2016
Exempled’unCMsketch
33
151515363636444292929999363636141414444
15 29 9 36 14 4
0 0 0 0
0 0 0 0
0 0 0 0
1
1
1
1
1
1
1
1
2
1
1
21
2
22
2
3 1
2
3 2
3
3
min=1 min=1 min=1 min=2 min=1 min=2
h1(.)
h3(.)
h2(.)
15299 3614 4364
h1(15)=1
h3(15)=2
h2(15)=3
©YannBusnel,2016
Propriétésde[CM05]
• (ε,δ)-approxima9on-addi9vedunombred'occurrencesdesitemsduflux
- xj+ε(m-xj)≥ẋj≥xj• L’inégalitédedroiteesttoujoursvraie
• L’inégalitédegaucheéchoueavecuneprobabilitéauplusδ
• Complexitéenespace:O(1/εlog1/δ(logm+logn))
34
©YannBusnel,2016
Algorithmeaveugle35
jgetNode()
Taille C = constante
pj
aj = mini∈[N] ẋi / ẋj
rj = 1 / C
©YannBusnel,2016
Algorithmeaveugle36
jgetNode()
Taille C = constante
©YannBusnel,2016
Encasd’aNaqueduflux
• Onavuque- Lastratégieomniscientegénèreunfluxuniformeet«frais»àpar:rden’importequelfluxd’entrée
- Lastratégieaveugleémulelaversionomniscienteparapproxima:ondesfréquencesdesitems
• L’uniquepossibilitéd’aDaqueestd’accroitrear9ficiellementlesfréquenceses9mées
37
©YannBusnel,2016
Lastratégieaveugleenprésencedecollusions• A3aqueciblée- L’adversaireseconcentresurunitemjspécifique
- Doitgénérersuffisammentd’itemo1,...,oltelsque• pourchaquelignesdeCM,ilexisteoi,hs(oi)=hs(j)
• A3aqueparinonda9on- L’adversairesouhaitesures&mertouslesitems
- Doitgénérersuffisammentd’itemo1,...,oltelsque• pourtoutecasevdeCM,ilexisteoi,hs(oi)=v
38
©YannBusnel,2016
Lastratégieaveugleenprésencedecollusions• A#aqueciblée
๏ L’adversaireseconcentresurunitemjspécifique
๏ Doitgénérersuffisammentd’itemo1,...,oltelsque
• pourchaquelignesdeCM,ilexisteoi,hs(oi)=hs(j)
• A#aqueparinonda3on๏ L’adversairesouhaitesures=mertouslesitems
๏ Doitgénérersuffisammentd’itemo1,...,oltelsque
• pourtoutecasevdeCM,ilexisteoi,hs(oi)=v
39
Question
Quel effort doit exercer un
adversaire pour réussir ces
attaques avec une probabilité 1-η ?
©YannBusnel,2016
AnalysedesaNaques• Modélisa9onparunproblèmed’urnes:- ChaquecasedeCMestreprésentéparuneurne
- Chaqueitemdis:nctestreprésentéparuneboule
• Oncherchelesvaleursde- Lk,t:nombredeballespourobtenirunecollisionavecunitemjdonné
- Ek:nombredeballespourobtenirunecollisionavectouslesitems
40
©YannBusnel,2016
Analysedesa3aques41
1
10
100
1000
10000
0 50 100 150 200 250 300 350 400 450 500
Lk,s
k
s = 10 | ηT = 0.5
s = 10 | ηT = 10-1
s = 10 | ηT = 10-2
s = 10 | ηT = 10-3
s = 10 | ηT = 10-4
s = 10 | ηT = 10-5
s = 10 | ηT = 10-6
Fig. 3. Number of distinct malicious node identifiers Lk,s as a function ofthe number of columns k and rows s of Matrix F , and ⌘T .
which completes the proof.
We are now able to compute, for every ` � 2, theprobabilities {N` = N`�1
}. We have
{N` = N`�1
} =
k^(`�1)X
i=1
{N` = i | N`�1
= i} {N`�1
= i}
=
1
k
k^(`�1)X
i=1
i {N`�1
= i}
=
E(N`�1
)
k
Figure 3 gives the number of distinct node identifiers Lk,s
(as defined in Relation 2) that the adversary has to inject tobias the identifier of at least one correct node. Recall thatparameters k and s of Algorithm 2 are common knowledge(except the random local coins) and thus the adversary iscapable of deriving Lk,s according to the desired probability⌘T . Lk,s is linear in k and sublinear in s and ⌘T which explainswhy attacking a single node requires a significant number ofdistinct malicious node identifiers. For instance, when k = 50
and s = 10, the adversary has to inject in the input stream 150
distinct node identifiers to have no more than 50% of chance toget its targeted attack successful. On the other hand, with thesame settings of k and s, 571 distinct node identifiers need tobe injected to guarantee with probability 0.9999 a successfultargeted attack.
Note that this analysis, as well as the one presentedin Section V-B, derives the minimum number of distinctidentifiers that need to be injected by the adversary in � tobias the output stream. It does not consider the recurrenceat which these identifiers must appear in the input stream �.As said in Section III, the effort required by an adversaryto bias the output stream is not in the repeated injection ofnode identifiers in � but rather on the cost of creation ofthese identifiers. Indeed, to own an identifier, a node typicallyneeds to interact with a central authority to receive a certificateassessing the validity and integrity of the identifier. The impactat which node identifiers recur in the input stream is analyzedin Section VI.
10
100
1000
10000
10 50 100 150 200 250 300 350 400 450 500
Ek
k
ηF = 0.5
ηF = 10-1
ηF = 10-2
ηF = 10-3
ηF = 10-4
ηF = 10-5
ηF = 10-6
Fig. 4. Number of distinct malicious node identifiers Ek as a function ofthe number of columns k of Matrix F , and ⌘F .
B. Analysis of the effort needed to make a flooding attacksuccessful
We now analyze the minimum effort that needs to beexerted by the adversary to make a flooding attack successfulwith probability 1 � ⌘F where ⌘F < 1. As for the targetedattack, we model this attack as a urn problem, where aspreviously, each entry is modeled as an urn and each receiveddistinct node identifier as a ball.
Let Uk be the number of balls needed in order to obtainall the k urns occupied, i.e., with at least one ball. It is easilychecked that {U
1
= 1} = 1 and that, for ` � k � 2, wehave
Uk = ` =) N`�1
= k � 1.
We thus have
{Uk = `} = {Uk = `, N`�1
= k � 1}= {Uk = ` | N`�1
= k � 1} {N`�1
= k � 1}
=
1
k{N`�1
= k � 1}.
From Theorem 6 and Relation (4), we get, for k � 2 and` � k,
{Uk = `} =
S(`� 1, k � 1)(k � 1)!
k`�1
=
1
k`�1
k�1X
r=0
(�1)
r
✓k � 1
r
◆(k � 1� r)`�1.
Finally, we consider the integer Ek which counts thenumber of balls needed to get a collision in all the k⇥ s urns.Note that this number is independent of s as by definition, thes experiments in parallel are identical and independent. Thus,filling entirely a set of k urns leads to obtain all the s sets ofk urns occupied. For given value of k and ⌘F 2 (0, 1), integerEk is defined by
Ek = inf
(` � k
�����X
i=k
{Uk = i} > 1� ⌘F
). (5)
Figure 4 gives the number Ek of distinct ids the adversaryhas to inject in the input stream to introduce a bias on the
8
©YannBusnel,2016
Analysedesa3aques42
1
10
100
1000
10000
0 50 100 150 200 250 300 350 400 450 500
Lk,s
k
s = 10 | ηT = 0.5
s = 10 | ηT = 10-1
s = 10 | ηT = 10-2
s = 10 | ηT = 10-3
s = 10 | ηT = 10-4
s = 10 | ηT = 10-5
s = 10 | ηT = 10-6
Fig. 3. Number of distinct malicious node identifiers Lk,s as a function ofthe number of columns k and rows s of Matrix F , and ⌘T .
which completes the proof.
We are now able to compute, for every ` � 2, theprobabilities {N` = N`�1
}. We have
{N` = N`�1
} =
k^(`�1)X
i=1
{N` = i | N`�1
= i} {N`�1
= i}
=
1
k
k^(`�1)X
i=1
i {N`�1
= i}
=
E(N`�1
)
k
Figure 3 gives the number of distinct node identifiers Lk,s
(as defined in Relation 2) that the adversary has to inject tobias the identifier of at least one correct node. Recall thatparameters k and s of Algorithm 2 are common knowledge(except the random local coins) and thus the adversary iscapable of deriving Lk,s according to the desired probability⌘T . Lk,s is linear in k and sublinear in s and ⌘T which explainswhy attacking a single node requires a significant number ofdistinct malicious node identifiers. For instance, when k = 50
and s = 10, the adversary has to inject in the input stream 150
distinct node identifiers to have no more than 50% of chance toget its targeted attack successful. On the other hand, with thesame settings of k and s, 571 distinct node identifiers need tobe injected to guarantee with probability 0.9999 a successfultargeted attack.
Note that this analysis, as well as the one presentedin Section V-B, derives the minimum number of distinctidentifiers that need to be injected by the adversary in � tobias the output stream. It does not consider the recurrenceat which these identifiers must appear in the input stream �.As said in Section III, the effort required by an adversaryto bias the output stream is not in the repeated injection ofnode identifiers in � but rather on the cost of creation ofthese identifiers. Indeed, to own an identifier, a node typicallyneeds to interact with a central authority to receive a certificateassessing the validity and integrity of the identifier. The impactat which node identifiers recur in the input stream is analyzedin Section VI.
10
100
1000
10000
10 50 100 150 200 250 300 350 400 450 500
Ek
k
ηF = 0.5
ηF = 10-1
ηF = 10-2
ηF = 10-3
ηF = 10-4
ηF = 10-5
ηF = 10-6
Fig. 4. Number of distinct malicious node identifiers Ek as a function ofthe number of columns k of Matrix F , and ⌘F .
B. Analysis of the effort needed to make a flooding attacksuccessful
We now analyze the minimum effort that needs to beexerted by the adversary to make a flooding attack successfulwith probability 1 � ⌘F where ⌘F < 1. As for the targetedattack, we model this attack as a urn problem, where aspreviously, each entry is modeled as an urn and each receiveddistinct node identifier as a ball.
Let Uk be the number of balls needed in order to obtainall the k urns occupied, i.e., with at least one ball. It is easilychecked that {U
1
= 1} = 1 and that, for ` � k � 2, wehave
Uk = ` =) N`�1
= k � 1.
We thus have
{Uk = `} = {Uk = `, N`�1
= k � 1}= {Uk = ` | N`�1
= k � 1} {N`�1
= k � 1}
=
1
k{N`�1
= k � 1}.
From Theorem 6 and Relation (4), we get, for k � 2 and` � k,
{Uk = `} =
S(`� 1, k � 1)(k � 1)!
k`�1
=
1
k`�1
k�1X
r=0
(�1)
r
✓k � 1
r
◆(k � 1� r)`�1.
Finally, we consider the integer Ek which counts thenumber of balls needed to get a collision in all the k⇥ s urns.Note that this number is independent of s as by definition, thes experiments in parallel are identical and independent. Thus,filling entirely a set of k urns leads to obtain all the s sets ofk urns occupied. For given value of k and ⌘F 2 (0, 1), integerEk is defined by
Ek = inf
(` � k
�����X
i=k
{Uk = i} > 1� ⌘F
). (5)
Figure 4 gives the number Ek of distinct ids the adversaryhas to inject in the input stream to introduce a bias on the
8
©YannBusnel,2016
Analysedesa3aques43
Settings
⌘T or ⌘F Lk,t Ekk t10 5
10
�138 44
(" ⇠ 0.3)✓� ⇠ 10
�2◆
10 5 10
�4104 110
50
5 10
�1193
306
(" ⇠ 0.05)
50
10
10
�1227
✓� ⇠ 10
�3◆
50
40
10
�1296
✓� ⇠ 10
�12◆
50 5 10
�4537
65150 10 10
�4571
50 40 10
�4640
250
10 10
�11,138 1,617
(" ⇠ 0.01)250 10 10
�42,871 3,363
Note: Parameters " and � are respectively defined
as precision (t = dlog(1/�)e) and error (k = de/"e).
2
©YannBusnel,2016
Evalua&ondeperformances
• Evalua9ondel’impactd’iden9fiantsmalveillantslargementsurreprésentés
• Tracessynthé9ques- Distribu:ons:Poissons,Pareto,Binomial
• Tracesréelles- ServeurshPp:NASA,ClarkNet,UniversitédeSaskatchewan
44
©YannBusnel,2016
Evalua&ondeperformances45
m = 40 000 items
n = 1 000 distincts
c =15
k =15
t =17
©YannBusnel,2016
Evalua&ondeperformances46
10
100
1000
10000
100000
0 100 200 300 400 500 600 700 800 900 1000
Fre
qu
ency
Node identifier
Max frequency for Knowledge-free strategy
Input StreamKnowledge-free strategy
Omniscient strategy
m = 100 000 items n = 1 000 distincts
c =10 k =10 t =5
L’adversaire injecte 50 000 fois le même item
Tous les autres présent ~50x
La stratégie aveugle réussi à réduire la plus haute
fréquence par un facteur 50
La stratégie omnisciente réussi à produire un flux
totalement uniforme
©YannBusnel,2016
Evalua&ondeperformances47
m = 100 000 items n = 1 000 distincts
c =10 k =10 t =5
Attaque ciblée : ~50 items sur-représentés
D’après le calcul de Lk,t : Attaque réussi avec une
probabilité de 0.9 si L = 48 0
200
400
600
800
1000
1200
0 100 200 300 400 500 600 700 800 900 1000
Fre
qu
ency
Node identifier
Input StreamKnowledge-free strategy
Omniscient strategy
©YannBusnel,2016
Evalua&ondeperformances48
m ~ 2 000 000 items / n = 100 000 distincts / t =5
0
0.5
1
1.5
2
2.5
NA
SA
ClarkNet
Saskatchewan
Ku
llb
ack
-Lei
ble
r D
iver
gen
ce
Input StreamKnowledge-free strategy - c = k = log nKnowledge-free strategy - c = k = 0.01n
Omniscient strategy
Commentgénérerdeséchan0llonsuniformessurdesgrandesmassesdedonnées?
YannBusnel Crest(Ensai)/InriaRennes–BretagneAtlan5que
9e Colloque Francophone sur les SondagesGatineau, Canada
15Octobre2016
Mercidevotrea,en.on
