Applicazione di metodi statistici alla
classificazione del traffico in reti dati
Alessandro Finamore
Relatori:
Marco Mellia
Fabio Neri
Il problema della classificazione
Internet
Service
Provider
Traffico
generico
Qual è il protocollo
della comunicazione?
1/17
Il problema della classificazione
Skype
Porta:
Payload:
Gtalk
Porta:
Payload: protocollo RTP
2/17
Bittorrent
Internet
Service
Provider
Porta:
Payload: “bittorrent”
eMule
Porta: 4662/4672
Payload: E4/E5
Classificazione statistica
Traffico
noto
Fase 1
Fase 2
Fase 3
Statistiche
Predizione
Testing
Caratterizzazione statistica delle comunicazioni
Sviluppo del sistema di predizione
Analisi degli errori di classificazione
3/17
Classificazione statistica
Traffico
noto
Fase 1
Fase 2
Fase 3
Statistiche
Predizione
Testing
Caratterizzazione statistica delle comunicazioni
Test c2
4/17
Chunking e c2
Primi N byte
C chunks
da
b bits
2
2
c
c
[ ,…, ]
1
C
Vettore di statistiche
5/17
Frequenze dei
valori assunti
dai chunk
Distribuzione
uniforme
Esempio di chunk di 4bit
random
6/17
Esempio di chunk di 4bit
deterministico
random
6/17
Esempio di chunk di 4bit
deterministico
mixed
random
6/17
Esempio di chunk di 4bit contatore
7/17
Classificazione statistica
Traffico
noto
Fase 1
Fase 2
Fase 3
Statistiche
Predizione
Testing
Caratterizzazione statistica delle comunicazioni
Test c2
Sviluppo del sistema di predizione
Distanza geometrica tra punti in uno spazio
8/17
Classificazione geometrica
[c21 , … , c2C]
c2j
Iperspazio
classe
Regioni di
classificazione
classe
Distanza
Euclidea
9/17
Support
Vector
Machine
classe
non nota
c2i
Distanza Euclidea
Centroide
cj2
media aritmetica
10/17
c2i
Distanza Euclidea
Centroide
media aritmetica
cj2
Veri Neg.
“lontani”
Veri Pos.
“vicini”
10/17
c2i
Distanza Euclidea
Centroide
cj2
media aritmetica
Ipersfera
10/17
Falsi Positivi
c2i
Distanza Euclidea
Centroide
cj2
media aritmetica
Ipersfera
10/17
Falsi Negativi
c2i
Distanza Euclidea
Centroide
cj2
media aritmetica
Ipersfera
min { Falsi Pos. }
min { Falsi Neg. }
Affidabilità
distanza euclidea
10/17
c2i
Support Vector Machine
Kernel functions
Clusterizzazione più
semplice
Spazio dei
campioni
(dim. D)
Kernel function
Spazio delle
feature
(dim. ∞)
11/17
Support Vector Machine
Kernel functions
Support vectors
Clusterizzazione più
semplice
Margine
Massimizzazione
Bordo di classificazione
Support Vector
LibSVM
Support vectors
11/17
Support Vector Machine
Kernel functions
Clusterizzazione più
semplice
Margine
Massimizzazione
Bordo di classificazione
Support Vector
LibSVM
Classificazione
Distanza dal bordo
Probabilità
11/17
p(
 classe
)
Classificazione statistica
Traffico
noto
Fase 1
Fase 2
Fase 3
Statistiche
Predizione
Testing
Caratterizzazione statistica delle comunicazioni
Test c2
Sviluppo del sistema di predizione
Distanza geometrica tra punti in uno spazio
Analisi degli errori di classificazione
Analisi dei Falsi Positivi e Falsi Negativi
12/17
Analisi delle tracce dati
Internet
Traccia
circa 1 giorno
di cattura
20 GByte di
traffico UDP
RTP
eMule
DNS
other
Traffico
noto
Training + Other
Traffico noto
Fastweb
13/17
Traffico generico
Traffico
generico
Modello
Falsi Negativi
Falsi Positivi
Errori % per alcuni casi critici
Distanza euclidea
Rtp
Traf. noto
(Falsi Neg.) Edk
Dns
Caso A Caso B
0.08
0.23
13.03
7.97
6.57
19.19
Caso A Caso B
Traf. gen.
13.6 17.01
(Falsi Pos.) other
SVM
Caso A Caso B
0.01
0.08
3.99
0.1
1.39
2.36
Caso A Caso B
36.68 26.92
Le SVM descrivono bene la geometria delle nuvole
… ma è difficile eliminare lo spazio non rappresentativo
Introduzione di una classe complementare
14/17
Errori % per alcuni casi critici
Distanza euclidea
Rtp
Edk
Dns
Caso A Caso B
0.08
0.23
13.03
7.97
6.57
19.19
Caso A Caso B
other
13.6 17.01
15/17
SVM
SVM con classe
complementare
Caso A Caso B
0.01
0.08
3.99
0.1
Caso A Caso B
0.05
0.98
0.54
1.39
2.36
0.12
2.14
Caso A Caso B Caso A Caso B
36.68 26.92
0.18
Prestazioni
Effettuate solo analisi offline
Valutazione puntuale difficile
Il calcolo del c2 può richiedere molta memoria
Numero di bit per chunk
Numero di chunk
La tempistica di predizione è lineare
Numero di bit per chunk
Numero di chunk
Numero di protocolli
Numero di Support Vector
Attraverso ottimizzazione mirate è possibile ottenere
risultati anche online
16/17
Conclusioni
2
Il c è un utile operatore di classificazione
Un semplice classificatore a distanza euclidea può
essere efficace
Le SVM danno risultati migliori ma richiedono l’uso di una
classe complementare
17/17