Quantifying the Effect of Co-location Information on Location Privacy

Mobile users increasingly report their co-locations with other users, in addition to revealing their locations to online services. For instance, they tag the names of the friends they are with, in the messages and in the pictures they post on social networking websites. Combined with (possibly obfuscated) location information, such co-locations can be used to improve the inference of the users’ locations, thus further threatening their location privacy: as co-location information is taken into account, not only a user’s reported locations and mobility patterns can be used to localize her, but also those of her friends (and the friends of their friends and so on). In this paper, we study this problem by quantifying the effect of co-location information on location privacy, with respect to an adversary such as a social network operator that has access to such information. We formalize the problem and derive an optimal inference algorithm that incorporates such co-location information, yet at the cost of high complexity. We propose two polynomial-time approximate inference algorithms and we extensively evaluate their performance on a real dataset. Our experimental results show that, even in the case where the adversary considers co-locations with only a single friend of the targeted user, the location privacy of the user is decreased by up to 75% in a typical setting. Even in the case where a user does not disclose any location information, her privacy can decrease by up to 16% due to the information reported by other users.

Quantifying Interdependent Privacy Risks with Location Data

Jean-Pierre Hubaux, Kévin Clément Huguenin, Mathias Jacques Jean-Marc Humbert, Alexandra-Mihaela Olteanu, Reza Shokri

Co-location information about users is increasingly available online. For instance, mobile users more and more frequently report their co-locations with other users in the messages and in the pictures they post on social networking websites by tagging the names of the friends they are with. The users’ IP addresses also constitute a source of co-location information. Combined with (possibly obfuscated) location information, such co-locations can be used to improve the inference of the users’ locations, thus further threatening their location privacy: As co-location information is taken into account, not only a user’s reported locations and mobility patterns can be used to localize her, but also those of her friends (and the friends of their friends and so on). In this paper, we study this problem by quantifying the effect of co-location information on location privacy, considering an adversary such as a social network operator that has access to such information. We formalize the problem and derive an optimal inference algorithm that incorporates such co-location information, yet at the cost of high complexity. We propose some approximate inference algorithms, including a solution that relies on the belief propagation algorithm executed on a general Bayesian network model, and we extensively evaluate their performance. Our experimental results show that, even in the case where the adversary considers co-locations of the targeted user with a single friend, the median location privacy of the user is decreased by up to 62% in a typical setting. We also study the effect of the different parameters (e.g., the settings of the location-privacy protection mechanisms) in different scenarios.

Ieee Computer Soc2017

Context and Semantic Aware Location Privacy

Berker Agir

With ever-increasing computational power, and improved sensing and communication capabilities, smart devices have altered and enhanced the way we process, perceive and interact with information. Personal and contextual data is tracked and stored extensively on these devices and, oftentimes, ubiquitously sent to online service providers. This routine is proving to be quite privacy-invasive, since these service providers mine the data they collect in order to infer more and more personal information about users. Protecting privacy in the rise of mobile applications is a critical challenge. The continuous tracking of users with location- and time-stamps expose their private lives at an alarming level. Location traces can be used to infer intimate aspects of users' lives such as interests, political orientation, religious beliefs, and even more. Traditional approaches to protecting privacy fail to meet users' expectations due to simplistic adversary models and the lack of a multi-dimensional awareness. In this thesis, the development of privacy-protection approaches is pushed further by (i) adapting to concrete adversary capabilities and (ii) investigating the threat of strong adversaries that exploit location semantics. We first study user mobility and spatio-temporal correlations in continuous disclosure scenarios (e.g., sensing applications), where the more frequently a user discloses her location, the more difficult it becomes to protect. To counter this threat, we develop adversary- and mobility-aware privacy protection mechanisms that aim to minimize an adversary's exploitation of user mobility. We demonstrate that a privacy protection mechanism must actively evaluate privacy risks in order to adapt its protection parameters. We further develop an Android library that provides on-device location privacy evaluation and enables any location-based application to support privacy-preserving services. We also implement an adversary-aware protection mechanism in this library with semantic-based privacy settings. Furthermore, we study the effects of an adversary that exploits location semantics in order to strengthen his attacks on user traces. Such extensive information is available to an adversary via maps of points of interest, but also from users themselves. Typically, users of online social networks want to announce their whereabouts to their circles. They do so mostly, if not always, by sharing the type of their location along with the geographical coordinates. We formalize this setting and by using Bayesian inference show that if location semantics of traces is disclosed, users' privacy levels drop considerably. Moreover, we study the time-of-day information and its relation to location semantics. We reveal that an adversary can breach privacy further by exploiting time-dependency of semantics. We implement and evaluate a sensitivity-aware protection mechanism in this setting as well. The battle for privacy requires social awareness and will to win. However, the slow progress on the front of law and regulations pushes the need for technological solutions. This thesis concludes that we have a long way to cover in order to establish privacy-enhancing technologies in our age of information. Our findings opens up new venues for a more expeditious understanding of privacy risks and thus their prevention.

