Defensive Measures to reduce False Negatives

In this section, we show that one can adaptively set the parameters $N$, $T$ in the listen algorithm to drastically reduce the probability of false negatives due to spurious TCP connections. In particular, we show that by adaptively tuning the minimum time period, $T$, one can reduce false negatives due to port scanners and by tuning the number of distinct destinations, $N$, one can deal with non-live hosts.

Given the nature of incomplete connections in our testbed, we use outbound incomplete connections as a test sample for non-live hosts and inbound connections as the test sample for port scanners and worms. In both inbound and outbound, we restricted our samples to only those connections which are known to be false negatives.

Setting $T$: One possibility is to choose an interval $T$ large enough such that the router will notice at least one genuine TCP flow during the interval. Such a value of $T$ will depend on the popularity of a prefix. The popularity of a prefix, $pop(P)$, is defined as the mean time between two complete TCP connections to prefix $P$. We can model the arrival of TCP connections as a Poisson process with a mean arrival rate as $1/pop(P)$ [30]. Given this, we can set the value of $T= 4.6 \times pop(P)$ to be $99\%$ certain that one would experience at least one genuine connection within the period $T$. To have a $99.9\%$ certainty, one needs to set $T=6.9 \times pop(P)$. For prefixes that hardly observe any traffic, the value of $T$ will be very high implying that port scanners generating incomplete connections to such prefixes will not generate any false alarms.

From our testbed, we determine the mean separation time between the arrival of two incoming connections to be $pop(P) = 34.1$ sec. By merely setting $T=156.8$ to achieve $99\%$ certainty, we could reduce the probability of false negatives in Listen from $91.83\%$ to $0.37\%$. Throughout the entire period of measurement, only during $8$ periods of $156$ seconds each did we verify incorrectly that the local prefix is not reachable.

Setting $N$: The choice of an appropriate value of $N$ trades off between minimizing the false negative ratio due to non-live hosts and the number of reachability problems detected. In our testbed, we noticed that by merely setting $N=2$, we can significantly reduce the false negative ratio in outbound connections from $63\%$ to less than $1\%$. However, Listen reported only $35$ out of $663$ potential prefixes to have routing problems. For several $/24$ prefixes, we observed TCP connections to only a single host and by setting $N=2$, we tend to omit these cases. In practice, the value of $N$ is dependent on the diversity of traffic to a destination prefix and the traffic concentration at a router. For many $/24$ prefixes, we need to set $N=1$. For $/8$ and $/16$ prefixes, one can choose larger values of $N=4$ or $N=5$ provided the prefix observes diversity in the traffic.