Protecting Movement: Defending Against Advanced Attacks in Location Social Networks

TL;DR

As we share our lives on platforms like Foursquare or Facebook Places, we often trade privacy for convenience. This paper presents a comprehensive defense system against sophisticated "Linkage Attacks." It moves beyond simple region-hiding to protect against adversaries who use physics (velocity), friends (geotagged posts), and social context (secret meetings) to track you.

Problem & Motivation: The Physics of Privacy

Most location-privacy tools use a Cloaking Region (CR)—a box that says "Alice is somewhere in downtown" instead of "Alice is at 123 Hospital St."

However, the authors point out a fatal flaw: The Velocity Attack. If an attacker knows Alice's maximum speed, they can look at her previous CR and her current CR. By calculating how far someone could actually travel in that timeframe (the Minkowski sum), they can "prune" the safe regions, potentially leaving only the hospital as a possible location.

Furthermore, the rise of external disclosure events (like a friend tagging you in a photo at a restaurant) can retroactively shrink the privacy bounds of your previously reported locations.

Methodology: The Three Pillars of Defense

1. Velocity-Aware Cloaking

The paper introduces two distances: Hausdorff distance (for basic coordinate protection) and Point-Pairwise distance (for protection when an attacker knows where sensitive landmarks are).

• Temporal Transformation: If reported too soon, a location is either deferred (delayed until the travel time matches the distance) or postdated (reporting the last safe location visited).
• Spatial Transformation: Instead of building a CR around the user's current point—which is vulnerable to reverse engineering—the algorithm builds it starting from the previous CR.

2. The Overprovisioning Strategy

To handle External Events, the authors propose an "Overprovisioning" parameter ($\alpha$). By pretending the user's maximum velocity is lower than it actually is, the system creates "buffer room."

• Dynamic Tuning: Uses a linear-decrease/exponential-increase logic (similar to TCP congestion control) to adjust $\alpha$. This minimizes the number of geotagged posts Alice has to block while keeping her past locations safe.

3. Mutual Proximity Protection

How do you keep a secret meeting secret? If Alice and Bob both report CRs that overlap, an attacker infers they met. The system detects this and "pushes" their reported CRs apart, ensuring they remain separated by a threshold distance $S$ in the eyes of the adversary.

Experiments & Results

The researchers tested their Java-based prototype on real GPS data from Rome taxi drivers.

• Quality of Service (QoS): In temporal cloaking, space error was remarkably low—at most 12 meters on real datasets.
• Success Rate: Even under high-sensitivity requirements (meaning Alice wants to be very hidden), the "failure ratio" (dropped requests) stayed roughly at 5%.
• Efficiency: The time to compute a cloaked region was consistently under 1 second, making it viable for mobile deployment.

Deep Insight & Conclusion

This work highlights a critical evolution in privacy: Privacy is not a static property of a single data point; it is a dynamic property of a trajectory.

Takeaway: The "physics" of our movement provides a side-channel for attackers. By mathematically binding our reported regions to our physical capabilities (velocity), we can close this channel.

Limitations: The current model assumes free-space movement. In a dense city with a rigid road network, an attacker could prune even more space by excluding buildings or non-drivable areas. Future research into road-network-constrained cloaking is the next logical frontier.