W³-tess: Defeating De-anonymization via Socially-Aware Trace Synthesis
Synthesizing Privacy-Preserving Traces: Enhancing Plausibility with Social Networks
This paper introduces W³-tess, a novel privacy-preserving framework that synthesizes plausible location traces by integrating temporal, spatial, and social dimensions. It achieves state-of-the-art protection against social relationship-based de-anonymization attacks while providing theoretically provable differential privacy guarantees.
TL;DR
Location privacy is no longer just about hidding your coordinates; it's about hiding your behavioral identity. W³-tess is a breakthrough framework that synthesizes "plausible" fake location traces by simulating not just where you go, but how your social circle influences your movement. By injecting social logic into synthetic data, it provides a theoretically robust shield against advanced de-anonymization attacks that exploit social network correlations.
The "Why" behind the Movement: Identifying the Social Gap
Traditional location cloaking methods (like PAD or INTER) treated users as random dots on a map, using grids or circles to generate "dummies." Later models like PULE improved this by adding temporal and spatial logic—recognizing that humans move between home and work.
However, there was a missing dimension: Social Influence. Attackers today don't just look at a single trace; they look at the contact graph. If a user's trace shows frequent proximity to identified "friends" in a social network, a synthetic trace that ignores these meetings stands out like a sore thumb. This is the Social Relationship-based De-anonymization Attack. W³-tess was designed specifically to bridge this gap.
Methodology: The Three Dimensions of Plausibility
The core innovation of W³-tess lies in its Three-Dimension Mobility Model:
- Spatial Behavior: Geographic centers (home, work) and movement ranges.
- Temporal Behavior: Periodic movements based on time-of-day.
- Social Behavior: "Social locations" triggered by the dynamic influence of a user's friends.
1. Modeling Social Dynamics
Instead of static rules, W³-tess uses a Dynamic Strategy to update influential friends. It calculates influence based on both spatial proximity (friends living near your current trajectory center) and temporal coincidence (friends who checked into a place you recently visited).
Figure 1: The W³-tess architecture, showing the trusted server generating synthetic traces before sending them to an untrusted aggregator.
2. (F, k, ρ) Sampling
To ensure that adding fake traces doesn't ruin the "utility" of the data for legitimate researchers (e.g., map makers or city planners), the authors proposed a specialized sampling mechanism. By ensuring the statistical features (Task ) of the synthetic traces match the real traces, they achieve a unique bridge between Differential Privacy and Data Utility.
Experimental Results: Proving the Plausibility
The researchers tested W³-tess against two massive real-world datasets: loc-Gwalla and loc-Brightkite.
Privacy: Thwarting De-anonymization
While previous SOTA models like PULE were effective against simple inference attacks, their success rate plummeted when faced with social graph attacks. W³-tess maintained a consistently low attack success rate because its "dummies" mimicked social nodes effectively.
Figure 2: Success rate of de-anonymization attacks. W³-tess (the lowest line) significantly outperforms heuristic and semantic-only models.
Utility: Keeping the Data "Real"
Whether the task was extracting "Top-K Frequently Visited Locations" or "Friendship Inference," W³-tess synthetic traces were indistinguishable from real data from a statistical perspective. This means aggregators can still perform high-quality analysis without ever seeing the "true" individual traces.
Critical Insight: Why This Matters
The fundamental contribution of W³-tess is the formal proof that Privacy and Utility are not a zero-sum game if the synthesis model is sufficiently high-dimensional. By proving (k, ε, δ)-differential privacy, the authors move trace synthesis from a heuristic "guessing game" to a mathematically grounded security protocol.
Limitations & Future Work
While W³-tess is efficient, it assumes the existence of a "Trusted Server" to handle the initial raw data. In a fully decentralized world, moving this logic to a Local Differential Privacy (LDP) setting where the user's phone generates its own social-aware dummies without a central server would be the next frontier.
Conclusion
W³-tess sets a new standard for trace privacy. By acknowledging that our movement is a social act, it creates a "crowd" of synthetic users so realistic that even social-network-aware attackers can't find the needle in the haystack.