8000 Add recursion depth protections to regular expression matching. · highb/postgres@e7de1bc · GitHub
[go: up one dir, main page]
Skip to content

Commit e7de1bc

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 6301549 commit e7de1bc

File tree

7 files changed

+129
-27
lines changed

7 files changed

+129
-27
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 *);
@@ -279,7 +280,8 @@ struct vars
279280
/* static function list */
280281
static struct fns functions = {
281282
rfree, /* regfree insides */
282-
rcancelrequested /* check for cancel request */
283+
rcancelrequested, /* check for cancel request */
284+
rstacktoodeep /* check for stack getting dangerously deep */
283285
};
284286

285287

@@ -1609,6 +1611,16 @@ subre(struct vars * v,
16091611
{
16101612
struct subre *ret = v->treefree;
16111613

1614+
/*
1615+
* Checking for stack overflow here is sufficient to protect parse() and
1616+
* its recursive subroutines.
1617+
*/
1618+
if (STACK_TOO_DEEP(v->re))
1619+
{
1620+
ERR(REG_ETOOBIG);
1621+
return NULL;
1622+
}
1623+
16121624
if (ret != NULL)
16131625
v->treefree = ret->left;
16141626
else
@@ -1921,6 +1933,22 @@ rcancelrequested(void)
19211933
return InterruptPending && (QueryCancelPending || ProcDiePending);
19221934
}
19231935

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

19261954
/*

‎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
@@ -749,6 +749,9 @@ cdissect(struct vars * v,
749749
/* handy place to check for operation cancel */
750750
if (CANCEL_REQUESTED(v->re))
751751
return REG_CANCEL;
752+
/* ... and stack overrun */
753+
if (STACK_TOO_DEEP(v->re))
754+
return REG_ETOOBIG;
752755

753756
switch (t->op)
754757
{

‎src/backend/tcop/postgres.c

Lines changed: 22 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -3092,15 +3092,32 @@ restore_stack_base(pg_stack_base_t base)
30923092
}
30933093

30943094
/*
3095-
* check_stack_depth: check for excessively deep recursion
3095+
* check_stack_depth/stack_is_too_deep: check for excessively deep recursion
30963096
*
30973097
* This should be called someplace in any recursive routine that might possibly
30983098
* recurse deep enough to overflow the stack. Most Unixen treat stack
30993099
* overflow as an unrecoverable SIGSEGV, so we want to error out ourselves
31003100
* before hitting the hardware limit.
3101+
*
3102+
* check_stack_depth() just throws an error summarily. stack_is_too_deep()
3103+
* can be used by code that wants to handle the error condition itself.
31013104
*/
31023105
void
31033106
check_stack_depth(void)
3107+
{
3108+
if (stack_is_too_deep())
3109+
{
3110+
ereport(ERROR,
3111+
(errcode(ERRCODE_STATEMENT_TOO_COMPLEX),
3112+
errmsg("stack depth limit exceeded"),
3113+
errhint("Increase the configuration parameter \"max_stack_depth\" (currently %dkB), "
3114+
"after ensuring the platform's stack depth limit is adequate.",
3115+
max_stack_depth)));
3116+
}
3117+
}
3118+
3119+
bool
3120+
stack_is_too_deep(void)
31043121
{
31053122
char stack_top_loc;
31063123
long stack_depth;
@@ -3126,14 +3143,7 @@ check_stack_depth(void)
31263143
*/
31273144
if (stack_depth > max_stack_depth_bytes &&
31283145
stack_base_ptr != NULL)
3129-
{
3130-
ereport(ERROR,
3131-
(errcode(ERRCODE_STATEMENT_TOO_COMPLEX),
3132-
errmsg("stack depth limit exceeded"),
3133-
errhint("Increase the configuration parameter \"max_stack_depth\" (currently %dkB), "
3134-
"after ensuring the platform's stack depth limit is adequate.",
3135-
max_stack_depth)));
3136-
}
3146+
return true;
31373147

31383148
/*
31393149
* On IA64 there is a separate "register" stack that requires its own
@@ -3148,15 +3158,10 @@ check_stack_depth(void)
31483158

31493159
if (stack_depth > max_stack_depth_bytes &&
31503160
register_stack_base_ptr != NULL)
3151-
{
3152-
ereport(ERROR,
3153-
(errcode(ERRCODE_STATEMENT_TOO_COMPLEX),
3154-
errmsg("stack depth limit exceeded"),
3155-
errhint("Increase the configuration parameter \"max_stack_depth\" (currently %dkB), "
3156-
"after ensuring the platform's stack depth limit is adequate.",
3157-
max_stack_depth)));
3158-
}
3161+
return true;
31593162
#endif /* IA64 */
3163+
3164+
return false;
31603165
}
31613166

31623167
/* GUC check hook for max_stack_depth */

‎src/include/miscadmin.h

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

266267
/* in tcop/utility.c */
267268
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)
0