EPFL2016

Quantifying and Protecting Location Privacy

Reza Shokri

Recent developments in information and communication technologies have been profound and life-changing. Most people are now equipped with smart phones with high computation power and communication capabilities. These devices can efficiently run multiple software applications in parallel, store a non-negligible amount of (personal) user data, process various sophisticated sensors and actuators, and communicate over multiple wireless media. Furthermore, they are commonly equipped with high-precision localization capabilities based, for example, on a GPS receiver or on triangulation with nearby base stations or access points. Mobile applications take advantage of this feature to provide location-based services to users. The ever-increasing usage of these personal communication devices and mobile applications, although providing convenience to their owners, comes at a very high cost to their privacy. Interacting with location-based services (LBSs) leaves an almost indelible digital trace of users' whereabouts. Moreover, the contextual information attached to these traces can reveal users' personal habits, interests, activities, and relationships. Consequently, exposure of this private information to third parties (such as service providers) escalates their power on individuals, and opens the door to various misuses of users' personal data. Individuals have the right, and should also have the means to control the amount of their private (location) information that is disclosed to others. In the context of location-based services, various privacy enhancing mechanisms, such as location obfuscation and user anonymization, are proposed in the literature. However, the existing design methodologies for location-privacy preserving mechanisms do not consistently model users' (privacy and service quality) requirements together with the adversary's knowledge and objectives. Protection mechanisms are instead designed in an ad hoc manner and irrespective of the adversary model. Consequently, there is a mismatch between the goals and results of these protection mechanisms. Furthermore, the evaluation of privacy preserving mechanisms and their comparison remain problematic because of the absence of a systematic method to quantify them. In particular, the assumptions about the adversary model tend to be incomplete, with the risk of a possibly wrong estimation of the users’ location privacy. Arguably, the lack of a generic analytical framework for specifying protection mechanisms and for evaluating location privacy is evident. The absence of such a framework makes the design of effective protection mechanisms and the objective comparisons between them impossible. In this thesis, we address these issues and provide solutions for a systematic quantification and protection of location privacy. To this end, we construct an analytic framework for location privacy. We formalize users' mobility model, their access pattern to location-based services, and their privacy and service quality requirements. We also model location-privacy preserving mechanisms as probabilistic functions that obfuscate users' (location and identity) information before being shared with location-based services. Moreover, in order to quantify users' location privacy, we propose inference mechanisms that measure users' information leakage to third parties. They combine various pieces of information about users and estimate (by establishing a probabilistic belief on) users' private information (e.g., their location at a given time). Therefore, we propose the adversary's expected estimation error as, arguably, the right metric for location privacy. In our inference framework, we formalize the adversary's prior knowledge on users, his observation (on the users' accesses to LBS), and his inference objectives (e.g., re-identifying or localizing users). We assume that adversary constructs a (mobility) profile for each user, to be used in his inference attacks. We make use of statistical tools to construct these profiles, given users' partial traces. Moreover, we model the inference attacks as the estimation of users' actual locations, given their profiles and their LBS accesses (observed by the adversary). We mainly use Bayesian inference to perform the estimation. In particular, we use known inference algorithms for hidden Markov models to design de-anonymization, localization, and tracking attacks. To cover more adversary's objectives, we propose an algorithm for generic location inference attacks, based on Markov-chain Monte-Carlo methods. We also provide a software tool: the Location-Privacy and Mobility Meter (LPM). It is designed based on our formal framework for evaluating the effectiveness of various location-privacy preserving mechanisms and quantifying users' location privacy. As an example, using LPM, we validate the efficacy of existing location obfuscation and anonymization mechanisms on real location traces. We show that other metrics (k-anonymity and entropy) are not correlated with the adversary's success (in learning users' private information), thus are inappropriate as privacy metrics. Our results also confirm that anonymization alone is a weak location-privacy preserving mechanism. Moreover, our results show how the resilience of a protection mechanism varies with respect to different inference attacks. Hence, it is a necessity for privacy protection mechanisms to be designed with concrete attack objectives in mind. Relying on these findings, we design optimal location obfuscation techniques tailored against localization attacks. A user needs a protection mechanism that maximizes her location privacy. This is at odds with the objectives of the adversary who designs inference attacks that minimize his estimation error. We propose a game-theoretic methodology that models the conflicting objectives of user and adversary simultaneously. More precisely, we model the problem as a Bayesian Stackelberg game and solve it by using linear programming. In the optimization problem, users constrain the protection mechanism to respect their service quality requirements. This enables us to find the optimal point in the tradeoff curve between privacy and service quality that satisfies both user privacy and service quality requirements. Our results indicate that anticipating for the inference attacks and considering the adversary's knowledge lead to the design of more effective protection mechanisms. This thesis is a step towards a more systematic modeling, analysis, and design of (location) privacy enhancing technologies. We believe that our analytical approach can be used to quantify and protect privacy in scenarios and domains that are not covered in this thesis.