Full Version - University of Pittsburgh

Exploiting Users' Inconsistent Preferences in Online
Social Networks to Discover Private Friendship Links
Lei Jin*, Hassan Takabi#, Xuelian Long*, James Joshi*
*School of Information Sciences
#Department
of Computer Science and Engineering
University of Pittsburgh
University of North Texas
{lej17, xul10, jjoshi}@pitt.edu
[email protected]
ABSTRACT
1. INTRODUCTION
In a social network system, a friendship relation between two users
is usually represented by an undirected link and it is visible in both
users' friend lists. Such a dual visibility of a friendship link may
raise privacy threats. This is because both the users of a friendship
link can separately control its visibility to other users and their
preferences of sharing such a friendship link may not be consistent.
Even if one of them conceals the friendship link from a third user,
that third user may find the link through the other user's friend list.
In addition, as most social network users allow their friends to see
their friend lists, an adversary can exploit these inconsistent
policies caused by users' conflicting preferences to identify and
infer many of a targeted user's friends and even reconstruct the
topology of an entire social network. In this paper, we propose,
characterize and evaluate such an attack referred as the Friendship
Identification and Inference (FII) attack. In an FII attack scenario,
an adversary first accumulates the initial attack relevant
information based on the friend lists visible to him in a social
network. Then, he utilizes this information to identify and infer a
target's friends using a random walk based approach. We formally
define the attack and present the attack steps, the attack algorithm
and various attack schemes. Our experimental results using three
real social network datasets show that FII attacks are effective in
inferring private friendship links of a target and predicting the
topology of the social network. Currently, most popular social
network systems, such as Facebook, LinkedIn and Foursquare, are
susceptible to FII attacks.
In social network systems (SNSs), such as Facebook and LinkedIn,
friendship links are usually undirected. A friendship link involves
two users and the relationship is visible in both users' friend lists.
Both users can separately control the visibility of their friend lists
to other users, and hence, a privacy policy conflict may arise in
terms of users' inconsistent preferences. Such an inconsistency of
the policies could cause the violation of a user's privacy settings. In
an SNS, such as Facebook, a friendship between users A and C is
not visible to another user B only when both A and C do not allow
B to view their friend lists. When only A (C) disallows B to see the
link, B can find that A (C) is in C's (A's) friend list if C (A) allows
B to view his friend list. Since the friendship graph is undirected, B
can now conclude that A and C are friends. In this case, A's (C's)
privacy policy for B is violated.
Categories and Subject Descriptors
K.4.1 [Computer and Society]: Public Policy Issues – privacy
General Terms
Experimentation, Security
Keywords
Privacy; Social Networks; Friendship Attack
Permission to make digital or hard copies of all or part of this work for personal
or classroom use is granted without fee provided that copies are not made or
distributed for profit or commercial advantage and that copies bear this notice and
the full citation on the first page. Copyrights for components of this work owned
by others than ACM must be honored. Abstracting with credit is permitted. To
copy otherwise, or republish, to post on servers or to redistribute to lists, requires
prior specific permission and/or a fee. Request permissions from
[email protected].
WPES '14, November 3, 2014, Scottsdale, Arizona, USA.
Copyright © 2014 ACM 978-1-4503-2948-7/14/11…$15.00.
http://dx.doi.org/10.1145/2665943.2665956
Identified Link in an FII Attack
Visible Link
Inferred Link in an FII Attack
I
F
E
A
T
D
C
A
T
C
D
B
G
II
E
B
Figure 1. Examples of the FII attack
Most users in Facebook, LinkedIn and Foursquare allow their
friends to see their friend lists since it is the default policy and users
tend not to change the default privacy policies [30, 31]. An
adversary can first target a friend or 2-distant neighbor who does
not allow the adversary to see his friends. He can then exploit any
inconsistency in policies related to the visibility of the friend lists
to identify and infer many friends of the targeted user. For example,
as shown in Figure 1.I, let user B be the adversary and user T be his
target whose privacy settings do not allow B to see his friend list.
Users A, D and E are B's friends and they allow B to view their
friend lists. A, C and D are actually T's friends but initially B is not
supposed to know that. However, by checking A's and D's friend
lists, B can directly identify that A and D are T's friends. In addition,
using the proposed random walk based approach (introduced in
Section 2.4) on this social graph, B can infer that C has a high
probability of being a friend of T. Now, all of T's friends are
identified and inferred by B.
in Section 4 and conclude the paper with a discussion of future
work in Section 5.
In an SNS, the friend lists of some users are public. An adversary
can also target one user from these friend lists and then identify and
infer friends of the targeted user. Note that the targeted user is not
limited to be a friend or a 2-distant neighbor of the adversary in this
attack scenario. For example, in Figure 1.II, let user B be the
adversary and user T be his target whose privacy settings do not
allow B to see his friend list. Users A, C, D and E are friends of T
but B is initially not supposed to know that. The friend lists of A
and C are public and T is included in both A's and C's friend lists.
Then, B can directly see that A and C are friends of T from A's and
C's public friend lists. Using the proposed random walk based
approach, B can also infer that D and E are also highly possible to
be T's friends.
2. FRIENDSHIP IDENTIFICATION &
INFERENCE ATTACK
A user's friend list in an SNS is usually a valuable and sensitive
piece of information for the user [1-4]. For instance, Facebook's
move to suspend Google's Friend Connect program's access to
Facebook's social graph in 2008 was motivated by the perceived
importance of ensuring the privacy of friendship links [1]. In
LinkedIn, when a user connects with several well-known
professionals, it may help him in his search for jobs. At the same
time, the exposure of a user's friend list may also play against his
opportunities, for instance, if it includes an individual with a bad
reputation. In addition, if an adversary finds a user's friend list, he
may leverage it to launch further, more dangerous privacy attacks.
For example, the adversary may infer the user's private attributes in
his profile based on the public information of his friends [2, 5, 6];
the adversary can also successfully launch a profile cloning or
identity clone attack on a targeted user whose friend list is exposed
[7, 8].
In this paper, we propose a Friendship Identification and Inference
(FII) attack that aims to identify and infer a target's friends in an
SNS. In an FII attack, an adversary first constructs his initial attack
knowledge based on the friend lists visible to him in a social graph.
Based on this, his goal is to identify and infer a target's friends using
our proposed random walk with restart approach; this approach has
been shown to be probably the most effective approach for
predicting links in social networks [27]. Here, we assume that an
adversary uses it, as part of an FII attack, to infer as many private
friendship relationships of a target as possible based on the initial
knowledge he has. We demonstrate the effectiveness of FII attacks
on three different real social network datasets using various
measurements. The contributions of this paper can be summarized
as follows:
 We first define an FII attack that aims to identify and infer a
target's friends in SNSs and then present the detailed attack
steps, the attack algorithm and various attack schemes which
can make FII attacks more successful.
 Our experimental results show that FII attacks are effective in
inferring private friendship links of a target and predicting the
topology of the friendship network. We also evaluate the
relationships between social network features and the attack
results and discuss the potential defense solutions against such
FII attacks.
The remainder of the paper is organized as follows. We propose the
FII attack, its associated algorithm and various attack schemes in
Section 2 and present simulations of the FII attacks using three real
social network datasets in Section 3. We present the related work
In this section, we formalize the Friendship Identification and
Inference (FII) attack and introduce the attack steps, the
corresponding attack algorithm and various attack schemes.
2.1 Basic Definitions in SNSs
An SNS is generally modeled as a graph G(V, E), where V
represents a set of users and E={(x, y) | x, y ∈V} represents a set of
friendship links among users. In a social graph, such as Facebook
and LinkedIn, the friend link is usually undirected. An edge e = (x,
y) is added to E when a friend request from x to y or from y to x is
accepted.
Adjacency Matrix. A social graph G can be represented by an
adjacency matrix An×n where n = |V|. For each aij ∈ A, aij = 1 if there
is an edge e = (i, j) ∈ E; otherwise aij = 0. For each user i ∈V, the
user set F(i) ={ j | j ∈ V, aij = 1} is the friend list of i. Note that in a
social graph, when aij = 1, then aji = 1, i.e., j ∈ F(i) and i ∈ F(j). The
user set D2(i) = { j | ∃k, j ∈ V, aij = 0, aik = 1 and akj = 1} represents
the 2-distant neighbors of i. The 2-distant neighborhood
relationship in a social graph is also undirected.
Transition Matrix. Transition matrix is a matrix which describes
the probability of transitioning from one node to another node in a
social graph. It can be obtained based on the adjacency matrix. Let
Pn×n be a transition matrix, where pij represents the probability of
stepping on node j from node i and pij = aij / ∑j aij. The transition
matrix is an important variable in the random walk based approach
described in Section 2.4.
2.2 Adversary's Initial Attack Knowledge in
an FII Attack
In an SNS, such as Facebook, a user can see his friend list; most
users share their friend lists with their friends [30, 31]; few users
may hide their friend lists from specific friends; and some users
make their friend lists public. Hence, given an adversary b, we
categorize these types of friend lists that he can see:
 Type A: the friend lists of his friends who authorize b to view
them.
 Type B: the friend lists of users whose friend lists are public.
Note that these users are not friends of b.
Hence, b's friend list, the friend lists in Type A and those in Type
B form a sub graph which is an adversary's initial attack knowledge
K(b) for an FII attack. K(b) = (Vkb, Ekb) where Vkb is a set of all users
in K(b) and Ekb is a set of all edges in K(b).
For example, in Figure 2, there are two connected components of a
social graph. Let user B be the adversary. In the left part, we can
see that users A and C are B's friends. Assume that A allows B to
see his friend list while C hides his friend list from B. B does not
know that the edge (E, F) exists as B is not a friend of user E and E
does not allow B to see his friend list. B does not know that the edge
(C, D) exists since C conceals his friend list from B. Note that B
can identify the edge (B, C) = (C, B) from his friend list. B can also
know edges (A, B), (A, E) and (A, D) from A's friend list. In the right
part, assume that B cannot find a path to the sub graph composed
of G, H, I and J in the social graph. Assume that the friend lists of
users G and I are public and those of H and J are only visible to
their friends. From these public friend lists, B can know edges (G,
H), (G, J), (H, I) and (I, J). Hence, VkB ={A, B, C, D, E, G, H, I, J},
EkB = {(A, B), (A, E), (A, D), (B, C), (G, H), (G, J), (H, I), (I, J)} in
this case.
The edge initially visible to B
E
F
A
B
D
C
The edge initially invisible to B
G
H
J
I
Figure 2. Adversary B's initial attack knowledge
Assume there are m distinct nodes in Vkb for an adversary b. As
mentioned in the previous subsection, we can use the adjacency
matrix Am×m (b) and the transition matrix Pm×m (b) to represent K(b).
2.3 Friendship Identification and Inference
(FII) Attack
2.3.1 Definition
We present the definition of an FII attack as follows:
DEFINITION 1: Given a social graph G(V, E), an adversary b ∈V
and a target t ∈V,
Assumption on Target t's Privacy Setting: t defines a policy that
does not authorize b to see F(t);
Assumptions on Adversary's Initial Knowledge:
A1: b's initial attack knowledge K(b) = (Vkb, Ekb) is constructed
based on friend lists visible to him;
A2: t is included in Vkb.
Privacy Attack: We say that t is a victim (compromised1 node) of
an FII attack launched by b if b can identify and correctly infer at
least e friends of t's friends in Fb(t) based on the proposed random
walk based link predictions on K(b).
In the definition, Fb(t) represents a set of t's friends identified and
inferred by b through the FII attack and each user in Fb(t) is
regarded as t's friend by b. Note that some users in Fb(t) may not be
actual friends of t. Parameter e is a threshold set to distinguish the
point at which privacy violation becomes a significant concern (a
successful attack).
Note that in an FII attack, we assume that additional actions, such
as mutual friend based queries, are not needed to extend K(b)
defined above. We note that b may be even more successful in
carrying out the FII attack using some additional features and the
related attack schemes are discussed in Section 2.5.
Also note that an FII attack can also be used to identify and infer
the absence of friendship links between t and other users. The
exposure of absence of friendship links (potential friends) between
t and other users can cause various problems for t. For example, in
an identity clone attack [8], an adversary can connect with the
potential friends of a targeted user before the targeted user actually
does that. Such an action will make it difficult for the targeted user
to become friends with the potential friends. However, in this paper,
we only focus on identifying and inferring the existing friends of a
targeted user.
2.3.2 Targets
In an FII attack, a target t can be considered as one of these three
types based on the relationship with an adversary b: 1) a friend; 2)
a 2-distant neighbor; 3) other users who are more than 2-distant
away from b in a social graph.
Note that a target t should be included in Vkb according to one of
the assumptions from an adversary b's initial knowledge. t can be
any of b's friends since t is included in b's friend list and it is
included in Vkb. When t is a 2-distant neighbor of b, 1) b should be
able to see at least one friend list of his friend who is friend with
the 2-distant neighbor; or 2) there is at least one public friend list
that contains t. In these two cases, t can also be included in Vkb.
When t is more than 2-distant away from b in a social graph, b has
to search the public friend lists within the SNS to see if b is included
in one of them.
To discover users' public friend lists in a social graph, an adversary
1) can utilize the public search feature built in an SNS to discover
the users whose friend lists are public; and 2) can discover the
groups where the members are publicly available and then to check
if some members' friend lists are public [4].
2.3.3 Property
Below we propose and prove a key property related to the FII attack
based on the following definitions.
DEFINITION 2: Given a social graph G(V, E), an adversary b ∈V,
a target t ∈V, K(b) = (Vkb, Ekb) and t's friend list F(t), we define a
user set Ib(t) = Vkb ∩ F(t).
DEFINITION 3: Given a social graph G(V, E), an adversary b ∈V,
a target t ∈V and Fb(t) which is generated by b from an FII attack,
we define a user set FCb(t) which represents correctly identified and
inferred friends of t. FC b(t) = Fb(t) ∩ F(t).
Theorem: When b can compromise t in an FII attack, FCb(t) ⊆ Ib(t).
Proof: Since Fb(t) ⊆ Vkb according to the definition of the FII attack,
FC b(t) = Fb(t) ∩ F(t) ⊆ Vkb ∩ F(t) = I b(t).
From this theorem, we can know the specific set of t's friends who
can be exposed to b in an FII attacks. We can also see that the
maximum number of friends exposed to b is equal to | Ib(t) |.
K(b)
T’s Friend Network
E
User in Ib(t)
F
D
C
I
B
A
T
J
H
G
Figure 3. An example of the exposed friends to an adversary
1
In this paper, when we say b compromises t in an FII attack, it
means that b can successfully identify and/or infer t's friends
during the attack.
For example, in Figure 3, let user B be the adversary and user T be
his target. We can see that only users A, C and D can be exposed to
B in an FII attack. User I and J will not be exposed since they are
not included in VkB.
tends to be higher. This is because the value of β ∑j xl (j) ×pji is
higher (j represents the number of 2-distant paths between t and i).
Additionally, since i is closer to t (2-distant away), the part of (1–
β) X0 will also make the Xl+1(i) be a higher value.
2.4 Attack Algorithm & Schemes
2.4.2 Attack Steps & Algorithm
2.4.1 Random Walk & Attack Modeling
Intuitively, the probability of a user A being a friend of another user
C is related to the following conditions [14]:
 Condition 1: A's degree (number of friends);
 Condition 2: the network distance between A and C. When A is
