Emperical results: Worm vs Alert :Who wins control over a Large Scale Network

James Aspnes, Navin Rustagi, Jared Saia

We simulated the spread of a worm and an alert through a network to empirically determine the fraction of nodes saved. We performed our experiment using a random $d$ regular graph as the overlay network and set each node in the network to be a detector node independently with probability $\gamma$. In addition, we fixed the worm strategy such that each infected node, in each round, sent out the worm to $\beta$ unique nodes selected uniformly at random, and we fixed the alert strategy such that each alerted node sent out the alert to $\alpha$ unique nodes selected uniformly at random among its neighbors in the overlay network. We note that the worm strategy we used in these experiments is not necessarily the best possible worm strategy, but we selected this strategy for concreteness. Our $d$ regular random graph was created using the configuration model method proposed in Bollobas, ``Random Graphs'', Academic Press , 1985.

In each round we iterate through the set of vertices, allowing each infected or alerted node to send the worm or alert to the appropriate number of other nodes in the network. There are several possible strategies for resolving the status of a virgin (i.e. neither alerted or infected) node that gets both a worm message and an alert message in the same round. In our previous theoretical analysis, we assumed that if a node receives just one worm message it becomes infected. However, in our experiments, we have also used the somewhat more relaxed and realistic assumption that the probability that the node gets infected equals the number of worm messages received divided by the total number of messages received, and that the probability the node becomes alerted is $1$ minus this quantity. We note that this assumption is equivalent to assuming that the messages all arrive in the node's message queue according to some random permutation.
In the following experiment we have used the stringent condition that the alert always wins in case a virgin nodes gets even a single alert message.

The first experiment(Fig a in the paper) $\gamma =0.1$, $\beta=1$, $\alpha=1$ and $d=10$, where we varyed the value of $n$ from $2^{10}$ to $2^{20}$, multiplying at each step by $2$. To remove noise in the simulation, each data point represents the average over $30$ trials. The best result we obtained was saving only $52\%$ of the nodes for $n=2^{20}$. Even though this final data point is somewhat disappointing, we do observe a clear increasing trend in the fraction saved as $n$ increases. Whole of the code was written in C. The file which computed the fraction of nodes given spcific values of all the parameter is here. The script used to change the values of the parameters and averaging over 30 trials is given here. The file containing the different values of the parameter N is given < a href="replace_alert.txt">. Just downloading all these files in a single directory and compiling the script will give the desired results.

Given these results, it seems for current network sizes, there is not much hope for the alert when $\alpha = \beta$. We thus next considered the case where $\alpha > \beta$. In practice, this condition may hold since the alerts are travelling through a predetermined overlay network and a technique such as throttling can ensure that alert messages received through the overlay are given priority over types of messages. To explore this scenario, we conducted experiments where we fixed $\beta$ at $1$. We then determined necessary values of $\gamma$ for each $\alpha$ ranging from 2 to 10, that would ensure that we save $90\%$, $95\%$ and $99\%$ of the nodes. The values of $n$ and $d$ used in the experiment were $10^6$ and $100$ respectively. In this experiment we gave a fair advantage to the worm node as is described in the first paragraph(i.e) the worm infects a nodes with the probability of the number of bad messages recieved over the total number of messages. The file which would compile the results for specific values of the parameters is given here . The scripts used for these experiments are given here. the file in which the values of gamma are given is here. The files used for replacing values of alpha is given here. The results of these experiments were much more encouraging. In particular, for $\alpha = \2$, we were able to save $99\%$ of the nodes with $\gamma = .14$. When $\alpha = 5$, we required a $\gamma$ of $.018$ to save $99\%$ of the nodes, and when $\alpha = 10$, we required a $\gamma$ of only $.001$ to save $99\%$ of the nodes. These results suggest that our algorithms for spreading alerts might be most effective in conjunction with other techniques (like throttling) that would enable the alerts to spread more quickly than the worm.