Student
comments 12/03/2008
Andrew Berry
Cheng and Friedman develop a formal representation
of sybilproofness using a graph formulation. They determine that there is no
symmetric sybilproof reputation function and there is an asymmetric reputation
function given that there are diminishing returns, no splitting and the
function is monotonic. However, I would like a more thorough explanation (and
perhaps an example) of these attributes. I have two main questions surrounding
this work. Although many formulations employ the notion of transitive trust, is
this a good assumption? For a directed graph representation this makes sense,
but I do not think this necessarily an assumption that fits with the spirit of
the problem. A may trust B, but the second individual may be an imperfect judge
of other individuals. I would argue that one rarely finds this concept of
transitive trust. Perhaps a more accurate representation would have weighted,
directed edges and for edges with large weights the argument for transitive
trust could be sound. Additionally, what would be an example of a trivial
symmetric sybilproof function?
Haoqi Zhang
Sybilproof Reputation Mechanisms
The main contribution of the paper is the formal
characterization of sybilproofness on a static graph and showing that there is
no symmetric sybilproof reputation function. This result is significant because
most common reputation systems we think of on graphs (e.g. pagerank) is symmetric
in this manner. In a sense this result isn't too surprising because
sybilproofness is quite a strong assumption, almost to the extend of
anonymity-proofness. The authors then provide some sufficient conditions for an
asymmetric graph to be sybilproof.
Manipulability of PageRank under Sybil Strategies
The main contribution of the paper is an analytical
quantification of the effect of sybil manipulations in the pageRank algorithm.
The authors show that they can give upper and lower value bounds on the amount
of value increase as a function of the random walk probability and the number
of sybils created. The authors then took data actual web data and looked at the
rank increase for varying parameters.
From the bounds given in this paper, is the
implication that one can improve their value monotonically as k increases?
I think this work is interesting in that it gives
both a formalism for thinking about sybilproofness but also discusses practical
implications of choosing a ranking system on sybil-manipulability. This leaves
me with a couple of questions:
- the analysis seems to be for sybil attacks by a
single user. What is the effect on the total ranking if many users were using
sybil attacks (not colluding but for personal gain)?
- why can't a reputation system (e.g. pageRank)
become sybilproof by automatically adding an infinite number of sybils for each
user? What happens to the rankings? Are they still informative?
- do many of the results here apply to non-graph
settings? What are the connections between the sybilproofness formalism for
reputation system on a graph versus other structures?
Sagar Mehta
Sybilproof Reputation Mechanisms
This paper attempts to formalize
the notion of sybilproofness (i.e. a reputation system is immune to a sybil
attack where a peer attempts to raise reputation by creating fake links between
sybils). The main result is negative in that the authors find that symmetric
reputation functions fail to be sybilproof, but they show the existence of
sybilproofness for asymmetric reputation functions. Intuitively, this makes
sense since a function based on trusting each node equally will not be able to
distinguish between real and fake nodes in the graph. One idea which the
authors briefly mention in the conclusion is the notion of dynamic reputation
models where in each time step the reputation function depends not only on the
current state of the network, but also the state of the network in previous
time steps. First off, I think the idea of looking at previous time steps could
be a useful means of catching manipulation (i.e. if I get 100 positive reviews
today, its highly likely that I'm using a sybil strategy or colluding). I also
think it would be interesting to incorporate previous time steps to slow the
rate at which your reputation changes. For example, what happens if we reworked
the definition of page rank of a node to be my page rank today + (delta) (my
page rank yesterday) + (delta)^2 (my page rank two days ago)É for some 0 <
delta < 1? This would be a simple model to incorporate "history"
into the page rank mechanism and would perform better at slowing sybil
strategies while not hurting the effectiveness of the ranking mechanism in
finding relevant pages.
Manipulability of PageRank under
Sybil Strategies
The second paper computes explicit bounds for the
possible PageRank value increase for a specific type of sybil attack and
compares it with actual experimental data. The degree of manipulability with
even just one sybil node surprised me (figure 1) and I wonder what the results
of using a dynamic reputation model (like the one proposed above) in the same
experiment.
Rory Kulz
Manipulability of PageRank
I guess this paper would have been a more
interesting read if I hadn't
heard of SEO before
(http://en.wikipedia.org/wiki/Search_engine_optimization),
but I was
already fairly familiar with the idea behind this
paper, although not
the particular framing of it as a "sybil
strategy." Still, it was cool
to see some experimental data for this.
A few questions though:
- Is stanford.edu a representative domain for this
experiment? I feel
like the main Stanford page is only a couple hops
away at any time
within that domain. I understand the Internet
basically follows a
power law, but a single domain might be a little
too extreme a case
study. Basically, would the results change by
incorporating more
domains?
- And more to the point, what happens when you're
really dealing with
the much larger cloud of the Internet? And is there
an estimate on
Google's epsilon?
- Do Sybil attacks really extend easily, as the
Introduction and the
other paper suggest, to other reputation systems?
There is certainly
manipulation on eBay, but it's much harder than
manipulating Google
results, as evidenced by the infamous
"miserable failure" Googlebomb.
Symbilproof Reputation
The first part on symmetric reputation mechanisms
provides an
interesting no-go result, but it suffers I think
from how strong the
assumption is regarding common and complete
knowledge of the
reputation graph structure. Will the result still
stand if the
attacker only knows the graph structure up to, say,
one, two, or three
hops away but no farther? Clearly the proof of
Theorem 1 immediately
breaks down, but it is not clear that the result
ceases to hold.
The really fascinating part, I found, was the second
half. The
asymmetric mechanism based on max flow is a very
nice result and much
more relevant to reality. I had been thinking about
how eBay
consolidates information into a single number for
reputation that is
the same for anyone viewing the feedback data, and
I had thought,
"Wait. What if seller X mistreats group Y but
treats group Z extremely
well? A person in group Y then should trust other
people from group Y
more than feedback relating to dealings with group
Z. Can we
incorporate this into different reputations per
user using a social
network somehow?" I think this line of
thinking may have been spurred
by someone's comment in class about dealing with
eBay vendors your
friends have dealt with. In any case, when the
authors wrote about the
possibility of "each user [computing]
separately the reputations of
other users with respect to themselves," my
ears perked up.
Alice Gao
Sybilproof Reputation Mechanisms
The main contribution of this
paper is to characterize reputation functions that are sybilproof. This
is important direction of research on the manipulability of reputation systems.
I think this approach can be used for investigating other types of
manipulations to reputation systems other than sybil attacks. I
understood the intuition for why symmetric reputation function cannot be
sybilproof, but I couldn't follow the proof fully. For the asymmetric
case, I am not very familiar with the flow-based reputation functions.
Perhaps an overview of different types of reputation functions would be
helpful.
Manipulability of PageRank under
Sybil Strategies
The main contribution of this paper is to have both
analytical and empirical results on the manipulability of the PageRank
reputation system. It is not surprising that the PageRank system is
easily manipulated. I think a more important question is how much the
rank of a page can be improved using manipulations. I think a more
fundamental question is what makes a reputation system manipulable. And
if we can prevent manipulation, what are our gains and losses? These
basically revolve around the trade off between the quality of the ranking
system and its manipulability.
Subhash Arja
Paper A
This paper seeks to formalize a method to prevent
users of P2P networks from creating new identities known as "sybils".
This is a purely theoretic paper which likens the creation of identities and
communication between users to a weighted, directed graph. Each user is
represented by a node on the graph and the interaction between a pair of users
constitutes the weight of the edge between the two users. I thought the central
idea of the paper was very good since it presents a framework to analyze how
good a particular reputation mechanism is in dealing with multiple identities.
The theoretical concepts presented here can be applied to identify and fix
flaws that exist in such P2P networks. Also, such an application would possibly
expose some of the limitations of formalizing the problem in the manner
presented in the paper.
Paper B
This paper looks at the effect of sybils on the
pagerank algorithm and how it can manipulated through the creation of fake
identities. The conclusion is that PageRank is highly vulnerable to such an
attack. I am not surprised by the result because there have been many instances
where Google searches have been manipulated relatively easily to display search
results in a wrong order. I thought the analysis section of the paper was well
done since the authors provide tangible results showing the affect of various
numbers of sybils and their effect on PageRank. The results are only a starting
point and the authors don't really provide solutions to the manipulability of
the system, but I would have liked a mention of this in the Future Work
section.
Nick Wells
Sybilproof Reputation
A sybil attack is where a single user creates a
large number of
accounts/websites (sybils) and uses them to add to
his own reputation. This
paper studies a trust graph where users build each
other's reputation through
their recommendations. The authors lay out whether
one can create sybilproof
reputation functions.
The authors show that there is no symmetric
sybilproof reputation function, and
extend the proof to include k-sybilproofness. I
don't understand this actually,
and am sort of lost here. The gist though seems to
be that no symmetric
reputation function can be sybilproof. The authors
also lay out the conditions
for asymmetric reputation functions to be
sybilproof.
I'm wondering whether more can go into a system or
website into making it
sybilproof. Also, how feasible are these
nonsymmetric reputation functions that
are sybilproof?
Manipulability of PageRank
Sybil attacks are a surprisingly easy way to
influence systems to favor one's
reputation, particularly through manipulating
PageRank. The authors of this
paper examine the usefulness of creating sybils and
examine their effects.
They examine PageRank data and examine what the
effect would be of a sybil
strategy that they set up. They develop a system
that shows how many sybils
would be required for a page to rise to be among
the top ranked. It seems to be
surprisignly few. For example, with 500 sybils, one
can expect to rise to the
top 100 out of 300 thousand with a median rank of
0.3 in their dataset. The
authors of this paper show that use of s sybil strategy
is quite effective
except for those already at the top.
Like most net users, I've seen sybil strategies at
work though I did not know
that they were quite as effective as they are. I
wonder how effective sybil
strategies are at beating out similar keyworded
sites that are already tightly
knit together.
Obviously, some people spend quite a lot of money
on sybil strategies. If one
could compare the use of sybil strategies to simply
buying ads on websites, I
wonder which would be more cost-effective. I noticed
that Google has certain
restrictions on its advertising, perhaps sybils are
the best alternatie in some
cases.
Victor Chan
he two papers Sybilproof Reputation Mechanisms and
Manipulability of PageRank under Sybil Strategies written by A.Cheng and E.
Friedman present the case Sybil attacks on reptuation systems. The first paper
talks about the requirements for a Sybilproof system, while the second paper
talks about how the PageRank algorithm is vulnerable to sybil attacks.
The main contribution the first
paper showed that there is no symmetric sybilproof reputation mechanism. After
that it shows that there exist sybilproof asymmetric systems. However the
system needs to follow a set of properties defined by diminishing returns,
monotonicity, and no splitting. The application of this paper can be used to
design reputation systems which are sybilproof. However similar to the false-name
proof paper earlier, the constraints can be hard to explain to users.
The second paper deals with PageRank manipulation
where the reputation is the ranking of a webpage on the internet. PageRank
treats the internet like a graph, with webpages being vertices and links being
edges. In this system a sybil attack can be creating a link farm that joins
together many pages, and then links to an attackers page to make it rank
higher. The paper shows the upper and lower bounds of increase in reputation in
such attacks.
Ziyad Aljarboua
Sybilproof Reputation Mechanisms:
This paper is a continuation to the papers we
discussed so far dealing with online reputation systems and online identity.The
need for sybilproofness p2p networks rises from the fact that users can easily
and cheaply obtain new identities. Users can create sybils to boost his/her
reputation in the network.
In this paper, sybilproofness is discussed for
symmetric and asymmetric reputation functions. It shows that there is no
sybilproof mechanism for symmetric reputation functions. Where as some sort of
syilproof mechanism can be devised for asymmetric reputation functions. several
asymmetric reputation functions that are sybilproof are presented.
Beside from the graphical meaning of symmetric and
asymmetric reputation function, i am not sure i understand the practical
meaning of the two conditions. In general, the sybilproofness of reputation
functions was represented through graphs where reputation was shown as a
mapping between nodes (users). While this might seem reasonable, reputation in
real life is much more that just an edge between two users. Opinions on
transactions between users are not restricted to certain values unlike in this
model.
-----------------------------------------------------------------------------------------------
Manipulability of PageRank under Sybil Strategies:
This paper discusses the effect of Sybil attacks on
the PageRank algorithm. It shows that the effect of the Sybil attacks on the
performance of the PageRank algorithm is limited and an upper bound for value
increase from a Sybil attack and collusion can be defined.
Similar to the previous paper, this paper presents
the reputation system on the PageRank algorithm as a connected graph where the
nodes are the users (pages) and the edges are the level of trust. rank of pages
on the PageRank system represent the probability that a user would end up at
this page when starting from a different one. It is shown that there is an
upper and lower bound to the value increase from a Sybil attack that is
proportional to the number of sybils. A way to improve the PageRank algorithm
is to alter the probability of making a random jump at each step of the random
walk from a node to another. As this probability increases, the value gain from
a Sybil attack is reduced.
In conclusion, this paper shows that the PageRank
algorithm is easily manipulable.
Angela Ying
Paper 1: Sybilproof Reputation Mechanisms
This paper discusses ways to make reputation
systems sybilproof, safe from sybil attacks, where people arbitrarily create
more identities to enhance their reputation. The main results of the paper were
proving that there is no symmetric reputation system that is sybilproof (including
Google Pagerank, which is addressed in the next paper), and that there exists
asymmetric reputation systems that are sybilproof under certain conditions. The
authors did this by showing that a user can construct a sybil that is the same
as the current graph, so that when the sybils are collapsed the reputation of
the user is enhanced. Both reputation systems were modeled as static graphs,
which may not be a valid assumption
I thought this paper was interesting, but I
questioned the main assumption that a user, in constructing a sybil attack, can
have knowledge of the entire space. It seems like something like PageRank is
more successful in generating relevant pages than other search engines because
the search space is so big that it is difficult to find relevant content based
on the search query. I would be interested in seeing results if the user only
had a limited knowledge of the graph (perhaps only locally or something).
Paper 2: Manipulability of PageRank under Sybil
Strategies
This paper is a complement to the previous paper,
admitting that developing a sybil-proof reputation is nearly impossible,
discussing instead the impact of sybil attacks on ranking in the PageRank
system. In particular, the paper examined sybil attacks with "petal shapes",
where a user creates n new pages that only link to the main page, which links
back to the n new pages. The main contribution of the paper was establishing
upper and lower bounds for how effective sybil attacks are in increasing your
value. In addition, the paper examines the effect on rankings for pages who use
sybil attacks and found that sybil strategies are useful for almost all pages,
except the very highly ranked and very lowly ranked.
I thought this paper was interesting, but was
surprised to find that the lowest ranked pages are not improved by sybils. I
would like to see some statistics on how often sybils are actually used
(although this would be very hard to tell) and to what extent. I would also
like to see the data for different sybil strategies, particularly the one
brought up in the last paper about replicating the graph.
Michael Aubourg
First paper :
First of all, I would like to
temper an assumption. Even if many existing reputation mechanisms use it,
the transitive trust is quiet a strong hypothesis.
This idea states that if a user A trusts B, and B trusts C, then
A may trust C to some extent, even if A hasnÕt
previously interacted with C, which means that A trust C more than unknown node
D.
It is intuitive, generally speaking but I am not
convinced it is always possible to consider it as true. For instance, PageRank
uses this kind of
reputation system based on transitive trust, but in
my opinion, after 3 or 4 "intermediary nodes", a website shouldn't
trust more C than D.
Secondly, as the authors
added, this paper only focused on static reputations functions that are
independent on the state of the network, and I guess
there are a lot of things to discover in this path.
Second paper:
Now we can wonder why Internet works since it is so
easy to manipulate the PageRank.
The Internet works because there is a set of sites
that we know have good reputations, so PageRank worked.
Another researching path would
be to have a look at how these principles apply in the P2P setting, where users
want to know which other nodes will give them valid copies of the file, and
have good performance.
Into the bargain, a curious
phenomenon is currently taking place in the webmasters community: for
search-engine optimization purposes, some companies offer to sell high PageRank
links to webmasters. As links from higher-PR pages are more valuable, they tend
to be more expensive. It can be an effective and viable marketing strategy to
buy link advertisements on content pages of quality and relevant sites to drive
traffic and increase a webmaster's link popularity. However, Google is of
course aware of it and is going to ÒpunishÓ any webmaster discovered to
be selling links for that purpose : their links will be then ignored in
the calculation of other pages' PageRanks.
Another funny phenomenon of
manipulating the PageRank is what people call the ÒGoogle BombÓ :
It is a certain kind of attempt to raise the
ranking of a given page in results from a Google search, often for humorous or
political intentions. Before 2007, Google's search-rank algorithm could rank a
page higher if enough other sites linked to that page using similar ÒanchorÓ
text but Google changed the ranking by January 2007 to list pages instead
about the repeated linking of that text. And this is not limited to Google : a
search for "miserable failure" or "failure" on September
29, 2006 brought up the official George Bush biography number 1 on Google,
Yahoo and MSN !
Avner May
I found both of these papers
interesting and very relevant to the real world, given that the PageRank of a
webpage is such a huge factor in determining the web traffic and general
visibility of a webpage. The first paper I think is most valuable due to
its impossibility result – Òthat no nonconstant, symmetric reputation
function exists.Ó In my opinion, symmetry is a very natural property to
demand of a reputation function, and the fact that no symmetric sybilproof
reputation mechanism exists suggests that maybe this is too much to ask.
Knowing this, it then becomes important to ask the following questions about
symmetric reputation functions: which of these functions are more resistant to
sybil attacks? Given a reputation function, what nodes in the graph are
particularly susceptible to sybil strategies (eg, in PageRank, maybe higher
ranked pages are harder to manipulate, as they would probably require more
sybils to create the same increase in rank)? Are there ways of detecting
sybil manipulations by tracking the evolution of the graph (for example, maybe
you can ignore cases where the rank of a node increases substantially due to
the creation of many new webpages. Maybe tracking IP addresses could be
helpfulÉ)? Are there reputation mechanisms which take into account the
evolution of the graph which are sybilproof and symmetric? Are there ways
of imposing extra costs for creating new nodes or edges in the graph, such that
large scale manipulations become infeasible/not worth it (for example, requiring
someone to complete a captcha before creating a webpage, or requiring a new
eBay user to complete a captcha, or only allowing one node per email address,
etc). I think that one very fertile area of research could be the
development of reputation functions which depend on the evolution of the graph,
in addition to just the current structure. Maybe just like in eBay it
takes a long time to develop a good reputation, it should take a long time to
be able to acquire a good ranking. This might decrease vulnerability of a
reputation mechanism to sybil manipulations.
The second paper is more straightforward, as its
results are more empirical/limited in nature. One thing IÕm curious about
is how sybil-manipulability of a pageÕs ranking depends on its rank
pre-manipulation. Is it easier to manipulate lower ranked pages, and much
harder to manipulate higher ranked webpages?
Peter Blair
Manipulability of PageRand under Sybil Strategies
This paper presents an empirical examination of the
how easy it is to manipulate the PageRank algorithm, used by Google in its web
searches, by sybil users. Sybil users are fake identities created to boost the
reputation of a given agent by posting links to his/her website. In the paper
the authors derive an analtyic expression that quantifies the effects of sybil
manipulation on both the page value and page rank of a given website operating
under the page rank algorithm. This analytic expression was then used to place
bounds on the potential effects of sybil attacks on the reputation of webpages.
The predictions of this model were then tested using webpages from Standford
University's website, and the empirical results were found to agree remarkably
well with the predictions from the analytic treatment of hte PageRank
Algorithm. For example, the theory predicted a lower bound of a 0.13 decrease
in page rank for sybil attacks -- the Stanford data yielded a value of 0.14.
Other interesting results were that an individual user (of inferior rank)
would need to create 500 sybils inorder to break the top 100 sites in the
Stanford data, and just 76 to break the top 3000. The model advanced here is
very well-motivated, as are the emprical studies. One modificiation that I
would recommend to the data collection would be to choose some power law
distribution fr the number of agents in the sample who create a given number of
sybil users. In short, it seems more reasonable that a greater portion of
malicious users will create one sybil as opposed to 5. I wonder how this might
affect the results? I was also interested in whether a study has been made to
quantify the effect of having a good page ranking, analogous to the ebay paper
which showed an 8% premium to users with better reputations.
Sybilproof Reputation Mechanicsm
This paper is important for estabilishing the
conditions under which a reputation system can be sybil proof. In particular in
the paper the authors show that symmetric reputation functions can not be sybil
proof, since one can create an identical copy of the network map which would
have a maximal element that would have an improved page rank or repuation over
the true sites. It turns out therefore, that the only hope for sybil-proof
reputation functions are asymmetric reputation functions. In particular, the
authors model asymmetric reputation fucntiosn using the static graph form of
reputations, where nodes and edges correspond to agents and their interactions
within the network and there is a notion of transitive trust which is path
dependent, breaking the symmetry of information flow in the network. We
discover that sybil-proof reputation functions in addition to being asymmetric
must also statisfy the following properties: (i) dimishing returns for longer
paths (ii) monoticity for the aggregation operator with respect the edge values
and (iii) no splitting (non-maximal) of paths. Importnat future work in this
area includes creating a dynamical model of this type of reputation system, and
developping more general constructions for assymetric reputation functions.
This paper does a solid job of setting up the theoretical frame work for graph
repreentations of reputation systems. The explanatio for why symmetric
reputation functions are not sybil proof is also strong; the corresponding
proof for max flow is weaker and a somewhat incomprerhensible to me at the
moment. The major result of requiring asymmetric reeputation functions is also
quite compelling, even as it holds for k sybilproofness and value sybil
proofness. The idea of breaking the symmetry by selecting one reference mode in
the graph is an interesting one. It would be interesting to know how stable the
sybilproofness is to non-sybil attacks on the reputation of this reference
user. It might be better to construct a basket of reference users to mitigate
against the integrity of the who reputation system's sybilpoofness hinging on
the secruity of the reference user. Empirical measure of how vulnerable single
user refence systems are to distortions based on non-sybil attacks woulda slo
be an interesting area of future research.
Xiaolu Yu
The first
paper differs from the second paper in a sense that it explores potential
sybilproof reputation function, and shows that no nontrivial symmetric
reputation system can be sybilproof. The paper gives a collection of flow-based
asymmetric reputation functions which are sybilproof under some conditions.
However, a more generalized formulation along with necessary and sufficient
conditions in both static and dynamic reputation models would be necessary to
study real life reputation system and improve its resistance to manipulability.
The second paper, based on the result from the
first paper, shows that PageRank is extremely manipulable (vulnerable to sybil
attacks), and analytically estimate the manipulability of PageRank, say,
analytic bounds for the rank related value increase upon creating sybils.
Different sybil strategies are considered, and an improvement in PageRank value
and rank were observed, which suggests a potential direction of research, to
quantify necessary improvements for a typical node to beat its competitors. The
trade-off problem of a ranking system – trade off between its
effectiveness and manipulability – looks quite interesting to me. This
problem per se is a dilemma because people would not bother to create sybils to
increase their reputation and rank if the system doesn't effectively rank them
according to their ranking value. On the contrary, the more effectively the
ranking system performs (in another word, the better the rank reflects agents'
ranking values), the more effort a node will put in creating sybils. Solving
this problem is not the same as reverting the trade off, but rather calls for
the development of robust and efficient ranking mechanisms.
Brett Harisson
These two papers discuss the problem that commonly
exists in reputation systems, where a user can create multiple fake identities
for the sole purpose of boosting that user's own reputation in the system.
These fake identities are called "sybils". In the first paper, the
authors define reputation functions on graph-based network structures, and show
that no symmetric sybilproof functions exist, where a symmetric reputation
function is a reputation function that is fixed under graph isomorphisms. But
the authors do show that there exist asymmetric sybilproof functions, in
particular by constructing one. In the second paper, the authors provide and
empirically verify bounds that describe how sybil strategies can manipulate the
PageRank reputation system.
The main drawback of their reputation system
(described in the first paper) is that all calculations are based the choice of
a source node, which needs to be a constant participant in the network. It
would seem that if that participant were to drop out of the system, or that
node's immediate neighbors dropped out, then there would be difficulty in
calculating the reputation of the other nodes. But this could be my naive
understanding of the mechanism.
Hao-Yu Su
Paper A
This paper discussed about the sybilproof
conditions of reputation system.
It claims that symmetric reputation function is
vulnerable to sybil attack.
When defining the term: symmetric, it used the idea
of renaming nodes.
I would like to know what is the physical meaning
of renaming the nodes.
Besides, is there any real example of such activity
in existing reputation
systems? Other question is about the validity of
the results of this paper.
When deriving its conclusions, the authors used
static graph model. I
would like how well this model can represent the
real reputation system.
As the author has mentioned in the final section of
this paper, it is still an
open question about the sybilproofness in a dynamic
reputation model. I
am thinking if the same analysis approach can still
be applied in such
dynamic model. Will these two types of models hold
similar properties?
Paper B
This paper conducted experiments to analyze the
vulnerability of PageRank.
In the beginning, it says that a reputation
function base on max flow is not
sybilproof, but it is more difficult to manipulate.
The first part of this statement
has been shown to be true in the previous paper.
However, the remaining
part is unclear. What kind of manipulation is
specified in this case? I think
that sybil attack is also a kind of manipulation.
Beyond this questionable
statement, I agree with the argument that each
reputation system has its
own degree of vulnerability, and the future work of
this paper is to take
similar approach to quantize the vulnerability of
other systems. In this paper,
the author has motioned the un-uniform distribution
of the subset of
competitors. The example for this argument is a
subset of nodes that are r
elated to the same topic, and these nodes may be
more clustered than a
random set of the web. I am wondering if there
exists an opposite case in
which nodes with related topic are fewer links
between them. That is,
nodes are less clustered. Moreover, when we can
reasonably assume
that a subset is a uniformly random subset?
Travis May
These two papers each assess the
impact and potential solutions for the problem of sybils in online reputation
systems. Users can cheaply create new nodes and edges in the network,
such as a new website with links to the old one, increasing the centrality of a
user and boosting their credibility. This is a substantial problem in
practice; in P2P systems, users build their credibility before distributing
viruses and malware, while there is a large and continually booming link
farming industry that artificially inflates particular sites. The papers
conclude that –while this is a substantial problem – the only
possible solution is to create an asymmetric algorithm, in which certain nodes
are ÒtrustedÓ and are thus valued more highly. Such a trust system,
however, is difficult to create in a scalable and non-arbitrary fashion, as it
requires an in-group that is always deemed trustworthy.
An alternative that I would propose is through the
use of draconian punishment. Harsh punishments have a long tradition in
society, and disproportionate punishments have often been used historically in
order to deter future criminals. My proposal is for trust networks to use
extremely harsh punishments. For example, if you are caught ÒcheatingÓ
with sybils by Google, then Google could ban all of your web properties from
its search engine and restrict your IP from being able to use any Google
product (and potentially a much wider portion of the internet, if they sought
to build a trust network), creating a strong economic disincentive against
being caught. If the punishment is harsh enough, the expected cost of
cheating could outweigh the expected benefit, especially if it is well-enforced
such that there is a reasonable probability of being caught. Ultimately,
the solution to cheating in trust networks rests not only on improved
algorithmic design, but also on aligning economic incentives.
Malvika Rao
The paper "Sybilproof Reputation
Mechanisms" presents a theoretical
framework that models the sybilproofness of a
reputation system. The paper
draws distinctions between symmetric and asymmetric
reputation functions
giving conditions for their sybilproofness. It
would be really interesting
ot see this model implemented on a real system. Can
we indeed successfully
detect when sybils exist in a webgraph G? What
would such an algorithm
look like and what would be its complexity? Also,
the paper focuses on a
static graph model of reputation. It would be
interesting to consider how
to define an update function to update the
reputation and sybilproof
conditions of a webgraph as it changes - new links
are created and/or
deleted. It is unclear whether this would
necessarily be Markovian.
The second paper analyzes the vulnerability of the
PageRank algorithm to
sybil strategies. It would be interesting to
compare this to other ranking
algorithms and classify them in order of degree of
sybilproofness. What
properties characterize ranking systems that are
relatively more
sybilproof? Also, it would be interesting to
compare collusion and sybil
strategies and their effects. What are the
similarities and differences?
Can we say that when collusion is easily possible
then that implies that
the system is not sybilproof? What is the
correlation, if any? Is this
analogous to what we saw in social choice - i.e
false-name-proofness
versus group false-name-proofness versus strategyproofness?
Zhenming Liu
This set of papers discusses
about the manipulation issues of reputation systems that are solely based on
the structure of the graphs. The first paper formalized some desired properties
of a reputation function and shows the non-existence of such function. The
second paper studies the performance of the manipulation for a specific ranking
algorithm PageRank both analytically and experimentally.
Although it is not very
surprising to see the impossible results for the reputation function, we still
see hopes for finding appropriate reputation functions via relaxing some
(unnecessary) properties. In particular, the additive property that attempts to
capture the notion of Òtotal reputationÓ (See Def 2 & 3) may not be a
necessary property. I believe the assumption that ÒreputationÓ can be added (or
has other linear property) needs a lot justification. On the other hand, I am
feeling that positive result might be possible if we work on a general
reputation aggregation function.
For the second paper, it is nice to see the
experiments match closely with the theory. However, the definition for
Sybil strategy looks strange to me. Specifically, I am convinced that it is
easy to create edges sybils while it looks strange to force node iÕth adjacent
outgoing edges are replicated. I guess the author meant that this specific strategy
is optimal over all Sybil strategies albeit I have no intuition of this result.