Re: Having too many access lists in Linux

Roberto Nibali (ratz@drugphish.ch)
Fri, 29 Mar 2002 09:02:40 +0100


Hello,

Sorry for the length of this email but we just did tests on that topic
and I'd like to share some results with you (and whoever might read this).

> I just curious (since I haven't tried this), what happened to linux (the
> kernel especially), when a Linux Box has for example 100 access lists,
> 500 access lists, 1000 access lists, etc ?

I assume you mean rules (with regard to your text below)? With ACL in a
Linux environment I mean filesystem ACLs or TE in B+ security systems.

> Will I see a process consuming 100% of CPU Resources, or people will
> feeling much slower when they are accessing my server, or the box starts
> dropping some packets ?

This is indeed a very interesting topic and depends on a huge amount of
parameters as thinking and tests in our lab have shown. I wrote a paper
about it. This paper however had been stripped down since it contained
company specific information but the interesting graphs are still in
there. You can find it at [1]. It's called "Packetfilters and their
Behavior under high Network Load:The impact of extreme (real) conditions
analyzed on Linux, Solaris and OpenBSD". It had been done under strict
time constraints since we're not a testing lab but a security company. I
can summarize what we've done for people that don't want to read it:

Problem:
--------
Coming from ipfwadm, used to having 3 chains only, our company had
written a firewall suite (mostly userspace) on top of that. Eventually
the transition to ipchains came and we startet migrating the codebase to
the new framework. This old legacy (addressing 3 chains only) was not
redesigned because at that time there was no need to and boxes weren't
as fast anyway to have a box filter 100Mbit/s. Plus not a lot of
e-commerce projects really had more then 10Mbit/s of traffic.

Now in the meantime we started building packetfilters with 16-24 NIC's
on a box depending on the overall filtering needs. This worked fine
until we reached the limits of ipchains (when used in the legacy
framework). The worst case chain traversing had always been suspect to
be inefficient when no active rule reordering had been taken place. I
once started implementing active rule reordering by having a kernel
thread parsing the chain tables and account the bytes and packets. But
since this would lead to a change of semantics of the firewall itself I
dropped that idea.

Action:
-------
So we started some primitive tests which actually turned out to reflect
the 'real world' you're facing when doing 'high speed' packetfiltering.
First thing it showed us was that you can filter extremely efficient and
with a lot more rules loaded into the kernel when your L2 cache is big.
The bigger the better. Don't take a Celeron to do serious packet
filtering. We've done tests on Tualatins and I've talked to some guy
that did tests on Xeon's. With a 500MHz Celeron raw TCP throughput
(payload ~ MTU) dropped down to 8Mbit/s when having more than 500 rule
entries in the input chain (which is not a lot) and having the matching
rule at the end of the chain. With a Tualatin we were able to sustain a
92Mbit/s throughput until we hit the 2000 rule limit. Starting from
there performance goes down linearly first and then quadratic. It seems
to have to do with L1-L2 cache transitions or ineffective cache
reloading because not all rules can be hold in the hot cache anymore.

Well, we've been stuck with 5000 and more unordered rules in one chain.
This can happen if you have legacy software and as everyone with
software engineering skills knows it is not feasable to rewrite a big
software suite when the overall needed men programming power can't be
raised without risking important market losses during the development
phase. [We've done it, we've ported the whole stuff from an architecture
of the 3-chain approach to a multiple chain architecture and preliminary
support for iptables. And we have no CPU/kernel related problems anymore
ever since. ;)]

Solutions:
----------
Another very interesting way of doing high speed packetfiltering is by
policy routing achieved with iproute2. Add rules for every net entity
you'd like to address and put blackhole routes to the reference routing
tables to block specific net entities and use bounce table walking to
realize the inter-chaining jumps you have with the '-j' target. This is
extremely fast (think CISCO IOS) but a little complex to setup and I
haven't yet found a meta definition language to map a network onto a
routing policy in a way that you only allow traffic you'd like to
(policy: DENY/DROP).

Active rule reordering: It should be possible to reorder rules according
to their usage so the most used rules have an early match. This is not
such an issue anymore with stateful packetfiltering where we have
matches with the '-state' directive.

Buy decent hardware and use 2.4.x kernels for network related task!

Use QoS to rate limit stuff or give administrational 'tasks' (ssh) high
priority. Mark packets with iproute2 and set up a CBQ scheduler.

Do packet filtering in user space so the kernel doesn't use up all
available CPU time for the filtering process. A user space filter
wouldn't simply get that much processing time.

> (what I meant access lists is the TCP filtering managed thru ipchains,
> iptables, etc.)

Conclusion:
-----------
As a fast conclusion but also reflecting the truth in 99% of the time I
need to tell you that in all our tests we've seen that TCP filtering
under 2.4.x and iptables is _much_ more efficient than with 2.2.x and
ipchains when it comes to a lot of rules and a lot of NICs. This can be
due to the softnet framework and/or the improved dequeuing mechanism
(which will yet be improved in 2.5.x by Hadi/Kuznetsov), the more
efficient target/chain handling, reduced CPU overhead for NICs with
integrated TX/RX zerocopy functionality and definitely because with a
stateful packetfilter you tend not to have as many rules for the same
kind of "security" as you would have with ipchains.

And to come back to your question: Depending on the amount of rules in a
chain and the L2 cache size of your CPU and on the NIC you're having you
might encounter everything, from random early packet drops in the rx
queue to late drops in the packet filter engine due to inefficiency of
matching packets. This is _very_ annoying if you need to do machine
maintainance via ssh and a login takes you 40 Minutes (been there done
that). And the bigger annoyance is that you can't log the packets
anymore and as everybody in the security business knows, not having
logfiles is about the worst thing that can happen to you besides getting
hacked :). Customers tend to care and know the difference.

[1] http://www.terreactive.ch/home/archive/pdf/pf-speed-test.pdf

HTH. Best regards,
Roberto Nibali, ratz

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/