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

Commit98f27aa

Browse files
committed
Fix assorted security-grade bugs in the regex engine. All of these problems
are shared with Tcl, since it's their code to begin with, and the patcheshave been copied from Tcl 8.5.0. Problems:CVE-2007-4769: Inadequate check on the range of backref numbers allowscrash due to out-of-bounds read.CVE-2007-4772: Infinite loop in regex optimizer for pattern '($|^)*'.CVE-2007-6067: Very slow optimizer cleanup for regex with a large NFArepresentation, as well as crash if we encounter an out-of-memory conditionduring NFA construction.Part of the response toCVE-2007-6067 is to put a limit on the number ofstates in the NFA representation of a regex. This seems needed even thoughthe within-the-code problems have been corrected, since otherwise the codecould try to use very large amounts of memory for a suitably-crafted regex,leading to potential DOS by driving the system into swap, activating a kernelOOM killer, etc.Although there are certainly plenty of ways to drive the system into effectiveDOS with poorly-written SQL queries, these problems seem worth treating assecurity issues because many applications might accept regex search patternsfrom untrustworthy sources.Thanks to Will Drewry of Google for reporting these problems. Patches by WillDrewry and Tom Lane.Security:CVE-2007-4769,CVE-2007-4772,CVE-2007-6067
1 parent8af31d5 commit98f27aa

File tree

6 files changed

+143
-21
lines changed

6 files changed

+143
-21
lines changed

‎src/backend/regex/regc_color.c

