Skip to content

Commit 54b116d

Browse files
tglsfdctglsfdc
committed
Add recursion depth protections to regular expression matching.
Some of the functions in regex compilation and execution recurse, and therefore could in principle be driven to stack overflow. The Tcl crew has seen this happen in practice in duptraverse(), though their fix was to put in a hard-wired limit on the number of recursive levels, which is not too appetizing --- fortunately, we have enough infrastructure to check the actually available stack. Greg Stark has also seen it in other places while fuzz testing on a machine with limited stack space. Let's put guards in to prevent crashes in all these places. Since the regex code would leak memory if we simply threw elog(ERROR), we have to introduce an API that checks for stack depth without throwing such an error. Fortunately that's not difficult.
1 parent 2a88782 commit 54b116d

File tree

7 files changed

+128
-25
lines changed

7 files changed

+128
-25
lines changed

‎src/backend/regex/regc_nfa.c

Lines changed: 61 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -683,6 +683,8 @@ delsub(struct nfa * nfa,
683683
rp->tmp = rp; /* mark end */
684684

685685
deltraverse(nfa, lp, lp);
686+
if (NISERR())
687+
return; /* asserts might not hold after failure */
686688
assert(lp->nouts == 0 && rp->nins == 0); /* did the job */
687689
assert(lp->no != FREESTATE && rp->no != FREESTATE); /* no more */
688690

@@ -702,6 +704,13 @@ deltraverse(struct nfa * nfa,
702704
struct arc *a;
703705
struct state *to;
704706

707+
/* Since this is recursive, it could be driven to stack overflow */
708+
if (STACK_TOO_DEEP(nfa->v->re))
709+
{
710+
NERR(REG_ETOOBIG);
711+
return;
712+
}
713+
705714
if (s->nouts == 0)
706715
return; /* nothing to do */
707716
if (s->tmp != NULL)
@@ -713,6 +722,8 @@ deltraverse(struct nfa * nfa,
713722
{
714723
to = a->to;
715724
deltraverse(nfa, leftend, to);
725+
if (NISERR())
726+
return; /* asserts might not hold after failure */
716727
assert(to->nouts == 0 || to->tmp != NULL);
717728
freearc(nfa, a);
718729
if (to->nins == 0 && to->tmp == NULL)
@@ -767,6 +778,13 @@ duptraverse(struct nfa * nfa,
767778
{
768779
struct arc *a;
769780

781+
/* Since this is recursive, it could be driven to stack overflow */
782+
if (STACK_TOO_DEEP(nfa->v->re))
783+
{
784+
NERR(REG_ETOOBIG);
785+
return;
786+
}
787+
770788
if (s->tmp != NULL)
771789
return; /* already done */
772790

@@ -796,6 +814,13 @@ cleartraverse(struct nfa * nfa,
796814
{
797815
struct arc *a;
798816

817+
/* Since this is recursive, it could be driven to stack overflow */
818+
if (STACK_TOO_DEEP(nfa->v->re))
819+
{
820+
NERR(REG_ETOOBIG);
821+
return;
822+
}
823+
799824
if (s->tmp == NULL)
800825
return;
801826
s->tmp = NULL;
@@ -1284,7 +1309,7 @@ fixempties(struct nfa * nfa,
12841309
*/
12851310
for (s = nfa->states; s != NULL && !NISERR(); s = s->next)
12861311
{
1287-
for (s2 = emptyreachable(s, s); s2 != s && !NISERR(); s2 = nexts)
1312+
for (s2 = emptyreachable(nfa, s, s); s2 != s && !NISERR(); s2 = nexts)
12881313
{
12891314
/*
12901315
* If s2 is doomed, we decide that (1) we will always push arcs
@@ -1342,19 +1367,28 @@ fixempties(struct nfa * nfa,
13421367
*
13431368
* The maximum recursion depth here is equal to the length of the longest
13441369
* loop-free chain of EMPTY arcs, which is surely no more than the size of
1345-
* the NFA, and in practice will be a lot less than that.
1370+
* the NFA ... but that could still be enough to cause trouble.
13461371
*/
13471372
static struct state *
1348-
emptyreachable(struct state * s, struct state * lastfound)
1373+
emptyreachable(struct nfa * nfa,
1374+
struct state * s,
1375+
struct state * lastfound)
13491376
{
13501377
struct arc *a;
13511378

1379+
/* Since this is recursive, it could be driven to stack overflow */
1380+
if (STACK_TOO_DEEP(nfa->v->re))
1381+
{
1382+
NERR(REG_ETOOBIG);
1383+
return lastfound;
1384+
}
1385+
13521386
s->tmp = lastfound;
13531387
lastfound = s;
13541388
for (a = s->outs; a != NULL; a = a->outchain)
13551389
{
13561390
if (a->type == EMPTY && a->to->tmp == NULL)
1357-
lastfound = emptyreachable(a->to, lastfound);
1391+
lastfound = emptyreachable(nfa, a->to, lastfound);
13581392
}
13591393
return lastfound;
13601394
}
@@ -1433,19 +1467,22 @@ cleanup(struct nfa * nfa)
14331467
struct state *nexts;
14341468
int n;
14351469

1470+
if (NISERR())
1471+
return;
1472+
14361473
/* clear out unreachable or dead-end states */
14371474
/* use pre to mark reachable, then post to mark can-reach-post */
14381475
markreachable(nfa, nfa->pre, (struct state *) NULL, nfa->pre);
14391476
markcanreach(nfa, nfa->post, nfa->pre, nfa->post);
1440-
for (s = nfa->states; s != NULL; s = nexts)
1477+
for (s = nfa->states; s != NULL && !NISERR(); s = nexts)
14411478
{
14421479
nexts = s->next;
14431480
if (s->tmp != nfa->post && !s->flag)
14441481
dropstate(nfa, s);
14451482
}
1446-
assert(nfa->post->nins == 0 || nfa->post->tmp == nfa->post);
1483+
assert(NISERR() || nfa->post->nins == 0 || nfa->post->tmp == nfa->post);
14471484
cleartraverse(nfa, nfa->pre);
1448-
assert(nfa->post->nins == 0 || nfa->post->tmp == NULL);
1485+
assert(NISERR() || nfa->post->nins == 0 || nfa->post->tmp == NULL);
14491486
/* the nins==0 (final unreachable) case will be caught later */
14501487

14511488
/* renumber surviving states */
@@ -1466,6 +1503,13 @@ markreachable(struct nfa * nfa,
14661503
{
14671504
struct arc *a;
14681505

1506+
/* Since this is recursive, it could be driven to stack overflow */
1507+
if (STACK_TOO_DEEP(nfa->v->re))
1508+
{
1509+
NERR(REG_ETOOBIG);
1510+
return;
1511+
}
1512+
14691513
if (s->tmp != okay)
14701514
return;
14711515
s->tmp = mark;
@@ -1485,6 +1529,13 @@ markcanreach(struct nfa * nfa,
14851529
{
14861530
struct arc *a;
14871531

1532+
/* Since this is recursive, it could be driven to stack overflow */
1533+
if (STACK_TOO_DEEP(nfa->v->re))
1534+
{
1535+
NERR(REG_ETOOBIG);
1536+
return;
1537+
}
1538+
14881539
if (s->tmp != okay)
14891540
return;
14901541
s->tmp = mark;
@@ -1502,6 +1553,9 @@ analyze(struct nfa * nfa)
15021553
struct arc *a;
15031554
struct arc *aa;
15041555

1556+
if (NISERR())
1557+
return 0;
1558+
15051559
if (nfa->pre->outs == NULL)
15061560
return REG_UIMPOSSIBLE;
15071561
for (a = nfa->pre->outs; a != NULL; a = a->outchain)

‎src/backend/regex/regcomp.c

Lines changed: 31 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -34,7 +34,7 @@
3434

3535
#include "regex/regguts.h"
3636

37-
#include "miscadmin.h" /* needed by rcancelrequested() */
37+
#include "miscadmin.h" /* needed by rcancelrequested/rstacktoodeep */
3838

3939
/*
4040
* forward declarations, up here so forward datatypes etc. are defined early
@@ -70,6 +70,7 @@ static int newlacon(struct vars *, struct state *, struct state *, int);
7070
static void freelacons(struct subre *, int);
7171
static void rfree(regex_t *);
7272
static int rcancelrequested(void);
73+
static int rstacktoodeep(void);
7374

7475
#ifdef REG_DEBUG
7576
static void dump(regex_t *, FILE *);
@@ -152,7 +153,7 @@ static int push(struct nfa *, struct arc *);
152153
#define COMPATIBLE 3 /* compatible but not satisfied yet */
153154
static int combine(struct arc *, struct arc *);
154155
static void fixempties(struct nfa *, FILE *);
155-
static struct state *emptyreachable(struct state *, struct state *);
156+
static struct state *emptyreachable(struct nfa *, struct state *, struct state *);
156157
static void replaceempty(struct nfa *, struct state *, struct state *);
157158
static void cleanup(struct nfa *);
158159
static void markreachable(struct nfa *, struct state *, struct state *, struct state *);
@@ -277,7 +278,8 @@ struct vars
277278
/* static function list */
278279
static struct fns functions = {
279280
rfree, /* regfree insides */
280-
rcancelrequested /* check for cancel request */
281+
rcancelrequested, /* check for cancel request */
282+
rstacktoodeep /* check for stack getting dangerously deep */
281283
};
282284

283285

@@ -1602,6 +1604,16 @@ subre(struct vars * v,
16021604
{
16031605
struct subre *ret = v->treefree;
16041606

1607+
/*
1608+
* Checking for stack overflow here is sufficient to protect parse() and
1609+
* its recursive subroutines.
1610+
*/
1611+
if (STACK_TOO_DEEP(v->re))
1612+
{
1613+
ERR(REG_ETOOBIG);
1614+
return NULL;
1615+
}
1616+
16051617
if (ret != NULL)
16061618
v->treefree = ret->left;
16071619
else
@@ -1914,6 +1926,22 @@ rcancelrequested(void)
19141926
return InterruptPending && (QueryCancelPending || ProcDiePending);
19151927
}
19161928

1929+
/*
1930+
* rstacktoodeep - check for stack getting dangerously deep
1931+
*
1932+
* Return nonzero to fail the operation with error code REG_ETOOBIG,
1933+
* zero to keep going
1934+
*
1935+
* The current implementation is Postgres-specific. If we ever get around
1936+
* to splitting the regex code out as a standalone library, there will need
1937+
* to be some API to let applications define a callback function for this.
1938+
*/
1939+
static int
1940+
rstacktoodeep(void)
1941+
{
1942+
return stack_is_too_deep();
1943+
}
1944+
19171945
#ifdef REG_DEBUG
19181946

19191947
/*

‎src/backend/regex/rege_dfa.c

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -628,6 +628,13 @@ lacon(struct vars * v,
628628
struct smalldfa sd;
629629
chr *end;
630630

631+
/* Since this is recursive, it could be driven to stack overflow */
632+
if (STACK_TOO_DEEP(v->re))
633+
{
634+
ERR(REG_ETOOBIG);
635+
return 0;
636+
}
637+
631638
n = co - pcnfa->ncolors;
632639
assert(n < v->g->nlacons && v->g->lacons != NULL);
633640
FDEBUG(("=== testing lacon %d\n", n));

‎src/backend/regex/regexec.c

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -746,6 +746,9 @@ cdissect(struct vars * v,
746746
/* handy place to check for operation cancel */
747747
if (CANCEL_REQUESTED(v->re))
748748
return REG_CANCEL;
749+
/* ... and stack overrun */
750+
if (STACK_TOO_DEEP(v->re))
751+
return REG_ETOOBIG;
749752

750753
switch (t->op)
751754
{

‎src/backend/tcop/postgres.c

Lines changed: 21 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -3103,15 +3103,31 @@ restore_stack_base(pg_stack_base_t base)
31033103
}
31043104

31053105
/*
3106-
* check_stack_depth: check for excessively deep recursion
3106+
* check_stack_depth/stack_is_too_deep: check for excessively deep recursion
31073107
*
31083108
* This should be called someplace in any recursive routine that might possibly
31093109
* recurse deep enough to overflow the stack. Most Unixen treat stack
31103110
* overflow as an unrecoverable SIGSEGV, so we want to error out ourselves
31113111
* before hitting the hardware limit.
3112+
*
3113+
* check_stack_depth() just throws an error summarily. stack_is_too_deep()
3114+
* can be used by code that wants to handle the error condition itself.
31123115
*/
31133116
void
31143117
check_stack_depth(void)
3118+
{
3119+
if (stack_is_too_deep())
3120+
{
3121+
ereport(ERROR,
3122+
(errcode(ERRCODE_STATEMENT_TOO_COMPLEX),
3123+
errmsg("stack depth limit exceeded"),
3124+
errhint("Increase the configuration parameter \"max_stack_depth\", "
3125+
"after ensuring the platform's stack depth limit is adequate.")));
3126+
}
3127+
}
3128+
3129+
bool
3130+
stack_is_too_deep(void)
31153131
{
31163132
char stack_top_loc;
31173133
long stack_depth;
@@ -3137,13 +3153,7 @@ check_stack_depth(void)
31373153
*/
31383154
if (stack_depth > max_stack_depth_bytes &&
31393155
stack_base_ptr != NULL)
3140-
{
3141-
ereport(ERROR,
3142-
(errcode(ERRCODE_STATEMENT_TOO_COMPLEX),
3143-
errmsg("stack depth limit exceeded"),
3144-
errhint("Increase the configuration parameter \"max_stack_depth\", "
3145-
"after ensuring the platform's stack depth limit is adequate.")));
3146-
}
3156+
return true;
31473157

31483158
/*
31493159
* On IA64 there is a separate "register" stack that requires its own
@@ -3158,14 +3168,10 @@ check_stack_depth(void)
31583168

31593169
if (stack_depth > max_stack_depth_bytes &&
31603170
register_stack_base_ptr != NULL)
3161-
{
3162-
ereport(ERROR,
3163-
(errcode(ERRCODE_STATEMENT_TOO_COMPLEX),
3164-
errmsg("stack depth limit exceeded"),
3165-
errhint("Increase the configuration parameter \"max_stack_depth\", "
3166-
"after ensuring the platform's stack depth limit is adequate.")));
3167-
}
3171+
return true;
31683172
#endif /* IA64 */
3173+
3174+
return false;
31693175
}
31703176

31713177
/* GUC assign hook for max_stack_depth */

‎src/include/miscadmin.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -261,6 +261,7 @@ typedef char *pg_stack_base_t;
261261
extern pg_stack_base_t set_stack_base(void);
262262
extern void restore_stack_base(pg_stack_base_t base);
263263
extern void check_stack_depth(void);
264+
extern bool stack_is_too_deep(void);
264265

265266
/* in tcop/utility.c */
266267
extern void PreventCommandIfReadOnly(const char *cmdname);

‎src/include/regex/regguts.h

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -404,11 +404,15 @@ struct fns
404404
{
405405
void FUNCPTR(free, (regex_t *));
406406
int FUNCPTR(cancel_requested, (void));
407+
int FUNCPTR(stack_too_deep, (void));
407408
};
408409

409410
#define CANCEL_REQUESTED(re) \
410411
((*((struct fns *) (re)->re_fns)->cancel_requested) ())
411412

413+
#define STACK_TOO_DEEP(re) \
414+
((*((struct fns *) (re)->re_fns)->stack_too_deep) ())
415+
412416

413417
/*
414418
* the insides of a regex_t, hidden behind a void *

0 commit comments

Comments
 (0)