Claude Castelluccia
email: claude.castelluccia@inria.fr

Mohamed Ali Kaafar
email: mohamed-ali.kaafar@inria.fr

Minh-Dung Tran
email: minh-dung.tran@inria.fr

Betrayed by Your Ads! Reconstructing User Profiles From Targeted Ads

Keywords: Targeted Advertising, Privacy, Information leakage

In targeted (or behavioral) advertising, users' behaviors are tracked over time in order to customize served ads to their interests. This creates serious privacy concerns since for the purpose of profiling, private information is collected and centralized by a limited number of companies. Despite claims that this information is secure, there is a potential for this information to be leaked through the customized services these companies are offering. In this paper, we show that targeted ads expose users' private data not only to ad providers but also to any entity that has access to users' ads. We propose a methodology to filter targeted ads and infer users' interests from them. We show that an adversary that has access to only a small number of websites containing Google ads can infer users' interests with an accuracy of more than 79% (Precision) and reconstruct as much as 58% of a Google Ads profile in general (Recall). This paper is, to our knowledge, the first work that identifies and quantifies information leakage through ads served in targeted advertising.

Introduction

Context: Internet users are being increasingly tracked and profiled. Companies utilize profiling to provide customized, i.e. personalized services to their customers, and hence increase revenues. In particular, behavioral advertising takes advantage from profiles of users' interests, characteristics (such as gender, age and ethnicity) and purchasing activities. For example, advertising or publishing companies use behavioral targeting to display advertisements that closely reflect users' interests (e.g. 'sports enthusiasts'). Typically, these interests are inferred from users' web browsing activities, which in turn allows building of users' profiles.

It can be argued that customization resulting from profiling is also beneficial to users who receive useful information and relevant online ads in line with their interests. However, behavioral targeting is often perceived as a threat to privacy mainly because it heavily relies on users' personal information, collected by only a few companies. In this paper, we show that behavioral advertising poses an additional privacy threat because targeted ads expose users' private data to any entity that has access to a small portion of these ads. More specifically, we show that an adversary who has access to a user's targeted ads can retrieve a large part of his interest profile. This constitutes a privacy breach because, as illustrated in Section 2, interest profiles often contain private and sensitive information.

Motivation: This work was largely motivated by the Cory Doctorow's "Scroogled" short story that starts as follows [12]:

Greg landed at San Francisco International Airport at 8 p.m... The officer stared at his screen, tapping...

-"Tell me about your hobbies. Are you into model rocketry?" -"What?" -"Model rocketry." -"No," Greg said, "No, I'm not." -"You see, I ask because I see a heavy spike in ads for rocketry supplies showing up alongside your search results and Google mail."

-"You're looking at my searches and e-mail?" -"Sir, calm down, please. No, I am not looking at your searches,... That would be unconstitutional. We see only the ads that show up when you read your mail and do your searching. I have a brochure explaining it ..."

The main goal of this paper is to study whether such scenario would be possible today, and if one can infer a user's interests from his targeted ads. More specifically, we aim at quantifying how much of a user's interest profile is exposed by his targeted ads. However, as opposed to the above story, we do not consider ads that show up when a user reads his email or uses a search engine. These ads are often contextual, i.e. targeted to email contents or search queries. Instead, we consider targeted ads that are served on websites when a user is browsing the web.

Contributions of this paper:

We describe an attack that allows any entity that has access to users' targeted ads to infer these users' interests recovering a significant part of their interest profiles. More specifically, our experiments with the Google Display Network [START_REF]Google Display Network[END_REF] demonstrate that by analyzing a small number of targeted ads, an adversary can correctly infer users' Google interest categories with a high probability of 79% and retrieve as much as 58% of Google Ads profiles.

The attack described in this paper is practical and easy to perform, since it only requires the adversary to eavesdrop on a network for a short period of time and collect a limited number of served ads.

The crux of the problem is that even if some websites use secure connections such as SSL (Secure Socket Layer), ads are almost always served in clear. For example, Google currently does not provide any option to serve ads with SSL1 [START_REF]Google AdSense Help[END_REF]. We acknowledge that in some scenarios the adversary can recover a user's profile directly from the websites he visits, i.e. without considering targeted ads. However, we show in this paper that targeted ads can often improve the accuracy of recovered profiles and reduce the recovery time. Furthermore, in some circumstances, the victim has different browsing behaviors according to his environment. For example, a user at work mostly visits websites related to his professional activity, while he visits websites related to his personal interests at home. We show in this paper that an adversary, such as an employer, that can eavesdrop on the victim's computer or network while at work can infer information about his "private" and personal interest profile. In other words, targeted ads constitute a covert channel that can leak private information.

Although there are various targeted advertising networks today, this work focuses on Google advertising system, which is "the most prevalent tracker" according to a survey of The Wall Street Journal [START_REF] Valentino-Devries | What they know about you[END_REF]. However, our methodology is general enough to be extended to other ad networks. The problem of generality will be discussed in Section 3.1.

Structure of the paper: Section 2 describes the Google targeted advertising system. In section 3, we present our approach to filter targeted ads and describe how we infer Google Ads profiles from them. We then present in Section 4 the performance of our method through some experiments in the Google Display Network. In section 5, we discuss the related work. Section 6 presents possible countermeasures and discusses some relevant problems. Section 7 concludes the paper.

Targeted Advertising: The case of Google

Google Display Network is a network of websites (also called publishers) that serve Google ads. Google receives ads from advertisers and then selects the appropriate publishers using various criteria such as relevant content, bid price and revenue.

In the Google targeted advertising model, Google Display Network sites are also used to track users as they browse the Internet. Each time a user visits a website that contains Google ads, i.e. a website that belongs to the Google Display Network, he sends his DoubleClick2 cookie to Google, along with information about the visited website. As a result, Google collects all the sites within the Google Display Network that have been visited by a user, and builds an interest profile from them. A Google profile is defined as a set of categories and sub-categories (see figure 1). For example, if a user visits a football site several times, Google may assign him the category Sport, or more specifically the subcategory Sport → Football. In addition, a Google profile may include location information and some demographic data such as the gender and age of the user. These profiles are then used to target ads to users.

A user can access and modify his Google Ads Preferences by accessing the webpage http://www.google.com/ads/preferences [START_REF]Google Ads Preferences[END_REF]. Furthermore, a user can choose to opt out of the Google targeted advertising if he no longer wants to receive targeted ads. Figure 1 displays an example of a Google user profile that contains potentially private and sensitive information. For example, the "Job listing" category indicates that the user is probably looking for a job. A user might probably want to keep this information secret, in particular from his current employer. Furthermore, the category "Dating & Personals" indicates that the user is currently actively looking for a relationship, and the subcategories "Baby names" and "Adoption" that he has been recently visiting web sites related to baby adoption.

In its privacy policy, Google states that "We take appropriate security measures to protect against unauthorized access to or unauthorized alteration, disclosure or destruction of data.", and "We restrict access to personal information to Google employees, contractors and agents who need to know that information in order to process it on our behalf" [START_REF]Google Privacy Policy[END_REF]. Nevertheless, in this paper we show that a portion of personal users' profiles could be leaked through targeted ads. Even if Google does not consider users' interests as "personal information", this data which is related to users online activities, can be very private from a user's perspective.

Inferring users' profiles from targeted Ads

As targeted ads are personalized to each user based on his profile, they can reveal a lot of information about users' interests. This section describes how an adversary who has access to an user's ads can derive part of his interests from them.

As shown in Figure 2, our approach is composed of two main phases. The first phase collects all ads served to a target user and filters them to only retain targeted ones. In the second phase, targeted ads are classified into categories and a profile is re-constructed. These two phases are detailed in the rest of this section. However, we first start by presenting two building blocks used by these both phases. The first one is an algorithm that is used to categorize webpages.

The second one is a set of algorithms to compare categories.

Building Blocks

Web Page Categorization The web page categorization tool is an algorithm that derives interest categories from a web page. This algorithm relies on the tool used by Google to generate Google Ads Preferences pages. As described in the previous section, each time a user visits a web page, Google derives some interests in the form of categories and updates the user's Google Ads Preferences page accordingly. We use this tool to build our page categorization algorithm. Given a webpage W , our algorithm operates as follows:

1. W is visited and and the resulting DoubleClick cookie is saved. 2. A request is made to the Google Ads Preferences page with the previously saved cookie. Note that Google does not always update the Google Ads Preferences page upon a single web page visit. Usually, a webpage has to be visited multiple times to update the Google Ads Preferences page. Furthermore, we noticed that users' Ads preferences are updated after a period of time ranging between 1 and 2 minutes. Therefore, this step is repeated 5 times (heuristic value) every 2 minutes. 3. The Google Ads Preferences page is parsed and the corresponding categories are retrieved.

