Quantifying Robustness of Trust Systems against Collusive Unfair Rating Attacks Using Information Theory

1 Introduction

Trust and reputation systems are designed to help users select trustworthy agents for interactions. Due to their rising popularity (e.g., e-marketplaces), various attacks have been discovered, and are threatening the security of these systems. Considering the threats, trust and reputation systems should be designed to mitigate these attacks (i.e. be robust). In this paper, we analyze collusive unfair rating (CUR) attacks.

CUR attacks are among various unfair ratings attacks, which aim to influence the trust evaluations made by users. CUR attacks differ from other unfair rating attacks, as malicious users (attackers) collude to achieve a same goal. Robustness issues of trust and reputation systems against collusion attacks are extensively studied. Some work focuses on detection of collusive unfair rating behaviours, while others aim to design mechanisms to defend against such attacks.

There can be various ways of colluding. Designers of trust and reputation systems sometimes verify the robustness only under specific CUR attacks [Qureshi et al., 2010; Swamynathan et al., 2010; Li et al., 2013; Weng et al., 2010]. This results in the following problems: first, these systems can only be known to be robust against the assumed attacks. Hence, one cannot know whether they are also robust to all other kinds of CUR attacks. Second, comparing the robustness of two trust models under specific attacks is not fair. The designer may design a system to be robust against a given attack, and use that specific attack to compare his system with another. Such a comparison is biased in favour of the proposed system.

Considering these two problems, we argue that if the general robustness of a trust system against CUR attacks are measured, then it should be tested against the strongest CUR attacks. If a trust system functions well under the strongest attack, then it is generally robust. Otherwise, if trust systems are merely robust to some given CUR attacks, which they are tested against, then we need to be able to compare the strength of these attack(s). In both the cases, we need to measure the strength of CUR attacks.

In [Wang et al., 2015], we introduced information theory to identify and measure the worst-case (strongest) attacks by independent attackers. There, we focused on general robustness only, which depends on how effective the system is, given the strongest attacks. Here, we focus on how strong arbitrary attacks are (also using information theory), which allows us to reason about the quality of the validation of a trust system. Moreover, we shift focus from independent attackers to colluding attackers (including Sybil attackers). The formalism from [Wang et al., 2015] must be fundamentally altered to allow for measurements of coalitions of attackers.

Contributions: We extend the methodology from [Wang et al., 2015] to 1) quantify and compare CUR attacks found in the literature (Section 4), 2) quantify types of CUR attacks (Section 5), and 3) identify the strongest possible CUR attacks. Doing this, we found 1) attacks from the literature are not suitable to stress-test trust systems, 2) strongest CUR attacks are not considered in the literature, 3) always assuming the strongest attacks barely reduces the effectiveness, but greatly increases the robustness of trust systems. We consider the results from [Wang et al., 2015] explicitly as a special case of CUR attacks.

2 Preliminaries

Our approach uses concepts from information theory:

Definition 1. (Shannon entropy [McEliece, 2001]) The Shannon entropy of a discrete random variable X is:

The Shannon entropy measures the uncertainty of a random variable, which reflects the expected amount of information carried in it. W.l.o.g. let 2 be the base of the logarithms. Since x log(x) is a common term, we introduce the shortcut f (x) = x log(x). For practical reasons, we let 0 log(0) = 0.

Definition 2. (Conditional entropy [McEliece, 2001]) The conditional entropy of discrete random variable X given Y

The conditional entropy measures the uncertainty of a random variable, given that another random variable is known. In other words, it measures the reduction of the expected information of a random variable when another random variable is revealed. Note that H(X|Y ) = H(X) if and only if X and Y are independent random variables, and 0 ≤ H(X|Y ) ≤ H(X).

Definition 3. (Joint entropy [Plunkett and Elman, 1997]) The joint entropy of discrete random variables X, Y (given Z) is:

The joint entropy of X and Y is at most equal to the sum of the entropy of X and Y , with equality holds only if X and Y are independent.

