Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20130716165534.GR15323@port70.net>
Date: Tue, 16 Jul 2013 18:55:35 +0200
From: Szabolcs Nagy <nsz@...t70.net>
To: musl@...ts.openwall.com
Subject: Re: regex libs (was Re: embedded newbies site.)

* Justin Cormack <justin@...cialbusservice.com> [2013-07-16 16:41:44 +0100]:
> Lua includes a proper regex library. Lua is smaller than PCRE and you get a
> whole programming language thrown in which shows how complex PCRE is...

no, lua uses backtracking matching just like most of the
other listed regex matchers
(it also has weird syntax that is gratuitously different
from the posix one)

you can easily try it yourself with the (a?)^n a^n pattern:

s1 = ''
s2 = ''
for i = 1,24 do
        s1 = s1 .. 'a?'
        s2 = s2 .. 'a'
end
print(string.match(s2, '^'..s1..s2..'$'))

24 is not even a big number but since the matching
is O(2^n) it quickly becomes unresponsive..
(it takes 5s here)

(in the main lua implementation there is a recursion
limit of 200 which is more than enough to render a lua
interpreter completely unresponsive if the regex comes
from untrusted input)

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.