3 ms·
There is a type of regex called a "pathological" regex which can be used to make certain regex implementations have exponential time complexity. If you exposed
by cyphar 8y ago
There is a type of regex called a "pathological" regex which can be used to make certain regex implementations have exponential time complexity. If you exposed this in your application, someone could DoS you. Some libraries might have accidentally pathological regular expressions, and so some user input might be able to trigger the pathological case (Atom had a bug a few years ago where certain source files would cause the editor to lock up, and it was caused by a bad regex they used for parsing to figure out the auto indentation[1]).
Russ Cox wrote an article about this in 2007[2], and the situation is still the same. Go doesn't have this problem since Russ Cox is one of the lead authors of Go, and wrote Go's regex library.
[1]: http://davidvgalbraith.com/how-i-fixed-atom/ http://davidvgalbraith.com/how-i-fixed-atom/
[2]: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
- eunoia 8y agoThanks for an excellent answer!
- gpm 8y agoRust's regex library also doesn't have this issue [1], and is easily usable by other languages [2]. If you're concerned about this issue in your code and your not using go it's probably easier to use this than the go one. [1] https://docs.rs/regex/1.1.0/regex/ https://docs.rs/regex/1.1.0/regex/ [2] - C (and thus everything with a FFI): https://github.com/rust-lang/regex/tree/master/regex-capi https://github.com/rust-lang/regex/tree/master/regex-capi - Go (heh): https://github.com/BurntSushi/rure-go https://github.com/BurntSushi/rure-go - Possibly somewhat out of date Python: https://github.com/davidblewett/rure-python https://github.com/davidblewett/rure-python
- cyphar 8y agoSure, but the only reason I mentioned Go is because Russ Cox literally wrote the paper on this problem and also happened to write the Go regex library (as well as a large part of Go itself). I wrote an FSA-based regex implementation in Python some years ago[1] as a learning experience, but that's not really relevant to someone asking "what is a pathological regex". [1]: https://github.com/cyphar/redone https://github.com/cyphar/redone