🤖 AI

Practical Graph Optimisation and AI-Driven Models for Active Directory Security Hardening

Questo articolo propone una serie di modelli basati sulla teoria dei giochi e sull'ottimizzazione per affrontare la natura dinamica, i meccanismi di difesa attiva limitati e i vincoli di implementazione pratica dell'irrigidimento della sicurezza di Active Directory, introducendo strategie per il posizionamento degli honeypot, l'impiego dinamico di esche e la prioritizzazione adattiva della rimedio con l'intervento dell'amministratore.

Autori originali: Huy Q. Ngo

Pubblicato 2026-07-27

📖 8 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Huy Q. Ngo

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immaginate il mondo digitale di una grande azienda come un enorme castello invisibile. All'interno di questo castello ci sono migliaia di stanze, passaggi segreti e torri di guardia. Il tesoro più importante — i gioielli della corona dei dati dell'azienda — è custodito nella cassaforte "Tier 0", sorvegliata dagli Amministratori di Dominio. Per mantenere il castello al sicuro, i team di sicurezza costruiscono una mappa di ogni possibile percorso che un intruso potrebbe intraprendere per raggiungere la cassaforte. Questa mappa è chiamata "grafo di attacco". In un mondo perfetto, il castello è progettato in modo che nessuno possa infiltrarsi dal cancello principale (il computer di un dipendente di basso livello) fino alla cassaforte senza passare attraverso una serie di porte chiuse a chiave. Ma in realtà, il castello è disordinato. I dipendenti dimenticano di chiudere le porte, gli amministratori accidentalmente lasciano le chiavi sui tavoli sbagliati e nuovi passaggi segreti si aprono ogni volta che qualcuno accede a un computer. Questo disordine è chiamato "drift di insicurezza" (insecure drift).

Il documento che state per leggere affronta un problema molto complicato: come proteggere un castello che cambia costantemente forma, dove le mura si muovono e nuove porte appaiono ogni ora? Gli strumenti di sicurezza tradizionali sono come una lista statica di "porte cattive" da sistemare. Ti dicono: "Sistema questa porta, poi quella". Ma in un castello dinamico, sistemare una porta potrebbe semplicemente aprire una finestra cinque minuti dopo. I ricercatori in questo studio hanno capito che, invece di limitarsi a riparare le porte rotte, bisogna essere più intelligenti. Bisogna allestire delle trappole (honeypot) che sembrino tesori veri ma che siano in realtà falsi, e bisogna capire esattamente dove posizionarle in modo che, anche se il castello cambia, l'intruso venga catturato presto. Volevano anche sapere come chiedere ai manager umani del castello: "Dovremmo chiudere questa porta?" in un modo che non sprechi tempo chiedendo di ogni singola porta, ma che trovi comunque il modo migliore per fermare il ladro.

La Missione del Documento: Catturare il Ladro in un Castello in Movimento

Questa ricerca, intitolata "Practical Graph Optimisation and AI-Driven Models for Active Directory Security Hardening", scava profondamente nella complicata realtà della protezione delle reti Microsoft Active Directory (AD). Gli autori, guidati da Quang Huy Ngo, sostengono che il vecchio modo di pensare alla sicurezza sia rotto perché tratta la rete come un'istantanea congelata. Nel mondo reale, la rete è un organismo vivente che cambia ogni secondo mentre le persone effettuano l'accesso, escono o si spostano.

Il documento propone quattro modi principali per superare in astuzia gli attaccanti in questo ambiente a bersaglio mobile, utilizzando un mix di matematica, teoria dei giochi e intelligenza artificiale.

1. Il problema del "Dove Nascondere il Tesoro Falso" (Posizionamento degli Honeypot)
Immaginate di essere la guardia del castello. Avete un numero limitato di bauli di tesori falsi (honeypot) da posizionare. Se un ladro tocca uno di essi, scatta un allarme. Il problema è: dove li metti?
Gli autori hanno scoperto che se guardi solo la mappa del castello in un momento specifico, potresti posizionare le tue trappole perfettamente per quel secondo. Ma se il castello si sposta un'ora dopo, le tue trappole potrebbero essere inutili. Hanno dimostrato matematicamente che trovare il punto perfetto per queste trappole è incredibilmente difficile (così difficile da essere definito "NP-hard" e "W[1]-hard").
Per risolvere questo problema, hanno sviluppato un nuovo metodo che guarda a molte diverse versioni della mappa del castello contemporaneamente. Hanno utilizzato una tecnica chiamata "clustering" per trovare le versioni più "rappresentative" del castolo e hanno posizionato le trappole lì. I loro esperimenti hanno dimostrato che questo metodo funziona su reti massicce con oltre 137.000 nodi (stanze) e quasi 1,5 milioni di connessioni (porte). Hanno scoperto che la loro nuova strategia può fermare gli attaccanti molto meglio dei vecchi metodi, anche quando la rete è in costante mutamento.

