Student Member, IEEE, K évin Huguenin Nevena Vratonjic

Member, IEEE Vincent Bindschaedler

Student Member, IEEE Jean-Pierre Hubaux

A Location-Privacy Threat Stemming from the Use of Shared Public IP Addresses

Keywords: Privacy, Network Address Translation (NAT), IP-Geolocation

This paper presents a concrete and widespread example of situation where a user's location privacy is unintentionally compromised by others, specifically the location-privacy threat that exists at access points (public hotspots, FON, home routers, etc.) that have a single public IP and make use of network address translation (NAT). As users connected to the same hotspot share a unique public IP address, a single user's making a location-based request is enough to enable a service provider to map the IP address of the hotspot to its geographic coordinates, thus compromising the location privacy of all the other connected users. When successful, the service provider can locate users within a few hundreds of meters, thus improving over existing IP-location databases. Even in the case where IPs change periodically (e.g., by using DHCP), the service provider is still able to update a previous (IP, Location) mapping by inferring IP changes from authenticated communications (e.g., cookies). The contribution of this paper is three-fold: (i) We identify a novel location-privacy threat caused by shared public IPs in combination with NAT. (ii) We formalize and analyze the threat theoretically. In particular we derive and provide expressions of the probability that the service provider will learn the mapping and of the expected proportion of victims. (iii) We experimentally assess the state in practice by using real traces (collected from deployed hotspots over a period of 23 days) of users who accessed Google services. We also discuss how existing countermeasures can thwart the threat.

INTRODUCTION

A S mobile users benefit from online services while on the go, location information has become mainstream. On the one hand, by providing their location with so-called location-based services (LBS), users can enjoy context-aware features, such as finding nearby restaurants, and social features, such as sharing location information with their friends on social networks [START_REF] Patil | Check Out Where I Am!": Location-Sharing Motivations, Preferences, and Practices[END_REF]. Although very convenient, the usage of LBS raises serious privacy issues, because much sensitive information can be inferred from users' locations, including users' movements and associated activities. On the other hand, location information has become essential for many online service providers [START_REF] Goodell | The right place at the right time[END_REF], especially for those whose business models revolve around personalized services. A prominent example is (mobile) online advertising, an ever-increasing business whose worldwide annual revenue is in the tens of billions of US Dollars [START_REF]Internet Advertising Revenue Report[END_REF], as location-specific ads

• This article is a revised and extended version of a paper that appears in the Proceedings of the 13th Privacy Enhancing Technologies Symposium (PETS 2013) Vratonjic et al. [START_REF] Vratonjic | How Others Compromise your Location Privacy: The Case of Shared Public IPs at Hotspots[END_REF]. • Nevena Vratonjic is with Kudelski Security, Cheseaux-sur-Lausanne, Switzerland (e-mail: nevena.vratonjic@nagra.com). This work was carried out while N. Vratonjic was with EPFL, Lausanne, Switzerland • K. Huguenin and J.-P. Hubaux are with EPFL, Lausanne, Switzerland (e-mail: kevin.huguenin@epfl.ch; jean-pierre.hubaux@epfl.ch). • V. Bindschaedler is with the University of Illinois at Urbana-Champaign (UIUC), Urbana-Champaign, IL 61801, USA (e-mail: bindsch2@illinois.edu). This work was carried out while V. Bindschaedler was with EPFL, Lausanne, Switzerland.

have become significantly more appealing to users [START_REF]Targeting Local Markets: An IAB Interactive Advertising Guide[END_REF]. Even if users do not willingly disclose their location to the service provider (typically a non-LBS service provider), the service can obtain users' locations through IP-location, i.e., determining the location of a device from its IP. Existing IP-location services rely either on (i) active techniques, typically based on network measurements [START_REF] Katz-Bassett | Towards IP Geolocation Using Delay and Topology Measurements[END_REF], [START_REF] Qian | You Can Run, but You Can't Hide: Exposing Network Location for Targeted DoS Attacks in Cellular Networks[END_REF], or (ii) passive techniques, relying on databases with records of IP-location mappings [START_REF]Geolocation and Online Fraud Prevention from MaxMind[END_REF], [START_REF]HostIP: My IP Address Lookup and Geotargeting Community Geotarget IP Project[END_REF]. Active techniques provide more accurate results than passive ones, however, they incur high measurement overhead and a high response time (in the range of several seconds to several minutes). A passive approach is several orders of magnitude faster and, hence preferred by service operators. A number of IP-location databases are available, either for free (e.g., HostIP [START_REF]HostIP: My IP Address Lookup and Geotargeting Community Geotarget IP Project[END_REF]) or commercial (e.g., MaxMind [START_REF]Geolocation and Online Fraud Prevention from MaxMind[END_REF]). They provide a country-level accuracy, and at most city-level, and most of the entries refer only to a few countries [START_REF] Poese | IP Geolocation Databases: Unreliable?[END_REF]. For instance, MaxMind reports it correctly geo-locates, within a radius of 40 km, 81% of IP addresses in the US and 60%-80% in Europe. This level of accuracy is only effective for regional advertising but is not sufficient for local businesses (e.g., coffee shops) that require neighborhood or street-level accuracy [START_REF]Targeting Local Markets: An IAB Interactive Advertising Guide[END_REF]. Therefore, major web companies, including Google, are working on improving IP-location 1 by constructing their own IP-location databases. An original way for the service providers to obtain a user's location is via transitivity by relying on other users to disclose their location (typically LBS users) and that of others in their vicinity (typically in a social network): if a provider knows the location of user B and that user A is close to user B, the provider knows roughly the location of A. For instance when users check-in on online social networks and tag friends who are with them. Even if the proximity information is not directly revealed by users, the adversary is still able to infer this, as we will show in the case of access points that make use of network address translation.

In this paper, we study a location-privacy threat users are exposed to on a daily basis. When a user connects to the Internet through the same access point (AP) as other users (e.g., a public hotspot, home router) who make (or made) LBS queries, the service provider (the adversary in this paper) learns the user's location. Indeed, because the devices connected to a public hotspot, implementing network address translation, share the AP's public IP address, when users generate LBS queries, the service provider learns the fine-grained geographic location of the AP and maps it to the AP's public IP. IP addresses remain the same for a certain amount of time, therefore for any connection for which the source IP is the same as the AP's IP, the service provider can conclude that the device is located nearby the location of the AP. The accuracy of the estimated location depends on the range of the AP (typically under one hundred meters) and on the accuracy of the locations reported by users in LBS queries (typically under ten meters with GPS-geolocation). Thus, it is significantly more accurate than the existing IP-location databases.