close to C in a social graph, it is more likely for them to be
friends.
 Condition 3: number of the different paths between A and C.
For example, in Figure 1.I, there are two different shortest paths
(the length is 2) between users T and C and hence it is highly likely
for them to be friends in this case. User F is a 4-distant neighbor of
T in the social graph and the probability of the friendship between
them is low.
A simple random walk is a mathematical formalization of a path
that consists of a succession of random steps. Assume there is a
surfer walking in a network and let xl(i) be the probability that the
surfer is at node i at time l. xl+1(i) is probability that the surfer is at
node i at time l+1. Xl+1(i) = ∑j (Probability of being at node j)×
Probability of walking from j to i = ∑j xl (j) ×pji where pji is an
element of the transition matrix for the network (see Section 2.1).
Let Xl = (xl(i)) be a vector that represents the probabilities of the
surfer being at any node in the network at time l. Hence, we have
Xl+1 = XlP = Xl-1PP = … =X0 Pl where P represents the transition
matrix for the network and X0 is a predefined vector. When |Xl+1 –
XlP| < ɛ, we say that the probability of the surfer being at any node
i is stable for a long period of time.
We model an FII attack as a random walk as follows:
 An adversary's initial attack knowledge K(b) is modeled as the
network of the random walk.
 The probability of the surfer being at any node i in the random
walk can be regarded as the probability of the friendship
between the surfer and node i in an FII attack.
 In an FII attack, a target t is the surfer and Xl+1 is the probability
indicating whether there is a friendship link between t and other
users when |Xl+1 – XlP| < ɛ. When the probability of the
friendship between t and a user i is higher than that for other
users, i is more likely to be friends with t.
Random walk based approaches have been proved to be effective
for predicting friend and users' trajectory in SNSs [12-15].
However, the simple random walk mentioned above is not
appropriate for an FII attack. This is because the probability of the
friendship between t and any user i is only related to the number of
i's friends in the simple random work (Condition 1) [14]. Further,
the related conditions 2 and 3 are also overlooked.
By considering all the conditions, we adopt the random walk with
restart approach [13, 28]. In such an approach, a node follows the
simple random walk with the probability of β but it jumps back to
the originator (it is a target t in an FII attack) with probability 1– β.
That is Xl+1(i) = β ∑j xl (j) ×pji + (1– β) X0. From this equation, we
can see that the probability of t and a user i being friends tends to
be higher when i is closer to t. In addition, when there are more
paths between t and i, the probability of t and i being friends also
In an FII attack, there are three steps: collection of adversary's
initial attack knowledge, friend identification and friend inference.
The adversary b's initial attack knowledge K(b) is constructed
based on users' privacy settings for their friend lists. When a user is
b's friend, b can find him from his friend list and check whether his
friend list is visible. When a user is b's 2-distant neighbor, b may
find the user from one of friend lists of his friends and then check
whether the user's friend list is visible. For a user who is neither b's
friend nor 2-distant neighbor, b may find the user using the
approaches mentioned in Section 2.3.2 and then check whether the
user's friend list is available.
Note that when b's initial attack knowledge contains several
separated sub-graphs, we only consider the sub-graph that includes
the target. For example, in Figure 2, there are two separate subgraphs. Sub-graph 1 consists of users A, B, C, D, E and F while subgraph 2 consists of users G, H, I and J. There is no edge connecting
these two sub-graphs. Assume B is the adversary and J is the target
in an FII attack. In this scenario, b's initial attack knowledge
includes only sub-graph 2. Such a setting can make sure that the
random walk will be stable for a long period of time and it can also
help in improving the attack result.
Additionally, an adversary needs to set a parameter λ, which is used
to determine the total number of users identified and inferred as t's
friends (the size of Fb(t)) before launching an FII attack.
The purpose of the friend identification step is to identify a target's
friends based on the initial attack knowledge that an adversary has.
In this step, an adversary b is able to check whether a target t exists
in the edges in Ekb of K(b). When (i, t) or (t, i)∈ Ekb, i is t's friend.
In the friend inference step, an adversary b adopts the random walk
with restart approach to infer friends of a target t based on K(b). In
particular, an adversary b has to complete the following steps to
infer t's friends:
1. Compute the adjacency matrix A and the transition matrix P
based on K(b).
2. Get FIDb(t) which represents the friends identified in the friend
identification step.
3. Define the initial vector V0 =(vi)m, where m is the number of
distinct nodes in A. For each vi, when i is the index of t in A, vi
= 1; otherwise, vi = 0.
4. Define a parameter β ∈ (0, 1). Define Vl as a distribution for t
after l times walking. Vl = β ×P ×Vl-1 + (1 − β) ×V0. Set second
parameter ɛ which represents a very small value, e.g., 10-6. Keep
walking till |Vl – Vl-1 | < ɛ. In this case, we say Vl is a stationary
distribution and it reflects the probabilities of the friendship link
between t and any other nodes in A.
5. Choose (λ – |FIDb(t)|) distinct nodes from A based on the result
of Vl. These nodes have the higher probabilities of being friends
with t than for those of the remaining nodes. However, the
selected nodes should not be already included in FIDb(t) (note
that t is excluded). These chosen nodes are inferred friends of t
and we add them into FINb(t).
6. Finally, Fb(t) = FIDb(t) ∪ FINb(t).
The attack algorithm used for an FII attack is shown below.
Input: an adversary b, a target t, parameters λ, β and ɛ, users'
privacy settings PS in a social graph
Output: the identified and inferred friend set Fb(t)
1. Fb(t) = ∅
2. K(b) = ConstructAdversaryInitialKnowledge(PS)
3. A(b) = convertToAdjacencyMatrix(K(b))
4. P(b) = convertTransitionMatrix(K(b))
5. m = ncol(A(b)) // number of distinct nodes in A(b)
6. i = indexOf(A(b), t)
7. // identify friends of t from A(b)
8. FIDb(t) = getNodeFromIndex(A(b), j)
9. // infer additional friends of t
10. // using the random walk with restart
11. if FIDb(t) ≠ ∅
12. V0 = setInitialVector (i, m)
13. l=1
14. Vl= a × P(b) ×Vl-1 + (1– a) ×V0
15. while |Vl – Vl-1 | ≧ ɛ
16.
l++
17.
Vl= a × P(b) ×Vl-1 + (1– a) × V0
18. end while
19. // rank the probability from high to low
20. rankedProb = rank(Vl)
21. k = λ – |FIDb(t)|
22. FINb(t) = getTopProbabilityUsers(rankedProb, k)
23. Fb(t) = FIDb(t) ∪ FINb(t)
24. end if
2.4.3 Attack Schemes
In this section, we introduce three attack schemes of FII attacks
where an adversary has one or more attacker nodes and focuses on
one or more targets, respectively.
One attacker node and one target. We introduce three basic
attack schemes using one attacker node here:
 Attack Scheme 1: It is the most basic attack scheme that is the
