fuzz-format: Timeout in fuzz-format

[mohammed90]

Detailed Report: https://oss-fuzz.com/testcase?key=5957507767926784

Project: caddy
Fuzzing Engine: libFuzzer
Fuzz Target: fuzz-format
Job Type: libfuzzer_asan_caddy
Platform Id: linux

Crash Type: Timeout (exceeds 60 secs)
Crash Address:
Crash State:
fuzz-format

Sanitizer: address (ASAN)

Regressed: https://oss-fuzz.com/revisions?job=libfuzzer_asan_caddy&range=202401210622:202401220608

Reproducer Testcase: https://oss-fuzz.com/download?testcase_id=5957507767926784

Issue on oss-fuzz tracker: Issue 66099

Minimized reproducer test case: clusterfuzz-testcase-minimized-fuzz-format-5957507767926784.txt

[francislavoie]

FYI @bbaa-bbaa we might have an infinite loop in the formatter

[bbaa-bbaa]

I think there may be a ReDos going on here.

Perhaps we should limit the length of heredocMarker.

caddy/caddyconfig/caddyfile/formatter.go

Line 102 in f5344f8

if len(heredocMarker) > 0 && heredocMarkerRegexp.MatchString(string(heredocMarker)) {

The regexp implementation provided by this package is guaranteed to run in time linear in the size of the input

It seems that golang is not vulnerable to redos. I will do a deeper investigation.

(pprof) top10
Showing nodes accounting for 17.37s, 94.30% of 18.42s total
Dropped 126 nodes (cum <= 0.09s)
Showing top 10 nodes out of 37
      flat  flat%   sum%        cum   cum%
    10.65s 57.82% 57.82%     15.62s 84.80%  runtime.slicerunetostring
     4.87s 26.44% 84.26%      4.87s 26.44%  runtime.encoderune
     0.56s  3.04% 87.30%      1.78s  9.66%  runtime.scanobject
     0.28s  1.52% 88.82%      0.29s  1.57%  runtime.spanOf (inline)
     0.23s  1.25% 90.07%      0.23s  1.25%  runtime.heapBits.nextFast (inline)
     0.22s  1.19% 91.26%      0.51s  2.77%  runtime.findObject
     0.17s  0.92% 92.18%      0.17s  0.92%  runtime.(*gcBits).bitp (inline)
     0.15s  0.81% 93.00%      0.15s  0.81%  runtime.heapBitsForAddr
     0.13s  0.71% 93.70%      2.45s 13.30%  runtime.gcDrain
     0.11s   0.6% 94.30%      0.11s   0.6%  runtime.futex

Converting []rune to string seems to be inefficient.

caddy/caddyconfig/caddyfile/formatter.go

Lines 130 to 132 in b9c40e7

	// check if we're done
	if string(heredocClosingMarker) == string(heredocMarker) {
	heredocMarker = nil

[francislavoie]

Yeah that makes sense. We could limit it to like 16 or 32 chars, which is probably way longer than anyone would ever need.