Hi all, Here is a new string match. New kernel code, and updated userspace code.
Changes: o no more dependance on max() macro! (so works for 2.4.9 now) o skip/shift tables are now stored in matchinfo, making for tidier code and removing the need to generate skip/shift tables all the time. o due to above change it should now be AT LEAST 100 times faster o memcmp() matching removed alltogether o fix iptables-save quotation bug I am now working on a patch to the userspace libraries to allow snort-style binary data to be in the string eg: --string "|ef ff ff ff|/bin/sh" I have been testing this code extensively both in userspace and inside netfilter for a while now so it should be stable as a table. -- // Gianni Tedesco <[EMAIL PROTECTED]> 8646BE7D: 870E A2C9 8F60 3A3C 91B5 7669 8646 BE7D
diff -urN netfilter.orig/userspace/extensions/libipt_string.c netfilter/userspace/extensions/libipt_string.c
--- netfilter.orig/userspace/extensions/libipt_string.c Thu Mar 14 11:35:58 2002
+++ netfilter/userspace/extensions/libipt_string.c Wed May 29 11:58:17 2002
@@ -22,11 +22,9 @@
help(void)
{
printf(
-"STRING match v%s options:\n"
-"--string [!] string Match a string in a packet\n",
-NETFILTER_VERSION);
-
- fputc('\n', stdout);
+ "STRING match v%s options:\n"
+ "--string [!] string Match a string in a packet\n\n",
+ NETFILTER_VERSION);
}
static struct option opts[] = {
@@ -35,23 +33,70 @@
};
/* Initialize the match. */
-static void
-init(struct ipt_entry_match *m, unsigned int *nfcache)
+static void init(struct ipt_entry_match *m, unsigned int *nfcache)
{
*nfcache |= NFC_UNKNOWN;
}
-static void
-parse_string(const unsigned char *s, struct ipt_string_info *info)
+/* Content matcher (generic string matching) */
+void bm_skip(char *x, int m, int *skip)
+{
+ int i;
+
+ for (i = 0; i < 256; ++i)
+ skip[i] = m+1;
+
+ while(m)
+ skip[(unsigned char)*x++]=m--;
+}
+
+void bm_shift(char *ptrn, int plen, int *shift)
+{
+ int *sptr=shift+plen-1;
+ char *pptr=ptrn+plen-1;
+ char c;
+
+ c=ptrn[plen-1];
+ *sptr=1;
+
+ while(sptr-- != shift) {
+ char *p1=ptrn+plen-2, *p2, *p3;
+
+ do {
+ while(p1>=ptrn && *p1-- !=c );
+
+ p2=ptrn+plen-2;
+ p3=p1;
+
+ while(p3>=ptrn &&
+ *p3-- == *p2-- &&
+ p2 >= pptr);
+ }
+
+ while(p3>=ptrn &&
+ *p3-- == *p2-- &&
+ p2 >= pptr);
+
+ *sptr=shift+plen-sptr+p2-p3;
+
+ pptr--;
+ }
+}
+
+static void parse_string(const unsigned char *s, struct ipt_string_info *info)
{
- if (strlen(s) <= BM_MAX_NLEN) strcpy(info->string, s);
- else exit_error(PARAMETER_PROBLEM, "STRING too long `%s'", s);
+ if ( (info->len=strlen(s)) >= BM_MAX_NLEN)
+ exit_error(PARAMETER_PROBLEM, "STRING too long `%s'", s);
+
+ /* Copy the string and setup the skip/shift tables */
+ strcpy(info->string, s);
+ bm_shift(info->string, info->len, info->shift);
+ bm_skip(info->string, info->len, info->skip);
}
/* Function which parses command options; returns true if it
ate an option */
-static int
-parse(int c, char **argv, int invert, unsigned int *flags,
+static int parse(int c, char **argv, int invert, unsigned int *flags,
const struct ipt_entry *entry,
unsigned int *nfcache,
struct ipt_entry_match **match)
@@ -62,9 +107,7 @@
case '1':
check_inverse(optarg, &invert, &optind, 0);
parse_string(argv[optind-1], stringinfo);
- if (invert)
- stringinfo->invert = 1;
- stringinfo->len=strlen((char *)&stringinfo->string);
+ stringinfo->invert = (invert==0) ? 0 : 1;
*flags = 1;
break;
@@ -74,27 +117,20 @@
return 1;
}
-static void
-print_string(char string[], int invert, int numeric)
+static void print_string(char string[], int invert, int numeric)
{
- if (invert)
- fputc('!', stdout);
- printf("%s ",string);
+ if (invert) fputc('!', stdout);
+ printf("\"%s\" ",string);
}
-/* Final check; must have specified --string. */
-static void
-final_check(unsigned int flags)
+/* Final check */
+static void final_check(unsigned int flags)
{
- if (!flags)
- exit_error(PARAMETER_PROBLEM,
- "STRING match: You must specify `--string'");
}
/* Prints out the matchinfo. */
-static void
-print(const struct ipt_ip *ip,
+static void print(const struct ipt_ip *ip,
const struct ipt_entry_match *match,
int numeric)
{
@@ -104,28 +140,26 @@
}
/* Saves the union ipt_matchinfo in parsable form to stdout. */
-static void
-save(const struct ipt_ip *ip, const struct ipt_entry_match *match)
+static void save(const struct ipt_ip *ip, const struct ipt_entry_match *match)
{
printf("--string ");
print_string(((struct ipt_string_info *)match->data)->string,
((struct ipt_string_info *)match->data)->invert, 0);
}
-static
-struct iptables_match string
-= { NULL,
- "string",
- NETFILTER_VERSION,
- IPT_ALIGN(sizeof(struct ipt_string_info)),
- IPT_ALIGN(sizeof(struct ipt_string_info)),
- &help,
- &init,
- &parse,
- &final_check,
- &print,
- &save,
- opts
+static struct iptables_match string= {
+ NULL,
+ "string",
+ NETFILTER_VERSION,
+ IPT_ALIGN(sizeof(struct ipt_string_info)),
+ IPT_ALIGN(sizeof(struct ipt_string_info)),
+ &help,
+ &init,
+ &parse,
+ &final_check,
+ &print,
+ &save,
+ opts
};
void _init(void)
diff -urN netfilter.orig/userspace/patch-o-matic/extra/string.patch netfilter/userspace/patch-o-matic/extra/string.patch
--- netfilter.orig/userspace/patch-o-matic/extra/string.patch Tue Mar 19 07:54:57 2002
+++ netfilter/userspace/patch-o-matic/extra/string.patch Wed May 29 11:57:54 2002
@@ -1,37 +1,17 @@
-diff -urN linux.orig/include/linux/netfilter_ipv4/ipt_string.h linux/include/linux/netfilter_ipv4/ipt_string.h
---- linux.orig/include/linux/netfilter_ipv4/ipt_string.h Thu Jan 1 01:00:00 1970
-+++ linux/include/linux/netfilter_ipv4/ipt_string.h Thu Feb 21 20:26:23 2002
-@@ -0,0 +1,21 @@
-+#ifndef _IPT_STRING_H
-+#define _IPT_STRING_H
-+
-+/* *** PERFORMANCE TWEAK ***
-+ * Packet size and search string threshold,
-+ * above which sublinear searches is used. */
-+#define IPT_STRING_HAYSTACK_THRESH 100
-+#define IPT_STRING_NEEDLE_THRESH 20
-+
-+#define BM_MAX_NLEN 256
-+#define BM_MAX_HLEN 1024
-+
-+typedef char *(*proc_ipt_search) (char *, char *, int, int);
-+
-+struct ipt_string_info {
-+ char string[BM_MAX_NLEN];
-+ u_int16_t invert;
-+ u_int16_t len;
-+};
-+
-+#endif /* _IPT_STRING_H */
diff -urN linux.orig/net/ipv4/netfilter/ipt_string.c linux/net/ipv4/netfilter/ipt_string.c
---- linux.orig/net/ipv4/netfilter/ipt_string.c Thu Jan 1 01:00:00 1970
-+++ linux/net/ipv4/netfilter/ipt_string.c Thu Feb 21 20:26:09 2002
-@@ -0,0 +1,214 @@
+--- linux.orig/net/ipv4/netfilter/ipt_string.c Wed May 29 11:42:54 2002
++++ linux/net/ipv4/netfilter/ipt_string.c Wed May 29 11:42:54 2002
+@@ -0,0 +1,111 @@
+/* Kernel module to match a string into a packet.
+ *
+ * Copyright (C) 2000 Emmanuel Roger <[EMAIL PROTECTED]>
++ * Copyright (c) 2002 Gianni Tedesco <[EMAIL PROTECTED]>
+ *
+ * ChangeLog
++ * 29.05.2002: Gianni Tedesco <[EMAIL PROTECTED]>
++ * Totally re-wrote, much more efficient. Use boyer-moore
++ * in all cases now. No more SMP problems - data is now
++ * stored in the matchinfo.
+ * 19.02.2002: Gianni Tedesco <[EMAIL PROTECTED]>
+ * Fixed SMP re-entrancy problem using per-cpu data areas
+ * for the skip/shift tables.
@@ -55,77 +35,6 @@
+#include <linux/netfilter_ipv4/ip_tables.h>
+#include <linux/netfilter_ipv4/ipt_string.h>
+
-+struct string_per_cpu {
-+ int *skip;
-+ int *shift;
-+ int *len;
-+};
-+
-+struct string_per_cpu *bm_string_data=NULL;
-+
-+/* Boyer Moore Sublinear string search - VERY FAST */
-+char *search_sublinear (char *needle, char *haystack, int needle_len, int haystack_len)
-+{
-+ int M1, right_end, sk, sh;
-+ int ended, j, i;
-+
-+ int *skip, *shift, *len;
-+
-+ /* use data suitable for this CPU */
-+ shift=bm_string_data[smp_processor_id()].shift;
-+ skip=bm_string_data[smp_processor_id()].skip;
-+ len=bm_string_data[smp_processor_id()].len;
-+
-+ /* Setup skip/shift tables */
-+ M1 = right_end = needle_len-1;
-+ for (i = 0; i < BM_MAX_HLEN; i++) skip[i] = needle_len;
-+ for (i = 0; needle[i]; i++) skip[needle[i]] = M1 - i;
-+
-+ for (i = 1; i < needle_len; i++) {
-+ for (j = 0; j < needle_len && needle[M1 - j] == needle[M1 - i - j]; j++);
-+ len[i] = j;
-+ }
-+
-+ shift[0] = 1;
-+ for (i = 1; i < needle_len; i++) shift[i] = needle_len;
-+ for (i = M1; i > 0; i--) shift[len[i]] = i;
-+ ended = 0;
-+
-+ for (i = 0; i < needle_len; i++) {
-+ if (len[i] == M1 - i) ended = i;
-+ if (ended) shift[i] = ended;
-+ }
-+
-+ /* Do the search*/
-+ while (right_end < haystack_len)
-+ {
-+ for (i = 0; i < needle_len && haystack[right_end - i] == needle[M1 - i]; i++);
-+ if (i == needle_len) {
-+ return haystack+(right_end - M1);
-+ }
-+
-+ sk = skip[haystack[right_end - i]];
-+ sh = shift[i];
-+ right_end = max(right_end - i + sk, right_end + sh);
-+ }
-+
-+ return NULL;
-+}
-+
-+/* Linear string search based on memcmp() */
-+char *search_linear (char *needle, char *haystack, int needle_len, int haystack_len)
-+{
-+ char *k = haystack + (haystack_len-needle_len);
-+ char *t = haystack;
-+
-+ while ( t++ < k ) {
-+ if ( memcmp(t, needle, needle_len) == 0 ) return t;
-+ }
-+
-+ return NULL;
-+}
-+
-+
+static int
+match(const struct sk_buff *skb,
+ const struct net_device *in,
@@ -138,35 +47,40 @@
+{
+ const struct ipt_string_info *info = matchinfo;
+ struct iphdr *ip = skb->nh.iph;
-+ int hlen, nlen;
-+ char *needle, *haystack;
-+ proc_ipt_search search=search_linear;
++ int hlen;
++ char *haystack;
++ int b_idx;
+
+ if ( !ip ) return 0;
+
-+ /* get lenghts, and validate them */
-+ nlen=info->len;
-+ hlen=ntohs(ip->tot_len)-(ip->ihl*4);
-+ if ( nlen > hlen ) return 0;
-+
-+ needle=(char *)&info->string;
-+ haystack=(char *)ip+(ip->ihl*4);
-+
-+ /* The sublinear search comes in to its own
-+ * on the larger packets */
-+ if ( (hlen>IPT_STRING_HAYSTACK_THRESH) &&
-+ (nlen>IPT_STRING_NEEDLE_THRESH) ) {
-+ if ( hlen < BM_MAX_HLEN ) {
-+ search=search_sublinear;
-+ }else{
-+ if (net_ratelimit())
-+ printk(KERN_INFO "ipt_string: Packet too big "
-+ "to attempt sublinear string search "
-+ "(%d bytes)\n", hlen );
++ /* get lengths, and validate them */
++ b_idx=info->len;
++ hlen=ntohs(ip->tot_len)-(ip->ihl<<2);
++ if ( b_idx > hlen ) return 0;
++
++ /* We search everything below the IP header, hrm...
++ * not sure about what we should be searching exactly
++ */
++ haystack=((char *)ip)+(ip->ihl<<2);
++
++ while(b_idx<=hlen) {
++ int p_idx=info->len;
++ int skip_stride,shift_stride;
++
++ while(haystack[--b_idx]==info->string[--p_idx]) {
++ if(b_idx<0) return info->invert^0;
++ if(p_idx==0) return info->invert^1;
+ }
++
++ skip_stride=info->skip[(unsigned char)haystack[b_idx]];
++ shift_stride=info->shift[p_idx];
++
++ /* max() avoidance */
++ b_idx += (skip_stride>shift_stride) ?
++ skip_stride : shift_stride;
+ }
-+
-+ return ((search(needle, haystack, nlen, hlen)!=NULL) ^ info->invert);
++
++ return 0 ^ info->invert;
+}
+
+static int
@@ -183,61 +97,37 @@
+ return 1;
+}
+
-+void string_freeup_data(void)
-+{
-+ int c;
-+
-+ if ( bm_string_data ) {
-+ for(c=0; c<smp_num_cpus; c++) {
-+ if ( bm_string_data[c].shift ) kfree(bm_string_data[c].shift);
-+ if ( bm_string_data[c].skip ) kfree(bm_string_data[c].skip);
-+ if ( bm_string_data[c].len ) kfree(bm_string_data[c].len);
-+ }
-+ kfree(bm_string_data);
-+ }
-+}
-+
+static struct ipt_match string_match
+= { { NULL, NULL }, "string", &match, &checkentry, NULL, THIS_MODULE };
+
+static int __init init(void)
+{
-+ int c;
-+ size_t tlen;
-+ size_t alen;
-+
-+ tlen=sizeof(struct string_per_cpu)*smp_num_cpus;
-+ alen=sizeof(int)*BM_MAX_HLEN;
-+
-+ /* allocate array of structures */
-+ if ( !(bm_string_data=kmalloc(tlen,GFP_KERNEL)) ) {
-+ return 0;
-+ }
-+
-+ memset(bm_string_data, 0, tlen);
-+
-+ /* allocate our skip/shift tables */
-+ for(c=0; c<smp_num_cpus; c++) {
-+ if ( !(bm_string_data[c].shift=kmalloc(alen, GFP_KERNEL)) )
-+ goto alloc_fail;
-+ if ( !(bm_string_data[c].skip=kmalloc(alen, GFP_KERNEL)) )
-+ goto alloc_fail;
-+ if ( !(bm_string_data[c].len=kmalloc(alen, GFP_KERNEL)) )
-+ goto alloc_fail;
-+ }
-+
+ return ipt_register_match(&string_match);
-+
-+alloc_fail:
-+ string_freeup_data();
-+ return 0;
+}
+
+static void __exit fini(void)
+{
+ ipt_unregister_match(&string_match);
-+ string_freeup_data();
+}
+
++MODULE_LICENSE("GPL");
+module_init(init);
+module_exit(fini);
+diff -urN linux.orig/include/linux/netfilter_string.h linux/include/linux/netfilter_ipv4/ipt_string.h
+--- linux.orig/include/linux/netfilter_ipv4/ipt_string.h Wed May 29 11:25:42 2002
++++ linux/include/linux/netfilter_ipv4/ipt_string.h Wed May 29 11:25:42 2002
+@@ -0,0 +1,14 @@
++#ifndef _IPT_STRING_H
++#define _IPT_STRING_H
++
++#define BM_MAX_NLEN 256
++
++struct ipt_string_info {
++ u_int16_t invert;
++ u_int16_t len;
++ char string[BM_MAX_NLEN];
++ int shift[BM_MAX_NLEN];
++ int skip[256];
++};
++
++#endif /* _IPT_STRING_H */
diff -urN netfilter.orig/userspace/patch-o-matic/extra/string.patch.help netfilter/userspace/patch-o-matic/extra/string.patch.help
--- netfilter.orig/userspace/patch-o-matic/extra/string.patch.help Sun Oct 21 14:45:41 2001
+++ netfilter/userspace/patch-o-matic/extra/string.patch.help Wed May 29 12:04:23 2002
@@ -1,8 +1,5 @@
Author: Emmanuel Roger <[EMAIL PROTECTED]>
-Status: Working, not with kernel 2.4.9
+Status: Working
This patch adds CONFIG_IP_NF_MATCH_STRING which allows you to
match a string in a whole packet.
-
-THIS PATCH DOES NOT WORK WITH KERNEL 2.4.9 !!!
-
signature.asc
Description: This is a digitally signed message part
