# 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`

```java
// 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`

```java
// 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`

```java
// 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:

```java
// 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>`:

```java
// 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.
