Exploits of multiple attributes

To tolerate exploits on multiple attributes, we need to construct cores such that, for subsets of attributes possessed by members of a core, there must be a core member that does not have these attributes. We call a $k$-resilient core $C$ a group of hosts in $\cal H$ such that, for every $k$ attributes of members of $C$, there is at least one host in $C$ that does not contain any of these attributes. In this terminology, the cores we have been considering up to this point have been $1$-resilient cores.

To illustrate this idea, consider the following example. Hosts run Windows, Linux, and Solaris as operating systems, and IIS, Apache, and Zeus as Web servers. An example of a $2$-resilient core is a subset composed of hosts $h_1, h_2, h_3$ with configurations: $h_1 = \{\mbox{Linux, Apache}\}$; $h_2 = \{\mbox{Windows, IIS}\}$; $h_3 = \{\mbox{Solaris, Zeus}\}$. In this core, for every pair of attributes, there is at least one host that contains none of them.

As before, every host $h$ builds a $k$-resilient core Core($h$). To build Core($h$), host $h$ uses the following heuristic:

Step 1

Select randomly $k-1$ hosts, $h_1$ through $h_{k-1}$, such that $h_i.\mbox{\emph{os}} \not= h.\mbox{\emph{os}}$, for every $i \in \{1, \ldots, k-1\}$;

Step 2

Use Uniform to search for a $1$-resilient core $C$ for $h$;

Step 3

For each $i \in \{1, \ldots, k-1\}$, use Uniform to search for a $1$-resilient core $C_i$ for $h_i$;

Step 4

$\mbox{\emph{Core}}(h) \leftarrow C\cup C_1 \cup \ldots \cup C_{k-1}$.

Intuitively, to form a $k$-resilient core we need to gather enough hosts such that we can split these hosts into $k$ subsets, where at least one subset is a $1$-resilient core. Moreover, if there are two of these subsets where, for each subset, all of the members of that subset share some attribute, then the shared attribute of one set must be different from the shared attribute of the other set. Our heuristic is conservative in searching independently for $1$-resilient cores because the problem does not require all such sets to be $1$-resilient cores. In doing so, we protect clients and at the same time avoid the complexity of optimally determining such sets. The sets output by the heuristic, however, may not be minimal, and therefore they are approximations of theoretical cores. We discuss this heuristic further in [13].

In Table 4, we show simulation results for this heuristic for $k=2$. The first column shows the values of load limit ($L$) used by the Uniform heuristic to compute cores. We chose values of $L \ge 5$ based on an argument generalized from the one given in Section 5.2 giving the lower bound of $L$ [13]. In the second and third columns, we present our measurements for coverage with standard error in parentheses. For each computed core Core$(h)$, we calculate the fraction of pairs of attributes such that at least one host $h^\prime \in$ Core$(h)$ contains none of attributes of the pair. We name this metric 2-coverage, and in the table we present the average across all hosts and across all eight runs of the simulator. 1-coverage is the same as the average coverage metric defined in Section 5.2. Finally, the last column shows average core size.

Table 4: Summary of simulation results for $k=2$ for $8$ different runs.

$L$	Avg. 2-coverage	Avg. 1-coverage	Avg. Core size
5	0.829 (0.002)	0.855 (0.002)	4.19 (0.004)
6	0.902 (0.002)	0.917 (0.002)	4.59 (0.005)
7	0.981 (0.001)	0.987 (0.001)	5.00 (0.005)
8	0.995 (0.0)	1.0 (0.0)	5.11 (0.005)
9	0.996 (0.0)	1.0 (0.0)	5.14 (0.005)
10	0.997 (0.0)	1.0 (0.0)	5.17 (0.003)

According to the coverage results, the heuristic does well in finding cores that protect hosts against potential pathogens that exploit vulnerabilities in at most two attributes. A beneficial side-effect of protecting against exploits on two attributes is that the amount of diversity in a $2$-resilient core permits better protection to its client against pathogens that exploit vulnerabilities on single attributes. For values of $L$ greater than seven, all clients have all their attributes covered (the average $1$-coverage metric is one and the standard error is zero).

Having a system that more broadly protects its hosts requires more resources: core sizes are larger to obtain sufficiently high degrees of coverage. Compared to the results in Section 5.2, we observe that we need to double the load limit to obtain similar values for coverage. This is not surprising. In our heuristic, for each host, we search for two $1$-resilient cores. We therefore need to roughly double the amount of resources used.

Of course, there is a limit to what can be done with informed replication. As $k$ increases, the demand on resources continues to grow, and a point will be reached in which there is not enough diversity to withstand an attack that targets $k+1$ attributes. Using our diversity study results in Table 2, if a worm were able to simultaneously infect machines that run one of the first four operating systems in this table, the worm could potentially infect $84\%$ of the population. The release of such a worm would most likely cause the Internet to collapse. An approach beyond informed replication would be needed to combat an act of cyberterrorism of this magnitude.