russell@unturf.com
9934133dcf
Add 88 new defect entries to HIGH and MEDIUM tables:
HIGH: mysql-0001/0002, mariadb-0001, redis-0001/0002, valkey-0001/0002, openvpn-0001,
vlc-0001, prometheus-0001, otel-collector-0001, cockroachdb-0001..0004,
tidb-0001..0008, kubernetes-0001/0002, go-0001, kotlin-0002, scala-0001,
allegro5-0001, sdl2-0001, grafana-0001, clickhouse-0001, duckdb-0001,
mongodb-0001, envoy-0001, istio-0001, cilium-0001, linkerd2-0001,
linux-0001/0002/0003, tor-0002/0003, curl-0001, julia-0001, lua-0001,
perl5-0001, nats-0001, spring-0003/0004, tomcat-0001, onos-0002, odl-0002
MEDIUM: helm-0001, mariadb-0002, openssl-0001/0002, memcached-0001,
cassandra-0001..0004, flink-0001, storm-0001/0002, zookeeper-0001..0003,
pip-0001, gradle-0001, nginx-0001, haproxy-0001, caddy-0001, varnish-0001,
ffmpeg-0001, gstreamer-0001, raylib-0001, love2d-0001, php-0001/0002,
r-source-0001, cpython-0002, ruby-0001, rabbitmq-0003/0004, activemq-0001,
ovs-0001, onos-0003, odl-0002, jetty-0001
PDF: 976K
255 lines
11 KiB
Java
255 lines
11 KiB
Java
package unit;
|
||
|
||
import java.util.ArrayList;
|
||
import java.util.HashSet;
|
||
import java.util.List;
|
||
import java.util.Set;
|
||
|
||
/**
|
||
* Unit test for CWE-407 jetty-0001:
|
||
* HttpFields.formatCsvExcludingExisting() calls existing.getValues().contains()
|
||
* inside a loop — List.contains() is O(M) per call, total O(V×M).
|
||
*
|
||
* Models the exact defect and fix without Jetty dependencies.
|
||
*
|
||
* Run: java -ea -cp . unit.JettyHttpFieldsCsvTest
|
||
*/
|
||
public class JettyHttpFieldsCsvTest {
|
||
|
||
// -----------------------------------------------------------------------
|
||
// Model of QuotedCSV.getValues() — returns ArrayList<String>
|
||
// -----------------------------------------------------------------------
|
||
|
||
static final class QuotedCsvValues {
|
||
final List<String> values;
|
||
QuotedCsvValues(List<String> values) { this.values = new ArrayList<>(values); }
|
||
public List<String> getValues() { return values; }
|
||
public boolean isEmpty() { return values.isEmpty(); }
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// Defective: mirrors HttpFields.formatCsvExcludingExisting() as-is
|
||
// -----------------------------------------------------------------------
|
||
|
||
static FilterResult formatCsvDefective(QuotedCsvValues existing, String... values) {
|
||
long probes = 0;
|
||
boolean add = true;
|
||
// Work on a copy so we can null out entries
|
||
String[] vals = values.clone();
|
||
if (existing != null && !existing.isEmpty()) {
|
||
add = false;
|
||
for (int i = vals.length; i-- > 0; ) {
|
||
String unquoted = vals[i];
|
||
probes += existing.getValues().size(); // O(M) per iteration
|
||
if (existing.getValues().contains(unquoted)) // ArrayList.contains()
|
||
vals[i] = null;
|
||
else
|
||
add = true;
|
||
}
|
||
}
|
||
return new FilterResult(add, vals, probes);
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// Fixed: build HashSet once before the loop
|
||
// -----------------------------------------------------------------------
|
||
|
||
static FilterResult formatCsvFixed(QuotedCsvValues existing, String... values) {
|
||
long probes = 0;
|
||
boolean add = true;
|
||
String[] vals = values.clone();
|
||
if (existing != null && !existing.isEmpty()) {
|
||
add = false;
|
||
Set<String> existingSet = new HashSet<>(existing.getValues()); // O(M) once
|
||
for (int i = vals.length; i-- > 0; ) {
|
||
String unquoted = vals[i];
|
||
probes += 1; // O(1) per lookup
|
||
if (existingSet.contains(unquoted))
|
||
vals[i] = null;
|
||
else
|
||
add = true;
|
||
}
|
||
}
|
||
return new FilterResult(add, vals, probes);
|
||
}
|
||
|
||
static final class FilterResult {
|
||
final boolean add;
|
||
final String[] filtered;
|
||
final long probes;
|
||
FilterResult(boolean add, String[] filtered, long probes) {
|
||
this.add = add; this.filtered = filtered; this.probes = probes;
|
||
}
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// Test 1 — correctness: null-out matching values, keep new ones
|
||
// -----------------------------------------------------------------------
|
||
static void test1_correctness() {
|
||
List<String> existingValues = List.of("gzip", "br", "deflate");
|
||
QuotedCsvValues existing = new QuotedCsvValues(existingValues);
|
||
|
||
// "gzip" already present, "zstd" is new
|
||
String[] incoming = {"gzip", "zstd"};
|
||
|
||
FilterResult def = formatCsvDefective(existing, incoming);
|
||
FilterResult fix = formatCsvFixed(existing, incoming);
|
||
|
||
assert def.add == fix.add
|
||
: "jetty-0001 correctness: add flag differs — defective=" + def.add + " fixed=" + fix.add;
|
||
assert def.filtered.length == fix.filtered.length
|
||
: "jetty-0001 correctness: filtered array length differs";
|
||
for (int i = 0; i < def.filtered.length; i++) {
|
||
assert java.util.Objects.equals(def.filtered[i], fix.filtered[i])
|
||
: "jetty-0001 correctness: filtered[" + i + "] differs: def=" + def.filtered[i] + " fix=" + fix.filtered[i];
|
||
}
|
||
|
||
// "gzip" should be nulled out (already in existing), "zstd" should survive
|
||
assert fix.filtered[0] == null : "jetty-0001 correctness: 'gzip' should be nulled (already existing)";
|
||
assert "zstd".equals(fix.filtered[1]) : "jetty-0001 correctness: 'zstd' should survive (new value)";
|
||
assert fix.add : "jetty-0001 correctness: add should be true because 'zstd' is new";
|
||
|
||
System.out.println("PASS test1_correctness: gzip nulled, zstd kept, add=true");
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// Test 2 — correctness: all values already present
|
||
// -----------------------------------------------------------------------
|
||
static void test2_correctness_all_existing() {
|
||
List<String> existingValues = List.of("gzip", "br", "deflate");
|
||
QuotedCsvValues existing = new QuotedCsvValues(existingValues);
|
||
String[] incoming = {"gzip", "br"};
|
||
|
||
FilterResult def = formatCsvDefective(existing, incoming);
|
||
FilterResult fix = formatCsvFixed(existing, incoming);
|
||
|
||
assert !def.add && !fix.add
|
||
: "jetty-0001 correctness: add should be false when all values already present";
|
||
for (int i = 0; i < fix.filtered.length; i++) {
|
||
assert fix.filtered[i] == null
|
||
: "jetty-0001 correctness: value at " + i + " should be null (already exists)";
|
||
}
|
||
|
||
System.out.println("PASS test2_correctness_all_existing: all nulled, add=false");
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// Test 3 — complexity: O(V×M) probes vs O(V) probes
|
||
// -----------------------------------------------------------------------
|
||
static void test3_complexity_ratio() {
|
||
// Small: M=10 existing, V=10 incoming
|
||
// Large: M=100 existing, V=100 incoming
|
||
int small = 10;
|
||
int large = 100;
|
||
|
||
List<String> smallExisting = new ArrayList<>();
|
||
List<String> largeExisting = new ArrayList<>();
|
||
for (int i = 0; i < small; i++) smallExisting.add("exist-" + i);
|
||
for (int i = 0; i < large; i++) largeExisting.add("exist-" + i);
|
||
|
||
// Incoming values are all new (no matches) — worst case for defective (always scan to end)
|
||
String[] smallIncoming = new String[small];
|
||
String[] largeIncoming = new String[large];
|
||
for (int i = 0; i < small; i++) smallIncoming[i] = "new-" + i;
|
||
for (int i = 0; i < large; i++) largeIncoming[i] = "new-" + i;
|
||
|
||
FilterResult defSmall = formatCsvDefective(new QuotedCsvValues(smallExisting), smallIncoming);
|
||
FilterResult defLarge = formatCsvDefective(new QuotedCsvValues(largeExisting), largeIncoming);
|
||
FilterResult fixSmall = formatCsvFixed(new QuotedCsvValues(smallExisting), smallIncoming);
|
||
FilterResult fixLarge = formatCsvFixed(new QuotedCsvValues(largeExisting), largeIncoming);
|
||
|
||
double defRatio = (double) defLarge.probes / defSmall.probes;
|
||
double fixRatio = (double) fixLarge.probes / fixSmall.probes;
|
||
|
||
System.out.printf(" defective probes: small=%d large=%d ratio=%.1fx%n",
|
||
defSmall.probes, defLarge.probes, defRatio);
|
||
System.out.printf(" fixed probes: small=%d large=%d ratio=%.1fx%n",
|
||
fixSmall.probes, fixLarge.probes, fixRatio);
|
||
|
||
// 10x input → ~100x probes (O(V×M))
|
||
assert defRatio > 50.0
|
||
: "jetty-0001 complexity: defective ratio should be >50x at 10x scale, got " + defRatio;
|
||
// 10x input → ~10x probes (O(V))
|
||
assert fixRatio < 20.0
|
||
: "jetty-0001 complexity: fixed ratio should be <20x at 10x scale, got " + fixRatio;
|
||
assert defRatio > fixRatio * 3
|
||
: "jetty-0001 complexity: defective should scale much worse, def=" + defRatio + " fix=" + fixRatio;
|
||
|
||
System.out.printf("PASS test3_complexity_ratio: defective=%.0fx fixed=%.0fx%n", defRatio, fixRatio);
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// Test 4 — absolute probe counts at V=M=50
|
||
// -----------------------------------------------------------------------
|
||
static void test4_absolute_counts() {
|
||
int N = 50;
|
||
List<String> existingValues = new ArrayList<>();
|
||
for (int i = 0; i < N; i++) existingValues.add("val-" + i);
|
||
|
||
// All incoming values are new (worst case: full scan per value)
|
||
String[] incoming = new String[N];
|
||
for (int i = 0; i < N; i++) incoming[i] = "new-" + i;
|
||
|
||
FilterResult def = formatCsvDefective(new QuotedCsvValues(existingValues), incoming);
|
||
FilterResult fix = formatCsvFixed(new QuotedCsvValues(existingValues), incoming);
|
||
|
||
// Defective: N values × N existing = N² probes (worst case, no early exit)
|
||
long expectedDefMin = (long) N * N;
|
||
assert def.probes >= expectedDefMin
|
||
: "jetty-0001 counts: defective probes=" + def.probes + " expected>=" + expectedDefMin;
|
||
|
||
// Fixed: exactly N probes (one per value, O(1) HashSet lookup)
|
||
assert fix.probes == N
|
||
: "jetty-0001 counts: fixed probes=" + fix.probes + " expected=" + N;
|
||
|
||
long speedup = def.probes / fix.probes;
|
||
System.out.printf("PASS test4_absolute_counts: defective=%d fixed=%d speedup=%dx%n",
|
||
def.probes, fix.probes, speedup);
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// Test 5 — edge case: null/empty existing → no loop entered
|
||
// -----------------------------------------------------------------------
|
||
static void test5_empty_existing() {
|
||
FilterResult def = formatCsvDefective(null, "gzip", "br");
|
||
FilterResult fix = formatCsvFixed(null, "gzip", "br");
|
||
|
||
assert def.probes == 0 && fix.probes == 0
|
||
: "jetty-0001 edge: null existing should produce 0 probes";
|
||
assert def.add && fix.add
|
||
: "jetty-0001 edge: null existing means all values should be added";
|
||
|
||
System.out.println("PASS test5_empty_existing: null existing → 0 probes, add=true");
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// main
|
||
// -----------------------------------------------------------------------
|
||
public static void main(String[] args) {
|
||
System.out.println("=== JettyHttpFieldsCsvTest — CWE-407 jetty-0001 ===");
|
||
int passed = 0;
|
||
int failed = 0;
|
||
|
||
Runnable[] tests = {
|
||
JettyHttpFieldsCsvTest::test1_correctness,
|
||
JettyHttpFieldsCsvTest::test2_correctness_all_existing,
|
||
JettyHttpFieldsCsvTest::test3_complexity_ratio,
|
||
JettyHttpFieldsCsvTest::test4_absolute_counts,
|
||
JettyHttpFieldsCsvTest::test5_empty_existing,
|
||
};
|
||
|
||
for (Runnable test : tests) {
|
||
try {
|
||
test.run();
|
||
passed++;
|
||
} catch (AssertionError e) {
|
||
System.out.println("FAIL: " + e.getMessage());
|
||
failed++;
|
||
}
|
||
}
|
||
|
||
System.out.println("---");
|
||
System.out.println("Results: " + passed + " passed, " + failed + " failed");
|
||
if (failed > 0) System.exit(1);
|
||
}
|
||
}
|