Our contribution in this paper is three-fold: (i) We identify the location-privacy threat that arises from the use of shared IPs. (ii) We formalize and analyze the problem and we provide a framework for estimating the location-privacy threat, namely the probability of a user being localized by a service provider. The framework is easily applicable to any access point setting: it employs our closed-form solution and takes as input an AP's parameters (i.e., a few aggregated parameters that can be extracted from logs), and it quantifies the potential threat. It is a light-weight alternative to extensive traffic analysis. (iii) We evaluate experimentally the scale of the threat using real traces (collected for a period of one month from deployed hotspots) of users who accessed Google services. Even at a moderately often visited hotspot, we observe the large scale of the threat: the service provider, namely Google, learns the location of the AP only about an hour after users first connect and within 24 hours it can locate up to 73% of the users. To the best of our knowledge, this is the first paper that addresses the problem of users' locations being exposed by others at NAT access points: related works either focus on other attacks to infer a user's location or on how sporadic location exposure can be exploited to track a user or to infer high-level information about her.

Our paper is organized as follows. In Sec. 2 we provide the relevant background. We describe the system setting, the adversary and the threat model in Sec. 3. We formalize the problem by modeling user behaviors in Sec. 4 and we analytically quantify the threat by providing closed-form expressions of the number of victims. We further evaluate the threat based on traces from deployed access points and present the results in Sec. 5. In Sec. 6, we consider possible countermeasures. Further discussion is presented in Sec. 7. Finally, we conclude in Sec. 8.

BACKGROUND

In this section, we provide relevant background on the technical aspects underlying the considered problem.

IPv4 (public) Address Allocation.

To communicate on the Internet, hosts need public IP addresses. An IP can be either static or dynamic, i.e., periodically obtained from a pool of available addresses, typically through the Dynamic Host Configuration Protocol (DHCP). The host can use the IP for a limited amount of time specified by the DHCP lease. For convenience, upon DHCP lease expiration, hosts are often reassigned the same IP. A large-scale study shows that over the period of one month, less than 1% of the clients used more than one IP and less than 0.07% of clients used more than three IP addresses [START_REF] Casado | Peering Through the Shroud: The Effect of Edge Opacity on IP-Based Client Identification[END_REF].

Network Address Translation (NAT).

In order to cope with IP address depletion, NAT was introduced. NAT hides an IP address space, usually consisting of private IPs, behind one or several public IPs. It is typically used in Local Area Networks (LANs), where each device has a private IP, including the gateway router that runs NAT. The router is also connected to the Internet with a public IP assigned by an ISP. As traffic is routed from the LAN to the Internet, the private source IP in each packet is translated on-thefly to the public IP of the router: traffic from all of the hosts in the LAN appears with the same public IPthe public IP of the NAT router. A study shows that about 60% of users are behind NATs [START_REF] Casado | Peering Through the Shroud: The Effect of Edge Opacity on IP-Based Client Identification[END_REF].

Geolocation. Mobile devices determine their positions by using their embedded GPS or an online geolocation service. With a GPS unit, the computation takes place locally by using satellites positions. Commercial GPS units provide highly accurate location results (less than ten meters) [START_REF]Global Positioning System: Standard Positioning Service Performance Standard[END_REF], especially in open sky environments. With online geolocation services (e.g., Skyhook) a device shares the list of nearby cell towers and Wi-Fi APs, together with their signal strengths, based on which the server estimates the device location by using a reference database. This database is built typically by deploying GPS-equipped mobile units that scan for cell towers and Wi-Fi APs and plot their precise geographic locations. In addition, they take into account input reported by users with GPSequipped devices who provide both their positions and the surrounding parameters. The accuracy of such systems is in the range of 10 meters [START_REF]Skyhook Location Perf[END_REF].

Note that Skyhook cannot be used by a service provider to infer users' locations from their IP. Indeed, Skyhook provides only APs' MAC addresses to location mappings and the service provider does not know the MAC addresses of a user's neighboring APs (not even the MAC address of the AP the user connects from) unless the user discloses them.

SYSTEM MODEL

In this section, we elaborate on the considered setting, notably NAT access points, the location-privacy threat, and the adversary.

Setting

We consider a NAT access point setting, a prevalent network configuration, where users connect to the Internet through an access point (AP), such as a public hotspot or a home (wireless) router, as depicted in Fig. 1. An AP, located at (x 1 ,y 1 ), is connected to the Internet and provides connectivity to the users. The AP has a single dynamic public IP address that is allocated with DHCP by its Internet provider (from a given pool of available IPs) and that is valid during the DHCP lease time. The AP operator has no control over the way the AP's IP is assigned by the Internet provider. The AP implements NAT.

While connected to the Internet through an AP, users make use of various online services including search engines, e-mail, social networks, location-based and online geolocation services. Services can be used either in an authenticated (e.g., e-mail) or unauthenticated way (e.g., search). We consider that the requests a server receives are of the following types:

1) Geolocation requests: Geo-Req(MACs), where MACs refer to the MAC addresses of the APs and cell towers in the range of the device; 2) LBS requests: LBS-Req(x 0 , y 0 ), where (x 0 , y 0 ) denotes the coordinates of the device 2 (assumed close to the AP's location (x 1 , y 1 )); 3) Authenticated standard (i.e., that are neither Geolocation nor LBS) requests: Auth-Req(tok ), where tok represents any information that allows for user authentication or linkability of user requests (e.g., a cookie or a username); 4) Unauthenticated standard requests: Req(). With LBS requests, the service provider obtains the user's location under several forms and by different 2. We assume that all LBS requests concern users' actual locations, or that the server has means to distinguish between such LBS requests and other LBS requests. This is the case when the location is obtained directly using the methods described in Sec. 2.

means. The user can specify her position in freetext (e.g., "bars near Park and 57th, Manhattan") or by pin-pointing her position on a map. The location can also be determined by the user's device (see Sec. 2) and communicated to the service provider by a mobile app or by her browser through the geolocation.getCurrentPosition JS function used by websites. Both Geo-Req and LBS-Req contain an estimate of the AP's coordinates, thus they both enable the server to build the (IP, (x 1 , y 1 )) mapping. Consequently, there is no need to distinguish between these two types of requests, and we refer to both as LBS requests. For all types of request, the server knows the source IP, i.e., the AP's public IP.

Adversary and Threat Models

We consider an adversary whose goal is to learn users' current (or past) locations, for instance, to make a profit by providing geo-targeted (mobile) ads and recommendations (e.g., a private company). The adversary has access to the information collected by a number of servers that provide services described above. Companies, such as Google, provide web searches (Google), e-mail (GMail), social networking (Google+), and geolocation and location-based services (Google Maps). As such, Google receives requests of the three types and consolidates all the information obtained [START_REF]Google Privacy Policy[END_REF]. The extent to which these services are used is exacerbated by their deep integration in the widely spread Android operating system, which frequently sends the devices' locations to Google services 3 . In addition, Google has an advertising network and thus has a strong incentive to obtain and monetize information about users' locations. As a matter of fact, Google is working on improving its IP-location based on users' traffic, by mining locationrelated events (e.g., search queries associated with location such as "best burgers Manhattan") [START_REF]Technology and Innovation for Web Search[END_REF].

Microsoft (with Bing, Hotmail, Bing Maps, and Windows Phones) and Apple (with iCloud and iPhone) are other relevant potential candidates for the considered adversary. Besides these major companies, an alliance of service providers can be envisioned to jointly build an IP-location database: each provider contributes IP-location records of its visitors with known locations and benefits from the database for the IPs of users connecting from unknown locations. This joint effort can be coordinated by an ad network that is common to the participating service providers. This approach extends the potential of the threat as it increases the set of potential adversaries: it alleviates the need for each service provider to receive all three types of requests and a significant fraction of user traffic. Instead, they can do so through aggregation. Controlled by the adversary 4.

1.

3.

2.

Fig. 1. System and threat model. Devices connect through a NAT Access Point. A user who makes an LBS request reveals her location to the adversary (1) who maps the IP to its location [START_REF] Patil | Check Out Where I Am!": Location-Sharing Motivations, Preferences, and Practices[END_REF]. When another user connects to a different server (3), the adversary uses the mapping to locate her as she connects with the same IP (4).

In this paper, we focus on the case where the adversary has access to all three types of requests. The adversary is assumed to be honest-but-curious, meaning that he passively collects information.

Given such an adversarial model, we consider the threat of the adversary who learns the location of a user without it being explicitly disclosed: The threat comes from the fact that the adversary can build mappings between the APs' IPs and their geographic coordinates based on LBS requests he receives from other users connected to the APs. Because all requests (from devices connected through the AP) share the same public IP, the adversary can subsequently infer the location of the other users. More specifically, considering the example depicted in Fig. 1, when the LBS provider's server (assumed to be controlled by the adversary) receives an LBS request for position (x 0 , y 0 ), which is the actual position of the user (located close to the AP) determined by her GPS-equipped mobile phone, the server can map the AP's public IP (i.e., 82.63.142.34) to the approximated AP's location (i.e., (x 1 , y 1 ) ≈ (x 0 , y 0 )). Note that the accuracy of the AP's estimated location depends on the accuracy of the GPS of the user-reported location and the range of the AP. Later, when another user, connected through the AP, makes a request to a server (also controlled by the adversary), then the adversary can exploit the obtained mapping and infer from the source IP (i.e., the AP's public IP again) that the second user is at the same location (i.e., (x 1 , y 1 )). The adversary can subsequently provide geo-targeted ads. If the adversary is interested in tracking specific users, he can locate those who make an authenticated request.

We assume that the IP addresses in the DHCP pool can be assigned to clients at very distant locations [START_REF] Freedman | Geographic Locality of IP Prefixes[END_REF]. For instance, some nation-wide ISPs (e.g., SFR in France) assign IPs among the whole set of their clients scattered all over the country. Consequently, the fact that the AP's public IP is dynamic limits in time the extent of the threat: If the AP is assigned a new IP by the ISP, the mapping built by the adversary becomes invalid, unless the adversary is able to infer the IP change. The inference can be based on authenticated requests as depicted in Fig. 2: A request, authenticated by cookie john@dom.com and originating from IP 82.63.142.34, is shortly followed by another request authenticated by the same cookie john@dom.com but originating from a different IP (i.e., 82.63.140.25). There are two options: either the AP's IP has changed or the user has moved and is now connected from a different AP. If the inference time interval (delimited with diamonds in Fig. 2) around the IP renewal time is short enough, then the adversary can infer, with high confidence, that the IP has changed and infer its new value.

Summary. The problem we study is as follows. Considering a single AP, time is divided into intervals corresponding to DHCP leases, during which the AP's public IP address remains the same. At a certain point in time, the adversary knows the location of the AP associated to the IP because (i) a user made an LBS request earlier in the time interval or (ii) the adversary knew the location corresponding to the public IP address from the previous interval and a user made an authenticated request shortly before and after the public IP address was renewed. The location-privacy threat is to be evaluated in terms of the number of users whose locations are known by the adversary. In the case of geo-targeted mobile ads, the adversary needs to know the location of the user when the user makes a requests: the victims are therefore the users who make a standard request after the adversary

FORMALIZATION AND ANALYSIS

In this section, we model the aforementioned setting and build a framework to quantify the threat, which takes only a few parameters as input. The notations are summarized in Table 1 in the appendix.

Model

We consider an access point AP, a passive adversary A, and a set of users who connect to AP and make requests to servers controlled by A. We study the system over the continuous time interval [0, +∞). At each time instant t, AP has a single public IP. Every T time units, starting at time 0, the DHCP lease expires and AP is either re-assigned the same IP or allocated a new one. We model this with independent random variables drawn from a Bernoulli distribution: with probability p New AP is assigned a new IP, and with probability 1 -p New it is re-assigned the same IP. We divide time into successive sub-intervals I k , k ≥ 0, of duration T , corresponding to the DHCP leases:

I k = [kT, (k +1)T ],
and we conduct a continuous-time analysis of the system within the sub-intervals. Each sub-interval is aligned with a DHCP lease. Therefore, within each sub-interval AP's public IP remains unchanged. For any time instant t, we denote by t, the relative time within the corresponding sub-interval, that is t = t mod T . Users connect to AP, remain connected for a certain time and then disconnect. While connected, users make requests, each of which is of one of the following types: LBS, authenticated, or standard. All modeling choices in this section follow well-established conventions [START_REF] Ross | Stochastic Processes[END_REF] -e.g., Poisson processes are known to fit well users arrival and access to services-and are backed up by several public Wi-Fi hotspot workload analysis (e.g., [START_REF] Ghosh | Modeling and Characterization of Large-Scale Wi-Fi Traffic in Public Hot-Spots[END_REF]). We model users who arrive and connect to AP with a homogeneous Poisson process with intensity λ Arr , thus the number N Arr (t) of users who connect to AP, during any time interval of length t, follows a Poisson distribution with parameter λ Arr t:

P [N Arr (t) = n] = (λ Arr t) n n! e -λArrt , n ≥ 0.
We denote the time users stay connected to AP by T Dur , which follows an exponential distribution with average 1 λDur . This means that the associated cumulative distribution function (cdf) and probability density function (pdf) are

f Dur (t) = λ Dur e -λDurt and F Dur (t) = P [T Dur < t] = 1 -e -λDurt .
A noteworthy property of exponential distributions is memorylessness: the probability distribution of the time spent by a given user at a certain AP since a given time instant t, provided that the user is still connected at time t, is the same for all t. In other words, ∀t, ∀δt,

