java-topology/docs/tickets/jetty-0001-httpfields-quotedcsv-getvalues-list-contains.md

jetty-0001: HttpFields.formatCsvExcludingExisting — QuotedCSV.getValues() List.contains() O(n²)

Target: Eclipse Jetty File: jetty-core/jetty-http/src/main/java/org/eclipse/jetty/http/HttpFields.java CWE: CWE-407 — Inefficient Algorithmic Complexity Severity: MEDIUM Status: PATCHED

Description

HttpFields.Mutable.addCSV() (both header and name variants) calls the private helper formatCsvExcludingExisting(QuotedCSV existing, String... values). Inside that helper the loop iterates over all incoming values and calls existing.getValues().contains(unquoted) on each iteration.

QuotedCSV.getValues() returns the internal _values field, which is ArrayList<String> (line 107). Each .contains() call is therefore O(m) where m is the number of existing CSV values. With V values to add and M existing values, the total is O(V × M).

When addCSV() is called per-request (e.g. to add Vary or Cache-Control token lists), V and M grow with the number of directives/values, making this O(n²) under adversarial or large header inputs.

// HttpFields.java  line 1576-1591
private static String formatCsvExcludingExisting(QuotedCSV existing, String... values) {
    boolean add = true;
    if (existing != null && !existing.isEmpty()) {
        add = false;
        for (int i = values.length; i-- > 0; ) {
            String unquoted = QuotedCSV.unquote(values[i]);
            if (existing.getValues().contains(unquoted))   // O(m) scan per value → O(V×M)
                values[i] = null;
            else
                add = true;
        }
    }
    ...
}

// QuotedCSV.java  line 107
private final List<String> _values = new ArrayList<>();   // O(n) contains()

Fix

Convert the existing values to a HashSet<String> once before the loop, then call existingSet.contains(unquoted) at O(1) per lookup.

private static String formatCsvExcludingExisting(QuotedCSV existing, String... values) {
    boolean add = true;
    if (existing != null && !existing.isEmpty()) {
        add = false;
        Set<String> existingSet = new HashSet<>(existing.getValues()); // O(m) once
        for (int i = values.length; i-- > 0; ) {
            String unquoted = QuotedCSV.unquote(values[i]);
            if (existingSet.contains(unquoted))                        // O(1) per lookup
                values[i] = null;
            else
                add = true;
        }
    }
    ...
}

Patch

defects/jetty/patch/jetty-0001.patch

Unit Test

defects/jetty/unit/JettyHttpFieldsCsvTest.java