Cardinality is Not Enough: Super Host Detection via Segmented Cardinality Estimation

Il paper propone SegSketch, un approccio di stima della cardinalità segmentata che utilizza una strategia di hashing ridotta per inferire i prefissi IP comuni e migliorare l'accuratezza nel rilevamento dei super host malintenzionati riducendo i falsi positivi e il consumo di memoria rispetto alle soluzioni esistenti.

L'essenziale

🕵️‍♂️ Il Problema: Trovare l'Imbroglione nella Folla

Immagina di essere un guardiano di un enorme stadio (Internet). Il tuo compito è trovare i "super-host": persone sospette che stanno cercando di distruggere lo stadio o rubare cose. Questi criminali si comportano in modo strano: invece di parlare con una sola persona, parlano con migliaia di persone diverse in pochi secondi.

Fino a oggi, i sistemi di sicurezza usavano un metodo semplice: "Conta quanti amici hai".
Se un ospite parla con più di 10.000 persone, il sistema suona l'allarme: "Attenzione! È un criminale!".

Ma c'è un grosso problema:
Immagina due persone nello stadio:

1. Il Criminale (Super-host): È un hacker che sta cercando di colpire un intero quartiere. Parla con 10.000 persone, ma tutte vivono nello stesso quartiere (stesso sottorete). È un attacco mirato e pericoloso.
2. Il Benigno (Server Web): È un sito di notizie molto popolare. Parla con 10.000 persone, ma queste vengono da tutto il mondo, da città e paesi diversi. È normale per lui.

Il vecchio sistema vedeva entrambi e gridava: "Entrambi hanno 10.000 amici! Sono entrambi criminali!".
Risultato? Falsi allarmi. Il sistema si bloccava cercando di arrestare il sito di notizie, mentre il vero hacker del quartiere scappava indisturbato perché il sistema non capiva la differenza tra "amici sparsi ovunque" e "amici tutti vicini".

💡 La Soluzione: SegSketch (Il Detective Intelligente)

Gli autori di questo paper hanno creato un nuovo sistema chiamato SegSketch. Invece di contare solo il numero totale di amici, SegSketch chiede: "Da dove vengono questi amici?".

Ecco come funziona, usando una metafora:

1. Il Trucco della "Mappa a Fette" (Hashing a Segmenti)

