MobiHoc 2007

Protecting Location Privacy in Mobile Computing Systems: Architecture and Algorithms

Ling Liu, Georgia Tech, USA


With the rapid development in positioning technologies such as GPS, GSM, RFID, and WiFi (802.11) and the wide deployment of wireless local area networks (WLAN), many devices today are equipped with wireless communication capabilities and location-awareness. These new technologies have enabled a new class of applications, known as Location-Based Services (LBSs). While location-based services (LBSs) hold the promise of new business opportunities and a wide range of life enhancing services, the ability to locate users and mobile objects accurately also opens door for new threats - intrusion of location privacy. Location privacy threats refer to the risks that an adversary can obtain unauthorized access to raw location data, derived or computed location information by locating a transmitting device, hijacking the location transmission channel, and identifying the subject (person) using the device.

Location privacy refers to the ability to prevent other unauthorized parties from learning one's current or past location. In LBSs, there are conceivably two types of location privacy - personal subscriber level privacy and corporate enterprise-level privacy. Extensive deployment of location-based services without safeguards may endanger location privacy of mobile users due to significant vulnerabilities for abuse. For example, location information can be used to spam users with unwanted advertisements or to learn about users, medical conditions, alternative lifestyles or unpopular political views. Inferences can be drawn from visits to clinics, doctor offices, entertainment districts, or political events. In extreme cases, public location information can lead to physical harm, for example in stalking or domestic abuse scenarios.

Location privacy has attracted attention by the research community in the recent couple of years. Most of the solutions proposed so far are focused on dealing with location privacy protection under a uniform assumption (i.e., all mobile users have similar location privacy requirements). Very few have studied personalized privacy protection strategies and have provided qualitative and quantitative analysis of the inherent tradeoff between the utility that LBSs can offer and the location privacy they afford to risk. Furthermore, there is an inherent tradeoff between the utility that LBSs can offer and the location privacy they afford to risk. On one hand, the quality of an LBS depends on the accuracy of the location of mobile users, and on the other hand, the more accurate the location information is disclosed, the higher risk of location privacy being invaded. It is important to develop mechanisms that can help finding an acceptable balance between the extreme of fully disclosure and completely withheld of location data. In this tutorial we present an in-depth description of location privacy and privacy-aware location-based services in mobile information systems, with the emphasis on architectures, concepts, and techniques.

Tutorial Content (3 hours)

1. Motivation: Applications and Requirements (0.5 hours)

First, we motivate the need for location privacy in future mobile and ubiquitous computing environments and address different requirements for protecting location privacy. We also define the concept of location privacy, and discuss the tradeoffs between the utility of locations, the quality of service provided by the LBS, and the desired location privacy of the user, and how to reach such a tradeoff through location cloaking mechanisms.

(1) Location Privacy and Location Service Quality

In mobile computing environments, location-based applications track people's movement so they can offer various location-dependent services. Users who do not want such services should be given the choice of refusing to be tracked and thus maintain their location privacy. Of course, if a user provides little location information to the service provider, the risk of her privacy being compromised will be significantly reduced. However, this may prevent an LBS from providing the best service to the user. Alternatively, before contacting the LBS provider, a user can have her location information filtered by reducing its precision/resolution in terms of time and space. An important question is how much privacy protection is necessary. Perfect privacy is clearly impossible as long as communication takes place. Moreover, different users may have varying privacy needs in different contexts. Therefore, it is important to develop customizable privacy protection mechanisms that can help users finding a comfortable balance between the extreme of fully disclosed and completely withheld location data. This includes the qualitative and quantitative analysis of the inherent tradeoff between the quality of service provided by the LBS and the desired location privacy of the user, and how fuzzy the location information sent by a mobile user to the LBS can be in order to reach such a tradeoff.

(2) Location Privacy and Personalization

We argue that location privacy is context sensitive. Different users may require different levels of privacy at different times. A user's willingness to share location data may depend on a range of factors, including different contextual information about the user (such as environmental context, task context, social context, etc.). Thus, ``one size fits all'' framework for location privacy does not work. We promote user-defined privacy rules combined with a personalized anonymization model since it allows users to tailor the system-level privacy protection strategies to meet their personal privacy preferences.

2. Protecting Location Privacy: Policy-based Model v.s. Location Anonymization (1 hour)

Several approaches have been proposed for protecting location privacy of a user. Most of them try to prevent disclosure of unnecessary information by techniques that explicitly or implicitly control what information is given to whom and when. These techniques can be classified into three categories:

  1. Location protection through user-defined or system-supplied privacy policies;
  2. Location protection through anonymous usage of information, such as location cloaking, by reducing temporal and spatial resolutions of location information; and
  3. Location protection through pseudonymity of user identities, which uses an internal pseudonym rather than the user’s actual identity. Such pseudonyms should be different for different services and frequently changing to prevent applications tracking them. More importantly, such pseudonyms should be generated in such a manner that makes the linking between the old and the new pseudonym very hard.

Some location-based services can operate completely anonymously, such as ``when I pass a gas station, alert me with the unit price of the gas". Others can not work without the user's identity, such as ``when I am inside the office building, let my colleagues find out where I am". Between these two extremes are those applications that cannot be accessed anonymously but do not require the user's true identity, such as ``when I walk past a computer screen, let me teleport my desktop to it". Here, the application must know whose desktop to teleport but it could do this using an internal pseudonym rather than the user's true identity. For those LBSs that require our true identity, strong security mechanisms, such as location authentication and authorization, have to be enforced in conjunction with their location privacy policy.

