大网数据广告活动
服务器运维问答

What is the difference BM and KMP algorithms in iptables string search?

· 52CE 我爱测

Iptables has a string module for searching packet contents. But it forces you to choose between one these algorithms: Boyer-Moore (bm) and Knuth-Pratt-Morris (kmp). I couldn't find any good documentation on which cases should I u…

问题原文

原帖链接 · LatinSuD · CC BY-SA 4.0

Iptables has a string module for searching packet contents. But it forces you to choose between one these algorithms: Boyer-Moore (bm) and Knuth-Pratt-Morris (kmp). I couldn't find any good documentation on which cases should I use one algorithm over the other.

Which one is better?

The other issue I found is that BM sometimes misses packets. I've found reports of people having the same issue.

# 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

As you can see, the BM rule didn't match despite being placed first.

社区高分解答

原帖链接 · A.B · CC BY-SA 4.0

In this answer I'm leaving aside the mathematics/complexity considerations (one algorithm might be more adequate depending on the type of problem and size of the pattern) that should normally have been the only considerations to have.

Various references: 1, 2, 3.


The Linux's xtables implementation has recently (2023-06) received two patches coming after a longstanding (2019-12) bug report: Bug 1390 - iptables -m string not working with --algo bm and OUTPUT chain under 5.3.x

Under 5.3.x, iptables -A OUTPUT -p tcp -m string --algo bm --string POST -j DROP does not drop outgoing packets containing "POST". This command was instead working as intended with 5.0.0.

one part was a bug that got fixed, but the other part is a known limitation since the algorithm is available.

Thus an iptables-extensions documentation update to get more attention:

man: string: document BM false negatives

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.

It's the same warning as the one present in kernel sources (since 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.
 */

So in presence of a non-linear skbuff (the kernel object handling any packet, where data can sometimes be split in multiples memory blocks), possibly due to acceleration available in NIC and drivers, possibly with features like TCP Segmentation Offload or various tunnel offload features, etc., the BM algorithm could fail to find a result when KMP will find one.

The warning tells:

  • correctness? stick to KMP
  • performance? you can use BM

摘自公开归档,保留原文语言,版式经整理,外部媒体与邮箱地址已移除。

资料来源与适用范围

资料来源
Server Fault
适用范围
以原帖系统、软件版本与发布日期为准(2023-08-20)
内容语言
中文;命令、路径和错误标识保留技术原文
本地收录日期
2026-11-15
授权说明
CC BY-SA 4.0

正文与所需资源由本站本地存储。查看来源及更新记录 ↗

请按适用版本和实际日志确认原因;本站没有对每一种系统或设备逐项执行文中的操作。