Silvie Levy
email: levy@gmail.com

Ehud Gudes

Sharing-habits based privacy control in social networks

We study users behavior in online social networks (OSN) as a means to preserve privacy. People widely use OSN for a variety of objectives and fields. Each OSN has different characteristics, requirements, and vulnerabilities of the private data shared. Sharing-habits refers to users' patterns of sharing information. These sharing-habits implied by the communication between users and their peers hides a lot of additional private information. Most users are not aware that the sensitive private information they share might leak to unauthorized users. We use several different well-known strategies from graph flows, and the sharing-habits of information flow among OSN users to define efficient and easy to implement algorithms for ensuring privacy preservation with a predefined privacy level.

Introduction

Online Social networks (OSN) are websites enabling users to build connections and relationships among each other. The OSN structure represents social interactions and relationships between entities which are the users of the OSN. Social networks are widely used by members for information sharing with the purpose of reaching as many friends as possible. The shared-information spread, is influenced by human decisions, and users are not fully aware of the possible consequences of their preferences when specifying access rules to their shared data. It is the responsibility of OSN administrators to effectively control the shared information, reduce the risk of information leakage, and constantly evaluate the potential risks of shared-information leakage. Most access rules are defined in terms of the degree of relationship required to access ones data. These rules are not refined enough to allow for dynamic denial of content from certain peers of the community. We propose a model for access control that works with minimal user intervention. The model is based on users' patterns of sharing information denoted as Sharing-habits. Naturally some users are more likely to share information with others. To minimize the probability of information leakage, the social network is analyzed to determine based on these habits, the probability of information flow through network connections. In a graph representation of the network, where edges indicate relationship between users, the challenge is to select the set of edges that should be blocked to prevent leakage of the shared information to unwanted recipients. We review some methods for handling and preserving privacy in social networks, and present our new privacy preserving approach, based on sharing-habits data. Our model combines algorithms that use graph flow methods such as max-flow-min-cut, and contract. Experimental results show the effectiveness of these algorithms in controlling the flow of information sharing to allow sharing with friends while hiding from others. The paper is structured as follows: in the next section we review related work, in section 3 we define the privacy assurance in OSN problem, and in section 4 we present our method for dealing with this problem. We explain our evaluation method and primary results in section 5 and conclude by summarizing our contribution and discussing directions for future work in section 6.

Related Work

There are various types of Online Social Networks, each with different properties. Privacy preservation can be viewed and handled from various aspects. Carmagnola et al [START_REF] Torre | Escaping the big brother: An empirical study on factors influencing identification and information leakage on the web[END_REF] present a research about the factors that help users identification, and information leakage in social networks, based on entity resolution. They conducted a study on the possible factors that make users vulnerable to identification, and of personal information leakage, and the perception of users about privacy related to the spreading of their public data. To find the risk factors, they studied the relations between the user behavior (habits) on OSNs and the probability of users' identification. Kleinberg and Ligett [START_REF] Ligett | Information-sharing in social networks[END_REF] describe the social network as a graph where nodes represent users, and an edge between two nodes indicates that those two users are enemies that do not wish to share information. The problem of information sharing is described as the graph coloring problem, Kleinberg and Ligett [START_REF] Ligett | Information-sharing in social networks[END_REF] analyze the stability of solutions for this problem, and the incentive of users to change the set of partners with whom they are willing to share information. Tassa and Cohen [START_REF] Dror | Anonymization of centralized and distributed social networks by sequential clustering[END_REF], handle the information release problem, and present algorithms to compute an anonymization of the released data to a level of k-anonymity; the algorithm can be used in sequential and distributed environments, while maintaining high utility of the anonymized data. Vatsalan et al [START_REF] Vassilios | A taxonomy of privacypreserving record linkage techniques[END_REF] conducted a survey of privacy-preserving record linkage (PPRL) techniques, with an overview of techniques that allow the linking of databases between organizations while at the same time preserving the privacy of these data. In this paper Vatsalan et al [START_REF] Vassilios | A taxonomy of privacypreserving record linkage techniques[END_REF] present taxonomy of PPRL which characterize the known PPRL techniques along 15 dimensions, highlight shortcomings of current techniques avenues for future research. Jaehong and Ravi [START_REF] Sandhu | Originator control in usage control[END_REF] present the ORIGIN CONTROL access control model where every piece of information is associated with its creator forever. Ranjbar and Maheswaran [START_REF] Maheswaran | Using community structure to control information sharing in online social networks[END_REF], describe the social network as a graph where nodes represent users, and an edge between two nodes indicates that those two users are friends that wish to share information. They present algorithms for defining communities among users, were the information is shared among users within the community, and algorithms for defining a set of users that should be blocked in order to prevent the shared information from reaching the adversaries, and leaking outside the community. In OSN, communities are subsets of users connected to each other; the community members have common interests and high levels of mutual trust, it can be described by a connected graph, where each user is a node in the graph, and an edge connecting two nodes indicates a relationship between two users. A community is defind by Ranjbar and Maheswaran [START_REF] Maheswaran | Using community structure to control information sharing in online social networks[END_REF] from the view point of an individual user. myCommunity is defined as the largest sub-graph of users who are likely to receive and hold the information without leaking. In other words, myCommunity is the subset of an individual users friends that have intense and frequent interactions and describes a grouping abstraction of a set of users that surrounds an individual based on the communication patterns used for information sharing. Our study is based on the ideas described in their paper; while they only share information within the defined community, and block users that might leak information to adversaries, we relax the limitation defined in their study, and block only edges on the path to the adversaries, instead of blocking all the information from the source user to the users that might leak the information.

The Privacy Assurance in OSN Problem

In this section we define the general problem of privacy assurance in OSN and our proposed method that uses information from users sharing-habits.

Let G = (V, E) be a directed graph that describes a social network, where V is the set of network's users, and E is the set of directed and weighted edges representing the users' information flow relationships. An edge (u i , u j ) ∈ E exists only if u i shares information with u j . The distance between two vertices,dist G (u i , u j ) is the length of the shortest path from u i to u j in G. Ego is an individual focal node, it is the specific user from which we consider the information flow. A network has as many egos as it has nodes, ego-community is the collection of ego and all nodes to whom ego has a connection at some path length. The δ-community of a user, represented by the ego vertex u i is the sub-graph

G δ (u i )=(V δ (u i ),E δ (i)), where for each v i ∈ V δ (u i ), v i = u i , dist G (u i , v i ) ≤ δ.
The following definitions are as defined by Ranjbar et al. [START_REF] Maheswaran | Using community structure to control information sharing in online social networks[END_REF]: p i is the probability that user u i is willing to share the information with some of his friends.

p i = (outf low/inf low) (outf low < inf low), 1 (outf low ≥ inf low). (1)
-Outflow is the number of sharing interactions from u i to his friends.

-Inflow is the number of sharing interactions from u i s friends to u i .

The likelihood of u i sharing information with u j along the edge (u i , u j ) is represented by w i,j , the weight on the edge (u i , u j ); This weight is derived from the relationship between u i and u j , it is a fixed number indicating the willingness of u i to share information with u j , it does not change or change very infrequently, and may be set by the user. The probability of flow between two neighbor users, u i and u j is denoted as p ij , and calculated by p i,j = p i × w i,j . Since the flow may change quite often this probability may also changes with it. We assume that the user behavior is consistent; user u i shares all the data with user u j with probability p i,j . This probability can change with time, but it does not depend on the content of the shared information. The Probability of Information Flow (P IF ), is the maximum probability of information flow throughout the entire paths between u i and u j . A path probability flow between u i and u j is the flow of the edge with the minimum p i,j . It is denoted as P AT H i,j . The PIF is the maximum among of all paths between u i and u j of P AT H i,j . The function f which denotes flow, is computed by using the log of the edges' probabilities on a path between u i and u j . To prevent information flow from one user to another we search for the minimal set of edges that when removed from the community graph, or blocked, disables the flow. We denote this set of blocked edges as B. Note that after edges are removed, the P IF and therefore f should be recomputed.

Problem goal

Our aim is to enable a user u i to share information with as many friends and acquaintances as possible, while preventing information leakage to adversaries within the user's community. Ranjbar et al. [START_REF] Maheswaran | Using community structure to control information sharing in online social networks[END_REF] describe a method for sharing information within the source user u i defined community, while blocking users (friends and acquaintances) that might leak information to adversaries. We relax the limitation due to blocking friends, and instead of blocking all the information from the source user u i to the users that might leak the information, block only edges on the path from u i to his adversaries. We use the following criteria to define and evaluate the resulting u i ego-community graph:

1. Minimum Friends Information Flow: the minimum information flow from u i to every user within his community must preserve a certain percentage of the original information flow to every user denoted by α.

Let G δ (u i ) = (V δ (u i ), E δ (u i )) be the δ-community of u i , v ∈ V (u i ) f (u i , v) ≥ α • f original (u i , v) (2)
2. Close Friends Distance: Close friends are defined by their distance from

u i . G β (u i ) = (V δ (u i ), E δ (u i )) is the β-community of u i , v ∈ V (u i ), β < δ.
This criteria reflects the requirement that all the users within u i s β-community must receive the entire information from u i , and cannot be blocked. Let B be the set of blocked edges, than

B ⊂ {(u s , u t )|d G δ (u i , u s ) ≥ β, u s , u t , u i ∈ V G δ (u i )} (3)
We assume that there are no adversaries within u i s β-community, otherwise the above condition can never be fulfilled. 3. Maximum Adversaries Information Flow: the maximum information flow from u i to each of his adversaries cannot be more than γ from the original information flow to each adversary.

f (u i , u adv ) ≤ γ • f original (u i , u adv ) (4)
For example the threshold parameters can be: α = 0.9, β = 2, and γ = 0.1. The problem goal is to remove the least number of edges such that the three equations 2,3,4 will be satisfied.

Cuts in graphs

A cut in a graph is a set of edges between two subsets of a graph, one containing u i , and the other containing u i s adversaries, such that when removed, prevents information flow from one subset to the other. A naive algorithm for solving the problem would be an algorithm that finds any cut between the adversaries' set and u i s community, and defines this cut as the blocked edges list. Algorithm 1 is a naive algorithm for blocked users.

The naive algorithm is not suitable for our problem, since it doesn't comply with the (1) Minimum Friends Information Flow, (2) Close Friends Distancecriteria of our problem. Condition (1) requires minimum information flow from u i to all members in u i s community, the naive algorithm doesn't handle this requirement. Condition (2) defines close friends by their distance from u i , the naive algorithm doesn't handle this requirement. While the naive algorithm is not sufficient to our problem, it is important for understanding the theoretical problem defined here.

Algorithm 1 Naive algorithm for blocked users

Input: G = (V, E) a directed graph that describes the social network.

ui the ego user. δ the community distance criteria.

AdversariesList: the list of u i s adversaries. Output: B:the set of blocked edges.

1: set B = ∅ 2: for all uj ∈ V and (uj / ∈ AdversariesList) and (distG(ui, uj) ≤ δ) do 3:

insert uj to V δ (ui) 4: for all uj ∈ AdversariesList do 5:

insert uj to V δ (adversaries) 6: Choose any cut between the community graph, V δ (ui) and the adversaries V δ (adversaries). 7: for all eij ∈ {the cut between V δ (ui) and V δ (adversaries)} do 8:

insert eij to B 9: return B

The Sharing-habits based privacy assurance in OSN Solution

In our solution we propose a model for finding the set of edges that should be blocked in order to achieve maximum information sharing among the community of the information source with minimum information leak. Our model uses two methods for defining candidate sets for blocked edges, along with the evaluation method for choosing the best set to be blocked. Our method consists of two major steps, the first is the initialization step that creates a multi-graph with a super-vertex s 1 containing u i s β-community, this step is described in subsection 4.1. The second step described in sub-section 4.2, uses two methods to find candidates-sets for blocked edges. Algorithm 2 warps these steps to construct the set of edges to be blocked.

Fig. 2: Construct Blocked Edges main building blocks

Figure 2 describes the main building blocks of the algorithm for defining the edges to be removed from u i s δ-community in order to prevent information leakage to u i s adversaries.

Next we detail each one of these building blocks.

Algorithm 2 Construct blocked edges

Input: ui: the ego vertex. G δ (ui) = (V δ (ui), E δ (ui)): u i s δ-community graph. α, γ: Flow thresholds. β: β-community distance.

AdversariesList: the list of u i s adversaries. Output: B:a set with edges to be blocked.

1: M ultiSet function Initialize(ui, G δ (ui), β, AdversariesList) 2: set s1 = {ui} 3: for all (uj ∈ G δ (ui)) and (distG δ (ui, uj) ≤ β) do 4: if (uj / ∈ AdversariesList) then 5:
insert uj to s1 6:

else 7: return ∅ 8: return s1 {----Main----------} 9: s1 =Initialize(ui, G δ (ui), β, AdversariesList) 10: if (s1 = ∅) then 11:
InitialCandidatesSet=CondtructBlockedEdgesCandidates(ui, G δ (ui), s1, AdversariesList, α, γ) 12: B = SelectBestBlockedEdges(InitialCandidatesSet) 13: return B

Initialization

The δ-community of u i s consists of all users u j connected to u i with a path with distance ≤ δ. The β parameter defines the size of the community of close friends. Therefore, a β-community of u i would be a sub-graph contained in δ-community were β ≤ δ, as demonstrated in figure 1. The privacy criteria that is defined in sub-section 3.1 requires that the entire information shared by u i must be shared with u i s close friends [START_REF] Ronald | Introduction to Algorithms[END_REF]. In order to comply with (2), the Initialization step creates a multi-graph with one super-vertex s 1 containing u i and his close friends with distance ≤ β. This step ensures that the algorithm won't define edges for blocking on paths between u i and his close friends, since u i and his close friends are in the same super-vertex,s 1 , see figure 3.

Figure 3(a) describes a δ-community graph for u 0 , with 10 members, δ=3, 4 are close friends with distances=1 (blue vertices), 4 acquaintances (green vertices), and 2 adversaries (red vertices). Figure 3(b) describes the graph after initialization.

Construct Blocked Edges Candidates

We use two methods derived from flow problems, to find the initial candidatesset of edges to be blocked. This candidates-set is a cut between two sets of vertices, one set containing u i , u i s β-community, and some vertices from of u i s δ-community. The other set containing the remaining part of u i s δ-community, and u i s adversaries.

This candidates-set is evaluated to filter out the final candidates-sets by selecting a set that complies with the required privacy criteria. This process is described in section 4.3; the two methods we use for finding the initial candidatessets of edges to be blocked are:

1. Min-Cut: based on Ford-Fulkerson [START_REF] Ford | Maximal flow through a network[END_REF], Max-flow-min-cut algorithm, to find the minimum cut between super-vertex s 1 that contains u i and his close friends, and each of u i s adversaries. This process is described in paragraph 4.2. 2. Contract: based on Karger et al. [START_REF] Karger | A new approach to the minimum cut problem[END_REF], contract algorithm, to find any cut between super-vertex s 1 that contains u i and his close friends, and each of u i s adversaries, .This process is described in subsection 4.2.

Block edges by Min-Cut

Algorithm 3 implements the Sharing-habits privacy assurance based on the maxflow min-cut method by Ford and Fulkerson [START_REF] Ford | Maximal flow through a network[END_REF], and then checks for privacy criteria compliance:

1. Find a minimum cut between super-vertex s 1 and u i s adversaries [START_REF] Ford | Maximal flow through a network[END_REF].

2. Check if the cut complies with the required privacy criteria as defined in sub-section 3.1, and select the final candidates-set. This process is described in section 4.3.

Algorithm 3 Block edges by Min-Cut

Input: ui: the ego vertex. G δ (ui) = (V δ (ui), E δ (ui)): u i s δ-community graph, after the initialization step. α, γ: Flow threshold. AdversariesList: the list of u i s adversaries. Output: B:a set with edges to be blocked.

1: set B = ∅ 2: InitialBlockedEdges= FindMinCut(ui,G δ (ui),AdversariesList) 3: if (InitialBlockedEdges = ∅) then 4:
B=ComputeFinalCandidatesSet(ui,G δ (ui),AdversariesList,InitialBlockedEdges,α, γ) 5: return B

Block edges by Contract

The minimum cut between G β (u i ), and u i s adversaries, found by BlockEdges-ByMinCut algorithm, might not be the optimal solution for our problem, since the edges in this cut may not satisfiy the privacy criteria. Thus, we use the contract algorithm, that finds a variety of other cuts possibly complying with the required privacy criteria. Algorithm 4 implements the Sharing-habits privacy assurance based on the contract method by Karger and Stein [START_REF] Karger | Global min-cuts in rnc, and other ramifications of a simple mincut algorithm[END_REF][START_REF] Karger | A new approach to the minimum cut problem[END_REF]. In each iteration, the contract algorithm finds a different cut between the supervertex containing G β (u i ) and the super-vertex containing u i s adversaries. The contract algorithm repeatedly contract vertices to super-vertices until it gets two super-vertices connected by a set of edges that defines a cut between the two sets of vertices contained in each super-vertex. Algorithm 4 is composed of the following main steps:

1. Find a cut between super-vertex G β (u i ) and u i s adversaries; this step uses the contract algorithm presented [8, 9] 2. Check if the cut complies with the required privacy criteria as defined in sub-section 3.1, and select the final candidates-set. This process is described in 4.3.

Algorithm 4 Block edges by Contract

Input: ui : the source. G δ (ui) = (V δ (ui), E δ (ui)): u i s δ-community graph, after the initialization step. α, γ: Flow thresholds.

AdversariesList: the list of u i s adversaries. Output: B:the set with the blocked edges.

1: set B = ∅ 2: InitialBlockedEdges= ContractFindCut(ui,G δ (ui), AdversariesList) 3: if (InitialBlockedEdges = ∅) then 4:
B=ComputeFinalCandidatesSet(ui,G δ (ui),AdversariesList,InitialBlockedEdges,α, γ) 5: return B Algorithm 5 is called by algorithm 4 to find a cut between two vertices by randomly selecting an edge and contracting the two vertices connected by the selected edge into one super-vertex.

Algorithm 5 ContractFindCut Find a cut in a graph by repeatedly contracting vertices into two super vertices

Input: G δ (ui) = (V δ (ui), E δ (ui)): δ-community multi-graph, after the initialization step.

ui: the source.

AdversariesList: the list of u i s adversaries. Output: CutSet: the resulting cut.

1: set CutSet = ∅ 2: repeat 3:
if (all edges (u, v) are tested) then 4:

return CutSet 5: else 6:

choose an edge (u, v) uniformly at random from E \ testededges 7:

if (u and v don't contain each others' adversaries) then 8:

contract the vertices u and v to a super vertex w 9:

keep parallel edges, remove self loops 10: until (G has only two super-vertices) 11: set CutSet = the edges between the two vertices 12: return CutSet

Compute Final Candidates Set

After selecting the initial candidates-set of edges to be blocked, each method uses algorithm 6 for selecting the final candidates-set of edges that should be removed from u i s δ-community graph. In the first step of the algorithm, we check if by removing the initial-candidates-set of edges from u i s δ-community graph, the remaining δ-community graph for user u i complies with the required privacy criteria. If it doesn't comply with the required privacy criteria, we try to remove edges from the initial blocked candidates-set, and insert them back into u i s δ-community graph, until the remaining community graph complies with the required criteria, or until we tested the entire edges in the initial candidate-set, and couldn't find a set of edges to be blocked. We propose three methods for selecting and removing an edge from the initial candidates-set, and insert the selected edge back to δ-community graph: 1. Randomize: select an edge randomly.

2. Maximum PIF: select the edge with the maximum probability of information flow. 3. Minimum PIF: selecting the edge with the minimum probability of information flow.

Algorithm 6 implements the three methods and algorithm 7 tests the criteria.

Algorithm 6 Compute final candidates-set

Input: ui : the source. Gu i : u i s δ-community multi-graph, after the initialization step.

AdversariesList: the list of u i s adversaries.