2. Comprare Tempo: La Metrica del "Tempo di Risposta"
I ricercatori si sono resi conto che catturare un ladro non significa solo fermarlo; si tratta di quanto tempo si ha per reagire dopo averlo visto. Hanno inventato un nuovo modo per misurare il successo chiamato "Tempo di Risposta". Questo è il tempo che intercorre tra il momento in cui un ladro calpesta una trappola falsa e il momento in cui ruba effettivamente i gioielli della corona.
Hanno modellato l'attaccante come un giocatore intelligente e paziente che aspetta il momento perfetto per muoversi. L'obiettivo per il difensore è posizionare le trappole in modo che, anche se il ladro riesce a passare, impieghi il maggior tempo possibile per raggiungere la cassaforte.
Hanno scoperto che gli algoritmi standard sono troppo lenti per calcolare questo su mappe grandi e in movimento. Così, hanno costruito un algoritmo più veloce e intelligente (usando un metodo chiamato Evolutionary Diversity Optimization) che può calcolare i migliori posizionamenti delle trappole rapidamente. Nei loro test, il loro nuovo metodo è stato circa 5 volte più veloce degli strumenti esistenti nel calcolare i percorsi e ha trovato soluzioni 108 volte più velocemente rispetto ai vecchi metodi in alcuni casi. Hanno anche dimostrato che il loro metodo può gestire reti con milioni di connessioni senza mandare in crash il computer.

3. Il "Mago Adattivo": Fare le Domande Giuste
A volte, non puoi semplicemente eliminare una connessione (come un permesso) perché è necessaria per il lavoro dell'azienda. Devi chiedere a un manager umano: "È ok chiudere questa porta?". Ma chiedere di ogni singola porta richiederebbe troppo tempo.
Gli autori hanno creato un "Wizard" (una guida software intelligente) che pone al manager domande in un ordine specifico. Invece di chiedere "Dovremmo chiudere la Porta A?" poi "Porta B?", lo Wizard osserva un intero percorso che il ladro potrebbe seguire e chiede: "Quale di queste tre porte su questo percorso dovremmo chiudere?".
Hanno dimostrato che trovare il modo perfetto per porre queste domande è anche matematicamente impossibile da risolvere perfettamente in un tempo ragionevole. Tuttavia, hanno costruito un algoritmo di "Programmazione Dinamica" che si avvicina molto alla risposta perfetta. Le loro simulazioni hanno mostrato che questo "Wizard" può trovare il set ottimale di porte da chiudere interrogando il manager umano molto meno spesso rispetto al caso casuale o alle semplici liste.

4. Il "Robot che Impara da Solo" (Reinforcement Learning)
Infine, il team ha cercato di insegnare a un computer come imparare a porre le domande giuste da solo usando una tecnica chiamata Reinforcement Learning (RL). Hanno creato un agente IA che gioca il gioco del "Security Hardening" ripetutamente.
All'inizio, l'IA è scarsa in questo compito. Ma gli hanno dato un trucco speciale di "auto-miglioramento": ogni volta che commette un errore, impara da esso e migliora. Gli hanno anche dato un "sistema di ricompensa" che lo incoraggia a trovare il percorso più breve verso una soluzione.
Nei loro test, questo agente IA ha imparato a porre meno domande rispetto a qualsiasi altro metodo provato. È stato in grado di generalizzare il suo apprendimento, il che significa che poteva applicare ciò che ha imparato su un tipo di rete a un tipo completamente diverso. I risultati hanno mostrato che questo approccio basato sull'IA ha superato significativamente gli altri metodi, riducendo il numero di domande necessarie per mettere in sicurezza la rete.

Cosa il Documento Esclude
Gli autori sono molto chiari su ciò che non funziona. Mostrano esplicitamente che trattare la rete come un'immagine statica e immutabile è una cattiva idea. Se pianifichi la tua difesa basandoti su una mappa di stamattina, probabilmente fallirai entro il pomeriggio perché la rete sarà cambiata. Escludono anche l'idea che tu possa semplicemente elencare le "peggiori" vulnerabilità e sistemarle una alla volta; mostrano che è necessario guardare l'insieme e come i percorsi si collegano.

