A Privacy Preserving and Collusion Resistance in a Location Proof Updating System

A Privacy Preserving and Collusion Resistance in a Location Proof Updating System

Sanjay M Nandeeswar S. B

4th Sem M.Tech, Asst.Professor

Apsce, Bangalore Apsce, Bangalore

AbstractIn todays world location-sensitive service presents on users mobile device in order to determine the current location. But some malicious users may access a restricted resource or provide bogus location details by cheating on their locations. To address this issue, we propose A Privacy-Preserving Location proof Updating System (APPLAUS) in which colocated Bluetooth enabled mobile devices mutually generate location proofs and send updates to a location proof server. Mobile devices use the Periodically changed pseudonyms to protect source location privacy from each other, and from the untrusted location proof server. We also develop user-centric location privacy model in which individual users evaluate their location privacy levels and decide whether and when to accept the location proof requests. In order to defend against colluding attacks, we also present betweenness ranking-based and correlation clustering-based approaches for outlier detection. APPLAUS can be implemented with existing network infrastructure, and can be easily deployed in Bluetooth enabled mobile devices with little computation or power cost. Extensive experimental results show that APPLAUS can effectively provide location proofs, significantly preserve the source location privacy, and effectively detect colluding attacks.

Index TermsLocation-based service, location proof, location privacy, pseudonym, colluding attacks

1 INTRODUCTION

Nowadays, more and more location-based applications and services require users to provide location proofs at a particular time. For example, Google Latitude and Loopt are two services that enable users to track their friends locations in real time. These applications are location-sensitive since location proof plays a critical role in enabling these applications.

Location-Based Services (LBSs) can be classified into various categories based on their functionality. Examples of LBS applications include navigation (directions, traffic control), information (travel and tourist guides), tracking (people, vehicle or product tracking), emergency (police, ambulance), advertising (advertisement alerts), billing (road tolls), and social networking (locating friends,

instant messaging). Controlled disclosure of location information is important for some of these applications. For example, a service like advertisement alert or travel and tourist guides may need to verify

legitimate use but may not need other personal information about the user requesting the service. Privacy issues are not important for such applications. Some services may need location information of the requester but not his exact identity. Examples include navigation and road tolling services. Privacy is also not important for such services. Other services, such as, people tracking and social networking, need both the identity of the user as well as his exact location. Controlled disclosure of location information is critical for such applications. We focus on this category of applications and show how location information of a user can be disclosed such that it respects his privacy. The notion of privacy varies from one individual to another. One individual may be willing to disclose his location to his co-workers while he is on vacation, whereas another individual may not want to do so.

Location-sensitive application requires user to prove that they really are (or were) at the claimed locations. Although most mobile users have devices capable of discovering their locations, some users may cheat on their locations and there is a lack of secure mechanism to provide their current or past locations to applications and services. One possible solution is to build a trusted computing module on each mobile device to make sure trusted GPS data is generated and transmitted. For example, Lenders et al. proposed such a solution which can be used to generate unforgeable geotags for mobile content such as photos and video; however, it relies on the expensive trusted computing module on mobile devices to generate proofs. Although cellular service providers have tracking services that can help verify the locations of mobile users in real time, the accuracy is not good enough and the location history cannot be verified.

Recently, several systems have been designed to let end users prove their locations through WiFi infrastructures. For example, Saroiu and Wolman proposed a solution suitable for third-party attestation, but it relies on PKI and the wide deployment of WiFi infrastructure.

In this paper, we propose A Privacy- Preserving Loca-tion proof Updating System (APPLAUS), which does not rely on the wide deployment of network infrastructure or the expensive trusted computing module. In APPLAUS, Bluietooth enabled mobile devices in

range mutually generate location proofs,

which are uploaded to a untrusted location proof server that can verify the trust level of each location proof. An authorized verifier can query and retrieve location proofs from the server. Moreover, our location proof system guarantees user location privacy from every party. More specifically, we use statistically updated pseudonyms at each mobile device to protect location privacy from each other, and from the untrusted location proof server. We develop a user-centric location privacy model in which individual users evaluate their location privacy levels in real time and decide whether and when to accept a location proof request. In order to defend against colluding attacks, we also present betweenness ranking-based and correlation clustering-based approaches for outlier detection. Extensive experimental and simula-tion results based on multiple data sets show that APPLAUS can effectively provide location proofs, signifi-cantly preserve the source location privacy, and effectively detect colluding attacks.

The rest of the paper is organized as follows: We first introduce preliminaries of our scheme in Section 2, and then present our location proof updating scheme in Section 3. Section and Section 4 discusses colluding attacks and countermensures. The performance of our scheme is evaluated in Section 5. Finally, we describe related work in Section 6 and conclude the paper in Section 7.

