Progress against SYN flooding

October 9, 1996

Vernon Schryver <vjs@sgi.com> posted these notes on 1996-09-18 and 1996-10-05 detailing the development of the Random Drop defense against SYN flooding attacks.

Date: Wed, 18 Sep 1996 14:32:14 -0600
From: vjs@mica.denver.sgi.com (Vernon Schryver)
Subject: SYN bombing defense

As reported here, in article
<vxjiv9hkmcb.fsf_-_@dominator.eecs.harvard.edu>
in comp.protocols.tcp-ip, Robert Morris 
<rtm@dominator.eecs.harvard.edu> wrote:

>Perhaps TCP's listen queue should use random early drop (RED), a
>technique used by routers to prevent any one source from monopolizing
>a queue. See http://www-nrg.ee.lbl.gov/floyd/abstracts.html#FJ93 or
>rfc1254.
> ...

I've just hacked IRIX 6.3 to do random-drop when sonewconn() in
tcp_input.c fails.  It works great!  An IP22 receiving 1200 bogus
SYN's per second directed to port 23 continues to answer requests
for new telnet as if nothing is happening.

I don't think that random <<Early>> drop is necessary or desirable.
It is not as if we're trying to drop packets early to trigger
slow start in the sources.

As I figure it, as long as the length of the queue is longer than RTT
of the real telnet client times the rate of bogus SYNs, the real
clients have an excellent probability of getting through on their
first attempt.  For example, at 1200 bogus SYNs/sec and the IRIX 6.3
telnet listen queue of 383, there should be no trouble with peers
with RTT up to about 300 milliseconds.  I've tested with a telnet
client 250 milliseconds away while simultaneously bombing the machine
from nearby with ~1200 SYNs/sec, and see no telnet TCP retransmissions.

- - - - - - - -

Date: Sat, 5 Oct 1996 09:02:29 -0600
From: vjs@mica.denver.sgi.com (Vernon Schryver)

...things have changed a little in the weeks since then.

For one thing, another solution involving increasing the listen queue
to 10,000 or more entries has been published by BSDI. Also, code to do
random-drop and/or drop-oldest has been distributed for FreeBSD and Linux.

The main problem with publishing that old note of mine is that I was
somewhat wrong.  If you try enough times and don't get lucky, you see 
frequent failures to get through.  The probability of a successful
connection using the random-drop tactic is P=((L-1)/L)**(R*RTT), where
L=limit on the half-open queue, R=SYN bombing rate, and RTT=round trip
time to the good guy.  With L=383, R=1200, and RTT=250 ms, P is only
about 35%.  But at the commonly observed R=130, P is 90%.

Since that initial note, I've been pushing (i.e. distributing code) a
slightly more complicated solution, involving about 25 lines of code
instead of 10. It switches to random-drop from oldest-drop when the
bombing rate exceeds (queue limit)/1 second. Thus, if possible, the
good guys within a predetermined RTT (I chose 1 second) are treated
with drop-oldest instead of random drop.

One trouble with random drop is that it kills some good connections.
With a queue limit of 512 and a bombing rate of 100 SYNs per second,
good guys with an RTT of up to 5 seconds are completely safe with
drop-oldest.  With 512 and 100 S/s, random-drop messes up 5% of good
connections with an RTT of 250 ms, 10% at 500 ms, and fully 62% at 5
seconds.  Another trouble with random drop is that it takes CPU cycles
to pick its target, and the bigger the queue, the greater the cost.
The trouble with drop-oldest is that it kills 100% of valid connections
with RTT at least L/R.  For the classic BSD SO_MAXCONN=5 giving a queue
limit of L=7 and current bombing rates of R=130 SYNs/second, that RTT is
54 ms.

Random-early-drop does not work at all, if it is understood to mean
that as the listen queue begins to fill, you drop randomly chosen
arriving SYNs.  That is becuse if your random algorithm allows more
one SYN every 75 seconds, then your queue will eventually fill and
the system will become deaf.  But with a bombing rate of 100 SYNs/sec,
you must drop more than 99.9% of all incoming SYNs to limit to allow
only 1 SYN/75 seconds, which is not very random.

Note that the SYN excitement was bound to be short lived. It's too
boring for the bad guys. Between 75 seconds and 12 minutes after they
stop paying their ISP to send their SYNs, their target heals itself and
goes on as if nothing had happened. Unless they are very persistent or
lucky, the rest of the universe will assume the Internet path to the
target hiccupped. Worse, they've a good chance of not being noticed at
all. This is quite different from PC viruses, the Morris Worm, sendsys
bombing, mail bombing, test group bombing, and so forth.