Tolerância a ataques

No contexto da ciência das redes, a tolerância a ataques está relacionada com a robustez da rede. Isso significa que, na medida em que alguns nós da rede estão sendo removidos, ela consegue manter a sua conectividade e o seu diâmetro entre os nós restantes. Caso a rede analisada seja em forma de estrela, por exemplo, quando ela sofrer algum ataque focado em nós com maior grau, ela pode ser “desconectada” totalmente arrancando somente 1 nó, mostrando que ela foi fragmentada, e que houve uma desconexão geral da rede. Esse exemplo pode ser visto na imagem ao lado. ^{[carece de fontes]}

Acima temos uma rede em forma de estrela sendo atacada. Depois que o nó maior é atingido, todos os outros nós foram desconectados.

Definição

Para abordar a tolerância a ataques das redes, são estudadas as mudanças no diâmetro ou a conexão da rede, enquanto uma fração $f$ (entre 0 e 1) de nós é removida. Isso quer dizer que, quanto maior for o valor de $f$, mais nós serão retirados na rede. Portanto, ao retirar ou danificar um nó, pode acarretar em um aumento da distância entre os nós restantes, pois durante essa ação, são eliminados alguns caminhos que contribuem para a conectividade interna da rede. Além disso, quando alguns nós são removidos da rede, “novos” clusters podem aparecer, pois os nós que ligavam esses clusters a um conjunto maior foram removidos, gerando assim uma fragmentação da rede.

Para uma melhor visualização dos dois efeitos, podemos olhar as duas imagens a seguir. A primeira mostra uma rede que se fragmenta quando é retirado o nó principal (nó de maior grau), que faz a ligação entre dois lados da rede. Depois de ser retirado, formam-se dois clusters. Já a outra imagem mostra o aumento do diâmetro da rede com a retirada de um nó.

Imagem demonstrando uma rede sendo fragmentada em dois clusters.

Imagem mostra uma rede que logo depois de uma retirada de um dos nós, o diâmetro da rede é aumentado.

Dois métodos mais comuns para atacar uma rede são:

• Aleatórios: Como o nome já diz, é um ataque onde se escolhe qualquer nó da rede para ser retirado.
• Nó mais importante: Esse tipo de ataque tenta priorizar os nós com maior grau (mais importantes para uma conexão) para ser retirado da rede, em alguns casos pode ser mais efetivo comparado com o ataque anterior.

Tipos de redes

Como foi dito na seção anterior, algumas redes se comportam diferente com um certo tipo de ataque. Portanto, a seguir serão mostrados alguns exemplos de redes e suas vulnerabilidades, todos os resultados estão mais detalhados no artigo citado.

Modelo livre de escala

No modelo livre de escala, a rede tem seus graus definidos pela lei da potência, isso significa que, nessa rede, a maioria dos nós tem graus baixos, e a minoria dos nós (hubs) possuem graus altos.

Analisando mudança de diâmetro

Para analisar o diâmetro foi utilizada uma rede livre de escala com 10000 (dez mil) nós e 20000 (vinte mil) ligações. Foi observado que, após a rede sofrer um ataque aleatório e perder 5% dos nós, o seu diâmetro não foi afetado, pois como a distribuição da lei da potência implica que a maioria dos nós possui apenas alguns links, isso faz com que nós com pequena conectividade sejam selecionados com uma probabilidade muito maior. Contudo, a remoção desses nós 'pequenos' não altera a estrutura do caminho dos nós restantes e, portanto, não tem impacto na topologia geral da rede.

Porém, quando a rede sofreu um ataque direcionado a nós com maior grau, a rede foi bastante danificada, pois, depois da retirada de 5% de nós, o diâmetro da rede aumentou tão rapidamente que chegou a ser duplicado. Isso se dá pelo fato da rede possuir poucos nós altamente conectados, cuja remoção altera drasticamente a topologia da rede e diminui a capacidade dos nós restantes de se comunicarem entre si.

Analisando desfragmentação da rede

Para esse teste foi observado o maior cluster de uma rede livre de escala, e quando ela foi atacada aleatoriamente por uma fração de $f$, o tamanho desse cluster diminui lentamente, pois a maioria dos nós possuem poucos links, que, caso retirados, não modificam tanto o tamanho do maior cluster.

Entretanto, nos testes em que a rede sofreu um ataque direcionado a nós com maior grau, os nós mais significativos eram os pilares do maior cluster, e quando retirados, fizeram com que a rede fosse fragmentada. Isso mostra que essa rede é mais prejudicada por ataques em nós com maior grau.

Limite crítico sob ataque

Nessa parte vamos analisar a fração crítica $f_{c}$ dessa rede. Para isso vamos analisar as duas consequências que acontecem nessa rede durante um ataque:

• O valor do limite crítico é $f_{c}$ < 1, indicando que sob ataques essa rede pode ser fragmentada pela remoção de uma fração finita de seus hubs.
• O $f_{c}$ observado é notavelmente baixo, indicando que precisamos remover apenas uma pequena fração dos hubs para paralisar a rede.

Portanto, para quantificar esse processo, precisamos calcular analiticamente $f_{c}$ para uma rede sob ataque. Para fazer isso, contamos com o fato de que a remoção de hubs altera a rede de duas maneiras:

• Ela altera o grau máximo da rede de $k_{max}$ para $k_{max}^{\prime }$, considerando que todos os nós com grau maior do que $k_{max}^{\prime }$ tenham sido removidos.
• O grau de distribuição da rede muda de $p_{k}$ para $p_{k^{\prime }}^{\prime }$ , à medida que os nós conectados aos hubs removidos perderão links, alterando os graus dos nós restantes.

