string match for iptables

PATCH Applied Pablo Neira 6 participants 14 messages Aug 20, 2005 – Aug 26, 2005

Subsystems (2)

Networking netfilter

lore

Share & tools

lore

Pablo Neira

author

2005-08-20 16:06 UTC #0 lore raw

PATCH 1/2 string match for iptables

Hi,

Here comes the iptables string match since the textsearch infrastructure went into 2.6.13. This adds to iptables the ability of looking for given patterns in packets. I'll be happy to see this stuff in Davem's 2.6.14 tree ;)

Signed-off-by Pablo Neira Ayuso <[email protected]>

--
Pablo

net/ipv4/netfilter/ipt_string.c new file +91 -0

Index: netfilter-2.6.14/net/ipv4/netfilter/ipt_string.c
===================================================================
@@ -0,0 +1,91 @@
+/* String matching match for iptables
+ * 
+ * (C) 2005 Pablo Neira Ayuso <[email protected]>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ */
+
+#include <linux/init.h>
+#include <linux/module.h>
+#include <linux/kernel.h>
+#include <linux/skbuff.h>
+#include <linux/netfilter_ipv4/ip_tables.h>
+#include <linux/netfilter_ipv4/ipt_string.h>
+#include <linux/textsearch.h>
+
+MODULE_AUTHOR("Pablo Neira Ayuso <[email protected]>");
+MODULE_DESCRIPTION("IP tables string match module");
+MODULE_LICENSE("GPL");
+
+static int match(const struct sk_buff *skb,
+		 const struct net_device *in,
+		 const struct net_device *out,
+		 const void *matchinfo,
+		 int offset,
+		 int *hotdrop)
+{
+	struct ts_state state;
+	struct ipt_string_info *conf = (struct ipt_string_info *) matchinfo;
+
+	memset(&state, 0, sizeof(struct ts_state));
+
+	return (skb_find_text((struct sk_buff *)skb, conf->from_offset, 
+			     conf->to_offset, conf->config, &state) 
+			     != UINT_MAX) && !conf->invert;
+}
+
+#define STRING_TEXT_PRIV(m) ((struct ipt_string_info *) m)
+
+static int checkentry(const char *tablename,
+		      const struct ipt_ip *ip,
+		      void *matchinfo,
+		      unsigned int matchsize,
+		      unsigned int hook_mask)
+{
+	struct ipt_string_info *conf = matchinfo;
+	struct ts_config *ts_conf;
+
+	if (matchsize != IPT_ALIGN(sizeof(struct ipt_string_info)))
+		return 0;
+
+	/* Damn, can't handle this case properly with iptables... */
+	if (conf->from_offset > conf->to_offset)
+		return 0;
+
+	ts_conf = textsearch_prepare(conf->algo, conf->pattern, conf->patlen,
+				     GFP_KERNEL, TS_AUTOLOAD);
+	if (IS_ERR(ts_conf))
+		return 0;
+
+	conf->config = ts_conf;
+
+	return 1;
+}
+
+static void destroy(void *matchinfo, unsigned int matchsize)
+{
+	textsearch_destroy(STRING_TEXT_PRIV(matchinfo)->config);
+}
+
+static struct ipt_match string_match = {
+	.name 		= "string",
+	.match 		= match,
+	.checkentry	= checkentry,
+	.destroy 	= destroy,
+	.me 		= THIS_MODULE
+};
+
+static int __init init(void)
+{
+	return ipt_register_match(&string_match);
+}
+
+static void __exit fini(void)
+{
+	ipt_unregister_match(&string_match);
+}
+
+module_init(init);
+module_exit(fini);

net/ipv4/netfilter/Makefile +1 -0

Index: netfilter-2.6.14/net/ipv4/netfilter/Makefile
===================================================================
@@ -65,6 +65,7 @@
 obj-$(CONFIG_IP_NF_MATCH_ADDRTYPE) += ipt_addrtype.o
 obj-$(CONFIG_IP_NF_MATCH_PHYSDEV) += ipt_physdev.o
 obj-$(CONFIG_IP_NF_MATCH_COMMENT) += ipt_comment.o
+obj-$(CONFIG_IP_NF_MATCH_STRING) += ipt_string.o
 
 # targets
 obj-$(CONFIG_IP_NF_TARGET_REJECT) += ipt_REJECT.o

net/ipv4/netfilter/Kconfig +12 -0

Index: netfilter-2.6.14/net/ipv4/netfilter/Kconfig
===================================================================
@@ -410,6 +410,18 @@
 	  destination IP' or `500pps from any given source IP'  with a single
 	  IPtables rule.
 
