TY - JOUR
T1 - Rumor Source Obfuscation on Irregular Trees
AU - Fanti, Giulia
AU - Kairouz, Peter
AU - Oh, Sewoong
AU - Ramchandran, Kannan
AU - Viswanath, Pramod
N1 - Funding Information:
We would like to thank the anonymous reviewers for their helpful comments. This work has been supported by NSF CISE awards CCF-1422278 and CCF-1553452, and SaTC award CNS-1527754.
Publisher Copyright:
© 2016 ACM.
PY - 2016/6
Y1 - 2016/6
N2 - 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 differ 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.
AB - 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 differ 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.
KW - anonymous social media
KW - privacy
KW - rumor spreading
UR - http://www.scopus.com/inward/record.url?scp=85112751794&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85112751794&partnerID=8YFLogxK
U2 - 10.1145/2896377.2901471
DO - 10.1145/2896377.2901471
M3 - Article
AN - SCOPUS:85112751794
SN - 0163-5999
VL - 44
SP - 153
EP - 164
JO - Performance Evaluation Review
JF - Performance Evaluation Review
IS - 1
ER -