# UNDF: UNDF-2026-000000541
# spring-0006: VersionResourceResolver — O(N²) patternsList.contains() in addFixedVersionStrategy()

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

| Field        | Value |
|--------------|-------|
| ID           | spring-0006 |
| Severity     | MEDIUM |
| Ecosystem    | spring-framework |
| Package      | spring-webmvc |
| File         | `spring-webmvc/src/main/java/org/springframework/web/servlet/resource/VersionResourceResolver.java` |
| Lines        | 130–141 |
| Complexity   | O(N²) where N = pathPatterns.length |
| Fix          | Convert `patternsList` to `HashSet<String>` for O(1) membership check |

## Defective Code

```java
// Line 130-141: VersionResourceResolver.addFixedVersionStrategy()
public VersionResourceResolver addFixedVersionStrategy(String version, String... pathPatterns) {
    List<String> patternsList = Arrays.asList(pathPatterns);   // O(N) list
    List<String> prefixedPatterns = new ArrayList<>(pathPatterns.length);
    String versionPrefix = "/" + version;
    for (String pattern : patternsList) {                       // outer loop: O(N)
        prefixedPatterns.add(pattern);
        if (!pattern.startsWith(versionPrefix) && !patternsList.contains(versionPrefix + pattern)) {
            //                                    ^^^^^^^^^^^^^^^^^^^^ O(N) scan — CWE-407
            prefixedPatterns.add(versionPrefix + pattern);
        }
    }
    return addVersionStrategy(new FixedVersionStrategy(version), StringUtils.toStringArray(prefixedPatterns));
}
```

**Pattern:** `for (x : list) { list.contains(y) }` — inner `contains()` is O(N) on
`Arrays.asList()` backed array. Outer loop is O(N). Total: **O(N²)**.

Triggered at application startup / configuration time when configuring versioned resource
resolvers (common in Spring MVC static resource handling). Large Spring apps with many
path patterns suffer quadratic cost.

## Complexity Table

| N (pathPatterns) | Operations (before) | Operations (after) |
|-----------------|---------------------|-------------------|
| 10              | ~100                | ~10               |
| 100             | ~10,000             | ~100              |
| 1,000           | ~1,000,000          | ~1,000            |

Speedup ratio: **~N×** — 100x at N=100, 1000x at N=1000.

## Fix

```java
public VersionResourceResolver addFixedVersionStrategy(String version, String... pathPatterns) {
    // spring-0006 fix: HashSet for O(1) membership check.
    // Previously Arrays.asList() returned a plain List — patternsList.contains() was O(N).
    // With N patterns, the loop called contains() N times = O(N²) total.
    Set<String> patternsSet = new HashSet<>(Arrays.asList(pathPatterns));
    List<String> prefixedPatterns = new ArrayList<>(pathPatterns.length * 2);
    String versionPrefix = "/" + version;
    for (String pattern : pathPatterns) {
        prefixedPatterns.add(pattern);
        if (!pattern.startsWith(versionPrefix) && !patternsSet.contains(versionPrefix + pattern)) {
            prefixedPatterns.add(versionPrefix + pattern);
        }
    }
    return addVersionStrategy(new FixedVersionStrategy(version), StringUtils.toStringArray(prefixedPatterns));
}
```

## Patch

```diff
--- a/spring-webmvc/src/main/java/org/springframework/web/servlet/resource/VersionResourceResolver.java
+++ b/spring-webmvc/src/main/java/org/springframework/web/servlet/resource/VersionResourceResolver.java
@@ -27,6 +27,7 @@ import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Comparator;
+import java.util.HashSet;
 import java.util.LinkedHashMap;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;

@@ -130,10 +131,13 @@ public class VersionResourceResolver extends AbstractResourceResolver {
 	public VersionResourceResolver addFixedVersionStrategy(String version, String... pathPatterns) {
-		List<String> patternsList = Arrays.asList(pathPatterns);
-		List<String> prefixedPatterns = new ArrayList<>(pathPatterns.length);
+		// spring-0006 fix: use HashSet for O(1) duplicate detection; was O(N²) with List.contains()
+		Set<String> patternsSet = new HashSet<>(Arrays.asList(pathPatterns));
+		List<String> prefixedPatterns = new ArrayList<>(pathPatterns.length * 2);
 		String versionPrefix = "/" + version;
-		for (String pattern : patternsList) {
+		for (String pattern : pathPatterns) {
 			prefixedPatterns.add(pattern);
-			if (!pattern.startsWith(versionPrefix) && !patternsList.contains(versionPrefix + pattern)) {
+			if (!pattern.startsWith(versionPrefix) && !patternsSet.contains(versionPrefix + pattern)) {
 				prefixedPatterns.add(versionPrefix + pattern);
 			}
 		}
```