3 ms·

I've seen several regexs in various code reviews that are used to validate user input but do so in an exponential manner that can be exploited for simple DOS at

by IncRnd 5y ago

I've seen several regexs in various code reviews that are used to validate user input but do so in an exponential manner that can be exploited for simple DOS attacks.

CyberDildonics 5y ago
Like what? I've never thought about what regex features are exponential.
- llbeansandrice 5y ago
  From the same site: https://www.rexegg.com/regex-explosive-quantifiers.html https://www.rexegg.com/regex-explosive-quantifiers.html
- throwanem 5y ago
  It's more a question of which ones can't be. There are some really nasty and not very obvious gotchas here; https://regular-expressions.mobi/catastrophic.html https://regular-expressions.mobi/catastrophic.html has a good dive into how, for example, backtracking combines with incautious regex design to produce exponential behavior in the length of input. I don't have a hard and fast rule of my own about regex complexity, but I do have a strong intuition over what's now ca. 25 years of working with regexes dating back to initial exposure in Perl 5 as a high schooler. That intuition boils down more or less to the idea that, when a regex grows too complex to comprehend at a glance, it's time to start thinking hard about replacing it with a proper parser, especially if it's operating over (as yet) imperfectly sanitized user input. Sure, it's maybe a little more work up front, at least until you get good at writing small fast parsers - which doesn't take long, in my experience at least; formal training might make it easier still, but I've rarely felt the lack. In exchange for that small investment, you gain reliability and maintainability benefits throughout the lifetime of the code. Much of that comes from the simple source of no longer having to re-comprehend the hairball of punctuation that is any complex regex, before being able to modify it at all - something at which I was actually really good, as recently as a decade or so ago. The expertise has since expired through disuse, and that's given me no cause for regret; the thing about being a regex expert is that it's a really good skill for writing unreadable and subtly dangerous code, and not a skill good for much of anything else. Unreadable and subtly dangerous code was fine when I was a kid doing my own solo projects for fun, where the worst that'd happen is I might have to hit ^C. As an engineer on a team of engineers building software for production, it's not even something I would want to be good at doing.
  - User23 5y ago
    > That intuition boils down more or less to the idea that, when a regex grows too complex to comprehend at a glance, it's time to start thinking hard about replacing it with a proper parser You can get some surprisingly complex yet readable regexes in Perl by using qr//x[1] and decomposing the pieces into smaller qr//s that are then interpolated into the final pattern, along with proper inline comments in the regexes themselves. [1] https://perldoc.perl.org/perlre#/x-and-/xx https://perldoc.perl.org/perlre#/x-and-/xx
    - throwanem 5y ago
      You still have to reason about the whole thing, though. This doesn't make that any easier, but I bet it makes it feel easier.
      - User23 5y ago
        Decomposition is a proven method for making complex code both feel and actually be easier to reason about. Regexes are code. Therefore, decomposition makes complex regexes both feel and actually be easier to reason about.
        throwanem 5y ago
        I don't see anything about qr//x that makes regexes built this way less vulnerable to the kind of exponential backtracking problem under discussion here. I do see a great opportunity to, by assuming interpolated qr// substrings have the locality the syntax falsely suggests, inadvertently create exactly that kind of mishap with it being minimally no easier, and potentially actually more difficult, to notice. Write your code however you like, of course, including concatenating strings and passing the result to 'eval'. The last time I dealt with more Perl than a shell one-liner was around 2012, and that the language encourages this kind of thing is one of the reasons I'm glad of that.
        User23 5y ago
xtracto 5y ago
Ooooh or worse, I once caught someone's "email matching" RegEx code during a code review that was opening the door for some nasty SQL Injection or XSS attacks (kind of like validating if the text field contained a valid email.. but not if it was ONLY a valid email). The problem with RegEx is its "obscurity". However Maybe someone could write a nice testing tool that would throw millions of known exploits into each regex it finds in your code to see if it is vulnerable.

by IncRnd 5y ago

I've seen several regexs in various code reviews that are used to validate user input but do so in an exponential manner that can be exploited for simple DOS attacks.

CyberDildonics 5y ago

Like what? I've never thought about what regex features are exponential.

llbeansandrice 5y ago
From the same site: https://www.rexegg.com/regex-explosive-quantifiers.html https://www.rexegg.com/regex-explosive-quantifiers.html
throwanem 5y ago
It's more a question of which ones can't be. There are some really nasty and not very obvious gotchas here; https://regular-expressions.mobi/catastrophic.html https://regular-expressions.mobi/catastrophic.html has a good dive into how, for example, backtracking combines with incautious regex design to produce exponential behavior in the length of input. I don't have a hard and fast rule of my own about regex complexity, but I do have a strong intuition over what's now ca. 25 years of working with regexes dating back to initial exposure in Perl 5 as a high schooler. That intuition boils down more or less to the idea that, when a regex grows too complex to comprehend at a glance, it's time to start thinking hard about replacing it with a proper parser, especially if it's operating over (as yet) imperfectly sanitized user input. Sure, it's maybe a little more work up front, at least until you get good at writing small fast parsers - which doesn't take long, in my experience at least; formal training might make it easier still, but I've rarely felt the lack. In exchange for that small investment, you gain reliability and maintainability benefits throughout the lifetime of the code. Much of that comes from the simple source of no longer having to re-comprehend the hairball of punctuation that is any complex regex, before being able to modify it at all - something at which I was actually really good, as recently as a decade or so ago. The expertise has since expired through disuse, and that's given me no cause for regret; the thing about being a regex expert is that it's a really good skill for writing unreadable and subtly dangerous code, and not a skill good for much of anything else. Unreadable and subtly dangerous code was fine when I was a kid doing my own solo projects for fun, where the worst that'd happen is I might have to hit ^C. As an engineer on a team of engineers building software for production, it's not even something I would want to be good at doing.
- User23 5y ago
  > That intuition boils down more or less to the idea that, when a regex grows too complex to comprehend at a glance, it's time to start thinking hard about replacing it with a proper parser You can get some surprisingly complex yet readable regexes in Perl by using qr//x[1] and decomposing the pieces into smaller qr//s that are then interpolated into the final pattern, along with proper inline comments in the regexes themselves. [1] https://perldoc.perl.org/perlre#/x-and-/xx https://perldoc.perl.org/perlre#/x-and-/xx
  - throwanem 5y ago
    You still have to reason about the whole thing, though. This doesn't make that any easier, but I bet it makes it feel easier.
    - User23 5y ago
      Decomposition is a proven method for making complex code both feel and actually be easier to reason about. Regexes are code. Therefore, decomposition makes complex regexes both feel and actually be easier to reason about.
      - throwanem 5y ago
        I don't see anything about qr//x that makes regexes built this way less vulnerable to the kind of exponential backtracking problem under discussion here. I do see a great opportunity to, by assuming interpolated qr// substrings have the locality the syntax falsely suggests, inadvertently create exactly that kind of mishap with it being minimally no easier, and potentially actually more difficult, to notice. Write your code however you like, of course, including concatenating strings and passing the result to 'eval'. The last time I dealt with more Perl than a shell one-liner was around 2012, and that the language encourages this kind of thing is one of the reasons I'm glad of that.
        User23 5y ago

xtracto 5y ago

Ooooh or worse, I once caught someone's "email matching" RegEx code during a code review that was opening the door for some nasty SQL Injection or XSS attacks (kind of like validating if the text field contained a valid email.. but not if it was ONLY a valid email). The problem with RegEx is its "obscurity". However Maybe someone could write a nice testing tool that would throw millions of known exploits into each regex it finds in your code to see if it is vulnerable.