# 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