InitialBlockedEdges: the list of edges to be blocked. α, γ: Flow thresholds. EdgeM ethod : the method for selecting the next edge for unblocking. Output: BlockedEdges: the final set of edges to be blocked.

Evaluation

In this section we describe the evaluation method we use for the proposed algorithm, and the results we obtained using real data [START_REF] Leskovec | SNAP Datasets: Stanford large network dataset collection[END_REF]. We first demonstrate our methods and the difference between them using a toy community.

Algorithm 7 Compute the required criteria

Input: ui : the source.

Gu i : u i s δ-community multi-graph, after the initialization step.

AdversariesList: the list of u i s adversaries.

BlockedEdges: the list of edges to be removed. α, γ: Flow thresholds. Output: ComplyCriteria: indicator whether the community graph without the blocking-set complies with the required privacy criteria.

1: for all v ∈ Gu i do 2: if (f (ui, v) < α • f original (ui, v)) then 3: return F ALSE 4: for all a adv ∈ AdversariesList do 5: if (f (ui, u adv ) > γ • f original (ui, u adv )) then 6:
return F ALSE 7: return T RU E

Demonstration on a synthetic community

We demonstrate our algorithms on a small graph representing a synthetic community that we built from the example in [START_REF] Ronald | Introduction to Algorithms[END_REF], containing 11 vertices, and 23 edges. We selected community distance δ = 3, close friends distance β = 1, and assigned 2 adversaries. The algorithms were tested with different probabilities of information flow from source user U 0 to the community members. In the following example, Figure 6 describes the synthetic community graph with high probability of information flow on the edges to adversaries. This situation simulates a collision, and it is hard to select α and γ such that we get minimum leakage of information flow to u i s adversaries, and maximum information flow to u 0 s community. The maximum probability of information flow from U 0 to the members of his community graph is depicted in table 1 The Minimum cut found by Min-Cut method is depicted in table 2. If we remove the initial candidates-set edges from u 0 s community graph, the probability of information flow to 7 and 8 will be 0, meaning no flow at all. In the final step of algorithm 6, we try unblocking each edge from the initial candidtes-set, and reach the required privacy criteria, which is computed by algorithm 7; in this example the only edge that improves the PIF to community without increasing the information leakage to u 0 s adversaries is [START_REF] Vassilios | A taxonomy of privacypreserving record linkage techniques[END_REF][START_REF] Ligett | Information-sharing in social networks[END_REF], thus the final candidates-set is {(3, 7)}. In this example we can't define α, and γ with values that comply with the required privacy criteria, which is computed by algorithm 7.

Block edges by Contract method

A Cut found by an iteration of contract method is depicted in table 3.

If we remove the initial candidates-set edges, the probability of information flow to 5, 6, and 8 will be 0, meaning no flow at all. Algorithm 6 tries unblocking each edge from the initial candidtes-set, and reach the required privacy criteria, which is computed by algorithm 7; the final candidates-set is empty, since each edge we unblock not only improves the information flow to u 0 s community, but also increases the information leakage to u 0 s adversaries. It is obvious that when the edges to the adversaries have high probabilities, the max-flow-min-cut methods might not select those edges, and might not find a solution that comply with the required privacy criteria, while the contract method might find the trivial cut that contains only the edges to the adversaries, and thus comply with the required privacy criteria.

Test on SNAP Database

We evaluated our algorithms on the Facebook network data from Stanford Large Network Data-set Collection [START_REF] Leskovec | SNAP Datasets: Stanford large network dataset collection[END_REF]. The SNAP library is being actively developed since 2004 and is organically growing as a result of Stanford research pursuits in analysis of large social and information networks. The website was launched in July 2009. The social network graph describes the Social circles from Facebook (anonymized) and consists 4,039 nodes (users), and 88,234 edges, it describes the Social circles from Facebook (anonymized). We took the structure and relationship from the SNAP database, and assigned random probabilities to the edges in the network graph in the following way. We defined four types of users, the type reflects the user's willing to share information: very high sharing users, medium, sometimes, and very low. For each user in the graph we randomly assigned a type. To conform the edges' probabilities to the users' types, we randomly assigned probabilities to the users' edges according to their types, from the following ranges: very high sharing users (probability 0.75-1), medium (0.5-0.75), sometimes(0.25-0.5), very low (0-0.25). The four types were generated uniformly among all the network users.

Preliminary Results

Tables 4-5 summarize the results of four different evaluation runs, for different communities. 4 presents four runs with the four different sub-communities. The community size is derived by the user selected as the sharing user. Friends column refers to the amount of first degree friends. Table 5 present the results obtained by the four runs. Columns 2-3 and 4-5 present the initial set of edges to be blocked and the final set of edges found by min-cut and contract algorithm respectively. Columns 6-8 present the threshold parameters used for the run. The difference between the two algorithms is the method for finding the initial candidates set, min-cut versus contract. Both algorithms use the same method for computing the privacy criteria. For each community graph we performed the algorithms with extreme thresholds, (α = 0, β = 1, γ = 1, and α = 1, β = 1, γ = 0), and with random thresholds. The remark indicates which edges were found as candidates for blocking. We can see that in the simple case (e.g., run 1 and 2)the solution is trivial and the blocked edges were the edges to the adversaries. While both algorithm are complete, in the non trivial cases, min-cut finds the the best solution with respect to blocking adversaries, while contract may return a compromised solution that is less efficient in blocking adversaries but allows more sharing with friend. However, the time performance of the contract is much better.

It is important to note that the contract algorithm if executed multiple times, is guaranteed to eventually find the optimal solution with respect to the threshold criteria. In the case where there is no solution, the contract algorithm will provide the best cut that satisfies the threshold.

Conclusion

The problem of uncontrolled information flow in social network is a true concern to ones privacy. In this paper we address the need to follow the social trend of information sharing while enabling the owner to prevent their information from flowing to undesired recipients. The goal of the suggested method is to find the minimal set of edges that should be excluded from ones community graph to allow sharing of information while blocking adversaries. To reduce side effect of limiting legitimate information flow, we minimize this impact according to the flow probability. Our algorithms can be used within the ORIGIN CONTROL access control model [START_REF] Sandhu | Originator control in usage control[END_REF]. In this model every piece of information is associated with its creator forever. The set of cut edges found by our algorithms, is stored for each user and can be checked when the origin controlled information is accessed. This way the administrator can check whenever this information is access by a certain user, if the edge between them was cut for the originator user. In future work, we intend to expand the evaluation and test our algorithms on different types of social networks (e.g., twitter). We intend to further explore more approaches to identifying the edges to be blocked, such as genetic algorithm.

Fig. 1 :

 1 Fig. 1: u i s Community Graph

Fig. 3 :

 3 Fig. 3: u 0 s δ-community graph: (a) u 0 s comuunity (b) after initialization Figures 4-5 describe a simple community graph and some steps of one run of the contract algorithm.

Fig. 4 :

 4 Fig. 4: Contract: (a) Edge (5,10) was randomly selected, (b) Edge (5, 2) cannot be selected, since the algorithm can't contract a super-vertex containing u 0 with a super-vertex containing u 0 s adversary.

Fig. 5 :

 5 Fig. 5: Contract: (a) Edge (3, 7) is randomly selected (b) The obtained cut from one run of Contract algorithm

Fig. 6 :

 6 Fig. 6: Synthetic community graph with collision

Table 1 :

 1 . PIF from U 0 to his community Next, using this example we show why the contract approach has better chance of finding a good set of edged that can be blocked while satisfying the privacy criteria.

	User	1	2	3	4	5	6	7	8	9	10
	MAX PIF 0.76 0.62 0.43 0.67 0.4332 0.4154 0.2949 0.4281 0.4115 0.4332
		Edge PIF
		(5,9) 0.95
		(6,9) 0.19
		(8,9)	0.8
		(3,8)	0.9
		(3,7) 0.62
		(5,10)	1

Table 2 :

 2 Min-Cut Candidates

	Edge PIF
	(4,5) 0.62
	(1,5) 0.57
	(2,6) 0.67
	(3,8)	0.9
	(7,10) 0.85

Table 3 :

 3 Contract CandidatesBlock edges by Min-Cut method

Table 4 :

 4 Data sizeTable

Table 5 :

 5 Evaluation Runs Results


Daniele Sgandurra
email: d.sgandurra@imperial.ac.uk

Erisa Karafili
email: e.karafili@imperial.ac.uk

Emil Lupu
email: e.c.lupu@imperial.ac.uk

Formalizing Threat Models for Virtualized Systems

We propose a framework, called FATHoM (FormAlizing THreat Models), to define threat models for virtualized systems. For each component of a virtualized system, we specify a set of security properties that defines its control responsibility, its vulnerability and protection states. Relations are used to represent how assumptions made about a component's security state restrict the assumptions that can be made on the other components. FATHoM includes a set of rules to compute the derived security states from the assumptions and the components' relations. A further set of relations and rules is used to define how to protect the derived vulnerable components. The resulting system is then analysed, among others, for consistency of the threat model. We have developed a tool that implements FATHoM, and have validated it with use-cases adapted from the literature.

Introduction

Addressing security concerns in computing systems requires careful consideration of the threats, usually described through threat models. But for virtualized systems, attacks, solutions and threat models have evolved considerably over the years [START_REF] Sgandurra | Evolution of attacks, threat models, and solutions for virtualized systems[END_REF]. Before presenting a security solution, research papers usually describe their assumptions on the environment where the solution is meant to be deployed. However, threat models are given in a descriptive rather than a formal syntax, which is also not standardized. As a consequence, many publications rely on implicit, and different, assumptions or lack clarity in their assumptions for which there is no commonly understood semantics. For example, different terms are used to refer to a component assumed to be insecure such as "malicious", "untrusted", "in control of the attacker", when the underlying assumption is whether the component is inside or outside the trusted computing base (TCB).

