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.
84 lines
3.1 KiB
ReStructuredText
84 lines
3.1 KiB
ReStructuredText
Java — CWE-407 Language Analysis
|
|
=================================
|
|
|
|
.. contents:: :local:
|
|
|
|
Overview
|
|
--------
|
|
|
|
Java's ``java.util.ArrayList`` and related ``List`` implementations expose a ``contains(Object o)``
|
|
method that performs a linear scan of the backing array. This is O(n) and is the canonical source
|
|
of CWE-407 defects in the Java ecosystem. The pattern is endemic because ``ArrayList`` is the
|
|
default collection in Java idiom and developers frequently use ``contains`` without considering
|
|
its cost in loops.
|
|
|
|
The fix in all cases is to replace the ``List`` with a ``HashSet`` (or ``LinkedHashSet`` when
|
|
insertion order must be preserved). ``HashSet.contains()`` and ``HashSet.add()`` are O(1)
|
|
amortized.
|
|
|
|
Canonical Defect Pattern
|
|
------------------------
|
|
|
|
.. code-block:: java
|
|
|
|
// Defective — O(V²) for V membership tests
|
|
List<Node> visited = new ArrayList<>();
|
|
for (Node n : graph.nodes()) {
|
|
if (!visited.contains(n)) { // O(|visited|) each time
|
|
visited.add(n);
|
|
// ... process n
|
|
}
|
|
}
|
|
|
|
.. code-block:: java
|
|
|
|
// Fixed — O(V) for V membership tests
|
|
Set<Node> visited = new HashSet<>();
|
|
for (Node n : graph.nodes()) {
|
|
if (visited.add(n)) { // O(1) — add returns false if already present
|
|
// ... process n
|
|
}
|
|
}
|
|
|
|
Confirmed Defects in this Language's Compiler/Runtime
|
|
------------------------------------------------------
|
|
|
|
All five javac defects are Java code: see :doc:`../compiler/javac` for full analysis.
|
|
|
|
| Defect | File | Complexity | Status |
|
|
|------------|---------------------------------------|------------|----------|
|
|
| javac-0001 | ``GraphUtils.java:186`` | O(V²) | Patched |
|
|
| javac-0002a| ``Infer.java:1850`` | O(N²) | Patched |
|
|
| javac-0002b| ``Infer.java:1747`` | O(K·V) | Patched |
|
|
| javac-0003 | ``ModuleHashesBuilder`` | O(V²) | Unpatched|
|
|
| javac-0004 | ``Dependencies.java:197`` | O(M²) | Patched |
|
|
| javac-0005 | ``InferenceContext.java:506`` | O(B²) | Patched |
|
|
|
|
The ``javac-0003`` defect is in the ``java.base`` module (``ModuleHashesBuilder``), not in the
|
|
compiler package itself. It also affects JVM module resolution at runtime for large module
|
|
graphs.
|
|
|
|
Java Ecosystem Note
|
|
-------------------
|
|
|
|
Maven also carries two instances of this pattern in its project graph implementation: see
|
|
:doc:`../tool-harness/maven`.
|
|
|
|
The canonical fix summary for Java:
|
|
|
|
- Replace ``ArrayList<T>.contains(x)`` with ``HashSet<T>.contains(x)``
|
|
- Replace ``if (!list.contains(x)) { list.add(x); }`` with ``set.add(x)`` (idempotent)
|
|
- Replace ``list.containsAll(other)`` with ``new HashSet<>(list).equals(new HashSet<>(other))``
|
|
- Replace ``Deque.contains(x)`` with a companion ``HashSet`` for O(1) membership tests
|
|
|
|
Clean Java Implementations (Reference)
|
|
---------------------------------------
|
|
|
|
- **Gradle** ``ExecutionPlan``: uses ``HashSet`` and ``HashMultimap`` throughout — correct O(V+E)
|
|
- **Cargo main resolver** (Java-adjacent): HashSet throughout
|
|
|
|
References
|
|
----------
|
|
|
|
* :doc:`../compiler/javac`
|
|
* :doc:`../tool-harness/maven`
|