From: "Tikhon B." <lists@...>
Date: 2013-02-21T20:12:52+09:00
Subject: Questionable regex performance when using lazy matching and inverted character classes

Hi All,

I am trying to figure out a performance question with the ruby regex
matcher. Running the following code takes excessively longer than
expected.

1. Benchmark.measure {("a" * 10_000).match(/a.*?b/)}
=>   1.140000   0.010000   1.150000 (  1.195161)

2. Benchmark.measure {("a" * 10_000).match(/a[^b]*b/)}
=>   1.400000   0.000000   1.400000 (  1.462178)

Thinking the parser was doing some unnecessary backtracking I also tried
atomic grouping, and other simpler expressions with very limited
success:

3. Benchmark.measure {("a" * 10_000).match(/(?>a[^b]*b)/)}
=>   1.400000   0.000000   1.400000 (  1.462178)

4. Benchmark.measure {("a" * 10_000).match(/aa*b/)}
=>   1.270000   0.000000   1.270000 (  1.331137)

5. Benchmark.measure{val.match(/a.*b/)}
=>   0.460000   0.000000   0.460000 (  0.487267)

Simplifying the expression further produces the expected results.

6. Benchmark.measure {("a" * 10_000).match(/a*b/)}
=>   0.000000   0.000000   0.000000 (  0.000093)

As best as I can tell this is caused by the repetition of the first
character in the expression in the string:

7. Benchmark.measure{("a" + "c" * 9999).match(/ac*b/)}
=>   0.000000   0.000000   0.000000 (  0.000372)

This may be a very simple vector for a DDOS attack against a server
using a similar expression to verify input data. What more, since valid
input data is not likely to resemble scenarios 1-6 the issue may go
undetected by a developers and testers not aware of this problem.

Conversely, other developers may be turned off from using a regex in a
place where it would perform well due to simple performance testing as
above.

This sort of performance hit is in neither the NodeJS nor Python regex
engines. Writing this message I think I got a better grasp of the cause
of the issue, but I still feel that it needs to be addressed for the
sake of security.

-- 
Posted via http://www.ruby-forum.com/.