I pattern sequenziali forniscono un’utile astrazione per la comprensione delle strategie adottate da un attaccante per raggiungere il proprio obiettivo. Il ranking dei pattern sequenziali, utilizzando le metriche viste nel Cap. 6.1, evidenzia i pattern con un supporto più alto, più lunghi, o che sono vicini al raggiungimento dell’obiettivo. In particolare, l’ultima strategia di ranking menzionata risulta essere molto utile per la predisposizione di contromisure dinamiche mirate a bloccare un attaccante che sta seguendo un pattern prima che arrivi all’obiettivo prefissato.
Tuttavia, il nostro lavoro si concentra su di un approccio differente che si pone l’obiettivo di superare la limitazione principale dei pattern sequenziali ovvero la visione locale che ciascuno di essi fornisce. Siamo interessati ad un livello di comprensione globale del comportamento degli attaccanti. Quindi, è utile definire un’astrazione che ci consenta di caratterizzare il comportamento di un attaccante. Tale astrazione ci fornirebbe una miglior comprensione riguardo l’esposizione di un sistema alla strategia di attacco di una minaccia. Un problema immediata- mente correlato a questo consiste nell’individurare un’astrazione che caratterizzi specificatamente una minaccia rispetto alle altre. Tale astrazione potrebbe essere interpretata come signature della minaccia.
Inoltre, l’astrazione della strategia della minaccia ci consente di definire un catalogo di contromisure, da applicare al sistema attraverso un nuovo design, utili anche per analisi di scenari what-if. Basti pensare, ad esempio, ad una integrazione del sistema Haruspex con il mining di pattern sequenziali in cui, iterativamente, vengono generate le sequenze di attacco, caratterizzate le strategie degli attaccanti attraverso i pattern sequenziali e definite le contromisure per poi ripetere il processo sul sistema rivisto e corretto.
Per gli esperti di sicurezza informatica è interessante individuare, tra tutti i pattern sequenziali estratti, un sottoinsieme degli stessi che abbia il massimo impatto sullo stato di sicurezza della rete. Siamo interessati a cercare un sottoinsieme di pattern con la maggiore copertura sulle sequenze di attacco. Questo tipo di problema è riconducibile a quanto noto in letteratura come Maximum Coverage Problem, MCP, ed appartiene alla classe di complessità computazionale NP-hard. Di seguito vediamo la formalizzazione del problema.
Definizione 6.1 (Maximum Coverage Problem). Dato un insieme di elementi E = {e1, e2, . . . , em}, un insieme di insiemi S = {S1, S2, . . . , Sn} in cui ciascun Si ⊆ E
ed un numero intero positivo k, il MCP consiste nel trovare un sottoinsieme S0 ⊆ S
tale che sia massimo il numero di elementi coperti |∪Si∈S0Si| rispettando il vincolo
|S0| ≤ k. Il problema può essere formulato come un problema di programmazione
maxX ej∈E yj X xi ≤ k X ej∈Si xi ≥ yj yj ∈ {0, 1} xi ∈ {0, 1}
La variabile yj descrive se l’elemento ej è coperto oppure no. La variabile xi descrive
se l’insieme Si è selezionato oppure no.
Il MCP può essere approcciato con una strategia greedy che ad ogni passo sceglie l’insieme con il maggior numero di elementi non ancora coperti [19]. È stato dimostrato che un algoritmo greedy è l’approssimazione migliore, in tempo polinomiale, per questo problema [12].
Per modellare il problema sul nostro caso di specie introduciamo quindi la definzione formale di copertura di un insieme di pattern sequenziali:
Definizione 6.2(Copertura di un insieme di pattern sequenziali). Dato un insieme di pattern sequenziali X ed un database di sequenze DB, dal quale sono stati estratti i pattern, si definisce copertura di un insieme di pattern l’insieme delle sequenze distinte in DB che sono verificate da almeno un pattern appartenente ad X. Formalmente:
Coverage(X) = {S ∈ DB | ∃ SP ∈ X ∧ SP v S}
La cardinalità di questo insieme, |Coverage(X)|, è utile per la valutazione dell’in- sieme dei pattern in quanto può essere interpretata come il grado di interesse dei pattern stessi.
Per utilizzare un algoritmo greedy si rende necessario definire una metrica sulla base della quale ad ogni iterazione verrà selezionato un pattern. Dato che ad ogni iterazione l’algoritmo deve selezionare il pattern con il maggior numero di sequenze non ancora coperte chiameremo questa metrica “copertura residua” che è definita come segue:
Definizione 6.3 (Copertura residua di un pattern sequenziale). La copertura residua di un generico pattern sequenziale SPi rispetto ad un insieme di pattern X
con copertura Coverage(X), è la cardinalità dell’insieme di sequenze che supportano SPi non ancora coperte da X. Formalmente:
CAPITOLO 6. RANKING DI PATTERN SEQUENZIALI E INSIEMI DI COPERTURA Direttamente correlata alla nozione di copertura di un insieme di pattern sequenziali vi è quella di Black Swan. Di seguito la definzione:
Definizione 6.4 (Black Swan). Data la copertura di un insieme di pattern se- quenziali Coverage(X) ed un database di sequenze DB, sul quale la copertura è stata calcolata, si definisce Black Swan l’insieme delle sequenze in DB che non sono incluse in Coverage(X). Formalmente:
BlackSwan = DB \ Coverage(X)
6.3.1
Algoritmo per il calcolo dell’insieme di copertura
L’algoritmo 6.1 calcola l’insieme di copertura per un dato insieme di pattern. Di seguito ne forniamo la descrizione.
Le istruzioni alle righe 2 e 3 inizializzano le variabili di output topK e C rispettivamente con una lista vuota e con un insieme vuoto. In topK vengono memorizzati gli identificativi dei pattern trovati e in C vengono memorizzati gli identificativi delle sequenze coperte dai pattern in topK.
L’istruzione alla riga 4 inizializza la variabile ResidualCoverage con una lista vuota. In questa lista verranno memorizzate le cardinalità degli insiemi degli identificativi delle sequenze in S. La cardinalità di un insieme in posizione i in S rappresenta la copertura residua del pattern con identificativo uguale ad i.
Alla riga 5 inizia un ciclo che si fermerà al verificarsi di una delle condizioni seguenti: è stata raggiunta la copertura del numero di sequenze indicato dalla variabile MaxSeq, è stato raggiunto il numero massimo di pattern desiderati indicato dalla variabile K oppure non esistono più pattern che possono apportare nuove sequenze ovvero con coperura residua massima diversa da 0. Quest’ultima condizione è verificata dalla guardia del costrutto if-then-else che comincia alla riga 11 e termina alla riga 20.
Dalla riga 6 alla riga 20 si svolge il ciclo del costutto while di riga 5 che ad ogni iterazione con il ciclo for, dalla riga 6 alla riga 8, calcola la copertura residua di ogni pattern e memorizza il relativo valore dentro la variabile ResidualCoverage. Da questa lista viene prelevato, con l’istruzione alla riga 9, l’identificativo del pattern con la copertura residua massima. Il relativo valore di copertura residua viene memorizzato nella variabile MaxResidualCoverage con l’istruzione della riga 10. Con l’istruzione della riga 11 si verifica che questo valore sia maggiore di 0. Se la condizione è verificata si prosegue aggiungendo l’identificativo del pattern alla lista topK e memorizzando gli identificativi delle relative sequenze coperte nella variabile Sequences. Con l’istruzione alla riga 14 si aggiungono all’insieme C gli identificativi in Sequences. Con il seguente ciclo for, dalla riga 15 alla riga
17, si ricalcola per ogni pattern l’insieme delle sequenze di copertura residua con l’operazione di sottrazione insiemistica di Sequences da ciascun insieme in S.
Se invece la condizione della riga 11 non è soddisfatta l’esecuzione dell’algoritmo passa al costrutto else, alla riga 18, che interrompe il ciclo while di riga 5 con l’istruzione break alla riga 19.
Infine con l’istruzione della riga 22 vengono prodotte in output le variabili topK e C.
Implementazione e complessità computazionale
Vediamo di seguito come sono state implementate le variabili definite nella pseudocodifica dell’algoritmo. Le liste sono state implementate utilizzando le built-in list di Python. La lista degli insiemi degli identificativi delle sequenze S e la lista degli identificativi dei top K pattern topK sono implementate in questo modo. Ciascun elemento della lista topK è un numero intero che rappresenta l’identificativo del pattern mentre per quanto riguarda la lista S ogni suo elemento è un insieme di numeri interi e ciascun numero di un insieme è l’identificativo di una sequenza. Questi insiemi di numeri interi non sono stati implementati utilizzando le built-in list di Python ma si è preferito invece ricorrere ad una struttura dati array della libreria numpy. Questa struttura dati è molto vantaggiosa sotto il profilo dell’ocuppazione in memoria rispetto alle built-in list di Python in quanto si tratta di oggetti ottimizzati per grandi quantità di dati omogenei. Nel nostro caso trattandosi di numeri interi positivi queste strutture dati sono state inizializzate con il parametro dtype=’uint32’, unsigned 32 bit integers, che specifica numeri interi positivi. Tutti gli elementi dell’array sono memorizzati in un area contigua di memoria velocizzandone l’accesso e le operazioni su di essi compiute. Inoltre su questi oggetti sono nativamente definite le operazioni insiemistiche di unione (numpy.union1d(set1,set2)) e differenza (numpy.setdiff1d(set1,set2)) che utilizziamo
per il calcolo degli insiemi di copertura e di copertura residua.
A supporto di quanto detto riguardo all’efficienza in occcupazione di memoria riportiamo un esempio. Una built-in list di Python contenente 5000 numeri interi occupa 43040 bytes mentre un array di numpy con gli stessi elementi occupa 20096 bytes (valori ottenuti con la funzione sys.getsizeof(object) di Python) evidenziando un risparmio di oltre il 50%.
Per il calcolo della complessità computazionale dell’algoritmo bisogna prendere in considerazione alcuni parametri:
• k: numero massimo di pattern cercati; • n: numero totale di pattern;
CAPITOLO 6. RANKING DI PATTERN SEQUENZIALI E INSIEMI DI COPERTURA Trattandosi di un algoritmo greedy che preleva ad ogni iterazione il pattern con la copertura residua massima la sua complessità computazionale è determinata dal numero massimo di iterazioni, dal numero totale dei pattern che deve essere esaminato, ad ogni iterazione, per la ricerca di quello con la copertura residua massima e infine dal numero massimo di sequenze che possono supportare ciascun pattern in quanto in ogni iterazione deve essere ricalcolato l’insieme di copertura residua di ciascun pattern. La complessità computazionale risultante è O(k · n · m).