  In order to prevent the disclosure of privacy-sensitive data, such as names
and relations between users, social network graphs have to be anonymised before
publication. Naive anonymisation of social network graphs often consists in
deleting all identifying information of the users, while maintaining the
original graph structure. Various types of attacks on naively anonymised graphs
have been developed. Active attacks form a special type of such privacy
attacks, in which the adversary enrols a number of fake users, often called
sybils, to the social network, allowing the adversary to create unique
structural patterns later used to re-identify the sybil nodes and other users
after anonymisation. Several studies have shown that adding a small amount of
noise to the published graph already suffices to mitigate such active attacks.
Consequently, active attacks have been dubbed a negligible threat to
privacy-preserving social graph publication. In this paper, we argue that these
studies unveil shortcomings of specific attacks, rather than inherent problems
of active attacks as a general strategy. In order to support this claim, we
develop the notion of a robust active attack, which is an active attack that is
resilient to small perturbations of the social network graph. We formulate the
design of robust active attacks as an optimisation problem and we give
definitions of robustness for different stages of the active attack strategy.
Moreover, we introduce various heuristics to achieve these notions of
robustness and experimentally show that the new robust attacks are considerably
more resilient than the original ones, while remaining at the same level of
feasibility.
