Date: Sat, 21 Sep 1996 05:20:38 -0700 From: "David E. Tweten" <tweten@frihet.com> To: newton@communica.com.au (Mark Newton) Cc: imp@village.org (Warner Losh), spfarrel@midway.uchicago.edu, security@freebsd.org Subject: Re: comments on the SYN attack Message-ID: <199609211220.FAA06633@ns.frihet.com>
index | next in thread | raw e-mail
newton@communica.com.au said:
>This is so bogus, Warner.
Before you put down someone else's idea it is best to *do your homework*.
In this case, it's a little probability. Werner has a good idea, if not a
world beater. See below.
>The difference between the two is that the random method makes no
>effort to bias itself in favour of newly arrived packets which
>haven't had a chance to be SYN-ACK'ed yet.
This is exactly why making room on a stocastic basis is superior to doing
it on a deterministic basis. Newly arrived packets are likely to be flood
packets. Besides, the problem isn't to identify and eliminate flood
packets, because identification seems to be impossible. The problem is to
give legitimate SYN packets a fighting chance to survive long enough to be
paired with an ACK.
>The two approaches are so similar that if you were to implement the
>random approach, I could transform it into the deterministic approach
> by merely *changing your random number generator routine* [to one that
>isn't random].
This is hogwash. A "stocastic" process which is driven deterministically
isn't stocastic.
What follows is my version of the homework:
Make the following definitions, useful later on:
f the number of flood SYNs per the amount of time from
legitimate SYN/ACK sent to legitimate ACK received
n the number of pending SYN storage slots
p probability of a legitimate SYN lasting long enough to
be paired with an ACK
c probability of completing a successful connection
t tries needed to get a connection with probability, c
Make a variety of simplifying assumptions:
1. Flood SYNs arrive at a constant rate.
2. The required interval between SYN/ACK and ACK is constant for all
attempted connections.
3. The time between SYN arrival and SYN/ACK transmission is zero.
First we calculate p, for the deterministic algorithm. It throws away the
oldest unacknowleged SYN when it needs to make room for a new SYN. Stated
in C, it is:
p = f < n ? 1.0 : 0.0;
Next, calculate the same value for the stocastic algorithm. It chooses a
SYN at random to discard when it needs to make room for a new one.
p = pow((n - 1) / n, f);
Finally, the value for t is dependent upon p, however obtained.
t = ceil(log(c) / log(1 - p));
Now, lets run some numbers. Assume Werner's value of n, 100. The column
labeled "det" gives p for the deterministic algorithm, and the column
labeled "stat" gives p for Werner's stocastic algorithm. The column
labeled "t for c >= 0.5" applies only to the stocastic algorithm. For the
deterministic algorithm, t is either 1 or not defined.
f det stat t for c >= 0.5
------- ------- -------- --------------
< 68 1.0 > 0.5 1
68 1.0 0.5 1
99 1.0 0.37 2
100 0.0 0.37 2
200 0.0 0.13 5
400 0.0 0.02 39
800 0.0 0.0003 2151
Obviously, the deterministic algorithm fails to be able to establish a
legitimate connection when the flood rate is high enough to flush
legitimate SYNs just before their coresponding ACKs arrive. Werner's
stocastic algorithm will allow a legitimate connection to be made after a
reasonable number of retries for twice the flood rate that can be survived
by the deterministic algorithm, though sadly not for ten times the flood
rate.
I leave checking of my simple derivations and running the numbers for other
values of n as "an exercise to the reader". The moral seems to be, "Do
your homework before ridiculing someone else's idea."
Oh, and "Nice idea, Werner."
--
David E. Tweten | 2047-bit PGP Key fingerprint: | tweten@frihet.com
12141 Atrium Drive | E9 59 E7 5C 6B 88 B8 90 | tweten@and.com
Saratoga, CA 95070-3162 | 65 30 2A A4 A0 BC 49 AE | (408) 446-4131
Those who make good products sell products; those who don't, sell solutions.
help
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199609211220.FAA06633>