Le-Hung Vu
email: lehung.vu@epfl.ch

Thanasis G Papaioannou
email: thanasis.papaioannou@epfl.ch

Karl Aberer
email: karl.aberer@epfl.ch

Impact of Trust Management and Information Sharing to Adversarial Cost in Ranking Systems

Keywords: trust, information sharing, open systems, adversarial cost, ranking systems, dishonesty detection

Ranking systems such as those in product review sites and recommender systems usually use ratings to rank favorite items based on both their quality and popularity. Since higher ranked items are more likely selected and yield more revenues for their owners, providers of unpopular and low quality items have strong incentives to strategically manipulate their ranking. This paper analyzes the adversary cost for manipulating these rankings in a variety of scenarios. Particularly, we analyze and compare the adversarial cost to attack ranking systems that use various trust measures to detect and eliminate malicious ratings to systems that use no such a trust management mechanism. We provide theoretical results showing the relation between the capability of the trust mechanism in detecting malicious ratings and the minimal adversarial cost for successfully changing the ranking. Furthermore, we study the impact of sharing trust information between ranking systems to the adversarial cost. It is proved that sharing information between two ranking systems on common user identities and malicious behaviors detected can increase considerably the minimal adversarial cost to successfully attack the two systems under certain assumptions. The numerical evaluation of our results shows that the estimated adversary cost for manipulating the item ranking can be made significant when proper trust mechanisms are employed or combined.

Introduction

Ranking has become a popular and important feature of online business applications. A ranking system enables users to rate their favorite items based on item quality and also according to their own preferences. Items may represent services, products, sellable articles, digital content, or search results in different application scenarios. To facilitate the searching of users, these ratings are then used to rank a large number of items of the same category according to both their quality and popularity, e.g. ranking of digital content in social sites (Digg.com) or products in recommender systems (Amazon.com).

The impact of user online opinions on sales and profits is significant [START_REF] Chevalier | The effect of word of mouth on sales: Online book reviews[END_REF]. One can reasonably expect that items with higher ranks are more likely to be selected by clients and thus to produce more value for their providers. Consequently, there is a clear incentive for owners of unpopular and bad items to employ malicious identities to promote (i.e. "ballot-stuff") their own items and demote (i.e. "badmouth") competing ones to generate higher revenue. In real applications these issues are inevitable. For example, sellers can pay people for posting positive reviews on their products, as in [START_REF] Parsa | Belkins Development Rep is Hiring People to Write Fake Positive Amazon Reviews[END_REF] where Amazon reviews are bought with 65 cents each. Botnets can even be hired to conduct the attacks [START_REF] Namestnikov | The economics of Botnets[END_REF].

Regarding manipulation-resistance of ranking metrics, there have been a large number of works on studying resistance of Web page ranking algorithms, such as by throttling Web spams via link structure and link credibility analysis [START_REF] Caverlee | A parameterized approach to spamresilient link analysis of the web[END_REF][START_REF] Gyongyi | Combating web spam with trustrank[END_REF]. These works are applicable to large scale ranking systems that sort Web pages based on various criteria, such link quality and credibility of provider sites [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF][START_REF] Kleinberg | Authoritative sources in a hyperlinked environment[END_REF]. The application of trust mechanisms [START_REF] Golbeck | Trust on the world wide web: A survey[END_REF][START_REF] Jøsang | A survey of trust and reputation systems for online service provision[END_REF] to improve the robustness of a ranking system under adversarial attacks, such as ballot-stuffing and badmouthing is also well-explored [START_REF] Gyongyi | Combating web spam with trustrank[END_REF][START_REF] Feng | Voting Systems with Trust Mechanisms in Cyberspace: Vulnerabilities and Defenses[END_REF]. However, the impact of the capability of a trust mechanism in detecting malicious ratings to the robustness of the ranking system using such mechanisms has not been analyzed yet.

To this end, we present in this paper an analytical approach to evaluate the robustness of a ranking system under attack by an intelligent adversary with limited resources. Particularly, we analyze the cost of an adversary to successfully manipulate the item ranking in smaller-scale systems, such as product review sites and recommender systems. The adversarial cost is estimated as the number of identities and ratings that need to be employed by the adversary to successfully change the ranks of specific targeted items. In practice, this cost may represent the cost of hiring people or botnets to post fake ratings on the targets [START_REF] Namestnikov | The economics of Botnets[END_REF]. We compare the adversary costs when specific trust mechanisms to eliminate biased ratings are employed or not. Thus, we provide theoretical results showing the relation between the capability of the trust mechanism being used to detect malicious ratings and the adversarial cost to attack a ranking system. By numerically evaluating our results, we show that the improvement in robustness of a ranking system using a trust mechanism with a given capability to detect dishonest ratings can be significant under certain assumptions.

Moreover, we extend our analysis to quantify the adversarial cost in an interesting scenario where two similar ranking systems share information regarding common users and the detection of malicious ratings. This scenario is realistic for the following reasons. On one hand, building applications that allows better exchanges of information on user activities with similar systems is an emerging trend adopted by many research and commercial initiatives, e.g., the on-going standardization of the OASIS committee on information exchange across reputation systems 1 and the OpenSocial API for better sharing information among online social networks. Commercial initiatives that are capable of collecting user activities across virtual communities are already available, some examples of which include Spokeo2 and Reputation Defender3 . On the other hand, malicious providers may want to publish their items in different systems for higher profits. To reduce cost, an adversarial provider may reuse a number of malicious identities across systems when posting bogus votes to manipulate the ranking of their items in different systems, e.g., by hiring only one botnet. Hence, by sharing the detection of malicious behaviors across systems, more malicious users are discovered and eliminated, which in turn helps to improve the robustness of the participating systems. We prove that, under certain realistic assumptions, two systems sharing information on common user identities and detected malicious ratings can increase the attack cost of an adversary considerably.

The remainder of this paper is organized as follows: in the next section, we describe the problem of ranking items in the presence of malicious raters. In Section 3, we analytically derive the minimum cost for the adversary to manipulate the ranking of the items under a trust mechanism that detects malicious votes with a certain effectiveness. In Section 4, we prove that the adversarial cost for manipulating the ranking of items increases when two systems exchange information regarding user identities and detected malicious ratings. Our results are numerically evaluated in Section 5, in Section 6 we discuss the related work before concluding the paper in Section 7.

Problem Formulation

Consider a ranking system with a set S of items (e.g. products or services), each having a binary static quality (good or bad). A user may rate the quality of the item after buying it. Let U be the set of honest raters. We denote as r(u, s) ∈ {1, 0, -1} the value of a rating from a user u ∈ U for an item s ∈ S, where a value r(u, s) = 0 implies that u does not rate s. In general, a user u ∈ U reports accurately the item quality. However, due to some observation noise, u may rate an item inaccurately with a small probability 0 < ε 1, e.g. a bad item is rated positively or vice versa. The items are ranked by their quality and popularity score (QP-score) f (s) defined for any item s ∈ S as:

f (s) = u∈U r(u, s) , ( 1
)
where a rating r(u, s) is counted only once for each user u and each item s.

Let S = {s i , 1 ≤ i ≤ M } be the set of all items, where s i has an original rank i according to the formula [START_REF] Chevalier | The effect of word of mouth on sales: Online book reviews[END_REF]. Intuitively, i < j, or the item s i is said to have a higher rank than

s j iff f (s i ) > f (s j ).
The simple ranking function in (1) that only counts the number of positive and negative votes on an item is already effective to rank items in terms of their quality and popularity, provided that no adversary is present. In fact such a metric has been used for ranking the digital contents on various Web 2.0 sites, e.g., to identify the most popular videos or blog entries. The use of sophisticated ranking metrics in more complex business applications, e.g. by considering credibility of the raters, belongs to the class of trust-based ranking functions that we will consider later on. We note that our approach to estimate the adversarial cost as presented in this work can even be extended to arbitrary ranking functions, although a closed-form solution cannot be easily obtained.

Suppose that there is an adversary who wants to boost the rank of an item s k to the highest rank k * = 1 < k. Herein, we use k * = 1 to reduce the number of notations, but it is trivial to extend our analysis for any k * < k. The same analytical reasoning could also be applied to the case that the adversary wanted to raise or lower the rank of a set of items instead of a single one. In order to promote item s k , the adversary uses a set D of malicious user identities to post positive ratings on s k and negative ratings on competing items, i.e. s i , 1 ≤ i ≤ k -1. The total number of malicious ratings is C, and the cost of the adversary includes both components C and |D|.