Definition 4. (Information Leakage) The information leakage of X under Y is given as: H(X) -H(X|Y ).

Information leakage measures the gain of information about one random variable by learning another random variable. This definition coincides with mutual information [Papoulis and Pillai, 2002]. Information leakage is zero, if and only if the two variables are independent.

Definition 5. (Hamming distance [Hamming, 1950]) The Hamming distance between a = a0, . . . , an and b = b0, . . . , bn, denoted δ(a, b) is the number of 0 ≤ i ≤ n where ai ̸= bi.

Theorem 1. (Jensen's inequality [Jensen, 1906]) For a convex function f:

where equality holds iff x1 = x2 = . . . = xn or f is linear. Two instances of convex functions are f (x) and - log(x).

For brevity, we may use X to represent a collection of random variables, e.g., {X1,X2, . . . ,Xn}. Moreover, we may write p(a) to mean p(A = a), or even p(a) to mean p(A1=a1, . . . , An=an).

3 Modeling CURAttacks

In trust systems, users make trust decisions based on the available information. Part of such information comes from ratings. A user aims to learn from ratings to make deductions about an advisor's real opinion. For the user, an attacker hinders such learning, hiding its real opinion. In [Wang et al., 2015], we proposed to quantify how much a user can learn as the information leakage of the ratings, which can then be used to measure the strength of the corresponding attacks.

From an information theoretic perspective, advisors can be seen as a (noisy) channel. See Figure 1. The opinions of the advisors are being output as ratings, where the ratings need not match the true opinions (i.e., noise). Like in digital channels, not just the amount of noise matters, but also the shape of the noise. Thus, not just the amount of attackers matters, but also their behaviour. The difference in noise-per-advisor is often ignored in the literature, potentially skewing analysis of the attacker-resistance.

However, in [Wang et al., 2015], only the strongest independent attackers are considered. In this paper, we extend the quantification method there to cover 1) collusive attackers and 2) non-strongest attacks. To measure the strength of a collusion attack, we need to measure the information leakage of the coalition as a unit. The ratings provided by colluders are interdependent, (potentially) revealing extra information to the user. Hence, when measuring the information leakage of a coalition, we cannot simply sum up the information leakage of individuals. (as can be seen below)

Example 1. Consider a trust system with 4 advisors, 2 of which are colluding attackers. 1 Take the perspective of a user; he gets a rating from each of the advisors about their opinions of the target, and he does not know which two advisors are colluding. We assume that the opinions are positive and negative with 50% probability each. Non-colluding advisors always report the truth. Colluding advisors have one shared strategy. Here, the strategy dictates that if the attackers agree, then they both lie, and if they disagree, then they report the truth. The user received four ratings, three positive and one negative.

1 Note that there exist many methods which can estimate the number of colluders in a system [Liu et al., 2008; Allahbakhsh et al., 2013]. Hence we make the reasonable assumption in this work that the number or percentage of colluders is known.

We model the attackers' strategy in this example with the matrix in Table 1. The left column represents the real opinions (observations) of the two colluding advisors, represented as the combinations of positive: 1 and negative: 0. The top row represents the ratings which are in the same form. The cells provide the probability that the attackers report the column's rating, given the row's observation.

The user wants to learn about the observations of all advisors from the received ratings. We use random variables Oi,Ri, i ∈ {1, . . . , 4} to represent the observation and the rating of advisor i respectively. And we use random variable C2 to represent two colluding advisors.

Before receiving the ratings, the information that the user has about the observations can be represented using joint entropy (Definition 3): H(O1,O2,O3,O4). The joint entropy expresses the uncertainty associated with these four observations. Given the ratings, the information the user has of the observations becomes the conditional entropy: H(O1,O2,O3,O4|R1,R2,R3,R4). Thus, the information that the ratings leak about the observations (information leakage) can be represented as follows:

The conditional entropy of observations given the ratings is:

