k-Trustee: Location injection attack-resilient anonymization for location privacy

Cloaking-based location privacy preserving mechanisms have been widely proposed to protect users' location privacy when using location-based services. A fundamental limitation of such mechanisms is that users and their location information in the system are inherently trusted by the Anonymization Server without any verification. In this paper, we show that such an issue could lead to a new class of attacks called location injection attacks which can successfully violate users' in-distinguishability among a set of users. We propose and characterize location injection attacks by presenting a set of attack models and quantifying the costs associated with them. We present and evaluate k-Trustee, a trust-aware location cloaking mechanism that is resilient to location injection attacks and guarantees a lower bound on the user's in-distinguishability. k-Trustee guarantees that each user in a given cloaked region can achieve the required k-Anonymity by including at least k-1 other trusted users in the cloaked region. We demonstrate the effectiveness of k-Trustee through extensive experiments in a real-world geographic map and our experimental results show that the proposed cloaking algorithm guaranteeing k-Trustee is effective against various location injection attacks.