Skip to contentSkip to conversation

Boyer Moore textsearch bug fix

PATCH Applied Michael Rash 3 participants 6 messages Aug 17, 2006

Subsystems (2)
Library code netfilter
lore
Share & tools
lore

Michael Rash

author
#0 lore raw

PATCH 1/1 Boyer Moore textsearch bug fix

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

lib/ts_bm.c renamed from lib/ts_bm.c.orig +1 -1
@@ -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;
 }
#1 lore raw

lib/ts_bm.c line 155

Quoted 9 lines · Michael Rash
lib/ts_bm.c renamed from lib/ts_bm.c.orig +1 -1
@@ -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.

maintainer
#2 lore raw
Quoted 18 lines · Patrick McHardy

lib/ts_bm.c line 155

Quoted 9 lines · Michael Rash
lib/ts_bm.c renamed from lib/ts_bm.c.orig +1 -1
@@ -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.

Quoted 2 lines

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?

Signature · 1 line
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
#3 lore raw
Quoted 1 line · Pablo Neira Ayuso

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

Not yet, but I can do that.

author
#4 lore raw
In reply to Patrick McHardy
Quoted 17 lines · Patrick McHardy

lib/ts_bm.c line 155

Quoted 9 lines · Michael Rash
lib/ts_bm.c renamed from lib/ts_bm.c.orig +1 -1
@@ -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.

Quoted 2 lines

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 <[email protected]>
lib/ts_bm.c renamed from lib/ts_bm.c.orig +5 -6
@@ -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;
 }
Applied
#5 lore raw
Quoted 1 line · Michael Rash

Got it. Here is a new patch. Thanks.

Applied, thanks Michael.