Teoría de grafos en ciberseguridad

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Por qué las preguntas de seguridad son preguntas sobre grafos

Un escáner de vulnerabilidades produce una lista. Te dice que este host ejecuta una biblioteca desactualizada, que aquel expone una interfaz de administración y que un tercero tiene una cuenta de servicio débil. Cada elemento recibe una severidad, la lista se ordena y se corrige lo de arriba.

Los atacantes no leen esa lista como los defensores. Una intrusión es una secuencia: un punto de apoyo en algún sitio sin importancia, una credencial obtenida allí, un servicio que confía en esa credencial, un recurso compartido que confía en ese servicio y, al final, algo que importa. Cada paso puede ser anodino por sí solo. La combinación es la brecha.

Esa diferencia es exactamente la diferencia entre un conjunto y un grafo. Una lista de debilidades no tiene estructura; un conjunto de debilidades más las transiciones entre ellas es un grafo dirigido, y en cuanto existe, las preguntas que interesan a los defensores se convierten en algoritmos estándar. ¿Qué ruta es la más fácil? Camino mínimo. ¿Qué controles cortan todas las rutas? Corte mínimo. ¿Hasta dónde llega un compromiso? Alcanzabilidad. ¿Cuándo deja el malware de extinguirse solo? El mayor autovalor de la matriz de adyacencia.

No es una idea nueva en la literatura. Phillips y Swiler propusieron el análisis de vulnerabilidades basado en grafos en 1998, Sheyner y sus colegas automatizaron la generación de grafos de ataque con model checking en 2002, y desde entonces el enfoque es estándar en la investigación. Lo nuevo es que las herramientas por fin se han puesto al día: los entornos actuales son tan grandes que nadie puede tener todos los caminos en la cabeza, y los grafos de este tamaño se resuelven en milisegundos.

Cada número de este artículo se calculó resolviendo el modelo, no estimándolo. Si el vocabulario de grafos te resulta ajeno, la introducción a la teoría de grafos cubre las definiciones que se usan aquí.

2. El grafo de ataque: nodos, arcos y pesos

Tres decisiones de modelado cargan con el peso, y cada una tiene una contrapartida honesta.

¿Qué es un nodo? La opción útil más sencilla es un host, que es lo que usa este artículo. Los modelos de investigación suelen ser más finos: un nodo es un estado, un par formado por una máquina y un nivel de privilegio, de modo que «usuario en web01» y «root en web01» son vértices distintos. Es más fiel y mucho más grande, porque el espacio de estados se multiplica. También existen modelos más gruesos, en los que un nodo es una subred entera. Elige la granularidad a la que actúan tus controles, porque el modelo existe para comparar controles.

¿Qué es un arco? Una transición que el atacante puede hacer: un servicio explotable, una relación de confianza, una credencial reutilizada, un recurso compartido montado, un objetivo de phishing. Los arcos son dirigidos, porque el compromiso fluye en un solo sentido. Una estación de trabajo que monta un recurso compartido te da un arco hacia el recurso, no desde él, y equivocarse de dirección invierte todos los resultados.

¿Qué va en el arco? Al menos un número, y la elección determina qué significa «más corto»:

• Esfuerzo del atacante, una puntuación de dificultad. El camino mínimo significa entonces la intrusión más fácil. Este artículo usa el esfuerzo.
• Probabilidad de éxito. Multiplica a lo largo del camino en lugar de sumar, o suma los logaritmos negativos y usa sin cambios el mismo algoritmo de camino mínimo.
• Coste del control. El precio de la medida que elimina ese arco. El corte mínimo sobre estos números es la forma más barata de cortar todas las rutas, que es la sección 6.

¿De dónde salen los números? Normalmente de un sistema de puntuación como la explotabilidad de CVSS, calibrado por alguien que conoce el entorno. Son estimaciones, y la postura honesta es que el orden es mucho más robusto que los valores absolutos. Si no puedes defender un 3 frente a un 4, sí puedes defender que un exploit web público es más fácil que robar una credencial de administrador de dominio, y ese orden es lo que determina los resultados de abajo.

3. La red que recorre todo el artículo

El ejemplo es una pequeña empresa, deliberadamente corriente. Internet llega a tres sistemas expuestos: un servidor web público, una pasarela de correo y un concentrador VPN. Detrás hay dos estaciones de trabajo y un servidor de aplicaciones, luego un servidor de ficheros y una base de datos y, por último, el controlador de dominio, que es lo que quiere el atacante.

Cada uno de los dieciséis arcos lleva una puntuación de esfuerzo y un coste de control. Las puntuaciones de esfuerzo dicen que explotar la aplicación web pública cuesta 3, que una llamada interna entre servicios de la DMZ a la capa de aplicación cuesta 2 y que robar credenciales de administrador de dominio en caché de una estación de trabajo cuesta 8, lo que es difícil pero no imposible. Esos juicios relativos son la única entrada real del modelo.

Una nota estructural antes de ejecutar ningún algoritmo: este grafo no tiene ciclos, porque cada arco lleva al atacante hacia dentro. Los grafos de ataque reales sí tienen ciclos, porque un atacante puede pivotar de un lado a otro, y todos los algoritmos de abajo los manejan. El caso acíclico solo hace que los ejemplos resueltos sean más fáciles de comprobar a mano.

4. La entrada más fácil: rutas de ataque mínimas

La primera pregunta es la que un pentester responde a mano en quince días: ¿cuál es la ruta más fácil de internet al controlador de dominio? Con el esfuerzo en los arcos es un problema de camino mínimo, y el algoritmo de Dijkstra lo responde para todos los activos a la vez.

La respuesta es internet → web01 → app01 → db01 → dc01 con un esfuerzo total de 12. Lee los pasos: explotar la aplicación web pública (3), usar la llamada interna de confianza a la capa de aplicación (2), llegar a la base de datos que la aplicación tiene derecho a consultar (3) y abusar de la cuenta de servicio de la base de datos contra el controlador de dominio (4).

Dos cosas de ese resultado importan más que el número.

Ninguno de esos cuatro pasos es alarmante por sí solo. Una vulnerabilidad de aplicación web con una puntuación de 3 sobre 10 no encabeza un registro de riesgos. Tampoco una llamada entre dos sistemas que se supone que deben hablar entre sí. La ruta es peligrosa como composición, y ninguna puntuación de severidad por host puede expresar una composición. Es el argumento fundamental a favor de los grafos de ataque, planteado por Phillips y Swiler en 1998 y repetido en todos los artículos desde entonces.

La ruta más fácil evita a las personas. El phishing es el vector de acceso inicial más comentado, y aquí la ruta de phishing al controlador de dominio cuesta 14, no 12. El modelo no dice que el phishing no importe; dice que en este entorno, con estas puntuaciones, la ruta por los servidores es más barata. Resolver la opción más barata para el atacante en lugar de la más temida por el defensor es precisamente para lo que sirve el algoritmo.

El mismo cálculo da el esfuerzo para llegar a cualquier otro activo: web01 cuesta 3, app01 cuesta 5, el servidor de ficheros 8 y la base de datos 8. Esos son los números que hay que poner delante de un comité de auditoría que quiere saber lo lejos que está realmente el perímetro de las joyas de la corona.

5. Dieciséis formas de entrar, y qué host las soporta

El camino más barato es una respuesta. Bloquearlo no es una estrategia, porque el atacante simplemente toma el siguiente. La pregunta útil es cuántas rutas existen y por qué activos pasan.

Enumerar todos los caminos simples de internet al controlador de dominio en este grafo da 16 rutas distintas, con costes entre 12 y 25 y una mediana de 18,5. Dieciséis es un número pequeño precisamente porque el ejemplo es pequeño; un entorno real con unos miles de hosts tiene habitualmente más rutas de ataque de las que tiene sentido contar, por eso la enumeración es un recurso didáctico y las métricas de abajo son la técnica de producción.

Contar cuántas de esas rutas pasan por cada host produce una clasificación, y no es la que daría un informe de perímetro.

El servidor de ficheros está en 12 de las 16 rutas, tres cuartas partes. El servidor web público, la máquina más vigilada en la mayoría de las organizaciones, está en 3. Nada del servidor de ficheros llamaría la atención en un escaneo externo: no está expuesto, no ejecuta nada exótico y existe para guardar documentos. Es crítico por el lugar que ocupa en el grafo, y solo un grafo puede decirlo.

La enumeración es también donde este enfoque deja de escalar, y vale la pena ver por qué. De diez hosts y dieciséis arcos salen dieciséis rutas. Añade un segundo servidor de ficheros al que lleguen las dos estaciones y la cifra casi se duplica; un entorno real con unos miles de máquinas y una red interna plana tiene un número de caminos con más cifras de las que nadie leerá nunca. Todas las métricas de abajo evitan enumerar, y eso es lo que las hace utilizables en una red real.

Esta medida es una prima, propia de la seguridad, de la centralidad de intermediación, introducida por Freeman en 1977, que cuenta la fracción de caminos mínimos que pasan por un vértice. La intermediación sobre todos los pares es la medida estándar de la ciencia de redes y se calcula en O(nm) con el algoritmo de Brandes. Para la defensa, contar los caminos entre el par concreto que importa, la entrada del atacante y el activo que te preocupa, suele ser más accionable: responde a «si endurezco una máquina, cuántas rutas altero» en lugar de «qué central es en general».

Noel y Jajodia plantearon el mismo argumento para la colocación de sensores en 2008: pon la detección donde se concentran las rutas de ataque, no donde están los activos más valiosos, porque los puntos de concentración son donde obtienes más cobertura por sensor.

6. Cortar todas las rutas: el corte mínimo

Clasificar los hosts te dice dónde mirar. La pregunta más fuerte es qué conjunto de controles cortaría todas las rutas a la vez, y lo poco que podría costar.

Asigna a cada arco el coste del control que lo elimina y calcula el corte mínimo entre internet y el controlador de dominio. El teorema de flujo máximo y corte mínimo garantiza que el conjunto más barato es exactamente el corte mínimo, y el algoritmo lo devuelve en tiempo polinómico. La misma maquinaria se trata en flujo en redes, flujo máximo y corte mínimo.

La respuesta son tres controles que suman 7: impedir que el servidor web de la DMZ llame a la capa de aplicación (3), impedir que los adjuntos de correo se ejecuten en las estaciones de trabajo (2) y hacer que los usuarios de VPN lleguen a un segmento restringido en lugar de junto a las estaciones (2). Volver a enumerar los caminos tras aplicarlos devuelve cero.

Fíjate en dónde cae el corte. Los tres controles están en la frontera entre el perímetro y el interior, y ninguno toca el controlador de dominio, la base de datos ni el servidor de ficheros. El instinto de endurecer primero las joyas de la corona no es lo que recomiendan las matemáticas: la solución completa más barata está en el punto más estrecho del grafo, y aquí es el primer salto hacia dentro.

La misma pregunta sobre máquinas en lugar de enlaces usa el truco de dividir nodos. Sustituye cada host por una copia de entrada y otra de salida unidas por un arco de capacidad 1, da capacidad infinita a los arcos reales, y el corte mínimo cuenta ahora hosts en lugar de enlaces. Aquí la respuesta es 3 hosts: web01, mail01 y vpn, que son justo los tres que dan a internet. En un ejemplo pequeño es una comprobación tranquilizadora y en uno grande un cálculo realmente útil, porque allí el conjunto equivalente rara vez es obvio.

7. Lo que compra realmente un solo control

Los presupuestos rara vez financian tres controles a la vez, así que la pregunta práctica es cuál comprar primero. Eliminar cada arco por turno y volver a resolver da una respuesta, y la respuesta es aleccionadora.

El mejor control individual eleva el esfuerzo del atacante de 12 a 14. Eso es todo. Ninguna medida individual en esta red compra más de dos puntos de dificultad, porque el grafo está muy conectado y el atacante simplemente cambia a la siguiente ruta más barata. Es la versión cuantitativa de una verdad conocida en seguridad: la defensa en profundidad no es un eslogan, es una consecuencia de que los cortes aislados en un grafo denso hacen muy poco.

La tabla también muestra que la métrica que eliges cambia la clasificación. Bloquear la transición de la pasarela de correo a la estación de trabajo reduce a la mitad el número de rutas, de 16 a 8, y deja intacta en 12 la ruta más fácil del atacante. Si tu consejo mide «rutas de ataque eliminadas», llamarías a ese control un éxito; si mide «esfuerzo del atacante», lo llamarías inútil. Los dos números son reales, miden cosas distintas, y citar solo uno es la forma en que los programas de seguridad acaban optimizando la magnitud equivocada.

