Finding weaknesses in networks using Greedy Randomized Adaptive Search Procedure

Abstract

En los últimos años, la relevancia de la ciberseguridad ha sido cada vez más evidente para las empresas e instituciones, así como para los usuarios finales. Por ello, es importante garantizar la robustez de una red. Con el objetivo de mejorar la seguridad de la red, es conveniente averiguar cuáles son los nodos críticos de la infraestructura, para protegerlos de atacantes externos. Este trabajo aborda este problema, denominado problema α-separador, desde una perspectiva heurística, proponiendo un algoritmo basado en el Procedimiento de Búsqueda Adaptativa Aleatoria Greedy (GRASP). En particular, se propone un enfoque novedoso para el procedimiento constructivo, en el que se utilizan métricas de centralidad derivadas del análisis de redes sociales como criterio voraz. Además, se mejora la calidad de las soluciones proporcionadas mediante un método de combinación basado en Path Relinking (PR). Este trabajo explora diferentes variantes de PR, adaptando también la más reciente, Exterior PR, para el problema considerado. La combinación de GRASP + PR permite al algoritmo obtener soluciones de alta calidad en un tiempo de computación razonable. La propuesta se apoya en un conjunto de experimentos computacionales intensivos que muestran la calidad de la propuesta, comparándola con el algoritmo más competitivo encontrado en el estado del arte.