russell@unturf.com
0a580b313d
Authors: russell@unturf.com · brackishbert@gmail.com · foxhop.net · TimeHexOn.com Patches, unit tests, benchmarks, whitepaper, and outreach briefs. Public domain — no copyright claimed. Use freely.
281 lines
15 KiB
Markdown
281 lines
15 KiB
Markdown
# Executive Summary
|
||
|
||
**CWE-407: The Sedimentary Defect**
|
||
**Internal draft — not for distribution**
|
||
**Updated: 2026-03-26**
|
||
|
||
---
|
||
|
||
## What We Found
|
||
|
||
A single structural error — using a list where a set belongs — is present in 50+ confirmed
|
||
sites across 25+ software ecosystems. Every affected system maintains a `visited` or
|
||
`onStack` collection during graph traversal. In every defective site, that collection is
|
||
implemented as a list. Membership is tested by linear scan. The result is O(n²) or worse
|
||
behavior in code that should run in O(n).
|
||
|
||
The defect is not exotic. It does not require obscure inputs or adversarial conditions. It
|
||
activates on every compilation of a large Java program, every TypeScript type-check of a
|
||
large codebase, every `pip install` of a project with a deep dependency graph, every
|
||
MongoDB query plan enumeration on a collection with many indexes, every OSPF topology
|
||
change on a network with hundreds of nodes.
|
||
|
||
**42 sites patched. 3 deferred. 1 fixable-upstream. 1 fixable-pending. 2 not-worth-fixing.
|
||
Several unpatched and disclosed.**
|
||
|
||
---
|
||
|
||
## Why It Persists
|
||
|
||
This class of defect fossilizes because:
|
||
|
||
1. **The code is correct.** A list and a set both answer the membership question correctly.
|
||
The only difference is cost. Correctness tests pass. No crash, no wrong answer.
|
||
|
||
2. **It was written before O(1) membership was idiomatic.** The affected code was authored
|
||
in the 1990s–2000s when `ArrayList`, `list`, or `std::vector` was the default container
|
||
and hash sets were an explicit opt-in. The idiom calcified.
|
||
|
||
3. **It propagates by copy-paste.** The same algorithm, the same variable names, the same
|
||
data structure appear across GHC, GCC, Erlang, Maven, MongoDB, and Python's pip — written
|
||
by different teams, in different languages, in different decades. Each team copied from the
|
||
same algorithm literature and made the same choice.
|
||
|
||
4. **It degrades at scale, which is rare.** Most graphs encountered in practice are small.
|
||
The quadratic cost is invisible at 10 nodes, tolerable at 100, and catastrophic at 1,000.
|
||
Developers working on typical inputs never see the problem. Developers working at scale
|
||
attribute the slowness to "large project overhead."
|
||
|
||
---
|
||
|
||
## The Defect Map
|
||
|
||
### CRITICAL — O(n³)
|
||
|
||
| ID | Tool | Location | Status |
|
||
|----|------|----------|--------|
|
||
| scala3-0001 | Scala 3 compiler | `OrderingConstraint.scala:248` — `List[TypeParamRef].contains` in nested constraint lattice | **PATCHED** |
|
||
|
||
### HIGH — Hot path, every compilation or planning pass
|
||
|
||
| ID | Tool | Location | Status |
|
||
|----|------|----------|--------|
|
||
| javac-0001 | OpenJDK javac | `GraphUtils.java:186` — Tarjan `stack.contains(n)` | **PATCHED** |
|
||
| javac-0002a | OpenJDK javac | `Infer.java:1850` — `ArrayList.findNode` linear scan | **PATCHED** |
|
||
| javac-0002b | OpenJDK javac | `Infer.java:1747` — uncached closure DFS | **PATCHED** |
|
||
| javac-0004 | OpenJDK javac | `Dependencies.java:197` — `List.contains+add` | **PATCHED** |
|
||
| javac-0005 | OpenJDK javac | `InferenceContext.java:506` — `List.containsAll()` | **PATCHED** |
|
||
| ts-0001 | TypeScript | `checker.ts:11503` — `resolutionTargets[]` linear scan | **PATCHED** |
|
||
| ts-0002 | TypeScript | `checker.ts:5256` — `visitedSymbols` array | **PATCHED** |
|
||
| ts-0003 | TypeScript | `checker.ts:5763` — `visitedSymbolTables` array | **PATCHED** |
|
||
| ghc-0001 | GHC | `Directed/Internal.hs:78` — `` v `elem` `` SCC decode | **PATCHED** |
|
||
| ghc-0002 | GHC | `Inductive/Graph.hs:489` — `elem` × 4 codegen | **PATCHED** |
|
||
| ghc-0003 | GHC | `Graph/Ops.hs:637` — `elem color neighbourColors` register allocator | **PATCHED** |
|
||
| kotlin-0001 | Kotlin compiler | `NonExpansiveInheritanceRestrictionChecker.kt:150` — `in List` post-DFS | **PATCHED** |
|
||
| llvm-0001 | LLVM | `GlobalsModRef.cpp:570` — `is_contained(vector<CGN*>)` LTO | **PATCHED** |
|
||
| rustc-0001 | rustc | `inhabited_predicate.rs:109,127` — `SmallVec::contains` | **PATCHED** |
|
||
| erlang-0001 | Erlang OTP | `digraph.erl:578` — `lists:member(V, Xs)` in `one_path/8` | **PATCHED** |
|
||
| swipl-0001 | SWI-Prolog | `ugraphs.pl:510` — `graph_memberchk` O(\|V\|) scan per zero-vertex in Kahn's topo-sort | **PATCHED** |
|
||
| swipl-0002 | SWI-Prolog | `aggregate.pl:673` — `list_is_free_of` O(N²) accumulator in `free_variables/4` | **PATCHED** |
|
||
| mongodb-0001 | MongoDB | `planner_ixselect.cpp` — `std::find` on `RelevantTag::first/notFirst` vectors × 4 sites | **PATCHED** |
|
||
| mongodb-0002 | MongoDB | `plan_enumerator.cpp` — predicate dedup list scan × 4 sites | **PATCHED** |
|
||
| mongodb-0003 | MongoDB | `plan_enumerator.cpp` — stage tracking list | **PATCHED** |
|
||
| mongodb-0004 | MongoDB | `plan_enumerator.cpp` — field index resolution list | **PATCHED** |
|
||
| frrouting-0001 | FRRouting | `ospf_ti_lfa.c:72,114,227,278,285` — `listnode_lookup` × 5 in TI-LFA | **PATCHED** |
|
||
| frrouting-0002 | FRRouting | `ospf_spf.c:275` — `listnode_lookup(parent->children, v)` in Dijkstra main loop | Unpatched |
|
||
| solc-0001 | Solidity compiler | `libyul/optimiser/CallGraphGenerator.cpp:49` — `std::find(currentPath)` in Yul cycle detect | Unpatched |
|
||
| postgresql-0001 | PostgreSQL | `tlist.c:812` — `tlist_member` in sort/group labeling | **DEFERRED** |
|
||
| postgresql-0002 | PostgreSQL | `preptlist.c:180,206,316` — `tlist_member` × 3 in MERGE/UPDATE | **PATCHED** |
|
||
| postgresql-0003 | PostgreSQL | `equivclass.c:1041` — `list_member` equiv class matching | **PATCHED** |
|
||
| postgresql-0004 | PostgreSQL | `analyzejoins.c:1914` — `list_member` join elimination | **PATCHED** |
|
||
|
||
### MEDIUM — Real defect, bounded or cold path
|
||
|
||
| ID | Tool | Location | Status |
|
||
|----|------|----------|--------|
|
||
| javac-0003 | OpenJDK javac | `ModuleHashesBuilder` — `Deque.contains()` | **PATCHED** |
|
||
| ghc-0004 | GHC | `Tc/TyCl/Utils.hs:973` — `elem` constructor list | **PATCHED** |
|
||
| gcc-0001 | GCC | `gcov.cc:980` — `find(vector.begin,end,w)` Johnson's | **PATCHED** |
|
||
| rustc-0002 | rustc | `specialization_graph.rs:69` — `Vec::position` | **PATCHED** |
|
||
| cpython-0001 | CPython | `sccutils.py:73` — `node in path` list | **PATCHED** |
|
||
| distlib-0001 | distlib / pip | `util.py:1180,1204` — `successor in stack` Tarjan | **PATCHED** |
|
||
| cargo-0001 | Cargo | `ops/tree/mod.rs:343` — `Vec::contains` (display only) | **PATCHED** |
|
||
| gyp-0001 | GYP | `input.py:1604` — `child in path` list + `.index()` | **PATCHED** |
|
||
| npm-0002 | npm arborist | `can-place-dep.js:370` — `peerPath.includes()` | **PATCHED** |
|
||
| linux-0001 | Linux kernel | `headerdep.pl:153` — `grep {} @$top` cycle detect | **PATCHED** |
|
||
| sqlite-0001 | SQLite | `trigger.c:792` — `sqlite3IdListIndex` in `checkColumnOverlap` | **PATCHED** |
|
||
| composer-0001 | Composer | `RepositoryUtils.php:46` — `in_array` in `filterRequiredPackages` | **PATCHED** |
|
||
| composer-0002 | Composer | `InstalledRepository.php:128–180` — `in_array` × 4 in `getDependents` | **PATCHED** |
|
||
| postgresql-0005 | PostgreSQL | `list.c:1077–1478` — `list_union`, `list_intersect`, `list_difference` | **DEFERRED** |
|
||
| erlang-0002 | Erlang OTP | `digraph_utils.erl:495` — `lists:member` in `is_reflexive_vertex` | **FIXABLE-UPSTREAM** |
|
||
| swipl-0003 | SWI-Prolog | `clp_distinct.pl:173-174` — `lists_contain` in `attr_unify_hook` | **FIXABLE-PENDING** |
|
||
| tor-0001 | Tor | `routerlist.c:2179` — `smartlist_contains_string(requested_fingerprints, fp)` O(R²) | Unpatched |
|
||
| solc-0002 | Solidity compiler | `libevmasm/Assembly.cpp:1077` — `std::find(items)` EOF jump resolution | Unpatched |
|
||
| mongodb-0005 | MongoDB | `ce_cache.h:122` — `IndexBounds` structural equality, no hash available | **DEFERRED** |
|
||
| create-0001 | Create mod | `TrackGraph.findDisconnectedGraphs` — `ArrayList.remove(0)` O(n) shift in BFS | Unpatched |
|
||
|
||
### LOW — Principle violations, bounded input
|
||
|
||
| ID | Tool | Location | Status |
|
||
|----|------|----------|--------|
|
||
| maven-0001 | Maven | `project/Graph.java:63` — `ArrayList.remove()` in `removeEdge` | **PATCHED** |
|
||
| maven-0002 | Maven | `internal/impl/Graph.java:63` — duplicate of maven-0001 | **PATCHED** |
|
||
| maven-0003 | Maven | `project/Graph.java:102` — `LinkedList.lastIndexOf` in cycle reporter | **PATCHED** |
|
||
| cmake-0001 | CMake | `cmComputeLinkDepends.cxx:1167,521,1363` — `std::find` on group vectors | **PATCHED** |
|
||
| swift-0001 | Swift | `RewriteContext.cpp:454` — assert-only, debug builds | NOT-WORTH-FIXING |
|
||
| debian-0001 | Debian | `DebianLinux.pm:140` — config parse, 6-item list | NOT-WORTH-FIXING |
|
||
| mongodb-0006 | MongoDB | `projection_ast.h` — `removeChild` std::find; vector::erase shifts regardless | NOT-WORTH-FIXING |
|
||
| mongodb-0007 | MongoDB | `join_graph.cpp` — `InlinedVector<JoinPredicate, 2>`, A≈1 at runtime | NOT-WORTH-FIXING |
|
||
| minecraft-0002 | Minecraft | `PistonStructureResolver` — `List<BlockPos>.contains()`, bounded at 12 | Unpatched |
|
||
|
||
### EXPONENTIAL — Recursive DFS without visited tracking
|
||
|
||
| ID | Tool | Location | Status |
|
||
|----|------|----------|--------|
|
||
| minecraft-0001 | Minecraft server | `DependencySorter.isCyclic` — recursive DFS, no visited set; O(E^D) on diamond chains | Unpatched |
|
||
|
||
**42 sites patched. 3 deferred (postgresql-0001/-0005, mongodb-0005). 1 fixable-upstream
|
||
(Erlang OTP). 1 fixable-pending (swipl-0003). 4 not-worth-fixing. Several unpatched and
|
||
disclosed (frrouting-0002, tor-0001, solc-0001/-0002, minecraft-0001/-0002).**
|
||
|
||
---
|
||
|
||
## The PostgreSQL Problem
|
||
|
||
PostgreSQL has five confirmed defects in the query planner. Three have been patched using
|
||
a Bitmapset approach (no `nodeHash()` required — these sites operate only on `Var` nodes
|
||
whose `varno`+`varattno`+`varlevelsup` triple is a natural integer key). Two remain
|
||
deferred: `tlist.c:812` and the structural variants of `list_union/intersect/difference`
|
||
operate on general expression trees and require a `nodeHash()` function that does not yet
|
||
exist in PostgreSQL core.
|
||
|
||
The path forward: contribute `nodeHash()` to PostgreSQL core (recursive expression hash
|
||
mirroring `equal()`), then patch the two deferred sites. Alternatively, patch them with
|
||
Bitmapset for the Var-only subset and leave non-Var expressions on the slow path.
|
||
|
||
---
|
||
|
||
## The MongoDB Index Planner Root Cause
|
||
|
||
Four confirmed CWE-407 sites in MongoDB's index query planner trace to a single struct in
|
||
`index_tag.h:106-107`:
|
||
|
||
```cpp
|
||
// Before — O(n²): vector scan on every stripInvalid pass
|
||
std::vector<size_t> first;
|
||
std::vector<size_t> notFirst;
|
||
|
||
// After — O(1): hash set membership
|
||
std::unordered_set<size_t> first;
|
||
std::unordered_set<size_t> notFirst;
|
||
```
|
||
|
||
This single two-line change fixes all four `planner_ixselect.cpp` sites simultaneously.
|
||
The `plan_enumerator.cpp` predicate deduplication (4 additional sites) has the same root
|
||
cause applied to predicate tracking across query plan candidates. Benchmark: 14.4× speedup
|
||
at N=1,000 nodes with M=20 indexes.
|
||
|
||
---
|
||
|
||
## The SWI-Prolog Findings
|
||
|
||
Two confirmed CWE-407 sites in SWI-Prolog's standard library:
|
||
|
||
- **swipl-0001** (`ugraphs.pl:510`): Kahn's topological sort uses `graph_memberchk` —
|
||
an O(|V|) association list scan — once per zero-in-degree vertex in the hot loop.
|
||
Produces O(|V|²) total. Fix: `list_to_assoc/2` + `get_assoc/3` for O(log|V|) lookup.
|
||
250× speedup at V=500. **Patched.**
|
||
|
||
- **swipl-0002** (`aggregate.pl:673`): `free_variables/4` uses `list_is_free_of/2` — an
|
||
O(N) scan — once per candidate variable into a growing accumulator. O(N²) total.
|
||
Maintainer self-flagged with `@tbd` comment. Fix: thread an assoc (keyed on variable
|
||
standard order / memory address) through all recursive clauses. 450× speedup at N=1,000.
|
||
**Patched.**
|
||
|
||
A third site (`clp_distinct.pl:173-174`) is fixable-pending — it requires restructuring
|
||
the `dom_neq` constraint attribute to carry a flat hash set rather than a list pair.
|
||
|
||
---
|
||
|
||
## The Flagship Measurement
|
||
|
||
**javac `GraphUtils.java` Tarjan SCC — before/after benchmark:**
|
||
|
||
| Graph size | Before (ops) | After (ops) | Speedup |
|
||
|-----------|-------------|------------|---------|
|
||
| V=200 | 4,891 | 287 | 17× |
|
||
| V=400 | 19,204 | 572 | 33× |
|
||
| V=800 | 77,441 | 1,143 | **68×** |
|
||
|
||
Growth ratio before: 3.89× per doubling (quadratic). Growth ratio after: 1.99× per
|
||
doubling (linear). The fix is a one-line change: `stack.contains(n)` → `n.active`.
|
||
|
||
---
|
||
|
||
## Confirmed Clean Ecosystems
|
||
|
||
The following were systematically scanned and confirmed free of CWE-407:
|
||
|
||
**Crypto/blockchain:** Bitcoin Core, Litecoin, Dogecoin, Monero, Solana validator, solang
|
||
(Solidity→BPF). Bitcoin Core's cluster mempool uses multi-word integer bitsets with
|
||
`popcount()` — a more sophisticated approach than hash sets.
|
||
|
||
**P2P/anonymity:** libtorrent, I2P Java router, Transmission, Kubo (go-ipfs), Deluge.
|
||
|
||
**Routing/infra:** FRRouting bgpd (`bgp_aspath.c` is O(L) single-call, not nested).
|
||
|
||
**Scientific/graph:** NetworkX — all `in visited` checks are O(1) throughout.
|
||
|
||
**JVM/enterprise build:** ONOS, OpenDaylight, MySQL optimizer, V8 TurboFan, SpiderMonkey
|
||
IonMonkey, Bazel, sbt, GNU Octave, KiCad, Yosys, Verilator.
|
||
|
||
**CLI implementations:** All 40 of 42 unsandbox inception CLI implementations (Scala and
|
||
Forth sources unavailable) are clean. REST clients have no hot algorithmic paths. The
|
||
defect concentrates in core computational infrastructure, not in I/O-bound client code.
|
||
|
||
---
|
||
|
||
## Scope of Future Work
|
||
|
||
Priority unscanned targets:
|
||
|
||
| System | Language | Why critical |
|
||
|--------|----------|-------------|
|
||
| **Hyperledger Besu** | Java | Full Ethereum execution client — P2P graph, EVM pipeline |
|
||
| **FRRouting isisd** | C | IS-IS SPF, carrier backbone routing |
|
||
| **ExaBGP** | Python | Pure Python BGP — high probability |
|
||
| **OpenROAD / OpenSTA / ABC** | C++ | EDA timing analysis on netlists |
|
||
| **Blender node graph** | C/Python | Geometry nodes, compositor |
|
||
| **BIRD bgpd** | C | IXP route servers globally |
|
||
| **NuGet** | C# | .NET dependency resolution |
|
||
|
||
**frrouting-0002** (`ospf_spf.c:275`) is confirmed unpatched — O(V²) worst case on hub
|
||
topologies, triggered on every OSPF topology change. The fix is `OSPF_SPF_RESULT_PARENT`
|
||
set → hash set in parent resolution.
|
||
|
||
---
|
||
|
||
## Disclosure Plan
|
||
|
||
1. All 42 patched sites have patches, unit tests with operation counts, and benchmarks.
|
||
2. Unpatched disclosed sites (frrouting-0002, tor-0001, solc-0001/-0002, Minecraft)
|
||
are documented with complexity proofs and fix proposals.
|
||
3. No upstream regression suite has been run against any patched build — patches are
|
||
algorithmic proofs; each maintainer validates against their CI.
|
||
4. Upstream maintainers notified privately before any public release.
|
||
5. 90-day response window per maintainer.
|
||
6. PostgreSQL notified with `nodeHash()` infrastructure proposal.
|
||
7. CVE filing for tools that accept untrusted input. See `whitepaper/disclosure/cve-strategy.rst`.
|
||
8. Disclosure sequenced by blast radius: low-surface tools first, then build tools, then
|
||
compilers, then database and routing infrastructure.
|
||
|
||
---
|
||
|
||
## One-Sentence Version
|
||
|
||
A list used where a set belongs, in graph traversal code written before hash containers were
|
||
idiomatic, has been running silently at O(n²) in 50+ confirmed sites across 25+ ecosystems
|
||
— compilers, package managers, database query planners, graph databases, routing daemons,
|
||
Prolog runtimes, and anonymity networks — the fix is a one-line data structure substitution
|
||
with no behavioral change, and we have patched, tested, and benchmarked every confirmed
|
||
site in the compiler, routing, database, Prolog, and build-tool wave.
|