same as the attack algorithm mentioned in Section 2.4.2. In this
scheme, an adversary chooses (λ – |FIDb(t)|) distinct users as
friends of a target once (refer to the attack step 5 and line 22 in
the attack algorithm).
 Attack Scheme 2: In this attack scheme, in the attack step 5, an
adversary b chooses only one user who has the highest
probability of being friends with a target t in one attack. Then,
b assumes that the identified friendship link is correct and adds
the link into Ekb of K(b). After that, b launches the attack again
and chooses another user who has the highest probability of
being friends with t and repeats this process until (λ – |FIDb(t)|)
users are chosen. We can see that b's initial attack knowledge is
expanded gradually in this attack scheme.
 Attack Scheme 3: In this attack scheme, besides a target t, there
are also several users who hide their friend lists from an
adversary b. b first tries to expand edges in K(b) by launching
FII attacks on these users before launching the attack on t. For
example, in Figure 2, let user B be the adversary and user C be
the target. B can first try to attack user D and E who do not allow
B to view their friend lists. Then, B adds the attack results
(identified and inferred friendship links of D and E) to K(B).
After that, B starts to launch the attack on C. In addition, when
an adversary is attacking multiple other users to expand his
initial attack knowledge, he can first target the user who may be
the most vulnerable to the attack. For example, a user, who is
closer to the adversary and has more paths to the adversary is
more vulnerable to the attack.
We expect that the attack schemes 2 and 3 will be able to produce
better results on a specific target. We will demonstrate these attack
schemes and compare the attack results in Section 3.
Multiple attacker nodes and one target. It is possible that there
are multiple adversaries or an adversary can control multiple
accounts in an SNS. These accounts can be used to conduct an FII
attack on the same target. In this case, we believe more friends of
the target will be identified and correctly inferred as the adversary
can gain more knowledge related to the target. To launch the attack
using multiple accounts, the adversary can first combine the initial
attack knowledge from each attacker node to form a network that
potentially includes more users related to the target. Then, the
adversary can choose any of the basic attack schemes mentioned in
the previous paragraphs to launch an FII attack on the target using
the combined network. We will demonstrate such an attack scheme
and compare its performance to those of the basic attack schemes
(proposed in previous paragraph) in Section 3.3.
Topology of the entire social network (multiple attacker nodes
and multiple targets). When an adversary is able to have enough
attacker nodes to launch the FII attacks, he may be able to infer the
topology of an entire social network. At first, based on the initial
attacker node, the adversary can first choose the target, who is the
most vulnerable for the FII attack, from a set of targets and then
launch an FII attack on the selected target. For example, the target
that has many more paths to the attacker node may be more
vulnerable for the FII attack. After more private friend links are
identified and inferred from the initial attack, similarly, the
adversary can continue to find such vulnerable targets and further
conduct more FII attacks on them. Finally, after enough FII attacks
have been conducted, the adversary may be able reconstruct the
topology of the entire social network using his identified and
inferred friendship links. We will show the attack results of such an
attack scheme in Section 3.4.
2.5 Discussion
The edge initially visible to B
The edge initially invisible to B
Inferred Friend of T from an
FII attack
Identified Friend of T from an
MFB attack
B
C
E
A
T
D
Figure 4. The FII attack vs. the MFB attack
FII and Mutual-friend Based (MFB) attacks. In a mutual-friend
based attack [4], an adversary can identify a target’s private friends
by conducting various queries of mutual friends. We find that an
FII attack and a mutual-friend based attack are complimentary and
they can be used together for more successful privacy attacks. For
example, in Figure 4, let user B be the adversary and user T be the
target who does not allow B to view his friend lists. B has three
friends A, C and D. Only C allows B to see his friend lists. By
launching an MFB attack, B immediately knows that A and D are
friends of T through the mutual friend query between B and T. In
an FII attack, B can infer that user E is more likely to be a friend of
T. Using only MFB attack, B cannot infer that E is a T's friends with
a high probability. Using just an FII attack, B can only acquire that
A and D are friends of T with low probabilities.
Defense Approaches. The problem causing FII attacks is similar
to the resource sharing problem among multiple users or policy
conflict problem in an SNS. The intuitive approach to defend
against FII attacks is to design a mechanism to address the conflicts
of privacy policies among users.
In the literature, there are several existing works that can be used to
address conflicts in policies. XACML provides the algorithms
including Deny-overrides, Permit-overrides, First-applicable and
Only-one-applicable to address policy conflicts [34]. For instance,
when Policy A (decision of deny) and Policy B (decision of allow)
have conflicting decisions, an SNS will ignore Policy B and accept
Policy A using Deny-overrides. However, the mechanisms in
XACML do not take users' requirements into account. For example,
if user A hides his friend lists from user B and Deny-overrides is
applied, all of A's friends have to hide their friend lists from B in
order to conceal their friendships from A. However, most of these
friends may be likely to share their friend lists with B and these
users' preferences are sacrificed. When Permit-overrides is applied
in the above example, B can have a high probability to identify and
correctly infer A's friends using FII attacks and hence A's preference
will be violated.
Squicciarini et al. propose an auction mechanism to address the
policy conflicts in shared resources based on a voting algorithm
(Clarke-Tax mechanism) and game theory [32]. Hu et al. propose
a conflict resolution approach that balances the need for privacy
protection and the users' desire for information sharing by
quantitative analysis of privacy risk and sharing loss [33]. Both
approaches can be applied to address policy conflicts and defend
against FII attacks.
3. EXPERIMENTS
In this section, we introduce the setup of the experiments for the
FII attacks and demonstrate various FII attacks.
3.1 Datasets
In this paper, we use three real social network datasets to
demonstrate FII attacks:
 D1: It is a Facebook friend network dataset used in [9]. We
