# UNDF: UNDF-2026-000000472
# UNDF: (pending)
# nifi-0001: StandardParameterContext.verifyNoCycles — O(D²) Stack.contains on DFS path

## CWE-407 — Algorithmic Complexity

| Field | Value |
|-------|-------|
| ID | nifi-0001 |
| Severity | MEDIUM |
| Ecosystem | nifi |
| Package | nifi-framework-components |
| File | `nifi-framework-bundle/nifi-framework/nifi-framework-components/src/main/java/org/apache/nifi/parameter/StandardParameterContext.java` |
| Lines | 532–556 |
| Complexity | O(D²) |
| Hot path | Called on every ParameterContext inheritance update |

## Defect

`verifyNoCycles` uses a `Stack<String>` (which extends `Vector<String>`) to track the DFS
path and calls `traversedIds.contains(id)` to detect back-edges. `Stack.contains()` is an
O(D) linear scan, called once per node at each recursion level, giving O(D²) total where D is
the depth of the ParameterContext inheritance chain.

```java
private void verifyNoCycles(final Stack<String> traversedIds,
                             final List<ParameterContext> parameterContexts) {
    for (final ParameterContext parameterContext : parameterContexts) {
        final String id = parameterContext.getIdentifier();
        if (traversedIds.contains(id)) {          // O(D) linear scan
            throw new IllegalStateException(...);
        }
        traversedIds.push(id);
        verifyNoCycles(traversedIds, parameterContext.getInheritedParameterContexts());
        traversedIds.pop();
    }
}
```

## Fix

Replace `Stack<String>` with a `HashSet<String>` for the visited-in-current-path set. Since
`Stack` is used as a DFS path tracker, we need O(1) membership checks. Use a `Set<String>` for
the cycle check and a separate `Deque<String>` only if ordering is needed (it is not here).

```java
private void verifyNoCycles(final List<ParameterContext> parameterContexts) {
    final Set<String> traversedIds = new HashSet<>();
    traversedIds.add(id);
    verifyNoCycles(traversedIds, parameterContexts);
}

private void verifyNoCycles(final Set<String> traversedIds,
                             final List<ParameterContext> parameterContexts) {
    for (final ParameterContext parameterContext : parameterContexts) {
        final String id = parameterContext.getIdentifier();
        if (traversedIds.contains(id)) {          // O(1) hash lookup
            throw new IllegalStateException(
                String.format("Circular references in Parameter Contexts not allowed. "
                    + "[%s] was detected in a cycle.", parameterContext.getName()));
        }
        traversedIds.add(id);
        verifyNoCycles(traversedIds, parameterContext.getInheritedParameterContexts());
        traversedIds.remove(id);
    }
}
```

## Speedup

| D (chain depth) | Before (ops) | After (ops) | Speedup |
|-----------------|-------------|-------------|---------|
| 10 | 100 | 10 | 10× |
| 50 | 2,500 | 50 | 50× |
| 100 | 10,000 | 100 | 100× |
| 500 | 250,000 | 500 | 500× |