google / google/closure-compiler

Algorithmic complexity / performance issue on fuzzed input

Open
#3,173 1 comment 0 reactions 0 assignees View on GitHub
internal-issue-created triage-done
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.