Kvantitativní analýza
internetového provozu (5)
Ladislav Lhotka
lhotka@cesnet.cz
Osnova přednášky
* Origin-destination flows
* Struktura toků, hlavní komponenty
* Vlastní toky a jejich taxonomie
* Síťové anomálie
* Metoda podprostorů
* Jak ošálit m. p.
* Rozložení vlastností toků ve vzorku
* Shluky anomálií
2
Origin-destination flows
Způsob agregace IP toků, např. podle adresového prefixu, anebo geograficky,
např. podle uzlů páteřní sítě ­ každý OD tok je charakterizován
zdrojem (origin) a cílem (destination).
V síti o n uzlech (PoP) tak máme až n2
různých OD toků.
3
39 uzlů + 7 mezinárodních linek - 2116 OD toků.
50 linek
4
Směrovací matice
Boolovská matice, která zachycuje, které linky v síti OD toky používají
(předpokládáme n linek, p OD toků):
R = [rij]i=1,...,n
j=1,...,p
rij =
{
1, jde-li j-tý tok přes i-tou linku;
0, jinak.
Je-li yi celkový objem dat na i-té lince a xj objem přenášený j-tým tokem,
platí
y = Rx. (1)
Směrovací matice se může v čase měnit.
5
Jak získáme OD toky?
1. Pokud máme jen celkové toky na linkách, můžeme zkusit "vyřešit"
rovnici (1), což je obvykle těžké (problém je obvykle silně nedourčený).
2. Snadno, pokud můžeme měřit IP toky na všech rozhraních, jimiž jsou
PoPy připojené do páteřní sítě. Origin je PoP, kde tok změříme a
destination určíme z cílové adresy (např. pomocí směrovacích proto-
kolů).
6
Časové řady OD toků
X =




X11 X12 . . . X1p
X21 X22 . . . X2p
... ... ... ...
XT1 XT2 . . . XTp




V každém řádku jsou hodnoty OD toků v daném okamžiku (např. pětiminutové
agregáty).
Kudy na ně?
* Napřed čas, pak prostor: časová řada s více proměnnými (napřed se
separuje trend a periodická složka)
* Napřed prostor, pak čas: principal component analysis.
7
Struktura OD toků
Lakhina, A. et al. Structural analysis of network traffic flows. Proceedings
of SIGMETRICS/Performance'04, New York, 2004.
V článku se aplikuje PCA na matici X.
Přechod do báze hlavních komponent:
ui = Xvi, pro i = 1, 2, . . . , T,
kde vi jsou vlastní vektory příslušné kovarianční matice.
Vektory u = (u1, u2, . . . , uT) se nazývají vlastní toky.
8
Typický vlastní tok (nahoře) a jeho zastoupení v původních OD tocích.
9
Rekonstrukce z hlavních komponent
Analýza vzorků z komerční sítě Sprint (13 PoPů) a akademické Abilene
(11 PoPů) ukazují, že původní OD toky lze reprezentovat pomocí relativně
velmi malého počtu hlavních komponent (vlastních toků). Podíl
hlavních komponent na rozptylu prudce klesá:
10
Tento obrázek ukazuje původní od tok a jeho reprezentaci pomocí 5
hlavních vlastních toků (Sprint ­ vlevo a uprostřed, Abilene ­vpravo).
11
Taxonomie vlastních toků
1. Deterministické ­ obvyklé periodicity
2. Špičkové (spike) ­ izolované "výstřelky" (alfa toky)
3. Šumové (noise) ­ náhodný šum s normálním rozdělením
12
13
Síťové anomálie
* Alfa toky: objemné krátkodobé přenosy mezi dvěma počítači;
* Denial of Service (DoS): z jednoho místa nebo distribuované;
* Flash crowd: soustředění velkého počtu klientů;
* Port scan: sondování velkého počtu portů na malém počtu cílových
adres;
* Network scan: sondování velkého počtu cílových adres s malým počtem
portů (hledání konkrétní bezpečnostní díry);
* Výpadky sítě: náhlé nebo plánované;
* Vějířovitá distribuce: šíření obsahu, např. video streaming, nové verze
distribucí Linuxu atd.
* Viry a červi
* Spam
14
Metody detekce anomálií
* signature-based (Snort)
* supervised classification (antispamové filtry)
* non-supervised classification
Parametry pro hodnocení účinnosti: false negative rate (FNR) a false
positive rate (FPR).
15
Metoda podprostorů (subspace method)
Původně vytvořena pro kontrolu kvality výroby. Zde používáme pro OD
toky.
X =




X11 X12 . . . X1p
X21 X22 . . . X2p
... ... ... ...
XT1 XT2 . . . XTp




Aplikujeme PCA a vybereme několik hlavních komponent, které generují
normální podporostor. Každé měření (v soustavě PC) pak rozložíme na
dvě složky:
Yt = ^Yt + ~Yt,
kde ^Yt leží v normálním podprostoru a ~Yt je anomálie.
Při určité velikosti ~Yt se měření prohlásí za anomální.
16
Problémy
1. Síťová data obsahují se mění periodicky i trvale (trend), takže PCA
na časově omezeném tréninkovém vzorku nemusí po nějakém čase
odpovídat. Obvykle se proto detekční systémy periodicky "přeučují"
(např. každý týden).
2. Tréninková data mohou sama obsahovat anomálie, které tím mohou
být zahrnuty pod normální provoz. Je proto dobré je z tréninkového
vzorku pokud možno odfiltrovat.
3. Obzvláště rafinovaný útočník může přidávání vhodně zvoleného umělého
provozu cíleně "otrávit" tréninkový vzorek tak, že se následně
nezachytí skutečný útok.
17
Jak ošálit metodu podprostorů
Rubinstein, B.I.P. et al. Compromising PCA-based Anomaly Detectors
for Network-Wide Traffic. Technical report UCB/EECS-2008-73, Berkeley:UCB,
2008.
Útočník přidává datový tok ct s řízenými statistickými parametry (chaff
= plevy), obvykle tak, aby zvětšil rozptyl ve zvoleném OD toku a přitom
nebyl nápadný.
18
Volba umělého toku
1. ct = |nt|, kde nt  N(0, 2
) ( je parametr). Střední hodnota je
2/  0.8 a rozptyl (1 - 2/)2
 0.362
.
2. ct = bt, kde bt nabývá hodnot 0 a 1 se stejnou pravděpodobností.
Střední hodnota je /2 a rozptyl 2
/4.
3. Pokud je na na lince z místa, odkud posíláme umělý tok, objem provozu
St větší než nějaká prahová hodnota  (např. dlouhodobý průměr),
přidáme ct = .
4. Jako předchozí případ, jen s odstupňovaným přídavkem, např. ct =
(St - )
.
19
Boiling frog
Funguje na systémy, které se periodicky přeučují (např. každý týden).
Dlouhodobá příprava, kdy se přidává umělý provoz s postupně rostoucím
parametrem . Tím se příspěvek stane nenápadným a klasifikační
metoda se otráví postupně.
Rubinstein et al. toto vyzkoušeli na datech ze sítě Abilene (27 týdnů) a
metodě podprostorů založené na PCA. Umělý tok zvyšovali postupně v
tak, aby celkový tok na první lince rostl mezi dvěma týdny o stanovený
faktor (1 %, 2 %, 5 % a 15 %). Použili metodu 4.
20
21
Rozdělení vlastností toků
Lakhina, A.; Crovella, M.; Diot, C. Mining Anomalies Using Traffic Feature
Distributions. Proceedings of ACM SIGCOMM, Philadelphia, 2005.
Některé anomálie jsou špatně detekovatelné, pokud používáme pouze
objemové charakteristiky OD toků (počty paketů/bajtů), často je ale lze
poznat ze změny distribuce některých vlastností ­ IP adres, portů aj.
22
Port scan
23
Entropie
Vhodným kvantitativním měřítkem koncentrace rozložení je entropie:
Obor hodnot dané vlastnosti X rozdělíme na N stejných intervalů a zjistíme
počty výskytů ni v každém intervalu pro i = 1, 2, . . . , N (= histogram).
Hodnota entropie veličiny X je
H(X) =
N
i=1
(
ni
S
) log2(
ni
S
).
24
Detekce port scanu pomocí objemů a entropie
25
Vícecestná metoda podprostorů
Měříme-li pro každý z p OD toků časovou řadu k parametrů, vytvoříme
matici o T řádcích a p  k sloupcích a na ni aplikujeme PCA a metodu
podprostorů.
Lakhina et al. použili data o OD tocích z akademických sítí Abilene (11
PoP, 20 dnů) a GÉANT (22 PoP, 23 dnů), které smíchali se vzorky běžných
anomálií ­ celkem 444 ve vzorku Abilene a 1011 ve vzorku GÉANT.
Pro každý OD tok byly v pětiminutových intervalech měřeny počty paketů
a bajtů a entropie těchto vlastností: zdrojová a cílová IP adresa, zdrojový
a cílový port. Metodu podprostorů aplikovali zvlášť na objemové
parametry a na entropie.
26
Úspěšnost detekce anomálií
27
Klasifikace anomálii
Lakhina et al. dále použili shlukovou analýzu pro automatickou klasifikaci
anomálií. Jako míru nepodobnosti použili vzdálenost anomálních složek
entropií (tj. bez normální složky po rozkladu do podprostorů). Každá
anomálie tvořila jasně oddělený cluster (nebo i více clusterů).
28
29
Optimální počet clusterů
Mírou pro nalezení vhodné granularity clusterů jsou celková vzdálenost
uvnitř clusterů (čím menší, tím lepší) a celková vzdálenost mezi clustery
(čím větší, tím lepší).
30