Filed under: Uncategorized | Tags: algorithms, game theory, networks, security, theory

This post is the first part of a two part series. This is by Jared’s student Navin.

Jared and I submitted a paper to SSS 2010. This blog entry will describe the results and some of the ideas used in that paper. The problem is as follows.

Consider the following game between a worm and an alert over a network of n nodes. Initially, no nodes are infected or alerted and each node in the network is a special detector node independently with small but constant probability, γ. A detector node is dedicated to protecting itself against a worst case worm attack and to generate a trace of that attack called S*elf Certifying Alerts*(SCA). Any node which has a SCA, can run that trace in a sand boxed environment to verify the vulnerability and take necessary measures to protect itself.

The game starts with a single node becoming infected. In every round thereafter, every infected node sends out β worms to other nodes in the population for some constant β; in addition, every alerted node sends out α alerts for some constant α. Nodes in the network change state according to the following three rules: 1) If a worm is received by a node that is not a detector and is not alerted, that node becomes infected; 2) If a worm is received by a node that is a detector, that node becomes alerted; 3) If an alert is received by a node that is not infected, that node becomes alerted.

We allow an infected node to send worm messages to any other nodes in the network, but, in contrast, only allow the alerts to be sent over a special precomputed overlay network with degree d. This network is a random d regular graph. We assume that the infected nodes collaborate with each other, and know everything except which nodes are detectors, and the alerted nodes’ random coin flips.

So, is there a strategy which the alerted nodes should follow to ensure that all but o(n) nodes in the network would be alerted? Are there any properties of the underlying overlay network, which are necessary for any successful strategy by alerted nodes to work?

Consider the following strategy for propagating alerts. Each alerted node, chooses α neighbors uniformly at random from its neighbors to send alerts to in the next time step. In our paper titled “Worm Versus Alert: Who Wins in a Battle for Control of a Large-Scale Network?’‘ which appeared in OPODIS 2007, we showed that this strategy for the alerted nodes ensures that only a vanishingly small fraction of the nodes become infected w.h.p, no matter what strategy is used by the infected nodes. In particular, we prove that if d ≥ α and ( α / β(1 – γ) ) > (2d)/c where c is the expansion constant, then w.h.p all but o(n) nodes are infected. We also prove in this paper that there is a worm strategy to take over the network, if the underlying network does not have good expansion.

There is a run of this game for 600 nodes given in the figure. Time moves from left to right, top to bottom in the figure and the red nodes are infected, green nodes are alerted and blue nodes are neither.

So far this post describes the problem statement and previous contributions. I will describe the most recent contributions in the next blogpost.

**1 Comment so far**

Leave a comment

[…] Posts Windfall of MaliceGenerating FunctionologyWorm Vs Alert (Part 1) Beating omniscient worms with faulty detector […]

Pingback by Worm vs Alert (Part 2) « MachinationsJune 25, 2010 @ 4:33 pm