CompileString hangs on malformed input due to unbounded recursion in unify/completeAllArcs

[pskry]

What version of CUE are you using (cue version)?

Tested via Go API with cuelang.org/go v0.15.3, Go 1.25.6 darwin/arm64

Does this issue reproduce with the latest stable release?

Yes, confirmed on v0.15.3 (latest as of 2026-01-20).

What did you do?

This input was discovered via fuzzing a CUE-based configuration loader. The string A0:A&A,A:A0:A0:A,A causes CompileString to hang indefinitely.

Minimal reproducer:

package main

import (
      "fmt"
      "cuelang.org/go/cue/cuecontext"
)

func main() {
      input := "A0:A&A,A:A0:A0:A,A"
      ctx := cuecontext.New()
      v := ctx.CompileString(input)
      fmt.Printf("Result: %v, Err: %v\n", v, v.Err())
}

Option A: Build and run the binary (will eventually stack overflow):

go build -o repro . && ./repro

Option B: Build and run with Go test timeout to capture stack trace:

Wrap the reproducer as a test for the timeout to work:

package main

import (
      "testing"
      "cuelang.org/go/cue/cuecontext"
)

func TestRepro(t *testing.T) {
      input := "A0:A&A,A:A0:A0:A,A"
      ctx := cuecontext.New()
      v := ctx.CompileString(input)
      t.Logf("Result: %v, Err: %v", v, v.Err())
}

Then:

go test -run=TestRepro -timeout=3s

This produces the panic:
test timed out after 3s with the full stack trace showing the elided frames.

What did you expect to see?

A CUE compilation error indicating invalid/malformed CUE syntax, returned promptly.

What did you see instead?

The program hangs indefinitely. When forced to terminate with a timeout and stack dump, it reveals ~46,000 stack frames of mutual recursion between (*Vertex).unify and (*nodeContext).completeAllArcs in internal/core/adt.

Stack trace excerpt:
...45995 frames elided...
cuelang.org/go/internal/core/adt.(*Vertex).unify
    .../internal/core/adt/unify.go:334
cuelang.org/go/internal/core/adt.(*nodeContext).completeAllArcs
    .../internal/core/adt/unify.go:614
cuelang.org/go/internal/core/adt.(*Vertex).unify
    .../internal/core/adt/unify.go:334
...

This represents a potential DoS vector for applications that process untrusted CUE input.

[mvdan]

Thanks! FWIW we are aware that we should do more fuzzing, we just don't have the bandwidth to quickly fix all the bugs that it would uncover. So by all means raise issues if you find any, but bear in mind that we might not be able to fix all of them as quickly as we'd hope.

[mvdan]

Reduced slightly to:

b: a
a: b: b: a
a

[pskry]

Thanks for the quick response!
I am unsure if I should open a new issue for every fuzz result I find, that's a bit much overhead.
Following is the guard-rails I installed to guard against bugs that will hang CUE eval/unification. Hope this helps, otherwise I can provide the inputs (as raw go fuzz diagnostics).

I would strongly suggest that CUE validates (a subset) itself. And to honor context.Context so unbounded recursion at least can be aborted.

Let me know if I can provide further assistance.

var (
	// resourceBombRe matches CUE string/bytes multiplication with large multipliers
	// that would cause resource exhaustion, e.g. "x"*10000000 or "x"*++++10000000
	resourceBombRe = regexp.MustCompile(`\*[\s+\-]*\d{7,}`)

	// stringMultRe matches string/bytes literal multiplication which can trigger CUE hangs
	// e.g. "x"*7T, 'x'*something, or 7*"x" (single quotes are byte literals in CUE)
	stringMultRe = regexp.MustCompile(`(["'][^"']*["']\s*\*|\*\s*["'][^"']*["'])`)

	// unicodeMarkRe matches Unicode combining marks which can cause CUE stack overflow
	// when used in certain contexts (triggers infinite recursion in error path resolution)
	unicodeMarkRe = regexp.MustCompile(`\p{M}`)

	// whitespaceRe matches all whitespace characters for normalization
	whitespaceRe = regexp.MustCompile(`\s+`)
)