1. PRELIMINARIES

   In this paper, we focus on mobile networks where mobile devices such as cellular phones communicate with each other through Bluetooth. In our implementation, mobile devices periodically initiate location proof requests

   to all neighboring devices through Bluetooth. After receiving a request, a mobile node decides whether to exchange location proof, based on its own location proof updating requirement and its own privacy consideration. Given its appropriate range (about 10 m) and low power consump-tion, Bluetooth is a natural choice for mutual encounters and location proof exchange.

   1. Pseudonym

      As commonly used in many networks, we consider an online Certification Authority (CA) run by independent trusted third party which can preestablish credentials for the mobile devices. Similar to many pseudonym approaches, to protect location privacy, every mobile node i registers with the CA by preloading a set of M public/private key pairs KPub; KPrvM before entering the network. The public key KPub is used to serve as the pseudonym of node i. The private key KPrv enables node i to digitally sign messages so that the receiver can validate the signature authenticity.

      Due t the broadcast nature of wireless communication, probes are used for mobile nodes to discover their neighbors. When a node i receives a probe from another node, it checks the certificate of the public key of the sender and the physical identity, e.g., Bluetooth MAC address. After that, i verifies the signature of the probe message. Subsequently, if confidentiality is required, a security association is established (e.g., with Diffie-Hellman).

   2. Threat Model

      We assume that an adversary aims to track the location of a mobile node. An adversary can have the same credential as a mobile node and is equipped to eavesdrop communications. We assume that the adversary is internal, passive, and global. By internal, we mean that the adversary is able to compromise or control individual mobile device and then communicate with others to explore private information, or individual devices may collude with each other to generate false proofs, which will be discussed in detail in Section 5. We assume that the number of colluders is small compared with that of valid devices. In the worst case, the adversary could compromise the location proof server to get

      the stored location proof records. However, it is not able to take control of the server to work as a colluder, since once compromised, the attack will be detected promptly and the location proof server will be replaced by a back-up server. The same assumption applies to the CA. By passive, we assume the adversary cannot perform active channel jamming, mobile worm attacks or other denial-of- service attacks, since these attacks are not related to location privacy. By global, we assume the adversary can monitor, eavesdrop, and analyze all the traffic in its neighboring area, or even monitor all the traffic around the server.

      In practice, the adversary can thus be a rogue individual, a set of malicious mobile nodes, or eavesdrop-ping devices in the network. In the worst case, it is possible that the untrusted location proof server may be compro-mised by the adversary and the location information can then be easily inferred by examining the records of location proofs, e.g., the adversary could apply statistical testing such as K-S test to identify a user although no real identity is included. Therefore, we need to appropriately design and arrange the location proof records in the untrusted server so that no private information related to individual users will be revealed even after it is compromised. Hence, the problem we address in this paper consists of collecting a set of location proofs for each peer node and protecting the location privacy of peer nodes from each other, from the adversary, or even from the untrusted location proof server to prevent other parties from learning a nodes past and current location information.

   3. Location Privacy Level

      In this paper, we use multiple pseudonyms to preserve location privacy; i.e., mobile nodes periodically change the pseudonym used to sign messages, thus reducing their long term linkability. To avoid spatial correlation of their location, mobile nodes in proximity coordinate pseudonym changes by using silent mix zones or regions where the adversary has no coverage. Without loss of generality, we assume each node changes its pseudonyms from time to time according to its privacy requirement. If this node changes its pseudonym at least once during a time period (mix zone), a mix of its identity and location occurs, and the

      mix zone becomes a confusion point for the adversary.

      Consider a mobile network composed of N mobile nodes and each node has M pseudonyms. At time t, for each node i there are a group of mðtÞ pseudonyms observed at the location proof server. Each pseudonym among the mðtÞ pseudonyms can involve multiple location proofs across various locations l1; l2; .. . ; ln at different time t1; t2; . . . ; tn. An adversary is able to correlate the location and time distribution of each pseudonym to see if two pseudonyms belong to the same node. For example, the adversary can observe a series of location proofs with mðT Þ pseudonyms during time T . He then compares the distribution of location proof set B of pseudonym b with the distribution of location proof set D of pseudonym d to determine if the two pseudonyms can be linked. Let pd¼b ¼ Pr (distribution D of pseudonym corresponds to distribution B of pseudonym b), the location privacy level of node i (i.e., the uncertainty of the adversary) at time T , is

      The achievable location privacy depends on the number of nodes (mðT Þ) and the unpredictability of their where-abouts in the mix zone (pdjb). If a node i has only one pseudonym observed till time T , its identity is known to the adversary and its location privacy level is defined to be EiðT Þ

      ¼ 0. We can achieve the maximum entropy when every pd¼b is close to 0; i.e., the distribution of location proofs for each pseudonym is undistinguishable.

      Fig. 1. Location proof updating architecture and message flow.

