Dealing with False Positives

Malicious end-hosts can create false positives by opening bogus TCP connections to keep a router from detecting that a particular route is stale or invalid. Adversaries noticing route advertisements from multiple vantage points (e.g., Routeviews [8]) can potentially notice mis-configurations before routers notice reachability problems. Such adversaries can exploit the situation and open bogus TCP connections.

We propose a combination of active dropping and retransmission checks as a countermeasure to reduce the probability of false positives.

1. Active dropping: Choose a random subset of $m_1$ packets within a completed connection (or across connections), drop them and raise an alarm if these packets are not retransmitted. Alternatively, one can just delay packets at the router instead of dropping them.
2. Retransmission check: Sample a different random subset of $m_2$ packets and raise an alarm if more than $50\%$ of the packets are retransmitted.

=An adversary generating a bogus connection cannot decide which packets to retransmit without receiving ACKs. If the adversary blindly retransmits many packets to prevent being detected by Active dropping, the Retransmission check notices a problem. We set a threshold of 50% for retransmission checks assuming that most genuine TCP connections will not experience a loss-rate close to 50%.

Consider an adversary that has transmitted $k$ packets in a TCP connection without receiving ACKs to retransmit a fraction, $q$, of these packets. Let $C(x,y)= \frac{x!}{(x-y)!.y!}$ represent the binomial coefficient for two values $x$ and $y$. The probability with which the adversary is able to mislead the active dropping test is given by $\frac{C(k\cdot q,m_1)}{C(k,m_1)}$. The probability with which the retransmission check cannot detect an adversary is given by the tail of the binomial distribution $(1 - (\sum_{l=m_2/2}^{m_2} C(m_2,l) q^l (1-q)^{m_2-l}))$. Hence the overall probability, $p_e$, that our algorithm does not detect an adversary is:

$$\frac{C(k\cdot q,m_1)}{C(k,m_1)} \times (1 - (\sum_{l=m_2/2}^{m_2} C(m_2,l) q^l (1-q)^{m_2-l}))$$

For a given prefix, the overhead of active dropping can be made very small. By choosing $m_1=6$ and dropping only $6$ packets across different TCP flows, we can reduce the probability of false positive, $p_e$, to be less than $0.1\%$.

This countermeasure is applied only when we notice a discrepancy across different TCP connections to the same destination prefix, i.e., number of incomplete connections and complete connections are roughly the same. In this case, we sample and test whether a few complete connections are indeed bogus.