In this tutorial we will give an overview of two types of location privacy protection strategies: Policy-based models and anonymity-based models, describe different classes of location privacy threats, and provide an overview of the possible techniques and solutions for location privacy protection. We will describe the design and development of a secure and customizable architecture for privacy-aware location-based services, which provides a careful combination of policy-based location privacy mechanisms and location anonymization based privacy schemes. In the policy-based approach, mobile subscribers need to evaluate and choose privacy policies offered by the service provider. These policies serve as a contractual agreement about which data can be collected, for what purpose the data can be used, and how it can be distributed. Typically the mobile subscribers have to trust the service provider that private data is adequately protected. In contrast, the anonymity-based approach de-personalizes data before it is dispatched to service providers. Thus it can provide a high degree of privacy, save users from dealing with service providers’ privacy policies, and reduce the service providers’ requirements for safeguarding private information. However, guaranteeing anonymous usage of location services requires that the precise location information transmitted by a user cannot be easily used to re-identify the subject. One common way to anonymize location information is to provide location k-anonymity by location cloaking, which reduces temporal and spatial resolutions of location information.

3. Location k-anonymity and Location Privacy (1 hour)

The concept of k-anonymity is originally introduced in the context of relational data privacy research. In the context of LBSs and mobile users, location k-anonymity refers to k-anonymous usage of location information. A larger k indicates more difficulty in linking a location to a particular user. This uncertainty will increase with the increasing value of k. Users can specify the value of k in her location privacy policy as a parameter to control her desired level of privacy. Location perturbation is an effective technique for implementing location k-anonymity. Two fundamental questions are raised frequently with location k-anonymity: (1) how large the value of k should be? and (2) should we use different k values for different users or even different service requests of the same user (context sensitivity)? We argue that there is a close synergy between location privacy and location k-anonymity. Larger k in location anonymity usually implies higher guarantees for location privacy. We will present the design of several personalized anonymization models and location cloaking algorithms, and discuss issues such as safeguards for secure transmission, use and storage of location information, reducing the risks of unauthorized disclosure of location information. We also describe our impact study on both the performance of the system and the quality of service by incorporating different location privacy protection strategies into the proposed distributed location service middleware architecture.

4. Privacy and Security of Location Information (05. hours)

Security and privacy are two dimensions of the safety problem in future mobile and ubiquitous computing systems. I will discuss the intrinsic relationships between location security and location privacy, in terms of requirements, potential risks and defense mechanisms, and how the solutions to these problems will impact the future mobile computing systems, services, and applications.

Audience and Prerequisite Knowledge

The tutorial presents the necessary concepts, architectures, techniques, and infrastructure to understand location privacy in mobile location-based services (LBSs). The tutorial is designed to be self-contained, and gives the essential background for anyone interested in learning about the concept of location privacy, and the principles for design and development of a secure and customizable architecture for privacy-aware location-based services. This tutorial will guide the researchers, graduate students, and practitioners by highlighting best practices in building scalable and privacy-aware distributed location based services, including the location utility and location privacy trade-offs, the limitations of current approaches, the need for a careful combination of policy-based location privacy mechanisms and location anonymization based privacy schemes, as well as the set of safeguards for secure transmission, use and storage of location information, reducing the risks of unauthorized disclosure of location information. This tutorial is presented at a senior graduate student level and is accessible to data management administrators, advanced mobile location based service developers, and graduate students who are interested in mobile information systems, pervasive computing, and data privacy.

Biography of Presenter

Dr. Ling Liu is an Associate Professor in the College of Computing at Georgia Institute of Technology. There she directs the research programs in Distributed Data Intensive Systems Lab (DiSL), examining performance, security, privacy, and data management issues in building large scale distributed computing systems. Dr. Liu and the DiSL research group have been working on various aspects of distributed data intensive systems, ranging from decentralized overlay networks, mobile computing and location based services, sensor network and event stream processing, to service oriented computing and architectures. She has published over 150 international journal and conference articles in the areas of Internet Computing systems, Internet data management, distributed systems, and information security. Her research group has produced a number of open source software systems, among which the most popular ones include WebCQ, XWRAPElite, PeerCrawl. She has chaired a number of conferences as a PC chair, vice PC chair, or a general chair, including IEEE International Conference on Data Engineering (ICDE 2004, ICDE 2006, ICDE 2007), IEEE International Conference on Distributed Computing (ICDCS 2006), IEEE International Conference on Web Services (ICWS 2004), ACM International Conference on Knowledge and Information Management (CIKM 2000). Dr. Liu is currently on the editorial board of several international journals, including IEEE Transactions on Knowledge and Data Engineering, International Journal of Very Large Database systems (VLDBJ), Wireless Network Journal (WINET), International Journal of Peer-to-Peer Networking and Applications (Springer), International Journal of Web Services Research. Dr. Liu is the recipient of the best paper award of ICDCS 2003 and the best paper award of WWW 2004, a recipient of 2005 Pat Goldberg Memorial Best Paper Award, and a recipient of IBM faculty award in 2003 and 2006. Dr. Liu’s research is primarily sponsored by NSF, DARPA, DoE, and IBM.

 Acknowledgement: This work is partially funded by the NSF CyberTrust Program.

Last modified 12-05-2007