To evaluate the performance of our approach, we scraped 5000 ads from Google search page and 2000 sites from Google Display Network, classified them by the tool, and reviewed the results. We detected that almost all of these pages can be categorized by Google (more than 90%). We also manually reviewed the categorization results and observed that, although there are some irrelevant It should be noted that relying on Google does not reduce the generality of our method. There exist many efficient techniques to categorize the content of web pages. For example [START_REF] Toubiana | Adnostic: Privacy preserving targeted advertising[END_REF] uses cosine similarity. This method is very efficient since it relies on social/crowd data (folksonomy) which is continuously updated, and is appropriate for fine-grained categorization. We implemented this method and compared its performance with the Google-based categorization approach we described above. The obtained results were quite similar, with more than 60% of the categories overlapping. We therefore believe that our work can be extended to other ad networks, such as Yahoo! or Microsoft, either by applying their own categorization, or by simply using an existing webpages categorization technique. Note that Yahoo! and Microsoft also build users' behavior-based interest profiles and similarly to Google personalize ads to users according to their interests [START_REF]Personalized Advertising from Microsoft[END_REF] [START_REF]Yahoo! Ad Interest Manager[END_REF].

Category Comparison Methods Many of the filtering and evaluation algorithms presented in this paper need to compare categories. We use three methods for this purpose: "Same category", "Same parent" and "Same root":

1. Same category: Two categories are considered equivalent in the "Same category" method if they match exactly. 2. Same parent: Two categories are considered equivalent in the "Same parent" method if they have the same parent category. For example, the two categories "Arts & Entertainment → Entertainment Industry → Film & TV Industry → Film & TV Awards" and "Arts & Entertainment → Entertainment Industry → Film & TV Industry → Film & TV Production" have the same parent category "Film & TV Industry", so they are considered equivalent to each other in the "Same parent" method. 3. Same root: Two categories with same root category are considered equivalent in the "Same root" method. For example, the two categories "Arts & Entertainment → Entertainment Industry → Recording Industry → Music Awards" and "Arts & Entertainment → Movies → Action & Adventure Films → Superhero Films" have the same root category "Arts & Entertainment" and therefore are equivalent to each other in the "Same root" method. Obviously, if two categories are equivalent in the "Same parent" method, they are also equivalent in the "Same root" method.

Extracting Targeted Ads

Ads provided by Google are either location-based, content-based (we call hereafter contextual, i.e. related to the visited page's content), generic, or profilebased (we call hereafter targeted, i.e. customized to users' profiles). In this paper, we only consider targeted ads. We therefore need to filter out location-based, content-based and generic ads (see figure 3). We conducted all experiments with users from the same location. As a result, the location-based filter is not used (and therefore not presented here). Furthermore, we consider that an ad is contextual if it shares at least one category with its displaying page (the page on which the ad is delivered). To filter out contextual ads, we therefore categorize, using the categorization technique described in Section 3.1, each ad and their displaying page. If at least one category is in common, the ad is classified as contextual. To filter generic (i.e. not customized) ads, we create a number of non-overlapping user profiles (i.e. profiles without any categories in common), and perform 10 requests to the tested pages 3 . Ads that are served independently of the requesting profile are then deemed generic and filtered out.

User-Profile Reconstruction

Given the targeted ads from the previous step, there are possibly many approaches to infer user information. In our work, we aim at reconstructing the Google-assigned interest categories which are presented as user profiles. In order to reconstruct a user profile, we categorize all of his targeted ads using our Google-based web page categorization tool. The reconstructed profile is then the set of resulting Google categories.

For example, considering the ads provided in table 1, the reconstructed profile will look as follows:

Experimental Results

In this section, we evaluate the performance of our profile reconstructing technique.

Experiment Setup

Figure 4 illustrates the setup of our experiments. Our experiments are composed of two main phases: Profile creation: In this phase, we create a set of profiles corresponding to different web users. Each of these profiles, that we call targeted profiles, P t , is obtained by visiting several websites from a user's real web-history (i.e. list of websites that the user has visited). We refer to these websites as training sites. Each of them is visited 15 times to make sure it really affects profiles. We then retrieve the generated Google profile from the Google Ads Preferences page (this phase corresponds to the lower part of figure 4).

Profile re-construction: In this phase, we visit for each targeted profile (P t ) created as described above another set of websites, that we refer to hereafter as visited websites. As opposed to the training sites, each visited site is only visited once. The ads are then collected, filtered and the profile reconstructed as described in Section 3. We refer to the set of profiles we obtain as reconstructed profiles, P r (this phase corresponds to the upper part of figure 4).

Evaluation Methodology

Dataset: Our target web-history data comes from a set of 40 volunteers who provided their list of websites they visited during two days. The first X websites in each profile were used as the set of training sites to create P t . The Y following websites were used to build the reconstructed profiles, P r , as shown in Figure 5.

In the presented experiments, X was set to 30 and different values of Y were used. The average number of root categories and categories in a targeted profile from X websites is displayed in Table 3.

# of root categories # of categories X = 30 6.64 18.06 Performance evaluation metrics: To evaluate the results, we compare each reconstructed profile with the corresponding original one. We compare profiles using the "same-category", "same-parent" and "same-root" methodologies described in Section 3.1. We evaluate the performance of our technique by computing the average Precision, Recall and F-Measure values of all reconstructed profiles. Precision is the fraction of rebuilt categories that are correct, while Recall is the fraction of original categories that are correctly rebuilt. F-Measure is the harmonic mean between Precision and Recall, defined as: F = 2.precision.recall precision+recall . In other words, if we denote by P r,c the categories of the reconstructed profile P r that are correct, and P r,i the categories of P r that are incorrect, P recision = Adversary strategies: In order to evaluate the performance gain obtained by using targeted ads as opposed to only using visited websites, we consider the following three strategies:

-the adversary only uses visited websites ("Sites only").

-the adversary only uses targeted ads ("Ads only").

-the adversary uses visited websites and targeted ads ("Ads & Sites")

Tested scenarios: Finally, we consider two different scenarios, corresponding to two different browsing behaviors:

1. HotSpot Scenario: This scenario corresponds to the case where the victim is connecting to an open network and browses the Internet according to his interests. In this scenario, the X training sites and the Y visited sites are related to each others, i.e. generated from the same interest profiles. The goal of this scenario is to show that targeted ads can be used to boost the accuracy of profile reconstruction. 2. Workplace Scenario: This scenario corresponds to the case where the victim changes his browsing behavior during the reconstruction phase. In other words, profiles used to generate the training sites and the visited sites are significantly different. This situation happens, for example, when the victim is moving from his home to his work environment. The goal of this scenario is to study how much of the home profile leaks from the targeted ads shown at work.

In the following, we present, for the workplace scenario, how we select the visited websites so that they are largely separated from a user's interests. We first randomly select a set of Google root categories, namely "Autos & Vehicles", "Law & Government", "Books & Literature", "Beauty & Fitness", "Jobs & Education" and "Business & Industrial". We then get for each of these categories 500 websites using the Google Adwords Placement Tool [START_REF]Google Adwords Placement Tool[END_REF]. This tool aims at helping advertisers to select websites to publish their ads. We then get for each user all of his root categories, and select a root category C that does not belong to them. The user's visited sites are then randomly selected from the 500 websites corresponding to category C. For example, if a profile contains 4 root categories: "Law & Government", "Books & Literature", "Beauty & Fitness", "Jobs & Education", then one of the remaining categories, "Autos & Vehicles" or "Business & Industrial", will be chosen for visited websites. We verified that none of our test profiles contains all the six visited categories.

Note that a website classified in a Google category according to Google Adwords Placement Tool may result in another category in Google Ads Preferences. For instance, Google may assign a website W to category "Arts & Entertainment". However, when categorizing this website using Google Ads Preferences, the result may include, in addition to "Arts & Entertainment", another root category, say "Books & Literature". Therefore, we cannot completely guarantee that the visited websites are totally separated from the training ones.

Result Analysis

