Monitoring stealthy diffusion

Nika Haghtalab, Aron Laszka, Ariel D. Procaccia, Yevgeniy Vorobeychik, Xenofon Koutsoukos

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


A broad variety of problems, such as targeted marketing and the spread of viruses and malware, have been modeled as maximizing the reach of diffusion through a network. In cyber-security applications, however, a key consideration largely ignored in this literature is stealth. In particular, an attacker who has a specific target in mind succeeds only if the target is reached before the malicious payload is detected and corresponding countermeasures deployed. The dual side of this problem is deployment of a limited number of monitoring units, such as cyber-forensics specialists, to limit the success of such targeted and stealthy diffusion processes. We investigate the problem of optimal monitoring of targeted stealthy diffusion processes. While natural variants of this problem are NP-hard, we show that if stealthy diffusion starts from randomly selected nodes, the defender’s objective is submodular and can be approximately optimized. In addition, we present approximation algorithms for the setting where the choice of the starting point is adversarial. We further extend our results to settings where the diffusion starts at multiple-seed nodes simultaneously, and where there is an inherent delay in detecting the infection. Our experimental results show that the proposed algorithms are highly effective and scalable.

Original languageEnglish (US)
Pages (from-to)657-685
Number of pages29
JournalKnowledge and Information Systems
Issue number3
StatePublished - Sep 1 2017

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Human-Computer Interaction
  • Hardware and Architecture
  • Artificial Intelligence


Dive into the research topics of 'Monitoring stealthy diffusion'. Together they form a unique fingerprint.

Cite this