ABSTRACT
We provide a systematic study of the problem of finding the source of a computer virus in a network. We model virus spreading in a network with a variant of the popular SIR model and then construct an estimator for the virus source. This estimator is based upon a novel combinatorial quantity which we term rumor centrality. We establish that this is an ML estimator for a class of graphs. We find the following surprising threshold phenomenon: on trees which grow faster than a line, the estimator always has non-trivial detection probability, whereas on trees that grow like a line, the detection probability will go to 0 as the network grows. Simulations performed on synthetic networks such as the popular small-world and scale-free networks, and on real networks such as an internet AS network and the U.S. electric power grid network, show that the estimator either finds the source exactly or within a few hops in different network topologies. We compare rumor centrality to another common network centrality notion known as distance centrality. We prove that on trees, the rumor center and distance center are equivalent, but on general networks, they may differ. Indeed, simulations show that rumor centrality outperforms distance centrality in finding virus sources in networks which are not tree-like.
- The CAIDA AS relationships dataset. http://www.caida.org/data/active/as--relationships, August 30th, 2009.Google Scholar
- N. T. J. Bailey. The Mathematical Theory of Infectious Diseases and its Applications. Griffin, London, 1975.Google Scholar
- A. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286:509--512, 1999.Google ScholarCross Ref
- P. Bonacich. Power and centrality: A family of measures. American Journal of Sociology 92:1170{1182, 1987.Google ScholarCross Ref
- L. C. Freeman. A set of measure of centrality based on betweenness. Sociometry, 40:35--41, 1977.Google ScholarCross Ref
- A. Ganesh, L. Massoulie, and D. Towsley. The effect network topology on the spread of epidemics. Proc 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2:1455--1466, 2005.Google ScholarCross Ref
- C. Moore and M. E. J. Newman. Epidemics and percolation in in small-world networks. Phys. Rev. E, 61:5678--5682, 2000.Google ScholarCross Ref
- M. E. J. Newman. The spread of epidemic disease on networks. Phys. Rev. E, 66:016128, 2002.Google ScholarCross Ref
- H. Okamura, K. Tateishi, and T. Doshi. Statistical inference of computer virus propagation using non-homogeneous poisson processes. Proc. 18th IEEE International Symposium on Software Reliability, 5:149--158, 2007. Google ScholarDigital Library
- R. Pastor-Satorras and A. Vespignani. Epidemic spreading in scale-free networks. Phys. Rev. Lett., 6:3200--3203, 2001.Google ScholarCross Ref
- G. Sabidussi. The centrality index of a graph. Psychometrika, 31:581--603, 1966.Google ScholarCross Ref
- G. Streftaris and G. J. Gibson. Statistical inference for stochastic epidemic models. Proc. 17th international Workshop on Statistical Modeling, pages 609--616, 2002.Google Scholar
- D. J. Watts and S. Strogatz. Collective dynamics of `small--world' networks. Nature, 393:440--442, 1998.Google ScholarCross Ref
Index Terms
- Detecting sources of computer viruses in networks: theory and experiment
Recommendations
Rumor centrality: a universal source detector
Performance evaluation reviewWe consider the problem of detecting the source of a rumor (information diffusion) in a network based on observations about which set of nodes possess the rumor. In a recent work [10], this question was introduced and studied. The authors proposed rumor ...
Rumor centrality: a universal source detector
SIGMETRICS '12: Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer SystemsWe consider the problem of detecting the source of a rumor (information diffusion) in a network based on observations about which set of nodes possess the rumor. In a recent work [10], this question was introduced and studied. The authors proposed rumor ...
Detecting sources of computer viruses in networks: theory and experiment
Performance evaluation reviewWe provide a systematic study of the problem of finding the source of a computer virus in a network. We model virus spreading in a network with a variant of the popular SIR model and then construct an estimator for the virus source. This estimator is ...
Comments