Resumen Técnico: La aguja es un hilo: Encontrando caminos plantados en árboles de procesos con ruido

1. Definición del problema

El artículo aborda el problema del "camino plantado" (planted path), un desafío matemático definido como la recuperación de una secuencia pequeña y significativa (un camino) incrustada dentro de un grafo acíclico dirigido (DAG) etiquetado y con ruido de gran tamaño. Si bien el problema tiene analogías teóricas en la literatura de "clique plantado" y "estructura plantada", este trabajo se centra en aplicaciones prácticas en ciberseguridad, específicamente en árboles de procesos.

En este contexto, el objetivo es identificar la secuencia de procesos ejecutados por un atacante (el "camino plantado") enterrada dentro de los masivos y ruidosos registros de computadoras comprometidas. El desafío radica en que:

• El volumen total de datos de registro es enorme.
• Las heurísticas ingenuas producen demasiadas líneas "sospechosas" para la inspección humana.
• La verdadera secuencia maliciosa suele ser una fracción pequeña del árbol total y está oscurecida por el ruido (eventos faltantes, falsos positivos y procesos de fondo irrelevantes).
• Es posible que el evento completo no exista estrictamente como un único camino contiguo en los datos observados.

Los autores argumentan que, si bien la abstracción del camino plantado es imperfecta para los datos del mundo real, la extracción de caminos parciales sirve como un paso crítico de "agregación de señal" para aumentar la señal de las secuencias dañinas y filtrar el ruido.

2. Metodología

2.1 Algoritmo de coincidencia difusa (Algoritmo 1)

La contribución central es un algoritmo de programación dinámica diseñado para calcular una puntuación de similitud basada en características entre dos árboles, $G$ y $H$.

• Entrada: Dos árboles dirigidos con nodos etiquetados por características de un conjunto $S$, y una función de peso $w$ que cuantifica la similitud entre cualquier par de características.
• Mecanismo: El algoritmo utiliza un enfoque de tabulación de abajo hacia arriba (evitando la recursión) para encontrar el emparejamiento óptimo de nodos $(u_1, v_1), \dots, (u_k, v_k)$ de tal manera que la secuencia respete el orden padre-hijo en ambos árboles ($u_i <_G u_{i+1}$ y $v_i <_H v_{i+1}$).
• Puntuación: La puntuación de un emparejamiento es la suma de los pesos $w(\phi_G(u_i), \phi_H(v_i))$. El algoritmo maximiza esta puntuación para encontrar el mejor alineamiento "difuso".
• Complejidad: La complejidad temporal es polinomial, $O(nm)$, donde $n$ y $m$ son el número de nodos en los respectivos árboles.
• Salida: El algoritmo devuelve la secuencia de nodos emparejados y la puntuación máxima. Puede configurarse para devolver el mejor camino único o adaptarse para los "top-K" caminos.

2.2 Flujos de trabajo

Los autores proponen utilizar el Algoritmo 1 como un bloque de construcción para flujos de trabajo de aprendizaje automático más amplios:

• Clustering no supervisado (Algoritmo 2):

  • Objetivo: Identificar plantillas desconocidas dentro de una colección de grafos grandes.
  • Proceso:
    1. Calcular puntuaciones de similitud de pares entre todos los árboles en un conjunto de datos usando el Algoritmo 1.
    2. Convertir la matriz de similitud en una matriz de distancia utilizando una normalización específica (Ec. 5).
    3. Incrustar los árboles en un espacio de baja dimensión (usando UMAP).
    4. Agrupar las incrustaciones (usando HDBSCAN).
    5. Aplicar un enfoque de Alineamiento de Múltiples Secuencias (MSA) a las mejores secuencias emparejadas dentro de los clusters para extraer "exemplares" representativos.

• Aumento de características para clasificadores (Sección 3.2):

  • Objetivo: Mejorar la clasificación de árboles (por ejemplo, benigno vs. malicioso).
  • Proceso: Utilizar un conjunto de plantillas conocidas (por ejemplo, secuencias de ataque conocidas) para generar características auxiliares para cada árbol observado. La característica $X_{i,j}$ representa la longitud del camino común más largo (o la puntuación) entre el árbol $G_i$ y la plantilla $T_j$. Estas características se introducen luego en clasificadores estándar (por ejemplo, Random Forest).

2.3 Generación de datos sintéticos

Para validar el enfoque, los autores introducen un proceso de generación de datos (Algoritmos 3 y 4) análogo al Modelo de Bloques Estocásticos (SBM) pero adaptado para árboles:

• Generación de Árboles: Utiliza un proceso de Galton-Watson para generar árboles "frondosos" (bushy).
• Camino Plantado: Una secuencia específica de etiquetas se planta en un camino aleatorio dentro del árbol.
• Modelo de Ruido: Las etiquetas en el camino plantado están sujetas a una probabilidad de observación $p$ (submuestreo) y una probabilidad de error (remuestreo). Otros nodos se etiquetan uniformemente de un alfabeto.
• Objetivo de Diseño: El modelo asegura que los algoritmos triviales (como contar frecuencias de etiquetas) fallen, ya que la distribución de las etiquetas es independiente de la clase del camino plantado, obligando al algoritmo a depender de la información estructural del camino.

3. Resultados clave

3.1 Experimentos sintéticos

• Distinguibilidad: La puntuación de similitud derivada del Algoritmo 1 distinguió con éxito entre árboles que contenían un camino plantado y aquellos que no lo contenían, incluso cuando el camino era una fracción pequeña de un árbol grande y se observaba a una tasa baja ($p=0.75$).
• Clustering: En entornos no supervisados con 4 clases, el flujo de trabajo de incrustación (Algoritmo 2) separó con éxito los clusters de la verdad de campo (ground-truth).
• Impacto de la ponderación: Los experimentos mostraron que el uso de una función de puntuación ponderada por probabilidad (reduciendo el peso de símbolos raros) mejoró significativamente la separación de los clusters en comparación con una puntuación binaria sin ponderar, particularmente cuando el alfabeto contenía símbolos raros.

3.2 Aplicación en el mundo real (Conjunto de datos ACME4)

Los autores aplicaron sus métodos al conjunto de datos ACME4, un conjunto de datos de ciberseguridad que simula una red empresarial de Windows con diversos ataques.

• Escala de Datos: El conjunto de datos contenía más de 1.1 millones de árboles de procesos (la mayoría de tamaño 2) y casi 3 millones de nodos. Solo 8 árboles contenían usuarios "malos" (maliciosos).
• Construcción de Sub-árboles: Para superar la prevalencia de árboles pequeños, los autores construyeron 2,693 sub-árboles (tamaño 3–9,558) a partir de árboles de procesos más grandes.
• Resultados de Coincidencia:
  • Usando un árbol de referencia que contiene un usuario "malo", el algoritmo identificó con éxito caminos coincidentes en otros árboles.
  • Flexibilidad de Puntuación: Los autores demostraron que diferentes funciones de puntuación (coincidencia exacta en nombres de procesos vs. coincidencia suave en nombres de procesos y nombres de usuario) produjeron resultados diferentes pero significativos. Por ejemplo, una coincidencia "suave" pudo identificar un camino donde la secuencia de procesos era idéntica pero el nombre de usuario era ligeramente diferente (por ejemplo, "user88" vs. "bad3").
• Rendimiento del Flujo de Trabajo:
  • Filtrado: Al usarse como filtro para seleccionar árboles que comparten caminos con plantillas conocidas, el método aisló con éxito un subconjunto de árboles con puntuaciones más altas, lo cual se correlacionó con tamaños de árbol mayores y secuencias de procesos específicas (por ejemplo, winlogon.exe $\to$ cmd.exe).
  • Clasificación: Un clasificador Random Forest entrenado con características derivadas del emparejamiento de caminos (longitud de caminos comunes contra 38 plantillas) logró una alta precisión en la clasificación de árboles basados en los nombres de sus procesos raíz, con solo confusiones menores entre bash.exe y cmd.exe.

4. Significancia y Reivindicaciones

El artículo se posiciona como un trabajo exploratorio que demuestra que la extracción de caminos es tanto factible como útil para datos reales de ciberseguridad.

• Utilidad Práctica: Los autores afirman que, si bien el problema del "camino plantado" es una abstracción, el algoritmo propuesto agrega eficazmente las señales de eventos relacionados, filtrando la gran mayoría del ruido que abrumaría a los expertos humanos.
• Alcance Modesto: Los autores declaran explícitamente que este es un estudio preliminar. Reconocen que el trabajo actual no proporciona soluciones estadísticamente óptimas para versiones limpias del problema, sino que se enfoca en desarrollar modelos realistas para datos "sucios".
• Trabajo Futuro: El artículo señala que una versión futura proporcionará más detalles sobre flujos de trabajo de aprendizaje automático realistas, comparaciones con otros algoritmos en conjuntos de datos reales y un análisis teórico básico.
• Limitaciones: Los autores admiten que en datos reales, el evento completo podría no estar contenido estrictamente en un único camino, y que la naturaleza ruidosa de las observaciones puede impedir la observación de un camino plantado completo. Sin embargo, argumentan que incluso un filtrado imperfecto aumenta la señal de las secuencias maliciosas.

En resumen, el artículo introduce un algoritmo de coincidencia difusa como una herramienta fundamental para recuperar secuencias significativas de árboles de procesos ruidosos, validando su eficacia mediante modelos sintéticos y demostrando su potencial como generador de características y filtro en el triaje de ciberseguridad del mundo real.