Riepilogo Tecnico: L'ago nel pagliaio: Trovare percorsi piantati in alberi di processi rumorosi

1. Definizione del Problema

Il documento affronta il problema del "percorso piantato" (planted path), una sfida matematica definita come il recupero di una sequenza piccola e significativa (un percorso) incorporata all'interno di un grande grafo diretto aciclico (DAG) etichettato e rumoroso. Sebbene il problema abbia analoghi teorici nella letteratura del "planted clique" e del "planted structure", questo lavoro si concentra su applicazioni pratiche nella sicurezza informatica, specificamente nei process tree (alberi di processi).

In questo contesto, l'obiettivo è identificare la sequenza di processi eseguiti da un attaccante (il "percorso piantato") sepolta nei massicci e rumorosi log dei computer compromessi. La sfida risiede nel fatto che:

• Il volume totale di dati di log è enorme.
• Le euristiche naive producono troppe linee "sospette" per l'ispezione umana.
• La vera sequenza malevola è spesso una piccola frazione dell'albero totale ed è oscurata dal rumore (eventi mancanti, falsi positivi e processi di background irrilevanti).
• L'evento completo potrebbe non esistere strettamente come un singolo percorso contiguo nei dati osservati.

Gli autori sostengono che, sebbene l'astrazione del percorso piantato sia imperfetta per i dati reali, l'estrazione di percorsi parziali serve come uno step critico di "aggregazione del segnale" per aumentare il segnale delle sequenze dannose e filtrare il rumore.

2. Metodologia

2.1 Algoritmo di Fuzzy Matching (Algoritmo 1)

Il contributo principale è un algoritmo di programmazione dinamica progettato per calcolare un punteggio di somiglianza basato su feature tra due alberi, $G$ e $H$.

• Input: Due alberi diretti con nodi etichettati da feature appartenenti a un insieme $S$, e una funzione di peso $w$ che quantifica la somiglianza tra due feature.
• Meccanismo: L'algoritmo utilizza un approccio di tabulazione bottom-up (evitando la ricorsione) per trovare il matching ottimale dei nodi $(u_1, v_1), \dots, (u_k, v_k)$ tale che la sequenza rispetti l'ordinamento genitore-figlio in entrambi gli alberi ($u_i <_G u_{i+1}$ e $v_i <_H v_{i+1}$).
• Scoring: Il punteggio di un matching è la somma dei pesi $w(\phi_G(u_i), \phi_H(v_i))$. L'algoritmo massimizza questo punteggio per trovare il miglior allineamento "fuzzy".
• Complessità: La complessità temporale è polinomiala, $O(nm)$, dove $n$ e $m$ sono il numero di nodi nei rispettivi alberi.
• Output: L'algoritmo restituisce la sequenza dei nodi accoppiati e il punteggio massimo. Può essere configurato per restituire il singolo miglior percorso o adattato per i "top-K" percorsi.

2.1 Workflow

Gli autori propongono di utilizzare l'Algoritmo 1 come blocco costruttivo per workflow di machine learning più ampi:

• Clustering Non Supervisionato (Algoritmo 2):

  • Obiettivo: Identificare template sconosciuti all'interno di una collezione di grandi grafi.
  • Processo:
    1. Calcolare i punteggi di somiglianza a coppie tra tutti gli alberi in un dataset utilizzando l'Algoritmo 1.
    2. Convertire la matrice di somiglianza in una matrice di distanza utilizzando una specifica normalizzazione (Eq. 5).
    3. Embeddare gli alberi in uno spazio a bassa dimensionalità (usando UMAP).
    4. Clusterizzare gli embedding (usando HDBSCAN).
    5. Applicare un approccio di Allineamento di Sequenze Multiple (MSA) ai migliori percorsi accoppiati all'interno dei cluster per estrarre "exemplar" rappresentativi.

• Augmentation delle Feature per Classificatori (Sezione 3.2):

  • Obiettivo: Migliorare la classificazione degli alberi (es. benigno vs malevolo).
  • Processo: Utilizzare un set di template noti (es. sequenze di attacco note) per generare feature ausiliarie per ogni albero osservato. La feature $X_{i,j}$ rappresenta la lunghezza del percorso comune più lungo (o il punteggio) tra l'albero $G_i$ e il template $T_j$. Queste feature vengono poi fornite a classificatori standard (es. Random Forest).

2.3 Generazione di Dati Sintetici

Per validare l'approccio, gli autori introducono un processo di generazione dati (Algoritmi 3 e 4) analogo al Modello a Blocchi Stocastici (SBM) ma adattato per gli alberi:

• Generazione dell'Albero: Utilizza un processo di Galton-Watson per generare alberi "folti" (bushy).
• Percorso Piantato: Una specifica sequenza di etichette viene piantata in un percorso casuale all'interno dell'albero.
• Modello di Rumore: Le etichette nel percorso piantato sono soggette a una probabilità di osservazione $p$ (sottocampionamento) e a una probabilità di errore (ricampionamento). Altri nodi sono etichettati uniformemente da un alfabeto.
• Obiettivo di Design: Il modello assicura che gli algoritmi banali (come il conteggio delle frequenze delle etichette) falliscano, poiché la distribuzione delle etichette è indipendente dalla classe del percorso piantato, costringendo l'algoritmo a fare affidamento sulle informazioni strutturali del percorso.

3. Risultati Chiave

3.1 Esperimenti Sintetici

• Distinguibilità: Il punteggio di somiglianza derivato dall'Algoritmo 1 ha distinto con successo tra alberi contenenti un percorso piantato e quelli senza, anche quando il percorso era una piccola frazione di un grande albero ed era osservato a un tasso basso ($p=0.75$).
• Clustering: In contesti non supervisionati con 4 classi, il workflow di embedding (Algoritmo 2) ha separato con successo i cluster della ground-truth.
• Impatto della Pesatura: Gli esperimenti hanno mostato che l'uso di una funzione di punteggio pesata per probabilità (riducendo il peso dei simboli rari) ha migliorato significativamente la separazione dei cluster rispetto a un punteggio binario non pesato, specialmente quando l'alfabeto conteneva simboli rari.

3.2 Applicazione nel Mondo Reale (Dataset ACME4)

Gli autori hanno applicato i loro metodi al dataset ACME4, un dataset di cybersecurity che simula una rete aziendale Windows con vari attacchi.

• Scala dei Dati: Il dataset conteneva oltre 1,1 milioni di process tree (prevalentemente di dimensione 2) e quasi 3 milioni di nodi. Solo 8 alberi contenevano utenti "bad" (malevoli).
• Costruzione di Sub-tree: Per superare la prevalenza di piccoli alberi, gli autori hanno costruito 2.693 sub-tree (dimensione 3–9.558) partendo da alberi di processi più grandi.
• Risultati di Matching:
  • Utilizzando un albero di riferimento contenente un utente "bad", l'algoritmo ha identificato con successo percorsi corrispondenti in altri alberi.
  • Flessibilità dello Scoring: Gli autori hanno dimostrato che diverse funzioni di punteggio (match esatto sui nomi dei processi vs soft matching su nomi dei processi e nomi utente) hanno prodotto risultati diversi ma significativi. Ad esempio, un match "soft" poteva identificare un percorso in cui la sequenza di processi era identica ma il nome utente era leggermente diverso (es. "user88" vs "bad3").
• Performance del Workflow:
  • Filtraggio: Usato come filtro per selezionare alberi che condividono percorsi con template noti, il metodo ha isolato con successo un sottoinsieme di alberi con punteggi più alti, che correla con dimensioni dell'albero maggiori e specifiche sequenze di processi (es. winlogon.exe $\to$ cmd.exe).
  • Classificazione: Un classificatore Random Forest addestrato su feature derivate dal matching di percorsi (lunghezza dei percorsi comuni contro 38 template) ha raggiunto un'alta accuratezza nel classificare gli alberi in base ai nomi dei processi radice, con solo lievi confusioni tra bash.exe e cmd.exe.

4. Significato e Rivendicazioni

Il paper si posiziona come un lavoro esplorativo che dimostra che l'estrazione di percorsi è sia fattibile che utile per dati reali di cybersecurity.

• Utilità Pratica: Gli autori sostengono che, sebbene il problema del "percorso piantato" sia un'astrazione, l'algoritmo proposto aggrega efficacemente i segnali da eventi correlati, filtrando la stragrande maggioranza del rumore che sovraccaricherebbe gli esperti umani.
• Ambito Modesto: Gli autori dichiarano esplicitamente che questo è uno studio preliminare. Riconoscono che il lavoro attuale non fornisce soluzioni statisticamente ottimali per versioni specifiche e pulite del problema, ma si concentra invece sullo sviluppo di modelli realistici per dati "sporchi".
• Lavoro Futuro: Il paper nota che una versione futura fornirà maggiori dettagli su workflow di machine learning realistici, confronti con altri algoritmi su dataset reali e un'analisi teorica di base.
• Limitazioni: Gli autori ammettono che nei dati reali, l'evento completo potrebbe non essere strettamente contenuto in un singolo percorso, e che la rumorosità delle osservazioni potrebbe impedire l'osservazione di un intero percorso piantato. Tuttavia, sostengono che anche un filtraggio imperfetto aumenta il segnale delle sequenze malevole.

In sintesi, il paper introduce un algoritmo di fuzzy matching come strumento fondamentale per recuperare sequenze significative da alberi di processi rumorosi, validandone l'efficacia attraverso modelli sintetici e dimostrando il suo potenziale come generatore di feature e filtro nel triage della cybersecurity nel mondo reale.