Gábor György Gulyás
email: gabor.gulyas@inria.fr

Gergely Acs
email: gergely.acs@inria.fr

Claude Castelluccia Near

György Gábor

Gulyás

Claude Castelluccia
email: claude.castelluccia@inria.fr

{a

} {u

} {a

Subset of Attributes Anonymity sets

Keywords: {U 1 }, {U 2 }, {U 3 }, {U 4 }, {U 5 }, {U 6 }

Several recent studies have demonstrated that people show large behavioural uniqueness. This has serious privacy implications as most individuals become increasingly re-identifiable in large datasets or can be tracked while they are browsing the web using only a couple of their attributes, called as their fingerprints. Often, the success of these attacks depend on explicit constraints on the number of attributes learnable about individuals, i.e., the size of their fingerprints. These constraints can be budget as well as technical constraints imposed by the data holder. For instance, Apple restricts the number of applications that can be called by another application on iOS in order to mitigate the potential privacy threats of leaking the list of installed applications on a device. In this work, we address the problem of identifying the attributes (e.g., smartphone applications) that can serve as a fingerprint of users given constraints on the size of the fingerprint. We give the best fingerprinting algorithms in general, and evaluate their effectiveness on several real-world datasets. Our results show that current privacy guards limiting the number of attributes that can be queried about individuals is insufficient to mitigate their potential privacy risks in many practical cases.

Introduction

People exhibit large behavioural uniqueness. The way how they move around [START_REF] De Montjoye | Unique in the crowd: The privacy bounds of human mobility[END_REF], purchase goods [START_REF] De Montjoye | Unique in the shopping mall: On the reidentifiability of credit card metadata[END_REF], configure their browser [START_REF] Eckersley | How unique is your web browser?[END_REF], or browse the web [START_REF] Olejnik | On the uniqueness of web browsing history patterns[END_REF] make them unique in very large populations. Even various combinations of seemingly innocuous behavioural attributes, such as in which shops they used to buy goods or where they live and work make them unique [START_REF] Zang | Anonymization of location data does not work: A large-scale measurement study[END_REF]. For example, it was demonstrated that only four spatio-temporal positions are enough to uniquely identify an individual 95% of the times in a dataset of one and a half million users [START_REF] De Montjoye | Unique in the crowd: The privacy bounds of human mobility[END_REF].

As many devices record people's behavioural patterns today, it becomes relatively easy for third parties to access such personal information. This has detrimental effect on individuals' privacy, as behavioural attributes can be easily used for the purpose of reidentification and tracking in different contexts. For example, advertiser companies often use behavioural attribute values (e.g., the list of installed fonts [START_REF] Eckersley | How unique is your web browser[END_REF] or applications [START_REF] Marshall | Twitter is tracking users' installed apps for ad targeting[END_REF]) to fingerprint website visitors in order to show them more personalized ads. That is, each time a user visits a website where a 3rd party tracker is embedded, the tracker retrieves the user's fingerprint (such as certain fonts installed on the device [START_REF] Boda | User tracking on the web via cross-browser fingerprinting[END_REF]) and link all his visited sites together [START_REF] Acar | The web never forgets: Persistent tracking mechanisms in the wild[END_REF]. As visited sites can belong to very different topics, the tracker can build accurate interest profiles of visitors in order to show them more personalized ads. However, the list of visited sites can also potentially uncover sensitive information such as sexual behaviour or religion among others. Indeed, most popular website categories that employ such user tracking were found to be porn (15%) and dating (12.5%) [START_REF] Bujlow | Web tracking: Mechanisms, implications, and defenses[END_REF].

Several countermeasures have been introduced against fingerprinting in the context of web-tracking [START_REF] Bujlow | Web tracking: Mechanisms, implications, and defenses[END_REF]. A simple solution is to completely disable all techniques which allow a tracker to fingerprint visitors, such as the execution of Javascript and Flash programs in a browser. However, this causes significant degradation of user experience and hence it is a less appealing option. Another, more flexible approach is to enable but constrain the usage of such techniques. For example, only limited number of system fonts can be used by an entire website [START_REF] Perry | The design and implementation of the tor browser[END_REF], or only limited number of applications can be opened from another application on a smartphone [2]. Hence, the goal of an adversary is to identify at most a given number of attributes (e.g., fonts or applications), whose values make either a targeted user or every user as unique as possible in the dataset, i.e., the number of users sharing the same values of these attributes is minimized.

In this paper, we show that the practice of constraining attribute queries per user to mitigate the privacy risks of fingerprinting is often inadequate. We construct efficient greedy fingerprinting algorithms for the above fingerprinting problems given constraints on the maximum size of the fingerprint. We provide essentially the best fingerprinting algorithms under standard computational assumptions. In particular, we address two general problems. Suppose a positive integer s. First, given a targeted user and all his attribute values, we want to know the subset of attributes with cardinality at most s, called the individual fingerprint of the user, whose values make this user as unique as possible in a given dataset. This is referred to as the targeted fingerprinting problem and analogous to the re-identification (de-anonymization) problem when, for example, a Tor Browser user is re-identified using some of his/her attributes which can be queried by visited websites. Second, we want to know the subset of attributes with cardinality at most s, called general fingerprint, whose values make each member of a group as unique as possible within the group. This is referred to as the general fingerprinting problem and analogous to the linking problem when, for example, the browsing activities of users are tracked, perhaps without re-identifying them.

For example, in Table 1, the individual fingerprint of U 1 with maximum size 2 is {A 2 , A 4 }, and the fingerprint values are {A 2 : 0, A 4 : 1} which make U 1 unique among 5 other users. However, U 2 has many possible fingerprints with maximum size 2 (e.g., {A 2 , A 4 }), but none of them provides unique fingerprint values to U 2 , because there is always at least another user which remains indistinguishable from U 2 with respect to the fingerprint. Table 2 shows the anonymity sets of all possible subsets of attributes with cardinality 3 (in one anonymity set, users share the same values of these attributes). We find that the only general fingerprint of all the six users, with maximum size 3, is {A 2 , A 3 , A 4 }, because this is the combination of attributes (with size at most 3) which yields the smallest anonymity sets.

We believe that the solutions of the above fingerprinting problems also have great importance in practice due to the upcoming European General Data Protection Regulation which mandates privacy risk assessment [START_REF]Proposal for European Parliament and the Council (General Data Protection Regulation)[END_REF]. This requires to measure the re-identification risk given certain "reasonable" constraints on the adversarial background knowledge. Moreover, the general fingerprinting problem also appears in the Article 29 Working Party Opinion 05/2014 on data anonymization techniques [5], which suggests that the linkability of records concerning the same data subject in an anonymized dataset should be mitigated in order to be "robust against re-identification performed by the most likely and reasonable means any third party may employ" [5].

Finally, we must note that our problems are different from the one in [START_REF] Motwani | Efficient algorithms for masking and finding quasi-identifiers[END_REF], which is about finding a minimal subset of attributes that provides a certain separation of all the users in a dataset. That is, given a separation value α, the minimum subset of attributes which provides separation α (i.e., it separates at least α fraction of all possible record pairs) is approximated in [START_REF] Motwani | Efficient algorithms for masking and finding quasi-identifiers[END_REF]. By contrast, in our problems, we are given a threshold s and we aim to give a subset of attributes with size at most s which provides the best separation. Obviously, the larger s the better separation is provided. Moreover, as we describe in Section 4.2, our general fingerprinting algorithm solves some problems in [START_REF] Motwani | Efficient algorithms for masking and finding quasi-identifiers[END_REF] more efficiently than prior algorithms. We also note that the naive approach of using a limited number of random attributes as a fingerprint, which is also employed by prior re-identification studies [START_REF] Achara | On the unicity of smartphone applications[END_REF] [10] [START_REF] De Montjoye | Unique in the shopping mall: On the reidentifiability of credit card metadata[END_REF], is inferior to our solution. In particular, these naive approaches build individual fingerprints from only those attributes whose values are set in a record. For example, in Table 1, {A 2 , A 4 } is not a possible fingerprint of U 1 with such a naive approach, as A 2 is not set in the first record. In fact, U 1 has no unique fingerprint with size 2 out of the attributes whose values are 1 in U 1 's record. Even more, in our work, missing attributes such as {A 1 = 0} could be a valid individual fingerprint of U 3 .

Our main contributions are summarized as follows:

-We provide essentially the best fingerprinting algorithms when constraints of the size of the fingerprint is provided. In particular, we first prove that both targeted and general fingerprinting are NP-hard in general and the best possible polynomial time approximations are greedy heuristics. -We provide real-life applications where these fingerprinting methods can be used in practice. In particular, we analyze the privacy protection used by many popular services, such as iOS or Tor Browser Bundle, which are based on limiting the number items (e.g., installed apps or fonts) that can be queried on

Model

Suppose that each individual in a population P has a set of items from a larger universe U with size n. The universe can contain any observable items of individuals (e.g., set of all possible applications installed on individual's smartphones, set of possible visited locations, etc.). Therefore, each user is represented by a binary vector u, called the user's profile, where u[i] = 1 only if the user has the corresponding item i ∈ U.

Our goal is twofold. First, we want to identify at most s items, called individual fingerprint items, which separates a single individual from others the most, i.e., whose values are the most unique to the individual in the population. We refer to this problem as targeted fingerprinting. Second, we want to identify at most s items, called general fingerprint, which simultaneously separate all users from each other in a group the most, i.e., whose values make each member of the group the most unique within the group. We call this problem as general fingerprinting.

In particular, we are given the following constraints. [START_REF]Proposal for European Parliament and the Council (General Data Protection Regulation)[END_REF] We have only access to a subset B of the whole population P , where one can think of B as a subsample of P . (2) We can query at most s items of a user to check whether the user has these items in his/her profile or not. Then, our exact problems to be solved are as follows.

Targeted fingerprinting: Given a targeted profile u and a subset B of population Simply put, we intend to compute the uniqueness of different itemsets in B and generalize these results to the whole population. The underlying assumption of this approach is that B is a subset of the population P , and hence if B has sufficient number of users, the uniqueness of different itemsets in B and P are also similar.

Hardness of fingerprinting

We show that identifying the fingerprint items for both problems described in Section 2 is NP-hard. In both cases, we reduce the problem to the Maximum Coverage Problem which is NP-hard [START_REF] Chekuri | Maximum coverage problem with group budget constraints and applications[END_REF].

Maximum

Algorithms

As the underlying problems for both fingerprinting problems are NP-hard, we cannot hope for finding the optimal solutions. However, a simple greedy heuristics, which approximates the solution of the Maximum Coverage problem, provides essentially the best possible approximations for our fingerprinting problems.

The greedy algorithm for the Maximum Coverage Problem iteratively picks the set which covers the largest number of uncovered elements. It can be shown that this algorithm achieves an approximation ratio of (1 -1/e) ≈ 0.632 [START_REF] Nemhauser | An analysis of approximations for maximizing submodular set functions i[END_REF]. That is, if OPT denotes the optimal solution (i.e., the maximum number of covered elements by at most s sets), then the greedy algorithm will cover at least (1 -1/e) • OPT elements. Moreover, it has also been proven that, unless P = NP, there is no 1-1/e-o(1) approximation for the Maximum Coverage Problem [START_REF] Feige | A threshold of ln(n) for approximating set cover[END_REF], which means that the greedy approach is essentially the best-possible polynomial time approximation for this problem.

Targeted fingerprinting

The first problem is straightforward to approximate with the greedy approach which is described in Algorithm 1. Instead of maximizing the number of users which disagree on the values of fingerprint queries with the targeted user u, we minimize the number of users which agree on those values with u. Although the two problems are equivalent, the solution of the latest is conceptually easier to capture.

We iteratively squeeze the anonymity set of u, denoted by anon_set in Algorithm 1, which is the set of users sharing identical values at all items of the fingerprint queries K with u. Initially, anon_set is composed of all the users in B. Then, in each iteration, we select the item i sep which separates u from the other profiles in the anonymity set the most, i.e., minimizes the number of profiles which agree at all items of K with u. For this purpose, we pre-compute a table, denoted as users in Line 2, which maps each item i ∈ U to the list of profiles which has the value of u[i] at position i. The computation of this table takes time of O(|B||U|). Then, we can easily identify the most separating item in each iteration by the intersection of the anonymity set of u and each list of table users. Fast implementations of the intersection of sorted integers are described in [START_REF] Lemire | SIMD compression and the intersection of sorted integers[END_REF]. If users in the anonymity set are no further distinguishable by any item, we terminate and return K as the final fingerprint (in Line 7). Otherwise, we continue the separation as long as |K| ≤ s.

This solution has a storage complexity of O(|B||U|) and computational complexity of O(s|B||U|).

Example 1. Suppose that u = U 5 in Table 1 and s = 3. First, we select the attribute which makes U 5 the most unique. U 5 shares the same values of A 1 , A 2 , A 3 and A 4 with 4, 3, 3, and 2 other users, respectively, hence we select A 4 in the first iteration. As a result, U 4 and U 6 still remain indistinguishable from U 5 . In the next iteration, we select the attribute which distinguishes U 5 from U 4 and U 6 the most. We have two options: A 2 or A 3 , as A 1 are identical for all of them. We select, say, A 2 , which means that U 5 and U 6 are still indistinguishable. Hence, in the final iteration, we select A 2 , which yields {A 2 , A 3 , A 4 } as the individual fingerprint of U 5 .

General fingerprinting

The naive greedy algorithm, which includes enumerating and storing each pair of profiles distinguished by each attribute, has a storage complexity of O(|U||B| 2 ) and computational complexity of O(s|U||B| 2 ). Instead, we design a greedy algorithm whose storage complexity is O(|U||B|) and its computational complexity is O(s|U||B|).

Our proposal is shown in Algorithm 2. We iteratively partition the set of profiles in B into anonymity sets, where all profiles in an anonymity set have identical values at all items of K (i.e., they are not distinguished by any items in K). Our goal is to compute a partitioning where each partition (i.e., anonymity set) is as small as possible.

To do so, in each iteration, we compute a separation metric of each item for the current partitioning C, which is the total number of separated pairs of profiles over all partitions (in Line 7-11). For example, if a partition is split into sub-partitions P 1 and P 2 by item i (where all profiles in a partition share identical value at position i), then the separation of i with respect to

P is |P 1 | × |P 2 |.
The total separation of i is the sum of separations over all partitions. Then, the item with the largest separation, denoted by i sep , is selected (Line 12). Finally, each partition in C is split by i sep into two sub-partitions (Line 17-21) such that a sub-partition contains all profiles from C which have identical values at position i sep . To speed up the computation of the separation metric, we pre-compute a table called items which maps each profile u to the set of items which are contained by u (in Line 2 of Algorithm 2). Again, this pre-computation runs in O(|U||B|).

Example 2. Suppose that s = 3 and we want to compute the general fingerprint of Table 1. The operation of the algorithm can also be illustrated by a binary tree which is shown in Figure 1. In the first iteration, we compute the separation metric of all attributes A 1 , A 2 , A 3 , A 4 which are 5×1, 4×2, 4×2, and 3×3, respectively. Hence, we select A 4 which separates all users into two partitions {U 1 , U 2 , U 3 } and {U 4 , U 5 , U 6 }. In the second iteration, we again compute the separation metric of A 1 , A 2 , A 3 over the two partitions, which are 2 × 1 + 0 = 2, 2×1+2×1 = 4, 2×1+2×1 = 4, respectively. Hence, we can select A 2 or A 3 . We select, say, A 2 , which produces partitions {U 1 }, {U 2 , U 3 }, {U 4 }, {U 5 , U 6 }. Next, we compute again the separation metrics of A 1 and A 3 over the new partitions which are 0 + 1 × 1 + 0 + 0 = 1 and 0 + 1 × 1 + 0 + 1 × 1 = 2, respectively. Therefore, we finally select A 3 . As 3 attributes have been selected, we terminate and return K = {A 2 , A 3 , A 4 } as the general fingerprint.

Notice that the maximum number of partitions in any iterations is at most |B| (i.e., the number of all records), and we only maintain the partitioning resulted by the last iteration. The complexity of computing the separation metric of each attribute takes O(|U||B|) (Line [START_REF] Bujlow | Web tracking: Mechanisms, implications, and defenses[END_REF][START_REF] Cai | Touching from a distance: Website fingerprinting attacks and defenses[END_REF][START_REF] Chekuri | Maximum coverage problem with group budget constraints and applications[END_REF][START_REF] De Montjoye | Unique in the crowd: The privacy bounds of human mobility[END_REF][START_REF] De Montjoye | Unique in the shopping mall: On the reidentifiability of credit card metadata[END_REF] in each iteration, as set-memberships can be checked in O(1) using hash-maps. Similarly, the separation itself (Line 17-21) runs in O(|U||B|), which means that the total complexity is O(s|U||B|) (Line 5-22).

Finally, we note that Algorithm 2 can be adapted to compute the minimum number of items which separate all users in B (this is referred to as the Minimum Key Problem in [START_REF] Motwani | Efficient algorithms for masking and finding quasi-identifiers[END_REF]). To do so, we only need to set s to |U| in Algorithm 2, which means that the running complexity becomes O(|U| 2 |B|). By contrast, the best greedy solution of this problem, which is also proposed in [START_REF] Motwani | Efficient algorithms for masking and finding quasi-identifiers[END_REF], runs in O(|U| 3 |B|). However, this is impractical if the number of attributes/items is large. Although several probabilistic relaxations of this problem is considered in [START_REF] Motwani | Efficient algorithms for masking and finding quasi-identifiers[END_REF] in order to reduce running complexity, these also degrade the accuracy of the solution.

Algorithm 1: Greedy Approximation for Targeted Fingerprinting

Input: Fingerprint size s, Universe of items U , Dataset B, Targeted user's profile u Output: Fingerprint items K 1 K := ∅ 2 users[i] := {u | u ∈ B ∧ u[i] = u [i]} for all i ∈ U 3 anon_set := B 4 repeat 5 // if

Applications

In this section, we describe some potential applications of targeted and general fingerprinting in practice. The first application relates to fingerprinting smartphone applications, which has also been partially studied in [START_REF] Achara | On the unicity of smartphone applications[END_REF]. The second application shows how to fingerprint users using the list of (non-)installed fonts in order to track them while they are browsing the web. Finally, we show a use-case of mass de-anonymization in location datasets using our fingerprinting techniques, which can serve as a potential investigation tool for authorities.

{U1, U2, U3, U4, U5, U6} A4 = 1 A4 = 0 {U1, U2, U3} {U4, U5, U6} A2 = 1 A2 = 0 A2 = 1 A2 = 0 {U1} {U2, U3} Iteration 1: isep = A4 K = {A4} Iteration 2: isep = A2 K = {A4, A2} Iteration 3: isep = A3 K = {A4, A2, A3} A3 = 1 A3 = 0 {U4} {U5, U6} {U2} {U3} A3 = 1 A3 = 0 {U5} {U6}
Fig. 1. General fingerprinting on the dataset of Table 1: Greedy algorithm builds a binary tree of partitions, where the leaves constitute the final anonymity sets of the fingerprint

K = {A 2 , A 3 , A 4 }.
Algorithm 2: Greedy Approximation for General Fingerprinting

Input: Fingerprint size s, Universe U , Dataset B Output: Fingerprint items K 1 K := ∅ 2 items[u] := {i | i ∈ U ∧ u i = True} for all u ∈ B 3 users[i] := {u | u ∈ B ∧ u i = True} for all i ∈ U 4 C := B // anonymity sets 5 while |K| < s do 6 // compute the separation of all items 7 separation[i] := 0 for all i ∈ U 8 for S ∈ C do 9 for i ∈ u∈S items[u] do 10 t[i] := |{u | u ∈ S ∧ i ∈ items[u]}| 11 separation[i] := separation[i]+t[i]•(|S|-t[i])
V := {u | u ∈ S ∧ isep ∈ items[u]} 20 T := T ∪ {{V }, {S \ V }} 21 C := T 22 K := K ∪ {isep} 23 return K

Smartphone App Fingerprinting

It has been shown that knowing the presence of four randomly chosen applications on a device are enough to reidentify users in a dataset of 54,893 users [START_REF] Achara | On the unicity of smartphone applications[END_REF]. Moreover, installed apps also reveal a lot about the owner's interests, and Twitter also used this information for targeted interest-based advertising among others [START_REF] Marshall | Twitter is tracking users' installed apps for ad targeting[END_REF]. In this section, we show how a third party can use such information for tracking. The main idea is to install a malicious application on the user's device which executes the fin-gerprint queries and identifies the fingerprint values of the user. As some operating systems, such as iOS, limit the number of apps whose existence can be checked by another app, the queries should be optimized such that their result distinguish as many users as possible. In particular, we envision a re-identification scenario using targeted fingerprinting (see Fig. 2a), when the browsing activities of some targeted users are tracked, and also a linking scenario using general fingerprinting (see Fig. 2b), when the browsing activities of multiple users are tracked without re-identifying any of them.

In both cases, when the (individual or general) fingerprint apps are provided to the malicious app, it opens a legitimate URL in the browser. This redirects to a third party tracker in order to generate and store a tracking cookie of the tracker as a visited first party in the browser 1 . This cookie contains the user's unique identifier. When the same browser visits a site having this tracker, the user will be tracked using the previously stored cookie (and also re-identified in case of targeted fingerprinting).

We must note that although this attack generates and stores cookies on the users' device with a random identifier, in contrast to traditional web cookies, this identifier is strictly bound to a persistent, behavioural attribute (i.e., the list of installed/non-installed apps). This means that even if the user deletes the cookie, he can still be re-linked to the same identifier by regenerating the same cookie based on possibly the same list of (non-)installed apps. The identifier even persists, if the application is removed and then re-installed, or 1 In order to circumvent the third-party blocking of Safari, the legitimate URL specifies a malicious website which redirects to the third-party tracker. The tracker then becomes a first party and can set a tracking cookie in the browser. Finally, the tracker redirects to the initial website, and the device can be tracked across websites. (a) Re-identification: after the tracker app is installed 1 , the individual fingerprint apps of the targeted users, whose identities are known, are retrieved from the 3rd party tracker 2 -3 . These fingerprints are matched with the list of (non)-installed apps on the device 4 . If there is a positive match, the browsing activities of the user along with his identity is tracked using a cookie created by the tracker app 5 .

application store web tracker 1 2 3 (b) Linking attack: the tracker app is installed with the general fingerprint apps which distinguish all users the most 1 . After the fingerprint values are computed by checking the existence of the fingerprint apps on the device 2 , a cookie is created by the tracker which is bound to these fingerprint values. As a result, the browsing activities of any user in the group can be tracked 3 .

Fig. 2.

Targeted fingerprinting (for re-identification) and general fingerprinting (for linking) using the list of installed apps on a smartphone.

other applications are installed that can generate the same identifier. Next, we provide the details of the attack, which consists of three phases: (1) Identify the fingerprint apps (queries) of the targeted user (targeted fingerprinting) or a group of users (general fingerprinting), (2) Retrieving the list of fingerprint apps on users' device, (3) Deanonymize the targeted user and/or track user activities. As the third phase has been detailed before, we will focus on the first two phases.

Identifying the fingerprint apps

For targeted fingerprinting, the malicious 3rd party tracker, called as adversary henceforth, first needs to obtain the list of (non-)installed apps of a known, targeted user. This is relatively easy by consulting with some social media where users often post the applications they use, or simply retrieving the app list directly from the user's device (if the user has iOS 9, the adversary may get access to the full list of installed apps before the user upgrades to iOS 9, see below for details). As another work suggests [START_REF] Achara | On the unicity of smartphone applications[END_REF], the adversary does not need to get the complete list of applications, but only 4 random apps are sufficient to re-identify the user with 95% of the times. We show later that, by using the greedy optimization algorithm, described in Section 4.1, the adversary can re-identify most users with even fewer queries.

For both targeted and general fingerprinting, the adversary needs to have access to a subset of user profiles in order to identify the fingerprint apps of the users to be tracked. In particular, for targeted fingerprinting, the adversary identifies at most s apps, using Algorithm 1, whose existence need to be checked on the targeted user's device to construct his/her individual fingerprint. As we detail below, the value of s changes depending on which operating system the app is built for. In certain cases, iOS allows to query at most 50 apps, while in other cases the queries need to be pre-defined and cannot be changed later when the app is installed, which is reminiscent of our general fingerprinting problem.

For general fingerprinting, the dataset is used to identify at most s fingerprint apps, using Algorithm 2, whose existence need to be checked on every group member's device to construct a fingerprint for each group member which sufficiently distinguish them. This dataset can contain the profiles of the group themselves, or another subset of the same population. After calculating the phone identifier, this could be used as an identifier for web tracking; we show how in Fig. 3 (with a proof-of-concept demo).

Retrieving the fingerprint apps on iOS

Equipped with the list of the fingerprint apps, the malicious application needs to check their existence on the device. To the best of our knowledge, Android al- Example on how the device identifier could be leaked to the web. The malicious application opens a URL that seems to be legitimate, but it contains the hidden or obfuscated device identifier 1 . In order to circumvent third-party blocking privacy settings of Safari, the malicious websites redirects to a third-party tracker 2 . The tracker then is now becomes a first party and can set a tracking cookie. Finally, the tracker redirects to the initial website 3 , while it also remains able to track the devices across websites.

lows to retrieve the complete list of installed apps, but Apple has introduced some limitations with the release of iOS 9 [2]. On iOS, applications can use the canOpenURL() call to determine if another application is available on the system (i.e., whether it can be called).

That is, each fingerprint app query corresponds to a call of canOpenURL() specifying a URL. The call returns a boolean value indicating whether or not the specified URL's scheme can be handled by some app installed on the device. However, Apple introduced two restrictions that apply when the program is compiled on iOS 9 [2]. Applications built for systems before iOS 9 but executed on iOS 9 can invoke canOpenURL() with at most 50 distinct apps. This number is reset each time the user re-installs or upgrades the app. Applications built for iOS 9 and also executed on iOS 9 have to declare in advance which other applications they would like to check with canOpenURL(), making abuses noticeable well in advance. Every canOpenURL() call which is over the limit of 50, or specifies a non-declared app, will return a negative response. We emphasize again that these limitations are in effect only when a user builds an app on iOS 9, leaving users of older systems vulnerable. The proportion of such systems was measured to be 23% according a statistic revealed by the Apple Store (as of February 22, 2016) 2 .

2 Statistic published by the Apple Store: https://developer. apple.com/support/app-store/

Font fingerprinting

Fingerprinting projects, such as the Panopticlick3 [START_REF] Eckersley | How unique is your web browser[END_REF] and the cross-browser fingerprinting project4 [START_REF] Boda | User tracking on the web via cross-browser fingerprinting[END_REF] have revealed that websites can effectively query browser properties to track their visitors. In particular, it has been shown that detecting fonts is an important technique to track users as their entropy is one of the highest among the available identifiers [START_REF] Eckersley | How unique is your web browser[END_REF], and they can be queried independently from the browser [START_REF] Boda | User tracking on the web via cross-browser fingerprinting[END_REF]. Font detection mechanisms were also shown to be used in device tracking mechanisms [START_REF] Nikiforakis | Cookieless monster: Exploring the ecosystem of web-based device fingerprinting[END_REF].

One cutting edge web browser that promises anonymity is called the Tor Browser Bundle5 (TBB) or the Tor Browser, whose anonymity guarantees have been widely studied [START_REF] Cai | Touching from a distance: Website fingerprinting attacks and defenses[END_REF][START_REF] Hayes | k-fingerprinting: a robust scalable website fingerprinting technique[END_REF]. Up to version 5.5, TBB developers tackled font-based tracking by introducing two limits: one on the number of font load trials, and one on the number of successful font loads [START_REF] Perry | The design and implementation of the tor browser[END_REF]. These parameters are called browser.display.max_font_count and browser.display.max_font_attempts, and by default they are set to a value of 10. These options can be changed by accessing about:config. Detecting the existence of fonts on a system is relatively easy using Javascript, which can be embedded on the visited website: it can be measured if the rendered text has a different width and height compared to the system default 6 . Notice that TBB allows the execution of Javascripts by default due to their prevalence on the web today. TBB addresses two types of attacks, among others, which we analyze in this paper: de-anonymization (see Section 3.1.2 in [START_REF] Perry | The design and implementation of the tor browser[END_REF]) and linking attacks (see Section 3.1.4 in [START_REF] Perry | The design and implementation of the tor browser[END_REF]). Our attack schemes are depicted in Fig. 4.

De-anonymization occurs when an attack correlates TBB and non-TBB activities of a targeted user. First, the adversary collects the available fonts on the user's system when the user visits a website with a regular, non-TBB browser, thus the list of fonts can be associated with the user's identity. We note that this does not mean that the site is under a total control of the adversary. This can also be a site where a malicious tracker (or web bug) is installed. Then, the adversary selects at most 10 fingerprint fonts whose existence need to profiles by installing trackers (or web bugs) on websites which are also accessed without TOR 1 . In case of targeted fingerprinting, when the user visits a site containing a malicious tracker 2 , the adversary gets informed by is trackers and retrieves the complete profile of the targeted user 3 . Then, using the collected dataset of font profiles, the adversary can compute the fingerprint fonts of the user, which can be later queried in order de-anonymize the user when he visits a site through TOR containing a malicious tracker 4 . In case of general fingerprinting, the adversary computes the general fingerprint using the collected dataset of font profiles, and queries these fonts from each TOR visitor 4 .

be checked on the user's system to re-identify him/her. When the user visits this or another malicious website via Tor Browser, this site queries these fingerprint fonts through Javascript. As a result, "private" (TBB) and "public" (non-TBB) activities of the web user can be linked. De-anonymization is analogous to our targeted fingerprinting problem, where the maximum number of fingerprint queries is limited to 10.

Linking attack refers to linking the activities of a user together within TBB. As opposed to deanonymization, the identity of the user is not known (i.e., the attack does not require a visit to a site with a regular browser), and the goal is to track the user using TBB. In this case, the adversary needs to identify at most 10 fingerprint fonts which can distinguish any TBB user from the rest. This means that a malicious tracker queries the same set of 10 fonts of each TBB user visiting a site, and the results of these queries serve as a fingerprint for each user. This is analogous to our general fingerprinting problem, where the maximum number of fingerprint queries is limited to 10. Notice that while these fingerprints may not be sufficiently unique to every user in the whole TBB community, they should be quite unique per site. According to a measurement based on TBB usage data of 2012-2013 [START_REF] Graham | The anonymous internet[END_REF], the average number of daily Tor Browser users per country was well below 1%, e.g., 0.08% in Europe, meaning that even visitors of well known websites receiving a large daily traffic could be easily identified even if they would use TBB.

In order to identify the fingerprint fonts, the adversary needs to have access to a subset of all profiles in the TBB population, where a profile contains the list of installed and non-installed fonts of a user.

Note on deprecation:

In the beginning of our investigation, we found out that the font limitation was not working at all in the Tor Browser, making TBB users vulnerable to the above attacks without limitation (the current stable version was TBB 5.0.4 at that time). We published a blog post to demonstrate the feasibility of the above attacks [START_REF] Gulyás | Update your tor browser settings -otherwise it is less anonymous than you would think[END_REF], and informed the developers about this issue. It turned out that developers had already been working on other workarounds to defeat font fingerprinting [START_REF] Gacar | Improve persistence and webfont compatibility of font patch, comment #13[END_REF], and the lack of the above limitation on the number of font queries was due to implementation difficulties in newer Firefox versions. The new countermeasure, which is shipping the Tor Browser with a pre-defined set of fonts that the browser can only use, was introduced two months later with TBB 5.5 at January 26, 2016. While this makes our fingerprinting techniques deprecated in the context of TBB, we believe that our work can be a useful warning for developers who may use similar countermeasures in the future, as the case of application fingerprinting also shows.

Mass de-anonymization in location datasets

We can also use fingerprinting techniques in a quite different context than online tracking, that is, to deanonymize a location database (e.g., a Call Detail Record dataset). Suppose that the adversary has access to a weakly anonymized location dataset containing the set of visited locations per individual in a city (time information is omitted for the sake of simplicity). For example, this dataset contains pseudonymized records (i.e., only direct personal identifiers are removed), but location information are kept intact. The goal of the adversary is to re-identify as many users as possible in this dataset, i.e., to perform a mass de-anonymization attack without knowing any locations of the victims a priori 7 , but only their personal photos (e.g., by crawling a social media of the city). The plan of the adversary is to mount at most s cameras at different spots of the city, and reidentify all individuals observed by any of these cameras by using some face recognition mechanism and the photos that she has. Knowing the fact that an individual does (not) visit these camera spots (i.e., the visiting pattern of individuals with respect to only these spots), the adversary locates the record which has the observed visiting pattern in the anonymized dataset, and learn all other unknown visited places of the individual. 8In order to maximize the number of de-anonymized users in the dataset, the adversary wants to identify at most s camera spots which can distinguish all users in the anonymized dataset as much as possible. In particular, the values of any record at these spots should be unique in the dataset, or at least the number of records sharing the same values at these spots should be minimized. This goal is reminiscent of our general fingerprinting problem. Hence, the adversary runs our greedy heuristic in Algorithm 2, with input s and the anonymized dataset, in order to identify these fingerprint spots.

Although deploying cameras at any spot of a city is unlawful and easily detectable, we believe that the above scenario is not far-fetched at all. Authorities, who have the right to install or access such surveillance cameras, may be interested in the above "privacy-friendly" approach of learning the trajectories of suspects. Indeed, authorities do not need to ask telecom companies to reveal the exact identity of any of their customers, but only their anonymized CDRs.

Experimental Results

In this section, we compute the uniqueness of targeted and general fingerprints on real-world datasets. In particular, we consider three real-world datasets, each corresponding to an application described in Section 5, which can be used by the adversary to identify the fingerprint items of users. We report the size of the anonymity sets of all targeted and general fingerprints for each dataset.

Datasets and Ethical Considerations

Smartphone applications

Dataset

The dataset comes from the Carat research project [START_REF] Oliner | Carat: Collaborative energy diagnosis for mobile devices[END_REF]. The dataset includes data from 54, 893 Carat Android users between 11/03/2013 and 15/10/2013 [START_REF] Truong | The company you keep: Mobile malware infection rates and inexpensive risk indicators[END_REF]. During this period, the Carat app9 was collecting the list of running apps (and not the list of all installed apps) on users' devices when the battery level changes. As collecting the list of running apps multiple times over more than 7 months is likely to sum up to the set of all installed apps of a user, we consider a record as the set of installed applications in this paper, even if a record might not be the complete set of installed apps all the time.

We removed system apps from all records because they are common to all users. Without system apps, our analyzed dataset contains 92, 210 different applications whereas the total number of apps available on the GooglePlay were around 1 million during this time 10 . Table 3 summarizes the main characteristics of our dataset.

Ethical Considerations

This dataset contains the list of installed smartphone applications per user. The data were collected with the users' consent, and they were explicitly informed that their data could be used and shared for various research projects. In fact, the Carat privacy policy (available at http://carat.cs.helsinki.fi) clearly specifies that "Carat is a research project, so we reserve the right to publish our results online and in academic publications. We also reserve the right to release the data sets into the public domain." Also, the dataset was shared with us by the Carat team in a pseudo-anonymised form. In particular, identifiers were removed, and each application name was replaced with its SHA1 hash. It contained 54, 893 records [START_REF] Truong | The company you keep: Mobile malware infection rates and inexpensive risk indicators[END_REF], i.e. one record per user. Each record is composed of the list of applications installed and run by the user. Furthermore, the data sharing agreement that we signed, stipulated that we cannot use the dataset to deanonymize the users in the dataset.

Fonts used by web browsers

Dataset

This dataset contains the list of installed fonts, the screen size and available screen size per user. The data collection was done on fingerprint.pet-portal.eu where users could test and compare their OS fingerprint in different browsers. Data was collected with the purpose of analyzing OS fingerprint uniqueness. In particular, users were advised to run the test in different browsers which collected the list of installed fonts, among others, and compare the calculated fingerprint if they match The website have collected more than 107, 102 font profiles between 05/04/2012 and 22/09/2015, which do not necessarily belong to distinct users due to the purpose of the project. In our experiments, we only used a subset of users and attributes that were collected, and the data was cleaned as follows.

In order to remove possible duplicates (a user could visit the fingerprinting site multiple times), several records were removed by comparing hashed IPs and stored usernames. If username was not given by a person who conducted the test, the site stored the font profile of the user in an evercookie 11 . Given a list of profiles having the same IP address where creation dates were closer than 10, only the first entry was preserved. All record duplicates having the same username were removed regardless of date differences.

The resulted database had 43, 656 records, which contained the list of detected fonts, and the screen and available screen sizes12 of each user. As this is the first paper using the given dataset, we provide descriptive metrics of the data in order to help understanding our results. We also provide attributes of the original Panopticlick dataset for comparison, and Fig. 5b is also easily comparable with Fig. 3 in [START_REF] Eckersley | How unique is your web browser[END_REF]. This figure confirms that our dataset has been cleaned properly. The main properties of the dataset is described in Table 4.

Ethical considerations

The data were collected with users' consent on a website that raises awareness on tracking using OS (or device) fingerprinting. On the website it is clearly described that all collected information is treated confidentially, and the goal of the data collection is to analyze uniqueness of generated OS fingerprints. Types of data that are collected is also clearly communicated, from which we used screen size, available screen size, and available fonts per user. The data we used was shared with us with the operators of the fingerprint website, and our agreement allowed us to conduct the uniqueness study we present in this paper.

Location dataset

Dataset

This dataset contains the list of visited locations per user in a large European city. We use a CDR (Call Data Record) dataset provided by a cell phone operator in Europe. A cell tower is visited by an individual, if the operator has a recorded event at the tower related to the individual over the observed period (01/09/2007 -17/10/2007). An event can be an incoming/outgoing call or message to/from the individual. The dataset contains the events of 4, 427, 486 users at 1, 303 towers within the administrative region of the city, where the GPS coordinates of all the towers are also available. In our dataset, a record contains only the set of towers that are visited by a user over six weeks, i.e., it does not contain the time of visits.

The average number of individuals per tower over this period was 38, 817 with a standard deviation of 50, 911. The total area of the city which is covered by cell towers is 128.1 km 2 . The main characteristics of our dataset and the cell towers are shown in Table 5.

Ethical Considerations

The dataset was shared with us by the telecom operator in a pseudo-anonymised form. Each record in this dataset represented an event belonging to a single user with a pseudonymized phone number, i.e., the last 8 digits of the original phone number were changed to a randomly chosen 8 digit number. The record included the GPS location of the cell tower, the type of the event (incoming/outgoing SMS or call) and the timestamp of the event. Records (events) belonging to the same individual contained identical pseudonymized phone number, hence all events of an individual could be linked together. We signed a data sharing agreement with the operator which stipulated that we cannot use the dataset to deanonymize the users in the dataset.

Targeted Fingerprinting

Smartphone users by applications

We run Algorithm 1 on the smartphone application dataset, described in Section 6.1.1, to generate fingerprints for each user in our dataset with different constraints on the maximum size of the fingerprint. When s = 50 (this threshold comes from the iOS countermeasure detailed in Section 5.1.2), on average, only 2.3 app queries per user provided the fingerprint values. The exact distribution of fingerprint length is shown in Fig. 6. Our greedy algorithm generated fingerprints shorter than 50 apps for all users. With the exception of 27 users, 10 apps are enough for re-identification in our dataset. However, we must note that this does not necessarily mean unequivocal re-identification, as our algorithm can terminate before the fingerprint size reaches s (see Line 7 in Algorithm 1). Thus, for example, if there are only 2 apps which distinguish the targeted user from the others, the fingerprint will consist of two items for any s ≥ 2. Another example is the case of a user who only installed a single app, which is also installed by some other users. For such user that application is the only possible fingerprint.

For s = 50, we find 4,098 users (7.47%) in our dataset who cannot be uniquely re-identified and therefore belong to some anonymity sets with size greater than 1. We visualized the sizes of anonymity sets and their population in Fig. 8a. This figure shows that 96.15% of users are almost unique (the size of their anonymity sets is at most 3), while only 3.02% of users fall into anonymity sets with size at least 10. (Note: large anonymity sets concerning only a couple of users are possible as these anonymity sets are not disjoint.)

We also measured the size anonymity sets when s = 2 (instead of 50); results are reported in Fig. 8b. The proportion of almost unique users decreased to 85.54%, eventually showing that the current privacy protection method on iOS is ineffective against fingerprinting users. In addition, this uniqueness value is larger than the one in [START_REF] Achara | On the unicity of smartphone applications[END_REF], which was about 75% for 2 apps. The difference, as we have discussed in Section 1, is due to the fact that only existing apps of users are selected to measure their uniqueness in [START_REF] Achara | On the unicity of smartphone applications[END_REF], meanwhile we optimize the queries for the targeted user's profile and they can also include the queries of non-existing apps.

Finally, we note that similar uniqueness is expected in even larger datasets based on the same reasoning as in [START_REF] Achara | On the unicity of smartphone applications[END_REF]. With a growing number of users, the number of available applications should also increase with a lower pace. This means that the number of possible combinations of apps also increases exponentially with each new application added to the dataset.

TBB users by font detection

We also run Algorithm 1 on the font dataset, described in Section 6.1.2, to measure the effectiveness of fingerprinting using fonts. We believe that, despite that non-Firefox browsers are not excluded from our dataset, our results are generic. While there are minor differences of JavaScript font detection in different browsers, this method is reliable enough to detect the majority of fonts in all browsers. As a result, a record characterizes the OS of a user, rather than his browser. We also studied the uniqueness of fingerprints when they are extended with the screen resolution and available screen size. While the Tor Browser makes various efforts to hinder access to this information, it cannot block full access [START_REF] Perry | The design and implementation of the tor browser[END_REF]; for example, it warns users of related privacy hazards in case the window of a Tor Browser maximized.

The distribution of fingerprint length is shown in Fig. 7. Results are better for user privacy compared to our app dataset, as only 53.8% of users have fingerprints no longer than the font load limit of s = 10 imposed by the Tor Browser (see Section 5.2). Peaks appearing for longer length are likely to be due to pre-set OS configurations that were not altered at all, or only slightly. For example, these can be computers running in institutions or at companies, where configurations are very similar to each other. Barely modified fresh installs could also be behind this phenomena.

As font fingerprints are not necessarily unique (due to the same reasons discussed in Section 6.2.1), we report the sizes of anonymity sets for each user. Results are shown in Fig. 9a. Detection of 10 fonts allows unique identification of 13, 155 users in our datasets (30.13%), and 39.26% of the users are almost unique (i.e., has anonymity set size at most 3). This roughly means that one third of TBB users at a given service can effectively be de-anonymized.

We also report the size of anonymity sets if screen resolution and available screen size are also added to the fingerprint (see Fig. 9a and9b). These results show that these extra attribute values significantly increase the uniqueness of users. While we find that the proportion of almost unique users is roughly doubled when available screen size is added to the fingerprint, probably this would not be the case for TBB users. In particular, TBB users are discouraged to install any browser extensions and other tools which usually change the available screen size.

We additionally examine if decreasing the limit s is a remedy for the situation. Our negative findings show that when the font load limit is decreased to 5, significant uniqueness can be still observed (see Fig. 10 for details). For example, detecting solely 5 fonts makes still 30.58% of users unique (Fig. 10a).

General Fingerprinting

We run Algorithm 2 on the three datasets to compute general fingerprints and partition users into anonymity sets, where users have the same fingerprint value in each set. The average size of anonymity sets for small fingerprint sizes (less than 20) are shown in Fig. 12. The average set size drops fast; we observed 135.15 for s = 10 in s = 29. In case of the other datasets, the average never falls below 3, and we found 3.99 at s = 76 for the app dataset, and 3.96 at s = 73 for the font dataset. While these results may not be promising to the adversary, measuring the proportion of unique users, whose anonymity sets are singletons, provides a different view. Unique users do not share the same fingerprint value with any other users in the dataset. As Fig. 13 shows, the proportion of unique users remains relatively low. The proportion does not change too much even for almost unique users which have anonymity set with size at most 3.

As regards linking attack against TBB users, we find that the available screen size as an auxiliary information (in addition to the detection of 10 fonts) makes this attack a significant threat, as 8, 303 users (19.02%) are unique in this case. We provide further details in Fig. 11 on the apps dataset, where uniqueness was the highest, that is, 76.30% of users have a size of anonymity set smaller than 4. This means that even if all 50 apps need to pre-defined for all users, which is the case for iOS 9 at present, privacy threats still persist. For the location 10 0 10 1 10 2 10 3 10 4

Anonymity Set Size (k) dataset, we find that 29% of all users are unique, and the average size of the anonymity set is 3.13 with s = 100. That is, an authority would need to deploy at least 100 cameras in the city to re-identify every third person on average in an pseudonymized CDR dataset (see Section 5.3).

Conclusion

In this paper we addressed two fingerprinting problems with constraints on the maximum size of the fingerprint. Targeted fingerprinting is executed on a specific user, whose profile and identity are known to the adversary, and the goal is to re-identify him/her in an anonymous context, where only a limited number of his attributes can be queried. General fingerprinting is used to link the activities of multiple users without their reidentification in an anonymous context, where only a limited number of their attributes can be queried. We provided essentially the best fingerprinting algorithms for both problems.

We evaluated these fingerprinting methods on reallife examples focusing on web tracking, smartphone user identification and mass de-anonymization of location datasets. We showed that targeted fingerprinting is a significant threat to user privacy, as a significant ratio of users can be re-identified with our technique in case of web tracking and smartphone identification. This holds even when tighter constraints are applied than the default. Our results with general fingerprinting also support this claim; we found that 19.02% of web browsers could be uniquely identified by combining the presence of 10 fonts and the available screen size. We also found that by installing 100 surveillance cameras in a city of 4 million people, one can re-identify on average every fourth person in pseudonymized CDR dataset. Moreover, by querying 50 apps on a smartphone, which can be even pre-defined and identical for all users, one can obtain a unique fingerprint value for more than 65% of users in a dataset of 55k users.

All these findings show a conceptual weakness of limiting attribute access as a privacy guard.

Acknowledgement

The authors are thankful for Viktor Fábián and Jagdish Prasad Achara for the discussions and their advises related to the iOS platform. This work was carried out during the tenure of an ERCIM 'Alain Bensoussan' Fellowship Programme. Some icons we used in the illustrations were made by Freepik (from www.flaticon.com)

no further separation is possible 6 if 7 break 8 isep 10 K

 67810 min i∈U \K {|users[i] ∩ anon_set|} = 0 then := arg min i∈U \K {|users[i] ∩ anon_set|} 9 anon_set := anon_set ∩ users[isep] := K ∪ {isep} 11 until |K| = s or |anon_set| = 0 12 return K

12 isep 16 /

 1216 := arg max i∈U \K separation[i] 13 // if no further separation is possible 14 if separation[isep] = 0 then 15 break / splitting all partitions with isep 17 T = ∅ 18 for S ∈ C do 19

  Fig.3. Example on how the device identifier could be leaked to the web. The malicious application opens a URL that seems to be legitimate, but it contains the hidden or obfuscated device identifier 1 . In order to circumvent third-party blocking privacy settings of Safari, the malicious websites redirects to a third-party tracker 2 . The tracker then is now becomes a first party and can set a tracking cookie. Finally, the tracker redirects to the initial website 3 , while it also remains able to track the devices across websites.

Fig. 4 .

 4 Fig.4. Attacks against TOR browser. Initially, the malicious websites (or collaborating sites) build a large dataset of (font)profiles by installing trackers (or web bugs) on websites which are also accessed without TOR 1 . In case of targeted

Fig. 5 .

 5 Fig. 5. Descriptive attributes of our datasets that also enablesthe comparison with previous work in[START_REF] Eckersley | How unique is your web browser[END_REF].

Fig. 6 .Fig. 7 .Fig. 8 .Fig. 9 .

 6789 Fig. 6. Distribution of the length of individual fingerprints for the app dataset. Almost all users have fingerprint size smaller than 10, with only 27 exceptions.

Fig. 10 .

 10 Fig. 10. Targeted fingerprinting: Uniqueness in the font dataset with size of anonymity sets when s = 5.

Fig. 11 .

 11 Fig. 11. General Fingerprinting: Distribution of size of anonymity sets for different values of s on the apps dataset.

Fig. 12 .Fig. 13 .

 1213 Fig. 12. General fingerprinting: Average size of anonymity sets as the function of s.

Table 1 .

 1 Example dataset where each row is a record of a user with binary attributes A 1 , A 2 , . . . , A 4 .

Table 2 .

 2 The anonymity sets of all possible subsets of attributes (from Table1) with size 3. The single general fingerprint is {A 2 , A 3 , A 4 } whose values make every user unique.

	a device for the purpose of fingerprinting. Our aim
	is to raise awareness about the weakness of such
	privacy guards.
	-We evaluate our fingerprinting algorithms on differ-
	ent large real-life datasets. Specifically, we analyze
	the separation of different targeted as well as gen-
	eral fingerprints on several datasets, where a record
	can contain the list of installed fonts, smartphone
	applications, or visited locations by an individual.

The code base related to this paper is available at https://github.com/gaborgulyas/constrainted_ fingerprinting.

  P . Identify at most s items {i 1 , i 2 , . . . , i s } ⊂ U such that the number of profiles in B which share identical values at positions i 1 , i 2 , . . . , i s with u is minimized. General fingerprinting: Given a subset B of population P . Identify at most s items {i 1 , i 2 , . . . , i s } ⊂ U such that the number of profiles in B which share identical values at positions i 1 , i 2 , . . . , i s is minimized.

Coverage Problem: Given

  Let u denote the profile of the targeted user. Assign a set of profiles P i ⊆ B to each item i ∈ U, where item i of each profile in P i has value u[i]. Let P = {P i |i ∈ U}, where |P| = |U|. The problem is to find at most s sets in P such that the size of their intersection is minimized. This is identical to finding at most s sets such that the size of the complement of their intersection is maximized. Following from De Morgan's laws, this is further equivalent to finding at most s sets in P = {P i |i ∈ U} such that the size of their union is maximized, where P i contains all profiles whose value at i is not u[i]. This problem is identical to the Maximum Coverage Problem, and hence Problem 1 is

		a positive in-
	teger s and a collection of sets C = C 1 , C 2 , . . . , C m . Find
	a subset C ⊆ C of sets such that |C | ≤ s and the num-
	ber of covered elements	Cj ∈C C j is maximized.
	The reductions are as follows.
	Targeted fingerprinting:

NP-hard. General fingerprinting: Let

  A denote the number of all pairs of profiles in B, where |A| = |B| 2 . For each item i ∈ U, let T i ⊂ A denote all pairs of profiles which have different values at i (i.e., they can be separated by item i). Clearly, i∈U T i = A. Let T = {T i |i ∈ U}, where |T| = |U|. Hence, Problem 2 is equivalent to finding at most s sets in T such that the size of their union (i.e., the total number of separated pairs of profiles) is maximized, which is again the Maximum Coverage Problem.

# of records 54, 893 # of all apps in the dataset 92, 210 Maximum record size 541 Minimum record size 1 Average record size 42 Std.dev of record size 39Table 3 .

 3 Characteristics of the smartphone app dataset

	# of records	43, 656
	#

of all fonts in the dataset 81, 195 Maximum record size 6, 072 Minimum record size 1 Average record size 143 Std.dev of record size 118Table 4 .

 4 Characteristics of the font fingerprint dataset

Panopticlick current User agent string 10.0 7.18

	Timezone	3.04 2.23
	All fonts	13.9 7.79
	Plugins	15.4 7.91
	Screen	4.83 3.34
	(a) Comparison of entropy values for each attribute.
				p
	p
		p p p pp	p p
		p p p p pp p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pp pp pp p p p p p p p	p p p p p p p p	user_agent timezone fonts plugins screen
	10 0	10 1 Anonymity Set Size (k) 10 2 10 3 10 4	10 5

(b) Number of users w.r.t. the sizes of the anonymity set they belong to.

Dataset size 4, 427, 486 # of all cell towers 1303 Maximum record size 422 Minimum record size 1 Average record size 11.42 Std.dev of record size 17.23 Total area of all cells 128.1 km 2Table 5 .

 5 Characteristics of our location dataset (up) andVoronoi-tessellation of cell towers (down). Red lines denote the boundaries of districts.

Website: https://panopticlick.eff.org

Website: https://pet-portal.eu/fingerprint/; newer version available at: https://fingerprint.pet-portal.eu

The TOR project website can be found here: https://www. torproject.org

Example: http://www.lalit.org/lab/javascript-css-fontdetect/

Otherwise, the adversary has good chance to locate the victim's record based on[START_REF] De Montjoye | Unique in the crowd: The privacy bounds of human mobility[END_REF]

8 It is not reasonable to assume that the adversary can mount any number of cameras due to budget constraints.

http://carat.cs.helsinki.fi

f f f f f ff ff ff ff f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f ff f f f ff f f f f f f f f f f f f

Evercookies: http://samy.pl/evercookie/

Referring to JavaScript properties screen.width & screen.height and screen.availWidth & screen.availHeight


a programmer dreams that he commands Eclipse, is it not Eclipse dreaming it is a programmer? (after 庄子)

  is part of the real world TM object-orientation can be used for representing object-orientation An object meta-model a UML model modelling the entities of object-orientation, i.e. classes, associations, attributes, methods, ... with classes, associations, attributes, methods, ... inherently ambiguous plays on words programming languages, although formal, are ambiguous, too because they serve as man-machine interfaces through various names compilers don't joke! Foundation requirement in the modelled program, each occurrence of the name of a modelled entity must denote a single instance of the metamodel inherently ambiguous plays on words programming languages, although formal, are ambiguous, too because they serve as man-machine interfaces through various names compilers don't joke! Foundation requirement in the modelled program, each occurrence of the name of a modelled entity must denote a single instance of the metamodel named A a method named foo(), defined in A class B extends A { foo() {...} bar() {...} } a class named B, subclass of A a method named foo(), defined in B redefining foo() of A a method named bar(), defined in B with class A a type annotation with class B a message foo() introduced in A sent to x with late binding a message bar() introduced in B class A { foo() {...} } a class, named A a method named foo(), defined in A class B extends A { foo() {...} bar() {...} } a class named B, subclass of A a method named foo(), defined in B redefining foo() of A a method named bar(), defined in B with class A a type annotation with class B a message foo() introduced in A sent to x with late binding a message bar() introduced in B class A { foo() {...} } a class, named A a method named foo(), defined in A class B extends A { foo() {...} bar() {...} } a class named B, subclass of A a method named foo(), defined in B redefining foo() of A a method named bar(), defined in B with class A a type annotation with class B a message foo() introduced in A sent to x with late binding a message bar() introduced in B An object model of the object model (3/3) A single class for classes for all usages: declarations, type annotations and new Two classes for properties a class for local properties, implementations defined in a class a class for global properties, messages invoked from the code What are properties? methods, attributes formal type parameters, virtual types, ... by substituting an instance of local/global property to each property name, even when it seems ambiguous Actual ambiguities = compiler errors When this substitution is not possible (several candidates) by substituting an instance of local/global property to each property name, even when it seems ambiguous Actual ambiguities = compiler errors When this substitution is not possible (several candidates) A providing a service foo and a class B providing a service bar both developped independently of each other (apart from common superclasses) define a common subclass C providing both services A providing a service foo and a class B providing a service bar both developped independently of each other (apart from common superclasses) define a common subclass C providing both services Motivation for multiple inheritance (2/2) In static typing There is no language without full multiple inheritance (C++, Eiffel), or mixins (Scala), or at least multiple subtyping (Java, C , Ada 2005) between two global properties with the same name between two local properties of the same global property plus the method combination case conflict between two global properties with the same name Solution: Fully Qualified Names short names are used in most situations names qualified with the introduction class used when a conflict occurs a global property is introduced by a single class static typing required local properties of the same global property none more specific than the other Solution redefinition in the class where the conflict occurs a Human must behave like a Mortal Redefinition is non-monotonic redefining a method yields non-monotonicity Method combination = Call to super a way to recover monotonicity a Human behaves like a Mortal, with extra behaviour Monotonicity vs redefinition Aristotelian logic is monotonic a Human must behave like a Mortal Redefinition is non-monotonic redefining a method yields non-monotonicity Method combination = Call to super a way to recover monotonicity a Human behaves like a Mortal, with extra behaviour no problem with local property conflicts, nor method combination except with default methods in Java 8 ad hoc solution for global property conflicts in C no solution for global property conflicts in Java no problem with local property conflicts, nor method combination except with default methods in Java 8 ad hoc solution for global property conflicts in C no solution for global property conflicts in Java the answer, what was the question? just add unnecessary asymmetry between classes and traits right solution for global attribute conflicts no solution for global method conflicts two distinct attributes for a single accessor! method combination with static calls and repeated inheritance linearization used for constructor/destructor combination but not C3 C++ non-virtual inheritance repeated inheritance for non-conflicting global attributes an abomination right solution for global attribute conflicts no solution for global method conflicts two distinct attributes for a single accessor! method combination with static calls and repeated inheritance linearization used for constructor/destructor combination but not C3 C++ non-virtual inheritance repeated inheritance for non-conflicting global attributes an abomination for global property conflicts, with renaming method combination with static calls and repeated inheritance With dynamic typing (CLOS, Python) no solution for global property conflicts linearization-based method combination C3 default linearization only in Python possibility to define metaclasses using C3 in CLOS classes and traits the same for methods, attributes, virtual types, type parameters metamodeling semantics with fully qualified names for global properties without any repetition local property conflicts solved by redefinition method combination using the C3 linearization declare properties and create instances types serve as annotations in the code allow the compiler to ensure the code is type safe Nominal vs structural types a nominal type is a symbol with explicit subtyping a structural type is a record of named signatures, with implicit subtyping When parameter types are invariant, there is room for static overloading Principle a name denoting different entities in a common context disambiguated with static types originates in pre-object languages like PL/1 and C Static overloading (1/3) When parameter types are invariant, there is room for static overloading Principle a name denoting different entities in a common context disambiguated with static types originates in pre-object languages like PL/1 and C Mal nommer les choses, c'est ajouter au malheur du monde Misnaming things adds to the world's misfortunes (Albert Camus) Albert Camus a French writer and philosopher (1913-60) Peyo a Belgian author of comic strips (1928-92) creator of the Schtroumpfs Schtroumpfs small characters whose language has a single noun and verb: "schtroumpf" Mal nommer les choses, c'est ajouter au malheur du monde Misnaming things adds to the world's misfortunes (Albert Camus) Albert Camus a French writer and philosopher (1913-60) Peyo a Belgian author of comic strips (1928-92) creator of the Schtroumpfs Schtroumpfs small characters whose language has a single noun and verb: "schtroumpf" Misnaming things adds to the world's misfortunes in the context of a picture, even small children can understand! to the schtroumpf's schtroumpfs in the context of a picture, even small children can understand! object-oriented languages are now generic (Eiffel, C++, Java, C , ...) generic languages (Ada) are now object-oriented object-oriented languages are now generic (Eiffel, C++, Java, C , ...) generic languages (Ada) are now object-oriented heterogeneous pure textual substitution (C++) no recursive types + code explosion homogeneous type erasure and code sharing (Java 1.5, Scala) limited expressivity, unsafe casts, inefficient boxing mixed code shared or specialized, with runtime types (C ) best tradeoff expressivity-efficiency-safety Stack<? extends Animal> s = new Stack<Cat>(); Animal a = s.pop(); // OK s.push(a); // KO interface restricted to methods where the type parameter is not in a contravariant position useful for exporting "almost read-only" collections Stack<? extends Animal> s = new Stack<Cat>(); Animal a = s.pop(); // OK s.push(a); // KO interface restricted to methods where the type parameter is not in a contravariant position useful for exporting "almost read-only" collections Stack<? super Cat> s = new Stack<Animal>(); Animal a = s.pop(); // KO Object o = s.pop(); // OK s.push(new Cat()); // OK interface restricted to methods where the type parameter is not in a covariant position or is replaced by the parameter bound counter-intuitive and rarely used, apart from Comparable Stack<? super Cat> s = new Stack<Animal>(); Animal a = s.pop(); // KO Object o = s.pop(); // OK s.push(new Cat()); // OK interface restricted to methods where the type parameter is not in a covariant position or is replaced by the parameter bound counter-intuitive and rarely used, apart from Comparable class ImmutableContainer<+ T> { T get() ;} class Container<T> inherit ImmutableContainer<T> { put(T) ;} with + the type parameter is covariant and cannot be used in a contravariant position useful for exporting "actual read-only" collections class ImmutableContainer<+ T> { T get() ;} class Container<T> inherit ImmutableContainer<T> { put(T) ;} with -the type parameter is contravariant and cannot be used in a covariant position counter-intuitive and rarely used

R. Ducournau (LIRMM)Ideal Classes and Types 沈阳市, 2016