
% TEMPLATE for Usenix papers, specifically to meet requirements of
%  TCL97 committee.
% originally a template for producing IEEE-format articles using LaTeX.
%   written by Matthew Ward, CS Department, Worcester Polytechnic Institute.
% adapted by David Beazley for his excellent SWIG paper in Proceedings,
%   Tcl 96
% turned into a smartass generic template by De Clarke, with thanks to
%   both the above pioneers
% use at your own risk.  Complaints to /dev/null.
% make it two column with no page numbering, default is 10 point

% Munged by Fred Douglis <douglis@research.att.com> 10/97 to separate
% the .sty file from the LaTeX source template, so that people can
% more easily include the .sty file into an existing document.  Also
% changed to more closely follow the style guidelines as represented
% by the Word sample file. 
% This version uses the latex2e styles, not the very ancient 2.09 stuff.

% adapted for Ottawa Linux Symposium

\documentclass[twocolumn]{article}
\usepackage{ols,epsfig}
\begin{document}

%don't want date printed
\date{}

%make title bold and 14 pt font (Latex default is non-bold, 16 pt)
\title{\Large \bf Packet Mangling in The 2.4 Linux Kernel}

%for single author (just remove % characters)
\author{
Paul `Rusty' Russell \\
%{\em Your Department} \\
{\em Linuxcare}\\
%{\em Your City, State, ZIP}\\
% is there a standard format for email/URLs??
% remember that ~ doesn't do what you expect, use \~{}.
{\normalsize rusty@linuxcare.com, http://netfilter.kernelnotes.org/diary} \\
%
% copy the following lines to add more authors
% \smallskip
% Name Two Here \\
%{\em Two's Institution}\\
%% is there a standard format for email/URLs??
%{\normalsize two@host.site.dom, http://host.site.dom/twourl}
%
} % end author

\maketitle

% You have to do this to suppress page numbers.  Don't ask.
\thispagestyle{empty}


\subsection*{Abstract}
% nuked italics -- FD
Linux 2.4 contains new packet filtering and fully dynamic Network
Address Translation code.  This paper will cover the design decisions
and corner cases which were encountered in implementing these.

\section{Introduction}

Linux has had IP packet filtering and kernel-based accounting since
Linux 1.2.  In 2.0, Transparent Proxying, Masquerading and some port
forwarding were added.  In 2.2, general port forwarding became
available, packet filtering changed from ipfwadm to ipchains, the
routing code became capable of doing static NAT.  In 2.4, most of
these disparate methods were unified in a common filtering
infrastructure, called netfilter.

The redesign was meant to serve several important user goals:
\begin{enumerate}
\item Allow packet filtering in a user-comprehensible way.
\item Make packet filtering independent of Network Address Translation
(NAT).
\item Allow packet mangling in userspace.
\end{enumerate}

It was also meant to serve the following kernel-developer goals:
\begin{enumerate}
\item Remove filtering and NAT from the core stack (the IP stack is
hard enough to maintain without the 33 `\#ifdef
CONFIG\_IP\_TRANSPARENT\_PROXY', and 19 `\#ifdef
CONFIG\_IP\_MASQUERADE' inside the major ipv4 C source files).
\item Replace the simple `firewall hook' infrastructure with one
powerful enough to encompass NAT.
\item Remain independent of the (complex) Linux routing code: we don't
want to lose the power of rp\_filter.
\item Provide an efficient, flexible infrastructure for the network
stacks, which was not biassed towards the current implementations; it
should be powerful enough for future (unimagined?) uses.
\item Ensure that the packet filtering module was easily expandable,
to avoid instant obsolescence.
\end{enumerate}

\section{The Netfilter Infrastructure}

\begin{figure}[t]
\begin{center}
\begin{picture}(300,150)(0,200)
\put(0,200){\special{psfile = netfilter.eps hscale = 50 vscale = 70}}
\end{picture}\\
\end{center}
\caption{Netfilter Inside IPv4}
\end{figure}

Netfilter allows all protocols to register hooks, but we will
concentrate on IPv4 (IPv6 and DecNET have chosen similar hook
layouts), shown in Figure 1.  An arbitrary number of (numerically
ordered) functions can be registered to receive packets at any of
these points.

\subsection{Asynchronous Packet Handling}

In order to have asynchronous packet handling (usually passing packets
to userspace), each call to the {\tt NF\_HOOK} macro within the stack
must be at the end of a function: one of the arguments is the next
function to call if the packet is OK.  If one of functions at the hook
returns {\tt NF\_QUEUE}, then the packet is queued to the asynchronous
handler for that protocol: currently there is a netlink-based
userspace communication module for IPv4.

{\tt NF\_HOOK} is a macro so that this `okfn' argument can be inlined
in the case where there are no functions registered on a hook, and
vanishes entirely when {\tt CONFIG\_NETFILTER} is not enabled.

\subsection{Altering Packets On {\tt NF\_IP\_LOCAL\_OUT}}

In Figure 1 we show routing happening after the {\tt LOCAL\_OUT} hook.
Of course, routing must have happened before this, to determine the
packet's source address and maximum size.  Hence, we need to reroute
packets if they have been altered by this hook; this allows the
commonly-requested `transparent proxy for local users' feature.

Fortunately, the netfilter design includes a bitmask {\tt nfcache},
which indicates what a hook based its decisions upon, for a future
fast-forwarding method to take advantage of.  One of these bits is the
NFC\_ALTERED bit (meaning that this hook can never be cached), which we
can also use to decide whether another route checkup is required.

\subsection{Tunnel Semantics}

The flow of packets through Figure 1 is intuitive, but more complex
manipulations (such as entunnelling or detunnelling a packet for IPIP,
GRE, SIT or IPsec) were left undefined until quite recently.  It
became clear that the simplest fit with connection tracking was for an
entunnelled packet to be (artificially) passed through the {\tt
NF\_IP\_LOCAL\_OUT} hook.  Detunnelled packets are always reinjected
through {\tt netif\_rx}, and hence are treated as if they were
received normally.

\subsection{Hook Functions Which Fragment}

Hook functions are designed to return a single verdict ({\tt
NF\_ACCEPT}, {\tt NF\_DROP}, {\tt NF\_QUEUE}); not a stream of
packets, as would be required by a function which does IP packet
fragmentation.  For this reason, there is an {\tt NF\_STOLEN} verdict:
it indicates that the hook function has taken responsibility of the
packet, and it must not be freed or otherwise touched.  Also, each
hook function is passed a pointer to the {\tt okfn} argument, so it
can be called directly.  This argument must only be called directly by
hook functions with priority {\tt NF\_IP\_PRI\_LAST}, otherwise later
priority hook functions may be unexpectedly skipped.

\section{Backwards Compatibility}

A compatibility layer has been written to support {\tt ipfwadm} and
{\tt iptables} as modules.  These use a very hackish system for
implementing the {\tt REDIRECT} target (a simple list of redirected
ports which is checked each time) which is not sufficient for
transparent proxies, which could previously use {\tt getsockname()} to
determine the packet's destination address.

The MASQUERADE target uses the lower layers of the connection tracking
and NAT code, causing those parts of the code to be split into `core'
and `standalone' sections.  The more niche features such as port
forwarding and masquerading modules are not supported.

The three implementations all use the same range of setsockops, and so
cannot be used all at once.  The {\tt iptables} modules goes so far as
to return {\tt -ENOPROTOOPT} if the {\tt SET\_REPLACE} sockopt
specifies bogus length: this is causes ipchains to report that it is
`incompatible with this kernel'.

\section{\tt iptables}

{\tt iptables} began as an extensible version of 2.2's {\tt ipchains};
the main architectural difference was that the kernel only deals with
an entire table of rules, and provides the following operations via
{\tt getsockopt()} and {\tt setsockopt()} (now dynamically
registerable).

\begin{itemize}
\item[] GET\_INFO: \\ Gets the table size, number of entries and entry
points.
\item[] GET\_ENTRIES: \\ Gets the table (size must match that supplied
by user).
\item[] SET\_REPLACE: \\ Atomically replace entire table: returns old
64-bit rule counters.
\item[] SET\_ADD\_COUNTERS: \\ Atomically add in a set of counters.
\end{itemize}

New `match' functions (usually lower case) and new `target' functions
(usually upper case) can be registered: usually they are modules, with
a shared library counterpart to extend the {\tt iptables} userspace
tool.  Only simple IP address, interfaces, protocol number and
fragment matches are built-in: even TCP port/flags matching is an
extension (albeit one that is always present).

From here it was a trivial step to turn this into a generic `packet
matching' architecture, which could be used by the NAT code (to decide
how a connection should be mapped, based on the first packet).  Hence
each table was given a name:

\begin{itemize}
\item[filter] The packet filtering table (the {\tt iptables} tool acts
on this by default.
\item[mangle] Table designed to allow mangling before routing (usually
to set TOS or nfmark to alter routing behaviour).
\item[nat] Table for new connections to decide Network Address Translation.
\item[dropped] Special table to allow post-mortem of suspicious packets.
\end{itemize}

\subsection{Hooks, Extensions and Loops}

Each table specifies which hooks it is valid on: the {\tt filter}
table is optimally placed for simple packet filtering.  Registering a
table does not cause packets to begin flowing: you must register your
own functions on the netfilter hooks which feed in the packets
(eg. NAT only feeds packets for new connections to the {\tt nat}
table).

Some extensions are only valid in some tables.  For example, we only
allow the {\tt TOS} target in the {\tt mangle} table.  Others are only
allowed if packets are coming off a certain netfilter hook: the {\tt
mac} match extension is not valid from the {\tt LOCAL\_OUT} hook.
This requires that the kernel traverse the new table (using the
counters field in the rules to store back pointers, since we can't
recurse), marking rules with the bitmask of the hooks they can be
called from.  This also means that we can check for loops, and avoid a
runtime check.

\subsection{Tables and Alignment: It Seemed Like A Good Idea At The Time}

For maximal flexibility, the rules in the table needed to be of
variable length (it is easy to imagine a match target which was an
entire state machine, and wanted to store the program in the rule):
once the C structure semantics were abandoned, allowing a rule to have
any number of extended matches (eg. matching a tcp port and a mac
address) was a simple addition.

This means that the table must be laid out such that alignment
restraints are respected (both in userspace and kernel).  Initial
assumptions that aligning everything to {\tt \_\_alignof\_\_(void *)}
proved too weak: on 32-bit PowerPC, the alignment requirement of the
64-bit counters is 8 bytes.  Hence all match and targets (laid out in
the rule after the base {\tt struct ipt\_entry}) are padded out using
the IPT\_ALIGN() macro.

I'd be amazed if Ultrasparc (32-bit userland, 64-bit kernel) works at
all.

\subsection{Hook Reentry: REJECT and MIRROR}

The netfilter code itself relies on the `big reader' network lock
({\tt BR\_NETPROTO\_LOCK}) to protect the hooks, so doesn't need to
worry about reentrancy.  The {\tt iptables} code uses a read-write
spinlock, blocking local soft irqs ({\tt read\_lock\_bh()}) and a copy
of the rules per CPU, so target extensions can send packets which
reenter the iptables code, as long as they return {\tt NF\_DROP}.
Otherwise, the return pointers kept in the iptables rules will have
been mangled by the reentered packet, and strange behavior will
result (detected when {\tt CONFIG\_NETFILTER\_DEBUG} enabled).

The experimental {\tt MIRROR} target has has its own problems with
connection tracking: this target simply inverts the source and
destination IP addresses, injects the packet (after checking that it
will be routed out the same interface as the incoming packet), and
drops the original.  This could open a hole, if connection tracking
were to think this mirrored packet was creating a new connection from
the local machine: hence this target injects the packet directly to
the device, in voilation of the convention established by {\tt
REJECT}.

\section{Connection Tracking}

\begin{figure}[t]
\begin{center}
\begin{picture}(300,150)(0,200)
\put(-10,200){\special{psfile = conntrack.eps hscale = 40 vscale = 70}}
\end{picture}\\
\end{center}
\caption{Connection Tracking for IPv4}
\end{figure}

Connection Tracking provides tracking of all packets which pass
through the stack, required by dynamic NAT and stateful packet
filtering: it does this by hooking in at {\tt NF\_IP\_PRE\_ROUTING}
and {\tt NF\_IP\_LOCAL\_OUT} as shown in Figure 2.  It uses the `nfct'
field in the skbuff, allowing a destructor to be called when the
skbuff is freed.  This intrustion into the stack was grudgingly
implemented following failed (and extremely ugly) experiments using
the `nfmark' field to hold the pointer to the connection structure,
which required continual sanity checks to ensure that this pointer was
still valid before dereference.

We must know two things about any packet: what connection it is
related to, and how it is related:
\begin{itemize}
\item[NEW] The packet is attempting to start a new connection, or is a
retransmit of one.
\item[ESTABLISHED] A reply packet, or a packet on a connection which
has already seen replies (this can be either way).
\item[RELATED] An ICMP error in either direction, or a NEW packet for
a connection which is related to another connection (eg. ftp data
connection).
\item[INVALID] Not part of any connection, or out of memory.
\end{itemize}

\subsection{(De-)fragmentation}

For accurate connection tracking, we must (prematurely) defragment:
this means that all packets in any connection must pass through this
box, which is already a connection tracking requirement.  For packets
passing through {\tt PRE\_ROUTING}, forwarding the packet will
refragment it; for packets defragmented at {\tt LOCAL\_OUT}, we need a
tiny `refragment' hook at {\tt POST\_ROUTING}.

Concerns about speed of such operations are generally invalid:
fragments are the antithesis of speed already.  NFS over a LAN is the
exception: two extra copies of the packet are now done as the packet
passes through a connection tracking box.  Fortunately, such uses seem
to be rare, since neither packet filtering nor NAT are generally
combined with NFS.

\subsection{Use And Abuse Of The {\tt nfct} Field}

The {\tt nfct} field in the skbuff is a {\tt struct nf\_ct\_info}
pointer:

\begin{verbatim}
struct nf_conntrack {
    atomic_t use;
    void (*destroy)(struct nf_conntrack *);
};

struct nf_ct_info {
    struct nf_conntrack *master;
};
\end{verbatim}

When destroying the skbuff, if the {\tt nfct} field is set, the count
is decremented: if zero, the {\tt destroy} function is called; in our
case this destroys the connection structure.  The double indirection
is used because we need to store both the connection and the
relationship inside this pointer (using the bottom 3 bits was
blecherous).  So the {\tt nfct} points into an array of pointers to
the connection structure: this array is inside the connection
structure itself, so we can tell which element is being pointed to,
which reflects which of the seven states (some states have two
directions) this packet is in.

\subsection{ICMP Tracking}

\begin{figure}[t]
\begin{center}
\begin{picture}(300,150)(0,200)
\put(0,200){\special{psfile = icmptrack.eps hscale = 80 vscale = 70}}
\end{picture}\\
\end{center}
\caption{ICMP Tracking}
\end{figure}

Tracking ICMP errors which relate to a connection is relatively
simple: when an ICMP error is received, the packet within it will be
the reverse of the packet we would normally see: we reverse it and do
a lookup.  This is shown in Figure 3.

\subsection{Locking and Module Counts}

A single read-write spinlock protects the connection tracking hash
table: each connection is in the hash table twice (one `tuple' for
each direction).  The packet's tuple is extracted, and a lookup is
done holding the read lock: if found, the {\tt nfct} field in the
skbuff is set and the count on the connection incremented.  If it is
not found, the lock is dropped, a new connection is created, a write
lock is grabbed, and the lookup repeated (if it now succeeds, we free
the new connection and loop), before the new connection is inserted.

This optimizes for the common case: already-established connection.

We keep track of the total number of connections, but do not reflect
this in the module usage count: the sysadmin can remove the module
independent of (hostile) network traffic.

\subsection{Connection Confirmation}

We track connections before packet filtering and route verification,
but we don't want a (filtered-out) flood to fill our connection table,
nor do we want a race: marking a faked `reply' as {\tt ESTABLISHED} on
a connection created by an about-to-be-dropped packet.

Hence, in the very-final `defragment' hook function on {\tt
POST\_ROUTING}, and on another {\tt NF\_IP\_PRI\_LAST} hook function
on {\tt LOCAL\_IN}, we set a bit to `confirm' the connection: if the
packet gets filtered, the connection is never confirmed.  It is only
at this point that we increment the usage count again and start a
destruction timer for the connection: until then, the skbuff holds the
sole reference, meaning that the connection will be immediately
destroyed should the packet be dropped.

ICMP replies, or packets in the reply direction will never match
unconfirmed connection.  The exception is locally-generated ICMP
errors and TCP RST packets as generated by the REJECT target.  We make
sure that neither of these causes the connection to be confirmed as it
passes the {\tt POST\_ROUTING} hook: only packets in state {\tt NEW}
can set this bit.

\section{Connection Timeouts}

The code for tracking TCP connections is stolen shamelessly from the
2.2 kernel: the fact that it works at all is a testimony to how hard
this is to screw up.  However, it is suboptimal and should be
reviewed; the {\tt ESTABLISHED} timeout has already been increased to
5 days, to match ipfilter's example.

Timeout for tracking UDP connections was recently enhanced: 30 seconds
is great for DNS and other `one shot' services, but terrible for ICQ.
Now, the timeout is increased to 3 minutes if another packet is seen
after traffic has been seen in both directions (implying some kind of
UDP stream).

\subsection{Denial Of Service}

A remote user must not use up all memory by flooding with new
connections.  Using a hard limit on the number of connections is
almost as bad: the administrator will not be able to ssh into her own
box.  We reduce the scope of this problem by four main methods:

\begin{enumerate}
\item The connection limit is adjustible through the sysctl {\tt
net/ipv4/ip\_conntrack\_max}.
\item Don't track connections created by dropped packets once packet
is dropped.
\item Delete `never-seen-reply-packet' TCP connections when a RST
packet is seen (port scanners).
\item Early drop when a limit is reached.
\end{enumerate}

Early drop works by having a pointer sweep through the hash table:
when we reach the connection limit, we traverse that hash chain
backwards (from oldest to newest), and prematurely time out the first
unreplied connection.  This `oldest' approximates `least recently
used', with the sweep providing some pseudo-randomness: we increment
the pointer each time we hit the connection limit.

If there is nothing in this hash chain, then we do the same traversal
in the hash chain {\it which the new connection is about to be
placed:} this prevents bombing a single hash chain.

This does not protect against SYN flood attacks through the box: if we
see replies (SYN/ACK packets) on the connections, they are immune to
the early timeout systems above.  Hence it is important to ensure that
the sum of the TCP backlogs on the services behind the connection
tracking box is less than the maximum number of connections: using SYN
cookies on the server actually means that the DoS is moved to the
connection tracking box itself.

