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.

▲

inigyou an hour ago | parent | next [-]

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...

▲

chr15m 3 hours ago | parent | prev [-]

If a regex runs too long just kill it and show the user an error.

▲

maleldil 2 hours ago | parent [-]

How often have you encountered code that adds a timeout to regex matching?

▲

chr15m 2 hours ago | parent [-]

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).

	▲	inigyou an hour ago \| parent [-]
		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.