5 ms·
"Your regex engine uses a slow regex matching algorithm. This is the case for the regex engines built into most programming language runtimes — this includes Ja
by tyingq 6y ago
"Your regex engine uses a slow regex matching algorithm. This is the case for the regex engines built into most programming language runtimes — this includes Java, JavaScript (various flavors) and Node.js, C#/.NET, Ruby, Python, Perl, and PHP. On the safe side, Go and Rust both use fast regex engines, and Google’s RE2 library is fast as well."
I don't feel like "slow" and "fast" are the right adjectives here. Perhaps some form of "backtracking capable" instead of "slow".
Edit: For example, the jit version of pcre2 is often faster than Rust's re engine. But it still supports backtracking and can be "dos-ed".
- davisjam314 6y agoYes, those terms are definitely imprecise. My target audience for that blog post was "anyone vaguely technical, from programmers to managers". I therefore attempted to minimize the amount of technical detail and to focus on the core algorithmic concepts.
- labster 6y agoYou could have just used one sentence to explain that regular expressions in (list of languages) have a feature called backtracking which can be exploited to slow down and DoS a site. I mean, even that sentence, right there. Instead, you boil it down so the reader knows Go and Rust are good and other languages are bad.
- cbarrick 6y agoMaybe instead of "a slow regex matching algorithm" you could just say "a backtracking algorithm". And instead of "a fast regex engine" you could say "a linear algorithm". That way it's both more concise and more technically correct.
- chubot 6y agoI suggest using the term "regular language" in contrast to "regex" or "regular expression". https://news.ycombinator.com/item?id=23598078 https://news.ycombinator.com/item?id=23598078 "Regular language" is an accurate mathematical term that's not "corrupted" by programming. I think you could also use "automata-based" but it's probably less clear and refers more to the implementation [1] If you scroll down about 3 pages here, there is table explaining regexes vs. regular languages: https://www.oilshell.org/share/05-31-pres.html https://www.oilshell.org/share/05-31-pres.html It's the same stuff that's in RSC's articles but those are too dense for a general programming audience (they're more for regex engine implementers). And the existence of the OP's article shows that people haven't gotten it :) You could also use the terms: - regex engine (Perl/Python/PCRE/Java/etc.) - regular language engine (libc, RE2, rust/regex) Or "hybrid engine" may be more accurate for some of those. That is, they may use either automata-based techniques or backtracking depending on the situation. ----- BTW, the Oil shell has a new syntax Eggex for both regular languages and regexes that makes the difference clear. In other words, you should be able to see from the syntax if a construct may cause exponential backtracking. https://www.oilshell.org/release/0.8.pre6/doc/eggex.html https://www.oilshell.org/release/0.8.pre6/doc/eggex.html In other words, it's a static property that's easily detected (if you have a parser for the regex language itself, which is not hard at all in theory, but maybe it is a little in practice :) ) ----- [1] Aside: The terms NFA and DFA were also corrupted by Friedl in a popular O'Reilly book. I have this book and remember being super confused by it, since I read it long after I learned what a DFA and NFA were. https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html What little text it devotes to implementation issues perpetuates the widespread belief that recursive backtracking is the only way to simulate an NFA. Friedl makes it clear that he neither understands nor respects the underlying theory. http://regex.info/blog/2006-09-15/248 http://regex.info/blog/2006-09-15/248
- adrianmonk 6y agoThe "corrupted" term is better here because it describes what the article is about: how to avoid security issues with real-world software tools, some of which match true regular expressions and some which match extended pseudo-"regular expressions". See where the article says, "Faster engines may not support advanced features, most notably backreferences and lookaround assertions." In a discussion about sucrose, fructose, aspartame, and stevia, you wouldn't tell someone to stop using the term "sweetener" and instead use the narrower and more precise term "sugar". If you did, you'd be advising them to use a word with the wrong meaning.
- chubot 6y agoI'm replying to the parent, so the article could be called: Regular Expression Denial of Service Can be Avoided by Using Regular Languages In other words, accepting regular expressions / regexes exposes you to a DoS. Accepting regular languages does not (as long as you're using an appropriate engine.)
- glangdale 6y agoThis seems like a quibble, but putting the emphasis on "using an appropriate engine" in parentheses at the end is burying the lede. Sticking to regular languages will not, in itself, help - you can have catastrophic backtracking in a backtracking engine even with a regular expression that uses only "regular language" concepts. It's also at least theoretically possible that an engine could implement a subset of the non-regular-language "regex" constructs and still avoid backtracking. We considered this in Hyperscan - there are a number of backreference cases that are tractable in practice: First, sometimes the backreferences just don't contain that many different possibilities - sometimes they are used to match quotes (or absence of quotes) so the three alternatives are ("|'|epsilon). This can be done by expansion. Second, a number of backreference uses are structured so that you can only have a small - fixed size - number of back-references "alive" at once. For example, /\s+(\d+)\s+\1/ in libpcre notation matches whitespace, then a number, then more whitespace, then that number again. The thing being referred to by the backref can't ever have multiple live simultaneous values - an automata could note the boundary-crossings in and out of this particular backref and make a note of the value, then do a simple compare later. There are quite a number of backreferences out there that work this way. No-one, to my knowledge, does this, but it could be done. The point is - it's the engine. Not the language. Fully general support for nasty regular expression constructs does lead in practice to ugly blowouts but it doesn't have to. Notably, received wisdom that matching backreferences is exponential is based on a false assumption. The proof that it's in NP requires you to arbitrarily increase the number of backreferences, which is counter to the way most people would imagine regex matching or string matching is analyzed - you either assume that the regex or string is a fixed workload or you give it another parameter 'm' and talk about O(nm) things.
- GuB-42 6y agoI don't know if it has a particular name, but it is a common problem: fast average case, slow worst case. A common example is the quicksort algorithm. It is often considered the fastest sorting algorithm in the general case but it is still O(n²) in the worst case. According to statistics, it should never happen in practice, however, with cleverly ordered data, it can. That's why some libraries prefer to use a slightly slower algorithm (ex: heap sort) but with a O(n.log(n)) guarantee, so that it can't be DDoSed. Unbalanced binary trees can have the same problem, on random data, they work fine, but improperly used, they degenerate into much slower linked lists. Hash tables can also be exploited if they don't used a cryptographically secure hash function, and these are rarely used because they can be so slow as to negate the advantage of using a hash table in the first place.
- Thorrez 6y ago>cryptographically secure hash function I doubt that would help you. Hash tables take the hash and mod it by the size of the array. That will lead to collisions after the mod even if it's essentially impossible to generate collisions before the mod. What you actually need is a secret hash function, so attackers don't know what the values hash to. This is done using a keyed hash function with a secret key.
- eyegor 6y agoAs to sorting, a lot of libraries use timsort these days since it's more optimal than quicksort in the real world and has nlogn worst case. Or b trees for big storage and sorting, but that's generally a different use case (databases et al). If your threat model is "users who create hash collisions to slowly encumber data operations", you've either royally pissed someone off or you have a very determined competitor. No one who cares about performance would deploy a crypto hash function for a dictionary unless they absolutely had to. You can always add more buckets to reduce collision probability. There's an entire class of hash functions dedicated to non crypto purposes (xxhash, murmur, etc).
- davisjam314 6y agoThe name for this in the security literature is "algorithmic complexity attacks". They were first proposed by Crosby & Wallach in 2003, with a running example of degraded hash tables.