[Tcl-bugs] [ tcl-Bugs-1810264 ] Out of band read and expensive/looping operations

[SourceForge.net <no...@so...>]

Bugs item #1810264, was opened at 2007-10-09 12:18
Message generated for change (Comment added) made by dgp
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=110894&aid=1810264&group_id=10894

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: 42. Regexp
Group: obsolete: 8.5b1
Status: Open
Resolution: None
Priority: 9
Private: Yes
Submitted By: Will Drewry (gwad)
Assigned to: Pavel Goran (pvgoran)
Summary: Out of band read and expensive/looping operations

Initial Comment:
Hi Tcl team,


Recently a colleague (Tavis Ormandy) and I uncovered some bugs in Postgresql's regular expression engine.  It turns out that they're using code derived from Tcl.  With Tom Lane's help, we have some tentative patches, but first the bugs :-)


The out of band read in the UCS-4-enabled build -- [CVE-2007-4769]
(the numeric value must be > INT_MAX and <= UINT_MAX)

  select text (E'\\' || '3161573148') ~ (E'\\' || '3161573148');

  regexp {\3161573148} {\3161573148};

(The code location applies to postgres
Backreferences over INT_MAX slip through the check for a single-digit due to
a signedness error in regcomp.c's lexescape() near line 948.  v->numsubexp
is a signed integer and c is unsigned.  The cast to a signed int avoids
warnings but means that any c > INT_MAX will pass the test against the
default nsubexp value of 10.

This mistake allows indexing into v->subs in regcomp.c's parsebranch() near
line 948 to be controlled.  However, this is just a NULL test.  If the value
given indexes out of valid memory, a segmentation fault will occur and the
child process will die.


An infinite loop -- [CVE-2007-4772]\
  regexp {($|^)*} {x}

Tom Lane provided an analysis:
"""
 The problem seems to occur when
an NFA state has a regular ^-constraint as an outgoing arc, plus both
^-constraint and $-constraint outgoing arcs that loop back to itself.
The latter two should be destroyed as useless, but the code didn't get
rid of the $-constraint soon enough and instead transferred it to the
new state that was generated as part of pushing the regular ^-constraint
back to this state's predecessor states.  This then re-created a
situation that needed another iteration of pullback().

The proposed fix deals with this by changing the order of operations:
useless arcs are destroyed in a separate pass before we do the pull()
calls.

I made a similar change in pushfwd(), which has effectively identical
logic.  This part of the patch is not needed to fix the particular
test cases we have, and I'm not certain it can be a problem once
pullback() has gotten rid of ^-constraints.  But it seems like a good
idea to keep the logic in sync, and maybe there are cases where it's
necessary for pushfwd() to protect itself.

The patches pass the Postgres and Tcl regression tests, but I'd sure
like to have someone who understands this regex code look at them.
In particular I'm not entirely sure whether it's OK to flush *all*
non-PLAIN circular arcs.
"""


An expensive regular expression:

regexp {(x{200}){200}$y} {x}


Again with excellent analysis from Tom Lane:
"""
This is not as slow as your original (about 2m rather than 15m on
my machine), but it illustrates the basic issue: the doubly nested
iteration generates 200*200 = 40000 NFA states, all of which are
later found to be dead because the trailing "$y" cannot possibly
match anything, and then when we try to clean them up we spend
O(N^2) time at it because they're all on the same colorchain.

AFAICS the only use of the colorchain data structure is in okcolors(),
which could probably be rewritten to do one iteration over all the NFA's
states/arcs.  So I'm tempted to propose just getting rid of the
colorchain lists.  But I'd *really* want to talk to someone who knows
this code better, first.  There might be cases where the colorchains
are essential for performance.
"""


It'd be great if we could chat about this more, but I wasn't sure the best place to email.  I know that Tom Lane would appreciate any additional insight before patching postgresql.  Tom currently has a few patches explicitly for postgres, but they appear that they'll be pretty portable.  Here are the relevant addresses:

Will Drewry <wa...@go...>	 
Tavis Ormandy <ta...@go...>
Tom Lane <tg...@ss...>
Postgresql Security <sec...@po...>


Thanks!
will


----------------------------------------------------------------------

>Comment By: Don Porter (dgp)
Date: 2007-10-29 17:24

Message:
Logged In: YES 
user_id=80530
Originator: NO


first issue fixed;

second issue duplicate of 1810038?

And 3rd issue looks more like
a feature request than a bug?
Still important but better handled
in another ticket?

----------------------------------------------------------------------

Comment By: Donal K. Fellows (dkf)
Date: 2007-10-27 10:00

Message:
Logged In: YES 
user_id=79902
Originator: NO

No patches?

Fixed first issue though; I can understand that "locally". :-)

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=110894&aid=1810264&group_id=10894