google / google/closure-compiler
Algorithmic complexity / performance issue on fuzzed input
- Dominant language
- JavaScript
- Stars
- 7.7k
- Forks
- 1.2k
- Avg merge
- 2d 12h
- Merged PRs (30d)
- 6
Description
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
Contributor guide
Assessment
This issue has not been assessed yet.