\subsection{TCP Sequence Number Tracking}

Guido van Rooij has written an excellent analysis of ipfilter's TCP
Sequence Number Tracking implementation \cite{rooij}.

Currently, our connection tracking module does not implement sequence
number tracking: it would be most useful for recognizing successful
three-way handshakes (thus allowing early timeout of incomplete
handshakes under stress), and timed-out TCP keepalives.

\subsection{Broadcast Packets}

There is no point tracking broadcast packets, as they will never see
replies.  However, without routing (in {\tt PRE\_ROUTING}) it is not
possible to identify them, so we do not bother (and I did not find a
way of identifying outgoing broadcasts either).  These bogus entries
merely clutter the connection tracking table, but as they are easily
deleted under stress, it is of little concern.

\subsection{FTP}

FTP is a classic, well-known nightmare; the packet payload needs to be
examined to identify related connections which should be expected.
Partial FTP messages is one case where the connection tracking code
will actually drop a packet (rather than mark it as invalid), to try
to force a retransmission which can be accurately tracked (wuftpd will
do this occasionally, as it gets hit by Nagle).

It is important to not to simply accept all `PORT' commands or `PASV'
responses: it is frequently possible to convince a client or server to
evoke these embedded in another message, then play with TCP window
sizes to cause it to be aligned on a packet boundary correctly.  Hence
we track the sequence number of the last `$\backslash$n' at the tail of a
packet, and insist that the pattern occur after that.

\section{Network Address Translation}

\begin{figure}[t]
\begin{center}
\begin{picture}(300,150)(0,200)
\put(0,200){\special{psfile = nat.eps hscale = 50 vscale = 70}}
\end{picture}\\
\end{center}
\caption{NAT For IPv4}
\end{figure}

The implementation of Network Address Translation on top of netfilter
is designed to provide full, dynamic, port translation, with support
for arbitrary protocols (eg. TCP, UDP, IPIP) and subprotocols (FTP,
IRC)\footnote{At the other end of the scale is the routing code's
(static, one way) Fast NAT.}  It registers onto the hooks {\tt
PRE\_ROUTING}, {\tt POST\_ROUTING} and {\tt LOCAL\_OUT} (before packet
filtering).

\subsection{Not Interfering With Other Systems}

The NAT system alters the packets destination {\bf before} routing at
the {\tt PRE\_ROUTING} and {\tt LOCAL\_OUT} hooks, and the packet
source at the {\tt POST\_ROUTING} hook.  This means that the routing
system does not need to know that the packet has been transformed,
neither do the packet filtering rules.  In both cases, the packets
seem to be flowing unmangled between the two realms.  For example, if
we are doing Source NAT (SNAT) to map packets coming out of our
192.168.1.0 network onto our public IP address of 1.2.3.4, the routing
code and packet filtering code sees packets from 192.168.1.0 to
1.2.3.4, as the source alteration happens just before the packet is
placed on the wire, at {\tt POST\_ROUTING}, and sees replies from
1.2.3.4 to 192.168.1.0, as destination alteration happens at {\tt
PRE\_ROUTING}.

We do need to take special care when altering the destination of
packets at the {\tt LOCAL\_OUT} hook: if this causes the packet to be
sent out a different interface, it will also need its source IP
address altered.  In this case, the source IP address is altered at
that hook, to preserve the transparency for the routing and packet
filtering code.

\subsection{Untracked Packets, and Packets on Established Connections}

When a packet is seen which is part of a connection which has {\bf
not} had its translation established at that hook, the packet is
passed through the {\tt nat} table beginning the {\tt PRE\_ROUTING},
{\tt LOCAL\_OUT} or {\tt POST\_ROUTING} chain.  If it is not dropped,
this sets the translation for all future packets at that hook, as well
as the opposite translations for reply packets at the opposing hook.

If there is no connection associated with this packet, it is dropped.
This is to ensure that we do not stop NAT'ing connections when the box
is under stress, but has the unfortunate side-effect of preventing
`strange' packets (such as generated by network test tools).

