Regexes with Quardratic Time on Adversarial Inputs

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")

  2000 chars     0.03s
  4000 chars     0.08s
  8000 chars     0.36s
 16000 chars     1.20s
 32000 chars     4.76s

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")

old: 3.523s
new: 0.001s

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")

old: 4.900s
new: 0.001s