Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Why not detect (a+)+ #7

Open
nibiwodong opened this issue Apr 30, 2021 · 3 comments
Open

Why not detect (a+)+ #7

nibiwodong opened this issue Apr 30, 2021 · 3 comments

Comments

@nibiwodong
Copy link

Why not detect (a+)+

Welcome to Regexploit. Enter your regexes:
(a+)+
No ReDoS found.
@SugarP1g
Copy link

SugarP1g commented Jul 5, 2022

Same doubt.

@b-c-ds
Copy link
Contributor

b-c-ds commented Jul 5, 2022

As intended.

There is no payload which will cause backtracking with this regex unless you are using it with a function like python's re.fullmatch. A slight trade-off to avoid false positives.

/(a+)+/.test('ay')  // js matches, no ReDoS possible
re.compile(r"(a+)+").match("ay") # python matches, no ReDoS possible

It does find ReDoS when it is possible to cause backtracking:

Welcome to Regexploit. Enter your regexes:
(a+)+$
Pattern: (a+)+$
---
Redos(starriness=11, prefix_sequence=SEQ{  }, redos_sequence=SEQ{ [a]{1+}{1+} $[a] }, repeated_character=[a], killer=[^a])
Worst-case complexity: 11 ⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐ (exponential)
Repeated character: [a]
Final character to cause backtracking: [^a]
Example: 'a' * 3456 + '0'

(a+)+x
Pattern: (a+)+x
---
Redos(starriness=11, prefix_sequence=SEQ{  }, redos_sequence=SEQ{ [a]{1+}{1+} [x] }, repeated_character=[a], killer=None)
Worst-case complexity: 11 ⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐ (exponential)
Repeated character: [a]
Example: 'a' * 3456

(a+)+\w
Pattern: (a+)+\w
---
Redos(starriness=11, prefix_sequence=SEQ{  }, redos_sequence=SEQ{ [a]{1+}{1+} [WORD] }, repeated_character=[a], killer=[^WORD])
Worst-case complexity: 11 ⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐ (exponential)
Repeated character: [a]
Final character to cause backtracking: [^WORD]
Example: 'a' * 3456 + '!'

@shiraSC
Copy link

shiraSC commented Nov 13, 2023

A follow up to this question: how come it doesn't seem to find ReDoS for patterns like (a|aa)+ or (a|a?)+ both examples from OWASP https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants