Tcl Source Code

This example hangs tclsh in versions I have handy to test:

regexp {(^(?!aa))+} {aa bb cc}

I believe this demonstrates that the response to CVE-2007-4772 (Tcl bug 1810038) was inadequate.
We prevented a hang in cases where a state-to-be-pulled-past has a trivial circular constraint arc.  But in the above example, there is a loop of two states connected by constraint arcs, and the code gets into an infinite loop trying to push back the constraints indefinitely.  While I've not experimented to prove it, I think that loops of any number of states could be built by extending this example, so the quick-hack solution embodied in the previous fix can't readily be improved to handle this.

One possible line of attack to fix this is to replace the previous check with a generic search to see if the current state is included in any circular chain of constraint arcs.  That might be expensive though.

Another idea is to simply exclude any states created during pull() from subsequent processing in pullback(), which we could do by remembering the largest state number at entry to pullback() and ignoring states with higher numbers.

A question for either of these approaches is whether the pullback processing is necessary for correctness (because it satisfies some execution-time assumption) or is just an optimization that can safely be skipped in some cases.  I think the latter but am not exactly sure.

Thoughts?

Fix accepted.

I think we got the earlier fixes:

http://core.tcl.tk/tcl/info/135d4456205cb134

http://core.tcl.tk/tcl/info/7e49ffdb090666b2

Let me know if you think I missed something.

Oh, I didn't realize you were going to hop right in with that.  There are some earlier patches that went into the Postgres repo around the beginning of October.  I think that these may depend on those to some extent.  I was planning to provide a converted patch for the whole batch, but do not have time to work on it till next week or so.  If you want to push forward sooner, feel free, but see also the earlier fixes.

Adapted version of re-fixconstraintloops.patch is now committed
as branch tgl-pg-re

I see there are several more patches, and I think I'll adapt each
onto that branch in turn for people to try, and then to be merged.

I've written a fix for this problem.  It's included along with a batch of other regex fixes in this submission to the Postgres project:
http://www.postgresql.org/message-id/[email protected]

I plan to submit a Tcl-adapted version of this code once it's committed to Postgres, but if anyone would like to help review it right now, please step up.

Just a very minor update on this one.

This regexp does not in fact hang Tcl.
It runs for quite some time, on the order
of a few minutes, but then returns with
the error:

% regexp -about {(^(?!aa))+}
couldn't compile regular expression pattern: nfa has too many states

Tested 8.5.15, 8.6.1, and current dev sources for 8.5* and 8.6*

I experimented with modifying the code to suppress pullback/pushfwd when there's a circular loop of constraints involving the target state.  While this wasn't hard to code, it turns out not to work at all, because the problem case then ends up hitting the assert(NOTREACHED) in compact().  So my fear that the pullback processing is necessary was correct: not only the regex executor, but even the data representation used for CNFAs, depend on the assumption that pullback/pushfwd can eliminate *every* non-LACON constraint arc.

I don't know whether this was a fundamental oversight on Henry Spencer's part, or whether this assumption is really OK but there's some bug in the way pullback/pushfwd operate.  In any case, I'm clueless at the moment about how we might fix this.

In looking at this, I'm wondering whether there isn't an additional bug in the patch for CVE-2007-4772.  That added code to pull() and push() that deletes any circular constraint arcs ("circular" meaning that from == to).  It's obviously correct to remove such arcs, since traversing one can do nothing useful.  However, the types of arcs that are removed are just '^', '$', BEHIND, AHEAD.  Should not circular LACON arcs be removed as well?  The reason I note this is that the trouble we're looking at comes from the case where we try to swap two COMPATIBLE arcs, and combine() will say COMPATIBLE for cases involving a LACON and another constraint arc.  So it seems like loops involving LACON arcs are just as dangerous, and unnecessary, as loops involving only other constraint types.

BTW, it looks to me like https://core.tcl.tk/tcl/tktview?name=1280817 is another variant of the same issue; at least, it's definitely looping in pullback().

I confirm that 

    regexp -about {(^(?!aa))+}

hangs the current Tcl releases 8.5.15 and 8.6.1

I have not examined the sources yet, but your
description has the sound of correctness about it,
from what I recall from the earlier bug.  It may be
several days before I can attempt to refresh myself
on things.

Thanks for keeping us informed!