+config IP_NF_MATCH_STRING
+	tristate  'string match support'
+	depends on IP_NF_IPTABLES 
+	select TEXTSEARCH
+	select TEXTSEARCH_KMP
+	select TEXTSEARCH_FSM
+	help
+	  This option adds a `string' match, which allows you to look for
+	  pattern matchings in packets.
+
+	  To compile it as a module, choose M here.  If unsure, say N.
+
 # `filter', generic and specific targets
 config IP_NF_FILTER
 	tristate "Packet filtering"

include/linux/netfilter_ipv4/ipt_string.h new file +18 -0

Index: netfilter-2.6.14/include/linux/netfilter_ipv4/ipt_string.h
===================================================================
@@ -0,0 +1,18 @@
+#ifndef _IPT_STRING_H
+#define _IPT_STRING_H
+
+#define IPT_STRING_MAX_PATTERN_SIZE 128
+#define IPT_STRING_MAX_ALGO_NAME_SIZE 16
+
+struct ipt_string_info
+{
+	u_int16_t		from_offset;
+	u_int16_t		to_offset;
+	char			algo[IPT_STRING_MAX_ALGO_NAME_SIZE];
+	char			pattern[IPT_STRING_MAX_PATTERN_SIZE];
+	u_int8_t		patlen;
+	u_int8_t		invert;
+	struct ts_config	*config;
+};
+
+#endif /*_IPT_STRING_H*/

Patrick McHardy

2005-08-20 16:35 UTC #1 lore raw

Quoted 5 lines · Pablo Neira

Here comes the iptables string match since the textsearch infrastructure went into 2.6.13. This adds to iptables the ability of looking for given patterns in packets. I'll be happy to see this stuff in Davem's 2.6.14 tree ;)

include/linux/netfilter_ipv4/ipt_string.h line 16

Quoted 10 lines

include/linux/netfilter_ipv4/ipt_string.h new file +10 -0

+struct ipt_string_info
+{
+	u_int16_t		from_offset;
+	u_int16_t		to_offset;
+	char			algo[IPT_STRING_MAX_ALGO_NAME_SIZE];
+	char			pattern[IPT_STRING_MAX_PATTERN_SIZE];
+	u_int8_t		patlen;
+	u_int8_t		invert;
+	struct ts_config	*config;
+};

Embedding a pointer in the struct causes different alignment depending on the wordsize and doesn't work in mixed 64/32 bit environments. Please use __attribute__((aligned(8))) to prevent this.

Otherwise, it looks good.

David S. Miller

maintainer

2005-08-20 20:14 UTC #2 lore raw

From: Patrick McHardy <[email protected]>
Subject: Re: [PATCH 1/2] string match for iptables
Date: Sat, 20 Aug 2005 18:35:54 +0200

Quoted 6 lines

Quoted 4 lines · Pablo Neira
Here comes the iptables string match since the textsearch infrastructure went into 2.6.13. This adds to iptables the ability of looking for given patterns in packets. I'll be happy to see this stuff in Davem's 2.6.14 tree ;)

Quoted 14 lines

include/linux/netfilter_ipv4/ipt_string.h line 16
Quoted 10 lines
include/linux/netfilter_ipv4/ipt_string.h new file +10 -0
+struct ipt_string_info
+{
+	u_int16_t		from_offset;
+	u_int16_t		to_offset;
+	char			algo[IPT_STRING_MAX_ALGO_NAME_SIZE];
+	char			pattern[IPT_STRING_MAX_PATTERN_SIZE];
+	u_int8_t		patlen;
+	u_int8_t		invert;
+	struct ts_config	*config;
+};
Embedding a pointer in the struct causes different alignment depending on the wordsize and doesn't work in mixed 64/32 bit environments. Please use __attribute__((aligned(8))) to prevent this.

Our ability to translate netfilter structures in compat mode is primitive, at best, and I think we really should try to do something about this soon.

This IP tables modules can provide a bit of help, with some kind of descriptor, or set of methods the compat layer can call into for help (or a flag saying, "no translation necessary").

One thing about the implementation is that it is apparent that people often load an _enormous_ amount of rules. A large enough set that kmalloc() can't get enough space for the entire rule set. I've seen a report about this recently on sparc64, where someone tries to load enough ipt_replace rules that the kmalloc() done by the compat mode translation stuff was too large.

One thing that can help is to not put pointers into these rules, that is actually the most difficult case to handle. Without pointers, the entire struct can be defined using portable types that require no translation. Once you introduce a pointer, using the user's struct as-is becomes impossible. (as an added bonus such rules could thus be sent over the wire as well, if we ever wanted to do that)

