Felix Dietze
email: dietze@comm.rwth-aachen.de

Johannes Karoff
email: johannes.karoff@rwth-aachen.de

André Calero Valdez
email: calero-valdez@comm.rwth-aachen.de

Martina Ziefle
email: ziefle@comm.rwth-aachen.de

Christoph Greven
email: greven@cs.rwth-aachen.de

Ulrik Schroeder
email: schroeder@cs.rwth-aachen.de

An Open-Source Object-Graph-Mapping Framework for Neo4j and Scala: renesca

Keywords: Graph Databases, Scala, Neo4j, REST API, Object-Graph-Mapper, OGM

The usage and application of graph databases is increasing. Many research problems are based on understanding relationships between data entities. This is where graph databases are powerful. Nevertheless, software developers model and think in object-oriented software. Combining both approaches leads to a paradigm mismatch. This mismatch can be addressed by using object graph mappers (OGM). OGM adapt graph databases for object-oriented code, to relieve the developer. Most graph database access frameworks only support tablebased result outputs. This defeats one of the strongest purposes of using graph databases. In order to harness both the power of graph databases and object-oriented modeling (e.g. type-safety, inheritance, etc.) we propose an open-source framework with two libraries: 1) renesca, which is a graph database driver providing graph-query-results and changetracking. 2) renesca-magic, a macro-based ER-modeling domain specific language (DSL). Both were tested in a graph-based application and lead to dramatic improvements in code size (factor 10) and extensibility of the code, with no significant effect on performance.

Introduction

An increasing amount of today's applications uses graph-based data structures. Social Network Analysis [START_REF] Dev | Privacy preserving social graphs for high precision community detection[END_REF], bibliometrics [START_REF] Holzinger | On graph entropy measures for knowledge discovery from publication network data[END_REF], biomedical data [START_REF] Singh | Sql2neo: Moving health-care data from relational to graph databases[END_REF], recommender systems, and neural networks are just some of the research fields that use graphbased data structures (e.g. railroad-planning [START_REF] Mpinda | Graph database application using neo4j (railroad planner simulation)[END_REF], remote sensing [START_REF] Lampoltshammer | Improving the computational performance of ontology-based classification using graph databases[END_REF]). Even software development itself can benefit from the power of graph databases [START_REF] Urma | Source-code queries with graph databases-with application to programming language usage and evolution[END_REF]. Graph

The framework is available at https://github.com/renesca/ databases differ from other forms of databases as they rely on graph-based data storage internally. This comes with the benefit of naturally modeling data that derives meaning from structure and relations. Another benefit of graph databases is their performance in local search tasks that are based on relationships of the stored data. This is particularly helpful when using social network data [START_REF] Angles | Benchmarking database systems for social network applications[END_REF].

On the other hand a lot of software development today is done using the object-oriented software paradigm. Object-oriented modeling and programming allows an intuitive organization of code as it allows the developer to think in object terms that are natural to the human mind.

Holzschuher and Peinl [START_REF] Holzschuher | Querying a graph database-language selection and performance considerations[END_REF] investigated the benefits of graph databases in comparison to Apache Shinding that uses a relational database backend. They state that using graph-based databases comes with little performance overhead and more readable code.

Object-Graph Mapping

Naturally, vendors have come up with Object-Graph Mapping tools that are already in use. Neo4j comes with an OGM 4 that is currently in release 2. But also third party vendors provide OGM for Neo4j. Hibernate is a very popular example. Hibernate OGM5 also supports Neo4j and several other databases like NoSQL but also relational Databases (ORM). A similar solution is provided by Spring Data Neo4j6 that uses AspectJ for advanced mapping features. The NoSQL database OrientDB also comes with a type-safe property-graph model that is ensured by the database itself 7 . The framework Structr8 provides a Graph-Database and an Object Schema, but is aimed mostly at enterprise data management and comes with graphical editing tools. To the best of our knowledge there is no OGM that supports graph-query results, hyper-graphs and multiple-inheritance at our time of development.

Neo4j and Scala

We picked Neo4j as it is the graph database that outperforms many of its competitors [START_REF] Beis | Benchmarking graph databases on the problem of community detection[END_REF][START_REF] Jouili | An empirical comparison of graph databases[END_REF]. Neo4j can be used as an embedded database or over the network via a REST API. In the embedded case the data is stored in the file system and is accessed by using Neo4j as a library. This allows to work imperatively with the complete graph to traverse and modify nodes as well as relations or to declaratively query data with the Cypher query language. The REST API provides access to nodes and relations via REST calls or Cypher queries.

Traditional relational databases have table data structures and the queries always result in a table form. Query results coming from the Neo4j REST API can be graphs and tables. At the time of development, the existing Scala Neo4j REST libraries imitated ORMs (Object Relational Mapper) and were therefore limited to list or table structures of nodes and relations. This is neither convenient to work with nor does it fit the purpose of a graph database, especially when using hypergraph data structures.

Our Contribution

We present the framework renesca for handling graph database query results using a new paradigm. With renesca, the result data structure can be a graph instead of a table. Changes to the data can be cumulatively applied (c.f. Unit of Work [START_REF] Fowler | Patterns of enterprise application architecture[END_REF]).

