Piattaforme e Software per la rete - lezione 13

Giacomo Verticale

26 April 2016

IP Traceback

Per un pacchetto osservato ad certo nodo, ci interessa sapere da dove il pacchetto è entrato nella rete e che nodi ha attraversato. Vediamo pacchetto P in V Vogliamo ricostruire il suo percorso nella rete. Possiamo mandare un altro pacchetto verso la stessa sorgente, ma essendo il routing asimmetrico, non è detto che un pacchetto nella direzione opposta seguirà lo stesso percorso. Altrimenti possiamo loggare tutti i pacchetti e chiedere ai vicini del nodo ricevente se hanno visto il pacchetto in questione. Un altro problema è che il pacchetto man mano che viaggia nella rete cambia alcuni dei suoi campi. Inoltre salvare su disco tutti i pacchetti è oneroso come capacità richiesta e velocità. Un terzo motivo è che i log stessi diventano un bersaglio interessante per gli intrusi. Serve una soluzione con costo computazionale costante, anche a costo di aumentare la probabilità di falsi positivi.

Una soluzione adottata sono i filtri di Bloom

Filtro di Bloom

Implementa in modo efficiente anche se non esatto il test di appartenenza ad un insieme. I browser ultimamente ci mettono tempo ad avviarsi perchè scaricano l'ultimo aggiornamento del filtro di bloom con la lista dei siti malicious. Le operazioni consentite sono:

Inizializzazione
Inserimento
Test

Per implementarlo ci serve:

h_i(x) una famiglia di k funzioni hash indipendenti.
A array binario di m elementi inizialmente nullo

è analogo alla tecnica di classificazione dei pacchetti.

INSERT(x)
FOR i<-1,k
    A[h_i(x)]=1

Do in pasto il mio input a tutte le funzioni di hash e setto a 1 le posizioni risultanti nell'array, se sono già a 1 le lascio così. All'aumentare delle funzioni di hash aumenta la probabilità di riempire l'array.

TEST(x)
FOR i<-1,k
    IF A[h_i(x)]==0 THEN
        RETURN 0
    END IF
END FOR
RETURN 1

Se durante l test trovo 1 in tutte le posizioni, potrei avere un match che però potrebbe essere un falso positivo

In pratica il sistema viene dimensionato in modo da rendere trascurabile la probabilità di falso positivo.

Probabilità errore

Prob che elemento j di a sia pari a 0 dopo 1 inserimento. =(1-1/m)^h
Prob [A(j)=1 | n] =1-(1-1/m)kn
Probabilità di falso positivo Equivale al caso in cui la probabilità precedente si verifica per k funzioni hash = [1-(1-1/n)^kn]^k=~[1-exp(kn/n)]^k

Esempio

Supponiamo di avere un bloom filter con m=5 e k=2

h_1(x) = x*mod5
h_2(x) = (2x+3)*mod5 Una funzione di hash pessima è h(x)=2xmod8 perchè l'ultimo bit rimane sempre a 1 Un'altra cattiva scelta di funzioni hash è quando le funzioni hash sono correlate e quidi non producono più output indipendenti. Richieste:
Inserire x=9 e x=11
Testare x=15 e x=16

Filtro vuoto = 00000 Inserisco x=9:

h1(9)=4 h2(9)=1 Risultato = 01001 Inserisco x=11
h1(11)=1 h2(11)=0 Risultato = 11001 Test
h2(15)=0 h2(15)=3

Consideriamo il sistema visto applicato ad un router x= identificativo del flusso lunghezza pacchetti = 512byte Su x sono calcolati n hash dalla famiglia hi(x) con 1<=i<=n tali hash sono usati come indici in n array di m elementi A1,A2,...,An. Ad ogni pacchetto si incrementa Ai[hi(x)] per ogni i Se Ai[hi(x)]>=S per ogni i, salvo x su disco.

Tutti array azzerati ogni T=10s 1- Dire quali campi scegliere per X per avere nello stesso flusso i pacchetti verso lo stesso socket nello stesso host. x = IP dest || porta || porta dest

Come scegliere S in modo da selezionare tutti i flussi da almeno 25Mbit/s

S=(25*10^6bit/s*10s)/8*512 =61036 pacchetti

Un certo flusso g ha superato la soglia considerando m = 2^8 e n=3 oltre la prob che un nuovo flusso sia selezionato dire la probabilità che un nuovo flusso sia selezionato

Pr(hi(x)=hi(y)) per un dat i = 1/m Probabilità di falso positivo = (1/m)^n =1/2^24=~6*10^-8

lesson_13.md 3.8 KB Historie Surový