In this case, we could put a zero length array at the end. But I realize that with iptables rules this may be difficult due to some restriction I am not aware of.

Patrick McHardy

2005-08-21 13:55 UTC #3 lore raw

Quoted 3 lines · David S. Miller

Our ability to translate netfilter structures in compat mode is primitive, at best, and I think we really should try to do something about this soon.

The compat code looks broken, it assumes struct ipt_entry is equal in both environments, which is not true, at least not on my AMD64. But we have a couple of spots in userspace were 32bit iptables on 64bit kernel is explicitly handled (libipt_MARK, libipt_CONNMARK, ...), so it does seem to work on some machines.

Anyway, I already started working on this after Andi claimed it was unfixable, but so far I can only dump the ruleset, insertion doesn't work yet.

Quoted 3 lines

This IP tables modules can provide a bit of help, with some kind of descriptor, or set of methods the compat layer can call into for help (or a flag saying, "no translation necessary").

At the moment we have two modules that need translation, CLUSTERIP and hashlimit. Thanks to versioning we can just fix them in a new structure.

Quoted 6 lines

One thing about the implementation is that it is apparent that people often load an _enormous_ amount of rules. A large enough set that kmalloc() can't get enough space for the entire rule set. I've seen a report about this recently on sparc64, where someone tries to load enough ipt_replace rules that the kmalloc() done by the compat mode translation stuff was too large.

Where does it call kmalloc? net/compat.c uses compat_alloc_user_space for the translated ruleset.

Quoted 11 lines

One thing that can help is to not put pointers into these rules, that is actually the most difficult case to handle. Without pointers, the entire struct can be defined using portable types that require no translation. Once you introduce a pointer, using the user's struct as-is becomes impossible. (as an added bonus such rules could thus be sent over the wire as well, if we ever wanted to do that)
In this case, we could put a zero length array at the end. But I realize that with iptables rules this may be difficult due to some restriction I am not aware of.

The entire ruleset is one big blob so dynamically sizing structures doesn't work. There's also no room to put a pointer somewhere outside of the match/target structures where they could keep instantiated private data. I think there is no way to avoid this until we get rid of the one-big-blob thing.

David S. Miller

maintainer

2005-08-21 22:34 UTC #4 lore raw

From: Patrick McHardy <[email protected]>
Date: Sun, 21 Aug 2005 15:55:22 +0200

Quoted 10 lines

Quoted 6 lines · David S. Miller
One thing about the implementation is that it is apparent that people often load an _enormous_ amount of rules. A large enough set that kmalloc() can't get enough space for the entire rule set. I've seen a report about this recently on sparc64, where someone tries to load enough ipt_replace rules that the kmalloc() done by the compat mode translation stuff was too large.
Where does it call kmalloc? net/compat.c uses compat_alloc_user_space for the translated ruleset.

Sorry, that's the 2.4.x code, perhaps it should be converted to use either vmalloc() of compat_alloc_user_space().

Patrick McHardy

2005-08-22 00:13 UTC #5 lore raw

Quoted 8 lines · David S. Miller

From: Patrick McHardy <[email protected]>
Date: Sun, 21 Aug 2005 15:55:22 +0200
Quoted 2 lines
Where does it call kmalloc? net/compat.c uses compat_alloc_user_space for the translated ruleset.
Sorry, that's the 2.4.x code, perhaps it should be converted to use either vmalloc() of compat_alloc_user_space().

I'll look into it after fixing the 2.6 compat code.

David S. Miller

maintainer

2005-08-22 02:14 UTC #6 lore raw

From: Patrick McHardy <[email protected]>
Date: Mon, 22 Aug 2005 02:13:59 +0200

Quoted 5 lines

Quoted 2 lines · David S. Miller
Sorry, that's the 2.4.x code, perhaps it should be converted to use either vmalloc() of compat_alloc_user_space().
I'll look into it after fixing the 2.6 compat code.

Thanks a lot Patrick.

Harald Welte

2005-08-25 10:42 UTC #7 lore raw

In reply to David S. Miller

Sorry for the late reply, I just returned from holidays.

Quoted 3 lines · David S. Miller

Our ability to translate netfilter structures in compat mode is primitive, at best, and I think we really should try to do something about this soon.

mh. I always dreamed of pkttables happening earlier so we don't have to deal with this...

Quoted 7 lines

This IP tables modules can provide a bit of help, with some kind of descriptor, or set of methods the compat layer can call into for help (or a flag saying, "no translation necessary").
One thing about the implementation is that it is apparent that people often load an _enormous_ amount of rules. A large enough set that kmalloc() can't get enough space for the entire rule set.

