Resumen Técnico: Asignación de Seguridad Basada en la Centralidad de Katz en Redes Positivas

Formulación del Problema

Este artículo aborda el desafío de la asignación de seguridad para sistemas de control de redes positivas (NCS) representados por grafos dirigidos con pesos positivos bajo ataques de inyección de datos falsos (FDI) sigilosos. El sistema consiste en subsistemas interconectados de una dimensión (nodos) donde las variables de estado están restringidas a ser no negativas, lo que refleja aplicaciones del mundo real como las redes de transporte y de distribución de agua.

El escenario involucra a dos agentes opuestos:

1. El Adversario: Selecciona un conjunto específico de $\alpha$ nodos para inyectar señales de FDI aditivas y no negativas en la información transmitida a sus vecinos. El adversario busca maximizar la pérdida de rendimiento de la red (definida como la norma $L_2$ del vector de estado ponderado) mientras permanece sigiloso. La sigilosidad se define mediante la condición de que la energía de la salida en los nodos monitoreados no exceda un umbral de alarma predefinido.
2. El Defensor: Selecciona un conjunto de a lo sumo $\beta$ nodos para monitorear. El objetivo del defensor es minimizar la pérdida de rendimiento de la red en el peor de los casos causada por el adversario, sujeto a las restricciones de sigilosidad.

Los problemas centrales de investigación son:

• Problema 1 (Evaluación Escalable): Calcular la máxima perturbación (métrica de seguridad) de una manera independiente del tamaño de la red.
• Problema 2 (Selección Óptima): Seleccionar mediante teoría de grafos un conjunto de monitoreo para un escenario de ataque fijo para minimizar la máxima perturbación.
• Problema 3 (Selección Robusta): Seleccionar mediante teoría de grafos un conjunto de monitoreo que sea robusto contra todos los escenarios de ataque admisibles.

Metodología

Los autores aprovechan la positividad de la dinámica del sistema y la teoría de sistemas disipativos para transformar el problema de evaluación de seguridad no convexo en un marco de optimización tratable.

1. Cota Superior SDP: Inicialmente, se demuestra que la máxima perturbación está acotada superiormente por un problema de Programación Semidefinida (SDP) derivado de una función de almacenamiento y una tasa de suministro. Sin embargo, este SDP estándar involucra una variable matricial de tamaño $N \times N$ (donde $N$ es el tamaño de la red), lo que conduce a una complejidad computacional que escala como $O(N^6)$, resultando intratable para redes grandes.
2. Cálculo Exacto mediante la Condición de Robustez: Al introducir una condición de robustez suficiente (que relaciona la máxima perturbación sin monitores con los umbrales de alarma y los pesos de rendimiento), los autores demuestran que la solución del SDP se vuelve exacta y se simplifica significamente. Bajo esta condición, la variable matricial $P$ puede restringirse a ser una matriz diagonal no negativa.
3. Conexión con la Centralidad de Katz: El SDP simplificado se reduce aún más a una formulación independiente del tamaño de la red $N$. Este problema reducido establece una relación directa entre la métrica de seguridad y dos medidas de centralidad de Katz adaptadas:
   • Centralidad de Katz de Monitoreo ($K_\delta$): Incorpora los umbrales de alarma.
   • Centralidad de Katz de Rendimiento ($K_W$): Incorpora los factores de ponderación de rendimiento.
     La métrica de seguridad se caracteriza por la relación geométrica entre un elipsoide que representa el impacto del ataque (derivado de $K_W$) y un elipsoide que representa la cobertura del monitor (derivado de $K_\delta$).
4. Heurística Geométrica: Basándose en la interpretación geométrica del SDP simplificado, los autores proponen una heurística de dirección principal (Algoritmo 1). Este algoritmo:
   • Calcula los pares de autovalores de la matriz de impacto del ataque.
   • Calcula una puntuación para cada nodo basada en qué tan bien su "dirección de crecimiento" (derivada de $K_\delta$) se alinea con los ejes principales del elipsoide de impacto del ataque.
   • Selecciona los nodos de monitoreo con las puntuaciones más altas para cubrir las direcciones de ataque, asegurando que se cumpla la condición de rango necesaria para una solución finita.

Principales Contribuciones

El artículo realiza las siguientes contribuciones específicas:

• Cota Superior Tratable: Demuestra que la máxima pérdida de rendimiento de la red bajo ataques sigilosos está acotada superiormente por un problema SDP tratable utilizando la teoría de sistemas disipativos.
• Independencia del Tamaño de la Red: Establece que, bajo una condición de robustez suficiente, la máxima perturbación es igual a la solución de un SDP simplificado que es independiente del tamaño de la red $N$. Esto se logra demostrando que la matriz solución óptima $P$ es diagonal.
• Caracterización Geométrica: Proporciona una condición geométrica necesaria y suficiente para la existencia de una solución finita, vinculando el problema con dos versiones adaptadas de la medida de centralidad de Katz. Esto revela que la métrica de seguridad depende de la alineación entre las direcciones de ataque y las direcciones de crecimiento inducidas por el monitoreo.
• Algoritmo de Búsqueda Heurística: Desarrolla un algoritmo de búsqueda heurística (Algoritmo 1) basado en las medidas de centralidad de Katz para seleccionar subóptimos nodos de monitoreo. Este enfoque evita la necesidad de resolver problemas complejos de optimización de enteros mixtos, haciéndolo escalable para redes grandes.

Resultados

Los métodos propuestos fueron validados mediante extensas simulaciones en grafos aleatorios de Erdős–Rényi con diversos tamaños de red ($N=100$ a $200$ para la evaluación, $N=20$ a $30$ para la asignación debido al costo computacional de la comparación de referencia).

• Validación del Teorema 1: Las simulaciones confirmaron que, bajo la condición de robustez suficiente, el SDP diagonal simplificado y la formulación sin $P$ producen valores casi idénticos a la el SDP completo (diferencias relativas $< 4 \times 10^{-5}\%$). Incluso cuando la condición no se cumple estrictamente, las formulaciones simplificadas proporcionan cotas superiores e inferiores significativas con una razón consistentemente cercana a 1.
• Tiempo de Computación: Las formulaciones simplificadas (diagonal y sin $P$) demostraron tiempos de computación significativamente menores en comparación con el SDP completo, confirmando su escalabilidad.
• Desempeño del Algoritmo: El conjunto de monitoreo heurístico ($M^*_{Katz}$) logró una máxima perturbación comparable al conjunto óptimo con restricción de presupuesto ($M^*_{MISDP}$) obtenido mediante SDP de enteros mixtos. En la mayoría de los casos, la heurística requirió solo un nodo de monitoreo adicional más allá del presupuesto $\beta$ para satisfacer la condición de rango (Teorema 2), resultando en una razón de desempeño ($\rho_Q$) cercana a cero.

Significado y Pretensiones

El artículo afirma ofrecer perspectivas prácticas para salvaguardar los sistemas de control de redes a gran escala contra ataques de inyección de datos falsos sigilosos. Su importancia radica en:

• Escalabilidad: Pasar de formulaciones de SDP de enteros mixtos de difícil resolución (NP-hard) y complejidad $O(N^6)$ hacia heurísticas de teoría de grafos que escalan con el tamaño de la red.
• Interpretabilidad: Proporcionar una clara interpretación de la métrica de seguridad mediante la centralidad de Katz, vinculando la dinámica del sistema, la topología de la red y los parámetros de seguridad.
• Factibilidad: Ofrecer un método para identificar conjuntos de ataque "vulnerables" y nodos de monitoreo "efectivos" sin tener que resolver problemas de optimización complejos, permitiendo así la evaluación de seguridad y la asignación de recursos en redes positivas de gran escala donde los métodos anteriores eran computacionalmente prohibitivos.

Los autores señalan que, si bien la heurística no garantiza el conjunto de monitoreo absolutamente óptimo, proporciona un conjunto candidato factible que a menudo supera al conjunto óptimo con restricción de presupuesto al relajar ligeramente la restricción de presupuesto para asegurar la factibilidad (disrupción finita).