Attribute Couplet Attacks and Privacy Preservation in Social Networks

Abstract-The emerging of social networks, e.g., Facebook, Twitter, Instagram has eventually changed the way in which we live. Social networks are acquiring and storing a significant amount of profile information and daily activities of over billions of active users. The datasets, drawn from the social networks, are becoming great sources for exploring and attracting huge interests from different research communities. However, publishing social network datasets have also raised serious security and privacy risks; it is highly likely that they will be targeted by the hackers due to their substantially commercial values. To deal with the problem of privacy leakage, a number of attack models and corresponding privacy preserving solutions have been proposed recently. A common approach is to anonymize the identities of the users when publishing the datasets while we argue that the remaining relationship is sufficient to identify an anonymized user. In this paper, we define a new type of attack as Attribute Couplet Attack. The attribute couplet attack facilitates the relationship of a couplet of anonymous nodes (i.e., a pair of users) and some limited background information to unveil the protected identities. To achieve privacy-preservation under attribute couplet attacks, we propose a new anonymity concept as k-couplet anonymity. A social network dataset satisfies the kcouplet anonymity if, for any pair of nodes, there exist at least the other k − 1 couplets sharing the same attributes. Then we design and implement two heuristic algorithms to promote the k-couplet anonymity. Furthermore, we design an approximate algorithm for multiple-attribute social networks to realize the k-couplet anonymity. The evaluation results on multiple datasets demonstrate that the privacy and utility of the social network datasets can be well preserved when incorporating the proposed k-couplet anonymity and the associate heuristic algorithms.