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

Commit20c6277

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 parent51f2359 commit20c6277

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
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*);
@@ -279,7 +280,8 @@ struct vars
279280
/* static function list */
280281
staticconststructfnsfunctions= {
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

@@ -1626,6 +1628,16 @@ subre(struct vars * v,
16261628
{
16271629
structsubre*ret=v->treefree;
16281630

1631+
/*
1632+
* Checking for stack overflow here is sufficient to protect parse() and
1633+
* its recursive subroutines.
1634+
*/
1635+
if (STACK_TOO_DEEP(v->re))
1636+
{
1637+
ERR(REG_ETOOBIG);
1638+
returnNULL;
1639+
}
1640+
16291641
if (ret!=NULL)
16301642
v->treefree=ret->left;
16311643
else
@@ -1938,6 +1950,22 @@ rcancelrequested(void)
19381950
returnInterruptPending&& (QueryCancelPending||ProcDiePending);
19391951
}
19401952

1953+
/*
1954+
* rstacktoodeep - check for stack getting dangerously deep
1955+
*
1956+
* Return nonzero to fail the operation with error code REG_ETOOBIG,
1957+
* zero to keep going
1958+
*
1959+
* The current implementation is Postgres-specific. If we ever get around
1960+
* to splitting the regex code out as a standalone library, there will need
1961+
* to be some API to let applications define a callback function for this.
1962+
*/
1963+
staticint
1964+
rstacktoodeep(void)
1965+
{
1966+
returnstack_is_too_deep();
1967+
}
1968+
19411969
#ifdefREG_DEBUG
19421970

19431971
/*

‎src/backend/regex/rege_dfa.c

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

630+
/* Since this is recursive, it could be driven to stack overflow */
631+
if (STACK_TOO_DEEP(v->re))
632+
{
633+
ERR(REG_ETOOBIG);
634+
return0;
635+
}
636+
630637
n=co-pcnfa->ncolors;
631638
assert(n<v->g->nlacons&&v->g->lacons!=NULL);
632639
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
@@ -624,6 +624,9 @@ cdissect(struct vars * v,
624624
/* handy place to check for operation cancel */
625625
if (CANCEL_REQUESTED(v->re))
626626
returnREG_CANCEL;
627+
/* ... and stack overrun */
628+
if (STACK_TOO_DEEP(v->re))
629+
returnREG_ETOOBIG;
627630

628631
switch (t->op)
629632
{

‎src/backend/tcop/postgres.c

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

30803080
/*
3081-
* check_stack_depth: check for excessively deep recursion
3081+
* check_stack_depth/stack_is_too_deep: check for excessively deep recursion
30823082
*
30833083
* This should be called someplace in any recursive routine that might possibly
30843084
* recurse deep enough to overflow the stack. Most Unixen treat stack
30853085
* overflow as an unrecoverable SIGSEGV, so we want to error out ourselves
30863086
* before hitting the hardware limit.
3087+
*
3088+
* check_stack_depth() just throws an error summarily. stack_is_too_deep()
3089+
* can be used by code that wants to handle the error condition itself.
30873090
*/
30883091
void
30893092
check_stack_depth(void)
3093+
{
3094+
if (stack_is_too_deep())
3095+
{
3096+
ereport(ERROR,
3097+
(errcode(ERRCODE_STATEMENT_TOO_COMPLEX),
3098+
errmsg("stack depth limit exceeded"),
3099+
errhint("Increase the configuration parameter \"max_stack_depth\" (currently %dkB), "
3100+
"after ensuring the platform's stack depth limit is adequate.",
3101+
max_stack_depth)));
3102+
}
3103+
}
3104+
3105+
bool
3106+
stack_is_too_deep(void)
30903107
{
30913108
charstack_top_loc;
30923109
longstack_depth;
@@ -3112,14 +3129,7 @@ check_stack_depth(void)
31123129
*/
31133130
if (stack_depth>max_stack_depth_bytes&&
31143131
stack_base_ptr!=NULL)
3115-
{
3116-
ereport(ERROR,
3117-
(errcode(ERRCODE_STATEMENT_TOO_COMPLEX),
3118-
errmsg("stack depth limit exceeded"),
3119-
errhint("Increase the configuration parameter \"max_stack_depth\" (currently %dkB), "
3120-
"after ensuring the platform's stack depth limit is adequate.",
3121-
max_stack_depth)));
3122-
}
3132+
return true;
31233133

31243134
/*
31253135
* On IA64 there is a separate "register" stack that requires its own
@@ -3134,15 +3144,10 @@ check_stack_depth(void)
31343144

31353145
if (stack_depth>max_stack_depth_bytes&&
31363146
register_stack_base_ptr!=NULL)
3137-
{
3138-
ereport(ERROR,
3139-
(errcode(ERRCODE_STATEMENT_TOO_COMPLEX),
3140-
errmsg("stack depth limit exceeded"),
3141-
errhint("Increase the configuration parameter \"max_stack_depth\" (currently %dkB), "
3142-
"after ensuring the platform's stack depth limit is adequate.",
3143-
max_stack_depth)));
3144-
}
3147+
return true;
31453148
#endif/* IA64 */
3149+
3150+
return false;
31463151
}
31473152

31483153
/* 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
@@ -268,6 +268,7 @@ typedef char *pg_stack_base_t;
268268
externpg_stack_base_tset_stack_base(void);
269269
externvoidrestore_stack_base(pg_stack_base_tbase);
270270
externvoidcheck_stack_depth(void);
271+
externboolstack_is_too_deep(void);
271272

272273
/* in tcop/utility.c */
273274
externvoidPreventCommandIfReadOnly(constchar*cmdname);

‎src/include/regex/regguts.h

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -452,11 +452,15 @@ struct fns
452452
{
453453
voidFUNCPTR(free, (regex_t*));
454454
intFUNCPTR(cancel_requested, (void));
455+
intFUNCPTR(stack_too_deep, (void));
455456
};
456457

457458
#defineCANCEL_REQUESTED(re) \
458459
((*((struct fns *) (re)->re_fns)->cancel_requested) ())
459460

461+
#defineSTACK_TOO_DEEP(re)\
462+
((*((struct fns *) (re)->re_fns)->stack_too_deep) ())
463+
460464

461465
/*
462466
* the insides of a regex_t, hidden behind a void *

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp