Achieving Guaranteed Anonymity in GPS Traces via Uncertainty-Aware Path Cloaking

The integration of Global Positioning System (GPS) receivers and sensors into mobile devices has enabled collaborative sensing applications, which monitor the dynamics of environments through opportunistic collection of data from many users' devices. One example that motivates this paper is a probe-vehicle-based automotive traffic monitoring system, which estimates traffic congestion from GPS velocity measurements reported from many drivers. This paper considers the problem of achieving guaranteed anonymity in a locational data set that includes location traces from many users, while maintaining high data accuracy. We consider two methods to reidentify anonymous location traces, target tracking, and home identification, and observe that known privacy algorithms cannot achieve high application accuracy requirements or fail to provide privacy guarantees for drivers in low-density areas. To overcome these challenges, we derive a novel time-to-confusion criterion to characterize privacy in a locational data set and propose a disclosure control algorithm (called uncertainty-aware path cloaking algorithm) that selectively reveals GPS samples to limit the maximum time-to-confusion for all vehicles. Through trace-driven simulations using real GPS traces from 312 vehicles, we demonstrate that this algorithm effectively limits tracking risks, in particular, by eliminating tracking outliers. It also achieves significant data accuracy improvements compared to known algorithms. We then present two enhancements to the algorithm. First, it also addresses the home identification risk by reducing location information revealed at the start and end of trips. Second, it also considers heading information reported by users in the tracking model. This version can thus protect users who are moving in dense areas but in a different direction from the majority.