We believe that using a precise model for threat modelling in virtualized systems would help understanding: (i) the meaning of each assumption, by harmonizing the terminology; (ii) whether the threat model has included all the required assumptions at all architectural levels; and (iii) whether these assumptions are consistent. Currently, the relations among components, and how assumptions on one component impact (e.g., restrict) assumptions that can be made on other components, are usually not considered. We propose a model, FATHoM, that allows developers and system designers to precisely state the conditions under which a component can be assumed trusted (or untrusted) given that another component is assumed trusted (or untrusted). FATHoM allows designers to define and analyse a threat model to determine whether it is consistent and complete. The framework, which can be applied with fine granularity, can also be used to describe how components are protected. Furthermore, the framework is compositional.

The main contributions of this work are:

a precise notation to define threat models (FATHoM), which considers the components' security states, the relations among them, and the rules to compute the derived security states based on the assumptions and the relations; a set of relations and rules used to define how to protect vulnerable components, derived by checking the threat model definition for consistency; a prototype tool that implements FATHoM that can be used to define and analyse threat models. FATHoM allows system designers to check the threat model for consistency, completeness, and equality among threat models given a subset of required states.

The paper is structured as follows. In Sect. 2 we list some existing threat models and discuss their limitations. In Sect. 3 we describe FATHoM, including the assumptions, relations and the composition rules. Sect. 4 describes how threat models are defined in the FATHoM prototype tool, and how they can be analysed. In Sect. 5 we show some instantiations of threat models using our approach. Sect. 6 discusses related works, while we conclude in Sect. 7.

Current Threat Models in Virtualized Systems

Virtualization is a technique used to emulate in software the physical properties of a computer, which is encapsulated in a virtual machine (VM) managed independently from other VMs. This allows physical resources such as processor, memory, storage and I/O channels, to be shared between concurrent VMs, while preserving isolation. This enables a more efficient use of the resources, e.g. on Cloud computing datacenters, as they can be allocated on-demand. A virtual machine monitor (VMM) is the software component that creates, manages and monitors VMs. In virtualized systems, the assumptions described in a threat model form the basis from which security control is enforced. For example, if in one threat model physical access is not considered possible, attacks trying to subvert the VMM from the lower levels may not be taken into account by the solution, but may still exist. Similarly, if the threat model assumes the VMM to be with no (exploitable) bugs, whereas the OS is vulnerable, then a proposed protection solution can be deployed directly inside the VMM while considering attacks against the kernel as possible. Threat models have considerably evolved over the years, in an attempt to cope with novel attacks. However, we lack a standard approach to define and analyse the threat models, which is used across the research community [START_REF] Sgandurra | Evolution of attacks, threat models, and solutions for virtualized systems[END_REF]. Some approaches, such as STRIDE [START_REF] Shostack | Threat modeling: Designing for security[END_REF], allow designers to draw trust boundaries across components, and check for a set of known (classes of) vulnerabilities. However, they are not used to check if the definition of threat model is consistent and, furthermore, it is not possible to perform custom analysis, e.g. to compare two threat models for equality. Note that inconsistencies in the description of a threat model can arise as the exact meaning of each assumption is not precise, and how assumptions on a component are related to assumptions on other components is not defined. It is therefore difficult to compare two threat models because, even if they appear similar, they could mean different things to their designers. Furthermore, if some component is not included in the model, the consequences to the trustworthiness of the model, when this component exists in the real world, are not determined. Concerning the nomenclature, the most common set of assumptions encountered in the literature is expressed using a terminology that includes terms such as trusted, vulnerable (or exploitable), untrusted or malicious. However, the words are not used consistently, or with a well understood semantics. Our goal is to provide a framework that enables the definition of the threat models more precisely and clearly. The properties and features of the model we want to provide are: (i) it should be easy to define a threat model based on this framework; (ii) it should be clear what the assumptions are; (iii) the threat model should be consistent and complete; (iv) it should be possible to compose several components together.

3 Language for the Threat Models

The system we represent is composed of different components that have different security properties (also called security states), and different relations between them. We denote by A the nonempty set of components of the system:

A ::= {A, B, C, • • • }.
Components can be added or removed from the system. We denote by Insert the function for adding a new component to the system, and by Remove the one that removes a component from the system:

Insert(A, E) := A ∪ {E} Remove(A, D) := A\{D}
where E is a new component inserted to A, while D is removed from A.

We denote by Φ the set of all formulas of our system. Given the set of components, A, the formulas of our system φ ∈ Φ, are defined by the grammar:

φ ::= true | f alse | φ ∧ φ | φ ∨ φ | φ → φ | (φ) | π | ¬π | ρ π ::= υ(A), where υ ∈ V ρ ::= (A, A), where ∈ R
where A is a component of our system (A ∈ A), V is the set of all security properties of the components, and R the set of all relations between components. The connectors ∧, ∨, →, (, ), and ¬ are the standard ones. Through our language, we can define a set of rules which governs how the relations are used to compute the different properties of the components starting from other properties.

Security Properties of Components

The components of our system can have different security properties, for simplicity just properties, which are associated with their trustworthiness, reliability and restorability values. We divide the properties of our system in basic, high-level, derived and accessory properties, respectively divided in the following sets V B , V H , V D , V A , as represented in Table 1. These sets compose the set of properties of our system: The designer has to specify only the assumptions of the basic properties, which are the most important ones. The rest of the properties are mostly syntactic sugar and can be derived from the basic properties and the relations. The high-level properties, V H , are constructed from the basic ones. As the high-level properties are commonly used, the designer sometimes specifies these properties instead of the basic ones. We distinguish between the derived and accessory properties (V D and V A ) of the system components and the assumed ones that are given by a designer. For sake of simplicity we will consider the high-level, derived, and accessory properties as properties of their own. Basic Properties. The basic properties represent the main assumptions we can make about the properties of a component. These define whether the components are assumed to be under control of the defenders or the attackers, by using the controlled property (trustworthiness), assContr and ¬assContr respectively. When a component is controlled, we consider whether it is assumed to be exploitable or not by attackers (reliability), and thus can be compromised. We use the properties assSafe, and ¬assSaf e, respectively for a reliable component and an exploitable (vulnerable) one. If the component is compromised (¬assContr), we consider whether it can be protected or not (restorability), and introduce protectable or unprotectable, respectively assP rot and ¬assP rot.

V = V B ∪ V H ∪ V D ∪ V A . VB =
Derived Properties. The system also includes the derived version of the assumed properties: derContr, derSaf e, and derP rot, taken from V D . Note that the relations between these properties are the same as their assumed version. Thus, we omit the assumed/derived prefix for them in Fig. 1, which shows the security properties associated with system components. When a component is Controlled the relevant properties are Safe and Vulnerable, which specify whether a component A cannot be compromised (Saf e(A)) or is vulnerable (¬Saf e(A)), because it has known vulnerabilities or is believed it can be maliciously exploited by an attacker. This property identifies components that need to be protected.

Alternatively, if a component is Compromised (and thus not controlled), the relevant properties are Protectable and Unprotectable, which specify whether a compromised component A can be protected (P rot(A)) or not (¬P rot(A)). The difference with the previous case is that a Vulnerable component can always be protected, since it is Controlled, whereas an Unprotectable component refers to a Malicious component, such as an external attacker, a malicious provider, or more generally any external component already compromised and that impacts the security properties of other components, and cannot always be reverted to the Controlled state. A component is assumed vulnerable, if it is assumed controllable and not safe:

assV uln(A) := assContr(A) ∧ ¬assSaf e(A).
A component is assumed untrusted, if it is assumed not controllable (compromised) but is assumed protectable:

assU ntrust(A) := ¬assContr(A) ∧ assP rot(A).
Finally, a component is assumed malicious, if it is assumed not controllable and not protectable:

assM alic(A) := ¬assContr(A) ∧ ¬assP rot(A).
We represent the rules between these properties and the basic ones in Table 2.

assT rust(A) → assContr(A) assT rust(A) → assSaf e(A) assV uln(A) → assContr(A) assV uln(A) → ¬assSaf e(A) assU ntrust(A) → ¬assContr(A) assU ntrust(A) → assP rot(A) assM alic(A) → ¬assContr(A)

assM alic(A) → ¬assP rot(A)

Table 2: Derivation Rules Between Basic and High-Level Properties in FATHoM

In Table 3 we show the semantics of each combination, and give examples of their occurrence in virtualized systems. Recalling the terms discussed in Sect. 2, which are used frequently in related works, if we compare our nomenclature with these terms, we can see that the combinations of security properties in Table 3 correspond to (from top to bottom): Trusted (assT rust), a component that is assumed to be trustworthy; (ii) Vulnerable (assV uln), a component that can have bugs and/or can be attacked but is not in the hand of the attacker; (iii) Untrusted (assU ntrust), assuming that an attacker has full control of this component; (iv) Malicious (assM alic), i.e., a component that is compromised by the attacker and cannot be recovered or protected.

assContr assSaf e assProt Meaning Examples High-Level Property A component that is assumed not to have been compromised and that cannot be exploited.

A micro-kernel OS formally verified, or an app that is protected from integrity attacks from lower levels, or where the attacker has no access.

Trusted (assT rust)

A component that is assumed not to have been compromised but that can be compromised in the future due to a vulnerability.

An OS with bugs during the boot, where the attacker has not direct access to it but can, for example, access it remotely.

Vulnerable (assV uln)

A component that is assumed to be compromised and that can be protected.

The OS kernel in a VM, assumed to be compromised, and that is protected at run-time through the hypervisor for control-flow integrity attacks.

Untrusted (assU ntrust)

A component that is assumed to be compromised and that cannot protected.

An external component (the attacker has full control of it) on which the security solution cannot do anything to change its state.

Malicious (assM alic)

Table 3: Combinations of Security Properties for Components

Relations and Derivation Rules

In FATHoM components can have the following relations between them: R := {Contr, T hreat, P rotect, Ign, Contain, Group, M erge}.

Contr defines a binary relation, where Contr(A, B) means that component A controls component B, e.g., when A is at lower virtualisation layer than B, or A is more privileged than B. Therefore, A can (potentially) change B's security properties by attacking or protecting it. This relation is already given to the system, or it can be implied by other relations. Contr is transitive.

