Shrnutí poslední přednášky Časové řady Shlukování Další metody PV210 Bezpečnostní analýza síťového provozu Pokročilé metody zpracovávající síťové toky Mgr. Tomáš Jirsík 12. 11. 2014 Osnova Shrnutí poslední přednášky Časové řady Shlukování Jednoduché metody zpracovávající informace o tocích I shrnutí Časové řady Shlukování Další metody Shrnutí poslední přednášky Časové řady Shlukování Další metody Shrnutí Agregace provozu v podobě síťových toků je dobrým stavebním kamenem jednoduchých metod. Metody zpracovávající záznamy o tocích jsou v porovnání s inspekcí paketů velmi rychlé. I jednoduché metody (např. detekce TCP SYN skenů) jsou v praxi velmi užitečné. Shrnutí poslední přednášky Časové řady Shlukování Pokročilé metody zpracovávající síťové toky • Časové řady • Klouzavý průměr • Holt-Wintersova metoda • Analýza hlavních komponent • Shlukování a hledání odlehlých pozorování • K-means • Local Outlier Factor • Další metody Shrnutí poslední přednášky Časové řady Shlukování Časové řady Využití v síťovém provozu • Cíl - automatizovat detekci anomálií (pohled na graf a následné nalezení špiček). • Hlavní myšlenka využití: • porovnání predikce a reálně naměřené hodnoty • pokud se hodnoty liší o více než je "únosná míra", je detekována anomálie Osnova Shrnutí poslední přednášky Časové řady Shlukování Další metody Časové řady Klouzavý průměr Shrnutí poslední přednášky Časové řady Další metody Klouzavý průměr rSOOO Průběh časové řady MAX: 5432 MIN: 1 ■ Průměr: 1225 Uživatelské pásmo netolerance Detekovaná anomálie Systémové pásmo netolerance netolerance ^■^■^^■^^■^^■^^^B | posuvné okno | = 12 hodnot 1 Cas 11 rnutí poslední přednášky Časové řady Shlukování Časové řady Holt-Wintersova metoda Osnova Shrnutí poslední přednášky Časové řady Shlukování Další metody Úvod • V literatuře také jako trojité exponenciální vyhlazování (triple exponential smoothing). • Navržena v roce 1957 Holtem, v roce 1960 vylepšena Wintersem. • Původní využití predikce časové řady. • Časová řada je posloupnost pozorování jedné nebo více náhodných veličin uspořádaná v čase. Shrnutí poslední přednášky Časové rady Shlukování Předpoklady ekvidistantní časový interval. časová řada může být rozložena na tři komponenty základnu, lineární trend a sezónní trend. Osnova Shrnutí poslední přednášky Časové řady Shlukování Další metody Předpoklady Decomposition of additive time series / if] 1 Shrnutí poslední přednášky Časové řady Shlukování Další Využití v síťovém provozu Metoda je vhodná i pro síťový provoz a toky. Časové řady objemových charakteristik mnohých služeb totiž vykazují toto chování (příklad): • Trend: postupné zvyšování požadavků na nějakou službu v čase. • Sezónnost: nejvíce požadavků se objevuje dopoledne, odpoledne méně a v noci obvykle minimum. • Sezónní proměnlivost: ve špičce je zaznamenána velká fluktuace počtu požadavků, kdežto v noci ne. • Postupný vývoj všech předcházejících složek v čase: vliv letního času na počty požadavků v průběhu dne. Osnova Shrnutí poslední přednášky Časové řady Shlukování Další metody Vizualizace předpovědi Holt-Wintersovou metodou Osnova Shrnutí poslední přednášky Časové řady Shlukování Další metody Holt-Wintersova metoda podrobně • Mějme časovou řadu: /i.../ř-i,/ř,/ř+i, t je aktuální čas. • Předpovídaná hodnota v časové řadě se vypočítá takto: /ř+1 = at + t>t + Cř+i_m • m označuje periodu sezónního trendu (např. počet pozorování za den). • Základna: a, = a(yt - ct-m) + (1 - a)(ař-i + fcf-i) • Lineární trend (sklon): bt = /3{at - af_0 + (1 -/3)Vi • Sezónní trend: ct = 7(/f - af) + 0 - l)ct-m Osnova Shrnutí poslední přednášky Časové řady Shlukování Další metody Holt-Wintersova metoda podrobně - pokr. • a, (3,7 jsou parametry adaptace. 0 < a, (3,7 < 1. • Hodnoty blíže k 1 povedou k rychlejší adaptaci, hodnoty blíže k 0 k opaku (větší důraz bude kladen na historii). • Důležité je vhodně zvolit tyto parametry a to je docela problematické. • Pozor na otrávení učení • Tuto „otrockou" práci může za nás dělat někdo jiný (až na volbu parametrů). Např. aplikace R, konkrétně funkce HoltWintersQ (http: / /www. r-pro ject. org/ nebo v balících vaší oblíbené linuxové distribuce) nebo nástroj rrdtool. Osnova Shrnutí poslední přednášky Časové řady Shlukování Další metody Časové řady Analýza základních komponent Principal component analysis (PCA) Osnova Shrnutí poslední přednášky Časové řady Shlukování Další metody Úvod do PCA • Cíl: rozdělit skupinu vzájemně korelovaných pozorování na vzájemně nekorelované • Využití ortogonální transformace První základní komponenta vysvětluje co nejvíce variability v datech, další obsahuje co nejvíce zbylé variability atd... • Využití pro oddělení anomálního provozu od normálního. Osnova Shrnutí poslední přednášky Časové řady Shlukování Další metody x 107 Vizualizace PCA OD flow b-i x 107 Linkf-i x 10° Linkd-f J x 10 Link c-c x 10° Link b-c / Wed Thu Fri Shrnutí poslední přednášky Časové řady Shlukování Další metody Shluková analýza Vícerozměrná statistická metoda používaná ke klasifikaci objektů. Jednotky náležící do stejné skupiny jsou si podobnější než objekty z různých skupin. Je možné provádět jak na množině objektů, z nichž každý musí být popsán prostřednictvím stejného souboru znaků, které má smysl v dané množině sledovat, tak na množině znaků, které jsou charakterizovány prostřednictvím určitého souboru objektů, nositelů těchto znaků. Osnova Shrnutí poslední přednášky Časové řady Shlukování Další metody Shluková analýza K-means Osnova Shrnutí poslední přednášky Časové řady Shlukování Další metody K-means • Vícerozměrná statistická metoda používaná ke klasifikaci objektů. • Využití ke klasifikaci provozu na normální a anomální • Cíl: rozdělit pozorování na k skupin, tak aby minimalizovaly k argmm^ || xj - /i,- || (1) /=1 XjeSi kde fij je průměr ve skupině s, Osnova Shrnutí poslední přednášky Časové řady Shlukování Další metody K-means 6 Bl-1-,-,-,-,-,-,-,-,-1 -5 -4 -3 -2 -1 0 1 2 3 4 5 https://www.youtube.com/watch?v=_aWzGGNrcic Osnova Shrnutí poslední přednášky Časové řady Shlukování Další metody K-means Shrnutí poslední přednášky Časové řady K-means Shlukování Nevýhody metody: • Rozdělí data do skupin, ale neurčí, zdaje skupina anomální, či ne. • Určit počet skupin, do kterých se mají data rozdělit. Shrnutí poslední přednášky Časové řady Shlukování Shluková analýza Local Outlier Factor (LÖF) Osnova Shrnutí poslední přednášky Časové řady Shlukování Další metody Princip Definice odlehlého pozorování: • An outlier is an observation that deviates so much from other observations as to arouse suspicion that it was generated by a different mechanisms 1 Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng, Jorg Sander LOF: Identifying Density-Based Local Outliers Osnova Shrnutí poslední přednášky Časové řady Shlukování Dosažitelná vzdálenost: (Reachability Distance) RDk(A,B) = \ Výpočet { k-distance(e),c/(Ae)} Osnova Shrnutí poslední přednášky Časové řady Shlukování Výpočet Místní hustota dosažitelnosti: (Local Reachability Density) lrd{A) = 1 / Local Outlier Factor: \Nk(A)\ LOF*^)- \Nk{A)\ - \Nk(A)\ /lrd{A) Shrnutí poslední přednášky Časové řady Shlukování Osnova Shrnutí poslední přednášky Časové řady Shlukování Další metody Minnesota Intrusion Detection System (MINDS) • Navrženo pro velké sítě (Univerzita v Minnesotě, 2002). Pracuje s NetFIow daty v lOminutovém časovém okně. • Nejprve je provedena feature extraction - pro každý tok jsou spočítány klíčové položky. • Cílem detekce je najít spojení s „vyčnívajícími" (outliers) položkami = anomálie síťového provozu. • Detekce vyžívá Local Outlier Factor (LOF). • LOF stojí na předpokladu, že vlastnost „vyčnívání" není binární, že lze vyjádřit míru „vyčnívání". • Local- míra vyčnívání je počítána jen v uzavřeném sousedství objektu. Osnova Shrnutí poslední přednášky Časové řady Shlukování Další metody MINDS: extrakce položek • Používají se dva typy položek. • Time window-basedJsou extrahovány z toků za posledních t sekund. • Z principu není možné zachytit anomálie trvající déle než t sekund (např. pomalé skenování portů). • Connection window-based z posledních n toků odchozích z různých zdrojů/příchozích na různé cíle. Osnova Shrnutí poslední přednášky Časové řady Shlukování Další metody MINDS: typy položek Time window-based features: • count-dest, number of flows to unique destination IP addresses inside the network in the last f seconds from the same source, • count-src, number of flows from unique source IP addresses inside the network in the last f seconds to the same destination, • count-serv-src, number of flows from the source IP to the same destination port in the last f seconds • count-serv-dest, number of flows to the destination IP address using same source port in the last f seconds. Connection window-based features: • count-dest-conn, number of flows to unique destination IP addresses inside the network in the last n flows from the same source • count-src-conn, number of flows from unique source IP addresses inside the network in the last n flows to the same destination • count-serv-src-conn, number of flows from the source IP to the same destination port in the last n flows • count-serv-dest-conn, number of flows to the destination IP address using same source port in the last n flows. Osnova Shrnutí poslední přednášky Časové řady Shlukování Další metody MINDS: zhodnocení • Navrženo a experimentálně vyzkoušeno v roce 2002. • Úspěšně detekován SQL červ Slammerv prvotním stádiu šíření, kdy tvořil jen 2% celkového provozu. • Snort na základě detekce signatur neodhalil tuto mutaci červu. • Výpočetně náročné: LOF počítá vzdálenosti mezi každými dvěma body, tzn. 0(n2). • Pro velké sítě nutno použít vzorkování, to však může mít vliv na přesnost detekce. • Zdrojové kódy MINDS však nejsou dostupné. Shrnutí poslední přednášky Časové řady Další metody Přehled dalších metod Network Anomaly Detection Methods Statistical Classification Based Clustering and Outlier Based Soft Computing Knowledge Based Combination Learners a. Parametric b. Non-parametric a. GA based b. ANN based c. Fuzzy set d. Rough set e. Ant colony and AIS a. Rule and expertsystem b. Ontology and logic based a. Ensemble based b. Fusion based c. Hybrid Osnova Shrnutí poslední přednášky Časové řady Shlukování Další metody Entropie • Nechť X = {rij, / = 1,..., A/}, kde hodnota / nastává Dj krát v tomto vzorku. N je počet různých hodnot. • Entropie vzorku (sample entropy) je pak definována takto: • S je celkový počet pozorování. • Hodnota entropie leží v intervalu [0, log2N]. • Entropie je rovna nule, právě tehdy když jsou všechna pozorování stejná. • Entropie je log2N, právě když jsou četnosti stejné, tj. m = n2 = ■ ■ ■ = nN N N • Relativní entropie: h(X) H(X) H(X)