Bloom Filters

Ottobre 2006
Bloom Filters
Olivier Morandi
[email protected]
Ottobre 2006
Set-membership query
Lookup
Insieme S = {x1, x2, …, xn}
1 iff k Є S
Dato k, lookupS(k) =
0 iff k Є S
Implementazioni
Linked List
Balanced Binary Search Tree
Storage: O(N)
Lookup: O(1)
Array o bit-vector
Bloom Filters - 2
Storage: O(N)
Lookup: O(log2 N)
Hash-Set
Storage: O(N)
Lookup: O(N)
Storage: O(N), con grande spreco di memoria se l’insieme è sparso
Lookup: O(1)
Ottobre 2006
Bloom Filters
Se si è disposti a sacrificare un certo grado di
accuratezza nelle operazioni di lookup, a favore
dell’efficienza in occupazione di memoria della
rappresentazione del set, una possibile soluzione è
data dall’impiego di strutture dati particolarmente
compatte: i Bloom Filters
Inventati da Burton Bloom nel 1970 per ottimizzare le
operazioni di lookup in dizionari per lo spellchecking
Stanno riscuotendo un rinnovato successo nelle
applicazioni di networking
Bloom Filters - 3
Reti P2P: possono essere impiegati per riassumere in
forma compatta le liste di contenuti da condividere
Resource routing: consentono di implementare algoritmi
probabilistici per la localizzazione di risorse
Misure e statistiche: i Bloom Filters forniscono uno
strumento per l’acquisizione di statistiche sul traffico nei
router e nei dispositivi di rete
Ottobre 2006
Bloom Filters
The Bloom Filter principle:
“Wherever a list or set is used, and space is
a consideration, a Bloom Filter should be
considered.
When using a Bloom Filter, consider the
potential effects of false positives.”
Bloom Filters - 4
Ottobre 2006
Standard Bloom Filters
Un Bloom Filter consente di mappare un insieme S = {x1, x2, …, xn}
di n elementi su un bit-vector B di m elementi inizialmente posti a
0 (eventualmente con m<<n)
Il filtro è composto da k funzioni di hash indipendenti h1(x), …,
hk(x), che producono un valore (si suppone distribuito
uniformemente) nel range [1..m]
Su ogni elemento xi (1 ≤ i ≤ n) del set si applicano in sequenza le k
funzioni di hash z1 = h1(xi), …, zk = hk(xi) e si pongono ad 1 gli
elementi zk all’interno del bit-vector B
Un bit in B può essere posto ad 1 più di una volta
Set S = {x1, x2} n = 2
Bloom Filter
h1(x1)
k=3
h2(x2)
h1(x2)
Bit-Vector B: 1
m = 10
Bloom Filters - 5
1
h2(x1)
h3(x2) h3(x1)
0
0
1
0
0
1
1
0
1
2
3
4
5
6
7
8
9
10
Ottobre 2006
Standard Bloom Filters
Per verificare che un generico elemento y
appartenga ad S, le k funzioni di hash del Bloom
Filter vengono applicate ad y:
z1 = h1(y), …, zk = hk(y)
y appartiene ad S se e solo se tutti gli elementi B[z1],
…, B[zk] del bit-vector sono posti ad 1
y1 Є S, y2 Є S
Bloom Filter
h1(y1)
h3(y2)
k=3
h1(y2)
Bit-Vector B: 1
m = 10
Bloom Filters - 6
1
h2(y2)
h2(y1)
h3(y1)
0
0
1
0
0
1
1
0
1
2
3
4
5
6
7
8
9
10
Ottobre 2006
Caratteristiche dei Bloom Filters
Se l’esito del lookup è negativo, allora l’elemento
non appartiene sicuramente all’insieme
Se l’esito del lookup è positivo, è possibile che
l’elemento appartenga all’insieme, con una certa
probabilità di errore
Possibilità di falsi positivi
Le funzioni di hash calcolate su valori diversi possono
portare allo stesso risultato
Nella fase di test, è possibile che uno hash restituisca
l’indice di una posizione precedentemente impostata
ad 1 per un altro elemento dell’insieme
Particolarità:
Bloom Filters - 7
L’unione di due insiemi si ottiene ponendo in OR i
rispettivi Bloom Filters
Ottobre 2006
Bloom Filters
Probabilità di errore
Probabilità di avere un falso positivo:
P = (1 - ekn/m)k
Fissando uno o più parametri nella funzione
della probabilità di errore, è possibile
ottimizzare altri parametri per ottenere le
prestazioni desiderate
Ad esempio, fissati n ed m, è possibile
trovare il k (numero di funzioni di hash) che
minimizzi la probabilità di errore
Bloom Filters - 8
Ottobre 2006
Counting Bloom Filters
L’operazione di inserimento di un elemento nel Bloom Filter non è
invertibile
Non è possibile rimuovere in modo semplice gli elementi
I Counting Bloom Filters consentono di superare tale limitazione
sostituendo i bit del bit-vector con dei contatori
Quando un elemento viene inserito, i rispettivi k contatori vengono incrementati
di 1
Quando un elemento viene rimosso, i rispettivi k contatori vengono
decrementati di 1
I contatori devono essere di dimensione sufficiente ad evitare casi di
overflow
Nella pratica, 4 bit per contatore sono spesso sufficienti
Set S = {x1, x2} n = 2
Bloom Filter
h1(x1)
k=3
h2(x2)
h1(x2)
Counters Array B: 2
m = 10
Bloom Filters - 9
1
h2(x1)
h3(x2) h3(x1)
0
0
1
0
0
1
1
0
1
2
3
4
5
6
7
8
9
10
Ottobre 2006
Bloom Filters
Applicazioni in reti P2P (I)
Ogni nodo di una rete P2P ha bisogno di conoscere
gli oggetti o i contenuti resi disponibili da tutti gli
altri nodi
Mantenere intere liste di oggetti associate agli altri
nodi della rete sarebbe proibitivo
Invece di utilizzare veri e prori database di oggetti è
possibile associare ad ogni altro nodo un Bloom
Filter che rappresenti l’insieme degli oggetti che
questo rende disponibili
Se un’operazione di lookup in un Bloom Filter porta
ad un falso positivo, il risultato è semplicemente una
query ad un nodo remoto per un oggetto che in
realtà non possiede
Accettando una certa probabilità di errore si
risparmia in occupazione di memoria
Bloom Filters - 10
Ottobre 2006
Applicazioni in reti P2P (II)
Approximate Set Reconciliation
Si supponga che A condivida gli oggetti
rappresentati dall’insieme SA e che B condivida gli
oggetti rappresentati da SB
B vuole sapere quali elementi ci sono in SA in modo
da richiedere ad A gli oggetti che gli mancano (cioè
S A - SB )
Soluzione:
Bloom Filters - 11
B invia ad A un Bloom Filter (BF) del set SB
A, tramite una serie di lookup nel Bloom Filter verifica
quali dei propri elementi potrebbero essere in SB ed
invia a B gli oggetti che questo sicuramente non
possiede
A causa dei falsi positivi alcuni degli elementi di A,
mancanti a B, non verranno trasferiti
Ottobre 2006
Bloom Filters
Intrusion Detection System
Match!
Rule
Rule Set
Set
(e.g.
(e.g. ~3000
~3000 Snort
Snort Rules)
Rules)
Forwarding Element
DATA PLANE
IDS
ENGINE
Input
packets
Gli algoritmi di string & pattern matching
tradizionali non funzionano bene a wire-speed
Bloom Filters - 12
Ottobre 2006
Deep Packet Inspection using
Parallel Bloom Filters*
Il sistema IDS è composto da due moduli principali
Un modulo lavora a wire-speed ed indica la possibilità
che il pacchetto abbia un contenuto sospetto
Un altro modulo, più lento, viene attivato solo per i casi
dubbi ed effettua una ricerca esaustiva di possibili
attacchi
Forwarding Element
DATA PLANE
IDS
IDS ENGINE
ENGINE
Deterministico
Deterministico
(più
(più lento)
lento)
IDS ENGINE
Input
packets
Probabilistico
Classifier
Classifier
(wire-speed)
* Sarang Dharmapurikar, Praveen Krishnamurthy, Todd S. Sproull, John W. Lockwood, "Deep Packet
Inspection using Parallel Bloom Filters," IEEE Micro, vol. 24, no. 1, pp. 52-61, Jan/Feb, 2004.
Bloom Filters - 13
Ottobre 2006
Deep Packet Inspection using
Parallel Bloom Filters
Il modulo più lento (analyzer) implementa un algoritmo di string
matching esatto
Il modulo più veloce è composto da un insieme di Bloom Filters
implementati in Hardware
Bloom Filters - 14
Le signature degli attacchi vengono inserite in diversi Bloom Filters in
base alla loro lunghezza
Diverse
porzioni
del
pacchetto
vengono
ricercate
contemporaneamente all’interno dei vari Bloom Filters
Se c’è un match il pacchetto viene inviato al modulo di pattern
matching esatto per un controllo più accurato, ma solo sull’insieme di
regole della lunghezza corrispondente al filtro che ha ottenuto un
match
Ottobre 2006
Deep Packet Inspection using
Parallel Bloom Filters
Bloom Filters - 15