T hreat defines a binary relation, where T hreat(A, B) means that component A can threaten (attack) component B. Thus, A may be able to exploit B's vulnerabilities, e.g., when A is a remote attacker and B a reachable server from the Internet, or A is a component at a higher level (e.g., application) and B one at a lower level (e.g., OS). A successful attack must be carried out by a compromised component A against a vulnerable one B. Component A threatens an other component B because of the design of the system, or if A controls B and component A is assumed/derived compromised.

Contr(A, B) ∧ (¬assContr(A) ∨ ¬derContr(A)) → T hreat(A, B)

Some examples of these relations, in the context of virtualized systems, are shown in Fig. 2.

Fig. 2: Examples of Controls and Threatens Relations

As we focus on threat models, we consider the worst-case scenario. This means that, for example, if A controls B, and A is assumed not controlled, then we cannot assume B to be controlled. Thus, we consider as not controlled all components that could be compromised within our knowledge. We can now introduce one of the accessory properties from V A , which is the can be compromised property, derCanBeCompr, that can be derived from the above relation. We say that B can be compromised, if it is controlled by a compromised component, or if B is threatened by a compromised component and B is vulnerable:

((Contr(A, B) ∧ (assContr(B) ∨ derContr(B))) ∨(T hreat(A, B) ∧ (¬assSaf e(B) ∨ ¬derSaf e(B)))) ∧(¬assContr(A) ∨ ¬derContr(A) ∨ derCanBeCompr(A)) → derCanBeCompr(B).
The derived versions of the high-level properties: derT rust, derV uln, derU ntrust, and derM alic, which are part of V D , are defined as follows:

derT rust(A) := ¬derCanBeCompr(A) ∧ assT rust(A) derV uln(A) := ¬derCanBeCompr(A) ∧ assV uln(A) derU ntrust(A) := derCanBeCompr(A) ∨ assU ntrust(A) derM alic(A) := assM alic(A).

We represent in Table 4 the derivation rules between derived properties. Finally, the Ign (Ignore) relation, used to ignore components, forces the model to assume a given component as trusted:

Ign(A) → assT rust(A). derT rust(A) → derContr(A) derT rust(A) → derSaf e(A) derV uln(A) → derContr(A) derV uln(A) → ¬derSaf e(A) derU ntrust(A) → ¬derContr(A) derU ntrust(A) → derP rot(A) derM alic(A) → ¬derContr(A) derM alic(A) → ¬derP rot(A)
Table 4: Derivations rules between derived properties in FATHoM

Composability

We further introduce the possibility of composing components together, by exploiting three compositional relations: Contains, Groups and Merges. They are respectively used to: (i) enforce consistency among the state of a composite component and the state of its set components; (ii) simplify the description of the threat model, by grouping components together; (iii) abstract from inner components by introducing a new component that summarizes their security states and relations.

Contain(A, B) ∧ Contain(B, C) → Contain(A, C) (1)
Contain(A, B) ∧ assT rust(A) → assT rust(B) (2)
Contain(A, B) ∧ assV uln(A) → assV uln(B) (3)
Contain(A, B) ∧ assU ntrust(A) → assU ntrust(B) (4)
Contain(A, B) ∧ assM alic(A) → assM alic(B) (5)
Group(A, B) ∧ Group(B, C) → Group(A, C) (6)
Group(B, C) ∧ Contr(A, B) → Contr(A, C) (7)
Group(A, B) ∧ Contr(A, C) → Contr(B, C) (8)
Group(B, C) ∧ T hreat(A, B) → T hreat(A, C) (9)
Group(A, B) ∧ T hreat(A, C) → T hreat(B, C) (10)
Group(A, B) ∧ Group(C, D) ∧ Contr(A, C) → Contr(B, D) (11)
Group(A, B) ∧ Group(C, D) ∧ T hreat(A, C) → T hreat(B, D) (12)
M erge(C, A) ∧ Contr(A, B) → Contr(C, B) (13)
M erge(C, A) ∧ T hreat(A, B) → T hreat(C, B) (14)
M erge(C, A) ∧ assT rust(A) → assT rust(C)

M erge(C, A) ∧ assV uln(A) → assV uln(C) (16)

M erge(C, A) ∧ assU ntrust(A) → assU ntrust(C) (17)
M erge(C, A) ∧ assM alic(A) → assM alic(C) (18)

Table 5: The Composability Rules in FATHoM

Contain is a binary relation, where Contain(A, B) means that A contains B, and all of A's internal components must have the same security property as A. This is useful when an external component always includes an internal one, such as a VM that includes the OS, and the security states need to be coherent among them. This relation is transitive given the assumptions in the internal components, represented in Table 5 (1)- [START_REF] Butt | Self-service cloud computing[END_REF]. Group is a binary relation, where Group(A, B) means that A is a new (virtual) component, which groups B (together with, possibly, other components). In this case A is a new component, and Group is consistent in terms of Contr and T hreat relations, as shown in Table 5 (6)- [START_REF] Sommestad | The cyber security modeling language: A tool for assessing the vulnerability of enterprise system architectures[END_REF]. The last composability relation is M erge, where M erge(A, B) means that a new component A is used to consolidate all the internal components (B, and possibly other components) into a new one and merges their states and relations, as represented in Table 5 (13)-(18). The internal components are no longer considered, and assumptions and relations can be now expressed about A. This is useful when we want to consider several, similar, components in a single one with the same properties. The difference between Groups and Merges is that the Groups relation is only used to facilitate the definition of several rules and assumptions on several components together, but the external (virtual) component is not used by the rules, only the internal (real) ones. Instead, Merges is used to remove from the model similar components and replaces them by a new (real) one. In this case, the assumptions and the relations are firstly given on the internal component B, and applied to the external one. Note that a precondition to merge components together is that they are similar, i.e., there are no conflicts. An example of these three relations is shown in Fig. 3.

Protecting Components

We introduce in FATHoM two versions of the P rotect relation. This relation is given by the system/designer, and through it we can derive a very important security property derIsP rot, which defines the property of a component being protected. The first version of P rotect is a binary relation, where P rotect(A, B) means that A can protect component B from the threats considered in the model. The second version is a ternary relation, where P rotect(A, C, B) means that component A can protect component B, with the help of a new component C. This relation is reflexive, where P rotect(A, C, A) means that component A can protect itself, with the help of a new component C (that enhances A). For the ternary P rotect relation, the new component C is inserted in the set of components of A. We show these relations in Fig. 4 (for the sake of readability, we split the ternary relation in two cases, a) and c)).

The Protects relations are used to define the derIsP rot property, which means that a component is in the state of being protected. There are four cases when we can derive that a component is protected, as shown in Table 6. We say that A is protected when it is derived trusted, as shown in (19). We say that A is protected when there exists a controlled component B that protects A (and B can control A), in case A is not safe or protectable, as shown in (20). We say that A is protected when there exists a controlled component B that protects A, with the help of another component C, where B controls A and A is not safe or protectable, as shown in (21). In this case, C is a new component, inserted in the set of components, that is contained in B, and is assumed controlled or

P rotect(A, C, A) ∧ derContr(A) ∧ (¬derSaf e(A) ∨ derP rot(A)) ∧ Insert(A, C) ∧ Contain(A, C) ∧ (assContr(C) ∨ Contr(A, C)) → derIsP rot(A) (22)
Table 6: The Four Cases When a Component is Derived Protected is controlled by B. Finally, we say that A is protected when it can protect itself with the help of C, where A is controllable, exploitable or protectable, as shown in (22). In this case, C is a new component, contained in A, assumed or derived controlled by A. Note that with the current rules, a component is derived Vulnerable only if it is assumed so. Furthermore, a component is derived Malicious iff it is assumed so, using the worst-case rule. However, in some situations, we need to take into account threat models where a component A is assumed to be vulnerable and either (i) it is the target of the protection solution itself or (ii) it is assumed protected by another component (e.g., a vulnerable VMM protected by a trusted module). Hence, it is assumed, and required for the threat model definition, that the component is vulnerable. To limit the cascading effect of this vulnerable component being exploited, we need to check whether it is already protected. This is captured by one of the properties in V A :

derCanBeExpl(A) := derCanBeCompr(A) ∧ assV uln(A)
where a component is derived exploitable if it can be compromised and it is assumed vulnerable.

Using FATHoM to Define and Analyse a Threat Model

We now discuss the implementation of FATHoM, and how it can be used to define and analyse threat models.

FATHoM Prototype Tool

