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
1.5 KiB
flink-0001: JobGraph user-jar dedup — List.contains() O(n²)
Target: Apache Flink
File: flink-runtime/src/main/java/org/apache/flink/runtime/jobgraph/JobGraph.java
CWE: CWE-407 — Inefficient Algorithmic Complexity
Severity: MEDIUM
Status: PATCHED
Description
JobGraph.addJar(Path) and addUserJarBlobKey(PermanentBlobKey) deduplicate entries
using List.contains() on ArrayList fields. Each call scans the entire list linearly.
When a job graph is constructed with N jar entries (via addJars(List<URL>)), total cost
is O(1) + O(2) + … + O(n) = O(n²).
// flink-runtime/.../JobGraph.java line 568
private final List<Path> userJars = new ArrayList<Path>(); // O(n) contains
private final List<PermanentBlobKey> userJarBlobKeys = new ArrayList<>(); // O(n) contains
public void addJar(Path jar) {
if (!userJars.contains(jar)) { // O(n) per call
userJars.add(jar);
}
}
public void addUserJarBlobKey(PermanentBlobKey key) {
if (!userJarBlobKeys.contains(key)) { // O(n) per call
userJarBlobKeys.add(key);
}
}
addJars(List<URL>) calls addJar() in a loop, making the total cost O(n²) for n jars.
Fix
Replace ArrayList with LinkedHashSet (preserves insertion order, O(1) contains/add)
and expose a List view via new ArrayList<>(set) only at read time.
Patch
defects/flink/patch/flink-0001.patch
Unit Test
defects/flink/unit/FlinkJobGraphJarDedupTest.java