Resumo Técnico: A Agulha é um Fio: Encontrando Caminhos Plantados em Árvores de Processos Ruidosas

1. Definição do Problema

O artigo aborda o problema do "caminho plantado" (planted path), um desafio matemático definido como a recuperação de uma sequência pequena e significativa (um caminho) inserida dentro de um grafo acíclico dirigido (DAG) grande e ruidoso e rotulado. Embora o problema tenha análogos teóricos na literatura de "clique plantado" e "estrutura plantada", este trabalho foca em aplicações práticas em cibersegurança, especificamente em árvores de processos.

Neste contexto, o objetivo é identificar a sequência de processos executados por um atacante (o "caminção plantado") enterrada nos enormes e ruidosos logs de computadores comprometidos. O desafio reside no fato de que:

• O volume total de dados de log é enorme.
• Heurísticas ingênuas produzem linhas "suspeitas" demais para inspeção humana.
• A verdadeira sequência maliciosa é frequentemente uma fração pequena da árvore total e é obscurecida pelo ruído (eventos ausentes, falsos positivos e processos de fundo irrelevantes).
• O evento completo pode não existir estritamente como um único caminho contíguo nos dados observados.

Os autores argumentam que, embora a abstração do caminho plantado seja imperfeita para dados do mundo real, a extração de caminhos parciais serve como uma etapa crítica de "agregação de sinal" para aumentar o sinal de sequências ruins e filtrar o ruído.

2. Metodologia

2.1 Algoritmo de Correspondência Difusa (Algoritmo 1)

A principal contribuição é um algoritmo de programação dinâmica projetado para calcular uma pontuação de similaridade baseada em características entre duas árvores, $G$ e $H$.

• Entrada: Duas árvores direcionadas com nós rotulados por características de um conjunto $S$, e uma função de peso $w$ que quantifica a similaridade entre quaisquer duas características.
• Mecanismo: O algoritmo utiliza uma abordagem de tabulação bottom-up (evitando recursão) para encontrar o emparelhamento ideal de nós $(u_1, v_1), \dots, (u_k, v_k)$ de tal forma que a sequência respeite a ordenação pai-filho em ambas as árvores ($u_i <_G u_{i+1}$ e $v_i <_H v_{i+1}$).
• Pontuação: A pontuação de um emparelhamento é a soma dos pesos $w(\phi_G(u_i), \phi_H(v_i))$. O algoritmo maximiza essa pontuação para encontrar o melhor alinhamento "difuso" (fuzzy).
• Complexidade: A complexidade de tempo é polinomial, $O(nm)$, onde $n$ e $m$ são o número de nós nas respectivas árvores.
• Saída: O algoritmo retorna a sequência de nós correspondentes e a pontuação máxima. Pode ser configurado para retornar o melhor caminho único ou adaptado para os "Top-K" caminhos.

2.2 Fluxos de Trabalho

Os autores propõem o uso do Algoritmo 1 como um bloco de construção para fluxos de trabalho de aprendizado de máquina mais amplos:

• Agrupamento Não Supervisionado (Algoritmo 2):

  • Objetivo: Identificar templates desconhecidos dentro de uma coleção de grafos grandes.
  • Processo:
    1. Calcular pontuações de similaridade par a par entre todas as árvores em um conjunto de dados usando o Algoritmo 1.
    2. Converter a matriz de similaridade em uma matriz de distância usando uma normalização específica (Eq. 5).
    3. Incorporar as árvores em um espaço de baixa dimensão (usando UMAP).
    4. Agrupar os embeddings (usando HDBSCAN).
    5. Aplicar uma abordagem de Alinhamento de Múltiplas Sequências (MSA) aos melhores sequências correspondentes dentro dos clusters para extrair "exemplares" representativos.

• Aumento de Características para Classificadores (Seção 3.2):

  • Objetivo: Melhorar a classificação de árvores (ex: benignas vs. maliciosas).
  • Processo: Usar um conjunto de templates conhecidos (ex: sequências de ataque conhecidas) para gerar características auxiliares para cada árvore observada. A característica $X_{i,j}$ representa o comprimento do caminho comum mais longo (ou a pontuação) entre a árvore $G_i$ e o template $T_j$. Essas características são então alimentadas em classificadores padrão (ex: Random Forest).

2.3 Geração de Dados Sintéticos

Para validar a abordagem, os autores introduzem um processo de geração de dados (Algoritmos 3 e 4) análogo ao Modelo de Blocos Estocásticos (SBM), mas adaptado para árvores:

