103 lines
4.6 KiB
Markdown
103 lines
4.6 KiB
Markdown
# 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);
|
||
}
|
||
}
|
||
```
|