# Questionable regex performance when using lazy matching and inverted character classes

**URL:** <https://rubytalk.org/t/questionable-regex-performance-when-using-lazy-matching-and-inverted-character-classes/67346>\
**Category:** ruby-talk\
**Created:** [21 February 2013 11:12 UTC](https://rubytalk.org/t/questionable-regex-performance-when-using-lazy-matching-and-inverted-character-classes/67346 "2013-02-21T11:12:52Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![7stud2](https://avatars.discourse-cdn.com/v4/letter/7/9de053/32.png) [@7stud2](https://rubytalk.org/u/7stud2)\
**Post date:** [21 February 2013 11:12 UTC](https://rubytalk.org/t/questionable-regex-performance-when-using-lazy-matching-and-inverted-character-classes/67346/1 "2013-02-21T11:12:52Z")

</div>

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/](http://www.ruby-forum.com/).

---

<div class="post-metadata">

**Author:** ![Robert\_K1](https://yyz1.discourse-cdn.com/flex029/user_avatar/rubytalk.org/robert_k1/32/1830_2.png) [@Robert\_K1](https://rubytalk.org/u/Robert_K1)\
**Post date:** [21 February 2013 11:30 UTC](https://rubytalk.org/t/questionable-regex-performance-when-using-lazy-matching-and-inverted-character-classes/67346/2 "2013-02-21T11:30:17Z")

</div>

> 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.

You are doing the measurement wrong. You do not only measure matching  
but also creation of the String. Given that fact, all your results  
are moot.

> 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)

Where does 'val' come from and what does it reference?

> 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.

Before we jump to conclusions please provide the proper and complete  
test. Note also that it is a common fact that NFA's can suffer from  
backtracking in certain conditions. So I am not too surprised nor  
worried. I did not look closely at all your test cases but often  
backtracking issues can be remedied by using greediness modifiers  
(either "greedy" or "reluctant").

Kind regards

robert

> **···**
>
> On Thu, Feb 21, 2013 at 12:12 PM, Tikhon B. \<lists@ruby-forum.com\> wrote:
> 
> --  
> remember.guy do |as, often| as.you\_can - without end  
> [http://blog.rubybestpractices.com/](http://blog.rubybestpractices.com/)

---

<div class="post-metadata">

**Author:** ![7stud2](https://avatars.discourse-cdn.com/v4/letter/7/9de053/32.png) [@7stud2](https://rubytalk.org/u/7stud2)\
**Post date:** [22 February 2013 00:21 UTC](https://rubytalk.org/t/questionable-regex-performance-when-using-lazy-matching-and-inverted-character-classes/67346/3 "2013-02-22T00:21:19Z")

</div>

Robert Klemme wrote in post #1098199:

> > 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.
> 
> You are doing the measurement wrong. You do not only measure matching  
> but also creation of the String. Given that fact, all your results  
> are moot.

I actively considered this matter when submitting the post, but in the  
end I included the string creating in the test to allow anyone to try  
out the example by copying one line. The time necessary for the actual  
creation process is negligible; I need to run the string creation ten  
thousand times before the result is substantial enough to significantly  
affect the numbers I'm getting.

Benchmark.measure {10\_000.times {"a" \* 10\_000}}  
=\> 0.100000 0.000000 0.100000 ( 0.105442)

Case in point:

val = "a" \* 10\_000  
3a. Benchmark.measure {val.match(/(?\>a[^b]\*b)/)}  
=\> 1.430000 0.000000 1.430000 ( 1.490874)

4a. Benchmark.measure {val.match(/aa\*b/)}  
=\> 1.310000 0.000000 1.310000 ( 1.366131)

> > 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)
> 
> Where does 'val' come from and what does it reference?

As I just mentioned, I included the string creating as part of the  
benchmark for simple reproduction. While I was figuring out the answer  
myself, I assigned `val = "a" * 10_000` for ease of use.

I added that final example shortly before submitting, and simply did not  
notice that I would need to re-write it to

> > 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.
> 
> Before we jump to conclusions please provide the proper and complete  
> test. Note also that it is a common fact that NFA's can suffer from  
> backtracking in certain conditions. So I am not too surprised nor  
> worried. I did not look closely at all your test cases but often  
> backtracking issues can be remedied by using greediness modifiers  
> (either "greedy" or "reluctant").
> 
> Kind regards
> 
> robert

I am not sure what sort of proper and complete tests you are looking  
for. Regarding the actual slowdown, the issue comes down to the engine  
repeating the match from the start for every single "a" in the string,  
then failing and trying again with the next letter. I do not see how a  
greedy modifier can help in this situation, and I do not know enough  
about the ruby regex engine to comment on the underlying design.

> **···**
>
> > On Thu, Feb 21, 2013 at 12:12 PM, Tikhon B. \<lists@ruby-forum.com\> \> wrote:
> 
> --  
> Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C).

---

<div class="post-metadata">

**Author:** ![Robert\_K1](https://yyz1.discourse-cdn.com/flex029/user_avatar/rubytalk.org/robert_k1/32/1830_2.png) [@Robert\_K1](https://rubytalk.org/u/Robert_K1)\
**Post date:** [22 February 2013 14:32 UTC](https://rubytalk.org/t/questionable-regex-performance-when-using-lazy-matching-and-inverted-character-classes/67346/4 "2013-02-22T14:32:01Z")

</div>

> Robert Klemme wrote in post #1098199:

> > You are doing the measurement wrong. You do not only measure matching  
> > but also creation of the String. Given that fact, all your results  
> > are moot.
> 
> I actively considered this matter when submitting the post, but in the  
> end I included the string creating in the test to allow anyone to try  
> out the example by copying one line.

Having a second line which defines a variable or constant isn't really  
that more inconvenient.

> The time necessary for the actual  
> creation process is negligible; I need to run the string creation ten  
> thousand times before the result is substantial enough to significantly  
> affect the numbers I'm getting.

Still you are measuring one thing but reasoning about another.

> I am not sure what sort of proper and complete tests you are looking  
> for.

Tests which measure exactly the functionality you want to scrutinize  
not something else.

> Regarding the actual slowdown, the issue comes down to the engine  
> repeating the match from the start for every single "a" in the string,  
> then failing and trying again with the next letter.

Backtracking.

> I do not see how a  
> greedy modifier can help in this situation, and I do not know enough  
> about the ruby regex engine to comment on the underlying design.

Mine was a general statement about issues that can be avoided with  
greediness modifiers. I didn't say it's the solution to all  
performance issues of this kind.

I had a closer look at your expressions. They are of course  
artificial to demonstrate the effects of backtracking. I would assume  
that one would typically write different expressions in real  
applications, for example, using anchoring which dramatically improves  
the situation here.

$ ruby rx-bm.rb  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;user system total real  
0 /(?\>a[^b]\*b)/ 11.732000 0.000000 11.732000 ( 11.737671)  
1 /(?\>a[^b]\*b)/ 0.015000 0.000000 0.015000 ( 0.003000)  
0 /\A(?\>a[^b]\*b)/ 0.000000 0.000000 0.000000 ( 0.002000)  
1 /\A(?\>a[^b]\*b)/ 0.000000 0.000000 0.000000 ( 0.003000)  
0 /(?\<!a)(?\>a[^b]\*b)/ 0.016000 0.000000 0.016000 ( 0.012001)  
1 /(?\<!a)(?\>a[^b]\*b)/ 0.000000 0.000000 0.000000 ( 0.003000)  
0 /aa\*b/ 11.700000 0.000000 11.700000 ( 11.703670)  
1 /aa\*b/ 0.000000 0.000000 0.000000 ( 0.002000)  
0 /\Aaa\*b/ 0.000000 0.000000 0.000000 ( 0.002000)  
1 /\Aaa\*b/ 0.015000 0.000000 0.015000 ( 0.002000)  
0 /(?\<!a)aa\*b/ 0.000000 0.000000 0.000000 ( 0.013001)  
1 /(?\<!a)aa\*b/ 0.016000 0.000000 0.016000 ( 0.002000)  
0 /a+b/ 11.248000 0.000000 11.248000 ( 11.252644)  
1 /a+b/ 0.000000 0.000000 0.000000 ( 0.002000)  
0 /\Aa+b/ 0.000000 0.000000 0.000000 ( 0.003000)  
1 /\Aa+b/ 0.000000 0.000000 0.000000 ( 0.002000)  
0 /(?\<!a)a+b/ 0.015000 0.000000 0.015000 ( 0.012001)  
1 /(?\<!a)a+b/ 0.000000 0.000000 0.000000 ( 0.003000)  
0 /a.\*b/ 4.649000 0.000000 4.649000 ( 4.641265)  
1 /a.\*b/ 0.000000 0.000000 0.000000 ( 0.001000)  
0 /\Aa.\*b/ 0.000000 0.000000 0.000000 ( 0.001000)  
1 /\Aa.\*b/ 0.000000 0.000000 0.000000 ( 0.001000)  
0 /(?\<!a)a.\*b/ 0.016000 0.000000 0.016000 ( 0.011001)  
1 /(?\<!a)a.\*b/ 0.000000 0.000000 0.000000 ( 0.000000)  
$ cat -n rx-bm.rb  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2 require 'benchmark'  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;3  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;4 strings = [  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;5 ("a" \* 10\_000).freeze,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;6 ("a" \* 10\_000 + "b").freeze  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;7 ]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;8  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;9 data = [  
&nbsp;&nbsp;&nbsp;&nbsp;10 /(?\>a[^b]\*b)/,  
&nbsp;&nbsp;&nbsp;&nbsp;11 /\A(?\>a[^b]\*b)/,  
&nbsp;&nbsp;&nbsp;&nbsp;12 /(?\<!a)(?\>a[^b]\*b)/,  
&nbsp;&nbsp;&nbsp;&nbsp;13  
&nbsp;&nbsp;&nbsp;&nbsp;14 /aa\*b/,  
&nbsp;&nbsp;&nbsp;&nbsp;15 /\Aaa\*b/,  
&nbsp;&nbsp;&nbsp;&nbsp;16 /(?\<!a)aa\*b/,  
&nbsp;&nbsp;&nbsp;&nbsp;17  
&nbsp;&nbsp;&nbsp;&nbsp;18 /a+b/,  
&nbsp;&nbsp;&nbsp;&nbsp;19 /\Aa+b/,  
&nbsp;&nbsp;&nbsp;&nbsp;20 /(?\<!a)a+b/,  
&nbsp;&nbsp;&nbsp;&nbsp;21  
&nbsp;&nbsp;&nbsp;&nbsp;22 /a.\*b/,  
&nbsp;&nbsp;&nbsp;&nbsp;23 /\Aa.\*b/,  
&nbsp;&nbsp;&nbsp;&nbsp;24 /(?\<!a)a.\*b/,  
&nbsp;&nbsp;&nbsp;&nbsp;25 ]  
&nbsp;&nbsp;&nbsp;&nbsp;26  
&nbsp;&nbsp;&nbsp;&nbsp;27 REP = 20  
&nbsp;&nbsp;&nbsp;&nbsp;28  
&nbsp;&nbsp;&nbsp;&nbsp;29 Benchmark.bm 25 do |x|  
&nbsp;&nbsp;&nbsp;&nbsp;30 data.each do |rx|  
&nbsp;&nbsp;&nbsp;&nbsp;31 strings.each\_with\_index do |s, i|  
&nbsp;&nbsp;&nbsp;&nbsp;32 x.report sprintf("%2d %p", i, rx) do  
&nbsp;&nbsp;&nbsp;&nbsp;33 REP.times do  
&nbsp;&nbsp;&nbsp;&nbsp;34 rx.match s  
&nbsp;&nbsp;&nbsp;&nbsp;35 end  
&nbsp;&nbsp;&nbsp;&nbsp;36 end  
&nbsp;&nbsp;&nbsp;&nbsp;37 end  
&nbsp;&nbsp;&nbsp;&nbsp;38 end  
&nbsp;&nbsp;&nbsp;&nbsp;39 end  
$

So, yes, there is a cost for backtracking involved, but it only shows  
only in particular situations:  
- large inputs  
- specific expressions (absence of anchoring, using unlimited  
repetition operators vs. limited (e.g. /a{0,10}/).

The phenomenon is well known with regular expression engines I  
believe. The cases you mention seem to be rather the exception than  
the common state of affairs. Which doesn't mean that Ruby's engine  
cannot be improved. I just don't think it's not that dramatic an  
issue.

Kind regards

robert

> **···**
>
> On Fri, Feb 22, 2013 at 1:21 AM, Tikhon B. \<lists@ruby-forum.com\> wrote:
> 
> > > On Thu, Feb 21, 2013 at 12:12 PM, Tikhon B. \<lists@ruby-forum.com\> \>\> wrote:
> 
> --  
> remember.guy do |as, often| as.you\_can - without end  
> [http://blog.rubybestpractices.com/](http://blog.rubybestpractices.com/)

---

<div class="post-metadata">

**Author:** ![7stud2](https://avatars.discourse-cdn.com/v4/letter/7/9de053/32.png) [@7stud2](https://rubytalk.org/u/7stud2)\
**Post date:** [22 February 2013 15:24 UTC](https://rubytalk.org/t/questionable-regex-performance-when-using-lazy-matching-and-inverted-character-classes/67346/5 "2013-02-22T15:24:49Z")

</div>

Robert Klemme wrote in post #1098439:

> So, yes, there is a cost for backtracking involved, but it only shows  
> only in particular situations:  
> - large inputs  
> - specific expressions (absence of anchoring, using unlimited  
> repetition operators vs. limited (e.g. /a{0,10}/).
> 
> The phenomenon is well known with regular expression engines I  
> believe. The cases you mention seem to be rather the exception than  
> the common state of affairs. Which doesn't mean that Ruby's engine  
> cannot be improved. I just don't think it's not that dramatic an  
> issue.
> 
> Kind regards
> 
> robert

I took another look at the anchors ruby provides, and I found that the  
\G anchor actually solves the issue outlined in this particular example  
as it applies in my real use case to my satisfaction.

I'm still a bit unsettled that there is such a caveat to consider when  
writing a relatively benign expression. However, given what the symptoms  
of the problem imply about the engine design, I suspect fixing the issue  
would take quite a bit of either hackery, or a fair amount of re-design.

I'll chalk it up to yet another one of those strange landmines you  
encounter in ruby every once in a while.

Thanks,

Tikhon

> **···**
>
> --  
> Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C).

---

<div class="post-metadata">

**Author:** ![Robert\_K1](https://yyz1.discourse-cdn.com/flex029/user_avatar/rubytalk.org/robert_k1/32/1830_2.png) [@Robert\_K1](https://rubytalk.org/u/Robert_K1)\
**Post date:** [22 February 2013 16:09 UTC](https://rubytalk.org/t/questionable-regex-performance-when-using-lazy-matching-and-inverted-character-classes/67346/6 "2013-02-22T16:09:05Z")

</div>

> I took another look at the anchors ruby provides, and I found that the  
> \G anchor actually solves the issue outlined in this particular example  
> as it applies in my real use case to my satisfaction.

Good!

> I'm still a bit unsettled that there is such a caveat to consider when  
> writing a relatively benign expression.

I actually believe this is just one more item to watch out for when  
creating regular expressions. Many expressions I see posted (here and  
elsewhere) are done a bit sloppy and will match properly with the few  
inputs the user is considering right now but break with other inputs.  
I believe you can say the art (?) of creating regular expressions is  
not well developed on average.

> However, given what the symptoms  
> of the problem imply about the engine design, I suspect fixing the issue  
> would take quite a bit of either hackery, or a fair amount of re-design.

Have you read "Mastering Regular Expressions"? If not, it's a good  
read about the matter. Backtracking occurs in every regexp engine  
which is implemented with a NFA and so every of those engines is in  
principle vulnerable here. It's different for DFA based engines which  
do not need backtracking. But today's regexp engines usually use a  
NFA (with sed being a prominent exception) because of the greater  
flexibility. It's a trade off and you always pay a price. 🙂

Cheers

robert

> **···**
>
> On Fri, Feb 22, 2013 at 4:24 PM, Tikhon B. \<lists@ruby-forum.com\> wrote:
> 
> --  
> remember.guy do |as, often| as.you\_can - without end  
> [http://blog.rubybestpractices.com/](http://blog.rubybestpractices.com/)

---

<div class="post-metadata">

**Author:** ![Justin\_Collins](https://avatars.discourse-cdn.com/v4/letter/j/3e96dc/32.png) [@Justin\_Collins](https://rubytalk.org/u/Justin_Collins)\
**Post date:** [22 February 2013 18:41 UTC](https://rubytalk.org/t/questionable-regex-performance-when-using-lazy-matching-and-inverted-character-classes/67346/7 "2013-02-22T18:41:12Z")

</div>

You might be interested in the following pages:

> **[ReDoS](https://en.wikipedia.org/wiki/ReDoS)**
>
> A regular expression denial of service (ReDoS)
> is an algorithmic complexity attack that produces a denial-of-service by providing a regular expression and/or an input that takes a long time to evaluate. The attack exploits the fact that many regular expression implementations have super-linear worst-case complexity; on certain regex-input pairs, the time taken can grow polynomially or exponentially in relation to the input size. An attacker can thus cause a program to spend substantial time Regul...

> **[Runaway Regular Expressions: Catastrophic Backtracking](https://www.regular-expressions.info/catastrophic.html)**
>
> This is the reason why your regular expression takes forever, or crashes your program.

-Justin

> **···**
>
> On 02/22/2013 07:24 AM, Tikhon B. wrote:
> 
> > Robert Klemme wrote in post #1098439:
> > 
> > > So, yes, there is a cost for backtracking involved, but it only shows  
> > > only in particular situations:  
> > > - large inputs  
> > > - specific expressions (absence of anchoring, using unlimited  
> > > repetition operators vs. limited (e.g. /a{0,10}/).
> > > 
> > > The phenomenon is well known with regular expression engines I  
> > > believe. The cases you mention seem to be rather the exception than  
> > > the common state of affairs. Which doesn't mean that Ruby's engine  
> > > cannot be improved. I just don't think it's not that dramatic an  
> > > issue.
> > > 
> > > Kind regards
> > > 
> > > robert
> > 
> > I took another look at the anchors ruby provides, and I found that the  
> > \G anchor actually solves the issue outlined in this particular example  
> > as it applies in my real use case to my satisfaction.
> > 
> > I'm still a bit unsettled that there is such a caveat to consider when  
> > writing a relatively benign expression. However, given what the symptoms  
> > of the problem imply about the engine design, I suspect fixing the issue  
> > would take quite a bit of either hackery, or a fair amount of re-design.
> > 
> > I'll chalk it up to yet another one of those strange landmines you  
> > encounter in ruby every once in a while.
> > 
> > Thanks,
> > 
> > Tikhon