  This paper addresses active re-identification attacks in the context of
privacy-preserving social graph publication. Active attacks are those where the
adversary can leverage fake accounts, a.k.a. sybil nodes, to enforce structural
patterns that can be used to re-identify their victims on anonymised graphs. In
this paper we present a new probabilistic interpretation of this type of
attacks. Unlike previous privacy properties, which model the protection from
active adversaries as the task of making victim nodes indistinguishable in
terms of their fingerprints with respect to all potential attackers, our new
formulation introduces a more complete view, where the attack is countered by
jointly preventing the attacker from retrieving the set of sybil nodes, and
from using these sybil nodes for re-identifying the victims. Under the new
formulation, we show that the privacy property $k$-symmetry, introduced in the
context of passive attacks, provides a sufficient condition for the protection
against active re-identification attacks leveraging an arbitrary number of
sybil nodes. Moreover, we show that the algorithm K-Match, originally devised
for efficiently enforcing the related notion of $k$-automorphism, also
guarantees $k$-symmetry. Empirical results on several collections of synthetic
graphs corroborate that our approach allows, for the first time, to publish
anonymised social graphs (with formal privacy guarantees) that effectively
resist the strongest active re-identification attack reported in the
literature, even when it leverages a large number of sybil nodes.
