java-topology/whitepaper/outreach/kafka.md

Apache Kafka — CWE-407 Disclosure Brief

2026-03-26 · Patch available — awaiting upstream merge

Finding

Three O(n²) defects in Apache Kafka's sticky partition assignor. All patched. Patches ready for upstream review. All defects are in AbstractStickyAssignor.java — the base class for Kafka's sticky consumer group rebalancing algorithm.

The Defects

kafka-0001 (PATCHED — HIGH): clients/src/main/java/org/apache/kafka/clients/consumer/internals/AbstractStickyAssignor.java:1207

// currentAssignment: Map<String, List<TopicPartition>>
// Inside isBalanced() — called inside while(!isBalanced()) rebalance loop:
if (currentAssignment.get(consumer).contains(topicPartition)) { ... }

currentAssignment.get(consumer) returns a List<TopicPartition>. The .contains() call performs a linear scan over P previously-assigned partitions, called inside a triple-nested loop: for each consumer C, for each topic T, for each partition P. Total cost per isBalanced() call: O(C × T × P²).

kafka-0002 (PATCHED — MEDIUM): AbstractStickyAssignor.java:1267

// consumer2AllPotentialTopics: Map<String, List<String>>
// Inside maybeAssignPartition() — called per partition per consumer:
if (consumer2AllPotentialTopics.get(consumer).contains(partition.topic())) { ... }

consumer2AllPotentialTopics values are List<String>. The .contains() call scans T topic strings per call, called P × C times: O(P × C × T).

kafka-0003 (PATCHED — MEDIUM): AbstractStickyAssignor.java:1458

// Inside reassignPartition() — same consumer2AllPotentialTopics collection:
if (consumer2AllPotentialTopics.get(anotherConsumer).contains(partition.topic())) { ... }

Same root cause as kafka-0002 — same Map<String, List<String>> field, same O(T) .contains() per consumer scan. The kafka-0002 fix (changing field type to Map<String, Set<String>>) resolves kafka-0003 as a consequence.

Complexity Proof

kafka-0001: For C consumers, T topics, P partitions per topic:

• Outer loop: C consumers
• Middle loop: T topics per consumer
• Inner loop: P partitions per topic
• .contains() scan: up to P entries
• Total: C × T × P × P = O(C × T × P²)

At C=5, T=8, P=100: defective=1,201,000 comparisons, fixed=4,000. Measured ratio: 300×.

kafka-0002: For T topics, P total partitions, C consumers:

• Per-partition, per-consumer: O(T) .contains() scan
• Total: O(P × C × T)

At T=100, P=50, C=10: defective=2,525,000 comparisons, fixed=50,000. Measured ratio: 50×.

Impact

Every Kafka consumer group rebalance hits isBalanced(). Sticky assignment is the default partition.assignment.strategy as of Kafka 2.4+ (CooperativeStickyAssignor). Consumer groups with many partitions (high-throughput topics, heavily-partitioned clusters) and many consumers maximize P×T and hit the worst case on every rebalance.

Consumer group rebalances occur at startup, on member join/leave (rolling deploy, pod restart), on topic metadata change, and on consumer failure. In production Kafka clusters, rebalances are frequent — this overhead runs on every one.

The Fix

kafka-0001: Snapshot to HashSet<TopicPartition> before inner loops:

// Before
if (currentAssignment.get(consumer).contains(topicPartition)) { ... }

// After
// CWE-407 fix: snapshot to HashSet for O(1) contains() instead of O(P) List scan.
Set<TopicPartition> assignedSet = new HashSet<>(currentAssignment.get(consumer));
if (assignedSet.contains(topicPartition)) { ... }

kafka-0002: Store consumer2AllPotentialTopics values as Set<String>:

// Before
private Map<String, List<String>> consumer2AllPotentialTopics;

// After
// CWE-407 fix: Set<String> for O(1) contains() instead of O(T) List scan.
private Map<String, Set<String>> consumer2AllPotentialTopics;

TopicPartition and String both implement equals()/hashCode() — no additional changes needed.

Patch

Fix available: defects/kafka/patch/kafka-0001-0002-stickassignor-hashset.patch

Two-location change in AbstractStickyAssignor.java. No behavioral change — Set semantics match the existing membership-test use case exactly.

Unit test: 5/5 pass. kafka-0001 at C=5, T=8, P=100: defective=1,201,000 comparisons, fixed=4,000, 300× speedup. kafka-0002 at T=100, P=50, C=10: defective=2,525,000, fixed=50,000, 50× speedup.

What We Ask

A patch is ready for review.

1. Confirm receipt and assign a JIRA reference (KAFKA project at issues.apache.org/jira).
2. Assess severity — kafka-0001 fires on every consumer group rebalance with sticky assignment.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the Apache Kafka team in the public disclosure. Preferred acknowledgment format welcome.

Contact: see cover email. This brief is confidential until coordinated disclosure.