Immagina che ogni indirizzo IP (l'indirizzo di casa di ogni persona) sia una torta lunga 32 centimetri.
I vecchi sistemi guardavano la torta intera. SegSketch invece la taglia in fette (segmenti) e guarda solo le prime fette.

• Se il criminale parla con 10.000 persone, SegSketch nota che le prime fette della torta (il prefisso dell'indirizzo) sono identiche per tutti. Significa che tutti vivono nello stesso quartiere.
• Se il benigno parla con 10.000 persone, SegSketch nota che le prime fette sono diverse per tutti. Significa che vengono da quartieri diversi.

2. La "Biblioteca Magica" (Struttura dei Dati)

SegSketch usa una memoria molto piccola (come un quaderno tascabile) invece di un archivio gigante.

• Usa un metodo intelligente chiamato "Hashing a metà" (Halved-segment hashing). È come se, invece di cercare un libro in una biblioteca enorme, usassi un trucco per capire subito in quale scaffale (quartiere) si trova il libro, senza dover scorrere tutti i libri.
• Questo permette di capire rapidamente: "Ah, questi 10.000 contatti appartengono tutti allo stesso blocco di indirizzi!".

3. Il Vero Test: "Quanti vicini?"

Una volta capito che gli amici sono tutti dello stesso quartiere, SegSketch conta quanti vicini unici ci sono in quel quartiere.

• Se un host parla con 10.000 persone dello stesso quartiere, è un attacco grave (come un'epidemia che colpisce un solo condominio). ALLARME ROSSO!
• Se un host parla con 10.000 persone di tutti i quartieri, è probabilmente un sito legittimo. Tutto ok.

🏆 Perché è Geniale?

1. Risparmia Spazio: I vecchi metodi per fare questo controllo avevano bisogno di archivi enormi (come una biblioteca intera per ogni possibile quartiere). SegSketch usa un quaderno tascabile. È così leggero che può essere installato direttamente sui router di internet (gli "switch" programmabili) senza rallentarli.
2. Non sbaglia più: Riduce drasticamente i falsi allarmi. Non arresta più il sito di notizie innocente, ma cattura l'hacker che sta bombardando un singolo quartiere.
3. È Veloce: Grazie al suo trucco matematico, analizza milioni di pacchetti al secondo senza sudare.

📊 I Risultati nella Vita Reale

Gli autori hanno provato SegSketch su dati reali di internet. I risultati sono stati impressionanti:

• Ha individuato i criminali 8 volte meglio delle tecnologie attuali (misurando il punteggio F1, che combina precisione e completezza).
• Ha usato molta meno memoria (solo l'1,77% della memoria disponibile su un router), lasciando spazio per altre cose importanti.
• È stato testato su un router vero (un switch Tofino) e ha funzionato perfettamente, dimostrando che non è solo teoria, ma qualcosa che può proteggere Internet domani.

In Sintesi

SegSketch è come un detective che non si fida solo del numero di persone che incontri, ma guarda dove vivono. Se incontri 10.000 persone tutte nella stessa strada, c'è qualcosa di sospetto. Se le incontri in tutto il mondo, probabilmente sei solo un socializzatore. Questo piccolo cambio di prospettiva salva la sicurezza di Internet, risparmiando memoria e tempo.

Sommario tecnico

1. Il Problema

La rilevazione accurata degli Super Host (host che stabiliscono connessioni con un numero elevato di peer distinti, come super spreader o super receiver) è fondamentale per mitigare attacchi web (es. scansioni IP, DDoS, distribuzione di spam) e garantire la qualità del servizio.

Le soluzioni esistenti basate su sketch (strutture dati probabilistiche) stimano la cardinalità del flusso (numero di indirizzi IP di destinazione unici) utilizzando l'indirizzo IP completo. Tuttavia, questo approccio presenta due limiti critici:

1. Falsi Positivi Elevati: Molti host benigni (es. server DNS o web server) hanno un'alta cardinalità di flusso perché si connettono a molti peer legittimi in tutta la rete. Gli attuali metodi non riescono a distinguere questi host benigni dagli attaccanti reali.
2. Inefficienza delle Soluzioni Gerarchiche: Approcci che tentano di considerare la struttura gerarchica degli indirizzi IP (sottoreti) per migliorare la precisione richiedono strutture dati a più livelli. Questo comporta un consumo di memoria proibitivo, rendendoli impraticabili per dispositivi di rete con risorse limitate (es. switch programmabili).

L'osservazione chiave del paper è che gli attacchi provenienti da super host (o verso di essi) tendono a coinvolgere indirizzi IP che condividono lo stesso prefisso di rete (sottorete), mentre gli host benigni spesso si connettono a peer distribuiti su diverse sottoreti.

2. Metodologia: SegSketch

Gli autori propongono SegSketch, un nuovo schema di stima della cardinalità segmentata progettato per funzionare con vincoli di memoria rigorosi.

Struttura Dati

SegSketch utilizza una struttura compatta composta da $r$ righe e $c$ bucket. Ogni bucket contiene:

• Host Key: L'indirizzo IP dell'host candidato.
• Subnet Bitmap: Una mappa di bit utilizzata per inferire la lunghezza del prefisso comune (sottorete).
• Host Bitmap: Una mappa di bit utilizzata per stimare la cardinalità degli host all'interno della sottorete identificata.

Strategia Chiave: Hashing a Segmenti Divisi (Halved-Segment Hashing)

Il cuore dell'innovazione è una strategia leggera per inferire la lunghezza del prefisso IP senza conoscere a priori la lunghezza della sottorete:

1. Segmentazione: L'indirizzo IP (32 bit) viene diviso in segmenti di lunghezza fissa $G$ (es. 8 bit).
2. Hashing Binario: Per ogni segmento, viene applicata una funzione di hash a 2 valori (0 o 1).
3. Selezione Ricorsiva: In base al risultato dell'hash, viene selezionata solo una metà della subnet bitmap corrente.
   • Se tutti i pacchetti di un host hanno lo stesso risultato di hash per un segmento, la ricerca si restringe a quella metà (indicando che il prefisso è comune fino a quel punto).
   • Se i risultati differiscono, entrambe le metà vengono marcate, indicando che il prefisso comune termina prima di quel segmento.
4. Stima della Lunghezza: Questo processo ricorsivo (simile a una ricerca binaria) permette di determinare un intervallo per la lunghezza del prefisso comune (es. tra 16 e 24 bit) con un overhead di memoria minimo.

Stima della Cardinalità della Sottorete

Una volta stimata la lunghezza del prefisso:

• L'indirizzo IP viene diviso in Indirizzo di Sottorete (prefisso) e Indirizzo Host (resto).
• Viene utilizzata la tecnica Linear Counting sull'Host Bitmap per stimare il numero di indirizzi host unici all'interno di quella specifica sottorete.
• Un host viene classificato come "Super Host" se la sua cardinalità stimata all'interno della sottorete supera una soglia dinamica $T(p)$, che dipende dalla dimensione della sottorete stessa.

3. Contributi Chiave

1. SegSketch: Un nuovo sketch che integra la stima della cardinalità con l'identificazione del prefisso IP comune, offrendo un ottimo compromesso tra overhead di memoria e accuratezza.
2. Analisi Teorica: Gli autori hanno sviluppato un modello matematico per analizzare il limite di errore della stima. Hanno dimostrato teoricamente che l'hashing basato sull'indirizzo host (dopo la segmentazione) produce un errore di stima inferiore rispetto all'hashing dell'indirizzo IP completo.
3. Implementazione Hardware: SegSketch è stato implementato su uno switch programmabile (Tofino) utilizzando il linguaggio P4, dimostrando un utilizzo estremamente efficiente delle risorse hardware (solo il 1.77% della SRAM).

4. Risultati Sperimentali

Le valutazioni sono state condotte su dataset reali (UNSW-NB15, MAWI, CAIDA) confrontando SegSketch con lo stato dell'arte (SpreadSketch, Couper, RHHH).

• Accuratezza: SegSketch supera significativamente le soluzioni esistenti. In scenari con memoria limitata (32 KB), ha migliorato il F1-Score fino a 8.04 volte rispetto alle soluzioni più avanzate.
• Riduzione dei Falsi Positivi: Grazie alla considerazione della cardinalità della sottorete, il sistema distingue efficacemente gli attaccanti (che colpiscono una singola sottorete) dagli host benigni (che si connettono a molte sottoreti diverse).
• Efficienza di Memoria: A differenza degli approcci gerarchici che richiedono memoria esponenziale per coprire tutte le lunghezze di prefisso, SegSketch mantiene un footprint di memoria costante e molto basso.
• Throughput: Il sistema raggiunge un throughput di 28 Mpps (milioni di pacchetti al secondo) anche con 32 KB di memoria, superando le prestazioni di elaborazione degli altri metodi.
• Deploy su P4: L'implementazione su switch Tofino ha mostrato che SegSketch utilizza meno risorse (SRAM, unità di hashing, istruzioni VLIW) rispetto a SpreadSketch, Couper e RHHH, rendendolo ideale per la rilevazione in tempo reale ad alta velocità.

5. Significato e Impatto

Questo lavoro dimostra che la semplice stima della cardinalità degli indirizzi IP completi non è sufficiente per la rilevazione accurata delle minacce moderne. Introducendo il concetto di cardinalità segmentata (basata sulla sottorete), il paper risolve il dilemma tra accuratezza e consumo di memoria.

L'importanza di SegSketch risiede nella sua capacità di essere implementato direttamente nell'hardware di rete (data plane degli switch), permettendo la rilevazione di attacchi di tipo "super host" in tempo reale, anche in ambienti con risorse di memoria estremamente vincolate, un requisito critico per le infrastrutture di rete ad alta velocità del futuro.