Tables 4, 5, 6 and 7 represent the achieved Precision, Recall and F-Measure values in percentage with (X = 30, Y = 10) and (X = 30, Y = 15) for the hotspot and workplace scenarios respectively. The rows in these tables specify the category comparison methods used to filter out contextual ads 4 . This comparison method is also used to evaluate the results (i.e. to compare the reconstructed profiles with the original ones) 5 . We remind the reader that these comparison methods are described in Section 3.1. The columns of the table specify the three different cases of profile reconstruction, using "Sites only", "Ads only" and "Ads & Sites", respectively. The tables show that the Ads-based information leakage is significantly high, with precision values ranging from 73 to 82% for reconstructed profiles evaluation based on recovering the root of categories solely from Ads. For example, in case (X = 30, Y = 15) in the workplace scenario, with "Ads only" and the "Same root" comparison method (used for both filtering and evaluation processes), we achieve Precision, Recall and F-Measure of more than 79%, 58% and 67% respectively (Table 7). The average number of targeted ads we observed accounts for approximately 30% of all collected ads in each case. We note that the results of the row "Same Category" show in general a relatively lower precision and recall values than the results of the "Same Parent" and "Same Root" rows.

Figures 7 and8 display the variation of Precision, Recall and F-Measure when varying the number Y of visited web sites for each targeted profile, for different comparison methods. We observe that, for a given profile (i.e. when X and therefore |P t | are fixed), the recall increases noticeably with Y , the number of visited web sites, while the precision is steady. This shows that the number of correctly reconstructed categories, i.e. |P r,c |, increases with Y . This result is expected since when Y increases the number of collected ads also increases and as such the amount of available information is higher. However for a given X, the precision is not notably affected by Y , which means that the number of incorrectly reconstructed categories, i.e. |P r,i |, also increases with Y .

Sites Only Ads Only Ads & Sites

Fig. 7. Precision, Recall and F-Measure with the "Same category", "Same parent" and "Same Root" comparison methods (from left to right respectively) used in both filtering and evaluation processes (In hotspot scenario with X = 30). Fig. 8. Precision, Recall and F-Measure with the "Same category", "Same parent" and "Same Root" comparison methods (from left to right respectively) used in both filtering and evaluation processes (In workplace scenario with X = 30).

In the hotspot scenario, the visited websites are largely relevant to the training websites, therefore reconstructing profiles from "Sites only" achieves the results as good as, if not better than, the results obtained from "Ads only" (see figure 7). However, when we combine both sites and ads in the reconstruction process, we get nearly the same Precision, while increasing Recalls remarkably (almost the sum of the two cases "Sites only" and "Ads only"). In this scenario, Ads are very useful to boost the performance since they allow the recovery of a larger part of the targeted profiles.

In the workplace scenario, the visited websites are considerably separated from training websites. Therefore, reconstructing profiles from "Sites only" leads to very poor results, whereas the "Ads only" technique achieves significantly better results (see figure 8). By combining sites and ads, we slightly increase the Recall while reducing the Precision. In this scenario, we observe that ads do indeed constitute a "hidden" channel that leaks private information about users.

While the performance of our method when evaluating the recovery of "root" and "parent" categories is notably high, we acknowledge that it can only recover a small proportion of a user's actual categories (Precision varies between 10 and 18% when using the same category method for evaluation, and Recall ranges from 10 to 17%). We believe there are several explanations for this result. First, Google might not be using the user's actual categories to deliver ads, and instead might use the root or parent categories for a broader coverage of users' interests. Furthermore, our ads classification method is probably not optimal and could be improved in many ways. In particular, we took a simple and conservative approach in the filtering step by ignoring location-based ads. In addition, we did not consider remarketing ads that, as discussed in Section 6, may contain additional information about the users recent online activities.

However, even only 10 to 15% of an user's interest categories can constitute a severe privacy breach. To illustrate this statement, we ran our technique on the profile shown in Figure 1, and using targeted ads only, we recovered the profile shown in Figure 9. Among the recovered categories, the category "Online Communities → Dating & Personals" may constitute a private piece of information which a user might not be willing to share.

Related work

To the best of our knowledge, this work is the first work to quantify the private information leakage from targeted ads content. In the following, we present the most relevant work to our paper:

Privacy-preserving advertising systems. Some initial efforts have been put in designing targeted advertising models yet preventing users from being tracked by ad networks. Among them are Privad [START_REF] Guha | Practical privacy in online advertising[END_REF] and Adnostic [START_REF] Toubiana | Adnostic: Privacy preserving targeted advertising[END_REF]. Their main idea is to keep behavioral information at the client side and then to perform the ad selection process locally. The proposed models provide a stronger protection for user privacy than current systems do, but their feasibility is in turn still open to debate. Our work considers a different adversary model. While these schemes try to prevent ad networks from tracking users, we assume that the ad network is trusted and aim at protecting users privacy from eavesdroppers.

Privacy violations using microtargeted ads. Korolova has recently presented attacks that could be used by advertisers to obtain private user information on Facebook [START_REF] Korolova | Privacy violations using microtargeted ads: A case study[END_REF]. The author showed that an advertiser can manipulate its served ads in order to learn information about users' profiles. This work is complementary to ours, since it considers a different adversary model.

Retrieving user's profile. [START_REF] Castelluccia | Private information disclosure from web searches[END_REF] presented an attack to infer user search history from Google Web search suggestions. While the webhistory webpage is protected by SSL and Google account authentication, the authors showed that a large part of a user's search history can be reconstructed by a simple session hijacking attack.

Discussion

Countermeasures. In order to protect against this information leakage, the easiest solution today is to simply opt out of targeted advertising, frequently delete cookies or use ad-blocking software. Initiatives such as NAI (Network Advertising Initiative) [START_REF]Network Advertising Initiative[END_REF], DNT (Do Not Track) [START_REF]Do Not Track[END_REF] or TPLs (Tracking Protection Lists) [START_REF][END_REF] that aim to provide users with tools to restrict tracking and/or behavioral advertising could also mitigate the identified privacy threat. However, these solutions often prevent to target ads or even to serve ads to users.

There exist several possible countermeasures that could be used to target ads to users and mitigate the information leakage identified in this paper. In particular, there are ongoing efforts to design and deploy privacy-preserving ad systems (e.g. Privad [START_REF] Guha | Practical privacy in online advertising[END_REF] and Adnostic [START_REF] Toubiana | Adnostic: Privacy preserving targeted advertising[END_REF]) whose main principle is to select ads locally. These solutions make the eavesdropping and filtering of targeted ads, and therefore our inferring attack, much more difficult. Another possible solution would be to send all ad requests and responses (containing DoubleClick cookies and ads content) over secure channels (SSL). However, we believe that this solution needs deeper analysis from the research community and the advertising industry since it might be too costly, not practical or altogether hard to deploy.

Stealing ads preferences via an active attack. The attack presented in this paper is passive, i.e. completely transparent to the victim and to the ads providers. We note that a user's preferences can also be stolen by a simple active attack. If fact, if an adversary is able to steal the victim's DoubleClick cookie, it can connect to his Google Ads preference page and retrieve his preferences. We examined the top 100 commercial websites from Alexa and found that at least 71% of them exchange DoubleClick cookie in clear with remote servers. Stealing a Double Click cookie is then quite easy. We implemented and tested this cookie hijacking attack, and were always able to retrieve the victim's Ads preferences page with a simple request to Google Ads servers. This attack is simple, however as opposed to our scheme, it is active and intrusive.

Remarketing ads. This paper did not consider "remarketing ads", which advertise the services or products of a site that a user has visited. Consider a user who is looking for a hotel in Vigo, Spain and performs some searches on the site www.hotels.com. It is very likely that he will consequently receive frequent ads advertising hotels in Vigo while browsing the Internet. Remarketing ads are not only targeting a particular user's interests, but specifically aim to match an exact intention or previous online action. Remarketing ads actually leak much more information about the user. In fact, in our example, they will not only leak that the user is interested in travelling, but also his actual destination i.e. Vigo, Spain. Note that remarketing ads are served independently of Google Ads Preferences profiles. A user will receive remarketing ads even if he empties his ads preferences profile. The only way to stop receiving remarketing ads is to clear his cookies or to completely opt out of targeted ads.

Conclusion

In this paper, we showed that targeted ads contain valuable information that allows accurate reconstruction of users' interest profiles. We presented a methodology to categorize and filter targeted ads, which are in turn used to infer users' profiles. Based on both real users' web histories and synthetic users' profiles, we showed that our technique achieves a high accuracy in predicting general topics of users' interests. Additionally, using only a limited number of collected targeted ads we demonstrated that an adversary can capture on average more than half of targeted profiles. The algorithms described in this paper are simple and probably not optimal. We believe they could be improved in many ways.

Many people claim that the main issue in online behavioral advertising is not related to ads personalization itself, which allows users to receive useful ads, but rather to the fact that it requires users' activities tracking. In this paper, we show that ads personalization can also be harmful to users' privacy and does actually leak sensitive information such as users' profiles. We also note that this information leakage is not specific to online behavioral advertising, but in fact exists in any personalized content (news, searches, recommendations, etc.). As the web is moving toward services personalization almost everywhere, special attention should be paid to these privacy threats. This paper contributes in the understanding of possible privacy risks of content personalization.

Fig. 1 .

 1 Fig. 1. An Example of a Google Ads Preferences Page.

Fig. 3 .

 3 Fig. 3. Filtering targeted ads

Fig. 4 .

 4 Fig. 4. Filtering targeted ads and inferring user interests

Fig. 5 .

 5 Fig. 5. Profile creation and reconstruction.

Fig. 6 .

 6 Fig. 6. An illustration of Precision and Recall.

Fig. 9 .

 9 Fig. 9. Reconstructed Profile.

Table 1 .

 1 Ad page categorization example categories, the categorization generally reflects the content of each page. Table1presents several examples of ad page categorization.

	Ad Url	Categories
	http://www.elasticsteel.net	Beauty & Fitness → Fitness
	ID=156
	http://www.livecarhire.com	Travel → Car Rental & Taxi Services
	http://www.terracebeachresort.ca	Travel → Hotels & Accommodations
		Travel → Tourist Destinations → Beaches
		& Islands
	http://www.sanibelbayfronthouse.com	Arts & Entertainment → Entertainment
		Industry → Film & TV Industry → Film
		& TV Production
		Real Estate → Timeshares & Vacation
		Properties
		Travel → Tourist Destinations → Zoos-
		Aquariums-Preserves
	http://www.siestakeyaccommodation.com Real Estate → Timeshares & Vacation
		Properties
		Travel

Table 2 .

 2 Tourist Destinations → Beaches & Islandsl Arts & Entertainment → Entertainment Industry → Film & TV Industry → Film & TV Production Real Estate → Timeshares & Vacation Properties Profile reconstruction example

	Reconstructed profile
	Beauty & Fitness → Fitness
	Travel
	Travel → Car Rental & Taxi Services
	Travel → Hotels & Accommodations
	Travel →

Table 3 .

 3 Profile size statistics

	Pt	Pr
	Profile Creation (X training sites)	Profile Reconstruction (Y visited sites)	Browsing

Table 4 .

 4 Reconstructing Google profiles performance in Hotspot scenario (X = 30 and Y = 10)

		Av.# of Sites only	Ads only Ads & Sites
		targ. ads Prec./Recall Prec./Recall Prec./Recall
			/F	/F	/F
	Same	14.29	19.66/7.6	18.04/7.06	18.3/14
	cat.		/10.96	/10.15	/15.86
	Same	10.94	58.25/29	53.67/19.38 55.98/42.29
	parent		/38.72	/28.48	/48.18
	Same	9.24	79.26/51.44 73.08/30.06 79.6/68.33
	root		/62.39	/42.6	/73.54
		Av.# of Sites only	Ads only Ads & Sites
		targ. ads Prec./Recall Prec./Recall Prec./Recall
			/F	/F	/F
	Same	21.53	19.67/10.28 15.71/8.47 17.07/17.66
	cat.		/13.50	/11.01	/17.36
	Same	16.67	54.46/34.44 51.26/23.54 52.73/50.16
	parent		/42.2	/32.26	/51.41
	Same	14.4	75.57/61.13 82.24/40.3 78.5/80.52
	root		/67.59	/54.09	/79.5

Table 5 .

 5 Reconstructing Google profiles performance in Hotspot scenario (X = 30 and Y = 15)

		Av.# of Sites only	Ads only Ads & Sites
		targ. ads Prec./Recall Prec./Recall Prec./Recall
			/F	/F	/F
	Same	19.23	2.92/1.05 14.73/10.28 11.84/10.94
	cat.		/1.54	/12.11	/11.37
	Same	13.6	9.09/3.99 46.31/30.31 34.39/31.56
	parent		/5.55	/36.64	/32.91
	Same	11.2	12.65/6.43 78.07/53.96 56.49/55.94
	root		/8.53	/63.81	/56.21

Table 6 .

 6 Reconstructing Google profiles performance in Workplace scenario (X = 30 and Y = 10)

		Av.# of Sites only	Ads only Ads & Sites
		targ. ads Prec./Recall Prec./Recall Prec./Recall
			/F	/F	/F
	Same	28.11	2.99/1.31 13.44/11.95 10.89/12.62
	cat.		/1.82	/12.65	/11.69
	Same	20.3	9.13/5.06	44.95/33.8 32.75/35.45
	parent		/6.51	/38.59	/34.05
	Same	17.13	14/8.61	79.37/58.12 55.85/60.1
	root		/10.66	/67.10	/57.9

Table 7 .

 7 Reconstructing Google profiles performance in Workplace scenario (X = 30 and Y = 15)

