[PATCH iptables] man: string: document BM false negatives

[PATCH iptables] man: string: document BM false negatives

[Jeremy Sowden]

For non-linear skb's there's a possibility that the kernel's Boyer-Moore
text-search implementation may miss matches.  There's a warning about
this in the kernel source.  Include that warning in the man-page.

Signed-off-by: Jeremy Sowden <jeremy@azazel.net>
---
 extensions/libxt_string.man | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

diff --git a/extensions/libxt_string.man b/extensions/libxt_string.man
index 5f1a993c57eb..34a8755ba14e 100644
--- a/extensions/libxt_string.man
+++ b/extensions/libxt_string.man
@@ -29,3 +29,18 @@ iptables \-A INPUT \-p tcp \-\-dport 80 \-m string \-\-algo bm \-\-string 'GET /
 # The hex string pattern can be used for non-printable characters, like |0D 0A| or |0D0A|.
 .br
 iptables \-p udp \-\-dport 53 \-m string \-\-algo bm \-\-from 40 \-\-to 57 \-\-hex\-string '|03|www|09|netfilter|03|org|00|'
+.P
+Note: Since Boyer-Moore (BM) performs searches for matchings from right to left
+and the kernel may store a packet in multiple discontiguous blocks, it's still
+possible that a match could be spread over multiple blocks, in that case this
+algorithm won't find it.
+.P
+If you wish to ensure that such thing won't ever happen, use the
+Knuth-Pratt-Morris (KMP) implementation instead. In conclusion, choose the
+proper string search algorithm depending on your setting.
+.P
+Say you're using the textsearch infrastructure for filtering, NIDS or any
+similar security focused purpose, then go KMP. Otherwise, if you really care
+about performance, say you're classifying packets to apply Quality of Service
+(QoS) policies, and you don't mind about possible matchings spread over multiple
+fragments, then go BM.
-- 
2.39.2

[PATCH iptables] man: string: document BM false negatives

[Jeremy Sowden]

For non-linear skb's there's a possibility that the kernel's Boyer-Moore
text-search implementation may miss matches.  There's a warning about
this in the kernel source.  Include that warning in the man-page.

Signed-off-by: Jeremy Sowden <jeremy@azazel.net>
---
 extensions/libxt_string.man | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

diff --git a/extensions/libxt_string.man b/extensions/libxt_string.man
index 5f1a993c57eb..34a8755ba14e 100644
--- a/extensions/libxt_string.man
+++ b/extensions/libxt_string.man
@@ -29,3 +29,18 @@ iptables \-A INPUT \-p tcp \-\-dport 80 \-m string \-\-algo bm \-\-string 'GET /
 # The hex string pattern can be used for non-printable characters, like |0D 0A| or |0D0A|.
 .br
 iptables \-p udp \-\-dport 53 \-m string \-\-algo bm \-\-from 40 \-\-to 57 \-\-hex\-string '|03|www|09|netfilter|03|org|00|'
+.P
+Note: Since Boyer-Moore (BM) performs searches for matchings from right to left
+and the kernel may store a packet in multiple discontiguous blocks, it's still
+possible that a match could be spread over multiple blocks, in that case this
+algorithm won't find it.
+.P
+If you wish to ensure that such thing won't ever happen, use the
+Knuth-Pratt-Morris (KMP) implementation instead. In conclusion, choose the
+proper string search algorithm depending on your setting.
+.P
+Say you're using the textsearch infrastructure for filtering, NIDS or any
+similar security focused purpose, then go KMP. Otherwise, if you really care
+about performance, say you're classifying packets to apply Quality of Service
+(QoS) policies, and you don't mind about possible matchings spread over multiple
+fragments, then go BM.
-- 
2.39.2

[PATCH iptables v2] man: string: document BM false negatives

[Jeremy Sowden]

For non-linear skb's there's a possibility that the kernel's Boyer-Moore
text-search implementation may miss matches.  There's a warning about
this in the kernel source.  Include that warning in the man-page.

Link: https://bugzilla.netfilter.org/show_bug.cgi?id=1390
Signed-off-by: Jeremy Sowden <jeremy@azazel.net>
---
Since v1:

 * Adapt the text better to the context
 * Add `Link:` to the commit message
 
 extensions/libxt_string.man | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

diff --git a/extensions/libxt_string.man b/extensions/libxt_string.man
index 5f1a993c57eb..0822ffdb7870 100644
--- a/extensions/libxt_string.man
+++ b/extensions/libxt_string.man
@@ -29,3 +29,18 @@ iptables \-A INPUT \-p tcp \-\-dport 80 \-m string \-\-algo bm \-\-string 'GET /
 # The hex string pattern can be used for non-printable characters, like |0D 0A| or |0D0A|.
 .br
 iptables \-p udp \-\-dport 53 \-m string \-\-algo bm \-\-from 40 \-\-to 57 \-\-hex\-string '|03|www|09|netfilter|03|org|00|'
+.P
+NB since Boyer-Moore (BM) performs searches for matches from right to left and
+the kernel may store a packet in multiple discontiguous blocks, it's possible
+that a match could be spread over multiple blocks, in which case this algorithm
+won't find it.
+.P
+If you wish to ensure that such thing won't ever happen, use the
+Knuth-Pratt-Morris (KMP) algorithm instead.  In conclusion, choose the proper
+string search algorithm depending on your use-case.
+.P
+For example, if you're using the module for filtering, NIDS or any similar
+security-focused purpose, then choose KMP. On the other hand, if you really care
+about performance \(em for example, you're classifying packets to apply Quality
+of Service (QoS) policies \(em and you don't mind about missing possible matches
+spread over multiple fragments, then choose BM.
-- 
2.39.2

Re: [PATCH iptables v2] man: string: document BM false negatives

[Jan Engelhardt]

On Sunday 2023-06-11 13:34, Jeremy Sowden wrote:

> iptables \-p udp \-\-dport 53 \-m string \-\-algo bm \-\-from 40 \-\-to 57 \-\-hex\-string '|03|www|09|netfilter|03|org|00|'
>+.P
>+NB since Boyer-Moore (BM) performs searches for matches from right to left and
>+the kernel may store a packet in multiple discontiguous blocks, it's possible
>+that a match could be spread over multiple blocks, in which case this algorithm
>+won't find it.

It was better when it just said "Note" instead of NB (notebook, nota bene)

Re: [PATCH iptables v2] man: string: document BM false negatives

[Phil Sutter]

On Sun, Jun 11, 2023 at 02:07:57PM +0200, Jan Engelhardt wrote:
> On Sunday 2023-06-11 13:34, Jeremy Sowden wrote:
> 
> > iptables \-p udp \-\-dport 53 \-m string \-\-algo bm \-\-from 40 \-\-to 57 \-\-hex\-string '|03|www|09|netfilter|03|org|00|'
> >+.P
> >+NB since Boyer-Moore (BM) performs searches for matches from right to left and
> >+the kernel may store a packet in multiple discontiguous blocks, it's possible
> >+that a match could be spread over multiple blocks, in which case this algorithm
> >+won't find it.
> 
> It was better when it just said "Note" instead of NB (notebook, nota bene)

Applied after s/NB/Note:/, thanks everyone!