On top of this paradigm we present the framework and DSL renesca-magic for describing graph database schemata. The DSL is implemented with Scala macros which generate code for using renesca in a type-safe way. This allows to interpret graph results with regards to a schema (see Fig. 1). Furthermore, the framework allows to realize hyperrelations, which means connecting relations with nodes.

The whole renesca framework (i.e. renesca and renesca-magic) is implemented in Scala as a lightweight (approx. 3,200 LOC + 6,500 LOC tests) OGM which can be used as two separate libraries. Renesca provides the query interface to the Neo4j REST API. It manages submission of prepared statements and returns the results in appropriate data structures. The data is handled using the following concepts:

Treat Query Results as Graphs instead of Tables

Like the embedded version of Neo4j, with renesca it is possible to query a subgraph from the database and get the result as a graph or table data structure. The graph can be traversed like a Scala collection and properties are represented as hashmaps on nodes and relations. The property values can be casted to the expected type. The resulting graph consists of three classes: Node, Relation(startNode, endNode) and Graph(nodes, relations).

Track Changes and Persist Later as One Unit of Work

When modifying, creating and deleting nodes as well as connecting them with relationships, it is very expensive to submit a REST request for each change. In renesca we track changes and apply all of them at once when persisting the whole graph, with as few queries as possible. This takes fewer REST requests and leaves room for optimization. Changes to properties are also tracked and persisted. This approach allows to pass around the graph structure in the code and after all changes have been applied, persist once. // access the graph like scala collections val snake = graph . nodes . find ( _ . properties ( " name " ) . asInstanceOf [ StringPropertyValue ] == " snake " ) . get // useful methods to access the graph ( requires implicit val graph in scope )

Example Code

// e . g .: neighbours , successors , predecessors , inDegree , outDegree , degree , ... val name = snake . neighbours . head . properties ( " name " ) . asInstanceOf [ StringPropertyValue ]. value println ( " Name of snake neighbour : " + name ) // prints " dog " // changes to the graph are tracked snake . labels += " REPTILE " snake . properties ( " hungry " ) = true // creating a local Node // ( a Node the database does not know about yet ) val hippo = Node . create // changes to locally created Nodes are also tracked hippo . labels += " ANIMAL " hippo . properties ( " name " ) = " hippo " // add the created node to the Node Set graph . nodes += hippo // create a new local relation // from a locally created Node to an existing Node graph . relations += Relation . create ( snake , " EATS " , hippo ) // persist all tracked changes to the database // and commit the transaction tx . commit . persistChanges ( graph )

The Graph-Object Impedance Mismatch

The renesca framework provides graph query results which return object-graphs that can be worked with procedurally. Usually, entities in the business logic of an application directly correspond to records in the database -these are nodes in the context of graph databases. The abstraction layer renesca-magic generates boilerplate code for Node, Relation and Hyperrelation objects using a high level Scala DSL. This wraps the pure data-graph in an object-graph.

The renesca-magic Abstraction Layer

When only working with renesca, it is natural to write wrappers for specific nodes that correspond to objects, as these objects always have specific properties. So, instead of looking up in the property hashmap and casting every time, we write a wrapper class which implements typed getters and setters for the needed properties. Relations between objects can be implemented by wrapping the graph traversal with an appropriate getter. Therefore, we extended renesca with simple schema helpers to wrap nodes, relations and graphs.

For large models it can be very error prone to change the model and therefore refactor the boilerplate code. This issue leads to the idea of generating the boilerplate based on a compactly described model. The code generator is implemented as a set of Scala macros which transform a class-based ER-model DSL to work with the graph database in a type safe way.

Scala macros are hygienic macros and therefore work on abstract syntax trees instead of strings of code. The trees which are read from the schema definition are transformed and directly compiled. The macros analyze the multiple inheritance hierarchies and relation graph of the ER-Model to decide which labels to set on nodes and which getters / setters to generate. This is the heart of renesca-magic. Explaining it here is beyond the scope of this article. The interested reader can examine the code online 9 .

The following subsections explain how renesca-magic transforms the model definition in order to map it to the property-graph model used by the database.

Labels The names of the node and relation definitions are directly translated to labels and relation-types of the property graph model.

Properties Renesca-magic generates wrapper classes and factories for nodes and relations. Both can have properties which can be primitives or optional primitives. The properties can be immutable by writing them with a val and mutable by using a var. Default values can be specified with an assignment of an expression which is evaluated on creation. The classes are generated with getters and setters, taking mutability and optionality into account. The factories provide methods to wrap existing nodes or relations and methods to create new instances with the required properties and the optional ones as default parameters.

Graphs There is a wrapper for the whole graph, which provides access to the different types of nodes and relations contained in the graph. This graph can be persisted like the graph from renesca.

Relations and Neighbors

The wrapper for relations takes two additional parameters. The start node and the end node of the directed relation. This triggers the generation of accessors in the start node and end node wrappers to access neighbors over this relation in both directions.

