Where’s Wally? Precise User Discovery Attacks in Location Proximity Services

Location proximity schemes have been adopted by social networks and other smartphone apps as a means of balanc-ing user privacy with utility. However, misconceptions about the privacy offered by proximity services have rendered users vulnerable to trilateration attacks that can expose their lo-cation. Such attacks have received major publicity and, as a result, popular service providers have deployed countermea-sures for preventing user discovery attacks. In this paper, we systematically assess the effectiveness of the defenses that proximity services have deployed against adversaries attempting to identify a user’s location. We pro-vide the theoretical foundation for formalizing the problem under different proximity models, design practical attacks for each case, and prove tight bounds on the number of queries required for carrying out the attacks. To evaluate the completeness of our approach, we conduct extensive experi-ments against popular services. While we identify a diverse set of defense techniques that prevent trilateration attacks, we demonstrate their inefficiency against more elaborate at-tacks. In fact, we pinpoint Facebook users within 5 meters of their exact location, and 90 % of Foursquare users within 15 meters. Our attacks are extremely efficient and complete within 3-7 seconds. The severity of our attacks was acknowl-edged by Facebook and Foursquare, both of which have fol-lowed our recommendations and adopted spatial cloaking to protect their users. Furthermore, our findings have wide implications as numerous popular apps with a massive user base remain vulnerable to this significant threat