Most users of online services have unique behavioral or usage patterns. These behavioral patterns can be used to identify and track users by using only the observed patterns in the behavior. We study the task of identifying users from statistics of their behavioral patterns. Specifically, we focus on the setting in which we are given histograms of users’ data collected in two different experiments. In the first dataset, we assume that the users’ identities are anonymized or hidden and in the second dataset we assume that their identities are known. We study the task of identifying the users in the first dataset by matching the histograms of their data with the histograms from the second dataset. In a recent work ,  the optimal algorithm for this user identification task was introduced. In this paper, we evaluate the effectiveness of this method on a wide range of datasets with up to 50, 000 users, and in a wide range of scenarios. Using datasets such as call data records, web browsing histories, and GPS trajectories, we demonstrate that a large fraction of users can be easily identified given only histograms of their data, and hence these histograms can act as users’ fingerprints. We also show that simultaneous identification of users achieves better performance compared to one-by-one user identification. Furthermore, we show that using the optimal method for identification does indeed give higher identification accuracies than heuristics-based approaches in such practical scenarios. The accuracies obtained under this optimal method can thus be used to quantify the maximum level of user identification that is possible in such settings. We show that the key factors affecting the accuracy of the optimal identification algorithm are the duration of the data collection, the number of users in the anonymized dataset, and the resolution of the dataset. We also analyze the effectiveness of k-anonymization in resisting user identification attacks on these datasets.
First, download the code and data files, uncompress them and copy/paste the content of the data files into the
generatingResultsFigures/ folder. Then, to generate the figures in the paper, simply open MATLAB and navigate to the
generatingResultsFigures/ folder (in the code files) and follow the instructions below.
In MATLAB, type
to reproduce Figures 8 and 9, respectively.
In MATLAB, type
to reproduce Figures 10 and 11, respectively.
To reproduce Figure 12(b), type
For Figure 12(c), run
In the code folder, there are other useful MATLAB functions which can be used
test1.m: Generates histograms based on iid generated data and tests histogram matching by using the four different metrics
calculateMatchAllMetrics.m: Gets as inputs two sets of histograms and computes the matching using the four different metrics
bipartite_matching.m: An algorithm for performing weighted bipartite matching
generatingResultsFigures\GSMS_T2.m: performs microaggregation, where the l2-norm has been replaced by the l1-norm
Copyright (c) 2014, Farid M. Naini, Jayakrishnan Unnikrishnan, Patrick Thiran and Martin Vetterli