  In this paper, a new mathematical formulation for the problem of
de-anonymizing social network users by actively querying their membership in
social network groups is introduced. In this formulation, the attacker has
access to a noisy observation of the group membership of each user in the
social network. When an unidentified victim visits a malicious website, the
attacker uses browser history sniffing to make queries regarding the victim's
social media activity. Particularly, it can make polar queries regarding the
victim's group memberships and the victim's identity. The attacker receives
noisy responses to her queries. The goal is to de-anonymize the victim with the
minimum number of queries. Starting with a rigorous mathematical model for this
active de-anonymization problem, an upper bound on the attacker's expected
query cost is derived, and new attack algorithms are proposed which achieve
this bound. These algorithms vary in computational cost and performance. The
results suggest that prior heuristic approaches to this problem provide
sub-optimal solutions.
