martedì 20 maggio 2014

Espressioni regolari, intrusion detection e tesi di laurea

Un lavoro tratto da una tesi di laurea magistrale svolta di recente nel Machine Learning Lab è stato accettato per la presentazione ad una conferenza internazionale molto prestigiosa. Ancora una volta mi chiedo perché molti studenti in gamba preferiscano fare tesi di laurea in cui l'obbiettivo è fare qualche finestra colorata con qualche bottone altrettanto colorato usando una delle N tecnologie esistenti al momento...ma questo è un altro discorso.

Difficile spiegare sinteticamente di cosa si tratti. Ci provo.

Molte organizzazioni sono dotate di "Intrusion detection systems", sistemi che analizzano tutto il traffico in ingresso ed uscita alla ricerca di pattern indicativi di attività fraudolente. I pattern sono moltissimi. Un modo compatto per descrivere questi pattern consiste nell'utilizzo di "espressioni regolari". Ad esempio:

 ^[A-Z0-9._%+-]+@[A-Z0-9.-]+\.(?:[A-Z]{2}|com|org|net|edu|gov|mil|
biz|info|mobi|name|aero|asia|jobs|museum)$ 

è una espressione regolare che could be used to identify email addresses from any two-letter country code top level domain, and only specific generic top level domains. Un sistema di intrusion detection deve spesso applicare centinaia di espressioni regolari ad ogni singolo pacchetto e deve essere in grado di farlo "at line speed", cioè in tempo reale su ogni singolo pacchetto---un sistema che avvisa di attività fraudolente con un ritardo di ore o di giorni non è inutile ma neanche molto utile. Sono state quindi proposte molte soluzioni per rendere questo procedimento veloce ed efficiente, molte delle quali consistono nell'implementazione dei sistemi di valutazione delle espressioni regolari su hardware dedicato.

Noi abbiamo fatto una cosa radicalmente diversa: invece di ottimizzare la valutazione delle regole esistenti, abbiamo trasformato l'insieme di regole in un insieme diverso, molto più piccolo ed "equivalente sul traffico di interesse" (dettagli nel paper). In questo modo siamo riusciti a ridurre la dimensione dell'insieme di regole del 75% (!).

Post sul sito del  Machine Learning Lab.


Posta un commento