We have designed and developed a tool implementing FATHoM (available at http://rissgroup.org/fathom/) that includes in its knowledge base all the general rules discussed so far. The tool is used also to load a template with the components and relations. A graphical interface facilitates the description of the threat model, which is converted into FATHoM language. (An example of a template is described in Sect.5.) After loading the template, the user can customize some components, and then specify the security states of the components. Finally, the FATHoM tool compiles the threat model (derived from the template and the user choices) and the model's rules into an executable program for XSB 1 . After converting the threat model and the rules for XSB, a designer can query the FATHoM tool to analyse the system: to display those components whose assumed state is different from the derived ones (i.e., a consistency check); to add protection components and exploit the Protects relations. At this point, FATHoM re-compiles the updated threat model (i.e, the derived initial model plus the new protection components and relations), and shows the derived and final threat model.

Definition of the Threat Model

The following steps are used to define threat models within our model: (i) FATHoM loads the rules already defined for all domains, i.e., Controls and Threatens; (ii) the user defines (or imports an existing) template that includes the components' ontology for the domain of interest (e.g., virtualized system), which defines: the components specific to the domain and the Controls and Threatens relations on these components; (iii) the user selects those components that need to be Merged (if any) and those to Ignore (if any); (iv) the user can add new components (optional) or new relations in the model to both existing or new components (optional); finally, (v) the user sets, for each component, the assumed value for Trusted or Vulnerable or Untrusted or Malicious. In contrast to the current, verbose, definitions of threat models, which often span several pages in research papers, in FATHoM users only need to define the assumed security states for all the components, e.g., through a table, such as Table 7, or through a figure, such as Fig. 5b. Not only is the representation very succinct, but the underlying semantics is also common across all the threat models.

Derivation and Analysis

Once the model has been defined (and possibly customized), and the values of the assumptions on the security states has been chosen, FATHoM is used to derive the security states. FATHoM allows the developer to analyse the consistency and completeness of the model, and query possible combinations of assumptions to derive a desired target model. In particular, FATHoM allows the designers to check if there are some security states whose assumptions are different from the derived ones. When an inconsistency is found, the developer is asked to only update the inconsistent assumptions. FATHoM also forces the designers to define the security states for all the components. When a security state for a component is not defined, unless the user has specifically chosen to Ignore it, a warning is returned. Designers can analyse possible solutions to protect the vulnerable and protectable components in the derived threat model. This can be done by refining the model as follows: (i) the user introduces new protection components in the system, such as a hardware co-processor; (ii) the users specifies which components are used to Protect which other components, e.g. the Vulnerable ones. Then, FATHoM enables the user to perform the same analyses on the improved model.

Use-Cases Analysis: Virtualized Systems

We show an instantiation of FATHoM for virtualized systems including the template we have defined for a use-case scenario.

Ontology of Components and Relations

The components we model in this template are defined at four layers: (i) virtualization level: OS, application (APP), administrative VM (AVM), co-resident VM (CO-VM), VT-Driver-domain (i.e., a VM that interfaces all the request to the devices using shared drivers); (ii) hypervisor level: VMM, VMM interface; (iii) firmware level: BIOS (or UEFI), SMM; (iv) hardware level: DMA, Trusted Boot, which can be specialized in static-root-of-trust (SRTM), dynamic-root-of-trust (DRTM), Intel SGX [START_REF] Anati | Innovative technology for cpu based attestation and sealing. 2nd Workshop on Hardware and Architectural Support for Security and Privacy[END_REF], Memory (MEM), which can be refined into RAM and L2-Cache, CPU2 . We augment these elements with additional ones to consider further threats. In detail, when the virtualized environment is run by an external provider, the trust placed in that provider also needs to be considered [START_REF] Butt | Self-service cloud computing[END_REF] [14] [7] [START_REF] Santos | Policy-sealed data: A new abstraction for building trusted cloud services[END_REF]. Hence, other components that we introduce are: (i) physical-access: a component that defines whether physical access is possible for the attacker; (ii) actors: the Cloud service provider (CSP), the tenant and a generic external attacker. Note that for some components, such as actors and physical-access, the only relevant security state is the Controlled /Compromised one, which is semantically equivalent to the component being trusted or not, whereas the Protected /Vulnerable may not need to be considered. Hence, we will restrict their security states to Trusted and Malicious only. Furthermore, the actors in the system can be further refined if we consider entities such as the manufacturer of the hardware used by the provider, the developers of the software run by the provider, and, in general, any third-party involved with the Cloud provider [START_REF] Bleikertz | Defining the cloud battlefield -supporting security assessments by cloud customers[END_REF].

The template we have defined includes the following relations: (i) we Group the components at the hardware-, firmware-, hypervisor-and virtualization-level;

Analysis of the Threat Model

Defining the Threat Model and Checking for Inconsistencies. This analysis is used to identify inconsistencies in the threat model's assumptions, by showing the derived security states that are different from the assumed ones. In this use-case, we firstly customize the template depicted in Fig. 5a to adapt it to the description of this use-case. Here, we consider a threat model that assumes the VMM to be Vulnerable, the tenant and remote attacker to be Malicious, and co-resident VM to be Untrusted. The goal, from the point of view of the provider, is to protect the OS from attacks by tenants and remote attackers by enhancing the VMM to check the integrity of the OS. This use case is adapted from [START_REF] Xiong | Practical protection of kernel integrity for commodity os from untrusted extensions[END_REF], [START_REF] Srivastava | Trusted vm snapshots in untrusted cloud infrastructure[END_REF]. In particular, we consider that a trusted boot-based solution is used to protect the loading of the hypervisor. Then, the provided solution will describe how a new component inside the VMM is used to protect the OS. In detail, we use the FATHoM compositional rules on the template as follows: (i) we Merge RAM and L2Cache into MEM; (ii) we Merge SRTM and DRTM into a single Tboot component; (iii) we Merge BIOS and SMM into a Firmware component; (iv) MEM and CPU are Ignored ; (v) SGX is Ignored. We then set the assumptions on the security states as shown in Fig. 5b (the relations are not shown, since after loading the template we only need to define the assumptions). This graphical description is then translated in the FATHoM syntax, and then compiled for XSB. By using these assumptions, and by querying the FATHoM tool for inconsistencies among assumptions and derived states, FATHoM shows that the components App, OS, AVM, Co-VM and hypervisor are inconsistent3 . These components are those whose assumed states is different than the derived one. In this specific case, FATHoM shows that, by letting the attacker being able to threaten the hypervisor, he/she can compromise the AVM and Co-VM too, as well as the OS and App, and this is not consistent with the initial assumptions. Furthermore, the tenant can compromise the OS. Note that, since in this usecase we have assumed the VMM to be vulnerable, but protected by a Tboot solution 4 , we need to update the model with the relations to protect the VMM from Tboot, and check the model again. By querying FATHoM we see that the hypervisor is consistent with the assumptions, and, hence, we only need to change the App and OS to "untrusted" to be consistent. We have now an initial consistent threat model, whose instantiation is shown in Table 7. As we can see, the formulation of the threat model is very succinct.

Related Work

Mulval [START_REF] Ou | MulVAL: A logic-based network security analyzer[END_REF] is a logic-based analyser that enables the modelling and reasoning about components' interaction. The main difference with our model is that in FATHoM we define assumptions on the security of components, not vulnerabilities or attack paths. Furthermore, our goal is to formalize these assumed security states using a common terminology and ontology, and check its soundness. The CORAS method [START_REF] Braendeland | Using dependent CORAS diagrams to analyse mutual dependency[END_REF] defines a language, and a set of UML-based diagrams, for threat and risk modelling. FATHoM differs from CORAS as it focuses only on threat modelling. Furthermore, FATHoM facilitates the description of the system's assumptions, and follows a worst-case approach, instead of a probabilistic one, and can analyse its soundness. The goals are also different: using CORAS it is possible to implement a risk-evaluation plan, while in our model we depict a static scenario. Similarly, CySeMoL [START_REF] Sommestad | The cyber security modeling language: A tool for assessing the vulnerability of enterprise system architectures[END_REF] is a modelling language targeted at enterprise architectures, to enable administrators to perform a probabilistic inference analysis. The model includes a set of meta-components to define probabilistic dependencies, attack-paths, preconditions, etc. In FATHoM we are focused on describing the initial security preconditions of the system in an easy and sound way, and to take into account generic attacks. Nemesis [START_REF] Kamongi | Nemesis: Automated architecture for threat modeling and risk assessment for cloud computing[END_REF] is a risk-assessment framework to test Cloud systems, by collecting measurements on known vulnerabilities of the system components, modelling the threats and assessing the risk. FATHoM is a framework to define in a consistent way the threat model and used to reason on generic security solutions valid for a set of use-cases. Finally, [START_REF] Alexander | Model checking distributed mandatory access control policies[END_REF] exploits model checking to verify system-level security properties of interacting VMs, and is focused in particular on distributed access control policies. Even if the context is similar, i.e., virtualized environment, the goal of FATHoM is the formalization and analysis of threat models, rather than the verification of access control policies. In summary, none of the the existing works allows designers to (i) define in a compact way threat models, and (ii) perform custom analysis, e.g. to check their consistency. Most existing tools allow users to perform predefined queries over such a threat model (i.e., to check for vulnerabilities), which is supposed to be consistent. Hence, these approaches and FATHoM are complementary.

Conclusion and Future Work

Current threat models lack a common terminology to describe the trusted components, and the relations between them. This gives rise to possible inconsistencies, and incompleteness, of the considered definition. This issue may also impact the assumptions on which a security solution is built upon. In this paper we have proposed FATHoM to describe and analyse threat models and have demonstrated that in real-world scenarios the usability of the FATHoM model is very simple, since it only requires to load an existing template, optionally customize it, and set the assumed values for the security states. We are considering other attacker's goals, such as confidentiality, to be defined in the relations and rules, and other scenarios (e.g., mobile). Finally, the worst-case assumptions underlying our model could be mitigated using probabilistic assumptions on the relations and rules.

Fig. 1 :

 1 Fig. 1: Security Properties High-Level Properties. Let us introduce FATHoM's high-level properties, which can be defined from the basic ones. We define a component A assumed trusted, if it is assumed controllable and safe: assT rust(A) := assContr(A) ∧ assSaf e(A).

Fig. 3 :

 3 Fig. 3: Contains (a), Groups (b) and Merges (c) Relations

Fig. 4 :

 4 Fig. 4: Rules Protects Relation: a) Using a Patch, b) Using an External Component, c) Enhancing an External Component with a Patch

(

  ii) any element at lower-levels can Control those at higher ones (and physical access Controls all the levels); (iii) the Tenant Controls the user VM; (iv) the remote attacker Threatens all the Virtualization level and VMM; (v) the CSP Controls all the VMs, the VMM and lower levels; (vi) the VT-d Threatens the VM, VMM; (vii) the AVM Controls the VM, VMM; (viii) the Co-resident VM Threatens the VM, VMM. These relations used on the previous ontology give rise to the template shown in Fig. 5a.

  (a) FATHoM Template for Virtualized System: Components and Relations (b) Use-Case of Assumptions on a FATHoM Threat Model

Fig. 5 :

 5 Fig. 5: FATHoM Template and Initial Assumptions

Table 1 :

 1 The Security Properties Sets for FATHoM

	{assContr, assSaf e, assP rot}
	VH = {assT rust, assV uln, assU ntrust, assM alic}
	VD = {derContr, derSaf e, derP rot, derT rust, derV uln, derU ntrust, derM alic}
	VA = {derCanBeCompr, derCanBeExpl, derIsP rot}

Table 7 :

 7 Components and Assumptions of the Use-CasesProtecting the Components and Derivation Analysis. On this stable threat model, we then introduce a patch in the VMM to protect the OS5 . Then, by recompiling the threat model with the new protection component, and its relation(s), we query the FATHoM tool again to check the derived Protected components. In this case, FATHoM derives VMM and OS as Protected as well.

