Abstract
Over the last decade we have witnessed the rapid proliferation of online networks and Internet activity. Such activity is considered as a blessing but it brings with it a large increase in risk of computer malware — malignant software that actively spreads from one computer to another. To date, the majority of existing models of malware spread use stochastic behavior, when the set of neighbors infected from the current set of infected nodes is chosen obliviously. In this work, we initiate the study of adversarial infection strategies which can decide intelligently which neighbors of infected nodes to infect next in order to maximize their spread, while maintaining a similar “signature” as the oblivious stochastic infection strategy as not to be discovered. We first establish that computing an optimal and near-optimal adversarial strategies is computationally hard. We then identify necessary and sufficient conditions in terms of network structure and edge infection probabilities such that the adversarial process can infect polynomially more nodes than the stochastic process while maintaining a similar “signature” as the oblivious stochastic infection strategy. Among our results is a surprising connection between an additional structural quantity of interest in a network, the network toughness, and adversarial infections. Based on the network toughness, we characterize networks where existence of adversarial strategies that are pandemic (infect all nodes) is guaranteed, as well as efficiently computable.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Albert, R., Jeong, H., Barabasi, A.-L.: Error and attack tolerance of complex networks. Nature 406(6794), 378–382 (2000)
Alon, N.: A note on network reliability. In: Discrete Probability and Algorithms, pp. 11–14. Springer (1995)
Balthrop, J., Forrest, S., Newman, M.E.J., Williamson, M.M.: Technological networks and the spread of computer viruses. Science 304(5670), 527–529 (2004)
Bauer, D., Broersma, H., Schmeichel, E.F.: Toughness in graphs - a survey. Graphs and Combinatorics 22(1), 1–35 (2006)
Bazgan, C., Santha, M., Tuza, Z.: On the approximation of finding a(nother) Hamiltonian cycle in cubic Hamiltonian graphs. J. Algorithms 31(1), 249–268 (1999)
Britton, T., Janson, S., Martin-Löf, A.: Graphs with specified degree distributions, simple epidemics, and local vaccination strategies. Advances in Applied Probability 39(4), 922–948 (2007)
Chen, Z., Chen, C., Ji, C.: Understanding localized-scanning worms. In: IPCCC, pp. 186–193 (2007)
Cohen, R., Havlin, S., Ben-Avraham, D.: Efficiency immunization strategies for computer networks and populations. Physical Review Letters 91(24), 247901-1–247901-4 (2003)
Crucitti, P., Latora, V., Marchiori, M., Rapisarda, A.: Efficiency of scale-free networks: Error and attack tolerance. Physica A 320(642), 622–642 (2003)
Easley, D.A., Kleinberg, J.M.: Networks, Crowds, and Markets - Reasoning About a Highly Connected World. Cambridge University Press (2010)
Fürer, M., Raghavachari, B.: Approximating the minimum-degree Steiner tree to within one of optimal. J. Algorithms 17(3), 409–423 (1994)
Karger, D.R., Motwani, R., Ramkumar, G.D.S.: On approximating the longest path in a graph. Algorithmica 18(1), 82–98 (1997)
Kempe, D., Kleinberg, J.M., Tardos, É.: Maximizing the spread of influence through a social network. In: KDD, pp. 137–146 (2003)
Komlós, J., Szemerédi, E.: Limit distributions for the existence of Hamiltonian circuits in a random graph. Discrete Mathematics (43), 55–63 (1983)
Ozeki, K., Yamashita, T.: Spanning trees: A survey. Graphs and Combinatorics 27(1), 1–26 (2011)
Serazzi, G., Zanero, S.: Computer virus propagation models. In: Calzarossa, M.C., Gelenbe, E. (eds.) MASCOTS 2003. LNCS, vol. 2965, pp. 26–50. Springer, Heidelberg (2004)
Weaver, N., Paxson, V., Staniford, S., Cunningham, R.: A taxonomy of computer worms. In: WORM, pp. 11–18 (2003)
Win, S.: On a connection between the existence of k-trees and the toughness of a graph. Graphs and Combinatorics 5(1), 201–205 (1989)
Yan, G., Chen, G., Eidenbenz, S., Li, N.: Malware propagation in online social networks: nature, dynamics, and defense implications. In: ASIACCS, pp. 196–206 (2011)
Zou, C.C., Towsley, D.F., Gong, W.: Email worms modeling and defense. In: ICCCN, pp. 409–414 (2004)
Zou, C.C., Towsley, D.F., Gong, W.: On the performance of internet worm scanning strategies. Perform. Eval. 63(7), 700–723 (2006)
Zou, C.C., Towsley, D.F., Gong, W., Cai, S.: Routing worm: A fast, selective attack worm based on IP address information. In: PADS, pp. 199–206 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Brautbar, M., Draief, M., Khanna, S. (2013). On the Power of Adversarial Infections in Networks. In: Bonato, A., Mitzenmacher, M., Prałat, P. (eds) Algorithms and Models for the Web Graph. WAW 2013. Lecture Notes in Computer Science, vol 8305. Springer, Cham. https://doi.org/10.1007/978-3-319-03536-9_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-03536-9_4
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03535-2
Online ISBN: 978-3-319-03536-9
eBook Packages: Computer ScienceComputer Science (R0)