لخّصلي

The effect can be dramatic. Figure 5.29 shows the speed by which partial
views are fully polluted, that is, each contains references only to attackers.
In this example, we consider a network of 100,000 nodes, a partial view size
of 30, and only 30 attackers. After less than 300 rounds, all benign nodes
have fully polluted partial views. Also note that, completely consistent with
the push-pull behavior of epidemic protocols, it may take a while before any
serious effect is seen. However, as soon as a few hundred nodes are completely polluted, they increasingly contribute to contaminating the rest of the nodes,
and so on.
It can be argued that there is no standard security measure that can combat
these kinds of attacks. For example, even with using secure channels by which
both parties have genuinely authenticated each other, there is no reason to
assume that both of them will also behave as they should. In other words,
authentication provides no guarantees for trust. In the case of gossiping
systems, security often comes in the form of trying to detect and prevent
malicious behavior. For our example, the question is how can a benign node
can detect that it is under attack, and which countermeasures can it take to
mitigate the effects of an attack?
A solution in the case of peer sampling, and developed by Jesi et al. [2010],
works as follows. The essence is to discover if there are nodes that behave
badly. The attack we just described is characterized by the fact that, eventually,
many nodes will be referencing a very small of set of nodes. In terms of
graphs, this means that the indegree of some nodes is extraordinarily high,
while for most nodes, their indegree will be low, and actually 0. An indegree
of 0 means that a node is unknown to any other node in the network.
When using Cyclon [Voulgaris et al., 2005] as the peer-sampling service,
we know that the indegrees follow a normal distribution, as shown in Figure 5.30(a). In this example, the y-axis shows the fraction of nodes with a
specific indegree value. Even with a mere 30 colluding attackers, we already
see that after 10 rounds, the indegree distribution has started to becoming
wider and shifting to the left, as shown in Figure 5.30(b). This continues,
and after 40 rounds (Figure 5.30(e)), we already have that about 15% of all
nodes have an indegree of 0. (Note that for Figure 5.29, we were counting
the number of nodes that were referencing only attacking nodes, which is
different from measuring indegrees. An attacked node can still be referenced
by others.) Finally, after less than 300 rounds, virtually all nodes have an
indegree of 0; the attackers have now full control over the entire network.
Figure 5.30 also gives us a hint toward a solution. As explained by Jesi et al.
[2010], each node can gather statistics on which nodes are being referenced.
If certain nodes are gradually being referenced unusually more often than
others, then something fishy may be going on. There are a few issues we
need to deal with. First, spreading of “bad” links can be so efficient, that
we need to consider that once a benign node has come to the conclusion
that it has identified an attacker, it may already be too late. Second, we also
want to prevent that every benign node has to build up complete knowledge
of the entire network, partly also because attackers have to be identified
quickly. Third, attackers do not want to be caught, i.e., be recognized as acting
maliciously, as they collectively do need some time to be successful.
Notably the last aspect, not wanting to be caught, provides a solution to
mitigating an attack. In essence, a benign node can force an attacker to behave