regexp/syntax: character class negation is slow

[func25]

I've submitted a benchmark and a fix at #69304.

New benchmark:

goos: darwin
goarch: arm64
pkg: regexp/syntax
cpu: Apple M1
BenchmarkString/^(.*);$|^;(.*)-8                 4972814               232.1 ns/op            56 B/op          3 allocs/op
BenchmarkString/(foo|bar$)x*-8                   5602014               212.6 ns/op            56 B/op          3 allocs/op
BenchmarkString/[^=,]-8                         21872083                53.84 ns/op            8 B/op          1 allocs/op
BenchmarkString/([^=,]+)=([^=,]+)-8              5726475               207.3 ns/op            56 B/op          3 allocs/op
BenchmarkString/([^=,]+)=([^=,]+),.*-8           4588252               259.2 ns/op            56 B/op          3 allocs/op
PASS
ok      regexp/syntax   7.603s

Go version

1.23 darwin/arm64

What did you do?

I received a report at VictoriaMetrics/VictoriaMetrics#6911 and ran a benchmark for Regexp.String().

What did you see happen?

Some regexes are extremely slow, even when they're simple. The negate [^] causes calcFlags to run over a large character space to find a fold case.

goos: darwin
goarch: arm64
pkg: regexp/syntax
cpu: Apple M1
BenchmarkString/^(.*);$|^;(.*)-8                 4594401               253.2 ns/op            56 B/op          3 allocs/op
BenchmarkString/(foo|bar$)x*-8                   5006730               236.1 ns/op            56 B/op          3 allocs/op
BenchmarkString/[^=,]-8                              256           4227434 ns/op               8 B/op          1 allocs/op
BenchmarkString/([^=,]+)=([^=,]+)-8                  151           8032660 ns/op              56 B/op          3 allocs/op
BenchmarkString/([^=,]+)=([^=,]+),.*-8               146           8095255 ns/op              56 B/op          3 allocs/op
PASS
ok      regexp/syntax   9.011s

[gabyhelp]

Related Issues and Documentation

• regexp/syntax: fix >10000x slower Regexp.String() #69304
• regexp: MatchString run time could be independent of the string length #39480 (closed)
• Dramatically speed down regexp while grow difficulty it #14167 (closed)

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[gopherbot]

Change https://go.dev/cl/611300 mentions this issue: regexp/syntax: Optimize calcFlags() for OpCharClass fold case

[valyala]

This issue sounds like a denial of service security issue, which can be exploited by attackers, who can pass specially crafted regular expressions to a service written in Go, which calls Regexp.String() on the received regexp, so this function consumes a lot of CPU.

[vadimalekseev]

I created a simple way to reproduce the issue - please find it below. This benchmark shows that calling re.String() after Simplify() takes ~4 seconds on a modern CPU, while Parse() itself takes microseconds for the same expression.

package main

import (
	"regexp/syntax"
	"testing"
)

// cpu: AMD Ryzen 9 5950X 16-Core Processor
// BenchmarkRegexpString
// BenchmarkRegexpString-32    	       1	4562344323 ns/op
func BenchmarkRegexpString(b *testing.B) {
	re, err := syntax.Parse("(\\S\\S\\S){1000}", syntax.Perl)
	if err != nil {
		b.Fatal(err)
	}

	re = re.Simplify()

	for b.Loop() {
		_ = re.String()
	}
}