Detecting sources of computer viruses in networks: Theory and experiment
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 wh...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2011
|
| Online Access: | http://hdl.handle.net/1721.1/63150 https://orcid.org/0000-0003-0737-3259 https://orcid.org/0000-0003-4973-9343 |
| _version_ | 1811096585097969664 |
|---|---|
| author | Shah, Devavrat Zaman, Tauhid R. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Shah, Devavrat Zaman, Tauhid R. |
| author_sort | Shah, Devavrat |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T16:45:43Z |
| format | Article |
| id | mit-1721.1/63150 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:45:43Z |
| publishDate | 2011 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/631502022-09-29T21:21:00Z Detecting sources of computer viruses in networks: Theory and experiment Shah, Devavrat Zaman, Tauhid R. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Shah, Devavrat Shah, Devavrat Zaman, Tauhid R. 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. United States. Air Force Office of Scientific Research (Complex Networks Program SubAward 00006517) 2011-05-31T19:10:41Z 2011-05-31T19:10:41Z 2010-06 Article http://purl.org/eprint/type/ConferencePaper 978-1-4503-0038-4 http://hdl.handle.net/1721.1/63150 Shah, Devavrat and Tauhid Zaman. "Detecting Sources of Computer Viruses in Networks: Theory and Experiment." Proceedings of the ACM SIGMETRICS international conference on Measurement and modeling of computer systems, SIGMETRICS '10, June 14-18, 2010, Columbia University, New York. https://orcid.org/0000-0003-0737-3259 https://orcid.org/0000-0003-4973-9343 en_US http://dx.doi.org/10.1145/1811099.1811063 Proceedings of the ACM SIGMETRICS international conference on Measurement and modeling of computer systems, SIGMETRICS '10 Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery MIT web domain |
| spellingShingle | Shah, Devavrat Zaman, Tauhid R. Detecting sources of computer viruses in networks: Theory and experiment |
| title | Detecting sources of computer viruses in networks: Theory and experiment |
| title_full | Detecting sources of computer viruses in networks: Theory and experiment |
| title_fullStr | Detecting sources of computer viruses in networks: Theory and experiment |
| title_full_unstemmed | Detecting sources of computer viruses in networks: Theory and experiment |
| title_short | Detecting sources of computer viruses in networks: Theory and experiment |
| title_sort | detecting sources of computer viruses in networks theory and experiment |
| url | http://hdl.handle.net/1721.1/63150 https://orcid.org/0000-0003-0737-3259 https://orcid.org/0000-0003-4973-9343 |
| work_keys_str_mv | AT shahdevavrat detectingsourcesofcomputervirusesinnetworkstheoryandexperiment AT zamantauhidr detectingsourcesofcomputervirusesinnetworkstheoryandexperiment |