Università degli Studi di TriesteUniversità degli Studi di TriesteDipartimento di Ingegneria e ArchitetturaDipartimento di Ingegneria e Architettura

Corso di Laurea Magistrale in Ingegneria InformaticaCorso di Laurea Magistrale in Ingegneria Informatica

Compressione di insiemi di espressioni Compressione di insiemi di espressioni regolari tramite programmazione regolari tramite programmazione

genetica in sistemi di rilevazione delle genetica in sistemi di rilevazione delle intrusioniintrusioni

Tesi di Laurea in Reti di Calcolatori II

Laureando

Simone CumarRelatore

Alberto Bartoli

Correlatore

Eric Medvet

➢IntroduzioneIntroduzione➢Problema➢Approccio➢Fase Sperimentale

BackgroundBackground

➢ Network Intrusion Detection System (NIDS)➢ Uno standard de facto: Snort

➢ Deep Packet Inspection ➢ Analisi Contenuto➢ Ricerca Signature

Deep Packet InspectionDeep Packet Inspection

➢ Ricerca Signature➢ Pattern Fissi➢ Espressioni Regolari

➢ Pesante Computazionalmente➢ Implementazione HW su FPGA

Espressioni RegolariEspressioni Regolari

➢ Descrivono pattern➢ Esempio

➢ Regex: a*(b|c)➢ Pattern: b, c, ab, ac, aab, aac, aaab...

➢ I motori di valutazione rappresentano internamente una regex con NFA o DFA

➢Introduzione➢ProblemaProblema➢Approccio➢Fase Sperimentale

OsservazioniOsservazioni

➢ NIDS usano molte Regex

➢ Importante ridurre l'impatto sul sistema

➢ Difficile implementarle in HW

Soluzioni in LetteraturaSoluzioni in Letteratura

➢ Ottimizzare passaggio Regex NFA→

➢ Ottimizzare implementazione NFA su FPGA

Soluzioni in Letteratura (2)Soluzioni in Letteratura (2)

RE

Ottimizzazione FPGA

HW

Ottimizzazione NFA

RE NFA→

NFA FPGA→

Soluzione PropostaSoluzione Proposta

RE

Ottimizzazione NFA

HW

Compressione RE

Ottimizzazione FPGA

RE NFA→

NFA FPGA→

ObiettiviObiettivi

➢ Ridurre la lunghezza delle Regex “all regular expressions are NOT created equal”

➢ Ridurre il numero di Regex

➢ Il tutto riconoscendo le stesse stringhe

““Riconoscendo le stesse Riconoscendo le stesse stringhe...”stringhe...”

➢ RE riconosce s RE estrae una sottostringa non ↔vuota di s

➢ Regex: a*(b|c)➢ Estrazione: daaabde

• a*beee• a*ceee• a*deee

• a*(b|c|d)eee

Confrontare Insiemi di Confrontare Insiemi di Espressioni RegolariEspressioni Regolari

➢ Con la definizione precedente: stringhe riconosciute da una RE infinite→

➢ Confronto su insiemi finiti di stringhe➢ Classificare stringhe

➢ Da riconoscere – Esempi Positivi➢ Da NON riconoscere – Esempi Negativi

➢Introduzione➢Problema➢ApproccioApproccio➢Fase Sperimentale

Genetic ProgrammingGenetic Programming

➢ Paradigma di calcolo evoluzionistico per l'ottimizzazione multi-obiettivo➢ Le basi

➢ Individui➢ Fitness➢ Generazioni➢ Operatori genetici – Crossover e Mutation

GP nel Nostro CasoGP nel Nostro Caso

➢ Individui➢ Ogni individuo è un'espressione regolare

➢ Fitness➢ Lunghezza➢ Distanza di edit tra la stringa estratta e quella che si desidera estrarre

➢ Popolazione Iniziale➢ Mix Regex da ridurre e casuali

StrategiaStrategia

R

Genetic Programming

R'

Classificazione Esempi

Esempi Classificati

RE da Ridurre

Strategia (2)Strategia (2)

R

Genetic Programming

R'

Classificazione Esempi Generatore Esempi

Generazione EsempiGenerazione Esempi

➢ Esempi Negativi➢ Generati casualmente

➢ Esempi Positivi➢ Generati dalle espressioni regolari

ConsiderazioniConsiderazioni

➢ GP ricerca un individuo ottimo➢ Il nostro obiettivo è un insieme di individui

Come trovare questo insieme?

Strategia di Set CoverageStrategia di Set Coverage

R'

Set Coverage

R''

Output GP

Insieme Ricoprente

Generazione di un nuovo insieme di esempi

Esempi Positivi Esempi Negativi

Selezioniamo RE con maggior accuracy

Selezioniamo RE

Eliminiamo esempi positivi riconosciuti

Positivi Riconosciuti

Selezioniamo RE con maggior accuracy sui restanti

Selezioniamo RE

Eliminiamo esempi positivi riconosciuti

Positivi Riconosciuti

Stop quando l'accuracy non può più aumentare

STOP

Accuracy NON può più aumentare

Accuracy Aumenta

Strategia di Set Coverage (2)Strategia di Set Coverage (2)

R R'

Set Coverage

R''

Regex Iniziali Output GP

Insieme Ricoprente

Set Coverage

➢Introduzione➢Problema➢Approccio➢Fase SperimentaleFase Sperimentale

Fase SperimentaleFase Sperimentale

➢ Evoluzione➢ 7 insiemi di espressioni regolari da Snort – Ruleset➢ 4 evoluzioni per insieme➢ Tempi esecuzione – da 4/5h fino a qualche giorno

➢ Testing➢ Verifica su insieme di esempi differente

RisultatiRisultati

RulesetRuleset # RE prima# RE prima # RE dopo# RE dopo RatioRatio

chat.rules.pcre 14 8 0.57

policy.rules.pcre 10 4 0.4

pop3.rules.pcre 16 2 0.13

web-php.rules.pcre 16 2 0.13

ftp.rules.pcre 35 5 0.14

spyware-put.rules.pcre 460 67 0.15

web-activex.rules.pcre 474 1 < 0.01

Diminuzione media di circa l'80% sul numero di espressioni regolari

Risultati (2)Risultati (2)

Ruleset Σ lunghezze prima Σ lunghezze dopo Ratio

chat.rules.pcre 307 82 0.27

policy.rules.pcre 260 134 0.52

pop3.rules.pcre 265 42 0.16

web-php.rules.pcre 400 127 0.32

ftp.rules.pcre 645 66 0.10

spyware-put.rules.pcre 16277 2421 0.15

web-activex.rules.pcre 59742 24 < 0.01

Diminuzione media di circa l'80% sulla lunghezza aggregata delle RE

TestingTesting

Ruleset Accuracy FPR FNR

chat.rules.pcre 100.00% 0% 0%

policy.rules.pcre 97.14% 5.13% 0%

pop3.rules.pcre 99.82% 0.36% 0%

web-php.rules.pcre 99.29% 1.43% 0%

ftp.rules.pcre 98.00% 4.09% 0%

spyware-put.rules.pcre 99.17% 1.67% 0%

web-activex.rules.pcre 100.00% 0% 0%

Accuracy superiore al 97%

FNR sempre 0%

Sviluppi FuturiSviluppi Futuri

➢ Esempi➢ Esempi più significativi

➢ Set Coverage➢ Tener conto della lunghezza RE

➢ Fitness➢ Mantenere la “biodiversità”

Grazie per l'attenzioneGrazie per l'attenzione