隐私保护框架-PIRI.docx

Article
A privacy-aware framework for participatory sensing.
Leyla Kazemi, Cyrus Shahabi
SIGKDD Explorations 01/2011; 13:43-51. DOI:10.1145/2031331.2031337
Source: DBLP
ABSTRACT  With the abundance and ubiquity of mobile devices, a new class of applications is emerging, called participatory sensing (PS), where people can contribute data (e.g., images, video) collected by their mobile devices to central data servers. However, privacy concerns are becoming a major impediment in the success of many participatory sensing systems. While several privacy preserving techniques exist in the context of conventional location-based services, they are not directly applicable to the PS systems because of the extra information that the PS systems can collect from their participants.
In this paper, we formally define the problem of privacy in PS systems and identify its unique challenges assuming an un-trusted central data server model. We propose PiRi, a privacy-aware framework for PS systems, which enables participation of the users without compromising their privacy. Our extensive experiments verify the efficiency of our approach.
[more]

Intr0duce
1. With the advent of mobile technology, the area of participatory sensing (PS) [6] has attracted many researchers in different domains such as public health, urban planning, and traffic. The goal is to leverage sensor equipped mobile devices to collect and share data, which can later be utilized for analysis, mining, prediction or any other type of data processing. While many unsolicited PS systems exist (e.g., Flickr, Youtube), in which users participate by arbitrarily collecting data, other PS systems are campaign-based, which require a coordinated effort of the participants to collect a particular set of data that the server requires for any purpose. Some real-world examples of PS campaigns include [15; 20; 2], where users leverage their mobile devices to collect traffic information. In CycleSense [1], bikers document their trajectories along with other data modalities (e.g., pollution, traffic, accidents). In [24], the focus is on participatory texture documentation, where users, in a coordinated effort, aim to collect maximum amount of urban texture in- formation from a set of predefined locations. However, privacy concerns are the significant barriers to the success of any participatory sensing campaign, which delay the progress of massive deployment of such systems. Consider a scenario where the goal of the PS campaign is to collect pictures/videos from the anti-government riots at different locations of a city with the coordinated effort of the participants. Accordingly, each participant u should query the server for the set of closeby locations from which data (e.g., picture, video, temperature) needs to be collected (termed data collection points or DC-points). These are the DC- points that are closer to u than to any other participant. However, u may not be willing to disclose his identity due to safety reasons. An alternative is that u sends his query to a trusted server, known as anonymizer. The anonymizer removes the user’s ID from the query and forwards the query to the server. However, the server requires u’s location information to answer the query. Due to the strong correlation between people and their movements (see [12]), a malicious server can identify u by associating his location information to u.

For example, if u issues the query from his home, his identity can be easily revealed by linking the home address to u using the online white page services. Thus, the server can identify a query issuer by associating the query to the location from which the query is issued. We refer to this process as a location-based attack. Our goal in this paper is to protect the campaign participants from location-based attacks by disassociating a query from the query location. Existing privacy preserving techniques have been proposed to address these concerns in the context of location-based services (LBS) [18; 21; 7], one of which is spatial K-anonymity (SKA). The idea behind SKA is that user blurs his location among K-1 other users, such that the probability of identifying the query issuer does not exceed 1/K, even if in the worst case all the user locations are known to the adversary. The existing studies on cloaking techniques are classified into three categories: centralized, distributed, and peer-to-peer, of which the first two are not applicable to the highly ad-hoc mobile P2P environments because of their reliance on a fixed communication infrastructure and centralized/distributed servers. Thus, we focus on SKA approaches in P2P environments. Unfortunately, certain characteristics of a PS campaign distinguish it from conventional LBS, and therefore, prevent a direct adaption of SKA to such systems. One characteristic of a PS campaign is that in order to collect data through a coordinated effort, all the participants query the PS server for the closeby DC-points. This is in contrast to LBS which serves millions of users from which any arbitrary subset of them might ask query at a given time and location. We refer to this as the all-inclusivity property. Another characteristic of a PS campaign, is that each participant queries for all the DC-points, which are closer to him than to any other participant. Thus, the second property of the PS campaign is that each participant asks a range query from the server
Page 2
which is dependent on the location of other users. We refer to this property as range dependency. These two properties, which reveal extra information to the server as compared to the conventional LBS, introduce major privacy leaks to the system. Thus, the system becomes unresilient to location- based attacks. In this paper, we devise a privacy-aware framework for PS campaigns, which addresses these two major privacy leaks. Our approach, termed PiRi has the two following properties: Partial-inclusivity and Range independence. PiRi is based on the observation that the range queries sent by participants have significant overlaps. Therefore, instead of each participant asking a separate query, only a group of the representative participants ask queries from the server, and share their results with those who have not posed any query. Moreover, instead of each participant submitting a range query, which is dependent on other participants’ locations, we propose an adjustment technique that adjusts the range query such that the query becomes independent of the others. A preliminary version of this work appeared as a short paper in [17], where the privacy problem in PS systems was introduced, and the PiRi approach was briefly discussed. This article subsumes [17] by delving into more details of the proposed approach as well as defining a new metric for quantifying the privacy leak in the PS campaigns, with which we can measure the resilience of our system to location-based attacks.

Finally, in this paper we include our experimental studies that show the efficacy of our approach. Our extensive experiments show that our PiRi approach is 98% more resilient to such attacks, while the extra communication cost is tolerable.

The remainder of this paper is organized as follows.
Section 2 reviews the related work.
In Section 3, we discuss some background studies, formally define our problem, and discuss our system model.
Thereafter, in Section 4 we explain our PiRi approach.
Section 5 presents the experimental results.
Finally, in Section 7 we conclude and discuss the future directions of this study.

