Π-CoLab

Privacy, Inference,
and Communications Laboratory






Project 2: A Framework for Web Privacy

Internet users reasonably expect their online identities and web browsing activities to remain private. Unfortunately, this is far from the case in practice; in reality, users are constantly tracked on the internet.  As web tracking technologies become more sophisticated and pervasive, there is an urgent need  to understand and quantify web users' privacy risks. In this project we address this problem by considering online fingerprinting attacks as well as offline social network de-anonymization (graph matching attacks).

Offline Social Network De-anonymization Attacks

In this project, we investigate the matchability of pairs of  correlated graphs and propose graph matching algorithms based on the concept of typicality from information theory. Graph matching algorithms can be used to exploit the publicly available information over several social networks to match their corresponding graphs and reveal private information.  Given a pair of stochastically correlated graphs, the objective is to deduce the one-to-one correspondence between their vertices which is consistent with the underlying statistical correlation. Previous approaches to the problem often leverage the graph structure for reliable matching. In contrast, the approach proposed in this work considers the adjacency matrices of the two graphs and uses concentration of measure theorems to determine whether the two graphs can be matched reliably. We apply the framework both to seeded and seedless matching scenarios under various random graph models. Our main result shows that reliable matching is contingent upon the value of the mutual information between the variables corresponding to the edge probabilities of the two graphs being greater than a critical value.


Featured Publications:
  1. F. Shirani Chaharsooghi, S. Garg, E. Erkip, "A concentration of measure approach to correlated graph matching", IEEE Journal on Selected Areas in Information Theory 2.1 (2021): 338-351.
  2. F. Shirani Chaharsooghi, S. Garg, E. Erkip, "Seeded graph matching: efficient algorithms and theoretical guarantees", 51st Asilomar Conference on Signals, Systems, and Computers, pp. 253-257. IEEE, 2017.

Online Fingerprinting Attacks

In this project, we develop a new mathematical formulation for the problem of de-anonymizing internet users by actively querying their membership in social network groups. In social network de-anonymization, it is assumed that an anonymous victim visits an attacker’s website, and the attacker uses the victim’s browser history to query her social media activity to find the victim's real-world identity. The objective is to use the minimum number of queries possible to de-anonymize the user. In our stochastic model of the problem, the attacker has partial prior knowledge of the group membership graph and receives noisy responses to its queries.  A new information theoretic framework for the design and analysis of de-anonymization algorithms is developed and several new attack strategies are proposed which operate under different de-anonymization scenarios. It is shown that the new strategies achieve optimal performance under certain statistical models. 

Featured Publications:

  1. M. Shariatnasab, F. Shirani, E. Erkip,   "Fundamental privacy limits in bipartite networks under active attacks" , IEEE Journal on Selected Areas in Communications 40.3 (2022): 940-954.
  2. F. Shirani Chaharsooghi, S. Garg, E. Erkip,   "An information theoretic framework for active de-anonymization in social networks based on group memberships" , 55th Annual Allerton Conference on Communication, Control, and Computing, pp. 470-477. IEEE, 2017.
  3. F. Shirani Chaharsooghi, S. Garg, E. Erkip, "Optimal active social network de-anonymization using information thresholds" , IEEE International Symposium on Information Theory (ISIT), pp. 1445-1449. IEEE 2018.