P [T Dur > δt] = P [T Dur > t + δt | T Dur > t].
We assume the system to be stationary in terms of user connections and disconnections. Based on Little's law [START_REF] Ross | Stochastic Processes[END_REF], the average number of connected users at any time instant t is therefore constant and given by:

N Con = λ Arr /λ Dur .
Users generate requests independently of each other. For each user, the three types of requests she makes are also independent: Standard and authenticated requests are modeled by independent Poisson processes with average intensity λ Std and λ Auth , respectively. 4 The probability that at least one request of a type is made during an interval of length t is

P Std (t) = 1 -e -λ Std t and P Auth (t) = 1 -e -λ Auth t .
Another noteworthy property of Poisson processes is that the numbers of requests in two disjoint intervals are independent. We assume that each user makes a request when she connects to AP. For instance, an e-mail or RSS client usually automatically connects to a server when an Internet connection is available. We assume that only a proportion α LBS of the users make LBS requests, and we model such requests by independent homogeneous Poisson processes with intensity λ LBS for each user.

Fig. 3 depicts the user arrivals, departures, and the standard and LBS request processes and it illustrates the key notations and concepts introduced in this section.

Threat

We first focus on a single sub-interval and quantify the location-privacy threat, in terms of the number of users whose locations are disclosed to the adversary because of other users. Specifically, we call a victim a user who makes a standard request at some point in time at which the adversary already knows the (IP, Location) mapping. Such a user is considered a victim "once-for-ever" (for the entire sub-interval).

Quantifying the threat in a sub-interval. If at least one user connected to AP uses an LBS at some time instant (thus revealing her current location), A obtains the (IP, Location) mapping based on which it can locate other users.

We define the compromise time T Comp as the first time within the sub-interval, when a user connected to AP uses an LBS. If such an event does not occur, the compromise time is equal to T . At any time, there are on average N Con users connected to AP, out of which α LBS N Con potentially make LBS queries. The aggregated process of LBS requests is a Poisson process with intensity Λ LBS = α LBS N Con λ LBS . Therefore, the probability that at least one LBS request (from the aggregated process) is made before time t is

F Comp ( t) = P [T Comp < t] = 1 -e -ΛLBS t ,
and the expected compromise time is 1 ΛLBS (1e -ΛLBST ). We call f Comp the corresponding probability density function. The time interval that spans from the compromise time to the end of the sub-interval is called the vulnerability window (see Fig. 3) and the expected value W of its duration is

E [W ] = T - 1 -e -ΛLBST Λ LBS . (1)
Fig. 4 depicts the cumulative distribution function of the compromise time and its average value in an example setting 5 . We observe that, even with moderate AP popularity and LBS usage, the adversary obtains the mapping before the DHCP lease expires in 83% of the cases and he does so after 11 hours on average.

In order to compute the cumulative number of victims (all the users who made a standard request at some point in time in the vulnerability window), we distinguish between two groups of users: those who were already connected when the first LBS request was made, e.g., User 6 in Fig. 3, and those who subsequently connected during the vulnerability window (and are, de facto, victims as they make a standard request when they connect), e.g., User 7. We call V 1 and V 2 the number of victims in each group.

There are N Con users connected at the compromise time (recall that there are on average N Con users 5. Throughout this section, we use different, yet reasonable, values for the parameters of the model in order to highlight singular aspects of the threat, e.g., the sensitivity of the different metrics and the respective contributions of the different parameters. in the system at any time). Whenever we compute an expected value involving the number of users connected, Wald's equation [START_REF] Ross | Stochastic Processes[END_REF] allows us to consider that the system is composed of exactly N Con users.

Provided that an LBS request is made, the number of victims at that time is the number V 1 of connected users who make a standard request before leaving and before the end of the sub-interval. We compute the expected value of V 1 by applying the law of total probability, conditioning over both the compromise time and the time spent in the system. A user connects at time t ∈ [0, T ] (with a distribution f Comp ) and stays connected for a time u ∈ [0, +∞) (with a distribution f Dur ). The user is a victim if she makes a standard request before she disconnects and before the end of the lease, that is in the interval [t, min(T, t + u)]; this happens with a probability P Std that depends on the duration of the interval, i.e., min(u, T -t).

E [V 1 ] = N Con T t=0 ∞ u=0 f Comp (t)f Dur (u)P Std (min(u, T -t)) = N Con Λ LBS λ Std (λ Std + λ Dur ) -Λ LBS • 1 -e -ΛLBST Λ LBS - 1 -e -(λ Std +λDur)T (λ Std + λ Dur ) (2)
The average number V 2 of users who connect to AP between the compromise time and the end of the subinterval is:

E [V 2 ] = λ Arr • E [W ] = λ Arr T - 1 -e -ΛLBST Λ LBS . (3)
The average number of victims in a sub-interval is the expectation of the sum of the number of victims connected at the compromised time (V 1 ) and victims arriving within the vulnerability window (V 2 ). This number has to be compared to the average number of users who have been connected at some point within the sub-interval: V total = N Con + λ Arr T . It can be observed in Fig. 5 that the proportion of victims

(E [V 1 ]+E [V 2 ]
)/V total increases with T . This is because all users who connect during the vulnerability window are victims. As the probability of the adversary obtaining the mapping before time T increases with T , V 1 /V total first increases. However, because V 1 is upperbounded by N Con and V total increases with T , V 1 /V total eventually tends to 0. After 24 hours, the location of more than half of the users is compromised. Following the same line of reasoning, we can compute the number of victims with respect to the tracking attack. In this scenario, we call a victim a user who made an authenticated request during a DHCP lease for which the adversary learned -potentially a posteriori -the (IP,Location mapping). We assume that a user makes an authenticated request when she connects to AP (e.g., checking e-mails automatically). The average number of users who were connected at the beginning of the lease and subsequently made an authenticated request before leaving is

E [V ′ 1 ] = N Con ∞ u=0 f Dur (u)P Auth (min(u, T )) = N Con λ Auth (λ Auth + λ Dur ) (1 -e -(λ Auth +λDur)T )
and the number of users who connected during the lease (and are de facto victims) is E [V ′ 2 ] = λ Arr T . To obtain the average total number of victims, we add up these two quantities and condition over the fact that the adversary obtains the mapping before the end of the lease, that is

E [V ′ ] = (1-e -ΛLBST )(E [V ′ 1 ]+E [V ′ 2 ]
). The proportion of victims is depicted in Fig. 6.