remove the isolated nodes in the original dataset since they are
useless in our experiments.
 D2: It is another Facebook friend network dataset used in [10].
Since it is not a well-connected network, we filter the nodes and
choose the giant component of the original dataset for our
experiments.
 D3: It is a Foursquare friend network dataset used in [11]. This
network is a well-connected network.
The basic statistical information of these datasets is shown in Table
1. We can see that users in D1 have the highest degrees and they
are most connected with each other according to the average
clustering coefficient and average path length. Users in D3 have the
least degrees but they are more connected with each other than
those in D2, although users in D2 have higher degrees than those in
D3.
Table 1. Basic statistical information of the datasets
Nodes
Edges
Ave. Degree
Ave. Clustering Coefficient
Ave. Path Length
D1
3,963
88,156
44.49
0.62
3.78
D2
63,392
816,886
25.77
0.25
8.09
D3
10,326
52,974
10.26
0.29
4.41
3.2 Attacks using One Attacker Node
3.2.1 Initializations
To simulate FII attacks using one attacker node, in each dataset, we
randomly choose 1,000 users as attacker nodes. Each attacker node
has three targets:
 Target 1: we randomly choose one target from the attacker
node's friend lists.
 Target 2: we randomly choose one target from the attacker
node's 2-distant neighbors.
 Target 3: we randomly choose one target that is more than 2distant away from the attacker node in the social graph.
Hence, an attacker node has to conduct three FII attacks on three
targets and there are 3,000 FII attacks in each dataset.
Note that all these targets do not allow the corresponding attacker
nodes to view their friend lists. Also note that the selected targets
have at least 10 friends since the corresponding attacker nodes need
to identify and infer 10 (|Fb(t)| = 10) of their friends.
For each attacker node, besides the corresponding targets, we
randomly choose additional 0 to 4 of his friends and set their friend
lists invisible to the attacker node. The rest of the friends of the
attacker node allow the attacker node to view their friend lists. Note
that we set that Target 2 of an attacker node is included in the
attacker node's initial attack knowledge.
We also randomly choose 2 to 5 users who are not friends of the
attacker node and whose friend lists are public and visible to the
attacker node. We set that these selected users are friends of the
Target 3 to make sure that the Target 3 is included in the attacker
node's initial attack knowledge.
3.2.2 Initialization of Parameters
In the experiments, we set |Fb(t)| = λ = 10, where λ is a parameter
mentioned in the attack steps. A parameter e, which is mentioned
in the definition of the FII attack and is used to evaluate the success
of the FII attack, is dynamically set in our experiments.
In Section 2.4.2, we mentioned other two parameters in the attack
steps: β and ɛ. In all of our experiments, we set ɛ=10-6 for the
equation |Vl – Vl-1 | < ɛ. Note that β is the parameter to determine
the probability that a node follows the random walk. Pan et al. show
that β = 0.15 works on the web graph with the diameter 19 [29]. In
our case, we assume the average diameter in the FII attacks is round
3. Theoretically, we can get a better value of β from (1–0.15)19=(1–
β)3 where it should be 0.65. Hence, in all of our experiments, we
set β = 0.65.
3.2.3 Measurements
In our experiments, we use the following measures to evaluate the
FII attacks:
 True Positive: It represents the number of identified and
correctly inferred friends of a target. When it is larger than e (e
is a pre-defined parameter in the definition of an FII attack), it
indicates that the attack is successful.
 Rate of Correctly Identified & Inferred Friends (RC): It
indicates the percentage of exposed friends for a target. It can
be captured as True Positive / |Fb(t)| (the number of identified
and inferred friends).
 False Positive: It represents the number of incorrectly inferred
friends of a target in Fb(t). It is equal to | Fb(t) | – True Positive.
 Rate of Incorrectly Identified & Inferred Friends (RIC): It
indicates the percentage of incorrectly exposed friends for a
target. It can be captured as False Positive / |Fb(t)|.
 Coverage: It represents the maximum number of exposed
