Skip to contentSkip to conversation

string matching ematch

RFC In review Thomas Graf 4 participants 9 messages Jan 26, 2005 – Feb 1, 2005

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

RFC 1/1 string matching ematch

I'd like to discuss the string matching ematch, I don't care about the algorithm used but rather whether to make it stateful, match over fragments, etc. I attached a simple stateless string matching ematch using the Knuth-Morris-Pratt algorithm as a starting point.

KMP ::= pattern [ BEGIN ] [ END ]
BEGIN ::= from OFFSET [ layer LAYER ]
END ::= to OFFSET [ layer LAYER ]

where:
default value for BEGIN: skb->h.raw
default value for END: skb->tail

The prefix table used by the KMP algorithm is calculated in userspace.

The layering schema used is the one I introduced in the ematch patchset which is likely to be extended by another layer dynamically calculated from the packet payload.

The limitation is pretty obvious, it relies on linear skbs and is not quite limited in matching the payload of a stream based protocol.

Making it aware of non-linear skbs isn't that hard, the matcher gets a bit more complicated but shouldn't slow down too much so this is probably worth doing.

Making it aware of a state gets much more complicated and if we don't queue packets we can only classify on the packet holding the last part of the pattern. So we need to either tell the underlying qdisc to hold the packet for some time or accept this limitation. The state of the matcher could be stored in the conntrack entry so the match can be resumed when the relevent packet arrives. We're moving more and more towards netfilter and application level filtering and I think this should be covered by netfilter itself. If we do this, we should at least share the code with netfilter.

Thoughts?

include/linux/pkt_cls.h +1 -0
diff -Nru linux-2.6.11-rc2-bk3.orig/include/linux/pkt_cls.h linux-2.6.11-rc2-bk3/include/linux/pkt_cls.h
@@ -401,6 +401,7 @@
 	TCF_EM_NBYTE,
 	TCF_EM_U32,
 	TCF_EM_META,
+	TCF_EM_KMP,
 	__TCF_EM_MAX
 };
 
include/linux/tc_ematch/tc_em_kmp.h +24 -0
diff -Nru linux-2.6.11-rc2-bk3.orig/include/linux/tc_ematch/tc_em_kmp.h linux-2.6.11-rc2-bk3/include/linux/tc_ematch/tc_em_kmp.h
@@ -0,0 +1,24 @@
+#ifndef __LINUX_TC_EM_KMP_H
+#define __LINUX_TC_EM_KMP_H
+
+#include <linux/pkt_cls.h>
+
+enum
+{
+	TCA_EM_KMP_UNSPEC,
+	TCA_EM_KMP_FROM,	/* struct tcf_kmp_offset */
+	TCA_EM_KMP_TO,		/* struct tcf_kmp_offset */
+	TCA_EM_KMP_LENGTH,	/* u32 */
+	TCA_EM_KMP_PATTERN,	/* unsigned char[] */
+	TCA_EM_KMP_PREFIX_TBL,	/* u32[] */
+	__TCA_EM_KMP_MAX
+};
+#define TCA_EM_KMP_MAX (__TCA_EM_KMP_MAX - 1)
+
+struct tcf_kmp_offset
+{
+	__u16		off;
+	__u16		layer;
+};
+
+#endif
net/sched/Kconfig +10 -0
diff -Nru linux-2.6.11-rc2-bk3.orig/net/sched/Kconfig linux-2.6.11-rc2-bk3/net/sched/Kconfig
@@ -449,6 +449,16 @@
 	  To compile this code as a module, choose M here: the
 	  module will be called em_meta.
 
+config NET_EMATCH_KMP
+	tristate "Knuth-Morris-Pratt string matching"
+	depends on NET_EMATCH
+	---help---
+	  Say Y here if you want to be able to classify packets by
+	  matching strings using the KMP string matching algorithm.
+	  
+	  To compile this code as a module, choose M here: the
+	  module will be called em_kmp.
+
 config NET_CLS_ACT
 	bool "Packet ACTION"
 	depends on EXPERIMENTAL && NET_CLS && NET_QOS
net/sched/Makefile +1 -0
diff -Nru linux-2.6.11-rc2-bk3.orig/net/sched/Makefile linux-2.6.11-rc2-bk3/net/sched/Makefile
@@ -39,3 +39,4 @@
 obj-$(CONFIG_NET_EMATCH_NBYTE)	+= em_nbyte.o
 obj-$(CONFIG_NET_EMATCH_U32)	+= em_u32.o
 obj-$(CONFIG_NET_EMATCH_META)	+= em_meta.o
+obj-$(CONFIG_NET_EMATCH_KMP)	+= em_kmp.o
net/sched/em_kmp.c +175 -0

175 lines not on this page · raw message

maintainer
#1 lore raw
Quoted 3 lines · On Wed, 26 Jan 2005 16:07:14 +0100 Thomas Graf <[email protected]> wrote:

I'd like to discuss the string matching ematch, I don't care about the algorithm used but rather whether to make it stateful, match over fragments, etc.

I think you'll need to make it stateful.

I assume this is meant to be used for things like catching references to "Falun Gong" in SMTP sessions and stuff like that. Not that I know any entity interested in such applications :-)