La mejor relación calidad-precio de la tabla es bloquear la ruta de la base de datos al controlador de dominio: coste 5, esfuerzo hasta 14 y rutas bajando a 7. Es el único control que mejora sustancialmente las dos métricas, y ninguna intuición lo habría identificado.

8. Radio de impacto: hasta dónde llega un compromiso

Las rutas de ataque preguntan cómo entra un intruso. La pregunta complementaria es qué pasa una vez que está dentro de algún sitio, y es un simple cálculo de alcanzabilidad: desde un host comprometido, ¿a qué activos se puede llegar al final? Un recorrido por host lo responde en tiempo lineal.

La clasificación invierte la de exposición. El servidor web público, la máquina más expuesta del entorno, alcanza 4 activos. La pasarela de correo alcanza 6. Una estación de trabajo alcanza 5. La exposición mide quién puede llegar a ti; el radio de impacto mide a quién puedes llegar tú, y los dos producen listas de prioridades distintas a partir del mismo grafo.

El número que debería detener una reunión es este: nueve de los diez hosts pueden llegar al final al controlador de dominio. Solo el propio controlador no puede, porque no hay nada más allá. En un entorno real, esa cifra es el resultado más útil de todo el ejercicio, porque convierte «tenemos una red plana» de una opinión en una medición.

El radio de impacto también hace manejables las decisiones de contención durante un incidente. Cuando se confirma que un host está comprometido, el conjunto de máquinas que hay que investigar es su conjunto alcanzable hacia delante, y el que podría haberlo infectado es su conjunto alcanzable hacia atrás, calculado sobre el grafo invertido. Ambos son un solo recorrido, y ambos son mucho más precisos que aislar una subred entera por instinto.

9. A qué velocidad se propaga: el umbral epidémico

El ransomware y los gusanos no siguen un único camino; se propagan. Modelarlo requiere otra pregunta: dada una red y una infección que se propaga entre vecinos y se limpia a cierto ritmo, ¿se extingue o se apodera del entorno?

La respuesta es uno de los resultados más útiles de la ciencia de redes, y es exacta. Para una clase muy amplia de modelos de propagación, el punto de inflexión depende de un solo número: el mayor autovalor de la matriz de adyacencia, escrito λ₁. Una infección cuya razón entre propagación y limpieza está por debajo de 1 / λ₁ se extingue por sí sola; por encima, se vuelve endémica. Wang, Chakrabarti, Wang y Faloutsos lo demostraron en 2003, y Chakrabarti y sus colegas lo generalizaron en 2008.

En el grafo de movimiento lateral de este ejemplo, nueve hosts y trece enlaces, λ₁ vale 3,573, así que el umbral es 0,280. Simulando una infección al 40 % de esa razón, con la media de 600 ejecuciones, se extingue en el paso 21. Al cuádruple de la razón se estabiliza en 5,5 de los 9 hosts y se queda ahí indefinidamente. El umbral predijo ambos resultados antes de ejecutar ninguna simulación.

Lo que lo hace interesante en la práctica es que λ₁ es algo que puedes cambiar. Aislar el servidor de ficheros de las estaciones de trabajo y de la capa de aplicación elimina tres enlaces y baja λ₁ de 3,573 a 2,570, lo que eleva el umbral de 0,280 a 0,389. Es un margen un 39 % mayor: las infecciones que antes habrían arraigado ahora se extinguen.

Dos hechos hacen que el autovalor sea más fácil de razonar de lo que parece. Siempre está entre el grado medio y el grado máximo del grafo, que aquí significa entre 2,889 y 5, y 3,573 queda debidamente entre ambos. Y lo domina la parte más densa de la red, así que la forma más rápida de bajarlo es reducir la conectividad del host más conectado. Eso es exactamente lo que hace la segmentación de arriba: el servidor de ficheros tiene grado 5, el más alto del entorno, y cortar tres de sus enlaces lo deja en 2 y baja el grado máximo de todo el grafo de 5 a 3. La máquina más conectada es la que hay que aislar, y el grado es un cálculo de una línea que puedes hacer antes de tocar ningún código de autovalores.

Esto cambia la forma de ver la segmentación. «Segmenta la red» suele justificarse con una historia; aquí es una intervención sobre una magnitud calculable, con un antes y un después. La idea se remonta a Kephart y White, que construyeron modelos epidemiológicos de virus informáticos sobre grafos dirigidos para el IEEE Security and Privacy en 1991, y a Staniford, Paxson y Weaver, cuyo análisis de 2002 sobre la propagación de gusanos mostró lo rápido que se mueve la curva cuando el grafo es denso.