We verified this feature by browsing through several https websites (e.g. https://www.nytimes.com/).

In order to keep track of users visiting the Google Display Network, Google uses the DoubleClick cookie issued from the doubleclick.net domain which belongs to Google

The number of 10 requests is considered to be enough to get a sufficient ad collection while resisting well to the ad churn[START_REF] Guha | Challenges in measuring online advertising systems[END_REF].

For example, the row "same parent" displays results when ads are considered contextual if they share the same parent categories with the pages that display them.

[START_REF]Google Privacy Policy[END_REF] For example, the column "same parent" means that two categories are deemed identical if they share the same parent.

Acknowledgments

The authors are grateful to numerous colleagues for thought-provoking discussions on an earlier version of this paper, and to the anonymous reviewers for their valuable comments.


Mathieu Cunche

Mohamed Ali Kaafar

Roksana Boreli

I know who you will meet this evening! Linking wireless devices using Wi-Fi probe requests

Active service discovery in Wi-Fi involves wireless stations broadcasting their Wi-Fi fingerprint, i.e. the SSIDs of their preferred wireless networks. The content of those Wi-Fi fingerprints can reveal different types of information about the owner. We focus on the relation between the fingerprints and the links between the owners. Our hypothesis is that social links between devices owners can be identified by exploiting the information contained in the fingerprint. More specifically we propose to consider the similarity between fingerprints as a metric, with the underlying idea: similar fingerprints are likely to be linked. We first study the performances of several similarity metrics on a controlled dataset and then apply the designed classifier to a dataset collected in the wild. Finally we discuss how Wi-Fi fingerprint can reveal informations on the nature of the links between users. This study is based on a dataset collected in Sydney, Australia, composed of fingerprints corresponding to more than 8000 devices.

I. INTRODUCTION

The huge popularity of mobile and portable wireless devices, including smart phones, tablets and laptops, has further increased the widespread of one of the most used wireless technologies, IEEE 802.11 or Wi-Fi. Included in over a billion of mobile and portable devices in use worldwide, Wi-Fi is provided by Access Points (AP) from a vast majority of homes in the developed and developing world, businesses and by around 750,000 worldwide hotspots. The extensive availability of Wi-Fi connectivity, together with a growing popularity of community networks, has resulted in mobile and portable devices establishing connections to an increasingly large number of APs in various locations.

The open nature of Wi-Fi connectivity has raised a number of privacy concerns in both the media and research literature [START_REF] Pang | 802.11 user fingerprinting[END_REF], [START_REF] Zhang | Inferring users' online activities through traffic analysis[END_REF], [START_REF] Greenstein | Can Ferris Bueller still have his day off? protecting privacy in the wireless era[END_REF], including the well publicized Google Street View collection of traffic from home Wi-Fi APs.

Mobile and portable devices are likely to move across the coverage areas of different APs, e.g. while a person is traveling between home and work. In this likely scenario, low-latency service discovery is a highly desirable feature, as it will maximize the amount of connection time for such devices. We note that the Wi-Fi passive discovery mode, in which the AP periodically sends beacons announcing the AP's Service Set IDentifier (SSID), and where devices listening to these probes select the desired specific SSID, can lead to high discovery delays. In the active discovery mode, the device periodically and actively probes the neighborhood for known APs. This mode, which is supported by operating systems and Wi-Fi chipset drivers on the majority of devices and often activated by default, allows a much lower discovery delay. However, the active discovery mode also raises privacy concerns. Indeed, while in active discovery mode, the mobile or portable device is periodically broadcasting, in the clear, the SSIDs of the APs to which this device has previously been connected to. The device also broadcasts its MAC address, a globally unique identifier. As a consequence, the device is not only advertising its presence to any eavesdropping equipment, but, as an associated issue, this also makes the owner vulnerable to location tracking and possibly profiling attacks.

In this paper, we introduce and study a new privacy threat caused by the Wi-Fi active discovery mode, that is the possibility to infer a relation between devices (and hence the owners of these devices) based on their device's "publicly" announced preferred networks. We refer to the list of preferred networks stored on a device, either partially or globally collected by monitoring wireless probes, as a device Wi-Fi fingerprint.

Various sources of Wi-Fi related potential privacy loss have been addressed in the research literature. The timing pattern of the probe messages can be used to identify the wireless interface's driver [START_REF] Franklin | Passive data link layer 802.11 wireless device driver fingerprinting[END_REF], or to create a unique device identifier [START_REF] Chin | Identifying unique devices through wireless fingerprinting[END_REF]. Our work considers the list of preferred networks as the fingerprint, rather than the timing of probes. We use this fingerprint to link selected devices with similar fingerprints, with the aim of grouping devices and, by association, the owners of these devices.

The SSID of the probed network can also reveal sensitive information about the user, as shown in [START_REF] Greenstein | Can Ferris Bueller still have his day off? protecting privacy in the wireless era[END_REF], [START_REF] Pang | Tryst: The Case for Confidential Service Discovery[END_REF], [START_REF] Lindqvist | Privacy-preserving 802.11 access-point discovery[END_REF]. In particular, SSIDs can reveal geographical location of users [START_REF] Rose | Mapping the urban wireless landscape with Argos[END_REF] when combined with specific databases containing APs' location coordinates, like [START_REF]WiGLE: Wireless Geographic Logging Engine[END_REF]. Our work is complimentary to the research showing how user location can be derived from AP locations, as e.g. users who are detected by our methodology as linked socially or professionally, may also reside in a similar location. This enables additional location detection of users who have APs which may not be in publicly available data bases, or which do not have globally unique SSIDs. In regard of the various problems caused by the current probing process, a privacy preserving access-point discovery has been proposed by Lindqvist et. al [START_REF] Lindqvist | Privacy-preserving 802.11 access-point discovery[END_REF].

In general, discovering links between any two devices is a challenging task. In [START_REF] Quercia | Friendsensing: recommending friends using mobile phones[END_REF] the geographical proximity sensing capabilities of bluetooth technology have been used to suggest potential friendship links to a user. This approach relies on an always-on application running on the user's phone, which constantly monitors surrounding bluetooth-enabled devices. In [START_REF] Eagle | Inferring friendship network structure by using mobile phone data[END_REF] friendship links are predicted using a large set of information collected from mobile phones. In both research works, discovering a relationship is seen from the perspective of one of the partners', and assumes the collection of a sustainable amount of complete information both in terms of temporal data and number of attributes. In our case, the amount of information is quite limited and often partial (Wi-Fi fingerprints consist of small pieces of information, and the information is sparse). On the other hand, the datasets we consider are composed of a much larger set of samples, and thus contain much more possibilities, which in turn makes the task of linking the devices more challenging.

We propose to exploit the device's Wi-Fi fingerprint to group devices and the owners of those devices. The techniques presented hereafter are widely applicable to all devices that publicly expose the SSIDs to which they have been previously associated. Our purpose is to show that the evaluation of fingerprint similarity enables simple, yet efficient tracking and profiling of mobile devices users. In light of these findings, it is desirable that the research community investigates the capabilities and limits of these techniques. This will, in turn, allow for the design of appropriate countermeasures to protect users' privacy.

The contributions of this paper are manifold. First, we introduce the problem of linking devices relying on monitored wireless probes. This problem is, to the best of our knowledge, novel and has not been explored in the literature. Second, we consider and adapt several record linkage techniques as fingerprint similarity metrics, to build a classifier that, given two fingerprints, can determine with high accuracy whether the two devices belong to individuals with an established relationship. This tool, when used with suitable record linkage techniques, validates an intuitive observation: the two separate devices belonging to two socially linked individuals most likely share common SSIDs. However, only the existence of a large and/or rare overlap in SSIDs between the two fingerprints results in establishing the links between individuals with an established social relationship. These results are tested and validated on real world data. By passively monitoring broadcast Wi-Fi probes in the city of Sydney, Australia for a period of 100 days, we have collected fingerprints of more than 8K unique devices and more than 24K different SSIDs. Additionally, we have collected a control dataset comprising of device fingerprints representing 30 social relationships, which we use to validate the classifier. We then apply selected metrics to the public dataset and analyse the characteristics of the detected links.

We envision several possible uses of these techniques, not all of them malicious. In particular, in cases of criminal investigations, where the Wi-Fi device fingerprint of a known suspect is collected. Forensics analysts can for instance, collect the fingerprints of users in the suspect's neighborhood, and our classifier could allow them to distinguish if a set of individuals are likely to have a social relationship with the suspect. As a second use case, wireless service providers could gather valuable information across a specific geographical area to send extremely targeted advertisements to users they deem to be socially linked to their (known) customers. For example, when a group of people have been identified as linked through a friendship relation, the knowledge of a single individual's age can allow the service provider to infer the whole group's age category. This would enable very targeted and efficient ad campaigns.

The paper is organized as follows. In Section II, we overview the related work, and present the background related to the IEEE 802.11 standard probe requests, along with the details of our data collection and observations on the collected dataset. The feasibility of discovering links between devices based on their fingerprint is analyzed in Section III. In Section IV the proposed detection mechanism is applied to a wild dataset. A discussion is presented in section V. Finally we conclude in Section VI.

II. WI-FI SERVICE DISCOVERY AND DEVICE FINGERPRINT COLLECTION

In this section, we introduce the Wi-Fi service discovery and present the underlying mechanisms of the IEEE 802.11 protocol. We then describe the methodology we have used to collect the set of Wi-Fi fingerprints belonging to various Wi-Fi enabled devices and finally we present some observations on the collected dataset.

A. Wi-Fi service discovery

The service discovery feature is a key element of the IEEE 802.11 standard family, which allows a Wi-Fi station to detect other stations and access points in range. The 802.11 standard implements two modes of service discovery.

a) Passive service discovery: In passive mode, access points are advertising services to stations in range using beacons, which are broadcasted periodically on the access point's operating channel. Stations passively listen for these beacons, while switching through the set of possible channels. Depending on the frequency on which the beacons are transmitted, and the channel switching speed and strategy, the resulting lengthy discovery of an AP [START_REF] Judd | Fixing 802.11 access point selection[END_REF] may not be suitable for mobile devices.

b) Active service discovery: In the active service discovery mode, the wireless station actively searches for known APs by probing each channel. The probing consists in broadcasting probe request messages for known APs and then listening for probe response messages . The probe request messages are management frames defined by the 802.11 standard, which embed the SSID of the target AP. The probing is repeated on each channel until the station successfully associates to an AP.

Compared to the passive mode, actively probing the network for known APs has the advantage of reducing potentially long service discovery delays. Indeed, following a complete cycle through the channels, the wireless station is guaranteed to discover all the known APs in range. In addition, the active service discovery mode is required in the case of wireless networks with a hidden SSID, when the AP is not broadcasting beacons with its associated SSID embedded into the management frames.

B. Wi-Fi Fingerprint of a device

We note that the active service discovery process is enabled on a large number of operating systems (e.g. iOS, Google Android, Windows). As a consequence, when the devices running those OSs are out of range of a known AP, they continuously broadcast probe request messages. The latter contain the MAC address of the device , and as such uniquely identify the device. While listening in to traffic containing these management frames (broadcasted in plain text), an eavesdropper can easily collect the set of announced SSIDs i.e. the Wi-Fi fingerprint and associate them with a specific device. In the following sub-sections, we present our experimentation approach and characteristics of the collected Wi-Fi fingerprints.

C. Fingerprint collection

For our dataset collection, we have used a netbook with a Wi-Fi interface set to monitoring mode1 and a packet analysis tool to filter out the probe messages2 . For each probe request, we record a time stamp, the source MAC address, the destination MAC address, and the content of the SSID field. As mentioned previously, in active probing mode, the probe requests are broadcasted. Notably, since the MAC address of the AP associated to the target SSID is not available, we cannot uniquely identify the AP to which the device has been previously associated. Indeed, the same SSID can simply be used by several APs, and the number of APs associated to an SSID ranges from one, e.g. a personal AP with a "unique" name such as the concatenation of the first bytes of the AP MAC address and the Internet service provider name, to several thousands of APs, default equipment SSIDs such as NETGEAR or common hotspot names such as BTOpenzone or McDonald's FREE WiFi.

