Source-linked AI summary
How Unique and Traceable are Usernames?
Daniele Perito, Claude Castelluccia, Mohamed Ali Kaafar, Pere Manils
TL;DR
The paper asks whether profiles on different services can be linked using usernames alone, despite additional profile information often being missing or unreliable. It develops username-uniqueness and linkage methods using language models and Markov-Chain techniques and evaluates them on real-service data. The authors report that digital identities can be tied together, and potentially to real identities, in many cases using ubiquitous usernames.
Problem
The paper addresses whether usernames alone can reveal when accounts on different online services belong to the same person, because associated profile information is often unreliable, heterogeneous, or unavailable.
Method
The authors estimate username uniqueness and cross-service linkage probabilities using language models, Markov Chain techniques, and username-pair probability comparisons.
Results
The authors show that digital identities can be tied together, and most likely to real identities in many cases, using ubiquitous usernames.
Takeaways & Limitations
Username-based profiling forms a class of techniques that can link and abuse public information across online social networks and web services.
Takeaways & Limitations
The validation ground truth comes from Google Profiles, whose users may be less privacy concerned, and the technique cannot trace intentionally unrelated usernames.
Abstract
from arXiv · showhide
Suppose you find the same username on different online services, what is the probability that these usernames refer to the same physical person? This work addresses what appears to be a fairly simple question, which has many implications for anonymity and privacy on the Internet. One possible way of estimating this probability would be to look at the public information associated to the two accounts and try to match them. However, for most services, these information are chosen by the users themselves and are often very heterogeneous, possibly false and difficult to collect. Furthermore, several websites do not disclose any additional public information about users apart from their usernames (e.g., discus- sion forums or Blog comments), nonetheless, they might contain sensitive information about users. This paper explores the possibility of linking users profiles only by looking at their usernames. The intuition is that the probability that two usernames refer to the same physical person strongly depends on the "entropy" of the username string itself. Our experiments, based on crawls of real web services, show that a significant portion of the users' profiles can be linked using their usernames. To the best of our knowledge, this is the first time that usernames are considered as a source of information when profiling users on the Internet.
1. INTRODUCTION
The paper studies linking online identities using usernames alone, motivated by privacy risks and the limitations of heterogeneous, missing, or misleading profile information. It develops username-based methods for estimating uniqueness and cross-service identity linkage, and provides a tool for assessing username traceability.
- Online profiling can combine identities across public profiles, sharpening user knowledge for targeted spam, social phishing, advertising, or employment screening.
- The paper proposes using usernames rather than social graphs to tie online identities across web services that publicly expose usernames.
- Profile-linking methods face incorrect, misleading, heterogeneous, or missing public information, while some services expose usernames without additional user data.
- Its model uses language models and Markov Chain techniques to estimate username uniqueness and the probability that usernames from different services refer to the same user.
- The authors acknowledge that intentionally unrelated usernames cannot be traced by the technique, while experiments indicate users often choose closely related usernames across services.
- An online tool measures username uniqueness and traceability to help users make decisions about anonymity and username choice.
2. RELATED WORK AND BACKGROUND
The paper situates username-based profiling within record linkage, social-network de-anonymization, browser fingerprinting, and information-theoretic background. It defines surprisal as a basis for measuring username uniqueness and distinguishes this task from conventional record linkage.
- Related work: Prior approaches retrieve information across social networks by exploiting API weaknesses, social-graph topology, or search-based comparisons of profile fields.
- Related work: Record linkage finds records referring to the same entity across databases when unique identifiers are unavailable.
- Related work: Unlike conventional record linkage, matching two usernames does not necessarily establish positive identification, creating distinct challenges for public online-profile linkage.
- Related work: Browser fingerprinting similarly uses distinctive features or entropy to support re-identification without long-lived identifiers such as cookies.
- Background: Information surprisal is I(x) = −log2(P(x)); rarer outcomes have higher surprisal and therefore more associated identifying information.
- Background: For a population of W users, a username uniquely identifies a user when I(P(u)) > log2(W), making surprisal the paper’s username-uniqueness measure.
3. THE DATASET
The study analyzes username lists from Google Profiles, eBay, an INRIA directory, Finnish forums, and MySpace. These datasets support model training, ground-truth validation, and characterization of username uniqueness and policy compatibility.
- The datasets include 3.5 million Google usernames, 6.5 million eBay usernames, about 16,000 INRIA usernames, and Finnish and MySpace username lists.
- The combined 10 million Google and eBay usernames train the Markov Chain model used for probability estimation.
- Google Profiles provide ground-truth linked accounts because users can optionally list accounts on other social networks and web services.
- 85% of users in the 10-million-username set choose alphanumerical-only usernames, which comply with the policies of all username services examined.
4. ESTIMATING USERNAME UNIQUENESS
The paper estimates username uniqueness by modeling username probabilities with Markov Chains and converting them into information surprisal. Experiments across multiple services find generally high and relatively stable surprisal, supporting usernames as identifying information.
- Measure: Information Surprisal quantifies username uniqueness in bits, but requires estimating each username’s probability P(u).The paper defines surprisal as −log2(P(u)).
- Probability estimation: Maximum Likelihood Estimation assigns observed usernames their empirical frequency and unseen usernames probability zero, making estimates coarse and unusable for unseen usernames.This limitation motivates a model that can assign probabilities to usernames absent from the training sample.
- Probability estimation: Markov Chains estimate username probabilities from character sequences, using conditional probabilities over preceding characters; the experiments use 5-grams trained on approximately 10 million usernames.Longer n-grams capture longer histories but have fewer samples per n-gram.
- Experiments: More than 35 bits of entropy characterize both eBay and Google username distributions, suggesting usernames are highly unique identifiers on average.The distributions overlap despite different username policies and interfaces.
- Experiments: Google usernames have higher Information Surprisal than eBay usernames, while similar distributions across services indicate relative stability of the measure.Google’s username suggestions derived from first and last names are offered as a possible explanation for its higher surprisal.
- Experiments: Across other datasets, surprisal results are similar; INRIA is highest, with almost 75% of usernames exceeding 40 bits of surprisal.The Finnish dataset supports stability across different languages, while the INRIA pattern is associated with first-and-last-name username policies.
- Experiments: At most 25% of usernames have information surprisal below 30 bits across the datasets, and in some cases the fraction is below 5%.These distributions indicate that most observed usernames carry substantial identifying information.
5. USERNAME COUPLES LINKAGE
The paper estimates whether different usernames belong to the same person by modeling username uniqueness and likely transformations between strings. Experiments show that linked usernames are typically more similar than non-linked ones, enabling high-precision linkage, while coverage and representativeness remain limited in some settings.
- Problem and model: Users may change usernames across services, so the paper models the probability that two different strings belong to the same person.The probability depends on information in the shared username content and how likely users are to transform one username into another.
- Empirical patterns: Linked username couples have mean Levenshtein distance 4.2, compared with 12 for non-linked couples.The linked and non-linked standard deviations are 2.2 and 3.1, respectively, indicating substantially closer strings among linked accounts.
- Methods: The paper combines Markov Chains with weighted Levenshtein distance and compares them with TF-IDF and baseline string metrics.The baseline comparison uses normalized Levenshtein Distance and Jaro distance.
- Results: The Markov-Chain method has the highest precision up to recall 0.7, while TF-IDF offers good precision at higher recalls.A recall of 0.71 corresponds to successfully linking 71% of matching username couples.
- Results: NLD and Jaro also perform well, partly because non-linked usernames have higher distances and string length may approximate surprisal.The paper reports that all tested methods achieve high precision for linking username couples belonging to the same users.
- Limitations and improvements: The ground truth came from Google Profiles, and the method was not tested on privacy-sensitive services such as dating and medical websites.The authors also note that exhaustive pairwise matching requires quadratic time, motivating clustering or hybrid approaches as possible improvements.
6. RELEVANT USERNAME STATISTICS
Users frequently construct usernames from their real names, often adding predictable digits, and most users maintain only a few distinct usernames.
- 70% of usernames contain at least one part of the user’s first or last name.30% concatenate both names without adding digits.
- More than 50% of usernames exactly match the tested combinations of names, initials, and digits.
- Users commonly add postfix numbers when their first-choice usernames are already in use or suggested by the service.
- 40% of cases add exactly two numbers and 20% add exactly four, patterns that may indicate birth years or dates.
- Most users have two or three different usernames, with a mean of 2.3 usernames per user.
7. DISCUSSION
The discussion frames username linkage as both a privacy threat and a practical tool, while noting computational costs and limits on preventing linkage.
- Linking usernames can tie digital identities, and likely real identities, across services in many cases.
- Advertisers could build online profiles with high accuracy and minimum effort without users’ consent.
- Matching profiles can enable highly targeted spam using information combined across services, including recent eBay transactions.
- Users can assess username uniqueness and linkability with the released web tool before deciding whether to change a pseudonym.
- Preventing linkage may require different usernames across services, but unlinkable choices can sacrifice some social-network features.
8. CONCLUSION
The paper introduces username-only profile linkage, combining uniqueness estimation with methods for linking different usernames. It reports high precision and frames the techniques as broadly applicable but potentially abusive.
- The paper estimates username uniqueness using language-model and Markov-Chain techniques to link profiles sharing usernames.
- The approach extends to profiles whose linked usernames differ by treating the task as record linkage.
- All tested methods achieve high precision when linking username pairs belonging to the same users.
- The resulting profiling techniques can link and potentially abuse public information on social networks and web services.
Username uniqueness from a probabilistic point of view
The paper estimates username uniqueness by modeling how many users in a population are expected to choose a given string, with uniqueness depending on both username likelihood and population size. The estimate adjusts when the username is already known to be taken.
- Puniq(u) is the probability that exactly one user has selected username u in a specified population.
- Username uniqueness increases as P(u) decreases but also depends on the size of the population being analyzed.
- An uncommon first name may be non-unique in a large population such as the US but unique in a smaller population such as a classroom.
- The expected number of users choosing string u is computed from P(u) for a given population W.
- When username u is known to be taken, n(u) changes to P(u) ∗(W −1) + 1 by accounting separately for the confirmed user.The added 1 represents the user known to have selected u, while W −1 represents the remaining population.
- The paper estimates username uniqueness by evaluating whether the user is unique within the reference set determined by n(u).