3 ms·
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 pr
by GuB-42 2mo ago
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.
- chr15m 2mo agoIf a regex runs too long just kill it and show the user an error.
- maleldil 2mo agoHow often have you encountered code that adds a timeout to regex matching?
- chr15m 2mo agoGood 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).
- inigyou 2mo agoNo 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.
- chr15m 2mo agoWhat do you want it to do under those conditions then? Stall pathologically?
- chr15m 2mo agoWhy do you say "randomly fails"? Do you consider a configurable timeout with an exception to be a random failure?
- inigyou 2mo agoYes. It will fail whenever something else in the system steals your CPU time. Calling code definitely isn't checking for errors either.
- simonreiff 2mo agoI 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.
- GuB-42 2mo agoBy 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.
- chr15m 2mo ago> 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.
- inigyou 2mo agoActually, 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. Oh you think you'll never write a regex like that? Think again. It took down all of Cloudflare once: https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/ https://blog.cloudflare.com/details-of-the-cloudflare-outage...
- inigyou 2mo agoThe regex I meant to write above is (a*)* but the pair of *s got swallowed into HN formatting.