  Despite the large effort devoted to cybersecurity research over the last
decades, cyber intrusions and attacks are still increasing. With respect to
routing networks, route hijacking has highlighted the need to reexamine the
existing protocols that govern traffic routing. In particular, our pri- mary
question is how the topology of a network affects the susceptibility of a
routing protocol to endogenous route misdirection. In this paper we define and
analyze an abstract model of traffic interception (i.e. eavesdropping) in
distance-vector routing networks. Specifically, we study al- gorithms that
measure the potential of groups of dishonest agents to divert traffic through
their infrastructure under the constraint that messages must reach their
intended destinations. We relate two variants of our model based on the allowed
kinds of lies, define strategies for colluding agents, and prove optimality in
special cases. In our main theorem we derive a provably optimal monitoring
strategy for subsets of agents in which no two are adjacent, and we extend this
strategy to the general case. Finally, we use our results to analyze the
susceptibility of real and synthetic networks to endogenous traffic
interception. In the Autonomous Systems (AS) graph of the United States, we
show that compromising only 18 random nodes in the AS graph surprisingly
captures 10% of all traffic paths in the network in expectation when a
distance-vector routing protocol is in use.