Our study was conducted on two types of Wi-Fi fingerprint data sets. First, we collected fingerprints advertised by wireless devices in the city of Sydney (Australia) over a period of 6 months. The monitoring (fingerprint collection) was performed by one of the authors, during the daily commute and various social activities. The rate at which fingerprints have been collected depended on the density of the surrounding area, and can go up to several 10's of devices per minute.

The collected dataset initially contained over 24.000 unique devices and 30.000 different advertised SSIDs. In this data set a large fraction (more than 60%) of the devices had a fingerprint reduced to one SSID. As it is unlikely that a large number of devices have been associated to only one AP, we believe that those fingerprints may have been partially collected 3 . Therefore we have decided to discard them and base our study only on the devices with fingerprints with at least two SSIDs. After this filtering, the dataset still contained 8834 devices and 26262 SSIDs. This dataset is referred to as PubProbes.

A second dataset has been collected from a set of volunteers, with known device MAC addresses, also by our monitoring devices. This dataset is composed of 30 fingerprint pairs with a well established and known (disclosed) underlying social link. This dataset is referred to as VolunteerProbes.

During our fingerprint collection campaign, we have observed that the frequency at which the fingerprints are collected depends on the density of devices in the surrounding area. It can range from one to several dozens of devices per minute. In fact, probe requests are transmitted within small bursts. The frequency at which those bursts are emitted over a given channel depends on the device and more particularly on the operating system/driver [START_REF] Franklin | Passive data link layer 802.11 wireless device driver fingerprinting[END_REF]. The average interval between any two bursts from the same device varies from 50 to 60 seconds. Conservatively, being in range of any station for 60 seconds could be sufficient to collect the whole fingerprint of a device. However, it is important to note that due to potential loss of probes (e.g. when the quality of the channel is low), several bursts may be required to collect the complete set of SSIDs broadcasted by a device. c) Observations on the collected dataset: Within the PubProbes dataset, the size of the fingerprints varies from one to 100 SSIDs, and has an average size of 5.34. Figure 1 shows the cumulative distribution of the number of SSIDs per fingerprint; it shows, that large majority of the fingerprints have a size lower than 20, while some fingerprints contains more than 80 SSIDs. Figure 2 shows the cumunlative distribution of number of fingerprint per SSID. We can observe that a large fraction of the SSIDs are unique to a single fingerprint while on the other hand, a few very popular SSIDs are shared among a large number of fingerprints. As a consequence of this SSID diversity, each fingerprint is unique, which makes it an excellent unique identifier. We note that those observation are similar to those drawn based on a similar dataset collected on a university campus by Rose et. al. [START_REF] Rose | Mapping the urban wireless landscape with Argos[END_REF].

III. LINKABILITY OF THE DEVICES

As outlined in the introduction, our interest is in measuring the similarity between the Wi-Fi fingerprints of various devices, which can in turn allow us to link the devices and the owners of these devices. Many well-known Record Linkage (RL) (alternatively, Entity Resolution) techniques have been successfully used to find records that may belong to the same entity in two or more databases. In RL terminology, two records that have been matched are said to be linked (we will use the same term throughout this work). To the best of our knowledge, the application of record linkage techniques to link Wi-Fi fingerprints is novel and it presents several challenges on its own. Information retrieval techniques typically measure distances between two documents (or a search query and a document), which are a set of words and thus need to be adapted for our purpose. Therefore, before presenting the study of fingerprint similarity in the wild, we start by studying the characteristics of fingerprint pairs with a known underlying link. For this purpose, we use ground truth evidence (the VolunteerProbes dataset) in which social links between devices' holders are known.

A. The (VolunteerProbes) dataset characteristics

We have collected the Wi-Fi fingerprints from a set of volunteers, along with the fingerprints of individuals with whom they maintain a strong social relationship (family members, close friends, flat mates). Once the VolunteerProbes dataset has been collected, all the devices pairs have been considered and categorized into two groups: those for which we verified that their owners are linked (we refer to this set as L for linked), and others for which we verified that their owners are not linked, referred to as N L for non linked group of device pairs.

To assist with the analysis, we first define the frequency of an SSID z within a corpus, F, that is the ratio between the fingerprints X containing the SSID z, over the total number of fingerprints in the corpus:

F as f z = |X,z∈X| |F |
. In our case, the corpus F is the set of total fingerprints from the PubProbes and VolunteerProbes datasets. The PubProbes dataset serves as a reference, since we can be confident that the SSID frequency estimation, although coarse, gives a stable frequency measure of the common SSIDs. Indeed, in f z we will measure the number of occurrences of SSIDs in the collected sample, and hence we are assigning maximum probability to the observed samples and zero to all the others. Since, as we will discuss next, we are interested in the rarity of SSIDs in intersections and it is highly likely that common SSIDs would be overrepresented in the PubProbes dataset, a simple frequency estimation as defined by f z can be used for this purpose.

B. Characteristics of fingerprint pairs

Our approach determines the similarity between any two fingerprints primarily on the SSIDs they have in common, rather than on the semantic analysis of the Wi-Fi fingerprints. We focus on two aspects of the fingerprint intersections: the size and the rarity. The size of the intersection simply represents the number of SSIDs shared by the two fingerprints. The rarity of the intersection of any two fingerprints X and Y , denoted Rarity(X, Y ) hereafter, measures its uniqueness and is equal to the product of the frequency estimation of the elements in the intersection. The higher the rarity score, the more unique the intersection is.

Rarity(X, Y ) =    z∈X∩Y -log f z if X ∩ Y = ∅ 0 otherwise (1)
where f z , the frequency of the element z.

Figure 3 shows the distributions of the intersection for both sets L and N L of fingerprint pairs. In particular, we can clearly observe that the size of the intersection is at least equal to one for all pairs with an established social link, while it is empty for more than 90% of the pairs that are not linked. Put simply, Wi-Fi fingerprints of devices with owners who are socially linked are more likely to have a non-empty intersection. The size of the intersection seems to be the first discriminatory characteristic for the existence of a relation between devices holders. However, as illustrated by Figure 3, matching the intersection sizes, although the two distributions differ, does not always indicate that the two devices belong to socially Figure 4 shows the cumulative distribution of the rarity for the Intersection sets of pairs (again for both L and N L). We observe that the linked pairs are characterized by the highest rarity scores whereas a large majority of the non linked pairs have a low score. In general, almost all the rarity scores of the "linked" fingerprints intersection (in L) are higher than the non linked devices rarity scores. This validates an intuitive observation: having a non empty intersection between two device fingerprints is not sufficient to consider a social link between the devices holders, as it should be necessary to include the rarity of the shared SSIDs. The underlying idea is that a common SSID does not provide much information on a potential social link between specific users. As shown in Section II, some SSIDs might be shared by a large number of devices' fingerprints, e.g. hotspots and redundant by-default SSIDs.

C. Similarity metrics

To infer a social link between two devices holders, we need to compare the similarity between two sets of SSIDs. In this paper, we consider a well known set of similarity metrics, used in record linkage related problems. The argument for using the theory and techniques utilised for information retrieval i.e. computing of document similarity, is that we can view the SSIDs as a collection of words. We have tested a number of similarity metrics and in this paper we present those that produce the best results, based on considering either the size or the rarity of the SSID intersection sets.

1) Jaccard Index: The Jaccard index simply considers the similarity of two samples, as the ratio the ratio of the intersection's cardinal by the union's cardinal, i.e. J(X, Y ) = |X∩Y | |X∪Y | . The Jaccard Index ranges from 0 (disjoints sets) to 1 (identical sets). It only consider the intersection size and does not take into account the rarity of the elements in the intersection.

2) IDF similarity: In this case we use a well known information retrieval tool called TF-IDF. However, TF-IDF similarity measures the distance between two documents (or a search query and a document), which are set of words. We need to slightly alter the TF-IDF measure to apply it to Wi-Fi fingerprints instead. The term frequency-inverse document frequency (TF-IDF) is a weight used to evaluate how important is a word to a document that belongs to a corpus. The weight assigned to a word increases proportionally to the logarithm of the number of times the word appears in the corpus but the importance decreases for common words in the corpus.

