Location proximity schemes have been adopted by social networks and other smartphone apps as a means of balancing user privacy with utility. However, misconceptions about the privacy offered by proximity services have rendered users vulnerable to trilateration attacks that can expose their location. Such attacks have received major publicity. and, as a result, popular service providers have deployed countermeasures 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 provide 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 experiments against popular services. While we identify a diverse set of defense techniques that prevent trilateration attacks, we demonstrate their inefficiency against more elaborate attacks. 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 acknowledged by Facebook and Foursquare, both of which have followed 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.