10. Active Directory: el grafo que los atacantes ya usan

Todo lo anterior ha sido un modelo construido por un defensor. El grafo más importante de la seguridad empresarial ya existe, nadie lo diseñó deliberadamente y los atacantes llevan años consultándolo: Active Directory.

Un entorno de AD es un grafo lo dibuje alguien o no. Los usuarios son vértices, los grupos son vértices, los equipos son vértices, y los arcos son las relaciones que el directorio ya almacena: es miembro de, es administrador en, puede restablecer la contraseña de, tiene una sesión en, es propietario de, tiene GenericWrite sobre. Cada una de esas relaciones es una transición que un atacante puede usar.

En 2016 Robbins, Vazarkar y Schroeder publicaron BloodHound y dieron la charla que puso nombre a la técnica, «Six Degrees of Domain Admin». Su idea es exactamente la de este artículo: los hechos individualmente inofensivos se componen. Un grupo de soporte que puede restablecer contraseñas de un grupo que contiene a un usuario que resulta tener una sesión activa en un servidor donde un administrador de dominio inició sesión el martes pasado es un camino de cuatro saltos hacia el compromiso total, y ningún eslabón por separado parece una mala configuración.

Lo que hace BloodHound es recoger esas relaciones y lanzar sobre ellas una consulta de camino mínimo. Es Dijkstra, sobre un grafo que a nadie se le había ocurrido dibujar. El resultado cambió la práctica defensiva, porque los caminos que sacaba a la luz eran reales e invisibles para cualquier otra herramienta en uso.

Tres lecciones se aplican a cualquier entorno:

• Los datos ya existen. Las relaciones de directorio, las políticas de IAM en la nube, los role bindings de Kubernetes y los permisos de compartición de SaaS son todos grafos guardados en una base de datos, esperando a que se consulten como tales.
• Las sesiones también son arcos. Una sesión iniciada crea una arista temporal de esa máquina a los privilegios de esa identidad, por eso «quién ha iniciado sesión dónde» es una pregunta de seguridad y no de inventario.
• Limpiar es editar el grafo. Eliminar una sola pertenencia anidada a un grupo puede borrar miles de caminos, y no hay forma de verlo sin el grafo.

11. Detección: grafos de procedencia y culpa por asociación

Los grafos de ataque sirven para prevenir. Otras dos técnicas de grafos funcionan en el lado de la detección, y usan grafos completamente distintos.

Los grafos de procedencia registran lo que ocurrió realmente en un sistema: procesos, ficheros, sockets y las relaciones causales entre ellos. Un proceso lee un fichero, escribe otro, lanza un hijo, abre una conexión. King y Chen introdujeron el rastreo hacia atrás con su sistema BackTracker en SOSP en 2003: dado un punto de detección, como un fichero sospechoso, se recorre hacia atrás el grafo causal para averiguar cómo llegó ahí. El recorrido hacia delante desde un punto de entrada te dice el daño; el recorrido hacia atrás desde un síntoma te dice la causa raíz. Ambos son recorridos sobre la misma estructura registrada.

La versión moderna correlaciona esos flujos con el comportamiento conocido de los atacantes. HOLMES, publicado en IEEE Security and Privacy en 2019, asigna los flujos de información sospechosos de un grafo de procedencia a las tácticas y técnicas del ciclo de vida de un ataque y lanza una alerta cuando el patrón de flujos se parece más a una intrusión que a la actividad normal. La dificultad de ingeniería es la escala: los grafos de procedencia crecen en millones de aristas por hora en un solo host con carga, lo que convierte su reducción y consulta eficientes en todo el problema de investigación.

La culpa por asociación es la segunda técnica, y es inferencia sobre grafos en lugar de recorrido. Se construye un grafo bipartito de máquinas y ficheros: una máquina está conectada con cada fichero que ha visto. La mayoría de ficheros y máquinas no tienen etiqueta, pero algunos se sabe que son buenos y otros que son malos. La propagación de creencias (belief propagation) difunde entonces esas etiquetas por las aristas, suponiendo que los ficheros que aparecen en muchas máquinas infectadas son sospechosos y que las máquinas con muchos ficheros malos están comprometidas.