The TF-IDF of term i in document X is TF-IDF(X, i) = TF X,i .IDF i , where TF X,i is the term frequency of i in document X defined as TF X,i = |{t∈X:t=i}| |X| and IDF i is the inverse document frequency of the term i in the considered corpus. In our case the inverse document frequency is simply the logarithm of the SSID's frequence inverse: IDF i = log 1 fi . The TF-IDF is often used to measure the similarity between two documents, in the following way: first the TF-IDF is computed over all the terms in the two documents, and the results are stored in two vectors; then the similarity between the two vectors is computed, for example using a cosine similarity measure. In our case, terms appear at most once in a fingerprint. Therefore, we replaced the term frequency component by a binary function: 1 if the fingerprint contains the term, 0 otherwise. The modified cosine similarity-based IDF is:

Cosine-IDF(X, Y ) = x∈X∩Y IDF x 2 x∈X IDF x 2 y∈Y IDF y 2 (2)
The Cosine-idf ranges from 0 (disjoints sets) to 1 (identical sets).

3) Adamic similarity: In [START_REF] Lada | Friends and Neighbors on the Web[END_REF], Adamic & Adar proposed a metric to estimate between personal pages similarities, and used this metric to infer social links. The Adamic metric takes into account the frequency of the pages elements by considering the logarithm of their frequency, as follows:

Adamic(X, Y ) = z∈X∩Y 1 log f z (3)
where f z is the frequency of the element z. The Adamic metric ranges from 0 (disjoints sets) to a given maximum value depending on the considered corpus. Notably, this metric takes into account both the rarity and the size of the intersection. 4) Modified Adamic similarity: Since the Adamic metric considers the logarithm of the element's frequency, it naturally tends to reduce the impact of the rarest elements. We argue that the rarest elements, i.e. those shared by only two fingerprints, are actually those containing the more information about a potential link. In order to strengthen the similarity metric, we propose to modify the Adamic metric by replacing the logarithm of the frequency by a power of the frequency. Using a power of the frequency instead of a logarithm-based value will strengthen the importance of the rarest SSIDs among the sample. Our modified Adamic similarity, called Psim-q, is as follows:

Psim-q(X, Y ) = z∈X∩Y 1 f q z (4)
where f z is the frequency of the element z, and q is the power considered. This metric ranges from 0 (disjoints sets) to a given maximum value depending on the considered corpus. Similarly to the original Adamic metric, the Psim-q metric takes into account both the rarity and the size of the intersection. Several values for q have been tried, and the best results were obtained for q = 3. Therefore, from now on, we will consider the metric Psim-3.

D. Evaluation

Our goal is to assess how accurately Wi-Fi fingerprints can be used to link two different individuals. For this purpose, we build a classifier to separate the two sets L and N L, respectively of linked and non linked pairs of devices fingerprints. In order to fairly estimate the performance of the classifier, the fingerprint pairs were separated, shuffled and a list of fingerprints derived from L and N L was constructed. The task of the classifier is to re-link the fingerprints in L maximizing the fingerprints couples correctly linked while linking as few incorrect couples as possible. In practice, for each possible couple in the list our classifier computed the similarity metrics and kept only the couples with highest similarity. If the fingerprints pair similarity value is above a threshold then the candidate couple is considered linked; otherwise it is non-linked.

a) Classification performances: Binary classifiers are primarily evaluated using the classical false/true positives/negatives indicators. We can consider our binary classifier as a simple hypothesis test where the classifier is a detection scheme that tests the following null hypothesis: The pair of devices corresponds to an underlying social link. Given a set of n pairs of devices, containing n P pairs with a social link (positive) and n N with no social link (negative). In our case, we are interested in finding fingerprint pairs that are actually linked (true positives which number is n T P ) while minimizing the number of pairs that are linked by mistake (false positives, which number is n F P ). In addition, let us consider n F N as the number of false negatives and n T N as the number of true negatives. The false positive rate (FPR) is the proportion of all devices do not corresponding to an underlying link that have been wrongly reported as positive by the test, so FPR = n F P n F P +n T N . Similarly, the true positive rate (TPR) is the proportion of linked devices that have been rightly reported as such by the test, and we have TPR = n T P n T P +n F N . To evaluate the efficiency of the classifier, we first plot in Figure 5 ROC (Receiver Operation Characteristics) curves observed for different similarity metrics and several thresholds. These plots show, for each threshold, the point corresponding to the false positive rate along the x-axis and to the true positive rate along the y-axis, with one curve per similarity metric. Obviously, the closer to the upper left corner of the graph a curve is, the better, since such points correspond to high true positive rates (i.e. a high proportion of positives being reported as such by the test) for low false positive rates (i.e. a small proportion of negatives incorrectly reported as positives). We observe that from this perspective Cosine-IDF and Psim-3 metrics outperform the other metric, offering excellent compromises between high true positive rates and law false positive rates. Since the Jaccard index does not take into account the rarity of the common SSIDs, and hence suggests that the rarity of the intersection is less important than its cardinal, with no surprise, we can verify that it performs less efficient results than other metrics. Comparing the results of the Adamic metric and our modified version, the Psim-q, we can observe that the change of weighting function, i.e. power of the frequency rather than a logarithmic function, has significantly improved the performances. Where the Adamic displayed poor performances, the Psim-3 performs as well as the two best metrics.

Another interesting property of ROC curves is that they show the optimal range for the threshold. Indeed, as the slope of the ROC curve flattens, the increase in true positive rate is proportionally smaller than the corresponding increase in false positives. In other words, a lower threshold, although it always increases the true positive rate of the test, is not always productive as it eventually does more damage than good through increased false positive rates. In general, this means that the threshold of the similarity tests should be set to a value that yields a point in the "elbow" of the ROC curve. In practice, the choice of the threshold depends on the application of the classifier: one might favor detecting as much true positives as possible at the expense of a higher false positive rate; while in other cases, one might be interested in increasing the threshold so as to detect fewer true positives but minimizing the probability of mistakenly linking any two devices. We will now concentrate on the Cosine-IDF and Psim-3 metrics as both of them yield at least similar results than the other considered metrics.

Figure 6 shows the true positive rates and false positive rates variation for various thresholds, respectively for the Psim-3 and Cosine-IDF metrics. As expected, a higher threshold results in a more aggressive classification test that correctly classifies only a few of actually linked devices, but on the other end wrongly reports a tiny proportion of non linked devices.

Our study focuses on a set of thresholds providing optimal performances. Social and professional graphs are rather sparse, i.e. the number of existing edges is much smaller than the number of potential edges. Therefore the number of false, i.e. vertex pairs not connected by an edge, will be much higher than the number of true, i.e. vertex pairs connected by an edge. Given the difference between the size of the positive and negative sets, we focus on thresholds with low corresponding FPR, namely F P R < 0.1. Even with this strict constraint, thresholds with high and medium TPR are possible. For instance, for the Psim-3 a threshold of t = 1.5710 -5 leads to a TPR= 0.8 and FPR= 0.0772. Even if a part of the positive sets are missed, this will limit the number of false positive. In our use case example, the investigation of a criminal group, two cases may be possible: either the goal is to reduce the set of suspects to a more manageable size, or to use the result of the classifier as an evidence. In the first case, additional information may be available on the potential suspects, and could be be used to further refine the results returned by the classifier. Therefore having a high FPR may not be an issue. On the other hand, as missing positives is not acceptable, a high TPR should be targeted, e.g. by using Psim-3 with a threshold t = 1.19 10 -8 , which results in T P R = 1 and F P R = 0.2618. In the second case, false positives are not acceptable, hence the FPR must be as small as possible. Therefore, a good threshold for the Psim-3 could be t = 0.162 which results in T P R = 0.1 and F P R = 0.

IV. LINKING DEVICES IN THE WILD

We apply the link detection scheme using the metrics defined in Section III-D to the public PubProbes dataset. This dataset is composed of more than 8K unique device identifiers, with collected fingerprints comprising of more than 26K distinct SSIDs. We note that, since this dataset consists of fingerprints collected in the wild, no information on the links between the devices is available. In the light of our results in Section III-D, we will focus on two similarity metrics: Cosine-IDF and Psim-3. We consider three threshold values for each metric. The three thresholds have been selected respectively to yield (resp.) to values of F P R = 0, T P R = 1 and a desired trade-off between between FPR and TPR, from the results in Section III-D. In the following, we analyze the characteristics of the resulting set of linked devices from the PubProbes dataset. We derive additional insights about the general applicability of the selected metrics.

A. Results

Table I summarizes the threshold values chosen for the Cosine-IDF and the Psim-3 metrics, with the corresponding FPR and TPR values as obtained for the VolunteerProbes dataset.