http://xsb.sourceforge.net/

Further components that could be considered here are virtualization extensions, chipset, hard-disk firmware.

For the sake of conciseness, we do not show the complete rules, ontology, assumptions, and analysis in XSB here. All the examples are available at http: //rissgroup.org/fathom/, along with a technical report.

[START_REF] Braendeland | Using dependent CORAS diagrams to analyse mutual dependency[END_REF] We only focus on static integrity

protection.[START_REF] Butt | Self-service cloud computing[END_REF] The description of the patch is outside the scope of the use-case.

Acknowledgement

Supported by FP7 EU-funded project Coco Cloud under grant no. 610853, and EPSRC Project CIPART grant no. EP/L022729/1.


Giovanni Di Crescenzo
email: gdicrescenzo@appcomsci.com

Euthimios Panagos
email: epanagos@appcomsci.com

Brian Coan
email: bcoan@appcomsci.com

Enhanced Functionality and Confidentiality for Database Search and Publish/Subscribe Protocols

We show a privacy-preserving and performance-preserving approach to provably transform any database search protocol into a (pull-mode or batchmode) publish-subscribe protocol, and viceversa. This enhances functionality of both protocol types, notably implying practically efficient publish-subscribe solutions for a large class of subscriptions (e.g., index, keyword, range and conjunction). Previous work either missed practicality or focused on customized solutions for specific subscription types. We also show simple padding techniques that enhance the confidentiality of database search and publish-subscribe protocols against communication eavesdroppers. Specifically, these techniques provide optimal hiding of the number of matching database records or publications, while restricted to keeping the communication increase below a specified limit.

Introduction

Private information retrieval, in its early results, showed the possibility of accessing data while provably not leaking undesired information about a database or a query, although at significant applicability restrictions [START_REF] Chor | Private information retrieval[END_REF] or performance costs [START_REF] Kushilevitz | Replication is not needed: Single database, computationally-private information retrieval[END_REF]. After several advances, more recent literature on provably privacy-preserving database retrieval (DR) protocols contains constructions with practical efficiency (i.e., only a constant factor slower than an analogue non-private solution to the problem) for specific query types, and in a 3-party model. There, a help server facilitates a querying client and a data owner achieve their goal, where the only leakage is to the help server and can be provably characterized as 'access-pattern' over encrypted data. Intriguing questions related to this area include: what other types of protocols are possible with similar (or better) privacy and efficiency guarantees?

In this paper, we answer this question for a large class of publish/subscribe (PS) protocols. We show a general paradigm to transform a class of DR protocols into a related class of (pull-mode or batch-mode) PS protocols, while preserving privacy and practical efficiency. The resulting PS protocols provably protect the privacy of publications and subscriptions, and have efficiency only a constant factor slower than an analogue nonprivate solution to the problem. Moreover, they can benefit from practically efficient 3-party database retrieval protocols, without inheriting their drawbacks ('access pattern' leakage to the matching server). To the best of our knowledge, this is the first example in the area of an application where this combination of properties is achievable. We also show a converse transformation of a class of (pull-mode) publish-subscribe protocols into a related class of database retrieval protocols that have practical latency and provably protect privacy of database and queries. Finally, we show how simple padding approaches can further enhance confidentiality against eavesdroppers for both DR and PS protocols. To capture tradeoffs between privacy and communication, we formulate a restricted padding problem, and define a simple padding algorithm that provably increases the eavesdropper's uncertainty about the number of matched database records or publications. Using entropy, we can then quantify the improved confidentiality, and show that the proposed simple padding algorithm is optimal within the considered restriction model.

Related work.

We note that designing PS or DR protocols using general solutions from the area of secure function evaluation protocols in the 2-party [START_REF] Yao | How to generate and exchange secrets (extended abstract)[END_REF] or 3-party [START_REF] Goldreich | How to play any mental game or a completeness theorem for protocols with honest majority[END_REF][START_REF] Feige | A minimal model for secure computation (extended abstract)[END_REF] model, would not result in practically efficient solutions. Practically efficient 3-party DR protocols with provable privacy include [START_REF] Dicrescenzo | Practical private information retrieval from a time-varying, multi-attribute, and multiple-occurrence database[END_REF][START_REF] Jarecki | Outsourced symmetric private information retrieval[END_REF][START_REF] Pappas | Blind seer: A scalable private DBMS[END_REF] for the case of index, keyword, range and conjunction queries. Practically efficient PS protocols with provable privacy in the 3-party model include [START_REF] Dicrescenzo | Efficient and private three-party publish/subscribe[END_REF] for the case of subscriptions based on boolean circuits. (See references therein for more related work on DR and PS protocols.)

2 Models and Definitions for DR and PS protocols DR protocols. A database is an n-row, (m+1)-column matrix Db = (A 1 , . . . , A m+1 ), where each row is associated with a data record, denoted as rec i , for i = 1, . . . , n, each column is associated with an attribute, denoted as A j , for j = 1, . . . , m + 1, and each entry is denoted as A j (i). The first m columns are value attributes, where entries A j (i) are values in a domain Dom j = {0, 1} allowing suitable operations, and the last column A m+1 , is a payload attribute, where entries are from a domain Dom m+1 = {0, 1} r , for integers , r > 0. The database schema, including all parameters and domain descriptions, is known to all parties. A query is a sequence q = (qv 1 , . . . , qv s , mc), where s ≥ 1, mc is a boolean (matching) circuit and, for h = 1, . . . , s, each query value qv h ∈ Dom j , for some j ∈ {1, . . . , m}. An equality query gate (A(i), q, j, h), for some j ∈ {1, . . . , m} and h ∈ {1, . . . , s}, is a function that takes as input A j (i) and qv h , and outputs 1 if A j (i) = qv h and 0 otherwise. An equality-based query is a query where mc = mc (x 1 , . . . , x t ), where mc is a boolean circuit and, for h = 1, . . . , t, each x h is the output of the h-th equality query gate.

A secure database retrieval (DR) protocol in the 3-party model is an interactive protocol between 3 types of efficient parties: a querier Q, having as input a query; a data owner D, having as input database Db = (A 1 , . . . , A m+1 ); and a help server HS, helping Q and D to more efficiently reach their goals. To align with many results in the area, we consider DR protocols with the following 4 subprotocols, as detailed in Figure 1: 1. (Key Setup) D and Q share a key k that is unknown to HS; 2. (Db Setup) D sends an encrypted (using k) version of its database to HS; 3. (Query) Q sends an encrypted (using k) version of its query value(s) to HS; 4. (Answer) HS computes an answer over the received encrypted data, possibly interacting with Q and without involving D, and resulting in Q returning an output.

We define correctness and privacy requirements for DR protocols.

Correctness. The protocol's outcome should be Q's retrieval of the payload(s) A m+1 (i) such that C's query is 'matched' by attribute values A 1 (i), . . . , A m (i). Important examples of queries and matching conditions are as follows:

1. index query: an index ind ∈ {1, . . . , n}; matching condition: i = ind; 2. keyword query: a keyword v ∈ Dom j ; matching condition:

A j (i) = v; 3. conjunction query: multiple keywords v 1 ∈ Dom 1 , . . . , v t ∈ Dom t ; matching condition: (A 1 (i) = v 1 ) ∧ . . . ∧ (A t (i) = v t ) for a specific column j; 4. range query: a range [v 1 , v 2 ] ⊆ Dom j ; matching condition: v 1 ≤ A j (i) ≤ v 2 .
Privacy. The protocol communication should not reveal to any efficient adversary Adv corrupting any one among C, S or HS, any information other than system parameters σ, m, s, r, , κ, n, or the following: (a) when Adv corrupts C, the query and the matching payloads which C is entitled to retrieve in the correctness requirement; (b) when Adv corrupts HS, 'access pattern' information relative to when HS accesses encrypted data provided by D. Given this intended leakage, a formal privacy definition can be derived using known approaches frequently used in the cryptography literature [START_REF] Goldreich | General cryptographic protocols: The very basics[END_REF]. Note that such protocols, even when all communication is encrypted, can leak information to an eavesdropper, such as an upper bound on the number of matching records [START_REF] Dicrescenzo | Practical private information retrieval from a time-varying, multi-attribute, and multiple-occurrence database[END_REF]. We study how to limit this leakage in Section 4. PS protocols. We formally define a data model for PS protocols so to exactly mirror the one for DR protocols; that is, publications are defined like database records, subscriptions like queries, and equality-based subscriptions like equality-based queries. A secure publish/subscribe retrieval protocol is an interactive protocol between 3 types of efficient parties: a subscriber S, having as input a subscription; a publisher P , having as input a publication; and a matching server, denoted as M S, maintaining a repository rp and helping subscribers and publishers to store their subscriptions, publications and carry out their desired functions, including matching publications with subscriptions based on matching circuit mc. To align with some results in the area, we consider publish-subscribe protocols as made of the following 4 subprotocols, with a specific structure, as detailed in Figure 2: 1. (Init): P and S share a key k that is unknown to M S; 2. (Subscribe): S sends an encrypted (using k) version of its subscription to M S; 3. (Publish): P sends an encrypted (using k) version of its publication to M S; 4. (Pull-based Match): Upon S' request, M S determines if there is a match between the subscription and the publication, based on the received encrypted data and matching predicate mc, resulting in S returning an output.

We define correctness and privacy requirements for pull-mode PS protocols.

Correctness. At the end of the protocol S should receive a publication item data i for all publications issued by S and matching with C's current subscription.

Privacy. The communication transmitted during the protocol should not reveal to any efficient adversary Adv that corrupts any one among S, P or HS, any information other than system parameters σ, m, s, r, , κ, n, and the following: (a) when Adv corrupts S, the matching publication data items which S is entitled to retrieve in the correctness requirement; (b) when Adv corrupts M S, the number of matching publication data items in each execution of subprotocol PbMatch. Given this intended leakage, a formal privacy definition can be derived using known approaches from the cryptography literature [START_REF] Goldreich | General cryptographic protocols: The very basics[END_REF]. Note that such protocols, even when all communication is encrypted, can leak information to an eavesdropper, such as the number matching publications, as it is intended to be leaked to S by the correctness requirement. We study how to limit this leakage in Section 4.

