Containment: Penalty Based Route Selection

Figure: Detecting Suspicious AS's: In this example, $M$ is a malicious AS that propagates 3 invalid routes to 3 different destinations $A$,$B$,$C$. The AS paths in the routes propagated are indicated along the links. The verifier $V$ assigns penalty values of $3$,$1,1,1$ to $M, A,B,C$ respectively.

Route consistency testing only provides the ability to trigger alarms whenever a node propagates invalid route announcements. We append consistency testing with penalty based route selection, a simple containment strategy that attempts to identify suspicious candidates and avoid routes propagated by them. The strategy works as follows: A router counts across destinations how often an AS appears on an invalid route, and assigns this count as a penalty value for the AS. The more destinations an adversary affects the higher becomes its penalty and the clearer it stands out from the rest. The route selection strategy is to choose the route to a destination with the lowest penalty value.

Consider the topology in Figure 5, where $M$ is a malicious node that propagates $3$ invalid route announcements with AS paths $MA$, $MB$, $MC$. By choosing the minimum penalty route, the verifier $V$ can avoid the invalid routes through $M$ since they have a higher penalty value. One key assumption used in this technique is: The identity of an AS propagating invalid routes is always present in the AS path attribute of the routes. The identity of every AS is verified by the neighboring AS which receives the advertisement. For example, Zebra's BGP implementation [2] explicitly checks for this constraint for every announcement it receives. BGP should use shared keys across peering links to avoid man in the middle attacks.

Penalties should primarily be viewed as a reasonable first response to detect suspicious candidates and not as a fool-proof mechanism. In the presence of an isolated adversary, penalty based filtering can ensure that the effects of the adversary are contained. We believe that penalties is a good mechanism to detect malicious adversaries in customer AS's but should be applied with caution when involving AS's in the Internet core. In particular, penalties are not a good security measure in the presence of colluding adversaries or when the number of independent adversaries is large. For example, multiple adversaries can artificially raise the penalty of an innocent AS by including its AS number in the invalid route.