Inferring IP change. We consider two successive sub-intervals, without loss of generality I 0 and I 1 , and we look at the linking probability F Link that the adversary infers the IP change from authenticated requests (i.e., the probability that the adversary links two requests based on a common authentication token, e.g., a cookie). This occurs if at least one user makes both an authenticated request at most ∆T time . We denote by P 1 (resp. P 2 ) the probability that the adversary infers the IP change from the authenticated requests made by a user of the first group (resp. second group). First consider a user who was already connected at time T -∆T (there are N Con such users). In order to infer the IP change from the authenticated requests of such a user before time t ∈ I 1 , the following conditions must be satisfied: (i) the user stays connected at least until time T , (ii) the user makes an authenticated request between the times T -∆T and T , and (iii) the user makes an authenticated request, before time t, and before she leaves (if she leaves before time T +∆T or until T + ∆T otherwise) (see Fig. 7). We compute the probability that at least one user (among N Con ) satisfies the above conditions by applying the law of total probability, conditioning over the time spent in the system from time T -∆T :

P 1 (t) = 1 -(1 -p 1 (t)) NCon , (4)
where over the number of such users, their arrival times (independent of each other and uniformly distributed within [T -∆T, T ]) and their departure times, we compute the probability that at least one of the newcomers satisfies the above conditions

p 1 (t) =
P 2 (t) = ∞ n=1 P [N Arr (∆T ) = n] • (1 -(1 -p 2 (t)) n ) = 1 -e -λArr∆T •p2(t) , (5)
where

p 2 (t) = T v=T -∆T ∆T -1 ∞ u=T -v f Dur (u)P Auth (T -v)• P Auth (min (∆T, v+u-T, t-T ))
Due to space constraints, we do not include the closed-form expressions of P 1 and P 2 . These can be easily computed because all integrals are of the form t u=0 ue -a u du, which is equal to (1 -e -a t )/a.

In conclusion, the probability that the adversary infers the IP change before time t > T , referred to as the linking probability, is given by:

F Link (t) = 1 -(1 -P 1 (t))(1 -P 2 (t)) .
Note that the above equations can easily be generalized to any sub-interval I k , k ≥ 1, by replacing t -T (the relative time in I 1 ) by t = t mod T (the relative time in any sub-interval).

The linking probability can be thought of as a function of both t and ∆T . Fig. 8 depicts the linking probability at time T + ∆T as a function of ∆T . It can be observed that this probability rapidly converges to 1. The probability P 1 (resp. P 2 ) of inferring the IP change from the users already connected at time T -∆T (resp. from the users who connect after time T -∆T and before the end of the sub-interval) first increases with ∆T : the probability of generating authenticated requests increases with the length of the interval. For large values of ∆T however (typically higher than the average connection time), P 1 decreases. This is because users connected at time T -∆T are not likely to still be connected at time T when ∆T is large (compared to the expected connection duration 1/λ Dur ). Note that the fact that linking probability increases with ∆T is balanced by the decreased confidence of the adversary. This is because the probability that a user makes two authenticated requests from two distinct APs in the time interval [T -∆T, T + ∆T ] (moving from one to the other) increases with ∆T . i.e., P 2 , are represented by the dotted and dashed curves, respectively. The solid curve represents the total probability of inferring the IP change, i.e., F Link .

Fig. 9 depicts the linking probability as a function of t. It remains constant for t ≥ T + ∆T because only authenticated requests made before T + ∆T are taken into account to infer the IP change. Note that with a value of ∆T as small as 5 minutes, which provides high confidence, the adversary can still infer the IP change with a probability of 43%.

Quantifying the threat over multiple sub-intervals.

When the adversary infers the IP changes, the probability

F (k)
Map (t) that the adversary knows the (IP, Location) mapping at time

t ∈ I k , k ≥ 1 is F (k) Map ( t) = F Comp ( t) + (1 -F Comp ( t)) • F (k-1) Map (T ) • ((1 -p New ) + p New F Link ( t)) (6) with initial condition F (0) Map ( t) = F Comp ( t):
Either the adversary obtained the mapping from a LBS request during the current sub-interval (i.e., F Comp ( t)) or he did not but he obtained the mapping in the previous sub-interval and either (1) the IP did not change or (2) he inferred the IP change. Note that the assumption ∆T < T /2 is required here. Indeed, this technical restriction ensures that the time interval [kT -∆T, kT + ∆T ] (used by the adversary for the linking), does not overlap with the time interval [(k -1)T -∆T, (k -1)T + ∆T ]. Essentially, this makes the two intervals disjoint hence also independent with respect to the number of authenticated requests, which allows us to multiply the corresponding probabilities. From Equation ( 6), it can be seen that F (k) Map (T ) obeys the following recursive equation:

F (k) Map (T ) = a + bF (k-1) Map (T ) where a = F Comp (T ) and b = (1 -F Comp (T )) • ((1 -p New ) + p New F Link (T )). This equation has as a solution a(1 -b k+1 )/(1 -b). As b < 1, F (k)
Map (T ) converges to a finite value, i.e., a/(1 -b).

The number of victims in the sub-interval I k can be computed by replacing the density f Comp in Equations ( 2) and (3) with the density of F (k) Map . The probability that the adversary has the mapping (IP, Location) at time t in sub-interval I k , i.e., F

Map is illustrated in Fig. 10. It can be observed that the mapping probability increases over time and, after the convergence, the adversary successfully obtains the mapping before the lease expires in 79% of the cases and before the half-lease in 60% of the cases. To highlight the respective contributions of the linking and compromise probabilities, some values differ from our previous setting (e.g., ∆T ). In the first sub-interval, the linking probability is zero and the probability of having the mapping is the compromise probability. In subsequent sub-intervals, this probability F

Map (t) increases due to the potential inference of IP changes: it is a combination of F Link ( t) and F Comp ( t).

Note that in the case of the tracking attack, inferring IP change can be used to infer the location of users who connected during the past leases. Assume that the adversary could not obtain the mapping during a given lease. If he infers the IP change at the end of the lease and learns the mapping (from LBS requests) during the next lease, he can infer a posteriori the mapping for the previous lease and track all the users who made authenticated requests during this lease.

EXPERIMENTAL RESULTS

In this section, we complement our theoretical analysis with experimental results based on traces from a network of deployed Wi-Fi access points. Dataset. Our dataset consists of daily user Wi-Fi session traces, traffic traces and DNS traces for a period of 23 days in June 2012. To emulate the scenario of a single popular hotspot and to avoid side effects of micro-mobility, i.e., devices frequently changing the AP they are connected to, we aggregate the data of two APs located close to each other (∼ 15 meters),.

Session traces contain information, obtained from RADIUS [START_REF] Rigney | Remote Authentication Dial In User Service[END_REF] logs, related to users who connect to the APs. There are three types of RADIUS events: (i) start: a user is successfully authenticated and the device is assigned an IP denoting the beginning of a session; (ii) update: a user connected to the AP periodically issues a status message; and (iii) stop: a user disconnects denoting the end of the session. Each entry in the log contains a timestamp, the device's anonymized MAC address, the assigned IP, the ID of the AP the device is connected to, and an event type. We observed that users typically begin arriving around 7:AM. The number of connected users peaks around 6:PM (136 on average). See diurnal patterns in the appendix. In total, 4,302 users connected over the 23 days.

