Poisoning Attacks to Local Differential Privacy Protocols for Trajectory Data

Abstract

Trajectory data, which captures the movement of individuals over time, is essential for modern urban planning and location-based services. To mitigate privacy risks, Local Differential Privacy (LDP) protocols are frequently deployed to perturb data at the user level. However, these protocols are primarily designed to defend against passive eavesdropping rather than active manipulation. This paper presents TRAP (Trajectory Poisoning), the first systematic poisoning attack framework against LDP-based trajectory data collection. By injecting a small fraction of malicious trajectories, an attacker can significantly skew aggregate statistics, even in the presence of existing defense mechanisms.

Introduction

As location-aware devices become ubiquitous, the collection of trajectory data has become a cornerstone for services ranging from taxi route optimization to public health monitoring. To protect individual privacy, Local Differential Privacy (LDP) has emerged as a gold standard. In an LDP setting, users apply noise to their own data before transmission, ensuring the central server never observes raw, sensitive paths.

While LDP provides robust theoretical guarantees against data reconstruction, its resilience against data poisoning—where malicious actors inject fake data to manipulate the final aggregate results—remains largely unexplored in the context of complex, high-dimensional trajectory data. Unlike simple categorical or numerical data, trajectories are constrained by geographic "reachability" and high dimensionality, making effective poisoning a significant technical challenge.

The Challenge of Trajectory Poisoning

Poisoning trajectory data is significantly more complex than attacking simple data types for two primary reasons:

1. Reachability Constraints: A fake trajectory must be physically plausible. For example, a user cannot move between two distant cities in a matter of seconds. Simple random noise injection is easily filtered by basic geographic checks.
2. High Dimensionality: The number of possible paths in a geographic grid grows exponentially with the length of the trajectory. Finding the optimal set of fake paths to promote a specific target pattern is computationally prohibitive for standard brute-force methods.

The TRAP Attack Framework

The researchers developed TRAP, a heuristic-based poisoning algorithm designed to promote specific "target patterns" (path segments) within the server's aggregated results. TRAP overcomes the dimensionality barrier through a specialized prefix-suffix approach.

Incremental Trajectory Generation

Instead of generating entire paths at once, TRAP builds trajectories incrementally. It categorizes candidate paths based on their "prefix"—the initial segment that matches a portion of the attacker's target pattern. To maintain computational efficiency, the algorithm employs a greedy pruning strategy. If two candidate paths end at the same location but one has a lower score (less potential to match the target pattern), the lower-scoring path is discarded as "hopeless."

Attack Vectors: IPA vs. OPA

TRAP evaluates two distinct attack scenarios:

• Input Poisoning Attack (IPA): Malicious users provide poisoned raw data to the standard LDP protocol. The protocol then adds noise to this fake data before it reaches the server.
• Output Poisoning Attack (OPA): Malicious users bypass the local LDP software entirely. They generate carefully crafted "noisy" data that mimics the output of an LDP protocol but is optimized to maximize the impact on the server’s aggregate statistics.

Experimental Evaluation

The effectiveness of TRAP was evaluated across seven diverse real-world and simulated datasets, including check-in data from Chicago (CHI), Cleveland (CLE), New York City (NYC), and Gowalla, as well as taxi traces from Porto and campus movement data (CPS).

Key Findings

• Significant Impact with Minimal Effort: The study found that injecting just 20% fake users could increase the popularity score of target patterns by more than fourfold. This demonstrates that LDP protocols are highly vulnerable to coordinated, low-volume attacks.
• Efficiency and Scalability: While brute-force methods failed to generate trajectories longer than four points due to memory exhaustion, TRAP successfully generated plausible trajectories up to 183 points long within the same resource constraints.
• The Paradox of Defense: The researchers tested Frequent Itemset Mining (FIM), a defense intended to filter out outlier paths. Surprisingly, this defense sometimes aided the attacker. If the defense mistakenly removed legitimate, common user patterns while the attacker’s poisoned data remained just below the detection threshold, the relative influence of the poisoned data actually increased.
• Independence from Privacy Budgets: In several protocols (such as n-gram and ATP), the success of the attack was largely independent of the privacy budget ($\epsilon$). Because OPA allows attackers to bypass local noise generation, the server's aggregate results can be manipulated regardless of the privacy level set for legitimate users.

Conclusion

The TRAP framework reveals a critical security gap in current LDP implementations for trajectory data. The ability to manipulate urban statistics through plausible, reachability-constrained fake data poses a threat to the integrity of location-based decision-making systems. These findings serve as an urgent call for the development of "poisoning-aware" LDP protocols that can distinguish between the random noise inherent in privacy preservation and the coordinated noise of a malicious attack.