Use IPtables or null route for blacklisting about 1 million IP addresses?

Question

I've come across a situation where a client needs to blacklist a set of just under 1 million individual IP addresses (no subnets), and network performance is a concern. While I would conjecture that IPTables rules would have less of a performance impact than routes, that's just conjecture.

Does anyone have any solid evidence or other justification for favoring either IPTables or null routing as solution for blacklisting long lists of IP addresses? In this case everything is automated, so ease-of-use isn't really a concern.

EDIT 26-Nov-11

After some testing and development, it appears that none of these options are workable. It appears that both route lookups and iptables do linear searches through the ruleset, and take simply too long to process this many rules. On modern hardware, putting 1M items in an iptables blacklist slows the server down to about 2 dozen packets per second. So IPTables and null routes are out.

ipset, as recommended by Jimmy Hedman, would be great, except that it doesn't allow you to track more than 65536 addresses in a set, so I can't even try to use it unless someone has any ideas.

Apparently the only solution for blocking this many IPs is doing an indexed lookup in the application layer. Is that not so?

---

More Information:

The usage case in this instance is blocking a "known offenders" list of IP addresses from accessing static content on a web server. FWIW, doing blocking through Apache's Deny from is equally slow (if not more so) as it also does a linear scan.

---

FYI: Final working solution was to use apache's mod_rewrite in conjunction with a berkeley DB map to do lookups against the blacklist. The indexed nature of berkeley DBs allowed the list to scale with O(log N) performance.

Answer 1

try using iptables and building multi-level tree to decrease number of lookups.

iptables -N rules_0_0_0_0_2
iptables -N rules_64_0_0_0_2
iptables -N rules_128_0_0_0_2
iptables -N rules_192_0_0_0_2
iptables -N rules_0_0_0_0_4
iptables -N rules_16_0_0_0_4

iptables -A INPUT -p tcp --dport 80 -s 0.0.0.0/2 -j rules_0_0_0_0_2
iptables -A INPUT -p tcp --dport 80 -s 64.0.0.0/2 -j rules_64_0_0_0_2
iptables -A INPUT -p tcp --dport 80 -s 128.0.0.0/4 -j rules_128_0_0_0_2
iptables -A INPUT -p tcp --dport 80 -s 192.0.0.0/4 -j rules_192_0_0_0_2

iptables -A rules_0_0_0_0_2 -s 0.0.0.0/4 -j rules_0_0_0_0_4
iptables -A rules_0_0_0_0_2 -s 16.0.0.0/4 -j rules_16_0_0_0_4

and so on - adding nesting levels; obviously you'll need an automatic way of building the rules and you should have chains just for the networks where you have one or more offenders - in this way you can reduce number of lookups that have to be done quite significantly and i think it might actually work.

Answer 2

This is exactly what ipset is for.

From its website http://ipset.netfilter.org/:

If you want to

• store multiple IP addresses or port numbers and match against the collection by iptables at one swoop;
• dynamically update iptables rules against IP addresses or ports without performance penalty;
• express complex IP address and ports based rulesets with one single iptables rule and benefit from the speed of IP sets

then ipset may be the proper tool for you.

It is written by a netfilter core team member Jozsef Kadlecsik (who also wrote the REJECT target) so this is the best choice I can think of.

It is even included in the recent kernels.

Answer 3

I have not tested this myself, but when I heard your problem description I instantly thought "pf" (as from OpenBSD).

pf has the concept of address tables which may just be what you're looking for.

According to some very cursory research I did, it would seem that this has the potential to scale better than ipset. According to the PF FAQ's chapter on Runtime Options, out of the box without tuning, pf supports a total of 1,000 tables, with a total of 200,000 entries across all tables by default. (100,000 if the system has <100MB physical memory). This leads me to believe that it's at least worth considering trying to test this to see if it works on any kind of useful level.

Of course, I'm assuming you're running your servers on Linux, so you'd have to have a seperate firewall box running some OS with pf (like OpenBSD or FreeBSD). You might also be able to improve throughput by doing away with any kind of stateful packet filtering at all.

Answer 4

Have you investigated using a FIB_TRIE instead of FIB_HASH.

FIB_TRIE should scale much better for your prefix counts. (/32s null routes are still prefixes, just very specific)

You might need to compile your own kernel to use it, but it help.

FIB_TRIE Notes