Na Li1, Yuhong Liu2, Venu Madhavi Doddapaneni1, and Sai Samrat Malka1 1. Department of Mathematics, Computer Science and Information Systems, Northwest Missouri State University, Email: nali@nwmissouri.edu
2. Department of Information Sciences and Technology, Penn State Altoona, Email: yuhong@psu.edu
Abstract—Recently, one of the most popular services in online social networks (OSNs) is the friend search engine, which is intended for querying the friend lists of individual users. However, privacy concerns have risen since users may not feel comfortable to display their full friend lists in response to queries. In our previous work, we have proposed a privacy-aware display strategy which prevents the search engine from displaying more friends than the users are willing to expose. However, the lack of real attack data makes it hard to evaluate the effectiveness of such a strategy in reality. In this article, we propose the design of a web application which can be used to collect real friend search behaviors of normal users as well as attack strategies which aim to violate users’ friendship privacy. The collected data will advance our understanding of advanced attack strategies and help with the design of a more secured search engine with privacy protection.
I. INTRODUCTION
In recent years, online social networks (OSN), such as
Facebook and Twitter, have become very popular and attracted
a large number of users who use them on a daily basis.
Various service applications are developed to help OSN users
easily network with their families and friends, for instance,
commenting on a friend’s wall, exchanging instant messages,
making new friends and so on. One of the most popular
services is the friend search engine, which is intended for
querying the friend lists of individual users.
The OSN operator is inclined to return a full friend list per
query to increase the sociality of the OSN and attract more
people to join the online community. This is because displaying
the full list will increase the possibility of disclosing more
people with whom the requestor may be acquainted, thereby
encouraging the requestor to make friend with the queried user.
However, releasing the full list may cause the queried user to
concern about his privacy as it may expose more friendship
information than he feels comfortable to share. Some attentions
[1], [2], [5] have been paid to the vulnerabilities against
friend search engines on OSNs. Particularly, in our previous
work [2], a privacy preserving strategy is proposed to prevent
the search engine from displaying more friends than the users’
privacy settings.
However, the lack of real attack data makes it hard to
evaluate the effectiveness of the proposed strategy in reality.
Moreover, the OSN operators have the full control over the data
that they collected from their users and leave it impossible for
the third-party researchers to study the normal and abnormal
query behaviors of OSN users so as to design effective defense
technologies. Considering such restrictions, we are motivated
to design a web application which can not only provide a
user-friendly interface for OSN users to query friend lists of
individual users but also help the third-party researchers collect
data and analyze users’ query behaviors through the search
engine so as to better understand the possible attack strategies
and design a securer search engine.
This article intends to introduce the design of our web
application. The roadmap of the article is outlined as follows.
In Section II, we will describe the infrastructure of our web
application in terms of the front and back ends, respectively.
We will address the basic workflow of the application in
Section III. In Section IV, we will introduce the display
strategy proposed in [2], which prevents attackers from getting
more friendship information of an individual user than he
wants to share. We plan to implement this strategy in our web
application as a basic defense. Finally, a conclusion is given
in Section V.
II. THE INFRASTRUCTURE OF THE WEB APPLICATION
This web application will be developed as a third-party
application which can be integrated with an OSN, for instance,
Facebook. In the following, we will describe the detailed
design of the front and back ends of the web application.
A. Front end
The front end has a web interface, which requires a user
(i.e. requestor) to sign in to access the friend search engine.
This requirement is reasonable as in practice, a user needs to
log into an OSN to use all services provided by it. After the
requestor logs into the web site, he will be able to see the web
page used for searching the friend lists of individual users. The
page is divided into four sections as shown in Figure 1. The
upper-left section is the basic search engine interface which
contains a text field and a search button. The requestor enters
the target user’s user name or ID into the text field and clicks
the search button to query the target user’s friend list in the
OSN.
 Fig. 1. The mock web interface