Traffic traces are obtained from the logs at a border router that connects the network to the Internet. Each entry in the log contains a timestamp, the source IP, and the destination (including the IP address and port). The mapping between a user's assigned IP address and her MAC address enables us to correlate traffic with user session traces.

DNS traces are obtained from the local DNS servers and each entry in the log contains a timestamp, the source IP and the requested host name. By using the source IP, timestamps and requested resources, we are able to correlate the DNS traces with the traffic traces.

We filtered traffic to a number of Google services (including e-mail, search, LBS, analytics, advertising) and classified each request (i.e., standard, LBS, or authenticated) based on the destination IP, port and DNS requests. We sanitized the traffic data beforehand by appropriately grouping traffic traces into user-service sessions. To do so, we correlated traffic and DNS requests. This was made possible by the fact that DNS replies for Google services are cached for a relatively short time (i.e., TTL of 300 seconds), and therefore a traffic request is very often preceded by a DNS request. Consequently, a request accounts for a user-service interaction, regardless of how much traffic the interaction generates. The monitored services and their classification is presented in Table 1. Entries of the type service.* refer to all the top-leveldomains observed in the traces (e.g., .com, .fr, .ca). Entry *.gmail.com includes imap., smtp., pop., www. and m. and doubleclick.* includes .de and .com. The m. prefix stands for mobile services. Traffic to the monitored services (in terms of the number of sessions) constitutes about 17% of the total traffic generated at the AP and 81.3% of users who connected have accessed at least one of the services, which shows the tremendous popularity of Google services. During a day, the average numbers of standard, authenticated and LBS requests (i.e., user-service interactions) to the monitored services are depicted in Fig. 11. It can be observed that standard requests are prevalent, followed by authenticated requests. The moderate usage of LBS services can be explained by the location of the APs: most of the users visit this area on almost a daily-basis, therefore the need for location-based information is expected to be low. In our dataset, 9.5% of users generate LBS requests. Results. First, we measure the compromise time and the proportion of victims, by using the traces from our dataset. We compare the averaged experimental results with those from our theoretical analysis and show them in Fig. 12. For the theoretical analysis, we use our framework with the parameters extracted from the real traces: λ Arr = 14.54 users/h and an average connection time of 2.17 hours (λ Dur = 1/2.17), obtained from the session traces; and traffic rates of λ Std = 28.3 req./h, λ Auth = 14.6 req./h and λ LBS = 0.16 req./h (with α LBS = 0.095), obtained from the traffic traces. Because the theoretical model assumes a homogeneous user arrival rate, we compute the expected proportion of victims and compromise time as if the arrival process spanned from 7:30:AM -the time at which a significant number of users first connect to the AP in our traces-to 7:PM. It can be observed that although the model does not capture the time-of-theday effects of the user arrival and traffic processes, the theoretical and experimental expected proportions of victims match at the end of the day.

We observe that around 8:AM (7:42AM estimated with our theoretical analysis and 8:25AM with our experimental results), only 1 hour after users typically start connecting to the AP, users' location privacy is compromised. By the end of the day, about 73% of the users who connected through the AP were compromised, out of which 90.5% did not make any LBS requests (α LBS = 0.095). Note however, that in terms of the number of users of Google services the proportion of victims actually corresponds to 90%.

Once the adversary obtains the (IP, Location) mapping, it can maintain it over time by relying on Using traces from our dataset, we compute the probability of the adversary inferring the IP change for different renewal times during a day, considering the authenticated requests made at most ∆T minutes before and after the IP is changed. We consider three different values, ∆T = 1, ∆T = 5 and ∆T = 10 minutes, and we show the results in Fig. 13. We assume that each time the DHCP lease expires the AP is assigned a new IP address. Even with the smallest inference time window of 1 minute, the adversary can infer the IP change with the probability 1.0 between 2:PM and 5:PM. With higher values of ∆T the time during which the adversary can infer with probability 1.0 is even longer, i.e., from 11:AM to 7:PM with ∆T = 10. However, the adversary's confidence decreases with larger ∆T . During the periods where there is less traffic (e.g., from 11:PM to 6:AM), the probability of the adversary inferring the mapping is smaller (< 0.2). Between 5:AM and 6:AM, the adversary cannot infer the IP change, as there is no traffic. Consequently, the IP renewal time affects the adversary's success at maintaining the (IP, Location) mapping over time. To confirm the importance of the IP renewal time and its affect on the adversary's success, we plot the cumulative number of victims compromised at the AP during three weeks, depending on the IP renewal time (Fig. 14). We set ∆T = 5 minutes and based on the previous findings, we consider the renewal times at 5:AM, 4:PM and 8:PM, when the adversary is expected to be least successful, most successful and moderately successful, respectively. Indeed, from the results in Fig. 14, we confirm that the highest number of users (3,545 out of 4,302 total number of users, which corresponds to virtually all users who access Google services) is compromised when the IP renewal happens at 4:PM, followed by 8:PM (3,149 victims). The adversary is least successful when the IP renewal is at 5:AM (compromising 2,879 users). These results confirm our previous findings.

COUNTERMEASURES

Cryptographic primitives are efficient at protecting users' privacy, but because of the way networking protocols operate, they might not be sufficient, especially when the private information is the source IP.

Hiding users' actual source IPs from the destination (i.e., the adversary) naturally comes to mind as a straightforward countermeasure against the considered threat. This can be done in several ways. In relaybased anonymous communications, a user's traffic is forwarded from the source to the destination by several relay nodes, in such a way that the destination cannot know the user's source IP. Examples of such networks include Tor [START_REF] Dingledine | Tor: The Second-generation Onion Router[END_REF], mix networks [START_REF] Chaum | Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms[END_REF], [START_REF] Danezis | Mixminion: Design of a Type III Anonymous Remailer Protocol[END_REF], or HTTP proxies. With Virtual Private Networks (VPN), the user is assigned an IP address that belongs to a remote network (e.g., a corporate network or public/commercial VPNs). To the adversary, the user's requests appear to originate from within the remote network whose location is different from that of the user. Unfortunately, such techniques are not widely adopted, especially in the case of mobile communications [START_REF]Tor Metrics Portal[END_REF]. Moreover, anonymization networks have a noticeable price, in terms of usability, speed and latency, that users are not willing to pay for privacy [START_REF] Acquisti | On the economics of anonymity[END_REF], [START_REF] Dingledine | Anonymity loves company: Usability and the network effect[END_REF], [START_REF] Fabian | Privately waiting -a usability analysis of the tor anonymity network[END_REF]. Note also that there are several techniques for identifying the IP of a client, even behind a NAT/proxy, e.g., by using a Java applet [START_REF] Muir | Internet Geolocation: Evasion and Counterevasion[END_REF].

