☰

iptables 字符串搜索中 BM 和 KMP 算法有什么区别？

tag-icon • tag-icon iptables
iptables 字符串搜索中 BM 和 KMP 算法有什么区别？

Iptables 有一个用于搜索数据包内容的字符串模块。但它迫使您在以下算法之间进行选择：Boyer-Moore (bm) 和 Knuth-Pratt-Morris (kmp)。我找不到任何好的文档来说明在哪些情况下应该使用一种算法而不是另一种算法。

哪一个更好？

我发现的另一个问题是 BM 有时会丢失数据包。我发现有人报告遇到同样的问题。

# iptables -A OUTPUT -m string --string teststring --algo bm
# iptables -A OUTPUT -m string --string teststring --algo kmp

# wget -O/dev/null http://www.example.com/teststring

# iptables -nvL OUTPUT
Chain OUTPUT (policy ACCEPT 0 packets, 0 bytes)
 pkts bytes target     prot opt in     out     source               destination         
    0     0            0    --  *      *       0.0.0.0/0            0.0.0.0/0            STRING match  "teststring" ALGO name bm
    1   192            0    --  *      *       0.0.0.0/0            0.0.0.0/0            STRING match  "teststring" ALGO name kmp

如您所见，尽管 BM 规则被放在第一位，但它并不匹配。

答案1

在这个答案中，我抛开了数学/复杂性的考虑（一种算法可能更适合于问题的类型和模式的大小），而这些通常应该是唯一需要考虑的因素。

各种参考：1，2，3。

Linux 的 xtables 实现最近（2023-06）收到了两个补丁，这些补丁是在长期存在的（2019-12）错误报告之后发布的：错误 1390- iptables -m 字符串在 5.3.x 下无法与 --algo bm 和 OUTPUT 链配合使用

在 5.3.x 下，iptables -A OUTPUT -p tcp -m string --algo bm --string POST -j DROP不会丢弃包含“POST”的传出数据包。此命令在 5.0.0 中按预期工作。

一部分是已经修复的错误，但另一部分是已知的限制，因为算法可用。

因此iptables-extensions 文档更新获得更多关注：

man: 字符串：document BM 误判

对于非线性 skb，内核的 Boyer-Moore 文本搜索实现可能会错过匹配。内核源代码中有一个关于此问题的警告。请将该警告包含在手册页中。

这与当前的警告相同在内核源代码中（自 2005 年起）：

 *   Note: Since Boyer-Moore (BM) performs searches for matchings from right 
 *   to left, it's still possible that a matching could be spread over 
 *   multiple blocks, in that case this algorithm won't find any coincidence.
 *   
 *   If you're willing 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. 
 *
 *   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.
 */

因此，在存在非线性 skbuff（处理任何数据包的内核对象，其中数据有时可以分成多个内存块）的情况下，可能由于 NIC 和驱动程序中可用的加速，可能具有 TCP 分段卸载或各种隧道卸载功能等功能，当 KMP 找到结果时，BM 算法可能无法找到结果。

警告告知：

  • 正确吗？坚持使用 KMP
  • 性能？您可以使用 BM

答案2

Boyer-Moore (BM) 和 Knuth-Pratt-Morris (KMP) 算法都是用于模式匹配的字符串搜索算法。在iptables字符串模块中，它们用于在数据包内容中搜索特定模式。然而，在这两种算法之间做出选择可能并不像其中一种绝对“优于”另一种那么简单。

以下是这两种算法及其差异的简要概述：

  1. Boyer-Moore（BM）算法：

    • BM 算法以高效处理不匹配而闻名。它对模式进行预处理以创建两个表：“坏字符”表和“好后缀”表。
    • BM 从右向左扫描数据包内容，将模式与内容进行匹配。它根据两个表中的信息将模式移动较大的量，从而跳过不必要的比较。
    • BM 对于较长的模式以及字母表（模式中的字符集）相对较小的情况特别有效。

  2. Knuth-Pratt-Morris（KMP）算法：

    • KMP 算法专注于高效处理部分匹配。它对模式进行预处理，以创建一个“失败”表，用于在不匹配发生时指导模式转移。
    • KMP 从左到右扫描数据包内容，根据故障表中的信息调整其位置，以避免重新检查先前匹配的字符。
    • 当模式具有重复元素或小字母时，通常首选 KMP。

关于您观察到的 BM 规则虽然被放在第一位但却不匹配，这种行为可能有多种原因，包括您的环境的具体情况以及模式和数据包内容的特征。链中规则的顺序iptables可能很重要，如果前一个规则匹配并终止数据包处理，则可能不会评估后续规则。

值得注意的是，两种算法都不是普遍优越的；它们的性能可能因模式、数据包内容和其他因素的具体情况而异。在某些情况下，BM 可能表现更好，而在其他情况下，KMP 可能更高效。

如果您遇到 BM 算法丢失数据包的问题，​​这可能是由于您的模式或数据包内容的特定特征影响了其性能。分析您要搜索的模式、数据包的内容和系统的整体配置以确定最适合您用例的算法是一个好主意。

实际上，您可能需要尝试这两种算法以及其他可能的选项来找到适合您特定场景的最佳解决方案。

相关内容