[PATCH] lib-imap: imap-match - Fix excessive CPU usage caused by backtracking
Backport the NFA/non-backtracking algorithm from
2684624… while retaining the
byte-oriented matcher semantics of 2.4.1.
Original commit message:
Replace the recursive backtracking matcher with a Thompson-style NFA
simulation over grapheme clusters.
Each grapheme cluster of the compressed pattern becomes one state:
LITERAL, PERCENT (consume any number of non-separator clusters) or STAR
(consume any number of clusters including separators). A virtual
ACCEPT position sits at index n_states. Simulation tracks the set of
active positions in a bitmap. Epsilon-closure (skipping a PERCENT or
STAR without consuming) is a single forward pass because the NFA is
linear: each state can only epsilon-skip to i+1.
The resulting match is O(n_data * n_pattern) regardless of pattern
shape, with no recursion and no backtracking, so there is no way for
a malicious pattern or mailbox name to trigger exponential CPU,
excessive stack depth, or unbounded memory.
IMAP_MATCH_YES / NO / CHILDREN / PARENT semantics are preserved:
- YES: ACCEPT reachable after consuming all data.
- PARENT: ACCEPT was active at some point while the next data
grapheme cluster was the separator.
- CHILDREN: some active non-ACCEPT state remains after consuming all
data, and either the data ends with a separator or an
active state can still consume a separator (precomputed
as sep_accept[]).
Inboxcase handling (case-insensitive comparison for the INBOX prefix
of data) and grapheme-cluster comparison are unchanged - the existing
match_gc logic is reused inline as literal_matches().
pattern_compress() and pattern_is_inboxcase() are unchanged.
Gbp-Pq: Name 0001-lib-imap-imap-match-Fix-excessive-CPU-usage-caused-b.patch