84 lines
3.7 KiB
Markdown
84 lines
3.7 KiB
Markdown
# Apache Storm — CWE-407 Disclosure Brief
|
||
|
||
**Project:** Apache Storm
|
||
**Disclosure date:** 2026-03-27
|
||
**Severity:** HIGH
|
||
**Speedup:** varies with n²
|
||
**Status:** PATCHED
|
||
|
||
---
|
||
|
||
## Finding
|
||
|
||
Apache Storm's `Fields` class in `storm-client` uses `ArrayList.contains()` for deduplication in its constructor, producing O(n²) behavior when constructing field sets with many entries. This constructor is called on every tuple schema definition and is on the critical path of Storm topology initialization and worker startup. Two independent dedup paths in the constructor share the same root cause.
|
||
|
||
## The Defect(s)
|
||
|
||
| ID | Location | Pattern | Complexity |
|
||
|----|----------|---------|------------|
|
||
| storm-0001 | `storm-client/src/jvm/.../Fields.java` | `ArrayList.contains()` O(n²) during `Fields` constructor dedup (first dedup path) | O(n²) |
|
||
| storm-0002 | `storm-client/src/jvm/.../Fields.java` | `ArrayList.contains()` O(n²) during `Fields` constructor dedup (second dedup path) | O(n²) |
|
||
|
||
## Complexity Proof
|
||
|
||
Let n = number of field names passed to the `Fields` constructor.
|
||
|
||
The constructor deduplicates field names by appending each to an `ArrayList` only if it is not already present. `ArrayList.contains()` is an O(n) linear scan. At step i, the list contains up to i entries:
|
||
|
||
```
|
||
Field 1: contains() scans 0 entries
|
||
Field 2: contains() scans 1 entry
|
||
...
|
||
Field n: contains() scans n-1 entries
|
||
Total (one path): 0 + 1 + ... + (n-1) = n(n-1)/2 = O(n²)
|
||
Two paths: 2 × n(n-1)/2 = n(n-1) = O(n²)
|
||
```
|
||
|
||
Replacing both dedup checks with `HashMap.containsKey()` (O(1) amortized) reduces the full constructor to O(n). For n = 100 fields, the defective path performs ~9,900 comparisons; the fixed path performs ~100 map lookups.
|
||
|
||
## Impact
|
||
|
||
`Fields` objects are constructed at topology definition time and during worker deserialization of tuple schemas. Large Storm topologies with many-field tuples — stream processing pipelines handling wide events, IoT sensor aggregations, financial tick processing — trigger this path on every worker startup and topology rebalance. Storm supervisors that frequently restart workers (due to crashes, scaling, or rolling upgrades) repeatedly pay this O(n²) cost. The defect is in the core client library shared by all Storm language bindings.
|
||
|
||
## The Fix
|
||
|
||
Replace both `ArrayList<String>` dedup accumulators in the `Fields` constructor with `HashMap<String, Integer>` (mapping field name to index) or a `LinkedHashMap` to preserve insertion order. Use `containsKey()` for O(1) duplicate detection.
|
||
|
||
## Patch
|
||
|
||
```diff
|
||
- public Fields(List<String> fields) {
|
||
- _fields = new ArrayList<>(fields.size());
|
||
- for (String field : fields) {
|
||
- if (_fields.contains(field)) {
|
||
- throw new IllegalArgumentException("duplicate field " + field);
|
||
- }
|
||
- _fields.add(field);
|
||
- }
|
||
- // second dedup path
|
||
- for (String field : _fields) {
|
||
- if (Collections.frequency(_fields, field) > 1) {
|
||
- throw new IllegalArgumentException("duplicate: " + field);
|
||
- }
|
||
- }
|
||
- }
|
||
+ public Fields(List<String> fields) {
|
||
+ _fields = new ArrayList<>(fields.size());
|
||
+ Map<String, Integer> index = new HashMap<>(fields.size() * 2);
|
||
+ for (String field : fields) {
|
||
+ if (index.containsKey(field)) {
|
||
+ throw new IllegalArgumentException("duplicate field " + field);
|
||
+ }
|
||
+ index.put(field, _fields.size());
|
||
+ _fields.add(field);
|
||
+ }
|
||
+ }
|
||
```
|
||
|
||
## What We Ask
|
||
|
||
Please review, apply, and coordinate a 90-day disclosure window before public release. Reply to security@undefect.com.
|
||
|
||
---
|
||
|
||
*This brief is part of coordinated disclosure of CWE-407 (Inefficient Algorithmic Complexity) across 207 open-source ecosystems. Full report: https://undefect.com*
|