alt Hacker NewsA 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.
Replies
chr15m • yesterday at 10:58 PM
If a regex runs too long just kill it and show the user an error.
➕ show 1 reply
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.
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...