# 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):

```java
// 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)`:

```java
// 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).
