From b62c26d999c07f1cfa9287a4e478d2528c67c0e3 Mon Sep 17 00:00:00 2001 From: drh <> Date: Fri, 26 Sep 2025 15:38:52 +0000 Subject: [PATCH] Limit the complexity of a REGEXP pattern using SQLITE_LIMIT_LIKE_PATTERN_LENGTH FossilOrigin-Name: 869c968569b09d05a5b7d587d8fddb3b4611daf7467dc157701e5dc6c9608606 --- ext/misc/regexp.c | 47 +++++++++++++++++++++++++++++++++-------------- manifest | 14 +++++++------- manifest.uuid | 2 +- test/regexp2.test | 8 ++++---- 4 files changed, 45 insertions(+), 26 deletions(-) diff --git a/ext/misc/regexp.c b/ext/misc/regexp.c index cea94df144..92343bf03b 100644 --- a/ext/misc/regexp.c +++ b/ext/misc/regexp.c @@ -26,7 +26,7 @@ ** X* zero or more occurrences of X ** X+ one or more occurrences of X ** X? zero or one occurrences of X -** X{p,q} between p and q occurrences of X, 0 <= p,q <= 999 +** X{p,q} between p and q occurrences of X ** (X) match X ** X|Y X or Y ** ^X X occurring at the beginning of the string @@ -56,16 +56,16 @@ ** regular expression in the O(N*M) performance bound is computed after ** this expansion. ** -** To help prevent DoS attacks, the values of p and q in the "{p,q}" syntax -** are limited to SQLITE_MAX_REGEXP_REPEAT, default 999. +** To help prevent DoS attacks, the size of the NFA is limit to +** SQLITE_MAX_REGEXP states, default 9999. */ #include #include #include "sqlite3ext.h" SQLITE_EXTENSION_INIT1 -#ifndef SQLITE_MAX_REGEXP_REPEAT -# define SQLITE_MAX_REGEXP_REPEAT 999 +#ifndef SQLITE_MAX_REGEXP +# define SQLITE_MAX_REGEXP 9999 #endif /* @@ -165,6 +165,7 @@ struct ReCompiled { int nInit; /* Number of bytes in zInit */ unsigned nState; /* Number of entries in aOp[] and aArg[] */ unsigned nAlloc; /* Slots allocated for aOp[] and aArg[] */ + unsigned mxAlloc; /* Complexity limit */ }; /* Add a state to the given state set if it is not already there */ @@ -382,11 +383,12 @@ re_match_end: static int re_resize(ReCompiled *p, int N){ char *aOp; int *aArg; + if( N>p->mxAlloc ){ p->zErr = "REGEXP pattern too big"; return 1; } aOp = sqlite3_realloc64(p->aOp, N*sizeof(p->aOp[0])); - if( aOp==0 ) return 1; + if( aOp==0 ){ p->zErr = "out of memory"; return 1; } p->aOp = aOp; aArg = sqlite3_realloc64(p->aArg, N*sizeof(p->aArg[0])); - if( aArg==0 ) return 1; + if( aArg==0 ){ p->zErr = "out of memory"; return 1; } p->aArg = aArg; p->nAlloc = N; return 0; @@ -575,7 +577,7 @@ static const char *re_subcompile_string(ReCompiled *p){ if( iPrev<0 ) return "'{m,n}' without operand"; while( (c=rePeek(p))>='0' && c<='9' ){ m = m*10 + c - '0'; - if( m>SQLITE_MAX_REGEXP_REPEAT ) return "integer too large"; + if( m*2>p->mxAlloc ) return "REGEXP pattern too big"; p->sIn.i++; } n = m; @@ -584,7 +586,7 @@ static const char *re_subcompile_string(ReCompiled *p){ n = 0; while( (c=rePeek(p))>='0' && c<='9' ){ n = n*10 + c-'0'; - if( n>SQLITE_MAX_REGEXP_REPEAT ) return "integer too large"; + if( n*2>p->mxAlloc ) return "REGEXP pattern too big"; p->sIn.i++; } } @@ -605,7 +607,7 @@ static const char *re_subcompile_string(ReCompiled *p){ re_copy(p, iPrev, sz); } if( n==0 && m>0 ){ - re_append(p, RE_OP_FORK, -sz); + re_append(p, RE_OP_FORK, -(int)sz); } break; } @@ -686,7 +688,12 @@ static void re_free(void *p){ ** compiled regular expression in *ppRe. Return NULL on success or an ** error message if something goes wrong. */ -static const char *re_compile(ReCompiled **ppRe, const char *zIn, int noCase){ +static const char *re_compile( + ReCompiled **ppRe, /* OUT: write compiled NFA here */ + const char *zIn, /* Input regular expression */ + int mxRe, /* Complexity limit */ + int noCase /* True for caseless comparisons */ +){ ReCompiled *pRe; const char *zErr; int i, j; @@ -698,9 +705,11 @@ static const char *re_compile(ReCompiled **ppRe, const char *zIn, int noCase){ } memset(pRe, 0, sizeof(*pRe)); pRe->xNextChar = noCase ? re_next_char_nocase : re_next_char; + pRe->mxAlloc = mxRe; if( re_resize(pRe, 30) ){ + zErr = pRe->zErr; re_free(pRe); - return "out of memory"; + return zErr; } if( zIn[0]=='^' ){ zIn++; @@ -753,6 +762,14 @@ static const char *re_compile(ReCompiled **ppRe, const char *zIn, int noCase){ return pRe->zErr; } +/* +** Compute a reasonable limit on the length of the REGEXP NFA. +*/ +static int re_maxlen(sqlite3_context *context){ + sqlite3 *db = sqlite3_context_db_handle(context); + return 75 + sqlite3_limit(db, SQLITE_LIMIT_LIKE_PATTERN_LENGTH,-1)/2; +} + /* ** Implementation of the regexp() SQL function. This function implements ** the build-in REGEXP operator. The first argument to the function is the @@ -778,7 +795,8 @@ static void re_sql_func( if( pRe==0 ){ zPattern = (const char*)sqlite3_value_text(argv[0]); if( zPattern==0 ) return; - zErr = re_compile(&pRe, zPattern, sqlite3_user_data(context)!=0); + zErr = re_compile(&pRe, zPattern, re_maxlen(context), + sqlite3_user_data(context)!=0); if( zErr ){ re_free(pRe); sqlite3_result_error(context, zErr, -1); @@ -823,7 +841,8 @@ static void re_bytecode_func( zPattern = (const char*)sqlite3_value_text(argv[0]); if( zPattern==0 ) return; - zErr = re_compile(&pRe, zPattern, sqlite3_user_data(context)!=0); + zErr = re_compile(&pRe, zPattern, re_maxlen(context), + sqlite3_user_data(context)!=0); if( zErr ){ re_free(pRe); sqlite3_result_error(context, zErr, -1); diff --git a/manifest b/manifest index 436da6ac63..12bcc57f0b 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C In\sthe\sregexp\sextension,\slimit\sthe\smaximum\svalue\sof\sintegers\sin\sthe\n"{p,q}"\ssyntax,\sas\sperformance\sof\sthe\sNFA\sused\sto\sdo\spattern\smatching\nis\slinear\sin\sthe\smaximum\ssuch\sinteger.\s\sThe\slimit\sis\sSQLITE_MAX_REGEXP_REPEAT\nwhich\sdefaults\sto\s999.\s\sThis\shelps\sto\sprevent\sDoS\sattacks\sin\ssystems\sthat\nmake\suse\sof\sthe\sregexp\sextension. -D 2025-09-26T13:14:20.156 +C Limit\sthe\scomplexity\sof\sa\sREGEXP\spattern\susing\sSQLITE_LIMIT_LIKE_PATTERN_LENGTH +D 2025-09-26T15:38:52.279 F .fossil-settings/binary-glob 61195414528fb3ea9693577e1980230d78a1f8b0a54c78cf1b9b24d0a409ed6a x F .fossil-settings/empty-dirs dbb81e8fc0401ac46a1491ab34a7f2c7c0452f2f06b54ebb845d024ca8283ef1 F .fossil-settings/ignore-glob 35175cdfcf539b2318cb04a9901442804be81cd677d8b889fcc9149c21f239ea @@ -389,7 +389,7 @@ F ext/misc/percentile.c 72e05a21db20a2fa85264b99515941f00ae698824c9db82d7edfbb16 F ext/misc/prefixes.c 82645f79229877afab08c8b08ca1e7fa31921280906b90a61c294e4f540cd2a6 F ext/misc/qpvtab.c fc189e127f68f791af90a487f4460ec91539a716daf45a0c357e963fd47cc06c F ext/misc/randomjson.c ef835fc64289e76ac4873b85fe12f9463a036168d7683cf2b773e36e6262c4ed -F ext/misc/regexp.c 8a762ed5d34a26f85fcaff687a405c38e85c541f5f489c964d99b5bc95aedbe1 +F ext/misc/regexp.c b92da686f6d6915887758803b30c33fdd628aab055bbf6e1075ae579186be626 F ext/misc/remember.c add730f0f7e7436cd15ea3fd6a90fd83c3f706ab44169f7f048438b7d6baa69c F ext/misc/rot13.c 51ac5f51e9d5fd811db58a9c23c628ad5f333c173f1fc53c8491a3603d38556c F ext/misc/scrub.c 2a44b0d44c69584c0580ad2553f6290a307a49df4668941d2812135bfb96a946 @@ -1520,7 +1520,7 @@ F test/rdonly.test 64e2696c322e3538df0b1ed624e21f9a23ed9ff8 F test/readonly.test 0d307c335b3421898cfe64a783a376138aa003849b6bff61ee2d21e805bc0051 F test/recover.test c76d05f33f0271fba0f0752170e03b0ab5952dc61dcea7ab3ba40df03c4c42de F test/regexp1.test 8f2a8bc1569666e29a4cee6c1a666cd224eb6d50e2470d1dc1df995170f3e0f1 -F test/regexp2.test 02ebe3cf5a06c5fcc40387d906875bafa1cdbe8d3289170a05e34bbb57dc2884 +F test/regexp2.test 64f9726b2ddc71aea06725fcad53231833d038d58b936d49083ace658b370a13 F test/reindex.test cd9d6021729910ece82267b4f5e1b5ac2911a7566c43b43c176a6a4732e2118d F test/reservebytes.test 6163640b5a5120c0dee6591481e673a0fa0bf0d12d4da7513bad692c1a49a162 F test/resetdb.test 54c06f18bc832ac6d6319e5ab23d5c8dd49fdbeec7c696d791682a8006bd5fc3 @@ -2169,8 +2169,8 @@ F tool/version-info.c 3b36468a90faf1bbd59c65fd0eb66522d9f941eedd364fabccd7227350 F tool/warnings-clang.sh bbf6a1e685e534c92ec2bfba5b1745f34fb6f0bc2a362850723a9ee87c1b31a7 F tool/warnings.sh 1ad0169b022b280bcaaf94a7fa231591be96b514230ab5c98fbf15cd7df842dd F tool/win/sqlite.vsix deb315d026cc8400325c5863eef847784a219a2f -P 36bc2514f70af5608aa20903d9c38b316603e2f78f2cbf4a20c7c79b60c5b8d5 -R 8d76d36b83ffa10f8973f107bc375552 +P 911c745f88c0ee8569e67bbcbbab034264f8c981b505aadac3ce7289486a1a68 +R 828f930d9062f970a087f3cd9db90d9c U drh -Z 3a7db3386aaa43ed8b2a45f636c561b9 +Z 512ef129556a7f8a07d748aea238fc85 # Remove this line to create a well-formed Fossil manifest. diff --git a/manifest.uuid b/manifest.uuid index 7e1b86a63e..65228ee353 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -911c745f88c0ee8569e67bbcbbab034264f8c981b505aadac3ce7289486a1a68 +869c968569b09d05a5b7d587d8fddb3b4611daf7467dc157701e5dc6c9608606 diff --git a/test/regexp2.test b/test/regexp2.test index f2643c4a5c..55ce59d05a 100644 --- a/test/regexp2.test +++ b/test/regexp2.test @@ -145,14 +145,14 @@ do_execsql_test 5.0 { SELECT 'abc' REGEXP 'a{1,999}bc'; } 1 do_catchsql_test 5.1 { - SELECT 'abc' REGEXP 'a{1,1000}bc'; -} {1 {integer too large}} + SELECT 'abc' REGEXP 'a{1,25000}bc'; +} {1 {REGEXP pattern too big}} do_execsql_test 5.2 { SELECT 'abc' REGEXP 'a{999}bc'; } 0 do_catchsql_test 5.3 { - SELECT 'abc' REGEXP 'a{1000}bc'; -} {1 {integer too large}} + SELECT 'abc' REGEXP 'a{25000}bc'; +} {1 {REGEXP pattern too big}} -- 2.47.3