friends of a target for an attacker node. It is equal to |Ib(t)|
mentioned in Section 2.3.3. A higher value of the coverage
value indicates that an adversary can find more friends of a
target ideally in the attack. This measurement is used to analyze
the attack results in Section 3.5.2.
3.2.4 General Attack Results from Different Datasets
In this subsection, we simulate the Attack Scheme 1 for the FII
attacks in the three datasets to compare the attack results on these
datasets. The attack results are shown in Table 2.
From Table 2, we can see that FII attacks in D1 are the most
successful one among the three datasets since attacker nodes from
D1 can achieve the highest true positive and the lowest false
positive. FII attacks in D2 are the least successful one and the
attacker node gets the lowest true positive and highest false positive.
Additionally, in D2, the average false positive is even higher than
the average true positive, which indicates that the attack using one
attacker node in D2 is not successful.
Table 2. Results of attack scheme 1 in the three datasets
Average True Positive for Attacker
Nodes (Average RC)
Average False Positive for Attacker
Nodes (Average RIC)
Relationship Between an
Attacker Node & a Target
Friend
2-distant Neighbor
More than 2-distant Neighbor
Friend
2-distant Neighbor
More than 2-distant Neighbor
D1
D2
D3
7.82 (78.2%)
5.78 (57.8%)
4.03 (40.3%)
2.18 (21.8%)
4.22 (42.2%)
5.97 (59.7%)
4.71 (47.1%)
2.85 (28.5%)
3.13 (31.3%)
5.29 (52.9%)
7.15 (71.5%)
6.87 (68.7%)
5.48 (54.8%)
3.25 (32.5%)
3.19 (31.9%)
4.52 (45.2%)
6.75 (67.5%)
6.81 (68.1%)
Table 3. Results of attack schemes in the three datasets
Average True Positive for Attacker Nodes
Attack Scheme
Attack Scheme 1
Attack Scheme 2
Attack Scheme 3
D1
5.88
5.92
6.91
D2
3.56
3.78
4.85
D3
3.97
4.22
5.32
Table 4. Results from FII attacks on the topology of the entire network
Average Correctly Inferred Friendship Links
(Percentage of All Friendship Links)
Average Incorrectly Friendship Links
After Launching
1K FII Attacks
After Launching
5K FII Attacks
After Launching
10K FII Attacks
After Launching 20K
FII Attacks
4113.4 (7.76%)
17948.3 (33.88%)
32231.4 (60.84%)
37891.2 (71.53%)
4528.6
13314.4
21653.2
25472.3
We can also see that the FII attacks are the most successful when
the attacker nodes and targets are friends. Such a result is expected
since the attacker nodes are very close to the targets and have more
opportunities to have more mutual friends with the targets. When
attacker nodes and targets are 2-distant neighbors, generally, the
FII attacks are second most successful. However, in D2, the FII
attacks where the attacker nodes and the targets are 2-distant
neighbors, are less successful than those where the attacker nodes
more than 2-distant away from the targets.
nodes, number of edges, the average degree of nodes and the
number of triangles, empirically, have insignificant impact on
attack results. In theory, when the clustering coefficient is higher
and the path length is smaller, it indicates that the nodes in the graph
tend to cluster together. If nodes tend to cluster in a social graph,
instinctively, an FII attack has a higher probability of success. This
result suggests that an adversary should launch an FII attack in a
more highly clustered network, in order to ensure a more successful
attack.
To quantify the successful attacks in the simulations, we can set
various values of e which is a pre-defined parameter to indicate a
successful FII attack. When we set e = 3, we find out that most of
FII attacks in D1 are successful. More than half of the FII attacks
in D3 and around half of the FII attacks in D2 are successful. When
we set e = 5, many FII attacks in D1 are still successful while
around half of the FII attacks in D3 and around 20% of FII attacks
in D2 are successful.
3.2.5 Attack Results from Different Attack Schemes
By comparing the basic network statistics shown in Table 1, we
may conclude that FII attacks are more effective in a social graph
with a higher average clustering coefficient and a lower average
path length. Other features for the social graph, such as number of
We can see that Attack Scheme 3 can significantly improve the
attack results in each dataset. An attacker node using Attack
Scheme 3 can identify and correctly infer at least one more friends
of a target compared to the Attack Scheme 1. In addition, Attack
In this subsection, we first compare the attack results using three
basic attack schemes (mentioned in Section 2.4.3) where an
adversary only uses one attacker node. We simulate these three
attack schemes in D1, D2 and D3. The results are shown in Table
3. Note that each attacker node has three different targets and we
compute the average true positive from each attacker node on these
three targets in Table 3.
Scheme 2 can improve the attack results a bit compared to the result
of Attack Scheme 1.
3.3 Attacks using Multiple Attacker Nodes
To simulate the FII attacks using multiple attacker nodes, we first
randomly choose 1000 targets in D3 and all of them have at least
10 friends. We then select four sets of attacker nodes for each
selected target:
 M1: Attacker nodes in the set are one friend of the target, one
2-distant neighbor of the target and one user who is more than
2-distant away from the target.
 M2: Attacker nodes in the set are three friends of the target, one
2-distant neighbor of the target and one user who is more than
2-distant away from the target.
 M3: Attacker nodes in the set are three friends of the target, five
2-distant neighbors of the target and five users who are more
than 2-distant away from the target.
 M4: Attacker nodes in the set are five friends of the target, five
