From 84687ae3ecb8efe0e21bd8be655b53b77122a56b Mon Sep 17 00:00:00 2001 From: Timo Sirainen Date: Sun, 19 Apr 2026 23:10:29 +0000 Subject: [PATCH] [PATCH] lib-sieve: Enforce CPU time limit within :contains and :matches matcher loops The naive O(N*M) substring search in mcht-contains.c and the naive find loop in mcht-matches.c can run for hours on a large value (e.g. a message body), completely bypassing sieve_max_cpu_time because that limit was only checked between bytecode operations. Expose the active CPU limit via sieve_runtime_cpu_limit_exceeded() and poll it every 4096 inner iterations. When the limit is hit the match returns SIEVE_EXEC_RESOURCE_LIMIT, matching the existing behavior at the bytecode boundary. This is a minimal safety net ahead of switching the matchers to algorithms that do not require it. Gbp-Pq: Name CVE-2026-40016.patch --- pigeonhole/src/lib-sieve/mcht-contains.c | 21 ++++++++ pigeonhole/src/lib-sieve/mcht-matches.c | 55 ++++++++++++++++++-- pigeonhole/src/lib-sieve/sieve-interpreter.c | 19 +++++++ pigeonhole/src/lib-sieve/sieve-interpreter.h | 12 +++++ 4 files changed, 103 insertions(+), 4 deletions(-) diff --git a/pigeonhole/src/lib-sieve/mcht-contains.c b/pigeonhole/src/lib-sieve/mcht-contains.c index a9b3190..b077351 100644 --- a/pigeonhole/src/lib-sieve/mcht-contains.c +++ b/pigeonhole/src/lib-sieve/mcht-contains.c @@ -8,6 +8,7 @@ #include "sieve-match-types.h" #include "sieve-comparators.h" +#include "sieve-interpreter.h" #include "sieve-match.h" #include @@ -38,7 +39,14 @@ const struct sieve_match_type_def contains_match_type = { /* FIXME: Naive substring match implementation. Should switch to more * efficient algorithm if large values need to be searched (e.g. message body). + * + * The inner loop polls the interpreter CPU time limit periodically so that a + * single O(N*M) match on a large value cannot run for many times the + * configured sieve_max_cpu_time (which is otherwise only checked between + * bytecode operations). */ +#define SIEVE_CONTAINS_CPU_CHECK_INTERVAL 4096 + static int mcht_contains_match_key (struct sieve_match_context *mctx, const char *val, size_t val_size, const char *key, size_t key_size) @@ -48,6 +56,7 @@ static int mcht_contains_match_key const char *kend = (const char *) key + key_size; const char *vp = val; const char *kp = key; + unsigned int counter = 0; if ( val_size == 0 ) return ( key_size == 0 ? 1 : 0 ); @@ -58,6 +67,18 @@ static int mcht_contains_match_key while ( (vp < vend) && (kp < kend) ) { if ( !cmp->def->char_match(cmp, &vp, vend, &kp, kend) ) vp++; + + if ( ++counter >= SIEVE_CONTAINS_CPU_CHECK_INTERVAL ) { + counter = 0; + if ( sieve_runtime_cpu_limit_exceeded(mctx->runenv) ) { + sieve_runtime_error( + mctx->runenv, NULL, + "execution exceeded CPU time limit"); + mctx->exec_status = + SIEVE_EXEC_RESOURCE_LIMIT; + return -1; + } + } } return ( kp == kend ? 1 : 0 ); diff --git a/pigeonhole/src/lib-sieve/mcht-matches.c b/pigeonhole/src/lib-sieve/mcht-matches.c index 050fce9..3ddf769 100644 --- a/pigeonhole/src/lib-sieve/mcht-matches.c +++ b/pigeonhole/src/lib-sieve/mcht-matches.c @@ -9,6 +9,7 @@ #include "sieve-match-types.h" #include "sieve-comparators.h" +#include "sieve-interpreter.h" #include "sieve-match.h" #include @@ -46,16 +47,38 @@ const struct sieve_match_type_def matches_match_type = { #endif /* FIXME: Naive implementation, substitute this with dovecot src/lib/str-find.c + * + * The inner loop polls the interpreter CPU time limit periodically so that a + * single O(N*M) search on a large value cannot run for many times the + * configured sieve_max_cpu_time. Returns 1 on match, 0 on exhaustion, or -1 + * when the CPU time limit was exceeded (mctx->exec_status is set). */ -static inline bool _string_find(const struct sieve_comparator *cmp, - const char **valp, const char *vend, const char **keyp, const char *kend) +#define SIEVE_MATCHES_CPU_CHECK_INTERVAL 4096 + +static int +_string_find(struct sieve_match_context *mctx, + const struct sieve_comparator *cmp, + const char **valp, const char *vend, + const char **keyp, const char *kend, + unsigned int *counter) { while ( (*valp < vend) && (*keyp < kend) ) { if ( !cmp->def->char_match(cmp, valp, vend, keyp, kend) ) (*valp)++; + if (++(*counter) >= SIEVE_MATCHES_CPU_CHECK_INTERVAL) { + *counter = 0; + if (sieve_runtime_cpu_limit_exceeded(mctx->runenv)) { + sieve_runtime_error( + mctx->runenv, NULL, + "execution exceeded CPU time limit"); + mctx->exec_status = + SIEVE_EXEC_RESOURCE_LIMIT; + return -1; + } + } } - return (*keyp == kend); + return (*keyp == kend ? 1 : 0); } static char _scan_key_section @@ -93,6 +116,7 @@ static int mcht_matches_match_key char wcard = '\0'; /* Current wildcard */ char next_wcard = '\0'; /* Next widlcard */ unsigned int key_offset = 0; + unsigned int counter = 0; if ( cmp->def == NULL || cmp->def->char_match == NULL ) return 0; @@ -134,6 +158,19 @@ static int mcht_matches_match_key while (kp < kend && vp < vend ) { const char *needle, *nend; + if (++counter >= SIEVE_MATCHES_CPU_CHECK_INTERVAL) { + counter = 0; + if (sieve_runtime_cpu_limit_exceeded(mctx->runenv)) { + sieve_runtime_error( + mctx->runenv, NULL, + "execution exceeded CPU time limit"); + mctx->exec_status = + SIEVE_EXEC_RESOURCE_LIMIT; + sieve_match_values_abort(&mvalues); + return -1; + } + } + if ( !backtrack ) { /* Search the next '*' wildcard in the key string */ @@ -268,10 +305,20 @@ static int mcht_matches_match_key /* Match may happen at any offset (>= key offset): find substring */ vp += key_offset; - if ( (vp >= vend) || !_string_find(cmp, &vp, vend, &needle, nend) ) { + if (vp >= vend) { debug_printf(" failed to find needle at an offset\n"); break; } + int fres = _string_find(mctx, cmp, &vp, vend, + &needle, nend, &counter); + if (fres < 0) { + sieve_match_values_abort(&mvalues); + return -1; + } + if (fres == 0) { + debug_printf(" failed to find needle at an offset\n"); + break; + } prv = vp - str_len(section); prk = kp; diff --git a/pigeonhole/src/lib-sieve/sieve-interpreter.c b/pigeonhole/src/lib-sieve/sieve-interpreter.c index 67a3286..353be4d 100644 --- a/pigeonhole/src/lib-sieve/sieve-interpreter.c +++ b/pigeonhole/src/lib-sieve/sieve-interpreter.c @@ -85,6 +85,13 @@ struct sieve_interpreter { struct sieve_runtime_trace trace; struct sieve_resource_usage rusage; + /* CPU time limit for the current sieve_interpreter_continue() call; + NULL when no limit is configured or not currently executing. Exposed + via sieve_runtime_cpu_limit_exceeded() so long-running runtime code + can enforce the limit without waiting for the next bytecode + boundary. */ + struct cpu_limit *climit; + /* Current operation */ struct sieve_operation oprtn; @@ -362,6 +369,15 @@ sieve_interpreter_svinst(struct sieve_interpreter *interp) return interp->runenv.exec_env->svinst; } +bool sieve_runtime_cpu_limit_exceeded(const struct sieve_runtime_env *renv) +{ + struct sieve_interpreter *interp = renv->interp; + + if (interp->climit == NULL) + return FALSE; + return cpu_limit_exceeded(interp->climit); +} + /* Do not use this function for normal sieve extensions. This is intended for * the testsuite only. */ @@ -939,6 +955,7 @@ int sieve_interpreter_continue(struct sieve_interpreter *interp, climit = cpu_limit_init(svinst->set->max_cpu_time, CPU_LIMIT_TYPE_USER); } + interp->climit = climit; while (ret == SIEVE_EXEC_OK && !interp->interrupted && *address < sieve_binary_block_get_size(renv->sblock)) { @@ -959,6 +976,8 @@ int sieve_interpreter_continue(struct sieve_interpreter *interp, ret = sieve_interpreter_operation_execute(interp); } + interp->climit = NULL; + if (climit != NULL) { sieve_resource_usage_init(&rusage); rusage.cpu_time_msecs = diff --git a/pigeonhole/src/lib-sieve/sieve-interpreter.h b/pigeonhole/src/lib-sieve/sieve-interpreter.h index ec38029..e147ba3 100644 --- a/pigeonhole/src/lib-sieve/sieve-interpreter.h +++ b/pigeonhole/src/lib-sieve/sieve-interpreter.h @@ -164,6 +164,18 @@ int sieve_interpreter_start(struct sieve_interpreter *interp, int sieve_interpreter_run(struct sieve_interpreter *interp, struct sieve_result *result); +/* + * CPU limit + */ + +/* Returns TRUE if the current interpreter execution has exceeded its CPU + time limit (sieve_max_cpu_time). Callable from within long-running runtime + code (e.g. matcher inner loops) so that limit enforcement is not deferred + until the next bytecode boundary. Returns FALSE if no limit is active or + no execution is currently in progress. Cheap: does not call getrusage() + on each invocation. */ +bool sieve_runtime_cpu_limit_exceeded(const struct sieve_runtime_env *renv); + /* * Error handling */ -- 2.30.2