By doing this you open a whole new can of worms. How long is too long? Sometime on a non-realtime system, you may get a big latency spike, maybe some housekeeping is going on, whatever, sometimes, things go slow. Finding the right balance is hard, too long a delay and it doesn't protect enough, as if such queries are repeated, it can still stall your system. Too short and you may kill legitimate queries.
Much simpler in these cases to use a regex engine with runtime guarantees. It may not support some advanced features, but you are sure that it won't explode.
Whether you chose to use a regex engine with runtime guarantees or one that support NP-hard features depends on the situation. If you are in control, it is not worth limiting yourself for the rare case it might explode, just Ctrl-C if it happens and move on. But on an automated system that deals with user data, you want the guarantees.
If you have to use one that supports NP-hard features I think a configurable CPU time timeout is also a reasonable backstop, just as configurable timeouts are reasonable in network code.
Good point. The number of times is zero. Probably something that should be implemented defensively at the library level. I guess most developers don't realise this can happen (I did not).
I actually did add a timer as a final "if all else fails" for my regex implementation rather recently, maybe 6 months ago. I don't even know of any scenario that could reach the timer because I have a robust allowlist/denylist and a ton of unit tests. But I would rather just be certain and it wasn't hard.
No you don't actually want a regex library that randomly fails when someone runs one of Chris Domas's pathological stall instructions on a different core.
By doing this you open a whole new can of worms. How long is too long? Sometime on a non-realtime system, you may get a big latency spike, maybe some housekeeping is going on, whatever, sometimes, things go slow. Finding the right balance is hard, too long a delay and it doesn't protect enough, as if such queries are repeated, it can still stall your system. Too short and you may kill legitimate queries.
Much simpler in these cases to use a regex engine with runtime guarantees. It may not support some advanced features, but you are sure that it won't explode.
Whether you chose to use a regex engine with runtime guarantees or one that support NP-hard features depends on the situation. If you are in control, it is not worth limiting yourself for the rare case it might explode, just Ctrl-C if it happens and move on. But on an automated system that deals with user data, you want the guarantees.
> use a regex engine with runtime guarantees
That's a good idea.
If you have to use one that supports NP-hard features I think a configurable CPU time timeout is also a reasonable backstop, just as configurable timeouts are reasonable in network code.
How often have you encountered code that adds a timeout to regex matching?
Good point. The number of times is zero. Probably something that should be implemented defensively at the library level. I guess most developers don't realise this can happen (I did not).
I actually did add a timer as a final "if all else fails" for my regex implementation rather recently, maybe 6 months ago. I don't even know of any scenario that could reach the timer because I have a robust allowlist/denylist and a ton of unit tests. But I would rather just be certain and it wasn't hard.
No you don't actually want a regex library that randomly fails when someone runs one of Chris Domas's pathological stall instructions on a different core.
Why do you say "randomly fails"? Do you consider a configurable timeout with an exception to be a random failure?
Yes. It will fail whenever something else in the system steals your CPU time. Calling code definitely isn't checking for errors either.
What do you want it to do under those conditions then? Stall pathologically?
Yes? If someone locks up the CPU for 60 seconds while your regex library is running, it should take 60 seconds longer to give the same result.
Why would you use wall clock time for this?