October 9, 1996
Vernon Schryver <email@example.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: firstname.lastname@example.org (Vernon Schryver) Subject: SYN bombing defense As reported here, in article <email@example.com> in comp.protocols.tcp-ip, Robert Morris <firstname.lastname@example.org> 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: email@example.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.