in the extreme pathological case but also on average cases, as both determinization and bitwise implementations are way faster than backtracking. The advantage of PCRE and backtracking is expressiveness, not speed. I don't know whether you're trolling here or just woefully ...
-
-
Replying to @geofflangdale @pcwalton
underinformed. You're also wrong elsewhere on the thread where you claim that you need to have user-provided regexes to find a regex DDoS. It was, historically, not hard to find rules in the VRT set or the public Snort set that could have handcrafted input that would ...
1 reply 0 retweets 0 likes -
Replying to @geofflangdale @pcwalton
case the system to time out. Back in 2008-2009 or so, we found a regex where every "<" added would double the processing time in the public Snort set. Best of all, those systems *failed open* if they timed out, so in theory, if you could get a threat through that has such a ...
2 replies 0 retweets 0 likes -
Replying to @geofflangdale
The post you’re responding to is from 2014. I readily admit that
@burntsushi5’s Rust regex implementation proved me wrong.2 replies 0 retweets 0 likes -
Replying to @pcwalton @burntsushi5
Ha. Welp, my tweetstorm is misdirected then. Silly me. Although in 2014 we'd been in business since about 2008 *selling* that capability (not widely known) and
@burntsushi5's implementation is hardly the first OSS proof point (Russ Cox's blog posts date from 2007 onwards).1 reply 0 retweets 0 likes -
Replying to @geofflangdale @pcwalton
To be fair, PCRE2's *JIT* is still faster than Rust's regex library in several cases, and faster than RE2 in a lot more cases. Literal optimizations really help bring Rust above RE2, otherwise performance between the two is pretty similar. Hyperscan is a cut above the rest. :P
1 reply 0 retweets 1 like -
Replying to @burntsushi5 @pcwalton
That was my feeling between RE2 and Rust regex (similar algos). I still think Patrick's original point from 2014 was wrong even then in many contexts - being faster on avg. doesn't compensate for a catastrophic performance vulnerability that users can find on many regexes.
1 reply 0 retweets 0 likes -
i.e. you can point an algorithm at a fixed regex and find an input that's dangerous. The dirty secret is of course that it's possible to do this for many libraries - but RE2 and Hyperscan should at worst be a 'bad constant factor'. I have given some thought to exploring how ..
2 replies 0 retweets 0 likes -
Replying to @geofflangdale @burntsushi5
Note that for JS regex implementations this is the wrong tradeoff if you could compile faster in common cases with recursive backtracking.
2 replies 0 retweets 0 likes -
SunSpider regex test: https://github.com/WebKit/webkit/blob/master/PerformanceTests/SunSpider/tests/sunspider-1.0.2/regexp-dna.js#L1684 … Runs repeatedly for a few ms at most. Compilation speed dominates…
1 reply 0 retweets 0 likes
Note that compilation time *plus* runtime is your SunSpider score. So compilation time counts against you…
-
-
Replying to @pcwalton @burntsushi5
Yes, indeed. And RE2's strategy of determinization is unlikely to pay off in a world where you're not going to be keeping the states around. Both RE2-style matchers and Hyperscan would pootle endlessly around on irrelevant opts in this case.
0 replies 0 retweets 0 likesThanks. Twitter will use this to make your timeline better. UndoUndo
-
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.