Show HN: 500x faster string matching for Linux Netfilter (O(1) vs. O(N))
landerrosette Sunday, February 15, 2026
I built a drop-in replacement for the kernel’s xt_string module.
xt_string scales linearly (O(N)), causing massive slowdowns with many rules. Strider uses Aho–Corasick for O(1) matching.
Key Features:
O(1) Algorithmic Complexity: Uses a compact, double-array trie-based Aho–Corasick automaton, sustaining above 1 Gbps when matching 3,000 patterns, while xt_string (KMP) drops below 2 Mbps.
Lockless Datapath: RCU-protected lookups ensure zero locking overhead on the packet processing hot path.
Correctness: Never misses patterns spanning across IP fragments (unlike xt_string’s fast Boyer–Moore mode).
3
0
github.com