2. THE LOCATION PROOF UPDATING

   SYSTEM

   In this section, we introduce the location proof updating architecture, the protocol, and how mobile nodes schedule their location proof updating to achieve location privacy in APPLAUS.

   1. Architecture

      In APPLAUS, mobile nodes communicate with neighboring nodes through Bluetooth, and communicate with the untrusted server through the cellular network interface. Based on different roles they play in the process of location proof updating, they are categorized as Prover, Witness, Location Proof Server, Certificate Authority or Verifier. The architecture and message flow of APPLAUS is shown in Fig. 1.

      . Prover: the node who needs to collect location proofs from its neighboring nodes. When a location proof is needed at time t, the prover will broadcast a location proof request to its neighboring nodes through Bluetooth. If no positive response is received, the prover will generate a dummy location proof and submit it to the location proof server.

      . Witness: Once a neighboring node agrees to provide location proof for the prover, this node becomes a witness of the prover. The witness node will generate a location proof and send it back to the prover.

      . Location proof server: As our goal is not only to monitor real-time locations, but also to retrieve history location proof information when needed, a location proof server is necessary for storing the history records of the location proofs. It commu-nicates directly with the prover nodes who submit their location proofs. As the source identities of the location proofs are stored as pseudonyms, the location proof server is untrusted in the sense that even though it is compromised and monitored by attackers, it is impossible for the attacker to reveal the real source of the location proof.

      . Certificate authority: As commonly used in many networks, we consider an online CA which is run by an independent trusted third party. Every mobile node registers with the CA and pre-loads a set of public/private key pairs before entering the net-work.

      CA is the only party who knows the mapping between the real identity and pseudonyms (public keys), and works as a bridge between the verifier and the location proof server. It can retrieve location proof from the server and forward it to the verifier.

      . Verifier: a third-party user or an application who is authorized to verify a provers location within a specific time period. The verifier usually has close relationship with the prover, e.g., friends or collea-gues, to be trusted enough to gain authorization.

   2. Protocol

      When a prover needs to collect location proofs at time t, it executes the protocol in Fig. 2 to obtain location proofs from the neighboring nodes within its Bluetooth communication range. Each node uses its M pseudonyms PMi=1 as its identity throughout the communication.

      Fig. 2. Location proof updating protocol

      1. The prover broadcasts a location proof request to its neighboring noes through Bluetooth according to its update scheduling. The request should contain the provers current pseudonym Pprov, and a random number Rprov.

      2. The witness decides whether to accept the location proof request according to its witness scheduling. Once agreed, it will generate a location proof for both prover and itself and send the proof back to the prover. This location proof includes the provers pseudonym Pprov, provers random number Rprov, witnesss current time stamp Twitt, witnesss pseu-donym Pwitt, and their shared location L. This proof is signed and hashed by the witness to make sure that no attacker or prover can modify the location proof and the witness cannot deny this proof. It is also encrypted by the servers public key to prevent from traffic monitoring or eavesdropping.

      3. After receiving the location proof, the prover is responsible for submitting this proof to the location proof server. The message also

         includes provers pseudonym Pprov and random number Rprov, or its own location for verification purpose.

      4. An authorized verifier can query the CA for location proofs of a specific prover. This query contains a real identity and a time interval. The CA first authenticates the verifier, and then converts the real identity to its corresponding pseudonyms during that time period and retrieves their location proofs from the server. In order not to expose correlation between pseudonyms to the location server, CA will always collect enough queries from k different nodes before a set of queries are sent out.

      5. The location proof server only returns hashed location rather than the real location to the CA, who then forwards to the verifier. The verifier compares the hashed location with the claimed location acquired from the prover to decide if the claimed location is authentic.

      In order to prevent the CA from knowing locations of a real identity, the location proof server calculates the hash of each location and only sends the hashed locations to the CA in step 5. In this way, the following property can be achieved.

      The privacy property of our protocol is ensured by the separation of privacy knowledge: the location proof server only knows pseudonyms and locations, the CA only knows the mapping between the real identity and its pseudonyms, while the verifier only knows the real identity and its authorized locations. Attackers are unable to learn a users location information without integrating all the knowledge. Therefore, compromising either party of the system does not reveal privacy information.

   3. Scheduling Location Proof Updates

      As discussed before, the adversary may obtain complete coverage and track nodes throughout the entire network, by compromising the location proof server and obtain all history location proofs. Therefore, we need to appropriately design and arrange the location proof updating schedules for both prover and witness so that no source location information related to individual user is revealed even if the server is compromised.

      Suppose a mobile node i has a set of pseudonyms P1; P2; .. . ; PM which change periodically, and distinct parameters _1; _2; .. . ; _M for each pseudonym are prede-termined. If each pseudonym Pj updates its location proofs such that the interupdate interval follows Poisson distribu-tion with parameter _j, as shown in Fig. 3, then the entire interupdate intervals for node i follow Poisson distribution with a parameter of _ ¼ _1 þ

      _2 þ __ _ þ _M. As will be discussed in the next section, it has the properties of pseudonym unlinkability and statistically strong source location unobservability. The detailed scheduling protocol for the prover is shown in Algorithm 1. The predefined updating parameter _ determines how frequently location proofs are updated. In some cases, no location proof is generated when the location proof updating time arrives. To ensure that location proof updating follows the scheduled Poisson distribution, a dummy proof is gener-ated and submitted. The dummy proof has the same format as the real location proof and cannot be differentiated by the attackers.

      Fig. 3. Example of individual pseudonym update versus entire node update.

      The location privacy of witness nodes varies depending on the time and location when they exchange location proofs. It is thus desirable to protect the location privacy in a user-centric manner, such that each user can decide when and how to protect his location privacy. User- centric location privacy follows a distributed approach where each mobile node locally monitors its location privacy level over time. A network wide metric measures the average location privacy but may ignore that some nodes have low location privacy levels. However, the user centric approach is more scalable and can maintain location privacy at a more fine-grained level. In our model, the location privacy of a node may accumulate over time. It depends on the distribution diversity of the last pseudo- nym and its previous pseudonyms before the last success-ful pseudonym change. Each mobile node monitors and measures its own privacy level in real time and decides whether and when to accept a location proof exchange request. After receiving a location proof exchange request, it calculates the privacy loss between the next scheduled updating time and the current updating time. In this way, a node has autonomy to control the time period over which its location is tracked. The privacy loss of node i is defined as follows:

      where EiðtÞ is the location privacy level when the location proof exchange request is accepted while Eiðt0Þ is the location privacy level at the next scheduled location proof updating cycle. The difference between them indicates the privacy loss if this location proof request is accepted. The location proof request is only accepted when the privacy loss is less than a predefined threshold. The drawback of the user-centric model is that nodes may have misaligned incentives (i.e., different privacy requirement), which can lead to failed attempts to obtain enough location proofs. We use dummy proofs in Algorithm 1 to deal with failed attempts. The detailed scheduling protocol for witness is presented in Algorithm 2.

