Hacker News Reader

Comment by freedomben | Hacker News Reader

Timeouts for Regexp is quite interesting. The engineering purity in me saddens at such a thought, but indeed it seems highly practical.

The syntax feels a little rough although I have no ideas how to make it better:

    Regexp.timeout = 1.0
    ...
    /^a*b?a*$/ =~ "a" * 50000 + "x"

I think I would favor the:

    long_time_re = Regexp.new("^a*b?a*$", timeout: 1.0)

version instead but I use the `=~` almost entirely, so that would still be a big style change. Probably end up setting a global timeout per app and then overriding for individual checks as needed?

View on HN

I wouldn't expect people to have to change that setting often, and 1 second seems very reasonable to me.

So yes, `Regexp.timeout` is supposed to be a default setting for the app, and when really needed you can override it with the `timeout:` key.

Yeah the implementation they've chosen seems totally perfect to me. Sane global default, easily overridable globally or locally.

No easy way to override it locally when using =~, but I can't imagine too many cases where you would want to use a local timeout anyway.... can just switch away from =~ syntax for those.

This is mostly a denial-of-service mitigation tool, something you'd just want to apply globally to avoid disasters spawned by malformed or malicious input. In practice, it's hard to imagine a use case where you'd really want to be twiddling the knobs on a regexp-by-regexp basis.

Yes good point, I was initially thinking that it would make sense to always ask yourself "how long should this take" and tune appropriately, but for the vast majority of regexes that's overkill, especially if you're not doing anything O(n^2). sticking a 1 second in there gives you a lot of headroom and you can just get more specific for any exceptions.

    I was initially thinking that it would make sense 
    to always ask yourself "how long should this take" 
    and tune appropriately, but for the vast majority 
    of regexes that's overkill

More than being overkill, it's actually impossible right?

The execution time will also vary greatly based on base CPU performance, and current server load.

A regexp that takes 10ms to process right now might take 500ms tomorrow when your server is under heavy load. So we can't predict how much time each regexp "needs."

But, like you said, we can set a somewhat ridiculously high limit to help prevent regex-based oopsies or re-based DoS attacks from dragging us down =)

A timeout for regexps makes so much sense. And it would end all these denial of service security reports.

It does not make sense to me, best solution is to have an implementation like re2 that does not have those problems.

Adding a timeout is a bit strange, first because you don't know in advance how long it's going to take for large search. The timeout is a failsafe against something that should be fixed in the first place.

You can use re2 in Ruby if you like - it's just not the default. https://github.com/mudge/re2

    best solution is to have an implementation like re2 that does not have those problems.

By design RE2 isn't fully compatible with Onigmo. As another poster mentioned, a hybrid "use RE2 when possible; fall back to Onigmo otherwise" approach was considered and rejected for well-explained reasons https://bugs.ruby-lang.org/issues/18653

Maybe in addition to `Regexp.timeout = 1.0` there could also be a `Regexp.parser = :re2` option with `:onigmo` being the default.

I think a limit on stack/recursion/backtracking depth would be tad a bit more elegant than a timeout and would keep your code behaviour the same between different machines.

It'd be harder to control perceived performance of user facing applications though. If I can set the timeout, I can guarantee that something happens within X seconds, instead of within X iterations which could have different performance machine to machine.

is this not the halting problem? You can guarantee a certain depth isnt reached but you cant guarantee a recursion will unwind or anything like that

No, because we’re not trying to find out if the computation will ever halt with unbounded time. It just determines if it will halt after a certain number of steps, which you can always determine by executing that number of steps and bailing out.

It's not the halting problem; it's bounding computational depth

Their suggestion is essentially making stack overflow a feature in regex, & then allowing that stack depth to be tuned

Wooosh

thats the problem with all these syntax sugar features in languages. you literally can't change them without blowing up your entire ecosystem.

How would this problem be different if Ruby did not have syntax support for regexes and instead offered a regex module in the standard library?

If it isn’t syntax then it is a function/method call. By being a method call, one can define default options, allowing overridability.

They could easily add another regex flag to indicate a "safe" regex. That really isn't the problem here. The problem is that adding a safe regex engine doesn't retroactively fix the thousands and thousands of regexes in gems which can't be unilaterally forced over to the new engine.

actually that is the problem. no they can't 'easily' add a new flag (or they would have). it doesn't fix the problem of being broken by default and any fundamental change in behavior will lead to problems as well.

the point is the language is broken fundamentally and because its syntax sugar there isn't anything you can do realistically. a function call can be replaced, deprecated, and then removed and all of that can be automated and be non-disruptive over a few releases.

> It does not make sense to me

What are your credentials for being you?

The grand-parent post exhibits feigned confusion and using opinions as arguments. It also proposes an _optimal_ solution that will most likely not get implemented in place of pragmatic solution. We see this kind of argumentation when discussing crypto libraries.

The OP is not _confused_, they just don't like the solution.

It makes zero sense, if I'm completely honest. Why stop to regexps? What about every other long-running function? This is better handled on a layer above, in a general fashion - imagine a server running some queries and being able to kill/discard/interrupt them in case they seem stuck.

If you don’t stop long processes on a server, you expose yourself to denial of service attacks. It’s good practice to have a maximum duration for database queries as well.

Of course you should limit the query duration - just not on some arbitrary function-level like done here. To me this sounds like PHP-level incompetence on API design.

Slightly off-topic digression:

Would WAS compilation help solve the ruby / rails timeout problem?

https://devcenter.heroku.com/articles/h12-request-timeout-in... > H12 - Request Timeout in Ruby (MRI) > Rack-timeout limitations > Due to the design of the Ruby programming language’s Thread#raise API, which timing out code depends on, there is a known bug with rack-timeout that can put your app into a bad state if rack-timeout fires too frequently.

I wonder why they didn't just include an option to use a non-backtracking algorithm, like re2's[1]. As far as I know, that would completely eliminate the possibility of catastrophic backtracking happening.

[1]: https://github.com/google/re2

It was explored but decided against, at least for now https://bugs.ruby-lang.org/issues/18653

Wrapping RE2 with a fallback to the existing engine to try to maintain compatibility was explored; that, like the timeout approach, is pretty clearly a stopgap measure; actually implementing an RE2-style algorithm without the compatibility and toolchain warts of RE2 for Ruby's existing code and functionality is a bigger but more permanent solution, that I don't think has really been ruled out of explored.

if you break compatibility you might as well just use some re2 bindings[0]

[0] https://github.com/mudge/re2

Better arguably would be to use a generator or continuation.

Reply on news.ycombinator.com