  In an undirected social graph, a friendship link involves two users and the
friendship is visible in both the users' friend lists. Such a dual visibility
of the friendship may raise privacy threats. This is because both users can
separately control the visibility of a friendship link to other users and their
privacy policies for the link may not be consistent. Even if one of them
conceals the link from a third user, the third user may find such a friendship
link from another user's friend list. In addition, as most users allow their
friends to see their friend lists in most social network systems, an adversary
can exploit the inconsistent policies to launch privacy attacks to identify and
infer many of a targeted user's friends. In this paper, we propose, analyze and
evaluate such an attack which is called Friendship Identification and Inference
(FII) attack. In a FII attack scenario, we assume that an adversary can only
see his friend list and the friend lists of his friends who do not hide the
friend lists from him. Then, a FII attack contains two attack steps: 1) friend
identification and 2) friend inference. In the friend identification step, the
adversary tries to identify a target's friends based on his friend list and
those of his friends. In the friend inference step, the adversary attempts to
infer the target's friends by using the proposed random walk with restart
approach. We present experimental results using three real social network
datasets and show that FII attacks are generally efficient and effective when
adversaries and targets are friends or 2-distant neighbors. We also
comprehensively analyze the attack results in order to find what values of
parameters and network features could promote FII attacks. Currently, most
popular social network systems with an undirected friendship graph, such as
Facebook, LinkedIn and Foursquare, are susceptible to FII attacks.