3. COLLUDING ATTACKS AND COUNTERMEASURES

The joint issues of location proof and location privacy have been studied in [33], but the threat of colluding attack is still an open issue. This threat exists when two nodes collude with each other to generate bogus location proofs. For example, when a dishonest node C1 from San Francisco needs to prove herself in New York City (NYC), she can have another colluding node C2 to generate bogus location proofs for her, with location tag of New York City. Generally speaking, such attacks can be identified by looking into the location traces and examining the interactions between colluders as well as the time and location consistency along the moving trajectory. We first consider statistical threshold based solution in which the system requires the prover to obtain a number of witness nodes, no matter what their real identities are. As we know, the location proof server has information about the number of pseudonyms at a particular time and location. This information can be used to estimate whether the prover lies about not finding enough peers or always finding the same peer based on some statistical techniques.

More specifically, the server-level detection is performed on individual location proof based on its embedded time stamp and location information, where all concurrent and co-located location proofs from other nodes (pseudonyms) are used to verify its trust level. For example in the normal case, as in Fig. 4a, PA is a legitimate prover who has received location proofs from all neighboring witness nodes PB, PE, and PF , except PG due to interference or synchronization reasons. Therefore, PA

has collected three location proofs (Nproof ¼ 3) from four neighbors (Nneighbor ¼ 4),and we denote the trust level of this location proof as T L= Nproof/N neighbor = 0:75. Since the trust level T L is higher than preselected threshold, PA is considered as a good node.

Fig. 4b illustrate a colluding case where node PA tries to claim her location in New York city with her colluders although she is not at NYC. Although PA finds a colluder PB who is located in NYC

to generate a fake location proof for her, it cant use other provers since she is not at NYC. The location proof server looks through the location proof records to check if there are other provers in PAs communication range. In this example, several other nodes (e.g., PE, PF , and PG) exist. It is easy to calculate the trust level of PAs location proof is T LPA ¼ 1=4 ¼ 0:25, which is below the threshold. Thus, PA is listed as suspicious to be malicious

Fig. 4. Threshold based verification. (a) all nodes are legitimate nodes. TLPA ¼ Nproof Nneighbor ¼ 0:75. (b) PA tries to claim her location in NYC with her colluders although she is not at NYC. PB is PAs colluder and witness. TLPA ¼ 1=4 ¼ 0:25, and PA is detected as malicious.

Calculating the trust level of a location proof involves the examination of its surrounding location proofs for both prover and witness, as well as large amount of redundant calculations between individual location proofs. To address this problem, we develop techniques that can perform verifications on a set of location proofs which are relevant in time and space, rather than individual proofs. We present two approaches to detect suspicious location proofs and pseudonyms: betweenness ranking and correlation clustering. The betweenness ranking approach calculates the between-ness of each pseudonym in a graph and then ranks these pseudonyms based on their betweenness value. The pseudonyms with low ranking are considered as suspicious nodes. The correlation clustering approach takes into account the time delay between two neighboring location proofs, and uses a modified correlation clustering algorithm on a temporal-weighted graph to rule out outlier clusters, which are considered as

suspicious location proofs. Both ap- proaches use undirected graph to reflect the relationship between pseudonyms or between location proofs.

