]> dgit.raspbian.org Git - dovecot.git/commit
[PATCH] lib-imap: imap-match - Fix excessive CPU usage caused by backtracking
authorNoah Meyerhans <noahm@debian.org>
Thu, 10 Sep 2026 13:59:18 +0000 (09:59 -0400)
committerNoah Meyerhans <noahm@debian.org>
Wed, 16 Sep 2026 19:06:35 +0000 (15:06 -0400)
commiteeb3b3bc073e12bcfee63a270cc992d2fe6159e7
tree7a70698625f77f7f3e60fc546412a25976afa0ac
parentd6e00ee311705d04218c128b320cca8a7e705f3d
[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
src/lib-imap/imap-match.c
src/lib-imap/test-imap-match.c