All combinations of O1,O2,O3,O4 are captured in o1,o2, o3, o4. The second equality follows from the law of total probability.

The entropy H(O1, O2, O3, O4) = log(24 ), since each Oi is positive or negative with exactly 50% probability. By Definition 4, therefore, we get log(24 ) - (-1/2 log(1/12)) ≈ 2.21 bits of information leakage.

We now consider more general collusion attacks from the perspective of users. There are m advisors, k attackers (0 ≤ k ≤ m), and we assume non-attacking advisors always report the truth. The random variable Oi represents the opinion of the ith advisor. We assume maximum entropy for the random variables O, meaning H(O) = m. Similarly, Ri represents the rating of the ith advisor. For non-attacking advisors, Oi = Ri. For attacking advisors, we use σo,r to represent the probability that attackers that have observed o provide the ratings r. The random variable C represents the coalition; its outcomes are, therefore, sets of advisors. The probability that a set c of k advisors are colluding is p(c) = 1/(mk ). The strategies of attackers are expressed using the matrix in Table 2. The sum of each row equals 1, since, given an observation, the sum of the probabilities of all ratings is one.

The information leakage of all advisors' observations given their ratings is

1 · · · 1 σ1···1,0···0 · · · σ1···1,1···1

Table 2: Strategy matrix of general collusion attacks

The conditional entropy of observations given ratings is as follows:

The general modeling and measurement of collusion attacks in this section can give us a way to quantify different attacks in the literature.

4 Quantifying CURAttacks

Collusive unfair rating attacks have been studied by many researchers [Jiang et al., 2013; Swamynathan et al., 2010; Li et al., 2013; Weng et al., 2010; Jurca and Faltings, 2007]. They propose various methods to counter such attacks, e.g., detection based approaches [Qureshi et al., 2010], incentive based approaches [Jurca and Faltings, 2007], and defensemechanism design based approaches [Swamynathan et al., 2010; Jiang et al., 2013]. Based on simulations or experiments, they verify how effective their methods are in minimizing the influence of collusion attacks, namely improving the robustness of trust models. Sometimes such verification only covers specific attacks that are assumed or designed by the researchers themselves [Qureshi et al., 2010; Swamynathan et al., 2010; Li et al., 2013; Weng et al., 2010]. To compare the robustness of two trust models under specific attacks is unfair. One that fails under these attacks may behave better for some other attacks.

We argue that to equitably compare the robustness of two trust models, we need to compare the strength of attacks that they are tested against. A trust model should be considered more robust if it is verified under stronger attacks. From the section above, we know that information leakage of ratings can be used to measure the strength of attacks. We apply the method to some attacks found in the literature.

The authors in [Weng et al., 2010] propose to mitigate the influence of unfair ratings by helping users to evaluate the credibility of the advisors, based on which to further filter and aggregate ratings. For collusive unfair ratings, the authors only consider the case in which malicious advisors provide unfairly high ratings for the colluding target, to boost its trustworthiness - ballot-stuffing. When evaluating the method, such attacks are configured as various percentages of attackers, namely 20%, 40%, 60%, 80%.

We use parameter m=100 to represent the number of all advisors in the system, then the number of attackers can be 0.2m, 0.4m, 0.6m, 0.8m. The expected information leakage is 61.13, 39.69, 23.72, 10.84 bits, respectively 2 .

The "FIRE+" trust model is proposed in [Qureshi et al., 2010]. FIRE+ aims to detect and prevent collusion attacks. It considers two kinds of collusion attacks: in the first type, advisors collude with the target under evaluation, providing false positive ratings to promote the target as trustable. In the second type, advisors may collude to degrade the target, by providing false negative ratings. When evaluating the performance of "FIRE+", the authors consider three types of advisors: 10 honest advisors who always report the truth, 20 attackers that report all others as trustworthy, and 20 attackers that report the opposite of the truth. The information leakage for the second type of advisors is 6.79 bits1 , and for the third type of advisors is 22.52 bits 3 .

