We Aren’t Returning You to Your Regular Programming

My colleague, Russ Cox, has a series of articles discussing the regular expression work he did for Google Code Search (part 1, part 2, part 3). The commonly used PCRE library wasn’t suitable because it can take exponential time in some cases, which could allow a denial-of-service attack. Part 1 gives this example:

Note that the Y-axis on the left is measured in seconds, the one on the right is measured in microseconds.

RE2 is now open source.

Disclosure: I work for Google, but had no involvement in RE2 or Google Code Search. As always, this is my personal blog, and the views expressed on these pages are mine alone and not those of my employer.