[ANNOUNCE] new iptables module match large amount of ip addresses

[ANNOUNCE] new iptables module match large amount of ip addresses

[Mikulas Patocka]

Hi

Here I submit an iptables module that can match large amounts (millions) 
of ip addresses efficiently using binary search. I needed it to protect my 
home network from spam. It may be useful for other people too, so if you 
want it, you can take it and add it to the kernel.

Get the patches for netfilter and kernel at:
http://artax.karlin.mff.cuni.cz/~mikulas/xt_ipfile/
(you need to copy the file include/linux/netfilter/xt_ipfile.h from kernel 
sources to /usr/include/linux/netfilter/ to compile the userspace)

The main features:
- fast matching of large amount of ip addresses using binary search.
- an ability to match ranges of addresses or address/mask subnets.
- fast loading of the addresses (on Pentium 3 850, 2 million addresses 
load in 5.5s, if they are already sorted in the file, the load time is 
just 1.5s).
- memory efficient --- consumes only 8 bytes per address.

USAGE:

prepare a file with addreses, in this example /root/firewall/bad-ips. One 
entry per line, the allowed formats are:
1.2.3.4
1.2.3.0/24
1.2.3.4-1.2.3.8

insert it into iptables with:
iptables -A SPAM -m ipfile --src-file /root/firewall/bad-ips -j DROP

The module doesn't support ipv6 because I don't use it, but it's generic 
enough that it could be extended for it. It could be also extended to 
match ethernet MAC addresses.

Mikulas

Re: [ANNOUNCE] new iptables module match large amount of ip addresses

[Eric Leblond]