The authors in [Li et al., 2013] design a SocialTrust mechanism to counter the suspicious collusion attacks, the patterns of which are learned from an online e-commerce website. Instead of filtering collusive unfair ratings or preventing collusion behaviours, SocialTrust adjusts the weights of detected collusive ratings based on social closeness and interest similarity between a pair of nodes.

To evaluate the mechanism, it considers three attack scenarios: pairwise collusion in which two agents promote each other, multiple agents collusion in which agents all promote a boosted agent, and the collusion in which multiple agents promote each other. All the three scenarios are essentially about colluders ballot-stuffing to boost trustworthiness of other attackers that are under evaluation. The attacks for testing are configured as 9 pretrusted nodes and 30 attackers. Based on Theorem 3, the information leakage is 5.96 bits1 .

The authors in [Swamynathan et al., 2010] aim to design a reliable reputation systems against two leading threats, one of which is user collusion. For performance evaluation of their system, the three same collusion scenarios as in the SocialTrust are considered. For the configuration of attacks, the percentage of attackers are varied from 10 to 50 percent. Based on Theorem 3, the information leakage is between 31.33 bits (for 50% attackers) to 75.97 bits (for 10% attackers)1 .

In summary, the CUR attacks used above are essentially ballot-stuffing and lying. From the quantification, we get following results: 1) referring to [Swamynathan et al., 2010; Weng et al., 2010], the information leakage of ballot-stuffing CUR attack decreases with the increase of the percentage of attackers. 2) Given the same number of attackers, the attack strategy of ballot-stuffing leads to much less information leakage than the strategy of lying (6.97<22.52 bits).

By relating these results with the strength of attacks, we get following conclusions. The ballot-stuffing attack gets stronger as the number of attackers increase. On the other hand, with the same amount of attackers, ballot-stuffing attack is stronger than the lying based attack.

2 The computation of these values is omitted, as their generalization is provided in Theorem 3.

3 The computation of these values is omitted, as their generalization is provided in Theorem 4.

5 Quantifying Types of CURAttacks

The papers we discussed in the previous section only consider specific attacks in the verification of trust systems. As a result, we cannot know whether these systems are also robust against other attacks. We argue that to verify the robustness of a trust system, it should be tested against all kinds of attacks. However, this is not generally feasible. Therefore, we identify the strength of each attack type (and if it is a range, we identify the strongest attack within the type). To verify the robustness of a trust system to a type of attacks, we propose to test it against the strongest attack in that type.

We summarize various types of collusive unfair rating attacks from the literature. Information leakage measures the strength of the attacks. The information leakage is totally ordered, with an infimum (zero information leakage), therefore, there exists a least element. We refer to these least elements as the strongest attacks.

The types of collusion attacks are summarized as follows:

• I There is no colluding among malicious advisors, and they are behaving independently.
• II All attackers either boost (affiliated) targets, by unfairly providing good ratings (ballot-stuffing), or degrade (unaffiliated) targets, by unfairly providing bad ratings (badmouthing).
• III All the colluding advisors lie regarding their true opinions. As ratings are binary, they always report the opposite.
• IV The colluding advisors coordinate on their strategies in any arbitrary fashion.

The first attacking type is a special case of the collusion attacks, namely those that coincide with the independent attacks. The second type of attacks is commonly found in the literature, where all attackers are either ballot-stuffing or badmouthing (see, e.g., [Swamynathan et al., 2010; Weng et al., 2010; Li et al., 2013]). There are also papers considering the other two types of attacks [Jurca and Faltings, 2007]. The last type of attacks is interesting, since it covers the three preceding types, as well as all other conceivable types.

We use the general CUR attack model from Section 3 to quantify these types of attacks. We use m, k to represent the number of advisors and the number of attackers, and use 0 to represent negative ratings, and 1 to represent positive ratings.

In the first type of attacks, all attackers operate independently. Each attacker chooses to report the truth with probability q, and lie with probability 1 - q.

Proof sketch. Since, when δ(o, r) > k, p(o|r) = 0, wlog,

Moreover, since if ∃i̸∈cri ̸= oi then p(o|r, c) = 0, wlog, ∑c p(o|r, c)p(c|r) = ∑c:∀i̸∈cri=oi p(o|r, c)p(c|r).

Substituting p(r) by 1/2m, p(c|r) by 1/(mk ) and p(o|r, c) by (1 - q)d qd , we obtain the information leakage.

In the second type of attacks, we use x, (1 - x) to represent the probability that all attackers are ballot-stuffing and bad-mouthing, respectively. For x = 1, attackers are always ballot-stuffing and for x = 0, attackers are always badmouthing. To express this using the general attack model in Table 2, we assign the probability of "all ratings are 0" (meaning bad-mouthing) to be 1-x and "all ratings are 1" (meaning ballot-stuffing) to be x.

Before showing the next theorem, we introduce a shorthand notation. Let αk,h,y,0 = 0, let αk,h,y, = (hk)·y (mk)·2m-k and let βk,i,j,z = 1/2k - ∑kℓ=1 (iℓ) · f( z·( i-ℓ k-ℓ) z·( ik)·(1-z)·(jk)·2k ) + (jℓ) ·

f( (1-z)·(j-ℓ k-ℓ) z·( ik)·(1-z)·(jk)·2k ). And let i be the number of "1" ratings, j = m- i the "0" ratings, and Ri,j be the set of all ratings with i "1" ratings and j "0" ratings.

Theorem 3. If i<k, let z=0; if j<k, let z=1; otherwise, let z=x. The information leakage of any attack of type II, is m- ∑r∈Ri,j (αk,i,x,z + αk,j,1-x,1-z) · βk,i,j,z bits.

Proof sketch. Note that i < k and j < k cannot simultaneously be the case, since at least k attackers rated "1" or k attackers rated "0". If i < k, then the attackers must have degraded (and if j < k, then boosted). The analysis of these two cases contains the same elements as the general case, which we prove below.

If i ≥ k and j ≥ k, then the conditional entropy follows (via Definition 2), as - ∑r p(r) · ∑o f(p(o|r)). Remains to prove that p(r) = αk,i,x,z + αk,j,1-x,1-z and that ∑o f (p(o|r)) = βk,i,j,z .

The equality ∑o f(p(o|r)) = βk,i,j,z also follows from total probability over c via ∑o f(∑c p(o|r, c) · p(c|r)). Straightforwardly, p(o|r, c) = 1/2k , provided for all ℓ ̸∈ c, oℓ = rℓ, and zero otherwise. Furthermore, p((|r) = x (1-x)·(jk)+x·( ik) if for all i ∈ c, ri = 1, and symmetrically when for all i ∈ c, ri = 1. If neither is the case p(c|r) = 0. The equality ∑o f(p(o|r)) = βk,i,j,z follows by applying these substitutions.

The equality p(r) = αk,i,x,z + αk,j,1-x,1-z follows from simple combinatorics, given that p(r) = ∑c p(r|c) · p(c).

In the third type of attacks, with probability q, all attackers report their true opinion, and with probability 1 - q, they all report the opposite. In the strategy model, we assign probabilities of reporting the opposite ratings as 1 - q, and probabilities of other cases as q. Then we compute the information leakage as follows:

Theorem 4. The information leakage of the attack of type III, is m+ ((1- q) · log( 1-q (mk) ) + q · log q) bits.

Proof sketch. Either o = r, or δ(o, r) = k, since either all attackers tell the truth, or all lie. Wlog ∑o f(p(o|r)) = ∑o:δ(o,r)=k f (p(o|r)) + f (p(O = r|r)).

Straightforwardly, p(o|r) = 1-q (mk) , when δ(o, r) = k, and p(o|r) = q, when o = r; substituting these terms yields the theorem.

For q = 0 and k/m < 1/2, log((mk )) ≈ mH2(k/m), where H2(p) is the entropy of a bernoulli distribution with parameter p. Thus, for small k and x = 1, information leakage roughly equals m(1-H2(k/m), which models the entropy m transmissions of bits that arrive intact with probability k/m.

In the fourth type of attacks, attackers are allowed to take any strategies, including the cases when they coordinate on different strategies. We aim to find a range of the strength of all of these attacks:

Theorem 5. The information leakage of any attack of type IV, is between m and 2k ∑0≤i≤k (mi ) bits.

Proof sketch. The upper bound happens when H(O|R) = 0, which is satisfied R completely decides the value of O. The crux is the lower bound; the minimal information leakage of type IV.

No matter what the attackers' strategy matrix is, k attackers can change at most k values. Therefore, ∑o p(o|r) = ∑o:δ(o,r)≤k p(o|r). There are ζ = ∑ki=0 (mk ) possibilities for o given r.

By Jensen's inequality (Theorem 1):

The equality holds iff for all o with δ(o, r) ≤ k, p(o|r) is equal; meaning p(o|r) = 1/ζ iff δ(o, r) ≤ k. Note that the number of o with δ(o, r) ≤ k is the same for any r, hence the minimum of each H(O|r) is the same, allowing us to ignore p(r). Filling in p(o|r) = 1/ζ, the minimal information leakage can be computed: 2k ∑0≤i≤k (mi ) .

The corresponding strategy matrix that leads to the minimal information leakage can be easily derived:

where 0 ≤ i ≤ k represents the Hamming distance between observations o and ratings r. To give a concrete example of such a strategy, let there be 4 advisors, 2 of which are colluding, the strongest attack strategy is given in Table 3. Naively, one may expect the attackers to always lie, to ensure the probability that a given rating is truthful is half. However, each attacker in Table 3 reports the truth 3/11 times on average, disproving the naive view.

Finally, we show that attacks of types I, II and III are not the strongest attacks. In other words, the strongest attacks only occur in type IV (except in edge cases like k=1 or k=m):

Theorem 6. For 1 < k < m, there are attacks of type IV, such that every attack in type I, II or III has strictly more information leakage.

Proof sketch. The proof of Theorem 5 applies Jensen's inequality, to prove that setting all p(o|r) equal (when δ(o, r) < k) provides the optimal solution. Jensen's inequality is strict when not all those p(o|r) are equal. Thus, it suffices to prove that for types I, II and III, with 1 < k < m, p(o|r) ̸= 1/ζ.

For types I, II and III, there is only one degree of freedom (q, x and q, respectively). For no value for q or x, for all o with Hamming distance below k, p(o|r) = 1/ζ.

6 Discussion

We model a group of m advisors, containing k attackers, as a channel transmitting m bits, of which k bits are subject to noise (Figure 1). Like there are different types of noise, there are different types of attackers. We studied attack models found in the literature, and the types themselves. In this section, we analyze our findings, and put them into context.

The information leakage of the attacks from the literature (Section 4) is high compared to the minimum (e,g, FIRE+ provides 5.79 or 22.52 bits, whereas 0.03 bits is optimal). Higher information leakage means that it is easier for a user to learn from ratings. Models of attacks with high information leakage may not be suitable to stress-test a trust system, since it would be too easy to learn from ratings.

When interpreting these results, we must keep in mind that existing papers do not aim to minimize information leakage, but to faithfully model existing attacks. However, underapproximating attacks is undesirable. This is why we focus on the strength of attacks, even if minimizing the information leakage is not the original intention of the attackers. In fact, a robust system may never underapproximate the strength of attacks, linking robustness to the strength of attacks.

We now propose a method of designing robust trust systems based on the above. Given the attackers' behavior, trust evaluation becomes relatively simple. In [Muller and Schweitzer, 2013], the authors provide a general formula that allows mathematically correcting trust evaluations, given the attackers' behaviour. We propose to use computations in the formula, based on the assumption that the attackers' behaviour is the strongest possible attacks - minimal information leakage. Since such a model, by definition, can resist the strongest attacks, the system is robust. Whenever the system makes a trust evaluation, the actual information content of the evaluation can only exceed the systems' estimate.

The possible downside of assuming the strongest attacks, is that information available when attacks are weaker, is not being used effectively. However, the amount of information leakage when k ≪ m is high, even in the strongest attacks. When, on the other hand, k ≈ m, the information leakage is significantly lower in the strongest attacks. We argue, however, that if k ≈ m, it is unsafe to try to use the ratings as a source of information anyway. When the group of attackers is too large, no robust solution should use the ratings, as using the ratings would open a user to be easily manipulated. For small groups of attackers, the robust solution loses little performance, and for large groups of attackers, non-robust solutions are not safe. Therefore, we propose robust solution (and the strongest attack) to be the standard.

We distinguish four types of attacks. Attacks without collusion (I), attacks where the coalition boosts or degrades (II), attacks where the coalition lies (III), and the class of all attacks with collusion (IV). The former three are all instances of the latter. Attacks I, II and III deserve extra attention, since most unfair rating attacks in the literature are instances of them. However, while attacks I, II and III are interesting, they are trivially special cases of IV. Moreover, per Theorem 6, there are attacks in IV, not present in either I, II, and III - particularly, the strongest attacks.

The differences between the strongest attacks of type I and IV are remarkably small. For attacks of type I, we can only set one parameter, p, whereas for IV, we have k(k - 1) parameters that we can set. However, if, for example, we take m=30 and k=10, then attacks of type IV have at most a conditional entropy of 25.6597 (at least 4.3403 bits information leakage), whereas attacks of type I have at most a conditional entropy of 25.6210 (at least 4.3790 bits information leakage). The difference in conditional entropy is less than one part in a thousand. We conjecture that the minute difference is an artifact of the fact that the size of the coalition is given, and that if we remove that, the difference disappears entirely. Effectively, we suppose that the coalition does not effectively help minimize information leakage about observations, but rather help minimize information leakage about the shape and size of the coalition.

In Section 3, we have made several assumptions about ratings, advisors and targets. Non-binary ratings are also common in the literature. Our approach can generalize to other rating types by extending the alphabet of the ratings, at the expense of elegance. Our assumption that observations are 1 or 0 with 50% probability is just a simplifying assumption. In reality, these probabilities depend on the target. Since we are not interested in the target, but rather the advisors, we assumed maximum entropy from the target. The entropy is, therefore, lower for real targets - meaning the user has more information in practice than in theory.

7 Conclusion

In this paper we quantify and and analyze the strength of collusive unfair rating attacks. Sybil attacks where Sybil accounts provide unfair ratings are important examples of such attacks. Compared with independent attackers, the additional attacker strength gained by collusion is surprisingly small.

We apply our quantification to collusive unfair rating attacks found in the literature, where ballot-stuffing/badmouthing form the most well-studied types. The attacks in the literature are not maximally strong. We also quantify different types of attacks. And we identify the strongest possible collusive unfair attacks. Based on these strongest attacks, we propose trust systems robust against unfair rating attacks.

By this paper, the approach of applying information theory to quantify the strength of attacks becomes general and adaptable. Different types of unfair rating attacks (whitewashing, camouflage, etc.) can be quantified if the assumptions are changed accordingly.

Acknowledgement

This research is supported (in part) by the National Research Foundation, Prime Minister's Office, Singapore under its National Cybersecurity R & D Program (Award No. NRF2014NCR-NCR001-30) and administered by the National Cybersecurity R & D Directorate. This research is also partially supported by "Formal Verification on Cloud" project under Grant No: M4081155.020, and the ASTAR / I2R - SERC, Public Sector Research Funding (PSF) Singapore (M4070212.020) awarded to Dr. Jie Zhang.