Poisoning the Predictor: Enhancing MSN Privacy via Strategic Fake Locations

TL;DR

Mobile Social Networks (MSNs) present a unique privacy paradox: even if you hide your location, your friends' data and your own movement history can "betray" you. This paper proposes a decentralized solution that injects mathematically optimized fake locations into the data stream, specifically designed to defeat Kalman filter-based trajectory estimation.

The "Invisible" Threat: Contextual Correlation

In the world of Location-Based Services (LBS), privacy is usually treated as a "hide and seek" game. Most users assume that if they stop uploading data near a sensitive area (like a hospital), their privacy is safe.

However, the authors point out two fatal flaws in this intuition:

1. Temporal Correlation: Human movement isn't random. An adversary using Kalman Filling (a combination of forward and backward Kalman filters) can interpolate missing gaps with terrifying accuracy.
2. Social Correlation: If you are at the hospital with a friend, and that friend reports their location, the MSN provider can infer your position through your "closeness" relationship.

Fig 1. Left: Gap filling via historical data. Right: Privacy leak through a friend's reported location.

Methodology: Outsmarting the Kalman Filter

Instead of omitting data, the authors suggest reporting fake locations. But not just any random points—these points must be "plausible" yet "distorting."

1. Optimal Fake Location Generation

A fake location $(x,y)$ must satisfy physical constraints (maximum speed $S_{max}$) so that the MSN's anomaly detection doesn't immediately discard it. The goal is to maximize the Euclidean distance from the real location while staying within the intersection of two "reachability circles" defined by the previous and next time steps.

2. Social Decoherence

For groups, the paper leverages Information Theory. By calculating the Mutual Information $I(L_A;L_B)$ between friends, the system identifies periods of high closeness. To protect the group, friends alternate: when A reports a real location, B reports a fake one, and vice versa. This effectively "blurs" the social link in the eyes of the service provider.

Algorithm 1: The Adversary's tracking logic which the proposed method seeks to disrupt.

Experimental Validation

The authors tested their scheme against a "Location Omission" baseline. The results in Fig 4 and Fig 5 are telling:

• Fake vs. Omission: Reporting fake locations causes a much higher estimation error for the adversary compared to simply leaving gaps.
• Stability: As observation time increases, the protection level (average error) doesn't degrade; it stabilizes, proving the robustness of the noise injection.

Fig 4 & 5: Average estimation error remains consistently higher when using fake locations compared to omission.

Critical Insight & Conclusion

The brilliance of this work lies in its adversarial mindset. It recognizes that modern tracking is a probabilistic process. By treating the adversary’s Kalman filter as a system to be "poisoned" rather than merely avoided, the authors provide a much stronger privacy guarantee.

Limitations: The model assumes a relatively linear human movement pattern. In reality, human mobility often follows heavy-tailed distributions (like Levy-walks), which the authors acknowledge as a direction for future refinement.

The Takeaway? In the era of big data, silence is not enough. To stay private, you need to provide a "plausible lie" that keeps the algorithms guessing.