Our classifier looks for potentially similar fingerprints based on the selected threshold. Table I shows the number of linked device pairs for both chosen metrics. The Cosine-IDF metric, independently from the used threshold, detects a relatively large number of device pairs, compared to the Psim-3 metric. We note a property of the Cosine-IDF metric, which may result in inconsistencies when attempting to detect links between devices in the wild. When two fingerprints are identical, the resulting similarity score is always the highest (i.e. equal to one), regardless of the size of the fingerprints and the frequency of those SSIDs in the corpus.On the other hand, we note that Psim-3 (and more generally Psim-q) is more sensitive to both the variations in the number of SSIDs shared between the two compared fingerprints and the rarity of those SSIDs. In particular, in case of identical fingerprints, the Psim-3 similarity score still depends on the frequency (rarity) and the number of the common SSIDs.

Given the device pairs detected in PubProbes dataset, we further explore the underlying reasons why the devices have been linked. We now focus on the characteristics of the intersections of linked fingerprints. The rarity of SSIDs comprising these intersections is shown in Figure 7, while the size of intersections is shown in Figure 8. We observe that for the Psim-3 metric, when the highest threshold is applied (curve labeled t = 0.162 in Figures 7 and8), more than 60% of the intersections of linked devices fingerprints have their sizes larger than 2, while for the two lower thresholds (t = 1.71 10 -4 and 1.19 10 -8 ), the vast majority of the intersections are reduced to one SSID. In addition, these two lower thresholds result in a set of links in which a large majority of the intersection SSIDs have a rarity of less than 18. When applying the the highest threshold (t = 0.162), the majority of linked fingerprints possess rare SSIDs. For the Cosine-IDF, the thresholds variation seems to have a small impact on the rarity and the size of the intersections of linked fingerprints. Indeed for the three thresholds, almost all the intersections are reduced to only one SSID. The rarity for the two higher thresholds appear to be sensibly similar and in the three cases the majority of intersections has a rarity lower than 10.

B. Detecting links from the VolunteerProbes dataset embedded in the PubProbes dataset

We now focus on a scenario where given a device and its fingerprint, we would like to detect the potentially linked devices from a large dataset. For this purpose, the VolunteerProbes dataset is embedded into the PubProbes dataset and we apply the classifier (considering our chosen two metrics) to retrieve the links a priori known from the VolunteerProbes dataset established relationships. For each device in the VolunteerProbes data set, we collect all the devices returned by the classifier as linked to the considered device. The number of returned candidates is considered as a performance metric as it quantifies how well the initial set, composed of more than 8K devices, can be reduced to a more manageable size.

Table II presents the average/min/max number of retrieved candidates for each threshold. Obviously, for the two metrics decreasing the thresholds' value significantly increase the number of candidates. Again, depending on the application, one might favor detecting all the positives at the expense of false positives and a larger number of candidates. The Cosine-IDF returns much larger sets of candidates than the Psim-3. Focusing on the Psim-3 metric, we observe that the most restrictive threshold (t = 1.57 10 -5 ) yields to 0.475 candidates in average and a maximum of 2. The candidates' set is rather small, but the threshold is so high that it may miss some positive (in this case the TPR is only 0.1). For the intermediate threshold (t = 1.57 10 -5 ) we observe that in average 28.125 candidates are returned, which represents 0.35% of the PubProbes data set. For the lowest thresold (t = 1.19 10 -8 ), the average number rise to 437.425, i.e. 5.4% of the full set. This last threshold yields a TPR of 1 on the VolunteerProbes data set, but when it is applied to the PubProbes data set it returned large sets of candidates.

V. DISCUSSION

This work shows that it is clearly possible to tie physical Wi-Fi devices together and, most likely, to infer relationship between the owners of those devices. This open up the potential for the proposed technique to be used as an additional tool when investigating real world crimes. It may however also be subject to abuse and could result in breaches in privacy.

A. Addressing possible limitations

The linked device pairs we used as ground truth have been collected from a set of volunteers devices. We have shown that, in this sample dataset, Wi-Fi fingerprints can be used to infer the relationship between the devices owners. However, one might argue that this sample may not be sufficiently representative of the whole population. We tested our tool in linking devices of other unknown individuals with no a priori knowledge of any established relationship. This was due to the difficulty of gathering ground truth evidence. However, a more thorough analysis of the collected public Wi-Fi fingerprints is left for future work, to try to establish implicit relationship (e.g. based on semantic analysis of some SSIDs in the fingerprints).

Finding linked devices in a population requires time that is quadratic in the population size, as all possible pairs must be tested for similarity. This might be too costly if one has millions of devices to match. A solution to this problem is to divide the matching task in two phases. First, divide devices in clusters that are likely be linked. For example, one could choose devices that share at least one (even very popular) SSID, thus restricting the number of combinations that need to be tried. Second, test all possible combinations within a cluster.

Finally, during our experiments, we noticed that some operating systems broadcast the SSIDs with a meaningful order which represents either the preferences of users or the most recent associations to the APs. Our technique could be improved by exploiting this additional information.

B. Counter-measures

Our technique primarily exploits the fact that wireless fingerprints can be easily collected. Disabling, or at least reducing the frequency of active probe requests is a first step to preventing large scale linkage of devices. However, as previously discussed, this will in turn create performances issues and might prevent devices from associating to APs with hidden SSIDs. Another class of solutions requires the deployment of a new dedicated protocol. Privacy preserving discovery services have been proposed in [START_REF] Lindqvist | Privacy-preserving 802.11 access-point discovery[END_REF], [START_REF] Pang | Tryst: The Case for Confidential Service Discovery[END_REF]. The latter achieves the goal of hiding the SSIDs when probing, however they require software modifications in current access points and devices, which will hamper the adoption of such proposals.

VI. CONCLUSION

We presented a mechanism capable of detecting links between individuals, by exploiting the information broadcast in plaintext by their wireless devices. We have shown on a controled dataset that a relationship can be easily detected. To the best of our knowledge this is the first use of wireless data to establish link between users. This work demonstrates yet another privacy breach allowed by the 802.11 probe requests, and this should further support the initiatives aiming at privacy preserving Access Point discovery [START_REF] Lindqvist | Privacy-preserving 802.11 access-point discovery[END_REF].

Fig. 1 .

 1 Fig. 1. Cumulative distribution function of the fingerprint size (number of SSID per device).

Fig. 2 .

 2 Fig. 2. Cumulative distribution function of the number of device per SSID.

Fig. 3 .

 3 Fig. 3. Intersection size distribution for Wi-Fi fingerprints pairs collected from volunteers.

Fig. 4 .

 4 Fig. 4. Intersection rarity distribution for device pairs with and without social link.

Fig. 5 .Fig. 6 .

 56 Fig. 5. ROC curve of the classifier.

Fig. 7 .

 7 Fig. 7.CDF of the Intersection rarity for device pairs detected in the PubProbes dataset for selected thresholds.

Fig. 8 .

 8 Fig. 8. Intersection size for device pairs detected in the PubProbes dataset for selected thresholds.

TABLE I SELECTED

 I THRESHOLD AND ASSOCIATED NUMBER OF PAIRS DETECTED IN THE PubProbes DATASET. CORRESPONDING TPR AND FPR ON THE CONTROLED DATA SET.

		Thresh.	Nb. detected pairs TPR 4	FPR 4
	Cosine-IDF	0.188	215 384	0.5	0
		0.117	502 102	0.8	0.0300
		0.0153	3 934 564	1	0.2446
	Psim-3	0.162	408	0.1	0
		1.57 10 -5	88 476	0.8	0.0772
		1.19 10 -8	3 812 524	1	0.2618

TABLE II NUMBER

 II OF CANDIDATES FOR EACH DEVICE IN THE VolunteerProbes DATASET WHEN PLUNGED IN THE PubProbes DATASET.

		Thresh.	Average Min	Max
	Cosine-IDF	0.188	34.025	0	142
		0.117	80.65	2	307
		0.0153	555.175	2	1411
	Psim-3	0.162	0.475	0	2
		1.57 10 -5	28.125	0	238
		1.19 10 -8	437.425	2	1208

We used the driver and software provided by the aircrack suite to monitor Wi-Fi frames.

We used tshark, the command-line version of wireshark

Fingerprint of size 1 can be explain by several reasons. It can come from an partial collection of the fingerprint, e.g. the device wasn't in range long enough to collect all the SSIDs. It is also possible that those SSIDs correspond to AP with hidden SSID.

The TPR and FPR in this table are those obtained with the VolunteerProbes data set in section III. They do not imply anything on the TPR and FPR that will be obtained on the PubProbes data set.