Alternatively, these countermeasures can be implemented by ISPs, for instance, by deploying a countrywide NAT that aggregates traffic from all hosts connected to the ISP at several gateways (e.g., Telefonica [START_REF]Telefonica Implements NAT for ADSL Users[END_REF]) or by IP Mixing [START_REF] Raghavan | Enlisting ISPs to Improve Online Privacy: IP Address Mixing by Default[END_REF]. This also applies to operators of AP networks (e.g., Starbucks, AT&T Wi-Fi). However, they may not have incentives to implement such solutions.

Another approach to thwarting the threat consists in degrading the knowledge of the adversary, by reducing the accuracy of the reported location and by increasing the uncertainty about the AP's location. Examples of location privacy enhancing technologies (PETs) reducing the adversary's accuracy include spatial cloaking [START_REF] Gruteser | Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking[END_REF], [START_REF] Ardagna | An Obfuscation-Based Approach for Protecting Location Privacy[END_REF] and adding noise to reported locations [START_REF] Agrawal | Privacy-Preserving Data Mining[END_REF]. To increase the adversary's uncertainty, [START_REF] Kido | An Anonymous Communication Technique using Dummies for Location-Based Services[END_REF] proposes to inject "dummy" requests, i.e., not related to the user's location. It is not easy for users to implement these PETs, because some geolocation requests are implemented in the operating system that can be controlled by the adversary (e.g., Google Android). Moreover, when these techniques are implemented in a non-coordinated fashion, the adversary might still be able to infer the actual location by filtering out requests that stand out from the bulk (increasing its certainty) and averaging the remaining requests (increasing its accuracy). Better results could be achieved by having the AP operators implement the location-privacy preserving mechanisms, but they might lack incentives to do so.

Finally, as highlighted by our analysis, various other countermeasures can be implemented by the ISP or the AP's owner: reduce the DHCP lease, always allocate a new IP, trigger the IP change when the traffic is low (e.g., at 5:AM as suggested by our experimental results) or purposely impose silent periods around the renewal time (reducing the chances that the adversary infers the IP change from authenticated requests). Unfortunately, all these techniques have a negative effect on the quality of service and impose a significant overhead in network management. Thus, they are unlikely to be deployed in practice. Beyond technical countermeasures, we envision a "Do-notgeolocalize" initiative, similar to "Do-not-track", letting users to opt-out of being localized.

DISCUSSION

Scale and implications of the threat. By maintaining (IP, Location) mappings in the manner we have described, an adversary can build an IP-location system with which he can obtain (at least) sporadic user locations. For an online service provider whose goal is to profit from delivering location-targeted information, it might be sufficient to learn only current user locations at the time users access services.

However, we can envision a different type of adversary, whose goal is to mount more powerful at-tacks on user privacy. In fact, once the adversary has access to sporadic user-location information, he is able to reconstruct entire trajectories, produce patterns of user movement habits, or infer other information about users, e.g., users' real identities, interests and activities. For example, in [START_REF] Shokri | Quantifying Location Privacy[END_REF] it is shown how an adversary that observes each user's sporadic locations (that could be noisy and anonymized) can deanonymize the users, can compute the probability that a given user is at a given location at a given time, and can construct a full trajectory of each user. Golle and Partridge [START_REF] Golle | On the Anonymity of Home/Work Location Pairs[END_REF], Beresford and Stajano [START_REF] Beresford | Location Privacy in Pervasive Computing[END_REF], Hoh et al. [START_REF] Hoh | Enhancing Security and Privacy in Traffic-Monitoring Systems[END_REF], and Krumm [START_REF] Krumm | Inference Attacks on Location Tracks[END_REF] use different techniques to show that users can be identified by inferring where they spend most of their time (notably their home and workplace). Our contribution is orthogonal to the aforementioned pieces of work as we identify and study a case of sporadic exposure whereas they study the effect of sporadic exposure on location privacy. In these cases, the location-privacy threat we identified serves as a building block for more powerful attacks.

Evolution of the threat with IPv6. IPv6 uses a larger address space than IPv4, hence fixing IPv4's addresses depletion issue. The wide adoption IPv6 could therefore lead to the removal of NATs. With IPv6, each host has a public IP, composed of a prefix (leftmost 64 bits), shared with other hosts in the same network, and a unique host part (rightmost 64 bits). Sharing a prefix is similar to sharing a public IPv4 address behind a NAT: (IPv4, location) mappings correspond to (prefix, location) mappings. As IPv6 prefixes are less dynamic than IPv4 addresses, the threat is amplified.

Business opportunities.

Beyond threatening the location-privacy of users, the (IP, Location) mapping technique presented in this paper can be used as a novel IP-location solution that potentially improves on existing solutions [START_REF] Poese | IP Geolocation Databases: Unreliable?[END_REF], [START_REF] Wang | Towards Street-Level Client-Independent IP Geolocation[END_REF]. Online service providers, such as Google and Microsoft, are in a position to build and monetize this service by simply utilizing the user traffic they receive. Additional advantages of this approach are that it does not require a dedicated infrastructure or network measurements. Such a system can be used on its own, or as a complementary approach to one of the existing ones. Because ISPs control the IPs assignments and can prevent service providers from building the mapping (using the aforementioned countermeasure), they can make a profit by selling IP locations to service providers (e.g., Verizon in the US [START_REF] Cnn | Your Phone Company is Selling Your Personal Data[END_REF]) -some ISPs sell geographic information on the topology of their networks [START_REF] Muir | Internet Geolocation: Evasion and Counterevasion[END_REF] or by selling privacy-protection services to users.

Legal and Policy Aspects. Because the threat presented in this papers is based only on a passive analysis of the received traffic, it does not raise additional legal or policy issues, compared to what web services already do, i.e., inferring information from IPs and mining user traffic to improve the offered services.

CONCLUSION

In this paper, we have presented a practical threat, effectively demonstrating that the location privacy of users connected to access points can be (unintentionally) compromised by others. The scale of the threat is significant because it simply relies on the way most networks are designed (i.e., using NAT). When successful, the service provider locates users within a few hundreds of meters, i.e., more accurately than existing IP-location databases. Our theoretical analysis provides a framework that enables us to quantify the threat for any access-point setting and to identify the key parameters and their effect on the adversary's success. This framework serves as a lightweight alternative to an extensive traffic analysis for estimating the threat. We experimentally investigate the state in practice, by analyzing real traces (collected from deployed Wi-Fi access points) of users of Google services. We observe the large scale of the threat, even with a modest use of LBS services. We survey possible countermeasures and we find that adequate ones can be used to protect users' location privacy. However, they need to be widely deployed.

