Project Abstract Machines Assignment PDF

Resisting SYN flood DoS attacks with a SYN cache
Jonathan Lemon [e-mail]
FreeBSD Project
Abstract
Machines that provide TCP services are often suscepti-
ble to various types of Denial of Service attacks from
external hosts on the network. One particular type of
attack is known as a SYN flood, where external hosts
attempt to overwhelm the server machine by sending a
constant stream of TCP connection requests, forcing the
server to allocate resources for each new connection until
all resources are exhausted. This paper discusses several
approaches for dealing with the exhaustion problem, in-
cluding SYN caches and SYN cookies. The advantages
and drawbacks of each approach are presented, and the
implementation of the specific solution used in FreeBSD
is analyzed.
1 Introduction
The Internet today is driven by machines that communi-
cate using services layered on top of the TCP/IP proto-
cols, these include HTTP, ftp and ssh, among others. The
accessibility of these services is dependent on how well
the underlying transport protocol performs, which in this
case is TCP. If TCP is unable or unavailable to deliver the
layered service to a remote machine, the user perceives
the site as being dead or inaccessible. Perhaps merely
an inconvenience in the past, this is a much more serious
problem today as machines are being used for commerce
and business.
One way that a malicious host can attempt to deny ser-
vices provided by a server machine is by sending a large
number of TCP open requests. These are known as SYN
packets, named after the specific bit in the TCP speci-
fication, hence this type of Denial of Service attack is
often called SYN bombing or SYN flooding. When the
server receives this packet, it is interpreted as a request
by the remote host to initiate a TCP connection, and at
this point, the OS on the server machine commonly allo-
cates resources to track the TCP state. By sending these
requests in rapid succession, an attacker can exhaust the
resources on the machine to the point where it becomes
unresponsive, or crashes.
The server can attempt to reduce the impact of the
flooding by changing the resource allocation strategy that
it uses. One approach is to allocate minimal state when
the initial request is received, and only allocate all the re-
sources required when the connection is completed; this
is termed a SYN cache. Another approach is to allo-
cate no state, but instead send a cryptographic secret back
to the originator, called a cookie; hence the name SYN
cookie. Both approaches are intended to allow the ma-
chine to continue to provide its services to valid users.
The rest of this paper is structured as follows: Sec-
tion 2 examines the details involved in the SYN flood
Denial of Service attacks and examines the approaches
of different defenses. Section 3 details the experimental
setup used for testing, while Section 4 describes the cur-
rent system behavior and motivation for change. Section
5 discusses the SYN cache implementation and presents
the performance measurements from the change, while
Section 6 does the same for SYN cookies. Section 7
discusses related work, and the paper concludes with a
summary in Section 8.
2 TCP Denial of Service
A traditional TCP 3 way handshake for establishing con-
nections is shown in Figure 1, where state is allocated on
the server side upon receipt of the SYN to hold informa-
tion associated with the incomplete connection. The goal
of a SYN flood is to tie up resources on the server ma-
chine, so that it is unable to respond to legitimate connec-
tions. This is accomplished by having the client discard
the returning SYN,ACK from the server and not send the
final ACK. This results in the server retaining the partial
state that was allocated from the initial SYN.
The attacker does not necessarily have to be on a fast
machine or network to accomplish this. Standard TCP

incomplete
SYN,ACK
ACK
SYN
serverclient
connectioninitiate
connectioncomplete
connectioncomplete
connection
Figure 1: Standard TCP 3 way handshake.
will not time out connections until a certain number of
retransmits have been made, which usually is a total of
511 seconds[7]. Assuming a machine permits a max-
imum of 1024 incomplete connections per socket, this
means an attacker has only to send 2 connection attempts
per second to exhaust all allocated resources. In prac-
tice, this does not form a DoS attack, as existing incom-
plete connections are dropped when a new SYN request
is received. The time required for the server to send
a SYN,ACK and have the client reply is known as the
round trip time (RTT); if an ACK arrives at the server
but does not find a corresponding incomplete connection
state, the server will not establish a connection. By forc-
ing the server to drop incomplete connection state at a
rate larger than the RTT, an attacker is able to insure that
no connections are able to complete.
Each connection is dropped with probability, and
if the goal is to recycle every connection before the aver-
age RTT, an attacker would need to flood the machine at
a rate of
packets per second. For a listen queue
size of 1024, and a 100 millisecond RTT, this results in
about 10,000 packets per second. A minimal size TCP
packet is 64 bytes, so the total bandwidth used is only
4Mb/second, within the realm of practicality.
As the sender may forge their source IP address, a de-
fense that relies on filtering packets based on the source
IP will not be effective in all cases. Using a random
source IP address will also cause more resources to be
tied up on the server if a per-IP route structure is allo-
cated.
Often it is not possible to distinguish attacks from real
connection attempts, other than by observing the volume
of SYNs that are arriving at the server, so the machine
needs to be able to handle them in some fashion.
In order to defend against this type of attack, the
amount of the amount of state that is allocated should
be reduced, or even eliminated completely by delaying
allocation until the connection is completed. Two known
approaches to do this are known as SYN cache and SYN
cookies. The caching approach is similar to the exist-
ing behavior, but allocates a much smaller state structure
to record the initial connection request, while the cookie
approach attempts to encode the state in a small quantity
which is returned by the client when the TCP handshake
is completed.
2.1 Defenses
SYN caching allocates some state on the machine, but
even with this reduced state it is possible to encounter
resource exhaustion. The code must be prepared to han-
dle state overflows and choose which items to drop in
order to preserve fairness.
The initial SYN request carries a collection of options
which apply the TCP connection, these commonly in-
clude the desired MSS, requested window scaling for the
connection, use of timestamps, and various other items.
Part of the purpose of the allocated state is to record these
options, which are not retransmitted in the return ACK
from the client.
SYN cookies do not store any state on the machine,
but keep all state regarding the initial TCP connection in
the network, treating it as an infinitely deep queue. This
is done by use of a cryptographic function to encode all
information into a value that is sent to the client with the
SYN,ACK and returned to the server in the final portion
of the 3 way handshake. While this approach appears
attractive, it has the drawback of not being able to encode
all the TCP options from the initial SYN into the cookie.
These options are then lost, denying the use of certain
TCP performance enhancements.
A secondary problem related to cookies is that the
TCP protocol requires unacknowledged data to be re-
transmitted. The server is supposed to retransmit the
SYN,ACK before giving up and dropping the connec-
tion, whereupon a RST is sent to the client in order to
shutdown the connection. When SYN,ACK arrives at a
client but the return ACK is lost, this results in a disparity
about the established state between the client and server.
Ordinarily, this case will be handled by server retrans-
mits, but in the case of SYN cookies, there is no state
kept on the server, and a retransmission is not possible.
SYN cookies also have the property that the entire
connection establishment is performed by the returning
ACK, independent of the preceding SYN and SYN,ACK
transmissions. This opens the possibility of flooding the
server with ACK requests, in hopes that one will con-
tain the correct value which allows a connection to be
established. This also provides an approach to bypass
firewalls which restrict external connections by filtering