Multiple Inheritance When using the same property over and over again on different types of nodes it makes sense to define it only once in a trait and compose it into all the needed nodes by inheritance 10 . This helps to keep the schema definition DRY (Don't repeat yourself). The name of the trait is added to the list of labels. Like in OOP (Object oriented programming), all children of the trait can be handled as the same type. This allows to work with collections of nodes sharing the same properties. There are also traits for relations with the same functionality. Hyperrelations Hyperedges in mathematical terms are edges which connect an arbitrary set of vertices. In renesca-magic we define Hyperrelations as relations which get all characteristics of a node. They can be used as a drop-in replacement for nodes and relations. Hyperrelations can therefore connect two nodes and be connected with other nodes (see Figure 2). So this is a specialized form of the mathematical definition. Internally in the generated code they are represented by a node with an incoming and outgoing relation.

Example Boilerplate Code

Since these benefits are hard to imagine without examples we demonstrate the benefits of using renesca-magic in a short artificial example (see Listing 1.7 in the appendix). We want to have a simple two node-type graph with one relationship.

A class Animal has a relationship Eats with a class Food. Each class has getter and setters to access its neighbors and its properties. We omitted any comments in the generated code to not blow up the code unintentionally, yet we get 50 lines of boilerplate. The amount of boilerplate needed to represent and access such a simple relationship is far too large. Using a Scala-Macro we can reduce the 50 lines of code to a mere 13 lines of code -including comments (see Listing 1.2). This short example also shows how to use properties that are immutable (using val ) and mutable (using var ). Accessing this graph is now equally simple (see Listing 1.3).

Listing 1.3. Creation of objects and changing properties val snake = Animal . create ( " snake " ) val cake = Food . create ( name = " cake " , amount = 1000) val eats = Eats . create ( snake , cake ) cake . amount -= 100

Additional Features Provided by renesca-magic

Wrapping induced subgraphs The framework renesca-magic supports wrapping of induced subgraphs from a schema. By using such a wrapper (i.e. by using graph) renesca-magic automatically generates accessors for each node and relation. This comes with the benefit of traversing an induced sub-graph with methods of the object itself. In our example (see Listing 1.4) we can see that the relations between specified nodes will be induced. FOOD ) RETURN a ,e , f " ) ) val elefant = Animal . create ( " elefant " ) val pizza = Food . create ( name = " pizza " , amount = 2) zoo . add ( Eats . create ( elefant , pizza ) ) zoo . animals // provides Set ( elefant ) zoo . relations // provides Set ( elefant eats pizza ) db . persistChanges ( zoo )

Traits and Relations to Traits

Since Scala allows for multiple inheritance using traits, we can map our relations to traits instead of classes. This allows for polymorphic relations between nodes that share common traits (see Listing 1.5, line 15).

Hyperrelations

We can use hypergraphs in renesca-magic by masquerading a node as a hyperrelation (see Fig. 2). In our example (see Listing 1.6, line 13) we model an online document system where articles are annotated with tags. The relation tags relates an article and a tag. The relation itself can now be in a relation supports, which can store who is supporting which tagging-action -thus a (tag, taggable)-tuple.

Performance Evaluation

In order to asses the impact of using an additional abstraction layer on top of Neo4j, we measure runtimes of the usage example from the renesca documentation.

In the benchmark example the database already contains two nodes connected by one edge. The example consists of two transactions. In the first transaction we query both nodes and set an additional label and property on one of them. Then we create another node and connect it to the previously modified node. In the second transaction we query one node and add a property. The first trial uses change tracking provided by the renesca library, while the native implementation uses explicit Cypher-Queries to do the same reads and modifications to the database 11 .

Method

We run both implementations 2000 times on the same hardware with a local Neo4J 3.0.3 instance. We measure runtime and compare results using a Welch unpaired sample test. We report results using 95% confidence interval and testresult against a significance level of α = .05. This means that we have a 95% chance of missing an existing difference in our sample. Since runtime data is often not normally distributed, we also apply BCa bootstrapping to verify our test results. After 2000 trials we could not detect a significant difference (see Fig. 3) in performance using a Welch two-sample test comparing means in required time (t(3683.2) = -0.09142, p = .9272, n.s.). Renesca has an average runtime of M R = 0.02894985s (SD R = 0.0165216S), while the native implementation has a mean runtime of M N = 0.02900663s (SD N = 0.02232678s).

Results

The bootstrapped results confirm our results, even for our heavily skewed sample (i.e. long-tail distribution). Uncertainty only shifts to longer times.

Discussion

We evaluate our frameworks with very simplistic means, to ensure no dramatic overhead is generated from them. We can show that no meaningful overhead comes from using renesca in our examples. This benchmark is by far not extensive, yet only explorative in nature. But it is necessary to keep in mind that for any given abstraction layer a benchmark can be generated that brings the benefits of the layer to a halt. Direct API access is always faster than through any abstraction layer. The benefits are more sought in clever optimization (i.e. removing redundant operations on higher levels of abstraction), maintainability and increases in developing speed. The trade-off on different aspects in efficiency (runtime vs. development) must be balanced to attain an effective abstraction layer.

Fields of Application

We see potential of using renesca in applications with complex data models which are not easily represented with ORMs. For example:

cliques of Entities where each entity can be related to any other entity in the clique. This usually results in an quadratic amount of N:M relations in relational models. -Relations to other Relations (Hyperrelations) These examples describe advantages of graph databases in contrast to relational databases in general. They are not limited to renesca-magic, but the boilerplate generation allows to handle them with the same usability as ORMs for relational databases.

Argument Mapping Systems

Using all the features of renesca we implemented a real-life online discussion system that relies on a hypergraph-based data structure to organize its data. The system uses tags (similar as in Listing 6) to organize tagging and voting. The db-schema required to write 266 lines of code (LOC) including comments. Using renesca-magic it generated 2,739 LOC of boilerplate code without comments. This shows that we can reduce code size to a tenth using renesca-magic.

