UNDF: UNDF-2026-000000469

UNDF: (pending)

quarkus-0003: BeanDeployment.recursiveBuild — transitive binding traversal no visited set O(2^D)

CWE-407 — Algorithmic Complexity: Exponential Recursion on Diamond Annotation Hierarchy

Field	Value
ID	quarkus-0003
Severity	MEDIUM
Ecosystem	quarkus
Package	arc/processor
File	`independent-projects/arc/processor/src/main/java/io/quarkus/arc/processor/BeanDeployment.java`
Lines	955–964
Complexity	O(2^D) where D = diamond depth in annotation hierarchy
Hot path	Called at application startup for every binding annotation

Description

BeanDeployment.recursiveBuild(DotName name, Map<DotName, Set<AnnotationInstance>> transitiveBindingsMap) traverses the transitive annotation binding graph recursively with no visited-set guard.

On a diamond-shaped annotation hierarchy (annotation A meta-annotated with @B and @C; both @B and @C meta-annotated with @D), the call tree is:

recursiveBuild(A) → recursiveBuild(B) → recursiveBuild(D)
                 → recursiveBuild(C) → recursiveBuild(D)   ← D visited twice

At depth D, @D is visited 2^D times. At D=24: 16,777,216 redundant visits.

// BEFORE — O(2^D): no visited set — exponential on diamond annotation hierarchies
private static Set<AnnotationInstance> recursiveBuild(DotName name,
        Map<DotName, Set<AnnotationInstance>> transitiveBindingsMap) {
    Set<AnnotationInstance> result = transitiveBindingsMap.get(name);
    for (AnnotationInstance instance : transitiveBindingsMap.get(name)) {
        if (transitiveBindingsMap.containsKey(instance.name())) {
            result.addAll(recursiveBuild(instance.name(), transitiveBindingsMap));
        }
    }
    return result;
}

Note: result is the same reference as transitiveBindingsMap.get(name) — the function modifies the map's values in-place during iteration, which also carries a ConcurrentModificationException risk if the Set implementation doesn't tolerate modification.

Fix

Add a Set<DotName> visited parameter to guard against revisiting the same annotation node.

// AFTER — O(N+E): visited set prevents exponential re-traversal
for (DotName name : result.keySet()) {
    result.put(name, recursiveBuild(name, result, new HashSet<>()));
}

private static Set<AnnotationInstance> recursiveBuild(DotName name,
        Map<DotName, Set<AnnotationInstance>> transitiveBindingsMap,
        Set<DotName> visited) {
    if (!visited.add(name)) {
        return Collections.emptySet();
    }
    Set<AnnotationInstance> result = new HashSet<>(transitiveBindingsMap.get(name));
    for (AnnotationInstance instance : transitiveBindingsMap.get(name)) {
        if (transitiveBindingsMap.containsKey(instance.name())) {
            result.addAll(recursiveBuild(instance.name(), transitiveBindingsMap, visited));
        }
    }
    return result;
}

Speedup

Annotation depth (D)	Before (calls)	After (calls)	Speedup
10	1,023	10	102×
15	32,767	15	2,184×
20	1,048,575	20	52,428×

Growth before: O(2^D). Growth after: O(D).

3.3 KiB Raw Permalink Blame History Unescape Escape