This tends to happen on smp 2.4.x systems, since they use NR_CPUS times the ruleset size. On (at least somewhat recent) 2.6.x, we use num_possible_cpus() to reduce the bloatage.

Quoted 3 lines

I've seen a report about this recently on sparc64, where someone tries to load enough ipt_replace rules that the kmalloc() done by the compat mode translation stuff was too large.

was this 2.4.x or 2.6.x ? and was it smp or not?

if it was 2.6.x and smp, we could introduce an option that would use only one ruleset even on multiple cpus. it will produce counter cacheline ping-pong but reduce the memory usage significantly.

Quoted 7 lines

One thing that can help is to not put pointers into these rules, that is actually the most difficult case to handle. Without pointers, the entire struct can be defined using portable types that require no translation. Once you introduce a pointer, using the user's struct as-is becomes impossible. (as an added bonus such rules could thus be sent over the wire as well, if we ever wanted to do that)

The only reason why a pointer is needed at all, is the "dump whole table to userspace, do some modifications and read it back" approach. I seriously doubt that we would be able to change that assumption. If we did, it wouldn't be iptables anymore, but half-way into pkttables.

As an intermediate solution we could do some form of indirect resolval/mapping. The core could provide an allocation wrapper API which matches/targets could use for malloc'ing their private data structures. In addition to a pointer, it would return an (32bit) ID. That ID can then be embedded in kernel/userspace data structures. When userspace rules come in, the ID gets translated to the real pointer by some call to that API of the core.

Signature · 5 lines

- Harald Welte <[email protected]>                 http://netfilter.org/
============================================================================
  "Fragmentation is like classful addressing -- an interesting early
   architectural error that shows how much experimentation was going
   on while IP was being designed."                    -- Paul Vixie

Martin Josefsson

2005-08-25 16:54 UTC #8 lore raw

Quoted 13 lines · Harald Welte

Quoted 7 lines
One thing that can help is to not put pointers into these rules, that is actually the most difficult case to handle. Without pointers, the entire struct can be defined using portable types that require no translation. Once you introduce a pointer, using the user's struct as-is becomes impossible. (as an added bonus such rules could thus be sent over the wire as well, if we ever wanted to do that)
The only reason why a pointer is needed at all, is the "dump whole table to userspace, do some modifications and read it back" approach. I seriously doubt that we would be able to change that assumption. If we did, it wouldn't be iptables anymore, but half-way into pkttables.

Quoted 7 lines

As an intermediate solution we could do some form of indirect resolval/mapping. The core could provide an allocation wrapper API which matches/targets could use for malloc'ing their private data structures. In addition to a pointer, it would return an (32bit) ID. That ID can then be embedded in kernel/userspace data structures. When userspace rules come in, the ID gets translated to the real pointer by some call to that API of the core.

Now that we have support for diffrent revisions of matches/targets we can easily add new revisions that uses diffrent structs and later deprecate the older revisions.

Matches and targets have two sizes defined for their datastructures, size and userspacesize. size is the total size of the datastructure, the amount that is allocated for the rule private data. And userspacesize is the amount transferred to/from userspace when rules are modified.

So we could put all portable members at the top of the structure and all pointers at the end and set userspacesize to the offset of the first pointer in the structure. There's no need to transfer that data back and forth to userspace, it just introduces races in the cases where there's members used for refcounting in the structure.
So the remaining problem is that the total size of the structure is diffrent on 32/64 bit.
The userspacesize stays the same on both but not the part of the structure that holds the "kernelprivate data", iow the last part of the structure, that changes on 32/64bit and I don't think we can assume that the size on 64bit is 2 * size on 32bit, that only holds for non portable types, what if someone wants a portable size in this section...

Any ideas?

Signature · 1 line

/Martin

Martin Josefsson

2005-08-25 17:19 UTC #9 lore raw

On Thu, 2005-08-25 at 18:54 +0200, Martin Josefsson wrote:

I wonder why davem got lost on the CC, he's there in my Sent folder but not in the mail I got from netfilter-devel... I hope he makes it this time.

Quoted 47 lines · Harald Welte