Es lo que Chau, Nachenberg, Wilhelm, Wright y Faloutsos construyeron como Polonium en 2011, sobre un grafo de unos 60.000 millones de aristas máquina-fichero procedentes de la telemetría de Symantec, con una tasa de detección de verdaderos positivos en torno al 85 %. La técnica importa porque no necesita firma ni sandbox: un fichero que nadie ha analizado nunca puede juzgarse por las compañías que frecuenta. La misma forma de cálculo, un grafo bipartito más propagación de etiquetas, impulsa la detección de fraude en pagos y la detección de abusos en redes sociales.

12. El grafo de la cadena de suministro de software

El último grafo es el que recorre tu sistema de compilación. Una aplicación moderna declara un puñado de dependencias directas, cada una declara las suyas, y el cierre transitivo llega habitualmente a cientos o miles de paquetes. Ese cierre es un grafo dirigido acíclico, y es una superficie de ataque.

La pregunta de seguridad es de alcanzabilidad. Si un paquete profundo del grafo está comprometido, ¿cuáles de tus aplicaciones ejecutan su código? Es alcanzabilidad hacia delante desde el nodo comprometido en el grafo de dependencias invertido, y es la consulta que toda organización se apresura a responder en la primera hora de un incidente de cadena de suministro. Los equipos que mantienen una lista de materiales de software (SBOM) la responden en segundos; los que no, pasan días con grep.

Dos propiedades del grafo lo hacen peligroso de maneras que una lista no revelaría. La profundidad oculta el riesgo: un paquete que nunca elegiste, tres niveles por debajo de uno que sí elegiste, se ejecuta con los mismos privilegios que tu propio código. La popularidad lo concentra: los paquetes con mayor grado de entrada son los objetivos más valiosos, porque comprometer uno alcanza de golpe a miles de proyectos que dependen de él, que es justo el patrón documentado en la revisión de ataques reales a la cadena de suministro de código abierto de Ohm, Plate, Sykosch y Meier en 2020.

Las métricas defensivas útiles son métricas de grafos. Cuenta el tamaño del cierre transitivo, no el número de dependencias directas. Clasifica las dependencias según cuántas de tus aplicaciones llegan a ellas. Vigila los paquetes con un solo mantenedor y un gran grado de entrada, que es exactamente el perfil de riesgo que ha producido varios de los incidentes más conocidos. La técnica es idéntica al cálculo del radio de impacto de la sección 8, aplicado a otro grafo.

13. Qué es fácil y qué es difícil

El análisis de grafos de ataque es poco habitual entre las técnicas de seguridad porque tiene una historia de complejidad limpia, y saber de qué lado de la línea cae una pregunta ahorra mucho esfuerzo perdido.

El patrón es el conocido: las preguntas sobre flujo y conectividad son baratas, las preguntas sobre qué cosas discretas cambiar son caras. La enumeración es la trampa del medio. Es intuitiva, es lo que hace toda demostración, y el número de caminos simples puede crecer exponencialmente con el tamaño de la red, por eso las herramientas serias calculan métricas sobre el grafo en lugar de listar sus caminos. Ammann, Wijesekera y Kaushik plantearon exactamente este argumento en 2002 al proponer una representación compacta y monótona que escala polinómicamente en lugar de enumerar.

Una métrica que conviene conocer por su nombre es k-zero day safety, propuesta por Wang, Jajodia, Singhal, Cheng y Noel en 2014. Pregunta cuántas vulnerabilidades desconocidas distintas necesitaría un atacante para llegar a un activo, lo que esquiva la pregunta imposible de cuán probable es cada exploit. Es una distancia en el grafo con otra ponderación, y un buen ejemplo del mejor instinto del campo: medir la estructura, no la probabilidad.

14. Errores de modelado

Un grafo de ataque erróneo es peor que ninguno, porque produce prioridades seguras, concretas e incorrectas. Estos son los fallos que se repiten.

• Equivocarse en la dirección de los arcos. Una estación de trabajo que monta un recurso compartido crea un arco hacia el recurso. Invertirlo hace que el servidor de ficheros parezca seguro y la estación crítica, y nada de la salida parece roto.
• Modelar hosts cuando el riesgo está en las identidades. Si la transición real es una credencial que funciona en tres sitios, un arco entre dos máquinas no la recoge. Por eso el grafo de Active Directory de la sección 10 es un modelo aparte y no un refinamiento de este.
• Tratar las puntuaciones como mediciones. Los números de esfuerzo son juicios. Fíate del orden, desconfía de la tercera cifra decimal y comprueba si la conclusión sobrevive a perturbar las puntuaciones. Si el control recomendado cambia cuando un 3 pasa a ser un 4, dilo.
• Olvidar que el grafo es una instantánea. Un portátil que se une a la VPN añade arcos; un servidor dado de baja los quita; una excepción temporal del cortafuegos durante una migración puede abrir una ruta que ningún diagrama registró. Un grafo de ataque solo está tan al día como el inventario que lo respalda.
• Enumerar caminos en un entorno real. Funciona de maravilla con diez hosts y no termina nunca con diez mil. Calcula en su lugar cortes, centralidad y alcanzabilidad, que son todos polinómicos.
• Informar de una sola métrica. La sección 7 mostró un control que reduce a la mitad el número de rutas de ataque y no frena en absoluto al atacante. Publica el esfuerzo del atacante y el número de rutas juntos, o el programa optimizará la que esté en la diapositiva.
• Ignorar los arcos que no se pueden quitar. Algunas transiciones son el propio negocio: la aplicación tiene que consultar la base de datos. El modelo debería marcarlas como fijas, para que el optimizador deje de proponer controles que nunca se aprobarán.

15. Del modelo a la práctica

Cuatro cosas separan un diagrama que impresiona en una reunión de un modelo que cambia decisiones.

Construye el grafo con datos que ya tienes. Los conjuntos de reglas del cortafuegos, las definiciones de grupos de seguridad en la nube, los resultados de escaneos de vulnerabilidades, las relaciones de Active Directory y la telemetría EDR describen todos aristas. Un modelo montado a mano en un taller queda obsoleto la semana siguiente; un modelo generado a partir de la configuración se regenera cada noche.

Empieza por la alcanzabilidad, no por las rutas de ataque. El resultado valioso más barato es la tabla de radio de impacto de la sección 8, porque no necesita ninguna puntuación de exploits, solo conectividad. «Nueve de nuestros diez hosts pueden llegar al controlador de dominio» es un hallazgo que cala, y puedes producirlo antes de que nadie discuta sobre CVSS.

Usa las herramientas que existen. MulVAL, el generador escalable de grafos de ataque publicado por Ou, Boyer y McQueen en 2006, sigue siendo la implementación de referencia en investigación. BloodHound cubre el grafo de identidades. NetworkX o una base de datos de grafos se encarga del análisis una vez que existen las aristas. Ninguno de los algoritmos de este artículo hay que escribirlo desde cero, y los capítulos de grafos de cualquier libro de algoritmos cubren los que sí.

Vuelve a resolver en lugar de discutir. Cada afirmación de este artículo la zanjó el modelo en milisegundos: que la ruta más fácil evita las estaciones de trabajo, que el servidor de ficheros soporta cuatro veces más rutas que el servidor web, que el mejor control individual compra dos puntos de esfuerzo, que la segmentación eleva el umbral epidémico un 39 %. La intuición sobre redes falla justo en los casos que importan, y todo el valor de construir el grafo es que dejas de necesitarla.

16. Cómo seguir

La forma más rápida de interiorizar este material es construir un grafo en lugar de leer sobre él, y la barrera es más baja de lo que parece. Diez hosts y dieciséis arcos, que es todo lo que usó este artículo, caben en un fichero de texto, y cada resultado de arriba salió de unas pocas docenas de líneas de código corriente.

Un orden sensato para aprender las piezas: familiarízate con la búsqueda en anchura y en profundidad, ya que la alcanzabilidad y el radio de impacto no son más que un recorrido con contabilidad. Luego los algoritmos de camino mínimo, que te dan el análisis de la ruta más fácil y, con logaritmos negativos en los arcos, también el de la ruta más probable. Luego flujo máximo y corte mínimo, que es todo el contenido de las secciones 6 y 7 y el resultado más infrautilizado de la seguridad defensiva.

Después, la dirección útil es estructural más que algorítmica: los grafos dirigidos y no dirigidos zanjan un número sorprendente de discusiones de modelado, y la representación de grafos decide si tu análisis tarda un segundo o una hora cuando el entorno es grande. Los límites de complejidad de la sección 13 se exponen de forma más general en algoritmos de grafos y complejidad.

Si prefieres empezar por el lado de la seguridad, el camino más corto hacia un resultado real es exportar tus relaciones de Active Directory y consultarlas, porque ese grafo ya existe y nadie tuvo que modelarlo. El hallazgo que sigue suele ser el mismo con el que termina este artículo: el número de máquinas que pueden llegar al final al controlador de dominio es mucho mayor de lo que nadie en la sala esperaba.

18. Referencias

Los artículos que establecieron estas técnicas, en orden cronológico.

1. Ford, L. R. y Fulkerson, D. R. (1956). “Maximal flow through a network.” Canadian Journal of Mathematics, 8, 399–404.
2. Freeman, L. C. (1977). “A set of measures of centrality based upon betweenness.” Sociometry, 40(1), 35–41.
3. Kephart, J. O. y White, S. R. (1991). “Directed-graph epidemiological models of computer viruses.” Proceedings of the IEEE Symposium on Security and Privacy, 343–359.
4. Phillips, C. y Swiler, L. P. (1998). “A graph-based system for network-vulnerability analysis.” Proceedings of the New Security Paradigms Workshop, 71–79.
5. Ammann, P., Wijesekera, D. y Kaushik, S. (2002). “Scalable, graph-based network vulnerability analysis.” Proceedings of the 9th ACM Conference on Computer and Communications Security, 217–224.
6. Sheyner, O., Haines, J., Jha, S., Lippmann, R. y Wing, J. M. (2002). “Automated generation and analysis of attack graphs.” Proceedings of the IEEE Symposium on Security and Privacy, 273–284.
7. Jha, S., Sheyner, O. y Wing, J. (2002). “Two formal analyses of attack graphs.” Proceedings of the 15th IEEE Computer Security Foundations Workshop, 49–63.
8. Staniford, S., Paxson, V. y Weaver, N. (2002). “How to own the Internet in your spare time.” Proceedings of the 11th USENIX Security Symposium, 149–167.
9. King, S. T. y Chen, P. M. (2003). “Backtracking intrusions.” Proceedings of the 19th ACM Symposium on Operating Systems Principles, 223–236.
10. Wang, Y., Chakrabarti, D., Wang, C. y Faloutsos, C. (2003). “Epidemic spreading in real networks: an eigenvalue viewpoint.” Proceedings of the 22nd International Symposium on Reliable Distributed Systems, 25–34.
11. Ou, X., Boyer, W. F. y McQueen, M. A. (2006). “A scalable approach to attack graph generation.” Proceedings of the 13th ACM Conference on Computer and Communications Security, 336–345.
12. Chakrabarti, D., Wang, Y., Wang, C., Leskovec, J. y Faloutsos, C. (2008). “Epidemic thresholds in real networks.” ACM Transactions on Information and System Security, 10(4), 1–26.
13. Noel, S. y Jajodia, S. (2008). “Optimal IDS sensor placement and alert prioritization using attack graphs.” Journal of Network and Systems Management, 16(3), 259–275.
14. Chau, D. H., Nachenberg, C., Wilhelm, J., Wright, A. y Faloutsos, C. (2011). “Polonium: tera-scale graph mining and inference for malware detection.” Proceedings of the SIAM International Conference on Data Mining, 131–142.
15. Wang, L., Jajodia, S., Singhal, A., Cheng, P. y Noel, S. (2014). “k-zero day safety: a network security metric for measuring the risk of unknown vulnerabilities.” IEEE Transactions on Dependable and Secure Computing, 11(1), 30–44.
16. Robbins, A., Vazarkar, R. y Schroeder, W. (2016). “Six degrees of Domain Admin.” DEF CON 24.
17. Milajerdi, S. M., Gjomemo, R., Eshete, B., Sekar, R. y Venkatakrishnan, V. N. (2019). “HOLMES: real-time APT detection through correlation of suspicious information flows.” Proceedings of the IEEE Symposium on Security and Privacy, 1137–1152.
18. Ohm, M., Plate, H., Sykosch, A. y Meier, M. (2020). “Backstabber's knife collection: a review of open source software supply chain attacks.” Detection of Intrusions and Malware, and Vulnerability Assessment (DIMVA), 23–43.