Monitoring Stealthy Diffusion
Nika Haghtalab, Aron Laszka, Ariel Procaccia, Yevgeniy Vorobeychik, Xenofon Koutsoukos

Citation
Nika Haghtalab, Aron Laszka, Ariel Procaccia, Yevgeniy Vorobeychik, Xenofon Koutsoukos. "Monitoring Stealthy Diffusion". 15th IEEE International Conference on Data Mining (ICDM), November, 2015.

Abstract
Starting with the seminal work by Kempe et al., a broad variety of problems, such as targeted marketing and the spread of viruses and malware, have been modeled as selecting a subset of nodes to maximize diffusion through a network. In cyber-security applications, however, a key consideration largely ignored in this literature is stealth. In particular, an attacker often has a specific target in mind, but succeeds only if the target is reached (e.g., by malware) 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, so as to limit the likelihood of such targeted and stealthy diffusion processes reaching their intended targets. We investigate the problem of optimal monitoring of targeted stealthy diffusion processes, and show that a number of natural variants of this problem are NP-hard to approximate. On the positive side, we show that if stealthy diffusion starts from randomly selected nodes, the defender's objective is submodular, and a fast greedy algorithm has provable approximation guarantees. In addition, we present approximation algorithms for the setting in which an attacker optimally responds to the placement of monitoring nodes by adaptively selecting the starting nodes for the diffusion process. Our experimental results show that the proposed algorithms are highly effective and scalable.

Electronic downloads

Internal. This publication has been marked by the author for FORCES-only distribution, so electronic downloads are not available without logging in.

Citation formats

• HTML

  Nika Haghtalab, Aron Laszka, Ariel Procaccia, Yevgeniy
  Vorobeychik, Xenofon Koutsoukos. <a
  href="http://www.cps-forces.org/pubs/119.html"
  >Monitoring Stealthy Diffusion</a>, 15th IEEE
  International Conference on Data Mining (ICDM), November,
  2015.

• Plain text

  Nika Haghtalab, Aron Laszka, Ariel Procaccia, Yevgeniy
  Vorobeychik, Xenofon Koutsoukos. "Monitoring Stealthy
  Diffusion". 15th IEEE International Conference on Data
  Mining (ICDM), November, 2015.

• BibTeX

  @inproceedings{HaghtalabLaszkaProcacciaVorobeychikKoutsoukos15_MonitoringStealthyDiffusion,
      author = {Nika Haghtalab and Aron Laszka and Ariel Procaccia
                and Yevgeniy Vorobeychik and Xenofon Koutsoukos},
      title = {Monitoring Stealthy Diffusion},
      booktitle = {15th IEEE International Conference on Data Mining
                (ICDM)},
      month = {November},
      year = {2015},
      abstract = {Starting with the seminal work by Kempe et al., a
                broad variety of problems, such as targeted
                marketing and the spread of viruses and malware,
                have been modeled as selecting a subset of nodes
                to maximize diffusion through a network. In
                cyber-security applications, however, a key
                consideration largely ignored in this literature
                is stealth. In particular, an attacker often has a
                specific target in mind, but succeeds only if the
                target is reached (e.g., by malware) 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, so as to limit the likelihood of such
                targeted and stealthy diffusion processes reaching
                their intended targets. We investigate the problem
                of optimal monitoring of targeted stealthy
                diffusion processes, and show that a number of
                natural variants of this problem are NP-hard to
                approximate. On the positive side, we show that if
                stealthy diffusion starts from randomly selected
                nodes, the defender's objective is submodular, and
                a fast greedy algorithm has provable approximation
                guarantees. In addition, we present approximation
                algorithms for the setting in which an attacker
                optimally responds to the placement of monitoring
                nodes by adaptively selecting the starting nodes
                for the diffusion process. Our experimental
                results show that the proposed algorithms are
                highly effective and scalable.},
      URL = {http://cps-forces.org/pubs/119.html}
  }
  

Posted by Aron Laszka on 15 Mar 2016.
For additional information, see the Publications FAQ or contact webmaster at cps-forces org.