A well known NP-hard problem is matching some flavors of regex (ex: PCRE). You can turn a 3-SAT problem into such a regex.
In normal situations, it is not a problem, I have written thousands of regex without ever hitting a galactic case (at least not one I am aware of).
But it can still be a problem because if the regex engine is too powerful and accepts user input, a specially crafted regex can be used as a denial of service attack.
Actually, regices with really bad running times are a known vulnerability class. For example (a) is exponential (factorial maybe?) and if you try to match user input against (a) someone who enters a long string of a followed by a single b will bring down your server.
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.
In normal situations, it is not a problem, I have written thousands of regex without ever hitting a galactic case (at least not one I am aware of).
But it can still be a problem because if the regex engine is too powerful and accepts user input, a specially crafted regex can be used as a denial of service attack.