Rumor source detection with multiple observations under adaptive diffusions
This work addresses anonymity vulnerabilities in social networks for users of anonymous messaging platforms, revealing that incremental improvements in adversary capabilities can compromise source obfuscation guarantees.
The paper tackles the problem of rumor source detection when an adversary has multiple independent snapshots of an adaptive diffusion protocol, showing that weak obfuscation is possible with two snapshots but a simple algorithm can find the source with constant probability using three snapshots on an infinite d-regular tree.
Recent work, motivated by anonymous messaging platforms, has introduced adaptive diffusion protocols which can obfuscate the source of a rumor: a "snapshot adversary" with access to the subgraph of "infected" nodes can do no better than randomly guessing the entity of the source node. What happens if the adversary has access to multiple independent snapshots? We study this question when the underlying graph is the infinite $d$-regular tree. We show that (1) a weak form of source obfuscation is still possible in the case of two independent snapshots, but (2) already with three observations there is a simple algorithm that finds the rumor source with constant probability, regardless of the adaptive diffusion protocol. We also characterize the tradeoff between local spreading and source obfuscation for adaptive diffusion protocols (under a single snapshot). These results raise questions about the robustness of anonymity guarantees when spreading information in social networks.