A novel attack to spatial cloaking schemes in location-based services

• We design a variance-based attack to exploit weaknesses of some existing algorithms.
• We verify the effectiveness of our VBA on several existing algorithms.
• We propose a random walk-based cloaking algorithm to mitigate the proposed attack.

Location-based services (LBSs) have been one of the novel uses and most popular activities in internet of things (IoT). In such location-based applications, mobile users enjoy plenty of conveniences at the cost of privacy. To protect user’s location privacy, many research solutions have been proposed. In this paper, we focus on an important class of solutions, short-range communication-based spatial cloaking algorithms, which achieve kk-anonymity within some collaborative groups. We first analyze the inherent drawbacks of existing P2P-based and encounter-based spatial cloaking approaches and propose a Variance-Based Attack (VBA) against them. Then we study the proposed attack on several existing spatial cloaking solutions. Finally, we propose a countermeasure RR-cloak, which can mitigate VBA for current P2P cloaking algorithms. Our empirical evaluations further verify the effectiveness and efficiency of RR-cloak.