In this section, we quantify the maximum damage an isolated adversary can inflict on the Internet given that Strong Split Whisper is deployed. Since SSW offers path integrity, an isolated adversary cannot propagate invalid routes without raising alarms unless there exists no alternate route from the origin to the verifier (i.e. adversary is present in all paths from the origin to the Internet).
Given an adversary that is willing to raise alarms, we analyzed how many AS's can one such adversary affect. In this analysis, we exclude cases where the adversary is already present in the only routing path to a destination AS. We use penalty based route selection as the main defense to contain the effects of such invalid routes. We assume that in the worst-case, an adversary compromising a single router in an AS is equivalent to compromising the entire AS especially if all routers within the AS choose the invalid route propagated by the compromised router.
Let represent an isolated adversary propagating an invalid route
claiming direct connectivity to an origin AS
. AS
is said to
be affected by the invalid route if
chooses the route
through
rather than a genuine route to
either due to BGP
policies or shorter hop length. Based on common practices, we
associate all AS's with a simple policy where customer routes have the
highest preference followed by peers and
providers [18]. Given all these relationships, we define the
vulnerability of an origin AS,
, as
to be the
maximum fraction of AS's,
can affect. Given an isolated adversary
, we can quantify the worst-case effect that
can have on the
Internet using the cumulative distribution of
across
all origin AS's in the Internet.
With AS's deploying penalty based route selection as a defense, we
expect the vulnerability to reduce. We study how the
cumulative distribution of
for a single adversary
varies
as a function of how many AS's deploy penalty based route
selection. We consider the scenario where the top
ISPs deploy
penalty based route selection (based on AS degree).
Figure 7 shows this cumulative distribution for for
different values of
and
. These distributions
are averaged across all possible choices for
.
We make the following observations. First, a median value of for
indicates that a randomly located adversary can affect at
most
of destination AS's by propagating bogus advertisements
assuming that the top
ISPs use penalties. This is orders of
magnitude better that what the current Internet can offer where a
randomly located adversary can on an average affect nearly
of
the routes (repeat the same analysis without SSW) to a randomly chosen
destination AS.
Second, in the worst case, a single AS can at most affect of the
destination AS's for
.
is a limit imposed by the
structure of the Internet topology since it represents the size of the
largest connected without the top
ISPs. One malicious AS in
this component can potentially affect other AS's within the same
component.
Third, if all provider AS's use penalties for route selection, the
worst case behavior can be brought to a much smaller value than .
Additionally, there is very little benefit in deploying penalty based
route selection in the end-host networks since they are not transit
networks and typically are sources and sinks of route advertisements.
Hence, any filtering at these end-hosts only protects themselves but
not other AS's.
To summarize, the Whisper protocol in conjunction with penalty based
route selection can guarantee that a randomly placed isolated
adversary propagating invalid routes can affect at most of the
AS's in the Internet topology.