Anyways, if the string goes across the TCP data portion of multiple packets, statefulness becomes necessary to catch it. Right?

#2 lore raw

* David S. Miller <[email protected]> 2005-01-26 13:03

Quoted 7 lines
Quoted 3 lines · On Wed, 26 Jan 2005 16:07:14 +0100 Thomas Graf <[email protected]> wrote:

I'd like to discuss the string matching ematch, I don't care about the algorithm used but rather whether to make it stateful, match over fragments, etc.

Quoted 5 lines

I think you'll need to make it stateful.

I assume this is meant to be used for things like catching references to "Falun Gong" in SMTP sessions and stuff like that. Not that I know any entity interested in such applications :-)

Hehe, it's main purpose is to catch mail from your sweetie and redirect them through a low latency link but of course you can also use it to match on text based protocols without strict header ordering. ;->

Quoted 2 lines

Anyways, if the string goes across the TCP data portion of multiple packets, statefulness becomes necessary to catch it. Right?

Yes and no, it is of course necessary if one wants to match any string at any position without limitation. OTOH, it gets quite complex. We'd have to store the state of every configured kmp ematch to just be able to tell the result. On top of that, the whole classification process is stateless and should be kept like this. Assuming one configures three ematches like this:

u32(ip dport 333 0xff)
and (
kmp("Falun Gong" from 20 layer transport)
and nbyte("SMTP" at 0 layer application)
)

assuming the u32 and nbyte ematch matches in the first packet, the string matches only partially. We can't regard regard the ematch tree as matched so we must return false. The next packet in the flow completes the string but the nbyte match doesn't match anymore so no match either. In fact a stateless filter can't do any better but it doesn't consume as much resources.

There are cases where a statefull string matching would be of use, one of them is when it doesn't matter which packet you actually classify, e.g. dropping connections such as to protect your web server from stilly requests.

I'm not sure if mixing stateful with stateless stuff is such of a good idea. I think it should be separated and have stateful filters only be executed when the flow matters, not packets.

maintainer
#3 lore raw
Quoted 3 lines · On Wed, 26 Jan 2005 22:41:19 +0100 Thomas Graf <[email protected]> wrote:

I'm not sure if mixing stateful with stateless stuff is such of a good idea. I think it should be separated and have stateful filters only be executed when the flow matters, not packets.

I think keeping things totally stateless would be the best idea.

#4 lore raw

* David S. Miller <[email protected]> 2005-01-26 15:26

Quoted 9 lines
Quoted 3 lines · On Wed, 26 Jan 2005 22:41:19 +0100 Thomas Graf <[email protected]> wrote:

I'm not sure if mixing stateful with stateless stuff is such of a good idea. I think it should be separated and have stateful filters only be executed when the flow matters, not packets.

I think keeping things totally stateless would be the best idea.

Yes, I think so too.

I'm still thinking about pskbs in the background and the problem gets more serious with this. So far, even with the multi byte ematch, all filters were focusing on header content even if they were able to read from any offset.

Our goal must of course be to to avoid lineraization for as many cases as possible, therefore I think it would be worth making all matchers aware of pskbs without linearization. In case the packet goes though the pedit or ipt action later on then we definitely need to take further actions but these should be special cases.

For the string matching it is fairly easy, we can check for partial matches at the end and begin of every fragment. The multi byte ematch could be splitted into two paths, a fast path using memcmp directly on the skb data for linear skbs and a "slow" path for non-linear skbs fetching the needed byte sequence from the relevant fragments first. The cmp ematch and u32 ematch and classifier could fetch the needed bucket via a function tcf_read_at_offset taking an offset and the length of the bucket {8|16|32} which iterates over the fragments as needed. I know, for most cases it is not needed but it shouldn't cost us too much.

Thoughts?

#5 lore raw
In reply to Thomas Graf

Hi Thomas,

Quoted 6 lines · Thomas Graf

I'd like to discuss the string matching ematch, I don't care about the algorithm used but rather whether to make it stateful, match over fragments, etc. I attached a simple stateless string matching ematch using the Knuth-Morris-Pratt algorithm as a starting point.

I've posted something similar after christmas in netfilter-devel[1]. It's fragment aware, actually my implementation uses boyer-moore to look for matches in the payload, and it uses brute force together with Rusty's skb_iter stuff to look for matches on the edges. The worst case is not that bad for small patterns. Anyway I'm still looking for alternatives solutions. BTW, Harald Welte is also interested in this stuff.

I'll give it more spins these days since I've got some spare time. I'll also have a look at your work. I think that we could join efforts and push something good, thoughts?

References:

https://lists.netfilter.org/pipermail/netfilter-devel/2005-January/018034.html

--
Pablo

#6 lore raw

* Pablo Neira <[email protected]> 2005-01-27 21:17

Quoted 8 lines
Quoted 5 lines · Thomas Graf

I'd like to discuss the string matching ematch, I don't care about the algorithm used but rather whether to make it stateful, match over fragments, etc. I attached a simple stateless string matching ematch using the Knuth-Morris-Pratt algorithm as a starting point.