Lines changed: 15 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,7 @@
2828
* OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
2929
* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3030
*
31-
* $PostgreSQL: pgsql/src/backend/regex/regc_color.c,v 1.7 2007/11/15 21:14:37 momjian Exp $
31+
* $PostgreSQL: pgsql/src/backend/regex/regc_color.c,v 1.8 2008/01/03 20:47:55 tgl Exp $
3232
*
3333
*
3434
* Note that there are some incestuous relationships between this code and
@@ -569,12 +569,9 @@ okcolors(struct nfa * nfa,
569569
while ((a=cd->arcs)!=NULL)
570570
{
571571
assert(a->co==co);
572-
/* uncolorchain(cm, a); */
573-
cd->arcs=a->colorchain;
572+
uncolorchain(cm,a);
574573
a->co=sco;
575-
/* colorchain(cm, a); */
576-
a->colorchain=scd->arcs;
577-
scd->arcs=a;
574+
colorchain(cm,a);
578575
}
579576
freecolor(cm,co);
580577
}
@@ -604,7 +601,10 @@ colorchain(struct colormap * cm,
604601
{
605602
structcolordesc*cd=&cm->cd[a->co];
606603

604+
if (cd->arcs!=NULL)
605+
cd->arcs->colorchainRev=a;
607606
a->colorchain=cd->arcs;
607+
a->colorchainRev=NULL;
608608
cd->arcs=a;
609609
}
610610

@@ -616,19 +616,22 @@ uncolorchain(struct colormap * cm,
616616
structarc*a)
617617
{
618618
structcolordesc*cd=&cm->cd[a->co];
619-
structarc*aa;
619+
structarc*aa=a->colorchainRev;
620620

621-
aa=cd->arcs;
622-
if (aa==a)/* easy case */
621+
if (aa==NULL)
622+
{
623+
assert(cd->arcs==a);
623624
cd->arcs=a->colorchain;
625+
}
624626
else
625627
{
626-
for (;aa!=NULL&&aa->colorchain!=a;aa=aa->colorchain)
627-
continue;
628-
assert(aa!=NULL);
628+
assert(aa->colorchain==a);
629629
aa->colorchain=a->colorchain;
630630
}
631+
if (a->colorchain!=NULL)
632+
a->colorchain->colorchainRev=aa;
631633
a->colorchain=NULL;/* paranoia */
634+
a->colorchainRev=NULL;
632635
}
633636

634637
/*

‎src/backend/regex/regc_lex.c

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,7 @@
2828
* OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
2929
* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3030
*
31-
* $PostgreSQL: pgsql/src/backend/regex/regc_lex.c,v 1.6 2007/10/22 01:02:22 tgl Exp $
31+
* $PostgreSQL: pgsql/src/backend/regex/regc_lex.c,v 1.7 2008/01/03 20:47:55 tgl Exp $
3232
*
3333
*/
3434

@@ -846,7 +846,7 @@ lexescape(struct vars * v)
846846
if (ISERR())
847847
FAILW(REG_EESCAPE);
848848
/* ugly heuristic (first test is "exactly 1 digit?") */
849-
if (v->now-save==0|| (int)c <=v->nsubexp)
849+
if (v->now-save==0|| ((int)c>0&& (int)c<=v->nsubexp))
850850
{
851851
NOTE(REG_UBACKREF);
852852
RETV(BACKREF, (chr)c);

‎src/backend/regex/regc_nfa.c

Lines changed: 108 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,7 @@
2828
* OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
2929
* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3030
*
31-
* $PostgreSQL: pgsql/src/backend/regex/regc_nfa.c,v 1.4 2005/10/15 02:49:24 momjian Exp $
31+
* $PostgreSQL: pgsql/src/backend/regex/regc_nfa.c,v 1.5 2008/01/03 20:47:55 tgl Exp $
3232
*
3333
*
3434
* One or two things that technically ought to be in here
@@ -60,11 +60,12 @@ newnfa(struct vars * v,
6060
nfa->nstates=0;
6161
nfa->cm=cm;
6262
nfa->v=v;
63+
nfa->size=0;
6364
nfa->bos[0]=nfa->bos[1]=COLORLESS;
6465
nfa->eos[0]=nfa->eos[1]=COLORLESS;
66+
nfa->parent=parent;/* Precedes newfstate so parent is valid. */
6567
nfa->post=newfstate(nfa,'@');/* number 0 */
6668
nfa->pre=newfstate(nfa,'>');/* number 1 */
67-
nfa->parent=parent;
6869

6970
nfa->init=newstate(nfa);/* may become invalid later */
7071
nfa->final=newstate(nfa);
@@ -88,6 +89,57 @@ newnfa(struct vars * v,
8889
returnnfa;
8990
}
9091

92+
/*
93+
* TooManyStates - checks if the max states exceeds the compile-time value
94+
*/
95+
staticint
96+
TooManyStates(structnfa*nfa)
97+
{
98+
structnfa*parent=nfa->parent;
99+
size_tsz=nfa->size;
100+
101+
while (parent!=NULL)
102+
{
103+
sz=parent->size;
104+
parent=parent->parent;
105+
}
106+
if (sz>REG_MAX_STATES)
107+
return1;
108+
return0;
109+
}
110+
111+
/*
112+
* IncrementSize - increases the tracked size of the NFA and its parents.
113+
*/
114+
staticvoid
115+
IncrementSize(structnfa*nfa)
116+
{
117+
structnfa*parent=nfa->parent;
118+
119+
nfa->size++;
120+
while (parent!=NULL)
121+
{
122+
parent->size++;
123+
parent=parent->parent;
124+
}
125+
}
126+
127+
/*
128+
* DecrementSize - decreases the tracked size of the NFA and its parents.
129+
*/
130+
staticvoid
131+
DecrementSize(structnfa*nfa)
132+
{
133+
structnfa*parent=nfa->parent;
134+
135+
nfa->size--;
136+
while (parent!=NULL)
137+
{
138+
parent->size--;
139+
parent=parent->parent;
140+
}
141+
}
142+
91143
/*
92144
* freenfa - free an entire NFA
93145
*/
@@ -122,6 +174,11 @@ newstate(struct nfa * nfa)
122174
{
123175
structstate*s;
124176

177+
if (TooManyStates(nfa))
178+
{
179+
NERR(REG_ETOOBIG);
180+
returnNULL;
181+
}
125182
if (nfa->free!=NULL)
126183
{
127184
s=nfa->free;
@@ -158,6 +215,8 @@ newstate(struct nfa * nfa)
158215
}
159216
s->prev=nfa->slast;
160217
nfa->slast=s;
218+
/* track the current size and the parent size */
219+
IncrementSize(nfa);
161220
returns;
162221
}
163222

@@ -220,6 +279,7 @@ freestate(struct nfa * nfa,
220279
s->prev=NULL;
221280
s->next=nfa->free;/* don't delete it, put it on the free list */
222281
nfa->free=s;
282+
DecrementSize(nfa);
223283
}
224284

225285
/*
@@ -633,6 +693,8 @@ duptraverse(struct nfa * nfa,
633693
for (a=s->outs;a!=NULL&& !NISERR();a=a->outchain)
634694
{
635695
duptraverse(nfa,a->to, (structstate*)NULL);
696+
if (NISERR())
697+
break;
636698
assert(a->to->tmp!=NULL);
637699
cparc(nfa,a,s->tmp,a->to->tmp);
638700
}
@@ -793,6 +855,25 @@ pull(struct nfa * nfa,
793855
return1;
794856
}
795857

858+
/*
859+
* DGP 2007-11-15: Cloning a state with a circular constraint on its list
860+
* of outs can lead to trouble [Tcl Bug 1810038], so get rid of them first.
861+
*/
862+
for (a=from->outs;a!=NULL;a=nexta)
863+
{
864+
nexta=a->outchain;
865+
switch (a->type)
866+
{
867+
case'^':
868+
case'$':
869+
caseBEHIND:
870+
caseAHEAD:
871+
if (from==a->to)
872+
freearc(nfa,a);
873+
break;
874+
}
875+
}
876+
796877
/* first, clone from state if necessary to avoid other outarcs */
797878
if (from->nouts>1)
798879
{
@@ -917,6 +998,29 @@ push(struct nfa * nfa,
917998
return1;
918999
}
9191000

1001+
/*
1002+
* DGP 2007-11-15: Here we duplicate the same protections as appear
1003+
* in pull() above to avoid troubles with cloning a state with a
1004+
* circular constraint on its list of ins. It is not clear whether
1005+
* this is necessary, or is protecting against a "can't happen".
1006+
* Any test case that actually leads to a freearc() call here would
1007+
* be a welcome addition to the test suite.
1008+
*/
1009+
for (a=to->ins;a!=NULL;a=nexta)
1010+
{
1011+
nexta=a->inchain;
1012+
switch (a->type)
1013+
{
1014+
case'^':
1015+
case'$':
1016+
caseBEHIND:
1017+
caseAHEAD:
1018+
if (a->from==to)
1019+
freearc(nfa,a);
1020+
break;
1021+
}
1022+
}
1023+
9201024
/* first, clone to state if necessary to avoid other inarcs */
9211025
if (to->nins>1)
9221026
{
@@ -1039,7 +1143,8 @@ fixempties(struct nfa * nfa,
10391143
do
10401144
{
10411145
progress=0;
1042-
for (s=nfa->states;s!=NULL&& !NISERR();s=nexts)
1146+
for (s=nfa->states;s!=NULL&& !NISERR()&&
1147+
s->no!=FREESTATE;s=nexts)
10431148
{
10441149
nexts=s->next;
10451150
for (a=s->outs;a!=NULL&& !NISERR();a=nexta)

‎src/include/regex/regerrs.h

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
/*
2-
* $PostgreSQL: pgsql/src/include/regex/regerrs.h,v 1.4 2007/02/01 19:10:29 momjian Exp $
2+
* $PostgreSQL: pgsql/src/include/regex/regerrs.h,v 1.5 2008/01/03 20:47:55 tgl Exp $
33
*/
44

55
{
@@ -73,3 +73,7 @@
7373
{
7474
REG_BADOPT,"REG_BADOPT","invalid embedded option"
7575
},
76+
77+
{
78+
REG_ETOOBIG,"REG_ETOOBIG","nfa has too many states"
79+
},

‎src/include/regex/regex.h

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -29,7 +29,7 @@
2929
* OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
3030
* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3131
*
32-
* $PostgreSQL: pgsql/src/include/regex/regex.h,v 1.28 2005/10/15 02:49:46 momjian Exp $
32+
* $PostgreSQL: pgsql/src/include/regex/regex.h,v 1.29 2008/01/03 20:47:55 tgl Exp $
3333
*/
3434

3535
/*
@@ -151,6 +151,7 @@ typedef struct
151151
#defineREG_INVARG16/* invalid argument to regex function */
152152
#defineREG_MIXED17/* character widths of regex and string differ */
153153
#defineREG_BADOPT18/* invalid embedded option */
154+
#defineREG_ETOOBIG19/* nfa has too many states */
154155
/* two specials for debugging and testing */
155156
#defineREG_ATOI101/* convert error-code name to number */
156157
#defineREG_ITOA102/* convert error-code number to name */

‎src/include/regex/regguts.h

Lines changed: 11 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -27,7 +27,7 @@
2727
* OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
2828
* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2929
*
30-
* $PostgreSQL: pgsql/src/include/regex/regguts.h,v 1.5 2005/10/15 02:49:46 momjian Exp $
30+
* $PostgreSQL: pgsql/src/include/regex/regguts.h,v 1.6 2008/01/03 20:47:55 tgl Exp $
3131
*/
3232

3333

@@ -272,6 +272,7 @@ struct arc
272272
#definefreechain outchain
273273
structarc*inchain;/* *to's ins chain */
274274
structarc*colorchain;/* color's arc chain */
275+
structarc*colorchainRev;/* back-link in color's arc chain */
275276
};
276277

277278
structarcbatch
@@ -311,6 +312,9 @@ struct nfa
311312
structcolormap*cm;/* the color map */
312313
colorbos[2];/* colors, if any, assigned to BOS and BOL */
313314
coloreos[2];/* colors, if any, assigned to EOS and EOL */
315+
size_tsize;/* Current NFA size; differs from nstates as
316+
* it also counts the number of states created
317+
* by children of this state. */
314318
structvars*v;/* simplifies compile error reporting */
315319
structnfa*parent;/* parent NFA, if any */
316320
};
@@ -343,7 +347,12 @@ struct cnfa
343347
#defineZAPCNFA(cnfa)((cnfa).nstates = 0)
344348
#defineNULLCNFA(cnfa)((cnfa).nstates == 0)
345349

346-
350+
/*
351+
* Used to limit the maximum NFA size to something sane. [Tcl Bug 1810264]
352+
*/
353+
#ifndefREG_MAX_STATES
354+
#defineREG_MAX_STATES100000
355+
#endif
347356

348357
/*
349358
* subexpression tree

0 commit comments

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