Enhanced Functionality for PS and DR Protocols

In this section we describe our privacy-preserving transformations of any DR protocol into a PS protocol. Our first result is the following Theorem 1. Assuming the existence of pseudo-random functions, and of a secure 3party DR protocol π dr for equality-based queries, there exists (constructively) a secure 3-party pull-mode PS protocol π ps for equality-based subscriptions, satisfying: 1. publication correctness; 2. privacy against any polynomial-time adversary Adv corrupting any one among S, P or M S (that is, other than intentionally revealed data, π ps only leaks to M S the number of matching publication data items in any execution of PbMatch) 3. latency and round complexity of π dr is the same as those of π ps ; 4. if π dr has communication complexity linear in number of matching records, then π ps has communication complexity linear in the number of matching publications.

Among mentioned examples of equality-based query and subscription types, Theorem 1 is applicable to index subscriptions, keyword, range and conjunction subscriptions. Remarkably, even if π dr leaks information like 'access pattern' to encrypted data to the help server HS, its application in constructing π ps does not result in any leakage of this same type. This is due to the following: in PS protocols, encrypted publications are only processed once and are deleted afterwards, while in DR protocols, encrypted data records remain stored with HS until they are explicitly deleted.

Description of protocol π ps . We now describe the four subprotocols (Init for initialization, Subscribe for subscription, Publish for publication, and PbMatch for pull-mode matching) of our PS protocol. The overall main idea consists of the following ingredients: P and M S create an encrypted database from a batch of publications issued by P ; S defines a subscription as a database query, and finally an execution of the PbMatch subprotocol can be defined as an execution of the Answer subprotocol. We note that our publication, subscription and pull-based match models well mirror the database record, query and answer models, respectively. Thus, this main idea almost defines the entire construction, by preserving efficiency of the original DR protocol. Only two more refinements are needed to satisfy correctness and privacy requirements. With respect to correctness, we note a potential issue: Subscribe may be run before Publish, while Query needs to run after DbSetup. We circumvent this issue as follows: during Init, a first batch of publications is collected and used by M S with Db-Setup to create a first publication database; later, the next batches of publications for the next publication databases are collected by M S between any two consecutive executions of PbMatch. With respect to privacy, note that repeated use of the same key k during Subscribe and Publish may result in subscription leakage to M S (e.g., repeated occurrences of the same subscription). We avoid this issue using a fresh session key k i at the i-th execution of Subscribe, for i ≥ 1. Each session key is derived from the originally agreed upon key k using standard key derivation techniques. A high-level pictorial description of the protocol can be found in Figure 3. Our next result and protocol are somewhat dual and simpler than our first ones. Formally, we obtain the following Theorem 2. Assuming the existence of pseudo-random functions, and of a secure 3party pull-mode PS protocol π ps for equality-based queries, there exists (constructively) a secure 3-party DR protocol π dr for equality-based subscriptions, satisfying:

Publisher Matching Server Subscriber

1. publication correctness;

2. privacy against any polynomial-time adversary Adv corrupting any one among C, D or HS (that is, other than intentionally revealed data, π dr only leaks the number of matching records to HS for each execution of subprotocol Answer); 3. latency and round complexity of π ps is the same as in π dr ; 4. if π ps has communication complexity linear in number of matching publications, then π dr has communication complexity linear in the number of matching records.

Among the mentioned examples of equality-based query and subscription types, Theorem 2 is directly applicable to index, keyword, conjunction and range queries. A pictorial description of the protocol can be found in Figure 4.

Enhanced Confidentiality for Both Types of Protocols

In this section we describe our main results on enhanced confidentiality against eavesdroppers of DR and PS protocols. First, we define the problem of confidentiality against eavesdroppers in both protocol types. Then, we define a padding algorithm that reduces confidentiality loss while limiting communication increase. Using entropy, this loss can be shown to be optimal within the considered class of padding algorithms.

The eavesdropper confidentiality problem. As proved in [START_REF] Dicrescenzo | Practical private information retrieval from a time-varying, multi-attribute, and multiple-occurrence database[END_REF], in any DR protocol in our model, including both those from the literature and the one obtained from Theorem 2, an eavesdropper can infer information about the number of matching database records. Note that this happens even when the communication is encrypted, since encryption, as is well known, does not hide the length of the plaintext. Padding is an often mentioned approach to reduce such leakage. We study a constrained version of the problem where we use an additive constraint on the amount of affordable padding, and ask the following questions: [START_REF] Chor | Private information retrieval[END_REF] what is the reduction in leakage to the adversary under any such padding strategies, and ( 2) is there an optimal padding strategy, where optimality is in the sense of minimizing leakage about m to an eavesdropper. (Note that although we study the problem for DR protocols, a similar study can be done for PS protocols, where an eavesdropper can infer information about the number of publications matching a given subscription.) Let X(i) denote the random variable that is = 1 (resp., 0) if the i-th database record matches (resp., does not match) the client's query, for i = 1, . . . , n. We assume that all X(i) are independently and uniformly distributed on {0, 1}. Also, let hwX denote the random variable that is equal to the Hamming weight (i.e., the number of 1's) in the vector X = (X(1), . . . , X(n)).

Let pA be an efficient (possibly probabilistic) padding algorithm that takes as input m ∈ {1, . . . , n} and always returns a non-decreasing output m = pA(m); that is, for any m ∈ {1, . . . , n}, with probability 1, it holds that m ≥ m. We say that pA is a c-restricted padding algorithm if for any m ∈ {1, . . . , n}, with probability 1, it holds that m = pA(m) ≤ c • m. Let phwX denote the random variable returning the output of algorithm pA on input a value drawn from random variable hwX.

To analyze the information leaked about m, we use the well-known notion of entropy of a random variable, denoting as H the entropy function which maps a random variable to a real number ≥ 0. In what follows, we study the conditional entropy H(X|phwX = m ), modeling the uncertainty that an (even infinitely powerful) adversary has on matching bits X(1), . . . , X(n), after eavesdropping a communication of length λ(m ), for some m returned by a c-restricted padding algorithm. Entropy-based confidentiality analysis. First of all, we analyze the uncertainty on X from a value for the number of matching records hwX. Then, we define a c-restricted padding algorithm pA and show the implied uncertainty on X from the resulting value for phwX pA . Finally, we show that algorithm pA is optimal, in that it maximizes the uncertainty among all c-restricted padding algorithms. Uncertainty on X from a value for hwX. Let m be an integer in {1, . . . , n}. We observe that Prob[ X = x|hwX = m ] is 0 when the Hamming weight of n-bit vector x, denoted as hw(x), is = m. Otherwise, when hw(x) = m, we have that

Prob[ X = x|hwX = m ] = Prob[ X = x ] • Prob[ hwX = m|X = x ] x Prob[ X = x ] • Prob[ hwX = m|X = x ] = 2 -n • 1 x:hw(x)=m 2 -n • 1 = 2 -n n m • 2 -n = 1 n m
, where the first equality follows from Bayes' rule, and the second on the assumption of X's distribution. Denoting p x,m = Prob[ X = x|hwX = m ], we obtain that

H(X|hwX = m) = - x p x,m log(p x,m ) = - x:hw(x)=m p x,m log(p x,m ) = log n m .
Defining an algorithm pA. Let m be an integer in {1, . . . , n}. We define the c-restricted padding algorithm pA as the algorithm that maps m to the next larger integer m that is an integer multiple of c. Formally, m = (q + 1)c, where (q, r) is the only pair of non-negative integers such that m = qc + r. Note that pA is a deterministic algorithm.

Uncertainty on X from a value for phwX pA . We observe that Prob Optimality of padding algorithm pA. Note that the described algorithm pA always increases the uncertainty on X since H(X|phwX pA = m ) is strictly larger than H(X|hwX = m). It turns out that pA is the best algorithm among all c-restricted padding algorithms. This can be proved into two parts, depending on whether we consider deterministic or probabilistic algorithms, and the proof is based on the above computed expressions and known properties of the entropy function.

Implications on DR and PS protocols. Consider a DR protocol, where a help server HS can augment its answer to C based on a c-restricted padding algorithm. Because of our analysis above, this increases the eavesdropper's uncertainty on the Hamming weight of vector X denoting how many database records were matched with C's query, and this increase is optimal among all c-restricted padding algorithms. Consider a PS protocol obtained from a DR protocol via Theorem 1, where additionally a matching server M S can augment its answer to S based on a c-restricted padding algorithm. Because of our analysis above, this increases the eavesdropper's uncertainty on the Hamming weight of vector X denoting the number of publications matching S' subscription, and this increase is optimal among all c-restricted padding algorithms.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Structure of 3-party DR protocols

Subscribe:Fig. 3 .

 3 Fig. 3. Our Construction of PS Protocols

Fig. 4 .

 4 Fig. 4. Our Construction of DR Protocols

1 =,

 1 [ X = x|phwX = m ] is 0 when hw(x) ∈ {m -c + 1, . . . , m} or m is not an integer multiple of c. Otherwise, when hw(x) ∈ {m -c + 1, . . . , m} and m = kc, for some positive integer k, we have thatProb[ X = x | phwX pA = m ] = Prob[ X = x ] • Prob[ phwX pA = m |X = x ] x Prob[ X = x ] • Prob[ phwX pA = m |X = x ] = 2 -n • 1 hw(x)∈[m -c+1,m ] 2 -n •where the first equality follows from Bayes' rule. Denoting p x,m = Prob[ X = x|phwX pA = m ], we obtain that H(X|phwX pA = m ) is equal to x p x,m log(p x,m ) =hw(x)∈[m -c+1,m ] p x,m log(p x,m ) =

Acknowledgements. Part of this work was supported by the Intelligence Advanced Research Projects Activity (IARPA) via Department of Interior National Business Center (DoI/NBC) contract number D12PC00520. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation hereon. Disclaimer: The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of IARPA, DoI/NBC, or the U.S. Government.