🤖 AI

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

Este artigo propõe uma série de modelos baseados em teoria dos jogos e otimização para abordar a natureza dinâmica, os mecanismos limitados de defesa ativa e as restrições de implementação prática do endurecimento de segurança do Active Directory, introduzindo estratégias para o posicionamento de honeypots, implantação dinâmica de iscas e remediação adaptativa com o administrador no ciclo de controle (admin-in-the-loop) de priorização.

Autores originais: Huy Q. Ngo

Publicado 2026-07-27

📖 8 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Huy Q. Ngo

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine o mundo digital de uma grande empresa como um castelo imenso e invisível. Dentro deste castelo, existem milhares de quartos, passagens secretas e torres de vigia. O tesouro mais importante — as joias da coroa dos dados da empresa — está trancado no cofre "Tier 0", guardado pelos Administradores de Domínio. Para manter o castelo seguro, as equipes de segurança constroem um mapa de todas as rotas possíveis que um intruso poderia seguir para chegar a esse cofre. Esse mapa é chamado de "grafo de ataque". Em um mundo perfeito, o castelo é projetado para que ninguém consiga esgueirar-se do portão da frente (o computador de um funcionário de baixo nível) até o cofre sem passar por uma série de portas trancadas. Mas, na realidade, o castelo é bagunçado. Funcionários esquecem de trancar portas, administradores acidentalmente deixam chaves sobre as mesas erradas e novas passagens secretas se abrem toda vez que alguém faz login em um computador. Essa bagunça é chamada de "drift inseguro" (insecure drift).

O artigo que você está prestes a ler aborda um problema muito complexo: Como proteger um castelo que muda constantemente de forma, onde as paredes se movem e novas portas aparecem a cada hora? As ferramentas de segurança tradicionais são como uma lista estática de "portas ruins" para consertar. Elas dizem: "Conserte esta porta, depois aquela". Mas em um castelo dinâmico, consertar uma porta pode apenas abrir uma janela cinco minutos depois. Os pesquisadores neste estudo perceberam que, em vez de apenas consertar portas quebradas, você precisa ser mais inteligente. Você precisa montar armadilhas (honeypots) que pareçam tesouros reais, mas que sejam falsos, e precisa descobrir exatamente onde colocá-las para que, mesmo que o castelo mude, o intruso seja pego cedo. Eles também queriam saber como perguntar aos gestores humanos do castelo: "Devemos trancar esta porta?" de uma forma que não desperdice tempo perguntando sobre cada uma das portas, mas que ainda encontre a melhor maneira de deter o ladrão.

A Missão do Artigo: Pegando o Ladrão em um Castelo Móvel

Esta pesquisa, intitulada "Practical Graph Optimisation and AI-Driven Models for Active Directory Security Hardening", mergulha fundo na realidade desordenada de proteger redes Microsoft Active Directory (AD). Os autores, liderados por Quang Huy Ngo, argumentam que a antiga forma de pensar sobre segurança está quebrada porque trata a rede como um instantâneo congelado. No mundo real, a rede é algo vivo, que respira, e que muda a cada segundo conforme as pessoas fazem login, logout e se movimentam.

O artigo propõe quatro formas principais de superar os atacantes neste ambiente de alvo móvel, usando uma mistura de matemática, teoria dos jogos e inteligência artificial.

1. O Problema de "Onde Esconder o Tesouro Falso" (Posicionamento de Honeypots)
Imagine que você é o guarda do castelo. Você tem um número limitado de baús de tesouro falsos (honeypots) para posicionar. Se um ladrão tocar em um deles, um alarme soa. O problema é: onde você os coloca?
Os autores descobriram que, se você apenas olhar para um mapa do castelo em um momento específico, poderá colocar suas armadilhas perfeitamente para aquele segundo. Mas, se o castelo mudar uma hora depois, suas armadilhas podem ser inúteis. Eles provaram matematicamente que encontrar o lugar perfeito para essas armadilhas é incrivelmente difícil (tão difícil que é chamado de "NP-hard" e "W[1]-hard").
Para resolver isso, eles desenvolveram um novo método que observa muitas versões diferentes do mapa do castelo ao mesmo tempo. Eles usaram uma técnica chamada "clustering" (agrupamento) para encontrar as versões mais "representativas" do castelo e posicionaram as armadilhas nelas. Seus experimentos mostraram que este método funciona em redes massivas com mais de 137.000 nós (quartos) e quase 1,5 milhão de conexões (portas). Eles descobriram que sua nova estratégia podia deter atacantes muito melhor do que os métodos antigos, mesmo quando a rede estava em constante mudança.

