Hidden Connectivity in Networks with Vulnerable Classes of Nodes

In many complex systems representable as networks, nodes can be separated into different classes. Often these classes can be linked to a mutually shared vulnerability. Shared vulnerabilities may be due to a shared eavesdropper or correlated failures. In this paper, we show the impact of shared vulnerabilities on robust connectivity and how the heterogeneity of node classes can be exploited to maintain functionality by utilizing multiple paths. Percolation is the field of statistical physics that is generally used to analyze connectivity in complex networks, but in its existing forms, it cannot treat the heterogeneity of multiple vulnerable classes. To analyze the connectivity under these constraints, we describe each class as a color and develop a “color-avoiding” percolation. We present an analytic theory for random networks and a numerical algorithm for all networks, with which we can determine which nodes are color-avoiding connected and whether the maximal set percolates in the system. We find that the interaction of topology and color distribution implies a rich critical behavior, with critical values and critical exponents depending both on the topology and on the color distribution. Applying our physics-based theory to the Internet, we show how color-avoiding percolation can be used as the basis for new topologically aware secure communication protocols. Beyond applications to cybersecurity, our framework reveals a new layer of hidden structure in a wide range of natural and technological systems.

Popular Summary

When assessing the security or robustness of a complex network, it is essential to take into account the fact that many nodes may fail together. For example, businesses within the same geographic area are subject to the same weather events, and computers running the same version of software may be subject to the same security vulnerabilities. Ignoring this heterogeneity of vulnerabilities leads to substantial overestimation of robustness, with potentially catastrophic consequences. Here, we develop a method to analyze this heterogeneity and show how it can be used to improve a system’s functionality.

We color each node by its vulnerability and develop a “color-avoiding” percolation theory that allows us to determine the set of nodes that are connected while avoiding any single color. We apply our framework by proposing a new topological approach to cybersecurity, and we make use of data collected from the autonomous systems-level Internet. If there are entities that control many nodes or software bugs that affect many nodes, eavesdroppers to large sets of nodes may exist. In such a case, we propose splitting the message and transmitting each piece on a path that avoids all of the nodes that are vulnerable to one of the eavesdroppers. Our theory determines which nodes can securely communicate and which paths they should take. Our investigation is the first systematic study of the effect of vulnerability classes on robustness and security.

We expect that our findings will open up a new frontier in the study of complex systems with important practical applications to cybersecurity as well as network robustness.

Figure 1

Avoidable and nonavoidable adversaries. In this scenario, the sender must transmit their message through nodes that are controlled by either Lancaster (red rose) or York (white rose). In diagram (a), a message can be split in two and transmitted on two different paths: The upper path avoids York’s nodes, while the lower path avoids Lancaster’s nodes. In diagram (b), both of the paths pass through York’s nodes, and York cannot be avoided. Lancaster and York were opponents in the Wars of the Roses in England in the 15th century. Artwork after Ref. [7].

Figure 2

Illustration of color-avoiding connectivity. (a) In this network, the sender S and the receiver R are color-avoiding connected (CAC), as the green path avoids blue nodes, the purple path avoids white nodes, and the yellow path avoids black nodes. (b) Finding ${\mathcal{L}}_{\text{color}}$, the largest color-avoiding connected component. (b1) The largest component without white nodes (${\mathcal{L}}_{\overline{\mathrm{white}}}$) and its direct white neighbors (links to white neighbors are dashed) form ${\mathcal{L}}_{\overline{\mathrm{white}}}^{+}$. Each pair of nodes in this component (${\mathcal{L}}_{\overline{\mathrm{white}}}^{+}$) can communicate, avoiding white nodes on the path between sender and receiver. We repeat the process in (b2) for blue and in (b3) for black nodes. (b4) Nodes that belong to all three components (in red) constitute the largest CAC component, ${\mathcal{L}}_{\text{color}}$. Note that some nodes are not CAC but are necessary to form the largest color-avoiding component, for example, node A. This node is not in ${\mathcal{L}}_{\overline{\mathrm{black}}}^{+}$ [see (b3)]. However, it is still required to form a path avoiding blue nodes between nodes S and R [see (a)]. (c) Total CAC pairs $p_{\mathrm{pair}}$ compared to the size of the giant CAC component ($S_{\text{color}}$) for quenched graphs. Red squares show Poisson graphs with $N=10^5$ nodes, average degrees $\overline{k}=1.6$, 1.7, 1.9, 4.0 (from left to right) and $C=3$ colors; the green circle shows the AS-level Internet [34, 35], with colors representing countries as described in Fig. 4. The black line $S_{\text{color}}^2=p_{\mathrm{pair}}$ represents all CAC occurring within the giant CAC component. Note that $p_{\mathrm{pair}}$ was approximated with samples of up to $5\times 10^5$ pairs; error bars are smaller than the visible range.

Figure 3

Size of the giant color-avoiding component $S_{\text{color}}$ in random networks with uniformly distributed colors. We show the dependence of $S_{\text{color}}$ on average degree $\overline{k}$ (a) for Erdős-Rényi networks and (b) scale-free networks with different numbers of colors. Standard-deviation error bars are shown but barely visible for networks of size $N=10^6$. The blue lines show the corresponding analytical results. For comparison, we include the giant component size of standard percolation $S$ (black solid line) and the limiting case of a system with an infinite number of colors, $S_{\text{color},\infty }$ (black dashed line). As mentioned in the text, $S_{\text{color},\infty }$ is the same as the giant component in two-core percolation. (c) Critical exponent and finite-size scaling for Erdős-Rényi networks with $C=3$. Note that in the critical region, the theory and simulations show a slope of almost exactly 3 as predicted by Eq. (8). Finite-size scaling is shown, with results of $>150$ realizations per size plotted individually and averaged.

