Disclaimer: These notes are taken for the CS577 Data Privacy course offered by Dr. Erman Ayday in the 2021/2022 Fall Semester at Bilkent University.
There has been a rapid increase in the number of social network sites in the late 2010s. Spending time on Instagram, Snapchat, Facebook, LinkedIn or Twitter became a regular activity for people as they continue to share a lot of personal information on these sites willingly. Although social networking sites employ mechanisms to protect the privacy of their users, there is always the risk that an attacker can correlate data or abuse the structure of a social network to infer information about registered individuals [1]. While there are several ways to effectively track browsers on the Internet, these methods leave the user pseudonymous and the real-world identity of a user cannot be discovered in any known way. As a result, current tracking methods only provide information on which sites have been visited, but not who the user behind these visits actually is. On the other hand, network owners often share this information with advertising partners and other third parties for the sake of business. Some networks are even published for research purposes [2]. Thus, a user needs to have a certain degree of anonymity to preserve their privacy in these situations.
De-anonymization Attacks Using Browser History
In general, there are two assumptions about the attacker that tries to de-anonymize users: (i) the attacker can determine which web pages, from a given set, a specific user v has accessed within time τ (from third-party cookies, network latencies, or browser characteristics etc.), and (ii) the attacker has a way to learn about the members of groups for a given social network S.
1. Basic Attack
An attacker can use history stealing to probe for URLs that encode user information. In particular, the attacker can probe for a URL φ that contains an identifier of user v. When a link is found that contains this identifier for v, then the attacker can reasonably assume that the browser was used by v in the past to access the user-specific URL φ.
In practice, the attacker has to generate and check one URL for every user in the social network, and each potential victim’s browser would have to download all links and process them. Due to this issue, this attack is not very feasible.
2. Improved Attack
An improved attack leverages group membership information. By checking the browser history, the attacker can infer that v is a member of group g if s/he has recently accessed a page related tog. Being able to check more groups, the attacker could learn more about the group fingerprint of v.
One should note that the information that the attacker learns may not be entirely accurate. Hence, generating a candidate set, C that contains the union of all members, and applies a basic attack to each candidate in C is more robust than generating C that contains the only interaction of all members, even though the latter is faster
De-anonymization Attacks That Intersects Multiple Networks
The re-identification algorithm using an auxiliary graph and a target graph follows 2 steps [2].
The attacker identifies a small number of “seed” nodes that are present both in the anonymous target graph and the attacker’s auxiliary graph and maps them to each other.
The seed mapping is extended to new nodes using only the topology of the network, and the new mapping is fed back to the algorithm. The eventual result is a large mapping between subgraphs of the auxiliary and target networks which re-identifies all mapped nodes in the latter.
The success of the attack is measured with respect to a centrality measure. Note that such a
measure only gives a lower bound on privacy breach because privacy can be violated without complete deanonymization.
[1] G. Wondracek, T. Holz, E. Kirda, and C. Kruegel, “A practical attack to de-anonymize social network users,” in 2010 IEEE symposium on security and privacy, IEEE, 2010, pp. 223–238. [2] A. Narayanan and V. Shmatikov, “De-anonymizing social networks,” in 2009 30th IEEE symposium on security and privacy, IEEE, 2009, pp. 173–187.