The lower-left section visualizes the target user and his
friend list through the network graph model, where nodes
represent users and edges represent friendships. Whenever
a new query is issued, the network graph is updated with
the information collected from the query result. As more
queries are conducted, the graph becomes denser. In addition,
the requestor is able to interact with the displayed network.
Specifically, he can either zoom in to check a specific part of
the network or zoom out to accommodate all visible nodes and
edges in the network. By simply selecting a node, the requestor will see the selected user’s ID in the text field in the upper-left
section. He can then launch a search on the selected user by clicking the search button.The lower-right section contains a request function and a table view. This section is used for requesting another requestor’s network graph. For example, a requestor A can type in the user name or ID of another requestor B to request his network graph. If the permission is granted, A’s network graph will be updated with the graph imported from B. Additionally, an entry will be added to the table to record the importing time and B’s user name or id. Such function may provide the requestor a chance to check and compare their search results with the results from others. If two requestors obtain different friendship information about the same target user, a privacy leakage occurs. As designers, we aim to use this function to collect the ground truth data of multiple requestors’ collusion behaviors.
In the upper-right section, there is a chart which updates in a real-time manner. It shows how many users have had their friendship privacy compromised due to the queries conducted by the requestor. Whenever a new query is conducted or another requestor’s network graph is imported, this chart may be updated.
B. Back end
The back end of our web application has a server which accesses the data stored in a MySQL database and interacts with the OSN through the API provided by the social site to retrieve the friend lists. The database contains all of the information about the queries conducted through our web interface, which will be used for analyzing the requestors’ query behaviors.
III. THE DESIGN OF THE WORKFLOW
In this section, we will use the sequence diagram in
Figure 2 to describe the activities which may occur through
our web interface. A requestor can take five actions with our
web application, including signing in, querying a user’s friend
list, requesting the view of another requestor, replying to the
request sent by another requestor to import the view, and
logging off. Next, we will detail each of these actions
Actions I. Sign in. When a requestor visits the home page
of the web application, he is required to provide his user name
and password to sign in to the site. His user name and the
time he signed in are recorded in the back-end database. Then
the visualization section on the web page displays the network
graph that the requestor could see before he logged off in the
previous visit to the site. Additionally, the chart shows how
many users have had their friendship privacy compromised by
this requestor’s previous queries. Fig. 2. The sequential diagram of our web service
Action II. Query a user’s friend list. Once a query is sent to
our web server, the server will check whether the same target
user has been queried recently. If so, we can find his friend
list in the database rather than send a new query to the OSN
through the API. Note if the previous query on the target user
was made a long time ago, the friend list is out of date. In that
case, we will send a new query, although his list is already in
the database.
Once the friend list is retrieved from the OSN, we save
a copy of the list in the database and then run our display
strategy [2] on the server to decide which friends should
be visualized in the web interface. The decision should be
made based on both the target user’s privacy concern and the
sociability of the OSN, which will be detailed in Section IV.
With the list of friends for display, both the network graph
visualized and the chart of compromised users are updated
accordingly.
Action III. Import the network graph viewed by another
user. This action is taken by malicious requestors (i.e., attackers)
who want to share each other’s view to infer more
friendship information than what they can see independently
in their query results. With this feature, one requestor can
send a request to another requestor to import his view from
his previous queries. After typing the user name of another
requestor and sending a request, this requestor waits for the reply.
Action IV. Respond to the request sent by another user
for importing the network graph. This action is taken once
a requestor receives a request for sharing his network view.
As a response to the request, the requestor can grant the
permission for importing his network view or deny the request.
The decision the requestor makes is saved in the database.
For the requestor who sent the importing request, if the
permission is granted, his network graph and the chart of
compromised users will be updated. Additionally, a new entry
is added in the table in the lower-right section on the web page
to record the user name or ID of the requestor who shared his
view. If the view-sharing request is denied, the requestor will
be notified. The visualization on the web page will not be
changed.
Action V. Log off. When a requestor leaves the site, the
time of his logging off and the network graph formed by the queries he already made are stored in the database.
IV. THE PRIVACY-AWARE DISPLAY STRATEGY
The strategy we use for deciding which friends to return
in response to each query was designed in our previous work [2]. This work made a reasonable assumeption where
individual users set a parameter, k, to indicate how many
friends they feel comfortable to display. A large value tells
the user doesn’t care much about his friendship privacy, while
a small number indicates he is sensitive about sharing such information. The proposed display strategy handles the tradeoff between preserving privacy and stimulating sociability of the social site.A. The comparison of three display strategies
In the paper [2], the proposed display strategy is compared with two other strategies, Random k - randomly selecting k friends to display, and Rank k - always choosing the k most influencial friends on the OSN. These three strategies are compared in terms of their effectiveness against attacks that compromise users’ friendship privacy by direct exposure, mutual effect and link prediction. The result of the comparison is given in Table I.
 Direct Exposure. With Random k, the direct exposure occurs when the same user is queried more than once. This is because different sets of k friends may be displayed to expose more than k friends in total. An example is shown in Figure 3 in which x is queried twice. Different colors are used to distinguish the sets of friends displayed in response to different queries. With Rank k, since it always displays the k
most influential friends, the same set of k friends is returned regardless of the times that user is queried. The proposed strategy [2] can defend against this type of attacks.
 Fig. 3. An example of direct exposure
Mutual Effect. An example of the occurrence of the attack caused by mutual effect is given in Figure 4. Suppose when we query user x, his friendship with user y is not displayed, but it is exposed when user y is queried. In this case, user x’s privacy is compromised as its k +1 friends are disclosed. The problem results from the fact that each friendship is associated with two users and it can be exposed by a query upon either of them. Both of the display strategies of Random k and Rank k are vulnerable to this type of attacks, while the proposed strategy [2] can defend against the attacks.
 Fig. 4. An example of mutual effect
Link Prediction. The link prediction problem in social networks was first proposed to predict which connection between users will be generated in the near future in a social network graph. A simple but effective prediction technology [3], [4] is based on the number of common friends the two users have. If they share many friends, most likely, they will become friends soon. If this link prediction technique is applied to the friendship network detected by queries, more friendship information may be inferred. An example is given in Figure 5, where solid lines represent the friendships already detected by queries, and dotted lines denote the friendships which exist in the original OSN but have not been discovered yet. Suppose we assume if two users share equal to or greater than two friends in the network graph detected by queries, they will be friends in the original OSN with a high probability. In Figure 5, as user x and user y have three common friends visible in the query results, we can predict that it is very likely that they have a connection in the OSN. Neither of Random k and Rank k works against this type of attacks, while the display strategy [2] can deal with the attacks.
 Fig. 5. Relationship disclosure by common friends
B. The models for attacks and privacy preservation
In the attack model, an attacker attempts to independently compromise users’ friendship privacy. He intends to send a large number of queries through a friend search engine and then analyze the query results he collects to infer more friendship information than what he can obtain from his query results.
A privacy preservation model, called (β, k)-inference privacy preservation model, was defined in our previous work [2]. This model ensures that each node appearing in the query results will not have more than k friends exposed, even when the link prediction techniques are applied. k is the parameter individual users determine for their privacy settings. β holds a threshold used for the link prediction technique - if two users share equal to or greater than β friends, most likely, they are friends in the OSN.
C. The proposed strategy
The proposed strategy handles the tradeoff between preserving privacy and stimulating the sociability of an OSN. It consists of two primary steps: (1) sorting neighbors (i.e., friends) of the queried user in the descending order of their influence on the sociability of the OSN; and (2) checking each neighbor in the sorted list to determine whether it can be displayed as a friend of the queried user.
1) Sort neighbors: The purpose of sorting neighbors in terms of their influence on the sociability of the OSN is to consider the most influential friends for display first. OSNs may use different ways to evaluate the influence of individual users; however, we believe the number of a user’s friends can indicate his influence on the sociability of the OSN. Therefore, we use it for measuring such influence. Additionally, in order to defend against the attacks caused by mutual effect, the users whose friendships with the queried user have already been seen in the query results should be displayed as friends. Therefore, we exclude those users from the set of neighbors that need to be sorted.
2) Check friendships for display: In the second step, the proposed display strategy colors nodes white, gray and black. If a node is queried or has had k friends displayed, it’s colored black. If a node is visible in the query result but has not been queried yet, it’s colored gray. All other nodes in the original OSN are colored white. Then the strategy checks each nonblack node from the sorted list to decide whether to display it as the queried user’s friend. The reason for skipping black nodes is that a black node has had k friends displayed, therefore, exposing its friendship with the queried node will cause it to have more than k friends exposed.
 Fig. 6. An example of not approving the disclosure of a friendship
