UNDF: UNDF-2026-000000520

UNDF: (pending)

hv-0002: Sequence.addInheritedGroups — O(2^D) diamond re-traversal in group inheritance expansion

CWE-407 — Algorithmic Complexity: O(2^D) recursive diamond re-traversal in validation group hierarchy

Field	Value
ID	hv-0002
Severity	HIGH
Ecosystem	hibernate-validator
Package	hibernate-validator
File	`engine/src/main/java/org/hibernate/validator/internal/engine/groups/Sequence.java`
Lines	130–139
Complexity	O(2^D) on diamond group inheritance hierarchies
Hot path	Called during validation order initialization for @GroupSequence

Defect

Sequence.addInheritedGroups recursively expands group interface hierarchies. Although it uses Set<Group> expandedGroups to track visited groups, the recursion guard is MISSING — the method recurses unconditionally even after expandedGroups.add(g) returns false (indicating the group was already visited):

// Sequence.java:130-139 (DEFECT)
private void addInheritedGroups(Group group, Set<Group> expandedGroups) {
    for ( Class<?> inheritedGroup : group.getDefiningClass().getInterfaces() ) {
        if ( isGroupSequence( inheritedGroup ) ) { throw LOG.getSequenceDefinitionsNotAllowedException(); }
        Group g = new Group( inheritedGroup );
        expandedGroups.add( g );                    // adds to set — returns false if already present
        addInheritedGroups( g, expandedGroups );    // DEFECT: recurses unconditionally, ignores add() return value
    }
}

On a diamond group hierarchy (interface D extends A and B; interface A extends BaseGroup; interface B extends BaseGroup; class C implements D), BaseGroup is traversed twice:

Via D→A→BaseGroup: expandedGroups.add(BaseGroup) succeeds → recurse into BaseGroup
Via D→B→BaseGroup: expandedGroups.add(BaseGroup) fails (already present) → BUT STILL RECURSES into BaseGroup!

At diamond depth D, BaseGroup is visited 2^D times.

Fix

Guard the recursion with the return value of expandedGroups.add(g):

// AFTER — O(N+E) where N=groups, E=inheritance edges
private void addInheritedGroups(Group group, Set<Group> expandedGroups) {
    for ( Class<?> inheritedGroup : group.getDefiningClass().getInterfaces() ) {
        if ( isGroupSequence( inheritedGroup ) ) { throw LOG.getSequenceDefinitionsNotAllowedException(); }
        Group g = new Group( inheritedGroup );
        if ( expandedGroups.add( g ) ) {              // only recurse if newly added
            addInheritedGroups( g, expandedGroups );
        }
    }
}

Speedup

Diamond depth (D)	Before (visits)	After (visits)	Speedup
5	31	5	6×
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.1 KiB Raw Permalink Blame History Unescape Escape