• Geração de Árvore: Utiliza um processo de Galton-Watson para gerar árvores "frondosas" (bushy).
• Caminho Plantado: Uma sequência específica de rótulos é plantada em um caminho aleatório dentro da árvore.
• Modelo de Ruído: Os rótulos no caminho plantado estão sujeitos a uma probabilidade de observação $p$ (subamostragem) e uma probabilidade de erro (reamostragem). Outros nós são rotulados uniformemente a partir de um alfabeto.
• Objetivo de Design: O modelo garante que algoritmos triviais (como contagem de frequências de rótulos) falhem, pois a distribuição de rótulos é independente da classe do caminho plantado, forçando o algoritmo a depender da informação estrutural do caminho.

3. Principais Resultados

3.1 Experimentos Sintéticos

• Distinguibilidade: A pontuação de similaridade derivada do Algoritmo 1 distinguiu com sucesso árvores contendo um caminho plantado daquelas sem ele, mesmo quando o caminho era uma pequena fração de uma árvore grande e observado a uma taxa baixa ($p=0,75$).
• Agrupamento (Clustering): Em configurações não supervisionadas com 4 classes, o fluxo de trabalho de embedding (Algoritmo 2) separou com sucesso os clusters da verdade fundamental (ground-truth).
• Impacto da Ponderação: Experimentos mostraram que o uso de uma função de pontuação ponderada por probabilidade (reduzindo o peso de símbolos raros) melhorou significativamente a separação dos clusters em comparação com uma pontuação binária não ponderada, particularmente quando o alfabeto continha símbolos raros.

3.2 Aplicação no Mundo Real (Conjunto de Dados ACME4)

Os autores aplicaram seus métodos ao conjunto de dados ACME4, um conjunto de dados de cibersegurança que simula uma rede empresarial Windows com vários ataques.

• Escala de Dados: O conjunto de dados continha mais de 1,1 milhão de árvores de processos (majoritariamente de tamanho 2) e quase 3 milhões de nós. Apenas 8 árvores continham usuários "ruins" (maliciosos).
• Construção de Subárvores: Para superar a prevalência de árvores pequenas, os autores construíram 2.693 subárvores (tamanho 3–9.558) a partir de árvores de processos maiores.
• Resultados de Correspondência:
  • Usando uma árvore de referência contendo um usuário "ruim", o algoritmo identificou com sucesso caminhos correspondentes em outras árvores.
  • Flexibilidade de Pontuação: Os autores demonstraram que diferentes funções de pontuação (correspondência exata em nomes de processos vs. correspondência suave em nomes de processos e nomes de usuário) produziram resultados diferentes, porém significativos. Por exemplo, uma correspondência "suave" pôde identificar um caminho onde a sequência de processos era idêntica, mas o nome de usuário era ligeiramente diferente (ex: "user88" vs. "bad3").
• Desempenho do Fluxo de Trabalho:
  • Filtragem: Ao ser usado como um filtro para selecionar árvores que compartilham caminhos com templates conhecidos, o método isolou com sucesso um subconjunto de árvores com pontuações mais altas, o que correlacionou com tamanhos de árvore maiores e sequências de processos específicas (ex: winlogon.exe $\to$ cmd.exe).
  • Classificação: Um classificador Random Forest treinado com características derivadas da correspondência de caminhos (comprimento dos caminhos comuns contra 38 templates) alcançou alta precisão na classificação de árvores com base em seus nomes de processo raiz, com apenas confusões menores entre bash.exe e cmd.exe.

4. Significância e Alegações

O artigo posiciona-se como um trabalho exploratório demonstrando que a extração de caminhos é tanto viável quanto útil para dados reais de cibersegurança.

• Utilidade Prática: Os autores alegam que, embora o problema do "caminho plantado" seja uma abstração, o algoritmo proposto agrega efetivamente sinais de eventos relacionados, filtrando a vasta maioria do ruído que sobrecarregaria especialistas humanos.
• Escopo Modesto: Os autores declaram explicitamente que este é um estudo preliminar. Eles reconhecem que o trabalho atual não fornece soluções estatisticamente ótimas para versões limpas do problema, mas foca no desenvolvimento de modelos realistas para dados "bagunçados".
• Trabalhos Futuros: O artigo observa que uma versão futura fornecerá mais detalhes sobre fluxos de trabalho de aprendizado de máquina realistas, comparações com outros algoritmos em conjuntos de dados reais e análise teórica básica.
• Limitações: Os autores admitem que, em dados reais, o evento completo pode não estar estritamente contido em um único caminho, e que a natureza ruidosa das observações pode impedir a observação de um caminho plantado completo. No entanto, argumentam que mesmo uma filtragem imperfeita aumenta o sinal de sequências maliciosas.

Em resumo, o artigo introduz um algoritmo de correspondência difusa como uma ferramenta fundamental para recuperar sequências significativas de árvores de processos ruidosas, validando sua eficácia através de modelos sintéticos e demonstrando seu potencial como gerador de características e filtro em triagens de cibersegurança do mundo real.