1. Betweenness Ranking

   As the pseudonyms of each node keep changing, we dont have the contact patterns of individual nodes except their pseudonyms. Therefore, we can only verify pseudonyms that are relevant enough in both temporal and spatial domains. Considering all the concurrent (within 60 seconds delay) location proofs in a region, we first describe how to construct a pseudonym-correlation graph.

   Let s ¼ v0 and t ¼ vl. A path from s to t is defined as a sequence of edges ðvi; viþ1Þ, 0

   _ i _ l. The length of a path is the number of edges in the sequence. We use dðs; tÞ to denote the distance (the minimum length of any path connecting s and t in G) between s and t. With dði; iÞ ¼ 0, we have the following definition of betweenness:

   Betweenness is defined as the number of shortest paths from all vertices to all others that pass through node v. It is an indicator of who is the most influential node in the network (i.e., who interconnects with most others). As in Fig. 5a, there are seven shortest paths (v1 _ v5; v1 _ v6; v2 _ v5; v2 _ v6; v3 _ v5; v3 _ v6; v5 _ v6) pass through v4, the betweenness of node v4 can be calculated as Bðv4Þ ¼ 7 ð1Þ ¼ 7. Similarly, we can get Bðv5Þ ¼ Bðv6Þ ¼ 0. Ob-viously v5 and v6 have higher chance to be malicious node than v4. One notable feature of the definition is that the betweenness measurement gives very clear winners and losers among the nodes in the network: individuals with the highest betweenness are well ahead of

   those with the second highest, who are in turn well ahead of those with the third highest, and so on. Individuals with the lowest betweenness usually only connect to one or few neighbors. They are treated as outliers among all the nodes and thus most likely are colluding attackers.

   In Algorithm 3, n single-source shortest paths are first computed, for each s. The predecessor sets PsðwÞ are maintained during these computations. Next, for every s, using the information from the shortest path tree and predecessor sets along the paths, we can compute the dependencies _s0 ðvÞ for all other vertex v. To obtain the betweenness value of vertex v, we then calculate the sum of all

   Fig. 5. Examples of unweighted pseudonym-correlation graph and temporal-weighted proof-correlation graph.

   dependency values. The Oðn2Þ space requirements can be reduced to Oðn þ mÞ by maintaining a running betweenness score. This algorithm runs in OðnmÞ time for unweighted pseudonym-correlation graphs.

2. Correlation Clustering

   The above approach only considers two location proofs correlated if they occurred at the same time (e.g., within 60 seconds). However, in most case, a node may have to wait for a time period until its next location proof updating cycle. If the time delay between two location proofs is not too large, we should still consider them correlated. There-fore, if we consider each location proof as a vertex, we have the following definition of temporal-weighted proof-corre-lation graph.

   Fig. 5b shows one example of weighted proof-correlation graph. Location proof v1 and location proof v2 share the same prover node, so the edge between them is positive with weight of 1. On the other hand, location proof v5s prover is also location proof v6s witness, so the edge is negative. Our goal is to have location proofs with position edges grouped together (e.g., v1 and v2), and to separate the location proofs with negative edges (e.g., v5 and v6). The reason is intuitive: the location proofs with negative edges are abnormal, since within similar time interval and similar space, there should be another location proof consisting of v5s prover and v6s witness. Fig. 5b shows how correlation clustering works on the graph. Since this problem is NP-hard, we transfer the above proof-correlation graph to a double-labeled graph.

1. PERFORMANCE EVALUATIONS

In this section, we study the feasibility of deploying APPLAUS such as the computation and storage constraint, power consumption, and the proof exchange latency. We also use simulations to evaluate the performance of APPLAUS.

5.1 Prototype Implementation

To study the feasibility of our scheme, we have developed a prototype of APPALUS based o the technique presented in the previous sections. The prototype has two software components: client and server. The client is implemented in JAVA on Android Developer Phone 2 (ADP2), which is equipped with 528 MHz chipset, 512 MB ROM, 192 MB RAM, Bluetooth, and GPS module, and running Google Android 1.6 OS. It can communicate with the server anytime through AT&Ts 3G wireless data service. The server is implemented on a T4300 2.1 GHz 3 GB RAM laptop. It stores the uploaded location proof records and manages corresponding indices using MySQL 5.0. We use two android phones to communicate with each other to test our solution.

The client code consumes only 80 KB of

data memory. When running, less than

2.5 percent of the available memory is used. We measure the CPU utilization of our client code using a monitoring application, which allows one to monitor the CPU usage of all the processes running on the phone. When the application is in standby, the CPU utilization is about 0.5 percent, indicating that listening to incoming Bluetooth inquiries requires very low computa-tion. The CPU utilization goes to 3 and 5 percent, respectively,

when communicating with another device and with the server, due to using different communication interfaces. We observe that the CPU utilization reaches the highest level of 10 percent when a location proof packet is generated, in which heavy computations such as authenti-cation and encryption/decryption are involved.

We also study the appropriate size ofthe public/private key pair. The key size determines the number of bits of the encrypting key as well as the size of the pseudonym. Larger key size can provide better security, but involves more computations and storage resources, as well as power consumption. We use Elliptic Curve Cryptography (ECC) in our implementation as it provides the same functionality and security features as the widely used RSA cryptosystem, but requires much shorter key length for achieving a similar security level. For example, a 160-bit ECC-key attains about the same level of security as a 1,024-bit RSA key. There is always a tradeoff between performance and security level when choosing the key size. In mobile computing scenario where computation and power resource are limited, we tend to assign more weight to performance. Some of the organizations (e.g., recent ECRYPT II recommendation) recommend 160-bit key for ECC, while others recommend 256-bit. Our experimental results in Fig. 6 show that 256- bit key consumes much more power than that of 160-bit key, under different Poisson distribution parameters. As our goal is to find the smallest key size which can achieve general security requirement for light-weight mobile sce-nario, 160-bit is used to in our prototype. Other crypto- graphy methods or key sizes can be also applied depending on different emphasis of performance or security.

We also show how power consumption

