Hacker News new | past | comments | ask | show | jobs | submit login

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/ [2]: https://swtch.com/~rsc/regexp/regexp1.html




Rust'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/

[2]

- C (and thus everything with a FFI): https://github.com/rust-lang/regex/tree/master/regex-capi

- Go (heh): https://github.com/BurntSushi/rure-go

- Possibly somewhat out of date Python: https://github.com/davidblewett/rure-python


Sure, 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


I agree entirely.

I wasn't trying to say "you should have linked this instead", just trying to point anyone who sees this and goes "that's an issue in my code" in the right direction.


Ah, sorry -- I misunderstood the thrust of your point. Didn't mean to bite your head off.


Thanks for an excellent answer!




Applications are open for YC Winter 2020

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: