Resumo Técnico: Alocação de Segurança Baseada na Centralidade de Katz em Redes Positivas

Formulação do Problema

Este artigo aborda o desafio da alocação de segurança para sistemas de controle de rede positivos (NCS) representados por grafos direcionados (digrafos) com pesos positivos sob ataques furtivos de injeção de dados falsos (FDI). O sistema consiste em subsistemas interconectados unidimensionais (nós) onde as variáveis de estado são restritas a valores não negativos, refletindo aplicações do mundo real, como redes de transporte e de distribuição de água.

O cenário envolve dois agentes opostos:

1. O Adversário: Seleciona um conjunto específico de $\alpha$ nós para injetar sinais de FDI aditivos e não negativos nas informações transmitidas aos seus vizinhos. O adversário visa maximizar a perda de desempenho da rede (definida como a norma $L_2$ do vetor de estado ponderado) enquanto permanece furtivo. A furtividade é definida pela condição de que a energia na saída nos nós monitorados não exceda um limiar de alarme predefinido.
2. O Defensor: Seleciona um conjunto de no máximo $\beta$ nós para monitorar. O objetivo do defensor é minimizar a pior perda de desempenho da rede causada pelo adversário, sujeito às restrições de furtividade.

Os problemas centrais de pesquisa são:

• Problema 1 (Avaliação Escalável): Calcular a interrupção máxima (métrica de segurança) de maneira independente do tamanho da rede.
• Problema 2 (Seleção Ótima): Selecionar graficamente um conjunto de monitoramento para um cenário de ataque fixo para minimizar a pior interrupção.
• Problema 3 (Seleção Robusta): Selecionar graficamente um conjunto de monitoramento que seja robusto contra todos os cenários de ataque admissíveis.

Metodologia

Os autores utilizam a positividade da dinâmica do sistema e a teoria dos sistemas dissipativos para transformar o problema de avaliação de segurança não convexo em um framework de otimização tratável.

1. Limite Superior SDP: Inicialmente, mostra-se que a pior interrupção é limitada superiormente por um problema de Programação Semidefinida (SDP) derivado de uma função de armazenamento e taxa de suprimento. No entanto, este SDP padrão envolve uma variável de matriz de tamanho $N \times N$ (onde $N$ é o tamanho da rede), levando a uma complexidade computacional de escala $O(N^6)$, o que é intratável para redes grandes.
2. Computação Exata via Condição de Robustez: Ao introduzir uma condição de robustez suficiente (relacionando a pior interrupção sem monitores com os limiares de alarme e pesos de desempenho), os autores provam que a solução do SDP torna-se exata e simplifica-se significativamente. Sob esta condição, a variável de matriz $P$ pode ser restrita a ser uma matriz diagonal não negativa.
3. Conexão com a Centralidade de Katz: O SDP simplificado é ainda reduzido a uma formulação independente do tamanho da rede $N$. Este problema reduzido estabelece uma relação direta entre a métrica de segurança e duas medidas de centralidade de Katz adaptadas:
   • Centralidade de Katz de Monitoramento ($K_\delta$): Incorpora limiares de alarme.
   • Centralidade de Katz de Desempenho ($K_W$): Incorpora fatores de ponderação de desempenho.
     A métrica de segurança é caracterizada pela relação geométrica entre um elipsoide representando o impacto do ataque (derivado de $K_W$) e um elipsoide representando a cobertura do monitor (derivado de $K_\delta$).
4. Heurística Geométrica: Com base na interpretação geométrica do SDP simplificado, os autores propõem uma heurística de direção principal (Algoritmo 1). Este algoritmo:
   • Calcula os autovalores/autovetores da matriz de impacto do ataque.
   • Calcula uma pontuação para cada nó baseada em quão bem sua "direção de crescimento" (derivada de $K_\delta$) se alinha com os eixos principais do elipsoide de impacto do ataque.
   • Seleciona nós de monitoramento com as maiores pontuações para cobrir as direções de ataque, garantindo que a condição de posto necessária para uma solução finita seja atendida.

