  In this paper, de-anonymizing internet users by actively querying their group
memberships in social networks is considered. In this problem, an anonymous
victim visits the attacker's website, and the attacker uses the victim's
browser history to query her social media activity for the purpose of
de-anonymization using the minimum number of queries. A stochastic model of the
problem is considered where the attacker has partial prior knowledge of the
group membership graph and receives noisy responses to its real-time queries.
The victim's identity is assumed to be chosen randomly based on a given
distribution which models the users' risk of visiting the malicious website. A
de-anonymization algorithm is proposed which operates based on information
thresholds and its performance both in the finite and asymptotically large
social network regimes is analyzed. Furthermore, a converse result is provided
which proves the optimality of the proposed attack strategy.
