explosion / explosion/spaCy

Regexes with Quardratic Time on Adversarial Inputs

Open
#14,020 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
33.9k
Forks
4.7k
Avg merge
3m
Merged PRs (30d)
1

Description

## How to reproduce the behaviour

### HTTP Regex

```python
import time
import spacy

nlp = spacy.blank("en")

for n in (1000, 2000, 4000, 8000, 16000):
text = "a:" * n
start = time.perf_counter()
nlp(text)
print(f"{len(text):>6} chars {time.perf_counter() - start:7.2f}s")
```
would ouput
```
2000 chars 0.03s
4000 chars 0.08s
8000 chars 0.36s
16000 chars 1.20s
32000 chars 4.76s
```
It is addressed in #14016

### NER Format Autodetection
It is addressed in #14017

In `spacy/cli/convert.py:213-214` `r"\S+\|(O|[IB]-\S+)"` and `r"\S+\s+(O|[IB]-\S+)$"` can lead to quardratic time on some inputs:
```python
import re
import time

line = "x|" * 10000

for name, pattern in [
("old", r"\S+\|(O|[IB]-\S+)"),
("new", r"\S\|(O|[IB]-\S+)"),
]:
start = time.perf_counter()
re.search(pattern, line)
print(f"{name}: {time.perf_counter() - start:.3f}s")
```
Would output:
```
old: 3.523s
new: 0.001s
```
Also:
```python
import re
import time

line = "a" * 20000

for name, pattern in [
("old", r"\S+\s+(O|[IB]-\S+)$"),
("new", r"\S\s+(O|[IB]-\S+)$"),
]:
start = time.perf_counter()
re.search(pattern, line)
print(f"{name}: {time.perf_counter() - start:.3f}s")
```
Would output:
```
old: 4.900s
new: 0.001s
```

## Your Environment

* Operating System: Ubuntu 24.04
* Python Version Used: 3.12.1
* spaCy Version Used: 3.8.0

Contributor guide

Open the contributing guide

Research direction

Start by reviewing issues #14016 and #14017, which the report identifies as addressing the HTTP and NER autodetection cases. Then inspect spacy/cli/convert.py lines 213-214 and reproduce the reported timing comparisons; the work is done when the affected inputs no longer show quadratic behavior and the existing behavior remains correct.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
performance
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.