Principais Contribuições

O artigo apresenta as seguintes contribuições específicas:

• Limite Superior Tratável: Demonstra que a pior perda de desempenho da rede sob ataques furtivos é limitada superiormente por um problema SDP tratável usando a teoria de sistemas dissipativos.
• Independência do Tamanho da Rede: Estabelece que, sob uma condição de robustez suficiente, a pior interrupção é igual à solução de um SDP simplificado que é independente do tamanho da rede $N$. Isso é alcançado ao provar que a solução de matriz ótima $P$ é diagonal.
• Caracterização Geométrica: Fornece uma condição geométrica necessária e suficiente para a existência de uma solução finita, vinculando o problema a duas versões adaptadas da medida de centralidade de Katz. Isso revela que a métrica de segurança depende do alinhamento entre as direções de ataque e as direções de crescimento induzidas pelo monitor.
• Algoritmo de Busca Heurística: Desenvolve um algoritmo de busca heurística baseado nas medidas de centralidade de Katz para selecionar subconjuntos de nós de monitoramento. Esta abordagem evita a necessidade de resolver problemas complexos de otimização de números inteiros mistos, tornando-a escalável para redes de grande escala.

Resultados

Os métodos propostos foram validados através de extensas simulações em grafos aleatórios de Erdős–Rényi com variados tamanhos de rede ($N=100$ a $200$ para avaliação, $N=20$ a $30$ para alocação devido ao custo computacional da comparação com o baseline).

• Validação do Teorema 1: Simulações confirmaram que, sob a condição de robustez suficiente, o SDP diagonal simplificado e a formulação não-P produzem valores quase idênticos ao SDP completo (diferenças relativas $< 4 \times 10^{-5}\%$). Mesmo quando a condição não se mantém estritamente, as formulações simplificadas fornecem limites superiores e inferiores significativos com uma razão consistentemente próxima de 1.
• Tempo de Computação: As formulações simplificadas (diagonal e não-P) demonstraram tempos de computação significativamente menores em comparação ao SDP completo, confirmando sua escalabilidade.
• Desempenho do Algoritmo: O conjunto de monitoramento heurístico ($M^*_{Katz}$) alcançou uma interrupção máxima comparável ao conjunto ótimo com restrição de orçamento ($M^*_{MISDP}$) obtido via SDP de números inteiros mistos. Na maioria dos casos, a heurística exigiu apenas um nó de monitoramento adicional além do orçamento $\beta$ para satisfazer a condição de posto (Teorema 2), resultando em uma razão de desempenho ($\rho_Q$) próxima de zero.

Significância e Alegações

O artigo afirma oferecer insights práticos para salvaguardar sistemas de controle de rede de grande escala contra ataques furtivos de injeção de dados falsos. Sua significância reside na:

• Escalabilidade: Afastando-se de formulações de SDP de números inteiros mistos NP-difíceis e complexidade $O(N^6)$ para heurísticas baseadas em teoria dos grafos que escalam com o tamanho da rede.
• Interpretabilidade: Fornecendo uma interpretação clara da métrica de segurança através da centralidade de Katz, vinculando a dinâmica do sistema, a topologia da rede e os parâmetros de segurança.
• Viabilidade: Oferecendo um método para identificar conjuntos de ataque "vulneráveis" e nós de monitoramento "eficazes" sem resolver problemas de otimização complexos, permitindo assim a avaliação de segurança e a alocação de recursos em redes positivas de grande escala onde métodos anteriores eram computacionalmente proibitivos.

Os autores observam que, embora a heurística não garanta o conjunto de monitoramento absolutamente ótimo, ela fornece um conjunto candidato viável que frequentemente supera o conjunto ótimo com restrição de orçamento ao relaxar levemente a restrição de orçamento para garantir a viabilidade (interrupção finita).