For a non-black neighbor in the sorted list, to determine whether to display it as a friend of the queried node, our strategy checks the neighbors of the non-black neighbor and the neighbors of the queried user in the query results to see whether their privacy will be compromised if the friendship between the non-black neighbor and the queried user is exposed. Figure 6 shows an example of not approving the disclosure of a friendship. If the friendship between x and y is displayed, x and z have 2 common friends exposed. Since β has the value of 2, the attacker can infer the friendship between x and z, which causes the leakage of z’s friendship privacy, given k = 2. After checking all of the neighbors, if no neighbor’s privacy is affected, we will display the non-black neighbor as the queried user’s friend. Then, we will go to check the next non-black node in the sorted list until we find enough friends to return in response to the query on the user’s friend list.
V. CONCLUSION
In this article, we introduced the design of a web application which implements a friend search engine connected to an OSN through the OSN API. This application can be used to collect real friend search behaviors of normal users as well as attack strategies which aim to violate users’ friendship privacy. Additionally, it can help us verify the effectiveness of the defense proposed in [2] and study abnormal querying behaviors so as to design a more secured search engine with privacy protection. We discussed the design of the front and back ends of our application and the possible actions a user can take through our web interface. Additionally, we introduced the privacy-aware display strategy proposed in the work [2] which we plan to implement in the back end in our web application.
ACKNOWLEDGMENT
The authors thank Ram Prasad Jayini for his early involvement
in the project and Anil Kumar Pamulapati for his support
on the development of the web application.
REFERENCES
[1] J. Bonneau, J. Anderson, F. Stajano, and R. Anderson. Eight friends are enough: social graph approximation via public listings. In Proceedings of ACM SNS’09, pages 13–18, 2009.
[2] N. Li. Privacy-aware display strategy in friend search. In Proceedings of IEEE International Conference on Communications (ICC), Communication and Information Systems Security Symposium, pages 951–956, 2014.
[3] L. Lu and T. Zhou. Link prediction in complex networks: A survey. Physica A: Statistical Mechanics and its Applications, 390(6):11501170, March 2011.
[4] P. Sarkar, D. Chakrabarti, and A. W. Moore. Theoretical justification of popular link prediction heuristics. In Proceedings of COLT’10, 2010.
[5] A. Yamada, T. H.-J. Kim, , and A. Perrig. Exploiting privacy policy conflicts in online social networks. In Technical report, 2012.   Yuhong Liu is an assistant professor in the Department of Information Science Technology at Penn State Altoona. She received her Ph.D. degree from University of Rhode Island in 2012. She was the recipient of the 2013 University of Rhode Island Graduate School Excellence in Doctoral Research Award. With expertise in trustworthy computing and cyber security, her research interests include three major directions: online social network security, trust management in cyber-physical systems and trustworthy cloud computing. Her work on securing online reputation systems received the best paper award at the IEEE International Conference on Social Computing 2010 (acceptance rate = 13%).
 Venu Madhavi Doddapaneni is currently pursuing her Master’s degree in the program of Applied Computer Science at Northwest Missouri State University. Also, she is a Research Assistant supervised by Dr. Na Li. She received her Bachelor’s degree in Information Technology from Acharya Nagarjuna University, India. Prior to joining Northwest, she worked for SYNTEL as a software engineer in Research and Development (Mobile Computing - iOS) in India for 1 year. Her research interests include network security and mobile computing.  Sai Samrat Malka is currently pursuing his Master’s degree in the program of Applied Computer Science in Northwest Missouri State University. He received his Bachelor’s degree in Electronics and Communication Engineering from Kakatiya University, India. He worked as Software Engineer in an IT company for 2 years prior coming to Northwest. His professional interests include Network security, Mobile computing, Web technology, analysis of real time application and current trends in it. |
E-Letter > STCSN-E-Letter-Vol-2-No-4 >