Figure 4

Color-avoiding connectivity of the AS-level Internet. (a) Here, we show the routers of the AS-level Internet in the Iberian peninsula as a disjointly vulnerable network, with the colors determined by the country to which the router is registered. (b) The green nodes are members of this set, while the red are not. This means that these routers can take advantage of multiple paths to maintain security, as described in the main text. Panel (c) shows the number of CAC routers (nodes in $L_{\text{color}}$) compared to the total number of routers for the top 20 countries worldwide, in terms of total number of AS routers registered to that country in ${\mathcal{L}}_{\text{color}}$. Data for the USA have been truncated for visibility; the total number of AS routers is 17 690. We use a symmetrized version of the network of Ref. [34], which was generated using data from the CAIDA project [35] up to December 2013.

Figure 5

Details for the AS-level Internet. (a) For comparing with theoretical results $S_{\text{color}}=|{\mathcal{L}}_{\text{color}}|/N$ (black line), we calculate shares $|{\mathcal{L}}_{\text{color}}\cap \{c_i=c\}|/|\{c_i=c\}|$ for 20 countries with the most AS. Here, $\{c_i=c\}$ is the set of all AS assigned to country $c$, and $||$ is the number of nodes in a set or component. Results are shown with black bars and compare well with theoretical results for the group of eleven countries shown to the left of the vertical dashed line. To understand why color connectivity breaks down for the other countries, we also plot the shares of two-core AS in the respective countries (white bars). The fraction $|{\mathcal{L}}_{\overline{c}}^{+}\cap \{c_i=c\}|/|\{c_i=c\}|$ (shown with red bars) is the fraction of AS in a country $c$ which can communicate while avoiding further AS of that country $c$. The fraction $|{\mathcal{L}}_{c=\overline{\mathrm{U}}\mathrm{SA}}^{+}\cap \{c_i=c\}|/|\{c_i=c\}|$ (shown with cyan bars) is the fraction of AS in a country $c$ which can communicate while avoiding AS registered to the USA. Color-avoiding connectivity when sender and receiver colors are trusted: (b) The fraction of nodes of row color that are in the largest CAC component when trusting all nodes of row color and column color. The value indicates the probability that a node of color $i$ can communicate with the largest CAC set of nodes of color $j$. In panel (c), we show the relative improvement compared to not trusting the sender-receiver colors. For USA nodes, this makes them 4 times more likely to be color-avoiding connected, while for most countries, it makes a less substantial difference, unless they are communicating with the USA.

Figure 6

Variety of color-avoiding components. Color-avoiding components may overlap, as shown in diagrams (b) and (c). Color-avoiding components can assume diverse forms. In a chain (a), paths between nodes of one color exist and can be reached by connections between nodes of different colors. In diagram (b), the black node serves as an alternative path provider for the blue nodes. Graph (d) does not need any connection among nodes of the same color, but there is a massive overhead of nodes and connections to achieve color-avoiding connectivity of the blue nodes. Graph (e) shows that a clique is a color-avoiding component.

Figure 7

We base our theory on the method to calculate the size of normal giant components, as illustrated in this figure. Using a self-consistency equation, the probability $u$ can be calculated. This is the probability that a node is not connected to the giant component over a single link (see top). On the bottom, the probability for a node with $k$ links is illustrated to have at least one link connecting to the giant component. Note that $u^k$ is the probability that all links fail.

Figure 8

We have to calculate the probability, if a node with $k$ links is, for every color $c$, connected to the giant component ${\mathcal{L}}_{\overline{c}}$ with deleted color $c$. All connections over at least one link have to exist at the same time. We illustrate this question with red ($c=\mathrm{r}$), green ($c=\mathrm{g}$), and blue ($c=\mathrm{b}$). If a link connects to $\mathcal{L}$${\mathcal{L}}_{\overline{\mathrm{g}}}$, it definitely does not connect to ${\mathcal{L}}_{\overline{c}}$ for one of the other colors. This kind of dependence forces us to use a stepwise calculation with conditional probabilities.

Figure 9

Probabilities for a single link to connect to different parts of the network. We use these probabilities as primitives to calculate the probability for many links. While $u$, $r_c$, and $u_{\overline{c}}$ can be calculated with standard methods invented for the configuration model, the conditional probability $U_{\overline{c}}$ can be calculated as a combination of the others.

Figure 10

Calculation of $U_{\overline{\mathrm{g}}}$ using the equality $(1-u)(1-r_{\mathrm{g}})(1-U_{\overline{\mathrm{g}}})=1-u_{\overline{\mathrm{g}}}$. For this calculation, we have assumed independence of the qualities of the link under consideration, especially of the color it connects to and if it connects to the giant component.

Figure 11

For calculating the probability of a node with $k$ links to belong to ${\mathcal{L}}_{\text{color}}$, we have to average over different link constellations that this node might show. First, $B_{k,k^{\prime }}$ is the probability that, out of the $k$ links, $k^{\prime }$ connect to the giant component. It is calculated using $u$ (compare the left side of Fig. 9). Second, $M_{k^{\prime },\overrightarrow{\kappa }}$ gives the probability for a certain color distribution among the links. It is calculated using $r_{\mathrm{g}}$, etc. (compare Fig. 9, second from left). We assume that this second step is independent of the first step, which is confirmed with the final results. Third, $P_{\overrightarrow{\kappa }}$ gives the joint probability that for this color distribution, ${\mathcal{L}}_{\overline{\mathrm{r}}}$, ${\mathcal{L}}_{\overline{\mathrm{b}}}$, and ${\mathcal{L}}_{\overline{\mathrm{g}}}$ are connected at the same time. This is calculated using $U_{\overline{\mathrm{r}}}$, etc. (compare the right side of Fig. 9).