Quoted 14 lines
Quoted 8 lines
One thing that can help is to not put pointers into these rules, that is actually the most difficult case to handle. Without pointers, the entire struct can be defined using portable types that require no translation. Once you introduce a pointer, using the user's struct as-is becomes impossible. (as an added bonus such rules could thus be sent over the wire as well, if we ever wanted to do that)
The only reason why a pointer is needed at all, is the "dump whole table to userspace, do some modifications and read it back" approach. I seriously doubt that we would be able to change that assumption. If we did, it wouldn't be iptables anymore, but half-way into pkttables.
Quoted 7 lines
As an intermediate solution we could do some form of indirect resolval/mapping. The core could provide an allocation wrapper API which matches/targets could use for malloc'ing their private data structures. In addition to a pointer, it would return an (32bit) ID. That ID can then be embedded in kernel/userspace data structures. When userspace rules come in, the ID gets translated to the real pointer by some call to that API of the core.
Now that we have support for diffrent revisions of matches/targets we can easily add new revisions that uses diffrent structs and later deprecate the older revisions.
Matches and targets have two sizes defined for their datastructures, size and userspacesize. size is the total size of the datastructure, the amount that is allocated for the rule private data. And userspacesize is the amount transferred to/from userspace when rules are modified.
So we could put all portable members at the top of the structure and all pointers at the end and set userspacesize to the offset of the first pointer in the structure. There's no need to transfer that data back and forth to userspace, it just introduces races in the cases where there's members used for refcounting in the structure.
So the remaining problem is that the total size of the structure is diffrent on 32/64 bit.
The userspacesize stays the same on both but not the part of the structure that holds the "kernelprivate data", iow the last part of the structure, that changes on 32/64bit and I don't think we can assume that the size on 64bit is 2 * size on 32bit, that only holds for non portable types, what if someone wants a portable size in this section...
Any ideas?

Signature · 1 line

/Martin

Patrick McHardy

2005-08-26 12:00 UTC #10 lore raw

Quoted 5 lines · Martin Josefsson

On Thu, 2005-08-25 at 18:54 +0200, Martin Josefsson wrote:
I wonder why davem got lost on the CC, he's there in my Sent folder but not in the mail I got from netfilter-devel... I hope he makes it this time.

Yes, I noticed this multiple times, mails to the list seem to remove Dave automatically. Perhaps this has something to do with the "may sent to list even if not subscribed" setting that was made when he wasn't subscribed to the list.

Harald Welte

2005-08-26 13:27 UTC #11 lore raw

DaveM get's removed from Cc (was Re: [PATCH 1/2] string match for iptables)

Quoted 11 lines · Patrick McHardy

Quoted 5 lines · Martin Josefsson
On Thu, 2005-08-25 at 18:54 +0200, Martin Josefsson wrote:
I wonder why davem got lost on the CC, he's there in my Sent folder but not in the mail I got from netfilter-devel... I hope he makes it this time.
Yes, I noticed this multiple times, mails to the list seem to remove Dave automatically. Perhaps this has something to do with the "may sent to list even if not subscribed" setting that was made when he wasn't subscribed to the list.

it's a per-user configuration setting of mailman called "nodupes".

If X subscribes to a mailinglist L and sets "nodupes", and Z sends a message to L with Cc: X, then X will be removed.

DaveM had his netfilter-devel subscription set to "nodupes". I assume that was a mistake and have disabled that switch via the admin interface.

Signature · 5 lines

- Harald Welte <[email protected]>                 http://netfilter.org/
============================================================================
  "Fragmentation is like classful addressing -- an interesting early
   architectural error that shows how much experimentation was going
   on while IP was being designed."                    -- Paul Vixie

Phil Oester

2005-08-26 15:21 UTC #12 lore raw

Re: DaveM get's removed from Cc (was Re: [PATCH 1/2] string match for iptables)

Quoted 4 lines · Harald Welte

it's a per-user configuration setting of mailman called "nodupes".
If X subscribes to a mailinglist L and sets "nodupes", and Z sends a message to L with Cc: X, then X will be removed.

FWIW, most other lists seem to default to 'dupes', but netfilter-devel defaults to nodupes. Perhaps the default should be flipped?

Phil

Harald Welte

2005-08-26 18:33 UTC #13 lore raw

Re: DaveM get's removed from Cc (was Re: [PATCH 1/2] string match for iptables)

Quoted 8 lines · Phil Oester

Quoted 4 lines · Harald Welte
it's a per-user configuration setting of mailman called "nodupes".
If X subscribes to a mailinglist L and sets "nodupes", and Z sends a message to L with Cc: X, then X will be removed.
FWIW, most other lists seem to default to 'dupes', but netfilter-devel defaults to nodupes. Perhaps the default should be flipped?

Thanks, changed the default for new members accordingly.

Signature · 5 lines

- Harald Welte <[email protected]>                 http://netfilter.org/
============================================================================
  "Fragmentation is like classful addressing -- an interesting early
   architectural error that shows how much experimentation was going
   on while IP was being designed."                    -- Paul Vixie