Title: Network Defense Games

Speaker: Navin Rustagi, University of New Mexico

Date/Time: Thursday, June 24, 2010, 10:00 am MDT      

Location: CSRI Building/Room 90 (Sandia NM)

Brief Abstract: Attacks on the Internet are characterized by several alarming trends:
1) increases in frequency; 2) increases in speed; and 3) increases in severity. Modern computer worms simply propagate too quickly for human detection. Since attacks are now occurring at a speed which prevents direct human intervention,  there is a need to develop automated defenses.  Since the financial, social and political stakes are so high,  we need defenses which are *provably good* against a worst case attack and are not too costly to deploy.  In this talk we present two  approaches to tackle these problems.

For the first part of the talk we consider a game between an alert and a worm over a large network. We show, for this game, that it is possible to design an algorithm for the alerts that can prevent any worm from infecting more than a vanishingly small fraction of the nodes with high probability.  Critical to our result is designing a communication network for spreading the alerts that has high expansion. The expansion of the network is related to the gap between the first and second eigenvalues of the adjacency matrix. Intuitively high expansion ensures redundant connectivity. We Also present results simulating our algorithm on networks of size up to 2^{25}.

In the second part of the talk we consider the virus inoculation game which models the selfish behavior of the nodes involved. We present a technique for this game which makes it possible to achieve the ``windfall of malice" even without the actual presence of malicious players. We also show the limitations of this technique for congestion games that are known to have a windfall of malice.

CSRI POC: Cindy Phillips, (505) 845-7296