affects the daily normal usage of the mobile device. Fig. 6 shows the percentage of power consumption as a function of the Poisson parameter _ used in location proof exchange. As _ becomes larger, the power consumption increases, due to the more frequent location proof updating activities. It is easy to see our scheme will not increase the power

consumption too much (with less than 2.5 percent power consumption).

The distance between the phones when they exchange location proofs also affects the latency, where longer distance means longer delay due to the weak signal strength. As has been

Fig. 6. Power consumptions under different key sizes and Poisson distribution mean _.

established in earlier studies more than 80 percent of contact durations are less than 10 seconds, and thus there is no problem for our proof exchange process to be finished within the contact duration. Fig. 7 measures the power consumption under different Bluetooth status. There are three status: inquiry, standby and proof exchange. The inquiry status is used to discover other Bluetooth devices within communication range, and send out proof requests. The inquiry process continues for a prespecified time, until a prespecified number of units have been discovered or until it is stopped explicitly. Bluetooth devices that only listen to inquiry messages are in standby. In our system, inquiry and standby are mutual exclusive at any time. The device enters the proof exchange status when it exchanges location proofs with others. The most frequent status is standby, which consumes less than 0.1 mW of power with any communica-tion distance. The proof exchange status consumes the most amount of power and deteriorates with increasing commu-nication distance; however, it will not appear until the next location proof updating cycle.

5.2 Simulation Results

In our simulations, 1,000 mobile nodes are

deployed in a 3 km _ 3 km area. We use

_1; _2; .. . ; _10, where _ ¼ _1 þ

_2 þ __ _ þ

the Levy walk mobility model to generate synthetic node contact events. Previous work has shown that the Levy walk model can describe the mobility patterns of a human being relatively well for a campus- sized area. A contact between two nodes happens when the nodes are within 10 m range of each other, which is the communication range of Bluetooth.

For each simulation run, we generate a Levy walk trace with a certain contact rate and initiate the

Fig. 7. Power consumption under different Bluetooth status and different communication distance.

location proof updating process with various time intervals. We repeat this experiment 100 times, choosing different contact rates for each run. Each node has M

¼ 10 pairs of 160-bit public/ private keys and a Poisson distribution parameter _, which divided into 10 different numbers:

_10. We define a parameter _, which is the standard deviation of two consecutive _i and _iþ1 (assum-ing _i and _iþ1 are in nondecreasing order), to control how to cut

_. Another parameter _ is chosen by each node as a threshold to determine whether to accept a location proof exchange request based on the user-centric privacy level.

We compare our APPLAUS scheme with a baseline scheme. In the baseline scheme, each node does not change pseudonyms based on Poisson distribution. Instead, it uses a constant rate to upload location proofs. Unlike APPLAUS where two nodes mutually exchange location proofs, the baseline scheme only uploads its own location proof if there is a proof available. A dummy message is uploaded when there is no proof available.

In the comparisons, we use three metrics: message overhead ratio, proof delivery ratio, and average delay. The message overhead ratio is defined as the ratio of dummy proof traffic and real location proof traffic. The proof delivery ratio is the percentage of location proof message that is successfully uploaded to the location proof server. The average delay is the time difference between the time when a location proof update is needed and when the location proof message has reached the location proof server.

Fig. 8 shows the performance comparisons between our scheme and the baseline scheme

Fig. 8. Performance under different ratio of ! ¼ Tproof=Tcontact.

under different ratio of ! ¼ Tproof =Tcontact, where Tproof is the required interval between two location

proof updates, and Tcontact is the mean real node contact interval. Fig. 8a shows that APPLAUS outperforms

baseline on overhead ratio when ! is larger than 0.75. When ! > 1:5, the overhead ratio of APPLAUS decreases to as low as 0.2. As shown in Fig. 8b, the proof delivery ratio of APPLAUS significantly outper-forms the baseline scheme, and it reaches 93 percent when ! > 1:5. From Fig. 8c, we can see that APPLAUS and baseline have similar average delay when

! > 1, in which the delay is measured as the unit of Tproof . When ! > 1:5, the delay of APPLAUS becomes lower than 0.15 of Tproof. Thus, when ! > 1:5; i.e., when the location proof update interval is at least

1.5 of the contact interval, the performance of APPLAUS reaches an adequate level. The delay will not change too much after ! ¼ 2. Therefore, an appropriate ratio ! should be chosen between 1.5 and 2.

