Inoculation strategies for victims of viruses and the sum-of-squares partition problem

ABSTRACT

We propose a simple game for modeling containment of the spread of viruses in a graph of n nodes. Each node must choose to either install anti-virus software at some known cost C, or risk infection and a loss L if a virus that starts at a random initial point in the graph can reach it without being stopped by some intermediate node. The goal of individual nodes is to minimize their individual expected cost. We prove many game theoretic properties of the model, including an easily applied characterization of Nash equilibria, culminating in our showing that allowing selfish users to choose Nash equilibrium strategies is highly undesirable, because the price of anarchy is an unacceptable Θ(n) in the worst case. This shows in particular that a centralized solution can give a much better total cost than an equilibrium solution. Though it is NP-hard to compute such a social optimum, we show that the problem can be reduced to a previously unconsidered combinatorial problem that we call the sum-of-squares partition problem. Using a greedy algorithm based on sparse cuts, we show that this problem can be approximated to within a factor of O(log² n), giving the same approximation ratio for the inoculation game.

REFERENCES

• 1: R. Anderson. Why information security is hard - an economic perspective, 2001. Available at http://www.cl.cam.ac.uk/-rja14/econsec.html.
• 2: Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
• 3: J. Aspnes, K. Chang, and A. Yampolskiy. Inoculation strategies for victims of viruses and the sum-of-squares partition problem. Technical Report YALEU/DCS/TR-1295, Yale University, July 2004. Available at ftp://ftp.cs.yale.edu/pub/TR/tr1295.pdf.
• 4: J. Aspnes, J. Feigenbaum, M. Mitzenmacher, and D. Parkes. Towards better definitions and measures of Internet security. In Workshop on Large-Scale Network Security and Deployment Obstacles, 2003.
• 5: N. T. Bailey. The Mathematical theory of infectious diseases and its applications. Hafner Press, 1975.
• 6: M. G. H. Bell. The measurement of reliability in stochastic transport networks. In Proceedings of 2001 Intelligent Transportation Systems, pages 1183--1188, 2001.
• 7: Katherine Campbell , Lawrence A. Gordon , Martin P. Loeb , Lei Zhou, The economic cost of publicly announced information security breaches: empirical evidence from the stock market, Journal of Computer Security, v.11 n.3, p.431-448, 1 March 2003
• 8: Guy Even, Fast Approximate Graph Partitioning Algorithms, SIAM Journal on Computing, v.28 n.6, p.2187-2214, Dec. 1999 [doi>10.1137/S0097539796308217]
• 9: Uriel Feige , Robert Krauthgamer, A Polylogarithmic Approximation of the Minimum Bisection, SIAM Journal on Computing, v.31 n.4, p.1090-1118, 2002 [doi>10.1137/S0097539701387660]
• 10: J. C. Frauenthal. Mathematical modeling in epidemiology. Springer-Verlag, New York, 1980.
• 11: Lawrence A. Gordon , Martin P. Loeb, The economics of information security investment, ACM Transactions on Information and System Security (TISSEC), v.5 n.4, p.438-457, November 2002 [doi>10.1145/581271.581274]
• 12: S. N. Hamilton, W. L. Miller, A. Ott, and O. S. Saydjari. Challenges in applying game theory to the domain of information warfare. In 4th Information survivability workshop (ISW-2001/2002), Vancouver, Canada, 2002.
• 13: S. N. Hamilton, W. L. Miller, A. Ott, and O. S. Saydjari. The role of game theory in information warfare. In 4th Information survivability workshop (ISW-2001/2002), Vancouver, Canada, 2002.
• 14: K. Hoo. How much is enough? A risk-management approach to computer security. Consortium for Research on Information Security Policy (CRISP) Working Paper., 2000.
• 15: M. Kearns and L. Ortiz. Algorithms for interdependent security games. In S. Thrun, L. Saul, and B. Schölkopf, editors, Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA, 2004.
• 16: Jeffrey O. Kephart , Steve R. White , David M. Chess, Computers and epidemiology, IEEE Spectrum, v.30 n.5, p.20-26, May 1993 [doi>10.1109/6.275061 ]
• 17: J. O. Kephart and S. R. White. Directed-graph epidemiological models of computer viruses. In IEEE Symposium on Security and Privacy, pages 343--361, 1991.
• 18: Jeffrey O. Kephart , Steve R. White, Measuring and Modeling Computer Virus Prevalence, Proceedings of the 1993 IEEE Symposium on Security and Privacy, p.2, May 24-26, 1993
• 19: H. Kesten. Percolation Theory for Mathematicians, volume 2. Birkhäuser, Boston, 1982.
• 20: E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In Proceedings of the 16th annual symposium on theoretical aspects of computer science, pages 403--413, 1999.
• 21: H. Kunreuther and G. Heal. Interdependent security. Journal of Risk and Uncertainty (Special Issue on Terrorist Risks), 2003.
• 22: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 23: R. Pastor-Satorras and A. Vespignani. Epidemics and immunization scale-free networks. In S. Born-holdt and H. Schuster, editors, Handbook of graphs and networks: from the genome to the Internet, pages 113--132, Berlin, 2002. Wiley-VCH.
• 24: R. Pastor-Satorras and A. Vespignani. Immunization of complex networks. In Physical Review Letters, volume 65, 2002.
• 25: Paul F. Syverson, A Different Look at Secure Distributed Computation, Proceedings of the 10th Computer Security Foundations Workshop (CSFW '97), p.109, June 10-12, 1997
• 26: Chenxi Wang , J. C. Knight , M. C. Elder, On computer viral infection and the effect of immunization, Proceedings of the 16th Annual Computer Security Applications Conference, p.246, December 11-15, 2000
• 27: C. Zou, D. Towsley, and W. Gong. Email virus propagation modeling and analysis. Technical Report CSE-03-04, University of Massachusetts, Amherst, 2002.