For each item s i , 1 ≤ i ≤ k, denote as U i and D i the set of honest and malicious users who rate on s i , respectively. The number of ratings on an item s i by a honest and malicious users are respectively

x i =| U i | and y i = |D i |.
Depending the true quality (high or low) of s i , the majority of x i honest ratings on s i would be positive or negative. Naturally, k i=1 D i = D and k i=1 y i = C, since ratings items ranked lower than s k does not help boosting the rank of the target item s k but increase the cost of the adversary. Note that the adversary can observe, prior to his attack, the set U i of any item s i . We assume the worst case scenario where the adversary can estimate the numerical ranking score of every item, apart from the ranking, and thus can derive the cost C and |D| to strategically change the ranking of items.

The system designer wants the ranking to reflect the true quality and popularity of items, so that the system is useful to its users. One naive approach that is often followed would be to simply ignore the presence of a possible adversary, and the items to be ranked according to the QP-score of each item s as in (1): f N (s) = u∈U ∪D r(u, s). To restrict the effect of the malicious ratings posted by the adversary, a preferable approach is to rank items based on the following trust-based QP score:

fT (s) = u∈U ∪D r(u, s)t(u, s) , ( 2
)
where 0 ≤ t(u, s) ≤ 1 is the estimated trustworthiness of the rating r(u, s) and it is measured differently based on the trust management approach employed. We focus in the comparison of the optimal cost of the adversary in terms of its minimal numbers of ratings C and malicious identities |D|, to successfully boost the rank of the item s k in many situations where different QP scores f T (s), f N (s) are used to rank items, and under different possible approaches to evaluate the trustworthiness of ratings. Note that without the adversary D = ∅, we have f T (s) = f N (s) = f (s). Since r(u, s) can be considered as a random variable, i.e., subject to observation noise or the honesty of the rating user, we estimate the expected values

E[f (s)], E[f N (s)], E[f T (s)]
, whenever the exact rating r(u, s) is unknown. Regarding the quality of the other items, we only consider the most important case where items in the competing set s i , 1 ≤ i ≤ k -1 are of good quality (and thus they should be highly ranked for the benefit of the users). The other cases can be similarly analyzed.

3 Adversarial Cost under Trust-based Ranking

Uniform Detection Capability of Malicious Ratings

Consider the system as described in Section 2, with approximate x i = |U i | honest ratings (both positive and negative ones) on an item s i , i = 1, ..., |S|. With the trust-based QP-score (2) as a ranking metric, the minimal cost of the adversary to manipulate the ranking is given by Proposition 1.

Proposition 1. Suppose that the system uses a trust mechanism that can detect malicious ratings on any item with a probability 0 < γ < 1. It is possible to design a ranking system in which the minimal adversarial cost, in expectation, to boost the rank of an item from k to 1 includes the cost of creating |D T | identities and posting C T = |D T | ratings on the target item s k , where:

|D T | = (x 1 + x k ) 1 -2ε + εγ 1 -γ (3)
Proof. First, we prove that there exists a simple trust management approach that is capable of detecting malicious ratings on any item with a probability 0 < γ < 1. The following naive trust management approach to define the trustworthiness t(u, s) of a rating satisfies such a requirement (see Fig. 1):

• A trusted rater e is used to monitor the quality of a (uniformly) randomly selected set of items E ⊆ S, where |E| = γ|S|. • For any u ∈ U ∪ D, if there exists some item s ∈ S such that the rating r(u, s) = r(e, s), and r(u, s)r(e, s) = 0, we define t(u, s) = 0. • Each remaining rating r(u, s) has its trustworthiness proportional to the number of ratings with the same value. Formally, t(u, s) = |Ut(s)|/|U (s)|, where U (s) ⊆ U ∪ D is the group of users who rate on s, and Ut(s) ⊆ U (s) is the users with ratings r(u, s) on s. Apparently, the above trust mechanism can detect malicious ratings on any item s ∈ S with a probability γ, at the cost of the system designer evaluating |E| = γ|S| items to learn of their true quality. Of course there may exist other trust mechanisms that are more cost-efficient, i.e., require the evaluation of less than γ|S| services for a given capability of detection γ. The designing of such a trust mechanism is out of the scope of this analysis.

Recall that U i and D i are correspondingly the sets of honest and cheating raters on s i . The trust-based QP score of an item

s i , 1 ≤ i ≤ k is f T (s i ) = u∈U i ∪D i r(u, s i )t(u, s i ).
To effectively boost the rank of s k , the adversary needs to post at least y i negative ratings on each item s i , 1 ≤ i ≤ k -1 and at least y k positive ratings on the item s k . The goal of the adversary is to ensure the expected trust-based QP-score of the target item s k to be as high as that of every other item of higher rank, i.e.,

E[f T (s k )] ≥ E[f T (s i )], 1 ≤ i ≤ k -1.
Consider any item s i , 1 ≤ i ≤ k -1 with a good quality. Due to observation noise, among honest users U i , a subset U i ⊆ U i may give unfair (negative) ratings on s i . A smaller subset U i ⊆ U i may be detected by the trust management approach as cheater. Similarly, a subset of malicious users D i who rate s i negatively (to favor s k ) would be detected by the trust management mechanism. Denote as L i ⊆ D i the set of malicious raters that are not detected. Then, users in the group P i = U i -U i vote positively and those in the group

N i = (U i -U i ) ∪ L i vote negatively on s i . Note that P i ∪ N i = (U i -U i ) ∪ L i , as in Fig. 2(a). The trustworthiness t(u, s i ) of a rating r(u, s i ) is estimated as: • For u ∈ U i ∪ (D i -L i ) : t(u, s i ) = 0, i.e.
, users with erroneous observation and malicious users are marked as cheaters. Eliminating ratings with 0 trustworthiness, i.e., those of users in the shaded parts of Fig. 2(a), the trust-based QP-score of any s i ∈ S, i = 1, ..., k-1 becomes:

• For u ∈ P i = U i -U i : t(u, s i ) = |Pi| |P i ∪N i | . Similarly, for u ∈ N i = (U i -U i ) ∪ L i , t(u, s i ) = |N i | |Pi∪Ni| . Li Di-Li L2 Li (D2-L2) D2-L2 Ui U2 U'i U''i U2' U2'' Di D2 Li Di-Li Ui U'i U''i Di (a) (b) Dk Z2 Z Dk2 (c)
f T (s i ) = u∈P i 1. |Pi| |P i | + |N i | + u∈N i (-1) |Ni| |P i | + |N i | = |P i | -|N i |
Since with a probability γ, malicious ratings on any item will be detected by the trust mechanism, we have:

• E[|U i |] = |U i |ε = x i ε, and E[|U i |] = E(|U i |)γ = x i εγ. • E[|D i -L i |] = E[ u∈D i 1 {u detected} ] = u∈D i E[1 {u detected} ] = |D i |γ. It follows that E|L i | = |D i |(1 -γ) = y i (1 -γ). As a result E[|P i |] = E[|U i -U i |] = E[|U i | -|U i |] = x i (1 -ε) and E[|N i |] = E[|(U i -U i )∪L i |] = E[|U i |-|U i |+|L i |] = x i ε-x i εγ+y i (1-γ) = (1-γ)(x i ε+y i ). Therefore, for any 1 ≤ i ≤ k -1: E[fT (si)] = E[|Pi|] -E[|Ni|] = xi(1 -ε) -(1 -γ)(xiε + yi) = xi(1 -2ε + εγ) -yi(1 -γ)
Similarly for the target item s k , noting that honest users mostly rate negatively and malicious users rate positively on s k , we have:

E[f T (s k )] = -E[|P k |]+E[|N k |] = -x k (1-ε)+(1-γ)(x k ε+y k ) = -x k (1-2ε+εγ)+y k (1-γ)
The item s k has a higher rank than

s i iff E[f T (s k )] ≥ E[f T (s i )]
, or:

y k + y i ≥ (x k + x i ) 1 -2ε + εγ 1 -γ
The minimal number of ratings the adversary needs to insert into the system is the solution of the following integer program:

C T = min{y 1 + y 2 + . . . + y k } s.t. y k + y i ≥ (x i + x k )(1 -2ε + εγ)/(1 -γ), i = 1, ..., k -1 (4)
where all x i , y i are non-negative integers, x i s are fixed. One can also verify that as the first k -1 items are assumedly good, the number of ratings on them satisfies x i ≥ x i+1 , for i = 1, ..., k -2. This program has the following complete set of solutions 4 :

