The REGEX() function in the Wikidata Query Service is not subject to the timeout of 60 s, allowing an attacker to take up much more CPU time on the service than should be allowed.
One example of a pathological regular expression is (x+x+)+y (from CodingHorror), which takes exponential time (twice as long per extra input character) to verify that xxxxx… does not match the regular expression.
The following query returned false after 90 s:
SELECT (REGEX("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx", "(x+x+)+y") AS ?b) {}The following query resulted in a 504 Gateway Time-out error after an unknown duration (I didn’t check, probably between 3 and 15 minutes):
SELECT (REGEX("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx", "(x+x+)+y") AS ?b) {}BlazeGraph implements the REGEX() function directly with java.util.regex regexes, which are implemented in C and not interruptible (which is why the timeout has no effect). There is a workaround (custom CharSequence implementation), but the real fix should be for BlazeGraph to implement regular expressions properly – SPARQL’s regular expression language is that of XQuery 1.0 and XPath 2.0, which AFAIU is not identical to Java regexes anyways (for instance, I’m pretty sure it shouldn’t support Java’s named capturing group syntax, i. e. SELECT (REGEX("aa", "(?<name>a)\\k<name>") AS ?b) WHERE {} should result in an error).