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

Algorithmic complexity / performance issue on fuzzed input #3173

Open
rohanpadhye opened this issue Dec 15, 2018 · 1 comment
Open

Algorithmic complexity / performance issue on fuzzed input #3173

rohanpadhye opened this issue Dec 15, 2018 · 1 comment
Labels
internal-issue-created An internal Google issue has been created to track this GitHub issue triage-done Has been reviewed by someone on triage rotation.

Comments

@rohanpadhye
Copy link

Running with SIMPLE_OPTIMIZATIONS enabled on v20181210 (reproducible with much older versions too).

The following input takes 1.5 seconds to report syntax error on my Macbook:

((((((((((((((((((((((((e foo = 1; => 1;

The following takes 3 seconds:

((((((((((((((((((((((((((((((((((((e foo = 1; => 1;

The following takes 6 seconds:

((((((((((((((((((((((((((((((((((((((((((((e foo = 1; => 1;

The following takes 12 seconds:

(((((((((((((((((((((((((((((((((((((((((((((((e foo = 1; => 1;

The following takes 1+ minute:

(((((((((((((((((((((((((((((((((((((((((((((((((((((e foo = 1; => 1;

... and so on. I haven't measured the exact complexity but it is highly non-linear (possibly exponential). It is fairly easy to create a long enough string that practically leads to a complete hang.

Is this a performance bug?

Found using JQF: https://github.com/rohanpadhye/jqf

@blickly
Copy link
Contributor

blickly commented Dec 17, 2018

Thanks for the simple repro cases! I think this should help quite a bit with finding the source of this performance issue in the parser.

Created internal bug b/121144320 track.

@blickly blickly added the triage-done Has been reviewed by someone on triage rotation. label Dec 17, 2018
@brad4d brad4d added the internal-issue-created An internal Google issue has been created to track this GitHub issue label Dec 19, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
internal-issue-created An internal Google issue has been created to track this GitHub issue triage-done Has been reviewed by someone on triage rotation.
Projects
None yet
Development

No branches or pull requests

3 participants