\subsection{Implicit NAPT}

Generally, the NAT code tries to make the minimal mapping possible to
put the connection into the target source/destination range.  In some
cases, even when the the user has not specified that NAT be done, the
connection is already taken (eg. local connections over which as
connection has already been masqueraded), and the code will manipulate
the source protocol-part (port) of the connection, if it knows how.
In this case, the UDP and TCP code preserves the port ranges 1-511,
512-1023, and above 1024.

\subsection{Dan Kegel's Peer-to-peer Gaming NAT Requirements}

Dan Kegel developed a draft for NAT gateways to be usable by
peer-to-peer gaming software, while working at Activision
\cite{kegel}.  It comes down to:

\begin{quotation}
     If a host behind a NAT sends a series of packets from a single
     UDP port, the packets as relayed by the NAT should also appear to
     come from a single host and UDP port.
\end{quotation}

This means we keep a hash of outgoing Src IP/Src Port/protocol tuples,
for fast lookup, and always follow that previous mapping if it is
available and within the source range specified (if any).  This
overrides the `minimal change' heuristic.

\subsection{Fragments}

The NAT code can only handle unfragmented packets, for simplicity.
Fragmented packets passing through the box have are defragmented by
the connection tracking code, then are fragmented again upon
forwarding: in order to provide source NAT at {\tt POST\_ROUTING}, we
defragment again (and connection tracking will refragment afterwards).

As the IP stack now preserves connection tracking information across
fragmentation and defragmentation of packets, it would be possible to
do NAT on these fragments directly, as long as the following
conditions are met:
\begin{enumerate}
\item nfct is set on the fragment.
\item The NAT for this hook has already been initialized (we need the
whole packet if we're to pass it through the {\tt nat} table).
\item There is no NAT helper for this connection (eg. ftp).
\end{enumerate}

\subsection{An Aside: NAT of Fragments}

Compressing address space using NAPT (network address port
translation) can corrupt sessions if packets are fragmentable: two
packets could have the same fragment ID, and get translated to have
the same protocol/srcip/dstip.  This could be overcome by setting our
own fragment identifier on every IP packet which doesn't have DF set,
which sacrifices transparency (eg. ICMP errors).  This is the Net's
way of saying `use transparent proxies'.

It is theoretically possible to do full NAPT without defragmenting, as
follows:
\begin{enumerate}
\item For a non-head fragment, find possible translations (any
matching that source IP, destination IP and protocol): if none have
{\tt REQUIRE\_COMPLETE\_PACKETS} set, translate fragment once for each
one, and spray out.  Otherwise gather fragments.
\item When a head fragment arrives, find the connection it relates to,
and only do that translation.
\item If the head fragment does not match an existing connection, use
it to start a new connection, set {\tt REQUIRE\_COMPLETE\_PACKETS} on
it, and drop the packet.
\item Set {\tt REQUIRE\_COMPLETE\_PACKETS} on any new connection which
needs a helper (which may examine data).
\end{enumerate}

The NAPT gateway is now a fragment-bomb exploder: the current NAT code
always maps to the least used srcip/dstip pair available for that
protocol.

A less sophisticated NAPT implementation (which never needed to
examine entire packets to establish initial mapping, and had no
helpers) could simplify this approach furthur.

\subsection{ICMP Translation}

In the section on ICMP Tracking, we inverted the ICMP error payload
and did a normal lookup.  For ICMP errors generated between the NAT
box and the server, we will have done some translation, hence the ICMP
payload will not look like the original packet.  Similarly for errors
generated between the client and the NAT box; the payload will not
look like a server reply, which would have been translated.

Inverting the payload is only neccessary when we are doing NAT:
otherwise the two hashes of the connection are the simple inverse of
each other, and we would find the connection by finding the other
half.

The exception is locally-generated ICMP errors before SNAT is done:
they may correspond to ICMP packets heading the other way, which we do
not normally see.  Hence locally-generated ICMP errors have an extra
`non-inverted' lookup.  This does not handle the case of double NAT,
where the packet is in a no-man's land which relates to no known
connection.  This case is rare, and would have to be handled by the
NAT code itself, which already has a hash of the Source IP/Source
Port/Protocol hash (although the replies would need to be placed in
the hash).  I'm waiting for someone to encounter this in the field,
before I fix it...

When translating ICMP errors, it is not strictly neccessary to alter
the source IP address, but we do (altering it to appear to be from the
server or client, depending on the direction).  Some people use NAT
for anonymizing, and many people block all packets from the Private
Internet Addresses (both these groups are foolish, but in different
ways).  This gives strange traceroute results.

We drop locally-generated ICMP Redirect messages related to
connections which have non-null NAT: both machines will get upset if
they begin talking directly.  This scenario (redirecting a connection
back into the same network) is also the one case where double-NAT is
required: if the source IP address is not changed, the server will
attempt to respond directly to the client.

\subsection{Masquerading}

Linux's `masquerading' is a specialized form of Source NAT, but it
still exists in the form of the `MASQUERADE' target extension.  It is
exactly the same as using `SNAT' with the interface address, except
that all connections are deleted whenever the (original outgoing)
interface goes down, or changes address.

This is most useful for dialup connections with dynamic IP addresses:
when the link returns, we don't want to send out packets from the old
address (especially irritating for DNS requests which keep the stale
connection alive).  It is extremely harmful for static IP addresses,
and should {\bf not} be used there.

\subsection{FTP}

NAT for FTP makes connection tracking for NAT seem like a kindergarten
entrance exam.

Altering the data inside an FTP packet may mean changing its length,
as the address and port are sent as an ASCII string: comma-separated
numbers.  This means:

\begin{enumerate}
\item Adjusting all sequence numbers for packets in the same direction
which originate after that point.
\item Adjusting (in reverse) all acknowledgement numbers for packets
in the reverse direction after that point.
\item Adjusting all retransmissions the same way.
\item Checking that we don't enlarge packets over 64k.
\item Removing `SACK OK' options from SYN packets.
\end{enumerate}

Fortunately, we can assume that only one of these adjustments will be
in the current window at any time, due to the command/response nature
of the FTP protocol.  Theoretical MTU path discovery problems also do
not arise, due to the short nature of these packets.

Simply mapping the expected ftp data connection to the client or
server is not enough, as in many cases they will refuse it if the
source IP address does not match the ftp control connection: hence any
data connections must have the source IP mangled the same was as the
control connection, even if not strictly neccessary.

\section{Acknowledgments}

The Networking Trimverate: Dave Miller, who taught me how to swear in
source code, Alexey Kuznetsov who knows more about networking than I
ever will, and Andi Kleen who always appears in the most unlikely
parts of the code.

The netfilter core team: Marc Boucher, James Morris.

Everyone who hacked on netfilter: they're all on the scoreboard.

Watchguard for sponsoring the early work, Linuxcare for sponsoring it
now.

\section{Availability}

There are three netfilter home pages:

{\tt http://netfilter.kernelnotes.org}\\
{\tt http://netfilter.filewatcher.org}\\
{\tt http://www.samba.org/netfilter}\\

\begin{thebibliography}{99}

\bibitem[Kegel]{kegel} D.~Kegel, {\em NAT and Peer-to-peer networking} \\
{\tt http://www.alumni.caltech.edu/\~{}dank/peer-nat.html}

\bibitem[van Rooij]{rooij} G.van Rooij,
{\em Real Stateful TCP Packet Filtering in IP Filter} \\
{\tt http://www.iae.nl/users/guido/papers/tcp\_filtering.ps.gz}

\end{thebibliography}
\end{document}