Quanto sono Sicuri?
Gli autori sono molto fiduciosi nelle loro prove matematiche che questi problemi siano difficili da risolvere. Tuttavia, le loro soluzioni si basano su simulazioni ed esperimenti su reti sintetiche (false ma realistiche) e su alcuni dati reali provenienti da organizzazioni anonime. Non hanno testato questo su una rete aziendale reale e attiva dove un errore potrebbe causare una vera violazione. Quindi, sebbene la matematica sia solida e le simulazioni promettenti, l'efficacia nel mondo reale è suggerita da questi test piuttosto che provata in una battaglia reale. Dimostrano che i loro metodi possono funzionare e sono molto più veloci ed efficaci rispetto agli strumenti attuali, ma presentano questo come un forte consiglio basato su test rigorosi, non come una soluzione garantita per ogni situazione.

In breve, questo documento suggerisce che per proteggere un moderno e disordinato castello digitale, devi smettere di guardare mappe statiche e iniziare a usare strategie intelligenti e adattive che possano gestire il cambiamento, porre le domande giuste e comprarti tempo prezioso per reagire.

Sintesi Tecnica: Ottimizzazione Pratica dei Grafi e Modelli Guidati dall'IA per l'Hardening della Sicurezza di Active Directory

1. Definizione del Problema

Microsoft Active Directory (AD) funge da sistema centrale per la gestione delle identità e degli accessi per circa il 90% delle aziende Fortune 500. Nonostante la sua ubiquità, gli ambienti AD sono frequentemente compromessi, con i penetration tester che ottengono il controllo totale in fino all'82% delle reti analizzate. La vulnerabilità primaria deriva dallo "drift insicuro" (insecure drift), dove le operazioni quotidiane (ad esempio, amministratori privilegiati che effettuano l'accesso su workstation a basso privilegio) creano percorsi di attacco cross-tier che violano il "Principio della Fonte Pulita" (Clean Source Principle).

I difensori si affidano tradizionalmente a grafi di attacco (ad esempio, generati da BloodHound) per visualizzare questi percorsi. Tuttavia, gli approcci di hardening esistenti affrontano tre criticità fondamentali:

Assunzioni Statiche: La maggior parte dei modelli tratta il grafo AD come statico, ignorando gli archi dinamici (ad esempio, archi HasSession) che appaiono e scompaiono in base all'attività dell'utente, portando a difese subottimali negli scenari reali.
Meccanismi di Difesa Limitati: La ricerca attuale si concentra quasi esclusivamente sulla rimozione degli archi (revoca dei permessi). Manca di modelli per la difesa attiva, come il posizionamento strategico di honeypot o esche (decoys), che possono intercettare gli attaccanti senza interrompere le operazioni.
Mancanza di Scalabilità Human-in-the-Loop: L'hardening pratico richiede l'approvazione di un amministratore IT. I modelli esistenti o assumono che la rimovibilità di tutti gli archi sia nota in anticipo (impraticabile) o interrogano gli archi uno alla volta (non scalabile). È necessario un modello adattivo che apprenda i pattern decisionali dell'amministratore per minimizzare lo sforzo di interrogazione garantendo al contempo la disconnessione dei percorsi di attacco.

Questa tesi affronta tali lacune sviluppando modelli basati sulla teoria dei giochi e sull'ottimizzazione specificamente per i grafi di attacco tipo AD, dimostrando l'intrattabilità computazionale di questi problemi e proponendo algoritmi scalabili che spaziano dalla Programmazione Lineare Intera Mista (MIP) all'Apprendimento per Rinforzo (RL).

2. Metodologia e Contributi

La tesi è strutturata attorno a quattro contributi primari, ognuno dei quali affronta obiettivi di ricerca specifici riguardanti la difesa attiva, la dinamica temporale e l'interazione umana adattiva.

Contributo 1: Posizionamento di Honeypot in Grafi Statici e Dinamici (Capitolo 3)

Problema: Come posizionare in modo ottimale un budget limitato di honeypot sui nodi AD per intercettare gli attaccanti, considerando sia attaccanti "semplici" (che non possono rilevare le honeypot) sia attaccanti "competenti" (che possono osservare ed evitarle).
Metodologia:

Formulazione Teoria dei Giochi: Il problema è modellato come un gioco di Stackelberg. Il difensore minimizza la probabilità di successo dell'attaccante contro un mix di attaccanti semplici e competenti.
Complessità: Il problema è dimostrato essere NP-hard contro gli attaccanti semplici e W[1]-hard contro quelli competenti.
Soluzione Statica: Viene sviluppata una formulazione MIP. Sfruttando la struttura ad albero dei grafi AD, il solver raggiunge un'elevata efficienza anche su grafi di grandi dimensioni (fino a ~137k nodi).
Soluzione Dinamica: Riconoscendo che i grafi AD evolvono tramite archi HasSession, la tesi propone dyMIP(m), che ottimizza su $m$ $m$ snapshot del grafo. Per gestire la scalabilità, vengono introdotti due euristiche:
- Basata sul voto (Voting-based): Esegue la MIP su batch di snapshot e seleziona i nodi che appaiono più frequentemente.
- Basata sul clustering (Clustering-based): Utilizza il clustering k-means sulle caratteristiche del grafo per selezionare snapshot rappresentativi, risolvendo la MIP solo su questo set ridotto.
  Risultati: Gli esperimenti su dati di autenticazione sintetici e reali mostrano che l'euristica basata sul clustering produce piani di blocco quasi ottimali con un costo computazionale significativamente inferiore rispetto alla risoluzione di tutti gli snapshot. L'approccio scala a grafi con milioni di archi, superando le difese puramente statiche che non riescono a tenere conto della comparsa di archi dinamici.

Contributo 2: Ottimizzazione del Tempo di Risposta Cyber su Grafi Temporali (Capitolo 4)

Problema: In un contesto temporale, gli attaccanti possono "stazionare" (lurk) in un nodo in attesa che un particolare arco diventi disponibile. L'obiettivo non è solo bloccare i percorsi, ma massimizzare il Tempo di Risposta (RT) — ovvero la durata tra il primo trigger del decoy e il raggiungimento del Domain Admin (DA).
Metodologia:

Metrica: L'RT è definito come la differenza temporale tra il primo trigger dell'honeypot e il compromesso del DA. Il difensore mira a massimizzare l'RT nel caso peggiore.
Complessità: Il problema di ottimizzazione è dimostrato essere NP-hard tramite riduzione dal problema del separatore temporale $(s, d)$ stretto.
Algoritmo: Viene impiegato un algoritmo di Ottimizzazione della Diversità Evolutiva (EDO) per trovare strategie di difesa diverse e di alta qualità.
Ottimizzazioni:
- Valutazione della Fitness più Rapida: Viene proposto un nuovo algoritmo basato su Dijkstra per calcolare il "percorso di arrivo anticipato" nei grafi temporali. Esso sfrutta il fatto che la maggior parte degli archi AD è statica, ottenendo un'accelerazione di 5x rispetto agli algoritmi di percorso temporale allo stato dell'arte (Wu et al.).
- Gestione dei Vincoli: Vengono introdotte due tecniche per gestire la difficoltà di trovare soluzioni fattibili (cut) nella ricerca evolutiva:
  1. Riparazione ILP: Utilizza la Programmazione Lineare Intera per "riparare" i discendenti (offspring) non fattibili in tagli validi.
  2. Fitness Assistita da Surrogati: Utilizza una funzione surrogata leggera che valuta solo un set di percorsi "importanti", aggiornata iterativamente con i nuovi percorsi di attacco ottimali trovati dall'attaccante.

Risultati: L'approccio assistito da surrogati (EST) converge a soluzioni fattibili circa 108 volte più velocemente del vanilla EDO e supera la riparazione basata su ILP di circa il 23% nelle metriche di tempo di risposta, evitando al contempo errori di Out-of-Memory su grafi più grandi.

Contributo 3: Adaptive Wizard per la Rimozione di Percorsi Cross-Tier (Capitolo 5)

Problema: Come interrogare in modo interattivo un amministratore IT per rimuovere gli archi e disconnettere i percorsi di attacco con il minimo numero di query, senza conoscere in anticipo quali archi siano rimovibili.
Metodologia:

Rimozione Adattiva dei Percorsi (APR): Un "wizard" presenta all'amministratore un percorso di attacco come un insieme di opzioni a scelta multipla (archi su quel percorso). L'amministratore seleziona un arco da rimuovere. Il processo si ripete finché il percorso non viene tagliato o il budget non viene esaurito.
Complessità: Trovare la politica adattiva ottimale è dimostrato essere #P-hard.
Algoritmi:
- Esatto (OPT): Un approccio di Programmazione Dinamica per grafi piccoli.
- Approssimazione (APP): Un algoritmo di approssimazione submodulare adattiva.
- Euristica Scalabile (DPR): Un'euristica di "Programmazione Dinamica con Restrizioni" che si basa sui metodi esatti ma scala su grafi più grandi.
- Approccio RL: Un'euristica di Reinforcement Learning addestrata offline per un basso tempo di inferenza.
  Risultati: L'euristica DPR fornisce i risultati più solidi, garantendo l'eliminazione di tutti i percorsi $s-t$ quando il budget è sufficiente. Supera significativamente le strategie baseline non adattive nel ridurre il numero atteso di query.

Contributo 4: Test di Connettività Adattivo Basato su Feature (F-ACT) (Capitolo 6)

Problema: Estendere il modello di query adattiva per generalizzare le decisioni dell'amministratore in base alle feature degli archi (ad esempio, proprietà dell'oggetto) anziché interrogare i singoli archi.
Metodologia:

Framework F-ACT: Invece di chiedere "Rimuovi l'arco $e$ ?", il wizard presenta un arco con il suo vettore di feature. La decisione dell'amministratore (taglia/mantieni) viene applicata a tutti gli archi che condividono quel pattern di feature.
Soluzione RL (RL4FT): Un agente di Reinforcement Learning viene addestrato per apprendere una politica di query adattiva.
- Auto-miglioramento: Un meccanismo che permette all'agente di migliorare rispetto a qualsiasi politica di riferimento fornita.
  와 Reward Shaping: Uno schema invariante rispetto alla policy per gestire le ricompense sparse.
- Prioritized Experience Replay: Un buffer di replay personalizzato per concentrarsi sulle transizioni ad alto valore.
  Risultati: RL4FT garantisce il miglioramento rispetto a qualsiasi politica di riferimento e supera significativamente le baseline allo stato dell'arte (incluso l'euristica DPR del Capitolo 5) nel minimizzare il numero atteso di query, dimostrando l'efficacia della generalizzazione basata sulle feature per l'hardening della sicurezza.

3. Risultati Chiave e Significato

La tesi dimostra che:

La Difesa Dinamica è Critica: Le strategie di posizionamento delle honeypot statiche degradano significativamente quando applicate a grafi AD dinamici. Le euristiche proposte basate su clustering e voto per i grafi dinamici raggiungono prestazioni quasi ottimali con alta scalabilità.
La Consapevolezza Temporale Migliora la Risposta: Modellando il grafo temporalmente e massimizzando il tempo di risposta, i difensori ottengono una finestra critica per la risposta agli incidenti. I processi di valutazione della fitness basati su Dijkstra e gli algoritmi EDO assistiti da surrogati rendono tutto questo computazionalmente fattibile per reti su larga scala.
L'Interazione Umana è Scalabile: I modelli di query adattiva (APR e F-ACT) riducono con successo l'onere amministrativo dell'hardening. Generalizzando le decisioni attraverso le feature degli archi (F-ACT) o attraverso la selezione adattiva dei percorsi (APR), il sistema minimizza il numero di query necessarie per mettere in sicurezza la rete garantendo la disconnessione dei percorsi.
Difficoltà Computazionale: La tesi stabilisce rigorosamente che i problemi sottostanti (posizionamento honeypot, massimizzazione del taglio temporale, interrogazione adattiva) sono computazionalmente intrattabili (NP-hard, W[1]-hard, #P-hard), giustificando la necessità dei proposti algoritmi euristici e di approssimazione.

Significato:
Questo lavoro colma il divario tra i modelli teorici di sicurezza dei grafi e l'hardening pratico di Active Directory. Va oltre le semplici euristiche di rimozione degli archi per fornire un toolkit completo che include la difesa attiva (honeypot), la consapevolezza temporale (ottimizzazione del tempo di risposta) e l'automazione centrata sull'uomo (adaptive wizards). Gli algoritmi proposti sono progettati per scalare su reti di dimensioni enterprise (centinaia di migliaia di nodi), affrontando i vincoli specifici degli ambienti AD reali dove la continuità operativa e il carico di lavoro degli amministratori sono fondamentali. La tesi conclude che, sebbene i problemi siano teoricamente difficili, gli approcci basati su IA e ottimizzazione proposti forniscono soluzioni pratiche ed efficaci per la moderna sicurezza di AD.