y k = (x1 + x k )(1 -2ε + εγ)/(1 -γ) -d; y1 = d; yi = 0, 2 ≤ i ≤ k -1, where 0 ≤ d ≤ d max = (x 1 -x 2 )(1 -2ε + εγ)/(1 -γ) (5)
Each solution above (for each 0 ≤ d ≤ d max ) requires the adversary to post the same total number of ratings

C T = k i=1 y i = (x 1 + x k ) 1-2ε+εγ
1-γ . For each d, a corresponding attack strategy is to create at least max{C T -d, d} = C T -d identities 5 . Each of these C T -d identities posts a positive rating on the target item s k ; d identities are then reused to post negative ratings on the highest ranked item s 1 . With the attack strategy of d = 0, the adversary needs to create C T identities, and the probability the attack is successful is 1 -γ. For d > 0, the adversary needs to create fewer (C T -d) identities, since he can use the same user to post ratings on both items s 1 and s k . However, a strategy with d > 0 leads to higher chance that these identities are detected, and the probability that the attack is successful in this case becomes smaller, i.e., (1 -γ) 2 < 1 -γ. Formally, considering the expected gain and the risk of the adversary being detected, we can prove that the utility of the adversary is maximized at d = 0 in any of the two cases (1) γ is within a certain range or (2) the gain of the adversary if the attack is success is very large compared to its cost of creating d max malicious identities. The proof is skipped due to space limitation. If we assume the case that the adversary cares most about the probability of success of the attack, the optimal strategy of the adversary is when d = 0, which incurs the following cost of creating at least

|D T | = (x 1 + x k ) 1-2ε+εγ 1-γ
identities and posting at least C T = |D T | ratings on the item s k , as claimed by the proposition.

In this paper, we refrain from presenting the analysis for the general case where an item s i , 1 ≤ i ≤ k has a true quality q i ∈ {1, 0} (high or low) for clarity reasons. This general result can be obtained by similar reasoning and by replacing the factor x 1 + x k in (3) with (-1) 1-q1 x 1 -(-1) 1-q k x k . Also by analogy, one can verify that the adversarial cost for promoting the target item to a desired rank k * < k can be obtained from (3) after replacing x 1 with x k * .

Following immediately from Proposition 1, we have an estimate of the extent of rank manipulation that can be done by an adversary.

Corollary 1. If the system uses a trust mechanism that can detect malicious ratings on any item with probability 0 < γ < 1, an adversary with capability to create at most |D| identities and posts C ratings may manipulate the rank of a favorite item from the origin k to the highest rank k * ≤ k defined by:

k * = k min k =1 {k : (x k + x k ) 1 -2ε + εγ 1 -γ ≤ min(C, |D|)} (6)
By similar reasoning, we obtain another result on the minimal adversarial cost when no trust mechanism is employed in the system (see Proposition 2).

Proposition 2. In a system with no trust management mechanism to detect malicious users and eliminate their ratings, the minimal cost of the adversary to boost an item with rank k to rank 1 includes:

• The cost to create |D| = (x 2 + x k )(1 -2ε) identities.

• The cost to post C = (x 1 + x k )(1 -2ε) ratings on the two items s 1 and s k . The optimal attack strategy is to post d max = (x 1 -x 2 )(1 -2ε) negative ratings on the top item s 1 and post C -d max positive ratings on the target item s k .

The proof is similar to that of Proposition 1 for γ = 0. The difference is in the optimal attack strategy of the adversary. If the system uses no trust mechanism to detect malicious users and eliminate their ratings, the optimal strategy of the adversary to boost an item with rank k to rank 1 is attained at d = d max , for which the adversary needs to create only C -d max identities and uses them to vote negatively for s 1 and rate positively on the target item s k .

From Proposition 2, we can also estimate to which extent an adversary with a fixed cost may manipulate the rank of his or her favorite items (Corollary 2).

Corollary 2. Consider a system with no trust management mechanism to detect malicious users and eliminate their ratings. An adversary with capability to create at most |D| identities and posts C ratings to the system may manipulate the rank of its favorite item from k to the highest rank k * ≤ k defined by:

k * = max{ k min k =1 {k : (x k +1 + x k )(1 -2ε) ≤ |D|}, k min k =1 {k : (x k + x k )(1 -2ε) ≤ C}} (7)
Compared between the cost in Proposition 1 and Proposition 2, using a trust management mechanism that detects malicious ratings on any item with a probability γ would increase the minimal adversarial cost by some magnitudes:

|DT |/|D| (x 1 + x k )(1 -2ε + εγ) (x2 + x k )(1 -2ε)(1 -γ) > 1 (8) CT /C 1 -2ε + εγ (1 -2ε)(1 -γ) > 1 ( 9
)
Our analysis is general as the notion of γ include the capability of the trust mechanism to detect malicious on any item. There may exist other trust mechanisms that are more efficient in terms of guaranteeing a higher detection probability γ. These mechanisms might consider the reputation of the raters, credibilities of the item providers, and the correlation of ratings among raters to each others, etc. Designing such trust mechanism is, however, orthogonal to our work.

The cost of attacking the system also strongly depends on the set of votes by honest users, i.e., x i . In systems where honest users outnumber the malicious users deployed by the adversary, manipulation of the trust-based ranking is much more costly to the adversary. Existing techniques to restrict the number of identities created by the adversary can be easily integrated to our analytical framework to restrict the capability of the adversary to manipulate the ranking.

Non-Uniform Detection Capability of Malicious Ratings

Generally, the probability that the trust mechanism detects malicious ratings on different items may be non uniformed. For example, the trust mechanism may focus more on protecting of popular (and usually higher ranked) items, thereby increasing the probability of detecting unreliable ratings on these items. Let γ i be the probability that malicious ratings on an item s i ∈ S are detected and eliminated. As a generalization of the analysis in Section 3.1, the optimal cost of the adversary to successfully manipulate the rank of the item s k is the solution to the following integer program:

C ext = min{y 1 + y 2 + . . . + y k } s.t. y k (1 -γ k ) + yi(1 -γi) ≥ xi(1 -2ε + εγi) + x k (1 -2ε + εγ k ) = φi, i = 1, ..., k -1
where all 0 < γ i < 1 are fixed, all x i are fixed non-negative integers, and

x i ≥ x i+1 , for i = 1, ..., k -2.
The probabilities γ i are inherent to the trust mechanism, possibly determined by the system designer, while unknown to the adversary. The solution to the above optimization problem is the lower bound of the cost of the adversary. It is also our interest to evaluate which setting of γ 1 , ..., γ k , ..., γ |S| would result in a higher minimal cost of the adversary. Finding closed-form solutions for these cases is non-trivial and thus it is done numerically in Section 5.

The Benefits of Sharing Trust across Ranking Systems

This section presents the analysis of the adversarial cost in a system that uses an open trust management approach for detection and elimination of malicious ratings. That is, the system exchanges information on the identities of malicious users detected with another ranking system. Let S2 be the item set of the second system. Given any item s j ∈ S2, define U 2 j the set of honest users with ratings on s j , and U 2 = s j ∈S2 U 2 j . Also, let D2 j be the set of malicious users with ratings on s j , and also define D2 = s j ∈S2 D2 j .

Assume that the second system uses another trust management approach that can detect malicious ratings on any item with a probability 0 < γ 2 < 1. We assume that the two ranking systems are designed to automatically and reliably share the identities of malicious users detected to each other, and the system managers have low incentive to modify the software implementation to tamper such information. Fair and reliable information sharing between systems is an important issue that is beyond the scope of this paper and subject to future work. The identification of common users (in a privacy-preserving way) can be done via alias detection and entity resolution methods, e.g., based on credential attributes of the users. This problem is, however, orthogonal to the current analysis and thus is not further discussed.

For the case where two systems do not share any information, the adversary would need a set of D users to post a minimal number of C T ratings to boost his favorites item s k in the first system. Suppose that the goal of the adversary when attacking the second system is to boost the rank of an item s k 2 ∈ S2 from k 2 to k * 2 = 1 6 . Then, the adversary would use another set of malicious users D2 to post a minimal number of C T ratings on his favorite items s k 2 in the second system. According to the analysis in Section 3.1:

C T = (x k + x 1 ) 1 -2ε + εγ 1 -γ =| D | and C T = (x k 2 + x 1 ) 1 -2ε + εγ2 1 -γ 2 =| D2 |(10)
where x i , i = 1, ..., k 2 have similar meanings to those of the first system. Suppose that the adversary is able to create up to N =| D ∪ D2 | identities in two systems for its malicious purposes. It is required that N > max{C T , C T }, otherwise with all N identities the adversary is still unable to attack both systems successfully. We will evaluate the benefit of sharing information between two systems where such sharing is beneficial to both. That happens if the adversary does not have enough resources and needs to use a certain number of identities in both systems for its attacks, i.e., when max{C T , C T } < N < C T + C T . Under this restriction, the adversary would use C T among N identities to post C T ratings on the first system. The posting of C T ratings in the second system will be done by employing: (1) the unused N -C T identities; (2) C T +C T -N among those C T identities already used in the first system.

Hence, the cost of the adversary in case of no information sharing is:

• The cost of creating N identities, where max{C T , C T } ≤ N ≤ C T + C T .
• The cost of posting C T + C T ratings in both systems. When the two systems share trust evaluation results, the adversarial cost is:

• The same cost of N identities as in the case of not sharing information.

• The cost of posting R T ratings, which would be defined later on.

6 Again we use k * 2 = 1 to reduce the notations without loss of generality of the analysis.

We want to analyze how the adversarial cost in the case of sharing trust evaluation result differs from the case of not sharing any information, i.e., to quantify

R T -C T -C T . Denote as τ i =| U i ∩ U 2 |, 1 ≤ i ≤ k
the number of honest users who post ratings on s i and also appear in the second system. We may approximate that

τ i =| U i ∩ U 2 |≈ τ / | S |, 1 ≤ i ≤ k,
where τ is the number of common honest users who post ratings in both systems. Similarly define

τ i =| U 2 i ∩ U |≈ τ / | S2 |, 1 ≤ i ≤ k 2 the
number of honest users who post ratings on s i ∈ S2 and also appear in the first system. The following main result gives us an estimation of the benefit of sharing information between the two systems. Proposition 3. Consider two ranking systems with capabilities γ, γ 2 of detection malicious ratings, where 0 < γ ≤ γ 2 < 1. Assume ∆ be the number of identities the adversary needs to reuse in two systems, in the best case for the adversary, we have:

0 ≤ ∆ ≤ min{(x k + x1) 1 -2ε + εγ 1 -γ , (x k 2 + x 1 ) 1 -2ε + εγ 2 1 -γ 2 } ( 11
)
If the two systems share trust evaluation information to each other, then the difference of the adversary cost to attack the two systems between two cases of sharing vs. non-sharing of information is bounded below by:

R T -C T -C T > ∆γ 1 -γ - εγ 2 (τ k + τ 1 )(1 -2ε + εγ) (1 -γ) 2 - εγ(τ k 2 + τ 1 )(1 -2ε + εγ 2 ) (1 -γ2) 2 (12)
Proof. We provide here a sketch of the proof (the full proof can be found in [START_REF] Vu | Impacts of trust management and information sharing to adversarial cost in ranking systems[END_REF]). Let z i =| D i ∩ D2 |≤ y i , 1 ≤ i ≤ k be the number of malicious raters who appear in both systems and rate an item s i ∈ S (of the first system). Similarly denote z j =| D2 j ∩ D |≤ y j , 1 ≤ j ≤ k 2 the number of cheating users present in both systems and rate an item s j ∈ S2 (of the second system). Proceed as in Proposition 1, the minimal number of ratings C T by the adversary to successfully attack the first systems is the solution to the following integer program:

C T = min{y 1 + y 2 + ... + y k } subject to:

y k + y i ≥ (x k + x i -εγ 2 (τ k + τ i )) 1 -2ε + εγ 1 -γ + (z k + z i )γ 2 , i = 1, ..., k -1 y i ≥ z i , i = 1, ..., k
where x j , y j , τ j , z j , j = 1, ..., k are non-negative integers, all

x i , τ i , z i , i = 1, ...k is fixed, x i ≤ x j , for i ≤ j, i, j = 1, ..., k -1. For i = 1, ...k, define g i = (x k + x i -εγ 2 (τ k + τ i )) 1-2ε+εγ 1-γ -(z k + z i )(1 -γ 2 )
. One may verify that any solution of the above program results in the same optimal number of ratings C T = max{0, max k-1 i=1 g i } + k i=1 z i . Similar to the previous section, if we assume that the adversary cares most about the probability of success of the attack, the optimal attack strategy is:

• for the item s k : the adversary uses a set of users D k from the first system and z k identities from the second system to post

y k =| D k | +z k ratings on s k . We have | D k |= max{0, max k-1 i=1 g i }, and thus C T =| D k | + k i=1 z i .
• for the items s i , i = 1, ..., k -1: the adversary uses z i identities from the second system to post z i ratings on each s i . The set of malicious users to be used by the adversary in the first system is then D = D k ∪ Z, where Z ⊆ D2 is set of identities borrowed from the set of malicious users D2 in the second system. These borrowed identities are used by the adversary to post a total of k i=1 z i ratings on those items s i , i = 1, ..., k. Likewise, the set of malicious users in the second system is D2 = D k 2 ∪Z2, where Z2 ⊆ D is set of identities borrowed from the first system to rate on items in the second system. D k2 is the set of malicious users who are only present in the second system and rate the target item s k2 ∈ S2.

The set of malicious users used by the adversary to attack both systems is thus

D T = D k ∪ Z ∪ D k 2 ∪ Z2. Fig. 2(c) illustrates the relation among different sets D k , Z, Z2, D k2 . Clearly, the malicious set D T is smallest iff Z ⊆ D k2 and Z2 ⊆ D k .
That is, the same malicious users in one system, e.g., D k2 , are used to rate items in the other system, e.g., to rate item s i ∈ S, i = 1, ..., k. Under such a situation, the total minimal number of identities the adversary needs to create in the two systems is

| D T |=| D k | + | D k 2 |.
Similarly, the minimal number of ratings to be posted in the second system is

C T =| D k 2 | + k 2 i=1 z i .
Thus the total cost of the adversary to attack both systems includes two cost: (1) to create | D T | identities and (2) to post R T = C T + C T ratings in the two systems. Given a fixed number of identities N , the goal of the adversary is to determine the number of common users z i ≥ 0, z j ≥ 0, i = 1, ..., k, j = 1, ..., k 2 such that R T is minimized. In other words:

R T = min{| D k | + | D k 2 | + k i=1 z i + k 2 j=1 z j } subject to: | D T |=| D k | + | D k 2 |= N where | D k |= max{0, k-1 max i=1 {(x k + x i -εγ 2 (τ k + τ i )) 1 -2ε + εγ 1 -γ -(z k + z i )(1 -γ 2 )}} and | D k 2 |= max{0, max 1≤i≤k 2 -1 {(x k 2 + x i -εγ(τ k + τ i )) 1 -ε + 2εγ 2 1 -γ 2 -(z k + z i )(1 -γ)}} Solving this program give us R T ≥ -N γ 1-γ +max k-1 i=1 { fi 1-γ }+max k2-1 j=1 { f j 1-γ }
, where for simplicity we define

f i = (x k + x i -εγ 2 (τ k + τ i )) 1-2ε+εγ 1-γ , i = 1, ..., k -1 and f i = (x k 2 + x i -εγ(τ k 2 + τ i )) 1-2ε+εγ 2 1-γ2 , i = 1, ..., k 2 -1. Since max{C T , C T } ≤ N < C T + C T , there are at least ∆ = C T + C T -N
identities used by the adversary in the two systems, where:

0 ≤ ∆ ≤ min{C T , C T } = min{(x k + x 1 ) 1 -2ε + εγ 1 -γ , (x k 2 + x 1 ) 1 -2ε + εγ 2 1 -γ 2 }
The bound of ∆ is for the best case of the adversary, when he can estimate the cost C T , C T to successfully attack the two systems. Given ∆ defined as above, with basic computations we obtain:

R T -C T -C T > ∆γ 1 -γ - εγ2(τ k + τ1)(1 -2ε + εγ) (1 -γ) 2 - εγ(τ k 2 + τ 1 )(1 -2ε + εγ2) (1 -γ 2 ) 2 (13)
and Proposition 3 follows naturally.

The cost difference R T -C T -C T in Proposition 3 mostly depends on the shortage of identities ∆ of the adversary. The fewer number of identities the adversary has, the higher number of common identities it shall reuse across the two systems, and the more ratings it needs to insert into both systems to successfully manipulate the ranks of its favorite items. For most ∆ and where the noise ε is negligible, it is apparent that R T -C T + C T > 0, or the adversarial cost to manipulate the ranking in both systems in the case of sharing trust information between the two systems is higher than the adversarial cost C T +C T where no information is shared. The capabilities of the two trust mechanisms in detecting malicious ratings, i.e. the probability γ, γ 2 also play an important rule in increasing this total adversarial cost. The sharing of information, however, may also lead to some false positives when estimating common users as cheating. This observation noise however plays a minor role, as the two negative terms on the right hand side of ( 12) are small, given small values of ε. Note that this cost difference R T -C T -C T is estimated in the worst case where the adversary knows the common users (τ i , τ i ) and is aware of the effectiveness of the two system at detecting malicious activities (γ, γ 2 ) to develop an optimal strategy of placement malicious ratings in the two systems.

Numerical Evaluation

In this section, we numerically evaluate our results. All items including the target items are assumed to be good (but differ in popularity), which can be proven as even less costly for the adversary to promote them, and with the least difference between the number of ratings between items (hence the minimum adversarial cost is the lowest possible). The estimates are for ε = 0.05 and M = |S| = 100 items. There are x i = M -i honest ratings for each item with rank 1 ≤ i ≤ M . Fig. 3 evaluates the increase in the minimal adversarial cost |D T |/|D| with respect to uniform detection capabilities γ of the trust management and with various values of the original rank k and desired rank k * < k of the target item. We observe that even in this pessimistic scenario, the use of a trust mechanism with reasonable detection capability γ = 0.5 doubles the adversarial cost to manipulate the rankings in terms of the number of identities, irrespective of the original rank of the target item. The increase in adversarial cost by the number of malicious ratings C T /C has a similar trend. Also, the raise of the adversarial cost for promoting the lowest ranked item can be achieved by increasing the detection capability of the trust mechanism being used γ (Fig. 3).

Next, we consider the impact to the minimal adversarial cost of a trust mechanism with non-uniform detection capabilities γ. For simplicity, we assume linear ascending and descending γ functions with respect to the item original rank and numerically solve the linear program of Section 3.2. The adversarial identities and ratings ratios (|D T |/|D| and C T /C respectively) with respect to the initial item rank are depicted in Fig. 4. Thus, an ascending γ distribution increases the minimum adversarial cost for promoting lower ranked services. Then, we consider multiple permutations of the γ values for the items of various ranks and we observe that a trust mechanism that focuses more on detecting malicious ratings on lower ranked items increases the minimal adversarial cost to promote their ranking. In Fig. 5 the permutations corresponding to to the highest cost are those with γ ascending w.r.t the item rank. The impact of sharing trust information to the overall robustness of the two systems for an example case is given in Fig. 6, measured in the increase of adversarial cost (the number of ratings the adversary needs to insert into both 12) in the worst case scenario with the least difference between the item popularity, x i = M -i, 1 ≤ i ≤ M, x j = M -j, 1 ≤ j ≤ M . Observe that the sharing of information between two systems helps to significantly raise the total cost of the adversary to attack the two systems, thus strengthening both systems significantly. The conditions for this sharing of trust information to be beneficial to both systems, i.e., log(R T -C T -C T ) > 0 are: (1) the detection capabilities of the two systems are sufficiently high, and (2) the resources of the adversary are limited, e.g., γ, γ 2 > 0.5 and ∆ > 5 in the case of Fig. 6.

Related Work

The works most related to ours include existing research on resilience of Web page ranking algorithms against Web spams, via link structure and credibility analysis, namely [START_REF] Caverlee | A parameterized approach to spamresilient link analysis of the web[END_REF][START_REF] Gyongyi | Combating web spam with trustrank[END_REF]. The use of trust and reputation mechanisms to minimize the influence of adversarial attacks in ranking systems has also attracted much effort [START_REF] Golbeck | Trust on the world wide web: A survey[END_REF][START_REF] Jøsang | A survey of trust and reputation systems for online service provision[END_REF]. EigenTrust [START_REF] Kamvar | The EigenTrust algorithm for reputation management in P2P networks[END_REF] presents a global trust metric to measure the credibility to a node in a network based on inter-connecting links among nodes. Other works, as [START_REF] Gyongyi | Combating web spam with trustrank[END_REF], use reputation-based trust management techniques to improve the robustness of ranking systems but with little analysis on the impact of trust mechanisms to the adversarial cost for strategic manipulation the system. A more recent work [START_REF] Feng | Voting Systems with Trust Mechanisms in Cyberspace: Vulnerabilities and Defenses[END_REF] studies vulnerabilities and attacks by an adversary with a given cost to voting systems and propose defense mechanisms based on item popularity. This work is different from ours as it only considers the binary voting result on item quality while our work is more general: we consider ranking systems that use both popularity and quality of items as ranking metrics.

Conclusion

This paper analyzes the minimum adversarial cost to manipulate the ranking of items in systems where a trust mechanism is employed for detecting unfair and biased ratings. We provide theoretical results showing the relation between the capability of the trust mechanism being used to detect malicious ratings and the minimal adversarial cost to successfully attack a ranking system. Moreover, we have proved that, under certain realistic assumptions, two systems with shared information on malicious user activities can increase the minimal successful attack cost of an adversary considerably. Our analysis indicates that the cost of the system designer to prevent attacks from the adversary with a certain power, is related to the cost of implementing a trust management mechanism with a certain capability of detecting malicious rating behaviors. The analytical framework in the paper can be extended to estimate the robustness of more complex ranking score metrics against the adversary. It may also be our interest to analyze the cost and the influence on the final ranking result in presence of many competing adversaries with different powers.

Fig. 1 .

 1 Fig.1. Detection possibly malicious ratings on items by using a trusted rater.

Fig. 2 .

 2 Fig. 2. (a) Venn diagram of the set of malicious and honest users detected by a trust mechanism. (b) The set of malicious and honest users detected by combining two trust management mechanisms. (c) Different sets of malicious users used by the adversary.

Fig. 3 .Fig. 4 .

 34 Identities cost by a trust mechanism with different detection capabilities γ: (a) the target has variable original rank k and desired rank k * = 1; and (b) the target has original rank k = M/2 and variable desired rank k * . Identities (a) and ratings (b) cost ratio for promoting an item with rank k with or without a trust mechanism employing an ascending or descending γ distribution.

Fig. 5 .

 5 Identities (a) and ratings (b) minimum cost for promoting an item initially ranked last with different γ distributions.

Fig. 6 .

 6 cost R T -C T -C T ', k=50, k 2 =5 Shortage of identities of the adversary ∆ Impact of the trust information sharing to the increase of adversarial cost (in log scale) where: (a) the (origin) rank of the target is average in both systems; (b) the rank of the target in one system is high. The results in other cases are similar. systems). The two systems are assumed to use trust management mechanisms with similar detection capabilities γ = γ 2 , have two similar item sets |S| = |S2| = M with roughly τ = 10% common honest users. The measurements are done in two representative cases where the target items have different original ranks in the two systems. The estimates are based on Eq. (

www.spokeo.com

www.reputationdefender.com

For clarity, we omit rounding operators . from the right side of equations[START_REF] Gyongyi | Combating web spam with trustrank[END_REF].

Without loss of generality, we assume that x1 + x k ≥ 2(x1 -x2), hence CT -dmax ≥ d max and thus max{C T -d, d} = C T -d.


Jose M Del Alamo

Miguel A Monjas
email: miguel-angel.monjas@ericsson.com

Juan C Yelmo
email: jcyelmo@dit.upm.es

Beatriz San

Ruben Trapero
email: rubentb@dit.upm.es

Antonio M Fernandez
email: antoniofer@dit.upm.es

Self-service Privacy: User-Centric Privacy for Network-Centric Identity

Keywords: privacy, identity management, user-centric, network-centric, user control

User privacy has become a hot topic within the identity management arena. However, the field still lacks comprehensive frameworks even though most identity management solutions include built-in privacy features. This study explores how best to set up a single control point for users to manage privacy policies for their personal information, which may be distributed (scattered) across a set of network-centric identity management systems. Our goal is a user-centric approach to privacy management. As the number of schemas and frameworks is very high, we chose to validate our findings with a prototype based on the Liberty Alliance architecture and protocols.

Introduction

Being online today means so much more than just being connected to the Internet and browsing simple Web sites. Users join, interact with and enjoy social Web sites and online communities such as Facebook and MySpace, photo and video hosting Web sites such as Flickr and YouTube, streaming music programs such as Spotify and Last.fm, application stores such as the Apple App Store, online banks and e-commerce businesses such as PayPal, e-government sites, and so forth.

The process is quite simple. Users create a new account on any of these featurerich content and service providers by filling in a registration form and providing a few personal details. Additionally, by accepting the default service privacy policy, users may allow the provider to share these details with the outside world. At the end of the process, the user is allowed to access and enjoy the provider's site.

The amount of scattered personal information begins to grow as users repeat this simple process with different providers. As a result, some undesirable problems can arise: not only the most obvious of bad user experience (users have to remember different logins and passwords), and increased risk of identity theft, but, eventually, data privacy concerns. In this context, we understand privacy as someone's right to keep their personal information and relationships secret and thereby reveal themselves selectively.

In truth, the privacy concerns might not be a problem. Legislation usually forces providers (to different extents, depending on the jurisdiction) to handle user data in accordance with the law. Thus, service providers generally offer different mechanisms and custom tools to manage user data. However, the resulting heterogeneity is a huge disadvantage for users who wish to actively manage and control their personal information. As concluded by a thorough analysis of 45 social networking sites [START_REF] Bonneau | The Privacy Jungle: On the Market for Data Protection in Social Networks[END_REF], "privacy in social networks is dysfunctional in that there is significant variation in sites' privacy controls, data collection requirements, and legal privacy policies".

In summary, users currently lack a simple mechanism to verify what personal information is available on the Web, how it is used and how they can modify, update or delete it. Our vision is that in the short run privacy awareness will rise much higher as a result of the lack of comprehensive solutions. Thus governments and individuals alike will demand simple tools to govern the use and release of their personal information. In this article, we introduce a solution that aims to address some of these problems by enabling users to manage their personal data privacy in a simple and efficient way.

The remainder of the paper is organized as follows. First, in section 2 and 3 we describe the main approaches to identity management and stress the differences between them regarding privacy control. Then, section 4 details the solution that we have implemented to enable users to manage their personal data privacy in a simple and efficient way. After that, section 5 describes the validation we have conducted. Finally, section 6 analyses the state of the art of the related work and section 7 concludes the paper.

Network-Centric Identity Management

Identity Management commonly refers to the processes involved in the management and selective disclosure of user-related identity information, either within an institution or between several entities, while preserving and enforcing both privacy and security requirements. Identity management systems can be classified according to several different criteria. A common taxonomy distinguishes networkfrom user-centric approaches. With regard to the former, the first comprehensive specifications were created by the Liberty Alliance Project [2], a business alliance established in 2001, which has been recently succeeded by the Kantara Initiative [START_REF][END_REF]. Its early work was followed by others such as SAML 2.0 (Security Assertion Markup Language) [START_REF] Cantor | Assertions and protocols for the OASIS Security Assertion Markup Language (SAML) Version[END_REF] and WS-Federation [START_REF]Web Services Federation Language (WS-Federation) Version 1[END_REF].

The Liberty approach to identity federation and identity-based web services associates service providers with trusted domains (identity networks), which are supported by Liberty technology and operative agreements through which trust relationships are defined between providers. The identity network infrastructure supports users in transacting business with associated providers in a secure and apparently seamless environment. Each company maintains its own customer accounts, including relevant identity resources. Users can federate (link) accounts at different providers using an opaque pseudonym, which enables a single sign-on between providers and allows for the secure sharing of identity information.

Some entities may focus on managing these federations, as well as providing ancillary services:

• Identity Providers (IdP) know all users and service providers within the identity network and their affiliations. They also know how to authenticate users; thus, they can certify a user's identity to any provider. Whenever users want to access a service provider, they will be redirected to the IdP, where they will be authenticated. Once a user has successfully logged in, the IdP will send a statement back to the service provider containing information related to the identity of the user (pseudonym), information about other entities within the identity network and the credentials needed to access them. • Discovery Services (DS) record where the users' identity resources are stored within the identity network. When a service provider wishes to find any user's information it sends a query to the DS, which returns the endpoint reference for that resource and a valid credential for one-time access. In the Liberty context, a service provider is a Web service that acts with a certain identity resource to retrieve information about an identity, update information about an identity or perform an action for the benefit of some identity. A service provider may play the roles of both an identity-based Web Service Consumer (WSC) or an identity-based Web Service Provider (WSP). WSPs usually aggregate several identity resources into an identity profile (e.g., a personal profile or address book). The Liberty protocol that allows WSCs to access WSPs to query/update/delete personal data on behalf of a user is called the Data Service Template (DST) [START_REF]Liberty ID-WSF Data Services Template Specification[END_REF].

Within a given Liberty-based identity network, privacy is supposed to be handled by the user at each WSP (and not at the IdP/DS level). From that point on, the WSP is responsible for managing user privacy settings and preferences. The method for choosing and recording privacy settings is outside the scope of the Liberty specifications.

User-Centric Identity Management

Network-centric identity management approaches, such as the one proposed by the Liberty Alliance, have failed to reach the interest (and trust) of users, becoming constrained to the enterprise or governmental domains. For years, companies (especially telecommunication operators) have controlled user attributes: they know who you are, what is done with some of your identity-related information, who is using it, how and for what. Fortunately now, multiple service providers populate the Internet without being associated to any operator thus bringing the ex-isting identity management systems towards a new scope around the concept of user centricity.

The term user-centric was introduced in the identity management arena in about 2006. A user-centric identity management system "needs to support user control and considers user-centric architectural and usability aspects" [START_REF] Bhargav-Spantzely | User centricity: A taxonomy and open issues[END_REF]. Two main principles support user-centric identity management:

• The user is in the middle of a data transaction. Any information that flies between any entity pass through the user as a must condition, who has the power of consenting the transaction. • Huge scale advantages, since the identity provider does not need to know about every service provider, the user directly deals with them. The identity provider can simply be used to validate the information that will be sent to the service provider. User-centric identity management principles can be implemented by different means but the most popular ones can be divided into two categories, namely: URL-and card-based systems.

• Simple URL-based systems are decentralized and use URLs as users' identifiers. Compatible service providers accept identifiers created by a trusted entity (the identity provider); users are free to choose any identity provider to create an identity. The security of the transaction depends on how much the user relies on her identity provider. This is precisely one of the drawbacks of this approach. Malicious identity providers may give a false trust feeling, allowing unaware users to gain access to malicious service providers. Once inside the service provider, the victims can be easily cheated taking advantage of a false security feeling. Some examples of URL-based systems are OpenID [START_REF]OpenID Web site[END_REF] and LID (Light-Weight Identity) [START_REF]Light-Weight Identity Web site[END_REF]. • Identity card-based systems are built using the information card metaphor [START_REF]Identity Metasystem Interoperability Version 1[END_REF]. Although there are different definitions of this concept, the simplest could be that expressed by the Information Card Foundation [11]: "Information Cards are the digital version of the cards you carry in your purse or wallet today. You use them with a new kind of digital wallet called a selector." Selectors are pieces of software that complement Web browsers and allow users to choose the information card that will be supplied to service providers upon access. Depending on the user identity information that the service provider requires, the user chooses a certain information card. In these systems users decide, using a single interface (the card selector), which pieces of their identity they share with a given service provider. This approach gives users excellent control over their identity resources: they can assume at least partial control over their privacy, while enjoying enhanced usability. Additionally, card-based systems provide user with a consistent user experience. No matter what service provider is being used or what type of identity information is being enclosed towards them. In general, users interact with the same type of identity managers for every identity transaction they do. This is an important difference with respect to the network centric identity management scenario, where each service provider provides its own user interface which means the user is learning a new interface, sometime simply for using it only one time (for instance, at registration time). Examples of identity card based systems are Higgins [START_REF] Higgins | [END_REF] and Windows Cardspace [START_REF]Windows Cardspace[END_REF]. However, several security and privacy issues arise in information card based systems [START_REF] Alrodhan | Addressing privacy issues in Cardspace[END_REF]. Firstly, the identity providers are aware of the service providers to which the user attempts to log in, so malicious identity provider can learn about the behavior of the users on the Web. Secondly, and even more important, is the problem of the reliance on the user's judgment of the trustworthiness of the service provider. This means that if a service provider is not trustworthy, it could gather information about users and potentially use this in unauthorized ways. In both URL-and card-based approaches, the user identity information sharing happens in the foreground, since the user must be online and the service provider must actively request this information. This might be seen as a major handicap since users must be online and connected with the consumer service provider. Additionally, users cannot configure default privacy preferences to infer automated decisions regarding the release of their identity information. Instead, users must always give explicit permission for the release of information on a per-request basis.

Furthermore, it is unrealistic to expect that all user-related data are reachable through a user agent. Consider, for instance, information such as cellular networkbased location information. Moreover, consider identity-based services such as sending an SMS or billing the user on behalf of a third party. These are identitybased services that only a specialized identity-based service provider can offer, preferably within a trusted domain.

Self-service Privacy in Practice

We feel that network-centric identity management solutions are essential to manage some identity information and identity-based transactions. However, a usercentric approach to privacy enabling consistent user-experience is still required in order to provide users with adequate control of their information. Therefore we introduce a solution that merges both approaches, providing a user-centric privacy approach to a network-centric identity management solution to put the concept of Self-Service Privacy into practice.

Fig. 1 introduces a high-level view of a network-centric identity management architecture consistent with the Liberty Alliance specifications. A new entity has been added to this architecture, namely Privacy Controller (PC). The PC joins the identity network so that its users can federate (link) their accounts with those they have in other providers (using pseudonyms).

Using this new entity users are able to: 1. Retrieve a global view (snapshot) of their identity resources across different nodes of the identity network to understand which identity resources are stored, where they exist and their specific values. Users are also allowed to modify and delete any data. 2. See the history of how their identity resources have been used, i.e., what entities have requested them, when, the outcome of each request, etc. 3. Govern the future use and release of all identity resources by setting privacy preferences.

A generic requirement for all scenarios is that the PC must be authenticated, on behalf of the user, against the identity network in order to gain access to participating entities. The authentication is carried out against the IdP following standard Liberty protocols (Fig. 1, flow 0) using the pseudonyms obtained during the federation process. At the end of the authentication process the PC obtains an endpoint reference and credentials to access the DS.

Apart from these interactions, Fig. 1 also shows some other information flows. There is a communication flow between the user and the PC through a Graphical User Interface (GUI). The PC shows information to users and, in response, users take certain actions and decisions, which are sent back to the PC in order to drive the aforementioned flows.

Flows labelled A, B and C correspond to standard protocols as defined by the Liberty specifications: (A) a WSP informs the DS that it is storing an identity resource for a certain user; (B) a WSC queries the DS to discover which WSP stores selected identity resources about a user and also asks the DS for credentials to access them; and (C) a WSC uses the credentials retrieved in (B) to attempt to access an identity resource stored in a WSP. The following sections further elaborate on each particular scenario in order to describe the functionality that allows user-centric privacy management of distributed personal information.

Providing a Snapshot of Distributed User Identity Resources

Our first sample scenario is a combination of two major flows. Firstly, users see an overall picture of the distribution of their identity resources (Fig. 2, steps 0 to 4). Through this flow, the user is able to determine which parties are hosting user resources and what kind of resources are being stored. Once the users have seen the overall set of identity resources, they can choose to manage (modify or delete) any or all of the stored data (Fig. 2, steps 5 to 11). The PC performs as a Liberty WSC to query or update a WSP using the DST protocol. The PC receives the end-point reference and the credentials needed to access the WSP each time information about identity resources is retrieved (Fig. 2, step 3).

Fig. 3 shows a screenshot of the user interface that we have implemented for the PC. It is an example of the personal data that a user has stored in two different WSPs (iProfile and myPaymentBroker). Specifically, it indicates that myPay-mentBroker stores two personal resources (name and credit card) that the user can edit and modify.

Retrieving the Usage History for Identity Resources

In this scenario a user wants to know the usage history of one of their previously obtained identity resources. The PC shows the usage history for that resource with details about the resource type and value, timestamps of access and all WSCs that accessed the resource. Further information can be presented if available, such as privacy protection commitments made by the requestor, or conditions on the release of the information.

Fig. 4 shows a screenshot of the user interface that we have implemented. It shows the services that have requested access to an identity resource (credit card details stored at myPaymentBroker), for what purpose, the timestamp of the request and the outcome of the process (shown with self-explaining icons).

Fig. 4. Screenshot of the PC showing a usage history for a personal data

There are several approaches to gathering usage history. An approach based on proactive notifications from the WSP that stores the identity resource to the PC is not viable because it might cause scalability and performance problems in the event of large bursts of notifications. These problems can be reduced using thre-sholds and timers to smooth out the data flow. Nevertheless, this mechanism is always WSP-initiated (push mode), preventing the PC from requesting information at will.

A better approach is to extend the Liberty identity profiles with information that registers the use of the identity resources. These records can be considered an extension of the information in a profile since they add relevant information about the retrieval of identity resources. As in the previous scenario, the PC uses the DST protocol to retrieve this information. The main benefit of this approach is that it can be PC-initiated (pull mode). This means that the information is retrieved whenever the PC requires it and is limited to PC requests. Thus, we do not foresee any scalability or performance issues. Additionally, the Liberty specifications for identity services consider extensions of the identity resources, and thus our solution can be considered Liberty-compliant.

We assume at this point that every WSP registers the request and release of the identity resources it stores. This information could be used, for example, for future audits (in fact, this may be compulsory under the laws in certain countries). The minimum information to be recorded at the WSP every time a WSC tries to access an identity resource includes:

• UserID -to identify whose information is being accessed. This is the user alias in the WSP. • IdentityResourceType -to identify what information has been accessed. This is a subset of the information included within the identity profile. • WSC -to identify who requested the information.

• Other information -for example, the time of access. Other relevant information that could be useful for future requirements may be the intended use of the information retrieved, whether the WSC will share it with third parties, and the promises the WSC makes about any future use of the requested information.

Enabling User-Centric Privacy Management

This scenario elaborates on the mechanisms that allow users to centrally manage their privacy preferences. The scenario is composed of four major steps: 1. The user selects a specific identity resource stored in a WSP and reviews its privacy preferences. 2. The PC retrieves and displays the privacy preferences associated with that identity resource. 3. The user modifies the privacy preferences and the PC updates them in the WSP. 4. The WSP enforces the privacy preferences whenever a requestor tries to access the identity resource. Initial preferences might have been set by the user at the service provider's site or by the service provider itself using default values, or they can even be undefined. Privacy preferences follow a default-deny pattern: An empty set of prefe-rences implies that all requests should be denied (other than those issued by the PC itself). Each preference added to the set grants a specific type of permission.

The PC allows users to change the policy applied to an identity resource by selecting one of a set of pre-defined policies, each of which is described in natural language. This natural language description is mapped to a specific policy described in machine-oriented privacy policy expression language. Policies are hierarchical so that it is easier for users to compare them and choose the one that best meets their needs. This approach benefits from simplicity and usability because users do not have to deal with technical policy details.

Additionally, the PC allows users to define specific options for the use and release of each data element from their profile (Fig. 5). Although this approach provides greater flexibility, it also poses some usability risks, since only advanced users understand (and probably want to know) the detailed meaning of each available policy. Therefore, this is offered only as an advanced option. The variables that define a custom privacy preference include the identity resource, the requestor of the identity resource, the operation requested, the permission level chosen by the user and the resource owner identifier. The identity resource values are constrained to those defined within the identity profile provided by the WSP. The requestor can be any WSC from within the identity network. The operation values might be those defined in a DST protocol (i.e., query, create, delete, modify and subscribe). The permission can be set to grant, deny or askMe, when the user prefers to decide on a per-request basis.

Since the number of rule combinations will increase exponentially (number of requestors multiplied by number of identity resources), we allow for simpler options such as allow anyone to query this specific identity resource or allow just this WSC to update any identity resource. Therefore, options such as all or just one are supported.

The solution presented in this article does not impose any specific privacy preference language. However, we have evaluated several different alternatives in terms of the following requirements. On one hand, we must allow users to easily describe their preferences and on the other hand, we have to translate these preferences into policies that a Web service provider can enforce. For our prototype we have chosen the Extensible Access Control Markup Language (XACML) [START_REF]Extensible Access Control Markup Language (XACML)[END_REF] since it allows for easy governance of information once the policy has been defined. However, it poses certain usability difficulties in terms of limiting how a user can express this information. Previous paragraphs have described the measures that we have taken to address these problems.

User-generated privacy preferences (and their expression in the form of privacy policies) govern user identity resources. Thus, privacy policies must be associated with the identity of a user or, more specifically, with the identity resources that they govern. Our solution realizes this association by extending the generic identity profile as defined by Liberty with a privacy policy description schema. Thus, the schema is defined once and can be added to any existing Liberty-based identity profile. Additionally, this approach allows the PC, using the DST protocol, to set (Fig. 6, steps 0 to 3) and query (Fig. 6, steps 4 to 8) the privacy policies associated with a given identity resource.

To set a privacy policy, the PC must play the role of a WSC and include the privacy policy as part of the Create or Modify element that is sent to the WSP to store the identity resource and its associated privacy policy. This mechanism does not require any changes in current DST protocols, as the policy is transmitted in the same way as any other information, namely, in the body of the message. On arrival, the WSP retrieves the policy and stores it in a policy repository.

