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

Exponential running time when chaining bounds #54

Open
Sjlver opened this issue Mar 17, 2017 · 2 comments
Open

Exponential running time when chaining bounds #54

Sjlver opened this issue Mar 17, 2017 · 2 comments

Comments

@Sjlver
Copy link

Sjlver commented Mar 17, 2017

Expressions like the following cause TRE's run-time to be very high:

echo 'x' | agrep 'x?{100}{100}'
echo 'x' | agrep 'x?{5}{5}{5}{5}{5}{5}'

Found using LLVM's LibFuzzer.

@Sjlver
Copy link
Author

Sjlver commented Mar 17, 2017

I think this can be fixed by allowing only a single repetition operator after every atom. This is what the grammar specifies. However, the implementation currently allows repetiton because it calls STACK_PUSHX(stack, int, PARSE_POSTFIX) again after parsing a postfix operator.

@Sjlver
Copy link
Author

Sjlver commented Mar 17, 2017

My suggested fix does not fully solve the problem. Expressions like (({81}){81}){81} still lead to stack overflows.

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

1 participant