Los grafos no solo permiten representar relaciones entre elementos dentro de un sistema, sino también realizar diferentes operaciones que facilitan el análisis de redes complejas. Estas operaciones incluyen recorridos dentro del grafo, búsqueda de rutas entre nodos, identificación de caminos óptimos y análisis de estructuras críticas dentro de una red.

Estas técnicas son fundamentales para analizar el comportamiento de redes informáticas, detectar vulnerabilidades y comprender cómo podría propagarse un ataque dentro de una infraestructura tecnológica. Los algoritmos de grafos permiten estudiar rutas de comunicación, identificar nodos críticos y determinar caminos mínimos entre sistemas conectados.

Los recorridos en grafos son algoritmos diseñados para visitar sistemáticamente todos los nodos o vértices de un grafo siguiendo determinadas reglas de exploración. Su objetivo principal es analizar la estructura del grafo y comprender las relaciones existentes entre los diferentes elementos que lo conforman. Estos algoritmos son esenciales dentro del estudio de la teoría de grafos y tienen aplicaciones en diversas áreas de la informática, como la inteligencia artificial, el análisis de redes y la optimización de rutas.

Los recorridos permiten modelar y analizar la forma en que un atacante podría desplazarse dentro de una infraestructura tecnológica. Mediante estos métodos es posible identificar rutas potenciales hacia sistemas críticos, detectar puntos vulnerables dentro de la red o estudiar la propagación de malware entre dispositivos interconectados. Los dos métodos de recorrido más utilizados son la Búsqueda en Profundidad (DFS) y la Búsqueda en Anchura (BFS), los cuales exploran los nodos del grafo siguiendo estrategias distintas pero complementarias. (Cormen et al., 2016).

6.1.1. Búsqueda en profundidad (DFS)

Algoritmo de recorrido de grafos que explora los nodos siguiendo cada rama del grafo hasta llegar lo más lejos posible antes de retroceder. Prioriza la exploración profunda de los caminos disponibles, lo que permite analizar detalladamente cada posible ruta dentro de la estructura del grafo. DFS permite recorrer sistemáticamente todos los vértices de un grafo explorando cada camino antes de considerar alternativas. Se inicia en la raíz y continúa avanzando hacia uno de sus nodos vecinos que aún no haya sido visitado. Este proceso se repite sucesivamente hasta que se alcanza un nodo desde el cual ya no es posible continuar avanzando. En ese momento, el algoritmo retrocede al nodo anterior para explorar otras ramas que aún no hayan sido recorridas. La Figura 1 muestra el paso a paso del funcionamiento del algoritmo de búsqueda en profundidad.

Este tipo de recorrido es útil para analizar rutas completas dentro de una red, detectar ciclos y explorar estructuras jerárquicas. DFS puede emplearse para simular cómo un atacante podría desplazarse dentro de una red informática comprometiendo diferentes sistemas de manera progresiva, lo que permite identificar posibles caminos de intrusión y puntos vulnerables en la infraestructura tecnológica (Cormen et al., 2016).

Ejemplo en Python:

grafo = {
"Internet": ["Firewall"],
"Firewall": ["ServidorWeb"],
"ServidorWeb": ["BaseDatos"],
"BaseDatos": []
}

def dfs(nodo, visitados):
if nodo not in visitados:
print(nodo)
visitados.add(nodo)
for vecino in grafo[nodo]:
dfs(vecino, visitados)

dfs("Internet", set())

6.1.2. Búsqueda en anchura (BFS)

Algoritmo de recorrido de grafos que explora los nodos de manera progresiva por niveles. A diferencia de otros métodos que profundizan en una sola ruta, BFS visita primero todos los nodos vecinos del nodo inicial antes de avanzar hacia niveles más profundos del grafo. Este enfoque permite analizar la estructura de la red de forma ordenada, comenzando desde el nodo de origen y expandiéndose gradualmente hacia los demás nodos conectados.

Funciona utilizando una cola para almacenar los nodos que están pendientes de ser explorados. Inicialmente se coloca el nodo de partida en la cola y, a medida que se visitan los nodos, sus vecinos no visitados se agregan a la cola para ser procesados posteriormente. Esto garantiza que los nodos se recorran en orden de proximidad al nodo inicial. Útil para analizar grafos cuando se requiere identificar caminos mínimos o explorar estructuras organizadas por niveles. (Cormen et al., 2016)

En la figura 2 se presenta un ejemplo de búsqueda en anchura junto con su cola.

Entre sus principales aplicaciones están calcular la distancia mínima entre nodos, analizar redes por niveles y estudiar la propagación de información o malware en sistemas interconectados. BFS puede emplearse para modelar cómo un ataque informático o un malware podría propagarse dentro de una red desde un punto inicial, permitiendo identificar rápidamente qué sistemas podrían verse afectados primero y cuáles serían los siguientes en la cadena de propagación (Cormen et al., 2016).

Ejemplo en Python:

from collections import deque

 

def bfs(grafo, nodo_inicio):

visitados = set()

cola = deque([nodo_inicio])

visitados.add(nodo_inicio)

while cola:

nodo_actual = cola.popleft()

print(f"Visitando nodo: {nodo_actual}")

for vecino in grafo[nodo_actual]:

if vecino not in visitados:

visitados.add(vecino)

cola.append(vecino)

 

mi_grafo = {

'A': ['B', 'C'],

'B': ['A', 'D', 'E'],

'C': ['A', 'F'],

'D': ['B'],

'E': ['B', 'F'],

'F': ['C', 'E']

}

 

bfs(mi_grafo, 'A')

6.1.3. Comparación DFS vs BFS

DFS y BFS permiten recorrer un grafo visitando todos sus nodos, pero difieren en la forma en que exploran la estructura del grafo y en las aplicaciones para las que resultan más adecuados. Estos algoritmos representan dos estrategias distintas para explorar grafos: una que profundiza en cada camino antes de retroceder y otra que avanza nivel por nivel. (Bhargava, 2017)

DFS explora el grafo siguiendo una rama hasta llegar al punto más profundo posible antes de regresar para explorar otras rutas. Generalmente se implementa mediante recursión o utilizando una pila, lo que la hace útil para analizar rutas complejas, detectar ciclos o explorar completamente todas las posibles conexiones entre nodos. BFS recorre el grafo por niveles, visitando primero todos los nodos vecinos antes de avanzar a niveles más profundos, este algoritmo utiliza una cola para gestionar los nodos pendientes de explorar, lo que permite encontrar de manera eficiente la distancia mínima entre nodos en un grafo no ponderado. La Tabla 1 muestra la comparación entre los algoritmos DFS y BFS.

En redes, BFS suele emplearse para encontrar rutas más cortas entre nodos, por ejemplo, en protocolos de enrutamiento o análisis de conectividad. DFS es más útil cuando se requiere explorar completamente todas las rutas posibles dentro de un sistema, lo que puede ayudar a comprender la estructura completa de una red o detectar posibles caminos de acceso dentro de un análisis de seguridad informática (Bhargava, 2017).

6.1.4. Uso de recorridos en análisis de propagación de ataques

Los algoritmos de recorrido permiten analizar cómo un ataque podría propagarse dentro de una infraestructura tecnológica. Por ejemplo, si un atacante compromete una computadora dentro de una red, podría intentar acceder a otros sistemas conectados.

La Figura 3 muestra un ejemplo de cómo los grafos permiten representar relaciones entre componentes de una red.

Mediante algoritmos de recorrido es posible:

Simular ataques

Analizar rutas de propagación de malware

Identificar puntos críticos de acceso

Diseñar estrategias de defensa

Estas técnicas también se utilizan en herramientas de análisis de seguridad para evaluar la superficie de ataque de una organización.

6.1.5. Recursividad implícita en recorridos

Muchos algoritmos de recorrido de grafos utilizan recursividad, especialmente en el caso de DFS. La recursividad es una técnica de programación en la que una función se llama a sí misma para resolver un problema dividiéndolo en subproblemas más pequeños. En grafos, este enfoque permite que el algoritmo visite un nodo y, posteriormente, llame nuevamente a la misma función para explorar cada uno de sus nodos vecinos que aún no han sido visitados. La Figura 4 muestra un ejemplo de código de recursividad para calcular el factorial de un número.

Este mecanismo facilita avanzar de forma natural por cada rama del grafo hasta llegar a un punto donde ya no existan más nodos por explorar, momento en el cual la función retorna al nivel anterior para continuar con otras rutas. Gracias a esto, la recursividad simplifica la implementación de algoritmos como DFS, haciendo que el código sea más claro, organizado y fácil de comprender.

Ejemplo simple:

def dfs(nodo, visitados):
visitados.add(nodo)
print(nodo)

for vecino in grafo[nodo]:
if vecino not in visitados:
dfs(vecino, visitados)

Además de los recorridos básicos, existen otros que permiten analizar grafos de manera más profunda.

Estos algoritmos permiten:

encontrar rutas óptimas

analizar costos de conexión

identificar caminos críticos

optimizar infraestructuras de red

Uno de los problemas más importantes en grafos es el problema de caminos mínimos.

6.2.1. Caminos mínimos

El problema de caminos mínimos consiste en encontrar la ruta más corta entre dos nodos dentro de un grafo. Este permite determinar la mejor forma de desplazarse entre distintos puntos dentro de una red. Los algoritmos de caminos mínimos buscan minimizar el costo total de un recorrido considerando los pesos asociados a las aristas del grafo (Cormen et al., 2016).

En grafos ponderados, cada conexión o arista posee un valor numérico denominado peso, el cual puede representar diferentes variables dependiendo del problema que se esté analizando, tales como:

• distancia
• tiempo
• costo
• nivel de riesgo

La Figura 6 muestra un ejemplo de recorridos mínimos.

En redes, este problema puede aplicarse para identificar la ruta más eficiente para transmitir información entre dispositivos conectados. Puede utilizarse para determinar la ruta más rápida para enviar datos, el camino con menor latencia dentro de una red o el trayecto más probable de propagación de un ataque o malware dentro de una infraestructura tecnológica. Estos análisis permiten optimizar el funcionamiento de la red y mejorar las estrategias de seguridad informática.

6.2.2. Algoritmo de Dijkstra

Uno de los métodos más conocidos y utilizados para encontrar el camino mínimo entre nodos en un grafo ponderado, siempre que los pesos de las aristas sean no negativos, Este algoritmo permite determinar la distancia mínima desde un nodo origen hacia todos los demás nodos del grafo (Cormen et al., 2016).

Dijkstra consiste en seleccionar en cada paso el nodo cuya distancia mínima desde el nodo inicial ya es conocida. Una vez seleccionado, se actualiza las distancias hacia sus nodos vecinos, verificando si existe un camino más corto a través de ese nodo. Si se encuentra una ruta más eficiente, se actualiza el valor de la distancia almacenada. Este proceso se repite de manera repetitiva hasta que todos los nodos han sido evaluados o hasta que se ha encontrado la ruta más corta hacia el nodo destino. Debido a su eficiencia, Dijkstra es ampliamente utilizado en sistemas de navegación, protocolos de enrutamiento de redes y análisis de infraestructuras informáticas.

La Figura 6 muestra un ejemplo de algoritmo de Dijkstra con la distancia mínima desde la raíz.

Ejemplo en Python:

import heapq

grafo = {
"Internet": [("Firewall",3)],
"Firewall": [("ServidorWeb",2)],
"ServidorWeb": [("ServidorApp",2)],
"ServidorApp": [("BaseDatos",4)],
"BaseDatos": []
}

def dijkstra(inicio):
distancias = {nodo: float("inf") for nodo in grafo}
distancias[inicio] = 0
cola = [(0,inicio)]

while cola:
distancia_actual, nodo = heapq.heappop(cola)

for vecino, peso in grafo[nodo]:
distancia = distancia_actual + peso
if distancia < distancias[vecino]:
distancias[vecino] = distancia
heapq.heappush(cola,(distancia,vecino))

return distancias

print(dijkstra("Internet"))

6.2.3. Análisis de rutas críticas

Consiste en identificar los caminos más importantes o influyentes dentro de una red, sistema o estructura representada mediante grafos. Estas rutas corresponden a secuencias de nodos y conexiones que tienen un impacto significativo en el funcionamiento del sistema, ya que concentran flujos de información, dependencias operativas o puntos clave de acceso. El análisis de caminos dentro de grafos permite comprender cómo se relacionan los componentes de una red y detectar rutas que influyen de manera determinante en su comportamiento (Kleinberg & Tardos, 2006).

El análisis de rutas críticas resulta útil para identificar posibles vectores de ataque o dependencias que podrían comprometer la estabilidad de un sistema. Estas rutas pueden representar:

• Caminos de acceso a sistemas sensibles.
• Dependencias entre servicios, donde la falla o compromiso de un componente afecta a otros.
• Posibles rutas de ataque.

La identificación de estas rutas permite a los especialistas priorizar las medidas de protección, concentrando los controles y mecanismos de defensa en los puntos más vulnerables o estratégicos de la red.

6.2.4. Optimización de recorridos

La optimización de recorridos busca mejorar la eficiencia al explorar un grafo.

Esto puede implicar:

reducir el tiempo de búsqueda

minimizar el costo de una ruta

limitar la exploración de nodos innecesarios

Estas optimizaciones son importantes en sistemas que analizan grandes redes, como:

sistemas de monitoreo de tráfico

análisis de redes sociales

plataformas de ciberseguridad

6.2.5. Aplicaciones en análisis de infraestructuras comprometidas

Hay múltiples aplicaciones en ciberseguridad, ya que permiten representar y estudiar las relaciones entre los distintos dispositivos, servicios y sistemas que forman parte de una infraestructura tecnológica.

Mediante el uso de grafos, los analistas pueden modelar una red como un conjunto de nodos conectados por aristas que representan las comunicaciones o dependencias entre ellos. Los algoritmos de grafos permiten analizar estructuras complejas de redes e identificar patrones de conexión relevantes para la toma de decisiones (Kleinberg & Tardos, 2006).

Entre las aplicaciones más importantes se encuentran:

• Análisis de movimiento lateral de atacantes, que permite estudiar cómo un intruso podría desplazarse entre distintos sistemas dentro de una red.
• Detección de rutas de propagación de malware, identificando los posibles caminos que podría seguir para infectar otros dispositivos.
• Identificación de nodos críticos dentro de una red.
• Análisis de vulnerabilidades en infraestructuras tecnológicas, permitiendo detectar puntos débiles o rutas potenciales de explotación.

Así, los especialistas pueden comprender mejor el comportamiento de una red, anticipar posibles escenarios de ataque y diseñar estrategias más efectivas para proteger los sistemas informáticos.