* [PATCH] textsearch oops fix on 64-bit
@ 2006-01-28 22:54 Michael Rash
2006-01-29 18:50 ` Pablo Neira Ayuso
0 siblings, 1 reply; 3+ messages in thread
From: Michael Rash @ 2006-01-28 22:54 UTC (permalink / raw)
To: Pablo Neira Ayuso; +Cc: netfilter-devel
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
^ permalink raw reply [flat|nested] 3+ messages in thread* Re: [PATCH] textsearch oops fix on 64-bit 2006-01-28 22:54 [PATCH] textsearch oops fix on 64-bit Michael Rash @ 2006-01-29 18:50 ` Pablo Neira Ayuso 2006-01-29 20:29 ` Michael Rash 0 siblings, 1 reply; 3+ messages in thread From: Pablo Neira Ayuso @ 2006-01-29 18:50 UTC (permalink / raw) To: Michael Rash; +Cc: netfilter-devel [-- 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; + } } } ^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] textsearch oops fix on 64-bit 2006-01-29 18:50 ` Pablo Neira Ayuso @ 2006-01-29 20:29 ` Michael Rash 0 siblings, 0 replies; 3+ messages in thread From: Michael Rash @ 2006-01-29 20:29 UTC (permalink / raw) To: Pablo Neira Ayuso; +Cc: Michael Rash, netfilter-devel 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; > + } > } > } > ^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2006-01-29 20:29 UTC | newest] Thread overview: 3+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2006-01-28 22:54 [PATCH] textsearch oops fix on 64-bit Michael Rash 2006-01-29 18:50 ` Pablo Neira Ayuso 2006-01-29 20:29 ` Michael Rash
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.