Abstract
========

.. contents:: :local:

Thesis
------

CWE-407 (Algorithmic Complexity: Inefficient Algorithmic Complexity) describes a class of defect
in which a membership test with O(n) cost is embedded inside a loop that also iterates O(n) times,
yielding O(n²) overall where O(n) is achievable. This document proves that CWE-407 is not an
isolated occurrence: it is a **sedimentary defect** that fossilizes in foundational libraries
written before O(1) membership was idiomatic, propagates by copy-paste into downstream tools, and
persists indefinitely because the code is functionally correct and only degrades at scale.

The specific context is graph traversal — strongly connected component algorithms (Tarjan, Kosaraju),
cycle detection, reachability, dependency resolution, and type inference. Every affected system
maintains a ``visited`` or ``onStack`` set to track which nodes have been seen. The defect is
universally the same: that set is represented as a list, and membership is tested by linear scan.

Scope
-----

As of 2026-03-23, this research has confirmed **44 defect sites across 19 ecosystems**:

- **Compilers:** OpenJDK ``javac`` (5 sites, all patched), GHC (4 sites), TypeScript ``tsc``
  (3 sites), Kotlin ``kotlinc``, Scala 3, GCC, LLVM/Clang, ``rustc`` (2 sites),
  CPython PEG parser generator (patched)
- **Build tools and package managers:** Maven (2 sites), CMake, npm Arborist (2 sites),
  pip/distlib (Tarjan SCC — O(V²)), Cargo, GYP, Composer (2 sites — ``filterRequiredPackages``,
  ``getDependents``)
- **Language runtimes:** Erlang/OTP stdlib (``digraph.erl``, ``digraph_utils.erl``)
- **Operating system tooling:** Linux kernel ``scripts/headerdep.pl``
- **Routing infrastructure:** FRRouting TI-LFA (``ospfd/ospf_ti_lfa.c`` × 5 call sites)
- **Databases:** PostgreSQL query planner (5 sites — ``tlist.c``, ``preptlist.c``,
  ``equivclass.c``, ``analyzejoins.c``, ``list.c``); SQLite (2 sites — ``trigger.c``
  ``checkColumnOverlap``, NATURAL JOIN USING resolution)

**Scanned and confirmed CLEAN:** BIRD, ExaBGP, ONOS, OpenDaylight, MySQL, V8, SpiderMonkey,
Bazel, KiCad, GNU Octave, Redis, Varnish, nginx, Apache2, Memcached, Verilator, Yosys,
Apache Ant, sbt, Bundler, DuckDB, Composer solver core — all use O(1) containers for
graph traversal state. The defect pattern does not propagate to modern EDA tools, JavaScript
engines, or tools that adopted idiomatic set/hash containers from the start.

The scan is substantially complete. The 35 confirmed sites represent the empirical scope of
this defect class across the compiler, build tool, and routing protocol ecosystems.

Severity Distribution
---------------------

One site is **CRITICAL** (O(n³)): ``scala3-0001`` in the Scala 3 compiler
``OrderingConstraint.scala``, where a ``List[TypeParamRef].contains`` call inside nested
constraint-lattice traversal produces cubic behavior in the number of type parameters.
**This site is now patched** — patch in ``defects/scala3/patch/``.

Twenty-three sites are **HIGH**: hot paths triggered by ordinary user source, every compilation
or planning pass. This includes the five patched javac defects, all three TypeScript
``checker.ts`` defects (all now patched), the four GHC compiler defects, the npm Arborist
dependency queue defect, and four PostgreSQL planner defects (``tlist.c``, ``preptlist.c``,
``equivclass.c``, ``analyzejoins.c``).

Twelve sites are **MEDIUM or LOW**: real defect, but input is bounded, path is cold, or impact
is limited to display/diagnostic output. This includes PostgreSQL ``list.c`` utility functions
(bounded inputs in practice) and the three LOW-severity sites.

The Fix Pattern
---------------

The fix is structurally identical across all languages and ecosystems:

  Replace the list/array/vector used for ``visited``, ``onStack``, or ``stack`` state with a
  hash-backed set or map. Change every membership test from O(n) linear scan to O(1) hash lookup.

Canonical forms:

- **Java:** ``List<T>.contains()`` → ``Set<T>.contains()``
- **Python:** ``x in list`` → ``x in set``
- **Haskell:** ``x \`elem\` list`` → ``Set.member x set``
- **Erlang:** ``lists:member(x, list)`` → ``maps:is_key(x, map)``
- **TypeScript:** ``array.includes(x)`` → ``Set<T>.has(x)``
- **Kotlin:** ``x in list`` → ``x in hashSet``
- **Scala:** ``list.contains(x)`` → ``set.contains(x)``
- **Rust:** ``vec.contains(&x)`` → ``HashSet::contains(&x)``
- **C/C++:** ``std::find(v.begin(), v.end(), x)`` → ``unordered_set::count(x)``

Semantics are preserved: the visited/stack set never contains duplicates by construction, so set
membership returns the identical boolean as list membership for every call site addressed here.

The Proof
---------

For each patched defect, this document provides:

1. **Exact operation-count formula** — derived from unit tests that count comparisons directly,
   not from asymptotic argument alone
2. **Before/after benchmark** — measured on real hardware against the real tool with
   ``--patch-module`` or equivalent mechanism
3. **Formal complexity proof** — the two-line argument that O(V) loop × O(V) scan = O(V²),
   and O(V) loop × O(1) lookup = O(V)

The flagship measurement is javac ``GraphUtils.java`` Tarjan SCC: at V=800 nodes the patched
implementation is **23x faster** than the defective one. Growth ratio drops from 3.89x
(quadratic) to 1.98x (linear) between V=200 and V=800.

Responsible Disclosure
----------------------

This document is **INTERNAL DRAFT** status. No defect information will be published until:

1. All 44 confirmed defect sites have patches, unit tests, integration tests, and benchmarks
2. This white paper is complete with all proofs
3. Each upstream maintainer has been privately notified with patch and proof
4. A 90-day response window has elapsed (or maintainer has acknowledged and merged)

Networking vendors with confirmed defects — specifically FRRouting (frrouting-0001 in
TI-LFA) — will be notified via their security disclosure process alongside compiler vendors.
BIRD, ExaBGP, ONOS, and OpenDaylight are confirmed clean and require no notification.
PostgreSQL will be notified via their security team (security@postgresql.org) with all
five patches and proofs prior to public disclosure.

CVE filing applies to tools that accept untrusted input — specifically any compiler or build tool
where an adversary can craft source that maximizes the O(n²) path. See
:doc:`disclosure/cve-strategy` for the full analysis.
