Adversarial Clustering

Gli algoritmi di clustering vengono sempre più di frequente utilizzati con lo scopo di individuare attività illecite o malevole all'interno di grossi volumi di dati. Un esempio è rappresentato dalle applicazioni di malware clustering, dove l'obiettivo è quello di individuare delle famiglie di malware con caratteristiche uniformi. A partire da queste famiglie, è possibile creare delle firme che, una volta installate all'interno di un anti-virus o di un intrusion detection system signature-based (come Snort) consentono la rilevazione dei malware stessi.

Gli algoritmi di clustering comunemente utilizzati non sono stati tuttavia pensati per essere robusti rispetto a dei tentativi di attacco che siano finalizzati a sovvertire il risultato del clustering. Resta pertanto da stabilire se tali algoritmi possano essere utilizzati in maniera sicura in contesti non privi di potenziali avversari.

Recentemente abbiamo proposto un framework che consente di identificare potenziali attacchi contro gli algoritmi di clustering e di valutarne l'impatto, a partire da delle specifiche assunzioni sugli obiettivi dell'avversario, sulla conoscenza del sistema da attaccare da parte dell'avversario, e sulle capacità di quest'ultimo di manipolare i dati di input. Il lavoro mostra che un potenziale avversario può significativamente compromettere l'intero processo di clustering (poisoning), aggiungendo una frazione di campioni comunque piccola rispetto alla dimensione del dataset di partenza. Lo studio, mostra anche che i campioni di attacco possono essere offuscati così da venir inclusi all'interno di cluster già esistenti e passare così inosservati. Lo studio è stato finora focalizzato sugli algoritmi di single- e complete-linkage hierarchical clustering. Tuttavia, sono attualmente allo studio tecniche di poisoning e offuscamento contro altri algoritmi di clustering presenti in letteratura. Abbiamo anche recentemente dimostrato che attacchi di tipo contaminativo (poisoning) possono significativamente degradare le prestazioni di tool realmente utilizzati nella pratica per il clustering di malware basato su caratteristiche comportamentali.

Il semplice esempio di seguito, mostra il principio di funzionamento degli attacchi di poisoning.

    

Il plot a sinistra mostra un set iniziale di quattro cluster, ottenuti a partire da un dataset bidimensionale di 80 campioni. Il plot a destra mostra invece il clustering ottenuto a seguito dell'aggiunta di 20 campioni di attacco (evidenziati dai cerchi in rosso). L'esempio mostra dunque uno scenario in cui l'attaccante è in grado di controllare fino al 20% dei dati. E' facile notare sia che il numero di cluster ottenuti è aumentato significativamente, sia che il partizionamento generato dall'algoritmo è completamente differente rispetto a quello iniziale. E' dunque possibile, attraverso l'aggiunta di punti individuati in accordo ad una precisa strategia di attacco, sovvertire il risultato del clustering. La seguente animazione mostra infine il variare del partizionamento generato dall'algoritmo all'aumentare del numero di punti di attacco inseriti.