func validateCueInput(data []byte) error {
	// Reject invalid UTF-8 - CUE hangs on certain malformed byte sequences
	if !utf8.Valid(data) {
		return MalformedInput{Reason: "invalid UTF-8 encoding"}
	}
	// Reject Unicode control characters (C0 and C1 ranges) except tab, newline, CR
	// CUE hangs or crashes on certain control characters
	if hasDisallowedControlChars(data) {
		return MalformedInput{Reason: "disallowed control characters"}
	}
	// Reject Unicode combining marks which cause CUE stack overflow
	if unicodeMarkRe.Match(data) {
		return MalformedInput{Reason: "Unicode combining marks trigger CUE stack overflow"}
	}
	if resourceBombRe.Match(data) {
		return MalformedInput{Reason: "resource exhaustion pattern detected (large multiplier)"}
	}
	if stringMultRe.Match(data) {
		return MalformedInput{Reason: "string literal multiplication triggers CUE hang"}
	}
	// Normalize whitespace before checking hang pattern
	normalized := whitespaceRe.ReplaceAll(data, nil)
	// Check if input lacks structural braces (outside of strings) and has at least one colon
	// These patterns trigger CUE evaluator bugs
	if !hasStructuralBraces(normalized) && countColons(normalized) >= 1 {
		return MalformedInput{Reason: "pattern triggers CUE evaluator bug (upstream issue #4231)"}
	}
	return nil
}

// hasDisallowedControlChars checks for C0 (0x00-0x1F), DEL (0x7F), and C1 (0x80-0x9F)
// control characters except common whitespace (tab, newline, CR). These cause CUE to hang.
func hasDisallowedControlChars(data []byte) bool {
	for _, r := range string(data) {
		// C0 control characters (except tab, newline, CR)
		if r < 0x20 && r != '\t' && r != '\n' && r != '\r' {
			return true
		}
		// DEL character
		if r == 0x7F {
			return true
		}
		// C1 control characters (0x80-0x9F)
		if r >= 0x80 && r <= 0x9F {
			return true
		}
	}
	return false
}

// hasStructuralBraces checks if the input has { or } outside of string literals.
// This indicates the input has CUE structure (struct definitions) rather than
// being just a bare expression which can trigger CUE bugs.
func hasStructuralBraces(data []byte) bool {
	inString := false
	stringChar := byte(0)
	escaped := false

	for _, b := range data {
		if escaped {
			escaped = false
			continue
		}
		if b == '\\' && inString {
			escaped = true
			continue
		}
		if !inString && (b == '"' || b == '\'') {
			inString = true
			stringChar = b
			continue
		}
		if inString && b == stringChar {
			inString = false
			continue
		}
		if !inString && (b == '{' || b == '}') {
			return true
		}
	}
	return false
}

func countColons(data []byte) int {
	n := 0
	for _, b := range data {
		if b == ':' {
			n++
		}
	}
	return n
}

[mvdan]

I am unsure if I should open a new issue for every fuzz result I find, that's a bit much overhead.

Well, on one hand, it can be noisy. But on the other, it's good to be able to track the bugs and fixes separately.

You're welcome to keep raising issues. I would just ask that you don't open too many at once (a handful open at a time is probably as much as we can deal with at the moment), and that you follow a relatively simple template, like:

1. verify the panic/hang still happens at master
2. provide a pure CUE reproducer, i.e. one that happens with e.g. cue export
3. try to reduce the size of the input CUE as much as possible

You can also file bugs for any panics or hangs you encounter with odd inputs like invalid UTF-8 or unusual unicode codepoints. Those sound like bugs we should fix as well.

We do plan to use fuzzing ourselves; we already have a fuzzer in the parser, we're missing ones for other packages like the compiler, evaluator, or formatter. I just don't have the bandwidth to set that up right now.