1. Privacy Evaluation

   In the previous section, we already showed that our location proof updating system has the property of pseudonym unlinkability and statistically strong source location unob-servability. In this section, we evaluate the robustness of APPLAUS such as defending against traffic analysis and statistical test.

   With our scheme, we consider what the attacker can do to detect real events. Clearly, we cannot prevent the attacker from using any statistical analysis tool, so what we show below are based on the general techniques that can be used by the attacker. We believe other statistic testing methods will render similar results.

   We assume that the attacker has enough resources (e.g., storage and computation ability) to collect and analyze location proof updating time by traffic monitoring or by compromising the location proof server. Then, the attacker will try to infer that two pseudonyms belong to the same ID if the distributions of their location proof updating time intervals are identical. To achieve this, the attacker can first conduct some goodness of fit tests such as the Kolmogorov-Simirnov (K-S) test to check whether the probabilistic distributions of the location proof updat- ing time intervals from every pseudonym follow the same Poisson distribution. The attacker then performs the mean test such

   as Sequential Probability Ratio Test (SPRT) if the distributions can pass the goodness of fit test. Those distributions whose sample means deviate from the true mean beyond a certain degree will be marked as potential abnormal pseudonyms.

   To detect if two pseudonyms belong to the same source, the attacker can check whether the two probabilistic distributions of location proof updating time intervals from the two pseudonyms are identical. For the attacker, the hypotheses of the test are:

   . H0the two pseudonyms belong to the same source.

   . H1the two pseudonyms belong to different source.

   When the attacker makes a decision, there are some risks to get wrong decision. The decision is called a detection, if H0 is accepted when it is actually true. If H0 is in fact true, accepting H1 is a false negative. On the other hand, if H1 is in fact true, accepting H0 is a false positive. False positive has no negative effect on privacy since taking two different pseudonyms as the same would not help identifying the real source. We focus on false negative which indicates the percentage of cases that has not been detected by the attackers.

   To evaluate false negative, we use the same

   Fig. 9. False negative rate under different parameter of lamda and E

   simulation setup as previous section and repeatedly perform K-S test [22] on the distributions under different standard deviation (ranging from 0.2 to 1) and threshold _ (ranging from 0.02 to 0.1).

   Based on the test results, we get the false negative rate as shown in Fig. 9. The x- axis is the threshold of each user. The smaller _ is, the less likely a location proof exchange request will be accepted. The y-axis represents the standard deviation

   _ of two Poisson distribution means. Obviously, larger _ indicates wider difference between the two Poisson distributions, which is harder for attackers to differentiate. We can observe from the figure that the false negative rate of the attackers test is high (above 90 percent), especially when _ > 0:04 and _ > 0:5, which indicates that as long as the parameters of _ and _ are appropriately selected, the privacy of our system can be preserved.

2. Collusion Detection

   In this section, we evaluate the performance of collusion detection based on betweenness ranking and correlation clustering approaches. We consider three data sets: besides the above mentioned synthetic trace and the MIT reality trace, we also crawl live data from Foursquare, one of the most popular location-based social networking ser-vices. The data crawling task is to collect correlated user and location data. We select well- connected users (who have hundreds of friends) as seeds to start the crawling. After aggregating the user and location data, we obtain a data set of 58,659 users and 96,219 locations. Note that each user and location in the data set are associated with an address which can be converted to a geographical location (i.e., latitude and longitude) via Google map service.

   The quality of betweenness ranking is

   measured by the ranking score, where we use Mean Average Precision (MAP), to measure the ranking performance of the calculated betweenness. MAP is the most frequently used summary measure of a ranked retrieval run. In our scenario, it stands for the mean of the precision score after each betweenness is generated:

   where B is the number of betweenness. Fig. 10a shows the ranking score of the betweenness ranking method.

   The quality of correlation clustering is measured by the separation score, which is calculated as a weighted average distance between cluster centers:

   where Ci and Cj are the centers of the ith and jth clusters, Ni and Nj are the number of vetices in the ith and jth clusters, and D is the distance function. Thus, Sep reflects the overall distance between clusters. Higher Sep means better results. Fig. 10b shows the separation score of our temporal-weighted correlation clustering results. Worth to mention, when the threshold of the time delay between location proofs is around 1 hour, our solution achieves the best clustering quality. In order to evaluate the performance of these two approaches on detecting colluding nodes, we use compu-tation time and successful detection ratio to measure the efficiency and effectiveness, respectively. We also compare these two approaches with a standard algorithm, in which every location proof or pseudonym is verified individu-ally. All approaches are evaluated based on the Four-square data set. As shown in Fig. 11, the correlation clustering approach runs faster than the betweenness ranking approach, and both are much faster than the standard algorithm. Even though the detection ratio of the clustering approach and the ranking approach is a little bit lower than the standard algorithm, the big difference in computation time is worth the cost.

   Fig. 10. Metrics of quality evaluation for two approaches.

   Fig. 11. Performance of colluding detection for two approaches.