2. Comprando Tempo: A Métrica de "Tempo de Resposta"
Os pesquisadores perceberam que deter um ladrão não é apenas sobre pará-lo; é sobre quanto tempo você tem para reagir após vê-lo. Eles inventaram uma nova forma de medir o sucesso chamada "Tempo de Resposta". Este é o tempo entre o momento em que um ladrão pisa em uma armadilha falsa e o momento em que ele realmente rouba as joias da coroa.
Eles modelaram o atacante como um jogador inteligente e paciente que espera pelo momento perfeito para agir. O objetivo para o defensor é posicionar as armadilhas de modo que, mesmo que o ladrão passe, leve o maior tempo possível para ele alcançar o cofre.
Eles descobriram que algoritmos de computador padrão eram muito lentos para calcular isso em mapas grandes e móveis. Por isso, construíram um algoritmo mais rápido e inteligente (usando um método chamado Otimização de Diversidade Evolutiva) que consegue calcular os melhores posicionamentos de armadilhas rapidamente. Em seus testes, seu novo método foi cerca de 5 vezes mais rápido que as ferramentas existentes para calcular caminhos e encontrou soluções 108 vezes mais rápidas do que métodos antigos em alguns casos. Eles também mostraram que seu método pode lidar com redes de milhões de conexões sem travar o computador.

3. O "Mago Adaptável": Fazendo as Perguntas Certas
Às vezes, você não pode simplesmente deletar uma conexão (como uma permissão) porque ela é necessária para o negócio funcionar. Você tem que perguntar a um gestor humano: "Está tudo bem trancar esta porta?". Mas perguntar sobre cada uma das portas levaria uma eternidade.
Os autores criaram um "Mago" (um guia de software inteligente) que faz perguntas ao gestor em uma ordem específica. Em vez de perguntar "Devemos trancar a Porta A?", depois "a Porta B?", o Mago olha para um caminho inteiro que o ladrão pode seguir e pergunta: "Qual destas três portas neste caminho devemos trancar?".
Eles provaram que encontrar a maneira perfeita de fazer essas perguntas também é matematicamente impossível de resolver perfeitamente em um tempo razoável. No entanto, eles construíram um algoritmo de "Programação Dinâmica" que chega muito perto da resposta perfeita. Suas simulações mostraram que este "Mago" conseguia encontrar o melhor conjunto de portas para trancar enquanto fazia ao gestor humano muito menos perguntas do que o acaso ou listas simples.

4. O "Robô de Autoaperfeiçoamento" (Aprendizado por Reforço)
Finalmente, a equipe tentou ensinar um computador a aprender como fazer as perguntas certas por conta própria usando uma técnica chamada Aprendizado por Reforço (Reinforcement Learning - RL). Eles criaram um agente de IA que joga o jogo do "Fortalecimento de Segurança" repetidamente.
No início, a IA é ruim nisso. Mas eles lhe deram um truque especial de "autoaperfeiçoamento": toda vez que ela comete um erro, ela aprende com ele e melhora. Eles também lhe deram um "sistema de recompensa" que a incentiva a encontrar o caminho mais curto para uma solução.
Em seus testes, este agente de IA aprendeu a fazer menos perguntas do que qualquer outro método que tentaram. Ele foi capaz de generalizar seu aprendizado, o que significa que pôde aplicar o que aprendeu sobre um tipo de rede para um tipo completamente diferente. Os resultados mostraram que esta abordagem de IA superou significativamente os outros métodos, reduzindo o número de perguntas necessárias para proteger a rede.

O Que o Artigo Descarta
Os autores são muito claros sobre o que não funciona. Eles mostram explicitamente que tratar a rede como uma imagem estática e imutável é uma má ideia. Se você planejar sua defesa baseada em um mapa de hoje de manhã, ela provavelmente falhará até o meio da tarde porque a rede mudou. Eles também descartam a ideia de que você pode simplesmente listar as "piores" vulnerabilidades e consertá-las uma a uma; eles mostram que você precisa olhar para o quadro geral e para como os caminhos se conectam.

