UNDF: UNDF-2026-000000461

micronaut-0001: ClassUtils — O(H²) hierarchy.contains in resolveHierarchy loop

CWE-407 — Algorithmic Complexity: Linear Membership Test in Loop

Field	Value
ID	micronaut-0001
Severity	MEDIUM
Ecosystem	micronaut-core
Package	micronaut-core/core
File	`core/src/main/java/io/micronaut/core/reflect/ClassUtils.java`
Lines	340, 366
Complexity	O(H²) where H = class hierarchy depth × interfaces breadth
Fix	Convert `hierarchy` and `interfaces` from `ArrayList` to `LinkedHashSet`

Description

resolveHierarchy(Class<?> type) builds a List<Class<?>> hierarchy = new ArrayList<>() and a List<Class<?>> interfaces = new ArrayList<>(). In the while(superclass != Object.class) loop it calls hierarchy.contains(superclass) — O(H). The recursive helper populateHierarchyInterfaces iterates all interfaces of a class and for each calls hierarchy.contains(aClass) — O(H) per interface, recursively throughout the hierarchy.

For a class with C superclasses and I total (transitive) interfaces the cost is O((C+I)²).

Pattern

// ClassUtils.java:334
List<Class<?>> hierarchy = new ArrayList<>();
List<Class<?>> interfaces = new ArrayList<>();
while (superclass != Object.class) {
    if (!hierarchy.contains(superclass)) {   // O(H) per iteration
        hierarchy.add(superclass);
    }
    populateHierarchyInterfaces(superclass, interfaces);
    superclass = superclass.getSuperclass();
}

// populateHierarchyInterfaces - line 360
for (Class<?> aClass : superclass.getInterfaces()) {
    if (!hierarchy.contains(aClass)) {       // O(H) per interface
        hierarchy.add(aClass);
    }
    populateHierarchyInterfaces(aClass, hierarchy); // recursive
}

Impact

resolveHierarchy is called during bean introspection and type resolution at application startup and during annotation metadata processing. Deep class hierarchies with many interfaces (common in enterprise Java with multiple layers of abstract base classes) trigger O(H²) computation. This is also called from hot paths like BeanIntrospectionMap.

Fix

// Before
List<Class<?>> hierarchy = new ArrayList<>();
List<Class<?>> interfaces = new ArrayList<>();

// After
Set<Class<?>> hierarchySet = new LinkedHashSet<>();
Set<Class<?>> interfacesSet = new LinkedHashSet<>();
// contains() on LinkedHashSet is O(1)
// At end: return new ArrayList<>(hierarchySet) + interfacesSet if ordered list needed

Update populateHierarchyInterfaces signature to accept Set<Class<?>> (or Collection).

Speedup Estimate

For H=30 (superclasses + interfaces, typical enterprise class): 30² = 900 → 30. 30x speedup per hierarchy resolution call.

2.8 KiB Raw Permalink Blame History Unescape Escape