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.
159 lines
4.4 KiB
ReStructuredText
159 lines
4.4 KiB
ReStructuredText
Apache Maven — CWE-407 Analysis
|
|
=================================
|
|
|
|
.. contents:: :local:
|
|
|
|
Overview
|
|
--------
|
|
|
|
Apache Maven is the dominant build and dependency management tool for Java projects. It
|
|
constructs a project dependency graph and uses topological sorting for build-order resolution.
|
|
Three CWE-407 defect sites were found across Maven's internal graph implementation. All three
|
|
are unpatched.
|
|
|
|
Defect Sites
|
|
------------
|
|
|
|
maven-0001
|
|
~~~~~~~~~~
|
|
|
|
**File:** ``impl/maven-core/src/main/java/org/apache/maven/project/Graph.java:63-64``
|
|
|
|
**Pattern:**
|
|
|
|
.. code-block:: java
|
|
|
|
// Project dependency graph — ArrayList.remove() in removeEdge
|
|
private final Map<String, List<String>> edges = new HashMap<>();
|
|
|
|
public void removeEdge(String from, String to) {
|
|
List<String> deps = edges.get(from);
|
|
if (deps != null) {
|
|
deps.remove(to); // O(n) — ArrayList.remove(Object) is linear scan
|
|
}
|
|
}
|
|
|
|
**Why this is O(n):** ``ArrayList.remove(Object)`` scans the list for the first occurrence of
|
|
the element. Called during edge removal in cycle-breaking traversal.
|
|
|
|
**Complexity:** ``O(n)`` per edge removal; ``O(E²/V)`` for full graph reduction
|
|
|
|
**Patch:**
|
|
|
|
.. code-block:: java
|
|
|
|
private final Map<String, LinkedHashSet<String>> edges = new HashMap<>();
|
|
|
|
public void removeEdge(String from, String to) {
|
|
LinkedHashSet<String> deps = edges.get(from);
|
|
if (deps != null) {
|
|
deps.remove(to); // O(1) — HashSet.remove is O(1)
|
|
}
|
|
}
|
|
|
|
**Data structure change:** ``Map<String, List<String>>`` → ``Map<String, LinkedHashSet<String>>``
|
|
|
|
**Status:** Unpatched
|
|
|
|
Benchmark Results
|
|
-----------------
|
|
|
|
.. TODO: benchmark pending patch
|
|
|
|
Complexity Proof
|
|
----------------
|
|
|
|
Let E = edges, V = vertices. ``ArrayList.remove(Object)`` is O(E/V) per call (average degree).
|
|
With E removals total: O(E²/V). With ``HashSet.remove``: O(1) per removal, O(E) total. QED.
|
|
|
|
References
|
|
----------
|
|
|
|
* Defect ticket: ``tools/tickets/defects/maven-0001.md``
|
|
|
|
maven-0002
|
|
~~~~~~~~~~
|
|
|
|
**File:** ``impl/maven-core/src/main/java/org/apache/maven/internal/impl/Graph.java:63-64``
|
|
|
|
**Pattern:**
|
|
|
|
Duplicate of maven-0001 in a parallel internal implementation class. Identical defect, identical
|
|
fix.
|
|
|
|
**Why this is O(n):** Same as maven-0001 — ``ArrayList.remove(Object)`` linear scan.
|
|
|
|
**Complexity:** ``O(n)`` per edge removal
|
|
|
|
**Patch:**
|
|
|
|
Identical to maven-0001: replace ``List<String>`` adjacency lists with ``LinkedHashSet<String>``.
|
|
|
|
**Data structure change:** ``Map<String, List<String>>`` → ``Map<String, LinkedHashSet<String>>``
|
|
|
|
**Status:** Unpatched
|
|
|
|
Benchmark Results
|
|
-----------------
|
|
|
|
.. TODO: benchmark pending patch (same as maven-0001)
|
|
|
|
Complexity Proof
|
|
----------------
|
|
|
|
Identical to maven-0001. QED.
|
|
|
|
References
|
|
----------
|
|
|
|
* Defect ticket: ``tools/tickets/defects/maven-0002.md``
|
|
|
|
maven-0003
|
|
~~~~~~~~~~
|
|
|
|
**File:** ``impl/maven-core/src/main/java/org/apache/maven/project/Graph.java:102``
|
|
|
|
**Pattern:**
|
|
|
|
.. code-block:: java
|
|
|
|
// Cycle reporter — LinkedList.lastIndexOf in diagnostic output
|
|
private String formatCycle(LinkedList<String> cycle) {
|
|
int start = cycle.lastIndexOf(cycle.getLast()); // O(n) — lastIndexOf is linear
|
|
return cycle.subList(start, cycle.size()).stream()
|
|
.collect(Collectors.joining(" -> "));
|
|
}
|
|
|
|
**Why this is O(n):** ``LinkedList.lastIndexOf()`` traverses the entire list. This is in the
|
|
cycle-reporting path (diagnostic output), so it is cold-path and bounded by the cycle length.
|
|
|
|
**Complexity:** ``O(n)`` where n = cycle length (LOW severity — diagnostic path only)
|
|
|
|
**Patch:**
|
|
|
|
.. code-block:: java
|
|
|
|
// Use a Map to track node→index for O(1) lookup
|
|
private String formatCycle(List<String> path) {
|
|
Map<String, Integer> indexMap = new HashMap<>();
|
|
for (int i = 0; i < path.size(); i++) indexMap.put(path.get(i), i);
|
|
int start = indexMap.get(path.get(path.size() - 1));
|
|
return path.subList(start, path.size()).stream()
|
|
.collect(Collectors.joining(" -> "));
|
|
}
|
|
|
|
**Data structure change:** ``LinkedList`` + ``lastIndexOf`` → ``HashMap<String,Integer>`` index
|
|
|
|
**Status:** Unpatched
|
|
|
|
Complexity Proof
|
|
----------------
|
|
|
|
Let n = cycle length. ``LinkedList.lastIndexOf`` is O(n). Building a ``HashMap`` is O(n);
|
|
each lookup is O(1). For the diagnostic path this is academically correct but operationally
|
|
insignificant — cycles in Maven builds are short (usually 2-3 nodes). QED.
|
|
|
|
References
|
|
----------
|
|
|
|
* Defect ticket: ``tools/tickets/defects/maven-0003.md``
|