O Quão Certos Eles Estão?
Os autores estão muito confiantes em suas provas matemáticas de que esses problemas são difíceis de resolver. No entanto, suas soluções baseiam-se em simulações e experimentos em redes sintéticas (falsas, mas realistas) e alguns dados do mundo real de organizações anônimas. Eles não testaram isso em uma rede de uma empresa real e viva, onde um erro poderia causar uma brecha real. Portanto, embora a matemática seja sólida e as simulações sejam promissoras, a eficácia no mundo real é sugerida por esses testes, e não provada em uma batalha real. Eles mostram que seus métodos podem funcionar e são muito mais rápidos e mais eficazes do que as ferramentas atuais, mas apresentam isso como uma recomendação forte baseada em testes rigorosos, não como uma solução garantida para todas as situações.

Em resumo, este artigo sugere que, para proteger um castelo digital moderno e bagunçado, você deve parar de olhar para mapas estáticos e começar a usar estratégias inteligentes e adaptáveis que possam lidar com mudanças, fazer as perguntas certas e ganhar tempo precioso para reagir.

Resumo Técnico: Otimização de Grafos Prática e Modelos Impulsionados por IA para o Fortalecimento da Segurança do Active Directory

1. Definição do Problema

O Microsoft Active Directory (AD) serve como o núcleo do sistema de gestão de identidade e acesso para aproximadamente 90% das empresas da Fortune 500. Apesar de sua ubiquidade, os ambientes de AD são frequentemente comprometidos, com testadores de penetração alcançando o comprometimento total em até 82% das redes avaliadas. A vulnerabilidade primária advém do "drift inseguro" (desvio inseguro), onde operações do dia a dia (ex: administradores privilegiados fazendo login em estações de trabalho de baixo privilégio) criam caminhos de ataque entre camadas que violam o "Princípio da Fonte Limpa".

Os defensores tradicionalmente dependem de grafos de ataque (ex: gerados pelo BloodHound) para visualizar esses caminhos. No entanto, as abordagens de endurecimento existentes enfrentam três limitações críticas:

Suposições Estáticas: A maioria dos modelos trata o grafo do AD como estático, ignorando arestas dinâmicas (ex: arestas HasSession) que aparecem e desaparecem com base na atividade do usuário, levando a defesas subótimas em cenários do mundo real.
Mecanismos de Defesa Limitados: A pesquisa atual foca quase exclusivamente na remoção de arestas (revogação de permissões). Ela carece de modelos para defesas ativas, como o posicionamento estratégico de honeypots ou decoy (iscas), que podem interceptar atacantes sem interromper as operações.
Falta de Escalabilidade com o Humano no Ciclo (Human-in-the-Loop): O endurecimento prático requer a aprovação de um administrador de TI. Os modelos existentes ou assumem que toda a removibilidade de arestas é conhecida antecipadamente (impraticável) ou consultam arestas uma a uma (não escalável). Há uma necessidade de modelos adaptativos que aprendam padrões de decisão do administrador para minimizar o esforço de consulta, garantindo simultaneamente a desconexão dos caminhos de ataque.

Esta tese aborda essas lacunas desenvolvendo modelos de teoria dos jogos e de otimização especificamente para grafos de ataque do tipo AD, provando a intratabilidade computacional desses problemas e propondo algoritmos escaláveis que variam de Programação Inteira Mista (MIP) a Aprendizado por Reforço (RL).

2. Metodologia e Contribuições

A tese está estruturada em torno de quatro contribuições primárias, cada uma abordando objetivos de pesquisa específicos relativos à defesa ativa, dinâmica temporal e interação humana adaptativa.

Contribuição 1: Posicionamento de Honeypot em Grafos Estáticos e Dinâmicos (Capítulo 3)

Problema: Como posicionar otimamente um orçamento limitado de honeypots em nós de AD para interceptar atacantes, considerando tanto atacantes "simples" (que não conseguem detectar honeypots) quanto atacantes "competentes" (que podem observar e evitá-los).
Metodologia:

Formulação de Teoria dos Jogos: O problema é modelado como um jogo de Stackelberg. O defensor minimiza a probabilidade de sucesso do atacante contra uma mistura de atacantes simples e competentes.
Complexidade: O problema é provado como NP-difícil contra atacantes simples e W[1]-difícil contra atacantes competentes.
Solução Estática: Uma formulação de Programação Inteira Mista (MIP) é desenvolvida. Aproveitando a estrutura em árvore dos grafos de AD, o solver alcança alta eficiência mesmo em grafos grandes (até ~137k nós).
Solução Dinâmica: Reconhecendo que os grafos de AD evoluem via arestas HasSession, a tese propõe o dyMIP(m), que otimiza sobre $m$ $m$ instantâneos (snapshots) do grafo. Para lidar com a escalabilidade, duas heurísticas são introduzidas:
- Baseada em Votação: Executa o MIP em lotes de snapshots e seleciona os nós que aparecem com mais frequência.
- Baseada em Agrupamento (Clustering): Utiliza k-means clustering em características do grafo para selecionar snapshots representativos, resolvendo o MIP apenas neste conjunto reduzido.
  Resultados: Experimentos em dados de autenticação sintéticos e do mundo real mostram que a heurística baseada em agrupamento produz planos de bloqueio próximos do ideal com custo computacional significamente menor do que resolver para todos os snapshots. A abordagem escala para grafos com milhões de arestas, superando defesas puramente estáticas que falham ao não considerar a aparência de arestas dinâmicas.

Contribuição 2: Otimizando o Tempo de Resposta Cibernética em Grafos Temporais (Capítulo 4)

Problema: Em um cenário temporal, atacantes podem "espreitar" em um nó esperando que uma aresta específica se torne disponível. O objetivo não é apenas bloquear caminhos, mas maximizar o Tempo de Resposta (RT) — a duração entre o gatilho do primeiro decoy pelo atacante e o alcance do Domain Admin (DA).
Metodologia:

Métrica: O RT é definido como a diferença de tempo entre o primeiro gatilho do honeypot e o comprometimento do DA. O defensor visa maximizar o pior caso de RT.
Complexidade: O problema de otimização é provado como NP-difícil via redução do problema de separador temporal $(s, d)$ estrito.
Algoritmo: Um algoritmo de Otimização de Diversidade Evolucionária (EDO) é empregado para encontrar estratégias de defesa diversas e de alta qualidade.
Otimizações:
- Avaliação de Fitness Mais Rápida: Um novo algoritmo baseado em Dijkstra é proposto para computar o "caminho de chegada mais cedo" em grafos temporais. Ele explora o fato de que a maioria das arestas de AD é estática, alcançando uma aceleração de 5x sobre os algoritmos de caminho temporal de última geração (Wu et al.).
- Tratamento de Restrições: Duas técnicas são introduzidas para lidar com a dificuldade de encontrar soluções viáveis (cortes) na busca evolucionária:
  1. Reparo por ILP: Usa Programação Linear Inteira para "corrigir" descendentes inviáveis em cortes válidos.
  2. Fitness Assistido por Surrogates: Usa uma função de surrrogato leve que avalia apenas um conjunto de caminhos "importantes", sendo iterativamente atualizada com novos caminhos de ataque encontrados pelo atacante.

Resultados: A abordagem Assistida por Surrogato (EST) converge para soluções viáveis aproximadamente 108 vezes mais rápido que o EDO vanilla e supera o reparo baseado em ILP em cerca de 23% nas métricas de tempo de resposta, evitando erros de Out-of-Memory em grafos maiores.

Contribuição 3: Assistente Adaptativo para Remoção de Caminhos Entre Camadas (Capítulo 5)

Problema: Como consultar interativamente um administrador de TI para remover arestas e desconectar caminhos de ataque com o número mínimo de consultas, sem saber antecipadamente quais arestas são removíveis.
Metodologia:

Remoção de Caminho Adaptativa (APR): Um "assistente" (wizard) apresenta um caminho de ataque ao administrador como um conjunto de opções de múltipla escolha (arestas naquele caminho). O administrador seleciona uma aresta para remover. O processo se repete até que o caminho seja cortado ou o orçamento se esgote.
Complexidade: Encontrar a política adaptativa ótima é provado como #P-difícil.
Algoritmos:
- Exato (OPT): Uma abordagem de Programação Dinâmica para grafos pequenos.
- Aproximação (APP): Um algoritmo de aproximação submodular adaptativa.
- Heurística Escalável (DPR): Uma heurística de "Programação Dinâmica com Restrições" que se baseia em métodos exatos, mas escala para grafos maiores.
- Abordagem de RL: Uma heurística de Aprendizado por Reforço treinada offline para baixo tempo de inferência.
  Resultados: A heurística DPR entrega os resultados mais fortes, garantindo a eliminação de todos os caminhos $s-t$ quando o orçamento é suficiente. Ela supera significativamente as estratégias não adaptativas de base na redução do número esperado de consultas.

Contribuição 4: Teste de Conectividade Adaptativo Baseado em Características (F-ACT) (Capítulo 6)

Problema: Estender o modelo de consulta adaptativa para generalizar decisões do administrador com base em características das arestas (ex: propriedades de objetos), em vez de consultar arestas individualmente.
Metodologia:

Framework F-ACT: Em vez de perguntar "Remover aresta $e$ ?", o assistente apresenta uma aresta com seu vetor de características. A decisão do administrador (cortar/manter) é aplicada a todas as arestas que compartilham aquele padrão de característica.
Solução de RL (RL4FT): Um agente de Aprendizado por Reforço é treinado para aprender uma política de consulta adaptativa.
- Auto-melhoria: Um mecanismo que permite ao agente melhorar sobre qualquer política de referência dada.
- Modelagem de Recompensa (Reward Shaping): Um esquema invariante de política para lidar com recompensas esparsas.
- Replay de Experiência Priorizado: Um buffer de replay customizado para focar em transições de alto valor.
  Resultos: O RL4FT garante a melhoria sobre qualquer política de referência e supera significativamente as baselines de última geração (incluindo a heurística DPR do Capítulo 5) na minimização do número esperado de consultas, demonstrando a eficácia da generalização baseada em características no endurecimento de segurança.

3. Principais Resultados e Significância

A tese demonstra que:

Defesa Dinâmica é Crítica: Estratégias de posicionamento de honeypot estáticas degradam significativamente quando aplicadas a grafos de AD dinâmicos. As heurísticas propostas baseadas em agrupamento e votação para grafos dinâmicos alcançam desempenho próximo do ótimo com alta escalabilidade.
Consciência Temporal Melhora a Resposta: Ao modelar o grafo temporalmente e maximizar o tempo de resposta, os defensores ganham uma janela crítica para resposta a incidentes. A avaliação de fitness baseada em Dijkstra e os algoritmos EDO assistidos por surrogato tornam isso computacionalmente viável para redes de grande escala.
O Humano no Ciclo é Escalável: Modelos de consulta adaptativa (APR e F-ACT) reduzem com sucesso o fardo administrativo do endurecimento. Ao generalizar decisões através de características de arestas (F-ACT) ou usar seleção de caminho adaptativa (APR), o sistema minimiza o número de consultas necessárias para assegurar a rede enquanto garante a desconexão dos caminhos.
Dificuldade Computacional: A tese estabelece rigorosamente que os problemas subjacentes (posicionamento de honeypot, maximização de corte temporal, consulta adaptativa) são computacionalmente intratáveis (NP-difícil, W[1]-difícil, #P-difícil), justificando a necessidade dos algoritmos de heurística e aproximação propostos.

Significância:
Este trabalho preenche a lacuna entre modelos teóricos de segurança de grafos e o endurecimento prático do Active Directory. Ele vai além das heurísticas simples de remoção de arestas para fornecer um conjunto de ferramentas abrangente que inclui defesa ativa (honeypots), consciência temporal (otimização de tempo de resposta) e automação centrada no humano (assistentes adaptativos). Os algoritmos propostos são projetados para escalar para redes de tamanho empresarial (centenas de milhares de nós), abordando as restrições específicas dos ambientes de AD reais, onde a continuidade operacional e a carga de trabalho do administrador são primordiais. A tese conclui que, embora os problemas sejam teoricamente difíceis, as abordagens baseadas em IA e otimização propostas fornecem soluções práticas e eficazes para a segurança moderna do AD.