[PATCH] textsearch oops fix on 64-bit

[PATCH] textsearch oops fix on 64-bit

[Michael Rash]

Hi -

When using the string match on kernels 2.6.14 through 2.6.15.1, I get an
oops with Boyer-Moore on my AMD Athlon 64 processor (the Knuth-Morris-Pratt
algorithm works fine).  The oops happens at load time for any Netfilter
rule that attempts to use the string match.  I believe the problem stems
from missing bounds checking on array indices in lib/ts_bm.c within
compute_prefix_tbl().  Here is a patch against 2.6.15.1; I have tested it
on both 32-bit and 64-bit processors and it seems to work.  If the patch
looks ok, I will submit it to the kernel mailing list:


--- linux-2.6.15.1/lib/ts_bm.c.orig     2006-01-27 18:22:44.000000000 -0500
+++ linux-2.6.15.1/lib/ts_bm.c  2006-01-27 18:22:50.000000000 -0500
@@ -107,8 +107,10 @@ static void compute_prefix_tbl(struct ts
        /* Compute the good shift array, used to match reocurrences
         * of a subpattern */
        for (i = 1; i < bm->patlen; i++) {
-               for (j = 0; j < bm->patlen && bm->pattern[bm->patlen - 1 - j]
-                               == bm->pattern[bm->patlen - 1 - i - j]; j++);
+               for (j = 0; j < bm->patlen
+                               && (int)(bm->patlen - 1 - i - j) >= 0
+                               && bm->pattern[bm->patlen - 1 - j]
+                                       == bm->pattern[bm->patlen - 1 - i - j]; j++);
                l[i] = j;
        }


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

Re: [PATCH] textsearch oops fix on 64-bit

[Pablo Neira Ayuso]

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

Hi,

Michael Rash wrote:
> When using the string match on kernels 2.6.14 through 2.6.15.1, I get an
> oops with Boyer-Moore on my AMD Athlon 64 processor (the Knuth-Morris-Pratt
> algorithm works fine).  The oops happens at load time for any Netfilter
> rule that attempts to use the string match.  I believe the problem stems
> from missing bounds checking on array indices in lib/ts_bm.c within
> compute_prefix_tbl().  Here is a patch against 2.6.15.1; I have tested it
> on both 32-bit and 64-bit processors and it seems to work.  If the patch
> looks ok, I will submit it to the kernel mailing list

I've revisited the current logic to calculate the good shift array and I
found more problems, my fault. Could you give a try to the patch
attached and tell me if it works for you?

Thanks.

-- 
Pablo

[-- Attachment #2: fix-bm-goodsuffix.patch --]
[-- Type: text/plain, Size: 2202 bytes --]

[TEXTSEARCH] Fix broken good shift array calculation in Boyer-Moore

The current logic does not calculate correctly the good shift array:
Let x be the pattern that is being searched. Let y be the block of data. 
The good shift array aligns rightmost the segment:

x[i+1 ... m-1] = y[i+j+1 ... j+m-1]

with its rightmost occurrence in x that fulfils x[i] neq y[i+j].

In previous version, the good shift array for the pattern ANPANMAN is:
[1, 8, 3, 8, 8, 8, 8, 8]
and should be:
[1, 8, 3, 6, 6, 6, 6, 6]

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>

Index: net-2.6.git/lib/ts_bm.c
===================================================================
--- net-2.6.git.orig/lib/ts_bm.c	2006-01-29 05:10:25.000000000 +0100
+++ net-2.6.git/lib/ts_bm.c	2006-01-29 05:25:47.000000000 +0100
@@ -94,10 +94,28 @@ next:			bs = bm->bad_shift[text[shift-i]
 	return UINT_MAX;
 }
 
+static int subpattern(u8 *pattern, int i, int j, int g)
+{
+	int x = i+g-1, y = j+g-1, ret = 0;
+
+	while(pattern[x--] == pattern[y--]) {
+		if (y < 0) {
+			ret = 1;
+			break;
+		}
+		if (--g == 0) {
+			ret = pattern[i-1] != pattern[j-1];
+			break;
+		}
+	}
+
+	return ret;
+}
+
 static void compute_prefix_tbl(struct ts_bm *bm, const u8 *pattern,
 			       unsigned int len)
 {
-	int i, j, ended, l[ASIZE];
+	int i, j, g;
 
 	for (i = 0; i < ASIZE; i++)
 		bm->bad_shift[i] = len;
@@ -106,23 +124,15 @@ static void compute_prefix_tbl(struct ts
 
 	/* Compute the good shift array, used to match reocurrences 
 	 * of a subpattern */
-	for (i = 1; i < bm->patlen; i++) {
-		for (j = 0; j < bm->patlen && bm->pattern[bm->patlen - 1 - j]
-				== bm->pattern[bm->patlen - 1 - i - j]; j++);
-		l[i] = j;
-	}  
-
 	bm->good_shift[0] = 1;
 	for (i = 1; i < bm->patlen; i++)
 		bm->good_shift[i] = bm->patlen;
-	for (i = bm->patlen - 1; i > 0; i--)
-		bm->good_shift[l[i]] = i;
-	ended = 0;
-	for (i = 0; i < bm->patlen; i++) {
-		if (l[i] == bm->patlen - 1 - i)
-			ended = i;
-		if (ended)
-			bm->good_shift[i] = ended;
+        for (i = bm->patlen-1, g = 1; i > 0; g++, i--) {
+		for (j = i-1; j >= 1-g ; j--)
+			if (subpattern(bm->pattern, i, j, g)) {
+				bm->good_shift[g] = bm->patlen-j-g;
+				break;
+			}
 	}
 }
 

Re: [PATCH] textsearch oops fix on 64-bit

[Michael Rash]

Looks good.  I'm currently running with about 1500 string matching rules
generated by fwsnort (http://www.cipherdyne.org/fwsnort/), and I have
tested on both 32 and 64 bit processors.

Michael


On Jan 29, 2006, Pablo Neira Ayuso wrote:

> Hi,
> 
> Michael Rash wrote:
> > When using the string match on kernels 2.6.14 through 2.6.15.1, I get an
> > oops with Boyer-Moore on my AMD Athlon 64 processor (the Knuth-Morris-Pratt
> > algorithm works fine).  The oops happens at load time for any Netfilter
> > rule that attempts to use the string match.  I believe the problem stems
> > from missing bounds checking on array indices in lib/ts_bm.c within
> > compute_prefix_tbl().  Here is a patch against 2.6.15.1; I have tested it
> > on both 32-bit and 64-bit processors and it seems to work.  If the patch
> > looks ok, I will submit it to the kernel mailing list
> 
> I've revisited the current logic to calculate the good shift array and I
> found more problems, my fault. Could you give a try to the patch
> attached and tell me if it works for you?
> 
> Thanks.
> 
> -- 
> Pablo

> [TEXTSEARCH] Fix broken good shift array calculation in Boyer-Moore
> 
> The current logic does not calculate correctly the good shift array:
> Let x be the pattern that is being searched. Let y be the block of data. 
> The good shift array aligns rightmost the segment:
> 
> x[i+1 ... m-1] = y[i+j+1 ... j+m-1]
> 
> with its rightmost occurrence in x that fulfils x[i] neq y[i+j].
> 
> In previous version, the good shift array for the pattern ANPANMAN is:
> [1, 8, 3, 8, 8, 8, 8, 8]
> and should be:
> [1, 8, 3, 6, 6, 6, 6, 6]
> 
> Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
> 
> Index: net-2.6.git/lib/ts_bm.c
> ===================================================================
> --- net-2.6.git.orig/lib/ts_bm.c	2006-01-29 05:10:25.000000000 +0100
> +++ net-2.6.git/lib/ts_bm.c	2006-01-29 05:25:47.000000000 +0100
> @@ -94,10 +94,28 @@ next:			bs = bm->bad_shift[text[shift-i]
>  	return UINT_MAX;
>  }
>  
> +static int subpattern(u8 *pattern, int i, int j, int g)
> +{
> +	int x = i+g-1, y = j+g-1, ret = 0;
> +
> +	while(pattern[x--] == pattern[y--]) {
> +		if (y < 0) {
> +			ret = 1;
> +			break;
> +		}
> +		if (--g == 0) {
> +			ret = pattern[i-1] != pattern[j-1];
> +			break;
> +		}
> +	}
> +
> +	return ret;
> +}
> +
>  static void compute_prefix_tbl(struct ts_bm *bm, const u8 *pattern,
>  			       unsigned int len)
>  {
> -	int i, j, ended, l[ASIZE];
> +	int i, j, g;
>  
>  	for (i = 0; i < ASIZE; i++)
>  		bm->bad_shift[i] = len;
> @@ -106,23 +124,15 @@ static void compute_prefix_tbl(struct ts
>  
>  	/* Compute the good shift array, used to match reocurrences 
>  	 * of a subpattern */
> -	for (i = 1; i < bm->patlen; i++) {
> -		for (j = 0; j < bm->patlen && bm->pattern[bm->patlen - 1 - j]
> -				== bm->pattern[bm->patlen - 1 - i - j]; j++);
> -		l[i] = j;
> -	}  
> -
>  	bm->good_shift[0] = 1;
>  	for (i = 1; i < bm->patlen; i++)
>  		bm->good_shift[i] = bm->patlen;
> -	for (i = bm->patlen - 1; i > 0; i--)
> -		bm->good_shift[l[i]] = i;
> -	ended = 0;
> -	for (i = 0; i < bm->patlen; i++) {
> -		if (l[i] == bm->patlen - 1 - i)
> -			ended = i;
> -		if (ended)
> -			bm->good_shift[i] = ended;
> +        for (i = bm->patlen-1, g = 1; i > 0; g++, i--) {
> +		for (j = i-1; j >= 1-g ; j--)
> +			if (subpattern(bm->pattern, i, j, g)) {
> +				bm->good_shift[g] = bm->patlen-j-g;
> +				break;
> +			}
>  	}
>  }
>