out incoming packets which have the SYN bit set, since
initial SYN packet is no longer required to establish a
connection.
Another difficulty with cookies is that they are in-
compatible with transactional TCP[6]. T/TCP works by
sending monotonically increasing sequence numbers to
the peer in the TCP options field, and uses previously re-
ceived sequence numbers to establish connections on the
initial SYN, eliminating the 3 way handshake. However,
use of the T/TCP sequence numbers is mandatory once a
TCP connection is initiated, and this requires the server
to record the initial sequence number, and whether the
T/TCP option was requested.
Thus cookies cannot be used as the normal line of de-
fense in a high performance server. The usual approach
is to use a state allocation mechanism, and fall back to us-
ing cookies only after a certain amount of state has been
allocated. This is the approach taken by the the Linux
kernel implementation.
3 Experimental Setup
The code base used was FreeBSD 4.4-stable, from
sources as of November 14th, 2001. The target machine
used for testing was an Intel PIII/850, with 320MB of
memory, and was equipped with an onboard Intel Ether-
Express 100Mb/s chip, an Intel 1000/Pro Gigabit adapter
and a NetGear GA620 Gigabit adapter. The NetGear
adapter was attached directly to a second machine that
acted as a packet source, while the Intel adapter was di-
rectly attached to a third machine that acted as a packet
sink. A fourth machine was connected via the 100Mb
port and was used for taking timing measurements of real
connection requests to the test machine.
A default route was installed on the test ma-
chine so that all incoming traffic from the source
was sent out to the sink via the other gigabit link.
The kern.ipc.somaxconn parameter, which controls the
maximum listen backlog, was raised to 1024, while
net.inet.tcp.msl was turned down to 30 milliseconds in
order not to run out of TCP ports. Mbufs and mbuf clus-
ters were set to 65536 and 16384 respectively, and the
system was monitored to insure that the mbuf limit was
not reached.
When SYN flooding the box, the source was config-
ured to generate SYN packets at a rate of 15,000 packets
per second. This rate was chosen as a load that the box
could reasonably handle without becoming susceptible
to receiver livelock. Under this load, the box was han-
dling upwards of 30,000 packets per second, incoming
and outgoing. The source addresses of the SYN packets
were randomly chosen from the 10.x.x.x subnet, and the
source port numbers and ISS were also randomly gener-
ated.
A small program that accepted and closed incoming
connections was run on the test machine, in order to pro-
vide a listen socket for incoming packets. Timing mea-
surements were taken on the control machine that was
attached to the 100Mb port, which involved taking 2000
samples of the amount of time required for a connect()
call to complete to the target machine.
4 Motivation
Initial tests were performed on the target machine using
an unmodified 4.4-stable kernel while undergoing SYN
flooding. The size of the listen socket backlog was varied
from the default 128 entries to 1024 entries, as permitted
by kern.ipc.somaxconn. The results of the test are pre-
sented in Figure 2.
In this test, with a backlog of 128 connections, 90%
of the 2000 connections initiated to the target machine
complete within 500ms. When the application specifies
a backlog of 1024 connections in the listen() call, only
2.5% of the connections complete within the same time
period.
The dropoff in performance here may be attributed to
the fact that the sodropablereq() function does not scale.
The goal of this function is to provide a random drop of
incomplete connections from the listen queue, in order to
insure fairness.
However, the queue is kept on a linear list, and in order
to drop a random element, a list traversal is required to
reach the target element. This means that on average,
of the total length of the queue must be traversed
to reach the element; for a listen queue backlog of 1024
elements, this leads to an average of , or
768 elements traversed for each incoming SYN.
Profiling results show that in this particular case, the
system spends 30% of its time in sodropablereq(), and
subjectively, is almost completely unresponsive. Ex-
amining the graph, we see that there is a considerable
dropoff in performance between the backlog cases of 768
entries and 1024 entries, the reason of which is unclear.
It is likely that there is a ’knee’ in the performance curve
is between these points, and system may have reached a
point of saturation.
For the rest of the paper, a listen queue backlog of
1024 entries is used, as this is a realistic value used on
production systems[4]. It also serves to illustrate the per-
formance gains from a syncache or syncookie implemen-
tation.
4.1 Implementation
The new implementation for FreeBSD provides a SYN
cache as the first approach for handling incoming con-
nections, and has every connection pass through the