1. RELATED WORK

   Recently, several systems have been proposed to provide end users the ability to prove that they were in a particular place at a particular time. The solution in [1] relies on the fact that nothing is faster than the speed of light in order to compute an upper bound of a users distance. Capkun and Hubax [2] propose challenge-response schemes, which use multiple receivers to accurately estimate a wireless node location using RF propagation characteristics. In [3], the authors describe a secure localization service that can be used to generate unforgeable geotags for mobile content such as photos and video. However dedicated measuring hardware or high-cost trusted computing module are required. Saroiu and Wolman [4] propose a solution suitable for third-party attestation, but it relies on a PKI and the wide deployment of WiFi infrastructure. Different from these solutions, APPLAUS uses a peer-to-peer approach and does not require any change to the existing infrastructure. SmokeScreen [5] introduces a presence sharing mobile social service

   between colocated users which relies on centralized, trusted brokers to coordinate anonymous communication between strangers. SMILE [6] allows users to establish missed connections and utilizes similar wireless techniques to prove if a physical encounter occurred. However, this service does not reveal the actual location information to the service provider thus can only provide location proofs between two users who have actually encountered. APPLAUS can provide location proofs to third-party by uploading real encounter location to the untrusted server while maintaining location privacy. There are lots of existing works on location privacy in wireless networks. In [7], the authors propose to reduce the accuracy of location information along spatial and/or temporal dimensions. This basic concept has been improved by a series of works [8]. All the above techniques cloak a nodes locations with its current neighbors by trusted central servers which is vulnerable to DoS attacks or to be compromised. Different from them, our approach does not require the location

   proof server to be trustworthy. Xu and Cai

   [9] propose a feeling-based model which allows a user to express his privacy requirement. One important concern here is that the spatial and temporal correlation between successive locations of mobile nodes must be carefully eliminated to prevent external parties from compromising their location privacy. The techniques in [10] achieve location privacy by changing pseudonyms in regions called mix zones. In this paper, pseudonyms of each node are changed by the node itself periodically following a Poisson distribution, rather than being exchanged between two untrusted nodes. Identifying a fundamental tradeoff be-tween performance and privacy, Shao et al. [11], [12] propose a notion of statistically strong source anonymity in wireless sensor networks for the first time, while Li and Ren [13] nd Zhang et al. [14] tried to provide source location privacy against traffic analysis attacks through dynamic routing or anonymous authentication. Our scheme uses similar source location unobservability concept in which the real location proof message is scheduled through statistical algorithms. However,

   their focus is to generate identical distributions between different nodes to hide the real event source, while our focus is to design distinct distributions between different pseudonyms to protect the real identity.

2. CONCLUSIONS

In this paper, we proposed a privacy- preserving location proof updating system called APPLAUS, where colocated Bluetooth enabled mobile devices mutually generate location proofs and upload to the location proof server. We use statistically changed pseudonyms for each mobile devices to protect source location privacy from each other, and from the untrusted location proof server. We also develop a user-centric location privacy model in which individual users evaluate their location privacy levels in real time and decide whether and when to accept a location proof request based on their location privacy levels. To the best of our knowledge, this is the first work to address the joint problem of location proof and location privacy. To deal with colluding attacks, we proposed betweenness ranking based and correlation clustering-based approaches for outlier detection. Extensive experimental and simulation results show that APPLAUS can provide real-time location proofs effectively. Moreover, it preserves source location privacy and it is a collision resistance.

REFERENCES

1. S. Brands and D. Chaum, Distance-Bounding Protocols, Proc. Workshop Theory and Application of Cryptographic Techniques on Advances in Cryptology (EUROCRYPT 93), 1994.

2. S. Capkun and J.-P. Hubaux, Secure Positioning of Wireless Devices with Application to Sensor Networks, Proc. IEEE INFOCOM, 2005.

3. V. Lenders, E. Koukoumidis, P. Zhang, and M. Martonosi, Location-Based Trust for Mobile User- Generated Content: Applications Challenges and Implementations, Proc. Ninth Workshop Mobile Computing Systems and Applications, 2008.

4. S. Saroiu and A. Wolman, Enabling New Mobile Applications with Location Proofs, Proc. ACM 10th Workshop Mobile Computing Systems and Applications (HotMobile 09), 2009.

5. L.P. Cox, A. Dalton, and V. Marupadi, SmokeScreen: Flexible Privacy Controls for Presence-Sharing, Proc. ACM MobiSys, 2007.

6. J. Manweiler, R. Scudellari, Z. Cancio, and L.P. Cox, We Saw Each Other on the Subway: Secure Anonymous Proximity-Based Missed Connections, Proc. ACM 10th Workshop Mobile Computing Systems and Applications (HotMobile 09), 2009.

7. M. Gruteser and D. Grunwald, Anonymous Usage of Location Based Services through Spatial and Temporal Cloaking, Proc. ACM MobiSys, 2003.

8. B. Gedik and L. Liu, A Customizable K-Anonymity Model for Protecting Location Privacy, Proc. IEEE Intl Conf. Distributed Computing Systems (ICDCS), 2005.

9. T. Xu and Y. Cai, Feeling-Based Location Privacy Protection for Location-Based Services, Proc. 16th ACM Conf. Computer Comm. Security (CCS), 2009

10. A.R. Beresford and F. Stajano, Location Privacy in Pervasive Computing, IEEE Security and Privacy, 2003.

11. M. Shao, Y. Yang, S. Zhu, and G. Cao, Towards Statistically Strong Source Anonymity for Sensor Networks, Proc. IEEE INFOCOM, 2008.

12. Y. Yang, M. Shao, S. Zhu, B. Urgaonkar, and G. Cao, Towards Event Source Unobservability with Minimum Network Traffic in Sensor Networks, Proc. First ACM Conf. Wireless Network Security (WiSec), 2008.

13. Y. Li and J. Ren, Source-Location Privacy Through Dynamic Routing in Wireless Sensor Networks, Proc. IEEE INFOCOM, 2010.

14. Y. Zhang, W. Liu, and W. Lou, Anonymous Communications in Mobile Ad Hoc Networks, Proc. IEEE INFOCOM, 2005.

    • Referred By SIDDARAMAPPA(CITY COLLEGE)