  Location-based queries enable fundamental services for mobile road network
travelers. While the benefits of location-based services (LBS) are numerous,
exposure of mobile travelers' location information to untrusted LBS providers
may lead to privacy breaches. In this paper, we propose StarCloak, a
utility-aware and attack-resilient approach to building a privacy-preserving
query system for mobile users traveling on road networks. StarCloak has several
desirable properties. First, StarCloak supports user-defined k-user anonymity
and l-segment indistinguishability, along with user-specified spatial and
temporal utility constraints, for utility-aware and personalized location
privacy. Second, unlike conventional solutions which are indifferent to
underlying road network structure, StarCloak uses the concept of stars and
proposes cloaking graphs for effective location cloaking on road networks.
Third, StarCloak achieves strong attack-resilience against replay and query
injection-based attacks through randomized star selection and pruning. Finally,
to enable scalable query processing with high throughput, StarCloak makes
cost-aware star selection decisions by considering query evaluation and network
communication costs. We evaluate StarCloak on two real-world road network
datasets under various privacy and utility constraints. Results show that
StarCloak achieves improved query success rate and throughput, reduced
anonymization time and network usage, and higher attack-resilience in
comparison to XStar, its most relevant competitor.