Combinando as duas mudanças acima, podemos observar um ataque com remoção aleatória de nós dessa rede, com $k_{max}^{\prime }$ e $p_{k^{\prime }}^{\prime }$ ajustados. Os cálculos prevêem que o limite crítico $f_{c}$ para ataques em uma rede livre de escala é a solução da equação abaixo:

$f_{c}^{\left(2{\boldsymbol {-\gamma }}\right)/\left(1{\boldsymbol {-\gamma }}\right)}=2+{\frac {2{\boldsymbol {-\gamma }}}{3{\boldsymbol {-\gamma }}}}k_{min}\left(f_{c}^{\left(3{\boldsymbol {-\gamma }}\right)/\left(1{\boldsymbol {-\gamma }}\right)}-1\right)$

A equação acima mostra uma solução numérica em função do expoente de grau $\gamma$, permitindo-nos tirar várias conclusões a partir da equação encontrada:

• Enquanto $f_{c}$ para falhas diminui monotonicamente de acordo com o valor de $\gamma$, o valor de $f_{c}$ para ataques não possui o comportamento monotônico, levando em consideração que: o valor aumenta para um $\gamma$ pequeno e o valor diminui para um $\gamma$ grande.
• O valor de $f_{c}$ para ataques é sempre menor que o valor de $f_{c}$ para falhas aleatórias.
• Considerando um valor de $\gamma$ grande, uma rede livre de escala se comporta como uma rede aleatória. Como uma rede aleatória não possui hubs, isso significa que o impacto de um ataque direcionado é semelhante ao dano causado por um ataque de remoção aleatória. Além disso, a falha e os limiares de ataque convergem entre si quando se obtém um valor grande de $\gamma$. Portanto, se $\gamma \to \infty$ então $p_{k}\to \delta \left(k-k_{min}\right)$, o que significa que todos os nós têm o mesmo grau $k_{min}$. Portanto, falhas aleatórias e ataques direcionados tornam-se indistinguíveis no limite $\gamma \to \infty$, obtendo:

$f_{c}\to 1-{\frac {1}{k_{min}-1}}$

Modelo Erdős–Rényi

Este tipo de rede gerada pode ser considerada como homogênea. Isso significa que, a maioria dos nós possuem aproximadamente o mesmo número de ligações.

Analisando mudança de diâmetro

Para analisar o diâmetro foi utilizado uma rede homogênea com 10000 (dez mil) nós e 20000 (vinte mil) ligações. Foi observado que, para a rede exponencial, o diâmetro aumenta monotonicamente de acordo com que os nós são retirados (independentemente do tipo de ataque), portanto é cada vez mais difícil para os nós restantes se comunicarem entre si. Isso acontece pois todos os nós têm aproximadamente o mesmo número de links, todos contribuem igualmente para o diâmetro da rede, portanto, a remoção de cada nó causa a mesma quantidade de dano.

Analisando desfragmentação da rede

Como já foi dito acima, o tipo de ataque não importa para essa rede, pois a maioria dos nós possui o mesmo número de links. Portanto, para analisar este fato, foi calculado o tamanho do maior cluster de uma rede homogênea, e enquanto ela sofria um ataque, foi notado que enquanto alguns nós foram retirados, o tamanho do maior cluster ficava diminuindo, formando clusters isolados, fazendo com que a rede rapidamente seja fragmentada em vários clusters.

Limite crítico sob ataque

Considerando esse tipo de rede, podemos encontrar também o seu limite critico sob ataque $f_{c}$. O seu limite critico pode ser encontrado utilizando a fórmula abaixo, considerando que $Y=\left\langle k\right\rangle$ e $X=\left\langle k^{2}\right\rangle =\left\langle k\right\rangle (\left\langle k\right\rangle +1)$:

$f_{c}=1-{\frac {1}{{\frac {X}{Y}}-1}}=1-{\frac {1}{pN}}=1-{\frac {1}{Y}}$

Podemos notar através dessa fórmula que, quanto maior for o grau médio dos nós da rede, mais a rede está protegida por danos causados pelos ataques.

Paul Baran e a internet

Em 1959, Paul Baran, um jovem engenheiro da época, foi designado para desenvolver um sistema de comunicação que pudesse sobreviver a um ataque nuclear soviético. Como um ataque nuclear prejudica todo o equipamento dentro do alcance da detonação, Baran teve que projetar um sistema cujos usuários fora desse alcance não perdessem o contato uns com os outros. Ele descreveu a rede de comunicação de seu tempo como uma estrutura hierárquica de um conjunto de estrelas conectadas na forma de uma estrela maior, oferecendo uma descrição inicial do que chamamos hoje de rede sem escala. Ele concluiu que essa topologia é muito centralizada para ser viável sob ataque. Ele também descartou a topologia centralizada que é obviamente vulnerável, pois a destruição de um único nó central destrói a comunicação entre as estações finais.

Baran decidiu que a arquitetura de sobrevivência ideal era uma rede em malha distribuída. Esta rede é suficientemente redundante, de forma que mesmo se algum dos nós falhar, caminhos alternativos podem conectar os nós restantes. As ideias de Baran foram ignoradas pelos militares, então, quando a internet nasceu, uma década depois, ela dependia de protocolos distribuídos que permitiam que cada nó decidisse onde se conectar. Essa filosofia descentralizada pavimentou o caminho para o surgimento de uma internet sem escala, em vez da topologia em malha uniforme imaginada por Baran.