[PATCH] Boyer Moore textsearch bug fix

[PATCH] Boyer Moore textsearch bug fix

[Michael Rash]

Hi -

The patch below fixes Bugzilla #501:

The compute_prefix_tbl() function in lib/ts_bm.c is called before
bm->pattern is initialized, and this results in the following issue.
If the rule below is put within the OUTPUT chain (note the slightly
repetitive pattern "aaabbbccc" which I think is necessary to expose
the fact that the good_shift array is not getting populated
correctly):

iptables -I OUTPUT -p tcp --dport 80 -m string --string "aaabbbccc" \
--algo bm -j LOG --log-prefix "bm "

...then the issuing the following commands fail to match the rule (no
log message is generated):

echo "1aaabbbccc" |nc <someserver> 80
echo "12aaabbbccc" |nc <someserver> 80
echo "1234aaabbbccc" |nc <someserver> 80

...but these do match:

echo "aaabbbccc" |nc <someserver> 80
echo "123aaabbbccc" |nc <someserver> 80

--
Michael Rash
http://www.cipherdyne.org/
Key fingerprint = 53EA 13EA 472E 3771 894F  AC69 95D8 5D6B A742 839F


--- linux-2.6.17.8/lib/ts_bm.c.orig	2006-08-16 21:17:38.000000000 -0400
+++ linux-2.6.17.8/lib/ts_bm.c	2006-08-16 21:17:56.000000000 -0400
@@ -151,8 +151,8 @@
 	bm = ts_config_priv(conf);
 	bm->patlen = len;
 	bm->pattern = (u8 *) bm->good_shift + prefix_tbl_len;
-	compute_prefix_tbl(bm, pattern, len);
 	memcpy(bm->pattern, pattern, len);
+	compute_prefix_tbl(bm, pattern, len);
 
 	return conf;
 }

Re: [PATCH] Boyer Moore textsearch bug fix

[Patrick McHardy]

Michael Rash wrote:
> --- linux-2.6.17.8/lib/ts_bm.c.orig	2006-08-16 21:17:38.000000000 -0400
> +++ linux-2.6.17.8/lib/ts_bm.c	2006-08-16 21:17:56.000000000 -0400
> @@ -151,8 +151,8 @@
>  	bm = ts_config_priv(conf);
>  	bm->patlen = len;
>  	bm->pattern = (u8 *) bm->good_shift + prefix_tbl_len;
> -	compute_prefix_tbl(bm, pattern, len);
>  	memcpy(bm->pattern, pattern, len);
> +	compute_prefix_tbl(bm, pattern, len);


Good catch, thanks. But since both pattern and len are also passed
to compute_prefix_tbl as arguments, I think we should either make
it use only those arguments, or remove those arguments and use only
the values from struct ts_bm.

Please send a new patch and add a Signed-off-by line so I can
apply it. Thanks.

Re: [PATCH] Boyer Moore textsearch bug fix

[Pablo Neira Ayuso]

Patrick McHardy wrote:
> Michael Rash wrote:
> 
>>--- linux-2.6.17.8/lib/ts_bm.c.orig	2006-08-16 21:17:38.000000000 -0400
>>+++ linux-2.6.17.8/lib/ts_bm.c	2006-08-16 21:17:56.000000000 -0400
>>@@ -151,8 +151,8 @@
>> 	bm = ts_config_priv(conf);
>> 	bm->patlen = len;
>> 	bm->pattern = (u8 *) bm->good_shift + prefix_tbl_len;
>>-	compute_prefix_tbl(bm, pattern, len);
>> 	memcpy(bm->pattern, pattern, len);
>>+	compute_prefix_tbl(bm, pattern, len);
> 
> 
> 
> Good catch, thanks. But since both pattern and len are also passed
> to compute_prefix_tbl as arguments, I think we should either make
> it use only those arguments, or remove those arguments and use only
> the values from struct ts_bm.

Damn, that is my fault, thanks for the catch Michael.

> Please send a new patch and add a Signed-off-by line so I can
> apply it. Thanks.

Patrick, do you plan to pass this patch to -stable as well?

-- 
The dawn of the fourth age of Linux firewalling is coming; a time of 
great struggle and heroic deeds -- J.Kadlecsik got inspired by J.Morris

Re: [PATCH] Boyer Moore textsearch bug fix

[Patrick McHardy]

Pablo Neira Ayuso wrote:
> Patrick, do you plan to pass this patch to -stable as well?

Not yet, but I can do that.

Re: [PATCH] Boyer Moore textsearch bug fix

[Michael Rash]

On Aug 17, 2006, Patrick McHardy wrote:

> Michael Rash wrote:
> > --- linux-2.6.17.8/lib/ts_bm.c.orig	2006-08-16 21:17:38.000000000 -0400
> > +++ linux-2.6.17.8/lib/ts_bm.c	2006-08-16 21:17:56.000000000 -0400
> > @@ -151,8 +151,8 @@
> >  	bm = ts_config_priv(conf);
> >  	bm->patlen = len;
> >  	bm->pattern = (u8 *) bm->good_shift + prefix_tbl_len;
> > -	compute_prefix_tbl(bm, pattern, len);
> >  	memcpy(bm->pattern, pattern, len);
> > +	compute_prefix_tbl(bm, pattern, len);
> 
> 
> Good catch, thanks. But since both pattern and len are also passed
> to compute_prefix_tbl as arguments, I think we should either make
> it use only those arguments, or remove those arguments and use only
> the values from struct ts_bm.
> 
> Please send a new patch and add a Signed-off-by line so I can
> apply it. Thanks.

Got it.  Here is a new patch.  Thanks.

--Mike


Signed-off-by: Michael Rash <mbr@cipherdyne.org>


--- linux-2.6.17.8/lib/ts_bm.c.orig	2006-08-16 21:17:38.000000000 -0400
+++ linux-2.6.17.8/lib/ts_bm.c	2006-08-17 10:35:25.000000000 -0400
@@ -112,15 +112,14 @@
 	return ret;
 }
 
-static void compute_prefix_tbl(struct ts_bm *bm, const u8 *pattern,
-			       unsigned int len)
+static void compute_prefix_tbl(struct ts_bm *bm)
 {
 	int i, j, g;
 
 	for (i = 0; i < ASIZE; i++)
-		bm->bad_shift[i] = len;
-	for (i = 0; i < len - 1; i++)
-		bm->bad_shift[pattern[i]] = len - 1 - i;
+		bm->bad_shift[i] = bm->patlen;
+	for (i = 0; i < bm->patlen - 1; i++)
+		bm->bad_shift[bm->pattern[i]] = bm->patlen - 1 - i;
 
 	/* Compute the good shift array, used to match reocurrences 
 	 * of a subpattern */
@@ -151,8 +150,8 @@
 	bm = ts_config_priv(conf);
 	bm->patlen = len;
 	bm->pattern = (u8 *) bm->good_shift + prefix_tbl_len;
-	compute_prefix_tbl(bm, pattern, len);
 	memcpy(bm->pattern, pattern, len);
+	compute_prefix_tbl(bm);
 
 	return conf;
 }

Re: [PATCH] Boyer Moore textsearch bug fix

[Patrick McHardy]

Michael Rash wrote:
> Got it.  Here is a new patch.  Thanks.

Applied, thanks Michael.