The PC retrieves privacy policies that are associated with an identity resource using the DST protocol as well. In this case, however, the PC uses the Query operation. Once the policy has been retrieved, it is translated back into privacy preferences so that the user can understand it. Finally, privacy policies are enforced whenever a request for an identity resource is received by a WSP. To meet this requirement we have introduced three functions in the WSP (Fig. 7): Policy Enforcement Point (PEP), Policy Decision Point (PDP) and Policy Repository (PR).

The PEP catches the incoming identity resource request and retrieves information about the requesting entity (requestor WSC), the requested identity resource, the operation and the user to whom it refers. Then the PEP creates a request for the PDP with the information retrieved. When the PDP receives the request it retrieves the applicable policies from the PR and compares the request and the policies before sending a decision back to the PEP. When the PEP receives the decision it can allow the requested resource retrieval, deny the operation or pause the operation until further actions have been completed (e.g., asking the resource owner for permission). The last step can be implemented using a Liberty Interaction Service [START_REF]Liberty Id-WSF Interaction Service Specification[END_REF].

Validation

To validate our approach we have developed an identity network made up of five entities (Fig. 8):

• A standard IDP/DS that provides the basic infrastructure as defined by the Liberty Alliance architecture and protocols. • Two modified identity-based WSPs. The first one, namely iProfile, is a personal profile containing postal address information. The second one, myPay-mentBroker, is an identity-based payment service that stores credit card numbers. These WSPs have been modified to incorporate our contributions. • A standard identity-based WSC; an online shop called goShopping. Once a user selects a product and decides to buy it goShopping queries myPay-mentBroker to retrieve the credit card number to charge the user and, if successful, then queries iProfile to retrieve the delivery details. • A Privacy Controller, which allows users to centrally govern their identity information in the identity network, to trace the use of the information, and to set privacy policies for its future governance. Our solution does not introduce any impact on standard-based IDP/DS or WSCs implementations. Regarding WSPs, they must enforce privacy policies and log transactions related to the release of personal information, which anyway may be compulsory according to privacy protection laws in some countries. Additionally, an extension to identity data services is needed, which has been done following Liberty recommendations. The extension defines a container for privacy policies governing the use of the information contained within the profile. This extension must be included in any data service supporting privacy policy management.

Liberty-based entities were developed using the open source access management and federation server platform and libraries Open Web SSO (OpenSSO) [START_REF] Moses | [END_REF] by Sun Microsystems. With regard to the management and enforcement of privacy policies, we have used an open source implementation of XACML [START_REF]Sun's XACML Implementation[END_REF], also by Sun Microsystems. This implementation provides support for creating privacy policies in the PC and managing and evaluating requests against policies in the WSPs.

The PC and the WSC were deployed on a Tomcat server, while the IDP/DS and the WSPs were deployed in a Glassfish Server running the OpenSSO platform. In our demonstration scenario, a user firstly signs in the PC to obtain a snapshot of her information distributed in the identity network (Fig. 3), that is, the personal information stored in iProfile and myPaymentBroker. From the PC interface, the user can also modify the values stored.

Additionally, the user can also review the history of use of any piece of this information. For example, Fig. 4 shows the screenshot that the user sees when she chooses to review the history of use of her credit card details stored at myPay-mentBroker.

Since goShopping has been denied access to the credit card details, the user is not able to buy at this online shop. Thus, using the PC interface, the user modifies her privacy preferences. Fig. 5 shows the screenshot that the PC presents to set new privacy preferences regarding her credit card details. Once the new preferences are set, the user is able to go back to goShopping and successfully carry out the purchase.

Related work

The approach to identity management described by Liberty Alliance specifications is a solution for the problem of how to manage shared identity resources in a network-centric identity management system. However, this solution does not allow for user-centric management of the scattered users' identity resources and privacy settings in the identity network. The Liberty approach forces users to know where every identity resource is stored and to set privacy preferences for every single node of the identity network. Moreover, it cannot possibly provide overall information about the flows of identity resources among entities since each entity only knows about others to which it has released information or from which it has retrieved information.

Recently, Liberty has announced the release of the Identity Governance Framework (IGF) [START_REF]Liberty IGF Privacy Constraints Specification, Version 1.0[END_REF], which aims to describe detailed privacy constraints and the mechanisms by which entities within an identity network can interact. IGF privacy constraints describe fundamental restrictions regarding the propagation, usage, retention, storage and display of identity data for entities involved in consuming and providing them. Unfortunately, the IGF is enterprise-oriented and thus does not allow for user-centric privacy management.

A promising initiative for user-centric privacy management is the PRIME Console [START_REF] Leenes | PRIME White Paper, Version 3. PRIME Project[END_REF], which is an interface to the user's identity management system. It allows users to create partial identities (pseudonyms) and associate personal data with each of these identities, assists the user in understanding privacy policies, makes decisions on the basis of the user's preferences and allows users to inspect the transaction history for their personal data. However, sometimes identity information is not initially disclosed by users. For example, in a network-centric identity system some entities can automatically retrieve and offer identity information regarding a user, such as geolocation. Therefore, the PRIME Console is not a comprehensive solution as it focuses only on user-centric identity systems and fails to support network-centric ones.

The HP Virtual Identity and Profile Broker (VIP Broker) [START_REF]HP Virtual Identity and Profile Broker[END_REF] provides a single, centralised point of access to distributed identity data, allowing users to monitor relevant information flows. With the VIP Broker, users can also configure release policies, which will be centrally enforced whenever a request for personal information is received. Unlike the VIP Broker, our solution distributes the policies to the custodians of the information. Thus, privacy preferences are applied wherever the information is stored, avoiding the need for an intermediate broker. This is convenient from a business standpoint, since service providers usually want to retain control of the distribution of any information they own. Recently, Google has announced the release of the Google Dashboard [START_REF]Google Dashboard[END_REF]. The dashboard lists some of the information associated with the Google services the user has subscribed and provides links to control their personal settings. However, unlike our Privacy Controller, Google Dashboard redirects the user to every service provider in order to modify the privacy preferences. Therefore, users are not provided with a comprehensive tool from where to centrally define their privacy preferences. In addition, users are not able to trace how their information has been used, which is one of the contributions of our proposal.

Conclusions

In this article we have presented a comprehensive solution, the Privacy Controller, to help users to actively control the privacy of their personal information while using services in the digital world. The Privacy Controller leverages various identity management technologies (consistent with the Liberty Alliance specifications) to help users understand how much personal information about them is being stored, who has accessed it and how it will be safeguarded in the future.

The lack of simple tools and inadequate privacy-awareness among users are two major obstacles that prevent the involvement of users in privacy control. Therefore, enhanced usability and better default settings play a fundamental role. We have described different measures that our Privacy Controller introduces to support users in defining their own privacy preferences. Nevertheless, we feel that there is room for improvement in this area and thus we are evaluating user modelling techniques that allow the automatic generation of user privacy preferences.

For our solution to be practical, collaboration and coordination with service providers is a must: Service providers would have to provide new interfaces and capabilities to allow external control of personal data. We envision that in the near term governments will force providers to declare the personal information they store and to provide standards-based mechanisms to interact with it. As a matter of fact, in Europe recent privacy protection initiatives [23] have introduced legislative principles such as 'privacy by design' and 'accountability'.

In the future we hope to extend the Privacy Controller to other identity networks such as social networks, which are huge and often unregulated sources of personal information. We feel that such Web sites urgently need mechanisms to provide semantic interoperability between different identity networks. The use of ontologies as information mediators might be a promising future direction.

Fig. 1 .

 1 Fig. 1. Overview of the Privacy Controller.

Fig. 2 .

 2 Fig. 2. Sequence diagram for the retrieval and management of identity resources.

Fig. 3 .

 3 Fig. 3. Screenshot of the PC providing a snapshot of distributed personal data.

Fig. 5 .

 5 Fig. 5. Screenshot of the PC to control privacy preferences

Fig. 6 .

 6 Fig. 6. The Privacy Controller sets and queries privacy policies.

Fig. 7 .

 7 Fig. 7. Sequence diagram for privacy enforcement.

Fig. 8 .

 8 Fig. 8. Demonstration scenario for the prototype validation.

Acknowledgments

This work has been partially supported by CDTI Ministry of Science and Innovation of Spain, as part of the SEGUR@ project (https://www.cenitsegura.es/), under the CENIT program, CENIT-2007CENIT- /2004. .