[-- Attachment #1: Type: text/plain, Size: 1900 bytes --]

Hi,

Le jeudi 17 septembre 2009 à 21:15 +0200, Mikulas Patocka a écrit :
> Hi
> 
> Here I submit an iptables module that can match large amounts (millions) 
> of ip addresses efficiently using binary search.

What are the differences with ipset ? (http://ipset.netfilter.org/)

BR,

>  I needed it to protect my 
> home network from spam. It may be useful for other people too, so if you 
> want it, you can take it and add it to the kernel.
> 
> Get the patches for netfilter and kernel at:
> http://artax.karlin.mff.cuni.cz/~mikulas/xt_ipfile/
> (you need to copy the file include/linux/netfilter/xt_ipfile.h from kernel 
> sources to /usr/include/linux/netfilter/ to compile the userspace)
> 
> The main features:
> - fast matching of large amount of ip addresses using binary search.
> - an ability to match ranges of addresses or address/mask subnets.
> - fast loading of the addresses (on Pentium 3 850, 2 million addresses 
> load in 5.5s, if they are already sorted in the file, the load time is 
> just 1.5s).
> - memory efficient --- consumes only 8 bytes per address.
> 
> USAGE:
> 
> prepare a file with addreses, in this example /root/firewall/bad-ips. One 
> entry per line, the allowed formats are:
> 1.2.3.4
> 1.2.3.0/24
> 1.2.3.4-1.2.3.8
> 
> insert it into iptables with:
> iptables -A SPAM -m ipfile --src-file /root/firewall/bad-ips -j DROP
> 
> The module doesn't support ipv6 because I don't use it, but it's generic 
> enough that it could be extended for it. It could be also extended to 
> match ethernet MAC addresses.
> 
> Mikulas
> --
> To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
-- 
Eric Leblond <eric@inl.fr>
INL: http://www.inl.fr/
NuFW: http://www.nufw.org/

[-- Attachment #2: Ceci est une partie de message numériquement signée --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [ANNOUNCE] new iptables module match large amount of ip addresses

[Mikulas Patocka]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 736 bytes --]

On Thu, 17 Sep 2009, Eric Leblond wrote:

> Hi,
> 
> Le jeudi 17 septembre 2009 a 21:15 +0200, Mikulas Patocka a écrit :
> > Hi
> > 
> > Here I submit an iptables module that can match large amounts (millions) 
> > of ip addresses efficiently using binary search.
> 
> What are the differences with ipset ? (http://ipset.netfilter.org/)
> 
> BR,

What I wrote is static --- once loaded, then used. The only way to update 
the addresses is to reload it. Ipset is dynamic (and has more memory 
consumption because of it). In my implementation, the kernel reads the ip 
addresses, in ipset, the userspace tool reads them. 

I didn't know about ipset before because it is not in the kernel (will it 
ever be?)

Mikulas

Re: [ANNOUNCE] new iptables module match large amount of ip addresses

[Jan Engelhardt]

On Thursday 2009-09-17 21:15, Mikulas Patocka wrote:
>
>Here I submit an iptables module that can match large amounts (millions) 
>of ip addresses efficiently using binary search.

So you just reinvented xt_geoip...

>- fast matching of large amount of ip addresses using binary search.
>- an ability to match ranges of addresses or address/mask subnets.
>- fast loading of the addresses (on Pentium 3 850, 2 million addresses 
>load in 5.5s, if they are already sorted in the file, the load time is 
>just 1.5s).
>- memory efficient --- consumes only 8 bytes per address.


xt_geoip uses less than that -- 8 bytes per range. Of course it depends 
on the data, but on the average, since large netblocks is used, it's 
much better than 8 per address.

Re: [ANNOUNCE] new iptables module match large amount of ip addresses

[Mikulas Patocka]

On Fri, 18 Sep 2009, Jan Engelhardt wrote:

> On Thursday 2009-09-17 21:15, Mikulas Patocka wrote:
> >
> >Here I submit an iptables module that can match large amounts (millions) 
> >of ip addresses efficiently using binary search.
> 
> So you just reinvented xt_geoip...

I am wondering, if there are two approaches for matching large amounts of 
addresses (xt_geoip and ipset), why is none of them in the kernel?

I was saying how OpenBSD is better than Linux because OpenBSD has 
tree-based firewall tables --- hmm --- well --- Linux has them too, except 
that noone can really find them because they are not in the kernel.

> >- fast matching of large amount of ip addresses using binary search.
> >- an ability to match ranges of addresses or address/mask subnets.
> >- fast loading of the addresses (on Pentium 3 850, 2 million addresses 
> >load in 5.5s, if they are already sorted in the file, the load time is 
> >just 1.5s).
> >- memory efficient --- consumes only 8 bytes per address.
> 
> xt_geoip uses less than that -- 8 bytes per range. Of course it depends 
> on the data, but on the average, since large netblocks is used, it's 
> much better than 8 per address.

My code uses 8 bytes per range too, not really per address.

Mikulas

Re: [ANNOUNCE] new iptables module match large amount of ip addresses

[Fred Moyer]

On Thu, Sep 17, 2009 at 12:15 PM, Mikulas Patocka
<mikulas@artax.karlin.mff.cuni.cz> wrote:
> Hi
>
> Here I submit an iptables module that can match large amounts (millions)
> of ip addresses efficiently using binary search. I needed it to protect my
> home network from spam. It may be useful for other people too, so if you
> want it, you can take it and add it to the kernel.

I'm not familiar with xt_geoip or ipset, but from the first look at
this module I want to say thank you!  This is the perfect tool for a
problem I have been wanting to solve for a while.



>
> Get the patches for netfilter and kernel at:
> http://artax.karlin.mff.cuni.cz/~mikulas/xt_ipfile/
> (you need to copy the file include/linux/netfilter/xt_ipfile.h from kernel
> sources to /usr/include/linux/netfilter/ to compile the userspace)
>
> The main features:
> - fast matching of large amount of ip addresses using binary search.
> - an ability to match ranges of addresses or address/mask subnets.
> - fast loading of the addresses (on Pentium 3 850, 2 million addresses
> load in 5.5s, if they are already sorted in the file, the load time is
> just 1.5s).
> - memory efficient --- consumes only 8 bytes per address.
>
> USAGE:
>
> prepare a file with addreses, in this example /root/firewall/bad-ips. One
> entry per line, the allowed formats are:
> 1.2.3.4
> 1.2.3.0/24
> 1.2.3.4-1.2.3.8
>
> insert it into iptables with:
> iptables -A SPAM -m ipfile --src-file /root/firewall/bad-ips -j DROP
>
> The module doesn't support ipv6 because I don't use it, but it's generic
> enough that it could be extended for it. It could be also extended to
> match ethernet MAC addresses.
>
> Mikulas
> --
> To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [ANNOUNCE] new iptables module match large amount of ip addresses

[Jan Engelhardt]

On Friday 2009-09-18 01:01, Mikulas Patocka wrote:
>> On Thursday 2009-09-17 21:15, Mikulas Patocka wrote:
>> >
>> >Here I submit an iptables module that can match large amounts (millions) 
>> >of ip addresses efficiently using binary search.
>> 
>> So you just reinvented xt_geoip...
>
>I am wondering, if there are two approaches for matching large amounts of 
>addresses (xt_geoip and ipset), why is none of them in the kernel?

Because, so I would estimate, Patrick would decline patches with the 
reasoning of redundant code. Especially so "IPMARK".

>I was saying how OpenBSD is better than Linux because OpenBSD has 
>tree-based firewall tables --- hmm --- well --- Linux has them too, except 
>that noone can really find them because they are not in the kernel.

You can build trees of chains with iptables. (Which would be quite a 
fast thing if you do not have modules at hand.)

Re: [ANNOUNCE] new iptables module match large amount of ip addresses

[Mikulas Patocka]

> >I was saying how OpenBSD is better than Linux because OpenBSD has 
> >tree-based firewall tables --- hmm --- well --- Linux has them too, except 
> >that noone can really find them because they are not in the kernel.
> 
> You can build trees of chains with iptables. (Which would be quite a 
> fast thing if you do not have modules at hand.)

I thought about this too but I realized that building the tree in kernel 
would be easier to write than building it with a shell script :)

Mikulas