Quoted 4 lines

I've posted something similar after christmas in netfilter-devel[1]. It's fragment aware, actually my implementation uses boyer-moore to look for matches in the payload, and it uses brute force together with Rusty's skb_iter stuff to look for matches on the edges.

I've seen it but sticked to KMP because it uses less memory. Their searching phase time complexity is nearly equal around O(nm) for n being the length of T[] and m being the length of P[]. BM definitely has a better performance for highly periodic P[]'s in a periodic T[] though.

I'm missing a few things in your string matching API, namely the ability to define a upper limit of the searching range which can give much better performance gains than the best optimization can do. A naive searching method around the borders of fragments is definiltey easier but even there you could benefit from ruling out invalid shifts.

Quoted 1 line

The worst case is not that bad for small patterns.

I don't think that any of the algorithms really make a difference, theoretically yes but what we're basically should be looking for is one with good average performance by detecting unnecessary shifts. Our T[] is limited by the skb as long as we're not going into statefull searches and thus other resources matter more to me than a few more cycles.

Quoted 3 lines

I'll give it more spins these days since I've got some spare time. I'll also have a look at your work. I think that we could join efforts and push something good, thoughts?

Definitely, being able to specify the upper limit is a must for me though. Another difference is that I compute the prefix table in userspace.

#7 lore raw

Reading email backward ..

I think we should allow for all sorts of algrithms KMP, Boyer-Moore etc to be plugged in (in tc this is already there).
The stuff that Harald was looking at (at least around July when i last talked to him on this) is an infrastructure level thing. Its derived from someone who seems to have well thought of the callbacks etc for a good stateful solution. I cant remember the person from whom Harald was deriving his stuff (email was somewhere in .fr) - but it did seem pretty sensible. If we can have infrastructure that is also usable by tc, that would be great so we dont go cutnpasting unnecessarily.

Having said all that:
Thomas, I think you should leave what you have as totaly stateless unless we dont have a shareable solution. I have tons of ideas i could share when we get to that level.

cheers,
jamal

Quoted 45 lines · Thomas Graf

* Pablo Neira <[email protected]> 2005-01-27 21:17

Quoted 8 lines
Quoted 5 lines · Thomas Graf

I'd like to discuss the string matching ematch, I don't care about the algorithm used but rather whether to make it stateful, match over fragments, etc. I attached a simple stateless string matching ematch using the Knuth-Morris-Pratt algorithm as a starting point.

Quoted 4 lines

I've posted something similar after christmas in netfilter-devel[1]. It's fragment aware, actually my implementation uses boyer-moore to look for matches in the payload, and it uses brute force together with Rusty's skb_iter stuff to look for matches on the edges.

I've seen it but sticked to KMP because it uses less memory. Their searching phase time complexity is nearly equal around O(nm) for n being the length of T[] and m being the length of P[]. BM definitely has a better performance for highly periodic P[]'s in a periodic T[] though.

I'm missing a few things in your string matching API, namely the ability to define a upper limit of the searching range which can give much better performance gains than the best optimization can do. A naive searching method around the borders of fragments is definiltey easier but even there you could benefit from ruling out invalid shifts.

Quoted 1 line

The worst case is not that bad for small patterns.

I don't think that any of the algorithms really make a difference, theoretically yes but what we're basically should be looking for is one with good average performance by detecting unnecessary shifts. Our T[] is limited by the skb as long as we're not going into statefull searches and thus other resources matter more to me than a few more cycles.

Quoted 3 lines

I'll give it more spins these days since I've got some spare time. I'll also have a look at your work. I think that we could join efforts and push something good, thoughts?

Definitely, being able to specify the upper limit is a must for me though. Another difference is that I compute the prefix table in userspace.

#8 lore raw

Hi jamal,

Harald, I've cc'ed you since I think that this could be interesting.

Quoted 9 lines · jamal

I think we should allow for all sorts of algrithms KMP, Boyer-Moore etc to be plugged in (in tc this is already there).
The stuff that Harald was looking at (at least around July when i last talked to him on this) is an infrastructure level thing. Its derived from someone who seems to have well thought of the callbacks etc for a good stateful solution. I cant remember the person from whom Harald was deriving his stuff (email was somewhere in .fr) - but it did seem pretty sensible.

yes, Phil Biondi's libqsearch. I started working with it but then I thought that it was a bit bloated because I didn't see the point of using several algorithms since boyer-moore is the best AFAIK. But Thomas thoughts about memory usage made me see that maybe this doesn't fit well all possible scenarios. So I've changed my mind and I think that such infrastructure level thing is required.

Harald told me that he's going to finish soon his hacks based on libqsearch, then we could merge ideas based in that thing I've posted after christmas and his libqsearch mutant.

Quoted 4 lines

If we can have infrastructure that is also usable by tc, that would be great so we dont go cutnpasting unnecessarily.

definitely.

Quoted 6 lines

Having said all that:
Thomas, I think you should leave what you have as totaly stateless unless we dont have a shareable solution. I have tons of ideas i could share when we get to that level.

I've got also some ideas, let's see if I can get settled one of them at least after the infrastructure have been cooked :).

--
Pablo