Conclusions and Future Work

In this paper we introduced two frameworks that improve the usability of the Neo4j database with Scala. The framework renesca implements access to the REST API of Neo4j and is the foundation of renesca-magic. The latter implements macros that allow object-graph-mapping (OGM). The amount of written code can be reduced by factor of 10. This improves both maintainability and extensibility. It also improves code-readability and facilitates Scala's power to use multiple inheritance.

Since cypher queries are not type safe, queries can create and retrieve data that does not match an existing object model. This is a source of common pitfalls for developers. Adding a query-parser that ensures type-safety in the query language at compile time could alleviate this burden off the user. At this time of writing Neo4j 3.0.0 is already released. It brings a high performance binary protocol called Bolt as an alternative to the REST API to access the database over a network. We plan to integrate this binary protocol into renesca to reduce the protocol overhead. We also plan to evaluate renesca using the methodology presented by Jouili and Vansteenberghe [START_REF] Jouili | An empirical comparison of graph databases[END_REF]. Naturally using an OGM will increase processing time, but determining under which circumstance this plays a role must be identified.

Fig. 1 .

 1 Fig.1. The renesca-framework uses two libraries: renesca is an abstraction layer that allows to handle graphs over the REST-API of Neo4j. Changes can be done locally and persistence can be deferred as a Unit of Work. renesca-magic is a type-safe wrapper for the low-level property-graph model of Neo4j.

Listing 1 . 1 .

 11 Usage example of renesca // establishing the database connection is left out in this example db . query ( " CREATE (: ANIMAL { name : ' snake '}) -[: EATS ] ->(: ANIMAL { name : ' dog '}) " ) val tx = db . newTransaction // query a subgraph from the database implicit val graph = tx . queryGraph ( " MATCH ( n : ANIMAL ) -[ r ] ->() RETURN n , r " )

Fig. 2 .

 2 Fig. 2. left: A regular graph connects two nodes (N) using a relation (R). right: A hypergraph allows for hyperrelations (H) which can be connected to a Node (N) itself by a regular relation (R). (H) and (R) together form a hyperedge in mathematical terms.