We intend to further study this threat by focusing on the following aspects: (i) the accuracy of a IPlocation service, based on (IP, Location) mappings, in particular the adversary's inference of the AP's precise location based on all the LBS requests it receives (in this paper, we assumed that the adversary learns the mapping as soon as he receives one LBS request), (ii) the adversary's inference of IP changes, taking into account e.g., fingerprinting users, and the trade-off between the probability of inferring the IP change and the adversary's confidence, and (iii) the evolution of the threat for mobile users, in particular the adversary's ability to track users as they move and connect to different APs..

Fig. 2 .

 2 Fig. 2. AP's IP renewal and update of the (IP, Location) mapping. A user makes an authenticated request during a lease in which the adversary learns the mapping, shortly before and after the AP is assigned a new IP. The adversary infers that the AP's IP changed from 82.63.142.34 to 82.63.140.25 and updates the mapping.

Fig. 4 .

 4 Fig. 4. Cumulative distribution function of the compromise time T Comp . The parameters were set to λ Arr = 5 users/h, λ Dur = 1/1.5 (i.e., average connection time of one hour and a half), λ LBS = 0.05 req./h, and α LBS = 0.2. Homogeneous (left) / inhomogeneous (right) Poisson processes for traffic.

Fig. 5 .

 5 Fig. 5. Cumulative proportion of victims as a function of time. The parameters were set to: λ Arr = 5 users/h, λ Dur = 1.5, λ Std = 10 req./h, λ LBS = 0.05 req./h, and α LBS = 0.2. The dotted curve (resp. dashed) corresponds to the victims connected at (resp. arriving after) the compromise time. The solid curve represents the total proportion. Homogeneous (left) / inhomogeneous (right) Poisson processes for traffic.

Fig. 6 .

 6 Fig. 6. Proportion of victims (wrt. the tracking attack) as a function of the duration of the lease T . The parameters were set to: λ Arr = 5 users/h, λ Dur = 1.5, λ Auth = 2 req./h, λ LBS = 0.05 req./h, and α LBS = 0.2. The dotted curve (resp. dashed) corresponds to the victims connected at (resp. arriving after) the beginning of the lease. The solid curve represents the total proportion. Homogeneous (left) / inhomogeneous (right) Poisson processes for traffic.

∞fFig. 7 .

 7 Fig. 7. Timeline for the two groups of users from which the adversary can infer the IP change. A user remains connected for a random time u. (a) The user is already connected at time T -∆T . For the adversary to infer the IP change, u needs to be greater than ∆T and the user must make at least two authenticated requests: One during the time interval [T -∆T, T ] and another one during [T, T + min (∆T, u -∆T )]. (b) The user connects at some time v during the time interval [T -∆T, T ]. For the adversary to infer the IP change, u needs to be greater than T -v (i.e., the user must still be connected at time T ) and the user must make at least two authenticated requests: one during the time interval [v, T ] and another one during [T, T + min (∆T, v + u -T )].

Fig. 8 .

 8 Fig. 8. Linking probability at time T + ∆T as a function of ∆T . The parameters were set to λ Arr = 5 users/h, λ Dur = 1/1.5, λ Auth = 2 req./h, and α LBS = 0.2. The probabilities of the adversary inferring the IP change based on users connected at time T -∆T i.e., P 1 , and based on users connecting in the interval [T -∆T, T ], i.e., P 2 , are represented by the dotted and dashed curves, respectively. The solid curve represents the total probability of inferring the IP change, i.e., F Link .

Fig. 9 .

 9 Fig. 9. Probability of inferring the IP change before time t > T as a function of t, i.e., F Link (t). The parameters were set to: λ Arr = 5 users/h, λ Dur = 1/1.5, λ LBS = 0.05 req./h, ∆T = 5 minutes, and α LBS = 0.2.

Fig. 10 .

 10 Fig.10. Probability of obtaining the (IP, Location) mapping over several sub-intervals. The solid curve represents the probability of obtaining the mapping before time t. The dashed curve represents the probability of obtaining the mapping from an LBS request. The dotted curve represents the probability of inferring the IP change. The parameters were set to λ Arr = 5 users/h, λ Dur = 1/1.5, λ LBS = 0.035 req./h, λ Auth = 0.2 req./h, T = 24 h, ∆T = 3 h, α LBS = 0.1, and p New = 1. To highlight the respective contributions of the linking and compromise probabilities, some values differ from our previous setting (e.g., ∆T ). In the first sub-interval, the linking probability is zero and the probability of having the mapping is the compromise probability. In subsequent sub-intervals, this probability F

Fig. 11 .

 11 Fig. 11. Average number of standard, authenticated, and LBS requests to the monitored services over a day (averaged over 23 days).

Fig. 12 .

 12 Fig. 12. Expected proportion of victims. Vertical lines represent average compromise times: theoretical T Comp = 7:42:AM and experimental T Comp = 8:25:AM.

Fig. 13 .

 13 Fig. 13. Linking probability (i.e., probability of inferring the IP change) as a function of the renewal time, for different inference time window lengths (∆T ).

Fig. 14 .

 14 Fig. 14. Cumulative number of victims during the whole experiment, for three different IP renewal times.

  Fig.3. Threat caused by a user making an LBS request. A i and D i represent User i's arrival and departure, respectively. Users 1 and 4 are already present at time kT . The time at which the first LBS request is made (LBS 5 ) is called the compromise time (T Comp ). From time T Comp on, any user who makes a standard request is a victim. Users already connected at T Comp are victims if they make a standard request after T Comp , e.g., User 4. Users who connect after T

		A 5	A 6	D 1	A 7	D 4
	| kT	Std 5	Std 6	LBS 5	Std 7 Std 4 Std 6	| (k + 1)T	t
				vulnerability window (W )
		compromise time (T Comp )

Comp are, de facto, victims as users make a standard request when they connect, e.g., User 7.

TABLE 1

 1 Monitored services.

	Req. type Services
		www.google.*, pagead2.googlesyndication.com
	Std.	www.youtube.com, www.google-analytics.com, doubleclick.*, m.doubleclick.*,
	LBS	maps.google.*, earth.google.com
	Auth.	calendar.google.com, *.gmail.com, plus.google.com

Note that mobile phones are less susceptible to the threat presented in this paper as they often access the Internet over cellular networks (e.g., 3G/4G) instead of Wi-Fi access points.

For the sake of clarity, the derivations and expressions presented in the paper are for homogeneous processes. We did the derivations for inhomogeneous Poisson processes with piece-wise constant (over the intervals 1:30AM -7:30PM -1:30PM -7:30PM) intensities as well, and we included the corresponding graphs.

ACKNOWLEDGEMENTS

The authors are very grateful to Yves Despond and Patrick Timsit, from the IT department, for their valuable help in collecting data from the Wi-Fi network of EPFL, and to Alevtina Dubovitskaya for her effort.

APPENDIX A NOTATIONS