2. related work

Privacy preserving techniques have been studied in the context of location-based services. One category of techniques [9; 26; 18] focuses on evaluating the query in a transformed space, where both the data and query are encrypted, and their spatial relationship is preserved to answer the location- based query. However, many of the transformation tech- niques fail to guarantee practical query accuracy. Another group of well-known techniques in preserving users’ privacy is the spatial cloaking technique [10; 7; 4; 8; 21; 16], where the user’s location is blurred in a cloaked area, while satisfying the user’s privacy requirements. An example of spatial cloaking is the spatial K-anonymity (SKA) [25], where the location of the user is cloaked among K-1 other users. While any of the privacy preserving techniques can be utilized to protect the users’ privacy,

in this paper without loss of generality we use cloaking techniques due to the following reasons: 1) accuracy and 2) popularity in different environments (i.e, centralized, distributed, peer to peer).
Most of the SKA techniques assume a centralized architecture [4; 8; 21; 16], which utilizes a trusted third party known as location anonymizer. The anonymizer is responsible for first cloaking user’s location in an area, while satisfying the user’s privacy requirements, and then contacting the location-based server. The server computes the result based on the cloaked region rather than the user’s exact location. Thus, the result might contain false hits.
The centralized approach has two drawbacks. First, the centralized approach does not scale because the users should repeatedly report their location to the anonymizer. the users’ locations, the anonymizer becomes a single point for attacks.To address these shortcomings, recent tech- niques [10] focus on distributed environments, where the users employ some complex data structures to anonymize their location among themselves via fixed infrastructures (e.g., base stations). However, because of high update cost, these approaches are not designed for the cases where users frequently move or join/leave the system. Therefore, alternative approaches have been proposed [7] for unstructured peer-to-peer networks where users cloak their location in a region by communicating with their neighboring peers with- out requiring a shared data structure.
In this paper, we employ the P2P spatial cloaking techniques to hide the user’s location when querying the PS server.
Despite all the studies about privacy in the context of LBS, only a few work [14; 23; 13] have studied privacy in participatory sensing. In [23], the concept of participatory privacy regulation is introduced, which allows the participants to decide the limits of disclosure. Moreover, in [14; 13], differ- ent approaches are proposed, which focus on preserving privacy in a PS campaign during the data contribution, rather than the coordination phase. That is, these approaches deal with how participants upload the collected data to the server without revealing their identity, whereas our focus is on how to privately assign a set of data collection points to each participant. The combination of private data assignment and private data contribution forms an end-to-end privacy-aware framework for the PS systems.
3 Preliminaries
3.1 Background
As discussed in Section 2, we start by using the P2P SKA to address the privacy problem in participatory sensing. Here, we provide a background on the P2P SKA approach. The idea of P2P SKA approach (see [7]) is that a user communicates with his neighboring peers via multihop routing to find at least K-1 other peers. Each user has two privacy requirements: K, and A. K is the minimum number of users in the cloaked region, and A is the minimum area of the cloaked region. After satisfying the K-anonymity requirement, the user extends the cloaked region to A, so that the minimum area privacy requirement is also satisfied. Consequently, the user sends his spatial query along with the cloaked region to the server. The server is equipped with a privacy-aware query processor, which computes a minimal answer set that contains the user’s exact result. After receiving the answer set from the server, the user refines the answer set to retrieve the exact result.

Figure 1 illustrates an example of a privacy-aware range query, where user U1 issues a query with K = 4 and a radius of 3 (i.e., r = 3). He first collaborates with his neighbors through multi-hop routing to form the cloaked region with 3 other peers. After sending the cloaked region (solid lined rectangle) along with the range query to the server, the query processor determines the minimal answer set (i.e., the answer to the range query for every point in the cloaked region). The reason is that the server does not know which of the 4 users asked the query. According to [7], the minimal answer set includes all the objects inside the region as well as all the objects within the radius of 3 from every point on the edges of the cloaked region (i.e., all the objects inside the dotted line rectangle).
This guarantees no missing hits, but probably includes some false hits. Consequently, once U1 receives the answer set, he can refine it to retrieve all the objects within the radius of 3 from his location.

3.2 Formal Problem Definition
A major focus in the PS campaign is to design a framework in which each participant is assigned to a set of data collection points (DC-points), where data should be collected. In this section, we formally define this problem.
Definition 1 (Participatory Assignment).
Given a campaign C(P,U) ∈ R2, with P as the set of DC-points, and U as the set of participants, the Participatory Assignment (PA) problem is to assign to each participant u ∈ U any DC-point p ∈ P, such that p is closer to u than to any other participant in U.
Note that for simplification, we define the assignment problem for a given snapshot of time and location. we do not assume the participants move during the assignment. This seems intuitive, since participants usually plan their paths from their residential location (e.g., home, office) before starting their movement. Moreover, participants are the current active users of the system willing to participate in the process.
In order to solve the PA problem, a straightforward solution is that each participant sends his location to the server. The server then assigns to each participant the set of DC- points close to him by computing the Voronoi diagram of the participants.

Figure 2 depicts such scenario. The formal definition of the Voronoi diagram is as follows.
Definition 2(Voronoi Diagram).
Given an environment E(U) ∈ R2, with U as the set of participants, the Voronoi diagram of U is a partitioning of E into a set of cells, where each cell Vu belongs to a participant u, and any point p ∈ E in the cell Vu is closer to u than to any other participants in the environment. Here, the closeness between two points is defined in terms of Euclidean distance.
Once the server computes the Voronoi diagram of the participants, it forwards to each participant u, all the DC-points lying inside the corresponding cell Vu. However, in many scenarios the server is not trusted, and therefore, a participant may not be willing to r