Listing 1 . 2 . 5 /

 125 Macro code for our example (Animal)-[eats]->(Food) 1 import renesca . schema . macros @ macros . GraphSchema object Exam pleSch emaWr apping { / Nodes get their class name as uppercase label @ Node class Animal { val name : String } @ Node class Food { val name : String var amount : Long } // Relations get their class name as uppercase relationType @ Relation class Eats ( startNode : Animal , endNode : Food ) }

Listing 1 . 4 .

 14 Wrapping an induced subgraph import renesca . schema . macros @ macros . GraphSchema object Exam pleSch emaSu bgraph { @ Node class Animal { val name : String } @ Node class Food { val name : String var amount : Long } @ Relation class Eats ( startNode : Animal , endNode : Food ) // Subgraph induction @ Graph trait Zoo { Nodes ( Animal , Food ) } } // Usage begins here import Exam pleSch emaSu bgraph . _ val zoo = Zoo ( db . queryGraph ( " MATCH ( a : ANIMAL ) -[ e : EATS ] ->( f :

Listing 1 . 5 .

 15 Multiple inheritance using traits @ macros . GraphSchema object ExampleSchemaTraits { // Inheriting Nodes receive their name as additional label @ Node trait Animal { val name : String } // Node with labels FISH and ANIMAL @ Node class Fish extends Animal @ Node class Dog extends Animal @ Relation trait Consumes { val funny : Boolean } // Relations can connect Node traits // instead of defining separate relations // for Fish and Dog explicitly @ Relation class Eats ( startNode : Animal , endNode : Animal ) extends Consumes @ Relation class Drinks ( startNode : Animal , endNode : Animal ) extends Consumes // Zoo contains all Animals ( Animal expands to child nodes ) @ Graph trait Zoo { Nodes ( Animal ) } }

Listing 1 . 6 .

 16 Multiple inheritance using traits @ macros . GraphSchema object E x a m p l e S c h e m a H y p e r R e l a t i o n s { @ Node trait Uuid { val uuid : String = java . util . UUID . randomUUID . toString } @ Node trait Taggable @ Node class Tag extends Uuid { val name : String } @ Node class User extends Uuid { val name : String } @ Node class Article extends Uuid with Taggable { val content : String } // A HyperRelation is a node representing a relation : // ( n ) -[] ->( hyperRelation ) -[] ->( m ) // It behaves like node and relation at the same time // and therefore can extend node and relation traits @ HyperRelation class TaggingAction ( startNode : Tag , endNode : Taggable ) extends Uuid // Because these are nodes , we can connect a HyperRelation with another Node @ Relation class Supports ( startNode : User , endNode : TaggingAction ) }

Fig. 3 .

 3 Fig. 3. Performance evaluation of renesca against a native implementation. Error bars denote 95% confidence intervals. The left image shows means and CI, the right image shows bootstrapped means and CIs with 10,000 BCa[12] replications.

https://neo4j.com/docs/ogm-manual/current/

http://hibernate.org/ogm/

http://projects.spring.io/spring-data-neo4j/

http://orientdb.com/docs/last/Schema.html

https://structr.org

https://github.com/renesca/renesca-magic

Acknowledgments

We would like to thank the anonymous reviewers for their constructive comments on an earlier version of this manuscript. The authors thank the German Research Council DFG for the friendly support of the research in the excellence cluster "Integrative Production Technology in High Wage Countries".


Francesco Buccafurri

Gianluca Lax
email: lax@unirc.it

Serena Nicolazzo
email: s.nicolazzo@unirc.it

Antonino Nocera
email: a.nocera@unirc.it

A threat to friendship privacy in Facebook

Keywords: Facebook privacy, assortativity, identity management

scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Facebook's privacy setting gives a user the possibility to choose who is allowed to see their profile information. Hence, a user who wants not to reveal his friend list information to everyone can specify to hide such an information in the privacy setting page. By default, everyone can see the friends of a user. As a matter of fact, there are many Facebook users having a private list of friends, meaning that this information is often (reasonably) perceived as sensible. In this paper, we study the robustness of this privacy protection feature, showing that it can be broken even in the less advantageous conditions for the adversary. Obviously, if the adversary knows the victim in the real life or has information about the contexts in which the victim lives, he can easily guess some Facebook profiles owned by a real-life friend of the victim whose friend list is public. It is rather intuitive that only few seeds are enough to discover incrementally large portions of private friends, as usually friends form highly connected clusters. Therefore, this case is trivial. But we want to consider the most difficult case. The adversary has only the name of the victim and the link to his Facebook profile, he can guess only some general information about him (nationality, for example), but has no information about his real life, his job, his interests, etc. This case, for example, may occur in Web investigation. Again, the privacy of the list of friends can be broken once only a few friends (even one) is found with public profile. But, how to find them? Since guessable general information selects a very large portion of Facebook users, it would seem that the only way for the adversary is to try an infeasible guess-and-check attack. In this paper, we show that, by exploiting a social network property recently demonstrated for Twitter [START_REF] Buccafurri | Interest assortativity in twitter[END_REF], a much more efficient attack is possible, allowing the adversary to break the privacy of the victim in the most cases. This short paper includes the first experimental evidence of this result, thus encouraging us to more deeply analyze this issue in the next future.

The plan of this paper is as follows. In section 2, we present our approach to discover private friendships in Facebook. Section 3 describes the preliminary experimentation carried out to study the effectiveness of our technique. Section 4 deals with literature related to our work. Finally, in Section 5, we draw our conclusions.

Approach formalization

In this section, we describe the technique we propose to discover (at least a part of) friends of a social network user who decided to make private his friend list. First, we observe that our approach works for social networks, such as Facebook, in which friendship relations are symmetric (that is, if the user u 1 is friend of u 2 , then also u 2 is friend of u 1 ).

The intuition underlying our approach is that privacy setting of an account is indicated by the account owner, meaning that u 1 can choose to make private his friendship with u 2 , whereas u 2 can choose to make public his friendship with u 1 . Consequently, by looking at u 2 's account, the friendship between u 1 and u 2 can be inferred even thought u 1 tries to hide it. It is worth noting that the mere execution of the strategy sketched above has a strong limitation that makes this trivial search unfeasible. Indeed, due to the huge number of social network accounts, the search space of possible friends is limitless. Moreover, this strategy returns at most one friend for each possible friend analyzed.

To overcome these drawbacks, we designed a technique more sophisticated than the above one to reach two important advantages. The first one is to provide a relatively limited number of accounts to analyze (say candidates), thus reducing the search space and making this solution feasible. The second advantage is that, thanks to a suitable selection of each candidate, the processing of each candidate account is able to return more friends of the initial account u 1 (to obtain this, we exploit the mechanism of friend community present in social networks).

The technique used to discover private friends basically relies on three procedures, find alter accounts, select candidates, and find common friends. For the sake of presentation, we describe at high level how our proposal works, whereas the detailed implementations of the above three procedures are provided in Sections 2.1, 2.2, and 2.3, respectively.

The input of our technique is u F , which is the account of the user u in a social network F that supports symmetric friendship relations. In the follow, we instantiate F with Facebook, the most popular social network. Clearly, the friend list of u F is private. The output of our technique is a set of accounts f i u F that are friends of u F in Facebook. Our approach is schematized in Figure 1 and consists of 4 steps.

1. In order to discover private friends of u F , the first step we run is finding alter accounts of u F . This step aims to identify a secondary account of u in another social network (how to perform this task is described in Section 2.1).

It is well know that users register account on different social networks and use them for different purposes [START_REF] Buccafurri | Comparing twitter and facebook user behavior: privacy and other aspects[END_REF][START_REF] Jain | @ i seek'fb. me': Identifying users across multiple online social networks[END_REF]. Among all the social networks in which u has registered an account, we are interested in his secondary account in Twitter: indeed, Twitter is a very famous and common social networks, which is used to exchange very short messages. At the end of this step, we obtain u T , which is the account of the user u in Twitter. 2. Now, we run the second step of our technique, that is select candidates. This steps aims to identify Twitter accounts that are in the same community of u and that can lead to discover the private friends of u F . Among the three steps, this is the core one and is deeply explained in Section 2.2. Let c T 1 , . . . , c T n be the set of candidates outputted at this step. 3. In this step, we run the procedure finding alter accounts for each candidate c T j , in order to discover his/her account on Facebook, say c F j . At the end of this step, we have found some accounts on Facebook that hopefully are in the same Facebook community of u F (because they are alter accounts of users in the same community of u in Twitter). 4. In the last step, for each c F j , we run the procedure finding common friends in order to find the list of friends in common between c F j and u F . This procedure, which can appear magic, is instead provided by many social networks in order to give members the opportunity to find new friends. The detail on the implementation of this step is given in Section 2.3 At the end of this step, we obtain the set f i u F containing some (hopefully all) private friends of u F .

From the high-level description of how our technique works, it is clear we cannot guarantee that this approach is always able to break the privateness of friend list: indeed, it is necessary that alter accounts are found and friend community exists. However, as we will show in Section 3, we experimented that for many real-life accounts, the execution of this technique is able to discover at least a portion of private friend list.

In the next sections, we will describe the implementation of the three procedures used in our technique.

Finding alter accounts

Many social networks provide their users with the possibility to add in their own profiles a link toward one of their accounts in another social site or external website. This feature is typically enabled during the creation of the user profile. This information is extremely useful in our approach because it allows the identification of the accounts belonging to the same person in a multi-social network scenario.

Technically speaking, users who explicitly declare their alter accounts via social network tools, physically create special links among social networks. These special links are referred as me edges [START_REF] Gyongyi | Social affinity on the web[END_REF][START_REF] Buccafurri | A model to support design and development of multiple-social-network applications[END_REF]. Information about these inter-social network links can be extracted in several ways. The basic strategy leverages the use of social network APIs, a set of methods and services, typically available for social network developers, allowing the interaction with social-network data and functionalities to create new software on top of them.

However, not all social networks provides APIs to extract this information. Therefore, another possibility to extract alter accounts relies on the XFN (XHTML Friends Network) standard, an HTML microformat to represent relationship among user accounts. This is obtained by empowering the set of values that the rel attribute of the HTML tag <a> (which represents a link) can assume. In particular, the value "me" (i.e., rel='me') is used to indicate that the corresponding <a> link represents a me edge.

Finally, in cases in which users do not declare explicitly their alter accounts, several approaches proposed by the scientific community can be applied to detect missing me edges (see, for example, [START_REF] Buccafurri | Discovering links among social networks[END_REF][START_REF] Korula | An efficient reconciliation algorithm for social networks[END_REF][START_REF] Zafarani | Connecting users across social media sites: a behavioralmodeling approach[END_REF][START_REF] Gani | Towards multiple identity detection in social networks[END_REF]).

In summary, alter accounts can be retrieved by using social network APIs, XFN, or techniques such as those defined in [START_REF] Buccafurri | Discovering links among social networks[END_REF][START_REF] Korula | An efficient reconciliation algorithm for social networks[END_REF][START_REF] Zafarani | Connecting users across social media sites: a behavioralmodeling approach[END_REF][START_REF] Gani | Towards multiple identity detection in social networks[END_REF]. Observe that, in the case of Facebook and Twitter, XFN is adopted for declaring alter accounts.

Selecting Candidates

The approach we follow to obtain the set of candidates leverages the concept of assortativity in social networks. Assortativity is an empirical measure describing a positive correlation in personal attributes of people socially connected with each other [START_REF] Newman | Assortative mixing in networks[END_REF]. Hence, if a network is assortative with respect to a given attribute, it means that the majority of its users tend to act as their friends when it comes of the aspect expressed by that particular attribute.

It is proved that Twitter shows assortative behavior with respect to user interests [START_REF] Buccafurri | A new form of assortativity in online social networks[END_REF], where interest assortativity is defined as the preference for friends to share the same interest (e.g., sport, music). Indeed, in Twitter there exist accounts belonging to public figures, which, due to their influence w.r.t. a specific topic, act as a sort of representative for that topic [START_REF] Cha | Measuring user influence in twitter: The million follower fallacy[END_REF]. This way, the abstract concept of interest (or topic) can be mapped to the concrete entity of a public figure.

Assortativity w.r.t. an interest I, say IA I , is given by the difference between the fraction of the users interested in I having at least one friend interested in I measure in the real network, and that computed in the random graph corresponding to the real network, said null model [START_REF] Newman | Assortative mixing in networks[END_REF]. Indeed, the random graph models the case in which no assortativity occurs and is obtained by preserving the nodes of the social network and replacing the deterministic occurrence of edges by a random variable in such a way that node degree distribution is unaltered. More in details, the fraction referred above has as numerator the number of nodes that: (1) follow a public figure associated with the interest I and (2) have at least a friend who is follower of any other public figure representative of I; the denominator is the total number of nodes following any public figures associated with I.

Thanks to the assortative behavior of Twitter users, we can find people belonging to his clique by searching on the neighbors of a public figure of interest for a given user, obtaining a set of suitable candidates for our technique.

Finding common friends

By following the reasoning described in Section 2.2, we can extract a set of Twitter accounts, which are potentially "close" to the user, say u, for whom we want to reconstruct the friend list. Now, for each of the candidates obtained we can adopt the strategy described in Section 2.1 to find their alter-accounts in Facebook, thus obtaining a set of Facebook-candidate accounts.

At this point, if these candidates have a public friend list, we can verify whether u is present in any of these lists. Each time we find an account in any of these lists, due to the bidirectional nature of Facebook friendships, we have discovered an element of the friend list of u. Because the set of candidates may be very big, it is very likely that we can reconstruct the entire friend list of u. However, this strategy would require a very large number of checks to verify the membership of u in any of the friend list of the candidates.

Fortunately, Facebook provides a very powerfull set of APIs, namely Graph API [START_REF]Facebook Graph API Documentation[END_REF], that can give us some advantages in our objective. Graph APIs are a low-level HTTP-based APIs useful to retrieve data from Facebook.

Specifically, it is possible to discover the mutual friends between two Facebook users by performing an HTTPS request at the following link: https://www.facebook.com/friendship/<screen-name1>/<screen-name2>

where the parameters <screen-name1> and <screen-name2> represent the string ids used to univocally identify the two users in Facebook. Interestingly, this API method works also if one of the two accounts (that of u in our case) has the friend list private. Due to the tendency of Facebook users to form cliques [START_REF] Van Cleemput | Friendship type, clique formation and the everyday use of communication technologies in a peer group: A social network analysis[END_REF] the above API method allows us to discover a very large set of items of the friend list of u with a single call. This reduces the number of operations required to reconstruct the entire friend list.

Preliminary evaluation

Our experiments were performed on a machine equipped with a 2 Quad-Core E5440 processor and 16 GB of RAM. The operating system was Linux Ubuntu Server 14.04.4 LTS, with kernel version 4.2.0-35, Java Virtual Machine version 1.8.0 45 (64-Bit) and Twitter4J [2] as external library for Twitter API support. We wrote our implementations in Java.

To obtain the initial set of Facebook profiles to test our approach performance, we could not rely on existing datasets as they do not provide information about me edges. To extract necessary data, we exploited the SNAKE system [START_REF] Buccafurri | A system for extracting structural information from social network accounts[END_REF] which allows the extraction of profile contact information from a very large set of social networks. One of the main issues in this activity was the detection of the profiles showing the right features for our investigation (i.e., an alter account in Twitter and a private friend list). However, using one of the classical crawling technique [START_REF] Rao | The visit problem: visibility graph-based solution[END_REF] is not suitable for two main reasons:

1. First, the percentage of accounts with a me edge is very low [START_REF] Buccafurri | Moving from social networks to social internetworking scenarios: The crawling perspective[END_REF], so it is extremely difficult to find these particular users. This implies that an almost complete visit should be performed to obtain necessary information. However, full structural information of the network is not needed, because we are interested only in Facebook users with an alter account in Twitter. 2. Secondly, a crawling technique may privilege the visit of some nodes with particular structural properties (i.e., very high degree) introducing some biases in our results.

As a consequence, we decided to perform uniform sampling. Although, uniform sampling is not a trivial task in general, for Facebook and Twitter, it is facilitated by how user identifiers are organized. Indeed, both social networks adopt 64-bit identifiers for user accounts. However, because we are looking for private Facebook accounts, we cannot start our sampling from Facebook. We started by uniformly sampling Twitter to collect accounts having a me edge towards Facebook 1 . In particular, the URL address of the profile page of Twitter has the following structure: http://twitter.com/account/ redirect_by_id?id=xxx , where xxx is a 64-bit positive integer. Hence, to obtain a uniform sampling, we generated numbers uniformly at random in a suitable interval and then we checked if it corresponds to a real account with a me edge towards Facebook and whose alter account in Facebook has a private friend list. From this sampling step we obtained a set of 355 accounts.

We proceeded by analyzing the set of Twitter friends for each of the accounts above, and we selected public figures among them. In our case, because the set of candidates (see Section 2) is a subset of followers of these public figures, we neglected those public figures who have a too high in-degree and considered only accounts with an in-degree ranging from 500 to 1500. Clearly, this choice was made only to guarantee computation feasibility, and did not affect the performance of our technique as will be shown in the following.

After this, we considered the Facebook alter accounts of the candidates, extracted in the previous step, and continued by calling the Graph API method described in Section 2.3 to verify whether we were able to reconstruct the private friend list of the original set of 355 users. As a result, we succeeded in 259 cases, thus obtaining a probability of success of 0.73.

Related Work

The more social networks take a central role in people everyday life, the more users privacy becomes a critical issue for researchers. As stated in [START_REF] Bartsch | Control your facebook: An analysis of online privacy literacy[END_REF], although a considerable part of Facebook users are not aware of privacy options or do not use them, there is an always increasing number of active users having more online privacy literacy. Indeed, a number of studies [START_REF] Liu | Analyzing facebook privacy settings: user expectations vs. reality[END_REF][START_REF] Hargittai | Facebook privacy settings: Who cares? First Monday[END_REF][START_REF] Child | Fuzzy facebook privacy boundaries: Exploring mediated lurking, vague-booking, and facebook privacy management[END_REF][START_REF] Hofstra | Understanding the privacy behavior of adolescents on facebook: The role of peers, popularity and trust[END_REF][START_REF] Beldad | Sealing one's online wall off from outsiders: Determinants of the use of facebook's privacy settings among young dutch users[END_REF][START_REF] Debatin | Facebook and online privacy: Attitudes, behaviors, and unintended consequences[END_REF] analyse users behaviour when it comes of privacy in social networks. In particular, the authors of [START_REF] Liu | Analyzing facebook privacy settings: user expectations vs. reality[END_REF] measure the disparity between what users desire and their actual privacy settings, and perform an analysis of problems emerging from a not proper management of privacy. They found that privacy settings match users' expectations only in 37% of the time, exposing content to more users than expected. Hargittai et. al [START_REF] Hargittai | Facebook privacy settings: Who cares? First Monday[END_REF] examine how users privacy practices have changed over time according to modifications on Facebook privacy settings. However, concerning the problem faced in this paper, no change of privacy setting can affect neither the issue nor the solution. The study presented in [START_REF] Child | Fuzzy facebook privacy boundaries: Exploring mediated lurking, vague-booking, and facebook privacy management[END_REF] aims at exploring relationships between concern about mediated lurking and strategic ambiguity on Facebook, and Facebook privacy management. Moreover, the authors of [START_REF] Hofstra | Understanding the privacy behavior of adolescents on facebook: The role of peers, popularity and trust[END_REF] and [START_REF] Beldad | Sealing one's online wall off from outsiders: Determinants of the use of facebook's privacy settings among young dutch users[END_REF] focus on privacy settings of adolescents on Facebook. As explained in [START_REF] Christofides | Risky disclosures on facebook the effect of having a bad experience on online behavior[END_REF] unintentional disclosure to friends and acquaintances on Facebook can led to bullying/ meanness and unwanted contacts, especially among adolescents. Other work surveys users' awareness, attitudes, and privacy concerns towards profile visibility and show that only a minority of users change the default privacy preferences on Facebook [START_REF] Acquisti | Imagined communities: Awareness, information sharing, and privacy on the facebook[END_REF][START_REF] Gross | Information revelation and privacy in online social networks[END_REF].

From Facebook birth, privacy flaws have continued to keep appearing. For instance, in 2006 Facebook introduced a new functionality, called "News Feed", which tracks and displays the online activities of a user's friends on start pages of the user. Although none of the individual actions were private, users felt deprived of their sense of control over their information and began to form protest groups on Facebook [START_REF] Boyd | Facebook\'s privacy trainwreck[END_REF]. Subsequently, Facebook introduced privacy controls that allowed users to determine what was shown on the news feed and to whom.

The information gained can be exploited for a number of reasons [START_REF] Gross | Information revelation and privacy in online social networks[END_REF][START_REF] Jagatic | Social phishing[END_REF]. An attacker could, for instance, deduce social security numbers (which are often derived from name, gender, and date of birth) from the information posted on the user profiles [START_REF] Gross | Information revelation and privacy in online social networks[END_REF][START_REF] Buccafurri | Implementing disposable credit card numbers by mobile phones[END_REF]. Moreover, data on relationships or common interests in groups can be exploited for phishing [START_REF] Jagatic | Social phishing[END_REF].

In order to mitigate privacy threats, authors of [START_REF] Ghazinour | Yourprivacyprotector, a recommender system for privacy settings in social networks[END_REF] propose a recommender system that suggests privacy settings automatically learned for a given profile (cluster) of users. Whereas, in [START_REF] Young | Privacy protection strategies on facebook: The internet privacy paradox revisited[END_REF] the authors investigate what strategies undergraduate students have developed in addition to the use of the default privacy settings, to protect their privacy on Facebook. These are excluding contact information, using the limited profile option, untagging and removing photographs, and limiting friendship requests from strangers.

Despite these attempts and in addition to the low level of users privacy awareness, there exist more complex ways to bypass privacy setting on Facebook. Indeed, our work shows how, leveraging Twitter data, a user can discover the private Facebook friend list of a victim. This combined use of multi-social network resources adds further privacy concerns to the above literature.

Conclusion

Although a considerable part of Facebook users is not aware of privacy options or do not use them, there is an always increasing number of active users who decide to protect their personal information by restricting the access to their profile. One of the most sensitive profile information is the friend list. In this paper, we described a possible attack on the privateness of the list of friends.

For this purpose, we started by the observation that if the adversary has information about the contexts in which the victim lives, he can easily guess some Facebook profiles owned by the victim real-life friends, and from them reconstruct some portions of the victim friend list (as usually friends form highly connected clusters).

Therefore, our attention moved toward the most difficult case: The adversary knows the minimum information that is only the name of the victim and his Facebook profile. In this scenario, it would seem that the only way for the adversary is to try an infeasible guess-and-check attack. In this paper, we showed that, a much more efficient strategy is possible, allowing the adversary to bypass Facebook privacy settings and break the privacy of the victim in most cases. Our attack exploits the concept of alter accounts combined with a recently studied property, named interest assortativity.

Starting from the victim Facebook profile, we first identify his alter account on Twitter (if any), and then, thanks to interest assortativity, we are able to select some suitable candidates that can lead to some public friends in common with the victim, thus breaking his privacy. The attack incrementally proceeds, by discovering the most of private friends.

This short paper includes the first experimental evidence of this result, thus encouraging us to more deeply analyze this issue in the next future.

Fig. 1 .

 1 Fig. 1. Graphical representation of the approach.

Observe that, the direction of the me edge is not relevant for our objective, because we only need to know that the two accounts belong the same person.

Acknowledgment

This work has been partially supported by the Program "Programma Operativo Nazionale Ricerca e Competitività" 2007-2013, Distretto Tecnologico CyberSecurity funded by the Italian Ministry of Education, University and Research.