2-distant neighbors of the target and five users who are more
than 2-distant away from the target.
For each selected attacker node, we randomly choose additional 0
to 4 of his friends and set their friend lists invisible to the attacker
node. The rest of the friends of the attacker node allow the attacker
node to view their friend lists. We also randomly choose 2 to 5 users
who are not friends of the attacker node and whose friend lists are
public and visible to the attacker node.
The initialization of parameters in the FII attacks in these
simulations is the same as those described in Section 3.2.2. For each
target, we adopt the Attack Scheme 1 and use the combine available
network formed by the initial knowledge of all the attacker nodes
to launch the attack. The attack results are shown in Figure 5. From
the figure, we can see that the attack result highly depends on the
number of attacker nodes that are friends of the corresponding
targets. When the attacker nodes are 2-distant neighbors of the
corresponding target or more than 2-distant away from the target,
these attacker nodes contribute less for the attack result. Compared
to the result of the FII attacks using one attacker node (shown in
Table 2 and 3), we can see that the FII attacks using multiple
attacker nodes can significantly identify and infer more private
friends of a target.
First, we focus on D3. We randomly select an initial attacker node
whose degree is larger than 10 in D3. For this attacker node, we set
the initial attack knowledge of the attacker node by randomly
choosing additional 0 to 4 of his friends whose friend lists are
invisible to the attacker node. Then, a small set of the available
friendship links forms the adversary's initial knowledge about the
network topology. We then choose the most vulnerable target that
has the most number of mutual friends (more 2-distant paths) with
the attacker node and launch an FII attack using the Attach Scheme
1 (the adopted parameters in an FII attack are same as those
mentioned in Section 3.2.2). We add the inferred friendship links
into the adversary’s knowledge. After that, from the adversary’s
knowledge about the network, we choose a pair of users who have
the most number of mutual friends. We then set one of them as the
attacker node and the other as the target in a new FII attack. Note
that, before the new FII attack, we also initialize the attack
knowledge for this attacker node using the same approach used for
the initial attacker node. Lastly, we keep choosing the attacker
nodes and targets to launch the FII attacks to infer the entire
topology of the friendship network.
We repeated each attack 10 times in D3 and the results are shown
in Table 4. From the table, we can see that such an attack is effective
and a large percentage of the network is exposed when an adequate
number of of FII attacks are launched. For example, this attack can
correctly infer more than 70% of the network topology when 20000
FII attacks were conducted. However, the number of incorrect
friendship links included cannot be eliminated although it increases
slowly with the increasing number of FII attacks launched. We
argue that this is because the matrix indicating the friendship
network in D3 is very sparse and there are many users who have
fewer friends or even no friends. We evaluate this assumption by
conducting the attack in D1, which has fewer users but has more
friendship links. Our simulation of the attack in D1 confirms our
assumption: when 1000 FII attacks were launched, such an attack
scheme can correctly infer more than 85% of the network topology
in D1 and achieves fewer than 2000 incorrectly inferred friendship
links.
3.5 Discussions
3.5.1 Attack Results & Attacker Nodes' Initial Attack
Knowledge
In this subsection, we try to find out the relationship between attack
results and attacker nodes' initial attack knowledge. We simulate
the three attack schemes proposed in Section 2.4.3 using one
attacker node. The results are shown in Figure 6 and Figure 7.
Average True Positive for Targets
Average False Positive for Targets
8
7
6
Note that an attacker node's initial attack knowledge in our
simulations is determined by 1) the number of additional friends
who hide friend lists from the attacker nodes and 2) the number of
users who are not friends of the attacker nodes and whose friend
lists are public as mentioned in Section 3.2.1.
5
4
3
2
1
0
M1
M2
M3
M4
Figure 5. Attack results using multiple attacker nodes
3.4 Using FII Attacks to Infer the Topology of
the Entire Network
We present the results of using the FII attacks to infer the topology
of the entire network in this subsection.
Figure 6 shows the average true positive of attacker nodes with
regard to different number of friends who hide friend lists from the
attacker nodes. We can see that the true positive does not decrease
significantly with the increase of the number of additional friends
hiding their friend lists from attacker nodes in D1. However, in D2
and D3, the true positive decreases significantly with the increase
of the number of additional friends whose friend lists are invisible
to the attacker nodes. It indicates that attacker nodes in D2 and D3
are more sensitive to the number of visible friends than those in D1.
It is reasonable since users in D1 have more friends than those in
D2 and D3. For the attacker nodes in D1, the friends whose friend
lists are invisible does not constitute a significant part in his friend
list. However, such friends constitute the larger part of an attacker
node's friend list in D2 and D3.
D1
D2
D3
Average True Positive
7
6
5
4
3
2
1
0
0
1
2
3
4
Number of Additional Friends Who Hide their Friend Lists from
an Attacker Node
Figure 6. The attack result vs. the number of additional
friends whose friend lists are invisible to an attacker node
Figure 7 shows the average true positive of attacker nodes with
regards to the different number of public friend lists in the FII
attacks. We can see that the true positive increases more
significantly when there are more public friend lists in D1.
However, in D2 and D3, with the increase of the number of public
friend lists, the true positive does increase but the increase is not
significant. It indicates that the number of public friend lists is more
useful for attacker nodes in D1 than those in D2 and D3. The reason
is that users in D1 tend to cluster with each other and it is more
likely for the public friend lists to include the information related
to the targets. On the other hand, users in D2 and D3 are not inclined
to cluster with each other and hence it is less likely for the public
friend lists to contain the information related to the targets.
Average True Posituve
D1
D2
D3
9
8
7
6
5
4
3
2
1
0
2
3
4
5
Number of Users Who are not Friends of an Attacker Node and
Whose Friend Lists are Public
Figure 7. The attack result vs. the number of users whose
friend lists are public
3.5.2 Analysis of Unsuccessful Attacks
In this subsection, we aim to find out potential reasons that cause
FII attacks to be unsuccessful. We set e=3 and analyze the attacks
using Attack Scheme 1 in D3 using one attacker node. In the attack
results, there are around 32% of unsuccessful attacks (the number
of correct friends in Fb(t) is less than 3). The statistics about these
attacks and the results are shown in Table 5.
Table 5. Statistical information about the unsuccessful attacks
Ave. Friends of Attacker nodes
Ave. Friends of Targets
8.27
12.94
Ave. Mutual Friends between an Attacker Node and a Target
Ave. Coverage
1.12
6.28
By comparing the corresponding information in Table 5 and Table
1, we can see that the attacker nodes usually have fewer friends in
unsuccessful attacks. The average number of friends for attacker
nodes in unsuccessful attacks is 8.27 while the average number of
friends for users in D3 is 10.26. In addition, we find that the average
number of mutual friends between an attacker node and a target is
also limited. This may be another reason that leads to an
unsuccessful attack. Furthermore, the most important reason is that
the average coverage (6.28) is much less than 10 (the number of
identified and inferred friends in an FII attack). Note that the
coverage represents the maximum number (|Ib(t)|) of friends of a
target exposed to an attacker node. According to the Theorem in
Section 2.3.3, an attacker node cannot find more than |Ib(t)| friends
of a target in an FII attack. In an unsuccessful attack, an attacker
node can only correctly identify up to 6.28 friends of targets in
average. However, in a successful attack in our experiments, |Ib(t)|
is usually larger than 12. Hence, we believe that the small value of
|Ib(t)| is another important reason that causes an attack to be
unsuccessful.
4. RELATED WORK
Many research efforts have focused on the link prediction/inference
issues in SNSs based on the users' attributes. Hasan and Zaki
summarize the supervised link prediction algorithms, including
Bayesian probabilistic models, linear algebraic models and
probabilistic relational models in [17]. Yin et al. introduce SocialAttribute Network (SAN), an attribute-augmented social network,
to integrate network structure and node attributes to perform the
link recommendations using the random walk with restart
algorithm [12, 18]. Gong et al. extend the SAN framework based
on their observation that inferring attributes could help predict links
[19]. However, the above approaches usually require users'
attribute information for link prediction. In an FII attack, an
adversary can launch the attack without knowing users' attribute
information.
Recently, some efforts have focused on predicting missing links in
a global SNS. Korolova et al. mention that users' behavior of
sharing their friends to the public could allow an attacker to
discover the topology of an SNS [1]. Effendy et al. extend the work
by Korolova et al. and show that such an attack can be “magnified”
substantially with the inference on user degrees [20]. Bonneau et al.
report that the social network structure can be disclosed when a
random sample of k edges from each node in the SNS is exposed
[21]. Leroy et al. use group information to build a bootstrap
probabilistic graph in order to perform friendship link inferences
[22]. Kim and Leskovec adopt the Expectation Maximization (EM)
algorithm to infer the missing nodes and edges by observing part of
the network [23]. Erdös el al. propose a heuristic approach to
discover the missing links based on common neighbors of subnetworks [24]. Chen et al. construct the Markov Logic Network to
infer the friendship links on a large scale social graph [26].
However, these approaches focus on inferring few missing
friendship links based on many observed friendship links. In an FII
attacks, an adversary launches attacks with the enforcement of
users' privacy settings and he is allowed to see friend lists that he is
authorized to view. The adversary focuses on inferring many
friendship links of a target from limited friendship information of
the target.
Some existing works propose attacks using the visible local
network to identify and/or infer users' private information.
Puttaswamy et al. introduce intersection attacks based on shared
contents, such as URLs, to infer users' attributes and preferences
[25]. The intersection attacks require an adversary to have two
compromised nodes in a social graph and then the adversary can
infer the value of the resource of a common user (victim) of the
compromised nodes. Jin et al. propose the mutual-friend based
attack to identify a target's friends via various mutual friend queries
among users [4]. Compared to the FII attack, the adversary in above
attacks has to know the common elements (e.g. mutual friends)
between users. For example, in a mutual-friend based attack, the
adversary can query mutual friends between him and any other
users. However, mutual friend queries are not necessary for an FII
attack. In addition, we believe that an FII attack and a mutual-friend
based attack are complimentary and they can be used together for
more successful privacy attacks.
[6] Z. Wen and C. Y. Lin. On the quality of inferring interests
from social neighbors. KDD '10.
Several approaches have been proposed that can be used to infer
friends of a target n the literature, such as the approaches based on
the various similarities among users [16, 17, 27] and the EM
algorithm [23]. We do not adopt these approaches because an
adversary in an FII attack does not need to know any of a target's
friends initially. Hence, the user-similarity based approaches and
the EM algorithm may be difficult to apply in this scenario.
Additionally, the random walk with restart algorithm is shown to
be probably the most effective approach for predicting links in
social networks [27].
[12] Z. Yin, M. Gupta, T. Weninger and J. Han. A Unified
Framework for Link Recommendation Using Random
Walks. ASONAM '10.
5. CONCLUSIONS
[7] L. Bilge, T. Strufe, D. Balzarotti and E. Kirda. All your
contacts are belong to us: automated identity theft attacks on
social networks. WWW '09.
[8] L. Jin, H. Takabi and J. B.D. Joshi. Towards active detection
of identity clone attacks on online social networks.
CODASPY '11.
[9] J. J. McAuley and J. Leskovec. Learning to Discover Social
Circles in Ego Networks. NIPS '12.
[10] B. Viswanath, A. Mislove, M. Cha and K. P. Gummadi. On
the evolution of user interaction in Facebook. WOSN '09.
[11] L. Jin, X. Long and J.Joshi. Towards understanding
Residential Privacy by Analyzing User' Activities in
Foursquare. BADGERS '12.
[13] A. Noulas, S.Scellato, N. Lathia and C. Mascolo. A Random
Walk Around the City: New Venue Recommendation in
Location-Based Social Networks. SOCIALCOM '12.
[14] M. E. J. Newman. Networks: An Introduction. Oxford
University Press, 2010.
[15] P. Sarkar. Random Walk in Social Networks and their
Applications: A Survey. Social Network Data Analytics, pp
43-77, 2011.
In this paper, we identify the threat of the inconsistent policies for
a friendship link involving two users in undirected SNSs. We
propose that such a threat can be abused by an adversary to launch
an FII attack to identify and infer friends of a target who conceal
his friend list from the adversary. We define an FII attack and
introduce the attack steps and the attack algorithm. In addition, we
propose various attack schemes which could improve the attacks.
Our simulation results show that the FII attacks are effective. We
note that most the popular SNSs, such as Facebook, LinkedIn and
Foursquare, are currently susceptible to FII attacks and, as the
future work, we will work on the defense approaches.
[16] D. Liben-Nowell and J. Kleinberg. The link prediction
problem for social networks. Journal of the American Society
for Information Science and Technology, v. 58, pp 10191031, 2007.
6. ACKNOWLEDGMENTS
[19] N. Z. Gong, A. Talwalkar, L. Mackey, L. Huang, E.C. R.
Shin, E. Stefanov, E. Shi and D. Song. Jointly Predicting
Links and Inferring Attributes using a Social-Attribute
Network (SAN). SNA-KDD '12.
Support for this research has been provided by NSF DGE Award
#1027167.
7. REFERENCES
[1] A. Korolova, R. Motwani, S. U. Nabar , and Y. Xu. Link
privacy in social networks. CIKM '08.
[2] D. G. Avello. All liaisons are dangerous when all your
friends are known to us. HT '11.
[3] A. U. Asuncion and M. T. Goodrich. Turning privacy leaks
into floods: surreptitious discovery of social network
friendships and other sensitive binary attribute vectors.
WPES '10.
[4] L. Jin, J. B.D. Joshi and M. Anwar. Mutual-friend Based
Attacks in Social Network Systems. Computer & Security, v.
37, pp 15-30, 2013.
[5] E. Zheleva and L. Getoor. To join or not to join: the illusion
of privacy in social networks with mixed public and private
user profiles, WWW '09.
[17] M. A. Hasan and M. J. Zaki. A survey of link prediction in
social net-works. Social Network Data Analytics, pp 243–
276. 2011.
[18] Z., Yin, M. Gupta, T. Weninger and J. Han. LINKREC: a
unified framework for link recommendation with user
attributes and graph structure. WWW '10.
[20] S. Effendy, R. H.C. Yap and F. Halim. Revisiting Link
Privacy in Social Networks. CODASPY '12.
[21] J. Bonneau, J. Anderson, R. Anderson and F. Stajano. Eight
Friends Are Enough: Social Graph Approximation via Public
Listings. SNS '09.
[22] V. Leroy, B. B. Cambazoglu and F. Bonchi. Cold Start Link
Prediction. KDD '10.
[23] M. Kim and J. Leskovec. The Network Completion Problem:
Inferring Missing Nodes and Edges in Networks. SDM '11.
[24] D. Erdös, R. Gemulla and E. Terzi. Reconstructing Graphs
from Neighborhood Data. ICDM '12.
[25] K. P.N. Puttaswamy, A. Sala and B. Y. Zhao. StarClique:
guaranteeing user privacy in social networks against
intersection attacks. CoNEXT '09.
[26] H. Chen, W. Ku, H. Wang, L. Tang, and M. Sun. LinkProbe:
Probabilistic Inference on Large-Scale Social Networks.
ICDE '13.
[27] L. Lüand T. Zhou. Link prediction in complex networks: A
survey. Physica A: Statistical Mechanics and its
Applications, v. 390, pp 1150-1170, 2011.
[28] H. Tong, C. Faloutsos and J. Pan. Fast Random Walk with
Restart and Its Applications. ICDM '06.
[29] J. Pan, H. Yang, C. Faloutsos and P.Duygulu. Automatic
Multimedia Cross-modal Correlation Discovery. KDD '04.
[30] A. N. Joinson. Looking at, looking up or keeping up with
people?: motives and use of facebook. CHI '08.
[31] D. Boyd and E. Hargittai. Facebook privacy settings: Who
cares. First Monday, vol. 15, no. 8, pp. 23, 2010.
[32] A. C. Squicciarini, M. Shehab, J. Wede. Privacy Policies for
Shared Content in Social Network Sites The VLDB Journal,
vol. 19(3). pp. 777-796, 2010.
[33] H. Hu, G. Ahn and J. Jorgensen. Detecting and resolving
privacy conflicts for collaborative data sharing in online
social networks. ACSAC '11.
[34] eXtensible Access Control Markup Language (XACML)
Version 3.0, http://docs.oasis-open.org/xacml/3.0/xacml-3.0core-spec-os-en.html.