Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit54b116d

Browse files
committed
Add recursion depth protections to regular expression matching.
Some of the functions in regex compilation and execution recurse, andtherefore could in principle be driven to stack overflow. The Tcl crewhas seen this happen in practice in duptraverse(), though their fix wasto put in a hard-wired limit on the number of recursive levels, which isnot too appetizing --- fortunately, we have enough infrastructure to checkthe actually available stack. Greg Stark has also seen it in other placeswhile fuzz testing on a machine with limited stack space. Let's put guardsin 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 throwingsuch an error. Fortunately that's not difficult.
1 parent2a88782 commit54b116d

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
structarc*a;
703705
structstate*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
structarc*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
structarc*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 willbea lot less than that.
1370+
* the NFA ... but that could stillbeenough to cause trouble.
13461371
*/
13471372
staticstructstate*
1348-
emptyreachable(structstate*s,structstate*lastfound)
1373+
emptyreachable(structnfa*nfa,
1374+
structstate*s,
1375+
structstate*lastfound)
13491376
{
13501377
structarc*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+
returnlastfound;
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
returnlastfound;
13601394
}
@@ -1433,19 +1467,22 @@ cleanup(struct nfa * nfa)
14331467
structstate*nexts;
14341468
intn;
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, (structstate*)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
structarc*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
structarc*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
structarc*a;
15031554
structarc*aa;
15041555

1556+
if (NISERR())
1557+
return0;
1558+
15051559
if (nfa->pre->outs==NULL)
15061560
returnREG_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 intnewlacon(struct vars *, struct state *, struct state *, int);
7070
staticvoidfreelacons(structsubre*,int);
7171
staticvoidrfree(regex_t*);
7272
staticintrcancelrequested(void);
73+
staticintrstacktoodeep(void);
7374

7475
#ifdefREG_DEBUG
7576
staticvoiddump(regex_t*,FILE*);
@@ -152,7 +153,7 @@ static intpush(struct nfa *, struct arc *);
152153
#defineCOMPATIBLE3/* compatible but not satisfied yet */
153154
staticintcombine(structarc*,structarc*);
154155
staticvoidfixempties(structnfa*,FILE*);
155-
staticstructstate*emptyreachable(structstate*,structstate*);
156+
staticstructstate*emptyreachable(structnfa*,structstate*,structstate*);
156157
staticvoidreplaceempty(structnfa*,structstate*,structstate*);
157158
staticvoidcleanup(structnfa*);
158159
staticvoidmarkreachable(structnfa*,structstate*,structstate*,structstate*);
@@ -277,7 +278,8 @@ struct vars
277278
/* static function list */
278279
staticstructfnsfunctions= {
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
structsubre*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+
returnNULL;
1615+
}
1616+
16051617
if (ret!=NULL)
16061618
v->treefree=ret->left;
16071619
else
@@ -1914,6 +1926,22 @@ rcancelrequested(void)
19141926
returnInterruptPending&& (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+
staticint
1940+
rstacktoodeep(void)
1941+
{
1942+
returnstack_is_too_deep();
1943+
}
1944+
19171945
#ifdefREG_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
structsmalldfasd;
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+
return0;
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
returnREG_CANCEL;
749+
/* ... and stack overrun */
750+
if (STACK_TOO_DEEP(v->re))
751+
returnREG_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
charstack_top_loc;
31173133
longstack_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
externpg_stack_base_tset_stack_base(void);
262262
externvoidrestore_stack_base(pg_stack_base_tbase);
263263
externvoidcheck_stack_depth(void);
264+
externboolstack_is_too_deep(void);
264265

265266
/* in tcop/utility.c */
266267
externvoidPreventCommandIfReadOnly(constchar*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
voidFUNCPTR(free, (regex_t*));
406406
intFUNCPTR(cancel_requested, (void));
407+
intFUNCPTR(stack_too_deep, (void));
407408
};
408409

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

413+
#defineSTACK_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)
[8]ページ先頭
©2009-2025 Movatter.jp