Rumor source obfuscation on irregular trees

Giulia Fanti, Peter Kairouz, Sewoong Oh, Kannan Ramchandran, Pramod Viswanath

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Anonymous messaging applications have recently gained popularity as a means for sharing opinions without fear of judgment or repercussion. Messages in these applications propagate anonymously (without authorship metadata) over a network that is typically defined by social connections or physical proximity. However, recent advances in rumor source detection show that the source of such an anonymous message can be inferred by statistical inference attacks. Adaptive diffusion was recently proposed as a solution that achieves optimal source obfuscation over regular trees. However, in real social networks, node degrees different from node to node, and adaptive diffusion can be significantly sub-optimal. This gap increases as the degrees become more irregular. In order to quantify this gap, we model the underlying network as coming from standard branching processes with i.i.d. degree distributions. Building upon the analysis techniques from branching processes, we give an analytical characterization of the dependence between the probability of detection achieved by adaptive diffusion and the degree distribution. Further, this analysis provides a key insight: passing a rumor to a friend who has many friends makes the source more ambiguous. This leads to a new family of protocols that we call Preferential Attachment Adaptive Diffusion (PAAD). When messages are propagated according to PAAD, we give both the MAP estimator for finding the source and also an analysis of the probability of detection achieved by this adversary. The analytical results are not directly comparable, since the adversary's observed information has a different distribution under adaptive diffusion than under PAAD. Instead, we present results from numerical experiments that suggest that PAAD achieves a lower probability of detection, at the cost of increased communication for coordination.

Original languageEnglish (US)
Title of host publicationSIGMETRICS/ Performance 2016 - Proceedings of the SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Science
PublisherAssociation for Computing Machinery, Inc
Pages153-164
Number of pages12
ISBN (Electronic)9781450342667
DOIs
StatePublished - Jun 14 2016
Event13th Joint International Conference on Measurement and Modeling of Computer Systems, ACM SIGMETRICS / IFIP Performance 2016 - Antibes Juan-les-Pins, France
Duration: Jun 14 2016Jun 18 2016

Publication series

NameSIGMETRICS/ Performance 2016 - Proceedings of the SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Science

Other

Other13th Joint International Conference on Measurement and Modeling of Computer Systems, ACM SIGMETRICS / IFIP Performance 2016
CountryFrance
CityAntibes Juan-les-Pins
Period6/14/166/18/16

Keywords

  • Anonymous social media
  • Privacy
  • Rumor spreading

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Rumor source obfuscation on irregular trees'. Together they form a unique fingerprint.

Cite this