spdx.Satisfies: unbounded recursion causes uncatchable stack overflow on deeply nested license expressions

[Amey-Thakur]

Summary

spdx.Satisfies parses SPDX license expressions with an unbounded recursive descent. A license string with deeply nested brackets recurses until the goroutine stack overflows, which is a Go fatal error that recover cannot catch, so the whole scan process aborts.

License strings are untrusted input: they come from the metadata of packages in the scanned target. When --licenses is enabled, every package license is passed to spdx.Satisfies at pkg/osvscanner/vulnerability_result.go:123.

This is distinct from #2968. That issue is an empty-input index out of range in tokens.next(); its proposed fix guards next() against an empty token stream. That guard does not bound recursion depth, so it does not address this crash. The two are separate defects in the same parser, one shallow (zero tokens) and one deep (many tokens).

Affected code

internal/spdx/satisfies.go. The recursion runs parseOr -> parseAnd -> parseExpression, and parseExpression calls back into parseOr on every ( (:215-237 at HEAD 567f3ea):

func parseExpression(tokens *tokens) (node, error) {
	next, err := tokens.nextAndIsNextNextValid()
	...
	if next == "(" {
		expr, err := parseOr(tokens)   // recurses; no depth limit
		...
	}
}

allowed["("] includes "(", so an arbitrarily long run of ( is accepted and each one adds a stack frame. There is no bound on nesting depth anywhere in the descent.

Reproduction

At HEAD 567f3ea, go 1.26:

package spdx_test

import (
	"strings"
	"testing"

	"github.com/google/osv-scanner/v2/internal/spdx"
	"github.com/google/osv-scanner/v2/pkg/models"
)

func TestReproDeepNest(t *testing.T) {
	license := models.License(strings.Repeat("(", 2_000_000))
	spdx.Satisfies(license, []string{"MIT"})
}

go test ./internal/spdx -run TestReproDeepNest

Observed:

runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow

runtime stack:
...
github.com/google/osv-scanner/v2/internal/spdx.(*tokens).isNextValid(...)
	internal/spdx/satisfies.go:99
github.com/google/osv-scanner/v2/internal/spdx.(*tokens).nextAndIsNextNextValid(...)
	internal/spdx/satisfies.go:94
github.com/google/osv-scanner/v2/internal/spdx.parseExpression(...)
	internal/spdx/satisfies.go:216
github.com/google/osv-scanner/v2/internal/spdx.parseAnd(...)
github.com/google/osv-scanner/v2/internal/spdx.parseOr(...)
github.com/google/osv-scanner/v2/internal/spdx.parseExpression(...)
	internal/spdx/satisfies.go:216
...

The closing brackets are not required to trigger it; an opening run alone overflows. On this machine the threshold sits between 1,000,000 nested brackets (survives) and 1,500,000 (overflows), so roughly a 3 MB license string. fatal error: stack overflow is not recoverable, so the process exits regardless of any recover on the scan path.

Impact

• Denial of the scan when --licenses is enabled and any scanned package carries a sufficiently nested license expression.
• The trigger is package metadata from the scanned target, so a single crafted or malformed package aborts the run and no remaining packages are evaluated.
• Reachable through the same --licenses code path as osv-scanner panics on empty license field (index out of range) when --licenses is enabled #2968, so both crash the scanner from an untrusted license field, by different mechanisms.

Severity is bounded by the input size required (a multi-megabyte license string), so this is defense-in-depth for a parser that consumes untrusted input, rather than a trivially small trigger. It is still a reachable, unrecoverable crash from untrusted data in a security scanner, which is the reason to bound it.

Suggested fix

Bound the nesting depth in the recursive descent and return a normal parse error past the limit, so a malformed or hostile license expression is rejected like any other invalid input instead of crashing the process. Real SPDX expressions nest only a few levels, so a generous ceiling (for example 1000) rejects nothing legitimate. A regression test drives a deeply nested expression and asserts an error rather than a crash.

CWE-674 (Uncontrolled Recursion).

I have this change and its test ready locally and can open a PR once assigned.

Environment

• osv-scanner at HEAD 567f3ea
• go 1.26.5

[Amey-Thakur]

I would like to work on this. My approach: thread a nesting-depth counter through the recursive descent in internal/spdx/satisfies.go and return a normal parse error once it passes a generous ceiling (1000), so an over-nested expression is rejected like any other invalid input rather than crashing the process. Legitimate SPDX expressions nest only a few levels, so nothing valid is affected. I will add a regression test that drives a deeply nested expression and asserts an error rather than a crash. The change stays local to the SPDX parser and does not overlap with the next() bounds-check discussed in #2968. Fix and test are ready; I can open the PR once assigned.

[prajaktadalawai]

Hi, I see the previous PR was closed. If this is still up for grabs and no one's currently working on it, I'd be happy to pick it up. No worries if it's already spoken for, however I have a fix and test ready locally.
/assign me